這回是幫自己家小妞的網(wǎng)店做的店標,宣傳什么的,所以風格相似恰恰是我想要的。

 

網(wǎng)店的Logo。那大腿不是別人的，正是韓國歌星寶兒……

她跟我說上面這張圖最大的問題就在于太有夜店風格，與她的店不符。不過用著用著，她自己倒也喜歡上了。

這個是剛出爐的5月新款的預告，照片里的人可全是她……

在文本分類的過程中，特征（也可以簡單的理解為“詞”）從人類能夠理解的形式轉(zhuǎn)換為計算機能夠理解的形式時，實際上經(jīng)過了兩步驟的量化——特征選擇階段的重要程度量化和將具體文本轉(zhuǎn)化為向量時的特征權(quán)重量化。初次接觸文本分類的人很容易混淆這兩個步驟使用的方法和各自的目的，因而我經(jīng)常聽到讀者有類似“如何使用TFIDF做特征選擇”或者“卡方檢驗量化權(quán)重后每篇文章都一樣”等等困惑。

文本分類本質(zhì)上也是一個模式識別的問題，因此我想借用一個更直觀的例子來說說特征選擇和權(quán)重量化到底各自是什么東西，當然，一旦解釋清楚，你馬上就會覺得文本分類這東西實在白癡，實在沒什么技術(shù)含量，你也就不會再繼續(xù)看我的技術(shù)博客，不過我不擔心，因為你已經(jīng)踏上了更光明的道路（笑），我高興還來不及。

想想通過指紋來識別一個人的身份，只看一個人的指紋，當然說不出他姓甚名誰，識別的過程實際上是比對的過程，要與已有的指紋庫比較，找出相同的，或者說相似到一定程度的那一個。

首要的問題是，人的指紋太復雜，包含太多的位置和幾何形狀，要完全重現(xiàn)一個人的指紋，存儲和計算都是大麻煩。因此第一步總是一個特征選擇的問題，我們把全人類的指紋都統(tǒng)計一下，看看哪幾個位置能夠最好的區(qū)分不同的人。顯然不同的位置效果很不一樣，在有的位置上，我的指紋是是什么形狀，其他人也大都是這個形狀，這個位置就不具有區(qū)分度，或者說不具有表征性，或者說，對分類問題來說，它的重要程度低。這樣的位置我們就傾向于在識別的時候根本不看它，不考慮它。

那怎么看誰重要誰不重要呢？這就依賴于具體的選擇方法如何來量化重要程度，對卡方檢驗和信息增益這類方法來說，量化以后的得分越大的特征就越重要（也就是說，有可能有些方法，是得分越小的越重要）。

比如說你看10個位置，他們的重要程度分別是：

   1 2   3   4   5 6   7 8 9  10

（20，5，10，20，30，15，4，3，7， 3）

顯然第1，第3，4，5，6個位置比其他位置更重要，而相對的，第1個位置又比第3個位置更重要。

識別時，我們只在那些重要的位置上采樣。當今的指紋識別系統(tǒng)，大都只用到人指紋的5個位置（驚訝么？只要5個位置的信息就可以區(qū)分60億人），這5個位置就是經(jīng)過特征選擇過程而得以保留的系統(tǒng)特征集合。假設(shè)這個就是剛才的例子，那么該集合應(yīng)該是：

（第1個位置，第3個位置，第4個位置，第5個位置，第6個位置）

當然，具體的第3個位置是指紋中的哪個位置你自己總得清楚。

確定了這5個位置之后，就可以把一個人的指紋映射到這個只有5個維度的空間中，我們就把他在5個位置上的幾何形狀分別轉(zhuǎn)換成一個具體的值，這就是特征權(quán)重的計算。依據(jù)什么來轉(zhuǎn)換，就是你選擇的特征權(quán)重量化方法，在文本分類中，最常用的就是TFIDF。

我想一定是“權(quán)重“這個詞誤導了所有人，讓大家以為TFIDF計算出的值代表的是特征的重要程度，其實完全不是。例如我們有一位男同學，他的指紋向量是：

（10，3，4，20，5）

你注意到他第1個位置的得分（10）比第3個位置的得分（3）高，那么能說第1個位置比第3個位置重要么？如果再有一位女同學，她的指紋向量是：

（10，20，4，20，5）

看看，第1個位置得分（10）又比第3個位置（20）低了，那這兩個位置到底哪個更重要呢？答案是第1個位置更重要，但這不是在特征權(quán)重計算這一步體現(xiàn)出來的，而是在我們特征選擇的時候就確定了，第1個位置比第3個位置更重要。

因此要記住，通過TFIDF計算一個特征的權(quán)重時，該權(quán)重體現(xiàn)出的根本不是特征的重要程度！

那它代表什么？再看看兩位同學的指紋，放到一起：

（10， 3，4，20，5）

（10，20，4，20，5）

在第三個位置上女同學的權(quán)重高于男同學，這不代表該女同學在指紋的這個位置上更“優(yōu)秀“（畢竟，指紋還有什么優(yōu)秀不優(yōu)秀的分別么，笑），也不代表她的這個位置比男同學的這個位置更重要，3和20這兩個得分，僅僅代表他們的”不同“。

在文本分類中也是如此，比如我們的系統(tǒng)特征集合只有兩個詞：

（經(jīng)濟，發(fā)展）

這兩個詞是使用卡方檢驗（特征選擇）選出來的，有一篇文章的向量形式是

（2，5）

另一篇

（3，4）

這兩個向量形式就是用TFIDF算出來的，很容易看出兩篇文章不是同一篇，為什么？因為他們的特征權(quán)重根本不一樣，所以說權(quán)重代表的是差別，而不是優(yōu)劣。想想你說“經(jīng)濟這個詞在第二篇文章中得分高，因此它在第二篇文章中比在第一篇文章中更重要“，這句話代表什么意義呢？你自己都不知道吧（笑）。

所以，當再說起使用TFIDF來計算特征權(quán)重時，最好把“權(quán)重“這個字眼忘掉，我們就把它說成計算得分好了（甚至”得分“也不太好，因為人總會不自覺的認為，得分高的就更重要），或者就僅僅說成是量化。

如此，你就再也不會拿TFIDF去做特征選擇了。

小Tips：為什么有的論文里確實使用了TFIDF作特征選擇呢？

嚴格說來并不是不可以，而且嚴格說來只要有一種方法能夠從一堆特征中挑出少數(shù)的一些，它就可以叫做一種特征選擇方法，就連“隨機選取一部分“都算是一種，而且效果并沒有差到驚人的地步哦！還是可以分對一大半的哦！所以有的人就用TFIDF的得分來把特征排排序，取得分最大的幾個進入系統(tǒng)特征集合，效果也還行（畢竟，連隨機選取效果也都還行），怎么說呢，他們愿意這么干就這么干吧。就像咱國家非得實行戶口制度，這個制度說不出任何道理，也不見他帶來任何好處，但不也沒影響二十一世紀成為中國的世紀么，呵呵。

又小忙了幾天。打算寫一篇澄清特征選擇和特征權(quán)重計算中許多容易誤解的問題的文章，不知大家有沒有興趣。

從 SVM的那幾張圖可以看出來，SVM是一種典型的兩類分類器，即它只回答屬于正類還是負類的問題。而現(xiàn)實中要解決的問題，往往是多類的問題（少部分例外，例如垃圾郵件過濾，就只需要確定“是”還是“不是”垃圾郵件），比如文本分類，比如數(shù)字識別。如何由兩類分類器得到多類分類器，就是一個值得研究的問題。

還以文本分類為例，現(xiàn)成的方法有很多，其中一種一勞永逸的方法，就是真的一次性考慮所有樣本，并求解一個多目標函數(shù)的優(yōu)化問題，一次性得到多個分類面，就像下圖這樣：

多個超平面把空間劃分為多個區(qū)域，每個區(qū)域?qū)?yīng)一個類別，給一篇文章，看它落在哪個區(qū)域就知道了它的分類。

看起來很美對不對？只可惜這種算法還基本停留在紙面上，因為一次性求解的方法計算量實在太大，大到無法實用的地步。

稍稍退一步，我們就會想到所謂“一類對其余”的方法，就是每次仍然解一個兩類分類的問題。比如我們有5個類別，第一次就把類別1的樣本定為正樣本，其余2，3，4，5的樣本合起來定為負樣本，這樣得到一個兩類分類器，它能夠指出一篇文章是還是不是第1類的；第二次我們把類別2 的樣本定為正樣本，把1，3，4，5的樣本合起來定為負樣本，得到一個分類器，如此下去，我們可以得到5個這樣的兩類分類器（總是和類別的數(shù)目一致）。到了有文章需要分類的時候，我們就拿著這篇文章挨個分類器的問：是屬于你的么？是屬于你的么？哪個分類器點頭說是了，文章的類別就確定了。這種方法的好處是每個優(yōu)化問題的規(guī)模比較小，而且分類的時候速度很快（只需要調(diào)用5個分類器就知道了結(jié)果）。但有時也會出現(xiàn)兩種很尷尬的情況，例如拿一篇文章問了一圈，每一個分類器都說它是屬于它那一類的，或者每一個分類器都說它不是它那一類的，前者叫分類重疊現(xiàn)象，后者叫不可分類現(xiàn)象。分類重疊倒還好辦，隨便選一個結(jié)果都不至于太離譜，或者看看這篇文章到各個超平面的距離，哪個遠就判給哪個。不可分類現(xiàn)象就著實難辦了，只能把它分給第6個類別了……更要命的是，本來各個類別的樣本數(shù)目是差不多的，但“其余”的那一類樣本數(shù)總是要數(shù)倍于正類（因為它是除正類以外其他類別的樣本之和嘛），這就人為的造成了上一節(jié)所說的“數(shù)據(jù)集偏斜”問題。

因此我們還得再退一步，還是解兩類分類問題，還是每次選一個類的樣本作正類樣本，而負類樣本則變成只選一個類（稱為“一對一單挑”的方法，哦，不對，沒有單挑，就是“一對一”的方法，呵呵），這就避免了偏斜。因此過程就是算出這樣一些分類器，第一個只回答“是第1類還是第2類”，第二個只回答“是第1類還是第3類”，第三個只回答“是第1類還是第4類”，如此下去，你也可以馬上得出，這樣的分類器應(yīng)該有5 X 4/2=10個（通式是，如果有k個類別，則總的兩類分類器數(shù)目為k(k-1)/2）。雖然分類器的數(shù)目多了，但是在訓練階段（也就是算出這些分類器的分類平面時）所用的總時間卻比“一類對其余”方法少很多，在真正用來分類的時候，把一篇文章扔給所有分類器，第一個分類器會投票說它是“1”或者“2”，第二個會說它是“1”或者“3”，讓每一個都投上自己的一票，最后統(tǒng)計票數(shù)，如果類別“1”得票最多，就判這篇文章屬于第1類。這種方法顯然也會有分類重疊的現(xiàn)象，但不會有不可分類現(xiàn)象，因為總不可能所有類別的票數(shù)都是0。看起來夠好么？其實不然，想想分類一篇文章，我們調(diào)用了多少個分類器？10個，這還是類別數(shù)為5的時候，類別數(shù)如果是1000，要調(diào)用的分類器數(shù)目會上升至約500,000個（類別數(shù)的平方量級）。這如何是好？

看來我們必須再退一步，在分類的時候下功夫，我們還是像一對一方法那樣來訓練，只是在對一篇文章進行分類之前，我們先按照下面圖的樣子來組織分類器（如你所見，這是一個有向無環(huán)圖，因此這種方法也叫做DAG SVM）

這樣在分類時,我們就可以先問分類器“1對5”（意思是它能夠回答“是第1類還是第5類”），如果它回答5，我們就往左走，再問“2對5”這個分類器，如果它還說是“5”，我們就繼續(xù)往左走，這樣一直問下去，就可以得到分類結(jié)果。好處在哪？我們其實只調(diào)用了4個分類器（如果類別數(shù)是k，則只調(diào)用k-1個），分類速度飛快，且沒有分類重疊和不可分類現(xiàn)象！缺點在哪？假如最一開始的分類器回答錯誤（明明是類別1的文章，它說成了5），那么后面的分類器是無論如何也無法糾正它的錯誤的（因為后面的分類器壓根沒有出現(xiàn)“1”這個類別標簽），其實對下面每一層的分類器都存在這種錯誤向下累積的現(xiàn)象。。

