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

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

　 謝靖 中國科學院國家科學圖書館

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

　[ [ 分類號] ] TP393 [ [ 關鍵字] ] 爆發(fā)探測

　主題聚類

　爆發(fā)特征

　算法對比分析 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 引言

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

　 ? 本文系國家社會科學基金項目“網絡科技信息中爆發(fā)主題的監(jiān)測與分析方法研究”（項目編號：09BTQ035）的研究成果之一。

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

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

　2 2 爆發(fā)探測 的 關鍵 問題

　1 2.1 主題結構的判定

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

　2.2 2 爆發(fā)特征 發(fā)現

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

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

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

　3 3 爆發(fā)探測 相關 算法 研究

　3.1 1 主題結構判定 算法模型

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

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

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

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

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

　K-MEANS 算法的特點是采用測度函數計算均方差，使得聚類內部各對象距離最小，各類之間的對象距離盡可能最大，已達到聚類的最佳效果。K-MEANS 算法的缺點是生成的聚類結果對于臟數據很敏感，臟數據的存在會引起較大的聚類誤差[5] 。

�、贙-MEDOIDS 算法[6]

　由于 K-MEANS 算法對臟數據敏感的缺點，K-MEDOIDS 算法選取一個 mediod的對象來代替 K-MEANS 算法的中心對象的作用， medoid 就標識了這個類。K-means 中心點取當前聚類中所有數據點的平均值，而在 K-medoids 算法中，取當前聚類中的點的距離之和最小的作為中心點。K-MEDOIDS 算法過程如下：

　? 從 n 個數據中任意選取 K 個對象數據作為 medoids；

　? 將余下的對象數據根據與 medoid 最相近的原則劃分到各個 medoids代表的類；

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

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

�、跜larans 算法[8]

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

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

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

�、貺SA（Latent Semantic Analysis）[9]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　4 4 算法 對比與 應用 分析

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

　1 4.1 數據流 的 信息 保真度

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

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

　圖 1 k-means 主題能量貢獻

　圖 2 LDA 主題能量貢獻

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

　4.2 爆發(fā)特征 計 算 的 準確性

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

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

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

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

　二元樹會將很多事件窗口可能被錯誤的標注為爆發(fā)點的問題。

　3 4.3 算法 的 執(zhí)行效率 與應用場景

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

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

　5 5 結語

　 爆發(fā)主題探測涉及到文本流的主題結構的判定和爆發(fā)特征的發(fā)現兩個方面的關鍵問題。針對兩個關鍵問題研究分析其中主要算法的思想和優(yōu)缺點，在信息保真度、爆發(fā)特征準確性、執(zhí)行效率三個方面對幾種典型算法進行比較分析。由于不同的算法在效率，文本和參數依賴性等方面各有不同特性，在不用的應用場景下，也衍生出相應適用于特定環(huá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

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