聚类介绍

本章包括

    1 实战操作了解聚类

    2.了解相似性概念

    3 使用mahout运行一个简单的聚类实例

    4.用于聚类的各种不同的距离测算方法

      作为人类，我们倾向于与志同道合的人合作—“鸟的羽毛聚集在一起。我们能够发现重复的模式通过联系在我们的记忆中的我们看到的、听到的、问道的、尝到的东 西。 例如，相比较盐 ，糖能够是我们更多地想起蜜。所以我们把糖和蜜的味道结合起来叫他们甜蜜。甚至我们不知道甜蜜的味道，但是知道他跟世界上所有的含糖的东西是相似的，是同 一类的。我们还知道它与盐是不同类的东西。无意中，我们不同的味道使用了聚类。把糖和盐做了聚类，每个组有数百个项目。

        在自然界中，我们观察不同类型的群体。认为猿与猴是同一种灵长类动物。所有的猴子 都有一些性状如短高度，长尾巴，和一个扁平的鼻子。相反，猿类有较大的尺寸，长长的手臂，和更大的头。猿看起来不同于猴子，但都喜欢香焦。所以我们可以认 为猿和猴子作为两个不同的组，或作为一个单一的爱香蕉的灵长类动物群。我们考虑一个集群完全取决于我们选择的项目之间的相似性测量的特点（在这种情况下， 灵长类动物）。

    在这一章中，从mahout学习的聚类的例子中，我们将会知道聚类是什么，如何有数据概念联系起来。让我们从基础开始吧！

 

7.1 聚类的基础

     聚类的过程是怎么样的呢?假如你可以去有成千上万的书籍的图书馆。在图书馆内 ，图书是杂乱无章的。要找到想读的书必须横扫所有的书籍，一本一本的才能特定的书。这不仅是繁琐和缓慢，而且非常枯燥。

     按照标题的字母顺序排序会对读者通过标题寻找有很大的帮助，如果大多数人只是简单地浏览一下，只是找一个大概的主题的书籍呢？这样通过按照书籍的主题进 行分类要比按照标题的字母顺序更有用。但是如何进行分组呢？刚刚接手这份工作，你也不会知道所有的书籍是什么的？是冲浪的、浪漫的，或你没有遇到过的课 题。

     通过按主题把书籍分类，你不得不把所有书放在同一线上，一本一本的开始阅读。当你遇到一本书的内容是类似以前的一本书，你就返回去把它们放在在一起。当你完成，你从数千上万的书中获取到你要的主题的一堆书。

    干得好！这是你的第一个聚类的经验。如果一百个主题组太多了，你就得从头开始和重复刚才的过程获得书堆，直到你的主题，从另一个堆是完全不同的。

    聚类是所有关于组织项目从一个给定集合成一组类似的项目。在某些方面，这些集群可以被认为是作为项目相似集，但是与其他集群项目不同的。

     聚类集合包含三项

● 算法 ———–这是用来组书籍的方法

           ●相似性和差异性的概念——-一个在前面讨论的，依赖于这本书是否属于已经存在的堆，还是应         该另组新一堆的判断。     

            ●终止条件———图书馆的例子中，当达到这些书不能堆积起来了，或这些堆已经相当不同的，这就是终止

          在这个简单的例子中，圈出来的显然是基于距离三个集群，代表了聚类的结果。圆是一个在聚类方面是一个很好的方法。由于群组通过中心点和半径来定义的，圆的中心被叫为群重心，或者群平均（平均值），群重心的坐标是类簇中的所有点的x,y轴的平均值

           项目的相似性测量

                                        图7.1x-y平面图的点，圆圈代表了聚类，在平面团中的点归类了单个逻辑群组，聚类算法有益于识别群组

        在本章中，我们将聚类可视化为一个几何问题。聚类的核心是使用几何的技术表达不同距离的测算。我们找到一些重要的距离测算法和聚类关系。平面聚类点与文本聚类之间的具体相似性就可以抽象出来。

          在后面的章节中，我们探讨了广泛用于聚类的方法数据，以及mahout 中使用

方法。图书馆的例子是将书分堆直到达到一定阈值的一种策 略。在这个例子中形成的簇的数目取决于数据；基于许多书和临界值，你可能发现了100后者20，甚至是1个类簇。一个更好的策略是建立目标簇，而不是一个 临界值，然后找到最好的群组与约束。接下来我们将详细的介绍目标簇和不同的变量

