[發明專利]基于遺傳算法的網絡文本分割方法

有效

• 申請號: 200910219163.8
• 申請日: 2009-11-26
• 公開（公告）號: CN101710333A
• 公開（公告）日: 2010-05-19
• 發明（設計）人: 蔡皖東;趙煜
• 申請（專利權）人: 西北工業大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F17/27;G06N3/12
• 代理公司: 西北工業大學專利中心 61204
• 代理人: 黃毅新

1.一種基于遺傳算法的網絡文本分割方法，其特征在于包括以下步驟：

(a)利用網絡蜘蛛在網絡上收集網頁，通過對收集的網頁進行文本預處理，僅保留文本 信息，并采用樸素貝葉斯的文本分類方法，對去除噪聲后的文本信息進行分類，按類別構建 擴展語料庫；

(b)采用層次聚類方法對擴展語料庫進行聚類，確定子主題的數目，采用Gibbs采樣方 法估計擴展語料庫的LDA模型，估計涉及的參數采用經驗值α＝0.01，β＝0.01，burn-in間距 是2000，thinning間距是100；

(c)對待分割文本進行分詞、詞性標注、命名實體識別、詞義消歧的文本預處理，統計 文本中名詞、動詞的頻率，選擇高頻詞匯作為文本的特征詞匯；再根據HowNet，計算文本的 特征詞匯與擴展語料庫的特征詞匯之間的相似度，選取相似度最大值對應的語料庫為文本分 割的外部語料庫；最后采用Gibbs采樣方法以及所述擴展語料庫對應的LDA模型推斷待分割 文本包含的語義結構信息，推斷的語義結構信息包括詞匯所屬子主題的類型以及詞匯在分割 單元中的概率；詞匯所屬子主題的類型用于待分割文本的表示，以句子為單位統計每個詞匯 所屬的子主題類型，句子表示為子主題空間向量，句子Sj＝s_j1s_j2...s_jj...s_jT，s_jj表示句子j中詞 匯屬于子主題j的頻率；

(d)利用并行遺傳算法進行文本分割，算法編碼方案采用二進制編碼方案，種群初始化 采用隨機數生成方法，同時利用語義段落的最小長度和文本包含語義段落的最小數量兩個指 標，過濾不合格的初始個體；根據公式

Coh=1-Σn=1j1kΣsi∈bnΣl=1T(sil-anl)2]]>

計算語義段落內的凝聚性；式中，|b_n|表示第n個語義段落中包含的句子數，a_n表示語義段落對應的平均向量，a_nl是該向量的第l個分量；

根據公式

Dis=Σn=1j|bn|kΣl=1T(anl-cl)2]]>

計算語義段落間的發散性；式中，

根據語義段落內的凝聚性和語義段落間發散性計算遺傳迭代中每個個體的適應度函數 值，計算公式如下：

式中，表示擴展種群，用于存儲迭代中的最優解；

種群選擇過程中，首先采用精英保留策略，保留種群及擴展種群中的精英個體，直接進 入下一代進化；然后采用輪盤賭方法，分別從種群和擴展種群中選擇個體，比較兩個體的適 應度值，選擇適應度小的個體進行交叉和變異操作；

交叉過程采用單點交叉方法，為了防止近親繁殖，當個體間漢明距離超過閾值時，才允 許在種群和擴展種群之間進行交叉操作，閾值設置為個體間平均漢明距離的20％；根據種群 的相似度自適應調節變異算子；種群的相似度計算公式如下：

根據公式計算不同迭代輪次擴展種群中最優個體的相似度， 當相似度超過閾值且持續50輪，則結束迭代過程，選取擴展種群中的個體作為文本分割的結 果，在個體的二進制表示中，數字“1”對應的句子就是文本分割的邊界。