基于無標記Web數(shù)據(jù)的層次式文本分類

何力，譚霜，賈焰，韓偉紅

(國防科學技術(shù)大學計算機學院，湖南長沙410073)

為了實現(xiàn)對互聯(lián)網(wǎng)上信息的有效管理和訪問，人們一般按照一個概念或主題類別層次對網(wǎng)絡(luò)信息進行標記和組織，以更好地搜索和訪問網(wǎng)絡(luò)資源。這些主題類別一般被組織為樹形結(jié)構(gòu)，例如雅虎目錄(Yahoo!directory)和 ODP(open directory project)。對于Web文本分類這個問題，傳統(tǒng)的有監(jiān)督方法需要標注好的語料來訓練分類器。在實際分類問題中，對于一個由專家編制的類別層次，通常并沒有標注好的語料，而Web分類目錄的規(guī)模往往比較大，通常包含數(shù)百甚至數(shù)千個類別，此時通過人工標記文檔類別來構(gòu)建語料庫將是一項非常繁重的工作。因為需要為每個類別人工標記足夠多的訓練樣本，這項工作需要耗費巨大的人力成本來完成。對此，本文試圖實現(xiàn)一個不需要有標記訓練樣本的層次式文本分類方法。

針對文本主題分類缺少訓練樣本的問題，已有工作利用外部數(shù)據(jù)源來豐富類別的特征信息[1-9]，這些方法利用類別的特征關(guān)鍵詞以及類別層次的上下文信息，到Web中獲取更多的相關(guān)數(shù)據(jù)，為分類學習產(chǎn)生訓練樣本，增加類別的分類依據(jù)。因為這一類方法在分類學習過程中不需要人工標記訓練樣本，稱為無標記數(shù)據(jù)分類方法。無標記數(shù)據(jù)分類利用Web搜索引擎和開放數(shù)據(jù)庫來獲取訓練樣本。對于Web搜索引擎，如谷歌，可以利用類別名稱以及類別的上下文信息搜索相關(guān)頁面，那么搜索結(jié)果應該和該類別具有一定相關(guān)性，體現(xiàn)了該主題類別的特征。對于開放數(shù)據(jù)庫，如維基百科、ODP等，可以利用主題類別在知識庫中搜索相關(guān)文檔，將這些文檔作為該類別的樣本。

無標記數(shù)據(jù)分類方法借助外部數(shù)據(jù)源學習分類模型，但是通過Web獲得的學習樣本可能會包含噪聲數(shù)據(jù)，從而影響分類學習效果[2，5]，這是其面臨的一個主要挑戰(zhàn)。本文針對Web搜索結(jié)果中含有噪聲數(shù)據(jù)的問題，采用以下3個手段來提高分類學習效果。

1)利用類別知識和類別層次信息構(gòu)造準確的Web查詢，采用節(jié)點的標簽路徑來產(chǎn)生查詢關(guān)鍵詞;

2)利用多數(shù)據(jù)源產(chǎn)生樣本，同時從谷歌搜索引擎、維基百科這2個數(shù)據(jù)源搜索相關(guān)頁面和文檔，以獲取更加全面的樣本數(shù)據(jù);

3)結(jié)合類別層次對樣本數(shù)據(jù)分組，為每個類別獲得更加完整的特征源，根據(jù)搜索到的樣本數(shù)據(jù)，利用主題類別層次學習分類模型，減小噪聲數(shù)據(jù)的影響。

相比已有的無標記數(shù)據(jù)分類方法，本文提出的方法通過這些手段可以獲取更加有效的樣本數(shù)據(jù)。在得到樣本數(shù)據(jù)之后，采用支持向量機分類算法訓練層次式分類模型，最后在ODP數(shù)據(jù)集上對提出的無標記數(shù)據(jù)分類方法進行實驗驗證。

1 無標記數(shù)據(jù)分類相關(guān)工作

對于有監(jiān)督學習缺少訓練樣本的問題，Weiss[10]可以將已有的解決策略概括為3類:過采樣技術(shù)[11-13]、利用外部數(shù)據(jù)生成新樣例[2-9]、采購新樣例。過采樣技術(shù)通過簡單復制已有樣本來增加訓練集，學習過程中會產(chǎn)生過擬合問題，而直接購買數(shù)據(jù)則要承擔非常高昂的代價。利用外部數(shù)據(jù)源生成新樣例則可以通過技術(shù)手段獲取比較有價值的新樣例。

