• 项目

到 2015 2015年 8 月

30 卷数 8

测试运行-K-手段 + + 数据聚类

由 James McCaffrey

James McCaffrey数据聚类是数据分组，以便类似项目被放置在一起的过程。一旦组合在一起，可以检查数据的集群以看看是否有可能有用的关系。举个例子，如果聚集了一大堆的销售数据，每个群集中的数据信息可能会泄露可用于有针对性的营销的模式。

有几种聚类算法。一个最常见的称为 k-均值算法。有几个变体这种算法。这篇文章解释了相对近期的变化称为 k-手段 + + 算法。

看一看在演示程序图 1。在程序启动与 20 的数据项目，每个组成的以英寸为单位的一个人的身高和体重的磅。接下来，将聚类数设置为 3。在大多数数据聚类分析方案中，必须由用户指定的分类数。

K-手段 + + 聚类在行动
图 1 K-手段 + + 聚类在行动

该演示程序然后对数据分类，使用 k-手段 + + 算法。每 20 数据项被分配给一个分类 id 为 0、 1 或 2。群集分配存储在一个数组，其中数组索引对应于数据索引，数组值是相关联的聚类 id。例如，最终演示数据聚类分析是：

0 2 1 1 2 . . . 1

这表明数据项目 0 (高度 = 65.0，重量 = 220.0) 是分配群集 0，数据项目 1 分配给群集 2，数据项目 2 被分配群集 1，等等。演示结束通过显示分组由群集的数据。在这里，揭示了一个非常清晰的模式。有八人中等身材和重的特点，与短的高度和重量轻、 七人和高度与中等重量的五人。

这篇文章假设你有至少中级编程技能，但不承担你知道任何关于 k-手段 + + 算法。演示程序使用 C# 编写，但你不应该有太大困难到另一种语言，如 Python 或 JavaScript 代码进行重构。演示代码太长，无法显示其全部内容，但完整的源代码是本文附带的代码下载中提供。

理解了 K-手段 + + 算法

K-手段 + + 算法是一种变体的标准 k-均值算法，所以为了了解 k-手段 + + 你必须首先了解定期的 k-均值。K-均值算法有有趣的历史，和有时被称为劳合社的算法。K-均值"k"是指团簇数目。在层次非常高的伪代码中，最常见的标准 k-均值是看似简单的:

pick k initial means
loop until no change
  assign each data item to closest mean
  compute new means based on new clusters
end loop

尽管它简单的外观，标准 k-均值算法是，事实上，很微妙的和执行是出奇的复杂。假定数据可以加入群集包含 20 的数据项中所示的 图 1, ，具有 k 将设置为 3。第一步是选择三个数据项使其作为初始的方式。常用的方法是随机选择的数据项目。假设三个随机选定数据项目是项目 2 (59.0，110.0) 群集 0，1，群集的平均数 4 (75.0，150.0) 项目和项目 6 (68.0，230.0) 第二组的平均数的平均数。

在主要处理循环中，每个数据项是审查和分配给群集与最接近的意思。所以，数据项目 0 (65.0，220.0) 会被分配到群集 2 因为项目 0 接近 (68.0，230.0) 比其他两个手段。每个剩余 19 数据项目将分配给群集。请注意，最初被选为手段的数据项会分配到正确的群集，因为距离将是 0。

每个数据项目分配到集群之一后，计算一个新的意思，为每个群集。假设该群集 0 目前包含只是三个数据项: (59.0, 110.0), (70.0, 210.0), (61.0, 130.0).将新的均值为此群集:

( (59 + 70 + 61)/3, (110 + 210 + 130)/3 ) =
(190/3, 450/3) =
(63.3, 150.0)

将同样的计算集群 1 和 2 的新手段。通知新的手段并不一定实际数据项目之一了。从技术上讲，每一个新的手段是"质"，但是"中庸"一词常用。

后计算新的手段，每个数据项是再次检查与分配给群集与最接近的新意思。迭代的更新群集，更新意味着过程持续进行直到群集分配没有变化。

这一切听起来相对简单，但很多可以去错与标准 k-均值算法的一个简单实现。尤其是，坏选型的最初手段可以到稳定，或两者都导致极差数据聚类分析，或一个很长的运行时。事实证明，良好的初步手段是那些不会互相靠近。K-手段 + + 算法选择初始意味着不接近对方，然后使用标准的 k-均值算法的聚类。

K-手段 + + 初始化机制

在高级别伪代码 k-手段 + + 初始化机制选择意味着:

