1、數據倉庫算法總結事務處理環境不適宜DSS應用的原因：(1) 事務處理和分析處理的性能特性不同(2) 數據集成問題歷史數據問題(4)數據的綜合問題數據倉庫數據的四個基本特征：(1) 數據倉庫的數據是面向主題的(2) 數據倉庫的數據是集成的(3) 數據倉庫的數據是不可更新的(4) 數據倉庫的數據是隨時間不斷變化 數據倉庫定義：數據倉庫是在企業管理和決策中面向主題的、集成的、與時間相關的(時變的)、不可修改的(非易失的)數據集合，用于支持管理決策。支持度若D中的事務包含 A U包含A和和的元組二者)的百分比為s，則稱關聯規則 A B的支持度為 元組總數s。即：support (A 二 B)=P(A

2、U B)可信度/置信度若D中包含A的事務同時也包含 B的百分比為c ,則稱關聯規則 A= B的置信度/可信度為c。即： confidence(A二 B)=P(B|A) = support(A U B)/support(A)頻繁項集項集的出現頻率是包含項集的事物數，簡稱項集的頻率。項集滿足最小支持度閾值min sup :如果項集的出現頻率大于或等于min sup與D中事物總數的乘積。滿足最小支持閾值的項集就稱為頻繁項集(或大項集)。頻繁k項集的集合記為Lk。定理(Apriori性質)頻繁項集的所有非空子集都必須也是頻繁的。任何非頻繁項集的超級一定也是非頻繁的Apriori 算法具體做法：對于所研

3、究的事務數據庫D，首先找出頻繁1-項集的集合，記為 L1 ;再用L1找頻繁2-項集的集合L2 ;再用L2找L3如此下去，直到不能找到頻繁 k-項集為止。找 每個Lk需要一次數據庫掃描。如何實現用Lk-1找Lk.連接步：為找Lk，通過Lk-1與Lk-1連接產生候選k-項集的集合。該候選項集的集合記作Ck，執行Lk-1與Lk-1的連接：如果他們前（k-2）個項相同，則可連接。剪枝步：任何非頻繁的（k-1）項集都不可能是頻繁k-項集的子集。因此，進行剪枝。7TO項2的列表Tim11. 12. J5T20012, 14T30012. 13T40011, 12, 14T50011. 13T600J2.

4、13T70011T80011. 12. 13, 15T90011， 12, 13例1:該例基于某商店的事務 DB。DB中有9個事務, Apriori假定事務中的項按字典次序存放。（1）在算法的第一次迭代，每個項都是候選1-項集的集合C1的成員。算法簡單地掃描所有的事務，對每個項的出現次數計 數。掃描D對每個候選計數（2）設最小支持計數為 2,可以確定頻繁1-項集 的集合L1。它由具有最小支持度的候選1-項集組成。比較候選支持度計數與最小支持度計數（3）為發現頻繁2-項集的集合L2，算法使用LL1（4）掃描D中事務，計算C2中每個候選項集的支持計 數。掃描D,對每 個候選計數項集支持度計數612

5、7何622項集玄持度計敎f/v6何7622產生候支持度汁數4阿134E 14111,阿2 02.踏42/52 13f 140 113r 15114, 150（5 ）確定頻繁2-項集的集合C2中的候選2-項集組成。L2，它由具有最小支持度的比較候選支持度計數與最小支持度計數L _支持度計融mm4I1r 134I1r 152t2, 13492r 142I2r 152掃描D,對每 個候選計數項集支持度計數11 r 12, 132H, 12, 152（6）候選3-項集的集合C3的產生如下： 連接：C3 = L2 7 1-2=11,12，11,13 , 11,15 , 12,13 , 12,14 , 1

6、2,15X 11,12，11,13 , 11,15 , 12,13 , 12,14 , 12,15=11,213 ，11,12,15，11,13,15 , 12,13,14，12,13,15 , 12,14,15 利用Apriori性質剪枝：頻繁項集的所有子集必須是頻繁的。存在候選項集，判斷其子集是否頻繁。11,12,13的2-項子集是11,12 , 11,13和12,13,它們都是L2的元素。因此保留11,12,13。 11,12,15的2-項子集是11,12 , 11,15和12,15,它們都是L2的元素。因此保留11,12,15。11,13,15的2-項子集是11,13 , 11,15和

