考試說明

注重基礎(chǔ)知識和概念的理解剂陡，因此解題中的計(jì)算過程不會很復(fù)雜狈涮，但是會有推公式的過程。本課程的重點(diǎn)知識包括：貝葉斯決策鸭栖、概率密度估計(jì)歌馍、參數(shù)法、非參數(shù)法晕鹊、線性分類器設(shè)計(jì)松却、神經(jīng)網(wǎng)絡(luò)、支撐向量機(jī)溅话、聚類分析晓锻、特征提取和選擇。

參考資料：

• 《機(jī)器學(xué)習(xí)》周志華： p
• 《統(tǒng)計(jì)學(xué)習(xí)方法》李航：*p
• 'Pattern Classification 2nd'：%p
• 'Pattern Classification and Machine Learning' :[pclm]
• ‘A Tutorial on Spectral Clustering’ [tsc]
• neural-networks-and-deep-learning [nndl]

本文結(jié)構(gòu)：哪些分類模型屬于參數(shù)法/非參數(shù)法飞几？哪些屬于生成模型/判別模型砚哆？

• 生成模型是基于概率密度的，會顯式地計(jì)算后驗(yàn)概率/類條件概率屑墨。將后驗(yàn)概率/類條件概率計(jì)算出來后躁锁，根據(jù)貝葉斯決策，可以得到最小誤差判別/最小風(fēng)險(xiǎn)判別卵史。計(jì)算后驗(yàn)概率/類條件概率可以分為參數(shù)法和非參數(shù)法：
  • 參數(shù)法：假設(shè)總體服從某含參數(shù)分布战转，然后根據(jù)樣本對參數(shù)進(jìn)行估計(jì)
  • 非參數(shù)法：直接根據(jù)樣本對類條件概率進(jìn)行估計(jì)。knn還可以直接對后驗(yàn)概率進(jìn)行估計(jì)程腹。
• 判別模型不基于后驗(yàn)概率匣吊。預(yù)先設(shè)定含參判別函數(shù)，然后從標(biāo)記樣本中學(xué)習(xí)參數(shù)寸潦。典型的有神經(jīng)網(wǎng)絡(luò)色鸳、線性判別、支持向量機(jī)

判別分析(判別模型)

判別模型不基于后驗(yàn)概率见转，而是設(shè)計(jì)一個函數(shù)(黑箱)命雀，對于給定樣本作為輸入，輸出一個類別斩箫。當(dāng)然這個函數(shù)在測試前需要進(jìn)行訓(xùn)練吏砂，也就是說這個函數(shù)是帶有參數(shù)的(可調(diào)節(jié)的)。判別模型訓(xùn)練本質(zhì)上是利用標(biāo)記樣本進(jìn)行判別函數(shù)參數(shù)學(xué)習(xí)乘客。
如何利用樣本進(jìn)行學(xué)習(xí)狐血？基本方法是構(gòu)造準(zhǔn)則函數(shù)(誤差函數(shù))，這個函數(shù)包含了樣本的標(biāo)記和模型的輸出(也就包含了判別模型的輸入和參數(shù))易核。誤差函數(shù)原則是樣本標(biāo)記和模型輸出一致時(或者近似匈织，對于回歸任務(wù))函數(shù)值為0或者很小；而當(dāng)樣本標(biāo)記與模型輸出差別很大時缀匕，函數(shù)值很大纳决。模型參數(shù)學(xué)習(xí)過程就是通過調(diào)節(jié)參數(shù)使得誤差函數(shù)值盡可能小(模型輸出與樣本標(biāo)記一致)。

這張圖展示了誤差函數(shù)乡小。對于樣本標(biāo)記與輸出一致的區(qū)域(紅色)阔加，誤差函數(shù)為0，其它區(qū)域存在誤差满钟，要求誤差函數(shù)對參數(shù)可導(dǎo)胜榔，這樣可以通過求導(dǎo)找到紅色的參數(shù)空間。三種誤差函數(shù)分別為分塊線性零远、平滑苗分、陡峭。陡峭的誤差函數(shù)更容易找到紅色區(qū)域