select one data item at random as first mean
loop k-1 times
  compute distance from each item to closest mean
  select an item that has large distance-squared
    as next initial mean
end loop

再次，伪代码非常简单。K-手段 + + 初始化机制所示图 2。有九个数据点，每个都有两个组件。团簇数目设置为 3，因此 3 数据项必须选择作为初始的手段。

K-手段 + + 初始化机制
图 2 K-手段 + + 初始化机制

在图图 2 显示 k-手段 + + 初始化过程后两个三个的初步手段已选定。首字母的意思是在 (3，6) 随机选定。计算距离平方从每个其他 8 个数据项目到第一的意思，然后使用该信息，第二个初始的意思是在 (4，3) (在我很快解释的方式) 被选中。

要选择一个数据项目作为第三个初始平均，计算了从每个数据点到其最接近平均值的平方的距离。距离显示为虚线。使用这些距离平方的值，选择第三个意思数据项与小距离平方的值已被选中，低概率和数据项目与大距离平方的值已经被选中的可能性很大。这种技术有时被称为比例健身选择。

比例的健身选择是 k 的心-手段 + + 初始化机制。有几种方法来执行比例健身选择。该演示程序使用一种叫做轮盘赌选择技术。在高级别的伪代码中，轮盘赌选择的一种形式是:

p = random value between 0.0 and 1.0
create an array of cumulative probabilities
loop each cell of cum prob array
  if cum[i] >= p
    return i
  end if
end loop

一个具体的例子将帮助澄清轮盘赌选择。关联的值 (30.0、 10.0、 40.0 20.0) 假设有四个候选项目 (0、 1、 2、 3)。值的总和是 20.0 + 40.0 + 10.0 + 30.0 = 100.0。比例的健身选择将选择项目 0 与概率 20.0/100.0 = 0.20; 选择项目 1 与概率 10.0/100.0 = 0.10; 选择项目 2 与概率 40.0/100.0 = 0.40; 和选择项目 3 与概率 30.0/100.0 = 0.30。

如果选择的概率都作为 (0.20，0.10，0.40，0.30) 存储在一个数组中，累积概率可以存储在一个数组值 (0.20、 0.30、 0.70、 1.00)。现在，假设使用值 0.83 生成一个随机的 p。如果 i 到累计概率的数组的数组索引时我 cum = 0 时，[i] = 0.20，不大于 p = 0.83，因此我需要增加到 1。现在变为 cum [i] = 0.30，仍不大于 p，因此 i 递增为 2。现在 cum [i] = 0.70，这是仍不大于 p，因此我需要增加到 3。现在 cum [i] = 1.00，大于 p，因此我 = 3 返回与所选的项目。

通知的累积概率之间的距离不同，与对应于这些项目与更高的概率的选择的差异较大。

综上所述，k-手段 + + 算法选择的初步手段，那么方法不一样，然后使用标准的 k-均值算法对群集数据。初始化过程使用比例的健身选择，可以采用多种方式实现。演示项目用途轮盘赌轮选择。

程序的整体结构

演示程序，与一些少量的编辑，以节省空间，整体结构在图 3。若要创建该演示程序，我发起了 Visual Studio，创建一个新 C# 控制台应用程序项目命名为 KMeansPlus。演示程序有没有重大的 Microsoft.NET 框架依赖关系，因此，任何较新版本的 Visual Studio 将工作。

图 3 程序的整体结构

using System;
using System.Collections.Generic;
namespace KMeansPlus
{
  class KMeansPlusProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin k-means++ demo");
      // All program code here
      Console.WriteLine("End k-means++ demo");
      Console.ReadLine();
    }
    public static int[] Cluster(double[][] rawData,
      int numClusters, int seed) { . . }
    public static double[][] InitMeans(int numClusters,
      double[][] data, int seed) { . . }
    private static double[][] Normalized(double[][] rawData) { . . }
    private static double[][] MakeMatrix(int rows, int cols) { . . }
    private static bool UpdateMeans(double[][] data,
      int[] clustering, double[][] means) { . . }
    private static bool UpdateClustering(double[][] data,
      int[] clustering, double[][] means) { . . }
    private static double Distance(double[] tuple,
      double[] mean) { . . }
    private static int MinIndex(double[] distances) { . . }
    static void ShowData(double[][] data, int decimals,
      bool indices, bool newLine) { . . }
    static void ShowVector(int[] vector, bool newLine) { . . }
    static void ShowClustered(double[][] data, int[] clustering,
      int numClusters, int decimals)
  }
} // ns

