aai知识发现和数据挖掘高级人工智能史忠植2

第九章知识发现和数据挖掘数据库中知识发现

史忠植中科院计算所2023/1/111知识发现关联规则数据仓库知识发现工具2023/1/112知识发现知识发现是指从数据集中抽取和精炼新的模式。范围非常广泛：经济、工业、农业、军事、社会数据的形态多样化：数字、符号、图形、图像、声音数据组织各不相同：结构化、半结构化和非结构发现的知识可以表示成各种形式 规则、科学规律、方程或概念网。2023/1/113数据库知识发现

目前,关系型数据库技术成熟、应用广泛。因此,数据库知识发现(KnowledgeDiscoveryinDatabasesKDD)的研究非常活跃。

该术语于1989年出现，Fayyad定义为“KDD是从数据集中识别出有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程”

2023/1/114不同的术语名称

知识发现是一门来自不同领域的研究者关注的交叉性学科，因此导致了很多不同的术语名称。

知识发现:人工智能和机器学习界。数据挖掘(datamining): 统计界、数据分析、数据库和管理信息系统界知识抽取(informationextraction)、信息发现(informationdiscovery)、智能数据分析(intelligentdataanalysis)、探索式数据分析(exploratorydataanalysis)信息收获(informationharvesting)

数据考古(dataarcheology)2023/1/1152023/1/116知识发现的任务(1)数据总结：对数据进行总结与概括。传统的最简单的数据总结方法是计算出数据库的各个字段上的求和值、平均值、方差值等统计值,或者用直方图、饼状图等图形方式表示。分类： 根据分类模型对数据集合分类。分类属于有导师学习，一般需要有一个训练样本数据集作为输入。聚类：

根据数据的不同特征，将其划分为不同的类。无导师学习2023/1/117知识发现的任务(2)相关性分析：发现特征之间或数据之间的相互依赖关系 关联规则偏差分析：

基本思想是寻找观察结果与参照量之间的有意义的差别。通过发现异常,可以引起人们对特殊情况的加倍注意。建模： 构造描述一种活动或状态的数学模型2023/1/118知识发现的方法(1)统计方法：

传统方法： 回归分析、判别分析、聚类分析、探索性分析模糊集(fuzzyset)Zadeh1965支持向量机(SupportVectorMachine)Vapnik90年代初粗糙集(RoughSet)Pawlak80年代初2023/1/119知识发现的方法(2)机器学习：

