于本成，鮑 宇，曹天杰，朱作付

（1.中國礦業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 徐州221000；2.徐州工業(yè)職業(yè)技術(shù)學(xué)院 信息管理技術(shù)學(xué)院，江蘇 徐州221000）

0 引 言

隨著信息科技的發(fā)展，大規(guī)模、大容量的數(shù)據(jù)集開始出現(xiàn)并被廣泛使用，其中包含了超多的文本、圖像、視頻和音頻數(shù)據(jù)，而且需要從這些海量的數(shù)據(jù)中分析出需要的、有價(jià)值的數(shù)據(jù)，這就是數(shù)據(jù)挖掘技術(shù)的目標(biāo)。聚類算法作為數(shù)據(jù)挖掘技術(shù)的具體實(shí)現(xiàn)方法之一，已經(jīng)成為現(xiàn)今研究的熱點(diǎn)方向。在大型數(shù)據(jù)集中使用傳統(tǒng)聚類方式進(jìn)行聚類主要面臨兩方面問題：第一，數(shù)據(jù)集高維比低維分布更稀疏，數(shù)據(jù)之間的距離幾乎相等，一般的聚類方法都是基于距離進(jìn)行聚類的，那么高維數(shù)據(jù)集則無法構(gòu)建類［1］；第二，高維數(shù)據(jù)集中存的各類數(shù)據(jù)的屬性基本無關(guān)，那么在所有維中存在類的概率基本為0［2］。然而對(duì)于任何的聚類算法都不可能適用于所有的數(shù)據(jù)集，因?yàn)橛械囊筮\(yùn)算效率高而對(duì)運(yùn)算精度要求不高，有的是運(yùn)算精度必須要高。針對(duì)上述問題本文提出部分優(yōu)先算法，首先從原始集中分出第1類，在數(shù)據(jù)集中刪除規(guī)劃到第1類的數(shù)據(jù)，然后分出第2類，循環(huán)此操作，該算法效率高而運(yùn)算精確度不理想，對(duì)于精度要求不高的數(shù)據(jù)集來說在運(yùn)算效率上有較強(qiáng)的優(yōu)勢(shì)。

1 部分優(yōu)先聚類算法 （partial priority algorithm，PPA）

1.1 概念定義

r－鄰域：以某一數(shù)據(jù)點(diǎn)為圓心，以r為半徑的區(qū)域。

典型樣本p：若樣本A里某數(shù)據(jù)的r－鄰域內(nèi)至少有Minpts（密度閥值）［2］個(gè)數(shù)據(jù)，則稱為典型樣本。

典型點(diǎn)C［3］：p中所有數(shù)據(jù)的均值為典型點(diǎn)

類中心［3］：類中所有數(shù)據(jù)的均值則為類中心。

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

在傳統(tǒng)聚類算法的基礎(chǔ)上，按照以下算法步驟設(shè)計(jì)部分優(yōu)先聚類算法：

（1）在某一數(shù)據(jù)集中任意選取樣本A，判斷A的典型性。隨機(jī)在A中取一點(diǎn)為初始點(diǎn)，并設(shè)定Minpts和r。設(shè)該點(diǎn)為中心，r－鄰域內(nèi)的數(shù)據(jù)數(shù)量大于Minpts，則A為典型樣本；

（2）若A為典型樣本，通過式 （1）求出樣本中心既A的典型點(diǎn)C1；

（3）若A不為典型樣本，則重復(fù)步驟 （1），至找到典型樣本；

（4）找到典型樣本后，以C1為中心進(jìn)行聚類，通過

求出C1和A中每個(gè)對(duì)象間的距離；

（5）如果C1和某對(duì)象xi的間離小于r，則把該對(duì)象納入A中，否則，計(jì)算C1與下個(gè)對(duì)象xi＋1的間距，直至遍歷A中的所有對(duì)象。

該算法的流程如圖1所示。

圖1 部分優(yōu)先聚類算法流程

