第六章文本分類與聚類

1、文本分類與聚類這一部分將講述這一部分將講述n文本分類及聚類的概念文本分類及聚類的概念n文本特征的提取方法文本特征的提取方法n貝葉斯分類，貝葉斯分類，KNNKNN分類分類n層次聚類的方法層次聚類的方法文本分類概述文本分類概述概述概述n文本分類包括普通文本分類和網(wǎng)頁文本分類文本分類包括普通文本分類和網(wǎng)頁文本分類n中文網(wǎng)頁分類技術(shù)已經(jīng)成為中文信息處理領(lǐng)中文網(wǎng)頁分類技術(shù)已經(jīng)成為中文信息處理領(lǐng)域的一項基礎(chǔ)性工作域的一項基礎(chǔ)性工作n網(wǎng)頁分類可以為搜索引擎用戶提供目錄導航網(wǎng)頁分類可以為搜索引擎用戶提供目錄導航服務(wù)，進而提高系統(tǒng)查準率服務(wù)，進而提高系統(tǒng)查準率n網(wǎng)頁分類可以為個性化搜索引擎奠定基礎(chǔ)網(wǎng)頁分類可以為

2、個性化搜索引擎奠定基礎(chǔ)5引言引言n物以類聚、人以群分物以類聚、人以群分n相似的對象總聚集在一起相似的對象總聚集在一起n根據(jù)聚集情況可以對新的對象進行劃分根據(jù)聚集情況可以對新的對象進行劃分n分類分類/ /聚類的根本原因就是因為對象數(shù)目太多，處理困難聚類的根本原因就是因為對象數(shù)目太多，處理困難n一些信息處理部門，一個工作人員一天要看上千份信息一些信息處理部門，一個工作人員一天要看上千份信息n分門別類將會大大減少處理難度分門別類將會大大減少處理難度n分類是非常普遍的一種處理手段分類是非常普遍的一種處理手段n性別、籍貫、民族、學歷、年齡等等，我們每個人身上貼滿了性別、籍貫、民族、學歷、年齡等等，我們每

3、個人身上貼滿了“標簽標簽”n我們從孩提開始就具有分類能力：電影中的好人、壞人；好阿姨、壞我們從孩提開始就具有分類能力：電影中的好人、壞人；好阿姨、壞阿姨；親人、非親人等等。阿姨；親人、非親人等等。n分類無處不在，從現(xiàn)在開始，我們可以以分類的眼光看世界分類無處不在，從現(xiàn)在開始，我們可以以分類的眼光看世界 6分類和聚類的例子分類和聚類的例子n分類的例子：分類的例子：n在新街口馬路上碰到一個人，判斷他在新街口馬路上碰到一個人，判斷他/ /她是不是學生？她是不是學生？n根據(jù)某些特征給對象貼一個根據(jù)某些特征給對象貼一個“標簽標簽”。n聚類的例子：聚類的例子：n去綜合樓一個大教室上自習，往往發(fā)現(xiàn)大家三三兩

4、兩扎去綜合樓一個大教室上自習，往往發(fā)現(xiàn)大家三三兩兩扎推地坐，一打聽，原來坐在一塊的大都是一個班的。推地坐，一打聽，原來坐在一塊的大都是一個班的。n事先不知道事先不知道“標簽標簽”，根據(jù)對象之間的相似情況進行成，根據(jù)對象之間的相似情況進行成團分析。團分析。分類的概念分類的概念n給定給定: :n一個實例的描述一個實例的描述, , x x X X, X, X是實例空間是實例空間n一個固定的文本分類體系一個固定的文本分類體系: : C=C= c c1 1, , c c2 2, ,c cn n n由于類別是事先定義好的，因此分類是有指由于類別是事先定義好的，因此分類是有指導的（或者說是有監(jiān)督的）導的（或

