k近邻（k-NN）算法
发布时间
阅读量：
阅读量
k近邻算法的基本概念，原理
- K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。
- K近邻算法原理即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例，这K个实例的多数属于某个类，就把该输入实例分类到这个类中。
k近邻算法中距离的度量
k近邻模型的特征空间一般是n维实数向量空间Rn,使用的距离是欧式距离,但也可以是其他距离,如更一般的Lp距离(Lpdistance)或Minkowski距离(Minkowski distance).
其中当p=2的时候，就是我们最常见的欧式距离，我们也一般都用欧式距离来衡量我们高维空间中俩点的距离。
k近邻算法中k的选取
当 k=1 时的k近邻算法称为最近邻算法，此时将训练集中与xx最近的点的类别作为xx的分类。
k值的选择会对k近邻法的结果产生重大影响.
如果选择较小的k值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差会减小，只有与输入实例较近的(相似的)训练实例才会对预测结果起作用.但缺点是“学习”的估计误差会增大，预测结果会对近邻的实例点非常敏感 如果邻近的实例点恰巧是噪声，预测就会出错．
换句话说，k值的减小就意味着整体模型变得复杂，容易发生过拟合.
如果选择较大的k值，就相当于用较大邻域中的训练实例进行预测．
其优点是可以减少学习的估计误差．但缺点是学习的近似误差会增大．这时与输入实例较远的（不相似的）训练实例也会对预测起作用，使预测发生错误．k值的增大就意味着整体的模型变得简单.
如果k=N，那么无论输入实例是什么，都将简单地预测它属于在训练实例中最多的类．这时，模型过于简单，完全忽略训练实例中的大量有用信息，是不可取的.
在应用中，k值一般取一个比较小的数值．通常采用交叉验证法来选取最优的k值.
本文使用k=3 来演示核心算法
k近邻算法核心程序
Python实现
import operator
import numpy as np
def calculateDistances(test_in, train_dataSet):
"""计算inX到各个点的距离"""
dataSetSize = train_dataSet.shape[0]
# tile函数是将原矩阵横向、纵向地复制
# 这里是将输入的in复制为行:dataSetSize 列1的矩阵
diffMat = np.tile(test_in, (dataSetSize, 1)) - train_dataSet
# 先平方和再开方
distances = (diffMat ** 2).sum(axis=1) ** 0.5
return distances
def classify(inX, dataSet, labels, k):
# k-近邻算法分类器
distances = calculateDistances(inX, dataSet)
# argsort返回的是数组值从小到大的索引值
sortedDisIndicies = distances.argsort()
classCount = {}
for i in range(k):
# 根据索引值获取标签值
votelabel = labels[sortedDisIndicies[i]]
# 统计个数
classCount[votelabel] = classCount.get(votelabel, 0) + 1
sortClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
return sortClassCount[0][0]
def createDataSet():
"""创建样本数据集合"""
data = np.array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
labels = ['A', 'A', 'B', 'B']
return data, labels
if __name__ == '__main__':
data, labels1 = createDataSet()
print(classify([1.2, 0.8], data, labels1, 3));
打印结果应该是
A
参考资料：《统计学习方法》 ——李航
全部评论 (0)
还没有任何评论哟~