《網(wǎng)絡(luò)信息檢索》課件第11章

第11章信息分類與聚類11.1基本知識

第11章.ppt

11.3聚類方法

11.4分類方法

11.5方法評測

11.6小結(jié)

思考題

11.1基本知識

信息分類是指將對象分到類別集合中去的過程。如果類別集合是事先給定，對訓(xùn)練集中的對象給出類別標(biāo)識，則稱為有監(jiān)督的分類(通常所說的分類)。如果類別不是事先給定，而是在操作過程中生成，則稱為無監(jiān)督的分類(通常稱為聚類)。

無論是聚類還是分類，都涉及“類”的概念。如何認(rèn)識和定義“類”的概念，如何對類的特征進行描述，是信息自動處理的首要問題。11.1.1類的概念

在信息聚類和分類中，類是一個核心概念。如何認(rèn)識類，定義類，描述類等是聚類和分類的基礎(chǔ)。只有認(rèn)識了什么是類，了解了如何抽取描述類的特征，才能熟悉信息聚類與分類的本質(zhì)所在。

直觀而言，類是相似物體的集合。我們通常談及“車”，其實可以看成是談及“車”這樣一個類?！败嚒鳖惪赡馨ㄆ?、自行車、摩托車和火車等元素?！败嚒鳖愔械倪@些元素都有一些共同的特征，都有輪子，都可以移動等。除了相似性之外，“車”類的各元素之間也有不同的地方，比如輪子數(shù)目的不同，動力源的差異等。

信息聚類和分類的目的就是根據(jù)各個元素的一個特征信息，應(yīng)用機器學(xué)習(xí)的方法[1]，將這些元素劃分到不同的類中。11.1.2對象特征描述

對象的形式化表示是一個基本的，而又非常重要的問題。首先要將對象從無結(jié)構(gòu)的原始形式轉(zhuǎn)化為計算機能夠理解的結(jié)構(gòu)化形式，然后才能進行分析與處理。常見的對象表示模型有向量空間模型、概率模型和語言模型等。其中最常用的是向量空間模型(VSM)。

向量空間模型以特征項作為對象表示的基本單位，特征項可以由字、詞、短語、顏色、紋理等組成。每一個對象Oi被看成是由特征項組成的n維特征空間的一個向量Wi，Wi=(t1，wi1;t2，wi2;…;tj，wij)，其中wij為第j個特征項tj在對象Oi中的權(quán)重。

類通常具有質(zhì)量、直徑等性質(zhì)，設(shè)類S有n個對象，這n個對象的特征抽象成n個向量W1，W2，…，Wn，則：

1．類的質(zhì)心

類的質(zhì)心為該類所有對象的平均向量，即(11-1)

2．類的直徑通?？梢杂妙愔袑ο箝g的最大距離，或者類中各元素到類的質(zhì)心距離的歐氏距離平方和作為類的直徑。即(11-2)或者(11-3)式(11-3)將類直徑定義為各元素的離差平方和的總和，簡稱離差平方和。11.1.3文檔相似性

許多分類方法基于對象之間的二元關(guān)系來分類。對象之間的二元關(guān)系，通常有“相似性”、“相關(guān)系數(shù)”、“差異性”和“距離”等多種表達方式。確定文檔的相似性是對文檔進行分類的基礎(chǔ)。對于有m個特征屬性的對象而言，其總體特征可以看成一個m維向量，也可以看成是m維空間中的一個點，向量的第i個分量大小對應(yīng)著第i個屬性的權(quán)重。設(shè)Oi與Oj為兩個對象，s(Oi，Oj)為Oi與Oj之間的相似性，s(Oi，Oj)應(yīng)該滿足：

(1)非負(fù)性。對于任何i、j，恒有s(Oi，Oj)≥0。

(2)對于任何i、j，恒有s(Oi，Oj)≤1。

(3)對稱性。對于任何i、j，恒有s(Oi，Oj)=s(Oj，Oi)。

在檢索技術(shù)的研究過程中，研究者們提出了眾多的相似性度量方式，其中最常用的有以下5種，如表11-1所示。設(shè)Wi，Wj為兩個向量，wi，k與wjk分別為其第k個分量。通常使用距離來衡量兩個對象之間的相異度。兩個文檔之間的差異性系數(shù)越接近1，則表明這兩個文檔之間的距離越大。設(shè)d(Oi，Oj)為對象Oi與Oj之間的距離。常用的距離度量方法有以下幾種。

明考斯基距離(Minkowskidistance)：(11-4)當(dāng)q分別取1、2和∞時，明考斯基距離分別對應(yīng)于曼哈坦距離(Manhattandistance)、歐幾里德距離(Euclideandistance)和切比雪夫距離(Chebyishevdistance)。曼哈坦距離，也叫做絕對值距離：(11-5)歐幾里德距離，也叫做歐氏距離：(11-6)切比雪夫距離：(11-7)其他的距離函數(shù)包括蘭氏距離(Lancedistance)、馬氏距離(Mahalanobisdistance)和斜交距離(Obliquedistance)等。一般地，這些距離函數(shù)都有如下特性：●非負(fù)性：d(Oi，Oj)≥0●自相似性：d(Oi，Oi)=0●對稱性：d(Oi，Oj)=d(Oj，Oi)●三角不等式：d(Oi，Oj)≤d(Oi，Ok)+d(Ok，Oj)

三角不等式的物理意義表現(xiàn)在：對于歐幾里德空間(EuclideanSpace)，一個三角形的任意兩邊長度之和總是大于第三條邊的長度。

在文本自動分類和處理的過程中，最基本的就是要得到文檔之間相似系數(shù)或者距離。設(shè)共有N個文檔，則任意兩文檔之間的二元關(guān)系可以構(gòu)成一個N×N的關(guān)系矩陣MN×N。此關(guān)系矩陣全面地反映了文檔之間的相似程度及其差異性，這是對文檔進行分類和聚類的基礎(chǔ)。由于相似系數(shù)和距離都滿足對稱性，故此關(guān)系矩陣是一個對稱矩陣，即MN×N=MTN×N。

