机器学习算法-k近邻

2021-03-01 10:31:12 浏览数 (1)

机器学习实战-2-K近邻算法

本文中介绍的机器学习中最基础的一个算法：k-近邻算法，将从如下方面展开：

算法概述

k近邻法(k-nearest neighbor, k-NN)是1967年由Cover T和Hart P提出的一种基本分类与回归方法。简单地说，k-近邻算法就是采用不同特征值之间的距离来进行分类，算法主要特点为：

  • 优点：精度高，对异常值不敏感，没有数据输入假定
  • 缺点：计算复杂度高，空间复杂度高
  • 适用数据范围：数值型和标称型（男女）

有人曾经统计过很多电影的打斗镜头和接吻镜头，如下图显示的电影打斗镜头和接吻镜头：

假设有一部未看过的电影，如何确定它是爱情片还是动作片呢？我们看看下表的数据：

当我们不知道未知电影史属于何种类型，我们可以通过计算未知电影和其他电影的距离，按照电影的递增排序，可以找到k个距离最近的电影。在距离最近的电影中，选择类别最多的那部电影，即可判断为未知电影的类型。

比如k=5，这5部电影中3部是爱情片，2部是动作片，那么我们将未知电影归属为爱情片。

工作原理
  1. 存在一个样本数据集和数据标签，知道样本和标签的对应关系
  2. 输入没有标签的数据，将新数据的每个特征与样本集中数据对应的特征进行比较
  3. 提取样本集中特征最相似数据的分类标签，只选取前k个最相似的数据，一般k是小于20
算法步骤
  • 计算已知类别数据集中的点与当前点之间的距离；
  • 按照距离递增次序排序；
  • 选取与当前点距离最小的k个点；
  • 确定前k个点所在类别的出现频率；
  • 返回前k个点所出现频率最高的类别作为当前点的预测分类。

机器学习中向量距离度量准则

下面?列举了机器学习中常用的向量距离度量准则：

  • 欧式距离
  • 曼哈顿距离
  • 切比雪夫距离
  • 马氏距离
  • 巴氏距离
  • 汉明距离
  • 皮尔逊系数
  • 信息熵

图解过程

Python3版本代码

伪代码

首先给出KNN算法的伪代码（对未知类别属性的数据集中的每个点依次执行以下操作）：

  1. 计算已知类别数据集中的点和当前点之间的距离
  2. 按照距离递增次序排序
  3. 选取与当前距离最小的k个点
  4. 确定k个点所在类别的出现频率
  5. 返回前k个点出现频率最高的类别作为当前点的预测分类
Python3实现

下面给出实际的Python3的代码。使用内置的collections模块来解决：

代码语言：txt复制
import pandas as pd
import numpy as np
import collections


"""
名称：创建数据集
参数：无
返回值：
    group - 数据集
    labels - 分类标签
"""

def createData():  # 创建数据集的函数
    # 四组二维特征
    group = np.array([  
        [1,101],  # 第1个数表示打斗次数，第2个表示接吻次数
        [5,89],
        [108,5],
        [115,8]
    ])
    # 每个特征对应的标签
    labels = ["爱情片","爱情片","动作片","动作片"]
    # 返回每个特征和标签值
    return group, labels  


"""
名称：KNN算法，分类器
参数：
    inX：用于分类的数据，测试集
    dataSet：用于训练的数据集，训练集
    labels：分类标签
    k：算法参数，选择距离最小的k个点
"""

def classify(inX,dataSet,labels,k):
    # 计算欧式距离
    dist = np.sum((inX-dataSet) ** 2, axis=1) ** 0.5
    print("dist:",dist)
    # k个最近的标签:
    # argsort()：距离从小到大排列，取出前k个数据；将前k个对应的label标签全部取出来
    k_labels = [labels[index] for index in dist.argsort()[0:k]]
    print("k_labels:",k_labels)
    # 出现最多次数的标签即为最终类别
    label = collections.Counter(k_labels).most_common(1)[0][0]
    print("label:",label)
    
    return label


if __name__ == "__main__":
    # 创建数据集
    group ,labels = createData() 
    # 传入测试数据
    test = [98,17]
    # KNN分类
    test_class = classify(test,group,labels,3)
    # 打印结果
    print("test_class:",test_class)

运行上面的代码，显示的结果为：

  • dist：待预测的电影和已知电影欧式距离
  • k_labels：取出排序后前（k=3）3个最小距离的电影对应的类别标签，结果是["动作片","动作片","爱情片"]
  • label：判断的结果是动作片，因为动作片有2票
代码解释

1、函数首先需要生成数据集：关于给出的前4部电影，已知打斗次数和接吻次数，同时还有电影的分类情况；

2、现在新出现了一部电影：打斗次数是98，接吻次数是17，如何确定其属于哪种类型的电影？

打斗次数

接吻次数

电影分类

1

1

101

爱情片

2

5

89

爱情片

3

108

5

动作片

4

115

8

动作片

待预测

98

17

？

不使用collections模块如何解决？

代码语言：txt复制
import numpy as np
import operator  

