svdd演算法

『壹』 有人知道怎麼把SVDD工具箱裝到libsvm嗎

1 先下載 libsvm-svdd-3.18.zip和 libsvm-3.18.zip，並解壓得到文件夾 libsvm-svdd-3.18和libsvm-3.18；
2 將文件夾 libsvm-svdd-3.18根目錄下的svm.cpp、svm.h和svm-train.c復制到 libsvm-3.18根目錄下並覆蓋原來的這3個文件；將文件夾 libsvm-svdd-3.18中 matlab里的文件 svmtrain.c 復制到 libsvm-3.18中的matlab文件夾中覆蓋原來的c文件；
3 安裝 libsvm-3.18，這個教程網上一大堆，主要是兩步：mex -setup和 make；
4 測試安裝是否成功。

『貳』 異常檢測方法 二

  離群點是一個數據對象，它顯著不同於其他數據對象，好像它是被不同的機制產生的一樣。有時也稱非離群點為「正常數據」，離群點為「異常數據」。
  離群點不同於雜訊數據。雜訊是被觀測變數的隨機誤差或方差。一般而言，雜訊在數據分析（包括離群點分析）中不是令人感興趣的。如在信用卡欺詐檢測，顧客的購買行為可以用一個隨機變數建模。一位顧客可能會產生某些看上去像「隨機誤差」或「方差」的雜訊交易，如買一份較豐盛的午餐，或比通常多要了一杯咖啡。這種交易不應該視為離群點，否則信用卡公司將因驗證太多的交易而付出沉重代價。因此，與許多其他數據分析和數據挖掘任務一樣，應該在離群點檢測前就刪除雜訊。
  離群點檢測是有趣的，因為懷疑產生它們的機制不同於產生其他數據的機制。因此，在離群點檢測時，重要的是搞清楚為什麼檢測到的離群點被某種其他機制產生。通常，在其餘數據上做各種假設，並且證明檢測到的離群點顯著違反了這些假設。

離群點可以分成三類：全局離群點、情境（或條件）離群點和集體離群點。

在給定的數據集中，一個數據對象是全局離群點，如果它顯著的偏離數據集中的其他對象。全局離群點是最簡單的一類離群點，大部分的離群點檢測方法都旨在找出全局離群點。

在給定的數據集中，一個數據對象是情境離群點，如果關於對象的特定情境，它顯著的偏離其他對象。情境離群點又稱為條件離群點，因為它們條件的依賴於選定的情境。一般地，在情境離群點檢測中，所考慮數據對象的屬性劃分成兩組：
情境屬性 ：數據對象的情境屬性定義對象的情境。一般為靜態屬性變數，如信用卡欺詐檢測中，不同年齡、不同地區的人消費情況是不同的，先按照靜態屬性將人群大致分類，再檢測每一類的離群點，會得到更好的結果。
行為屬性 ：定義對象的特徵，並用來評估對象關於它所處的情境是否為離群點。在上述例子中，行為屬性可以是消費金額，消費頻率等
情境離群點分析為用戶提供了靈活性，因為用戶可以在不同情境下考察離群點，這在許多應用中都是非常期望的。

給定一個數據集，數據對象的一個子集形成集體離群點，如果這些對象作為整體顯著的偏離整個數據集。如一家供應鏈公司，每天處理數以千計的訂單和出貨。如果一個訂單的出貨延誤，則可能不是離群點，因為統計表明延誤時常發生。然而，如果有一天有100個訂單延誤，則必須注意。這100個訂單整體來看，形成一個離群點，盡管如果單個考慮，它們每個或許都不是離群點。你可能需要更詳細地整個考察這些訂單，搞清楚出貨問題。
與全局和情境離群點檢測不同，在集體離群點檢測中，不僅必須考慮個體對象的行為，而且還要考慮對象組群的行為。因此，為了檢測集體離群點，需要關於對象之間聯系的背景知識，如對象之間的距離或相似性測量方法。

離群點檢測的統計學方法對數據的正常性做假定。假定數據集中的正常對象由一個隨機過程（生成模型）產生。因此，正常對象出現在該隨機模型的高概率區域中，而低概率區域中的對象是離群點。
離群點檢測的統計學方法的一般思想是：學習一個擬合給定數據集的生成模型，然後識別該模型低概率區域中的對象，把它們作為離群點。有許多不同方法來學習生成模型，一般而言，根據如何指定和如何學習模型，離群點檢測的統計學方法可以劃分成兩個主要類型： 參數方法和非參數方法。
參數方法: 假定正常的數據對象被一個以為參數的參數分布產生。該參數分布的概率密度函數給出對象被該分布產生的概率。該值越小，越可能是離群點。
非參數方法: 並不假定先驗統計模型，而是試圖從輸入數據確定模型。非參數方法的例子包括直方圖和核密度估計。

  假定數據集由一個正態分布產生，然後，可以由輸入數據學習正態分布的參數，並把低概率的點識別為離群點。
  在正態分布的假定下，區域包含99.7%的數據，包含95.4%的數據，包含68.3%的數據。視具體情況而定，將其區域外的數據視為離群點。
  這種直截了當的統計學離群點檢測方法也可以用於可視化。例如盒圖方法使用五數概況繪制一元輸入數據：最小的非離群點值（Min）、第一個四分位數（Q1）、中位數（Q2）、第三個四分位數（Q3）和最大的非離群點值（Max）。
  四分位數極差（IQR）定義為Q3-Q1。比Q1小1.5倍的IQR或者比Q3大1.5倍的IQR的任何對象都視為離群點，因為Q1-1.5 IQR和Q3+1.5 IQR之間的區域包含了99.3%的對象。