在生成新樣例方面，已有工作主要是利用Web數(shù)據(jù)為主題層次中的類別產(chǎn)生新的樣本文檔，來豐富類別的特征信息[2-9]。Ha-Thuc等[2]根據(jù)類別層次為每個類別構(gòu)造一個查詢，查詢詞包括類別名稱、類別描述以及父、子節(jié)點名稱，利用Web搜索引擎獲取相關(guān)文檔，然后采用產(chǎn)生式模型對文檔建模，為每個類別建立一個語言模型，最后采用自上而下的分類方法對文檔分類。Wetzker等[3]利用類別主題名以及父類別主題名構(gòu)造查詢，采用雅虎搜索獲取每個類別的top-k相關(guān)文檔，然后為每個類別學習一個中心向量，構(gòu)造了一個支持多標簽分類的層次式分類器。Zhang等[4]利用ODP目錄的數(shù)據(jù)集學習主題分類模型，并對知識監(jiān)督學習中的預測風險進行優(yōu)化。Huang等[5]利用那些在一個類別和它祖先類別中同時出現(xiàn)的單詞構(gòu)造查詢，以谷歌搜索結(jié)果作為訓練樣本，然后采用KNN算法對文檔進行分類。這些方法利用主題目錄的類別層次信息和類別知識來構(gòu)造Web查詢。類別知識包括一個類別的主題名稱、關(guān)鍵詞、描述信息等。除了類別自身知識之外，還可以利用主題層次的結(jié)構(gòu)特征，例如類別在主題層次中的父類別、子類別、鄰居類別等信息。Wang等[6]利用維基百科知識庫構(gòu)造通用分類器，該方法首先人工為每個類別確定一組關(guān)鍵詞，然后根據(jù)這些類別關(guān)鍵詞到維基百科中獲取相關(guān)概念與文檔，最后利用這些概念與文檔訓練分類器。Hung等[7-8]提出了一種Web語料獲取方法，該方法首先為每個類別搜索少量相關(guān)度較高的Web文檔，然后從這些文檔中抽取出類別的關(guān)鍵詞，然后利用這些關(guān)鍵詞搜索更多的相關(guān)Web文檔。劉麗珍等[9]提出一種模糊劃分聚類方法，該方法對無標記樣本進行模糊劃分聚類，通過一定的相似度度量，將相關(guān)文本歸并，得到少量標記文本，從而為監(jiān)督學習找到了分類依據(jù)。

另外，Chen等[1]試圖利用外部數(shù)據(jù)源學習類別和詞匯之間的關(guān)系，即在每個類別中不同單詞的概率權(quán)重，從自然語言處理角度考慮，就是為每個類別建立一個語言模型，從而實現(xiàn)對微博短文本的主題分類。Ko等[14]采用自舉法進行機器標注樣本，根據(jù)無標記文檔集合和類別的標題詞來自動生成標記文檔，然后針對機器標注過程中的噪聲數(shù)據(jù)，采用特征投影技術(shù)訓練分類器。Veeramachaneni等[15]提出了一個層次式狄利克雷產(chǎn)生式模型，對類別層次中的語料文檔進行主題建模，通過學習每個類別中不同單詞的概率權(quán)重，實現(xiàn)了一種無監(jiān)督分類方法。

2 無標記數(shù)據(jù)的HSVM分類模型

首先利用類別知識和主題層次信息從Web數(shù)據(jù)獲取每個類別的相關(guān)文檔，然后根據(jù)這些相關(guān)文檔為主題類別層次學習分類模型。

2.1 獲取Web樣本

本文采用多種技術(shù)手段來提高樣本文檔的質(zhì)量，首先根據(jù)類別標簽路徑構(gòu)造Web查詢，然后融合多個Web數(shù)據(jù)源的搜索結(jié)果產(chǎn)生相關(guān)文檔，最后利用類別層次結(jié)構(gòu)對相關(guān)文檔進行數(shù)據(jù)分組，具體過程如圖1所示。

圖1 無標記文檔分類方法示意圖Fig.1 The classification method with no labeled data

1)構(gòu)造Web查詢

