Mahout决策森林

时间:2024-01-21 12:12:57

Mahout决策森林算法

一、决策树

决策树(Decision Tree)是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的概率,评价项目风险,判断其可行性的决策分析方法,是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干,故称决策树。在机器学习中,决策树是一个预测模型,他代表的是对象属性与对象值之 间的一种映射关系。Entropy = 系统的凌乱程度,使用算法ID3,C4.5和C5.0生成树算法使用熵,这一度量是基于信息学理论中熵的概念。

决策树是数据挖掘分类算法的一个重要方法。在各种分类算法中,决策树是最直观的一种。下面是对于“Play golf dataset”数据集生成的决策树。

二、Bagging

两个著名的增强学习技术为Bagging和Boosting,它们都是构造多个分类器,并且最终的分类是由某种分类器的投票机制决定。Bagging和Boosting的区别在于,前者能够并行,而后者不行。对于不稳定的分类器,增强学习的方法可以显著提高分类效果;而对于稳定的分类器,用增强学习,有可能会降低分类的效果。稳定的分类器如:朴素贝叶斯,KNN,SVM等。不稳定的分类器如决策树,基于规则的分类。

给定一个有个样例的训练集合和一个基本的分类算法。Bagging的实现步骤如下。

训练:

生成K个样本集合,每个样本集合都有放回的从D中随机抽取得到。这样的一个样本集合成为原始训练样本D的一个自展复制。每个样本平均含有原始样本的63.2%,其中一个样本有可能重复出现。

对每一个样本集都构造一个分类器,将得到k个分类器。

测试:

对测试样例进行分类,由k个分类投票(由权重),占多数的类别将被赋予该测试样例。

三、决策森林

机器学习中,随机森林是一个包含多个决策树分类器
并且其输出的类别是由个别树输出的类别的众数而定。Leo
Breiman
Adele Cutler发展出推论出随机森林的算法。 而 "Random Forests" 是他们的商标
这个术语是1995年由贝尔实验室的Tin Kam Ho所提出的随机决策森林(random decision forests)而来的。这个方法则是结合 Breimans 的 "Bootstrapaggregating"
想法和 Ho 的"randomsubspace method" 以建造决策树的集合。

根据下列算法而建造每棵树:

(1)用 N 来表示训练用例(样本)的个数,M表示特征数目。

(2)输入特征数目 m ,用于确定决策树上一个节点的决策结果;其中m应远小于M。

(3)从N个训练用例(样本)中以有放回抽样的方式,取样N次,形成一个训练集(即bootstrap取样),并用未抽到的用例(样本)作预测,评估其误差。

(4)对于每一个节点,随机选择m个特征,决策树上每个节点的决定都是基于这些特征确定的。根据这 m 个特征,计算其最佳的分裂方式。

(5)每棵树都会完整成长而不会剪枝(Pruning)(这有可能在建完一棵正常树状分类器后会被采用)。

所以“决策树+Bagging=决策森林”。

决策树算法的优点:

1.        在数据集上表现良好。

2.        在当前的很多数据集上,相对其他算法有着很大的优势。

3.        它能够处理很高维度(feature很多)的数据,并且不用做特征选择。

4.        在训练完后,它能够给出哪些feature比较重要。

5.        在创建随机森林的时候,对generlization error使用的是无偏估计。

6.        训练速度快。

7.        在训练过程中,能够检测到feature间的互相影响。

8.        容易做成并行化方法。

9.        实现比较简单。

四、MapReduce实现决策森林

训练:

(1)用随机抽样的方法抽取多组固定个数的特征属性集S={F1,F2,...Fn}.

(2)输入数据集,Hadoop自动划分到各个节点;将特征集用DistributeCache发送到各个执行Task的节点。

(3)每个节点Map中根据特征属性集,以及数据信息,分别统计不同决策树节点分支的信息,构建决策树。该过程构造的决策树不需要做剪枝。

分类:

将构建好的K个决策树,用DistributeCache发送到各个节点。

在Map中通过K个决策树表决,得到分类信息。

五、API说明

示例数据:(Iris数据)

萼片长度,萼片宽度,花瓣长度,花瓣宽度,类型

5.1, 3.5, 1.4, 0.2, Iris-setosa

