基于局部保持的KNN算法

(西華大學計算機與軟件工程學院，四川 成都 610039)

·計算機軟件理論、技術與應用·

基于局部保持的KNN算法

曾俊杰，王曉明*，楊曉歡

(西華大學計算機與軟件工程學院，四川 成都 610039)

距離度量對K近鄰(KNN)算法分類精度起著重要的作用。傳統KNN算法通常采用歐氏距離，但該距離將所有特征的差別平等對待，忽略了數據的局部內在幾何結構特征。針對此問題，文章借鑒局部保持投影(LPP)的基本思想，在考慮數據的局部內在幾何結構特征基礎上，依據類內局部保持散度矩陣構造一種距離度量新方法，利用該距離度量提出一種局部保持K近鄰算法。實驗結果表明，與采用歐氏距離和傳統馬氏距離的KNN相比，本算法能夠得到更好的分類精度。

K-近鄰;局部保持投影;馬氏距離

分類不僅在模式識別、機器學習、數據挖掘和人工智能等相關領域有廣泛的研究，而且在醫療診斷、信用評估、選擇購物等生活實踐中也得到了廣泛的應用。K近鄰(K-nearest neighbor，KNN)算法[1-2]具有直觀、簡單、有效、易實現等特點，成為分類算法中比較常用的算法之一。該算法由Cover和Hart在1967年提出，是一種基于向量空間模型的算法，通過計算向量之間的相似度來確定待分類對象的類別。與其他分類算法不同，KNN算法不用提前設計出分類器。同時，該方法對較復雜的問題也有很好的分類能力。

KNN中距離度量[3-4]的設計會直接影響該分類算法的性能。傳統的KNN算法采用歐氏距離[5]，這種距離度量本質上會賦予每個屬性相等的權值，這樣近鄰間的距離會被大量的不相關屬性所支配，分類效果就會受到很大的影響。……