数据库与数据挖掘8-9

第8章数据挖掘技术概述8.1什么是数据挖掘？数据挖掘（DataMining），是指从大量数据中提取人们感兴趣的知识，这些知识是隐含的、事先未知的、潜在有用信息，提取的知识一般可表示为概念（Concepts）、规则（Rules）、规律（Regularities）、模式（Patterns）等形式。•有人将数据挖掘称为数据库中的知识发现（KDD:KnowledgeDiscoveryinDatabase）。•也有人将数据挖掘看成为KDD中的一个步骤。KDD过程由以下步骤组成：•数据清理（消除噪音和不一致数据）•数据集成（多种数据源组合在一起）•数据选择（选择与分析任务相关的数据）•数据变换（变换成适合挖掘的形式）•数据挖掘•模式评估（用兴趣度度量）易于理解、新颖、潜在有用、有效•知识表示8.2数据挖掘产生与发展•1989年8月在美国底特律召开的第11届国际人工智能会议上首先出现“数据库中知识发现（KDD）”这个术语，随后引起了国际人工智能和数据库等领域专家的广泛关注。•1995年在加拿大蒙特利尔召开了首届KDD&DataMining国际学术会议。•1997年《KDD&DataMining》国际刊物创刊。•20多年来，数据挖掘研究引起国际国内广泛重视，成为一个重要的研究方向，研究内容不断扩展，被各国列为重点资助的科技计划，并且向其他应用领域渗透。数据挖掘:多学科的融合数据挖掘数据库技术统计学归纳推理模式识别机器学习可视化技术8.3数据挖掘分类1.针对不同的数据源分：•关系数据挖掘文本数据挖掘•图像数据挖掘声音数据挖掘•空间数据挖掘时态数据挖•数据流挖掘Web数据挖掘•树挖掘图挖掘2.根据挖掘的知识分：•关联分析:关联规则挖掘•分类:构造分类器，用于离散值的预测•聚类分析：发现新的事物/模式•序列模式分析：发现事物变化的规律/周期•离群数据挖掘：发现异常事物/模式•趋势分析：用于预测•回归分析：建立数学模型，用于连续值的预测8.4数据挖掘采用的技术/方法(1)统计归纳(2)决策树方法(3)神经网络(4)支持向量机(5)遗传算法(6)粗集方法(7)Bayes方法等8.5数据挖掘技术研究的选题•(1)针对不同的数据源进行挖掘例如：关系数据挖掘、文本数据挖掘、Web数据挖掘、空间数据挖掘、数据流挖掘、树挖掘、图挖掘等•(2)针对不同的知识类型/目标进行挖掘例如:关联分析、分类、聚类分析、离群数据挖掘、序列模式挖掘•(3)采用不同技术进行挖掘例如：统计推理、支持向量机方法、遗传算法、决策树、粗糙集方法(4)数据挖掘的应用研究例如：用于网络入侵检测、生物信息学、医学图像自动诊断、地理信息系统等•(5)针对不同环境下的数据挖掘单机环境、网络环境、分布式环境、云计算环境8.6数据挖掘应用数据挖掘技术在科学研究、金融投资、市场营销、保险、医疗卫生、产品制造业、通信网络管理等行业已得到应用。（1）科学研究：在信息量极为庞大的天文、气象、生物技术等领域中，所获得的大量实验和观测数据靠传统的数据分析工具难以对付，因此对功能强大的智能化自动分析工具要求迫切，这种需求推动了KDD技术在科学研究领域的应用发展，并且已获得一些重要的应用成果。例如，美国加州理工学院喷气推进实验室与天文学家合作开发的SKICAT系统通过对几百万个天体进行分类，帮助天文学家发现了16个新的类星体。（2）金融投资：由于金融投资的风险很大，因此在进行投资决策时，需要对各种投资方向的有关数据进行分析，以选择最佳的投资方向。数据挖掘可以通过对已有数据进行处理，利用学习得到的模式进行市场预测。例如，智能股票分析系统，可以对股票行情进行分析预测。（3）市场营销：主要用于商品的市场定位和消费者分析，辅助制定市场策略；还可以用来分析购物模式，预测销售行情。例如，IBM公司开发的QUEST和IntelligentMiner系统可以挖掘顾客的购物行为模式。（4）保险业：保险是一项风险业务，保险公司的一个重要工作就是进行风险评估。可以利用数据挖掘技术进行风险分析，在保险公司建立的保单及索赔信息数据库的基础上寻找保单中风险较大的领域，从而得出一些实用的控制风险的规则，指导保险公司的工作。例如，利用SGI公司的MineSet系统提供的分类器就可以预测投保人在将来的索赔概率。（5）制造业：制造业应用数据挖掘技术进行零件故障诊断、资源优化、生产过程分析等。通过对生产数据进行分析，发现容易产生质量问题的工序以及相关的故障因素等。例如，Acknosoft公司开发的CASSIOPEE系统已用于诊断和预测在波音飞机制造过程中可能出现的问题。（6）通信网络管理：在通信网络运行过程中，会产生一系列警告，这些警告有的可以置之不理，而有的如果不及时采取措施则会带来不可挽回的损失。由于警告产生的随机性很大，究竟哪些警告可以不予理睬，哪些警告必须迅速处理往往很难判断，一般需要由人工根据经验进行处理，效率不高。数据挖掘可以通过分析已有的警告信息的正确处理方法以及警告之间的前后关系，得到警告之间的关联规则，这些有价值的信息可用于网络故障的定位检测和严重故障的预测。例如，芬兰Helsinki大学开发了一个基于通信网络中警报数据库的知识发现系统TASA，用来寻找通信网络中警报序列规则，从而进行故障预测。第9章关联规则挖掘9.1基本概念1.什么是关联规则？（相关性分析）设I={}是由m个不同的项目组成的集合，给定一个事务数据库DB，其中的每一个事务T是I中一组项目的集合，即，一条关联规则就是形如的蕴含式，其中，X∩Y=Φ。例：AB,ABC,MNPQbuy(X,‘computer’)buy(X,‘printer’)buy(X,‘尿布’)buy(X,‘啤酒’)miii,......,21ITYXIYIX,2.项目集的支持度设DB的总记录数为N，DB中包含X的记录数S,则X的支持度为：3.规则的可信度NSXport)(sup)(sup)(sup)(XportYXportXYXYXconf的记录数含）的记录数含（NYXYXport）的记录数含（)(sup4.关联规则成立的条件用户给定最小支持度minsup,最小可信度minconf,要求：supmin)(supYXporconfYXconfmin)(5.k-项集：项目集中含有k个项目6.频繁项目集：7.挖掘关联规则的步骤（1）计算所有的频繁项目集（2）利用频繁项目集生成关联规则对于每个频繁项目集A,supmin)(supXport.min)(sup)(sup,aAaconfaportAportAa则且若9.2关联规则挖掘研究工作（1）单机环境下的关联规则挖掘算法•这是关联规则挖掘的基本方法。其中比较著名的算法包括Agrawal等人提出的Aprior，Savasere等人提出的分割算法PARTITION，Toivonen提出的抽样算法Sampling以及HanJW等人提出的基于频繁模式树（FP-tree）的频繁项目集挖掘算法FP-growth等等。其中，Apriori算法的基本思想是重复扫描数据库，PARTITION算法是针对海量数据库，将数据库进行分割，减少挖掘过程中I/O操作次数；Sampling算法是首先对数据库进行抽样，然后对抽样数据库进行挖掘，从而提高挖掘效率。FP-growth算法是通过构建FP-tree来求解频繁项目集。研究人员还提出了一些Aprior算法的改进算法。（2）多值属性关联规则挖掘关联规则可分为布尔关联规则和多值属性关联规则。多值属性关联规则又可分为数量关联规则和类别关联规则。数量关联规则是指同时包含布尔属性和连续属性的关联规则。目前提出的类别属性关联规则的挖掘算法大多是将类别属性关联规则挖掘问题转化为布尔型关联规则挖掘问题。即将类别属性中的每一个类别当作一个属性。数量关联规则挖掘的关键问题是对连续属性进行离散化。（3）关联规则更新算法•关联规则的更新问题主要有两种情况：①在给定的最小支持度和最小置信度条件下，当数据库变化后，如何生成数据库中的关联规则；②给定一个数据库，在最小支持度和最小置信度发生变化时，如何生成数据库中的关联规则。（4）基于约束条件的关联规则挖掘•基于约束条件的关联规则挖掘的主要目的是发现更有趣、更实用、更特别的关联规则。•在提供布尔表达式约束情况下的关联规则发现问题。•分布式数据库环境下带有约束条件的关联规则挖掘。（5）关联规则并行及分布挖掘算法•目前已经提出的关联规则并行挖掘算法有：Agrawal等人提出的算法CD（CountDistribution）、CaD（CandidateDistribution）、DD（DataDistribution），Park等人提出的算法PDM等。用于分布式数据库系统中进行关联规则挖掘的比较著名的算法有：FDM、DMA、DDDM等。•云计算环境下的关联规则挖掘-------并行挖掘9.3Apriori算法1.Apriori性质频繁项目集的所有子集都是频繁的。2.算法思想重复扫描数据库，在第K次扫描时产生出长度为K的频繁项目集LK，而在第K＋1次扫描时，由LK中的K项集产生长度为K＋1的候选集CK＋1；11221......KKkLCLLCL举例：设minsupport=2TID购物列表T1I1，I2，I5T2I2，I4T3I2，I3T4I1，I2，I4T5I1，I3T6I2，I3T7I1，I3T8I1，I2，I3，I5T9I1，I2，I3L1supportI16I27I36I42I52项集supportI16I27I36I42I52•L1C2(I1，I2),(I1，I3),(I1，I4),(I1，I5)(I2，I3),(I2，I4),(I2，I5)(I3，I4),(I3，I5)(I4，I5)•C2L2扫描数据库，计算支持数(I1，I2)：4,(I1，I3)：4,(I1，I4)：1,(I1，I5)：2(I2，I3)：4,(I2，I4)：2,(I2，I5)：2(I3，I4)：0,(I3，I5)：1(I4，I5)：0•L2：(I1，I2)：4,(I1，I3)：4,(I1，I5)：2(I2，I3)：4,(I2，I4)：2,(I2，I5)：2•L2C3经过连接、剪枝得C3：(I1，I2，I3)、（I1，I2，I5)•C3L3扫描数据库，计算支持数(I1，I2，I3)：2，（I1，I2，I5)：2•L3：(I1，I2，I3)：2，（I1，I2，I5)：2•L3C4C4={(I1，I2，I3，I5)}剪枝后：C4=终止。•对于每个频繁项目集L2、L3，产生规则,计算可信度，根据最小可信度minconf，确定关联规则。例如：设minconf=70%,•对于（I1，I2，I5)I1andI2I5,conf=2/4=50%I1andI5I2,conf=2/2=100%√I2andI5I1,conf=2/2=100%√I1I2andI5,conf=2/6=33%I2I1andI5,conf=2/7=29%I5I1andI2,conf=2/2=100%√•对于（I1，I2，I3)同样产生关联规则3.Apriori算法描述如下：(1)L1={large1-itemset};//生成含有1个项目的频繁集(2)for(k=2;Lk-1≠Ø;k++)do(3){Ck=Apriori_gen(Lk-1);(4)foralltransactiont∈Ddo(5){Ct=subset(Ck,t);//产生包含于事务t中的k项目集Ct(6)forallCandidatec∈Ctdo(7)c.count++;}(8)Lk={c∈Ck∣c.count≥minsup}}(9)Answer=∪kLk;Apriori_gen(Lk-1)的算法步骤：(1)insertintoCkselectp.item1，p.item2，……，p.itemk-1，q.itemk-1fromLk-1.p，Lk-1.qwherep.item1=q.item1，p.item2=q.item2，