第1章數(shù)據(jù)挖掘課件..ppt

1、2020年7月7日星期二,Data Mining: Concepts and Techniques,1,何謂數(shù)據(jù)挖掘？,數(shù)據(jù)挖掘是從大量數(shù)據(jù)中尋找其規(guī)律的技術(shù)，主要有數(shù)據(jù)準(zhǔn)備、規(guī)律尋找和規(guī)律表示三個步驟。 數(shù)據(jù)準(zhǔn)備是從各種數(shù)據(jù)源中選取和集成用于數(shù)據(jù)挖掘的數(shù)據(jù)； 規(guī)律尋找是用某種方法將數(shù)據(jù)中的規(guī)律找出來； 規(guī)律表示是用盡可能符合用戶習(xí)慣的方式（如可視化）將找出的規(guī)律表示出來。 數(shù)據(jù)挖掘在自身發(fā)展的過程中，吸收了數(shù)理統(tǒng)計、數(shù)據(jù)庫和人工智能中的大量技術(shù)。,2020年7月7日星期二,Data Mining: Concepts and Techniques,2,數(shù)據(jù)挖掘項目實例, 信用卡公司分析信用卡歷

2、史數(shù)據(jù)，判斷哪些人有風(fēng)險，哪些沒有 超市分析交易數(shù)據(jù)，安排貨架上貨物擺布，以提高銷售 調(diào)查局分析行為模式，判斷哪些人對受保護的信息具有潛在威脅 藥房分析醫(yī)師的處方，判斷哪些醫(yī)師愿意購買他們的產(chǎn)品 保險公司分析以前的客戶記錄，決定哪些客戶是潛在花費昂貴的 汽車公司分析不同地方人的購買模型，針對性地發(fā)送給客戶喜歡的汽車的手冊 人才中心分析不同客戶的工作歷史，發(fā)送客戶潛在的感興趣的工作信息 訪問沒有歸類的競爭對手?jǐn)?shù)據(jù)庫，推斷出潛在的歸類信息,2020年7月7日星期二,Data Mining: Concepts and Techniques,3, 教育學(xué)院分析學(xué)生歷史信息，決定哪些人愿意參加培訓(xùn)，發(fā)送

3、手冊給他們 核武器工廠分析歷史核查信息記錄，決定沒有采用哪項預(yù)防措施將導(dǎo)致核災(zāi)難 廣告公司分析人們購買模式,估計他們的收入和孩子數(shù)目,作為潛在的市場信息 調(diào)查局分析不同團體的旅游模式，決定不同團體之間的關(guān)聯(lián) 醫(yī)師分析病人歷史和當(dāng)前用藥情況，不僅診斷用藥而且預(yù)測潛在的問題 稅務(wù)局分析不同團體的交所得稅的記錄，發(fā)現(xiàn)異常模型和趨勢 調(diào)查局分析罪犯記錄，推斷哪些人可能會犯恐怖罪和大的謀殺罪,2020年7月7日星期二,Data Mining: Concepts and Techniques,4,Chapter 1. Introduction,什么激發(fā)了數(shù)據(jù)挖掘，為什么它是重要的？ 什么是數(shù)據(jù)挖掘？ 在何

4、種數(shù)據(jù)上進行數(shù)據(jù)挖掘？ 數(shù)據(jù)挖掘功能可以挖掘什么類型的模式 所有模式都是有趣的嗎？ 數(shù)據(jù)挖掘系統(tǒng)的分類 數(shù)據(jù)挖掘的主要問題,2020年7月7日星期二,Data Mining: Concepts and Techniques,5,動機： “需要是發(fā)明之母”,數(shù)據(jù)泛濫問題 自動數(shù)據(jù)收集工具和成熟的數(shù)據(jù)庫技術(shù)使得大量數(shù)據(jù) 存儲于數(shù)據(jù)庫，數(shù)據(jù)倉庫和其他信息庫。 我們數(shù)據(jù)豐富但信息貧乏 解決辦法：數(shù)據(jù)倉庫和數(shù)據(jù)挖掘 數(shù)據(jù)倉庫和聯(lián)機分析處理 大型數(shù)據(jù)庫中的有趣知識（規(guī)則、模式）,2020年7月7日星期二,Data Mining: Concepts and Techniques,6,數(shù)據(jù)庫技術(shù)的演化,196

