Machine Learning in Action:KNN Algorithm
概述
在分类问题中，核心的任务即为找到对应数据集上合适的分类方法。而机器学习中的另一个主要任务则是回归分析,例如CTR预测等应用领域。根据是否带有标签,机器学习算法可分为有监督学习和无监督学习两大类,其中无监督学习的经典代表算法为聚类算法,相比之下有监督学习的方法更为丰富多样,基本涵盖了各类回归类算法的核心要素。按照是否包含可调节参数,算法可分为有参数模型和无参数模型及半参数模型三类:具有parameter model具备两个显著特征,即利用训练数据获取的信息并通过target function进行建模以实现收敛;而完全不带parameter的无parameter model则直接存储训练数据而不依赖于任何parameter来进行建模;半parameter model则兼具两者的特性,即必然包含parameter但仍然能够实现收敛,其中最为经典的代表便是神经网络model理论体系完善的神经网络model理论上能够拟合任意形式的目标函数;只要提供足够的训练样本量就能保证其收敛性,因为其hypothesis space能够涵盖所有可能的目标函数类型
选择合适的机器学习算法需要综合考虑两个维度:一是该算法的设计目的是什么?二是所处理的数据情况如何?开发一个开放式的机器学习程序通常会经历以下几个关键步骤:首先是数据收集阶段;其次是数据预处理环节;然后是特征分析阶段;接着是算法选择与训练过程;最后是评估与优化阶段
KNN Algorithm
KNN算法属于近邻算法的一种，在之前的章节6中已有详细阐述。KNN的VC维为无穷大，并不会超过最优分类器两倍的效果（如需进一步了解相关内容可参考章节6的相关博客）。该算法的优势显而易见：无需经过复杂的训练过程即可直接应用到测试数据上（即无需存储训练数据即可进行预测），操作简便且易于上手（即直接使用测试数据即可获得预测结果）。此外该算法还具有较高的预测精度（即对异常值较为稳健），对于超出预期的数据点也不会产生显著影响（即即使有少量异常值也无需担心预测结果受到较大波动）。另外该算法对输入数据并没有做出特定的假设（即无需满足特定的数据分布条件）。
尽管看似完美无缺但事实上training cost并未消失而是转移到了预测阶段并且会导致空间复杂度升高（即每次都需要重新计算距离并排序）
工作原理非常简单：首先建立一个包含样本数据集以及每个样本对应的标签的数据集（即训练样本集）。输入新数据后系统会计算其与现有样本中最近的k个邻居并根据这些邻居的标签进行投票最终得出分类结果（其中k的选择应避免导致两个类别得票相同的情况）
在计算前必须定义相似度衡量标准前面的文章也对此进行了详细讨论
伪代码
首先需要计算已知类别数据集中各点与当前待分类样本之间的距离度量。然后对这些距离进行排序，并选择其中距离最小的前K个样本。统计这K个样本中各类别出现的频数统计方法即为待分类样本所属类别的判断依据。通常情况下,K值取3被认为是一个合理的选择。然而,提高K值带来的精度提升并不值得与其带来的计算成本增加相抵消。例如，在实际应用中,K=3时准确率达到97%,而当增加到5时仅提升到97.1%,这种微小的进步在实际应用中并不值得投入额外的时间和资源
from numpy import *
import operator
class KNN(object):
@staticmethod
def classify(inX, dataSet, labels, k):
datasetsize = dataSet.shape[0]
diffmat = tile(inX, (datasetsize, 1)) - dataSet
sqdiffMat = diffmat *
sqdistance = sqdiffMat.sum(axis=1)
distance = sqdistance ** 0.5
sortDistance = distance.argsort()
classcount = {}
for i in range(k):
voteLabel = labels[sortDistance[i]]
classcount[voteLabel] = classcount.get(voteLabel, 0) + 1
sortclasscount = sorted(classcount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortclasscount[0][0]这即是具体的实现方案。觉得较为繁琐的是在上述使用numpy.tile进行操作的部分。该方法属于数组复制技术，在其参数形式为（a, b）时的具体作用机制是将基础数组沿纵向方向重复a次后再沿横向方向重复b次以完成扩展。这种操作方式是为了满足每个数据点对应一个训练集的需求而设计的简便途径
使用KNN改进约会网站配对效果
约会网站可为用户提供三种不同类型的选项：不太合适的人、中等吸引力的用户以及特别有吸引力的客户。
实现步骤
收集原始数据，并接收输入文本作为分析对象。
进行预处理工作，在Python环境下对文件内容进行解析和处理。
提取特征并进行可视化展示以辅助理解。
构建无监督学习模型（如KNN），该模型在 training set上表现完美。
对模型进行验证测试，并确保其泛化能力良好。
将优化后的方法应用于实际项目中。
准备数据
数据包含有以下三种指标：每年飞行常客获得的里程数、玩游戏视频所占时间百分比、每周冰淇淋消费量。展示数据分布情况。
@staticmethod
def drawDataSet(X, Y):
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(X[:, 1], X[:, 2])
plt.show()
这里只是使用了第一和第二个特征，加上类别颜色：
最后试一下之后会发现，23，13，12列得到的分布差不多一样的，只有12列是不同：
数据归一化
计算出的数据规模差异导致的距离结果存在差异；其中第一个指标的数据全部采用千为单位表示；而后两个指标的数据规模较小；因此必须对各指标进行归一化处理使其统一采用相同的量纲单位。
@staticmethod
def autoNorm(dataSet):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataset = np.zeros(shape(dataSet))
m = dataSet.shape[0]
normDataset = dataSet - tile(minVals, (m, 1))
normDataset = normDataset / tile(ranges, (m, 1))
return normDataset, ranges, minVals测试数据
还是可以的
手写数字识别
所有的手写数字都是这个样子。预测效果，代码就不贴了，很普通。
还可以接受。但当KNN算法应用于基于图片相似度的任务时可能会遇到困难；因为当图像在某些区域存在一致性（通常由相同的背景区域组成）时容易导致误判；例如一张图像显示一辆汽车而另一张显示一架飞机但两张图像均具有广泛的天空背景区域时可能出现误判情况；该算法基于实例进行学习因此需要与实际训练样本高度相似的数据集才能有效工作并且需要存储所有相关的训练样本；在处理大量数据时该方法可能导致计算开销增加从而影响计算效率；此外它无法提供任何关于数据基础结构信息也无法区分平均实力样本与典型样例之间的特征差异