文本分類與聚類課件

1、文本分類與聚類這一部分將講述文本分類及聚類的概念文本特征的提取方法貝葉斯分類，KNN分類及決策樹分類K均值及層次聚類的方法文本分類概述概述文本分類包括普通文本分類和網(wǎng)頁文本分類中文網(wǎng)頁分類技術已經(jīng)成為中文信息處理領域的一項基礎性工作網(wǎng)頁分類可以為搜索引擎用戶提供目錄導航服務，進而提高系統(tǒng)查準率網(wǎng)頁分類可以為個性化搜索引擎奠定基礎分類的概念給定:一個實例的描述, xX, X是實例空間一個固定的文本分類體系: C=c1, c2,cn由于類別是事先定義好的，因此分類是有指導的（或者說是有監(jiān)督的）確定:實例x的類別 c(x)C, c(x) 是一個分類函數(shù)，定義域是 X ，值域是C說明分類模式2類問題，

2、屬于或不屬于(binary)多類問題，多個類別(multi-class)，可拆分成2類問題一個文本可以屬于多類(multi-label)分類體系一般人工構造政治、體育、軍事中美關系、恐怖事件很多分類體系: Reuters分類體系、中圖分類A類 馬列主義、毛澤東思想 B類 哲學 C類 社會科學總論 D類 政治、法律 E類 軍事 F類 經(jīng)濟 G類 文化、科學、教育、體育 H類 語言、文字 I類 文學 J類 藝術 K類 歷史、地理 N類 自然科學總論 O類 數(shù)理科學和化學 P類 天文學、地球科學 Q類 生物科學 R類 醫(yī)藥、衛(wèi)生 S類 農(nóng)業(yè)科學 U類 交通運輸 V類 航空、航天 X類 環(huán)境科學、勞動

3、保護科學（安全科學） TB類 一般工業(yè)技術 TD類 礦業(yè)工程 TE類 石油、天然氣工業(yè) TF類 冶金工業(yè) TG類 金屬學、金屬工藝 TH類 機械、儀表工藝 TJ類 武器工業(yè) TK類 動力工業(yè) TL類 原子能技術 TM類 電工技術 TN類 無線電電子學、電信技術 TP類 自動化技術、計算技術 TQ類 化學工業(yè) TS類 輕工業(yè)、手工業(yè) TU類 建筑科學 TV類 水利工程 中圖分類法 系統(tǒng)結(jié)構標注工具機器學習工具模型數(shù)據(jù)標注的樣本分類工具類別預處理預處理訓練數(shù)據(jù)文本新數(shù)據(jù)文本MultimediaGUIGarb.Coll.SemanticsMLPlanningplanningtemporalreaso

4、grammingsemanticslanguageproof.learningintelligencealgorithmreinforcementnetwork.garbagecollectionmemoryoptimizationregion.“planning language proof intelligence”訓練數(shù)據(jù)測試數(shù)據(jù)類別(AI)文本分類示例(Programming)(HCI).分類的一般過程收集訓練集和測試集，對文本進行預處理對文本進行特征提取分類器訓練（學習）測試與評價精確率、召回率、F1宏平均，微平均分類的評測偶然事件表（Cont

5、ingency Table）對一個分類器的度量準確率(precision) = a / (a + b)召回率(recall) = a / (a + c)fallout = b / (b + d)屬于此類不屬于此類判定屬于此類AB判定不屬于此類CDBEP和F測度BEP（break-even point）當準確率和召回率相等時的值即為BEPF測度，取=1 BEP和F測度的值越大，則表示分類器的性能越好。BEP只是F1所有可能取值中的一個特定值（當p = r時），因此BEP小于或等于F1的最大值。多類分類問題的評價宏平均（macro-averaging）先對每個分類器計算上述量度，再對所有分類器求平

6、均是關于類別的均值微平均（micro-averaging）先合并所有分類器的偶然事件表中的各元素，得到一個總的偶然事件表，再由此表計算各種量度。是關于文本的均值收集訓練數(shù)據(jù)TREC提供統(tǒng)一的訓練集和測試集進行系統(tǒng)評測國外：CMU,BERKLEY,CORNELL國內(nèi)：中科院計算所，清華大學，復旦大學后續(xù)增加了網(wǎng)頁語料和中文文本但是中文文本是新華社的新聞稿，與網(wǎng)頁的分類體系還有差別目前已有的評測語料有指導的機器學習方法是實現(xiàn)中文網(wǎng)頁自動分類的基礎，因此訓練集是實現(xiàn)分類的前提條件已有訓練語料863評測語料(中圖分類)搜狗語料復旦語料訓練語料分類體系中圖分類體系處理對象是圖書，不適合網(wǎng)頁分類學科分類與

