第六章文本分類(lèi)與聚類(lèi)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、有本質(zhì)的區(qū)別，它們都是想得到某種規(guī)律性的東西來(lái)指導(dǎo)分類(lèi)，統(tǒng)計(jì)方法得到的數(shù)學(xué)表達(dá)式可以認(rèn)為律性的東西來(lái)指導(dǎo)分類(lèi)，統(tǒng)計(jì)方法得到的數(shù)學(xué)表達(dá)式可以認(rèn)為是某種隱式規(guī)則。是某種隱式規(guī)則。n在目前的文本分類(lèi)當(dāng)中，統(tǒng)計(jì)方法占據(jù)了主流地位。在目前的文本分類(lèi)當(dāng)中，統(tǒng)計(jì)方法占據(jù)了主流地位。分類(lèi)的評(píng)測(cè)分類(lèi)的評(píng)測(cè)n偶然事件表（偶然事件表（Contingency TableContingency Table）n對(duì)一個(gè)分類(lèi)器的度量對(duì)一個(gè)分類(lèi)器的度量n準(zhǔn)確率準(zhǔ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)屬于此類(lèi)不屬于此類(lèi)判定屬于此類(lèi)AB判定不屬于此類(lèi)CDBEPBEP和和F F測(cè)度測(cè)度nBEPBEP（break-even pointbreak-even point）n當(dāng)準(zhǔn)確率和召回率相等時(shí)的值即為當(dāng)準(zhǔn)確率和召回率相等時(shí)的值即為BEPBEPnF F測(cè)度，取測(cè)度，取=1 =1 nBEPBEP和和F F測(cè)度的值越大，則表示分類(lèi)器的性能越測(cè)度的值越大，則表示分類(lèi)器的性能越好。好。nBEPBEP只是只是F1F1所有可能取值中的一個(gè)特定值（當(dāng)所有可能取值中的一個(gè)特定值（當(dāng)p p =

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

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

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

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

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

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

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

25、是已知一個(gè)詞信息增益計(jì)算的是已知一個(gè)詞t t是否出現(xiàn)在一份文本中對(duì)于是否出現(xiàn)在一份文本中對(duì)于類(lèi)別預(yù)測(cè)有多少信息。類(lèi)別預(yù)測(cè)有多少信息。n這里的定義是一個(gè)更一般的、針對(duì)多個(gè)類(lèi)別的定義。這里的定義是一個(gè)更一般的、針對(duì)多個(gè)類(lèi)別的定義?；バ畔ⅲɑバ畔ⅲ∕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)計(jì)量（統(tǒng)計(jì)量（CHICHI）：）：n 2 2統(tǒng)計(jì)量的定義可以從一個(gè)詞統(tǒng)計(jì)量的定義可以從一個(gè)詞t t與一個(gè)類(lèi)別與一個(gè)類(lèi)別c c的的偶然事件表引出（假設(shè)文本的總數(shù)為偶然事件表引出（假設(shè)文本的總數(shù)為N N ）n度量?jī)烧叨攘績(jī)烧?term(term和類(lèi)別和類(lèi)別) )獨(dú)立性程度獨(dú)立性程度n 2 2 越大，獨(dú)立性越小，相關(guān)性越大越大，獨(dú)立性越小，相關(guān)性越大n若若ADBC,ADBC,則類(lèi)和詞獨(dú)立則類(lèi)和詞獨(dú)立, 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性能相當(dāng)性能相當(dāng)nDFDF具有算法簡(jiǎn)單，質(zhì)量高的優(yōu)點(diǎn)，可以具有算法簡(jiǎn)單，質(zhì)量高的優(yōu)點(diǎn)，可以替代替代CHICHI，IGIG分類(lèi)器學(xué)習(xí)分類(lèi)器學(xué)習(xí)n訓(xùn)練樣本實(shí)例：訓(xùn)練樣本實(shí)例：)n一個(gè)文本實(shí)例一個(gè)文本實(shí)例 x x X Xn帶

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

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

