交叉支持模式
交叉支持模式是一个项集 ,它的支持度比率
小于用户指定的阈值 。
约 1161 字大约 4 分钟
2024-06-04
本节讨论一种重要性质,该性质对关联分析算法的性能和提取模式的质量具有重要影响。我们将关注具有倾斜支持度分布的数据集,其中大多数项具有较低或中等频率,但是少数项具有很高的频率。
如下图所示,p 是具有 83.8% 的高支持度的项,而 q 和 r 则是具有 16.7% 的低支持度的项。尽管 q 和 r 的支持度不高,但是二者显现出非常强的相关性。一个模式挖掘算法应当能发现 {q,r} 是有趣的。
但是很显然为项集 {q,r} 选择一个合适的支持度是非常困难的,如果阈值太高(如 20%),则可能遗漏涉及类似 {q,r} 这种支持度较低的模式。如果支持度阈值设置太低,则会使得模式挖掘过程变得过于复杂。
提示
特别地,可能会提取大量的高频项(如 p)和低频率项(如 q)相关联的虚假模式,这样的模式就是所谓的 交叉支持模式(cross-support)。
这是由于 p 和 q 之间的关联性大部分都是受 p 项的频率发生而不是 p 和 q 共同出现的影响。由于 {p,q} 的支持度和 {q,r} 的支持度非常接近,当为了挖掘 {q,r} 而将支持度设置较低时,很自然地 {p,q} 也会被选择出来。
交叉支持模式
交叉支持模式是一个项集 X={i1,i2,…,ik},它的支持度比率
r(X)=max[s(i1),s(i2),…,s(ik)]min[s(i1),s(i2),…,s(ik)](6.1)
小于用户指定的阈值 hc。
很遗憾的是现有的度量都不足以消除交叉支持模式。不过这不代表我们什么都做不了。
虽然 {p}→{q} 的置信度非常低,但是 {r}→{q} 的置信度很高。通过这一观察,可以通过从给定项集提取出的最低置信度规则来检测交叉支持模式。使用下面的方法可以找到最低置信度规则:
前面章节中提到的置信度的反单调性:
conf({i1i2}→{i3,i4,…,ik})≤conf({i1i2i3}→{i4,…,ik})(6.2)
该性质表明,把关联规则左边的项不断一道右边之后不会增加规则的置信度。根据这个性质可以知道,一个频繁项集中置信度最低的规则是左边仅包含一个项的规则,我们用 R1 表示。
规定一个频繁项集 {i1,i2,…,ik},如果 s(ij)=max[s(i1),s(i2),…,s(ik)],则规则:
{ij}→{i1,i2,…,ij−1,ij+1,…,ik}(6.3)
是 R1 中具有最小置信度的规则。
所以,可以从频繁项集 {i1,i2,…,ik} 中得到的最低置信度为:
max[s(i1),s(i2),…,s(ik)]s({i1,i2,…,ik})(6.4)
该表达式也被称为 **h 置信度(h-confidence)**或 全置信度(all-confidence)。由于支持度的单调性,所以我们又能知道:
h-confidence(X)≤max[s(i1),s(i2),…,s(ik)]min[s(i1),s(i2),…,s(ik)](6.5)
我们可以看到 公式(6.5) 和 公式(6.1)是一样的。
那么 h-confidence 是如何帮助我们消除交叉支持模式的呢?由于交叉支持模式的支持度比率总是小于 hc,所以这类模式的 h-confidence 也一定小于 hc。所以,通过确保模式的 h-confidece 大于 hc 即可消除交叉支持模式。最后值得一提的是:使用 h-confidence 的好处不仅仅是能消除交叉支持模式,这种度量也是反单调的,即:
h-confidece({i1,i2,…,ik})≥h-confidece({i1,i2,…,ik+1})(6.6)
从而可以将其并入挖掘算法。此外,h-confidence 可以确保项集中的项之间是强关联的。例如,假定一个项集 X 的 h-confidence 是 80%。如果 X 的一个项出现在某事务中,则 X 中其他的项至少有 80% 的概率属于同一个事务。这种强关联模式又被称为 超团模式(hyperclique pattern)。
超团模式
给定项集 X,如果 h-confidence(X)>hc,则称 X 为超团模式,其中 hc 表示用户定义的阈值。