一種實現微博興趣挖掘的粒子群優化k-means 算法?

沈 超 王 遜 黃樹成

（江蘇科技大學計算機學院 鎮江 212003）

1 引言

微博是人們日常交流、獲取社會資訊不可或缺的一種網絡渠道。由于微博用戶數量的急劇增長，產生的信息量也隨之呈指數級增長。一個正常的微博用戶，通常每天收到的博文數高達幾千甚至上萬條。面對如此巨大的數據量，用戶很難在其中發現感興趣的博文，因此個性化地推薦用戶感興趣的博文就顯得格外重要。在此過程中，如何快速地捕獲用戶在當前時間段感興趣的話題是關鍵。

從文獻調查中發現，微博興趣挖掘近年來被國內外眾多學者關注和研究。對興趣挖掘的研究分為兩個方向，第一個方向是對挖掘文本的選擇研究，如Abel［1］等研究了微博文本長短對興趣挖掘的影響。第二個方向是對挖掘算法的研究，如劉紅兵等使用改進的Single-Pass 結合層次聚類算法對博文進行挖掘。使用聚類算法［2］對用戶博文數據進行挖掘，可以很好地將相似的興趣點挖掘出來。

目前k-means算法［3］在數據挖掘領域使用得較為廣泛，使用該算法可以很準確地挖掘出用戶當前時間所關注的興趣話題。但在對微博用戶大量數據處理時，時間代價較大，同時存在受初始聚類中心影響較大的缺點。因此，劉靖明提出在k-means的基礎上，結合粒子群算法加以優化。綜上所述，本文提出一種參數間相互作用的MPSO-kmeans 算法。該算法可以有效地節約處理時間，同時避免k-means的缺點，具有更好的聚類效果。

2 相關算法介紹

2.1 k-means算法

k-means 是聚類算法中使用場景最廣泛的一種，對數據的處理過程分為兩個階段，第一階段設置類族數量，將數據集中的每個數據分別劃分到類族中某一類中，第二階段通過迭代計算，找出聚類中心，重新劃分，達到結束條件為止。該算法原理是通過計算不同空間數據的歐式距離，進行相似度分析，將相似度高的數據聚類到同一個類族。

該算法聚類步驟如下：首先輸入樣本S=X1,X2,X3,…,Xm。

1）設定類族數量，即算法k值；

2）隨機指定k個聚類中心 μ1,μ2,…,μk,k ＜m；

4）若算法達到結束條件，則算法結束。如果沒有，使用同一類簇中的數據，計算新的類簇中心，然后轉到步驟2）進行迭代。

雖然k-means 具有操作簡單、所需資源少、計算速度快等優點。但仍存在一些缺點：

1）該算法需先給定聚類個數，聚類個數很難估計，在知道給定數據集前，并不能確定將其分為多少類最合適；

2）算法需先設置初始聚類中心，隨機選取，對導致聚類結果變化巨大；

3）迭代過程中，需要不斷的計算，找出新的中心，時間開銷很大；

4）若類族中存在孤立點，將導致均值偏移。

2.2 粒子群算法

粒子群算法［4］是一種基于動物集群活動而產生的群體搜索算法，該算法利用個體間信息的共享，使群體的求解從無序到有序，進而求出最優解。群體中的每個個體稱為粒子。粒子在空間以隨機初始速度飛行，根據個體最優位置、群體最優位置和粒子當前速度，不停地調整飛行位置和速度。

假設粒子在q 維空間飛行，那么粒子i 的位置、速度均為q 維向量，其速度可表示為優位置表示為Pbi=( Pbi1,Pbi2,…,Pbiq)，群體最優位置表示為Gb=(Gb1,Gb2,…,Gbq)。

如果找到個體最優解，群體最優解，可以使用以下公式調整粒子飛行的位置和速度：

在式（1）和（2）中，w表示慣性權重，而c1，c2表示學習因子，其表示個體最優位置、群體最優位置對粒子i 飛行速度的影響程度；r1，r2為[0,1]間隨機值，表示速度定義不同部分的隨機權重。

粒子群算法通過計算適應度函數，對算法結果評價。設適應度函數為f(X)，則個體最優位置Pbi對應的函數為f(Pbi)，全局最優位置對應的函數為f(Gbi)。如果粒子適應度值優于個體最優值，那么用粒子當前位置替代個體最優位置。群體中適應度值最優的粒子位置，即為群體最優位置。

粒子個體最優位置更新公式，如式（3）所示：

3 MPSO-kmeans算法

3.1 粒子群優化的k-means算法