最優(yōu)的學(xué)習(xí)率最好是經(jīng)過一次學(xué)習(xí)就能得到最小值點(diǎn)

線性判別模型

線性判別只支持線性可分情況牵辣，否則模型參數(shù)學(xué)習(xí)不收斂摔癣。當(dāng)然線性不可分情況可以改造成線性可分。

二分類器構(gòu)造多分類器 p64

• 一對一

  
  

  (很可能存在不確定區(qū)域)

• 逐步一對多：將 c 類問題逐步轉(zhuǎn)化個兩類分類問題纬向。 第一個分類器將其中一個類樣本與其余各類樣本分開择浊，
  接著在其余各類中設(shè)計(jì)第二個分類器铜犬，直至僅剩下兩個分類器為止氛谜。對新樣本判別時，當(dāng)判別結(jié)果對應(yīng)1個類時焕梅，就輸出那個類师脂，判別結(jié)果為多個類時担孔，繼續(xù)判別。

• 一對多

  
  
  
  

  (很可能存在不確定區(qū)域)
  改進(jìn)(線性機(jī)器)：對于第i個輸出結(jié)果吃警，不輸入符號函數(shù)進(jìn)行判別糕篇，而是看作屬于第i類的可能性。對于m個下線性判別函數(shù)的值酌心，取值最大的結(jié)果對應(yīng)的類別作為輸出拌消，不存在模糊區(qū)域。

  
  
  線性機(jī)器分類策略
  
  線性機(jī)器也存在重大缺陷：分類界面只能是
  1 凸的(因?yàn)槟尺吔缢诔矫姹仨毷沟眠@一類都在一側(cè)安券，而不可以將同一類的樣本分開)
  

  2 單連通的(理由同上墩崩，分塊是廣義上的非凸)
  此時稱為線性不可分

  
  
  線性機(jī)器無法正確分類的數(shù)據(jù)分布模式
  簡單的一維情形也無法分類

• 廣義線性判別：

1 屬性先經(jīng)過一個(非線性)單值函數(shù)，再利用常規(guī)的線性判別模型
2 高次推廣：加入原先屬性的高次項(xiàng)(或交叉項(xiàng))作為新的屬性侯勉，仍按照線性判別模型

• 感知器 *p25
  為了簡單鹦筹，僅考慮兩類線性可分
  將輸入向量進(jìn)行增廣，因此僅需要考慮經(jīng)過原點(diǎn)的超平面址貌。首先確定正負(fù)類盛龄，將負(fù)類樣本乘以系數(shù)-1(樣本規(guī)范化，在樣本空間中進(jìn)行了關(guān)于原點(diǎn)的中心對稱操作),后面都只考慮處理后的樣本(也就是訓(xùn)練樣本的無差別對待，包括判斷分類正確性和權(quán)值更新)余舶。正確樣本向量與法向量內(nèi)積大于0(或夾角小于90°)
  限制解區(qū)域
  • 尋找一個單位長度的解向量 a，能最大化樣本到分界面的最小距離(不過這樣就復(fù)雜了锹淌，還要進(jìn)行極值求解)
  • 尋找一個最小長度的解向量 a匿值，使a‘yi>b. 此時可以將 b 稱為間隔 (margin)

在線性可分情形下，滿足上述不等式的 a 是無窮多的赂摆， 因此需要引入一個準(zhǔn)則挟憔。僅考慮錯分樣本作為誤差，法向量以批錯誤樣本向量之和的方向進(jìn)行調(diào)整(乘以學(xué)習(xí)速率)烟号，這樣法向量與錯誤樣本之間的夾角減小绊谭。

感知機(jī)誤差函數(shù)

權(quán)值更新公式

其它感知機(jī)誤差函數(shù)

• 松弛準(zhǔn)則

  
  
  
  
  松弛準(zhǔn)則函數(shù)的梯度
  
  
  松弛準(zhǔn)則的更新公式

• 平方誤差準(zhǔn)則（也就是最常見的線性模型最小二乘解）

  
  
  線性模型最小二乘解
  
  

  這里采用梯度下降對求解a(直接求Y的偽逆計(jì)算量太大)

  
  
  梯度下降法權(quán)值更新公式
  
  
  Ho-Kashyap Algorithm

