王志凱 於躍成 蔡 瑩 嚴(yán)長(zhǎng)春

（江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江 212003）

1 引言

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

3.1 用戶間的親密度

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

通常，我們判斷一個(gè)用戶對(duì)一篇微博博文是否感興趣的標(biāo)準(zhǔn)是通過(guò)轉(zhuǎn)發(fā)、評(píng)價(jià)和點(diǎn)贊來(lái)計(jì)算的。但是由于在數(shù)據(jù)獲取上不便于得知一個(gè)用戶是否對(duì)于另一篇博文有點(diǎn)贊行為。因此，我們利用一個(gè)用戶對(duì)其他用戶的轉(zhuǎn)發(fā)和評(píng)價(jià)行為來(lái)控制約束項(xiàng)，通過(guò)微博博文來(lái)對(duì)用戶進(jìn)行約束聚類。

圖1 樣本選取圖示

假設(shè)一個(gè)用戶有評(píng)價(jià)行為Com 和轉(zhuǎn)發(fā)行為For，用Act 來(lái)表示兩個(gè)用戶之間關(guān)系的親密程度。由于一個(gè)用戶可能有多個(gè)關(guān)注的對(duì)象，因此用戶xi與另一個(gè)用戶xj之間關(guān)系的親密度可以量化為Actij，可用式（2）表示。

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

3.2 微博用戶劃分

如式（3）所示的聚類目標(biāo)函數(shù)，本文提出的用戶劃分方法只是建議有關(guān)注關(guān)系并且用戶關(guān)系相對(duì)親密的用戶，在根據(jù)文本內(nèi)容進(jìn)行聚類的時(shí)候能夠劃分到一個(gè)用戶群體中去，并沒(méi)有強(qiáng)制規(guī)定兩個(gè)有關(guān)注關(guān)系的用戶必須要?jiǎng)澐值酵粋€(gè)用戶群體中去。因此，相比于經(jīng)典的約束K-means 聚類，本文提出的方法是一種弱約束的K-means 聚類方法。算法流程如圖2所示。

圖2 結(jié)合用戶行為的約束聚類算法

其中，Ck表示第k個(gè)簇的樣本集。

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

2）最近三個(gè)月內(nèi)有過(guò)發(fā)布微博或者轉(zhuǎn)發(fā)微博的行為；

3）關(guān)注的用戶量至少有10人；

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

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

4.2 實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)

本節(jié)提出的用戶劃分方法不同于傳統(tǒng)的k-means 算法，由于在通過(guò)聚類劃分用戶的時(shí)候考慮到了用戶的關(guān)注關(guān)系，因此，實(shí)驗(yàn)采用模塊度Q值來(lái)作為評(píng)價(jià)用戶劃分的標(biāo)準(zhǔn)。

模塊度度值可以用來(lái)描述社交網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)好壞。模塊度Q 值可用用戶關(guān)系中實(shí)際的邊數(shù)減去隨機(jī)情況下用戶間的邊數(shù)。如式（4）所示。

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

4.3 弱約束聚類劃分效果

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

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

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

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

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

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

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

圖4 無(wú)約束關(guān)系但卻在同個(gè)群體中的用戶數(shù)

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

4.4 用戶群體劃分效果比較

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

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

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

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

5 結(jié)語(yǔ)

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