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

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

引言

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

1 傳統(tǒng)的分類算法與改進算法

1.1 傳統(tǒng)的kmeans算法與k近鄰算法

　　對于傳統(tǒng)的kmeans算法而言，對于給定的數據集n個樣本，在不知道數據集的標記時，通過指定該數據集中的k(k≤n)數據樣本作為初始中心，通過如下的方式進行聚類：

　　(1)對該數據集中任意一個數據樣本求其到k個中心的距離，將該數據樣本歸屬到數據樣本距離中心最短的類;

　　(2)對于得到的類中的數據樣本，以求類的均值等方法更新每類中心;

　　(3)重復上述過程1和2更新類中心，如果類中心不變或者類中心變化小于某一個閾值，則更新結束，形成類簇，否則繼續(xù)。

　　但是對于傳統(tǒng)的kmeans聚類算法而言，由于隨機指定初始點，對kmeans算法通過迭代這樣一種啟發(fā)式的貪心算法而言不能形成一個全局最優(yōu)解，迭代最終收斂的結果可能都是局部最優(yōu)解。這樣分類的精度就會難以預料，對最終的樣本分類就難以消除隨機指定初始點造成的聚類結果不一致的影響。

　　對于傳統(tǒng)的k近鄰算法而言，對于給定的數據集，有n個數據樣本是已標記的，另一部分數據樣本是未標記的，對未標記的數據樣本，通過如下的方式進行分類：

　　(1)度量每個未標記數據樣本與所有已標記數據樣本的距離;

　　(2)對所有求出的距離選擇與未標記數據樣本距離最近的k(k≤n)個已標記數據樣本;

　　(3)統(tǒng)計這k個已標記的數據樣本，哪一類的數據樣本個數最多，則未標記的數據樣本標記為該類樣本K近鄰算法沒有一個數據樣本訓練的過程，本身是一種惰性的監(jiān)督算法，該算法對k值的選擇以及距離的度量方式都會影響最終的分類精度。因為該算法只是選擇。

　　k個近鄰而沒有判斷近鄰中樣本是否分布得均勻。因此，該算法如果樣本分布不均勻，也會大大影響分類的結果。

1.2 改進的kmeans算法

　　由于傳統(tǒng)kmeans算法初始點的影響較大，因此可以做如下改進。

　　對于給定的數據集樣本，kmeans可以通過兩兩比較數據集中數據樣本點間的距離，選擇距離最遠的兩個點A，B作為初始標記。同時為了去除噪聲對初始點的影響，對于選定的初始標記點，可以選擇以初始標記點為中心，與初始標記點距離小于閾值的若干個點的幾何均值作為最終的初始點。對于A初始標記點的若干點的選擇原則是離初始標記A距離與離B距離的比值大于一定閾值的若干點，而對于B初始標記點的若干點的選擇原則是離初始標記B距離與A距離的比值大于一定閾值的若干點。選定了初始點后，其后的步驟如下：

　　(1)對該數據集中任意一個數據樣本求其到兩個中心的距離，將該數據樣本歸屬到數據樣本距離短的類;

　　(2)對于得到的類中的數據樣本，求類的均值更新兩類中心;

　　(3)重復上述過程1和2更新類中心，如果類中心不變或者類中心變化小于某一個閾值，則更新結束，形成類簇，否則繼續(xù)。

2 實驗結果與分析

　　采用手寫數字集MNIST Handwritten Digits ^[10]進行實驗，該數字集庫含有0-9的10類手寫訓練數據集和0-9的10類手寫測試數據集。每個數據集樣本的大小是28*28的圖片，轉化成向量是1*784維大小。從手寫數據集中抽取標記為1和2的兩類數據集樣本，從這類數據集中隨機抽取標記為1和2的數據樣本各1000個，共計2000個數據樣本進行實驗分析。從這2000個數據樣本中隨機選擇1600個數據樣本(標記為1和2的兩類數據各800個數據樣本)進行k近鄰分析，400個數據樣本(標記為1和2的兩類數據樣本各200個)進行測試。對于改進的kmeans算法，將小于閾值的5個點取幾何均值作為最終的初始點和傳統(tǒng)的kmeans算法采用400個數據樣本進行測試。改進的kmeans算法測試的正確率為84.25%，傳統(tǒng)的kmeans算法初始值不確定，可能的正確率為15.75%，51%以及83.75%等。很明顯，改進的kmeans算法不管從精度還是穩(wěn)定性方面都優(yōu)于傳統(tǒng)的kmeans算法。k近鄰算法選擇曼哈頓距離和歐式距離作為距離度量的方式，同時改變k值對k近鄰算法的結果進行測量，結果如圖1所示, 橫軸表示k值選擇的樣本數，縱軸表示對應的測試正確率。

　　從圖1中可以看出，隨著近鄰數的增多，在一定的范圍內，k近鄰的精度是下降趨勢。對于選擇曼哈頓距離度量樣本間距離的k近鄰算法，當k值大于200的時候，k近鄰算法對樣本的分類正確率明顯低于改良的kmeans算法對樣本分類的正確率。而采用歐式距離度量樣本間距離的k近鄰算法，當k值大于380的時候，k近鄰算法對樣本的分類正確率才明顯低于改良的kmeans算法對樣本分類的正確率。因此對于k近鄰算法而言，k近鄰數目的選擇以及樣本間距離度量的方式對分類的結果都是至關重要的。同時從中可以發(fā)現(xiàn)，在某些情況下，無監(jiān)督的學習方式可能比有監(jiān)督的學習方式更有利，也更方便。

參考文獻：

　　[1]Macqueen J. Some methods for classification and analysis of multivariate observations[C]. Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, 1967: 281-297

　　[2]馬勇. 一種改進的K-means聚類分析算法在醫(yī)院信息系統(tǒng)中的應用研究[J]. 信息資源管理學報, 2012, (03): 93-96

　　[3]楊明峰, 詹良, 魏春陽, 等. 基于K-means聚類分析的不同種植區(qū)烤煙外觀質量區(qū)域分類[J]. 中國煙草科學, 2012, (02): 12-16

　　[4]張文明, 吳江, 袁小蛟. 基于密度和最近鄰的K-means文本聚類算法[J]. 計算機應用, 2010, (07): 1933-1935

　　[5]袁方, 周志勇, 宋鑫. 初始聚類中心優(yōu)化的k-means算法[J]. 計算機工程, 2007, (03): 65-66

　　[6]陳帥均, 蔣平, 吳欽章. 改進的KNN算法在光測圖像關鍵事件評估中的應用[J]. 光電工程, 2014, (08): 66-72

　　[7]王淵, 劉業(yè)政, 姜元春. 基于粗糙KNN算法的文本分類方法[J]. 合肥工業(yè)大學學報(自然科學版), 2014, (12): 1513-1517

　　[8]孫秋月. 基于SNN相似度的KNN分類算法研究[D]. 云南大學, 2008

　　[9]嚴曉明. 基于類別平均距離的加權KNN分類算法[J]. 計算機系統(tǒng)應用, 2014, (02): 128-132

　　[10]The MNIST database of handwritten digits[EB/OL]. http://yann.lecun.com/exdb/mnist/

本文來源于中國科技期刊《電子產品世界》2016年第1期第79頁，歡迎您寫論文時引用，并注明出處。