数据挖掘-2015春季

1、数据库原理与应用Principles of Database Systems数据挖掘数据挖掘数据库原理与应用Principles of Database Systems 截止到截止到20122012年，数据量已经从年，数据量已经从TBTB（1024GB=1TB1024GB=1TB）级别）级别跃升到跃升到PBPB（1024TB=1PB1024TB=1PB）、）、EBEB（1024PB=1EB1024PB=1EB）乃至）乃至ZBZB(1024EB=1ZB)(1024EB=1ZB)级别。国际数据公司（级别。国际数据公司（IDCIDC）的研究结果表）的研究结果表明，明，20082008年全球产生的数据

2、量为年全球产生的数据量为0.49ZB0.49ZB，20092009年的数据量为年的数据量为0.8ZB0.8ZB，20102010年增长为年增长为1.2ZB1.2ZB，20112011年的数量更是高达年的数量更是高达1.82ZB1.82ZB，相当于全球每人产生，相当于全球每人产生200GB200GB以上的数据。而到以上的数据。而到20122012年为止，人类生产的所有印刷材料的数据量是年为止，人类生产的所有印刷材料的数据量是200PB200PB。IBMIBM的的研究称，研究称，整个人类文明所获得的全部数据中，有整个人类文明所获得的全部数据中，有90%90%是过去两年是过去两年内产生的。而到了内产

3、生的。而到了20202020年，全世界所产生的数据规模将达到今年，全世界所产生的数据规模将达到今天的天的4444倍。倍。大数据时代的来临大数据时代的来临数据库原理与应用Principles of Database Systems 除了数据量大之外，大数据时代的数据还呈现出其他三个特征除了数据量大之外，大数据时代的数据还呈现出其他三个特征: :第一个特征是第一个特征是数据类型繁多数据类型繁多。包括网络日志、音频、视频、图片、地。包括网络日志、音频、视频、图片、地理位置信息等等，多类型的数据对数据的处理能力提出了更高的要求。理位置信息等等，多类型的数据对数据的处理能力提出了更高的要求。 第二个特征

4、是第二个特征是数据价值密度相对较低数据价值密度相对较低。如随着物联网的广泛应用，信。如随着物联网的广泛应用，信息感知无处不在，信息海量，但价值密度较低，如何通过强大的机器算法息感知无处不在，信息海量，但价值密度较低，如何通过强大的机器算法更迅速地完成数据的价值更迅速地完成数据的价值“提纯提纯”，是大数据时代亟待解决的难题。，是大数据时代亟待解决的难题。 第三个特征是第三个特征是处理速度快，时效性要求高处理速度快，时效性要求高。这是大数据区分于传统数。这是大数据区分于传统数据挖掘最显著的特征。据挖掘最显著的特征。 既有的技术架构和路线，已经无法高效处理如此海量的数据。可以说，既有的技术架构和路线

5、，已经无法高效处理如此海量的数据。可以说，大数据时代对人类的数据驾驭能力提出了新的挑战，也为人们获得更为深大数据时代对人类的数据驾驭能力提出了新的挑战，也为人们获得更为深刻、全面的洞察能力提供了前所未有的空间与潜力。刻、全面的洞察能力提供了前所未有的空间与潜力。 数据库原理与应用Principles of Database Systems“大数据研究的科学价值大数据研究的科学价值” 2012年3月，美国奥巴马政府宣布投资2亿美元启动“大数据研究和发展计划”，这是继1993年美国宣布“信息高速公路”计划后的又一次重大科技发展部署。美国政府认为大数据是“未来的新石油”，将“大数据研究”上升为国家意

6、志，对未来的科技与经济发展必将带来深远影响。一个国家拥有数据的规模和运用数据的能力将成为综合国力的重要组成部分，对数据的占有和控制也将成为国家间和企业间新的争夺焦点。数据库原理与应用Principles of Database Systems数据科学(Data Science) l 图灵奖获得者图灵奖获得者Jim Gray:Jim Gray: 2007年最后一次演讲中提出“数据密集型科学发现(Data-Intensive Scientific Discovery)” 将成为科学研究的第四范式 实验科学 理论科学 计算科学 数据科学l世界著名存储技术公司世界著名存储技术公司EMCEMC：提出了“

