模式識(shí)別導(dǎo)論第9章模式分析的核方法.ppt

1、第9章 模式分析的核方法,9.1 核函數(shù) 9.2 核HCM算法 9.3 核FCM算法 9.4 核離散K-L變換 9.5 核Fisher線性判別 9.6 支持向量機(jī),現(xiàn)實(shí)世界存在的數(shù)據(jù)是復(fù)雜的，傳統(tǒng)的線性學(xué)習(xí)器一般很難適用于線性不可分?jǐn)?shù)據(jù)的劃分問(wèn)題，為此人們需要利用比線性函數(shù)更富有表達(dá)能力的假設(shè)空間。核方法提供了一種很好的解決途徑，它利用特征映射將低維輸入空間中的線性不可分?jǐn)?shù)據(jù)映射到高維特征空間(一般來(lái)說(shuō)，該高維特征空間是一個(gè)希爾伯特空間)，使其在該空間中變得線性可分。該方法使得數(shù)據(jù)在高維空間中易于處理，同時(shí)又避免了高維空間帶來(lái)的維數(shù)災(zāi)難問(wèn)題，大大提升了傳統(tǒng)線性學(xué)習(xí)器的計(jì)算能力。對(duì)核方法的研究受

2、到了研究者越來(lái)越多的關(guān)注。本章首先介紹核函數(shù)的基本理論，然后對(duì)模式識(shí)別領(lǐng)域中幾種經(jīng)典的核方法進(jìn)行敘述。,9.1 核 函 數(shù)9.1.1 非線性特征映射和核函數(shù)給定l維輸入空間X上的一個(gè)模式x=(x1，x2，xq)T，采用一種非線性特征映射函數(shù)()將x從q維原模式特征空間映射到Q維變換特征空間，即,(9-1),其中，(x)=(1(x)，2(x)，Q(x)T。()表示一個(gè)從低維特征空間到高維特征空間的非線性映射，映射的目的是將非線性可分的樣本在變換特征空間中線性可分。以圖9.1中左側(cè)的數(shù)據(jù)為例，對(duì)其進(jìn)行非線性映射，得到圖9.1中右側(cè)的數(shù)據(jù)，可以明顯看出，數(shù)據(jù)在新特征空間中是線性可分的。在現(xiàn)實(shí)生活中，

3、很多問(wèn)題都不能用線性函數(shù)來(lái)表示，但是如果改變其表達(dá)形式，則有可能用線性函數(shù)來(lái)描述。下面以物理學(xué)中的萬(wàn)有引力定律為例進(jìn)行說(shuō)明。,圖9.1 低維空間中的線性不可分?jǐn)?shù)據(jù)映射到 高維空間后變成線性可分,例9.1 牛頓萬(wàn)有引力定律是解釋物體之間的相互作用的引力定律，其表達(dá)式為其中,m1和m2為兩個(gè)物體的質(zhì)量，r為它們之間的距離。很明顯，傳統(tǒng)的線性學(xué)習(xí)器是不能表達(dá)這種關(guān)系的。我們按照如下方式對(duì)坐標(biāo)進(jìn)行變換；可以得到新的表達(dá)方式；該表達(dá)式可以通過(guò)一個(gè)線性學(xué)習(xí)器進(jìn)行學(xué)習(xí)。,根據(jù)模式識(shí)別理論，低維空間線性不可分的模式可以通過(guò)非線性映射將其映射到高維特征空間來(lái)實(shí)現(xiàn)線性可分，此高維特征空間應(yīng)該是完備且可分的內(nèi)積空間

4、。所謂內(nèi)積空間是指，在向量空間X上，如果存在一個(gè)實(shí)值對(duì)稱(chēng)的雙線性(對(duì)于每個(gè)自變量來(lái)說(shuō)都是線性的)映射，(這一映射也被稱(chēng)為內(nèi)積)，該映射滿足x，x0，則該向量空間是一個(gè)內(nèi)積空間。此外，如果當(dāng)且僅當(dāng)x=0時(shí)x，x=0，則稱(chēng)內(nèi)積是嚴(yán)格的。嚴(yán)格內(nèi)積空間也被稱(chēng)為希爾伯特空間，下面給出其正式的定義。,定義9.1 希爾伯特空間F是一個(gè)具備可分性和完備性的嚴(yán)格內(nèi)積空間。完備性是指F中的元素的每一柯西序列hnn1都收斂于元素hF。這里，柯西序列是滿足性質(zhì)的序列?？煞中允侵缚臻gF中有一組可數(shù)元素h1，hi，使得對(duì)于所有的hF和0，存在i滿足|hih| (9-3),(9-2),如果直接在映射后的特征空間進(jìn)行分類(lèi)，則

