第4章分類Chapter4:Classification主要內(nèi)容4.1概念4.2決策樹分類方法4.3樸素貝葉斯分類方法4.4k近鄰分類方法4.5邏輯回歸4.6支持向量機4.7分類性能的度量4.1基本概念分類及其相關(guān)的基本概念分類：總結(jié)已有類別的對象的特點并進而進行未知類別對象的類別預(yù)測的過程分類器（classifier)訓(xùn)練數(shù)據(jù)集（trainingdataset）分類屬性（classlabelattribute），每個取值稱為一個類別（classlabel）屬性，用于描述一個對象的某個特性或性質(zhì)測試數(shù)據(jù)集（testingdataset）分類及其相關(guān)的基本概念客戶編號年齡性別年收入（萬）婚姻豪華車1<30女86已婚否2<30男65單身否3<30男90離異否4<30女75已婚否530-50女82已婚是630-50男91已婚是730-50女200離異是830-50女40單身否930-50男20離異否10>50女96離異否11>50女80單身否12>50男50單身是13>50女80離異否14>50男92離異是分類屬性類別訓(xùn)練數(shù)據(jù)集屬性分類方法LazyEager構(gòu)建模型測試、使用模型分類：構(gòu)建模型TrainingDataClassificationAlgorithmsIFrank=‘professor’ORyears>6THENtenured=‘yes’Classifier(Model)TestingDataUnseenData(Jeff,Professor,4)ClassifierTenured?分類：測試分類模型并預(yù)測分類技術(shù)決策樹（decisiontree）樸素貝葉斯（Na?veBayes）K近鄰（KnearestNeighbors）基于關(guān)聯(lián)的分類支持向量機（SupportVectorMachines）人工神經(jīng)網(wǎng)絡(luò)LogisticRegression……4.2決策樹分類方法4.2決策樹分類方法4.2.1決策樹的構(gòu)建過程4.2.2屬性的類型及分裂條件4.2.3決策樹的剪枝決策樹的概念決策樹葉子節(jié)點：類別其余節(jié)點：測試屬性樹的層次

根結(jié)點的層次為1

根結(jié)點的子女結(jié)點的層次為2……邊：一種基于此結(jié)點屬性的判斷（分裂）條件根節(jié)點葉子節(jié)點雙親節(jié)點子女節(jié)點決策樹的構(gòu)建奧卡姆剃刀（Occam’sRazor）原理：“如無必要，勿增實體”（Entitiesshouldnotbemultipliedunnecessarily）一棵小的樹的預(yù)測能力更好采用分而治之的思想，利用貪心策略從局部出發(fā)來構(gòu)造一棵大小緊湊的決策樹。Hunt、ID3、C4.5、CART決策樹的構(gòu)建過程主要步驟：訓(xùn)練數(shù)據(jù)集D，類別集合C={c1,c2,…,ck}創(chuàng)建一個結(jié)點t，初始情況下訓(xùn)練數(shù)據(jù)集中的所有樣本與根結(jié)點關(guān)聯(lián)，記為Dt。將t設(shè)為當(dāng)前結(jié)點。如果當(dāng)前結(jié)點t所關(guān)聯(lián)的數(shù)據(jù)集Dt中所有樣本的類別相同（假設(shè)為ci）,則將該結(jié)點標(biāo)記為葉子節(jié)點，記錄類別為ci，停止對該結(jié)點所關(guān)聯(lián)的數(shù)據(jù)集的進一步分裂。接著處理其他非葉子節(jié)點。否則，進入下一步。為數(shù)據(jù)集Dt選擇分裂屬性和分裂條件。根據(jù)分裂條件將數(shù)據(jù)集Dt分裂為m個子集，為結(jié)點t創(chuàng)建m個子女結(jié)點，將這m個數(shù)據(jù)集分別與之關(guān)聯(lián)。依次將每個結(jié)點設(shè)為當(dāng)前結(jié)點，轉(zhuǎn)至步驟2進行處理，直至所有結(jié)點都標(biāo)記為葉子結(jié)點。決策樹的構(gòu)建過程分裂屬性和分裂條件的選擇分裂屬性的選擇通常利用類別純度的衡量作為標(biāo)準信息熵和gini指數(shù)兩種ABclasscount00-5001-5010+011+100A+-01B-01A+-01分類屬性的選擇信息熵entropy(D)數(shù)據(jù)集D及類別集合C={c1,c2,…,ck}count(ci)：類別ci在D中出現(xiàn)的次數(shù)，p(ci)：ci在D中出現(xiàn)的相對頻率

p(ci)=count(ci)/|D||D|代表D中的數(shù)據(jù)行數(shù)1--+--1+1--+111信息熵若所有行屬于同一類別:

Entropy=?若兩個類別均勻分布(0.5,0.5)

