基于情節(jié)記憶的高效短文本流聚類算法

劉子健，王勇，劉媛妮，周由勝，

（1.重慶郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，重慶 400065；2.大唐微電子技術(shù)有限公司，北京 100094；3.重慶郵電大學(xué) 網(wǎng)絡(luò)空間安全與信息法學(xué)院，重慶 400065）

0 概述

隨著互聯(lián)網(wǎng)技術(shù)的快速發(fā)展，社交媒體平臺(tái)上每天都涌現(xiàn)出海量的短文本數(shù)據(jù)，例如微博、Twitter、新聞網(wǎng)站等。隨著時(shí)間推移這些源源不斷產(chǎn)生的短文本數(shù)據(jù)形成了短文本流。近年來(lái)，短文本流聚類受到較多的關(guān)注，廣泛應(yīng)用于熱點(diǎn)話題檢測(cè)［1］、事件檢測(cè)與追蹤［2］、新聞推薦［3］等任務(wù)。但由于短文本流具有無(wú)限長(zhǎng)、特征稀疏、多歧義、主題演化等特性，對(duì)其進(jìn)行聚類仍是一個(gè)很大的挑戰(zhàn)。

與K-means［4］、高斯混合模型［5］、譜聚類［6］等傳統(tǒng)聚類算法不同，流聚類算法根據(jù)所采用的技術(shù)可分為基于相似度的流聚類算法和基于模型的流聚類算法。基于相似度的短文本流聚類算法大多使用向量空間模型來(lái)表示文檔，通過(guò)相似度度量計(jì)算文檔和聚類之間的相似度，再根據(jù)相似度閾值將文檔分配給現(xiàn)有聚類或新的聚類。CluStream［7］是經(jīng)典的短文本流聚類算法，包括在線微聚類階段和離線宏聚類階段，使用金字塔時(shí)間框架存儲(chǔ)不同時(shí)刻的歷史微集群，使用改進(jìn)的K-means 算法在微集群上進(jìn)行聚類，獲得用戶指定數(shù)量為K的宏集群。之后提出的很多流聚類算法都借鑒了這個(gè)框架。DenStream［8］將微聚類與用于流聚類的密度估計(jì)過(guò)程相結(jié)合，能夠在線對(duì)離群值和真實(shí)數(shù)據(jù)進(jìn)行區(qū)分，形成任何形狀的數(shù)據(jù)聚類。SHOU等［9］建立一個(gè)持久摘要模型Sumblr，在Twitter文本流中將Tweet壓縮成Tweet 特征向量（TCVs）并進(jìn)行在線維護(hù)，模型根據(jù)TCVs 的統(tǒng)計(jì)信息將未來(lái)的Tweet 分配到聚類。MStream［10］計(jì)算文檔屬于現(xiàn)有集群和新集群的概率，并根據(jù)這些概率將文檔分配給現(xiàn)有集群或新集群，無(wú)須設(shè)置相似度閾值，能更自然地檢測(cè)新集群并處理概念漂移問(wèn)題。RAKIB等［11］提出一種利用文本中高頻的biterm 項(xiàng)對(duì)每批文本中的小部分文本進(jìn)行聚類的方法，然后利用獲得的聚類分配填充MStream 算法的聚類模型，使用基于統(tǒng)計(jì)度量的相似度閾值進(jìn)行文本分配，在緩解概念漂移問(wèn)題的同時(shí)提升了聚類效率?；谙嗨贫鹊牧骶垲愃惴ù蠖噙\(yùn)行速度較快、實(shí)時(shí)性較好，局限性在于需要手動(dòng)設(shè)置閾值以確定在線文檔的主題分配以及難以處理文本稀疏問(wèn)題。

