數(shù)據(jù)挖掘-概念與技術(shù)：Lecture 5 分類算法

1、Lecture 5 分類分類（有監(jiān)督學(xué)習(xí)）什么是分類非參數(shù)化方法(非概率派/確定性派)決策樹算法最近鄰分類器基于規(guī)則的分類器參數(shù)化方法(概率派/不確定性派)通用框架：模型、學(xué)習(xí)與推導(dǎo)樸素貝頁斯分類器集成學(xué)習(xí)樣本復(fù)雜性分類n維屬性空間X：x1, x2, , xn ，類標(biāo)識集合Y：y1, y2, , ym。給定一組實例（i = 1, 2, ），表示n維向量xi的類標(biāo)識是yi，其中xi X 。 這組實例實際上隱含了某一個函數(shù)f：XY，使得對于所有的i，有f(xi) =yi。分類問題：找到一個函數(shù)h(x)，使得對于x X，Pr(x)|f(x)h(x) 盡可能的小。分類：一個2步的過程分類過程（1）模型

2、構(gòu)造: 對已經(jīng)分類的數(shù)據(jù)集進(jìn)行描述。分類模型可以表示為分類規(guī)則, 決策樹, 或數(shù)學(xué)公式等。分類過程（1）模型評價:對構(gòu)造出的分類模型進(jìn)行評價（準(zhǔn)確度）。分類過程（2）模型使用：如果精度可以接受, 可以用該模型對未知類型的對象分類。分類過程 (1): 模型構(gòu)造訓(xùn)練數(shù)據(jù)分類算法IF rank = professorOR years 6THEN tenured = yes 分類器(模型)分類過程 (1): 模型評價 I劃分法: 訓(xùn)練集與測試集把樣本劃分成2個獨立的數(shù)據(jù)集合, 如, 訓(xùn)練集 (2/3), 測試集(1/3)。適用于大規(guī)模的數(shù)據(jù)樣本。分類過程 (1): 模型評價 II交叉驗證(Cross-

3、validation)把數(shù)據(jù)集合劃分成k 個子樣本；使用k - 1 個子樣本作為訓(xùn)練集，另一個作為測試樣本k-折交叉驗證。適用于中等規(guī)模的數(shù)據(jù)。留一測試(Leave One Out， k = n)適用于小規(guī)模數(shù)據(jù)。分類過程 (2): 用模型預(yù)測分類器測試數(shù)據(jù)未分類對象(Jeff, Professor, 4)Tenured?分類（有監(jiān)督學(xué)習(xí)）什么是分類非參數(shù)化方法(非概率派/確定性派)決策樹算法最近鄰分類器基于規(guī)則的分類器參數(shù)化方法(概率派/不確定性派)通用框架：模型、學(xué)習(xí)與推導(dǎo)樸素貝頁斯分類器集成學(xué)習(xí)樣本復(fù)雜性決策樹簡介 根結(jié)點脖子短大象長頸鹿松鼠老鼠會吱吱叫不會吱吱叫個子大在水里鼻子長脖子長

4、個子小鼻子短在陸地上犀牛河馬內(nèi)部節(jié)點：決策屬性葉子節(jié)點：目標(biāo)屬性屬性值決策樹簡介合?。簭母?jié)點到葉節(jié)點的每一條路經(jīng)都對應(yīng)著一條分類規(guī)則，規(guī)則間各個部分（各個層的條件）的關(guān)系是合取關(guān)系。析取：整個決策樹就對應(yīng)著一組析取的規(guī)則(Disjunctive Rule)。簡單：決策樹學(xué)習(xí)算法的最大優(yōu)點是簡單，不需要使用者了解過多背景知識，只需要對訓(xùn)練例子進(jìn)行較好的標(biāo)注，就能夠進(jìn)行學(xué)習(xí)。決策樹學(xué)習(xí)要解決的主要問題特征選擇：數(shù)據(jù)的哪些屬性可以被用來分類。分支準(zhǔn)則：即在眾多分支準(zhǔn)則中，每一步選擇哪一準(zhǔn)則使最終的樹更令人滿意。分類停止條件：樹增長滿足什么條件時停止。決策樹歸納算法ID3：描述ID3(Example

5、s, Attributes)Examples即訓(xùn)練樣例集，Attributes是決策屬性列表。算法返回一棵能正確分類給定Examples的決策樹。1.創(chuàng)建樹的根節(jié)點Root。2.如果Examples都為同一類，則節(jié)點標(biāo)記為該類，并返回單節(jié)點樹Root。3.如果Attributes為空，則節(jié)點標(biāo)記為Examples中最普遍的類(多數(shù)投票)，并返回單結(jié)點樹Root。決策樹歸納算法：描述（續(xù)）4.否則開始：4.1 A Attributes中分類Examples能力最好的屬性.4.2 Root的決策屬性A.4.3 對于A的每個可能值vi4.3.1 在Root下加一個新的分枝對應(yīng)測試A=vi.4.3.2