（1）使用馬哈拉諾比斯距離檢測多元離群點。
對於一個多元數據集，設為均值向量。對於數據集中的對象，從到的馬哈拉諾比斯（Mahalanobis）距離為其中S是協方差矩陣。是一元數據，可以對它進行離群點檢測。如果被確定為離群點，則也被視為離群點。
（2）使用統計量的多元離群點檢測。
在正態分布的假設下，統計量可以用來捕獲多元離群點。對於對象，統計量是
其中，是在第維上的值，是所有對象在第維上的均值，而是維度。如果對象的統計量很大，則該對象是離群點。
（3）使用混合參數分布
在許多情況下，數據是由正態分布產生的假定很有效。然而，當實際數據很復雜時，這種假定過於簡單。在這種情況下，假定數據是被混合參數分布產生的。
混合參數分布中用期望最大化（EM）演算法來估計參數。具體情況比較復雜，可以參考韓家煒的《數據挖掘：概念與技術》一書。

在離群點檢測的非參數方法中，「正常數據」的模型從輸入數據學習，而不是假定一個先驗。通常，非參數方法對數據做較少假定，因而在更多情況下都可以使用。

使用直方圖檢測離群點
包括如下兩步：
步驟1： 構造直方圖。盡管非參數方法並不假定任何先驗統計模型，但是通常確實要求用戶提供參數，以便由數據學習。如指定直方圖的類型（等寬或等深的）和其他參數（如直方圖中的箱數或每個箱的大小）。與參數方法不同，這些參數並不指定數據分布的類型（如高斯分布）。
步驟2： 檢測離群點。為了確定一個對象是否是離群點，可以對照直方圖檢驗它。在最簡單的方法中，如果該對象落入直方圖的一個箱中，則該對象被看做是正常的，否則被認為是離群點。

對於更復雜的方法，可以使用直方圖賦予每個對象一個離群點得分。一般可以令對象的離群點得分為該對象落入的箱的容積的倒數。得分越高，表明是離群點的概率越大。

使用直方圖作為離群點檢測的非參數模型的一個缺點是，很難選擇一個合適的箱尺寸。一方面，如箱尺寸太小，則由很多正常對象都會落入空的或稀疏箱，因而被誤識別為離群點。這將導致很高的假正例率或低精度。相反，如果箱尺寸太大，則離群點對象可能滲入某些頻繁的箱中，這將導致很高的假負例率或召回率。為了解決這些問題，使用核密度估計來估計數據的概率密度分布。具體參考韓家煒的《數據挖掘：概念與技術》。

  給定特徵空間中的對象集，可以使用距離度量來量化對象間的相似性。基於鄰近性的方法假定：離群點對象與它最近鄰的鄰近性顯著偏離數據集中其他對象與它們近鄰之間的鄰近性。
  有兩種類型的基於鄰近性的離群點檢測方法：基於距離的和基於密度的方法。基於距離的離群點檢測方法考慮對象給定半徑的鄰域。一個對象被認為是離群點，如果它的鄰域內沒有足夠多的其他點。基於密度的離群點檢測方法考察對象和它近鄰的密度。這里，一個對象被識別為離群點，如果它的密度相對於它的近鄰低得多。

對於待分析的數據對象集D，用戶可以指定一個距離閾值r來定義對象的合理鄰域。對於每個對象o，可以考察o的r-鄰域中的其他對象的個數。如果D中大多數對象都遠離o，即都不在o的r-鄰域中，則o可以被視為一個離群點。
令是距離閾值，是分數閾值。對象是一個離群點，如果
其中是距離度量。
如何計算-離群點？一是嵌套循環方法，時間復雜度為。當數據集很大時，該方法的開銷很大。為了改進性能，可以用基於網格的方法來實現。具體見韓家煒《數據挖掘》一書。

基於距離的離群點檢測從全局考慮數據集。由於以下兩個原因，這種離群點被看成「全局離群點」：
l 例如，一個-離群點至少遠離（用參數r定量）數據集中的對象。換言之，這種離群點遠離數據的大多數。
l 為了檢測基於距離的離群點，需要兩個距離參數，它們用於每個離群點對象。
現實世界的許多數據集都呈現更復雜的結構，那裡對象可能關於其局部鄰域，而不是關於整個數據分布而被視為離群點。如下圖，基於距離的離群點檢測方法不能捕獲像o1和o2這樣的局部離群點。
那麼，如何確切地定義如圖所示的局部離群點？這里關鍵的思想是，需要把對象周圍的密度與對象鄰域周圍的密度進行比較。基於密度的離群點檢測方法的基本假定是：非離群點對象周圍的密度與其鄰域周圍的密度類似，而離群點對象周圍的密度顯著不同於其鄰域周圍的密度。

基於聚類的方法通過考察對象與簇之間的關系檢測離群點。直觀地，離群點是一個對象，它屬於小的偏遠簇，或不屬於任何簇。
這導致三種基於聚類的離群點檢測的一般方法。考慮一個對象。
l 該對象屬於某個簇嗎？如果不，則它被識別為離群點。
l 該對象與最近的簇之間的距離很遠嗎？如果是，則它是離群點。
l 該對象是小簇或稀疏簇的一部分嗎?如果是，則該簇中的所有對象都是離群點。

下面對每一種方法考察一個例子。

例1 把離群點檢測為不屬於任何簇的對象。如圖1所示，使用基於密度的聚類方法，如DBSCAN,注意到黑色點都屬於簇，白色點a不屬於任何簇，因而被認為是離群點。

圖1 對象a是離群點，因為 它不屬於任何簇

圖2 離群點（a,b,c）都（關於簇中心）遠離距它們最近的簇

例2 使用到最近簇的距離的基於聚類的離群點檢測。如圖2所示，使用k-均值聚類方法，可以把圖2中的數據點劃分成3個簇，如圖中不同符號所示，每個簇中心用「+」標記。對於每個對象o，都可以根據該對象與最近簇中心的距離，賦予該對象一個離群點得分。假設到o的最近中心為c,則o與c之間的距離為dist(o,c)，c與指派到c的對象之間的平均距離為L,比率度量與平均值的差異程度。在圖2中，點a,b和c都相對遠離它們的對應中心，因而被懷疑是離群點。

例3 檢測小簇中的離群點

