随着时代发展,特别是近几年进入数据爆炸的时代,数据挖掘领域的重要性越发凸显。而一些经典的算法及其改进已经无法满足日益增长的对数据处理的要求了。聚类,作为数据挖掘中一个重要的领域,对于更加优秀的聚类算法的需求也是日益迫切。在新时代,对聚类算法的时空间效率以及聚类效果当然要求更高,但是新时代对其的要求并不止于此,一个优秀的聚类算法除此之外还应该具有以下性质：可扩展性和可伸缩性；识别任意形状的类簇的能力；自动确定类簇数的能力；输入参数足够少；输入参数敏感性足够低；具有对离群点的识别能力；对输入数据的兼容性；可约束性等。决策图(Decision Graph)聚类算法,可简称DG算法,根据作者论文标题首字母缩写又可叫CFSFDP算法。于2014年6月在Science杂志上一经刊载出来就受到了广泛的讨论。该算法几乎完全具备以上性质,比如它不需要事先指定聚类数量；需提前设定的参数很少,只有一个,且敏感度较低；可以非常简单地确定离群点；整体算法复杂度比一般的K-means算法的复杂度更低；可以得到非球形的聚类结果,可以很好地识别异形数据分布。除此之外DG算法还具有其他非常优秀的性质,能够仅以待聚类点之间的距离矩阵作为输入数据,而并不需要将点映射到向量空间中;算法稳定,只要输入的数据源是同样的,那么得到的聚类结果也是同样的等。而最重要的是,DG算法在选取聚类中心的算法思想上另辟蹊径,非常简洁巧妙。对于该算法,有对其选取聚类中心的巧妙方法大加赞扬的；也有对该算法的如选取聚类中心需要人工参与等问题进行质疑的。笔者对此是持肯定态度的,毕竟该算法优秀之处有目共睹,不足之处也并不是硬伤,经过广泛的优化改进之后,其未必不能成为聚类领域的又一经典算法。文本也是在对该算法的问题发现以及解决改进方面提供了一份贡献。本文的主要内容就是针对笔者发现的一个该算法设计上的问题：密度冲突问题。该问题主要是出在计算决策图算法的重要参数δ时,对需要考虑的基于另外一个重要参数ρ的判断条件存在漏洞。于是本文之后举出该问题会导致的错误聚类结果,然后就该问题设计了两种分别基于δ和基于ρ的改进方案。然后在设计、实现了这两种改进算法后,用对比性实验验证了原算法的出现的错误以及改进算法的解决效果,以及用验证性实验验证了改进决策图算法最主要的两大特点：可以是被异形类簇、可以不依赖于数据点之间的空间分布而只以数据点之间的距离矩阵作为输入数据。最后针对决策图算法选择聚类中心的另辟蹊径的巧妙算法的应用,选择将其实现于简单经典的K-means算法上。设计并实现了新算法DG-means之后,设计对比实验验证了新算法相比于K-means算法的各项优秀性质。间接证明了DG算法在选取聚类中心上的优秀效果。