[計算機(jī)軟件及應(yīng)用]第4講 基于判別函數(shù)的分類方法ppt課件

1、第第4講講 基于判別函數(shù)的分類方基于判別函數(shù)的分類方法法點到平面的間隔 公式222000CBADCzByAxd點 x0, y0, z0 到平面 Ax+By+Cz+D=0的間隔 為：內(nèi)積和向量空間x和y的內(nèi)積點積定義為假如xT y=0，那么x和y是正交的.向量的模定義為 niiiTTyx1xyyxyx，2112niiTxxxx要點:什么是判別函數(shù)線性判別函數(shù)高階判別函數(shù)兩類情況下的線性判別函數(shù)多類情況下的線性判別函數(shù)課堂練習(xí)，課后作業(yè)什么是判別函數(shù)設(shè)有c個類別，對每個類別ii=1,2,c定義一個關(guān)于特征向量X的單值函數(shù)giX, 假如giX滿足： 返回1.假如X屬于第i類，那么：2.假如X在第i類

2、和第j類的分界面上，那么：ijcjiXgXgji,.,2 , 1,),()(ijcjiXgXgji,.,2 , 1,),()(線性判別函數(shù)線性判別函數(shù)的定義線性判別函數(shù)的簡潔形式線性判別函數(shù)的增廣形式線性判別函數(shù)的作用線性判別函數(shù)舉例:例1, 例2,例3返回線性判別函數(shù)的定義最簡單的判別函數(shù)是線性判別函數(shù)，它是所有形式特征的線性組合。對于第i類形式，它有如下的形式：式中i=1,2,c, wik是特征的系數(shù)，稱為權(quán)weight，wi0稱為閾值權(quán)threshold weight或偏置bias，而- wi0 通常被稱為閾值。在線性判別函數(shù)中，每個特征所作的奉獻(xiàn)是不一樣的，奉獻(xiàn)的大小就是它的權(quán)。返回0

3、221101.)(ininiiinkkikiwxwxwxwwxwXg線性判別函數(shù)的簡潔形式假如對第i類形式定義n維權(quán)向量為：那么線性判別函數(shù)可寫成更簡潔的形式：其中i=1,2,c返回TiniiiwwwW),.,(210)(iTiiwXWXg線性判別函數(shù)的增廣形式分別定義增廣形式向量和廣義權(quán)向量：那么線性判別函數(shù)可以寫成增廣形式：增廣形式的線性判別函數(shù)是n+1維空間的齊次線性函數(shù)。 返回XxxxYTn1),., 1 (21TiniiiwwwA),.,(10YAYgTii)(線性判別函數(shù)的作用線性判別函數(shù)可以提供超平面作為形式類的分界面線性判別函數(shù)linear discriminant funct

4、ion超平面hyperplane返回線性判別函數(shù)舉例1g1 (x1, x2)= x1g2 (x1, x2)= x2x1x2返回線性判別函數(shù)舉例2g1 (x1, x2)= x1g2 (x1, x2)= -x2x1x2返回線性判別函數(shù)舉例3返回高階判別函數(shù)二次判別函數(shù) quadratic discriminant function多項式判別函數(shù) polynomial discriminant function廣義線性判別函數(shù)generalized linear discriminant function返回二次判別函數(shù)判別函數(shù)不一定是線性的，例如，在線性判別函數(shù)上加上wijxixj項，就得到二次判

5、別函數(shù)： 其中xlxm=xmxl 。 返回二次判別函數(shù)可以提供超二次曲面hyperquadric surface作為形式類的分界面，其中包括超球hypersphere、超橢球hyperellipsoid和超雙曲面hyperboloid。 dkdlidmmllmkikiwxxwxwXg1101)(多項式判別函數(shù)假如給二次判別函數(shù)參加更高次的項，比方wijkxixjxk，就可得到多項式判別函數(shù)。多項式判別函數(shù)可以提供更復(fù)雜的超曲面作為形式類的分界面，但系數(shù)會增加許多，求解比較困難。所以通常盡量采用線性判別函數(shù)，以及由它派生的分段線性判別函數(shù)。返回廣義線性判別函數(shù)假如判別函數(shù)gx可以分解為假設(shè)干分量

6、函數(shù)yix的線性組合，即：那么gx稱為廣義線性判別函數(shù)舉例返回YATdiiixyaxg1)()(廣義線性判別函數(shù)舉例返回YATxaxaaxg2321)(23211,xxaaaYA兩類情況下的線性判別函數(shù)兩類線性判別函數(shù)的決策面兩類線性判別函數(shù)的決策法那么兩類形式的線性分類器兩類線性決策面的幾何解釋兩類線性決策面的求解方法返回兩類線性判別函數(shù)的決策面兩類線性判別函數(shù)的簡化兩類線性決策面方程返回兩類線性判別函數(shù)的簡化在只有兩類形式的情況下，c=2, 容易得到兩個線性判別函數(shù)，即：兩式相減得:其中返回1011)(wXWXgT2022)(wXWXgT021)()()(wXWXgXgXgT2010021

7、,wwwWWW兩類線性決策面方程兩類形式的分界面由下式?jīng)Q定:上式稱為兩類線性決策面方程，它所決定的點集稱為兩類線性決策面。返回00)(0wXWXgT兩類線性判別函數(shù)的決策法那么假如gX0, 那么決策1，即把X歸到1類；假如gX0, 那么決策2，即把X歸到2類； 當(dāng)權(quán)向量W和形式向量X的內(nèi)積超過閾值w0時，就把X歸到1類，否那么就歸到2類。返回兩類形式的線性分類器返回Xg(X)-1+1+1 X11 X2x1w1x2w2xnwn+1w0X兩類線性決策面的幾何解釋決策面的幾何意義決策面的法向量決策面的正面和反面判別函數(shù)值的幾何意義返回決策面的幾何意義兩類線性決策面gX=0，對于二維空間情況，它是一條

8、直線，對于三維空間情況，它是一個平面，而對于高維空間的情況，那么是一個超平面。返回決策面的法向量對于決策面上的任意兩個點X1和X2，都有：即見示意圖1，示意圖2這說明權(quán)向量W和決策面上的任一向量X2X1正交,也就是說權(quán)向量的方向就是法線的方向。 返回0201wXWwXWTT0)(12 XXWT示意圖1返回Xpx1x2R1R2g(X)=0g(X)0Ww0WXg)(X1X2示意圖2返回決策面的正面和反面在兩類形式的情況下，線性決策面把形式空間分成兩個半空間，即對1的決策域R1和對2的決策域R2。當(dāng)特征向量X在R1中時gX0，所以決策面的法線方向指向R1。我們稱R1位于決策面的正面，R2位于決策面的

9、反面。返回 判別函數(shù)值的幾何意義判別函數(shù)值gX是一點X到?jīng)Q策面H的間隔 的度量?？梢园严蛄縓表示為：其中Xp是H上的一點，向量XpX是H的法線方向；是待求的間隔 ，它是一個代數(shù)量，當(dāng)X在H的正面時它為正，X在H的反面時它為負(fù)。 返回WWXXp的計算因為Xp在決策面上，所以gXp=0，從而可以得出：所以：由此可計算出原點到?jīng)Q策面的間隔 000()()()()TTpTTTppWg XW XWWXWWW WW WW XWg XWWWWXg)(原點到?jīng)Q策面的間隔 令X為原點，可求得原點到?jīng)Q策面H的間隔 為：假如w00，那么原點在H的正面；假如w00 。解: 令 ，k =1，用梯度下降算法得易知A1Yi

