1、搜索引擎開發實踐第十二講支持向量機文本分類主講人： 概 述支持向量機支持向量機文本分類支持向量機文本分類實現支持向量機實現多類分類問題基于錯誤校正輸出編碼的多類分類作業：實現基于錯誤校正輸出編碼的多類分類2作業講解：實現CHI平均期望值計算int N = schema.getNumberOfClasses();/類別數int classCnt = new intN;double totalCnt = 0.0;/文檔總數for (int c = 0; c N; c+) classCntc = index.size(schema.getClassName(c);totalCnt += classC

2、ntc;for (Iterator i = index.featureIterator(); i.hasNext();) Feature f = i.next();int a = new intN;int b = new intN;int c = new intN;int d = new intN;double chiScore = new doubleN;/按類別的CHIfor (int ci = 0; ci N; ci+) aci = index.size(f, schema.getClassName(ci);cci = classCntci - aci;for (int ci = 0;

3、ci N; ci+) for (int ck = 0; ck N; ck+) if (ci != ck) bci += ack;dci += cck;ContingencyTable ct = new ContingencyTable(aci, bci,cci, dci);chiScoreci = ct.getChiSquared();double chiAvg = 0;/ CHI平均期望值for (int ci = 0; ci N; ci+) chiAvg += (classCntci / totalCnt) * chiScoreci;filter.addFeature(chiAvg, f)

4、;3解決分成兩類問題的線性分類器考慮把點分成兩類定義線性可分性:在二維空間中，可以通過一條線分割例如：好，差詞在文檔中出現的次數作為判斷情感極性的依據在高維空間中，需要超平面Class 差評Class 好評好 出現次數差 出現次數x1-x2=0輸出 +1輸出 -1文檔x1x24線性規劃(Linear programming)找到a,b,c, 使得ax1 + bx2 c 對于紅色點ax1 + bx2 c對于綠色點這個函數叫做判別函數(discriminant function)5判別函數假設有N個點在p維特征空間X=x1, x2, , xp中分別屬于兩類：C+和C-。要解決的問題是找到一個判別函

5、數f(x1, x2, , xp)判別出兩類，對于C+類的點返回正值，而對于C-類的點返回負值。如果判別函數是線性的，則可以把判別函數看成如下形式：f(x1, x2, , xp)= w1*x1+w2*x2+wp*xp+b假設向量w=(w1, w2, , wp)，向量x=(x1, x2, , xp)。用表示向量w和x之間的內積(inner product)，或者叫做點乘積。因此這個函數的向量化表示g(x)的形式是：g(x)=sign(+b)也記做wTx，也就是向量w的轉置點乘向量x。這里sign是符號函數。這里符號函數sign(a)的定義是當a 0，則返回1；當a=0，則返回0；當a0，則返回-1

6、。有時候也把符號函數寫作。一般把w稱作權重向量(weight vector)，把b叫做偏移量(bias)。+b=0所定義的面叫做超平面(hyperplane)。 6判別式模型與生成式模型訓練集 (x1,y1), ,(xn,yn)判別式模型用判別函數建立模型例如:支持向量機生成式模型估計聯合概率P(X,Y)例如:貝葉斯、隱馬爾科夫模型7線性分類器許多常見的文本分類是線性分類器對于可分的問題，有無數可分的 超平面。選擇哪一個？線性不可分的問題怎么辦?Class 1Class 2Class 1Class 28支持向量機(SVM)一般來說，如果超平面遠離分類訓練集中的點應該會最小化對新數據錯誤分類的風

7、險。所以選取w和b，使得超平面到最近點的距離最大，或者說最大化邊界m。 Class 1Class 2m9最大化間隔點i到平面w,b的距離d(w,b , xi) = | w xi + b | / |w| 選取w和b，使得超平面到最近點的距離最大。也就是求解：max(w,b) (mini d(w,b , xi)， 這里的|w|叫做向量w的歐幾里德范數(Euclidean norm)，計算公式是：對于距離超平面最近的C+類的點x+來說wT x+b=1；對于距離超平面最近的C- 類的點x-來說wT x-+b = -1。因此： max(w,b) (mini d(w,b , xi)= 10約束條件訓練集

8、(xi, yi)i=1.n, xiRp, yi -1, 1 可以通過超平面分隔。 因此對每個訓練實例(xi, yi):wTxi + b -1 if yi = -1wTxi + b 1 if yi = 1yi(wTxi + b) 111最大化間隔也就是求解下面這個基本的問題:在yi(wT xi + b)1的條件下，求最小值：滿足相等約束條件的這些點叫做支持向量(support vector)，因為這些點在支持(約束)超平面。 線性約束下的優化問題 12線性約束下的優化問題 用拉格朗日乘子(Lagrange multiplier) 來解決線性約束下的優化問題。把一個拉格朗日乘子的函數整合進需要求最

9、大或最小值的表達式。例如求極值： f (x,y) = x+2y 有約束條件：g(x,y) = x2+y2-4 = 0則對應拉格朗日函數：L(x,y,) = x+2y+(x2+y2-4)求導數： =1+2x=0 (1) =2+2y=0 (2) =x2+y2-4=0 (3)首先根據(1)，(2) ，(3)解出拉格朗日乘子的值，然后就可以計算出f (x,y)的最小值。 13求解最大間隔n個點對應n個約束條件，因此引入n個拉格朗日乘子1,n L=求解最大間隔等價于求解對偶問題：i 0和 的條件下可以通過二次規劃(Quadratic programming)求解i 然后得出 b=yi wTxi注意：僅僅

10、對于支持向量點i 0，對于非支持向量點i = 014通過伽瑪矩陣求解拉格朗日方程伽瑪矩陣(Gramm matrix) G = xiTxji,j=1:n伽瑪矩陣中的元素 Gij=xiTxj衡量了任意兩個訓練點之間的距離(相似度)伽瑪矩陣是一個對稱方形矩陣，也就是元素以對角線為對稱軸對應相等的矩陣。15線性SVM總結分類器是一個分隔超平面最重要的訓練點是支持向量，支持向量定義了超平面二次優化算法可以識別哪些訓練點 xi 是支持向量，也就是帶有非零的拉格朗日乘子 i的訓練點 在這個問題的對偶公式和判別函數中，訓練點都只出現在內積中: 尋找 1N 使得Q() =i - ijyiyjxiTxj 最大化，

11、并且 (1) iyi = 0(2) 0 i C for all if(x) = iyixiTx + b16計算兩個稀疏向量的點積 維度有個編號，叫做Index，對應的值叫做Value。為了節省空間不采用哈希表儲存。而是將index全部按升序排列，然后通過歸并兩個排好序的數組來計算。計算向量x和y的點積的實現代碼：static double scalarProduct(Node x, Node y)double sum = 0;int xlen = x.length;int ylen = y.length;int i = 0;int j = 0;while(i xlen & j yj.index

12、)+j;else+i;return sum; 17對二維空間分類的例子在二維空間中有4個點，對應的標記值是y。四個點描述如下： x1=(-2,-2) y1= +1x2=(-1,1) y2= +1x3=(1,1) y3= -1x4=(2,-2) y4= -1在i=0的條件下求下面這個拉格朗日函數的最大值： =1+2+3+4 - 412 - 22 - 32 - 442 - 413 - 424 18伽瑪矩陣伽瑪矩陣(Gramm matrix) G = xiTxji,j=1:l=x1Tx1 x1Tx2 x1Tx3 x1Tx4 x2Tx1 x2Tx2 x2Tx3 x2Tx4x3Tx1 x3Tx2 x3T

13、x3 x3Tx4x4Tx1 x4Tx2 x4Tx3 x4Tx4=8 0 -4 00 2 0 -4-4 0 2 00 -4 0 819求解判別函數得到：1=0 2= 3= 4=0因此支持向量是x2和x3。b=y2 wTx2=0 x1x2x3x4超平面間隔20多類分類SVM只能輸出兩個可能的分類結果 (1 和 -1)如何解決多類分類問題？答案: 有N類，學習N個SVMSVM 1 學習 “Output=1” vs “Output != 1”SVM 2 學習 “Output=2” vs “Output != 2”:SVM N 學習 “Output=N” vs “Output != N”計算文檔屬于每個

14、類別的隸屬度，然后取最大隸屬度對應的類別21取最大隸屬度對應的類別/ 輸入每個類別的隸屬度組成的數組/ 得到文檔的所屬類別IDprivate int singleCategory(double simRatio) int catID = 0;double maxNum = simRatiocatID;for (int i = 1; i maxNum) maxNum = simRatioi;catID = i;return catID;22錯誤校正輸出編碼(Error Correcting Output Coding)m = 4 個類別politics, sports, business, ar

15、ts分配唯一的n位向量給每個類名這里n log2m第i個位向量作為類名i的唯一的編碼位矩陣記作C對每列構建獨立的二元分類器這里是10個分類器正類文本是Cij = 1對應的類別負類是Cij = 0對應的類別例如：第三個分類器把sports,arts作為正類，politics,business作為負類類名編碼politics0110110001sports0001111100business1010101101arts100001101023通過插件分類器判斷文檔類別預測某一位的值的分類器叫做插件分類器，一個插件分類器預測文檔屬于某個類別的子集。根據1, 2 ,n來判斷文檔的類別計算文檔x的類別時

16、, 先生成一個n位的向量(x) = 1(x), 2(x), , n(x)很有可能，生成的位向量(x)不是C中的一行，但是可能更像某些行也就是和某些行的海明距離更近argmini HamingDistance(Ci,(x)然后根據海明距離判斷(x)和哪行最相似假設Ci和(x)最相似，則第i個類別作為文檔x的類別例如，如果生成的位向量是(x) = 1010111101，則把這篇文檔分到business類24計算海明距離海明距離是長度相同的字符串或二進制數組對應位有差別的數量。例如：1011101 和 1001001 的海明距離是2。public static int hammingXOR(long

17、 l1, long l2) long lxor = l1 l2; /按位異或return BitUtil.pop(lxor); /計算1的個數 A = 1 1 1 0B = 0 1 0 0A XOR B = 1 0 1 01的個數(海明距離) 225文本分類整體架構訓練集TF DF 文檔表示詞SVMLightsvm_learnlabel分類特征測試文本 文檔表示詞TF DF SVMLightsvm_classifySVM模型判斷類別特征/權重特征/權重26文檔表示詞頻(TF)每個不同的詞對應一個特征詞在文檔中出現的次數作為這個特征維度對應的值文檔頻率的倒數IDF(Invert Document Frequence)DF是包含指定詞的文檔數IDF是DF的倒數例如“的”在100文檔中的40篇文檔中出現過，則文檔頻率DF(Document Frequence)是40，IDF是1/40。“的”在第一篇文檔中出現了15次，則TF*IDF(的) = 15 * 1/40=0.375。另外一個詞 “反腐