密度偏差抽樣在近鄰傳播聚類中的應(yīng)用

潘春燕，張仁崇，楊忠保

(1.黔南民族師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，貴州 都勻 558000，2.貴州商學(xué)院 計(jì)算機(jī)與信息工程學(xué)院，貴州 貴陽(yáng) 550014)

聚類分析是數(shù)據(jù)挖掘中的一項(xiàng)技術(shù)，通過聚類分析不僅可獲得數(shù)據(jù)內(nèi)部結(jié)構(gòu)還可作為其他數(shù)據(jù)挖掘方法的預(yù)處理步驟以及對(duì)數(shù)據(jù)噪聲點(diǎn)、孤立點(diǎn)的檢測(cè)，在數(shù)據(jù)挖掘中占有較高地位.因此尋求一種適用性較強(qiáng)、能高效解決任意分布數(shù)據(jù)和應(yīng)用場(chǎng)景的聚類方法尤為重要.近年來，根據(jù)數(shù)據(jù)規(guī)模、數(shù)據(jù)分布特征以及應(yīng)用場(chǎng)景，研究聚類的方向主要有：一是提出新的聚類算法，二是根據(jù)實(shí)際需要優(yōu)化傳統(tǒng)聚類算法.

AP聚類算法被學(xué)者Frey和Dueck在2007年提出[1]，該聚類算法無需人為設(shè)定類別和指定初始類中心、穩(wěn)定性好能高效處理數(shù)據(jù)分類問題，但算法仍存在不足[2]，如偏向參數(shù)會(huì)直接影響最終聚類數(shù)，選擇不當(dāng)會(huì)導(dǎo)致聚類結(jié)果不優(yōu)；時(shí)間復(fù)雜度高，無法滿足大規(guī)模數(shù)據(jù)的應(yīng)用需求.針對(duì)AP聚類算法選擇偏向參數(shù)問題，2014年，Chen等人通過提出的穩(wěn)定性來設(shè)置偏向參數(shù)[3]，2017年，唐丹基于其它所有點(diǎn)到某點(diǎn)的隸屬度之和越大則假設(shè)該點(diǎn)成為類代表可能性越大來選擇偏向參數(shù)[4]；針對(duì)AP聚類算法計(jì)算時(shí)間復(fù)雜度高問題已有學(xué)者引入抽樣技術(shù)，通過減少數(shù)據(jù)輸入來提高聚類效率[5,6]，但算法處理大規(guī)模數(shù)據(jù)其效率有待提高[7].2014年劉曉楠等人提出分層近鄰傳播聚類算法來解決大規(guī)模數(shù)據(jù)的應(yīng)用需求，該算法聚類效果較好也極大降低聚類時(shí)間[8]；2017年，孫勁光等人采用隨機(jī)采樣思想并通過引入Nystr?m逼近策略求解相似度矩陣，降低算法的時(shí)間復(fù)雜度[9].2019年，劉槿通過簡(jiǎn)單隨機(jī)抽樣、密度偏差抽樣對(duì)數(shù)據(jù)進(jìn)行約簡(jiǎn)，降低AP聚類的時(shí)間復(fù)雜度，對(duì)分布偏斜的數(shù)據(jù)引用密度偏差抽樣，樣本聚類得到較好的結(jié)果[10]，但數(shù)據(jù)規(guī)模較小，針對(duì)分布偏斜的大規(guī)模數(shù)據(jù)，AP聚類算法如何在保證原始數(shù)據(jù)信息的分布特征、類不丟失條件下對(duì)數(shù)據(jù)進(jìn)行約簡(jiǎn)、合理減少數(shù)據(jù)輸入來提高算法的效率極為重要.

針對(duì)分布偏斜的大規(guī)模數(shù)據(jù)，借助簡(jiǎn)單隨機(jī)抽樣和基于網(wǎng)格的密度偏差抽樣對(duì)進(jìn)行數(shù)據(jù)約簡(jiǎn)，再對(duì)樣本數(shù)據(jù)執(zhí)行AP聚類，通過減少數(shù)據(jù)輸入來降低算法時(shí)間復(fù)雜度，探討適用于分布偏斜的大規(guī)模數(shù)據(jù)進(jìn)行AP聚類時(shí)的約簡(jiǎn)技術(shù).

1 算法

1.1 AP聚類算法

AP聚類算法是引入因子圖理論、是基于數(shù)據(jù)點(diǎn)間“信息傳遞”的一種聚類算法，算法在聚類開始時(shí)把所有數(shù)據(jù)點(diǎn)都認(rèn)為是潛在的類代表點(diǎn)，實(shí)現(xiàn)步驟如下[10]：

