聚类技术优化

优化聚类，是通过对某些数值判据寻优（或者最大，或者最小），来找到对应给定数量的分组的一个分划。这种方法不同于之前提到的层次聚类方法，它不需要产生一个层级结构。不同的优化聚类方法的区别在于：1，聚类判据（数值）；2，优化算法。

数据挖掘研究院

优化聚类算法的基本思想是，对于将n个样本聚成某个给定数量分组的问题，给每个符合条件的分划赋一个指数值(index) c(n,g)，用这个值来衡量这种分划是否适当（adequacy）。一些方法需要找到指数最高的分划，另一些则需要找到值最小的分划。一些方法基于邻近度矩阵，而另一些需要使用原始的数据矩阵。下面分别介绍基于距离和基于连续数据的优化聚类算法。

由相异性（距离）矩阵衍生的聚类判据

同质性（homogeneity）和分离性（separation）可以被用来定义前面指数。我们需要最后得到的有实际意义的分类具有这样两个特点，一是组内的样本具有内聚的结构；二是组与组之间被很好的分开。基本的一些指数列在P91页的 Table5.2里，它们都利用了距离矩阵Delta中的元素delta_{ij}（表示第i个样本跟第j个样本之间的距离）。头三个公式h_1,h_2,h_3都是用来衡量第m组内部的性质，量化“同质性的缺乏”或称“异质性”（heterogeneity）。h_1是所有（平方）距离之和，h_2是所有（平方）距离中的最大者，h_3是组内单个样本点离其他点的（平方）距离之和的最小值。h_3中如果r=1，即用距离而非平方距离，则又被成为星指数，那个用来代表组的拥有离其他点距离和最小的样本，称为 `medoid′。接下来的两个公式跟组间的分离性质有关，i_1是组内所有样本跟组 外所有样本的（平方）距离的总和，而i_2是这些距离中的最小值。当选定一个指数之后，整个分划的聚类评价就能定义为所有组的指数的总和： 数据挖掘实验室

c_1(n,g)=sum_{m=1}^g h(m)
 数据挖掘实验室 

或

c_2(n,g)=max_{m=1,...,g} h(m)
 
数据挖掘研究院
 

或

c_3(n,g)=min_{m=1,...,g} h(m)
 数据挖掘实验室 

当我们要评价组内异质性的时候，我们需要最大化c值，反之考虑分离性时则需要最小化c值。当c_1使用于h_1时，由于这个值会跟组内的成员数相关，所以需要作一下修正：

c_1^{*}(n,g)=sum_{m=1}^g frac{h_1(m)}{n_m}
 
数据挖掘研究院
 

最后，这些聚类判据存在关联性，比如对sum_{m=1}^{g}h_1(m)求最小相当于对 sum_{m=1}^{g}i_1{m}求最大。有时候可以将几个判据组合起来对分划作出评价。

 

数据挖掘研究院

从连续数据衍生的聚类判据

出发点是原始的n*p的数据矩阵X，对于连续数据我们使用一个p*p的离差矩阵T: 数据挖掘研究院

T = sum_{m=1}^{g} sum_{l=1}^{n_m}(x_{ml}-ar{x})(x_{ml}-ar{x})^{′}
 数据挖掘研究院 

这里，x_{ml}是组m中第l个观测点的p维数据向量，ar{x}是所有这种数据向量的样本均值。T可以分解为组内的离散矩阵W和组间的离散矩阵 B：

W = sum_{m=1}^{g} sum_{l=1}^{n_m}(x_{ml}-ar{x}_m)(x_{ml}-ar{x}_m)^{′}
 数据挖掘实验室 

B = sum_{m=1}^{g} n_m(ar{x}_m-ar{x})(ar{x}_m-ar{x})^{′}
 数据挖掘研究院 

其中ar{x}_m是组m内的样本平均向量。它们之间的关系是T=W+B。对于单变量的情况p=1，T，W，B成为平方和，我们只要选择拥有最小W值，或最大B值的划分即可。

 

数据挖掘研究院

最小化 race(W)

多变量的情况下，上面那些矩阵就很难说明问题了，为了实用性需要作一些变化。比如用 race(W)来衡量。这相当于找组内的点到组内平均向量的欧式距离的总和的最小值：

E = sum_{m=1}^{g} sum_{l=1}^{n_m}
(x_{ml}-ar{x}_m)^{′}(x_{ml}-ar{x}_m)= sum_{m=1}^{g} sum_{l=1}^{n_m}d^2_{ml,m}
 数据挖掘研究院 

其中d_{ml,m}是第m组第l个样本到第m组的平均向量的欧式距离。用距离矩阵中 的元素表示则成为：

E =
sum_{m=1}^{g}frac{1}{2n_m}sum_{l=1}^{n_m}sum_{v=1,v≠l}^{n_m}d^2_{ml,mv}
 
数据挖掘研究院
 

这里的d_{ml,mv}是第m组中第l和第v个样本之间的距离，因此，最小化 race{W}相当于最小化前面提到的c^{*}_1异质性判据（r=2 for h_1）。

  数据挖掘研究院

最小化det(W)

这基于完整的离差矩阵T和组内离差矩阵W的行列式之比值，当det(T)/det(W) 很大时，说明组内的平均向量差异大。由于对于将n个样本分到g组里这种情况， T是保持不变的，所以这相当于最小化det(W)

最大化 ract(BW^{-1})

也即寻找组间离差矩阵与组内离差矩阵的逆矩阵的乘积的迹的最大值。这个值越大那么组内平均向量的差别就越大。 数据挖掘研究院

聚类判据的性质

前面提到的三个判据中第一个，也即最小化W的迹的方法最为常见，但是它有不少问题。首先，它是比例相关的，在给数据加上权重，或者标准化之后，聚类的结果会变得不同；其次，它会产生不必要的球形的组结构。另外两个判据是跟比例无关的。 数据挖掘研究院

最小化W的行列式值的判据避免了上面的两个问题，但是det(W)和 race(W)都有倾向于产生相等大小（样本数量）的分组，而且当det(W)给椭圆形结构的数据聚类时，会产生形状差不多的分组，有时会带来问题。

数据挖掘研究院

给拥有不同形状和大小的分类结构的可选判据

为了解决det(W)方法倾向于形成相同形状的分组的问题，有人提出了这个判据，最小化：

prod_{m=1}^g[det(W_m)]^{n_m}
 
数据挖掘研究院
 

其中，W_m是第m组的组内离差矩阵:

W_m = sum_{l=1}^{n_m}(x_{ml}-ar{x}_m)(x_{ml}-ar{x}_m)^{′}
 
数据挖掘研究院
 

这个方法需要每个组都包含p+1个样本点，否则这个组的W_m的行列式值可能为零。另外可选的判据是，最小化：

sum^{g}_{m=1}(n_m-1)[det(W_m)]^{1/p}
 数据挖掘研究院 

为了解决 race(W)和det(W)倾向于产生相同大小的分类的问题，提出的判据包括最小化：

prod_{m-1}^{g}[det(W/n_m^2)]^{n_m}
 数据挖掘研究院 

和

prod_{m=1}^{g}[det(W_m/n_m^2)]^{n_m}
 数据挖掘研究院 

需要注意，大部分聚类判据是启发式的（heuristic），也就是是说，聚类过程相当于使用了一种潜在的统计学模型，而最优化是在最大化这个模型的可能性。因此，最好对于特定的情况，设计特定的统计学模型，并对应设计聚类的判据。

 

数据挖掘研究院

以上的讨论限于连续数据的情况，如果变量是分类变量，那么需要使用第三章的办法产生一个相异矩阵，然后在它上面应用聚类判据。或者把这个相异矩阵转换到欧几里得空间，然后再进行聚类。 数据挖掘研究院

优化算法

当确定聚类判据后，接下来要做的是如何找到一个分划使判据达到最优化。穷举所有可能的分划是不明智的，因为将n个数据划分到g组里的不同分划有：

N(n,g) = frac{1}{g!}sum_{m=1}^{g}(-1)^{g-m}{g choose m}m^n
 
数据挖掘研究院
 

种之多。对于某些判据来说，不需要穷举所有的分划，对于其他的判据，可以使用诸如动态规划的方法提升速度，但是总的来说，全局的去寻找符合条件的分划是不实际的。

 

数据挖掘研究院

于是人们发展了瞎子爬山法(hill-climbing)，对现有分划进行重组，如果新分划比原分划更好，才保留。具体步骤是：

数据挖掘实验室

1. 找一个初始分划，将n个样本分到g组中。
2. 将每个样本从自己的组移到其他组里（即重组，一次移动一个），再计算聚类判据的变化。
3. 保留可以最好的优化聚类判据的新分划。
4. 重复前两步，直到移动任何一个样本都无法改善聚类判据。

  数据挖掘实验室

初始分划的选择非常重要，不同的初始分划将极有可能带来不同的局部最优解。选择初始分划，可以：1，通过先验知识；2，由其他聚类方法中得来；3，随机选择；4，将样本在欧几里得空间中表示，以某种方式选择g个点作为聚类中心。建议选择不同的初始分划多做几次优化聚类。 数据挖掘研究院

最早的爬山法算法之一是k-means法。它相当于对 race(W)进行优化，每一步，计算每个样本离各组的均值向量的距离，然后把他们移至距离最近的那个组中。算法实现时不一定符合前面说的4步，比如对于k-means来说，可能在每一步同时移动多个或一个样本，移动一个样本时可能按照某种系统顺序（比如给样本编的号码）或者按随机顺序，样本可能被丢到最近的组或者丢到可以给聚类判据带来最大改善的组，组的平均向量可以在移动一个样本后即重新计算，也可以在移动某个固定数量样本后重新计算，另外还有在两组间成对交换样本的方法。如前所述， race(W)方法是比例相关的，为了解决这个问题，我们可以通过每步都是用Mahalanobis距离来计算使得k-means成为适应性过程（adaptive procedure）。

其他的在爬山法上改良的优化算法像：

• 允许分组的数量改变，或将一定数量非典型数据放在一个例外的组中，不把它们包括在聚类判据的计算中。
• 模拟退火法，允许一定几率下，保留使聚类判据恶化的结果。这个方法可以在一定程度上使计算逃离局部最优的陷阱。

但由于这些方法中，都需要设定一些内部参数，像模拟退火中的“几率”，所以实用中不如k-means类型的方法受欢迎。

 

其他优化算法待考。 数据挖掘研究院

选择分组数目

在大部分聚类研究中，我们需要“估计”数据可以分为多少组。这种估计可以是非正式的，比如把不同分组数量下优化出的聚类判据值作图，在变化最大的位置确定分组数量。这样的做法多少有些主观，所以出现一些更正式(formal)的方法. 数据挖掘实验室

更正式的方法很多，这里举几个评价比较高的。 数据挖掘研究院

• Calinski and Harabasz的C(g)，选择使C最大的g：

  C(g) = frac{	race(B)}{g-1}/frac{trace(W)}{n-g}
   
  数据挖掘研究院
   

  由于它需要完成聚类过程后得到的B和Ｗ，所以这个方法跟选定的聚类方法及其实现相关。
• Duda and Hart的L(m)，这个评价用于对一个聚类完成的组m，比较组内的距离质心的平方距离和，于将该组分成两块之后的距各自质心平方距离和：

  L(m) = left{1-frac{J^2_2}{J_1^2}-frac{2}{pi
  p}
  ight}left{frac{n_m p}{2[1-8/(pi^2 p)]}^{1/2}
   数据挖掘研究院 

  如果L(m)超过一个值（来自正则分布），则该组m同质性的无意假设被驳回，该组需要被细分。这个方法可以发展至全局，比如选择每个组的同质性假设都成立的分划g。
• Beale的F test。定义S^2_g为到类质心的方差和。对n个样本的分划g_2优于另一个分划g_2，如果：

  F(g_1,g_2) = frac{(S^2_{g_1}-S^2_{g_2})/S^2_{g_2}}{[(n-g_1)/(n-g_2)](g_2/g_1)^{2/p}-1}
   数据挖掘研究院 

  超出p(g_2-g_1)和p(n-g2)自由度的F分布中得到的某个值。
• Marriott使用最小化det(W)作为聚类判据时，选择g使得g^2det(W)最小，当数据成单峰分布时，g很可能为1，对于有很强的类结构的数据，将很有可能得到正确的分组数目。另外，g^2det(W)/det(T)可以给聚类结构提供证据，这个值在聚类程度变高时（g变大的时候么？）变小。特别的，如果对一个类的所有可能的分类都使得g^2det(W)/det(T)比之前要大，那么这些样本应该合为一组而不被细分。
• 对于分类数据，可以使用在层级聚类中提到的Goodman和Kruskal的gamma 统计。利用邻近度矩阵，比较每一对组内距离和组间距离。在这里，定义一对距离是协和的(concordant),如果组内邻近度严格小于组间邻近度，反之称为不协和的(discordant)。定义协和指数(concordance index)为：

  I(g) = frac{S_{+}-S_{-}}{S_{+}+S_{-}} in [-1,1]
   
  数据挖掘研究院
   

  其中，S_{+}和S_{-}为协和和不谐和的距离对的数量。选择使I(g)最大的g值 。
• Silhouette plot是一种基于距离矩阵的图示方法。对于每一个样本i，定义指数 s(i)in[-1,1]来衡量b(i),a(i)之间的标准差，其中a(i)是样本到同组样本的平均距离，而b(i)是样本到最近的组中所有样本的平均距离。如果s(i)接近1，那么样本i离自己的组比离其他邻近的组近，所以是分类良好的(well classified) ，反之如果接近-1，则是被错分的(misclassified)，但如果在0附近则难以判断是否分类正确。画图（plot）的时候，一般是将s(i)用水平条表示，并按照各个样本在组内的s(i)从高到底竖直排列。这样有助于找出那些分类不佳的样本。对于不同的分组，可以作不同的Silhouette plot，并比较它们的平均 (average)silhouette width，当然是越大越好。Kaufman 和Rousseeuw认为，超过0.5的silhouette width就是好的分类结果，0.2以下是缺少实质聚类结构的。

最后要说的是，建议使用不止一个规则来选择分组数量。而且，就像聚类判据那样，一些规则假定了一些聚类结构，所以只在这样的结构满足时表现良好。比如 Beale的规则只在聚类成清晰的球形结构时适用。

  数据挖掘研究院

在所有这些建议的优化聚类中，有两个比较流行：最小化 race(W)和最小化 det(W)。因为k-means法在很多软件包里都能找到所以更常见。但是后者比前者更有优势，比如比例无关性，而且它并未对聚类结构有预先的假定。 数据挖掘研究院