10、0，所以A=A1 。 返回01,11,21321YYY000A33321010YYYYAAAY梯度下降算法的收斂性只要兩類樣本是線性可分的，那么求解線性不等式組的梯度下降法總是收斂的。返回梯度下降算法的缺點每次迭代必須遍歷全部樣本，才能得到當(dāng)前權(quán)向量Ak下的誤分類樣本集返回kA固定增量算法與梯度下降算法的關(guān)系什么是固定增量算法固定增量算法舉例固定增量算法的幾個問題固定增量算法的收斂性定理固定增量算法的收斂性證明返回與梯度下降算法的關(guān)系通過對梯度下降算法作如下兩點改變，可以得到固定增量算法：1. 把全部樣本看作是一個序列，每當(dāng)前一步迭代的權(quán)向量把某個樣本錯誤分類時，就對這個權(quán)向量作一次修正。2.

11、考慮每次迭代時保持k不變，即乘上一個固定的比列因子。例如，k =1。返回什么是固定增量算法設(shè) 是兩類增廣形式向量樣本集 令k =1，A0為零向量。把 的樣本Y依次取出，Ak+1用以下規(guī)那么調(diào)整：返回假如 ，而 ，那么Ak+1=Ak+Y；假如 ，而 ，那么Ak+1=AkY；假如 ，而 ，那么Ak+1=Ak；假如 ，而 ，那么Ak+1=Ak；*2*1RR 和*2*1RR 和*1RY 0YATk*2RY *2RY *1RY 0YATk0YATk0YATk固定增量算法舉例三維二值向量樣本集：試用固定增量算法求出解向量。 返回求解過程分三步：1.構(gòu)造增廣形式向量；2.選擇初始廣義權(quán)向量；3.利用固定增量

