連續(xù)值處理
西瓜書的例子
- Temperature: 40 48 60 72 80 90
- PlayTennis: No No Yes Yes Yes No
決策樹學(xué)習(xí)是一種逼近離散值目標(biāo)函數(shù)的方法，在這種方法中學(xué)習(xí)到的函數(shù)被表示 為一棵決策樹。學(xué)習(xí)得到的決策樹也能再被表示為多個(gè) if-then 的規(guī)則，以提高可讀性。 這種學(xué)習(xí)算法是最流行的歸納推理算法之一，已經(jīng)被成功地應(yīng)用到從學(xué)習(xí)醫(yī)療診斷到學(xué) 習(xí)評(píng)估貸款申請的信用風(fēng)險(xiǎn)的廣闊領(lǐng)域。
對屬性 Temprature，首先按照連續(xù)屬性 A 排序樣例，然后確定目標(biāo)分類不同的 相鄰實(shí)例，于是我們可以產(chǎn)生一組候選閾值，它們的值是相應(yīng)的 A 值之間的中間值。 可以證明產(chǎn)生最大信息增益的 c 值必定位于這樣的邊界中(Fayyad 1991)。然后可以通過計(jì)算與每個(gè)候選閾值關(guān)聯(lián)的信息增益評(píng)估這些候選值。在當(dāng)前的例子中，有兩個(gè)候選 閾值，它們對應(yīng)于目標(biāo)屬性 PlayTennis 變化時(shí)屬性 Temperature 的值:(48+60)/2 和 (80+90)/2。然后計(jì)算每一個(gè)候選屬性——Temperature>54 和Temperature>85的信息增 益，并選擇最好的(Temperature>54)?，F(xiàn)在這個(gè)動(dòng)態(tài)創(chuàng)建的布爾屬性便可以和其他候選 的離散值屬性一同“競爭”，以用于增長決策樹。Fayyad & Irani(1993)討論了這種方 法的一個(gè)擴(kuò)展，即把連續(xù)的屬性分割成多個(gè)區(qū)間，而不是基于單一閾值的兩個(gè)區(qū)間。 Utgoff & Brodley(1991)和 Murthy et al.(1994)討論了通過對幾個(gè)連續(xù)值屬性的線性 組合定義閾值參數(shù)的方法。
c4.5缺失值處理
1）如何選擇劃分屬性。
2）給定劃分屬性，若某樣本在該屬性上缺失值，如何劃分到具體的分支上。
按不同權(quán)重劃分到每個(gè)節(jié)點(diǎn)，例如給定一個(gè)布爾屬性 A，如果結(jié)點(diǎn) n 包含 6 個(gè)已知 A=1 和 4個(gè) A=0 的樣例， 那么 A(x)=1 的概率是 0.6，A(x)=0 的概率是 0.4。于是，實(shí)例 x 的 60%被分配到 A=1 的 分支，40%被分配到另一個(gè)分支。
其他缺失值處理
處理不完備數(shù)據(jù)集的方法主要有以下三大類：
（一）刪除元組
也就是將存在遺漏信息屬性值的對象（元組，記錄）刪除，從而得到一個(gè)完備的信息表。這種方法簡單易行，在對象有多個(gè)屬性缺失值、被刪除的含缺失值的對象與信息表中的數(shù)據(jù)量相比非常小的情況下是非常有效的，類標(biāo)號(hào)（假設(shè)是分類任務(wù)）缺少時(shí)通常使用。然而，這種方法卻有很大的局限性。它是以減少歷史數(shù)據(jù)來換取信息的完備，會(huì)造成資源的大量浪費(fèi)，丟棄了大量隱藏在這些對象中的信息。在信息表中本來包含的對象很少的情況下，刪除少量對象就足以嚴(yán)重影響到信息表信息的客觀性和結(jié)果的正確性；當(dāng)每個(gè)屬性空值的百分比變化很大時(shí)，它的性能非常差。因此，當(dāng)遺漏數(shù)據(jù)所占比例較大，特別當(dāng)遺漏數(shù)據(jù)非隨機(jī)分布時(shí)，這種方法可能導(dǎo)致數(shù)據(jù)發(fā)生偏離，從而引出錯(cuò)誤的結(jié)論。
（二）數(shù)據(jù)補(bǔ)齊
這類方法是用一定的值去填充空值，從而使信息表完備化。通常基于統(tǒng)計(jì)學(xué)原理，根據(jù)決策表中其余對象取值的分布情況來對一個(gè)空值進(jìn)行填充，譬如用其余屬性的平均值來進(jìn)行補(bǔ)充等。數(shù)據(jù)挖掘中常用的有以下幾種補(bǔ)齊方法：
(1)人工填寫（filling manually）
由于最了解數(shù)據(jù)的還是用戶自己，因此這個(gè)方法產(chǎn)生數(shù)據(jù)偏離最小，可能是填充效果最好的一種。然而一般來說，該方法很費(fèi)時(shí)，當(dāng)數(shù)據(jù)規(guī)模很大、空值很多的時(shí)候，該方法是不可行的。
(2)特殊值填充（Treating Missing Attribute values as Special values）
將空值作為一種特殊的屬性值來處理，它不同于其他的任何屬性值。如所有的空值都用“unknown”填充。這樣將形成另一個(gè)有趣的概念，可能導(dǎo)致嚴(yán)重的數(shù)據(jù)偏離，一般不推薦使用。
(3)平均值填充（Mean/Mode Completer）
將信息表中的屬性分為數(shù)值屬性和非數(shù)值屬性來分別進(jìn)行處理。如果空值是數(shù)值型的，就根據(jù)該屬性在其他所有對象的取值的平均值來填充該缺失的屬性值；如果空值是非數(shù)值型的，就根據(jù)統(tǒng)計(jì)學(xué)中的眾數(shù)原理，用該屬性在其他所有對象的取值次數(shù)最多的值(即出現(xiàn)頻率最高的值)來補(bǔ)齊該缺失的屬性值。另外有一種與其相似的方法叫條件平均值填充法（Conditional Mean Completer）。在該方法中，缺失屬性值的補(bǔ)齊同樣是靠該屬性在其他對象中的取值求平均得到，但不同的是用于求平均的值并不是從信息表所有對象中取，而是從與該對象具有相同決策屬性值的對象中取得。這兩種數(shù)據(jù)的補(bǔ)齊方法，其基本的出發(fā)點(diǎn)都是一樣的，以最大概率可能的取值來補(bǔ)充缺失的屬性值，只是在具體方法上有一點(diǎn)不同。與其他方法相比，它是用現(xiàn)存數(shù)據(jù)的多數(shù)信息來推測缺失值。
(4)熱卡填充（Hot deck imputation，或就近補(bǔ)齊）
對于一個(gè)包含空值的對象，熱卡填充法在完整數(shù)據(jù)中找到一個(gè)與它最相似的對象，然后用這個(gè)相似對象的值來進(jìn)行填充。不同的問題可能會(huì)選用不同的標(biāo)準(zhǔn)來對相似進(jìn)行判定。該方法概念上很簡單，且利用了數(shù)據(jù)間的關(guān)系來進(jìn)行空值估計(jì)。這個(gè)方法的缺點(diǎn)在于難以定義相似標(biāo)準(zhǔn)，主觀因素較多。
(5)K最近距離鄰法（K-means clustering）
先根據(jù)歐式距離或相關(guān)分析來確定距離具有缺失數(shù)據(jù)樣本最近的K個(gè)樣本，將這K個(gè)值加權(quán)平均來估計(jì)該樣本的缺失數(shù)據(jù)。
同均值插補(bǔ)的方法都屬于單值插補(bǔ)，不同的是，它用層次聚類模型預(yù)測缺失變量的類型，再以該類型的均值插補(bǔ)。假設(shè)X=(X1,X2…Xp)為信息完全的變量，Y為存在缺失值的變量，那么首先對X或其子集行聚類，然后按缺失個(gè)案所屬類來插補(bǔ)不同類的均值。如果在以后統(tǒng)計(jì)分析中還需以引入的解釋變量和Y做分析，那么這種插補(bǔ)方法將在模型中引入自相關(guān)，給分析造成障礙。
(6)使用所有可能的值填充（Assigning All Possible values of the Attribute）
這種方法是用空缺屬性值的所有可能的屬性取值來填充，能夠得到較好的補(bǔ)齊效果。但是，當(dāng)數(shù)據(jù)量很大或者遺漏的屬性值較多時(shí)，其計(jì)算的代價(jià)很大，可能的測試方案很多。另有一種方法，填補(bǔ)遺漏屬性值的原則是一樣的，不同的只是從決策相同的對象中嘗試所有的屬性值的可能情況，而不是根據(jù)信息表中所有對象進(jìn)行嘗試，這樣能夠在一定程度上減小原方法的代價(jià)。
(7)組合完整化方法（Combinatorial Completer）
這種方法是用空缺屬性值的所有可能的屬性取值來試，并從最終屬性的約簡結(jié)果中選擇最好的一個(gè)作為填補(bǔ)的屬性值。這是以約簡為目的的數(shù)據(jù)補(bǔ)齊方法，能夠得到好的約簡結(jié)果；但是，當(dāng)數(shù)據(jù)量很大或者遺漏的屬性值較多時(shí)，其計(jì)算的代價(jià)很大。另一種稱為條件組合完整化方法（Conditional Combinatorial Complete），填補(bǔ)遺漏屬性值的原則是一樣的，不同的只是從決策相同的對象中嘗試所有的屬性值的可能情況，而不是根據(jù)信息表中所有對象進(jìn)行嘗試。條件組合完整化方法能夠在一定程度上減小組合完整化方法的代價(jià)。在信息表包含不完整數(shù)據(jù)較多的情況下，可能的測試方案將巨增。
(8)回歸（Regression）
基于完整的數(shù)據(jù)集，建立回歸方程（模型）。對于包含空值的對象，將已知屬性值代入方程來估計(jì)未知屬性值，以此估計(jì)值來進(jìn)行填充。當(dāng)變量不是線性相關(guān)或預(yù)測變量高度相關(guān)時(shí)會(huì)導(dǎo)致有偏差的估計(jì)。
(9)期望值最大化方法（Expectation maximization，EM）
在缺失類型為隨機(jī)缺失的條件下，假設(shè)模型對于完整的樣本是正確的，那么通過觀測數(shù)據(jù)的邊際分布可以對未知參數(shù)進(jìn)行極大似然估計(jì)（Little and Rubin）。這種方法也被稱為忽略缺失值的極大似然估計(jì)，對于極大似然的參數(shù)估計(jì)實(shí)際中常采用的計(jì)算方法是期望值最大化(Expectation Maximization，EM）。該方法比刪除個(gè)案和單值插補(bǔ)更有吸引力，它一個(gè)重要前提：適用于大樣本。有效樣本的數(shù)量足夠以保證ML估計(jì)值是漸近無偏的并服從正態(tài)分布。但是這種方法可能會(huì)陷入局部極值，收斂速度也不是很快，并且計(jì)算很復(fù)雜。
EM算法是一種在不完全數(shù)據(jù)情況下計(jì)算極大似然估計(jì)或者后驗(yàn)分布的迭代算法。在每一迭代循環(huán)過程中交替執(zhí)行兩個(gè)步驟：E步（Excepctaion step,期望步），在給定完全數(shù)據(jù)和前一次迭代所得到的參數(shù)估計(jì)的情況下計(jì)算完全數(shù)據(jù)對應(yīng)的對數(shù)似然函數(shù)的條件期望；M步（Maximzation step，極大化步），用極大化對數(shù)似然函數(shù)以確定參數(shù)的值，并用于下步的迭代。算法在E步和M步之間不斷迭代直至收斂，即兩次迭代之間的參數(shù)變化小于一個(gè)預(yù)先給定的閾值時(shí)結(jié)束。該方法可能會(huì)陷入局部極值，收斂速度也不是很快，并且計(jì)算很復(fù)雜。
(10)多重填補(bǔ)（Multiple Imputation，MI）
多值插補(bǔ)的思想來源于貝葉斯估計(jì)，認(rèn)為待插補(bǔ)的值是隨機(jī)的，它的值來自于已觀測到的值。具體實(shí)踐上通常是估計(jì)出待插補(bǔ)的值，然后再加上不同的噪聲，形成多組可選插補(bǔ)值。根據(jù)某種選擇依據(jù)，選取最合適的插補(bǔ)值。
多重填補(bǔ)方法分為三個(gè)步驟：;為每個(gè)空值產(chǎn)生一套可能的填補(bǔ)值，這些值反映了無響應(yīng)模型的不確定性；每個(gè)值都被用來填補(bǔ)數(shù)據(jù)集中的缺失值，產(chǎn)生若干個(gè)完整數(shù)據(jù)集合。;每個(gè)填補(bǔ)數(shù)據(jù)集合都用針對完整數(shù)據(jù)集的統(tǒng)計(jì)方法進(jìn)行統(tǒng)計(jì)分析。;對來自各個(gè)填補(bǔ)數(shù)據(jù)集的結(jié)果進(jìn)行綜合，產(chǎn)生最終的統(tǒng)計(jì)推斷，這一推斷考慮到了由于數(shù)據(jù)填補(bǔ)而產(chǎn)生的不確定性。該方法將空缺值視為隨機(jī)樣本，這樣計(jì)算出來的統(tǒng)計(jì)推斷可能受到空缺值的不確定性的影響。該方法的計(jì)算也很復(fù)雜。
多重插補(bǔ)方法分為三個(gè)步驟：①為每個(gè)空值產(chǎn)生一套可能的插補(bǔ)值，這些值反映了無響應(yīng)模型的不確定性；每個(gè)值都可以被用來插補(bǔ)數(shù)據(jù)集中的缺失值，產(chǎn)生若干個(gè)完整數(shù)據(jù)集合。②每個(gè)插補(bǔ)數(shù)據(jù)集合都用針對完整數(shù)據(jù)集的統(tǒng)計(jì)方法進(jìn)行統(tǒng)計(jì)分析。③對來自各個(gè)插補(bǔ)數(shù)據(jù)集的結(jié)果，根據(jù)評(píng)分函數(shù)進(jìn)行選擇，產(chǎn)生最終的插補(bǔ)值。
假設(shè)一組數(shù)據(jù)，包括三個(gè)變量Y1，Y2，Y3，它們的聯(lián)合分布為正態(tài)分布，將這組數(shù)據(jù)處理成三組，A組保持原始數(shù)據(jù)，B組僅缺失Y3，C組缺失Y1和Y2。在多值插補(bǔ)時(shí)，對A組將不進(jìn)行任何處理，對B組產(chǎn)生Y3的一組估計(jì)值（作Y3關(guān)于Y1，Y2的回歸），對C組作產(chǎn)生Y1和Y2的一組成對估計(jì)值（作Y1，Y2關(guān)于Y3的回歸）。
當(dāng)用多值插補(bǔ)時(shí)，對A組將不進(jìn)行處理，對B、C組將完整的樣本隨機(jī)抽取形成為m組（m為可選擇的m組插補(bǔ)值），每組個(gè)案數(shù)只要能夠有效估計(jì)參數(shù)就可以了。對存在缺失值的屬性的分布作出估計(jì)，然后基于這m組觀測值，對于這m組樣本分別產(chǎn)生關(guān)于參數(shù)的m組估計(jì)值，給出相應(yīng)的預(yù)測即，這時(shí)采用的估計(jì)方法為極大似然法，在計(jì)算機(jī)中具體的實(shí)現(xiàn)算法為期望最大化法（EM）。對B組估計(jì)出一組Y3的值，對C將利用 Y1,Y2,Y3它們的聯(lián)合分布為正態(tài)分布這一前提，估計(jì)出一組(Y1，Y2）。
上例中假定了Y1,Y2,Y3的聯(lián)合分布為正態(tài)分布。這個(gè)假設(shè)是人為的，但是已經(jīng)通過驗(yàn)證（Graham和Schafer于1999），非正態(tài)聯(lián)合分布的變量，在這個(gè)假定下仍然可以估計(jì)到很接近真實(shí)值的結(jié)果。
多重插補(bǔ)和貝葉斯估計(jì)的思想是一致的，但是多重插補(bǔ)彌補(bǔ)了貝葉斯估計(jì)的幾個(gè)不足。
(1)貝葉斯估計(jì)以極大似然的方法估計(jì)，極大似然的方法要求模型的形式必須準(zhǔn)確，如果參數(shù)形式不正確，將得到錯(cuò)誤得結(jié)論，即先驗(yàn)分布將影響后驗(yàn)分布的準(zhǔn)確性。而多重插補(bǔ)所依據(jù)的是大樣本漸近完整的數(shù)據(jù)的理論，在數(shù)據(jù)挖掘中的數(shù)據(jù)量都很大，先驗(yàn)分布將極小的影響結(jié)果，所以先驗(yàn)分布的對結(jié)果的影響不大。
(2)貝葉斯估計(jì)僅要求知道未知參數(shù)的先驗(yàn)分布，沒有利用與參數(shù)的關(guān)系。而多重插補(bǔ)對參數(shù)的聯(lián)合分布作出了估計(jì)，利用了參數(shù)間的相互關(guān)系。
決策樹總結(jié)
- 決策樹學(xué)習(xí)為概念學(xué)習(xí)和學(xué)習(xí)其他離散值的函數(shù)提供了一個(gè)實(shí)用的方法。ID3 系列算法使用從根向下增長法推斷決策樹，為每個(gè)要加入樹的新決策分支貪婪 地選擇最好的屬性。
- ID3算法搜索完整的假設(shè)空間(也就是說，決策樹空間能夠表示任何定義在離散 值實(shí)例上的任何離散值函數(shù))。所以它避免了僅考慮有限的假設(shè)集合的方法的 主要問題:目標(biāo)函數(shù)可能不在假設(shè)空間中。
- 隱含在ID3算法中的歸納偏置包括優(yōu)先選擇較小的樹，也就是說，它通過對假 設(shè)空間的搜索增長樹，使樹的大小為正好能分類已有的訓(xùn)練樣例。
- 過度擬合訓(xùn)練數(shù)據(jù)是決策樹學(xué)習(xí)中的重要問題。因?yàn)橛?xùn)練樣例僅僅是所有可能 實(shí)例的一個(gè)樣本，向樹增加分支可能提高在訓(xùn)練樣例上的性能，但卻降低在訓(xùn) 練實(shí)例外的其他實(shí)例上的性能。因此，后修剪決策樹的方法對于避免決策樹學(xué) 習(xí)中(和其他使用優(yōu)選偏置的歸納推理方法)的過度擬合是很重要的。
- 對于基本ID3算法，研究者已經(jīng)開發(fā)了大量的擴(kuò)展。其中包括后修剪的方法; 處理實(shí)數(shù)值的屬性;容納缺少屬性值的訓(xùn)練樣例;當(dāng)有了新的訓(xùn)練實(shí)例時(shí)遞增 精化決策樹;使用信息增益之外的其他屬性選擇度量;考慮與實(shí)例屬性關(guān)聯(lián)的 代價(jià)。
--參考
- http://blog.csdn.net/qq_30091945/article/details/71655660
- 周本華機(jī)器學(xué)習(xí)