4.9, 3.0, 1.4, 0.2, Iris-setosa

4.7, 3.2, 1.3, 0.2, Iris-setosa

4.6, 3.1, 1.5, 0.2, Iris-setosa

5.0, 3.6, 1.4, 0.2, Iris-setosa

5.4, 3.9, 1.7, 0.4, Iris-setosa

4.6, 3.4, 1.4, 0.3, Iris-setosa

5.0, 3.4, 1.5, 0.2, Iris-setosa

4.4, 2.9, 1.4, 0.2, Iris-setosa

4.9, 3.1, 1.5, 0.1, Iris-setosa

5.4, 3.7, 1.5, 0.2, Iris-setosa

4.8, 3.4, 1.6, 0.2, Iris-setosa

4.8, 3.0, 1.4, 0.1, Iris-setosa

4.3, 3.0, 1.1, 0.1, Iris-setosa

5.8, 4.0, 1.2, 0.2, Iris-setosa

5.7, 4.4, 1.5, 0.4, Iris-setosa

5.4, 3.9, 1.3, 0.4, Iris-setosa

5.1, 3.5, 1.4, 0.3, Iris-setosa

5.7, 3.8, 1.7, 0.3, Iris-setosa

5.1, 3.8, 1.5, 0.3, Iris-setosa

5.4, 3.4, 1.7, 0.2, Iris-setosa

5.1, 3.7, 1.5, 0.4, Iris-setosa

4.6, 3.6, 1.0, 0.2, Iris-setosa

5.1, 3.3, 1.7, 0.5, Iris-setosa

4.8, 3.4, 1.9, 0.2, Iris-setosa

5.0, 3.0, 1.6, 0.2, Iris-setosa

5.0, 3.4, 1.6, 0.4, Iris-setosa

5.2, 3.5, 1.5, 0.2, Iris-setosa

5.2, 3.4, 1.4, 0.2, Iris-setosa

4.7, 3.2, 1.6, 0.2, Iris-setosa

4.8, 3.1, 1.6, 0.2, Iris-setosa

5.4, 3.4, 1.5, 0.4, Iris-setosa

5.2, 4.1, 1.5, 0.1, Iris-setosa

5.5, 4.2, 1.4, 0.2, Iris-setosa

4.9, 3.1, 1.5, 0.1, Iris-setosa

5.0, 3.2, 1.2, 0.2, Iris-setosa

5.5, 3.5, 1.3, 0.2, Iris-setosa

4.9, 3.1, 1.5, 0.1, Iris-setosa

4.4, 3.0, 1.3, 0.2, Iris-setosa

5.1, 3.4, 1.5, 0.2, Iris-setosa

5.0, 3.5, 1.3, 0.3, Iris-setosa

4.5, 2.3, 1.3, 0.3, Iris-setosa

4.4, 3.2, 1.3, 0.2, Iris-setosa

5.0, 3.5, 1.6, 0.6, Iris-setosa

5.1, 3.8, 1.9, 0.4, Iris-setosa

4.8, 3.0, 1.4, 0.3, Iris-setosa

5.1, 3.8, 1.6, 0.2, Iris-setosa

4.6, 3.2, 1.4, 0.2, Iris-setosa

5.3, 3.7, 1.5, 0.2, Iris-setosa

5.0, 3.3, 1.4, 0.2, Iris-setosa

7.0, 3.2, 4.7, 1.4, Iris-versicolor

6.4, 3.2, 4.5, 1.5, Iris-versicolor

6.9, 3.1, 4.9, 1.5, Iris-versicolor

5.5, 2.3, 4.0, 1.3, Iris-versicolor

6.5, 2.8, 4.6, 1.5, Iris-versicolor

5.7, 2.8, 4.5, 1.3, Iris-versicolor

6.3, 3.3, 4.7, 1.6, Iris-versicolor

4.9, 2.4, 3.3, 1.0, Iris-versicolor

6.6, 2.9, 4.6, 1.3, Iris-versicolor

5.2, 2.7, 3.9, 1.4, Iris-versicolor

5.0, 2.0, 3.5, 1.0, Iris-versicolor

5.9, 3.0, 4.2, 1.5, Iris-versicolor

6.0, 2.2, 4.0, 1.0, Iris-versicolor

