7.2　第一个例子：k-means聚类算法

7.2　第一个例子：k-means聚类算法

k-means聚类算法将预先未分类的项集分组到预定的K个簇。它在数据挖掘和机器学习领域非常流行，并且在这些领域中用于以无监督方式组织和分类数据。

每一项通常都由一个特征（或者说属性）向量（这里使用向量是作为一个数学概念而非数据结构）定义。所有项都有相同数目的属性。每个簇也由一个含有同样属性数目的向量定义，这些属性描述了所有可分类到该簇的项。该向量叫作centroid。例如，如果这些项是用数值型向量定义的，那么簇就定义为划分到该簇的各项的平均值。

该算法基本上可以分为四个步骤。

初始化：在第一步中，要创建最初代表K个簇的向量，通常，你可以随机初始化这些向量。
指派：然后，你可以将每一项划分到一个簇中。为了选择该簇，可以计算项和每个簇之间的距离。可以使用欧氏距离作为距离度量方式，计算代表项的向量和代表簇的向量之间的距离。之后，你可以将该项分配到与其距离最短的簇中。
更新：一旦对所有项进行分类之后，必须重新计算定义每个簇的向量。如前所述，通常要计算划分到该簇所有项的向量的平均值。
结束：最后，检查是否有些项改变了为其指派的簇。如果存在变化，需要再次转入指派步骤。否则算法结束，所有项都已分类完毕。

该算法有如下两个主要局限。

如前所述，如果随机初始化最初的簇向量，那么对同一项集执行两次分类的结果是不同的。
簇的数目是预先定义好的。从分类的视角来看，如果属性选择得不好将会导致糟糕的结果。

尽管如此，在对不同类型的项做聚类分析时该算法仍然广受欢迎。为了测试我们的算法，需要实现一个应用程序来对某个文档集进行聚类。就文档集而言，第5章已经介绍了有关电影信息的维基百科网页集，本章使用的是该网页集的缩减版，仅从中选取了1000个文档。为了表示每个文档，必须使用向量空间模型表示。在这种表示方法中，每个文档都可以用数值型向量表示，向量的每个维度都代表一个单词或者一个术语，而向量的取值则是一个指标，它定义了该单词或术语在该文档中的重要程度。

使用向量空间模型表示一个文档集时，向量维度的数量和整个文档集中不同单词的数量相同，这样向量中就会有大量为0的值，因为每个文档都不会包含所有单词。你可以使用一种在内存中更优的表示方式来避免表示所有的0值，从而节省内存并提升应用程序的性能。

在我们的例子中，选择了术语频次-逆文档频次（TF-IDF）作为定义每个单词重要性的指标，而且将具有最高TF-IDF值的50个词作为代表每个文档的术语。

我们使用两个文件：movies.words文件和movie.data文件。movies.words文件中存放了向量中用到的所有单词，movie.data中存放了每个文档的表示。movies.data文件的格式如下。

10000202,rabona:23.039285705435507,1979:8.09314752937111,argentina:7.953798
614698405,la:5.440565539075689,argentine:4.058577338363469,editor:3.0401515
284855267,spanish:2.9692083275217134,image_size:1.3701158713905104,narrator
:1.1799670194306195,budget:0.286193223652206,starring:0.25519156764102785,c
ast:0.2540127604060545,writer:0.23904044207902764,distributor:0.20430284744
786784,cinematography:0.182583823735518,music:0.1675671228903468,caption:0.
14545085918028047,runtime:0.127767002869991,country:0.12493801913495534,pro
ducer:0.12321749670640451,director:0.11592975672109682,links:0.079255823038
12376,image:0.07786973207561361,external:0.07764427108746134,released:0.074
47174080087617,name:0.07214163435745059,infobox:0.06151153983466272,film:0.
035415118094854446

其中，10000202是文档的标识符，而文件其余的部分都按照“单词：tfxidf值”的格式排列。

与其他例子一样，我们将实现串行版和并发版，并且执行两个版本以验证Fork/Join框架为该算法带来的性能提升。