5、者說是有監(jiān)督的）n確定確定: :n實例實例x x的類別的類別 c c( (x x) ) C C, , c c( (x x) ) 是一個分類函數(shù)，是一個分類函數(shù)，定義域是定義域是 X X ，值域是，值域是C C8文本分類的定義文本分類的定義n事先給定分類體系和訓練樣例事先給定分類體系和訓練樣例( (標注好類別標注好類別信息的文本信息的文本) )，將文本分到某個或者某幾個，將文本分到某個或者某幾個類別中。類別中。n計算機自動分類，就是根據(jù)已經(jīng)標注好類別信計算機自動分類，就是根據(jù)已經(jīng)標注好類別信息的訓練集合進行學習，將學習到的規(guī)律用于息的訓練集合進行學習，將學習到的規(guī)律用于新樣本新樣本( (也叫測試

6、樣本也叫測試樣本) )的類別判定。的類別判定。n分類是有監(jiān)督分類是有監(jiān)督/ /指導學習指導學習(Supervised Learning)(Supervised Learning)的的一種。一種。文本分類的模式文本分類的模式n從類別數(shù)目來分從類別數(shù)目來分n2 2類問題，屬于或不屬于類問題，屬于或不屬于(binary)(binary)n多類問題，多個類別多類問題，多個類別(multi-class)(multi-class)，可拆分成，可拆分成2 2類問題類問題n一個文本可以屬于多類一個文本可以屬于多類(multi-label)(multi-label)n從是否兼類看分從是否兼類看分n單標簽單標簽(

7、single label)(single label)問題：一個文本只屬于一個類問題：一個文本只屬于一個類n多標簽多標簽(multi-label)(multi-label)問題：一個文本可以屬于多類，即出問題：一個文本可以屬于多類，即出現(xiàn)兼類現(xiàn)象現(xiàn)兼類現(xiàn)象10關(guān)于分類體系關(guān)于分類體系n分類體系的構(gòu)建標準可以是按照語義分類體系的構(gòu)建標準可以是按照語義( (如：政治、如：政治、經(jīng)濟、軍事經(jīng)濟、軍事)，也可以是按照其他標準，也可以是按照其他標準( (如：垃圾如：垃圾vs. vs. 非垃圾；游戲網(wǎng)站非垃圾；游戲網(wǎng)站vs. vs. 非游戲網(wǎng)站非游戲網(wǎng)站) )，完全取決，完全取決于目標應(yīng)用的需求。于目標應(yīng)

8、用的需求。n分類體系一般由人工構(gòu)造，可以是層次結(jié)構(gòu)。分類體系一般由人工構(gòu)造，可以是層次結(jié)構(gòu)。n一些分類體系一些分類體系: Reuters: Reuters語料分類體系、中圖分類、語料分類體系、中圖分類、Yahoo Yahoo ！分類目錄。！分類目錄。11訓練語料分類體系訓練語料分類體系n中圖分類體系中圖分類體系n處理對象是圖書，不適合網(wǎng)頁分類處理對象是圖書，不適合網(wǎng)頁分類n學科分類與代碼學科分類與代碼n19921992年制定，時間過久，包括一些過時類別年制定，時間過久，包括一些過時類別n上述兩個分類標準都不能直接用做中文上述兩個分類標準都不能直接用做中文網(wǎng)頁的分類網(wǎng)頁的分類n中文網(wǎng)頁的分類體系

9、中文網(wǎng)頁的分類體系A(chǔ)類 馬列主義、毛澤東思想 B類 哲學 C類 社會科學總論 D類 政治、法律 E類 軍事 F類 經(jīng)濟 G類 文化、科學、教育、體育 H類 語言、文字 I類 文學 J類 藝術(shù) K類 歷史、地理 N類 自然科學總論 O類 數(shù)理科學和化學 P類 天文學、地球科學 Q類 生物科學 R類 醫(yī)藥、衛(wèi)生 S類 農(nóng)業(yè)科學 U類 交通運輸 V類 航空、航天 X類 環(huán)境科學、勞動保護科學（安全科學） TB類 一般工業(yè)技術(shù) TD類 礦業(yè)工程 TE類 石油、天然氣工業(yè) TF類 冶金工業(yè) TG類 金屬學、金屬工藝 TH類 機械、儀表工藝 TJ類 武器工業(yè) TK類 動力工業(yè) TL類 原子能技術(shù) TM類

10、電工技術(shù) TN類 無線電電子學、電信技術(shù) TP類 自動化技術(shù)、計算技術(shù) TQ類 化學工業(yè) TS類 輕工業(yè)、手工業(yè) TU類 建筑科學 TV類 水利工程 中圖分類法中圖分類法13一種中文網(wǎng)頁的分類體系 系統(tǒng)結(jié)構(gòu)標注工具模型數(shù)據(jù)標注的樣本類別預(yù)處理預(yù)處理訓練數(shù)據(jù)文本新數(shù)據(jù)文本15文本分類的應(yīng)用文本分類的應(yīng)用n垃圾郵件的判定垃圾郵件的判定(spam or not spam)(spam or not spam)n類別類別spam, not-spamspam, not-spamn新聞出版按照欄目分類新聞出版按照欄目分類n類別類別 政治政治, ,體育體育, ,軍事軍事,n詞性標注詞性標注n類別類別 名詞名詞

11、, ,動詞動詞, ,形容詞形容詞,n詞義排歧詞義排歧n類別類別 詞義詞義1, 1,詞義詞義2,2,16文本分類的過程（文本分類的過程（1 1）n獲取訓練文檔集合獲取訓練文檔集合 n訓練訓練(training)(training)：即從訓練樣本中學習分類的規(guī)律。：即從訓練樣本中學習分類的規(guī)律。n測試測試(test(test或分類或分類classification)classification)：根據(jù)學習到的規(guī)律對新來：根據(jù)學習到的規(guī)律對新來的文本進行類別判定。的文本進行類別判定。n建立文檔表示模型建立文檔表示模型 n目前的文本分類系統(tǒng)，絕大多數(shù)都是以詞語來表征文檔目前的文本分類系統(tǒng)，絕大多數(shù)都是

12、以詞語來表征文檔的，用關(guān)鍵詞、短語、主題詞、概念的都有。的，用關(guān)鍵詞、短語、主題詞、概念的都有。17文本分類的過程（文本分類的過程（2 2）n特征選擇特征選擇n不管是訓練還是測試，都要先分析出文本的某些特征不管是訓練還是測試，都要先分析出文本的某些特征(feature(feature，也稱為標引項，也稱為標引項term)term)，然后把文本變成這些特，然后把文本變成這些特征的某種適宜處理的表示形式，通常都采用向量表示形征的某種適宜處理的表示形式，通常都采用向量表示形式或者直接使用某些統(tǒng)計量。式或者直接使用某些統(tǒng)計量。n選擇或設(shè)計分類模型選擇或設(shè)計分類模型n建立從文檔特征（或?qū)傩裕┑轿臋n類別的

