基于個人微博特征的事件提取研究

高永兵　陳　超　熊振華　王　宇　馬占飛

(內蒙古科技大學信息工程學院　內蒙古 包頭 014010)

?

基于個人微博特征的事件提取研究

高永兵陳超熊振華王宇馬占飛

(內蒙古科技大學信息工程學院內蒙古 包頭 014010)

摘要個人微博在事件提取上大多都是運用文本進行相似度計算最終達到聚類結果，而沒有充分的考慮到微博特征。針對微博標簽、URL、時間等特征，提出一種基于微博特征的事件提取算法。該算法針對微博的特征進行TF-IDF的改進，并加入標簽相似度，URL相似度，進行綜合相似度計算，最后按時間先分段后合并的改進K-means聚類方法得出事件提取結果。實驗結果表明，基于微博特征的事件提取算法對微博關鍵字提取和事件提取的精確度有明顯的提高。

關鍵詞微博特點事件提取綜合相似度

0引言

在這個信息飛速發展的年代，我們渴望了解我們感興趣的人和事。企業想了解自己的競爭對手，公司員工想了解老板的信息，追星族想了解自己喜歡的明星，個人想了解自己的親戚朋友的近況。微博由此承載著我們個人的想法而誕生。

微博作為一種新型的社交網絡工具發展急速，用戶可以通過Web、移動客戶端等途徑將自己日常生活的點點滴滴發布并和大家分享。個人發表的微博以140(本文以新浪微博為主)為字數上限，并加入標題、表情、URL、圖片等豐富的信息。因為微博這種開放性的特點，使得它的用戶劇增。

隨著微博的快速發展，微博的歷史信息量也越來越大，加上微博獨特的特征，這使得我們在想了解我們感興趣的人和事情的時候困難加劇。所以本文根據微博的特征，進行事件提取研究，實驗也充分證明了本文算法的有效性。

1相關工作

針對微博事件提取的問題，國內外學者做了大量的研究。1) 改進的TF-IDF方法。Phuvipadawat等[1]首先用 TF-IDF方法將文本轉換到向量空間模型中，并提出了一種基于命名實體加權的改進TF-IDF方法；周炎濤等[2]引入了信息熵與信息增益的概念，用以解決詞語在類別間的分布不均；張保富等[3]考慮到特征項在類間和類內的分布情況的不足，提出一種結合信息熵的 TF-IDF改進方法。2) 微博分段的方法。Li等[4]提出了基于分段的Tweets事件檢測算法。3) 基于索引的方法。姚俊杰等[5]提出了基于索引結構的方法。4) 主題模型的方法。Li等[6]提出了基于時間線的LDA綜合模型方法。5) 基于微博摘要的算法。童薇等[7]提出了基于EDM的事件提取和摘要算法，Sharifi[8]提出一種微博自動分類算法。6) 主題模型的聚類算法。王春龍等[9]提出了主題模型的K-means算法。基于上述方法沒有充分考慮到微博的特征的問題，本文把微博特征進行細化，把微博的部分特征加入到TF-IDF的改進中。通過改進的TF-IDF提取出關鍵詞，再把提取的關鍵詞根據微博的部分特征進行詳細化，然后把微博細化的特征逐個進行相似度計算得到綜合相似度，最后以綜合相似度為基礎，運用改進的聚類算法得出事件提取結果。

2個人微博特征的事件提取算法

個人微博特征的事件提取算法流程如圖1所示。

圖1　個人微博特征的事件提取算法流程圖

個人微博特征的事件提取算法分為以下幾部分：

(1) 對微博數據進行預處理，提取出微博特征。

(2) 針對微博特征和關鍵詞的定義，對預處理的數據進行改進的TF-IDF計算，主要運用了標簽(Hashtag)、URL對應的標題、詞長、轉發、評論、贊以及詞在每條微博中的分布熵。

(3) 提取關鍵詞，主要提取標簽關鍵詞、URL對應的標題關鍵詞和普通文本關鍵詞。

(4) 根據微博特征對微博進行綜合相似度計算，主要包括：標簽相似度、URL對應標題相似度、文本相似度。

(5) 改進的聚類方法提取事件。

基于個人微博特征的事件提取算法主要是以上述五個部分作為技術手段，把一個人發的多條微博進行整理，提取出個人微博中博主發表的主要事件。以李開復微博為例，把李開復所發表的微博內容按照事件類型進行分類，并把所說相同事件的微博聚集在一起。比如李開復在不同的時間發表了關于“大學生大學規劃”的事件，現通過技術手段把這些零散的微博聚集在一起，使得關注李開復的粉絲能快速地瀏覽關于“大學生大學規劃”的事件。

