前言
本文介绍机器学习分类算法中的K-近邻算法并给出伪代码与Python代码实现。
算法原理
首先获取训练集中与目标对象距离最近的k个对象，然后再获取这k个对象的分类标签，求出其中出现频数最大的标签。
而这个标签，就是分类的结果。
伪代码
对训练集做以下操作：
1. 计算训练集中各点与当前点之间的距离(本文采用最经典的欧式距离)
2. 按照距离递增次序对各点排序
3. 选取与当前点距离最小的k个点
4. 确定前k个点所在类别的出现频率
5. 返回前k个点出现频率最高的类别，即为分类结果。
代码示例
1 #!/usr/bin/env python 2 # -*- coding:UTF-8 -*- 3 4 ''' 5 Created on 20**-**-** 6 7 @author: fangmeng 8 ''' 9 10 # 导入numpy数学运算库 11 import numpy 12 # 导入运算符函数库 13 import operator 14 15 # ============================================== 16 # 输入： 17 # 空 18 # 输出： 19 # group, labels：样本训练集及其对应标签集 20 # ============================================== 21 def createDataSet(): 22 '创建训练集及其对应标签集并返回' 23 24 group = numpy.array([[1.0, 1.1], [1.0, 1.0], [0.0, 0.0], [0.0, 0.1]]) 25 labels = ['A', 'A', 'B', 'B'] 26 27 return group, labels 28 29 # ============================================== 30 # 输入： 31 # inX：目标向量 32 # dataSet：训练集 33 # labels：训练集对应的标签集 34 # k：算法参数 35 # 输出： 36 # sortedClassCount[0][0]：目标向量的分类结果 37 # ============================================== 38 def classify0 (inX, dataSet, labels, k): 39 'kNN 分类器' 40 41 #计算目标向量与训练集中所有对象的距离并排序 42 dataSetSize = dataSet.shape[0] 43 diffMat = numpy.tile(inX, (dataSetSize, 1)) - dataSet 44 sqDiffMat = diffMat ** 2 45 sqDistances = sqDiffMat.sum(axis=1) 46 distances = sqDistances ** 0.5 47 sortedDistIndicies = distances.argsort() # 返回数组从小到大的索引值 48 49 # 取出与目标向量距离最近的三个 50 classCount = {} # 该字典存放各种标签及其对应的频数 51 for i in range(k): # 由前 k 位索引的结果构建字典 52 voteIlable = labels[sortedDistIndicies[i]] 53 classCount[voteIlable] = classCount.get(voteIlable, 0)+1 54 55 # 以各个标签的频率为基准进行排序 56 sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True) 57 58 return sortedClassCount[0][0] # 返回出现频率最高的标签 59 60 def test(): 61 '分类器测试函数' 62 63 # 新建训练集及其对应标签集 64 group, labels = createDataSet() 65 66 # 输入目标向量并返回分类结果后打印 67 label = classify0([0.0, 0.0], group, labels, 3) 68 print label 69 70 if __name__ == '__main__': 71 # 调用测试函数 72 test()
运行结果
小结
1. 本文简要介绍了机器学习中经典的K-近邻算法，并给出了代码实现。
2. 该算法的缺点有三个：
a. 耗费空间资源大：要保存整个数据集
b. 耗费时间资源大：要对数据集中的每个样本求距离。当样本很多，或者特征信息多的时候，效率是挺坑的。
c. 没有给出数据的基础结构信息。(本身K-近邻算法就没有严格意义上的训练过程)
3. 后面的文章中，将讲解如何将此算法应用于具体项目中。