迄今為止我們看到的每種方法都只檢測個體離群點，因為它們一次把一個對象與數據集中的簇進行比較。然而，在大型數據中，一些離群點可能是類似的，並且形成一個小簇。例如，在入侵檢測中，使用相同手段攻擊系統的黑客可能形成一個簇。迄今為止所討論的方法可能被這種離群點所欺騙。
為了解決這一問題，第三種基於聚類的離群點檢測方法識別小簇或稀疏簇，並宣告這些簇中的對象也是離群點。這種方法的一個例子是FindCBLOF演算法，其方法如下。

（1） 找出數據集中的簇，並把它們按大小降序排列。該演算法假定大部分數據點都不是離群點，它使用一個參數來區別大簇和小簇。任何至少包含數據集中百分之（如，=90%）數據點的簇都被視為大簇，而其餘的簇被看成小簇。
（2） 對於每個數據點賦予基於簇的局部離群點因子（CBLOF），對於屬於大簇的點，它的CBLOF是簇的大小和該點與簇的相似性的乘積。對於屬於小簇的點，它的CBLOF用小簇的大小和該點與最近的大簇的相似性的乘積計算。
CBLOF用統計學方法定義點和簇之間的相似性，代表點屬於簇的概率。該值越大，點與簇越相似。CBLOF值可以檢測遠離任何簇的離群點。
基於聚類的離群點檢測方法具有如下優點。首先，它們可以檢測離群點，而不要求數據是有標號的，即它們以無監督方式檢測。它們對許多類型的數據都有效。簇可以看成是數據的概括，一旦得到簇，基於聚類的方法只需要把對象與簇進行比較，以確定該對象是否是離群點，這一過程通常很快，因為與對象總數相比，簇的個數通常很小。
基於聚類的方法的缺點是：它的有效性高度依賴於所使用的聚類方法。這些方法對於離群點檢測而言可能不是最優的。對於大型數據集，聚類方法通常開銷很大，這可能成為一個瓶頸。

如果訓練數據具有類標號，則離群點檢測可以看做分類問題。基於分類的離群點檢測方法的一般思想是，訓練一個可以區分「正常」數據和離群點的分類模型。
基於分類的離群點檢測方法通常使用一類模型（單分類模型SVDD），即構造一個僅描述正常類的分類器，不屬於正常類的任何樣本都被視為離群點。
基於分類的方法和基於聚類的方法可以聯合使用，以半監督的方式檢測離群點。
例通過半監督學習檢測離群點

如上圖所示，其中對象被標記為「正常」或「離群點」，或者沒有標號。使用基於聚類的方法，發現一個大簇C和一個小簇C1。因為C中的某些對象攜帶了標號「正常」，因此可以把該簇的所有對象（包括沒有標號的對象）都看做正常對象。在離群點檢測中，使用這個簇的一類模型來識別離群點。類似的，因為簇C1中的某些對象攜帶標號「離群點」，因此宣布C1中的所有對象都是離群點。未落入C模型中的任何對象（如a）也被視為離群點。

與一般的離群點檢測相比，識別情境離群點需要分析對應的情境信息。情境離群點檢測方法可以根據情境是否可以清楚地識別而分成兩類。

這類方法適用於情境可以被清楚識別的情況，其基本思想是把情境離群點檢測問題轉換成典型的離群點檢測問題。具體地說，對於給定的數據對象，用兩步來評估該對象是否是離群點。第一步，使用對象的情境屬性識別對象的情境。第二步，使用一種傳統的離群點檢測方法，估計該對象的離群點得分。

在某些應用中，清楚地把數據劃分成情境是不方便的或不可行的。這時，可以關於情境對正常行為建模。使用一個訓練數據集，這種方法訓練一個模型，關於情境屬性的值，預測期望的行為屬性值。然後，為了確定一個數據對象是否是情境離群點，可以在該對象的情境屬性上使用該模型。如果該對象的行為屬性值顯著地偏離該模型的預測值，則該對象被宣布為情境離群點。
通過使用連接情境和行為的預測模型，這些方法避免直接識別具體情境。許多分類和預測技術都可以用來構建這種模型，如回歸、馬爾科夫模型和有窮狀態自動機等等。

與情境離群點檢測一樣，集體離群點檢測方法也可以劃分為兩類。第一類方法把問題歸結為傳統的離群點檢測。其策略是識別結構單元，把每個結構單元（例如，子序列、時間序列片段、局部區域或子圖）看做是一個數據對象，並提取特徵。這樣，集體離群點檢測問題就轉換成在使用提取的特徵構造的「結構化對象」集上的離群點檢測。一個結構單元代表原數據集中的一組對象，如果該結構單元顯著地偏離提取的特徵空間中的期望趨勢，則它是一個集體離群點。
為集體離群點檢測預先定義結構單元可能是困難的，或者是不可能的。因此，第二類方法直接對結構單元的期望行為建模。例如，為了在時間序列中檢測離群點，一種方法是從序列中學習馬爾科夫模型。因此，一個子序列被宣布為集體離群點，如果它顯著地偏離該模型。

一般地，高維數據的離群點檢測方法應該應對以下挑戰：

l 離群點的解釋：不僅應該能夠識別檢測離群點，而且能夠提供離群點的解釋。離群點的解釋可能是，例如，揭示離群點的特定子空間，或者關於對象的「離群點性」的評估。這種解釋可以幫助用戶理解離群點的含義和意義。
l 數據的稀疏性：這些方法應該能處理高維空間的稀疏性。隨著維度的增加，對象之間的距離嚴重地被雜訊所左右。因此，高維空間中的數據通常是稀疏的。
l 數據子空間：它們應該以合適的方式對離群點建模，例如，自適應現實離群點的子空間和捕獲數據的局部變化。在所有的子空間上使用固定的距離閾值來檢測離群點捕食一種好想法，因為兩個對象之間的距離隨著維度增加而單調增加。
l 關於維度的可伸縮性：隨著維度的增加，子空間的數量指數增加。包含所有可能的子空間的窮舉組合探索不是可伸縮的選擇。
高維數據的離群點檢測方法可以劃分成三種主要方法，包括擴充的傳統離群點檢測、發現子空間中的離群點和對高維離群點建模。

