PG平台 电子PG平台 电子下面通过一个例子来说明这种方法. 例1 假设数据库中有 9 个事务,即 D = 9 ,Apriori 假定事务中的项
按字典次序存放.下面用图示法来解释 Apriori 算法寻找 D 中的频繁 项集.
support( A B )= P ( A ∪ B ) , confidence( A B )= P( B A) 同时满足最小支持度阈值(min_sup)和最小置信度阈值(min_conf) 的规则称作强规则. 项的集合称为项集(itemset).包含 k 个项的项集称为 k -项集.项 集的出现频率是包含项集的时务数,简称为项集的频率,支持计数或 计数.项集满足最小支持度 min_sup,如果项集的出现频率大于或等 于 min_sup 与 D 中事务总数的乘积.如果项集满足最小支持度,则它 称为频繁项集(frequent itemset).频繁 k 项集的集合通常记为项集 Lk . 关联规则的挖掘是一个两步的过程: (1)找出所有频繁项集; (2)由频繁项集产生强关联规则. 3)关联规则挖掘:一个路线图 购物篮分析只是关联规则挖掘的一种形式.事实上,有许多种关
生如下: (1)对于每个频繁项集 l ,产生 l 的所有非空子集; (2)对于 l 的每个非空子集 s ,如果
如果最小置信度阈值为 70%.则只有第 2,第 3 和最后一个规则 可以输出,因为只有这些是产生的强规则.
3)提高 Apriori 算法的有效性 怎样能够提高 Apriori 算法的有效性?目前有一些变形,常见有 以下变形: (1)基于散列的技术(散列项集计数)
图3 (2)事务压缩(压缩进一步迭代扫描的事务数) :不包含任何 k 项集 的事务不可能包含任何 k 1 项集.这样,这种事务在其后的考虑时, 可以加上标记或删除,因为为产生 j 项集 ( j k ) ,扫描数据库时不再 需要它们. (3)划分(为找侯选项集划分数据)
1 什么激发了数据挖掘,为什么它是重要的 需要是发明之母.数据挖掘之所以引起信息产业界的极大关注, 其主要原因是存在大量数据,可以广泛使用,并且迫切需要将这些数 据转换成有用的信息和知识. 获取的信息和知识可以广泛地用于各种 应用,包括商务管理,生产控制,市场分析,工程设计和科学探索. 所以,数据挖掘是信息技术自然演化的结果,因而是重要的.
3 在何种数据上进行数据挖掘 原则上讲,数据挖掘可以在任何类型的信息存储上进行.它包括 以下几个方面: 1)关系数据库 2)数据仓库 3)事务数据库 4)高级数据库系统 5)展开文件和 数据挖掘功能---可以挖掘什么类型的模式 数据挖掘功能用于指定数据挖掘任务中要找的模式类型. 数据挖 掘任务一般可以分为两类:描述和预测.描述性挖掘任务刻划数据库 中数据的一般特性.预测性挖掘任务在当前数据上进行推断,并加以 预测.通常我们把它们分为以下几个类型: 1) 概念/类描述: 特征化和区分 (Characterization and Discrimination) 2)关联分析(Association Analysis) 3)分类和预测(Classification and Predict) 4)聚类分析(Clustering Analysis) 5)孤立点分析(Outlier Analysis) 6)演变分析(Evolution Analysis) 5 所有模式都是有趣的吗 答案显然是否定的.实际上,对于给定的用户,在可能产生的模 式中,只有一小部分是他感兴趣的.这就对数据挖掘系统提出了一系
关联规则挖掘的一个典型例子是购物篮分析. 该过程通过发现顾 客放入其购物篮中不同商品之间的联系,分析顾客的购买习惯.通过 了解哪些商品频繁地被顾客同时购买, 这种关联的发现可以帮助零售 商制定营销策略.这就是说,数据是事务的或关系的,如何由大量的 数据中发现关联规则?什么样的关联规则最有趣?我们如何帮助或 指导挖掘过程发现有趣的关联规则?对于关联规则挖掘, 什么样的语 言结构对于定义关联挖掘查询是有用的? 1 关联规则挖掘 1)购物篮分析:一个引发关联规则挖掘的例子
2 什么是数据挖掘 简单地说,数据挖掘是从大量数据中提取或挖掘知识.从广 义上来说,数据挖掘是从存放在数据库,数据仓库或其他信息库中的 大量数据中挖掘有趣知识的过程.基于这种观点,典型的数据挖掘系 统具有以下主要成分: 1)数据库,数据仓库或其他信息库 2)数据库或数据仓库服务器 3)知识库 4)数据挖掘引擎(用于特征化,关联,分类,聚类分析以及演变与 偏差分析) 5)模式评估模块 6)图形用户界面
4)根据应用分类(如金融,电信,股票市场,DNA,e-mail 等) 7 数据挖掘的主要问题 1)挖掘方法和用户交互问题 a.在数据库中挖掘不同类型的知识 b.多个抽象层的交互知识挖掘 c.结合背景知识 d.数据挖掘查询语言和特定的数据挖掘 e.数据挖掘结果的表示和显示 f.处理噪声和不完全数据 g.模式评估----兴趣度问题 h.数据挖掘算法的有效性和可伸缩性 I.并行,分布式和增量挖掘算法 2)关于数据库类型的多样性 a.关系的和复杂的数据类型的处理 b.由异种数据库和全球信息系统挖掘信息
联规则.根据下面的标准,关联规则有多种分类方法: (1)根据规则中所处理的值类型(如项的在与不在—布尔关联规则) (2)根据规则中涉及的数据维(分为单维关联规则和多维关联规则) (3)根据规则集所涉及的抽象层 (如 age(X,30…39) buys(X,laptop computer) (4)根据关联挖掘的各种扩充(如相关分析) 2 由事务数据库挖掘单维布尔关联规则 1)Apriori 算法:使用侯选项集找频繁项集 Apriori 算法是一种最有影响的挖掘布尔关联规则频繁项集的算 法. Apriori 性质:频繁项集的所有非空子集都必须也是频繁的. Apriori 性质基于如下观察:根据定义,如果项集 I 不满足最小支持度 阈值 min_sup,则 I 不是频繁的,即 P ( A) min_sup.如果项 A 添加到
列的问题.你可能会想: 什么样的模式是有趣的?数据挖掘系统能 够产生所有有趣的模式吗?数据挖掘系统能够仅产生有趣的模式 吗? 模式是有趣的,通常它含以下几点: (1)它易于被人理解; (2) 在某种程度上,对于新的或测试数据是有效的; (3)是潜在有用的; (4)是新颖的.这样就存在一些模式兴趣度的客观度量.这些度量 基于所发现模式的结构和关于它们的统计. 第二个问题涉及数据挖掘算法的完全性. 期望数据挖掘系统产生 所有可能的模式是不现实和低效的.实际上,应当根据用户提供的限 制和兴趣度对搜索聚焦. 第三个问题是数据挖掘的优化问题.对于数据挖掘系统,仅产生 有趣的模式是非常期望的.这对于用户和数据挖掘系统是非常有效 的, 因为这样就不需要搜索所产生的模式, 以便识别真正有趣的模式. 在这方面目前已经有了进展,然而,在数据挖掘中,这种优化仍然是 个挑战. 6 数据挖掘系统的分类 数据挖掘是一个交叉学科领域,受多个学科影响,包括数据库系 统,统计学,机器学习不,可视化和信息科学.根据不同的标准,数 据挖掘系统可以分类如下: 1) 根据挖掘的数据库类型分类(不同标准如数据模型, 涉及应用类型) 2)根据挖掘的知识类型分类(不同功能如特征化,区分,关联等) 3)根据所用的技术分类(如机器学习,统计学,可视化,模式识别)
图4 (4)选样(在给定数据的一个子集挖掘) 选取给定数据库 D 的随机样本 S ,然后,在 S 而不是在 D 中搜索 频繁项集.
(5)动态项集计数(在扫描的不同点添加侯选项集) 动态项集计数技术将数据库划分为标记开始点的块. 该技术动态 地评估已被计数的所有项集的支持度, 如果一个项集的所有子集已被 确定为频繁的,则添加它作为新的侯选.结果算法需要的数据库扫描 比 Apriori 少. 4)不产生侯选挖掘频繁项集 (1)它可能需要产生大量侯选项集. (2)它可能需要重复地扫描数据库,通过模式匹配检查一个很大的 候选集合. 能否设计一种方法, 挖掘全部频繁项集而不产生候选吗?频繁模 式增长(frequent-pattern growth)简称 FP-增长就这样产生.它采取 如下分治策略:将提供频繁项集的数据库压缩到一棵频繁模式树(或 FP 树) ,但仍保留项集有关信息;然后,将这种压缩后的数据库分成 一组条件数据库,每个关联一个频繁项,并分别挖掘每个数据库.
I ,则结果项集 I ∪ A 不可能比 I 更频繁出现.因此, I ∪ A 也不是频繁
的,即 P( I ∪ A) min_sup. 该性质属于一种特殊的分类,称作反单调,意指如果一个集合不 能通过测试,则它的所有超集也都不能通过相同的测试. 如何将 Apriori 性质用于算法?我们必须弄清如何用 Lk 1 找 Lk . 下 面的两步过程由连接和剪枝组成. (1) 连接步:通过 Lk 1 与自己连接产生侯选 k 项集的集合 Ck . (2) 剪枝步: Ck 是 Lk 的超集;压缩 Ck ,可以使用所有频繁项集 的散列树快速完成.
可以由 l 产生哪些关联规则?根据以上关联规则原理,我们有以下关 联规则及对应的置信度:
