最近鄰居法

维基百科，自由的百科全书
跳转至： 导航、 搜索
本条目需要精通或熟悉本主题的專業人士参与及協助编辑。
請协助邀請適合的人士，或參照相關專業文獻，自行改善这篇条目。更多的細節與詳情請參见條目討論頁。

在模式识别领域中，最近鄰居法（KNN算法，又譯K-近邻算法）是将在特征空间中最接近的训练样本进行分类的方法。

最近鄰居法採用向量空間模型來分類，概念為相同類別的案例，彼此的相似度高，而可以藉由計算與已知類別案例之相似度，來評估未知類別案例可能的分類。

K-NN是一种基于实例的学习，或者是局部近似和将所有计算推迟到分类之后的惰性学习。k-近邻算法是所有的机器学习算法中最简单的之一：被分配的对象被列为了其邻域对象较多的类别的K近邻算法是最常见的（k是一个正整数，通常很小）。如果k=1，那么对象被简单分配给其近邻的类。

同样的方法可以用于回归，如：简单地将对象的属性值分配为其K近邻的属性值的平均值。它可以有效的衡量邻居的权重，使较近邻居的权重比较远邻居的权重大。（一种常见的加权方案是给每个邻居权重赋值为1/ d，其中d是到邻居的距离。这个方案是一个线性插值的推广。）

邻居都取自一组已经正确分类（在回归的情况下，指属性值正确）的对象。虽然没要求明确的训练步骤，但这也可以当作作是一种训练样本集的算法。k-近邻算法对数据的局部结构是非常敏感的。近邻算法能用一种有效的方式准确地计算决策边界[1]。

目录

方法 [编辑]

  • 目標：分類未知類別案例。
  • 輸入：待分類未知類別案例項目。已知類別案例集合D ，其中包含 j個已知類別的案例。
  • 輸出：項目可能的類別。

步驟 [编辑]

  1. 依公式計算 Item 與 D1、D2 … …、Dj 之相似度。得到Sim(Item, D1)、Sim(Item, D2)… …、Sim(Item, Dj)。
  2. 將Sim(Item, D1)、Sim(Item, D2)… …、Sim(Item, Dj)排序，若是超過相似度門檻t則放入鄰居案例集合NN。
  3. 自鄰居案例集合NN中取出前k名，依多數決，得到Item可能類別。

先看一个K近邻分类例子，试验样品（绿圈）应归入第一类蓝色正方形还是第二类红色三角形。如果k= 3，被分配到第二类，因为有2个三角形，而蓝色正方形只有一个。如果k= 5，被分配到第一类（3个正方形 2个三角形）。

训练样本是多维特征空间向量，其中每个训练样本带有一个类别标签。算法的训练阶段只包含存储的特征向量和训练样本的标签。

在分类阶段，k是一个用户定义的常数。一个没有类别标签的向量 （查询或测试点）将被归类为最接近该点的K个样本点中最频繁使用的一类。

一般情况下，将欧氏距离作为距离度量，但是这是只适用于连续变量。在文本分类这种非连续变量情况下，另一个度量——重叠度量（或海明距离）可以用来作为度量。通常情况下，如果运用一些特殊的算法来计算度量的话，K近邻分类精度可显著提高，如运用大边缘最近邻法或者近邻成分分析法。

“多数表决”分类的一个缺点是出现频率较多的样本将会主导测试点的预测结果，那是因为他们比较大可能出现在测试点的K邻域而测试点的属性又是通过K领域内的样本计算出来的[2]。解决这个缺点的方法之一是在进行分类时将样本到测试点的距离考虑进去。

参数选择 [编辑]

如何选择一个最佳的K值取决于数据。一般情况下，在分类时较大的K值能够减小噪声的影响。但会使类别之间的界限变得模糊。一个较好的K值能通过各种启发式技术来获取，比如，交叉验证。