一種高維數據離群點檢測方法是擴充的傳統離群點檢測方法。它使用傳統的基於鄰近性的離群點模型。然而，為了克服高維空間中鄰近性度量惡化問題，它使用其他度量，或構造子空間並在其中檢測離群點。

HilOut演算法就是這種方法的一個例子。HitOut找出基於距離的離群點，但在離群點檢測中使用距離的秩，而不是絕對距離。具體地說，對於每個對象o，HitOut找出o的k個最近鄰，記作nn1(o),nn2(o)……nnk(o),其中k是一個依賴於應用的參數。參數o的權重定義為

所有對象按權重遞減序定秩。權重最高的top-p個對象作為離群點輸出，其中p是另一個用戶指定的參數。

HilOut演算法計算每個對象的k-最近鄰開銷很大，當維度很高並且數據很大時不能伸縮。
另一種方法則是通過維歸約，把高維離群點檢測問題歸結為較低維上的離群點檢測。其基本思想是，把高維空間歸約到低維空間，那裡標準的距離度量仍然能夠區分離群點。如果能夠找到這樣的較低維空間，則可以用傳統的離群點檢測方法。
為了降低維度，可以對離群點檢測使用或擴充一般的特徵特徵選擇和提取方法。例如，可以用主成分分析（PCA）來提取一個低維空間。

高維數據中離群點檢測的另一種方法是搜索各種子空間中的離群點。其唯一的優點是，如果發現一個對象是很低維度的子空間的離群點，則該子空間提供了重要信息，解釋該對象為什麼和在何種程度上是離群點。
如何檢測子空間中的離群點，一種方法是基於網格的子空間離群點檢測。具體做法見韓家煒《數據挖掘》。

另一種方法是試圖直接為高維離群點建立一個新模型。這種方法通常避免鄰近性度量，而是採用新的啟發式方法來檢測離群點。具體做法見韓家煒《數據挖掘》。

『叄』 sklearn之OneClassSVM

（1）無監督異常值檢測

（2）解決非平衡樣本分類

class  sklearn.svm.OneClassSVM( kernel=』rbf』 ,  degree=3 ,  gamma=』auto』 ,  coef0=0.0 ,  tol=0.001 ,  nu=0.5 ,  shrinking=True ,  cache_size=200 ,  verbose=False ,  max_iter=-1 ,  random_state=None )

kernel：

    典型的2類問題：識別郵件是否是垃圾郵件，一類「是」，另一類「不是」

    典型的多類問題：人臉識別，每個人對應的臉就是一個類，然後把待識別的臉分到對應的類中去

    而OneClassClassification，它只有一個類，屬於該類就返回結果「是」，不屬於就返回結果「不是」，乍一聽感覺與2分類沒什麼區別，其實他們的思想有很大差異。在2分類問題中，訓練集中就由兩個類的樣本組成，訓練出的模型是一個2分類模型；而OneClassClassification中的訓練樣本只有一類，因此訓練出的分類器將不屬於該類的所有其他樣本判別為「不是」即可，而不是由於屬於另一類才返回的「不是」結果。

    現實場景中的OneClassClassification例子：現在有一堆某商品的歷史銷售數據，記錄著買該產品的用戶信息，此外還有一些沒有購買過該產品的用戶信息，想通過2分類來預測他們是否會買該產品，也就是弄兩個類，一類是「買」，一類是「不買」。當我們要開始訓練2分類器的時候問題來了，一般來說沒買的用戶數會遠遠大於已經買了的用戶數，當將數量不均衡的正負樣本投入訓練時，訓練出的分類器會有較大的bias（偏向值）。因此，這時可以使用OneCLassClassification方法來解決，即訓練集中只有已經買過該產品的用戶數據，在識別一個新用戶是否會買該產品時，識別結果就是「會」或者「不會」。

多類Classification方法有很多，比如SVM尋找一個最優超平面把正負樣本分開，總之都涉及到不止一個類的樣本，相當於告訴演算法「這種東西長什麼樣，那種東西長什麼樣」。於是訓練出一個模型能夠區分這些東西。

問題在於，OneCLassClassification只有一個類，該怎麼辦？

介紹一個方法：SVDD（support vector domain description），中文翻譯為「支持向量域描述」

其基本思想是：既然只有一個class，那麼我就訓練出一個最小的超球面（超球面是指3維以上的空間中的球面，對應的2維空間中就是曲線，3維空間中就是球面），將這堆數據全部「包起來」，識別一個新的數據點時，如果這個數據點落在超球面內，就屬於這個類，否則不是。

下面是在2維空間（實際情況中，如果提取的特徵多，維數就高）中的例子，

更多原理公式推導，詳見 http://blog.sina.com.cn/s/blog_4ff49c7e0102vlbv.html

『肆』 怎麼在libsvm安裝包基礎上進行特徵加權

一 安裝
1. 下載
在LIBSVM的主頁上下載最新版本的軟體包，並解壓到合適目錄中。

2. 編譯
如果你使用的是64位的操作的系統和Matlab，那麼不需要進行編譯步驟，因為自帶軟體包中已經包含有64位編譯好的版本：libsvmread.mexw64、libsvmwrite.mexw64、svmtrain.mexw64、svmpredict.mexw64。否則，需要自己編譯二進制文件。

首先在Mtlab中進入LIBSVM根目錄下的matlab目錄（如C:\libsvm-3.17\matlab），在命令窗口輸入

>>mex –setup

然後Matlab會提示你選擇編譯mex文件的C/C++編譯器，就選擇一個已安裝的編譯器，如Microsoft Visual C++ 2010。之後Matlab會提示確認選擇的編譯器，輸入y進行確認。

然後可以輸入以下命令進行編譯。

>>make

注意，Matlab或VC版本過低可能會導致編譯失敗，建議使用最新的版本。

編譯成功後，當前目錄下會出現若干個後綴為mexw64（64位系統）或mexw32（32位系統）的文件。

