数据挖掘导论(第一讲)

1、数据挖掘概念与技术孙翀 2014.02qq:第一讲. 引言 动机: 为何要进行数据挖掘？ 什么是数据挖掘? Data Mining: 挖什么？ 数据挖掘功能性 数据挖掘系统的分类 排名前十的数据挖掘算法 数据挖掘领域的主要问题 课程概述为何要数据挖掘？数据的爆炸增长: from Terabytes to Petabytes数据收集和数据可用性自动化数据收集工具, 数据库系统, 网络, 电脑化社会产生大量数据的主要来源商业领域:网络,电子商务, 交易, 股票, 科学领域: 遥感, 生物信息, 科学模拟, 社交和个人: 信息, 数码照片,微博每个人都是数据源！ We are drowning in

2、 data, but starving for knowledge! 现状：穷的只剩下数据了！“需求是发明她老娘”-数据挖掘应运而生-大规模数据集上进行数据分析科学史1600之前，实证科学1600-1950s,理论科学每个学科产生一个理论组件. 理论模型指导实验并且对我们的理解进行概括。1950s-1990s, 计算科学后50年, 大多数学科都产生第三个组件，计算分支 (e.g. 实证, 理论,和计算生态学；物理学；语言学.)计算科学传统上意味着模拟。模拟是因为我们无法找到复杂数学模型封闭形式下的解而应运而生的。 1990-now,数据科学科学仪器和模拟所产生的数据洪流存储和管理线上数据的代价

3、internet网和计算网格使得所有的归档数据全局可访问科学的信息。管理，采集，组织，查询和可视化任务的规模几乎呈线性数据量。. 数据挖掘面临新的挑战！Jim Gray and Alex Szalay, The World Wide Telescope: An Archetype for Online Science, Comm. ACM, 45(11): 50-54, Nov. 2002 数据库技术演化1960s:数据收集, 数据库建立, 信息管理系统和网络数据库管理系统IMS and network DBMS1970s: 关系数据模型,关系数据库管理系统实现1980s: 关系型数据库，高级

4、数据模型（扩展关系模型，面向对象模型，演绎数据库等）基于应用的数据库管理系统(空间数据,科学数据,工程数据, etc.)1990s: 数据挖掘, 数据仓库, 多媒体数据库, 网络数据库2000s流数据管理和挖掘数据挖掘和应用Web技术 (XML, 数据集成)和全局信息系统（包含各种数据类型的系统） 数据挖掘是个啥？ 数据挖掘 (从数据中挖掘知识) 从大量数据中抽取感兴趣的（非平凡的，隐含的，先前未知的，潜在有用的）模式或者知识数据挖掘：是否名不副实？ 数据挖掘的别名数据库中的知识发现(KDD), 知识抽取（knowledge extraction）, 数据/模式分析（data/pattern

5、analysis）, 数据考古（data archeology）,数据疏通（ data dredging）, 信息丰收（information harvesting）,商业智能（ business intelligence）, etc. 注意：是不是啥都是数据挖掘？ 简单搜索和查询处理 （演绎）专家系统知识发现过程数据挖掘是知识发现的核心过程Data CleaningData IntegrationDatabasesData WarehouseTask-relevant DataSelectionData MiningPattern Evaluation知识发现过程（2） 数据清理：消除噪音或

6、不一致数据 数据集成：多种数据源可以组合在一起（如异构数据库） 数据选择：从数据库中提取与分析任务相关的数据 数据变换：数据变换或统一成适合挖掘的形式；如，通过汇总或聚集操作 数据挖掘：基本步骤，使用智能方法提取有趣的模式 模式评估：根据兴趣度度量，识别提供知识的有趣模式 知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识典型的数据挖掘系统Data Mining and Business Intelligence 业务决策的增长潜力业务决策的增长潜力最终用户最终用户业务分析业务分析 数据分析数据分析DBA决策决策数据展示数据展示可视化技术可视化技术数据挖掘数据挖掘信息发现信息发现数据探索

