流數(shù)據(jù)聚類算法是一種適用于大規(guī)模數(shù)據(jù)聚類的算法，盡管流數(shù)據(jù)聚類算法已經(jīng)獲得廣泛研究，但它仍然是數(shù)據(jù)挖掘的重要研究課題[1-3]。CluStream是較早的流數(shù)據(jù)聚類算法[3]，它采用微聚類來獲取和保存歷史流數(shù)據(jù)的統(tǒng)計信息。兩個主要的局限是，ClusStream只能用于線性可分?jǐn)?shù)據(jù)并且不適合于高維流數(shù)據(jù)處理。為了適應(yīng)高維流數(shù)據(jù)的處理，Aggarwal等人提出了一個改進(jìn)的CluStream算法，稱為HPStream[4]，其主要思想是通過一個數(shù)據(jù)投影算法將維數(shù)降低，然后再執(zhí)行ClusStream，但它仍然無法解決非線性可分流數(shù)據(jù)的問題。Guha等人提出一種基于K均值的流數(shù)據(jù)處理方法[8]，與K均值算法本身的局限類似，該方法也同樣不能處理非線性可分流數(shù)據(jù)。另一種流數(shù)據(jù)處理模型是基于網(wǎng)格的方法，如DUCStream[5]。

　　摘要：提出一種能夠有效處理大規(guī)模分布的數(shù)據(jù)聚類問題且簡化計算復(fù)雜度的分階段非線性聚類方法，該算法包含兩個階段：首先將數(shù)據(jù)劃分為若干個球形分布的子類，采用K近鄰圖理論對原始數(shù)據(jù)計算頂點能量并提取頂點攻能量樣本；再采用K近鄰算法對該高能量樣本做一個劃分，從而得到一個考慮高能量樣本的粗劃分同時估計出聚類的個數(shù)，最后，綜合兩次聚類結(jié)果整理得到最終聚類結(jié)果。該方法的主要優(yōu)點是可以用來處理復(fù)雜聚類問題，算法較為穩(wěn)定，并且在保持聚類正確率的同時，降低了大規(guī)模分布數(shù)據(jù)為相似性度量的計算代價。

　　關(guān)鍵詞：流數(shù)據(jù),數(shù)據(jù)挖掘,聚類,非線性

　　通過動態(tài)地刪除密度小于某個閾值的區(qū)域所組成的類，這種方法可以自適應(yīng)于數(shù)據(jù)流中的類變化，但是仍然無法解決非線性可分流數(shù)據(jù)問題。流數(shù)據(jù)近鄰傳播方法StrAP[9]，雖然可以解決密度變化及自適應(yīng)估計聚類個數(shù)的問題，但是卻不能夠處理非線性可分流數(shù)據(jù)。近年來，非線性可分流數(shù)據(jù)聚類問題才引起了大家的關(guān)注[6-8]。為了解決非線性可分流數(shù)據(jù)聚類，Cao等人將經(jīng)典的密度聚類算法DBSCAN推廣到了流數(shù)據(jù)處理，提出了DenStream算法[6]。朱蔚恒等人提出的ACluStream聚類算法[7]，通過定義有空間位置信息的聚類塊，較好地克服了CluStream算法不能支持對任意形狀聚類的缺陷。劉青寶提出的基于相對密度的數(shù)據(jù)流模糊聚類算法結(jié)合了相對密度聚類和模糊聚類的優(yōu)點[8]，能形成任意形狀、多密度分辨率的層次聚類結(jié)果。這些富有啟發(fā)性的研究工作為非線性可分流數(shù)據(jù)聚類問題建立了初步的基礎(chǔ)，但該問題的研究遠(yuǎn)沒有達(dá)到人們的期望。任何新的非線性可分聚類算法的出現(xiàn)，都有可能改善流數(shù)據(jù)聚類算法的效率。

　　在設(shè)計基于進(jìn)化計算的聚類算法時，最核心的兩個問題就是進(jìn)化個體的編碼以及相似性度量。針對聚類問題的個體編碼方式有很多，其中使用較多的是借用于K-均值算法的編碼方式。即每個個體只對K個聚類中心進(jìn)行編碼，然后對數(shù)據(jù)樣本按照其與聚類中心的相似性進(jìn)行類別劃分。因此，相似性度量對這類算法的性能有重要影響。最簡單的相似性度量應(yīng)該是歐氏距離，但是以歐氏距離作為相似性度量的進(jìn)化聚類算法雖然在全局最優(yōu)化性能上比傳統(tǒng)的基于梯度下降的K-均值算法有較大提高，但同樣存在一個重要的缺點。它們只對空間分布為球形或超球體的數(shù)據(jù)具有較好的性能，而對空間分布復(fù)雜的數(shù)據(jù)聚類效果很差，這是基于歐氏距離的相似性度量的缺陷導(dǎo)致的必然結(jié)果[10]。