3. 重命名（可選，但建議執行）
編譯完成後，在當前目錄下回出現svmtrain.mexw64、svmpredict.mexw64（64位系統）或者svmtrain.mexw32、svmpredict.mexw32（32位系統）這兩個文件，把文件名svmtrain和svmpredict相應改成libsvmtrain和libsvmpredict。

這是因為Matlab中自帶有SVM的工具箱，而且其函數名字就是svmtrain和svmpredict，和LIBSVM默認的名字一樣，在實際使用的時候有時會產生一定的問題，比如想調用LIBSVM的變成了調用Matlab SVM。

如果有進行重命名的，以後使用LIBSVM時一律使用libsvmtrain和libsvmpredict這兩個名字進行調用。

4. 添加路徑
為了以後使用的方便，建議把LIBSVM的編譯好的文件所在路徑（如C:\libsvm-3.17\matlab）添加到Matlab的搜索路徑中。具體操作為：（中文版Matlab對應進行）

HOME -> Set Path -> Add Folder -> 加入編譯好的文件所在的路徑（如C:\libsvm-3.17\matlab）

當然也可以把那4個編譯好的文件復制到想要的地方，然後再把該路徑添加到Matlab的搜索路徑中。

二 測試
LIBSVM軟體包中自帶有測試數據，為軟體包根目錄下的heart_scale文件，可以用來測試LIBSVM是否安裝成功。這里的heart_scale文件不能用Matlab的load進行讀取，需要使用libsvmread讀取。

進入LIBSVM的根目錄運行以下代碼（因為heart_scale文件沒有被添加進搜索路徑中，其他路徑下無法訪問這個文件）：

[heart_scale_label, heart_scale_inst] = libsvmread('heart_scale');
model = libsvmtrain(heart_scale_label, heart_scale_inst, '-c 1 -g 0.07');
[predict_label, accuracy, dec_values] = libsvmpredict(heart_scale_label, heart_scale_inst, model);
如果LIBSVM安裝正確的話，會出現以下的運行結果，顯示正確率為86.6667%。

*
optimization finished, #iter = 134
nu = 0.433785
obj = -101.855060, rho = 0.426412
nSV = 130, nBSV = 107
Total nSV = 130
Accuracy = 86.6667% (234/270) (classification)
三 原理簡介
使用SVM前首先得了解SVM的工作原理，簡單介紹如下。

SVM(Support Vector Machine，支持向量機）是一種有監督的機器學習方法，可以學習不同類別的已知樣本的特點，進而對未知的樣本進行預測。

SVM本質上是一個二分類的演算法，對於n維空間的輸入樣本，它尋找一個最優的分類超平面，使得兩類樣本在這個超平面下可以獲得最好的分類效果。這個最優可以用兩類樣本中與這個超平面距離最近的點的距離來衡量，稱為邊緣距離，邊緣距離越大，兩類樣本分得越開，SVM就是尋找最大邊緣距離的超平面，這個可以通過求解一個以超平面參數為求解變數的優化問題獲得解決。給定適當的約束條件，這是一個二次優化問題，可以通過用KKT條件求解對偶問題等方法進行求解。

對於不是線性可分的問題，就不能通過尋找最優分類超平面進行分類，SVM這時通過把n維空間的樣本映射到更高維的空間中，使得在高維的空間上樣本是線性可分的。在實際的演算法中，SVM不需要真正地進行樣本點的映射，因為演算法中涉及到的高維空間的計算總是以內積的形式出現，而高維空間的內積可以通過在原本n維空間中求內積然後再進行一個變換得到，這里計算兩個向量在隱式地映射到高維空間的內積的函數就叫做核函數。SVM根據問題性質和數據規模的不同可以選擇不同的核函數。

雖然SVM本質上是二分類的分類器，但是可以擴展成多分類的分類器，常見的方法有一對多（one-versus-rest）和一對一（one-versus-one）。在一對多方法中，訓練時依次把k類樣本中的某個類別歸為一類，其它剩下的歸為另一類，使用二分類的SVM訓練處一個二分類器，最後把得到的k個二分類器組成k分類器。對未知樣本分類時，分別用這k個二分類器進行分類，將分類結果中出現最多的那個類別作為最終的分類結果。而一對一方法中，訓練時對於任意兩類樣本都會訓練一個二分類器，最終得到k*(k-1)/2個二分類器，共同組成k分類器。對未知樣本分類時，使用所有的k*(k-1)/2個分類器進行分類，將出現最多的那個類別作為該樣本最終的分類結果。

LIBSVM中的多分類就是根據一對一的方法實現的。

四 使用
關於LIBSVM在Matlab中的使用，可以參看軟體包中matlab目錄下的README文件，這里對裡面內容做一個翻譯和一些細節的講解。

1. 訓練
libsvm函數用於對訓練集的數據進行訓練，得到訓練好的模型。

model = libsvmtrain(training_label_vector, training_instance_matrix [, 'libsvm_options']);

這個函數有三個參數，其中

-training_label_vector:訓練樣本的類標，如果有m個樣本，就是m x 1的矩陣（類型必須為double）。這里可以是二分類和多分類，類標是（-1,1）、（1,2,3）或者其他任意用來表示不同的類別的數字，要轉成double類型。
-training_instance_matrix:訓練樣本的特徵，如果有m個樣本，每個樣本特徵是n維，則為m x n的矩陣（類型必須為double）。
-libsvm_options:訓練的參數，在第3點詳細介紹。
2. 預測
libpredict函數用於對測試集的數據進行測試，還能對未知樣本進行預測。

[predicted_label, accuracy, decision_values/prob_estimates]
= libsvmpredict(testing_label_vector, testing_instance_matrix, model [, 'libsvm_options']);

這個函數包括四個參數，其中

-testing_label_vector:測試樣本的類標，如果有m個樣本，就是m x 1的矩陣（類型必須為double）。如果類標未知，可以初始化為任意m x 1的double數組。
-testing_instance_matrix:測試樣本的特徵，如果有m個樣本，每個樣本特徵是n維，則為m x n的矩陣（類型必須為double）。
-model:使用libsvmtrain返回的模型
-libsvm_options:預測的參數，與訓練的參數形式一樣。
3. 訓練的參數
LIBSVM訓練時可以選擇的參數很多，包括：

-s svm類型：SVM設置類型（默認0)
0 — C-SVC； 1 –v-SVC； 2 – 一類SVM； 3 — e-SVR； 4 — v-SVR
-t 核函數類型：核函數設置類型（默認2）
0 – 線性核函數：u』v
1 – 多項式核函數：（r*u』v + coef0)^degree
2 – RBF(徑向基)核函數：exp(-r|u-v|^2）
3 – sigmoid核函數：tanh(r*u』v + coef0)
-d degree：核函數中的degree設置（針對多項式核函數）（默認3）
-g r(gamma）：核函數中的gamma函數設置（針對多項式/rbf/sigmoid核函數）（默認1/k，k為總類別數)
-r coef0：核函數中的coef0設置（針對多項式/sigmoid核函數）（（默認0)
-c cost：設置C-SVC，e -SVR和v-SVR的參數（損失函數）（默認1）
-n nu：設置v-SVC，一類SVM和v- SVR的參數（默認0.5）
-p p：設置e -SVR 中損失函數p的值（默認0.1）
-m cachesize：設置cache內存大小，以MB為單位（默認40）
-e eps：設置允許的終止判據（默認0.001）
-h shrinking：是否使用啟發式，0或1（默認1）
-wi weight：設置第幾類的參數C為weight*C (C-SVC中的C) （默認1）
-v n: n-fold交互檢驗模式，n為fold的個數，必須大於等於2
以上這些參數設置可以按照SVM的類型和核函數所支持的參數進行任意組合，如果設置的參數在函數或SVM類型中沒有也不會產生影響，程序不會接受該參數；如果應有的參數設置不正確，參數將採用默認值。