5、0s: 從原始的文件處理演化到復(fù)雜的、功能強大的數(shù)據(jù)庫系統(tǒng) 數(shù)據(jù)收集，數(shù)據(jù)庫創(chuàng)建，信息管理系統(tǒng)（IMS)和數(shù)據(jù)庫管理系統(tǒng) 1970s: 從層次和網(wǎng)狀數(shù)據(jù)庫系統(tǒng)發(fā)展到開發(fā)關(guān)系數(shù)據(jù)庫系統(tǒng) 關(guān)系數(shù)據(jù)模型，關(guān)系數(shù)據(jù)庫管理系統(tǒng)工具 1980s:廣泛接受關(guān)系技術(shù)，研究和開發(fā)新的、功能強大的數(shù)據(jù)庫系統(tǒng)。使用了先進的數(shù)據(jù)模型，面向?qū)ο竽Ｐ?，擴充關(guān)系模型，對象-關(guān)系模型和演繹模型。 關(guān)系數(shù)據(jù)庫管理系統(tǒng)（RDBMS）, 高級數(shù)據(jù)模型(面向?qū)ο蟆⒀堇[ 等等)和面向應(yīng)用的DBMS(空間的、科學(xué)的、工程的） 1990s: 數(shù)據(jù)倉庫是一種數(shù)據(jù)庫結(jié)構(gòu)。這是一種多個異種數(shù)據(jù)源在單個站點以統(tǒng)一的模式組織的存儲，以支持管理決策。

6、 數(shù)據(jù)挖掘和數(shù)據(jù)倉庫，多媒體數(shù)據(jù)庫和web數(shù)據(jù)庫 2000s（新一代綜合信息系統(tǒng)） Stream data management and mining Data mining and its applications Web technology (XML, data integration) and global information systems,2020年7月7日星期二,Data Mining: Concepts and Techniques,7,數(shù)據(jù)挖掘的出現(xiàn),數(shù)據(jù)挖掘出現(xiàn)于20世紀(jì)80年代后期，90年代有了突飛猛進的發(fā)展。2001年，Gartner Group的一次高級技術(shù)調(diào)查將

7、數(shù)據(jù)挖掘和人工智能列為“未來三到五年內(nèi)將對工業(yè)產(chǎn)生深遠影響的五大關(guān)健技術(shù)”之首，并且還將并行處理體系和數(shù)據(jù)挖掘列為未來五年內(nèi)投資焦點的十大新興技術(shù)前兩位。 數(shù)據(jù)挖掘出現(xiàn)于20世紀(jì)80年代末，最早是在數(shù)據(jù)庫領(lǐng)域發(fā)展起來的，稱為數(shù)據(jù)庫中的知識發(fā)現(xiàn)(KDD，Knowledge Discovery in Database)。數(shù)據(jù)挖掘是KDD過程中的一個環(huán)節(jié)，它的歷史雖然較短，但從20世紀(jì)90年代以來，發(fā)展速度很快，目前還沒有一個完整的定義。 數(shù)據(jù)庫中發(fā)現(xiàn)知識一詞首次出現(xiàn)于1989年在美國底特律召開的第十一屆國際聯(lián)合人工智能學(xué)術(shù)會議上，到1995年在加拿大蒙特利爾召開的首屆KDD&Data Mining

8、國際學(xué)術(shù)會議，再到以后每年都要召開一次的KDD&Data Mining國際學(xué)術(shù)會議，經(jīng)過十多年的努力，數(shù)據(jù)挖掘技術(shù)的研究已經(jīng)取得了豐碩的成果，不少軟件公司已研制出數(shù)據(jù)挖掘軟件產(chǎn)品，并在北美、歐洲等國家得到應(yīng)用。,2020年7月7日星期二,Data Mining: Concepts and Techniques,8,數(shù)據(jù)挖掘的當(dāng)前熱點,數(shù)據(jù)挖掘技術(shù)的三大支柱為：數(shù)據(jù)庫技術(shù)；人工智能技術(shù)及概率與數(shù)理統(tǒng)計。 當(dāng)前數(shù)據(jù)挖掘的研究熱點為： 1.網(wǎng)站的數(shù)據(jù)挖掘（Web site data mining） 2.生物信息或基因的數(shù)據(jù)挖掘 3.文本的數(shù)據(jù)挖掘（Textual Mining）,2020年7月7日星

9、期二,Data Mining: Concepts and Techniques,9,什么是數(shù)據(jù)挖掘？,Data mining (knowledge discovery from data) 在大型數(shù)據(jù)庫中提取有趣的（重要的，隱含的，目前未知的，潛 在有用的）信息和模式 Data mining: a misnomer? 另外的名字和它們的“內(nèi)在故事” Knowledge discovery (mining) in databases (KDD), knowledge extraction, data/pattern analysis, data archeology, data dredging

10、, information harvesting, business intelligence, etc. 什么不是數(shù)據(jù)挖掘？ Simple search and query processing (Deductive) expert systems,2020年7月7日星期二,Data Mining: Concepts and Techniques,10,專家系統(tǒng),專家系統(tǒng)曾經(jīng)是人工智能研究工作者的驕傲。在研制一個專家系統(tǒng)時，知識工程師首先要從領(lǐng)域?qū)＜夷抢铽@取知識，這一過程實質(zhì)上是歸納過程，是非常復(fù)雜的個人到個人之間的交互過程，有很強的個性和隨機性。因此，知識獲取成為專家系統(tǒng)研究中公認的瓶頸問

