06文本分類與聚類課件

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

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

TB類一般工業(yè)技術(shù)TD類礦業(yè)工程TE類石油、天然氣工業(yè)TF類冶金工業(yè)TG類金屬學(xué)、金屬工藝TH類機(jī)械、儀表工藝TJ類武器工業(yè)TK類動(dòng)力工業(yè)TL類原子能技術(shù)TM類電工技術(shù)TN類無(wú)線電電子學(xué)、電信技術(shù)TP類自動(dòng)化技術(shù)、計(jì)算技術(shù)TQ類化學(xué)工業(yè)TS類輕工業(yè)、手工業(yè)TU類建筑科學(xué)TV類水利工程中圖分類法A類馬列主義、毛澤東思想T

系統(tǒng)結(jié)構(gòu)標(biāo)注工具機(jī)器學(xué)習(xí)工具模型數(shù)據(jù)標(biāo)注的樣本分類工具類別預(yù)處理預(yù)處理訓(xùn)練數(shù)據(jù)文本新數(shù)據(jù)文本系統(tǒng)結(jié)構(gòu)標(biāo)注工具機(jī)器學(xué)習(xí)工具模型數(shù)據(jù)標(biāo)注的樣本分類工具M(jìn)ultimediaGUIGarb.Coll.SemanticsMLPgrammingsemanticslanguageproof...learningintelligencealgorithmreinforcementnetwork...garbagecollectionmemoryoptimizationregion...“planninglanguageproofintelligence”訓(xùn)練數(shù)據(jù)測(cè)試數(shù)據(jù)類別(AI)文本分類示例(Programming)(HCI)......MultimediaGUIGarb.Coll.Semanti分類的一般過(guò)程收集訓(xùn)練集和測(cè)試集，對(duì)文本進(jìn)行預(yù)處理對(duì)文本進(jìn)行特征提取分類器訓(xùn)練（學(xué)習(xí)）測(cè)試與評(píng)價(jià)精確率、召回率、F1宏平均，微平均分類的一般過(guò)程收集訓(xùn)練集和測(cè)試集，對(duì)文本進(jìn)行預(yù)處理分類的評(píng)測(cè)偶然事件表（ContingencyTable）對(duì)一個(gè)分類器的度量準(zhǔn)確率(precision)=a/(a+b)召回率(recall)=a/(a+c)fallout=b/(b+d)屬于此類不屬于此類判定屬于此類AB判定不屬于此類CD分類的評(píng)測(cè)偶然事件表（ContingencyTable）屬BEP和F測(cè)度BEP（break-evenpoint）當(dāng)準(zhǔn)確率和召回率相等時(shí)的值即為BEPF測(cè)度，取β=1BEP和F測(cè)度的值越大，則表示分類器的性能越好。BEP只是F1所有可能取值中的一個(gè)特定值（當(dāng)p=r時(shí)），因此BEP小于或等于F1的最大值。BEP和F測(cè)度BEP（break-evenpoint）多類分類問(wèn)題的評(píng)價(jià)宏平均（macro-averaging）先對(duì)每個(gè)分類器計(jì)算上述量度，再對(duì)所有分類器求平均是關(guān)于類別的均值微平均（micro-averaging）先合并所有分類器的偶然事件表中的各元素，得到一個(gè)總的偶然事件表，再由此表計(jì)算各種量度。是關(guān)于文本的均值多類分類問(wèn)題的評(píng)價(jià)宏平均（macro-averaging）收集訓(xùn)練數(shù)據(jù)TREC提供統(tǒng)一的訓(xùn)練集和測(cè)試集進(jìn)行系統(tǒng)評(píng)測(cè)國(guó)外：CMU,BERKLEY,CORNELL國(guó)內(nèi)：中科院計(jì)算所，清華大學(xué)，復(fù)旦大學(xué)后續(xù)增加了網(wǎng)頁(yè)語(yǔ)料和中文文本但是中文文本是新華社的新聞稿，與網(wǎng)頁(yè)的分類體系還有差別收集訓(xùn)練數(shù)據(jù)TREC提供統(tǒng)一的訓(xùn)練集和測(cè)試集進(jìn)行系統(tǒng)評(píng)測(cè)目前已有的評(píng)測(cè)語(yǔ)料有指導(dǎo)的機(jī)器學(xué)習(xí)方法是實(shí)現(xiàn)中文網(wǎng)頁(yè)自動(dòng)分類的基礎(chǔ)，因此訓(xùn)練集是實(shí)現(xiàn)分類的前提條件已有訓(xùn)練語(yǔ)料863評(píng)測(cè)語(yǔ)料(中圖分類)搜狗語(yǔ)料復(fù)旦語(yǔ)料目前已有的評(píng)測(cè)語(yǔ)料有指導(dǎo)的機(jī)器學(xué)習(xí)方法是實(shí)現(xiàn)中文網(wǎng)頁(yè)自動(dòng)分類訓(xùn)練語(yǔ)料分類體系中圖分類體系處理對(duì)象是圖書，不適合網(wǎng)頁(yè)分類學(xué)科分類與代碼1992年制定，時(shí)間過(guò)久，包括一些過(guò)時(shí)類別上述兩個(gè)分類標(biāo)準(zhǔn)都不能直接用做中文網(wǎng)頁(yè)的分類中文網(wǎng)頁(yè)的分類體系訓(xùn)練語(yǔ)料分類體系中圖分類體系一種中文網(wǎng)頁(yè)的分類體系一種中文網(wǎng)頁(yè)的分類體系訓(xùn)練集的大小通過(guò)不斷增加實(shí)例的個(gè)數(shù)，考察每個(gè)類訓(xùn)練樣本對(duì)分類器質(zhì)量的影響宏觀F1微觀F1訓(xùn)練集的大小通過(guò)不斷增加實(shí)例的個(gè)數(shù)，考察每個(gè)類訓(xùn)練樣本對(duì)分類網(wǎng)頁(yè)預(yù)處理去掉網(wǎng)頁(yè)中的導(dǎo)航信息去掉HTML網(wǎng)頁(yè)中的tag標(biāo)記(中文)分詞、詞性標(biāo)注、短語(yǔ)識(shí)別、…去除停用詞和詞根還原(stemming)數(shù)據(jù)清洗：去掉不合適的噪聲文檔或文檔內(nèi)垃圾數(shù)據(jù)網(wǎng)頁(yè)預(yù)處理去掉網(wǎng)頁(yè)中的導(dǎo)航信息特征提取特征提取特征提取(FeatureSelection)在文本分類問(wèn)題中遇到的一個(gè)主要困難就是高維的特征空間通常一份普通的文本在經(jīng)過(guò)文本表示后，如果以詞為特征，它的特征空間維數(shù)將達(dá)到幾千，甚至幾萬(wàn)大多數(shù)學(xué)習(xí)算法都無(wú)法處理如此大的維數(shù)為了能夠在保證分類性能的前提下，自動(dòng)降低特征空間的維數(shù)，在許多文本分類系統(tǒng)的實(shí)現(xiàn)中都引入了特征提取方法特征提取(FeatureSelection)在文本分類問(wèn)題舉例對(duì)每類構(gòu)造k

個(gè)最有區(qū)別能力的term例如：計(jì)算機(jī)領(lǐng)域：主機(jī)、芯片、內(nèi)存、編譯

…汽車領(lǐng)域:

輪胎，方向盤，底盤，氣缸，…舉例對(duì)每類構(gòu)造k個(gè)最有區(qū)別能力的term用文檔頻率選特征文檔頻率DF(DocumentFrequency)DFi：所有文檔集合中出現(xiàn)特征i的文檔數(shù)目基本假設(shè)：稀少的詞或者對(duì)于目錄預(yù)測(cè)沒(méi)有幫助，或者不會(huì)影響整體性能。實(shí)現(xiàn)方法：先計(jì)算所有詞的DF，然后刪除所有DF小于某個(gè)閾值的詞，從而降低特征空間的維數(shù)。優(yōu)缺點(diǎn)：最簡(jiǎn)單的降低特征空間維數(shù)的方法稀少的詞具有更多的信息，因此不宜用DF大幅度地刪除詞用文檔頻率選特征文檔頻率詞的熵term的熵該值越大，說(shuō)明分布越均勻，越有可能出現(xiàn)在較多的類別中；該值越小，說(shuō)明分布越傾斜，詞可能出現(xiàn)在較少的類別中詞的熵term的熵信息增益(InformationGain,IG)t出現(xiàn)的概率t不出現(xiàn)假定t出現(xiàn)時(shí)取第i

個(gè)類別的概率取第i

個(gè)類別時(shí)的概率該term為整個(gè)分類所能提供的信息量不考慮任何特征的熵和考慮該特征后的熵的差值信息增益計(jì)算的是已知一個(gè)詞t是否出現(xiàn)在一份文本中對(duì)于類別預(yù)測(cè)有多少信息。這里的定義是一個(gè)更一般的、針對(duì)多個(gè)類別的定義。信息增益(InformationGain,IG)t出現(xiàn)互信息（MutualInformation）互信息(MutualInformation)：MI越大t和c共現(xiàn)程度越大互信息的定義與交叉熵近似，只是互信息不考慮t不出現(xiàn)的概率，它的定義為：互信息（MutualInformation）互信息(Mutχ2統(tǒng)計(jì)量（CHI）：2統(tǒng)計(jì)量的定義可以從一個(gè)詞t與一個(gè)類別c的偶然事件表引出（假設(shè)文本的總數(shù)為N）度量?jī)烧?term和類別)獨(dú)立性程度χ2

越大，獨(dú)立性越小，相關(guān)性越大若AD<BC,則類和詞獨(dú)立,N=A+B+C+DABCDt~tc~cχ2統(tǒng)計(jì)量（CHI）：2統(tǒng)計(jì)量的定義可以從一個(gè)詞t與一個(gè)類特征提取方法的性能比較(Macro-F1)特征提取方法的性能比較(Macro-F1)特征提取方法的性能比較(Micro-F1)特征提取方法的性能比較(Micro-F1)結(jié)論可以看出CHI，IG，DF性能好于MIMI最差CHI，IG，DF性能相當(dāng)DF具有算法簡(jiǎn)單，質(zhì)量高的優(yōu)點(diǎn)，可以替代CHI，IG結(jié)論可以看出CHI，IG，DF性能好于MI分類器學(xué)習(xí)訓(xùn)練樣本實(shí)例：<x,c(x)>一個(gè)文本實(shí)例xX帶有正確的類別標(biāo)記c(x)學(xué)習(xí)的過(guò)程是在給定訓(xùn)練樣本集合D

的前提下，尋找一個(gè)分類函數(shù)h(x),使得:分類器學(xué)習(xí)訓(xùn)練樣本實(shí)例：<x,c(x)>貝葉斯分類貝葉斯分類貝葉斯分類基于概率理論的學(xué)習(xí)和分類方法貝葉斯理論在概率學(xué)習(xí)及分類中充當(dāng)重要角色僅使用每類的先驗(yàn)概率不能對(duì)待分的文本提供信息分類是根據(jù)給定樣本描述的可能的類別基礎(chǔ)上產(chǎn)生的后驗(yàn)概率分布貝葉斯分類基于概率理論的學(xué)習(xí)和分類方法貝葉斯理論得到：由條件概率的定義：貝葉斯理論得到：由條件概率的定義：貝葉斯分類設(shè)各個(gè)類別的集合為{c1,c2,…cn}設(shè)E為實(shí)例的描述確定E的類別P(E)可以根據(jù)下式確定貝葉斯分類設(shè)各個(gè)類別的集合為{c1,c2,…cn}貝葉斯分類(cont.)需要知道:先驗(yàn)概率:P(ci)條件概率:P(E|ci)P(ci)容易從數(shù)據(jù)中獲得如果文檔集合D中，屬于ci的樣例數(shù)為ni則有 P(ci)=ni/|D|假設(shè)樣例的特征是關(guān)聯(lián)的:指數(shù)級(jí)的估計(jì)所有的P(E|ci)貝葉斯分類(cont.)需要知道:樸素的貝葉斯分類如果假定樣例的特征是獨(dú)立的，可以寫為：因此，只需要知道每個(gè)特征和類別的P(ej|ci)如果只計(jì)算單個(gè)特征的分布，大大地減少了計(jì)算量樸素的貝葉斯分類如果假定樣例的特征是獨(dú)立的，可以寫為：文本分類Na?veBayes算法(訓(xùn)練)設(shè)V為文檔集合D所有詞詞表對(duì)每個(gè)類別ci

CDi是文檔D中類別Ci的文檔集合

P(ci)=|Di|/|D|設(shè)ni為Di中詞的總數(shù)對(duì)每個(gè)詞

wjV

令nij

為Di中wij的數(shù)量

P(wi|ci)=(nij+1)/(ni+|V|)文本分類Na?veBayes算法(訓(xùn)練)設(shè)V為文檔集合D文本分類Na?veBayes算法(測(cè)試)給定測(cè)試文檔X設(shè)n