近幾年，越來(lái)越多的研究人員對(duì)基于模型的短文本流聚類算法進(jìn)行研究。MStream［10］是一種基于狄利克雷多項(xiàng)式混合模型的短文本流聚類算法，該算法使用了兩個(gè)狄利克雷先驗(yàn)α和β，其中，α是指文本選擇新集群的先驗(yàn)概率，β對(duì)應(yīng)于文本選擇與共享比其他集群更相似內(nèi)容集群的先驗(yàn)概率，該算法的變體為MStreamF（刪除舊群體）。DP-BMM［12］是一種基于比特?cái)?shù)的短文本流聚類混合算法，與MStreamF 類似，該算法的變體為DP-BMM-FP（刪除以前批次中獲得的聚類）。OSDM［13］是一種基于語(yǔ)義增強(qiáng)狄利克雷模型的短文本流聚類算法，它擴(kuò)展了MStream 算法，整合了文本和集群之間的常用詞，從中獲得單詞的語(yǔ)義信息，并使用該語(yǔ)義信息計(jì)算文本和集群之間的相似性。DCT-L［14］是一種基于狄利克雷多項(xiàng)式混合模型的短文本流動(dòng)態(tài)聚類算法，它在一個(gè)特定的時(shí)間戳內(nèi)為每個(gè)短文本分配一個(gè)主題（即集群），并使用產(chǎn)生的主題分布作為推斷后續(xù)文檔主題的優(yōu)先級(jí)。OSGM［15］在計(jì)算文本分配概率中引入詞共現(xiàn)語(yǔ)義信息，在線地在詞匯變化的子空間中動(dòng)態(tài)維護(hù)不斷變化的活動(dòng)主題，并且無(wú)須通過(guò)外部資源來(lái)處理術(shù)語(yǔ)歧義問(wèn)題。LAST［16］是一個(gè)終身學(xué)習(xí)增強(qiáng)短文本流聚類算法，在基于模型的流聚類算法上增加了情節(jié)記憶模塊，使得聚類算法同時(shí)保持基于批處理和基于單遍處理的優(yōu)點(diǎn)?；谀Ｐ偷亩涛谋玖骶垲愃惴僭O(shè)文檔是由一個(gè)混合模型生成的，這個(gè)混合模型通過(guò)選擇一定概率的主題，再?gòu)倪@個(gè)主題中選擇一定概率的單詞生成文檔，通常使用吉布斯采樣［17］或EM 算法［18］來(lái)估計(jì)混合模型的參數(shù)，局限性在于需要預(yù)先指定主題數(shù)量，不能處理短文本流中不斷發(fā)展的未知數(shù)量的主題。

本文提出一種帶情節(jié)記憶的短文本流聚類算法。該算法由兩個(gè)階段組成：在線聚類和離線聚類。在線聚類階段將情節(jié)記憶思想［19］融入聚類算法，通過(guò)稀疏經(jīng)驗(yàn)重放增強(qiáng)聚類的特征表示，使得未來(lái)文本以更大的概率選擇最近的聚類，并采用反向索引計(jì)算文本和選定聚類的相似度并分配文檔到現(xiàn)有聚類或新的聚類，通過(guò)動(dòng)態(tài)閾值處理概念漂移問(wèn)題。離線聚類階段采用目前最優(yōu)的聚類增強(qiáng)算法進(jìn)行優(yōu)化，并通過(guò)語(yǔ)義再分配算法處理歧義問(wèn)題，同時(shí)根據(jù)聚類id 對(duì)過(guò)時(shí)聚類進(jìn)行刪減。

1 基礎(chǔ)知識(shí)

1.1 情景記憶模塊與稀疏經(jīng)驗(yàn)重放

情景記憶模塊［19］用于在內(nèi)存中存儲(chǔ)一些之前處理過(guò)的文本。由于內(nèi)存有限，選擇在一定更新間隔內(nèi)將新文本寫入內(nèi)存。算法在內(nèi)存中維護(hù)一個(gè)情節(jié)記憶模塊，如圖1 所示，當(dāng)連續(xù)到達(dá)的文檔數(shù)量達(dá)到存儲(chǔ)間隔時(shí)，就把當(dāng)前文本添加到情節(jié)記憶模塊。由于文本流中的文本是按順序到達(dá)的，最開(kāi)始存入的文本具有更高的過(guò)時(shí)性，因此當(dāng)情節(jié)記憶模塊的大小超過(guò)了設(shè)置的最大值時(shí)，則從后往前刪除文本，以保持記憶模塊中存儲(chǔ)最近的一些文本數(shù)據(jù)。

圖1 情節(jié)記憶模塊結(jié)構(gòu)Fig.1 Structure of episodic memory module

在聚類過(guò)程中，每經(jīng)過(guò)一定的更新間隔從情節(jié)記憶模塊中選擇文本進(jìn)行經(jīng)驗(yàn)重放。經(jīng)驗(yàn)重放將有助于利用過(guò)去的文本信息更新這些主題的特征向量，增大這些主題在聚類過(guò)程中被選中的概率。但將記憶模塊中的文本全部用來(lái)經(jīng)驗(yàn)重放，一方面增加了時(shí)間和空間的開(kāi)銷，另一方面太多不相關(guān)的文本也會(huì)影響聚類結(jié)果，因此隨機(jī)抽取記憶模塊中的部分文本進(jìn)行稀疏經(jīng)驗(yàn)重放。當(dāng)?shù)竭_(dá)重放間隔時(shí)，在情節(jié)記憶模塊中隨機(jī)抽取數(shù)量為E的文本，并對(duì)其進(jìn)行一次掃描聚類。對(duì)這些過(guò)去已經(jīng)處理的文本都只選擇一個(gè)已經(jīng)存在的聚類而不是產(chǎn)生一個(gè)新聚類。在確定聚類后需要更新聚類對(duì)應(yīng)的詞匯特征和語(yǔ)義表示。重放文本用t表示，更新聚類詞匯特征過(guò)程如式（1）～式（3）所示，更新聚類語(yǔ)義表示過(guò)程如式（4）和式（5）所示。

