基于半監(jiān)督學習的短文本分類方法

孫學琛，高志強，全志斌，施嘉鴻

（東南大學計算機科學與工程學院，江蘇南京211189）

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

1 問題描述

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

2 相關(guān)研究

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

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

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

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

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

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

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

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

3．2 算法描述

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

圖2 SS－ICA算法流程圖

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

2）使用X作為訓練集訓練分類器f．

3）對Y中的每個實例Yi：使用f進行分類，yi←f（ai）．

4）使用X∩Y作為訓練集更新分類器f．

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

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

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

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

4 實驗結(jié)果與分析

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

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

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

表2 各分類器在不同標注比例訓練集上的性能

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

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

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

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

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

5 結(jié)束語

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

為了有效解決短文本分類問題，本文提出了基于半監(jiān)督的迭代分類算法SS－ICA，算法綜合利用了短文本內(nèi)容信息和文本的引用關(guān)系，同時借鑒半監(jiān)督學習中使用未標記數(shù)據(jù)的思想，在迭代過程中使用未標記數(shù)據(jù)更新修正分類器，有效提高了標注數(shù)據(jù)稀少情況下短文本分類的精度．通過在CORA和CiteSeer數(shù)據(jù)集進行實驗證明，在標注數(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] ．北京：清華大學出版社，2002：142－143．