7.2.1　公共类

串行版和并发版有一些共同特征，如下所示。

VocabularyLoader类：这个类用于加载文档集中构成词汇表的单词列表。
Word类、Document类和DocumentLoader类：这三个类用于加载有关文档的信息。在串行版和并行版算法中，这些类几乎没有差别。
DistanceMeasure类：该类用于计算两个向量之间的欧氏距离。
DocumentCluster类：该类用于存储有关簇的信息。

下面详细说明一下这些类。

VocabularyLoader类

如前所述，数据存放在两个文件中。其中一个是movies.words文件。该文件存放的列表含有文档中用到的所有词。VocabularyLoader类会将该文件转换成HashMap。该HashMap的键是整个单词，而其值为一个代表单词在列表中索引位置的整数值。我们使用该索引来判定单词在表示文档的向量空间模型中的位置。

该类只有一个方法，即load()，该方法接收文件路径为参数，并且返回该HashMap。

public class VocabularyLoader {
  public static Map<String, Integer> load (Path path) throws
                                              IOException {
    int index=0;
    HashMap<String, Integer> vocIndex=new HashMap<String,
                                               Integer>();
    try(BufferedReader reader = Files.newBufferedReader(path)){
      String line = null;
      while ((line = reader.readLine()) != null) {
        vocIndex.put(line,index );
        index++;
      }
    }
    return vocIndex;
  }
}

Word类、Document类和DocumentLoader类

这些类存储了将在算法中用到的文档的所有信息。首先，Word类存放了一个文档中某个单词的信息，这包括该单词的索引及其在文档中的TF-IDF值。该类仅包括这些属性（分别是int型和double型），并且实现了Comparable接口来根据两个单词的TF-IDF值对它们进行排序。这里不再介绍该类的源代码。

Document类存放了有关文档的所有信息。首先，该类有一个存放文档中单词的Word对象数组，它是向量空间模型的表示形式。为了节省内存空间，我们仅存储文档中用到的单词。然后，该类还有一个String变量，用于表示存放文档的文件名。最后，该类还有一个DocumentCluster对象，用于表示与该文档相关的簇。该类还包括一个构造函数，用于初始化这些属性和方法以获取和设置其取值。我们仅给出setCluster()方法的代码。在本例中，该方法将返回一个布尔值，这个值表明属性的新值是与旧值相同，还是一个新值。我们将用该值判定是否应该停止算法。

public boolean setCluster(DocumentCluster cluster) {
  if (this.cluster == cluster) {
    return false;
  } else {
    this.cluster = cluster;
    return true;
  }
}

最后，DocumentLoader类用于加载有关文档的信息。它含有一个静态方法load()，该方法接收文件路径和存放词汇表的HashMap作为参数，返回一个Document对象的数组。该方法逐行加载文件，并且将每一行都转换成为一个Document对象。代码如下：

public static Document[] load(Path path, Map<String, Integer>
                               vocIndex) throws IOException{
  List<Document> list = new ArrayList<Document>();
  try(BufferedReader reader = Files.newBufferedReader(path)) {
    String line = null;
    while ((line = reader.readLine()) != null) {
      Document item = processItem(line, vocIndex);
      list.add(item);
    }
  }
  Document[] ret = new Document[list.size()];
  return list.toArray(ret);
}

为了将文本文件的某一行转换成一个Document对象，可以使用processItem()方法。

private static Document processItem(String line,Map<String,
                                    Integer> vocIndex) {
  String[] tokens = line.split(",");
  int size = tokens.length - 1;
  Document document = new Document(tokens[0], size);
  Word[] data = document.getData();
  for (int i = 1; i < tokens.length; i++) {
    String[] wordInfo = tokens[i].split(":");
    Word word = new Word();
    word.setIndex(vocIndex.get(wordInfo[0]));
    word.setTfidf(Double.parseDouble(wordInfo[1]));
    data[i - 1] = word;
  }
  Arrays.sort(data);
  return document;
}