7、Data Science”的概念，“Data Science teams will become the driving force for success with big data analytics” l 李国杰院士：李国杰院士：“数据科学”研究的对象是什么？计算机科学是关于算法的科学，数据科学是关于数据的科学。数据库原理与应用Principles of Database Systems基础设施系统平台算法应用大数据处理的技术、架构是什么？ 从信息处理系统视角看大数据处理数据库原理与应用Principles of Database Systems云计算资源与平台虚拟化弹性资源调度管理虚拟

8、资源池小粒度应用与服务分布式存储并行计算框架查询分析挖掘并行算法云安全管理云计算管理大数据应用与服务云计算应用与服务数据库原理与应用Principles of Database Systems从云计算的视角看大数据系统架构从云计算的视角看大数据系统架构数据库原理与应用Principles of Database Systems一、大数据存储管理和索引查询二、Hadoop性能优化和功能增强三、并行计算模型和框架四、并行化机器学习和数据挖掘算法五、社会网络分析六、Web信息搜索和排名推荐七、媒体分析检索八、基于本体的语义分析与挖掘九、大数据自然语言处理智能化应用十、大数据可视化计算与分析系统层基础

9、算法典型/共性应用算法与技术数据库原理与应用Principles of Database Systems大数据的挑战：数据的存储、分析处理。大数据的挑战：数据的存储、分析处理。 大数据分析的理论核心就是数据挖掘算法，各种数据挖掘的算法基于不同的数据类型和格式才能更加科学的呈现出数据本身具备的特点，也正是因为这些被全世界统计学家所公认的各种统计方法才能深入数据内部，挖掘出公认的价值。另外一个方面也是因为有这些数据挖掘的算法才能更快速的处理大数据，如果一个算法得花上好几年才能得出结论，那大数据的价值也就无从说起了。数据库原理与应用Principles of Database Systems曼联昔日

10、黄金组合成累赘曼联昔日黄金组合成累赘 一起首发欧冠胜率仅一起首发欧冠胜率仅20% 2014-02-26 10:39:22来源: 网易体育 费迪南德费迪南德和和维迪奇维迪奇这对中卫组合曾被誉为黄金组合。但事实这对中卫组合曾被誉为黄金组合。但事实上，从上，从2011年年8月到现在，两人在欧冠一起首发，月到现在，两人在欧冠一起首发，曼联曼联胜率只有胜率只有20%，输球率达到了，输球率达到了60%。 费迪南德和维迪奇自费迪南德和维迪奇自2011年年8月以来在欧冠只一起首发过月以来在欧冠只一起首发过5次，次，曼联成绩是曼联成绩是1胜胜1平平3负。两人一起首发少有伤病的因素，让两人一负。两人一起首发少有伤

11、病的因素，让两人一起首发，两人老迈的问题是起首发，两人老迈的问题是1+12。所以尽管。所以尽管埃文斯埃文斯、斯莫林斯莫林等等年轻中卫表现也不怎么靠谱，但年轻中卫表现也不怎么靠谱，但弗格森弗格森和和莫耶斯莫耶斯还都是尽量使用还都是尽量使用老少配的中卫组合。老少配的中卫组合。 数据库原理与应用Principles of Database Systems何谓数据挖掘？2013年NBA总决赛战术分析（2013年6月22日）为什么当热火打出制胜高潮，韦德却在场边观战？为什么当热火打出制胜高潮，韦德却在场边观战？ 为什么詹姆斯和韦德都在场上时，热火却在失分？为什么詹姆斯和韦德都在场上时，热火却在失分？ 数

