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

混合属性数据集的基于近邻图的两阶段聚类算法
混合属性数据集的基于近邻图的两阶段
聚类算法
陈新泉
(重庆三峡学院智能信息处理研究所，重庆 404000) 5
摘要:面对混合属性数据集的数据预处理需求，本文在给出若干定义及相关性质之后，提出 了一种基于近邻图的两阶段聚类算法。为提高算法的时间效率，给出了几点算法改进技术。 多个人工数据集和 UCI 标准数据集的仿真实验结果表明，对于一些具有明显聚类分布结构的
数据集，该算法经常能取得比 k-means 算法和 AP 算法更好的聚类精度，说明其具有一定的
有效性。为进一步推广并在实际中发掘出该算法的应用价值，最后给出了几点较有价值的研 10
究展望。 关键词:计算机应用技术;混合属性; 聚类特征;初级聚类; 近邻图
中图分类号:TP181
15 A Dual-Steps Clustering Algorithm Based on Two Near
Neighbor Graphs for Mixed-attributes Data Set
Chen Xinquan (Graduate School of Intelligent Information Processing, Chongqing Three Gorges University,
ChongQing 404000)
Abstract: IIn order to effectively preprocessing mixed-attributes data sets, given, this paper first 20
gives a number of definitions and related properties, then presents a dual-steps clustering algorithm based on two near neighbor graphs. To improve the time efficiency of the algorithm, some improving techniques are described. Through the simulation experiments of some artificial
data sets and UCI standard data sets, we can verify that this clustering algorithm can often obtain
better clustering quality than k-means algorithm and AP algorithm when facing to some data sets 25
with apparent clusters. So we can say this clustering algorithm has certain value. In the end, it
gives several research expectations to disinter and popularize this method.
Keywords: computer application technology; mixed attributes; cluster feature; primary cluster; near
neighbor graph
30
0 引言
由于应用领域的拓展及数据库技术的发展，从高维、海量、具有不同类型属性的数据库
中去发现潜在的模式或有价值的信息吸引了一些研究人员的注意。此时，作为数据预处理技
术的多元统计分析(聚类分析的前身)得到了进一步的研究。
从数据挖掘的角度看，聚类分析的目的是为了获取数据集的空间分布结构，进而描述那 35
[1]。因此，聚类簇可近似 些有意义、有实际价值的数据集分布结构，从而简化数据集的描述 地、概要地描述数据集。 与本文有所关联的聚类算法有层次聚类算法、基于密度的聚类算法、概率层次聚类算法、 图聚类算法等。在一些经典的聚类算法中，BIRCH 算法[2]是一个利用聚类特征树结构进行
增量聚类或动态聚类的层次聚类算法，它首先对数据集进行一次扫描来构造一个具有层次树 40
结构的子聚类集合，接着通过多次扫描来改善聚类质量，其时间复杂度为 O(n)。由于 BIRCH
算法利用半径的概念来控制聚类的生成，所以它更适合于具有球形聚类分布结构的数值型数
据集。CURE 算法[3]也是一个层次聚类算法，它从最底层的数据点开始探测聚类结构，每次
作者简介:陈新泉，(197