基于決策樹方法的突發(fā)事件新聞分類

文/閆宏麗 羅永蓮

（晉中學(xué)院信息技術(shù)與工程學(xué)院 山西省晉中市 030619）

1 引言

決策樹學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法[1]，它著眼于從一組無(wú)次序、無(wú)規(guī)則的事例中推理出決策樹表示形式的分類規(guī)則，通常用來(lái)對(duì)未知數(shù)據(jù)進(jìn)行分類或預(yù)測(cè)[2]。在J.R.Quinlan于1986年提出ID3算法以后，決策樹方法在機(jī)器學(xué)習(xí)、知識(shí)發(fā)現(xiàn)領(lǐng)域得到了進(jìn)一步應(yīng)用及巨大的發(fā)展[3]。

突發(fā)事件新聞可分為多個(gè)類別，不同類別的新聞?dòng)迷~差別較大。如交通事故新聞中出現(xiàn)“公路”、“側(cè)翻”、“超速”、“客車”等的頻率較高；疾病傳染類的新聞則常出現(xiàn)“疫苗”、“隔離”、“預(yù)防”、“病毒”、“療效”等詞。上述詞語(yǔ)在一則新聞中很少單獨(dú)出現(xiàn)，即一些相關(guān)詞匯常同時(shí)出現(xiàn)在一個(gè)事件新聞中[4，5]。通過(guò)分析發(fā)現(xiàn)突發(fā)事件新聞文檔具有以下特點(diǎn)：

（1）事件新聞描述有許多相似之處。

（2）同一類事件用詞類似，語(yǔ)句格式也很相似。

（3）不同事件有各自特殊的用語(yǔ)，可以用圖1表示其部分層次結(jié)構(gòu)。

根據(jù)上述特點(diǎn)，設(shè)計(jì)基于決策樹的分類算法將成組出現(xiàn)的類別關(guān)鍵詞作為決策樹的屬性項(xiàng)，本組詞語(yǔ)在一篇新聞文檔中同時(shí)出現(xiàn)的詞數(shù)作為屬性項(xiàng)的值，通過(guò)判定文檔的詞語(yǔ)組合情況實(shí)現(xiàn)分類。

2 突發(fā)事件新聞的文檔表示

2.1 提取類別組合詞串

對(duì)于訓(xùn)練樣本集中的每一個(gè)類別，分別選取與此類別相關(guān)的詞條作為本類特征詞。然后由特征詞中抽取類別組合詞串，對(duì)于每一類新聞可抽取若干組合詞串，為防止詞語(yǔ)過(guò)度組合，影響分類效果，限定每個(gè)組合詞串包含10個(gè)以內(nèi)的詞語(yǔ)。

其中nij為類別ci中包含詞條wj的文檔數(shù)，nj為訓(xùn)練集中包含詞條wj的文檔數(shù)，ni為類別ci中的文檔總數(shù)，N為訓(xùn)練集的文檔總數(shù)。

將類別ci的特征詞按降序排列，生成特征詞集TSi，按下列步驟提取本類的組合詞串：

第1步 若TSi中的特征詞數(shù)為0或1，則抽取結(jié)束，否則取TSi的第一個(gè)特征詞Tf；

圖1：新聞事件的層次結(jié)構(gòu)示意圖

第2步 檢索本類中與Tf在同一文檔中出現(xiàn)的所有特征詞，并生成Tf的候選組合詞集

第3步 若T為空，從TSi中刪除Tf，轉(zhuǎn)入第1步，否則對(duì)于統(tǒng)計(jì)其與Tf同時(shí)出現(xiàn)的文檔數(shù)

第5步 若此時(shí)T為空，從TSi中刪除Tf，轉(zhuǎn)入第1步，否則，取T中的前10個(gè)詞（若詞數(shù)不足10個(gè)，則取全部詞）與Tf組成類別Ci的一個(gè)類別組合詞串；

第6步 將上述組合詞串中的所有詞從TSi中刪除，轉(zhuǎn)入第一步。

2.2 文檔表示

規(guī)則1 若fi包含的詞條個(gè)數(shù)為5個(gè)或5以下，di的值為fi中的詞條在文檔中的出現(xiàn)個(gè)數(shù)，若文檔中不包含fi中的任何一個(gè)詞條，則di賦值為0。

規(guī)則2 若fi包含詞條個(gè)數(shù)為5個(gè)以上，則di的值為0到6 間的整數(shù)，當(dāng)fi中的詞條在文檔中的出現(xiàn)個(gè)數(shù)大于5時(shí)，di賦值為6，其他值的賦值方法與規(guī)則1相同。

3 建立決策樹并實(shí)現(xiàn)分類

3.1 計(jì)算屬性項(xiàng)的信息增益

信息增益是決策樹分類方法中常用的一種特征值計(jì)算方法，它利用熵來(lái)計(jì)算屬性項(xiàng)的信息增益值，并作為決策樹創(chuàng)建節(jié)點(diǎn)的依據(jù)。各屬性項(xiàng)的信息增益計(jì)算公式為：

其中，I(c)表示類別的熵，其計(jì)算公式為：

pi是某新聞文檔被標(biāo)識(shí)為ci類別的概率，可用當(dāng)前樣本集中ci類的文檔數(shù)與文檔總數(shù)的比值來(lái)估計(jì)。