已有方法利用類別的本體知識和類別層次的上下文信息為類別構(gòu)造查詢[2-3，5]。本文利用類別在類別層次樹中的標簽路徑來構(gòu)造查詢，即以從根節(jié)點到該節(jié)點路徑上的所有類別的名稱作為查詢詞。例如，對于ODP中的類別“英語”，其標簽路徑為“科學_社會科學_語言學_語言_英語”，那么以“科學”、“社會科學”、“語言學”、“語言”、“英語”這些詞匯作為該類別的查詢詞。相比已有的這些方法，利用類別樹為每個類別生成查詢詞，更能代表一個類別的完整語義。

2)搜索相關(guān)文檔

本文同時從Web搜索引擎和開源分類目錄來獲取樣本。對于Web搜索引擎，采用谷歌從互聯(lián)網(wǎng)上搜索相關(guān)頁面。對于開源目錄，由于本文采用ODP目錄進行實驗測試，因此采用了維基百科來搜索相關(guān)文檔。通過利用多種Web數(shù)據(jù)，本文能夠獲取更多的相關(guān)文檔數(shù)據(jù)，減少噪聲數(shù)據(jù)的影響。

3)樣本抽取

在從Web數(shù)據(jù)中搜索到這些相關(guān)頁面之后，需要將其轉(zhuǎn)化為訓練樣本。對于搜索到的相關(guān)頁面，本文按照標準的文本處理過程抽取網(wǎng)頁中的文本，刪除停用詞和低頻詞，將文檔轉(zhuǎn)換為TFIDF特征向量。另外采用top-down數(shù)據(jù)分組方式，對于一個類別，首先找到類別樹中以該類別為根節(jié)點的子樹，然后將該子樹中所有節(jié)點的相關(guān)文檔作為這個類別的訓練樣本。這樣結(jié)合類別層次對數(shù)據(jù)分組，可以為每個類別獲得更加完整的特征源。

2.2 學習分類器

在從Web獲取樣本數(shù)據(jù)之后，接下來結(jié)合主題類別層次學習分類模型。本文采用層次式支持向量機(hierarchical SVMs，HSVM)學習分類模型，基于搜索到的Web樣本訓練HSVM分類器。HSVM是一個基于支持向量機的層次式分類模型，已被驗證是一個有效的層次式文本分類方法[16]。本文實現(xiàn)并比較了2種HSVM方法，分別是二元分類器的HSVM和多元分類器的HSVM。二元分類器的HSVM為類別層次樹中除根節(jié)點以外的每個節(jié)點訓練一個二元SVM分類器，對文檔進行自上而下的分類。二元分類器的HSVM如圖2(a)所示，每個虛線框表示一個二元分類器，對于一個文檔，自上而下進行分類預測，由每個節(jié)點上的本地分類器判斷文檔是否屬于當前類別。多元分類器的HSVM如圖2(b)所示，根據(jù)類別層次樹逐層為具有相同父節(jié)點的所有類別建立一個多類SVM分類器，即在類別層次樹中所有中間節(jié)點上分別訓練一個多類分類器，對文檔進行自上而下的分類。這2種HSVM均是對測試文檔進行自上而下的分類預測。

圖2 HSVM分類模型Fig.2 The classification models of HSVM

Liblinear[17]是臺灣大學林智仁教授開發(fā)的一個SVM分類器，根據(jù)林智仁小組的研究結(jié)果，Liblinear適用于具有高維特征的Web文檔分類，因此本文采用LibLinear來實現(xiàn)HSVM。

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

3.1 實驗準備

本文采用ODP簡體中文網(wǎng)站目錄作為實驗對象，ODP簡體中文網(wǎng)站目錄是一個深度為6層的類別層次樹，包括參考、商業(yè)、休閑、體育、健康、計算機、新聞、家庭、社會、游戲、藝術(shù)、購物、科學等13個大類，1 763個類別，整個目錄包括24 570個網(wǎng)站。根據(jù)ODP中的網(wǎng)站URL爬取頁面，然后對采集到的網(wǎng)頁進行解析、分詞和停用詞過濾，最終將每個網(wǎng)站表示為一個文檔。ODP數(shù)據(jù)的類別分布和文檔分布如圖3所示。

在ODP樣本集中，有1 048個類別的樣本個數(shù)不足10個，由于這些稀有類別的實例非常少，采用現(xiàn)有的機器學習方法很難對這些類別的網(wǎng)頁進行有效地自動分類。為了使有監(jiān)督分類算法能夠同本文提出的方法進行公平比較，采用父類別模型對稀有類別進行分類預測，即將文檔分到稀有類別的父類別后就不再繼續(xù)往下細分，以避免這些稀有類別對有監(jiān)督分類方法的性能影響。

