爆發(fā)主題探測(cè)關(guān)鍵問題算法研究

　爆發(fā) 主題 探測(cè) 關(guān)鍵 問題 的 算法研究* *

　 謝靖 中國(guó)科學(xué)院國(guó)家科學(xué)圖書館

　[ [ 摘要] ] 本文闡述爆發(fā)主題探測(cè)研究中面臨主題結(jié)構(gòu)判定和爆發(fā)特征發(fā)現(xiàn)兩個(gè)關(guān)鍵問題，分別對(duì)解決兩個(gè)問題中使用的常用算法進(jìn)行研究。分析對(duì)比各種算法的優(yōu)缺點(diǎn)，以及算法適用的環(huán)境。從信息保真度、爆發(fā)特征計(jì)算準(zhǔn)確性、算法效率等三個(gè)方面的指標(biāo)對(duì)各種算法對(duì)比評(píng)述。

　[ [ 分類號(hào)] ] TP393 [ [ 關(guān)鍵字] ] 爆發(fā)探測(cè)

　主題聚類

　爆發(fā)特征

　算法對(duì)比分析 Research on Key

　Problems of Burst Detection and Relate d Algorithms

　Xie Jing National Science Library, Chinese Academy of Sciences

　[Abstract] This paper describes the two key issues: topic structure determination and burst feature detection in burst topic detection research. Do research work on the algorithms to solve the two problems. Compare the advantages and disadvantages of these algorithms, as well as algorithms applicable environmental. Give the algorithms analysis from information fidelity, calculation accuracy, and the algorithm efficiency three indicators. [Keyword] Burst Detection, Topic Clustering, Burst Feature, Algorithms Analysis 1 1 引言

　 當(dāng)前正處于一個(gè)信息爆炸的時(shí)代，面對(duì)每天層出不窮該的海量信息，人們希望從這些信息中發(fā)現(xiàn)熱點(diǎn)的、重要的、關(guān)鍵的信息，以及自己最關(guān)注的資源。因此，對(duì)大量的信息進(jìn)行識(shí)別、分析和篩選，發(fā)現(xiàn)有價(jià)值，熱點(diǎn)的信息顯得尤為重要。爆發(fā)主題探測(cè)是一項(xiàng)重要研究領(lǐng)域，其主要目標(biāo)是發(fā)現(xiàn)在一定時(shí)間段內(nèi)以較

　 ? 本文系國(guó)家社會(huì)科學(xué)基金項(xiàng)目“網(wǎng)絡(luò)科技信息中爆發(fā)主題的監(jiān)測(cè)與分析方法研究”（項(xiàng)目編號(hào)：09BTQ035）的研究成果之一。

　高的頻率出現(xiàn)，或者在某個(gè)時(shí)間范圍出現(xiàn)突增特征或有異常變化的主題信息。這類主題即被標(biāo)識(shí)為具有爆發(fā)特征的熱點(diǎn)主題[1] 。具有爆發(fā)特征的信息，往往更加被人們關(guān)注，因此被認(rèn)為擁有更高的情報(bào)價(jià)值。

　爆發(fā)主題探測(cè)從網(wǎng)絡(luò)信息中獲取文本流，將信息在一定范圍內(nèi)進(jìn)行主題分布的聚類，然后將數(shù)據(jù)集合在時(shí)間或空間維度映射分析，從而根據(jù)分布特征，發(fā)現(xiàn)具有爆發(fā)特征的主題。針對(duì)主題結(jié)構(gòu)和爆發(fā)特征的算法，由于研究領(lǐng)域和應(yīng)用場(chǎng)景各不相同，算法的特性各有千秋。本文將爆發(fā)探測(cè)研究分解為：爆發(fā)主題的判定和爆發(fā)特征分析兩個(gè)方面的關(guān)鍵問題。對(duì)兩個(gè)研究方面使用的相關(guān)算法做重點(diǎn)研究，分析其核心算法，以及其衍生算法。對(duì)比在解決同類問題中的算法特征和優(yōu)缺點(diǎn)，以及算法適用的場(chǎng)景。

　2 2 爆發(fā)探測(cè) 的 關(guān)鍵 問題

