資料探勘 (Data Mining)蔡懷寬 D7526010csie.ntu.edu.twPlease tell menWhy you are here?nMake a definition of Data Mining？InputOutput道道InputOutput？InputLinear SystemInputInput？InputNonlinear SystemNonlinear SystemInput？Chaotic SystemInputIntroductionnWhat is data mining?nWhy data mining?nHow to do data mining?nData Mining: On what kind of data?nData preprocessingnAssociation rulesnClusteringnClassificationDATA?“Data Structure”WisdomKnowledgeInformationData“Data Structure”n資料(Data)n未經處理的資訊n資訊(Information)n經某人組織,展現的資料n知識(Knowledge)n資訊經過讀,看,聽後理解而得到了知識n智慧(Wisdom)n知識經過精煉,整合後萃取出的精華有哪些資料 ?n文字n書籍, 期刊, WWW, 備忘錄, n刊載/參考n膠捲n照片, 其它影像n廣播, 電視n電話通訊n資料庫資料量:以美國國會圖書館為例n國會圖書館藏書量 (1999)n書: 約 20 Terabytes(1012 bytes)n20M booksn1 MB per bookn其他資料n13M 影像照片, 1MB each = 13 TBn4M 地圖, say 200 TBn500K 檔案, 1GB each = 500 TBn3.5M 有聲資料, 2000 TBn總計: 約3 petabytes (3000 terabytes)網路世界.n在1999年有約 800 Million Web Page在網際網 路上nFaulkers Cyberscape Digest 08/06/99n網路的交通流量是每 100 天成長二倍 估 計有 62 Million 美國人已經在使用網際網路 (US Commerce Dept 1998)n廣播節目花了 38 年才得到五千萬聽眾, 電視 節目花了 13 年, 而網際網路才花了 4 年.資訊生命週期(Information Life Cycle)CreationUtilizationSearchingActiveInactiveSemi-ActiveRetention/ MiningDispositionDiscardUsing CreatingAuthoring ModifyingOrganizing IndexingStoring RetrievalDistribution NetworkingAccessing Filtering資訊產生的問題n資訊儲存n如何且在哪裡儲存資訊 ?n資訊擷取n如何從儲存的資料還原成資訊n如何找到所需要的資訊n如何和 存取(Accessing)/過濾(Filtering)的方 法連結Key Issues CreationUtilizationSearchingActiveInactiveSemi-ActiveRetention/ MiningDispositionDiscardUsing CreatingAuthoring ModifyingOrganizing IndexingStoring RetrievalDistribution NetworkingAccessing FilteringData Mining ?DEFINITIONnDATA MINING 就是從資料中裡，將隱含 的、潛在性有用的及不清楚的資料，挖 掘、淬取出來的過程。也就是說從資料 中挖掘以前不知道的知識。n相關名詞 : 知識淬取(knowledge extraction) 資料打撈(data dredging) 資料考古學(data archaeology)遠古至今即存在Data Miningn月暈知風n礎潤知雨 n晚上起霧第二天晴天n看到媽媽拿鞭子落跑n這些在我們的傳統用法稱之為：n經驗法則Data Mining 之演進過程Statistics 1800?Pattern Recognition 1970Rule induction Machine learning1980Expert Systems 1970Relational Databases, Triggers 1980Knowledge Discovery for Databases (KDD) 1990 MIS decision support 1990Data Mining 1995Why Data MiningnNecessity is the Mother of Invention!Data Mining 為何興起?n商品條碼之廣泛使用n企業界之電腦化n數以百萬計之資料庫正在使用n多年來累積了大量企業交易資料Data KnowledgeData Mining 之同義詞nKnowledge Discovery in Databases (KDD) nKnowledge ExtractionnData archaeologynData Patten Analysis主要功用n從資料庫中挖掘知識n了解使用者行為n幫助企業作決策n增進商機nToo much!Data Mining 應用例子(1)n樂透Data Mining 應用例子(2)n超級市場n牛奶與白麵包n啤酒與香菸n啤酒與尿布Data Mining 應用例子(3)nNBA 美國職籃n1996, 紐約尼克隊 總教練 Pat Rileyn運用Data Miningn發現: 出戰芝加哥公牛隊，尼克中鋒尤 恩被包夾時，得分率偏低n一般被包夾防守時，有一人空出來，可輕鬆投籃得分Data Mining 應用例子(4)n搜尋網站nGOOGLEData Mining 應用例子(5)n公司對客戶的市場分析，例如：n消費習慣、客戶分群、消費預測n例子：n超級市場、錄影帶出租店、信用卡Data Mining 應用例子(7)n大宇宙的預測：n天氣預測n地震預測n土石流預測n慧星撞地球nData Mining 應用例子(8)n小宇宙的預測n疾病預測n基因功能預測n結構預測nHow to Do Data Mining?nFirst of all, you have to learnnHow to put your data DatabasenThen, you have to do ndata preprocessingnFinally, you should have some weapons :nData mining techniquesTypical Data Mining SystemData WarehouseWhy Data Preprocessing?nData in the real world is dirtynincomplete: lacking attribute values, lacking certain attributes of interest, or containing only aggregate datannoisy: containing errors or outliersninconsistent: containing discrepancies in codes or namesnNo quality data, no quality mining results!nQuality decisions must be based on quality datanData warehouse needs consistent integration of quality dataMajor Tasks in Data PreprocessingnData cleaningnFill in missing values, smooth noisy data, identify or remove outliers, and resolve inconsistenciesnData integrationnIntegration of multiple databases, data cubes, or filesnData transformationnNormalization and aggregationnData reductionnObtains reduced representation in volume but produces the same or similar analytical resultsnData discretizationnPart of data reduction but with particular importance, especially for numerical dataData Mining 主要方法介紹n關聯規則 (Association rule)n屬性導向歸納法(Attribute Oriented Induction)n資料分類 (Classification) n資料分群 (Data Clustering)n模式導向相似性搜尋(Pattern-Based Similarity Search)n資料方塊法 (Data Cube)nSequence Pattern Mining 關聯規則 Association Rulen同一個交易中，一個item出現也會引起另 一個item的出現nAssociation rule例子n若顧客購買麵包，則他很可能也會購買牛奶nAssociation rule: 麵包 = 牛奶nP(牛奶|麵包) 的機率值高關聯規則之 可信度 (confidence)n關聯規則 A = Bn可信度為: 在A出現之條件下出現B之機率n例子: 資料庫中的交易紀錄如下: t1: (,麵包,牛奶,) t2: (,麵包,) t3: (,麵包,牛奶,) t4: ()n請問 麵包 = 牛奶 之可信度為多少?關聯規則之 可信度 (Confidence)n資料庫中的交易紀錄 t1: (,麵包,牛奶,) t2: (,麵包,) t3: (,麵包,牛奶,) t4: ()n可信度= P(B|A) = P(A,B)/P(A)P(牛奶|麵包) = P(麵包 ,牛奶)P(麵包)N(麵包 ,牛奶)N(麵包)=關聯規則之 支持度 (Support)n關聯規則 A = Bn支持度為: A與B同時出現之機率 P(A, B)n例子: 資料庫中的交易紀錄如下: t1: (,麵包,牛奶,) t2: (,麵包,) t3: (,麵包,牛奶,) t4: ()n請問 麵包 = 牛奶 之支持度為多少?練習n交易編號購買產品nT1(K, A, D, B)nT2(D, A, C, E, B)nT3(C, A, B, E)nT4(B, A, D)n關聯規則 A= D 之 可信度 為多少?n關聯規則 A= D 之 支持度 為多少?練習n交易編號購買產品nT1(K, A, D, B)nT2(D, A, C, E, B)nT3(C, A, B, E)nT4(B, A, D)n請找出可信度 = 60% 支持度 = 50%之關聯規則Interestingness of Association Rules調查學生早餐: 打棒球