第七章——数据挖掘(2)

一、 关联规则

关联模式是数据库系统和数据挖掘领域中被开发出并广泛研究的最重要的发现。它的主要目标是在大型数据库中发现大量数据间的关联性，并将这种关系也被称为关联模式。

1.基本概念

定义为关联规则的形式：令i=1到m时的情况；iz…im构成一个项目集合；T则由一系列这样的交易组成。每个关联规则都可以表示为以下形式的一种蕴含关系：前件→后件（antecedent → consequent）。这种形式中前件（antecedent）和后件（consequent）都来自同一个项集I，并且它们之间存在至少一个共同元素。

2.关联规则强度指标

评估关联规则的强度通常采用的支持度与置信度这两个关键指标。其中，关联规则X→Y的支持度定义为所有包含X∪Y的事务占总事务数的比例。即其发生概率为P(X∪Y)，记作 support(X→Y) = P(X∪Y).

关联规则X→Y的支持度衡量了同时包含属性X和Y的所有记录数量与仅包含属性X的记录数量的比例；它表示在给定条件下属性Y出现的概率。

3.频繁项集

每个属性通常包含多个元素，在数据挖掘中我们把这些元素称之为"term"或者"item"。所有这些term组合在一起形成一个term set或者item set。当某一个term set满足预先设定的支持度阈值时，则我们称其为frequent term set或者important item set；而所有的frequent k-term sets所构成的集合则通常被标记为L_k.

二、关联规则挖掘算法

在关联规则挖掘算法中，Apriori algorithm is the most famous, and its mining process mainly consists of two steps. First, it extracts all frequent itemsets from the dataset that meet or exceed the minimum support degree threshold. Second, based on these frequent itemsets, candidate association rules are generated, and their confidence levels are calculated. Finally, association rules with confidence levels above the minimum confidence degree threshold are retained.

1.Apriori 算法中候选集合的产生

(1)连接

为了获取L_k值，请考虑从L_{k−}中与自身进行连接以生成候选{k}−−项目集C_k：将该候选集合标记为C_k。其中，在{ L_{k−} }中任意两个项目集{ l_0 }和{ l_0' }若满足特定条件，则可执行连接操作{ loolz }：即对于所有i从0到n−−3的情况（其中n代表项目集长度），必须满足{ l_0[i] = l_0'[i] }。

(2)剪枝

G被视为Lr的一个superset，在其中它的元素可能并非都是frequent itemsets。然而，在这种情况下，则所有的 frequent k-项集都必然是Ck中的成员。因此可以通过遍历数据库并计算每个候选k-项集的支持度来获得所有的 frequent k-项集。

为了减少计算规模，
能够被用来应用Apriori性质进行剪枝。
也就是如果一个包含k项元素的集合中的所有(k−1)项子集都不在L_{k−1}中，
则该候选集合不可能成为频繁项集，并可以直接从C_k中移除。

2.Apriori 算法过程

Apriori算法的computational complexity主要取决于minimum support threshold、dimensionality（项数）、transaction count以及average transaction width等参数的影响。详细说明如下：输入包括transactions database D、minimum support threshold min_sup以及minimum confidence threshold min_conf；输出则为D中的所有frequent itemsets L以及关联规则AR。

3.例子

下面举例说明该算法的规则。

该事务数据库系统如表所示，请提取其中的所有满足最小支持度计数的关联规则。

表中的每个记录对应一条交易信息；总共有9条记录；左侧列对应顾客ID；右侧列对应商品ID；其中定义了最小支持度计数为min_sup=2（即相当于最低支持度设置为22%）；为了便于后续计算的需求

在数据库中进行扫描以提取所有的单项目集合，并计算它们的支持度计数值以确定候选单项目集合G₁；随后筛选出满足最小支持度条件的所有项目并将其标记为候选项集G₁；最终获得所有满足条件的频繁单项目集合L₁。

下面需要执行类似的任务, 生成所有可能频繁出现的二元组集合, 称为候选二元组集合, 记为C₂. 这可以通过遍历数据库, 生成所有可能的二元组集合来完成. 遍历数据库后, 计算C₂中每个二元组集合的支持度, 然后从中筛选出符合标准 (即支持度大于或等于min_sup) 的二元组集合, 进而得到L₂.

4.关联规则生成

在获得所有的频繁项集之后, 建立关联规则变得容易. 对于置信度的计算, 则可以通过以下公式来实现.

条件概率可通过项集的支持度计数来表示，在这种情况下符号support\_count(A\cup B)代表包含项集A\cup B的所有事务的数量，并且support\_count(A)则代表包含项集A的所有事务的数量。基于此依据我们能够系统地推导出关联规则的具体生成流程：

(1)对于每个频繁项集L，产生L的所有非空子集。

每一个非空的真子集S都属于集合L，在满足其概率值达到或超过最小置信度阈值的情况下，则生成规则模式串s指向(l−S)