大数据的广泛应用，着这样的背景下是值得我们研究与学习的。大数据分析机器学习算法实现的演化。首先，这里列出了目前可用的三代机器学习工具。

1. 传统的机器学习和数据分析的工具，包括SAS，IBM的SPSS，Weka以及R语言。它们可以在小数据集上进行深度分析——工具所运行的节点的内存可以容纳得下的数据集。
2. 第二代机器学习工具，包括Mahout，Pentaho，以及RapidMiner。它们可以对大数据进行我称之为粗浅的分析。基于Hadoop之上进行 的传统机器学习工具的规模化的尝试，包括Revolution Analytics的成果(RHadoop)以及Hadoop上的SAS，都可以归到第二代工具里面。
3. 第三代工具，比如Spark, Twister，HaLoop，Hama以及GraphLab。它们可以对大数据进行深度的分析。传统供应商最近的一些尝试包括SAS的内存分析，也属于这一类。

 
第一代机器学习工具/范式
由于第一代工具拥有大量的机器学习算法，因此它们适合进行深度的分析。然而，由于可扩展性的限制，它们并不都能在大数据集上进行工作——比如TB或者PB 级的数据（受限于这些工具本质上是非分布式的）。也就是说，它们可以进行垂直扩展（你可以提高工具运行的节点的处理能力），但无法进行水平扩展（它们并非 都能在集群上运行）。第一代工具的供应商通过建立Hadoop连接器以及提供集群选项来解决这些局限性——这意味着它们在努力对R或者SAS这样的工具进 行重新设计以便可以进行水平扩展。这些都应该归入第二代和第三代工具，下面我们将会介绍到。
 
第二代机器学习工具/范式
第二代工具（现在我们可以把传统的机器学习工具比如SAS这些称之为第一代工具了）比如 Mahout（http://mahout.apache.org），Rapidminer以及Pentaho，它们通过在开源的MapReduce产品 ——Hadoop之上实现相关算法，提供了扩展到大数据集上的能力。这些工具仍在快速完善并且是开源的（尤其是Mahout）。Mahout拥有一系列的 聚类及分类的算法，以及一个相当不错的推荐算法（Konstan和Riedl，2012）。因此它可以进行大数据的处理，现在在生产环境上已经有大量的使 用案例，主要用于推荐系统。我在一个线上系统中也使用Mahout来实现了一个金融领域的推荐算法，发现它确是可扩展的，尽管并不是一点问题没有（我还修 改了相当一部分代码）。
关于Mahou的一项评测发现它只实现了机器学习算法中的很小的一个子集——只有25个算法是达到了生产质量的，8到9个在 Hadoop之上可用，这意味着能在大数据集上进行扩展。这些算法包括线性回归，线性支持向量机，K-means聚类算法，等等。它通过并行训练，提供了 顺序逻辑回归的一个快速的实现。然而，正如别人指出的（比如Quora.com），它没有实现非线性支持向量机以及多变项逻辑回归（这也称为离散选择模 型）。
毕竟来说，本书并不是要为了抨击Mahout的。不过我认为有些机器学习算法的确是很难在Hadoop上实现，比如支持向量机的核函数以及共轭梯度法 （CGD，值得注意的是Mahout实现了一个随机梯度下降）。这一点别人也同样指出了，比方说可以看一下Srirama教授的一篇论文（Srirama 等人，2012年）。这里详细地比较了Hadoop和Twister MR（Ekanayake
等，2010年）在诸如共轭梯度法等迭代式算法上的不同，它指出，Hadoop上的开销非常明显。我所说的迭代式是指什么？一组执行特定计算的实体，在等待邻居或者其它实体的返回结果，然后再进行下一轮迭代。CGD是迭代式算法的最佳范例——每个CGD都可以分解成daxpy,ddot，matmul等原语。我会分别解释这三种原语都是什么：daxpy操作将向量x与常量k相乘，然后再和另一个向量y进行相加；ddot会计算两个向量x,y的点积;matmul将矩阵与向量相乘，然后返回另一个向量。
这意味着每个操作对应一个MapReduce操作，一次迭代会有6个MR操作，最终一次CG运算会有100个MR操作，以及数GB的数据交互，尽管这只是很小的矩阵。事实上，准备每次迭代的开销（包括从HDFS加载数据到内存的开销）比迭代运算本身的都大，这导致Hadoop上的MR会出现性能下降。相反，Twister会区分静态数据和可变数据，使得数据可以在MR迭代过程中常驻内存，同时还有一个合并阶段来收集reduce阶段输出的结果，因此性能有明显的提升。
第二代工具还有一些是传统工具基于Hadoop上进行的扩展。这类可供选择的有Revolution Analytics的产品，它是在Hadoop上对R语言进行了扩展，以及在Hadoop上实现R语言程序的一个可扩展的运行时环境（Venkataraman等，2012）。SAS的内存分析，作为SAS的高性能分析工具包中的一部分，是传统工具在Hadoop集群上进行规模化的另一个尝试。然而，最近发布的版本不仅能在Hadoop上运行，同时也支持Greenplum/Teradata，这应该算作是第三代机器学习的方法。
另一个有趣的产品是一家叫Concurrent Systems的初创公司实现的，它提供了一个预测模型标记语言（Predictive Modeling Markup Language，PMML）在Hadoop上的运行环境。PMML的模型有点类似XML，使得模型可以存储在描述性语言的文件中。传统工具比如 R以及SAS都可以将模型保存在PMML文件里。Hadoop上的运行环境使得它们可以将这些模型文件存储到一个Hadoop集群上，因此它们也属于第二代工具/范式。
 