【例11-1】

設(shè)有兩對象所對應(yīng)的總體特征分別是O1=〈1，3，5〉，O2=〈2，3，1〉。查詢q的總體特征為

q=〈1，1，0〉。求q與O1，O2之間的夾角余弦相似性以及歐幾里德距離。根據(jù)這些度量，q與O1，O2中的哪個對象更相似？

解：計算查詢與兩對象之間的余弦夾角相似性：

計算查詢與兩對象之間的歐幾里德距離：由于s(q，O1)<s(q，O2)，d(q，O1)>d(q，O2)，從而可知q與O2更為相似。11.1.4類間距離

在文檔分類和聚類的過程中，通常用類間距離來衡量不同類之間的相似性和差異性。與文檔距離一樣，類間距離同樣有多種度量方式。設(shè)Si、Sj為兩個類，常用的類間距離度量方式有最小距離法(Single-linkage)、最大距離法(Complete-linkage)、類平均距離法(Averagelinkage)、質(zhì)心法(Centroid

hierarchical)和離差平方和法(Ward’smethod)。

1．最小距離法(11-8)因為在實際中很少出現(xiàn)極小異常值，使用最小距離法可以避免極大值的影響。

2．最大距離法(11-9)利用不同類的元素之間的最長距離作為類間距離。在一些應(yīng)用中，為避免異常的極大值扭曲分類和聚類結(jié)果，需要刪除這些異常值之后再進行處理。3．類平均距離法(11-10)利用類間所有樣本點的平均距離作為類間距離。該法利用了所有樣本的信息，是一種較為常用的類間距離度量方式。

4．質(zhì)心法

設(shè)兩個類Si，Sj的質(zhì)心分別為

，，利用類的質(zhì)心之間的距離作為類間距離：

(11-11)

這種度量方式對異常值不敏感，結(jié)果比較穩(wěn)定。

5．離差平方和法

用式(11-3)的類直徑的定義得到兩個類Si,Sj分別為,

，合并后新類為Si+j的直徑為，則可以定義類間距離的平方為(11-12)類間距離即為總類Si+j的離差平方和減去各子類的離差平方和。這種度量方式對異常值很敏感；對較大的類傾向產(chǎn)生較大的距離，從而不易合并，較符合實際需要。

11.2特征描述及提取

在前面描述文檔的相似性時提到，對于有m個特征屬性的文檔而言，其總體特征可以看成一個m維向量，也可以看成是m維空間中的一個點。在本節(jié)中，將描述如何從待分類的元素中提取總體特征，以及如何選擇合適的特征，進行信息的分類和聚類。11.2.1特征提取

基于VSM模型的文本表示常用TF-IDF算法計算特征項的權(quán)重。這里回顧一下TF-IDF算法：

TF：詞頻(TermFrequency)，向量空間模型中特征項termi在文檔dj中出現(xiàn)的次數(shù)，記作tfi，j。tfi，j越高，意味著ti對文檔dj越重要。比如，在一篇描寫計算機應(yīng)用的文檔中，“計算機”、“電腦”出現(xiàn)的頻率比較大，TF值比較高。TF還可以通過文檔中的最大詞頻進行規(guī)范化。

DF：文檔頻率(DocumentFrequency)，文檔集中含有特征項ti的文檔個數(shù)，記作dfi。dfi越高，意味著termi在衡量文檔之間差異性方面的作用越低。比如，在漢語中，“的”、“我”這種詞的DF值一定比較高；在英語中，“if”、“is”等詞的DF值也很高，這些詞對于區(qū)分文檔的意義不大。DF

可以通過文檔總數(shù)進行規(guī)范化。

IDF：逆文檔頻率(InverseDocumentFrequency)，與dfi形成反比關(guān)系。常用的IDF形式有idfi=1/dfi、idfi=lg(D/dfi)等。idfi越高，意味著ti在衡量文檔之間差異性方面的作用越大。

TF-IDF：同時考慮標(biāo)引項在所在文本中的分布情況以及在全部文本集合中的分布情況。TF-IDF值的計算公式可參見第2章公式(2-4)。11.2.2特征選擇

實現(xiàn)文本自動分類的基本困難之一是特征項空間的維數(shù)過高。所謂“特征項”，在中文文本中主要指分詞處理后得到的詞匯，而特征項的維數(shù)則對應(yīng)不同詞匯的個數(shù)。數(shù)量過大的特征項一方面導(dǎo)致分類算法的代價過高，另一方面導(dǎo)致無法準(zhǔn)確地提取文檔的類別信息，造成分類效果不佳。因此，需要在不犧牲分類質(zhì)量的前提下盡可能地降低特征項空間的維數(shù)?！疤卣鬟x取”的任務(wù)就是要將信息量小、“不重要”的詞匯從特征項空間中刪除，從而減少特征項的個數(shù)，它是文本自動分類系統(tǒng)中的一個關(guān)鍵步驟。

常用的特征選擇算法有文檔頻率、信息增益(InformationGain，IG)、互信息量(MutualInformation，MI)以及卡方檢驗(χ2test，CHI)，以下對這4種方法作簡單的介紹。

1．文檔頻率

DF表示在訓(xùn)練集中包含某個特征項t的文檔數(shù)。這種衡量特征項重要程度的方法基于這樣一個假設(shè)：DF較小的特征項對分類結(jié)果的影響較小。這種方法優(yōu)先取DF較大的特征項，而DF較小的特征項將被剔除。DF是最簡單的特征項選取方法，而且該方法的計算復(fù)雜度低，能夠勝任大規(guī)模的分類任務(wù)。但這種策略不符合被廣泛接受的信息檢索理論：高頻詞沒有低頻詞對文檔特征貢獻大。

