一種基于劃分的周期性話題挖掘方法研究

鄧定勝

一種基于劃分的周期性話題挖掘方法研究

鄧定勝

周期性話題挖掘是目前數(shù)據挖掘領域的研究熱點之一，針對當前絕大部分研究只限于時間序列數(shù)據庫、無法直接應用于文本數(shù)據的不足，提出了一種基于劃分的周期性話題挖掘方法（PTMP），首先，將話題劃分為周期性話題、背景話題和突發(fā)性話題，然后，將每個周期性話題的時標分布建模為混合高斯分布，為了緩解背景噪聲問題，通過均勻分布生成背景話題的時標，用高斯分布來生成突發(fā)話題的時標，然后通過將該混合模型根據時標文本數(shù)據進行調整，從而發(fā)現(xiàn)周期性話題及其時間分布。最后，收集了包括研討會、DBLP和Flickr在內的多個代表性數(shù)據集，驗證方法的有效性。

周期性話題；數(shù)據挖掘；混合高斯分布；噪聲；時標

0 引言

隨著Web技術的發(fā)展，許多文本數(shù)據帶有時間信息，比如新聞帶有發(fā)布日期，F(xiàn)lickr照片帶有拍照日期（http://www.flickr.com），Twitter（http://twitter.com）上發(fā)布的tweet帶有上傳時間。這些文本數(shù)據蘊含了許多有用信息。發(fā)現(xiàn)周期性話題并描述它們的時間模式，是個非常有趣的課題。由于周期性分析的重要性，人們針對時間序列數(shù)據庫進行了周期性檢測研究[1,2]。一些研究為了檢測周期性模式，在分析單個標記或單次查詢的時間分布時使用的策略非常類似[3]。然而，當前絕大部分研究只限于時間序列數(shù)據庫，無法直接應用于文本數(shù)據。首先，一個詞組并不足以描述一個話題，只有更多的詞組才能全面概括一個話題。其次，只對單個詞組進行分析并不足以發(fā)現(xiàn)周期性話題。例如，“音樂”、“節(jié)日”、“芝加哥”等詞組如果單獨考慮，不會展現(xiàn)出周期性模式，但如果綜合考慮則可能存在周期性話題。第三，由于語言的多樣性，存在許多同義詞和多義詞，這讓周期性話題檢測更加困難。

本文提出PTMP方法來處理以上問題。本文方法不是根據單個詞組或模式出現(xiàn)的周期性展開分析，而是利用了詞組的周期性及共生性，進而檢測出以詞組分布為載體的周期性話題。本文貢獻總結如下：（1）首次引入潛在周期性話題分析問題。（2）提出PTMP模型，通過利用詞組的周期屬性及共性結構來檢測周期性話題。（3）基于多個代表性數(shù)據集進行全面的實驗，證明了本文算法的有效性。

1 相關工作

相繼有眾多學者提出了一系列方法用于解決周期性話題挖掘問題。如Mei等人[4]將時線分割為多個儲體，并提出概率算法對網絡博客的子話題主題和時空主題模式同時建模。Wang等人[5]從同等處理過后的文本流中挖掘相關的突發(fā)話題模式。Blei等[6]針對話題多項式分布的自然參數(shù)使用了狀態(tài)空間模型，設計了一種動態(tài)話題模型，以模擬文件流的時間進化情況。Iwata等人[7]提出了一種在線話題模型，可依次分析文檔集合話題的時間進化情況，該模型假設根據上一時間的多尺度詞匯分布生成了具體話題的當前詞匯分布。Lahiri等人[8]提出了如何在動態(tài)社交網絡中檢測周期性或近似周期性子圖這一新的數(shù)據挖掘問題。Murata等人[9]根據搜索意圖數(shù)量及其時間特性來對檢索分類，然后對每個搜索意圖的比例進行離散傅立葉變換，以檢測出周期性變化。然而，這些研究只分析了單個詞匯的分布。本文則采用更為系統(tǒng)的方式，對潛在周期性話題分析進行建模，每個話題用詞匯分布表示。然后，從話題而非單個詞匯角度分析周期性模式，并對周期性突發(fā)情況及其對應話題實現(xiàn)了同步檢測，而不是分步進行。

2 問題建模

本節(jié)將對潛在周期性話題分析問題進行定義。本文所用標記法如表1所示：

表1 本文采用的標記法

定義1：話題是指具有語義條理性的一種主題，它通過詞組的多項式分布表現(xiàn)出來。一般地，每個話題z可表示為如下詞組分布：

定義2：周期性話題 是指定期重復的一種話題。給定話題z且時間t時的條件概率遵守周期性間隔為T的周期性模式。換句話說，每個話題的時標分布每隔時間T展現(xiàn)一次。周期性間隔T可由用戶根據自身需要確定，可以是1周、1月、1年，等等。