• 支持向量機(jī)

優(yōu)點(diǎn)
理論基礎(chǔ)強(qiáng)；訓(xùn)練容易汪拥；能夠避免過擬合
缺點(diǎn)
核函數(shù)選擇达传；C參數(shù)選擇；復(fù)雜度高

• 線性可分問題

函數(shù)間隔：y(wx+b)迫筑，用于表示分類確信度
關(guān)于樣本點(diǎn)的函數(shù)間隔

關(guān)于數(shù)據(jù)集的函數(shù)間隔

更常用的是幾何間隔宪赶，物理意義是點(diǎn)到平面的有向距離

平面外一點(diǎn)用其在超平面上的投影以及到超平面的距離表示.注意r為幾何距離，有正負(fù)

點(diǎn)到平面距離推導(dǎo)

最大化距離的優(yōu)化問題：

令函數(shù)距離為1脯燃，轉(zhuǎn)化為等價優(yōu)化問題：

• 線性不可分問題

對于每一個樣本引入一個松弛變量搂妻，對約束進(jìn)行放寬。將松弛變量視為代價辕棚，加到目標(biāo)函數(shù)中

利用對偶問題求解上述優(yōu)化問題

-### 非線性劃分

因此雖然需要非線性函數(shù)將原空間進(jìn)行非線性映射扁瓢，但是并不需要具體去求這個函數(shù)，只需要求內(nèi)積形式的核函數(shù)

• 線性核：輸入向量的內(nèi)積

• 高斯核：輸入向量之差的模經(jīng)過高斯后的輸出

  
  

神經(jīng)網(wǎng)絡(luò)

誤差函數(shù)

**輸入層節(jié)點(diǎn)下標(biāo)為i,節(jié)點(diǎn)輸出為x涤妒；隱含層節(jié)點(diǎn)下標(biāo)為h,節(jié)點(diǎn)輸出為y；輸出層節(jié)點(diǎn)下標(biāo)為j;節(jié)點(diǎn)輸出為z**

• RBF網(wǎng)絡(luò)

  
  
  一列的徑向基函數(shù)不相同赚哗；一個樣本產(chǎn)生p維輸出

• Hopfield網(wǎng)絡(luò)
  wij：從結(jié)點(diǎn)i 到結(jié)點(diǎn) j 的連接權(quán)重她紫，Hopfield網(wǎng)絡(luò)是對稱的
  達(dá)到穩(wěn)定狀態(tài)。穩(wěn)定狀 態(tài)即為網(wǎng)絡(luò)的輸出

• 受限玻爾茲曼機(jī)RBM p111
  具有兩層結(jié)構(gòu)(完全二部圖)屿储，層內(nèi)結(jié)點(diǎn)不相連贿讹，信息可雙向流動

• 自組織映射網(wǎng)絡(luò)SOM p109

  
  

  競爭層結(jié)點(diǎn)之間并沒有連接，不過存在一種平面關(guān)系够掠。SOM 獲勝神經(jīng)元對其鄰近神經(jīng)元的影響是由近及遠(yuǎn)的,由興奮逐漸轉(zhuǎn)變?yōu)橐种泼窆印Ｔ趯W(xué)習(xí)算法中，不僅獲勝神經(jīng)元本身要調(diào)整權(quán)向量(隱層到競爭層的連接權(quán)重)，它周圍的神經(jīng)元在其影響下也要不同程 度地調(diào)整權(quán)重赊堪。鄰域大小可隨時間增長而減小面殖。
  競爭層每一個結(jié)點(diǎn)都有各自的權(quán)向量，用于與輸入計(jì)算距離哭廉。當(dāng)輸入得到后脊僚，每一個競爭層的結(jié)點(diǎn)的權(quán)重都與之計(jì)算距離，然后選出最小的距離對應(yīng)的結(jié)點(diǎn)作為勝出者遵绰。

  
  
  權(quán)向量更新公式

• 自動編碼機(jī) Autoencoder

• 線性判別分析（LDA）

  • 兩個類別的分類 p60
    將樣本空間投影到一維空間辽幌，優(yōu)化目標(biāo)為

    
    