2.1預處理

(1) 去除個人微博中相同的微博。

(2) 提取出微博中的標簽(微博標簽一般在博文的開頭，兩個#號之間或者【】之間的詞語或者句子)。

(3) 提取出微博中含有URL鏈接所對應的標題(因為微博以140為字數上限，所以URL鏈接所對應的標題很大程度上能突出微博的主題)。

(4) 提取每一條微博的評論、轉發、贊的次數(評論、轉發、贊越多，那這條微博關注的人數就越多。說明這條微博很重要，應給微博中的每個詞給予更大的權重)。

(5) 分詞采用中科院漢語詞法分析系統ICTCLAS(Institute of Computing Technology, Chinese Lexical Analysis System)分詞。

(6) 去除微博中的停用詞、表情、特殊符號(停用詞、表情、特殊符號對于整條微博的價值是很低的，去除這些詞，同時也降低了噪聲)。

2.2改進的TF-IDF算法

2.2.1傳統TF-IDF缺點

傳統的TF-IDF應用在微博當中有以下缺點：

(1) 傳統的TF-IDF是針對長文本而不是針對微博的，所以沒有考慮到微博的特征。

(2) 詞的長度越長，那么詞含有的信息量就越大，就越有可能成為主題詞，即這個詞的TF-IDF權重應越高。

(3) 傳統的TF-IDF沒有考慮微博的影響力度，微博有評論、轉發、贊等特征，直接影響微博的重要性。

(4) 如果一個詞只出現在一條微博當中，那么這個詞的IDF會很高，傳統的TF-IDF會把這個詞當作權重高的主題詞。但在微博中，一個詞只出現在一條微博當中，我們可能不會把它當成關鍵詞，而是把一些分布在各個微博當中的詞當成主題詞來提取，所以我們引入信息熵的概念。

2.2.2改進的TF-IDF

(1) 針對傳統TF-IDF應用在微博中的第一個缺點，在微博的TF的改進當中加入了微博的特征(HashTag、URL對應的標題)。

① Hashtag

HashTag俗稱標簽，就是在發微博的時候，兩個#號之間或者【】之間的文字，一般代表主題，預處理時我們把微博數據當中的Hashtag提取出來。然后判斷普通文本中每個詞(去除Hashtag和URL微博數據)在標簽中是否出現，一般一條微博當中的一個詞在Hashtag中出現，這個詞應給予很高的權重，因為微博中的這個詞有可能代表著本條微博的主題。

② URL對應的標題

微博因為有140的字數限制，使得URL比較流行。在實際中，可以提取出URL所對應的標題，判斷普通文本(去除Hashtag和URL微博數據)中每個詞在URL對應的主題中是否出現。如果一條微博中的一個詞在URL對應的標題中出現，那這個詞應該被給予更高的權重。

綜上兩個特征對TF進行改進，改進的TF如下：

(1)

TF = α×w_hashtagi,j+β×w_urli,j+w_posi,j

(2)

其中每個個人微博中包含n條微博(d1,d2,…,dn)，而每條微博d中包含k個預處理后的詞(w1,w2,…,wk)。式(1)中TF(wi,dj) 表示詞wi在微博dj中的詞頻 ,其中分子表示詞wi在微博dj中出現的次數；分母表示微博dj中所有詞出現的次數和；式(2)中w_hashtagi,j表示分詞后詞wi在微博標簽中出現的次數，w_urli,j表示分詞后詞wi在微博dj中的URL所對應的標題中出現的次數，w_posi,j表示分詞后的詞wi在微博除標簽和URL對應標題外的文本中出現的次數，α、β分別為詞在標簽中和詞在URL鏈接對應的標題中出現詞匯wi的加權值，通過實驗α=2、β=1.5最佳。

(2) 詞長對TF-IDF的影響

針對傳統TF-IDF應用在微博中第二個缺點，加入了詞長對TF-IDF的影響，通常一個詞的長度不同包含信息量也不同，詞越長包含的信息量就越大，詞越短包含的信息量就越小。詞長權重公式如下：

f(len(wi))=(lglen(wi)-0.1)+1

(3)

其中len(wi)表示詞的長度，f(len(wi))表示詞長的權重，減0.1是為了平衡詞長因子的影響度大小，加1主要是為避免出現負數或0。

(3) 微博的影響力度

針對傳統TF-IDF應用在微博中第三個缺點，引入了微博的“影響力度”的概念。一條微博的影響力度主要通過轉發數、評論數和贊數來評定。如果一條微博的轉發數、評論數和贊數都很高，那么這條微博的權重也應很高，當然這條微博中的每個詞的權重也應很高。

微博影響力度公式如下：

(4)

其中,fas(wi，dj)表示微博dj中詞wi的影響力度,com表示微博dj被評論的數量，max(com)表示一個人發的所有微博中評論數的最大值，α1是一個加權值,par表示微博dj被贊的數量，max(pra)表示一個人發的所有微博中贊數最大值，β1是一個加權值,rep表示微博dj被轉發的數量，max(rep)表示一個人發的所有微博中轉發數的最大值，γ1是一個加權值。α1+β1+γ1=1，實驗設定α1=0.35、β1=0.35、γ1=0.3。

(4) IDF的改進

IDF的公式如下:

(5)

其中N表示個人微博的總微博數，n表示個人微博中包含字wi的微博數。

針對傳統TF-IDF應用在微博中第三個缺點：如果一個詞只出現在一條微博當中，那么這個詞的IDF會很高。傳統的TF-IDF會把這個詞當作權重高的主題詞，但是在微博中一個詞只出現在一條微博中，那么我們很可能不會把它當成關鍵詞而是把一個出現在各個微博中的詞當成主題詞來提取，因為這樣的詞更具有關鍵詞的特點，所以我們引入信息熵的概念。

定義1給定概率分布為P=(p1,p2,…,pn),則由該分布傳遞的信息量成為P的熵，即：

(6)

定義2若一個個人用戶發了n條微博(d1,d2,…,dn)，每條微博當中包含詞wi的概率分布為p(m1/M,m2/M,…,mn/M)。其中M表示詞wi在所有微博中出現的次數，mi表示詞wi在每條微博中出現的次數。我們把H(p)作為詞wi在整個微博中的分布熵。

H(p)越大則表示詞wi在每個微博當中分布越均勻，那么這個詞成為關鍵詞的概率就越大。相反，H(p)越小那么詞wi在不同微博分布中出現的次數不均勻，那么成為關鍵詞的概率就越小。

綜合改進的TF-IDF公式如下：

TF-IDF(wi,dj)=TF(wi,dj)×IDF×f(len(wi))×

H(p)×fas(wi,dj)

(7)

綜合上述公式可知，改進后的TF-IDF算法更加適應關鍵詞概念的定義，為下一步的提取關鍵詞包括相似度的計算提高了精確度。

2.3提取關鍵詞

提取關鍵詞時，根據每個詞的TF-IDF進行關鍵詞提取，我們運用了三種不同關鍵詞定義，定義如下：

定義3標簽關鍵詞：表示每條微博中的標簽經過預處理后的所有詞(因為標簽一般都很短，所以把標簽進行預處理后對應的所有詞作為標簽關鍵詞)。

定義4URL關鍵詞：表示每條微博中的URL所對應標題經過預處理后的所有詞(因為URL所對應標題一般都很短，所以把URL所對應標題經過預處理后對應的所有詞作為URL關鍵詞)。

定義5普通文本關鍵詞：表示每條微博中普通文本分詞后詞的TF-IDF權重大于這條微博中所有詞的平均TF-IDF值(普通文本表示微博文本中去除標簽和URL后的文本)。

2.4綜合相似度計算

關鍵詞提取完成后，我們要對提取的關鍵詞進行綜合相似度計算，其中綜合相似度分為三個部分。

2.4.1標簽相似度

對個人微博中的每條微博的標簽按定義3提取出來的標簽關鍵詞進行相似度計算，計算公式如下：

(8)

其中hashtag(di)∩hashtag(dj)表示微博di中的標簽和微博dj中的標簽有相同詞的個數，hashtag(di)∪hashtag(dj)表示微博di中的標簽和微博dj中標簽中詞的總數和。如果兩條微博當中都沒有hashtag或者兩條微博中只有一條微博含有hashtag，那么我們把標簽相似度設為0。

2.4.2URL對應的標題相似度

對個人微博中每條微博的URL對應的標題按定義4提取出的URL關鍵詞進行相似度計算，計算公式如下：

(9)

其中url(di)∩url(dj)表示微博di中url所對應的標題和微博dj中URL所對應的標題所含共同詞的個數，url(di)∪url(dj)表示微博di中URL所對應的標題和微博dj中URL所對應的標題所含詞的總數和(相同詞只加一次)。如果兩條微博都不含URL或者兩條微博中有一條微博不含URL，那么我們把URL對應的標題相似度設為0。

2.4.3文本相似度

對個人微博中的每條微博的普通文本按定義5提取出的普通文本關鍵字進行余弦相似度計算，計算公式如下：

(10)

其中，TF-IDF(w,di)和TF-IDF(w,dj)分別表示詞w在微博di和dj中的TF-IDF值。

2.4.4綜合相似度

兩條微博的綜合相似度對以上的兩個個特點進行加權得到公式如下：

sim(di,dj)=αsimhashtag(di,dj)+βsimurl(di,dj)+γsimpos(di,dj)

(11)

其中α、β、γ為三個加權參數，α+β+γ=1，通過對實驗數據的測試，α=0.4，β=0.3，γ=0.3，對最終事件提取效果最佳。

2.5聚類提取事件

根據綜合相似度的計算，進行改進的K-means聚類。

2.5.1在聚類中K-means算法對于微博聚類缺點

(1) 聚類算法的中心點選擇對聚類的結果會產生很大的影響。

(2) 常規的聚類算法沒有考慮到微博時間的特征，因為兩條微博時間跨度越大，那么這兩條微博成為一個事件的概率就越小。基于K-means算法聚類的缺點，我們把K-means算法做如下改動。改進K-means聚類流程如圖2所示。

圖2　改進的K-means聚類流程圖

2.5.2改進K-means聚類算法的詳細過程

(1) 把一個人的所有微博按照發表時間的順序進行分組，分為(T1,T2,…,Tn)。

(2) 對每個組按中心點選擇原則進行各自選擇中心點，運用綜合相似度式(11)進行K-means聚類。

(3) 每個組聚類完成后進行逐漸合并，并且在合并的同時加入時間的因素判斷，當兩條微博的發表時間差大于一個閾值時，不把這兩條微博合并成一個類簇，當兩條微博的發表時間在一個閾值范圍內，執行K-means聚類算法。

(4) 直到合并所有分組完成得出聚類結果。

2.5.3K-means聚類中心點選擇原則

(1) 統計微博在每個時間組內所有關鍵詞的詞頻。

(2) 在每個時間組內，包含更多的關鍵詞詞頻高的微博作為首要的中心點選擇。

2.5.4K-means聚類過程

Step1選取聚類中心點，合并前，在每組中按中心點選擇原則選擇初始中心聚類點，合并后，聚類中心點為合并后的兩個或者多個組的共同中心點。

Step2根據相似度式(11)把個人所有的微博進行歸類到每個中心點集合中。

Step3選取每個集合中與其他微博相關度最為密切的一條微博作為新的聚類中心，重復執行步驟Step2直到聚類中心的位置不再發生變化停止運行。

3實驗

本文數據集通過新浪微博第三方軟件爬蟲的數據：其中包括李開復1621、楊毅1532、馮小剛1376的微博一共4529條數據進行實驗。

實驗環境：CPU Inter(R)Core(TM)2 (2.93 GHz)，操作系統為64位Win 7旗艦版，實驗工具為Visual Studio 2010，數據庫為MYSQL Server 5.1。

3.1TF-IDF改進前后實驗比對

提取李開復、楊毅、馮小剛的微博中關鍵詞個數實驗對比。如果提取的關鍵詞越準確，那么對于相似度計算和聚類提取事件也會更加精確，對比如表1所示。

表1　改進TF-IDF前后提取關鍵詞個數與人工比對

從表1中的數據可以看出，改進后TF-IDF提取關鍵詞與人工標注的關鍵詞個數更接近，也充分的說明了改進TF-IDF算法的準確性。

改進前TF-IDF和改進后的TF-IDF算法對提取關鍵字和人工標注的比對的查全率和查準率。

改進前TF-IDF和改進后的TF-IDF算法對提取關鍵字和人工標注的比對的查全率和查準率。

查全率=改進前或后TF-IDF提取關鍵詞與人工標注關鍵詞相同的個數/人工標注的總個數

查準率=改進前或后TF-IDF提取關鍵詞與人工標注關鍵詞相同的個數/改進前或后TF-IDF提取關鍵詞的個數

對三個實驗人員數據進行人工的關鍵詞標注，讓傳統的TF-IDF和改進的TF-IDF提取的關鍵詞和人工標注的關鍵詞進行比對，來實現查全率和查準率對比，對比如圖3和圖4所示。

圖3　TF-IDF改進前后查全率對比圖

圖4　TF-IDF改進前后查準率對比圖

從圖3和圖4中可以看出，改進后的TF-IDF提取關鍵字的準確度遠遠高于改進前的TF-IDF，同時也會提高微博事件提取的精確度。

3.2K-means算法改進前后實驗對比

把三個實驗人員的微博進行了人工事件提取的標注，讓傳統的K-means算法和改進后的K-means算法聚類出的事件和人工的事件進行對比，如圖5所示。

圖5　K-means算法改進前后事件查全率對比

查全率=傳統K-means聚類算法或改進K-means算法查出事件與人工標注事件相同的個數/人工標注事件的個數

從圖5中可以看出，改進后的K-means算法提高了事件提取的準確度，同時也提高了微博事件提取的精確度。

3.3執行改進K-means算法得出事件提取結果

現以李開復的微博作為實例來分析聚類后事件提取結果，結果如圖6所示。聚類結果把李開復的1621條微博分為了63個事件， 這63個事件代表了李開復所發1621條微博所說的主要的事件。

圖6　事件提取部分結果

如圖6所示左側表示個人微博數據，中間表示提取的事件，右側表示聚類結果即事件提取結果，其中每個事件都包含多條微博，但多條微博所表述的意思基本相同或相關。

4結語

本文針對微博的特征，提出了基于個人微博特征的事件提取算法。首先該算法中的TF-IDF改進加入了信息熵的概念，提高了關鍵詞的提取精度；其次相似度計算的算法加入了微博的四種特征進行相似度計算，使得微博在相似度計算的同時更加細化；最后基于分段合并的K-means算法加入微博時序性的特點，使得事件提取結果更加準確。

在個人微博的事件提取中，我們還面臨著眾多的挑戰，其中，如何進一步發現微博更多的特征運用到事件提取中；如何提高事件提取的精確度；如何利用提取的事件產生自動摘要，是我們未來的工作中需要研究的重點問題。

參考文獻

[1] Phuvipadawat S,Murata T.Breaking news detection and tracking in twitter[C]//Web Intelligence and Intelligent Agent Technology (WI-IAT),2010 IEEE/WIC/ACM International Conference on.IEEE,2010,3:120-123.

[2] 周炎濤,唐劍波,王家琴.基于信息熵的改進TFIDF特征選擇算法[J].計算機工程與應用,2011,43(35):156-158.

[3] 張保富,施化吉,馬素琴.基于TFIDF文本特征加權方法的改進研究[J].計算機應用與軟件,2011,28(2):17-20.

[4] Li C,Sun A,Datta A.Twevent: segment-based event detection from tweets[C]//Proceedings of the 21st ACM international conference on Information and knowledge management.ACM,2012:155-164.

[5] Yao J,Cui B,Xue Z,et al.Provenance-based indexing support in micro-blog platforms[C]//Data Engineering (ICDE),2012 IEEE 28th International Conference on.IEEE,2012:558-569.

[6] Li J,Cardie C.Timeline generation:tracking individuals on twitter[C]//Proceedings of the 23rd international conference on World wide web.International World Wide Web Conferences Steering Committee,2014:643-652.

[7] 童薇,陳威,孟小峰.EDM:高效的微博事件檢測算法[J].計算機科學與探索,2012,6(12):1076-1086.

[8] Sharifi B,Hutton M A,Kalita J.Summarizing microblogs automatically[C]//Human Language Technologies:The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics.Association for Computational Linguistics,2010:685-688.

[9] 王春龍,張敬旭.基于LDA的改進K-means算法在文本聚類中的應用[J].計算機應用,2014,34(1):249-254.

收稿日期：2015-01-16。國家自然科學基金項目(61163025)。高永兵，副教授，主研領域：數據管理，信息檢索。陳超，碩士生。熊振華，碩士生。王宇，碩士生。馬占飛，教授。

中圖分類號TP399

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.07.011

ON EVENTS EXTRACTION BASED ON MICROBLOGGING CHARACTERISTICS

Gao YongbingChen ChaoXiong ZhenhuaWang YuMa Zhanfei

(SchoolofInformationEngineering,InnerMongoliaUniversityofScienceandTechnology,Baotou014010,InnerMongolia,China)

AbstractIndividual microblogs, in regard to events extraction, mostly use their texts to calculate the similarity to finally achieve the clustering results, but the microblogging features are not fully taken into consideration. Aiming at the characteristics of microblogging hashtag, URL and time, this paper puts forward a microblogging characteristic-based events extraction algorithm. The algorithm makes the TF-IDF improvement against microblogging characteristics, and adds hashtag similarity and URL similarity to carry out the comprehensive similarity calculation. Finally, it uses the improved K-means clustering method, that segments first and merges afterwards according to the time, to get the events extraction results. Experimental results show that the microblogging characteristics-based events extraction algorithm achieves obvious improvement in accuracy of microblogging keywords extraction and events extraction.

KeywordsMicroblogging characteristicEvents extractionComprehensive similarity