数据挖掘中关联规则集的优化(2)

设初始规则集∑的子集∑ｔ，由定义４可知，规则集∑７是矛盾的，当且仅当∑７ｕ｛ｘ｝ＦＹｉｔ∑７

则的前、后件可以写为ｉ。Ａｉ：Ａｉ３．． （称为正事实公式）或７

ｉ１

ｕ｛ｘ｝卜］ｙ．规

Ａ

７ｉｚ

Ａ］ｉ３．． （负事实公式）．本文讨论的规则和事实公式

７

都可以转换为特定形态的子句集．正关联规则对应的子句集中的子句包含１个正文字和１个或多个负文字，如７ｉ。Ｖ

Ｖ

７

ｉ２

ｉ３Ｖ…Ｖ

７ｉｋ

Ｖｉ蚪１．负关联规则对应的子句集中的子句包含２个或２个以上的负文字，如１ｉｌＶ

７

ｉ２

Ｖ］ｉ３Ｖ…

Ｖ１讧，．正事实公式对应的子句集中的子句只包含１个正文字，如ｉｓ．负事实公式对应的子句集中的子句只包含１个负文

字，如７

ｉｔ．可以借助归结原理判定∑７ｕ｛ｘ）卜ｙ且∑７

ｕ｛ｘ｝卜］ｙ．

为方便说明问题，文中后面讨论的算法均采用下述示例作为辅助说明．例中给出了１５条关联规则，并相应地给出了它

们的兴趣度，其中包括３条负关联规则．设关联规则集∑包含１５条规则如表１所示．

表１

关联规则集∑包含的１５条规则

兴趣度

０．６０．５０．６０．７０．６０．６０．６

关联规则

口Ａ６一ｄ

关联规则｜Ｉｌ一，ｚ咒 ０

兴趣度

０．５０．６

Ⅱ’ｃ口一ｉｃ４１ｄｅ—ｆ氏ｇｆ—ｈｇ—ｉ＾一１

ｉ

ｊ一五０．７点一ｆ奄一ｆＺ—ｍ研＋７砚Ａ］０

０．６０．５０．６０．６

０．６

２．２找出关联规则集∑中的所有极小矛盾集

采用一般归结过程进行归结时，会产生许多无用的和重复的子句，浪费时间和空间．由此，必须考虑压缩初始子句集以

及选择１种合适的归结策略，尽量避免无用的子旬出现．对于文中的问题，∑Ｕ｛ｘ｝中可能存在多个矛盾规则集合，所以归

吉首大学学报（自然科学版）

结过程的停机条件不是出现空子句，必须重新确定程序的终止条件．

第３１卷

对于每个事实公式ｘ，首先将∑Ｕ｛ｘ｝中的所有公式转化为子句形式，然后对其进行归结．文中采用纯文字删除

法［”６］对整个子句集进行处理可以非常有效地缩小归结空间，提高效率．

过程１：删除包含纯文字的子旬．

考察文中的例子，假设对∑ｕ

Ｕ）进行处理．删除处理前包含１７个子句：｛Ｊ，１ＪＶ惫，－３志ｖ

ｚ，］ｚｖｍ，］ｍＶ］行，１，，ｌ

Ｖ］ｏ，１五Ｖｆ，］ｆＶｈ，］ｈＶ忍，］珂Ｖｏ，］ｈＶ］ｆ，］ｅＶｆ，］ｅＶｇ，］ｇＶｉ，］口Ｖ

ｃ，］ｃ

Ｖ］ｄ，］ａＶ］６Ｖｄ｝．

删除处理后只包含１０个子句：｛ｊ，］ＪＶ正，１可以看出，对子句集的压缩幅度是很大的．

ｋ

Ｖｚ，１ｚＶｍ，］ｍＶ］ｎ，］ｍＶ］Ｄ，］惫Ｖｆ，］ｆＶ＾，］ｈＶ起，１行ＶＤ｝．

（１）子句集的归结．支持集策略［卜６］是Ｗｏｓ等提出的一种归结策略，它在一般归结过程中引入了某种限制条件，这种限制条件代表一种启发信息，因而有较高的效率．对于文中的问题，可能得到空子句的子句集中必定包含由事实公式所得的子句．可以将事实公式看成目标公式的否定而采用支持集策略进行归结，以便得到备选矛盾规则集．具体由过程２实现．过程２的停机条件是归结过程无法得到与初始子句集和归结过程中已经得到的子句不同的子句．