為X中詞的個(gè)數(shù)返回的類別:wi是X中第i個(gè)位置的詞文本分類Na?veBayes算法(測(cè)試)給定測(cè)試文檔XNa?veBayes分類舉例C={allergy,cold,well}e1=sneeze;e2=cough;e3=fever當(dāng)前實(shí)例是：E={sneeze,cough,fever}ProbWellColdAllergyP(ci)0.90.050.05P(sneeze|ci)P(cough|ci)P(fever|ci)0.010.70.4過(guò)敏打噴嚏Na?veBayes分類舉例C={allergy,cNa?veBayes舉例(cont.)參數(shù)計(jì)算：P(well|E)=(0.9)(0.1)(0.1)(0.99)/P(E)=0.0089/P(E)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.50Na?veBayes舉例(cont.)參數(shù)計(jì)算：Play-tennis例子:估算P(xi|C)P(p)=9/14P(n)=5/14Play-tennis例子:估算P(xi|C)P(p)outlookP(sunny|p)=2/9P(sunny|n)=3/5P(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/5正例反例outlookP(sunny|p)=2/9P(sunnyPlay-tennis例子:分類X例子X(jué)=<rain,hot,high,false>P(X|p)·P(p)=

P(rain|p)·P(hot|p)·P(high|p)·P(false|p)·P(p)=3/9·2/9·3/9·6/9·9/14=0.010582P(X|n)·P(n)=

P(rain|n)·P(hot|n)·P(high|n)·P(false|n)·P(n)=2/5·2/5·4/5·2/5·5/14=0.018286樣本X被分到n類，即“不適合打網(wǎng)球”Play-tennis例子:分類X例子X(jué)=<rai舉例在Joachims(1996)的一個(gè)實(shí)驗(yàn)中，被應(yīng)用于分類新聞組文章20個(gè)電子新聞組，每個(gè)新聞組1000篇文章，形成2萬(wàn)個(gè)文檔的數(shù)據(jù)集2/3作訓(xùn)練集，1/3作測(cè)試集衡量性能20個(gè)新聞組，隨機(jī)猜測(cè)的分類精確度5%，由程序獲得的精確度89%舉例在Joachims(1996)的一個(gè)實(shí)驗(yàn)中，被應(yīng)用于分類討論樸素的貝葉斯假定在一個(gè)位置上出現(xiàn)的詞的概率獨(dú)立于另外一個(gè)位置的單詞，這個(gè)假定有時(shí)并不反映真實(shí)情況雖然獨(dú)立性假設(shè)很不精確，別無(wú)選擇，否則計(jì)算的概率項(xiàng)將極為龐大幸運(yùn)的是，在實(shí)踐中樸素貝葉斯學(xué)習(xí)器在許多文本分類中性能非常好，即使獨(dú)立性假設(shè)不成立討論樸素的貝葉斯假定在一個(gè)位置上出現(xiàn)的詞的概率獨(dú)立于另外一個(gè)K近鄰K近鄰K近鄰（KNN）最近鄰分類規(guī)則

對(duì)于測(cè)試樣本點(diǎn)x，在集合中距離它最近的的x1。最近鄰分類就是把x分為x1所屬的類別最近鄰規(guī)則的推廣-KNN沒(méi)有好的相似度矩陣不能用KNNK近鄰（KNN）最近鄰分類規(guī)則KNN算法目標(biāo)：基于訓(xùn)練集X的對(duì)y分類在訓(xùn)練集中，尋找和y最相似的訓(xùn)練樣本x得到k個(gè)最相似的集合A,A為X的一個(gè)子集設(shè)n1,n2分別為集合中屬于c1,c2的個(gè)數(shù)如果p(c1|y)>p(c2|y),判為c1,否則判為c2KNN算法目標(biāo)：基于訓(xùn)練集X的對(duì)y分類kNN方法一種基于實(shí)例的學(xué)習(xí)方法新文本k=1,A類k=4，B類k=10，B類帶權(quán)重計(jì)算，計(jì)算權(quán)重和最大的類。k常取3或者5。kNN方法一種基于實(shí)例的學(xué)習(xí)方法新文本k=1,A類k=4，KNN在文本分類中的應(yīng)用KNN在文本分類中的應(yīng)用KNN分類錯(cuò)誤是由于：?jiǎn)蝹€(gè)的非典型樣例單個(gè)訓(xùn)練樣本的噪音.更魯棒的方法是發(fā)現(xiàn)k個(gè)最相似的樣本，返回k個(gè)樣本最主要的類別KNN分類錯(cuò)誤是由于：相似度矩陣最近鄰方法依賴于相似度矩陣(或距離).對(duì)連續(xù)m維空間最簡(jiǎn)單的方法采用歐氏距.對(duì)m維二值實(shí)例空間最簡(jiǎn)單的方法是海明距.對(duì)于基于文本tf/idf權(quán)重向量的余弦相似度是經(jīng)常被采用的.相似度矩陣最近鄰方法依賴于相似度矩陣(或距離).影響KNN的因素K的取值K一般取15計(jì)算距離的方法歐式距離蘭式距離（余弦相似度）影響KNN的因素K的取值KNN和NB比較從表中看，KNN質(zhì)量較高，NB的效率較高從各個(gè)類別看，KNN比NB穩(wěn)定，NB對(duì)類別敏感KNN和NB比較決策樹(shù)決策樹(shù)簡(jiǎn)介決策樹(shù)方法的起源是概念學(xué)習(xí)系統(tǒng)CLS，然后發(fā)展到ID3方法而為高潮，最后又演化為能處理連續(xù)屬性的C4.5。有名的決策樹(shù)方法還有CART和Assistant應(yīng)用最廣的歸納推理算法之一一種逼近離散值目標(biāo)函數(shù)的方法簡(jiǎn)介決策樹(shù)方法的起源是概念學(xué)習(xí)系統(tǒng)CLS，然后發(fā)展到ID3方?jīng)Q策樹(shù)的表示法決策樹(shù)通過(guò)把實(shí)例從根節(jié)點(diǎn)排列到某個(gè)葉子節(jié)點(diǎn)來(lái)分類實(shí)例，葉子節(jié)點(diǎn)即為實(shí)例所屬的分類。樹(shù)上的每一個(gè)節(jié)點(diǎn)說(shuō)明了對(duì)實(shí)例的某個(gè)屬性的測(cè)試，并且該節(jié)點(diǎn)的每一個(gè)后繼分支對(duì)應(yīng)于該屬性的一個(gè)可能值決策樹(shù)的表示法決策樹(shù)通過(guò)把實(shí)例從根節(jié)點(diǎn)排列到某個(gè)葉子節(jié)點(diǎn)來(lái)分決策樹(shù)表示舉例決策樹(shù)表示舉例表達(dá)式表達(dá)式?jīng)Q策樹(shù)學(xué)習(xí)的適用問(wèn)題實(shí)例是由屬性-值對(duì)表示的目標(biāo)函數(shù)具有離散的輸出值可能需要析取的描述訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例決策樹(shù)學(xué)習(xí)的適用問(wèn)題實(shí)例是由屬性-值對(duì)表示的屬性選擇構(gòu)造好的決策樹(shù)的關(guān)鍵在于如何選擇好的邏輯判斷或?qū)傩?。?duì)于同樣一組例子，可以有很多決策樹(shù)能符合這組例子。一般情況下或具有較大概率地說(shuō)，樹(shù)越小則樹(shù)的預(yù)測(cè)能力越強(qiáng)。要構(gòu)造盡可能小的決策樹(shù)，關(guān)鍵在于選擇恰當(dāng)?shù)倪壿嬇袛嗷驅(qū)傩?。由于?gòu)造最小的樹(shù)是NP-難問(wèn)題，因此只能采取用啟發(fā)式策略選擇好的邏輯判斷或?qū)傩?/p>

屬性選擇構(gòu)造好的決策樹(shù)的關(guān)鍵在于如何選擇好的邏輯判斷或?qū)傩?。用熵度量樣例的均一性（純度）熵的定義舉例用熵度量樣例的均一性（純度）熵的定義關(guān)于某布爾分類的熵函數(shù)關(guān)于某布爾分類的熵函數(shù)用信息增益度量期望熵最低一個(gè)屬性的信息增益就是由于使用這個(gè)屬性分割樣例而導(dǎo)致的期望熵的降低用信息增益度量期望熵最低一個(gè)屬性的信息增益就是由于使用這個(gè)屬舉例舉例計(jì)算信息增益計(jì)算信息增益確定最佳分類的屬性哪一個(gè)屬性是最好的分類？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確定最佳分類的屬性哪一個(gè)屬性是最好的分類？S:[9+,5-]不同屬性的信息增益計(jì)算各屬性的熵值Gain(S,Outlook)=0.246Gain(S,Humidity)=0.151Gain(S,Wind)=0.048Gain(S,Temperature)=0.029可以看到，Outlook得信息增益最大不同屬性的信息增益計(jì)算各屬性的熵值D1,D2,…D149+,5-OutlookSunnyD1,D2,D8,D9,D112+,3-RainD4,D5,D6,D10,D143+,2-D3,D7,D12,D134+,0-Overcast?哪一個(gè)屬性在這里被測(cè)試？Ssunny={D1,D2,D8,D9,D11}Gain（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,Wind)=0.970-(2/5)1.0-(3/5)0.918=0.019?YesD1,D2,…D14OutlookSunnyD1,D2,D8ID3算法創(chuàng)建樹(shù)的Root結(jié)點(diǎn)開(kāi)始

AAttributes中分類能力最好的屬性

Root的決策屬性A

對(duì)于每個(gè)可能值vi

在Root下加一個(gè)新的分支對(duì)應(yīng)測(cè)試A=vi

令Examplesvi為Examples中滿足A屬性值為vi的子集 如果Examplesvi為空 在這個(gè)新分支下加一個(gè)葉子結(jié)點(diǎn)，節(jié)點(diǎn)的lable=Examples中最普遍的目標(biāo)屬性值(target-attribute)