第三代机器学习工具/范式
Hadoop自身的局限性以及它不太适合某类应用程序，这促进研究人员提出了新的替代方案。第三代工具主要是尝试超越Hadoop来进行不同维度的分析。我将会根据三种维度来讨论不同的实现方案，分别是机器学习算法，实时分析以及图像处理。
迭代式机器学习算法
伯克利大学的研究人员提出了一种替代方案：Spark（Zaharia等，2010年）——也就是说，在大数据领域，Spark被视为是替换Hadoop的下一代数据处理的解决方案。Spark有别于Hadoop的关键思想在于它的内存计算，这使得数据可以在不同的迭代和交互间缓存在内存里。研发Spark的主要原因是，常用的MR方法，只适用于那些可以表示成无环数据流的应用程序，并不适用于其它程序，比如那些在迭代中需要重用工作集的应用。
因此他们提出了这种新的集群计算的方法，它不仅能提供和MR类似的保证性和容错性，并且能同时支持迭代式及非迭代式应用。伯克利的研究人员提出了一套技术方案叫作BDAS，它可以在集群的不同节点间运行数据分析的任务。BDAS中最底层的组件叫做Mesos，这是个集群管理器，它会进行任务分配以及集群任务的资源管理。第二个组件是基于Mesos构建的Tachyon文件系统 。
Tachyon提供了一个分布式文件系统的抽象以及在集群间进行文件操作的接口。在实际的实施方案中，作为运算工具的Spark，是基于Tachyon和Mesos来实现的，尽管不用Tachyon，甚至是不用Mesos也可以实现。而在Spark基础上实现的Shark，则提供了集群层面的结构化查询 语言的抽象——这和Hive在Hadoop之上提供的抽象是一样的。Zacharia等人在他们的文章中对Spark进行了探索，这是实现机器学习算法的重要组成部分。
HaLoop（Bu等人，2010）也扩展了Hadoop来实现机器学习算法——它不仅为迭代式应用的表示提供了一层编程抽象，同时还使用了缓存的概念来 进行迭代间的数据共享，以及对定点进行校验，从而提高了效率。Twister( http://iterativemapreduce.org )是类似HaLoop的一个产品。
 
实时分析
实时分析是超越Hadoop考虑的第二个维度。来自Twitter的Storm（感觉原文说反了）是这一领域的最有力的竞争者。Storm是一个可扩展的复杂事件处理引擎，它使得基于事件流的实时复杂运算成为了可能。一个Storm集群的组件包括：  Spout，用于从不同的数据源中读取数据。有HDFS类型的spout，Kafka类型的spout，以及TCP流的spout。
 
Bolt，它用于数据处理。它们在流上进行运算。基于流的机器学习算法通常都在这里运行。
拓扑。这是具体应用特定的spout和bolt的一个整合——拓扑运行于集群的节点上。
在实践中，一个架构如果同时包含了Kafka（来自LinkedIn的一个分布式队列系统）集群来作为高速的数据提取器，以及Storm集群来进行处理或 者分析，它的表现会非常不错，Kafka spout用来快速地从Kafka集群中读取数据。Kafka集群将事件存储在队列中。由于Storm集群正忙于进行机器学习，因此这么做是很有必要 的。
本书的后续章节将会对这个架构进行详细的介绍，以及在Storm集群中运行机器学习算法所需的步骤。Storm也被拿来跟实时计算领域的其它竞争者进 行比较，包括Yahoo的S4以及Typesafe的Akka。

中国古代《周髀算经》卷上有：“数之法出于圆方。圆出于方，方出于矩。矩出于九九八十一”。意思是： 算数的方法都出于对圆、对方的计算，其中圆出于方(圆形面积=外接正方形x圆周率/4)，方出于矩(正方形源自两边相等的矩)，矩的计算出于九九八十一 (长乘宽面积的计算依自九九乘法表)。在西方，真正推动算法传播的是一个居住在巴格达的阿拉伯人，Al Khwarizmi，他引进了印度更为先进的十进制数字系统。Al Khawarizmi展示了加、减、乘、除，乃至平方根和圆周率π的计算步骤。那么，我们为什么要思考算法？
 
算法的定义
究竟什么是算法呢，字面理解，就是计算的办法或法则。这里的计算不单指加减乘除等算术运算，而是广义的做任何事情的计算。办法和法则，则意味着使用它可以解决眼前的问题。
就拿我们喜闻乐见的世界杯比赛来说，每四年一届比赛的目的就是选出此时世界上踢球最牛掰的那个国家。在200多个国家里头，如果用单循环联赛赛制，也就是每个队都必须和另外所有队踢一场，以此决定本队成绩，假设每隔三天踢一场，最快也要600来天。怎么样，累觉不爱吧，还是广场舞来的更收放自如些。对于比赛组织者来说，明智的策略当然是先在几个大洲里选出几个屈指可数的球队，然后大家聚在一起，一个月内论出高下，这时甚至还要再分成几个组，每组最强的几个队才能突出重围，踏上冠军之路。
道理上来讲，最好的球队，无论哪种赛制，总是会脱颖而出的；而上述这种优中选优的方式，难度和开销就降低许多了。上述过程有一个特定叫法：分治，也就是将一个大问题（寻找全世界的最佳球队），分解成多个类型相同但规模更小的问题（寻找一个大洲的最佳球队），如果小问题得以解决，那么大问题就更加容易解决了（各大洲最佳球队PK一下，就知道世界冠军的奖杯，花落谁家了）。这只是生活中众多算法应用的一个例子，那么由事实到抽象拔高出来一个完备的字典式定义，对应用和分析者来说，其实无太多必要。事实上，算法的定义也因看待的角度不同而不同。
如果你是个哲学家：算法是解决一个问题的抽象行为序列。
如果你是个码农：算法是一个计算过程，它接受一些输入，并产生某些输出。
如果你喜欢高大上：算法是解决一个精确定义的计算问题的工具。
但他们共同强调了一点：算法的不变式，即算法必须能够让人一步一步照着执行。
 
算法的核心
算法是解决问题的办法或法则。但解决一个问题不一定只有一种办法，不同的办法之间便有了好坏之分。对于解决同一个问题的不同算法，我们如何比较它们的好坏呢？
能够比较的东西当然很多，如模块性、正确性、可维护性、健壮性、友好性、简易性、可扩展性和可靠性等，但这些并不是算法设计与分析中最为关心的问题。但它们更加像是人类附加在算法上的外部属性，因为它们通常依赖于使用或实现算法的人员的其他方面素质：理解力、表述力、编程水平、数据结构的运用与设计技巧等。
那么算法的核心或灵魂是什么呢？也许您已经可以猜到：速度。也就是其解决问题的速度。因为速度往往是区分可行和不可行方案的分水岭。例如，一个让人等上很多年才能运行结束的算法，就是再正确，也不会令我们满意。从实际意义上看，这种算法的正确和不正确并无太大的本质区别。
如果一个算法在你的改进下，效率提高了成百上千倍，则当你坐在显示屏前，所获得的快感不会亚于很多其他的事情。
 
堆机器还是拼算法
说到提升速度，真壕们会不约而同的移步华强北，血拼内存处理器。然而，计算机速度的增长可以多大程度上解决一些简单问题呢？我们来看一个经典的例子吧。
我们有一个描述兔子增长数量的模型：
原点：一对雌雄兔子
规律：每对兔子每月产下一对兔子，且一生只能生产两次，而且第二次生产后老死。（我们这里假设产下的每对兔子都继续正常繁衍，方舟子及果壳知识帝请绕路……）
如果定义在第n个月的兔子数量为F(n)，那么F(n)个兔子中包含这个月新生的兔子（也就是（第n-1月）兔子总数F(n-1)），和上个月的新生兔子数目（因为上个月的老兔子们这个月已经死掉了），即F(n-2)。所以F(n)=F(n-1)+F(n-2)，F(n)的序列叫做斐波那契序列。
那么我们就开始算F(n)吧，比如说你想知道第30个月时的兔子数量，那么F(30)=F(29)+F(28)，那么F(29)=F(28)+F(27)，我们一直分解下去，最后变成数数一共多少个F(0)了。我们写段代码，运行它，约朋友出去打个台球，回来也许可以得到答案。若你眼光长远，想知道第300个月时的兔子数量，那么你必须要寻找其它算法了。因为F(0)的数量太庞大了。这种天真递归解法，事实上要对F(0)进行指数级次的运算。聪明的你会进一步发现斐波那契数列是一个二阶递推数列，于是最后可以用对数级次运算搞定F(300)，这里细节省略，感兴趣的话我们会在后续详细讨论。
问题是，在硬件性能愈加强悍的今天，大规模运算或者大数据的实践者们，时常认为更快的算法也许没有必要。那么我们来看斐波那契数的天真递归解法，它的时间复杂度为1.6的n次方，即计算F(n+1)的时间约是计算F(n)的1.6倍。按照摩尔定律计算性能每18个月翻倍的速度，每过一年，我们只能多计算一个未知的斐波那契数。
我们说IBM的Roadrunner 超级计算机性能为NEC的Earth Simulator的30倍，但这也仅仅意味着Roadrunner比后者在同样的时间下以指数级复杂度多算7个数。但如果使用log(n)复杂度的算法，那么Roadrunner可多算10的30次方个斐波那契数。
所以，算法书其实不全是用来垫咖啡杯的……改进算法比起提升硬件速度的效果，还是很显著的，不是吗。

KMeans算法和简单命令使用 
算法简介
 同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小
 以空间中k个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。
 首先从n个数据对象任意选择 k个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。
 对于每一个 cluster，我们可以选出一个中心点 (center)，使得该 cluster中的所有的点到该中心点的距离小于到其他 cluster的中心的距离
 
建立文件 
https://cwiki.apache.org/confluence/display/MAHOUT/Clustering+of+synthetic+control+data
下载数据集synthetic_control.data，在以上官网上的Input data set. Download it here点击可下载
把里面的内容复制到了testdata文件上并放在了/root/input目录下
转换成seq文件 
 
首先简单说明下，mahout下处理的文件必须是SequenceFile格式的，所以需要把txtfile转换成sequenceFile。SequenceFile是hadoop中的一个类，允许我们向文件中写入二进制的键值对，具体介绍请看eyjian写的http://www.hadoopor.com/viewthread.php?tid=144&highlight=sequencefile
输入命令: mahout seqdirectory --input /root/input/ --output /root/input/ --charset UTF-8

可以看到在input目录下多了2个文件， 这就是我们要的SequenceFile格式文件
把文件导入到分布式文件系统上
hadoop fs -mkdir testdata  在hadoop下建立testdata文件
 hadoop fs -put /root/input/kmeans.data/  testdata testdata 把kmean.data放到HDFS上
我们可以看到：
执行使用k-means算法
 
 
输入命令：mahoutorg.apache.mahout.clustering.syntheticcontrol.kmeans.Job
 
出现错误：
Exception in thread "main" org.apache.hadoop.mapreduce.lib.input.InvalidInputException:Input path does not exist: file:/root/testdata
 
解决：
考虑可能是默认目录为root/testdata
所以cd到input文件名字改成testdata后重新运行命令：mahout org.apache.mahout.clustering.syntheticcontrol.kmeans.Job
后运行成功：  

 
如果是在本地执行的话算法执行完之后在input目录下可以找到output，hadoop集群的话就从hdfs上面导出

数据输入格式
测试数据
 
 
 
 
每个数据和数据之间用空格分开，数据都是double型的
Kmean算法在每次取数据时对所有的数据只取其中的一列
 
kmeans命令使用：
mahout kmeans \
 -i \ 输入目录
 -c \输入的簇目录
 -o

\输出目录
 -k \
 -dm \路径方法的类名，默认是SquaredEuclidean   
-x \迭代的次数
-cd \delta的值
-ow 如果存在覆盖输出目录
-cl 在运行Canopy算法后运行输入向量簇
-xm 用sequential或者mapreduce运行
注意：当-k被指定的时候，-c目录下的所有聚类都将被重写，将从输入的数据向量中随机抽取-k个点作为初始聚类的中心。
 查看结果
 
mahout seqdumper：将SequenceFile文件转成可读的文本形式，对应的源文件是org.apache.mahout.utils.SequenceFileDumper.java
mahout vectordump：将向量文件转成可读的文本形式，对应的源文件是org.apache.mahout.utils.vectors.VectorDumper.java
mahout clusterdump：分析最后聚类的输出结果，对应的源文件是org.apache.mahout.utils.clustering.ClusterDumper.java
 
例如我的文件输出在/root/input/output，我可以
输入命令：mahout seqdumper -s /root/input/output/clusteredPoints/part-m-00000
来查看point
mahout clusterdump --seqFileDir /root/input/output/clusteredPoints/part-m-00000

如果直接在本地打开是会有乱码的
出现问题：但目前我还不知道如何输出到本地上，-o命令总是报错，目前只会在console上观察结果
解决：例如要输出上述的point文件，可以使用命令：mahout seqdumper -s /root/input/output/clusteredPoints/part-m-00000 -o result.txt

 
 运行结果分析
 
首先Kmeans算法默认是10次迭代，所以我们得到的clusters是10个
结果文件夹有clusteredPoints，clusters-N，data，用命令mahout seqdumper仔细看了一下结果文件
 
clusteredPoints：存放的是最后聚类的结果，将cluster-id和documents-id都展示出来了，用mahout seqdumper读clusteredPoints结果的key-value类型是(IntWritable,WeightedVectorWritable)
例如之前的/root/input/output/clusteredPoints/part-m-00000文件

 
 
clusters-N：是第N次聚类的结果，其中n为某类的样本数目，c为各类各属性的中心，r为各类属性的半径。 clusters-N结果类型是(Text,Cluster)
例如要观察clusters-10的内容，可以使用命令：
mahout seqdumper -s /root/input/output/clusters-10/part-r-00000
要输出到txt文件则要在后面加上：-o xxxx.txt(xxxx是文件名)

data：存放的是原始数据，这个文件夹下的文件可以用mahout vectordump来读取，原始数据是向量形式的，其它的都只能用mahout seqdumper来读取，向量文件也可以用mahout seqdumper来读取，只是用vectordump读取出来的是数字结果，没有对应的key，用seqdumper读出来的可以看到key，即对应的url，而value读出来的是一个类描述，而不是数组向量
例如要查看data下的文件用命令：
mahout vectordump -s /root/input/output/data/part-m-00000/    
同样的要输出的话在后面加上 –o  xxxx.txt

 适用场景展望
 
对于像kmeans这样的聚类算法都是用来求相似度的，如果想要得到某些数据的在某些条件下的相似程度就可以用kmean算法，它可以帮助总结出一些数据规律。比如：在所有女人当中打市内电话的数据，如果按通话时间分的话就可以用kmeans算法，分成时间长的会形成一个簇，时间短的也会形成一个簇。
 
但是对例外和噪声文本比较敏感。另外一个问题是，没有一个好的办法确定k的取值。

mahout bayes（贝叶斯）算法研究
接前面的mahout-bayes（贝叶斯）算法研究（1）
9.输出数据含义分析与研究 
 
这个混合矩阵的意思说明： 
上述a到u分别是代表了有20类别，这就是我们之前给的20个输入文件                                                                                                            
列中的数据说明每个类别中被分配到的字节个数，classified说明应该被分配到的总数
381 0   0   0   0   9   1   0   0   0   1   0   0   2   0   1   0   0   3   0   0    |  398  a     = rec.motorcycles
意思为rec.motorcycles 本来是属于 a，有381篇文档被划为了a类，这个是正确的数据，其它的分别表示划到b~u类中的数目。我们可以看到其正确率为  381/398=0.95728643216080402010050251256281 ,可见其正确率还是很高的了。
 
 
10.输入数据格式分析研究
 
就像案例一样：需要输入的内容是文本分类和模型使用              
在train中添加特征类型数据
在test中添加测试数据
 
Train的输入格式，第一个字符时类标签，剩余的是特征（单词），标签和特征词用table键隔开，如下面的格式：

比如在20newsgroup这个例子中的文件中

alt.atheism是类标签，剩下的是特征。其他的类似11.如何将业务数据转换成对应的输入数据
 
假设我们要通过某一些关键词来确定这个账单是最可能属于谁的
 
账单1

 账单2

当特征值选取

时
Result

 
 
在zhangdan2中一共3条记录，有2条被收录到b（zhangdan1）中，有1条被收录到a（zhangdan2）
满足条件：字段：shanghai和zhangchun都在zhangdan1中满足2条
          字段：beijing在zhangdan2中满足1条
所以该文档更可能属于zhangdan1
 
测试可能不够全面只是为了了解大致了解
 12.如何将结果提取并应用
 
 
看这条输出：
a列代表数据在a中的符合条数（即可能有386个在a），所以a被归类在comp.graphics的可能性很高
所以可能通过这样的数据来判断数据可能被归类到哪里
13.适用场景展望
 
该算法可能用来处理大规模数据的分类，特征值选取越准确，正确率越高，算法简单容易理解，但在单机上的实验运行速度较慢。

mahout bayes（贝叶斯）算法研究
朴素贝叶斯分类是一种十分简单的分类算法，叫它朴素贝叶斯分类是因为这种方法的思想真的很朴素，朴素贝叶斯的思想基础是这样的：对于给出的待分类项，求解在此项出现的条件下各个类别出现的概率哪个最大，就认为此待分类项属于哪个类别。
这二十个新闻组数据集合是收集大约20,000新闻组文档，均匀的分布在20个不同的集合。这20个新闻组集合采集最近流行的数据集合到文本程序中作为实验，根据机器学习技术。例如文本分类，文本聚集。我们将使用Mahout的Bayes Classifier创造一个模型，它将一个新文档分类到这20个新闻组集合范例演示
2.环境要求
 
hadoop已经开启
mahout已经安装
 3.数据的准备
 
下载20news-bydate.tar.gz数据包并解压缩
http://people.csail.mit.edu/jrennie/20Newsgroups/20news-bydate.tar.gz
例如：我已经把数据包放在/root/bayes下了，所以以下的命令都是在这个目录下的

 
 
原以为这么20个文件是不可以一起输出的，但事实证明是可以的
 
 4.算法流程
5.数据输入与输出准备过程5.1生成input的数据
mahout org.apache.mahout.classifier.bayes.PrepareTwentyNewsgroups -p/root/bayes/20news-bydate-train -o /root/bayesoutput/train -a org.apache.mahout.vectorizer.DefaultAnalyzer -c UTF-8
5.2生成test的数据
 
mahout org.apache.mahout.classifier.bayes.PrepareTwentyNewsgroups -p/root/bayes/20news-bydate-test -o /root/bayesoutput/test -a org.apache.mahout.vectorizer.DefaultAnalyzer -c UTF-8
5.2生成test的数据
 
mahout org.apache.mahout.classifier.bayes.PrepareTwentyNewsgroups -p/root/bayes/20news-bydate-test -o /root/bayesoutput/test -a org.apache.mahout.vectorizer.DefaultAnalyzer -c UTF-8
5.2生成test的数据
mahout org.apache.mahout.classifier.bayes.PrepareTwentyNewsgroups -p/root/bayes/20news-bydate-test -o /root/bayesoutput/test -a org.apache.mahout.vectorizer.DefaultAnalyzer -c UTF-8

步骤1:下载测试数据(格式为SGML):
http://www.daviddlewis.com/resou ... reuters21578.tar.gz

步骤2:将数据解压
$ mkdir -p mahout-work/reuters-sgm
$ cd mahout-work/reuters-sgm && tar xzf ../reuters21578.tar.gz && cd .. && cd ..

步骤3:将SGML格式数据转化为文本文件
$ bin/mahout org.apache.lucene.benchmark.utils.ExtractReuters mahout-work/reuters-sgm mahout-work/reuters-out

步骤4:将数据转化为SequenceFile格式
$ bin/mahout seqdirectory \
    -i mahout-work/reuters-out \
    -o mahout-work/reuters-out-seqdir \
    -c UTF-8 -chunk 5

步骤5:创建向量和Sequence文件
$ bin/mahout seq2sparse
    -i mahout-work/reuters-out-seqdir \
    -o mahout-work/reuters-out-seqdir-sparse-kmeans

步骤6: 运行K-means
$ bin/mahout kmeans \
    -i mahout-work/reuters-out-seqdir-sparse-kmeans/tfidf-vectors/ \
    -c mahout-work/reuters-kmeans-clusters \
    -o mahout-work/reuters-kmeans \
    -dm org.apache.mahout.common.distance.CosineDistanceMeasure –cd 0.1 \
    -x 10 -k 20 –ow

 Mahout是Apache下的开源机器学习软件包，目前实现的机器学习算法主要包含有协同过滤/推荐引擎，聚类和分类三个部分。Mahout从设计开始就旨在建立可扩展的机器学习软件包，用于处理大数据机器学习的问题，当你正在研究的数据量大到不能在一台机器上运行时，就可以选择使用Mahout，让你的数据在Hadoop集群的进行分析。Mahout某些部分的实现直接创建在Hadoop之上，这就使得其具有进行大数据处理的能力，也是Mahout最大的优势所在。相比较于Weka，RapidMiner等图形化的机器学习软件，Mahout只提供机器学习的程序包
（library），不提供用户图形界面，并且Mahout并不包含所有的机器学习算法实现，这一点可以算得上是她的一个劣势，但前面提到过Mahout并不是“又一个机器学习软件”，而是要成为一个“可扩展的用于处理大数据的机器学习软件”，但是我相信会有越来越多的机器学习算法会在Mahout上面实现。[1]
 
    二、介绍K-Means
    https://cwiki.apache.org/confluence/display/MAHOUT/K-Means+Clustering#，这是Apache官网上的算法描述，简单来说就是基于划分的聚类算法，把n个对象分为k个簇，以使簇内具有较高的相似度。相似度的计算根据一个簇中对象的平均值来进行。[2]    三、在Hadoop上实现运行    1，实验环境
        ①hadoop集群环境：1.2.1 一个Master，两个Slaves，在开始运行kmeans时启动hadoop
        ②操作系统：所有机器的系统均为ubuntu12.04
        ③Mahout版本：采用的是0.5版    2，数据准备
        数据采用的是http://archive.ics.uci.edu/ml/databases/synthetic_control/synthetic_control.data，这是网上提供的一个比较不错是数据源。然后用指令 hadoop fs -put /home/hadoop/Desktop/data testdata，将在我桌面的文件data上传到HDFS的testdata目录下，这里为什么是testdata，我也正在思考，因为我本来是上传到input里，但是运行时提示could not find ….user/testdata之类的，所以现改为了testdata。    3，运行
        ①配置Mahout环境：在Apache官网下载Mahout的版本，我选择的是0.5，下载地址：https://cwiki.apache.org/confluence/display/MAHOUT/Downloads。然后解压到你指定的目录，将此目录路径写入/etc/profile，添加如下语句：
export MAHOUT_HOME=/home/hadoop/hadoop-1.2.1/mahout-distribution-0.5
export HADOOP_CONF_DIR=/home/hadoop/hadoop-1.2.1/conf
export PATH=$PATH:/home/hadoop/hadoop-1.2.1/binMAHOUT_HOME/bin
然后执行 source /etc/profile。在mahout目录下执行bin/mahout命令，检测系统是否安装成功。
注：此处修改环境变量有些网上提示是/etc/bash.bashrc，我也试着修改过，但是发现在我这里使环境变量生效的是profile。
②运行Mahout里自带的K-Means算法，bin/mahout org.apache.mahout.clustering.syntheticcontrol.kmeans.Job，这里启动后遇到了一点问题，提示Could not find math.vector，后来参考这篇http://jerrylead.iteye.com/blog/1188929日志解决。
    4，结果
       在我的环境下运行5分钟左右，最后生成一个文件
   四、总结
Mahout是一个很强大的数据挖掘工具，需要进行更深层的了解。

摘要： 贝叶斯分类器的分类原理发源于古典概率理论，是通过某对象的先验概率，利用贝叶斯公式计算出其后验概率，即该对象属于某一类的概率，选择具有最大后验概率 的类作为该对象所属的类。朴素贝叶斯分类器(Naive Bayes Classifier)做了一个简单的假定：给定目标值时属性之间相互条件独立，即给定元组的类标号，假定属性值有条件地相互独立，即在属性间不存在依赖 关系。朴素贝叶斯分类模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。
一.简介
      贝叶斯分类器的分类原理发源于古典概率理论，是通过某对象的先验概率，利用贝叶斯公式计算出其后验概率，即该对象属于某一类的概率，选择具有最大后验概率 的类作为该对象所属的类。朴素贝叶斯分类器(Naive Bayes Classifier)做了一个简单的假定：给定目标值时属性之间相互条件独立，即给定元组的类标号，假定属性值有条件地相互独立，即在属性间不存在依赖 关系。朴素贝叶斯分类模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。
      Mahout 实现了Traditional Naive Bayes 和Complementary Naive Bayes，后者是在前者的基础上增加了结果分析功能(Result Analyzer).
      主要相关的Mahout类:
      org.apache.mahout.classifier.naivebayes.NaiveBayesModel
      org.apache.mahout.classifier.naivebayes.StandardNaiveBayesClassifier
      org.apache.mahout.classifier.naivebayes.ComplementaryNaiveBayesClassifier

二.数据
      使用20 newsgroups data (http://people.csail.mit.edu/jren ... 0news-bydate.tar.gz) ，数据集按时间分为训练数据和测试数据，总大小约为85MB，每个数据文件为一条信息，文件头部几行指定消息的发送者、长度、类型、使用软件，以及主题 等，然后用空行将期与正文隔开，正文没有固定的格式。

三.目标
      根据新闻文档内容，将其分到不同的文档类型中。

四.程序
      使用Mahout自带示例程序，主要的训练类和测试类分别为TrainNaiveBayesJob.java和 TestNaiveBayesDriver.java，JAR包为mahout-core-0.7-job.jar，详细代码见(mahout- distribution-0.7/core/src/main/java/org/apache/mahout/classifier/naivebayes/trainning,mahout-distribution-0.7/core/src/main/java/org/apache/mahout/classifier/naivebayes/test).

五.步骤
      1. 数据准备
      a.将20news-bydate.tar.gz解压，并将20news-bydate中的所有子文夹中的内容复制到20news-all中，该步骤已经完成，20news-all文件夹存放在hdfs:/share/data/ Mahout_examples_Data_Set中
      b.将20news-all放在hdfs的用户根目录下
      $  hadoop dfs -cp /share/data/Mahout_examples_Data_Set/20news-all .
      c.从20newsgroups data创建序列文件(sequence files)
      $  mahout seqdirectory -i 20news-all -o 20news-seq
      d.将序列文件转化为向量
      $  mahout seq2sparse -i ./20news-seq -o ./20news-vectors  -lnorm -nv  -wt tfidf
      e.将向量数据集分为训练数据和检测数据，以随机40-60拆分
     $  mahout split -i ./20news-vectors/tfidf-vectors 
                         --trainingOutput ./20news-train-vectors 
                         --testOutput ./20news-test-vectors 
                         --randomSelectionPct 40 --overwrite 
                         --sequenceFiles -xm sequential
      2.训练朴素贝叶斯模型
      $  mahout trainnb -i  ./20news-train-vectors -el -o ./model 
                           -li ./labelindex -ow -c
      3.检验朴素贝叶斯模型
    $  mahout testnb -i ./20news-train-vectors -m ./model 
                   -l ./labelindex -ow -o 20news-testing -c 
      4.检测模型分类效果
      $  mahout testnb -i ./20news-test-vectors -m ./model 
              -l ./labelindex -ow -o ./20news-testing -c
      5.查看结果，将序列文件转化为文本
      $  mahout seqdumper -i ./20news-testing/part-m-00000 -o ./20news_testing.res 
      $ download 20news_testing.res
      $  cat 20news_testing.res 

现有n片不同种类的树叶，编写程序，完成对它们的自动分类。采用基于K-means算法的方法来完成分类。
       K-means算法的处理流程如下。首先，随机或按一定规则选择k个对象，每个对象代表一个簇的初始均值或中心。对剩余的每个对象，根据其与各个簇均值的距离，将它指派到与之最相近的簇中。然后计算每个簇新的均值。不断重复这个过程，直到数据的划分不再发生变化。
      整个分类算法的伪代码：

01
input:n //样本数
02
      k //欲分类数
03
      mrows //行像素
04
      ncols //列像素
05
for i=1 to n
06
      读取图片i;
07
      改变图片i的像素数为mrows*ncols；
08
      将真彩图像转换为灰度图;
09
      将像素矩阵转换为行向量leafs(i);
10
end;
11
调用K-means算法对leafs矩阵进行自动聚类；
12
返回聚类结果；
13
end;
        Matlab源代码：
01
function idx=kmean( )
02
n=input('输入样本总数n：   ');
03
k=input('输入要分成的类数k：   ');
04
mrows=input('输入行像素mrows:     ');
05
ncols=input('输入行像素ncols:     ');
06
leaf=cell(1,n);
07
leafs=rand(n,mrows*ncols);
08
for i=1:n
09
    imageName=strcat(num2str(i),'.jpg'); %图片名为1.jpg,2.jpg……n.jpg
10
    leaf{i}=imread(imageName); %读取图片
11
    leaf{i}=imresize(leaf{i},[mrows,ncols]); %统一图片的像素数
12
    leaf{i}=rgb2gray(leaf{i}); %真彩图转为灰度图
13
    leafs(i,=reshape(leaf{i},1,mrows*ncols); %将矩阵转成向量，所有向量统一保存在leafs矩阵中
14
end
15
idx=kmeans(leafs,k);%调用kmeans函数，返回分类结果
16
end
实验样本（n=12,k=5）：


由实验结果可见，分类效果基本令人满意。

不足与改进：

1．K-means算法需要用户首先确定k值，确定不恰当的k值将使得分类效果较差。K-means算法是一种典型的划分聚类方法，聚类结果可以用层次聚类方法作为验证，层次聚类方法具有自底向上、逐步聚类的优点，两相结合，可以取得令人满意的聚类结果。

2.K-means算法初始化采用随机取点的方法，可能会使算法产生收敛到局部最优而难以发现全局最优。可以采用模拟退火算法与K-means算法的结合来解决此问题[2]。

        3.K-means算法对于孤立点数据或噪声数据是敏感的，少量的该类数据能够对平均值产生较大的影响。在处理有孤立点或噪声的数据时，可采用K-medoids算法，该算法采用簇中最接近簇均值的点来表示簇，更具有鲁棒性。

本文讲一下mahout中kmeans算法和Canopy算法实现原理。
 
一. Kmeans是一个很经典的聚类算法，我想大家都非常熟悉。虽然算法较为简单，在实际应用中却可以有不错的效果；其算法原理也决定了其比较容易实现并行化。
学习mahout就先从简单的kmeans算法开始学起，就当抛砖引玉了。
1. 首先来简单的回顾一下KMeans算法：
 
(1)   根据事先给定的k值建立初始划分，得到k个Cluster，比如，可以随机选择k个点作为k个Cluster的重心，又或者用其他算法得到的Cluster作为初始重心；
(2)、计算每个点到各个Cluster重心的距离，将它加入到最近的那个Cluster；
(3)、重新计算每个Cluster的重心；
(4)、重复过程2~3，直到各个Cluster重心在某个精度范围内不变化或者达到最大迭代次数；
 
其时间复杂度是：O(nkt)，其中：n是聚类点个数，k是Cluster个数，t是迭代次数。容易并行化，
kmeans缺点是：对孤立点敏感，K值难以估计
 
2. kmeans的算法思想决定了其实现并行化还是比较容易的，主要是在迭代中计算某个点属于哪一个新的聚类中心的过程是可以并行化的。
 
主要分成以下几个步骤：
（1）datanode在map阶段读出位于本地的数据集，并且从HDFS中读到上一次聚类后的聚类中心（从cluster-N-1的目录中），计算并输出每个点及其对应的Cluster；
（2）combiner操作对位于本地包含在相同Cluster中的点进行reduce操作并输出，
（3）reduce操作得到全局Cluster集合并写入HDFS的指定目录(cluster-N)。
 
Kmeans每一轮迭代会生成新的全局聚类中心，这个聚类中心在下一次迭代的时候是会使用到的，所以每一轮迭代（实际上每一轮迭代是一个新mapreduce job）之后，reduce任务会负责将此次的聚类中心输出到集群中。命名是以cluster加上迭代次数命名的。为：Cluster-N
 
由于每次迭代是起了一个job，mahout中有一个KMeansDriver的类来对整个过程进行控制。抽象过程。最后，当获得了稳定的全局聚类中心后，简单的想想就能知道，只要用一个Map过程就可以实现对全体数据的分类。具体流程如下图：

二. 在开始的时候说过，Kmeans算法收初始点的影响较大，如果起始点是一个孤立点是一个很麻烦的事情。解决的办法是先对数据集进行一个较为“粗”的聚类算法。目的是对全体数据集进行一个大致的分组过程，然后这些组为单位选取Kmeans的初始聚类中心点，这样初始点的选择就不至于因为随即而偏离的太远。Mahout里面是使用Canopy算法来实现这一初始聚类过程的，当然mahout中也会提供随机选取初始中心点的方法，用的是RandomSeedGenerator类。（运行mahout kMeans时会默认选择Canopy算法作为聚类中心选择的初始算法，但当你提供-k参数，即指明有几个聚类中心时，则会选择随机的方式生成初始中心点）
 
1. Canopy算法其实本身也可以用于聚类，但它的结果可以为之后代价较高聚类提供帮助，其用在数据预处理上要比单纯拿来聚类更有帮助；
Canopy算法的步骤如下:
（1） 将所有数据放进list中，选择两个距离，T1，T2，T1>T2
（2）While(list不为空)
 { 
随机选择一个节点做canopy的中心；并从list删除该点；
遍历list：
对于任何一条记录，计算其到各个canopy的距离；
如果距离 如果距离 如果到任何canopy中心的聚类都>T1,那么将这条记录作为一个新的canopy的中心，并从list中删除这个元素；
}
 
同样，Canopy算法的实现也比较简单，其使用T1和T2两个距离来实现对数据集的一个粗略的划分，表现为最终会生成几个Canopy下面举一个例子。
8.1,8.1  
7.1,7.1  
6.2,6.2  
7.1,7.1  
2.1,2.1  
1.1,1.1  
0.1,0.1  
3.0,3.0  
一共有8个二维的点，为了计算简便，我们选择曼哈顿距离作为距离的量度，即|x1 – x2| + |y1 – y2|。选取T1=8，T2=4。mahout里面是可以为Kmeans算法设置不同的距离计算方法的，如欧式距离，向量夹角，曼哈顿距离，雅克比系数等。
首先选取(8.1, 8.1)作为第一个Canopy的中心，并从list中删除这个点。
然后开始遍历整个list。
第二个点(7.1,7.1)
距离Canopy 1 (8.1,8.1)的距离是2，2 第三个点(6.2,6.2)
距离Canopy 1 (8.1,8.1)的距离是3.8，3.8 第四个点(7.1,7.1)与第一个点是相同的。
第五个点(2.1,2.1)
其余Canopy 1的距离是12，大于T1，所以第五个点不属于任何Canopy，新生成一个Canopy，其中心是(2.1,2.1)，并从list中删除该点，因为这个点不会属于其他Canopy了。
第六个点(1.1,1.1)
到Canopy 1 (8.1,8.1)的距离是14，14> T1，到Canopy 2(2.1,2.1)的距离是2，2 第七个点(0.1,0.1 )
到Canopy 1 (8.1,8.1)的距离是16，16> T1，到Canopy 2(2.1,2.1)的距离是4，4=T2，所以将第七个点打上属于Canopy 2(2.1,2.1)的弱标记，但并不从集群中删除该点；
第八个点(3.0,3.0)
到Canopy 1 (8.1,8.1)的距离是10.2，10.2> T1，到Canopy 2(2.1,2.1)的距离是1.8，1.8 此时所有Canopy的状态是：
Canopy 1 (8.1,8.1) :[ (8.1,8.1),  (7.1,7.1),  (6.2,6.2) ,(7.1,7.1) ]
Canopy 2 (2.1,2.1) :[ (2.1,2.1), (1.1,1.1) ,(0.1,0.1),  (3.0,3.0)  ]
并且算法的第一词While循环已经跑过，此时list中还剩下的元素是(0.1,0.1)
将他自己作为一个新的Canopy，Canopy 3(0.1,0.1)，集群中Canopy的最后状态是
Canopy 1 (8.1,8.1) :[ (8.1,8.1),  (7.1,7.1),  (6.2,6.2) ,(7.1,7.1) ]
Canopy 2 (2.1,2.1) :[ (2.1,2.1), (1.1,1.1) ,(0.1,0.1),  (3.0,3.0)  ]
Canopy 3 (0.1,0.1) :[ (0.1,0.1)]
所以最终的Canopy聚类中心是(7.125,7.125)，(1.575,1.575)，(0.1,0.1)
 
2. Canopy算法的并行化:
Canopy算法的并行点也是比较明显的，即生成Canopy的过程可以并行，
（1）  各个mapper可以依据存储在本地的数据，各自在本地用上述算法生成若干Canopy；（2）  reducer将这些Canopy用相同算法汇总后计算出最终的Canopy集合；
下图可以较好的反应并行化的过程：

举个例子，我们只有两个map任务：
第一个map的数据是
8.1,8.1  
7.1,7.1  
6.2,6.2  
7.1,7.1  
2.1,2.1  
1.1,1.1  
0.1,0.1  
3.0,3.0  
根据上文的计算，我们得到其Canopy中心是(7.125,7.125)，(1.575,1.575)，(0.1,0.1)
那么第一个map的数据就是(7.125,7.125)，(1.575,1.575)，(0.1,0.1)
 
第二个map的数据是
8,8  
7,7  
6.1,6.1  
9,9  
2,2  
1,1  
0,0  
2.9,2.9
运用Canopy算法我们可以到，其Canopy中心是(7.525,7.525)，(1.475,1.475)，(1.45,1.45)
第二个map的输出数据就是(7.525,7.525)，(1.475,1.475)，(1.45,1.45)
 
那么Reduce中获得数据就是(7.125,7.125)，(1.575,1.575)，(0.1,0.1)，(7.525,7.525)，(1.475,1.475)，(1.45,1.45)
Reduce任务会用Canopy算法对这个六个点进行Canopy划分。从而得到全局的Canopy中心。

来做一些遥感图像自动解译的工作，需要根据遥感图像每个单元（像元，像素）的几个波段值和相互之间的位置关系来进行自动分类，也就是确定哪些区域是耕地，哪些是林地，哪些是草地。之前虽然有上过数据挖掘和机器学习的课，但是自己的专业并不在此，对遥感图像的自动分类更是一窍不通，所以慢慢自学，顺便写个博客记录一下自己的学习过程，谬误在所难免，大家多多包涵指正。
  根据最近的Mahout Wiki，Mahout实现的分类算法有：随机梯度下降（SGD），贝叶斯分类，Online Passive Aggressive，HMM和决策森林（随机森林）。随机梯度下降当前不能并行处理，贝叶斯分类更适合处理文本数据，所以这两个算法都不太适合我的应用场景（并行处理，特征类型为数字），OPA和HMM不太熟悉，所以就选用了决策森林（随机森林）。
决策森林，顾名思义，就是由多个决策树组成森林，然后用这个森林进行分类，非常适合用MapReduce实现，进行并行处理。决策森林又称为随机森林，这是因为不同于常规的决策树（ID3，C4.5），决策森林中每个每棵树的每个节点在选择该点的分类特征时并不是从所有的输入特征里选择一个最好的，而是从所有的M个输入特征里随机的选择m个特征，然后从这m个特征里选择一个最好的（这样比较适合那种输入特征数量特别多的应用场景，在输入特征数量不多的情况下，我们可以取m=M）。然后针对目标特征类型的不同，取多个决策树的平均值（目标特征类型为数字类型（numeric））或大多数投票（目标特征类型为类别（category））。
  在Mahout的example中有一个Decision Tree的例子，可以直接在命令行运行：
1. 准备数据：
  数据为Breiman提供的glass：http://archive.ics.uci.edu/ml/datasets/Glass+Identification。
  2. 生成数据的说明文件：
  在Mahout目录下执行：bin/mahout org.apache.mahout.df.tools.Describe -p testdata/glass.data -f testdata/glass.info -d I 9 N L
  数据格式为CSV，最后的I 9 N L说明各特征的属性：
  I表示忽略第一个特征值（该特征值一般用来标示每一条训练样例，亦即可以作为ID）。
  9 N表示接下来的9个特征是输入特征，类型为数字类型。
  L 表示该特征是目标特征，亦即Label。
  以glass文件的前几行为例为例：
1,1.52101,13.64,4.49,1.10,71.78,0.06,8.75,0.00,0.00,1
2,1.51761,13.89,3.60,1.36,72.73,0.48,7.83,0.00,0.00,1
3,1.51618,13.53,3.55,1.54,72.99,0.39,7.78,0.00,0.00,1
4,1.51766,13.21,3.69,1.29,72.61,0.57,8.22,0.00,0.00,1
5,1.51742,13.27,3.62,1.24,73.08,0.55,8.07,0.00,0.00,1
  第一个特征被忽略，因为这个特征是作为ID用来表示每个样例的，2-10是9个输入特征，用来训练分类器，类型为数字（Numeric），最后一个特征是目标特征，代表每个样例所属的类别，这里所有样例都属于"1"类。
  3. 进行分类和测试
  在Mahout目录下执行：bin/mahout org.apache.mahout.df.BreimanExample -d testdata/glass.data -ds testdata/glass.info -i 10 -t 100
  -i表示迭代的次数
  -t表示每棵决策树的节点的个数
  BreimanExample默认会构造两个森林，一个取m=1，一个取m=log（M+1）。之所以这么做是为了说明即使m值很小，整个森林的分类结果也会挺好。
  4. 分类的结果：
  12/09/13 15:18:07 INFO df.BreimanExample: Selection error : 0.2952380952380952
  12/09/13 15:18:07 INFO df.BreimanExample: Single Input error : 0.29999999999999993
  12/09/13 15:18:07 INFO df.BreimanExample: One Tree error : 0.41874436090225553
  Selection Error是用两个森林中误差较小的森林做分类得到的错误率。
  Single Input Error是用m=1的森林做分类得到的错误率。
  One Tree Error是单棵树的平均错误率。

一、介绍Mahout
    Mahout是Apache下的开源机器学习软件包，目前实现的机器学习算法主要包含有协同过滤/推荐引擎，聚类和分类三个部分。Mahout从设计开始就旨在建立可扩展的机器学习软件包，用于处理大数据机器学习的问题，当你正在研究的数据量大到不能在一台机器上运行时，就可以选择使用Mahout，让你的数据在Hadoop集群的进行分析。Mahout某些部分的实现直接创建在Hadoop之上，这就使得其具有进行大数据处理的能力，也是Mahout最大的优势所在。相比较于Weka，RapidMiner等图形化的机器学习软件，Mahout只提供机器学习的程序包（library），不提供用户图形界面，并且Mahout并不包含所有的机器学习算法实现，这一点可以算得上是她的一个劣势，但前面提到过Mahout并不是“又一个机器学习软件”，而是要成为一个“可扩展的用于处理大数据的机器学习软件”，但是我相信会有越来越多的机器学习算法会在Mahout上面实现。
   二、介绍K-Means
    https://cwiki.apache.org/confluence/display/MAHOUT/K-Means+Clustering#，这是Apache官网上的算法描述，简单来说就是基于划分的聚类算法，把n个对象分为k个簇，以使簇内具有较高的相似度。相似度的计算根据一个簇中对象的平均值来进行。[2]   
 三、在Hadoop上实现运行
    1，实验环境
        ①hadoop集群环境：1.2.1 一个Master，两个Slaves，在开始运行kmeans时启动hadoop
        ②操作系统：所有机器的系统均为ubuntu12.04
        ③Mahout版本：采用的是0.5版
    2，数据准备
        数据采用的是http://archive.ics.uci.edu/ml/databases/synthetic_control/synthetic_control.data，这是网上提供的一个比较不错是数据源。然后用指令 hadoop fs -put /home/hadoop/Desktop/data testdata，将在我桌面的文件data上传到HDFS的testdata目录下，这里为什么是testdata，我也正在思考，因为我本来是上传到input里，但是运行时提示could not find ....user/testdata之类的，所以现改为了testdata。    3，运行
        ①配置Mahout环境：在Apache官网下载Mahout的版本，我选择的是0.5，下载地址：https://cwiki.apache.org/confluence/display/MAHOUT/Downloads。然后解压到你指定的目录，将此目录路径写入/etc/profile，添加如下语句：

• export MAHOUT_HOME=/home/hadoop/hadoop-1.2.1/mahout-distribution-0.5
• export HADOOP_CONF_DIR=/home/hadoop/hadoop-1.2.1/conf
• export PATH=$PATH:/home/hadoop/hadoop-1.2.1/bin:$MAHOUT_HOME/bin

然后执行 source /etc/profile。在mahout目录下执行bin/mahout命令，检测系统是否安装成功。如图：

注：此处修改环境变量有些网上提示是/etc/bash.bashrc，我也试着修改过，但是发现在我这里使环境变量生效的是profile。
        ②运行Mahout里自带的K-Means算法，bin/mahout org.apache.mahout.clustering.syntheticcontrol.kmeans.Job，这里启动后遇到了一点问题，提示Could not find math.vector，后来参考这篇http://jerrylead.iteye.com/blog/1188929日志解决。
     4，结果
       在我的环境下运行5分钟左右，最后生成一个文件，如图

四、总结
        Mahout是一个很强大的数据挖掘工具，需要进行更深层的了解。
 
 

一致性Hash算法
1）问题描述
分布式常常用Hash算法来分布数据，当数据节点不变化时是非常好的，但当数据节点有增加或减少时，由于需要调整Hash算法里的模，导致所有数据得重新按照新的模分布到各个节点中去。如果数据量庞大，这样的工作常常是很难完成的。一致性Hash算法是基于Hash算法的优化，通过一些映射规则解决以上问题
2）算法本身
对于一致性Hash算法本身我也不做完整的阐述，有篇blog《一致性hash算法 - consistent hashing》 描述这个算法非常到位，我就不重复造轮子了。
实际上，在其他设计和开发领域我们也可以借鉴一致性Hash的思路，当一个映射或规则导致有难以维护的问题时，可以考虑更一步抽象这些映射或规则，通过规则的变化使得最终数据的不变。一致性hash实际就是把以前点映射改为区段映射，使得数据节点变更后其他数据节点变动尽可能小。这个思路在操作系统对于存储问题上体现很多，比如操作系统为了更优化地利用存储空间，区分了段、页等不同纬度，加了很多映射规则，目的就是要通过灵活的规则避免物理变动的代价
3）算法实现
一致性Hash算法本身比较简单，不过可以根据实际情况有很多改进的版本，其目的无非是两点：
节点变动后其他节点受影响尽可能小
节点变动后数据重新分配尽可能均衡
实现这个算法就技术本身来说没多少难度和工作量，需要做的是建立起你所设计的映射关系，无需借助什么框架或工具，sourceforge上倒是有个项目libconhash ，可以参考一下
以上两个算法在我看来就算从不涉及算法的开发人员也需要了解的，算法其实就是一个策略，而在分布式环境常常需要我们设计一个策略来解决很多无法通过单纯的技术搞定的难题，学习这些算法可以提供我们一些思路。

Paxos算法

1）问题描述

分布式中有这么一个疑难问题，客户端向一个分布式集群的服务端发出一系列更新数据的消息，由于分布式集群中的各个服务端节点是互为同步数据的，所以运行完客户端这系列消息指令后各服务端节点的数据应该是一致的，但由于网络或其他原因，各个服务端节点接收到消息的序列可能不一致，最后导致各节点的数据不一致。举一个实例来说明这个问题，下面是客户端与服务端的结构图：



当client1、client2、client3分别发出消息指令A、B、C时，Server1~4由于网络问题，接收到的消息序列就可能各不相同，这样就可能由于消息序列的不同导致Server1~4上的数据不一致。对于这么一个问题，在分布式环境中很难通过像单机里处理同步问题那么简单，而Paxos算法就是一种处理类似于以上数据不一致问题的方案。

2）算法本身

算法本身我就不进行完整的描述和推导，网上有大量的资料做了这个事情，但我学习以后感觉莱斯利·兰伯特（Leslie Lamport，paxos算法的奠基人，此人现在在微软研究院）的Paxos Made Simple 是学习paxos最好的文档，它并没有像大多数算法文档那样搞一堆公式和数学符号在那里吓唬人，而是用人类语言让你搞清楚Paxos要解决什么问题，是如何解决的。这里也借机抨击一下那些学院派的研究者，要想让别人认可你的成果，首先要学会怎样让大多数人乐于阅读你的成果，而这个描述Paxos算法的文档就是我们学习的榜样。

言归正传，透过Paxos算法的各个步骤和约束，其实它就是一个分布式的选举算法，其目的就是要在一堆消息中通过选举，使得消息的接收者或者执行者能达成一致，按照一致的消息顺序来执行。其实，以最简单的想法来看，为了达到大伙执行相同序列的指令，完全可以通过串行来做，比如在分布式环境前加上一个FIFO队列来接收所有指令，然后所有服务节点按照队列里的顺序来执行。这个方法当然可以解决一致性问题，但它不符合分布式特性，如果这个队列down掉或是不堪重负这么办？而Paxos的高明之处就在于允许各个client互不影响地向服务端发指令，大伙按照选举的方式达成一致，这种方式具有分布式特性，容错性更好。

说到这个选举算法本身，可以联想一下现实社会中的选举，一般说来都是得票者最多者获胜，而Paxos算法是序列号更高者获胜，并且当尝试提交指令者被拒绝时（说明它的指令所占有的序列号不是最高），它会重新以一个更好的序列参与再次选举，通过各个提交者不断参与选举的方式，达到选出大伙公认的一个序列的目的。也正是因为有这个不断参与选举的过程，所以Paxos规定了三种角色（proposer，acceptor，和 learner）和两个阶段（accept和learn），三种角色的具体职责和两个阶段的具体过程就见Paxos Made Simple ，另外一个国内的哥们写了个不错的PPT ，还通过动画描述了paxos运行的过程。不过还是那句话不要一开始就陷入算法的细节中，一定要多想想设计这些游戏规则的初衷是什么。

Paxos算法的最大优点在于它的限制比较少，它允许各个角色在各个阶段的失败和重复执行，这也是分布式环境下常有的事情，只要大伙按照规矩办事即可，算法的本身保障了在错误发生时仍然得到一致的结果。

3）算法的实现

Paxos的实现有很多版本，最有名的就是google chubby ，不过看不了源码。开源的实现可见libpaxos 。另外，ZooKeeper 也基于paxos解决数据一致性问题，也可以看看它是如果实现paxos的。

4）适用场景

弄清楚paxos的来龙去脉后，会发现它的适用场景非常多，Tim有篇blog《Paxos在大型系统中常见的应用场景》 专门谈这个问题。我所见到的项目里，naming service是运用Paxos最广的领域，具体应用可参考ZooKeeper

鉴于在PPT上面，关于Reuters路透社的新闻使用kmeans的命令有残缺，导致我一头雾水。其实在mahout的examples文件夹里面已经有这个build-reuters.sh的脚本，大家直接运行就可以了。我这里附上官方版的直接运行脚本：
#/**
# * Licensed to the Apache Software Foundation (ASF) under one or more
# * contributor license agreements.  See the NOTICE file distributed with
# * this work for additional information regarding copyright ownership.
# * The ASF licenses this file to You under the Apache License, Version 2.0
# * (the "License"); you may not use this file except in compliance with
# * the License.  You may obtain a copy of the License at
# *
# *     http://www.apache.org/licenses/LICENSE-2.0
# *
# * Unless required by applicable law or agreed to in writing, software
# * distributed under the License is distributed on an "AS IS" BASIS,
# * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# * See the License for the specific language governing permissions and
# * limitations under the License.
# */

#
# Downloads the Reuters dataset and prepares it for clustering
#
# To run:  change into the mahout directory and type:
#  examples/bin/build-reuters.sh
#!/bin/sh

cd examples/bin/
mkdir -p work
if [ ! -e work/reuters-out ]; then
  if [ ! -e work/reuters-sgm ]; then
    if [ ! -f work/reuters21578.tar.gz ]; then
      echo "Downloading Reuters-21578"
      curl http://kdd.ics.uci.edu/databases/reuters21578/reuters21578.tar.gz  -o work/reuters21578.tar.gz
    fi
    mkdir -p work/reuters-sgm
    echo "Extracting..."
    cd work/reuters-sgm && tar xzf ../reuters21578.tar.gz && cd .. && cd ..
  fi
fi

cd ../..
./bin/mahout org.apache.lucene.benchmark.utils.ExtractReuters ./examples/bin/work/reuters-sgm/ ./examples/bin/work/reuters-out/
./bin/mahout seqdirectory -i ./examples/bin/work/reuters-out/ -o ./examples/bin/work/reuters-out-seqdir -c UTF-8 -chunk 5
./bin/mahout seq2sparse -i ./examples/bin/work/reuters-out-seqdir/ -o ./examples/bin/work/reuters-out-seqdir-sparse
./bin/mahout kmeans -i ./examples/bin/work/reuters-out-seqdir-sparse/tfidf-vectors/ -c ./examples/bin/work/clusters -o ./examples/bin/work/reuters-kmeans -x 10 -k 20 -ow
./bin/mahout clusterdump -s examples/bin/work/reuters-kmeans/clusters-10 -d examples/bin/work/reuters-out-seqdir-sparse/dictionary.file-0 -dt sequencefile -b 100 -n 20

 前言
面试 IT 企业的研发岗位，数据结构和算法显然是必考的项目。俺只学过普通的数据结构课程，没读过 STL，也没有过 ACM 的训练和比赛经历，在一开始面对这样类型题目的时候，心里还是十分忐忑的。大大小小几十场面试下来，自己在这方面总算有了一定的心得积累，在此抛砖引玉，以飨读者。
在正式介绍题目和准备方法之前，有两点需要说明，

• Google 和 Facebook 这类对算法有很高要求的公司的在线测试我没有参加过（不过在牛人内推帮助下有过面试体验……），这超出了我目前的编码能力范围，网上有不少拿到 Google、Facebook offer 的经验总结文章，可以移步观赏；
• 前段时间在微博上又看到有人说自己把 leetcode 刷了好几遍，不过一些转发评论者觉得， IT 公司面试中的算法考察没有价值，一来工作里用不太上，二来把程序员素质考察搞成了应试教育，他们认为更重要的是应聘者的工程能力。遇到这样的讨论，我一般喜欢和一把稀泥。若干年前， Google、微软的面试题让大家眼前一亮，觉得能选拔出个性十足的聪明人来，不过随着大家对这类题目的适应，可能选拔出来的人也在趋同，至少很多人都会在面试前用心准备。没有什么一劳永逸、一成不变的考查方式，毕竟面试是人和人之间的动态“较量”。不要贪恋算法的奇技淫巧，也不要因为题目筛选力度的衰减而否定考察初衷。面试不仅是考验求职者，也同样在考验面试官，如果问的都是老题儿，那本山大叔肯定都会抢答了。

言归正传，以下分数据结构题目、算法题目、开放题目三部分来介绍我在面试中碰到的问题。数据结构题目概述虽然课本由简到繁、由难到易地介绍了诸多数据结构，我在面试中被问到的却还都是基本类型，比如堆栈、队列、链表、二叉树。题目主要有两类，数据结构实现和具体情境下数据结构的应用。 分类讨论：类型一：数据结构实现[list=1]

实现 java.util.List 中的基础功能；

实现栈，使得 添加、删除、max 操作的复杂度为 O(1)（我脚着好像是不可实现的，想到最好的是添加、删除 O(log)， max 是 O(1)）；

选取任意数据结构实现添加、删除、随机返回三个功能，分析复杂度；

用数组实现队列，各操作的复杂度分析。

类型二：数据结构应用[list=1]

两棵树相加——对应位置两棵树都有值则相加，对应位置只有一棵树有值则取该值；

用速度不同的指针可以判断链表中是否有环，问两速度满足怎样的关系可以保证发现环；

如何在语料中寻找频繁出现的字串，分析复杂度（tire树）；

中缀表达式转逆波兰表达式，逆波兰表达式求值；

数据解压缩，3(a4(ab)) -> aababababaababababaabababab；

二叉树的文件存储

准备建议上上之选当然是看《算法导论》，书和公开课都算。注意熟记不同数据结构的不同操作的不同实现方式（比如哈希表的插入删除查找）的复杂度分析，不管面试官给你出的题目是难是易，妥妥儿的会问复杂度。 算法题目概述有过面试经历的企业（BAT、小米、宜信、猿题库、FreeWheel等）当中，还没有谁问过我需要复杂算法才能解决的问题。我遇到的算法题目大致可以分为两类：

• 经典算法实现题 快速排序、归并排序、堆排序、KMP算法等都是重点，重要的是代码的正确性，其次是复杂度分析，当然，人家也不都是直接问你怎么实现这个具体算法，而是包装到情境里；
• 思维益智题 考察你分析问题的能力，大部分可以归结到二分、动态规划、递归上，重要的是思路，其次是尽量低的复杂度，再次是代码的正确性。

 下面具体介绍我遇到的两种类型题目中的问题。分类讨论：类型一：经典算法实现题[list=1]

实现快速排序、归并排序、堆排序，各排序算法复杂度分析；

实现KMP，解释原理；

迷宫的深度搜索、广度搜索；

写 find 函数，在目标串中匹配模式串（要考虑中文字符的情况）。

类型二：思维益智题[list=1]

数列中找第 k 大的数字（与快排或堆排序有关）；

两个有序数组，寻找归并排序后数组的中位数/第 k 大数字（与二分有关）；

一维数组，swap 其中的几对数字（每个数字只属于一次 swap 操作），实现查找（与二分有关）；

一个有序数组，其中一个数字发生变异，但不知道变异后会不会影响整体序，如何实现查找；

二维数组，每行递增，每列递增

• 实现查找；
• 二维数组，每行递增，每列递增，求第 k 大的数；
• 任意交换其中的两数，发现并恢复 

寻找字符串中第一个只出现一次的字符；

统计数列中的逆序对（归并排序有关）；

最长公共子串（动态规划有关）；

最大子序列和，允许交换一次的最大子序列和；

给定数组，寻找 next big（堆排序有关）；

一维有序数组，经过循环位移后，最小的数出现在数列中间

• 如果原数组严格递增，如何找这个最小数；
• 如果原数组严格递增或递减，如何找这个最小数；
• 如果原数组非严格递增或递减，如何找这个最小数 

数组可能是递增、递减、递减后递增、递增后递减四种情况，递增递减都是非严格的，如果有转折点，返回转折点的值，否则返回-1；

单向网络，起点和终点唯一且连通，寻找那些一旦被删除将导致起点终点无法连通的点；

有序数组寻找和为某数的一对数字；

墙里能装多少水；

打印螺旋数组；

打印组合数；

字符数组，统计指定区间内的回文串个数。

准备建议

• 不要纠结于是否是最佳思路，要保证能在 10-15 分钟内给出一个解决方案，并分析复杂度；
• hihocoder、topcoder、leetcode、codility、POJ 等网站择一练手;
• Soulmachine 在 Github 中有高质量的学习资料，适合系统学习 & 临时抱佛脚
  • LeetCode 题解
  • ACM Cheat Sheet
  • HackerRank题解

开放题这类开放题目让你自主选择数据结构，主要是考察求职者对于数据结构的特性与使用场景的综合理解，在面对具体应用场景时能否运用已有的数据结构和算法知识提出合理的解决方案。一般来说在这类问题里哈希表的出场率会比较高……例题如下[list=1]

大数据量的 url log，怎么去重且统计每个 url 的出现次数，复杂度分析；

设计 cache 系统

• 设计 cache 的接口；
• 可以用什么数据结构实现；
• 如何实现可伸缩的容量；
• cache 的空间管理策略，比如 cache 哪些条目，何时清理；
• cache 系统启动时分配多大的空间，之后按照怎样的策略增大； 

设计爬虫；

流媒体播放客户端从多个完全相同的发送方接收视频包，同一发送方的包会按序到达，不同发送方的包则不一定，有可能会丢包，但还是要保证播放流畅度，设计播放客户端的算法。

总结

• 数据结构和算法的基础知识还是十分重要的，大部分题目的思路来源于此；
• 训练自己算法复杂度的分析能力，有的时候对复杂度的分析会反过来会帮助你找到更好的算法；
• 一定量的题目积累很重要，就好像准备高考数学压轴题一样，见识的越多，思路来得越快，当然，前提是你能够不断总结反思。

  来源：太极儒的博客

之前一段时间一直在准备面试， 因而博客太久没更新； 现在基本知识点都复习完毕， 接下来就分享下 面试的一些常见问题：

去正规的互联网公司笔试、面试有很大的概率会碰到 使用javascript实现数组去重 的编码问题：如：魅族笔试题；

本博文就 js 如何实现数组去重整理出5种方法，并附上演示Demo 以及 源码。1.遍历数组法

最简单的去重方法， 实现思路：新建一新数组，遍历传入数组，值不在新数组就加入该新数组中；注意点：判断值是否在数组的方法“indexOf”是ECMAScript5 方法，IE8以下不支持，需多写一些兼容低版本浏览器代码，源码如下：// 最简单数组去重法 function unique1(array){ var n = []; //一个新的临时数组 //遍历当前数组 for(var i = 0; i < array.length; i++){ //如果当前数组的第i已经保存进了临时数组，那么跳过， //否则把当前项push到临时数组里面 if (n.indexOf(array[i]) == -1) n.push(array[i]); } return n; }
// 判断浏览器是否支持indexOf ，indexOf 为ecmaScript5新方法 IE8以下（包括IE8， IE8只支持部分ecma5）不支持 if (!Array.prototype.indexOf){ // 新增indexOf方法 Array.prototype.indexOf = function(item){ var result = -1, a_item = null; if (this.length == 0){ return result; } for(var i = 0, len = this.length; i < len; i++){ a_item = this[i]; if (a_item === item){ result = i; break; } } return result; } }2.对象键值对法

该方法执行的速度比其他任何方法都快， 就是占用的内存大一些；实现思路：新建一js对象以及新数组，遍历传入数组时，判断值是否为js对象的键，不是的话给对象新增该键并放入新数组。注意点： 判断是否为js对象键时，会自动对传入的键执行“toString()”，不同的键可能会被误认为一样；例如： a[1]、a["1"] 。解决上述问题还是得调用“indexOf”。// 速度最快， 占空间最多（空间换时间） function unique2(array){ var n = {}, r = [], len = array.length, val, type; for (var i = 0; i < array.length; i++) { val = array[i]; type = typeof val; if (!n[val]) { n[val] = [type]; r.push(val); } else if (n[val].indexOf(type) < 0) { n[val].push(type); r.push(val); } } return r; }3.数组下标判断法

还是得调用“indexOf”性能跟方法1差不多，实现思路：如果当前数组的第i项在当前数组中第一次出现的位置不是i，那么表示第i项是重复的，忽略掉。否则存入结果数组。function unique3(array){ var n = [array[0]]; //结果数组 //从第二项开始遍历 for(var i = 1; i < array.length; i++) { //如果当前数组的第i项在当前数组中第一次出现的位置不是i， //那么表示第i项是重复的，忽略掉。否则存入结果数组 if (array.indexOf(array[i]) == i) n.push(array[i]); } return n; }4.排序后相邻去除法

虽然原生数组的”sort”方法排序结果不怎么靠谱，但在不注重顺序的去重里该缺点毫无影响。实现思路：给传入数组排序，排序后相同值相邻，然后遍历时新数组只加入不与前一值重复的值。// 将相同的值相邻，然后遍历去除重复值 function unique4(array){ array.sort(); var re=[array[0]]; for(var i = 1; i < array.length; i++){ if( array[i] !== re[re.length-1]) { re.push(array[i]); } } return re; }5.优化遍历数组法

源自外国博文，该方法的实现代码相当酷炫；实现思路：获取没重复的最右一值放入新数组。（检测到有重复值时终止当前循环同时进入顶层循环的下一轮判断）// 思路：获取没重复的最右一值放入新数组 function unique5(array){ var r = []; for(var i = 0, l = array.length; i < l; i++) { for(var j = i + 1; j < l; j++) if (array[i] === array[j]) j = ++i; r.push(array[i]); } return r; }实现demo     demo 源码

参考资料：Fast Algorithm To Find Unique Items in JavaScript Array