7、代碼1992年制定，時間過久，包括一些過時類別上述兩個分類標準都不能直接用做中文網(wǎng)頁的分類中文網(wǎng)頁的分類體系一種中文網(wǎng)頁的分類體系訓練集的大小通過不斷增加實例的個數(shù)，考察每個類訓練樣本對分類器質(zhì)量的影響 宏觀F1 微觀F1網(wǎng)頁預處理去掉網(wǎng)頁中的導航信息去掉HTML網(wǎng)頁中的tag標記(中文)分詞、詞性標注、短語識別、去除停用詞和詞根還原(stemming)數(shù)據(jù)清洗：去掉不合適的噪聲文檔或文檔內(nèi)垃圾數(shù)據(jù)特征提取特征提取(Feature Selection)在文本分類問題中遇到的一個主要困難就是高維的特征空間通常一份普通的文本在經(jīng)過文本表示后，如果以詞為特征，它的特征空間維數(shù)將達到幾千，甚至幾萬大多

8、數(shù)學習算法都無法處理如此大的維數(shù)為了能夠在保證分類性能的前提下，自動降低特征空間的維數(shù)，在許多文本分類系統(tǒng)的實現(xiàn)中都引入了特征提取方法舉例對每類構造k 個最有區(qū)別能力的term例如：計算機領域：主機、芯片、內(nèi)存、編譯 汽車領域: 輪胎，方向盤，底盤，氣缸，用文檔頻率選特征文檔頻率DF (Document Frequency)DFi：所有文檔集合中出現(xiàn)特征i的文檔數(shù)目基本假設：稀少的詞或者對于目錄預測沒有幫助，或者不會影響整體性能。實現(xiàn)方法：先計算所有詞的DF，然后刪除所有DF小于某個閾值的詞，從而降低特征空間的維數(shù)。優(yōu)缺點：最簡單的降低特征空間維數(shù)的方法稀少的詞具有更多的信息，因此不宜用DF大

9、幅度地刪除詞詞的熵term的熵該值越大，說明分布越均勻，越有可能出現(xiàn)在較多的類別中；該值越小，說明分布越傾斜，詞可能出現(xiàn)在較少的類別中信息增益(Information Gain, IG)t 出現(xiàn)的概率 t 不出現(xiàn)假定t 出現(xiàn)時取第i 個類別的概率 取第 i 個類別時的概率該term為整個分類所能提供的信息量不考慮任何特征的熵和考慮該特征后的熵的差值信息增益計算的是已知一個詞t是否出現(xiàn)在一份文本中對于類別預測有多少信息。這里的定義是一個更一般的、針對多個類別的定義?；バ畔ⅲ∕utual Information）互信息(Mutual Information)：MI越大t和c共現(xiàn)程度越大互信息的定義

10、與交叉熵近似，只是互信息不考慮t不出現(xiàn)的概率，它的定義為：2統(tǒng)計量（CHI）：2統(tǒng)計量的定義可以從一個詞t與一個類別c的偶然事件表引出（假設文本的總數(shù)為N ）度量兩者(term和類別)獨立性程度2 越大，獨立性越小，相關性越大若ADBC,則類和詞獨立, N=A+B+C+DABCDttcc特征提取方法的性能比較(Macro-F1)特征提取方法的性能比較(Micro-F1)結(jié)論可以看出CHI，IG，DF性能好于MIMI最差CHI，IG，DF性能相當DF具有算法簡單，質(zhì)量高的優(yōu)點，可以替代CHI，IG分類器學習訓練樣本實例：一個文本實例 xX帶有正確的類別標記 c(x)學習的過程是在給定訓練樣本集合

11、D 的前提下，尋找一個分類函數(shù)h(x), 使得:貝葉斯分類貝葉斯分類基于概率理論的學習和分類方法貝葉斯理論在概率學習及分類中充當重要角色僅使用每類的先驗概率不能對待分的文本提供信息分類是根據(jù)給定樣本描述的可能的類別基礎上產(chǎn)生的后驗概率分布貝葉斯理論得到：由條件概率的定義：貝葉斯分類設各個類別的集合為 c1, c2,cn設E為實例的描述確定E的類別P(E) 可以根據(jù)下式確定貝葉斯分類(cont.)需要知道:先驗概率: P(ci) 條件概率: P(E | ci)P(ci) 容易從數(shù)據(jù)中獲得如果文檔集合D中，屬于ci的樣例數(shù)為 ni則有P(ci) = ni / |D|假設樣例的特征是關聯(lián)的:指數(shù)級的

