杜芳華,冀俊忠,吳晨生,吳金源

(1.北京工業(yè)大學計算機學院多媒體與智能軟件技術北京市重點實驗室,北京100124;

2.北京市科學技術情報研究所,北京100048)

基于蟻群聚集信息素的半監(jiān)督文本分類算法

杜芳華1,冀俊忠1,吳晨生2,吳金源1

(1.北京工業(yè)大學計算機學院多媒體與智能軟件技術北京市重點實驗室,北京100124;

2.北京市科學技術情報研究所,北京100048)

半監(jiān)督文本分類中已標記數據與未標記數據分布不一致,可能導致分類器性能較低。為此,提出一種利用蟻群聚集信息素濃度的半監(jiān)督文本分類算法。將聚集信息素與傳統(tǒng)的文本相似度計算相融合,利用Top-k策略選取出未標記螞蟻可能歸屬的種群,依據判斷規(guī)則判定未標記螞蟻的置信度,采用隨機選擇策略,把置信度高的未標記螞蟻加入到對其最有吸引力的訓練種群中。在標準數據集上與樸素貝葉斯算法和EM算法進行對比實驗,結果表明,該算法在精確率、召回率以及F1度量方面都取得了更好的效果。

文本分類;半監(jiān)督學習;聚集信息素;自訓練;Top-k策略;隨機選擇策略

1 概述

基于機器學習原理的有監(jiān)督文本分類技術［1］,已在自然語言處理［2］、信息過濾、文本挖掘［3］、情感挖掘、輿情監(jiān)控等領域具有廣泛的應用,但是有監(jiān)督的文本分類方法一般都需要事先擁有大量的已標記數據來完成分類器的訓練。然而,隨著大數據時代的到來,人們通常得到的數據往往是海量的且數據分布未知的未標記數據［4］。由于客觀資源的限制和手工標記數據的主觀性,因此在實際應用中準確地獲取大量的已標記數據非常困難。面對這一挑戰(zhàn),基于半監(jiān)督學習的分類器迅速興起,并成為有效解決該問題的一種途徑［5-6］。 半監(jiān)督學習(semisupervised learning)是指利用少量已標記數據和大量未標記數據來進行分類的學習技術［7］,其基本思想是基于數據分布上的模型假設［8-9］,建立學習器來對未標記數據進行標記。

目前,已有許多學者對半監(jiān)督文本分類進行了研究。文獻［10-11］將EM算法與樸素貝葉斯分類器(Na?ve Bayes classifier)相結合實現了一種半監(jiān)督的文本分類。該算法首先利用已標記樣本來訓練一個初始的分類器,然后用這個分類器對未標記樣本進行不確定性標記,從而使每個未標記樣本都部分地屬于某一類別。再利用所有的樣本訓練新的分類器,這一步驟迭代進行直到分類器穩(wěn)定為止。文獻［12］提出了基于自訓練的改進EM算法。在利用EM算法訓練中間分類器的過程中,引入了利用中間結果的自訓練機制,即將置信度高的未標記樣本加到已標記樣本集中,能夠使未標記數據集不斷縮小,從而加快迭代速度,提高分類器的訓練性能。但是由于訓練出的中間分類器也可能存在比較大的誤分類,因此該方法并不適用于已標記類別比較相似的情況。文獻［13］提出了一種基于緊密度的半監(jiān)督文本分類方法。這種方法首先在負例集合中提取出一些置信度較高的負例,然后再根據未標記集合中樣本與正例以及抽取出負例的相應緊密度來對可信的負例集合進行相應的擴展,得到用于分類訓練所用的負例集合。最后結合訓練集中原來給出的正例集,進行文本分類。由于此方法只擴展了負例集合,因此并不適用于正例集合本身就比較少的情況。上述這些半監(jiān)督文本分類算法本質上都是基于數據統(tǒng)計理論上的分布假設,即將已標記樣本與未標記樣本視為具有獨立同分布的文本數據。但是,這一假設在現實世界中一般難以成立,這是因為大量未標記樣本可能來自于與已標記樣本的分布不同或完全未知的環(huán)境,而且這些未標記樣本可能帶有噪聲。當未標記樣本的分布與已標記樣本不同時,使用未標記樣本可能會降低分類器的性能。因此,如何在已標記樣本的分布與未標記樣本的分布有較大差異的情況下,提高半監(jiān)督文本學習器的性能,已經成為半監(jiān)督學習領域的一個研究熱點。

本文借鑒了基于蟻群聚集信息素濃度的半監(jiān)督分類算法(Aggregation Pheromone Density Based Semi-Supervised Classification,APSSC)的基本思想,提出一種基于蟻群聚集信息素濃度的半監(jiān)督文本分類算法。針對文本數據,將文本相似度融合到聚集信息素的計算之中,從而擴展了聚集信息素濃度的計算模型。