否則在這個(gè)新分支下加一個(gè)子樹(shù)ID3(examplevi,target- attribute,attributes-{A})返回RootID3算法創(chuàng)建樹(shù)的Root結(jié)點(diǎn)C4.5C4.5是對(duì)ID3的改進(jìn)算法對(duì)連續(xù)值的處理對(duì)未知特征值的處理對(duì)決策樹(shù)進(jìn)行剪枝規(guī)則的派生C4.5C4.5是對(duì)ID3的改進(jìn)算法決策樹(shù)學(xué)習(xí)的常見(jiàn)問(wèn)題過(guò)度擬合數(shù)據(jù)基本的決策樹(shù)構(gòu)造算法沒(méi)有考慮噪聲，生成的決策樹(shù)完全與訓(xùn)練例子擬合有噪聲情況下，完全擬合將導(dǎo)致過(guò)分?jǐn)M合（overfitting），即對(duì)訓(xùn)練數(shù)據(jù)的完全擬合反而不具有很好的預(yù)測(cè)性能

決策樹(shù)學(xué)習(xí)的常見(jiàn)問(wèn)題過(guò)度擬合數(shù)據(jù)解決方法剪枝是一種克服噪聲的技術(shù)，同時(shí)它也能使樹(shù)得到簡(jiǎn)化而變得更容易理解。向前剪枝（forwardpruning）向后剪枝（backwardpruning）

理論上講，向后剪枝好于向前剪枝，但計(jì)算復(fù)雜度大。剪枝過(guò)程中一般要涉及一些統(tǒng)計(jì)參數(shù)或閾值，如停機(jī)閾值有人提出了一種和統(tǒng)計(jì)參數(shù)無(wú)關(guān)的基于最小描述長(zhǎng)度（MDL）的有效剪枝法解決方法剪枝是一種克服噪聲的技術(shù)，同時(shí)它也能使樹(shù)得到簡(jiǎn)化而變決策樹(shù)的優(yōu)點(diǎn)可以生成可以理解的規(guī)則計(jì)算量相對(duì)來(lái)說(shuō)不是很大可以處理連續(xù)和離散字段決策樹(shù)可以清晰的顯示哪些字段比較重要過(guò)程可見(jiàn)

決策樹(shù)的優(yōu)點(diǎn)可以生成可以理解的規(guī)則不足之處對(duì)連續(xù)性的字段比較難預(yù)測(cè)當(dāng)類別太多時(shí)，錯(cuò)誤可能會(huì)增加的比較快一般的算法分類的時(shí)候，只是根據(jù)一個(gè)屬性來(lái)分類。不是全局最優(yōu)

不足之處對(duì)連續(xù)性的字段比較難預(yù)測(cè)文本分類的應(yīng)用新聞出版按照欄目分類類別{政治,體育,軍事,…}網(wǎng)頁(yè)分類類似于Yahoo的分類個(gè)性化新聞智能推薦垃圾郵件過(guò)濾類別{spam,not-spam}文本分類的應(yīng)用新聞出版按照欄目分類

文本聚類

TextClustering

文本聚類

TextClustering聚類式搜索聚類式搜索聚類式搜索聚類式搜索聚類將無(wú)標(biāo)記的樣本劃分到聚類的各個(gè)子集中:類內(nèi)樣本非常相似類間樣本非常不同無(wú)監(jiān)督方法發(fā)現(xiàn)新類別聚類.聚類樣例................................聚類樣例.........................層次聚類在無(wú)標(biāo)注的樣本集合中建立樹(shù)狀層次分類結(jié)構(gòu)遞歸的標(biāo)準(zhǔn)層次聚類算法應(yīng)用生成層次聚類.animalvertebratefishreptileamphib.mammalworminsectcrustaceaninvertebrate層次聚類在無(wú)標(biāo)注的樣本集合中建立樹(shù)狀層次分類結(jié)構(gòu)anima會(huì)聚vs.分裂聚類會(huì)聚(bottom-up)以每個(gè)樣本獨(dú)自一類開(kāi)始，迭代合并到越來(lái)越大的類中分裂

(partitional,top-down)將所有樣本不斷劃分到類別中會(huì)聚vs.分裂聚類會(huì)聚(bottom-up)以每個(gè)樣本獨(dú)會(huì)聚層次聚類(HAC)設(shè)定相似度函數(shù)確定任意兩個(gè)實(shí)例的相似度開(kāi)始每個(gè)實(shí)例獨(dú)自一類然后重復(fù)合并最相似的類別，直到成為一類：在當(dāng)前的類別中，確定最近的兩類ci和cj用單一的類別ci

cj取代

ci和cj合并的過(guò)程成為層次結(jié)構(gòu)會(huì)聚層次聚類(HAC)設(shè)定相似度函數(shù)確定任意兩個(gè)實(shí)例的相似聚類相似度設(shè)定一個(gè)相似度函數(shù)確定兩個(gè)實(shí)例的相似程度文本向量的余弦相似度如何計(jì)算包含多個(gè)樣例的兩個(gè)類別的相似度？SingleLink:兩個(gè)類別中最近成員的相似度CompleteLink:兩個(gè)類別中最遠(yuǎn)成員的相似度GroupAverage:成員間的平均相似度聚類相似度設(shè)定一個(gè)相似度函數(shù)確定兩個(gè)實(shí)例的相似程度06文本分類與聚類課件06文本分類與聚類課件06文本分類與聚類課件06文本分類與聚類課件計(jì)算復(fù)雜度在第一次迭代中，HAC方法需要計(jì)算所有樣例的每一對(duì)的距離在合并迭代中，需要計(jì)算新形成的類與其他類的距離為了維持O(n2)的性能，計(jì)算類與類之間的相似度需要常數(shù)時(shí)間計(jì)算復(fù)雜度在第一次迭代中，HAC方法需要計(jì)算所有樣例的每一對(duì)計(jì)算類別間相似度合并ci,cj后，計(jì)算該類和其他類的相似度可以如下計(jì)算：SingleLink:CompleteLink:計(jì)算類別間相似度合并ci,cj后，計(jì)算該類和其他類的相似度可平均連通凝聚聚類單連通容易導(dǎo)致狹長(zhǎng)聚類，全連通的算法復(fù)雜度為O(n3)用合并后的類中所有對(duì)平均相似度度量?jī)蓚€(gè)類的相似度是全連通和單連通的折中.平均連通凝聚聚類單連通容易導(dǎo)致狹長(zhǎng)聚類，全連通的算法復(fù)雜度為計(jì)算平均連通相似度設(shè)定余弦相似度及單位長(zhǎng)度歸一化向量.總是維持每個(gè)類別的向量和.計(jì)算類別相似度在常數(shù)時(shí)間內(nèi):計(jì)算平均連通相似度設(shè)定余弦相似度及單位長(zhǎng)度歸一化向量.非層次聚類需要確定期望的類別數(shù)k隨機(jī)選擇k個(gè)種子

進(jìn)行初始聚類迭代，將樣例重新劃分直到樣例所屬的類別不再改變非層次聚類需要確定期望的類別數(shù)kK-Means設(shè)定樣例是一個(gè)實(shí)值向量基于質(zhì)心或類c中樣本的均值聚類根據(jù)樣例與當(dāng)前類別質(zhì)心的相似度重新劃分類別K-Means設(shè)定樣例是一個(gè)實(shí)值向量距離矩陣歐式距(L2norm):L1norm:余弦相似度(轉(zhuǎn)換成距離):距離矩陣歐式距(L2norm):K-Means算法令d為兩個(gè)實(shí)例的距離度量.選擇k

個(gè)隨機(jī)樣例{s1,s2,…sk}作為種子.直到聚類收斂或滿足停止策略:

對(duì)每個(gè)樣例xi:

將

xi

分配到cj

，

d(xi,sj)是最小的.

(Updatetheseedstothecentroidofeachcluster)