12、算法迭代計算。;010,011;110,10121RR構(gòu)造增廣形式向量首先把樣本集 R1和 R2中的全部成員都變成增廣形式向量。從而得到增廣形式向量集：返回;0101,0111;1101,1011*2*1 RR選擇初始廣義權(quán)向量令初始廣義權(quán)向量為：返回00000A迭代計算過程返回迭代次數(shù)kY結(jié)果權(quán)向量Ak+110, +2, +2, 12+1, 0, +1, 13+1, +1, 2, 1YATk0101,0111,1101,10110101,0111,1101,10110101,0111,1101,10111100,1100,1011,10112110,2110,2001,11002110,21

13、10,2110,2110固定增量算法的幾個問題什么是迭代? 什么是收斂?形式必須是二值的嗎？執(zhí)行迭代時, 對 中成員的次序有何要求？ 中必須有相等數(shù)量的形式嗎？初始廣義權(quán)向量的選擇有何要求？ 返回*2*1RR 和*2*1RR 和什么是迭代屬于 的全部形式向量都用調(diào)整規(guī)那么處理一遍，稱為一次迭代。返回*2*1RR 和什么是收斂重復(fù)迭代過程，直到權(quán)向量Ak不再變化時為止，這時Ak收斂為解向量。假如 不是線性可分的，那么迭代過程不會收斂，將無限進(jìn)展下去，所以在編制程序時應(yīng)考慮或在一定時間限度內(nèi)停頓，或當(dāng)Ak在一個不收斂區(qū)域內(nèi)循環(huán)而停頓。 返回*2*1RR 和固定增量算法的收斂性定理假如增廣形式向量樣