　1 2.1 主題結(jié)構(gòu)的判定

　從新聞、網(wǎng)絡(luò)信息、郵件等一系列文本流是一系列文本詞匯的集合，這些詞匯中包含大量的非結(jié)構(gòu)化的、無組織的數(shù)據(jù)，并不能夠直接被人們所利用。顯著意義的主題信息和事件信息才是人們關(guān)注的重點(diǎn)，如何將人們關(guān)注的信息流聚焦成集中的主題、揭示文本流的主題結(jié)構(gòu)是爆發(fā)探測(cè)的首要工作。主題結(jié)構(gòu)判定首先需要從文本流中抽取出的關(guān)鍵詞或者術(shù)語(yǔ)等；其次需要對(duì)這些關(guān)鍵詞和術(shù)語(yǔ)在同一時(shí)間的爆發(fā)特征上進(jìn)行主題聚類，甚至是相似主題的匯聚和歸并；最后記錄聚類主題在文本中出現(xiàn)的頻率、密度等分布特征[2] 。通過特定算法計(jì)算出主題爆發(fā)能量特征，是爆發(fā)特征的發(fā)現(xiàn)的必要工作。

　2.2 2 爆發(fā)特征 發(fā)現(xiàn)

　文本信息匯聚由主題來組織和表達(dá)之后，判斷其是否具有爆發(fā)特征，需要根據(jù)它們的到達(dá)時(shí)間進(jìn)行分析研究。例如，特定時(shí)間點(diǎn)突然關(guān)于某個(gè)事件的新聞報(bào)道增多則說明該事件主題具有爆發(fā)性特征。某一時(shí)間段內(nèi)，關(guān)于某個(gè)研究領(lǐng)域的來往郵件頻繁，說明關(guān)于這個(gè)研究領(lǐng)域的主題討論具有爆發(fā)性特征。

　爆發(fā)特征與特定主題的文本流到達(dá)時(shí)間、到達(dá)率、統(tǒng)計(jì)頻率、以及主題能量

　等因素都有直接關(guān)系。這些因素的不規(guī)律性對(duì)準(zhǔn)確的發(fā)現(xiàn)爆發(fā)特征具有一定的難度，爆發(fā)特征經(jīng)常具有間歇性、粗糙性、隱匿性等特征[3] ，因而，從一系列文本流中提取爆發(fā)信息的爆發(fā)特征是爆發(fā)探測(cè)研究中的重點(diǎn)和難點(diǎn)。

　3 3 爆發(fā)探測(cè) 相關(guān) 算法 研究

　3.1 1 主題結(jié)構(gòu)判定 算法模型

　基于文本流中詞匯的爆發(fā)特征探測(cè)，由于詞匯表達(dá)意義的不明確和隨機(jī)性，簡(jiǎn)單的詞匯探測(cè)對(duì)爆發(fā)探測(cè)的實(shí)用價(jià)值不大，因此文本流的爆發(fā)主題結(jié)構(gòu)判定，是爆發(fā)探測(cè)的一個(gè)關(guān)鍵性問題。在文本的主題結(jié)構(gòu)判斷中，常用的方法是分為：主題聚類算法和概率統(tǒng)計(jì)模型算法，本文以幾種常用的算法為例對(duì)算法進(jìn)行研究對(duì)比。

　(1) 文本 主題聚類算法 模型

�、� K-MEANS 算法[4] ：

　K-MEANS預(yù)先定義k個(gè)聚類數(shù)量；然后將待聚類的n個(gè)數(shù)據(jù)對(duì)象按照定義的 k個(gè)聚類進(jìn)行迭代劃分，迭代后最終獲得的聚類滿足兩個(gè)條件：同一聚類中的對(duì)象相似度較高；而不同聚類中的對(duì)象相似度較小。K-MEANS 算法的工作過程說明如下：

　? 從 n 個(gè)數(shù)據(jù)對(duì)象任意選擇 k 個(gè)對(duì)象作為初始聚類起始中心點(diǎn)； ? 剩余的 n-k 個(gè)對(duì)象數(shù)據(jù)，則根據(jù)它們與這些聚類中心的相似度，通過中心度距離計(jì)算，分別分配給與其最相似的聚類中心所代表的聚類； ? 再計(jì)算每個(gè)所獲新聚類中所有對(duì)象的均值； ? 重復(fù)迭代這一計(jì)算過程，直到測(cè)度函數(shù)收斂為止。

