论文部分内容阅读
面对大规模的高维数据和各种约束条件,如何建立有效、可扩展的聚类算法是数据挖掘领域的一个研究热点。围绕以上问题,本文对聚类算法进行了深入研究,主要包括以下几个方面的内容:通过对密度类算法和网格类算法的分析,提出一种基于网格和密度综合的算法CluGD,算法使用网格方法得到反映数据空间的代表点,代表点不是实际的数据点,而是表示数据点特征的虚拟点,然后通过密度类算法对代表点进行聚类,此算法采用的参数和DBSCAN算法相同,由于采用了网格方法,算法的效率得到很大提高;又使用随机样例的方法针对参考点提出了算法GDRS;由于大规模数据中的密度变化较大,单一密度不能准确的刻画数据空间的特征,由CluGD扩展提出了算法VCluGD,此算法使用预处理过程给出数据空间内给定邻域半径后点密度和点数量的关系图,方便用户设置多级参数,从而进行多级聚类,获得较好的聚类效果。三种算法都具有对于数据集大小的线性时间复杂度,适合大规模数据的聚类问题。通过研究和分析处理非空间约束聚类算法的一些优点和不足,对DBSCAN算法进行扩展提出了DBSCAN+算法,然后针对非空间的高维特性提出使用SOM神经网络算法辅助进行处理,DBSCAN+对非空间数据采用按照不同数据类型分别计算相异度的方法,并给出了试验结果。辅助进行处理的方法是首先使用SOM对高维数据聚类的维进行选择,然后对候选维使用DBSCAN+算法聚类,或在候选维的基础上使用SOM方法进行非空间聚类,并把SOM和DBSCAN+两种算法的聚类结果相结合,试验表明算法是有效的。针对现有空间约束聚类的缺点,提出一种可以处理空间约束的算法DBOF。该方法对空间约束分为三种对象:障碍对象,通达对象,既具有障碍作用又具有通达作用的对象。对于障碍对象采用多边形建模,对于通达对象采用图拓扑的方法建模,对第三种约束采用带有穿越点属性的图拓扑进行建模。对于障碍对象采用完整的障碍距离衡量两点之间的距离,而对于后两种约束由于采用了图拓扑的方法,有利于算法的实际应用。试验结果表明,DBOF算法具有更好的聚类效果,并且具有良好的运行效率。