2 基于蟻群聚集信息素濃度的半監(jiān)督分類算法

文獻［14］將蟻群聚集信息素引入到半監(jiān)督分類中,提出了APSSC算法,它是一種自訓練的算法,并在非文本數據集上取得了比較好的效果。聚集信息素(aggregation pheromone)［15］是螞蟻等昆蟲分泌的一種化學物,可用于招引同種個體一起棲息,共同取食,攻擊異種對象,并最終形成群集智能的整體行為。

其中,ρ∈［0,1］是蒸發(fā)常量。

化處理,得到歸一化的聚集信息素濃度:

其中,K為訓練種群總數。

(4)根據算法1選取置信度高的未標記螞蟻加入到對其最有吸引力的一個訓練種群h中,它將在(t+1)代的自訓練過程中作為種群 h的已標記螞蟻。

(5)當訓練種群全部穩(wěn)定時,自訓練過程結束,此時訓練種群已經得到了擴展;否則,進入t+1代學習。

可見,APSSC算法的自訓練過程是一個利用大量置信度高的未標記螞蟻對訓練種群進行擴展的過程。因此,如何選取置信度高的未標記螞蟻即算法1,是APSSC算法的核心。自訓練過程完成以后,進入測試過程。

在測試過程中,根據種群k對測試螞蟻an釋放聚集信息素濃度Δnk(見式(5)),把測試螞蟻an分到對它釋放了最多聚集信息素的種群h中,即測試螞蟻an歸屬于種群h。

算法1 選取置信度高的未標記螞蟻

輸出 擴展后的訓練種群h

3 本文算法

3.1 APSSC算法在處理文本時存在的問題

APSSC算法在Ionosphere、Balance Scale、Sonar等來自UCI的數據集上取得了比較好的效果,證明了蟻群聚集信息素在半監(jiān)督學習中的有效性,但由于該算法存在著如下不足,使其無法完成文本分類。

(1)由式(2)可以看出,其聚集信息素計算公式中數據集的維度d作為2π的指數出現在分母中,由于2π＞e,當d取值比較大時,式(2)趨向于0,因此該算法不能處理像文本這樣的高維度數據。

也就是說,當遇到類別比較多且相似性較大的文本數據集時,該算法可能會學習不到置信度高的螞蟻,從而無法達到擴展訓練種群的目的。

3.2 SSTCACAP算法的主要思想

本文對APSSC算法進行了擴展,提出了基于蟻群聚集信息素濃度的半監(jiān)督文本分類算法(Semi-Supervised Text Classification Based on Ant Colony Aggregation Pheromone,SSTCACAP),使其能有效處理文本數據。

首先,根據文本數據高維稀疏的特點,結合文本相似度與聚集信息素之間的關系,將文本相似度作為蟻群聚集信息素濃度計算公式的一個影響因子,擴展了蟻群聚集信息素濃度的計算模型:

相應地擴展了測試過程中種群k對測試螞蟻釋放的聚集信息素濃度計算模型:

其次,根據文本數據集類別多且相似性高的特點,利用Top-k策略和隨機選擇策略擴展了APSSC算法中選取置信度高的未標記螞蟻算法即算法1,得到擴展后的算法2,具體的擴展過程如下:

在半監(jiān)督學習過程中,因為文本數據本身可能攜帶多個類別特征,并且初始的訓練種群包含的種群特征信息非常有限,所以各個訓練種群對其釋放的聚集信息素的差別很小,甚至可能出現幾個種群對其釋放的聚集信息素濃度相同的情況。因此,在判定未標記螞蟻置信度的過程中,采用在Web搜索引擎中被廣泛使用的Top-k查詢策略,選取對其最有吸引力的 k個種群,組成一個候選種群集合TTop-k。根據集合TTop-k中包含的種群數量來判定未標記螞蟻的置信度,判定規(guī)則為:

其中,|TTop-k|是TTop-k包含的種群數;K是訓練種群總數;β是設定的閾值。

當未標記螞蟻滿足判定式(9)時,就判定它的置信度高。這種Top-k策略可以有效處理因訓練種群對未標記螞蟻釋放的聚集信息素差別較小而可能學習不到置信度高的未標記螞蟻的情況。

3.3 SSTCACAP算法描述

在SSTCACAP算法的每一代學習中,需要判定每一只未標記螞蟻的置信度,并利用置信度高的未標記螞蟻擴展訓練種群。算法描述如下:

算法2 選取置信度高的未標記螞蟻

輸入 未標記螞蟻

輸出 擴展后的訓練種群h

4 實驗結果與分析

