基于增量文本聚類(lèi)算法的熱點(diǎn)話(huà)題檢測(cè)研究

魏藝澤，郭 慧，時(shí)曉旭

（華北科技學(xué)院計(jì)算機(jī)學(xué)院，北京東燕郊 065201）

0 引言

網(wǎng)絡(luò)輿情熱點(diǎn)發(fā)現(xiàn)（TDT）是一種通過(guò)檢測(cè)與跟蹤目標(biāo)話(huà)題的方法，提供對(duì)新信息的發(fā)現(xiàn)和特定熱點(diǎn)的關(guān)注。 通過(guò)數(shù)據(jù)收集、預(yù)處理、相關(guān)性分析和熱點(diǎn)跟蹤等步驟，自動(dòng)聚類(lèi)相關(guān)內(nèi)容，并跟蹤新聞事件的發(fā)展，為用戶(hù)提供事件發(fā)展的軌跡和態(tài)勢(shì)。 現(xiàn)有的研究技術(shù)主要有Single-Pass 聚類(lèi)算法、KNN 最鄰近法、K-means 算法等。

為了能夠?qū)崿F(xiàn)在線(xiàn)話(huà)題檢測(cè)，需要對(duì)現(xiàn)有聚類(lèi)算法進(jìn)行改進(jìn)，最常用的增量聚類(lèi)算法是Single-Pass 算法。 稅儀冬等［1］提出了一種結(jié)合周期性分類(lèi)和Single-Pass 聚類(lèi)話(huà)題識(shí)別和跟蹤方法，通過(guò)降低漏檢率和錯(cuò)檢率，提高了準(zhǔn)確性。 方星星，呂永強(qiáng)［2］通過(guò)引入子話(huà)題中心和時(shí)間距離計(jì)算公式以及優(yōu)化耗費(fèi)函數(shù)，顯著改善了算法在漏檢率、誤檢率、耗費(fèi)函數(shù)等方面的性能。 張琛等［3］使用了Single-Pass 算法來(lái)處理大量的評(píng)論語(yǔ)料，并從其中提取出主題信息以展現(xiàn)新冠肺炎期間公眾的關(guān)注熱點(diǎn)。 楊波［4］通過(guò)設(shè)置高閾值提高了Single-Pass算法的準(zhǔn)確性。 孫紅光等［5］只對(duì)新增加的文本進(jìn)行處理，提高了Single-Pass 算法的效率。

文本表示是將文本數(shù)據(jù)轉(zhuǎn)化成結(jié)構(gòu)化數(shù)據(jù)的方法，TF-IDF（Term Frequency-Inverse Document Frequency）以簡(jiǎn)單快速被好多學(xué)者所用。 羅燕等［6］采用齊普夫定律、特征詞的詞頻以及TF-IDF算法來(lái)提取文檔關(guān)鍵詞。 牛永潔等［7］綜合考慮張瑾提出基于TF-IDF、詞位置和詞跨度的關(guān)鍵詞自動(dòng)提取的方法，在情報(bào)關(guān)鍵詞提取中有廣泛的應(yīng)用價(jià)值。 高楠等［8］提出了一種融合語(yǔ)義特征的TF-IDF 提取方法。 曹義親等［9］使用TF-IDF算法作為基準(zhǔn)進(jìn)行關(guān)鍵詞提取，并結(jié)合特征詞詞頻均值化與特征詞位置信息對(duì)權(quán)重算法對(duì)其進(jìn)行改進(jìn)。 米碩等［10］使用TextRank 算法與TF-IDF算法相結(jié)合的方法，提高了關(guān)鍵詞提取的性能。

針對(duì)傳統(tǒng)TF-IDF 方法提取文本特征時(shí)無(wú)法增量更新以及傳統(tǒng)Single-Pass 算法聚類(lèi)準(zhǔn)確率較低的現(xiàn)象，本文提出一種增量的TF-IDF 算法和基于均值計(jì)算的Single-Pass 聚類(lèi)話(huà)題檢測(cè)方法，該方法首先利用提前設(shè)置IDF 表的方法，實(shí)現(xiàn)了增量獲取詞向量的功能，再通過(guò)均值計(jì)算簇中心來(lái)提高Single-Pass 算法在聚類(lèi)時(shí)的準(zhǔn)確率以及效率。