如前所述，一行中的第一项是文档的标识符。从tokens[0]中获取该标识符并且将其传送给Document类的构造函数。然后，对于tokens字符串数组中剩下的值，将其再次分割，进而获得每个单词的信息，包括整个单词及其TF-IDF值。

DistanceMeasurer类

该类计算文档与簇（用向量表示）之间的欧氏距离。经过排序之后，单词数组中的单词将以与质心数组同样的顺序存放，但是会缺少其中一些单词。对于缺少的这些单词，假设其TF-IDF值为0，这样其距离就是质心数组中对应值的平方。

public class DistanceMeasurer {
  public static double euclideanDistance(Word[] words, double[]
                                          centroid) {
    double distance = 0;
    int wordIndex = 0;
    for (int i = 0; i < centroid.length; i++) {
      if ((wordIndex < words.length) (words[wordIndex].getIndex()
                                      == i)) {
        distance += Math.pow( (words[wordIndex].getTfidf() –
                               centroid[i]), 2);
        wordIndex++;
      } else {
        distance += centroid[i] * centroid[i];
      }
    }
    return Math.sqrt(distance);
  }
}

DocumentCluster类

该类存放算法生成的每个簇的相关信息。这些信息包括与该簇相关联的所有文档构成的列表，以及代表簇的向量的质心。在本例中，该向量的维度数目与词汇表中单词的数目相同。该类含有两个属性，一个对这两个属性进行初始化的构造函数，以及获取和设置这两个属性值的方法。该类还有两个非常重要的方法，第一个是calculateCentroid()方法，该方法计算簇的质心作为向量的平均值，而这些向量代表所有与该簇相关的文档。代码如下：

public void calculateCentroid() {
  Arrays.fill(centroid, 0);
  for (Document document : documents) {
    Word vector[] = document.getData();
    for (Word word : vector) {
      centroid[word.getIndex()] += word.getTfidf();
    }
  }
  for (int i = 0; i < centroid.length; i++) {
    centroid[i] /= documents.size();
  }
}

第二个方法是initialize()方法，该方法接收一个Random对象作为参数，并且采用随机数来初始化簇向量的质心。如下所示：

public void initialize(Random random) {
  for (int i = 0; i < centroid.length; i++) {
    centroid[i] = random.nextDouble();
  }
}

7.2.2　串行版本

既然已经讲述了应用程序的公共特性，下面看看如何实现k-means聚类算法的串行版本。我们将用到两个类：用于实现算法的SerialKMeans类，以及实现main()方法来执行算法的SerialMain类。

SerialKMeans类

SerialKMeans类实现了k-means聚类算法的串行版本。该类的主要方法是calculate()方法，它接收如下参数。

Document对象数组，它存放了有关文档的信息。
要生成的簇的数目。
词汇表的大小。
用于随机数生成器的“种子”。
该方法返回一个DocumentCluster对象数组。每个簇都有一个与其相关的文档列表。首先，文档可以创建一个由clusterCount参数确定的簇的数组，并且使用initialize()方法和Random对象对其初始化，如下所示：

