机器学习1——K近邻算法

K近邻算法：一种基本的分类算法

基本内容#

输入：实例的特征向量

输出：实例的类别

思想：近朱者赤近墨者黑，对于输入实例x，选取距离x最近的K个点，x的分类结果就是K个点中数目最多的那个类别

三个要素：

• K的选择
• 距离的度量
• 分类决策规则

优点：精度高、异常值不敏感、无数据输入假定

缺点：计算复杂度高、空间复杂度高

适用数据范围：数值型、标称型

开发流程#

• 收集数据：任何方法
• 准备数据：距离计算所需要的数值，最好是结构化的数据格式
• 分析数据：任何方法
• 训练算法：此步骤不适用于 k-近邻算法
• 测试算法：计算错误率
• 使用算法：输入样本数据和结构化的输出结果，然后运行 k-近邻算法判断输入数据分类属于哪个分类，最后对计算出的分类执行后续处理

实战项目#

• 约会网站https://github.com/apachecn/AiLearning/blob/master/docs/ml/2.k-%E8%BF%91%E9%82%BB%E7%AE%97%E6%B3%95.md
• 手写数字识别https://github.com/apachecn/AiLearning/blob/master/docs/ml/2.k-%E8%BF%91%E9%82%BB%E7%AE%97%E6%B3%95.md

注意点在于使用数据前一定要对数据进行归一化，否则数据范围差距过大，会引起很大问题

归一化的方法#

• 线性函数转换：$y=(x-MinValue)/(MaxValue-MinValue)　　$
• 对数函数转换：$y=lg(x)　$ 是非线性转换，对x的取值范围有要求
• 反余切函数转换：$y=arctan(x)*2/PI　$，非线性转换，且对x的范围没有要求

三要素#

K的取值#

• K小时，近似误差小，估计误差大；K大时，近似误差大，估计误差小
• K小时，相当于用较小邻域中的训练实例进行预测，学习的近似误差会小，只有与输入实例相近的训练集样本才会对结果又影响。但缺点是学习误差会增大，如果恰好有噪声，则可能会出错。因此，K减小容易发生过拟合
• K大时，与上面相反
• 可以使用交叉验证选取合适的K值

PS:

• 近似误差：可以理解为对现有训练集的训练误差。
• 估计误差：可以理解为对测试集的测试误差。

距离度量#

通常是用欧氏距离，也可以是曼哈顿距离等

分类决策#

少数服从多数

核心算法#

• 暴力计算（Brute Force）
• 二叉树平分参数空间（KD Tree）
• 超球体平分训练数据 (Ball Tree)

具体可以看sklean文档 https://github.com/apachecn/sklearn-doc-zh/blob/master/docs/master/7.md

clf = neighbors.KNeighborsClassifier(k, weights='uniform') # weights选用uniform是所有维度数据权重一致
clf.fit(trainingMat, trainLabels)
pridects = clf.predict(testMat)