aai知识发现和数据挖掘1高级人工智能

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

史忠植中科院计算所2024/1/61高级人工智能史忠植知识发现关联规那么数据仓库知识发现工具2024/1/62高级人工智能史忠植知识发现知识发现是指从数据集中抽取和精炼新的方式。范围非常广泛：经济、工业、农业、军事、社会数据的形状多样化：数字、符号、图形、图像、声音数据组织各不一样：构造化、半构造化和非构造发现的知识可以表示成各种方式 规那么、科学规律、方程或概念网。2024/1/63高级人工智能史忠植数据库知识发现目前,关系型数据库技术成熟、运用广泛。因此,数据库知识发现(KnowledgeDiscoveryinDatabasesKDD)的研讨非常活泼。该术语于1989年出现，Fayyad定义为“KDD是从数据集中识别出有效的、新颖的、潜在有用的，以及最终可了解的方式的非平凡过程〞2024/1/64高级人工智能史忠植不同的术语称号知识发现是一门来自不同领域的研讨者关注的交叉性学科，因此导致了很多不同的术语称号。知识发现:人工智能和机器学习界。数据发掘(datamining): 统计界、数据分析、数据库和管理信息系统界知识抽取(informationextraction)、信息发现(informationdiscovery)、智能数据分析(intelligentdataanalysis)、探求式数据分析(exploratorydataanalysis)信息收获(informationharvesting)数据考古(dataarcheology)2024/1/65高级人工智能史忠植2024/1/66高级人工智能史忠植知识发现的义务(1)数据总结：对数据进展总结与概括。传统的最简单的数据总结方法是计算出数据库的各个字段上的求和值、平均值、方差值等统计值,或者用直方图、饼状图等图形方式表示。分类： 根据分类模型对数据集合分类。分类属于有导师学习，普通需求有一个训练样本数据集作为输入。聚类： 根据数据的不同特征，将其划分为不同的类。无导师学习2024/1/67高级人工智能史忠植知识发现的义务(2)相关性分析：发现特征之间或数据之间的相互依赖关系 关联规那么偏向分析： 根本思想是寻觅察看结果与参照量之间的有意义的差别。经过发现异常,可以引起人们对特殊情况的加倍留意。建模： 构造描画一种活动或形状的数学模型2024/1/68高级人工智能史忠植知识发现的方法(1)统计方法： 传统方法： 回归分析、判别分析、聚类分析、探求性分析模糊集(fuzzyset)Zadeh1965支持向量机(SupportVectorMachine)Vapnik90年代初粗糙集(RoughSet)Pawlak80年代初2024/1/69高级人工智能史忠植知识发现的方法(2)机器学习： 规那么归纳：AQ算法决策树：ID3、C4.5范例推理:CBR遗传算法:GA贝叶斯信心网络2024/1/610高级人工智能史忠植知识发现的方法(3)神经计算： 神经网络是指一类新的计算模型，它是模拟人脑神经网络的构造和某些任务机制而建立的一种计算模型。常用的模型：Hopfield网多层感知机自组织特征映射反传网络可视化： 2024/1/611高级人工智能史忠植KDD的技术难点动态变化的数据噪声数据不完好冗余信息数据稀疏超大数据量2024/1/612高级人工智能史忠植关联规那么属于知识发现义务中的相关性分析由于条形码技术的开展,零售部门可以利用前端收款机搜集存储大量的售货数据。因此,假设对这些历史事务数据进展分析,那么可对顾客的购买行为提供极有价值的信息。例如,可以协助如何摆放货架上的商品(如把顾客经常同时买的商品放在一同),协助如何规划市场(怎样相互搭配进货)。2024/1/613高级人工智能史忠植关联规那么的表示关联规那么的方式如“在购买面包顾客中,有70%的人同时也买了黄油〞,可以表示成：面包→黄油。用于关联规那么发现的主要对象是事务型数据库,其中针对的运用那么是售货数据,也称货篮数据。一个事务普通由如下几个部分组成:事务处置时间,一组顾客购买的物品,有时也有顾客标识号(如信誉卡号)。2024/1/614高级人工智能史忠植关联规那么的相关概念(1)设R={I1,I2……Im}是一组物品集，W是一组事务集。W中的每个事务T是一组物品，TR。假设有一个物品集A，一个事务T，假设AT，那么称事务T支持物品集A。关联规那么是如下方式的一种蕴含：A→B，其中A、B是两组物品，AI，BI，且A∩B=。2024/1/615高级人工智能史忠植关联规那么的相关概念(2)支持度物品集A的支持度：称物品集A具有大小为s的支持度,假设D中有s%的事务支持物品集XP(A)1000个顾客购物，其中200个顾客购买了面包，支持度就是20％〔200/1000〕。关联规那么A→B的支持度：关联规那么A→B在事务数据库W中具有大小为s的支持度,假设物品集A∪B的支持度为s100个顾客购买了面包和黄油，那么面包→黄油10％2024/1/616高级人工智能史忠植关联规那么的相关概念(3)可信度设W中支持物品集A的事务中，有c％的事务同时也支持物品集B，c％称为关联规那么A→B的可信度。P(B|A)1000个顾客购物，200个顾客购买了面包，其中140个买了黄油，那么可信度是70％〔140/200〕。2024/1/617高级人工智能史忠植关联规那么的相关概念(4)最小支持度minsup用户规定的关联规那么必需满足的最小支持度。最小可信度minconf用户规定的关联规那么必需满足的最小可信度。大项集(大项集、大物品集largeitemset)支持度不小于最小支持度minsup的物品集2024/1/618高级人工智能史忠植关联规那么发现义务给定一个事务数据库D，求出一切满足最小支持度和最小可信度的关联规那么。该问题可以分解为两个子问题：求出D中满足最小支持度的一切大项集；利用大项集生成满足最小可信度的一切关联规那么。对于每个大项集A，假设BA，B≠φ，且Confidence〔B(AB)〕minconf，那么构成关联规那么B(AB)2024/1/619高级人工智能史忠植关联规那么发现的根本思绪第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)，继续。2024/1/620高级人工智能史忠植思绪的正确性利用了大物品集向下封锁性，即大物品集X的恣意子集一定是大物品集，反过来说，假设X有一子集不是大项集，那么X一定不是。是宽度优先算法2024/1/621高级人工智能史忠植经典的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]∪…2024/1/622高级人工智能史忠植apriori-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)2024/1/623高级人工智能史忠植Prune算法：从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]2024/1/624高级人工智能史忠植举例：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}}2024/1/625高级人工智能史忠植2024/1/626高级人工智能史忠植2024/1/627高级人工智能史忠植2024/1/628高级人工智能史忠植2024/1/629高级人工智能史忠植关联规那么发现留意的问题充分了解数据目的明确数据预备任务要做好选取适当的最小的支持度和可信度很好地了解关联规那么2024/1/630高级人工智能史忠植关联规那么发现运用步骤衔接数据，做数据预备给定最小支持度和最小可信度，利用知识发现工具提供的算法发现关联规那么可视化显示、了解、评价关联规那么2024/1/631高级人工智能史忠植关联规那么在保险业务中的运用最小支持度1%，最小可信度为50%2024/1/632高级人工智能史忠植2024/1/633高级人工智能史忠植2024/1/634高级人工智能史忠植2024/1/635高级人工智能史忠植数据仓库在过去几十年，数据库技术，特别是OLTP〔联机事务处置〕，主要是为自动化消费、精简任务义务和高速采集数据效力。它是事务驱动的、面向运用的。20世纪80年代，人们要利用现有的数据，进展分析和推理，从而为决策提供根据。这种需求既要求联机效力，又涉及大量用于决策的数据。而传统的数据库系统已无法满足这种需求：所需历史数据量很大，而传统数据库普通只存储短期数据。涉及许多部门的数据，而不同系统的数据难以集成。对大量数据的访问性能明显下降2024/1/636高级人工智能史忠植数据仓库的定义信息处置技术的开展趋势是：从大量的事务型数据库中抽取数据，并将其清理、转换为新的存储格。随着此过程的开展和完善，这种九十年代初出现的支持决策的、特殊的数据存储即被称为数据仓库〔DataWarehouse〕。Inmon将数据仓库明确定义为：数据仓库〔DataWarehouse〕是面向主题的，集成的，内容相对稳定的、不同时间的数据集合，用以支持运营管理中的决策制定过程。2024/1/637高级人工智能史忠植数据仓库的特征(1)数据仓库中的数据是面向主题的与传统数据库面向运用相对应的。主题是一个在较高层次将数据归类的规范，每一个主题根本对应一个宏观的分析领域数据仓库中的数据是集成的在数据进入数据仓库之前，必然要经过加工与集成。要一致原始数据中的一切矛盾之处，还要进展数据综合和计算2024/1/638高级人工智能史忠植数据仓库的特征(2)数据仓库中的数据是稳定的数据仓库的数据主要供决策分析之用，所涉及的操作主要是数据查询，普通不进展修正操作数据仓库中的数据又是随时间不断变化的数据仓库的数据不是实时更新的，但并不是永远不变的，也要随着时间的变化不断地更新、增删和重新综合。更新周期 2024/1/639高级人工智能史忠植元数据元数据〔Metadata〕是关于数据的数据，它描画了数据的构造、内容、编码、索引等内容。传统数据库中的数据字典是一种元数据，但在数据仓库中，元数据的内容比数据库中的数据字典更加丰富和复杂。设计一个描画才干强、内容完善的元数据，是有效管理数据仓库的具有决议意义的重要前提2024/1/640高级人工智能史忠植元数据的重要性数据仓库运用者往往将运用元数据作为分析的第一步。元数据好像数据指示图，指出了数据仓库内各种信息的位置和含义从操作型数据环境到数据仓库的数据转换是复杂的、多方面的，是数据仓库建立的关键性步骤，元数据要包含对这种转换的明晰描画，保证这种转换是正确、适当和合理的，并且是灵敏可变的元数据还管理粒度的划分、索引的建立以及抽取更新的周期等，以便管理好数据仓库中的大规模数据2024/1/641高级人工智能史忠植数据仓库的相关概念现实表〔Fact〕：存储用户需求查询分析的数据，现实表中普通包含多个维〔Dimension〕和度量〔Measurement〕。维：代表了用户察看数据的特定视角，如：时间维、地域维、产品维等。每一个维可划分为不同的层次来取值，如时间维的值可按年份、季度、月份来划分，描画了不同的查询层次。度量：是数据的实践意义，描画数据“是什么〞，即一个数值的丈量目的，如：人数、单价、销售量等。2024/1/642高级人工智能史忠植数据仓库的建模模型度量的实践数据存放在现实表中。维的详细信息，如不同的层次划分和相应数据等在维表中存储，现实表中存放各个维的标识码键。现实表和维表将经过这些键关联起来，构成一种星型模型对于层次复杂的维,为防止冗余数据占用过大的存储空间,可以运用多个表来描画,这种星型方式的扩展称为雪花模型2024/1/643高级人工智能史忠植OLAP数据仓库技术中，多维数据分析〔MultidimensionalDataAnalysis〕方法是一种重要的技术，也称作联机分析处置〔On-LineAnalyticalProcessing，简称OLAP〕或数据立方体〔DataCube〕方法，主要是指经过各种即席复杂查询，对数据仓库中存储的数据进展各种统计分析的运用数据仓库是面向决策支持的，决策的前提是数据分析。在数据分析中经常要用到诸如求和、总计、平均、最大、最小等聚集操作，这类操作的计算量特别大。2024/1/644高级人工智能史忠植OLAP的类型ROLAP：数据保管在原有的关系型构造中，并且将聚合表也存储在关系数据库,在技术成熟及各方面的顺应性上较之MOLAP占有一定的优势，性能较差MOLAP:数据和聚合都存储在多维构造中，效率较高，便于进展优化操作。维数多数据量大时，存储是难点。HOALP:数据保管在原有的关系型构造中，聚合存储在多维构造。结合ROLAP和MOLAP两者的优点2024/1/645高级人工智能史忠植OLAP的分析操作OLAP的根本多维分析操作有钻取〔rollup和drilldown〕、切片〔slice〕和切块〔dice〕、以及旋转〔pivot)等。钻取是改动维的层次，变换分析的粒度。它包括向上钻取和向下钻取。rollup是在某一维上将低层次的细节数据概括到高层次的汇总数据；而drilldown那么相反，它从汇总数据深化到细节数据进展察看切片和切块是在一部分维上选定值后，关怀度量数据在剩余维上的分布。假设剩余的维只需两个，那么是切片，否那么是切块旋转是变换维的方向，即在表格中重新安排维的放置〔例如行列互换2024/1/646高级人工智能史忠植数据仓库和知识发现技术的结合(1)知识发现成为数据仓库中进展数据深层分析的一种必不可少的手段数据仓库是面向决策分析的，数据仓库从事务型数据抽取并集成得到的分析型数据后，需求各种决策分析工具对这些数据进展分析和发掘，得到有用的决策信息。而知识发现技术具备从大量数据中发现有用信息的才干。2024/1/647高级人工智能史忠植数据仓库和知识发现技术的结合(2)数据仓库为知识发现提供经过良好预处置的数据源知识发现往往依赖于经过良好组织和预处置的数据源，数据的好坏直接影响知识发现的效果。数据仓库具有从各种数据源中抽取数据，并对数据进展清洗、聚集和转换等各种处置的才干2024/1/648高级人工智能史忠植一、数据发掘概念----开展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.2024/1/649高级人工智能史忠植二、数据发掘软件的开展代特征数据发掘算法集成分布计算模型数据模型第一代作为一个独立的运用支持一个或者多个算法独立的系统单个机器向量数据第二代和数据库以及数据仓库集成多个算法：可以发掘一次不能放进内存的数据数据管理系统，包括数据库和数据仓库同质、部分区域的计算机群集有些系统支持对象,文本和延续的媒体数据第三代和预言模型系统集成多个算法数据管理和预言模型系统intranet/extranet网络计算支持半构造化数据和web数据第四代和挪动数据/各种计算设备的数据结合多个算法数据管理、预言模型、挪动系统挪动和各种计算设备普遍存在的计算模型RobertGrossman，NationalCenterforDataMiningUniversityofIllinoisatChicago的观念2024/1/650高级人工智能史忠植二、数据发掘软件的开展第一代数据发掘软件特点支持一个或少数几个数据发掘算法发掘向量数据〔vector-valueddata〕数据普通一次性调进内存进展处置典型的系统如SalfordSystems公司早期的CART系统(salford-systems)缺陷假设数据足够大，并且频繁的变化，这就需求利用数据库或者数据仓库技术进展管理，第一代系统显然不能满足需求。2024/1/651高级人工智能史忠植二、数据发掘软件的开展第一代数据发掘软件CBA新加坡国立大学。基于关联规那么的分类算法，能从关系数据或者买卖数据中发掘关联规那么，运用关联规那么进展分类和预测2024/1/652高级人工智能史忠植二、数据发掘软件的开展第二代数据发掘软件特点与数据库管理系统〔DBMS〕集成支持数据库和数据仓库，