决策树

决策树是常用的分类算法之一，其对于探索式的知识发现往往有较好的表现。决策树原理十分简单，可处理大维度的数据，不用预先对模型的特征有所了解，这些特性使得决策树被广泛使用。决策树采用贪心算法，其建立过程同样需要训练数据。决策树算法有ID3、在ID3基础上发展起来的C4.5，以及C4.5的商业化版本C5.0，C5.0核心与C4.5相同，只是在执行效率和内存使用方面有所改进。

决策树的核心问题是决策树分支准则的确定，以及分裂点的确定。为了直观起见，推荐大家玩一个游戏：通过20个问题来猜出你心中所想的那个人。

初次接触这个游戏的你是否觉得十分神奇，在20个不到的问题里真的就能猜出你心中所想的那个人，不论是你的女朋友、父母或者动漫人物、歌手、演员甚至是政界人物。其实仔细想想，一个20层的二叉树最后的叶子节点有多少个？1024*1024个，而我们能想到的人绝对是超不出这个数量的。这个网站的具体算法就是采用的类似决策树的算法，通过一个个问题来减少候选的数据，直至找出你所想的那个人。

多玩几次你就会发现，一般第一个或前几个问题就会问你：你描述的对象是男（女）性吗？这意味着什么，意味着第一个问题就能将候选数据减少一半左右。因为你想的那个人，除了男人就是女人了。这就是前面所说的决策树分支准则的确定。若将这个问题放在最后几个问题中，毫无疑问是个吃力不讨好的事情。那么如何才能将这些众多属性（如：性别、高矮、胖瘦、头发长短、是否是歌手、是否有money等）按照其重要程度来排个顺序，这就是ID3和C4.5算法所做的事情了。

预备知识

信息熵是信息论中的基本概念。信息论是C.E.Shannon于1948年提出并由此发展起来的，主要用于解决信息传递过程中的问题，也称为统计通信理论。信息论认为：信息是用来消除随机不确定性的，信息量的大小可由所消除的不确定大小来计量。详细了解。

信息量的数学定义为：

$I(u_i)=-log_2P(u_i)$

其中 $P(u_i)$ 为信息 $u_i$ 发生的概率。信息熵是信息量的数学期望，是信源发出信息前的平均不确定性，也成为先验熵，信息熵的数学定义为：

$Ent(U)=-\sum_iP(u_i)log_2P(u_i)$

当已知信号 $U$ 的概率分布 $P(U)$ 且收到信号 $V=v_i$ 后，发出信号的概率分布变为 $P(U|v_j)$ ，于是信源的平均不确定性变为（也称为条件熵）：

$Ent(U|v_i)=-\sum_iP(u_i|v_i)log_2P(u_i|v_i)$

一般来说， $Ent(U|v_i) < Ent(U)$ ，于是定义信息增益为：

$Gains(U,V)=Ent(U)-Ent(U|V)$

阅读全文>>

Levenshtein距离，又称为编辑距离，或者成为字符串相似度，意思是一个字符串转换为另一个字符串所需要的最小编辑次数。编辑包含：插入、删除和替换三种操作。例如字符串：yurnom和yunum的编辑距离为2，因为需要插入一个r和将u替换为o两次操作。

Levenshtein算法由俄罗斯科学家Vladimir Levenshtein在1965年提出，该算法现在广泛用于DNA匹配、字符串纠错、实体共指等领域。

算法简介

将2个字符串转换为一个矩阵，为了简单起见，采用字符串heqi和hoi。转换后进行初始化，如下所示：

其中数字部分为初始化的值，现计算绿色格子A处的值，其算法为：

1. 若A所对应的两个字符相同，则左上角蓝色格子的值+0，否则+1，结果记为R1
2. 选取上方和左方紫色格子中较小的值，并+1，结果记为R2
3. 选取R1和R2中的较小值为绿色格子A处的值

经过计算可以得出A处的值为0，当A处计算完毕后，其右方和下方的值可以接着进行计算了，如此整个矩阵的值将可全部计算出来。最后矩阵右下方红色格子的值即为两个字符串的编辑距离。

至于为何左方和上方的值加1、左上角的值根据不同的情况加0或1的原因（也就是这么算的原理）比较简单，在此不再详述。

阅读全文>>

分片、Block与Map数量

Block，即HDFS上的基本存储单元，默认大小是64MB。我们都知道一个block对应一个map任务，但实际过程是先将文件分片，然后每个分片启动一个map任务，只不过通常情况下分片的大小和Block是一致的。可以通过参数来将分片的大小进行改变，相应的启动的map数量也会改变，其对应关系如下：

如上所示，当分片值是128MB而block大小是64MB时，这时启动的map数量比默认情况下要少一半，但本地开销会变大，因为涉及到数据的传输等过程。当分片值是32MB而block大小是64MB时，这时启动的map数量比默认情况下要多一倍，也就是一个block启动了2个map来进行处理。

若遇到一个文件分为多个block存放，但启动任务时候又必须放在一个map中进行处理，则可以通过将分片最小值设置成一个大于该文件的值来实现。

对应API和参数如下：