求導(dǎo)求解

優(yōu)化求解

• 多個類別的分類
  將樣本空間投影到N-1維空間（類別數(shù)減一），優(yōu)化目標(biāo)為
  
  
  
  LDA不適合的情況

概率模型判別(生成模型)

一個實(shí)際為j類樣本判為某類i的風(fēng)險(xiǎn)

對于一個準(zhǔn)則函數(shù)的總體風(fēng)險(xiǎn)

由此導(dǎo)出貝葉斯判別準(zhǔn)則：對于每一個樣本都選擇最小期望代價對應(yīng)的類別椿访，

最小代價(風(fēng)險(xiǎn))決策

最小誤差率任務(wù)：0-1代價(風(fēng)險(xiǎn))成玫〖咏停或者是所有誤判代價相等且大于正確的代價

此時最小風(fēng)險(xiǎn)決策具體為最小錯誤率決策，也就是后驗(yàn)概率最大的對應(yīng)的類別(類條件概率) p147：

最小誤差率決策

• 貝葉斯分類器

貝葉斯分類器與貝葉斯學(xué)習(xí)有顯著區(qū)別梁剔，前者是通過最大后驗(yàn)概率進(jìn)行點(diǎn)估計(jì)虽画，而后者是進(jìn)行分布估計(jì)。
判別函數(shù)(用于計(jì)算c個類別對應(yīng)的風(fēng)險(xiǎn))：

最小代價(風(fēng)險(xiǎn))對應(yīng)的判別函數(shù)

最小誤差率(0-1風(fēng)險(xiǎn))分類對應(yīng)的判別函數(shù)

• 最小誤差判別：類條件分布假設(shè)為多元正態(tài)分布

一般類條件概率假設(shè)為多元正態(tài)分布模型荣病，帶入最小誤差準(zhǔn)則對應(yīng)的判別函數(shù)中码撰，得：

正態(tài)分布假設(shè)下，最小誤差準(zhǔn)則對應(yīng)的判別函數(shù)

接著討論一些情況

• 每一類協(xié)方差矩陣都相等个盆、樣本屬性之間線性無關(guān)脖岛、各屬性方差都相等

  
  

• 每一類協(xié)方差矩陣都相等

  
  
• 一般地，每一類協(xié)方差不相等
  

• 樸素貝葉斯分類器

求類條件概率時颊亮，考慮到樣本空間太大柴梆，因此假設(shè)樣本各屬性之間相互獨(dú)立，于是類條件概率可以寫成屬性類條件概率的乘積形式终惑。這樣對于每一個概率绍在，樣本空間都是一維的，根據(jù)樣本對求出每一個屬性的類條件分布雹有。類的概率按照樣本占比進(jìn)行估計(jì)偿渡。至此樣本學(xué)習(xí)完畢。

• 對于一個新的樣本進(jìn)行歸類
  按照窮舉法霸奕，對于每一個類別溜宽，由于類條件概率分布已知，根據(jù)樣本屬性求出各屬性的類條件概率(密度)值质帅，按照上式進(jìn)行相乘适揉，這樣求出所有的類別的后驗(yàn)值后進(jìn)行排序留攒，將最大值對應(yīng)的概率進(jìn)行輸出。

• 離散概率分布估計(jì) p153
  離散的概率分布一般直接用樣本出現(xiàn)頻率來估計(jì)嫉嘀，比如類別的先驗(yàn)概率炼邀。當(dāng)樣本不充足或分布覆蓋不廣會導(dǎo)致估計(jì)概率為0(連續(xù)型概率分布不會遇到這種情況)，很多時候0概率會帶來問題(例如樸素貝葉斯分類器吃沪，某個類條件屬性值為0汤善，那么這個類條件概率直接為0)。因此需要進(jìn)行平滑修正票彪，一般采用拉普拉斯修正：對于每一類，給每一個離散屬性值額外賦予一個樣本不狮。于是對于每一類降铸，樣本數(shù)增加了Ni；總樣本數(shù)增加N

• 參數(shù)法估計(jì)類條件概率

