机器学习方法概述

KNN k临近算法

遍历所有训练样本，求距离最近的点的结论，作为最后的预测结果

MR版：map求样本距离（key：样本，value：距离），combine求的最小值，是过滤功能，reduce就有一个求得距离最小值

 

贝叶斯：

贝叶斯定理公式：P(A|B)=P(B|A)*P(A)/P(B)

贝叶斯将在属性条件下的结论的概率转为：在结论条件下属性的概率的乘积*结论的概率

求得样本属性的在结论上的出现次数，样本结论的次数，商就是P(B|A)

MR版：map求拼接keyvalue（key：属性-结论  |结论，value：1）

              combine 求和（key：属性-结论  |结论，value：count）

              reduce和combine相同

 

决策树：

id3

香农熵 

 根据香农熵最大的来选择分裂特征，香农熵中的p(x)是在结论ci下xi的概率， 可以写成p(x,c|c);

 

c4.5

信息增益

p(c|c)-p(x,c|c)

信息增益率

p(c|c) - p(x,c|c) / p(x|x)

 

CART

 cart的决策树是二叉树，每次取特征值得规则是使得信息杂质最少

方法一：GINI 1- pow(yi/y,2)-pow(yi/y,2)

方法二：方差 pow(e-yi,2)+pow(e-yi,2)

 

 

 

SVM：

 SVM的原理是用超平面分割数据，不同分类在超平面的两侧；使得超平面离样本几何距离最大；

 使用对偶和梯度上升，调整超平面的参数W向量，使得所有样本都满足kkt条件

wx+b = 0 为超平面，wx+b=1和wx+b=-1为两类边界

 

 

 

logistic回归分类

是将y = 0|x<a;y=1|x>a 线性化为函数sigmod f(x) = 1/[1+e^(-x)]

 

使用坐标梯度上升求得参数w向量，求导后w := w + a(y-h(x))x ,其中a是每次梯度上升的步长，x是属性向量，h(x) = sigmod f(wx),不断循环进行梯队上升，知道w稳定或最大循环次数 

 

 

数值预测

线性回归

回归函数的确定，y=f(x) , 使得y-h(x)最小

方法一：使用梯度下降，求得w，同上

方法二：使用最小二阶乘

 

bagging 是用多个独立的分类器

 

boosting 是用多个分类器，分类器之间会有影响，后面的分类器会加重对前面分类错误的样本进行分类 

 

adaboost

是基于boosting，使用多个弱分类器，每个样本有权重D,每个弱分类器也有权重a

a = 正确分类的样本/所有样本

d = d*e^-a/sum(d) 正确的样本

d = d*e^a/sum(d) 错误的样本

 

随机森林：

进行行抽取，和列抽取

行抽取用可放回的抽取 m ，列抽数量是远远小于数据特征n<<N

 

聚类方法： 

kmeans

1.随机选择k个中心点

2.遍历所有训练样本，将样本分给距离最近的k点

3.遍历结束后更新k点，使其为所属样本的中心点

重复2,3步，知道k稳定，或循环次数到达阈值

 

二分kmeans

1.让所有样本属于一个集簇，求得中心点

2.用中心点二分所有样本，重新计算各自的中心点，选择误差最大的集簇作为下一个二分的数据集

重复 2操作，知道k点到达预期数，或误差到达阈值

 

canopy

canopy不是硬分类器，他有t1,t2,detal三个值，t1>t2

随机取一个样本为canopy，当d<t1时，样本在canopy中，并删除所有d<t2的样本，再进行循环

在mahout中，canopy不是删除样本这样实现的，mahout的mapper和reduce的操作一样，都是添加canopy中心点，当d<t1时，属于canopy中心点,当d>t2则新生成canopy中心点

 

mean shift

中心点漂移，有着梯度上升思想，不断优化中心点

mahout算法中用canopy修改，当d<t1时，属于canopy中心点，并记录此样本在canopy中，在reduce中增加一个操作，是跟新canopy属性，用canopy记录的样本去计算canopy中心点

 

fp-growth：

求频繁集合的算法，只用遍历数据集两次，就可建立fp树

遍历集合，求最小项集的出现次数

给所有样本内部排序，并且过滤掉出现次数小于阈值的项集

用排序好的数据建立fp树，树是字典树，节点是频繁集合的路径，值是路径出现次数

fp树建好后，使用header链表，自底向上获得频繁项

mahout的分布式fp：

第一次遍历样本一样，求最小项集的出现次数

根据排序的最小项集，分割项集，如a,b,c,d,e,f,g, 分割数据a,b,c,d,e,f,g;  c,d,e,f,g;  e f g; 这样频繁集合不会应为分片而丢失（可以理解为fp树从顶向下分割数据）

 

 基于项目的推荐算法：

计算人-物

计算物-物

获得物和物的相似矩阵

在用相似矩阵 * 人-物 ，就是人和其他物品的关联度