后加载到该模板代码编辑器中的，在我在 Program.cs，文件右击解决方案资源管理器窗口中改名为更具描述性的 KMeansPlusProgram.cs 和允许 Visual Studio 自动重命名类程序。在编辑器窗口顶部的模板生成的代码，我删除了所有对除了顶级的 System 命名空间和 Collections.Generic 命名空间的命名空间的引用。

Main 方法开始通过设置 20 个原始数据的项目:

double[][] rawData = new double[20][];
rawData[0] = new double[] { 65.0, 220.0 };
...
rawData[19] = new double[] { 61.0, 130.0 };

在非演示场景中可能会从一个文本文件或 SQL 数据库中读取数据。显示原始数据使用一个名为 ShowData 的程序定义的帮助器方法后, 数据被群集:

int numClusters = 3;
int[] clustering = Cluster(rawData,   numClusters, 0);

虽然有一些技巧，你可以用猜的最佳分类数，在一般情况下，您必须使用试验和错误。聚类方法接受数字原始数据到群集中的数组的数组样式矩阵; 集群使用数目 (可"k"，但"numClusters"的可读性更好); 和用于随机的种子值。

Main 方法最后显示聚类数组和显示分组由群集的原始数据:

ShowVector(clustering, true);
ShowClustered(rawData, clustering, numClusters, 1);

我使用静态方法，而不是面向对象的方法。聚类方法调用四个帮助器方法。帮助器方法规范化接受原始数据矩阵，并返回数据规范化，所有值都差不多都是同一数量级 (通常与-6.0 + 6.0) 的矩阵。方法 InitMeans 实现 k-手段 + + 初始化机制。方法 UpdateClustering 和 UpdateMeans 实现了标准的 k 平均值算法的核心部分。

方法 InitMeans 和 UpdateClustering 都调用帮助器方法返回两个数据的各项之间的欧氏距离的距离。例如，如果一个数据元组是 3.0，9.0 (5.0) 和第二个元组是 2.0，6.0 (1.0)，这两个项目之间的欧氏距离是:

Sqrt( (3-2)^2 + (9-6)^2 + (5-1)^2) ) =
Sqrt( 1 + 9 + 16 ) =
Sqrt(26) = 5.1

可以使用其他的距离定义。一般来说，k-均值和 k-手段 + + 用于群集严格数值数据，而不是分类数据。

执行 K-手段 + +

提出了聚类方法的代码图 4。聚类方法首先对原始数据进行规范化处理，以使数据项 (如重量值在演示中) 中的大型组件不会左右更小的组件 (高度值)。演示使用高斯正常化。两个常见的替代方法是最小最大规范化和数量级正常化。原始数据的规范化的设计替代是在预处理步骤中，然后将传递的归一化的数据直接到群集的方法。

图 4 方法群集

public static int[] Cluster(double[][] rawData,
 int numClusters, int seed)
{
  double[][] data = Normalized(rawData);
  bool changed = true;
  bool success = true;
  double[][] means = InitMeans(numClusters, data, seed);
  int[] clustering = new int[data.Length];
  int maxCount = data.Length * 10;
  int ct = 0;
  while (changed == true && success == true &&
    ct < maxCount)
  {
    changed = UpdateClustering(data, clustering, means);
    success = UpdateMeans(data, clustering, means);
    ++ct;
  }
  return clustering;
}

方法 InitMeans 实现 k-手段 + + 初始化机制并返回一组意味着是相距很远的欧氏距离。在主要的聚类循环中，UpdateClustering 方法遍历每个数据项和将每个项目分配给群集最接近当前的手段/质心与相关联。该方法返回 false，如果群集分配 (表明聚类完整) 没有变化或者新的聚类将导致在没有数据的项 (表示有什么不对劲) 的群集中。替代方法是在零计数群集情况时引发异常。

方法 UpdateMeans 循环访问分配给每个群集的数据，并计算新意思/质心为每个群集。该方法返回 false，如果不能计算一个或更多的手段，因为群集有没有数据的项目。

主聚类循环使用一个计数检查以防止无限循环。K-均值算法通常稳定速度非常快，但该算法将稳定根本没有保证。MaxCount 的值设置为 10 倍的数据项的数目，是任意的但我工作得很好在实践中。

InitMeans 方法的定义的开头:

