杜淑穎

摘要：就精確系數(shù)不算太嚴(yán)格的情況而言，針對各種大型數(shù)據(jù)集，通過對比各種聚類算法，提出了一種部分優(yōu)先聚類算法。然后在此基礎(chǔ)之上分析研究聚類成員的產(chǎn)生過程與聚類融合方式，通過設(shè)計共識函數(shù)并利用加權(quán)方式確定類中心，在部分優(yōu)先聚類算法的基礎(chǔ)上進(jìn)行聚類融合，從而使算法的計算準(zhǔn)度加以提升。通過不斷的實驗，我們可以感受到優(yōu)化之后算法的顯著優(yōu)勢，這不僅體現(xiàn)在其可靠性，同時在其穩(wěn)定性以及擴(kuò)展性、魯棒性等方面都得到了很好的展現(xiàn)。

關(guān)鍵詞：部分優(yōu)先聚類算法；聚類融合；效率；精度

中圖分類號：TP393

文獻(xiàn)標(biāo)識碼：A

DOI： 10.3969/j.issn.1003-6970.2016.01.030

0 引言

針對大型的數(shù)據(jù)來說，過去的聚類手段存在下面兩個關(guān)鍵的不足。首先就是其數(shù)據(jù)集不夠穩(wěn)定，與低維相比，高維的分布更加廣泛，這往往會出現(xiàn)數(shù)據(jù)之間等距的現(xiàn)象，通常而言，我們會按照距離來展開聚類工作，這樣意味著高維數(shù)據(jù)集的構(gòu)建難度進(jìn)一步加大；其次，就高維數(shù)據(jù)集而言，其內(nèi)在的屬性往往沒有直接的聯(lián)系，所以基本上在所有維中存在類的概率為0。

1 部分優(yōu)先聚類算法（Partial PriorityAlgorithm PPA）

就引言中的問題展開研究，進(jìn)而提出部分優(yōu)先算法，首先將第一類從原始數(shù)據(jù)中分離出來，刪除第一類數(shù)據(jù)后，再分離形成第二類，反復(fù)循環(huán)下去，我們會發(fā)現(xiàn)其計算速度非?？?，但是不滿足使用的準(zhǔn)確度要求，這種算法十分適用于準(zhǔn)確度要求不是十分嚴(yán)格的數(shù)據(jù)集的計算。針對其準(zhǔn)確度不足的情況，我們結(jié)合使用了加權(quán)的方法來確定類中心，以此來提升其穩(wěn)定性與典型程度，這對于聚類的穩(wěn)定性、延伸性以及時效性都是十分有利的。

1.1 概念定義

1.r-鄰域：其中心是某一個數(shù)據(jù)點(diǎn)，半徑用小寫字母r表示。

2.典型樣本p：其定義就是如果樣本集A內(nèi)部數(shù)據(jù)的r-鄰域里存在有最基本的Minpts（密度閥值）個數(shù)據(jù)，那么該樣本就叫做典型樣本。

3.典型點(diǎn)C：p中全部數(shù)據(jù)的平均值為典型點(diǎn)，

其中p中樣本的數(shù)量用|p|表示。

4.類中心：即樣本中全部數(shù)值的平均值。

1.2 部分優(yōu)先算法的設(shè)計案例

1.選擇某一個數(shù)據(jù)集，然后隨機(jī)抽取其中的一個樣本A，確定A典型與否。任取樣本中的某一個初始值，設(shè)置好固定的r與MinDts。然后以該點(diǎn)作為圓心，若Minpts的數(shù)值比r-鄰域內(nèi)的數(shù)據(jù)量小，那么就可以確定樣本A具有代表性；

2.如果A具有很好的代表性，即確定其典型性，那么我們可以利用公式（1）求解出C₁，其中C₁是樣本的典型點(diǎn)，也就是樣本的中心；

3.如果A不具有代表性，即不具典型性質(zhì)，那么可以重新進(jìn)行第一個環(huán)節(jié)，一直到發(fā)現(xiàn)典型樣本為止；

4.樣本的中心聚類用C₁表示，利用公式

求解出C1與樣本A中各對象的間距；

5.假如C₁與指定對象x_i兩者的間距沒有大于或等于，，那么我們將此對象合并進(jìn)A內(nèi)，反之，獲取C₁和其他對象X_i+l兩兩之間的間距，完成A內(nèi)包含的全部對象。

