机器学习算法——k-近邻(KNN)案例讲解

大潘的这篇文章参考了《机器学习实战》这本书，这是一本很优秀的机器学习入门书籍。

需要这本书的电子版的小伙伴可以在后台回复: 机器学习实战 获取！

《机器学习实战》封面

目录：

1.工作原理

2.代码实现

（1）创建样本数据集

（2）实现k-近邻算法

（3）创建测试集

KNN(k-近邻)实现电影主题分类

1. 工作原理

k近邻法(k-nearest neighbor, k-NN)是1967年由Cover T和Hart P提出的一种基本分类与回归方法。它的工作原理是：存在一个样本数据集合，也称作为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本最相似数据(最近邻)的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

举个例子你就懂了：我们通过统计一部电影里面接吻次数和打斗次数，并使用k-近邻算法来分类爱情片和动作片。如果一部电影里面有很多（比如100次）的接吻镜头，很少（比如3次）的打斗镜头，那么这部电影分为哪一类呢？肯定是爱情片吧，相反，如果一部电影里面有很多的打斗镜头，很少的接吻镜头，那么这部电影就会被划分为动作片。

所以，首先我们需要知道待分类的电影里面有多少次的接吻镜头和打斗镜头。下图是几部电影的接吻和打斗的次数的散点图：

下图是具体的每部电影打斗镜头的次数、接吻镜头的次数以及电影的类型：

‘？’是待分类的电影，它有18次的打斗镜头和90次的接吻镜头，凭你的感觉，你觉得这部电影属于什么类型呢？（肯定是爱情片吧，下面就用k-近邻算法和Python来实现一下分类）

即使不知道电影属于哪一类型，我们可以通过计算未知电影和样本集中电影（其余四部电影）的“距离”，用k-近邻算法来实现。下图是已知类型的电影与未知类型的电影的距离：

未知电影到其他已知类型电影的“距离”

已知距离之后，按照距离递增的顺序，可以找到k个距离最近的电影。假定k=3，则三个最靠近的电影依次是He's Not Really into Dudes、Beautiful Woman和California Man。k-近邻算法按照距离最近的三部电影类型，决定未知电影的类型，而这三部电影全是爱情片，因此我们判断该电影是爱情片。

讲解完原理之后，下面是Python代码实现：

2.代码实现

（1）创建样本数据集

# 四组二维特征
group = np.array([[1, 101], [5, 89], [108, 5], [115, 8]])
# 四组特征的标签
labels = ['爱情片', '爱情片', '动作片', '动作片']

（2）实现k-近邻算法

大致思路就是计算测试样本到每个点的欧几里得距离（下面代码的1—6行都是在做这件事），再得到最近的k部电影中，每个类型电影的个数，并按照数量降序的顺序排列，之后拿到数量最多的电影的类型，作为待分类电影的类型。

欧几里得距离

def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]  # numpy函数shape[0]：返回dataSet的行数
    diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet  # 在列向量方向上重复inX共1次(横向)，行向量方向上重复inX共dataSetSize次(纵向)
    sqDiffMat = diffMat ** 2  # 二维特征相减后平方
    sqDistances = sqDiffMat.sum(1)  # sum()所有元素相加，sum(0)列相加，sum(1)行相加
    distances = sqDistances ** 0.5  # 开方，计算出距离（欧式距离）
    sortedDistIndices = distances.argsort()  # 返回distances中元素从小到大排序后的索引值
    classCount = {}  # 先定义一个记录类别次数的字典
    for i in range(k):#遍历k次，取出k部电影的类型
        voteIlabel = labels[sortedDistIndices[i]]  # 取出第i个元素的类别
        # 计算距离最近的k部电影中，每个类别电影的个数:
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1 #字典的get()方法,返回指定键的值,如果值不在字典中添加进去，并返回默认值。
    # key=operator.itemgetter(1)根据字典的值进行排序
    # key=operator.itemgetter(0)根据字典的键进行排序
    # reverse降序排序字典
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    # 返回次数最多的类别,即所要分类的类别
    return sortedClassCount[0][0]

（3）创建测试集

给定测试样本，调用上一步的classify0()方法，打印出分类结果：

# 测试集
testData = [110, 10]#测试样本中打斗和接吻的次数
# 调用classify0方法进行kNN分类：
test_class = classify0(testData, group, labels, 3)
# 打印分类结果
print(test_class)

打印结果：

打印结果

可知，打斗110次，接吻10次的电影分为了动作片。这样就通过KNN实现了简单的电影分类。

其实这就已经是全部代码了，完整代码只是增加了几段注释文字，如果有需要完整代码的小伙伴可以在公众号后台回复 knn 即可获取！