k-近邻算法(kNN)

「爱情、让人受尽委屈。」 2022-06-04 04:23 181阅读 0赞

**kNN的工作原理：**  
存在一个样本数据集合，也称作样本训练集，并且样本集中每个数据都存在标签，即样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法个提取样本集中特征最详细数据（最近邻）的分类标签。一般来说，只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中的k值，通常k为不大于20的整数。

**kNN的伪代码：**  
对未知类似属性的数据集中的每个点依次执行以下操作：

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

**kNN.py：**

#-*- coding: utf-8 -*-
    from numpy import *
    import operator
    
    def createDataSet():
        group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]]) #训练集
        labels = ['A', 'A', 'B', 'B'] #标签
        return group, labels
    
    def classify0(inX, dataSet, labels, k): #inX为用于分类的输入向量，dataSet为输入的训练样本集， labels为训练标签，k表示用于选择最近的数目
        dataSetSize = dataSet.shape[0] #dataSet的行数
        diffMat = tile(inX, (dataSetSize, 1)) - dataSet #将inX数组复制成与dataSet相同行数，与dataSet相减，求坐标差
        sqDiffMat = diffMat**2 #diffMat的平方
        sqDistances = sqDiffMat.sum(axis=1) #将sqDiffMat每一行的所有数相加
        distances = sqDistances**0.5 #开根号，求点和点之间的欧式距离
        sortedDistIndicies = distances.argsort() #将distances中的元素从小到大排列，提取其对应的index，然后输出到sortedDistIndicies
        classCount = {} #创建字典
        for i in range(k):
            voteIlabel = labels[sortedDistIndicies[i]] #前k个标签数据
            classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1 #判断classCount中有没有对应的voteIlabel，
            # 如果有返回voteIlabel对应的值，如果没有则返回0，在最后加1。为了计算k个标签的类别数量
        sortedClassCount = sorted(classCount.items(),
                                  key=operator.itemgetter(1), reverse=True) #生成classCount的迭代器，进行排序，
                    # operator.itemgetter(1)以标签的个数降序排序
        return sortedClassCount[0][0] #返回个数最多的标签
    
    #测试分类器
    group, labels = createDataSet()
    label = classify0([1,1], group, labels, 3)
    print(label)
    
    >>A