先進(jìn)模式識(shí)別(ii)聚類分析和弱監(jiān)督學(xué)習(xí)

1、聚類分析1聚類和聚類分析聚類：是將數(shù)據(jù)分類到不同的類或者簇(Cluster)的過(guò)程，使得同一個(gè)簇中的對(duì)象具有最大的相似性，不同簇間的對(duì)象具有最大的相異性。2Connectivity based clusteringHierarchical Clustering3Centroid-based clusteringK-means Clustering4Distribution-based clustering5Graph-based clustering6最小割(mincut)7Normalized CutMinCut算法在實(shí)踐應(yīng)用中很容易造成將單個(gè)樣本劃分為一個(gè)子集的現(xiàn)象。8Normalized

2、 Cut9Normalized Cut10相似圖和鄰接矩陣相似圖：鄰接矩陣：11譜聚類算法12譜聚類示例樣本 (0,0), (0,1), (1, 0), (1,1), (0,10), (0,11), (1, 10), (1,11), (10,0), (10,1), (11, 0), (11,1), (10,10), (10,11), (11, 10), (11,11) 特征值： 最大4個(gè)特征值對(duì)應(yīng)的特征矢量：0.00000.00080.00080.00153.44773.44773.44773.44773.44813.44813.44813.44813.62013.62013.62013.62

3、01-0.2500+0.0431+0.3510+0.2501-0.2500+0.0432+0.3509+0.2500-0.2500+0.0431+0.3509+0.2500-0.2500+0.0431+0.3509+0.2499-0.2500+0.3509-0.0431-0.2500-0.2500+0.3510-0.0431-0.2501-0.2500+0.3509-0.0431-0.2499-0.2500+0.3509-0.0432-0.2500-0.2500-0.3509+0.0432-0.2500-0.2500-0.3509+0.0431-0.2499-0.2500-0.3510+0.0

4、431-0.2501-0.2500-0.3509+0.0431-0.2500-0.2500-0.0431-0.3509+0.2499-0.2500-0.0431-0.3509+0.2500-0.2500-0.0432-0.3509+0.2500-0.2500-0.0431-0.3510+0.250114譜聚類示例 原樣本分布 K均值聚類 特征值矩陣的行矢量15Laplacian矩陣的性質(zhì)16Laplacian矩陣的性質(zhì)17RatioCut的近似譜求解: k=218RatioCut的近似譜求解: k=2f與矢量1正交: 即:f的長(zhǎng)度平方為n:19RatioCut的優(yōu)化問(wèn)題嚴(yán)格的優(yōu)化問(wèn)題: 約束:

5、仍然是一個(gè)NP問(wèn)題。20近似的RatioCut的優(yōu)化問(wèn)題近似的優(yōu)化問(wèn)題：放松對(duì)f中元素的離散性約束問(wèn)題的解: 對(duì)應(yīng)L第2小特征值的特征矢量證明: 不考慮正交約束，問(wèn)題變成Rayleigh商的優(yōu)化，解是L的最小特征值對(duì)應(yīng)的特征矢量；最小特征值對(duì)應(yīng)特征矢量為1，不滿足正交條件，第2小特征值對(duì)應(yīng)特征矢量滿足正交條件（L為實(shí)對(duì)稱矩陣）；21k=2 示例將19個(gè)樣本分成2個(gè)聚類。x1=(0,0)t, x2=(1,0)t, x3=(0,1)t, x4= (1,1)t,x5=(2,1)t, x6=(1,2)t, x7=(2,2)t, x8=(3,2)t,x9=(6,6)t, x10=(7,6)t, x11=

6、(8,6)t, x12= (7,7)t,x13=(8,7)t, x14=(9,7)t, x15=(7,8)t, x16=(8,8)t,x17=(9,8)t, x18=(8,9)t, x19=(9,9)t22特征值 特征值前2個(gè)特征值對(duì)應(yīng)特征矢量0.00000.06824.35105.12675.49045.91425.94616.30806.41756.48266.76966.99577.37047.69837.77897.93428.37168.64448.8704-0.2294+0.2740-0.2294+0.2728-0.2294+0.2731-0.2294+0.2715-0.2294+

7、0.2694-0.2294+0.2699-0.2294+0.2655-0.2294+0.2553-0.2294-0.1838-0.2294-0.1920-0.2294-0.1954-0.2294-0.1953-0.2294-0.1968-0.2294-0.1978-0.2294-0.1969-0.2294-0.1977-0.2294-0.1984-0.2294-0.1985-0.2294-0.199123聚類結(jié)果24RatioCut的近似譜求解: k225RatioCut的優(yōu)化問(wèn)題嚴(yán)格的優(yōu)化問(wèn)題：約束：仍然是NP問(wèn)題。26近似的RatioCut的優(yōu)化問(wèn)題近似的優(yōu)化問(wèn)題：放松對(duì)h中元素的離散性約

8、束問(wèn)題的解：最小k個(gè)特征值對(duì)應(yīng)特征矢量。27NCut的近似譜求解：k=228NCut的近似譜求解：k=229NCut的近似譜求解：k=230NCut的優(yōu)化問(wèn)題嚴(yán)格的優(yōu)化問(wèn)題： 約束：31NCut的近似優(yōu)化問(wèn)題32NCut的近似譜求解：k233NCut的近似譜求解：k234NCut的優(yōu)化問(wèn)題：k2嚴(yán)格的優(yōu)化問(wèn)題： 約束:35NCut的近似優(yōu)化問(wèn)題：k236譜聚類算法37算法的實(shí)現(xiàn)38算法的實(shí)現(xiàn)39算法的實(shí)現(xiàn)40弱監(jiān)督學(xué)習(xí)41統(tǒng)計(jì)學(xué)習(xí)過(guò)程42學(xué)習(xí)的過(guò)程43統(tǒng)計(jì)學(xué)習(xí)過(guò)程44統(tǒng)計(jì)學(xué)習(xí)過(guò)程最大似然估計(jì)：貝葉斯估計(jì)：45統(tǒng)計(jì)學(xué)習(xí)過(guò)程46弱監(jiān)督學(xué)習(xí)過(guò)程標(biāo)簽不是直接來(lái)自于Oracle，而是由Priesthoo