规则归纳：AQ算法决策树：ID3、C4.5范例推理:CBR遗传算法:GA贝叶斯信念网络2023/1/1110知识发现的方方法(3)神经计算：神经网络是指指一类新的计计算模型，它它是模仿人脑脑神经网络的的结构和某些些工作机制而而建立的一种种计算模型。。常用的模型型：Hopfield网多层感知机自组织特征映映射反传网络可视化：2022/12/3011KDD的技术难点动态变化的数数据噪声数据不完整冗余信息数据稀疏超大数据量2022/12/3012关联规则属于知识发现现任务中的相相关性分析由于条形码技技术的发展,零售部门可可以利用前端端收款机收集集存储大量的的售货数据。。因此,如果果对这些历史史事务数据进进行分析,则则可对顾客的的购买行为提提供极有价值值的信息。例例如,可以帮帮助如何摆放放货架上的商商品(如把顾顾客经常同时时买的商品放放在一起),帮助如何规规划市场(怎怎样相互搭配配进货)。2022/12/3013关联规规则的的表示示关联规规则的的形式式如“在购买买面包包顾客客中,有70%的人人同时时也买买了黄黄油””,可可以表表示成成：面包→→黄油油。用于关关联规规则发发现的的主要要对象象是事事务型型数据据库,其中中针对对的应应用则则是售售货数数据,也称称货篮篮数据据。一一个事事务一一般由由如下下几个个部分分组成成:事事务处处理时时间,一一组顾顾客购购买的的物品品,有有时也也有顾顾客标标识号号(如如信用用卡号号)。。2022/12/3014关联规规则的的相关关概念念(1)设R={I1,I2……Im}是一组组物品品集，，W是一组组事务务集。。W中的每每个事事务T是一组组物品品，TR。假设有有一个个物品品集A，一个事事务T，如果AT，则称事事务T支持物物品集集A。关联规规则是是如下下形式式的一一种蕴蕴含：：A→B，其中A、B是两组组物品品，AI，BI，且A∩B=。2022/12/3015关联联规规则则的的相相关关概概念念(2)支持持度度物品品集集A的支支持持度度：：称称物物品品集集A具有有大大小小为为s的支支持持度度,如如果果D中有有s%的事事务务支支持持物物品品集集XP(A)1000个顾顾客客购购物物，，其其中中200个顾顾客客购购买买了了面面包包，，支持持度度就就是是20％（（200/1000）。。关联联规规则则A→→B的支支持持度度：：关关联联规规则则A→→B在事事务务数数据据库库W中具具有有大大小小为为s的支支持持度度,如如果果物物品品集集A∪∪B的支支持持度度为为s100个顾顾客客购购买买了了面面包包和和黄黄油油，，则则面面包包→黄油油10％％2022/12/3016关联联规规则则的的相相关关概概念念(3)可信信度度设W中支支持持物物品品集集A的事事务务中中，，有有c％％的事事务务同同时时也也支支持持物物品品集集B，，c％％称为为关关联联规规则则A→→B的可可信信度度。。P(B|A)1000个顾顾客客购购物物，，200个顾顾客客购购买买了了面面包包，，其其中中140个个买买了了黄黄油油，，则则可可信信度度是是70％（（140/200）。。2022/12/3017关联联规规则则的的相相关关概概念念(4)最小小支支持持度度minsup用户户规规定定的的关关联联规规则则必必须须满满足足的的最最小小支支持持度度。。最小小可可信信度度minconf用户户规规定定的的关关联联规规则则必必须须满满足足的的最最小小可可信信度度。。大项项集集(大大项项集集、、大大物物品品集集largeitemset)支持持度度不不小小于于最最小小支支持持度度minsup的物物品品集集2022/12/3018关联规则则发现任任务给定一个个事务数数据库D，求出所有有满足最最小支持持度和最最小可信信度的关关联规则则。该问问题可以以分解为为两个子子问题：：求出D中满足最最小支持持度的所所有大项项集；利用大项项集生成成满足最最小可信信度的所所有关联联规则。。对于每每个大项项集A，若BA，B≠≠φ，且Confidence（B(AB)）minconf，则构成关关联规则则B(AB)2022/12/3019关联规则则发现的的基本思思路第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)，继续。2022/12/3020思路的正确性性利用了大物品品集向下封闭闭性，即大物物品集X的任意子集一一定是大物品品集，反过来来说，如果X有一子集不是是大项集，则则X肯定不是。是宽度优先算算法2022/12/3021经典的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]∪…2022/12/3022apriori-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)2022/12/3023Prune算法：从C[k]中除去大小为为k-1且不在L[k-1]中的子集(1)Forallitemsetsc∈C[k]do(2)Forall(k-1)-subsetssofcdo(3)if(sL[k-1])(4)thendeletecfromC[k]2022/12/3024举例：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}}2022/12/30252022/12/30262022/12/30272022/12/30282022/12/3029关联联规规则则发发现现注注意意的的问问题题充分分理理解解数数据据目标标明明确确数据据准准备备工工作作要要做做好好选取取适适当当的的最最小小的的支支持持度度和和可可信信度度很好好地地理理解解关关联联规规则则2022/12/3030关联联规规则则发发现现使使用用步步骤骤连接接数数据据，，做做数数据据准准备备给定定最最小小支支持持度度和和最最小小可可信信度度，，利利用用知知识识发发现现工工具具提提供供的的算算法法发发现现关关联联规规则则可视视化化显显示示、、理理解解、、评评估估关关联联规规则则2022/12/3031关联规则在保保险业务中的的应用最小支持度1%，最小可可信度为50%2022/12/30322022/12/30332022/12/30342022/12/3035数据据仓仓库库在过过去去几几十十年年，，数数据据库库技技术术，，特特别别是是OLTP（联机机事事务务处处理理）），，主主要要是是为为自自动动化化生生产产、、精精简简工工作作任任务务和和高高速速采采集集数数据据服服务务。。它它是是事事务务驱驱动动的的、、面面向向应应用用的的。。20世世纪纪80年年代代，，人人们们要要利利用用现现有有的的数数据据，，进进行行分分析析和和推推理理，，从从而而为为决决策策提提供供依依据据。。这这种种需需求求既既要要求求联联机机服服务务，，又又涉涉及及大大量量用用于于决决策策的的数数据据。。而而传传统统的的数数据据库库系系统统已已无无法法满满足足这这种种需需求求：：所需需历历史史数数据据量量很很大大，，而而传传统统数数据据库库一一般般只只存存储储短短期期数数据据。。涉及及许许多多部部门门的的数数据据，，而而不不同同系系统统的的数数据据难难以以集集成成。。对大大量量数数据据的的访访问问性性能能明明显显下下降降2022/12/3036数据仓库库的定义义信息处理理技术的的发展趋趋势是：：从大量量的事务务型数据据库中抽抽取数据据，并将将其清理理、转换换为新的的存储格格。随着着此过程程的发展展和完善善，这种种九十年年代初出出现的支支持决策策的、特特殊的数数据存储储即被称称为数据据仓库（（DataWarehouse）。。Inmon将数据仓仓库明确确定义为为：数据仓库库（DataWarehouse）是面向主主题的，，集成的的，内容容相对稳稳定的、、不同时时间的数数据集合合，用以以支持经经营管理理中的决决策制定定过程。。2022/12/3037数据仓库库的特征征(1)数据仓库库中的数数据是面面向主题题的与传统数数据库面面向应用用相对应应的。主主题是一一个在较较高层次次将数据据归类的的标准，，每一个个主题基基本对应应一个宏宏观的分分析领域域数据仓库库中的数数据是集集成的在数据进进入数据据仓库之之前，必必然要经经过加工工与集成成。要统统一原始始数据中中的所有有矛盾之之处，还还要进行行数据综综合和计计算2022/12/3038数据仓仓库的的特征征(2)数据仓仓库中中的数数据是是稳定定的数据仓仓库的的数据据主要要供决决策分分析之之用，，所涉涉及的的操作作主要要是数数据查查询，，一般般不进进行修修改操操作数据仓仓库中中的数数据又又是随随时间间不断断变化化的数据仓仓库的的数据据不是是实时时更新新的，，但并并不是是永远远不变变的，，也要要随着着时间间的变变化不不断地地更新新、增增删和和重新新综合合。更新周周期2022/12/3039元数据据元数据据（Metadata））是关于于数据据的数数据，，它描描述了了数据据的结结构、、内容容、编编码、、索引引等内内容。。传统统数据据库中中的数数据字字典是是一种种元数数据，，但在在数据据仓库库中，，元数数据的的内容容比数数据库库中的的数据据字典典更加加丰富富和复复杂。。设计计一个个描述述能力力强、、内容容完善善的元元数据据，是是有效效管理理数据据仓库库的具具有决决定意意义的的重要要前提提2022/12/3040元数据据的重重要性性数据仓仓库使使用者者往往往将使使用元元数据据作为为分析析的第第一步步。元元数据据如同同数据据指示示图，，指出出了数数据仓仓库内内各种种信息息的位位置和和含义义从操作型数数据环境到到数据仓库库的数据转转换是复杂杂的、多方方面的，是是数据仓库库建设的关关键性步骤骤，元数据据要包含对对这种转换换的清晰描描述，保证证这种转换换是正确、、适当和合合理的，并并且是灵活活可变的元数据还管管理粒度的的划分、索索引的建立立以及抽取取更新的周周期等，以以便管理好好数据仓库库中的大规规模数据2022/12/3041数据仓库的的相关概念念事实表（Fact））：存储用户需需要查询分分析的数据据，事实表表中一般包包含多个维维（Dimension）和度量（Measurement）。。维：代表了用户户观察数据据的特定视视角，如：：时间维、、地区维、、产品维等等。每一个个维可划分分为不同的的层次来取取值，如时时间维的值值可按年份份、季度、、月份来划划分，描述述了不同的的查询层次次。度量：是数数据的实际际意义，描描述数据““是什么””，即一个个数值的测测量指标，，如：人数数、单价、、销售量等等。2022/12/3042数据仓库的的建模模型型度量的实际际数据存放放在事实表表中。维的的详细信息息，如不同同的层次划划分和相应应数据等在在维表中存存储，事实实表中存放放各个维的的标识码键键。事实表表和维表将将通过这些些键关联起起来，构成成一种星型模型对于层次复复杂的维,为避免冗冗余数据占占用过大的的存储空间间,可以使使用多个表表来描述,这种星型型模式的扩扩展称为雪花模型2022/12/3043OLAP数据据仓仓库库技技术术中中，，多多维维数数据据分分析析（（MultidimensionalDataAnalysis））方法法是是一一种种重重要要的的技技术术，，也也称称作作联联机机分分析析处处理理（（On-LineAnalyticalProcessing，，简称称OLAP））或数数据据立立方方体体（（DataCube））方法法，，主要要是是指指通通过过各各种种即即席席复复杂杂查查询询，，对对数数据据仓仓库库中中存存储储的的数数据据进进行行各各种种统统计计分分析析的的应应用用数据据仓仓库库是是面面向向决决策策支支持持的的，，决决策策的的前前提提是是数数据据分分析析。。在在数数据据分分析析中中经经常常要要用用到到诸诸如如求求和和、、总总计计、、平平均均、、最最大大、、最最小小等等汇汇集集操操作作，，这这类类操操作作的的计计算算量量特特别别大大。2022/12/3044OLAP的类类型型ROLAP：：数据据保保留留在在原原有有的的关关系系型型结结构构中中，，并并且且将将聚聚合合表表也也存存储储在在关关系系数数据据库库,在技技术术成成熟熟及及各各方方面面的的适适应应性性上上较较之之MOLAP占有有一一定定的的优优势势，，性性能能较较差差MOLAP:数据据和和聚聚合合都都存存储储在在多多维维结结构构中中，，效率率较较高高，便便于于进进行行优优化化操操作作。。维维数数多多数数据据量量大大时时，，存存储储是是难难点点。。HOALP:数据据保保留留在在原原有有的的关关系系型型结结构构中中，，聚聚合合存存储储在在多多维维结结构构。。结结合合ROLAP和MOLAP两者者的的优优点点2022/12/3045OLAP的分分析析操操作作OLAP的基基本本多多维维分分析析操操作作有有钻钻取取（（rollup和drilldown））、、切片片（（slice））和切切块块（（dice））、、以及及旋旋转转（（pivot)等。。钻取取是是改改变变维维的的层层次次，，变变换换分分析析的的粒粒度度。。它它包包括括向向上上钻钻取取和和向向下下钻钻取取。rollup是在在某某一一维维上上将将低低层层次次的的细细节节数数据据概概括括到到高高层层次次的的汇汇总总数数据据；；而而drilldown则相相反反，，它它从从汇汇总总数数据据深深入入到到细细节节数数据据进进行行观观察察切片片和和切切块块是是在在一一部部分分维维上上选选定定值值后后，，关关心心度度量量数数据据在在剩剩余余维维上上的的分分布布。。如如果果剩剩余余的的维维只只有有两两个个，，则则是是切切片片，，否否则则是是切切块块旋转转是是变变换换维维的的方方向向，，即即在在表表格格中中重重新新安安排排维维的的放放置置（（例例如如行行列列互互换换2022/12/3046数据仓仓库和和知识识发现现技术术的结结合(1)知识发发现成成为数数据仓仓库中中进行行数据据深层层分析析的一一种必必不可可少的的手段段数据仓仓库是是面向向决策策分析析的，，数据据仓库库从事事务型型数据据抽取取并集集成得得到的的分析析型数数据后后，需需要各各种决决策分分析工工具对对这些些数据据进行行分析析和挖挖掘，，得到到有用用的决决策信信息。。而知知识发发现技技术具具备从从大量量数据据中发发现有有用信信息的的能力力。2022/12/3047数据仓仓库和和知识识发现现技术术的结结合(2)数据仓仓库为为知识识发现现提供供经过过良好好预处处理的的数据据源知识发发现往往往依依赖于于经过过良好好组织织和预预处理理的数数据源源，数数据的的好坏坏直接接影响响知识识发现现的效效果。。数据仓仓库具具有从从各种种数据据源中中抽取取数据据，并并对数数据进进行清清洗、、聚集集和转转换等等各种种处理理的能能力2022/12/3048一、数数据挖挖掘概概念----发发展1989IJCAI会议：：数数据库库中的的知识识发现现讨论论专题题KnowledgeDiscoveryinDatabases(G.Piatetsky-ShapiroandW.Frawley,1991)1991-1994KDD讨论专专题AdvancesinKnowledgeDiscoveryandDataMining(U.Fayyad,G.Piatetsky-Shapiro,P.Smyth,andR.Uthurusamy,1996)1995-1998KDD国际会会议(KDD’95-98)JournalofDataMiningandKnowledgeDiscovery(1997)1998ACMSIGKDD,SIGKDD’1999-2002会议,以及及SIGKDDExplorations数据挖挖掘方方面更更多的的国际际会议议PAKDD,PKDD,SIAM-DataMining,(IEEE)ICDM,DaWaK,SPIE-DM,etc.2022/12/3049二、、数数据据挖挖掘掘软软件件的的发发展展代特征数据挖掘算法集成分布计算模型数据模型第一代作为一个独立的应用支持一个或者多个算法独立的系统单个机器向量数据第二代和数据库以及数据仓库集成多个算法：能够挖掘一次不能放进内存的数据数据管理系统，包括数据库和数据仓库同质、局部区域的计算机群集有些系统支持对象,文本和连续的媒体数据第三代和预言模型系统集成

多个算法数据管理和预言模型系统intranet/extranet网络计算支持半结构化数据和web数据第四代和移动数据/各种计算设备的数据联合

多个算法数据管理、预言模型、移动系统移动和各种计算设备普遍存在的计算模型RobertGrossman，，NationalCenterforDataMiningUniversityofIllinoisatChicago的观观点点2022/12/3050二、、数数据据挖挖掘掘软软件件的的发发展展第一一代代数数据据挖挖掘掘软软件件2022/12/3051二、、数数据据挖挖掘掘软软件件的的发发展展第一一代代数数据据挖挖掘掘软软件件CBA新加加坡坡国国立立大大学学。。基于于关关联联规规则则的的分分类类算算法法，，能能从从关关系系数数据据或或者者