第10章-聚類與集成算法-圖文

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

既可以作為一個單獨過程（用于找尋數(shù)據(jù)內在的分布結構） 也可作為分類等其他學習任務的前驅過程性能度量聚類性能度量，亦稱聚類“有效性指標”(validityindex)

外部指標(externalindex)將聚類結果與某個“參考模型”(referencemodel)進行比較如Jaccard系數(shù)，F(xiàn)M指數(shù)，Rand指數(shù)

內部指標(internalindex)直接考察聚類結果而不用任何參考模型如DB指數(shù)，Dunn指數(shù)等基本想法：?“簇內相似度”（intra-clustersimilarity）高，且?“簇間相似度”（inter-clustersimilarity）低距離計算距離度量(distancemetric)需滿足的基本性質：常用距離形式：閔可夫斯基距離(Minkowskidistance)p=2:歐氏距離(Euclideandistance)p=1:曼哈頓距離(Manhattandistance)距離計算(續(xù)）

對無序(non-ordinal)屬性，可使用VDM(ValueDifferenceMetric)令表示屬性u上取值為a的樣本數(shù)，表示在第i個樣本

簇中在屬性u上取值為a的樣本數(shù)，k為樣本簇數(shù)，則屬性u上兩個 離散值a與b之間的VDM距離為

對混合屬性，可使用MinkovDM必須記住聚類的“好壞”不存在絕對標準thegoodnessofclusteringdependsontheopinionoftheuser故事一則聚類的故事：老師拿來蘋果和梨，讓小朋友分成兩份。小明把大蘋果大梨放一起，小個頭的放一起，老師點頭，恩，體量感。小芳把紅蘋果挑出來，剩下的放一起，老師點頭，顏色感。小武的結果？不明白。小武掏出眼鏡：最新款，能看到水果里有幾個籽，左邊這堆單數(shù)，右邊雙數(shù)。老師很高興：新的聚類算法誕生了聚類也許是機器學習中“新算法”出現(xiàn)最多、最快的領域 總能找到一個新的“標準”，使以往算法對它無能為力常見聚類方法

原型聚類????亦稱“基于原型的聚類”(prototype-basedclustering)假設：聚類結構能通過一組原型刻畫過程：先對原型初始化，然后對原型進行迭代更新求解代表：k均值聚類，學習向量量化(LVQ)，高斯混合聚類

密度聚類????亦稱“基于密度的聚類”(density-basedclustering)假設：聚類結構能通過樣本分布的緊密程度確定過程：從樣本密度的角度來考察樣本之間的可連接性，并基于可連接樣本不斷擴展聚類簇代表：DBSCAN,OPTICS,DENCLUE

層次聚類(hierarchicalclustering)???假設：能夠產(chǎn)生不同粒度的聚類結果過程：在不同層次對數(shù)據(jù)集進行劃分，從而形成樹形的聚類結構代表：AGNES(自底向上)，DIANA(自頂向下)k-means每個簇以該簇中所有樣本點的“均值”表示

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

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

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

生成式模型高斯混合聚類（續(xù)）樣本xj由第i個高斯混合成分生成的后驗概率為：簡記為參數(shù)估計可采用極大似然法，考慮最大化對數(shù)似然EM算法：?(E步)根據(jù)當前參數(shù)計算每個樣本屬于每個高斯成分的后驗概率?(M步)更新模型參數(shù)集成學習(Ensemblelearning)集成學習通過構建并結合多個學習器來完成學習任務…...Problem …...ProblemLearnerLearnerLearnerLearner

同質(homogeneous)集成：集成中只包含同種類型的“個體學習器”

相應的學習算法稱為“基學習算法”(baselearningalgorithm)

個體學習器亦稱“基學習器”(baselearner)

異質(heterogeneous)集成：個體學習器由不同的學習算法生成

不存在“基學習算法”WhyEnsemble?

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

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

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

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

[Hansen&Salamon,TPAMI90]令個體學習器“好而不同”如何得到好的集成？想獲勝，用集成現(xiàn)實各類機器學習、數(shù)據(jù)挖掘應用中，廣泛使用集成學習技術很多成功的集成學習方法

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

?AdaBoost

?GradientBoost ?LPBoost ?……

并行化方法[Breiman,MLJ96][Breiman,MLJ01][Ho,TPAMI98]?Bagging?RandomForest?RandomSubspace?……Dataset1Dataset2DatasetTLearner1Learner2LearnerT…...…...…...byLearner1willplaymoreimportantrolesinthetrainingofLearner2weightedcombinationOriginaltrainingsetBoosting:Aflowchartillustration

traininginstancesthatarewronglypredictedBaggingDataset0Dataset1Dataset2Datasetn…...…...…...bootstrapasetoflearnersgeneratemanydatasetsfromtheoriginaldatasetthroughbootstrapsampling(randomsamplingwithreplacement),thentrainanindividuallearnerperdatasetaveragingforregressiontheoutputistheaverageoutputoftheindividuallearnersvotingforclassificationtheoutputistheclasslabelreceivingthemostnumberofvotesLearner1Learner2Learnern學習器結合常用結合方法：

投票法?絕對多數(shù)投票法?相對多數(shù)投票法?加權投票法

平均法?簡單平均法?加權平均法

學習法Stacking多樣性

“多樣性”(diversity)是集成學習的關鍵(error-ambiguitydecomposition):誤差-分歧分解

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

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

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

不適用于“穩(wěn)定基學習器”（如線性分類器、SVM、樸素貝葉斯等）

輸入屬性擾動?例如隨機子空間(RandomSubspace)

輸出表示擾動

?例如輸出標記隨機翻轉、分類轉回歸、ECOC

算法參數(shù)擾動“越多越好”？選擇性集成(selectiveensemble):給定一組個體學習器，從中選擇一部分來構建集成，經(jīng)常會比使用所有個體學習器更好(更小的存儲/時間開銷，更強的泛化性能)ProblemLearner

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

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

減小