步驟1 根據(jù)包含m維、n個(gè)數(shù)據(jù)點(diǎn)的原始數(shù)據(jù)集N={xi1,xi2,…,xim},i=1,2,…,n，首先計(jì)算相似度矩陣Sn×n，式(1)為第i個(gè)、第k個(gè)數(shù)據(jù)點(diǎn)的相似性，其中S的均值為對(duì)角線元素偏向參數(shù)初始值，此時(shí)支持度矩陣R和歸屬度矩陣A都為0.

S(i,k)=-‖xi-xk‖2

(1)

步驟2 計(jì)算支持度R和歸屬度A，計(jì)算公式為式(2)、(3).

(2)

(3)

步驟3 更新支持度R和歸屬度A的消息.

步驟4 判斷是否繼續(xù)迭代：若聚類結(jié)果保持不變或是迭代次數(shù)達(dá)到最大值則迭代結(jié)束，進(jìn)行下一步，否則轉(zhuǎn)步驟2.

步驟5 根據(jù)式(4)計(jì)算決策矩陣E.其中對(duì)角線元素若E(k,k)>0，則k為最終類代表點(diǎn)，剩余點(diǎn)分配時(shí)，觀察每一行的最大值，若第k行的最大值為E(k,j)，則表示點(diǎn)j為點(diǎn)k的類代表點(diǎn).

(4)

1.2 基于網(wǎng)格的密度偏差抽樣AP聚類算法

根據(jù)不同網(wǎng)格劃分方法獲得的網(wǎng)格空間不同，實(shí)現(xiàn)相異的基于網(wǎng)格劃分的密度偏差抽樣算法.首先對(duì)原始數(shù)據(jù)集進(jìn)行抽樣約簡(jiǎn)數(shù)據(jù)，再對(duì)樣本數(shù)據(jù)集執(zhí)行AP聚類，從而實(shí)現(xiàn)基于網(wǎng)格的密度偏差抽樣AP聚類算法，算法實(shí)現(xiàn)步驟如下：

輸入：原始數(shù)據(jù)集N，樣本量n.

輸出：樣本數(shù)據(jù)集Sn聚類結(jié)果.

步驟1 對(duì)原始數(shù)據(jù)集完整掃描一次，輸入不同網(wǎng)格劃分方法所構(gòu)成的網(wǎng)格空間.

步驟2 統(tǒng)計(jì)網(wǎng)格空間包含的網(wǎng)格總個(gè)數(shù)g、各個(gè)網(wǎng)格總數(shù)據(jù)點(diǎn)個(gè)數(shù)ni,i=1,2,…,g.

步驟4 針對(duì)第i個(gè)網(wǎng)格，若ni=0，則令i=i+1.

步驟5 對(duì)網(wǎng)格空間的每個(gè)網(wǎng)格單元執(zhí)行第2步到第3步.

步驟6 整合樣本點(diǎn)構(gòu)成樣本數(shù)據(jù)集，對(duì)樣本數(shù)據(jù)集上執(zhí)行AP聚類，其中算法使用歐氏距離計(jì)算相似度矩陣，偏向參數(shù)值為原始AP算法的默認(rèn)值.

步驟7 輸出樣本數(shù)據(jù)集Sn聚類結(jié)果.

從實(shí)現(xiàn)步驟可知，步驟3在同一個(gè)網(wǎng)格里各個(gè)數(shù)據(jù)點(diǎn)被抽取的概率一樣，抽樣概率函數(shù)f(ni)是遞減函數(shù)，網(wǎng)格包含的數(shù)據(jù)量ni越大f(ni)越小，反之f(ni)越大，在各個(gè)網(wǎng)格實(shí)現(xiàn)密度偏差抽樣從而獲得樣本數(shù)據(jù)集，其中e值常設(shè)為0.5.

2 評(píng)價(jià)標(biāo)準(zhǔn)與數(shù)值實(shí)驗(yàn)

2.1 評(píng)價(jià)標(biāo)準(zhǔn)

(1)聚類精度(AC)：本文用外部評(píng)價(jià)方式精度[15]來評(píng)估聚類結(jié)果，計(jì)算公式為式(5)，其中TC是聚類結(jié)果中類別正確的樣例總數(shù)，F(xiàn)C是聚類結(jié)果誤判的樣例總數(shù)，AC∈[0,1]，若AC越大，聚類精度越高.

(5)

(2)聚類個(gè)數(shù)(NC)：此度量數(shù)據(jù)集進(jìn)行AP聚類時(shí)自動(dòng)聚類的類數(shù)，若NC與原始數(shù)據(jù)的類越接近聚類效果越好.

(3)迭代次數(shù)(NI)：此度量各樣本數(shù)據(jù)集在進(jìn)行AP聚類時(shí)的迭代次數(shù)，若NI越小，聚類算法的效率越高.

(4)聚類耗時(shí)(AR)：此度量數(shù)據(jù)聚類的運(yùn)行效率，若AR越小，算法的效率越高.

