X-means：一种针对聚类个数的K-means算法改进5页

1、X-means：一种针对聚类个数的K-means算法改进摘要尽管K-means很受欢迎，但是他有不可避免的三个缺点：1、它的计算规模是受限的。2、它的聚类个数K必须是由用户手动指定的。3、它的搜索是基于局部极小值的。在本文中，我们引入了前两种问题的解决办法，而针对最后一个问题，我们提出了一种局部补救的措施。根据先前有关算法改进的工作，我们引入了一种根据BIC（Bayesian Information Criterion）或者AIC（Akaike information criterion）得分机制而确定聚类个数的算法，本文的创新点包括：两种新的利用充分统计量的方式，还有一种有效地测试方法，这种

2、方法在K-means算法中可以用来筛选最优的子集。通过这样的方式可以得到一种快速的、基于统计学的算法，这种算法可以实现输出聚类个数以及他们的参量值。实验表明，这种技术可以更科学的找出聚类个数K值，比利用不同的K值而重复使用K-means算法更快速。1、 介绍K-means算法在处理量化数据中已经用了很长时间了，它的吸引力主要在于它很简单，并且算法是局部最小化收敛的。但是它有三点不可避免的缺点：首先，它在完成每次迭代的过程中要耗费大量的时间，并且它所能处理的数据量也是很少的。第二，聚类个数K值必须由用户自身来定义。第三，当限定了一个确定的K值时，K-means算法往往比一个动态K值的算法表现的更

3、差。我们要提供针对这些问题的解决办法，通过嵌入树型的数据集以及将节点存储为充分统计变量的方式来大幅度提高算法的计算速度。确定中心的分析算法要考虑到泰森多边形边界的几何中心，并且在估计过程的任何地方都不能存在近似的方法。另外还有一种估计方法，“黑名单”，这个列表中将会包含那些需要在指定的区域内被考虑的图心。这种方法不仅在准确度上以及处理数据的规模上都表现的非常好，而这个快速算法在X-means聚类算法当中充当了结构算法的作用，通过它可以很快的估计K值。这个算法在每次使用K-means算法之后进行，来决定一个簇是否应该为了更好的适应这个数据集而被分开。决定的依据是BIC得分。在本文中，我们阐述了“

4、黑名单”方法如何对现有的几何中心计算BIC得分，并且这些几何中心所产生的子类花费不能比一个单纯的K-means聚类算法更高。更进一步的，我们还通过缓存状态信息以及估计是否需要重新计算的方法来改善估计方法。我们已经用X-means算法进行了实验，验证了它的确比猜K值更加科学有效。X-means算法可以在人造的或者是真实数据中表现的更好，通过BIC得分机制。它的运行速度也是比K-means更快的。2、 定义我们首先描述简单的K-means算法应该考虑哪些因素。通过K-means可以把一定量的数据集分为K个数据子集，这K个数据子集分别围绕着K个聚类中心。这种算法保持着K个聚类中心不变，并且通过迭代不

5、断调整这K个聚类中心。在第一次迭代开始之前，K个聚类中心都是随机选取的，算法当聚类中心不再变化的时候返回最佳的结果，在每一次迭代中，算法都要进行如下的动作：1、 对于每一个节点向量，找到距离它最近的聚类中心，归入此类。2、 重新评估每一个图心的位置，对于每一个图心，必须是簇的质心。K-means聚类算法通过局部最小化每个向量到对应图心的距离来实现聚类。同时，它处理真实数据时是非常慢的。许多情况下，真实的数据不能直接用K-means进行聚类，而要经过二次抽样筛选之后再进行聚类。Ester曾经提出了一种可以从树形数据中获得平衡的抽样数据的方法。Ng和Han曾经提出了一种可以指导概率空间对输入向量的

6、检索模拟模型。Zhang则提出了一种基于充分统计学的树形模型。可以被用来异常识别以及快速计算。然而，这种聚类器是近似的，并且要依靠许多的近似值。要注意虽然刚开始聚类的聚类中心是随便选取的，但是对于K-means算法来说，这K个聚类中心是实实在在确定了的。如果你选取了不科学的聚类中心，就有可能影响到最后的聚类结果以及算法的效率。Bradley和Fayyad讨论了通过二次抽样和平滑数据的方法来更加科学的选取聚类中心。在本文的剩余部分，我们将会用uj来表示第J个质心，用i表示距离向量i最近的聚类质心，例如说，ui表示在迭代中距离i最近的聚类质心。D表示输入的数据节点，而Di表示所有距离ui最近的节点

