论文部分内容阅读
关联规则自提出以来,受到很多研究者的关注。它在现实中也得到了广泛的应用。但是它仍有很多问题有待于解决。除了发现频繁集和关联规则的效率问题以外,从算法的结果来看存在的两个问题是:第一,产生的规则数量太多(规则数量问题);第二,在结果中真正令人感兴趣的规则比例太小(规则质量问题)。本文着重解决第二个问题。关联规则发现问题可以归纳为四个要素:数据集、规则形式、搜索方法、兴趣度量。它们分别对应机器学习问题中的数据空间、假设空间、算法、评价标准。实际上,采用何种搜索算法是由其他三个要素决定的。我们的工作是分别从优化数据集、简化规则形式和优化兴趣度量这三个方面提高规则质量。第一,从优化兴趣度量的角度出发,采用残差分析检测项(集)间是否独立,如果不独立,则用互信息度量它们之间的相关强度。在此基础上,提出了发现最优正/负相关规则的算法。为避免产生过多的平凡规则,根据残差分析度量和互信息的特点,使用遗传算法产生最优规则。在优化过程中,同时完成了对规则的修剪:通过适应度函数的设置,可以很好地控制输出规则的长度,从而避免了产生太多难以理解的规则。第二,从优化数据集的角度出发,提出了两种适用于数量关联规则的无监督多元离散化算法:EMVD-BDC和OMVD。关联规则发现任务是无监督的,而且需要产生的规则能够反映属性间的相互作用。基于这些原因,无监督和多元离散化算法非常适合关联规则发现任务。EMVD-BDC的思想是通过密度聚类把无监督任务转化为有监督的。把聚类结果看作不同的类,最终的分割点要能够较好地分割这些类,并且分割点不能太多。遗传算法很好地完成了这一任务。OMVD是对一种多元离散化算法(MVD)的改进。OMVD真正实现了同步多元离散化。即,所有属性的分割点是同时产生的,一个分割点的位置取决于其他属性的最终分割点的位置。这样更能反映项(集)间的相互作用。实验表明,OMVD具有比MVD更强的搜索支持度差异的能力。