Chapter 4: 決策樹(decision tree)
- what is decision tree精拟?
基本流程
遵循分而治之(divide-and-conquer)策略,決策樹學(xué)習(xí)基本算法如下:
- <決策樹學(xué)習(xí)基本算法.jpg>
- 算法line 8th, 如何選擇最優(yōu)劃分屬性?
劃分選擇
應(yīng)使決策樹的分支節(jié)點(diǎn)所包含的樣本盡可能屬于同一類別, 即節(jié)點(diǎn)的"純度(purity)"越高越好.
信息增益(information gain)
信息熵(information entropy)是度量樣本集合純度的常用指標(biāo).
算法line 8th選擇屬性 .
信息增益對可取值數(shù)目較多的屬性有所偏好.增益率(gain ratio)
其中,
增益率準(zhǔn)則對可取值數(shù)目較少的屬性有所偏好.
- C4.5算法使用啟發(fā)式: 先從后選劃分屬性中找出信息增益高于平均水平的屬性, 再從中選擇增益率最高的.
- 基尼指數(shù)(gini index)
數(shù)據(jù)集D的純度使用基尼值測量: .
Gini(D)反映了從數(shù)據(jù)集D中隨機(jī)抽取兩個(gè)樣本, 其類別標(biāo)記不一致的概率, 故Gini(D)越小, 數(shù)據(jù)集D的純度越高.
屬性a的基尼指數(shù)定義為: .
選擇劃分后基尼指數(shù)最小的屬性作為最優(yōu)劃分屬性: .
- Cart決策樹使用"基尼指數(shù)"選擇劃分屬性.
剪枝(pruning)處理
剪枝是決策樹學(xué)習(xí)算法中解決"過擬合"的主要手段, 基本策略如下:
-
prepruning, 預(yù)剪枝: 在決策樹生成過程中, 對每個(gè)節(jié)點(diǎn)在劃分前先進(jìn)行估計(jì), 若當(dāng)前節(jié)點(diǎn)的劃分不能帶來決策樹泛化性能提升, 則停止劃分并將當(dāng)前節(jié)點(diǎn)標(biāo)記為葉節(jié)點(diǎn).
- 降低了過擬合的風(fēng)險(xiǎn), 減少了決策樹的訓(xùn)練時(shí)間開銷和測試時(shí)間開銷.
- 帶來了欠擬合的風(fēng)險(xiǎn).
-
postpruning, 后剪枝: 先從訓(xùn)練集生成一棵完整的決策樹, 然后自底向上地對非葉節(jié)點(diǎn)進(jìn)行考察, 若將該節(jié)點(diǎn)對應(yīng)的子樹替換為葉節(jié)點(diǎn)能帶來決策樹泛化性能提升, 則將該子樹替換為葉節(jié)點(diǎn).
- 欠擬合風(fēng)險(xiǎn)小, 泛化性能往往由于預(yù)剪枝決策樹.
- 訓(xùn)練時(shí)間開銷比未剪枝決策樹和預(yù)剪枝決策樹都要大得多.
連續(xù)與缺失值
連續(xù)
在決策樹學(xué)習(xí)中, 若遇到連續(xù)屬性值, 可通過二分法(bi-partition)進(jìn)行處理, 即將出現(xiàn)的連續(xù)屬性的取值從小到大進(jìn)行排序, 基于某個(gè)劃分點(diǎn)t將D分為子集(包含屬性a上取值大于t的樣本)和(包含屬性a上取值不大于t的樣本).
如何選擇最優(yōu)的劃分點(diǎn):
其中 Gain(D,a,t)是樣本集D基于劃分點(diǎn)t二分后的信息增益, 選擇使 Gain(D,a,t)最大化的劃分點(diǎn).
note: 若當(dāng)前節(jié)點(diǎn)劃分屬性為連續(xù)屬性, 該屬性還可作為其后代節(jié)點(diǎn)的劃分屬性.缺失值
- Q: 如何在屬性值缺失的情況下進(jìn)行劃分屬性選擇?
給定劃分屬性, 若樣本在該屬性上的值確實(shí), 如何對樣本進(jìn)行劃分?
計(jì)算信息增益時(shí)帶入不缺失該屬性的樣本所占的比例. 具體推廣后的公式此處略.
多變量決策樹(multivariate decision tree)
若把每個(gè)屬性視為坐標(biāo)空間中的一個(gè)坐標(biāo)軸, 則d個(gè)屬性描述的樣本對應(yīng)了d維空間中的一個(gè)數(shù)據(jù)點(diǎn), 對樣本分類意味著這個(gè)坐標(biāo)空間中尋找不同類樣本之間的分類邊界, 決策樹所形成的的分類邊界具有特點(diǎn): 軸平行(axis-parallel), 即分類邊界由若干個(gè)與坐標(biāo)軸平衡的分段組成.
多變量決策樹: 能實(shí)現(xiàn)斜劃分或者更復(fù)雜劃分的決策樹. (需要對屬性的線性組合進(jìn)行分析.)
Chapter 5: 神經(jīng)網(wǎng)絡(luò)(neural networks)
神經(jīng)元(neuron)模型
神經(jīng)元是神經(jīng)網(wǎng)絡(luò)中最基本的單元. 神經(jīng)元接收到來自n個(gè)其他神經(jīng)元傳遞過來的輸入信號, 這些輸入信號通過帶權(quán)重的連接進(jìn)行傳遞, 神經(jīng)元接收到的總輸入值與該神經(jīng)元的閾值(threshold)進(jìn)行比較, 然后通過"激活函數(shù)(activation function)"處理以產(chǎn)生神經(jīng)元的輸出.理想的激活函數(shù)是階躍函數(shù), 但其不連續(xù)、不光滑, 常用Sigmoid函數(shù)(亦稱擠壓函數(shù), squashing function)作為激活函數(shù).
許多個(gè)這樣的神經(jīng)元按一定的層次結(jié)構(gòu)連接起來, 就得到了一個(gè)神經(jīng)網(wǎng)絡(luò). 可將神經(jīng)網(wǎng)絡(luò)視為包含了許多參數(shù)的數(shù)學(xué)模型, 這個(gè)模型是若干個(gè)數(shù)學(xué)函數(shù)(如 )相互嵌套而成.
感知機(jī)與多層網(wǎng)絡(luò)
perceptron, 感知機(jī): 由兩層神經(jīng)元組成, 輸入層接受外界輸入信號后傳遞給輸出層. 輸出層是M-P神經(jīng)元, 亦稱閾值邏輯單元(threshold logic unit). 感知機(jī)能容易地實(shí)現(xiàn)邏輯與、或鉴未、非運(yùn)算. 神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)過程就是對神經(jīng)元的連接權(quán)重和每個(gè)功能神經(jīng)元的閾值進(jìn)行學(xué)習(xí). 將閾值看成固定輸入為-1.0的啞結(jié)點(diǎn)(dummy node)所對應(yīng)的權(quán)重wn+1<>\sub, 則將參數(shù)都統(tǒng)一為權(quán)重的學(xué)習(xí). 對訓(xùn)練樣例(x, y), 若當(dāng)前感知機(jī)的輸出為y', 則感知機(jī)權(quán)重調(diào)整規(guī)則如下:
, 其中, 其中稱為學(xué)習(xí)率(learning rate).
感知機(jī)只能解決線性可分問題. 要解決非線性可分問題, 需使用多層功能神經(jīng)元.(兩層網(wǎng)絡(luò)->單隱層網(wǎng)絡(luò)) 輸出層與輸入層之間的神經(jīng)元, 被稱為隱層或隱含層(hidden layer), 隱含層和輸出層都是具有激活函數(shù)的功能神經(jīng)元(functional neural).
multi-layer feedforward neural networks, 多層前饋神經(jīng)網(wǎng)絡(luò): 每層神經(jīng)元與下一層神經(jīng)元全互連, 神經(jīng)元之間不存在同層辽幌、跨層連接.
誤差逆?zhèn)鞑ニ惴?/h2>
error BackPropagation, 誤差逆?zhèn)鞑ニ惴?BP): 訓(xùn)練多層網(wǎng)絡(luò)的常用算法. 主要目標(biāo)是最小化訓(xùn)練集上的累積誤差
- 標(biāo)準(zhǔn)BP: 每次僅針對一個(gè)訓(xùn)練樣例更新連接權(quán)和閾值, 參數(shù)更新頻繁, 針對不同樣例的更新可能出現(xiàn)"抵消".
- 累積BP(accumulated error backpropagation): 直接針對累積誤差最小化, 讀取完整個(gè)訓(xùn)練集D后才對參數(shù)進(jìn)行更新, 參數(shù)更新頻率低.
訓(xùn)練集
神經(jīng)網(wǎng)絡(luò)擁有d個(gè)神經(jīng)元须尚、l個(gè)輸出神經(jīng)元必逆、q個(gè)隱層神經(jīng)元.
輸出層第j個(gè)神經(jīng)元的閾值用θ_j表示, 隱層第h個(gè)神經(jīng)元的閾值用λ_h表示.
輸入層第i個(gè)神經(jīng)元與隱層第h個(gè)神經(jīng)元之間的連接權(quán)為v_ih, 隱層第h個(gè)神經(jīng)元與輸出層第j個(gè)神經(jīng)元之間的連接權(quán)為w_hj.
隱層第h個(gè)神經(jīng)元收到的輸入為 , 輸出層第j個(gè)神經(jīng)元接受到的輸入為 , 其中b_h為隱層第h個(gè)神經(jīng)元的輸出.
假設(shè)隱層和輸出神經(jīng)元都使用的Sigmoid函數(shù).
式(5.1): ? ?
式(5.2): ? ?
式(5.3): ? ?
? ? ? ? ? ? ? ? ? ? ?
式(5.4): ? ?
式(5.5): ? ?
式(5.6): ? ?
式(5.7): ? ?
# 標(biāo)準(zhǔn)BP算法
# input: 訓(xùn)練集D; 學(xué)習(xí)率η
在(0,1)范圍內(nèi)隨機(jī)初始化網(wǎng)絡(luò)中所有連接權(quán)和閾值
repeat
for all (x_k,y_k) ∈ D do:
根據(jù)當(dāng)前參數(shù)和式(5.1)計(jì)算當(dāng)前樣本的輸出 y'_k;
根據(jù)式(5.2)計(jì)算輸出層神經(jīng)元的梯度項(xiàng)g_j;
根據(jù)式(5.3)計(jì)算隱層神經(jīng)元的梯度項(xiàng)e_h;
根據(jù)式(5.4)~(5.7)更新連接圈w_hj萍嬉、v_ih與閾值θ_j幅垮、λ_h .
end for
until 達(dá)到停止條件
# output: 連接權(quán)與閾值確定的多層前饋神經(jīng)網(wǎng)絡(luò)
只需一個(gè)包含足夠多神經(jīng)元的隱層, 多層前饋網(wǎng)絡(luò)就能以任意精度逼近任意復(fù)雜度的連續(xù)函數(shù). 實(shí)際應(yīng)用中, 經(jīng)常使用"試錯(cuò)法(trial-by-error)"調(diào)整隱層神經(jīng)元的個(gè)數(shù).
緩解BP網(wǎng)絡(luò)的過擬合:
- early, stopping, 早停: 將數(shù)據(jù)集分成訓(xùn)練集和驗(yàn)證集, 驗(yàn)證集用來估計(jì)誤差, 若訓(xùn)練集誤差降低但驗(yàn)證集誤差升高, 則停止訓(xùn)練, 返回具有最小驗(yàn)證集誤差的連接權(quán)和閾值.
- regularization, 正則化: 在誤差目標(biāo)函數(shù)中增加一個(gè)用于描述網(wǎng)絡(luò)復(fù)雜度的部分, 對經(jīng)驗(yàn)誤差和網(wǎng)絡(luò)復(fù)雜度進(jìn)行折中.
全局最小與局部極小
神經(jīng)網(wǎng)絡(luò)的訓(xùn)練過程可看做參數(shù)(連接權(quán)和閾值)尋優(yōu)過程, 即尋找一組最優(yōu)參數(shù)使得誤差最小. "最優(yōu)"一般包括兩種:
- local minimum, 局部極小: 對w和θ, 若存在?>0使得 , 都有成立, 則 為局部極小解.
- global minimum, 全局最小: 若對參數(shù)空間中的任意都有成立, 則 為局部極小解.
局部極小解是參數(shù)空間中的某個(gè)點(diǎn), 其鄰域點(diǎn)的誤差函數(shù)值均不小于該點(diǎn)的函數(shù)值; 全局最小解是指參數(shù)空間中所有點(diǎn)的誤差函數(shù)值均不小于該點(diǎn)的誤差函數(shù)值. 顯然, 參數(shù)空間內(nèi)梯度為零的點(diǎn), 只要其誤差函數(shù)值小于鄰點(diǎn)的誤差函數(shù)值, 就是局部極小點(diǎn). 可能存在多個(gè)局部極小值, 但只會(huì)有一個(gè)全局最小值.
"基于梯度的搜索"是使用較為廣泛的參數(shù)尋優(yōu)方法. 但在存在多個(gè)局部極小的情況小, 不一定能找到全局最小, 如何跳出局部極小呢?
- 以多組不同參數(shù)值初始化(從多個(gè)不同的初始點(diǎn)開始搜索)多個(gè)神經(jīng)網(wǎng)絡(luò), 訓(xùn)練后取誤差最小的解作為最終參數(shù).
- simulated annealing, 模擬退火技術(shù): 在每一步都以一定的概率接受比當(dāng)前解更差的結(jié)果, 有助于跳出局部極小. 每步迭代過程中, 接受"次優(yōu)解"的概率隨時(shí)間的推移而逐漸降低, 從而保證算法穩(wěn)定.
- 隨機(jī)梯度下降: 標(biāo)準(zhǔn)梯度下降法精確計(jì)算梯度, 而隨機(jī)梯度下降在計(jì)算梯度時(shí)加入了隨機(jī)因素, 即便陷入局部極小, 計(jì)算出的梯度仍可能不為零, 有機(jī)會(huì)跳出局部極小繼續(xù)搜索.
- genetic algorithm, 遺傳算法: 遺傳算法詳解 http://www.reibang.com/p/ae5157c26af9 .
- heuristic algorithm, 啟發(fā)式: 一個(gè)基于直觀或經(jīng)驗(yàn)構(gòu)造的算法, 在可接受的花費(fèi)(計(jì)算時(shí)間和空間)下給出待解決組合優(yōu)化問題的每一個(gè)實(shí)例的可行解, 該可行解與最優(yōu)解的偏離程度一般不能預(yù)計(jì).
其他常見神經(jīng)網(wǎng)絡(luò)
RBF網(wǎng)絡(luò)
radial basis function network, 徑向基函數(shù)網(wǎng)絡(luò): 一種單隱層前饋神經(jīng)網(wǎng)絡(luò), 使用徑向基函數(shù)作為隱層神經(jīng)元激活函數(shù), 輸出層則是對隱層神經(jīng)元輸出的線性組合.
訓(xùn)練過程: 1. 通過隨機(jī)采樣或聚類等方式確定神經(jīng)元中心ci; 2. 利用BP算法確定參數(shù)wi和βi .
ART網(wǎng)絡(luò)
adaptive resonance theory network, 自適應(yīng)諧振理論網(wǎng)絡(luò): 競爭型學(xué)習(xí)的重要代表, 網(wǎng)絡(luò)由比較層腰池、識別層、識別閾值、重置模塊構(gòu)成.
競爭型學(xué)習(xí)(competitive learning), 一種無監(jiān)督學(xué)習(xí)策略, 網(wǎng)絡(luò)的輸出神經(jīng)元相互競爭, 在每一時(shí)刻僅有一個(gè)競爭獲勝的神經(jīng)元被激活, 其他神經(jīng)元的狀態(tài)被抑制(勝者通吃原則, winner-take-all).
SOM網(wǎng)絡(luò)
self-organizing map network, 自映射網(wǎng)絡(luò): 競爭型學(xué)習(xí)的代表之一, 將高維輸入數(shù)據(jù)映射到低維空間, 同時(shí)保持輸入數(shù)據(jù)在高維空間中的拓?fù)浣Y(jié)構(gòu), 即將高維空間中相似的樣本點(diǎn)映射到網(wǎng)絡(luò)輸出層中的鄰近神經(jīng)元.
訓(xùn)練過程: 接收到一個(gè)訓(xùn)練樣本, 每個(gè)輸出層神經(jīng)元會(huì)計(jì)算該樣本與自身攜帶的權(quán)向量之間的距離, 距離最近的神經(jīng)元稱為競爭獲勝者, 稱為最佳匹配單元(best matching unit). 最佳匹配單元及其臨近神經(jīng)元的權(quán)向量將被調(diào)整, 以使得這些權(quán)向量與當(dāng)前輸入樣本的距離縮小. 這個(gè)過程不斷迭代, 直至收斂.
級聯(lián)相關(guān)網(wǎng)絡(luò)
結(jié)構(gòu)自適應(yīng)網(wǎng)絡(luò): 一般神經(jīng)網(wǎng)絡(luò)模型假定網(wǎng)絡(luò)結(jié)構(gòu)是事先固定的, 訓(xùn)練目的是利用訓(xùn)練樣本來確定合適的連接權(quán)示弓、閾值等參數(shù); 結(jié)構(gòu)自適應(yīng)網(wǎng)絡(luò)則將網(wǎng)絡(luò)結(jié)構(gòu)也當(dāng)做學(xué)習(xí)的目標(biāo)之一, 希望在訓(xùn)練過程中找到最符合數(shù)據(jù)特定的網(wǎng)絡(luò)結(jié)構(gòu).
cascade-correlation network, 級聯(lián)相關(guān)網(wǎng)絡(luò): 結(jié)構(gòu)自適應(yīng)網(wǎng)絡(luò)的重要代表. 無需設(shè)置網(wǎng)絡(luò)層數(shù)讳侨、隱層神經(jīng)元數(shù)據(jù), 訓(xùn)練速度較快, 但數(shù)據(jù)較小時(shí)容易過擬合.
- 級聯(lián): 指建立層次連接的層級結(jié)構(gòu). 訓(xùn)練開始時(shí), 只有輸入層和輸出層, 處于最小拓?fù)浣Y(jié)構(gòu); 隨著訓(xùn)練的進(jìn)行, 新的隱層神經(jīng)元逐漸加入, 從而創(chuàng)建起層級結(jié)構(gòu).
- 相關(guān): 指通過最大化新神經(jīng)元的輸出與網(wǎng)絡(luò)誤差之間的相關(guān)性來訓(xùn)練相關(guān)的參數(shù).
Elman網(wǎng)絡(luò)
recurrent neural network, 遞歸神經(jīng)網(wǎng)絡(luò): 不同于前饋神經(jīng)網(wǎng)絡(luò), 網(wǎng)絡(luò)中可以出現(xiàn)環(huán)形結(jié)構(gòu), 從而讓一些神經(jīng)元的輸入反饋回來以作為輸入信號. 結(jié)構(gòu)與信息反饋, 使得網(wǎng)絡(luò)在t時(shí)刻的輸出不僅與t時(shí)刻的輸入有關(guān), 還與t-1時(shí)刻的網(wǎng)絡(luò)狀態(tài)有關(guān), 從而能處理與時(shí)間有關(guān)的動(dòng)態(tài)變化.
Elamn: 遞歸神經(jīng)網(wǎng)絡(luò)的代表之一, 結(jié)構(gòu)與多層前饋網(wǎng)絡(luò)相似, 但隱層神經(jīng)元的輸出會(huì)被反饋回來, 與下一時(shí)刻輸入層神經(jīng)元提供的信號一起, 作為隱層神經(jīng)元在下一時(shí)刻的輸入.
Boltzmann機(jī)
神經(jīng)網(wǎng)絡(luò)中有一類模型為網(wǎng)絡(luò)狀態(tài)定義一個(gè)"能量(energy)", 能量最小化時(shí)網(wǎng)絡(luò)達(dá)到理想狀態(tài), 而網(wǎng)絡(luò)的訓(xùn)練就是在最小化能量函數(shù).
Boltzmann機(jī): 一種基于能量的模型(energy-based model), 神經(jīng)元分為顯層和隱層——顯層用于數(shù)據(jù)的輸入輸出, 隱層則是數(shù)據(jù)的內(nèi)在表達(dá). 神經(jīng)元都是布爾型的, 狀態(tài)1代表激活, 0代表抑制.訓(xùn)練過程將每個(gè)訓(xùn)練樣本視為一個(gè)狀態(tài)向量, 使其出現(xiàn)概率盡可能大.
- 深度學(xué)習(xí)(deep learning): 可簡單理解為很深層的神經(jīng)網(wǎng)絡(luò). 對輸入信號進(jìn)行逐層加工, 把初始的、與輸出目標(biāo)聯(lián)系不太密切的輸入表示轉(zhuǎn)化為與輸出目標(biāo)聯(lián)系更密切的表示. 即通過多層處理, 逐漸將初始的低層特征表示轉(zhuǎn)化為高層特征表示, 用簡單模型完成復(fù)雜的分類等學(xué)習(xí)任務(wù).
詳?shù)群罄m(xù).