今天看了一篇文章，主要講的是數(shù)據(jù)挖掘在新聞事件的發(fā)現(xiàn)和跟蹤上面的應(yīng)用。論文的題目是Learing approaches for Detecting and Tracking News Events.
文章主要分成五個(gè)部分
新聞事件的特點(diǎn)分析，新聞事件的發(fā)現(xiàn)，新聞事件發(fā)現(xiàn)的評估，新聞時(shí)間的跟蹤，新聞事件跟蹤的評估

大致總結(jié)一些每一部分的主要內(nèi)容

新聞事件的特點(diǎn)分析：
   新聞事件和一般的文本分類，信息提取不同的地方在于，新聞事件的發(fā)展和報(bào)道和時(shí)間上的關(guān)系。新聞是以時(shí)間順序輸入TDT系統(tǒng)，關(guān)于某個(gè)事件的新聞，在時(shí)間上是一個(gè)尖峰脈沖。因此在做相似性聚類的時(shí)候需要充分考慮報(bào)道同一事件的新聞在時(shí)間上的相似性，以及文本相似性。
   還有就是，報(bào)道不同事件的新聞的term會大大不同，其起到的作用，即權(quán)值也大大不同，因此需要?jiǎng)討B(tài)的更改這些權(quán)值，為下面的聚類和分類使用。

新聞事件的發(fā)現(xiàn)
   新聞事件的發(fā)現(xiàn)，實(shí)際上就是文本聚類，和時(shí)間有關(guān)的，文本量不大的文本聚類
   事件發(fā)現(xiàn)又分為兩部分：回顧的事件挖掘和新事件的在線發(fā)現(xiàn)。
   這篇文章主要采用了兩個(gè)修改了的聚類算法：GAC和INCR，其中GAC是對塊數(shù)據(jù)進(jìn)行處理，會返回樹狀聚類，INCR是對流數(shù)據(jù)進(jìn)行處理
   聚類的表示，這篇文章使用的是ltc，但其中的idf因子進(jìn)行了修改
IDF(t,p)=log(N(p)/n(t,p)) 其中p是時(shí)間。

   GAC的步驟，

1.       把輸入集合的每一個(gè)文檔當(dāng)作一個(gè)單獨(dú)的聚類，設(shè)置初始劃分為單個(gè)集合的全部集。

2.       把當(dāng)前劃分分成兩個(gè)沒有重疊，并且連續(xù)的大小為m（用戶預(yù)定義的）的籃子

3.       在每個(gè)籃子里面使用GAC，重復(fù)的把兩個(gè)低層的聚類聚集成一個(gè)高層的聚類，直到籃子中的聚類降到p（用戶預(yù)定義的）或者任意兩個(gè)聚類間的相似性小于一個(gè)與定義的閾值（用戶預(yù)定義的）。

4.       移除籃子邊界，按照聚類的時(shí)間，把所有GAC聚類放在一起。使用的到的聚類序列作為更新的劃分。

5.       重新計(jì)算2-4部，直到劃分的大小不大于m，或者聚類之間的相似性達(dá)到限制。

6.       定期（once of 運(yùn)行第五步k次）的在每個(gè)最高層聚類中重聚類，通過撫平組建聚類和從葉結(jié)點(diǎn)重新增長聚類。防止新聞事件被分在兩個(gè)時(shí)間窗口的情況的影響。

      

    INCR算法是直接的，一個(gè)一個(gè)處理文檔，逐步增加聚類。如果一個(gè)新文檔和一個(gè)類的相似性大于一個(gè)閾值tc，則聚入到已有的最近類。如果和所有的聚類的相似性都小于閾值，則把他作為新類的種子。通過恰當(dāng)?shù)倪x取閾值，可以獲得不同粒度的聚類。

       對于INCR在線事件發(fā)現(xiàn)的應(yīng)用時(shí)，我們引入了一個(gè)附加的閾值，noverlty threshold(tn)。如果當(dāng)前文檔和任何聚類的相似性都小于noverlty threshold，這個(gè)文檔就標(biāo)記為“NEW”，表示這是一個(gè)新事件的開頭；否則就標(biāo)記“OLD”。通過調(diào)整這個(gè)閾值，可以調(diào)整對于在線發(fā)現(xiàn)新事件的敏感度。

       設(shè)置兩個(gè)閾值的原因在于可以為不同的任務(wù)進(jìn)行優(yōu)化，我們發(fā)現(xiàn)設(shè)置tc=tn對于回顧聚類比較合適，而設(shè)置tc=正無窮對于在線偵測比較更好，即，不產(chǎn)生任何聚類。

       對于INCR增加的另外一個(gè)功能是時(shí)間懲罰（time penalty）。最簡單的方法是使用一個(gè)時(shí)間窗口。給定當(dāng)前的文檔x，我們引入一個(gè)時(shí)間窗口m表示x前的m個(gè)文檔，然后定義修改后的x和任意聚類c相似性sim(x,c)

另外，他們引入了衰退相似性的權(quán)重函數(shù)sim(x,c)=(1-i/m)*sim(x,c)，其中i是x和類c中最近的文檔數(shù)。文中說，可以給出非線性的衰退函數(shù)，以求得更好的結(jié)果。

 

       對于新舊的預(yù)測，每個(gè)文檔要計(jì)算一個(gè)score，表示這個(gè)文檔有多新score（x）=1-arg max{sim(x,c)'}  其中x是當(dāng)前新文檔，c是過去的所有聚類。通過設(shè)定閾值，來控制準(zhǔn)確率和召回率的折中。
   
新聞事件發(fā)現(xiàn)的評估
   回顧事件的發(fā)現(xiàn)，使用關(guān)于籃子的GAC效果最好
   對于在線發(fā)現(xiàn)，處理流數(shù)據(jù)的INCR有天生的優(yōu)勢，但是需要恰當(dāng)?shù)恼{(diào)整相似性的權(quán)重函數(shù)和聚類的閾值，這可能需要通過實(shí)驗(yàn)測定。

新聞事件的跟蹤
   就是要在新聞事件到來的時(shí)候，確定他是關(guān)于那些事件，但是做決定的根據(jù)是先前到來的關(guān)于這個(gè)事件的為數(shù)不多的新聞。同時(shí)還要求能夠分開有關(guān)系的新聞事件，例如前后的礦難。另外就是要求對一個(gè)新聞事件的判斷必須是獨(dú)立的，與其他事件無關(guān)。
   文章選取了kNN和決策樹的算法。因?yàn)閗NN在TC上的性能非常好，對術(shù)語和新聞作了最少的假設(shè)。
   為每個(gè)新聞事件訓(xùn)練了一個(gè)kNN，并把它的m-ary變成了二維判斷。是由于正面事例太少，所以修改了一下YES的判斷標(biāo)準(zhǔn)。
   決策樹的算法暫時(shí)不考慮。
   在做分類時(shí)，一般只考慮一到一個(gè)半月以內(nèi)的新聞作為訓(xùn)練集，因?yàn)橐话阈侣劦某掷m(xù)時(shí)間不會超過兩個(gè)月

事件跟蹤的評估
修改后的kNN效果還是很不錯(cuò)的