今天继续看云计算有关的文章，

有关SLA的这个概念多次出现

在这里mark一下

转的百度百科上的地址：http://baike.baidu.com.cn/view/163802.htm

服务等级协议

定义

SLA：Service-Level Agreement的缩写，意思是服务等级协议。 服务等级协议是关于网络服务供应商和客户间的一份合同，其中定义了服务类型、服务质量和客户付款等术语。

项目

典型的SLA 包括以下项目： 分配给客户的最小带宽； 客户带宽极限； 能同时服务的客户数目； 在可能影响用户行为的网络变化之前的通知安排； 拨入访问可用性； 运用统计学； 服务供应商支持的最小网络利用性能，如99.9%有效工作时间或每天最多为1分钟的停机时间； 各类客户的流量优先权； 客户技术支持和服务； 惩罚规定，为服务供应商不能满足 SLA 需求所指定。

要求

按照 SLA 要求，服务供应商采用多种技术和解决方案去监控和管理网络性能及流量，以满足 SLP 中的相关需求，并产生对应的客户结果报告。 另一方面，客户本身也提出了自己的技术及解决方案去监控邻居的流量和服务，以确保提供他们答应的传送服务项目。 SLA概念已被大量企业所采纳，作为公司 IT 部门的内部服务。大型企业的 IT 部门都规范了一套服务等级协议，以衡量、确认他们的客户（企业其他部门的用户）服务，有时也与外部网络供应商提供的服务进行比较。

1)什么是IP SLA？

Service Level Agrement(服务等级协议）在ISP领域指的是用户和服务提供商签订的服务等级合同。用户可以享受什么样的等级什么样的带宽服务等等。当然此处我们探讨的和这个无关，我们主要对企业网络环境中应用SLA的作用做探讨。

2) 什么是静态浮动路由？

浮动静态路由是一种静态路由，在主路由失效时，提供备份路由。但在主路由存在的情况下它不会出现在路由表中。浮动静态路由主要用于拔号备份.

3) IP SLA有什么功能？

-检测路由器之间的网络性能。 -量化当前网络的性能，健康状况。 -评估现有网络的服务质量。 -帮助用户分析，排除网络故障。 -和浮动静态路由，HSRP等技术结合做track功能（工程中应用较多的实例）

4) IP SLA原理？

通过发送测试报文，对网络性能，服务质量进行分析，并为用户提供网络服务质量的各种参数，例如： 抖动延迟，文件传输速率，TCP时延等等。

编辑本段服务水平协议

定义

SLA 服务水平协议（简称：SLA，全称：service level agreement）是在一定开销下为保障服务的性能和可靠性，服务提供商与用户间定义的一种双方认可的协定。通常这个开销是驱动提供服务质量的主要因素。

内容

一个完整的SLA同时也是一个合法的文档，包括所涉及的当事人、协定条款(包含应用程序和支持的服务)、违约的处罚、费用和仲裁机构、政策、修改条款、报告形式和双方的义务等。同样服务提供商可以对用户在工作负荷和资源使用方面进行规定。

保障

传统上，SLA包含了对服务有效性的保障，譬如对故障解决时间、服务超时等的保证。但是随着更多的商业应用在Internet的广泛开展，越来越需要SLA对性能（如响应时间）作出保障。这种需要将会随着越来越多的商业在Internet 的开展而重要起来。实际上，SLA的保障是以一系列的服务水平目标（SLO）的形式定义的。服务水平目标是一个或多个有限定的服务组件的测量的组合。一个SLO被实现是指那些有限定的组件的测量值在限定范围里。SLO有所谓的操作时段，在这个时间范围内，SLO必须被实现。但是由于Internet的统计特性，不可能任何时候都能实现这些保障。因此SLA一般都有实现时间段和实现比例。实现比例被定义为SLA必须实现的时间与实现时段的比值。例如：在工作负荷<100 transaction/s前提下，早上8点到下午5点服务响应时间<85ms，服务有效率>95%，在一个月内的总体实现比例 <97%。

服务标准

一、紧急情况 当网站发生服务器宕机，数据库无法读写等一级紧急事件时，网站维护方应当在1小时内响应，2小时内协助解决该情况。并在因外部原因无法立即解决时（例如服务器所在机房受到黑客攻击，服务器硬盘读写失败等事件），向客户报告情况并提供具体解决的时间。成熟的网站建设公司对于紧急情况通常都会有一套完善的应急解决方案，帮助客户及时解决突发事件，最大程度的挽救因网站无法访问导致的损失。 二、重要情况 网站正式上线过程后，有时会出现在验收过程中没有察觉的bug，这个时候，建站企业应当积极协助客户解决该bug，具体的响应时间根据bug造成的影响程度而定。根据SLA服务标准，bug的等级亦可进行进一步的划分并制定相应的解决方案。这里不予以赘述。 三、标准情况 在网站设计和网站编码阶段，因设计师和程序员协作环节的不一致性，有可能出现网页的样式问题和兼容性问题。以及由于客户临时需求的变更和新增，都会对正式运行的网站产生新的维护需求。按照需求的难易性和工作量制定相应的响应标准，是保证客户满意度的关键所在，也是SLA服务标准体系当中的重要环节。 四、次要情况 包括页面上一些细节的小调整，如个别文字、样式上的调整，图片的更替等等，通常在24小时内响应，双方商议的时间内进行解决即可。当然，SLA服务体系的出发点是为IT服务提供完善、标准、科学的解决方案，任何忽略细节的处理方式都有可能影响客户满意度。^[1]

SLA的可量化

SLA的协定有一个很重要的关注点，即SLA的“可测量性”与“测量方法”，有一些运维服务商与客户协商一些复杂的指标，但这些指标在合同周期内是根本无法进行测量的，这种SLA的协定就丧失了意义，无法测量就意味着根本无法知道执行情况、无法计算执行结果，也无从改善与控制，这是一方面，另一方面，当我们确定了一些指标后，这些指标的计算方法与测量方法也是需要注意的，这些要与客户商定清楚，避免了有指标，但最后的测量方法双方不一致，导致最终的达成结果出现偏差而发生纠纷。

云计算SLA