Entropy=?分類屬性的選擇按屬性A分裂的信息熵entropy(D,A)數(shù)據(jù)集D按照屬性A的分裂條件分裂出的m個子數(shù)據(jù)集分別為D1,D2,…,Dm，則entropy(D,A)綜合這m個子數(shù)據(jù)集的信息熵就可以作為衡量一個屬性A優(yōu)劣的度gain(D,A)：一個數(shù)據(jù)集D按屬性A分裂前后信息熵的差值信息增益（informationgain）gain(D,A)=entropy(D)-entropy(D,A)4.2.2屬性的類型及分裂條件為了減少信息增益，需要確定根據(jù)屬性A對數(shù)據(jù)集的分裂方法屬性的分類定量（quantitative）和定性（qualitative）定量屬性又稱為數(shù)值（numerical）屬性，每個取值為數(shù)值，既可以比較大小，又可以進行數(shù)值運算，如加、減、乘、除等。如：“年收入”定性屬性又稱為類別（categorical）屬性，其取值不具有數(shù)的特點。定性屬性又可以分為標(biāo)稱（nominal）屬性和序數(shù)（ordinal）屬性屬性從另一個角度又可以分為離散（discrete）屬性和連續(xù)（continuous）屬性定性屬性的分裂條件一個數(shù)據(jù)集D若根據(jù)一個定性屬性A進行分裂，假設(shè)A在D中的取值由集合VA表示，VA={a1，a1，…，am}，則分裂條件為A=ai例如若按屬性“婚姻”進行數(shù)據(jù)集分裂，則分裂條件為婚姻=單身、婚姻=已婚和婚姻=離異entropy(D,年齡)=0.69，entropy(D,性別)=0.89按屬性“婚姻”進行數(shù)據(jù)集分裂客戶編號年齡性別年收入（萬）婚姻豪華車2<30男65單身否830-50女40單身否11>50女80單身否12>50男50單身是客戶編號年齡性別年收入（萬）婚姻豪華車1<30女86已婚否4<30女75已婚否530-50女82已婚是630-50男91已婚是客戶編號年齡性別年收入（萬）婚姻豪華車3<30男90離異否730-50女200離異是930-50男20離異否10>50女96離異否13>50女80離異否14>50男92離異是定量屬性的分裂條件（1）屬性及分類屬性抽出并按年收入升序排序?qū)τ诙繉傩訟，設(shè)A在數(shù)據(jù)集D中有m個不同的取值，a1<a1<…<am，其分裂數(shù)據(jù)集的候選條件為A

ai，（或取相鄰兩點的中點(ai+ai+1)/2），和A>ai

，其中1<i<m年收入（萬）豪華車累計類別分布20否是：0；否：140否是：0；否：250是是：1；否：265否是：1；否：375否是：1；否：480否是：1；否：580否是：1；否：682是是：2；否：686否是：2；否：790否是：2；否：891是是：3；否：892是是：4；否：896否是：4；否：9200是是：5；否：9定量屬性的分裂條件（2）以“年收入

40萬”為例可以證明不需要在每個取值處都計算信息熵，只需在類別發(fā)生變化的兩個點處進行數(shù)據(jù)集的分裂并計算信息熵即可年收入

50萬”、“年收入

65萬”、“年收入

80萬”、“年收入

86萬”、“年收入

91萬”、“年收入

96萬”最小的是“年收入

80萬”定量屬性的分裂條件（3）數(shù)據(jù)集的信息熵entropy(D)=0.94.gain(D,年齡)=0.24,gain(D,年收入)=0.15，gain(D,性別)=0.05，gain(D,婚姻)=0.03.屬性年齡的信息增益最大，故在根結(jié)點的分裂屬性為“年齡”信息增益的調(diào)整-增益比率以屬性“年齡”為例，分成的3個數(shù)據(jù)集的大小分別為4、5、5屬性“年齡”的增益比率則為0.24/1.58=0.15其他分裂方法CART算法：限定每次對數(shù)據(jù)集的分裂都是二分的若屬性Ａ有３個不同的取值a、b和c，則組合有3種情況{a}和{b，c}、{a，b}和{c}及{a，c}和4.2.3決策樹的剪枝過度擬合（overfitting）過度擬合了訓(xùn)練集中的樣本特點，訓(xùn)練集的準確度高，但通常具有較低的概括（generalization）能力，在預(yù)測未知類別對象時的準確率較低擬合不足（underfitting）如果過早地停止對結(jié)點的進一步分裂也會導(dǎo)致擬合不足問題剪枝（pruning）優(yōu)化先剪枝（pre-pruning）后剪枝（post-pruning）子樹替換（subtreereplacement）方法C4.5中所用的基于誤差估計的剪枝方法子樹替換剪枝：概括誤差估計

