文本分類與聚類(textcategorizationandclustering)概述廣義的分類(classification或者categorization)有兩種含義：一種含義是有領(lǐng)導(dǎo)的學(xué)習(xí)(supervisedlearning)過程，另一種是無領(lǐng)導(dǎo)的學(xué)習(xí)(unsupervisedlearning)過程。通常前者稱為分類，后者稱為聚類(clustering)，后文中提到的分類都是指有指點的學(xué)習(xí)過程。給定分類系統(tǒng)，將文本集中的每個文本分到某個或者某幾個類別中，這個過程稱為文本分類(textcategorization)。將文本聚集分組成多個類或簇，使得在同一個簇中的文本內(nèi)容具有較高的相似度，而不同簇中的文本內(nèi)容差異較大，這個過程稱為文本聚類(textclustering)0文本分類2.1文本分類的步驟典范的文本分類進程可以分為三個步驟：文本表現(xiàn)(TextRepresentation)這一過程的目標是把文本表示成分類器能夠處理的情形。最常用的方法是向量空間模型，即把文本集表示成詞一文檔矩陣，矩陣中每個元素代表了一個詞在相應(yīng)文檔中的權(quán)重。選取哪些詞來代表一個文本，這個過程稱為特點選擇。常見的特征選擇方法有文檔頻率、信息增益、互信息、期看交叉熵等等。為了減少分類過程中的計算量，經(jīng)常還需要進行降維處理，比如LSI。分類器構(gòu)建(ClassifierConstruction)這一步驟的目標是選擇或設(shè)計構(gòu)建分類器的方法。沒有一種通用的方法可以實用所有情形。不同的方法有各自的優(yōu)缺點和實用條件，要依據(jù)問題的特色來選擇一個分類器。后面專門講述常用的方法。選定方法之后，在訓(xùn)練集上為每個種別構(gòu)建分類器，然后把分類器利用于測試集上，得到分類結(jié)果。后果評估(ClassifierEvaluation)在分類過程完成之后，需要對分類后果進行評估。評估過程運用于測試集(而不是訓(xùn)練集)上的文本分類結(jié)果，常用的評估尺度由IR范疇繼續(xù)而來，包括查全率、查準率、F1值等等。對于某一類別i，查全率ri=li/ni，其中ni為所有測試文檔中，屬于第i類的文檔個數(shù)；li是經(jīng)分類系統(tǒng)輸出分類結(jié)果為第i類且結(jié)果準確的文檔個數(shù)。查準率pi=li/mi，其中mi是經(jīng)分類體系輸出分類結(jié)果為第i類的文檔個數(shù)，li是經(jīng)分類系統(tǒng)輸出分類結(jié)果為第i類且結(jié)果準確的文檔個數(shù)。F1值為查全率和查準率的協(xié)調(diào)均勻數(shù)，即：。相對于最簡略的練習(xí)集一測試集評估辦法而言，還有一種稱為k-foldcrossvalidation的方式，即把所有標志的數(shù)據(jù)劃分成k個子集，對于每個子集，把這個子集當作訓(xùn)練集，把其余子集作為測試集；這樣履行k次，取各次評估成果的均勻值作為最后的評估結(jié)果。2.2常見的文本分類方法Rocchio方法每一類斷定一個中心點(centroid)，計算待分類的文檔與各類代表元間的間隔，并作為判定是否屬于該類的判據(jù)。Rocchio方法最早由［Hull,1994］引進文本分類范疇，后來又有很多文章進行了改良。Rocchio方法的特點是輕易實現(xiàn)，效力高。缺點是受文本集分布的影響，比如計算出的中心點可能落在相應(yīng)的類別之外［Sebastiani,2002］。樸實貝葉斯(naivebayes)方式將概率論模型利用于文檔主動分類，是一種簡略有效的分類方法。應(yīng)用貝葉斯公式，通過先驗概率和類別的條件概率來估量文檔對某一類別的后驗概率，以此實現(xiàn)對此文檔所屬類別的斷定。［Lewis,1998］介紹了樸實貝葉斯方法的發(fā)展和各種變體及特點。K近鄰(K-NearestNeightbers,KNN)辦法從訓(xùn)練集中找出與待分類文檔最近的k個鄰居(文檔)，根據(jù)這k個鄰居的類別來決議待分類文檔的類別。KNN方法的長處是不需要特征選取和訓(xùn)練，很輕易處理類別數(shù)目多的情形，缺陷之一是空間復(fù)雜度高。KNN方法得到的分類器是非線性分類器。此方法最早由［Yang&Chute,1994］提出。支撐向量機(SVM)方法對于某個類別，找出一個分類面，使得這個種別的正例和反例落在這個分類面的兩側(cè)，而且這個分類面滿足：到最近的正例和反例的間隔相等，而且是所有分類面中與正例(或反例)距離最大的一個分類面。SVM方法最早由［Joachims,1998］引進到文本分類中。SVM方法的長處是應(yīng)用很少的練習(xí)集，計算量小；毛病是太依附于分類面鄰近的正例和反例的地位，具有較大的偏執(zhí)。其他常用的方法還包含決策樹方法和神經(jīng)網(wǎng)絡(luò)方法，詳見文獻［Sebastiani,2002］。2.3常用源碼和數(shù)據(jù)集Weka是一個開源的機器學(xué)習(xí)軟件，集成了數(shù)據(jù)預(yù)處置、機器學(xué)習(xí)算法、可視化功效，實現(xiàn)了大部分常見的機器學(xué)習(xí)算法，包含分類。Weka是國外有名教材《DataMining:PracticalMachineLearningToolsandTechniques(SecondEdition)》所采取的試驗平臺。與Weka相競爭的另一個開源的機器學(xué)習(xí)軟件是Yale，自稱實現(xiàn)了Weka的所有算法，兼容Weka的數(shù)據(jù)格局?，F(xiàn)在已經(jīng)商業(yè)化。與Weka和Yale不同，Bow是專門為文本處理設(shè)計的開源包。Bow包括三個部分：Rainbow(文本分類)、Arrow(文本檢索)和Crossbow(文本聚類)。文本分類常用的數(shù)據(jù)集有REUTERS,20NEWSGROUP,OHSUMED等語料庫。3.文本聚類文本聚類有很多運用，比如進步IR系統(tǒng)的查全率，導(dǎo)航/組織電子資源，等等。是一個成熟的文本聚類體系。依據(jù)聚成的簇的特色，聚類技術(shù)通常分為層次聚類(hierarchicalclustering)和劃分聚類(partitionalclustering)0前者比擬典范的例子是凝集層次聚類算法，后者的典范例子是k-means算法。近年來呈現(xiàn)了一些新的聚類算法，它們基于不同的理論或技巧，比如圖論，含混集理論，神經(jīng)網(wǎng)絡(luò)以及核技術(shù)(kerneltechniques)等等。3.1文本聚類的步驟與文本分類相似，文本聚類過程可以分為3個步驟：文本表現(xiàn)(TextRepresentation)把文檔表現(xiàn)成聚類算法可以處置的情勢。所采取的技巧請參見文本分類部分。聚類算法選擇或設(shè)計(ClusteringAlgorithms)算法的選擇，往往需要考慮相似度計算方法。在文本發(fā)掘中，最常用的相似度計算方法是余弦相似度。聚類算法有很多種，但是沒有一個通用的算法可以解決所有的聚類問題。因此，須要認真研討要解決的問題的特色，以選擇適合的算法。后面會有對各種文本聚類算法的內(nèi)容。聚類評估(ClusteringEvaluation)由于沒有訓(xùn)練文檔聚集，所以評測聚類后果是比較艱苦的。常用的方法是：選擇人工已經(jīng)分好類或者做好標志的文檔聚集作為測試集合，聚類停止后，將聚類結(jié)果與已有的人工分類結(jié)果進行比較。常用評測指標也是查全率、查準率及F1值。3.2常見的文本聚類算法層次聚類方法層次聚類可以分為兩種：凝集(agglomerative)層次聚類和劃分(divisive)層次聚類。凝集方法把每個文本作為一個初始簇，經(jīng)過不斷的合并進程，最后成為一個簇。劃分方法的進程正好與之相反。劃分方法在現(xiàn)實中采用較少，有關(guān)闡述請見［Kaufman&Rousseeuw,1990］。層次聚類可以得到層次化的聚類成果，但是計算復(fù)雜度高，不能處置大批的文檔。近年來呈現(xiàn)了新的層次聚類算法，包含CURE［Guha,Rastogi&Shim,1998］,ROCK［Guha,Rastogi&Shim,2000］,Chameleon［Karypis,Han&V.Kumar,1999］和BIRCH［Zhang,Ramakrishnan&Livny,1996］。劃分方法k-means算法是最常見的劃分方法。給定簇的個數(shù)k，隨機選定k個文本作為k個初始簇，然后遍歷剩下的所有文檔，分別計算與這k個文檔的相似度(如量化為距離)。將其他的文本加入到最近的簇中，并更新簇的中心點，然后再根據(jù)新的中心點對文本重新劃分；當簇不再變更時或經(jīng)過一定次數(shù)的迭代之后，算法結(jié)束。k-means算法復(fù)雜度低，而且輕易實現(xiàn)，但是對例外和噪聲文本比較敏感。另外一個問題是，沒有一個好的措施斷定k的取值。相干文獻參見［Forgy,1965］［Xu&Wunsch,2005］?；诿芏鹊霓k法為了發(fā)現(xiàn)任意形狀的非均勻分布的聚類，提出了基于密度的方法。這類方法將簇看作是數(shù)據(jù)空間中被低密度區(qū)域分割開的高密度區(qū)域。常見的基于密度的方法有DBSCAN,OPTICS,DENCLUE等等，參考文獻見［Han&Kamber,2006］。神經(jīng)網(wǎng)絡(luò)方式神經(jīng)網(wǎng)絡(luò)方法將每個簇描寫為一個標本，標本作為聚類的'原型”，不必定對應(yīng)一個特定的數(shù)據(jù)依據(jù)某些間隔度量，新的對象被分配到與其最類似的簇中。比較有名的神經(jīng)網(wǎng)絡(luò)聚類算法有：競爭學(xué)習(xí)(competitivelearing)和自組織特點映射(self-organizingmap)［Kohonen,1990］。神經(jīng)網(wǎng)絡(luò)的聚類方法須要較長的處理時間和龐大的數(shù)據(jù)龐雜性，所以不實用于大型數(shù)據(jù)的聚類。其他常見的方法包括基于圖論的聚類算法［Jain&Dubes,1988］、基于核的聚類算法［muller,Mika,R?tsch,et.al,2001］、混合聚類算法［Hoppner,Klawonn&Kruse,1999］，等等。3.3常用的源碼包和數(shù)據(jù)集前面提到的Weka、Yale、Bow這三個工具已經(jīng)包括了常用的聚類算法，下面再介紹幾個專門的聚類軟件：Scipy:/Theopensourceclusteringsoftwares:http://bonsai.ims.u-tokyo.ac.jp/~mdehoon/software/cluster/software.htmMICMOD:http://www-math.univ-fcomte.fr/mixmod/index.phpTheSemanticIndexingProject:/JUNG:/CompLearn