《數(shù)據(jù)挖掘基礎(chǔ)及其應(yīng)用》課件第4章

第4章分類I:概念與決策樹算法4.1引言4.2決策樹4.3決策樹原理與構(gòu)建4.4補充算法4.5過擬合/欠擬合4.6分類準確性評估本章小結(jié)

4.1引言

4.1.1分類的定義簡單地說,分類(CategorizationorClassification)就是按照某種標準給對象貼標簽(Label),再根據(jù)標簽進行區(qū)分歸類,而聚類是指事先沒有“標簽”而通過某種成團分析找出事物之間存在聚集性原因的過程。

這兩者的區(qū)別是:分類是事先定義好類別,且類別數(shù)不變,分類器需要由人工標注的訓(xùn)練樣本學(xué)習(xí)得到,屬于有指導(dǎo)學(xué)習(xí)范疇;聚類則沒有事先預(yù)定的類別,類別數(shù)不確定,分類器不需要人工標注和預(yù)先訓(xùn)練,類別在聚類過程中自動生成。分類適合類別或分類體系已經(jīng)確定的場合,如按照國圖分類法分類圖書;聚類則適合不存在分類體系、類別數(shù)不確定的場合,一般作為某些應(yīng)用的前端,如多文檔文摘、搜索引擎結(jié)果后聚類(元搜索)等。

分類的目的是學(xué)習(xí)一個分類函數(shù)或分類模型(也常常稱作分類器),該模型能把數(shù)據(jù)庫中的數(shù)據(jù)項映射到給定類別中的某一個類中。要構(gòu)造分類器,需要有一個訓(xùn)練樣本數(shù)據(jù)集

作為輸入。訓(xùn)練集由一組數(shù)據(jù)庫記錄或元組構(gòu)成,每個元組是一個由有關(guān)字段(又稱屬性或特征)值組成的特征向量。

定義4.1通過對訓(xùn)練集(已知類別屬性的數(shù)據(jù))進行學(xué)習(xí)構(gòu)建一個函數(shù),利用這個函數(shù)可以盡可能準確地對測試集(未知類別屬性的數(shù)據(jù))數(shù)據(jù)對象進行預(yù)測,把這樣的一個過程稱為分類。分類的基本流程如圖4-1所示,包含輸入訓(xùn)練數(shù)據(jù)、分類模型的訓(xùn)練、輸出類別信息三部分。圖4-1分類的基本流程

分類問題的目標是構(gòu)建分類器或分類函數(shù);分類問題的三大要素是訓(xùn)練集、測試集、模型。訓(xùn)練集與測試集的區(qū)別:訓(xùn)練集數(shù)據(jù)對象的類別屬性值已知,而測試集數(shù)據(jù)對象的

類別屬性未知。

分類模型根據(jù)其應(yīng)用目的不同,可分為描述性模型與預(yù)測性模型。描述性模型通常作為解釋性工具,用于區(qū)分不同類中的對象。

具體來說,分類技術(shù)(分類)是一種根據(jù)輸入數(shù)據(jù)建立分類模型的系統(tǒng)方法,包括學(xué)習(xí)過程、模型構(gòu)建、模型測試三個關(guān)鍵的步驟,其中要求所學(xué)習(xí)的模型能夠很好地反映輸入數(shù)

據(jù),同時也要對測試集數(shù)據(jù)進行準確的預(yù)測。圖4-2展示的是一個完整的分類算法流程。圖4-2典型的分類算法流程

4.1.2分類的應(yīng)用

分類是一種應(yīng)用非常廣泛的數(shù)據(jù)挖掘技術(shù),應(yīng)用的例子也很多。例如,根據(jù)信用卡支付歷史記錄,來判斷具備哪些特征的用戶往往具有良好的信用;根據(jù)某種病癥的診斷記錄,來分析哪些藥物組合可以帶來良好的治療效果。這些過程的一個共同特點是:根據(jù)數(shù)據(jù)的某些屬性,來估計一個特定屬性的值。

例如在信用分析案例中,根據(jù)用戶的“年齡”“性別”“收入水平”“職業(yè)”等屬性的值,來估計該用戶“信用度”屬性的值應(yīng)該取“好”還是“差”。在這個例子中,所研究的屬性“信用度”是一個離散屬性,它的取值是一個類別值,這種問題在數(shù)據(jù)挖掘中被稱為分類。還有一種問題,例如根據(jù)股市交易的歷史數(shù)據(jù)估計下一個交易日的大盤指數(shù),這里所研究的屬性“大盤指數(shù)”是一個連續(xù)屬性,它的取值是一個實數(shù),這種問題在數(shù)據(jù)挖掘中被稱為預(yù)測。

4.1.3分類算法

