基于概念格的无冗余关联规则提取算法.pdf

第３２卷第４期　　　 计算机应用与软件 Ｖｏｌ．３２ Ｎｏ．４ ２０１５ 年４ 月　　 Ｃｏｍｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ ａｎｄ Ｓｏｆｔｗａｒｅ Ａｐｒ．２０１５ 基于概念格的无冗余关联规则提取算法 翟　悦　秦　放 （大连科技学院信息科学系　辽宁 大连 １１６０５２） 摘　要　　针对传统挖掘算法生成的关联规则存在大量冗余、难于理解和应用的问题，提出一种新的频繁闭项集概念格ＦＣＩＬ（Ｆｒｅ- ｑｕｅｎｔ Ｃｌｏｓｅｄ Ｉｔｅｍｓｅｔｓ Ｌａｔｔｉｃｅｓ），用于生成无冗余关联规则。首先，对概念格理论进行研究，概念格节点间的泛化和例化关系非常适合 规则提取；然后，结合频繁闭项集能有效减少规则数目的特点，构建一种新的ＦＣＩＬ；最后，给出ＦＣＩＬ构造算法和相应的规则提取算 法。实验表明，该方法能够高效地产生无冗余规则集。 关键词　　频繁闭项集　ＦＣＩＬ　无冗余关联规则 中图分类号　ＴＰ３０１．０６　　　　文献标识码　Ａ　　　　ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００-３８６ｘ．２０１５．０４．０１１ ＣＯＮＣＥＰＴ ＬＡＴＴＩＣＥ-ＢＡＳＥＤ ＥＸＴＲＡＣＴＩＯＮＡＬＧＯＲＩＴＨＭＦＯＲ ＮＯＮ-ＲＥＤＵＮＤＡＮＣＹ ＡＳＳＯＣＩＡＴＩＯＮＲＵＬＥＳ Ｚｈａｉ Ｙｕｅ　Ｑｉｎ Ｆａｎｇ （Ｄｅｐａｒｔｍｅｎｔ ｏｆＩｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ，Ｄａｌｉａｎ Ｉｎｓｔｉｔｕｔｅ ｏｆＳｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｄａｌｉａｎ１１６０５２，Ｌｉａｏｎｉｎｇ，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ　　Ａｓｓｏｃｉａｔｉｏｎ ｒｕｌｅｓ ｇｅｎｅｒａｔｅｄ ｂｙ ｔｒａｄｉｔｉｏｎａｌ ｍｉｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｈａｖｅ ａ ｌａｒｇｅ ｎｕｍｂｅｒ ｏｆ ｒｅｄｕｎｄａｎｃｉｅｓ，ｗｈｉｃｈ ａｒｅ ｈａｒｄ ｔｏ ｂｅ ｕｎｄｅｒｓｔｏｏｄ ａｎｄ ａｐｐｌｉｅｄ．Ａｉｍｉｎｇ ａｔ ｔｈｉｓｐｒｏｂｌｅｍ，ｗｅ ｐｒｅｓｅｎｔ ａ ｎｅｗｆｒｅｑｕｅｎｔ ｃｌｏｓｅｄ ｉｔｅｍｓｅｔ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ （ＦＣＩＬ），ｗｈｉｃｈ ｃａｎ ｇｅｎｅｒａｔｅ ｎｏｎ- ｒｅｄｕｎｄａｎｃｙ ａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓ．Ｆｉｒｓｔ，ｗｅ ｓｔｕｄｙｔｈｅｔｈｅｏｒｙｏｆｃｏｎｃｅｐｔｌａｔｔｉｃｅ，ｔｈｅ ｇｅｎｅｒａｌｉｓａｔｉｏｎａｎｄ ｓｐｅｃｉａｌｉｓａｔｉｏｎｒｅｌａｔｉｏｎｓｂｅｔｗｅｅｎｔｈｅ ｎｏｄｅｓｏｆ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ａｒｅ ｖｅｒｙ ｓｕｉｔａｂｌｅ ｆｏｒ ｒｕｌｅ ｅｘｔｒａｃｔｉｏｎ；ｔｈｅｎ，ｗｅ ｂｕｉｌｄ ａ ｎｅｗ ＦＣＩＬ ｉｎ ｃｏｍｂｉｎａｔｉｏｎ ｗｉｔｈ ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃ ｏｆ ｆｒｅｑｕｅｎｔ ｃｌｏｓｅｄ ｉｔｅｍｓｅｔｓｗｈｉｃｈ ｃａｎ ｅｆｆｅｃｔｉｖｅｌｙ ｒｅｄｕｃｅ ｔｈｅ ｎｕｍｂｅｒ ｏｆｒｕｌｅｓ；ｆｉｎａｌｌｙ，ｗｅ ｄｅｖｅｌｏｐ ｔｈｅ ＦＣＩＬ ｃｏｎｓｔｒｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ａｎｄ ｔｈｅ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｒｕｌｅｓ ｅｘｔｒａｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ．Ｅｘｐｅｒｉｍｅｎｔ ｓｈｏｗｓ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄ ｃａｎ ｅｆｆｉｃｉｅｎｔｌｙ ｇｅｎｅｒａｔｅ ｎｏｎ-ｒｅｄｕｎｄａｎｃｙ ｒｕｌｅｓ ｓｅｔ． Ｋｅｙｗｏｒｄｓ　　Ｆｒｅｑｕｅｎｔ ｃｌｏｓｅｄ ｉｔｅｍｓｅｔｓ　Ｆｒｅｑｕｅｎｔ ｃｌｏｓｅｄ ｉｔｅｍｓｅｔｓ ｌａｔｔｉｃｅ　Ｎｏｎ-ｒｅｄｕｎｄａｎｃｙ ａｓｓｏｃｉａｔｉｏｎ ｒｕｌｅ １）根据频繁 生成完整的无冗余关联规则。方法分为两个步骤： ０　引　言