1 算法框架

研究框架如圖1 所示，主要分為三個(gè)部分，分別是數(shù)據(jù)讀取與預(yù)處理層、文本表示層、輿情分析層。 數(shù)據(jù)讀取與處理層是首先將來(lái)自國(guó)內(nèi)影響力比較大的社交平臺(tái)獲取的新聞數(shù)據(jù)存儲(chǔ)到Sqlite3數(shù)據(jù)庫(kù)并從數(shù)據(jù)庫(kù)中讀取出來(lái)，然后進(jìn)行數(shù)據(jù)清洗、jieba 分詞、去停用詞。 文本表示層是利用TF-IDF 算法獲得上下文向量。 輿情分析層利用Single-Pass 算法基礎(chǔ)，根據(jù)提取到的特征詞，劃分子話(huà)題，利用均值動(dòng)態(tài)更新類(lèi)簇中心，提高文本相似度計(jì)算的準(zhǔn)確性。

圖1 算法框架圖

2 增量TF-IDF 算法

分詞之后，要進(jìn)行文本特征提取，即識(shí)別文本中代表其特征的詞項(xiàng)［11］。 TF-IDF 算法在信息檢索和文本分類(lèi)等任務(wù)中廣泛應(yīng)用，有效地幫助提取關(guān)鍵信息和識(shí)別文本的重要特征。 TF-IDF 的核心思想是：一個(gè)詞在一個(gè)文檔中的詞頻較高，同時(shí)在整個(gè)文檔集合中的逆文檔頻率較低，則這個(gè)詞對(duì)于該文檔的重要性就越高。

由于計(jì)算IDF 是根據(jù)語(yǔ)料庫(kù)中文檔的數(shù)量和包含詞匯的文檔數(shù)量來(lái)計(jì)算的，所以傳統(tǒng)的TFIDF 具有依賴(lài)語(yǔ)料庫(kù)這一局限性，對(duì)于先到達(dá)的詞匯無(wú)法估計(jì)在之后文本中的出現(xiàn)頻率，影響了IDF 值計(jì)算的準(zhǔn)確性。 另外如果每次都重新計(jì)算IDF 值，會(huì)耗費(fèi)時(shí)間。 為了解決這個(gè)問(wèn)題，本文通過(guò)事先建立語(yǔ)料庫(kù)的方式來(lái)解決此問(wèn)題。 利用計(jì)算公式計(jì)算IDF 值，并將其存儲(chǔ)為IDF 表，語(yǔ)料庫(kù)中已包含絕大多數(shù)常用詞匯，可以滿(mǎn)足實(shí)驗(yàn)文本的需求，可以有效地避免每次重新計(jì)算。 對(duì)于新出現(xiàn)的詞匯，可以采用最大IDF 值作為估計(jì)值，以提高計(jì)算效率，并將新出現(xiàn)的IDF 值更新至IDF表中。 具體步驟如下：

（1） IDF 值用于衡量一個(gè)特定單詞在整個(gè)語(yǔ)料庫(kù)中的普遍重要性。 如果一個(gè)單詞在整個(gè)語(yǔ)料庫(kù)中出現(xiàn)的文章數(shù)較少，那么它在具體的文章中更加稀有和獨(dú)特，具有很好的區(qū)分能力。 將前n天的數(shù)據(jù)儲(chǔ)存成IDF 表，存儲(chǔ)成字典形式，計(jì)算IDF 值。 其計(jì)算式如下［12］：

式中，IDFi值表示第i個(gè)IDF 值；代表文檔總數(shù)；代表文檔dj包含分詞ti的文檔數(shù)。

（2） 將預(yù)處理好的詞計(jì)算TF 值，并且從IDF表查找該詞的IDF 值，若表中沒(méi)有該詞的IDF 值，則設(shè)為該表中的最大值并存入IDF 表中，具體公式如下：

