，

(山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，山東 青島 266590)

聚類分析是一種無監(jiān)督的學(xué)習(xí)[1]。聚類是根據(jù)數(shù)據(jù)對象集合中各數(shù)據(jù)對象的特征，將具有相似特征的數(shù)據(jù)對象劃分為一個類別，使得同類型相似性盡量高，不同類型相似性盡量低[2]。

K-means[3]算法具有理論可靠和計(jì)算快速的優(yōu)點(diǎn)，在實(shí)踐中被廣泛應(yīng)用[4-6]。隨著研究的深入，算法的一些缺點(diǎn)逐漸暴露出來。存在的主要問題有：①在數(shù)據(jù)對象分類中，將平方誤差和作為聚類質(zhì)量好壞的評價指標(biāo)，運(yùn)算量大，效率低；②算法在運(yùn)行時需要事先確定初始中心的個數(shù)k；③對初始中心的選擇敏感，由于算法隨機(jī)的選擇k個初始中心，造成聚類的結(jié)果不穩(wěn)定。

許多學(xué)者從算法初始k個聚類中心的選擇、數(shù)據(jù)對象相似度的計(jì)算、聚類質(zhì)量評價函數(shù)這三方面對算法進(jìn)行改進(jìn)，使算法聚類效果得到了一定改善。鄭丹等[5]基于密度選取初始聚類中心，選取各主要密度水平曲線上的第一個點(diǎn)作為k個初始聚類中心；馮波等[6]利用對象的距離矩陣來生成最小生成樹，然后將樹修剪成k個分支，將k個分支中所包含點(diǎn)的均值作為初始中心進(jìn)行聚類；石文峰等[7]提出了一種用個體輪廓系數(shù)作為聚類有效性評估參數(shù)的改進(jìn)算法；周煒奔等[8]提出基于數(shù)據(jù)密度分布特征，利用均衡函數(shù)自動生成最優(yōu)簇?cái)?shù)k值的算法；王宏杰等[9]結(jié)合初始中心優(yōu)化和特征加權(quán)，改進(jìn)K-Means聚類算法；陳小雪等[10]提出了一種基于螢火蟲優(yōu)化的加權(quán)K-means算法；王賽芳等[11]提出了基于點(diǎn)密度的初始聚類中心選擇方法；李敏等[12]提出密度峰值優(yōu)化初始中心的K-means算法；莊瑞格等[13]提出基于擬蒙特卡洛的K-means聚類算法；熊開玲等[14]提出基于核密度估計(jì)的K-means聚類優(yōu)化算法；張雪鳳等[15]通過調(diào)整K-means算法運(yùn)行中數(shù)據(jù)對象被重新分配時的分配策略，在再分類過程中，將數(shù)據(jù)對象分配到最小加權(quán)距離中心點(diǎn)所在的簇中，以提高聚類質(zhì)量；趙將等[16]提出了一種改進(jìn)K-means聚類的推薦方法IKC(Improved K-means Clustering Recommendation Method)。以上研究仍存在聚類k值需指定、聚類質(zhì)量評價函數(shù)不合理等問題，導(dǎo)致聚類結(jié)果不穩(wěn)定，準(zhǔn)確率低。

針對以上問題，本文提出PCA-KDKM算法：基于PCA進(jìn)行數(shù)據(jù)集的降維，提取出主屬性以加速聚類。借助k′dist[17]曲線圖來確定聚類簇?cái)?shù)k值，取第i(i≤k)段平緩曲線上所包含點(diǎn)的均值作為第一初始聚類中心。用基于密度和最小距離的算法思想，在剩下的數(shù)據(jù)對象中選取k-1個初始聚類中心。再利用傳統(tǒng)的K-means算法，把集合中剩下的數(shù)據(jù)對象分到最近的聚類中心所在的簇，計(jì)算聚類質(zhì)量評價函數(shù)的值來評價本次的聚類效果。重復(fù)k次，取聚類評價函數(shù)值最大的一組作為最后聚類結(jié)果。實(shí)驗(yàn)證明：PCA-KDKM算法在UCI數(shù)據(jù)集上得到的聚類結(jié)果比傳統(tǒng)K-means算法聚類結(jié)果準(zhǔn)確度高，聚類結(jié)果更穩(wěn)定。