定義3：時標文檔 是指帶有時標的文本文檔。它可以是帶有發(fā)布時期的新聞，帶有發(fā)布時期的Twitter網上的鳥叫聲，也可以是帶有上傳日期的Flickr網上的照片，此時照片上的標記可以看成是文本，照片的拍攝時間可以看成是照片的時標。

有了時標文件和周期性話題定義后，本文可以定義潛在周期性話題分析如下：

定義4：給定一組時標文檔D，周期性間隔T，話題數(shù)量K，我們希望發(fā)現(xiàn)每隔時間T便重復一次的K個周期性話題，即其中Z為話題集合，時間分布

3 潛在周期性話題分析

本節(jié)給出PTMP模型。首先，介紹本文模型的總體思路。然后，詳細介紹本文周期性話題生成過程。最后，解釋如何估計參數(shù)。

3.1 總體思路

我們將每個周期性話題的時標分布建模為混合高斯分布，其中兩個連續(xù)部分的間隔為T。除了周期性話題外，文檔集合可能包括背景詞匯。為了緩解背景噪聲問題，我們在模型中對背景話題進行了建模。尤其地，通過均勻分布生成背景話題的時標。除了周期性話題和背景話題外，我們使用突發(fā)話題來模擬短時間而非經常性的突發(fā)行為模式。用高斯分布來生成突發(fā)話題的時標。因此，文檔集合建模為背景話題、突發(fā)話題、周期性話題的混合。通過將該混合模型根據時標文本數(shù)據進行調整，我們可以發(fā)現(xiàn)周期性話題及其時間分布。

3.2 PTMP方法

（1）從多項式dφ中采樣一個話題z。（a）如果z是背景話題，則從均勻分布中采樣時間t，其中tstart和是文檔集合的開始和截止時間。（b）如果z是突發(fā)話題，從采樣t。（c）如果z是周期性話題，從均勻分布中采集文檔d的周期k，從采集時間t，其中T是周期性間隔。

（2）從多項式zθ采集一個詞匯w。若有數(shù)據集合，其中wd是文檔d的詞匯集合，td是文檔d的時標，時的集合對數(shù)似然概率為公式（1）、（2）：

其中，n( d, w)是文檔d中詞匯w的數(shù)量。

3.3 參數(shù)估計

為了估計等式1中的參數(shù)Ψ，我們使用最大期望估計（EM）算法[6]來解決問題，循環(huán)計算似然局部最大值。本文引入隱藏參數(shù)概率表示文檔d詞匯w屬于話題z的概率。在步驟E時，它計算完整似然期望值，其中是在第t次迭代時w的估計值。在步驟M時，它可以獲得使完整似然期望最大化的估計值

如果z是突發(fā)話題，zμ和zσ做如下更新為公式（9）、（10）：

如果話題z是周期性話題，我們將時間線分為長度為T的多個間隔，并假設每個文檔只與對應的間隔有關。換句話說，如果文檔d未在第k個間隔，則式5中的設為0。周期性話題z的zμ和zσ做如下更新為公式（11）、（12）：

其中，Id是文檔d的對應間隔。

4 實驗

4.1 數(shù)據集

本文基于多個數(shù)據集來評估所提方法：

1）研討會數(shù)據。我們收集了伊利諾斯州大學（http://cs.illinois.edu/）計算機專業(yè)6個研究小組一個學期內的每周研討會聲明。6個研究小組的研究內容包括AIIS（人工智能和信息系統(tǒng)），DAIS（數(shù)據庫和信息系統(tǒng)），圖像，HCI，理論和UPCRC（通用并行計算研究中心）。研討會時間作為文檔時標。為了確定每周話題，本文把周期間隔設為1周。該研討會數(shù)據集共有61個文件和901個詞匯。

2）數(shù)字目錄工程DBLP數(shù)據。它是基于計算機科學的目錄項目。我們收集了2010到2013年不同會議的論文題目。會議包括WWW, SIGMOD, SIGIR, KDD,VLDB和NIPS。根據項目安排確定文檔的時標。為了發(fā)現(xiàn)年度話題，本文設置周期性間隔T為1年。該DBLP數(shù)據集有4070個文檔和2132個詞匯。

3） Flickr。Flickr是一個在線照片共享網站。從Flickr API（http://www.flickr.com/services/api/）選擇照片。照片標記作為文檔文本，照片拍攝時間作為文檔時標。根據實際情況，本文選擇了2009到2013年間多個音樂會的照片，例如SXSW (South by Southwest), Coachella, Bonna-roo,Lollapalooza和ACL (Austin City Limits)等。我為了發(fā)現(xiàn)年度話題，設置周期間隔為1年。該數(shù)據集共有84244個文檔和7524個詞匯。

4.2 定量評估