2．信息增益

IG通過統(tǒng)計某個特征項在一篇文檔中出現(xiàn)或不出現(xiàn)的次數(shù)來預(yù)測文檔的類別。IG的計算公式如下所示。(11-13)式中：Pr(ci)表示一篇文檔屬于類別的概率；Pr(t)表示特征項t在一篇文檔內(nèi)出現(xiàn)的概率；Pr(

)表示特征項t不在一篇文檔內(nèi)出現(xiàn)的概率；Pr(ci|t)表示特征項t在屬于類別的文檔內(nèi)出現(xiàn)的概率；Pr(ci|

)表示特征項t不在屬于類別的文檔內(nèi)出現(xiàn)的概率；m是文檔類別數(shù)。G(t)值大則被選取的可能性大，即特征項按照G值排序。

3．互信息

MI使用公式(11-14)計算某個特征項和類別之間的相關(guān)性[2]。(11-14)式中：A為t和c同時出現(xiàn)的次數(shù)；B為t出現(xiàn)而c沒有出現(xiàn)的次數(shù)；C為c出現(xiàn)而t沒有出現(xiàn)的次數(shù)；N為所有文檔數(shù)。如果t和c不相關(guān)，則I(t，c)值為0。如果有m個類，于是對于每個t會有m個值，取它們的平均，就可得到特征選取所需的一個線性序。大的I平均值的特征被選取的可能性大。

4．χ2檢驗

使用MI衡量特征項的重要程度時，只考慮到了正相關(guān)對特征項重要程度的影響。如果特征項t和類別反相關(guān)，就說明含有特征項t的文檔不屬于的概率要大一些，這對于判斷一篇文檔是否不屬于類別c也是很有指導(dǎo)意義的。為克服這個缺陷，χ2使用公式計算特征項t和類別c的相關(guān)性：(11-15)式中：A為t和c同時出現(xiàn)的次數(shù)；B為t出現(xiàn)而c沒有出現(xiàn)的次數(shù)；C為c出現(xiàn)而t沒有出現(xiàn)的次數(shù)；D為t和c同時沒有出現(xiàn)的次數(shù)；N為訓(xùn)練集中的文檔數(shù)。與MI類似，如果t和c不相關(guān)，則χ2(t，c)值為0。與MI相同，如果有m個類，每個t就會有m個值，取它們的平均，就可得到特征選取所需的一個線性序。大的χ2平均值的特征被選取的可能性大。

【例11-2】

表11-2顯示了幾個特征詞在不同文檔類出現(xiàn)的次數(shù)，試計算χ2(財務(wù)，C1)。解：總共有80個文檔。計算特征值“財務(wù)”在類別C1和非C1(記為)中的分布：則有：χ2(財務(wù)，C1)=

11.3聚類方法

所謂聚類，就是完全根據(jù)元素之間的相關(guān)性，將所有元素聚集成若干個類，使得屬于同一類的元素之間盡可能相似，屬于不同類的元素之間差別顯著。由于事先沒有關(guān)于這些元素信息的分類知識和類別信息，所以文本聚類可以看成是一種“無監(jiān)督學(xué)習(xí)”(unsupervisionlearning)，文本聚類的特點是“先有元素后有類”，完全根據(jù)元素的信息來進行分類。

事實上，信息聚類的方法起源于數(shù)據(jù)分析和數(shù)據(jù)挖掘[3]的研究。聚類分析的目的是把一個給定的數(shù)據(jù)對象集合分成不同的簇(cluster)。簇是相似數(shù)據(jù)對象的集合，在同一個類中，對象之間具有相似性；不同類的對象之間是相異的。11.3.1劃分聚類法

較流行的劃分聚類方法(partitionalalgorithms)有動態(tài)聚類法(也稱逐步聚類法)，如k-均值(k-means)算法、k-中心點算法。其基本思想為：

隨機選擇k個對象，每個對象初始地代表一個類的平均值或中心，對剩余每個對象，根據(jù)其到類中心的距離，被劃分到最近的類；然后重新計算每個類的平均值。不斷重復(fù)這個過程，直到所有的樣本都不能再分配為止。

k-均值聚類法是一種常用的劃分聚類法，它利用類的質(zhì)心之間的距離作為類間距離。

下面以一個實際例子，來說明k-均值聚類法的過程。

【例11-3】

在(X，Y)平面有表11-3給出的點，試對它們進行聚類。解：在此例中，每個對象都有2個特征，分別表示在X軸和Y軸上。

第一步：k=3，隨機選取3個類的中心，分別用k1、k2、k3表示，如圖11-1所示。

為了將點指派到最近的中心，通?？梢杂脷W幾里得距離表示歐氏空間中的點，用余弦值表示文檔間距離，用公式(11-1)計算類中心。

第二步：對于所有對象，根據(jù)其到k1、k2、k3之間的距離，劃分到相應(yīng)的類中。然后重新計算每個類的質(zhì)心。此時的k1、k2、k3與第一步中的值已經(jīng)不同了，如圖11-2所示。圖11-1各類的中心點圖11-2各類的質(zhì)心第三步：此為第一次聚類后的情況，如圖11-3所示。圖11-3第一次聚類結(jié)果第四步：對于所有對象，根據(jù)其到k1、k2、k3之間的距離，繼續(xù)劃分到相應(yīng)的類中。然后重新計算每個類的質(zhì)心，如圖11-4所示。

第五步：重復(fù)“分類”→“計算新的質(zhì)心”→“分類”→“計算新的質(zhì)心”這樣的過程，直到分類情況不再變化為止。以下為最終的聚類情況，如圖11-5所示。圖11-4重新計算各類的質(zhì)心圖11-5最終聚類結(jié)果總之，劃分聚類法的特點為：k需要事先定好；創(chuàng)建一個初始劃分，再采用迭代的重定位技術(shù)；不必確定距離矩陣；時間復(fù)雜度為O(n)，比層次聚類法運算量要小，適用于處理龐大的樣本數(shù)據(jù)；適用于發(fā)現(xiàn)球狀類。劃分聚類法的缺陷是：不同的初始值，結(jié)果可能不同；有些k-均值算法的結(jié)果與數(shù)據(jù)輸入順序有關(guān)，如在線k-均值算法；用爬山法(hill-climbing)來尋找最優(yōu)解，容易陷入局部極小值。11.3.2層次聚類法

