约束关联规则的增量式维护算法.doc

计 算 机 研 究 与 发 展 JOU RN A L O F COM PU T ER R E SEA R CH D EV EL O PM EN T 第 38 卷 第 8 期 2001 年 8 月 V o l138, N o 18 A ug. 2001 约束关联规则的增量式维护算法 寇育敬 王春花 黄厚宽 ( 北方交通大学计算机与信息技术学院 北京 100044) (ko uyu jing@ 263. ne t) 摘 要 关联规则的挖掘是一个重要的数据挖掘问题, 在关联规则的挖掘过程中加入约束条件, 是实现用户参与 挖掘的一种方式. 在有约束的关联规则挖掘过程中, 用户会不断调整约束条件, 并要求更新挖掘结果. 针对这种情 况, 提出了约束关联规则的增量式维护算法 Sep a ra te M , 当约束条件发生变化时, 在原有挖掘结果的基础上实现增 量式更新, 较重新运行 Sep a ra te 算法而言, 减小了有哪些信誉好的足球投注网站空间, 节约了时间, 提高了挖掘效率. 关键词 数据挖掘, 关联规则, 项约束, 增量式算法, 频繁项目集 中图法分类号 T P 311 A N INCREM ENTAL AL GO R ITHM FO R M A INTA IN ING CO NSTRA INED A SSOC IA T IO N RUL ES KOU Y u 2J in g, W A N G C h u n 2H u a, an d HU A N G H o u 2K u an (S ch ool of C om p u ter S cience and I nf orm a tion T ech onology , N or th ern J iaotong U n iv ersity , B eij ing 100044) A bstra c t M in in g o f th e a sso c ia t io n ru le s is an im po r tan t issu e in th e da ta m in in g f ie ld. In th e p ro ce ss o f m in in g a sso c ia t io n ru le s, u se r s m ay add co n st ra in t s. In fac t th is h a s b een a w ay fo r u se r s to in te rac t w ith m in in g p ro ce ss, D u r in g th is p ro ce ss, co n st ra in t s m ay b e ch an ged co n stan t ly an d u se r s a lw ay s dem an d th e up da te o f th e m in in g re su lt acco rd in g to th e ch an ged co n st ra in t s. A im ed a t th is p ro b lem , an in c rem en ta l a lgo r ithm , n am ed Sep a ra te M , fo r m a in ta in in g co n st ra in ed a sso c ia t io n ru le s is p re sen ted. It can u se in fo rm a t io n f rom th e la st m in in g p ro ce ss an d avo id ru n n in g th e Sep a ra te a lgo r ithm o ve r aga in. In th is w ay, th e t im e can b e sho r ten ed an d th e eff ic ien cy o f da ta m in in g p ro ce ss can b e im p ro ved. Key word s da ta m in in g, a sso c ia t io n ru le s, co n st ra in t, in c rem en ta l a lgo r ithm , f requ en t se t item A p r io r i 为核心, 或者是其变体, 或者是其扩展2 . 经 典的关联规则挖掘算法, 一般是给定了支持度和可 信度, 算法自动实现关联规则的挖掘过程, 最后给出