• FileInputFormat.setMaxInputSplitSize(..)，mapred.max.split.size，设置分片最大值
• FileInputFormat.setMinInputSplitSize(..)，mapred.min.split.size，设置分片最小值

处理未知的脏数据

一般而言，脏数据过滤是每个任务通过编码来实现的，例如过滤掉维度数量不符的数据，过滤掉某些维度为空的数据，等等。但还有一些脏数据却无法通过编码来处理，因为这类脏数据是无法预料的，例如因为网络传输出错而导致的超长行，或者特殊字符（EOF等等）。一个超长的行很大可能会造成序列化、网络传输等过程中内存溢出。

对于这样的情况，若能准确的分析出问题所在，也可以通过代码来实现脏数据的过滤。如，使用TextInputFormat、NLineInputFormat时，可以通过设置mapred.linerecordreader.maxlength参数来防止“超长“行类的脏数据。但对于客观原因上无法定位其原因的脏数据，则只能采用SkipBadRecords工具类来避免出错了。

阅读全文>>

本文不涉及线性回归具体算法和原理性的东西，纯新手向、介绍性的文章。

线性回归

线性回归，对于初学者而言（比方说我）比较难理解，其实换个叫法可能就能立马知道线性回归是做什么的了：线性拟合。所谓拟合，就简单多了，如下图所示：

线性拟合，顾名思义拟合出来的预测函数是一条直线，数学表达如下：

$h(x)=a_0+a_1x_1+a_2x_2+..+a_nx_n+J(\theta)$

其中 $h(x)$ 为预测函数， $a_i(i=1,2,..,n)$ 为估计参数，模型训练的目的就是计算出这些参数的值。

而线性回归分析的整个过程可以简单描述为如下三个步骤：

1. 寻找合适的预测函数，即上文中的 $h(x)$ ，用来预测输入数据的判断结果。这个过程时非常关键的，需要对数据有一定的了解或分析，知道或者猜测预测函数的“大概”形式，比如是线性函数还是非线性函数，若是非线性的则无法用线性回归来得出高质量的结果。
2. 构造一个Loss函数（损失函数），该函数表示预测的输出（h）与训练数据标签之间的偏差，可以是二者之间的差（h-y）或者是其他的形式（如平方差开方）。综合考虑所有训练数据的“损失”，将Loss求和或者求平均，记为 $J(\theta)$ 函数，表示所有训练数据预测值与实际类别的偏差。
3. 显然， $J(\theta)$ 函数的值越小表示预测函数越准确（即h函数越准确），所以这一步需要做的是找到 $J(\theta)$ 函数的最小值。找函数的最小值有不同的方法，Spark中采用的是梯度下降法（stochastic gradient descent, SGD)。

阅读全文>>

原文地址：http://spark.apache.org/docs/latest/running-on-yarn.html

Spark从0.6.0版本开始对YARN提供支持，并在后续版本中持续改进。

准备

Spark-on-YARN需要二进制版本的Spark，可以在官网上下载。同样也可以自己编译，参考building with Maven guide。

配置

Spark on YARN的大多数参数配置与其它部署模式相同，详细参考configuration page。Spark on YARN的特殊参数如下：

环境变量

SPARK_YARN_USER_ENV：为运行在YARN上的Spark进程添加环境变量。可以是一个以逗号分隔的list，例如：SPARK_YARN_USER_ENV="JAVA_HOME=/jdk64,FOO=bar"。

Spark属性

阅读全文>>

聚类算法

聚类，Cluster analysis，有时也被翻译为簇类，其核心任务是：将一组目标object划分为若干个簇，每个簇之间的object尽可能的相似，簇与簇之间的object尽可能的相异。聚类算法是机器学习（或者说是数据挖掘更合适）中重要的一部分，除了最为简单的K-Means聚类算法外，较常见的还有：层次法（CURE、CHAMELEON等）、网格算法（STING、WaveCluster等）等等。

较权威的聚类问题定义：所谓聚类问题，就是给定一个元素集合D，其中每个元素具有n个可观察属性，使用某种算法将D划分成k个子集，要求每个子集内部的元素之间相异度尽可能低，而不同子集的元素相异度尽可能高。其中每个子集叫做一个簇。

与分类不同，分类是示例式学习，要求分类前明确各个类别，并断言每个元素映射到一个类别，而聚类是观察式学习，在聚类前可以不知道类别甚至不给定类别数量，是无监督学习的一种。目前聚类广泛应用于统计学、生物学、数据库技术和市场营销等领域，相应的算法也非常的多。

K-Means

K-Means属于基于平方误差的迭代重分配聚类算法，其核心思想十分简单：

1. 随机选择K个中心点
2. 计算所有点到这K个中心点的距离，选择距离最近的中心点为其所在的簇
3. 简单的采用算术平均数（mean）来重新计算K个簇的中心
4. 重复步骤2和3,直至簇类不在发生变化或者达到最大迭代值
5. 输出结果

K-Means算法的结果好坏依赖于对初始聚类中心的选择，容易陷入局部最优解，对K值的选择没有准则可依循，对异常数据较为敏感，只能处理数值属性的数据，聚类结构可能不平衡。