2.2 數(shù)值實(shí)驗(yàn)

數(shù)值實(shí)驗(yàn)在同一臺(tái)版本為Windows10_64位、CPU/2.6 GHz、RAM/8.0 GB的計(jì)算機(jī)，實(shí)驗(yàn)工具為VC++和RStudio的平臺(tái)上展開，其中抽樣算法在C++上進(jìn)行，AP聚類直接調(diào)用R的apcluster函數(shù)包.測(cè)試事例包括來自文獻(xiàn)[13]的人工數(shù)據(jù)集類型Data和UCI標(biāo)準(zhǔn)數(shù)據(jù)集，數(shù)據(jù)Data、Page-blocks分布偏斜較大，Waveform3分布較均勻，測(cè)試事例詳細(xì)信息如表1所示.分別比較分析SRS算法[11]、G_DBS算法[12]、VG_DBS算法[13]以及AVVG_DBS算法[14]按相同抽樣比例所獲得的樣本數(shù)據(jù)執(zhí)行AP聚類的結(jié)果.

表1 測(cè)試數(shù)據(jù)集的數(shù)據(jù)信息

2.2.1 抽樣效果分析

抽樣效果分析測(cè)試事例是Data，該數(shù)據(jù)總有100萬個(gè)數(shù)據(jù)點(diǎn)，數(shù)據(jù)分布不均勻，最大的類含有78萬個(gè)數(shù)據(jù)點(diǎn)，最小的類僅含有1000個(gè)數(shù)據(jù)點(diǎn)，分別對(duì)Data按0.1%、0.01%抽樣比例抽取1000、100個(gè)樣本點(diǎn)，各抽樣算法所獲得的樣本數(shù)據(jù)集詳細(xì)信息如表2所示、分布特征見圖1.

表2 原始數(shù)據(jù)集及各抽樣算法樣本數(shù)據(jù)集詳細(xì)信息

根據(jù)表2獲知，按0.1%抽取1000個(gè)數(shù)據(jù)點(diǎn)，SRS算法丟失第5類，按0.01%抽取100個(gè)數(shù)據(jù)點(diǎn)，SRS算法丟失第4、5類，在數(shù)據(jù)量為1000個(gè)數(shù)據(jù)點(diǎn)的第5類G_DBS算法分別取得6、1個(gè)數(shù)據(jù)點(diǎn)，VG_DBS算法分別取得21、3個(gè)數(shù)據(jù)點(diǎn)，AVVG_DBS算法分別取得25、4個(gè)數(shù)據(jù)點(diǎn).由此可知，當(dāng)抽樣比例低樣本量少時(shí)，SRS算法易造成類的丟失，其他三種算法均無類丟失，AVVG_DBS算法在數(shù)據(jù)量最小的類所獲得的樣本量較多，不易丟失類，結(jié)合圖1知AVVG_DBS算法的樣本數(shù)據(jù)較好的保留原始數(shù)據(jù)集分布特征.

圖1 各抽樣算法不同比例樣本分布

2.2.2 樣本集AP聚類效果分析

首先對(duì)UCI標(biāo)準(zhǔn)數(shù)據(jù)集Page-blocks、Waveform3進(jìn)行AP聚類，其聚類結(jié)果統(tǒng)計(jì)的類數(shù)、迭代次數(shù)和聚類執(zhí)行時(shí)間見表3.

表3 AP聚類算法在UCI標(biāo)準(zhǔn)數(shù)據(jù)集上聚類結(jié)果

由表3獲知，對(duì)數(shù)據(jù)量為5473、10維的數(shù)據(jù)Page-blocks，AP聚類自動(dòng)聚類個(gè)數(shù)為188個(gè)，與原始數(shù)據(jù)類個(gè)數(shù)5相差較大，迭代443次，耗時(shí)2069.98 s；對(duì)數(shù)據(jù)量為5000、21維的數(shù)據(jù)Waveform3，自動(dòng)聚類個(gè)數(shù)為139個(gè)，與原始數(shù)據(jù)類個(gè)數(shù)3相差較大，迭代260次，耗時(shí)546.87 s.由此可知對(duì)原始數(shù)據(jù)直接執(zhí)行AP聚類迭代次數(shù)較多、耗時(shí)較高且自動(dòng)聚類個(gè)數(shù)與原始數(shù)據(jù)的類個(gè)數(shù)相差較大，下面對(duì)各抽樣算法的樣本數(shù)據(jù)進(jìn)行AP聚類.