7、13,15,13,15不是L2的元素，因而不是頻繁的， 由 C3 中刪除11,13,15。12,13,14的2-項子集是12,13 , 12,14和13,14,其中13,14不是L2的元素，因而不是頻繁 的，由C3中刪除12,13,14。12,13,15的2-項子集是12,13 , 12,15和13,15,其中13,15不是L2的元素，因而不是頻繁 的，由C3中刪除12,13,15。12,14,15的2-項子集是12,14 , 12,15和14,15,其中14,15不是L2的元素，因而不是頻繁 的，由C3中刪除12,14,15。 這樣，剪枝后 C3 = 11,12,13，11,12,15。（7

8、） 掃描D中事務，以確定L3，它由具有最小支持度的C3中的候選3-項集組成。 由L2產生候選C38）算法使用L: L3產生候選4-項集的集合C4。盡管連接產生結果11,12,13,15,這個項集被剪去，因為它的子集 12,13,15不是頻繁的。則 C4 =空集,因此算法終止，找出了所有的頻繁項集。關聯規則的生成：根據上面介紹的關聯規則挖掘的兩個步驟，在得到了所有頻繁項目集后，可以按照下面的步驟生成關聯規則：對于每一個頻繁項目集I，生成其所有的非空子集；對于 I 的每一個非空子集 X，計算 Co nferen ce(X)，若 Con fide nce(X) mincon fide nee , 則

9、“ x= (I - X) ” 成立。由于規則由頻繁項集產生，每個規則都自動滿足最小支持度。例2:基于例1的結果，假定數據包含頻繁項集I =11 ,12 ,15。可以由I產生哪些關聯規則?T1DID列表T10011,12.15T200123T30012,13T40011,123T50011,13TBOO12,13T70011,13T800I1.I2AIST90011,1233如果最小置信度閾值為 70% , 這些是產生的強規則。L (L)的非空子集有11 , 12、11 , 15、I2 , 15、11、12 和15關聯規則如下：1112二 15,confidence = 2 4 = 50%111

10、5二 12,confidence 二 2 2 = 100%I2 15二 11,con fide nee = 2 2 二 100%11 = 12I5,confidence = 2 6 = 33%12二 11I5,con fide nee = 2 7 = 29%15二 11I2,confidence 二 2 2 = 100%2、3、6個規則可以作為最終的輸出，因為只有那么只有第序列關聯規則收集到的數據中常常存在某種順序關系，通常是基于時間的先后順序。對于識別動態系統的重要特征，或預測特定事件的未來發生，序列信息將是很有價 值的。對象時間戳事件A11 , 2 , 4A22 , 3A35B11 , 2

11、B22, 3 , 41C11 , 2 1C22, 3 , 4C32, 4 , 5D12D23 , 4D34 , 5每一行記錄與一個特定的對象相關聯的一些事件在 給定時刻的出現。時間戳不是一個具體的時間，而是一個象征性的時 間，表示時間上的先后次序。將與對象A有關的所有事件按時間戳增序排列就得 到對象 A的一個序列(sequenee)。數據序列(data sequenee)是指與單個數據對象相關 聯的事件的有序列表。如表中顯示的數據集包含四個數 據序列，對象 A , B, C , D各一個。設D是包含一個或多個數據序列的數據集序列s的支持度是包含s的所有數據序列所占的比例。如果序列s的支持度大于

12、或等于用戶給定的最小支持度閾值(minsup)，則稱s是一個頻繁序列。以前面給定的包含 4個數據序列的數據集為例，序列的支持度等于75%。假定minsup=50%，則至少出現在2個數據序列中的任何序列都是序列模式：minsup=50%序列模式的例子：s=75%，除 D 外s=75%，除 D 外序列合并規則序列S1和序列S2合并，僅當從S1中去掉第一個事件后得到的子序列與從S2中去掉最后一個事件后得到的子序列相同，結果候選是序列S1和序列S2的最后一個事件連接，S2的最后一個事件可以作為最后一個事件合并到S1的最后一個元素中，也可以作為一個不同的元素，這取決于如下條件：如果S2的最后兩個事件屬于