層次聚類法(hierarchicalmethod)也稱為系統(tǒng)聚類法，它對給定的數(shù)據(jù)進行層次的分解。層次聚類法又可分為凝聚的(agglomerative，bottom-up)的方法與分裂的(divisive，top-down)方法。

凝聚的方法一開始將每個對象單獨地看做一類，然后根據(jù)同類相近，異類相異的原則，合并類，直到所有的類并成一個，或達到一個終止條件為止。

分裂的方法一開始將所有的對象置于一類，在迭代的每一步中，一個類不斷地分為更小的類，直到每個對象在單獨的一個類中，或達到一個終止條件。設(shè)共有N個元素需要聚類，計算所有元素兩兩間的距離，共有C2N個，MN×N為元素之間的距離矩陣。顯然，MN×N為一個對稱矩陣，且MN×N的所有對角元素均為0。層次聚類法的基本流程如下：

(1)把每個元素當(dāng)成一個類，則初始時，系統(tǒng)一共存在N個類，每個類中只含有一個元素，這些類的類間距離等于其包含的元素之間的距離。

(2)找到最接近(距離最小)的兩個類，將這兩個類合并為一個類，現(xiàn)在系統(tǒng)中類的總數(shù)目將減少1。

(3)計算合并成的新類與其他舊類之間的距離。

(4)重復(fù)步驟(2)與(3)，直到所有的元素都合并成為了一個類。由此過程可見，每次合并都將使得系統(tǒng)中類的數(shù)目減少1，經(jīng)過N-1次合并，則原來的N個元素就聚合成為一類了，聚類過程也就結(jié)束了。在聚類的過程中，將會產(chǎn)生一個層次結(jié)構(gòu)的樹狀圖，這也是層次聚類法這個名字的由來。步驟(3)中的類間距離有多種計算方式，如最小距離、最大距離、重心距離、類平均距離等，關(guān)于類間距離的詳細(xì)介紹請參見11.1.4節(jié)。層次聚類法的特點為：

(1)類的個數(shù)不需事先定好；

(2)聚類的效果較好；

(3)需確定距離矩陣；

(4)時間復(fù)雜度至少是O(N2)，運算量較大，擴展性不佳，適用于處理小樣本數(shù)據(jù)。11.3.3其他聚類方法

除了劃分聚類法和層次聚類法之外，還有一些其他的聚類方法。這些聚類方法有其自身的特點，可以根據(jù)需要獨立運用于信息聚類中，也可以用來補充劃分聚類法和層次聚類法的不足。比如，基于距離的方法比較適合發(fā)現(xiàn)聚集球狀類，基于密度的方法(density-basedmethod)可以用來識別任意形狀的類。在基于密度的方法中，只要臨近區(qū)域的密度超過一定的閾值，就繼續(xù)聚類，所以這種方法可以過濾噪聲和孤立點(outlier)，發(fā)現(xiàn)任意形狀的類?；诰W(wǎng)格的方法(grid-basedmethod)把樣本空間量化為有限數(shù)目的單元，形成一個網(wǎng)絡(luò)結(jié)構(gòu)，聚類操作都在這個網(wǎng)格結(jié)構(gòu)(即量化空間)上進行。基于模型的方法(model-basedmethod)為每個類假定一個模型，尋找數(shù)據(jù)對給定模型的最佳擬合。

在此不詳述這些聚類方法，有興趣者可以參閱相關(guān)書籍。

11.4分類方法

與聚類不同的是，分類之前，已經(jīng)有分類知識和類別信息。在很多分類的應(yīng)用中，已經(jīng)知道了目標(biāo)數(shù)據(jù)需要分成哪些類。

文本分類是指在給定分類體系下，根據(jù)文本內(nèi)容自動確定文本類別的過程。文本分類的過程一般包括特征提取、特征選擇、分類判決的過程，如圖11-6所示。圖11-6自動分類的一般過程在整個文本分類過程中，分類算法是文本分類的核心。目前文本分類的算法有很多種，包括樸素貝葉斯算法(NaveBayes)、k近鄰法(kNN)、決策樹算法、決策規(guī)則算法、回歸模型、Rocchio算法、神經(jīng)網(wǎng)絡(luò)算法(NN)、支撐矢量機(SVM)、線性最小二乘方估計(LLSF)和分類器集成方法等，總體來說，分類算法大致可歸結(jié)為兩大類：參數(shù)類型和非參數(shù)類型。

參數(shù)類型的分類方法使用訓(xùn)練數(shù)據(jù)集估計各參數(shù)，然后利用估計的參數(shù)值進行分類判斷。樸素貝葉斯算法是典型的參數(shù)類型分類法。非參數(shù)類型的分類法還可以分為兩類：基于示例和基于樣本?；谑纠姆椒ㄊ菑拿總€類別的訓(xùn)練集中抽取或建立一個示例作為該類別的代表，示例用加權(quán)特征詞組成的特征向量來表示。若共有N個類別，則建立N個特征矢量作為各個類別的示例，未知類別的文檔通過與各個類別示例相比較來進行分類，Rocchio方法屬于該類方法。而基于樣本的方法將未知類別的文檔看做是對于訓(xùn)練集的一個查詢，它從訓(xùn)練集合中得到多個已知類別樣本，這些樣本的類別作為未知文本的候選樣本。k近鄰法就是一種基于樣本的方法。

下面介紹幾種常用的分類方法。11.4.1NaveBayes算法