11、題。 其次，知識工程師在整理表達從領(lǐng)域?qū)＜夷抢铽@得的知識時，用if-then等類的規(guī)則表達，約束性太大，用常規(guī)數(shù)理邏輯來表達社會現(xiàn)象和人的思維活動局限性太大，也太困難，知識表示又成為一大難題。 此外，即使某個領(lǐng)域的知識通過一定手段獲取并表達了，但這樣做成的專家系統(tǒng)對常識和百科知識相當(dāng)缺乏，而人類專家知識是以擁有大量常識為基礎(chǔ)的。 人工智能技術(shù)的三大難題：“知識獲取、知識表示、缺乏常識”大大限制了專家系統(tǒng)的應(yīng)用。人工智能學(xué)者開始著手基于案例的推理，尤其是從事機器學(xué)習(xí)的科學(xué)家們，不再滿足自己構(gòu)造的小樣本學(xué)習(xí)模式的象牙塔，開始正視現(xiàn)實生活中大量的、不完全的、有噪聲的、模糊的、隨機的大數(shù)據(jù)樣本，從而與

12、數(shù)據(jù)倉庫技術(shù)相結(jié)合，轉(zhuǎn)向數(shù)據(jù)挖掘技術(shù)。,2020年7月7日星期二,Data Mining: Concepts and Techniques,11,Database Processing vs. Data Mining Processing數(shù)據(jù)庫查詢對數(shù)據(jù)挖掘查詢,Query Well defined SQL,Query Poorly defined No precise query language,Data Operational data,Output Precise Subset of database,Data Not operational data,Output Fuzzy Not

13、 a subset of database,2020年7月7日星期二,Data Mining: Concepts and Techniques,12,Query Examples查詢實例對比,Database Data Mining,Find all customers who have purchased milk,Find all items which are frequently purchased with milk. (association rules),Find all credit applicants with last name of Smith.,Identify cu

14、stomers who have purchased more than $10,000 in the last month.,Find all credit applicants who are poor credit risks. (classification),Identify customers with similar buying habits. (Clustering),2020年7月7日星期二,Data Mining: Concepts and Techniques,13,Why Data Mining?Potential Applications,數(shù)據(jù)庫分析和決定支持 市場