給定類別摇零，假設(shè)對總體服從特定的概率分布形式推掸，然后基于樣本對模型參數(shù)進(jìn)行估計(jì)（一般是連續(xù)型分布，離散型直接通過出現(xiàn)頻率進(jìn)行估計(jì)）驻仅。確定參數(shù)后谅畅，類條件概率p(x|c)就完全確定下來了。
參數(shù)估計(jì)有兩種派別噪服，對應(yīng)兩種方法：

• 極大似然估計(jì)法
  由于樣本服從總體的分布毡泻，對于給定數(shù)目的樣本，可以構(gòu)建聯(lián)合概率分布粘优；由于樣本都是獨(dú)立同分布的仇味，樣本聯(lián)合概率分布可以通過總體概率分布的連乘得到(帶參數(shù))。由于樣本值已知雹顺，可以帶入樣本聯(lián)合概率分布中丹墨，得到只剩下模型參數(shù)為變量的似然函數(shù)。使得似然函數(shù)值最大的參數(shù)即為極大似然估計(jì)嬉愧。

• 貝葉斯參數(shù)估計(jì)

  
  
  貝葉斯后驗(yàn)概率估計(jì)核心公式
  
  

  其中參數(shù)因?yàn)椴淮_定贩挣，就當(dāng)作變量處理，因此具有分布p(θ)没酣，于是按照上述公式進(jìn)行積分求得類條件分布p(x|D)王财。而根據(jù)數(shù)據(jù)可以減少參數(shù)不確定程度，也就是參數(shù)后驗(yàn)概率p(θ|D)四康。

  
  
  貝葉斯學(xué)習(xí)過程：在數(shù)據(jù)量越來越多的情況下搪搏，參數(shù)的不確定程度越來越小，體現(xiàn)為參數(shù)的后驗(yàn)分布趨于尖峰狀

假設(shè)模型參數(shù)為正態(tài)分布

• 單變量情況p(μ|D):

假設(shè)類條件分布為正態(tài)分布闪金，均值未知疯溺，方差已知

均值參數(shù)服從已知的正態(tài)分布

求得均值參數(shù)的后驗(yàn)概率：

根據(jù)貝葉斯概率估計(jì)公式论颅，積分得到類條件分布：

• 多變量情況

  
  
  假設(shè)參數(shù)和后驗(yàn)概率都服從正態(tài)分布，協(xié)方差已知囱嫩，均值向量為參數(shù)
  
  
  
  

• 遞歸貝葉斯學(xué)習(xí)

  
  
  在線學(xué)習(xí)：新樣本對參數(shù)的后驗(yàn)分布更新公式
  
  

  例題：

  
  
  假設(shè)類條件分布如上恃疯，帶有未知參數(shù)θ
  且已知上述參數(shù)服從如上分布(先驗(yàn)知識)
  接著觀測到數(shù)據(jù)集D = {4, 7, 2, 8}.
  對于x1 = 4：當(dāng)θ<4時，p(x|θ)=0墨闲；當(dāng)θ>10時今妄，p(θ|D)=0；當(dāng)4<θ<10時,p(x|θ)=1/θ鸳碧，p(θ|D)=c盾鳞，p(x|θ)p(θ|D)=1/θ. 因此
  
  第一個數(shù)據(jù)到達(dá)后，參數(shù)的分布進(jìn)行了更新
  
  
  參數(shù)隨數(shù)據(jù)到來的分布更新

  從貝葉斯參數(shù)分布更新公式可以看出瞻离，參數(shù)在取值空間每一處的值是乘上一個系數(shù)（p(x|θ)在此參數(shù)值條件下腾仅，樣本處的概率值），因此區(qū)間是進(jìn)行了放縮套利，且一旦某點(diǎn)的后驗(yàn)概率更新為0推励，之后就始終為0. 因此參數(shù)的后驗(yàn)概率只會越來越集中，最終形成尖峰肉迫。

• EM算法

  • 首先選擇參數(shù)的初值
  • 注意是概率分布验辞，因此需要考慮歸一化

    
    

• 非參數(shù)法估計(jì)類條件概率

樣本空間中某一點(diǎn)處的概率密度用樣本在其鄰域出現(xiàn)的頻率來估計(jì)：