不同的應(yīng)用背景,所獲取的數(shù)據(jù)類型與任務(wù)不同,分類算法就有不同的分組。可通過不同層次對分類算法進行分組。按照機器學(xué)習(xí)的類型,將分類算法分成有監(jiān)督學(xué)習(xí)的分類與無監(jiān)督學(xué)習(xí)的分類;按照類別屬性是連續(xù)還是離散取值,分類算法可分為分類器算法與回歸分析;按照類別屬性的取值多少,分為二分類算法或多分類算法等。典型的分類算法包括決策樹、神經(jīng)網(wǎng)絡(luò)、SVM、貝葉斯、KNN、深度學(xué)習(xí),它們各自的優(yōu)點和缺點如表4-1所示。

4.2決策樹

決策樹(DecisionTree)是一類常見的分類方法,其目的是通過訓(xùn)練集獲取一個分類模型用以對新示例進行分類。分類任務(wù)可以通過一系列的問答方式進行,如“當(dāng)前樣本屬于正類嗎?”通過答案對分類的走向進行“決策”或“判定”。顧名思義,決策樹是基于樹結(jié)構(gòu)進行決策的,這恰恰是人類面臨決策問題時一種自然的處理機制。例如,校園中小貓和小狗的匹配問題,如圖4-3所示。圖4-3動物匹配問題的決策樹

決策樹分類算法包含兩大關(guān)鍵技術(shù)問題:

①決策樹定義與工作流程;

②決策樹構(gòu)建原理。

決策樹又稱為判定樹,是應(yīng)用于分類的一種樹結(jié)構(gòu),其每個內(nèi)部節(jié)點代表對某一屬性的一次測試,每條邊代表一個針對測試的判斷,葉節(jié)點代表最終的分類結(jié)果。給定一棵決

策樹,決策過程需要從樹的根節(jié)點出發(fā),將待測數(shù)據(jù)與決策樹中的特征節(jié)點進行比較,并按照比較結(jié)果選擇下一個比較分支,直到葉節(jié)點成為最終的決策結(jié)果。

定義4.2決策樹是一種樹形結(jié)構(gòu)的分類器,由節(jié)點和有向邊構(gòu)成,節(jié)點有內(nèi)部節(jié)點和葉節(jié)點,內(nèi)部節(jié)點代表一個特征或者屬性判定條件,葉節(jié)點代表分類結(jié)果。

節(jié)點是一棵決策樹的主體。其中,沒有父節(jié)點的節(jié)點稱為根節(jié)點,如圖4-4中的節(jié)點“有房”;沒有子節(jié)點的節(jié)點稱為葉節(jié)點。從根節(jié)點到每個葉節(jié)點的路徑對應(yīng)了一個判定測

試序列。決策樹學(xué)習(xí)的目的是產(chǎn)生一棵泛化能力強,即處理未見示例能力強的決策樹,其基本流程遵循簡單且直觀的“分而治之”(Divide-and-Conquer)策略,如算法4.1所示。

顯然,決策樹的生成是一個遞歸過程。在決策樹基本算法中,有三種情形會導(dǎo)致遞歸返回:①當(dāng)前節(jié)點包含的樣本全屬于同一類別,無須劃分;②當(dāng)前屬性集為空,或是所有樣本在所有屬性上取值相同,無須劃分;③當(dāng)前節(jié)點包含的樣本集合為空,不能劃分。在第②種情形下,我們把當(dāng)前節(jié)點標記為葉節(jié)點,并將其類別設(shè)定為該節(jié)點所包含樣本最多的類別;在第③種情形下,同樣把當(dāng)前節(jié)點標記為葉節(jié)點,但將其類別設(shè)定為其父節(jié)點所含樣本最多的類別。注意這兩種情形的處理實質(zhì)不同:情形②是利用當(dāng)前節(jié)點的后驗分布,而情形③則是把父節(jié)點的樣本分布作為當(dāng)前節(jié)點的先驗分布。

問題1:決策樹的關(guān)鍵詞是什么?

決策樹三大要素包括:

?樹狀結(jié)構(gòu);

?非葉節(jié)點代表屬性;

?葉節(jié)點代表類別。

問題2:決策樹預(yù)測的關(guān)鍵是什么?

第二個關(guān)鍵問題是:給定決策樹,如何對測試集中的數(shù)據(jù)對象進行預(yù)測,并為人們提供決策依據(jù)。決策樹可以用來回答是和否問題,通過樹形結(jié)構(gòu)將各種情況組合都表示出來,每個分支表示一次選擇(選擇是還是否),直到所有選擇都進行完畢,最終給出正確答案。

定義4.3決策樹預(yù)測是指沿從根節(jié)點到葉節(jié)點的路徑進行查找,即從根節(jié)點出發(fā),根據(jù)屬性取值尋找下一個節(jié)點,并重復(fù)上述過程,直到當(dāng)前節(jié)點為葉節(jié)點。葉節(jié)點對應(yīng)的值即為該數(shù)據(jù)對象的屬性類別,如圖4-4所示。圖4-4