服务等级协议是关于网络服务供应商和客户间的一份合同，其中定义了服务类型、服务质量和客户付款等术语。SLA概念已被大量企业所采纳，作为公司IT部门的内部服务。 云计算SLA现状 ^[2]许多IT经理正在考虑把许多应用及服务迁移进云端。一部分人因为经济原因被迫考虑云计算，而另外一部分人考虑提供一些新的IT服务。不管怎样，IT经理目前以及不久的将来不得不面对服务等级协议（SLA）。 对于许多IT经理来说，评估SLA是不容易的。毕竟大多数的SLA都是一些条款形式的内容，人们很难确定某个运营商实际能够提供哪些服务。而且SLA的提出主要是为了　保护运营商的利益，而不是针对客户，这样使整个事情变得更为复杂。许多运营商提供SLA主要是为了避免一些不必要的纠纷和诉讼，同时提供给客户最小限度的保证。也就是说，当其企业选择了一个云运营商并且对那些服务进行有效的安排之后，SLA同样能够成为IT经理一种有效的工具。 IT经理需要关注SLA的三个方面：数据保护，连续性和费用开销。毋庸置疑，数据保护是最需要关注的一个要素。IT经理想要确认谁有权使用这些数据。刚开始确定数据保护的级别似乎很容易，但是还是有很多隐藏的问题。IT经理必须查出这些问题并且解决他们。 这些问题进一步的升级就涉及到了知识产权保护问题。所有的问题最后都归结为谁最终能够控制客户的这些私有数据。 一个IT经理需要明白如何利用运营商的基础构架和服务来为那些必须的应用和数据提供连续不断的保护。业务不间断性非常重要。最理想的情形是运营商保证提供100%的不间断服务，但实际上这样的保证是不可能实现的。 所有的服务提供商都将会经历在某一时刻宕机的情况，因为有很多超出他们控制范围的情况发生，包括自然灾害以及社会生活中发生的一些不确定因素。大部分的服务提供商最多能够给予99.5%正常运行时间的保证。但是这些保证通常还附带另外一些限制条件。即便如此，运营商可以尽力保证这些服务在一个可接受的层次范围之内。 一些运营商都将价格要素包含在他们的SLA中，其余的则将这些费用放置在一些独立的合同条款中。不管怎样，IT经理必须明白这些费用包含在基于云的服务中。这些费用不仅仅和预算有关，而且通常被用来确定投资收益率。价格分析通常都是财务部门的任务，但是IT经理能够帮助加速这个过程，或许还能够为那些花费在云服务上的费用提供一些简单合理的解释。 找到这些问题的的答案并牢记以上要点能够帮助IT经理作出一些有理有据的决定。当他们选择一个服务提供商并且打算和提供商建立长期合作的时候，这些决定能够同时保证服务的有效以及可靠。所有这些归结起来都是为了简化关于服务等级协议（SLA）的描述，并且给大家提供SLA的一个通俗概念。 签署云计算SLA当注意事项 没有人能够确定所有与企业防火墙外机密或私有信息存储（云计算）相关的法律风险。但是，越来越多的舆论认为，企业用户应当要求云计算供应商来维护一个安全的IT环境，以规避与云计算相关的潜在法律风险。一般来说，与云计算相关的关注领域类似于传统IT的关注领域： · 传输与存储期间的数据安全； · 数据的私密性和保密； · 一般访问、地方政府访问以及电子查询的权利； · 数据所有权； · 服务的暂停与终止； · 与云计算供应商共同协商和制定服务等级协议（SLA）。 因为许多领先的云计算供应商是拥有更为庞大客户群的实体，SLA的处罚细节并不总是可以通过谈判解决的。通常情况下，SLA只是在“要就拿走，不要拉倒”基础上提出的简单形式。因此，你应当考虑的第一个问题是你是否愿意把贵公司的数据放到一个你无法掌控的环境中。如果你对此感到无所适从，我建议你找一个供应商一起来讨论服务条款细节。 云计算存储的新手，可以考虑优先级的数据存储。通过首先迁移非核心数据，许多公司开始了云计算化的实施。这个策略可使他们试用这一服务，并确定该服务是否具有成本效益而不会担心影响核心业务功能。例如，一个刚刚接触云计算技术的律师事务所可能会决定，在把特殊机密的客户信息迁往标准网络防火墙外之前，可以尝试先把后台管理系统信息（如薪金、雇员福利）放置在云中。 云计算SLA和点菜选项 要求敏感数据驻留在私有云中既然云计算的目的在于通过设施共享实现规模经济效益，那么这可能并不是一个合适的定义；但是，有可能出现这样的场景，即使用专用云计算基础设施才是有意义的。寻找特殊的数据加密技术。如果信息特别的敏感，那么你可能需要云计算供应商来提供额外的保护。 数据存储所在地的地域限制。出于法律或与客户相关的目的，你可能不希望数据存储在执法不严格或法律不确定的海外。 独特的服务等级。如果你的企业有特殊的数据访问和使用的需求，不要犹豫，请向你的云计算供应商请求特殊服务。对违反协议条款的特殊处罚。如果对于你或你的客户来说，违犯数据私密性处以特殊处罚是非常重要的，请直接向他们提出。 处理云计算供应商所有权变更的规定。云计算市场总是出于快速的变化中。你可能需要在你的SLA中增加所有权变更或不可转让的条款。在这样的规定中，你可能需要澄清云计算供应商永远不得拥有你委托他们管理的数据，即便在你决定更换供应商时。 关于发生灾难事件时业务连续性的规定。你需要知道在发生地震、海啸或其它自然灾害事件时对你的数据的影响。 除了这些条款之外，你可能还需要增加传统的IT外包合同条款，其中你已逐渐习惯的电子查询和违犯处罚，诸如： · 基于预定义标准——内容、发件人和/或收件人、日期范围和元数据的搜索； · 与任意元数据相关的存储搜索； · 从搜索结果中新增和删除，以创建一个电子查询集。

 

 

关于lyapunov optimization看了一些资料 包括之前看的那一篇论文： infocom2013年的 Profit-Maximizing Virtual Machine Trading in a Federation of Selfish Clouds

Hongxing Li_, Chuan Wu , Zongpeng Li† and Francis C.M. Lau _Department of Computer Science, The University of Hong Kong, Hong Kong, Email: {hxli, cwu, fcmlau}@cs.hku.hk †Department of Computer Science, University of Calgary, Canada, Email: zongpeng@ucalgary.ca

这里做一些摘录和说明： 先是wiki上的： 前面这里就不紧扯了，就是介绍一下这个方法，大致的意思就是很牛逼，对动态系统有效，队列网络什么的

Lyapunov optimization

From Wikipedia, the free encyclopedia

This article describes Lyapunov optimization for dynamical systems. It gives an example application to optimal control in queueing networks.

 

## Contents    [[hide](http://en.wikipedia.org/wiki/Lyapunov_optimization)]  * [1 Introduction](http://en.wikipedia.org/wiki/Lyapunov_optimization#Introduction) * [2 Lyapunov drift for queueing networks](http://en.wikipedia.org/wiki/Lyapunov_optimization#Lyapunov_drift_for_queueing_networks) * [2.1 Quadratic Lyapunov functions](http://en.wikipedia.org/wiki/Lyapunov_optimization#Quadratic_Lyapunov_functions) * [2.2 Bounding the Lyapunov drift](http://en.wikipedia.org/wiki/Lyapunov_optimization#Bounding_the_Lyapunov_drift) * [2.3 A basic Lyapunov drift theorem](http://en.wikipedia.org/wiki/Lyapunov_optimization#A_basic_Lyapunov_drift_theorem) * [3 Lyapunov optimization for queueing networks](http://en.wikipedia.org/wiki/Lyapunov_optimization#Lyapunov_optimization_for_queueing_networks) * [4 Related links](http://en.wikipedia.org/wiki/Lyapunov_optimization#Related_links) * [5 References](http://en.wikipedia.org/wiki/Lyapunov_optimization#References) * [6 Primary Sources](http://en.wikipedia.org/wiki/Lyapunov_optimization#Primary_Sources)

 

[edit]Introduction

Lyapunov optimization refers to the use of a Lyapunov function to optimally control a dynamical system. Lyapunov functions are used extensively in control theory to ensure different forms of system stability. The state of a system at a particular time is often described by a multi-dimensional vector. A Lyapunov function is a scalar measure of this multi-dimensional state. Typically, the function is defined to grow large when the system moves towards undesirable states. System stability is achieved by taking control actions that make the Lyapunov function drift in the negative direction.

Lyapunov drift is central to the study of optimal control in queueing networks. A typical goal is to stabilize all network queues while optimizing some performance objective, such as minimizing average energy or maximizing average throughput. Minimizing the drift of a quadratic Lyapunov function leads to the backpressure routing algorithm for network stability, also called the max-weight algorithm.^[1] [2] Adding a weighted penalty term to the Lyapunov drift and minimizing the sum leads to the drift-plus-penalty algorithm for joint network stability and penalty minimization. ^{[3] [4] [5]} The drift-plus-penalty procedure can also be used to compute solutions to convex programs and linear programs.^[6]

[edit]Lyapunov drift for queueing networks

Consider a queueing network that evolves in discrete time with normalized time slots t in {0, 1, 2, …}. Suppose there are N queues in the network, and define the vector of queue backlogs at time t by:

[edit]Quadratic Lyapunov functions

For each slot t, define L(t) as the sum of the squares of the current queue backlogs (divided by 2 for convenience later):

//这里到底是什么玩意完全搞不懂，貌似就是队列积压的工作的数目的平方的和再除以二

This function is a scalar measure of the total queue backlog in the network. It is called quadratic Lyapunov function on the queue state. Define the Lyapunov drift as the change in this function from one slot to the next:

//这里是前后时间片的这样一个函数的差

[edit]Bounding the Lyapunov drift

//貌似小标题是要对李雅普诺夫漂移进行限定

Suppose the queue backlogs change over time according to the following equation:

//单个队列来看，一个队列下一个时间片积累的数目就是收到的减去处理了的（管你怎么处理，直接扔掉也算是处理了）

where a_i(t) and b_i(t) are arrivals and service opportunities, respectively, in queue i on slot t. This equation can be used to compute a bound on the Lyapunov drift for any slot t:

//这里为什么就要用平方啊，可耻啊，完全搞不懂想干嘛，而且自己推了一下这个不等式尽然不成立

Rearranging this inequality, summing over all i, and dividing by 2 leads to:

//如果前面的成立，推出这个不等式，里面的B就是界限之类的东西，但是t+1跑哪里去了？被吃了么？

where B(t) is defined:

//上面那个不等式的一部分

