利用遗传思想进行数据划分的DBSCAN算法研究

摘要

数据挖掘是从海量的数据中挖掘出隐含的、先前未知的、对决策有潜在价值的知识和规则。聚类分析是数据挖掘领域中的一个重要研究课题。所谓聚类是将物理或抽象的集合分组成为类似的对象组成的多个类的过程。由聚类所生成的类是一组数据对象的集合，这些对象与同一个类中的对象彼此相似，与其它类中的对象相异。在许多应用中，可将一个类中的数据对象作为一个整体处理。当分析一个较大的、复杂的、连续的、有许多变量的数据库和完全未知的结构时，聚类是一个非常有用的工具。 目前，聚类分析算法大体上分为划分的方法，层次的方法，基于密度的方法，基于网格的方法和基于模型的方法。DBSCAN算法是一种典型的基于密度的方法，该算法的优点是可以发现任意形状的聚类，且聚类结果受噪音点影响小。但是该算法存在如下缺点：当数据量过大时，算法对主存的要求较高；算法中需使用到全局变量Eps和MinPts，若变量取值不当，会影响聚类质量；当数据分布不均匀时，采用全局统一的变量，会降低聚类质量。 针对DBSCAN算法的缺点，本文提出了一种利用遗传思想进行数据划分的DBSCAN算法(Data Partition DBSCAN using Genetic Algorithm, DPDGA)。DPDGA算法采用基于遗传算法的方法确定聚类中心。这种基于遗传算法的初始聚类中心获取方法采用了K-means算法的基本思想，但是它使用遗传算法而不是一般的迭代来进行逐步的优化。基于遗传算法的聚类中心获取方法的优点是不需要关于待分类数据的先验分布知识。实验证明，基于遗传算法的聚类中心选择方法所取得的聚类中心接近真实的聚类中心。 在使用基于遗传算法的方法获得较优的初始聚类中心后，DPDGA算法根据获得的初始聚类中心点划分数据集。对于划分得到的各个局部数据集，分别计算每个局部数据集的参数MinPts，然后对各个局部数据集分别使用DBSCAN算法进行聚类，最后合并各局部数据集的聚类结果。 DPDGA算法由于划分了数据集，降低了对主存的要求。算法中提出了计算各局部数据集参数的方法，对于分布不均匀的数据集，由于各个局部采用不同的参数值，使得算法对全局参数的依赖性降低，聚类质量更好。