5、存在確定非線性映射函數(shù)的形式和參數(shù)以及特征空間維數(shù)等問(wèn)題。此外，在高維空間進(jìn)行運(yùn)算存在“維數(shù)災(zāi)難”問(wèn)題。有時(shí)候我們可以把內(nèi)積作為輸入特征的直接函數(shù)來(lái)更高效地計(jì)算內(nèi)積，而不用顯式地計(jì)算映射函數(shù)()。我們把這種直接計(jì)算內(nèi)積的技術(shù)稱(chēng)為核函數(shù)技術(shù)。下面給出核函數(shù)的定義。,定義9.2 對(duì)于所有的x，若函數(shù)K滿足K(x，z)=(x)，(z) (9-4)則稱(chēng)函數(shù)K是核函數(shù)，其中是從輸入空間X到特征空間F的一個(gè)映射(見(jiàn)式(9-1)，表示內(nèi)積。下面給出一個(gè)核函數(shù)的例子來(lái)說(shuō)明非線性特征映射和核函數(shù)的關(guān)系。例9.2 考慮一個(gè)二維輸入空間，假設(shè)通過(guò)特征映射得到,那么，F(xiàn)中的線性函數(shù)的假設(shè)空間將是通過(guò)上面這樣一種特征映

6、射方式，輸入空間中的數(shù)據(jù)從二維空間被映射到三維空間。在特征空間中，利用給出的特征映射結(jié)果和內(nèi)積操作，可以得到,因此，函數(shù)K(x，z)=x，z2就是一個(gè)核函數(shù)。這意味著我們可以計(jì)算兩個(gè)點(diǎn)在原輸入特征空間上的內(nèi)積，而不用顯式地求出它們?cè)谛绿卣骺臻gF的坐標(biāo)。此外，x，z2也可以是下面給出的四維特征映射的內(nèi)積，這表明特征空間并不能由核函數(shù)唯一確定。,9.1.2 核函數(shù)的基本理論定義9.2中給出了核函數(shù)K與映射之間的關(guān)系。在實(shí)際應(yīng)用中，非線性映射的具體表達(dá)式是很難直接給出的，我們可以通過(guò)核函數(shù)的構(gòu)造和確定來(lái)隱式地定義特征空間，避免對(duì)原數(shù)據(jù)進(jìn)行映射。下面給出幾個(gè)與核函數(shù)相關(guān)的概念和性質(zhì)。定義9.3(Gra

7、m矩陣) 給定一個(gè)向量集合X=x1，x2，xn，Gram矩陣G為nn的矩陣，其矩陣元素Gij=xi，xj。,定義9.4(核函數(shù)矩陣) 給定輸入空間的向量集合X=x1，x2，xn，核函數(shù)矩陣K被定義為nn的矩陣，且其矩陣元素為Kij=(xi)，(xj)=K(xi，xj)。其中，K為核函數(shù)。從定義9.3和9.4中可以看出G和K都是對(duì)稱(chēng)矩陣，并且K是特征空間的Gram矩陣。定義9.5 半正定性(連續(xù)情況)對(duì)于任意的fL2(X)，如果對(duì)稱(chēng)函數(shù)K(xi，xj)使下式成立；,(9-5),則稱(chēng)函數(shù)K(xi，xj)為半正定的；,(離散情況)對(duì)于任意的n，任意的樣本集x1，x2，和任意的系數(shù)a1，a2，anR，

8、如果對(duì)稱(chēng)函數(shù)K(xi，xj)滿足下式；則稱(chēng)函數(shù)K(xi，xj)為半正定的?？梢宰C明，Gram矩陣和核函數(shù)矩陣都是半正定矩陣。下面，我們采用定理9.1對(duì)核函數(shù)進(jìn)行描述。,(9-6),定理9.1(核的描述) 假設(shè)函數(shù)K：XXR，K這個(gè)函數(shù)可分解為K(x，z)=(x)，(z)當(dāng)且僅當(dāng)該函數(shù)滿足半正定性質(zhì)。這里，是X到希爾伯特空間F的一個(gè)特征映射。證明 假設(shè)K(x，z)=(x)，(z)，令Gij=K(xi，xj)=(xi)，(xj)， 其中i，j=1，n對(duì)于任意一個(gè)向量v，我們有,因此函數(shù)K滿足半正定性。反過(guò)來(lái)，假設(shè)K滿足半正定性質(zhì)，通過(guò)構(gòu)造希爾伯特空間內(nèi)的映射，可使K是一個(gè)核函數(shù)。實(shí)際上，特征空間F

9、可以看成原始向量空間中數(shù)據(jù)點(diǎn)的映射的集合(x1)，(x2)，(xn)，這里令(xi)=K(xi，)。根據(jù)這些已知的數(shù)據(jù)，我們可以對(duì)整個(gè)特征空間進(jìn)行預(yù)測(cè)。給定權(quán)系數(shù)ai，整個(gè)特征空間可以表示為,對(duì)該空間中的兩個(gè)元素和作內(nèi)積，得到 其中，n1n，n2n。由上式可知，f，g是實(shí)值、對(duì)稱(chēng)和雙線性的，從而滿足內(nèi)積的性質(zhì)。由于核矩陣K是半正定的，因此，對(duì)于任意的fF,其中是一個(gè)元素為i(i=1，n1)的向量，K是構(gòu)造在x1，x2，xn上的核矩陣。此外，如果記g=K(x，)，則上式可以改寫(xiě)為因此，也有 K(xi，)，K(xj，)=K(xi，xj)上述兩式稱(chēng)為核K的再生性，這樣的核也稱(chēng)為再生核，它仍然具備完備