對(duì)每個(gè)類cjsj=(cj)K-Means算法令d為兩個(gè)實(shí)例的距離度量.KMeans舉例(K=2)PickseedsReassignclustersComputecentroidsxxReasssignclustersxxxxComputecentroidsReassignclustersConverged!KMeans舉例(K=2)PickseedsReass種子的選擇聚類結(jié)果與隨機(jī)種子的選擇是相關(guān)的隨機(jī)選擇的種子可能會(huì)導(dǎo)致收斂很慢或者收斂到局部最優(yōu)采用啟發(fā)式方法或其他方法選擇好的種子種子的選擇聚類結(jié)果與隨機(jī)種子的選擇是相關(guān)的Buckshot算法層次聚類和K-均值首先隨機(jī)選擇n1/2

大小的語(yǔ)料在這些樣例上運(yùn)行HAC利用HAC的結(jié)果做為K-均值的種子該方法避免了不良種子的選取Buckshot算法層次聚類和K-均值文本聚類HAC和K-Means可以直接應(yīng)用于文本中.典型的使用歸一化、基于TF/IDF權(quán)重的向量以及余弦相似度.應(yīng)用:在檢索階段，加入同一類別的其他文本作為初始檢索結(jié)果，提高召回率.檢索結(jié)果進(jìn)行聚類，可以提供給用戶更好的組織形式自動(dòng)生成的層次聚類結(jié)果為用戶提供方便，根據(jù)聚類結(jié)果生成文摘等文本聚類HAC和K-Means可以直接應(yīng)用于文本中.半監(jiān)督學(xué)習(xí)對(duì)于有監(jiān)督的分類，生成標(biāo)注的訓(xùn)練語(yǔ)料代價(jià)很大.Idea:用無(wú)標(biāo)記的數(shù)據(jù)幫助有監(jiān)督分類.通過(guò)用標(biāo)注和未標(biāo)注的語(yǔ)料訓(xùn)練EM，在半監(jiān)督模式中應(yīng)用.用已標(biāo)注的數(shù)據(jù)子集訓(xùn)練初始的模型.用戶已標(biāo)注的數(shù)據(jù)在迭代過(guò)程中不再改變.無(wú)指導(dǎo)的數(shù)據(jù)標(biāo)注在迭代過(guò)程中被重新標(biāo)注.半監(jiān)督學(xué)習(xí)對(duì)于有監(jiān)督的分類，生成標(biāo)注的訓(xùn)練語(yǔ)料代價(jià)很大.半監(jiān)督學(xué)習(xí)舉例假設(shè)“quantum”

出現(xiàn)在標(biāo)為物理的文檔中，但是“Heisenberg”（海森堡）沒(méi)有出現(xiàn)在標(biāo)注的數(shù)據(jù)中.從標(biāo)注的數(shù)據(jù)中學(xué)到“quantum”

是物理文檔的標(biāo)示.標(biāo)注無(wú)監(jiān)督數(shù)據(jù)時(shí)，將出現(xiàn)“quantum”

和“Heisenberg”的文檔標(biāo)為物理類.在進(jìn)行訓(xùn)練時(shí)，可以學(xué)到“Heisenberg”

也是物理類文檔的標(biāo)示.最后學(xué)到的模型可以正確地將僅包含“Heisenberg”

的文檔劃為物理類.半監(jiān)督學(xué)習(xí)舉例假設(shè)“quantum”出現(xiàn)在標(biāo)為物理的文檔中本章小結(jié)介紹了文本分類和聚類的概念介紹了幾種特征提取的方法介紹了貝葉斯，KNN及決策樹(shù)分類方法介紹了層次聚類和非層次聚類的方法本章小結(jié)介紹了文本分類和聚類的概念文本分類與聚類哈工大信息檢索研究室2007文本分類與聚類哈工大信息檢索研究室這一部分將講述文本分類及聚類的概念文本特征的提取方法貝葉斯分類，KNN分類及決策樹(shù)分類K均值及層次聚類的方法這一部分將講述文本分類及聚類的概念文本分類概述文本分類概述概述文本分類包括普通文本分類和網(wǎng)頁(yè)文本分類中文網(wǎng)頁(yè)分類技術(shù)已經(jīng)成為中文信息處理領(lǐng)域的一項(xiàng)基礎(chǔ)性工作網(wǎng)頁(yè)分類可以為搜索引擎用戶提供目錄導(dǎo)航服務(wù)，進(jìn)而提高系統(tǒng)查準(zhǔn)率網(wǎng)頁(yè)分類可以為個(gè)性化搜索引擎奠定基礎(chǔ)概述文本分類包括普通文本分類和網(wǎng)頁(yè)文本分類分類的概念給定:一個(gè)實(shí)例的描述,xX,X是實(shí)例空間一個(gè)固定的文本分類體系:C={c1,c2,…cn}由于類別是事先定義好的，因此分類是有指導(dǎo)的（或者說(shuō)是有監(jiān)督的）確定:實(shí)例x的類別c(x)C,c(x)是一個(gè)分類函數(shù)，定義域是X

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

TB類一般工業(yè)技術(shù)TD類礦業(yè)工程TE類石油、天然氣工業(yè)TF類冶金工業(yè)TG類金屬學(xué)、金屬工藝TH類機(jī)械、儀表工藝TJ類武器工業(yè)TK類動(dòng)力工業(yè)TL類原子能技術(shù)TM類電工技術(shù)TN類無(wú)線電電子學(xué)、電信技術(shù)TP類自動(dòng)化技術(shù)、計(jì)算技術(shù)TQ類化學(xué)工業(yè)TS類輕工業(yè)、手工業(yè)TU類建筑科學(xué)TV類水利工程中圖分類法A類馬列主義、毛澤東思想T