參數(shù)k在k′dist圖和K-means算法中沒有直接聯(lián)系，為避免混淆，本節(jié)以下K-means算法中的k仍然沿用k，而將k′dist圖中k改為k′。

圖1 k′dist曲線Fig.1 k′dist graph

1 k′dist圖

點(diǎn)p到離它最近的第k′(研究表明，k′>4的k′dist曲線變化非常小，幾乎與k′=4的k′dist曲線完全相同)個點(diǎn)的距離為該點(diǎn)p的k′dist值[18]。在同一簇中更改k′值不會導(dǎo)致k′dist值的顯著變化,該點(diǎn)的k′dist半徑至少包含k′+1個點(diǎn)。k′dist值按升序排列，然后用曲線連接起所有的點(diǎn)，即可繪出k′dist曲線圖。

圖1中兩條不同的曲線A和B分別對應(yīng)兩個不同的數(shù)據(jù)對象集合的k′dist曲線圖。其中曲線A開始部分比較平緩，說明A數(shù)據(jù)集大部分?jǐn)?shù)據(jù)相似性很高。曲線最后部分的k′dist值快速增加，表明A數(shù)據(jù)集只有少量點(diǎn)的k′dist值之間有很大的差異，這部分通常是邊界點(diǎn)或噪聲點(diǎn)。曲線B包含三部分平緩處a、c、e，說明這三部分?jǐn)?shù)據(jù)分別處于三個主要密度水平上。曲線B上b、d處的k′dist值增加迅速，表明這兩部分點(diǎn)是邊界點(diǎn)。其中b部分的數(shù)據(jù)連接a和c兩個主要的水平密度，而d部分?jǐn)?shù)據(jù)點(diǎn)連接c和e這兩個主要密度，f處k′dist迅速增加表明這部分點(diǎn)是噪聲點(diǎn)(一般情況下，處于低密度區(qū)域的數(shù)據(jù)對象被稱為噪聲點(diǎn)[19])。

2 PCA-KDKM算法

2.1 PCA-KDKM算法相關(guān)定義

假設(shè)數(shù)據(jù)對象集合U含有N個樣本數(shù)據(jù)，樣本數(shù)據(jù)有m個屬性，數(shù)據(jù)對象i表示為i=(i1,i2…im)。

定義1點(diǎn)密度。對于數(shù)據(jù)對象集合U中任一對象i，以i為球心，以某一正數(shù)r為半徑的圓球中所包括的數(shù)據(jù)對象j的數(shù)量即為數(shù)據(jù)對象i的點(diǎn)密度，記作Dens(i)，

Dens(i)=|Dist(i,j)≤r,j∈U|。

(1)

定義2兩個m維對象i,j的歐式距離公式為：

(2)

其中：i1,i2…im和j1,j2…jm分別表示數(shù)據(jù)對象i,j的各維數(shù)據(jù)；d(i,j)表示i和j的距離。

定義3高密度對象。在集合U中，如果一個對象i，在ε鄰域內(nèi)至少有ptsmin個對象，則稱該對象i為高密度對象。

定義4聚類質(zhì)量評價函數(shù)[20]

(3)

其中

(6)

N表示集合中數(shù)據(jù)對象的個數(shù)，假設(shè)樣本i被分類到C類，a(i)表示樣本i和C類中其他數(shù)據(jù)對象之間的平均距離。b(i)表示樣本i與其他非C類的各個類中所有樣本平均距離的最小值。

PCA-KDKM算法的聚類質(zhì)量評價函數(shù)S的值域介于-1和1之間。結(jié)合類內(nèi)距離與類間距離這兩個因素來評估數(shù)據(jù)對象分類的合理性。S越接近1，說明該數(shù)據(jù)對象的類內(nèi)平均距離遠(yuǎn)遠(yuǎn)小于類間的平均距離,該數(shù)據(jù)對象分類越合理；S越接近-1，說明數(shù)據(jù)對象類內(nèi)平均距離遠(yuǎn)遠(yuǎn)大于類間的平均距離，分類不合理，應(yīng)當(dāng)取消。