30、設(shè)各個(gè)類(lèi)別的集合為設(shè)各個(gè)類(lèi)別的集合為 c c1 1, , c c2 2, ,c cn n n設(shè)設(shè)E E為實(shí)例的描述為實(shí)例的描述n確定確定E E的類(lèi)別的類(lèi)別nP(P(E E) ) 可以根據(jù)下式確定可以根據(jù)下式確定)()|()()|(EPcEPcPEcPiiiniiiniiEPcEPcPEcP111)()|()()|(niiicEPcPEP1)|()()(貝葉斯分類(lèi)貝葉斯分類(lèi)(cont.)(cont.)n需要知道需要知道: :n先驗(yàn)概率先驗(yà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| |樸素的貝葉斯分類(lèi)樸素的貝葉斯分類(lèi)n如果假定樣例的特征是獨(dú)立的，可以寫(xiě)為：如果假定樣例的特征是獨(dú)立的，可以寫(xiě)為：n因此，只需要知道每個(gè)特征和類(lèi)別的因此，只需要知道每個(gè)特征和類(lèi)別的P(P(e ej j | | c ci i) ) n如果只計(jì)算單個(gè)特征的分布，大大地減少了如果只計(jì)算單個(gè)特征的分布，大大地減少了計(jì)算量計(jì)算量)|()|()|(121mjijimicePceeePcEP文本分類(lèi)文本分類(lèi) NaNa ve v

32、e BayesBayes算法算法( (訓(xùn)練訓(xùn)練) )設(shè)設(shè)V V為文檔集合為文檔集合D D所有詞詞表所有詞詞表對(duì)每個(gè)類(lèi)別對(duì)每個(gè)類(lèi)別 c ci i C C D Di i 是文檔是文檔D D中類(lèi)別中類(lèi)別C Ci i的文檔集合的文檔集合 P(P(c ci i) = |) = |D Di i| / | / |D D| |設(shè)設(shè) n ni i 為為D Di i中詞的總數(shù)中詞的總數(shù) 對(duì)每個(gè)詞對(duì)每個(gè)詞 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文本分類(lèi)文本分類(lèi) NaNa ve ve BayesBayes算法算法( (測(cè)試測(cè)試) )n給定測(cè)試文檔給定測(cè)試文檔 X Xn設(shè)設(shè) n n 為為X X中詞的個(gè)數(shù)中詞的個(gè)數(shù)n返回的類(lèi)別返回的類(lèi)別: :nwwi i是是X X中第中第i i個(gè)位置的詞個(gè)位置的詞)|()(argmax1niiiiCiccwPcPNaNa ve ve BayesBayes分類(lèi)舉例分類(lèi)舉例nC = allergy, cold, wellne1 = sneeze; e2 = cough; e3 = fevern當(dāng)前實(shí)例是：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過(guò)敏打噴嚏NaNa ve ve BayesBayes 舉例舉例 (cont.)(cont.)n參數(shù)計(jì)算：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最大概率類(lèi): 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例子: 分類(lèi) 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類(lèi)，即“不適合打網(wǎng)球”討論討論n樸素的貝葉斯假定在一個(gè)位置上出現(xiàn)的詞的概樸素的貝葉斯假定在一個(gè)位置上出現(xiàn)的詞的概率獨(dú)立于另外一個(gè)位置的單詞，這個(gè)假定有時(shí)率獨(dú)立于另外一個(gè)位置的單詞，這個(gè)假定有時(shí)并不反映真實(shí)情況并不反映真實(shí)情況n雖然獨(dú)立性假設(shè)很不精確，別無(wú)選擇，否則計(jì)雖然獨(dú)立性假設(shè)很不精確，別無(wú)選擇，否則計(jì)算的概率項(xiàng)

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

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

41、qd11)()(KNNKNN算法算法n目標(biāo)：基于訓(xùn)練集目標(biāo)：基于訓(xùn)練集X X的對(duì)的對(duì)y y分類(lèi)分類(lèi)n在訓(xùn)練集中，尋找和在訓(xùn)練集中，尋找和y y最相似的訓(xùn)練樣本最相似的訓(xùn)練樣本x xn得到得到k k個(gè)最相似的集合個(gè)最相似的集合A,AA,A為為X X的一個(gè)子集的一個(gè)子集n設(shè)設(shè)n1,n2n1,n2分別為集合中屬于分別為集合中屬于c1,c2c1,c2的個(gè)數(shù)的個(gè)數(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一種基于實(shí)例的學(xué)習(xí)方法一種基于實(shí)例的學(xué)習(xí)方法新文本k=1, A類(lèi)k=4，B類(lèi)k=10，B類(lèi)帶權(quán)重計(jì)算，計(jì)算權(quán)重和最大的類(lèi)。帶權(quán)重計(jì)算，計(jì)算權(quán)重和最大的類(lèi)。k k常取常取3 3或者或者5 5。KNNnkNNkNN分類(lèi)法其分類(lèi)法其優(yōu)點(diǎn)優(yōu)點(diǎn)不需要預(yù)先學(xué)習(xí)，分類(lèi)精度不需要預(yù)先學(xué)習(xí)，分類(lèi)精度較高，不存在漏識(shí)問(wèn)題較高，不存在漏識(shí)問(wèn)題n缺點(diǎn)缺點(diǎn)是分類(lèi)速度與訓(xùn)練文檔個(gè)數(shù)有關(guān)。對(duì)于每是分類(lèi)速度與訓(xùn)練文檔個(gè)數(shù)有關(guān)。對(duì)于每一個(gè)測(cè)試文檔，都必須求解它與訓(xùn)練文檔庫(kù)中一個(gè)測(cè)試文檔，都必須求解它與訓(xùn)練文檔庫(kù)中所有文檔的相似度，其時(shí)間復(fù)雜度為所有文檔的相似度，其時(shí)

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

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

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

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

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

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

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

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

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

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

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