（1）PTMP話題檢測：結合數(shù)據集構建情況，我們分別設置研討會、DBLP和Flickr的周期性話題數(shù)據為6、6、5。如表2所示：

表2 基于PTMP的部分周期性話題檢測。日期和括號中的持續(xù)時間是對應周期性話題時標的均值和標準差。

PTMP在不同數(shù)據集檢測出來的部分話題。對研討會數(shù)據集，PTMP可以有效檢測不同研究小組的話題及其對應時間。例如，第一個話題是DAIS，每周二下午4點，主流詞匯為數(shù)據、文本和挖掘。第二個話題是AIIS，每周5下午兩點，主要內容是機器學習和算法。對DBLP數(shù)據集，PTMP可以檢測出6個周期性話題，也就是6個年度會議。例如，第一個話題是8月的KDD，議題是數(shù)據挖掘。第二個話題是SIGIR，主要議題是數(shù)據檢索、網絡、搜索、相關性和評估。對Flickr數(shù)據集，PTMP可以有效檢測出音樂節(jié)及其持續(xù)時間。

（2）PTMP VS周期性檢測。為了證明把相關詞匯放在一起檢測比各個詞匯單獨分析更為合理，我們對PTMP和周期性檢測算法做一對比。與單個詞匯表示相比，PTMP使用多個詞匯描述話題，如表3所示：

表3 不同數(shù)據集使用PTMP和LDA時被檢測出來的部分話題

例如，對DBLP數(shù)據集，PTMP發(fā)現(xiàn)話題VLDB時的詞匯分布為data 0.0530, xml 0.0208, query 0.0196, queries 0.0176,efficient 0.0151, mining 0.0142, database 0.0136, streams 0.0112, databases 0.0111。我們可以看出，單個詞匯并不足以表示這樣一個話題，只有多個詞匯才能更好表示。PTMP不僅可以更全面的描述話題，還可以當組成詞匯單獨考慮不具有周期性模式時檢測出周期性話題。對PTMP，我們可以根據和文件時標，繪出檢測話題的時間分布，其中可以根據貝葉斯理論由獲得。如圖1所示：

圖1 基于PTMP檢測的話題VLDB的時間分布及話題詞匯的時間分布

我們可以繪出DBLP數(shù)據集VLDB話題的時間分布及話題最流行詞匯data、xml、query的時間分布。我們可以看出，話題VLDB的周期性模式非常清晰，而詞匯data、xml、query沒有周期性出現(xiàn)。這表明，即使周期性話題的組成詞匯本身沒有周期性，PTMP也可以有效檢測出這些周期性話題。

（3）PTMP VS 話題模式。為了研究傳統(tǒng)話題模型能否檢測出有意義話題，我們對話題建模算法結果進行比較，包括PLSA、LDA和PTMP。對PLSA和LDA，我們設置研討會、DBLP和Flickr數(shù)據集的話題數(shù)量分別為5、5、6?；赑LSA和LDA的部分話題如表4所示：

表4 使用PTMP時周期性及突發(fā)性數(shù)據集的話題檢測。

由于計算機領域詞匯的相關度非常高，PLSA和LDA無法檢測出研討會數(shù)據集不同研究領域的話題。對DBLP數(shù)據集，所有的話題非常類似，導致PLSA和LDA無法檢測出有意義的話題群組。對Flickr數(shù)據集，PLSA混合了幾個音樂節(jié)。例如，話題1包括southbysouthwest和coachella，話題2包括lollapalooza和austincitylimits。我們發(fā)現(xiàn)，LDA在該數(shù)據集上的表現(xiàn)要優(yōu)于PLSA。即使話題1混合了coachella和bonnaroo，LDA也可以檢測出不同的節(jié)日。與表2中的PTMP相比，我們可以發(fā)現(xiàn)，PTMP檢測出來的有意義話題的質量更高。

（5）周期性話題 VS 突發(fā)性話題。為了驗證PTMP方法對周期性話題和突發(fā)性話題的平衡性能，本文對Flickr數(shù)據集的以下情況進行研究。我們沒有將與音樂節(jié)有關的所有照片混在一起，而是只保存了2006-2010年間的SXSW和ACL及2009年的Coachella和Lollapalooza音樂節(jié)的照片。于是，我們模擬了帶有2個周期性話題和2個突發(fā)性話題的數(shù)據集情況。對PTMP，我們將周期性話題和突發(fā)性話題數(shù)據均設為2，并在表4中給出了被檢測出來的話題名稱。從表5中可以看出，每年出現(xiàn)時間比較類似的詞匯，比如sxsw和acl，屬于兩種對應的周期性話題（即話題1和話題2），而只在某段時間才會出現(xiàn)的詞匯，比如lollapalooza、chicago、grantpark、illinois、coachella、indio、california，屬于兩種對應的突發(fā)性話題（即話題3和話題4）。PTMP可以區(qū)分該數(shù)據集的突發(fā)性話題和周期性話題。周期性話題SXSW和ACL的平均日期為每年的3月18日和9月28日，突發(fā)性話題Lollapalooza和Coachella的平均日期為2009年的8月8日和4月17日。