　K-MEANS 算法的特點(diǎn)是采用測(cè)度函數(shù)計(jì)算均方差，使得聚類內(nèi)部各對(duì)象距離最小，各類之間的對(duì)象距離盡可能最大，已達(dá)到聚類的最佳效果。K-MEANS 算法的缺點(diǎn)是生成的聚類結(jié)果對(duì)于臟數(shù)據(jù)很敏感，臟數(shù)據(jù)的存在會(huì)引起較大的聚類誤差[5] 。

�、贙-MEDOIDS 算法[6]

　由于 K-MEANS 算法對(duì)臟數(shù)據(jù)敏感的缺點(diǎn)，K-MEDOIDS 算法選取一個(gè) mediod的對(duì)象來代替 K-MEANS 算法的中心對(duì)象的作用， medoid 就標(biāo)識(shí)了這個(gè)類。K-means 中心點(diǎn)取當(dāng)前聚類中所有數(shù)據(jù)點(diǎn)的平均值，而在 K-medoids 算法中，取當(dāng)前聚類中的點(diǎn)的距離之和最小的作為中心點(diǎn)。K-MEDOIDS 算法過程如下：

　? 從 n 個(gè)數(shù)據(jù)中任意選取 K 個(gè)對(duì)象數(shù)據(jù)作為 medoids；

　? 將余下的對(duì)象數(shù)據(jù)根據(jù)與 medoid 最相近的原則劃分到各個(gè) medoids代表的類；

　? 對(duì)于每個(gè)類中，順序選取一個(gè)數(shù)據(jù)，計(jì)算用該數(shù)據(jù)對(duì)象代替 medoids后的消耗 E，用消耗最少的代替 medoids 值，如此循環(huán)迭代直到 K個(gè) medoids 固定下來。

　這種算法對(duì)于臟數(shù)據(jù)和異常數(shù)據(jù)不敏感，但是在迭代計(jì)算 K 個(gè) medoids 值，算法的時(shí)間復(fù)雜度，計(jì)算量顯然很大，因此一般只適合小數(shù)據(jù)量聚類計(jì)算，不適用大數(shù)據(jù)的計(jì)算[7] 。

　③Clarans 算法[8]

　Clarans 算法是 K-MEDOIDS 算法基礎(chǔ)上的改進(jìn)算法，目的是改進(jìn) K-MEDOIDS算法在大數(shù)據(jù)量處理方面的性能。Clara 算法使用數(shù)據(jù)的抽樣來代替整個(gè)數(shù)據(jù)集合，在這些抽樣的數(shù)據(jù)上再利用 K-MEDOIDS 算法得到最佳的 medoids 值。Clarans算法將 K-MEDOIDS 算法的迭代計(jì)算分散在每個(gè)采樣上，從而使得 K-MEDOIDS 算法能夠處理大量的數(shù)據(jù)，其算法思想是將大的數(shù)據(jù)集拆分成小的數(shù)據(jù)集，類似于分布計(jì)算的思想，因此算法應(yīng)用在分布式計(jì)算平臺(tái)上效果更佳。

　(2) 文本 主題分布 算法 模型

　基于模型的方法給每一個(gè)聚類假定一個(gè)模型，然后去尋找一個(gè)能滿足這個(gè)模型的數(shù)據(jù)集，目標(biāo)數(shù)據(jù)集是由一系列的概率分布所決定的。以下比較了 LSA 和 LDA 兩種經(jīng)典主題分布算法。

　①LSA（Latent Semantic Analysis）[9]

　潛在語(yǔ)義分析算法采用 Bag of Word 模型假設(shè)，在已知一個(gè)文檔數(shù)據(jù)集及相應(yīng)的詞典 ，將數(shù)據(jù)集表示為一個(gè)的共生矩陣， ，其中， 表示詞典中的第 j 個(gè)單詞在第 i 個(gè)文檔中出現(xiàn)的次數(shù)。LSA 的基本思想就是，將文檔從稀疏的高維詞典

