Random Forest可以用来做聚类?

  统计/机器学习 无监督学习 随机森林    浏览次数:2871        分享
13

Random Forests一般是用来做分类问题的,听说它可以用来做clustering?我没搜到相关的内容,不知道这里有没有大神知道的。愿听详闻!谢谢!

 

擒贼先擒鱼   2017-03-19 13:24



   3个回答 
30

这是个很诡异的问题,看到后面你就知道为什么诡异了。首先声明一下,Random Forests的发明人Leo Breiman说Random Forest是可以做聚类的,具体可参考(Random forest clustering-Leo Brieman)。

那下面解释一下Brieman用RF做Clustering的神奇步骤。

其实@雷猴 说的并没有错,RF的确是监督式学习,的确是需要标签的。所以...

第一步:生成假冒数据和临时标签。

我们先给原数据集增加一列,名叫“标签”,原生数据每一行的标签都是“1”。下面生成一些假数据,假数据的每一列都是从原生数据中根据其经验分布随机产生的,人工合成的数据的标签是“0”。举个例子,

标签 身高 体重 年龄

1 184 158 25

1 170 162 37

1 165 132 45

1 110 78 9

1 145 100 14

1 ... ... ...

上面是原生数据,下面我们开始制造虚假数据

标签 身高 体重 年龄

1 184 158 25

1 170 162 37

1 165 132 45

1 110 78 9

1 145 100 14

1 ... ... ...

0 170 100 9

0 110 162 37

0 165 158 14

每行假数据的每一个元素都是从它所在的那一列中随机抽取的,列和列之间的抽取是独立的。这样一来,人工合成的假数据就破坏了原有数据的结构性。现在我们的数据集和标签就生成完了。

第二步:用该数据集训练Random Forest并获得样本间的临近性(proximity)。

假设原生样本有N行,我们再生成M个假数据。现在我们就有了带标签的样本之后就可以用它训练出一个Random Forest。Random Forest在训练的同时,可以返回样本之间的临近性(proximity,两个样本出现在树杈同一节点的频率越高,它们就越临近)。我们就有了一个(N+M)x(N+M)的临近矩阵(这是个对称矩阵)。把与假数据相关的M行、M列去掉,我们就得到了NxN的矩阵,矩阵的第i行第j列的数值就是原生数据中第i个样本和第j个样本之间的临近性。

第三步:根据每个样本点两两之间的临近性来聚类。

这个是最后一步,也是我认为诡异的一步。我们可以用两两之间的临近性当做两两之间的距离,然后再利用常规的聚类算法,比如层次聚类法(Hierarchical clustering),就可以完成对原样本的聚类。


以上就是Brieman的关于用Random Forest做聚类的思想。但是怎么说呢,我觉得Random Forest在上面的聚类步骤中更像是一个生成距离的手段。这有点像PCA,PCA也可以参与聚类,但是参与完了之后,需要用肉眼或者其他方法去划一条分界线。


SofaSofa数据科学社区DS面试题库 DS面经

高代兄   2017-03-21 09:37

原来如此!我也是头一次听说。。。 - batmanX   2017-03-27 00:06
大家共同学习!共同进步! - 高代兄   2017-03-28 08:11
用RF做聚类。。。刷新我三观 - 开门呀是我   2017-04-13 11:31
有没有随机森林聚类的相关学习资料,给推荐推荐 - codeants   2017-04-14 12:37
这个还真没有,我能找到的资料也就只有我回答里第一段的那个链接 - 高代兄   2017-04-14 12:46
好的,文章中所说的proximity,是说对每棵树而言,两个样本的分在同一类时,它们的proximity就加一吗?最后除以总的树的个数?是这样的吗? - codeants   2017-04-20 17:16
谢谢,请大神指点指点!!!不胜感激!!! - codeants   2017-04-20 17:17
准确地说不是同一类,而是同一个最终节点。换句话,两个样本在一个棵树中,经历了完全一样的路线(从根部到最外部的叶子),那么它们的prox+1 - 高代兄   2017-04-20 21:15
我写着写着,遇到一个问题,最终生成一个prox矩阵,那岂不是最终最多只能处理5000条数据。多了矩阵就存不下了。 - codeants   2017-04-25 15:32
如果再去掉假数据,那么最终只能处理2500条数据了 - codeants   2017-04-25 15:34
@高代兄,有什么建议吗? - codeants   2017-04-25 15:35
为什么只存得下5000多行?而且这个矩阵应该是稀疏的,不会太占空间。不知道你用的什么语言写得 - 高代兄   2017-04-25 21:03
java - codeants   2017-05-06 19:42
请问如何用随机森林获得样本之间临近性... - cmq2525   2017-12-06 16:41
2

根据高代兄的解说,说下RF做cluster的理解。Hierarchy clustering或Kmeans,最主要是要计算两点间距离或相似性。树结构可以用来生成相似性。一棵树主要目的就是把数据空间非线性的分为$K$份,$K$为叶节点个数。每一个叶节点就是一个cluster。根据breiman的定义,两个点在同一个叶节点,则相似性+1。我们对叶节点编号k=1,2,...,K,对数据点i在某叶节点的信息进行$K$位one-hot编码$x_i$,则数据点i和j的相似性$S_{ij}=x_i^Tx_j$。这个one-hot编码相当于新造的特征(feature),用一位binary的数据代替叶节点中的所有点。其实这个one-hot编码是一个kernel function。我们计算的是kernel space上的相似性。

因为RF有M棵树,这样的one-hot编码一共M组,合并为一组总编码$x_i'=[x_{i,1};x_{i,2};...;x_{i,M} ]$,最后两点间相似度为$S_{ij}=\sum_{m=1}^{M}S_{ij,m}=x_i'^Tx_j'$。

有几点想法:

1.最后相似性是由RF的$KM$维新特征(M组one-hot)上得到的。其实也可以加上原始数据中的相似性衡量(比如L2距离)。

2.造synthetic data来训练RF,有一个假设条件是新造的数据只有很小概率在原始数据附近。如果假设不成立,不知道结果如何。


SofaSofa数据科学社区DS面试题库 DS面经

Zealing   2018-10-02 02:35

-1

随机森林不可以用来做无监督学习,因为它需要用标签来训练一棵棵随机的决策树。

SofaSofa数据科学社区DS面试题库 DS面经

雷猴   2017-03-20 11:20



  相关主题

Random Forest和Tree Bagging什么区别?   2回答

Extra Tree算法   1回答

Gradient tree boosting和random forest (随机森林) 有什么区别和联系   1回答

Adaboost里的树有没有可能权重是负数?   1回答

python sklean中的决策树是用的哪一种决策树算法?   2回答

决策回归树   2回答

决策树怎么做增量学习或者online学习?   1回答

决策树是如何得到量化的概率,不只是0或1的标签?   2回答

决策树的深度和数据特征个数的关系   1回答

剪枝是什么意思   1回答

随机森林中增加树的数量对于偏差和方差的影响   2回答

关于knn算法中kd树的问题   1回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!