10、性和可分性兩個(gè)性質(zhì)。因此該函數(shù)是可分的，這里我們省去這一事實(shí)的證明細(xì)節(jié)。給定一個(gè)滿足半正定性質(zhì)的函數(shù)K，我們將對(duì)應(yīng)的空間FK稱(chēng)為它的再生核希爾伯特空間。,定義9.6 再生核希爾伯特空間(ReproducingKernelHilbertSpace，RKHS) 設(shè)X為一非空集合，給定一個(gè)核函數(shù)K，如果它具有再生性，那么由它張成的空間是一個(gè)再生核Hilbert空間。再生核希爾伯特空間上的內(nèi)積操作具有再生特性，是一個(gè)具備完備性和可分性的內(nèi)積空間。在核方法中，Mercer定理通常用來(lái)為有效的核函數(shù)構(gòu)造一個(gè)特征空間。前面我們已經(jīng)分析出核函數(shù)可以通過(guò)構(gòu)造再生核希爾伯特空間來(lái)實(shí)現(xiàn)，為了保證核方法理論的完整性，

11、下面對(duì)Mercer定理進(jìn)行介紹。,(9-7),定理9.2(Mercer定理) 令X是Rq上的一個(gè)緊湊子集，假定K是一個(gè)連續(xù)的對(duì)稱(chēng)函數(shù)，存在積分算子TK：L2(X)L2(X)，使得是正的，也就是說(shuō)，對(duì)于任意的L2(X)，有 上式等價(jià)于K(，),可以表示為XX上的一個(gè)一致收斂序列；其中i是TK的特征值，i是i對(duì)應(yīng)的特征函數(shù)，歸一化使得|i|L2=1，并且i0。,(9-8),(9-9),9.1.3 核函數(shù)的構(gòu)造前面給出的對(duì)核的描述不僅僅可以判定一個(gè)給定的核函數(shù)是否有效，還可以對(duì)一個(gè)或多個(gè)核進(jìn)行運(yùn)算以獲得新的核函數(shù)。下面我們給出與核函數(shù)運(yùn)算有關(guān)的性質(zhì)。引理9.1(封閉性質(zhì)) 令K1和K2是定義在XX上

12、的核，x，aR+，f()是X上的一個(gè)實(shí)值函數(shù)，：XRQ，K3是定義在RqRq上的一個(gè)核，B是一個(gè)qq的半正定對(duì)稱(chēng)矩陣，那么下列函數(shù)都是核：,(1)K(x，z)=K1(x，z)+K2(x，z)(2)K(x，z)=aK1(x，z)(3)K(x，z)=K1(x，z)K2(x，z)(4)K(x，z)=f(x)f(z)(5)K(x，z)=K3(x)，(z)(6)K(x，z)=xTBz證明 令S為一個(gè)有限點(diǎn)集x1，xl，K1和K2是通過(guò)把核函數(shù)K1和K2限制于這些點(diǎn)得到的對(duì)應(yīng)的核矩陣。由前面內(nèi)容可知，對(duì)于任意一個(gè)向量Rm，當(dāng)且僅當(dāng)對(duì)于所有的，有TK0，則矩陣K為半正定的。,(1)對(duì)于所有的，T(K1+K2

13、)=TK1+TK20，所以K1+K2是半正定的，K1+K2是一個(gè)核函數(shù)。(2)類(lèi)似地，TaK1=aTK10，因此aK1是一個(gè)核函數(shù)。(3)令K=K1K2是矩陣K1和K2的張量積，它是通過(guò)用K1中的每一個(gè)元素與K2相乘所得的積去取代K1中原來(lái)的元素得到的。兩個(gè)半正定矩陣的張量積本身也是半正定的，我們將對(duì)應(yīng)于函數(shù)K1K2的矩陣稱(chēng)為K1和K2的Schur積H，其元素是兩個(gè)成分中的對(duì)應(yīng)元素的乘積。因此，對(duì)于任意一個(gè)Rm，存在一個(gè)對(duì)應(yīng)的1Rll，使得,TH=T1K10，因此H是一個(gè)半正定矩陣，K1K2是一個(gè)核函數(shù)。該性質(zhì)說(shuō)明了任何一個(gè)核都可以分解為規(guī)范化的Schur積。(4)考慮一維特征映射：x|f(x

14、)，那么f(x)f(z)就是對(duì)應(yīng)的核。該性質(zhì)說(shuō)明了任何一個(gè)核可以分解為一維核，其中。(5)由于K3是一個(gè)核函數(shù)，通過(guò)把K3限制于點(diǎn)(x1)，(xl)而得到的矩陣是半正定的，因此K3(x)，(z)是一個(gè)核函數(shù)。,(6)已知B是半正定對(duì)稱(chēng)矩陣，利用正交矩陣V可以將矩陣B對(duì)角化，即B=VTV，這里V是一個(gè)對(duì)角矩陣，包含了非負(fù)特征值。令也是一個(gè)對(duì)角矩陣，其元素為特征值的平方根，并設(shè)。因此我們有即利用線性特征空間映射A得到了所需的內(nèi)積。利用這些封閉性質(zhì)我們可以從簡(jiǎn)單的核構(gòu)造出更加復(fù)雜的核。根據(jù)引理9.1，容易證明以下引理。,引理9.2 令K1(x，z)是定義在XX上的核，其中x，zX，那么下列函數(shù)也是核

