王志凱 於躍成 蔡 瑩 嚴長春

（江蘇科技大學計算機學院 鎮(zhèn)江 212003）

1 引言

隨著互聯(lián)網(wǎng)時代的發(fā)展，人們已經(jīng)步入了大數(shù)據(jù)時代，社交網(wǎng)絡上的數(shù)據(jù)也是如此。分析微博數(shù)據(jù)和微博用戶劃分方法已成為網(wǎng)絡數(shù)據(jù)挖掘的研究重點之一。而這之中涉及的主要方法有文本聚類和主題分析等。

值得注意的是，微博上的數(shù)據(jù)普遍存在著文本較短、口語化現(xiàn)象較為嚴重等問題。以新浪微博為例，它限制一篇微博的字數(shù)不超過150 字。同時，由于微博上的言論自由，個性化的語言通常伴隨著大量的省略和指代。微博博文的這些特點，為通過文本方式處理信息帶來很大的困難，采用普通方法分析這些數(shù)據(jù)時難以獲得有效的結果。

針對以上問題，結合微博數(shù)據(jù)特點來改進聚類過程的實現(xiàn)成為近年來分析微博數(shù)據(jù)的主流技術之一。劉濤［1］等通過在不同的聚類過程中使用有監(jiān)督的方式選擇特征，大幅提高了文本聚類的性能。彭京［2］等針對文本數(shù)據(jù)維度高和數(shù)據(jù)稀疏的特點，在內積空間的基礎上建立了詞和文本的相似度度量方法，獲得了比傳統(tǒng)方法質量更好的分析結果。文獻［3］以Hownet 的情感詞典為基礎，構建了一個自動機來計算短文本的情感傾向。相比于一般文本分類方法，改方法在短文本上優(yōu)勢明顯。張猛［4］等通過獲取文本的細化簇并結合了曲線的多項式擬合技術，在細化簇上進行聚類，改進了文本聚類方法。索紅光［5］等采用了局部搜索優(yōu)化的思想，根據(jù)目標函數(shù)值的變化對聚類的結果作再次劃分，改進了K-means在文本聚類上的應用。

另一方面，從微博上的用戶發(fā)布微博的行為來看，其出發(fā)點包括轉發(fā)好友的博文、和好友互動、遵從個人的興趣愛好［6～7］等情況。基于上述特點，利用微博用戶行為信息成為微博數(shù)據(jù)分析的另一類主流方法。Griven［8］等在2002 年提出了社交網(wǎng)絡中社區(qū)的概念。Gao Q［9］等結合用戶之間的關系和文本信息，把用戶劃分成不同拓撲結構上的群體。Java A［10］等通過對twitter上用戶的位置信息的研究發(fā)現(xiàn)，互動性強或者相關性高的用戶會逐漸形成一個個群體。Liu［11］等提出的NAS算法在挖掘社區(qū)信息是考慮了節(jié)點屬性的相似度。由此可見，對微博用戶進行劃分僅僅抓住博文信息是不夠的。

受以上方法的啟發(fā)，針對微博上新用戶的博文內容過少、朋友圈狹窄，部分用戶博文內容過短、主題單一等問題，以K-means 算法為基礎，結合半監(jiān)督聚類的思想，提出了一種基于用戶關系和行為的弱約束K-means 聚類算法來對微博上的用戶進行劃分。以改善標準K-means 進行文本聚類時過于依賴詞頻的缺陷。

2 相關工作

傳統(tǒng)的K-means［12～14］算法是一種無監(jiān)督的聚類算法，這種方式的聚類結果很可能會與我們的理想結果有一定的差距。因此，我們希望能夠附加一些條件，使得聚類算法的結果更符合預期的標準。