系統(tǒng)結(jié)構(gòu)標(biāo)注工具機(jī)器學(xué)習(xí)工具模型數(shù)據(jù)標(biāo)注的樣本分類工具類別預(yù)處理預(yù)處理訓(xùn)練數(shù)據(jù)文本新數(shù)據(jù)文本系統(tǒng)結(jié)構(gòu)標(biāo)注工具機(jī)器學(xué)習(xí)工具模型數(shù)據(jù)標(biāo)注的樣本分類工具M(jìn)ultimediaGUIGarb.Coll.SemanticsMLPgrammingsemanticslanguageproof...learningintelligencealgorithmreinforcementnetwork...garbagecollectionmemoryoptimizationregion...“planninglanguageproofintelligence”訓(xùn)練數(shù)據(jù)測(cè)試數(shù)據(jù)類別(AI)文本分類示例(Programming)(HCI)......MultimediaGUIGarb.Coll.Semanti分類的一般過(guò)程收集訓(xùn)練集和測(cè)試集，對(duì)文本進(jìn)行預(yù)處理對(duì)文本進(jìn)行特征提取分類器訓(xùn)練（學(xué)習(xí)）測(cè)試與評(píng)價(jià)精確率、召回率、F1宏平均，微平均分類的一般過(guò)程收集訓(xùn)練集和測(cè)試集，對(duì)文本進(jìn)行預(yù)處理分類的評(píng)測(cè)偶然事件表（ContingencyTable）對(duì)一個(gè)分類器的度量準(zhǔn)確率(precision)=a/(a+b)召回率(recall)=a/(a+c)fallout=b/(b+d)屬于此類不屬于此類判定屬于此類AB判定不屬于此類CD分類的評(píng)測(cè)偶然事件表（ContingencyTable）屬BEP和F測(cè)度BEP（break-evenpoint）當(dāng)準(zhǔn)確率和召回率相等時(shí)的值即為BEPF測(cè)度，取β=1BEP和F測(cè)度的值越大，則表示分類器的性能越好。BEP只是F1所有可能取值中的一個(gè)特定值（當(dāng)p=r時(shí)），因此BEP小于或等于F1的最大值。BEP和F測(cè)度BEP（break-evenpoint）多類分類問(wèn)題的評(píng)價(jià)宏平均（macro-averaging）先對(duì)每個(gè)分類器計(jì)算上述量度，再對(duì)所有分類器求平均是關(guān)于類別的均值微平均（micro-averaging）先合并所有分類器的偶然事件表中的各元素，得到一個(gè)總的偶然事件表，再由此表計(jì)算各種量度。是關(guān)于文本的均值多類分類問(wèn)題的評(píng)價(jià)宏平均（macro-averaging）收集訓(xùn)練數(shù)據(jù)TREC提供統(tǒng)一的訓(xùn)練集和測(cè)試集進(jìn)行系統(tǒng)評(píng)測(cè)國(guó)外：CMU,BERKLEY,CORNELL國(guó)內(nèi)：中科院計(jì)算所，清華大學(xué)，復(fù)旦大學(xué)后續(xù)增加了網(wǎng)頁(yè)語(yǔ)料和中文文本但是中文文本是新華社的新聞稿，與網(wǎng)頁(yè)的分類體系還有差別收集訓(xùn)練數(shù)據(jù)TREC提供統(tǒng)一的訓(xùn)練集和測(cè)試集進(jìn)行系統(tǒng)評(píng)測(cè)目前已有的評(píng)測(cè)語(yǔ)料有指導(dǎo)的機(jī)器學(xué)習(xí)方法是實(shí)現(xiàn)中文網(wǎng)頁(yè)自動(dòng)分類的基礎(chǔ)，因此訓(xùn)練集是實(shí)現(xiàn)分類的前提條件已有訓(xùn)練語(yǔ)料863評(píng)測(cè)語(yǔ)料(中圖分類)搜狗語(yǔ)料復(fù)旦語(yǔ)料目前已有的評(píng)測(cè)語(yǔ)料有指導(dǎo)的機(jī)器學(xué)習(xí)方法是實(shí)現(xiàn)中文網(wǎng)頁(yè)自動(dòng)分類訓(xùn)練語(yǔ)料分類體系中圖分類體系處理對(duì)象是圖書，不適合網(wǎng)頁(yè)分類學(xué)科分類與代碼1992年制定，時(shí)間過(guò)久，包括一些過(guò)時(shí)類別上述兩個(gè)分類標(biāo)準(zhǔn)都不能直接用做中文網(wǎng)頁(yè)的分類中文網(wǎng)頁(yè)的分類體系訓(xùn)練語(yǔ)料分類體系中圖分類體系一種中文網(wǎng)頁(yè)的分類體系一種中文網(wǎng)頁(yè)的分類體系訓(xùn)練集的大小通過(guò)不斷增加實(shí)例的個(gè)數(shù)，考察每個(gè)類訓(xùn)練樣本對(duì)分類器質(zhì)量的影響宏觀F1微觀F1訓(xùn)練集的大小通過(guò)不斷增加實(shí)例的個(gè)數(shù)，考察每個(gè)類訓(xùn)練樣本對(duì)分類網(wǎng)頁(yè)預(yù)處理去掉網(wǎng)頁(yè)中的導(dǎo)航信息去掉HTML網(wǎng)頁(yè)中的tag標(biāo)記(中文)分詞、詞性標(biāo)注、短語(yǔ)識(shí)別、…去除停用詞和詞根還原(stemming)數(shù)據(jù)清洗：去掉不合適的噪聲文檔或文檔內(nèi)垃圾數(shù)據(jù)網(wǎng)頁(yè)預(yù)處理去掉網(wǎng)頁(yè)中的導(dǎo)航信息特征提取特征提取特征提取(FeatureSelection)在文本分類問(wèn)題中遇到的一個(gè)主要困難就是高維的特征空間通常一份普通的文本在經(jīng)過(guò)文本表示后，如果以詞為特征，它的特征空間維數(shù)將達(dá)到幾千，甚至幾萬(wàn)大多數(shù)學(xué)習(xí)算法都無(wú)法處理如此大的維數(shù)為了能夠在保證分類性能的前提下，自動(dòng)降低特征空間的維數(shù)，在許多文本分類系統(tǒng)的實(shí)現(xiàn)中都引入了特征提取方法特征提取(FeatureSelection)在文本分類問(wèn)題舉例對(duì)每類構(gòu)造k

個(gè)最有區(qū)別能力的term例如：計(jì)算機(jī)領(lǐng)域：主機(jī)、芯片、內(nèi)存、編譯

…汽車領(lǐng)域:

輪胎，方向盤，底盤，氣缸，…舉例對(duì)每類構(gòu)造k個(gè)最有區(qū)別能力的term用文檔頻率選特征文檔頻率DF(DocumentFrequency)DFi：所有文檔集合中出現(xiàn)特征i的文檔數(shù)目基本假設(shè)：稀少的詞或者對(duì)于目錄預(yù)測(cè)沒(méi)有幫助，或者不會(huì)影響整體性能。實(shí)現(xiàn)方法：先計(jì)算所有詞的DF，然后刪除所有DF小于某個(gè)閾值的詞，從而降低特征空間的維數(shù)。優(yōu)缺點(diǎn)：最簡(jiǎn)單的降低特征空間維數(shù)的方法稀少的詞具有更多的信息，因此不宜用DF大幅度地刪除詞用文檔頻率選特征文檔頻率詞的熵term的熵該值越大，說(shuō)明分布越均勻，越有可能出現(xiàn)在較多的類別中；該值越小，說(shuō)明分布越傾斜，詞可能出現(xiàn)在較少的類別中詞的熵term的熵信息增益(InformationGain,IG)t出現(xiàn)的概率t不出現(xiàn)假定t出現(xiàn)時(shí)取第i

個(gè)類別的概率取第i

個(gè)類別時(shí)的概率該term為整個(gè)分類所能提供的信息量不考慮任何特征的熵和考慮該特征后的熵的差值信息增益計(jì)算的是已知一個(gè)詞t是否出現(xiàn)在一份文本中對(duì)于類別預(yù)測(cè)有多少信息。這里的定義是一個(gè)更一般的、針對(duì)多個(gè)類別的定義。信息增益(InformationGain,IG)t出現(xiàn)互信息（MutualInformation）互信息(MutualInformation)：MI越大t和c共現(xiàn)程度越大互信息的定義與交叉熵近似，只是互信息不考慮t不出現(xiàn)的概率，它的定義為：互信息（MutualInformation）互信息(Mutχ2統(tǒng)計(jì)量（CHI）：2統(tǒng)計(jì)量的定義可以從一個(gè)詞t與一個(gè)類別c的偶然事件表引出（假設(shè)文本的總數(shù)為N）度量?jī)烧?term和類別)獨(dú)立性程度χ2

越大，獨(dú)立性越小，相關(guān)性越大若AD<BC,則類和詞獨(dú)立,N=A+B+C+DABCDt~tc~cχ2統(tǒng)計(jì)量（CHI）：2統(tǒng)計(jì)量的定義可以從一個(gè)詞t與一個(gè)類特征提取方法的性能比較(Macro-F1)特征提取方法的性能比較(Macro-F1)特征提取方法的性能比較(Micro-F1)特征提取方法的性能比較(Micro-F1)結(jié)論可以看出CHI，IG，DF性能好于MIMI最差CHI，IG，DF性能相當(dāng)DF具有算法簡(jiǎn)單，質(zhì)量高的優(yōu)點(diǎn)，可以替代CHI，IG結(jié)論可以看出CHI，IG，DF性能好于MI分類器學(xué)習(xí)訓(xùn)練樣本實(shí)例：<x,c(x)>一個(gè)文本實(shí)例xX帶有正確的類別標(biāo)記c(x)學(xué)習(xí)的過(guò)程是在給定訓(xùn)練樣本集合D