15、：(1)K(x，z)=+1p(2)K(x，z)=exp(K1(x，z)(3)引理9.2的(1)對(duì)應(yīng)的是多項(xiàng)式核，p為次數(shù)，(2)為指數(shù)核函數(shù)，對(duì)應(yīng)的是高斯核函數(shù)。多項(xiàng)式核和高斯核都是常用的基本核，高斯核用得最為廣泛，高斯核函數(shù)組成了徑向基函數(shù)(RadialBasisFunction，RBF)網(wǎng)絡(luò)的隱藏單位，因此它也被稱(chēng)為RBF核。雖然有許多核函數(shù)可供選擇，但是對(duì)于某個(gè)具體的機(jī)器學(xué)習(xí)任務(wù)，并非所有的核函數(shù)都是合適的選擇。因此，需要根據(jù)具體問(wèn)題來(lái)構(gòu)造相應(yīng)的核。,基于核的模式分析方法有很多，其中包括核HCM算法、核FCM算法、核離散K-L變換、核Fisher線性判別以及支持向量機(jī)，下面對(duì)它們逐一進(jìn)行

16、介紹。,9.2 核HCM算法HCM聚類(lèi)算法是一種基于誤差平方和準(zhǔn)則的聚類(lèi)方法，當(dāng)各類(lèi)樣本的邊界是線性不可分以及類(lèi)分布為非高斯分布時(shí)，其聚類(lèi)性能較差。為了提高HCM算法的性能，可以引入核方法的思想，提出一種核HCM聚類(lèi)算法。該算法的主要思想就是將原空間的樣本映射到高維特征空間，使樣本在該空間中變得線性可分或近似線性可分，然后再利用HCM對(duì)它們進(jìn)行聚類(lèi)。,假設(shè)有n個(gè)待聚類(lèi)樣本x1，x2，xn，聚類(lèi)數(shù)目為c，設(shè)待聚類(lèi)的樣本被劃分成k(k=1，2，c)個(gè)類(lèi)。原樣本集通過(guò)非線性特征映射函數(shù)()，在特征空間中表示為(x1)，(x2)，(xn)。與傳統(tǒng)的HCM算法類(lèi)似，令為第k(k=1，c)類(lèi)的樣本的均值，

17、由下式計(jì)算；其中，nk是第k類(lèi)中樣本的數(shù)目。核HCM聚類(lèi)算法的目標(biāo)函數(shù)可以寫(xiě)為,(9-10),(9-11),在核空間中，任意一個(gè)樣本(xi)和第k類(lèi)的樣本的均值之間的距離可以展開(kāi)為,(9-12),一般情況下，非線性映射函數(shù)的表達(dá)式是未知的。這里我們不需要真正使用映射，而是利用滿足Mercer條件的核函數(shù)計(jì)算高維特征空間上的內(nèi)積，即K(x，z)=(x)，(z)，可以將式(9-12)進(jìn)一步化簡(jiǎn)得到：從上式可以看出，高維特征空間上的樣本與聚類(lèi)中心之間的距離可以通過(guò)計(jì)算原始空間樣本之間的核函數(shù)值得到，具體的核函數(shù)可以采用引理9.2中介紹的三種常用的核函數(shù)。,(9-13),根據(jù)上面給出的聚類(lèi)準(zhǔn)則(參考式

18、(9-11)和式(9-13)，核HCM算法的流程如下：步驟1：給定聚類(lèi)數(shù)目c，以及允許誤差和最大迭代次數(shù)T，并確定一種聚類(lèi)過(guò)程中使用的核函數(shù)形式。步驟2：對(duì)原始樣本集隨機(jī)初始化c個(gè)聚類(lèi)中心或者一個(gè)聚類(lèi)結(jié)果。這里以初始化聚類(lèi)中心為例，即在原始樣本集中任意選擇c個(gè)樣本作為初始聚類(lèi)中心。步驟3：設(shè)置迭代次數(shù)t=1，利用式(9-11)和式(9-13)計(jì)算核HCM聚類(lèi)算法的目標(biāo)函數(shù)值。,步驟4：根據(jù)式(9-13)計(jì)算每個(gè)樣本(xi)與中心的距離，并根據(jù)最近鄰原則將該樣本分配到與它距離最近的那個(gè)類(lèi)中。步驟5：獲得每個(gè)樣本的新的類(lèi)別標(biāo)簽之后，t=t+1，重新計(jì)算目標(biāo)函數(shù)值。步驟6：判斷算法是否達(dá)到最大迭代次

19、數(shù)T或者，如果滿足條件,則算法停止，否則轉(zhuǎn)至步驟4。,盡管這種算法很流行，但是由于其聚類(lèi)準(zhǔn)則的最優(yōu)化問(wèn)題是非凸的，很容易陷入局部極小值，為此，研究者試圖通過(guò)尋找更好的初始聚類(lèi)結(jié)果，或者引入額外的約束條件來(lái)提高算法性能。此外，核函數(shù)的選取對(duì)該算法的性能也具有一定的影響。對(duì)于這些方面的研究，這里就不再一一贅述。,9.3 核FCM算法與核HCM方法類(lèi)似，核模糊c-均值聚類(lèi)算法也是將數(shù)據(jù)通過(guò)核函數(shù)映射到高維特征空間后再進(jìn)行FCM聚類(lèi)，一定程度上克服了FCM不適合多種數(shù)據(jù)分布的缺陷。若樣本集為X=x1，x2，xn，c為聚類(lèi)個(gè)數(shù)，vj(j=1,2,c)為第j個(gè)聚類(lèi)的聚類(lèi)中心，通過(guò)非線性特征映射，將FCM的

20、目標(biāo)函數(shù)修改為高維特征空間下的目標(biāo)函數(shù)：,(9-14),uij必須滿足： 式中：n為樣本數(shù)，U=uijcn是模糊劃分矩陣，uij為樣本(xi)對(duì)應(yīng)于第j個(gè)聚類(lèi)的隸屬度值，m是影響隸屬度矩陣模糊化程度的指數(shù)權(quán)重。在高維特征空間中，將歐式距離|(xi)(vj)|2展開(kāi)，得到,(9-15),(9-16),對(duì)于每一個(gè)只使用內(nèi)積的線性算法來(lái)說(shuō)，都可以利用滿足Mercer條件的核函數(shù)把該算法擴(kuò)展成一個(gè)非線性版本。這里，我們不需要真正使用變換，而是利用核函數(shù)K(x，y)計(jì)算高維空間中樣本的內(nèi)積。因此，式(9-16)可以被改寫(xiě)為如果采用高斯核,(9-17),(9-18),作為核函數(shù)，則有 最終，KFCM的目標(biāo)

21、函數(shù)整理為 分別對(duì)JKFCM關(guān)于uij、vj求偏導(dǎo)，得到新的聚類(lèi)中心和隸屬度矩陣的更新公式：,(9-19),(9-20),(9-21),核模糊c-均值聚類(lèi)算法的具體步驟為：步驟1：給定聚類(lèi)數(shù)目c(2cn)，閾值，最大迭代次數(shù)T，加權(quán)指數(shù)m。步驟2：初始化聚類(lèi)中心，,設(shè)置迭代次數(shù)k=1。步驟3：利用式(9-22)計(jì)算隸屬度，i=1，2，n;j=1，2，c。,(9-22),步驟4：利用式(9-21)計(jì)算聚類(lèi)中心，j=1，2，c。步驟5：如果|V(k+1)V(k)|T，則算法結(jié)束，輸出最終聚類(lèi)結(jié)果；否則，k=k+1，執(zhí)行步驟3。核FCM算法與核HCM算法類(lèi)似，也容易出現(xiàn)局部極小化的問(wèn)題。人們?cè)O(shè)計(jì)了很

22、多方法來(lái)提高算法的性能，由于這些已經(jīng)超出了本書(shū)的內(nèi)容，這里就不再贅述。,9.4 核離散K-L變換在7.3節(jié)中討論的離散K-L變換是在最小均方誤差準(zhǔn)則下，找到一個(gè)d維子空間，使其能夠很好地表達(dá)原始數(shù)據(jù)。如果原始數(shù)據(jù)存在復(fù)雜的非線性關(guān)系，那么線性子空間的表示性能將很差。為了使離散K-L變換方法能夠處理非線性問(wèn)題，將核方法的思想引入進(jìn)來(lái)，得到核離散K-L變換方法。,已知原始樣本集X=x1，x2，xn，xi是q維的向量，利用非線性特征映射，得到高維特征空間的樣本(xi)(i=1，2，n)，(xi)RQ。假設(shè)在該高維空間中，樣本集的均值為，可以利用高維特征空間上的樣本集的協(xié)方差矩陣對(duì)樣本進(jìn)行離散K-L變

23、換。協(xié)方差矩陣采用下式表示：,(9-23),C為大小是QQ的矩陣。此時(shí)，與第7章中的式(7-42)的推導(dǎo)類(lèi)似，高維特征空間上的離散K-L變換就是通過(guò)求解Cw=w (9-24)來(lái)獲得w，從而得到高維特征空間上的最佳投影方向。這里，首先將高維特征空間中的每個(gè)樣本與上式的等號(hào)左右兩端做內(nèi)積，則有 由再生核理論可知，給定權(quán)系數(shù)i，高維特征空間中的所有向量都可以表示為,(9-25),(9-26),整理式(9-23)、式(9-25)和式(9-26)，可得 定義一個(gè)QQ核矩陣K=Kij，其中，則式(9-27)可簡(jiǎn)化為 nK=K2 (9-29)可以看出，n=K (9-30)的解也必然滿足式(9-29)中的等式

24、關(guān)系。,(9-27),(9-28),通過(guò)對(duì)核矩陣K進(jìn)行特征分解，可以獲得要求的特征值和特征向量。由式(9-26)可知，利用核矩陣K的特征向量=(1)，(2)，(Q)可以求出C的特征向量w，從而得到高維特征空間的投影方向。這里，用12Q表示核矩陣K的特征值，(1)，(2)，(Q)為對(duì)應(yīng)的特征向量，選擇前l(fā)個(gè)最大的非零特征根1，2，l及其特征向量(1)，(2)，(l)。根據(jù)式(9-26)，可以得到,， k=1，l(9-31),因此可以利用如下公式來(lái)計(jì)算新數(shù)據(jù)在w構(gòu)成的l維子空間上的投影；其中x為原始空間的輸入向量，(x)為高維空間的映射向量。因此，利用核矩陣計(jì)算(xj)，(x)可以得到在高維特征空

25、間上特征提取的結(jié)果；,(9-32),9.5 核Fisher線性判別我們?cè)?.5節(jié)已經(jīng)介紹了Fisher線性判別的基本內(nèi)容，F(xiàn)isher線性判別所要解決的基本問(wèn)題是找到一個(gè)最好的投影方向，使樣本在這個(gè)方向上的投影最容易分開(kāi)。顯然，對(duì)于大多數(shù)的實(shí)際數(shù)據(jù)，線性判別分析的方法顯得過(guò)于簡(jiǎn)單。為了增加判別函數(shù)的表達(dá)性，可以引入核方法，先把數(shù)據(jù)非線性地映射到某個(gè)高維特征空間，然后在這個(gè)特征空間中進(jìn)行Fisher線性判別，這就是核Fisher線性判別法。,下面以兩類(lèi)問(wèn)題為例來(lái)對(duì)核Fisher線性判別法進(jìn)行介紹。已知n個(gè)q維樣本x1，x2，xn，其中i(i=1，2)為第i類(lèi)對(duì)應(yīng)的樣本集，樣本容量為ni。設(shè)經(jīng)過(guò)一