Suppose the second moments of arrivals and service in each queue are bounded, so that there is a finite constant B>0 such that for all t and all possible queue vectors Q(t) the following property holds:

//这个期望中间那一竖搞不清楚是要干嘛，但是大致明白是什么意思了，就是B是这个的上限，因为不管怎么样a(t)-b(t)都是个有限数

Taking conditional expectations of (Eq. 1) leads to the following bound on the conditional expected Lyapunov drift:

//这里就是替换了一下，中间那一竖还是不知道什么意思

[edit]A basic Lyapunov drift theorem

//这里貌似是基本原理之类的

In many cases, the network can be controlled so that the difference between arrivals and service at each queue satisfies the following property for some real number :

//还是进行一些YY，反正就是先YY个上界（其实不是YY，应该是有道理的，使用了某些技术，比如松弛？）

If the above holds for the same epsilon for all queues i, all slots t, and all possible vectors Q(t), then (Eq. 2) reduces to the drift condition used in the following Lyapunov drift theorem. The theorem below can be viewed as a variation on Foster's theorem for Markov chains. However, it does not require a Markov chain structure.

 ^[7] [5]

Suppose there are constants  such that for all t and all possible vectors Q(t) the conditional Lyapunov drift satisfies:

//上面那个公式继续简化，这样就用两个常量限制了这个不等式

Then for all slots t>0 the time average queue size in the network satisfies:

//这个公式是下面证明了的，其实就是通过上面一个公式通过一定时间片的累加推出来的一个有意义的结论

Taking expectations of both sides of the drift inequality and using the law of iterated expectations yields:

//这就是上上面那个公式，怎么中间的一竖去掉了，忽悠我呢

Summing the above expression over  and using the law of telescoping sums gives:

//来吧从0加到t+1，然后就搞定了 Using the fact that L(t) is non-negative and rearranging the terms in the above expression proves the result.

[edit]Lyapunov optimization for queueing networks

//李雅普诺夫优化之于队列网络

Consider the same queueing network as in the above section. Now define p(t) as a network penalty incurred on slot t. Suppose the goal is to stabilize the queueing network while minimizing the time average of p(t). For example, to stabilize the network while minimizing time average power, p(t) can be defined as the total power incurred by the network on slot t. ^[8] To treat problems of maximizing the time average of some desirable reward r(t), the penalty can be defined p(t) = -r(t). This is useful for maximizing network throughput utility subject to stability. ^[3]

//这里一个比较有用的就是penalty和reward之间可以相互转化，加个负号就行 To stabilize the network while minimizing the time average of p(t), network algorithms can be designed to make control actions that greedily minimize a bound on the following drift-plus-penalty expression on each slot t:^[5]

//这里是相当关键的一步，使用的drift-plus-penalty方法，可以简单的理解成使用将这个公式最小化的方法来控制队列

where V is a non-negative weight that is chosen as desired to affect a performance tradeoff. Choosing V = 0 reduces to minimizing a bound on the drift every slot and, for routing in multi-hop queueing networks, reduces to the backpressure routing algorithm developed by Tassiulas and Ephremides.^[1][2] Using V>0 and defining p(t) as the network power use on slot t leads to the drift-plus-penalty algorithm for minimizing average power subject to network stability developed by Neely.^[8] Using V>0 and using p(t) as -1 times an admission control utility metric leads to the drift-plus-penalty algorithm for joint flow control and network routing developed by Neely, Modiano, and Li.^[3]

