考慮圖6-6給出的數據,這有點像圖6-1的方框C中的數據。前面我們用這類數據來描述非線性可分的情況。顯而易見,在該數據中存在某種可以識別的模式。其中一個問題就是,我們能否像線性情況一樣,利用強大的工具來捕捉數據中的這種模式?顯然,答案是肯定的。接下來,我們就要使用一種稱為核函數(kernel)的工具將數據轉換成易於分類器理解的形式。本節首先解釋核函數的概念,並介紹它們在支持向量機中的使用方法。然後,介紹一種稱為徑向基函數(radial basis function)的最流行的核函數。最後,將該核函數應用於我們前面得到的分類器。
圖6-6 這個數據在二維平面中很難用一條直線分隔,不過很明顯,這裡存在分隔方形點和圓形點的模式
6.5.1 利用核函數將數據映射到高維空間
在圖6-6中,數據點處於一個圓中,人類的大腦能夠意識到這一點。然而,對於分類器而言,它只能識別分類器的結果是大於0還是小於0。如果只在X和Y軸構成的坐標系中插入直線進行分類的話,我們並不會得到理想的結果。我們或許可以對圓中的數據進行某種形式的轉換,從而得到某些新的變量來表示數據。在這種表示情況下,我們就更容易得到大於0或者小於0的測試結果。在這個例子中,我們將數據從一個特徵空間轉換到另一個特徵空間。在新空間下,我們可以很容易利用已有的工具對數據進行處理。數學家們喜歡將這個過程稱之為從一個特徵空間到另一個特徵空間的映射。在通常情況下,這種映射會將低維特徵空間映射到高維空間。
這種從某個特徵空間到另一個特徵空間的映射是通過核函數來實現的。讀者可以把核函數想像成一個包裝器(wrapper)或者是接口(interface),它能把數據從某個很難處理的形式轉換成為另一個較容易處理的形式。如果上述特徵空間映射的說法聽起來很讓人迷糊的話,那麼可以將它想像成為另外一種距離計算的方法。前面我們提到過距離計算的方法。距離計算的方法有很多種,不久我們也將看到,核函數一樣具有多種類型。經過空間轉換之後,我們可以在高維空間中解決線性問題,這也就等價於在低維空間中解決非線性問題。
SVM優化中一個特別好的地方就是,所有的運算都可以寫成內積(inner product,也稱點積)的形式。向量的內積指的是兩個向量相乘,之後得到單個標量或者數值。我們可以把內積運算替換成核函數,而不必做簡化處理。將內積替換成核函數的方式被稱為核技巧(kernel trick)或者核「變電」(kernel substation)。
核函數並不僅僅應用於支持向量機,很多其他的機器學習算法也都用到核函數。接下來,我們將要來介紹一個流行的核函數,那就是徑向基核函數。
6.5.2 徑向基核函數
徑向基函數是SVM中常用的一個核函數。徑向基函數是一個採用向量作為自變量的函數,能夠基於向量距離運算輸出一個標量。這個距離可以是從<0,0>向量或者其他向量開始計算的距離。接下來,我們將會使用到徑向基函數的高斯版本,其具體公式為:
其中,σ
是用戶定義的用於確定到達率(reach) 或者說函數值跌落到0的速度參數。
上述高斯核函數將數據從其特徵空間映射到更高維的空間,具體來說這裡是映射到一個無窮維的空間。關於無窮維空間,讀者目前不需要太擔心。高斯核函數只是一個常用的核函數,使用者並不需要確切地理解數據到底是如何表現的,而且使用高斯核函數還會得到一個理想的結果。在上面的例子中,數據點基本上都在一個圓內。對於這個例子,我們可以直接檢查原始數據,並意識到只要度量數據點到圓心的距離即可。然而,如果碰到了一個不是這種形式的新數據集,那麼我們就會陷入困境。在該數據集上,使用高斯核函數可以得到很好的結果。當然,該函數也可以用於許多其他的數據集,並且也能得到低錯誤率的結果。
如果在svmMLiA.py
文件中添加一個函數並稍做修改,那麼我們就能夠在已有代碼中使用核函數。首先,打開svMLiA.py
代碼文件並輸入函數kernelTrans
。然後,對optStruct
類進行修改,得到類似如下程序清單6-6的代碼。
程序清單6-6 核轉換函數
def kernelTrans(X, A, kTup):
m,n = shape(X)
K = mat(zeros((m,1)))
if kTup[0]==\'lin\': K = X * A.T
elif kTup[0]==\'rbf\':
for j in range(m):
deltaRow = X[j,:] - A
K[j] = deltaRow*deltaRow.T
# ❶ 元素間的除法
K = exp(K /(-1*kTup[1]**2))
else: raise NameError(\'Houston We Have a Problem -- That Kernel is not recognized\')
return K
class optStruct:
def __init__(self,dataMatIn, classLabels, C, toler, kTup):
self.X = dataMatIn
self.labelMat = classLabels
self.C = C
self.tol = toler
self.m = shape(dataMatIn)[0]
self.alphas = mat(zeros((self.m,1)))
self.b = 0
self.eCache = mat(zeros((self.m,2)))
self.K = mat(zeros((self.m,self.m)))
for i in range(self.m):
self.K[:,i] = kernelTrans(self.X, self.X[i,:], kTup)
我建議讀者最好看一下optStruct
類的新版本。除了引入了一個新變量kTup
之外,該版本和原來的optStruct
一模一樣。kTup
是一個包含核函數信息的元組,待會兒我們就能看到它的作用了。在初始化方法結束時,矩陣K
先被構建,然後再通過調用函數kernelTrans
進行填充。全局的K
值只需計算一次。然後,當想要使用核函數時,就可以對它進行調用。這也省去了很多冗余的計算開銷。
當計算矩陣K
時,該過程多次調用了函數kernelTrans
。該函數有3個輸入參數:2個數值型變量和1個元組。元組kTup
給出的是核函數的信息。元組的第一個參數是描述所用核函數類型的一個字符串,其他2個參數則都是核函數可能需要的可選參數。該函數首先構建出了一個列向量,然後檢查元組以確定核函數的類型。這裡只給出了2種選擇,但是依然可以很容易地通過添加elif
語句來擴展到更多選項。
在線性核函數的情況下,內積計算在「所有數據集」和「數據集中的一行」這兩個輸入之間展開。在徑向基核函數的情況下,在for
循環中對於矩陣的每個元素計算高斯函數的值。而在for
循環結束之後,我們將計算過程應用到整個向量上去。值得一提的是,在NumPy矩陣中,除法符號意味著對矩陣元素展開計算而不像在MATLAB中一樣計算矩陣的逆❶。
最後,如果遇到一個無法識別的元組,程序就會拋出異常,因為在這種情況下不希望程序再繼續運行,這一點相當重要。
為了使用核函數,先期的兩個函數innerL
和calcEk
的代碼需要做些修改。修改的結果參見程序清單6-7。本來我並不想這樣列出代碼,但是重新列出函數的所有代碼需要超過90行,我想任何人都不希望這樣。讀者可以直接從下載的源碼中複製代碼段,而不必對修改片段進行手工輸入。下面列出的就是修改的代碼片段。
程序清單6-7 使用核函數時需要對innerL
及calcEk
函數進行的修改
innerL:
.
.
.
eta = 2.0 * oS.K[i,j] - oS.K[i,i] - oS.K[j,j]
.
.
.
b1 = oS.b - Ei- oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.K[i,i] -
oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.K[i,j]
b2 = oS.b - Ej- oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.K[i,j]-
oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.K[j,j]
.
.
.
def calcEk(oS, k):
fXk = float(multiply(oS.alphas,oS.labelMat).T*oS.K[:,k] + oS.b)
Ek = fXk - float(oS.labelMat[k])
return Ek
你已經瞭解了如何在訓練過程中使用核函數,接下來我們就去瞭解如何在測試過程中使用核函數。
6.5.3 在測試中使用核函數
接下來我們將構建一個對圖6-6中的數據點進行有效分類的分類器,該分類器使用了徑向基核函數。前面提到的徑向基函數有一個用戶定義的輸入σ
。首先,我們需要確定它的大小,然後利用該核函數構建出一個分類器。整個測試函數將如程序清單6-8所示。讀者也可以打開一個文本編輯器,並且加入函數testRbf
。
程序清單6-8 利用核函數進行分類的徑向基測試函數
def testRbf(k1=1.3):
dataArr,labelArr = loadDataSet(\'testSetRBF.txt\')
b,alphas = smoP(dataArr, labelArr, 200, 0.0001, 10000, (\'rbf\', k1))
datMat=mat(dataArr); labelMat = mat(labelArr).transpose
svInd=nonzero(alphas.A>0)[0]
#構建支持向量矩陣
sVs=datMat[svInd]
labelSV = labelMat[svInd];
print \"there are %d Support Vectors\" % shape(sVs)[0]
m,n = shape(datMat)
errorCount = 0
for i in range(m):
kernelEval = kernelTrans(sVs,datMat[i,:],(\'rbf\', k1))
predict=kernelEval.T * multiply(labelSV,alphas[svInd]) + b
if sign(predict)!=sign(labelArr[i]): errorCount += 1
print \"the training error rate is: %f\" % (float(errorCount)/m)
dataArr,labelArr = loadDataSet(\'testSetRBF2.txt\')
errorCount = 0
datMat=mat(dataArr); labelMat = mat(labelArr).transpose
m,n = shape(datMat)
for i in range(m):
kernelEval = kernelTrans(sVs,datMat[i,:],(\'rbf\', k1))
predict=kernelEval.T * multiply(labelSV,alphas[svInd]) + b
if sign(predict)!=sign(labelArr[i]): errorCount += 1
print \"the test error rate is: %f\" % (float(errorCount)/m)
上述代碼只有一個可選的輸入參數,該輸入參數是高斯徑向基函數中的一個用戶定義變量。整個代碼主要是由以前定義的函數集合構成的。首先,程序從文件中讀入數據集,然後在該數據集上運行Platt SMO算法,其中核函數的類型為\'rbf\'
。
優化過程結束後,在後面的矩陣數學運算中建立了數據的矩陣副本,並且找出那些非零的alpha值,從而得到所需要的支持向量;同時,也就得到了這些支持向量和alpha的類別標籤值。這些值僅僅是需要分類的值。
整個代碼中最重要的是for
循環開始的那兩行,它們給出了如何利用核函數進行分類。首先利用結構初始化方法中使用過的kernelTrans
函數,得到轉換後的數據。然後,再用其與前面的alpha及類別標籤值求積。其中需要特別注意的另一件事是,在這幾行代碼中,是如何做到只需要支持向量數據就可以進行分類的。除此之外,其他數據都可以直接捨棄。
與第一個for
循環相比,第二個for
循環僅僅只有數據集不同,後者採用的是測試數據集。讀者可以比較不同的設置在測試集和訓練集上表現出的性能。
為測試程序清單6-8的代碼,可以在Python提示符下輸入命令:
>>> reload(svmMLiA)
<module \'svmMLiA\' from \'svmMLiA.pyc\'>
>>> svmMLiA.testRbf
.
.
fullSet, iter: 11 i:497, pairs changed 0
fullSet, iter: 11 i:498, pairs changed 0
fullSet, iter: 11 i:499, pairs changed 0
iteration number: 12
there are 27 Support Vectors
the training error rate is: 0.030000
the test error rate is: 0.040000
你可以嘗試更換不同的k1
參數以觀察測試錯誤率、訓練錯誤率、支持向量個數隨k1
的變化情況。圖6-7給出了當k1
非常小(=0.1)時的結果。
圖6-7 在用戶自定義參數k1 = 0.1
時的徑向基函數。該參數此時減少了每個支持向量的影響程度,因此需要更多的支持向量
圖6-7中共有100個數據點,其中的85個為支持向量。優化算法發現,必須使用這些支持向量才能對數據進行正確分類。這就可能給了讀者徑向基函數到達率太小的直覺。我們可以通過增加σ
來觀察錯誤率的變化情況。增加σ
之後得到的另一個結果如圖6-8所示。
圖6-8 在用戶自定義參數k1=1.3
時的徑向基函數。這裡的支持向量個數少於圖6-7的,而這些支持向量在決策邊界周圍聚集
同圖6-7相比,圖6-8中只有27個支持向量,其數目少了很多。這時觀察一下函數testRbf
的輸出結果就會發現,此時的測試錯誤率也在下降。該數據集在這個設置的某處存在著最優值。如果降低σ
,那麼訓練錯誤率就會降低,但是測試錯誤率卻會上升。
支持向量的數目存在一個最優值。SVM的優點在於它能對數據進行高效分類。如果支持向量太少,就可能會得到一個很差的決策邊界(下個例子會說明這一點);如果支持向量太多,也就相當於每次都利用整個數據集進行分類,這種分類方法稱為k近鄰。
我們可以對SMO算法中的其他設置進行隨意地修改或者建立新的核函數。接下來,我們將在一個更大的數據上應用支持向量機,並與以前介紹的一個分類器進行對比。