其中等式左邊為需要估計(jì)的某一點(diǎn)處的概率密度，V為此點(diǎn)的一個鄰域喊衫，兩者乘積是一個概率值P（因?yàn)楦怕拭芏仁且粋€無窮小的概率跌造，在樣本空間上積分才是概率值）。k/n表示樣本在此鄰域內(nèi)出現(xiàn)的頻率格侯。對于給定的數(shù)據(jù)集鼻听，n固定，變量只剩下k和V. 固定k联四，稱為knn估計(jì)撑碴；固定V，稱為Parzen window估計(jì)朝墩。

• Parzen window

對于輸入向量醉拓，存在一個分量大于0.5就輸出0，否則輸出1.

推廣：不僅僅是鄰域內(nèi)的樣本才對此點(diǎn)有貢獻(xiàn)收苏，而是所有樣本根據(jù)距離遠(yuǎn)近加權(quán)做出貢獻(xiàn)亿卤。實(shí)際上只要滿足概率密度要求的函數(shù)都可以

推廣的delta函數(shù)含義為：一個樣本，對于給定距離（向量）帶來的計(jì)數(shù)

對于每一個樣本鹿霸，欲測量點(diǎn)處的概率密度為所有樣本對此點(diǎn)的概率密度影響之和的平均值

• knn

knn分類器可以直接估計(jì)后驗(yàn)概率(類條件概率也可以用knn進(jìn)行估計(jì))

• 泛化錯誤率不超過貝葉斯最優(yōu)估計(jì)兩倍 p226
  優(yōu)點(diǎn)：簡單好用排吴，容易理解，精度高懦鼠，理論成熟钻哩，既可以用來做分類也可以用來做回歸屹堰； 可用于數(shù)值型數(shù)據(jù)和離散型數(shù)據(jù)；無數(shù)據(jù)輸入假定街氢； 對異常值不敏感 扯键。
  缺點(diǎn)：當(dāng)樣本不平衡時有可能導(dǎo)致樣本的 K個鄰居中大容量類的樣本占多數(shù)。計(jì)算量較大珊肃，及時響應(yīng)性能不行荣刑。

k=3，說明包圍3個樣本最小區(qū)間的中心處是一個峰值

k=1時伦乔，樣本點(diǎn)處的概率密度值為無窮大厉亏。除非樣本重復(fù)，否則其它k>1概率密度值都有界

快速近鄰搜索

• 部分距離判斷：在進(jìn)行距離計(jì)算時烈和，實(shí)際是計(jì)算差向量的模叶堆，也就是其各個分量的平方和后開方。為了減少乘積運(yùn)算斥杜，一個分量一個分量計(jì)算相加，一旦累加和已經(jīng)超過限定的距離平方后就停止運(yùn)算沥匈，因?yàn)榫嚯x已經(jīng)超過限定距離蔗喂。
• 建立搜索樹：思想是：對于明顯行不通的方向，試都不要試高帖。好比鑰匙丟了缰儿，肯定是在最近去的地方找，而不是地毯式找散址。
• 樣本簡化：雖然樣本數(shù)量很多乖阵，但是對分類邊界有貢獻(xiàn)的僅占少數(shù)，類似于SVM中支持向量是少數(shù)预麸。通過去除冗余樣本可以降低計(jì)算復(fù)雜度瞪浸。

降維與特征提取

高維有利于不同類別之間的區(qū)分

• 高維樣本空間帶來的困難 p227
  數(shù)據(jù)樣本稀疏：對于一定量的樣本，樣本空間維數(shù)越大吏祸，樣本就越稀疏对蒲。可以反向理解：一定量的高維樣本空間中的樣本經(jīng)過降維贡翘，樣本分布就會密集蹈矮；低維線性不可分?jǐn)?shù)據(jù)在高維線性可分
  距離計(jì)算復(fù)雜
  泛化困難
  便于可視化
