数据挖掘——RainForest 算法学习

最近状态、情绪不由来的太糟糕了!

向影响到身边的人道歉,特指钟泠韵,最近辛苦她了

RainForest 算法的出现

之前学习的决策树算法比如 ID3、C4.5、CART 算法等,它们在构建决策树都是将数据集读到内存中来,这就引发了一个问题——当遇到比较大的数据集时,无法全部读到内存中,构建速度就非常慢了。

RainForest 算法就可以解决这个内存问题,这是一种具有可伸缩性的决策树算法框架。

并且可以在这个算法框架上运用任意决策树构建算法(比如 ID3,C4.5、CART、SPRINT 等等)。

RainForest 算法的数据结构

RainForest 算法采用的数据结构有两种:

  • AVC-set:节点 N 包含的所有记录在某个属性上的投影,其中该 AVC-set 包括了属性的不同值在每个类别上的计数。
  • AVC-group:就是一个结点上所有 AVC-set 的集合。

RainForest 在每个节点,对每个属性维护一个 AVC-set(AVC 表示“属性-值,类标号”),描述该节点的训练元组。

AVC-set 所占内存大小「正比于」对应属性的不同值的个数,AVC-group 不是数据库信息的简单压缩,他只提供建立决策树需要的统计信息,所以 AVC-group 所占用的内存空间远远小于数据库所实际占用的空间。

一个 AVC-set 就是这样:

age buys_computer
yes no
youth 2 3
middle_aged 4 0
senior 3 2

由于在每个节点只存储数据的统计信息,而不是真正的数据,对于非常大的数据集上的决策树归纳,RainForest 方法具有很好的可伸缩性。

RainForest 算法的过程

  • 建立每个节点的 AVC-group(通过读取整个原始数据库或者某个分支的数据表或文件)
  • 逐一检查 AVC-set 选择分裂属性和分裂标准(这点就取决于选择的算法是ID3,C4.5等等)
  • 将数据分解到各个子节点,建立一个或多个子节点的 AVC-group

RainForest 算法的优点

RainForest 算法框架,可以减少算法的内存占用,加快执行速度。

但是准确性由使用此框架的算法决定,比如说可以运用在该框架上的 Sprint 算法。

加速「参数选择过程」的计算。