圖3 數(shù)據(jù)的層次分布Fig.3 Data distribution on different level

網(wǎng)頁文檔是一種高維數(shù)據(jù)，因此需要進行特征降維以解決文本特征向量高維問題，本文采用基于詞頻逆文檔頻率值的特征詞子集選擇方法進行特征降維。對于有監(jiān)督分類方法，先將ODP數(shù)據(jù)集隨機分為10份，其中1份為測試集，其余作為訓練集，然后訓練分類器并計算各評價指標，如此反復10次，以這10次的平均值作為最終結(jié)果。對于無標記數(shù)據(jù)分類方法，本文采用Web樣本訓練分類器，然后對ODP數(shù)據(jù)集進行測試并計算各評價指標。

為了獲取更加廣泛的Web數(shù)據(jù)，同時從谷歌和維基百科搜索相關(guān)文檔。對于一個主題類別，首先利用谷歌搜索引擎搜索相關(guān)頁面，并從中抽取出相關(guān)文檔，然后同樣在維基百科中搜索該主題類別的相關(guān)文檔，補充到該類別的訓練樣本中去。最后結(jié)合所有從谷歌和維基百科獲取到的樣本訓練分類器，并將其記為GW-HSVM(Google Wikipedia based HSVM)。具體在實驗中，取谷歌搜索結(jié)果的top-50作為相關(guān)文檔，取維基百科搜索結(jié)果的top-10作為相關(guān)文檔。

對于標注樣本的有監(jiān)督分類方法，文中采用有標記的ODP數(shù)據(jù)集訓練HSVM分類器，記為S-HSVM(Supervised-HSVM)。顯然，GW-HSVM是基于Web樣本的無標記數(shù)據(jù)分類方法，S-HSVM是有監(jiān)督分類方法。

對于文本分類問題，通常采用精度precision、召回率recall、F1評價分類算法的好壞，同時根據(jù)這些指標的宏平均值和微平均值來衡量算法在所有類別上的性能。微平均評價指標體現(xiàn)了大類別對結(jié)果的影響，宏平均評價指標給每個類別以相等權(quán)重，更能體現(xiàn)算法在小類別上的性能表現(xiàn)。

本文實驗中的數(shù)據(jù)為單標簽文檔，此時precision、recall和F1的微平均值均相等，等于分類的準確率 accuracy。因此，采用 Macro-Precision，Macro-Recall，Macro-F1和 accuracy作為分類算法的評價標準。另外，層次式分類方法在自上而下的分類過程中會產(chǎn)生錯誤傳播問題，對此分析了算法在不同層級上的性能表現(xiàn)。在類別層次中，隨著深度增加，會出現(xiàn)大量的小類別，對此采用宏平均指標評價算法在各層級上的性能。具體在計算第n級的宏平均指標時，只考慮第n級上所有類別精度、召回率和F1的宏平均值。

3.2 實驗結(jié)果

在實驗中可以發(fā)現(xiàn)，二元分類器的HSVM和多元分類器的HSVM在分類準確率上性能接近，但是多元分類器的HSVM需要的訓練和預測時間要更少，這是因為多元分類器方法不需要在葉子節(jié)點上訓練分類器，如圖2(b)所示。因此，本文在實驗中采用多元分類器實現(xiàn)的HSVM。

GW-HSVM和S-HSVM對ODP中文目錄所有類別的分類性能如表1所示，包括精度、召回率、F1的宏平均值以及準確率。可以看到，GW-HSVM的分類準確率稍低于有監(jiān)督分類方法S-HSVM，但是在宏平均指標上，GW-HSVM的性能接近S-HSVM，這說明GW-HSVM能夠?qū)π☆悇e進行更為有效的分類，這是因為GW-HSVM為每個類別采集了足夠多的Web訓練文檔，而S-HSVM所采用的ODP數(shù)據(jù)集中則包含有大量的小類別。

表1 整體分類性能比較Table 1 Overall classification performance comparison

本文還比較了S-HSVM和GW-HSVM在類別樹中不同層級上的分類性能，包括Macro-P、Macro-R和Macro-F1，如圖4所示。

圖4 不同層級上的分類性能Fig.4 Performance on different level