其中：nz，f是聚類z中的特征f對(duì)應(yīng)的頻率；Nt，f是重放文本t中的特征f對(duì)應(yīng)的頻率；nz是聚類z的特征數(shù)量；Nt是文本t的特征數(shù)量；mz是聚類z的文本數(shù)量；Sz是聚類z的聚類向量；St是文本t的語(yǔ)義向量；Sz，m是聚類z的聚類中心向量。

1.2 反向索引

在線聚類階段先在內(nèi)存中生成聚類id-特征正向索引，再通過(guò)正向索引創(chuàng)建反向索引，如圖2 所示。算法通過(guò)反向索引能夠找到包括同一特征的聚類id。反向索引由向量I={lf，id}表示，其中，lf，id是聚類特征中包括特征f的聚類id 集合。通過(guò)計(jì)算當(dāng)前文本和選定具有共同特征聚類的相似度進(jìn)行聚類。使用反向索引減少文本相似度計(jì)算次數(shù)，提高算法運(yùn)行效率。

2 基于情節(jié)記憶的短文本流聚類算法

所提算法主要包括在線聚類和離線聚類兩個(gè)階段。整個(gè)算法流程如圖3 所示，其中，T表示當(dāng)前模型的運(yùn)行時(shí)間，UI 表示離線聚類算法運(yùn)行的更新間隔，通過(guò)取余在UI 內(nèi)執(zhí)行離線聚類算法。在線聚類階段包括特征提取、相似度計(jì)算、構(gòu)建聚類模型以及情節(jié)記憶模塊；離線聚類階段包括增強(qiáng)聚類、語(yǔ)義再分配和刪除過(guò)時(shí)聚類。

圖3 算法整體流程Fig.3 Overall procedure of the algorithm

從詞匯特征和語(yǔ)義兩個(gè)層面進(jìn)行文本特征提取。使用biterm［20］對(duì)文本進(jìn)行詞匯層面特征提取。與biterm 類似的還有unigram 和bigram。unigram 將單個(gè)單詞作為一個(gè)特征，而bigram 是將連續(xù)的兩個(gè)單詞作為一個(gè)特征。biterm 對(duì)文本預(yù)處理后的文本進(jìn)行分詞，然后計(jì)算單詞列表的笛卡爾積，能夠更加全面地提取文本中的詞匯特征，提取出的特征數(shù)量比其他方法更多。對(duì)于單詞數(shù)量為k的句子，特征數(shù)量為(k×(k-1))/2。特征提取過(guò)程如式（6）所示：

通過(guò)詞平均法構(gòu)建文檔向量表示文本語(yǔ)義信息，其中詞向量可以通過(guò)GloVe 模型［21］獲得。每個(gè)聚類的詞匯特征通過(guò)一個(gè)向量F表示，F(xiàn)={nz，f，nz，mz，iid，z}，其中，nz，f是聚類z中的特征f對(duì)應(yīng)的頻率，nz是聚類z的特征數(shù)量，mz是聚類z的文本數(shù)量，iid，z是聚類z的唯一id。每個(gè)聚類的語(yǔ)義表示由聚類向量Sz和聚類中心向量Sz，m組成。Sz為聚類z中文本的文檔向量求和。Sz，m由聚類向量除以聚類大?。ㄍㄟ^(guò)聚類中的文本數(shù)量mz表示）計(jì)算得到。

2.1 在線聚類階段

在線聚類階段基于單遍處理的方法。先對(duì)當(dāng)前文本進(jìn)行預(yù)處理和特征提取，如果已處理的文本數(shù)量達(dá)到了經(jīng)驗(yàn)重放間隔R，則隨機(jī)選取數(shù)量為E的文本進(jìn)行稀疏經(jīng)驗(yàn)重放更新聚類特征，再對(duì)當(dāng)前文本進(jìn)行聚類。聚類過(guò)程根據(jù)反向索引選擇現(xiàn)有包含該文本特征的聚類，計(jì)算文本和選取聚類的相似度，基于統(tǒng)計(jì)度量的動(dòng)態(tài)相似度閾值將文本分配到新的聚類或者是現(xiàn)有聚類中。如果處理文本數(shù)量達(dá)到了存儲(chǔ)間隔T，則將當(dāng)前文本加入情節(jié)記憶模塊，并且根據(jù)設(shè)置的內(nèi)存大小判斷是否刪除舊文本。

