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

文/閆宏麗 羅永蓮

（晉中學院信息技術與工程學院 山西省晉中市 030619）

1 引言

決策樹學習是以實例為基礎的歸納學習算法[1]，它著眼于從一組無次序、無規則的事例中推理出決策樹表示形式的分類規則，通常用來對未知數據進行分類或預測[2]。在J.R.Quinlan于1986年提出ID3算法以后，決策樹方法在機器學習、知識發現領域得到了進一步應用及巨大的發展[3]。

突發事件新聞可分為多個類別，不同類別的新聞用詞差別較大。如交通事故新聞中出現“公路”、“側翻”、“超速”、“客車”等的頻率較高；疾病傳染類的新聞則常出現“疫苗”、“隔離”、“預防”、“病毒”、“療效”等詞。上述詞語在一則新聞中很少單獨出現，即一些相關詞匯常同時出現在一個事件新聞中[4，5]。通過分析發現突發事件新聞文檔具有以下特點：

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

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

（3）不同事件有各自特殊的用語，可以用圖1表示其部分層次結構。

根據上述特點，設計基于決策樹的分類算法將成組出現的類別關鍵詞作為決策樹的屬性項，本組詞語在一篇新聞文檔中同時出現的詞數作為屬性項的值，通過判定文檔的詞語組合情況實現分類。

2 突發事件新聞的文檔表示

2.1 提取類別組合詞串

對于訓練樣本集中的每一個類別，分別選取與此類別相關的詞條作為本類特征詞。然后由特征詞中抽取類別組合詞串，對于每一類新聞可抽取若干組合詞串，為防止詞語過度組合，影響分類效果，限定每個組合詞串包含10個以內的詞語。

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

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

第1步 若TSi中的特征詞數為0或1，則抽取結束，否則取TSi的第一個特征詞Tf；

圖1：新聞事件的層次結構示意圖

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

第3步 若T為空，從TSi中刪除Tf，轉入第1步，否則對于統計其與Tf同時出現的文檔數

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

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

2.2 文檔表示

規則1 若fi包含的詞條個數為5個或5以下，di的值為fi中的詞條在文檔中的出現個數，若文檔中不包含fi中的任何一個詞條，則di賦值為0。

規則2 若fi包含詞條個數為5個以上，則di的值為0到6 間的整數，當fi中的詞條在文檔中的出現個數大于5時，di賦值為6，其他值的賦值方法與規則1相同。

3 建立決策樹并實現分類

3.1 計算屬性項的信息增益

信息增益是決策樹分類方法中常用的一種特征值計算方法，它利用熵來計算屬性項的信息增益值，并作為決策樹創建節點的依據。各屬性項的信息增益計算公式為：

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

pi是某新聞文檔被標識為ci類別的概率，可用當前樣本集中ci類的文檔數與文檔總數的比值來估計。

I(f)表示若按屬性項f分類時類別的熵，若當前樣本集根據屬性項f的v個不同取值可分為v個子集，I(f)的計算公式為：

p(fj)是屬性項f取第j個值的概率，可用第j個子集的文檔數與樣本集文檔總數的比值來估計。

E(fj)是屬性項f第j個值所提供的信息熵，其計算公式為：pij是當f取第j個值時文檔被標識為ci類別的概率，可用第j個子集中ci類的文檔數與第j個子集文檔總數的比值來估計。

3.2 生成決策樹

計算屬性項的信息增益，根據屬性項的信息增益值建立分枝，直至結點對應的分枝符合算法終止條件，此時生成決策樹[6，7]。生成決策樹的操作為：

第1步 生成一棵空決策樹，選取信息增益值最大屬性項的作為當前節點，根據屬性項的值建立多個分枝。

第2步 對于每個分枝，算法當下列條件之一時終止：

（1）當前分枝中的新聞文檔屬同一類別，此時設置此節點的類別標記為文檔所屬類別，并設置此節點的可信度為100%；

（2）當前分枝中的新聞文檔總數低于閾值,設置節點標記分類失敗，并設置此節點的可信度為0；

（3）訓練集訓練完畢，此時根據當前分枝中的多數標記此節點的類別標記，并設置此節點的可信度為類別正確的新聞文檔數與訓練集總數的比值。

第3步 否則，對當前分枝重復步驟1和步驟2。

3.3 利用決策樹實現分類

4 實驗結果與分析

為了驗證算法有效性，采用以下2種方式從網上搜集突發事件新聞作為信息資源。一是利用搜索引擎搜集資源。所有的搜索引擎和網絡信息資源數據庫都提供檢索功能，即在主頁上都有檢索輸入框可供輸入檢索詞。通過對突發事件用詞特點的分析，用適當的檢索詞，從此類資源中獲取相關網頁。為了使信息采集更準確、完整，在向搜索引擎提出搜索請求后，繼續進行關鍵詞擴充，即分析獲得的新聞語料，增加檢索詞。二是利用已有的新聞網站搜集資源。從選定的新聞分類網站上搜索新聞網頁，并通過相應的鏈接搜索更多類似網站并從中搜索新聞網頁。按新聞類別及發布時間、網站等分別采集新聞網頁2000篇，其中1500篇作為訓練集，500篇作為測試集。將訓練樣本分為5類，每一類300篇，測試500篇測試文檔的分類效果。

初始特征詞的選擇與閾值θ有關，測試當θ取不同值時分類準確的文檔數，其結果如圖2所示。

圖2：θ值的選取與分類正確文檔數的關系圖

由圖2可知，當θ小于1.2時，分類準確率趨于穩定，由于θ較小時，所選特征詞增加，其分類效果也較好，但若特征詞過多，一方面計算復雜度增加，另一方面，也會因其他詞的干擾，分類效果變差。由實驗結果可知若選取適當的參數，分類正確的文檔數達到439篇，即分類準確率達到87.8%。

5 結論

提出了一種突發事件新聞分類的方法。該方法為減少節點數，實現準確快速地分類，將新聞文檔中的相關特征詞進行組合，作為判定屬性項，計算其信息增益，以建立決策樹。在分類過程中，由測試文檔中組合詞的出現情況作類別判定。由實驗結果表明，上述算法有效。