1、基本資料探勘技巧 Basic Data Mining Techniques Prepared by: Dr. Tsung-Nan Tsai,Chapter 3,Data mining-951,Contents,建立決策樹之演算法 有效率推論關(guān)聯(lián)法則的技巧 了解關(guān)聯(lián)法則之支持度與涵蓋度 K-means 演算法 了解如何運(yùn)用基因演算法完成監(jiān)督式學(xué)習(xí)與非監(jiān)督式分群 如何選擇資料探勘技巧以解決問題,Data mining-951,資料探勘技術(shù),資料探勘,監(jiān)督式學(xué)習(xí)模型,非監(jiān)督式學(xué)習(xí)模型,屬性選擇與資料轉(zhuǎn)化,分群,樹型結(jié)構(gòu),關(guān)聯(lián)模式,規(guī)則誘發(fā),決策樹 (類別型屬性),迴歸樹 (連續(xù)型屬性),C4.5/C

2、5 ID3,CART,CART,M5,CN2,ITRULE,Cubist,3.1 決策樹 (Decision Trees),Data mining-951,決策樹演算法,決策樹的建立只會(huì)使用資料集中最適屬性用以訓(xùn)練建立決策樹。 選擇資料子集訓(xùn)練樣本建立決策樹完全正確分類Yes Stop。 選擇資料子集訓(xùn)練樣本建立決策樹分類錯(cuò)誤加入新的樣本正確分類Yes Stop。,決策樹演算法,令 T 為訓(xùn)練資料的集合 於T集合中選擇一個(gè)最具區(qū)別能力的屬性. 利用最具區(qū)別能力屬性建立一個(gè)節(jié)點(diǎn)樹 自此節(jié)點(diǎn)開始建立子鏈結(jié)，每一個(gè)鏈結(jié)對(duì)上層所選取的屬性而言都代表一個(gè)唯一值。 應(yīng)用子鏈結(jié)的值以進(jìn)一步將範(fàn)例切割成子類別

3、。 對(duì)產(chǎn)生於step 3之子類別而言： 若子類別中範(fàn)例滿足先前定義的準(zhǔn)則，且剩餘屬性集合並不符合樹的路徑，則採(cǎi)用新的範(fàn)例以供建立新的分類。 若子類別無法滿足準(zhǔn)則且至少有一個(gè)屬性可用以切割路徑，則令 T 為目前子類別範(fàn)例集合並回到 step 2.,Data mining-951,決策樹演算法,選擇適當(dāng)代表屬性主要用以決定樹的大小，並減少樹的高度與節(jié)點(diǎn)數(shù)量。 C4.5演算法： 假設(shè)有n個(gè)可能結(jié)果，C4.5利用-log2(1/n)個(gè)位元來配置。For example: n=4, -log2(1/4)=2. 可能結(jié)果為 (00, 01, 10, 11) 。即兩個(gè)位元可單獨(dú)表示四個(gè)類別。若選擇屬性A，其

4、 -log2(1/2)=1 1個(gè)位元可表示兩個(gè)可能結(jié)果。 Lift(增益值) = 1 C4.5 獲益率 C4.5 應(yīng)用獲益率測(cè)量法決定一個(gè)最好的屬性選擇,Data mining-951,C4.5,Quinlan(1979)提出，以Shannon(1949)的資訊理論為依據(jù)。 若一事件有k種結(jié)果,對(duì)應(yīng)的機(jī)率為pi。則此事件發(fā)生後所得到的資訊量I(視為Entropy-增益率)為： I= -(p1 log2(p1)+ p2 log2(p2)+ pklog2(pk) Example 1: 設(shè) k=4 p1=0.25, p2=0.25, p3=0.25, p4=0.25 I=-(0.25 log2(0.

5、25) 4)=2 Example 2: 設(shè) k=2 p1=0, p2=0.5, p3=0, p4=0.5 I=-(0.5 log2(0.5) 2)=1 Example 3: 設(shè) k=1 p1=1, p2=0, p3=0, p4=0 I=-(1 log2(1)=0,Data mining-951,決策樹演算法比較表,(Categorical),(Categorical),(Continuous),Data mining-951,範(fàn)例,Data mining-951,最高節(jié)點(diǎn),輸出: 壽險(xiǎn)促銷,精確度: 11/15=0.73 分?jǐn)?shù)=0.73/4=0.183,Data mining-951,See