6.1, 2.9, 4.7, 1.4, Iris-versicolor

5.6, 2.9, 3.6, 1.3, Iris-versicolor

6.7, 3.1, 4.4, 1.4, Iris-versicolor

5.6, 3.0, 4.5, 1.5, Iris-versicolor

5.8, 2.7, 4.1, 1.0, Iris-versicolor

6.2, 2.2, 4.5, 1.5, Iris-versicolor

5.6, 2.5, 3.9, 1.1, Iris-versicolor

5.9, 3.2, 4.8, 1.8, Iris-versicolor

6.1, 2.8, 4.0, 1.3, Iris-versicolor

6.3, 2.5, 4.9, 1.5, Iris-versicolor

6.1, 2.8, 4.7, 1.2, Iris-versicolor

6.4, 2.9, 4.3, 1.3, Iris-versicolor

6.6, 3.0, 4.4, 1.4, Iris-versicolor

6.8, 2.8, 4.8, 1.4, Iris-versicolor

6.7, 3.0, 5.0, 1.7, Iris-versicolor

6.0, 2.9, 4.5, 1.5, Iris-versicolor

5.7, 2.6, 3.5, 1.0, Iris-versicolor

5.5, 2.4, 3.8, 1.1, Iris-versicolor

5.5, 2.4, 3.7, 1.0, Iris-versicolor

5.8, 2.7, 3.9, 1.2, Iris-versicolor

6.0, 2.7, 5.1, 1.6, Iris-versicolor

5.4, 3.0, 4.5, 1.5, Iris-versicolor

6.0, 3.4, 4.5, 1.6, Iris-versicolor

6.7, 3.1, 4.7, 1.5, Iris-versicolor

6.3, 2.3, 4.4, 1.3, Iris-versicolor

5.6, 3.0, 4.1, 1.3, Iris-versicolor

5.5, 2.5, 4.0, 1.3, Iris-versicolor

5.5, 2.6, 4.4, 1.2, Iris-versicolor

6.1, 3.0, 4.6, 1.4, Iris-versicolor

5.8, 2.6, 4.0, 1.2, Iris-versicolor

5.0, 2.3, 3.3, 1.0, Iris-versicolor

5.6, 2.7, 4.2, 1.3, Iris-versicolor

5.7, 3.0, 4.2, 1.2, Iris-versicolor

5.7, 2.9, 4.2, 1.3, Iris-versicolor

6.2, 2.9, 4.3, 1.3, Iris-versicolor

5.1, 2.5, 3.0, 1.1, Iris-versicolor

5.7, 2.8, 4.1, 1.3, Iris-versicolor

6.3, 3.3, 6.0, 2.5, Iris-virginica

5.8, 2.7, 5.1, 1.9, Iris-virginica

7.1, 3.0, 5.9, 2.1, Iris-virginica

6.3, 2.9, 5.6, 1.8, Iris-virginica

6.5, 3.0, 5.8, 2.2, Iris-virginica

7.6, 3.0, 6.6, 2.1, Iris-virginica

4.9, 2.5, 4.5, 1.7, Iris-virginica

7.3, 2.9, 6.3, 1.8, Iris-virginica

6.7, 2.5, 5.8, 1.8, Iris-virginica

7.2, 3.6, 6.1, 2.5, Iris-virginica

6.5, 3.2, 5.1, 2.0, Iris-virginica

6.4, 2.7, 5.3, 1.9, Iris-virginica

6.8, 3.0, 5.5, 2.1, Iris-virginica

5.7, 2.5, 5.0, 2.0, Iris-virginica

5.8, 2.8, 5.1, 2.4, Iris-virginica

6.4, 3.2, 5.3, 2.3, Iris-virginica

6.5, 3.0, 5.5, 1.8, Iris-virginica

7.7, 3.8, 6.7, 2.2, Iris-virginica

7.7, 2.6, 6.9, 2.3, Iris-virginica

6.0, 2.2, 5.0, 1.5, Iris-virginica

6.9, 3.2, 5.7, 2.3, Iris-virginica

5.6, 2.8, 4.9, 2.0, Iris-virginica

7.7, 2.8, 6.7, 2.0, Iris-virginica

6.3, 2.7, 4.9, 1.8, Iris-virginica