決策樹預(yù)測過程示意圖

由圖4-4可以看出,決策樹預(yù)測通過三個步驟完成:

①從根節(jié)點出發(fā);

②根據(jù)根節(jié)點屬性值進入下一個非葉節(jié)點;

③進入葉節(jié)點,葉節(jié)點中的值就是該數(shù)據(jù)對象的類別(即最終決策)。

4.3決策樹原理與構(gòu)建

4.3.1算法原理通過4.2節(jié)決策樹的定義和工作流程可知,要構(gòu)建決策樹,需要解決三方面的問題:①如何選擇特征;②如何對特征進行分支;③決策樹修剪。

構(gòu)建決策樹的難點如下:

(1)給定訓(xùn)練數(shù)據(jù)集,如何來選擇特征作為根節(jié)點?如圖4-5所示,如何解決特征重要性刻畫問題和什么是特征的重要性兩個問題。圖4-5決策樹構(gòu)建難點之一:特征選擇困難

(2)給定特征,如何判斷分支和分支數(shù)?

一旦上述兩個難點問題得到解決,就可以利用遞歸方式構(gòu)建決策樹。通過將訓(xùn)練記錄相繼劃分成純度更高的子集,以遞歸方式建立決策樹,如圖4-6所示。圖4-6基于圖4-5的訓(xùn)練數(shù)據(jù),匈牙利算法流程示意圖

問題3:對于一個完整的決策樹算法,需要解決的問題是什么?

?如何選擇特征?

?特征如何分支?

?最佳分支如何獲取?

?算法如何終

4.3.2分支原則

假設(shè)特征已經(jīng)選定(后續(xù)討論),該如何解決特征分支問題?如何合理地對已選擇的特征進行分支需要考慮兩方面的因素,包括特征屬性取值、多分類/二分類,具體內(nèi)容如圖4-7所示。圖4-7特征分支分類

1.標量特征分支問題

標量數(shù)據(jù)只有不同特征之間的區(qū)別,無大小。給定車型特征,其取值為標量,例如,車型(Cartype)特征包括豪華型(Luxury)、家用型(Family)、運動型(Sports)。

由于標量的取值為離散的,所以可采用不同的值作為一個分支。車型特征可分為三個分支,如圖4-8所示,其中每種車型為一個分支。該情況下,多分帶來的優(yōu)點是:①簡單,易于實現(xiàn);②可解釋性強。但多分同樣也有一定的缺點:當(dāng)標量取值過多時,會導(dǎo)致子節(jié)點過多;特征的取值數(shù)過多時,分類的準確性極低。圖4-8車型特征的三分支情況

為了克服該缺陷,可以采用二分情況,如圖4-9所示。但車型特征的二分支情況存在一些缺點:當(dāng)特征的取值過多時,組合模式呈指數(shù)級增長。圖4-9車型特征的二分支情況

2.序數(shù)特征分支問題

序數(shù)數(shù)據(jù)的特征既有大小,也有順序。給定車尺寸特征,其取值為序數(shù)數(shù)據(jù)。例如,車尺寸(CarSize)特征包括大型(Large)、中型(Medium)、小型(Small)。

由于序數(shù)數(shù)據(jù)的取值為離散的,所以可采用不同的值作為一個分支。與車型特征的三分支情況相同,采用三分支對車尺寸特征進行分割,如圖4-10所示,其中每種尺寸類型一個分支。該情況下,多分帶來的優(yōu)點是:①簡單,易于實現(xiàn);②可解釋性強。但它同樣也有一定的缺點:分支數(shù)過多,導(dǎo)致過擬合,影響準確性。圖4-10車尺寸特征的三分支情況

為了克服該缺陷,可以采用二分情況。圖4-9中所涉及的二分支策略不適合序數(shù)數(shù)據(jù)的二分支要求,主要原因是標量數(shù)據(jù)僅考慮大小,不考慮順序關(guān)系,而序數(shù)數(shù)據(jù)要求分支同時考慮大小和順序關(guān)系。對序數(shù)數(shù)據(jù)而言,進行二分支時,不能破壞順序關(guān)系,如圖4-11所示。圖4-11車尺寸特征的二分支情況

根據(jù)圖4-11,對于車尺寸特征的二分支情況,可以合理劃分為以下三種:

?{小型,中型},{大型},劃分合理;

?{小型},{中型,大型},劃分合理;

?{小型,大型},{中型},劃分錯誤,破壞數(shù)據(jù)的順序性。

3.實數(shù)/區(qū)間特征分支問題

