10.聚類與集成算法10.聚類與集成算法1聚類(Clustering)在“無監(jiān)督學(xué)習(xí)”任務(wù)中研究最多、應(yīng)用最廣目標：將數(shù)據(jù)樣本劃分為若干個通常不相交的“簇”(cluster)

既可以作為一個單獨過程（用于找尋數(shù)據(jù)內(nèi)在的分布結(jié)構(gòu)） 也可作為分類等其他學(xué)習(xí)任務(wù)的前驅(qū)過程聚類(Clustering)在“無監(jiān)督學(xué)習(xí)”任務(wù)中研究最多、2性能度量聚類性能度量，亦稱聚類“有效性指標”(validityindex)外部指標(externalindex)將聚類結(jié)果與某個“參考模型”(referencemodel)進行比較如Jaccard系數(shù)，F(xiàn)M指數(shù)，Rand指數(shù)內(nèi)部指標(internalindex)直接考察聚類結(jié)果而不用任何參考模型如DB指數(shù)，Dunn指數(shù)等基本想法：?“簇內(nèi)相似度”（intra-clustersimilarity）高，且?“簇間相似度”（inter-clustersimilarity）低性能度量聚類性能度量，亦稱聚類“有效性指標”(validi3距離計算距離度量(distancemetric)需滿足的基本性質(zhì)：常用距離形式：閔可夫斯基距離(Minkowskidistance)p=2:歐氏距離(Euclideandistance)p=1:曼哈頓距離(Manhattandistance)距離計算距離度量(distancemetric)需滿足4距離計算(續(xù)）對無序(non-ordinal)屬性，可使用VDM(ValueDifferenceMetric)令表示屬性u上取值為a的樣本數(shù)，表示在第i個樣本

簇中在屬性u上取值為a的樣本數(shù)，k為樣本簇數(shù)，則屬性u上兩個 離散值a與b之間的VDM距離為對混合屬性，可使用MinkovDM距離計算(續(xù)）對無序(non-ordinal)屬性5必須記住聚類的“好壞”不存在絕對標準thegoodnessofclusteringdependsontheopinionoftheuser必須記住聚類的“好壞”不存在絕對標準thegoodness6故事一則聚類的故事：老師拿來蘋果和梨，讓小朋友分成兩份。小明把大蘋果大梨放一起，小個頭的放一起，老師點頭，恩，體量感。小芳把紅蘋果挑出來，剩下的放一起，老師點頭，顏色感。小武的結(jié)果？不明白。小武掏出眼鏡：最新款，能看到水果里有幾個籽，左邊這堆單數(shù)，右邊雙數(shù)。老師很高興：新的聚類算法誕生了聚類也許是機器學(xué)習(xí)中“新算法”出現(xiàn)最多、最快的領(lǐng)域 總能找到一個新的“標準”，使以往算法對它無能為力故事一則聚類的故事：老師拿來蘋果和梨，讓小朋友分成兩份。小明7常見聚類方法

原型聚類????亦稱“基于原型的聚類”(prototype-basedclustering)假設(shè)：聚類結(jié)構(gòu)能通過一組原型刻畫過程：先對原型初始化，然后對原型進行迭代更新求解代表：k均值聚類，學(xué)習(xí)向量量化(LVQ)，高斯混合聚類密度聚類????亦稱“基于密度的聚類”(density-basedclustering)假設(shè)：聚類結(jié)構(gòu)能通過樣本分布的緊密程度確定過程：從樣本密度的角度來考察樣本之間的可連接性，并基于可連接樣本不斷擴展聚類簇代表：DBSCAN,OPTICS,DENCLUE層次聚類(hierarchicalclustering)???假設(shè)：能夠產(chǎn)生不同粒度的聚類結(jié)果過程：在不同層次對數(shù)據(jù)集進行劃分，從而形成樹形的聚類結(jié)構(gòu)代表：AGNES(自底向上)，DIANA(自頂向下)常見聚類方法?亦稱“基于原型的聚類”(prototype-b8k-means每個簇以該簇中所有樣本點的“均值”表示

Step1:隨機選取k個樣本點作為簇中心Step2:將其他樣本點根據(jù)其與簇中心的距離，劃分給最近的簇Step3:更新各簇的均值向量，將其作為新的簇中心Step4:若所有簇中心未發(fā)生改變，則停止；否則執(zhí)行Step2若不以均值向量為原型，而是以距離它最近的樣本點為原型，則得到k-medoids算法k-means每個簇以該簇中所有樣本點的“均值”表示Step9高斯混合聚類(GausianMixtureClustering,GMM)?根據(jù)定義的先驗分布選擇高斯混合成分，其中

為選擇第i個混合成分的概率；?然后，根據(jù)被選擇的混合成分的概率密度函數(shù)進行采樣，從而生 成相應(yīng)的樣本采用概率模型來表達聚類原型

n維樣本空間中的隨機 向量x若服從高斯分布， 則其概率密度函數(shù)為假設(shè)樣本由下面這個高斯混合分布生成：

生成式模型高斯混合聚類(GausianMixtureCluster10高斯混合聚類（續(xù)）樣本xj由第i個高斯混合成分生成的后驗概率為：簡記為參數(shù)估計可采用極大似然法，考慮最大化對數(shù)似然EM算法：?(E步)根據(jù)當(dāng)前參數(shù)計算每個樣本屬于每個高斯成分的后驗概率?(M步)更新模型參數(shù)高斯混合聚類（續(xù)）樣本xj由第i個高斯混合成分生成11集成學(xué)習(xí)(Ensemblelearning)集成學(xué)習(xí)通過構(gòu)建并結(jié)合多個學(xué)習(xí)器來完成學(xué)習(xí)任務(wù)…...Problem …...ProblemLearnerLearnerLearnerLearner同質(zhì)(homogeneous)集成：集成中只包含同種類型的“個體學(xué)習(xí)器”

相應(yīng)的學(xué)習(xí)算法稱為“基學(xué)習(xí)算法”(baselearningalgorithm)

個體學(xué)習(xí)器亦稱“基學(xué)習(xí)器”(baselearner)異質(zhì)(heterogeneous)集成：個體學(xué)習(xí)器由不同的學(xué)習(xí)算法生成

不存在“基學(xué)習(xí)算法”集成學(xué)習(xí)(Ensemblelearning)集成學(xué)習(xí)通過構(gòu)12WhyEnsemble?

集成的泛化性能通常顯著優(yōu)于單個學(xué)習(xí)器的泛化性能一組神經(jīng)網(wǎng)絡(luò)的平均性能

選擇最優(yōu)神經(jīng)網(wǎng)絡(luò)

兩種簡單的神經(jīng)網(wǎng)絡(luò) 集成方法

一個觀察：誤差（曲線越低越好）

[Hansen&Salamon,TPAMI90]WhyEnsemble?一組神經(jīng)網(wǎng)絡(luò)的平均性能 一個觀察：13令個體學(xué)習(xí)器“好而不同”如何得到好的集成？想獲勝，用集成現(xiàn)實各類機器學(xué)習(xí)、數(shù)據(jù)挖掘應(yīng)用中，廣泛使用集成學(xué)習(xí)技術(shù)令個體學(xué)習(xí)器“好而不同”如何得到好的集成？想獲勝，用集成現(xiàn)14很多成功的集成學(xué)習(xí)方法

序列化方法[Freund&Schapire,JCSS97][Friedman,AnnStat01][Demiriz,Bennett,Shawe-Taylor,MLJ06]

?AdaBoost

?GradientBoost ?LPBoost ?……并行化方法[Breiman,MLJ96][Breiman,MLJ01][Ho,TPAMI98]?Bagging?RandomForest?RandomSubspace?……很多成功的集成學(xué)習(xí)方法[Freund&Schapire,15Dataset1Dataset2DatasetTLearner1Learner2LearnerT…...…...…...byLearner1willplaymoreimportantrolesinthetrainingofLearner2weightedcombinationOriginaltrainingsetBoosting:Aflowchartillustration

traininginstancesthatarewronglypredictedDataset1Dataset2DatasetT16BaggingDataset0Dataset1Dataset2Datasetn…...…...…...bootstrapasetoflearnersgeneratemanydatasetsfromtheoriginaldatasetthroughbootstrapsampling(randomsamplingwithreplacement),thentrainanindividuallearnerperdatasetaveragingforregressiontheoutputistheaverageoutputoftheindividuallearnersvotingforclassificationtheoutputistheclasslabelreceivingthemostnumberofvotesLearner1Learner2LearnernBaggingDataset0Dataset1Data17學(xué)習(xí)器結(jié)合常用結(jié)合方法：投票法?絕對多數(shù)投票法?相對多數(shù)投票法?加權(quán)投票法平均法?簡單平均法?加權(quán)平均法學(xué)習(xí)法學(xué)習(xí)器結(jié)合常用結(jié)合方法：投票法平均法18StackingStacking19多樣性

“多樣性”(diversity)是集成學(xué)習(xí)的關(guān)鍵(error-ambiguitydecomposition):誤差-分歧分解

多樣性度量一般通過兩分類器的預(yù)測結(jié)果列聯(lián)表定義????不合度量(disagreementmeasure)相關(guān)系數(shù)(correlationcoefficient)Q-統(tǒng)計量(Q-statistic)κ-統(tǒng)計量（κ-statistic）?……κ-誤差圖每一對分類器作為圖中的一個點多樣性(error-ambiguitydecomposit20多樣性增強常用策略

數(shù)據(jù)樣本擾動

?例如Adaboost使用重要性采樣、Bagging使用自助采樣?注意：對“不穩(wěn)定基學(xué)習(xí)器”(如決策樹、神經(jīng)網(wǎng)絡(luò)等)很有效

不適用于“穩(wěn)定基學(xué)習(xí)器”（如線性分類器、SVM、樸素貝葉斯等）輸入屬性擾動?例如隨機子空間(RandomSubspace)輸出表示擾動

?例如輸出標記隨機翻轉(zhuǎn)、分類轉(zhuǎn)回歸、ECOC算法參數(shù)擾動多樣性增強常用策略?注意：對“不穩(wěn)定基學(xué)習(xí)器”(如決策樹、21“越多越好”？選擇性集成(selectiveensemble):給定一組個體學(xué)習(xí)器，從中選擇一部分來構(gòu)建集成，經(jīng)常會比使用所有個體學(xué)習(xí)器更好(更小的存儲/時間開銷，更強的泛化性能)ProblemLearner

…...Learner…...Learner集成修剪(ensemblepruning)[Margineantu&Dietterich,ICML’97]較早出現(xiàn)，針對序列型集成

減小集成規(guī)模、降低泛化性能選擇性集成[Zhou,etal,AIJ02]稍晚，針對并行型集成，MCBTA(Manycouldbebetterthanall)定理

減小集成規(guī)模、增強泛化性能目前“集成修剪”與“選擇性集成