26、個(gè)非線性映射，將輸入空間的數(shù)據(jù)xi映射到高維特征空間中的(xi)，則在高維特征空間中各類(lèi)樣本的類(lèi)內(nèi)離散度矩陣和總的類(lèi)內(nèi)離散度矩陣分別為：,i=1，2 (9-33),(9-34),其中，(i=1，2)為在高維空間的第i類(lèi)樣本的均值向量。類(lèi)間離散度矩陣定義為由式(9-33)和式(9-35)知，和均為對(duì)稱(chēng)半正定矩陣。為了在高維特征空間上進(jìn)行Fisher線性判別分析，需要給出特征空間上的Fisher判別準(zhǔn)則函數(shù)，與第2章中Fisher準(zhǔn)則函數(shù)的推導(dǎo)類(lèi)似，可以得到；,(9-35),(9-36),其中，W為任一非零列向量。使J(W)達(dá)到最大值的W即為最佳投影方向W*。由于無(wú)法給出有效的非線性映射函數(shù)并且特

27、征空間的維數(shù)也是非常高甚至是無(wú)窮維的，直接求解最優(yōu)投影方向是不可能的。由再生核理論可知，高維特征空間中的任何一個(gè)向量W可以表示為根據(jù)式(9-37)和均值向量的定義，得到下面形式；,(9-37),(9-38),其中，=(1，2，n)T，。將上式引入到的定義中，則有其中，KB=(K1-K2)(K1-K2)T。同理，將式(9-38)引入到中，將其修改為,(9-39),(9-40),其中，Ki表示第i類(lèi)的核矩陣，其中(Ki)jk=K(xj，xk)，xki。I為單位矩陣，為元素全部為1/ni的矩陣。,此時(shí)，可以將高維特征空間上的Fisher判別準(zhǔn)則函數(shù)修改為上式即為核Fisher判別的準(zhǔn)則函數(shù)。類(lèi)似于F