7、集。R为D中节点的个数，Ri为Di中节点的个数。分布数量是M，高斯协方差矩阵为=diag(*)3、 K值的估计到目前为止，我们所描述的算法是K-means聚类算法的相关步骤，K值是由用户确定的，我们现在要描述X-means算法如何确定K值，通过BIC得分的优劣，通过聚类算法我们不仅仅要得到一些比较合理的聚类中心还要得到一个合理的K值。首先，我们描述整个确定K值的过程，不要太在意算法的细节。接下来，我们推导出适用于不同统计模型的测试集。再然后，我们回到高层的算法描述，显示算法是如何利用黑名单的思想将大量的数据存储在树形的数据集中。3.1 模型检索本质上，算法的运行过程主要是先给定一个聚类个数的下

8、限，然后不停的用K-means算法进行迭代，直到达到最好的BIC得分的结果，然后返回聚类结果。迭代算法中主要包括以下动作：X-means：1、 改变参数2、 改变结构3、 如果K大于最高限定的K值则返回结果，否则回到第一步对参数的改变过程很简单，就是传统的K-means收敛的过程。第二步中改变结构式算法的核心步骤，通过将一个大的聚类一分为二，然后决定新的质心应该出现的地方，我们要通过BIC得分来决定是否对聚类进行分割。分裂观点1：第一个想法是先选择一个重心，然后再它附近再产生一个重心，然后评价是否两个重心的情况下聚类表现的更好，如果是则分割聚类，如果不是则返回上一步。这个过程需要在X-mean

9、s算法聚类的整个过程中反复出现，直到返回最佳的聚类结果，算法的时间复杂度为O(Kmax)。但是如果没有得到BIC得分的提高应该怎么办呢，我们就必须对每一个聚类中心都采取这种方式进行处理，所以每一次都需要调用一次K-means算法，也就是说我们在加一个聚类中心的时候需要运行很多次K-means，耗费了太多时间。分裂观点2：将一个完整的簇分为两个部分，第二个想法用于SPLITLOOP系统，实现高斯混合模型识别。通过一些启发式的标准来简单的分割完整簇。分割他们时要调用K-means算法并且计算分割后的成绩是否比分割之前更好，如果更好的话就返回分割之后的结果，这是一个比较大的改善，因为通过这种方法进行

10、聚类的时间复杂度只有O(Logk)。不断的改善数据结构，直到X-means算法结束，但是这种思想的问题在于：什么样的启发机制用来分割聚类呢？还有图心应该拥有多大的规模呢？是图心决定了图结构的变化吗？如果只有一个或者是两个簇需要被分割，其他都不需要的话这种算法仍然是科学的吗？我们的解决办法同时考虑了想法一和想法二的优点，同时还避免了他们的缺点，并且我们的解决办法可以在很短时间内实现。我们将通过一个例子来解释。图1展示了拥有三个图心的一个稳定的K-means聚类。每一个图心所拥有的区域边界也在图中展示出来了，对这个图的结构改进的过程如下：首先将每一个簇分为两个孩子簇（图2）。他们是被距离质心相反方

11、向的两个向量的连线分割开来的。然后对于每一个父亲簇都运行一次K=2的K-means聚类算法，两个孩子类都要与对方争夺父亲类的聚类区域。图3表示了三个簇分别的分为两个孩子类的过程。图4表示所有的簇都已经分为了两个孩子类。在这个时候，模型的测试机制会对每一对子类进行测试，测试内容包括：两个子类的建模过程是否有证据支撑？还有两个子类是否是由父类平均分配的。下一节我们会涉及如何用这样的测试集来测试K-means。根据测试出的结果，删除不符合标准的父亲类以及他们的后代，只有通过了这个过程的父亲类以及他们的孩子类才能留存下来。另外一方面，没有被现有的图心描述好到的空间将会在增加图心的过程中获得更多的关注。

12、图5显示了图4经过这种处理之后的情况。因此我们的搜索空间覆盖了所有的2k种可能的分割设置，并且每个区域的分割是由BIC得分来确定的。与上述的想法1以及想法2比较，这种思路可以使得我们自动选择我们的聚类个数的增加量时非常少还是非常多。通过实际操作我们发现，K-means聚类运行两个聚类个数的时候是对局部最小化准则最不敏感的。我们在最高限制K值下面将会不断的进行参数改善以及框架改善来得到一个更加科学的K值。3.2 BIC得分假设我们已经有了一个数据集D以及一些可供选择的模型Mj，不同的模型对应了不同的K值。我们如何才能选择最好的K值呢？我们将要用到后验概率来给模型进行打分。我们的所有模型都被K-m

13、eans算法设定。为了按照统一的标准来设定后验概率，我们使用了以下公式：在这个公式当中lj(D)表示数据针对于第j个模型的对数似然函数，并且取极大似然函数值，pj是模型Mj中的参数数量，这个也被叫做Schwarz标准。这些变化之后的极大似然函数估计要在同一个高斯假设下：节点概率为：节点的对数似然函数为对于n属于1到K中间的数值时，只关注Dn数据集中属于n个图心的点，并且插入最大似然函数的估计值。参数Pj就是就是简单的的鞥与K-1个类别的概率、M.K个累心的坐标以及方差的估计值。为了把这一个图心的公式延伸到所有图心上，我们设定节点的似然函数为节点对于所有图心的相对似然函数值，并且将R替代为所有列