I(f)表示若按屬性項(xiàng)f分類時(shí)類別的熵，若當(dāng)前樣本集根據(jù)屬性項(xiàng)f的v個(gè)不同取值可分為v個(gè)子集，I(f)的計(jì)算公式為：

p(fj)是屬性項(xiàng)f取第j個(gè)值的概率，可用第j個(gè)子集的文檔數(shù)與樣本集文檔總數(shù)的比值來(lái)估計(jì)。

E(fj)是屬性項(xiàng)f第j個(gè)值所提供的信息熵，其計(jì)算公式為：pij是當(dāng)f取第j個(gè)值時(shí)文檔被標(biāo)識(shí)為ci類別的概率，可用第j個(gè)子集中ci類的文檔數(shù)與第j個(gè)子集文檔總數(shù)的比值來(lái)估計(jì)。

3.2 生成決策樹

計(jì)算屬性項(xiàng)的信息增益，根據(jù)屬性項(xiàng)的信息增益值建立分枝，直至結(jié)點(diǎn)對(duì)應(yīng)的分枝符合算法終止條件，此時(shí)生成決策樹[6，7]。生成決策樹的操作為：

第1步 生成一棵空決策樹，選取信息增益值最大屬性項(xiàng)的作為當(dāng)前節(jié)點(diǎn)，根據(jù)屬性項(xiàng)的值建立多個(gè)分枝。

第2步 對(duì)于每個(gè)分枝，算法當(dāng)下列條件之一時(shí)終止：

（1）當(dāng)前分枝中的新聞文檔屬同一類別，此時(shí)設(shè)置此節(jié)點(diǎn)的類別標(biāo)記為文檔所屬類別，并設(shè)置此節(jié)點(diǎn)的可信度為100%；

（2）當(dāng)前分枝中的新聞文檔總數(shù)低于閾值,設(shè)置節(jié)點(diǎn)標(biāo)記分類失敗，并設(shè)置此節(jié)點(diǎn)的可信度為0；

（3）訓(xùn)練集訓(xùn)練完畢，此時(shí)根據(jù)當(dāng)前分枝中的多數(shù)標(biāo)記此節(jié)點(diǎn)的類別標(biāo)記，并設(shè)置此節(jié)點(diǎn)的可信度為類別正確的新聞文檔數(shù)與訓(xùn)練集總數(shù)的比值。

第3步 否則，對(duì)當(dāng)前分枝重復(fù)步驟1和步驟2。

3.3 利用決策樹實(shí)現(xiàn)分類

4 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證算法有效性，采用以下2種方式從網(wǎng)上搜集突發(fā)事件新聞作為信息資源。一是利用搜索引擎搜集資源。所有的搜索引擎和網(wǎng)絡(luò)信息資源數(shù)據(jù)庫(kù)都提供檢索功能，即在主頁(yè)上都有檢索輸入框可供輸入檢索詞。通過(guò)對(duì)突發(fā)事件用詞特點(diǎn)的分析，用適當(dāng)?shù)臋z索詞，從此類資源中獲取相關(guān)網(wǎng)頁(yè)。為了使信息采集更準(zhǔn)確、完整，在向搜索引擎提出搜索請(qǐng)求后，繼續(xù)進(jìn)行關(guān)鍵詞擴(kuò)充，即分析獲得的新聞?wù)Z料，增加檢索詞。二是利用已有的新聞網(wǎng)站搜集資源。從選定的新聞分類網(wǎng)站上搜索新聞網(wǎng)頁(yè)，并通過(guò)相應(yīng)的鏈接搜索更多類似網(wǎng)站并從中搜索新聞網(wǎng)頁(yè)。按新聞?lì)悇e及發(fā)布時(shí)間、網(wǎng)站等分別采集新聞網(wǎng)頁(yè)2000篇，其中1500篇作為訓(xùn)練集，500篇作為測(cè)試集。將訓(xùn)練樣本分為5類，每一類300篇，測(cè)試500篇測(cè)試文檔的分類效果。

初始特征詞的選擇與閾值θ有關(guān)，測(cè)試當(dāng)θ取不同值時(shí)分類準(zhǔn)確的文檔數(shù)，其結(jié)果如圖2所示。

圖2：θ值的選取與分類正確文檔數(shù)的關(guān)系圖

由圖2可知，當(dāng)θ小于1.2時(shí)，分類準(zhǔn)確率趨于穩(wěn)定，由于θ較小時(shí)，所選特征詞增加，其分類效果也較好，但若特征詞過(guò)多，一方面計(jì)算復(fù)雜度增加，另一方面，也會(huì)因其他詞的干擾，分類效果變差。由實(shí)驗(yàn)結(jié)果可知若選取適當(dāng)?shù)膮?shù)，分類正確的文檔數(shù)達(dá)到439篇，即分類準(zhǔn)確率達(dá)到87.8%。

5 結(jié)論

提出了一種突發(fā)事件新聞分類的方法。該方法為減少節(jié)點(diǎn)數(shù)，實(shí)現(xiàn)準(zhǔn)確快速地分類，將新聞文檔中的相關(guān)特征詞進(jìn)行組合，作為判定屬性項(xiàng)，計(jì)算其信息增益，以建立決策樹。在分類過(guò)程中，由測(cè)試文檔中組合詞的出現(xiàn)情況作類別判定。由實(shí)驗(yàn)結(jié)果表明，上述算法有效。