【数据挖掘学习笔记】11.频繁模式挖掘进阶与关联规则
一、关联规则
关联规则步骤：
– 1、确定这一系列对应的规则拥有相同的支撑值（support），并筛选出支撑度高于或等于minsup的相关项集
– 2、评估该集合中各项规则的信任水平（confidence），并找出信任水平不低于minconf的各项规则
由频繁项集生成关联规则
生成关联规则
给定一个频繁项集L，请确定其每一个真子集f是否满足f\rightarrow L-f的支持度不低于设定的最小支持度。
基于给定的频繁项集\{A,B,C,D\}, 系统会生成以下候选关联规则：
ABC \rightarrow D, ABD \rightarrow C, ACD \rightarrow B, BCD \rightarrow A, A \rightarrow BCD, B \rightarrow ACD, C \rightarrow AB D, D \rightarrow ABC, AB \rightarrow CD, AC \rightarrow BD, AD \rightarrow BC, BC \rightarrow AD, BD \rightarrow AC以及CD\rightarrow AB。
当|L|=k时，在忽略"L\!\to\!\varnothing"和"\varnothing\!\to\! L"这两种情况的前提下, 总共有2k-2个可能的候选关联规则。
基于Apriori算法的关联规则生成
基于Apriori算法的关联规则生成
– 通过基于Apriori算法生成关联规则
– 通过合并具有共同前缀的条件项集生成候选关联规则
– 将CD→AB与BD→AC合并可得到D→ABC
– 若子集AD→BC的置信度低于设定最小阈值，则舍弃D→ABC
二、FP-TREE
FP-TREE方法
– 分治策略
– 不产生候选集
– 频繁过滤机制
– 计数机制
– 生长机制
FP-TREE算法步骤
– 对数据库进行一次扫描以计算各项目项集的频率
– 将各项目项集按照其频率值进行降序排序并生成频繁项头表文件
– 再次扫描数据库以构建FP树数据结构
FP-TREE建立方法
1. 生成树结构的基础节点，并将其标记为null。
2. 按照递减的支持度排序后排列各项，并生成相应的分支结构。
3. 在共同路径上的所有节点计数增加1；随后生成后续关联的分支。
4. 建立一项头索引表以便于后续操作访问；确保每个项目都能通过指针直接关联到其所在的位置。
例子
FP-TREE优点
– 完整性
• 通过避免破坏事务数据中的长期模式来确保频繁模式挖掘所需的所有相关信息得以保留
– 紧凑性
• 通过移除非频繁项来减少冗余信息，并按照频率从高到低排序以使高频项更容易在树结构中共享资源
• 存储的数据规模比原始数据库小得多
FP树挖掘——从FP树到条件模式基
– 基于项头表展开探索，在低频项节点上优先进行
– 按照各（频繁）项目及其关联链路对FP树进行遍历
– 收集该特征下的预设顺序下的特征序列以构建条件模式基
FP树挖掘——构建条件FP树
– 针对每一个条件模式基
• 统计并累加其在基中的出现次数
• 基于频繁项构建相应的FP树结构
三、多层关联规则
概念层次
多层关联规则
– 在某种程度上，在适当等级下提取出的数据项间的关系模式可能具有重要的应用价值
– 一般而言，在事务数据库中存储的数据也是按照基于层次化的架构来进行组织的
• 这种架构使得从不同层次中提取关联模式成为可能
– 在多层次抽象级别下实现关联规则的发现，并通过相应的转换机制实现各层次间的关联模式转换功能
• 单一维度关联规则：
– buys(X, "milk") \Leftarrow buys(X, "bread")
• 多维度关联规则：涉及至少两个维度或谓词的相关联规则
– 维间关联规则：强调谓词的独特性
• age(X,"19-25") \land occupation(X,"student") \Rightarrow buys(X,"coke")
– 混合型维相关联规则：涉及某些谓词的多重出现
• age(X,"19-25") \land buys(X, "popcorn") \Rightarrow buys(X, "coke")
• 在多维度关联规则挖掘过程中，我们关注的是频繁出现的谓词组合而非传统的项集。k-合取项是指由恰好k个合取关系构成的概念。
– 例如：\{age, occupation, buys\}是一个3-合取项
挖掘多维关联规则
- 数据 attribute 可可分为 classification 型 attribute 和 quantitative 型 attribute
• classification 型 attribute
– 包含有限数量的不同取值
– 各取值之间不存在 order 关系
• quantitative 型 attribute
– 具有数值类型的数据特征
– 特征间存在内在 order 关系
• 挖掘多维关联 rule 的技术可根据 quantitative 型 attribute 的处理方式分为两大类技术：
• 1. 静态离散化处理
– 通过预先设定的概念层次结构完成对量化的静态分割
• 2. 分布驱动型 quantification
– 根据数据分布特征将其划分为若干区间或区域（即所谓的箱体）
四、模式评估
• 关联规则算法能产生大量的规则
– 其中很多是无意义或是冗余的
– 冗余
– 例如：{A,B,C} →{D} 和{A,B} →{D}有同样的支持度和置信度
• 客观度量
– 两个流行的度量指标
• 支持度
• 置信度
• 主观度量
– 最终是由用户自己来确定一条规则是否具有吸引力的，并且这种判断结果具有主观性、因用户的不同而异；一般而言认为一条规则（模式）是吸引人的条件如下：
• 它出人意料
• 具备可操作性（能够被用户用于执行某些操作）
兴趣度(Interestingness)
– 体现模式的重要程度，并作为筛选模式或按一定的排序规则进行处理
– 支持度与置信度是采用的主要衡量标准
计算兴趣度
– 基于给定的规则关系X→Y，评估关联强度的相关信息完全可依据列联表进行获取，并且该信息的形式即为... (contingency table)
误导性规则
由关联分析到相关分析
兴趣度(Interest)
– Interest(A,B)=P(AB)/(P(A)*P(B))
辛普森悖论