13、相同的元素，則 是S1的最后一個元素的一部分如果S2的最后兩個事件屬于不同的元素，則 成為連接到S1的尾部的單獨元素序列關聯算法的連接和剪枝步驟的例子(其中，每個 事件)S2的最后一個事件在合并后的序列中S2的最后一個事件在合并后的序列中是指一個元素，1，2， 3， 4， 5是指頻繁3序列產生候選4序列,候選4序列剪枝對于給定的序列s,t，形如s= t的表達式就是序列關聯規則。 序列關聯規則s= t的置信度是支持序列s和t的數據序列數與僅支持s的數據序列數之比。例如，= 的置信度為：s()/s()=1樣本數據序號屬性1屬性2111221312422543653744854例3計算簇平均值點，得

14、到新的平均值點為（1.5, 1.5)和(4.5, 3.5) o只憑支持度和可信度閾值未必總能找到符合實際的或有意義的規則，應該在關聯規則X=Y的置信度超過某個特定的度量標準時，定義它為有意義。在此引入Lift值（增益）Lift （X 二 Y）=P（Y|X）/P（Y）=P（X U Y）/P（X）*P（Y）Lift=1 ,前項和后項經驗獨立X與Y實際同時發生的概率大于X與Lift 1,表明前項和后項是正相關的，說明Y獨立時同時發生的隨機概率Lift1 ,表明前項和后項是負相關的基于劃分的聚類方法1、k-means算法（k-平均或k-均值） 首先將所有對象隨機分配到k個非空的簇中。 計算每個簇的平均

15、值，并用該平均值代表相應的簇。 根據每個對象與各個簇中心的距離，分配給最近的簇。 然后轉第二步，重新計算每個簇的平均值。這個過程不斷重復直到滿足某個準則函 數才停止。根據所給的數據通過對其實施k-means （設n=8, k=2），其主要執行步驟：第一次迭代：假定隨機選擇的兩個對象，如序號 1和序號3 當作初始點，分別找到離兩點最近的對象，并產生兩個簇 1 , 2和3 , 4, 5, 6, 7, 8。對于產生的簇分別計算平均值，得到平均值點。對于1 , 2，平均值點為（1.5, 1）;對于3 , 4, 5, 6, 7, 8，平均值點為（3.5, 3）。第二次迭代：通過平均值調整對象的所在的簇，

16、重新聚類，即將所有點按離平均值點（1.5, 1 ）、（ 3.5, 3）最近的原則重新 分配。得到兩個新的簇：1 , 2, 3, 4和5 , 6, 7, 8。重新第三次迭代：將所有點按離平均值點（1.5, 1.5）和（4.5, 3.5）最近的原則重新分配，調整對象，簇仍然為1 , 2, 3, 4和5 , 6, 7 8，發現沒有出現重新分配，而且準則函數收斂，程序結束。迭代次數平均值平均值產生的新簇新平均值新平均值(簇1)(簇2)(簇1)(簇2)1(1, 1)(1 , 2)1 , 2 , 3 , 4, 5 , 6 , 7 , 8(1.5 , 1)(3.5 , 3)2(1.5, 1)(3.5, 3)

17、1 , 2 , 3 , 4, 5, 6 , 7 , 8(1.5 , 1.5)(4.5 , 3.5)3(1.5, 1.5)(4.5, 3.5)1 , 2 , 3 , 4, 5, 6 , 7 , 8(1.5 , 1.5)(4.5 , 3.5)請思考：4和7,結果與前面會一樣嗎？有何對于相同的樣本數據，若隨機選擇的兩個初始點為序號 結論？2、K-中心點算法1為每個簇隨機選擇一個代表對象 (中心點)；2剩余的對象根據其與代表對象的距離分配給與其最近的一個簇；3反復地用非代表對象來替換代表對象，以提高聚類的質量，直至找到最合適的中心點。例4假如空間中的五個點 A、E、C、D、E如圖1所示，各點之間的距離