2.2 主成分分析算法

主成分分析算法的思想是：當(dāng)數(shù)據(jù)對象集合中的每個對象數(shù)據(jù)有多維屬性信息，且數(shù)據(jù)對象的各維屬性之間具有一定的相關(guān)性時，首先要對數(shù)據(jù)對象進(jìn)行降維,去除無關(guān)屬性。數(shù)據(jù)對象降維，具體指使用主成分分析方法對各維數(shù)據(jù)進(jìn)行分析，提取并合成數(shù)據(jù)對象中無相關(guān)性的主要屬性，實(shí)現(xiàn)降維。主要屬性能夠代表數(shù)據(jù)對象集中的原有屬性且所包含的屬性互不相關(guān)。使用主成分分析法能夠有效降低數(shù)據(jù)對象集合中的無關(guān)屬性，大幅提高聚類運(yùn)算效率及聚類準(zhǔn)確率。

標(biāo)準(zhǔn)化變換公式：

(7)

(8)

2.3 PCA-KDKM算法步驟：

輸入：包含N個對象的數(shù)據(jù)對象集合UP×m，鄰域半徑以及包含對象的最小數(shù)目ptsmin。

輸出：根據(jù)數(shù)據(jù)對象特征分成的k個類別。

算法步驟：

1)UP×m按公式(7)、公式(8)計(jì)算相關(guān)系數(shù)矩陣R;

2) 根據(jù)|R-λIm|=0計(jì)算m個特征值λi;

4) 計(jì)算Dp×n中每個數(shù)據(jù)對象的k′dist值，并按從小到大的順序排列，繪出k′dist曲線圖；

5) 分析k′dist曲線圖，觀察有幾個平緩的曲線，確定聚類數(shù)值k并求出每段平緩曲線上所包含數(shù)據(jù)對象的均值，存放在集合Q中;

6) 利用距離矩陣表示Dp×n中兩兩數(shù)據(jù)對象之間的歐式距離d(i,j);

7) 計(jì)算Dp×n中每個對象的ε鄰域內(nèi)所包含的對象個數(shù)，如果滿足最小個數(shù)ptsmin，則將這個數(shù)據(jù)對象加入到高密度數(shù)據(jù)對象集合H中；

8) 從數(shù)據(jù)對象集合Q(利用k′dist曲線所求出的每段平緩曲線所包含對象的均值)中選取Q1作為第一個聚類中心k1，將k1放入初始聚類中心集合M中；

9) 計(jì)算高密度數(shù)據(jù)對象集合H中所有對象與選取的第一個初始聚類中心k1的距離d，從高密度數(shù)據(jù)對象集合H中，找出距離初始聚類中心集合M中的所有數(shù)據(jù)對象最遠(yuǎn)的數(shù)據(jù)對象k2，將k2從高密度集合H中刪除，并將k2加入到集合M中；

10) 從高密度數(shù)據(jù)對象集合H中找出距離初始聚類中心集合M中的所有數(shù)據(jù)對象距離最遠(yuǎn)的數(shù)據(jù)對象k3，從高密度集合中刪除k3，將k3加入到集合M中；

11) 從高密度集合H中找距離集合M距離最遠(yuǎn)的對象，直到找到k個初始中心為止；

12) 從集合M中的這k個中心出發(fā)，將其他對象分到離它距離最近的簇，用K-means算法進(jìn)行聚類，計(jì)算本次的聚類質(zhì)量評價函數(shù)值Si；

13) 從集合Q中選取第二個均值Q2作為第一個聚類中心k1，重復(fù)(6)～(12)，直到選取Qk為第一個初始聚類中心結(jié)束。

14) 比較每次的聚類質(zhì)量評價函數(shù)值Si，從中選取聚類質(zhì)量評價函數(shù)值Si最大的一組作為結(jié)果。