• 降維方法
• 針對樣本空間，線性變換降維方法（主成分導(dǎo)出）

  • 重構(gòu)與重構(gòu)誤差 p230

    
    

    一個樣本（即向量）可以由變換后的空間中的基底和對應(yīng)坐標(biāo)的線性組合表示（即重構(gòu)表示鸣驱，若重構(gòu)維數(shù)相等泛鸟，則是同一個向量），與原先空間的坐標(biāo)表示之間的偏差稱為“重構(gòu)誤差”：

    
    
    最小化這個誤差(x-WW'x)
    

  • 投影方差最大化 p230

    
    

  • 主成分 p231

上述兩個優(yōu)化問題等價踊东，運(yùn)用向量求導(dǎo)法則北滥，可得：

顯然解與隨機(jī)向量X的協(xié)方差陣的特征值和特征向量有關(guān)

PCA算法

• 保持樣本距離的非線性降維方法MDS p227
  測地線距離：沿著空間表面的距離也稱“本真距離”刚操。
  高維直線距離：可以脫離表面的高維空間距離

  
  

  注意，MDS僅僅是在低維空間保持樣本之間距離不變碑韵，但是并不保證樣本分布與高維分布同構(gòu)赡茸。MDS假設(shè)高維直線距離唯一代表樣本的近似程度，而實(shí)際很多情況下這個假設(shè)并不合理：

  
  
  如果僅僅使用MDS降維祝闻，C點(diǎn)比B點(diǎn)更接近A點(diǎn)占卧，有悖常理。于是引入流行學(xué)習(xí)(manifold learning)

• 流行學(xué)習(xí)

  • 等度量映射Isomap
    針對MDS的缺點(diǎn)联喘，Isomap局部采用MDS华蜒，得到樣本低維分布：

    
    
    Isomap算法

  • 局部線性嵌入LLE
    區(qū)別與Isomap保持局部樣本距離不變，LLE希望保持樣本之間相對位置不變

    
    

聚類分析

• 混合高斯分布 [pclm] p430
• k-means [pclm] p424
  采用最大似然估計(jì)或最小均方誤差作為評價聚類的準(zhǔn)則函數(shù)
  • 最大似然估計(jì): 先假設(shè)總體服從k個高斯混合分布豁遭，再假設(shè)樣本屬于某類的后驗(yàn)概率服從0-1分布叭喜，即距離樣本某類中心(因?yàn)榧僭O(shè)服從高斯分布，因此有中心)最近蓖谢，屬于那類的概率就為1捂蕴，而屬于其他類的概率為0。為了找到各類中心闪幽，k-means使用的是最大期望迭代算法(EM): 先隨機(jī)挑選k個樣本作為類中心啥辨，利用0-1后驗(yàn)概率，將樣本分為k類; 根據(jù)得到的k類盯腌，計(jì)算各類中心溉知，返回上一步。停機(jī)條件是類中心不再發(fā)生變化腕够。此時類中心就收斂到假設(shè)的k個高斯中心了级乍。k-means算法的有效性和收斂性證明參考EM算法。
    
    k-means

  • 最小均方誤差(適用于各類樣本平衡帚湘，云團(tuán)分布)：從一個類引出一個樣本會減少該類均方誤差玫荣； 但移入一個樣本至一個類會增加該類均方誤差。如果減 少量大于增加量客们，對這樣的樣本進(jìn)行移動是有利于總體 誤差減少的崇决。也可以進(jìn)一步改變準(zhǔn)則為：類內(nèi)散度最小底挫；類間散度最大

    
    
    樣本類調(diào)整原則
    隨機(jī)劃分成c類恒傻，并計(jì)算c類的中心；接著隨機(jī)挑選樣本建邓，判斷屬于哪一類盈厘，然后計(jì)算這個樣本若加入到其它類去引入的誤差和在本類中去除所減小的誤差；若引入誤差小于減小誤差官边，則進(jìn)行個樣本轉(zhuǎn)移沸手，并重新計(jì)算涉及到的兩個類別的均值外遇；直到無法進(jìn)行樣本轉(zhuǎn)移

kmeans局限性

• 必須事先給定簇的個數(shù)，且對初始值敏感

• 不適合于大小相差很大的簇

• 對噪聲契吉、孤立數(shù)據(jù)點(diǎn)很敏感跳仿。