6、page.72,精確度: 9/15=0.6 分?jǐn)?shù)=0.6/2=0.3,Data mining-951,精確度: 12/15=0.8 分?jǐn)?shù)=0.8/2=0.4,最佳節(jié)點(diǎn),信用卡促銷資料庫(kù),Data mining-951,C4.5,Data mining-951,C4.5,Data mining-951,ID3,Data mining-951,ID3,Data mining-951,信用卡促銷,Data mining-951,信用卡促銷,Data mining-951,信用卡促銷,A Rule for the Tree in Figure 3.4,Data mining-951,其他建立決策樹方法

7、,CART:為數(shù)個(gè)商業(yè)產(chǎn)品應(yīng)用. 迴歸樹採(cǎi)行決策樹形式。 CART與C4.5差別： CART 採(cǎi)行二元分裂(數(shù)值與類別皆可) CART利用測(cè)試資料以幫助刪除並歸納一顆二元樹。 CHAID: 建立於SAS與SPSS中。限制只從事類別型屬性值。,決策樹優(yōu)點(diǎn),容易了解。 將關(guān)係映射成一些生產(chǎn)法則。 可應(yīng)用於實(shí)務(wù)問題上。 資料探勘過程勿須預(yù)先假設(shè)。 可處理類別型資料。,決策樹缺點(diǎn),輸出屬性需為類別型. 只允許一個(gè)輸出屬性. 決策樹不穩(wěn)定. 若自數(shù)值型資料產(chǎn)生決策樹之過程可能非常複雜.,3.2 產(chǎn)生關(guān)聯(lián)法則,Data mining-951,親和力分析,親和力分析(affinity analysis) ：

8、決定事物結(jié)合一起與否的一般化過程。 購(gòu)物籃分析：決定顧客可能一起購(gòu)買的物項(xiàng)。 輸出為有關(guān)顧客購(gòu)買行為的關(guān)聯(lián)集合。 關(guān)聯(lián)法則允許多個(gè)輸出屬性 Example: 買牛奶也會(huì)買麵包 買麵包以會(huì)買牛奶 買牛奶/蛋 也會(huì)買 起司麵包,Data mining-951,信賴度與支撐度,法則“If A then B”, 其信賴度為條件機(jī)率，當(dāng)A為真而B亦為真之條件機(jī)率。 Example: 假設(shè)共有10,000筆購(gòu)買牛奶與麵包紀(jì)錄，買牛奶又同時(shí)買麵包有5000筆，則其信賴度為5000/10000=50%。 支撐(持)度：The minimum percentage of instances in the dat

9、abase that contain all items listed in a given association rule. 在交易中所佔(zhàn)比率。符合一條關(guān)聯(lián)法則所包含資料庫(kù)中最小範(fàn)例百分比。,探勘關(guān)聯(lián)法則例子,Data mining-951,關(guān)聯(lián)法則例子,Apriori演算法: 推論出項(xiàng)目集合(item set) 。項(xiàng)目及合為屬性-數(shù)值所組成。推論過程中若項(xiàng)目集合符合收斂準(zhǔn)則，則被捨棄。 Apriori 推論步驟： 集合項(xiàng)目推論 使用推論出的集合項(xiàng)目產(chǎn)出關(guān)聯(lián)法則 利用表3.3進(jìn)行推論，(已去除收入範(fàn)圍與年齡),Data mining-951,關(guān)聯(lián)法則例子,第1步驟設(shè)定4個(gè)項(xiàng)目屬性值所需最小

