source: http://blog./?uid-103964-action-viewspace-itemid-346301
1. 概述
廣義的分類（classification或者categorization）有兩種含義：一種含義是有領(lǐng)導(dǎo)的學(xué)習(xí)
（supervised learning）過程，另一種是無領(lǐng)導(dǎo)的學(xué)習(xí)（unsupervised
learning）過程。通常前者稱為分類，后者稱為聚類（clustering），后文中提到的分類都是指有指點(diǎn)的學(xué)習(xí)過程。
給
定分類系統(tǒng)，將文本集中的每個(gè)文本分到某個(gè)或者某幾個(gè)類別中，這個(gè)過程稱為文本分類（text
categorization）。將文本聚集分組成多個(gè)類或簇，使得在同一個(gè)簇中的文本內(nèi)容具有較高的相似度，而不同簇中的文本內(nèi)容差異較大，這個(gè)過程稱
為文本聚類（text clustering）。
[Berry, 2003]具體描寫了文本發(fā)掘技巧。[Sebastiani, 2002]供給了對文本分類的綜述。[Xu & Wunsch, 2005]對聚類算法做了全面的描寫，[He, 1999]則重點(diǎn)講述了聚類算法在IR中的利用。
2. 文本分類
文本分類過程可以分為手工分類和主動分類。前者最著名的實(shí)例是yahoo的網(wǎng)頁分類系統(tǒng)，是由專家定義了分類系統(tǒng)，然后人工將網(wǎng)頁分類。這種方法須要大批人
力，現(xiàn)實(shí)中已經(jīng)采用的很少了。自動文本分類（automatic text
categorization）算法大致可以分為兩類：知識工程（knowledge engineering）方法和機(jī)器學(xué)習(xí)（machine
learning）方法。知識工程方法指的是由專家為每個(gè)類別定義一些規(guī)矩，這些規(guī)矩代表了這個(gè)類別的特點(diǎn)，主動把符合規(guī)矩的文檔劃分到相應(yīng)的種別中。這
方面最有名的體系是CONSTRUE。上個(gè)世紀(jì)90年代之后，機(jī)器學(xué)習(xí)方法成為主導(dǎo)。機(jī)器學(xué)習(xí)方法與知識工程方法相比，能夠到達(dá)類似的準(zhǔn)確度，但是減少了
大批的人工參與。我們下面重要介紹基于機(jī)器學(xué)習(xí)方法的文本分類。
2.1 文天分類的步驟
典范的文本分類進(jìn)程可以分為三個(gè)步驟：
1. 文本表現(xiàn)（Text Representation）
這
一過程的目標(biāo)是把文本表示成分類器能夠處理的情勢。最常用的方法是向量空間模型，即把文本集表示成詞－文檔矩陣，矩陣中每個(gè)元素代表了一個(gè)詞在相應(yīng)文檔中
的權(quán)重。選取哪些詞來代表一個(gè)文本，這個(gè)過程稱為特點(diǎn)選擇。常見的特征選擇方法有文檔頻率、信息增益、互信息、期看交叉熵等等，[Yang &
Pedersen , 1997 ]對這幾種方法做了比較。為了下降分類過程中的計(jì)算量，經(jīng)常還需要進(jìn)行降維處理，比如LSI。
2. 分類器構(gòu)建（Classifier Construction）
這
一步驟的目標(biāo)是選擇或設(shè)計(jì)構(gòu)建分類器的方法。沒有一種通用的方法可以實(shí)用所有情形。不同的方法有各自的優(yōu)毛病和實(shí)用條件，要依據(jù)問題的特色來選擇一個(gè)分類
器。我們會在后面專門講述常用的方法。選定方法之后，在訓(xùn)練集上為每個(gè)種別構(gòu)建分類器，然后把分類器利用于測試集上，得到分類結(jié)果。
3. 后果評估（Classifier Evaluation）
在
分類過程完成之后，需要對分類后果進(jìn)行評估。評估過程運(yùn)用于測試集（而不是訓(xùn)練集）上的文本分類結(jié)果，常用的評估尺度由IR范疇繼續(xù)而來，包括查全率、查
準(zhǔn)率、F1值等等。對于某一類別i，查全率ri=li/ni，其中ni為所有測試文檔中，屬于第i類的文檔個(gè)數(shù)；li是經(jīng)分類系統(tǒng)輸出分類結(jié)果為第i類且
結(jié)果準(zhǔn)確的文檔個(gè)數(shù)。查準(zhǔn)率pi=li/mi，其中mi是經(jīng)分類體系輸出分類結(jié)果為第i類的文檔個(gè)數(shù)，li是經(jīng)分類系統(tǒng)輸出分類結(jié)果為第i類且結(jié)果準(zhǔn)確的
文檔個(gè)數(shù)。F1值為查全率和查準(zhǔn)率的協(xié)調(diào)均勻數(shù)，即：。
相對于最簡略的練習(xí)集－測試集評估辦法而言，還有一種稱為k-fold cross
validation的方式，即把所有標(biāo)志的數(shù)據(jù)劃分成k個(gè)子集，對于每個(gè)子集，把這個(gè)子集當(dāng)作訓(xùn)練集，把其余子集作為測試集；這樣履行k次，取各次評估
成果的均勻值作為最后的評估結(jié)果。
2.2 常見的文天職類方法
1. Rocchio方法
每一類斷定一個(gè)中心點(diǎn)（centroid），計(jì)算待分類的文檔與各類代表元間的間隔，并作為判定是否屬于該類的判據(jù)。Rocchio方法最早由[Hull, 1994]引進(jìn)文本分類范疇，后來又有很多文章進(jìn)行了改良。Rocchio方法的特點(diǎn)是輕易實(shí)現(xiàn)，效力高。毛病是受文本集散布的影響，比如計(jì)算出的中心點(diǎn)可能落在相應(yīng)的類別之外[Sebastiani, 2002]。
2. 樸實(shí)貝葉斯（naive bayes）方式
將概率論模型利用于文檔主動分類，是一種簡略有效的分類方法。應(yīng)用貝葉斯公式，通過先驗(yàn)概率和類別的條件概率來估量文檔對某一類別的后驗(yàn)概率，以此實(shí)現(xiàn)對此文檔所屬類別的斷定。[Lewis, 1998]介紹了樸實(shí)貝葉斯方法的發(fā)展和各種變體及特點(diǎn)。
3. K近鄰(K-Nearest Neightbers, KNN)辦法
從
訓(xùn)練集中找出與待分類文檔最近的k個(gè)鄰居（文檔），根據(jù)這k個(gè)鄰居的類別來決議待分類文檔的類別。KNN方法的長處是不需要特征選取和訓(xùn)練，很輕易處理類
別數(shù)目多的情形，缺陷之一是空間復(fù)雜度高。KNN方法得到的分類器是非線性分類器。此方法最早由[Yang & Chute,
1994]提出。
4. 支撐向量機(jī)（SVM）方法
對于某個(gè)類別，找出一個(gè)分類面，使得這個(gè)種別的正例和反例落在這個(gè)分類面的兩側(cè)，
而且這個(gè)分類面滿足：到最近的正例和反例的間隔相等，而且是所有分類面中與正例（或反例）距離最大的一個(gè)分類面。SVM方法最早由[Joachims,
1998]引進(jìn)到文本分類中。SVM方法的長處是應(yīng)用很少的練習(xí)集，盤算量小；毛病是太依附于分類面鄰近的正例和反例的地位，具有較大的偏執(zhí)。
其他常用的方法還包含決策樹方法和神經(jīng)網(wǎng)絡(luò)方法，詳見文獻(xiàn)[Sebastiani, 2002]。
2.3
常用源碼和數(shù)據(jù)集Weka是一個(gè)開源的機(jī)器學(xué)習(xí)軟件，集成了數(shù)據(jù)預(yù)處置、機(jī)器學(xué)習(xí)算法、可視化功效，實(shí)現(xiàn)了大部分常見的機(jī)器學(xué)習(xí)算法，包含分類。Weka
是國外有名教材《Data Mining: Practical Machine Learning Tools and Techniques
(Second Edition)》所采取的試驗(yàn)平臺。
與Weka相競爭的另一個(gè)開源的機(jī)器學(xué)習(xí)軟件是Yale，自稱實(shí)現(xiàn)了Weka的所有算法，兼容Weka的數(shù)據(jù)格局。現(xiàn)在已經(jīng)貿(mào)易化。
與Weka和Yale不同，Bow是專門為文本處理設(shè)計(jì)的開源包。Bow包括三個(gè)部分：Rainbow（文本分類）、Arrow（文本檢索）和Crossbow（文本聚類）。
文本分類常用的數(shù)據(jù)集有REUTERS,20NEWSGROUP,OHSUMED等語料庫。
3. 文本聚類
文本聚類有很多運(yùn)用，比如進(jìn)步IR系統(tǒng)的查全率，導(dǎo)航/組織電子資源，等等。www.vivisimo.com是一個(gè)成熟的文本聚類體系。
依
據(jù)聚成的簇的特色，聚類技術(shù)通常分為層次聚類（hierarchical clustering）和劃分聚類（partitional
clustering）。前者比擬典范的例子是凝集層次聚類算法，后者的典范例子是k-means算法。近年來呈現(xiàn)了一些新的聚類算法，它們基于不同的理
論或技巧，比如圖論，含混集理論，神經(jīng)網(wǎng)絡(luò)以及核技術(shù)（kernel techniques）等等。
3.1 文本聚類的步驟與文本分類相似，文本聚類過程可以分為3個(gè)步驟：
1. 文本表現(xiàn)（Text Representation）
把文檔表現(xiàn)成聚類算法可以處置的情勢。所采取的技巧請參見文天職類部分。
2. 聚類算法選擇或設(shè)計(jì)（Clustering Algorithms）
算法的選擇，往往隨同著類似度盤算方法的選擇。在文本發(fā)掘中，最常用的相似度計(jì)算方法是余弦相似度。聚類算法有很多種，但是沒有一個(gè)通用的算法可以解決所有的聚類問題。因此，須要認(rèn)真研討要解決的問題的特色，以選擇適合的算法。后面會有對各種文本聚類算法的先容。
3. 聚類評估（Clustering Evaluation）
由于沒有訓(xùn)練文檔聚集，所以評測聚類后果是比較艱苦的。 常用的方法是： 選擇人工已經(jīng)分好類或者做好標(biāo)志的文檔聚集作為測試集合，聚類停止后，將聚類結(jié)果與已有的人工分類結(jié)果進(jìn)行比較。常用評測指標(biāo)也是查全率、查準(zhǔn)率及F1值。
3.2 常見的文本聚類算法
1．層次聚類方法
層
次聚類可以分為兩種：凝集（agglomerative）層次聚類和劃分（divisive）層次聚類。凝集方法把每個(gè)文本作為一個(gè)初始簇，經(jīng)過不斷的合
并進(jìn)程，最后成為一個(gè)簇。劃分方法的進(jìn)程正好與之相反。劃分方法在現(xiàn)實(shí)中采用較少，有關(guān)闡述請見[Kaufman & Rousseeuw,
1990]。層次聚類可以得到層次化的聚類成果，但是盤算龐雜度比擬高，不能處置大批的文檔。近年來呈現(xiàn)了新的層次聚類算法，包含CURE[Guha,
Rastogi & Shim, 1998], ROCK[Guha, Rastogi & Shim, 2000],
Chameleon[Karypis, Han & V. Kumar, 1999]和BIRCH[Zhang, Ramakrishnan
& Livny, 1996]。
2．劃分方法
k-means算法是最常見的劃分方法。給定簇的個(gè)數(shù)k，選定k個(gè)文本分辨作
為k個(gè)初始簇，將其他的文本參加最近的簇中，并更新簇的中心點(diǎn)，然后再根據(jù)新的中心點(diǎn)對文本重新劃分；當(dāng)簇不再變更時(shí)或經(jīng)過必定次數(shù)的迭代之后，算法結(jié)
束。k-means算法復(fù)雜度低，而且輕易實(shí)現(xiàn)，但是對例外和噪聲文本比較敏感。另外一個(gè)問題是，沒有一個(gè)好的措施斷定k的取值。相干文獻(xiàn)參見
[Forgy, 1965][Xu & Wunsch, 2005]。
3．基于密度的辦法
為了發(fā)明任意外形的聚類成果，提出了基于密度的方法。這類方法將簇看作是數(shù)據(jù)空間中被低密度區(qū)域分割開的高密度區(qū)域。常見的基于密度的方法有DBSCAN,OPTICS, DENCLUE等等，參考文獻(xiàn)見[Han & Kamber, 2006]。
4．神經(jīng)網(wǎng)絡(luò)方式
神
經(jīng)網(wǎng)絡(luò)方法將每個(gè)簇描寫為一個(gè)標(biāo)本，標(biāo)本作為聚類的"原型"，不必定對應(yīng)一個(gè)特定的數(shù)據(jù),依據(jù)某些間隔度量，新的對象被分配到與其最類似的簇中。比擬有名
的神經(jīng)網(wǎng)絡(luò)聚類算法有:競爭學(xué)習(xí)（competitive learing）和自組織特點(diǎn)映射（self-organizing
map）[Kohonen, 1990]。神經(jīng)網(wǎng)絡(luò)的聚類方法須要較長的處理時(shí)光和龐雜的數(shù)據(jù)龐雜性，所以不實(shí)用于大型數(shù)據(jù)的聚類。
其他常見
的方法包括基于圖論的聚類算法[Jain & Dubes, 1988]、基于核的聚類算法[müller, Mika, R?tsch,
et. al, 2001]、含混聚類算法[H?ppner, Klawonn & Kruse, 1999]，等等。
3.3 常用的源碼包和數(shù)據(jù)集前面先容的Weka、Yale、Bow這三個(gè)工具已經(jīng)包括了常用的聚類算法，下面再介紹幾個(gè)專門的聚類軟件：
Scipy: http://www./
The open source clustering softwares: http://bonsai.ims./~mdehoon/software/cluster/software.htm
MICMOD: http://www-math./mixmod/index.php
The Semantic Indexing Project: http://www./
JUNG: http://jung./
CompLearn: http:///
目前還沒有專門為文本聚類設(shè)計(jì)的數(shù)據(jù)集，一般可以采取文本分類的數(shù)據(jù)集（前面有先容）。
闡明：本文轉(zhuǎn)載自網(wǎng)絡(luò)http://fusion./wiki/pages/viewpage.action?pageId=1033
練習(xí)數(shù)據(jù)集匯總網(wǎng)址
http://kdd.ics./summary.data.type.html（直接分類下載）
http://jeffdai./logs/37909800.html（分類鏈接）
|