不過不要被DAG方法的錯誤累積嚇倒，錯誤累積在一對其余和一對一方法中也都存在，DAG方法好于它們的地方就在于，累積的上限，不管是大是小，總是有定論的，有理論證明。而一對其余和一對一方法中，盡管每一個兩類分類器的泛化誤差限是知道的，但是合起來做多類分類的時候，誤差上界是多少，沒人知道，這意味著準確率低到0也是有可能的，這多讓人郁悶。

而且現(xiàn)在DAG方法根節(jié)點的選取（也就是如何選第一個參與分類的分類器），也有一些方法可以改善整體效果，我們總希望根節(jié)點少犯錯誤為好，因此參與第一次分類的兩個類別，最好是差別特別特別大，大到以至于不太可能把他們分錯；或者我們就總?cè)≡趦深惙诸愔姓_率最高的那個分類器作根節(jié)點，或者我們讓兩類分類器在分類的時候，不光輸出類別的標簽，還輸出一個類似“置信度”的東東，當它對自己的結(jié)果不太自信的時候，我們就不光按照它的輸出走，把它旁邊的那條路也走一走，等等。

大Tips：SVM的計算復雜度

使用SVM進行分類的時候，實際上是訓練和分類兩個完全不同的過程，因而討論復雜度就不能一概而論，我們這里所說的主要是訓練階段的復雜度，即解那個二次規(guī)劃問題的復雜度。對這個問題的解，基本上要劃分為兩大塊，解析解和數(shù)值解。

解析解就是理論上的解，它的形式是表達式，因此它是精確的，一個問題只要有解（無解的問題還跟著摻和什么呀，哈哈），那它的解析解是一定存在的。當然存在是一回事，能夠解出來，或者可以在可以承受的時間范圍內(nèi)解出來，就是另一回事了。對SVM來說，求得解析解的時間復雜度最壞可以達到O(N_sv³)，其中N_sv是支持向量的個數(shù)，而雖然沒有固定的比例，但支持向量的個數(shù)多少也和訓練集的大小有關(guān)。

數(shù)值解就是可以使用的解，是一個一個的數(shù)，往往都是近似解。求數(shù)值解的過程非常像窮舉法，從一個數(shù)開始，試一試它當解效果怎樣，不滿足一定條件（叫做停機條件，就是滿足這個以后就認為解足夠精確了，不需要繼續(xù)算下去了）就試下一個，當然下一個數(shù)不是亂選的，也有一定章法可循。有的算法，每次只嘗試一個數(shù)，有的就嘗試多個，而且找下一個數(shù)字（或下一組數(shù)）的方法也各不相同，停機條件也各不相同，最終得到的解精度也各不相同，可見對求數(shù)值解的復雜度的討論不能脫開具體的算法。

一個具體的算法，Bunch-Kaufman訓練算法，典型的時間復雜度在O(N_sv³+LN_sv²+dLN_sv)和O(dL²)之間，其中N_sv是支持向量的個數(shù)，L是訓練集樣本的個數(shù)，d是每個樣本的維數(shù)（原始的維數(shù)，沒有經(jīng)過向高維空間映射之前的維數(shù)）。復雜度會有變化，是因為它不光跟輸入問題的規(guī)模有關(guān)（不光和樣本的數(shù)量，維數(shù)有關(guān)），也和問題最終的解有關(guān)（即支持向量有關(guān)），如果支持向量比較少，過程會快很多，如果支持向量很多，接近于樣本的數(shù)量，就會產(chǎn)生O(dL²)這個十分糟糕的結(jié)果（給10，000個樣本，每個樣本1000維，基本就不用算了，算不出來，呵呵，而這種輸入規(guī)模對文本分類來說太正常了）。

這樣再回頭看就會明白為什么一對一方法盡管要訓練的兩類分類器數(shù)量多，但總時間實際上比一對其余方法要少了，因為一對其余方法每次訓練都考慮了所有樣本（只是每次把不同的部分劃分為正類或者負類而已），自然慢上很多。

前文提到過，除了開方檢驗（CHI）以外，信息增益（IG，Information Gain）也是很有效的特征選擇方法。但凡是特征選擇，總是在將特征的重要程度量化之后再進行選擇，而如何量化特征的重要性，就成了各種方法間最大的不同。開方檢驗中使用特征與類別間的關(guān)聯(lián)性來進行這個量化，關(guān)聯(lián)性越強，特征得分越高，該特征越應(yīng)該被保留。

在信息增益中，重要性的衡量標準就是看特征能夠為分類系統(tǒng)帶來多少信息，帶來的信息越多，該特征越重要。

因此先回憶一下信息論中有關(guān)信息量（就是“熵”）的定義。說有這么一個變量X，它可能的取值有n多種，分別是x₁，x₂，……，x_n，每一種取到的概率分別是P₁，P₂，……，P_n，那么X的熵就定義為：

意思就是一個變量可能的變化越多（反而跟變量具體的取值沒有任何關(guān)系，只和值的種類多少以及發(fā)生概率有關(guān)），它攜帶的信息量就越大（因此我一直覺得我們的政策法規(guī)信息量非常大，因為它變化很多，基本朝令夕改，笑）。

對分類系統(tǒng)來說，類別C是變量，它可能的取值是C₁，C₂，……，C_n，而每一個類別出現(xiàn)的概率是P(C₁)，P(C₂)，……，P(C_n)，因此n就是類別的總數(shù)。此時分類系統(tǒng)的熵就可以表示為：

有同學說不好理解呀，這樣想就好了，文本分類系統(tǒng)的作用就是輸出一個表示文本屬于哪個類別的值，而這個值可能是C₁，C₂，……，C_n，因此這個值所攜帶的信息量就是上式中的這么多。

信息增益是針對一個一個的特征而言的，就是看一個特征t，系統(tǒng)有它和沒它的時候信息量各是多少，兩者的差值就是這個特征給系統(tǒng)帶來的信息量，即增益。系統(tǒng)含有特征t的時候信息量很好計算，就是剛才的式子，它表示的是包含所有特征時系統(tǒng)的信息量。

問題是當系統(tǒng)不包含t時，信息量如何計算？我們換個角度想問題，把系統(tǒng)要做的事情想象成這樣：說教室里有很多座位，學生們每次上課進來的時候可以隨便坐，因而變化是很大的（無數(shù)種可能的座次情況）；但是現(xiàn)在有一個座位，看黑板很清楚，聽老師講也很清楚，于是校長的小舅子的姐姐的女兒托關(guān)系（真輾轉(zhuǎn)啊），把這個座位定下來了，每次只能給她坐，別人不行，此時情況怎樣？對于座次的可能情況來說，我們很容易看出以下兩種情況是等價的：（1）教室里沒有這個座位；（2）教室里雖然有這個座位，但其他人不能坐（因為反正它也不能參與到變化中來，它是不變的）。

對應(yīng)到我們的系統(tǒng)中，就是下面的等價：（1）系統(tǒng)不包含特征t；（2）系統(tǒng)雖然包含特征t，但是t已經(jīng)固定了，不能變化。

我們計算分類系統(tǒng)不包含特征t的時候，就使用情況（2）來代替，就是計算當一個特征t不能變化時，系統(tǒng)的信息量是多少。這個信息量其實也有專門的名稱，就叫做“條件熵”，條件嘛，自然就是指“t已經(jīng)固定“這個條件。

但是問題接踵而至，例如一個特征X，它可能的取值有n多種（x₁，x₂，……，x_n），當計算條件熵而需要把它固定的時候，要把它固定在哪一個值上呢？答案是每一種可能都要固定一下，計算n個值，然后取均值才是條件熵。而取均值也不是簡單的加一加然后除以n，而是要用每個值出現(xiàn)的概率來算平均（簡單理解，就是一個值出現(xiàn)的可能性比較大，固定在它上面時算出來的信息量占的比重就要多一些）。

因此有這樣兩個條件熵的表達式：

這是指特征X被固定為值x_i時的條件熵，

這是指特征X被固定時的條件熵，注意與上式在意義上的區(qū)別。從剛才計算均值的討論可以看出來，第二個式子與第一個式子的關(guān)系就是：

具體到我們文本分類系統(tǒng)中的特征t，t有幾個可能的值呢？注意t是指一個固定的特征，比如他就是指關(guān)鍵詞“經(jīng)濟”或者“體育”，當我們說特征“經(jīng)濟”可能的取值時，實際上只有兩個，“經(jīng)濟”要么出現(xiàn)，要么不出現(xiàn)。一般的，t的取值只有t（代表t出現(xiàn)）和（代表t不出現(xiàn)），注意系統(tǒng)包含t但t 不出現(xiàn)與系統(tǒng)根本不包含t可是兩回事。

因此固定t時系統(tǒng)的條件熵就有了，為了區(qū)別t出現(xiàn)時的符號與特征t本身的符號，我們用T代表特征，而用t代表T出現(xiàn)，那么：

與剛才的式子對照一下，含義很清楚對吧，P(t)就是T出現(xiàn)的概率，就是T不出現(xiàn)的概率。這個式子可以進一步展開，其中的

另一半就可以展開為：

因此特征T給系統(tǒng)帶來的信息增益就可以寫成系統(tǒng)原本的熵與固定特征T后的條件熵之差：

公式中的東西看上去很多，其實也都很好計算。比如P(C_i)，表示類別C_i出現(xiàn)的概率，其實只要用1除以類別總數(shù)就得到了（這是說你平等的看待每個類別而忽略它們的大小時這樣算，如果考慮了大小就要把大小的影響加進去）。再比如P(t)，就是特征T出現(xiàn)的概率，只要用出現(xiàn)過T的文檔數(shù)除以總文檔數(shù)就可以了，再比如P(C_i|t)表示出現(xiàn)T的時候，類別C_i出現(xiàn)的概率，只要用出現(xiàn)了T并且屬于類別C_i的文檔數(shù)除以出現(xiàn)了T的文檔數(shù)就可以了。

從以上討論中可以看出，信息增益也是考慮了特征出現(xiàn)和不出現(xiàn)兩種情況，與開方檢驗一樣，是比較全面的，因而效果不錯。但信息增益最大的問題還在于它只能考察特征對整個系統(tǒng)的貢獻，而不能具體到某個類別上，這就使得它只適合用來做所謂“全局”的特征選擇（指所有的類都使用相同的特征集合），而無法做“本地”的特征選擇（每個類別有自己的特征集合，因為有的詞，對這個類別很有區(qū)分度，對另一個類別則無足輕重）。

看看，導出的過程其實很簡單，沒有什么神秘的對不對。可有的學術(shù)論文里就喜歡把這種本來很直白的東西寫得很晦澀，仿佛只有讀者看不懂才是作者的真正成功。

咱們是新一代的學者，咱們沒有知識不怕被別人看出來，咱們有知識也不怕教給別人。所以咱都把事情說簡單點，說明白點，大家好，才是真的好。

接下來要說的東西其實不是松弛變量本身，但由于是為了使用松弛變量才引入的，因此放在這里也算合適，那就是懲罰因子C。回頭看一眼引入了松弛變量以后的優(yōu)化問題：

注意其中C的位置，也可以回想一下C所起的作用（表征你有多么重視離群點，C越大越重視，越不想丟掉它們）。這個式子是以前做SVM的人寫的，大家也就這么用，但沒有任何規(guī)定說必須對所有的松弛變量都使用同一個懲罰因子，我們完全可以給每一個離群點都使用不同的C，這時就意味著你對每個樣本的重視程度都不一樣，有些樣本丟了也就丟了，錯了也就錯了，這些就給一個比較小的C；而有些樣本很重要，決不能分類錯誤（比如中央下達的文件啥的，笑），就給一個很大的C。

