改良的kmeans與K近鄰算法特性分析

章宦記

摘要：kmeans算法作為無監督算法的一種，對初始點的選擇比較敏感；而k近鄰作為一種惰性且有監督的算法，對k值和樣本間距離度量方式的選擇也會影響結果。改良的kmeans算法通過遍歷樣本，篩選初始點，其準確率超過了k近鄰算法，同時穩定性也優于傳統的kmeans算法。無監督算法在一些情況下優于有監督算法。

關鍵詞：初始點；無監督；鄰近點；有監督

DOI：10.3969/j.issn.1005-5517.2016.1.022

引言

上個世紀60年代，MacQueen首次提出kmeans算法^[1]，而后的數十年中，kmeans算法被廣泛應用于各種領域，比如馬勇等人將kmeans算法應用在醫療系統中^[2]，楊明峰等人將kmeans聚類算法應用于對烤煙外觀的區域分類^[3]。同時很多的學者投入到對kmeans算法本身特性的研究中^[4-5]、目前kmeans算法已經成為機器學習，數據挖掘等領域比較重要的方法之一。而k近鄰算法是圖像以及文本分類領域應用比較廣泛的算法之一^[6-7]，對k近鄰算法而言，k值的選擇以及樣本間距離的度量方式都會影響到分類的精確度。但是同樣有許多學者對該算法進行了一些改善，比如孫秋月等^[8]通過對度量的樣本數據的每個維度賦不同權值的方式，降低了樣本數據分布不均勻導致的分類誤差。嚴曉明等通過類別平均距離進行加權對大于某一個閾值的數據樣本點進行剔除的方式來提高k近鄰算法的精度^[9]。k近鄰算法本身是一種惰性的監督算法，相較于其他監督算法比如支持向量機、邏輯回歸、隨機樹等，具有算法簡單、易于理解、易于實現、無需估計參數的特性。kmeans算法由于對初始點選擇較敏感，不同的初始點將會導致不同的聚類結果。……