1、聚類分析1聚類和聚類分析聚類：是將數據分類到不同的類或者簇(Cluster)的過程，使得同一個簇中的對象具有最大的相似性，不同簇間的對象具有最大的相異性。2Connectivity based clusteringHierarchical Clustering3Centroid-based clusteringK-means Clustering4Distribution-based clustering5Graph-based clustering6最小割(mincut)7Normalized CutMinCut算法在實踐應用中很容易造成將單個樣本劃分為一個子集的現象。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個特征值對應的特征矢量：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矩陣的性質16Laplacian矩陣的性質17RatioCut的近似譜求解: k=218RatioCut的近似譜求解: k=2f與矢量1正交: 即:f的長度平方為n:19RatioCut的優化問題嚴格的優化問題: 約束:

5、仍然是一個NP問題。20近似的RatioCut的優化問題近似的優化問題：放松對f中元素的離散性約束問題的解: 對應L第2小特征值的特征矢量證明: 不考慮正交約束，問題變成Rayleigh商的優化，解是L的最小特征值對應的特征矢量；最小特征值對應特征矢量為1，不滿足正交條件，第2小特征值對應特征矢量滿足正交條件（L為實對稱矩陣）；21k=2 示例將19個樣本分成2個聚類。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個特征值對應特征矢量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聚類結果24RatioCut的近似譜求解: k225RatioCut的優化問題嚴格的優化問題：約束：仍然是NP問題。26近似的RatioCut的優化問題近似的優化問題：放松對h中元素的離散性約

8、束問題的解：最小k個特征值對應特征矢量。27NCut的近似譜求解：k=228NCut的近似譜求解：k=229NCut的近似譜求解：k=230NCut的優化問題嚴格的優化問題： 約束：31NCut的近似優化問題32NCut的近似譜求解：k233NCut的近似譜求解：k234NCut的優化問題：k2嚴格的優化問題： 約束:35NCut的近似優化問題：k236譜聚類算法37算法的實現38算法的實現39算法的實現40弱監督學習41統計學習過程42學習的過程43統計學習過程44統計學習過程最大似然估計：貝葉斯估計：45統計學習過程46弱監督學習過程標簽不是直接來自于Oracle，而是由Priesthoo

9、d轉達的。47弱監督的風險48弱監督經驗風險的優化49半監督學習50Semi-Supervised Learning51Self-TrainingSelf-Training52Co-TrainingCo-Training53Tri-TrainingTri-Training54Transductive SVMTransductive SVM14:思路：讓分類邊界盡量遠離樣本稠密區域。方法：求解新的優化問題其中：55Graph-Based Methods假設不同類別的樣本分布在不同的流形上圖的構造：所有樣本構成節點，樣本之間的相似性構成節點之間的連接；思路：用正例節點作為源，反例節點作為匯，尋找圖

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

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

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

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