鄧先均 楊雅茜 羅昭 陳旭東 沈小平

摘要：數(shù)據(jù)聚類是基于某種相似性度量在多維數(shù)據(jù)中識(shí)別自然分組或集群的過(guò)程。聚類是許多不同學(xué)科的基本過(guò)程。 因此，來(lái)自不同領(lǐng)域的研究人員正在積極研究聚類問(wèn)題。文章首先對(duì)代表性的基于劃分的聚類方法進(jìn)行了一個(gè)概述，在此基礎(chǔ)之上，針對(duì)網(wǎng)絡(luò)輿情熱點(diǎn)話題檢測(cè)，文章使用這幾個(gè)聚類算法進(jìn)行對(duì)比試驗(yàn)，進(jìn)而分析出更適用于熱點(diǎn)話題檢測(cè)方面的算法。最后對(duì)文章的研究進(jìn)行總結(jié)，歸納出本研究的局限性，并指出改進(jìn)的方向。

關(guān)鍵詞：數(shù)據(jù)聚類；聚類算法；網(wǎng)絡(luò)輿情；熱點(diǎn)話題檢測(cè)

中圖分類號(hào)：TP391.1 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2018）05-0146-04

1 引言

數(shù)據(jù)聚類是基于某種相似性度量在多維數(shù)據(jù)中識(shí)別自然分組或集群的過(guò)程，這是模式識(shí)別和機(jī)器學(xué)習(xí)中一個(gè)重要的處理過(guò)程[1]。此外，數(shù)據(jù)聚類也是人工智能的一個(gè)核心問(wèn)題。聚類算法被使用在很多應(yīng)用中，比如圖像分割、矢量和彩色圖像量化、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等領(lǐng)域[2-4]。數(shù)據(jù)聚類是無(wú)監(jiān)督模式識(shí)別中的一個(gè)難題，因?yàn)閿?shù)據(jù)中的群集可能具有不同的形狀和大小[5]。

熱點(diǎn)話題指的是在某個(gè)時(shí)間段內(nèi)人們比較關(guān)注的話題，涉及民生、政治、經(jīng)濟(jì)以及文化等方面[6]。熱點(diǎn)話題檢測(cè)的核心部分實(shí)質(zhì)上是文本聚類的過(guò)程，對(duì)于不同的聚類算法對(duì)應(yīng)不同程度的有效性[7]。文章首先對(duì)常用的基于劃分的聚類算法進(jìn)行了一個(gè)概述，在此基礎(chǔ)上使用這些算法進(jìn)行對(duì)比試驗(yàn)，進(jìn)而選擇出適合熱點(diǎn)話題檢測(cè)的算法。

2 基于劃分的聚類技術(shù)

2.1 K-MEANS算法

最廣泛使用的基于劃分的算法是K-MEANS聚類方法，K-MEANS優(yōu)化的目標(biāo)函數(shù)是：

因此，K均值算法最小化簇內(nèi)距離。K均值算法以K個(gè)質(zhì)心開(kāi)始（質(zhì)心的初始值是隨機(jī)選擇的或從先驗(yàn)信息中導(dǎo)出的），然后，將數(shù)據(jù)集中的每個(gè)數(shù)據(jù)對(duì)象分配給最近的聚類（即最接近的質(zhì)心）。最后，質(zhì)心根據(jù)相關(guān)的數(shù)據(jù)對(duì)象重新計(jì)算，重復(fù)這個(gè)過(guò)程，直到收斂。

K均值的隸屬函數(shù)和權(quán)重函數(shù)定義如下：

因此，K-MEANS具有很強(qiáng)的隸屬函數(shù)。此外，K-MEANS具有恒定的權(quán)重函數(shù)，因此，所有數(shù)據(jù)對(duì)象具有同等的重要性。

2.2 模糊C均值算法

K-MEANS的模糊版本稱為模糊C均值（FCM）（有時(shí)稱為模糊K均值）。FCM是基于最小平方誤差準(zhǔn)則的模糊擴(kuò)展。FCM優(yōu)于K均值的優(yōu)點(diǎn)是FCM將每個(gè)數(shù)據(jù)對(duì)象分配給具有某種程度隸屬度（即模糊聚類）的每個(gè)聚類，這更適合于數(shù)據(jù)集中聚類之間存在一些重疊的實(shí)際應(yīng)用。FCM優(yōu)化的目標(biāo)函數(shù)是：

其中是模糊指數(shù)[8]，，增加的值會(huì)使算法更加模糊；是第個(gè)聚類中第個(gè)數(shù)據(jù)對(duì)象的隸屬度值，滿足以下約束條件：

因此，F(xiàn)CM具有軟隸屬函數(shù)和恒重函數(shù)。一般來(lái)說(shuō)，F(xiàn)CM表現(xiàn)比K-MEANS更好，并且受數(shù)據(jù)不確定性的影響較小。

2.3 K-調(diào)和均值算法