18、關系如表 1所示, 根據所給的數據對其運行 PAM算法實現劃分聚類(設 k=2 )。樣本點間距離如下表所示：第一步 建立階段：假如從5個對象中隨機抽取的 2個中心點為A , B,則樣本被劃分為A、 C、D和B、E。第二步交換階段：假定中心點 A、B分別被非中心點C、D、E替換，根據PAM算法需要計算下列代價 TCAC、TCAD、 TCAE、TCBC、TCBD、TCBE。以TCAC為例說明計算過程：a) 當A被C替換以后，A不再是一個中心點，因為 A離B比A離C近，A被分配到B中 心點代表的簇，CAAC=d(A,B)-d(A,A)=1 。b) B是一個中心點，當 A被C替換以后，B不受影響，CB

19、AC=0。c) C原先屬于A中心點所在的簇，當A被C替換以后，C是新中心點，符合PAM算法代價 函數的第二種情況 CCAC=d(C,C)-d(C,A)=0-2=-2 。d) D原先屬于A中心點所在的簇，當A被C替換以后，離D最近的中心點是 C,根據PAM算法代價函數的第二種情況CDAC=d(D,C)-d(D,A)=1-2=-1 。e) E原先屬于B中心點所在的簇，當A被C替換以后，離E最近的中心仍然是B,根據PAM算法代價函數的第三種情況CEAC=0。因此，TCAC=CAAC+ CBAC+ CBAC+ CDAC+ CEAC=1+0-2-1+0=-2。請計算代價 TCAD、 TCAE、TCBC、

20、TCBD、TCBE。在上述代價計算完畢后，選取一個最小的代價，顯然有多種替換可以選擇，選擇第一個最小代價的替換(也就是 C替換A),根據圖(a)所示，樣本點被劃分為 B、A、E和C、D 兩個簇。圖(b)和圖(c)分別表示了 D替換A , E替換A的情況和相應的代價(b) D 替換 A, TCAD= -2 圖替換中心點A圖(a)、(b)、(c)分別表示了用 C、D、E替換B的情況和相應的代價。(a) C 替換 B, TCBC=-2(b) D 替換 B, TCBD= -2(c) E 替換 B, TCBE= -2圖替換中心點B通過上述計算，已經完成了A、D、E替換中心點B、 不再減小為止。PAM算法

21、的第一次迭代。在下一迭代中，將用其他的非中心點 C，找出具有最小代價的替換。一直重復上述過程，直到代價層次聚類方法1、AGNES 算法例5將下列數據聚為兩個簇第1步：根據初始簇計算每個簇之間的距離，隨機找出距離最小的兩個簇，進行合并，最小距離為1，合并后1，2點合并為一個簇。第2步：對上一次合并后的簇計算簇間距離，找出距離最近的兩個簇進行合并，合并后3，4點成為一簇。第3步：重復第2步的工作，5，6點成為一簇。第4步：重復第2步的工作，7，8點成為一簇。第5步：合并1，2，3，4成為一個包含四個點的簇。第6步：合并5，6 ,7,8，由于合并后簇的數目達到了用戶輸入的終止條件，程序結束。序號屬性

22、1屬性2111步驟最近的簇距離最近的兩個簇合并后的新簇212111 ， 21，2，3，4，5，6，7，8321213，41，2，3，4，5，6，7，8422315，61，2，3，4，5，6，7，8534417 ， 81，2，3，4，5，6，7，8635511，2，3，41，2, 3，4，5，6，7，8744615，6，7，81，2, 3，4，5，6，7，8結束8452、DIANA算法（典型的分裂聚類方法） 兩種測度方法：簇的直徑：在一個簇中的任意兩個數據點的距離中的最大值。 平均相異度（平均距離）：davg(G,Cj)二例6yCjx y序號屬性1屬性2111212321422534635744

23、845將下列數據聚為兩個簇第i步，找到具有最大直徑的簇，對簇中的每個點計算平均相異 度（假定采用是歐式距離）。1 的平均距離：（1 + 1 + 1.414+3.6+4.24+4.47+5）/7=2.96類似地：2的平均距離為 2.526 ；3 的平均距離為2.68 ；4的平均距離為 2.18 ；5的平均距離為 2.18 ；6的平均距離為2.68 ；7 的平均距離為2.526 ； 8的平均距離為2.96。挑出平均相異度最大的點1放到splinter group中，剩余點在 oldparty 中。第2步，在old party里找出到最近的splinter group中的點的距離不大于到old pa

