支持向量机（理论+opencv实现）
1.拉格朗日乘子（Lagrangemultiplier） 假設需要求極值的目標函數(objectivefunction)為f(x,y)，限制條件為φ(x,y)=M 設? 定義一個新函數? 則用偏導數方法列出方程：?、?、??求出x,y,λ的值，代入即可得到目標函數的極值。 擴展為多個變量的式子為： F(x1,x2,...,xn,λ)=f(x1,x2,...,xn)-λg(x1,x2,...,xn) 則求極值點的方程為：?F/?xi=0（xi即為x1,x2,...,xn等自變量）?F/?λ=g(x1,x2,...,xn)=0 2.凸二次規劃 二次規劃的一般形式可以表示為，如右下圖： 其中G是Hessian矩陣，τ是有限指標集，c，x和{ai}，都是R中的向量。如果Hessian矩陣是半正定的，則我們說（1.1）是一個凸二次規劃， 在這種情況下該問題的困難程度類似于線性規劃如果=0，二次規劃問題就變成線性規劃問題了）。 如果有至少一個向量滿足約束并且在可行域有下界，則凸二次規劃問題就有一個全局最小值。 如果是正定的，則這類二次規劃為嚴格的凸二次規劃，那么全局最小值就是唯一的。如果是一個不定矩陣，則為非凸二次規劃， 這類二次規劃更有挑戰性，因為它們有多個平穩點和局部極小值點。
3.線性中的對偶
?
線性規劃有一個有趣的特性，就是任何一個求極大的問題都有一個與其匹配的求極小的線性規劃問題。例；原問題為
MAX X=8*Z1+10*Z2+2*Z3
s.t. 2*Z1+1*Z2+3*Z3 <=70
4*Z1+2*Z2+2*Z3 <=80
3*Z1+ 1*Z3 <=15
2*Z1+2*Z2 <=50
Z1，Z2，Z3 〉=0
Z則其對偶問題為
MIN =70*Y1+80*Y2+15*Y3+50*Y4
s.t 2*y1+4*y2+3*y3+2*y4>=8
1*y1+2*y2+ 1*y4>=10
3*y1+2*y2+1*y3 >=2
y1,y2,y3,y3>=0
可以看出：
1、若一個模型為目標求 極大 約束為 小于等于的不等式，則它的對偶模型為目標求極小 約束為極大的不等式
即 “MAX，〈=” “與MIN，〉=”相對應
2、從約束條件系數矩陣來看，一個模型中為A 另一個為A的轉質，一個模型是 m個約束n個變量 則他的對偶模型為n個約束 m個變量
3、從數據b c 的位置看 兩個規劃模型中b和 c的位置對換
即8、10、2 與 70、80、15、50 對換
4、兩個規劃模型中變量非負。
?
?4. 內積空間
?
?5.歐式空間
?
?
?6.線性空間、希爾伯特空間、巴拿赫空間
?
在數學中有許多空間表示，比如歐幾里德空間、賦范空間、希爾伯特空間等。這些空間之間有什么關系呢？
首先要從距離的定義說起。?
什么是距離呢？實際上距離除了我們經常用到的直線距離外，還有向量距離如Σni=1xi?yi????????√， 函數距離如∫ba(f(x)?g(x))2dx、 曲面距離、折線距離等等，這些具體的距離與距離之間的關系類似于蘋果、香蕉等與水果的關系，前面是具體的事物，后面是抽象的概念。距離就是一個抽象的概念，其定義為：?
設X是任一非空集，對X中任意兩點x,y，有一實數d(x,y)與之對應且滿足：?
1. d(x,y)?≥0，且d(x,y)=0當且僅當x=y;?
2. d(x,y)=d(y,x);?
3. d(x,y)?≤d(x,z)+d(z,y)。?
稱d(x,y)為X中的一個距離。
定義了距離后，我們再加上線性結構，如向量的加法、數乘，使其滿足加法的交換律、結合律、零元、負元；數乘的交換律、單位一；數乘與加法的結合律（兩個）共八點要求，從而形成一個線性空間，這個線性空間就是向量空間。
在向量空間中，我們定義了范數的概念，表示某點到空間零點的距離：?
1. ||x||?≥0;?
2. ||ax||=|a|||x||;?
3. ||x+y||≤||x||+||y||。
將范數與距離比較，可知，范數比距離多了一個條件2，數乘的運算，表明其是一個強化了的距離概念。范數與距離的關系可以類似理解為與紅富士蘋果與蘋果的關系。
接下來對范數和距離進行擴展，形成如下：?
范數的集合??賦范空間+線性結構?線性賦范空間?
距離的集合??度量空間+線性結構?線性度量空間
下面在已經構成的線性賦范空間上繼續擴展，添加內積運算，使空間中有角的概念，形成如下：?
線性賦范空間+內積運算??內積空間；?
這時的內積空間已經有了距離、長度、角度等，有限維的內積空間也就是我們熟悉的歐氏空間。
繼續在內積空間上擴展，使得內積空間滿足完備性，形成希爾伯特空間如下：?
內積空間+完備性??希爾伯特空間?
其中完備性的意思就是空間中的極限運算不能跑出該空間，如有理數空間中的2√?的小數表示，其極限隨著小數位數的增加收斂到2√，但2√?屬于無理數，并不在有理數空間，故不滿足完備性。一個通俗的理解是把學校理解為一個空間，你從學校內的宿舍中開始一直往外走，當走不動停下來時（極限收斂），發現已經走出學校了（超出空間），不在學校范圍內了（不完備了）。希爾伯特就相當于地球，無論你怎么走，都還在地球內（飛出太空除外）。
此外，前面提到的賦范空間，使其滿足完備性，擴展形成巴拿赫空間如下：?
賦范空間+完備性??巴拿赫空間
以上均是在距離的概念上進行添加約束形成的，遞增關系如下：?
距離?范數?內積?
向量空間+范數??賦范空間+線性結構?線性賦范空間+內積運算?內積空間+完備性?希爾伯特空間?
內積空間+有限維?歐幾里德空間?
賦范空間+完備性?巴拿赫空間
順便提以下，對距離進行弱化，保留距離的極限和連續概念，就形成拓撲的概念。
?
?
?
有了上面的基礎知識，下面開始支持向量機的理論學習
?
注：已經有很多關于SVM的優秀文章，自認為我距離大牛很遠而且表達的沒他們好，所以接下來的分析是我覺得難懂的地方，或者自認為老師和前輩們感覺太簡單沒說到的地方。?
?
1.開篇距離公式推導
推導如下的公式：
?
?
2.SMO算法（主體來自博客，下面會給出鏈接，自己更改的部分已經標注）
假設我們選取了初始值滿足了問題中的約束條件。接下來，我們固定，這樣W就是和的函數。并且和滿足條件：
由于?，所以推到出：
?
由于都是已知固定值，因此為了方面，可將等式右邊標記成實數值。
?
?
當和異號時，也就是一個為1，一個為-1時，他們可以表示成一條直線：a1-a2=ζ，相當于x-y=c作圖，斜率為1。如下圖：
?
橫軸是，縱軸是，和既要在矩形方框內，也要在直線上，因此
?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??，
注：這里L、H表示a1給定之后a2的取值范圍，從圖中可以看到a2取值兩種情況，其中{0，C-ζ}屬于一條直線、{-ζ，C}屬于一條直線，且后者在前者之上，那么：
a2的最小值從{0，-ζ}取最大的值，a2的最大值從{C-ζ，C}取最小的值，因為?ζ = a1 - a2，所以：
同理，當和同號時，
?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ，
?
?
?
opencv實現SVM
?
按照以前的性格肯定是用C++把SVM寫出來，現在感覺沒多大意思，因為很多算法都要自己去實現太難了而且沒那么多時間，畢竟現在還用不到SVM，先用opencv自帶的例子測試再說。
本文用的opencv3.1實現的非線性分類，看了網上的基本都是2.4或者2.9，要么就是用的線性實現的，弄了很長世間才實現！
?
?
其實主要是講解一些參數的意義和怎么調用：
?
SVM的類型：
1 enum Types { 2 /** C-Support Vector Classification. n-class classification (n \f$\geq\f$ 2), allows 3 imperfect separation of classes with penalty multiplier C for outliers. */ 4 C_SVC=100,?//C類支持向量分類機。?n類分組??(n≥2)，允許用異常值懲罰因子C進行不完全分類。 5 /** \f$\nu\f$-Support Vector Classification. n-class classification with possible 6 imperfect separation. Parameter \f$\nu\f$ (in the range 0..1, the larger the value, the smoother 7 the decision boundary) is used instead of C. */ 8 NU_SVC=101,//?類支持向量分類機。n類似然不完全分類的分類器。參數為取代C（其值在區間【0，1】中，nu越大，決策邊界越平滑）。 9 /** Distribution Estimation (One-class %SVM). All the training data are from 10 the same class, %SVM builds a boundary that separates the class from the rest of the feature 11 space. */ 12 ONE_CLASS=102,//單分類器，所有的訓練數據提取自同一個類里，然后SVM建立了一個分界線以分割該類在特征空間中所占區域和其它類在特征空間中所占區域。 13 /** \f$\epsilon\f$-Support Vector Regression. The distance between feature vectors 14 from the training set and the fitting hyper-plane must be less than p. For outliers the 15 penalty multiplier C is used. */ 16 EPS_SVR=103,//類支持向量回歸機。?代替了?p。? 17 /** \f$\nu\f$-Support Vector Regression. \f$\nu\f$ is used instead of p. 18 See @cite LibSVM for details. */ 19 NU_SVR=104 20 };?
核函數：
1 enum KernelTypes { 2 /** Returned by SVM::getKernelType in case when custom kernel has been set */ 3 CUSTOM=-1, 4 /** Linear kernel. No mapping is done, linear discrimination (or regression) is 5 done in the original feature space. It is the fastest option. \f$K(x_i, x_j) = x_i^T x_j\f$. */ 6 LINEAR=0,//線性核函數 7 /** Polynomial kernel: 8 \f$K(x_i, x_j) = (\gamma x_i^T x_j + coef0)^{degree}, \gamma > 0\f$. */ 9 POLY=1,//多項式函數(r*u'v + coef0)^degree 10 /** Radial basis function (RBF), a good choice in most cases. 11 \f$K(x_i, x_j) = e^{-\gamma ||x_i - x_j||^2}, \gamma > 0\f$. */ 12 RBF=2,//exp(-gamma|u-v|^2)基于徑向的函數，對于大多數情況都是一個較好的選擇： 13 /** Sigmoid kernel: \f$K(x_i, x_j) = \tanh(\gamma x_i^T x_j + coef0)\f$. */ 14 SIGMOID=3,//tanh(r*u'v + coef0) 15 /** Exponential Chi2 kernel, similar to the RBF kernel: 16 \f$K(x_i, x_j) = e^{-\gamma \chi^2(x_i,x_j)}, \chi^2(x_i,x_j) = (x_i-x_j)^2/(x_i+x_j), \gamma > 0\f$. */ 17 CHI2=4, 18 /** Histogram intersection kernel. A fast kernel. \f$K(x_i, x_j) = min(x_i,x_j)\f$. */ 19 INTER=5 20 };?
核函數的參數：
成員變量degree針對多項式核函數degree的設置，
gamma針對多項式/rbf/sigmoid核函數的設置，
coef0針對多項式/sigmoid核函數的設置，
Cvalue為損失函數，在C-SVC、e-SVR、v-SVR中有效，
nu設置v-SVC、一類SVM和v-SVR參數，
p為設置e-SVR中損失函數的值，
class_weightsC_SVC的權重，
?
一些函數的參數：
1 TermCriteria::TermCriteria(int _type, int _maxCount, double _epsilon) 2 : type(_type), maxCount(_maxCount), epsilon(_epsilon) {} 3 //_type:迭代結束的類型，如果為CV_TERMCRIT_ITER，則用最大迭代次數作為終止條件，如果為CV_TERMCRIT_EPS?則用精度作為迭代條件，如果為CV_TERMCRIT_ITER+CV_TERMCRIT_EPS則用最大迭代次數或者精度作為迭代條件，看哪個條件先滿足。 4 //_maxCount：終止程序的最大迭代次數 5 //_epsilon：終止程序的精度 1 train( InputArray samples, int layout, InputArray responses ); 2 //samples：輸入數據 3 //layout： 讀取數據方式 4 //----ROW_SAMPLE = 0, //!< 一行為一個樣本 5 //----COL_SAMPLE = 1 //!< 一列為一個樣本 6 //responses：返回的數據（默認為不返回）?
上代碼：
1 #include <opencv2/opencv.hpp> 2 #include <iostream> 3 #include "math.h" 4 5 using namespace cv; 6 using namespace std; 7 int test = 0; 8 RNG rng(99999); 9 void drawCross(Mat &img, Point center, Scalar color) 10 { 11 int col = center.x > 2 ? center.x : 2; 12 int row = center.y> 2 ? center.y : 2; 13 line(img, Point(col - 2, row - 2), Point(col + 2, row + 2), color); 14 line(img, Point(col + 2, row - 2), Point(col - 2, row + 2), color); 15 } 16 17 void newSvmTest(int rows, int cols, int testCount) 18 { 19 assert(testCount >= rows * cols); 20 21 Mat img = Mat::zeros(rows, cols, CV_8UC3); 22 Mat testPoint = Mat::zeros(rows, cols, CV_8UC1); 23 Mat data = Mat::zeros(testCount, 2, CV_32FC1); 24 Mat res = Mat::zeros(testCount, 1, CV_32SC1); 25 26 //Create random test points 27 for (int i = 0; i < testCount; i++) 28 { 29 int row = rng.uniform(0,255) % rows; 30 int col = rng.uniform(0,255) % cols; 31 //-----存儲數據 32 if (testPoint.at<unsigned char>(row, col) == 0) 33 { 34 testPoint.at<unsigned char>(row, col) = 1; 35 data.at<float>(i, 0) = float(col) / cols; 36 data.at<float>(i, 1) = float(row) / rows; 37 } 38 else//防止重復 39 { 40 i--; 41 continue; 42 } 43 //分成三類 44 if (row > (50 * cos(col * CV_PI / 100) + 200)) 45 { 46 drawCross(img, Point(col, row), CV_RGB(255, 0, 0)); 47 res.at<unsigned int>(i, 0) = 1; 48 } 49 else 50 { 51 if (col > 200) 52 { 53 drawCross(img, Point(col, row), CV_RGB(0, 255, 0)); 54 res.at<unsigned int>(i, 0) = 2; 55 } 56 else 57 { 58 drawCross(img, Point(col, row), CV_RGB(0, 0, 255)); 59 res.at<unsigned int>(i, 0) = 3; 60 } 61 } 62 63 } 64 Mat show = img.clone(); 65 //----SVM訓練 66 cv::Ptr<cv::ml::SVM> svm = cv::ml::SVM::create(); 67 svm->setType(cv::ml::SVM::Types::C_SVC); 68 svm->setKernel(cv::ml::SVM::KernelTypes::RBF); 69 svm->setDegree(3); 70 svm->setGamma(3); 71 svm->setCoef0(1.0); 72 svm->setC(10); 73 svm->setNu(0); 74 svm->setP(0.1); 75 svm->setTermCriteria(cv::TermCriteria(cv::TermCriteria::EPS, 1000, FLT_EPSILON)); 76 // train operation 77 svm->train(data, cv::ml::SampleTypes::ROW_SAMPLE, res); 78 //----預測數據 79 for (int i = 0; i< rows; i++) 80 { 81 for (int j = 0; j< cols; j++) 82 { 83 Mat m = Mat::zeros(1, 2, CV_32FC1); 84 m.at<float>(0, 0) = float(j) / cols; 85 m.at<float>(0, 1) = float(i) / rows; 86 87 float ret = 0.0; 88 ret = svm->predict(m); 89 Scalar rcolor; 90 91 switch ((int)ret) 92 { 93 case 1: rcolor = Scalar(100, 0, 0); break; 94 case 2: rcolor = Scalar(0, 100, 0); break; 95 case 3: rcolor = Scalar(0, 0, 100); break; 96 } 97 98 line(img, Point(j, i), Point(j, i), rcolor); 99 } 100 } 101 //-------獲得支持向量 102 int thickness = 2; 103 int lineType = 8; 104 //Mat sv = svm->getUncompressedSupportVectors();//不能使用，不知道什么原因，網上有的人可以使用 105 Mat sv = svm->getSupportVectors(); 106 for (int i = 0; i < sv.rows; ++i) 107 { 108 const float* v = sv.ptr<float>(i); 109 circle(img, Point((int)(v[0]*600), (int)(v[1]*400)), 4, Scalar(255, 255, 255), thickness, lineType); 110 } 111 112 imshow("dst", img); 113 waitKey(0); 114 } 115 116 int main(int argc,char** argv[]) 117 { 118 newSvmTest(400, 600, 500); 119 return 0; 120 }?
?
原圖
SVM預測
支持向量數據
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
參考： ?百度文庫（具體不標注了，都是公式和概念）
? ? ? ? ?《機器學習》周志華老師
https://wenku.baidu.com/view/8f48d70e581b6bd97f19eaaf.html（內積空間）
https://wenku.baidu.com/view/8bee6e76b0717fd5360cdced.html（歐式空間）
?http://open.163.com/movie/2013/3/T/0/M8PTB0GHI_M8PTBUHT0.html（網易公開課講函數空間，講的非常好！）
http://blog.csdn.net/shijing_0214/article/details/51052208（這篇博客是對上面視頻的總結，本來想自己總結的，感覺這篇博文總結的很好，所以自己偷懶不寫了）
http://blog.csdn.net/v_july_v/article/details/7624837（看了SMO感覺不錯）
http://blog.csdn.net/v_july_v/article/details/7624837（July不用說的大牛，寫的非常詳細，配合上面的資料就更容易理解）
http://www.pami.sjtu.edu.cn/people/gpliu/document/libsvm_src.pdf（代碼解釋，還沒看）
? http://blog.csdn.net/zhazhiqiang/article/details/20146243（很全的opencv實現SVM）
http://blog.csdn.net/firefight/article/details/6400060（程序核心是參考這篇文章，此博客opencv版本太低，很多不適合）
http://blog.csdn.net/changyuanchn/article/details/7540014（opencv SVM參數在這篇文章）
?
轉載于:https://www.cnblogs.com/wjy-lulu/p/6979436.html
總結
以上是生活随笔為你收集整理的支持向量机（理论+opencv实现）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： zTree实现单独选中根节点中第一个节点
- 下一篇： About Instruments