高維數(shù)據(jù)下決策樹的快速構造.pdf

1、從數(shù)據(jù)中挖掘知識和信息已成為解決許多實際問題的重要手段。決策樹是最常用的數(shù)據(jù)挖掘算法之一。但現(xiàn)有決策樹算法處理高維數(shù)據(jù)時存在計算量大、資源占用多的缺點。本論文面向高維數(shù)據(jù)，研究決策樹的快速構造方法。首先，為減少構建決策樹的計算量，我們提出了基于混淆度的啟發(fā)式決策樹構建算法。該算法利用父節(jié)點的計算結果估計部分子節(jié)點的上界，從而削減了找到子節(jié)點最優(yōu)解的計算量。實驗結果表明無論是單棵決策樹還是集成決策樹，該算法都不會對決策樹的模型準確度、概念

2、簡潔性造成負面影響，并且在數(shù)據(jù)維度大于1000的高維情形下可以降低約70％的計算量。其次，為優(yōu)化決策樹構建過程中的資源占用和磁盤負載，我們提出了一種基于橫縱劃分的決策樹并行構造方式。和傳統(tǒng)方法相比，該方法的集群內存占用量從O(T)降為O(√T)，其中T是并行進程數(shù)。對應的單并行進程的內存占用量從O(1)降至O（1/√T），即集群的擴大和并行數(shù)的增加可以降低單進程的內存占用量。數(shù)學分析和實驗結果表明，該方法對網絡通信量、磁盤讀寫量、計算量