24、rty中最近的點的距離的點，將該點放入splinter group中，該點是2。第3步，重復第2步，splinter group中放入點3。第4步，重復第2步，splinter group中放入點4。第5步，沒有在old party中的點放入了 splinter group中且達到終止條件（k=2），程序終止。如果沒有到終止條件，應該從分裂好的簇中選一個直徑最大的簇繼續分裂。步驟具有最大直;徑的簇splintergroupOldparty11，2,3,4,5,6,7,812 ,3,4,5,6, 7, 821，2,3,4,5,6,7,81 , 23 ,4,5,6,7, 831，2,3,4,5,6

25、,7,81 , 2,34 ,5,6,7,841，2,3,4,5,6,7,81 , 2,3,45 ,6,7,851，2,3,4,5,6,7,81 , 2,3,45 ,6,7,8終止3、BIRCH (1996)4、CURE算法密度聚類1、DBSCAN對于一個類中的每個對象，在其給定半徑的領域中包含的對象不能少于某一給定的最小數目 定義1對象的 -臨域（EpS近鄰）：給定對象在半徑內的區域。定義2核心對象：如果一個對象的-臨域至少包含最小數目 MinPts個對象，則稱該對象為核心對象。例如，在圖中， =1cm, MinPts=5 , q是一個核心對象。定義3直接密度可達：給定一個對象集合D，如果p是

26、在q的 -鄰域內，而q是一個核心對象，我們說對象p從對象q出發是直接密度可達的。例如，在圖中, =1cm, MinPts=5 , q是一個核心對象，對象p從對象q出發是直接密度可達的。圖直接密度可達圖密度可達定義4密度可達的：如果存在一個對象鏈圖密度相連圖噪聲p1,p2,，pn, p1=q , pn=p,對 pi D,( 1=i=n ),pi+1是從pi關于和MitPts直接密度可達的，則對象p是從對象q關于和MinPts密度可 達的。例如，在圖中， =1cm , MinPts=5 , q是一個核心對象，pl是從q關于和MitPts直接 密度可達，p是從pl關于和MitPts直接密度可達，則對

27、象p從對象q關于和Min Pts密 度可達的 （間接密度可達）。定義5密度相連的：如果對象集合D中存在一個對象0,使得對象p和q是從o關于和MinPts密度可達的，那么對象p和q是關于和MinPts密度相連的。定義6噪聲：一個基于密度的簇是基于密度可達性的最大的密度相連對象的集合。不包含 在任何簇中的對象被認為是“噪聲”。F面給出一個樣本事務數據庫（見左表），對它實施DBSCAN算法。根據所給的數據通過對其進行MinPts=4 )DBSCAN算法，以下為算法的步驟（設n=12,用戶輸入 =1 ,樣本事務數據庫DBSCAN算法執行過程示意歩驟選擇的點在屮點的個數通過計算可達點而找到的新簇112無