12、估計所有的 P(E | ci)樸素的貝葉斯分類如果假定樣例的特征是獨立的，可以寫為：因此，只需要知道每個特征和類別的P(ej | ci) 如果只計算單個特征的分布，大大地減少了計算量文本分類 Nave Bayes算法(訓練)設V為文檔集合D所有詞詞表對每個類別 ci C Di 是文檔D中類別Ci的文檔集合 P(ci) = |Di| / |D|設 ni 為Di中詞的總數(shù) 對每個詞 wj V 令 nij 為Di中wij的數(shù)量 P(wi | ci) = (nij+ 1) / (ni + |V |)文本分類 Nave Bayes算法(測試)給定測試文檔 X設 n 為X中詞的個數(shù)返回的類別:wi是X中第

13、i個位置的詞Nave Bayes分類舉例C = allergy, cold, welle1 = sneeze; e2 = cough; e3 = fever當前實例是：E = sneeze, cough, feverProbWellColdAllergyP(ci) 0.9 0.05 0.05P(sneeze|ci) 0.1 0.9 0.9P(cough|ci) 0.1 0.8 0.7P(fever|ci) 0.01 0.7 0.4過敏打噴嚏Nave Bayes 舉例 (cont.)參數(shù)計算：P(well | E) = (0.9)(0.1)(0.1)(0.99)/P(E)=0.0089/P(E)

14、P(cold | E) = (0.05)(0.9)(0.8)(0.3)/P(E)=0.01/P(E)P(allergy | E) = (0.05)(0.9)(0.7)(0.6)/P(E)=0.019/P(E)最大概率類: allergyP(E) = 0.089 + 0.01 + 0.019 = 0.0379P(well | E) = 0.23P(cold | E) = 0.26P(allergy | E) = 0.50Play-tennis 例子: 估算 P(xi|C)P(p) = 9/14P(n) = 5/14outlookP(sunny|p) = 2/9P(sunny|n) = 3/5P(

15、overcast|p) = 4/9P(overcast|n) = 0P(rain|p) = 3/9P(rain|n) = 2/5temperatureP(hot|p) = 2/9P(hot|n) = 2/5P(mild|p) = 4/9P(mild|n) = 2/5P(cool|p) = 3/9P(cool|n) = 1/5humidityP(high|p) = 3/9P(high|n) = 4/5P(normal|p) = 6/9P(normal|n) = 2/5windyP(true|p) = 3/9P(true|n) = 3/5P(false|p) = 6/9P(false|n) = 2

16、/5正例反例Play-tennis例子: 分類 X例子 X = P(X|p)P(p) = P(rain|p)P(hot|p)P(high|p)P(false|p)P(p) = 3/92/93/96/99/14 = 0.010582P(X|n)P(n) = P(rain|n)P(hot|n)P(high|n)P(false|n)P(n) = 2/52/54/52/55/14 = 0.018286樣本 X 被分到 n類，即“不適合打網(wǎng)球”舉例在Joachims(1996)的一個實驗中，被應用于分類新聞組文章20個電子新聞組，每個新聞組1000篇文章，形成2萬個文檔的數(shù)據(jù)集2/3作訓練集，1/3作測

17、試集衡量性能20 個新聞組，隨機猜測的分類精確度5%，由程序獲得的精確度89%討論樸素的貝葉斯假定在一個位置上出現(xiàn)的詞的概率獨立于另外一個位置的單詞，這個假定有時并不反映真實情況雖然獨立性假設很不精確，別無選擇，否則計算的概率項將極為龐大幸運的是，在實踐中樸素貝葉斯學習器在許多文本分類中性能非常好，即使獨立性假設不成立K近鄰 K近鄰（KNN）最近鄰分類規(guī)則 對于測試樣本點x，在集合中距離它最近的的x1。最近鄰分類就是把x分為x1 所屬的類別最近鄰規(guī)則的推廣- KNN沒有好的相似度矩陣不能用 KNNKNN算法目標：基于訓練集X的對y分類在訓練集中，尋找和y最相似的訓練樣本x得到k個最相似的集合A