　　本文提出一種能夠有效處理大規(guī)模分布的數(shù)據(jù)聚類問題且簡化計算復(fù)雜度的分階段非線性聚類方法，該算法包含兩個階段：首先將數(shù)據(jù)劃分為若干個球形分布的子類，采用K近鄰圖理論對原始數(shù)據(jù)計算頂點能量并提取頂點攻能量樣本；再采用K近鄰算法對該高能量樣本做一個劃分，從而得到一個僅僅考慮高能量樣本的粗劃分同時估計出聚類的個數(shù)，最后，綜合兩次聚類結(jié)果整理得到最終聚類結(jié)果。

　　2基于核方法的聚類中心點粗劃分

　　為研究核競爭學(xué)習(xí)聚類，本項目擬提出用中心點描述子[W?]表達(dá)核空間的聚類中心點。中心點描述子[W?]是一個內(nèi)積矩陣，其每一行表達(dá)一個中心點，元素為中心點與樣本點，中心點與中心點的核空間內(nèi)積，從而給中心點在核空間內(nèi)一個確定的表達(dá)，即：

　　核空間上的競爭學(xué)習(xí)過程主要就是更新這個中心點描述子[W?]，即對于某個新來的樣本[?（xi）]，選擇核空間上距離該樣本最近中心點作為優(yōu)勝者中心點，也即中心點描述子[W?]對應(yīng)的行向量[W?v，：]；接著再使之朝著該樣本在核空間內(nèi)移動一定的距離，是這個行向量[W?v，：]得到對應(yīng)的更新，如圖9所示。這樣便可以通過中心點描述子及對應(yīng)的競爭學(xué)習(xí)過程提出一個核競爭學(xué)習(xí)框架。

　　在核競爭學(xué)習(xí)的框架上，我們將進(jìn)一步考慮添加各種自動聚類個數(shù)估計機(jī)制，如對手懲罰機(jī)制，實現(xiàn)能夠自動估計聚類個數(shù)的核競爭學(xué)習(xí)算法。為添加對手懲罰機(jī)制，我們首先初始化一個中心點描述子，使其行向量的個數(shù)，即初始聚類個數(shù)遠(yuǎn)遠(yuǎn)大于實際聚類個數(shù)，接著在核空間的競爭學(xué)習(xí)過程中，對每一個新來的樣本，不但使優(yōu)勝者中心點所對應(yīng)的行向量朝著該樣本移動，并且使第二優(yōu)勝者，即對手所對應(yīng)的行向量朝著該樣本反向移動。不斷迭代，直至收斂為止。迭代結(jié)束之時，中心點描述子[W?]的某些行向量在核空間中距離所有的樣本都非常遠(yuǎn)，即為冗余的中心點，這樣便可以去除冗余中心點，實現(xiàn)核空間自動聚類個數(shù)估計的目的。

　　核競爭測度的引入，使復(fù)雜分布數(shù)據(jù)的結(jié)構(gòu)特點得到較好的體現(xiàn)，對于現(xiàn)實世界中的聚類問題可以達(dá)到較好的效果。然而正如前文提到的，要用圖論中的最短路徑來計算流形距離，其計算復(fù)雜度要明顯高于歐式距離的計算復(fù)雜度。隨著數(shù)據(jù)集規(guī)模的增加，這個弊端尤為明顯，就更無法應(yīng)用于大規(guī)模聚類問題。對于一個數(shù)據(jù)集，如果我們只利用其中一部分樣本點的信息就可以得出對整個數(shù)據(jù)集的正確聚類，勢必會大大縮減計算量.我們發(fā)現(xiàn)，對于一個數(shù)據(jù)集，無論是超球體分布還是復(fù)雜結(jié)構(gòu)，我們總能將其劃分為若干類，使得每一類都是符合球形分布的簡單子數(shù)據(jù)集。這一步可以通過選取合適的類數(shù)K，對數(shù)據(jù)集進(jìn)行K-均值聚類輕易實現(xiàn)，而這些子數(shù)據(jù)集的聚類中心即可很好地代表整個數(shù)據(jù)集的分布特點，此時采用具有流形距離作為相似性測度的聚類算法來處理代表點集（即K-均值聚類中心集），即可獲得符合數(shù)據(jù)分布結(jié)構(gòu)的合理聚類結(jié)果.這樣就可以達(dá)到降低計算量的目的�；�于上面的思想，我們設(shè)計了如下的兩階段聚類算法。3分階段非線性聚類方法

　　該算法首先采用基于K近鄰圖理論的能量方法構(gòu)造出一個粗劃分，然后再采用多中心點競爭學(xué)習(xí)算法對粗劃分進(jìn)一步處理產(chǎn)生精確的劃分。該算法主要解決如下科學(xué)問題。頂點能量的計算，基于K近鄰圖理論的頂點能量計算決定了高能量樣本的提取及粗劃分的產(chǎn)生。研究計算頂點能量的一個關(guān)鍵是K近鄰圖中近鄰個數(shù)即參數(shù)K的選取。頂點能量確定之后，就可以提取高能量樣本及構(gòu)建對應(yīng)的K近鄰圖。多中心點競爭學(xué)習(xí)，多中心點競爭學(xué)習(xí)的主要目的是通過采用多個中心點表達(dá)一個類，同時通過競爭學(xué)習(xí)對這些中心點進(jìn)行更新從而精確化由第一階段產(chǎn)生的粗劃分。這個問題的難點在于如何確定每個類的中心點個數(shù)及如何用競爭學(xué)習(xí)法則更新這些中心點。

　　本文擬考慮提出一個兩階段的算法。在第一階段，首先采用K近鄰圖理論對原始數(shù)據(jù)計算頂點能量，然后提取50%高能量樣本，再采用K近鄰算法對該高能量樣本做一個劃分，從而得到一個僅僅考慮高能量樣本的粗劃分同時估計出聚類的個數(shù)，這一階段的一個關(guān)鍵是頂點能量的計算。該文擬采用類似于密度的全局能量估計，實現(xiàn)對任意密度及形狀分布的聚類的有效劃分。即對每一個樣本點，其頂點能量是由整個數(shù)據(jù)集合計算得到，而非由某一個近鄰關(guān)系計算所得。第一階段得到的粗劃分僅僅考慮了高能量樣本，為了對低能量樣本進(jìn)行類標(biāo)賦值，同時得到精確化的聚類結(jié)果，在第二階段擬采用多中心點競爭學(xué)習(xí)對該粗劃分進(jìn)行精確化處理，對粗劃分中的每一個類，首先采用AP聚類算法求得最佳表達(dá)該類的多個中心點，所有類的這些多個中心點的集合我們稱之為多中心點集合，然后用競爭學(xué)習(xí)算法更新這些多中心點集合。更新多中心點集合的關(guān)鍵步驟是：對于某個當(dāng)前樣本，選擇一個離其最近的某個類的中心點，并使這個中心點朝著該樣本移動某個學(xué)習(xí)步長，而該類的其他中心點及其他類的中心點保持不變。這樣不斷迭代，直至所有中心點保持不動，收斂為止。這樣便使得低能量樣本也賦值類標(biāo)，從而實現(xiàn)對該粗劃分的一個精確化處理，最終得到聚類結(jié)果。

　　第1階段旨在根據(jù)全體樣本點提供的信息，尋找若干符合球形分布的子數(shù)據(jù)集，并構(gòu)造出一個較小的代表點集，這些代表點能夠較為完整、準(zhǔn)確地表現(xiàn)整個數(shù)據(jù)集的分布形狀及結(jié)構(gòu)特點。我們選擇采用歐氏距離測度的改進(jìn)K-均值算法作為第1階段的選擇手段，將得到的聚類中心作為數(shù)據(jù)集的代表點。對于數(shù)據(jù)集X={x1，…，xN}，期望聚為K類，我們先通過TPC的第1階段將其聚為K′類，表示為C={C1，C2，…，CK′}，聚類中心為μ={μ1，μ2，…，μK′}，其中，K′>K。

　　對第1階段得到的聚類中心μ={μ1，μ2，…，μk′}，我們在TPC的第2階段使用MEC將其聚為K類。在設(shè)計基于進(jìn)化計算的聚類算法時，最核心的兩個問題就是進(jìn)化個體的編碼以及相似性度量。我們從組合優(yōu)化的角度來考慮聚類問題，將指定類別數(shù)K的聚類問題建模為一個從數(shù)據(jù)集中選擇K個典型樣本來代表K個類別的優(yōu)化問題，然后按照樣本與K個典型樣本的相似性對數(shù)據(jù)集進(jìn)行類別劃分。因此，每個個體代表一種典型樣本序號的組合，顯然，對于一個K類的聚類問題，一個個體的長度為K，第1個基因位為代表第1個類別的樣本序號，第2個基因位為代表第2個類別的樣本序號，依此類推，為了更加具體地說明這種新的個體表示方式。

