基于CWMD和SP的微博話題發(fā)現(xiàn)算法

孫 悅，羅 倩，方梁雨

(北京信息科技大學(xué) 信息與通信工程學(xué)院，北京 100192)

0 引言

2020年新浪微博第一季度財(cái)報(bào)數(shù)據(jù)顯示，截至 2020 年 5月，微博的月活躍用戶已達(dá)5.50億，同比呈增長(zhǎng)趨勢(shì)。微博發(fā)布的信息往往具有時(shí)效性短、動(dòng)態(tài)性強(qiáng)和結(jié)構(gòu)不規(guī)范等特點(diǎn)[1]。從大量的文本數(shù)據(jù)中發(fā)掘出有價(jià)值的信息，具有重要意義。

微博話題發(fā)現(xiàn)過(guò)程就是一種有價(jià)值信息的發(fā)掘過(guò)程，其中最重要的環(huán)節(jié)是文本聚類過(guò)程。常見(jiàn)的聚類算法有基于劃分的K-means聚類[2],基于密度的DBSCAN算法[3],基于層次的Single-Pass算法[4]。武國(guó)勝等[5]對(duì)文本聚類使用了改進(jìn)的密度峰值算法，使用潛在語(yǔ)義分析模型(LSA)進(jìn)行建模，使用密度敏感距離作為聚類的標(biāo)準(zhǔn)。Wang等[6]使用Word2vec對(duì)文本進(jìn)行表示，引入了Canopy算法對(duì)文本進(jìn)行K-means聚類。劉金碩等[7]使用LDA模型表示文本，并使用K-means算法對(duì)文本進(jìn)行聚類處理，在食品安全文本類的數(shù)據(jù)集上進(jìn)行算法驗(yàn)證。車?yán)俚萚8]融合了向量空間模型、潛在狄利克雷分配模型和構(gòu)建命名實(shí)體模型3種方法，使用Single-Pass算法進(jìn)行新聞話題的發(fā)現(xiàn)。

這些聚類的相似度策略采用傳統(tǒng)的歐氏距離、余弦距離來(lái)計(jì)算文本之間的距離，用于相似度判斷的標(biāo)準(zhǔn)，忽略了當(dāng)文檔詞數(shù)不同時(shí)，詞與詞之間存在的“一對(duì)多”關(guān)系。因此，本文使用融合了余弦距離和WMD(word mover′s distance)的CWMD(cos-word mover′s distance) 來(lái)計(jì)算文本之間的距離，并且使用TF-IDF值代替WMD中的詞頻權(quán)重。同時(shí)，在微博話題發(fā)現(xiàn)中，因無(wú)法確定聚類后簇的個(gè)數(shù)，所以K-means算法并不適用；DBSCAN基于密度聚類，不能增量式聚類，即新到來(lái)的數(shù)據(jù)無(wú)法對(duì)已有的簇產(chǎn)生影響，也不適用于微博話題的檢測(cè)。對(duì)此，本文選取了基于層次聚類的Single-Pass算法進(jìn)行博話題檢測(cè)。

1 文本表示

常見(jiàn)的文本表示有向量空間模型(vector space model，VSM)、潛在的狄利克雷主題模型[9]等。在深度學(xué)習(xí)領(lǐng)域，Mikolov等[10]提出了Word2vec 模型，該模型結(jié)合上下文信息表示文檔中特定單詞的語(yǔ)義和語(yǔ)法信息。

VSM文本表示模型只考慮詞頻對(duì)文檔的影響，認(rèn)為詞之間獨(dú)立存在，忽略了其相關(guān)性。LDA主題模型對(duì)本文中微博數(shù)據(jù)的短文本信息不適用，因?yàn)檩^短的文本特征維度較高，數(shù)據(jù)比較稀疏,信息量少[11]，無(wú)法準(zhǔn)確地確定主題。

基于本文數(shù)據(jù)特點(diǎn)和各文本表示模型的優(yōu)缺點(diǎn)，提出TF-IDF & Word2vec文本表示模型。步驟如下：