18、,A為X的一個子集設n1,n2分別為集合中屬于c1,c2的個數(shù)如果p(c1|y)p(c2|y),判為c1,否則判為c2kNN方法一種基于實例的學習方法新文本k=1, A類k=4，B類k=10，B類帶權重計算，計算權重和最大的類。k常取3或者5。KNN在文本分類中的應用KNN分類錯誤是由于：單個的非典型樣例 單個訓練樣本的噪音.更魯棒的方法是發(fā)現(xiàn)k個最相似的樣本，返回k個樣本最主要的類別相似度矩陣最近鄰方法依賴于相似度矩陣(或距離).對連續(xù)m維空間最簡單的方法采用歐氏距.對m維二值實例空間最簡單的方法是海明距.對于基于文本tf/idf權重向量的余弦相似度是經(jīng)常被采用的.影響KNN的因素K的取值K

19、一般取15計算距離的方法歐式距離蘭式距離（余弦相似度）KNN和NB比較從表中看，KNN質(zhì)量較高，NB的效率較高從各個類別看，KNN比NB穩(wěn)定，NB對類別敏感決策樹簡介決策樹方法的起源是概念學習系統(tǒng)CLS，然后發(fā)展到ID3方法而為高潮，最后又演化為能處理連續(xù)屬性的C4.5。有名的決策樹方法還有CART和Assistant應用最廣的歸納推理算法之一一種逼近離散值目標函數(shù)的方法決策樹的表示法決策樹通過把實例從根節(jié)點排列到某個葉子節(jié)點來分類實例，葉子節(jié)點即為實例所屬的分類。樹上的每一個節(jié)點說明了對實例的某個屬性的測試，并且該節(jié)點的每一個后繼分支對應于該屬性的一個可能值決策樹表示舉例表達式?jīng)Q策樹學習的適

20、用問題實例是由屬性-值對表示的目標函數(shù)具有離散的輸出值可能需要析取的描述訓練數(shù)據(jù)可以包含錯誤訓練數(shù)據(jù)可以包含缺少屬性值的實例屬性選擇構造好的決策樹的關鍵在于如何選擇好的邏輯判斷或?qū)傩?。對于同樣一組例子，可以有很多決策樹能符合這組例子。一般情況下或具有較大概率地說，樹越小則樹的預測能力越強。要構造盡可能小的決策樹，關鍵在于選擇恰當?shù)倪壿嬇袛嗷驅(qū)傩?。由于構造最小的樹是NP-難問題，因此只能采取用啟發(fā)式策略選擇好的邏輯判斷或?qū)傩?用熵度量樣例的均一性（純度）熵的定義舉例關于某布爾分類的熵函數(shù)用信息增益度量期望熵最低一個屬性的信息增益就是由于使用這個屬性分割樣例而導致的期望熵的降低舉例計算信息增益確定

21、最佳分類的屬性哪一個屬性是最好的分類？S:9+,5-E=0.940Humidity3+，4-E=0.9856+,1-E=0.592Gain(S,Humidity)=0.940-(7/14)0.985-(7/14)0.592S:9+,5-E=0.940Wind6+，2-E=0.8113+，3-E=1.000Gain(S,Wind)=0.940-(8/14)0.811-(6/14)0.100highnormalstrongweak不同屬性的信息增益計算各屬性的熵值Gain(S,Outlook)=0.246Gain(S,Humidity)=0.151Gain(S,Wind)=0.048Gain(S,

22、Temperature)=0.029可以看到，Outlook得信息增益最大D1,D2,D149+,5-OutlookSunnyD1,D2,D8,D9,D112+,3-RainD4,D5,D6,D10,D143+,2-D3,D7,D12,D134+,0-Overcast?哪一個屬性在這里被測試？Ssunny=D1,D2,D8,D9,D11Gain（Ssunny,Humidity）=0.970-(3/5)0.0-(2/5)0.0=0.970Gain(Ssunny, Temperature)=0.970-(2/5)0.0-(2/5)1.0-(1/5)0.0=0.570Gain(Ssunny, Win

23、d)=0.970-(2/5)1.0-(3/5)0.918=0.019?YesID3算法創(chuàng)建樹的Root結(jié)點開始AAttributes中分類能力最好的屬性Root的決策屬性A對于每個可能值vi 在Root下加一個新的分支對應測試A=vi 令Examplesvi為Examples中滿足A屬性值為vi的子集 如果Examplesvi為空在這個新分支下加一個葉子結(jié)點，節(jié)點的lable=Examples中最普遍的目標屬性值(target-attribute)否則在這個新分支下加一個子樹ID3(examplevi,target-attribute,attributes-A)返回 RootC4.5C4.5是