7、数据探索统计摘要，统计摘要， 查询和报查询和报告告数据预处理和基础数据预处理和基础,数据仓库数据仓库数据源数据源纸质文档纸质文档, 文件文件, Web 文档文档, 科学实验科学实验, 数据库系统数据库系统数据挖掘是多学科的交汇数据挖掘数据挖掘数据库技术统计学机器学习模式识别算法其他学科可视化技术为何不适用传统的数据分析方法？超大数据量算法必须具有高度的可扩展性，以处理诸如万亿字节的数据数据的高纬度微阵列可能具有成千上万的维（dna微阵列）数据的高复杂性数据流和传感器数据时间序列数据,时态数据, 序列数据 结构化数据,图, 社交网络和多联数据异构数据库 和 遗产数据库空间, 时空,多媒体,文本和

8、web数据软件程序,科学模拟新兴复杂应用数据挖掘的方方面面被挖掘的数据关系的，数据仓库，事务的，数据流类型，面向对象和对象关系的，活动的，空间的，时序的，文本的，多媒体的，异构的，历史的，www挖掘出的知识特征, 区别, 关联，分类, 聚类, 趋势/偏差, 异常值分析等.在多个层次上的多个（集成）的函数所利用的技术数据库相关技术, 数据仓库(OLAP), 机器学习, 统计, 可视化,等.适合的应用零售业, 电信业, 银行业,欺诈分析, 生物数据挖掘, 股票系统分析, 文本挖掘, Web 挖掘等.数据挖掘的分类 根据通用功能来分类描述性数据挖掘 Descriptive data mining 预

9、测性数据挖掘 Predictive data mining 不同的视角也导致不同的分类被挖掘数据视角知识视角方法视角应用视角数据挖掘的功能性质多维概念描述:特征化和区分概况, 总结, 和比较数据特征,例如：干和湿的区域频繁模式, 关联（相关性与因果关系）尿布 啤酒 0.5%, 75% (相关性还是因果干系)分类和预测 构建用于描述和区分类和概念的模型，该模型用于未来预测例如 根据气候来分类国家 以及根据油耗来分类汽车预测某些未知的或者缺失的数值（连续性）数据挖掘的功能性质(2)聚类分析类标签未知:分组数据形成新类, 例如聚类房子来找到分布模式最大化类内相似性 & 最小化类间相似性异常点分析异常

10、点: 不符合大部分数据行为的数据对象噪点或异常? 在欺诈检测和稀有事件分析中很有用趋势和演变分析趋势和偏差:例如回归分析序列模式挖掘: e.g., digital camera large SD memory周期性分析基于相似性的分析其他模式指导的或统计分析Top-10 Most Popular DM Algorithms:18 Identified Candidates (I) Classification#1. C4.5: Quinlan, J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann., 1993.#2. CART:

11、 L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Wadsworth, 1984.#3. K Nearest Neighbours (kNN): Hastie, T. and Tibshirani, R. 1996. Discriminant Adaptive Nearest Neighbor Classification. TPAMI. 18(6)#4. Naive Bayes Hand, D.J., Yu, K., 2001. Idiots Bayes: Not S

12、o Stupid After All? Internat. Statist. Rev. 69, 385-398.Statistical Learning#5. SVM: Vapnik, V. N. 1995. The Nature of Statistical Learning Theory. Springer-Verlag. #6. EM: McLachlan, G. and Peel, D. (2000). Finite Mixture Models. J. Wiley, New York. Association Analysis#7. Apriori: Rakesh Agrawal a

13、nd Ramakrishnan Srikant. Fast Algorithms for Mining Association Rules. In VLDB 94.#8. FP-Tree: Han, J., Pei, J., and Yin, Y. 2000. Mining frequent patterns without candidate generation. In SIGMOD 00.The 18 Identified Candidates (II)Link Mining#9. PageRank: Brin, S. and Page, L. 1998. The anatomy of