約束聚類是一種將指定領域的知識通過“信息約束”的方式添加到聚類過程的方法。Wagstaff等［15］提出了must link 以及cannot link 這兩種形式的約束。must link 我們可以稱之為樣本間的正約束，cannot link 我們可以稱之為樣本間的負約束。在該思想中，若一對樣本(xi，xj)∈ML，即(xi，xj)滿足must link 約束條件，則樣本xi和樣本xj屬于同一個簇；反之，如果一對樣本(xi，xj)∈NL，即(xi，xj)滿足cannot link約束條件，則樣本xi和樣本xj不屬于同一個簇。其中集合ML則被稱為正約束的樣本集，集合NL被稱為負約束的樣本集。PCC［16］聚類 算 法（Pairwise Constrained Clustering）在 傳 統(tǒng)K-means的基礎上，在聚類的時候引入了約束性的監(jiān)督信息。將約束條件添加到K-means 的目標函數(shù)中，依靠約束信息，使得算法在執(zhí)行的時候有條件的進行搜索，以保證滿足正約束的樣本對能夠屬于同一個簇，滿足負約束的樣本對不屬于同一個樣本簇。由于基于劃分的聚類算法不能直接處理約束條件，需要優(yōu)化目標，使用懲罰約束參數(shù)，使得樣本對在滿足約束條件的同時，每個樣本到簇中心的距離和能夠最小。

因此，基于約束的K-means聚類的目標函數(shù)如下所示。

其中，Zi和Zj為樣本xa和xb的簇標記；ML和NL分別表示must link 和cannot link 兩種形式的約束集；Wij表示這兩種約束違反的代價權重。是一個指示函數(shù)，用來表示［true］=1，否則［false］=0，表示第k個簇的質心。

3 基于約束K-means 的微博用戶群體劃分

在微博中，一個用戶發(fā)布的博文，往往是轉發(fā)的好友博文、與好友的互動或者是自身興趣愛好的體現(xiàn)。每個微博文本都包含著評論、轉發(fā)、點贊等用戶行為，任何一篇博文都不是獨立存在的。在傳統(tǒng)的對微博用戶進行劃分的過程中，只重視了文本的信息，而忽視了用戶的行為信息。因此，本節(jié)提出了一種基于用戶行為的改進K-means 弱約束聚類，以通過引入用戶行為信息來改善僅僅使用文本信息來劃分微博用戶時所面臨的問題。

3.1 用戶間的親密度

根據(jù)微博博文中反映出來的用戶關系和用戶行為，我們使用聚類算法對微博用戶進行劃分的時候，給予每個樣本一個約束信息，同時保留博文之間的文本關系。為了防止數(shù)據(jù)信息偏差過大，我們在選取用戶約束關系時使用了三層關系網(wǎng)的數(shù)據(jù)。如圖1 所示，在描述目標用戶的約束信息時，選擇目標用戶自身關注的用戶。直覺上，目標用戶關注的用戶與目標用戶存在共同興趣的概率要高于隨機選擇的用戶，因此，為了改善新用戶直接關系用戶過少，約束信息太弱的現(xiàn)象，選擇目標用戶關注的用戶所關注的用戶作為當前目標用戶的弱約束信息，以進一步改善新用戶易被忽略的問題。

通常，我們判斷一個用戶對一篇微博博文是否感興趣的標準是通過轉發(fā)、評價和點贊來計算的。但是由于在數(shù)據(jù)獲取上不便于得知一個用戶是否對于另一篇博文有點贊行為。因此，我們利用一個用戶對其他用戶的轉發(fā)和評價行為來控制約束項，通過微博博文來對用戶進行約束聚類。

圖1 樣本選取圖示

假設一個用戶有評價行為Com 和轉發(fā)行為For，用Act 來表示兩個用戶之間關系的親密程度。由于一個用戶可能有多個關注的對象，因此用戶xi與另一個用戶xj之間關系的親密度可以量化為Actij，可用式（2）表示。

其中，Comij表示用戶xi對用戶xj的博文的評價次數(shù)，F(xiàn)orij表示用戶xi對用戶xj的轉發(fā)次數(shù)。Com表示用戶i對所有好友的評論總數(shù)，F(xiàn)or 表示用戶i對所有關注的好友的轉發(fā)總數(shù)。本文用用戶xi對用戶xj的博文的評價次數(shù)與轉發(fā)次數(shù)的和與用戶xi對于博文總共的評價次數(shù)和轉發(fā)次數(shù)的和的比值，來比較用戶xj相較于用戶的xi的親密程度。

3.2 微博用戶劃分