樸素貝葉斯(NaIveBayes，NB)算法是機器學(xué)習(xí)領(lǐng)域中最常見的一種基于概率的算法。它建立在類條件獨立的樸素假設(shè)之上，即假設(shè)文本中的各個特征項屬于特定類別的概率相互獨立。該算法計算待分類實例屬于各個類別的后驗概率，取后驗概率最大的類別作為所屬類別。

假設(shè)存在一些類別：{C1，C2，…，Cn}，E是一個實例的特征描述，現(xiàn)在要判斷該實例屬于哪個類別，即求P(Ci|E)。根據(jù)貝葉斯定理，有··(11-16)假設(shè)各類是獨立的，，則有(11-17)需要知道先驗概率P(Ci)和條件概率P(E|Ci)，才能計算后驗概率P(Ci|E)。P(Ci)可以從數(shù)據(jù)中估計得來，假設(shè)在樣本空間D中，類別Ci中有ni個樣本，總的樣本數(shù)是|D|，則可以估計P(Ci)為(11-18)再假設(shè)實例是由一系列獨立的特征來表述的，關(guān)于給定類別的條件概率也是獨立的：(此處最好準(zhǔn)確重述一下，這個條件獨立性假設(shè)即樸素貝葉斯假設(shè)。其最大作用在于NB假設(shè)下計算聯(lián)合分布時簡單可行。)(11-19)

【例11-4】

根據(jù)統(tǒng)計，天氣情況和幾種特征有如表11-4所示的關(guān)系。假定當(dāng)前天氣特征為有烏云，刮大風(fēng)，沒有閃電，試估計當(dāng)前的天氣情況。解：當(dāng)前特征：E={烏云，大風(fēng)，閃電}P(E)=0.0089+0.01+0.019=0.0379因此，P(晴天|E)=0.23，P(雨天|E)=0.26，P(陰天|E)=0.50。按樸素貝葉斯方法判斷，當(dāng)前最可能的天氣情況為陰天。將樸素貝葉斯應(yīng)用于文本分類。需要假設(shè)文本中的各個特征項屬于特定類別的概率相互獨立。該算法計算文本屬于各個類別的后驗概率，取后驗概率最大的類別作為文本類別。假設(shè)文本d屬于類別Cj的后驗概率為P(Cj|d)，可以由公式(11-20)計算。(11-20)由于P(d)代表文檔d的先驗概率，對所有類別為常數(shù)，則有式中：P(Cj)代表訓(xùn)練集中類別Cj的先驗概率；P(d|Cj)代表假設(shè)為類別Cj時觀察到d的概率；P(tk|Cj)代表類別Cj中特征tk出現(xiàn)的頻率；N(tk，d)代表在文檔d中特征tk出現(xiàn)的次數(shù)。各概率計算公式如下：(11-21)(11-22)(11-23)式中：|Dj|代表類別Cj中的訓(xùn)練文檔數(shù);|D|代表所有的訓(xùn)練文檔數(shù);N(tk，di)代表在訓(xùn)練文檔di中特征tk出現(xiàn)的次數(shù);|V|代表所有的特征數(shù)目。式(11-23)中，分子表示類別Cj中特征tk出現(xiàn)的次數(shù)，分母表示類別Cj中所有特征出現(xiàn)的總次數(shù)，并對分子和分母進行了平滑處理，避免出現(xiàn)零概率。在訓(xùn)練時，先對訓(xùn)練數(shù)據(jù)根據(jù)公式(11-22)和(11-23)計算各個類別的P(Cj)和P(tk|Cj)。當(dāng)待分類文本d到達時，再根據(jù)公式(11-21)計算出該文本的類別。

理論上講，貝葉斯分類具有最小的出錯率。然而，實踐中并非總是如此，這是由于對其應(yīng)用的假定(如類條件獨立性和特征獨立性)的不準(zhǔn)確性所造成的。

樸素貝葉斯算法描述如下：訓(xùn)練：

V是文檔D里面的所有詞匯，對于每一個分類Cj∈C

假設(shè)Di是文檔D的一個子集，屬于類Cj

P(Ci)=|Di|/|D|

Ti是所有文檔Di串接而成的總文檔，ni是Ti中詞匯出現(xiàn)的總數(shù)

對于每一詞wj∈V，nij是詞wj在Ti中的出現(xiàn)的次數(shù)

P(wj|Ci)=(nij+1|Ci)/(ni+|V|)

測試：

已知一個測試集X

N是X中詞匯出現(xiàn)的次數(shù)，得到分類為

其中，αj是測試集X中第j個位置出現(xiàn)的詞。

【例11-5】

有如表11-5所示的訓(xùn)練集和測試集，請問測試集中的文檔D5應(yīng)該歸屬于哪一類？解：用樸素貝葉斯算法，先計算“Yes”和“No”兩個類的先驗概率：測試集包含的詞匯V={Chinese，Japan，Tokyo}，對這幾個詞項計算關(guān)于兩個類別的條件概率：對文檔D5，計算關(guān)于每個類別的后驗概率：因此文檔D5屬于類別Yes。11.4.2kNN算法

kNN法是基于樣本(Instance-Based)的算法，該算法首先對訓(xùn)練集文本進行向量化，得到各文本的特征向量。當(dāng)待分類文本到達后，進行向量化，得到特征向量，然后計算該向量與每個訓(xùn)練文本向量的距離，找到與該文本相似度最近的k個文本。在這k個文本中，哪個類別的文本數(shù)最多，待分類文本就屬于哪個類別。相似度的計算公式如下：(11-24)

kNN算法可由圖11-7形象地表示。圖11-7kNN分類假設(shè)有兩個類別，k值取5，當(dāng)一個未知文檔d1到達時，計算該文檔與每個訓(xùn)練文檔的相似度，得到最近的5個訓(xùn)練文檔，4個屬于類別A，1個屬于類別B，則文檔d1判為類別A。同理，文檔d2判為類別B。