3 實(shí)驗(yàn)結(jié)果及分析

3.1 PCA-KDKM算法與各改進(jìn)K-means算法的對比

實(shí)驗(yàn)平臺：英特爾Xeon(至強(qiáng))E5450@3.00 GHz 四核、4 G內(nèi)存、500 G硬盤，Windows 7旗艦版系統(tǒng)。

實(shí)驗(yàn)描述：實(shí)驗(yàn)采用專為機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘算法設(shè)計(jì)的公共數(shù)據(jù)庫UCI來進(jìn)行實(shí)驗(yàn)[21]。UCI中的每個數(shù)據(jù)對象都有分類編號，因此可以將PCA-KDKM算法得出的聚類結(jié)果與UCI數(shù)據(jù)庫中數(shù)據(jù)對象的分類標(biāo)志進(jìn)行一致性統(tǒng)計(jì)，來評價PCA-KDKM算法的聚類質(zhì)量。采用UCI數(shù)據(jù)庫中的Iris、Glass Identification、Wine和Hayes-Roth 4組數(shù)據(jù)。為了對比K-means算法與PCA-KDKM算法的準(zhǔn)確度，對4組數(shù)據(jù)不作任何修改。

基于先前實(shí)踐經(jīng)驗(yàn)，PCA-KDKM算法進(jìn)行實(shí)驗(yàn)時對Iris和Glass Identification這兩組數(shù)據(jù)指定領(lǐng)域ε為1，某點(diǎn)p的ε范圍內(nèi)含數(shù)據(jù)對象的最小個數(shù)ptsmin為50；對于Wine指定領(lǐng)域ε為10 000，某點(diǎn)p的ε范圍內(nèi)含數(shù)據(jù)對象的最小個數(shù)ptsmin為50；對于Hayes-Roth指定領(lǐng)域，ε為600，某點(diǎn)p的ε范圍內(nèi)含數(shù)據(jù)對象的最小個數(shù)ptsmin為40。PCA-KDKM算法得到的初始中心是穩(wěn)定的，所以對PCA-KDKM算法進(jìn)行k次實(shí)驗(yàn)即可。K-means算法進(jìn)行了50次實(shí)驗(yàn)，與PCA-KDKM算法的實(shí)驗(yàn)對比結(jié)果如表1、2所示。

表1 PCA-KDKM算法與K-means算法聚類準(zhǔn)確率比較Tab.1 Comparison of clustering accuracy between PCA-KDKM algorithm and K-means algorithm

表2 PCA-KDKM算法與K-means算法聚類質(zhì)量評價函數(shù)值S比較Tab.2 Comparison of clustering quality evaluation function value S between PCA-KDKM algorithm and K-means algorithm

從表1、表2中可以看出，對于Iris、Glass、 Hayes-Roth 3個數(shù)據(jù)集合,PCA-KDKM算法在聚類準(zhǔn)確率和聚類質(zhì)量評價函數(shù)值方面比K-means算法的聚類準(zhǔn)確率明顯提高，聚類準(zhǔn)確度為90%以上；對于Wine數(shù)據(jù)對象集合來說，PCA-KDKM算法比K-means算法的準(zhǔn)確率提高不明顯，但從聚類質(zhì)量評價函數(shù)值S來看，PCA-KDKM算法比K-means算法的聚類效果好。

在UCI數(shù)據(jù)集中選取4個數(shù)據(jù)集yeast、abalone、magic和skin進(jìn)行實(shí)驗(yàn)。將PCA-TDKM算法分別與李敏等[12]的CFSFDP-KM算法、莊瑞格等[13]的QMC-KM聚類算法和熊開玲等[14]的KNE-KM聚類優(yōu)化算法進(jìn)行聚類準(zhǔn)確率及聚類誤差平方和的比較。文獻(xiàn)[12-14] 的3個算法都是針對K-means算法的初始k個聚類中心進(jìn)行了優(yōu)化，都在一定程度上克服了K-means聚類算法隨機(jī)選擇k個初始聚類中心所造成聚類不穩(wěn)定的問題。通過實(shí)驗(yàn)得到聚類精度的比較結(jié)果、誤差平方和的比較結(jié)果分別如表3、表4。其中HIG表示最高聚類準(zhǔn)確率，LOW表示最低聚類準(zhǔn)確率，AVG表示平均聚類準(zhǔn)確率。