2.1.1 文本與聚類相似度計(jì)算

采取基于共同特征的相似度計(jì)算公式計(jì)算文本和聚類之間的相似度，計(jì)算公式如式（7）所示：

其中：Nt，f為文本t的特征f對(duì)應(yīng)的頻率；Nt為文本t的特征總數(shù)。

首先對(duì)文本t和聚類z之間共同的特征f對(duì)應(yīng)的頻率求和，然后再乘上一個(gè)類似于逆文檔頻率（Inverse Document Frequency，IDF）的權(quán)重Df，計(jì)算公式如式（8）所示：

其中：|z|為存在的聚類總數(shù)；|f∈z|為包含特征f的聚類數(shù)量；Df的大小能夠反映特征f的重要性。

如果特征f在聚類中越多出現(xiàn)，那么該特征的重要性越低。

2.1.2 聚類模型構(gòu)建

當(dāng)文本t被分配到聚類z時(shí)更新聚類z的F向量，構(gòu)建過(guò)程如式（1）～式（5）所示。如果當(dāng)前文本沒(méi)有被分配到一個(gè)新的聚類，那么iid，z保持不變，否則iid，z自增1，因此最近創(chuàng)建的聚類擁有最高的聚類id。同時(shí)，更新反向索引I，對(duì)于文本中的每個(gè)特征添加聚類id 到相應(yīng)的F特征向量中。語(yǔ)義向量更新和文本分配過(guò)程如式（9）所示：

算法1在線聚類算法

輸入文本流、重放間隔R、重放文本數(shù)量E、寫入模塊更新間隔T

輸出每個(gè)文本的聚類標(biāo)簽ZSt

1.for t=1 to ∞ do//從短文本流開(kāi)始

2.if t % R=0 then//執(zhí)行稀疏經(jīng)驗(yàn)重放

3.從M 中隨機(jī)選取文本集E

4.通過(guò)式（1）和式（2）執(zhí)行稀疏經(jīng)驗(yàn)重放

5.通過(guò)式（1）～式（5）更新聚類模型M

6.end if

7.通過(guò)式（6）提取文本特征

8.通過(guò)反向索引I 得到與St有相同特征的聚類集L

9.通過(guò)式（7）計(jì)算St和L 中聚類的相似度Siml

10.計(jì)算Siml中的最大相似度maxl、相似度均值μl和方差σl

11.if maxl＞ μl+σlthen

12.j=cluster index for maxl//獲取maxl對(duì)應(yīng)的聚類標(biāo)簽

13.ZSt=jth//分配文本聚類標(biāo)簽

14.else

15.分配該文本到一個(gè)新聚類

16.end if

17.通過(guò)式（1）～式（5）更新聚類模型M

18.if t % T=0 then

19.把當(dāng)前文本St寫入情節(jié)記憶模塊M

20.end if

21.return ZSt

2.2 離線聚類階段

在每個(gè)更新間隔內(nèi)進(jìn)行離線聚類。離線聚類階段主要包括聚類增強(qiáng)、語(yǔ)義再分配、過(guò)時(shí)聚類刪除3步。

2.2.1 聚類增強(qiáng)

在每個(gè)更新間隔內(nèi)選擇一組在線聚類模塊獲得的聚類，對(duì)這些聚類的分布進(jìn)行增強(qiáng)。聚類的大小對(duì)應(yīng)聚類中文本的數(shù)量，選擇聚類大小大于μ+σ的聚類，μ和σ分別為在線聚類結(jié)果中所有聚類大小的平均值和方差。文本數(shù)量較大的聚類具有更多的異常值，這可能導(dǎo)致未來(lái)文本的不正確分配。通過(guò)增強(qiáng)較大聚類中的文本分布，將未來(lái)文本分配到合適的聚類。采用目前較優(yōu)的聚類增強(qiáng)算法［22］，該算法通過(guò)迭代分類進(jìn)行聚類增強(qiáng)，每次迭代生成分別包含非異常值和異常值的訓(xùn)練集和測(cè)試集，使用訓(xùn)練集訓(xùn)練分類算法，再使用訓(xùn)練好的模型對(duì)測(cè)試集進(jìn)行分類，重復(fù)迭代直到每個(gè)聚類中文本分布趨于穩(wěn)定或者達(dá)到預(yù)設(shè)的最大迭代次數(shù)。另外，該聚類增強(qiáng)算法的質(zhì)量在很大程度上取決于初始聚類質(zhì)量（對(duì)應(yīng)所提算法在線聚類階段的結(jié)果），具體算法過(guò)程參考文獻(xiàn)［22］。