式中，TFij表示分詞ti在文檔編號(hào)dj中出現(xiàn)的頻率；分子n代表分詞ti在文檔dj中出現(xiàn)的次數(shù)；分母表示文檔dj中所有詞出現(xiàn)次數(shù)的總和；k代表這個(gè)文檔的總詞數(shù)； 代表文檔j 的總詞數(shù)。

（3） 計(jì)算TF-IDF 值，具體公式如下：

其中，ti表示單詞；dj表示文檔；TFij表示單詞ti在文檔dj的詞頻；IDF（ti）表示單詞在ti的逆文檔頻率。 在計(jì)算過(guò)程中，可以先計(jì)算出文檔dj中每個(gè)單詞的詞頻TF（ti，dj），然后從IDF 表中查找對(duì)應(yīng)單詞的IDF 值IDF（ti），最后將兩者相乘即可得到單詞ti在文檔dj中的TF-IDF 值TF-IDF（ti，dj）。

3 基于均值計(jì)算的Single-Pass 聚類(lèi)算法

3.1 簇中心的選擇

對(duì)于網(wǎng)絡(luò)新聞而言，新聞信息的獲得、處理都是實(shí)時(shí)的。 對(duì)于此類(lèi)問(wèn)題，增量式的聚類(lèi)更適用，Single-Pass 方法是增量式聚類(lèi)方法的代表。 傳統(tǒng)的Single-Pass 算法是一種流式處理文本數(shù)據(jù)的聚類(lèi)算法，只需依次比較新輸入的文本數(shù)據(jù)與已有類(lèi)簇的文本相似度，不需要每次對(duì)整個(gè)文檔集合重新聚類(lèi)，具有實(shí)現(xiàn)便捷、易于理解和應(yīng)用廣泛的特點(diǎn)。

但傳統(tǒng)的Single-Pass 算法以每個(gè)話(huà)題的第一篇文章作為簇中心會(huì)導(dǎo)致簇的代表性不夠強(qiáng)，無(wú)法很好地代表整個(gè)簇的特征。 第一篇文章可能只是話(huà)題中的一個(gè)特例，不能很好地代表整個(gè)話(huà)題的特征。 這樣就會(huì)導(dǎo)致簇的準(zhǔn)確性較低，無(wú)法很好地區(qū)分不同的話(huà)題。 針對(duì)傳統(tǒng)Single-Pass聚類(lèi)算法不足，本文提出了基于均值計(jì)算的Single-Pass 聚類(lèi)算法通過(guò)動(dòng)態(tài)更新類(lèi)簇中心，僅僅需要將輸入的新文本與該類(lèi)簇的質(zhì)心向量比較相似度，就可以判斷是否屬于該聚類(lèi)，均值簇中心是根據(jù)簇中所有文章的特征值計(jì)算得到的，可以更全面地反映簇的特征，可以有效地減少與各個(gè)簇比較的次數(shù)，降低算法運(yùn)算復(fù)雜度以及提高新文本反應(yīng)能力。

3.2 話(huà)題檢測(cè)的流程

一個(gè)文本及閾值，將新進(jìn)入話(huà)題的文本設(shè)為簇中心，后續(xù)文本出現(xiàn)時(shí)計(jì)算該文本與待聚類(lèi)話(huà)題的簇中心的相似度，若相似度大于閾值則將新文檔和原話(huà)題的簇中心取平均值，更新簇中心；否則新建一個(gè)話(huà)題并將該文本經(jīng)過(guò)多次迭代計(jì)算可以得到多個(gè)話(huà)題類(lèi)，完成話(huà)題檢測(cè)。

（1） 按照文本的發(fā)布時(shí)間順序從數(shù)據(jù)庫(kù)中讀出；

（2） 利用正則表達(dá)式去掉特殊符號(hào)；

（4） 使用哈工大停用詞表以及自定義的疫情停用詞表對(duì)文檔去除停用詞；