的前提下，尋找一個(gè)分類函數(shù)h(x),使得:分類器學(xué)習(xí)訓(xùn)練樣本實(shí)例：<x,c(x)>貝葉斯分類貝葉斯分類貝葉斯分類基于概率理論的學(xué)習(xí)和分類方法貝葉斯理論在概率學(xué)習(xí)及分類中充當(dāng)重要角色僅使用每類的先驗(yàn)概率不能對(duì)待分的文本提供信息分類是根據(jù)給定樣本描述的可能的類別基礎(chǔ)上產(chǎn)生的后驗(yàn)概率分布貝葉斯分類基于概率理論的學(xué)習(xí)和分類方法貝葉斯理論得到：由條件概率的定義：貝葉斯理論得到：由條件概率的定義：貝葉斯分類設(shè)各個(gè)類別的集合為{c1,c2,…cn}設(shè)E為實(shí)例的描述確定E的類別P(E)可以根據(jù)下式確定貝葉斯分類設(shè)各個(gè)類別的集合為{c1,c2,…cn}貝葉斯分類(cont.)需要知道:先驗(yàn)概率:P(ci)條件概率:P(E|ci)P(ci)容易從數(shù)據(jù)中獲得如果文檔集合D中，屬于ci的樣例數(shù)為ni則有 P(ci)=ni/|D|假設(shè)樣例的特征是關(guān)聯(lián)的:指數(shù)級(jí)的估計(jì)所有的P(E|ci)貝葉斯分類(cont.)需要知道:樸素的貝葉斯分類如果假定樣例的特征是獨(dú)立的，可以寫為：因此，只需要知道每個(gè)特征和類別的P(ej|ci)如果只計(jì)算單個(gè)特征的分布，大大地減少了計(jì)算量樸素的貝葉斯分類如果假定樣例的特征是獨(dú)立的，可以寫為：文本分類Na?veBayes算法(訓(xùn)練)設(shè)V為文檔集合D所有詞詞表對(duì)每個(gè)類別ci

CDi是文檔D中類別Ci的文檔集合

P(ci)=|Di|/|D|設(shè)ni為Di中詞的總數(shù)對(duì)每個(gè)詞

wjV

令nij

為Di中wij的數(shù)量

P(wi|ci)=(nij+1)/(ni+|V|)文本分類Na?veBayes算法(訓(xùn)練)設(shè)V為文檔集合D文本分類Na?veBayes算法(測(cè)試)給定測(cè)試文檔X設(shè)n

為X中詞的個(gè)數(shù)返回的類別:wi是X中第i個(gè)位置的詞文本分類Na?veBayes算法(測(cè)試)給定測(cè)試文檔XNa?veBayes分類舉例C={allergy,cold,well}e1=sneeze;e2=cough;e3=fever當(dāng)前實(shí)例是：E={sneeze,cough,fever}ProbWellColdAllergyP(ci)0.90.050.05P(sneeze|ci)P(cough|ci)P(fever|ci)0.010.70.4過(guò)敏打噴嚏Na?veBayes分類舉例C={allergy,cNa?veBayes舉例(cont.)參數(shù)計(jì)算：P(well|E)=(0.9)(0.1)(0.1)(0.99)/P(E)=0.0089/P(E)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.50Na?veBayes舉例(cont.)參數(shù)計(jì)算：Play-tennis例子:估算P(xi|C)P(p)=9/14P(n)=5/14Play-tennis例子:估算P(xi|C)P(p)outlookP(sunny|p)=2/9P(sunny|n)=3/5P(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/5正例反例outlookP(sunny|p)=2/9P(sunnyPlay-tennis例子:分類X例子X(jué)=<rain,hot,high,false>P(X|p)·P(p)=

P(rain|p)·P(hot|p)·P(high|p)·P(false|p)·P(p)=3/9·2/9·3/9·6/9·9/14=0.010582P(X|n)·P(n)=

P(rain|n)·P(hot|n)·P(high|n)·P(false|n)·P(n)=2/5·2/5·4/5·2/5·5/14=0.018286樣本X被分到n類，即“不適合打網(wǎng)球”Play-tennis例子:分類X例子X(jué)=<rai舉例在Joachims(1996)的一個(gè)實(shí)驗(yàn)中，被應(yīng)用于分類新聞組文章20個(gè)電子新聞組，每個(gè)新聞組1000篇文章，形成2萬(wàn)個(gè)文檔的數(shù)據(jù)集2/3作訓(xùn)練集，1/3作測(cè)試集衡量性能20個(gè)新聞組，隨機(jī)猜測(cè)的分類精確度5%，由程序獲得的精確度89%舉例在Joachims(1996)的一個(gè)實(shí)驗(yàn)中，被應(yīng)用于分類討論樸素的貝葉斯假定在一個(gè)位置上出現(xiàn)的詞的概率獨(dú)立于另外一個(gè)位置的單詞，這個(gè)假定有時(shí)并不反映真實(shí)情況雖然獨(dú)立性假設(shè)很不精確，別無(wú)選擇，否則計(jì)算的概率項(xiàng)將極為龐大幸運(yùn)的是，在實(shí)踐中樸素貝葉斯學(xué)習(xí)器在許多文本分類中性能非常好，即使獨(dú)立性假設(shè)不成立討論樸素的貝葉斯假定在一個(gè)位置上出現(xiàn)的詞的概率獨(dú)立于另外一個(gè)K近鄰K近鄰K近鄰（KNN）最近鄰分類規(guī)則

對(duì)于測(cè)試樣本點(diǎn)x，在集合中距離它最近的的x1。最近鄰分類就是把x分為x1所屬的類別最近鄰規(guī)則的推廣-KNN沒(méi)有好的相似度矩陣不能用KNNK近鄰（KNN）最近鄰分類規(guī)則KNN算法目標(biāo)：基于訓(xùn)練集X的對(duì)y分類在訓(xùn)練集中，尋找和y最相似的訓(xùn)練樣本x得到k個(gè)最相似的集合A,A為X的一個(gè)子集設(shè)n1,n2分別為集合中屬于c1,c2的個(gè)數(shù)如果p(c1|y)>p(c2|y),判為c1,否則判為c2KNN算法目標(biāo)：基于訓(xùn)練集X的對(duì)y分類kNN方法一種基于實(shí)例的學(xué)習(xí)方法新文本k=1,A類k=4，B類k=10，B類帶權(quán)重計(jì)算，計(jì)算權(quán)重和最大的類。k常取3或者5。kNN方法一種基于實(shí)例的學(xué)習(xí)方法新文本k=1,A類k=4，KNN在文本分類中的應(yīng)用KNN在文本分類中的應(yīng)用KNN分類錯(cuò)誤是由于：?jiǎn)蝹€(gè)的非典型樣例單個(gè)訓(xùn)練樣本的噪音.更魯棒的方法是發(fā)現(xiàn)k個(gè)最相似的樣本，返回k個(gè)樣本最主要的類別KNN分類錯(cuò)誤是由于：相似度矩陣最近鄰方法依賴于相似度矩陣(或距離).對(duì)連續(xù)m維空間最簡(jiǎn)單的方法采用歐氏距.對(duì)m維二值實(shí)例空間最簡(jiǎn)單的方法是海明距.對(duì)于基于文本tf/idf權(quán)重向量的余弦相似度是經(jīng)常被采用的.相似度矩陣最近鄰方法依賴于相似度矩陣(或距離).影響KNN的因素K的取值K一般取15計(jì)算距離的方法歐式距離蘭式距離（余弦相似度）影響KNN的因素K的取值KNN和NB比較從表中看，KNN質(zhì)量較高，NB的效率較高從各個(gè)類別看，KNN比NB穩(wěn)定，NB對(duì)類別敏感KNN和NB比較決策樹(shù)決策樹(shù)簡(jiǎn)介決策樹(shù)方法的起源是概念學(xué)習(xí)系統(tǒng)CLS，然后發(fā)展到ID3方法而為高潮，最后又演化為能處理連續(xù)屬性的C4.5。有名的決策樹(shù)方法還有CART和Assistant應(yīng)用最廣的歸納推理算法之一一種逼近離散值目標(biāo)函數(shù)的方法簡(jiǎn)介決策樹(shù)方法的起源是概念學(xué)習(xí)系統(tǒng)CLS，然后發(fā)展到ID3方?jīng)Q策樹(shù)的表示法決策樹(shù)通過(guò)把實(shí)例從根節(jié)點(diǎn)排列到某個(gè)葉子節(jié)點(diǎn)來(lái)分類實(shí)例，葉子節(jié)點(diǎn)即為實(shí)例所屬的分類。樹(shù)上的每一個(gè)節(jié)點(diǎn)說(shuō)明了對(duì)實(shí)例的某個(gè)屬性的測(cè)試，并且該節(jié)點(diǎn)的每一個(gè)后繼分支對(duì)應(yīng)于該屬性的一個(gè)可能值決策樹(shù)的表示法決策樹(shù)通過(guò)把實(shí)例從根節(jié)點(diǎn)排列到某個(gè)葉子節(jié)點(diǎn)來(lái)分決策樹(shù)表示舉例決策樹(shù)表示舉例表達(dá)式表達(dá)式?jīng)Q策樹(shù)學(xué)習(xí)的適用問(wèn)題實(shí)例是由屬性-值對(duì)表示的目標(biāo)函數(shù)具有離散的輸出值可能需要析取的描述訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例決策樹(shù)學(xué)習(xí)的適用問(wèn)題實(shí)例是由屬性-值對(duì)表示的屬性選擇構(gòu)造好的決策樹(shù)的關(guān)鍵在于如何選擇好的邏輯判斷或?qū)傩?。?duì)于同樣一組例子，可以有很多決策樹(shù)能符合這組例子。一般情況下或具有較大概率地說(shuō)，樹(shù)越小則樹(shù)的預(yù)測(cè)能力越強(qiáng)。要構(gòu)造盡可能小的決策樹(shù)，關(guān)鍵在于選擇恰當(dāng)?shù)倪壿嬇袛嗷驅(qū)傩浴Ｓ捎跇?gòu)造最小的樹(shù)是NP-難問(wèn)題，因此只能采取用啟發(fā)式策略選擇好的邏輯判斷或?qū)傩?/p>