由表3可知，基于PCA的PCA-KDKM算法的聚類效果穩(wěn)定；對于yeast、abalone和skin數(shù)據(jù)集，PCA-KDKM算法的聚類準(zhǔn)確率都達(dá)到了84.35%以上，高于其他三種算法；在magic數(shù)據(jù)集上，PCA-KDKM算法聚類準(zhǔn)確率為79.63%，優(yōu)于其他三種算法。

表3 4種算法聚類準(zhǔn)確率對比Tab.3 Clustering accuracy comparison of 4 algorithms

表4 4種算法誤差平方和對比Tab.4 Squared error sums comparison of 4 algorithms

由表4可知，PCA-KDKM算法在4個數(shù)據(jù)集上的誤差平方和小于其他3種算法在4個數(shù)據(jù)集上的誤差平方和，說明PCA-KDKM算法的聚類效果比其他三種算法聚類效果好。

3.2 PCA-KMKD算法在網(wǎng)絡(luò)微博輿情檢測中的應(yīng)用

采用向量空間模型VSM(vector space model)將文本內(nèi)容的處理簡化為向量空間中的運(yùn)算，文檔中詞語的權(quán)重采用TF-IDF(term frequency-inverse document frequency)方法來計(jì)算。利用相同的數(shù)據(jù)集對PCA-KDKM算法及K-means算法進(jìn)行對比試驗(yàn)。

首先抓取一些目前比較熱門、關(guān)注度高的詞匯。本實(shí)驗(yàn)在新浪微博上分別為“戰(zhàn)爭”“上合峰會”“房地產(chǎn)”以及“中美貿(mào)易戰(zhàn)”等四個關(guān)鍵詞的每個詞匯均抓取10 000條數(shù)據(jù)，然后進(jìn)行人工過濾篩選來保證數(shù)據(jù)的準(zhǔn)確性及有效性。從每個詞匯分類中選取400條以上的微博數(shù)據(jù)，每條字符長度在20以上的微博共篩選出1 600條，作為本次微博輿情聚類實(shí)驗(yàn)的訓(xùn)練數(shù)據(jù)集。采用中國科學(xué)院研究開發(fā)的ICTCLAS分詞系統(tǒng)，對從新浪微博中提取的數(shù)據(jù)進(jìn)行數(shù)據(jù)鏡像分詞、詞性標(biāo)注處理，并借助停用詞表進(jìn)行過濾，把停用詞從分詞結(jié)果中過濾掉，然后使用TF-IDF方法構(gòu)造微博數(shù)據(jù)的向量空間模型(VSM特征項(xiàng)矩陣)，實(shí)現(xiàn)對網(wǎng)絡(luò)微博文本數(shù)據(jù)的聚類。

3.3 PCA-KDKM算法在輿情應(yīng)用中的實(shí)驗(yàn)結(jié)果分析

采用信息檢索領(lǐng)域廣泛使用的度量標(biāo)準(zhǔn)F度量值，作為微博文本數(shù)據(jù)聚類結(jié)果的評價標(biāo)準(zhǔn)。該方法將查準(zhǔn)率(W)和查全率(Z)兩個因素結(jié)合在一起，使得度量更加客觀公正，W和Z分別由以下公式計(jì)算得出：

W=TP/(TP+FP)，
Z=TP/(TP+FN)。

其中，TP即聚類的正確文檔數(shù)，為正類被劃分為正類的文檔數(shù)，F(xiàn)P為負(fù)類被劃分為正類的文檔數(shù)，F(xiàn)N為正類被劃分為負(fù)類的文檔數(shù)，TP+FP表示實(shí)際分類的文檔數(shù)，TP+FN表示應(yīng)有的文檔數(shù)。

