机器学习实战-2-KNN

机器学习实战-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个点所出现频率最高的类别作为当前点的预测分类。

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

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

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

图解过程

通过下面的一组图形来解释KNN算法的思想。

已知正方形和三角形两种类型，现在给定一个圆形，如何确定它是属于什么类型？

如果k=1，结果是三角形

如果k=3，结果还是三角形

如果k=5，结果是正方形

如果k=7，结果是正方形

通过上面的例子，我们得到一个结论：当k取不同值的时候，KNN算法的结果是不同的，所以k值的选取非常重要。

Python3版本代码

伪代码

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

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

Python3实现

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

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模块如何解决？

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个数并统计频数

封装成函数

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

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、《统计学习方法》-李航老师