當然實際使用的時候并沒有這么極端，但一種很常用的變形可以用來解決分類問題中樣本的“偏斜”問題。

先來說說樣本的偏斜問題，也叫數(shù)據(jù)集偏斜（unbalanced），它指的是參與分類的兩個類別（也可以指多個類別）樣本數(shù)量差異很大。比如說正類有10，000個樣本，而負類只給了100個，這會引起的問題顯而易見，可以看看下面的圖：

方形的點是負類。H，H₁，H₂是根據(jù)給的樣本算出來的分類面，由于負類的樣本很少很少，所以有一些本來是負類的樣本點沒有提供，比如圖中兩個灰色的方形點，如果這兩個點有提供的話，那算出來的分類面應(yīng)該是H’，H₂’和H₁，他們顯然和之前的結(jié)果有出入，實際上負類給的樣本點越多，就越容易出現(xiàn)在灰色點附近的點，我們算出的結(jié)果也就越接近于真實的分類面。但現(xiàn)在由于偏斜的現(xiàn)象存在，使得數(shù)量多的正類可以把分類面向負類的方向“推”，因而影響了結(jié)果的準確性。

對付數(shù)據(jù)集偏斜問題的方法之一就是在懲罰因子上作文章，想必大家也猜到了，那就是給樣本數(shù)量少的負類更大的懲罰因子，表示我們重視這部分樣本（本來數(shù)量就少，再拋棄一些，那人家負類還活不活了），因此我們的目標函數(shù)中因松弛變量而損失的部分就變成了：

 

其中i=1…p都是正樣本，j=p+1…p+q都是負樣本。libSVM這個算法包在解決偏斜問題的時候用的就是這種方法。

那C₊和C_-怎么確定呢？它們的大小是試出來的（參數(shù)調(diào)優(yōu)），但是他們的比例可以有些方法來確定。咱們先假定說C₊是5這么大，那確定C_-的一個很直觀的方法就是使用兩類樣本數(shù)的比來算，對應(yīng)到剛才舉的例子，C_-就可以定為500這么大（因為10，000：100=100：1嘛）。

但是這樣并不夠好，回看剛才的圖，你會發(fā)現(xiàn)正類之所以可以“欺負”負類，其實并不是因為負類樣本少，真實的原因是負類的樣本分布的不夠廣（沒擴充到負類本應(yīng)該有的區(qū)域）。說一個具體點的例子，現(xiàn)在想給政治類和體育類的文章做分類，政治類文章很多，而體育類只提供了幾篇關(guān)于籃球的文章，這時分類會明顯偏向于政治類，如果要給體育類文章增加樣本，但增加的樣本仍然全都是關(guān)于籃球的（也就是說，沒有足球，排球，賽車，游泳等等），那結(jié)果會怎樣呢？雖然體育類文章在數(shù)量上可以達到與政治類一樣多，但過于集中了，結(jié)果仍會偏向于政治類！所以給C₊和C_-確定比例更好的方法應(yīng)該是衡量他們分布的程度。比如可以算算他們在空間中占據(jù)了多大的體積，例如給負類找一個超球——就是高維空間里的球啦——它可以包含所有負類的樣本，再給正類找一個，比比兩個球的半徑，就可以大致確定分布的情況。顯然半徑大的分布就比較廣，就給小一點的懲罰因子。

但是這樣還不夠好，因為有的類別樣本確實很集中，這不是提供的樣本數(shù)量多少的問題，這是類別本身的特征（就是某些話題涉及的面很窄，例如計算機類的文章就明顯不如文化類的文章那么“天馬行空”），這個時候即便超球的半徑差異很大，也不應(yīng)該賦予兩個類別不同的懲罰因子。

看到這里讀者一定瘋了，因為說來說去，這豈不成了一個解決不了的問題？然而事實如此，完全的方法是沒有的，根據(jù)需要，選擇實現(xiàn)簡單又合用的就好（例如libSVM就直接使用樣本數(shù)量的比）。

現(xiàn)在我們已經(jīng)把一個本來線性不可分的文本分類問題，通過映射到高維空間而變成了線性可分的。就像下圖這樣：

 

圓形和方形的點各有成千上萬個（畢竟，這就是我們訓練集中文檔的數(shù)量嘛，當然很大了）。現(xiàn)在想象我們有另一個訓練集，只比原先這個訓練集多了一篇文章，映射到高維空間以后（當然，也使用了相同的核函數(shù)），也就多了一個樣本點，但是這個樣本的位置是這樣的：

 

就是圖中黃色那個點，它是方形的，因而它是負類的一個樣本，這單獨的一個樣本，使得原本線性可分的問題變成了線性不可分的。這樣類似的問題（僅有少數(shù)點線性不可分）叫做“近似線性可分”的問題。

以我們?nèi)祟惖某ＷR來判斷，說有一萬個點都符合某種規(guī)律（因而線性可分），有一個點不符合，那這一個點是否就代表了分類規(guī)則中我們沒有考慮到的方面呢（因而規(guī)則應(yīng)該為它而做出修改）？

其實我們會覺得，更有可能的是，這個樣本點壓根就是錯誤，是噪聲，是提供訓練集的同學人工分類時一打瞌睡錯放進去的。所以我們會簡單的忽略這個樣本點，仍然使用原來的分類器，其效果絲毫不受影響。

但這種對噪聲的容錯性是人的思維帶來的，我們的程序可沒有。由于我們原本的優(yōu)化問題的表達式中，確實要考慮所有的樣本點（不能忽略某一個，因為程序它怎么知道該忽略哪一個呢？），在此基礎(chǔ)上尋找正負類之間的最大幾何間隔，而幾何間隔本身代表的是距離，是非負的，像上面這種有噪聲的情況會使得整個問題無解。這種解法其實也叫做“硬間隔”分類法，因為他硬性的要求所有樣本點都滿足和分類平面間的距離必須大于某個值。

因此由上面的例子中也可以看出，硬間隔的分類法其結(jié)果容易受少數(shù)點的控制，這是很危險的（盡管有句話說真理總是掌握在少數(shù)人手中，但那不過是那一小撮人聊以自慰的詞句罷了，咱還是得民主）。

但解決方法也很明顯，就是仿照人的思路，允許一些點到分類平面的距離不滿足原先的要求。由于不同的訓練集各點的間距尺度不太一樣，因此用間隔（而不是幾何間隔）來衡量有利于我們表達形式的簡潔。我們原先對樣本點的要求是：

 

意思是說離分類面最近的樣本點函數(shù)間隔也要比1大。如果要引入容錯性，就給1這個硬性的閾值加一個松弛變量，即允許

因為松弛變量是非負的，因此最終的結(jié)果是要求間隔可以比1小。但是當某些點出現(xiàn)這種間隔比1小的情況時（這些點也叫離群點），意味著我們放棄了對這些點的精確分類，而這對我們的分類器來說是種損失。但是放棄這些點也帶來了好處，那就是使分類面不必向這些點的方向移動，因而可以得到更大的幾何間隔（在低維空間看來，分類邊界也更平滑）。顯然我們必須權(quán)衡這種損失和好處。好處很明顯，我們得到的分類間隔越大，好處就越多。回顧我們原始的硬間隔分類對應(yīng)的優(yōu)化問題：

||w||²就是我們的目標函數(shù)（當然系數(shù)可有可無），希望它越小越好，因而損失就必然是一個能使之變大的量（能使它變小就不叫損失了，我們本來就希望目標函數(shù)值越小越好）。那如何來衡量損失，有兩種常用的方式，有人喜歡用

而有人喜歡用

其中l(wèi)都是樣本的數(shù)目。兩種方法沒有大的區(qū)別。如果選擇了第一種，得到的方法的就叫做二階軟間隔分類器，第二種就叫做一階軟間隔分類器。把損失加入到目標函數(shù)里的時候，就需要一個懲罰因子（cost，也就是libSVM的諸多參數(shù)中的C），原來的優(yōu)化問題就變成了下面這樣：

這個式子有這么幾點要注意：

一是并非所有的樣本點都有一個松弛變量與其對應(yīng)。實際上只有“離群點”才有，或者也可以這么看，所有沒離群的點松弛變量都等于0（對負類來說，離群點就是在前面圖中，跑到H2右側(cè)的那些負樣本點，對正類來說，就是跑到H1左側(cè)的那些正樣本點）。

二是松弛變量的值實際上標示出了對應(yīng)的點到底離群有多遠，值越大，點就越遠。

三是懲罰因子C決定了你有多重視離群點帶來的損失，顯然當所有離群點的松弛變量的和一定時，你定的C越大，對目標函數(shù)的損失也越大，此時就暗示著你非常不愿意放棄這些離群點，最極端的情況是你把C定為無限大，這樣只要稍有一個點離群，目標函數(shù)的值馬上變成無限大，馬上讓問題變成無解，這就退化成了硬間隔問題。

四是懲罰因子C不是一個變量，整個優(yōu)化問題在解的時候，C是一個你必須事先指定的值，指定這個值以后，解一下，得到一個分類器，然后用測試數(shù)據(jù)看看結(jié)果怎么樣，如果不夠好，換一個C的值，再解一次優(yōu)化問題，得到另一個分類器，再看看效果，如此就是一個參數(shù)尋優(yōu)的過程，但這和優(yōu)化問題本身決不是一回事，優(yōu)化問題在解的過程中，C一直是定值，要記住。

五是盡管加了松弛變量這么一說，但這個優(yōu)化問題仍然是一個優(yōu)化問題（汗，這不廢話么），解它的過程比起原始的硬間隔問題來說，沒有任何更加特殊的地方。

從大的方面說優(yōu)化問題解的過程，就是先試著確定一下w，也就是確定了前面圖中的三條直線，這時看看間隔有多大，又有多少點離群，把目標函數(shù)的值算一算，再換一組三條直線（你可以看到，分類的直線位置如果移動了，有些原來離群的點會變得不再離群，而有的本來不離群的點會變成離群點），再把目標函數(shù)的值算一算，如此往復（迭代），直到最終找到目標函數(shù)最小時的w。

啰嗦了這么多，讀者一定可以馬上自己總結(jié)出來，松弛變量也就是個解決線性不可分問題的方法罷了，但是回想一下，核函數(shù)的引入不也是為了解決線性不可分的問題么？為什么要為了一個問題使用兩種方法呢？

其實兩者還有微妙的不同。一般的過程應(yīng)該是這樣，還以文本分類為例。在原始的低維空間中，樣本相當?shù)牟豢煞郑瑹o論你怎么找分類平面，總會有大量的離群點，此時用核函數(shù)向高維空間映射一下，雖然結(jié)果仍然是不可分的，但比原始空間里的要更加接近線性可分的狀態(tài)（就是達到了近似線性可分的狀態(tài)），此時再用松弛變量處理那些少數(shù)“冥頑不化”的離群點，就簡單有效得多啦。

本節(jié)中的（式1）也確實是支持向量機最最常用的形式。至此一個比較完整的支持向量機框架就有了，簡單說來，支持向量機就是使用了核函數(shù)的軟間隔線性分類法。

下一節(jié)會說說松弛變量剩下的一點點東西，順便搞個讀者調(diào)查，看看大家還想侃侃SVM的哪些方面。

生存？還是毀滅？——哈姆雷特

可分？還是不可分？——支持向量機

之前一直在討論的線性分類器,器如其名（汗，這是什么說法啊），只能對線性可分的樣本做處理。如果提供的樣本線性不可分，結(jié)果很簡單，線性分類器的求解程序會無限循環(huán)，永遠也解不出來。這必然使得它的適用范圍大大縮小，而它的很多優(yōu)點我們實在不原意放棄，怎么辦呢？是否有某種方法，讓線性不可分的數(shù)據(jù)變得線性可分呢？

有！其思想說來也簡單，來用一個二維平面中的分類問題作例子，你一看就會明白。事先聲明，下面這個例子是網(wǎng)絡(luò)早就有的，我一時找不到原作者的正確信息，在此借用，并加進了我自己的解說而已。