實數(shù)/區(qū)間取值范圍都是連續(xù)的。因此,基于標量數(shù)據(jù)與序數(shù)數(shù)據(jù)的二分/多分的技術(shù)和方法不適用于實數(shù)數(shù)據(jù)。離散化是連續(xù)特征進行分支的方式,如給定個人收入(Taxable

Incomes)特征,可以通過選取不同的閾值進行二分支和多分支,如圖4-12所示。圖4-12個人收入的分支情況

4.3.3最優(yōu)劃分

如何判斷最優(yōu)劃分,具體包括:

①多分還是二分的選擇?

②二分/多分條件下,多種方案如何選擇最優(yōu)?

例如圖4-13中,如何判斷和量化二分、三分、多分的優(yōu)劣性?其中C0表示第0類中的數(shù)據(jù)對象數(shù),C1表示第1類中的數(shù)據(jù)對象數(shù)。圖4-13不同特征的分支情況

圖4-14所示為圖4-13的兩種分類結(jié)果?？芍?左側(cè)結(jié)果不能有效地區(qū)分兩類,而右側(cè)結(jié)果可以區(qū)分兩類,因此左邊同質(zhì)性低/純度低,右邊同質(zhì)性高/純度高。即隸屬于同一類的數(shù)據(jù)對象越多,同質(zhì)性越高。圖4-14-兩種不同的分類結(jié)果

那么,如何量化同質(zhì)性/純度?一旦有了量化標準,可

以選擇最優(yōu)的劃分,一般而言,隨著劃分過程的不斷進行,

我們希望決策樹的分支節(jié)點所包含的樣本盡可能屬于同一類別,即節(jié)點的“純度”(Purity)越來越高。劃分的原則是:導(dǎo)致最大同質(zhì)性/純度變化的劃分為最優(yōu)劃分,如圖4-15所示。圖4-15基于同質(zhì)性/純度標準的最優(yōu)劃分示意圖

目前通用的度量方式有三種:Gini系數(shù)(基尼系數(shù))、信息增益與最大錯誤率。

1.Gini系數(shù)

Gini系數(shù)是經(jīng)濟學(xué)里的一個概念,它是美國經(jīng)濟學(xué)家阿爾伯特·赫希曼根據(jù)勞倫茨曲線所定義的判斷收入分配公平程度的指標。Gini系數(shù)是一個比值,是國際上用來綜合考察

居民內(nèi)部收入分配差異狀況的一個重要分析指標。

回歸分類樹(ClassificationandRegressionTree,CART)使用“基尼系數(shù)”(GiniIndex)來選擇劃分屬性。

定義4.4(Gini系數(shù))給定決策樹中的某個節(jié)點t,其對應(yīng)一組數(shù)據(jù)對象,統(tǒng)計該組數(shù)據(jù)中第j類數(shù)據(jù)對象所占有的比例,表示為P(j|t),則Gini系數(shù)定義為

問題5:Gini系數(shù)的性質(zhì)是什么?

提示:利用數(shù)據(jù)示例引導(dǎo)學(xué)生分析、理解Gini系數(shù)的基本性質(zhì)。Gini系數(shù)的基本性質(zhì)如下:

?取值范圍是[0,0.5];

?最小取值是0,對應(yīng)所有的數(shù)據(jù)對象都隸屬于一個類別;

?最大取值是0.5,對應(yīng)所有的數(shù)據(jù)對象都均勻分布在每個類別上;

?值越小,純度越高。

圖4-16顯示了二元分類問題中不同二元分布問題的Gini系數(shù)的計算,相應(yīng)的Gini系數(shù)結(jié)果列于表4-2中。圖4-16Gini系數(shù)計算

問題6:Gini系數(shù)可以選擇最佳劃分,是否可以決定特征可分?

決策樹算法追求更高的準確性以及高度的同質(zhì)性,一個特征是否可分,取決于同質(zhì)性/純度是否提高,如圖4-17所示。圖4-17基于純度/同質(zhì)性決定特征是否劃分

問題7:Gini系數(shù)可以選擇最佳劃分,是否可以選擇二分與多分?

二分還是多分,取決于同質(zhì)性/純度是否提高,如圖4-18所示。圖4-18基尼系數(shù)可有效地解決特征分支問題與最優(yōu)分支

結(jié)論:我們在候選屬性集合中,選擇那個使得劃分后Gini系數(shù)最小的屬性作為最優(yōu)劃分屬性。

也可得出結(jié)論:特征是否多分/二分,選擇Gini系數(shù)最小時所對應(yīng)的劃分。

考慮圖4-19所示的例子,圖4-20是圖4-19對應(yīng)的離散化的結(jié)果,其中“年收入≤v”用來劃分拖欠欠款分類問題的訓(xùn)練記錄。用窮舉方法確定v的值,將N個記錄中所有屬性值都作為候選劃分點,對每個候選v,都要掃描一次數(shù)據(jù)集,統(tǒng)計年收入大于和小于v的記錄數(shù),然后計算每個候選的Gini系數(shù),并從中選擇具有最小值的候選劃分點。圖4-19Gini系數(shù)如何選取實數(shù)最優(yōu)的閾值圖4-20圖4-19對應(yīng)的Gini系數(shù)結(jié)果

