一種含噪音處理的 K

一種含噪音處理的K-means聚類算法陸進淳B躍飛【摘要】K-meansclusteringasclassicalclusteringalgorithmissensitivetonoise.Inpracticalapplications,thedatausuallycontainmanynoisesandthismakesitdifficulttoobtainagoodclusteringresult.ThispaperproposesaK-meansclusteringalgorithmwithnoisepro-cessing.Thealgorithmdividesoriginalspacetoseveralregionsdynamically,andcalculatestheweightedsimilaritymatrixofsampleandeachregionalcentroidusingcorrelatedregionaldensityandusesitastheinputofK-meansalgorithm.Thematrixeffectivelydescribesthedistribu-tioninformationofdataandatthesametimerealisesthedimensionalityreductionoffeaturessothattheclusteringtaskswithnoisedatacanbeprocessedmoreeffectively.Theproposedalgorithmismoresuitableforthesituationofcomplexdatadistribution.Experimentalresultprovestheeffectivenessofthealgorithm.%K-means作為經典的聚類算法，對噪音很敏感。在實際應用中，數(shù)據通常包含較多噪音，聚類難以得到良好的效果。提出一種含噪音處理的K-means聚類算法。算法將原空間動態(tài)地劃分成若干個區(qū)域，利用對應的區(qū)域密度加權計算樣本與每個區(qū)域質心的相似度矩陣，作為K-means的輸入。該矩陣有效描述了數(shù)據的分布信息，同時實現(xiàn)了特征的降維，能更有效處理帶噪音數(shù)據的聚類任務，更適用于數(shù)據分布復雜的情況。實驗結果證實了此算法的有效性?！酒诳Q】《計算機應用與軟件》【總頁數(shù)】4頁(P265-268)【關鍵詞】抗噪;聚類;KD樹;密度;質心【作者】陸進淳B躍飛【作者單位】復旦大學計算機科學技術系上海201203;復旦大學計算機科學技術系上海201203【正文語種】中文【中圖分類】TP391聚類分析是無監(jiān)督學習的經典任務，最具有代表性的聚類算法是K-means，易于執(zhí)行與理解。K-means算法被國內夕卜研究者不斷研究拓展，提出了較多有效的改進算法［1-3］，被成功應用到不同的場合。但在處理含噪數(shù)據集時，K-means及其改進算法常常會得到不好的結果。究其原因，K-means的每個聚類可能都包含有噪音，影響了進一步的分析。經典的BagofWordsModel［4］的應用中，通常采用K-means算法對數(shù)據進行聚類生成字典。為了保證聚類質量，通常需要設置很大的K值，因此聚類速度很慢，若K值較小，則容易導致較多聚類都包含噪音，從而字典中的較多元素不具有代表性，從而模糊了BagofWordsModel描述能力，導致算法結果不佳。更具體地，如圖1所示，聚類的目的是過濾噪音點(三角點)，得到圓形點，但是無論怎么指定類數(shù)K和采用不同的初始化類中心策略，K-means得到的結果都難以保證圓形點的類內不含有三角點。這種情況需要多次指定K值，重新運行K-means以達到最優(yōu)。可見，K-means只適用于類內數(shù)據集中分布的情況?；贙-means的聚類算法中，最典型的是譜聚類［5］。譜聚類利用圖論的方法，算法與特征維度無關，將數(shù)據間兩兩關系描述成相似度矩陣，通過對相似度矩陣的前K個特征向量進行K-means聚類得到結果。譜聚類的效果很受相似度衡量方法的影響，參數(shù)的微小改動，會導致聚類結果不同。先降維后聚類的經典方法有主成分分析PCA［6］和拉普拉斯特征映射LE(LaplacianEigenmap)［6］。前者將數(shù)據投影到特征空間中方差最大的主方向上，然后進行K-means。后者通常用在譜聚類之前，通過只保存互為K最近鄰數(shù)據點的相似度信息，將相似度矩陣稀疏化，一定程度上去掉了噪音點的影響，同時也使得特征向量的求解得到加快。上述方法都需要求解矩陣的特征值和特征向量，復雜度是矩陣規(guī)模的三次方之高［7］。AbudalfaS等人提出了基于KD-tree［10］的動態(tài)聚類算法DLCKDT(DynamicLinkageClusteringu-singKD-Tree)［8］，利用全數(shù)據所構建的平衡KD-tree，將所有葉子節(jié)點的上兩代祖先點作為采樣集，其他所有點均可最近匹配到最近的采樣點中，形成最初的聚類，不斷兩兩聚類間的融合，直到聚類個數(shù)為K。文獻［8］中，實驗表明DLCKDT比著名的密度聚類方法DBSCAN［9］更能適用于復雜的聚類任務。然而，DLCKDT算法的融合階段，很容易受到噪音點的影響，一旦錯誤融合聚類，則后續(xù)融合將不斷將錯誤擴大，結果非常不理想。因此DLCKDT不適用于處理噪音較多的聚類任務。實際應用中，期望通過聚類得到不含噪音的聚類，至少應保證部分聚類效果較好且可用，同時應盡量避免反復指定K-means參數(shù)K以嘗試。基于此種考慮，本文提出了基于K-means帶噪音處理的聚類算法。利用KD-tree的檢索能力，動態(tài)劃分原特征空間為若干個局部空間，分別計算各個局部空間的質心，重新計算樣本與這些質心的相似度，作為樣本的新特征；同時，利用K近鄰數(shù)據點的密集程度以描述對應相似度的權重，再進行K-means聚類。實驗表明，本文算法能更有效處理帶噪數(shù)據，聚類性能更好。假設每個局部空間中，均有K個數(shù)據點，每個局部空間的描述信息可分成兩部分:位置信息和密度信息。位置信息可用K個數(shù)據點的質心來描述，而密度信息可利用K個數(shù)據點的相似度來描述。1.1質心的計算其中，mi為點xi的密度權重，本文統(tǒng)一采用mi=1;i=1,2,...,K。1.2密度的計算某個局部空間質心C的計算公式如下所示：對于基于密度的聚類方法來說，數(shù)據分布的局部密度描述了數(shù)據的聚攏程度，數(shù)據越密集則越可能同處一個聚類。DLCKDT算法將KD-tree葉子節(jié)點往上兩代的祖先節(jié)點當作采樣點，從而達到采樣描述數(shù)據的目的。但并不能保證采樣點附近區(qū)域的密集度一定高，進而導致密集度不高的初始聚類太多，在融合階段，數(shù)據點較少的聚類很容易受到噪音的影響，進而導致結果不佳。由此可見，數(shù)據局部分布的密度計算，也會影響某些聚類方法的結果。通常，估計K個數(shù)據點的密度方法，較為準確的是計算兩兩點間的相似度的均值，均值越大，則密度越大，反之密度越小。這種方法會導致O(K2)的時間復雜度，本文采用時間復雜度為O(K)的方法，某個局部空間密度D的計算方法如下所示:其中，S(xi,C)表示樣本xi與質心C的相似度，本文采用式(3)計算相似度:其中，dist(xi,xj)表示樣本xi和xj的二范式距離，a是相似度函數(shù)的唯一參數(shù)，其大小可以利用式(4)動態(tài)確定。其中為兩兩樣本點間二范式距離的均值。a的動態(tài)取值具體含義為，保證近一半樣本間的相似度大于0.5，近一半樣本間的相似度小于0.5。因此，式(4)的計算方法，對不同量綱不同維度的樣本特征均適用。2.1算法原理構建全數(shù)據范圍的KD-tree，可快速查詢到與某樣本點p最近的K個樣本點(包括點p)，從而組成了一個局部空間。通過計算該局部空間的質心和密度，實現(xiàn)對該局部空間分布的簡單描述。本文算法主要基于以下兩個原理。原理1同屬于某個局部空間內的兩個點，該局部空間密度越大，則兩個點屬于同一個聚類的概率相對越高。這也是眾多密度聚類算法的主要原理，著名的有DBSCAN、OPTICS[11]等。原理2K-means是基于點間相似度或距離的聚類算法。如圖2所示，若有某點target，可計算所有數(shù)據點xi與點target的相似度si,則si可以作為xi的一維特征。在僅此一維相對空間中做K-means聚類，與target相似的點更能聚類到同一類中。將相似度矩陣直接作為K-means的輸入，這種最原始的譜方法就是基于上述兩個原理的。具體地，假若有M個樣本點處于一個較為密集的局部空間中，則這M個樣本的相似度較高，而與其他樣本的相似度也比較接近，K-means聚類能很好地將M個樣本點與其他樣本區(qū)別開來。然而，直接使用相似度矩陣聚類，會導致很高的K-means復雜度。2.2算法描述本文利用KD-tree，動態(tài)地劃分原特征空間成若干個局部空間，每個局部空間包含K個樣本。算法輸入為局部空間的樣本個數(shù)K，輸出為若干個局部空間，具體如下:算法1動態(tài)劃分空間算法將所有樣本標記為未訪問；訪問一個未訪問的樣本點p，標記為已訪問；利用KD-tree查詢點p最近鄰的K個點，形成一個局部空間，并將K個點標記為已訪問；在KD-tree中刪除被查詢到的K個點；若已訪問過所有樣本點，則返回所有局部空間，終止算法；否則執(zhí)行(2)。由算法1可知，每個樣本點均被唯一歸入某個局部空間中，即只描述了一次。若以一次樣本點的處理為基本時間單位，則算法1的時間復雜度為O(N),其中N為總樣本個數(shù)。5個步驟中，時間復雜度最高的是第三步，即查詢K個最近點，最壞情況下為O(KxN1-1/K)[12]o結論1最壞情況下，算法1的時間復雜度為O(N2-1/K)。算法1總共需要查詢最近鄰N/K次，因此最壞時間復雜度為O((N/K)xKxN1-1/K),簡化得O(N2-1/K)。這相比于復雜度為O(N3)的譜聚類算法，降維步驟的時間復雜度大大提高。利用算法1,本文提出以下聚類算法，能更好地利用譜理論來解決K-means無法抗噪的問題。算法2基于K-means帶噪音處理的聚類算法(1)調用算法1生成N/K個局部空間，記M=N/K;(2)計算所有樣本與M個質心的加權相似度，生成NxM的相似度矩陣「，計算方法見式(5);相似度矩陣F作為K-means的輸入，執(zhí)行聚類，輸出聚類結果。其中，D表示局部空間的密度，C表示局部空間的質心，j=1,2，…，M;i=1,2,...,N。實驗分為仿真數(shù)據實驗以及真實數(shù)據實驗兩大部分，均利用Matlab，分別對K-means算法、DLCKDT算法、譜聚類算法與本文算法作對比實驗。仿真數(shù)據實驗驗證本文算法設計的過程與目的的一致性。真實數(shù)據實驗驗證本文算法的有效性。所有實驗中，本文算法1的參數(shù)K統(tǒng)一被指定為10。K-means算法、譜聚類中的K-means算法以及本文中的K-means算法均采用相同初始化類中心策略，即重復10次初始化類中心，取兩兩類中心二范式距離之和最大的一組類中心。所有聚類均采用相同的相似度衡量方法。3.1仿真數(shù)據實驗實驗仿真了二維數(shù)據集，該數(shù)據集中存在著較多的噪音點（即圖3中外圍的隨機分布點），而聚類的目的是希望在存在較多噪音點的情況下，將中間兩個圓形分布的點集區(qū)分開來。本文算法很好地處理了仿真數(shù)據的聚類任務，每個聚類最終只包含了少量的噪音點，結果如圖3、圖4、圖5、圖6所示。由結果可知，K-means在非類內集中分布的數(shù)據集中，難以一次達到理想的結果，需要反復地指定類數(shù)K的值以嘗試。DLCKDT算法由于融合階段是根據兩點最近距離指定的，噪音點較多的時候，因錯誤融合噪音點所在的聚類，導致結果不佳。譜聚類算法在前K個特征向量空間中進行K-means聚類，由于前K個特征向量丟失了全局的細節(jié)信息，導致結果不夠精確。本文算法，較好處理了仿真數(shù)據的聚類任務，只有少量數(shù)據點被錯分。究其原因，本文算法具有高密度區(qū)域的導向能力，根據局部數(shù)據分布密度的不同，賦予了各個空間位置不同的參考權重，最終使得越是密集的數(shù)據分布區(qū)域越能優(yōu)先聚在一起。3.2真實數(shù)據實驗聚類是實現(xiàn)類間距離最大化和類內距離最小化的劃分過程。然而，面向含噪較多的數(shù)據時，帶噪音處理的聚類的目的是將分布不集中的噪音歸為噪音類，同時實現(xiàn)其他類類間距離最大化和類內距離最小化。由于噪音類的存在，依賴聚類類內距離和類間距離的評價方法并不適用，例如散射準則［13］、類內距離與類間距離之比等。因此本文實驗可選用利用標簽信息來評價聚類效果的評價準則，常用的有蘭德指數(shù)RI（RandIndex）［14］、F值。其中，蘭德指數(shù)是F值的特殊情況，即將召回率和正確率視為同樣重要。聚類結果評價指標采用蘭德指數(shù)，蘭德指數(shù)是評價聚類正確性的有效指標。蘭德指數(shù)的計算公式如下：其中，TP是同一類的樣本被分在同一個聚類的計數(shù)總和，TN是不同類的樣本被分在不同聚類的計數(shù)總和，C2n表示n個樣本中取2個的組合運算。由式（6）知，輸入條件相同時，蘭德指數(shù)直接反映了兩個聚類算法過濾噪音點能力的高低。數(shù)據采用Iris數(shù)據庫，Iris是國內夕卜評價聚類算法常用的數(shù)據集。數(shù)據總共有3類植物，每類植物有50個樣本，特征為4維。其中，每一維的特征處于(0,10)區(qū)間。由于維度較低，噪音特征更少，特征更真實可靠，更適合做聚類算法的評價。實驗中，通過指定空間大小和數(shù)量多少兩個參數(shù)來生成高斯分布的隨機噪音點，并將此噪音集加入到Iris數(shù)據庫之中。其中在噪音數(shù)量一定時，噪音生成空間越大，則噪音越稀疏，對應密度越低；在噪音生成空間一定時，噪音數(shù)量越多，則噪音越稠密，對應密度越高。為了驗證本文算法的隨機噪音處理能力，實驗采用控制變量法，在輸入條件相同的情況下，分別對隨機噪音生成空間大小、隨機噪音相對比例對各個算法的蘭德指數(shù)的影響進行統(tǒng)計，每次統(tǒng)計都取100次重復實驗的蘭德指數(shù)平均值，結果如圖7、圖8所示。其中，噪音空間大小為10的倍數(shù)，因為Iris數(shù)據每一維特征都分布在(0,10)區(qū)間。噪音相對比例是噪音總數(shù)與非噪音總數(shù)之比。由圖7可知，在有20%隨機噪音的情況下，噪音隨機分布的空間越大，K-means的蘭德指數(shù)越低，DLCKDT算法和譜聚類有不穩(wěn)定的小幅度上升趨勢，而本文算法依然能維持較高的蘭德指數(shù)。這是因為本文算法是基于噪音分布稀疏的假設而設計的，而隨機噪音分布的空間越大，噪音分布越稀疏，利于本文算法。由圖8可知，在1倍的隨機噪音生成空間的條件下，隨著噪音增多，本文算法與K-means的蘭德指數(shù)均呈下降趨勢，但本文算法抗噪的能力更強，而K-means逐漸失效。DLCKDT與譜聚類均呈現(xiàn)了先下降后上升的趨勢，其中，DLCKDT算法更為明顯。隨著噪音不斷增多，噪音分布的密度逐漸增強，對本文算法有所影響，所以本文算法呈下降趨勢。但由于噪音分布密度依然是較高概率上小于Iris數(shù)據的密度，所以依然能保持著較高的蘭德指數(shù)。本文算法利用數(shù)據分布的空間位置信息以及分布的密度大小，弱化了噪音數(shù)據對聚類結果的影響，加強了非噪音數(shù)據對K-means聚類的導向能力。實驗結果表明，在蘭德指數(shù)的衡量下，本文算法整體優(yōu)于K-means、DLCKDT以及譜聚類，對含噪數(shù)據更加有效。為了解決聚類任務中，噪音影響K-means聚類結果的問題，本文提出了基于K-means算法的有效抗噪的聚類算法，動態(tài)地將原特征空間劃分為若干個區(qū)域，根據區(qū)域內數(shù)據局部分布的質心位置信息以及密度的大小，弱化噪音對K-means的影響，促使數(shù)據分布密度較大的樣本優(yōu)先聚于同類中。實驗表明，本文算法是優(yōu)先保證局部聚類質量的有效算法?！鞠嚓P文獻】[1]楊更.改進的DK算法在網絡信息聚類中的應用[J].計算機應用與軟件，2012,29(8):217-219.[2]徐森，周天，李先鋒，等.結合K均值與Laplacian的聚類集成算法[J].計算機應用與軟件,2012,29(10):69-70,140.[3]ElkanC.Usingthetriangleinequalitytoacceleratek-means[C]//ICML.2003,3:147-153.[4]滕舟，郭躍飛.基于EM的非監(jiān)督圖像多標簽區(qū)域標定算法[J].計算機應用與軟件，2012,29(2):5-8,26.[5]RoheK,ChatterjeeS,YuB.Spectralclusteringandthehigh-dimensionalstochasticblockmodel[J].TheAnnalsofStatistics,2011,39(4):1878-1915.[6]JainAK.Dataclustering:50-yearsbeyondK-means[J].PatternRecognitionLetters,2010,31(8):651-666.[7]ParlettBN.TheQRalgorithm[J].ComputinginScience&Engineering,2000,2(1):38-42.[8]AbudalfaS,MikkiM.AdynamiclinkageclusteringusingKD-tree[J].InternationalArabJournalofInformationTechnology(IAJIT),2013,10(3):283-289.[9]ZhouS,ZhouA,JinW,eta