数据挖掘-概念与技术：Lecture 1-引言

1、11 八月 2022Data Mining: Concepts and Techniques1数据挖掘: 概念与技术11 八月 2022Data Mining: Concepts and Techniques2课时安排及成绩评定总学时：40学时，其中：理论课时：24学时实验课时：16学时最终成绩由三部分构成，其中：笔试成绩：70%平时成绩：20%实验成绩：10%11 八月 2022Data Mining: Concepts and Techniques3内容安排引言数据预处理数据仓库数据挖掘频繁模式及关联挖掘有监督学习分类和预测无监督学习聚类分析社会网络分析（SNA）链接分析影响最大化11 八

2、月 2022Data Mining: Concepts and Techniques4Lecture 1. 引言什么是数据挖掘?为什么需要数据挖掘?数据挖掘: 能对什么样的数据进行挖掘?如何挖掘数据挖掘的功能分类模式评价所有模式都是有趣的吗?10大数据挖掘算法相关资源11 八月 2022Data Mining: Concepts and Techniques5什么是数据挖掘?数据挖掘 Data Mining 从海量数据中提取有兴趣的模式或知识Mining Knowledge from Data 数据库中的知识发现（Knowledge Discovery in Databases)关联学科机器学

3、习（ Machine Learning、AI派）模式识别（Pattern Recognition、CV派）11 八月 2022Data Mining: Concepts and Techniques6Lecture 1. 引言什么是数据挖掘?为什么需要数据挖掘?数据挖掘: 能对什么样的数据进行挖掘?如何挖掘数据挖掘的功能分类模式评价所有模式都是有趣的吗?10大数据挖掘算法相关资源11 八月 2022Data Mining: Concepts and Techniques7Why需求是发明之母数据爆炸问题 数据自动获取与数据库技术的不断发展，导致了数据呈指数级增长。BKB MB GB TB PB

4、 ZB一些大数据科学研究以欧洲核子中心的大型强子对撞机LHC(the Large Hadron Collider)为例, LHC上的4个主要实验每秒钟采集到的数据达到PB(1 PB=106 GB)级.新一代北京正负电子对撞机(BEPCII) 的实验探测器北京谱仪自 2008年运行以来, BESIII实验已经积累了超过5PB的数据（截至到2015）。 因此未来几年中, BESIII的数据规模将达到10 PB以上.深圳华大基因是世界上最大的基因测序机构,其每天进行的基因测序相当2000个人基因, 产生的数据超过6 TB （截至到2015）.11 八月 2022Data Mining: Concep

5、ts and Techniques8一些大数据社交网络Facebook:（2010）用户每天登录数据130TB； 每天上传的图片数据200-400TB/day（8300万张）；超过400亿张照片；11 八月 2022Data Mining: Concepts and Techniques9企业用户数企业用户数Facebook13亿新浪微博5.6亿Twitter62亿阿里巴巴5亿Amazon月活跃2.37亿腾讯网8亿活跃一些大数据搜索引擎 Google每天处理的数据量大于 25 PB(2010).百度每天处理的数据量将近100个PB，1PB就等于100万个G，相当于5000个国家图书馆的信息量的

6、总和(2013).商务Walmart （2010）每小时处理客户事务100万以上；有关 客户的数据大于2.5 PB。11 八月 2022Data Mining: Concepts and Techniques1011 八月 2022Data Mining: Concepts and Techniques11数据库技术的演化过程1960s:数据收集, 数据库创建等1970s: 关系数据模型（Relational data model）, 关系数据库的实现1980s: 关系数据库管理系统（RDBMS）, 高级数据模型面向应用的数据库管理系统(spatial, scientific, enginee

7、ring, etc.)1990s: 数据挖掘, 构造数据仓库, 多媒体数据库, Web数据库2000s流数据管理与挖掘Web技术与全球信息系统 我们处于数据丰富而知识贫乏的尴尬境地（Drowning in data, but starving for knowledge）! 解决方案: 数据仓库、数据挖掘、大规模分布式处理数据仓库与联机分析处理从大型数据库中挖掘感兴趣的知识Hadoop、Spark11 八月 2022Data Mining: Concepts and Techniques1211 八月 2022Data Mining: Concepts and Techniques13知识发现