子樹替換剪枝：概括誤差估計基于統(tǒng)計的誤差上界估計將上式中的不等式改為等式，解出p的上限為下式，作為每個結(jié)點中分類誤差的悲觀估計通過查標(biāo)準正態(tài)分布表格，當(dāng)

=25%時z=0.69。C4.5中

的默認值為25%。4.3樸素貝葉斯分類方法樸素貝葉斯分類給定一個樣本變量X的一個觀察到的樣本x，由n個屬性A1,A2,…,An描述，其屬性取值分別為x1,x2,…,xn，

即x=(x1,x2,…,xn)，要判斷其所屬的類別，即類別屬性Y的取值，C={c1,c2,…,ck}貝葉斯定理：

樸素貝葉斯分類假設(shè)給定類別變量取值一定的情況下，各個屬性取值之間互相獨立，則

概率計算P(ci)可以用訓(xùn)練數(shù)據(jù)集中類別ci出現(xiàn)的次數(shù)占訓(xùn)練數(shù)據(jù)集總行數(shù)的比例來近似對于定性屬性，P(xj|ci)可以通過計算類別為ci的樣本中屬性Aj取值為xj的樣本所占比例來近似對于定量屬性，有兩種方法。一種方法是先將該屬性取值離散化假設(shè)變量服從某種概率分布，通過訓(xùn)練數(shù)據(jù)集估計分布的參數(shù)概率計算對于定量屬性，有兩種方法。假設(shè)變量服從正態(tài)分布N（

，

2）。計算P(xj|ci)時，在類別為ci的樣本中為屬性Aj（xj是屬性Aj的取值）的取值計算均值

ij和標(biāo)準差

ij，然后利用下面的公式進行近似估計x=（年齡<30，男，年收入30萬，單身），要預(yù)測其是否購買豪華車客戶編號年齡性別年收入（萬）婚姻豪華車1<30女86已婚否2<30男65單身否3<30男90離異否4<30女75已婚否530-50女82已婚是630-50男91已婚是730-50女200離異是830-50女40單身否930-50男20離異否10>50女96離異否11>50女80單身否12>50男50單身是13>50女80離異否14>50男92離異是P(是)=5/14,P(否)=9/14P(年齡=30-50|是)=3/5P(年齡>50|是)=2/5P(性別=女|是)=2/5P(性別=男|是)=3/5P(婚姻=已婚|是)=2/5P(婚姻=離異|是)=2/5P(婚姻=單身|是)=1/5P(年齡<30|否)=4/9P(年齡=30-50|否)=2/9P(年齡>50|否)=3/9P(性別=女|否)=6/9P(性別=男|否)=3/9P(婚姻=已婚|否)=2/9P(婚姻=離異|否)=4/9P(婚姻=單身|否)=3/9類別=“是”時，年收入的均值

為103，標(biāo)準差

為56.8類別=“否”時，年收入的均值

為70，標(biāo)準差

為25平滑處理在計算P(是|x)時，由于年齡<30的情況在類別為是的訓(xùn)練數(shù)據(jù)集中沒有出現(xiàn)，導(dǎo)致結(jié)果為0平滑（smoothing）方法count(xj,ci)代表訓(xùn)練數(shù)據(jù)集中類別為ci且屬性Aj取值為xj的樣本個數(shù)，count(ci)代表訓(xùn)練數(shù)據(jù)集中類別為ci的樣本個數(shù)。m和p的取值有各種不同的方法，一種常用的取值為，p=1/|C|,m=|C|，C為類別集合，|C|為類別的個數(shù)平滑處理DayOutlookTemperatureHumidityWind

PlayTennis

1SunnyHotHighWeakNo

2SunnyHotHighStrongNo

3OvercastHotHighWeakYes

4RainMildHighWeakYes

5RainCoolNormalWeakYes

6RainCoolNormalStrongNo

7OvercastCoolNormalStrongYes

8SunnyMildHighWeakNo

9SunnyCoolNormalWeakYes10RainMildNormalWeakYes11SunnyMildNormalStrongYes12OvercastMildHighStrongYes13OvercastHotNormalWeakYes14RainMildHighStrongNoP(PlayTennis=yes)=9/14=0.64P(outlook=sunny|yes)=2/9P(temp=cool|yes)=3/9P(humidity=hi|yes)=3/9P(wind=strong|yes)=3/9P(yes|X)~0.0053給定：X=(Outlook=sunny;Temperature=cool;Humidity=high;Wind=strong)

預(yù)測:

PlayTennis=?

給定:

(Outlook=sunny;Temperature=cool;Humidity=high;Wind=strong)