6、 令Examplesvi為Examples中滿足A屬性值為vi的子集. 4.3.3 如果Examplesvi為空4.3.3.1 在這個新分支下加一個葉子節(jié)點, 并標(biāo)記為 Examples 中最普遍的類，并返回.4.3.3.2 否則在這個新分支下加一個子樹 ID3(Examplesvi, Attributes - A)屬性選擇度量: 信息增益(ID3/C4.5)啟發(fā)式策略：選擇具有最高信息增益的屬性。期望信息：設(shè)樣本集合s含有si 個類為Ci 的元組, i = 1, , m，則對一個給定的樣本分類所需的期望信息是：熵（Entropy）：具有值 a1,a2,av的屬性A的熵E(A)為屬性A導(dǎo)致的s

7、的劃分的期望信息的加權(quán)平均和。：信息增益：在A上分枝將獲得的信息增益是決策樹構(gòu)造：一個例子決策樹構(gòu)造：一個例子計算分類所需的期望信息：決策樹構(gòu)造：一個例子屬性 age的熵的計算：決策樹構(gòu)造：一個例子屬性age的信息增益：同樣，對其它屬性有：遞歸調(diào)用：5個：3個買，2個不買決策樹構(gòu)造：一個例子ID3(5個, BC, I, S, C)ID3(4個, BC, I, S, C)ID3(5個, BC, I, S, C)age?4030.405個：2個買，3個不買4個：都買算法停止所以我們有決策樹：5個：3個買，2個不買age?4030.405個：2個買，3個不買yes決策樹構(gòu)造：一個例子ID3(5個,

8、BC, I, S, C)ID3(5個, BC, I, S, C)下一步遞歸調(diào)用ID3：針對年齡30的樣本集測試剩余的屬性計算對30的樣本集進(jìn)行分類所需的信息：其中2個買（類Yes或1），3個不買（類No或2），所以有：決策樹構(gòu)造：一個例子計算屬性student的熵E(student)：學(xué)生（屬性值1）有2個，都買，即屬于類Yes或1，非學(xué)生（屬性值2）有3個，屬于類No或2。決策樹構(gòu)造：一個例子因此，Gain(student)=I(s1,s2)-E(stu)=0.971同樣，計算其它幾個屬性的增益：Gain(income)=略Gain(credit_rating)=略屬性Student的增益最

9、大。決策樹構(gòu)造：一個例子遞歸調(diào)用：決策樹構(gòu)造：一個例子ID3(3個, BC, I, C)ID3(2個, BC, I, C)算法停止算法停止age?student?noyes40yes30.40ID3(5個, BC, I, S, C)2個：都買3個：都不買5個：3個買，2個不買所以我們有決策樹：決策樹構(gòu)造：一個例子ID3(5個, BC, I, S, C)age?student?noyes40noyesyes30.405個：3個買，2個不買下一步遞歸調(diào)用ID3：針對年齡40的樣本集測試剩余的屬性計算對40的樣本集進(jìn)行分類所需的信息：其中3個買（類Yes或1），2個不買（類No或2）決策樹構(gòu)造：一個

10、例子計算屬性Credit_Rating的熵E(CR)：fair（屬性值1）有3個，都買，即屬于類Yes或1，excellent（屬性值2）有2個，屬于類No或2。決策樹構(gòu)造：一個例子Gain(CR)=I(s1,s2)-E(CR)=0.971同樣，計算其它幾個屬性的增益Gain(income)=略Gain(Stu)=略屬性Credit_Rating的增益最大決策樹構(gòu)造：一個例子遞歸調(diào)用：決策樹構(gòu)造：一個例子ID3(2個, BC, I, S)ID3(3個, BC, I, S)算法停止算法停止age?overcaststudent?credit rating?noyesfairexcellent40

