6.文本分類全解

數(shù)據(jù)挖掘：文本分類專題王成〔副教授〕華僑大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院主要內(nèi)容文本分類及文檔的特征向量余弦相似度使用分類算法進(jìn)行文本分類逆文檔頻率TF-IDFTF-IDF的信息論依據(jù)淺談中文分詞本節(jié)內(nèi)容來源于吳軍博士?數(shù)學(xué)之美?文本分類文本分類所謂新聞的分類，或者更廣義的講任何文本的分類，無非是要把相似的新聞放到同一類中如果讓編輯來對新聞分類，他一定是先把新聞讀懂，然后找到它的主題，最后根據(jù)主題的不同對新聞進(jìn)行分類但計算機(jī)根本讀不懂新聞，計算機(jī)本質(zhì)上只能做快速計算，為了讓計算機(jī)能“算〞新聞，就要求：1〕把文字的新聞變成可以計算的一組數(shù)字2〕然后再設(shè)計一個算法來計算兩篇新聞的相似度特征向量相似性度量新聞的特征向量如何用特征向量來表示一篇新聞？幸福的家庭都是相似的，不幸的家庭各有各的不幸。托爾斯泰?安娜?卡列尼娜?同一類新聞用詞都是相似的，不同類的新聞用詞各不相同。詞例如詞匯表有64000個詞，其編號分別為1,2,...,64000統(tǒng)計一篇新聞中各詞的出現(xiàn)次數(shù)，按照對應(yīng)詞在詞匯表中的位置依次排列，就得到一個向量編號漢字詞1阿2啊3阿斗4阿姨......789服裝......64000做作新聞的特征向量編號漢字詞10253043......78910......640002新聞的特征向量如果單詞表中的某個詞在新聞中沒有出現(xiàn)，對應(yīng)的值為零，那這64000個數(shù)，組成一個64000維的特征向量，我們就用這個特征向量來表示一篇新聞。這樣，新聞就可以拿來“計算〞了(0,0,0,3,0,...,28,0,0,0,3)(1,0,5,0,0,...,10,0,20,0,1)(0,0,3,5,0,...,0,8,0,12,0)新聞的特征向量一篇新聞里有很多詞，有些詞表達(dá)的語義重要，有些相對次要。例如“的、地、得、了〞這些助詞，這些詞對確定新聞主題沒有幫助，反而會影響分類結(jié)果，因此在計算時應(yīng)忽略它們。這些詞稱為停用詞(stopwords)新聞長短不同，同一個詞在長新聞中出現(xiàn)的次數(shù)一般要比在短新聞中出現(xiàn)的次數(shù)多，因此需要根據(jù)新聞長度，對詞的出現(xiàn)次數(shù)進(jìn)行歸一化，即用詞的出現(xiàn)次數(shù)除以總詞數(shù)，稱為詞頻(TermFrequency，簡稱TF)，然后用詞頻來替代特征向量中相對應(yīng)的計數(shù)值例如某新聞有1000個詞，其中“原子能〞和“應(yīng)用〞分別出現(xiàn)了2次和5次，那么它們的詞頻分別為0.002和0.005詞頻的簡單應(yīng)用關(guān)鍵字提?。簩τ谝黄侣?，提取出詞頻最高的前N個詞，即可作為該篇新聞的關(guān)鍵字度量新聞和查詢的相關(guān)性：直接使用各個關(guān)鍵字在新聞中出現(xiàn)的總詞頻。例如，查詢“原子能應(yīng)用〞，“原子能〞在新聞A中的詞頻是0.035，“應(yīng)用〞在新聞A中的詞頻是0.020，那么這個查詢和新聞A的相關(guān)性為0.035+0.020=0.055主要內(nèi)容文本分類及文檔的特征向量余弦相似度使用分類算法進(jìn)行文本分類逆文檔頻率TF-IDFTF-IDF的信息論依據(jù)淺談中文分詞度量兩篇新聞的相似度設(shè)兩篇新聞的特征向量為x(x1,x2,...)和y(y1,y2,...)，它們的歐氏距離為d(x,y)：那么它們的相似度可以表示為余弦相似度向量實際上是多維空間中從原點出發(fā)的有向線段。余弦相似度使用向量的夾角來衡量兩個向量的相近程度，兩個向量的夾角越小表示越相似，夾角越大表示越不相似。余弦相似度根據(jù)向量的點積公式假設(shè)新聞X和新聞Y的特征向量為(x1,x2,...)和(y1,y2,...)，那么它們的夾角余弦為因向量中每一個變量都是正數(shù)，因此余弦的取值在0和1之間，即夾角在0度到90度之間。當(dāng)余弦等于1時，夾角為0，兩新聞完全相同；當(dāng)余弦為0時，夾角為90度，兩新聞毫不相關(guān)。當(dāng)夾角余弦越接近1時，夾角越小，說明兩新聞越相似。余弦相似度練習(xí)A(1,1)B(2,2)利用余弦相似度C(3,3)similarity(A,B)=similarity(A,C)=11利用歐氏距離similarity(A,B)=similarity(A,C)=應(yīng)用：論文分組1998年，約翰?霍普金斯大學(xué)的教授雅讓斯基是某國際會議的程序委員會主席，需要把提交上來的幾百篇論文發(fā)給各個專家去評審決定是否錄用。為保證評審的權(quán)威性，需要把每個研究方向的論文交給這個方向最有權(quán)威的專家。雖然論文作者自己給定了論文方向，但范圍太廣，沒有什么指導(dǎo)意義。雅讓斯基當(dāng)然沒有時間瀏覽這近千篇論文，于是就讓他的學(xué)生實現(xiàn)了一個算法，大致思想為：1.計算所有論文間兩兩的余弦相似性，把相似性大于一個閾值的論文合并成一個小類。2.把每個小類中所有論文作為一個整體，計算小類的特征向量，再計算小類之間兩兩的余弦相似性，然后合并成大一點的小類。3.不斷重復(fù)上述過程，類別越來越少，而每個類越來越大。當(dāng)子類的數(shù)量比較少時，就會看清楚這些子類了。(聚類的思想)主要內(nèi)容文本分類及文檔的特征向量余弦相似度使用分類算法進(jìn)行文本分類逆文檔頻率TF-IDFTF-IDF的信息論依據(jù)淺談中文分詞分類系統(tǒng)設(shè)計的根本步驟傳感器特征提取特征選擇分類器設(shè)計系統(tǒng)評估模式應(yīng)用：新聞分類準(zhǔn)備事先標(biāo)記好類別的新聞訓(xùn)練數(shù)據(jù)將新聞轉(zhuǎn)化為特征向量，訓(xùn)練分類算法使用分類算法對未知新聞進(jìn)行自動分類應(yīng)用：新聞分類-使用kNN計算每訓(xùn)練數(shù)據(jù)中每條新聞和待分類新聞的相似度找出和待分類新聞相似度最大的k條新聞?wù)业降膋條新聞中哪個類別占的最多，待分類新聞就屬于哪個類別應(yīng)用：新聞分類-使用樸素貝葉斯w為新聞特征向量，Ci為新聞類別。對于一條新聞，找到使P(Ci|w)最大的新聞分類，將新聞劃分到該類別中P(Ci)的計算：將訓(xùn)練樣本中屬于Ci類的新聞條數(shù)除以用于訓(xùn)練的所有新聞條數(shù)P(w|Ci)的計算：P(w|Ci)=P(w0|Ci)P(w1|Ci)P(w2|Ci)...P(wn|Ci)其中w0,w1..為詞匯表中的詞，P(wk|Ci)為詞wk在Ci類中的出現(xiàn)概率(詞頻或權(quán)重)主要內(nèi)容文本分類及文檔的特征向量余弦相似度使用分類算法進(jìn)行文本分類逆文檔頻率TF-IDFTF-IDF的信息論依據(jù)淺談中文分詞逆文檔頻率(TF-IDF)以“原子能的應(yīng)用〞為例，去除停用詞“的〞后，它可以分成“原子能〞和“應(yīng)用〞兩個詞但“應(yīng)用〞是個非常通用的詞，而“原子能〞是個很專業(yè)的詞?？吹健霸幽塄晻r，或多或少能了解到新聞的主題，而看到“應(yīng)用〞一詞，對新聞主題根本上還是一無所知。因此，相比于“應(yīng)用〞，“原子能〞對新聞主題確實定更有幫助，“原子能〞的權(quán)重應(yīng)當(dāng)比“應(yīng)用〞高。而單純的詞頻(TF)并不能反映這種權(quán)重上的差異逆文檔頻率(TF-IDF)因此，需要對每一個詞設(shè)置一個權(quán)重，權(quán)重的設(shè)定必須滿足兩個條件：(1)一個詞預(yù)測主題的能力越強(qiáng)，權(quán)重越大，反之權(quán)重越小(2)停用詞的權(quán)重為零逆文檔頻率(TF-IDF)容易發(fā)現(xiàn)，如果一個關(guān)鍵詞只在少量的新聞中出現(xiàn)，通過它就容易確定新聞主題，它的權(quán)重也就應(yīng)該大反之，如果一個詞在大量新聞中出現(xiàn)，通過它仍然難以確定新聞主題，因此它的權(quán)重就應(yīng)該小概括的講，假定一個關(guān)鍵詞w在Dw條新聞中出現(xiàn)過，那么Dw越大，w的權(quán)重越小，反之那么權(quán)重越大逆文檔頻率(TF-IDF)在信息檢索中，使用最多的權(quán)重是逆文檔頻率(InverseDocumentFrequency，簡稱IDF)其中D為所有文檔(新聞)數(shù)量，Dw為出現(xiàn)關(guān)鍵詞w的文檔數(shù)量假定新聞條數(shù)是10億，停用詞“的〞在所有新聞中都出現(xiàn)，即Dw=10億，那它的IDF=log(10億/10億)=log(1)=0假設(shè)“原子能〞在200萬條新聞中出現(xiàn)，即Dw=200萬，那么它的權(quán)重IDF=log(10億/200萬)=log(500)=9.96假設(shè)“應(yīng)用〞在5億條新聞中出現(xiàn)，即Dw=5億，那么它的權(quán)重IDF=log(10億/5億)=log(2)=1逆文檔頻率(TF-IDF)將一個詞的TF乘上其IDF，即為其TF-IDF權(quán)重，即TF-IDF=TF?IDFTF-IDF中的-是連字符，不是代表相減主要內(nèi)容文本分類及文檔的特征向量余弦相似度使用分類算法進(jìn)行文本分類逆文檔頻率TF-IDFTF-IDF的信息論依據(jù)淺談中文分詞信息熵(Entropy)我們常說信息很多，或信息很少，但卻很難說清楚信息到底有多少比方一本50多萬字的?史記?有多少信息量？或一套莎士比亞全集有多少信息量？這個問題幾千年來都沒有人給出很好的解答，直到1948年，香農(nóng)(ClaudeShannon)在他著名的論文“通信的數(shù)學(xué)原理〞中提出了信息熵的概念，才解決了信息的度量問題，并且量化出信息的作用信息熵(Entropy)一條信息的信息量和它的不確定性有著直接的關(guān)系比方，要搞清楚一件非常不確定的事，或是我們一無所知的事情，就需要了解大量信息。相反，如果我們對某件事已經(jīng)有了較多了解，那么不需要太多信息就能把它搞清楚從這個角度看，信息量就等于不確定性的多少如何量化信息的度量呢？信息熵(Entropy)假設(shè)我錯過了一個有32支球隊參加的足球賽，賽后我問一個知道比賽結(jié)果的觀眾“哪支球隊是冠軍〞？他不愿意直接告訴我，而讓我猜，每猜一次，他要收一元錢才肯告訴我是否猜對，那我需要付多少錢才能知道誰是冠軍呢？我可以把球隊編號，從1到32，然后問“冠軍球隊在1-16號中嗎？〞，假設(shè)他告訴我猜對了，我就接著問“冠軍在1-8號中嗎？〞，假設(shè)他說猜錯了，那我就知道冠軍在9-16號中。這樣只要5次，我就能知道哪支球隊是冠軍當(dāng)然，香農(nóng)不是用錢，而是用比特(bit)來度量信息量，在上例中，這條消息的信息量是5比特信息量的比特數(shù)和所有可能情況的對數(shù)有關(guān)，例如本例中，信息量=log(球隊數(shù))，即5=log(32)。Why?信息熵(Entropy)實際上可能不需要5次就能猜出誰是冠軍，因為一些強(qiáng)隊得冠的可能性更高，因此第一次猜測時可以把少數(shù)幾支強(qiáng)隊分成一組，其它球隊分成另一組，然后猜冠軍球隊是否在那幾支強(qiáng)隊中這樣，也許三次或四次就能猜出結(jié)果。因此，當(dāng)每支球隊奪冠的可能性(概率)不等時，這條信息的信息量比5比特少香農(nóng)指出，它的準(zhǔn)確信息量應(yīng)該是p1,p2,...,p32分別是這32支球隊奪冠概率，香農(nóng)把它稱作信息熵，單位為比特；可以算出，當(dāng)32支球隊奪冠概率相同時，對應(yīng)的信息熵為5比特。信息熵(Entropy)對于任意一個隨機(jī)變量X(比方奪冠球隊)，它的熵定義為變量的不確定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大TF-IDF的信息論依據(jù)衡量一個詞的權(quán)重時，一個簡單的方法就是用每個詞的信息量作為它的權(quán)重，即其中N是整個語料庫大小，是個可以省略的常數(shù)，因此公式可簡化成TF-IDF的信息論依據(jù)但是這個公式有個缺陷，兩個詞出現(xiàn)的頻率TF相同，一個是某特定文章中的常見詞，而另一個是分散在多篇文章中，顯然第一個詞有更高的分辨率，它的權(quán)重應(yīng)更大。更好的權(quán)重公式應(yīng)反映出關(guān)鍵詞的分辨率。TF-IDF的信息論依據(jù)如果做一些理想的假設(shè)，(1)每個文獻(xiàn)大小根本相同，均為M個詞，即(2)一個關(guān)鍵詞一旦在文獻(xiàn)中出現(xiàn)，不管次數(shù)多少，奉獻(xiàn)都等同，這樣一個詞在文獻(xiàn)中要么出現(xiàn)c(w)=TF(w)/Dw次，要么出現(xiàn)零次。注意，c(w)<MTF-IDF中的-是連字符，不是代表相減。TF-IDF的信息論依據(jù)因為c(w)<M，因此M/c(w)>1，故等式右邊第二項大于零，且c(w)越大，第二項越小，c(w)越小，第二項越大可以看到，一個詞的信息量I(w)越大，TF-IDF值越大；出現(xiàn)頻率相同的一個詞，越分散在多篇文檔中，其平均出現(xiàn)次數(shù)越小，第二項越大，TF-IDF值越??；反之，越集中出現(xiàn)，其平均出現(xiàn)次數(shù)越大，第二項越小，TF-IDF值越大。這些結(jié)論和信息論完全相符。主要內(nèi)容文本分類及文檔的特征向量余弦相似度使用分類算法進(jìn)行文本分類逆文檔頻率TF-IDFTF-IDF的信息論依據(jù)淺談中文分詞分詞在對文檔轉(zhuǎn)化為特征向量時，需要對文檔內(nèi)容進(jìn)行分詞，將文檔轉(zhuǎn)化成一個個詞條(token)的列表，這個過程稱為詞條化(tokenization)Thequickbrownfoxjumpsoverthelazydogthequickbrownfoxjumpoverthelazydogquickbrownfoxjumpoverlazydog中文分詞中國航天官員應(yīng)邀到美國與太空總署官員開會中國/航天/官員/應(yīng)邀/到/美國/與/太空/總署/官員/開會？中文分詞最簡單的方法是“查字典〞：從左向右掃描句子，遇到字典里有的詞就標(biāo)識出來，遇到復(fù)合詞就找最長匹配(如“上海大學(xué)〞)，遇到不認(rèn)識的字串就分割成單字詞(有限狀態(tài)機(jī))中/國航天官員中國/航天官員中國/航/天官員中國/航天/官員中國/航天/官/員中國/航天/官員/中文分詞這個簡單的方法可以解決七八成的分詞問題，但畢竟太簡單，稍微復(fù)雜一點的情況就無能為力了。例如當(dāng)遇到有二義性(有雙重理解意思)的分割時：開展中國家開展/中國/家X上海大學(xué)城書店上海大學(xué)/城/書店X北京大學(xué)生北京大學(xué)/生X中文分詞能否讓計算機(jī)像人類一樣去理解自然語言？例如，句子“徐志摩喜歡林徽因。〞可分為主語、動詞短語(即謂語)和句號三局部，對每個局部進(jìn)行分析，得到如下的語法分析樹〔編譯器〕中文分詞分析它采用的文法規(guī)那么通常被計算機(jī)科學(xué)家和語言學(xué)家稱為重寫規(guī)那么(RewritingRules)，具體到上例，重寫規(guī)那么為：句子->主語謂語句號主語->名詞謂語->動詞名詞短語名詞短語->名詞名詞->徐志摩動詞->喜歡名詞->徐志摩句號->。中文分詞20世紀(jì)80年代以前，自然語言處理工作中的文法規(guī)那么都是人寫的?？茖W(xué)家原以為隨著對自然語言語法概括得越來越全面，同時計算能力的提高，這種方法可以逐步解決自然語言理解的問題。但這種想法很快遇到了麻煩。從前面例子中的圖可看出，句法分析很啰唆：一個短短的句子居然分析出這么一個復(fù)雜的樹結(jié)構(gòu)，居然需要八條文法規(guī)那么。中文分詞一個更真實的句子：美聯(lián)儲主席本?伯南克昨天告訴媒體7000億美元的救助資金將借給上百家銀行、保險公司和汽車公司。這個句子依然符合“句子→主語謂語句號〞的文法規(guī)那么：主語【美聯(lián)儲主席本?伯南克】||動詞短語【昨天告訴媒體7000億美元的救助資金將借給上百家銀行、保險公司和汽車公司】||句號【?！拷酉聛砜蛇M(jìn)一步劃分，例如主語“美聯(lián)儲主席本?伯南克〞分解成兩個名詞短語“美聯(lián)儲主席〞和“本?伯南克〞，對動詞短語也可做同樣分析。但這樣生成的語法分析樹非常大且復(fù)雜?；谝?guī)那么的自然語言處理的缺陷想通過文法規(guī)那么覆蓋哪怕20%真實語句，文法規(guī)那么的數(shù)量至少幾萬條，語言學(xué)家?guī)缀跻呀?jīng)是來不及寫了這些文法規(guī)那么寫到后來甚至?xí)霈F(xiàn)矛盾，為了解決這