9461人阅读
计算机视觉（9）
（转载本文请注明来源：http://blog.csdn.net/jiang1st2010/article/details/7654120）
& & 机器学习的常用方法，主要分为有监督学习()和无监督学习()。监督学习，就是人们常说的分类，通过已有的训练样本（即已知数据以及其对应的输出）去训练得到一个最优模型（这个模型属于某个函数的集合，最优则表示在某个评价准则下是最佳的），再利用这个模型将所有的输入映射为相应的输出，对输出进行简单的判断从而实现分类的目的，也就具有了对未知数据进行分类的能力。在人对事物的认识中，我们从孩子开始就被大人们教授这是鸟啊、那是猪啊、那是房子啊，等等。我们所见到的景物就是输入数据，而大人们对这些景物的判断结果（是房子还是鸟啊）就是相应的输出。当我们见识多了以后，脑子里就慢慢地得到了一些泛化的模型，这就是训练得到的那个（或者那些）函数，从而不需要大人在旁边指点的时候，我们也能分辨的出来哪些是房子，哪些是鸟。监督学习里典型的例子就是KNN、SVM。无监督学习（也有人叫非监督学习，反正都差不多）则是另一种研究的比较多的学习方法，它与监督学习的不同之处，在于我们事先没有任何训练样本，而需要直接对数据进行建模。这听起来似乎有点不可思议，但是在我们自身认识世界的过程中很多处都用到了无监督学习。比如我们去参观一个画展，我们完全对艺术一无所知，但是欣赏完多幅作品之后，我们也能把它们分成不同的派别（比如哪些更朦胧一点，哪些更写实一些，即使我们不知道什么叫做朦胧派，什么叫做写实派，但是至少我们能把他们分为两个类）。无监督学习里典型的例子就是了。聚类的目的在于把相似的东西聚在一起，而我们并不关心这一类是什么。因此，一个聚类算法通常只需要知道如何计算相似度就可以开始工作了。
& & & & &那么，什么时候应该采用监督学习，什么时候应该采用非监督学习呢？我也是从一次面试的过程中被问到这个问题以后才开始认真地考虑答案。一种非常简单的回答就是从定义入手，如果我们在分类的过程中有训练样本(training data)，则可以考虑用监督学习的方法；如果没有训练样本，则不可能用监督学习的方法。但是事实上，我们在针对一个现实问题进行解答的过程中，即使我们没有现成的训练样本，我们也能够凭借自己的双眼，从待分类的数据中人工标注一些样本，并把他们作为训练样本，这样的话就可以把条件改善，用监督学习的方法来做。当然不得不说的是有时候数据表达的会非常隐蔽，也就是说我们手头的信息不是抽象的形式，而是具体的一大堆数字，这样我们很难凭借人本身对它们简单地进行分类。这个说的好像有点不大明白，举个例子说就是在的时候，我们利用k-means的方法聚类从而对数据投影，这时候用k-means就是因为我们当前到手的只有一大堆数据，而且是很高维的，当我们想把他们分为50个类的时候，我们已经无力将每个数据标记说这个数应该是哪个类，那个数又应该是哪个类了。所以说遇到这种情况也只有无监督学习能够帮助我们了。那么这么说来，能不能再深入地问下去，如果有训练样本（或者说如果我们可以获得到一些训练数据的话），监督学习就会比无监督学习更合适呢？（照我们单纯地想，有高人教总比自己领悟来的准，来的快吧！）我觉得一般来说，是这样的，但是这要具体看看训练数据的获取。本人在最近课题的研究中，手动标注了大量的训练样本（当然这些样本基本准确了），而且把样本画在特征空间中发现线性可分性非常好，只是在分类面附近总有一些混淆的数据样本，从而用线性分类器进行分类之后这样样本会被误判。然而，如果用来分的话，这些易混淆的点被正确分类的更多了。对这个现象的一个解释，就是不管是训练样本，还是待聚类的数据，并不是所有数据都是相互独立同分布的。换句话说，数据与数据的分布之间存在联系。在我阅读监督学习的大量材料中，大家都没有对训练数据的这一假设（独立同分布）进行说明，直到我阅读到的提示后才恍然大悟。对于不同的场景，正负样本的分布如果会存在偏移（可能是大的偏移，也可能偏移比较小），这样的话用监督学习的效果可能就不如用非监督学习了。
聚类的方法有很多种，k-means要数最简单的一种聚类方法了，其大致思想就是把数据分为多个堆，每个堆就是一类。每个堆都有一个聚类中心（学习的结果就是获得这k个聚类中心），这个中心就是这个类中所有数据的均值，而这个堆中所有的点到该类的聚类中心都小于到其他类的聚类中心（分类的过程就是将未知数据对这k个聚类中心进行比较的过程，离谁近就是谁）。其实k-means算的上最直观、最方便理解的一种聚类方式了，原则就是把最像的数据分在一起，而“像”这个定义由我们来完成，比如说欧式距离的最小，等等。想对k-means的具体算法过程了解的话，请看这里。而在这篇博文里，我要介绍的是另外一种比较流行的聚类方法----GMM（Gaussian
Mixture Model）。
& & GMM和k-means其实是十分相似的，区别仅仅在于对GMM来说，我们引入了概率。说到这里，我想先补充一点东西。统计学习的模型有两种，一种是概率模型，一种是非概率模型。所谓概率模型，就是指我们要学习的模型的形式是P(Y|X)，这样在分类的过程中，我们通过未知数据X可以获得Y取值的一个概率分布，也就是训练后模型得到的输出不是一个具体的值，而是一系列值的概率（对应于分类问题来说，就是对应于各个不同的类的概率），然后我们可以选取概率最大的那个类作为判决对象（算软分类soft
assignment）。而非概率模型，就是指我们学习的模型是一个决策函数Y=f(X)，输入数据X是多少就可以投影得到唯一的一个Y，就是判决结果（算硬分类hard
assignment）。回到GMM，学习的过程就是训练出几个概率分布，所谓混合高斯模型就是指对样本的概率密度分布进行估计，而估计的模型是几个高斯模型加权之和（具体是几个要在模型训练前建立好）。每个高斯模型就代表了一个类（一个Cluster）。对样本中的数据分别在几个高斯模型上投影，就会分别得到在各个类上的概率。然后我们可以选取概率最大的类所为判决结果。
& & 得到概率有什么好处呢？我们知道人很聪明，就是在于我们会用各种不同的模型对观察到的事物和现象做判决和分析。当你在路上发现一条狗的时候，你可能光看外形好像邻居家的狗，又更像一点点女朋友家的狗，你很难判断，所以从外形上看，用软分类的方法，是女朋友家的狗概率51%，是邻居家的狗的概率是49%，属于一个易混淆的区域内，这时你可以再用其它办法进行区分到底是谁家的狗。而如果是硬分类的话，你所判断的就是女朋友家的狗，没有“多像”这个概念，所以不方便多模型的融合。
& & 从中心极限定理的角度上看，把混合模型假设为高斯的是比较合理的，当然也可以根据实际数据定义成任何分布的Mixture Model,不过定义为高斯的在计算上有一些方便之处，另外，理论上可以通过增加Model的个数，用GMM近似任何概率分布。
& & 混合高斯模型的定义为：
& & 其中K为模型的个数，πk为第k个高斯的权重，则为第k个高斯的概率密度函数，其均值为μk，方差为σk。我们对此概率密度的估计就是要求πk、μk和σk各个变量。当求出的表达式后，求和式的各项的结果就分别代表样本x属于各个类的概率。
& & 在做参数估计的时候，常采用的方法是。最大似然法就是使样本点在估计的概率密度函数上的概率值最大。由于概率值一般都很小，N很大的时候这个连乘的结果非常小，容易造成浮点数下溢。所以我们通常取log，将目标改写成：
& & 也就是最大化log-likelyhood function，完整形式则为：
& & 一般用来做参数估计的时候，我们都是通过对待求变量进行求导来求极值，在上式中，log函数中又有求和，你想用求导的方法算的话方程组将会非常复杂，所以我们不好考虑用该方法求解（没有闭合解）。可以采用的求解方法是——将求解分为两步：第一步是假设我们知道各个高斯模型的参数（可以初始化一个，或者基于上一步迭代结果），去估计每个高斯模型的权值；第二步是基于估计的权值，回过头再去确定高斯模型的参数。重复这两个步骤，直到波动很小，近似达到极值（注意这里是个极值不是最值，EM算法会陷入局部最优）。具体表达如下：
& & 1、对于第i个样本xi来说，它由第k个model生成的概率为：
& & 在这一步，我们假设高斯模型的参数和是已知的（由上一步迭代而来或由初始值决定）。
& &（E step）
& & （M step）
& & 3、重复上述两步骤直到算法收敛（这个算法一定是收敛的，至于具体的证明请回溯到EM算法中去，而我也没有具体关注，以后补上）。
& & 最后总结一下，用GMM的优点是投影后样本点不是得到一个确定的分类标记，而是得到每个类的概率，这是一个重要信息。GMM每一步迭代的计算量比较大，大于k-means。GMM的求解办法基于EM算法，因此有可能陷入局部极值，这和初始值的选取十分相关了。GMM不仅可以用在聚类上，也可以用在概率密度估计上。
（转载请注明来源：）
不管是GMM，还是k-means，都面临一个问题，就是k的个数如何选取？比如在bag-of-words模型中，用k-means训练码书，那么应该选取多少个码字呢？为了不在这个参数的选取上花费太多时间，可以考虑层次聚类。
假设有N个待聚类的样本，对于层次聚类来说，基本步骤就是：
& & & &1、（初始化）把每个样本归为一类，计算每两个类之间的距离，也就是样本与样本之间的相似度；
& & & &2、寻找各个类之间最近的两个类，把他们归为一类（这样类的总数就少了一个）；
& & & &3、重新计算新生成的这个类与各个旧类之间的相似度；
& & & &4、重复2和3直到所有样本点都归为一类，结束。
整个聚类过程其实是建立了一棵树，在建立的过程中，可以通过在第二步上设置一个阈值，当最近的两个类的距离大于这个阈值，则认为迭代可以终止。另外关键的一步就是第三步，如何判断两个类之间的相似度有不少种方法。这里介绍一下三种：
& & & & SingleLinkage：又叫做 nearest-neighbor ，就是取两个类中距离最近的两个样本的距离作为这两个集合的距离，也就是说，最近两个样本之间的距离越小，这两个类之间的相似度就越大。容易造成一种叫做 Chaining 的效果，两个 cluster 明明从“大局”上离得比较远，但是由于其中个别的点距离比较近就被合并了，并且这样合并之后 Chaining 效应会进一步扩大，最后会得到比较松散的 cluster
& & & &CompleteLinkage：这个则完全是 Single Linkage 的反面极端，取两个集合中距离最远的两个点的距离作为两个集合的距离。其效果也是刚好相反的，限制非常大，两个 cluster 即使已经很接近了，但是只要有不配合的点存在，就顽固到底，老死不相合并，也是不太好的办法。这两种相似度的定义方法的共同问题就是指考虑了某个有特点的数据，而没有考虑类内数据的整体特点。
& & & &Average-linkage：这种方法就是把两个集合中的点两两的距离全部放在一起求一个平均值，相对也能得到合适一点的结果。
& & & &average-linkage的一个变种就是取两两距离的中值，与取均值相比更加能够解除个别偏离样本对结果的干扰。
这种聚类的方法叫做agglomerative hierarchical clustering（自顶向下）的，描述起来比较简单，但是计算复杂度比较高，为了寻找距离最近/远和均值，都需要对所有的距离计算个遍，需要用到双重循环。另外从算法中可以看出，每次迭代都只能合并两个子类，这是非常慢的。尽管这么算起来时间复杂度比较高，但还是有不少地方用到了这种聚类方法，在一书的第14章介绍新闻分类的时候，就用到了自顶向下的聚类方法。
&&&&&& 是这样的，谷歌02年推出了新闻自动分类的服务，它完全由计算机整理收集各个网站的新闻内容，并自动进行分类。新闻的分类中提取的特征是主要是词频因为对不同主题的新闻来说，各种词出现的频率是不一样的， 比如科技报道类的新闻很可能出现的词就是安卓、平板、双核之类的，而军事类的新闻则更可能出现钓鱼岛、航母、歼15、歼20这类词汇。一般对每篇文章提取(词频-逆文本频率值)特征，组成一个高维的特征向量（每一维表示一个词出现的TF-IDF值），然后采用的方法对新闻进行分类。在已知一些新闻类别的特征的情况下，采用监督学习的方法是很OK的。但是在未知的情况下，就采用这种agglomerative
hierarchical clustering进行自动分类。&这种分类方法的动机很有意思。1998年雅让斯基是某个国际会议的程序委员会主席，需要把提交上来的几百篇论文发给各个专家去评审是否录用。虽然论文的作者自己给定了论文的方向，但方向还是太广，没有什么指导意义。雅让斯基就想到了这个将论文自动分类的方法，由他的学生费罗里安很快实现了。
另外有一种聚类方法叫做divisive hierarchicalclustering（自下而上），过程恰好是相反的，一开始把所有的样本都归为一类，然后逐步将他们划分为更小的单元，直到最后每个样本都成为一类。在这个迭代的过程中通过对划分过程中定义一个松散度，当松散度最小的那个类的结果都小于一个阈值，则认为划分可以终止。这种方法用的不普遍，原文也没有做更多介绍。
不管是 agglomerative还是divisive实际上都是贪心算法了，也并不能保证能得到全局最优的。&
层次聚类的一个例子，请参考
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：480243次
积分：5016
积分：5016
排名：第5812名
原创：69篇
转载：56篇
评论：38条
(window.slotbydup = window.slotbydup || []).push({
id: '4740881',
container: s,
size: '200,200',
display: 'inlay-fix'安全检查中...
请打开浏览器的javascript，然后刷新浏览器
< 浏览器安全检查中...
还剩 5 秒&聚类分析及k均值聚类(K-means)简介zz
以下内容摘自下面链接：&
聚类分析（Cluster&analysis&）
Clustering(聚类)&和Classification(分类)
Clustering&中文翻译作“聚类”，简单地说就是把相似的东西分到一组，同Classification(分类)不同，对于一个&classifier&，通常需要你告诉
它“这个东西被分为某某类”这样一些例子，理想情况下，一个&classifier&会从它得到的训练集中进行“学习”，从而具备对未知数据进行分类的能
力，这种提供训练数据的过程通常叫做&supervised&learning&(监督学习)，而在聚类的时候，我们并不关心某一类是什么，我们需要实现
的目标只是把相似的东西聚到一起，因此，一个聚类算法通常只需要知道如何计算相似&度就可以开始工作了，因此&clustering&通常并不需要使用
训练数据进行学习，这在&Machine&Learning&中被称作&unsupervised&learning&(无监督学习)。
举一个简单的例子：现在有一群小学生，你要把他们分成几组，让组内的成员之间尽量相似一些，而组之间则差别大一些。最后分出怎样的结果，就取决于你对于“相似”的定义了（因此，在分类前，一定要知道，每一类的特征到底是什么），
比如，你决定男生和男生是相似的，女生和女生也是相似的，而男生和女生之间则差别很大”，这样，你实际上是用一个可能取两个值“男”和“女”的离散变量来
代表了原来的一个小学生，我们通常把这样的变量叫做“特征”。实际上，在这种情况下，所有的小学生都被映射到了两个点的其中一个上，已经很自然地形成了两
个组，不需要专门再做聚类了。另一种可能是使用“身高”这个特征。我在读小学候，每周五在操场开会训话的时候会按照大家住的地方的地域和距离远近来列队，
这样结束之后就可以结队回家了。除了让事物映射到一个单独的特征之外，一种常见的做法是同时提取&N&种特征，将它们放在一起组成一个&N&维向量（特征向量），从而得到一个从原始数据集合到&N&维向量空间的映射——你总是需要显式地或者隐式地完成这样一个过程，因为许多机器学习的算法都需要工作在一个向量空间中。
聚类分析指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的分析过程。聚类分析的目标就是在相似的基础上收集数据来分类。在不同的应用领域，很多聚类技术都得到了发展，这些技术方法被用作描述数据，衡量不同数据源间的相似性，以及把数据源分类到不同的簇中。
Cluster&analysis&or&clustering&is&the&task&of&assigning&a&set&of&objects&into&groups&(called&clusters)&so&that&the&objects&in&the&same&cluster&are&more&similar&(in&some&sense&or&another)&to&each&other&than&to&those&in&other&clusters.[1]
Cluster&analysis&itself&is&not&one&specific&algorithm,&but&the&general&task&to&be&solved.&It&can&be&achieved&by&various&algorithms&that&differ&significantly&in&their&notion&of&what&constitutes&a&cluster&and&how&to&efficiently&find&them.&Popular&notions&of&clusters&include&groups&with&low&distances&among&the&cluster&members,&dense&areas&of&the&data&space,&intervals&or&particular&statistical&distributions.&Clustering&can&therefore&be&formulated&as&a&multi-objective&optimization&problem.&The&appropriate&clustering&algorithm&and&parameter&settings&(including&values&such&as&the&distance&function&to&use,&a&density&threshold&or&the&number&of&expected&clusters)&depend&on&the&individual&data&set&and&intended&use&of&the&results.&Cluster&analysis&as&such&is&not&an&automatic&task,&but&an&iterative&process&of&knowledge&discovery&or&interactive&multi-objective&optimization&that&involves&trial&and&failure.&It&will&often&be&necessary&to&modify&preprocessing&and&parameters&until&the&result&achieves&the&desired&properties.
那么让我们再回到&clustering&的问题上，暂且抛开原始数据是什么形式，假设我们已经将其映射到了一个欧几里德空间上，为了方便展示，就使用二维空间吧，如下图所示：
注意：上面的横纵坐标是特征变量，也即，已经把某一数据投影到特征向量空间中。
从数据点的大致形状可以看出它们大致聚为三个&cluster&，其中两个紧凑一些，剩下那个松散一些。我们的目的是为这些数据分组，以便能区分出属于不同的簇的数据，如果按照分组给它们标上不同的颜色，就是这个样子：
那么计算机要如何来完成这个任务呢？当然，计算机还没有高级到能够“通过形状大致看出来”，不过，对于这样的&N&维欧氏空间中的点进行聚类，有一个非常简单的经典算法，也就是本文标题中提到的k-means&。
K-means（K-均值聚类法）
K-均值算法表示以空间中k个点为中心进行聚类，对最靠近他们的对象归类。
该算法的最大优势在于简洁和快速。劣势在于对于一些结果并不能够满足需要，因为结果往往需要随机点的选择非常巧合。
算法归纳为(J.&MacQueen,&1967):
(1)&&初始化：选择（或人为指定）某些记录作为凝聚点&
(2)&&循环：&
&&&&&&2.1&&按就近原则将其余记录向凝聚点凝集&
&&&&&&2.2&&计算出各个初始分类的中心位置（均值）&
&&&&&&2.3&&用计算出的中心位置重新进行聚类&
如此反复循环，直到凝聚点位置收敛为止&
　　通常要求已知类别数&
　　节省运算时间&
　　样本量大于100时有必要考虑&
　　只能使用连续性变量
k-means对于需要进行聚类的数据有一个基本假设：对于每一个&cluster&，我们可以选出一个中心
点&(center)，使得该&cluster&中的所有的点到该中心点的距离小于到其他&cluster&的中心的距离。虽然实际情况中得到的数据并不
能保证总是满足这样的约束，但这通常已经是我们所能达到的最好的结果，而那些误差通常是固有存在的或者问题本身的不可分性造成的。例如下图所示的两个高斯
分布，从两个分布中随机地抽取一些数据点出来，混杂到一起，现在要让你将这些混杂在一起的数据点按照它们被生成的那个分布分开来：
于这两个分布本身有很大一部分重叠在一起了，例如，对于数据点&2.5&来说，它由两个分布产生的概率都是相等的，你所做的只能是一个猜测；稍微好一点的
情况是&2&，通常我们会将它归类为左边的那个分布，因为概率大一些，然而此时它由右边的分布生成的概率仍然是比较大的，我们仍然有不小的几率会猜错。而
整个阴影部分是我们所能达到的最小的猜错的概率，这来自于问题本身的不可分性，无法避免。因此，我们将&k-means&所依赖的这个假设看作是合理的。
基于这样一个假设，我们再来导出k-means&所要优化的目标函数：设我们一共有&N&个数据点需要分为&K&个&cluster&，k-means&要做的就是最小化
这个函数，其中在数据点&n&被归类到&cluster&k&的时候为&1&，否则为&0&。直接寻找和来最小化并不容易，不过我们可以采取迭代的办法：先固定，选择最优的，很容易看出，只要将数据点归类到离他最近的那个中心就能保证最小。下一步则固定，再求最优的。将对求导并令导数等于零，很容易得到最小的时候应该满足：
=mean(xn),其中xn为属于cluster&k的点的坐标
亦即的值应当是所有&cluster&k&中的数据点的平均值。由于每一次迭代都是取到&的最小值，因此&只会不断地减小（或者不变），而不会增加，这保证了&k-means&最终会到达一个极小值。虽然&k-means&并不能保证总是能得到全局最优解，但是对于这样的问题，像&k-means&这种复杂度的算法，这样的结果已经是很不错的了。
下面我们来总结一下&k-means&算法的具体步骤：
选定&K&个中心的
初值。这个过程通常是针对具体的问题有一些启发式的选取方法，或者大多数情况下采用随机选取的办法。因为前面说过k-means&并不能保证全局最优，而
是否能收敛到全局最优解其实和初值的选取有很大的关系，所以有时候我们会多次选取初值跑&k-means&，并取其中最好的一次结果。
将每个数据点归类到离它最近的那个中心点所代表的&cluster&中。
计算出每个&cluster&的新的中心点。
重复第二步，一直到迭代了最大的步数或者前后的的值相差小于一个阈值为止。
不过正如前面所说的那样&k-means&也并不是万能的，虽然许多时候都能收敛到一个比较好的结果，但是也有运气不好的时候会收敛到一个让人不满意的局部最优解
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。使用 Spark MLlib 做 K-means 聚类分析
此内容是该系列 # 部分中的第 # 部分： Spark 实战，第 4 部分/search/csass/search/?q=spark%2B%E5%AE%9E%E6%88%98%2B%E7%8E%8B%E9%BE%99&dws=cndw&ibm-search.x=-655&ibm-search.y=-329&ibm-search=Search&sn=dw&lang=zh&cc=CN&ddr=&en=utf&lo=zh&hpp=20敬请期待该系列的后续内容。此内容是该系列的一部分：Spark 实战，第 4 部分敬请期待该系列的后续内容。
引言提起机器学习 (Machine
Learning)，相信很多计算机从业者都会对这个技术方向感到兴奋。然而学习并使用机器学习算法来处理数据却是一项复杂的工作，需要充足的知识储备，如概率论，数理统计，数值逼近，最优化理论等。机器学习旨在使计算机具有人类一样的学习能力和模仿能力，这也是实现人工智能的核心思想和方法。传统的机器学习算法，由于技术和单机存储的限制，只能在少量数据上使用，随着 HDFS(Hadoop
Distributed File
System) 等分布式文件系统出现，存储海量数据已经成为可能。然而由于 MapReduce 自身的限制，使得使用 MapReduce 来实现分布式机器学习算法非常耗时和消耗磁盘容量。因为通常情况下机器学习算法参数学习的过程都是迭代计算的，即本次计算的结果要作为下一次迭代的输入，这个过程中，如果使用 MapReduce，我们只能把中间结果存储磁盘，然后在下一次计算的时候从新读取，这对于迭代
频发的算法显然是致命的性能瓶颈。Spark 立足于内存计算，天然的适应于迭代式计算，相信对于这点，读者通过前面几篇文章已经有了较为深入的了解。然而即便这样，对于普通开发者来说，实现一个分布式机器学习算法仍然是一件极具挑战的事情。MLlib 正是为了让基于海量数据的机器学习变得更加简单，它提供了常用机器学习算法的分布式实现，开发者只需要有 Spark 基础并且了解机器学习算法的原理，以及方法相关参数的含义，就可以轻松的通过调用相应的 API 来实现基于海量数据的机器学习过程。当然，原始数据 ETL，特征指标提取，调节参数并优化学习过程，这依然需要有足够的行业知识和数据敏感度，这往往也是经验的体现。本文的重点在于向读者介绍如何使用 MLlib 机器学习库提供的 K-means 算法做聚类分析，这是一个有意义的过程，相信会对读者特别是初学者有启发意义。Spark 机器学习库简介Spark
机器学习库提供了常用机器学习算法的实现，包括聚类，分类，回归，协同过滤，维度缩减等。使用 Spark 机器学习库来做机器学习工作，可以说是非常的简单，通常只需要在对原始数据进行处理后，然后直接调用相应的 API 就可以实现。但是要想选择合适的算法，高效准确地对数据进行分析，您可能还需要深入了解下算法原理，以及相应 Spark
MLlib API 实现的参数的意义。需要提及的是，Spark 机器学习库从 1.2 版本以后被分为两个包，分别是： spark.mllibSpark MLlib
历史比较长了，1.0 以前的版本中已经包含了，提供的算法实现都是基于原始的 RDD，从学习角度上来讲，其实比较容易上手。如果您已经有机器学习方面的经验，那么您只需要熟悉下 MLlib 的 API 就可以开始数据分析工作了。想要基于这个包提供的工具构建完整并且复杂的机器学习流水线是比较困难的。 spark.mlSpark ML Pipeline 从 Spark1.2 版本开始，目前已经从 Alpha 阶段毕业，成为可用并且较为稳定的新的机器学习库。ML Pipeline
弥补了原始 MLlib 库的不足，向用户提供了一个基于 DataFrame 的机器学习工作流式 API 套件，使用 ML Pipeline
API，我们可以很方便的把数据处理，特征转换，正则化，以及多个机器学习算法联合起来，构建一个单一完整的机器学习流水线。显然，这种新的方式给我们提供了更灵活的方法，而且这也更符合机器学习过程的特点。从官方文档来看，Spark ML Pipeline 虽然是被推荐的机器学习方式，但是并不会在短期内替代原始的 MLlib 库，因为 MLlib 已经包含了丰富稳定的算法实现，并且部分 ML
Pipeline 实现基于 MLlib。而且就笔者看来，并不是所有的机器学习过程都需要被构建成一个流水线，有时候原始数据格式整齐且完整，而且使用单一的算法就能实现目标，我们就没有必要把事情复杂化，采用最简单且容易理解的方式才是正确的选择。本文基于 Spark 1.5，向读者展示使用 MLlib API 进行聚类分析的过程。读者将会发现，使用 MLlib
API 开发机器学习应用方式是比较简单的，相信本文可以使读者建立起信心并掌握基本方法，以便在后续的学习和工作中事半功倍。K-means 聚类算法原理聚类分析是一个无监督学习 (Unsupervised Learning) 过程, 一般是用来对数据对象按照其特征属性进行分组，经常被应用在客户分群，欺诈检测，图像分析等领域。K-means
应该是最有名并且最经常使用的聚类算法了，其原理比较容易理解，并且聚类效果良好，有着广泛的使用。和诸多机器学习算法一样，K-means 算法也是一个迭代式的算法，其主要步骤如下: 第一步，选择 K 个点作为初始聚类中心。
第二步，计算其余所有点到聚类中心的距离，并把每个点划分到离它最近的聚类中心所在的聚类中去。在这里，衡量距离一般有多个函数可以选择，最常用的是欧几里得距离 (Euclidean&#160;Distance), 也叫欧式距离。公式如下：其中 C 代表中心点，X 代表任意一个非中心点。 第三步，重新计算每个聚类中所有点的平均值，并将其作为新的聚类中心点。 最后，重复 (二)，(三) 步的过程，直至聚类中心不再发生改变，或者算法达到预定的迭代次数，又或聚类中心的改变小于预先设定的阀值。 在实际应用中，K-means 算法有两个不得不面对并且克服的问题。 聚类个数 K 的选择。K 的选择是一个比较有学问和讲究的步骤，我们会在后文专门描述如何使用 Spark 提供的工具选择 K。 初始聚类中心点的选择。选择不同的聚类中心可能导致聚类结果的差异。 Spark MLlib K-means 算法的实现在初始聚类点的选择上，借鉴了一个叫 K-means||的类 K-means++ 实现。K-means++ 算法在初始点选择上遵循一个基本原则:
初始聚类中心点相互之间的距离应该尽可能的远。基本步骤如下: 第一步，从数据集 X 中随机选择一个点作为第一个初始点。 第二步，计算数据集中所有点与最新选择的中心点的距离 D(x)。
第三步，选择下一个中心点，使得最大。 第四部，重复 (二),(三) 步过程，直到 K 个初始点选择完成。MLlib 的 K-means 实现Spark MLlib 中 K-means 算法的实现类 (KMeans.scala) 具有以下参数，具体如下。图 1. MLlib K-means 算法实现类预览通过下面默认构造函数，我们可以看到这些可调参数具有以下初始值。图 2. MLlib K-means 算法参数初始值参数的含义解释如下：k 表示期望的聚类的个数。maxInterations 表示方法单次运行最大的迭代次数。runs 表示算法被运行的次数。K-means 算法不保证能返回全局最优的聚类结果，所以在目标数据集上多次跑 K-means 算法，有助于返回最佳聚类结果。initializationMode 表示初始聚类中心点的选择方式, 目前支持随机选择或者 K-means||方式。默认是 K-means||。initializationSteps表示 K-means||方法中的部数。epsilon 表示 K-means 算法迭代收敛的阀值。seed 表示集群初始化时的随机种子。通常应用时，我们都会先调用 KMeans.train 方法对数据集进行聚类训练，这个方法会返回 KMeansModel 类实例，然后我们也可以使用 KMeansModel.predict
方法对新的数据点进行所属聚类的预测，这是非常实用的功能。KMeans.train 方法有很多重载方法，这里我们选择参数最全的一个展示。图 3. KMeans.train 方法预览KMeansModel.predict 方法接受不同的参数，可以是向量，或者 RDD，返回是入参所属的聚类的索引号。图 4. KMeansModel.predict 方法预览聚类测试数据集简介在本文中，我们所用到目标数据集是来自 UCI Machine Learning Repository 的 。UCI 是一个关于机器学习测试数据的下载中心站点，里面包含了适用于做聚类，分群，回归等各种机器学习问题的数据集。Wholesale customer Data Set
是引用某批发经销商的客户在各种类别产品上的年消费数。为了方便处理，本文把原始的 CSV 格式转化成了两个文本文件，分别是训练用数据和测试用数据。图 5. 客户消费数据格式预览读者可以从标题清楚的看到每一列代表的含义，当然读者也可以到 UCI 网站上去找到关于该数据集的更多信息。虽然 UCI 的数据可以自由获取并使用，但是我们还是在此声明，该数据集的版权属 UCI 以及其原始提供组织或公司所有。案例分析和编码实现本例中，我们将根据目标客户的消费数据，将每一列视为一个特征指标，对数据集进行聚类分析。代码实现步骤如下清单 1. 聚类分析实现类源码import org.apache.spark.{SparkContext, SparkConf}
import org.apache.spark.mllib.clustering.{KMeans, KMeansModel}
import org.apache.spark.mllib.linalg.Vectors
object KMeansClustering { def main (args: Array[String]) { if (args.length & 5) {
println("Usage:KMeansClustering trainingDataFilePath testDataFilePath numClusters
numIterations runTimes") sys.exit(1) } val conf = new
SparkConf().setAppName("Spark MLlib Exercise:K-Means Clustering") val sc = new SparkContext(conf)
/** *Channel Region Fresh Milk Grocery Frozen Detergents_Paper Delicassen * 2 3
4 1338 * 2 3 68 76 * 2 3
16 7844 */
val rawTrainingData = sc.textFile(args(0)) val parsedTrainingData =
rawTrainingData.filter(!isColumnNameLine(_)).map(line =& {
Vectors.dense(line.split("\t").map(_.trim).filter(!"".equals(_)).map(_.toDouble)) }).cache()
// Cluster the data into two classes using KMeans
val numClusters = args(2).toInt val numIterations = args(3).toInt val runTimes =
args(4).toInt var clusterIndex:Int = 0 val clusters:KMeansModel =
KMeans.train(parsedTrainingData, numClusters, numIterations,runTimes)
println("Cluster Number:" + clusters.clusterCenters.length)
println("Cluster Centers Information Overview:") clusters.clusterCenters.foreach(
println("Center Point of Cluster " + clusterIndex + ":")
println(x) clusterIndex += 1 })
//begin to check which cluster each test data belongs to based on the clustering result
val rawTestData = sc.textFile(args(1)) val parsedTestData = rawTestData.map(line =&
Vectors.dense(line.split("\t").map(_.trim).filter(!"".equals(_)).map(_.toDouble))
}) parsedTestData.collect().foreach(testDataLine =& { val predictedClusterIndex:
Int = clusters.predict(testDataLine)
println("The data " + testDataLine.toString + " belongs to cluster " +
predictedClusterIndex) })
println("Spark MLlib K-means clustering test finished.") } private def
isColumnNameLine(line:String):Boolean = { if (line != null &&
line.contains("Channel")) true else false }该示例程序接受五个入参，分别是 训练数据集文件路径 测试数据集文件路径 聚类的个数 K-means 算法的迭代次数 K-means 算法 run 的次数运行示例程序和本系列其他文章一样，我们依然选择使用 HDFS 存储数据文件。运行程序之前，我们需要将前文提到的训练和测试数据集上传到 HDFS。图 6. 测试数据的 HDFS 目录清单 2. 示例程序运行命令./spark-submit --class com.ibm.spark.exercise.mllib.KMeansClustering \
--master spark://&spark_master_node_ip&:7077 \
--num-executors 6 \
--driver-memory 3g \
--executor-memory 512m \
--total-executor-cores 6 \
/home/fams/spark_exercise-1.0.jar \
hdfs://&hdfs_namenode_ip&:9000/user/fams/mllib/wholesale_customers_data_training.txt \
hdfs://&hdfs_namenode_ip&:9000/user/fams/mllib/wholesale_customers_data_test.txt \
8 30 3图 7. K-means 聚类示例程序运行结果如何选择 K前面提到 K 的选择是 K-means 算法的关键，Spark
MLlib 在 KMeansModel 类里提供了 computeCost 方法，该方法通过计算所有数据点到其最近的中心点的平方和来评估聚类的效果。一般来说，同样的迭代次数和算法跑的次数，这个值越小代表聚类的效果越好。但是在实际情况下，我们还要考虑到聚类结果的可解释性，不能一味的选择使 computeCost 结果值最小的那个 K。清单 3. K 选择示例代码片段val ks:Array[Int] = Array(3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20)
ks.foreach(cluster =& {
val model:KMeansModel = KMeans.train(parsedTrainingData, cluster,30,1)
val ssd = puteCost(parsedTrainingData)
println("sum of squared distances of points to their nearest center when k=" + cluster + " -& "+ ssd)
})图 8. K 选择示例程序运行结果从上图的运行结果可以看到，当 K=9 时，cost 值有波动，但是后面又逐渐减小了，所以我们选择 8 这个临界点作为 K 的个数。当然可以多跑几次，找一个稳定的 K 值。理论上 K 的值越大，聚类的 cost 越小，极限情况下，每个点都是一个聚类，这时候 cost 是 0，但是显然这不是一个具有实际意义的聚类结果。结束语通过本文的学习，读者已经初步了解了 Spark 的机器学习库，并且掌握了 K-means 算法的基本原理，以及如何基于 Spark
MLlib 构建自己的机器学习应用。机器学习应用的构建是一个复杂的过程，我们通常还需要对数据进行预处理，然后特征提取以及数据清洗等，然后才能利用算法来分析数据。Spark
MLlib 区别于传统的机器学习工具，不仅是因为它提供了简单易用的 API，更重要的是 Spark 在处理大数据上的高效以及在迭代计算时的独特优势。虽然本文所采用的测试数据集很小，并不能反映大数据的应用场景，但是对于掌握基本原理已经足够，并且如果读者拥有更大的数据集就可以轻松的将本文的测试程序推广到大数据聚类的场景下，因为 Spark
MLlib 的编程模型都是一致的，无非是数据读取和处理的方式略有不同。希望读者可以在本文中找到自己感兴趣的知识，相信这对读者今后深入学习是有帮助的。另外，读者在阅读本文的过程中，如果遇到问题或者发现不足之处，请不吝赐教，在文末留言，共同交流学习，谢谢。
相关主题参考 ，查看关于 Spark MLlib 的基本介绍。查看 ，了解更多 K-means 算法的原理。：查找丰富的操作信息、工具和项目更新，帮助您掌握开源技术并将其用于 IBM 产品。
添加或订阅评论，请先或。
有新评论时提醒我
static.content.url=/developerworks/js/artrating/SITE_ID=10Zone=Open source, Big data and analyticsArticleID=1015688ArticleTitle=Spark 实战，第 4 部分: 使用 Spark MLlib 做 K-means 聚类分析publish-date=}