2.信息增益

定義4.5(信息熵)“信息熵”(InformationEntropy)是度量樣本集合純度最常用的一種指標。假定當(dāng)前樣本集合D中第k類樣本所占的比例為pk(k=1,2,…,|y|),則D的信息熵定義為

Ent(D)的值越小,則D的純度越高。信息熵的基本性質(zhì)如下:

?取值范圍是[0,1];

?最小取值是0,對應(yīng)所有的數(shù)據(jù)對象都隸屬于一個類別;

?最大取值是1,對應(yīng)所有的數(shù)據(jù)對象都均勻分布在每個類別上;

?熵越小,純度越高。

類似地,我們可以計算出采用其他兩個特征“性別”和“月收入”作為根節(jié)點的信息增益分別為

顯然,特征“性別”的信息增益最大,于是將其選為劃分屬性。如圖4-21所示,16個樣本被按照性別特征分成了兩組,“性別=女性”組有9個樣本,其中1人購車;“性別=男性”組有7個樣本,其中3人購車。圖4-21基于“性別”特征對根節(jié)點進行劃分

然后,決策樹算法將對每個分支節(jié)點進行進一步的劃分。對“性別=女性”組和“性別=男性”組,采用與上面相同的方法分別計算兩組樣本上如果再采用“年齡”或“月收入”作為劃分屬性所得的信息增益。結(jié)果發(fā)現(xiàn),對于“性別=男性”組,采用“年齡”特征后信息增益最大,為0.9852;而對于“性別=女性”組,采用“月收入”作為特征后信息增益最大,為0.688。這樣就可以分別用這兩個特征構(gòu)建決策樹下一級的節(jié)點,最終得到的決策樹如圖4-22所示。圖4-22表4-3數(shù)據(jù)生成的判斷客戶是否購車的決策樹

問題8:決策樹構(gòu)建過程中節(jié)點的純度一定是越高越好嗎?

實際上,純度并非越高越好,例如圖4-23中最右側(cè)的決策樹,其每個節(jié)點下面的Gini系數(shù)都達到最優(yōu),但是這種方式未必是最好的。圖4-23在決策樹中是否純度越高越好?

實際上,信息增益準則對可取值數(shù)目較多的屬性有所偏好,為減少這種偏好可能帶來的不利影響,著名的C4.5決策樹算法不直接使用信息增益,而是使用“增益”(Gain

Ratio)來選擇最優(yōu)劃分屬性。采用與式(4-3)相同的符號表示,增益率定義為

其中

稱為屬性a的“固定值”(IntrinsicValue)。屬性a的可能取值數(shù)目越多(即V越大),則IV(a)的值通常會越大。顯然,對于表4-3汽車銷售的例子,也可以使用這種決策對“年齡”和“月收入”進行處理,選出當(dāng)前數(shù)據(jù)下最優(yōu)的劃分方案。

需注意的是,增益率準則對可能取值數(shù)目較少的屬性有所偏好。因此,C4.5算法并不是直接選擇增益率最大的候選劃分屬性,而是使用了一個啟發(fā)式:先從候選劃分屬性中找出信息增益高于平均水平的屬性,再從中選擇增益率最高的。

3.最大錯誤率(MaximumErrorRate)

定義4.6(最大錯誤率)給定決策樹中的某個節(jié)點t,其對應(yīng)一組數(shù)據(jù)對象,統(tǒng)計該組數(shù)據(jù)中第j類數(shù)據(jù)對象所占有的比例,表示為p(j|t),則最大錯誤率定義為

類似于Gini系數(shù)、信息增益,可利用數(shù)據(jù)來分析最大錯誤率的基本性質(zhì)。最大錯誤率的基本性質(zhì)如下:

?取值范圍是[0,1];

?最小取值是0,對應(yīng)所有的數(shù)據(jù)對象都隸屬于一個類別;

?最大取值是1-1/n,對應(yīng)所有的數(shù)據(jù)對象都均勻分布在每個類別上;

?錯誤率越小,純度越高。

課堂練習(xí)示例:圖4-24給出了最大錯誤率不純性度量方法的計算實例。圖4-24-最大錯誤率不純性度量方法計算實例

問題9:Gini系數(shù)、信息熵、最大錯誤率的區(qū)別是什么?

圖4-25展示了二元分類問題不純性度量值的比較,可以看出,不同的不純性度量是一致的。三種量化方式的區(qū)別是:①Gini系數(shù)與信息熵是連續(xù)的,而最大錯誤率是不連續(xù)的;②都是在p=0.5時取值最大;③兩端時取值最小。圖4-26具體展示了三種量化方式的區(qū)別。其中最大錯誤率不發(fā)生變化,為