13、映射關(guān)系，是建立從文檔特征（或?qū)傩裕┑轿臋n類別的映射關(guān)系，是文本分類的核心問題?，F(xiàn)有的分類方法主要來自兩個方文本分類的核心問題?，F(xiàn)有的分類方法主要來自兩個方面：統(tǒng)計和機器學習，比較著名的文檔分類方法有面：統(tǒng)計和機器學習，比較著名的文檔分類方法有kNNkNN、Nave Nave BayesBayes（NBNB）、）、SVMSVM等等。等等。 18文本分類的過程（文本分類的過程（3 3）n性能評測模型性能評測模型 n性能評測是分類處理流程中的重要一環(huán)。對改進和性能評測是分類處理流程中的重要一環(huán)。對改進和完善分類系統(tǒng)具有指導意義。完善分類系統(tǒng)具有指導意義。 19文本分類的方法文本分類的方法n人工方法

14、：人工總結(jié)規(guī)則人工方法：人工總結(jié)規(guī)則n優(yōu)點：優(yōu)點：n結(jié)果容易理解：如足球結(jié)果容易理解：如足球and and 聯(lián)賽聯(lián)賽體育類體育類n缺點：缺點：n費時費力費時費力n難以保證一致性和準確性難以保證一致性和準確性(40%(40%左右的準確率左右的準確率) )n專家有時候憑空想象，沒有基于真實語料的分布專家有時候憑空想象，沒有基于真實語料的分布n代表方法：人們曾經(jīng)通過知識工程的方法建立專家系統(tǒng)代表方法：人們曾經(jīng)通過知識工程的方法建立專家系統(tǒng)(80(80年代末期年代末期) )用于分類。用于分類。n自動的方法自動的方法( (學習學習) )：從訓練語料中學習規(guī)則：從訓練語料中學習規(guī)則n優(yōu)點：優(yōu)點：n快速快速

15、n準確率相對高準確率相對高( (準確率可達準確率可達60%60%或者更高或者更高) )n來源于真實文本，可信度高來源于真實文本，可信度高n缺點：缺點：n結(jié)果可能不易理解結(jié)果可能不易理解( (比如有時是一個復(fù)雜的數(shù)學表達式比如有時是一個復(fù)雜的數(shù)學表達式) )20規(guī)則方法和統(tǒng)計方法規(guī)則方法和統(tǒng)計方法n規(guī)則方法通過得到某些規(guī)則來指導分類，而這些規(guī)則往往是人規(guī)則方法通過得到某些規(guī)則來指導分類，而這些規(guī)則往往是人可以理解的?？梢岳斫獾?。n統(tǒng)計方法通過計算得到一些數(shù)學表達式來指導分類。統(tǒng)計方法通過計算得到一些數(shù)學表達式來指導分類。n規(guī)則方法和統(tǒng)計方法沒有本質(zhì)的區(qū)別，它們都是想得到某種規(guī)規(guī)則方法和統(tǒng)計方法沒

16、有本質(zhì)的區(qū)別，它們都是想得到某種規(guī)律性的東西來指導分類，統(tǒng)計方法得到的數(shù)學表達式可以認為律性的東西來指導分類，統(tǒng)計方法得到的數(shù)學表達式可以認為是某種隱式規(guī)則。是某種隱式規(guī)則。n在目前的文本分類當中，統(tǒng)計方法占據(jù)了主流地位。在目前的文本分類當中，統(tǒng)計方法占據(jù)了主流地位。分類的評測分類的評測n偶然事件表（偶然事件表（Contingency TableContingency Table）n對一個分類器的度量對一個分類器的度量n準確率準確率(precision) = a / (a + b)(precision) = a / (a + b)n召回率召回率(recall) = a / (a + c)(re

17、call) = a / (a + c)nfallout = b / (b + d)fallout = b / (b + d)屬于此類不屬于此類判定屬于此類AB判定不屬于此類CDBEPBEP和和F F測度測度nBEPBEP（break-even pointbreak-even point）n當準確率和召回率相等時的值即為當準確率和召回率相等時的值即為BEPBEPnF F測度，取測度，取=1 =1 nBEPBEP和和F F測度的值越大，則表示分類器的性能越測度的值越大，則表示分類器的性能越好。好。nBEPBEP只是只是F1F1所有可能取值中的一個特定值（當所有可能取值中的一個特定值（當p p =

18、r= r時），因此時），因此BEPBEP小于或等于小于或等于F1F1的最大值。的最大值。rpprrpF221,rpprF21多類分類問題的評價多類分類問題的評價n宏平均（宏平均（macro-averagingmacro-averaging）n先對每個分類器計算上述量度，再對所有分先對每個分類器計算上述量度，再對所有分類器求平均類器求平均n是關(guān)于類別的均值是關(guān)于類別的均值n微平均（微平均（micro-averagingmicro-averaging）n先合并所有分類器的偶然事件表中的各元素，先合并所有分類器的偶然事件表中的各元素，得到一個總的偶然事件表，再由此表計算各得到一個總的偶然事件表，再由