（6）小結。從以上定量分析可以看出，與針對單個詞匯的周期性檢測相比，PTMP不僅可以更全面的描述話題，還可以當周期性話題的構成詞匯單獨分析不具有周期性模式時，檢測出周期性話題。與PLSA和LDA話題建模算法相比，PTMP可以檢測出更具語義的周期性話題。此外，PTMP還可以有效檢測出每個周期性話題的平均日期和標準差。我們從DBLP的SIGMOD vs. VLDB及SIGMOD vs. CVPR數(shù)據集可以看出，如果沒有綜合文本和時間信息，則難以檢測出有意義的話題；同時可以看出，PTMP在二者間實現(xiàn)了很好的平衡。對于周期性話題和突發(fā)性話題間的折衷，我們從Flickr網站周期性話題VS突發(fā)性話題示例中可以看出，具有周期性或突發(fā)性模式的詞匯將隸屬于對應的周期性或突發(fā)性話題。

5 總結

本文引入了帶有時標的文檔的潛在周期性話題分析問題。提出了PTMP潛在周期性話題分析模型，既利用了詞匯周期性，又利用了詞匯共生性。在測試本文算法時，收集了研討會、DBLP和Flickr等幾個代表性數(shù)據集。評估結果表明，本文PTMP模型綜合了話題聚類和周期性模式信息，可以有效檢測出潛在周期性話題。周期性分析是網絡挖掘和社交媒體挖掘的重要課題。下步工作中，我們將重點研究如何對本文結論進行拓展，以應對不斷增加的網絡文檔數(shù)量和日趨復雜的社交媒體結構。

[1] Vlachos M, Yu P, Castelli V. On periodicity detection and structural periodic similarity[C]. SIAM International Conference on Data Mining. 2005: 449-460

[2] Bathoorn R, Welten M, Richardson M, et al. Frequent episode mining to support pattern analysis in developmental biology[M]. Pattern Recognition in Bioinformatics. Springer Berlin Heidelberg, 2010: 253-263

[3] Chen L, Roy A. Event detection from flickr data through wavelet-based spatial analysis[C]. Proceedings of the 18th ACM conference on Information and knowledge management. ACM, 2009: 523-532

[4] Mei Q, Liu C, Su H, et al. A probabilistic approach to spatiotemporal theme pattern mining on weblogs[C]. Proceedings of the 15th international conference on World Wide Web. ACM, 2006: 533-542

[5] Wang X, Zhai C X, Hu X, et al. Mining correlated bursty topic patterns from coordinated text streams[C]. Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2007: 784-793

[6] Blei D M. Probabilistic topic models [J]. Communications of the ACM, 2012, 55(4): 77-84

[7] Iwata T, Yamada T, Sakurai Y, et al. Online multiscale dynamic topic models[C]. Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2010: 663-672

[8] Lahiri M, Berger-Wolf T Y. Periodic subgraph mining in dynamic networks [J]. Knowledge and information systems, 2010, 24(3): 467-497

[9] Murata M, Toda H, Matsuura Y, et al. detecting periodic changes in search intentions in a search engine[C]. Proceedings of the 19th ACM international conference on Information and knowledge management. ACM, 2010: 1525-1528

Research on A Periodic Topic Ming Method Based on Partition

Deng Dingsheng
(Computer Science Department, Sichuan University Nationalities, Kangding 626001, China)

Periodic topic mining is a hot problem of current research in the data mining region. Aiming at the disadvantages of most existing studies which are limited to time series database and cannot be applied on text data directly, this paper proposes a periodic topic mining method based on partition, firstly, topics can be classified into three types: periodic topics, background topics, and bursty topics, we model the distribution of time-stamps for each periodic topic as a mixture of Gaussian distributions, in order to alleviate the problem of background noises, the time-stamps of the background topics are generated by a uniform distribution, the time-stamps of the bursty topics are generated from a Gaussian distribution, and then By fitting such a mixture model to time-stamped text data, we can discover periodic topics along with their time distributions. To show the effectiveness of our model, we collect several representative datasets including Seminar, DBLP and Flickr.

Periodic Topic; Data Ming; Mixture of Gaussian Distributions; Noise; Time-Stamps

TP391

A

2014.06.05)

鄧定勝（1978-），男，四川廣安人，四川民族學院計算機科學系，碩士，講師。研究方向：軟件體系結構，算法分析與程序設計，康定，626001

1007-757X(2014)08-0021-06