聚類分析中的基本算法k-means算法綜述

聚類分析中的基本算法k-means算法綜述

無線傳感器。1.ni。1min1j，xiaj.2（1）無線傳感器。jk，xiaj2（1）。由于K-means算法易于描述,具有時間效率高且適于處理大規(guī)模數(shù)據等優(yōu)點,自20世紀70年代以來,該算法在國內外已經被應用到包括自然語言處理、土壤、考古等眾多領域。在文本聚類領域,K-means算法已經成為基本的算法。隨著K-means算法研究的深入,該算法的一些不足紛紛暴露出來,主要包括:需要預先確定K值、會受到初始聚類中心影響、難以處理分類屬性數(shù)據以及容易收斂于局部最優(yōu)解等。3k-mean文本搜索算法的優(yōu)化3.1算法收斂函數(shù)的改進K-means算法通過不斷地迭代與重新計算聚類中心直至收斂進行聚類,因此聚類收斂條件是算法的重要組成部分。在最初的算法中,MacQueen以平方距離和Wn為目標函數(shù),作為聚類質量的衡量標準,并證明了Wn的收斂性。1978年Hartigan分析了一維情況下的算法,令K=2,即將全部數(shù)據點分割成兩個簇,證明了可以用概率收斂點來定義最佳的分割點。Pollard考察了多維空間的情況,并將Hartigan的結論推廣到多維空間,提出了K-means算法新的聚類質量評價標準,即在保證Wn收斂的同時,還需保證各聚類中心也收斂到最優(yōu)解。Creator等的研究發(fā)現(xiàn),由于目標函數(shù)Wn存在局部極小值點,K-means算法會陷入局部最優(yōu)解。為了使聚類結果盡量接近全局最優(yōu)解,需要在算法中加入新的機制,而這些改進都以犧牲目標函數(shù)Wn的收斂速度為代價。其中較著名的是1995年Chinrungrueng等提出的改進算法,該算法在原有算法中加入了兩種新的機制,分別是:允許算法在自適應過程中擺脫目標函數(shù)Wn的干擾;采用反饋方式,根據當前聚類質量動態(tài)地調整算法的收斂速度。由于Wn計算的是所有數(shù)據點到其聚類中心的距離平方和,因而事實上其反映的僅僅是類內距離的度量,而根據聚類算法的基本思想,即聚類算法應使聚簇內相似度盡可能大,而聚簇間相似度盡可能小的基本原則,聚類收斂函數(shù)應該綜合考慮類內距離和類間距離。為此,學界提出了很多改進的聚類收斂函數(shù),以期更加全面地反映聚類的質量。其中大多數(shù)的改進都是采用類內緊密性(Within-clusterScatter)與類間分散性(Between-clusterSeparation)的比值來作為收斂函數(shù),這樣當收斂函數(shù)收斂到極小值時,類內緊密性和類間分散性都可以達到較優(yōu)值。著名的Davies-Bouldin指數(shù)(DBI)和Dunn指數(shù)(DI)都是采用這種思想,Davies-Bouldin指數(shù)是計算類內距離之和與類間距離之和的比值,而Dunn指數(shù)是計算類內距離和類間距離的最值之比。3.2影響算法性能的聚類數(shù)和很多聚類算法一樣,K-means算法需要事先確定K值,K值的選取很大程度上會影響算法的性能。Rezaee等根據經驗規(guī)律認為最佳的聚類數(shù)應該在2與√ΝN√之間,其中N為數(shù)據空間中的所有數(shù)據點的個數(shù)。學界對K-means算法最優(yōu)聚類數(shù)的確定進行了深入的研究,提出了多種解決方法。(1)聚類聚類算法基于聚類有效性函數(shù)的解決方法是一種十分簡單的解決方法,通過在[2?√Ν][2?N√]區(qū)間逐個選取K值,并利用聚類有效性函數(shù)評價聚類效果,最終得到最優(yōu)的K值,這種解決思想的關鍵是提出優(yōu)秀的聚類有效性函數(shù)。經典的K-means算法所選用的聚類有效性函數(shù)是Wn指數(shù),在此基礎上許多學者提出了改進,學界公認較優(yōu)秀的有MH指數(shù)、DB指數(shù)、Dunn指數(shù)、GeneralizationofDunn’sIndex等。在國內,許多學者也按照這種思想提出了一系列的解決方法。李永森等提出的距離代價函數(shù)綜合了類間距離和類內距離兩項距離函數(shù),類間距離為所有聚類中心到全域數(shù)據中心的距離和。類內距離即所有類中對象到其聚類中心的距離之和。作者證明了當距離代價函數(shù)取得最小值時,此時對應的K值為最佳聚類數(shù)。張逸清等在K-means算法的目標函數(shù)中加入一個新的數(shù)據項。該數(shù)據項用于衡量其他鄰近聚類中心與當前聚類中心的距離平方和,并引入一個權值λ,用于調節(jié)新數(shù)據項在整個目標函數(shù)中所占的比例。當算法初始K值過大時,在聚類算法的前期訓練中,新數(shù)據項的引入就可以使得聚類中心彼此靠近,然后考察聚類中心兩兩之間的距離值,若小于設定閾值,則將其合并,這樣得到的K值更加接近最優(yōu)解。張忠平等提出了一種基于二分均值聚類的K值決定方法。算法思想為:首先設定兩個閾值:簇內相似度λ和簇間相似度γ;在整個數(shù)據集上運行二分K均值聚類算法,得到兩個類C1和C2,考察C1和C2的簇內相似度,若大于閾值λ,則繼續(xù)運行二分K均值聚類算法,不斷迭代以上過程,最終得到所有的類簇內相似度都小于λ;計算所有類的簇間相似度,將簇間相似度小于γ的類合并,最終得到的類的個數(shù)即為K值。該算法思想比較簡單,通過兩步分裂和合并的過程,得到較好的K值。算法中最重要的問題是確定閾值λ和γ值,這兩個閾值決定了數(shù)據分裂和合并的效果。作者采用了概率統(tǒng)計的方法確定λ值,計算文本集中兩兩文本之間相似度的均值μ和標準差σ,并根據實際應用中對簇內相似度的要求給出了一個系數(shù)θ,從而可以利用公式λ=μ+θ×σ計算出較優(yōu)的λ值。在確定另一個閾值γ時,通過實驗證明了γ=0.6λ時,合并的效果最好。(2)染色體編碼算法遺傳算法在K值選擇的研究中也得到了學者的重視。Bandyopadhyay等提出了基于遺傳算法的GCUK算法。該算法的染色體采用字符串方式編碼,即將每一個初始聚類中心的坐標按順序編碼,沒有作為初始聚類中心的數(shù)據點則以符號“#”表示,編碼完成后在逐代交叉中最終得到最佳的K值。該算法的缺點是染色體的字符串表示方法大大增加了算法的開銷。為了解決該問題,Lin等采用了二進制方式進行染色體編碼。該編碼方案采用染色體長度作為數(shù)據集的大小,被選為初始聚類中心的數(shù)據點編碼為1,否則為0。Liu等在此基礎上提出了AGCUK算法,在染色體編碼時為每一個染色體選用K×m個基因(K為隨機選取的聚類數(shù)目,m為數(shù)據點的維度),前m個基因表示第一個初始聚類中心的坐標,接著m個基因表示第二個初始聚類中心的坐標,以此類推完成編碼,通過染色體的逐代交叉動態(tài)改變K值,此外,在遺傳過程中算法還運用了最佳個體保留法,把具有最高適應度的個體不經交叉直接遺傳到下一代,最終即可得到最佳的K值。而鞏敦衛(wèi)等在Merwe等、Omran等的研究基礎上提出了一種基于微粒群的優(yōu)化算法。微粒群優(yōu)化算法是一種群智能優(yōu)化算法,其算法思想類似于遺傳算法,由Merwe等首次將其運用于聚類。基于微粒群優(yōu)化K值的K-means算法為:首先初始化微粒群,隨機產生一個K值,這個K值在[2?√Ν][2?N√]區(qū)間內。隨機選取K個初始聚類中心,按照事先確定的微粒編碼方式編碼并在微粒群上運行K-means算法,更新微粒的編碼結構以及微粒的速度和位置。在算法中引入了一種不同于傳統(tǒng)微粒群優(yōu)化算法的微粒更新運算,即通過新定義的+、-運算可以動態(tài)改變此前隨機選取的K值,隨后逐代迭代以上步驟,最終使目標函數(shù)收斂。(3)算法的基本思想Xu等提出了RPCL原則,該原則可以在聚類過程中自動確定適當?shù)腒值。其主要思想是:對于每個輸入而言,對獲勝單元的權值予以修正以適應輸入值,同時對次勝單元進行懲罰,使之遠離輸入值。這樣經過多次競爭學習之后,就可以使權值向量趨向于聚類中心。Pelleg等提出了X-means算法用于解決K值選定的問題。算法的主要步驟為:首先通過經典的K-means算法對數(shù)據集聚類,得到K個聚類中心;對聚類所得的K個類逐個進行聚類,再運用貝葉斯信息標準(BIC)進行判斷,如果BIC標準得分更高,則采用新的聚類中心,否則回到原來的聚類,算法經過O(K)的時間開銷,就可以尋找到最佳的K值。綜合上述研究可以發(fā)現(xiàn),學界已經提出了多種K值選取方法,并分別基于不同的思想?；诰垲愑行院瘮?shù)的解決方法算法思想簡單,但是需要付出較大的時間開銷,遺傳算法作為一種優(yōu)秀的優(yōu)化算法,應用于K值的確定是十分有效的。目前,多種K值確定算法都運用了遺傳算法或者類似于遺傳算法的方法,這些算法聚類效果的優(yōu)劣取決于染色體的編碼方式,在編碼時既需要兼顧進化速度,又需要保證得到令人滿意的進化結果。RPCL算法通過吸引競爭獲勝者,并推開次勝者的方法確定聚類中心和K值,目前已經比較成熟,在文本聚類中應用廣泛。其他的如X-means等算法的聚類效果也都得到了實驗結果的證明。3.3基于k-meas算法的聚類算法在K-means算法中,初始聚類中心是隨機選取的,因此可能造成在同一類別的樣本被強行當作兩個類的初始聚類中心,使聚類結果最終只能收斂于局部最優(yōu)解,因此K-means算法的聚類效果在很大程度上依賴于初始聚類中心的選擇。針對該問題,學界提出了多種改進的算法。Duda等在實現(xiàn)K-means算法時采用了最簡單的解決辦法,即進行多次初始聚類中心的選擇并聚類,從中找到最優(yōu)解。該解決辦法思想非常簡單,但在數(shù)據量較大時實用價值不大。(1)初始聚類中心選擇基于密度的初始聚類中心選擇方法是根據聚類對象數(shù)據點的密度分布情況選擇初始聚類中心,這樣可以很好地避免初始聚類中心過于密集的情況發(fā)生?；诿芏鹊慕鉀Q方法有許多種,其中具有代表性的有:①1994年,Katsavounidis等提出一種簡單的解決方法,即盡可能分散初始聚類中心,算法思想為:D為數(shù)據集,C為初始聚類中心集合,先選擇D邊界上的點c1作為第一個聚類中心,加入集合C中,然后使用距離c1最遠的點c2作為第二個聚類中心,也加入集合C中。maxx∈D(minc∈C(d(x,c)))(2)maxx∈D(minc∈C(d(x,c)))(2)隨后迭代計算式(2)的值,選擇符合條件的點作為初始聚類中心。事實上,式(2)就是計算空間中的每個點與已經被選取的聚類中心的距離,找出離該點最近的聚類中心,然后比較它們與最近聚類中心的距離,選出距離最大的點作為聚類中心。②2004年,Khan等提出了CCIA算法,其主要思想是利用數(shù)據點的均值、標準差、百分位數(shù)等統(tǒng)計信息提供數(shù)據點的密度分布信息,可以得到m個描述數(shù)據的標簽信息,在標簽上進行聚類得到K’(K’>K)個聚類中心,然后進行合并,從而得到初始聚類中心,通過在多個數(shù)據集上的實驗,證明了CCIA算法的優(yōu)越性。③2007年,Redmond等提出了另一種基于密度的解決辦法,即通過構建Kd-tree得到數(shù)據集的密度分布,然后利用密度信息,采用類似于Katsavounidis等的算法得到初始聚類中心。④2006年,張文君等提出的算法類似于CCIA,其思想為:若K-means算法的初始聚類中心分布在點密度較大區(qū)域,則能獲得更好的收斂速度和聚類效果,因此利用聚類數(shù)據的均值標準差與數(shù)據分布的關系則可得到更好的初始聚類中心選取方法。⑤2007年,牛琨等提出了基于密度指針的初始聚類中心選擇算法DP。DP算法以網格單元的幾何中心為對稱中心,連接該中心與網格單元各頂點,形成超三角形子空間;進而根據各超三角形子空間與鄰居單元相鄰的超三角形子空間的密度差異確定密度指針的方向,并根據密度指針計算出每個密集網格單元的聚集因子;最后將具有較大局部聚集因子的網格單元簇的重心作為初始聚類中心。⑥2010年,張文明等提出的文本聚類初始中心選擇算法的思想是:給定閾值R、t,對于文本集中任意一個文本p,如果在半徑R的鄰域之內只有自身一個文本,則將該文本加入候選參考集。如果在半徑R的鄰域之內含有不少于t個文本,則稱p為核心文本,將p的R鄰域內的所有文本的均值加入候選參考集。這樣就可得到候選參考集S{S1,S2,…,Sj},如果j大于設定的聚類數(shù)K,則將候選參考集中最相似的兩個文本刪除,將其均值放入候選參考集。如果j小于設定的聚類數(shù)K,則重新設定閾值R、t的值。通過三組實驗,結果表明該算法在聚類效果和穩(wěn)定性方面都有了一定的提高。(2)基于局部最優(yōu)估計的聚類優(yōu)化隨著研究的深入,許多優(yōu)化算法也被應用于初始聚類中心的選擇。其中模擬退火算法以其高效的尋優(yōu)效率被廣泛應用。模擬退火算法是模擬物理學上固體退火過程的一種尋優(yōu)算法,最早由Metropolis等在1953年提出。20世紀80年代,模擬退火算法被應用到組合優(yōu)化問題,算法思想為:先設定一個初始解X作為當前解,并設定初始溫度C作為控制參數(shù);然后在當前解的鄰域中隨機產生一個新解X’,計算轉移概率,如果新解優(yōu)于當前解,則置轉移概率為1,如果新解劣于當前解,則賦予一定的轉移概率,轉移概率的計算公式為exp(-(f(X’)-f(X))/C),不斷迭代以上過程,最終以概率1得到全局最優(yōu)。由于模擬退火算法在優(yōu)化過程中允許目標函數(shù)以一定的概率惡化,因此可以避免其他算法容易陷入局部最優(yōu)解的問題。1989年,Klein等進行了實證研究,對模擬退火算法和經典K-means算法的聚類效果進行了比較,結果表明模擬退火算法獲得了較好的聚類效果,但是算法的時間復雜度增加明顯。2009年,Dong等先通過二分K-means算法將數(shù)據集分為K個大類,再利用模擬退火算法優(yōu)化聚類中心,提高了聚類的準確度。和模擬退火算法一樣,遺傳算法也被應用于初始聚類中心的優(yōu)化。1991年,Bhuyan等提出可以用遺傳算法改進聚類效果,隨后Jones等,Babu等也相繼提出應用遺傳算法改進K-means算法初始聚類中心的思路?；诖?1999年,Krishna等提出GKA算法(GeneticK-meansAlgorithm)。在此前的算法中,染色體交叉和適應度計算存在一個矛盾,即優(yōu)化一方的計算復雜度會影響到另一方的速度,而GKA算法采取了效率更高的染色體編碼方案解決了該問題。2000年,Maulik等在多個人工數(shù)據集和現(xiàn)實數(shù)據集中對應用遺傳算法優(yōu)化后的K-means算法進行了測試,得到了明顯優(yōu)于傳統(tǒng)K-means算法的聚類效果。2007年,Laszlo等采用了新的交叉算子改進了該算法,實驗結果證明,在基準測試程序和大規(guī)模數(shù)據集上,都得到了更優(yōu)的實驗效果。(3)基于局部聚類優(yōu)化算法的聚類中心聚類能力的確定除了上述方法外,國內外學者還提出了一些其他的解決方法,都取得了良好的聚類效果。1998年,Bradley等提出了RA(RefinementAlgorithm)算法,其主要思想是將原始數(shù)據集分為J個子集,運用K-meansMod算法對J個子集進行聚類,(K-meansMod算法是Bradley等對K-means算法的修改,主要的不同在于對空類的處理),得到聚類中心集,共J×K個點,再分別對這J×K個點運用K-means算法,得到的K個類中心作為最終初始聚類中心。2001年,Bandyopadhyay等提出了SAKM聚類算法,算法綜合了模擬退火算法的尋優(yōu)能力和K-means算法的搜索能力,在聚類過程中不再采用確定性的聚類方式,而是根據數(shù)據點離聚類中心的距離賦予數(shù)據點一定的轉移概率,最終完成聚類。2008年,Zalik提出的算法很好地解決了K-means算法的兩個問題:K值和初始聚類中心的選擇。即構建一個耗損函數(shù),通過兩步使得函數(shù)取得全局最小值,第一步通過初始聚類給每一個類賦予至少一個聚類中心,第二步在迭代中算法自動懲罰可能獲勝的非全局最優(yōu)點,最終通過調整聚類中心使得耗損函數(shù)最小化。當耗損函數(shù)取得最小值時,正確的聚類數(shù)K值和初始聚類中心也就同時確定。2010年,Cao等提出利用數(shù)據點的鄰居信息來確定初始聚類中心的方法。首先通過設定閾值ε,將距離小于ε的兩個點視為鄰居點。利用數(shù)據點的鄰居信息計算得到每個數(shù)據點的凝聚度,凝聚度的值越大,則該數(shù)據點的鄰居集出現(xiàn)在類別分界的個數(shù)越少,因而該數(shù)據點更應該被選為初始聚類中心。通過與其他三種初始聚類中心選取算法的對比證明了該算法在聚類效果和時間復雜度上的優(yōu)越性。2004年,劉立平等在RA算法基礎上提出了一種新的初始聚類中心選擇方法,算法思想為:首先從原始數(shù)據集中抽取一個樣本集,在樣本集中隨機選擇pK個(p為常數(shù))初始聚類中心,運用K-means算法得到pK個類。去除較小的類,對剩余的類運用聚類算法聚成K個類,得到K個聚類中心,再選用離這些聚類中心最近的數(shù)據點作為初始聚類中心。算法通過兩步聚類保證初始聚類中心分別屬于不同的類,經過實驗證明比RA算法具有更好的聚類效果。2005年,王漢芝等利用超立方體技術,首先將數(shù)據中心劃分為幾個區(qū)間,并計算每個區(qū)間的超立方體編碼,再利用超立方體編碼計算K-means算法的初始聚類中心。自Creator等發(fā)現(xiàn)K-means算法會受到初始聚類中心的影響而收斂于局部最優(yōu)解的問題之后,初始聚類中心的選擇就一直是K-means算法的研究熱點。上述研究中的解決方案各有優(yōu)缺點,基于密度的方法根據數(shù)據點的密度信息使得初始聚類中心盡可能分散開來,一定程度上緩解了局部最優(yōu)解問題,但是卻難以做到進一步的優(yōu)化。利用模擬退火算法和遺傳算法這樣的優(yōu)化算法對初始聚類中心進行優(yōu)化是目前學界研究的熱點。相比確定K值,優(yōu)化算法應用于初始聚類中心的選擇更加合適,目前已經提出了許多比較成熟的算法,并且已經有相關的專著問世。值得一提的是,該方向國內的許多研究成果也十分出色,如王漢芝、牛琨等學者的研究。3.4基于k-meas算法的分類屬性問題傳統(tǒng)的K-means算法只適用于處理數(shù)值屬性的數(shù)據,而對于分類屬性和混合屬性數(shù)據集則不太適用。圍繞該問題,國外學者提出了眾多解決方法,1995年Ralambondrainy提出將分類屬性轉化為多個取值為0和1的數(shù)值屬性,再運用K-means算法的思路;1997年、1998年Huang分別提出了適用于純分類屬性數(shù)據集的K-modes算法和適用于混合屬性數(shù)據集的K-prototypes算法。(1)分類數(shù)據集的定義K-modes算法針對分類數(shù)據的特點引入Modes的概念來代替原有算法中的聚類中心Means。首先給出分類數(shù)據之間的距離度量方法,數(shù)據點X(x1,x2,…,xj)和Y(y1,y2,…,yj)之間的距離定義為:d(X,Y)=m∑j=1δ(xj,yj)(3)d(X,Y)=∑j=1mδ(xj,yj)(3)其中函數(shù)δ定義為:δ(xj,yj)={0xj=yj1xj≠yj(4)Modes的定義為:給定任意的分類數(shù)據集X(X1,X2,…,Xn),都有m個分類屬性A{A1,A2,…,Am},使得Xi取得集合A中的一個分類,那么分類數(shù)據集X的Modes(記為Q),Q{q1,q2,…,qm}使得目標函數(shù)D(Q,X)取得最小值。D(Q,X)=n∑i=1d(Xi,Q)(5)K-modes算法是K-means算法在分類數(shù)據集應用上的擴展。相比其他解決方法,K-modes算法無需對分類數(shù)據進行變換,Huang通過在大豆疾病數(shù)據集和健康保險數(shù)據集上的實驗證明了K-modes優(yōu)秀的收斂速度和聚類性能。(2)面向聚類目標函數(shù)的算法K-prototypes算法是在K-means和K-modes算法的基礎上提出的,用于處理混合屬性數(shù)據集。與K-modes算法一樣,Huang還首先給出了混合屬性情況下數(shù)據點之間的距離度量方法,對于兩個混合屬性對象集X,Y,設前p個數(shù)據點為數(shù)值屬性,后面為分類屬性。則距離度量公式為:d2(X,Y)=p∑j=1(xj-yj)2+γm∑j=p+1δ(xj,yj)(6)隨后也相應地對聚類目標函數(shù)進行了改寫:Ρ(W,Q)=k∑l=1(n∑i=1wi,lp∑j=1(xi,j-ql,j)2+γn∑i=1wi,lm∑j=p+1δ(xi,j,ql,j))(7)K-prototypes算法就是要找到最佳的Q,使得目標函數(shù)P(W,Q)取得最小值。除了K-modes和K-prototypes算法以外,Chaturvedi等在2001年也提出了一項面向分類數(shù)據集的K-modes-CGC算法。Huang在后期的研究中證明了K-modes-CGC算法與原始的K-modes算法是等價的。K-modes和K-prototypes算法很好地解決了K-means算法在處理分類數(shù)據集和混合數(shù)據集上的不足。但是,與K-means算法一樣,K-modes算法也需要預先設定初始Modes,這樣算法會受到初始Modes的影響而收斂于一個局部最優(yōu)解。基于這個問題,Sun等在2002年提出應用迭代初始點求精算法得到初始Modes,再應用K-modes算法,該算法得到了比普通K-modes算法更好的聚類效果。(3)混合屬性數(shù)據聚類計算方法2006年,蔣盛益等針對K-modes算法的不足提出了K-summary算法,認為K-modes算法采用Modes來表示類的對應“中心”,難以準確反映類中對象的取值情況,會導致距離計算不夠精確,從而影響聚類質量。因此,他們提出用摘要信息CSI(ClusterSummaryInformation)來表示一個類,CSI包括集合{n,Summary}中兩項信息,n表示類大小,Summary則由分類屬性中不同取值的頻度信息和數(shù)值型屬性的質心兩部分組成。同時提出了一套與CSI配套的距離計算方法,適用于混合屬性數(shù)據集。K-summary算法的步驟類似于K-means算法:先通過初始化,選擇k個初始點構造初始的類CSI,再將數(shù)據集中的每個點劃分到最近的類中,更新類CSI的值,迭代以上過程,直到算法收斂。采用大豆疾病等5個數(shù)據集進行測試,結果表明,相比K-modes和K-prototypes算法,K-summary算法取得了更好的聚類效果,但是需要付出更大的時間和空間開銷。除了提到的三種算法以外,2010年,Roy等還提出了基于遺傳算法的混合屬性數(shù)據聚類K-means算法,采用新的染色體編碼方案和適應度計算方法解決了混合屬性數(shù)據