过程２：支持集策略归结．

对于文中的例子，对所有事实公式测试之后，可得到下述备选矛盾集：｛七一Ｚ，Ｚ—ｍｍ一］，ｌＡ］Ｄ，七一，，，一＾，ｈ一

咒），（惫＿’Ｚ，ｌ一研，优一］咒Ａ］ｏ，忌＿’厂＇，斗ｈ，ｈ一竹，行一０｝，｛歹一点，量÷Ｚ，Ｚ啼ｉｎ，ｍ斗］咒＾］Ｄ，忌斗厂，，一ｈ，ｈ一行），｛ｊ—ｋ，量一Ｚ，Ｚ—ｍ，优一］竹＾１ｏ，惫一，＇，一ｈ，ｈ一，ｌ，雄一０｝，｛ｇ—ｉ，，一ｈ，ｈ一１ｉ｝，｛ｅ一，＾ｇ，ｇ—ｉ，，一＾，ｈ一

１

ｉ｝，｛口一ｃ，ｃ一１

ｄ，ｎ

Ａｂ—ｄ｝．

（２）极小矛盾集的产生．可以接着从上述备选矛盾集中产生≥：中所有的极小矛盾集．首先将所有备选矛盾集按其基数

由小到大排序．从首个集合开始，逐一比较该集合与其后的集合，如果该集合是后面某集合的子集，就删除后面的这个集合．再从第２个集合开始重复该操作，直到末尾集合．最后余下的集合都是极小矛盾集．具体由过程３实现．

过程３：从备选矛盾集产生芝：中所有的极小矛盾集．

输入：Ｆ－Ｑｕｅｕｅ（备选矛盾集ｒＩ）

输出：Ｆ－Ｑｕｅｕｅ（∑中所有极小矛盾集ｒｎ）

方法：将所有备选矛盾集ｒｉ按Ｉｒｉｌ由小到大排序；ｊ＝１；

ｗｈｉｌｅ（ｆｉｎｉｓｈｅｄ＝ｆａｌｓｅ）

ｒｅｔｕｒｎ

｛ｉｆ（ｒｊ是队尾）ｔｈｅｎｆｉｎｉｓｈｅｄ＝ｔｒｕｅ

ｅｌｓｅ｛逐一比较ｒｊ与它后面的所有元素ｒｋ

ｉｆ（ｒＪ∈Ｆｋ）删除ｒｋ；ｊ＋＋；｝｝

ｒ－Ｑｕｅｕｅ

Ｉ

下面给出的算法１将通过调用上述过程对初始关联规则集∑进行处理，产生∑中所有的极小矛盾集．算法１：产生∑中所有的极小矛盾集．输入：∑（初始关联规则集）输出：ｒ（∑中所有的极小矛盾集）方法：ｐ＿－－∑中所有前，后件构成的集合；置空队列一；

ｆｏｒＰ中的每个元素Ｘ

｛ｃａｌｌ过程２；

过程２的输出加入队列一；｝）ｉｆ队列ｒ’非空ｔｈｅｎ｛ｃａｌｌ过程３，

ｒｅｔｕｍ过程３的输出ｒ；｝

ｅｌｓｅ

ｒｅｔｕｒｎ

｛ｃａｌｌ过程１（∑Ｕ｛Ｘ｝）；ｉｆ过程１的输出非空

ＮＵＬＬ；

对于文中的例子，得出≥：中的极小矛盾集包括：｛五一ｚ，ｚ—ｍ，ｍ一］咒＾］Ｄ，忌一，，，一．Ｉｌ，ｈ—ｎ），｛ｇ—ｉ，，一ｈ，

ｈ一１ｉ｝，｛ａ—ｃ，ｃ一１ｄ，口Ａｂ—ｄ）．

２．３修正关联规则集≥：

为得到一致的关联规则集合，最简单的方法就是在每个极小矛盾集中删除１条规则．为了尽可能少地修改初始规则集，

对≥：中所有的极小矛盾集进行预处理，目的是删除最小数目的规则实现在每个极小矛盾集中至少删除１条规则．

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说公务员考试数据挖掘中关联规则集的优化(2)在线全文阅读。