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

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

引言

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

1 傳統的分類(lèi)算法與改進(jìn)算法

1.1 傳統的kmeans算法與k近鄰算法

　　對于傳統的kmeans算法而言，對于給定的數據集n個(gè)樣本，在不知道數據集的標記時(shí)，通過(guò)指定該數據集中的k(k≤n)數據樣本作為初始中心，通過(guò)如下的方式進(jìn)行聚類(lèi)：

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

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

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

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

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

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

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

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

　　k個(gè)近鄰而沒(méi)有判斷近鄰中樣本是否分布得均勻。因此，該算法如果樣本分布不均勻，也會(huì )大大影響分類(lèi)的結果。

1.2 改進(jìn)的kmeans算法

　　由于傳統kmeans算法初始點(diǎn)的影響較大，因此可以做如下改進(jìn)。

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

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

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

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

2 實(shí)驗結果與分析

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

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

參考文獻：

　　[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]馬勇. 一種改進(jìn)的K-means聚類(lèi)分析算法在醫院信息系統中的應用研究[J]. 信息資源管理學(xué)報, 2012, (03): 93-96

　　[3]楊明峰, 詹良, 魏春陽(yáng), 等. 基于K-means聚類(lèi)分析的不同種植區烤煙外觀(guān)質(zhì)量區域分類(lèi)[J]. 中國煙草科學(xué), 2012, (02): 12-16

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

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

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

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

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

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

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

本文來(lái)源于中國科技期刊《電子產(chǎn)品世界》2016年第1期第79頁(yè)，歡迎您寫(xiě)論文時(shí)引用，并注明出處。