论文部分内容阅读
随着聚类分析的应用领域日益扩展,越来越多高维的、混合类型属性数据需要处理。然而现有的大部分算法要么只能对低维数据有效,要么只能处理某一种特定类型的数据。针对这两个矛盾,对高维的、三种混合类型(二元型,类别型,数值型)属性数据的聚类算法做了一些研究。
首先,基于密度的分组方法(DGM)将数据集中每一维的数值型数据分别离散化,用区间标号替代其实际的数据值。然后,将数据集中所有有效数据统一编号,转化成一个类别型数据集,去掉空缺值并添加事务标识符后成为一个事务数据库。在定义了最长频繁闭项集(LFCI)的概念后,利用LFCI的两个关键属性,即(1)LFCI最大地覆盖了事务;(2)LFCI能够作为事务的描述,可将具有相同LFCI的事务归为一簇。为了适应聚类的要求,对传统的频繁模式树(FP-树)从三个方面进行了改造,并详细叙述了改造FP-树的创建。分析挖掘LFCI的过程后,更新FP-树以降低空间复杂度;根据LFCI的特点,导出无效树的剪切策略以降低时间复杂度,给出的LFCI-增长方法挖掘出每个事务的LFCI。从事务的多个LFCI中,选取一个作为该事务的描述,插入到定义的簇树中。每一个从根节点到链接有事务标识符的节点即为一个簇,其路径中的项对应于相关维,事务标识符对应于相关点。以上过程被总结成一个对高维混合属性数据的聚类框架,它本质上是投影聚类方法。
为了验证聚类框架的性能,在模拟数据集上做了基于最长频繁闭项集的算法(CA-LFCI)的伸缩性,对高维数据处理,对不同类型属性处理,健壮性等方面的实验。仿真实验表明,CA-LFCI具有较好的综合性能。另外,还将算法应用在两个真实数据集Votes和Mushroom上。结果表明,在算法的输入参数——最小支持度小于22%的情况下,对Votes数据集,精确度保持在95%以上,最高可达98.62%,运行时间少于0.71秒;对Mushroom数据集,精确度保持在97%以上,最高可达99.8%,运行时间少于5.5秒。此外,结果是可用的和可解释的。