19、此表計算各種量度。種量度。n是關(guān)于文本的均值是關(guān)于文本的均值收集訓練數(shù)據(jù)收集訓練數(shù)據(jù)nTRECTREC提供統(tǒng)一的訓練集和測試集進行系提供統(tǒng)一的訓練集和測試集進行系統(tǒng)評測統(tǒng)評測n國外：國外：CMU,BERKLEY,CORNELLCMU,BERKLEY,CORNELLn國內(nèi)：中科院計算所，清華大學，復(fù)旦大學國內(nèi)：中科院計算所，清華大學，復(fù)旦大學n后續(xù)增加了網(wǎng)頁語料和中文文本后續(xù)增加了網(wǎng)頁語料和中文文本n但是中文文本是新華社的新聞稿，與網(wǎng)頁的但是中文文本是新華社的新聞稿，與網(wǎng)頁的分類體系還有差別分類體系還有差別目前已有的評測語料目前已有的評測語料n有指導的機器學習方法是實現(xiàn)中文網(wǎng)頁有指導的機器學習方

20、法是實現(xiàn)中文網(wǎng)頁自動分類的基礎(chǔ)，因此訓練集是實現(xiàn)分自動分類的基礎(chǔ)，因此訓練集是實現(xiàn)分類的前提條件類的前提條件n已有訓練語料已有訓練語料n863863評測語料評測語料( (中圖分類中圖分類) )n搜狗語料搜狗語料n復(fù)旦語料復(fù)旦語料訓練集的大小訓練集的大小n通過不斷增加實例的個數(shù)，考察每個類訓練樣通過不斷增加實例的個數(shù)，考察每個類訓練樣本對分類器質(zhì)量的影響本對分類器質(zhì)量的影響 宏觀F1 微觀F1特征提取特征提取特征提取特征提取(Feature Selection)(Feature Selection)n在文本分類問題中遇到的一個主要困難就是高維在文本分類問題中遇到的一個主要困難就是高維的特征空間的

21、特征空間n通常一份普通的文本在經(jīng)過文本表示后，如果以詞為特通常一份普通的文本在經(jīng)過文本表示后，如果以詞為特征，它的特征空間維數(shù)將達到幾千，甚至幾萬征，它的特征空間維數(shù)將達到幾千，甚至幾萬n大多數(shù)學習算法都無法處理如此大的維數(shù)大多數(shù)學習算法都無法處理如此大的維數(shù)n在不犧牲分類質(zhì)量的前提下盡可能降低特征空間在不犧牲分類質(zhì)量的前提下盡可能降低特征空間的維數(shù)的維數(shù)n特征選取的任務(wù)將信息量小，不重要的詞匯從特特征選取的任務(wù)將信息量小，不重要的詞匯從特征空間中刪除，減少特征項的個數(shù)征空間中刪除，減少特征項的個數(shù)n在許多文本分類系統(tǒng)的實現(xiàn)中都引入了特征提取在許多文本分類系統(tǒng)的實現(xiàn)中都引入了特征提取方法方法特

22、征選擇舉例特征選擇舉例n對每類構(gòu)造對每類構(gòu)造k k 個最有區(qū)別能力的個最有區(qū)別能力的termtermn例如：例如：n計算機領(lǐng)域計算機領(lǐng)域：n主機、芯片、內(nèi)存、編譯主機、芯片、內(nèi)存、編譯 n汽車領(lǐng)域汽車領(lǐng)域: : n輪胎，方向盤，底盤，氣缸，輪胎，方向盤，底盤，氣缸，用文檔頻率選特征用文檔頻率選特征n文檔頻率文檔頻率nDF (Document Frequency)DF (Document Frequency)nDFiDFi：所有文檔集合中出現(xiàn)特征：所有文檔集合中出現(xiàn)特征i i的文檔數(shù)目的文檔數(shù)目n基本假設(shè)：稀少的詞或者對于目錄預(yù)測沒有幫基本假設(shè)：稀少的詞或者對于目錄預(yù)測沒有幫助，或者不會影響整體

23、性能。助，或者不會影響整體性能。n實現(xiàn)方法：先計算所有詞的實現(xiàn)方法：先計算所有詞的DFDF，然后刪除所有，然后刪除所有DFDF小于某個閾值的詞，從而降低特征空間的維小于某個閾值的詞，從而降低特征空間的維數(shù)。數(shù)。n優(yōu)缺點：優(yōu)缺點：n最簡單的降低特征空間維數(shù)的方法最簡單的降低特征空間維數(shù)的方法n稀少的詞具有更多的信息，因此不宜用稀少的詞具有更多的信息，因此不宜用DFDF大幅度地大幅度地刪除詞刪除詞詞的熵詞的熵ntermterm的熵的熵n該值越大，說明分布越均勻，越有可能出現(xiàn)在該值越大，說明分布越均勻，越有可能出現(xiàn)在較多的類別中；較多的類別中；n該值越小，說明分布越傾斜，詞可能出現(xiàn)在較該值越小，說明

