第一篇：K-近邻分类算法原理分析与代码实现

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

前言

本文介绍机器学习分类算法中的K-近邻算法并给出伪代码与Python代码实现。

算法原理

首先获取训练集中与目标对象距离最近的k个对象，然后再获取这k个对象的分类标签，求出其中出现频数最大的标签。

而这个标签，就是分类的结果。

伪代码

对训练集做以下操作：

1. 计算训练集中各点与当前点之间的距离(本文采用最经典的欧式距离)

2. 按照距离递增次序对各点排序

3. 选取与当前点距离最小的k个点

4. 确定前k个点所在类别的出现频率

5. 返回前k个点出现频率最高的类别，即为分类结果。

特别说明：该算法中，因为没有训练步骤，因此对它而言训练集也就是数据集。

代码示例

#!/usr/bin/env python # -*- coding:UTF-8 -*- ''' Created on 2016-12-05 @author: fangmeng ''' # 导入numpy数学运算库 import numpy # 导入运算符函数库 import operator # ============================================== # 输入： # 空 # 输出： # group, labels：样本训练集及其对应标签集 # ============================================== def createDataSet(): '创建训练集及其对应标签集并返回' group = numpy.array([[1.0, 1.1], [1.0, 1.0], [0.0, 0.0], [0.0, 0.1]]) labels = ['A', 'A', 'B', 'B'] return group, labels # ============================================== # 输入： # inX：目标向量 # dataSet：训练集 # labels：训练集对应的标签集 # k：算法参数 # 输出： # sortedClassCount[0][0]：目标向量的分类结果 # ============================================== def classify0 (inX, dataSet, labels, k): 'kNN 分类器' #计算目标向量与训练集中所有对象的距离并排序 dataSetSize = dataSet.shape[0] diffMat = numpy.tile(inX, (dataSetSize, 1)) - dataSet sqDiffMat = diffMat ** 2 sqDistances = sqDiffMat.sum(axis=1) distances = sqDistances ** 0.5 sortedDistIndicies = distances.argsort()# 返回数组从小到大的索引值 # 取出与目标向量距离最近的三个 classCount = {} # 该字典存放各种标签及其对应的频数 for i in range(k): # 由前 k 位索引的结果构建字典 voteIlable = labels[sortedDistIndicies[i]] classCount[voteIlable] = classCount.get(voteIlable, 0)+1 # 以各个标签的频率为基准进行排序 sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True) return sortedClassCount[0][0] # 返回出现频率最高的标签 def test(): '分类器测试函数' # 新建训练集及其对应标签集 group, labels = createDataSet() # 输入目标向量并返回分类结果后打印 label = classify0([0.0, 0.0], group, labels, 3) print label if __name__ == '__main__': # 调用测试函数 test()

运行结果