基于Apriori性质的多维关联规则数据挖掘 汇报人：王雷

背景知识 关于数据挖掘 关联规则及Apriori算法

数据挖掘是一项从大量的记录数据中提取有价值的、人们感兴趣的知识，这些知识是隐含的、事先未知的有用信息，提取的知识一般可表示为概念(Concepts)、规则(Rules)、规律(Regular ides)、模式(Patterns)等形式。 关联规则是当前数据挖掘研究的主要方法之一，侧重于确定数据中不同领域之间的联系，找出满足给定支持度和可信度阈值的多个域之间的依赖关系 。 例：在销售手机的商店中，70%的包含手机的交易中包含充电器,在所有交易中，有56%同时包含这两种物品。 于是规则表示为手机 充电器 （可信度70%，支持度56%）

关联规则的基本概念 设 是项的集合，设任务相关的数据D是数据库事务的集合，其中每个事物T是项的集合，使得 每一个事务有一个标识符TID，设A是一个项集，事务T包含A当且仅当 。关联规则是形如 的蕴涵式，其中 ， 并且规则在事务D中成立具有支持度S和置信度C, 把满足最小支持度阈值和最小置信度阈值的规则成为强规则。项的集合称为项集（itemset），包含K个项集称为K－项集，如果项集满足最小支持度，则称它为频繁项集。

关联规则的挖掘是一个两步的过程： 1、找出所有频繁项集 2、由频繁项集产生强关联规则，根据定义，这些规则必须满足最小支持度和最小置信度。

Apriori算法 Apriori算法是最有影响的关联规则挖掘算法之一。它的中心思想是首先通过对事务数据库进行扫描,找出支持度不小于最小支持度的所有项目,即频繁1 - 项集. 接下来的工作是循环的,每次循环分2步进行: 1)连接，对频繁k - 项集中的项进行连接. 2)减枝，在减枝这一步主要根据一个频繁项目集的任何一个子集都应该是频繁的这一思想对连接后的项目集进行筛选,删除那些子集不是频繁集的项目集,得出候选( k + 1) - 项集.即 对数据库进行扫描, 计算候选项的支持度,从候选集中删除支持度小于最小支持度的候选项, 进而得出频繁( k + 1) - 项集. 循环的终止条件是频繁k - 项集为空, 也就是说再也找不出相关联的项目了.

举例说明Aporiori算法 数据库 D 扫描 D C1 L1 L2 C2 C3 L3

Apriori性质 频繁项集的所有非空子集也是频繁的 例如：如果{AB} 是频繁项目集，则 {A} {B} 也一定是频繁项目集

加权关联规则挖掘 传统的关联规则挖掘算法通常都认为数据库里每个项目都有相同的重要性，没有主要、次要之分。但在实际中，往往存在一类这样的情况：用户对每个项目的看重程度不一样，有的项目是用户最看重、最关心的，有的项目是用户关注性不大，因此需要引进权重的概念。

加权关联规则的描述 设 是项的集合，每个项都有一个权值与之对应。它们的权值分别是{w1,w2,…,wk}（wi ∈[0,1]）。事先指定最小加权支持度阈值为 wminsup和最小置信度阈值 minconf。 对于项目集X，如果 wsup(X)≥wminsup，则 X 是加权频繁的。 形如X →Y 的关联规则的加权支持度为： 置 信 度 的 定 义 仍 然 沿 用 Apriori算 法 里 的 定 义 ， 即 ：conf (X →Y) = sup(X ∪Y)/sup(X ) 。

加权关联规则的描述 对于项目集 X、Y， ，X ∩Y =φ ，如果有 wsup( X ∪Y )≥wminsup，且 conf(X→Y)≥minconf，则称 X→Y 是一条加权关联规则。

权值的设定 加权支持度 (1)、平均值： (2)、归一化： (3)、最大值：

想法 (1) 先不考虑项目的权值，利用传统的 Apriori 算法找出支持度不小于最小加权支持度的所有的频繁项目集。由于项目集的权值小于 1，所以项目集的加权支持度一定小于支持度，所以生成的频繁集一定是加权频繁集的超集。 (2) 计算所生成频繁项目集中所有项目集的加权支持度，并把加权支持度小于最小加权支持度的项目集删除，从而得到所有加权频繁集。 (3) 利用加权频繁集来生成所有的加权关联规则。

Apriori的瓶颈 Apriori算法的核心: 用频繁的(k – 1)-项集生成候选的频繁 k-项集 用数据库扫描和模式匹配计算候选集的支持度 Apriori 的瓶颈: 候选集生成 巨大的候选集: 104 个频繁1-项集要生成 107 个候选 2-项集 要找尺寸为100的频繁模式，如 {a1, a2, …,a100}, 你必须先产生2100  1030 个候选集 多次扫描数据库： 如果最长的模式是n的话，则需要 (n +1 ) 次数据库扫描

提高Apriori效率的方法 基于哈希表的算法 事务压缩: 不包含任何频繁k-项集的交易也不可能包含任何大于k的频繁集 基于划分: 一个项集要想在整个数据库中是频繁的，那么他至少在数据库的一个分割上是频繁的。 采样: 在给定数据的子集上挖掘，使用小的支持度+完整性验证方法 动态项集计数: 在添加一个新的候选集之前，先估计一下是不是他的所有子集都是频繁的。 基于哈希表的算法

今后的工作 加权关联规则挖掘算法的研究，项目属性加权后，Apriori性质不再适用，算法如何优化。

参考文献 [1] 范明，孟小峰等译.数据挖掘：概念与技术.北京：机械工业出版社，2001. [2] Agrawal R, Srikant R. Fast Algorithms for Mining Association Rules. In: Proc of 1994 Int’1Conf of Very Large Data Base. Santiago, Chili: VLDB Endowment, 1994, 487~499. [3]胡和平, 路松峰. 加权关联规则的开采. 小型微型计算机系统,2001,22(3): 347~375. [4]张文献, 陆建江. 加权布尔型关联规则的研究. 计算机工程, 2003, 29(9): 55~57. [5]张智军, 方颖, 许云涛. 基于Apriori算法的水平加权关联规则挖掘. 计算机工程与应用, 2003, 39(14): 197~199.

[6] R. Agrawal, et al. Mining association rules between sets of items in lager databases. In: Proc.ACM SIGMOD int'1 conf. management of data, Washington, DC, May 1993, 207-216. [7] Wei wang, Effcient Mining of weighted Association rules.