例子是下面這張圖：

我們把橫軸上端點a和b之間紅色部分里的所有點定為正類，兩邊的黑色部分里的點定為負類。試問能找到一個線性函數(shù)把兩類正確分開么？不能，因為二維空間里的線性函數(shù)就是指直線，顯然找不到符合條件的直線。

但我們可以找到一條曲線，例如下面這一條：

顯然通過點在這條曲線的上方還是下方就可以判斷點所屬的類別（你在橫軸上隨便找一點，算算這一點的函數(shù)值，會發(fā)現(xiàn)負類的點函數(shù)值一定比0大，而正類的一定比0小）。這條曲線就是我們熟知的二次曲線，它的函數(shù)表達式可以寫為：

問題只是它不是一個線性函數(shù)，但是，下面要注意看了，新建一個向量y和a：

這樣g(x)就可以轉(zhuǎn)化為f(y)=<a,y>，你可以把y和a分別回帶一下，看看等不等于原來的g(x)。用內(nèi)積的形式寫你可能看不太清楚，實際上f(y)的形式就是：

g(x)=f(y)=ay

在任意維度的空間中，這種形式的函數(shù)都是一個線性函數(shù)（只不過其中的a和y都是多維向量罷了），因為自變量y的次數(shù)不大于1。

看出妙在哪了么？原來在二維空間中一個線性不可分的問題，映射到四維空間后，變成了線性可分的！因此這也形成了我們最初想解決線性不可分問題的基本思路——向高維空間轉(zhuǎn)化，使其變得線性可分。

而轉(zhuǎn)化最關(guān)鍵的部分就在于找到x到y(tǒng)的映射方法。遺憾的是，如何找到這個映射，沒有系統(tǒng)性的方法（也就是說，純靠猜和湊）。具體到我們的文本分類問題，文本被表示為上千維的向量，即使維數(shù)已經(jīng)如此之高，也常常是線性不可分的，還要向更高的空間轉(zhuǎn)化。其中的難度可想而知。

小Tips:為什么說f(y)=ay是四維空間里的函數(shù)?

大家可能一時沒看明白。回想一下我們二維空間里的函數(shù)定義
  g(x)=ax+b
變量x是一維的，為什么說它是二維空間里的函數(shù)呢？因為還有一個變量我們沒寫出來，它的完整形式其實是
  y=g(x)=ax+b
即
  y=ax+b
看看，有幾個變量？兩個。那是幾維空間的函數(shù)？（作者五歲的弟弟答：五維的。作者：……）
再看看
f(y)=ay
里面的y是三維的變量，那f(y)是幾維空間里的函數(shù)？（作者五歲的弟弟答：還是五維的。作者：……）

用一個具體文本分類的例子來看看這種向高維空間映射從而分類的方法如何運作，想象一下，我們文本分類問題的原始空間是1000維的（即每個要被分類的文檔被表示為一個1000維的向量），在這個維度上問題是線性不可分的。現(xiàn)在我們有一個2000維空間里的線性函數(shù)

f(x^’)=<w^’,x^’>+b

注意向量的右上角有個 ’哦。它能夠?qū)⒃瓎栴}變得可分。式中的 w^’和x^’都是2000維的向量，只不過w^’是定值，而x^’是變量（好吧,嚴格說來這個函數(shù)是2001維的,哈哈），現(xiàn)在我們的輸入呢，是一個1000維的向量x，分類的過程是先把x變換為2000維的向量x^’，然后求這個變換后的向量x^’與向量w^’的內(nèi)積，再把這個內(nèi)積的值和b相加，就得到了結(jié)果，看結(jié)果大于閾值還是小于閾值就得到了分類結(jié)果。

你發(fā)現(xiàn)了什么？我們其實只關(guān)心那個高維空間里內(nèi)積的值，那個值算出來了，分類結(jié)果就算出來了。而從理論上說， x^’是經(jīng)由x變換來的，因此廣義上可以把它叫做x的函數(shù)（有一個x，就確定了一個x^’，對吧，確定不出第二個），而w^’是常量，它是一個低維空間里的常量w經(jīng)過變換得到的，所以給了一個w 和x的值，就有一個確定的f(x^’)值與其對應(yīng)。這讓我們幻想，是否能有這樣一種函數(shù)K(w,x),他接受低維空間的輸入值，卻能算出高維空間的內(nèi)積值<w^’,x^’>？

如果有這樣的函數(shù)，那么當給了一個低維空間的輸入x以后，

g(x)=K(w,x)+b

f(x^’)=<w^’,x^’>+b

這兩個函數(shù)的計算結(jié)果就完全一樣，我們也就用不著費力找那個映射關(guān)系，直接拿低維的輸入往g(x)里面代就可以了（再次提醒，這回的g(x)就不是線性函數(shù)啦，因為你不能保證K(w,x)這個表達式里的x次數(shù)不高于1哦）。

萬幸的是，這樣的K(w,x)確實存在（發(fā)現(xiàn)凡是我們?nèi)祟惸芙鉀Q的問題，大都是巧得不能再巧，特殊得不能再特殊的問題，總是恰好有些能投機取巧的地方才能解決，由此感到人類的渺小），它被稱作核函數(shù)（核，kernel），而且還不止一個，事實上，只要是滿足了Mercer條件的函數(shù)，都可以作為核函數(shù)。核函數(shù)的基本作用就是接受兩個低維空間里的向量，能夠計算出經(jīng)過某個變換后在高維空間里的向量內(nèi)積值。幾個比較常用的核函數(shù)，俄，教課書里都列過，我就不敲了（懶！）。

回想我們上節(jié)說的求一個線性分類器，它的形式應(yīng)該是：

現(xiàn)在這個就是高維空間里的線性函數(shù)（為了區(qū)別低維和高維空間里的函數(shù)和向量，我改了函數(shù)的名字，并且給w和x都加上了 ’），我們就可以用一個低維空間里的函數(shù)（再一次的，這個低維空間里的函數(shù)就不再是線性的啦）來代替，

又發(fā)現(xiàn)什么了？f(x’) 和g(x)里的α，y，b全都是一樣一樣的！這就是說，盡管給的問題是線性不可分的，但是我們就硬當它是線性問題來求解，只不過求解過程中，凡是要求內(nèi)積的時候就用你選定的核函數(shù)來算。這樣求出來的α再和你選定的核函數(shù)一組合，就得到分類器啦！

明白了以上這些，會自然的問接下來兩個問題：

1． 既然有很多的核函數(shù)，針對具體問題該怎么選擇？

2． 如果使用核函數(shù)向高維空間映射后，問題仍然是線性不可分的，那怎么辦？

第一個問題現(xiàn)在就可以回答你：對核函數(shù)的選擇，現(xiàn)在還缺乏指導原則！各種實驗的觀察結(jié)果（不光是文本分類）的確表明，某些問題用某些核函數(shù)效果很好，用另一些就很差，但是一般來講，徑向基核函數(shù)是不會出太大偏差的一種，首選。（我做文本分類系統(tǒng)的時候，使用徑向基核函數(shù)，沒有參數(shù)調(diào)優(yōu)的情況下，絕大部分類別的準確和召回都在85%以上，可見。雖然libSVM的作者林智仁認為文本分類用線性核函數(shù)效果更佳，待考證）

對第二個問題的解決則引出了我們下一節(jié)的主題：松弛變量。

讓我再一次比較完整的重復一下我們要解決的問題：我們有屬于兩個類別的樣本點（并不限定這些點在二維空間中）若干，如圖，

圓形的樣本點定為正樣本（連帶著，我們可以把正樣本所屬的類叫做正類），方形的點定為負例。我們想求得這樣一個線性函數(shù)（在n維空間中的線性函數(shù)）：

g(x)=wx+b

使得所有屬于正類的點x₊代入以后有g(shù)(x₊)≥1，而所有屬于負類的點x_-代入后有g(shù)(x_-)≤-1（之所以總跟1比較，無論正一還是負一，都是因為我們固定了間隔為1，注意間隔和幾何間隔的區(qū)別）。代入g(x)后的值如果在1和-1之間，我們就拒絕判斷。

求這樣的g(x)的過程就是求w（一個n維向量）和b（一個實數(shù)）兩個參數(shù)的過程（但實際上只需要求w，求得以后找某些樣本點代入就可以求得b）。因此在求g(x)的時候，w才是變量。

你肯定能看出來，一旦求出了w（也就求出了b），那么中間的直線H就知道了（因為它就是wx+b=0嘛，哈哈），那么H1和H2也就知道了（因為三者是平行的，而且相隔的距離還是||w||決定的）。那么w是誰決定的？顯然是你給的樣本決定的，一旦你在空間中給出了那些個樣本點，三條直線的位置實際上就唯一確定了（因為我們求的是最優(yōu)的那三條，當然是唯一的），我們解優(yōu)化問題的過程也只不過是把這個確定了的東西算出來而已。

樣本確定了w，用數(shù)學的語言描述，就是w可以表示為樣本的某種組合：

w=α₁x₁+α₂x₂+…+α_nx_n

式子中的α_i是一個一個的數(shù)（在嚴格的證明過程中，這些α被稱為拉格朗日乘子），而x_i是樣本點，因而是向量，n就是總樣本點的個數(shù)。為了方便描述，以下開始嚴格區(qū)別數(shù)字與向量的乘積和向量間的乘積，我會用α₁x₁表示數(shù)字和向量的乘積，而用<x₁,x₂>表示向量x₁,x₂的內(nèi)積（也叫點積，注意與向量叉積的區(qū)別）。因此g(x)的表達式嚴格的形式應(yīng)該是：

g(x)=<w,x>+b

但是上面的式子還不夠好，你回頭看看圖中正樣本和負樣本的位置，想像一下，我不動所有點的位置，而只是把其中一個正樣本點定為負樣本點（也就是把一個點的形狀從圓形變?yōu)榉叫危Y(jié)果怎么樣？三條直線都必須移動（因為對這三條直線的要求是必須把方形和圓形的點正確分開）！這說明w不僅跟樣本點的位置有關(guān)，還跟樣本的類別有關(guān)（也就是和樣本的“標簽”有關(guān)）。因此用下面這個式子表示才算完整：

w=α₁y₁x₁+α₂y₂x₂+…+α_ny_nx_n （式1）

其中的y_i就是第i個樣本的標簽，它等于1或者-1。其實以上式子的那一堆拉格朗日乘子中，只有很少的一部分不等于0（不等于0才對w起決定作用），這部分不等于0的拉格朗日乘子后面所乘的樣本點，其實都落在H1和H2上，也正是這部分樣本（而不需要全部樣本）唯一的確定了分類函數(shù)，當然，更嚴格的說，這些樣本的一部分就可以確定，因為例如確定一條直線，只需要兩個點就可以，即便有三五個都落在上面，我們也不是全都需要。這部分我們真正需要的樣本點，就叫做支持（撐）向量！（名字還挺形象吧，他們“撐”起了分界線）

式子也可以用求和符號簡寫一下：

 

因此原來的g(x)表達式可以寫為：

注意式子中x才是變量，也就是你要分類哪篇文檔，就把該文檔的向量表示代入到 x的位置，而所有的x_i統(tǒng)統(tǒng)都是已知的樣本。還注意到式子中只有x_i和x是向量，因此一部分可以從內(nèi)積符號中拿出來，得到g(x)的式子為：

發(fā)現(xiàn)了什么？w不見啦！從求w變成了求α。

但肯定有人會說，這并沒有把原問題簡化呀。嘿嘿，其實簡化了，只不過在你看不見的地方，以這樣的形式描述問題以后，我們的優(yōu)化問題少了很大一部分不等式約束（記得這是我們解不了極值問題的萬惡之源）。但是接下來先跳過線性分類器求解的部分，來看看 SVM在線性分類器上所做的重大改進——核函數(shù)。

從最一般的定義上說，一個求最小值的問題就是一個優(yōu)化問題（也叫尋優(yōu)問題，更文縐縐的叫法是規(guī)劃——Programming），它同樣由兩部分組成，目標函數(shù)和約束條件，可以用下面的式子表示：