輸入:文本語(yǔ)料M= {m1,m2,…,mn} 輸出:文本向量集 Step1:輸入文本語(yǔ)料集,對(duì)文本進(jìn)行Jieba分詞以及去除停用詞。每一條文本變?yōu)楹刑卣髟~的集合,即mi= {fi1,fi2,…}; Step2:將處理后的文本集合輸入到Word2vec模型中進(jìn)行訓(xùn)練,對(duì)于每一個(gè)特征詞fij都會(huì)得到一個(gè)N維的特征向量V(fij); Step3:利用TF-IDF公式計(jì)算文檔中特征詞的權(quán)重W(fij); Step4:根據(jù)Step2和 Step3中的計(jì)算結(jié)果,向量化表示mi= {(V(fi1),W(fi1)),(V(fi2),W(fi2)),…}。

2 CWMD算法

2.1 傳統(tǒng)文本距離計(jì)算方式

對(duì)文本進(jìn)行聚類，需要確定一種標(biāo)準(zhǔn)來(lái)判斷不同的文本是否相似，這個(gè)標(biāo)準(zhǔn)就是距離函數(shù)。常見(jiàn)的距離函數(shù)有歐氏距離、余弦距離、馬氏距離、曼哈頓距離等。在文本聚類中，歐氏距離和余弦距離因計(jì)算簡(jiǎn)便、易于理解而被廣泛使用。圖1展示了空間內(nèi)P、Q兩點(diǎn)的歐氏距離和余弦距離。

圖1 歐氏距離和余弦距離

假設(shè)計(jì)算兩個(gè)特征詞都為p維的文檔m1、m2的距離，m1的空間向量表示形式為W1=，〈w11,w13,…，w1p〉，m2的表示形式為W2=〈w21,w22,…，w2p〉，其歐氏距離為

(1)

余弦距離為

(2)

式(1)、(2)計(jì)算的是特征項(xiàng)個(gè)數(shù)相等的兩個(gè)文檔的距離，即W1的維度等于W2的維度。圖2展示的是當(dāng)兩個(gè)文檔特征項(xiàng)個(gè)數(shù)不同時(shí)，利用傳統(tǒng)方式計(jì)算文檔1到文檔2距離的情況。如果僅考慮兩文檔距離和最小，則最佳解決方案是使文檔1、2中每?jī)蓚€(gè)單詞的距離最小。在這種情況下，可能會(huì)出現(xiàn)文檔2中的一個(gè)詞對(duì)應(yīng)文檔1中多個(gè)特征詞，而忽略了文檔2中其他特征詞與文檔1中該詞的距離，極端情況下會(huì)出現(xiàn)一對(duì)所有的情況，這樣的計(jì)算方式并沒(méi)有考慮整個(gè)文檔中所有詞對(duì)于該文檔的貢獻(xiàn)。

圖2 傳統(tǒng)的文本距離計(jì)算方式

2.2 WMD計(jì)算方式

WMD是Kusner等[12]提出的一種基于EMD(earth mover′s distance)計(jì)算詞移距離的度量方式，與歐氏距離、余弦距離不同，WMD本質(zhì)是線性規(guī)劃問(wèn)題，計(jì)算的是兩個(gè)分布之間的距離，其計(jì)算公式如下：

(3)

圖3為使用WMD算法計(jì)算文檔P1和P2距離的方式。

圖3 WMD計(jì)算距離的方式

WMD具體算法過(guò)程如下：

兩個(gè)文檔P1、P2經(jīng)過(guò)Word2vec模型表示后，P1中的第i個(gè)詞和P2中的第j個(gè)詞的歐氏距離為

c(i,j)=‖xi-xj‖2

(4)

2.3 CWMD計(jì)算方式

在WMD中，Kusner等[12]使用歐氏距離衡量詞間的轉(zhuǎn)移代價(jià)。Word2vec模型屬于嵌入式模型，歐氏距離側(cè)重于數(shù)值上的絕對(duì)差值，計(jì)算結(jié)果受維度的影響。而余弦距離在維度變化情況下，仍體現(xiàn)方向上的差異，計(jì)算結(jié)果與維度無(wú)關(guān)。所以本文提出將余弦距離作為WMD詞轉(zhuǎn)移代價(jià)的度量方式，即提出CWMD算法。