28、222無333445敷1： 1,薊4, 5f久他12553已在一個簇q中663無775簇q 2r 6( 7f11S2已在-個簇q中993已在一個簇q中101D4已在個議q中，11112已在一個簇C!中12122已崔個簇匸中聚出的類為1 , 3, 4, 5, 9, 10, 12 , 2 , 6,乙 8 , 11可達步驟選擇的點一 一一 - 在中點的個數222無33無n.75打3pfO.11*3中-IX C 個一在 已m63無_T87,A- IT 1 p2E2丄So14叵2中 個一在 已EH中1C 簇 個一在 已點。算法執行過程：第1步，在數據庫中選擇一點 1,由于在以它為圓心的，以 1 為半徑的

29、圓內包含 2個點（小于4）,因此它不是核心點，選 擇下一個點。第2步，在數據庫中選擇一點 2,由于在以它為圓心的，以 1 為半徑的圓內包含 2個點，因此它不是核心點，選擇下一個 點。第3步，在數據庫中選擇一點 3,由于在以它為圓心的，以 1 為半徑的圓內包含 3個點，因此它不是核心點，選擇下一個 點。第4步，在數據庫中選擇一點 4,由于在以它為圓心的，以 1 為半徑的圓內包含 5個點，因此它是核心點，尋找從它出發 可達的點（直接可達 4個，間接可達2個），聚出的新類1， 3，4，5，9，10，12，選擇下一個點。第5步，在數據庫中選擇一點 5,已經在簇1中，選擇下一 個點。第6步，在數據庫中選

30、擇一點 6,由于在以它為圓心的，以 1 為半徑的圓內包含 3個點，因此它不是核心點，選擇下一個第7步，在數據庫中選擇一點7,由于在以它為圓心的，以 1為半徑的圓內包含 5個點，因2 , 6, 7, 8, 11，選擇下一個點。 中，選擇下一個點。中，選擇下一個點。1中，選擇下一個點。2中，選擇下一個點。8, 已經在簇29, 已經在簇110, 已經在簇11, 已經在簇第12步，選擇12點，已經在簇1此它是核心點，尋找從它出發可達的點，聚出的新類 第8步，在數據庫中選擇一點 第9步，在數據庫中選擇一點 第10步，在數據庫中選擇一點 第11步，在數據庫中選擇一點 中，由于這已經是最后一點所有點都已處理

31、，程序終止。網格聚類1、STING 算法是一種基于網格的多分辨率聚類技術，它將空間區域劃分為矩形單元。針對不同級別的分辨率，通常存在多個級別的矩形單元，這些單元形成了一個層次結構：高層的每個單元被劃分為多個低一層的單元。 高層單元的統計參數可以很容易的從底層單元的計算得到。這些參數包括屬性無關的參數 count、屬性相關的參數 m （平均值）、s（標準偏差）、min（最小值卜max（最 大值）以及該單元中屬性值遵循的分布類型。模型聚類K最近鄰居算法（KNN）通過計算每個訓練數據到待分類元組的距離，取和待分類元組距離最近的K個訓練數據，K個數據中哪個類別的訓練數據占多數，則待分類元組就屬于哪個類

32、別。“身高”用于計算距離，K=5，對Pat,女,1.6分類。姓名性別身高（米）類別Kristina女1.6矮Jim男2高Maggie女1.9中等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.95中等Kim女1.9中等Amy女1.8中等Wynette女1.75中等女,1.6、 Debbie,女,1.8 、 對第12到14個記錄，沒變化。1取前K=5個記錄：N=Kristina,女,1.6、 Jim,男,2、 Maggie,女,1.9、 Martha,女

33、,1.88和 Stephanie,女,1.7。2對第 6 個記錄 d=Bob,男,1.85，得到 N=Kristina,女,1.6、 Bob,男,1.85、 Maggie,女，1.9、 Martha, 女,1.88和 Stephanie,女,1.7。3. 對第 7 個記錄 d=Kathy,女,1.6，得到 N=Kristina, 女,1.6、 Bob,男,1.85、 Kathy,女，1.6、 Martha, 女,1.88和 Stephanie,女,1.7。4. 對第 8個記錄 d=Dave,男,1.7，得到 N=Kristina,女,1.6、 Bob,男,1.85 、 Kathy,女,1.6、

34、 Dave, 男,1.7和 Stephanie，女,1.7。對第9和10個記錄，沒變化。5，對第 11 個記錄 d=Debbie,女,1.8，得到 N=Kristiina, Kathy,女,1.6、 Dave,男,1.7和 Stephanie,女,1.7。6. 對第 15 個記錄 d=Wynette,女,1.75，得到 N=Kristina,女,1.6、Wynette,女,1.75、 Kathy,女,1.6、 Dave,男,1.7 和 Stephanie,女,1.7。7. 最后輸出元組是：Kristina,女,1.6、Kathy,女,1.6、Stephanie,女,1.7、Dave,男,1.7

35、和 Wynette,女,1.75。 其中，四個屬于矮個、一個屬于中等。最終KNN方法認為Pat為矮個。請問：若K=5，Pety，男,1.96的身高應該屬于那種類型?ID3算法生成決策樹信息增益信息增益是指劃分前后進行正確預測所需的信息量之差。即原始分割的熵與劃分以后各分割的熵累加得到的總熵之間的差。選擇屬性的方法：選擇具有最大信息增益（熵減少的程度最大）的屬性作為當前節點的測試 屬性信息增益的計算設S是有s個訓練樣本數據的集合，類標號屬性具有m個不同值，定義 m個不同類Ci（i=1,2，,m）, si是類Ci中的樣本數，則對一個給定的訓練樣本分類所需要的期望信息為：mI S1,S2,Sm -

36、八 pi log 2 Pi其中pi是任意樣本屬于 Ci的概率，可用si/s來估計設屬性A具有v個不同值a1,a2,av，則可用屬性 A將S劃分為v個子集S1,S2,Sv, Sj中包含的樣本在屬性 A上具有值aj。如果選擇A作為測試屬性，則這些子集對應于由包 含集合S的結點生長出來的分枝。設sij是子集Sj中類Ci的樣本數，則按照 A劃分成子集的熵為：v s 亠亠s .E(A) Y Igj,，Smj)j丄s其中 S!j Smjs為第j個子集的權，等于子集(A值為aj)中的樣本數除以 S中的樣本數。對于給定的子集Sj，它的信息I(s1j,s2j,smj)可用下式計算mI (sij , S2j ,

37、Smj )為 Pij log 2 ( P ij )i丄亠Pij =|S|是Sj中的樣本屬于類 Ci的概率由A劃分的信息增益為：Gain(A)=l(s1,s2,sm)-E(A)例8一個商場顧客數據庫(訓練樣本集合)ridifceincum.esludentcrwiilratingbuiv-cumpulcr30HighNuFairNo240MediumNoFairYes540Law?sFair畑640LowYes臼cd lentNo7LowYesExcdlettYes&30MediumNdFairNd940MediumYesFairYes1140MediumNoExcd kitNd樣本集合的類別屬

