孫學(xué)琛，高志強(qiáng)，全志斌，施嘉鴻

（東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇南京211189）

自20世紀(jì)50年代以來，人們對文本自動分類的研究獲得了豐碩的成果，但這些研究都局限于長文本，對短文本分類問題涉及較少．短文本分類是一種特殊的文本分類任務(wù)，隨著萬維網(wǎng)（world wide web）的快速普及和發(fā)展，web上出現(xiàn)了大量短文本，例如科技文獻(xiàn)摘要、微博和電子郵件．短文本內(nèi)容短小，相互聯(lián)系，已標(biāo)注數(shù)據(jù)獲得困難，傳統(tǒng)分類方法已經(jīng)不能適用于短文本分類場景．短文本分類對于獲取數(shù)據(jù)的分布特征以及后續(xù)進(jìn)一步的數(shù)據(jù)挖掘工作有重要的意義．

1 問題描述

短文本在日常生活中非常常見，例如數(shù)字化圖書館中的論文快照（包括標(biāo)題、摘要、參考文獻(xiàn)等，但不包括正文內(nèi)容）、微博（少于140字）和搜索引擎片段等．本文的主要研究分類對象是論文快照（在沒有特別說明的情況下，本文所指論文均指論文快照）．短文本的特征主要有兩個，一是內(nèi)容短小，二是特征稀疏．這就導(dǎo)致使用傳統(tǒng)的基于bag－of－words表示方法的分類器很難取得令人滿意的效果．另外，短文本的規(guī)模一般很大，而已標(biāo)注的數(shù)據(jù)卻很少，利用手工方法對數(shù)據(jù)進(jìn)行標(biāo)注非常耗時(shí)耗力．如何利用少量的已標(biāo)注數(shù)據(jù)和大量未標(biāo)注數(shù)據(jù)進(jìn)行學(xué)習(xí)，從而對短文本數(shù)據(jù)進(jìn)行高效分類，是本文研究的主要問題．

2 相關(guān)研究

對短文本分類的研究在九十年代末才逐漸引起人們的注意，文獻(xiàn)［1] 提出了一種使用作者信息和tweets內(nèi)部特征的Twitter短文本分類方法，取得了較好的分類效果，由于采用手工尋找類別特征的方法，所以通用性較差．文獻(xiàn)［2] 使用維基百科作為外部通用數(shù)據(jù)集，在通用數(shù)據(jù)集上使用LDA（Latent Dirichlet Allocation）獲得主題模型，經(jīng)過推理得到待分類短文本的主題特征向量，使用詞向量和主題向量一起用于分類過程，取得了較好的分類效果．文獻(xiàn)［3] 總結(jié)了常用的協(xié)作分類（Collective Classification，CC）方法，它將整個數(shù)據(jù)集看成實(shí)例組成的網(wǎng)絡(luò)，網(wǎng)絡(luò)蘊(yùn)含了實(shí)例之間的聯(lián)系，借助于網(wǎng)絡(luò)結(jié)構(gòu)訓(xùn)練分類器以提高分類性能，實(shí)驗(yàn)證明協(xié)作分類的效果優(yōu)于基于內(nèi)容的分類器．上述研究成果都側(cè)重于關(guān)系數(shù)據(jù)使用，而沒有考慮在較少已標(biāo)記數(shù)據(jù)時(shí)的學(xué)習(xí)問題．半監(jiān)督學(xué)習(xí)是一種利用較少已標(biāo)記數(shù)據(jù)和大量未標(biāo)注數(shù)據(jù)進(jìn)行學(xué)習(xí)的方法．文獻(xiàn)［4] 提出了協(xié)同訓(xùn)練算法，并給出了使用未標(biāo)注數(shù)據(jù)學(xué)習(xí)的PAC（Probably Approximately Correct）形式分析，但它假設(shè)數(shù)據(jù)集有兩個充分冗余視圖很難得到滿足．本文在上述相關(guān)研究工作基礎(chǔ)上綜合協(xié)同分類和半監(jiān)督學(xué)習(xí)技術(shù)，提出了一種基于半監(jiān)督學(xué)習(xí)的短文本分類方法．

3 基于半監(jiān)督學(xué)習(xí)的迭代分類算法

