一、关联规则

关联规则步骤：

– 1、找个这个“同一项集”，相同的项集对应的规则有相同的支持度，找到支持度≥minsup的项集
– 2、计算项集中所有规则的置信度，找到置信度≥minconf的规则

由频繁项集生成关联规则

生成关联规则

– 给定频繁项集L，找出L的所有非空子集f，满足f →L–f 的置信度不小于最小置信度阈值
– 如果{A,B,C,D}是频繁项集，则候选的规则有：
    ABC →D, ABD →C, ACD →B, BCD →A, 
    A →BCD,B →ACD,C →ABD, D →ABC
    AB →CD,AC →BD, AD →BC, BC →AD, 
    BD →AC, CD →AB, 
– 令|L| = k，则有2k–2 个候选的关联规则(不考虑L →∅and ∅→L)

基于Apriori算法的关联规则生成

基于Apriori算法的关联规则生成
– 通过合并具有共同前缀结论的关联规则生成候选规则
– 合并(CD=>AB,BD=>AC)将生成D => ABC
– 裁减D=>ABC如果其子集AD=>BC置信度小于最小阈值

二、FP-TREE

FP-TREE方法

– 分治策略
– 不产生候选集
– 频繁过滤机制
– 计数机制
– 生长机制

FP-TREE算法步骤

– 扫描一次数据库，计算各项的频繁度
– 将各项按照频繁度进行降序排列，生成频繁项头表
– 扫描数据库，建立FP-TREE

FP-TREE建立方法

1. 创建树的根节点，用null标记；
2. 将每个事务中的项按递减支持度计数排列，并对每个事务创建一个分枝；
    • 比如为第一个事务{f, c, a, m, p}构建一个分枝
3. 当为一个事务考虑增加分枝时，沿共同前缀上的每个节点的计数加1，为跟随前缀后的项创建节点并连接
    • 比如将第二个事务{f, c, a, b, m}加到树上时，将为f，c，a各增计数1，然后为{b, m}创建分枝
4. 创建一个项头表，以方便遍历，每个项通过一个节点链指向它在树中的出现。

例子

FP-TREE优点

– 完整性
    • 不会打破任何事务数据中的长模式
    • 为频繁模式的挖掘保留了完整的信息
– 紧凑性
    • 减少了不相关的信息——非频繁的项被删除
    • 按频率递减排列——使得更频繁的项更容易在树结构中被共享
    • 数据量比原数据库要小

FP树挖掘——从FP树到条件模式基

– 从项头表开始挖掘，由频率低的节点开始
– 沿循每个（频繁）项的链接来遍历FP树
– 通过积累该项的前缀路径来形成一个条件模式基

FP树挖掘——构建条件FP树

– 对每个条件模式基
    • 为基中的每一项累积计数
    • 为模式基中的频繁项构建FP树

三、多层关联规则

概念层次

多层关联规则

– 在适当的等级挖掘出来的数据项间的关联规则可能是非常有用的
– 通常，事务数据库中的数据也是根据维和概念分层来进行储存的
    • 这为从事务数据库中挖掘不同层次的关联规则提供了可能。
– 在多个抽象层挖掘关联规则，并在不同的抽象层进行转化，是数据挖掘系统应该提供的能力

• 单维关联规则：
    – buys(X, “milk”) ＝ buys(X, “bread”)
• 多维关联规则：涉及两个或多个维或谓词的关联规则
    – 维间关联规则：不包含重复的谓词
        • age(X,”19-25”) ∧occupation(X,“student”) => buys(X,“coke”)
    – 混合维关联规则：包含某些谓词的多次出现
        • age(X,”19-25”) ∧buys(X, “popcorn”) => buys(X, “coke”)
• 在多维关联规则挖掘中，我们搜索的不是频繁项集，而是频繁谓词集。k-谓词集是包含k个合取谓词的集 合。
    – 例如：{age, occupation, buys}是一个3-谓词集

挖掘多维关联规则

– 数据属性可以分为分类属性和量化属性
    • 分类属性
        – 具有有限个不同值，值之间无序
    • 量化属性
        – 数值类型的值，并且值之间有一个隐含的序
– 挖掘多维关联规则的技术可以根据量化属性的处理分为两种种基本方法：
    • 1. 量化属性的静态离散化
        – 使用预定义的概念分层对量化属性进行静态地离散化
    • 2. 量化关联规则
        – 根据数据的分布，将量化属性离散化到“箱”

四、模式评估

• 关联规则算法能产生大量的规则
– 其中很多是无意义或是冗余的
– 冗余

– 例如：{A,B,C} →{D} 和{A,B} →{D}有同样的支持度和置信度

• 客观度量
– 两个流行的度量指标
    • 支持度

    • 置信度

• 主观度量
– 最终，只有用户才能确定一个规则是否有趣的，而且这种判断是主观的，因不同的用户而异；通常认为一个规则（模式）是有趣的，如果：
    • 它是出人意料的
    • 可行动的（用户可以使用该规则做某些事情）

兴趣度(Interestingness)

– 反映模式重要程度，用于裁减模式或对模式排序
– 支持度和置信度是用到的两个度量

计算兴趣度

– 给定规则X →Y，计算规则兴趣度的信息可完全由列联表给出(contingency table)

误导性规则

由关联分析到相关分析

兴趣度(Interest)

– Interest(A,B)=P(AB)/(P(A)*P(B))

辛普森悖论