11、noyesyes30.403個：都買2個：都不買所以我們有決策樹：age?overcaststudent?credit rating?noyesfairexcellent40nonoyesyesyes30.40決策樹構(gòu)造：一個例子所有樣本已經(jīng)被分類，算法停止，我們得到最終的決策樹如下：age?student?credit rating?noyesfairexcellent40nonoyesyesyes30.40決策樹構(gòu)造：一個例子決策樹裁剪“Everything should be made as simple as possible, but not simpler.” Albert Ein

12、stein避免過度擬合Class BClass BClass AClass A noyesnonononoyesyesyesClass BClass AClass Bnoyesyes裁剪前裁剪后Class BClass AClass A noyesnonoyesyesClass B分類（有監(jiān)督學(xué)習(xí)）什么是分類非參數(shù)化方法(非概率派/確定性派)決策樹算法最近鄰分類器基于規(guī)則的分類器參數(shù)化方法(概率派/不確定性派)通用框架：模型、學(xué)習(xí)與推導(dǎo)樸素貝頁斯分類器集成學(xué)習(xí)樣本復(fù)雜性最近鄰分類（k-NN）“故近朱者赤，近墨者黑；聲和則響清，形正則影直?！泵献与墓戮湎伦罱彿诸悾╧-NN）給定一個未知樣本

13、， k最近鄰分類法搜索模式空間，找出最接近未知樣本的k個訓(xùn)練樣本。這k個訓(xùn)練樣本是未知樣本的k個“近鄰”?！敖徯浴庇卸喾N定義方式，如歐幾里得距離。未知樣本被分配到k個最近鄰者中最公共的類。k1時，未知樣本被指定到模式空間中與之最近鄰的訓(xùn)練樣本的類。示例給定訓(xùn)練集合：k=3對象1,2, 3的類是 C1。 對象4, 5, 6的類是 C2。確定對象7： (15,17)的類標(biāo)識。123456(12,8)(7,9)(13,11)(23,10)(18,23)(20,18)示例計算對象7與所有訓(xùn)練樣本的距離：7的3個最近鄰對象是3, 5, 6, 其中3的類是C1，5和6的類是C2，因此7的類標(biāo)識是 C2。

14、No1 2 3 4 5 6790 128 40 113 45 26分類（有監(jiān)督學(xué)習(xí)）什么是分類非參數(shù)化方法(非概率派/確定性派)決策樹算法最近鄰分類器基于規(guī)則的分類器參數(shù)化方法(概率派/不確定性派)通用框架：模型、學(xué)習(xí)與推導(dǎo)樸素貝頁斯分類器集成學(xué)習(xí)樣本復(fù)雜性基于規(guī)則的分類器IF Condition THEN Prediction_Class IF age = “=30” AND student = “no” THEN buys_computer = “no” IF age = “=30” AND student = “yes” THEN buys_computer = “yes”前件，后件，覆

15、蓋利用分治法學(xué)習(xí)規(guī)則Separate_and_Conquer(D)設(shè)Dc為D中類c的示例集合;For each class c While(Dc ) R Learn_One_Rule(D, Dc); Dc Dc Dc中被R覆蓋的實例; Rule_Set Rule_Set R; End whileEnd forReturn Rule_Set;學(xué)習(xí)一個規(guī)則Learn_One_Rule(D, Dc)R ; Dc D Dcwhile(R還覆蓋反例I Dc) 根據(jù)某種規(guī)則質(zhì)量度量標(biāo)準(zhǔn)選擇一個屬性Amax;從Dc 中 移除被Amax 區(qū)分的反類； R R Amax;End whileReturn R;一個

16、示例ABCD類 11111111001101011000101111010010010100000111101100010100100000111001000001000000選擇屬性AT使得：與AT取值不同的其它類的示例數(shù)目最多。A6B6C8 D8以“1”為正類學(xué)習(xí)覆蓋“1”類的規(guī)則。一個示例ABCD類11111111001101011000101111010010010100000111101100010100100000111001000001000000A2B2CD4 一個示例ABCD類11111111001101011000101111010010010100000111101100