12、据库原理与应用Principles of Database Systems刺眼的詹韦矛盾刺眼的詹韦矛盾 第三节最后2分25秒，热火一波11-3建立10分优势。第四节前5分钟，热火又是一波16比2的高潮，韦德不在场的近8分钟时间内，热火轰出一波24比9。 两段制胜高潮，韦德都在场下。事实上，总决赛期间，詹姆斯詹姆斯和韦德同时在场和韦德同时在场230230分钟，在此期间，热火净负分钟，在此期间，热火净负5757分之多。而在勒分之多。而在勒布朗独自在场的布朗独自在场的7171分钟里，热火净胜马刺分钟里，热火净胜马刺5757分。分。韦德不在，勒布朗每48分钟可以轰下惊人的38.5分、12.8个篮板、1

13、0.1次助攻，准星53.5%；而当两人同时在场，勒布朗的数据暴跌到了25分、11.9个篮板、7.1次助攻，准星41.1%。数据库原理与应用Principles of Database Systems 韦德在场，勒布朗5尺内34投仅19中，而当韦德不在，勒布朗5尺内15投14中。韦德在场，热火外线缺少牵制力，拉不开空间，勒布朗的突破被限制，前6场当韦德在场时，他的每48分钟突破只有8.4次，比韦德不在时少了6.3次之多，准星也跌了27%。相同的情况，在韦德身上也出现了，总决赛当勒布朗在场时，韦德每48分钟只有24.4分5.8助攻4.8篮板，而当勒布朗不在时，他的数据暴涨到38.4分7.7助攻9.

14、6篮板，准星从46.3%提升到55.6%。 数据库原理与应用Principles of Database Systems数据挖掘技术的产生数据挖掘技术的产生数据挖掘的概念与分类体系数据挖掘的概念与分类体系数据挖掘的原理与方法数据挖掘的原理与方法WebWeb数据挖掘问题数据挖掘问题数据挖掘系统结构数据挖掘系统结构本章主要内容本章主要内容数据库原理与应用Principles of Database Systems大批成熟的业务信息系统大批成熟的业务信息系统投入运行投入运行信息系统多年运行，积累信息系统多年运行，积累了海量的数据了海量的数据各类信息系统大多属于面各类信息系统大多属于面向事务处理的向事

15、务处理的OLTPOLTP系统系统数据是一种宝贵的资源，数据是一种宝贵的资源，但没有充分发挥作用但没有充分发挥作用企业信息化发展现状企业信息化发展现状数据库原理与应用Principles of Database Systems发展趋势发展趋势数据集中化数据集中化业务综合化业务综合化管理管理“扁平化扁平化”决策科学化决策科学化特点特点以客户为中心以客户为中心以服务求发展以服务求发展企业信息化发展现状企业信息化发展现状我在数据中获我在数据中获取知识取知识数据库原理与应用Principles of Database Systems技术的产生技术的产生 随着数据库技术的迅速发展以及数据库管理系统的广随着

16、数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来越多。激增的泛应用，人们积累的数据越来越多。激增的数据背后隐藏着数据背后隐藏着许多重要的信息许多重要的信息，人们希望能够对其进行更高层次的分析。，人们希望能够对其进行更高层次的分析。目前的数据库系统可以高效地实现数据的录入、查询、统计目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，缺乏挖掘数等功能，但无法发现数据中存在的关系和规则，缺乏挖掘数据背后隐藏的知识的手段，导致了据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏数据爆炸但知识贫乏”的现象。的现象。 数据库原理与应用Prin

17、ciples of Database Systems 四个主要的技术理由激发了数据挖掘的开发、应用和研究四个主要的技术理由激发了数据挖掘的开发、应用和研究的兴趣：的兴趣： 超大规模数据库的出现。如商业数据仓库和计算机自动超大规模数据库的出现。如商业数据仓库和计算机自动收集的数据记录；收集的数据记录； 先进的计算机技术。如更快和更大的计算能力和并行体先进的计算机技术。如更快和更大的计算能力和并行体系结构；系结构； 对巨大量数据的快速访问能力；对巨大量数据的快速访问能力； 对这些数据应用精深的统计方法计算的能力。对这些数据应用精深的统计方法计算的能力。数据库原理与应用Principles of D