如果考慮相似度的量化值，可以改進kNN算法的判別方法。計算文檔關(guān)于類別的權(quán)重：(11-25)這里，x是一個新的點，Cj是已知類別，di是x的k個最近的鄰居點，sim(x，di)是x和di的相似度。而I(di，Cj)為類別屬性函數(shù)，即如果di屬于類Cj，那么函數(shù)值為1，否則為0。

比較類的權(quán)重，將文本分到權(quán)重最大的那個類別中。

kNN法的缺點就是k值不好確定，傳統(tǒng)上要進行一系列實驗來比較不同k值所產(chǎn)生的結(jié)果，從而得到最優(yōu)的k值。并且大量的計算在分類時進行，當(dāng)訓(xùn)練文本集很大時，會導(dǎo)致分類耗時較多。(11-26)

kNN的算法描述如下：

1．根據(jù)特征項集合重新描述訓(xùn)練文本向量。

2．在新文本到達后，根據(jù)特征詞分詞新文本，確定新文本的向量表示。

3．在訓(xùn)練文本集中選出與新文本最相似的k個文本，計算公式為(11-24)。

其中，k值的確定目前沒有很好的方法，一般采用先定一個初始值，然后根據(jù)實驗測試的結(jié)果調(diào)整k值，一般初始值定為幾百到幾千之間(并非定論，可以不提此句)。

4．在新文本的k個鄰居中，依次計算每類的權(quán)重，計算公式為(11-25)。

5．比較類的權(quán)重，將文本分到權(quán)重最大的那個類別中。

【例11-6】

假定通過計算某文檔與訓(xùn)練集文檔的相似度，得出表11-6(k=10)。11.4.3Rocchio算法

Rocchio算法是一種典型的基于示例的算法。它首先為每個類別建立一個代表矢量，當(dāng)一個待分類文檔到達后，計算該文檔矢量和類別代表矢量的距離，取距離最小的類別作為文檔所屬類別[4]。

Rocchio分類器是基于向量空間模型和最小距離的方法。此方法起初應(yīng)用于信息檢索系統(tǒng)中，后來最早由Hull在1994年應(yīng)用于分類[5],此后，Rocchio方法就在分類中廣泛應(yīng)用起來。

Rocchio計算公式為(11-27)式中：wic為類C中心向量的權(quán)重；β為訓(xùn)練樣本中正例的控制參數(shù)；γ為訓(xùn)練樣本中反例的控制參數(shù)；nC為訓(xùn)練樣本中類別C的正例數(shù)目；n為訓(xùn)練樣本的文檔數(shù)；β和γ是兩個控制參數(shù)，可以通過提高β，降低γ來削弱反例的影響。當(dāng)β＝1，γ＝0時，wic為正例的質(zhì)心。

文檔di與類別C的距離度量公式為(11-28)假定有n個文檔類別記為{C1，C2，…，Cn}，訓(xùn)練過程的算法描述如下：循環(huán)：i從1到n，令pi=<0，0，…，0>(初始化原型向量)

對每一個訓(xùn)練樣本<x，C(x)>∈D

令d是文檔x的歸一化TF-IDF權(quán)重矢量

i=j(Cj=C(x))

(某類文檔向量之和形成原型向量pi)

pi=pi+d給定測試文檔x，分類過程的算法描述如下：

令d是文檔x的歸一化TF-IDF權(quán)重矢量

m=－2(初始化最大的余弦相似度)

循環(huán)：i從1到n，

(計算與原型向量的相似度)

s=cos(sim(d，pi))

如果s>m，令：

m=s

r=Ci(更新最相似的類原型向量)

返回類別r

【例11-7】已知訓(xùn)練集的文檔向量如表11-7所示。請區(qū)分測試集dnew(0，0.005，0.15，0.1)屬于哪類文檔？解：經(jīng)計算，C1的原型向量

p1=(0.06，0.2，0，0.2)

C2的原型向量

p2=(0.001，0.001，0.38，0.5)

相似度：

s1=0.4027，s2=0.9448

故文檔dnew屬于C2類。11.4.4SVM算法

支撐向量機(SupportVectorMachines，SVM)是Vapnik為了解決兩層模式識別問題于1995年提出來的[6]。SVM基于結(jié)構(gòu)風(fēng)險最小化(StructuralRiskMinimization)原理，這個方法定義在一個矢量平面上，問題就是找到一個決定平面可以最優(yōu)地把數(shù)據(jù)點分割成兩類。為了定義“最優(yōu)”分割，需要引入“間隔”(Margin)的概念。圖11-8解釋了這個想法。為了簡便，圖中只顯示了在二維空間上線性分割數(shù)據(jù)點，但是這種思想可以推廣到多維空間，并且對數(shù)據(jù)點可以不是線性分割。在一個線性分割空間中的分割平面是一個超平面，每組平行線間的距離叫做“間隔”。SVM的難點就是在訓(xùn)練集中找到分割平面σi，并且最大化間隔。圖11-8SVM分類由SVM決定的線性分割空間的決定平面是一個超平面(Hyper-plane)，這個超平面可以表示如下：

w·x－b=0

(11-29)

x是訓(xùn)練集中一個任意的數(shù)據(jù)點，矢量w和常數(shù)b是需要從訓(xùn)練集中學(xué)習(xí)的數(shù)據(jù)。用Tr={(xi，yi)}表示訓(xùn)練集，yi∈{±1}是對xi的分類(對于給定類別，＋1代表正例，－1代表負(fù)例)，SVM的任務(wù)就是找到滿足以下約束條件的w和b：

w·xi－b≥+1foryi=+1

(11-30)

w·xi－b≤－1foryi=－1

(11-31)