該算法的流程圖見圖1：

1.3 PPA的優(yōu)勢

1.旨在有效加強(qiáng)典型范例和相應(yīng)的典型點(diǎn)的計算速度，此算法放棄選取數(shù)據(jù)集全部內(nèi)容而是借助于隨機(jī)挑選的方式從而獲得典型樣本，與此同時典型點(diǎn)的分析過程僅出現(xiàn)1次。

2.旨在增強(qiáng)典型點(diǎn)的代表水平，增加r-鄰域中的數(shù)據(jù)密度，此計算方法制定典型樣本數(shù)值的平均數(shù)為典型點(diǎn)，另一方面此點(diǎn)也能夠被當(dāng)作聚類中心。

3.旨在下調(diào)舊有數(shù)據(jù)集的繁瑣程度，此算法在完成1個類之后，會把此類的數(shù)值從舊有合集內(nèi)刪除以避免重復(fù)。

面對數(shù)值的排列PPA并不具備敏感性，這就會使PPA面向球形以及凸形集合時的分析速度更快。與此同時，PPA在樣本平均數(shù)值處獲得典型樣本，所以在處理異常數(shù)據(jù)情況上相對更為敏感，評估異常點(diǎn)相對更為準(zhǔn)確。PPA于聚類環(huán)節(jié)精簡了舊有的合集，大幅度下調(diào)了舊有合集的繁瑣性，因此我們不難發(fā)現(xiàn)其于功效上具備較大優(yōu)勢。PPA的分析能力、輸入數(shù)據(jù)的敏感程度、面向異常數(shù)據(jù)的敏感程度、察覺聚類形狀等方面和K-means clustering algorithm、DBSCANclustering algorithm. COBWEB clustering algorithm_FCM clustering algorithm、單連接聚類算法、CLIQUEclustering algorithm. CUBE clustering algorithm等模型開展比對，得出的相關(guān)結(jié)論詳情見表1。

2 面向大型數(shù)據(jù)集的PPA的聚類融合

2.1 聚類融合基本思想

聚類融合（clustering ensemble，CE）旨在于消除單詞聚類（word clustering）的較大波動性，把合集映射為數(shù)據(jù)點(diǎn)的相似度隨之求出融合的劃分，面向合集的歸類途徑為借助于1種算法中的多項參數(shù)或是多項算法，聚類成員的產(chǎn)生詳情見圖2。

CE的核心理念：假定存在n項數(shù)據(jù)點(diǎn)x={X₁，x₂，…，x_n}，面向x開展H次聚類求出H項聚類，π={π₁，π₂，…，π_n}，在此之中π_k（k=l，2，…，H）是第k次求解數(shù)據(jù)。假定存在共識函數(shù)r，詳情見圖3。

共識函數(shù)（consensus function，CF，也稱為一致性函數(shù)）的定義標(biāo)準(zhǔn)為只要可以將需要聚類的所有聚類成員借助于其一標(biāo)準(zhǔn)完成融合過程，以共協(xié)矩陣（Co-association matrix）為例，相應(yīng)的功能為評價數(shù)據(jù)內(nèi)部的關(guān)聯(lián)性，函數(shù)方程詳見（3）：

聚類算法總次數(shù)H

接下來我們面向前面獲得的H項結(jié)果展開融合，求出所需的聚類結(jié)果π'。聚類融合的詳情情況見圖4。

2.2 聚類融合算法的設(shè)計

我們假設(shè)一數(shù)據(jù)合集X={X₁，x₂，…，x_n}，

x_i={X_i1，x_i2，…，x_in}，借助于PPA算法把它進(jìn)行歸納，PPA算法的特征為所有劃分行為均會先出現(xiàn)第1個類，隨后采取融合的途徑得到所需的第1個類。第1次歸納總結(jié)一直到第r次歸納總結(jié)的第1個類為{C₁₁，C_{12，…，C1r}}， 相關(guān)的類中心則是{

}，旨在確保所有劃分行為出現(xiàn)的第1個類存在差異，算法設(shè)計借助于改變數(shù)據(jù)的輸入順序從而達(dá)到目的。

