数据挖掘第五章 关联规则挖掘和序列模式

数据挖掘 关联规则挖掘

---

数据挖掘技术与原理主目录：
目录

第三章目录：

---

1 关联规则

1.1 规则 rules

itemset is a set of items in $I$

association rule: $X \rightarrow Y, where X, Y \subset I, and X\cap Y = \varnothing$

以上的公式定义了关联规则的一般特性

Support: $sup = Pr(X \cup Y)$，表示有多少的概率发生$X\cup Y$事件，即一个购物篮同时出现面包和牛奶。

Confidence: $conf = Pr(Y|X)$，表示发生了X的情况下发生了多少概率的Y，即在包含了面包的购物篮中有多少概率有牛奶

support count:

X.count：数据集里面有多少个事务包含X象集

$$support = \frac{(X \cup Y).count}{n}$$

$$conf = \frac{(X\cup Y).count}{X.count}$$

1.2 目标和主要特点

关联规则挖掘的目标：

寻找所有满足用户定义的最小支持度(minsup)和最小置信度(minconf)的所有规则。

主要特点：

• 完全性，寻找所有规则
• 右手端没有目标对象 (即不是if判断的运作模式，和决策树、分类等不同)
• 需要对磁盘上的数据进行挖掘

这样大小为k的象集需要$(2^k-2)$个潜在的关联规则，即指数级的计算量。

frequent itenset:

频繁象集，表示出现频率大于用于指定支持度的象集。

任何强关联规则在箭头的左右两端的并集都是频繁象集。任何强关联规则都是由频繁象集拆解成两个子集得到的。

不同的算法得到的是相同的强关联规则，但是每个算法的效率却不同。

1.3 the Apriori Algorithm

步骤：
1. 找到所有频繁象集
2. 根据频繁象集生成关联规则

1.3.1 找出所有频繁象集

The apriori property (downward closure property)：向下闭包属性
一个频繁象集的子集一定是频繁象集，一个非频繁象集的超集一定不是频繁象集。

逐层搜索的迭代算法，从一象集开始统计频繁象集，以频繁一象集的超集开始统计第二轮的频繁象集。

$C_k$表示大小为k的候选象集，$F_k$为大小为k的频繁象集。

全集$I$中的象以字典顺序排序，即从小到大排序。

Algorithm Apriori(T)
    C_1 = init-pass(T)
    F_1 = [f for f.count/n >- minsup]
    for (k=2; F_k-1 != NULL; k++) do
        C_k = candidate-gen(F_k-1);
        for each transaction t in T do
            for each candidate c in C_k do
                if c in t
                    c.count++;
            end
        end
        F_k = [c for c.count/n >= minsup]
    end
return all frequent itemset

生成候选象集
两个步骤：
1. join step: 生成所有可能的k个象的象集，$C_k$
$F_{k-1}$中的象进行连接操作，当且仅当前$k-2$个象相同而最后一个象不同的时候，才进行连接，得到$C_k$。

如({AB},{AC},{BC},{AD},{BD})四个频繁二项集进行连接，k为3，k-1为2，k-2为1，AB和AC的第一个项都是A，因此{ABC}是候选的二项集。同理，{ABD}，{ACD}，{BCD}也是可能的二项集。

2. 任何一个子集都属于$C_{k-1}$，如果不满足，则从$C_k$中去除。

进行剪枝，由于{ACD}的子集{CD}不在频繁二项集中，因此减掉{ACD}，同理减掉{BCD}，因此候选象集C3为{ABC}和{ABD}。要判断这两个候选象集是否是频繁的，需要查看他们支持度是否超过阈值。

3. 判断候选象集是否是频繁象集

1.3.2 根据频繁象集生成关联规则

$$confidence(A \rightarrow B) = \frac{support(A,B)}{support(A)}$$

判断confidence是否大于用户定义的阈值

原则上，加入频繁象集是{ABCD}，则从{ABCD}->{}开始，将左边的项移到右边，计算置信度。若当某个时候置信度小于阈值了，则可以停止将左边的项移到右边了，因为之后的组合都不是关联规则。

比如，{ABC}->{D}的置信度小于阈值，则所有D在箭头右边的组合都不是关联规则，因此这个时候D固定在了左边。又比如，{BC}->{AD}的置信度小于阈值，则所有AD在箭头右边的组合都不是关联规则，即A和D不能同时在右边。

计算时，从{ABCD}->{}开始，依次分别将A，B，C，D移到右边，若有一个如{BCD}->{A}不满足，则不再在此基础上把B，C，D移到右边，而是从{ACD}->{B}开始考虑。

$support(A,B)$和$support(A)$在之前扫描数据集的时候都已经储存。

该算法扫描数据集的个数取决于象集长度$k$，即购物篮的物品个数。一般来说，k取<10。即一般来说扫描数据集不超过10次。

计算举例：

2 序列模式挖掘

关联规则并没有考虑事务的序列信息

2.1 基本概念

$I = {i_1, i_2, i_3, ..., i_m}$是一个象集

Sequence:

一个有序的象集列表

比如：考虑买房之后购买家具的可能性，需要采用序列模式挖掘。

size:

表示一个序列象集的个数

length:

表示序列中出现了的象(item)的个数

比如说[{3,4},{5},{8}]的size是3，length是4。

如果sequence s1的每个象集都是sequence s2对应(顺序一一对应)的每个象集的子集，那么就说s1是s2的子序列(subsequence)，而S2是s1的超序列(supersequence)。

2.2 任务

mining sequential patterns的任务是在给定一系列序列的结合S的情况下，找到所有满足用户定义的最小支持度的序列 (频繁序列 frequent sequence 或 序列模式 sequential pattern)。

2.3 GSP mining algorithm

代码框架和Apriri算法相似
这里的k指的是序列长度length，而不是大小size

如何利用$F_{k-1}$形成$C_k$？

Join step

将$F_{k-1}$和$F_{k-1}$连接得到，连接条件是：去掉s1的第一个项以及去掉s2的最后一个项形成的是相同的序列。连接后的序列就是s1的序列+s2序列的最后一项
如果s2的最后一项是单独作为一个元素，则这一项也要在s1中单独一个元素。

例子：
$<\{x\}>$和$<\{y\}>$进行拼接，会产生$<\{x,y\}>或<\{x\},\{y\}>$
$<\{x\}\{y,z\}>和<\{y\}\{z,v\}>$进行拼接，会产生$<\{x\}\{y,z,v\}>$。因为v和z在一个项集里面，因此合并后v也和z在一个项集里面。
计算示例

因此，设频繁一序列的个数为$n$，则从$F_1$生成$C_2$的序列模式数目会有$2\cdot n+3\cdot C_n^2$，即5个频繁一序列可以生成40个未剪枝的候选二序列；而候选二序列集一般不会有序列被剪枝，因此候选二序列的数目就是$2\cdot n+3\cdot C_n^2$。

此后，对每一个候选二序列计算支持度，从而选出频繁二序列。

Prune step

任意去掉一项判断是否所有序列都是在$C_k$中。只有所有子序列都在$C_k$中的才是候选序列。

形成$C_k$后，计算支持度，如果支持度高于阈值，则划为频繁序列，否则剪掉。