聚类是数据挖掘中用来发现数据分布和隐含模式的一项重要技术。论文首先总结了数据挖掘中的聚类算法,并着重分析了几种经典的聚类算法:KMeans、DBSCAN,CLIQUE,分析了它们的各自的优缺点及算法的各种改进措施。论文接着简要介绍了Voronoi图。作为计算几何中的一个重要分支,Voronoi具有很多优良的特性,特别是它的最近邻特性,因此它在诸多领域都有应用。而它的这个特性,与基于原型的聚类算法有着理论上的相似性,因此利用Voronoi图进行聚类是可行的。论文简要介绍了各种Voronoi图的构造方法,并给出了增量构造法的一般过程。为了利用Voronoi图进行聚类,必须构造封闭区域的Voronoi图。论文提出一种构造封闭区域的Voronoi图的方法:先在整个空间上构造Voronoi图,并构造出封闭区域(一般是矩形),然后找出Voronoi图中非封闭单元,然后循环一周求出这些非封闭单元与封闭曲线的交点,其它的单元不发生改变,这样就可以得到封闭区域上的Voronoi图。并可得到每个单元的顶点序列,还可以计算每个单元的面积。在着重分析了基于密度与网格的聚类算法的基础上,提出了基于Voronoi图的聚类算法。算法利用Voronoi图构建平面上不规则的网格,利用Voronoi图的最近邻特性将不同网格中的点归于不同的类。利用网格点密度来自动调整最终的聚类数,利用前后质心变化来调整Voronoi母点的位置,最终的Voronoi单元就是聚类结果。算法能自动确定聚类数,还能自动识别低密度点。实验证明,该算法能对平面上的数据点集进行有效的聚类,性能与改进的Kmeans算法Xmeans相当,比基于密度的聚类算法DBSCAN、Optics更有效,当实验数据集规模较大时优势较为明显。论文还运用改进的算法来解决一类应用地理信息进行规划决策的实际问题。论文最后对算法的进一步改进提出了一些思路。