融合方式定義為：借助于加權(quán)的方法從而求出第1類的類中心，此類中心的權(quán)重需要借助于此類中的全部數(shù)據(jù)量和每類數(shù)據(jù)量之和的比例而獲得。

為類C..所含的數(shù)據(jù)量，V₁定義成所需的第1個類的類中心。隨著v₁的求出，再確定空集T₁，將V賦予Z作為類中心開始聚類，假設(shè)存在閥值r，利用PPA算法的第5環(huán)節(jié)，求出的T₁即是所需出現(xiàn)的第1個類。于所有劃分行為中把正包括的數(shù)值剔除，從而有效下調(diào)數(shù)據(jù)的繁瑣性。

按照上述步驟獲得剩余的k-l個類。由于V_i（i=l，2，…，k存在的典型性，所以出現(xiàn)T₁，T₂，…，T_k之后，余在舊有合集內(nèi)的數(shù)據(jù)接近于0，算法設(shè)計將余下數(shù)值平分成k份，再依次移到T₁，T₂，…，T_k中，函數(shù)（5）即是所有類中心的算法函數(shù)，各類產(chǎn)生的詳情見圖5。

2.3 聚類融合算法的優(yōu)勢

1.旨在讓類中心的代表水平以及相應(yīng)的典型程度更為突出，分析歸類更為精確，類中心借助于加權(quán)的方法從而實現(xiàn)此目的，借助于公式（5）獲得所有類中心。

2.旨在增加計算性能，采用的類中心讓原有數(shù)據(jù)集的內(nèi)容極限精簡。

3.旨在下調(diào)數(shù)據(jù)集的復(fù)雜程度，于歸類期間把已完成分類的部分從原有數(shù)據(jù)集內(nèi)剔除。

3 算法測試結(jié)果分析

采取9組從UCI Machine Learning Repo sitory合集中獲得的數(shù)據(jù)（Size<2*104），各為Fertility，CarEvaluation， Abalon. Artificial Characters. ISOLET，Callt2 Building People Counts （CBPC）. Gas SensorArray Drift Dataset （GSADD）， p53 Mutants， LetterRecognition詳細(xì)參數(shù)見表2，為驗證算法是否具有穩(wěn)定性，同時測試其可行性，面向表2囊括的9組合集分別開展5次PPA以及基于PPA的聚類融合算法，求解獲得平均時間值、精度值和方差值。

按照表3以及圖6中的內(nèi)容，我們不難發(fā)現(xiàn)PPA算法和基于PPA的聚類融合（EPPA）算法相比較，PPA的運(yùn)算效率更高一些，然而于精度層面開展比較，則是EPPA更勝一籌。按照獲得的實驗結(jié)果中的方差開展對比，我們發(fā)現(xiàn)PPA的魯棒性更勝一籌。按照表4以及圖7中的內(nèi)容，我們能夠得出結(jié)論：EPPA于處理大型數(shù)據(jù)過程中的抗外界干擾能力和其可靠性均具有顯著強(qiáng)勢。

根據(jù)獲得的實驗結(jié)果我們發(fā)現(xiàn)PPA以及EPPA容易受處理的數(shù)據(jù)量的多少以及維數(shù)大小的作用，于17，000數(shù)據(jù)處出現(xiàn)轉(zhuǎn)折情況，與此之前要更平穩(wěn)，之后就出現(xiàn)時間增加過快的現(xiàn)象。于精度層次上考慮，數(shù)據(jù)集超過6，000的情況下EPPA開始穩(wěn)定，能夠得出結(jié)論：EPPA的穩(wěn)定性和可靠程度較高，面向未知數(shù)據(jù)集的計算上存在著巨大的潛力。

4 結(jié)論

本研究將常見的聚類算法開展一定程度上的優(yōu)化，得到部分優(yōu)先聚類算法，增強(qiáng)了算法的處理能力，提高其效率，然而于精度層次上考量，其可靠性仍然有待于后續(xù)優(yōu)化，本研究于部分優(yōu)先聚類算法的基礎(chǔ)上開展了聚類融合，避免了此算法缺乏精度的缺點(diǎn)，增強(qiáng)其算法精度，使其于可擴(kuò)展程度、魯棒性、可靠程度等方面均有著傳統(tǒng)聚類算法無法匹敵的優(yōu)勢，對于大型數(shù)據(jù)集的計算具有舉足輕重的作用。