17、010100100000111001000001000000所有反例已被覆蓋，我們得到一條規(guī)則如下：(C=1) (D=1)(Class = 1)一個示例ABCD類111001101011000101001001010000011000101001000001000001000000利用規(guī)則(C=1) (D=1)(Class = 1)刪除所有正類。該規(guī)則已覆蓋所有正類。以“0”為正類繼續(xù)學(xué)習(xí)覆蓋“0”類的規(guī)則?；谝?guī)則的分類若干問題學(xué)習(xí)到的規(guī)則能夠覆蓋整個示例空間嗎？缺省規(guī)則如何學(xué)到最優(yōu)規(guī)則？NPhard問題分類（有監(jiān)督學(xué)習(xí)）什么是分類非參數(shù)化方法(非概率派/確定性派)決策樹算法最近鄰分類器基于

18、規(guī)則的分類器參數(shù)化方法(概率派/不確定性派)通用框架：模型、學(xué)習(xí)與推導(dǎo)樸素貝頁斯分類器集成學(xué)習(xí)樣本復(fù)雜性“I, at any rate, am convinced that He does not throw dice.”1926, Albert Einstein“As I have said so many times, God doesnt play dice with the world.” 1943, Albert Einstein模型、學(xué)習(xí)與推導(dǎo)模型(Model): 用一個模型(如概率分布的數(shù)學(xué)公式)，將數(shù)據(jù)x與類狀態(tài)w聯(lián)系起來, 該模型含有參數(shù)集合;學(xué)習(xí)(Learning): 利用

19、訓(xùn)練集合xi=xi, wi, i =1, 2, , I，學(xué)習(xí)上述模型的參數(shù)集合;推導(dǎo)(Inference): 給定新數(shù)據(jù)x，確定其類狀態(tài)的后驗概率Pr(w|x, ).區(qū)分模型：Pr(w|x)針對w，選擇一個合適的概率分布Pr(w) 。其中該分布的參數(shù)是關(guān)于x的函數(shù)。例如，若類狀態(tài)w是連續(xù)的，則我們可以假設(shè)Pr(w)是一個高斯分布（正態(tài)分布），其中均值是一個關(guān)于x的函數(shù)。因為Pr(w|x)的值還依賴于分布的參數(shù)集合 ，因此我們記為 Pr(w|x, )，并稱之為后驗分布 (the posterior distribution)。區(qū)分模型：Pr(w|x)然后我們利用訓(xùn)練數(shù)據(jù)xi =xi, wi i

20、=1, 2, , I，利用極大似然法 (the maximum likelihood , ML), 極大后驗概率法( maximum a posteriori, MAP), 或貝葉斯方法來學(xué)習(xí)參數(shù)集合.推導(dǎo)：給定新數(shù)據(jù)x，直接確定其類狀態(tài)的后驗概率Pr(w|x, ).產(chǎn)生式模型 ：Pr(x|w)針對x，選擇一個合適的概率分布Pr(x) 。其中該分布的參數(shù)是關(guān)于w的函數(shù)。例如，若x是離散的，則我們可以假設(shè)Pr(x)是一個離散分布函數(shù)(a categorical distribution )，其中參數(shù)向量是一個關(guān)于w的函數(shù)。同樣，因為Pr(x|w)的值還依賴于分布的參數(shù)集合 ，因此我們記為 Pr(

21、x|w, )，并稱之為似然( the likelihood )。產(chǎn)生式模型 ：Pr(x|w)然后我們利用訓(xùn)練數(shù)據(jù) xi=xi, wi i =1, 2, , I，利用ML法，MAP法，或貝葉斯方法來學(xué)習(xí)參數(shù)集合.推導(dǎo)：給定新的數(shù)據(jù)x，計算其類狀態(tài)的后驗概率，這里用到了貝葉斯定理極大似然法ML極大似然法尋找參數(shù)集合 ，使得訓(xùn)練數(shù)據(jù)xi=xi, wi i =1, 2, , I 在該參數(shù)下最有可能 。假設(shè)訓(xùn)練數(shù)據(jù)是利用獨立同分布采樣產(chǎn)生的，則極大似然法的參數(shù)估計為：極大后驗概率法MAP在極大后驗概率法中，我們加入關(guān)于參數(shù)集合的先驗概率Pr() 。假設(shè)訓(xùn)練數(shù)據(jù)是利用獨立同分布采樣產(chǎn)生的，則極大后驗概率法

