人工智能之K近邻算法（KNN）
人工智能之K近邻算法（KNN）
原创 张志荣
前言：人工智能机器学习有关算法内容，请参见公众号“科技优化生活”之前相关文章。人工智能之机器学习主要有三大类:1)分类;2)回归;3)聚类。今天我们重点探讨一下K近邻（KNN）算法。^_^
K近邻KNN(k-NearestNeighbor)算法,也叫K最近邻算法，1968年由Cover和Hart提出，是机器学习算法中比较成熟的算法之一。K近邻算法使用的模型实际上对应于对特征空间的划分。KNN算法不仅可以用于分类，还可以用于回归。
KNN概念：
K近邻算法KNN就是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例（K个邻居），这K个实例的多数属于某个类，就把该输入实例分类到这个类中。
如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。K近邻算法使用的模型实际上对应于对特征空间的划分。
通俗地讲，就是“物以类聚，人以群分”。
分类策略，就是“少数从属于多数”。
算法描述：
KNN没有显示的训练过程，在测试时，计算测试样本和所有训练样本的距离，根据最近的K个训练样本的类别，通过多数投票的方式进行预测。具体算法描述如下：
输入：训练数据集T={(x1,y1),(x2,y2),...,(xn,yn)}，其中xi∈Rn,yi∈{c1,c2,...,cK}和测试数据x
输出：实例x所属的类别
1)根据给定的距离度量，在训练集T中找到与x距离最近的k个样本，涵盖这k个点的x的邻域记作Nk(x)。
2）在Nk(x)中根据分类规则(如多数表决)确定x的类别y：
核心思想：
当无法判定当前待分类点是从属于已知分类中的哪一类时，依据统计学的理论看它所处的位置特征，衡量它周围邻居的权重，而把它归为到权重更大的那一类中。
kNN的输入是测试数据和训练样本数据集，输出是测试样本的类别。
KNN算法中，所选择的邻居都是已经正确分类的对象。KNN算法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
算法要素：
KNN 算法有3个基本要素：
1）K值的选择：K值的选择会对算法的结果产生重大影响。K值较小意味着只有与输入实例较近的训练实例才会对预测结果起作用，但容易发生过拟合；如果K值较大，优点是可以减少学习的估计误差，但缺点是学习的近似误差增大，这时与输入实例较远的训练实例也会对预测起作用，使预测发生错误。在实际应用中，K值一般选择一个较小的数值，通常采用交叉验证的方法来选择最优的K值。随着训练实例数目趋向于无穷和K=1时，误差率不会超过贝叶斯误差率的2倍，如果K也趋向于无穷，则误差率趋向于贝叶斯误差率。
2）距离度量：距离度量一般采用Lp距离，当p=2时，即为欧氏距离，在度量之前，应该将每个属性的值规范化，这样有助于防止具有较大初始值域的属性比具有较小初始值域的属性的权重过大。
对于文本分类来说，使用余弦(cosine)来计算相似度就比欧式(Euclidean)距离更合适。
3）分类决策规则：该算法中的分类决策规则往往是多数表决，即由输入实例的K个最临近的训练实例中的多数类决定输入实例的类别。
算法流程：
1)准备数据，对数据进行预处理。
2)选用合适的数据结构存储训练数据和测试元组。
3)设定参数，如K。
4)维护一个距离由大到小的优先级队列（长度为K），用于存储最近邻训练元组。随机从训练元组中选取K个元组作为初始的最近邻元组，分别计算测试元组到这K个元组的距离，将训练元组标号和距离存入优先级队列。
5)遍历训练元组集，计算当前训练元组与测试元组的距离，将所得距离L与优先级队列中的最大距离Lmax。
6)进行比较。若L>=Lmax，则舍弃该元组，遍历下一个元组。若L