4. 訓練返回的內容
libsvmtrain函數返回訓練好的SVM分類器模型，可以用來對未知的樣本進行預測。這個模型是一個結構體，包含以下成員：

-Parameters: 一個5 x 1的矩陣，從上到下依次表示：
-s SVM類型（默認0）；
-t 核函數類型（默認2）
-d 核函數中的degree設置(針對多項式核函數)(默認3)；
-g 核函數中的r(gamma）函數設置(針對多項式/rbf/sigmoid核函數) (默認類別數目的倒數)；
-r 核函數中的coef0設置(針對多項式/sigmoid核函數)((默認0)
-nr_class: 表示數據集中有多少類別，比如二分類時這個值即為2。
-totalSV: 表示支持向量的總數。
-rho: 決策函數wx+b中的常數項的相反數（-b）。
-Label: 表示數據集中類別的標簽，比如二分類常見的1和-1。
-ProbA: 使用-b參數時用於概率估計的數值，否則為空。
-ProbB: 使用-b參數時用於概率估計的數值，否則為空。
-nSV: 表示每類樣本的支持向量的數目，和Label的類別標簽對應。如Label=[1; -1],nSV=[63; 67]，則標簽為1的樣本有63個支持向量，標簽為-1的有67個。
-sv_coef: 表示每個支持向量在決策函數中的系數。
-SVs: 表示所有的支持向量，如果特徵是n維的，支持向量一共有m個，則為m x n的稀疏矩陣。
另外，如果在訓練中使用了-v參數進行交叉驗證時，返回的不是一個模型，而是交叉驗證的分類的正確率或者回歸的均方根誤差。

5. 預測返回的內容
libsvmtrain函數有三個返回值，不需要的值在Matlab可以用~進行代替。

-predicted_label：第一個返回值，表示樣本的預測類標號。
-accuracy：第二個返回值，一個3 x 1的數組，表示分類的正確率、回歸的均方根誤差、回歸的平方相關系數。
-decision_values/prob_estimates：第三個返回值，一個矩陣包含決策的值或者概率估計。對於n個預測樣本、k類的問題，如果指定「-b 1」參數，則n x k的矩陣，每一行表示這個樣本分別屬於每一個類別的概率；如果沒有指定「-b 1」參數，則為n x k*(k-1)/2的矩陣，每一行表示k(k-1)/2個二分類SVM的預測結果。
6. 讀取或保存
libsvmread函數可以讀取以LIBSVM格式存儲的數據文件。

[label_vector, instance_matrix] = libsvmread(『data.txt』);

這個函數輸入的是文件的名字，輸出為樣本的類標和對應的特徵。

libsvmwrite函數可以把Matlab的矩陣存儲稱為LIBSVM格式的文件。

libsvmwrite(『data.txt』, label_vector, instance_matrix]

這個函數有三個輸入，分別為保存的文件名、樣本的類標和對應的特徵（必須為double類型的稀疏矩陣）。

五 更新:svdd擴展安裝（2014.10）
從libsvm官網下載svdd工具箱，目前使用libsvm3.18以及svdd3.18版本。

svdd工具箱裡面有一個matlab文件夾和3個文件svm.cpp、svm.h、svm-train.c。
將matlab文件夾中的文件svmtrain.c覆蓋原libsvm的matlab文件夾中的文件。
將svm.cpp、svm.h、svm-train.c這3個文件覆蓋libsvm文件夾下的相同文件。
按本文剛開始講述的方法進行mex -setup、make等完成安裝，根據需要進行改名以及添加Path。

『伍』 小球大間隔模型存在的對偶問題

軟間隔
在上文當中我們說了，在實際的場景當中，數據不可能是百分百線性可分的，即使真的能硬生生地找到這樣的一個分隔平面區分開樣本，那麼也很有可能陷入過擬合當中，也是不值得追求的。

因此，我們需要對分類器的標准稍稍放鬆，允許部分樣本出錯。但是這就帶來了一個問題，在硬間隔的場景當中，間隔就等於距離分隔平面最近的支持向量到分隔平面的距離。那麼，在允許出錯的情況下，這個間隔又該怎麼算呢？

為了解決這個問題，我們需要對原本的公式進行變形，引入一個新的變數叫做鬆弛變數。鬆弛變數我們用希臘字母𝜉
ξ
來表示，這個鬆弛變數允許我們適當放鬆$y_i(\omega^T x_i + b) \ge 1 這個限制條件，我們將它變成
這
個
限
制
條
件
，
我
們
將
它
變
成
y_i(\omega^T x_i + b) \ge 1-\xi_i $。

也就是說對於每一條樣本我們都會有一個對應的鬆弛變數𝜉𝑖
ξ
i
，它一共有幾種情況。

𝜉=0
ξ
=
0
，表示樣本能夠正確分類
0<𝜉<1
0
<
ξ
<
1
，表示樣本在分割平面和支持向量之間
𝜉=1
ξ
=
1
，表示樣本在分割平面上
𝜉≥1
ξ
≥
1
，表示樣本異常
我們可以結合下面這張圖來理解一下，會容易一些：

鬆弛變數雖然可以讓我們表示那些被錯誤分類的樣本，但是我們當然不希望它隨意鬆弛，這樣模型的效果就不能保證了。所以我們把它加入損失函數當中，希望在鬆弛得盡量少的前提下保證模型盡可能劃分正確。這樣我們可以重寫模型的學習條件：

min12||𝜔||2+𝐶∑𝑖=1𝑚𝜉𝑖𝑠.𝑡.𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏)≥1−𝜉𝑖,𝜉𝑖≥0,𝑖=1,2,3…,𝑛𝑖=1,2,3…,𝑛
min
1
2
|
|
ω
|
|
2
+C
∑
i
=
1
m
ξ
i
s.t.
y
i
(
ω
T
x
i
+b)≥1−
ξ
i
, i=1,2,3…,n
ξ
i
≥0, i=1,2,3…,n
這里的C是一個常數，可以理解成懲罰參數。我們希望||𝜔||2
|
|
ω
|
|
2
盡量小，也希望∑𝜉𝑖
∑
ξ
i
盡量小，這個參數C就是用來協調兩者的。C越大代表我們對模型的分類要求越嚴格，越不希望出現錯誤分類的情況，C越小代表我們對鬆弛變數的要求越低。

從形式上來看模型的學習目標函數和之前的硬間隔差別並不大，只是多了一個變數而已。這也是我們希望的，在改動盡量小的前提下讓模型支持分隔錯誤的情況。

模型推導
對於上面的式子我們同樣使用拉格朗日公式進行化簡，將它轉化成沒有約束的問題。

首先，我們確定幾個值。第一個是我們要優化的目標：𝑓(𝑥)=min𝜔,𝑏,𝜉12||𝜔||2+𝐶∑𝑚𝑖=1𝜉𝑖
f
(
x
)
=
min
ω
,
b
,
ξ
1
2
|
|
ω
|
|
2
+
C
∑
i
=
1
m
ξ
i

第二個是不等式約束，拉格朗日乘子法當中限定不等式必須都是小於等於0的形式，所以我們要將原式中的式子做一個簡單的轉化：

𝑔(𝑥)=1−𝜉𝑖−𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏)≤0ℎ(𝑥)=−𝜉𝑖≤0
g(x)=1−
ξ
i
−
y
i
(
ω
T
x
i
+b)≤0 h(x)=−
ξ
i
≤0
最後是引入拉格朗日乘子: 𝛼=(𝛼1,𝛼2,⋯,𝛼𝑚),𝛽=(𝛽1,𝛽2,⋯,𝛽𝑚)
α
=
(
α
1
,
α
2
,
⋯
,
α
m
)
,
β
=
(
β
1
,
β
2
,
⋯
,
β
m
)