　空間映射到一個(gè)低維的向量空間，稱之為隱含語(yǔ)義空間(Latent Semantic Space)。

　LSA 的優(yōu)點(diǎn)在于：低維空間表示可以刻畫同義詞對(duì)應(yīng)著相同或相似的主題、降維可去除部分噪聲，充分利用冗余數(shù)據(jù)，無監(jiān)督并且完全自動(dòng)化，該算法與語(yǔ)言無關(guān)；而 LSA 的不足在于：沒有刻畫 term 出現(xiàn)次數(shù)的概率模型，無法解決多義詞的問題。

�、贚DA（Latent Dirichlet Allocation）[10]

　LDA 算法也采用 Bag of Words 的研究方式，將每一篇文檔視為一個(gè)詞頻向量，從而將文本信息轉(zhuǎn)化為了易于建模的數(shù)字信息。LDA 的思想是利用文本建模的生成模型，該模型可以隨機(jī)生成可觀測(cè)的數(shù)據(jù)，是一種非監(jiān)督機(jī)器學(xué)習(xí)技術(shù)，可以用來識(shí)別大規(guī)模文檔集或語(yǔ)料庫(kù)中潛藏的主題信息。在 LDA 的視角中每一篇文檔代表了一些主題所構(gòu)成的一個(gè)概率分布，而每一個(gè)主題又代表了很多單詞所構(gòu)成的一個(gè)概率分布。

　狄利克雷分布是概率組合出現(xiàn)概率的統(tǒng)計(jì)，通過隱藏主題的發(fā)現(xiàn)過程，從而得到每一篇文檔在不同主題下可能的概率分布。一篇文章可以包括多個(gè)不同的主題，但是每個(gè)主題得出可能的概率值不同。在一篇文章中某個(gè)主題的概率值，可以作為該主題該文本中主題突發(fā)的能量統(tǒng)計(jì)值，因此是基于文本流的主題爆發(fā)探測(cè)重要依據(jù)。

　3.2 2 爆發(fā)特征的 發(fā)現(xiàn) 算法 模型

　發(fā)現(xiàn)主題在時(shí)間維度上的變化特征的是爆發(fā)探測(cè)的關(guān)鍵環(huán)節(jié)。其主要思想是對(duì)其文本流的到達(dá)時(shí)間在時(shí)間維度上的分析計(jì)算，發(fā)現(xiàn)其突增，高漲，波動(dòng)，衰減等一系列的變化和分布特征，從而確定主題的爆發(fā)時(shí)間和爆發(fā)特點(diǎn)。爆發(fā)特征的發(fā)現(xiàn)算法起初不局限于用在文本流的發(fā)現(xiàn)上，而是在物理學(xué)對(duì)伽馬射線的爆發(fā)探測(cè)，或者經(jīng)濟(jì)學(xué)對(duì)股價(jià)的分析探測(cè)上，隨著網(wǎng)絡(luò)的發(fā)展，文本流的激增過程中，爆發(fā)特征探測(cè)也逐漸被引入到對(duì)文本流的探測(cè)任務(wù)中。爆發(fā)特征的發(fā)現(xiàn)算法主要有以下幾個(gè)方面：

　（1）基于閾值的爆發(fā)探測(cè)：爆發(fā)探測(cè)研究，在早期 Swan and Allan (1999, 2000) 和 Swan and Jensen (2000)等人就提出了基于閾值探測(cè)的方法，但是這

　種方法具有局限性，它可以探測(cè)到顯著的消息突發(fā)，但是對(duì)于短小連續(xù)的，類似于白噪聲的突發(fā)則難以探測(cè)到。Towards Burst Detection for Non-Stationary Stream Data 文章使用大綱結(jié)構(gòu)的轉(zhuǎn)移聚集樹與時(shí)間序列預(yù)測(cè)的相關(guān)技術(shù)相結(jié)合[11] ，提出了一種新的動(dòng)態(tài)確定適當(dāng)?shù)拈撝迭c(diǎn)的方法，通過實(shí)驗(yàn)發(fā)現(xiàn)這種方法對(duì)與線性的趨勢(shì)爆發(fā)探測(cè)處理比較適用。