1.3 PPA的優(yōu)勢(shì)

相比較于經(jīng)典的聚類算法 （如K－mean聚類算法），此類算法包括一個(gè)具有n個(gè)數(shù)據(jù)的數(shù)據(jù)集，且因此產(chǎn)生的聚類數(shù)量為k，該算法的n個(gè)數(shù)據(jù)包含k個(gè)子集，表示一個(gè)聚類，相同聚類里的數(shù)據(jù)間距離很短，但是不同聚類里的數(shù)據(jù)間距離很大。用中心數(shù)值來代表每一個(gè)數(shù)據(jù)集，該中心值可由聚類里所有數(shù)據(jù)的平均數(shù)計(jì)算得到。

PPA為提高典型樣本及典型點(diǎn)的選取效率，相對(duì)于傳統(tǒng)聚類算法采用不選取完整數(shù)據(jù)集而通過隨機(jī)樣本的選取來尋找典型樣本，且典型點(diǎn)的計(jì)算只有一次；同時(shí)PPA為提高典型點(diǎn)的典型性，提高r－鄰域內(nèi)數(shù)據(jù)密度，算法設(shè)計(jì)典型樣本中的數(shù)據(jù)均值為典型點(diǎn)，該點(diǎn)亦可作為聚類的中心；以及PPA為降低原數(shù)據(jù)集的復(fù)雜度，算法設(shè)計(jì)在得到一個(gè)類后，同時(shí)將該類的數(shù)據(jù)從原數(shù)據(jù)集中剔除。

對(duì)于數(shù)據(jù)的順序PPA是不敏感的，故PPA在球星數(shù)據(jù)和凸形數(shù)據(jù)方面的計(jì)算效果較好，而且PPA從樣本均值處尋找典型樣本，所以在處理異常數(shù)據(jù)方面就比較敏感，判斷異常點(diǎn)精確。PPA在聚類過程中縮小了原始數(shù)據(jù)集，降低了原始數(shù)據(jù)集的復(fù)雜度，從而在效率方面更有非常明顯的優(yōu)勢(shì)。PPA在算法效率方面、輸入數(shù)據(jù)的敏感性方面、對(duì)異常數(shù)據(jù)的敏感性方面、發(fā)現(xiàn)聚類形狀方面與K－means、DBSCAN、COBWEB、FCM、單連接、CLIQUE、CUBE等算進(jìn)行比較［4，5］。結(jié)果分析見表1。

表1 算法的性能比較

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

部分優(yōu)先聚類算法 （PPA）相對(duì)于傳統(tǒng)的聚類算法在運(yùn)算效率上有了明顯優(yōu)勢(shì)，但在對(duì)于精度要求比較高的數(shù)據(jù)集計(jì)算上還有其固有的弊端。文章設(shè)計(jì)使用加權(quán)來確定類中心，提高類中心的典型性與穩(wěn)定性，再通過聚類融合提高了算法的運(yùn)算精度。最終算法在效果、可擴(kuò)展性、穩(wěn)定性、以及魯棒性等方面均有顯著提高。

2.1 聚類融合基本思想

聚類融合為克服單次聚類的不穩(wěn)定性，將群體映射為數(shù)據(jù)點(diǎn)的相似度后進(jìn)行融合而得到劃分，對(duì)數(shù)據(jù)集的分類方式是選擇使用一種算法下的不同參數(shù)或者多種算法。聚類成員的產(chǎn)生方法如圖2所示。聚類融合的基本思想：設(shè)有n個(gè)數(shù)據(jù)點(diǎn)X＝，對(duì)X進(jìn)行H次聚類得到H個(gè)聚類，π＝其中為第k次結(jié)果。設(shè)計(jì)共識(shí)函數(shù)г，如圖3所示。

圖2 聚類成員的產(chǎn)生方法

