Random Forest可以用来做聚类?

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

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

 

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



   3个回答 
29

这是个很诡异的问题,看到后面你就知道为什么诡异了。首先声明一下,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也可以参与聚类,但是参与完了之后,需要用肉眼或者其他方法去划一条分界线。


高代兄   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
1

根据高代兄的解说,说下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,有一个假设条件是新造的数据只有很小概率在原始数据附近。如果假设不成立,不知道结果如何。


Zealing   2018-10-02 02:35

-1

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

雷猴   2017-03-20 11:20



  相关主题

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

随机森林会发生过拟合(overfitting)吗?   1回答

求问:Cart分类树为什么是基尼指数最小化准则   1回答

决策树算法ID3,C4.5和CART的特点、异同?   3回答

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

决策树剪枝有什么策略或者注意事项?   2回答

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

决策树的熵是什么?怎么用熵来选分叉?   1回答

决策树可以做多元分类吗?   1回答

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

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

Extra Tree算法   1回答



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

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

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

我们谢绝答非所问。

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

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