�。�2）以“到達(dá)率”為依托的爆發(fā)探測(cè)：Kleinberg 在 Bursty and Hierarchical Structure in Streams 文章中提出了一種無限狀態(tài)自動(dòng)機(jī)的模型[12] ，根據(jù)突發(fā)消息的到達(dá)率而改變它的狀態(tài)，不管到達(dá)率如何變化可以在數(shù)據(jù)流中探測(cè)到長(zhǎng)期的范圍內(nèi)的突發(fā)變化。該算法設(shè)計(jì)了一個(gè)加權(quán)自動(dòng)機(jī)模型，充分考慮到低爆發(fā)率中包含高爆發(fā)率，遵照爆發(fā)率依賴于當(dāng)前的狀態(tài)的思路，由簡(jiǎn)單的二維狀態(tài)模型，引申為多維度無限狀態(tài)模型，根據(jù)到達(dá)率的變化自動(dòng)機(jī)改變當(dāng)前自身的狀態(tài)，從而自動(dòng)適應(yīng)爆發(fā)頻率。從而實(shí)現(xiàn)爆發(fā)特征的捕獲和探測(cè)。

　（3）基于窗口模型的爆發(fā)探測(cè)：在對(duì)多個(gè)領(lǐng)域的研究中使用的經(jīng)典窗口算法模型主要包括：里程碑窗口模型、滑動(dòng)窗口模型和阻尼窗口模型[13] 。這些模型的窗口大小是固定的，不能根據(jù)爆發(fā)到達(dá)率的變化而改變窗口的大小。紐約大學(xué)的 Yunyue Zhu 和 Dennis Shasha 在其論文 Efficient Elastic Burst Detection in Data Streams 中對(duì)經(jīng)典的固定大小窗口模型的局限性做了改進(jìn)，提出了彈性窗口爆發(fā)探測(cè)模型[14] 。彈性窗口算法實(shí)現(xiàn)類似小波分析的爆發(fā)監(jiān)測(cè)，該算法提出了一種 Haar 的小波樹層級(jí)數(shù)據(jù)結(jié)構(gòu)�；�于時(shí)間序列的數(shù)據(jù)流，可以分解成離散的數(shù)據(jù)塊，通過多個(gè)層級(jí)小波樹變化，在從低層級(jí)到高層級(jí)變換中，爆發(fā)數(shù)據(jù)會(huì)最終落入到一個(gè)窗口中，從而捕獲到爆發(fā)特征。文章提出一種變換小波樹（SWT）的算法，從而實(shí)現(xiàn)爆發(fā)特征更精確的定位。彈性窗口變換小波算法的優(yōu)勢(shì)在于：其利用離散數(shù)據(jù)流的特征，保存完整的信息，在小波變換中無信息損失；能夠監(jiān)測(cè)高維度的突發(fā)；算法執(zhí)行效率高出傳統(tǒng)統(tǒng)計(jì)型算法，幾十個(gè)數(shù)量級(jí)，達(dá)到 O（n）的時(shí)間復(fù)雜度，方便大數(shù)據(jù)量的分析和爆發(fā)特征的檢索。

�。�4）聚集金字塔爆發(fā)探測(cè)算法[15] ：Better Burst Detection 一文對(duì)變換小波樹或者簡(jiǎn)單的變換二元樹會(huì)將很多事件窗口可能被錯(cuò)誤的標(biāo)注為爆發(fā)點(diǎn)的問題做出了改進(jìn)，提出了聚集金字塔爆發(fā)探測(cè)算法。整個(gè)算法框架基于稱為聚集金字塔（aggregation pyramid）的密集數(shù)據(jù)結(jié)構(gòu)構(gòu)建，框架中的所有數(shù)據(jù)結(jié)構(gòu)都