24、分布越傾斜，詞可能出現(xiàn)在較少的類別中少的類別中iiitcPtcPtEntropy)|(log)|()(信息增益信息增益(Information Gain, IG)(Information Gain, IG)iiririrriiririrrcPtcPtcPtPcPtcPtcPtPtG)()|(log)|()()()|(log)|()()(t 出現(xiàn)的概率 t 不出現(xiàn)假定t 出現(xiàn)時取第i 個類別的概率 取第 i 個類別時的概率n該該termterm為整個分類所能提供的信息量為整個分類所能提供的信息量n不考慮任何特征的熵和考慮該特征后的熵的差值不考慮任何特征的熵和考慮該特征后的熵的差值n信息增益計算的

25、是已知一個詞信息增益計算的是已知一個詞t t是否出現(xiàn)在一份文本中對于是否出現(xiàn)在一份文本中對于類別預(yù)測有多少信息。類別預(yù)測有多少信息。n這里的定義是一個更一般的、針對多個類別的定義。這里的定義是一個更一般的、針對多個類別的定義?；バ畔ⅲɑバ畔ⅲ∕utual InformationMutual Information）n互信息互信息(Mutual Information)(Mutual Information)：MIMI越大越大t t和和c c共共現(xiàn)程度越大現(xiàn)程度越大n互信息的定義與交叉熵近似，只是互信息不互信息的定義與交叉熵近似，只是互信息不考慮考慮t t不出現(xiàn)的概率，它的定義為：不出現(xiàn)的概率，

26、它的定義為：1( )max( ,)mMAXiiItI t cmiiiAVGctIcPtI1),()()(iririrtPctPcPtI)()|(log)()( 2 2統(tǒng)計量（統(tǒng)計量（CHICHI）：）：n 2 2統(tǒng)計量的定義可以從一個詞統(tǒng)計量的定義可以從一個詞t t與一個類別與一個類別c c的的偶然事件表引出（假設(shè)文本的總數(shù)為偶然事件表引出（假設(shè)文本的總數(shù)為N N ）n度量兩者度量兩者(term(term和類別和類別) )獨立性程度獨立性程度n 2 2 越大，獨立性越小，相關(guān)性越大越大，獨立性越小，相關(guān)性越大n若若ADBC,ADBC,則類和詞獨立則類和詞獨立, N=A+B+C+D, N=A+B

27、+C+DABCDttcc)()()()(),(22DCBADBCACBADNct特征提取方法的性能比較特征提取方法的性能比較(Macro-F1)(Macro-F1)特征提取方法的性能比較特征提取方法的性能比較(Micro-F1)(Micro-F1)結(jié)論結(jié)論n可以看出可以看出CHICHI，IGIG，DFDF性能好于性能好于MIMInMIMI最差最差nCHICHI，IGIG，DFDF性能相當性能相當nDFDF具有算法簡單，質(zhì)量高的優(yōu)點，可以具有算法簡單，質(zhì)量高的優(yōu)點，可以替代替代CHICHI，IGIG分類器學習分類器學習n訓練樣本實例：訓練樣本實例：)n一個文本實例一個文本實例 x x X Xn帶

