自学教程：Python机器学习实战之k-近邻算法的实现

K-近邻算法概述

简单地说, k-近邻算法采用测量不同特征值之间的距离方法进行分类。

k-近邻算法

• 优点：精度高、对异常值不敏感、无数据输入假定。
• 缺点: 计算复杂度高、空间复杂度高。

适用数据范围: 数值型和标称型。

工作原理

• 存在一个样本数据集合, 也称作训练样本集, 并且样本集中每个数据都存在标签, 知道样本集中每一数据与所属分类的对应关系。
• 输入没有标签的新数据后, 将新数据的每个特征与样本集中数据对应的特征进行比较, 然后算法提取样本集中特征最相似数据 (最近邻)的分类标签。
• 一般来说, 只选择样本数据集中前 k个最相似的数据, 这就是k-近邻算法中k的出处, 通常 k 是不大于 20 的整数。
• 最后, 选择 k个最相似数据中出现次数最多的分类, 作为新数据的分类。

k-近邻算法的一般流程

1. 收集数据: 可以使用任何方法。
2. 准备数据: 距离计算所需要的数值, 最好是结构化的数据格式。
3. 分析数据: 可以使用任何方法。
4. 训练算法: 此步骤不适用于 k-近邻算法。
5. 测试算法: 计算错误率。
6. 使用算法: 首先需要输入样本数据和结构化的输出结果, 然后运行 k-近邻算法判定输 入数据分别属于哪个分类, 最后应用对计算出的分类执行后续的处理。

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

group, labels = createDataSet()

group

array([[1. , 1.1],       [1. , 1. ],       [0. , 0. ],       [0. , 0.1]])

labels

['A', 'A', 'B', 'B']

a = tile([3,3],(4,1))a

array([[3, 3],       [3, 3],       [3, 3],       [3, 3]])

实施KNN算法

其伪代码如下:

对末知类别属性的数据集中的每个点依次执行以下操作:

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

def classify0(inX, dataSet, labels, k):    dataSetSize = dataSet.shape[0]    diffMat = 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):        voteIlabel = labels[sortedDistIndicies[i]]        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1    sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1), reverse=True)    return sortedClassCount[0][0]

classify0([0,0],group,labels,3)

'B'

示例：手写识别系统

数据集如下图：

示例: 使用k-近邻算法的手写识别系统

1. 收集数据: 提供文本文件。
2. 准备数据: 编写函数 classify0(), 将图像格式转换为分类器使用的list格式。
3. 分析数据: 在Python命令提示符中检查数据, 确保它符合要求。
4. 训练算法: 此步骤不适用于 k-近邻算法。
5. 测试算法: 编写函数使用提供的部分数据集作为测试样本, 测试样本与非测试样本 的区别在于测试样本是已经完成分类的数据, 如果预测分类与实际类别不同, 则标记 为一个错误。
6. 使用算法：本例没有完成此步骤，若你感兴趣可以构建完整的应用程序，从图像中提 取数字, 并完成数字识别, 美国的邮件分栋系统就是一个实际运行的类似系统。

图像转换为向量
Python Django项目和应用的创建详解
python