一種基于人工免疫的We b文本分類方法研究——以Web信息分類為例

●何曉慶，賈 釗

(1．四川大學 圖書館，成都 610064；2．西安通信學院，西安 710106)

●王愛玲(內(nèi)蒙古農(nóng)業(yè)大學 圖書館，呼和浩特 010018)

1 引言

隨著信息技術(shù)的快速發(fā)展，Interne t已經(jīng)成為人們查找和獲取信息的一個重要途徑，發(fā)揮著日益重要的作用，互聯(lián)網(wǎng)上的數(shù)據(jù)也呈現(xiàn)出迅猛增長的態(tài)勢。據(jù)中國互聯(lián)網(wǎng)絡信息中心(CNNIC)第23次中國互聯(lián)網(wǎng)絡發(fā)展狀況統(tǒng)計報告，[1]截至2008年底，中國的域名總量達到1682萬個，網(wǎng)站數(shù)達到287.8萬個，中國網(wǎng)頁總數(shù)超過160億個，均比2007年出現(xiàn)大幅增長。面對We b上的海量數(shù)據(jù)，在處理重大突發(fā)事件等涉及社會層面較廣的社會事務時，政府等公共部門信息管理部門如何從中找到有價值的信息，并提取出有效知識已經(jīng)成為信息檢索、數(shù)據(jù)挖掘等領域的重要課題。[2]文本分類作為其中的重要內(nèi)容之一，也引起越來越多的關注。本文借鑒人工免疫理論的思想，提出了一種基于人工免疫的文本分類方法，可以更好地實現(xiàn)文本的自動分類。

2 人工免疫與文本分類

生物免疫系統(tǒng)是目前所知的識別和抵御外部有害物質(zhì)最精妙復雜的智能系統(tǒng)，它猶如一支擁有學習能力并且訓練有素的精銳部隊，保衛(wèi)人體的健康。[3]人工免疫系統(tǒng)(Artificial Immune Syste m，AIS)是一個受生物免疫系統(tǒng)啟發(fā)而建立的計算機研究領域，是人工智能領域的一個重要分支。類似于神經(jīng)網(wǎng)絡和遺傳算法，人工免疫同樣是智能信息處理的非常重要的一個手段。人工免疫系統(tǒng)中的克隆選擇、高頻變異等原理具有動態(tài)性、自適應和自學習性，非常適合用到自動文本分類中的分類器訓練和生成中。

文本分類(Text Categorizatio n，T C)的主要任務是在預先給定的類別標記集合下，根據(jù)待分文本內(nèi)容對其類別歸屬進行判定。從數(shù)學角度來看，文本分類是一個映射的過程，它將未標明類別的文本映射到已有的類別中。目前國內(nèi)外采用的比較多的文本分類方法主要有TFIDF算法、樸素貝葉斯算法(NaiveBaye s，N B)、K近鄰法(KNN)、支持向量機(Support VectorMachin e，SVM)、神經(jīng)網(wǎng)絡等方法。

文本分類問題與生物免疫系統(tǒng)所遇到的問題非常相似，兩者都需要在不斷變化的環(huán)境中對未知對象進行識別和分辨，所以本文借鑒免疫系統(tǒng)的相關工作原理，提出了一種基于免疫機制的文本分類方法。實驗證明，該方法不僅有效提高檢測率，而且還擁有良好的學習能力與較強的自適應性。

3 基于人工免疫的分類模型

3.1 文本的表示和分詞

We b文檔包含了多種信息，例如文字信息、圖片信息和視頻音頻信息等，我們主要關注其中的文本信息。文本信息通常由項(Ter m)的集合組成，項包括字、詞、短語等基本語言單位。所以文本可表示為T=｛t1,t2,…,tN｝，其中 t i(1≤i≤N)就是文本中的項。

由于中文文檔在語句中是以漢字為單位進行連寫，并沒有西方文字那樣每個詞都通過空格分開，所以必須對文檔進行分詞處理，找出和分類相關的項，以方便計算機的進一步處理。對于分詞現(xiàn)有的方法比較多，我們使用最大匹配法(Maximum Matching Metho d，M M)進行分詞處理。M M法是對給定的待分詞的漢字串s按照某種確定的原則(正向或逆向)取s的子串，若該子串和詞庫中的某詞條相匹配，則該子串是詞，繼續(xù)分割剩余的部分，直到剩余部分為空，否則，該子串不是詞，則取s的子串進行匹配。這是一種比較成熟，目前使用比較廣泛的漢字分詞方法。

分詞后的詞條中含有大量的單個獨立字，這些單個的字不僅所攜帶的文本信息較少，而且還對其它實詞起到一定的抑制作用，降低了分類過程中的處理效率和準確度，[4]所以要對這些獨立字進行去除。文本經(jīng)過以上預處理之后，就得到了文本的原始特征集T。

3.2 文本特征值的提取

經(jīng)過預處理的原始特征集還存在有項數(shù)過多，文本的特征提取實際上是一個降維的過程，目的是減少計算復雜度，提高分類效率。特征值提取是在經(jīng)過分詞處理后的原始特征集T=｛t1,t2,…,tN｝ 中選擇出用于實際應用的子集T'=｛t1,t2,…,tn｝，其中N為原始特征集維數(shù)，n為實際應用的特征集維數(shù)，n

選擇的標準是在不改變原始特征空間性質(zhì)的前提下，從原始特征空間中選擇一部分重要的特征，組成一個新的低維空間，用以提高文本分類效率。本文采用期望交叉熵這個定量來進行文本特征集中項的取舍。定義文本中的有效項為t，文本的類別為C，文檔的類別數(shù)為m，那么交叉熵的大小由式(1)完成計算。