（5） 新話(huà)題存在很多與舊話(huà)題相近的特征詞， 為了改善聚類(lèi)質(zhì)量，需要自定義替換詞表將意思相近的詞相互替換成相同的特征詞；

表1 同義詞替換表

（6） 通過(guò)TF-IDF 算法構(gòu)造文本向量矩陣V1［v1，v2，v3，…vn］，V2，V3，…，Vn；

（7） 選擇語(yǔ)料庫(kù)的第一條文本作為種子語(yǔ)料，設(shè)為第一個(gè)話(huà)題C0；

（8） 設(shè)置相似度閾值S，將依次到來(lái)的文本向量與已有話(huà)題中的文本向量做余弦相似度計(jì)算，余弦相似度的計(jì)算公式為：

式中，Vi為文本向量矩陣。

（9） 若相似度小于閾值S則建立新話(huà)題Ci（i＝1，2，3，……），并設(shè)置進(jìn)入新話(huà)題的第一條文本為簇中心mi，每次新加入的文檔僅僅需要與聚類(lèi)中心進(jìn)行比較即可；若相似度計(jì)算結(jié)果大于閾值S則將文本劃歸到所屬話(huà)題，并利用均值計(jì)算更新簇中心，對(duì)于每個(gè)簇Ci，其簇中心的更新公式為：

目前基本面情況缺乏推動(dòng)行情變動(dòng)的新消息，貿(mào)易摩擦是近期主導(dǎo)豆粕價(jià)格的重要因素。就目前情況，中美會(huì)談?wù)结尫藕途徯盘?hào)，考慮到市場(chǎng)近日已逐步反映對(duì)貿(mào)易摩擦和解的預(yù)期，加之2018/2019年度全球大豆供給充足，國(guó)內(nèi)大豆、豆粕庫(kù)存偏高的基本面情況，豆粕價(jià)格仍有繼續(xù)下跌的空間。

（10） 直至所有文本歸屬到所建立的話(huà)題類(lèi)別中，聚類(lèi)結(jié)束。

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

4.1 數(shù)據(jù)集與實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)新聞?wù)Z料庫(kù)選自微信、騰訊網(wǎng)、天天快報(bào)、中國(guó)青年網(wǎng)、百度新聞、搜狐新聞等多個(gè)平臺(tái)爬取的2021 年8 月4 日的1000 篇文章，共分為82 個(gè)類(lèi)別，閾值為0.8。 其中包含以下5 個(gè)新聞話(huà)題：“南航CZ3762 航班通報(bào)密切接觸者”“河南災(zāi)后重建恢復(fù)階段”“特效藥伊維菌素能結(jié)束新冠疫情系謠言”“單克隆抗體是全球新冠疫情防控研究的熱點(diǎn)”以及“外防輸入、內(nèi)防反彈”事件。其中每個(gè)話(huà)題的報(bào)道100 篇。

本文采用的實(shí)驗(yàn)環(huán)境：操作系統(tǒng)Windows11，開(kāi)發(fā)工具為Pycharm，數(shù)據(jù)庫(kù)為SQLite 數(shù)據(jù)庫(kù)。

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

4.2.1 精度評(píng)估

為了驗(yàn)證改進(jìn)算法的有效性，本文采用熱點(diǎn)話(huà)題檢測(cè)常用的評(píng)價(jià)指標(biāo)準(zhǔn)確率P、召回率R 和F 值對(duì)話(huà)題檢測(cè)的精度進(jìn)行評(píng)估，其定義如下：

（1） 精確率（Precision）。 表示分類(lèi)器在預(yù)測(cè)為正類(lèi)的情況下，預(yù)測(cè)正確的比例，計(jì)算公式如下：

（2） 召回率（Recall）。 所有實(shí)際為正類(lèi)的文檔中，被正確預(yù)測(cè)為正類(lèi)的比例，計(jì)算公式如下：

（3） 綜合評(píng)價(jià)指標(biāo)（F1）是精確率和召回率的調(diào)和均值，相當(dāng)于精確率和召回率的綜合評(píng)價(jià)指標(biāo)，計(jì)算公式如下：