9、d轉(zhuǎn)達(dá)的。47弱監(jiān)督的風(fēng)險(xiǎn)48弱監(jiān)督經(jīng)驗(yàn)風(fēng)險(xiǎn)的優(yōu)化49半監(jiān)督學(xué)習(xí)50Semi-Supervised Learning51Self-TrainingSelf-Training52Co-TrainingCo-Training53Tri-TrainingTri-Training54Transductive SVMTransductive SVM14:思路：讓分類邊界盡量遠(yuǎn)離樣本稠密區(qū)域。方法：求解新的優(yōu)化問(wèn)題其中：55Graph-Based Methods假設(shè)不同類別的樣本分布在不同的流形上圖的構(gòu)造：所有樣本構(gòu)成節(jié)點(diǎn)，樣本之間的相似性構(gòu)成節(jié)點(diǎn)之間的連接；思路：用正例節(jié)點(diǎn)作為源，反例節(jié)點(diǎn)作為匯，尋找圖

10、的最小割。算法：Mincut：直接求最小割；Spectrum of Laplacian: 用譜的方法近似求解。56Label Propagation57優(yōu)化問(wèn)題求解58優(yōu)化問(wèn)題求解59對(duì)算法的理解Harmonic性：可以證明優(yōu)化問(wèn)題的解具有Harmonic特性隨機(jī)游走過(guò)程：定義節(jié)點(diǎn)之間的轉(zhuǎn)移概率60隨機(jī)游走61多示例學(xué)習(xí)Multi-Instance Learning62問(wèn)題的提出1997年，Dietterich在分子制藥預(yù)測(cè)方面提出的；背景：藥物能否有效是由藥物分子與蛋白質(zhì)結(jié)合的緊密性決定的。問(wèn)題：在藥物中，每個(gè)分子存在著多個(gè)低能量的形狀；只能知道哪一種藥物分子有效，但無(wú)法確切知道是哪個(gè)分子形

11、狀起的作用。63問(wèn)題的描述每個(gè)分子形狀表示為一個(gè)特征矢量，稱為示例（Instance）；每個(gè)藥物分子表示為一個(gè)示例包(Bag of Instances)正例包：其中至少有一個(gè)示例是正例；反例包：所有示例均為反例。已知：每個(gè)示例包的標(biāo)簽；未知：每個(gè)示例的標(biāo)簽。64圖像識(shí)別已知圖像的標(biāo)簽，其中每個(gè)區(qū)域的標(biāo)簽未知。65示例包：正例包中至少有一個(gè)示例是正例；反例包中的示例都是反例。問(wèn)題：判別示例包A是正例包還是反例包？判別示例y是正例還是反例？問(wèn)題的表示66解決問(wèn)題的思路將示例包的標(biāo)簽傳遞給其中的每一個(gè)示例？將所有的示例連接成一個(gè)特征矢量？67算法的分類Bag Based Methods：將示例包作為

12、一個(gè)整體，看作是空間中一個(gè)點(diǎn)；將示例包空間視為度量空間，直接定義距離度量；采用某種辦法將示例包空間映射為歐氏空間，采用單示例分類器分類；Instance Based Methods：按照MI的定義，利用示例包學(xué)習(xí)一個(gè)示例的分類器，分類時(shí)對(duì)每個(gè)示例進(jìn)行分類，然后再判斷示例包的屬性。68Citation k-NN方法：直接定義示例包之間的距離Citation k-nn69嵌入空間算法CCE聚類示例，包括正例包和反例包的所有示例；按照每個(gè)示例包中包含各個(gè)聚類的示例情況，將示例包映射為一個(gè)矢量；用所有示例包對(duì)應(yīng)的矢量學(xué)習(xí)一個(gè)分類器；重復(fù)聚類，映射和學(xué)習(xí)分類器的過(guò)程，得到多個(gè)分類器；組合所有分類器。方法

13、：將示例包空間映射為一個(gè)矢量空間70CCE：Constructive Clustering based Ensemble71APR: Axis-Parallel Rectangles 思想：構(gòu)造APR，尋找一個(gè)超矩形，至少包含每個(gè)正例包中的一個(gè)示例，但不包含反例包中的任何示例。APR初始：計(jì)算正例包示例各維特征的最大值和最小值，構(gòu)造一個(gè)包含所有正例包示例的最小超矩形；循環(huán)，直到APR中不包含任何反例為止：尋找能夠排除某個(gè)反例，同時(shí)排除正例包示例數(shù)量最少的特征；在此特征維度上縮小APR。72APR: Axis-Parallel Rectangles 初始APR收斂APR73DD: Diverse Density思想：認(rèn)為在示例空間中只有一個(gè)點(diǎn)是正例，正例包都包含（靠近）這一點(diǎn)，反例包的示例遠(yuǎn)離這一點(diǎn)。74DD: Diverse Density75MI-SVM76mi-SVM學(xué)習(xí)：優(yōu)化問(wèn)題約束：正例包：反例包：分類：77其它的弱監(jiān)督學(xué)習(xí)問(wèn)題Multi-Label Learning：每個(gè)示例有多個(gè)標(biāo)簽Multi-Instance Multi-La