资料探勘 (Data Mining).ppt

《资料探勘 (Data Mining).ppt》由会员分享，可在线阅读，更多相关《资料探勘 (Data Mining).ppt（101页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、資料探勘(Data Mining)蔡懷寬D7526010csie.ntu.edu.twPlease tell menWhy you are here?nMake a definition of Data Mining？InputOutput道InputOutput？InputLinear SystemInput Input？InputNonlinear SystemInput？Chaotic SystemInputIntroductionnWhat is data mining?nWhy data mining?nHow to do data mining?nData Mining:On wh

2、at 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

3、電話通訊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年有約 800MillionWebPage在網際網路上nFaulkersCyberscapeDigest08/06/99n網路的交通流量是每 100 天成長二

4、倍 估計有 62Million 美國人已經在使用網際網路(USCommerceDept1998)n廣播節目花了 38 年才得到五千萬聽眾,電視節目花了 13 年,而網際網路才花了 4 年.資訊生命週期(InformationLifeCycle)CreationUtilizationSearchingActiveInactiveSemi-ActiveRetention/MiningDispositionDiscardUsing CreatingAuthoringModifyingOrganizingIndexingStoringRetrievalDistributionNetworkingAcc

5、essingFiltering資訊產生的問題n資訊儲存n如何且在哪裡儲存資訊?n資訊擷取n如何從儲存的資料還原成資訊n如何找到所需要的資訊n如何和 存取(Accessing)/過濾(Filtering)的方法連結Key IssuesCreationUtilizationSearchingActiveInactiveSemi-ActiveRetention/MiningDispositionDiscardUsing CreatingAuthoringModifyingOrganizingIndexingStoringRetrievalDistributionNetworkingAccessing

6、FilteringData Mining?DEFINITIONnDATA MINING 就是從資料中裡，將隱含的、潛在性有用的及不清楚的資料，挖掘、淬取出來的過程。也就是說從資料中挖掘以前不知道的知識。n相關名詞:知識淬取(knowledge extraction)資料打撈(data dredging)資料考古學(data archaeology)遠古至今即存在Data Miningn月暈知風n礎潤知雨 n晚上起霧第二天晴天n看到媽媽拿鞭子落跑n這些在我們的傳統用法稱之為：n經驗法則DataMining之演進過程Statistics 1800?Pattern Recognition 1970R

7、ule inductionMachine learning 1980Expert Systems 1970RelationalDatabases,Triggers1980Knowledge Discovery for Databases(KDD)1990MIS decision support1990Data Mining 1995Why Data MiningnNecessity is the Mother of Invention!Data Mining 為何興起?n商品條碼之廣泛使用n企業界之電腦化n數以百萬計之資料庫正在使用n多年來累積了大量企業交易資料 Data KnowledgeD

8、ata 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,紐約尼克隊 總教練 PatRileyn運用DataMiningn發現:出戰芝加哥公牛隊，尼

9、克中鋒尤恩被包夾時，得分率偏低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結構預測n HowtoDoDataMining?nFirst of all,you have to learnnHow to put your

10、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 o

11、nly 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

12、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

13、same or similar analytical resultsnData discretizationnPart of data reduction but with particular importance,especially for numerical dataData Mining 主要方法介紹n關聯規則(Associationrule)n屬性導向歸納法(AttributeOrientedInduction)n資料分類(Classification)n資料分群(DataClustering)n模式導向相似性搜尋(Pattern-BasedSimilaritySearch)n資料

14、方塊法(DataCube)nSequencePatternMining 關聯規則 AssociationRulen同一個交易中，一個item出現也會引起另一個item的出現nAssociationrule例子n若顧客購買麵包，則他很可能也會購買牛奶nAssociationrule:麵包=牛奶nP(牛奶|麵包)的機率值高關聯規則之 可信度(confidence)n關聯規則 A=Bn可信度為:在A出現之條件下出現B之機率n例子:資料庫中的交易紀錄如下:t1:(,麵包,牛奶,)t2:(,麵包,.)t3:(,麵包,牛奶,)t4:()n請問 麵包=牛奶 之可信度為多少?關聯規則之 可信度(Confide

15、nce)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關聯規則

16、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 調查學生早餐:打棒球:60%吃麥片:75%打棒球且吃麥片:40%nP(吃麥片|打棒球)=P(吃麥片打棒球)/P(打棒球)=40%/60%=0.66打棒球=吃麥片 (66%)nP(吃麥片)=75%AttributeOrientedInduction屬性導向歸納法nConcept Tree:gen