在K-調(diào)和均值算法（KHM）中，計(jì)算每個(gè)聚類中心到每個(gè)數(shù)據(jù)對(duì)象距離的調(diào)和平均值，然后相應(yīng)地更新簇質(zhì)心。KHM優(yōu)化的目標(biāo)函數(shù)是：

因此，KHM具有軟隸屬函數(shù)和變化的權(quán)重函數(shù)。KHM為遠(yuǎn)離所有質(zhì)心的數(shù)據(jù)對(duì)象分配更高的權(quán)重，以幫助質(zhì)心覆蓋更多的數(shù)據(jù)。

3 網(wǎng)絡(luò)輿情熱點(diǎn)話題檢測(cè)

3.1 話題檢測(cè)與跟蹤評(píng)價(jià)指標(biāo)

在話題檢測(cè)與跟蹤（Topic Detectionand Tracking，TDT）的評(píng)價(jià)標(biāo)準(zhǔn)中，有準(zhǔn)確率、召回率、漏報(bào)率和誤報(bào)率4個(gè)評(píng)價(jià)指標(biāo)[9]，這4個(gè)評(píng)價(jià)指標(biāo)的定義如下：

（1）準(zhǔn)確率（P）：檢索出的關(guān)于某個(gè)特定話題的相關(guān)信息數(shù)量與所有檢索出的信息總數(shù)之比（也被稱為查準(zhǔn)率），計(jì)算公式為，其中，A為系統(tǒng)正確檢索出的相關(guān)信息數(shù)量，B為把不相關(guān)的信息錯(cuò)誤的識(shí)別為相關(guān)信息的數(shù)量。

（2）召回率（R）：檢索出的關(guān)于某個(gè)特定話題的相關(guān)信息數(shù)量與系統(tǒng)中描述該話題的相關(guān)信息總量之比，也稱為查全率，計(jì)算公式為，其中，A為系統(tǒng)正確檢索出的相關(guān)信息數(shù)量，C為系統(tǒng)未檢索出的相關(guān)信息的數(shù)量。

（3）漏報(bào)率（M）：系統(tǒng)沒(méi)有檢索出的關(guān)于某個(gè)特定話題的相關(guān)信息數(shù)量與系統(tǒng)中描述該話題的相關(guān)信息總量之比，計(jì)算公式為，其中，A為系統(tǒng)正確檢索出的相關(guān)信息數(shù)量，C為系統(tǒng)未檢索出的相關(guān)信息的數(shù)量。

（4）誤報(bào)率（F）：系統(tǒng)將與某個(gè)特定話題不相關(guān)的信息錯(cuò)誤判斷為相關(guān)信息的數(shù)量與系統(tǒng)中沒(méi)有描述該話題的信息總量之比，計(jì)算公式為，其中，B為把不相關(guān)的信息錯(cuò)誤的識(shí)別為相關(guān)信息的數(shù)量，D為系統(tǒng)未檢索出的不相關(guān)信息的數(shù)量。

在對(duì)熱點(diǎn)話題檢測(cè)中，對(duì)于一個(gè)TDT系統(tǒng)的性能，我們使用歸一化識(shí)別代價(jià)這個(gè)指標(biāo)來(lái)評(píng)價(jià)，它通過(guò)系統(tǒng)的漏報(bào)率和誤報(bào)率計(jì)算得到，公式如下：

其中：

（1）為系統(tǒng)錯(cuò)誤檢索代價(jià)，它由公式（11）計(jì)算得到。

（2）、分別為漏報(bào)和誤報(bào)的代價(jià)，它們的值通常情況下由應(yīng)用預(yù)先給定。在大部分TDT測(cè)評(píng)任務(wù)中，它們分別取10和1，即漏報(bào)的代價(jià)比誤報(bào)代價(jià)高很多。

（3）、分別為系統(tǒng)檢索的漏報(bào)率和誤報(bào)率，它們可以通過(guò)系統(tǒng)輸出與標(biāo)準(zhǔn)答案對(duì)照的結(jié)果計(jì)算得到，計(jì)算公式是=漏檢數(shù)量/目標(biāo)數(shù)量、=誤報(bào)數(shù)量/非目標(biāo)數(shù)量。

（4）為一個(gè)先驗(yàn)?zāi)繕?biāo)出現(xiàn)的概率，即，表示關(guān)于某個(gè)話題新聞報(bào)道出現(xiàn)的可能性，它的值通常也由相關(guān)應(yīng)用給出。

為了使所得到的性能指標(biāo)能夠在更有意義的范圍之內(nèi)，我們將錯(cuò)誤識(shí)別代價(jià)做歸一化處理得到。在公式（10）中，分母部分事實(shí)上是一個(gè)最小的預(yù)期代價(jià)，它是由系統(tǒng)對(duì)每一項(xiàng)識(shí)別給出的全部肯定或全部否定猜測(cè)而得到的。歸一化處理后的識(shí)別代價(jià)的最小值為0，表示系統(tǒng)性能最佳，最大值為1，表示系統(tǒng)性能較差。

