【数据挖掘】关联规则挖掘 Apriori 算法 ( 关联规则性质 | 非频繁项集超集性质 | 频繁项集子集性质 | 项集与超集支持度性质 )

参考博客 :

• 【数据挖掘】关联规则挖掘 Apriori 算法 ( 关联规则简介 | 数据集 与 事物 Transaction 概念 | 项 Item 概念 | 项集 Item Set | 频繁项集 | 示例解析 )
• 【数据挖掘】关联规则挖掘 Apriori 算法 ( 关联规则 | 数据项支持度 | 关联规则支持度 )
• 【数据挖掘】关联规则挖掘 Apriori 算法 ( 置信度 | 置信度示例 )
• 【数据挖掘】关联规则挖掘 Apriori 算法 ( 频繁项集 | 非频繁项集 | 强关联规则 | 弱关联规则 | 发现关联规则 )

一、 非频繁项集超集性质

关联规则 性质 1 : 非频繁项集 的 超集 一定是 非频繁的 ;

超集 就是 包含 该集合的集合 ;

项集 X \rm X X 是 非频繁项集 ,

项集 Y \rm Y Y 是 项集 X \rm X X 的超集 ,

( 使用集合表示 : X ⊆ Y , X ≠ ∅ \rm X \subseteq Y , X \not= \varnothing X⊆Y,X​=∅ , 项集 Y \rm Y Y 包含 项集 X \rm X X , 并且 项集 X \rm X X 不为空集 )

则 项集 Y \rm Y Y 一定是 非频繁的 ;

举例 :

数据集 D \rm D D 为 :

事物编号事物 ( 商品 ) 001 001 001奶粉 , 莴苣 002 002 002莴苣 , 尿布 , 啤酒 , 甜菜 003 003 003奶粉 , 尿布 , 啤酒 , 橙汁 004 004 004奶粉 , 莴苣 , 尿布 , 啤酒 005 005 005奶粉 , 莴苣 , 尿布 , 橙汁

1 1 1 项集 { 甜 菜 } \{ 甜菜 \} {甜菜}

2 2 2 项集 { 甜 菜 , 啤 酒 } \{ 甜菜 , 啤酒 \} {甜菜,啤酒}

上述 { 甜 菜 , 啤 酒 } \{ 甜菜 , 啤酒 \} {甜菜,啤酒} 就是 { 甜 菜 } \{ 甜菜 \} {甜菜} 的 超集 ,

1 1 1 项集 { 甜 菜 } \{ 甜菜 \} {甜菜} 其支持度是 0.2 \rm 0.2 0.2 , 小于最小支持度 m i n s u p = 0.6 \rm minsup = 0.6 minsup=0.6, 是 非频繁项集

那么 { 甜 菜 , 啤 酒 } \{ 甜菜 , 啤酒 \} {甜菜,啤酒} 也是 非频繁项集 ;

在具体算法中会使用该性质 , 用于进行 “剪枝” 操作 ;

计算支持度时 , 按照 1 1 1 项集 支持度 , 2 2 2 项集 支持度 , ⋯ \cdots ⋯ 顺序进行计算 ,

如果发现 1 1 1 项集 中有 非频繁项集 , 则包含该 1 1 1 项集的 n \rm n n 项集 肯定是 非频繁项集 ;

然后使用 频繁 1 1 1 项集 组合成 2 2 2 项集 , 然后再计算这些 2 2 2 项集是否是频繁项集 ;

“剪枝” 操作 减少了不必要的计算量 ;

二、 频繁项集子集性质

频繁项集 的 所有非空子集 , 一定是 频繁项集 ;

项集 Y \rm Y Y 是 频繁项集 ,

项集 Y \rm Y Y 是 项集 X \rm X X 的超集 ,

( 使用集合表示 : X ⊆ Y , X ≠ ∅ \rm X \subseteq Y , X \not= \varnothing X⊆Y,X​=∅ , 项集 Y \rm Y Y 包含 项集 X \rm X X , 并且 项集 X \rm X X 不为空集 )

则 项集 X \rm X X 一定是 频繁的 ;

举例 :

数据集 D \rm D D 为 :

事物编号事物 ( 商品 ) 001 001 001奶粉 , 莴苣 002 002 002莴苣 , 尿布 , 啤酒 , 甜菜 003 003 003奶粉 , 尿布 , 啤酒 , 橙汁 004 004 004奶粉 , 莴苣 , 尿布 , 啤酒 005 005 005奶粉 , 莴苣 , 尿布 , 橙汁

1 1 1 项集 { 尿 布 } \{ 尿布 \} {尿布} , { 啤 酒 } \{ 啤酒 \} {啤酒}

2 2 2 项集 { 尿 布 , 啤 酒 } \{ 尿布 , 啤酒 \} {尿布,啤酒}

2 2 2 项集 { 尿 布 , 啤 酒 } \{ 尿布 , 啤酒 \} {尿布,啤酒} 其支持度是 0.6 \rm 0.6 0.6 , 等于最小支持度 m i n s u p = 0.6 \rm minsup = 0.6 minsup=0.6, 是 频繁项集

那么 2 2 2 项集 { 尿 布 , 啤 酒 } \{ 尿布 , 啤酒 \} {尿布,啤酒} 的子集是 1 1 1 项集 { 尿 布 } \{ 尿布 \} {尿布} , { 啤 酒 } \{ 啤酒 \} {啤酒} ,

根据上述性质 , 1 1 1 项集 { 尿 布 } \{ 尿布 \} {尿布} , { 啤 酒 } \{ 啤酒 \} {啤酒} 都是 频繁项集 ;

三、 项集与超集支持度性质

任意一个 项集 的 支持度 , 都 大于等于 其 超集 支持度 ;

超集 就是 包含 该集合的集合 ;