38、性為：“ buy_computer ”，該屬性有兩個不 同取值，即yes, no，因此就有兩 個不同的類別(m=2)。設C1對應 類 別yes, C2對應類別no。類別C1 包含9個樣本，類別 C2包含5個 樣本。為了計算每個屬性的信息增益，首先利用公式計算出所有(對一個給定樣本進行分類所需要) 的信息，具體計算過程如下：-logjlog2 = 0.94接著需要計算每個屬性的(信息)熵。假設先從屬性“age”開始，根據屬性“ age”每個取值在yes類別和no類別中的分布，就可以計算出每個分布所對應的信息。對于 agesi -2-3耳珀罔J = 0*971對于聘?孝0-4；jn=4甩=0HSn

39、） = O虻于 age40u;知二 3s5J =2口石陽）二 Q971然后利用公式計算出若根據屬性“ age對樣本集合進行劃分，所獲得對一個數據對象進行分類而需要的信息熵為：545E他e）二心屁）+亍（齡）+（知知）=0金4由此獲得利用屬性 “ age對樣本集合進行劃分所獲得的信息增益為：6加他0二I（5|尚卜（嘟）二0245類似可得Gain（income）=0.029，Gai n（stude nt）=0.151 ，Gain（credit_rating）=0.048。顯然選擇屬性“ age所獲得的信息 增益最大，因此被作為測試屬性用 于產生當前分支結點。這個新產生 的結點被標記為“ age；同

40、時根據 屬性“age的三個不同取值，產生 三個不同的分支，當前的樣本集合 被劃分為三個子集，如圖所示。in oo mestudentfnsdil_nilingtLklC1Itcreilic nilingdasBiniediumnofairyeslowyesfairyeslowye號no-mediumyesfairyesnwdiumnoexcellentnoC4.5算法信息增益比例：是在信息增益概念基礎上發展起來的，一個屬性的信息增益比例用下面的公式給出:GainRatio (A)二Gai n(A)SplitI (A)v其中 SplitI (A)八 Pjlog2(Pj)OutlookTemper