P(PlayTennis=no)=5/14=0.36P(outlook=sunny|no)=3/5P(temp=cool|no)=1/5P(humidity=hi|no)=4/5P(wind=strong|no)=3/5P(no|X)~0.02064.4K近鄰分類方法K近鄰積極方法（eagermethod）決策樹，貝葉斯懶惰方法（lazymethod）K近鄰對于一個預(yù)測樣本，從訓(xùn)練數(shù)據(jù)集中找到與其最相似的K個樣本，利用這K個樣本的類別來決定此樣本的類別K由用戶指定。相似樣本的選擇方法取決于樣本之間相似度的衡量方法，多種相似度衡量方法的介紹詳見第6章為一個測試樣本選取了K個與其距離最小的樣本之后，可以利用投票法（voting），統(tǒng)計各個類別的樣本個數(shù)，將K個類別中占大多數(shù)的類別賦予測試樣本

._+_xq+__+__+相似性度量歐式距離：給定樣本a和樣本b，分別由n個屬性A1,A2,…,An描述，兩個樣本分別表示為a=(xa1,xa2,…,xan)，b=(xb1,xb2,…,xbn)，兩個樣本之間歐式距離dab規(guī)范化（normalization）最小-最大值法（min-maxmethod）。假設(shè)屬性A原來的最大值為max，最小值為min，規(guī)范化后的取值范圍為[min1,max1]，則對于該屬性的任意的一個取值v，規(guī)范化后的取值v1可以如下計算：4.5邏輯回歸4.5邏輯回歸

4.5邏輯回歸

4.5邏輯回歸

4.5邏輯回歸

4.6支持向量機4.6支持向量機SVM:

support

vector

machine是一種二分類模型基本模型定義在特征空間上的間隔最大的線性分類器核技巧實質(zhì)上可用做非線性分類器學(xué)習(xí)策略間隔最大化，形式化為一個求解凸二次規(guī)劃問題學(xué)習(xí)算法求解凸二次規(guī)劃的最優(yōu)化算法514.6支持向量機線性可分線性不可分軟間隔支持向量機denotes+1denotes-14.6支持向量機線性可分：找到一個超平面(最優(yōu)分類面)，使得它能夠盡可能多的將兩類數(shù)據(jù)點正確的分開，同時使分開的兩類數(shù)據(jù)點距離分類面最遠。denotes+1denotes-14.6支持向量機泛化：generalization不同直線用于非訓(xùn)練樣本分類情況不同直線的泛化（generalization）能力不同4.6支持向量機

4.6支持向量機支持向量

(Support

vectors):

指的是那些離分割直線距離最近的樣本

denotes+1denotes-1SupportVectorsarethosedatapointsthatthemarginpushesupagainst4.6支持向量機間隔

(Margin):

支持向量到分割超平面（此處是直線）的距離稱為間隔

d4.6支持向量機有證明顯示，間隔最大的超平面具有最好的泛化能力為了使其與正、負例訓(xùn)練樣本的間隔都達到最大，分割超平面應(yīng)該與正例支持向量和負例支持向量的距離相同。

denotes+1denotes-14.6支持向量機

4.6支持向量機

x1x2

4.6支持向量機

x1x2

4.6支持向量機間隔:優(yōu)化問題：

約束二次規(guī)劃的求解dd對偶問題

對偶問題

4.6支持向量機線性不可分情況：x4.6支持向量機映射到高維空間如：在<x,x2>空間xx24.6支持向量機

4.6支持向量機

常用的核函數(shù)

kernel

function多項式核函數(shù)高斯核函數(shù)線性核函數(shù)

4.6

支持向量機

4.6

支持向量機軟間隔支持向量機為了使盡量多的樣本被正確分割，在目標(biāo)函數(shù)上加上懲罰項：其中C為大于0的常數(shù)。(4-44)4.6

支持向量機

4.7分類性能的度量4.5分類性能的度量4.5.1測試數(shù)據(jù)集的構(gòu)造4.5.2分類性能的度量指標(biāo)4.5.3不同分類模型的比較4.5.1測試數(shù)據(jù)集的構(gòu)造保持法（holdout）人為確定訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集的比例，常用的比例是2:1和1:1交叉驗證法（cross-validation）自助抽樣法（bootstrap）4.5.1測試數(shù)據(jù)集的構(gòu)造（續(xù)）Cross-validation(交叉驗證)每個樣本都交替地用于訓(xùn)練集或測試集n折交叉驗證n-Foldscross-validation常用：10折交叉驗證數(shù)據(jù)集分成10份，每次用9分作訓(xùn)練集，1份做測試集留一法（Leave-one-out）交叉驗證OutlookTempHumidityWindyPlaysunny8585FALSEnosunny8090TRUEnoovercast8386FALSEyesrainy7096FALSEyesrainy6880FALSEyesrainy6570TRUEnoovercast6465TRUEyessunny7295FALSEnosunny6970FALSEyesrainy7580FALSEyessunny7570TRUEyesovercast729