28、isher線性判別方法，可以通過(guò)求矩陣的最大的l個(gè)特征值及其對(duì)應(yīng)的特征向量(1)，(2)，(l)來(lái)求解核Fisher判別準(zhǔn)則函數(shù)的最大化問(wèn)題。此時(shí)新樣本y到W的投影可以采用下式計(jì)算；,(9-41),(9-42),核Fisher判別方法是一種基于Fisher線性判別的非線性分類(lèi)方法，無(wú)須通過(guò)非線性映射函數(shù)將數(shù)據(jù)映射到高維特征空間，只需要計(jì)算訓(xùn)練樣本的核矩陣即可。此外，不同形式的核由于其可能的非線性范圍很廣，因而具有很高的靈活性。,9.6 支持向量機(jī)支持向量機(jī)(Support Vector Machine，SVM)是數(shù)據(jù)挖掘的一項(xiàng)新技術(shù)，是借助于最優(yōu)化方法解決機(jī)器學(xué)習(xí)問(wèn)題的新工具。該方法以結(jié)構(gòu)風(fēng)險(xiǎn)

29、最小化(Structure RiskMinimization，SRM)為原則，是由Vapnik等人在統(tǒng)計(jì)學(xué)理論的基礎(chǔ)上提出的，該算法在有限個(gè)訓(xùn)練樣本的學(xué)習(xí)精度和泛化能力之間取得了很好的平衡，從而獲得了很好的推廣能力?，F(xiàn)在經(jīng)常使用的包括線性的和非線性的SVM算法，其中線性SVM也分為線性可分和線性不可分兩種情況。最初SVM方法是從線性可分情況下提出的，然而現(xiàn)實(shí)生活中很多問(wèn)題不能用線性函數(shù)來(lái)表示，因此非線性支持向量機(jī)方法得到了很好的推廣和使用。,在SVM方法中，為了解決非線性問(wèn)題，核方法被巧妙地引入進(jìn)來(lái)，使得SVM在獲得良好的泛化性能的同時(shí)，也有效地解決了經(jīng)典學(xué)習(xí)方法中過(guò)學(xué)習(xí)、維數(shù)災(zāi)難、局部極小等