8、的主要过程数据挖掘知识发现的核心Data CleaningData IntegrationDatabasesData WarehouseKnowledgeTask-relevant DataSelectionData MiningPattern Evaluation11 八月 2022Data Mining: Concepts and Techniques14创建目标数据集：数据选择数据预处理：数据清洗、数据约简与数据变换构建数据仓库（可选）数据挖掘模式评价与知识表示知识的使用知识发现的主要过程11 八月 2022Data Mining: Concepts and Techniques15数据

9、挖掘与商务智能 Increasing potentialto supportbusiness decisionsEnd UserBusiness Analyst DataAnalystDBA MakingDecisionsData PresentationVisualization TechniquesData MiningInformation DiscoveryData ExplorationOLAP, MDAStatistical Analysis, Querying and ReportingData Warehouses / Data MartsData SourcesPaper,

10、Files, Information Providers, Database Systems, OLTP11 八月 2022Data Mining: Concepts and Techniques16Lecture 1. 引言什么是数据挖掘?为什么需要数据挖掘?数据挖掘: 能对什么样的数据进行挖掘?如何挖掘数据挖掘的功能分类模式评价所有模式都是有趣的吗?10大数据挖掘算法相关资源11 八月 2022Data Mining: Concepts and Techniques17数据挖掘：针对什么样的数据?关系数据库（Relational database）数据仓库（Data warehouse）事

11、务数据库（Transactional database）高级数据库空间数据库（Spatial data）时间序列数据（Time-series data ）多媒体数据库（Multimedia database）文本数据库与WWW（Text databases & WWW）11 八月 2022Data Mining: Concepts and Techniques18Lecture 1. 引言什么是数据挖掘?为什么需要数据挖掘?数据挖掘: 能对什么样的数据进行挖掘?如何挖掘数据挖掘的功能分类模式评价所有模式都是有趣的吗?10大数据挖掘算法相关资源11 八月 2022Data Mining: Con

12、cepts and Techniques19数据挖掘功能 I概念描述: 特征化与区分(Characterization and discrimination)概化(Generalize), 摘要(summarize), 及对比数据特征等分类与预测（Classification and Prediction ）对类或者概念构造模型或函数以便对未来数据进行预测表示: 决策树, 分类规则, 神经网络，支持向量机、深度学习等对未知数据或遗失数据进行预测 关联 (相关性或因果关系，correlation and causality)Diaper Beer 0.5%, 75%11 八月 2022Data

13、Mining: Concepts and Techniques20数据挖掘功能 II聚类分析类标识符是未知的: 把数据分成不同的新类使得同一类中的元素具有极大的相似性，不同类元素的相似性极小趋势与演化分析趋势与偏差分析序列模式挖掘基于相似性的分析孤立点分析孤立点: 不符合该类数据的通用行为的数据不是噪声或异常葡萄酒的故事回归分析奥利(Orley Ashenfelter).普林斯顿大学的一位数量经济学家，提出了如下公式葡萄酒的品质= 12.145+0.0017冬天降雨量+0.0614 葡萄生长期平均气温-0.00386 收割季节降雨量。葡萄酒爱好者(The Wine Advocate)杂志最有影

14、响力的作家罗伯特帕克说奥利是一个“彻头彻尾的骗子”、“如果他邀请我去他家喝酒，我会感到恶心。”在酒放在木桶紧紧三个月之后、还从未被品酒师品尝过，奥利预测1989年波尔多葡萄酒将是“世纪佳酿”，稍后又预测1990年的将会更好。事实证明奥利是对的，此后传统的品酒专家们虽然从未公开承认奥利的预测，但他们自己的预测越来越与那个公式连接在一起。11 八月 2022Data Mining: Concepts and Techniques21葡萄酒的故事回归分析11 八月 2022Data Mining: Concepts and Techniques22“和过去不同的是，品酒师们不再犯严重的错误了。坦率地

15、说，我有点儿自绝前程，我不再有任何附加值了。”奥利11 八月 2022Data Mining: Concepts and Techniques23应用领域关联规则挖掘购物篮分析: 沃尔玛公司“尿布与啤酒”的故事。应用领域聚类分析11 八月 2022Data Mining: Concepts and Techniques24应用领域序列预测美国折扣零售商（Target）与怀孕预测：公司发现怀孕第三个月会买什么、再在什么时间段会买什么等。11 八月 2022Data Mining: Concepts and Techniques25应用领域热点探测2009流感（H1N1）预测：官方做流行病学调查再