在傳統(tǒng)的監(jiān)督學(xué)習(xí)中，學(xué)習(xí)器通過對大量有標(biāo)記訓(xùn)練樣例進(jìn)行學(xué)習(xí)，從而建立模型用于預(yù)測未見示例的標(biāo)記．隨著數(shù)據(jù)收集和存儲技術(shù)的飛速發(fā)展，收集大量未標(biāo)記實(shí)例已相當(dāng)容易，而獲取大量有標(biāo)記的實(shí)例則相對較為困難．如果只使用少量的已標(biāo)記實(shí)例，那么利用它們所訓(xùn)練出的學(xué)習(xí)器往往很難具有強(qiáng)泛化能力．另一方面，如果僅使用少量昂貴的已標(biāo)記實(shí)例而不利用大量廉價(jià)未標(biāo)記實(shí)例，則是對資源的極大浪費(fèi)．因此，在已標(biāo)記實(shí)例較少時(shí)，如何利用大量的未標(biāo)記實(shí)例來改善學(xué)習(xí)性能已成為當(dāng)前機(jī)器學(xué)習(xí)研究中最受關(guān)注的問題之一．

半監(jiān)督學(xué)習(xí)是利用少量標(biāo)注數(shù)據(jù)和大量未標(biāo)注數(shù)據(jù)進(jìn)行學(xué)習(xí)的框架．由于短文本數(shù)量巨大，而且僅有少量的已標(biāo)注數(shù)據(jù)，所以短文本分類本身就是一個半監(jiān)督學(xué)習(xí)問題．借鑒半監(jiān)督學(xué)習(xí)的思想，本文提出了基于半監(jiān)督學(xué)習(xí)的迭代分類算法（semi－supervised learning－based iterative classification algorithm，SS－ICA）．

3．1 數(shù)據(jù)模型

不同的分類方法對數(shù)據(jù)集模型的假設(shè)是不同的，常用的假設(shè)有兩種，如圖1所示．大部分只基于內(nèi)容的（Content－Only，CO）分類器使用圖1a所示的模型，它強(qiáng)調(diào)實(shí)例的獨(dú)立性，實(shí)例通過它的內(nèi)部特征表示，實(shí)例之間彼此是沒有聯(lián)系的．在分類問題中，實(shí)例的類別僅僅和它的內(nèi)容相關(guān)．例如樸素貝葉斯分類器（Naive Bayes Classifier，NB）．協(xié)作分類采用了如圖1b所示的模型，它強(qiáng)調(diào)實(shí)例之間聯(lián)系的重要性，在分類過程中綜合利用實(shí)例的內(nèi)部特征和外部關(guān)系．例如迭代分類算法［5]（Iterative Classification Algorithm，ICA）．本文提出的基于半監(jiān)督的迭代分類算法采用了圖1b所示的數(shù)據(jù)模型．

圖1 文本分類數(shù)據(jù)集模型

對于圖1b的模型，給出如下形式化定義．?dāng)?shù)據(jù)集由一組結(jié)點(diǎn)V＝｛V1，…Vn｝和一組近鄰函數(shù)N描述，Ni?V＼｛Vi｝，N體現(xiàn)了整個網(wǎng)絡(luò)的結(jié)構(gòu)．V中的每個結(jié)點(diǎn)都是在特定領(lǐng)域中取值的隨機(jī)變量，可以根據(jù)結(jié)點(diǎn)的類別是否已知將V分為已知結(jié)點(diǎn)集合X和待分類結(jié)點(diǎn)集合Y．類別的集合為L＝｛L1，…，Lq｝，分類任務(wù)是為結(jié)點(diǎn)Yi∈Y賦予一個合理的類別，簡記分類后Yi的標(biāo)記為yi．

3．2 算法描述

基于半監(jiān)督學(xué)習(xí)的迭代分類算法底層依賴于CO分類器．CO分類器一般要求輸入特征向量有固定的維數(shù)，對于關(guān)系數(shù)據(jù)，可以采用聚合算子［3]將外部關(guān)系聚合成實(shí)例的關(guān)系屬性，實(shí)例的關(guān)系屬性和內(nèi)部屬性共同組成實(shí)例的特征向量用于訓(xùn)練和分類過程．下面給出基于半監(jiān)督學(xué)習(xí)的迭代分類算法流程圖（圖2）與詳細(xì)描述．

圖2 SS－ICA算法流程圖

1）對每個實(shí)例Vi：根據(jù)鄰接關(guān)系Ni計(jì)算特征向量ai，在后續(xù)分類過程中均使用ai．

