X-means:一种针对聚类个数的 K-means 算法改进
尽管 K-means 很受欢迎,但是他有不可避免的三个缺点:1、它的计算规模是受限的。2、
它的聚类个数 K 必须是由用户手动指定的。3、它的搜索是基于局部极小值的。在本文中,
我们引入了前两种问题的解决办法,而针对最后一个问题,我们提出了一种局部补救的措施。
根据先前有关算法改进的工作,我们引入了一种根据 BIC(Bayesian Information Criterion)或
者 AIC(Akaike information criterion)得分机制而确定聚类个数的算法,本文的创新点包括:
两种新的利用充分统计量的方式,还有一种有效地测试方法,这种方法在 K-means 算法中可
以用来筛选最优的子集。通过这样的方式可以得到一种快速的、基于统计学的算法,这种算
法可以实现输出聚类个数以及他们的参量值。实验表明,这种技术可以更科学的找出聚类个
数 K 值,比利用不同的 K 值而重复使用 K-means 算法更快速。
K-means 算法在处理量化数据中已经用了很长时间了,它的吸引力主要在于它很简单,
并且算法是局部最小化收敛的。但是它有三点不可避免的缺点:首先,它在完成每次迭代的
过程中要耗费大量的时间,并且它所能处理的数据量也是很少的。第二,聚类个数 K 值必须
由用户自身来定义。第三,当限定了一个确定的K 值时,K-means 算法往往比一个动态 K 值
的算法表现的更差。我们要提供针对这些问题的解决办法,通过嵌入树型的数据集以及将节
点存储为充分统计变量的方式来大幅度提高算法的计算速度。确定中心的分析算法要考虑到
泰森多边形边界的几何中心,并且在估计过程的任何地方都不能存在近似的方法。另外还有
一种估计方法,“黑名单”,这个列表中将会包含那些需要在指定的区域内被考虑的图心。这
种方法不仅在准确度上以及处理数据的规模上都表现的非常好,而这个快速算法在 X-means
聚类算法当中充当了结构算法的作用,通过它可以很快的估计K 值。这个算法在每次使用
K-means 算法之后进行,来决定一个簇是否应该为了更好的适应这个数据集而被分开。决定
的依据是 BIC 得分。在本文中,我们阐述了“黑名单”方法如何对现有的几何中心计算BIC
得分,并且这些几何中心所产生的子类花费不能比一个单纯的K-means 聚类算法更高。更进
一步的,我们还通过缓存状态信息以及估计是否需要重新计算的方法来改善估计方法。
我们已经用 X-means 算法进行了实验,验证了它的确比猜 K 值更加科学有效。X-means
算法可以在人造的或者是真实数据中表现的更好,通过 BIC 得分机制。它的运行速度也是比
K-means 更快的。
我们首先描述简单的 K-means 算法应该考虑哪些因素。通过 K-means 可以把一定量的数
据集分为 K 个数据子集,这 K 个数据子集分别围绕着 K 个聚类中心。这种算法保持着 K 个
聚类中心不变,并且通过迭代不断调整这K 个聚类中心。在第一次迭代开始之前,K 个聚类
中心都是随机选取的,算法当聚类中心不再变化的时候返回最佳的结果,在每一次迭代中,
算法都要进行如下的动作:
1、 对于每一个节点向量,找到距离它最近的聚类中心,归入此类。
2、 重新评估每一个图心的位置,对于每一个图心,必须是簇的质心。
K-means 聚类算法通过局部最小化每个向量到对应图心的距离来实现聚类。同时,它处
理真实数据时是非常慢的。许多情况下,真实的数据不能直接用 K-means 进行聚类,而要经
过二次抽样筛选之后再进行聚类。Ester 曾经提出了一种可以从树形数据中获得平衡的抽样
数据的方法。Ng 和 Han 曾经提出了一种可以指导概率空间对输入向量的检索模拟模型。