30、問(wèn)題，其復(fù)雜度與樣本維數(shù)無(wú)關(guān)。正是由于這些優(yōu)點(diǎn)，使得支持向量機(jī)獲得了廣泛的關(guān)注，并在手寫(xiě)體識(shí)別、語(yǔ)音辨識(shí)、人臉檢測(cè)、文本分類(lèi)、DNA和蛋白質(zhì)數(shù)據(jù)分析等方面得到了廣泛應(yīng)用。,9.6.1 線性支持向量機(jī)1.線性可分在支持向量機(jī)中最早是從線性可分情況下的最優(yōu)分類(lèi)超平面提出的，基本思想如圖9.2所示。圖中實(shí)心點(diǎn)和空心點(diǎn)分別表示兩類(lèi)不同的樣本，H為將兩類(lèi)數(shù)據(jù)沒(méi)有錯(cuò)誤地分開(kāi)的最優(yōu)分類(lèi)線，H1和H2分別為過(guò)兩類(lèi)樣本中離分類(lèi)超平面最近的點(diǎn)且平行于分類(lèi)線的直線，H1和H2之間的距離叫做分類(lèi)間隔。所謂最優(yōu)分類(lèi)線(在多維空間稱(chēng)為最優(yōu)分類(lèi)超平面)就是要求分類(lèi)線不但能將兩類(lèi)正確分開(kāi)，還要保證分類(lèi)間隔最大?？梢钥闯?最優(yōu)

31、分類(lèi)線或者最優(yōu)分類(lèi)超平面所要求的第一個(gè)條件，就是將兩類(lèi)數(shù)據(jù)無(wú)錯(cuò)誤的分開(kāi)，即保證經(jīng)驗(yàn)風(fēng)險(xiǎn)最小；第二個(gè)條件是使分類(lèi)間距最大，即使推廣能力的界的置信區(qū)間最小，從而使真實(shí)風(fēng)險(xiǎn)最小。,圖9.2 支持向量機(jī)原理示意圖,假設(shè)已知n個(gè)線性可分的觀測(cè)樣本x1，x2，xn，xiRq，對(duì)于兩類(lèi)問(wèn)題，定義樣本xi的類(lèi)別標(biāo)記為yi，即若xi1，則yi=1若xi2，則yi=1于是所有的觀測(cè)樣本集可以表示為(xi，yi)。由于觀測(cè)樣本是線性可分的，因此正確分類(lèi)的界面H可以表示為wTx+b=0(9-43)對(duì)于給定的訓(xùn)練樣本集，通過(guò)學(xué)習(xí)可以確定適當(dāng)?shù)臋?quán)向量w和閾值b來(lái)建立分類(lèi)界面。圖9.2中給出的線性可分的例子中，能將這組樣本

