數(shù)據(jù)挖據(jù)技術(shù)集成學(xué)習(xí)方法(ensemblelearnig).ppt

數(shù)據(jù)挖據(jù)技術(shù)集成學(xué)習(xí)方法 ensemblelearnig 王磊 副教授 經(jīng)濟(jì)信息工程學(xué)院 2 2 第六章 集成學(xué)習(xí)方法 基本概念baggingboosting隨機(jī)森林選擇性集成方法 在機(jī)器學(xué)習(xí)中 直接建立一個(gè)高性能的分類(lèi)器是很困難的 但是 如果能找到一系列性能較差的分類(lèi)器 弱分類(lèi)器 并把它們集成起來(lái)的話 也許就能得到更好的分類(lèi)器 日常生活中 三個(gè)臭皮匠 勝過(guò)諸葛亮 便是體現(xiàn)了這種思想 集成學(xué)習(xí)的基本概念 集成學(xué)習(xí) 圖示 我們一般選定加權(quán)平均的方法來(lái)構(gòu)造集成學(xué)習(xí)的最終學(xué)習(xí)器 但是里面的每一個(gè)弱分類(lèi)器 i 怎樣構(gòu)造呢 有一些研究 是針對(duì)每個(gè)學(xué)習(xí)器都不同構(gòu)的情況 比如識(shí)別一個(gè)人 一個(gè)學(xué)習(xí)器考慮臉 另一個(gè)考慮步態(tài) 另一個(gè)考慮指紋 這種研究通常稱為InformationFusion 不在我們今天討論的范疇 狹義的集成學(xué)習(xí) ensemblelearning 是用同樣類(lèi)型的學(xué)習(xí)算法來(lái)構(gòu)造不同的弱學(xué)習(xí)器的方法 集成學(xué)習(xí) 如何構(gòu)造 辦法就是改變訓(xùn)練集 通常的學(xué)習(xí)算法 根據(jù)訓(xùn)練集的不同 會(huì)給出不同的學(xué)習(xí)器 這時(shí)就可以通過(guò)改變訓(xùn)練集來(lái)構(gòu)造不同的學(xué)習(xí)器 然后再把它們集成起來(lái) 集成學(xué)習(xí) 如何構(gòu)造 在原來(lái)的訓(xùn)練集上隨機(jī)采樣 可以得到新的訓(xùn)練集 隨機(jī)采樣 集成學(xué)習(xí) EnsembleLearning 是一種機(jī)器學(xué)習(xí)方法 它使用多個(gè) 通常是同質(zhì)的 學(xué)習(xí)器來(lái)解決同一個(gè)問(wèn)題 集成學(xué)習(xí)中使用的多個(gè)學(xué)習(xí)器稱為個(gè)體學(xué)習(xí)器當(dāng)個(gè)體學(xué)習(xí)器均為決策樹(shù)時(shí) 稱為 決策樹(shù)集成 當(dāng)個(gè)體學(xué)習(xí)器均為神經(jīng)網(wǎng)絡(luò)時(shí) 稱為 神經(jīng)網(wǎng)絡(luò)集成 集成學(xué)習(xí)的定義 由于集成學(xué)習(xí)技術(shù)可以有效地提高學(xué)習(xí)系統(tǒng)的泛化能力 因此它成為國(guó)際機(jī)器學(xué)習(xí)界的研究熱點(diǎn) 并被國(guó)際權(quán)威T G Dietterich稱為當(dāng)前機(jī)器學(xué)習(xí)四大研究方向之首 T G Dietterich AIMag97 問(wèn)題 對(duì)20維超立方體空間中的區(qū)域分類(lèi)左圖中縱軸為錯(cuò)誤率從上到下的四條線分別表示 平均神經(jīng)網(wǎng)絡(luò)錯(cuò)誤率最好神經(jīng)網(wǎng)絡(luò)錯(cuò)誤率兩種神經(jīng)網(wǎng)絡(luò)集成的錯(cuò)誤率令人驚奇的是 集成的錯(cuò)誤率比最好的個(gè)體還低 L K Hansen P Salamon TPAMI90 集成學(xué)習(xí)的重要性 集成學(xué)習(xí)技術(shù)已經(jīng)在行星探測(cè) 地震波分析 Web信息過(guò)濾 生物特征識(shí)別 計(jì)算機(jī)輔助醫(yī)療診斷等眾多領(lǐng)域得到了廣泛的應(yīng)用 只要能用到機(jī)器學(xué)習(xí)的地方 就能用到集成學(xué)習(xí) 集成學(xué)習(xí)的應(yīng)用 如何構(gòu)建好的集成 既然多個(gè)個(gè)體的集成比單個(gè)個(gè)體更好 那么是不是個(gè)體越多越好 更多的個(gè)體意味著 在預(yù)測(cè)時(shí)需要更大的計(jì)算開(kāi)銷(xiāo) 因?yàn)橐?jì)算更多的個(gè)體預(yù)測(cè)更大的存儲(chǔ)開(kāi)銷(xiāo) 因?yàn)橛懈嗟膫€(gè)體需要保存 個(gè)體的增加將使得個(gè)體間的差異越來(lái)越難以獲得 個(gè)體越多越好嗎 集成策略 有多種策略可以將q個(gè)弱分類(lèi)器組合成集成分類(lèi)器 集成策略 從大小為n的原始數(shù)據(jù)集D中獨(dú)立隨機(jī)地抽取n 個(gè)數(shù)據(jù) n n 形成一個(gè)自助數(shù)據(jù)集 重復(fù)上述過(guò)程 產(chǎn)生出多個(gè)獨(dú)立的自助數(shù)據(jù)集 利用每個(gè)自助數(shù)據(jù)集訓(xùn)練出一個(gè) 分量分類(lèi)器 最終的分類(lèi)結(jié)果由這些 分量分類(lèi)器 各自的判別結(jié)果投票決定 基本思想 對(duì)訓(xùn)練集有放回地抽取訓(xùn)練樣例 從而為每一個(gè)基本分類(lèi)器都構(gòu)造出一個(gè)跟訓(xùn)練集相當(dāng)大小但各不相同的訓(xùn)練集 從而訓(xùn)練出不同的基本分類(lèi)器 該算法是基于對(duì)訓(xùn)練集進(jìn)行處理的集成方法中最簡(jiǎn)單 最直觀的一種 Bagging算法 Bagging算法 Boosting算法 Boosting流程描述 Step1 原始訓(xùn)練集輸入Step2 計(jì)算訓(xùn)練集中各樣本的權(quán)重Step3 采用已知算法訓(xùn)練弱學(xué)習(xí)機(jī) 并對(duì)每個(gè)樣本進(jìn)行判別Step4 計(jì)算對(duì)此次的弱學(xué)習(xí)機(jī)的權(quán)重Step5 轉(zhuǎn)到Step2 直到循環(huán)到達(dá)一定次數(shù)或者某度量標(biāo)準(zhǔn)符合要求Step6 將弱學(xué)習(xí)機(jī)按其相應(yīng)的權(quán)重加權(quán)組合形成強(qiáng)學(xué)習(xí)機(jī) 核心思想 樣本的權(quán)重沒(méi)有先驗(yàn)知識(shí)的情況下 初始的分布應(yīng)為等概分布 也就是訓(xùn)練集如果有N個(gè)樣本 每個(gè)樣本的分布概率為1 N每次循環(huán)一后提高錯(cuò)誤樣本的分布概率 分錯(cuò)樣本在訓(xùn)練集中所占權(quán)重增大 使得下一次循環(huán)的弱學(xué)習(xí)機(jī)能夠集中力量對(duì)這些錯(cuò)誤樣本進(jìn)行判斷 弱學(xué)習(xí)機(jī)的權(quán)重準(zhǔn)確率越高的弱學(xué)習(xí)機(jī)權(quán)重越高循環(huán)控制 損失函數(shù)達(dá)到最小在強(qiáng)學(xué)習(xí)機(jī)的組合中增加一個(gè)加權(quán)的弱學(xué)習(xí)機(jī) 使準(zhǔn)確率提高 損失函數(shù)值減小 簡(jiǎn)單問(wèn)題演示 Boosting訓(xùn)練過(guò)程 算法 boosting數(shù)學(xué)描述 訓(xùn)練集 x1 y1 x2 y2 xN yN xi Rm yi 1 1 Dt為第t次循環(huán)時(shí)的訓(xùn)練樣本分布 每個(gè)樣本在訓(xùn)練集中所占的概率 Dt總和應(yīng)該為1 ht X 1 1 為第t次循環(huán)時(shí)的Weaklearner 對(duì)每個(gè)樣本給出相應(yīng)的假設(shè) 應(yīng)該滿足強(qiáng)于隨機(jī)猜測(cè) wt為ht的權(quán)重為t次循環(huán)得到的Stronglearner 樣本權(quán)重 思想 提高分錯(cuò)樣本的權(quán)重反映了stronglearner對(duì)樣本的假設(shè)是否正確采用什么樣的函數(shù)形式 弱學(xué)習(xí)機(jī)權(quán)重 思想 錯(cuò)誤率越低 該學(xué)習(xí)機(jī)的權(quán)重應(yīng)該越大為學(xué)習(xí)機(jī)的錯(cuò)誤概率采用什么樣的函數(shù)形式 和指數(shù)函數(shù)遙相呼應(yīng) AdaBoost算法 25 Adaboost訓(xùn)練過(guò)程 26 Adaboost訓(xùn)練過(guò)程 27 Adaboost訓(xùn)練過(guò)程 Adaboost的缺點(diǎn) 隨機(jī)森林算法 隨機(jī)森林算法是LeoBreiman于2001年提出的一種新型分類(lèi)和預(yù)測(cè)模型 它具有需要調(diào)整的參數(shù)少 不容易過(guò)度擬合 分類(lèi)速度快 能高效處理大樣本數(shù)據(jù)等特點(diǎn) Bagging和AdaBoost等方法只是通過(guò)改變樣本的權(quán)重來(lái)獲得不同的弱分類(lèi)器 隨機(jī)森林 RF 則通過(guò)同時(shí)改變樣本和特征子集來(lái)獲得不同的弱分類(lèi)器 隨機(jī)森林算法 隨機(jī)森林是采用隨機(jī)的方式建立一個(gè)森林 森林有很多決策樹(shù)組成 每棵決策樹(shù)之間沒(méi)有關(guān)聯(lián) 對(duì)于新的測(cè)試樣本 讓森林中的每一棵決策樹(shù)分布分別進(jìn)行一下判斷 依據(jù)多數(shù)者投票方法決定樣本的類(lèi)別 完全分裂的方式 隨機(jī)特征選取 當(dāng)特征個(gè)數(shù)M較多時(shí) 隨機(jī)選擇m個(gè)用于訓(xùn)練決策樹(shù) m越小 樹(shù)的相關(guān)性越小 且訓(xùn)練速度越快 當(dāng)特征個(gè)數(shù)M較少時(shí) 可以由M個(gè)特征進(jìn)行隨機(jī)線性組合來(lái)產(chǎn)生M 個(gè)擴(kuò)展特征 然后 在 M M 上隨機(jī)選擇m個(gè)特征 構(gòu)建決策樹(shù) 其中 每一個(gè)擴(kuò)展特征的構(gòu)造如下 從現(xiàn)有M特征中隨機(jī)抽取L個(gè) 它們的權(quán)重系數(shù)是 1 1 區(qū)間的均勻隨機(jī)數(shù) 然后 由L個(gè)已有特征線性組合出擴(kuò)展特征 隨機(jī)特征數(shù)的確定 選擇性集成算法 一方面 使用更多的學(xué)習(xí)器將導(dǎo)致更大的計(jì)算和存儲(chǔ)開(kāi)銷(xiāo) 另一方面 當(dāng)個(gè)體學(xué)習(xí)器數(shù)目增加之后 學(xué)習(xí)器之間的差異將越來(lái)越難以獲得 因此 提出問(wèn)題 為了達(dá)到更好的性能 是否必須使用更多的個(gè)體學(xué)習(xí)器 選擇性集成的理論分析 選擇性集成的理論分析 選擇性集成的理論分析 選擇性集成的理論分析 問(wèn)題求解 問(wèn)題求解 GASEN算法 論文講解 基于約束投影的支持向量機(jī)選擇性集成 2009 研究題目