18、atabase SystemsData MiningDatabase TechnologyStatisticsOtherDisciplinesInformationScienceMachineLearningVisualization数据挖掘数据挖掘多学科交叉的领域多学科交叉的领域数据库原理与应用Principles of Database Systems数据挖掘技术的产生数据挖掘技术的产生数据挖掘的概念与分类体系数据挖掘的概念与分类体系数据挖掘的原理与方法数据挖掘的原理与方法WebWeb数据挖掘问题数据挖掘问题数据挖掘系统结构数据挖掘系统结构数据库原理与应用Principles of Dat

19、abase Systems数据挖掘的定义数据挖掘的定义从技术角度看从技术角度看，数据挖掘是从大量的、不完全的、有噪声，数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的实际数据中，提取隐含在其中的、人的、模糊的、随机的实际数据中，提取隐含在其中的、人们所不知道的、但又是潜在有用的信息和知识的过程。们所不知道的、但又是潜在有用的信息和知识的过程。从商业应用角度看从商业应用角度看，数据挖掘是一种崭新的商业信息处理，数据挖掘是一种崭新的商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转化、分析和模式化处理，从中提取辅助商业决策

20、抽取、转化、分析和模式化处理，从中提取辅助商业决策的关键知识。的关键知识。 数据库原理与应用Principles of Database Systems数据挖掘（从数据中发现知识）数据挖掘（从数据中发现知识） （1 1）从大量的数据中挖掘哪些令人感兴趣的、有用的、隐含的、）从大量的数据中挖掘哪些令人感兴趣的、有用的、隐含的、先前求知的和可能有用的模式或知识；（先前求知的和可能有用的模式或知识；（2 2）挖掘的不仅仅是数据）挖掘的不仅仅是数据（所以（所以“数据挖掘数据挖掘”并非一个精确的用词）。并非一个精确的用词）。数据挖掘的替换词数据挖掘的替换词 数据库中的知识挖掘（数据库中的知识挖掘（KDD

21、KDD）、知识提炼、数据）、知识提炼、数据/ /模式分析、模式分析、数据考古、数据捕捞、信息收获等等。数据考古、数据捕捞、信息收获等等。数据库原理与应用Principles of Database Systems数据挖掘数据挖掘知识发现过程（知识发现过程（KDDKDD）的核心）的核心 数据清理数据清理：消除噪音或不一致消除噪音或不一致数据数据 数据集成数据集成：多种数据源可以组：多种数据源可以组合在一起合在一起 数据选择数据选择：从数据库中提取与从数据库中提取与分析任务相关的数据分析任务相关的数据 数据变换数据变换：数据变换或统一成数据变换或统一成适合挖掘的形式适合挖掘的形式 数据挖掘数据挖掘

22、：基本步骤，使用智基本步骤，使用智能方法提取数据模式能方法提取数据模式 模式评估模式评估：根据某种兴趣度度根据某种兴趣度度量，识别提供知识的真正有用量，识别提供知识的真正有用的模式的模式 知识表示知识表示：使用可视化和知识使用可视化和知识表示技术，向用户提供挖掘的表示技术，向用户提供挖掘的知识知识数据库原理与应用Principles of Database Systems数据挖掘系统分类数据挖掘系统分类 根据挖掘的根据挖掘的数据类型数据类型分类分类 根据挖掘的根据挖掘的知识类型知识类型分类分类 根据所用的根据所用的挖掘技术挖掘技术分类分类 根据系统的根据系统的应用领域应用领域分类分类数据库原理

23、与应用Principles of Database Systems关系数据库关系数据库面向对象数据库面向对象数据库文本数据文本数据多媒体数据多媒体数据异构数据异构数据WebWeb数据数据数据类型数据类型182491104832323811502232601023476233N =SEG210987654321TENU_MTH160140120100806040200-20182491104832323811502229181365476233N =SEG210987654321INV_RCNT400003000020000100000-10000Data Warehouse数据库原理与应用Pr