　包含了聚集金字塔單元的子集，在此數(shù)據(jù)機(jī)構(gòu)基礎(chǔ)上，采用一種啟發(fā)式的檢索算法從眾多的結(jié)構(gòu)中發(fā)現(xiàn)最有效的幾個(gè)，并給予對(duì)應(yīng)的輸入。通過對(duì)合成的數(shù)據(jù)和實(shí)際環(huán)境中的數(shù)據(jù)的實(shí)驗(yàn)發(fā)現(xiàn)，依據(jù)數(shù)據(jù)的分布，與變動(dòng)二元樹相比有很大的改進(jìn)效果。

　（5）動(dòng)力學(xué)加速度探測(cè)模型[16] ：主題動(dòng)力學(xué)模型是建立在物理學(xué)的質(zhì)量和速度—動(dòng)力學(xué)概念基礎(chǔ)上的，它的思想是將文本流的到達(dá)率看作是物理上能量的積累，引入物理學(xué)的動(dòng)量、加速度、勢(shì)能等概念，和物理學(xué)的思想，并將爆發(fā)看作一個(gè)物理學(xué)的動(dòng)態(tài)現(xiàn)象，是一段時(shí)間內(nèi)動(dòng)量的增加。該模型構(gòu)建了一個(gè)主題的加速度動(dòng)態(tài)模型，基于該模型分析判斷主題的爆發(fā)特征。

　4 4 算法 對(duì)比與 應(yīng)用 分析

　從 Kleinberg 基于詞頻統(tǒng)計(jì)的爆發(fā)特征探測(cè)算法，到 LDA 等基于主題分布的提取，發(fā)現(xiàn)主題的探測(cè)。從基于閾值的突發(fā)監(jiān)測(cè)方法，通過改進(jìn)和演化發(fā)展到無限狀態(tài)自動(dòng)機(jī)、彈性窗口、金字塔模型、動(dòng)力學(xué)模型等。并不能簡(jiǎn)單的說明算法的優(yōu)點(diǎn)和缺點(diǎn)，在不同的應(yīng)用場(chǎng)景下對(duì)信息失真度、爆發(fā)點(diǎn)定位的準(zhǔn)確度、算法效率等要求各不相同，只有結(jié)合爆發(fā)探測(cè)的研究?jī)?nèi)容和實(shí)際應(yīng)用環(huán)境，才能對(duì)算法做出實(shí)用性的選擇。

　1 4.1 數(shù)據(jù)流 的 信息 保真度

　 主題結(jié)構(gòu)判斷中，不同聚類的算法對(duì)原始信息的表示都有一定的損失，本文稱為信息的保真度。在以上算法中對(duì)信息的真實(shí)度還原表現(xiàn)不同的效果。文本主題聚類方法，例如 k-means 算法，可以根據(jù)預(yù)先設(shè)定對(duì)文本流聚類出 k 個(gè)主題分類。K 個(gè)主題分類中雖然有排序，但是沒有完整的包含每個(gè)主題對(duì)爆發(fā)探測(cè)貢獻(xiàn)能量的多少，如圖 1 所示，k-means 算法只保留了最大可能的主題 2 能量貢獻(xiàn)，而過濾掉其他主題的能量貢獻(xiàn)能力，因此在后續(xù)計(jì)算爆發(fā)特征的時(shí)候，會(huì)造成計(jì)算量化的偏差。而 LDA 等主題分布模型，是概率組合出現(xiàn)概率的統(tǒng)計(jì)，在一個(gè)文本流中某個(gè)主題可能的概率值，如圖 2 所示，在每個(gè)主題分布上的分布概率，可以作為該主題該文本中主題突發(fā)的能量統(tǒng)計(jì)值[17] ，因此在主題爆發(fā)量化的統(tǒng)計(jì)計(jì)

　算中，復(fù)雜的主題分布模型更具有信息的保真度。

　圖 1 k-means 主題能量貢獻(xiàn)

　圖 2 LDA 主題能量貢獻(xiàn)

　在爆發(fā)特征探測(cè)計(jì)算過程中，彈性窗口爆發(fā)探測(cè)模型和聚集金字塔爆發(fā)探測(cè)模型，都使用了小波變換樹來提高爆發(fā)特征探測(cè)的準(zhǔn)確性。由于在小波變換算法中，可以做到無信息損失，因此該類算法模型相對(duì)閾值分析和固定窗口模型的算法，有較高的信息爆發(fā)特征的保真性，這也是彈性窗口變換小波算法主要優(yōu)點(diǎn)之一[14] 。