2）使用X作為訓(xùn)練集訓(xùn)練分類器f．

3）對Y中的每個實(shí)例Yi：使用f進(jìn)行分類，yi←f（ai）．

4）使用X∩Y作為訓(xùn)練集更新分類器f．

5）對Y中的每個實(shí)例Y1：根據(jù)現(xiàn)在的Ni重新聚合更新ai，使用f進(jìn)行分類，yi←f（ai）．

6）如果達(dá)到預(yù)設(shè)迭代次數(shù)或類標(biāo)記穩(wěn)定，則分類結(jié)束，否則執(zhí)行步驟3）．

ICA是一種簡單有效的迭代分類方法，假定初始訓(xùn)練數(shù)據(jù)數(shù)目是充足的，整個訓(xùn)練過程都依靠使用初始訓(xùn)練數(shù)據(jù)訓(xùn)練得到的分類器f．由于f的性能和泛化能力受到已標(biāo)注數(shù)據(jù)質(zhì)量和數(shù)量的制約，如果初始訓(xùn)練數(shù)據(jù)數(shù)目較少，訓(xùn)練得到的局部分類器f將很難刻畫真實(shí)的分類邊界，迭代過程在增加外部關(guān)系作用的同時(shí)，也放大了f所帶來的誤差，導(dǎo)致整個迭代過程不能得到較高的分類精度．

SS－ICA也是一個迭代的分類過程，但是不同于ICA，迭代過程中不僅考慮到引入外部信息，同時(shí)也考慮到迭代中未標(biāo)記數(shù)據(jù)對分類器本身的影響．初次用于訓(xùn)練的已標(biāo)注數(shù)據(jù)過少，聚合后特征向量的外部關(guān)系特征不精確，訓(xùn)練得到的f有著一定的誤差．迭代中使用f對未標(biāo)注數(shù)據(jù)進(jìn)行分類后，再次聚合使得向量外部關(guān)系特征被進(jìn)一步豐富，更趨向真實(shí)的分布，使用更新后的數(shù)據(jù)訓(xùn)練分類器將會提高分類器正確分類的能力．這樣就可以在迭代過程中有效地使用未標(biāo)記數(shù)據(jù)．實(shí)驗(yàn)證明，SS－ICA方法在訓(xùn)練數(shù)據(jù)稀少的情況下對改善分類精度是十分有效的．

4 實(shí)驗(yàn)結(jié)果與分析

本文使用兩個關(guān)系數(shù)據(jù)集CORA［6]和CiteSeer［7]進(jìn)行試驗(yàn)．CORA包含了一系列計(jì)算機(jī)科學(xué)領(lǐng)域的學(xué)術(shù)論文（包括摘要和引用信息）．CiteSeer也是一個計(jì)算機(jī)科學(xué)領(lǐng)域的數(shù)據(jù)集，它的引用關(guān)系密度比CORA?。畠蓚€數(shù)據(jù)集均使用文檔頻數(shù)方法進(jìn)行特征選擇，刪除了單詞出現(xiàn)次數(shù)少于10的所有單詞屬性．CORA和CiteSeer的詳細(xì)信息見表1．

表1 CORA和CiteSeer數(shù)據(jù)集詳細(xì)信息

實(shí)驗(yàn)使用NB和ICA與本文提出的SS－ICA方法進(jìn)行了對比．其中NB分類器由WEKA［8]工具包提供，ICA和SS－ICA均采用NB作為迭代分類器，均采用計(jì)數(shù)聚合［5]（Count Aggregation）作為聚合算子．實(shí)驗(yàn)使用選擇采樣技術(shù)［9]隨機(jī)采樣，迭代次數(shù)為10次，精度取10次采樣實(shí)驗(yàn)的平均值．表2是在不同已標(biāo)注樣本比例訓(xùn)練集上的實(shí)驗(yàn)結(jié)果．

表2 各分類器在不同標(biāo)注比例訓(xùn)練集上的性能

由表2可知，當(dāng)初始已標(biāo)注數(shù)據(jù)稀少的情況下SS－ICA的分類精度明顯高于NB和ICA，在初始標(biāo)注比例為5%時(shí)，SS－ICA要比其他分類器的分類精度高出13%以上．注意到在初始標(biāo)注比例為5%時(shí)，ICA的分類精度要低于NB，這是因?yàn)闃?biāo)注數(shù)據(jù)稀少導(dǎo)致學(xué)習(xí)到的分類器泛化能力太差，而在迭代過程中分類器誤差被放大導(dǎo)致的．

