随机投影森林-一种近似最近邻方法（ANN）

本文主要是介绍随机投影森林-一种近似最近邻方法（ANN），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

转载自：http://blog.sina.com.cn/s/blog_7103b28a0102w1ny.html

当数据个数比较大的时候，线性搜索寻找KNN的时间开销太大，而且需要读取所有的数据在内存中，这是不现实的。因此，实际工程上，使用近似最近邻也就是ANN问题。其中一种方法是利用随机投影树，对所有的数据进行划分，将每次搜索与计算的点的数目减小到一个可接受的范围，然后建立多个随机投影树构成随机投影森林，将森林的综合结果作为最终的结果。

建立一棵随机投影树的过程大致如下（以二维空间为例）：

随机选取一个从原点出发的向量，与这个向量垂直的直线将平面内的点划分为了两部分，将属于这两部分的点分别划分给左子树和右子树。在数学计算上，是通过计算各个点与垂直向量的点积完成这一步骤的，点积大于零的点划分到左子树，点积小于零的点划分到右子树。注意一点，图中不带箭头的直线是用于划分左右子树的依据，带箭头的向量是用于计算点积的。这样，原有的点就划分为了两部分，图例如下：

但是此时一个划分结果内的点的数目还是比较多，因此继续划分。再次随机选取一个向量，与该向量垂直的直线将所有点进行了划分。图例如下：

注意一点，此时的划分是在上一次划分的基础上进行的。也就是说现在图中的点已经被划分成了四部分，对应于一棵深度为2，有四个叶节点的树。以此类推继续划分下去，直到每个叶节点中点的数目都达到一个足够小的数目。注意这棵树并不是完全树。

利用这棵树对新的点进行最近邻计算时，首先通过计算该点与每次划分所用向量的点积，来找到其所属于的叶节点，然后利用这个叶节点内的这些点进行最近邻算法的计算。这个过程是一棵随机投影树的计算过程，利用同样的方法，建立多个随机投影树构成随机森林，将森林的总和结果作为最终的结果。

python中可以完成这个功能的模块包括RPForest和sklearn.neighbors中的LSHForest。

下面这篇讲的更加形象一些，转自：http://blog.csdn.net/armily/article/details/8923961

在机器学习中，随机森林由许多的决策树组成，因为这些决策树的形成采用了随机的方法，因此也叫做随机决策树。随机森林中的树之间是没有关联的。当测试数据进入随机森林时，其实就是让每一颗决策树进行分类，最后取所有决策树中分类结果最多的那类为最终的结果。因此随机森林是一个包含多个决策树的分类器，并且其输出的类别是由个别树输出的类别的众数而定。随机森林可以既可以处理属性为离散值的量，比如ID3算法，也可以处理属性为连续值的量，比如C4.5算法。另外，随机森林还可以用来进行无监督学习聚类和异常点检测。

　随机森林由决策树组成，决策树实际上是将空间用超平面进行划分的一种方法，每次分割的时候，都将当前的空间一分为二，比如说下面的决策树（其属性的值都是连续的实数）：

　　将空间划分为成的样子为：

　　随机深林的优点：比较适合做多分类问题；训练和预测速度快；对训练数据的容错能力，是一种有效地估计缺失数据的一种方法，当数据集中有大比例的数据缺失时仍然可以保持精度不变；能够有效地处理大的数据集；可以处理没有删减的成千上万的变量；能够在分类的过程中可以生成一个泛化误差的内部无偏估计；能够检测到特征之间的相互影响以及重要性程度；不过出现过度拟合；实现简单容易并行化。

　　下面是具体决策树的生成过程：

　　其中关于信息增益这里就不作具体的介绍，反正信息增益越大，就说明那个属性相对来说越重要。流程图中的identical values 可以理解为是分类值，离散值，就是它本身不具备数值的意义，比如说颜色分为红，绿，蓝等，是人为给它标定的一个离散值而已。流程图中的real values可以理解为连续的实数，也就是说属性本身是具有数值的，比如说物体的长度，这就是一个real value，在进行这种连续值属性构造决策数时，需要按照属性值的范围进行生成子节点。

　　当可以生成好决策树后，就比较容易生成随机森林了。下面是随机森林的构造过程：

　　1. 假如有N个样本，则有放回的随机选择N个样本(每次随机选择一个样本，然后返回继续选择)。这选择好了的N个样本用来训练一个决策树，作为决策树根节点处的样本。

　　2. 当每个样本有M个属性时，在决策树的每个节点需要分裂时，随机从这M个属性中选取出m个属性，满足条件m << M。然后从这m个属性中采用某种策略（比如说信息增益）来选择1个属性作为该节点的分裂属性。

　　3. 决策树形成过程中每个节点都要按照步骤2来分裂（很容易理解，如果下一次该节点选出来的那一个属性是刚刚其父节点分裂时用过的属性，则该节点已经达到了叶子节点，无须继续分裂了）。一直到不能够再分裂为止。注意整个决策树形成过程中没有进行剪枝。

　　4. 按照步骤1~3建立大量的决策树，这样就构成了随机森林了。

　　从上面的步骤可以看出，随机森林的随机性体现在每颗数的训练样本是随机的，树中每个节点的分类属性也是随机选择的。有了这2个随机的保证，随机森林就不会产生过拟合的现象了。

　　随机森林有2个参数需要人为控制，一个是森林中树的数量，一般建议取很大。另一个是m的大小，推荐m的值为M的均方根。

　　参考资料:

决策树模型组合之随机森林与GBDT

random forest

http://en.wikipedia.org/wiki/Random_forest

作者：tornadomeet 出处：http://www.cnblogs.com/tornadomeet 欢迎转载或分享，但请务必声明文章出处。