　4.2 爆發(fā)特征 計(jì) 算 的 準(zhǔn)確性

　 在可見的爆發(fā)特征中可能分布著微小的潛在爆發(fā)特征，例如閾值探測(cè)方法中提到的“白噪聲爆發(fā)特征”；Kleinberg 無限狀態(tài)自動(dòng)機(jī)模型中提到的“低爆發(fā)率中包含高爆發(fā)率”；Yunyue Zhu 和 Dennis Shasha 彈性窗口模型的研究稱為“高維度爆發(fā)特征”。說明這種隱含爆發(fā)特征的準(zhǔn)確定位是難度較大的，對(duì)這種高維度的爆發(fā)特征的探測(cè)是對(duì)幾種算法模型的考驗(yàn)�；�于窗口閾值的爆發(fā)探測(cè)方法，在處理復(fù)雜的高緯度爆發(fā)有很多局限性，如圖 3 所示。

　 圖 3 窗口閾值探測(cè)低維度爆發(fā)特征[13]

　圖 4 變幻小波樹高維度爆發(fā)特征模型[14]

　 無限狀態(tài)自動(dòng)機(jī)算法中，考慮高維度爆發(fā)而對(duì)現(xiàn)有算法做出改進(jìn)。而彈性窗口小波變換算法在從低層級(jí)到高層級(jí)可以捕捉到落到高層級(jí)窗口的爆發(fā)特征，如圖 4 所示。因此小波變換算法自身有利于捕捉到高維度的爆發(fā)特征[14] 。此外，爆發(fā)特征的窗口邊界因素可能被誤判為突發(fā)特征，也是硬性爆發(fā)特征準(zhǔn)確性的重要因素。聚集金字塔爆發(fā)探測(cè)算法的重要改進(jìn)即克服了變換小波樹或者簡(jiǎn)單的變換

　二元樹會(huì)將很多事件窗口可能被錯(cuò)誤的標(biāo)注為爆發(fā)點(diǎn)的問題。

　3 4.3 算法 的 執(zhí)行效率 與應(yīng)用場(chǎng)景

　長(zhǎng)文本的文本流的主題爆發(fā)探測(cè)，由于單個(gè)文本信息豐富，容易從其中提取出反應(yīng)的主題信息，因此更實(shí)用 LDA 等復(fù)雜 bag of word 的文本主題分布算法，列舉出主題分布律，文本流中的主題分布概率將作為爆發(fā)探測(cè)中的主題能量，實(shí)現(xiàn)主題爆發(fā)探測(cè)。這種算法模型在計(jì)算效果和執(zhí)行效率上并不一定適合高速的短文本流應(yīng)用，如常用的 SNS 社交網(wǎng)絡(luò)的評(píng)論信息，論壇，微博等[18] 。

　對(duì)于高速的短文本流的爆發(fā)主題探測(cè)中，較為復(fù)雜的 LDA 等主題分布模型表現(xiàn)并不良好。在 Online Burst Detection Over High Speed Short Text Streams一文中對(duì)高速文本流提出了一種簡(jiǎn)單的時(shí)間概率判斷模型[19] ，并通過一系列的試驗(yàn)數(shù)據(jù)，證明了簡(jiǎn)單時(shí)間概率判斷模型相對(duì)于 von-Mises Fisher (vMF)的混合模型和潛在狄利克雷分布(Latent Dirichlet Allocation，LDA) 的主題分布模型在處理高速短文本流的效率上的優(yōu)勢(shì)。

　5 5 結(jié)語(yǔ)