如式（3）所示的聚類目標函數(shù)，本文提出的用戶劃分方法只是建議有關注關系并且用戶關系相對親密的用戶，在根據(jù)文本內容進行聚類的時候能夠劃分到一個用戶群體中去，并沒有強制規(guī)定兩個有關注關系的用戶必須要劃分到同一個用戶群體中去。因此，相比于經(jīng)典的約束K-means 聚類，本文提出的方法是一種弱約束的K-means 聚類方法。算法流程如圖2所示。

圖2 結合用戶行為的約束聚類算法

其中，Ck表示第k個簇的樣本集。

4 實驗結果與分析

4.1 實驗數(shù)據(jù)獲取與預處理

由于考慮到實驗的數(shù)據(jù)是要來自于微博平臺，并且很多信息來自于博文和用戶的信息，因此我們采用以下三種方式相結合的方式：1）通過網(wǎng)絡爬蟲，將爬出的網(wǎng)頁解析，運用正則表達式、人工觀察相結合的方式，獲取所需的數(shù)據(jù)。這個方式目的性明確，只是獲取數(shù)據(jù)的方式最為復雜且速度相對比較慢；2）通過申請新浪微博的公開的API的方式獲取數(shù)據(jù)，通過提供的指定接口，請求需求的數(shù)據(jù)；3）通過網(wǎng)上已經(jīng)公開的一些微博數(shù)據(jù)。最經(jīng)常使用的公開數(shù)據(jù)源的網(wǎng)站是中國爬盟。

為了保證獲取的數(shù)據(jù)源的質量，需要我們排除一些無用的數(shù)據(jù)，合適的數(shù)據(jù)有利于我們有效地分析數(shù)據(jù)，因此，在獲取數(shù)據(jù)之后，必須采取有效的方法對數(shù)據(jù)進行預處理。在數(shù)據(jù)預處理階段，首先刪除一些關注用戶過少的用戶（僵尸用戶不利于我們后續(xù)的推薦），同時對于一定的時間段內，發(fā)布微博過少（不活躍用戶）的用戶，也以予刪除。同時，對于予以采用數(shù)據(jù)的用戶，記錄下博文的評論數(shù)、轉發(fā)數(shù)、點贊數(shù)和用戶標簽信息（如果有的話）。本節(jié)實驗的數(shù)據(jù)篩選標準如下：

1）每條博文去除停用詞、分詞后，詞語的數(shù)量大于3；

2）最近三個月內有過發(fā)布微博或者轉發(fā)微博的行為；

3）關注的用戶量至少有10人；

4）發(fā)表的總微博數(shù)大于等于10。

對于從用戶獲取的微博文本信息，使用Jieba分詞算法進行分詞、去除停用詞并且去除一些過短的文本、文本中的表情、顏文字等。

4.2 實驗評價標準

本節(jié)提出的用戶劃分方法不同于傳統(tǒng)的k-means 算法，由于在通過聚類劃分用戶的時候考慮到了用戶的關注關系，因此，實驗采用模塊度Q值來作為評價用戶劃分的標準。

模塊度度值可以用來描述社交網(wǎng)絡中社區(qū)結構好壞。模塊度Q 值可用用戶關系中實際的邊數(shù)減去隨機情況下用戶間的邊數(shù)。如式（4）所示。

其中，eii表示社區(qū)i 中，有關注關系的用戶間邊的個數(shù)，ai表示社區(qū)i中，任意用戶相連邊的個數(shù)。

4.3 弱約束聚類劃分效果

由于本文提出的約束信息是基于用戶關系和用戶的行為的聚類。因此，在對用戶進行劃分后，首先分析每個用戶群體中，滿足約束條件的用戶的個數(shù)，分析弱約束聚類的效果。

在下圖實驗結果中，以選定的目標用戶為中心，選取周圍200 名，且在三個月內發(fā)布微博數(shù)超過30 條的用戶，總計7645 條微博文本。將周圍的用戶劃分為5、6、7、8、9、10 個用戶群體后，分析每個群體中有交互關系的用戶卻不在在一個群體中的個數(shù)、沒有關注交互卻仍在一個群體中的個數(shù)以及模塊度值。

圖3 反映了在不同的用戶群體數(shù)下，具有交互關系卻在不一個群體中的個數(shù)。

