主講人：陳鴻文 副教授 銘傳大學資訊傳播工程系所 日期：3/13/2010 淺談資料探勘及其應用 主講人：陳鴻文 副教授 銘傳大學資訊傳播工程系所 日期：3/13/2010 1

Relational Databases, Triggers ~1980 Data Mining 之演進過程 Statistics ~1800? Pattern Recognition ~1970 Expert Systems ~1970 Relational Databases, Triggers ~1980 Rule induction Machine learning ~1980 MIS decision support ~1990 Knowledge Discovery for Databases (KDD) ~1990 Data Mining ~1995 2

Knowledge Discovery (KDD) Process Data mining—core of knowledge discovery process Pattern Evaluation Data Mining Task-relevant Data Selection Data Warehouse Data Cleaning Data Integration Databases April 25, 2019 Data Mining: Concepts and Techniques 3

資料探勘(挖掘)Data Mining 資料庫的知識挖掘 分為 (Knowledge Discovery in Database ,KDD) 1.分類分析(Classification) 2.群集分析(Clustering Analysis) 3.聯結(關連)分析(Association Rule Analysis) 4.次序相關分析(Sequential Pattern Analysis) 5.鏈結分析(Link Analysis) 6.時間順序相似性分析(Time Series Similarity Analysis) 4

資料探勘(挖掘)Data Mining 程序 1.決定目的 2.資料收集與整合 3.採用適當技術 4.結果分析 5.知識應用 5

企業策略 資料探勘任務 資料探勘技術 決定資料探勘技術之範例 維繫客戶關係 避免客戶流失 穩定流動性 高的客戶 產品創新 交叉行銷 產品合售 定義／預測流 動性高之客戶 交叉行銷 新產品與 市場開發 產品合售 資料探勘任務 分類分析 群集分析 聯結分析 次序相關分析 資料探勘技術 決定資料探勘技術之範例 6

Data Mining 的前置步驟 1. Data Warehousing 2. Data Selection 3. Preprocessing and Cleaning 4. Data Reduction and Transformation 5. Data Mining Data Mining 之前必須將資料整理過 7

分類分析之範例資料 顧客屬性 顧客編號 居住區域 年紀 婚姻狀況 性別 忠誠度 1 2 3 4 5 6 7 8 9 10 11 12 13 14 市區 市郊 鄉鎮 小於21 21至30 大於30 已婚 未婚 女 男 低 高 8

年紀 居住區域 居住區域 性別 可正確描述表6-1中資料的複雜決策樹 市區 市郊 鄉鎮 市區 市郊 鄉鎮 男 女 性別 性別 男 女 男 女 大於30 21至30 小於21 居住區域 居住區域 性別 市區 市郊 鄉鎮 市區 市郊 鄉鎮 男 女 忠誠度高 忠誠度高 忠誠度高 婚姻狀況 忠誠度低 婚姻狀況 性別 性別 男 女 男 女 已婚 未婚 已婚 未婚 忠誠度低 忠誠度高 忠誠度高 忠誠度低 性別 忠誠度高 居住區域 忠誠度高 男 女 市區 市郊 鄉鎮 忠誠度低 忠誠度高 忠誠度低 忠誠度高 未知 可正確描述表6-1中資料的複雜決策樹 9

居住區域 忠誠 婚姻 度高 狀況 可正確描述表6-1中資料的簡單決策樹 市區 市郊 鄉鎮 性別 男 女 已婚 未婚 忠誠 度低 忠誠 度高 10

Data from Credit History of Loan Application 第一章　機 器 學 習 ID3 (Quinlan , 1986 ) Induction Decision Tree Data from Credit History of Loan Application 11

第一章　機 器 學 習 12

第一章　機 器 學 習 13

ID3 Information Content：I(M) Ex：an honeit ain Expected Information Heads showing with 75% 14

gain（credit history）= 0.266 gain（debt）= 0.581 gain（collateral）= 0.756 第一章　機 器 學 習 Table 13.1 Based on Fig 13.15 information gain = 1.531－0.564 = 0.967……..gain（income） gain（credit history）= 0.266 gain（debt）= 0.581 gain（collateral）= 0.756 Finally → Fig 13.14 15

Fig 10.15 A partially constructed decision tree. Fig 10.16 Another partially constructed decision tree. Luger: Artificial Intelligence, 5th edition. © Pearson Education Limited, 2005 16

決策樹方法的優點 產生易於了解的規則 在規則導向領域的表現能力 節省分類時的計算時間 可處理連續性與類別性變項的能力 可被轉換為簡明的英文或SQL語言，這是此技術最強大的力量 在規則導向領域的表現能力 決策樹在有規則可循的領域是個絕佳的選擇 節省分類時的計算時間 典型的測試包括數值比較、群組成員，以及簡單的連結，在電腦上使用時，這些測試轉換為簡單的部林與整數操作，相當快速且便宜 可處理連續性與類別性變項的能力 一個類別就是一個分支。連續性變數可以藉由選擇其數值範圍內的一個數字輕易的加以分類 明白的指出最佳變數的能力 根節點是用最好的分隔變數 17

決策樹方法的缺點 遇上太多類別時容易犯錯 計算上的訓練昂貴 對非方形區域無能為力 發生於有許多層次或一個節點有許多分支的決策樹上 建制及修剪決策樹的演算法必須重複計算且進行比對，這是費時費力的 對非方形區域無能為力 大部分決策樹演算法一次只能檢查一個變數。這導致方型的分類區域，無法和決策空間中真實的資料分部妥善對應。 18

關聯法則分析 Rule X→Y 滿足X∩Y=∮ X和Y的所有交易項目的集合必須出現在至少S%全部交易中……Minimum Support 在所有包含X之交易中，至少有C%包含Y的交易…… Minimum confidence 範例 交易代號 交易項目 1 柳橙汁,碳酸飲料,清潔用品 2 牛奶,柳橙汁,清潔用品 3 柳橙汁,洗衣精,碳酸飲料 4 碳酸飲料,底片 5 碳酸飲料,洋芋片 19

1 - itemset (S%=30%) 2 - itemset 1.柳橙汁→碳酸飲料 C=66.67% 2.碳酸飲料→柳橙汁 C=50% 支持率 Large 1-itemset 柳橙汁 60% ˇ 碳酸飲料 80% 清潔用品 40% 牛奶 20% X 洗衣精 底片 洋芋片 2 - itemset 2-itemset 支持率 Large 1-itemset (柳橙汁,碳酸飲料) 40% ˇ (柳橙汁,清潔用品) (碳酸飲料,清潔用品) 20% X 1.柳橙汁→碳酸飲料　　　C=66.67% 2.碳酸飲料→柳橙汁　　　C=50% 3.柳橙汁→清潔用品　　　C=66.67% 4.清潔用品→柳橙汁　　　C=100% ※ Large3-itemset is empty ˇ ˇ C=60% 20

分群演算法(K-MEANS ALGORITHM) Begin with an arbitrary assignment of samples to clusters or begin with an arbitrary set of cluster centers and assign samples to nearest centers. Compute the sample mean of each cluster. Reassign each sample to the cluster eith the nearest mean. If the classification of all samples has not changed ,stop ;else go to step2. 21

種子3 種子2 種子1 X2 X1 圖10.3 初始種子決定了初始的群集邊界 22

圖10.4 計算新群集的質心 X2 X1 23

X2 X1 圖10.5 每一次重複的過程中，所有群集分配都必須重新計算一次 24