數(shù)據(jù)挖掘-分類課件ppt

,Click to edit Master,,Click to edit Master text styles Click to edit Master Click to edit Master,,Second level,,Third level,,Fourth level,,Fifth level,,*,DMKD Sides By MAO,*,,Click to edit Master,,Click to edit Master text styles Click to edit Master Click to edit Master,,Second level,,Third level,,Fourth level,,Fifth level,,*,DMKD Sides By MAO,*,,Click to edit Master,,Click to edit Master text styles Click to edit Master Click to edit Master,,Second level,,Third level,,Fourth level,,Fifth level,,*,DMKD Sides By MAO,*,第三章 分類方法,,,,,內(nèi)容提要,分類的基本概念與步驟,,,基于距離的分類算法,,決策樹分類方法,,貝葉斯分類,,實(shí)值預(yù)測(cè),,與分類有關(guān)的問(wèn)題,,2024/11/26,1,,分類的流程,,根據(jù)現(xiàn)有的知識(shí)，我們得到了一些關(guān)于爬行動(dòng)物和鳥類的信息，我們能否對(duì)新發(fā)現(xiàn)的物種，比如動(dòng)物A，動(dòng)物B進(jìn)行分類？,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,2,,分類的流程,,步驟一：將樣本轉(zhuǎn)化為等維的數(shù)據(jù)特征（特征提取）。,,所有樣本必須具有相同數(shù)量的特征,,兼顧特征的全面性和獨(dú)立性,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,3,,分類的流程,,步驟二：選擇與類別相關(guān)的特征（特征選擇）。,,比如，綠色代表與類別非常相關(guān)，黑色代表部分相關(guān)，灰色代表完全無(wú)關(guān),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,4,,分類的流程,,步驟三：建立分類模型或分類器（分類）。,,分類器通?？梢钥醋饕粋€(gè)函數(shù)，它把特征映射到類的空間上,,,2024/11/26,5,,如何避免過(guò)度訓(xùn)練,,分類,也稱為,有監(jiān)督學(xué)習(xí),(supervised learning),與之相對(duì)于的是無(wú)監(jiān)督學(xué)習(xí)(unsupervised learning),比如聚類。,,分類與聚類的最大區(qū)別在于，分類數(shù)據(jù)中的一部分的類別是已知的，而聚類數(shù)據(jù)的類別未知。,,建立分類模型需要學(xué)習(xí)一部分已知數(shù)據(jù)，如果訓(xùn)練時(shí)間過(guò)長(zhǎng)，或者預(yù)測(cè)模型參數(shù)太多而樣本較少，將導(dǎo)致,過(guò)度訓(xùn)練,(overfitting)。,,,,2024/11/26,6,,如何避免過(guò)度訓(xùn)練,,避免過(guò)度訓(xùn)練最重要一點(diǎn)是，,模型的參數(shù)量應(yīng)遠(yuǎn)小于樣本的數(shù)量,。,,應(yīng)建立,訓(xùn)練集,(training set)和,測(cè)試集,(test set)。,,訓(xùn)練集應(yīng)用于建立分類模型,,測(cè)試集應(yīng)用于評(píng)估分類模型,,K折疊交叉驗(yàn)證,(K-fold cross validation)：將初始采樣分割成K個(gè)子樣本(S,1,，S,2,,...,S,k,)，取K-1個(gè)做訓(xùn)練集，另外一個(gè)做測(cè)試集。交叉驗(yàn)證重復(fù)K次，每個(gè)子樣本都作為測(cè)試集一次，平均K次的結(jié)果，最終得到一個(gè)單一估測(cè)。,,,,2024/11/26,7,,分類模型的評(píng)估,,真陽(yáng)性(,T,rue,P,ositive)： 實(shí)際為陽(yáng)性 預(yù)測(cè)為陽(yáng)性,,真陰性(,T,rue,N,egative)：實(shí)際為陰性 預(yù)測(cè)為陰性,,假陽(yáng)性(,F,alse,P,ositive)： 實(shí)際為陰性 預(yù)測(cè)為陽(yáng)性,,假陰性(,F,alse,N,egative)：實(shí)際為陽(yáng)性 預(yù)測(cè)為陰性,,,,預(yù)測(cè)是否正確 預(yù)測(cè)結(jié)果,,比如預(yù)測(cè)未知?jiǎng)游锸区B類還是爬行動(dòng)物，陽(yáng)性代表爬行動(dòng)物，陰性代表,非,爬行動(dòng)物，請(qǐng)大家闡述 TP=10，TN=8，F(xiàn)N=3，F(xiàn)P=2是什么意義,2024/11/26,8,,分類模型的評(píng)估,,靈敏度,(Sensitivity)： TP/(TP+FN),,也稱為查全率(Recall),,數(shù)據(jù)集共有13只爬行動(dòng)物，其中10只被正確預(yù)測(cè)為爬行動(dòng)物，靈敏度為10/13,,特異度,(Specificity): TN/(TN+FP),,數(shù)據(jù)集有10只非爬行動(dòng)物，其中8只被預(yù)測(cè)為非爬行動(dòng)物，特異度為8/10,,精度,(Precision): TP/(TP+FP),,分類器預(yù)測(cè)了12只動(dòng)物為爬行動(dòng)物，其中10只確實(shí)是爬行動(dòng)物，精度為10/12,,準(zhǔn)確率,(Accuracy): (TP+TN)/(TP+TN+FN+FP),,數(shù)據(jù)集包含23只動(dòng)物，其中18只預(yù)測(cè)為正確的分類，準(zhǔn)確率為18/23,,,2024/11/26,9,,分類模型的評(píng)估,,對(duì)于非平衡(unblanced)的數(shù)據(jù)集,以上指標(biāo)并不能很好的評(píng)估預(yù)測(cè)結(jié)果。,,非平衡的數(shù)據(jù)集是指陽(yáng)性數(shù)據(jù)在整個(gè)數(shù)據(jù)集中的比例很小。比如，數(shù)據(jù)集包含10只爬行動(dòng)物，990只爬行動(dòng)物，此時(shí)，是否預(yù)測(cè)正確爬行動(dòng)物對(duì)準(zhǔn)確率影響不大。,,更平衡的評(píng)估標(biāo)準(zhǔn)包括,馬修斯相關(guān)性系數(shù),(Matthews correlation coefficient)和,ROC曲線,。,,馬修斯相關(guān)性系數(shù),定義為,,,2024/11/26,10,,分類模型的評(píng)估,,ROC曲線通過(guò)描述真陽(yáng)性率(TPR)和假陽(yáng)性率(FPR)來(lái)實(shí)現(xiàn)，其中TPR=TP/(TP+FN), FPR=FP/(FP+TN)。,,大部分分類器都輸出一個(gè)實(shí)數(shù)值(可以看作概率),通過(guò)變換閾值可以得到多組TPR與FPR的值。,,,,2024/11/26,11,,第三章 分類方法,,,,,內(nèi)容提要,分類的基本概念與步驟,,基于距離的分類算法,,決策樹分類方法,,貝葉斯分類,,實(shí)值預(yù)測(cè),,與分類有關(guān)的問(wèn)題,,2024/11/26,12,,基于距離的分類算法的思路,,定義,4-2,給定一個(gè)數(shù)據(jù)庫(kù),D,={,t,1,，,t,2,，,…,，,t,n,},和一組類,C,={,C,1,，,…,，,C,m,},。假定每個(gè)元組包括一些數(shù)值型的屬性值：,t,i,={,t,i1,，,t,i2,，,…,，,t,ik,},，每個(gè)類也包含數(shù)值性屬性值：,C,j,={,C,j1,，,C,j2,，,…,，,C,jk,},，則分類問(wèn)題是要分配每個(gè),t,i,到滿足如下條件的類,C,j,：,,sim,(,t,i,，,C,j,)>=,sim,(,t,i,，,C,l,),，,?,C,l,∈,C,，,C,l,≠,C,j,，,,其中,sim,(,t,i,，,C,j,),被稱為相似性。,,在實(shí)際的計(jì)算中往往用,距離,來(lái)表征，距離越近，相似性越大，距離越遠(yuǎn)，相似性越小。,,距離的計(jì)算方法有多種，最常用的是通過(guò)計(jì)算每個(gè)類的中心來(lái)完成。,2024/11/26,13,,基于距離的分類算法的一般性描述,,,,,,,,,算法,4-1,通過(guò)對(duì)每個(gè)樣本和各個(gè)類的中心來(lái)比較，從而可以找出他的最近的類中心，得到確定的類別標(biāo)記。,算法,4-1,基于距離的分類算法,,輸入：每個(gè)類的中心,C,1,，,…,，,C,m,；待分類的元組,t,。,,輸出：輸出類別,c,。,,（,1,）,dist=,∞,；,//,距離初始化,,（,2,）,FOR i:=1 to m DO,,（,3,）,IF,dis,(,c,i,，,t,)<dist THEN BEGIN,,（,4,）,c,← i,；,,（,5,）,dist←dist(,c,i,，,t,),；,,（,6,）,END.,2024/11/26,14,,基于距離的分類方法的直觀解釋,,,,,（,a,）類定義,（,b,）待分類樣例,（,c,）分類結(jié)果,2024/11/26,15,,距離分類例題,,C1=(3,3,4,2), C2=(8,5,-1,-7), C3=(-5,-7,6,10);,,請(qǐng)用基于距離的算法給以下樣本分類：,,(5,5,0,0) (5,5,-5,-5) (-5,-5,5,5),,,2024/11/26,16,,K-,近鄰分類算法,,K-,近鄰分類算法（,K Nearest Neighbors,，簡(jiǎn)稱,KNN,）通過(guò)計(jì)算每個(gè)訓(xùn)練數(shù)據(jù)到待分類元組的距離，取和待分類元組距離最近的,K,個(gè)訓(xùn)練數(shù)據(jù)，,K,個(gè)數(shù)據(jù)中哪個(gè)類別的訓(xùn)練數(shù)據(jù)占多數(shù)，則待分類元組就屬于哪個(gè)類別。,算法,4-2 K-,近鄰分類算法,,輸入： 訓(xùn)練數(shù)據(jù),T,；近鄰數(shù)目,K,；待分類的元組,t,。,,輸出： 輸出類別,c,。,,（,1,）,N,=,?,；,,（,2,）,FOR each,d,∈,T,DO BEGIN,,（,3,）,IF |,N,|≤,K,THEN,,（,4,）,N,=,N,∪{,d,},；,,（,5,）,ELSE,,（,6,）,IF,?,,u,∈,N,such that,sim,(,t,，,u,)〈,sim,(,t,，,d,) THEN,,BEGIN,,（,7,）,N,=,N,- {,u,},；,,（,8,）,N,=,N,∪{,d,},；,,（,9,）,END,,（,10,）,END,,（,11,）,c=class to which the most u ∈N.,,2024/11/26,17,,KNN,的例子,,,姓名 性別 身高,(,米,),類別,,Kristina,女,1.6,矮,,Jim,男,2,高,,Maggie,女,1.,83,,高,,Martha,,,女,1.88,高,,Stephanie,女,1.7,矮,,Bob,男,1.85,中等,,Kathy,女,1.6,矮,,Dave,男,1.7,矮,,Worth,男,2.2,高,,Steven,男,2.1,高,,Debbie,女,1.8,高,,Todd,男,1.,82,,中等,,Kim,女,1.,7,,中等,,Amy,女,1.,75,,中等,,Wynette,女,1.7,3,,中等,只使用身高做特征，K=3，對(duì)于樣本應(yīng)屬于哪個(gè)類別？,,,,,僅使用同性別樣本做訓(xùn)練，K=3，對(duì)于樣本應(yīng)屬于哪個(gè)類別？,,,2024/11/26,18,,第三章 分類方法,,,,,內(nèi)容提要,分類的基本概念與步驟,,基于距離的分類算法,,決策樹分類方法,,,貝葉斯分類,,實(shí)值預(yù)測(cè),,與分類有關(guān)的問(wèn)題,,2024/11/26,19,,決策樹表示與例子,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,年齡,？,學(xué)生,？,是,信用,？,<=30,30—40,>40,否,是,良好,一般,是,否,是,否,2024/11/26,20,,決策樹表示與例子,,決策樹,（,Decision Tree,）的每個(gè)內(nèi)部結(jié)點(diǎn)表示一個(gè)屬性（特征），每個(gè)分枝代表一個(gè)特征的一個(gè)（類）取值；,,每個(gè)樹葉結(jié)點(diǎn)代表類或類分布。,,決策樹分類方法采用自頂向下的遞歸方式，在決策樹的內(nèi)部結(jié)點(diǎn)進(jìn)行屬性的比較，從而判斷從該結(jié)點(diǎn)向下的分枝，在決策樹的葉結(jié)點(diǎn)得到結(jié)論。,,從決策樹的根到葉結(jié)點(diǎn)的一條路徑就對(duì)應(yīng)著一條規(guī)則，整棵決策樹就對(duì)應(yīng)著一組規(guī)則。,,決策樹分類模型的建立通常分為兩個(gè)步驟：,,決策樹生成,,決策樹修剪,,,2024/11/26,21,,決策樹生成算法描述,,算法,4-3 Generate_decision_tree(samples, attribute_list) /*,決策樹生成算法*,/,,輸入：訓(xùn)練樣本,samples,，由離散值屬性表示；輸出：一棵決策樹。,,（,1,） 創(chuàng)建結(jié)點(diǎn),N,；,,（,2,）,IF,,samples,,都在同一個(gè)類,C,,THEN,,返回,N,,作為葉結(jié)點(diǎn)，以類,C,標(biāo)記；,,（,3,）,IF,attribute_list,為空,THEN,,返回,N,作為葉結(jié)點(diǎn)，標(biāo)記為,samples,中最普通的類；,//,多數(shù)表決,,（,4,） 選擇,attribute_list,中具有最高,信息增益,的屬性,test_attribute,；,,（,5,） 標(biāo)記結(jié)點(diǎn),N,為,test_attribute,；,,（,6,）,FOR,test_attribute,的每個(gè)取值,a,i,由結(jié)點(diǎn),N,長(zhǎng)出一個(gè)條件為,test_attribute=,a,i,的分枝；,,（,7,）設(shè),s,i,是,samples,中,test_attribute =,a,i,的樣本的集合；,//,一個(gè)劃分,,（,8,）,IF,,s,i,為空,THEN,,回退到test_attribute的其它取值；,,（,9,）,ELSE,,加上一個(gè)由,Generate_decision_tree(,s,i,，,attribute_list-test_attribute),返回的結(jié)點(diǎn)；,2024/11/26,22,,決策樹修剪算法,,基本的決策樹構(gòu)造算法沒有考慮噪聲，因此生成的決策樹完全與訓(xùn)練集擬合。在有噪聲情況下，將導(dǎo)致過(guò)分?jǐn)M合（,Overfitting,），即對(duì)訓(xùn)練數(shù)據(jù)的完全擬合反而使對(duì)現(xiàn)實(shí)數(shù)據(jù)的分類預(yù)測(cè)性能下降。,,比如每個(gè)樣本都是一個(gè)葉子節(jié)點(diǎn)。,,現(xiàn)實(shí)世界的數(shù)據(jù)一般不可能是完美的，可能缺值（,Missing Values,）；數(shù)據(jù)不完整；含有噪聲甚至是錯(cuò)誤的,。,,剪枝,是一種克服噪聲的基本技術(shù)，同時(shí)它也能使樹得到簡(jiǎn)化而變得更容易理解。有兩種基本的剪枝策略。,,2024/11/26,23,,決策樹修剪算法,,預(yù)先剪枝,（Pre-Pruning）：在生成樹的同時(shí)決定是繼續(xù)對(duì)不純的訓(xùn)練子集進(jìn)行劃分還是停機(jī)。,,后剪枝,（Post-Pruning）：是一種擬合+化簡(jiǎn)（fitting-and-simplifying）的兩階段方法。首先生成與訓(xùn)練數(shù)據(jù)完全擬合的一棵決策樹，然后從樹的葉子開始剪枝，逐步向根的方向剪。剪枝時(shí)要用到一個(gè)測(cè)試數(shù)據(jù)集合（Tuning Set或Adjusting Set），如果存在某個(gè)葉子剪去后能使得在測(cè)試集上的準(zhǔn)確度或其他測(cè)度不降低（不變得更壞），則剪去該葉子；否則停機(jī)。理論上講，后剪枝好于預(yù)先剪枝，但計(jì)算復(fù)雜度大。,,2024/11/26,24,,決策樹修剪算法,,構(gòu)造好的決策樹的關(guān)鍵在于,如何選擇屬性,進(jìn)行樹的拓展。研究結(jié)果表明，一般情況下,樹越小則樹的預(yù)測(cè)能力越強(qiáng)。由于構(gòu)造最小的樹是NP-難問(wèn)題，因此只能采取用啟發(fā)式策略來(lái)進(jìn)行。,,屬性選擇依賴于各種對(duì)例子子集的,不純度,（Impurity）度量方法，包括信息增益（Informatin Gain）、信息增益比（Gain Ratio）、Gini-index、距離度量（Distance Measure）、J-measure等。,,2024/11/26,25,,ID3,算法,,ID3,是一個(gè)著名決策樹生成方法：,,決策樹中每一個(gè),非葉結(jié)點(diǎn),對(duì)應(yīng)著一個(gè)非類別,屬性,(特征)，,樹枝,代表這個(gè),屬性的值,。一個(gè),葉結(jié)點(diǎn),代表從樹根到葉結(jié)點(diǎn)之間的路徑對(duì)應(yīng)的記錄所屬的,類別屬性,值。,,每一個(gè)非葉結(jié)點(diǎn)都將與屬性中具有最大信息量的非類別屬性相關(guān)聯(lián)。,,采用信息增益來(lái)選擇能夠最好地將樣本分類的屬性,。,,對(duì),ID3,算法采用如下方式講解：,,給出信息增益對(duì)應(yīng)的計(jì)算公式；,,通過(guò)一個(gè)例子來(lái)說(shuō)明它的主要過(guò)程。,2024/11/26,26,,信息增益的計(jì)算,,設(shè),S,是,s,個(gè)數(shù)據(jù)樣本的集合，定義,m,個(gè)不同類,C,i,（,i=1,，,2,，,…,，,m,），設(shè),s,i,是,C,i,類中的樣本的數(shù)量。對(duì)給定的樣本,S,所期望的,信息值,由下式給出：,,,,其中,p,i,是任意樣本屬于,C,i,的概率：,s,i,,/ s,。,,,例題：數(shù)據(jù)集有4個(gè)類，分別有8個(gè)，4個(gè)，2個(gè)，2個(gè)樣本，求該數(shù)據(jù)集的信息值。,,,問(wèn)題：信息值的取值范圍是什么？,2024/11/26,27,,信息增益的計(jì)算,,,,例題：數(shù)據(jù)集有2個(gè)類，求該數(shù)據(jù)集的信息值。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,28,,信息增益的計(jì)算,,設(shè)屬性A具有個(gè)不同值{a,1,, a,2,, …, a,v,} ，可以用屬性A將樣本S劃分為 {S,1,, S,2,, …, S,v,} ，設(shè),S,ij,是Sj中Ci類的樣本數(shù)，則由A劃分成子集的熵由下式給出：,,,,,,,有A進(jìn)行分枝將獲得的信息增益可以由下面的公式得到：,,,,,,使用屬性,,后的信息值,未使用屬性,,的信息值,2024/11/26,29,,信息增益的計(jì)算,,,,例題：數(shù)據(jù)集有2個(gè)類。,,使用,是否學(xué)生,作為屬性，求該屬性的信息增益。,,,,,使用,信用狀況,作為屬性，求該屬性的信息增益。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,30,,ID3算法的例子,,選擇信息增益最大的屬性特征作為根節(jié)點(diǎn)。,,Gain(年齡)=0.342 Gain(收入)=0,,Gain(是否學(xué)生)=0.333 Gain(信用狀況)=0,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,年齡,？,？,？,是,<=30,30—40,>40,2024/11/26,31,,ID3算法的例子,,對(duì)于,<=,30的分支,,Gain(收入)=0.315 Gain(是否學(xué)生)=0.315 Gain(信用狀況)=0.815,,對(duì)于30,—,40的分支,,Gain(收入)=1 Gain(是否學(xué)生)=0 Gain(信用狀況)=1,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,年齡？,信用狀況？,收入？,是,<=30,30—40,>40,否,是,是,否,良好,一般,高,低,2024/11/26,32,,ID3,算法的性能分析,,ID3,算法的假設(shè)空間包含所有的決策樹，它是關(guān)于現(xiàn)有屬性的有限離散值函數(shù)的一個(gè)完整空間。,,ID3,算法在搜索的每一步都使用當(dāng)前的所有訓(xùn)練樣例，大大降低了對(duì)個(gè)別訓(xùn)練樣例錯(cuò)誤的敏感性。因此，通過(guò)修改終止準(zhǔn)則，可以容易地?cái)U(kuò)展到處理含有噪聲的訓(xùn)練數(shù)據(jù)。,,2024/11/26,33,,ID3,算法的性能分析,,ID3算法在搜索過(guò)程中不進(jìn)行回溯。所以，它易受無(wú)回溯的爬山搜索中的常見風(fēng)險(xiǎn)影響：,收斂到局部最優(yōu)而不是全局最優(yōu),。,,ID3算法只能處理,離散值的屬性,。,,信息增益度量存在一個(gè)內(nèi)在偏置，它,偏袒具有較多值的屬性,。例如，如果有一個(gè)屬性為日期，那么將有大量取值，這個(gè)屬性可能會(huì)有非常高的信息增益。假如它被選作樹的根結(jié)點(diǎn)的決策屬性則可能形成一顆非常寬的樹，這棵樹可以理想地分類訓(xùn)練數(shù)據(jù)，但是對(duì)于測(cè)試數(shù)據(jù)的分類性能可能會(huì)相當(dāng)差。,,ID3算法增長(zhǎng)樹的每一個(gè)分支的深度，直到,屬性的使用無(wú)法導(dǎo)致信息增益,。當(dāng)數(shù)據(jù)中有噪聲或訓(xùn)練樣例的數(shù)量太少時(shí)，產(chǎn)生的樹會(huì)過(guò)渡擬合訓(xùn)練樣例。,,問(wèn)題,：ID3樹可以導(dǎo)致過(guò)度擬合，那是否它一定能對(duì)訓(xùn)練集完全正確的分類呢？,,2024/11/26,34,,C4.5,算法對(duì),ID3,的主要改進(jìn),,C4.5,算法是從,ID3,算法演變而來(lái)，除了擁有,ID3,算法的功能外，,C4.5,算法引入了新的方法和增加了新的功能：,,用信息增益,比例,的概念；,,合并具有,連續(xù)屬性,的值；,,可以處理具有缺少屬性值的訓(xùn)練樣本；,,通過(guò)使用不同的修剪技術(shù)以避免樹的過(guò)度擬合；,,K,交叉驗(yàn)證；,,規(guī)則的產(chǎn)生方式等。,2024/11/26,35,,信息增益比例的概念,,信息增益比例,是在信息增益概念基礎(chǔ)上發(fā)展起來(lái)的，一個(gè)屬性的信息增益比例用下面的公式給出：,,,,其中,,假如我們以屬性,A,的值為基準(zhǔn)對(duì)樣本進(jìn)行分割的化，,Splitl(A),就是前面熵的概念。,,,,,2024/11/26,36,,信息增益比例的計(jì)算,,,,例題：數(shù)據(jù)集有2個(gè)類。,,使用,是否學(xué)生,作為屬性，求該屬性的信息增益比例。,,,使用,年齡,作為屬性，求該屬性的信息增益比例。,,,,討論：信息增益和信息增益比例的差異在哪里？,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,37,,C4.5,處理連續(xù)值的屬性,,對(duì)于連續(xù)屬性值，,C4.5,其處理過(guò)程如下：,,根據(jù)屬性的值，對(duì)數(shù)據(jù)集排序；,,用不同的閾值將數(shù)據(jù)集動(dòng)態(tài)的進(jìn)行劃分；,,取兩個(gè)實(shí)際值中的中點(diǎn)作為一個(gè)閾值；,,取兩個(gè)劃分，所有樣本都在這兩個(gè)劃分中；,,得到所有可能的閾值、增益及增益比；,,在每一個(gè)屬性會(huì)變?yōu)槿蓚€(gè)取值，即小于閾值或大于等于閾值。,,,簡(jiǎn)單地說(shuō)，針對(duì)屬性有連續(xù)數(shù)值的情況，則在訓(xùn)練集中可以按升序方式排列。如果屬性,A,共有,n,種取值，則對(duì)每個(gè)取值,v,j,（,j=1,，,2,，┄，,n,），將所有的記錄進(jìn)行劃分：一部分小于,v,j,；另一部分則大于或等于,v,j,。針對(duì)每個(gè),v,j,計(jì)算劃分對(duì)應(yīng)的增益比率，選擇增益最大的劃分來(lái)對(duì)屬性,A,進(jìn)行離散化 。,2024/11/26,38,,C4.5處理連續(xù)值的屬性,,例題：使用C4.5算法將連續(xù)的屬性(收入)轉(zhuǎn)化為離散的類。,,根據(jù)屬性的值，對(duì)數(shù)據(jù)集排序；,,,取兩個(gè)實(shí)際值中的中點(diǎn)作為一個(gè)閾值；,,,取兩個(gè)劃分，所有樣本都在這兩個(gè)劃分中；,,,得到所有可能的閾值、增益及增益比；,,,在每一個(gè)屬性會(huì)變?yōu)槿蓚€(gè)取值，即小于閾值或大于等于閾值。,,,,,,,,,,,,,,,,,,,2024/11/26,39,,C4.5處理連續(xù)值的屬性,,例題：使用C4.5算法將連續(xù)的屬性(收入)轉(zhuǎn)化為離散的類。,,選擇增益最大的劃分來(lái)對(duì)屬性A進(jìn)行離散化 。,,,GainRatio(劃分：2750)=0.2,,GainRatio(劃分：3100)=0.39,,GainRatio(劃分：3625)=0.53,,GainRatio(劃分：4458)=1,,GainRatio(劃分：？)=0.53,,GainRatio(劃分：8285)=0.39,,GainRatio(劃分：10900)=0.2,,,收入小于4458合并為收入低,,收入大于等于4458合并為收入高,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,40,,C4.5,的其他處理,,,C4.5,處理的樣本中可以含有未知屬性值，其處理方法是用最常用的值替代或者是將最常用的值分在同一類中。,,具體采用概率的方法，依據(jù)屬性已知的值，對(duì)屬性和每一個(gè)值賦予一個(gè)概率，取得這些概率，取得這些概率依賴于該屬性已知的值。,,規(guī)則的產(chǎn)生：,一旦樹被建立，就可以把樹轉(zhuǎn)換成,if-then,規(guī)則。,,規(guī)則存儲(chǔ)于一個(gè)二維數(shù)組中，每一行代表樹中的一個(gè)規(guī)則，即從根到葉之間的一個(gè)路徑。表中的每列存放著樹中的結(jié)點(diǎn)。,,2024/11/26,41,,,C4.5,算法例子,,,,,,,,,,,樣本數(shù)據(jù),,天氣,,溫度,,濕度,,風(fēng),,網(wǎng)球,Sunny Hot 85 false No,,Sunny Hot 90 true No,,Overcast Hot 78 false Yes,,Rain Mild 96 false Yes,,Rain Cool 80 false Yes,,Rain Cool 70 true No,,Overcast Cool 65 true Yes,,Sunny Mild 95 false No,,Sunny Cool 70 false Yes,,Rain Mild 80 false Yes,,Sunny Mild 70 true Yes,,Overcast Mild 90 true Yes,,Overcast Hot 75 false Yes,,Rain Mild 80 true No,,,,,,（,1,）首先對(duì),濕度,進(jìn)行屬性離散化，針對(duì)上面的訓(xùn)練集合，通過(guò)檢測(cè)每個(gè)劃分而確定最好的劃分在,75,處，則這個(gè)屬性的范圍就變?yōu)?{,（,<=75,，,>75,）,},。,,（,2,）計(jì)算目標(biāo)屬性,打網(wǎng)球,分類的期望信息：,,,,,（,3,）計(jì)算每個(gè)屬性的,GainRatio,：,,,,,,,,,,,2024/11/26,42,,,C4.5,算法例子,,,,,,,,,,,,,,,（4）選取最大的GainRatio，根據(jù),天氣,的取值，得到三個(gè)分枝。,,（5）再擴(kuò)展各分枝節(jié)點(diǎn)，得到最終的決策樹（見課本圖4-7 ）。,,,,問(wèn)題：就天氣=Sunny這一分支，請(qǐng)用C4.5算法構(gòu)造決策樹。,樣本數(shù)據(jù),,天氣,,溫度,,濕度,,風(fēng),,網(wǎng)球,Sunny Hot 85 false No,,Sunny Hot 90 true No,,Sunny Mild 95 false No,,Sunny Cool 70 false Yes,,Sunny Mild 70 true Yes,,2024/11/26,43,,第三章 分類方法,,,,,內(nèi)容提要,分類的基本概念與步驟,,基于距離的分類算法,,決策樹分類方法,,貝葉斯分類,,實(shí)值預(yù)測(cè),,與分類有關(guān)的問(wèn)題,,2024/11/26,44,,貝葉斯分類,,定義4-,3,設(shè),X,是類標(biāo)號(hào)未知的數(shù)據(jù)樣本。設(shè),H,為某種假定，如數(shù)據(jù)樣本,X,屬于某特定的類,C。,對(duì)于分類問(wèn)題，我們希望確定,P(H|X)，,即給定觀測(cè)數(shù)據(jù)樣本,X，,假定,H,成立的概率。貝葉斯定理給出了如下計(jì)算,P(H|X),的簡(jiǎn)單有效的方法:,,,,P(X |H),代表假設(shè),H,成立的情況下，觀察到,X,的概率。,P(H| X ),是,后驗(yàn)概率,，,或稱為X發(fā)生后觀測(cè)到H的,條件概率,。,,例如，假定數(shù)據(jù)樣本由一些人組成，假定,X,表示頭發(fā)顏色，,H,表示膚色，則,P(H|X),反映當(dāng)我們看到,X,是黑色時(shí)，我們對(duì)H為黃色的確信程度。,,,,2024/11/26,45,,樸素貝葉斯分類的工作原理,,觀測(cè)到的樣本具有屬性,,收入低 是學(xué)生 信用良好,,現(xiàn)在的問(wèn)題相當(dāng)于比較兩個(gè)條件概率的大小,,P(買電腦|收入低,是學(xué)生, 信用良好),,P(不買電腦|收入低,是學(xué)生, 信用良好),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,46,,樸素貝葉斯分類,,樸素貝葉斯分類的工作過(guò)程如下：,,(1)  每個(gè)數(shù)據(jù)樣本用一個(gè),n,維特征向量,X,= {,x,1,，,x,2,，……，,x,n,},表示，分別描述對(duì),n,個(gè)屬性,A,1,，,A,2,，……，,A,n,樣本的,n,個(gè)度量。,,(2) 假定有,m,個(gè)類,C,1,，,C,2,，…，,C,m,，,給定一個(gè)未知的數(shù)據(jù)樣本,X,（,即沒有類標(biāo)號(hào)），分類器將預(yù)測(cè),X,屬于具有最高條件概率（條件,X,下）的類。,,也就是說(shuō)，樸素貝葉斯分類將未知的樣本分配給類Ci（1≤i≤m）當(dāng)且僅當(dāng)P(Ci|X)> P(Cj|X)，對(duì)任意的j=1，2，…，m，j≠i。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,47,,樸素貝葉斯分類,(,續(xù),),,根據(jù)貝葉斯定理：,,,,,,由于,P,(,X,),對(duì)于所有類為,常數(shù),，只需要,P,(,X,|,C,i,)*,P,(,C,i,),最大即可。,,注意，類的先驗(yàn)概率可以用P(C,i,)=S,i,/S計(jì)算，其中S,i,是類C,i,中的訓(xùn)練樣本數(shù)，而S是訓(xùn)練樣本總數(shù)。,,因此問(wèn)題就轉(zhuǎn)換為計(jì)算,P,(,X,|,C,i,),。,,,,,2024/11/26,48,,樸素貝葉斯分類,(,續(xù),),,給定具有許多屬性的數(shù)據(jù)集，計(jì)算,P,(,X,|,C,i,),的計(jì)算量可能非常大且不易計(jì)算。為降低計(jì)算,P,(,X,|,C,i,),的難度，可以做,類條件獨(dú)立的樸素假定,。給定樣本的類標(biāo)號(hào)，假定,屬性值相互條件獨(dú)立,，即在屬性間，不存在依賴關(guān)系。這樣,,,,,P(收入低,是學(xué)生, 信用良好|買電腦)=,,P(收入低|買電腦)*P(是學(xué)生|買電腦)*P(信用良好|買電腦),,2024/11/26,49,,樸素貝葉斯分類,(,續(xù),),,,其中概率,P,(,x,1,|,C,i,)，,P,(,x,2,|,C,i,)，……，,P,(,x,n,|,C,i,),可以由訓(xùn)練樣本估值。,,如果,A,k,是離散屬性，則,P,(,x,k,|,C,i,)=,s,ik,|,s,i,，,其中,s,ik,是在屬性,A,k,上具有值,x,k,的類,C,i,的訓(xùn)練樣本數(shù)，而,s,i,是,C,i,中的訓(xùn)練樣本數(shù)。,,,如果,A,k,是連續(xù)值屬性，則通常假定該屬性服從高斯分布。因而，,,,,,,是高斯分布函數(shù)， 而分別為平均值和標(biāo)準(zhǔn)差。,,,,,2024/11/26,50,,樸素貝葉斯分類(續(xù)),,例題：計(jì)算,,P(收入低|不買電腦),,P(是學(xué)生|不買電腦),,P(信用良好|不買電腦),,,,,假設(shè) 收入，是否學(xué)生，信用狀況互相獨(dú)立，計(jì)算,,P(收入低，是學(xué)生，信用良好|不買電腦),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,51,,樸素貝葉斯分類,(,續(xù),),,對(duì)未知樣本,X,分類，也就是對(duì)每個(gè)類,C,i,，,計(jì)算,P(,X,|,C,i,)*P(,C,i,)。,樣本,X,被指派到類,C,i,，,當(dāng)且僅當(dāng),P(,C,i,|,X,)> P(,C,j,|,X,)，1≤,j,≤,m,，,j,≠,i,，,換言之，,X,被指派到其,P(,X,|,C,i,)*P(,C,i,),最大的類。,,,,,2024/11/26,52,,,樸素貝葉斯分類舉例,,數(shù)據(jù)樣本,有,屬性,年齡,，,收入,，,是否學(xué)生,和,信用狀況,。類標(biāo)號(hào)屬性,”,是否買電腦,“,有兩個(gè)不同值{,是,，,否,}。設(shè),C,1,對(duì)應(yīng)于類,”,買電腦,”,；,則,C,2,對(duì)應(yīng)于類,”不買電腦”,。,,,,我們希望分類的未知樣本為:,,X=（,”年齡,<=30”，,”收入=中,”，,”是學(xué)生,”，,”信用一般”,）,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,53,,,樸素貝葉斯分類舉例,,我們需要最大化P(X|C,i,)*P(C,i,)，i=1，2。,,每個(gè)類的先驗(yàn)概率,P(C,i,),可以根據(jù)訓(xùn)練樣本計(jì)算,：,,P(C,1,)=P(買電腦）=,,P(C,2,)=P(不買電腦）=,,,計(jì)算,P(X|Ci),,P（"年齡<=30","收入=中","是學(xué)生","信用一般"|買電腦),,,P（"年齡<=30","收入=中","是學(xué)生","信用一般"|不買電腦),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,54,,,樸素貝葉斯分類舉例,,P（"年齡<=30","收入=中","是學(xué)生","信用一般"|買電腦)=,,P（"年齡<=30"|買電腦)*,,P（"收入=中"|買電腦)*,,P（"是學(xué)生"|買電腦)*,,P（"信用一般"|買電腦),,,P（"年齡<=30","收入=中","是學(xué)生","信用一般"|,不,買電腦)=,,P（"年齡<=30"|不買電腦)*,,P（"收入=中"|不買電腦)*,,P（"是學(xué)生"|不買電腦)*,,P（"信用一般"|不買電腦),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,55,,,樸素貝葉斯分類舉例,,假設(shè)屬性之間獨(dú)立,,P（"年齡<=30","收入=中","是學(xué)生","信用一般"|買電腦)=0.222*0.444*0.667 *0.667=0.044；,,,P（"年齡<=30","收入=中","是學(xué)生","信用一般"|,不,買電腦)=0.600*0.400*0.200*,,0.400=0.019,；,,,P（,X,|買電腦)>P（X|不買電腦)，因此對(duì)于樣本X，樸素貝葉斯分類預(yù)測(cè)為",是,"。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,56,,第三章 分類方法,,,,,內(nèi)容提要,分類的基本概念與步驟,,基于距離的分類算法,,決策樹分類方法,,貝葉斯分類,,基于規(guī)則的分類,,,與分類有關(guān)的問(wèn)題,,2024/11/26,57,,使用IF-THEN規(guī)則分類,,使用規(guī)則的分類法是使用一組IF-THEN規(guī)則進(jìn)行分類。,,IF,條件,THEN,結(jié)論,,比如,IF,(年齡<20,AND,學(xué)生=是),THEN,買電腦=是,,IF的部分稱為前提，THEN的部分稱為規(guī)則的結(jié)論,,規(guī)則可以用它的,覆蓋率,和,準(zhǔn)確率,來(lái)評(píng)價(jià),,,,,,n,covers,是條件(前提)覆蓋的樣本數(shù)，n,correct,是規(guī)則正確分類的樣本數(shù)。,2024/11/26,58,,使用IF-THEN規(guī)則分類,,規(guī)則(收入=低),^(信用狀況良好),?(是否買電腦=是)的覆蓋率為3/8,而它測(cè)準(zhǔn)確率為1/3。,,,規(guī)則(信用狀況=良好)?(是否買電腦=否)的覆蓋率為7/8,而它測(cè)準(zhǔn)確率為4/7。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,59,,使用IF-THEN規(guī)則分類,,如果一個(gè)規(guī)則R被一個(gè)樣本X滿足，則稱規(guī)則R被X觸發(fā)。,,比如X =(年齡=18，是學(xué)生，信用良好),,R為,IF,(年齡<20,AND,學(xué)生=是),THEN,買電腦=是,,則X的類別為,買電腦,,如果一個(gè)樣本X同時(shí)觸發(fā)了多個(gè)規(guī)則，我們需要制定解決沖突的策略。,,規(guī)模序,激活具有最多屬性測(cè)試的觸發(fā)規(guī)則,,規(guī)則序,將規(guī)則按重要性進(jìn)行排序，按順序進(jìn)行促發(fā),,如果一個(gè)樣本X無(wú)法促發(fā)任何規(guī)則,,建立一個(gè)缺省或者默認(rèn)規(guī)則,,2024/11/26,60,,使用決策樹來(lái)提取規(guī)則,,決策樹的規(guī)則是互斥與窮舉的,,互斥,意味著規(guī)則不會(huì)存在沖突，因此每個(gè)樣本只能促發(fā)一個(gè)規(guī)則,,窮舉,意味著一個(gè)樣本總能促發(fā)一個(gè)規(guī)則,,由于每個(gè)樹葉對(duì)應(yīng)一個(gè)一條規(guī)則，提取的規(guī)則并不比決策樹簡(jiǎn)單。,年齡？,信用狀況？,收入？,是,<=30,30—40,>40,否,是,是,否,良好,一般,高,低,2024/11/26,61,,使用順序覆蓋算法的規(guī)則歸納,,在提取規(guī)則時(shí)，一個(gè)現(xiàn)實(shí)的問(wèn)題是是否需要對(duì)現(xiàn)有規(guī)則進(jìn)行拓展，,,IF (年齡<20) THEN買電腦,是否需要拓展為,IF (年齡<20 AND 學(xué)生=是) THEN買電腦,,衡量規(guī)則好壞應(yīng)同時(shí)考慮覆蓋度與準(zhǔn)確率,,,,,,,,,準(zhǔn)確率太低 覆蓋度太低,2024/11/26,62,,使用順序覆蓋算法的規(guī)則歸納,,有兩種衡量規(guī)則好壞的度量,,FOIL_Gain的定義如下,,,,分別對(duì)應(yīng)于兩個(gè)規(guī)則R與R'。正在學(xué)習(xí)的類稱為正樣本(pos)，而其他類稱為負(fù)樣本(neg), pos(neg)為規(guī)則R覆蓋的正負(fù)樣本，而pos'(neg')為規(guī)則R'覆蓋的正負(fù)樣本。,2024/11/26,63,,判斷規(guī)則,(收入=低),?(是否買電腦=否),,是否需要拓展為,,規(guī)則,(收入=低),^(信用狀況=良好),?(是否買電腦=否),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,64,,使用順序覆蓋算法的規(guī)則歸納,,似然率統(tǒng)計(jì)量的的定義如下,,,,,其中m是分類的類別數(shù)。fi為滿足規(guī)則的樣本中屬于類i的概率，ei為屬于類i的期望(基準(zhǔn))概率。,,似然率越高，說(shuō)明規(guī)則越理想。,2024/11/26,65,,分別計(jì)算規(guī)則,(收入=低),?(是否買電腦=否),,與規(guī)則,,(收入=低),^(信用狀況=良好),?(是否買電腦=否),,的似然率。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,66,,順序覆蓋算法,,,,,,,,,,,終止條件包括，類c沒有樣本或者返回的規(guī)則質(zhì)量低于用戶指定的閾值等。,輸入：D，類標(biāo)記已知的樣本的集合。,,Att_vals,所有屬性與它們可能值得集合。,,輸出：IF-THEN規(guī)則的集合。,,（,1,）Rule_set={}；,//,規(guī)則的初始集為空集,,（,2,）,FOR,每個(gè)類 c DO,,,（,3,） repeat,,（4） Rule=Learn_One_Rule(D,Att_vals,c);,,（5） 從D中刪除Rule覆蓋的樣本；,,（6） untile 終止條件滿足；,,（7） Rule_set=Rule_set+Rule; //將新規(guī)則添加到規(guī)則集,,（8）END FOR,,（9）返回Rule_Set,2024/11/26,67,,使用順序覆蓋算法的規(guī)則歸納,,Rule_set={}；,,選擇一個(gè)類“買電腦”；,,選擇一個(gè),包含一個(gè)屬性,的規(guī)則,,(收入=低),?,“,買電腦,”,,分別計(jì)算,其它包含一個(gè)屬性的規(guī)則,的相對(duì)于已選擇規(guī)則的,FOIL_Gain,,(收入=高,)?,“,買電腦,”,,(學(xué)生=是),?,“,買電腦,”,,(學(xué)生=否),?,“,買電腦,”,,(信用=良好),?,“,買電腦,”,,(信用=一般),?,“,買電腦,”,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,68,,使用順序覆蓋算法的規(guī)則歸納,,分別計(jì)算規(guī)則的Foil_gain,,(收入=高),?"買電腦"為1.74,,(學(xué)生=是),?"買電腦"為0,,(學(xué)生=否),?"買電腦"為0,,(信用=良好),?"買電腦"為0,,(信用=一般),?"買電腦"為0,,,選擇Foil_gain最高的規(guī)則,,(收入=高),?"買電腦",,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,69,,使用順序覆蓋算法的規(guī)則歸納,,對(duì)最好的規(guī)則R進(jìn)行拓展,,(收入=高),?"買電腦",,在規(guī)則R中添加一個(gè)屬性，得到拓展以后的規(guī)則R',,(收入=高),^(學(xué)生=是),,(收入=高)^(學(xué)生=否),,(收入=高)^(信用=良好),,(收入=高)^(信用=一般),,分別計(jì)算這些規(guī)則的相對(duì)于R的Foil_gain,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,70,,使用順序覆蓋算法的規(guī)則歸納,,分別計(jì)算規(guī)則的Foil_gain,,(收入=高),^(學(xué)生=是) 為0.84,,(收入=高)^(學(xué)生=否) 為-1.16,,(收入=高)^(信用=良好) 為0.84,,(收入=高)^(信用=一般) 為-1.16,,,選擇Foil_gain最高的規(guī)則,,(收入=高),^(學(xué)生=是),,,(收入=高)^(信用=良好),,,由于這兩個(gè)規(guī)則準(zhǔn)確率已經(jīng)是100%，因此不用拓展,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,71,,使用順序覆蓋算法的規(guī)則歸納,,將規(guī)則覆蓋的樣本從數(shù)據(jù)集D中刪除，對(duì)剩下的正樣本生成規(guī)則,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,72,,使用順序覆蓋算法的規(guī)則歸納,,,,,,,,,,,,,,,,,,,,,,選擇,另外一個(gè)類,“不買電腦” (生成其它類的規(guī)則)；,,選擇一個(gè)包含一個(gè)屬性的規(guī)則,,(收入=低),?,“,不買電腦,”,,分別計(jì)算其它包含一個(gè)屬性的規(guī)則,的相對(duì)于已選擇規(guī)則的,FOIL_Gain,,(收入=高,)?,“,不買電腦,”,,(學(xué)生=是),?,“,不買電腦,”,,(學(xué)生=否),?,“,不買電腦,”,,(信用=良好),?,“,不買電腦,”,,(信用=一般),?,“,不買電腦,”,2024/11/26,73,,第三章 分類方法,,,,,內(nèi)容提要,分類的基本概念與步驟,,基于距離的分類算法,,決策樹分類方法,,貝葉斯分類,,基于規(guī)則的分類,,實(shí)值預(yù)測(cè),,,,2024/11/26,74,,實(shí)值預(yù)測(cè),,,,分類：把樣本分配到若干類之一(,離散的,)。,,比如預(yù)測(cè)是普通員工、中層管理還是高級(jí)管理人員,,,預(yù)測(cè)：預(yù)測(cè)樣本的某個(gè)屬性值(,連續(xù)的,)。,,比如預(yù)測(cè)收入,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,75,,實(shí)值預(yù)測(cè),,實(shí)值預(yù)測(cè)方法有兩種,,線性回歸,和多元回歸,,非線性回歸,,,2024/11/26,76,,實(shí)值預(yù)測(cè),,在回歸分析中，只包括一個(gè)自變量和一個(gè)因變量，且二者的關(guān)系可用一條直線近似表示，這種回歸分析稱為,一元線性回歸分析,。,,x={2,4,5,7,9}; y={6,10,12,16,20};,,,如果回歸分析中包括兩個(gè)或兩個(gè)以上的自變量，且因變量和自變量之間是線性關(guān)系，則稱為,多元線性回歸分析,。,,x={(2,4),(4,0),(5,6),(7,1),(9,-3)}; y={10,4,17,9,3};,2024/11/26,77,,一元,線性回歸模型,,給,n,個(gè)隨機(jī)樣本(Y,i,,X,i,,)，則Y與X的線性回歸模型可以寫為,,,,,,其中,,b,0,,，b,1,是參數(shù),,?,是被稱為,誤差,項(xiàng)的隨機(jī)變量,這是由于我們建立的線性回歸模型可能是不完美的,,,,,,,,,,,,,,,,,,,2024/11/26,78,,線性回歸模型,的求解,,回歸模型的求解相當(dāng)于求解β 使得,,,,,一元線性回歸分析的求解,,,,,,,,2024/11/26,79,,一元,線性回歸模型,,例題：請(qǐng)建立右表的線性回歸模型。,,,,,,,,,,,,,,,,,,,2024/11/26,80,,多元線性回歸模型,,給,n,個(gè)隨機(jī)樣本(Y,i,,X,i1,,X,i2,,...,X,ip,)，則Y與X的線性回歸模型可以寫為,,,,,,其中,,b,0,,，b,1,，b,2,，?，b,n,是參數(shù),,?,是被稱為,誤差,項(xiàng)的隨機(jī)變量,這是由于我們建立的線性回歸模型可能是不完美的,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/11/26,81,,線性回歸模型,的求解,,回歸模型的求解相當(dāng)于求解β 使得,,,,,多元線性回歸分析的求解,,,,其中X為,,,,,,,,2024/11/26,82,,AQ,算法,,多元回歸模型的求解在許多軟件中都可以得到，比如Matlab，SAS，SPSS，Weka等。,,2024/11/26,83,,AQR,算法有關(guān)定義,,AQR,為每一個(gè)分類推導(dǎo)出一條規(guī)則，每一條規(guī)則形式如下：,if then predict ,。,,在一個(gè)屬性上的基本測(cè)試被稱為一個(gè),Selector,。下面是一些,Selector,的例子：,,或,60>,。,,AQR,允許測(cè)試做,{=,，,≤,，,≥,，,≠},。,Selectors,的合取被稱為復(fù)合（,Complex,），,Complexes,之間的析取被稱為覆蓋（,Cover,）。如果一個(gè)表達(dá)式對(duì)某個(gè)樣本為真，則我們稱其為對(duì)這個(gè)樣本的一個(gè)覆蓋。這樣，一個(gè)空,Complex,覆蓋所有的樣本，而一個(gè)空,Cover,不覆蓋任何樣本。,,在,AQR,中，一個(gè)新樣本被區(qū)分是看其屬于哪個(gè)推導(dǎo)出來(lái)的規(guī)則。如果該樣本只滿足一條規(guī)則，則這個(gè)樣本就屬于這條規(guī)則；如果該樣本滿足多條規(guī)則，則被這些規(guī)則所預(yù)測(cè)的最頻繁的分類被賦予這條規(guī)則；如果該樣本不屬于任何規(guī)則，則其分類為樣本集中最頻繁的分類。,,2024/11/26,84,,,AQR,算法描述,,,,,,,,算法,4-5 AQR,,輸入：正例樣本,POS,；,,反例樣本,NEG,。,,輸出：覆蓋,COVER,。,,（,1,）,COVER= Φ,；,//,初始化,COVER,為空集,Φ,,（,2,）,WHILE COVER does not cover all positive examples in POS DO BEGIN,,（,3,）,Select a SEED,；,/,選取一個(gè)種子,SEED,，例如沒有被,COVER,覆蓋的一個(gè)正樣例,,（,4,）,Call procedure STAR,（,SEED,，,NEG,）；,//,產(chǎn)生一個(gè)能覆蓋種子而同時(shí)排除所有反例的星,,（,5,）,Select the best Complex BEST from the STAR according to user-defined criteria,；,,/*,從星中選取一個(gè)最好的復(fù)合*,/,,（,6,）,Add BEST as an extra disjuct to COVER /*,把最好的復(fù)合與,COVER,合取，形成新的,COVER*/,,（,7,）,END,,（,8,）,RETURN COVER.,,,在算法,AQR,中調(diào)用了過(guò)程,STAR,，來(lái)排除所有的反例，產(chǎn)生覆蓋種子的星。,2024/11/26,85,,,AQR,算法描述,(,續(xù),),,,,,,,,算法,4-6,,STAR,,輸入：種子,SEED,；反例,NEG,。,,輸出：星,STAR,。,,（,1,）初始化,STAR,為空,Complex,,（,2,）,WHILE one or more Complexes in STAR covers some negative examples in NEG BEGIN /*,如果,STAR,中的一個(gè)或多個(gè),Complex,覆蓋,NEG,中的負(fù)樣例*,/,,（,3,）,Select a negative example Eneg covered by a Complex in STAR,；,/*,選取一個(gè)被,STAR,中的,Complex,覆蓋的負(fù)樣例*,/,,（,4,）,Let EXTENSION be all Selectors that cover SEED but not ENEG,；,/*,令,EXTENSION,為那些覆蓋,SEED,但不覆蓋,ENEG,的,Selectors,；*,/,,（,5,）,Let STAR be the set {x∧y|x∈STAR,，,y∈EXTENSION},；,,/*,令,STAR= {x∧y|x∈STAR,，,y∈EXTENSION},；*,/,,（,6,）,Remove all Complexes in STAR subsumed by other Complexes in STAR,；,/*,從,STAR,中除去被其他,Complexes,所包含的,Complexes,；*,/,,（,7,）,Remove the worst Complexes from STAR UNTIL size of STAR is less than or equal to user-defined maximum,（,maxstar,）,/*,刪除,STAR,中最壞的,Complex,直到,STAR,的大小等于或小于用戶定義的最大數(shù)目,maxstar*/,,（,8,）,END,,（,9,）,RETURN STAR. /*,返回一系列覆蓋,SEED,但不覆蓋,NEG,的規(guī)則*,/,2024/11/26,86,,,AQR,算法舉例,,,,,,,,,,,假設(shè)現(xiàn)有一個(gè)訓(xùn)練集，其包含兩種屬性：,,size,（屬性值：,micro,，,tiny,，,mid,，,big,，,huge,，,vast,）,,type,（屬性值：,bicycl