频繁封闭项集的应用：减少冗余规则生成

1.冗余规则

使用传统的关联规则生成算法，在多数情况下将产生大量的规则，特别是当阈值设置不太合理时，所生成的规则可能会过多，当获取的规则太多就没有实际的意义了。大量的规则占用了系统的资源，也可能使系统无法对其进行处理。在这些生成的规则中有的是可以进行约简的，比如有些规则可以由其他规则推导得出，这种规则被称为冗余规则。例如，通过挖掘获取规则中如果有l1⇒l2l3、l1⇒l2和l1⇒l3三条规则，后两条规则就是冗余规则，因为可以通过第一条规则推理出后两条规则。对冗余规则的约简是决定挖掘质量的重要指标。

2.非冗余规则

与冗余规则相对，非冗余关联规则就是不能通过其他规则的推理获得，并且是有实际意义的规则。非冗余规则的重要特征就是通过尽可能少的条件推出尽可能多的结论，对空间数据能够提供最大的信息量。实质上它是隐含在数据中的最本质的规则。据此，非冗余规则的形式化定义为：对于某一规则r：l1⇒l2，如果┐∃r′：l′1⇒l′2，support(r)≤support(r′)，confidence(r)≤confidence(r′)，并且l′1⊆l1，l2⊆l′2，则称规则r为非冗余规则(Mohammed J.Zaki，1999)。

3.频繁封闭项集

在本书2.4.2中将模糊Galois联系表示为对象集合和属性集合之间的两个映射，因此可以定义封闭操作γ＝α◦β＝β(α(l))为映射的复合运算。它表示项集l的所有对象的集合所具有的最大的项集。

对于模糊概念格中的某一频繁项集l，如果其存在γ(l)＝l，并同时满足min_sup(最小支持度阈值)，那么项集l被称为频繁封闭项集。(www.xing528.com)

空间关联规则挖掘最核心的内容就是如何生成这些频繁封闭项集。Mohammed J.Zaki(1999)和秦昆(2004)分别对属性数据和空间数据的频繁封闭项集的获取算法进行了研究。其实，3.3节所设计的模糊概念格的构建算法可以生成频繁封闭项集(每个频繁概念格节点的内涵)。因此空间关联规则可以直接利用频繁概念格节点自动生成，通过生成频繁封闭项目集可以大量减少冗余规则的生成。

4.频繁封闭项集的产生子

用上述方法可以在一定程度上减少了冗余规则生成，但是不可避免的还会存在一定数量的冗余规则，可以用频繁封闭项集的产生子来解决。

产生子可以认为是决定该概念节点所对应的概念，谢志鹏博士称其为内涵缩减集。可以将产生子形式化定义为：在模糊概念格中如果项集g⊆I，满足γ(g)＝l，并且┐∃g′⊆I，满足λ(g′)＝l，则称g为封闭项集l的产生子(Toshiyuki Suzuki，2002)。

通过引入产生子的概念，就不需要对每个频繁封闭项集都产生空间规则，因为通过这种方式产生的规则必然存在着冗余。可以利用产生子根据下面的计算步骤获得产生子，避免冗余规则的产生：第一步，计算每个频繁封闭节点内涵集的非空子集，如果该子集是其中某个父节点的蕴含，则删掉该子集；第二步，如果对于每个子集存在另一个子集是该子集的真子集，则删掉。

通过上面两个步骤的处理所剩下的就是频繁封闭节点的产生子，利用产生子进行规则的提取就可以避免生成冗余规则。