【正文】 he algorithm focuses its attention only on the current support vector set. It then picks data points greedily for inclusion in the current support vector set. While augmenting the current support vector set, some already existing support vectors may bee well classified because of the addition of a new support vector. We prune away those points using the decrem ental technique described in[7]. It may also happen that other points in the data set may bee violators or Support Vectors. The Incremental algorithm handles such points by doing costly book keeping in the current iteration itself and hence does not need to make repeated passes over the data set. On the other hand our algorithm does not handle such points in the current iteration, it makes repeated passes over the data set to identify and satisfy such points.4 CBGSVM Model and Algorithm Design In this part, first, introduce clustering feature and kmeans clustering, and then we develop the algorithm of clusteringbased Geometric SVM. Clustering feature S = { xi , i = 1, L, N} ,xi Rd , then define the subclass’s clustering feature as: (6) where
A clustering feature is a triple summarizing the information that we maintain about a cluster, embody pression of the class’s information. It doesn’t include all samples, instead the information of 0 order moment, 1order moment, and 2order moment. Meanwhile, define the center and radius of a subclass: (7) （8） Definition1(CF Additively Theorem) [8]: Given subclass， , , their clustering feature are ,the CF vector of S
that is formed by merging the two clusters, is: (9)From the CF definition and additively theorem, we know that the CF vectors of clusters can be stored and calculated incrementally and accurately as clusters are merged.附錄2 中文譯文基于聚類的幾何支持向量機(jī)摘要 在規(guī)模龐大的數(shù)據(jù)集訓(xùn)練支持向量機(jī)可能會(huì)出現(xiàn)慢訓(xùn)練的問題。在本文中，提出一個(gè)基于聚類的幾何支持向量機(jī)（CBGSVM）來解決這一問題，初始類由Kmeans聚類獲得 ，然后制定一個(gè)快速迭代算法確定所有子類的中心的支持向量機(jī)。為了加快收斂，我們初始化我們的算法與距離最近的類的中心，然后使用一個(gè)基于優(yōu)化的方法來增加或刪減候選支持向量集合。該算法反復(fù)越過中心，以滿足KKT約束。該方法加快了訓(xùn)練過程，與幾乎相同的分類精度支持向量機(jī)相比 ，標(biāo)準(zhǔn)的支持向量機(jī)比較快。 關(guān)鍵詞：支持向量機(jī)分類，感知器，最大間隔超平面，Kmeans聚類 1引言 在過去的十年里，支持向量機(jī)一直是解決分類和回歸問題強(qiáng)有力的工具。這種方法由統(tǒng)計(jì)學(xué)習(xí)理論產(chǎn)生的系統(tǒng)的理論 。它已成功地應(yīng)用于許多應(yīng)用范圍從粒子識(shí)別，面部識(shí)別和文本分類發(fā)動(dòng)機(jī)爆震檢測，生物信息學(xué)和數(shù)據(jù)庫營銷等發(fā)面。 有兩個(gè)問題：第一，SVM的訓(xùn)練很慢，特別是對(duì)大的問題。其次，SVM訓(xùn)練算法是復(fù)雜的，微妙的，有時(shí)甚至難以實(shí)施。為了克服這些問題，目前，有三個(gè)重要算法用于訓(xùn)練SVM：分解，SVMlight 和順序最小優(yōu)化（SMO）。 所述分解算法開始數(shù)據(jù)的任意子集。經(jīng)過一個(gè)通用的優(yōu)化被用于訓(xùn)練SVM的子集，支持向量保持在工作組，其余都是從訓(xùn)練集違反Karush 庫恩 塔克條件的數(shù)據(jù)替代。但是，這種算法還是比較慢，由于效率低下的選擇工作集。 Joachims進(jìn)一步發(fā)展SVMlight分解算法SVM。他從Zoutendijk的方法策略基礎(chǔ)上，在陡可行方向的非零元素選擇一個(gè)良好的工作組。收縮戰(zhàn)略，最近最少使用（LRU）的緩存策略也被用于加快培訓(xùn)。但SVMlight其中一個(gè)的低效率原因來自于其高速緩存策略。它緩存某些行的總核Hessian矩陣，這樣它會(huì)占用大量的內(nèi)存，成為棘手的大規(guī)模學(xué)習(xí)問題。此外，熱收縮策略的失敗將導(dǎo)致在支持向量機(jī)學(xué)習(xí)問題的重新優(yōu)化。 普拉特[5]提出序貫最小優(yōu)化，這使得支持向量機(jī)訓(xùn)練得到了巨大的進(jìn)步。他選擇工作設(shè)定為兩者的大小，并給出一個(gè)明確的解析解的二變量優(yōu)化問題，而無需使用任何優(yōu)化包。幾個(gè)啟發(fā)性的建議來選擇工作集。 Keerthi等人[19]進(jìn)一步增強(qiáng)的SMO通過指出在普氏算法更新一個(gè)閾值參數(shù)，并與兩個(gè)閾參數(shù)替換它的低效率的性能。此外，值得注意的是，Keerthi和吉爾伯特證明停機(jī)狀態(tài)下的有限步驟終止很重要。 聚類[13]在很多應(yīng)用方面是一個(gè)重要的應(yīng)用領(lǐng)域，包括數(shù)據(jù)挖掘[14]，壓縮[15]，矢量量化，和其他業(yè)務(wù)應(yīng)用等 [16]。最根本的聚類問題是，（集群）類似的數(shù)據(jù)項(xiàng)[17]組合在一起的。最一般的方法是，以查看聚類作為一個(gè)密度估計(jì)問題。的K均值算法找到一個(gè)局部最佳解決方案，以最大限度地減少每一個(gè)數(shù)據(jù)點(diǎn)和其最近的聚類中心（“失真”）之間的L 2距離的總和的問題[18]，這相當(dāng)于列出一個(gè)最大化給定假設(shè)的可能性。 在本文中，快速迭代算法，是基于聚類的增量式算法的理論基礎(chǔ)提出。我們借用直接SVM的初始化技術(shù)[6]算法來加快我們的算法收斂。第2節(jié)談到標(biāo)準(zhǔn)的支持向量機(jī)分類。第3節(jié)談到幾何SVM。第4節(jié)談到了CBGSVM模型和算法設(shè)計(jì)。部分5呈現(xiàn)施加GBSVM算法三個(gè)數(shù)據(jù)集的結(jié)果。第6節(jié)是結(jié)論。2支持向量機(jī)的分類 在支持向量類別[1]，該分離功能可以表示為與支持向量作為相關(guān)聯(lián)的內(nèi)核的線性組合： （1）其中xi表示訓(xùn)練樣本，表示相應(yīng)的類標(biāo)簽，S表示支持向量的集合 。雙線性公式 （2）其中，是相應(yīng)的系數(shù)，為偏移量， 是對(duì)稱正定核矩陣，C是 參數(shù)用來在不可分割的情況下，懲罰錯(cuò)誤點(diǎn)。對(duì)于雙線性 Karush庫恩 塔克（KKT）條件可以表示為： （3）和 （4） 這種分割訓(xùn)練集分為S個(gè)支持向量集 如果在誤差的點(diǎn)二次曲線用懲罰因子，已經(jīng)證明，該問題簡化為一個(gè)可分離的情況下，該核函數(shù)修改為 （5）其中 if 和 否則，此公式優(yōu)點(diǎn)是，SVM問題簡化為一個(gè)線性可分的情況。 它可以看出，訓(xùn)練的SVM涉及解決這需要使用優(yōu)化例程從數(shù)值庫二次優(yōu)化問題。這一步是計(jì)算密集的，能受到穩(wěn)定性問題的影響而且不容易實(shí)現(xiàn)。3支持向量機(jī)的幾何算法 幾何算法[11]提高直接支持向量機(jī)的縮放行為[6]。D irect SVM是一種簡單快速的迭代 算法，它建立逐步建立支持向量。最近，已經(jīng)證明，算法將線性可分的兩類樣本中距離最近的兩個(gè)異類樣本點(diǎn)作為支持向量。Direct SVM建立候選支持向量組。據(jù)推測，在每個(gè)迭代中，通過的最大誤差的是一個(gè)支持向量。該算法發(fā)現(xiàn)最大違規(guī)者在每次迭代中并且通過旋轉(zhuǎn)候選人的支持面，使最大違規(guī)者為支持向量。假如空間的維數(shù)被超過或所有數(shù)據(jù)點(diǎn)都用完了，依然沒有收斂，算法將從相對(duì)的類重新初始化與下一個(gè)最接近的點(diǎn)對(duì)。直接SVM算法的優(yōu)點(diǎn)在于，它以幾何為基礎(chǔ)，簡單易懂。 利用幾何優(yōu)化為基礎(chǔ)的SVM方法，以點(diǎn)添加到候選人的支持向量集。該算法采用貪心算法，它采用下一個(gè)立即可用違反點(diǎn)列入候選支持向量集合。 這樣的的算法沒有 有規(guī)定原路返回，即一旦他們決定以包括候選人的支持向量集合點(diǎn)，他們不能放棄它。在每一步驟中，兩個(gè)算法花費(fèi)最大努力在尋找最大違反上 。如果S是 當(dāng)前候選支持向量集合，N是數(shù)據(jù)集的大小，該算法花（N S）s內(nèi)核評(píng)估，以找出最大違反者。緩存方案被提出，以增加該步驟的效率。貪婪算法挑選下一個(gè)立即可用的原因， 違反點(diǎn)列入候選支持向量集合。因?yàn)檫@種貪婪方法，一些雜散的非支持向量可以拿起，列入候選集。該算法通過從候選人的支持向量集剪枝等距離雜散點(diǎn)后回溯。為了滿足KKT條件為它必須使重復(fù)所有點(diǎn)傳遞通過數(shù)據(jù)集 。最近一些工作也已完成增量SVM算法，可以收斂到精確的解決方案，也有效地計(jì)算留一錯(cuò)誤[7]。該算法通過將一個(gè)點(diǎn)在第一時(shí)間加到當(dāng)前數(shù)據(jù)集。它表明，增加了一個(gè)點(diǎn)的會(huì)聚的步驟的數(shù)量有限。該算法計(jì)算以便做記錄在當(dāng)前數(shù)據(jù)點(diǎn)的每一個(gè)的KKT條件的變化。當(dāng)前的數(shù)據(jù)集的大小是N和支持的數(shù)目載體是S，那么，該算法為執(zhí)行內(nèi)核NS操作除此外之的下一個(gè)點(diǎn)。這組作者提出一個(gè)實(shí)用的在線變型，他們引入δ余量，集中只有那些點(diǎn)的范圍內(nèi)緣δ邊界。但是，很明顯，這些結(jié)果可以通過改變?chǔ)牡闹刀兓?。代替集中整個(gè)當(dāng)前數(shù)據(jù)集上的，這可能是代價(jià)高昂，在算法只集中關(guān)注當(dāng)前的支持向量確立。然后它選擇的數(shù)據(jù)點(diǎn)為貪婪列入當(dāng)前支持向量集。同時(shí)充實(shí)目前的支持向量集，一些已經(jīng)存在的支持向量可能是因?yàn)樵黾恿艘粋€(gè)新的支持向量的變得很好歸類。我們修剪距離使用[7]中描述的遞減技術(shù)的那些點(diǎn)。它也可能發(fā)生在數(shù)據(jù)集中的其他點(diǎn)可能成為違規(guī)者或支持向量。在當(dāng)前迭代同時(shí)處理這些點(diǎn)，本身增量算法做代價(jià)高昂記錄，因此不需要在數(shù)據(jù)集進(jìn)行反復(fù)通行證。另一方面我們的算法并不在當(dāng)前迭代中處理這樣的點(diǎn)，它使重復(fù)越過數(shù)據(jù)集，以確定并滿足這樣的點(diǎn)。4 CBGSVM模型與算法設(shè)計(jì) 在這一部分，首先介紹了聚類特征和K均值聚類，然后我們開發(fā)了基于聚類的SVM幾何算法。 訓(xùn)練樣本的子集 ， ，然后定義之類的集群功能為 (6)此時(shí) 聚類特征是一個(gè)三重總結(jié)，我們維持對(duì)集群，體現(xiàn)的類的信息壓縮的信息。它不包括所有的樣品中，而非0次矩信息，1階矩，以及2階，同時(shí)確定一個(gè)子類中心和半徑 ： (7) （8）定義1（CF相加定理）[8]：給定的子類， , ,其聚類特征是 ,S的CF矢量是通過合并兩個(gè)聚類形成的，是： (9)從CF定義和相加定理，我們知道，聚類的CF載體可被存儲(chǔ)和計(jì)算增量準(zhǔn)確地作為群集合并。 附錄3 代碼利用SVM解決二維空間向量的分類問題include opencv2/core/include opencv2/highgui/include opencv2/ml/using namespace cv。int main(){ // Data for visual representation int width = 512, height = 512。 Mat image = Mat::zeros(height, width, CV_8UC3)。 // Set up training data float labels[4] = {, , , }。 Mat labelsMat(3, 1, CV_32FC1, labels)。 float trainingData[4][2] = { {501, 10}, {255, 10}, {501, 255}, {10, 501} }。Mat trainingDataMat(3, 2, CV_32FC1, trainingData)。 // Set up SVM39。s parameters CvSVMParams params。 = CvSVM::C_SVC。 = CvSVM::LINEAR。 = cvTermCriteria(CV_TERMCRIT_ITER, 100, 1e6)。 // Train the SVM CvSVM SVM。 (trainingDataMat, labelsMat, Ma