ICA和SS－ICA在CORA數(shù)據(jù)集上的分類精度要高于CiteSeer上的分類精度，這是因?yàn)榍罢叩倪B接密度要高于后者，而高連接密度可以有效提高協(xié)作分類精度．由于NB只是基于內(nèi)容的分類，所以在兩個數(shù)據(jù)集上有著相似的性能．在總體上來看，隨著初始標(biāo)注數(shù)據(jù)的增多，所有分類器的誤分率都呈下降趨勢，兩個數(shù)據(jù)集上誤分率隨初始標(biāo)注比例變化情況如圖3所示．

圖3 CORA和CiteSeer數(shù)據(jù)集上的分類錯誤率隨標(biāo)注數(shù)據(jù)比例的變化情況

由于SS－ICA是ICA的一種改進(jìn)，它在初始標(biāo)注數(shù)據(jù)較少的情況下使用未標(biāo)記數(shù)據(jù)更新分類器提高分類精度，當(dāng)訓(xùn)練數(shù)據(jù)充足時(shí)SS－ICA和ICA能達(dá)到同樣高的分類精度．SS－ICA和ICA的精度曲線如圖4所示．

圖4 CORA和CiteSeer數(shù)據(jù)集上分類器分類精度比較

5 結(jié)束語

面對Web上日益增多的短文本數(shù)據(jù)，人們對短文本數(shù)據(jù)的挖掘越來越重視，有效的分類短文本對獲取數(shù)據(jù)的分布特征以及后續(xù)的挖掘工作都有重要的意義．短文本長度短小，特征稀疏，訓(xùn)練數(shù)據(jù)獲得困難，導(dǎo)致傳統(tǒng)分類方法不能取得令人滿意的分類精度．

為了有效解決短文本分類問題，本文提出了基于半監(jiān)督的迭代分類算法SS－ICA，算法綜合利用了短文本內(nèi)容信息和文本的引用關(guān)系，同時(shí)借鑒半監(jiān)督學(xué)習(xí)中使用未標(biāo)記數(shù)據(jù)的思想，在迭代過程中使用未標(biāo)記數(shù)據(jù)更新修正分類器，有效提高了標(biāo)注數(shù)據(jù)稀少情況下短文本分類的精度．通過在CORA和CiteSeer數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)證明，在標(biāo)注數(shù)據(jù)稀少的情況下SS－ICA比NB和ICA有更高的分類精度．

［1] Sriram B，F(xiàn)uhry D，Demir E，et al．Short text classification in twitter to improve information filtering［C] ／／Proceedings of the 33rd annual international ACM SIGIR conference on Research and development in information retrieval．Geneva：ACM，2010：841－842．

［2] Phan H X，Nguyen L M，Horiguchi S．Learning to classify short and sparse text ＆web with hidden topics from large－scale data collections［C] ／／Proceedings of the 17th Internatinal Conference on World Wide Web．Beijing：ACM，2008：91－100．

［3] Sen P，Namata G，Bilgic M，et al．Collective classification in network data［J] ．AI Magazine（AIM），29（3）：93－106．

［4] Blum A，Mitchell T．Combining labeled and unlabeled data with cotraining［C] ／／Proceedings of the 11th Annual Conference on Computational Learning Theory Madison：ACM，1998：92－100．

［5] Neville J，Jensen D．Iterative classification in relational data［C] ／／Proceedings of the AAAI 2000Workshop Learning Statistical Models from Relational Data．Austin：AAAI press，2000：13－20．

［6] McCallum A K，Nigam K，Rennie J，et al．Automating the construction of internet portals with machine learning［J] ．Information Retrieval Journal，2000，3（2）：127－163．

［7] Giles C L，Bollacker K，Lawrence S．CiteSeer：an automatic citation indexing system［C] ／／The third ACM conference on digital libraries，1998：89－98．

［8] Hall M，F(xiàn)rank E，Holmes G，et al．The WEKA data mining software：an update［J] ．SIGKDD Explorations（SIGKDD），2009，11（1）：10－18．

［9] Knuth D E．The art of computer Programming［M] ．北京：清華大學(xué)出版社，2002：142－143．