分類體系
分類：給定一個對象，從一個事先定義好的分類體系中挑出一個或多個最適合該對象的類別。
文本分類(TC, Text Categorization)：在給定的分類體系下，根據(jù)文本內(nèi)容自動的確定文本關(guān)聯(lián)的類別。從數(shù)學(xué)角度看，文本分類是一個映射的過程，它將未標明類別的文本映射到已有的類別中，該映射可以是一對一或一對多的映射。
f:A→B
其中，A表示待分類的文本集合，B表示分類體系中的類別集合。
文本分類屬于有監(jiān)督的學(xué)習(xí)(Supervised Learning)，它的基本步驟如下：
定義分類體系，即確定具體要分到哪些類。
將預(yù)先分類過的文檔作為訓(xùn)練集，對文檔做分詞、去停用詞等準備工作。
確定表達模型，對文檔矩陣進行降維，提取訓(xùn)練集中最有用的特征。
應(yīng)用具體的分類模型和分類算法，訓(xùn)練出文本分類器。
在測試集上測試并評價分類器的性能。
應(yīng)用性能最高的分類模型對待分類文檔進行分類。
評價指標
準確率和召回率是檢索(IR)系統(tǒng)中的概念，也可用來評價分類器性能。
TrueFalse
PositiveAB
NegativeCD
準確率(P, Precision)，A/(A+B)，在所有被判斷為正確的文檔中，有多大比例是確實正確的。
召回率(R, Recall)，A/(A+C)，在所有確實正確的文檔中，有多大比例被我們判為正確。
F1測度(F-measure)，2PR/(P+R)，既衡量準確率，也衡量召回率。
準確率和召回率是互相影響的，理想情況下肯定是做到兩者都高，但是一般情況下準確率高、召回率就低，召回率低、準確率高，當然如果兩者都低，那是什么地方出問題了。
其他一些指標：
漏報率(miss rate) = 1 - recall
準確度(accurarcy) = (A + D)/(A + B + C + D)
錯誤率(error) = (B+C)/(A+B+C+D) = 1 - accurarcy
虛報率(fallout) = B/(B+D) = false alarm rate
F = (β^2 +1)PR/(β^2+R)
BEP, Break Event Point, where P=R
AUC
表達模型
模型對每篇文檔默認構(gòu)造的向量是固定長度n，該n可能是我們漢語詞典收錄的詞條數(shù)目，顯然這會導(dǎo)致每個向量里的大部分特征值都是0。這是文本分類的主要特點：高維 和 數(shù)據(jù)稀疏。所以，降維是開始運用分類算法訓(xùn)練樣本之前的一個關(guān)鍵預(yù)處理步驟。
降維有兩種方法：
特征選擇(feature selection)，它是對原始特征利用一些評估函數(shù)獨立評估，按照評估結(jié)果高低排序，選擇那些評估值較高的特征。常用的特征選擇方法有詞頻信息、互信息、信息增益和卡方檢驗等
特征抽取(feature detection)，它是把原始特征映射到低維空間，這些被稱為二次特征 (比如，奇異值分解后得到的lsi)，從而生成模型產(chǎn)生的新特征。特征抽取方法比較常用的是lsa、plsa和lda等。
【注意】 特征選擇和特征權(quán)重值計算是不同的，前者是根據(jù)特征對分類的重要程度來實現(xiàn)降維的手段，而后者是用于區(qū)分向量，實現(xiàn)分類算法中的相似度判斷。它們是兩個階段的不同處理方法。特征權(quán)重值最典型的是tf-idf。
特征選擇(feature selection)
針對英文純文本的實驗結(jié)果表明：作為特征選擇方法時，卡方檢驗和信息增益的效果最佳（相同的分類算法，使用不同的特征選擇算法來得到比較結(jié)果）；文檔頻率方法的性能同前兩者大體相當，術(shù)語強度方法性能一般；互信息方法的性能最差。
卡方檢驗(the χ^2 test)
屬于分類c不屬于分類c總計
包含特征tABA+B
不包含特征tCDC+D
總計A+CB+DN
卡方檢驗是通過計算每個特征和每個類別的關(guān)聯(lián)程度，然后選擇那些關(guān)聯(lián)程度高的特征來實現(xiàn)降維。其基本思想就是衡量實際值與理論值的偏差來確定理論的正確與否。
χ2(t,c)=N×(AD?BC)2(A+C)×(B+D)×(A+B)×(C+D)
其中，t是具體的每個特征(比如詞)，c是類別號。
信息增益法(information gain)
信息增益是通過計算每個特征對分類貢獻的信息量，貢獻越大信息增益越大，然后可以選擇那些信息增益較高的特征實現(xiàn)降維。
信息熵定義：
H(C)=?∑i=1mP(ci)logP(ci)
其中，ci是類別變量C可能的取值，P(ci)是各個類別出現(xiàn)的概率。
條件熵定義：
H(C|T)=P(t)H(C|t)+P(tˉ)H(C|tˉ)=?P(t)∑i=1nP(Ci|t)log2P(Ci|t)?P(tˉ)∑i=1nP(Ci|tˉ)log2P(Ci|tˉ)
其中，帶tˉ的值表示特征t不出現(xiàn)的情況。
特征t給系統(tǒng)帶來的信息增益是系統(tǒng)原本的熵與固定特征T后的條件熵之差。
G(t,c)=H(T)?H(T|C)
信息增益也是考慮了特征出現(xiàn)和不出現(xiàn)兩種情況，與卡方檢驗一樣，是比較全面的，因而效果不錯。但信息增益最大的問題還在于它只能考察特征對整個系統(tǒng)的貢獻，而不能具體到某個類別上，這就使得它只適合用來做所謂“全局”的特征選擇（指所有的類都使用相同的特征集合），而無法做“本地”的特征選擇（每個類別有自己的特征集合，因為有的詞，對這個類別很有區(qū)分度，對另一個類別則無足輕重）。
分類模型
在訓(xùn)練階段，就是利用各種分類算法對轉(zhuǎn)化后的文本向量估計模型。常用的分類算法有樸素貝葉斯、knn、決策樹、神經(jīng)網(wǎng)絡(luò)和svm等。
一些基本概念：
輸入空間 為n維向量的集合 X?Rn，其中向量 x∈X， x=(w1,…,wn)，而 wi 是文檔向量x的一個特征，比如，詞，或者詞和權(quán)重的二元組。
輸出空間 為類標號集合，可以是二元分類 Y={+1,?1}，或者多元分類 Y={y1,…,ym}。
訓(xùn)練數(shù)據(jù) 為一組根據(jù)未知分布 P(x,y) 獨立采樣(i.i.d)的數(shù)據(jù)集合，由輸入向量與輸出類標號對組成D={(x1,y1),…,(xl,yl)}。
假設(shè) (hypothesis)：計算機對訓(xùn)練集背后的真實模型（真實的分類規(guī)則）的猜測稱為假設(shè)?？梢园颜鎸嵉姆诸愐?guī)則想像為一個目標函數(shù)，我們的假設(shè)則是另一個函數(shù)，假設(shè)函數(shù)在所有的訓(xùn)練數(shù)據(jù)上都得出與真實函數(shù)相同（或足夠接近）的結(jié)果。
監(jiān)督學(xué)習(xí)方法可以分為生成方法和判別方法，所學(xué)到的模型分別成為生成模型(generative model)和判別模型(discriminative model)。
生成方法由訓(xùn)練數(shù)據(jù)學(xué)習(xí)聯(lián)合概率分布P(X,Y)，然后求得條件概率分布P(Y|X)作為預(yù)測的模型，即生成模型：
P(Y|X)=P(X,Y)P(X)
這樣的方法之所以稱作生成模型，是因為模型表示了給定輸入X產(chǎn)生輸出Y的生成關(guān)系。典型的生成模型有：樸素貝葉斯法和隱馬爾科夫模型。
判別方法直接學(xué)習(xí)決策函數(shù)f(X)或者條件概率分布P(Y|X)作為預(yù)測模型，即判別模型。判別方法關(guān)心的是對給定的輸入X，應(yīng)該預(yù)測什么樣的輸出Y。典型的判別模型有：knn、決策樹、邏輯回歸、EM、SVM、各種boosting算法等等。
樸素貝葉斯
根據(jù)條件獨立性假設(shè)，Y=ck類別的后驗概率正比于該類別的先驗概率和條件概率的乘積：
P(Y=ck|X=x)=P(Y=ck)P(X=x|Y=ck)P(X=x)∝P(Y=ck)∏i=1nP(wi|Y=ck)
根據(jù) 極大后驗概率假設(shè)(MAP, Maximum a posteriori probability hypothesis)，使得后驗概率P(Y=ck|X=x)最大的那個類別號誤差最小。一般避免乘法導(dǎo)致浮點數(shù)溢出，可以轉(zhuǎn)換為對數(shù)計算，不改變凸函數(shù)性質(zhì)：
y=argmaxckP(Y=ck)∏i=1nP(wi|Y=ck)=argmaxcklogP(Y=ck)+∑i=1nlogP(wi|Y=ck)
實際的 參數(shù)計算 時會加入Laplace平滑：
P(Y=ck)=N(ck)∑mi=1N(ci)≈1+N(ck)|c|+∑mi=1N(ci)
其中，N(ck)是類別 ck 的文檔的總數(shù)，|c|是分類總數(shù)。
P(wi|Y=ck)=N(wi,ck)∑nk=1N(wk,ck)≈1+N(wi,ck)|w|+∑nk=1N(wk,ck)
其中，N(wi,ck)表示特征詞wi在類別ck的文檔中出現(xiàn)的次數(shù)，|w|表示所有特征詞總數(shù)。
建立NB分類器有兩種方法，上述是多項式模型(Multinomial model)，還有一種貝努利模型(Bernoulli model)。貝努利模型屬于二值模型，對于每個詞只統(tǒng)計是否出現(xiàn)，而不計算其出現(xiàn)次數(shù)。多項式模型適合處理長文本，而貝努利模型適合處理短文本。貝努利模型對噪聲敏感，所以在使用之前必須要做特征選擇。
SVM
對于一組訓(xùn)練數(shù)據(jù) {(x1,y1),…,(xl,yl)}，其中 x∈Rn，y∈{+1,?1}，在線性可分的情況下會有一個超平面，將這兩類樣本完全分開，并且離超平面最近的向量與超平面之間的距離最大。
f(x)=∑i=1nwixi+b=?w?x?+b
參考
統(tǒng)計學(xué)習(xí)方法, 李航, 4. 樸素貝葉斯
Introduction to IR, 13. Text classification and Naive Bayes
轉(zhuǎn)載自：http://blog.jqian.net/post/classification.html#content