22、的參數(shù)估計為： = 貝葉斯法在貝葉斯法中，我們不再對參數(shù)進(jìn)行點估計 (point estimates)，而是假設(shè)有一系列值適合訓(xùn)練數(shù)據(jù)集，因此用哪種模型？區(qū)分模型推導(dǎo)時更簡單；生成模型更加復(fù)雜一些：x比w往往高維，因此參數(shù)往往更多，訓(xùn)練困難；生成模型反映了數(shù)據(jù)的實際產(chǎn)生過程，如果想把數(shù)據(jù)的產(chǎn)生過程集成到模型中，則應(yīng)該考慮生成模型；如果訓(xùn)練數(shù)據(jù)中有大量的遺失數(shù)據(jù)，則應(yīng)該考慮生成模型；生成模型更容易集成背景（專家知識）。實例：二元分類類狀態(tài)：w=0或1區(qū)分模型：因為類w只有兩個值，因此我們采用Bernoulli分布，該分布具有唯一參數(shù)，表示w=1的概率。二元分類：區(qū)分模型學(xué)習(xí)(參數(shù)估計)： = 0

23、 1的最大似然估計推導(dǎo)：對于新的數(shù)據(jù)x，將學(xué)習(xí)到的和x代入計算后驗概率。二元分類：生成模型生成模型：w=1的先驗概率參數(shù)p二元分類：生成模型學(xué)習(xí)(參數(shù)估計)： = 0 0 1 1 p的最大似然估計：用w=0的數(shù)據(jù)訓(xùn)練參數(shù)0與0；用w=1的數(shù)據(jù)訓(xùn)練參數(shù)1，1。0 =二元分類：生成模型用w的 數(shù)據(jù)訓(xùn)練得到p。例如用極大似然法訓(xùn)練得到p= np /n.1 二元分類：生成模型推導(dǎo)：對于新的數(shù)據(jù)x，將學(xué)習(xí)到的和x代入下式計算后驗概率分類（有監(jiān)督學(xué)習(xí)）什么是分類非參數(shù)化方法(非概率派/確定性派)決策樹算法最近鄰分類器基于規(guī)則的分類器參數(shù)化方法(概率派/不確定性派)通用框架：模型、學(xué)習(xí)與推導(dǎo)樸素貝頁斯分類器

24、集成學(xué)習(xí)樣本復(fù)雜性樸素貝頁斯分類器X是一個類標(biāo)識未知的數(shù)據(jù)樣本。對分類問題, 確定P(Ci|X): 給定觀測數(shù)據(jù)樣本X，確定X屬于類Ci的概率。P(Ci): 類Ci的先驗概率(prior probability) (即在我們觀測任何數(shù)據(jù)之前的初始概率, 它反映了背景知識)P(X): 樣本數(shù)據(jù)被觀測的概率。P(X|Ci): 在屬于類Ci的前提下，觀測到樣本X的概率。貝葉斯定理給定訓(xùn)練集X, X屬于類Ci的后驗概率(posteriori probability), P(C|X) 遵守如下貝葉斯定理MAP (Maximum a posteriori，極大后驗) 假設(shè)實際應(yīng)用的困難: 需要許多概率的初

25、始知識, 需要較多的計算時間。簡化：樸素貝葉斯分類器一個簡化假設(shè): 屬性之間是條件獨立的:一旦知道了概率P(X|Ci), 把X賦予使得 P(X|Ci)*P(Ci)具有極大值的類Ci。一個例子類:C1:buys_computer=yesC2:buys_computer=no數(shù)據(jù)樣本X =(age=30,Income=medium,Student=yesCredit_rating=Fair)一個例子對每一個類，計算P(X|Ci) P(age=“30” | buys_computer=“yes”) = 2/9=0.222 P(age=“30” | buys_computer=“no”) = 3/5

26、=0.6 P(income=“medium” | buys_computer=“yes”)= 4/9 =0.444 P(income=“medium” | buys_computer=“no”) = 2/5 = 0.4 P(student=“yes” | buys_computer=“yes)= 6/9 =0.667 P(student=“yes” | buys_computer=“no”)= 1/5=0.2 P(credit_rating=“fair” | buys_computer=“yes”)=6/9=0.667 P(credit_rating=“fair” | buys_computer=“no”)=2/5=0.4X=(age=30 ,income =medium, student=yes,credit_rating=fair) P(X|Ci) : P(X|buys_computer=“yes”)= 0.222 0.444 0.667 0.0.667 =0.044 P(X|buys_computer=“no”)= 0.6 0.4 0.2 0.