為了更客觀地對算法的聚類性能進(jìn)行評價，本研究對K-means、PCA-KDKM、KNE-KM、QMC-KM、CFSFDP-KM 5種算法進(jìn)行實(shí)驗(yàn)。由于PCA-KDKM算法聚類中心穩(wěn)定，所以只進(jìn)行k(聚類中心的個數(shù)k)次實(shí)驗(yàn)，其他4種算法進(jìn)行30次實(shí)驗(yàn)。表5是K-means、PCA-KDKM、KNE-KM、QMC-KM、CFSFDP-KM 5種算法F平均值實(shí)驗(yàn)結(jié)果對比。

表5 5種算法F平均值對比Tab.5 Comparison of the average of F 5 algorithm %

由表5可知，PCA-KDKM算法F值相對穩(wěn)定，不像其他4種算法那樣波動大。此外，PCA-KDKM算法聚類準(zhǔn)確率相比K-means、KNE-KM、QMC-KM、CFSFDP-KM 4種算法聚類準(zhǔn)確率有明顯提高。運(yùn)用PCA-KDKM算法對微博文本中提取的5個詞匯，共計(jì)40 000條微博數(shù)據(jù)進(jìn)行抓取，然后對數(shù)據(jù)進(jìn)行聚類，所得到的聚類結(jié)果與時下討論的熱點(diǎn)問題事實(shí)數(shù)據(jù)一致，從每個簇中微博輿情數(shù)據(jù)的特征項(xiàng)，可以快速獲得時下微博輿論關(guān)注的熱點(diǎn)。以“中美貿(mào)易戰(zhàn)”為例，最近討論比較多的是“中興”“特普朗”“中國芯”等，其中“中興”熱度最高，符合最近微博輿情的基本情況。

圖2 運(yùn)行時間對比Fig.2 Comparison of running time

下面進(jìn)行運(yùn)行時間的比較。PCA-KDKM算法在初始計(jì)算初始聚類中心時，計(jì)算量較大，有一定的時間消耗，但從試驗(yàn)運(yùn)行情況來看，在微博關(guān)鍵詞聚類過程中迭代次數(shù)減少了，因此總體進(jìn)行微博聚類的運(yùn)行時間降低。為驗(yàn)證PCA-KDKM算法的時間效率，分別選取具有代表性的4次聚類時間，對K-means、KNE-KM、QMC-KM、CFSFDP-KM算法以及PCA-KDKM算法進(jìn)行比較。由圖2可得PCA-KDKM算法在運(yùn)行時間上比K-means算法有明顯優(yōu)勢，也比KNE-KM、QMC-KM、CFSFDP-KM三種算法的運(yùn)行時間短。

綜上，PCA-KDKM算法不僅顯著提高了聚類的準(zhǔn)確率，而且還提高了運(yùn)行效率，能夠更快更準(zhǔn)的發(fā)現(xiàn)輿論熱點(diǎn)話題。

4 結(jié)論

本文提出了PCA-KDKM算法：首先利用PCA算法進(jìn)行降維，選取主屬性，利用k′dist圖自動獲取k值并采用基于最大最小距離算法依次選取k個初始聚類中心，消除了當(dāng)初始聚類中心選取到噪音數(shù)據(jù)以及孤立點(diǎn)時導(dǎo)致的聚類結(jié)果不穩(wěn)定且容易陷入局部最優(yōu)解的影響。將本文提出的PCA-KDKM算法應(yīng)用到網(wǎng)絡(luò)微博高關(guān)注度詞匯分析中，實(shí)驗(yàn)結(jié)果表明：PCA-KDKM算法在聚類的準(zhǔn)確率和運(yùn)行效率方面都比K-means及其他算法高，在用于微博高關(guān)注度詞匯數(shù)據(jù)進(jìn)行聚類分析時，可以快速而準(zhǔn)確發(fā)現(xiàn)當(dāng)前微博輿論的熱點(diǎn)話題，有利于政府機(jī)構(gòu)快速決策，降低社會負(fù)面影響。