14、a large-scale hypertextual Web search engine. In WWW-7, 1998.#10. HITS: Kleinberg, J. M. 1998. Authoritative sources in a hyperlinked environment. SODA, 1998.Clustering#11. K-Means: MacQueen, J. B., Some methods for classification and analysis of multivariate observations, in Proc. 5th Berkeley Symp

15、. Mathematical Statistics and Probability, 1967.#12. BIRCH: Zhang, T., Ramakrishnan, R., and Livny, M. 1996. BIRCH: an efficient data clustering method for very large databases. In SIGMOD 96.Bagging and Boosting#13. AdaBoost: Freund, Y. and Schapire, R. E. 1997. A decision-theoretic generalization o

16、f on-line learning and an application to boosting. J. Comput. Syst. Sci. 55, 1 (Aug. 1997), 119-139.The 18 Identified Candidates (III)Sequential Patterns#14. GSP: Srikant, R. and Agrawal, R. 1996. Mining Sequential Patterns: Generalizations and Performance Improvements. In Proceedings of the 5th Int

17、ernational Conference on Extending Database Technology, 1996.#15. PrefixSpan: J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal and M-C. Hsu. PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth. In ICDE 01.Integrated Mining#16. CBA: Liu, B., Hsu, W. and

18、Ma, Y. M. Integrating classification and association rule mining. KDD-98. Rough Sets#17. Finding reduct: Zdzislaw Pawlak, Rough Sets: Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Norwell, MA, 1992Graph Mining#18. gSpan: Yan, X. and Han, J. 2002. gSpan: Graph-Based Substru

19、cture Pattern Mining. In ICDM 02.Top-10 Algorithm Finally Selected at ICDM06 #1: C4.5 (61 votes) #2: K-Means (60 votes) #3: SVM (58 votes) #4: Apriori (52 votes) #5: EM (48 votes) #6: PageRank (46 votes) #7: AdaBoost (45 votes) #7: kNN (45 votes) #7: Naive Bayes (45 votes) #10: CART (34 votes)Major

20、Issues in Data Mining挖掘方法从多种数据类型中挖掘不同的知识从多种数据类型中挖掘不同的知识, 如如., bio, stream, Web性能性能:效率效率 efficiency, 有效性有效性 effectiveness, 可扩展性可扩展性scalability模式评估模式评估: 兴趣点问题兴趣点问题合并背景知识合并背景知识处理噪点和不完整数据处理噪点和不完整数据并行的，分布式的，增量的挖掘算法并行的，分布式的，增量的挖掘算法新发现知识和已有知识的集成新发现知识和已有知识的集成:知识融合知识融合knowledge fusion 用户接口数据挖掘语言和临时挖掘数据挖掘语言和临

21、时挖掘数据挖掘结果的表达和可视化数据挖掘结果的表达和可视化在多个抽象级别交互的挖掘知识在多个抽象级别交互的挖掘知识应用和社会影响特定领域的数据挖掘特定领域的数据挖掘 & invisible data mining数据安全性，完整性和保密性的保护数据安全性，完整性和保密性的保护A Brief History of Data Mining Society1989 IJCAI Workshop on Knowledge Discovery in Databases Knowledge Discovery in Databases (G. Piatetsky-Shapiro and W. Frawle

22、y, 1991)1991-1994 Workshops on Knowledge Discovery in DatabasesAdvances in Knowledge Discovery and Data Mining (U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, 1996)1995-1998 International Conferences on Knowledge Discovery in Databases and Data Mining (KDD95-98)Journal of Data Mining

23、and Knowledge Discovery (1997)ACM SIGKDD conferences since 1998 and SIGKDD ExplorationsMore conferences on data miningPAKDD (1997), PKDD (1997), SIAM-Data Mining (2001), (IEEE) ICDM (2001), etc.ACM Transactions on KDD starting in 2007Conferences and Journals on Data MiningKDD ConferencesACM SIGKDD I

24、nt. Conf. on Knowledge Discovery in Databases and Data Mining (KDD)SIAM Data Mining Conf. (SDM)(IEEE) Int. Conf. on Data Mining (ICDM)Conf. on Principles and practices of Knowledge Discovery and Data Mining (PKDD)Pacific-Asia Conf. on Knowledge Discovery and Data Mining (PAKDD) Other related confere