10、信賴度(3) 。,7Y/3N,Data mining-951,關(guān)聯(lián)法則例子,Data mining-951,關(guān)聯(lián)法則例子,Data mining-951,二個(gè)項(xiàng)目集合規(guī)則,三個(gè)項(xiàng)目集合表: 雜誌促銷=是 且 手錶促銷=否 且 壽險(xiǎn)促銷=否 (只有一筆, 故不加入) 手錶促銷=否 且 壽險(xiǎn)促銷=否 且 信用卡=否 (無),總共7筆為雜誌促銷=是 其中5筆雜誌促銷與壽險(xiǎn)促銷=是,See page. 83 and 84,Data mining-951,三個(gè)項(xiàng)目集合規(guī)則,第3步驟: 利用二個(gè)項(xiàng)目集合表中屬性質(zhì)推論三個(gè)項(xiàng)目集合。,1,手錶促銷=否 且 壽險(xiǎn)促銷=否 且 信用卡保險(xiǎn)=否 (符合門檻值 3)

11、,Data mining-951,三個(gè)項(xiàng)目集合規(guī)則,Data mining-951,一般考量,We are interested in association rules that show a lift in product sales where the lift is the result of the products association with one or more other products. 吾輩只對(duì)具有高度增益值之關(guān)聯(lián)規(guī)則產(chǎn)生興趣, 其增益值說明一個(gè)或以上產(chǎn)品之產(chǎn)品銷售量關(guān)連。 We are also interested in association rules t

12、hat show a lower than expected confidence for a particular association. 吾亦對(duì)關(guān)聯(lián)規(guī)則之特定關(guān)聯(lián)信賴度低於預(yù)期信賴度。(代表品項(xiàng)間相互競(jìng)爭(zhēng)或互補(bǔ)效應(yīng)),Data mining-951,3.3 k-means 演算法,Choose a value for K(總分群數(shù)) the total number of clusters. Randomly choose K points (資料點(diǎn)) as cluster centers (群組中心). 最初群組中心 Assign the remaining instances to

13、their closest cluster center.利用歐幾得距離分配剩餘的資料點(diǎn) Calculate a new cluster center for each cluster. 計(jì)算各群集新的平均點(diǎn)(群組中心) Repeat steps 3-5 until the cluster centers do not change.(重複3-5步驟直到群組中心未改變),Data mining-951,K-means 範(fàn)例,包含兩個(gè)屬性例子說明之。 屬性x與y，硬設(shè)置x-y座標(biāo)系統(tǒng)，映射圖如圖3.6所示。,Data mining-951,K-means 範(fàn)例 (圖3.6),C2,C1,Data

14、 mining-951,K-means 範(fàn)例,步驟1: 選擇一個(gè)K=2，隨機(jī)選擇2個(gè)點(diǎn)表示最初群集中心。 假設(shè)範(fàn)例1, 3為兩個(gè)群集中心。,(1-1)2+1.5-1.5)20.5=0,(2-1)2+1.5-1.5)20.5=1,(1-1)2+1.5-4.5)20.5=3,(2-1)2+1.5-4.5)20.5=3.16,Data mining-951,K-means 範(fàn)例,C1包含範(fàn)例1 and 2. C2包含3, 4, 5, 6. 再計(jì)算各個(gè)群集中心。 C1: x=(1.0+1.0)/2 = 1.0 y=(1.5+4.5)/2 = 3.0 C2: x=(2.0+2.0+3.0+5.0)/4=

15、3.0 y=(1.5+3.5+2.5+6.0)/4=3.375 新的群集中心 C1=(1.0, 3.0) and C2=(3.0, 3.375) 重複第二步驟。See page. 89,Data mining-951,K-means 範(fàn)例,Data mining-951,K-means 範(fàn)例,Data mining-951,K-means 範(fàn)例 - Tanagra,Data mining-951,K-means之一般考量,無法得到最佳解 需要數(shù)值型資料. 吾輩必須設(shè)定群集數(shù). 只有群集大小接近時(shí)方可得到最佳分群績(jī)效. 無法保證哪一個(gè)屬性之重要性較高. 缺乏解釋能力.,Data mining-9

