论文部分内容阅读
关联分析又称关联挖掘,主要目的是在交易数据、关系数据或者其它信息载体中,挖掘存在于项目集合或者对像集合中的频繁模式、关联、相关性或者因果结构等。本文将所有基于事务和非基于事务的关联分析称为广义的关联分析。基于事务的关联分析主要依托支持度—置信度框架进行数据挖掘,而非基于事务的关联分析常采用参与度—条件概率框架。首先,提出了强关联规则的评估体系:正确性、可靠性和有趣性。传统的关联分析框架要么只能保证强关联规则的正确性和可靠性,要么只能保证强关联规则的正确性和有趣性,本文提出了蕴涵—约束框架,可以保证强关联规则正确、可靠、有趣。其次,提出并论证了最小支持度min_sup和最小置信度,nin_conf的合理取值范围,从而将最小置信度由支持度—置信度框架下的(0,1]缩小为蕴涵—约束框架下的(0.5,1],最小支持度由(0,1]缩小为(0, min_conf)。第3,提出随机顶点极大团划分法,它能将非基于事务的关联分析转化为基于事务的关联分析,从而使广义关联分析问题整合成为基于事务的关联分析问题,且在更新实例以后只需修改局部划分即可形成新的划分。第4,基于映射的概念,将约束划分为事前、事中和事后约束,从而形式化地解决了约束的应用及方法。第5,根据支持度的单调性,提出了nulti-dimensions and multi-layers算法。该算法能解决一般地多维多层的关联分析问题,且具有较高地效率。第6,利用稠密维和稀疏维,提出了一种multi-knowledge tree的树形存储结构,能有效降低算法的空间复杂度;基于前者提出了multi-pruning算法,该算法在数据增加、删除、修改后无论频繁项集是否满足向下闭合性都能快速获取新的强关联规则。最后,大量实验验证了所提出理论和算法的效果和效率。