public class SerialKMeans {
  public static DocumentCluster[] calculate(Document[] documents,
                   int clusterCount, int vocSize, int seed) {
  DocumentCluster[] clusters = new DocumentCluster[clusterCount];
  Random random = new Random(seed);
  for (int i = 0; i < clusterCount; i++) {
  clusters[i] = new DocumentCluster(vocSize);
  clusters[i].initialize(random);
}

然后，重复指派和更新阶段，直到所有文档对应的簇都不再变化为止。最后，返回描述了文档最终组织情况的簇数组，如下述代码所示：

  boolean change = true;
  int numSteps = 0;
  while (change) {
    change = assignment(clusters, documents);
    update(clusters);
    numSteps++;
  }
  System.out.println("Number of steps: "+numSteps);
  return clusters;
}

指派阶段的工作在assignment()方法中实现。该方法接收Document对象数组和DocumentCluster对象数组作为参数。对于每个文档，该方法都计算其与所有簇之间的欧氏距离，并且将该文档指派到距离最短的簇。该方法返回一个布尔值，该值表明从当前位置到下一位置是否有一个或多个文档改变了为其指派的簇。如以下代码所示：

private static boolean assignment(DocumentCluster[] clusters, Document[]
documents) {
  boolean change = false;
  for (DocumentCluster cluster : clusters) {
    cluster.clearClusters();
  }
  int numChanges = 0;
  for (Document document : documents) {
    double distance = Double.MAX_VALUE;
    DocumentCluster selectedCluster = null;
    for (DocumentCluster cluster : clusters) {
      double curDistance = DistanceMeasurer.euclideanDistance
                      (document.getData(), cluster.getCentroid());
      if (curDistance < distance) {
        distance = curDistance;
        selectedCluster = cluster;
      }
    }
    selectedCluster.addDocument(document);
    boolean result = document.setCluster(selectedCluster);
    if (result)
      numChanges++;
    }
    System.out.println("Number of Changes: " + numChanges);
    return numChanges > 0;
  }

更新阶段在update()方法中实现。该方法接收带有簇信息的DocumentCluster对象数组作为参数，并且直接重新计算每个簇的质心。

  private static void update(DocumentCluster[] clusters) {
    for (DocumentCluster cluster : clusters) {
      cluster.calculateCentroid();
    }
  }
}

SerialMain类

SerialMain类中含有main()方法，可以启动对k-means算法的测试。首先，它从文件加载数据（单词和文档）。

public class SerialMain {
  public static void main(String[] args) {
    Path pathVoc = Paths.get("data", "movies.words");
    Map<String, Integer> vocIndex=VocabularyLoader.load(pathVoc);
    System.out.println("Voc Size: "+vocIndex.size());
    Path pathDocs = Paths.get("data", "movies.data");
    Document[] documents = DocumentLoader.load(pathDocs,
                                               vocIndex);
    System.out.println("Document Size: "+documents.length);

然后，它初始化要生成的簇数以及随机数生成器的“种子”。如果它们并未作为main()方法的参数进行传递，可以使用如下的默认值。

if (args.length != 2) {
  System.err.println("Please specify K and SEED");
  return;
  }
  int K = Integer.valueOf(args[0]);
  int SEED = Integer.valueOf(args[1]);
}

最后，启动算法，度量其执行时间，并且输出为每个簇分配的文档数。

    Date start, end;
    start=new Date();
    DocumentCluster[] clusters = SerialKMeans.calculate(documents,
                                        K ,vocIndex.size(), SEED);
    end=new Date();
    System.out.println("K: "+K+"; SEED: "+SEED);
    System.out.println("Execution Time: "+(end.getTime()-
                        start.getTime()));
    System.out.println(Arrays.stream(clusters)
                           .map (DocumentCluster::getDocumentCount)
                           .sorted (Comparator.reverseOrder())
      .map(Object::toString)
      .collect( Collectors.joining(", ", "Cluster sizes: ", "")));
  }
}

7.2.3　并发版本

为实现该算法的并发版本，我们运用了Fork/Join框架。我们已经基于RecursiveAction类实现了两种任务。如前所述，当希望使用Fork/Join框架处理不返回结果的任务时，可以使用RecursiveAction任务。将指派阶段和更新阶段的工作作为在Fork/Join框架中执行的任务来实现。

为实现k-means算法的并发版本，将修改一些公共类以便使用并发数据结构。然后，要实现两个任务。最后，还将实现ConcurrentKMeans类和ConcurrentMain类。其中，ConcurrentKMeans类实现了算法的并发版本，而ConcurrentMain类用于测试算法的并发版本。

面向Fork/Join框架的两个任务：AssignmentTask和UpdateTask

如前所述，将指派阶段和更新阶段作为在Fork/Join框架中执行的任务实现。