我們寫出廣義拉格朗日函數：𝐿(𝜔,𝑏,𝜉,𝛼,𝛽)=12||𝜔||2+𝐶∑𝑚𝑖=1𝜉𝑖,+∑𝑚𝑖=1𝛼𝑖(1−𝜉𝑖−𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏))−∑𝑚𝑖=1𝛽𝑖𝜉𝑖
L
(
ω
,
b
,
ξ
,
α
,
β
)
=
1
2
|
|
ω
|
|
2
+
C
∑
i
=
1
m
ξ
i
,
+
∑
i
=
1
m
α
i
(
1
−
ξ
i
−
y
i
(
ω
T
x
i
+
b
)
)
−
∑
i
=
1
m
β
i
ξ
i

我們要求的是這個函數的最值，也就是min𝜔,𝑏,𝜉max𝛼≥0,𝛽≥0𝐿(𝜔,𝑏,𝜉,𝛼,𝛽)
min
ω
,
b
,
ξ
max
α
≥
0
,
β
≥
0
L
(
ω
,
b
,
ξ
,
α
,
β
)
。

在處理硬間隔的時候，我們講過對偶問題，對於軟間隔也是一樣。我們求L函數的對偶函數的極值。

對偶問題
原函數的對偶問題是max𝛼≥0,𝛽≥0min𝜔,𝑏,𝜉𝐿(𝜔,𝑏,𝜉,𝛼,𝛽)
max
α
≥
0
,
β
≥
0
min
ω
,
b
,
ξ
L
(
ω
,
b
,
ξ
,
α
,
β
)
，這個對偶問題要成立需要滿足KKT條件。

我們先把這個KKT條件放一放，先來看一下對偶問題當中的內部的極小值。這個極小值沒有任何約束條件，所以我們可以放心大膽地通過求導來來計算極值。這個同樣是高中數學的內容，我們分別計算∂𝐿∂𝜔
∂
L
∂
ω
，∂𝐿∂𝑏
∂
L
∂
b
和∂𝐿∂𝜉
∂
L
∂
ξ
。

求導之後，我們可以得到：

∂𝐿∂𝜔=0∂𝐿∂𝑏=0∂𝐿∂𝜉=0→𝜔=∑𝑖=1𝑚𝛼𝑖𝑦𝑖𝑥𝑖→∑𝑖=1𝑚𝛼𝑖𝑦𝑖=0→𝛽𝑖=𝐶−𝛼𝑖
∂
L
∂
ω
=0 →ω=
∑
i
=
1
m
α
i
y
i
x
i
∂
L
∂
b
=0 →
∑
i
=
1
m
α
i
y
i
=0
∂
L
∂
ξ
=0 →
β
i
=C−
α
i