Gini系數(shù)改進了結(jié)果。

因此以Gini系數(shù)為劃分準則更準確。圖4-25Gini系數(shù)、信息熵、最大錯誤率之間的比較圖4-26Gini系數(shù)、信息熵、最大錯誤率實例對比

4.4

補充算法

4.4.1ID3算法任何一個決策樹算法,其核心步驟都是為每一次分裂確定一個分裂屬性,即究竟按照哪一個屬性來把當(dāng)前數(shù)據(jù)集劃分為若干個子集,從而形成若干個“樹枝”。ID3算法以“信息增益”為度量來選擇分裂屬性。哪個屬性在分裂中產(chǎn)生的信息增益最大,就選擇該屬性作為分裂屬性。ID3算法是一個從上到下、分而治之的歸納過程。

ID3算法的核心是:在決策樹各級節(jié)點上選擇分裂屬性時,通過計算信息增益來選擇屬性,以使得在每一個非葉節(jié)點進行測試時,能獲得關(guān)于被測試樣本最大的類別信息。其具體方法是:檢測所有的屬性,選擇信息增益最大的屬性產(chǎn)生決策樹節(jié)點,由該屬性的不同取值建立分支,再對各分支的子集遞歸調(diào)用該方法建立決策樹節(jié)點的分支,直到所有子集僅包括同一類別的數(shù)據(jù)為止,最后得到一棵決策樹。它可以用來對新的樣本進行分類,如算法4.2所示。

ID3算法的缺點也很突出,具體包括以下幾點:

(1)ID3算法對訓(xùn)練樣本質(zhì)量的依賴性很強。

(2)ID3算法只能處理分類屬性(離散屬性),不能處理連續(xù)屬性(數(shù)值屬性)。

(3)ID3算法生成的決策樹是一棵多叉樹,分支的數(shù)量取決于分裂屬性有多少個不同的取值,這不利于處理分裂屬性取值數(shù)目較多的情況。因此,目前流行的決策樹算法大多采用二叉樹模型。

(4)ID3算法不包含對樹的修剪,無法對決策樹進行優(yōu)化。

4.4.2C4.5算法

1.用信息增益率來選擇屬性

假設(shè)要選擇有n個輸出的檢驗,把訓(xùn)練樣本集T分區(qū)成子集{T1,T2,T3,…,Tn}。假如S是任意樣本集,設(shè)freq(Ci,T)代表S中屬于類Ci的樣本數(shù)量,S表示集S中的樣本數(shù)量。最初的ID3算法用增益標準來選擇需要檢驗的屬性,即基于信息論中熵的概念。

下面的關(guān)系式可以計算出集合T的信息熵:

2.可以處理連續(xù)數(shù)值型屬性

最優(yōu)分割點是從候選分割點選取出來的,有兩種生成候選分割點的方式:

(1)對連續(xù)屬性排序,在每兩個相鄰的連續(xù)屬性之間,以它們的均值作為分割點。因此,對于N條數(shù)據(jù)記錄,將會有N-1個分割點。

(2)對連續(xù)屬性排序,在分類結(jié)果產(chǎn)生變化的兩組數(shù)據(jù)之間確定分割點,這樣可以有效地減少計算量。

3.采用后剪枝方法修剪決策樹

該方法使用訓(xùn)練樣本集本身來估計剪枝前后的誤差,從而決定是否確定要剪枝。方法中使用的公式為

式中:N是實例的數(shù)量;f=E/N為觀察到的誤差率(其中E為N個實例中分類錯誤的個數(shù));q為真實的誤差率;c為置信度(C4.5算法的一個輸入?yún)?shù),默認值為0.25);z為對應(yīng)于置信度c的標準差,其值可根據(jù)c的設(shè)定值通過查正態(tài)分布表得到。通過該公式即可計算出真實誤差率q的一個置信度上限,用此上限為該節(jié)點誤差率e做一個悲觀的估計:

4.對于缺失值的處理

對于缺失值數(shù)據(jù)我們需要解決兩個問題:①如何在屬性值缺失的情況下進行劃分屬性選擇?②給定劃分屬性,若樣本在該屬性上的值缺失,如何對樣本進行劃分?

優(yōu)點:C4.5算法采用信息增益率作為選擇分支屬性的標準,克服了ID3算法中信息增益選擇屬性時偏向選擇取值多的屬性的不足,并能夠完成對連續(xù)屬性離散化處理,還能夠?qū)Σ煌暾麛?shù)據(jù)進行處理。C4.5算法屬于基于信息論的方法,它以信息論為基礎(chǔ),以信息熵和信息增益度為衡量標準,從而實現(xiàn)對數(shù)據(jù)的歸納分類。