指派阶段指派一个文档至与该文档欧氏距离最短的簇。这样就必须要处理所有文档并且计算所有文档和所有簇之间的欧氏距离。我们将使用一个任务中的文档数作为指标，以便决定是否必须将该任务分割。从要处理所有文档的任务开始分割，直到任务要处理的文档数低于预定规模为止。

AssignmentTask类有以下几个属性。

含有有关簇数据的ConcurrentDocumentCluster对象数组。
含有有关文档数据的ConcurrentDocument对象数组。
两个整型属性start和end，它们决定了任务要处理的文档数。
AtomicInteger属性numChanges，它存放的是从上一轮执行到当前执行的过程中改变了为其指派的簇的文档数。
整型属性maxSize，它存放的是一个任务所能处理的最大文档数。
我们实现了一个构造函数来初始化所有属性，以及用于获取和设置这些属性值的方法。

这些任务（对每个任务都是如此）的主方法是compute()方法。首先，检查任务必须处理的文档数。如果该值小于或等于maxSize属性的值，那么处理这些文档。计算每个文档和所有簇之间的欧氏距离，并且为文档选择距离最短的簇。如果必要，可以使用incrementAndGet()方法增加numChanges原子变量的值。该原子变量可以同时由多个线程更新且无须同步机制，而且不会导致任何内存不一致问题。相关代码如下：

protected void compute() {
  if (end - start <= maxSize) {
    for (int i = start; i < end; i++) {
      ConcurrentDocument document = documents[i];
      double distance = Double.MAX_VALUE;
      ConcurrentDocumentCluster selectedCluster = null;
      for (ConcurrentDocumentCluster cluster : clusters) {
        double curDistance = DistanceMeasurer.euclideanDistance
                       (document.getData(), cluster.getCentroid());
        if (curDistance < distance) {
          distance = curDistance;
          selectedCluster = cluster;
        }
      }
      selectedCluster.addDocument(document);
      boolean result = document.setCluster(selectedCluster);
      if (result) {
        numChanges.incrementAndGet();
      }
    }

如果该任务要处理的文档数量太多，那么将该集合分割成两个部分，并且创建两个新的任务来分别处理这两个部分，如下所示：

  } else {
    int mid = (start + end) / 2;
    AssignmentTask task1 = new AssignmentTask(clusters, documents,
                                  start, mid, numChanges, maxSize);
    AssignmentTask task2 = new AssignmentTask(clusters, documents,
                                  mid, end, numChanges, maxSize);
    invokeAll(task1, task2);
  }
}

为了在Fork/Join池中执行上述任务，使用了invokeAll()方法。该方法在任务结束其执行后返回。

更新阶段重新计算每个簇的质心作为该簇中所有文档的平均值。如此便必须处理所有簇。我们将使用一个任务要处理的簇数作为指标来控制是否要对任务进行分割。从一个需要处理所有簇的任务开始，对其进行分割，直到任务要处理的簇比预定规模小为止。

UpdateTask类有如下属性。

含有有关簇数据的ConcurrentDocumentCluster对象数组。
两个整型属性start和end，它们确定了任务要处理的簇数。
整型属性maxSize，存储了一个任务可处理的最大簇数。
我们实现了一个初始化上述属性的构造函数，以及用于获取和设置这些属性值的方法。

compute()方法首先检查任务要处理的簇数。如果该数值小于或者等于maxSize属性的值，则该方法将处理这些簇并且更新其质心。

@Override
protected void compute() {
  if (end - start <= maxSize) {
    for (int i = start; i < end; i++) {
      ConcurrentDocumentCluster cluster = clusters[i];
      cluster.calculateCentroid();
    }

如果任务要处理的簇数量太大，那么将任务要处理的簇集合划分成两个部分，并且创建两个任务来分别处理每一半集合，如下所示：

  } else {
    int mid = (start + end) / 2;
    UpdateTask task1 = new UpdateTask(clusters, start, mid,
                                      maxSize);
    UpdateTask task2 = new UpdateTask(clusters, mid, end,
                                      maxSize);
    invokeAll(task1, task2);
  }
}