17、eral to specific加拿大 某大學資料庫 NameStatusMajorBirth_PlaceGPAAndersonM.A.historyVancouver3.5BachJuniormathCalgary3.7CarltonJuniorliberalartEdmonton2.6FraserM.S.physicsOttawa3.9GuptaPh.D.mathBombay3.3HartSophomorechemistryRichmond2.7JacksonSeniorcomputingVictoria3.5LiuPh.D.biologyShanghai3.4MeyerSophomore

18、musicBurnaby3.0MonkPh.D.computingVictoria3.8WangM.S.statisticsNanjing3.2WiseFreshmanliteratureToronto3.9ANYCanadaforeignB.COntarioChinaIndiaVancouverVictoriaBeijing.Bombay出生地之 Concept TreeBumaby,.,Vancouver,VictoriaBritishColumbiaCalgary,.Edmonton,LethbridgeAlbertaHamilton,Toronto,WaterlooOntarioBom

19、bay,.,NewDelhiIndiaBeijing,Nanjing,.,ShanghaiChinaIndia,ChinaforeignBritishColumbia,Alberta,.,OntarioCanadaforeign,CanadaANY(place)biology,chemistry,computing,.,physicsscienceliterature,music,.,paintingartscience,artANY(major)freshman,sophomore,junior,seniorundergraduateM.S.,M.A.,Ph.D.graduateunderg

20、raduate,graduateANY(status)0.0-1.99poor2.0-2.99average3.0-3.99good4.0-4.99excellentpoor,average,good,excellentANY(grade)年級與學位之 Concept TreefreshmansophomorejuniorseniorM.S.M.A.Ph.DundergraduategraduateANY問題:請找出研究生的特性法則(characteristic rule)nInitial Relation:將研究生資料過濾出來NamesMajorBirth_PlaceGPAVoteAnder

21、sonhistoryVancouver3.51FraserphysicsOttawa3.91GuptamathBombay3.31LiubiologyShanghai3.41MonkcomputingVictoria3.81WangstaisticsNanjing3.21策略1：屬性移除(Attribute Removal)nNames這個屬性中有許多不同的屬性值，且沒有較高的概念層級可以表示它，所以Names屬性就被移除 MajorBirth_PlaceGPAVotehistoryVancouver3.51physicsOttawa3.91mathBombay3.31biologyShang

22、hai3.41computingVictoria3.81staisticsNanjing3.21策略：概念樹的爬升(concept-tree climbing)n假如某一屬性在概念階層中存在著一個更高層級的概念，則該屬性值就以其更高層級的值來取代 n”history”、”physics”、”math”、”biology”會由”science”取代n”literature”、”music”、”painting”會由”art”取代策略：資料數的傳播(vote propagation)n屬性值向上爬升後，若產生相同的tuple，則將相同的tuple合併為一筆一般化tuple，並將vote值累加到歸納

23、後的tuple中MajorBirth_PlaceGPAVoteartB.Cexcellent35scienceOntarioexcellent10scienceB.Cexcellent30scienceIndiagood10scienceChinagood15策略4：門檻控制 (Threshold Control)n屬性的門檻值n設定屬性的門檻值5 nRecords的門檻值n設定歸納後Records的門檻值4 MajorBirth_PlaceGPAVoteArtCanadaexcellent35ScienceCanadaexcellent40ScienceForeigngood25MajorB

24、irth_PlaceGPAVoteart,scienceCanadaExcellent75ScienceForeigngood25策略：法則轉換(rule transformation)n將最終表格的tuple，轉換成法則 n一個研究生（有75%的機率）是加拿大人，得到極佳的GPA或（有25%的機率）是外國學生，得到不錯的GPA 練習(屬性導向歸納法)n請問:研究生與大學生之國籍狀況?註:屬性的門檻值2筆)(30)(90)(30)(40 70)思考:Association Rule 與 Sequential Pattern有何不同?思考:Association Rule 與 Sequentia

25、l Pattern有何不同?nAssociation Rule 關心同一時間的交易n若顧客購買麵包，則他同一時間也會購買牛奶nSequential Pattern 關心不同時間的交易n租過黃飛鴻第一集，經過一段時間，通常會再租黃飛鴻第二集weekDateTopic191.9.21Moon festival291.9.28Introduction to Data mining391.10.5Market basis analysis491.10.12Memory-based reasoning591.10.19Data Preprocessing691.10.26Classification I

26、:Decision tree791.11.2Classification II:Support Vector Machine891.11.9Classification III:Applications991.11.16Midterm1091.11.23Data Clustering I:Hierarchical clustering1191.11.30Data Clustering II:Partitioned clustering1291.12.7Data Clustering III:Applications1391.12.14Advanced algorithm:Neural Network and Genetic Algorithm1491.12.21Information retrieval1591.12.28Text mining1692.1.4Student project report1792.1.15Final term