資探勘導 - 以圖書為2 Ming-Yen Lin, IECS/FCU一個圖書的子 ?事實 (Nov. 2003) ? 約 494,000 書 ? 借還書記筆 ? 25000 (Jul.), 41000 (Aug.), 80000 (Sep.), 93000 (Oct.) ?每一筆記: 一堆書 (借或還) ?問題(a) 哪些書經常被一起借出去? (b) 張三借 (計概、C範），還有哪些書可能會被他 同時借出去？ (c) 四想借 (魔戒I)，我們可以推薦他一起借哪些書？3 Ming-Yen Lin, IECS/FCU資探勘可以給我們答案: 步驟1 - Data Selection?先從借還書記擷取出想要的資? 為於明，本子僅以 10 筆記為 ? 我們將書以代號表示(計概, C程式設計, 笑話大全) (笑話大全, 生活智慧王, C範) (棋王,魔戒I,英文寫作) (生活智慧王,魔戒I) (計概, C程式設計,魔戒I, C範) (魔戒I) (C程式設計,笑話大全,英文寫作) (計概, C程式設計,笑話大全,生活智慧王,棋王,魔戒I) (計概,笑話大全, C範) (C程式設計,笑話大全, C範)a:計概, c:C程式設計, d:笑話大全, e:生活智慧王 f:棋王, h:魔戒I, j:英文寫作, k:C範僅 需 借 書 記 4 Ming-Yen Lin, IECS/FCU資探勘可以給我們答案: 步驟2 - Perform Mining?我們覺得 frequency 30%是經 常的話 （本中至少出現 3 次）? (d, k): 3 表笑話大全 and C範 在 database中出 現3次? 問題 (a): 哪些書經常被一起借出去? Answer: (a, c, d) (d, e, k) (f, h, j) (e, h) (a, c, h, k) (h) (c, d, j) (a, c, d, e, f, h) (a, d, k) (c, d, k)(a): 4 (c): 5 (d): 6 (e): 3 (k): 4 (h): 5 (a, c): 3 (a, d): 3 (c, d): 4 (d, k): 3Perform mining task (task: discover frequent item-sets)(計概): 4 (C程式設計): 5 (笑話大全): 6 (生活智慧王): 3 (C範): 4 (魔戒I): 5 (計概, C程式設計): 3 (計概,笑話大全): 3 (C程式設計,笑話大全): 4 (笑話大全, C範): 3i.e.5 Ming-Yen Lin, IECS/FCU這個工作容容?Yes: 如果只要處 8本書與10筆記 ?No! 我們有494,000 書! 糟的是：在四個月 內，我們有 (25K+41K+80K+93K) = 239,000 筆借還書記?打對折，借書記也有約119,000 筆records ?我們要檢查多少種可能的組合? (哪些書會 一起借) ?假設: 一個者一次最多只能借 6 本書6 Ming-Yen Lin, IECS/FCU多少種可能的組合? 8本書 ? C(8,1) = 8, C(8,2) = 28, C(8,3) = 56, C(8,4) = 70, C(8,5) = 56, C(8,6) = 28; 8 + 28 + 56 + 70 + 56 + 28 = 246 組合組合 ? 但是，我們有494,000本書 ? 借一本 C(N,1) = 494,000 ? 借 2 本 C(N,2) = (N*N-1)/2 = 1.21011 ? 借 3 本 C(N,3) = 21016 ? 借 4 本 C(N,4) = 2.51021 ? 借 5 本 C(N,5) = 2.51026 ? 借 6 本 C(N,6) = 21031 ? 總共有: 嚇死人的多種可能組合! ? 要知道某一個組合X 的frequency: 檢查這119,000筆記筆記是 否包含X ? 檢查 21031可能組合，每個跟 119,000筆筆比對 ? OH! My God ! SOS! 我需要一個資探勘的好方法！7 Ming-Yen Lin, IECS/FCU最有名的方法: Apriori1stscanC1L1L2C2C22nd scanC3L33rdscan1/4(d) 3/4(e)3/4(c)3/4(b)2/4(a)supItemset3/4(e)3/4(c)3/4(b)2/4(a)supItemset(c, e)(b, e)(b, c)(a, e)(a, c)(a, b)Itemset1/4(a, b) 2/4(a, c) 1/4(a, e) 2/4(b, c) 3/4(b, e) 2/4(c, e)supItemset2/4(a, c) 2/4(b, c) 3/4(b, e) 2/4(c, e)supItemset(b, c, e)Itemset2/4(b, c, e)supItemsetminsup = 2/4Itemset DB(b, e)(a, b, c, e)(b, c, e)(a, c, d)Itemset?Ck: candidate k-itemsets?Lk: frequent k-itemsets?candidate potentially frequent 8 Ming-Yen Lin, IECS/FCU問題 (a) 解決，(b)呢?(b) 張三借 (計概、C範），還有哪些書可 能會被他同時借出去？ ? 簡單！ ?取出所有含 (計概、C範）的借書紀 ?紀在同一次借閱的其他書籍 ?這些書籍的集 ? 一、！如果我想預先指定 (計概、C 範），或者，我根本知道要指定麼，你 能能給我所有這種問題的相關資訊？ ?或者，跟 (a) 似，給那些經常出現的 ? (a) 的答案可以用回答問題(b) ? (a) 的答案 = 經常出現的組合，以及出現的次 （或頻）9 Ming-Yen Lin, IECS/FCU產生相關性的規則?X Y，這種資訊稱為關規則 (association rule) ?(a)(c): (a) 出現 暗示暗示 (c) 也會同時出現 ?(c)(a): (c) 出現 暗示暗示 (a) 也會同時出現 ?(a, c)(b,e): (a, c) 出現暗示暗示 (b, e) 也會同時出現 ?X (also Y) 是一種項目的集合 （組合），限於單一項目 ?本圖書借閱中，我們有?(a)(c), (c)(a), (a)(d), (d)(a), (c)(d), (d)(c),(d)(k), (k)(d) ?暗示的強呢?（規則可可靠？）(a): 4 (c): 5 (d): 6 (e): 3 (k): 4 (h): 5 (a, c): 3 (a, d): 3 (c, d): 4 (d, k): 310 Ming-Yen Lin, IECS/FCU關規則: Support 經常出現的門檻值)，及最 小confidence (minconf;信心的門檻值) ?挖出 所有關規則，每個規則滿足sup minsup, conf minconf. ?步驟解決: ?找出滿足minsup的頻繁項目集（frequent itemsets） ?導出滿足minconf 的規則12 Ming-Yen Lin, IECS/FCU等等，問題 (c)?(c) 四想借 (魔戒I)，要推薦他一起借？ ? Rules: (c)(d)40%, 80%, (c)(a)30%, 60% ?a:計概, c:C程式設計, d:笑話大全?(C程式設計)(笑話大全)40%, 80%?(C程式設計)(計概)30%, 60%?大頭想借C程式設計，我們比較有信心推薦 他一起借笑話大全 ?推薦的基礎是依過去的借閱情形，80% 者 借C程式設計 同時也會借笑話大全，而且 這種模式(pattern) 在資庫中出現40%13 Ming-Yen Lin, IECS/FCU還有問題哪 (I)? 原始問題(b) 跟 (計概、C範）有關，問題 (c) 跟 (魔戒 I)有關 ? 我們用(a)的答案回答 (b) and (c)，可惜這次(a) 面並 沒有包含 (計概、C範），也沒有 (魔戒I)? 因為他們是FREQUENT itemsets （常出現，怎麼辦？） ? 把門檻值（ minsup）低，想辦法讓結果包含多patterns ? 如果結果沒有想要的，重複這個程序 改變 minsup，重 新進mining, 再評估找到的 patterns ?互動式探勘互動式探勘 (Interactive mining) ? 像問題(b)指定答案必須有計概，這種在進探勘時 （一開始）就指定mining的條件（constraints）的?條 件式的資探勘 (constrained data mining).(計概): 4; (C程式設計): 5; (笑話大全): 6;(魔戒I): 5; (生活智慧王): 3; (C範): 4; (計概, C程式設計): 3; (計概,笑話大全): 3; (C程式設計,笑話大全): 4; (笑話大全, C範): 314 Ming-Yen Lin, IECS/FCU乖乖，還有問題哪 (II)? Page 3, Step1 - Data Selection, 先從借還書記 擷取出想要的資 ?原始資可沒那麼漂！可能長這樣笑話 大全C範C程 式Borrow11/11/0433?Ke英文 寫作魔戒I棋王Return06/10/032491001Mary棋王智慧王?C程式計概Return09/22/041993038LiBorrowBorrowaction03/10/1010/10/03Valid30022age9201892003idPeteTomname魔戒I笑話 大全C程式計概Titletitletitletitletitle15 Ming-Yen Lin, IECS/FCUData Cleaning （資清洗）?Data Cleaning: (1) 移除錯誤輸入、空白 位笑話 大全C範C程 式Borrow11/11/0433?Ke英文 寫作魔戒I棋王Return06/10/032491001Mary棋王智慧王?C程式計概Return09/22/041993038LiBorrowBorrowaction03/10/1010/10/03Valid30022age9201892003idPeteTomname魔戒I笑話 大全C程式計概titletitletitletitletitle(2) 取出需要的位16 Ming-Yen Lin, IECS/FCUKDD Process: 總圖Data CleaningDatabasesData WarehouseTask- relevant DataData SelectionData MiningEvaluationKnowledgePatternsan interactive and iterative process Knowledge Discovery in Databases (KDD)17 Ming-Yen Lin, IECS/FCUData Mining?Extraction of interesting information or patterns from data in large databases ?implicit: 非外顯收集的 ?non-trivial: 119,