2.2.2 語(yǔ)義再分配

單文本聚類（只包含一個(gè)文本的聚類）中的文本與其他聚類沒(méi)用共享的詞匯特征，但這些聚類可能在語(yǔ)義上與其他現(xiàn)有聚類類似，選擇這些文本重新分配至其他現(xiàn)有的聚類。通過(guò)余弦相似度計(jì)算文本和聚類中心的語(yǔ)義相似度，再分別計(jì)算相似度的均值μ和方差σ，如果最大的相似度值大于μ+σ，則將該文本分配到對(duì)應(yīng)的聚類，否則仍然在原來(lái)通過(guò)在線聚類階段得到的聚類中。在進(jìn)行語(yǔ)義分配后，需要同時(shí)更新聚類的詞匯特征表示以及語(yǔ)義表示。

算法2語(yǔ)義再分配算法

輸入聚類大小為1 的聚類文本集合T、詞向量字典D、聚類的語(yǔ)義特征集合字典｛Sz，Sz，m｝、文本語(yǔ)義特征向量和SSUM（初始化為0 向量）

輸出聚類模型M

1.for t in T do

2.對(duì)文本t 進(jìn)行預(yù)處理得到單詞列表Wt

3.for w in Wtdo

4.SSUM=SSUM+D(w)

8.計(jì)算Simt中的最大相似度maxt、相似度均值μt和方差σt

9.if maxt＞ μt+σtthen

10.獲取maxt對(duì)應(yīng)的聚類標(biāo)簽j

11.ZSt=j//修改當(dāng)前文本聚類標(biāo)簽為j

12.通過(guò)式（1）～式（5）更新聚類模型并刪除原始聚類中的文本t

13.else

14.文本t 保留在原始聚類中

15.end for

2.2.3 過(guò)時(shí)聚類刪除

根據(jù)聚類編號(hào)iid，z以及聚類大小來(lái)刪除過(guò)時(shí)聚類，根據(jù)在線聚類算法最近創(chuàng)建的聚類擁有更高的iid，z，分別計(jì)算聚類編號(hào)和聚類大小的均值μz、μm和方差σz、σm，刪除聚類編號(hào)idz小于μz-σz并且聚類大小小于μm-σm的聚類對(duì)應(yīng)的F向量和反向索引I中該聚類的信息。

算法3過(guò)時(shí)聚類刪除算法

輸入聚類id 集合{iid，z，z∈Z}、聚類大小集合{mz，z∈Z}

輸出聚類模型M

1.計(jì)算iid，z和mz的均值μz、μm和方差σz、σm

2.for z in F do

3.if iid，z＜μz-σzand mz＜μm-σmthen

4.Delete Fidzand reverse index lf，idz//刪除過(guò)時(shí)聚類的特//征向量以及反向索引中該聚類信息

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

3.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

實(shí)驗(yàn)環(huán)境為Windows 10 64 位操作系統(tǒng)，處理器為AMD Ryzen 7 4800H CPU，內(nèi)存為16.00 GB。使用PyCharm 2021 實(shí)現(xiàn)所提算法，調(diào)用Python 的Sklearn 包進(jìn)行指標(biāo)統(tǒng)計(jì)。在實(shí)驗(yàn)中使用3 個(gè)公開(kāi)的短文本數(shù)據(jù)集。News-T［23］和Tweets-T［10］數(shù)據(jù)集分別包含11 109 個(gè)新聞標(biāo)題和30 322 篇推文，它們分別有152 和269 個(gè)類別。NT［11］數(shù)據(jù)集是News-T 數(shù)據(jù)集和Tweets-T 數(shù)據(jù)集的結(jié)合，包括41 429 篇文本和416 個(gè)類別，文檔的平均長(zhǎng)度為7.97。文本預(yù)處理包括將所有字母轉(zhuǎn)化成小寫字母、刪除停用詞以及詞干提取。表1 顯示了這些短文本數(shù)據(jù)集預(yù)處理之后的統(tǒng)計(jì)數(shù)據(jù)，從平均單詞數(shù)可以看出這3 個(gè)數(shù)據(jù)集適用于短文本流聚類。在實(shí)驗(yàn)時(shí)對(duì)數(shù)據(jù)集進(jìn)行混亂處理，以檢驗(yàn)不同算法在處理順序隨機(jī)且不同主題的文本到達(dá)時(shí)的算法質(zhì)量。