24、inciples of Database Systems 关联挖掘关联挖掘 序列模式挖掘序列模式挖掘 聚类挖掘聚类挖掘 分类挖掘分类挖掘孤立点挖掘孤立点挖掘概化挖掘概化挖掘预测挖掘预测挖掘知识分类知识分类数据库原理与应用Principles of Database Systems数据库技术数据库技术机器学习技术机器学习技术统计技术统计技术神经网络技术神经网络技术可视化技术可视化技术挖掘技术挖掘技术数据库原理与应用Principles of Database Systems数据挖掘技术的产生数据挖掘技术的产生数据挖掘的概念与分类体系数据挖掘的概念与分类体系数据挖掘的原理与方法数据挖掘的原理与方法

25、WebWeb数据挖掘问题数据挖掘问题数据挖掘系统结构数据挖掘系统结构数据库原理与应用Principles of Database Systems关联挖掘关联挖掘序列模式挖掘序列模式挖掘分类挖掘分类挖掘聚类挖掘聚类挖掘孤立点挖掘孤立点挖掘数据库原理与应用Principles of Database Systems关联知识挖掘举例关联知识挖掘举例 一个超级市场的销售系统记录了顾客购物的情一个超级市场的销售系统记录了顾客购物的情况。下表中记录了况。下表中记录了5 5个顾客的购物单。个顾客的购物单。 记录号记录号所购物品清单所购物品清单1啤酒、尿布，婴儿爽身粉，面包，雨伞啤酒、尿布，婴儿爽身粉，面包，

26、雨伞2尿布，婴儿爽身粉尿布，婴儿爽身粉3啤酒、尿布，牛奶啤酒、尿布，牛奶4尿布，啤酒，洗衣粉尿布，啤酒，洗衣粉5啤酒，牛奶，可乐饮料啤酒，牛奶，可乐饮料表表1数据库原理与应用Principles of Database Systems 超市经理想知道商品之间的关联，要求列出那超市经理想知道商品之间的关联，要求列出那些同时购买的、且支持度些同时购买的、且支持度40%40%（即在（即在5 5行中至少出行中至少出现两次）的商品名称。现两次）的商品名称。 KDDKDD系统通过特定算法（系统通过特定算法（Apriori Apriori 算法）多次算法）多次扫描数据库，依次得出如表扫描数据库，依次得出如表

27、2 2和表和表3 3。其中支持度。其中支持度2/5 6THEN tenured = yes 模型数据库原理与应用Principles of Database Systems分类过程分类过程 : : 使用模型使用模型模型测试集NAMERANKYEARS TENUREDTomAssistant Prof2noMerlisa Associate Prof7noGeorge Professor5yesJoseph Assistant Prof7yes未知数据(Jeff, Professor, 4)Tenured?数据库原理与应用Principles of Database Systems一一 个训个训

28、 练练 集集ageincome studentcredit_ratingbuys_computer=30highnofairno40mediumnofairyes40lowyesfairyes40lowyesexcellentno3140 lowyesexcellentyes=30mediumnofairno40mediumyesfairyes40mediumnoexcellentno数据库原理与应用Principles of Database Systems一棵关于一棵关于“买计算机买计算机”的决策树实例的决策树实例age?overcaststudent?credit rating?noye

29、sfairexcellent40yes31.40nonoyesyes根内部节点叶子分枝数据库原理与应用Principles of Database Systems什么是一个好的聚类方法什么是一个好的聚类方法? ?1.1. 一个好的聚类方法要能产生高质量的聚类结果一个好的聚类方法要能产生高质量的聚类结果簇，这些簇要具备以下两个特点：簇，这些簇要具备以下两个特点： 高的簇内相似性高的簇内相似性 低的簇间相似性低的簇间相似性 2.2. 聚类结果的好坏取决于该聚类方法采用的相似性聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现；评估方法以及该方法的具体实现；3.3. 聚类方法的好

