混合属性数据集的基于近邻图的两阶段聚类算法.doc

混合属性数据集的基于近邻图的两阶段聚类算法混合属性数据集的基于近邻图的两阶段聚类算法陈新泉(重庆三峡学院智能信息处理研究所,重庆404000)5摘要:面对混合属性数据集的数据预处理需求,本文在给出若干定义及相关性质之后,提出了一种基于近邻图的两阶段聚类算法。为提高算法的时间效率,给出了几点算法改进技术。多个人工数据集和UCI标准数据集的仿真实验结果表明,对于一些具有明显聚类分布结构的数据集,该算法经常能取得比k-means算法和AP算法更好的聚类精度,说明其具有一定的有效性。为进一步推广并在实际中发掘出该算法的应用价值,最后给出了几点较有价值的研10究展望。关键词:计算机应用技术;混合属性;聚类特征;初级聚类;近邻图中图分类号:TP18115ADual-raphsforMixed-attributesDataSetChenXinquan(GraduateSchoolofIntelligentInformationProcessing,esUniversity,ChongQing404000)Abstract:IInordertoeffectivelypreprocessingmixed-attributesdatasets,given,thispaperfirst20givesanumberofdefinitionsandrelatedproperties,thenpresentsadual-,,wecanverifythatthisclusteringalgorithmcanoftenobtainbetterclusteringqualitythank-,;mixedattributes;clusterfeature;primarycluster;raph300引言由于应用领域的拓展及数据库技术的发展,从高维、海量、具有不同类型属性的数据库中去发现潜在的模式或有价值的信息吸引了一些研究人员的注意。此时,作为数据预处理技术的多元统计分析(聚类分析的前身)得到了进一步的研究。从数据挖掘的角度看,聚类分析的目的是为了获取数据集的空间分布结构,进而描述那35[1]。因此,聚类簇可近似些有意义、有实际价值的数据集分布结构,从而简化数据集的描述地、概要地描述数据集。与本文有所关联的聚类算法有层次聚类算法、基于密度的聚类算法、概率层次聚类算法、图聚类算法等。在一些经典的聚类算法中,BIRCH算法[2]是一个利用聚类特征树结构进行增量聚类或动态聚类的层次聚类算法,它首先对数据集进行一次扫描来构造一个具有层次树40结构的子聚类集合,接着通过多次扫描来改善聚类质量,其时间复杂度为O(n)。由于BIRCH算法利用半径的概念来控制聚类的生成,所以它更适合于具有球形聚类分布结构的数值型数据集。CURE算法[3]也是一个层次聚类算法,它从最底层的数据点开始探测聚类结构,每次作者简介:陈新泉,(1974-),男,副教授,主要研究方向为:数据挖掘等。E-mail:chenxqscut@-1-搜索出最相近的两个聚类进行合并,直到设定的聚类数目为止。由于CURE算法利用固定数目的多个分散点来表示一个聚类,所以它可以发现数值型数据集中具有任意形状的聚类区452),高维域。但CURE算法对参数比较敏感,而且需要较高的时间复杂度(低维数据需要O(n数据需要O(n2?logn)),所以在处理海量数据时,必须采用一些基于抽样、划分的改进技术。ROCK算法[4]是一个通过反复地对两个相邻簇进行合并的层次聚类算法,它可以处理布尔型或类别型数据集。CHAMELEON算法[5]则是一个基于动态建模的层次聚类算法,它首先通过图划分算法来获取大量较小的子聚类,然后采用一个凝聚型层次聚类算法来反复地合并子50聚类,最终探测出真实的聚类簇。该算法是通过计算聚类内部和聚类间的互连性及近似度来自适应地探测数据集的聚类分布结构。由于该算