16、通告通常会有1至2两周的延迟。谷歌利用用户输入的查询进行分析（特定检索词条的使用频率与流感在时间和空间上的传播之间的关系等）提前几周做出了预测（包括时间、地点，发表在Nature杂志），且与官方的相关性达到97%11 八月 2022Data Mining: Concepts and Techniques26数学基础确定性派数学规划凸规划：线性规划、半正定规划非凸规划组合优化：图论不确定性派（贝叶斯派）概率论、数理统计、随机过程11 八月 2022Data Mining: Concepts and Techniques2711 八月 2022Data Mining: Concepts and T

17、echniques28Lecture 1. 引言什么是数据挖掘?为什么需要数据挖掘?数据挖掘: 能对什么样的数据进行挖掘?如何挖掘数据挖掘的功能分类模式评价所有模式都是有趣的吗?10大数据挖掘算法相关资源11 八月 2022Data Mining: Concepts and Techniques29所有发现的模式都是感兴趣的吗?数据挖掘能产生成千上万的模式，而它们并非都是令人感兴趣的。兴趣度度量一个模式是有趣的，如果它是：易理解的, 在一定程度上对新数据或测试数据是有效的, 可能有用的, 新颖的, 或者验证了用户正在确证的某一个假设主观与客观兴趣度度量客观的: 基于统计或模式的结构, 如支持度

18、, 可信度等.主观的: 基于用户的观点, 如期望之中的，新颖的，等等.11 八月 2022Data Mining: Concepts and Techniques30Lecture 1. 引言什么是数据挖掘?为什么需要数据挖掘?数据挖掘: 能对什么样的数据进行挖掘?如何挖掘数据挖掘的功能分类模式评价所有模式都是有趣的吗?10大数据挖掘算法相关资源11 八月 2022Data Mining: Concepts and Techniques31十大挖掘算法Wu X., Kumar V,Quinlan R.,Ghosh J.,Yang Q.,Motoda H.,McLachlan G.J.,Ng A

19、.,Liu B.,Yu S.,Zhou Z.,Steinbach M.,Hand D.J.Steinberg D. Top 10 algorithms in data mining. Knowledge Information System (2008) 14:137.11 八月 2022Data Mining: Concepts and Techniques32Top-10 Most Popular DM Algorithms:18 Identified Candidates (I) Classification#1. C4.5: Quinlan, J. R. C4.5: Programs

20、for Machine Learning. Morgan Kaufmann., 1993.#2. CART: 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. Nai

21、ve Bayes Hand, D.J., Yu, K., 2001. Idiots Bayes: Not So 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 Y

22、ork. Association Analysis#7. Apriori: Rakesh Agrawal and 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.11 八月 2022Data Mining: Concepts and Techniques3

23、3The 18 Identified Candidates (II)Link Mining#9. PageRank: Brin, S. and Page, L. 1998. The anatomy of 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.,

24、 Some methods for classification and analysis of multivariate observations, in Proc. 5th Berkeley Symp. 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

25、 and Boosting#13. AdaBoost: Freund, Y. and Schapire, R. E. 1997. A decision-theoretic generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci. 55, 1 (Aug. 1997), 119-139.11 八月 2022Data Mining: Concepts and Techniques34The 18 Identified Candidates (III)Sequential Patte

26、rns#14. GSP: Srikant, R. and Agrawal, R. 1996. Mining Sequential Patterns: Generalizations and Performance Improvements. In Proceedings of the 5th International Conference on Extending Database Technology, 1996.#15. PrefixSpan: J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal and M-C. H

27、su. PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth. In ICDE 01.Integrated Mining#16. CBA: Liu, B., Hsu, W. and Ma, Y. M. Integrating classification and association rule mining. KDD-98. Rough Sets#17. Finding reduct: Zdzislaw Pawlak, Rough Sets: Theoretical Aspe

28、cts of Reasoning about Data, Kluwer Academic Publishers, Norwell, MA, 1992Graph Mining#18. gSpan: Yan, X. and Han, J. 2002. gSpan: Graph-Based Substructure Pattern Mining. In ICDM 02.11 八月 2022Data Mining: Concepts and Techniques35Top-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)Deep