6.7, 3.3, 5.7, 2.1, Iris-virginica

7.2, 3.2, 6.0, 1.8, Iris-virginica

6.2, 2.8, 4.8, 1.8, Iris-virginica

6.1, 3.0, 4.9, 1.8, Iris-virginica

6.4, 2.8, 5.6, 2.1, Iris-virginica

7.2, 3.0, 5.8, 1.6, Iris-virginica

7.4, 2.8, 6.1, 1.9, Iris-virginica

7.9, 3.8, 6.4, 2.0, Iris-virginica

6.4, 2.8, 5.6, 2.2, Iris-virginica

6.3, 2.8, 5.1, 1.5, Iris-virginica

6.1, 2.6, 5.6, 1.4, Iris-virginica

7.7, 3.0, 6.1, 2.3, Iris-virginica

6.3, 3.4, 5.6, 2.4, Iris-virginica

6.4, 3.1, 5.5, 1.8, Iris-virginica

6.0, 3.0, 4.8, 1.8, Iris-virginica

6.9, 3.1, 5.4, 2.1, Iris-virginica

6.7, 3.1, 5.6, 2.4, Iris-virginica

6.9, 3.1, 5.1, 2.3, Iris-virginica

5.8, 2.7, 5.1, 1.9, Iris-virginica

6.8, 3.2, 5.9, 2.3, Iris-virginica

6.7, 3.3, 5.7, 2.5, Iris-virginica

6.7, 3.0, 5.2, 2.3, Iris-virginica

6.3, 2.5, 5.0, 1.9, Iris-virginica

6.5, 3.0, 5.2, 2.0, Iris-virginica

6.2, 3.4, 5.4, 2.3, Iris-virginica

5.9, 3.0, 5.1, 1.8, Iris-virginica

生成数据描述文件

DirichletDriver.main(args);

--path (-p)

数据路径

--file (-f)

生成的描述文件路径

--descriptor (-d)

描述。I 表示忽略该属性,N表示数值类型属性,C表示类别类型属性,L表示类型

该数据四个数值属性,一个类型。描述字符串为,“4NL”

String  [] args={"-p","df/iris.data","-f","df/iris.info","-d","4","N","L"};

Describe.main(args);

训练API

Describe.main(args);

--oob

可选值,表示是否估计out-of-bag错误

--data (-d)

输入路径

--dataset (-ds)

数据表述文件路径

--selection (-sl)

每棵树随机选取的属性数

--seed (-sd)

可选值,随机数种子

--partial (-p)

是否由部分数据生成树

--nbtrees (-t)

树的棵树

--output (-o)

输出模型路径

 

训练示例

public void train() throws Exception{

String   [] args ={"-d","df/iris.data","-ds","df/iris.info",

"-sl","3","-p","-t","10","-o","df/irismodel"};

BuildForest.main(args);

}

 

测试、分类API

TestForest.main(args);

--input (-i)

输入路径

--dataset (-ds) dataset

数据表述文件路径

--model (-m) path

模型路径

--output (-o)

输出路径

--analyze (-a)

是否分析测试结果

--mapreduce (-mr)

用MapReduce模式运行

 

测试、分类示例

String  [] arg ={"-i","df/iris.data","-ds","df/iris.info",

"-m","df/irismodel","-o","df/iris.out","-a","-mr"};

TestForest.main(arg);

 

评估结果

Summary

-------------------------------------------------------

Correctly Classified Instances          :        150             100%

Incorrectly Classified Instances        :          0          0%

Total Classified Instances              :        150

=======================================================

Confusion Matrix

-------------------------------------------------------

a         b         c         d         <--Classified as

50        0         0         0          |  50        a     = Iris-setosa

0         50        0         0          |  50        b     = Iris-versicolor

0         0         50        0          |  50        c     = Iris-virginica

0         0         0         0          |  0         d     = unknown

Default Category: unknown: 3

 

分类结果:0,1,2分别表示类型为Iris-setosa,Iris-versicolor和Iris-virginica.

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

 

 

 

 

 

 

 

 

六、参考文档

1.《 Random Forest -Classification and Regression By Random Forest》

2.《基于云计算平台的随机森林算法的研究与实现》

2.博客:http://blog.csdn.net/abcjennifer/article/details/8164315