表1 實(shí)驗(yàn)數(shù)據(jù)集基本統(tǒng)計(jì)信息Table 1 Basic statistical information of experimental data sets 單位：個(gè)

3.2 評(píng)價(jià)指標(biāo)

使用4 種廣泛使用的度量指標(biāo)來(lái)評(píng)估聚類性能：歸一化互信息（Normalized Mutual Information，NMI），準(zhǔn)確率（A），同質(zhì)性（h）和V-Measure（V）［24］。

NMI 用于評(píng)價(jià)整體聚類質(zhì)量，代表聚類分配和文檔實(shí)際分配組的隨機(jī)變量共享的統(tǒng)計(jì)信息數(shù)量。NMI 定義如下：

其中：nc是類別c中文檔的數(shù)量；nk是聚類k中文檔的數(shù)量；nc，k是既在類別c又在聚類k中的文檔數(shù) 量；N是數(shù)據(jù)集中文檔的數(shù)量。NMI 越接近1，意味著聚類質(zhì)量越高。

準(zhǔn)確率用于將聚類結(jié)果與數(shù)據(jù)的實(shí)際類別進(jìn)行比較，測(cè)量了所有聚類中正確分配的文檔所占的比率。準(zhǔn)確率定義如下：

其中：ki和ci分別表示xi對(duì)應(yīng)的聚類結(jié)果和真實(shí)標(biāo)簽；δ表示指示函數(shù)；map 函數(shù)表示最佳類別標(biāo)記的重現(xiàn)分配，以保證統(tǒng)計(jì)結(jié)果的正確。一般通過(guò)匈牙利算法［25］實(shí)現(xiàn)最佳重分配，從而在多項(xiàng)式時(shí)間內(nèi)求解標(biāo)簽分配問(wèn)題。準(zhǔn)確率越高，意味著聚類效果越好。

同質(zhì)性表示算法從真值組的同一類中獲得的聚類成員所占的比例，定義如下：

其中：H(C|K)是給定集群劃分條件下類別劃分的條件熵；H(C)是類別劃分的熵；n表示實(shí)例總數(shù)；nc表示類別c下的實(shí)例數(shù)；nk表示集群k下的實(shí)例數(shù)；nc，k表示類別c中被劃分到集群k的實(shí)例數(shù)。

V-Measure 基于兩個(gè)類別之間的條件熵，也就是求已知某一個(gè)類別劃分后，另外一個(gè)類別劃分的不確定性程度。不確定性越小，意味著兩個(gè)類別劃分越接近，相應(yīng)h值或c值越大。完整性衡量了屬于同一個(gè)真實(shí)類別的樣本都被分配到同一個(gè)簇中的比例的加權(quán)平均值。V-Measure 是同質(zhì)性和完整性的調(diào)和平均值，定義如下：

3.3 結(jié)果分析

將所提算法與以下基準(zhǔn)算法進(jìn)行比較：

1）MStream，基于狄利克雷多項(xiàng)式混合模型的短文本流聚類算法有基于批處理和基于單遍處理的兩種變體。基于批處理的方法對(duì)每一批短文本進(jìn)行聚類，存儲(chǔ)一段時(shí)間內(nèi)產(chǎn)生的所有聚類。通過(guò)對(duì)同一批文本多次進(jìn)行吉布斯采樣，提高初始聚類結(jié)果。基于單遍處理的方法只對(duì)文本進(jìn)行一次聚類。

2）MStreamF，是MStream 的一個(gè)帶有遺忘規(guī)則的變體，只保留有限時(shí)間范圍內(nèi)的最新文本，刪除以前批次的過(guò)時(shí)聚類。本文采用基于批處理模式的MStream 和MStreamF 算法進(jìn)行實(shí)驗(yàn)，并采用原始論文中MStream 和MStreamF 算法的參數(shù)（α=0.03、β=0.03）。

3）OSDM，基于單遍處理的短文本流聚類算法，將詞形語(yǔ)義信息集成到MStream 算法，以消除短文本流聚類中的術(shù)語(yǔ)歧義問(wèn)題。本文采用原始論文中的參數(shù)進(jìn)行實(shí)驗(yàn)（α=2×10-3、β=4×10-5、γ=6×10-6)。

4）DP-BMM，采用與MStream 算法類似的方法，利用每個(gè)文檔構(gòu)造的詞來(lái)增強(qiáng)短文本中的單詞共現(xiàn)模式。與MStream 算法的區(qū)別在于，DP-BMM 采用基于biterm 的聚類方法。本文采用原論文中的DPBMM 算法參數(shù)進(jìn)行實(shí)驗(yàn)（α=0.03、β=0.03）。

