频繁项集与强规则

<数据挖掘导论>第六章第1节

项集和事务

项 : 就是集合中的一个元素
项集 : 就是项的集合

事务 : 事务作为关联分析的核心概念, 是整个体系的关键要素. 集合代表核心问题, 而关联分析则是解决这些问题的技术手段.

每个事务都单一地关联一个唯一的项集，在无需引起混淆的情形下, 我们无需将事务与之相关的项集加以区分.

基于项集的支持度指标与事务相关联的关键字集合：其中，一个项集的支持度是指该项集在其所有事务中以子集形式出现的频率。

形式上, 项集X的支持度用\sigma(X)表示.

关联分析问题

关联规则 : 具有形式X\rightarrow Y的关系被称为关联规则, 其中X和Y均为项集。

关联规则两大核心属性为支撑力与可靠性

通过正式定义的方式, 我们可以在给定事务数据库中提取出所有满足(s_0, c_0)阈值的支持度与置信度条件的关联规则。

平凡的方法是遍历所有的关联规则, 其复杂度为:

优化的方法之一是采用剪枝策略. 在分析关联规则时, 我们需关注其支持度仅受项集的影响. 为了提高效率, 可以先提取所有满足支持度高于阈值s_0的项集. 这样的项集叫做频繁项集

基于频繁项集F, 我们可以直接选择置信度高于阈值c_0的所有相关联规