（式1）

約束條件用函數(shù)c來表示，就是constrain的意思啦。你可以看出一共有p+q個約束條件，其中p個是不等式約束，q個等式約束。

關(guān)于這個式子可以這樣來理解：式中的x是自變量，但不限定它的維數(shù)必須為1（視乎你解決的問題空間維數(shù)，對我們的文本分類來說，那可是成千上萬啊）。要求f(x)在哪一點上取得最小值（反倒不太關(guān)心這個最小值到底是多少，關(guān)鍵是哪一點），但不是在整個空間里找，而是在約束條件所劃定的一個有限的空間里找，這個有限的空間就是優(yōu)化理論里所說的可行域。注意可行域中的每一個點都要求滿足所有p+q個條件，而不是滿足其中一條或幾條就可以（切記，要滿足每個約束），同時可行域邊界上的點有一個額外好的特性，它們可以使不等式約束取得等號！而邊界內(nèi)的點不行。

關(guān)于可行域還有個概念不得不提，那就是凸集，凸集是指有這么一個點的集合，其中任取兩個點連一條直線，這條線上的點仍然在這個集合內(nèi)部，因此說“凸”是很形象的（一個反例是，二維平面上，一個月牙形的區(qū)域就不是凸集，你隨便就可以找到兩個點違反了剛才的規(guī)定）。

回頭再來看我們線性分類器問題的描述，可以看出更多的東西。

（式2）

在這個問題中，自變量就是w，而目標函數(shù)是w的二次函數(shù)，所有的約束條件都是w的線性函數(shù)（哎，千萬不要把x_i當成變量，它代表樣本，是已知的），這種規(guī)劃問題有個很有名氣的稱呼——二次規(guī)劃（Quadratic Programming，QP），而且可以更進一步的說，由于它的可行域是一個凸集，因此它是一個凸二次規(guī)劃。

一下子提了這么多術(shù)語，實在不是為了讓大家以后能向別人炫耀學識的淵博，這其實是我們繼續(xù)下去的一個重要前提，因為在動手求一個問題的解之前（好吧，我承認，是動計算機求……），我們必須先問自己：這個問題是不是有解？如果有解，是否能找到？

對于一般意義上的規(guī)劃問題，兩個問題的答案都是不一定，但凸二次規(guī)劃讓人喜歡的地方就在于，它有解（教科書里面為了嚴謹，常常加限定成分，說它有全局最優(yōu)解，由于我們想找的本來就是全局最優(yōu)的解，所以不加也罷），而且可以找到！（當然，依據(jù)你使用的算法不同，找到這個解的速度，行話叫收斂速度，會有所不同）

對比（式2）和（式1）還可以發(fā)現(xiàn)，我們的線性分類器問題只有不等式約束，因此形式上看似乎比一般意義上的規(guī)劃問題要簡單，但解起來卻并非如此。

因為我們實際上并不知道該怎么解一個帶約束的優(yōu)化問題。如果你仔細回憶一下高等數(shù)學的知識，會記得我們可以輕松的解一個不帶任何約束的優(yōu)化問題（實際上就是當年背得爛熟的函數(shù)求極值嘛，求導再找0點唄，誰不會啊？笑），我們甚至還會解一個只帶等式約束的優(yōu)化問題，也是背得爛熟的，求條件極值，記得么，通過添加拉格朗日乘子，構(gòu)造拉格朗日函數(shù)，來把這個問題轉(zhuǎn)化為無約束的優(yōu)化問題云云（如果你一時沒想通，我提醒一下，構(gòu)造出的拉格朗日函數(shù)就是轉(zhuǎn)化之后的問題形式，它顯然沒有帶任何條件）。

讀者問：如果只帶等式約束的問題可以轉(zhuǎn)化為無約束的問題而得以求解，那么可不可以把帶不等式約束的問題向只帶等式約束的問題轉(zhuǎn)化一下而得以求解呢？

聰明，可以，實際上我們也正是這么做的。下一節(jié)就來說說如何做這個轉(zhuǎn)化，一旦轉(zhuǎn)化完成，求解對任何學過高等數(shù)學的人來說，都是小菜一碟啦。

上節(jié)說到我們有了一個線性分類函數(shù)，也有了判斷解優(yōu)劣的標準——即有了優(yōu)化的目標，這個目標就是最大化幾何間隔，但是看過一些關(guān)于SVM的論文的人一定記得什么優(yōu)化的目標是要最小化||w||這樣的說法，這是怎么回事呢？回頭再看看我們對間隔和幾何間隔的定義：

間隔：δ=y(wx+b)=|g(x)|

幾何間隔：

 

可以看出δ=||w||δ_幾何。注意到幾何間隔與||w||是成反比的，因此最大化幾何間隔與最小化||w||完全是一回事。而我們常用的方法并不是固定||w||的大小而尋求最大幾何間隔，而是固定間隔（例如固定為1），尋找最小的||w||。

而凡是求一個函數(shù)的最小值（或最大值）的問題都可以稱為尋優(yōu)問題（也叫作一個規(guī)劃問題），又由于找最大值的問題總可以通過加一個負號變?yōu)檎易钚≈档膯栴}，因此我們下面討論的時候都針對找最小值的過程來進行。一個尋優(yōu)問題最重要的部分是目標函數(shù)，顧名思義，就是指尋優(yōu)的目標。例如我們想尋找最小的||w||這件事，就可以用下面的式子表示：

但實際上對于這個目標，我們常常使用另一個完全等價的目標函數(shù)來代替，那就是：

(式1)

不難看出當||w||²達到最小時，||w||也達到最小，反之亦然（前提當然是||w||描述的是向量的長度，因而是非負的）。之所以采用這種形式，是因為后面的求解過程會對目標函數(shù)作一系列變換，而式（1）的形式會使變換后的形式更為簡潔（正如聰明的讀者所料，添加的系數(shù)二分之一和平方，皆是為求導數(shù)所需）。

接下來我們自然會問的就是，這個式子是否就描述了我們的問題呢？（回想一下，我們的問題是有一堆點，可以被分成兩類，我們要找出最好的分類面）

如果直接來解這個求最小值問題，很容易看出當||w||=0的時候就得到了目標函數(shù)的最小值。但是你也會發(fā)現(xiàn)，無論你給什么樣的數(shù)據(jù)，都是這個解！反映在圖中，就是H1與H2兩條直線間的距離無限大，這個時候，所有的樣本點（無論正樣本還是負樣本）都跑到了H1和H2中間，而我們原本的意圖是，H1右側(cè)的被分為正類，H2 左側(cè)的被分為負類，位于兩類中間的樣本則拒絕分類（拒絕分類的另一種理解是分給哪一類都有道理，因而分給哪一類也都沒有道理）。這下可好，所有樣本點都進入了無法分類的灰色地帶。

造成這種結(jié)果的原因是在描述問題的時候只考慮了目標，而沒有加入約束條件，約束條件就是在求解過程中必須滿足的條件，體現(xiàn)在我們的問題中就是樣本點必須在H1或H2的某一側(cè)（或者至少在H1和H2上），而不能跑到兩者中間。我們前文提到過把間隔固定為1，這是指把所有樣本點中間隔最小的那一點的間隔定為1（這也是集合的間隔的定義，有點繞嘴），也就意味著集合中的其他點間隔都不會小于1，按照間隔的定義，滿足這些條件就相當于讓下面的式子總是成立：

    y_i[(w·x_i)+b]≥1 (i=1,2,…,l) （l是總的樣本數(shù)）

但我們常常習慣讓式子的值和0比較，因而經(jīng)常用變換過的形式：

    y_i[(w·x_i)+b]-1≥0 (i=1,2,…,l) （l是總的樣本數(shù)）

因此我們的兩類分類問題也被我們轉(zhuǎn)化成了它的數(shù)學形式，一個帶約束的最小值的問題：

下一節(jié)我們從最一般的意義上看看一個求最小值的問題有何特征，以及如何來解。

按:之前的文章重新匯編一下,修改了一些錯誤和不當?shù)恼f法，一起復習,然后繼續(xù)SVM之旅.

（一）SVM的八股簡介

支持向量機(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的，它在解決小樣本、非線性及高維模式識別中表現(xiàn)出許多特有的優(yōu)勢，并能夠推廣應(yīng)用到函數(shù)擬合等其他機器學習問題中[10]。
支持向量機方法是建立在統(tǒng)計學習理論的VC 維理論和結(jié)構(gòu)風險最小原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型的復雜性（即對特定訓練樣本的學習精度，Accuracy）和學習能力（即無錯誤地識別任意樣本的能力）之間尋求最佳折衷，以期獲得最好的推廣能力[14]（或稱泛化能力）。

以上是經(jīng)常被有關(guān)SVM 的學術(shù)文獻引用的介紹，有點八股，我來逐一分解并解釋一下。

Vapnik是統(tǒng)計機器學習的大牛，這想必都不用說，他出版的《Statistical Learning Theory》是一本完整闡述統(tǒng)計機器學習思想的名著。在該書中詳細的論證了統(tǒng)計機器學習之所以區(qū)別于傳統(tǒng)機器學習的本質(zhì)，就在于統(tǒng)計機器學習能夠精確的給出學習效果，能夠解答需要的樣本數(shù)等等一系列問題。與統(tǒng)計機器學習的精密思維相比，傳統(tǒng)的機器學習基本上屬于摸著石頭過河，用傳統(tǒng)的機器學習方法構(gòu)造分類系統(tǒng)完全成了一種技巧，一個人做的結(jié)果可能很好，另一個人差不多的方法做出來卻很差，缺乏指導和原則。

所謂VC維是對函數(shù)類的一種度量，可以簡單的理解為問題的復雜程度，VC維越高，一個問題就越復雜。正是因為SVM關(guān)注的是VC維，后面我們可以看到，SVM解決問題的時候，和樣本的維數(shù)是無關(guān)的（甚至樣本是上萬維的都可以，這使得SVM很適合用來解決文本分類的問題，當然，有這樣的能力也因為引入了核函數(shù)）。

結(jié)構(gòu)風險最小聽上去文縐縐，其實說的也無非是下面這回事。

機器學習本質(zhì)上就是一種對問題真實模型的逼近（我們選擇一個我們認為比較好的近似模型，這個近似模型就叫做一個假設(shè)），但毫無疑問，真實模型一定是不知道的（如果知道了，我們干嗎還要機器學習？直接用真實模型解決問題不就可以了？對吧，哈哈）既然真實模型不知道，那么我們選擇的假設(shè)與問題真實解之間究竟有多大差距，我們就沒法得知。比如說我們認為宇宙誕生于150億年前的一場大爆炸，這個假設(shè)能夠描述很多我們觀察到的現(xiàn)象，但它與真實的宇宙模型之間還相差多少？誰也說不清，因為我們壓根就不知道真實的宇宙模型到底是什么。

這個與問題真實解之間的誤差，就叫做風險（更嚴格的說，誤差的累積叫做風險）。我們選擇了一個假設(shè)之后（更直觀點說，我們得到了一個分類器以后），真實誤差無從得知，但我們可以用某些可以掌握的量來逼近它。最直觀的想法就是使用分類器在樣本數(shù)據(jù)上的分類的結(jié)果與真實結(jié)果（因為樣本是已經(jīng)標注過的數(shù)據(jù)，是準確的數(shù)據(jù)）之間的差值來表示。這個差值叫做經(jīng)驗風險R_emp(w)。以前的機器學習方法都把經(jīng)驗風險最小化作為努力的目標，但后來發(fā)現(xiàn)很多分類函數(shù)能夠在樣本集上輕易達到100%的正確率，在真實分類時卻一塌糊涂（即所謂的推廣能力差，或泛化能力差）。此時的情況便是選擇了一個足夠復雜的分類函數(shù)（它的VC維很高），能夠精確的記住每一個樣本，但對樣本之外的數(shù)據(jù)一律分類錯誤。回頭看看經(jīng)驗風險最小化原則我們就會發(fā)現(xiàn)，此原則適用的大前提是經(jīng)驗風險要確實能夠逼近真實風險才行（行話叫一致），但實際上能逼近么？答案是不能，因為樣本數(shù)相對于現(xiàn)實世界要分類的文本數(shù)來說簡直九牛一毛，經(jīng)驗風險最小化原則只在這占很小比例的樣本上做到?jīng)]有誤差，當然不能保證在更大比例的真實文本上也沒有誤差。