　　該方法應(yīng)用視頻總結(jié)的聚類。如在圖像分割應(yīng)用中，傳統(tǒng)線性可分聚類技術(shù)需要對圖像的像素提取線性可分的特征，同時需要用戶提供圖像的感興趣個體的個數(shù)；在視頻聚類應(yīng)用中，這類技術(shù)需要對視頻的每一幀提取易劃分的低維特征，同時需要提供視頻中場景的個數(shù)，在大規(guī)模視頻聚類實時處理中，這是兩個聚類算法應(yīng)用的瓶頸問題。該文所提出的同時具有自動初始化和非線性可分能力的分階段聚類方法將有利于同時克服這兩個問題，并在圖像分析方面展示新的應(yīng)用效果，在視頻的關(guān)鍵幀選取任務(wù)中，聚類算法將視頻的每一幀看成特征空間里面的一個樣本點，假設(shè)該特征空間中的代表點集合（如聚類的中心點）可以當(dāng)成整個視頻序列的關(guān)鍵幀，則視頻關(guān)鍵幀的選取問題就直接轉(zhuǎn)化為聚類問題中的中心點選取問題。視頻聚類類似于場景圖片聚類，一段場景的視頻段通常包含多個主題，但它通常強(qiáng)調(diào)實時性。該文應(yīng)用上述已經(jīng)提出的非線性競爭學(xué)習(xí)的快速聚類算法來研究它在視頻聚類上的應(yīng)用，實驗顯示該方法提高了視頻分析效率。

　　4結(jié)束語

　　本文提出一種能夠有效處理大規(guī)模分布的數(shù)據(jù)聚類問題且簡化計算復(fù)雜度的分階段非線性聚類方法，該算法包含兩個階段：首先將數(shù)據(jù)劃分為若干個球形分布的子類，采用K近鄰圖理論對原始數(shù)據(jù)計算頂點能量并提取頂點攻能量樣本；再采用K近鄰算法對該高能量樣本做一個劃分，從而得到一個僅僅考慮高能量樣本的粗劃分同時估計出聚類的個數(shù)，最后，綜合兩次聚類結(jié)果整理得到最終聚類結(jié)果。該方法的主要優(yōu)點是可以用來處理復(fù)雜聚類問題，算法較為穩(wěn)定，并且在保持聚類正確率的同時，降低了大規(guī)模分布數(shù)據(jù)為相似性度量的計算代價。

　　參考文獻(xiàn)：

　　[1]金澈清，錢衛(wèi)寧，周傲英.流數(shù)據(jù)分析和管理綜述[J].軟件學(xué)報，2004，15（8）：1172-1181.

　　[2]周曉云，孫志揮，張柏禮.高維數(shù)據(jù)流聚類及其演化分析研究[J].計算機(jī)研究與發(fā)展，200643（11）：2005-2011.

　　[3]張晨，金澈清，周傲英.一種不確定數(shù)據(jù)流聚類算法[J].軟件學(xué)報，2010，21（9）：2173-2182.

　　[4]AggarwalCC，HanJ，WangJ.Aframeworkforprojectedclusteringofhighdimensionaldatastreams[M].Proceedingsofthe30thInternationalConferenceonVeryLargeDataBases，MorganKaufmann，Toronto，Canada，2004.

　　[5]GaoJ，LiJ，ZhangZ.Anincrementaldatastreamclusteringalgorithmbasedondenseunitsdetection[M].ProceedingsoftheNinthPacific-AsiaConferenceonAdvancesinKnowledgeDiscoveryandDataMining，LectureNotesinComputerScience，Springer，2005.

　　[6]CaoF，EsterM，QianW.Density-basedclusteringoveranevolvingdatastreamwithnoise[M].J.Ghosh，D.Lambert，D.B.Skillicorn，J.Srivastava（Eds.），ProceedingsoftheSixthSIAMInternationalConferenceonDataMining，SIAM，Bethesda，Maryland，USA，2006.

轉(zhuǎn)載請注明來自：http://www.jinnzone.com/jisuanjiyingyonglw/28950.html