28、有正確的類別標記帶有正確的類別標記 c c( (x x) )n學習的過程是在給定訓練樣本集合學習的過程是在給定訓練樣本集合D D 的的前提下，尋找一個分類函數(shù)前提下，尋找一個分類函數(shù)h h( (x x), ), 使得使得: :)()(: )(,xcxhDxcx貝葉斯分類貝葉斯分類貝葉斯分類貝葉斯分類n基于概率理論的學習和分類方法基于概率理論的學習和分類方法n貝葉斯理論在概率學習及分類中充當重貝葉斯理論在概率學習及分類中充當重要角色要角色n僅使用每類的先驗概率不能對僅使用每類的先驗概率不能對待分的文待分的文本本提供信息提供信息n分類是根據(jù)給定樣本描述的可能的類別分類是根據(jù)給定樣本描述的可能的類別

29、基礎(chǔ)上產(chǎn)生的后驗概率分布基礎(chǔ)上產(chǎn)生的后驗概率分布41貝葉斯分類的基本思想貝葉斯分類的基本思想nNave Nave BayesBayes分類方法（以下簡稱分類方法（以下簡稱NBNB法）將概法）將概率模型應(yīng)用于自動分類，是一種簡單而又有效率模型應(yīng)用于自動分類，是一種簡單而又有效的分類方法。的分類方法。n它的分類思想是使用貝葉斯公式，通過先驗概它的分類思想是使用貝葉斯公式，通過先驗概率和類別的條件概率來估計文檔率和類別的條件概率來估計文檔d d對類別對類別ci ci的后的后驗概率，以此實現(xiàn)對文檔驗概率，以此實現(xiàn)對文檔d d的類別歸屬判斷。的類別歸屬判斷。42Bayes Rule貝葉斯分類貝葉斯分類n

30、設(shè)各個類別的集合為設(shè)各個類別的集合為 c c1 1, , c c2 2, ,c cn n n設(shè)設(shè)E E為實例的描述為實例的描述n確定確定E E的類別的類別nP(P(E E) ) 可以根據(jù)下式確定可以根據(jù)下式確定)()|()()|(EPcEPcPEcPiiiniiiniiEPcEPcPEcP111)()|()()|(niiicEPcPEP1)|()()(貝葉斯分類貝葉斯分類(cont.)(cont.)n需要知道需要知道: :n先驗概率先驗概率: : P(P(c ci i) ) n條件概率條件概率: P(: P(E E | | c ci i) )nP(P(c ci i) ) 容易從數(shù)據(jù)中獲得容易從

31、數(shù)據(jù)中獲得n如果文檔集合如果文檔集合D D中，屬于中，屬于c ci i的樣例數(shù)為的樣例數(shù)為 n ni in則有則有P(P(c ci i) = ) = n ni i / |/ |D D| |樸素的貝葉斯分類樸素的貝葉斯分類n如果假定樣例的特征是獨立的，可以寫為：如果假定樣例的特征是獨立的，可以寫為：n因此，只需要知道每個特征和類別的因此，只需要知道每個特征和類別的P(P(e ej j | | c ci i) ) n如果只計算單個特征的分布，大大地減少了如果只計算單個特征的分布，大大地減少了計算量計算量)|()|()|(121mjijimicePceeePcEP文本分類文本分類 NaNa ve v

32、e BayesBayes算法算法( (訓練訓練) )設(shè)設(shè)V V為文檔集合為文檔集合D D所有詞詞表所有詞詞表對每個類別對每個類別 c ci i C C D Di i 是文檔是文檔D D中類別中類別C Ci i的文檔集合的文檔集合 P(P(c ci i) = |) = |D Di i| / | / |D D| |設(shè)設(shè) n ni i 為為D Di i中詞的總數(shù)中詞的總數(shù) 對每個詞對每個詞 wwj j V V 令令 n nij ij 為為D Di i中中wwij ij的數(shù)量的數(shù)量 P(P(wwi i | | c ci i) = () = (n nij ij+ 1) / (+ 1) / (n ni i

33、 + |+ |V V |)|)47文本分類文本分類 NaNa ve ve BayesBayes算法算法( (測試測試) )n給定測試文檔給定測試文檔 X Xn設(shè)設(shè) n n 為為X X中詞的個數(shù)中詞的個數(shù)n返回的類別返回的類別: :nwwi i是是X X中第中第i i個位置的詞個位置的詞)|()(argmax1niiiiCiccwPcPNaNa ve ve BayesBayes分類舉例分類舉例nC = allergy, cold, wellne1 = sneeze; e2 = cough; e3 = fevern當前實例是：E = sneeze, cough, feverProbWellCold

34、AllergyP(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過敏打噴嚏NaNa ve ve BayesBayes 舉例舉例 (cont.)(cont.)n參數(shù)計算：nP(well | E) = (0.9)(0.1)(0.1)(0.99)/P(E)=0.0089/P(E)nP(cold | E) = (0.05)(0.9)(0.8)(0.3)/P(E)=0.01/P(E)nP(allergy | E) = (0.05)(0.9)(0.7)(0.6)/P(E)=0.

35、019/P(E)n最大概率類: allergynP(E) = 0.089 + 0.01 + 0.019 = 0.0379nP(well | E) = 0.23nP(cold | E) = 0.26nP(allergy | E) = 0.50Play-tennis 例子: 估算 P(xi|C)Outlook Temperature Humidity Windy ClasssunnyhothighfalseNsunnyhothightrueNovercast hothighfalsePrainmildhighfalsePraincoolnormalfalsePraincoolnormaltrueN

36、overcast coolnormaltruePsunnymildhighfalseNsunnycoolnormalfalsePrainmildnormalfalsePsunnymildnormaltruePovercast mildhightruePovercast hotnormalfalsePrainmildhightrueNP(p) = 9/14P(n) = 5/14outlookP(sunny|p) = 2/9P(sunny|n) = 3/5P(overcast|p) = 4/9P(overcast|n) = 0P(rain|p) = 3/9P(rain|n) = 2/5temper

37、atureP(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/5正例反例Play-tennis例子: 分類 Xn例子 X = nP(X|p)P(p) = P(rain|p)P(hot|p)P(high

38、|p)P(false|p)P(p) = 3/92/93/96/99/14 = 0.010582nP(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.018286n樣本 X 被分到 n類，即“不適合打網(wǎng)球”討論討論n樸素的貝葉斯假定在一個位置上出現(xiàn)的詞的概樸素的貝葉斯假定在一個位置上出現(xiàn)的詞的概率獨立于另外一個位置的單詞，這個假定有時率獨立于另外一個位置的單詞，這個假定有時并不反映真實情況并不反映真實情況n雖然獨立性假設(shè)很不精確，別無選擇，否則計雖然獨立性假設(shè)很不精確，別無選擇，否則計算的概率項

39、將極為龐大算的概率項將極為龐大n幸運的是，在實踐中樸素貝葉斯學習器在許多幸運的是，在實踐中樸素貝葉斯學習器在許多文本分類中性能非常好，即使獨立性假設(shè)不成文本分類中性能非常好，即使獨立性假設(shè)不成立立K K近鄰近鄰 K K近鄰（近鄰（KNNKNN）n基本思想基本思想n給定一個經(jīng)過分類的訓練文檔集合，在對新文檔給定一個經(jīng)過分類的訓練文檔集合，在對新文檔（即測試文檔或待分類文檔）進行分類時，首先從（即測試文檔或待分類文檔）進行分類時，首先從訓練文檔集合中找出與測試文檔最相關(guān)的訓練文檔集合中找出與測試文檔最相關(guān)的k k篇文檔，篇文檔，然后按照這然后按照這k k篇文檔所屬的類別信息來對該測試文篇文檔所屬的

40、類別信息來對該測試文檔進行分類處理。檔進行分類處理。57文檔間的距離文檔間的距離n對于有對于有mm個特征屬性的文檔來說，個特征屬性的文檔來說，n n個文檔可以視為個文檔可以視為m-m-維維空間中的空間中的n n個點，自然地，可以設(shè)想用點間距離度量文檔個點，自然地，可以設(shè)想用點間距離度量文檔間的接近程度。常用間的接近程度。常用dijdij表示第表示第i i篇文檔與第篇文檔與第j j篇文檔間的距篇文檔間的距離。離。n n當當q q分別取分別取1 1，2 2和和時，明氏距離分別對應(yīng)于絕對值距離時，明氏距離分別對應(yīng)于絕對值距離、歐氏距離和切比雪夫距離。、歐氏距離和切比雪夫距離。qmkqjkikijww

41、qd11)()(KNNKNN算法算法n目標：基于訓練集目標：基于訓練集X X的對的對y y分類分類n在訓練集中，尋找和在訓練集中，尋找和y y最相似的訓練樣本最相似的訓練樣本x xn得到得到k k個最相似的集合個最相似的集合A,AA,A為為X X的一個子集的一個子集n設(shè)設(shè)n1,n2n1,n2分別為集合中屬于分別為集合中屬于c1,c2c1,c2的個數(shù)的個數(shù)n如果如果p(c1|y)p(c2|y),p(c1|y)p(c2|y),判為判為c1,c1,否則判為否則判為c2c2( )( , )MAXx NsimyMAXsim x ymax|( , )( )AxN sim x ysimy11(| )12np

42、 cynn22(| )12np cynnkNNkNN方法方法n一種基于實例的學習方法一種基于實例的學習方法新文本k=1, A類k=4，B類k=10，B類帶權(quán)重計算，計算權(quán)重和最大的類。帶權(quán)重計算，計算權(quán)重和最大的類。k k常取常取3 3或者或者5 5。KNNnkNNkNN分類法其分類法其優(yōu)點優(yōu)點不需要預(yù)先學習，分類精度不需要預(yù)先學習，分類精度較高，不存在漏識問題較高，不存在漏識問題n缺點缺點是分類速度與訓練文檔個數(shù)有關(guān)。對于每是分類速度與訓練文檔個數(shù)有關(guān)。對于每一個測試文檔，都必須求解它與訓練文檔庫中一個測試文檔，都必須求解它與訓練文檔庫中所有文檔的相似度，其時間復(fù)雜度為所有文檔的相似度，其時

43、間復(fù)雜度為OO（n1n1* *n2n2）。）。 相似度矩陣相似度矩陣n最近鄰方法依賴于相似度矩陣最近鄰方法依賴于相似度矩陣( (或距離或距離). ).n對連續(xù)對連續(xù)mm維空間最簡單的方法采用歐氏距維空間最簡單的方法采用歐氏距. .n對對mm維二值實例空間最簡單的方法是海明維二值實例空間最簡單的方法是海明距（絕對距離）距（絕對距離）. .n對于基于文本對于基于文本tf/idftf/idf權(quán)重向量的余弦相似度權(quán)重向量的余弦相似度是經(jīng)常被采用的是經(jīng)常被采用的. .影響影響KNNKNN的因素的因素nK K的取值的取值nK K一般取一般取1515n計算距離的方法計算距離的方法n歐式距離歐式距離n蘭式距離

44、（余弦相似度），分類質(zhì)量和分類效率較蘭式距離（余弦相似度），分類質(zhì)量和分類效率較高高n分類目錄中類別的層次關(guān)系分類目錄中類別的層次關(guān)系n基于層次模型的基于層次模型的KNNKNN分類比基本的分類比基本的KNNKNN效率高，效率高，但是效率也會有所下降但是效率也會有所下降KNNKNN和和NBNB比較比較n從表中看，從表中看，KNNKNN質(zhì)量較高，質(zhì)量較高，NBNB的效率較高的效率較高n從各個類別看，從各個類別看，KNNKNN比比NBNB穩(wěn)定，穩(wěn)定，NBNB對類別敏對類別敏感感文本聚類文本聚類Text Clustering聚類式搜索聚類式搜索聚類聚類n目的：目的：n發(fā)現(xiàn)與某文檔相似的一批文檔，發(fā)現(xiàn)相

45、關(guān)知識；發(fā)現(xiàn)與某文檔相似的一批文檔，發(fā)現(xiàn)相關(guān)知識； n導航，提供一種組織文檔集合的方法導航，提供一種組織文檔集合的方法 ；n生成用于文本自動分類的分類體系表生成用于文本自動分類的分類體系表 。n將無標記的樣本劃分到聚類的各個子集中將無標記的樣本劃分到聚類的各個子集中: :n類內(nèi)樣本非常相似類內(nèi)樣本非常相似n類間樣本非常不同類間樣本非常不同n無監(jiān)督方法發(fā)現(xiàn)新類別無監(jiān)督方法發(fā)現(xiàn)新類別.聚類樣例聚類樣例.層次聚類層次聚類n在無標注的樣本集合中建立在無標注的樣本集合中建立 樹狀層次分類結(jié)構(gòu)樹狀層次分類結(jié)構(gòu)n遞歸的標準層次聚類算法應(yīng)用生成層次聚類遞歸的標準層次聚類算法應(yīng)用生成層次聚類. .animalv

46、ertebratefish reptile amphib. mammal worm insect crustaceaninvertebrate會聚會聚vs. vs. 分裂聚類分裂聚類n會聚會聚( (bottom-upbottom-up) ) 以每個樣本獨自一類開以每個樣本獨自一類開始，迭代合并到越來越大的類中始，迭代合并到越來越大的類中n分裂分裂 ( (partitionalpartitional, top-down, top-down) ) 將所有樣本將所有樣本不斷劃分到類別中不斷劃分到類別中n不需要事先確定類別不需要事先確定類別n需要終止條件需要終止條件會聚層次聚類會聚層次聚類 (HAC)

47、(HAC)n設(shè)定相似度函數(shù)確定任意兩個實例的相似度設(shè)定相似度函數(shù)確定任意兩個實例的相似度n開始每個實例獨自一類開始每個實例獨自一類n然后重復(fù)合并最相似的類別，直到成為一類：然后重復(fù)合并最相似的類別，直到成為一類：n在當前的類別中，確定最近的兩類在當前的類別中，確定最近的兩類ci ci 和和cj cjn用單一的類別用單一的類別 ci ci cj cj取代取代 ci ci 和和 cj cjn合并的過程成為層次結(jié)構(gòu)合并的過程成為層次結(jié)構(gòu)系統(tǒng)樹圖系統(tǒng)樹圖: :d1d2d3d4d5d1,d2d4,d5d3d3,d4,d5 聚類相似度聚類相似度n設(shè)定一個相似度函數(shù)確定兩個實例的相似程度設(shè)定一個相似度函數(shù)確

48、定兩個實例的相似程度n文本向量的余弦相似度文本向量的余弦相似度n如何計算包含多個樣例的兩個類別的相似度？如何計算包含多個樣例的兩個類別的相似度？nSingle LinkSingle Link: : 兩個類別中最近成員的相似度兩個類別中最近成員的相似度nComplete LinkComplete Link: : 兩個類別中最遠成員的相似度兩個類別中最遠成員的相似度nGroup AverageGroup Average: : 成員間的平均相似度成員間的平均相似度計算類別間相似度計算類別間相似度n合并合并c ci i,c ,cj j后，計算該類和其他類的相似度后，計算該類和其他類的相似度可以如下計算

49、：可以如下計算：nSingle Link:Single Link:nComplete Link:Complete Link:),(),(max(),(kjkikjiccsimccsimcccsim),(),(min(),(kjkikjiccsimccsimcccsim單連通（單連通（Single LinkageSingle Linkage）全連通（全連通（Complete LinkageComplete Linkage）平均連通（平均連通（Average LinkageAverage Linkage） 計算復(fù)雜度計算復(fù)雜度n在第一次迭代中，在第一次迭代中，HACHAC方法需要計算所方法需要計算

50、所有樣例的每一對的距離有樣例的每一對的距離n在合并迭代中，需要計算新形成的類與在合并迭代中，需要計算新形成的類與其他類的距離其他類的距離n為了維持為了維持O(nO(n2 2) )的性能，計算類與類之間的性能，計算類與類之間的相似度需要的相似度需要常數(shù)時間常數(shù)時間平均連通凝聚聚類平均連通凝聚聚類n單連通容易導致狹長聚類，全連通的算單連通容易導致狹長聚類，全連通的算法復(fù)雜度為法復(fù)雜度為O(nO(n3 3) )n用合并后的類中所有對平均相似度度量用合并后的類中所有對平均相似度度量兩個類的相似度兩個類的相似度n是全連通和單連通的折中是全連通和單連通的折中. .)(: )(),() 1(1),(jiji

51、ccxxyccyjijijiyxsimccccccsim計算平均連通相似度計算平均連通相似度n設(shè)定余弦相似度及單位長度歸一化向量設(shè)定余弦相似度及單位長度歸一化向量. .n總是維持每個類別的向量和總是維持每個類別的向量和. .n計算類別相似度在常數(shù)時間內(nèi)計算類別相似度在常數(shù)時間內(nèi): :jcxjxcs)( ( )() ( ( )()(|)( ,)(|)(| 1)ijijijijijijs cs cs cs cccsim c ccccc非層次聚類非層次聚類(動態(tài)聚類動態(tài)聚類)n需要確定期望的類別數(shù)需要確定期望的類別數(shù)k kn隨機選擇隨機選擇k k個種子個種子 n進行初始聚類進行初始聚類n迭代，將樣例

52、重新劃分迭代，將樣例重新劃分n直到樣例所屬的類別不再改變直到樣例所屬的類別不再改變82動態(tài)聚類的核心問題n初始聚類中心的選取初始聚類中心的選取n重心法重心法n密度法密度法n調(diào)用等級聚類算法調(diào)用等級聚類算法n參數(shù)參數(shù)K K的設(shè)置的設(shè)置聚類中心的選擇聚類中心的選擇n聚類結(jié)果與聚類中心的選擇是相關(guān)的聚類結(jié)果與聚類中心的選擇是相關(guān)的n隨機選擇的聚類中心可能會導致收斂很隨機選擇的聚類中心可能會導致收斂很慢或者收斂到局部最優(yōu)慢或者收斂到局部最優(yōu)n采用啟發(fā)式方法或其他方法選擇好的聚采用啟發(fā)式方法或其他方法選擇好的聚類中心類中心84重心法n首先計算出全部聚類樣本的重心，把它作為第一凝聚點；首先計算出全部聚類樣

53、本的重心，把它作為第一凝聚點；n再選定一個正數(shù)，作為建立新凝聚點的最小臨界距離再選定一個正數(shù)，作為建立新凝聚點的最小臨界距離d d；n依次逐個輸入全部樣本，如果輸入樣本與已有凝聚點的距依次逐個輸入全部樣本，如果輸入樣本與已有凝聚點的距離大于離大于d d，則將它作為新凝聚點，否則就不作為凝聚點；，則將它作為新凝聚點，否則就不作為凝聚點；n直到把所有樣本處理完畢。直到把所有樣本處理完畢。85密度法密度法n先選定兩個正數(shù)先選定兩個正數(shù)d1d1和和d2d2，然后，以樣本空間的每個樣本點為，然后，以樣本空間的每個樣本點為中心，以中心，以d1d1為半徑做超維球，落在該球內(nèi)的樣本數(shù)（不包括為半徑做超維球，落在該球內(nèi)的樣本數(shù)（不包括中心樣本在內(nèi)）就稱為該