并且矢量使w的范數(shù)平方為最小。對線性可分?jǐn)?shù)據(jù)集而言，SVM的一個有趣的特性是分割平面僅由來自決定平面的等于距離1/‖w‖的數(shù)據(jù)點(圖11-8中帶框的點)決定。這些點叫做支撐向量(SupportingVector)，是訓(xùn)練集中唯一有效的元素。如果除掉所有的其他點，算法具有同樣的分類功能。這個特性使得SVM在理論上是獨特的，和其他方法都不同，如kNN、LLSF、NN和NB都是使用訓(xùn)練集中的所有數(shù)據(jù)點來優(yōu)化分類功能。

【例11-8】

圖11-9所示三個訓(xùn)練點坐標(biāo)分別為(1，1)、(2，0)和(2，3)，分屬兩個類別，求兩個類別的決定平面及最大間隔。圖11-9訓(xùn)練點分布圖解：具有最大邊緣的權(quán)重向量平行于兩個類的最短連接線，即(1，1)和(2，3)的連線，決定平面必定垂直于這條線，并與之相交于(1.5，2)，所以，SVM的決定平面是

y=x1+2x2－5.5

用代數(shù)方法求解，標(biāo)準(zhǔn)的約束是式子(11-28)和(11-29)，并且矢量w范數(shù)平方為最小，這僅當(dāng)兩個支撐向量滿足約束時才可能。矢量w平行于(1，1)和(2，3)的連線，可以設(shè)為w=(a，2a)，所以有解得：最大間隔為

SVM的求解實際上是一個優(yōu)化問題，因此可以引入拉格朗日乘子(Lagrangemultiplier)αi來求解。分類函數(shù)表示為(11-32)當(dāng)指定數(shù)值表達式的值為正或負(fù)時，sign函數(shù)分別返回1或－1，+1表示屬于一個類別，－1表示屬于另一個類別。

SVM算法的計算過程如下：給定訓(xùn)練樣本S=(x1，x2，…，xl)

初始化，α←0，b←0，R←

‖xi‖

重復(fù)以下循環(huán)直至沒有任何誤差

循環(huán)：i從1到l

如果yi(

αjyj〈xj·xi〉+b)≤0，則

αi=αi+1

b=b+yiR2

返回(α，b)，得到H(x)對于線性不可分的情況，可以把樣本X

映射到一個高維特征空間H，并在此空間中運用原空間的函數(shù)來實現(xiàn)內(nèi)積運算，這樣將非線性問題轉(zhuǎn)換成另一空間的線性問題。(最好明確一下核函數(shù)定義和作用)常用的內(nèi)積核函數(shù)有下面三種。

(1)多項式函數(shù)：(11-33)這樣得到的是p階多項式分類器。

(2)徑向基函數(shù)(RadialBasisFunction，RBF)，也稱高斯核函數(shù)：(11-34)

(3)Sigmoid函數(shù)：(11-35)這里，k是增益，Θ是閾值。

【例11-9】

使用SVM解決XOR分類問題，XOR值域及其分布如圖11-10所示。解：使用多項式核函數(shù)K(x1，x2)=(1+x1x2)2進行變換，也就是可以表示為表11-8給出了變換后的輸入輸出關(guān)系，變換后的函數(shù)圖像如圖11-11所示。圖11-10XOR值域及其分布圖11-11變換后的函數(shù)圖像變換后在高維空間的XOR值域分布如圖11-12所示，很顯然這是線性可分的。圖11-12高維空間中的XOR值域分布

11.5方法評測

11.5.1聚類方法評測

一個好的聚類方法要能產(chǎn)生高質(zhì)量的聚類結(jié)果——簇，這些簇要具備以下兩個特點：

(1)高的簇內(nèi)相似性。

(2)低的簇間相似性。

聚類結(jié)果的好壞取決于該聚類方法采用的相似性評估方法以及該方法的具體實現(xiàn)；聚類方法的好壞還取決于該方法是能發(fā)現(xiàn)某些還是所有的隱含模式。

一個聚類方法應(yīng)該滿足以下特點：

(1)時間和空間上的可擴展性；

(2)能夠處理不同類型的屬性；

(3)能發(fā)現(xiàn)任意形狀的簇；

(4)在決定輸入?yún)?shù)的時候，盡量不需要特定的領(lǐng)域知識；

(5)能夠處理噪聲和異常；

(6)對輸入數(shù)據(jù)對象的順序不敏感；

(7)能處理高維數(shù)據(jù)；

(8)能產(chǎn)生一個好的、能滿足用戶指定約束的聚類結(jié)果；

(9)結(jié)果是可解釋的、可理解的和可用的。由于聚類是一種無監(jiān)督的學(xué)習(xí)方法，事先沒有訓(xùn)練集，也不能事先確定聚成的類會是什么樣的，所以評測聚類的效果是比較困難的。聚類本身就是一個較為主觀的過程，很多時候多種聚類結(jié)果都同樣合理。目前有的做法采用分類測試集來測試聚類的效果，即把已經(jīng)分好類的測試集打亂，再利用聚類方法進行聚類，把聚類出來的結(jié)果與分好類的測試集進行比較，用來衡量聚類的效果。下面介紹兩個用于評估的指標(biāo)。

1.純度(purity)

聚類評估即評測其發(fā)現(xiàn)隱含模式或潛在類別的能力。假設(shè)有J個已經(jīng)標(biāo)注好的類C={c1,c2，…，cJ}，聚類算法產(chǎn)生K個簇Ω={ω1，ω2，…，ωK}，則聚類純度指標(biāo)定義為(11-36)

這里N是要聚類的文檔數(shù)。

2.Rand指標(biāo)(RandIndex)

把聚類看成是做一系列決定的過程，即對集合中N(N-1)/2對文檔做決定的過程，可能的決定種類有：

TP(truepositive):將兩個相似的文檔放到同一個簇的決定;

TN(truenegative):將兩個不相似的文檔放到不同簇的決定;

FP(falsepositive):將兩個不相似的文檔放到同一簇的決定;