統(tǒng)計學習因此而引入了泛化誤差界的概念，就是指真實風險應(yīng)該由兩部分內(nèi)容刻畫，一是經(jīng)驗風險，代表了分類器在給定樣本上的誤差；二是置信風險，代表了我們在多大程度上可以信任分類器在未知文本上分類的結(jié)果。很顯然，第二部分是沒有辦法精確計算的，因此只能給出一個估計的區(qū)間，也使得整個誤差只能計算上界，而無法計算準確的值（所以叫做泛化誤差界，而不叫泛化誤差）。

置信風險與兩個量有關(guān)，一是樣本數(shù)量，顯然給定的樣本數(shù)量越大，我們的學習結(jié)果越有可能正確，此時置信風險越小；二是分類函數(shù)的VC維，顯然VC維越大，推廣能力越差，置信風險會變大。

泛化誤差界的公式為：

R(w)≤R_emp(w)+Ф(n/h)

公式中R(w)就是真實風險，R_emp(w)就是經(jīng)驗風險，Ф(n/h)就是置信風險。統(tǒng)計學習的目標從經(jīng)驗風險最小化變?yōu)榱藢で蠼?jīng)驗風險與置信風險的和最小，即結(jié)構(gòu)風險最小。

SVM正是這樣一種努力最小化結(jié)構(gòu)風險的算法。

SVM其他的特點就比較容易理解了。

小樣本，并不是說樣本的絕對數(shù)量少（實際上，對任何算法來說，更多的樣本幾乎總是能帶來更好的效果），而是說與問題的復雜度比起來，SVM算法要求的樣本數(shù)是相對比較少的。

非線性，是指SVM擅長應(yīng)付樣本數(shù)據(jù)線性不可分的情況，主要通過松弛變量（也有人叫懲罰變量）和核函數(shù)技術(shù)來實現(xiàn)，這一部分是SVM的精髓，以后會詳細討論。多說一句，關(guān)于文本分類這個問題究竟是不是線性可分的，尚沒有定論，因此不能簡單的認為它是線性可分的而作簡化處理，在水落石出之前，只好先當它是線性不可分的（反正線性可分也不過是線性不可分的一種特例而已，我們向來不怕方法過于通用）。

高維模式識別是指樣本維數(shù)很高，例如文本的向量表示，如果沒有經(jīng)過另一系列文章（《文本分類入門》）中提到過的降維處理，出現(xiàn)幾萬維的情況很正常，其他算法基本就沒有能力應(yīng)付了，SVM卻可以，主要是因為SVM 產(chǎn)生的分類器很簡潔，用到的樣本信息很少（僅僅用到那些稱之為“支持向量”的樣本，此為后話），使得即使樣本維數(shù)很高，也不會給存儲和計算帶來大麻煩（相對照而言，kNN算法在分類時就要用到所有樣本，樣本數(shù)巨大，每個樣本維數(shù)再一高，這日子就沒法過了……）。

下一節(jié)開始正式討論SVM。別嫌我說得太詳細哦。

 

SVM入門（二）線性分類器Part 1

線性分類器(一定意義上,也可以叫做感知機) 是最簡單也很有效的分類器形式.在一個線性分類器中,可以看到SVM形成的思路,并接觸很多SVM的核心概念.

用一個二維空間里僅有兩類樣本的分類問題來舉個小例子。如圖所示

^­C₁和C₂是要區(qū)分的兩個類別，在二維平面中它們的樣本如上圖所示。中間的直線就是一個分類函數(shù)，它可以將兩類樣本完全分開。一般的，如果一個線性函數(shù)能夠?qū)颖就耆_的分開，就稱這些數(shù)據(jù)是線性可分的，否則稱為非線性可分的。

什么叫線性函數(shù)呢？在一維空間里就是一個點，在二維空間里就是一條直線，三維空間里就是一個平面，可以如此想象下去，如果不關(guān)注空間的維數(shù)，這種線性函數(shù)還有一個統(tǒng)一的名稱——超平面（Hyper Plane）！

實際上，一個線性函數(shù)是一個實值函數(shù)（即函數(shù)的值是連續(xù)的實數(shù)），而我們的分類問題（例如這里的二元分類問題——回答一個樣本屬于還是不屬于一個類別的問題）需要離散的輸出值，例如用1表示某個樣本屬于類別C₁，而用0表示不屬于（不屬于C₁也就意味著屬于C₂），這時候只需要簡單的在實值函數(shù)的基礎(chǔ)上附加一個閾值即可，通過分類函數(shù)執(zhí)行時得到的值大于還是小于這個閾值來確定類別歸屬。 例如我們有一個線性函數(shù)

g(x)=wx+b

我們可以取閾值為0，這樣當有一個樣本x_i需要判別的時候，我們就看g(x_i)的值。若g(x_i)>0，就判別為類別C₁，若g(x_i)<0，則判別為類別C₂（等于的時候我們就拒絕判斷，呵呵）。此時也等價于給函數(shù)g(x)附加一個符號函數(shù)sgn()，即f(x)=sgn [g(x)]是我們真正的判別函數(shù)。

關(guān)于g(x)=wx+b這個表達式要注意三點：一，式中的x不是二維坐標系中的橫軸，而是樣本的向量表示，例如一個樣本點的坐標是(3,8)，則x^T=(3,8) ，而不是x=3（一般說向量都是說列向量，因此以行向量形式來表示時，就加上轉(zhuǎn)置）。二，這個形式并不局限于二維的情況，在n維空間中仍然可以使用這個表達式，只是式中的w成為了n維向量（在二維的這個例子中，w是二維向量，為了表示起來方便簡潔，以下均不區(qū)別列向量和它的轉(zhuǎn)置，聰明的讀者一看便知）；三，g(x)不是中間那條直線的表達式，中間那條直線的表達式是g(x)=0，即wx+b=0，我們也把這個函數(shù)叫做分類面。

實際上很容易看出來，中間那條分界線并不是唯一的，我們把它稍微旋轉(zhuǎn)一下，只要不把兩類數(shù)據(jù)分錯，仍然可以達到上面說的效果，稍微平移一下，也可以。此時就牽涉到一個問題，對同一個問題存在多個分類函數(shù)的時候，哪一個函數(shù)更好呢？顯然必須要先找一個指標來量化“好”的程度，通常使用的都是叫做“分類間隔”的指標。下一節(jié)我們就仔細說說分類間隔，也補一補相關(guān)的數(shù)學知識。

SVM入門（三）線性分類器Part 2

上回說到對于文本分類這樣的不適定問題（有一個以上解的問題稱為不適定問題），需要有一個指標來衡量解決方案（即我們通過訓練建立的分類模型）的好壞，而分類間隔是一個比較好的指標。

在進行文本分類的時候，我們可以讓計算機這樣來看待我們提供給它的訓練樣本，每一個樣本由一個向量（就是那些文本特征所組成的向量）和一個標記（標示出這個樣本屬于哪個類別）組成。如下：

D_i=(x_i,y_i)

x_i就是文本向量（維數(shù)很高），y_i就是分類標記。

在二元的線性分類中，這個表示分類的標記只有兩個值，1和-1（用來表示屬于還是不屬于這個類）。有了這種表示法，我們就可以定義一個樣本點到某個超平面的間隔：

δ_i=y_i(wx_i+b)

這個公式乍一看沒什么神秘的，也說不出什么道理，只是個定義而已，但我們做做變換，就能看出一些有意思的東西。

首先注意到如果某個樣本屬于該類別的話，那么wx_i+b>0（記得么？這是因為我們所選的g(x)=wx+b就通過大于0還是小于0來判斷分類），而y_i也大于0；若不屬于該類別的話，那么wx_i+b<0，而y_i也小于0，這意味著y_i(wx_i+b)總是大于0的，而且它的值就等于|wx_i+b|！（也就是|g(x_i)|）

現(xiàn)在把w和b進行一下歸一化，即用w/||w||和b/||w||分別代替原來的w和b，那么間隔就可以寫成

這個公式是不是看上去有點眼熟？沒錯，這不就是解析幾何中點x_i到直線g(x)=0的距離公式嘛！（推廣一下，是到超平面g(x)=0的距離， g(x)=0就是上節(jié)中提到的分類超平面）

小Tips：||w||是什么符號？||w||叫做向量w的范數(shù)，范數(shù)是對向量長度的一種度量。我們常說的向量長度其實指的是它的2-范數(shù)，范數(shù)最一般的表示形式為p-范數(shù)，可以寫成如下表達式

    向量w=(w₁, w₂, w₃,…… w_n)

它的p-范數(shù)為

看看把p換成2的時候，不就是傳統(tǒng)的向量長度么？當我們不指明p的時候，就像||w||這樣使用時，就意味著我們不關(guān)心p的值，用幾范數(shù)都可以；或者上文已經(jīng)提到了p的值，為了敘述方便不再重復指明。

當用歸一化的w和b代替原值之后的間隔有一個專門的名稱，叫做幾何間隔，幾何間隔所表示的正是點到超平面的歐氏距離，我們下面就簡稱幾何間隔為“距離”。以上是單個點到某個超平面的距離（就是間隔，后面不再區(qū)別這兩個詞）定義，同樣可以定義一個點的集合（就是一組樣本）到某個超平面的距離為此集合中離超平面最近的點的距離。下面這張圖更加直觀的展示出了幾何間隔的現(xiàn)實含義：

H是分類面，而H₁和H₂是平行于H，且過離H最近的兩類樣本的直線，H₁與H，H₂與H之間的距離就是幾何間隔。

之所以如此關(guān)心幾何間隔這個東西，是因為幾何間隔與樣本的誤分次數(shù)間存在關(guān)系：

 

其中的δ是樣本集合到分類面的間隔，R=max ||xi||  i=1,...,n，即R是所有樣本中（xi是以向量表示的第i個樣本）向量長度最長的值（也就是說代表樣本的分布有多么廣）。先不必追究誤分次數(shù)的具體定義和推導過程，只要記得這個誤分次數(shù)一定程度上代表分類器的誤差。而從上式可以看出，誤分次數(shù)的上界由幾何間隔決定！（當然，是樣本已知的時候）

至此我們就明白為何要選擇幾何間隔來作為評價一個解優(yōu)劣的指標了，原來幾何間隔越大的解，它的誤差上界越小。因此最大化幾何間隔成了我們訓練階段的目標，而且，與二把刀作者所寫的不同，最大化分類間隔并不是SVM的專利，而是早在線性分類時期就已有的思想。

簡單的說,比較兩個int型或long型的數(shù)據(jù)沒有什么問題,可以用==來判斷,但對浮點數(shù)(float與double)來說,需要對Float.NaN和0.0這個兩個特殊數(shù)字作額外的處理。
Float.NaN嚴格說來不是一個數(shù)字（它的字面意思也就是Not a Number），但是因為這個值可以被保存在一個float型的變量中（因為它常常是除0的結(jié)果），所以暫且當它是個數(shù)字吧。但它與一般的浮點數(shù)有些許不同，就是兩個NaN用==比較的結(jié)果會得到false。
可以用下面的代碼驗證：

輸出結(jié)果為false

我用另一種除0的方法得到NaN，可以看到使用==判斷仍然得到false。代碼如下：


而當我們使用Float.compare()這個方法來比較兩個NaN時，卻會得到相等的結(jié)果。可以用下面的代碼驗證：