k-means 是聚類算法中最經典、簡單的一種，被運用到很多領域，如數據挖掘、模式識別等，但如2.1 節所介紹，傳統k-means 算法仍具有一些缺點，而粒子群算法在全局搜索方面具有顯著的優勢，為克服k-means 中存在的問題提供了新的方案。根據上述分析，使用粒子群算法和k-means融合［5］，不僅可以提高收斂速度、減少時間代價，而且可以提高聚類效果，克服算法缺陷。

雖然這種融合算法在選取最優聚類中心方面很好地克服了k-means 的缺陷，但是并不能擺脫粒子群自身存在的缺陷，如粒子在飛行過程中，根據式（1）、（2）不斷調整自身的位置和速度，而慣性權重和學習因子通常被設為固定常量，或者被設定為獨立變量，這種情況下各參數之間相互削弱，難以達到全局搜索、局部開發的相對平衡；粒子在迭代飛行過程中，可能存在過于早熟現象；針對上述問題，本文對融合PSO-kmeans算法進行優化處理。

3.2 算法優化策略

1）慣性權重優化

慣性權重［6］是粒子群優化中非常重要的參數之一，通過設置不同權重，可以控制算法具有不同的全局搜索能力。較大的慣性權重有助于提升全局搜索能力，防止算法早熟。而較小的慣性權重有助于提升局部搜索精度。因此，慣性權重在一定程度上有著平衡全局和局部搜索能力［7］的作用。

在利用粒子群優化算法尋找最優解的早期，希望算法具有較好的全局搜索能力，而后期則希望其具有較高的精度搜索。因此本文引入了一種線性遞減的慣性權重，該權重w 值隨運行次數的增加，不斷減小。最終，算法由初期的全局搜索轉為后期局部的高精度搜索，權重設置如式（4）所示：

式（4）中：wmax為慣性權重最大值；wmin為慣性權重最小值；一般wmax取0.9，wmin取0.4；t 為當前迭代次數；N為最大迭代次數。

2）學習因子優化

學習因子［8］也是影響粒子飛行的重要參數之一。學習因子c1表示自我認知對飛行軌跡的影響程度，學習因子c2表示群體認知對粒子飛行軌跡的影響程度。如果c1較大，會使粒子不斷地在局部飛行、震蕩；如果c2較大，會使粒子過早收斂，導致早熟。為了權衡自我認知、群體認知對飛行軌跡的影響，引入隨慣性權重變化的學習因子，公式如下所示：

式（5）、（6）中，c1s，c2s表示對應學習因子的初始值；c1e，c2e表示對應學習因子的終止值。

3）時間飛行因子的引入

由粒子位置更新公式可知，其位置更新方式是在原位置的基礎上加上粒子更新后的速度。在物理學概念中，位移只能與位移進行計算，由此可知，粒子位置更新公式中存在著隱藏的時間因子［9］。傳統的位置更新公式是將時間因子固定為1，在公式上會呈現位移加速度的更新方式。但這種更新方式將會導致粒子不斷在最優解附近震蕩，因此在算法中引入隨慣性權重線性變化的時間因子T 。令T=0.1+w，當T ≠1時，運行初期，因為慣性權重較大，時間因子也較大，粒子飛行位置保持著較大的變化，有利于全局搜索。后期由于慣性權重變小，時間因子也隨之變小，粒子飛行位置保持著較小的變化，提高了局部的搜索精度。

大數據分析平臺利用其分布式存儲能力，通過對綠通治理相關業務數據進行采集、清洗，存儲海量數據；同時，利用其并發計算能力，對海量歷史數據進行分析計算，對離散的數據進行實時的在線分析計算，并將計算結果同步至系統的各子平臺中。大數據分析平臺采用分布式主從節點架構、集群橫向可擴展和多數據副本冗余存儲，確保平臺穩定工作、數據安全不丟失；節點與節點之間使用RPC通信，經任務調度器實現任務資源的統一分配和統一管理。結合運維平臺，更加人性化、簡潔化地對整個大數據分析平臺進行監控、管理，可針對分析任務的實際情況進行調優，提升大數據平臺的分析效率。

因此，位置更新公式變更為式（7）所示：

3.3 MPSO-kmeans算法流程

本文采用粒子群算法融合k-means 算法進行改進優化，同時針對粒子群中存在的各參數相互獨立、相互削弱影響力的問題加以改進，改進后的算法步驟如下：