16、51,3.4 基因演算法 (Genetic algorithm),基因演算法乃應(yīng)用進(jìn)化論方法至學(xué)習(xí)模型中，其由John Holland (1986)所發(fā)展出，以達(dá)爾文的物競(jìng)天擇原則為基。 應(yīng)用面包括：排程最佳化、旅行銷售員路徑排定、交換式網(wǎng)路的路由問題、 基因演算法可用以代替監(jiān)督式與非監(jiān)督式的資料探勘作業(yè)。,Data mining-951,3.4 基因演算法 (GA),基因演算法： 自n個(gè)元素中給訂初始母群P，如同細(xì)胞中之染色體般可做為未來可能的答案。 直到滿足一個(gè)終止條件： 使用一個(gè)適應(yīng)函數(shù)評(píng)價(jià)目前每一個(gè)解答，若某一個(gè)元素符合適應(yīng)函數(shù)所定義之標(biāo)準(zhǔn)，則其被保留於P中。 此母群所包含m個(gè)元素(m

17、n) ，使用基因運(yùn)算子來推論(n-m)個(gè)新元素，在姜新元素加到母群中。,Data mining-951,3.4 基因演算法 (GA),Data mining-951,GA流程圖,Data mining-951,編碼,Data mining-951,3.4 基因演算法,基因?qū)W習(xí)操作元 選擇機(jī)制(Selection) 交配機(jī)制(Crossover) 突變機(jī)制(Mutation),Data mining-951,選擇,輪盤法(Roulette Wheel selection) 競(jìng)爭(zhēng)法(Tournament selection) 穩(wěn)態(tài)法(Steady-state selection) 排序與尺規(guī)法(R

18、anking and scaling) 共享法(Sharing),Data mining-951,交配,GAs運(yùn)算模式之核心部分：交配。其參照使用者所設(shè)定之交配率，自各母體中選擇數(shù)條染色體組中挑選兩兩交換彼此之基因內(nèi)容，期產(chǎn)生更優(yōu)秀之基因組合。 算數(shù)運(yùn)算交配(Arithmetical Crossover) 啟發(fā)式運(yùn)算交配(Heuristic Crossover),Data mining-951,突變,為了避免落入局部最佳解中之方式。一般而言突變之目的有二 開拓新的搜尋範(fàn)圍，使得求解之範(fàn)圍有無限種可能 重新導(dǎo)入求解過程中不小心遺失之優(yōu)秀基因，使其可以再加入運(yùn)算中,基因演算法與監(jiān)督式學(xué)習(xí),Data

19、 mining-951,基因演算法與監(jiān)督式學(xué)習(xí),P,新的元素,Data mining-951,範(fàn)例,使用一個(gè)促銷信用卡資料庫(kù)的子集合，建立可區(qū)分哪些接受壽險(xiǎn)促銷或沒有接受壽險(xiǎn)促銷之個(gè)體。,類別型,Data mining-951,範(fàn)例,使用一個(gè)促銷信用卡資料庫(kù)的子集合，建立可區(qū)分哪些接受壽險(xiǎn)促銷或沒有接受壽險(xiǎn)促銷之個(gè)體。,Data mining-951,範(fàn)例,使用一個(gè)促銷信用卡資料庫(kù)的子集合，建立可區(qū)分哪些接受壽險(xiǎn)促銷或沒有接受壽險(xiǎn)促銷之個(gè)體。,Data mining-951,範(fàn)例,使用一個(gè)促銷信用卡資料庫(kù)的子集合，建立可區(qū)分哪些接受壽險(xiǎn)促銷或沒有接受壽險(xiǎn)促銷之個(gè)體。,Genetic Algor

20、ithms and Unsupervised Clustering,Data mining-951,非監(jiān)督是基因分群法,Data mining-951,非監(jiān)督是基因分群法,Data mining-951,GA 一般考量,Global optimization is not a guarantee. The fitness function determines the complexity of the algorithm. Explain their results provided the fitness function is understandable. Transforming the data to a form suitable for genetic learning can be a challenge.,Data mining-951,3.5 選擇資料探勘技術(shù),Is learning supervised or unsupervised? Is explanation required? W