15、分析和管理 目標(biāo)市場， 用戶關(guān)系管理,市場菜籃子分析,交叉銷售, 市場分割。 風(fēng)險性分析和管理 預(yù)測， 顧客保留,改善保險,質(zhì)量控制, 競爭分析 欺騙察覺和發(fā)現(xiàn)不尋常的模式(outliers) 其他應(yīng)用 文本挖掘(新聞組，電子郵件，文件) 和WEB分析 智能詢問回答 生物信息學(xué)和生物數(shù)據(jù)分析,2020年7月7日星期二,Data Mining: Concepts and Techniques,14,市場分析和管理(1),用于分析的數(shù)據(jù)從何來？ 信用卡交易， 信譽卡，折扣券，用戶投訴電話，公眾生活方式調(diào)查。 目標(biāo)市場 找出具有相同特征（興趣，收入水平，消費習(xí)慣等等）的“模式”顧客群。 隨著時間的推

16、移決定顧客的購買方式 從單獨銀行賬戶向聯(lián)合銀行賬戶的轉(zhuǎn)變。例如：結(jié)婚 Predict what factors will attract new customers 交叉市場分析 不同產(chǎn)品之間的銷售關(guān)聯(lián)關(guān)系 在此關(guān)聯(lián)信息上進行預(yù)測,2020年7月7日星期二,Data Mining: Concepts and Techniques,15,市場分析和管理(2),顧客形象 數(shù)據(jù)挖掘可以告訴你什麼樣的顧客會買什麼樣的 產(chǎn)品（聚類或分類） 識別顧客需求 保證為不同的顧客提供了最好的產(chǎn)品 使用預(yù)測手段去發(fā)現(xiàn)什麼因素會吸引新的顧客。 提供匯總信息 各種各樣的多方位匯總信息 統(tǒng)計的匯總信息（數(shù)據(jù)中心的趨勢和變

17、化）,2020年7月7日星期二,Data Mining: Concepts and Techniques,16,公司分析和風(fēng)險管理,財政計劃和財產(chǎn)評估 現(xiàn)金流分析和預(yù)測 財產(chǎn)分析的偶發(fā)性需求分析 典型性分析和時序分析（財政比率，趨勢分析等等） 資源計劃： 總結(jié)和比較資源和花銷 競爭： 控制對手和市場的方向 把顧客劃分成許多類，依據(jù)類的劃分編制價格程序 把這個價格策略放到高度競爭的市場環(huán)境內(nèi),2020年7月7日星期二,Data Mining: Concepts and Techniques,17,欺騙性檢測和管理(1),廣泛應(yīng)用于醫(yī)療系統(tǒng), 零售系統(tǒng),信用卡服務(wù), 電信(電話卡欺騙行 為), 等

18、等. 實現(xiàn)途徑：利用歷史性數(shù)據(jù)建立欺騙性行為模型并使用數(shù)據(jù)挖掘幫助識別同類例子 具體事例 汽車保險：檢測出那些故意制造車禍而索取保險金的人 來路不明錢財?shù)淖粉? 發(fā)現(xiàn)可疑錢財交易(美國財政部的財政犯罪 執(zhí)行網(wǎng)) 醫(yī)療保險: 檢測出潛在的病人，呼叫醫(yī)生和證明人,2020年7月7日星期二,Data Mining: Concepts and Techniques,18,欺騙性檢測和管理(2),發(fā)現(xiàn)不正確的醫(yī)學(xué)治療 澳大利亞醫(yī)療保險協(xié)會證明在許多情況下全面審 查測試是很需要的 檢測電話錯誤 電話呼叫模式：呼叫目的地，持續(xù)時間，每天或 每周的次數(shù)。分析與預(yù)期標(biāo)準(zhǔn)相背離的模式 零售 分析家估計38%的零售