步驟一：初始化，將學習因子c1s，c2s初始值，c1e，c2e終止值，wmax，wmin慣性權重最大、最小值，群體中粒子的速度、個體最優位置、群體最優位置等參數初始化，并將其隨機分配到某一個類群中。

步驟二：運用粒子群算法搜尋最優的聚類中心。

1）采用式（3），調整粒子位置、速度，求出其適應度函數值；

2）比較當前粒子位置與歷史最優位置的適應度函數值，如果當前位置適應度更優，那么使用此位置替換個體最好位置；

4）按照最近鄰計算法則，把各粒子分類到對應的類簇；

5）利用新的類簇值計算出新的聚類中心，判斷是否達到結束條件，如果達到，則結束，否則，迭代執行步驟1）。

步驟三：將新的中心輸出到k-means，運行并得出結果。

4 實驗分析

4.1 數據集獲取與預處理

本文從微博獲取文本數據，獲取對象為某一位微博用戶及其特別關注的100 名用戶，獲取的時間是2017 年9 月10 號到2017 年9 月30 號，對于每個用戶取近20 天的相關數據，數據主要包括微博賬號自身信息，發布博文，轉發以及被轉發的微博數［10］等。使用每個用戶的這些數據，提取出其在當前時間段所感興趣的兩個話題。

對獲取到的文本數據，進行預處理［11］，以便計算機對數據的處理分析，過程如下。

1）對獲取到的文本數據進行清洗、分詞、去停用詞、提取特征詞等操作；

2）將預處理后的數據使用向量空間模型進行表示，將其轉變成計算機能處理的數據模型；

3）通過特征選擇、權重計算，對模型再次處理；

4）對預處理數據，進行聚類分析。

以一位用戶為例，預處理后的數據如表1 所示。

表1中，每一行中1表示此微博含有此特征詞，如第二行數據表示第一條博文含有的特征詞為“袁隆平”，“海水”，“水稻”，“改良”，“院士”，“鹽堿地”，0表示無此特征詞。

表1 各條博文的行特征詞（部分）

4.2 實驗分析

使用傳統的k-means、傳統粒子群和k-means混合算法、學習因子和飛行因子隨慣性權重調整的MPSO-kmeans 算法進行實驗。算法評價指標使用純度值［12］，如式（8）所示：

由于傳統k-means 對初始聚類中心較為依賴，不同中心的選取在實驗中產生的結果差別較大。因此使用傳統k-means 運算5 次，取其平均值進行比較分析。實驗得到的純度如表2所示。

表2 聚類挖掘結果純度比較

由表2純度值可知：傳統k-means的處理結果，雖然某些結果純度值較高，但其5 次運算的平均值偏低，且波動較大。這是因為傳統k-means 對初始中心的選擇存在隨機性的緣故。使用粒子群改進的k-means 算法可以很好地解決聚類結果波動較大的問題，使其不受初始聚類中心影響而產生較大波動。而結合了慣性權重、學習因子、飛行因子的MPSO-kmeans 算法，不僅提升了算法的全局搜索能力［13］，而且提升了算法的收斂精度［14］。實驗表明 ，改 進 后 的MPSO-kmeans 同PSO-kmeans、k-means 相比，在挖掘結果上具有更好的挖掘純度。

為了避免實驗數據的局限性，隨機選取的20名微博用戶近20 天的博文，使用以上這三種算法對其文本信息進行聚類分析，實驗結果如圖1 所示。

圖1 部分用戶不同算法聚類純度圖

圖1 中，橫軸數字i 代表第i 位用戶，縱軸表示聚類純度值。 由圖1 可知，使用k-means，PSO-kmeans，MPSO-kmeans 三種算法對微博用戶在近20 天所感興趣的兩個話題進行了挖掘［15］。經過比較分析得出改進后的MPSO-kmeans 算法在聚類效果上存在較為明顯的優勢。

5 結語

本文對微博用戶當前時間段感興趣的話題進行研究，根據微博用戶近20 天的博文信息，使用k-means 算法挖掘用戶所感興趣的話題。實驗過程中，為了提高聚類效果，克服k-means 存在的缺陷，引入了粒子群優化算法，并對相關參數進行了優化，提升了全局搜索能力，能夠更加精確、高效地完成聚類操作。實驗表明，MPSO-kmeans 算法可很好地解決了受初始聚類中心影響大的問題，同時提高了算法的全局搜索能力以及局部尋優能力，具有更好的聚類效果。后續工作將根據聚類出的用戶感興趣話題，搜索相關話題的博文，建立推薦模型，給用戶推薦其在當前時間段所感興趣的博文，實現微博的個性化博文推送。