41、atureHumidityWindPlayTennisSunnyHot85falseNoSunnyHot90trueNoOvercastHot78falseYesRainMild96falseYesRainCool80falseYesRainCool70trueNoOvercastCool65trueYesSunnyMild95falseNoSunnyCool70falseYesRainMild80falseYesSunnyMild70trueYesOvercastMild90trueYesOvercastHot75falseYes樣本數據d 1(9,5)二 0.9403)計算每個屬性的 Ga

42、inRatio :假如以屬性A的值為基準對樣本進行分割的化，Splitl(A) 就是前面熵的概念。C4.5處理連續值的屬性：根據屬性的值，對數據集排序；用不同的閾值將數據集動態的進行劃分；當輸出改變時確定一個閾值；取兩個實際值中的中點作為一個閾值；取兩個劃分，所有樣本都在這兩個劃分中；得到所有可能的閾值、增益及增益比；在每一個屬性會變為取兩個取值，即小于閾值或大于等于閾值。簡單地說，針對屬性有連續數值的情況，則在訓練集中可以按升序方式排列。如果屬性A共有n種取值，則對每個取值vj (j=1 , 2, n),將所有的記錄進行劃分：一部分小于vj ;另一部分則大于或等于 vj。針對每個vj計算劃分

43、對應的增益比率，選擇增益率最大的 劃分來對屬性A進行離散化。1) 首先對Humidity進行屬性離散化，針對上面的訓練集合，通過檢測每個劃分而確定最好的 劃分在75處，則這個屬性的范 圍就變為(75)。2) 計算目標屬性PlayTennis分 類的期望信息：GainRatio (Outlook) = 0246 =0.156;1.577GainRatio (windy) =0.049;GainRatio (Temperature) =0.0248;GainRatio (Humidity) =0.04834) 選取最大的 Gain Ratio，根據Outlook的取值，得到三個分支。5) 再擴展各

44、分枝節點，得到最終的決策樹。 貝葉斯定理設X是類標號未知的數據樣本。設H為某種假定，如數據樣本X屬于某特定的類 C。對于分類問題，我們希望確定P(H|X)，即給定觀測數據樣本 X，假定H成立的概率。貝葉斯定理給出了如下計算P(H|X)的簡單有效的方法P(H |X)二P(X | H )P(H )P(H):是先驗概率，或稱 H的先驗概率。P(X):樣本數據被觀察的概率。P(X|H)代表假設H成立的情況下，觀察到X的概率。P(H|X)是后驗概率，或稱條件 X下H的后驗概率。后驗概率P(H|X)比先驗概率 P(H)基于更多的信息。P(H)是獨立于X的。樸素貝葉斯分類樸素貝葉斯分類就是假定一個屬性值對給

45、定類的影響獨立于其他屬性的值。這一假定稱作類條件獨立。做此假定是為了簡化所需計算，并在此意義下稱為“樸素的” 樸素貝葉斯分類的工作過程如下:(1) 每個數據樣本用一個n維特征向量X=x1,x2, ,xn表示，分別描述對 n個屬性A1 ,A2 ,An樣本的n個度量。(2) 假定有m個類C1, C2,，Cm，給定一個未知的數據樣本X (即沒有類標號)，分類器將預測X屬于具有最高后驗概率(條件 X下)的類。也就是說，樸素貝葉斯分類將未知則通常假定這些類是等概率的，即 的最大化(P(X|Ci)常被稱為給定 大似然假設)。否則，需要最大化的樣本分配給類 Ci ( K i wm)當且僅當P(Ci|X) P(Cj|X)，對任意的j=1 , 2,，m, j豐i。 這樣，最大化P(Ci|X)。其P(Ci|X)最大的類Ci稱為最大后驗假定。(3)根據貝葉斯定理：CiP(X|Ci)P(Ci)P(X)由于P(X)對于所有類為常數，只需要 P(X|Ci)*P(Ci)最大即可。如果 Ci類的先驗概率未知,P(C1)=P(C2)=- =P(Cm)，因此問題就轉換為對 P(X|Ci)Ci時數據X的似然度，而使 P(X|Ci)最大的假設Ci稱為最P(X|Ci)*P(Ci)。注意，類的先驗概率可以用 P(Ci)=si/s計算，其中si是類Ci中的訓練樣本數，而s是訓練