• 不適用于總體不滿足k個混合高斯分布假設(shè)的情況，也就是數(shù)據(jù)不是一個一個云團(tuán)分布的捐晶。

  
  
  散度準(zhǔn)則
  
  

  總類內(nèi)散度跡最小準(zhǔn)則：與類均方誤差最小準(zhǔn)則是等價的菲语。
  類間散度最大準(zhǔn)則
  最小化總類內(nèi)行列式準(zhǔn)則

• 譜聚類

實(shí)際數(shù)據(jù)不服從高斯混合分布的情況更加普遍，由此引入譜聚類算法惑灵。

• 鄰接矩陣(權(quán)重矩陣)
  元素為0說明對應(yīng)的兩個頂點(diǎn)之間不相鄰（至于頂點(diǎn)自身相似度是多少山上，后面可以看到對角線元素對結(jié)果完全沒影響）

  
  
  頂點(diǎn)度數(shù)
  
  

  |A| 表示一個頂點(diǎn)集中頂點(diǎn)的個數(shù)； vol(A) 是頂點(diǎn)集中所有頂點(diǎn)度數(shù)之和
  由數(shù)據(jù)生成鄰接矩陣(權(quán)重矩陣)的方式

  • ε-neighborhood
  • k-nearest neighbor
  • 全連接

• 拉普拉斯圖矩陣

  
  
  未標(biāo)準(zhǔn)化的拉普拉斯圖矩陣
  兩種標(biāo)準(zhǔn)化的拉普拉斯圖矩陣
  
  

  拉普拉斯圖矩陣的特點(diǎn)是：
  1 半正定
  2 0特征值對應(yīng)的特征向量是全1向量
  3 o特征值的重?cái)?shù)表示原圖的連接子圖個數(shù)

  
  

圖切割

補(bǔ)充

• 凸優(yōu)化問題*p100

  
  
• 拉格朗日乘子法 p403
• 對偶問題*p225

常見問題：

• 協(xié)方差矩陣不滿秩

(a)將協(xié)方差矩陣與單位矩陣進(jìn)行平滑英支，得到非奇異矩陣佩憾。
(b)將協(xié)方差矩陣進(jìn)行正交分解(譜分解)后，將為 0 的特征值置為一個很小的非零值（如 0.001）.

• 距離度量
  距離需要滿足的基本性質(zhì)：
  1 非負(fù)性 2 同一性(當(dāng)且僅當(dāng)兩輸入相等時干花，距離為0) 3 對稱性 4 三角不等式(不滿足此性質(zhì)的稱為非度量距離p201)

• 向量之間的距離

• Minkowski：適用于有序?qū)傩酝保Ｓ玫氖荅uclidean distance (p=2)；還有曼哈頓距離(p=1)

• tangent distance
  因?yàn)镺CR常見的仿射變換對歐氏距離影響很大池凄，引入切空間距離寄摆。切空間距離不再是兩個向量之間的距離，而是樣本到另一個樣本生成的切空間的距離修赞。切空間是由一些仿射變換"線性"組合（線性系數(shù)看作仿射變換參數(shù)）形成的空間。一個樣本到這個空間的距離也就是其到那個樣本的各種仿射變換的最短距離桑阶。當(dāng)然這個切空間得是有限的（也就是仿射變換參數(shù)范圍有限）柏副，比如旋轉(zhuǎn)變換的角度需要控制在一定范圍內(nèi)。缺點(diǎn)是訓(xùn)練計(jì)算量大蚣录。

  
  

• 馬氏距離：同一分布的兩個樣本之間的距離割择；樣本與一總體之間的距離

• 樣本簇之間的距離
  最大距離、最小距離萎河、平均距離荔泳、中心距離

簇與樣本之間的距離采用最近距離

簇與樣本之間的距離采用最遠(yuǎn)距離

• 集成學(xué)習(xí)有效原因
  p181
• 特征選擇動機(jī)
  1.降維
  2.探索關(guān)鍵因素
• 局部最小問題解跳出思路
  1 重復(fù)、隨機(jī)初始化
  2 模擬退火：以衰減的概率接受次優(yōu)解
  3 隨機(jī)梯度下降