上述公式（7）～（9）中，TP代表將實(shí)際為正類(lèi)樣本分類(lèi)成正類(lèi)樣本的個(gè)數(shù)；TN代表將實(shí)際成負(fù)類(lèi)樣本分類(lèi)成負(fù)類(lèi)樣本的個(gè)數(shù)；FP代表將實(shí)際為負(fù)類(lèi)樣本分類(lèi)成正類(lèi)樣本的個(gè)數(shù)；FN代表將實(shí)際為正類(lèi)樣本分類(lèi)成負(fù)類(lèi)樣本的個(gè)數(shù)。

4.2.2 順序查找

為了驗(yàn)證算法的查找效率，利用順序查找的方式進(jìn)行測(cè)試。 順序查找是一種簡(jiǎn)單直觀的查找算法，它逐一比較待查找的元素和數(shù)據(jù)集中的每個(gè)元素，直到找到目標(biāo)元素或遍歷完整個(gè)數(shù)據(jù)集。

4.3 結(jié)果與分析

4.3.1 閾值的確定

圖2 為利用Single-Pass 算法將輿情文本數(shù)據(jù)聚類(lèi)出話(huà)題數(shù)目隨著不同的閾值變化的曲線(xiàn)，選出與人工分類(lèi)最接近的閾值。

圖2 聚類(lèi)數(shù)目隨閾值的變化

對(duì)依次輸入的輿情文本進(jìn)行建模，并實(shí)現(xiàn)增量聚類(lèi)，聚類(lèi)個(gè)數(shù)隨相似度的變化如圖2，可以看到，隨著閾值變大，聚類(lèi)數(shù)目增多，只有相似度極大的文本才會(huì)聚成一類(lèi)。 而隨著閾值變小，聚類(lèi)數(shù)目減少。 當(dāng)閾值為0.8 時(shí)最符合事先人工分類(lèi)的預(yù)期結(jié)果。 所以選取閾值為0.8 來(lái)進(jìn)行實(shí)驗(yàn)。

4.3.2 實(shí)驗(yàn)結(jié)果

表2 是利用1000 條輿情文本數(shù)據(jù)，為了驗(yàn)證基于增量TF-IDF 的Single-Pass 聚類(lèi)算法在改進(jìn)前后的差異，設(shè)計(jì)的兩組對(duì)照實(shí)驗(yàn)分別驗(yàn)證算法的聚類(lèi)質(zhì)量。

表2 改進(jìn)的Single-Pass 算法聚類(lèi)精確率對(duì)比表

利用五個(gè)不同的話(huà)題來(lái)驗(yàn)證原始算法和改進(jìn)算法的聚類(lèi)質(zhì)量，用傳統(tǒng)Single-Pass 算法聚類(lèi)得到的結(jié)果如表3 所示，用改進(jìn)的Single-Pass 得到的結(jié)果見(jiàn)表4。

表3 傳統(tǒng)Single-Pass 算法實(shí)驗(yàn)結(jié)果

表4 基于均值計(jì)算的Single-Pass 算法

為了驗(yàn)證算法在求解質(zhì)量與傳統(tǒng)算法之間的差別，可以看出，在熱點(diǎn)話(huà)題檢測(cè)任務(wù)上，基于均值計(jì)算的Single-Pass 算法在熱點(diǎn)話(huà)題檢測(cè)任務(wù)上表現(xiàn)出更好的準(zhǔn)確率、召回率和F 值。 相較于傳統(tǒng)的Single-Pass 聚類(lèi)算法改進(jìn)的算法在準(zhǔn)確率、召回率、F 值都提高了。 原因是傳統(tǒng)的Single-Pass 聚類(lèi)算法在選取某一話(huà)題的所有文本來(lái)表示話(huà)題類(lèi)時(shí)，隨機(jī)選取話(huà)題中心，通常選取第一個(gè)文本成為第一個(gè)類(lèi)別的聚類(lèi)簇中心，如果第一個(gè)文本不太具有代表意義，便不能全面地對(duì)一個(gè)類(lèi)中的話(huà)題進(jìn)行很好地闡述，隨著文本聚類(lèi)的進(jìn)行，被錯(cuò)分的可能性逐漸增加，準(zhǔn)確率會(huì)下降。 基于均值計(jì)算的Single-Pass 算法區(qū)別于傳統(tǒng)的算法，它不僅計(jì)算簡(jiǎn)單，均值代表了簇中所有數(shù)據(jù)點(diǎn)的平均位置，能反映出簇的中心趨勢(shì)。