30、坏还取决与该方法是能发现某些还聚类方法的好坏还取决与该方法是能发现某些还是所有的隐含模式。是所有的隐含模式。数据库原理与应用Principles of Database SystemsK-K-平均算法平均算法012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910K=2Arbitrarily choose K object as initial cluster centerAssign each objects to most similar centerUp

31、date the cluster meansUpdate the cluster meansreassignreassign数据库原理与应用Principles of Database Systems应用聚类分析的例子应用聚类分析的例子客户划分与市场销售客户划分与市场销售: : 帮助市场人员发现客户中帮助市场人员发现客户中的不同群体，然后用这些知识来开展一个目标明的不同群体，然后用这些知识来开展一个目标明确的市场计划；确的市场计划；土地使用土地使用: : 在一个陆地观察数据库中标识那些土在一个陆地观察数据库中标识那些土地使用相似的地区；地使用相似的地区；保险保险: : 对购买了汽车保险的客户，

32、标识那些有较对购买了汽车保险的客户，标识那些有较高平均赔偿成本的客户；高平均赔偿成本的客户；城市规划城市规划: : 根据类型、价格、地理位置等来划分根据类型、价格、地理位置等来划分不同类型的住宅；不同类型的住宅；数据库原理与应用Principles of Database Systems 数据库中可能包含一些数据对象，它们数据库中可能包含一些数据对象，它们与数据的一般行为或模型很不一致，这与数据的一般行为或模型很不一致，这些对象称作孤立点些对象称作孤立点 孤立点包括很多潜在的知识，如分类中孤立点包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测的反常实例、不满足规则的特例、观测结果

33、与模型预测值的偏差、量值随时间结果与模型预测值的偏差、量值随时间的变化等的变化等孤立点（孤立点（OutlierOutlier）挖掘）挖掘数据库原理与应用Principles of Database Systems数据挖掘技术的产生数据挖掘技术的产生数据挖掘的概念与分类体系数据挖掘的概念与分类体系数据挖掘的原理与方法数据挖掘的原理与方法WebWeb数据挖掘问题数据挖掘问题数据挖掘系统结构数据挖掘系统结构数据库原理与应用Principles of Database Systems 面向Web的数据挖掘比面向数据库和数据仓库的数据挖掘要复杂得多：异构数据源环境：异构数据源环境：Web网站上的信息是异

34、构: 每个站点的信息和组织都不一样；存在大量的无结构的文本信息、复杂的多媒体信息；站点使用和安全性、私密性要求各异等等。数据的是复杂性：数据的是复杂性：有些是无结构的（如Web页），通常都是用长的句子或短语来表达文档类信息；有些可能是半结构的（如Email，HTML页）。动态变化的应用环境：动态变化的应用环境：WebWeb的信息是频繁变化的，像新闻、股票等信息是实时更新的。的信息是频繁变化的，像新闻、股票等信息是实时更新的。这种高变化也体现在页面的动态链接和随机存取上。这种高变化也体现在页面的动态链接和随机存取上。WebWeb上的用户是难以预测的。上的用户是难以预测的。WebWeb上的数据环境

35、是高噪音的。上的数据环境是高噪音的。数据库原理与应用Principles of Database Systems Web结构挖掘：挖掘Web上的链接结构。通过Web页面间的链接信息可以识别出权威页面（Authoritative Page）、安全隐患（非法链接）等。 Web使用挖掘：对Web上的Log日志记录的挖掘Web上的Log记录了包括URL请求、IP地址以及时间等访问信息。分析和发现Log日志中蕴藏的规律可以帮助我们识别潜在的客户、跟踪Web服务的质量以及侦探非法访问的隐患等。 Web内容挖掘： Web的内容是丰富的，而且构成成分是复杂的。Web的内容主要是包含文本、声音、图片等的文档信息。文本挖掘（Text Mining）和Web搜索引擎（Search Engine）等相关领域的研究。多媒体信息挖掘技术。数据库原理与应用Principles of Database Systems数据挖掘技术的产生