7.2项目的相似性测量

       聚类的重要问题是找到一方法，通过任何两个数中的一个数来量化相似性。注意一下我们整片文章中使用的专业术语 ：项目和点，这两个是聚类数据的单位。

      在X-Y平面的例子，相似性的度量（相似性度量）的分为两个点之间的欧几里德距离。图书馆的例子没有这种清晰的数学手段，而不是完全依赖的智慧馆员之间的相似度来判断书。这工作不在我们的案例，因为我们需要一个度量，可在计算机上实现.

         一个可能的度量是基于两本书的标题共同含有的词的数量。基于哈利·波特：哲学家的石头和哈利·波特这两本书：阿兹卡班的囚徒中常见的三个词：哈利、波特、the。即时魔戒也：两塔是类似于哈利·波特系列，这一措施相似不会捕获这一切。你需要改变的相似性度量来对书籍本身的内容帐户。你可以将单词计数。

         只可惜，说的容易做起来难。这些书不仅有几百个网页的文本，而且英语的特点也使的分类方法更加困难。在英语文本中有一些很频繁的次例如 a,an ,the 等等，它总是经常发生但又不能说明这是这两本书的相似点。

         为了对抗这种影响，你可以在计算中使用的加权值，并且使用低权重表示这些词来减少对相似度值的影响。在出现很多次的词使用低权重值，出现少的用高权重。你可以衡量一个特定的书经常出现的，比如那些强烈建议内容的书籍–类似于魔术类的哈利波特。

       你给书中的每一个单词一个权重，就能算出这本中的相似性–就是所有词的词频乘以每一个词的权重的和。如果这两本书的长度相同，那么这个就是一个比较适当的方法。

   如果一本书有300页，另一本有1000页呢？当然书页大的书的词也多。

聚类算法

9.1 K-means聚类

K-means需要用户设定一个聚类个数（k）作为输入数据，有时k值可能非常大（10,000），这是Mahout闪光的（shines）地方，它确保聚类的可测量性。

为了用k-means达到高质量的聚类，需要估计一个k值。估计k值一种近似的方法是根据你需要的聚类个数。比如100万篇文章，如果平均500篇 分为一类，k值可以取2000（1000000/500）。这种估计聚类个数非常模糊，但k-means算法就是生成这种近似的聚类。

9.1.1 All you need to know about k-means

下面看一下k-means算法的细节，K-means算法是硬聚类算法，是典型的局域原型的目标函数聚类方法的代表，它是数据点到原型的某种距离作 为优化的目标函数，利用函数求极值的方法得到迭代运算的调整规则。算法采用误差平方和准则函数作为聚类准则函数。K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。k个初始类聚类中心点的选取对聚类结果具有较大的。

算法步骤：

（1）随机选取任意k个对象作为初始聚类中心，初始代表一个簇；

（2）计算点到质心的距离，并把它归到最近的质心的类；

（3）重新计算已经得到的各个类的质心；

（4）迭代2~3步直至新的质心与原质心相等或小于指定阈值，算法结束。

这种两步算法是最大期望算法（EM）的典型例子，

第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；

第二步是最大化（M），最大化在 E 步上求得的最大似然值来计算参数的值。

M 步上找到的参数估计值被用于下一个 E 步计算中，这个过程不断交替进行。

9.1.2 Running k-means clustering

K-mean聚类用到KMeansClusterer或KMeansDriver类，前一个是在内存（in-memory）里对节点聚类，后者采用 MapReduce任务执行。这两种方法都可以就像一个普通的Java程序运行,并且可以从硬盘读取和写入数据。它们也可以在hadoop上执行聚类，通 过分布式文件系统读写数据。

下面举例,使用一个随机点生成器函数来创建一些点。这些点生成矢量格式的点作为一个正态分布围绕着一个中心。使用Mahout的in-memory K-means 聚类方法对这些点聚类。

创建节点：generateSamples方法，取（1,1）为中心点，标准差为2,400个围绕着（1,1）的随机点，近似于正态分布。另外又取了2个数据集，中心分别为（1,0）和（0,2），标准差分别为0.5和0.1。

KMeansClusterer.clusterPoints()方法用到一下参数：

• List<Vector>作为输入；
• 距离算法DistanceMeasure采用EuclideanDistanceMeasure；
• 聚类的阈值Threshold为0.01；
• 聚类的个数为3；
• 聚类的中心点采用RandomPointsUtil，随机选取的节点。

Mahout-example里的DisplayKMeans类可以直观的看到该算法在二维平面的结果，9.2节将介绍运行一个Java Swing application的DisplayKMeans。

如果数据量很大时，应采取MapReduce运行方式，将聚类算法运行在多个机器上，每个mapper得到一个子集的点，每个子集运行一个mapper。这些mapper任务计算出最近的集群作为输入流。

K-means聚类的MapReduce Job

采用KMeansDriver类的run()方法，需要输入的参数有：

• Hadoop的配置conf；
• 输入Vectors的路径，SequenceFile格式；
• 初始化聚类中心的路径，SequenceFile格式；
• 输出结果的路径，SequenceFile格式；
• 求相似距离时采用的方法，这里采用EuclideanDistanceMeasure；
• 收敛的阈值，没有超过该阈值的点可移动时，停止迭代；
• 最大迭代次数，这是硬性限制，到达该最大迭代次数时，聚类停止；
• true-迭代结束后聚类；
• true-串行执行该算法，false-并行执行该算法；

public static void run(Configuration conf,Path input,Path clustersIn,Path output,
DistanceMeasure measure,
double convergenceDelta,
int maxIterations,
boolean runClustering,
boolean runSequential)

采用SparseVectorsFromSequenceFile工具，将sequenceFile转换成Vector，因为K-means算法需要用户初始化k个质心。