可以看到，GW-HSVM在第1級和第4級上的性能差于S-HSVM，這是因為ODP中文目錄中這兩層上的類別包含較多的實例。對于目錄中其他幾層，由于這些層級中包含有大量稀有類別，這時GW-HSVM的分類性能接近甚至優(yōu)于S-HSVM。結(jié)合表1和圖4的實驗結(jié)果可以發(fā)現(xiàn)，本文提出的無標記數(shù)據(jù)分類方法取得了較好的分類效果，其性能接近于有標記訓練樣本的監(jiān)督分類方法。

4 結(jié)束語

本文針對主題分類目錄缺少訓練樣本的問題，提出了一種無標記數(shù)據(jù)的層次式文本分類方法，該方法利用搜索引擎從Web數(shù)據(jù)中獲取訓練樣本，通過有效的Web查詢和樣本抽取方法降低了噪聲數(shù)據(jù)的影響，獲得了較好的分類效果，其分類性能接近于有標注訓練樣本的監(jiān)督分類方法。

[1]CHEN Y，LI Z，NIE L，et al.A semi-supervised bayesian network model for microblog topic classification[C]//Proceedings of the 24th International Conference on Computational Linguistics.Mumbai，India，2012:561-576.

[2]HA-THUC V，RENDERS J M.Large-scale hierarchical text classification without labelled data[C]//Proceedings of the fourth ACM International Conference on Web Search and Data Mining.Hong Kong，China，2011:685-694.

[3]WETZKER R，ALPCAN T，BAUCKHAGE C，et al.An unsupervised hierarchical approach to document categorization[C]//Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence.Silicon Valley，USA，2007:482-486.

[4]ZHANG C，XUE G R，YU Y.Knowledge supervised text classification with no labeled documents[C]//Proceedings of the 10th Pacific Rim International Conference on Artificial Intelligence.Hanoi，Vietnam，2008:509-520.

[5]HUANG C C，CHUANG S L，CHIEN L F.Liveclassifier:creating hierarchical text classifiers through Web corpora[C]//Proceedings of the 13th International Conference on World Wide Web.New York，USA，2004:184-192.

[6]WANG P，DOMENICONI C.Towards a universal text classifier:transfer learning using encyclopedic knowledge[C]//Proceedings of the Ninth IEEE International Conference on Data Mining Workshops.Miami，USA，2009:435-440.

[7]HUNG C M，CHIEN L F.Web-based text classification in the absence of manually labeled training documents[J].Journal of the American Society for Information Science and Technology，2007，58(1):88-96.

[8]HUNG C M，CHIEN L F.Text classification using Web corpora and em algorithms[C]//Proceedings of the Asia Information Retrieval Symposium.Beijing，China，2005:12-23.

[9]劉麗珍，宋瀚濤，陸玉昌.無標記訓練樣本的Web文本分類方法[J].計算機科學，2006，33(3):200-201.LIU Lizhen，SONG Hantao，LU Yuchang.The method of Web text classification of using non-labeled training sample[J].Computer Science，2006，33(3):200-201.

[10]WEISS G M.Mining with rarity:a unifying framework[J].ACM SIGKDD Explorations Newsletter，2004，6(1):7-19.

[11]CHEN S，HE H，GARCIA E A.Ramoboost:ranked minority oversampling in boosting[J].Neural Networks，IEEE Transactions on.2010，21(10):1624-1642.

[12]NGUYEN H M，COOPER E W，KAMEI K.Borderline over-sampling for imbalanced data classification[J].International Journal of Knowledge Engineering and Soft Data Paradigms，2011，3(1):4-21.

[13]GAO M，HONG X，CHEN S，et al.A combined smote and pso based rbf classifier for two-class imbalanced problems[J].Neurocomputing，2011，74(17):3456-3466.

[14]KO Y，SEO J.Learning with unlabeled data for text categorization using bootstrapping and feature projection techniques[C]//Proceedings of the 42nd Annual Meeting on Association forComputationalLinguistics.Barcelona，Spain，2004:255-262.

[15]VEERAMACHANENI S，SONA D，AVESANI P.Hierarchical dirichlet model for document classification[C]//Proceedings of the 22nd International Conference on Machine Learning.Bonn，Germany，2005:928-935.

[16]CAI L，HOFMANN T.Hierarchical document categorization with support vector machines[C]//Proceedings of the thirteenth ACM International Conference on Information and Knowledge Management.Washington，DC， USA，2004:78-87.

[17]FAN R E，CHANG K W，HSIEH C J，et al.Liblinear:a library for large linear classification[J].Journal of Machine Learning Research，2008，9:1871-1874.