计算机研究与发展ＩＳＳＮ１０００’１２３９１ＣＮ１１—１７７７１ＴＰＪｏｕｒｎａｌｏｆＣｏｍｐｕｔｅｒＲｅｓｅａｒｃｈａｎｄＤｅｖｅｌｏｐｍｅｎｔ４７（２）：２７７～２８５，２０１０
一种新的频繁项集精简表示方法及其挖掘算法的研究
宋威１李晋宏１’２徐章艳３杨炳儒２
－（北方工业大学信息工程学院北京１００１４４）
２（北京科技大学信息工程学院北京１０００８３）
。（广西师范大学计算机科学与信息工程学院广西桂林５４１００４）
（ｓｇｙｚｆｒ＠ｙａｈｏｏ．ｅｏｍ．ｃｎ）
ＲｅｓｅａｒｃｈｏｎａＮｅｗＣｏｎｃｉｓｅＲｅｐｒｅｓｅｎｔａｔｉｏｎｏｆＦｒｅｑｕｅｎｔｌｔｅｍｓｅｔａｎｄＩｔｓＭｉｎｉｎｇＡｌｇｏｒｉｔｈｍ
ＳｏｎｇＷｅｉｌ，ＬｉＪｉｎｈｏｎ９１”，ＸｕＺｈａｎｇｙａｎ３，ａｎｄＹａｎｇＢｉｎｇｒｕ２
‘（ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＮｏｒｔｈＣｈｉｎａＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ。Ｂｅｉｊｉｎｇ１００１４４）
２（ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙＢｅｉｊｉｎｇ，Ｂｅｉｊｉｎｇ１０００８３）
３（ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＩｔ，ＩｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＧｕａｎｇｘｉＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｇｕｉｌｉｎ，Ｇｕａｎｇｘｉ５４１００４）ＡｂｓｔｒａｃｔＦｒｅｑｕｅｎｔｉｔｅｍｓｅｔｍｉｎｉｎｇｈａｓｂｅｃｏｍｅａｎｉｍｐｏｒｔａｎｔｄａｔａｍｉｎｉｎｇｔａｓｋａｎｄｆｌｆｏｃｕｓｅｄｔｈｅｍｅｉｎｄａｔａｍｉｎｉｎｇｒｅｓｅａｒｃｈ．Ｔｈｅｂｏｔｔｌｅｎｅｃｋｓｏｆｆｒｅｑｕｅｎｔｉｔｅｍｓｅｔｍｉｎｉｎｇａｒｅａｓｆｏｌｌｏｗｓ：Ｏｎｔｈｅｏｎｅｈａｎｄ，ｔｈｅｎｕｍｂｅｒｏｆａｌｌｆｒｅｑｕｅｎｔｉｔｅｍｓｅｔｓｉｓｕｓｕａｌｌｙｅｘｔｒｅｍｅｌｙｌａｒｇｅ．Ｏｎｔｈｅｏｔｈｅｒｈａｎｄ，ｔｈｅｒｅｉｓｏｆｔｅｎｓｅｖｅｒｅｒｅｄｕｎｄａｎｃｙｉｎｔｈｅｒｅｓｕｌｔａｎｔｉｔｅｍｓｅｔｓ．Ｔｏｏｖｅｒｃｏｍｅｔｈｅｓｅｐｒｏｂｌｅｍｓ，ｒｅｃｅｎｔｌｙｓｅｖｅｒａｌｐｒｏｐｏｓａｌｓｈａｖｅｂｅｅｎｍａｄｅｔｏｃｏｎｓｔｒｕｃｔａｃｏｎｃｉｓｅｒｅｐｒｅｓｅｎｔａｔｉｏｎｏｆｔｈｅｆｒｅｑｕｅｎｔｉｔｅｍｓｅｔｓ，ｉｎｓｔｅａｄｏｆｍｉｎｉｎｇａｌｌｆｒｅｑｕｅｎｔｉｔｅｍｓｅｔｓ．ＴｈｅａｉｍｉＳｔｈａｔｔｈｅｒｅｓｕｌｔａｎｔｓｕｂｓｅｔｃａｎｅｉｔｈｅｒｓａｔｉｓｆｙｔｈｅｒｅｑｕｉｒｅｍｅｎｔｓｏｆａｐｐｌｉｃａｔｉｏｎｓ，ｏｒｃａｎｄｅｒｉｖｅａｌｌｔｈｅｏｔｈｅｒｆｒｅｑｕｅｎｔｉｔｅｍｓｅｔｓ．ＭａｘｉｍａｌｉｔｅｍｓｅｔａｎｄｃｌｏｓｅｄｉｔｅｍｓｅｔａｒｅｔＷＯｍｏｓｔｔｙｐｉｃａｌｒｅｐｒｅｓｅｎｔａｔｉｖｅｓｕｂｓｅｔｓｏｆａｌｌｆｒｅｑｕｅｎｔｉｔｅｍｓｅｔｓ．Ｂａｓｅｄｏｎｍａｘｉｍａｌｉｔｅｍｓｅｔａｎｄｃｌｏｓｅｄｉｔｅｍｓｅｔ，ａｎｅｗｃｏｎｃｉｓｅｒｅｐｒｅｓｅｎｔａｔｉｏｎｏｆｆｒｅｑｕｅｎｔｉｔｅｍｓｅｔ，ｎａｍｅｌｙｍｅｔａｉｔｅｍｓｅｔ，ｉｓｐｒｏｐｏｓｅｄ．Ｉｔｉｓｐｒｏｖｅｄｔｈａｔｂｏｔｈｍａｘｉｍａｌｉｔｅｍｓｅｔａｎｄｃｌｏｓｅｄｉｔｅｍｓｅｔａｒｅｓｐｅｃｉａｌｃａｓｅｓｏｆｍｅｔａｉｔｅｍｓｅｔ．Ｔｈｅｃａｒｄｉｎａｌｉｔｙｏｆｍｅｔａｉｔｅｍｓｅｔｉｓｂｅｔｗｅｅｎｔｈｏｓｅｏｆｍａｘｉｍａｌｉｔｅｍｓｅｔａｎｄｃｌｏｓｅｄｉｔｅｍｓｅｔ．Ｔｈｅｎ，ｐｒｏｐｅｒｔｙｏｆｍｅｔａｉｔｅｍｓｅｔｉｓｄｉｓｃｕｓｓｅｄ．Ｆｉｎａｌｌｙ，ｂｙｉｎｔｒｏｄｕｃｉｎｇｐｒｕｎｉｎｇｓｔｒａｔｅｇｉｅｓｔｏＤＣＩ－ｃｌｏｓｅｄ—ｉｎｄｅｘ，ｗｈｉｃｈｉｓａｃｌｏｓｅｄｉｔｅｍｓｅｔｍｉｎｉｎｇａｌｇｏｒｉｔｈｍ，ａｎａｌｇｏｒｉｔｈｍｆｏｒｍｉｎｉｎｇｍｅｔａｉｔｅｍｓｅｔｉｓｐｒｏｐｏｓｅｄ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｉｓｅｆｆｅｃｔｉｖｅａｎｄｅｆｆｉｃｉｅｎｔ．
Ｋｅｙｗｏｒｄｓｄａｔａｍｉｎｉｎｇ；ａｓｓｏｃｉａｔｉｏｎｒｕｌｅ；ｍａｘｉｍａｌｉｔｅｍｓｅｔ；ｃｌｏｓｅｄｉｔｅｍｓｅｔ；ｍｅｔａｉｔｅｍｓｅｔ
摘要频繁项集挖掘是数据挖掘研究领域的一个基本问题，其瓶颈在于频繁项集全集的结果过多，冗余现象严重．主要的解决思路是只挖掘全体频繁项集中有代表性的子集，使得这种子集或者可满足应用的需要或者可由它们导出其他项集．最大项集和闭项集便是这类解决方案中两种最典型的子集形式．在最大项集和闭项集的基础上，提出了元项集这一新的频繁项集精简表示方法．首先，证明了最大项集和闭项集都是元项集的特例，且元项集所包含的项集数目介于二者之间；其次，讨论了元项集的性质．最后，通过在闭项集挖掘算法ＤＣＩ—Ｃｌｏｓｅｄ—Ｉｎｄｅｘ的基础上引入剪枝策略，设计了一个元项集挖掘算法．实验结果表明，所提出的挖掘算法是有效的和高效的．
关键词数据挖掘；关联规则；最大项集；闭项集；元项集
中图法分类号ＴＰ３１１
收稿日期：２００８—０５－０４；修回日期：２００９—０６—２２
基金项目：国家自然科学基金项目（６０６７５０３０）；北京市优秀人才培养资助项目（２００９１）００５００２０００００９），北方工业大学青年重点研究基金项目；北方工业大学博士科研启动基金项目
万方数据