WMD用詞頻來(lái)表示詞的權(quán)重，認(rèn)為一個(gè)詞出現(xiàn)的次數(shù)越多，則權(quán)重越大，忽略了關(guān)鍵詞信息?？紤]到不同的詞對(duì)句子的貢獻(xiàn)不同，本文使用TF-IDF值代替原始的詞頻作為WMD權(quán)重的輸入。

3 聚類算法

聚類分析也稱為群集分析。針對(duì)實(shí)驗(yàn)數(shù)據(jù)特征，本文采用結(jié)構(gòu)性聚類的層次聚類算法——SP文本聚類算法。傳統(tǒng)的SP算法中，語(yǔ)料庫(kù)中的每條數(shù)據(jù)按照順序參與一次聚類，而且對(duì)文本輸入的順序比較敏感，即一個(gè)文本簇中初始的文本對(duì)該簇的影響較大。微博文本長(zhǎng)度較短，包含的信息量較少，針對(duì)短文本數(shù)據(jù)的特點(diǎn)，本文提出了一種對(duì)初始文本集預(yù)處理的SP聚類算法。

為了使簇中初始的文本向量相對(duì)準(zhǔn)確，當(dāng)處理文本向量Di時(shí)，先不對(duì)其進(jìn)行相似度比對(duì)，而是判斷向量的長(zhǎng)度。如果小于規(guī)定的閾值L，則進(jìn)入待定區(qū)U,否則進(jìn)入預(yù)處理集合M。等M中文本數(shù)據(jù)聚類完成后，對(duì)待定池U中的數(shù)據(jù)進(jìn)行聚類。這樣可以有效避免因初始文本長(zhǎng)度較短、信息量較少而使簇的初始中心不準(zhǔn)確的問(wèn)題。算法流程如圖4所示，偽代碼如圖5所示。

圖4 加入文本待定池的SP算法流程

圖5 改進(jìn)的SP聚類算法偽代碼

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)數(shù)據(jù)與評(píng)價(jià)指標(biāo)

本文使用中文分析語(yǔ)料庫(kù)中京東和攜程網(wǎng)上采集到的評(píng)價(jià)數(shù)據(jù)，包括書(shū)籍、衣服、計(jì)算機(jī)、酒店、平板、水果、洗發(fā)水、牛奶、手機(jī)8種類別共62 774條文本作為原始數(shù)據(jù)。原始數(shù)據(jù)中存在大量噪聲信息，為了使聚類的質(zhì)量有所提高，對(duì)其進(jìn)行篩選，刪除噪聲數(shù)據(jù)后，最終選用書(shū)籍、衣服、計(jì)算機(jī)、酒店4種類別各1 000條數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。

為了節(jié)省算法運(yùn)行空間，提高運(yùn)行速度，使用Jieba分詞對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行處理。將分詞之后對(duì)文檔貢獻(xiàn)值較小的助詞、語(yǔ)氣詞等“停用詞”剔除。

使用準(zhǔn)確率(P)、召回率(R)和F1值作為分類效果好壞的評(píng)價(jià)指標(biāo)。其中

(5)

準(zhǔn)確率、召回率越高，F(xiàn)1值越大，說(shuō)明模型的效果越好。

4.2 對(duì)比實(shí)驗(yàn)

4.2.1 SP聚類算法對(duì)比實(shí)驗(yàn)

將CWMD分別與傳統(tǒng)的SP聚類算法和改進(jìn)的SP聚類算法相結(jié)合，進(jìn)行文本聚類實(shí)驗(yàn)，使用F1值作為評(píng)價(jià)指標(biāo)，實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 改進(jìn)前后SP聚類算法實(shí)驗(yàn)效果對(duì)比

從圖6可以看出，改進(jìn)后的SP算法 4類文本的F1均值提高了35.52%，聚類的效果有了明顯提升。

4.2.2 距離標(biāo)準(zhǔn)對(duì)比實(shí)驗(yàn)

使用改進(jìn)的SP算法，將CWMD、余弦距離和歐氏距離分別作為其聚類標(biāo)準(zhǔn)進(jìn)行實(shí)驗(yàn)，F(xiàn)1值作為評(píng)價(jià)指標(biāo)，實(shí)驗(yàn)結(jié)果如圖7所示。

圖7 使用不同距離標(biāo)準(zhǔn)的實(shí)驗(yàn)效果對(duì)比

