數(shù)據(jù)挖掘中聚類算法的新發(fā)展-2019年

數(shù)據(jù)挖掘中聚類算法的新發(fā)展0引言聚類分析是數(shù)據(jù)挖掘技術(shù)中重要的組成部分，它能夠在潛在的數(shù)據(jù)中發(fā)現(xiàn)令人感興趣的數(shù)據(jù)分布模式[1]。聚類分析被廣泛應(yīng)用在金融數(shù)據(jù)的分類、空間數(shù)據(jù)處理、衛(wèi)星圖片分析和醫(yī)學(xué)圖像的自動檢測中。聚類分析就是把數(shù)據(jù)集分成簇,使簇內(nèi)數(shù)據(jù)盡量相似,簇間數(shù)據(jù)盡量不同。聚類的嚴(yán)格數(shù)學(xué)描述如下[2]:聚類分析可以作為獨立的數(shù)據(jù)挖掘工具，用來獲得數(shù)據(jù)分布的情況，觀察每個簇的特點，集中對特定的某些簇作進(jìn)一步處理；也可以作為其他數(shù)據(jù)挖掘算法（如特征和分類等）的預(yù)處理。到目前為止，傳統(tǒng)的聚類分析方法可以分為以下幾類[3]：a)基于劃分的方法（partitioningmethod），代表算法有Kmeans[4~6]、K_MEDOIDS[7]、CLARANS[8]等；b)層次方法(hierarchicalmethod)，代表算法有BIRCH[9]、CURE[1]、Chameleon[10]、CACTUS[11]等；c)基于網(wǎng)格的方法(gridbasedmethod)，代表算法有STING[12]、CLIQUE[13]、WaveClusier[14]等；d)基于模型的方法(modelbasedmethod)，通常有統(tǒng)計的方法和神經(jīng)網(wǎng)絡(luò)方法兩種；e)基于密度的方法(densitybasedmethod)，代表算法有DBSCAN[15]和OPTICS[16]等。聚類是一個富有挑戰(zhàn)性的研究領(lǐng)域，它的潛在應(yīng)用提出了各自特殊的要求。在數(shù)據(jù)挖掘領(lǐng)域中對聚類算法的典型要求主要有以下幾個方面：a)可伸縮性。聚類算法對小數(shù)據(jù)集和大規(guī)模數(shù)據(jù)有同樣的效果。b)處理不同數(shù)據(jù)類型屬性的能力。實際應(yīng)用要求算法能夠處理不同類型的數(shù)據(jù)。c)能發(fā)現(xiàn)任意形狀的聚類。聚類特征的未知性決定聚類算法要能發(fā)現(xiàn)球形的、嵌套的、中空的等任意復(fù)雜形狀和結(jié)構(gòu)的聚類。d)決定輸入?yún)?shù)的領(lǐng)域知識最小化。聚類算法要盡可能地減少用戶估計參數(shù)的最佳取值所需要的領(lǐng)域知識。e)能夠有效地處理噪聲數(shù)據(jù)。聚類算法要能處理現(xiàn)實世界的數(shù)據(jù)庫中普遍包含的孤立點、空缺或錯誤的數(shù)據(jù)。f)對于輸入記錄的順序不敏感。聚類算法對不同次序的記錄輸入應(yīng)具有相同的聚類結(jié)果。g)高維性。聚類算法不僅要擅長處理低維數(shù)據(jù)集，還要處理高維、數(shù)據(jù)可能稀疏和高度偏斜的數(shù)據(jù)集。h)基于約束的聚類。聚類結(jié)果既要滿足特定的約束，又要具有良好聚類特性。i)可解釋性和可用性。聚類結(jié)果應(yīng)該是可解釋的、可理解和可用的。所有的聚類方法都具有各自的特點。有些以方法簡單、執(zhí)行效率高見長（如Kmeans）；有些對任意形狀、大小的類識別能力強（如CUBN（clusteringusingborderandnearest））；有些能很好地過濾噪聲數(shù)據(jù)（如DBSCAN）。但這些方法都有各自的局限性。例如Kmeans方法只能識別大小近似的球形類；CUBN、DBSCAN的時間復(fù)雜度都為O(n2)。另外，很多聚類方法對輸入?yún)?shù)十分敏感，而且參數(shù)很難確定，加重了用戶的負(fù)擔(dān)。目前普遍認(rèn)為不存在某種方法能適合各種特點的數(shù)據(jù)。經(jīng)典聚類分析方法在很多領(lǐng)域已經(jīng)得到了成功的應(yīng)用。例如在商業(yè)上，聚類可以幫助市場分析人員從消費者數(shù)據(jù)庫中區(qū)分出不同的消費群體，并且概括出每一類消費者的消費模式或習(xí)慣；在生物學(xué)中，它可以被用來輔助研究動物、植物的分類，可以用來分類具有相似功能的基因，還可以用來發(fā)現(xiàn)人群中一些潛在的結(jié)構(gòu)等；另外它在空間數(shù)據(jù)處理、金融數(shù)據(jù)、衛(wèi)星圖像等領(lǐng)域都得到非常成功的應(yīng)用。但是由于每一種方法都有缺陷，再加上實際問題的復(fù)雜性和數(shù)據(jù)的多樣性，使得無論哪一種方法都只能解決某一類問題。近年來，隨著人工智能、機器學(xué)習(xí)、模式識別和數(shù)據(jù)挖掘等領(lǐng)域中傳統(tǒng)方法的不斷發(fā)展以及各種新方法和新技術(shù)的涌現(xiàn)，數(shù)據(jù)挖掘中的聚類分析方法得到了長足的發(fā)展。1數(shù)據(jù)挖掘領(lǐng)域中的聚類方法新發(fā)展1．1基于群的聚類方法這種方法可看做進(jìn)化計算的一個分支。它模擬了生物界中蟻群、魚群和鳥群在覓食或逃避敵人時的行為?？v觀文獻(xiàn)中對于群的分類方法的研究，將這種方法分為兩類：一類是蟻群算法或蟻群優(yōu)化（antcolonyoptimization，ACO）；另一類稱為PSO（particleswarmoptimization)[17]。用蟻群算法或蟻群優(yōu)化來進(jìn)行分類規(guī)則挖掘的算法稱為antminer[18，19]。Antminer是將數(shù)據(jù)挖掘概念和原理與生物界中蟻群行為結(jié)合起來形成的新算法。受生物進(jìn)化機理的啟發(fā)，1991年意大利學(xué)者A.Dorigo等人提出了蟻群算法，它是一種新型的優(yōu)化方法。該算法不依賴于具體問題的數(shù)字描述，具有全局優(yōu)化能力。后來其他科學(xué)家根據(jù)自然界真實螞蟻堆積尸體及分工行為，提出螞蟻的聚類算法[20,21]；2002年，Labroche等人提出基于螞蟻化學(xué)識別系統(tǒng)的聚類方法?？偟恼f來,基于蟻群算法的聚類方法從原理上可以分為四種:運用螞蟻覓食的原理,利用信息素來實現(xiàn)聚類[22];利用螞蟻自我聚集行為來聚類;基于螞蟻堆的形成原理實現(xiàn)數(shù)據(jù)聚類;運用蟻巢分類模型,利用螞蟻化學(xué)識別系統(tǒng)進(jìn)行聚類[23]。蟻群聚類算法的許多特性，如靈活性、健壯性、分布性和自組織性等，使其非常適合本質(zhì)上是分布、動態(tài)及又要交錯的問題求解中,能解決無人監(jiān)督的聚類問題,具有廣闊的前景。后來antminer3[24]對antminer進(jìn)行了改進(jìn)，它的預(yù)測精度高于antminer。PSO是進(jìn)化計算的一個新的分支，它模擬了魚群或鳥群的行為。PSO將群中的個體稱為particles，整個群稱為swarm。在優(yōu)化領(lǐng)域，PSO可以與遺傳算法相媲美。文獻(xiàn)[25]將PSO用于分類，對discretePSO(DPSO)[26]lineardecreasingweightPSO(LDWPSO)[27]和constrictedPSO(CPSO)[28]進(jìn)行了比較，并選取CPSO作為挖掘分類規(guī)則的工具。文獻(xiàn)[29]對CPSO進(jìn)行了改進(jìn)，并與遺傳算法進(jìn)行了比較。實驗結(jié)果表明，在預(yù)測精度和運行速度方面，PSO方法都占優(yōu)勢。對ACO或PSO在數(shù)據(jù)挖掘中應(yīng)用的研究仍處于早期階段，要將這些方法用到實際的大規(guī)模數(shù)據(jù)挖掘的聚類分析中還需要做大量的研究工作。1．2基于粒度的聚類方法從表面上看，聚類和分類有很大的差異――聚類是無導(dǎo)師的學(xué)習(xí)，而分類是有導(dǎo)師的學(xué)習(xí)。更進(jìn)一步地說，聚類的目的是發(fā)現(xiàn)樣本點之間最本質(zhì)的抱團(tuán)性質(zhì)的一種客觀反映；分類在這一點上卻不大相同。分類需要一個訓(xùn)練樣本集，由領(lǐng)域?qū)＜抑该髂男颖緦儆谝活?，哪些樣本?shù)據(jù)屬于另一類，但是分類的這種先驗知識卻常常是純粹主觀的。如果從信息粒度的角度來看的話，就會發(fā)現(xiàn)聚類和分類有很大的相通之處：聚類操作實際上是在一個統(tǒng)一粒度下進(jìn)行計算的；分類操作是在不同粒度下進(jìn)行計算的[30]。所以說在粒度原理下，聚類和分類是相通的，很多分類的方法也可以用在聚類方法中。作為一個新的研究方向，雖然目前粒度計算還不成熟，尤其是對粒度計算語義的研究還相當(dāng)少，但是相信隨著粒度計算理論本身的不斷完善和發(fā)展，今后幾年它必將在數(shù)據(jù)挖掘中的聚類算法及其相關(guān)領(lǐng)域得到廣泛的應(yīng)用。1．3基于模糊的聚類方法在實踐中大多數(shù)對象沒有嚴(yán)格的屬性，它們的類屬和形態(tài)存在著中介性，適合軟劃分。由于模糊聚類分析具有描述樣本類屬中間性的優(yōu)點，能客觀地反映現(xiàn)實世界，成為當(dāng)今聚類分析研究的主流。最早系統(tǒng)的表達(dá)和研究模糊聚類問題的著名學(xué)者Ruspini[31~33]率先提出了模糊劃分的概念。利用這一概念，人們相繼提出了多種模糊聚類分析方法。比較典型的有基于相似性關(guān)系和模糊關(guān)系的方法[34~36]、基于模糊等價關(guān)系的傳遞閉包方法[37，38]、基于模糊凸輪的最大樹方法[39~41]以及基于數(shù)據(jù)集的凸分解、動態(tài)規(guī)劃和難以辨識關(guān)系[42~44]等方法。然而上述方法均不適于大數(shù)據(jù)的情況，難以滿足實時性較高的場合?；谀繕?biāo)函數(shù)的模糊聚類方法把聚類歸結(jié)成一個帶約束的非線性規(guī)劃，通過優(yōu)化求解獲得數(shù)據(jù)集的模糊劃分和聚類?；谀繕?biāo)函數(shù)的模糊聚類算法成為新的研究熱點。FCM(基于目標(biāo)的模糊聚類方法)的原理為：由于梯度法的搜索方向總是沿著能量減小的方向，使得算法存在易陷入局部極小值和對初始化敏感的缺點。為了克服上述缺點，近幾年來人們提出了各種算法對目標(biāo)函數(shù)進(jìn)行優(yōu)化。采取的主要措施是在FCM算法中引入全局尋優(yōu)法[45]。例如1989年徐雷提出模擬退火對硬分類矩陣U進(jìn)行退火處理的硬C均值算法[46]；1993年Selim[47]和Asultan[48]等人提出模擬退火+模糊聚類算法；1995年劉健莊、謝維新等人提出用遺傳算法進(jìn)行硬聚類和模糊聚類的分析方法；1999年楊廣文等人利用確定性退火技術(shù)提出一種聚類模型及聚類算法[49]，然而由于模擬退火算法只有當(dāng)溫度下降足夠慢時才能收斂于全局最優(yōu)點，極長的運行時間限制了其實用性；1994年Babu和Murty提出利用進(jìn)化策略對目標(biāo)函數(shù)進(jìn)行聚類的方法[50]；2002年陳金山、韋崗提出遺傳+模糊C均值混合聚類算法[51]。這些算法利用遺傳算法的全局搜索能力來擺脫FCM聚類運算時可能陷入的局部極小點，優(yōu)化了聚類的性能。眾所周知，傳統(tǒng)的進(jìn)化算法是一種具有“生成+檢測”迭代過程的搜索算法。這種算法多是由體現(xiàn)群體搜索和群體中個體之間信息交換的兩大策略的交叉和變異算子組成，為每個個體提供了優(yōu)化機會，即進(jìn)化的趨勢。進(jìn)化算法在進(jìn)化過程中不可避免地產(chǎn)生退化現(xiàn)象的固有缺點，導(dǎo)致了進(jìn)化后期的波動現(xiàn)象，并會出現(xiàn)迭代次數(shù)過多和聚類準(zhǔn)確率不太高的現(xiàn)象。在某些情況下，這種退化現(xiàn)象還比較明顯。免疫進(jìn)化算法[52]（immuneevolutionaryalgorithm,IEA）借鑒生命科學(xué)中的免疫概念和理論在保留原算法優(yōu)良特性的前提下，力圖有選擇、有目的地利用待求問題中的一些特征或知識來抑制其優(yōu)化過程中出現(xiàn)的退化現(xiàn)象。免疫算法的核心在于免疫算子的構(gòu)造。免疫算子通過接種疫苗或免疫選擇兩個步驟來完成。免疫進(jìn)化算法能提高個體的適應(yīng)度和防止群體的退化，從而達(dá)到減輕原有進(jìn)化算法后期的波動現(xiàn)象和提高收斂速度。文獻(xiàn)[53]提出了基于免疫進(jìn)化的模糊聚類算法(IFCM、IFCSS、IFCL)和基于免疫進(jìn)化的硬聚類算法。這種算法既較大地提高了獲取全局最優(yōu)的概率，又減輕了基于遺傳聚類算法在遺傳后期的波動現(xiàn)象。進(jìn)一步的工作是參數(shù)的適當(dāng)選取和減小運行時間等。文獻(xiàn)[54]提出了一種基于有限資源的模糊網(wǎng)絡(luò)結(jié)構(gòu)聚類算法。由于該算法引入模糊識別球，大大提高了運算效率，使得該算法更加適合于大數(shù)據(jù)集聚類分析；同時，因為采用了有限資源網(wǎng)絡(luò)，克服了標(biāo)準(zhǔn)基于網(wǎng)絡(luò)聚類算法對噪聲點敏感的缺點，使得到的網(wǎng)絡(luò)具有清晰的結(jié)構(gòu)；通過分析網(wǎng)絡(luò)神經(jīng)元的最小樹，能夠快速準(zhǔn)確地獲得類別數(shù)以及相關(guān)的分類信息，從而實現(xiàn)了聚類分析的自動化。該算法不依賴于初始原型的選擇，也無須類數(shù)的先驗知識，可以真正做到無監(jiān)督自學(xué)習(xí)。該算法中只需要預(yù)先設(shè)定最大資源數(shù)一個參數(shù)，而初始的網(wǎng)絡(luò)規(guī)模并不影響最終的結(jié)果，所以該算法在現(xiàn)實生活中是非常方便的。人們對于客觀事物的認(rèn)識往往帶有模糊性。人類大多用一些模糊的詞語來交流思想、互通信息，然后進(jìn)行推理分析、綜合判斷，最后作出決策?？陀^事物是有確定性的，而反映在人的認(rèn)識上卻帶有模糊性。人對于客觀事物的識別往往只通過一些模糊信息的綜合，便可以獲得足夠精確的定論。實質(zhì)上，上面所說的模糊聚類算法就是利用了人認(rèn)識事物的規(guī)律，使計算機接近人類的智能。模糊聚類分析仍然是今后研究的重要課題之一。1．4基于綜合其他領(lǐng)域的聚類方法1．4．1量子聚類目前常用的聚類算法是基于距離的分割聚類算法，它僅僅根據(jù)數(shù)據(jù)間的幾何相似性進(jìn)行分類，是一種無監(jiān)督的學(xué)習(xí)方法。一般來說，它的效果并不加入數(shù)據(jù)間的幾何相識性進(jìn)行分類，是一種無監(jiān)督的學(xué)習(xí)方法，其效果并不盡如人意；而且在現(xiàn)有的聚類算法中，聚類數(shù)目一般需要事先指定，如Kohenon自組織算法、Kmeans算法和模糊Kmeans聚類算法。然而，在很多情況下類別數(shù)是不可知的，而且絕大多數(shù)聚類算法的結(jié)果一般都要依賴于初值，即使類別數(shù)目保持不變，聚類的結(jié)果也可能相差很大[55]。受到物理學(xué)中量子機理和特性的啟發(fā)，可以用量子理論解決此類問題。一個很好的例子就是基于相關(guān)點的Pott自旋和統(tǒng)計機理提出的量子聚類模型。它把聚類問題看做一個物理系統(tǒng)。許多算例表明：對于傳統(tǒng)聚類算法無能為力的幾種聚類問題，該算法都得到了比較滿意的結(jié)果。Horn等人提出了一種新的量子聚類算法[56]。該方法是對尺度空間向量聚類和支撐矢量機聚類固有思想的一種擴充。類似于支撐機聚類算法，該方法也與Hilbert空間中向量的每個點相關(guān)聯(lián)；同時，他還強調(diào)了它們的總和，這等于尺度空間概率函數(shù)。在這一點上與尺度空間聚類算法類似。新方法是研究Hilbert空間的一個算子，由Schrodinger等式表示，其概率函數(shù)是一個解。這個Schrodinger等式包括一個從概率函數(shù)中解析導(dǎo)出的勢函數(shù)。本文將聚類中心與勢能最小值聯(lián)系在一起，最后驗證了新方法在已知數(shù)據(jù)集合上的可行性，并通過限定Schrodinger勢能對數(shù)據(jù)點位置的估價，將此方法應(yīng)用到高維空間中的聚類問題。1．4．2核聚類算法目前比較經(jīng)典的聚類算法，如Kmeans、模糊Kmeans聚類算法和Kohonen自組織神經(jīng)網(wǎng)絡(luò)[57]等，只能對一些經(jīng)典分布的樣本奏效。它們沒有對樣本的特征進(jìn)行優(yōu)化，而是直接利用樣本的特征進(jìn)行聚類。因此這些方法的有效性在很大程度上取決于樣本的分布情況。例如一類樣本散布較大，而另一類散布較小的情況，這些方法的聚類效果就比較差。如果樣本分布更加混亂，則聚類的結(jié)果反而會面目全非[55]。通過把核方法[58，59]引入到聚類算法中，本文提出了一種核聚類方法。該方法增加了對樣本特征的優(yōu)化過程，通過利用Mercer核把輸入空間的樣本映射到高維特征空間，并在特征空間中進(jìn)行聚類。核聚類方法是普適的，并在性能上優(yōu)于經(jīng)典的聚類算法，它通過非線性映射能夠較好地分辨、提取并放大有用的特征，從而實現(xiàn)更為準(zhǔn)確的聚類；同時，算法的收斂速度也較快。在經(jīng)典聚類算法失效的情況下，核聚類算法仍能夠得到正確的聚類。1．4．3譜聚法最近一類有效的聚類方法開始受到廣泛關(guān)注。該類方法建立在譜圖理論基礎(chǔ)之上，并利用數(shù)據(jù)的相似矩陣的特征向量進(jìn)行聚類，因而統(tǒng)稱為譜聚類方法。譜聚類算法是一種基于兩點間相似關(guān)系的方法[60]，這使得該方法適用于非測度空間。算法與數(shù)據(jù)點的維數(shù)無關(guān)，而僅與數(shù)據(jù)點的個數(shù)有關(guān)，可以避免由特征向量的過高維數(shù)所造成的奇異性問題。譜聚類算法是一個判別式算法，不用對數(shù)據(jù)的全局結(jié)構(gòu)作假設(shè)，而是首先收集局部信息來表示兩點屬于同一類的可能性；然后根據(jù)某一聚類判據(jù)作全局決策，將所有數(shù)據(jù)點劃分到不同的數(shù)據(jù)集合中。通常這樣的判據(jù)可以在一個嵌入空間中得到解釋，該嵌入空間是由數(shù)據(jù)矩陣的某幾個特征向量張成的。譜方法成功的原因在于：通過特征分解，可以獲得聚類判據(jù)在放松了的連續(xù)域中的全局最優(yōu)解[55]。與其他方法相比，譜聚類方法具有明顯的優(yōu)勢。該方法不僅思想簡單、易于實現(xiàn)、不易陷入局部最優(yōu)解，而且具有識別非凸分布的聚類能力，非常適合于許多實際應(yīng)用問題。目前，譜聚類方法已應(yīng)用于語音識別、視頻分割、圖像分割、VLSI設(shè)計、網(wǎng)頁劃分、文本挖掘等領(lǐng)域。譜聚類方法盡管取得了很好的效果，但目前仍處在發(fā)展的初期。算法本身仍存在許多值得深入研究的問題。1．5多種聚類方法的融合實際應(yīng)用的復(fù)雜性和數(shù)據(jù)的多樣性往往使得單一的分類方法不夠有效。因此，學(xué)者們對多種分類方法的融合（fusion）進(jìn)行了廣泛研究，取得了一系列成果?？v觀文獻(xiàn)中的研究，大致可以分為以下幾類：a）基于傳統(tǒng)聚類方法的融合，如CLIQUE[13]、CUBN[61]、CURD[62]、RDVS（clusteringusingreferencesanddensitybyVISOM）[61]方法等。b）模糊理論與其他聚類方法融合的方法，如遺傳+模糊C均值混合聚類算法[51]等。c）遺傳算法與機器學(xué)習(xí)融合的方法。d）傳統(tǒng)聚類方法與其他學(xué)科理論融合的方法，如上文中的量子算法、核算法和譜算法等。CLIQUE方法就是一種綜合了基于密度和網(wǎng)格的聚類方法。它首先將數(shù)據(jù)空間劃分為網(wǎng)格單元；然后識別其中密度大于某輸入?yún)?shù)的密集單元，類定義為相連密集單元的最大集合。此方法明顯提高了算法執(zhí)行效率，但由于方法大大簡化，聚類的精確性較低。CUBN是一種基于密度、網(wǎng)格和距離的聚類新方法。為了提高算法執(zhí)行效率，該方法首先將數(shù)據(jù)空間劃分為網(wǎng)格單元；然后在每個單元中利用密度方法識別出該單元中各類邊界，并使用最鄰近距離的方法將非邊界點聚到各個類中；最后將各單元中相連的類合并成最后的聚類結(jié)果。CUBN方法綜合了基于密度和網(wǎng)格聚類方法的優(yōu)點，不僅算法執(zhí)行效率高，而且可識別任意形狀的聚類、過濾噪聲數(shù)據(jù)。Guha等人提出的CURE[61]方法采用了多代表點的思想來識別數(shù)據(jù)空間中形狀復(fù)雜和不同大小的類。CURE方法的出現(xiàn)，使人們對此思想很感興趣，出現(xiàn)了眾多基于代表點的聚類方法。CURD[62]也受到CURE