如圖3 所示，當只使用K-means 方法，通過文本分析劃分微博用戶的時候，在所有用戶群體中，具有交互關系但是不在一個群體中的用戶數(shù)量隨著用戶群體的增加，呈現(xiàn)了逐漸增長的態(tài)勢，當分為10 個用戶群體的時候，已經(jīng)有超過50%的用戶在被劃分的時候忽視了用戶間的交互信息。相比之下，使用約束K-means的方法劃分用戶群體的時候，隨著用戶群體的數(shù)量的增加，一直保持著將近80%的用戶能和與自己有交互關系的用戶位于同一個用戶群體中。

圖3 有交互關系但不在同個群體中的用戶數(shù)

綜上所述，由于微博中的任何博文都不是孤立存在的，當只使用傳統(tǒng)的文本聚類的方法劃分用戶時，已經(jīng)把每個用戶的博文看作是孤立存在的。通過這種方式劃分出來的用戶群體只有詞之間的聯(lián)系，沒有交互性。相反，使用本文的方法劃分用戶時，能較好地區(qū)分用戶的關系，相比于傳統(tǒng)的方法，具有較大的提升，更適合與微博用戶劃分。

根據(jù)本文的方法，分析了圖3 的數(shù)據(jù)后，還需要分析沒有交互關系卻被分到同一個群體中的數(shù)量。圖4 反映了用戶群體中沒有交互關系的用戶卻在同一個群體中的用戶數(shù)目。

圖4 無約束關系但卻在同個群體中的用戶數(shù)

通過比較兩種方法可以看出，傳統(tǒng)的聚類相比本文提出的方法，同一個用戶群體中存在著更多的沒有交互關系的用戶。隨著用戶群體的增多，傳統(tǒng)的方法保持著較高的非關系用戶，平均每200 個用戶就有80 個左右這樣的用戶。而本文提出的算法則較好地減少了這種用戶，并且隨著用戶群體的增加這類用戶對維持在55 左右。同時這也能證明本文的方法是一種弱約束的聚類算法，它并沒有強制規(guī)定每個用戶群體中只能存在有交互關系的用戶，只是建議將親密度比較高的用戶劃分在一個群體中。

4.4 用戶群體劃分效果比較

由于微博用戶的劃分不能僅僅通過比較每個用戶群體的文本聚類準確度來判斷，因此為了評價本文的算法和傳統(tǒng)的K-means 算法在劃分用戶時的差異，實驗使用模塊度值來評價兩種方法。結果如表1所示。

表1 兩種算法的模塊度值的比較

從表1 的實驗結果可以看出，本文提出的方法在劃分微博用戶群體的時候，比傳統(tǒng)的只通過文本聚類的方法更加的合理。在用戶群體個數(shù)從5 增長的過程中，傳統(tǒng)的方法由于只關心了文本信息，因此在將用戶劃分后，模塊度值一直處在很低的水平，這也說明傳統(tǒng)劃分方法結果雖然能使得每個群體中的用戶有相似的興趣，但是用戶之間卻都是陌生的，在處理微博上的新用戶或朋友少的用戶時，效果不佳。

而本文的方法在劃分用戶群體時，在微博用戶真實數(shù)據(jù)集下，當用戶被劃分為7 個群體時效果達到了峰值，最佳結果是0.343966，這時構成的用戶群體是最為穩(wěn)定的，同時也反映用戶在交友的過程中，興趣相似固然很重要，但是人與人之間能否溝通是不可忽略的。

5 結語

本文主要針對網(wǎng)絡社交平臺下，劃分用戶群體時僅僅依賴用戶的微博文本，忽略了用戶間的內在聯(lián)系等問題，采用聚類思想，改進了用戶劃分的方式。提出了基于用戶關系和用戶緊密度的約束聚類，將單獨的用戶劃分成有內部關聯(lián)的用戶群體，針對微博平臺，進行了適應性的改進并且通過實驗數(shù)據(jù)的比較證明了結合了用戶間關注信息的約束聚類能夠更好地劃分用戶，適應微博平臺。未來的工作中，將針對微博中朋友少的用戶、微博文本少的用戶，改進劃分用戶的方法。