论文部分内容阅读
数十年来,数据挖掘一直是一个热门话题。作为数据挖掘的一个主要技术领域,聚类分析产生了很多算法,并且演化成一个庞大家族。现有的聚类算法可以分为5类:分割算法,分层算法,基于密度算法,基于网格算法,以及基于建模的算法。也有很多算法是结合了两个或两个以上类别,以获得更好的性能。
在聚类分析的处理过程中,一方面很重要的一个问题是如何对聚类结果进行解释。用户希望聚类结果是比较容易解释和理解的,也就是如何为用户提供快捷有效的途径来调节聚类过程得到可理解的结果。为达此目的,两个问题比较关键:1)如何在聚类结果中包含尽可能多的有用信息,比如密度信息;2)如何不损失性能的前提下找到用户希望的结果。
本文相应的提出了第一个算法SDPHC:一个新的基于密度的分割和分层的算法。该算法是一个组合算法。它引入了一个新概念——密度权重,可以使得在聚类中采用人工反馈机制变得比较容易。有了反馈机制,用户就可以根据对数据的理解来对数据分类,而尽管这些数据有可能在空间上分的比较散。同时,通过对参数和聚类结果之间的分析,在参数设置方面引入一个自校技术,它可以节约用户花在最优参数设置方面的时间。理论分析和实验结果均表明该算法在性能和聚类质量方面要优于DBSCAN、PHC等算法。
另一方面,随着网络、存储、处理器等硬件方面的飞速发展,导致了极为巨大的数据库的产生,它们记录了数量巨大的高维事务信息。为了应对这种趋势,日益增长的信息隐私方面的发展要求逐渐为全球所关注,由于数据挖掘的目的就是从大规模数据库中有效的发现不明显但是非常有价值的信息,所以比较容易被误用【51。而个人用户:1)可能不愿暴露自己的特定信息;2)可能不介意给出部分真实信息;3)可能愿意给出的不是真实的但是经过修改的信息。所有的这些情况将导致缺失属性的产生。
本文相应的提出了第二个算法CLINCH:一个有效的挖掘缺失高维数据的聚类算法。CLINCH类似于大部分基于网格的算法,包括一个三步的框架,问题的解决主要在于识别出密集单元,通过逐维处理的方法识别出这些单元的方法。CLINCH在开始的几个维,采用了有效的筛选策略,很多候选被裁剪掉,因此整体的算法开销降了下来;随后还采用了一个预测机制来处理缺失数据的问题。通过实验和复杂度分析,CLINCH比CLIQUE算法要快而且聚类质量基本接近,而比FILV(DBSCAN)不但快而且聚类质量要好。