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

●何曉慶，賈 釗

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

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

1 引言

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

2 人工免疫與文本分類

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

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

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

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

3.1 文本的表示和分詞

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

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

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

3.2 文本特征值的提取

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

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

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

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

當(dāng)整個(gè)訓(xùn)練過(guò)程都完成后，最后得到的記憶細(xì)胞集合，亦即自體集合S，就是我們所要生成的文本分類器。其原理圖如下圖所示。

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

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

圖 文本分類器的生成原理

具體步驟可描述如下：

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

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

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

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

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

當(dāng)所有的抗原都與自體作用完畢后，最后得到的記憶細(xì)胞集合就是我們用于文本分類的分類器，下來(lái)我們就可以用該分類器對(duì)文本進(jìn)行自動(dòng)分類。

4 實(shí)驗(yàn)：以Web信息分類為例

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

表 實(shí)驗(yàn)結(jié)果表

由表中文本識(shí)別的準(zhǔn)確率和查全率可以看出，本文所采用的基于人工免疫生成的文本分類器在文本自動(dòng)分類中有著比較好的效果。在政府災(zāi)害管理等涉及社會(huì)領(lǐng)域較廣的公共事務(wù)領(lǐng)域，該方法對(duì)于災(zāi)害信息資源的整理和分類，具有一定的普適性。

5 結(jié)論

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

[1] 中國(guó)互聯(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] 李濤.計(jì)算機(jī)免疫學(xué)[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.