ConcurrentKMeans类

ConcurrentKMeans类实现了k-means聚类算法的并发版本。和串行版本一样，该类的主方法是calculate()方法。该方法接收如下参数。

存放有关文档信息的ConcurrentDocument对象数组。
想要生成的簇的数目。
词汇表的大小。
用于随机数生成器的“种子”。
在不将Fork/Join任务分割成其他任务的前提下，该任务所要处理的最大项数。
calculate()方法返回一个存放簇信息的ConcurrentDocumentCluster对象数组。每个簇都有与之相关的文档列表。首先，基于文档创建由numberClusters参数指定数目的簇数组，并且使用initialize()方法和一个Random对象来初始化这些簇。

public class ConcurrentKMeans {
  public static ConcurrentDocumentCluster[] calculate
                 (ConcurrentDocument[] documents int numberCluster
                  int vocSize, int seed, int maxSize) {
    ConcurrentDocumentCluster[] clusters = new
                        ConcurrentDocumentCluster[numberClusters];
    Random random = new Random(seed);
    for (int i = 0; i < numberClusters; i++) {
      clusters[i] = new ConcurrentDocumentCluster(vocSize);
      clusters[i].initialize(random);
    }

然后，重复指派阶段和更新阶段，直到所有文档所属的簇都不再改变为止。在进入循环之前，创建ForkJoinPool对象来执行该任务及其所有子任务。一旦循环完成，与其他Executor对象一样，必须对Fork/Join池使用shutdown()方法以结束其执行。最后，返回含有文档最终组织结果的簇数组。

  boolean change = true;
  ForkJoinPool pool = new ForkJoinPool();
  int numSteps = 0;
  while (change) {
    change = assignment(clusters, documents, maxSize, pool);
    update(clusters, maxSize, pool);
    numSteps++;
  }
  pool.shutdown();
  System.out.println("Number of steps: "+numSteps);
  return clusters;
}

指派阶段在assignment()方法中实现。该方法接收簇数组、文档数组和maxSize属性作为参数。首先，删除所有簇的关联文档列表。

private static boolean assignment(ConcurrentDocumentCluster[]
                       clusters, ConcurrentDocument[] documents,
                       int maxSize, ForkJoinPool pool) {
  boolean change = false;
  for (ConcurrentDocumentCluster cluster : clusters) {
    cluster.clearDocuments();
  }

然后，初始化必要的对象：用于存放已指派簇发生变化的文档数的AtomicInteger对象，以及用于启动处理过程的AssignmentTask对象。AtomicInteger类支持原子操作。也就是说，其他线程无法通过中间状态查看该操作。对于剩余线程来说，该操作可执行也可不执行。这两个对象还在set()操作和随后的get()操作之间建立了happens-before关系。使用AtomicInteger对象确保所有线程都可以以线程安全的方式更新其值。

AtomicInteger numChanges = new AtomicInteger(0);
AssignmentTask task = new AssignmentTask(clusters, documents, 0,
                            documents.length, numChanges, maxSize);
ForkJoinPool pool = new ForkJoinPool();

然后，使用ForkJoinPool的execute()方法以异步方式执行池中的任务，并且使用AssignmentTask对象的join()方法等待其结束，如下所示：

pool.execute(task);
task.join();

最后，检查已改变指派簇的文档数。如果存在发生改变的文档，将返回true值，否则返回false值。该代码如下所示：

  System.out.println("Number of Changes: " + numChanges);
  return numChanges.get() > 0;
}

更新阶段在update()方法中实现。该方法接收簇数组和maxSize作为参数。首先，创建一个UpdateTask对象来更新所有簇。然后，执行ForkJoinPool对象（该方法作为参数接收）中的任务，如下所示：