32、分開(kāi)的線性超平面很多，但是分類(lèi)間隔最大的超平面只有一個(gè)。,定義9.7(分類(lèi)間隔) 設(shè)超平面g(x)=wTx+b=0能將正負(fù)樣本分開(kāi)，且使得正樣本滿足g(x)=wTx+b1；負(fù)樣本滿足g(x)=wTx+b-1。其中w是一個(gè)垂直于超平面的權(quán)向量，b為閾值，一個(gè)超平面完全可以由其參數(shù)(w，b)決定。定義滿足條件min|wTxi+b|=1，i=1，n(9-44)的超平面為規(guī)范超平面，對(duì)于線性可分的樣本x，滿足下面的不等式：yi(wTxi+b)1，i=1，2，n9-45)此時(shí)，分類(lèi)間隔等于2/|w|。,能夠?qū)⒂?xùn)練樣本正確分類(lèi)，并且|w|最小的分類(lèi)面就是最優(yōu)分類(lèi)面。滿足|wxi+b|=1的樣本點(diǎn)，我們稱(chēng)之

33、為支持向量，它們離分類(lèi)線(或平面)的距離最小，決定了最優(yōu)分類(lèi)線(或平面)。在圖9.2中，用圓圈標(biāo)出的點(diǎn)即為支持向量。最優(yōu)分類(lèi)超平面要求分類(lèi)間隔最大，即等價(jià)于使|w|最小。為求最優(yōu)分類(lèi)面，可以利用拉格朗日優(yōu)化方法來(lái)求解函數(shù)在條件式(9-45)約束下的最小化問(wèn)題。為此，得到拉格朗日函數(shù),(9-46),其中，i0是拉格朗日乘子。為求該式的最小值，我們分別求上式對(duì)w和b的偏導(dǎo)數(shù)并令它們等于0，計(jì)算得 根據(jù)拉格朗日函數(shù)的二元性，將上述最優(yōu)分類(lèi)面問(wèn)題轉(zhuǎn)化為對(duì)偶問(wèn)題。將上式代入原拉格朗日函數(shù)式(9-46)，得到,和,(9-47),(9-48),其中，i為與每個(gè)樣本對(duì)應(yīng)的拉格朗日乘子。因此在約束條件下，權(quán)向量

34、就實(shí)現(xiàn)了分類(lèi)間隔最大。通過(guò)分析可知，只有那些最靠近超平面的點(diǎn)對(duì)應(yīng)的才非零，這樣的樣本就是支持向量。b*可以由任一xi用式(9-45)取等號(hào)時(shí)求解，即b*=yiw*Txi。通過(guò)對(duì)上述問(wèn)題的求解，最終得到相應(yīng)的判別函數(shù)是 sgn()為符號(hào)函數(shù)，進(jìn)而得到x的所屬類(lèi)別。,(9-49),2.線性不可分最優(yōu)分類(lèi)面是在線性可分的前提下討論的，但是在現(xiàn)實(shí)世界中許多問(wèn)題是不能用線性的方法來(lái)解決的。針對(duì)線性不可分的情況，可以增加松弛變量i，將約束條件放寬變成yiwTxi+b1+i0 i0，i=1，2，n) (9-50i=0是指那些位于H1和H2兩條線之外且分類(lèi)正確的向量的約束條件?，F(xiàn)在的任務(wù)仍然是求出分類(lèi)間隔最大

35、，且滿足使得i0的向量盡量少的最優(yōu)分類(lèi)面，這里稱(chēng)為廣義最優(yōu)分類(lèi)面。此時(shí)增加松弛變量的目標(biāo)函數(shù)為,其中，C是一個(gè)用來(lái)控制錯(cuò)分樣本數(shù)目的懲罰參數(shù)，C的值越小，對(duì)離群點(diǎn)的懲罰就越小，界面間隔越寬。由式(9-50)和式(9-51)可得到對(duì)應(yīng)的拉格朗日函數(shù)為,(9-51),(9-52),同前面求最優(yōu)分類(lèi)面解法相同，分別求上式對(duì)w、b和的偏導(dǎo)并令它們等于零，得到；由非負(fù)條件i0，可將式(9-55)修改為Ci0 i=1，2，n (9-56) 從該式中也可以看出，C控制了i的大小，因而控制了噪聲和離群點(diǎn)的影響。,(9-53),(9-54),(9-55),將上面得到的等式代入原拉格朗日函數(shù)中，可以對(duì)下面的目標(biāo)函數(shù)進(jìn)行優(yōu)化：解得的可以得到廣義最優(yōu)分類(lèi)面；這里b*需滿足yjg(xj)=1。此外，參數(shù)C選取的典型方法是在一定范圍內(nèi)試驗(yàn)，直到找到特定的訓(xùn)練集最好的參數(shù)為止。,(9-57),(9-58),9.6.2