19、收縮緣于雇員的不誠實。,2020年7月7日星期二,Data Mining: Concepts and Techniques,19,2020年7月7日星期二,Data Mining: Concepts and Techniques,20,Knowledge Discovery (KDD) Process,Data miningcore of knowledge discovery process,Data Cleaning,Data Integration,Databases,Data Warehouse,Knowledge,Task-relevant Data,Selection,Data M

20、ining,Pattern Evaluation,2020年7月7日星期二,Data Mining: Concepts and Techniques,21,KDD Process: Several Key Steps,了解應(yīng)用領(lǐng)域： 相關(guān)的預(yù)備知識和應(yīng)用目標(biāo) 創(chuàng)建一個目標(biāo)數(shù)據(jù)集：數(shù)據(jù)選擇 數(shù)據(jù)清理和預(yù)加工（可能占用60%精力） 數(shù)據(jù)變換： 發(fā)現(xiàn)有用的特征，維/變量的變換， 常量的表示 選擇數(shù)據(jù)挖掘功能(任務(wù)） 匯總，分類，關(guān)聯(lián)，聚集 選擇挖掘算法 數(shù)據(jù)挖掘：搜索興趣模式 模式評估和知識表達 可視化，變形，去掉冗余模式等等 使用發(fā)現(xiàn)的知識,2020年7月7日星期二,Data Mining: Co

21、ncepts and Techniques,22,Data Mining and Business Intelligence,Increasing potential to support business decisions,End User,Business Analyst,Data Analyst,DBA,Decision Making,Data Presentation,Visualization Techniques,Data Mining,Information Discovery,Data Exploration,Statistical Summary, Querying, an

22、d Reporting,Data Preprocessing/Integration, Data Warehouses,Data Sources,Paper, Files, Web documents, Scientific experiments, Database Systems,2020年7月7日星期二,Data Mining: Concepts and Techniques,23,2020年7月7日星期二,Data Mining: Concepts and Techniques,24,Architecture: Typical Data Mining System,2020年7月7日星

23、期二,Data Mining: Concepts and Techniques,25,2020年7月7日星期二,Data Mining: Concepts and Techniques,26,Data Mining: Confluence of Multiple Disciplines,2020年7月7日星期二,Data Mining: Concepts and Techniques,27,2020年7月7日星期二,Data Mining: Concepts and Techniques,28,Why Not Traditional Data Analysis?,Tremendous amou

24、nt of data Algorithms must be highly scalable to handle such as tera-bytes of data High-dimensionality of data Micro-array may have tens of thousands of dimensions High complexity of data Data streams and sensor data Time-series data, temporal data, sequence data Structure data, graphs, social netwo

25、rks and multi-linked data Heterogeneous databases and legacy databases Spatial, spatiotemporal, multimedia, text and Web data Software programs, scientific simulations New and sophisticated applications,2020年7月7日星期二,Data Mining: Concepts and Techniques,29,Data Mining: On What Kinds of Data?,Database

26、-oriented data sets and applications Relational database, data warehouse, transactional database Advanced data sets and advanced applications Data streams and sensor data Time-series data, temporal data, sequence data (incl. bio-sequences) Structure data, graphs, social networks and multi-linked dat

27、a Object-relational databases Heterogeneous databases and legacy databases Spatial data and spatiotemporal data Multimedia database Text databases The World-Wide Web,2020年7月7日星期二,Data Mining: Concepts and Techniques,30,2020年7月7日星期二,Data Mining: Concepts and Techniques,31,2020年7月7日星期二,Data Mining: Co

28、ncepts and Techniques,32,2020年7月7日星期二,Data Mining: Concepts and Techniques,33,Ex: Time Series Analysis,Example: Stock Market Predict future values Determine similar patterns over time Classify behavior,2020年7月7日星期二,Data Mining: Concepts and Techniques,34,Multi-Dimensional View of Data Mining,Data to

29、 be mined Relational, data warehouse, transactional, stream, object-oriented/relational, active, spatial, time-series, text, multi-media, heterogeneous, legacy, WWW Knowledge to be mined Characterization, discrimination, association, classification, clustering, trend/deviation, outlier analysis, etc

30、. Multiple/integrated functions and mining at multiple levels Techniques utilized Database-oriented, data warehouse (OLAP), machine learning, statistics, visualization, etc. Applications adapted Retail, telecommunication, banking, fraud analysis, bio-data mining, stock market analysis, text mining,

31、Web mining, etc.,2020年7月7日星期二,Data Mining: Concepts and Techniques,35,Data Mining: Classification Schemes,General functionality Descriptive data mining Predictive data mining Different views lead to different classifications Data view: Kinds of data to be mined Knowledge view: Kinds of knowledge to

32、be discovered Method view: Kinds of techniques utilized Application view: Kinds of applications adapted,2020年7月7日星期二,Data Mining: Concepts and Techniques,36,Data Mining Models and Tasks,預(yù)測型模型對數(shù)據(jù)的值進行預(yù)測。 預(yù)測模型建模可能是基于使用其他的歷史數(shù)據(jù)。 描述型模型對數(shù)據(jù)中的模式或關(guān)系進行辨識。與預(yù)測行型模型不同， 描述型模型提供了一種探索被分析數(shù)據(jù)的性質(zhì)的方法， 而不是預(yù)測新的性質(zhì)。,2020年7月7日

33、星期二,Data Mining: Concepts and Techniques,37,Are All the “Discovered” Patterns Interesting?,Data mining may generate thousands of patterns: Not all of them are interesting Suggested approach: Human-centered, query-based, focused mining Interestingness measures A pattern is interesting if it is easily

34、 understood by humans, valid on new or test data with some degree of certainty, potentially useful, novel, or validates some hypothesis that a user seeks to confirm Objective vs. subjective interestingness measures Objective: based on statistics and structures of patterns, e.g., support, confidence,

35、 etc. Subjective: based on users belief in the data, e.g., unexpectedness, novelty, actionability, etc.,2020年7月7日星期二,Data Mining: Concepts and Techniques,38,Find All and Only Interesting Patterns?,Find all the interesting patterns: Completeness Can a data mining system find all the interesting patte

36、rns? Do we need to find all of the interesting patterns? Heuristic vs. exhaustive search Association vs. classification vs. clustering Search for only interesting patterns: An optimization problem Can a data mining system find only the interesting patterns? Approaches First general all the patterns

37、and then filter out the uninteresting ones Generate only the interesting patternsmining query optimization,2020年7月7日星期二,Data Mining: Concepts and Techniques,39,Why Data Mining Query Language?,Automated vs. query-driven? Finding all the patterns autonomously in a database?unrealistic because the patt

38、erns could be too many but uninteresting Data mining should be an interactive process User directs what to be mined Users must be provided with a set of primitives to be used to communicate with the data mining system Incorporating these primitives in a data mining query language More flexible user

39、interaction Foundation for design of graphical user interface Standardization of data mining industry and practice,2020年7月7日星期二,Data Mining: Concepts and Techniques,40,DMQLA Data Mining Query Language,Motivation A DMQL can provide the ability to support ad-hoc and interactive data mining By providin

40、g a standardized language like SQL Hope to achieve a similar effect like that SQL has on relational database Foundation for system development and evolution Facilitate information exchange, technology transfer, commercialization and wide acceptance Design DMQL is designed with the primitives describ

41、ed earlier,2020年7月7日星期二,Data Mining: Concepts and Techniques,41,Primitives that Define a Data Mining Task,Task-relevant data Type of knowledge to be mined Background knowledge Pattern interestingness measurements Visualization/presentation of discovered patterns,2020年7月7日星期二,Data Mining: Concepts an

42、d Techniques,42,Major Issues in Data Mining,Mining methodology Mining different kinds of knowledge from diverse data types, e.g., bio, stream, Web Performance: efficiency, effectiveness, and scalability Pattern evaluation: the interestingness problem Incorporation of background knowledge Handling noise and incomplete data Parallel,