我們把所有用于訓練的M個文本特征集定義為文本域D=｛T1',T2',…,Tm｝'，然后將D分成兩個子集：自體集合和非自體集合有，自體集合即所有抗體(A b)構(gòu)成的集合，代表分類器中已有的記憶細胞；非自體集合即抗原(A g)構(gòu)成的集合，代表要進行分類的文本。我們模仿生物免疫系統(tǒng)，用記憶細胞集合對抗原集合進行動態(tài)耐受來生成成熟細胞，將耐受后親和力大于給定閾值的抗原放入成熟細胞集合。對于成熟細胞，一方面把對其進行克隆操作和變異操作，[5]使之生成新的用于動態(tài)耐受的抗原；另一方面要對新進入集合的成熟細胞進行去重處理，以保證記憶細胞集合中的細胞數(shù)量不至于過多而影響到整個識別效率。

成熟細胞的克隆和變異和細胞在耐受過程中的親和力有關。在克隆時，親和力與增殖復制量成正比，親和力越高，復制量越大，用以保證群體親和力逐步增大，提高分類器識別效率。在變異時，變異量與親和力成反比，也就是說親和力越高，變異量越少，這樣做可以保留最佳細胞，改進較差細胞。

當整個訓練過程都完成后，最后得到的記憶細胞集合，亦即自體集合S，就是我們所要生成的文本分類器。其原理圖如下圖所示。

3.3 文本分類實現(xiàn)

其中P(Ci|t)表示特征項t在屬于類別Ci的文檔內(nèi)出現(xiàn)的概率；P(Ci)表示文檔屬于類別Ci的概率。C E的值越大，則特征項t對文本類別分布的權(quán)值就越大。用該算法提取具有最高C E值的n個詞,建立具有n個特征值的特征子集T'=｛t1,t2,…,tn｝。

圖 文本分類器的生成原理

具體步驟可描述如下：

Step1：經(jīng)過特征提取的M個訓練文本，抽取一部分用作抗體集合A B=｛A b1,A b2,…,A bM1｝，也就是分類器中的記憶細胞，剩下的部分作為待識別的抗原集合A G=｛A g1,A g2,…,A gM2｝，其中M 1+M 2=M。

Step2：對抗原(未成熟細胞)進行動態(tài)耐受，耐受過程使用肯定選擇算法，[6]動態(tài)耐受中的親和力計算我們采用Euclidean距離d來表示，距離與親和力r成反比，d越小，親和力r越大。由式(2)(3)完成計算。

Step3：將耐受過程中親和力大于閾值ε的細胞送入成熟細胞的集合，親和力小于ε的細胞則刪除，令其死亡。

Step4：將成熟細胞進行克隆和變異，克隆的復制量與親和力r成正比，變異的變異量與r成反比，迭代次數(shù)age為10。

Step5：將成熟細胞與記憶細胞集合進行相似度計算，將相似度小于閾值θ的細胞加入到記憶細胞集合中，相似度大于θ的細胞則刪除，令其死亡。

當所有的抗原都與自體作用完畢后，最后得到的記憶細胞集合就是我們用于文本分類的分類器，下來我們就可以用該分類器對文本進行自動分類。

4 實驗：以Web信息分類為例

實驗中使用從人民網(wǎng)和新華網(wǎng)上采集到的We b文檔作為網(wǎng)頁數(shù)據(jù)集合，所屬文本類別按照網(wǎng)站上給定的分類進行歸屬。共選了新聞、經(jīng)濟、體育、房產(chǎn)四類文本共2800篇文章，每類700篇。每一類的前500篇作為訓練文本進行訓練，后200篇用作測試文本。實驗結(jié)果如下表所示。

表 實驗結(jié)果表

由表中文本識別的準確率和查全率可以看出，本文所采用的基于人工免疫生成的文本分類器在文本自動分類中有著比較好的效果。在政府災害管理等涉及社會領域較廣的公共事務領域，該方法對于災害信息資源的整理和分類，具有一定的普適性。

5 結(jié)論

人工免疫系統(tǒng)所具有的多樣性、耐受性、自學習、魯棒性等特點，為文本自動分類提供了良好的思路和解決辦法。本文利用人工免疫的動態(tài)耐受和克隆變異等機制提出了一種文本分類器的產(chǎn)生方法，從實驗結(jié)果來看效果良好。由于人工免疫系統(tǒng)的仿生機理復雜并且龐大，因此如何將更多的仿生機制融合到文本分類中，以及將這些方法更好地應用到面向政府決策支持的災害信息資源管理等政府信息管理領域，是進一步要研究的方向。

[1] 中國互聯(lián)網(wǎng)中心 [E B/O L].[2012－05－09]．htt p://www.cnnic.net.c n/index/0 E/00/11/index.htm.

[2] Jiawei Han, Micheline Kamber. Data Mining: Conceptand Techniques [M]．Morgan Kaufmann Publishers,Inc．2001.

[3] 李濤.計算機免疫學[M].北京：電子工業(yè)出版社,2004.

[4] YimingYang，XinLiu．ARe- Examination of Text CategorizationMethods [C]．Proceedings of ACMSIGIRConference on Research and Development in InformationRetrieval （SIGIR），1999：42- 49.

[5] J Hunt， et al．Jisys: The development of an ArtificialImmune System for real world applications [M]．Springer- Verlag, 1999.

[6] Seiden P E, Celada F. A Model for Simulating CognateRecognition andResearch in the Immune System[J]．J.theor.Biol. , 158：329- 357，1992.