屬性選擇構(gòu)造好的決策樹(shù)的關(guān)鍵在于如何選擇好的邏輯判斷或?qū)傩浴Ｓ渺囟攘繕永木恍裕兌龋╈氐亩x舉例用熵度量樣例的均一性（純度）熵的定義關(guān)于某布爾分類的熵函數(shù)關(guān)于某布爾分類的熵函數(shù)用信息增益度量期望熵最低一個(gè)屬性的信息增益就是由于使用這個(gè)屬性分割樣例而導(dǎo)致的期望熵的降低用信息增益度量期望熵最低一個(gè)屬性的信息增益就是由于使用這個(gè)屬舉例舉例計(jì)算信息增益計(jì)算信息增益確定最佳分類的屬性哪一個(gè)屬性是最好的分類？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確定最佳分類的屬性哪一個(gè)屬性是最好的分類？S:[9+,5-]不同屬性的信息增益計(jì)算各屬性的熵值Gain(S,Outlook)=0.246Gain(S,Humidity)=0.151Gain(S,Wind)=0.048Gain(S,Temperature)=0.029可以看到，Outlook得信息增益最大不同屬性的信息增益計(jì)算各屬性的熵值D1,D2,…D149+,5-OutlookSunnyD1,D2,D8,D9,D112+,3-RainD4,D5,D6,D10,D143+,2-D3,D7,D12,D134+,0-Overcast?哪一個(gè)屬性在這里被測(cè)試？Ssunny={D1,D2,D8,D9,D11}Gain（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,Wind)=0.970-(2/5)1.0-(3/5)0.918=0.019?YesD1,D2,…D14OutlookSunnyD1,D2,D8ID3算法創(chuàng)建樹(shù)的Root結(jié)點(diǎn)開(kāi)始

AAttributes中分類能力最好的屬性

Root的決策屬性A

對(duì)于每個(gè)可能值vi

在Root下加一個(gè)新的分支對(duì)應(yīng)測(cè)試A=vi

令Examplesvi為Examples中滿足A屬性值為vi的子集 如果Examplesvi為空 在這個(gè)新分支下加一個(gè)葉子結(jié)點(diǎn)，節(jié)點(diǎn)的lable=Examples中最普遍的目標(biāo)屬性值(target-attribute)

否則在這個(gè)新分支下加一個(gè)子樹(shù)ID3(examplevi,target- attribute,attributes-{A})返回RootID3算法創(chuàng)建樹(shù)的Root結(jié)點(diǎn)C4.5C4.5是對(duì)ID3的改進(jìn)算法對(duì)連續(xù)值的處理對(duì)未知特征值的處理對(duì)決策樹(shù)進(jìn)行剪枝規(guī)則的派生C4.5C4.5是對(duì)ID3的改進(jìn)算法決策樹(shù)學(xué)習(xí)的常見(jiàn)問(wèn)題過(guò)度擬合數(shù)據(jù)基本的決策樹(shù)構(gòu)造算法沒(méi)有考慮噪聲，生成的決策樹(shù)完全與訓(xùn)練例子擬合有噪聲情況下，完全擬合將導(dǎo)致過(guò)分?jǐn)M合（overfitting），即對(duì)訓(xùn)練數(shù)據(jù)的完全擬合反而不具有很好的預(yù)測(cè)性能

決策樹(shù)學(xué)習(xí)的常見(jiàn)問(wèn)題過(guò)度擬合數(shù)據(jù)解決方法剪枝是一種克服噪聲的技術(shù)，同時(shí)它也能使樹(shù)得到簡(jiǎn)化而變得更容易理解。向前剪枝（forwardpruning）向后剪枝（backwardpruning）

理論上講，向后剪枝好于向前剪枝，但計(jì)算復(fù)雜度大。剪枝過(guò)程中一般要涉及一些統(tǒng)計(jì)參數(shù)或閾值，如停機(jī)閾值有人提出了一種和統(tǒng)計(jì)參數(shù)無(wú)關(guān)的基于最小描述長(zhǎng)度（MDL）的有效剪枝法解決方法剪枝是一種克服噪聲的技術(shù)，同時(shí)它也能使樹(shù)得到簡(jiǎn)化而變決策樹(shù)的優(yōu)點(diǎn)可以生成可以理解的規(guī)則計(jì)算量相對(duì)來(lái)說(shuō)不是很大可以處理連續(xù)和離散字段決策樹(shù)可以清晰的顯示哪些字段比較重要過(guò)程可見(jiàn)

決策樹(shù)的優(yōu)點(diǎn)可以生成可以理解的規(guī)則不足之處對(duì)連續(xù)性的字段比較難預(yù)測(cè)當(dāng)類別太多時(shí)，錯(cuò)誤可能會(huì)增加的比較快一般的算法分類的時(shí)候，只是根據(jù)一個(gè)屬性來(lái)分類。不是全局最優(yōu)

不足之處對(duì)連續(xù)性的字段比較難預(yù)測(cè)文本分類的應(yīng)用新聞出版按照欄目分類類別{政治,體育,軍事,…}網(wǎng)頁(yè)分類類似于Yahoo的分類個(gè)性化新聞智能推薦垃圾郵件過(guò)濾類別{spam,not-spam}文本分類的應(yīng)用新聞出版按照欄目分類

文本聚類

TextClustering

文本聚類

TextClustering聚類式搜索聚類式搜索聚類式搜索聚類式搜索聚類將無(wú)標(biāo)記的樣本劃分到聚類的各個(gè)子集中:類內(nèi)樣本非常相似類間樣本非常不同無(wú)監(jiān)督方法發(fā)現(xiàn)新類別聚類.聚