14、本集 是線性可分的，那么固定增量算法一定收斂。返回*2*1RR 和固定增量算法的收斂性證明固定增量算法的規(guī)格化關(guān)于解向量的假設(shè)收斂性證明的關(guān)鍵收斂性的證明校正次數(shù)的估算返回固定增量算法的規(guī)格化用一個樣本集R來代替 ，方法如下：針對R的固定增量算法為：對YR，假如 ，那么Ak+1=Ak+Y； 否那么Ak+1=Ak。返回 *2*1RR 和*2*1|RYRYYR或0YATk關(guān)于解向量的假設(shè)由于樣本集是線性可分的，所以存在這樣一個解權(quán)向量 ，使得對于所有的YR，有：從而對任意0， 因此 也都是解向量。返回A0YAT0)(YATA收斂性證明的關(guān)鍵假如在第k步迭代時進(jìn)展校正，那么存在兩個正數(shù)和，使得因為此

15、時 ， 所以返回2221AAAAkk0YATk222222212)(2AAAAYYAAAAAAkkTkkkYAAkk1和的構(gòu)造方法令為形式向量的最大長度，即：令為解向量與形式向量的最小內(nèi)積，即：假如選擇 ，那么可滿足要求。返回22max YRY0minYATRY/2收斂性的證明假如第k步時進(jìn)展了m次校正，那么有:所以經(jīng)過m0次校正后校正將終止，其中 返回 校正終止意謂著Ak使R中所有樣本正確分類， Ak將不再發(fā)生變化，從迭代收斂。2202mAAAAk2200AAm校正次數(shù)的估算假如令初始向量A0為零向量，那么所以當(dāng)解向量與某個樣本的內(nèi)積非常小時，求解將非常困難。返回2222200minmaxA

16、YAYAAmTRYRY感知器算法設(shè)原樣本為Xi,類別yi = 1R=max|Xi|,1iN, h=1學(xué)習(xí)率W0 =0,b0 =0If yiWkXi+bk 0, then Wk+1=Wk+hyi Xi bk+1=bk+hyi R2校正次數(shù): 2R/d 2 , d為兩類最小間隔返回支持向量機(jī) 返回最小平方誤差方法求解線性不等式組的一種新思路平方誤差準(zhǔn)那么函數(shù)線性方程組的MSE解，舉例Widrow-Hoff算法或 最小均方算法least-mean-squared, LMSLMS解與分隔超平面的關(guān)系返回求解線性不等式組的一種新思路求解線性不等式組 可以通過下述求解線性方程組來實現(xiàn):或其中返回NiYAi

17、T,.,2, 1,0NibAYiTi,.,2, 1,BA Y),.,(,),.,(, 02121NTNibbbBYYYbY平方誤差準(zhǔn)那么函數(shù)平方誤差準(zhǔn)那么函數(shù)定義為其中誤差向量為返回212)()(iNiiTsbYABAAJYBAe Y線性方程組的MSE解JsA取極小值的必要條件是:即:假如 是非奇異的，那么可得MSE解：其中 。 返回NiTiiiTsBAYbYAJ1)(2)(20YYBATTYYYYYTBBATTYYYY1)(TTYYYY1)(關(guān)于MSE解的進(jìn)一步說明MSE解是惟一的。 返回 稱為Y的偽逆矩陣雖然 ，但通常Y+可以被定義為更一般的形式：該極限總存在，且 是 的解MSE解總是存在

18、的，不管樣本是否可分。TTYYYY1)(IYYIYY TTYIYYY10)(limBAYBA YMSE解舉例給定兩類二維樣本如下：示意圖試用MSE解構(gòu)造線性分類器求解過程及結(jié)果返回32,13,02,2121示意圖返回求解過程及結(jié)果構(gòu)造Y矩陣并計算Y的偽逆矩陣:令 ，可得到一個MSE解為選擇不同的B，將得到不同的A。 返回321131021211Y3/103/106/12/16/12/112/74/312/134/5)(1TTYYYYTB)1 , 1 , 1 , 1 (TBA)3/2, 3/4, 3/11(YWidrow-Hoff算法又稱為最小均方算法，計算過程如下：1.任意選擇初始向量A0 和

19、初始步長00;2.迭代計算： 其中 ， 當(dāng) 時停頓。返回)(1kTkkkABAAYYkk/0kkAA1LMS解與分隔超平面的關(guān)系LMS解將訓(xùn)練點到超平面點的間隔 平方和最小化，未必收斂于分隔超平面，即使這個平面存在。 返回多類情況下的線性判別函數(shù)轉(zhuǎn)化為兩類問題求解直接按多類問題求解返回轉(zhuǎn)化為兩類問題求解設(shè)有c類形式，分別記為i i=1,2,c，利用兩類情況下的線性判別函數(shù)設(shè)計分類器，通常有三種處理方法:第一種方法，舉例第二種方法，舉例第三種方法，舉例返回第一種方法把c類問題化為c1個兩類形式的分類問題，即：1為一類， 2, 3, c為另一類2為一類， 3, 4, c為另一類c-1為一類，c為另

20、一類返回第一種方法舉例R1R2R3返回第二種方法把c類問題化為c1個兩類形式的分類問題，即：1為一類， 2, 3, c為另一類2為一類， 1, 3, 4, c為另一類c-1為一類，1, 3, , c-2, c為另一類返回第二種方法舉例R1R2R3返回第三種方法用 次兩類形式線性判別，每一次只從樣本集中判別指定的兩類形式的決策面，比方i為一類，j為另一類。返回2) 1(2ccCc第三種方法舉例R1R3R2返回直接按多類問題求解什么是線性機(jī)器線性機(jī)器的決策面線性機(jī)器的決策域多類樣本的線性可分多類問題的增廣解向量多類問題的固定增量算法返回什么是線性機(jī)器線性機(jī)器是一種多類分類器，它通過c個線性判別函數(shù)

21、來對樣本分類，分類規(guī)那么是： 假如對所有 都有 ，就將X歸為i類。返回ciwXWXgiTi,.,2 , 1,)(0)()(XgXgjiij 線性機(jī)器的決策面假如線性機(jī)器把特征空間分成c個決策區(qū)域R1, R2, Rc，那么Ri和Rj相交的部分是超平面Hij的一部分，稱為決策面。 Hij的方程如下：不難看出決策面最多有 個。決策面舉例：例1，例2。 返回)()(XgXgji2) 1( cc決策面舉例13類3個決策面。 返回R1R2R3決策面舉例25類8個決策面。 返回R1R2R3R4R5線性機(jī)器的決策域所有決策域是凸的每個決策域都是單連通的不存在回絕分類的死區(qū)返回多類樣本的線性可分設(shè)有一個增廣形式向量樣本集Y1,Y2,YN，共有N個樣本；其中有n1個屬于1的樣本集合記為1，有n2