3.2 話題檢測(cè)算法實(shí)驗(yàn)對(duì)比

本節(jié)主要通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證和對(duì)比以下三種聚類算法的性能：K-MEANS算法、FCM算法和K-調(diào)和均值算法。

3.2.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)數(shù)據(jù)是通過(guò)網(wǎng)絡(luò)爬蟲從網(wǎng)易新聞（http：//news.163.com）和今日頭條（https：//www.toutiao.com/ch/news_hot/）上下載了2378篇新聞，包含了14個(gè)主題，發(fā)生的時(shí)間從2018年2月到2018年3月，涵蓋了政治、經(jīng)濟(jì)、生活等多個(gè)方面，其事件分布情況如表1所示（每個(gè)話題下選前80篇作為訓(xùn)練集，剩下的作為測(cè)試集）。

3.2.2 K-MEANS算法驗(yàn)證

在K-MEANS算法實(shí)驗(yàn)中，設(shè)置隱藏話題的數(shù)量K為14，表2給出了K-MEANS算法對(duì)14個(gè)話題的檢測(cè)準(zhǔn)確率、召回率、漏報(bào)率、誤報(bào)率和。

3.2.3 FCM算法驗(yàn)證

對(duì)實(shí)驗(yàn)數(shù)據(jù)集使用FCM算法，得到對(duì)14個(gè)話題的檢測(cè)準(zhǔn)確率、召回率、漏報(bào)率、誤報(bào)率和，如表3所示。

3.2.4 K-調(diào)和均值算法驗(yàn)證

將FCM算法應(yīng)用于實(shí)驗(yàn)數(shù)據(jù)集，得到14個(gè)話題的檢測(cè)準(zhǔn)確率、召回率、漏報(bào)率、誤報(bào)率和，如表4所示。

3.2.5 三種算法性能對(duì)比

根據(jù)表2、表3、表4中三種算法的漏報(bào)率、誤報(bào)率和，分別計(jì)算這三種算法的平均漏報(bào)率、誤報(bào)率和，通過(guò)這三項(xiàng)對(duì)比三種算法的性能，如表5所示。

從表5我們可以看出，這三種算法性能由高到低排序是：FCM算法、K-MEANS算法、K-調(diào)和均值算法，因此，在這三種算法中，選擇FCM算法作為熱點(diǎn)話題檢測(cè)算法是比較合適的。

4 總結(jié)與展望

文章在對(duì)代表性聚類方法進(jìn)行概述的基礎(chǔ)上，根據(jù)網(wǎng)易和今日頭條2018年度2月和3月兩個(gè)平臺(tái)的數(shù)據(jù)，提煉出14個(gè)主題，選擇FCM、K-MEANS、K-調(diào)和均值三種算法對(duì)網(wǎng)絡(luò)輿情熱點(diǎn)事件在檢測(cè)準(zhǔn)確率、召回率、漏報(bào)率、誤報(bào)率和這幾個(gè)方面進(jìn)行對(duì)比試驗(yàn)，最后得出相關(guān)結(jié)論。文章的局限性在于對(duì)信息發(fā)布平臺(tái)的選取不全面，同時(shí)在對(duì)比分析方面聚類算法種類的選擇也存在局限性，因而在接下來(lái)的研究中要加以改進(jìn)。

參考文獻(xiàn)

[1]Jacques， Julien， and Cristian Preda. "Functional data clustering： a survey."Advances in Data Analysis and Classification 8.3 （2014）：231-255.

[2]Schaub M T， O'Clery N， Billeh Y N， et al. Graph partitions and cluster synchronization in networks of oscillators[J]. Chaos，2016，26（9）：094821.

[3]Kandakatla M， Challa L R. Cluster analysis for purpose oriented data mining in large databases[J]. 2017.

[4]Nilashi M， Fard K B， Rahmani M， et al. A Recommender System for Tourism Industry Using Cluster Ensemble and Prediction Machine Learning Techniques[J]. Computers & Industrial Engineering，2017， 109.

[5]Fan W， Bouguila N， Ziou D. Unsupervised Hybrid Feature Extraction Selection for High-Dimensional Non-Gaussian Data Clustering with Variational Inference[J]. IEEE Transactions on Knowledge & Data Engineering，2013，25（7）：1670-1685.

[6]徐維林，張暉，殷玉嬌，等.基于微博的熱點(diǎn)話題跟蹤技術(shù)研究[J].電腦知識(shí)與技術(shù)，2016（13）：186-188.

[7]Lin T， Wei S. The research on document clustering of network hot topics[C]// IEEE International Conference on Computer and Communications. IEEE，2017.

[8]Kim D W， Lee K H， Lee D. Fuzzy cluster validation index based on inter-cluster proximity[J]. Pattern Recognition Letters，2003，24（15）：2561-2574.

[9]Allan， James. TOPIC DETECTION AND TRACKING[J].Information Retrieval，2016.