噪声和非相关性特征向量的存在会使K近邻算法的准确性减小。对于选择特征向量进行分类已经作了很多研究。一个普遍的做法是利用进化算法优化功能扩展[3]，还有一种较普遍的方法是利用训练样本的互信息进行选择特征。

属性 [编辑]

原始朴素的算法通过计算测试点到存储样本点的距离是比较容易实现的，但它属于计算密集型的，特别是当训练样本集变大时，计算量也会跟着增大。多年来，许多用来减少不必要距离评价的近邻搜索算法已经被提出来。使用一种合适的近邻搜索算法能使K近邻算法的计算变得简单许多。

近邻算法具有较强的一致性结果。随着数据趋于无限，算法保证错误率不会超过贝叶斯算法错误率的两倍[4]。对于一些K值，K近邻保证错误率不会超过贝叶斯的。

连续变量估计 [编辑]

K近邻算法也适用于连续变量估计，比如适用反距离加权平均多个K近邻点确定测试点的值。该算法的功能有：

  1. 从目标区域抽样计算欧式或马氏距离；
  2. 在交叉验证后的RMSE基础上选择启发式最优的K邻域；
  3. 计算多元k-最近邻居的距离倒数加权平均。

發展 [编辑]

然而k最近鄰居法因為計算量相當的大，所以相當的耗時，Ko與Seo提出一演算法TCFP(text categorization using feature projection)，嘗試利用特徵投影法（en:feature projection）來降低與分類無關的特徵對於系統的影響，並藉此提昇系統效能，其實實驗結果顯示其分類效果與k最近鄰居法相近，但其運算所需時間僅需k最近鄰居法運算時間的五十分之一。

除了針對文件分類的效率，尚有研究針對如何促進k最近鄰居法在文件分類方面的效果，如Han等人於2002年嘗試利用貪心法，針對文件分類實做可調整權重的k最近鄰居法WAkNN (weighted adjusted k nearest neighbor)，以促進分類效果；而Li等人於2004年提出由於不同分類的文件本身有數量上有差異，因此也應該依照訓練集合中各種分類的文件數量，選取不同數目的最近鄰居，來參與分類。

参见 [编辑]

參考文獻 [编辑]

  1. ^ Bremner D, Demaine E, Erickson J, Iacono J, Langerman S, Morin P, Toussaint G (2005). "Output-sensitive algorithms for computing nearest-neighbor decision boundaries". Discrete and Computational Geometry 33 (4): 593–604. doi:10.1007/s00454-004-1152-0
  2. ^ D. Coomans; D.L. Massart (1982). "Alternative k-nearest neighbour rules in supervised pattern recognition : Part 1. k-Nearest neighbour classification by using alternative voting rules". Analytica Chimica Acta 136: 15–27. doi:10.1016/S0003-2670(01)95359-0.
  3. ^ Nigsch F, Bender A, van Buuren B, Tissen J, Nigsch E, Mitchell JB (2006). "Melting point prediction employing k-nearest neighbor algorithms and genetic parameter optimization". Journal of Chemical Information and Modeling 46 (6): 2412–2422. doi:10.1021/ci060149f. PMID 17125183.
  4. ^ Cover TM, Hart PE (1967). "Nearest neighbor pattern classification". IEEE Transactions on Information Theory 13 (1): 21–27. doi:10.1109/TIT.1967.1053964.
  • E. H. Han, G. Karypis and V. Kumar, Text categorization using weight adjusted k-Nearest Neighbor classification, Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 53–65, 2001.
  • Y. J. Ko and Y. J. Seo, Text categorization using feature projections, Proceedings of the Nineteenth international conference on Computational linguistics, Volume 1, pp. 1–7, 2002.
  • B. L. Li, Q. Lu and S. W. Yu, An adaptive k-nearest neighbor text categorization strategy, ACM Transactions on Asian Language Information Processing,Volume 3 , Issue 4, pp. 215 –226, 2004.
来自“http://zh.wikipedia.org/w/index.php?title=最近鄰居法&oldid=25456935”