机器学习之K近邻算法（KNN）

标签： python 算法 KNN 机械学习

---

苛求真理的欲望让我想要了解算法的本质，于是我开始了机械学习的算法之旅

from numpy import *  
import operator  
from collections import Counter

#KNN需要测试集，训练集，标签和k值
#测试集：你需要测试的数据
#训练集：给定的标准数据
#标签：每个标准数据的类别
#k值 ：测试集和训练集相比较下前K个最相识的训练集的值


# 用KNN算法找出测试集的类别
#1，求出已知类别训练集中的点与当前点之间的距离
#2，对所求距离以此递增排序
#3，选取与当前点距离最小的k个点
#4，确定前k个点所在类别的出现频率
#5，返回前k个点出现频率最高的类别作为当前点的预测分类

def kNNClassify(testSet, trainSet, labels, k=3):  
    rows = trainSet.shape[0] #shape[0]得到训练集的行数

    
    #求距离
    distSet = tile(testSet, (rows, 1)) - trainSet #得到距离矩阵
    distance = sum(distSet ** 2 , axis = 1) ** 0.5 # 求出距离

    #排序     
    #得到排序后数据原位置的下标，排序后位置是不变的 
    #从而使得排序后的结果和trainSet的标签一一对应
    #然后就可以通过排序结果反向得到标签值
    sortedDistIndices = argsort(distance) 
    
    
    #选取k个最小值 
    classCount = Counter()# 保存类别
    
    #记录k值内相同标签出现的次数
    [classCount.update([labels[sortedDistIndices[i]]]) for i in xrange(k)]
    
    ## 得到出现次数最多的标签类别 
    return sorted(classCount.iteritems(), key=lambda d:d[1], reverse = True )[0][0]


if __name__ == '__main__':
    
    #然后我们在命令行中测试
    trainSet = array([
            [1.0, 0.9], 
            [1.0, 1.0], 
            [0.1, 0.2], 
            [0.0, 0.1]])  
    labels = ['A', 'A', 'B','B'] # 4个标签,2种类别

    testSet = array([1.2, 1.0])  
    
    label = kNNClassify(testSet, trainSet, labels, k=3)  
    print "输入:", testSet, "分类: ", label  

    testSet = array([0.1, 0.3])  
    label = kNNClassify(testSet, trainSet, labels, k=3) 
    print "输入:", testSet, "分类: ", label    

输入: [ 1.2  1. ] 分类:  A
输入: [ 0.1  0.3] 分类:  B