采用著名的語料庫20 Newsgroups,從中挑選5個comp.*類數據來進行實驗。對文本的預處理采用了去除停用詞(stop word)和基于信息增益(IG)的特征選擇等方法。在實驗中隨機地從每個類別中選取20%的文本作為測試樣本集,然后再從剩余的文本中選取50%作為固定的未標記樣本集。算法的評價度量采用精確率(precision)、召回率(recall)和宏平均F1度量(Macro F1),其中,宏平均F1度量的計算公式為:

其中,K為類別總數。實驗中SSTCACAP算法使用的參數配置δ=1.0,α=0.9,β=0.6。EM算法采用文獻［10］的終止條件。本文比較了 SSTCACAP、EM以及Na?ve Bayes算法的分類效果。通過不斷改變已標記樣本集的大小,得出算法的精確率、召回率以及宏平均F1度量與已標記樣本集大小之間的關系圖,如圖1～圖3所示。

圖1 精確率比較

圖2 召回率比較

圖3 宏平均F1度量比較

由圖 1可以看出,2種半監(jiān)督學習方法SSTCACAP算法和EM算法在引入未標記樣本后,都在一定程度上提高了分類的精確性,尤其在已標記樣本較少的情況下,半監(jiān)督學習方法的分類性能表現更好,且本文SSTCACAP算法的精確率比傳統(tǒng)有監(jiān)督的方法Na?ve Bayes算法提高了5%。SSTCACAP算法在大部分情況下,分類精確率都高于EM算法和Na?ve Bayes算法,只有在20%已標記樣本時,精確率低于EM算法。例外產生的一個可能原因是由于某個訓練種群的吸引力遠大于其他的訓練種群,使得這個訓練種群學習到了大部分置信度高的未標記螞蟻,從而出現了相對較多的誤分情況。隨著已標記樣本數量的增加,出現了Na?ve Bayes算法的分類精確率高于EM算法的情況。其中一個可能的原因是此時已標記樣本的數據分布與未標記樣本的數據分布存在較大的差異,導致EM算法學習到的分類器的性能下降。而本文SSTCACAP算法沒有出現分類性能低于Na?ve Bayes的情況,表明SSTCACAP算法的穩(wěn)定性要優(yōu)于EM算法。

由圖2可以看出,本文SSTCACAP算法在召回率方面的表現是最好的,大部分情況下召回率高于60%,要優(yōu)于EM算法和Na?ve Bayes算法。且在5%已標記樣本時,本文提出的SSTCACAP算法分類性能比EM算法和Na?ve Bayes算法分別提高了7.5%和5.1%。而另一種半監(jiān)督學習方法EM算法和傳統(tǒng)的有監(jiān)督的學習方法Na?ve Bayes算法在已標記樣本低于20%時,分類性能出現了交替上升的情況。出現這種情況的原因是基于樣本數據分布理論假設的半監(jiān)督學習方法在無法保證已標記樣本與未標記樣本的分布一致的情況下,導致半監(jiān)督學習方法學到的分類器的性能下降。

由圖3可以看出,本文提出的SSTCACAP算法在宏平均F1度量(Macro F1)方面的分類性能也是最好的。只有在 5% 已標記樣本的情況下, SSTCACAP算法的宏平均F1度量低于60%,但是SSTCACAP算法比EM算法和Na?ve Bayes算法在性能上分別提高了10.7%和8.1%。且只有在20%已標記數據時,另一種半監(jiān)督學習方法EM算法的分類性能達到了本文SSTCACAP算法的水平。而EM算法在已標記樣本低于20%時,分類性能與Na?ve Bayes算法相當,并沒有明顯的提升。

5 結束語

本文提出一種基于蟻群聚集信息素濃度的半監(jiān)督文本分類算法。在計算蟻群聚集信息素濃度時,把文本相似度作為其中的一個重要因素,擴展了聚集信息素濃度計算模型。在半監(jiān)督學習過程中,首先使用Top-k策略找出未標記螞蟻可能歸屬的種群集合,然后根據判斷規(guī)則計算并判定未標記螞蟻的置信度,最后利用隨機選擇的策略,把符合置信度條件的未標記螞蟻加入到一個訓練種群中,達到對訓練種群進行擴展的目的。實驗結果驗證了本文算法的有效性。

在本文提出的基于蟻群聚集信息素濃度的半監(jiān)督文本分類算法中,有一個重要的步驟就是需要對算法中的參數進行人工設置,并且參數選擇的好壞也會影響分類的效果,因此,下一步的工作是對算法中的參數優(yōu)化進行研究,以期進一步提高該算法的性能。

［1］ Sebastiani F.Machine Learning in Automated Text Categorization［J］.ACM Computing Surveys,2002, 34(1):1-47.