5）EStream，采用在線和離線兩個(gè)階段進(jìn)行短文本流聚類，并且通過(guò)反向索引計(jì)算文本和選定聚類相似度。EStream 算法的參數(shù)只有一個(gè)UI，實(shí)驗(yàn)中UI 設(shè)置為500。

將所提算法和以上基準(zhǔn)算法進(jìn)行比較。為了減少誤差，對(duì)每個(gè)數(shù)據(jù)集取10 次實(shí)驗(yàn)結(jié)果的平均值作為最終結(jié)果。表2 給出了所提算法與其他算法在3 個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，其中部分實(shí)驗(yàn)結(jié)果來(lái)源于文獻(xiàn)［11］，不同數(shù)據(jù)集的最優(yōu)結(jié)果用加粗字體標(biāo)示。從實(shí)驗(yàn)結(jié)果來(lái)看，所提算法相比于其他算法具有一定的性能優(yōu)勢(shì)，在3 個(gè)數(shù)據(jù)集上多項(xiàng)評(píng)價(jià)指標(biāo)都高于EStream，證明了改進(jìn)后的流聚類算法結(jié)合情節(jié)記憶模塊的有效性。值得注意的是，所提算法在News-T 數(shù)據(jù)集上的歸一化互信息指標(biāo)沒(méi)達(dá)到最優(yōu)，可能的原因是該數(shù)據(jù)集的數(shù)據(jù)量偏小，導(dǎo)致在進(jìn)行經(jīng)驗(yàn)重放時(shí)能夠增強(qiáng)的聚類表示較少。相比之下，DP-BMM 和MStreamF 進(jìn)行了超參數(shù)調(diào)優(yōu)，更好地實(shí)現(xiàn)了將文本分配到不同聚類。但是在NT 數(shù)據(jù)集上，所提算法的歸一化互信息、同質(zhì)性、準(zhǔn)確率指標(biāo)明顯高于其他算法，可能的原因是其他算法并沒(méi)有在NT數(shù)據(jù)集上進(jìn)行超參數(shù)調(diào)優(yōu)，而所提算法使用經(jīng)驗(yàn)重放緩解文本流稀疏性問(wèn)題，并且通過(guò)參數(shù)影響實(shí)驗(yàn)得到最佳的重放間隔和重放數(shù)量。

表2 各算法在3 個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果Table 2 Experimental results of each algorithm on three data sets

另外，對(duì)比所提算法和其他算法的平均運(yùn)行時(shí)間，實(shí)驗(yàn)結(jié)果如表3 所示。由表3 可知，所提算法比MStream、MStreamF、DP-BMM、OSDM 算法的運(yùn)行時(shí)間更短，證明了所提算法通過(guò)反向索引優(yōu)化聚類運(yùn)行效率的有效性。DP-BMM 算法的運(yùn)行時(shí)間最長(zhǎng)，可能的原因是該算法在每個(gè)聚類中存儲(chǔ)了該聚類所有文本的biterm項(xiàng)，使用吉布斯采樣選取聚類，而對(duì)同一文本多次執(zhí)行吉布斯采樣是一項(xiàng)很耗時(shí)的操作。假設(shè)文本數(shù)量為M，聚類數(shù)量為K，每個(gè)文本的單詞個(gè)數(shù)為L(zhǎng)，執(zhí)行吉布斯采樣的次數(shù)為I，那么DP-BMM 算法的時(shí)間復(fù)雜度為O(IKML)。由于所提算法包括情節(jié)記憶模塊和稀疏經(jīng)驗(yàn)重放，整體聚類次數(shù)得到了增加，因此運(yùn)行時(shí)間比EStream 算法略長(zhǎng)。在線聚類階段計(jì)算的是當(dāng)前文本和選定聚類的相似度，假設(shè)每次運(yùn)行需要挑選聚類個(gè)數(shù)為c，稀疏經(jīng)驗(yàn)重放的數(shù)量為E，因?yàn)樵诰€聚類對(duì)當(dāng)前文本只須執(zhí)行一次，只有產(chǎn)生重放才會(huì)再次執(zhí)行聚類，所以所提算法的時(shí)間復(fù)雜度為O((M+E)×cLL)。本文忽略了離線聚類階段的運(yùn)行時(shí)間，因?yàn)殡x線聚類階段只會(huì)對(duì)一小部分文本進(jìn)行再次聚類。

表3 不同算法的平均運(yùn)行時(shí)間Table 3 Average running time of different algorithms 單位：s

3.4 消融實(shí)驗(yàn)