24、對ID3的改進算法對連續(xù)值的處理對未知特征值的處理對決策樹進行剪枝規(guī)則的派生決策樹學習的常見問題過度擬合數(shù)據(jù)基本的決策樹構造算法沒有考慮噪聲，生成的決策樹完全與訓練例子擬合有噪聲情況下，完全擬合將導致過分擬合（overfitting），即對訓練數(shù)據(jù)的完全擬合反而不具有很好的預測性能 解決方法剪枝是一種克服噪聲的技術，同時它也能使樹得到簡化而變得更容易理解。向前剪枝（forward pruning）向后剪枝（backward pruning） 理論上講，向后剪枝好于向前剪枝，但計算復雜度大。剪枝過程中一般要涉及一些統(tǒng)計參數(shù)或閾值，如停機閾值有人提出了一種和統(tǒng)計參數(shù)無關的基于最小描述長度（MDL）

25、的有效剪枝法 決策樹的優(yōu)點可以生成可以理解的規(guī)則計算量相對來說不是很大可以處理連續(xù)和離散字段決策樹可以清晰的顯示哪些字段比較重要過程可見不足之處對連續(xù)性的字段比較難預測當類別太多時，錯誤可能會增加的比較快一般的算法分類的時候，只是根據(jù)一個屬性來分類。不是全局最優(yōu)文本分類的應用新聞出版按照欄目分類類別 政治,體育,軍事,網(wǎng)頁分類類似于Yahoo的分類個性化新聞智能推薦垃圾郵件過濾類別 spam, not-spam文本聚類Text Clustering聚類式搜索聚類式搜索聚類將無標記的樣本劃分到聚類的各個子集中:類內(nèi)樣本非常相似類間樣本非常不同無監(jiān)督方法發(fā)現(xiàn)新類別.聚類樣例.層次聚類在無標注的樣本

26、集合中建立 樹狀層次分類結(jié)構遞歸的標準層次聚類算法應用生成層次聚類.animalvertebratefish reptile amphib. mammal worm insect crustaceaninvertebrate會聚vs. 分裂聚類會聚(bottom-up) 以每個樣本獨自一類開始，迭代合并到越來越大的類中分裂 (partitional, top-down) 將所有樣本不斷劃分到類別中會聚層次聚類 (HAC)設定相似度函數(shù)確定任意兩個實例的相似度開始每個實例獨自一類然后重復合并最相似的類別，直到成為一類：在當前的類別中，確定最近的兩類ci 和cj用單一的類別 ci cj取代 ci

27、和 cj合并的過程成為層次結(jié)構聚類相似度設定一個相似度函數(shù)確定兩個實例的相似程度文本向量的余弦相似度如何計算包含多個樣例的兩個類別的相似度？Single Link: 兩個類別中最近成員的相似度Complete Link: 兩個類別中最遠成員的相似度Group Average: 成員間的平均相似度計算復雜度在第一次迭代中，HAC方法需要計算所有樣例的每一對的距離在合并迭代中，需要計算新形成的類與其他類的距離為了維持O(n2)的性能，計算類與類之間的相似度需要常數(shù)時間計算類別間相似度合并ci,cj后，計算該類和其他類的相似度可以如下計算：Single Link:Complete Link:平均連通

28、凝聚聚類單連通容易導致狹長聚類，全連通的算法復雜度為O(n3)用合并后的類中所有對平均相似度度量兩個類的相似度是全連通和單連通的折中.計算平均連通相似度設定余弦相似度及單位長度歸一化向量.總是維持每個類別的向量和.計算類別相似度在常數(shù)時間內(nèi):非層次聚類需要確定期望的類別數(shù)k隨機選擇k個種子 進行初始聚類迭代，將樣例重新劃分直到樣例所屬的類別不再改變K-Means設定樣例是一個實值向量基于質(zhì)心或類c中樣本的均值聚類根據(jù)樣例與當前類別質(zhì)心的相似度重新劃分類別距離矩陣歐式距 (L2 norm):L1 norm:余弦相似度 (轉(zhuǎn)換成距離):K-Means 算法令 d為兩個實例的距離度量.選擇 k 個隨機樣例s1, s2, sk 作為種子.直到聚類收斂或滿足停止策略