從圖7可以看出，當(dāng)文本數(shù)據(jù)集相同時(shí)，使用CWMD作為聚類標(biāo)準(zhǔn)的算法效果最好，4類文本的F1均值比使用歐氏距離、余弦距離作為聚類標(biāo)準(zhǔn)分別提高了19.25%、14.45%。使用相同的距離標(biāo)準(zhǔn)進(jìn)行聚類時(shí)，不同類別的文本效果略有差異，主要是受文本數(shù)據(jù)本身的影響。

5 應(yīng)用實(shí)例

將CWMD與改進(jìn)的SP相結(jié)合的聚類算法應(yīng)用到微博文本中，進(jìn)行話題發(fā)現(xiàn)分析。

5.1 微博數(shù)據(jù)采集以及文本聚類

本文采用Python語(yǔ)言對(duì)微博進(jìn)行網(wǎng)絡(luò)爬蟲(chóng)，采集到了2020-8-25至2020-9-1期間部分微博數(shù)據(jù)，共計(jì)2萬(wàn)余條，包括博主的ID、昵稱、博文、發(fā)布時(shí)間以及發(fā)布終端等。將獲取到的博文進(jìn)行文本預(yù)處理，去除噪音和一些特殊符號(hào)等。之后進(jìn)行Jieba分詞，去除停用詞并對(duì)數(shù)據(jù)作向量化表示。將處理后的數(shù)據(jù)結(jié)果輸入CWMD和改進(jìn)的SP聚類模型中。

5.2 聚類結(jié)果分析

針對(duì)聚類結(jié)果，根據(jù)包含文本數(shù)量取前3個(gè)話題簇，對(duì)其提取關(guān)鍵詞，將關(guān)鍵詞和微博官網(wǎng)提供的熱點(diǎn)話題進(jìn)行對(duì)比，從而驗(yàn)證聚類后話題詞與現(xiàn)實(shí)微博話題的一致性，結(jié)果如表1所示。

表1 微博文本聚類結(jié)果與熱搜話題對(duì)比

最右側(cè)一欄的3個(gè)話題是在數(shù)據(jù)采集時(shí)間段中新浪微博的熱搜話題。該時(shí)段正值國(guó)內(nèi)疫情放緩，國(guó)民經(jīng)濟(jì)復(fù)蘇，“澳門發(fā)放2.9億元消費(fèi)券吸引內(nèi)地游客”話題引起人們的廣泛關(guān)注，網(wǎng)民就此開(kāi)展廣泛討論。從聚類結(jié)果可以看出，“消費(fèi)”、“澳門”、“內(nèi)地”等詞是文本簇中的關(guān)鍵詞，這些詞與實(shí)際的熱搜話題緊密相關(guān)。在“非全研究生考教師被取消資格”話題中，網(wǎng)民就全日制和非全日制產(chǎn)生的學(xué)歷歧視問(wèn)題進(jìn)行討論?？梢钥闯?，每個(gè)文本簇提取到的關(guān)鍵詞和微博實(shí)際熱搜話題聯(lián)系緊密，證明本文提出的聚類模型可以較好地應(yīng)用到微博話題檢測(cè)中。

6 結(jié)束語(yǔ)

本文針對(duì)傳統(tǒng)的微博話題檢測(cè)中文本向量高維稀疏且無(wú)關(guān)鍵詞信息等缺陷，將Word2vec模型訓(xùn)練好的詞向量進(jìn)行TF-IDF加權(quán)表示，引入CWMD距離計(jì)算文本之間的差距。并且采用改進(jìn)的SP增量聚類的方式進(jìn)行最終的文本聚類。對(duì)有標(biāo)簽評(píng)論數(shù)據(jù)的實(shí)驗(yàn)結(jié)果表明，本文提出的聚類模型比傳統(tǒng)的聚類模型效果更好。在此基礎(chǔ)上，對(duì)爬取到的無(wú)標(biāo)簽微博文本進(jìn)行處理，將聚類結(jié)果與微博官方熱搜話題進(jìn)行比對(duì)，證實(shí)了聚類結(jié)果的有效性。下一步將增加爬取微博的時(shí)間跨度，進(jìn)行更全面的話題發(fā)現(xiàn)。