一種含噪音處理的 K

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