这里有一个K-Means的演示，需要安装Java Applet。

阅读全文>>

分类算法

何为分类算法？简单来说，就是将具有某些特性的物体归类对应到一个已知的类别集合中的某个类别上。从数学角度来说，可以做如下定义：

已知集合： $C=\{y_1,y_2,..,y_n\}$ 和 $I=\{x_1,x_2,..,x_m,..\}$ ，确定映射规则 $y=f(x)$ ，使得任意 $x_i \in I$ 有且仅有一个 $y_j \in C$ 使得 $y_j=f(x_i)$ 成立。

其中，C为类别集合，I为待分类的物体，f则为分类器，分类算法的主要任务就是构造分类器f。

分类算法的构造通常需要一个已知类别的集合来进行训练，通常来说训练出来的分类算法不可能达到100%的准确率。分类器的质量往往与训练数据、验证数据、训练数据样本大小等因素相关。

举个例子，我们日常生活中看到一个陌生人，要做的第一件事情就是判断其性别，判断性别的过程就是一个分类的过程。根据以往的生活经验，通常经过头发长短、服饰和体型这三个要素就能判断出来一个人的性别。这里的“生活经验”就是一个训练好的关于性别判断的模型，其训练数据是日常生活中遇到的形形色色的人。突然有一天，一个娘炮走到了你面前，长发飘飘，穿着紧身的衣裤，可是体型却很man，于是你就疑惑了，根据以往的经验——也就是已经训练好的模型，无法判断这个人的性别。于是你学会了通过喉结来判断其性别，这样你的模型被训练的质量更高了。但不可否认的是，永远会出现一个让你无法判断性别的人。所以模型永远无法达到100%的准确，只会随着训练数据的不断增多而无限接近100%的准确。

贝叶斯公式

贝叶斯公式，或者叫做贝叶斯定理，是贝叶斯分类的基础。而贝叶斯分类是一类分类算法的统称，这一类算法的基础都是贝叶斯公式。目前研究较多的四种贝叶斯分类算法有：Naive Bayes、TAN、BAN和GBN。

理工科的学生在大学应该都学过概率论，其中最重要的几个公式中就有贝叶斯公式——用来描述两个条件概率之间的关系，比如P(A|B)和P(B|A)。如何在已知事件A和B分别发生的概率，和事件B发生时事件A发生的概率，来求得事件A发生时事件B发生的概率，这就是贝叶斯公式的作用。其表述如下：

$P(B|A)={P(A|B)\times P(B)\over P(A)}$

阅读全文>>

概述

在2014年7月1日的Spark Summit上，Databricks宣布终止对Shark的开发，将重点放到Spark SQL上。Databricks表示，Spark SQL将涵盖Shark的所有特性，用户可以从Shark 0.9进行无缝的升级。现在Databricks推广的Shark相关项目一共有两个，分别是Spark SQL和新的Hive on Spark（HIVE-7292）。如下图所示：

Spark SQL运行以SQL的方式来操作数据，类似Hive和Pig。其核心组件为一种新类型的RDD——JavaSchemaRDD，一个JavaSchemaRDD就好比传统关系型数据库中的一张表。JavaSchemaRDD可以从已有的RDD创建，还可以从Parquet文件、JSON数据集、HIVE、普通数据文件中创建。但现阶段（1.0.2版本）的Spark SQL还是alpha版，日后的API难免会发生变化，所以是否要使用该功能，现阶段还值得商榷。

程序示例

Bean，必须要有get方法，底层采用反射来获取各属性。

阅读全文>>

概述

Spark Streaming类似于Apache Storm，用于流式数据的处理。根据其官方文档介绍，Spark Streaming有高吞吐量和容错能力强这两个特点。Spark Streaming支持的数据输入源很多，例如：Kafka、Flume、Twitter、ZeroMQ和简单的TCP套接字等等。数据输入后可以用Spark的高度抽象原语如：map、reduce、join、window等进行运算。而结果也能保存在很多地方，如HDFS，数据库等。另外Spark Streaming也能和MLlib（机器学习）以及Graphx完美融合。

其内部工作方式如下：

Word Count示例

阅读全文>>

Fork/Join简介

Fork/Join的核心思想为分治算法：将一个规模较大的问题划分为同样性质但规模较小的若干子问题来求解，然后将子问题的结果汇总并输出最后的结果。Fork/Join框架执行任务时，检查该任务的规模大小，若大于设定的阀值，则划分为更小的子任务，然后继续用框架来执行。若划分后的子问题小于阀值则直接执行，若大于阀值则继续划分成更小的子问题。下图总结了这个概念：

核心操作

• fork操作：把任务分成更小的任务和使用这个框架执行它们。
• join操作：一个任务等待它创建的任务的结束。

特性

Work-stealing算法，类似Hadoop中的推测执行：一个先完成所有任务的线程会尝试着窃取其它线程中没有完成的任务来执行（任务队列尾部窃取）。这样做的好处是重用利用了并发多线程的优点，并减少了线程间的竞争。

阅读全文>>