public static double[][] InitMeans(int numClusters,
  double[][] data, int seed)
{
  double[][] means = MakeMatrix(numClusters, data[0].Length);
  List<int> used = new List<int>();
...

名为手段的局部数组的数组样式矩阵保存的方法返回的行索引群集 ID，每一行都是一个数组，它保存的组件相关联的意思。列表 < int > 名为用作保留索引已分配的数据项目的初始意味着，这样可以防止重复的初始方法。这种方法假定没有数据的项目具有相同的值。当聚类，你如何处理重复数据项目取决于您的特定问题情况。对源数据中删除重复项的一种替代方法是重量重复的项目，可以通过它们的频率。

接下来，第一次初始平均是选择和存储:

Random rnd = new Random(seed);
int idx = rnd.Next(0, data.Length);
Array.Copy(data[idx], means[0], data[idx].Length);
used.Add(idx);

第一次初始均值是随机选择，从数据的所有项目。初始的手段现有数据项目和他们有时被称为中心点。

下一步，为循环构造选择剩下的 k-1 意味着:

for (int k = 1; k < numClusters; ++k)
{
  double[] dSquared = new double[data.Length];
  int newMean = -1;
...

阵列绑带认为每个数据项和最接近的现有初始平均值之间平方的距离。变量 newMean 认为将是下一个初始平均数据项的索引。接下来，检查 (标准化) 的每个数据项和它的绑带值是计算和存储:

for (int i = 0; i < data.Length; ++i)
{
  if (used.Contains(i) == true) continue;
  double[] distances = new double[k];
  for (int j = 0; j < k; ++j)
    distances[j] = Distance(data[i], means[k]);
  int m = MinIndex(distances);
  dSquared[i] = distances[m] * distances[m];
}

检查以确定是否已使用数据项作为初始平均值不东西真的有必要的这是因为如果已使用了项，平方秘密的平均值的距离将是到其自身，距离该是 0。名为距离列阵储存数据的当前数据项到每个到目前为止已选择的现有 k 初始方法之间的欧几里得距离。

记得在距离法的欧氏距离需要平方根的平方差之和数据项目组件的总和。因为 k-手段 + + 中使用平方的距离、 InitMeans 现蕾后撤消在距离平方根操作。因此，您可以通过定义直接返回距离平方的方法来简化代码。

接下来，循环扫描通过轮盘赌选择的累积概率被编写:

double p = rnd.NextDouble();
double sum = 0.0;
for (int i = 0; i < dSquared.Length; ++i)
  sum += dSquared[i];
double cumulative = 0.0;
int ii = 0;
int sanity = 0;

生成一个介于 0.0 和 1.0 之间的随机值与距离的平方和计算描述成比例的健身选择节中所述。而不是显式创建的累积概率数组，它是更有效地生成当前的累积概率上飞。

每个累积概率计算并在一段时间检查循环实现轮盘轮选择:

while (sanity < data.Length * 2)
{
  cumulative += dSquared[ii] / sum;
  if (cumulative >= p && used.Contains(ii) == false)
  {
    newMean = ii; // the chosen index
    used.Add(newMean); // don't pick again
    break;
  }
  ++ii; // next candidate
  if (ii >= dSquared.Length) ii = 0; // past the end
  ++sanity;
}

While 循环进展直到累积概率值是大于或等于随机 p 值。但是，不能允许重复的初始意味着，因此如果所选的平均值是"已使用的"列表 < int > 中，选择下一个可用的数据项目。如果 ii 索引运行的数据结束时，会将其重置为 0。请注意是否尚未为初始平均值选择数据项下, 一个可用的数据项目将可能并不是下一步最可能的产品。

方法 InitMeans 得出结论通过保存选定的初始平均，并返回数组的选定的手段:

...
    Array.Copy(data[newMean], means[k], data[newMean].Length);
  } // k, each remaining mean
  return means;
} // InitMean

InitMeans 方法的目的是寻求 k 不同数据项要用作初始的手段。轮盘赌选择并不能保证选择的手段最大限度地有别于彼此，和有选择的手段可能相当接近彼此的机会很小。因此，您可能想要重构方法 InitMeans，轮盘赌选择被多次使用，生成候选集的手段，，然后返回包含的意思是彼此最不同的集合。

总结

这篇文章基于 2007年研究论文中，"K-手段 + +: 优点小心种子设定"由 D.Arthur 和 S.Vassilvitskii。通常是研究论文这种情况，如几乎会不提供任何实现细节。然而，仔细阐述了如何 k-手段 + + 初始化工作和建立其行为的理论边界。

Dr.James McCaffrey 供职于华盛顿地区雷蒙德市中的 Microsoft Research他参与过多个 Microsoft 产品的工作，包括 Internet Explorer 和 Bing。Scripto可以在达到 McCaffrey jammc@microsoft.com。

感谢以下的微软研究院技术专家对本文的审阅: Kirk Olynyk