我們把這三個式子帶入對偶函數可以得到：

𝐿(𝜔,𝑏,𝜉,𝛼,𝛽)=12∑𝑖=1𝑚∑𝑗=1𝑚𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗𝑥𝑇𝑖𝑥𝑗+𝐶∑𝑖=1𝑚𝜉𝑖+∑𝑖=1𝑚𝛼𝑖(1−𝜉𝑖)−∑𝑖=1𝑚(𝐶−𝛼𝑖)𝜉𝑖=∑𝑖=1𝑚𝛼𝑖−12∑𝑖=1𝑚∑𝑗=1𝑚𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗𝑥𝑇𝑖𝑥𝑗
L(ω,b,ξ,α,β) =
1
2
∑
i
=
1
m
∑
j
=
1
m
α
i
α
j
y
i
y
j
x
i
T
x
j
+C
∑
i
=
1
m
ξ
i
+
∑
i
=
1
m
α
i
(1−
ξ
i
)−
∑
i
=
1
m
(C−
α
i
)
ξ
i
=
∑
i
=
1
m
α
i
−
1
2
∑
i
=
1
m
∑
j
=
1
m
α
i
α
j
y
i
y
j
x
i
T
x
j

由於𝛽𝑖≥0
β
i
≥
0
，所以我們可以得到0≤𝛼𝑖≤𝐶
0
≤
α
i
≤
C
，所以最後我們可以把式子化簡成：

max𝛼∑𝑖=1𝑚𝛼𝑖−12∑𝑖=1𝑚∑𝑗=1𝑚𝛼𝑖𝛼𝑗𝑦𝑖𝑦𝑗𝑥𝑇𝑖𝑥𝑗𝑠.𝑡.∑𝑚𝑖=1𝛼𝑖𝑦𝑖=00≤𝛼𝑖≤𝐶,𝑖=1,2,3…,𝑚
max
α
∑
i
=
1
m
α
i
−
1
2
∑
i
=
1
m
∑
j
=
1
m
α
i
α
j
y
i
y
j
x
i
T
x
j
s.t.
∑
i
=
1
m
α
i
y
i
=0 0≤
α
i
≤C, i=1,2,3…,m
將原始化簡了之後，我們再回過頭來看KKT條件。KKT條件單獨理解看起來有點亂，其實我們可以分成三個部分，分別是原始問題可行：

1−𝜉𝑖−𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏)≤0−𝜉𝑖≤0
1−
ξ
i
−
y
i
(
ω
T
x
i
+b)≤0 −
ξ
i
≤0
對偶問題可行：

𝛼𝑖≥0𝛽𝑖=𝐶−𝛼𝑖
α
i
≥0
β
i
=C−
α
i

以及鬆弛可行：

𝛼𝑖(1−𝜉−𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏))=0𝛽𝑖𝜉𝑖=0
α
i
(1−ξ−
y
i
(
ω
T
x
i
+b))=0
β
i
ξ
i
=0
我們觀察一下倒數第二個條件：𝛼𝑖(1−𝜉−𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏))=0
α
i
(
1
−
ξ
−
y
i
(
ω
T
x
i
+
b
)
)
=
0
。

這是兩個式子相乘並且等於0，無非兩種情況，要麼𝛼𝑖=0
α
i
=
0
，要麼後面那串等於0。我們分情況討論。

如果𝛼𝑖=0
α
i
=
0
，那麼𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏)−1≥0
y
i
(
ω
T
x
i
+
b
)
−
1
≥
0
，樣本分類正確，不會對模型產生影響。
如果𝛼𝑖>0
α
i
>
0
，那麼𝑦𝑖(𝜔𝑇𝑥𝑖+𝑏)=1−𝜉𝑖
y
i
(
ω
T
x
i
+
b
)
=
1
−
ξ
i
，則樣本是支持向量。由於𝐶=𝛼𝑖+𝛽𝑖
C
=
α
i
+
β
i
，並且𝛽𝑖𝜉𝑖=0
β
i
ξ
i
=
0
。我們又可以分情況：
𝛼𝑖<𝐶
α
i
<
C
，那麼𝛽𝑖>0
β
i
>
0
，所以𝜉𝑖=0
ξ
i
=
0
，那麼樣本在邊界上
如果𝛼𝑖=𝐶
α
i
=
C
，那麼𝛽𝑖=0
β
i
=
0
，如果此時𝜉≤1
ξ
≤
1
，那麼樣本被正確分類，否則樣本被錯誤分類
經過了化簡之後，式子當中只剩下了變數𝛼
α
，我們要做的就是找到滿足約束條件並且使得式子取極值時的𝛼
α
，這個𝛼
α
要怎麼求呢？我們這里先放一放，將在下一篇文章當中詳解講解。

『陸』 聚類演算法概述及比較

其本質是：尋找聯系緊密的事物進行區分，將數據劃分為有意義或有用的簇

目標是：同簇內的數據對象的相似性盡可能大，不同簇間的數據對象的差異性盡可能大。

核心是：相似度計算

回顧一下：無監督學習(Unsupervised learning)：是否有監督（supervised），就看輸入數據是否有標簽（label）。輸入數據有標簽，則為有監督學習，沒標簽則為無監督學習。

具體包含：

K-means DIANA OPTICS Spectral STING COBWeb
K-medoids BIRCH DBSCAN CLIQUE CLASSIT
CLARANS Chameleon FDC WAVE-CLUSTER SOM

新發展的方法:

基於約束 基於模糊 基於粒度 量子聚類 核聚類 譜聚類
COD (Clustering
with Ob2structed
Distance) FCM SVDD/SVC 圖論中的譜圖

劃分法（Partitioning methods）:

層次法（Hierarchical Clustering）:

基於密度的聚類（density-based methods）:

基於圖的聚類（Graph-based methods）：

基於網格的方法（grid-based methods）:

基於模型的方法（model-based methods）:

map詳細: http://scikit-learn.org/stable/tutorial/machine_learning_map/