compare()方法如果返回0，就說明兩個數(shù)相等，返回-1，就說明第一個比第二個小，返回1則正好相反。
上面這兩行語句的返回結(jié)果都是0。
一般來說，基本類型的compare()方法與直接使用==的效果“應(yīng)該”是一樣的，但在NaN這個問題上不一致，是利是弊，取決于使用的人作何期望。當程序的語義要求兩個NaN不應(yīng)該被認為相等時（例如用NaN來代表兩個無窮大，學過高等數(shù)學的朋友們都記得，兩個無窮看上去符號是一樣，但不應(yīng)該認為是相等的兩樣東西），就使用==判斷；如果NaN被看得無足輕重（畢竟，我只關(guān)心數(shù)字，兩個不是數(shù)字的東西就劃歸同一類好了嘛）就使用Float.compare()。

另一個在==和compare()方法上表現(xiàn)不一致的浮點數(shù)就是正0和負0（當然這也是計算機表示有符號數(shù)字的老大難問題），我們（萬能的）人類當然知道0.0f和-0.0f應(yīng)該是相等的數(shù)字，但是試試下面的代碼：

返回的結(jié)果是true和-1。看到了么，==認為正0和負0相等，而compare()方法認為正0比負0要大。所以對0的比較來說，==是更好的選擇。

目前為止不管后臺寫了多少邏輯（已經(jīng)登錄了Google，取了相冊數(shù)據(jù)），我們的Gadget都還是那個看上去白白的Gadget。而要想讓它看上去有所不同，就要在main.xml這個文件中，制定我們想要的“長相”（就跟征婚啟事里寫的一樣，身高1米6至1米7，體重不超過55公斤，相貌端正，賢良淑惠）。

如果你已經(jīng)下載了我提供的源碼，就可以打開看看，對照實際效果來看代碼，應(yīng)該很好理解。我們總計在界面上放了幾樣東西：

•  一張背景圖（就是白白的那個）
•  一張Picasa的Logo
•  兩行表示歡迎的文字（就是label啦）
•  一個用來顯示相冊信息的列表（listbox），當然，目前列表中還一個列表項都沒有（列表項稱之為item）
•  最后又貼了兩張圖，其中一張是某企業(yè)的logo（笑）

其中值得注意的事情有這么幾件：

一是背景圖片絕非可有可無，按google的說法，像label這種東西，如果沒有放在一張背景圖片之上的話，是顯示不出來的。

二是Gadget中界面的內(nèi)容，樣式和布局都在這一個文件中指定。

三是Gadget的界面沒有HTML那種流動布局的效果，就是說，所有要顯示的元素，必須明明白白的指出它的位置，也就是每個元素的x和y屬性，是從該元素的父元素左上角開始計算的坐標。如果你先寫了一個label（拿label舉個例子，實際上用什么效果都是一樣的），再挨著它寫了一個label，兩個label你都沒有指定x和y的值，那么這個兩個label會重疊著顯示在一起。不信你可以試一試。

四是圖片的源文件位置，從代碼中可以看到指定本機上的相對目錄是可以的，那么指定一個網(wǎng)絡(luò)上的url可以么？例如http://www.sina.com.cn/images/logo.gif？如果你頭腦中還存在著HTML的印象，可能想當然的以為可以這么做，而事實上不行，Gadget與Web沒有天然的聯(lián)系（沒記錯的話，我已經(jīng)說過四次了）。后面處理相冊縮略圖的時候，我們會看到怎么把網(wǎng)絡(luò)上的圖片顯示出來。

寫過圖形用戶界面程序的人一定想問，如何讓界面上的元素與代碼產(chǎn)生聯(lián)系呢？例如我們的列表，我想在代碼中對它作些修改的時候，如何取得它的引用呢？在Gadget中這一點還比較方便，主要有兩個途徑：一是只要你給元素賦了name屬性，例如我就給列表項起了一個名字叫做contentListBox，在main.xml中的這一行：

 

之后就可以直接在代碼中用contentListBox這個值來訪問這個列表項了（而且任你在代碼中怎么找，也找不到聲明或者初始化這個變量的地方）——當然前提是起的名字必須是唯一的。有意思吧？

第二種方式比較傳統(tǒng)也比較少用，可以通過DOM對象訪問每個元素。

廢話不多說，來看看在代碼中給列表插入列表項怎么做。

列表項對應(yīng)著Gadget API提供的一個名為item的對象實例，但我們要用new item()這樣的語法來得到一個新的列表項并逐一設(shè)置它的屬性么？不不，有更簡便也更好玩的方法，我們只要新建一個字符串：

然后調(diào)用列表contentListBox的方法來添加就可以，像這樣：

方便么？這種用法使得開發(fā)人員不需要為一個圖形界面的組件掌握兩套語法（XML的和JavaScript的），非常貼心。

好，現(xiàn)在來說另一個問題，既然不能為一個img對象的src屬性指定一個網(wǎng)絡(luò)地址，那到底如何顯示網(wǎng)絡(luò)上的圖片呢？答案很長，如果你有了圖片的url（就是 http://開頭的那種啦），首先要通過XmlHttpRequest把圖片的數(shù)據(jù)取回來，然后把這部分數(shù)據(jù)賦給src屬性。

具體點，記得一個請求最重要的四部分數(shù)據(jù)么？url：就是該圖片的url；請求類型：因為是要求數(shù)據(jù)，自然是“GET”；請求頭：對本請求來說沒有；消息體：同樣沒有。

所以發(fā)請求的部分并不困難，待請求的狀態(tài)變?yōu)?/span>4，也就是說明回傳數(shù)據(jù)已到達的時候，就可以從請求的responseStream這個屬性得到圖片的二進制數(shù)據(jù)。假設(shè)在代碼中我們要顯示的圖片是<img name=”myImg”/>,記得么，使用名字可以直接訪問這個圖片，再假設(shè)我們的請求對象取名為xhRequest，像下面這樣：

如此就可以了！哈哈，簡單吧（我當初倒是找了半天，讀過了YouTube Gadget的代碼才參透呢，愚笨愚笨）。

在我們剩下的唯一一個重要函數(shù)Main的fetchAlbumThumbnail()中，就是使用這種方法來取得相冊縮略圖的圖片并顯示在Gadget的界面中的。

這個函數(shù)我就不逐一分解了，相信你一定看得懂。

大的方向上說，從Picasa服務(wù)器上取數(shù)據(jù)，有兩種方式，一種是使用Google已經(jīng)開放的各種語言的API，可以在頁面http://code.google.com/apis/picasaweb/developers_guide_protocol.html找到很多相關(guān)的信息。另一種方式便是使用最樸素的網(wǎng)絡(luò)請求方式來自己構(gòu)造請求并解析回傳的數(shù)據(jù)。

由于Picasa只提供了Java,.NET,Python和PHP的接口，而Gadget目前只能使用JavaScript，因此我們只能使用樸素方式。

繼續(xù)第三節(jié)的路子，仍然使用XmlHttpRequest向Picasa服務(wù)發(fā)起請求，也要處理好四部分信息。

請求發(fā)向哪個URL：為了獲取Picasa的相冊信息，要向http://picasaweb.google.com/data/feed/api/user/default發(fā)請求，這個URL其實可以有很多變化的地方。例如user/default這個地方是請求所附token所屬的用戶相冊信息，這里當然可以明確的指定用戶名。”api”可以換成”base”，這個將影響回傳數(shù)據(jù)的格式，但Goolge推薦使用api而不是base。

請求的類型：我們是要索取數(shù)據(jù)，因此這是一個查詢的動作，應(yīng)該使用GET。

請求頭：只需要把token放進去就好。這樣來放：

消息體：對于我們查詢相冊的請求，不需要任何的消息體。

具體的代碼都在Main.prototype.fetchAlbumsInfo()函數(shù)中，就像這樣：

最后兩個函數(shù)是下一步要做的工作：解析回傳的相冊數(shù)據(jù)，并下載每個相冊的縮略圖。

 

要想解析回傳數(shù)據(jù)，首先得知道回傳的數(shù)據(jù)是什么。你可以把這些數(shù)據(jù)打印出來看看，應(yīng)該是類似下面的樣子：

怎么，看著有點眼熟？沒錯，這個回傳數(shù)據(jù)所使用的格式正是標準的Atom Feed（更多的描述可以參考W3C的標準和下面的鏈接：http://code.google.com/intl/zh-CN/apis/picasaweb/developers_guide_protocol.html）。

可以根據(jù)Atom Feed的格式來編寫我們解析回傳數(shù)據(jù)的函數(shù)parseAlbumFeed()，這個函數(shù)的作用是從回傳的xml數(shù)據(jù)中找出我們關(guān)心的幾樣東西：該用戶目前擁有的所有的相冊信息，包括每個相冊的標題，描述，訪問權(quán)限以及縮略圖的地址。找出這些信息以后，將會拼成一個包含相冊（Album）的數(shù)組作為函數(shù)返回值。

具體代碼如下：

這個函數(shù)中用到了一些我們還沒有新建的類，相冊（Album）以及縮略圖(Thumbnail)。這些類的聲明可以放在一個新的名為album.js的文件中，并在我們整個Gadget的main.xml文件中指名要導入它。因此main.xml的最后幾行應(yīng)該看上去是這個樣子：

而album.js的內(nèi)容大體如下：

最后還要在main.js里面添加一個函數(shù)createDomDocument()，用來提供一個DOM對象供我們解析XML用。代碼如下：

下一節(jié)來說說怎么取得相冊的縮略圖并顯示在Gadget的界面中。

向Google的服務(wù)器發(fā)起登錄請求之后，得到了免死金牌token，以后就可以拿著這個token去犯罪，不是，去Google的其它服務(wù)取數(shù)據(jù)，但是在此之前應(yīng)該第一，從響應(yīng)的消息中把token找出來；第二，這個token應(yīng)該想辦法保存起來，以備以后使用。

上一節(jié)已經(jīng)把響應(yīng)的內(nèi)容打印了出來，它的格式也很簡單，因此用下面的代碼很容易就可以把響應(yīng)的內(nèi)容轉(zhuǎn)成方便我們使用的形式，即一個map的形式，通過鍵值對來存儲：

在我們的相應(yīng)回調(diào)函數(shù)里，就可以調(diào)用這個函數(shù)處理一下響應(yīng)，從結(jié)果中取鍵為”Auth”這一項的值，并保存在Gadget Host為我們準備好的一個負責持久化的對象options中。找到上一節(jié)Main.prototype.login的代碼，把響應(yīng)的回調(diào)函數(shù)改成下面的樣子：

最后加的一行main.onLoginSuccess()就是我們下一步動作的起點，在這里應(yīng)該開始去取用戶mymail2009.test@gmail.com所擁有的相冊信息了，我們先聲明一個空函數(shù)放在那里。

繼續(xù)之前多扯兩句options這個對象，這是Gadget Host提供的持久化對象，你可以從代碼中看到它還有對存儲的內(nèi)容進行加密的功能，Google的文檔中提到這個options對象在后臺實際上是把內(nèi)容保存在一個XML文件中，當然該文件的位置是不會告訴你的啦，哈哈。

下一節(jié)將向Picasa服務(wù)發(fā)起請求！

Google帳戶最早用來申請巨大的Gmail郵箱（如今看來，一般個大吧），隨著后來的Blogger，Picasa，Docs等各種服務(wù)上線，也就順路繼承了過來。現(xiàn)在使用一個Google帳戶，就可以同時使用這些服務(wù)。

既然我們打算寫一個從Picasa取相冊數(shù)據(jù)的Gadget，就免不了要先了解一些和Goolge帳戶有關(guān)的知識。因為Picasa的數(shù)據(jù)也是受保護的，并非誰要看都可以（公開的相冊除外哦，那都是炫耀冊，巴不得全天下人都看見呢），我們的程序也不例外，要想取到相冊的數(shù)據(jù)，程序必須向Google的服務(wù)器證明自己得到了相應(yīng)用戶的授權(quán)。