FN(falsenegative):將兩個相似的文檔放到不同簇的決定。

定義Rand指標(biāo)值為(11-37)

【例11-10】

對三個類別的數(shù)據(jù)，用某聚類方法得到的聚類結(jié)果如圖11-13所示。圖11-13聚類結(jié)果解：該聚類方法的純度指標(biāo)值為該聚類方法的RI指標(biāo)值為11.5.2分類方法評測

在信息檢索領(lǐng)域，通常采用查準(zhǔn)率(Precision)和查全率(Recall)作為評價測度。在分類研究領(lǐng)域，人們通常也借鑒這些標(biāo)準(zhǔn)來評價分類系統(tǒng)的優(yōu)劣。

在信息檢索系統(tǒng)中，查準(zhǔn)率表示在所有被檢索出的文檔結(jié)果集中，真正符合檢索意圖的文檔所占的比率，它體現(xiàn)了系統(tǒng)檢索結(jié)果的準(zhǔn)確程度。查全率表示被檢索出的文檔集結(jié)果中真正符合檢索意圖的文檔數(shù)在所有符合檢索意圖的文檔集中所占的比率，它體現(xiàn)了系統(tǒng)檢索所有相關(guān)文檔的完備性。在分類系統(tǒng)中，查準(zhǔn)率是指被分類的正確文檔數(shù)與所有被分類的文檔數(shù)的比率，反映了分類的準(zhǔn)確程度，也稱準(zhǔn)確率，查全率是指被分類的正確文檔數(shù)與實際類別包含的文檔數(shù)的比率，反映了分類結(jié)果與實際類別的吻合程度。查準(zhǔn)率和查全率這兩個標(biāo)準(zhǔn)是互補的，單純提高查準(zhǔn)率就會導(dǎo)致查全率的降低，反之亦然。因此，盡管一個好的分類器應(yīng)該同時具有較高的查準(zhǔn)率和較高的查全率，但是實際的檢索分類器需要在兩者之間做出一些折中，而避免其中一個指標(biāo)過低。

為了反映查準(zhǔn)率和查全率的綜合效果，可用F測度：(11-38)比較常用的是F1(β=1)值。對多個類別的分類器，為了評價分類器的整體效果，需要對每個分類器的結(jié)果進行平均。采用的平均方法有兩種：宏平均(Macroaveraging)：對每個類分別求評測值，然后平均。這種平均方法將大類小類同等看待。

微平均(Microaveraging)：將所有文檔一塊兒計算，求評測值。這種平均方法使得評測結(jié)果易受大類的影響。

對測度F1根據(jù)不同的平均方法可以得到微平均F1和宏平均F1。

【例11-11】一個分類方法對兩個類的分類結(jié)果分別如表11-9和表11-10所示，求該分類方法的宏平均和微平均查準(zhǔn)率。解：宏平均查準(zhǔn)率：微平均查準(zhǔn)率：分類評測時要注意訓(xùn)練集合和測試集合是不同的集合，即用訓(xùn)練集合訓(xùn)練，用測試集合測試。常用的測試方法稱為N重交叉檢驗(Nfoldcross-validation)，即將已標(biāo)注好的標(biāo)準(zhǔn)數(shù)據(jù)集分成N份，用其中N－1訓(xùn)練分類器，預(yù)留一份用于測試，對測試N次的結(jié)果求平均。分類評測中用到的標(biāo)準(zhǔn)數(shù)據(jù)集也稱分類評測語料庫(corpus)，目前國際常用的測試語料庫是Reuters-21578數(shù)據(jù)集，該測試集經(jīng)路透社人工收集和分類而成，包含路透社1987年的21578篇新聞稿；其中9603個訓(xùn)練文檔，3299個測試文檔，118個類別。其他常用的語料庫還包括包含從270余種醫(yī)學(xué)雜志上搜集的23萬篇文檔的摘要的Ohsumed數(shù)據(jù)集，包含平均分布在20個類中的2萬篇新聞文章的Newsgroup數(shù)據(jù)集，以及包含分布在20個類別中的9833個測試文檔及9804個訓(xùn)練文檔的復(fù)旦大學(xué)中文文本分類語料庫。11.5.3顯著性檢驗

雖然分類方法已有很多的研究，但是由于發(fā)表的結(jié)果之間很難直接對比，所以這些方法的比較很難有清晰明確的結(jié)論。例如很難說神經(jīng)網(wǎng)絡(luò)方法(NNet)比SVM方法性能好還是壞。這是因為測試中使用了不同的語料集，并且沒有進行不同數(shù)據(jù)集對分類結(jié)果影響方面的分析。樸素貝葉斯方法在某些研究中性能表現(xiàn)得相對比較差，但是其他一些研究中卻被宣稱為表現(xiàn)得出乎意料地好。這是因為在實驗中要么使用了不一樣的性能指標(biāo)，要么只使用了基準(zhǔn)(Benchmark)語料的一些子集。而且上述說法也非常含糊，“出乎意料地好”其實有很多的理解，例如可以理解成這個方法在統(tǒng)計意義顯著地比其他方法好，或者說和最好的那些方法相比實際上在統(tǒng)計上并沒有什么不同，或者說比那些最好的方法差一些但是比作者預(yù)料的要好。如果上述某種理解成立的話，又有什么實驗證據(jù)可以證明。這些都是我們需要解決的問題。因此有必要引入顯著性檢驗(SignificanceTests)，來比較兩個系統(tǒng)的不同性能指標(biāo)是否有顯著的差別。

考慮比較兩個系統(tǒng)A和B。假設(shè)系統(tǒng)A在測試集合上的正確率是pa，系統(tǒng)B的正確率是pb，兩個測試集合分別包含na和nb個實驗樣本(trial)。注意到實驗樣本的定義在不同情形下是不同的：

(1)對于微平均的查全率(Micro-avgRecall)，N＝A+C。

(2)對于微平均的