英语原文共 415 页，剩余内容已隐藏，支付完成后下载完整资料
第七章 聚类介绍
本章介绍
- 实战操作了解聚类
- 了解相似性的概念
- 使用Mahout运行一个简单的聚类实例
- 用于聚类的各种不同的距离测算方法
作为人类，我们往往会与志同道合的人交往——“物以类聚“。我们能够发现重复的模式通过联系在我们的记忆中我们看到的、听到的、闻到的、尝到的东西。例如，相比较盐，糖能够是我们更多地想起蜜。所以我们把糖和蜜的味道结合起来叫他们甜蜜。甚至我们不知道甜蜜的味道，但是知道他跟世界上所有的含糖的东西是相似的，是同一类的。我们还知道它与盐是不同类的东西。无意中，我们不同的味道使用了聚类。把糖和盐做了聚类，每个组有数百个项目。
在自然界中，我们观察到许多其他类型的群体。认为猿与猴是同一种灵长类动物。所有的猴子都具有一些特质，如较矮的高度，长长的尾巴，和扁平的鼻子。在另一方面，类人猿拥有较大的尺寸，长长的手臂，和更大的头。猩猩看起来和猴子不同，但两者都喜欢香蕉。因此，我们可以认为猿猴作为两个不同的组或者是一个爱好香蕉的灵长类动物群。我们考虑一个聚类完全取决于我们选择的项目之间的相似性测量的特点（在这种情况下，灵长类动物）。
在本章中，你会学到聚类是什么，它如何与数学的概念有关，以及参照聚类的示例使用Mahout。让我们从基础开始。
7.1聚类的基础
那么，所有关于聚类的过程是怎么样的?假如你可以去有成千上万的书籍的图书馆。在图书馆内 ，图书是杂乱无章的。要找到想读的书必须横扫所有的书籍，一本一本的才能找到特定的书。这不仅是繁琐和缓慢，而且非常枯燥。
按照标题的字母顺序排序会对读者通过标题寻找有很大的帮助，如果大多数人只是简单地浏览一下，只是找一个大概的主题的书籍呢？这样通过按照书籍的主题进行分类要比按照标题的字母顺序更有用。但是如何进行分组呢？刚刚接手这份工作，你也不会知道所有的书籍是什么的?是冲浪的、浪漫的，或你没有遇到过的主题。
通过按主题把书籍分类，你不得不把所有书放在同一线上，一本一本的开始阅读。当你遇到一本书的内容是类似以前的一本书，你就返回去把它们放在一起。当你完成的时候，你看到的是数以百计成堆的书籍，而不是成千上万的单独书籍。
干得好！这是你的第一次聚类的经验。如果一百个主题组太多了，你就得从头开始和重复刚才的过程获得书堆，直到你的主题，和另一个堆是完全不同的。
聚类是所有关于组织项目从一个给定集合成一组类似的项目。在某些方面，这些聚类可以被认为是作为项目相似集，但是与其他聚类项目不同的。
聚类集合包括三个方面：
- 算法——这是用来组合书籍的方法。
- 相似性和差异性的概念——在前面的讨论中，依赖于这本书是否属于已经存在的堆，还是应该另组新一堆的判断。
- 停止条件——图书馆的例子中，当达到这些书不能堆积起来了，或这些堆已经相当不同的，这就是终止
到现在为止，我们认为聚类物品是叠加的，但实际上你只是将它们分组。从概念上讲，聚类更像是在看哪些项目附近形成群体和盘旋他们。图7.1所示的是在一个标准的x-y平面上聚类分析中的这些点。每个圆圈表示含有几个点一个聚类。
在这个简单的例子中，这些圆圈显然是基于距离的三个聚类，代表了聚类的结果。圆是一个在聚类方面的好方法，因为群组是由中心点和半径定义的。圆的中心被称为质心，或者是聚类的平均（平均值）。它的坐标是聚类中所有点的x和y轴的平均值。
图7.1 x-y平面图的点，圆圈代表了聚类，在平面中的点可被看作三个逻辑群组，聚类算法有益于识别群组。
在本章中，我们将聚类可视化为一个几何问题。聚类的核心算法是使用几何的技术表达不同距离的测算。我们找到一些重要的距离测量法和聚类的关系。平面聚类点与文本聚类之间的具体相似性就可以表现出来。
在后面的章节中，我们探讨了一些广泛用于聚类数据的方法，以及下mahout 中的实现方法。图书馆的例子是将书分堆直到达到一定阈值的一种策略。在这个例子中形成的簇的数目取决于数据；基于书的数量和临界值，你可能发现了100，20，甚至是1个类簇。一个更好的策略是建立目标簇，而不是一个临界值，然后找到最好的群组与约束。接下来我们将详细的介绍目标簇和不同的变量。
7.2项目的相似性测量
聚类的重要问题是找到一个函数，通过任何两个数中的一个数来量化相似性。注意一下我们整片文章中使用的专业术语 ：项目和点，这两个都是聚类数据的单位。
在X-Y平面的例子，相似性的度量（相似性度量）为两个点之间的Euclidean距离。图书馆的例子没有这种清晰的数学手段，而不是完全依赖智慧的馆员来判断书之间的相似度。这在我们的例子中肯定不可行，因为我们需要一个可在计算机上实现的度量。
一个可能的度量是基于两本书的标题共同含有的词的数量。基于哈利·波特：哈利·波特和魔法石这两本书：阿兹卡班的囚徒中常见的三个词：哈利、波特和the。即使指环王： 双塔是类似于哈利·波特系列，这一相似性的测量根本不会被捕捉。你需要改变的相似性度量来对顾及书籍本身的内容。你可以将每本书的单词计数，当数量和重叠的单词数接近时，你可以判断这些书相似。
只可惜，说易行难。这些书不仅有几百个网页的文本，而且英语的特点也使得分类方法更加困难。在英语文本中有一些很频繁的词，如 a,an ,the 等等，它总是在两本书中经常出现，但又不能说明这是这两本书的相似点。
为了对抗这种影响，你可以在计算中使用的加权值，并且使用低权重表示这些词来减少对相似度值的影响。在出现很多次的词使用低权重值，出现少的用高权重。你可以衡量一些在特定的书经常出现的单词，比如那些单词强烈建议书籍的内容——类似于哈利波特的魔法。
一旦你给书中的每一个单词一个权重值，就能算出这两本书的相似性——就是所有词的词频乘以每一个词的权重的和。如果这两本书的长度相同，那么这个就是一个比较适当的方法。
如果一本书有300页，另一本有1000页呢?当然书页多的书的词量也多。你必须确保字的权重是相对于文本的长度。在自由形式的文本中加权词是一门科学。
这些和许多其他技巧是一个受欢迎的加权法的一部分称为TF-IDF（词频率——逆文档频率）。我们从本章的平面上的点开始，接下来的章节进一步理解加权方法。我们深入到TF-Idf及其对聚类质量的影响。让我们从Hello World聚类示例开始。
7.3 Hello World：运行一个简单的聚类示例
Mahout包含各种聚类的实现方法，像k-means，模糊k-means，还有canopy，仅举几例。例如我们的Hello World例子，你将运行k-means 算法。在接下来的章节，我们在Mahout和它们真实世界的应用程序中审查其他聚类算法。
7.3.1 创建输入
首先，让我们尝试一个简单的例子，聚类点在二维空间中，图像如图7.1。
我们首先创建一个指向聚类列表。Mahout的聚类算法以输入一个称为SequenceFile的特定的二进制格式，一种被Hadoop库广泛使用的格式。输入编码向量，每个都代表一个点。
清单7.1 我们第一次聚类示例输入的样本值
检查清单7.1中的样本输入。图7.2所示在x-y平面上绘制，然后两个聚类清晰地显示出来。一个聚类在平面上的一个区域包含了五个点，另一个则在另一个区域包含四个点。
Mahout的聚类算法对于输入数据涉及三个步骤：你需要对数据进行预处理，使用该数据来创建向量，并以SequenceFile格式保存该向量作为算法的输入。至于这些点，没有经过预处理是必要的，因为它们已经在二维平面上向量化了——你只需要将它们转换为一个Mahout向量类。
当你听到这个词向量时，你可能会回想起高中物理课程，向量是有方向的箭头，不是空间中单一的点。对于我们机器学习的目的，向量指的是一组有序的数字，无论是一个点或物理向量。向量具有多维（在这里，二维），每个维度都有一个数值。
提示附录B说明了向量接口及其在一些细节上的实现；提到它，需要更好的理解Mahout如何表示向量。细节不是我们实例中的关键。
在下面的小节中，我们将使用Mahout聚类二维点。这个getPoints函数将用于给定的输入点集转换为RandomAccessSparseVector格式。这些向量一旦生成，用SequenceFile格式写的它们在Mahout中的聚类算法可以读取。WritePointsToFile函数显示如何做到这个。
图7.2 绘制x-y平面的清单7.1的输入点
7.3.2 使用Mahout聚类
一旦输入准备就绪，你就可以聚类这点点。在这个例子中，我们使用k-means聚类算法，它的输入参数如下：
- SequenceFile 包含的输入的向量。
- SequenceFile 包含初始聚类中心。在这种情况下，我们设置两个聚类，因此有两个中心。
- 使用相似性度量。这里我们使用Euclidean距离测量方法作为相似性测量，本章后段我们探讨其他相似性度量方法。
- 收敛阈值。如果在一个特定的迭代的聚类中心不超过这个阈值，是不需要做进一步的迭代。
- 迭代完成的数量。
- 向量实现中使用的输入文件。
你拥有你所需要的一切，除了初始聚类中心的集合。因为你试图由九个点生成两个聚类，你需要两个点在初始中心集合，正如图7.3所示。你试图使用k-means算法寻找这个初始的两个点作为两个聚类中心的最佳猜测。
当然，你可以观察到这些猜测不是很好；两者显然都属于聚类之一。很可惜，在重要的例子里，没有方法预先知道聚类在哪里。有很多种方法来估计聚类中心——聚类算法的canopy可以快速高效地估计。
图7.3 标记初始聚类中心在k-means聚类中是一个重要的步骤
即使估计的聚类中心与实际相差很远，k-means算法将在每次迭代后都计算聚类中所有点平均中心，或者质心来调整。为了演示这个k-means纠正的本质，你将从中心点开始接近——(1,1)和(2,1)。你也可以为中心点考虑不同的输入值，然后看看k-means如何让中心汇聚的各种组合收敛。
下面的清单显示的代码，是在inmemory模式下使用Mahout k-means来聚类平面上的点的集合。
清单7.2 Hello World 聚类代码
用图片更清楚地表示清单7.2做什么，请看图7.4。
7.3.3 分析输出
使用你喜爱的IDE或命令行执行编译和运行清单7.2的代码。确保在类路径中添加所有Mahout依赖的JAR包。由于数据集太小，你将在几秒内获得下面的输出：
清单7.2中的代码用字符串来唯一标识每一个向量。这可以帮助你评估和重组聚类。正如图7.5所示，该算法能够将聚类1的中心从(2,1)调整到(8.5,8.5)——聚类1中所有点的质心。
在这个简单的例子中，Mahout能快速并比较精确地将这些点聚类成两个集合。现实世界的数据并不是这么简单。数以百万计的输入向量，每个向量又有数以百万计的维度，快速聚类变得重要，还出现质量和性能问题。很难决定会产生多少聚类，或选择怎样的相似性度量方法。对于调优性能甚至评估聚类的质量，将需要一些努力。获得完美的聚类是永不休止的任务。
7.4 探讨距离度量
Mahout聚类实现可配置足以满足几乎所有的聚类问题——问题是哪些配置是最好的！在配置中的关键因素是距离度量的选择。
图7.5 Hello World K-means聚类程序的输出。即使远离中心，k-means算法能够迭代并给Euclidean距离测量来修正中心。
在前面的例子中，我们使用我们使用EuclideanDistanceMeasure来计算点之间的距离。虽然他被证明是一个生成聚类的有效测量方法，但是在Mahout聚类包中还有其他相似性测量实现。名为DistanceMeasure的实现，这些类根据各种定义的距离计算两个向量之间的距离。距离更短的暗示两个向量更相似，反之亦然；相似性和距离是有联系的。
7.4.1 Euclidean距离度量
可以看出，Euclidean距离是最简单的距离度量方法。他是最直观和匹配距离的常规想法。
例如，在平面上给定的两个点，Euclidean距离度量可以用一把尺子来计算它们的距离。数学上，两个n维度的向量(a1, a2, ... , an) and (b1,b2, ... , bn)的Euclidean距离是
No.7 实现这个测量的Mahout类是EuclideanDistanceMeasure。
7.4.2 平方的Euclidean距离度量
正如名字所说，这个距离度量值通过Euclidean距离度量返回值的平方。N维向量(a1, a2, ... , an)和 (b1, b2, ... ,bn)的距离变成
实现这个测量的Mahout类是SquaredEuclideanDistanceMeasure。
7.4.3 Manhattan距离度量<!--
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[147026]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
