1. Intro
- 和其他分類方法相比，建立Decision tree更快絮识，而且有時(shí)候能夠獲得相近或者更高的準(zhǔn)確率
- 但是绿聘，決策樹(shù)的并行實(shí)現(xiàn)有幾個(gè)難點(diǎn)：樹(shù)的形狀是不規(guī)則，而且是運(yùn)行時(shí)才確定的次舌， static的分配策略會(huì)造成imbalance問(wèn)題熄攘；樹(shù)的一個(gè)node的子node并行執(zhí)行時(shí)，它們需要父節(jié)點(diǎn)的部分?jǐn)?shù)據(jù)垃它，因此需要processor間data移動(dòng)鲜屏，如果數(shù)據(jù)劃分的不夠好烹看，poor locality會(huì)降低性能
2. Related Work
2.1. Task parallelism
- 將決策樹(shù)的node分配到不同的processor上
- 缺點(diǎn)是国拇， bad load balance，因?yàn)椴煌琾rocessor處理的樹(shù)的大小是不一致的
2.2. Data parallelism
- 將訓(xùn)練數(shù)據(jù)劃分到不同的processor上惯殊，劃分策略有水平劃分和垂直劃分
- 垂直劃分酱吝，一個(gè)processor處理訓(xùn)練數(shù)據(jù)的一部分屬性。垂直劃分還是有l(wèi)oad imbalance的問(wèn)題土思，因?yàn)檫B續(xù)屬性與離散屬性相比务热，需要更多的計(jì)算
- 水平劃分，將數(shù)據(jù)平均劃分到processor上己儒。需要在不同processor間通信以獲得最佳的split崎岂；對(duì)每個(gè)屬性，建立獨(dú)立的value list闪湾；每個(gè)node進(jìn)行split時(shí)冲甘，在不同processor之間有很高的通信負(fù)擔(dān)
2.3. Hybrid parallelism
- 同時(shí)使用Task parallelism和Data parallelism
3. C4.5 parallel implementation
- 水平劃分策略，與SLIQ (SPRINT: A scalable parallel classifier for data mining)類似
- 連續(xù)屬性的lists途样，根據(jù)屬性的值江醇，進(jìn)行全局的sorting
- C4.5的limitation：對(duì)連續(xù)屬性，每個(gè)node反復(fù)地sort訓(xùn)練examples
- 并行tree構(gòu)建過(guò)程主要是兩個(gè)問(wèn)題：split和找到最佳的split
- 每個(gè)processor統(tǒng)計(jì)本地?cái)?shù)據(jù)的每個(gè)屬性的分布情況何暇，然后發(fā)送給其他的processor陶夜；最佳split找到后，創(chuàng)建child node裆站，相應(yīng)地劃分?jǐn)?shù)據(jù)
- 為每個(gè)屬性建立獨(dú)立的list条辟，這樣能夠避免每次evaluate一個(gè)連續(xù)屬性時(shí)都要重復(fù)排序
- SPRINT避免保存class list黔夭，把屬性list擴(kuò)展其他兩個(gè)fields，訓(xùn)練數(shù)據(jù)的class label和global index