［2］ 蘇金樹,張博峰,徐 昕.基于機器學習的文本分類技術研究進展［J］.軟件學報,2006,17(9):1848-1859.

［3］ 王建會,王洪偉,申 展,等.一種實用高效的文本分類算法［J］.計算機研究與發(fā)展,2005,42(1):85-93.

［4］ 周志華,王 玨.機器學習及其應用［M］.北京:清華大學出版社,2007.

［5］ Zhu Xiaojin.Semi-supervised Learning Literature Survey［R］.University of Wisconsin,Technical Report:CS-1530,2008.

［6］ Zhu Xiaojin,Goldberg A B.Introduction to Semisupervised Learning［M］.［S.l.］:Morgan&Claypool Publishers,2009.

［7］ Cohen I,Cozman F G,Sebe N.Semi-supervised Learning of Classifiers:Theory,Algorithm,and Their Application to Human-computer Interaction［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(12):1553-1567.

［8］ Blum A,Chawla S.Learning from Labeled and Unlabeled Data Using Graph Mincuts［C］//Proceedings ofthe 18th InternationalConference on Machine Learning.San Francisco,USA:［s.n.］,2001:19-26.

［9］ Li Ming,ZhouZhihua.SETRED:Self-training with Editing［C］//Proceedings of the 9th Pacific-Asia Conference on Knowledge Discovery and Data Mining.Hanoi,Vietnam:［s.n.］,2005:611-621.

［10］ Nigam K,McCallum A K,Thrun S.Text Classification from Labeled and Unlabeled Documents Using EM［J］.Machine Learning,2000,39(2/3):103-134.

［11］ Nigam K.Using Unlabeled Data to Improve Text Classification［D］.［S.l.］:Carnegie Mellon University, 2001.

［12］ 張博峰,白 冰,蘇金樹.基于自訓練EM算法的半監(jiān)督文本分類［J］.國防科技大學學報,2007,29(6): 65-69.

［13］ 鄭海清,林 琛,牛軍鈺.一種基于緊密度的半監(jiān)督文本分類方法［J］.中文信息學報,2007,21(3):54-60.

［14］ Halder A,Ghosh S,Ghosh A.Aggregation Pheromone Metaphor for Semi-supervised Classification［J］.Pattern Recognition,2013,46(8):2239-2248.

［15］ Tsutsui S.AntColony Optimization forContinuous Domains with Aggregation Pheromones Metaphor［C］// Proceedings of the 5th International Conference on Recent Advances in Soft Computing.Nottingham,UK:［s.n.］,2004:207-212.

編輯 任吉慧

Semi-supervised Text Classification Algorithm Based on Ant Colony Aggregation Pheromone

DU Fanghua1,JI Junzhong1,WU Chensheng2,WU Jinyuan1
(1.Beijing Municipal Key Laboratory of Multimedia and Intelligent Software Technology,College of Computer Science and Technology,Beijing University of Technology,Beijing 100124,China;
2.Beijing Institute of Science and Technology Information,Beijing 100048,China)

There are many algorithms based on data distribution to effectively solve semi-supervised text categorization.However,they may perform badly when the labeled data distribution is different from the unlabeled data.This paper presents a semi-supervised text classification algorithm based on aggregation pheromone,which is used for species aggregation in real ants and other insects.The proposed method,which has no assumption regarding the data distribution, can be applied to any kind of data distribution.In light of aggregation pheromone,colonies that unlabeled ants may belong to are selected with a Top-k strategy.Then the confidence of unlabeled ants is determined by a judgment rule.Unlabeled ants with higher confidence are added into the most attractive training colony by a random selection strategy.Compared with Na?ve Bayes and EM algorithm,the experiments on benchmark dataset show that this algorithm performs better on precision,recall and Macro F1.

text classification;semi-supervised learning;aggregation pheromone;self-training;Top-k strategy; random selection strategy

1000-3428(2014)11-0167-05

A

TP311.12

10.3969/j.issn.1000-3428.2014.11.033

國家自然科學基金資助項目(61375059,61332016)。

杜芳華(1988-),男,碩士研究生,主研方向:數據挖掘,機器學習;冀俊忠,教授;吳晨生,研究員;吳金源,碩士研究生。

2013-11-13

2014-01-07E-mail:fanghuadu@126.com

中文引用格式:杜芳華,冀俊忠,吳晨生,等.基于蟻群聚集信息素的半監(jiān)督文本分類算法［J］.計算機工程,2014, 40(11):167-171.

英文引用格式:Du Fanghua,Ji Junzhong,Wu Chensheng,et al.Semi-supervised Text Classification Algorithm Based on Ant Colony Aggregation Pheromone［J］.Computer Engineering,2014,40(11):167-171.