本節(jié)主要分析內(nèi)存大小M、重放間隔R和重放文本數(shù)量E對(duì)算法性能的影響。參照EStream 算法設(shè)置在線階段和離線階段的更新間隔為500。采用控制變量法進(jìn)行實(shí)驗(yàn)。

3.4.1 內(nèi)存大小對(duì)算法性能的影響

內(nèi)存大小是指情節(jié)記憶模塊中存儲(chǔ)的文本數(shù)量。圖4 顯示了在News-T、Tweets-T、NT 數(shù)據(jù)集上不同的內(nèi)存大小對(duì)NMI 的影響。由圖4 可以看出，隨著內(nèi)存大小的不斷增大，NMI 數(shù)值總體而言也不斷增大。因?yàn)榍楣?jié)記憶模塊中存放著較多的最近文本，更有助于利用過(guò)去的文本信息更新主題的特征向量，但內(nèi)存大小并不是越大越好，可通過(guò)驗(yàn)證集來(lái)設(shè)置一個(gè)適合的數(shù)值。

圖4 內(nèi)存大小對(duì)歸一化互信息指標(biāo)的影響Fig.4 Influence of the memory size on the normalized mutual information index

3.4.2 重放間隔對(duì)算法性能的影響

重放間隔是指稀疏經(jīng)驗(yàn)重放的文本數(shù)量間隔。圖5 顯示了在News-T、Tweets-T、NT 數(shù)據(jù)集上不同的重放間隔對(duì)NMI 的影響。由圖5 可以看出，隨著重放間隔的增加，NMI 大體呈現(xiàn)下降趨勢(shì)，可能的原因是一些聚類的特征會(huì)隨著時(shí)間慢慢減少。過(guò)小的重放間隔會(huì)使得聚類時(shí)間變長(zhǎng)，而過(guò)大的重放間隔會(huì)使得算法的性能降低。

圖5 重放間隔對(duì)歸一化互信息指標(biāo)的影響Fig.5 Influence of the replay interval on the normalized mutual information index

3.4.3 重放文本數(shù)量對(duì)算法性能的影響

重放文本是指在每個(gè)重放間隔內(nèi)進(jìn)行經(jīng)驗(yàn)重放的文本。圖6 顯示了在News-T、Tweets-T、NT 數(shù)據(jù)集上不同的重放文本數(shù)量對(duì)NMI 的影響。由圖6 可以看出，隨著重放文本數(shù)量增加，NMI 呈現(xiàn)上升趨勢(shì)。可能的原因是重放文本數(shù)量越多，就會(huì)有更多的采樣文本被用來(lái)更新聚類特征向量。如圖7 所示，過(guò)少的重放文本會(huì)減少聚類的特征數(shù)量降低算法的性能，但過(guò)多的重放文本會(huì)導(dǎo)致算法運(yùn)行時(shí)間變長(zhǎng)。

圖6 重放文本數(shù)量對(duì)歸一化互信息指標(biāo)的影響Fig.6 Influence of the number of replay texts on the normalized mutual information index

圖7 重放文本數(shù)量對(duì)算法運(yùn)行時(shí)間的影響Fig.7 Influence of the number of replay texts on the running time of the algorithm

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

本文將情節(jié)記憶思想融入短文本流聚類算法，提出一種帶情節(jié)記憶的高效短文本流聚類算法。采用在線-離線階段對(duì)短文本流進(jìn)行聚類：在線階段融入情節(jié)記憶思想緩解短文本流的稀疏性問(wèn)題，通過(guò)反向索引減少聚類運(yùn)行時(shí)間；離線階段通過(guò)聚類增強(qiáng)、語(yǔ)義再分配以及刪除過(guò)時(shí)聚類來(lái)提高聚類性能。通過(guò)在3 個(gè)公開(kāi)數(shù)據(jù)集上與6 個(gè)基準(zhǔn)算法進(jìn)行實(shí)驗(yàn)對(duì)比，結(jié)果表明所提算法的多項(xiàng)評(píng)價(jià)指標(biāo)都取得了較好的結(jié)果，并且在運(yùn)行時(shí)間上比多數(shù)算法減少1～3 個(gè)數(shù)量級(jí)。通過(guò)消融實(shí)驗(yàn)可知，不同的記憶內(nèi)存大小、重放間隔以及重放文本數(shù)量對(duì)算法性能均有一定的影響。后續(xù)可將深度學(xué)習(xí)模型和詞共現(xiàn)矩陣引入短文本流聚類算法，對(duì)文本進(jìn)行深度順序編碼，以提高聚類精度，并將其應(yīng)用于針對(duì)短文本流的新聞推薦等場(chǎng)景進(jìn)一步拓寬使用范圍。