  private static void update(ConcurrentDocumentCluster[] clusters,
                              int maxSize, ForkJoinPool pool) {
    UpdateTask task = new UpdateTask(clusters, 0, clusters.length,
                                      maxSize, ForkJoinPool pool);
    pool.execute(task);
    task.join();
  }
}

ConcurrentMain类

ConcurrentMain类中含有main()方法，可启动对k-means算法的测试。它的代码与SerialMain类相当，只是将串行类改写为了并发类。

7.2.4　对比解决方案

为了对比两种解决方案，我们更改三个参数的取值并多次执行试验。

参数K确定了要生成的簇数。将其值分别设置为5、10、15和20来测试算法。
随机数生成器的“种子”。该“种子”确定了初始质心的位置。将其设置为1和13来测试算法。
对于并发算法来说，maxSize参数确定了一个任务在不分割的前提下所能处理的最大项（文档或者簇）数。将其设置为1、20和400来测试算法。

采用JMH框架执行这些示例，可以在Java中实现微型基准测试。使用面向基准测试的框架是比较好的解决方案，它直接用currentTimeMillis()方法或者nanoTime()方法度量时间。在两种不同的架构上分别执行这些示例10次。

一台计算机配置了Intel Core i5-5300处理器、Windows 7操作系统和16GB的RAM。该处理器有两个核，且每个核可以执行两个线程，这样就有四个并行线程。
另一台计算机配置了AMD A8-640处理器、Windows 10操作系统和8GB的RAM。该处理器有四个核。

下面是得到的执行时间（单位：毫秒）。首先，给出在AMD架构上得到的结果。

AMD架构
		串行版	并发版
K	种子		`maxSize`=1	`maxSize`=20	`maxSize`=400
5	1	8647.129	4919.924	3795.23	3754.424
10	1	9419.145	3665.896	3474.182	3456.362
15	1	16 324.931	6320.174	5477.755	5543.474
20	1	25 707.589	8360.485	9280.459	8362.34
5	13	5122.681	2754.947	2262.426	2254.837
10	13	12 629.098	4919.314	4593.705	4579.875
15	13	16 261.68	6838.753	5606.074	5474.2
20	13	23 626.983	7605.616	8114.582	6694.77

下面是在Intel架构上得到的结果。

Intel架构
		串行版	并发版
K	种子		`maxSize`=1	`maxSize`=20	`maxSize`=400
5	1	4049.579	5112.728	4111.275	4141.222
10	1	4290.91	4617.793	3966.848	3957.214
15	1	7155.934	4211.487	6358.552	6493.285
20	1	11 444.903	10 405.531	5949.083	10 009.849
5	13	2437.533	2893.485	2444.874	2489.087
10	13	5702.272	5637.996	5165.333	5206.648
15	13	7110.732	4115.091	6348.288	6445.648
20	13	10 495.405	9509.217	5995.638	5371.75

可以得出下述结论。

“种子”对于执行时间有着重要且不可预测的影响。有时使用“种子”13的执行时间会低一些，但有时使用“种子”1的执行时间会低一些。
增加簇的数目时，执行时间也会增加。
maxSize参数对于执行时间的影响不大。参数K或者“种子”对于执行时间的影响较大。如果增大了maxSize参数的值，将会获得更好的性能。1和20之间的差别比20和400之间的差别更大。
在所有情况下，算法的并发版本的性能都比串行版本更好。只有在Intel架构上，当簇的数目较少时，串行版的结果才会比并发版更好。

例如，如果用加速比来比较参数为K=20且seed=13的串行算法和参数为K=20、seed=13且maxSize=400的并行算法的执行速度，就会得到下面的结果。

$\begin{aligned}&S_{{\rm AMD}}=\frac{T_{{\rm serial}}}{T_{{\rm concurrent}}}=\frac{23~626.983}{6694.77}=3.529\\&S_{{\rm Intel}}=\frac{T_{{\rm serial}}}{T_{{\rm concurrent}}}=\frac{10~495.405}{5371.75}=1.95\end{aligned}$

7.2 第一个例子：k-means聚类算法