　 爆發(fā)主題探測(cè)涉及到文本流的主題結(jié)構(gòu)的判定和爆發(fā)特征的發(fā)現(xiàn)兩個(gè)方面的關(guān)鍵問題。針對(duì)兩個(gè)關(guān)鍵問題研究分析其中主要算法的思想和優(yōu)缺點(diǎn)，在信息保真度、爆發(fā)特征準(zhǔn)確性、執(zhí)行效率三個(gè)方面對(duì)幾種典型算法進(jìn)行比較分析。由于不同的算法在效率，文本和參數(shù)依賴性等方面各有不同特性，在不用的應(yīng)用場(chǎng)景下，也衍生出相應(yīng)適用于特定環(huán)境的算法模型。因此在算法的選擇上需根據(jù)文本流特征、信息保真度要求、以及文本流到達(dá)頻率所要求的算法效率等多方面綜合考慮，選取適用的算法模型。

　參考文獻(xiàn) ：

　[1] Chen W, Chundi P. Extracting hot spots of topics from time-stamped documents[J]. Data & Knowledge Engineering, 2011, 70(7): 642-660,

　[2] Wayne Xin Zhao, Jing Jiang, Jing He, Dongdong Shan, Hongfei Yan, Xiaoming Li. Context modeling for ranking and tagging bursty features in text streams[C]. International Conference on Information and Knowledge Management, 2010: 1769-1772

　[3] Wei Chen, Parvathi Chundi. Extracting Hot Spots of Basic and Complex Topics From Time Stamped Documents[C]. IEEE Symposium on Computational Intelligence and Data Mining, 2009: 125-132

　[4] Yiu-ming Cheung, k*Means: A new generalized k-means clustering algorithm[J]. Pattern Recognition Letters, 2003, 24(15):2883-2893 [5]MacQueen, J. B. Some Methods for classification and Analysis of Multivariate Observations[J]. University of California Press. 2009, 4(4): 281–297. [6]H.S. Park , C.H. Jun. A simple and fast algorithm for K-medoids clustering[J], Expert Systems with Applications, 2009, 36(2):3336-3341. [7]T. Velmurugan and T. Santhanam. Computational Complexity between K-Means and K-Medoids Clustering Algorithms for Normal and Uniform Distributions of Data Points, Journal of Computer Science[J] 2010(3), 363-368. [8]Raymond T. Ng, Jiawei Han. CLARANS: A Method for Clustering Objects for Spatial Data Mining[J]. IEEE Transactions on Knowledge and Data Engineering, 2002.14(5):1003-1016

　[9] Peter Wiemer-Hastings, Latent Semantic Analysis[J]. Information Science and Technology,

　2004, 38(1): 188–230 [10] David M. Blei, Andrew Y. Ng, Michael I. Jordan. Latent Dirichlet Allocation[J]. Journal of Machine Learning Research, 2003(3): 993-1022 [11] Daniel Klan, Marcel Karnstedt, Christian Pölitz, Kai-uwe Sattler. Towards Burst Detection for Non-Stationary Stream Data[C]. Lernen, Wissensentdeckung und Adaptivitat, 2008: 57-60 [12] Jon M. Kleinberg. Bursty and Hierarchical Structure in Streams[C]. Data Mining and Knowledge Discovery, 2003:91-101 [13] Srivatsan Laxman, P. S. Sastry, K. P. Unnikrishnan. A Fast Algorithm for Finding Frequent Episodes in Event Streams[C]. Knowledge discovery and data mining, 2007:410-419 [14] Yunyue Zhu, Dennis Shasha. Efficient Elastic Burst Detection in Data Streams[C]. Knowledge discovery and data mining, 2003: 336-345 [15] Xin Zhang Dennis Shasha. Better Burst Detection[C]. Data Engineering, ICDE, 2006 [16] Satoshi Morinaga, Kenji Yamanishi. Tracking dynamics of topic trends using a finite mixture model[C]. Knowledge discovery and data mining, 2004:811-816 [17] Dan He, D. Stott Parker. Topic Dynamics: an alternative model of "Bursts" in Streams of Topics[C]. Knowledge discovery and data mining, 2010:443-452 [18] Michael Mathioudakis, Nick Koudas. Twitter Monitor : Trend Detection over the Twitter Stream[C]. International Conference on Management of Data , 2010:1155-1158 [19] Zhijian Yuan, Yan Jia, Shuqiang Yang. Online Burst Detection Over High Speed Short Text Streams[C]. International Conference on Computational Science, 2007:717-725

相關(guān)熱詞搜索：探測(cè) 算法 爆發(fā)