25、ncesACM SIGMODVLDB(IEEE) ICDEWWW, SIGIRICML, CVPR, NIPS Journals Data Mining and Knowledge Discovery (DAMI or DMKD)IEEE Trans. On Knowledge and Data Eng. (TKDE)KDD ExplorationsACM Trans. on KDDWhere to Find References? DBLP, CiteSeer, GoogleData mining and KDD (SIGKDD: CDROM)Conferences: ACM-SIGKDD,

26、 IEEE-ICDM, SIAM-DM, PKDD, PAKDD, etc.Journal: Data Mining and Knowledge Discovery, KDD Explorations, ACM TKDDDatabase systems (SIGMOD: ACM SIGMOD AnthologyCD ROM)Conferences: ACM-SIGMOD, ACM-PODS, VLDB, IEEE-ICDE, EDBT, ICDT, DASFAAJournals: IEEE-TKDE, ACM-TODS/TOIS, JIIS, J. ACM, VLDB J., Info. Sy

27、s., etc.AI & Machine LearningConferences: Machine learning (ML), AAAI, IJCAI, COLT (Learning Theory), CVPR, NIPS, etc.Journals: Machine Learning, Artificial Intelligence, Knowledge and Information Systems, IEEE-PAMI, etc.Web and IR Conferences: SIGIR, WWW, CIKM, etc.Journals: WWW: Internet and Web I

28、nformation Systems, StatisticsConferences: Joint Stat. Meeting, etc.Journals: Annals of statistics, etc.VisualizationConference proceedings: CHI, ACM-SIGGraph, etc.Journals: IEEE Trans. visualization and computer graphics, etc.Recommended Reference BooksS. Chakrabarti. Mining the Web: Statistical An

29、alysis of Hypertex and Semi-Structured Data. Morgan Kaufmann, 2002R. O. Duda, P. E. Hart, and D. G. Stork, Pattern Classification, 2ed., Wiley-Interscience, 2000T. Dasu and T. Johnson. Exploratory Data Mining and Data Cleaning. John Wiley & Sons, 2003U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and

30、 R. Uthurusamy. Advances in Knowledge Discovery and Data Mining. AAAI/MIT Press, 1996U. Fayyad, G. Grinstein, and A. Wierse, Information Visualization in Data Mining and Knowledge Discovery, Morgan Kaufmann, 2001J. Han and M. Kamber. Data Mining: Concepts and Techniques. Morgan Kaufmann, 2nd ed., 20

31、06D. J. Hand, H. Mannila, and P. Smyth, Principles of Data Mining, MIT Press, 2001T. Hastie, R. Tibshirani, and J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Springer-Verlag, 2001B. Liu, Web Data Mining, Springer 2006.T. M. Mitchell, Machine Learning, McG

32、raw Hill, 1997G. Piatetsky-Shapiro and W. J. Frawley. Knowledge Discovery in Databases. AAAI/MIT Press, 1991P.-N. Tan, M. Steinbach and V. Kumar, Introduction to Data Mining, Wiley, 2005S. M. Weiss and N. Indurkhya, Predictive Data Mining, Morgan Kaufmann, 1998I. H. Witten and E. Frank, Data Mining:

33、 Practical Machine Learning Tools and Techniques with Java Implementations, Morgan Kaufmann, 2nd ed. 2005Summary数据挖掘:从大量数据中发现有趣的模式 数据库技术的自然进化, 在大量应用中有着广泛的需求一个知识发现过程包含下列步骤：数据清理, 数据集成, 数据选择, 数据变换, 数据挖掘, 模式评估, 知识展示挖掘可以在各种信息存储库中进行，挖掘数据源的多样性。数据挖掘的功能和可发现的模式类型: 特征化characterization, 区分discrimination, 频繁模式fr