"""
名称：创建数据集
参数：无
返回值：
    group - 数据集
    labels - 分类标签
"""

def createData():  # 创建数据集的函数
    # 四组二维特征
    group = np.array([  
        [1,101],  # 第1个数表示打斗次数，第2个表示接吻次数
        [5,89],
        [108,5],
        [115,8]
    ])
    # 每个特征对应的标签
    #  labels 包含的元素个数等于group矩阵的行数
    labels = ["爱情片","爱情片","动作片","动作片"]
    # 返回每个特征和标签值
    return group, labels  


"""
名称：KNN算法，分类器
参数：
    inX：用于分类的数据，测试集
    dataSet：用于训练的数据集，训练集
    labels：分类标签
    k：算法参数，选择距离最小的k个点
返回值: sortedClassCount[0][0]  分类结果
欧式距离计算：
    dis = ((x_2-x_1)^2   (y_2-y_1)^2) ** 0.5 
"""

def classify(inX,dataSet,labels,k):
    # shape函数返回行数和列数
    datasetsize = dataSet.shape[0]  # 返回的是行数 
    
    # 将待预测的数据（datasetsize, 1)的大小
    diffMat = np.tile(inX, (datasetsize, 1)) - dataSet
    print("tile：n", np.tile(inX, (datasetsize, 1)))
    
    # 二维特征相减再平方
    sqDiffMat= diffMat ** 2
    # sum(0)行相加，sum(1)列相加
    sqDistances = sqDiffMat.sum(axis=1)
    
    # 开方求出距离
    distances = sqDistances ** 0.5
    print("距离大小：n", distances)
    # 返回从小到大排序后的索引值
    sortedDistIndices = distances.argsort()  
    print("排序后的索引值：n",sortedDistIndices)
    
    # 假定一个字典来记录类别的次数
    classCount = {}
    for i in range(k):
        # 取出前k个元素的类别
        voteLabel = labels[sortedDistIndices[i]]
        # 字典的get方法：dict.get(key,default=None)，返回指定的值，如果不存在则返回的是默认值
        classCount[voteLabel] = classCount.get(voteLabel,0)   1
    
        
    # reverse降序排序字典
    # operator.itemgetter(1)：对值进行排序
    # operator.itemgetter(0)：对键进行排序
    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    # 返回次数最多的类别，即所要的分类结果
    return sortedClassCount[0][0]


if  __name__ == "__main__":
    # 创建数据集
    group, labels = createData()
    # 待预测数据
    test = [98,20]
    # KNN分类
    test_class = classify(test,group,labels,3)
    # 打印结果
    print(test_class)

classfiy函数有4个输入参数：

  1. 用于分类的输入向量inX
  2. 输入的训练样本集合为dataSet
  3. 标签向量为labels
  4. 用于选择最近邻居的数目k

其中标签向量的元素数目和矩阵dataSet的行数相同

看看具体的解释：

1、原始数据是什么样子？

打印出来的效果：

2、为什么使用np.tile方法？

为了和dataSet的shape保持一致，方便后续的求距离

3、每个距离和相对的索引关系

Jupyter notebook中使用KNN算法

步骤

下面也是通过一个模拟的电影数据来讲解如何在jupyter notebook中使用KNN算法，大致步骤分为：

  1. 构建数据集

构建一个包含接吻镜头、打斗镜头和电影类型的数据集

2、求距离

求出待预测分类的数据和原数据的欧式距离

3、距离排序

将求出的距离进行升序排列，并取出对应的电影分类

4、指定取出前k个数据

取出指定的前k个数据，统计这些数据中电影类型的频数，找出频数最多的类型，即可判断为未知待预测电影的类型

代码

1、模拟数据：

2、求解距离

3、对距离升序排列

4、取出前k个数并统计频数

封装成函数

将上面的整个过程封装成函数：

代码语言：txt复制
import pandas as pd

"""
函数功能：KNN分类器

参数说明：
    inX：待预测分类的数据
    dataSet：原数据集，训练集
    k：k-近邻算法中的超参数k
    
返回值：分类结果

"""

def classify0(inX, dataSet,k):
    result = []
    
    # 1、求新数据和每个原数据的距离
    dist = list(((data.iloc[:6,1:3] - new_data) ** 2).sum(1) ** 0.5)
    # 2、将求出的距离和电影标签放在一起
    dist_labels = pd.DataFrame({"dist":dist,"labels":data["电影类型"].tolist()})
    # 3、根据距离升序排列，取出前k个
    dist_sorted = dist_labels.sort_values(by="dist")[:k]
    # 4、排序之后取出标签，并统计频数
    res = dist_sorted.loc[:,"labels"].value_counts()
    result.append(res.index[0])
    
    return result

利用上面模拟的数据测试一下我们封装的代码，结果是相同的

参考资料

1、《机器学习实战》一书

2、机器学习实战教程（一）：K-近邻算法（史诗级干货长文）

3、《统计学习方法》-李航老师

机器学习 人工智能 数据挖掘

0 人点赞