14、入考虑的节点向量。我们在X-means确定最好的模型时全局的使用BIC公式，而局部的使用图心分割测试。3.3加速到目前为止，X-means可以用在之前的小型数据上，但是我们都忽略了X-means聚类算法的主要特点，那就是它可以使用在大型数据的分析当中。对K-means算法的加速：我们以一个简单的K-means算法迭代开始，任务是最终确定哪一个节点属于哪一个质心，通过这种迭代，我们可以计算出所有的质心，并且确定属于节点都是属于哪一个给定的质心，同时确定质心的确定位置。得出结果之后，我们立刻就会发现，对于一个节点数据集的质心分配与对于一个单独的节点的中心分配过程是一样的，因为我们又足够的数据量作为

15、支撑。显然，这样做可以节省很多的计算资源，所需要占用的资源往往不比证明一个点的归属问题多多少。既然kd-tree结构强加了一个分层的数据结构给数据，那么我们就可以很容易的计算它的节点的统计数据在建立他们的时候，对这些节点做一个局部的自然选择。每一个kd-tree代表一个点集。这个树形结构同样也有边界，即一个可以包括数据集中所有点的矩形。另外，这种树形结构有两个指针向量，向量表示每一个父亲节点都被分为了两个子节点。设置一个计数器来存储每一个质心拥有多少个节点，现在我们来展示这种计数器如何只扫描一遍树形结构就能够统计到所有的图心的数据。统计的过程是一个递归的过程，把每个图心所拥有的点视作参数。它的

16、任务就是更新节点计数器中点的值都到达一个适当的大小。在它递归返回之后，可能会由计数器产生新的位置信息。这个过程也包括根据之前提到的边界框将不可能拥有任何点的图心剔除出去，也就是在“黑名单”中出现的节点。这个过程的完整描述在Pelleg和Moore的论文中有体现。有一点要特别注意：在收缩了黑名单之后，这个过程要重新考虑现有节点的孩子节点。图心的计数器通过这样的方式增长。这种工作通常在较高级的树形结构中实现，但是清除工作往往在整个树形结构中实现。加速结构改善过程：这个过程就是在K-means迭代过程中改变图心位置的过程。我们现在运用同样的过程来实现结构改善的过程。之前的方法是，我们对于每一个泰森多

17、边形下的区域分为两块相同大小的区域。并首先列出父亲图心的列表，然后将其作为这个过程的输入变量。与全局迭代过程不同的地方在于当图心减少为只有一个单一图心的时候，算法所进行的动作。如果出现了这种情况，那就表明数据集中的所有的点都是可以被归纳为一个图心所包括的点。这个时候我们只要在它的孩子图心之间进行分割就可以了。为了达到这一目标，我们将这个图心分为两个孩子图心，然后评价是否应当对之前的结构进行分割。在对整个的树形结构进行扫描之后，（有可能删掉了很多的节点），子图心的计数器已经得到了一个最终的统计值，而且新的图心的位置也已经确定了，继而我们可以进行下一次迭代，直到所有的图心已经被处理完成。额外的加速

18、：在我哦们进行上述迭代的过程中，那些没有被考虑的空间区域往往为定义为活动的，那些已经被图心包括的区域被标记为静止的。我们可以将这种分析模式通过将它的先前迭代的统计状态作为缓存数据的方式来准换为一种更进一步的改进加速，考虑到两个图心的边界（这两个图心对数据集中的所有节点都有可能包括）。虽然我们必须遍历属性结构来更新我们计数器中的数值，但是我们没有理由在下一次迭代中再进行一遍这个动作，因为图心根本就没有移动过，也没有任何新加入的图心占用任何一个已经分配给图心的节点。因此我们可以记录下图心节点的数量然后进行连续迭代，而不用每次都对数据的树形结构进行一次遍历。为了能够快速比较两个图心位置的优劣，我们使

19、用一个写操作来实现：一旦数据结构不允许在数据形成之后改变图心的位置，一旦图心的位置改变了，那么一个新的元素就必须插入进来，并且这个插入的元素有特别的识别标识。这个方法仅仅在两个图心进行比较的时候会用到。显然，因为旧的图心再也不会用到了，所以也没有什么继续存储他们的必要了。这就涉及到我们要建立一个原始的M.K存储器配上一个哈希表来快速寻找响应的标签。这个想法的更进一步的扩展可以把这种存储方式利用在图心的孩子节点上。这些节点将会变为僵尸状态而不是被删除。又由于他们的标识符是不会变的，所以说缓冲区存储的数据就是最后一次迭代完成之后的数据。5、结论本文中展现了一种新型的K-means算法来选择更加科学的数据分类模型。通过适应和扩展来提高K-means，用这个算法可以免除用户用不同的K值来测试哪个结果更加科学，X-means算法只需