34、equent pattern，关联分析association, 分类和预测classification and prediction,聚类clustering, 离群点和趋势分析outlier and trend analysis, etc.数据挖掘系统和体系结构数据挖掘领域的主要研究问题本课程要讲的东东 引言（1） 数据预处理（2） 数据仓库与OLAP技术概述（1） 挖掘频繁模式、关联和相关（2） 分类和预测（2） 聚类分析（2） 常用挖掘工具介绍（1） 数据挖掘的应用和发展趋势(1)补充概念 关系数据库 case study例1.1 AllElectronics公司.customer,it

35、em,employee和branch表续数据仓库AllElectronics跨国公司，分部遍布全世界，每个分部有自己的一组数据。总裁要你提供公司第三季度每种商品、每个分部的销售分析。数据仓库（多维数据立方体） 数据仓库：从多个数据源收集的信息存储库，用多维数据库结构建模，多维数据立方体 维：每个维对应模式中一个或一组属性 单元：存放某种聚集度量值，count或sales_amount 上卷和下钻多维数据立方体（例）例 1.2 AllElectronics 的汇总销售数据数据方在图 1.8(a)中。该数据方有三个维：address（城市值），time（季度值 Q1, Q2, Q3, Q4）和 i

36、tem（商品类型值：家庭娱乐、计算机、电话、安全）。存放在方体的每个单元中的聚集值是 sales_amount（单位：$1000）。事务数据库 事务数据库：由一个文件组成，其中每个记录代表一个事务。通常，一个事务包含一个唯一的事务标识号(trans_ID)，和一个组成事务的项的列表（如，在商店购买的商品）。事务可以存放在表中，每个事务一个记录。AllElectronics 的事务数据库的片段在图 1.9中给出。从关系数据库的观点，图 1.9 的销售表是一个嵌套的关系，因为属性”list of item_ID”包含 item的集合。由于大部分关系数据库系统不支持嵌套关系结构，事务数据库通常存放在

37、一个类似于图 1.9中的表格式的展平的文件中。Q1: sam smith买了哪些物品？Q2: I3卖了了多少件？Q3: 哪些物品适合放在一起购买？概念/类描述：特征和区分 数据特征是目标类数据的一般特征或特性的汇总。数据特征的输出可以用多种形式提供。包括饼图、条图、曲线、多维数据方和包括交叉表在内的多维表。例如：数据挖掘系统应当能够产生一年之内在AllElectronics花费$1000以上的顾客汇总特征的描述。结果可能是顾客的一般轮廓，如年龄在 40-50、有工作、有很好的信誉度。系统将允许用户在任意维下钻，如在 occupation 下钻，以便根据他们的职业来观察这些顾客的职业。概念/类描

38、述：特征和区分（2） 数据区分是将目标类对象的一般特性与一个或多个对比类对象的一般特性比较。目标类和对比类由用户指定，而对应的数据通过数据库查询提取。例如：数据挖掘系统应当能够比较两组 AllElectronics 顾客，如定期（每月多于 2 次）购买计算机产品的顾客和偶尔（即，每年少于 3 次）购买这种产品的顾客。结果描述可能是一般的比较轮廓，如经常购买这种产品的顾客 80%在 20-40 岁之间，受过大学教育；而不经常购买这种产品的顾客 60%或者太老，或者太年青，没有大学学位。沿着维下钻，如沿 occupation 维，或添加新的维，income_level，可以帮助发现两类之间的更多区分特性。关联分析 关联分析：发现关联规则，这些规则展示属性-值频繁地在给定数据集中一起出现的条件。分类和预测 分类：它找描述或识别数据类或概念的模型(或函数)，以便能够使用模型预测类标号未知的对象。导出模型是基于对训练数据集（即，其类标号已知的数据对象）的分析。预测类标号 如何导出模型? 分类规则、判定树、数学公式或神经网络 预测：被预测值为非类标号而是数值数据，也包含可用数据的分布趋势识别。 相关分析：识别对于分类和预测无用的属性，将其排除。分类和预测（例）假定作为 AllElectronics 的销售经理，你想根据对销售活动的反映