^{//这一段的大致意思就是V=0和V>0是属于不同的情况，讲了一些具体的例子}

A generalization of the Lyapunov drift theorem of the previous section is important in this context. For simplicity of exposition, assume the penalty p(t) is lower bounded by some (possibly negative) real number p_min:

Let p* represent a desired target for the time average of p(t). Let V be a parameter used to weight the importance of meeting the target. The following theorem shows that if a drift-plus-penalty condition is met, then the time average penalty is at most O(1/V) above the desired target, while average queue size is O(V). The V parameter can be tuned to make time average penalty as close to (or below) the target as desired, with a corresponding queue size tradeoff.

^[5]

Suppose there are constants  such that for all t and all possible vectors Q(t) the following drift-plus-penalty condition holds:

![$(Eq. 3) text{ } E[Delta(t) + Vp(t)

Q(t)] leq B + Vp^* - epsilonsum_{i=1}^NQ_i(t)$](http://upload.wikimedia.org/math/b/1/6/b1675c31bb1684bae5ab33afd90e18e3.png)

//这里就是结论了，结合之前bounding的步骤，这里增加了V和p*这两个参数，这样对于一个有penalty需求的动态系统，使用李雅普诺夫优化可以解

Then for all t>0 the time average penalty and time average queue sizes satisfy:

• 

• 

//这有两个有用的结论，一个是有关penalty的和队列的时间上平均的大小得到上界

//证明就不讲了，和上面那个差不多

Taking expectations of (Eq. 3) and using the law of iterated expectations gives:

Summing the above over the first t slots and using the law of telescoping sums gives:

Since L(t) and Q_i(t) are non-negative quantities, it follows that:

Dividing the above by Vt and rearranging terms proves the time average penalty bound. A similar argument proves the time average queue size bound.

[edit]Related links

• Drift plus penalty
• Backpressure routing
• Lyapunov function
• Foster's theorem
• Control-Lyapunov function

[edit]References

1. ^ ^a b L. Tassiulas and A. Ephremides, “Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks, IEEE Transactions on Automatic Control, vol. 37, no. 12, pp. 1936-1948, Dec. 1992.
2. ^ ^a b L. Tassiulas and A. Ephremides, “Dynamic Server Allocation to Parallel Queues with Randomly Varying Connectivity,” IEEE Transactions on Information Theory, vol. 39, no. 2, pp. 466-478, March 1993.
3. ^ ^a b c M. J. Neely, E. Modiano, and C. Li, “Fairness and Optimal Stochastic Control for Heterogeneous Networks,” Proc. IEEE INFOCOM, March 2005.
4. [^](http://en.wikipedia.org/wiki/Lyapunov_optimization#cite_ref-now_4-0) L. Georgiadis, M. J. Neely, and L. Tassiulas, “Resource Allocation and Cross-Layer Control in Wireless Networks,” Foundations and Trends in Networking, vol. 1, no. 1, pp. 1-149, 2006.
5. ^ ^a b c d M. J. Neely. Stochastic Network Optimization with Application to Communication and Queueing Systems, Morgan & Claypool, 2010.
6. [^](http://en.wikipedia.org/wiki/Lyapunov_optimization#cite_ref-neely-dcdis_6-0) M. J. Neely, “Distributed and Secure Computation of Convex Programs over a Network of Connected Processors,” DCDIS Conf, Guelph, Ontario, July, 2005
7. [^](http://en.wikipedia.org/wiki/Lyapunov_optimization#cite_ref-leonardi_7-0) E. Leonardi, M. Mellia, F. Neri, and M. Ajmone Marsan, “Bounds on Average Delays and Queue Size Averages and Variances in Input-Queued Cell-Based Switches”, Proc. IEEE INFOCOM, 2001.
8. ^ ^a b M. J. Neely, “Energy Optimal Control for Time Varying Wireless Networks,” IEEE Transactions on Information Theory, vol. 52, no. 7, pp. 2915-2934, July, 2006.

[edit]Primary Sources

• M. J. Neely. Stochastic Network Optimization with Application to Communication and Queueing Systems, Morgan & Claypool, 2010.

Categories:  

• Networking algorithms
• Stochastic processes

 

这几天来看了一些hadoop相关的书，发现这个叫做mahout的库非常的有用，在这里mark一下

并找了一些相关的文章，这里是其中一篇，写的挺不错的。

转自：http://www.cnblogs.com/vivounicorn/archive/2011/10/08/2201986.html

——————–正文开始——————–

K-Means这个词第一次使用是在1967，但是它的思想可以追溯到1957年，它是一种非常简单地基于距离的聚类算法，认为每个Cluster由相似的点组成而这种相似性由距离来衡量，不同Cluster间的点应该尽量不相似，每个Cluster都会有一个“重心”；另外它也是一种排他的算法，即任意点必然属于某一Cluster且只属于该Cluster。当然它的缺点也比较明显，例如：对于孤立点敏感、产生最终聚类之间规模的差距不大。

一、基本思想

1、数学描述

      给定d维实数向量()，后面就将这个实数向量称作点吧，短！K-Means算法会根据事先制定的参数k，将这些点划分出k个Cluster(k ≤ n)，而划分的标准是最小化点与Cluster重心(均值)的距离平方和，假设这些Cluster为：，则数学描述如下：

![arg_Cmin sum limit_{i=1}^{k} sum limit_{x_j in C_i}{

x_j-mu_i

}^2 ](http://chart.apis.google.com/chart?cht=tx&chl=arg_Cmin+%5csum+%5climit_%7bi%3d1%7d%5e%7bk%7d+%5csum+%5climit_%7bx_j+%5cin+C_i%7d%7b%7c%7cx_j-%5cmu_i%7c%7c%7d%5e2%0a)，其中为第i个Cluster的“重心”(Cluster中所有点的平均值)。

     聚类的效果类似下图：

具体可见：http://en.wikipedia.org/wiki/K-means_clustering

2、算法步骤

      典型的算法如下，它是一种迭代的算法：

      (1)、根据事先给定的k值建立初始划分，得到k个Cluster，比如，可以随机选择k个点作为k个Cluster的重心，又或者用Canopy Clustering得到的Cluster作为初始重心(当然这个时候k的值由Canopy Clustering得结果决定)；

      (2)、计算每个点到各个Cluster重心的距离，将它加入到最近的那个Cluster；

      (3)、重新计算每个Cluster的重心；

      (4)、重复过程2~3，直到各个Cluster重心在某个精度范围内不变化或者达到最大迭代次数。

      别看算法简单，很多复杂算法的实际效果或许都不如它，而且它的局部性较好，容易并行化，对大规模数据集很有意义；算法时间复杂度是：O(nkt)，其中：n 是聚类点个数，k 是Cluster个数，t 是迭代次数。

 

三、并行化策略

      K-Means较好地局部性使它能很好的被并行化。第一阶段，生成Cluster的过程可以并行化，各个Slaves读取存在本地的数据集，用上述算法生成Cluster集合，最后用若干Cluster集合生成第一次迭代的全局Cluster集合，然后重复这个过程直到满足结束条件，第二阶段，用之前得到的Cluster进行聚类操作。

      用map-reduce描述是：datanode在map阶段读出位于本地的数据集，输出每个点及其对应的Cluster；combiner操作对位于本地包含在相同Cluster中的点进行reduce操作并输出，reduce操作得到全局Cluster集合并写入HDFS。

 

四、Mahout K-Means Clustering说明

      mahout实现了标准K-Means Clustering，思想与前面相同，一共使用了2个map操作、1个combine操作和1个reduce操作，每次迭代都用1个map、1个combine和一个reduce操作得到并保存全局Cluster集合，迭代结束后，用一个map进行聚类操作。可以在mahout-core下的src/main/java中的package：org.apache.mahout.clustering.kmeans中找到相关代码：

1、数据模型

      可以参见上一篇相同标题。

 

2、目录结构

      从目录结构上说，需要两个输入目录：一个用于保存数据点集——input，一个用来保存点的初始划分——clusters；在形成Cluster的阶段，每次迭代会生成一个目录，上一次迭代的输出目录会作为下一次迭代的输入目录，这种目录的命名为：Clusters-“迭代次数”；最终聚类点的结果会放在clusteredPoints文件夹中而Cluster信息放在Clusters-“最后一次迭代次数”文件夹中。

 

3、如何抽象Cluster

      可以从Cluster.java及其父类，对于Cluster，mahout实现了一个抽象类AbstractCluster封装Cluster，具体说明可以参考上一篇文章，这里做个简单说明：

      (1）、private int id; #每个K-Means算法产生的Cluster的id

      (2）、private long numPoints; #Cluster中包含点的个数，这里的点都是Vector

      (3）、private Vector center; #Cluster的重心，这里就是平均值，由s0和s1计算而来。

      (4）、private Vector Radius; #Cluster的半径，这个半径是各个点的标准差，反映组内个体间的离散程度，由s0、s1和s2计算而来。

      (5）、private double s0; #**表示Cluster**包含点的权重之和，

      (6）、private Vector s1; #**表示Cluster**包含点的加权和，

      (7）、private Vector s2; #**表示Cluster**包含点平方的加权和，

      (8）、public void computeParameters(); #根据s0、s1、s2计算numPoints、center和Radius：

            

            

            

                                        

            这几个操作很重要，最后三步很必要，在后面会做说明。

         (9）、public void observe(VectorWritable x, double weight); #每当有一个新的点加入当前Cluster时都需要更新s0、s1、s2的值 

      (10)、public ClusterObservation getObservations(); #这个操作在combine操作时会经常被用到，它会返回由s0、s1、s2初始化的ClusterObservation对象，表示当前Cluster中包含的所有被观察过的点

 

五、K-Means Clustering的Map-Reduce实现

      K-Means Clustering的实现同样包含单机版和MR两个版本，单机版就不说了，MR版用了两个map操作、一个combine操作和一个reduce操作，是通过两个不同的job触发，用Dirver来组织的，map和reduce阶段执行顺序是：

图1

1、初始划分的形成

      K-Means算法需要一个对数据点的初始划分，mahout里用了两种方法（以Iris dataset前3个feature为例）：

      (1)、使用RandomSeedGenerator类

      在指定clusters目录生成k个初始划分并以Sequence File形式存储，其选择方法希望能尽可能不让孤立点作为Cluster重心，大概流程如下：

      图2

      (2)、使用Canopy Clustering

      Canopy Clustering常常用来对初始数据做一个粗略的划分，它的结果可以为之后代价较高聚类提供帮助，个人觉得Canopy Clustering用在数据预处理上要比单纯拿来聚类更有用，比如对K-Means来说提供k值，另外还能很好的处理孤立点，当然，需要人工指定的参数由k变成了T1、T2，T1和T2所起的作用是缺一不可的，T1决定了每个Cluster包含点的数目，这直接影响了Cluster的“重心”和“半径”，而T2则决定了Cluster的数目，T2太大会导致只有一个Cluster，而太小则会出现过多的Cluster。通过实验，T1和T2取值会严重影响到算法的效果，如何确定T1和T2，似乎可以用AIC、BIC或者交叉验证去做，但是我没有找到具体做法，希望各位高人给指条明路:)。

      以Iris为例，canopy方法选择T1=3、T2=1.5、cd=0.5、x=10，两种方法结果的前三个维度比较如下：

      图3

      从图中不同Cluster的交界情况可以看出这两种方法的不同效果。

2、配置Cluster信息

      K-Means算法的MR实现，第一次迭代需要将随机方法或者Canopy Clustering方法结果目录作为kmeans第一次迭代的输入目录，接下来的每次迭代都需要将上次迭代的输出目录作为本次迭代的输入目录，这就需要能在每次kmeans map和kmeans reduce操作前从该目录得到Cluster的信息，这个功能由KMeansUtil.configureWithClusterInfo实现，它依据指定的HDFS目录将Canopy Cluster或者上次迭代Cluster的信息存储到一个Collection中，这个方法在之后的每个map和reduce操作中都需要。

3、KMeansMapper

      对照上一篇第三节关于MR的那幅图，map操作之前的InputFormat、Split、RR与上一篇完全相同。

      (1)、KMeansMapper接收的是(WritableComparable<?>, VectorWritable) Pair，setup方法利用KMeansUtil.configureWithClusterInfo得到上一次迭代的Clustering结果，map操作需要依据这个结果聚类。

      (2)、每个slave机器会分布式的处理存在硬盘上的数据，依据之前得到得Cluster信息，用emitPointToNearestCluster方法将每个点加入到与其距离最近的Cluster，输出结果为(与当前点距离最近Cluster的ID, 由当前点包装而成的ClusterObservations) Pair。

4、KMeansCombiner

      combiner操作是一个本地的reduce操作，发生在map之后，reduce之前：

5、KMeansReducer

      很直白的的操作，只是在setup的时候稍复杂。

      (1)、setup操作的目的是读取初始划分或者上次迭代的结果，构建Cluster信息，同时做了Map<Cluster的ID,Cluster>映射，方便从ID找Cluster。

      (2)、reduce操作非常直白，将从combiner传来的<Cluster ID，ClusterObservations>进行汇总；

      computeConvergence用来判断当前Cluster是否收敛，即新的“重心”与老的“重心”距离是否满足之前传入的精度要求；

      Last but not least，注意到有个cluster.computeParameters()操作，这个操作非常重要，它保证了本次迭代的结果不会影响到下次迭代，也就是保证了能够“重新计算每个Cluster的重心”这一步骤。

                              

                              

                              

      前三个操作得到新的Cluster信息；

                                                                                              

      后三个步骤清空S0、S1、S2信息，保证下次迭代所需的Cluster信息是“干净”的。

      之后，reduce将(Cluster ID, Cluster) Pair写入到HDFS中以”clusters-迭代次数“命名的文件夹中。

6、KMeansClusterMapper

      之前的MR操作用于构建Cluster信息，KMeansClusterMapper则用构造好的Cluster信息来聚类。

      (1)、setup依然是从指定目录读取并构建Cluster信息；

      (2)、map操作通过计算每个点到各Cluster“重心”的距离完成聚类操作，可以看到map操作结束，所有点就都被放在唯一一个与之距离最近的Cluster中了，因此之后并不需要reduce操作。

7、KMeansDriver

      如果把前面的KMeansMapper、KMeansCombiner、KMeansReducer、KMeansClusterMapper看做是砖的话，KMeansDriver就是盖房子的人，它用来组织整个kmeans算法流程(包括单机版和MR版)。示意图如下：

图4

 

8、Example

      在源码的/mahout-examples目录下的package org.apache.mahout.clustering.syntheticcontrol.kmeans中有个Job.java文件提供了对K-Means Clustering的一个版本。核心内容是两个run函数：第一个是用随机选择的方法确定初始划分；第二个是用Canopy 方法确定初始划分，需要注意的是，我们不需要Canopy 方法来做聚类操作，所以CanopyDriver.run的倒数第二个参数(runClustering)要设定为false。

      example的使用方法如下：

      ● 启动master和slave机器；

      ● 终端输入：hadoop namenode –format

      ● 终端输入：start-all.sh

      ● 查看hadoop相关进程是否启动，终端输入：jps

      ● 在HDFS创建testdata目录，终端输入：hadoop dfs -mkdir testdata

      ● 将http://archive.ics.uci.edu/ml/中Iris数据集下载，更改一下数据格式，将数据集中“，”替换为“ ”(空格)，并上传到HDFS的testdata文件夹中，进入Iris目录，终端输入：hadoop dfs -put iris.txt testdata/

      ● 用Canopy 方法确定初始划分，参数取值为：t1=3，t2=1.5，convergenceDelta=0.5，maxIter=10，进入mahout目录，确认终端执行ls后可以看到mahout-examples-0.5-job.jar这个文件，终端执行：hadoop jar mahout-examples-0.5-job.jar org.apache.mahout.clustering.syntheticcontrol.kmeans.Job -i testdata -o output -t1 3 -t2 1.5 -cd 0.5 -x 10

      ● 在http://localhost:50030/jobtracker.jsp 查看作业执行情况：

图5

 

      从HDFS上可以看到以下几个目录：

图6

      job_201110082236_0001是由InputDriver对原始数据集的一个预处理，输入目录是：testdata，输出目录是：output/data

      job_201110082236_0002是由CanopyDriver发起的对data的初始划分，输入目录是：output/data，输出目录是：output/clusters-0

      job_201110082236_0003是由KmeansDriver发起的构建Cluster的第一次迭代，输入目录是：output/clusters-0，输出目录是：output/clusters-1

      job_201110082236_0004是由KmeansDriver发起的构建Cluster的第二次迭代，输入目录是：output/clusters-1，输出目录是：output/clusters-2

      job_201110082236_0005是由KmeansDriver发起的Clustering，输入目录是：output/data，输出目录是：output/clusteredPoints

      可见，要查看最终结果需要两个信息：Cluster信息和Clustering data后点的信息，它们分别存储在HDFS的最后一次迭代目录output/clusters-2和聚类点目录output/clusteredPoints。

      ● 查看结果，将结果获取到本地，终端输入：bin/mahout clusterdump –seqFileDir /user/leozhang/output/clusters-2 –pointsDir /user/leozhang/output/clusteredPoints –output result.txt，终端输入：ls可以看到result.txt这个文件，文件内容类似：

      ● 为了能比较直观的查看数据，可以利用R(可以使用强大的RStudio，需要安装rgl)，我将数据整理到以下链接：http://files.cnblogs.com/vivounicorn/data%26result.rar ，分组显示数据前三维，不同Cluster用不同颜色表示。效果类似于图3，代码类似于：

      执行pca <- read.table(ttt,header=TRUE)可能会报错：Error in read.table(ttt, header = TRUE) : more columns than column names，没关系，再重新执行一下这句就行了。

 

六、总结

      K-Means Clustering是基于距离的排他的划分方法，初始划分对它很重要，mahout里实现了两种方法：随机方法和Canopy方法，前者比较简单，但孤立点会对其Clustering效果造成较大影响，后者对孤立点的处理能力很强但是需要确定的参数多了一个且如何合理取值需要探讨。

 

 

 

七、参考资料

      1、http://mahout.apache.org/        2、https://cwiki.apache.org/MAHOUT/k-means-clustering.html        3、http://developer.yahoo.com/hadoop/tutorial/        4、http://www.ibm.com/developerworks/cn/web/1103_zhaoct_recommstudy3/        5、http://grepcode.com/file/repo1.maven.org/maven2/org.apache.mahout/mahout-utils/0.5/org/apache/mahout/clustering/conversion/InputDriver.java#InputDriver

      6、http://faculty.chass.ncsu.edu/garson/PA765/cluster.htm

这几天在看hadoop相关的书籍，看到很多书里面提到mahout这个库，感觉非常强大，就在网上找了一些相关的文章转过来。

转自：http://www.cnblogs.com/vivounicorn/archive/2011/09/23/2186483.html

———————正文开始———————-

聚类是机器学习里很重要的一类方法，基本原则是将“性质相似”(这里就有相似的标准问题，比如是基于概率分布模型的相似性又或是基于距离的相似性)的对象尽可能的放在一个Cluster中而不同Cluster中对象尽可能不相似。对聚类算法而言，有三座大山需要爬过去：（1）、a large number of clusters，(2)、a high feature dimensionality，（3）、a large number of data points。在这三种情况下，尤其是三种情况都存在时，聚类的计算代价是非常高的，有时候聚类都无法进行下去，于是出现一种简单而又有效地方法：Canopy Method，说简单是因为它不用什么高深的理论或推导就可以理解，说有效是因为它的实际表现确实可圈可点。

一、基本思想

     1、基于Canopy Method的聚类算法将聚类过程分为两个阶段

      Stage1、聚类最耗费计算的地方是计算对象相似性的时候，Canopy Method在第一阶段选择简单、计算代价较低的方法计算对象相似性，将相似的对象放在一个子集中，这个子集被叫做Canopy ，通过一系列计算得到若干Canopy，Canopy之间可以是重叠的，但不会存在某个对象不属于任何Canopy的情况，可以把这一阶段看做数据预处理；

      Stage2、在各个Canopy 内使用传统的聚类方法(如K-means)，不属于同一Canopy 的对象之间不进行相似性计算。

      从这个方法起码可以看出两点好处：首先，Canopy 不要太大且Canopy 之间重叠的不要太多的话会大大减少后续需要计算相似性的对象的个数；其次，类似于K-means这样的聚类方法是需要人为指出K的值的，通过Stage1得到的Canopy 个数完全可以作为这个K值，一定程度上减少了选择K的盲目性。

     2、聚类精度

      对传统聚类来说，例如K-means、Expectation-Maximization、Greedy Agglomerative Clustering，某个对象与Cluster的相似性是该点到Cluster中心的距离，那么聚类精度能够被很好保证的条件是：

      对于每个Cluster都存在一个Canopy，它包含所有属于这个Cluster的元素。

      如果这种相似性的度量为当前点与某个Cluster中离的最近的点的距离，那么聚类精度能够被很好保证的条件是：

      对于每个Cluster都存在若干个Canopy，这些Canopy之间由Cluster中的元素连接（重叠的部分包含Cluster中的元素）。

      数据集的Canopy划分完成后，类似于下图：

二、单机生成Canopy的算法

      （1）、将数据集向量化得到一个list后放入内存，选择两个距离阈值：T1和T2，其中T1 > T2，对应上图，实线圈为T1，虚线圈为T2，T1和T2的值可以用交叉校验来确定；

      （2）、从list中任取一点P，用低计算成本方法快速计算点P与所有Canopy之间的距离（如果当前不存在Canopy，则把点P作为一个Canopy），如果点P与某个Canopy距离在T1以内，则将点P加入到这个Canopy；

      （3）、如果点P曾经与某个Canopy的距离在T2以内，则需要把点P从list中删除，这一步是认为点P此时与这个Canopy已经够近了，因此它不可以再做其它Canopy的中心了；

      （4）、重复步骤2、3，直到list为空结束。

三、并行策略

      并行点是比较明显的，就是生成Canopy的过程可以并行，第一阶段，各个slave可以依据存储在本地的数据，各自在本地用上述算法生成若干Canopy，最后在master机器将这些Canopy用相同算法汇总后得到最终的Canopy集合，第二阶段聚类操作就利用最终的Canopy集合进行。

      用map-reduce描述就是：datanode在map阶段，利用上述算法在本地生成若干Canopy，之后通过reduce操作得到最终的Canopy集合。

四、Mahout源码安装

      正式使用Mahout之前需要做以下准备工作：

      1、在http://mahout.apache.org/下载最新的Mahout 0.5源码包；

      2、安装mvn，可以在终端输入：sudo apt-get install maven2具体方法可以参照：http://www.mkyong.com/maven/how-to-install-maven-in-ubuntu/；

      3、安装Mahout源码，可以参照这里的方法进行：https://cwiki.apache.org/confluence/display/MAHOUT/BuildingMahout；

      4、打开eclipse，在“Help”菜单下单击“Install New Software…”，在地址栏添加：http://m2eclipse.sonatype.org/sites/m2e，之后把复选框勾上，然后一路Next即可。

      5、最后在eclipse的“File”菜单单击“Import…”，选择“Existing Maven Projects”，Next后选择Mahout源码所在目录，将感兴趣的项目勾上，最后完成步骤即可。mahout-core、mahout-examples和mahout-math是下一步我们需要的。

五、Mahout的Canopy Clustering

      mahout实现了一个Canopy Clustering，大致思路与前两节用的方法一样，用了两个map操作和一个reduce操作，首先用一个map和一个reduce生成全局Canopy集合，最后用一个map操作进行聚类。可以在mahout-core下的src/main/java中的package：org.apache.mahout.clustering.canopy中找到相关代码：

      

1、数据模型

      Mahout聚类算法将对象以Vector的方式表示，它同时支持dense vector和sparse vector，一共有三种表示方式（它们拥有共同的基类AbstractVector，里面实现了有关Vector的很多操作）：

      (1)、DenseVector

      位于mahout-math文件夹下的src/main/java中的package：org.apache.mahout.clustering.math中，它实现的时候用一个double数组表示Vector（private double[] values）， 对于dense data可以使用它；

      (2)、RandomAccessSparseVector

      位于mahout-math文件夹下的src/main/java中的package：org.apache.mahout.clustering.math中，它用来表示一个可以随机访问的sparse vector，只存储非零元素，数据的存储采用hash映射：OpenIntDoubleHashMap;

      关于OpenIntDoubleHashMap，其key为int类型，value为double类型，解决冲突的方法是double hashing，可能是我获取的源码问题，没有在0.5中找到它的source code，可以从http://grepcode.com/file/repo1.maven.org/maven2/org.apache.mahout/mahout-collections/0.3/org/apache/mahout/math/map/OpenIntDoubleHashMap.java#OpenIntDoubleHashMap.indexOfInsertion%28int%29中查看0.3中代码和较详细注释；

      (3)、SequentialAccessSparseVector

      位于mahout-math文件夹下的src/main/java中的package：org.apache.mahout.clustering.math中，它用来表示一个顺序访问的sparse vector，同样只存储非零元素，数据的存储采用顺序映射：OrderedIntDoubleMapping;

      关于OrderedIntDoubleMapping，其key为int类型，value为double类型，存储的方式让我想起了Libsvm数据表示的形式：非零元素索引:非零元素的值，这里用一个int数组存储indices，用double数组存储非零元素，要想读写某个元素，需要在indices中查找offset，由于indices应该是有序的，所以查找操作用的是二分法。

2、如何抽象Canopy？

      可以从Canopy.java文件及其父类中找到答案，Mahout在实现时候还是很巧妙的，一个Canopy包含的字段信息主要有：

      1）、private int id; #Canopy的id

      2）、private long numPoints; #Canopy中包含点的个数，这里的点都是Vector

      3）、private Vector center; #Canopy的重心

      4）、private Vector Radius; #Canopy的半径，这个半径是各个点的标准差，反映组内个体间的离散程度，它的计算依赖下面要说的s0、s1和s2。

      它并不会真的去用一个list去存储其包含的点，因为将来的计算并不关心这些点是什么，而是与由这些点得到的三个值有关，这里用三个变量来表示：

      5）、private double s0; #表示Canopy包含点的权重之和，

      6）、private Vector s1; #表示各点的加权和，

      7）、private Vector s2; #表示各点平方的加权和，

      以下是它的核心操作：

      8）、public void computeParameters(); #根据s0、s1、s2计算numPoints、center和Radius，其中numPoints=（int）s0，center=s1/s0，Radius=sqrt(s2s0-s1s1)/s0，简单点来，假设所有点权重都是1，那么：

                          ，其中

                               

                               

                               ，其中

                               

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

      9）、public void observe(VectorWritable x, double weight); #每当有一个新的点加入当前Canopy时都需要更新s0、s1、s2的值，这个比较简单。

3、Canopy Clustering的Map-Reduce实现

      Canopy Clustering的实现包含单机版和MR两个版本，单机版就不多说了，MR版用了两个map操作和一个reduce操作，当然是通过两个不同的job实现的，map和reduce阶段执行顺序是：CanopyMapper –> CanopyReducer –> ClusterMapper，我想对照下面这幅图来理解：

      (1)、首先是InputFormat，这是从HDFS读取文件后第一个要考虑的问题，mahout中提供了三种方式，都继承于FileInputFormat<K,V>：

 

**Format**	**Description**	**Key**	**Value**
TextInputFormat	Default format; reads lines of text files (默认格式，按行读取文件且不进行解析操作，基于行的文件比较有效)	The byte offset of the line(行的字节偏移量)	The line contents (整个行的内容)
KeyValueInputFormat	Parses lines into key, val pairs (同样是按照行读取，但会搜寻第一个tab字符，把行拆分为(Key，Value) pair)	Everything up to the first tab character(第一个tab字符前的所有字符)	The remainder of the line (该行剩下的内容)
SequenceFileInputFormat	A Hadoop-specific high-performance binary format (Hadoop定义的高性能二进制格式)	user-defined (用户自定义)	user-defined (用户自定义)

      在这里，由于使用了很多自定义的类型，如：表示vector的VectorWritable类型，表示canopy的canopy类型，且需要进行高效的数据处理，所以输入输出文件选择SequenceFileInputFormat格式。由job对象的setInputFormatClass方法来设置，如:job.setInputFormatClass(SequenceFileInputFormat.class)，一般在执行聚类算法前需要调用一个job专门处理原始文件为合适的格式，比如用InputDriver，这点后面再说。

      (2)、Split

      一个Split块为一个map任务提供输入数据，它是InputSplit类型的，默认情况下hadoop会把文件以64MB为基数拆分为若干Block，这些Block分散在各个节点上，于是一个文件就可以被多个map并行的处理，也就是说InputSplit定义了文件是被如何切分的。

      (3)、RR

      RecordReader类把由Split传来的数据加载后转换为适合mapper读取的(Key,Value) pair，RecordReader实例是由InputFormat决定，RR被反复调用直到Split数据处理完，RR被调用后接着就会调用Mapper的map()方法。

      “RecordReader实例是由InputFormat决定”这句话怎么理解呢？比如，在Canopy Clustering中，使用的是SequenceFileInputFormat，它会提供一个 SequenceFileRecordReader类型，利用SequenceFile.Reader将Key和Value读取出来，这里Key和Value的类型对应Mapper的map函数的Key和Value的类型，Sequence File的存储根据不同压缩策略分为：NONE：不压缩、RECORD：仅压缩每一个record中的value值、BLOCK：将一个block中的所有records压缩在一起，有以下存储格式：

**Uncompressed SequenceFile  **Header  Record

Record length  Key length  Key  Value  A sync-marker every few 100 bytes or so.

**Record-Compressed SequenceFile  **Header  Record

Record length  Key length  Key  Compressed Value  A sync-marker every few 100 bytes or so.

Block-Compressed SequenceFile Format  Header  Record Block

Compressed key-lengths block-size  Compressed key-lengths block  Compressed keys block-size  Compressed keys block  Compressed value-lengths block-size  Compressed value-lengths block  Compressed values block-size  Compressed values block  A sync-marker every few 100 bytes or so.

具体可参见：http://www.189works.com/article-18673-1.html     

      (4)、CanopyMapper

      CanopyMapper类里面定义了一个Canopy集合，用来存储通过map操作得到的本地Canopy。

      setup方法在map操作执行前进行必要的初始化工作；

      它的map操作很直白，就是将传来的(Key,Value) pair(以后就叫“点”吧，少写几个字)按照某种策略加入到某个Canopy中，这个策略在CanopyClusterer类里说明；     

      在map操作执行完后，调用cleanup操作，将中间结果写入上下文，注意这里的Key是一个固定的字符串“centroid”，将来reduce操作接收到的数据就只有这个Key，写入的value是所有Canopy的中心点(是个Vector哦)。

      (5)、Combiner

      可以看做是一个local的reduce操作，接受前面map的结果，处理完后发出结果，可以使用reduce类或者自己定义新类，这里的汇总操作有时候是很有意义的，因为它们都是在本地执行，最后发送出得数据量比直接发出map结果的要小，减少网络带宽的占用，对将来shuffle操作也有益。在Canopy Clustering中不需要这个操作。

      (6)、Partitioner & Shuffle

      当有多个reducer的时候，partitioner决定由mapper或combiner传来的(Key,Value) Pair会被发送给哪个reducer，接着Shuffle操作会把所有从相同或不同mapper或combiner传来的(Key,Value) Pair按照Key进行分组，相同Key值的点会被放在同一个reducer中，我觉得如何提高Shuffle的效率是hadoop可以改进的地方。在Canopy Clustering中，因为map后的数据只有一个Key值，也就没必要有多个reducer了，也就不用partition了。关于Partitioner可以参考：http://blog.oddfoo.net/2011/04/17/mapreduce-partition分析-2/

      (7)、CanopyReducer

      CanopyReducer 类里面同样定义了一个Canopy集合，用来存储全局Canopy。

      setup方法在reduce操作执行前进行必要的初始化工作，这里与mapper不同的地方是可以对阈值T1、T2(T1>T2)重新设置(这里用T3、T4表示)，也就是说map阶段的阈值可以与reduce阶段的不同；

      reduce操作用于map操作一样的策略将局部Canopy的中心点做重新划分，最后更新各个全局Canopy的numPoints、center、radius的信息，将(Canopy标示符，Canopy对象) Pair写入上下文中。

      (8)、OutputFormat

      它与InputFormat类似，Hadoop会利用OutputFormat的实例把文件写在本地磁盘或HDFS上，它们都是继承自FileOutputFormat类。各个reducer会把结果写在HDFS某个目录下的单独的文件内，命名规则是part-r-xxxxx，这个是依据hadoop自动命名的，此外还会在同一目录下生成一个_SUCCESS文件，输出文件夹用FileOutputFormat.setOutputPath() 设置。 

      到此为止构建Canopy的job结束。即CanopyMapper –> CanopyReducer 阶段结束。

      (9)、ClusterMapper

      最后聚类阶段比较简单，只有一个map操作，以上一阶段输出的Sequence File为输入，setup方法做一些初始化工作并从上一阶段输出目录读取文件，重建Canopy集合信息并存储在一个Canopy集合中，map操作就调用CanopyClusterer的emitPointToClosestCanopy方法实现聚类，将最终结果输出到一个Sequence File中。

      (10)、CanopyClusterer

      这个类是实现Canopy算法的核心，其中：

      1)、addPointToCanopies方法用来决定当前点应该加入到哪个Canopy中，在CanopyMapper和CanopyReducer 中用到，流程如下：

      2)、emitPointToClosestCanopy方法查找与当前点距离最近的Canopy，并将(Canopy的标示符，当前点Vector表示)输出，这个方法在聚类阶段ClusterMapper中用到。

      3)、createCanopies方法用于单机生成Canopy，算法一样，实现也较简单，就不多说了。

      (11)、CanopyDriver

      一般都会定义这么一个driver，用来定义和配置job，组织job执行，同时提供单机版和MR版。job执行顺序是:buildClusters –> clusterData。

4、其它

      CanopyMapper的输入需要是(WritableComparable<?>, VectorWritable) Pair，因此，一般情况下，需要对数据集进行处理以得到相应的格式，比如，在源码的/mahout-examples目录下的package org.apache.mahout.clustering.syntheticcontrol.canopy中有个Job.java文件提供了对Canopy Clustering的一个版本：

 

      利用InputDriver对数据集进行处理，将(Text, VectorWritable) Pair 以sequence file形式存储，供CanopyDriver使用。InputDriver中的作业配置如下：

 

5、实例说明

      可以用源码生成相关Jar文件，例如：

      (1)、准备若干数据集data，要求不同feature之间用空格隔开；

      (2)、在master的终端敲入命令：hadoop namenode –format;start-all.sh;用于初始化namenode和启动hadoop；

      (3)、在HDFS上建立testdata文件夹，聚类算法会去这个文件夹加载数据集，在终端输入：hadoop dfs –mkdir testdata；

      (4)、然后将各个datanode上的数据集data上传到HDFS，在终端输入hadoop dfs –put data testdata/

      (5)、进入mahout的那些Jar文件所在路径，在终端敲入：hadoop jar mahout-examples-0.5-job.jar org.apache.mahout.clustering.syntheticcontrol.canopy.Job;

      (6)、在localhost:50030查看作业执行情况，例如：

      可以看到，第一个作业由InputDriver发起，输入目录是testdata，一共做了一个map操作但没有做reduce操作，第二个作业由CanopyDriver发起，做了一对mapreduce操作，这里对应Canopy生成过程，最后一个作业也由CanopyDriver发起，做了一个map操作，对应Canopy Clustering过程。

      (7)、将执行结果抓到本地文件夹，在终端执行：hadoop dfs –get output output，得到目录如下：

其中聚类结果保存在第一个文件夹中，当然，结果是Sequence File，不能直接双击打开来看。

6、总结

      Mahout中对Canopy Clustering的实现是比较巧妙的，整个聚类过程用2个map操作和1个reduce操作就完成了，Canopy构建的过程可以概括为：遍历给定的点集S，设置两个阈值：T1、T2且T1>T2，选择一个点，用低成本算法计算它与其它Canpoy中心的距离，如果距离小于T1则将该点加入那个Canopy，如果距离小于T2则该点不会成为某个Canopy的中心，重复整个过程，直到S为空。

六、参考资料

      1、http://mahout.apache.org/

      2、https://cwiki.apache.org/MAHOUT/canopy-clustering.html

      3、http://developer.yahoo.com/hadoop/tutorial/

      4、http://www.ibm.com/developerworks/cn/web/1103_zhaoct_recommstudy3/

      5、http://grepcode.com/file/repo1.maven.org/maven2/org.apache.mahout/mahout-utils/0.5/org/apache/mahout/clustering/conversion/InputDriver.java#InputDriver

转自：http://www.cnblogs.com/LeftNotEasy/archive/2012/02/18/why-yarn.html

这段时间在研究map-reduce模型，看到hadoop最近alpha版动作频繁，似乎有大动作

yarn就是一个很好的例子，最近hadoop2.0放出来，其中最大的一个改变就是yarn的出现，这资源这一层独立出来

相对于之前死板的map-reduce架构，这个重大的改变使hadoop可以支持更多的计算模型

—————-分割线——————–

前言：

有一段时间没有写博客了(发现这是我博客最常见的开头，不过这次间隔真的好长），前段时间事情比较多，所以耽搁得也很多。 现在准备计划写一个新的专题，叫做《hadoop杂记》，里面的文章有深有浅，文章不是按入门-中级-高级的顺序组织的，如果想看看从入门到深入的书，比较推荐《the definitive guide of hadoop》。 今天主要想写写关于map-reduce v2(或者叫map-reduce next generation，或者叫YARN)与之前的map-reduce有什么不同。最近在学习Yarn的过程中，也参考了很多人的博客，里面的介绍都各有所长。不过一个很重要的问题是，为什么需要一个Yarn，初看之后，也不觉得Yarn有什么特别的，就是把之前设计中的一块拆成了几块，仔细想想，方才明白其中的奥妙。 理解本文需要对老的Map-reduce框架有一定的了解。有朋友如果对hadoop以及大数据处理的架构、应用的咨询、讨论等等可以按下一段的联系方式与我联系。 **版权声明：**本文由leftnoteasy发布于[http://leftnoteasy.cnblogs.com](http://leftnoteasy.cnblogs.com/)，本文可以部分或者全部的被引用，但请注明出处，可以联系wheeleast (at) gmail.com, 也可以加我weibo:[http://weibo.com/leftnoteasy](http://weibo.com/leftnoteasy)   ## Why Yarn： ### **Map-reduce****老矣，尚能饭否?** 第一次看到Yarn的问题，就需要问问，为什么要重新设计之前这样一个成熟的架构。 “The Apache Hadoop Map-reduce framework is showing it’s age, clearly”, 社区的Yarn设计文档 ”[MapReduce_NextGen-Architecture](https://issues.apache.org/jira/secure/attachment/12486023/MapReduce_NextGen_Architecture.pdf)”如是说。 目前的Map-reduce framework碰到了很多的问题，比如说过于大的内存消耗、不合理的线程模型设计、当集群规模增大后，扩展性/稳定性/性能的不足。这是目前hadoop的集群一直停留在Yahoo公布出来的3000台这个数量级上。 为了克服之前说道的问题，就需要对目前架构上进行重新思考，之后我会对新老Map-reduce架构上进行比较。   ### **Yarn****的设计需求** 这里放上设计需求不是为了凑字数的，最近越来越发现设计需求是软件开发的灵魂，虽然需求常常变化可以唤醒植物人，不过一份好的设计需求可以让之后怎么走变得非常清晰。参考自Yarn设计文档： **最优先的需求：** · Reliability · Availability · Scalability - Clusters of 10000 nodes and 200,000 cores · Backward Compatibility - Ensure customers’ Map-Reduce applications can run unchanged in the nextversion of the framework. Also implies forward compatibility. （向前兼容） · Evolution – Ability for customers to control upgrades to the grid software stack. · Predictable Latency – A major customer concern. · Cluster utilization **The second tier of requirements is****（优先级低一点的需求）:** · Support for alternate programming paradigms to Map-Reduce · Support for limited, short-lived services 这里解释一下这份需求，首先是可以支持非常大的集群规模，200k cores这个数字的确很惊人。 然后是向前兼容，之前大家都写了很多在map-reduce上面的程序，如果不能支持这些老的程序，老的用户怎么都不愿意切换到新版本上去。 另外集群资源最大化利用，这个之后会提一下 然后值得一提的是，支持增加除了Map-Reduce之外的计算模型，这个彰显了Hadoop想做领域霸主的决心，之前的Hadoop基本上就与Map-Reduce划上了等号，Map-Reduce干不了的事情，Hadoop基本上就干不了。Map-Reduce能做的事情有限（可以参考一下我之前的一篇[文章](http://www.cnblogs.com/LeftNotEasy/archive/2011/08/27/why-map-reduce-must-be-future-of-distributed-computing.html),在”hadoop的劣势”部分），简单的说就是，数据多，但是计算简单的时候，hadoop威力强大。如果计算逻辑复杂，需要搞个迭代至收敛之类的算法之类的，hadoop就玩不动了。如果能够在Hadoop上加入其他的计算模型，支持这种数据量不那么大，但是计算量大的场景，就防止一些挑剔的客户在这个问题上jjyy了。 最后说的支持limited, short-lived services还没有看到过更详细的说明，如果有人明白欢迎补充   ### **老的Map-reduce设计** 下面给出一个设计图， [](http://images.cnblogs.com/cnblogs_com/LeftNotEasy/201202/201202182305036535.png) **简单的介绍一下** 1\. 首先用户程序(Client Program)提交了一个job，job的信息会发送到Job Tracker中，Job Tracker是Map-reduce框架的中心，他需要与集群中的机器定时通信(heartbeat), 需要管理哪些程序应该跑在哪些机器上，需要管理所有job失败、重启等操作。 2\. TaskTracker是Map-reduce集群中每台机器都有的一个部分，他做的事情主要是监视自己所在机器的资源情况（资源的表示是“本机还能起多少个map-task，多少个reduce-task”，每台机器起map/reduce task的上限是在建立集群的时候配置的），另外TaskTracker也会监视当前机器的tasks运行状况。 TaskTracker需要把这些信息通过heartbeat发送给JobTracker，JobTracker会搜集这些信息以给新提交的job分配运行在哪些机器上。上图回形针一样的箭头就是表示消息的发送-接收的过程。 够简单吧？当前的架构这么两句话就概括出来了，不过当你去看代码的时候，发现代码非常的难读，因为常常一个类3000多行，因为一个class做了太多的事情，这样会造成class的任务不清楚。另外，从我的理解来说，上面的设计至少有下面的几个问题， 1\. JobTracker是Map-reduce的单点，看起来多多少少让人不爽 2\. JobTracker完成了太多的任务，造成了过多的资源消耗，当map-reduce job非常多的时候，会造成很大的内存开销，潜在来说，也增加了很多JobTracker fail的风险 3\. 在TaskTracker端，以map/reduce task的数目作为资源的表示过于简单，没有考虑到cpu/内存的占用情况，如果两个大内存消耗的task被调度到了一块，很容易出现OOM 4\. 在TaskTracker端，把资源强制划分为map task slot和reduce task slot, 如果当系统中只有map task或者只有reduce task的时候，会造成资源的浪费，也就是前面提过的集群资源利用的问题 [](http://images.cnblogs.com/cnblogs_com/LeftNotEasy/201202/201202182305092494.png) 上面提到的4个问题，在Yarn中，除了第一个属于“部分完成”以外，其他的几个问题都已经解决掉了     ### 看看Map-reduce v2的设计: **[](http://images.cnblogs.com/cnblogs_com/LeftNotEasy/201202/201202182305188402.jpg)**** ** 首先User还是User，JobTracker和TaskTracker不见了，取而代之的是ResourceManager, Application Master与Node Manager三个部分。我详细的说一下。 首先Resource Manager是一个中心的服务，它做的事情是调度、启动每一个Job所属的ApplicationMaster、另外监控ApplicationMaster的存在情况。 细心的朋友已经发现少了点什么，对！Job里面所在的task的监控、重启等等内容不见了。这就是ApplicationMaster存在的原因。 上图中的MPI Mast(er)与MR Master就是某一个MPI Job或者MR Job的ApplicationMaster，一定要记住，ApplicationMaster是每一个Job（不是每一种）都有的一个部分，ApplicationMaster可以运行在ResourceManager以外的机器上。老的框架中，JobTracker一个很大的负担就是监控job下的tasks的运行状况，现在，这个部分就扔给ApplicationMaster做了，而ResourceManager中有一个模块叫做ApplicationsMaster，它是监测ApplicationMaster的运行状况，如果出问题，会将其在其他机器上重启。 设计优点一：这个设计大大减小了JobTracker（也就是现在的ResourceManager）的资源消耗，并且让监测每一个Job子任务(tasks)状态的程序分布式化了，更安全、更优美 另外，在新版中，ApplicationMaster是一个可变更的部分，用户可以对不同的编程模型写自己的ApplicationMaster，让更多类型的编程模型能够跑在Hadoop集群中。 设计优点二：能够支持不同的编程模型 设计优点三：对于资源的表示以内存为单位(在目前版本的Yarn中，没有考虑cpu的占用)，比之前以剩余slot数目更合理 设计优点四：既然资源表示成内存量，那就没有了之前的map slot/reduce slot分开造成集群资源闲置的尴尬情况了 [](http://images.cnblogs.com/cnblogs_com/LeftNotEasy/201202/201202182305206092.png) 其实在Yarn中还有很多优美的设计，之后慢慢再给大家说一下   ## 总结： 在Hadoop 0.23版中，就已经加入了Yarn，这个改变让Hadoop从单一的“黑虎掏心”变成了少林七十二绝学，学习了解Yarn也将是一个合格的hadooper的基本素质   ## 参考资料： 主要就是官方设计文档：[https://issues.apache.org/jira/secure/attachment/12486023/MapReduce_NextGen_Architecture.pdf](https://issues.apache.org/jira/secure/attachment/12486023/MapReduce_NextGen_Architecture.pdf)