数据挖掘培训ppt课件.ppt

第九章知识发现和数据挖掘 数据库中知识发现 1 知识发现关联规则数据仓库知识发现工具 2 知识发现 知识发现是指从数据集中抽取和精炼新的模式 范围非常广泛 经济 工业 农业 军事 社会数据的形态多样化 数字 符号 图形 图像 声音数据组织各不相同 结构化 半结构化和非结构发现的知识可以表示成各种形式规则 科学规律 方程或概念网 3 数据库知识发现 目前 关系型数据库技术成熟 应用广泛 因此 数据库知识发现 KnowledgeDiscoveryinDatabasesKDD 的研究非常活跃 该术语于1989年出现 Fayyad定义为 KDD是从数据集中识别出有效的 新颖的 潜在有用的 以及最终可理解的模式的非平凡过程 4 不同的术语名称 知识发现是一门来自不同领域的研究者关注的交叉性学科 因此导致了很多不同的术语名称 知识发现 人工智能和机器学习界 数据挖掘 datamining 统计界 数据分析 数据库和管理信息系统界知识抽取 informationextraction 信息发现 informationdiscovery 智能数据分析 intelligentdataanalysis 探索式数据分析 exploratorydataanalysis 信息收获 informationharvesting 数据考古 dataarcheology 5 6 知识发现的任务 1 数据总结 对数据进行总结与概括 传统的最简单的数据总结方法是计算出数据库的各个字段上的求和值 平均值 方差值等统计值 或者用直方图 饼状图等图形方式表示 分类 根据分类模型对数据集合分类 分类属于有导师学习 一般需要有一个训练样本数据集作为输入 聚类 根据数据的不同特征 将其划分为不同的类 无导师学习 7 知识发现的任务 2 相关性分析 发现特征之间或数据之间的相互依赖关系关联规则偏差分析 基本思想是寻找观察结果与参照量之间的有意义的差别 通过发现异常 可以引起人们对特殊情况的加倍注意 建模 构造描述一种活动或状态的数学模型 8 知识发现的方法 1 统计方法 传统方法 回归分析 判别分析 聚类分析 探索性分析模糊集 fuzzyset Zadeh1965支持向量机 SupportVectorMachine Vapnik90年代初粗糙集 RoughSet Pawlak80年代初 9 知识发现的方法 2 机器学习 规则归纳 AQ算法决策树 ID3 C4 5范例推理 CBR遗传算法 GA贝叶斯信念网络 10 知识发现的方法 3 神经计算 神经网络是指一类新的计算模型 它是模仿人脑神经网络的结构和某些工作机制而建立的一种计算模型 常用的模型 Hopfield网多层感知机自组织特征映射反传网络 可视化 11 KDD的技术难点 动态变化的数据噪声数据不完整冗余信息数据稀疏超大数据量 12 关联规则 属于知识发现任务中的相关性分析由于条形码技术的发展 零售部门可以利用前端收款机收集存储大量的售货数据 因此 如果对这些历史事务数据进行分析 则可对顾客的购买行为提供极有价值的信息 例如 可以帮助如何摆放货架上的商品 如把顾客经常同时买的商品放在一起 帮助如何规划市场 怎样相互搭配进货 13 关联规则的表示 关联规则的形式如 在购买面包顾客中 有70 的人同时也买了黄油 可以表示成 面包 黄油 用于关联规则发现的主要对象是事务型数据库 其中针对的应用则是售货数据 也称货篮数据 一个事务一般由如下几个部分组成 事务处理时间 一组顾客购买的物品 有时也有顾客标识号 如信用卡号 14 关联规则的相关概念 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 15 关联规则的相关概念 2 支持度物品集A的支持度 称物品集A具有大小为s的支持度 如果D中有s 的事务支持物品集XP A 1000个顾客购物 其中200个顾客购买了面包 支持度就是20 200 1000 关联规则A B的支持度 关联规则A B在事务数据库W中具有大小为s的支持度 如果物品集A B的支持度为s100个顾客购买了面包和黄油 则面包 黄油10 16 关联规则的相关概念 3 可信度设W中支持物品集A的事务中 有c 的事务同时也支持物品集B c 称为关联规则A B的可信度 P B A 1000个顾客购物 200个顾客购买了面包 其中140个买了黄油 则可信度是70 140 200 17 关联规则的相关概念 4 最小支持度minsup用户规定的关联规则必须满足的最小支持度 最小可信度minconf用户规定的关联规则必须满足的最小可信度 大项集 大项集 大物品集largeitemset 支持度不小于最小支持度minsup的物品集 18 关联规则发现任务 给定一个事务数据库D 求出所有满足最小支持度和最小可信度的关联规则 该问题可以分解为两个子问题 求出D中满足最小支持度的所有大项集 利用大项集生成满足最小可信度的所有关联规则 对于每个大项集A 若B A B 且Confidence B A B minconf 则构成关联规则B A B 19 关联规则发现的基本思路 第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 继续 20 思路的正确性 利用了大物品集向下封闭性 即大物品集X的任意子集一定是大物品集 反过来说 如果X有一子集不是大项集 则X肯定不是 是宽度优先算法 21 经典的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 22 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 23 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 24 举例 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 25 26 27 28 29 关联规则发现注意的问题 充分理解数据目标明确数据准备工作要做好选取适当的最小的支持度和可信度很好地理解关联规则 30 关联规则发现使用步骤 连接数据 做数据准备给定最小支持度和最小可信度 利用知识发现工具提供的算法发现关联规则可视化显示 理解 评估关联规则 31 关联规则在保险业务中的应用 最小支持度1 最小可信度为50 32 33 34 35 数据仓库 在过去几十年 数据库技术 特别是OLTP 联机事务处理 主要是为自动化生产 精简工作任务和高速采集数据服务 它是事务驱动的 面向应用的 20世纪80年代 人们要利用现有的数据 进行分析和推理 从而为决策提供依据 这种需求既要求联机服务 又涉及大量用于决策的数据 而传统的数据库系统已无法满足这种需求 所需历史数据量很大 而传统数据库一般只存储短期数据 涉及许多部门的数据 而不同系统的数据难以集成 对大量数据的访问性能明显下降 36 数据仓库的定义 信息处理技术的发展趋势是 从大量的事务型数据库中抽取数据 并将其清理 转换为新的存储格 随着此过程的发展和完善 这种九十年代初出现的支持决策的 特殊的数据存储即被称为数据仓库 DataWarehouse Inmon将数据仓库明确定义为 数据仓库 DataWarehouse 是面向主题的 集成的 内容相对稳定的 不同时间的数据集合 用以支持经营管理中的决策制定过程 37 数据仓库的特征 1 数据仓库中的数据是面向主题的与传统数据库面向应用相对应的 主题是一个在较高层次将数据归类的标准 每一个主题基本对应一个宏观的分析领域数据仓库中的数据是集成的在数据进入数据仓库之前 必然要经过加工与集成 要统一原始数据中的所有矛盾之处 还要进行数据综合和计算 38 数据仓库的特征 2 数据仓库中的数据是稳定的数据仓库的数据主要供决策分析之用 所涉及的操作主要是数据查询 一般不进行修改操作数据仓库中的数据又是随时间不断变化的数据仓库的数据不是实时更新的 但并不是永远不变的 也要随着时间的变化不断地更新 增删和重新综合 更新周期 39 元数据 元数据 Metadata 是关于数据的数据 它描述了数据的结构 内容 编码 索引等内容 传统数据库中的数据字典是一种元数据 但在数据仓库中 元数据的内容比数据库中的数据字典更加丰富和复杂 设计一个描述能力强 内容完善的元数据 是有效管理数据仓库的具有决定意义的重要前提 40 元数据的重要性 数据仓库使用者往往将使用元数据作为分析的第一步 元数据如同数据指示图 指出了数据仓库内各种信息的位置和含义从操作型数据环境到数据仓库的数据转换是复杂的 多方面的 是数据仓库建设的关键性步骤 元数据要包含对这种转换的清晰描述 保证这种转换是正确 适当和合理的 并且是灵活可变的元数据还管理粒度的划分 索引的建立以及抽取更新的周期等 以便管理好数据仓库中的大规模数据 41 数据仓库的相关概念 事实表 Fact 存储用户需要查询分析的数据 事实表中一般包含多个维 Dimension 和度量 Measurement 维 代表了用户观察数据的特定视角 如 时间维 地区维 产品维等 每一个维可划分为不同的层次来取值 如时间维的值可按年份 季度 月份来划分 描述了不同的查询层次 度量 是数据的实际意义 描述数据 是什么 即一个数值的测量指标 如 人数 单价 销售量等 42 数据仓库的建模模型 度量的实际数据存放在事实表中 维的详细信息 如不同的层次划分和相应数据等在维表中存储 事实表中存放各个维的标识码键 事实表和维表将通过这些键关联起来 构成一种星型模型对于层次复杂的维 为避免冗余数据占用过大的存储空间 可以使用多个表来描述 这种星型模式的扩展称为雪花模型 43 OLAP 数据仓库技术中 多维数据分析 MultidimensionalDataAnalysis 方法是一种重要的技术 也称作联机分析处理 On LineAnalyticalProcessing 简称OLAP 或数据立方体 DataCube 方法 主要是指通过各种即席复杂查询 对数据仓库中存储的数据进行各种统计分析的应用数据仓库是面向决策支持的 决策的前提是数据分析 在数据分析中经常要用到诸如求和 总计 平均 最大 最小等汇集操作 这类操作的计算量特别大 44 OLAP的类型 ROLAP 数据保留在原有的关系型结构中 并且将聚合表也存储在关系数据库 在技术成熟及各方面的适应性上较之MOLAP占有一定的优势 性能较差MOLAP 数据和聚合都存储在多维结构中 效率较高 便于进行优化操作 维数多数据量大时 存储是难点 HOALP 数据保留在原有的关系型结构中 聚合存储在多维结构 结合ROLAP和MOLAP两者的优点 45 OLAP的分析操作 OLAP的基本多维分析操作有钻取 rollup和drilldown 切片 slice 和切块 dice 以及旋转 pivot 等 钻取是改变维的层次 变换分析的粒度 它包括向上钻取和向下钻取 rollup是在某一维上将低层次的细节数据概括到高层次的汇总数据 而drilldown则相反 它从汇总数据深入到细节数据进行观察切片和切块是在一部分维上选定值后 关心度量数据在剩余维上的分布 如果剩余的维只有两个 则是切片 否则是切块旋转是变换维的方向 即在表格中重新安排维的放置 例如行列互换 46 数据仓库和知识发现技术的结合 1 知识发现成为数据仓库中进行数据深层分析的一种必不可少的手段数据仓库是面向决策分析的 数据仓库从事务型数据抽取并集成得到的分析型数据后 需要各种决策分析工具对这些数据进行分析和挖掘 得到有用的决策信息 而知识发现技术具备从大量数据中发现有用信息的能力 47 数据仓库和知识发现技术的结合 2 数据仓库为知识发现提供经过良好预处理的数据源知识发现往往依赖于经过良好组织和预处理的数据源 数据的好坏直接影响知识发现的效果 数据仓库具有从各种数据源中抽取数据 并对数据进行清洗 聚集和转换等各种处理的能力 48 一 数据挖掘概念 发展 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 49 二 数据挖掘软件的发展 RobertGrossman NationalCenterforDataMiningUniversityofIllinoisatChicago的观点 50 二 数据挖掘软件的发展 第一代数据挖掘软件 特点支持一个或少数几个数据挖掘算法挖掘向量数据 vector valueddata 数据一般一次性调进内存进行处理典型的系统如SalfordSystems公司早期的CART系统 www salford 缺陷如果数据足够大 并且频繁的变化 这就需要利用数据库或者数据仓库技术进行管理 第一代系统显然不能满足需求 51 二 数据挖掘软件的发展 第一代数据挖掘软件CBA新加坡国立大学 基于关联规则的分类算法 能从关系数据或者交易数据中挖掘关联规则 使用关联规则进行分类和预测 52 二 数据挖掘软件的发展 第二代数据挖掘软件 特点与数据库管理系统 DBMS 集成支持数据库和数据仓库 和它们具有高性能的接口 具有高的可扩展性能够挖掘大数据集 以及更复杂的数据集通过支持数据挖掘模式 datamining