由于SRS算法丟失類不用于聚類效果分析，對(duì)G_DBS算法、VG_DBS算法、AVVG_DBS算法所獲得的樣本執(zhí)行AP聚類分別記為G_DB_AP算法、VG_DBS_AP算法、AVVG_DBS_AP算法，實(shí)驗(yàn)數(shù)據(jù)為表1的測(cè)試實(shí)例.圖2的(b3)-(d3)、(b4)-(d4)分別為人工數(shù)據(jù)Data按抽樣比例為0.1%、0.01%抽樣所獲得的樣本數(shù)據(jù)運(yùn)行cutree(aggres,k)聚類的結(jié)果，其中k為樣本數(shù)據(jù)集信息包含的原始數(shù)據(jù)類的個(gè)數(shù).

圖2 各抽樣算法樣本數(shù)據(jù)集AP聚類效果

由圖2獲知，各樣本數(shù)據(jù)在給出正確類個(gè)數(shù)下聚類效果較好，按抽樣比例0.1%抽取1000個(gè)樣本點(diǎn)各聚類算法都有誤判情況，按0.01%抽取100個(gè)樣本點(diǎn)各算法聚類效果更好，其中各算法中AVVG_DBS_AP算法聚類效果最好.表4為各算法在樣本數(shù)據(jù)上聚類評(píng)價(jià)指標(biāo)的統(tǒng)計(jì)結(jié)果.

表4 聚類算法評(píng)價(jià)指標(biāo)統(tǒng)計(jì)結(jié)果

由表4知，人工數(shù)據(jù)集Data按抽樣比例為0.1%、0.01%獲得的樣本數(shù)據(jù)，各算法聚類精度都在91%以上，按0.1%抽樣VG_DBS_AP算法精度最高，為94.6%，按0.01%抽樣，AVVG_DBS_AP算法精度最高，為100%.各算法自動(dòng)聚類個(gè)數(shù)都較小，三種算法按0.1%抽樣樣本聚類NC分別為28、17、19個(gè)，按0.01%抽樣樣本聚類NC分別為14、8、7個(gè)，與原始數(shù)據(jù)類個(gè)數(shù)5接近，由此可知隨著樣本量減少，聚類個(gè)數(shù)與原始數(shù)據(jù)聚類個(gè)數(shù)越接近.AVVG_DBS_AP算法消耗時(shí)間最低，聚類耗時(shí)分別為8.16 s，0.02 s.UCI標(biāo)準(zhǔn)數(shù)據(jù)Page-blocks、Waveform3按5%進(jìn)行抽樣，數(shù)據(jù)Page-blocks三種算法精度相當(dāng)，均在83%以上；對(duì)分布較均勻的Waveform3，三種算法精度較低，最高是AVVG_DBS_AP算法，為64%.三種算法自動(dòng)聚類的類數(shù)與原始數(shù)據(jù)類數(shù)較相近；與表3相比，各算法對(duì)Page-blocks的樣本聚類迭代次數(shù)有所降低，Waveform3卻有所升高.Page-blocks、Waveform3樣本聚類耗時(shí)分別為0.48 s、0.31 s，根據(jù)表3原始數(shù)據(jù)聚類耗時(shí)分別為2069.98 s、546.87 s，約是樣本聚類耗時(shí)的4312倍、1764倍.

綜上可知，對(duì)偏斜較大的數(shù)據(jù)集先借助基于網(wǎng)格的密度偏差抽樣算法進(jìn)行數(shù)據(jù)約簡(jiǎn)，再對(duì)樣本數(shù)據(jù)集執(zhí)行AP聚類，各算法在損失小部分精度的基礎(chǔ)上，樣本自動(dòng)聚類個(gè)數(shù)與原始數(shù)據(jù)類數(shù)較接近，耗時(shí)較低，可提高聚類的效率，其中AVVG_DBS_AP算法在保證聚類精度較高的基礎(chǔ)上耗時(shí)最小、效率最高.

3 結(jié) 語(yǔ)

針對(duì)偏斜的大規(guī)模數(shù)據(jù)，探討基于網(wǎng)格劃分的密度偏差抽樣算法在AP聚類中的應(yīng)用，根據(jù)3種抽樣算法在偏斜較大的人工數(shù)據(jù)集和UCI數(shù)據(jù)集上所獲得的樣本數(shù)據(jù)執(zhí)行AP聚類的效果可知，樣本數(shù)據(jù)集進(jìn)行AP聚類在損失小部分精度基礎(chǔ)上，大大提高聚類效率，其中AVVG_DBS_AP算法聚類的純度較高、自動(dòng)聚類個(gè)數(shù)與原始數(shù)據(jù)類個(gè)數(shù)較接近、迭代次數(shù)較低以及聚類執(zhí)行時(shí)間耗時(shí)少.面對(duì)分布偏斜的大規(guī)模數(shù)據(jù)，在進(jìn)行AP聚類之前可先借助AVVG_DBS算法進(jìn)行數(shù)據(jù)約簡(jiǎn)，再執(zhí)行聚類，以此通過減少數(shù)據(jù)輸入降低算法的時(shí)間復(fù)雜度，提高算法效率.