支援向量機（svm）非線性資料分割
本指導中你将學到：
l 當不可能線性分割訓練資料時，怎樣定義svm最優化問題；
l 在這種問題上，怎樣配置cvsvmparams中的參數滿足你的svm；
為什麼我們有興趣擴充svm最優化問題來處理非線性分割訓練資料？svm在計算機視覺應用中需要一個比線性分類器更加強有力的工具。原因在于，事實上，在這種問題上訓練資料幾乎不能被一個超平面分割開。考慮一個這種任務，例如，面部識别。這種情況下，訓練資料由圖像上的一組面部資料和非面部（任何除面部以外的其他東西）資料組成。這些訓練資料非常複雜，以至于可以對每一個樣本找到一種表述（特征向量），能把整個資料線性的從非面部中分割出來。
記住，通過svm我們得到一個分割超平面。那麼，因為現在訓練資料是非線性可分的了，我們必須承認原來找到的超平面将不能正确分類其中的一些樣本。誤分類是優化問題中需要考慮的一個新的變化。新的模型既要滿足找超平面的老問題，給出最大邊緣，并且還要做新工作，正确地生成新的訓練資料，而使其不出現太多分類錯誤。我們先從尋找超平面這個優化問題的構想出發，由超平面給出最大邊緣（邊緣的概念在上篇中有解釋）：
有很多種方法可以修改這個模型，是以它把誤分類考慮在内了。比如，你可以考慮最小化同一個量加上一個常數乘以訓練資料誤分類的錯誤數量，例如：
然而，這個并不是最好的解決方案，在其他原因中（amongsome other reasons）,我們對距離期望決策區域距離很小的誤分類樣本和沒有誤分類的樣本不作區分。是以，更好的解決方案将把誤分類樣本離他們的正确決策區域的距離考慮在内，例如：
對于每個訓練資料樣本，要定義一個新的參數ξi。每一個此參數都包含了訓練樣本到他們的正确決策區域的距離。下圖顯示了兩類非線性可分類的訓練資料，一個分類超平面和誤分類樣本到正确決定區域的距離。
注意：圖中值隻顯示了誤分類樣本的距離。其他樣本的距離為0，因為他們已經在正确的區域了。圖中紅色和藍色的線是每個決策區域的邊界。每一個ξi是從誤分類點到期望區域的邊界，明白這一點很重要。最後，優化問題的新公式為：
怎麼選擇常數c呢？很明顯這個問題依賴于訓練資料是怎麼分布的。盡管沒有統一的答案，考慮一下規則會很有幫助：
l c的值越大，誤分類的數量會越少，但邊緣也會越小。這種情況，是把誤分類錯誤看的很重，對誤分類要求嚴格。然而，優化的目标是最小化自變量，少量誤分類錯誤是允許的。
l c值越小，邊緣越大，誤分類錯誤越大。這種情況下最小化沒有過多考慮求和項，是以其焦點在于尋找具有更大邊緣的超平面。
你可能也在opencv源代碼庫中的此路徑sample/cpp/tutorial_code/gpu/non_linear_svm/non_linear_svms檔案夾中找到了源代碼，以及那些視訊檔案，也可以在此下載下傳。
譯者注：由于注釋直接添加在代碼中會導緻排版問題，偷懶把注釋堆在此下了：
（1）建立訓練資料
此處訓練資料由一組标記了的二維點組成，共兩類。為了讓這個練習更加有吸引力，訓練資料通過均勻分布機率密度方程(a uniform probability density functions (pdfs))随機生成。我們已經把訓練資料的生成分成了兩個主要部分。第一部分，我們生成線性可分的兩類資料。
第二部分，我們為兩類建立非線性可分的資料和重疊的資料。
譯者注：
void rng::fill(inputoutputarray mat, int disttype, inputarray a, inputarray b, bool saturaterange=false )
這個函數是對矩陣mat填充随機數，随機數的産生方式有參數2來決定，如果為參數2的類型為rng::uniform，則表示産生均一分布的随機數，如果為rng::normal則表示産生高斯分布的随機數。對應的參數3和參數4為上面兩種随機數産生模型的參數。比如說如果随機數産生模型為均勻分布，則參數a表示均勻分布的下限，參數b表示上限。如果随機數産生模型為高斯模型，則參數a表示均值，參數b表示方程。參數5隻有當随機數産生方式為均勻分布時才有效，表示的是是否産生的資料要布滿整個範圍（沒用過，是以也沒仔細去研究）。另外，需要注意的是用來儲存随機數的矩陣mat可以是多元的，也可以是多通道的，目前最多隻能支援4個通道。
（2）建立svm參數
可參見上一篇中關于cvsvmparams的講解。
這裡跟我們前一篇的配置僅有兩處不同：
l cvsvm::c_svc：我們這裡選擇了一個很小的數值，目的是，在優化中不對誤分類錯位做過多懲罰。這麼做到原因是我們希望獲得最接近直覺預期的解決方案。然而，我們推薦通過調整獲得一個更能反映問題的參數。
注意：這裡在兩類之間重疊的點很少，給frac_linear_sep一個更小的值，點的密度将增加，而且參數cvsvm::c_svc的影響更深。
l termination criteria of thealgorithm,算法終止标準：為了通過非線性可分離的訓練資料正确地解決問題，最大疊代次數必須增加很多。特别的，我們對這一參數值增加了5個數量級。
（3）訓練svm
我們調用方法cvsvm::train來建立svm模型。注意訓練過程可能會花很長時間。運作改程式是要有耐心。
（4）顯示決策區域
方法cvsvm::predict通過已訓練的svm來分類輸入樣本。在此例中，我們用這個方法依據svm的預測來着色相關區域。也就是說，周遊一個圖像，把它的像素當成笛卡爾平面的點。每一個點根據svm預測的類來着色；深綠色的是标記為1的類，深藍色是标記為2的類。
（5）顯示訓練資料
方法circle用來顯示訓練資料的樣本點。标記為1的類的樣本顯示為亮綠色，标記為2的類的樣本點顯示為亮藍色。
（6）支援向量機
這裡我麼用來很多方法來擷取支援向量的資訊。方法cvsvm::get_support_vector_count輸出該問題中支援向量的總數，方法cvsvm::get_support_vector可以根據索引擷取到每一個支援向量。我們用這些方法找到是支援向量的訓練樣本，并顯示為高亮。
l 代碼打開了一個圖像，顯示兩類的訓練資料。其中一類顯示為亮綠色，另一類顯示為亮藍色。
l 訓練svm，并用它來分類圖像上所有的像素點。圖像被分成藍綠兩塊區域。兩個區域的邊界就是分割超平面。因為訓練資料是非線性可分割的，能夠看到，一些樣本被誤分類了；一些綠色的點在藍色區域中，還有一些藍色的點在綠色區域中。
l 最後，被灰色的圈包圍的訓練樣本的點是支援向量。
原文：http://docs.opencv.org/doc/tutorials/ml/non_linear_svms/non_linear_svms.html#nonlinearsvms