數(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è)高性能的分類器是很困難的 但是 如果能找到一系列性能較差的分類器 弱分類器 并把它們集成起來的話 也許就能得到更好的分類器 日常生活中 三個(gè)臭皮匠 勝過諸葛亮 便是體現(xiàn)了這種思想 集成學(xué)習(xí)的基本概念 集成學(xué)習(xí) 圖示 我們一般選定加權(quán)平均的方法來構(gòu)造集成學(xué)習(xí)的最終學(xué)習(xí)器 但是里面的每一個(gè)弱分類器 i 怎樣構(gòu)造呢 有一些研究 是針對每個(gè)學(xué)習(xí)器都不同構(gòu)的情況 比如識(shí)別一個(gè)人 一個(gè)學(xué)習(xí)器考慮臉 另一個(gè)考慮步態(tài) 另一個(gè)考慮指紋 這種研究通常稱為InformationFusion 不在我們今天討論的范疇 狹義的集成學(xué)習(xí) ensemblelearning 是用同樣類型的學(xué)習(xí)算法來構(gòu)造不同的弱學(xué)習(xí)器的方法 集成學(xué)習(xí) 如何構(gòu)造 辦法就是改變訓(xùn)練集 通常的學(xué)習(xí)算法 根據(jù)訓(xùn)練集的不同 會(huì)給出不同的學(xué)習(xí)器 這時(shí)就可以通過改變訓(xùn)練集來構(gòu)造不同的學(xué)習(xí)器 然后再把它們集成起來 集成學(xué)習(xí) 如何構(gòu)造 在原來的訓(xùn)練集上隨機(jī)采樣 可以得到新的訓(xùn)練集 隨機(jī)采樣 集成學(xué)習(xí) EnsembleLearning 是一種機(jī)器學(xué)習(xí)方法 它使用多個(gè) 通常是同質(zhì)的 學(xué)習(xí)器來解決同一個(gè)問題 集成學(xué)習(xí)中使用的多個(gè)學(xué)習(xí)器稱為個(gè)體學(xué)習(xí)器當(dāng)個(gè)體學(xué)習(xí)器均為決策樹時(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)的泛化能力 因此它成為國際機(jī)器學(xué)習(xí)界的研究熱點(diǎn) 并被國際權(quán)威T G Dietterich稱為當(dāng)前機(jī)器學(xué)習(xí)四大研究方向之首 T G Dietterich AIMag97 問題 對20維超立方體空間中的區(qū)域分類左圖中縱軸為錯(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)在行星探測 地震波分析 Web信息過濾 生物特征識(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ù)測時(shí)需要更大的計(jì)算開銷 因?yàn)橐?jì)算更多的個(gè)體預(yù)測更大的存儲(chǔ)開銷 因?yàn)橛懈嗟膫€(gè)體需要保存 個(gè)體的增加將使得個(gè)體間的差異越來越難以獲得 個(gè)體越多越好嗎 集成策略 有多種策略可以將q個(gè)弱分類器組合成集成分類器 集成策略 從大小為n的原始數(shù)據(jù)集D中獨(dú)立隨機(jī)地抽取n 個(gè)數(shù)據(jù) n n 形成一個(gè)自助數(shù)據(jù)集 重復(fù)上述過程 產(chǎn)生出多個(gè)獨(dú)立的自助數(shù)據(jù)集 利用每個(gè)自助數(shù)據(jù)集訓(xùn)練出一個(gè) 分量分類器 最終的分類結(jié)果由這些 分量分類器 各自的判別結(jié)果投票決定 基本思想 對訓(xùn)練集有放回地抽取訓(xùn)練樣例 從而為每一個(gè)基本分類器都構(gòu)造出一個(gè)跟訓(xùn)練集相當(dāng)大小但各不相同的訓(xùn)練集 從而訓(xùn)練出不同的基本分類器 該算法是基于對訓(xùn)練集進(jìn)行處理的集成方法中最簡單 最直觀的一種 Bagging算法 Bagging算法 Boosting算法 Boosting流程描述 Step1 原始訓(xùn)練集輸入Step2 計(jì)算訓(xùn)練集中各樣本的權(quán)重Step3 采用已知算法訓(xùn)練弱學(xué)習(xí)機(jī) 并對每個(gè)樣本進(jìn)行判別Step4 計(jì)算對此次的弱學(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)重沒有先驗(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ī)能夠集中力量對這些錯(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ù)值減小 簡單問題演示 Boosting訓(xùn)練過程 算法 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 對每個(gè)樣本給出相應(yīng)的假設(shè) 應(yīng)該滿足強(qiáng)于隨機(jī)猜測 wt為ht的權(quán)重為t次循環(huán)得到的Stronglearner 樣本權(quán)重 思想 提高分錯(cuò)樣本的權(quán)重反映了stronglearner對樣本的假設(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)練過程 26 Adaboost訓(xùn)練過程 27 Adaboost訓(xùn)練過程 Adaboost的缺點(diǎn) 隨機(jī)森林算法 隨機(jī)森林算法是LeoBreiman于2001年提出的一種新型分類和預(yù)測模型 它具有需要調(diào)整的參數(shù)少 不容易過度擬合 分類速度快 能高效處理大樣本數(shù)據(jù)等特點(diǎn) Bagging和AdaBoost等方法只是通過改變樣本的權(quán)重來獲得不同的弱分類器 隨機(jī)森林 RF 則通過同時(shí)改變樣本和特征子集來獲得不同的弱分類器 隨機(jī)森林算法 隨機(jī)森林是采用隨機(jī)的方式建立一個(gè)森林 森林有很多決策樹組成 每棵決策樹之間沒有關(guān)聯(lián) 對于新的測試樣本 讓森林中的每一棵決策樹分布分別進(jìn)行一下判斷 依據(jù)多數(shù)者投票方法決定樣本的類別 完全分裂的方式 隨機(jī)特征選取 當(dāng)特征個(gè)數(shù)M較多時(shí) 隨機(jī)選擇m個(gè)用于訓(xùn)練決策樹 m越小 樹的相關(guān)性越小 且訓(xùn)練速度越快 當(dāng)特征個(gè)數(shù)M較少時(shí) 可以由M個(gè)特征進(jìn)行隨機(jī)線性組合來產(chǎn)生M 個(gè)擴(kuò)展特征 然后 在 M M 上隨機(jī)選擇m個(gè)特征 構(gòu)建決策樹 其中 每一個(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ǔ)開銷 另一方面 當(dāng)個(gè)體學(xué)習(xí)器數(shù)目增加之后 學(xué)習(xí)器之間的差異將越來越難以獲得 因此 提出問題 為了達(dá)到更好的性能 是否必須使用更多的個(gè)體學(xué)習(xí)器 選擇性集成的理論分析 選擇性集成的理論分析 選擇性集成的理論分析 選擇性集成的理論分析 問題求解 問題求解 GASEN算法 論文講解 基于約束投影的支持向量機(jī)選擇性集成 2009 研究題目