表5 實(shí)驗(yàn)是為了驗(yàn)證算法在求解效率與傳統(tǒng)算法之間的差別，評(píng)估標(biāo)準(zhǔn)為順序查找的比較次數(shù)。

表5 改進(jìn)的Single-Pass 算法聚類(lèi)效率對(duì)比表

通過(guò)比較傳統(tǒng)的Single-Pass 算法和基于均值計(jì)算的Single-Pass 算法兩者的查找次數(shù)，基于均值計(jì)算的Single-Pass 算法比較次數(shù)減少了。通過(guò)實(shí)驗(yàn)結(jié)果可以看出基于均值計(jì)算的Single-Pass 算法能夠?qū)⑽谋揪垲?lèi)到更好的話(huà)題類(lèi)別，熱點(diǎn)話(huà)題聚類(lèi)效果更好，提高了熱點(diǎn)話(huà)題聚類(lèi)的準(zhǔn)確率以及聚類(lèi)的效率。

圖3 在傳統(tǒng)Single-Pass 聚類(lèi)算法與改進(jìn)算法的運(yùn)行時(shí)間對(duì)比。

圖3 兩種算法的運(yùn)行時(shí)間對(duì)比圖

由圖3 可以看出，改進(jìn)的算法在時(shí)間消耗上明顯低于傳統(tǒng)Single-Pass 聚類(lèi)算法，原因是改進(jìn)后的算法中，利用文檔向量的平均值作為簇中心可以更好代表整篇文章的主題，相似度大的文章可以通過(guò)減少對(duì)比次數(shù)來(lái)歸類(lèi)，在一定程度上提高了算法的運(yùn)行效率。 傳統(tǒng)的算法是利用進(jìn)入文本的第一個(gè)文本作為簇中心，不能很好代表整篇文章，增加了對(duì)比的次數(shù)。

5 結(jié)論

（1） 針對(duì)TF-IDF 算法無(wú)法實(shí)現(xiàn)動(dòng)態(tài)更新的問(wèn)題，本文通過(guò)設(shè)置IDF 表對(duì)其進(jìn)行改進(jìn)。

（2） 針對(duì)Single-Pass 算法聚類(lèi)準(zhǔn)確率較低的問(wèn)題，本文對(duì)聚類(lèi)中心進(jìn)行了改進(jìn)，并對(duì)兩者聚類(lèi)算法進(jìn)行對(duì)比實(shí)驗(yàn)。 結(jié)果表明，在熱點(diǎn)話(huà)題檢測(cè)任務(wù)上，相比于傳統(tǒng)的Single-Pass 算法本文提出的計(jì)算每個(gè)話(huà)題簇中若干文檔的質(zhì)心向量作為此話(huà)題簇的話(huà)題簇代表這一概念，在保證精度的前提下，減少了比較次數(shù)，降低了計(jì)算復(fù)雜度，獲得的聚類(lèi)中心的代表性更強(qiáng)，有效提高了話(huà)題檢測(cè)的準(zhǔn)確性。

（3） 本文在使用TF-IDF 進(jìn)行文本表示時(shí)，只關(guān)注了詞頻和文檔頻率，未能捕捉到詞語(yǔ)之間的語(yǔ)義關(guān)系和上下文信息，導(dǎo)致在聚類(lèi)任務(wù)中單詞的語(yǔ)義信息沒(méi)有得到有效利用，下一階段將深入研究。