共識(shí)函數(shù)［6］的設(shè)計(jì)原則是只要能把需要聚類的各聚類成員以某種標(biāo)準(zhǔn)實(shí)現(xiàn)其融合，比如共協(xié)矩陣［7］（Co－association），其作用是衡量數(shù)據(jù)之間的相似度，計(jì)算公式為

圖3 設(shè)計(jì)共識(shí)函數(shù)

然后對(duì)H個(gè)結(jié)果進(jìn)行融合后得到最終聚類結(jié)果π′。聚類融合的過程如圖4所示。

圖4 聚類融合的過程

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

融合方法的設(shè)計(jì)［8－10］是用加權(quán)的方式來計(jì)算第一類的類中心，該類中心的權(quán)重是通過該類內(nèi)的所有數(shù)據(jù)量與每一類數(shù)據(jù)的總量之比來確定的

同樣產(chǎn)生余下的k－1個(gè)類。由于的典型性，故產(chǎn)生T1，T2，...，Tk后，剩余在原數(shù)據(jù)集中的數(shù)據(jù)幾乎為零，算法設(shè)計(jì)是把剩余數(shù)據(jù)均分為k份后按順序分

圖5 各類的產(chǎn)生過程

2.3 聚類融合的優(yōu)勢(shì)

為使類中心的代表性和典型性更強(qiáng)以及分類精度更高，類中心采用加權(quán)的方式來確定，通過式 （5）來產(chǎn)生各個(gè)類中心。在提高算法效率方面，選取的類中心使得原數(shù)據(jù)集的數(shù)據(jù)盡最大減縮。在數(shù)據(jù)集復(fù)雜度方面，在分類的同時(shí)將已分類的數(shù)據(jù)從原數(shù)據(jù)集中刪除，可以有效降低數(shù)據(jù)集的復(fù)雜度。

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

本次試驗(yàn)選用9組來自 UCI Machine Learning Repository數(shù)據(jù)集 （Size＜2＊104），分別是Fertility，Car Evaluation，Abalon，Artificial Characters，ISOLET，CalIt2Building People Counts，Gas Sensor Array Drift Dataset，p53 Mutants，Letter Recognition見表2，測(cè)試算法可行性和穩(wěn)定性，對(duì)表2所包含的9組數(shù)據(jù)集各運(yùn)行5次K－means算法和PPA以及基于PPA的聚類融合算法，計(jì)算出平均時(shí)間和精度以及方差。

根據(jù)表3數(shù)據(jù)和圖6曲線所示，在運(yùn)算效率上，PPA算法相比較于基于PPA的聚類融合，PPA更有優(yōu)勢(shì)。但是隨著數(shù)據(jù)集大小的增加，相比較于PPA算法，基于PPA的聚類融合算法在精度上的優(yōu)勢(shì)也隨之變大，而這正是大數(shù)據(jù)集處理問題中，我們迫切需要解決的。

同時(shí)如表3和圖6所示，根據(jù)實(shí)驗(yàn)數(shù)據(jù)結(jié)果中的方差比較，PPA有較好的魯棒性。根據(jù)表4數(shù)據(jù)和圖7曲線變化，可以判斷基于PPA的聚類融合算法在應(yīng)對(duì)大型數(shù)據(jù)集上抗干擾性和穩(wěn)定性方面都有明顯優(yōu)勢(shì)。由實(shí)驗(yàn)結(jié)果得出PPA算法和基于PPA的聚類融合算法受到數(shù)據(jù)量大小和維數(shù)的影響也較大，在數(shù)據(jù)為17000附近轉(zhuǎn)折，前面較平穩(wěn)，后面則時(shí)間增長(zhǎng)太快。在精度方面在數(shù)據(jù)集大于6000時(shí)基于PPA的聚類融合算法開始平穩(wěn)，可以推斷的基于PPA的聚類融合算法穩(wěn)定性高，對(duì)于未知數(shù)據(jù)集的計(jì)算有重要用途。

表2 實(shí)驗(yàn)的數(shù)據(jù)集

表3 算法運(yùn)行時(shí)間 （sec）