一個人類用戶當然可以這樣做：打開Picasa的首頁，發(fā)現(xiàn)要求登錄，于是輸入自己的用戶名密碼，成功后就查看自己的相冊。我們的程序可干不了，它不會打開瀏覽器，好吧，這個它會，但打開以后它找不著用戶名的輸入框在哪，即便找到了，也不知該往里面填什么，即便填對了，也不知要看什么，即便看到了，也看不懂，即便看懂了也學不會……（讀者：你貧不貧？）

所以一切的一切都還要咱們自己來寫，當然少不了Google的幫忙。

為了方便應(yīng)用程序的登錄，Google在自己的服務(wù)器上開放了被稱之為“Google Account Authentication”的服務(wù)，我們只用到其中一種方式：ClientLogin。使用這種方式訪問Google的服務(wù)大致是下面的流程：

很容易看出來，這基本上是一個兩步驟的工作：首先使用一個Google帳戶訪問Google Account Authentication 服務(wù)，并得到一個可以合法訪問服務(wù)數(shù)據(jù)的token（Google把它叫做得到一個“授權(quán)”，不過習慣上還是叫token吧，就是令牌，拿了以后皇帝不能砍你頭的那種，此過程也叫做申請一個token）；使用上一步得到的token去訪問具體的服務(wù)并取得數(shù)據(jù)（我們的例子中就是訪問Picasa服務(wù)）。

有一些東西從圖上看不出，我來說一說。一是程序訪問Gmail的時候使用的不是這種方式（畢竟Gmail太早啦，那時連Google自己都沒有考慮清楚吧），但其他大部分Goolge服務(wù)，包括Calendar,Docs,Picasa,Blogger,Contacts,Google Apps等等，都是上面這個流程。二是并非申請了一個token以后，就可以訪問Google所有的服務(wù)，實際上需要為每個服務(wù)申請不同的token。

具體到代碼中，我們使用XmlHttpRequest對象來發(fā)送請求并且接受回傳的數(shù)據(jù)。

XmlHttpRequest是Gadget Host提供的一個類型（注意我沒有說對象，因此要用的時候你還得自己初始化，也就是new一下，哈哈），其行為與W3C所指定的標準XmlHttpRequest相同。再一次的，不要聯(lián)想到瀏覽器，你不能假設(shè)這個XmlHttpRequest與IE或者FireFox提供的XmlHttpRequest有任何聯(lián)系，更不能依賴這樣的假設(shè)來編寫程序。

好，廢話少說，還用上一節(jié)新建的“白Gadget“（笑），在main.js文件里添加這樣一個函數(shù)：

調(diào)用這個函數(shù)就可以得到一個XmlHttpRequest的對象啦。

然后為我們的Gadget添加一個主類，并把需要的對象引用也聲明好，這些都寫在main.js文件中，像這樣：

我們就要在Main.login()函數(shù)中寫我們?nèi)?/span>token的邏輯。

詳細說說申請token的過程。請求是通過XmlHttpRequest對象發(fā)起的，而對一個請求來說，最重要的信息有四個：請求的URL，請求的類型，請求頭和消息體。

URL是說你的請求要發(fā)往哪里，既然我們要使用Google的服務(wù)，那當然要往Google那里發(fā)了，具體應(yīng)該為：

https://www.google.com/accounts/ClientLogin

如果你沒有看出這是一個安全的https請求，那我提醒一下（如果你看出來了，我就不提醒了，笑）。

請求的類型是指你要Google的服務(wù)器替你做什么事情，是返回你要查詢的數(shù)據(jù)？還是為你更新已有的數(shù)據(jù)，抑或僅僅是提交一些數(shù)據(jù)，還是要服務(wù)器幫你刪除一些數(shù)據(jù)？

Google的服務(wù)器通過你提交請求的類型來做相應(yīng)的操作，每一種操作的類型對應(yīng)如下：

•  查詢　　GET
•  提交　　POST
•  更新　　PUT
•  刪除　　DELETE

看著眼熟么？沒錯，正是輕量級的Web Service接口REST！

我們做登錄顯然是一個提交的動作， 要把我們的用戶名和密碼告訴Google，因此我們的請求類型是POST。

對登錄來說，請求頭沒有特殊要求，只需要請求頭Content-Type，其值為application/x-www-form-urlencoded

所需的用戶名，密碼等信息被統(tǒng)一稱為“屬性”，屬性的值將放在消息體中發(fā)送。因此你的消息體看起來是下面這個樣子的一個字符串：

Email=mymail2009.test%40gmail.com&Passwd=mymail2009&service=lh2&source=gd-picasa-gadget-1.0.0.0&accountType=HOSTED_OR_GOOGLE

注意其中紅色的部分，用戶名和密碼的位置你當然很容易找到，”service=lh2”這一項就指明了你要為訪問什么服務(wù)申請token，lh2是指Picasa，如果訪問Google Docs則要填writely，詳細的列表可以看這一節(jié)最后的附錄。

好，把登錄的代碼整個貼出來，你應(yīng)該很容易找到以上四部分對應(yīng)的地方。

在請求的回調(diào)函數(shù)中，目前只是先簡單的打印了相應(yīng)的文本內(nèi)容，實際上應(yīng)該在這里做更多的事，詳情咱們下節(jié)再聊。如果你看到類似下面這樣的輸出內(nèi)容，說明登錄的請求成功了。如果沒有成功，很可能是因為我已經(jīng)換掉了用戶名和密碼，用你自己的Google帳戶試試看。

應(yīng)該看到的內(nèi)容：

SID＝

DQAAAHYAAADYQ4hToTAEYRu0uEXP9yXZ1uc_W3-kBtZFpug78XQDGiykOb-Sv2qdXtdUOL-
npRJm9SSq-AEvSBodrcuy3UwgFM8SX_z6fXzpGaJzHzQx5YTzR0AJHCEkFh
4yOoBFs0iCE2LI0LWQs6_2BFyIuLLMwRA8m3vfuVzNE3CHjrUHZA

LSID＝

DQAAAHgAAAClSiMWRfKAonW8zIytZ7NEizJNMQZojiNqsDxm3elei36MV
7GzM72bMiqdQawt8Fd1Dpp68p5bs1XYOXUPmDunUsZM1BZsAiXbIEouAJz1XjlysUQG-0p9969zYCvUm2tqWkA1BFVU2UqvjMAaBSgj10VkZzvcAbZB8nQf_mwRyg

Auth＝

DQAAAHcAAAClSiMWRfKAonW8zIytZ7NEizJNMQZojiNqsDxm3elei36
MV7GzM72bMiqdQawt8FcmxySIt75kfLxcis5BZnNCsyVuCwKM-DtNZcToUtm9IWoJyvNbUD9UTFYZPdBu1OyXsfY_QJHZfZdAT2QC
cExSIYKMvLfhhit9RPz4Gk2xlQ/n

Auth那一項后面的值就是token啦，可以不被砍頭了。

附錄：已知的Google服務(wù)及服務(wù)名

Calendar Data API	cl
Google Base Data API	gbase
Blogger Data API	blogger
Contacts Data API	cp
Documents List Data API	writely
Picasa Web Albums Data API	lh2
Google Apps Provisioning API	apps
Spreadsheets Data API	wise
YouTube Data API	youtube

前文說道開發(fā)一個Gadget可以分為兩個步驟：先寫界面的XML文件，再寫邏輯部分的JavaScript。我們就遵循這個步驟來寫一個再簡單也不過的Gadget。

用到的工具有兩個，一個是隨Google Desktop SDK附帶的Gadget Designer，用來編寫并有限的預覽界面，還可以調(diào)試JavaScript（這個就更有限了）；一個是Google Desktop，用來測試寫好的Gadget。下面要寫的例子是我在為某研究院某個項目策劃階段作POC時所寫的一個小例子，可以顯示一個Google用戶的Picasa相冊中的Album名稱和縮略圖。雖然很小，但包含了Google賬戶的自動登錄，顯示網(wǎng)絡(luò)圖片，XmlHttpRequest的使用等很多實用技巧。整個完成之后是這個樣子：

 

請跟我一起來。現(xiàn)在打開Gadget Designer，選擇File->New Gadget，輸入了名稱“Picasa”之后，就可以看到一個完整Gadget的雛形了。你可以找到這個項目所在的文件夾，雙擊其中的gadget.gmanifest，此時如果你已經(jīng)安裝了Google Desktop，就可以看到Desktop自動啟動，并把這個很“白”的Gadget（別笑，除了一張白色背景圖片以外，確實什么也沒有）顯示在Sidebar中。如圖：

到項目文件夾里可以看到一個main.xml文件和一個main.js文件。我們的界面就是在main.xml文件里指定的，打開它，可以看見它指定了一張GadgetDesigner幫我們生成的白色png圖片作背景，還指定了我們要導入哪些個.js文件。我們來小改兩個地方：

一是把view的height改成250，二是給img元素添加一個屬性name并給一個值，就像這樣：

 

然后雙擊gadget.gmanifest，看看更改效果：

乍一看貌似沒什么改變，但是注意看我用黑色線圈出來的那一條橫杠，那是我們的Gadget的下邊沿，說明它的高度還是變化了，但是白色的背景沒有變，因為我們沒有改變背景圖片的大小。現(xiàn)在通過.js文件中代碼的方式來改變背景圖片的高度，可以看出些有意思的東西。

打開main.js文件，你應(yīng)該會看到一個view_onOpen()函數(shù)，這就是Gadget啟動時會自動調(diào)用的第一個函數(shù)（好吧，并不嚴格，但是在調(diào)用的順序上，它的確是相當靠前的），我們就在這個函數(shù)內(nèi)部添加下面這一句：

再雙擊gadget.gmanifest運行看看，白色背景也變高了吧。

我知道你一定會問，代碼里的bgImage是什么東西？怎么沒見在任何地方聲明這個變量，也沒見任何地方作初始化呢？回想我們剛才在main.xml文件里做了什么？我們給背景圖片取了一個名字，叫bgImage，而且別懷疑，你在代碼里訪問的這個bgImage，正是那張圖片！背后的工作就是Gadget Host通過JavaScript引擎為我們做的，凡是在.xml文件里放置的東西（無論什么，圖片也好，按鈕也好，一個抽象的div也好），只要你給了一個name屬性，在JavaScript代碼中就可以直接使用這個名字來訪問該對象（前提是你給的名字得是獨一無二的），這與瀏覽器中隨時可以訪問document對象而不用做任何聲明一樣，那是瀏覽器這個運行環(huán)境提供的對象，隨時可用。

另一個值得注意的地方是在.xml文件里，屬性的值都必須加上引號，像height=”250”（因為那里使用的是標準的xml語法），而在JavaScript代碼中，就要根據(jù)屬性具體的類型來決定，像高度這種整數(shù)型的值，就不用加。

你可能還會問，那么bgImage這個對象，是什么類型的，它有些什么屬性和方法可供我使用呢？它是一個img類型的對象，參考http://code.google.com/intl/zh-CN/apis/desktop/docs/gadget_apiref.html這個鏈接，這也是Google Desktop Gadget的API參考頁面，列出了Gadget Host提供的各種對象屬性和方法的說明（雖然事實驗證，Google自己列的這些都不全面，后話）。

最后叮囑一句：盡管main.xml文件里的東西（什么img啊，以后還會加進div啊，checkbox之類的東西）看起來多么的像HTML，Gadget都和Web沒有天然的聯(lián)系。Google自己發(fā)布了一些Gadget，例如Gmail和Google Docs，外觀與這兩個服務(wù)的網(wǎng)頁非常像，再加上Gadget也主要使用JavaScript開發(fā)（也少不了Universal Gadget跟著摻合），間接導致了總有人把Gadget顯示的地方考慮成一個小的瀏覽器窗口，而想把Web的一些東西簡單的放在這里，到底行不行呢？李寧說：一切皆有可能。阿迪說：沒有不可能。匹克說：我能，無限可能。我要說：可能，但很難（笑）。

所以在編寫Gadget的時候，最好的方法是把它當成純粹的桌面程序，忘掉Web的那一套。

這一節(jié)給大家入個門，下一節(jié)開始說說在Gadget中怎么做Google帳戶的登錄，還會很羅嗦的，請見諒（笑）。