PCA-KDKM算法及其在微博輿情中的應用

，

(山東科技大學 計算機科學與工程學院，山東 青島 266590)

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

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

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

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

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

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

1 k′dist圖

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

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

2 PCA-KDKM算法

2.1 PCA-KDKM算法相關定義

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

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

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

(1)

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

(2)

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

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

定義4聚類質量評價函數[20]

(3)

其中

(6)

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

PCA-KDKM算法的聚類質量評價函數S的值域介于-1和1之間。結合類內距離與類間距離這兩個因素來評估數據對象分類的合理性。S越接近1，說明該數據對象的類內平均距離遠遠小于類間的平均距離,該數據對象分類越合理；S越接近-1，說明數據對象類內平均距離遠遠大于類間的平均距離，分類不合理，應當取消。

2.2 主成分分析算法

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

標準化變換公式：

(7)

(8)

2.3 PCA-KDKM算法步驟：

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

輸出：根據數據對象特征分成的k個類別。

算法步驟：

1)UP×m按公式(7)、公式(8)計算相關系數矩陣R;

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗結果及分析

3.1 PCA-KDKM算法與各改進K-means算法的對比

實驗平臺：英特爾Xeon(至強)E5450@3.00 GHz 四核、4 G內存、500 G硬盤，Windows 7旗艦版系統。

實驗描述：實驗采用專為機器學習和數據挖掘算法設計的公共數據庫UCI來進行實驗[21]。UCI中的每個數據對象都有分類編號，因此可以將PCA-KDKM算法得出的聚類結果與UCI數據庫中數據對象的分類標志進行一致性統計，來評價PCA-KDKM算法的聚類質量。采用UCI數據庫中的Iris、Glass Identification、Wine和Hayes-Roth 4組數據。為了對比K-means算法與PCA-KDKM算法的準確度，對4組數據不作任何修改。

基于先前實踐經驗，PCA-KDKM算法進行實驗時對Iris和Glass Identification這兩組數據指定領域ε為1，某點p的ε范圍內含數據對象的最小個數ptsmin為50；對于Wine指定領域ε為10 000，某點p的ε范圍內含數據對象的最小個數ptsmin為50；對于Hayes-Roth指定領域，ε為600，某點p的ε范圍內含數據對象的最小個數ptsmin為40。PCA-KDKM算法得到的初始中心是穩定的，所以對PCA-KDKM算法進行k次實驗即可。K-means算法進行了50次實驗，與PCA-KDKM算法的實驗對比結果如表1、2所示。

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

表2 PCA-KDKM算法與K-means算法聚類質量評價函數值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個數據集合,PCA-KDKM算法在聚類準確率和聚類質量評價函數值方面比K-means算法的聚類準確率明顯提高，聚類準確度為90%以上；對于Wine數據對象集合來說，PCA-KDKM算法比K-means算法的準確率提高不明顯，但從聚類質量評價函數值S來看，PCA-KDKM算法比K-means算法的聚類效果好。

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

由表3可知，基于PCA的PCA-KDKM算法的聚類效果穩定；對于yeast、abalone和skin數據集，PCA-KDKM算法的聚類準確率都達到了84.35%以上，高于其他三種算法；在magic數據集上，PCA-KDKM算法聚類準確率為79.63%，優于其他三種算法。

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

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

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

3.2 PCA-KMKD算法在網絡微博輿情檢測中的應用

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

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

3.3 PCA-KDKM算法在輿情應用中的實驗結果分析

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

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

其中，TP即聚類的正確文檔數，為正類被劃分為正類的文檔數，FP為負類被劃分為正類的文檔數，FN為正類被劃分為負類的文檔數，TP+FP表示實際分類的文檔數，TP+FN表示應有的文檔數。

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

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

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

圖2 運行時間對比Fig.2 Comparison of running time

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

綜上，PCA-KDKM算法不僅顯著提高了聚類的準確率，而且還提高了運行效率，能夠更快更準的發現輿論熱點話題。

4 結論

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