圖6 運(yùn)行時(shí)間比較

表4 算法精度

圖7 精度比較

4 結(jié)束語

將傳統(tǒng)聚類算法進(jìn)行了優(yōu)化，提出了部分優(yōu)先聚類算法，相對(duì)于傳統(tǒng)聚類算法 （以K－means為例），提高算法的效率，但在運(yùn)算精度方面不為穩(wěn)定。文章進(jìn)一步在部分優(yōu)先聚類算法的基礎(chǔ)上進(jìn)行了聚類融合，彌補(bǔ)了該算法運(yùn)算精度不高的劣勢(shì)，并通過實(shí)驗(yàn)比較了傳統(tǒng)聚類算法，部分優(yōu)先聚類算法和基于部分優(yōu)先聚類算法的聚類融合在運(yùn)算效率、運(yùn)算精度方面的差異，得出了部分優(yōu)先聚類算法和基于部分優(yōu)先聚類算法的聚類融合分別適用于對(duì)運(yùn)算效率要求高和對(duì)運(yùn)算精度要求高的大型數(shù)據(jù)集上，并且在可擴(kuò)展性、魯棒性、穩(wěn)定性等方面都有著傳統(tǒng)聚類算法不可并論的優(yōu)點(diǎn)，對(duì)于大型數(shù)據(jù)集的計(jì)算有著極其重要的作用。

［1］Chaitali Chaitali.Optimizing clustering technique based on partitioning DBSCAN and ant clustering algorithm ［J］.International Journal of Engineering and Advanced Technology，2012，2 （2）：212－215.

［2］Guyon，Lemaire P，Pinson E.Cut generation for an integrated employee timetabling and production scheduling problem ［J］.European Journal of Operational Research，2010，201 （2）：557－567.

［3］Shi TN，Wang JS，Wang PL，et al.Application of grid－based K－means clustering algorithm for optimal image processing ［J］.Computer Science and Information Systems，2012，9 （4）：1679－1696.

［4］Andreas Bley， Natashia Boland， Christopher Fricke.A strengthened formulation and cutting planes for the open pit mine production scheduling problem ［J］.Computers＆Operations Research，2010，37 （9）：1641－1647.

［5］Parvin H，Beigi A，Mozayani N.A clustering ensemble learning method based on the ant colony clustering algorithm ［J］.Appl Comput Math，2012，11 （2）：286－302.

［6］LIU Mingshu，F(xiàn)ANG Hongbin，ZHANG Jian，et al.On effectiveness of attribute similarity in clustering algorithm ［J］.Computer Applications and Software，2012，29 （9）：146－147（in Chinese）.［劉明術(shù)，方宏彬，張建，等.屬性相似度在聚類算法中的有效性研究 ［J］.計(jì)算機(jī)應(yīng)用與軟件，2012，29（9）：146－147.］

［7］Partha Sarathi Bishnu，Vandana Bhattacherjee.Software fault prediction using quad tree－based K－means clustering algorithm［J］.IEEE Transactions on Knowledge and Data Engineering，2012，24 （6）：1146－1150.

［8］ZHANG Hongwei，WANG Zhoujing.C－means clustering algorithm based on interval－valued intuitionistic fuzzy sets ［J］.Computer Applications and Software，2011，28 （2）：122－124（in Chinese）.［張宏威，王周敬.基于區(qū)間直覺模糊集的C均值聚 類 算 法 ［J］.計(jì) 算 機(jī) 應(yīng) 用 與 軟 件，2011，28 （2）：122－124.］

［9］Chattopadhyay S，Pratihar DK，De Sarkar SC.A comparative study of fuzzy c－means algorithm and entropy－based fuzzy clustering algorithms ［J］.Computing and Informatics，2011，30（4）：701－720.

［10］Shenbaga Ezhil S，Dr C Vijayalakshmi.An implementation of integer programming techniques in clustering algorithm ［J］.Indian Journal of Computer Science and Engineering，2012，3（1）：173－179.