缺點:在構(gòu)造樹的過程中,需要對數(shù)據(jù)集進行多次的順序掃描和排序,因而導(dǎo)致算法的效率低。此外,C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集,當(dāng)訓(xùn)練集無法在內(nèi)存中容納時,程序?qū)o法運行。

4.5過擬合/欠擬合

4.5.1定義分類包括兩大關(guān)鍵技術(shù):分類器構(gòu)建與分類器評估。前面介紹的都是分類器的構(gòu)建,下面主要介紹分類器評估方法。分類器模型的評估涉及如何有效地選擇評價指標的問題。通常來說,偏差和方差是兩個典型的指標。偏差是指忽略了多少數(shù)據(jù),即預(yù)測出來的數(shù)據(jù)與真實值的差距;而方差是指模型對數(shù)據(jù)的依賴程度,即預(yù)測出來的數(shù)據(jù)的分散程度。

假設(shè)使用g來代表預(yù)測值(這里我們把它看成是隨機變量,即不同數(shù)據(jù)學(xué)習(xí)得到的模型),f代表真實值,=E(g)代表算法的期望預(yù)測(如可以用不同的數(shù)據(jù)集D1,D2,…,DK來

得到則有

借助偏差和方差可以有效地評價一個分類器。一個過擬合的模型具有高方差和低差。而反過來則被稱為欠擬合,即不是過于密切地跟蹤訓(xùn)練數(shù)據(jù),而是一個不合適的模型忽略了訓(xùn)練數(shù)據(jù)的訓(xùn)練,并且無法學(xué)習(xí)輸入和輸出之間的潛在關(guān)系。如圖4-27所示為過擬合與欠擬合示意圖。分類器過擬合/欠擬合最直觀的定義為:

過擬合:模型在訓(xùn)練樣本下效果很好,但預(yù)測時表現(xiàn)不好的情況;

欠擬合:模型在訓(xùn)練和預(yù)測時表現(xiàn)都不好的情況。

導(dǎo)致過擬合/欠擬合的原因大致有:數(shù)據(jù)噪聲導(dǎo)致不能很好地對訓(xùn)練數(shù)據(jù)集進行學(xué)習(xí);樣本量過小,導(dǎo)致學(xué)習(xí)不足,不能很好地泛化到測試數(shù)據(jù)集;過度追求純度,導(dǎo)致對訓(xùn)練數(shù)據(jù)集過分學(xué)習(xí),分類效果不佳。圖4-27過擬合與欠擬合示意圖(每個示例的過擬合/欠擬合情況均有標注)

4.5.2規(guī)避策略

通常來說,有幾種方式分別從不同的方面來解決過擬合問題,如表4-4所示。

理想決策算法滿足如下三個標準:

(1)葉節(jié)點數(shù)最少;

(2)葉節(jié)點深度最小。

決策樹剪枝的基本策略有“預(yù)剪枝”(Prepruning)和“后剪枝”(Postpruning)。預(yù)剪枝是指在決策樹生成過程中,對每個節(jié)點在劃分前先進行評估,若當(dāng)前節(jié)點的劃分不能帶來決策樹泛化性能提升,則停止劃分并將當(dāng)前節(jié)點標記為葉節(jié)點;后剪枝則是先從訓(xùn)練集生成一棵完整的決策樹,然后自底向上地對非葉節(jié)點進行考察,若將該節(jié)點對應(yīng)的子樹替換

為葉節(jié)點能帶來決策樹泛化性能的提升,則將該子樹替換為葉節(jié)點。

1.預(yù)剪枝

首先討論預(yù)剪枝。在決策樹生長過程中需要決定某些節(jié)點是否繼續(xù)分支或直接作為葉節(jié)點。若某些節(jié)點被判斷為葉節(jié)點,則該分支停止生長。用于判斷決策樹停止的方法一般有三種:

(1)數(shù)據(jù)劃分法。

(2)閾值法。

(3)信息增益的統(tǒng)計顯著性分析法。

由上總結(jié)預(yù)剪枝的主要原則如下:

?定義一個高度,當(dāng)決策樹達到該高度時就停止決策樹的生長;

?達到某個節(jié)點的示例具有相同的特征向量,即使這些示例不屬于同一類,也可以停止決策樹的生長;

?定義一個閾值,當(dāng)達到某個節(jié)點的示例個數(shù)小于閾值時停止決策樹的生長;

?定義一個閾值,計算每次擴張對系統(tǒng)性能的增益,通過比較信息增益值與該閾值的大小來決定是否停止決策樹的生長。

圖4-28給出了預(yù)剪枝算法示意圖。

2.后剪枝

與預(yù)剪枝不同,后剪枝(Postpruning)首先構(gòu)造完整的決策樹,再對其進行修剪。其核心思想是對一些分支進行合并,它從葉節(jié)點出發(fā),如果消除具有相同父節(jié)點的葉節(jié)點后不會導(dǎo)致信息熵的明顯增加,則取消執(zhí)行,并以其父節(jié)點作為新的葉節(jié)點。如此不斷地從葉節(jié)點往上進行回溯,直到合并操作不再需要為止。相比于預(yù)剪枝,這種方法更常用,因為在預(yù)剪枝方法中精確地估計何時停止樹增長很困難。１

常用的后剪枝規(guī)則包含三種:

(1)減少分類錯誤的修剪法。

(2)最小代價與復(fù)雜性的折中。

(3)最小描述長度(MinimalDescriptionLength,MDL)準則。

由上總結(jié)后剪枝的主要方法如下:

?Reduced-ErrorPruning(REP,錯誤率降低剪枝);

?Pesimistic-ErrorPruning(PEP,悲觀錯誤剪枝);

?Cost-ComplexityPruning(CCP,代價復(fù)雜度剪枝);

?Error-BasedPruning(EBP,基于錯誤的剪枝)。

圖4-29給出了后剪枝算法示意圖,樂觀估計條件下都不剪掉,悲觀估計下不剪左邊剪右邊。圖4-29后剪枝算法示意圖

3.缺失值處理方法

現(xiàn)實任務(wù)中常會遇到不完整樣本,也就是說樣本的某些屬性值缺失。例如由于診測成本、隱私保護等因素,患者的醫(yī)療數(shù)據(jù)在某些屬性上的取值(如HIV測試結(jié)果)未知;尤其

是在屬性數(shù)目較多的情況下,往往會有大量樣本出現(xiàn)缺失值。如果簡單地放棄這些不完整樣本,只使用無缺失值樣本進行學(xué)習(xí),顯然是對數(shù)據(jù)極大的浪費。

數(shù)據(jù)屬性值缺失有多種情況:

(1)樹節(jié)點中包括缺失特征值的記錄,影響其不純性計算;

(2)父節(jié)點中包括缺失特征值的記錄,影響該記錄如何分配到子節(jié)點;

(3)測試記錄中包括缺失特征值的記錄,影響測試記錄的分類。

針對問題(1)純度計算問題,采用數(shù)據(jù)完整的樣本數(shù)來估計信息增益,如圖4-30所示。圖4-30數(shù)據(jù)缺失導(dǎo)致純度計算問題

針對問題(2)純度計算問題,采用父節(jié)點的值來估計信息增益,如圖4-31所示。圖4-31利用父節(jié)點的取值解決數(shù)據(jù)分類問題

針對問題(3)測試記錄中包括缺失特征值的記錄,影響測試記錄的分類,通過不同樣本所占有的比例分別對子節(jié)點進行賦權(quán),利用概率方式進行估計與計算,如圖4-32所示。圖4-32利用概率賦權(quán)方式解決子節(jié)點分配問題

4.其他處理方法

解決過擬合問題除了上面提到的方法外,還有決策邊界、樹復(fù)制、數(shù)據(jù)分割等。多種解決過擬合問題的方法與策略的優(yōu)點和缺點如表4-5所示。

4.6分類準確性評估

4.6.1準確性混淆矩陣(ConfusionMatrix)也稱誤差矩陣,是表示精度評價的一種標準格式,用n行n列的矩陣形式來表示。具體評價指標有總體精度、制圖精度、用戶精度等,這些精度指標從不同的側(cè)面反映了圖像分類的精度。在人工智能中,混淆矩陣是可視化工具,特別用于監(jiān)督學(xué)習(xí),在無監(jiān)督學(xué)習(xí)中一般稱作匹配矩陣。

以分類模型最簡單的二分類為例,對于這種問題,我們的模型最終需要判斷樣本的結(jié)果是0還是1,或者說是陽性(Positive)還是陰性(Negative)。通過樣本的采集,能夠直接

知道真實情況下,哪些數(shù)據(jù)的結(jié)果是positive,哪些數(shù)據(jù)的結(jié)果是negative。同時,我們通過用樣本數(shù)據(jù)得到分類模型的結(jié)果,也可以通過模型預(yù)測知道這些數(shù)據(jù)哪些是positive,

哪些是negative。因此,我們能夠得到四個基礎(chǔ)指標,它們被稱為一級指標(最底層指標):

?真實值是Positive,模型預(yù)測是Positive的數(shù)量(TruePositive=TP);

?真實值是Positive,模型預(yù)測是Negative的數(shù)量(FalseNegative=FN);

?真實值是Negative,模型預(yù)測是Nositive的數(shù)量(FalsePositive=FP);

?真實值是Negative,模型預(yù)測是Negative的數(shù)量(TrueNegative=TN)。

將這四個指標一起呈現(xiàn)在表格中,就能得到如圖4-33所示的一個矩陣,我們稱它為混淆矩陣。圖4-33二分類問題混淆矩陣

說明:混淆矩陣的每一