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

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

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

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

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

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

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

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

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

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

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

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

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

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

一個(gè)觀察：誤差（曲線越低越好）

[Hansen&Salamon,TPAMI90]WhyEnsemble?一組神經(jīng)網(wǎng)絡(luò)的平均性能 一個(gè)觀察：13令個(gè)體學(xué)習(xí)器“好而不同”如何得到好的集成？想獲勝，用集成現(xiàn)實(shí)各類機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘應(yīng)用中，廣泛使用集成學(xué)習(xí)技術(shù)令個(gè)體學(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é)合方法：投票法?絕對(duì)多數(shù)投票法?相對(duì)多數(shù)投票法?加權(quán)投票法平均法?簡(jiǎn)單平均法?加權(quán)平均法學(xué)習(xí)法學(xué)習(xí)器結(jié)合常用結(jié)合方法：投票法平均法18StackingStacking19多樣性

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

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

數(shù)據(jù)樣本擾動(dòng)

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

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

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

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

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

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