44知识发现和数据挖掘--史忠植

高级人工智能史忠植1第九章知识发现和数据挖掘数据库中知识发现史忠植中科院计算所9/2004高级人工智能史忠植2知识发现关联规则数据仓库知识发现工具9/2004高级人工智能史忠植3知识发现知识发现是指从数据集中抽取和精炼新的模式。范围非常广泛：经济、工业、农业、军事、社会数据的形态多样化：数字、符号、图形、图像、声音数据组织各不相同：结构化、半结构化和非结构发现的知识可以表示成各种形式规则、科学规律、方程或概念网。9/2004高级人工智能史忠植4数据库知识发现目前,关系型数据库技术成熟、应用广泛。因此,数据库知识发现(KnowledgeDiscoveryinDatabasesKDD)的研究非常活跃。该术语于1989年出现，Fayyad定义为“KDD是从数据集中识别出有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程”9/2004高级人工智能史忠植5不同的术语名称知识发现是一门来自不同领域的研究者关注的交叉性学科，因此导致了很多不同的术语名称。知识发现:人工智能和机器学习界。数据挖掘(datamining):统计界、数据分析、数据库和管理信息系统界知识抽取(informationextraction)、信息发现(informationdiscovery)、智能数据分析(intelligentdataanalysis)、探索式数据分析(exploratorydataanalysis)信息收获(informationharvesting)数据考古(dataarcheology)9/2004高级人工智能史忠植69/2004高级人工智能史忠植7知识发现的任务(1)数据总结：对数据进行总结与概括。传统的最简单的数据总结方法是计算出数据库的各个字段上的求和值、平均值、方差值等统计值,或者用直方图、饼状图等图形方式表示。分类：根据分类模型对数据集合分类。分类属于有导师学习，一般需要有一个训练样本数据集作为输入。聚类：根据数据的不同特征，将其划分为不同的类。无导师学习9/2004高级人工智能史忠植8知识发现的任务(2)相关性分析：发现特征之间或数据之间的相互依赖关系关联规则偏差分析：基本思想是寻找观察结果与参照量之间的有意义的差别。通过发现异常,可以引起人们对特殊情况的加倍注意。建模：构造描述一种活动或状态的数学模型9/2004高级人工智能史忠植9知识发现的方法(1)统计方法：传统方法：回归分析、判别分析、聚类分析、探索性分析模糊集(fuzzyset)Zadeh1965支持向量机(SupportVectorMachine)Vapnik90年代初粗糙集(RoughSet)Pawlak80年代初9/2004高级人工智能史忠植10知识发现的方法(2)机器学习：规则归纳：AQ算法决策树：ID3、C4.5范例推理:CBR遗传算法:GA贝叶斯信念网络9/2004高级人工智能史忠植11知识发现的方法(3)神经计算：神经网络是指一类新的计算模型，它是模仿人脑神经网络的结构和某些工作机制而建立的一种计算模型。常用的模型：Hopfield网多层感知机自组织特征映射反传网络可视化：9/2004高级人工智能史忠植12KDD的技术难点动态变化的数据噪声数据不完整冗余信息数据稀疏超大数据量9/2004高级人工智能史忠植13关联规则属于知识发现任务中的相关性分析由于条形码技术的发展,零售部门可以利用前端收款机收集存储大量的售货数据。因此,如果对这些历史事务数据进行分析,则可对顾客的购买行为提供极有价值的信息。例如,可以帮助如何摆放货架上的商品(如把顾客经常同时买的商品放在一起),帮助如何规划市场(怎样相互搭配进货)。9/2004高级人工智能史忠植14关联规则的表示关联规则的形式如“在购买面包顾客中,有70%的人同时也买了黄油”,可以表示成：面包→黄油。用于关联规则发现的主要对象是事务型数据库,其中针对的应用则是售货数据,也称货篮数据。一个事务一般由如下几个部分组成:事务处理时间,一组顾客购买的物品,有时也有顾客标识号(如信用卡号)。9/2004高级人工智能史忠植15关联规则的相关概念(1)设R={I1,I2……Im}是一组物品集，W是一组事务集。W中的每个事务T是一组物品，TR。假设有一个物品集A，一个事务T，如果AT，则称事务T支持物品集A。关联规则是如下形式的一种蕴含：A→B，其中A、B是两组物品，AI，BI，且A∩B=。9/2004高级人工智能史忠植16关联规则的相关概念(2)支持度物品集A的支持度：称物品集A具有大小为s的支持度,如果D中有s%的事务支持物品集XP(A)1000个顾客购物，其中200个顾客购买了面包，支持度就是20％（200/1000）。关联规则A→B的支持度：关联规则A→B在事务数据库W中具有大小为s的支持度,如果物品集A∪B的支持度为s100个顾客购买了面包和黄油，则面包→黄油10％9/2004高级人工智能史忠植17关联规则的相关概念(3)可信度设W中支持物品集A的事务中，有c％的事务同时也支持物品集B，c％称为关联规则A→B的可信度。P(B|A)1000个顾客购物，200个顾客购买了面包，其中140个买了黄油，则可信度是70％（140/200）。9/2004高级人工智能史忠植18关联规则的相关概念(4)最小支持度minsup用户规定的关联规则必须满足的最小支持度。最小可信度minconf用户规定的关联规则必须满足的最小可信度。大项集(大项集、大物品集largeitemset)支持度不小于最小支持度minsup的物品集9/2004高级人工智能史忠植19关联规则发现任务给定一个事务数据库D，求出所有满足最小支持度和最小可信度的关联规则。该问题可以分解为两个子问题：1)求出D中满足最小支持度的所有大项集；2)利用大项集生成满足最小可信度的所有关联规则。对于每个大项集A，若BA，B≠φ，且Confidence（B(AB)）minconf，则构成关联规则B(AB)9/2004高级人工智能史忠植20关联规则发现的基本思路第2个子问题比较容易。目前大多数研究集中在第一个子问题上，即如何高效地求出大项集。•首先生成长度为1的大项集（即单个物品），记为L[1]；•在L[k]的基础上生成候选物品集C[k+1]，候选物品集必须保证包括所有的大项集。•用事务数据库D中的事务对C[k+1]进行支持度测试以生成长度为k+1的大项集L[k+1]，计算每个候选物品集的支持度，如果大于minsup，则加入到L[k+1]中。•如果L[k+1]为空集，则结束，L[1]∪L[2]∪…即为结果；否则转(2)，继续。9/2004高级人工智能史忠植21思路的正确性利用了大物品集向下封闭性，即大物品集X的任意子集一定是大物品集，反过来说，如果X有一子集不是大项集，则X肯定不是。是宽度优先算法9/2004高级人工智能史忠植22经典的Apriori算法(1)L[1]={large1-itemsets};(2)for(k=2;L[k-1]不为空;k++)dobegin(3)C[k]=apriori-gen(L[k-1]);//新候选物品集(4)Foralltransactionst∈Ddobegin(5)C=subset(C[k],t);//t中的候选物品集(6)Forallcandidatesc∈Cdo(7)c.count++;(8)end;(9)L[k]={c∈C[k]|c.count=minsup};(10)end;(11)Answer=L[1]∪L[2]∪…9/2004高级人工智能史忠植23apriori-gen(L[k-1])分成两步：join算法：从两个L[k-1]物品集生成候选物品集C[k]insertintoC[k]selectp.item1,p.item2,...,p.item(k-1),q.item(k-1)fromL[k-1]p,L[k-1]qwherep.item1=q.item1,...,p.item(k-2)=q.item(k-2),p.item(k-1)q.item(k-1)9/2004高级人工智能史忠植24Prune算法：从C[k]中除去大小为k-1且不在L[k-1]中的子集(1)Forallitemsetsc∈C[k]do(2)Forall(k-1)-subsetssofcdo(3)if(sL[k-1])(4)thendeletecfromC[k]9/2004数量型关联规则算法首先选定要挖掘的属性，将各个属性映射为相对各个区间的布尔值。扫描数据库产生支持度大于最小支持度的频繁1-项集。支持度超过最小支持度的区间直接作为频繁集内的项，支持度未达到最小支持度的区间进行合并操作然后加入频繁集。将频繁k-1-项集内的所有只有一个元素不同的两项合并，产生新的集合。然后对该集合进行修剪，当新产生的集合中的某项的k-1子集没有包含在频繁k-1项集中时，将该项从新产生的集合中删除。修剪完后的集合成为新一轮数据库扫描的候选集。依据前面生成的候选集扫描数据库，通过统计和合并产生频繁k-项集，然后回到步骤3,直到候选的集合为空为止。产生了所有频繁集之后，通过计算其能产生的规则的可信度。依照最小可信度剔除无用规则。高级人工智能史忠植259/2004合并小于最小支持度集合算法设未达到最小支持度的区间集合设为D={D1„„Dn}，则合并算法combine(D)为：ForAllElementinD在D中选出一个区间Di,其中Di为D中支持度sup(Di)最大的区间；If[sup(Di-1)sup(Di+1)]{将区间Di和Di-1合并为新区间D′i;sup(D′i)=sup(Di)+sup(Di-1);从D中删除Di和Di-1；}Else{将区间Di和Di+1合并为新区间D′i；sup(D′i)=sup(Di)+sup(Di+1);从D中删除Di和Di+1；}If(sup(D′i)最小支持度)将D′i加入频集；Else将D′i加入D中。高级人工智能史忠植269/2004高级人工智能史忠植27举例：L[3]为{{1,2,3},{1,2,4},{1,3,4},{1,3,5},{2,3,4}}经过join后，C[4]={{1,2,3,4},{1,3,4,5}}由于{1,3,4,5}有子集{1,4,5}不在L[3]中，所以经过prune后，得到L[4]={{1,2,3,4}}9/2004高级人工智能史忠植289/2004高级人工智能史忠植299/2004高级人工智能史忠植309/2004高级人工智能史忠植319/2004高级人工智能史忠植32关联规则发现注意的问题充分理解数据目标明确数据准备工作要做好选取适当的最小的支持度和可信度很好地理解关联规则9/2004高级人工智能史忠植33关联规则发现使用步骤连接数据，做数据准备给定最小支持度和最小可信度，利用知识发现工具提供的算法发现关联规则可视化显示、理解、评估关联规则9/2004高级人工智能史忠植34关联规则在保险业务中的应用最小支持度1%，最小可信度为50%9/2004高级人工智能史忠植359/2004高级人工智能史忠植369/2004高级人工智能史忠植379/2004高级人工智能史忠植38数据仓库在过去几十年，数据库技术，特别是OLTP（联机事务处理），主要是为自动化生产、精简工作任务和高速采集数据服务。它是事务驱动的、面向应用的。20世纪80年代，人们要利用现有的数据，进行分析和推理，从而为决策提供依据。这种需求既要求联机服务，又涉及大量用于决策的数据。而传统的数据库系统已无法满足这种需求：所需历史数据量很大，而传统数据库一般只存储短期数据。涉及许多部门的数据，而不同系统的数据难以集成。对大量数据的访问性能明显下降9/2004高级人工智能史忠植39数据仓库的定义信息处理技术的发展趋势是：从大量的事务型数据库中抽取数据，并将其