今天看了一篇文章，主要講的是數(shù)據(jù)挖掘在新聞事件的發(fā)現(xiàn)和跟蹤上面的應(yīng)用。論文的題目是Learing approaches for Detecting and Tracking News Events.
文章主要分成五個(gè)部分
新聞事件的特點(diǎn)分析，新聞事件的發(fā)現(xiàn)，新聞事件發(fā)現(xiàn)的評(píng)估，新聞時(shí)間的跟蹤，新聞事件跟蹤的評(píng)估
大致總結(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會(huì)大大不同，其起到的作用，即權(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是對(duì)塊數(shù)據(jù)進(jìn)行處理，會(huì)返回樹(shù)狀聚類，INCR是對(duì)流數(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è)沒(méi)有重疊，并且連續(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è)最高層聚類中重聚類，通過(guò)撫平組建聚類和從葉結(jié)點(diǎn)重新增長(zhǎng)聚類。防止新聞事件被分在兩個(gè)時(shí)間窗口的情況的影響。
INCR算法是直接的，一個(gè)一個(gè)處理文檔，逐步增加聚類。如果一個(gè)新文檔和一個(gè)類的相似性大于一個(gè)閾值tc，則聚入到已有的最近類。如果和所有的聚類的相似性都小于閾值，則把他作為新類的種子。通過(guò)恰當(dāng)?shù)倪x取閾值，可以獲得不同粒度的聚類。
對(duì)于INCR在線事件發(fā)現(xiàn)的應(yīng)用時(shí)，我們引入了一個(gè)附加的閾值，noverlty threshold(tn)。如果當(dāng)前文檔和任何聚類的相似性都小于noverlty threshold，這個(gè)文檔就標(biāo)記為“NEW”，表示這是一個(gè)新事件的開(kāi)頭；否則就標(biāo)記“OLD”。通過(guò)調(diào)整這個(gè)閾值，可以調(diào)整對(duì)于在線發(fā)現(xiàn)新事件的敏感度。
設(shè)置兩個(gè)閾值的原因在于可以為不同的任務(wù)進(jìn)行優(yōu)化，我們發(fā)現(xiàn)設(shè)置tc=tn對(duì)于回顧聚類比較合適，而設(shè)置tc=正無(wú)窮對(duì)于在線偵測(cè)比較更好，即，不產(chǎn)生任何聚類。
對(duì)于INCR增加的另外一個(gè)功能是時(shí)間懲罰（time penalty）。最簡(jiǎn)單的方法是使用一個(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ù)。文中說(shuō)，可以給出非線性的衰退函數(shù)，以求得更好的結(jié)果。
對(duì)于新舊的預(yù)測(cè)，每個(gè)文檔要計(jì)算一個(gè)score，表示這個(gè)文檔有多新score（x）=1-arg max{sim(x,c)'} 其中x是當(dāng)前新文檔，c是過(guò)去的所有聚類。通過(guò)設(shè)定閾值，來(lái)控制準(zhǔn)確率和召回率的折中。
新聞事件發(fā)現(xiàn)的評(píng)估
回顧事件的發(fā)現(xiàn)，使用關(guān)于籃子的GAC效果最好
對(duì)于在線發(fā)現(xiàn)，處理流數(shù)據(jù)的INCR有天生的優(yōu)勢(shì)，但是需要恰當(dāng)?shù)恼{(diào)整相似性的權(quán)重函數(shù)和聚類的閾值，這可能需要通過(guò)實(shí)驗(yàn)測(cè)定。
新聞事件的跟蹤
就是要在新聞事件到來(lái)的時(shí)候，確定他是關(guān)于那些事件，但是做決定的根據(jù)是先前到來(lái)的關(guān)于這個(gè)事件的為數(shù)不多的新聞。同時(shí)還要求能夠分開(kāi)有關(guān)系的新聞事件，例如前后的礦難。另外就是要求對(duì)一個(gè)新聞事件的判斷必須是獨(dú)立的，與其他事件無(wú)關(guān)。
文章選取了kNN和決策樹(shù)的算法。因?yàn)閗NN在TC上的性能非常好，對(duì)術(shù)語(yǔ)和新聞作了最少的假設(shè)。
為每個(gè)新聞事件訓(xùn)練了一個(gè)kNN，并把它的m-ary變成了二維判斷。是由于正面事例太少，所以修改了一下YES的判斷標(biāo)準(zhǔn)。
決策樹(shù)的算法暫時(shí)不考慮。
在做分類時(shí)，一般只考慮一到一個(gè)半月以內(nèi)的新聞作為訓(xùn)練集，因?yàn)橐话阈侣劦某掷m(xù)時(shí)間不會(huì)超過(guò)兩個(gè)月
事件跟蹤的評(píng)估
修改后的kNN效果還是很不錯(cuò)的