1、SLIQ：一種快速可伸縮分類器Manish Mehta, Rakesh Agrawal, Jorma RissanenIBM Almaden Research Center, 1996報告人：郭新濤2003.03.291內(nèi)容摘要決策樹算法SLIQ算法數(shù)據(jù)結(jié)構(gòu)預(yù)排序與廣度優(yōu)先增長策略種類型字段的最佳子集生成方法MDL剪枝SLIQ性能評估21. 決策樹算法決策樹算法SLIQ算法數(shù)據(jù)結(jié)構(gòu)預(yù)排序與廣度優(yōu)先增長策略種類型字段的最佳子集生成方法MDL剪枝SLIQ性能評估31. 決策樹算法什么是分類（Classification）？訓(xùn)練集待測試樣本集可伸縮性（Scalability）大多數(shù)分類算法面臨的共同

2、問題：訓(xùn)練集受內(nèi)存容量的限制。算法可伸縮性的優(yōu)勢：更高的準(zhǔn)確性設(shè)計目標(biāo)：一個可伸縮的分類器41. 決策樹算法什么是決策樹（Decision Tree）？決策樹的優(yōu)點與其他分類方法相比相對較快容易轉(zhuǎn)化為分類規(guī)則，也容易轉(zhuǎn)化為SQL查詢近似的或者更好的準(zhǔn)確度51. 決策樹算法算法建樹階段MakeTree (Training Data T) Partition (T);Partition (Data S) if (all points in S are in the same class) then return; evaluate splits for each attribute A Use b

3、est split found to partition S into S1 and S2; Partition (S1); Partition (S2);剪枝階段為什么剪枝：訓(xùn)練數(shù)據(jù)中的“噪聲”影響最終模型的準(zhǔn)確性。這些錯誤的枝條將導(dǎo)致利用模型時的分類錯誤。剪枝的方法：去除那些導(dǎo)致錯誤的枝條，在可能的自述中挑選出錯率最小的字樹。這一步是整個算法中時間消耗最大的部分61. 決策樹算法可伸縮性問題研討（1）設(shè)計目標(biāo)：一個可伸縮的、能夠處理大數(shù)據(jù)集的決策樹以前的可伸縮性方案數(shù)據(jù)采樣連續(xù)屬性的離散化數(shù)據(jù)分成若干小塊，分別構(gòu)建決策樹，然后綜合成一棵最終的樹面臨的問題：降低了準(zhǔn)確性7決策樹算法可伸縮性問

4、題研討（2）建樹階段關(guān)鍵：提高“確定最佳分裂（Best Split ）”的可伸縮性分裂指標(biāo)舉例 ，計算開銷不大數(shù)值型字段，最佳分裂型如 ，開銷主要是排序種類型字段，最佳分裂型如 ，開銷主要是尋找最佳的子集（遍歷所有子集，時間復(fù)雜度為指數(shù)級）。81. 決策樹算法可伸縮性問題研討（3）剪枝階段剪枝：選擇導(dǎo)致最低錯誤率的子樹方案一：使用原有的測試數(shù)據(jù)方案二：使用獨立的數(shù)據(jù)集取樣困難降低生成的模型的準(zhǔn)確率理想的剪枝方法：快速得到簡潔而且準(zhǔn)確的決策樹92. SLIQ算法決策樹算法SLIQ算法數(shù)據(jù)結(jié)構(gòu)預(yù)排序與廣度優(yōu)先增長策略種類型字段的最佳子集生成方法MDL剪枝SLIQ性能評估102. SLIQ算法SLI

5、Q的優(yōu)異性能可伸縮性良好縮短學(xué)習(xí)時間處理常駐磁盤的大數(shù)據(jù)集的能力：對訓(xùn)練數(shù)據(jù)的記錄個數(shù)和訓(xùn)練樣本的屬性個數(shù)沒有過多的限制處理大數(shù)據(jù)集，帶來結(jié)果的準(zhǔn)確性新的剪枝方法更簡潔、準(zhǔn)確的結(jié)果112. SLIQ算法SLIQ的關(guān)鍵詞預(yù)排序廣度優(yōu)先增長策略常駐磁盤的數(shù)據(jù)集快速尋找子集方法MDL剪枝122. SLIQ算法數(shù)據(jù)結(jié)構(gòu)屬性表（Attribute List）每個屬性有一個屬性表有必要的話，屬性表可以寫回磁盤類表（Class List）僅有一張類表，類表必須常駐內(nèi)存類表第n項，存放第n條記錄的類標(biāo)簽。屬性值指向類表表項的索引類標(biāo)簽指向該條記錄所屬樹結(jié)點的索引132. SLIQ算法數(shù)據(jù)結(jié)構(gòu)樹結(jié)點內(nèi)部節(jié)點記錄

6、必要的分類信息葉子節(jié)點代表訓(xùn)練集的一塊數(shù)據(jù)，也就是一個類別每個節(jié)點都有一個類直方圖，用來統(tǒng)計分類所需的必要的類別分布的信息。C1C2CnLfRC1C2CnV1fV2Vm數(shù)值型字段的類直方圖種類型字段的類直方圖142. SLIQ算法預(yù)排序與廣度優(yōu)先增長策略預(yù)排序的例子152. SLIQ算法預(yù)排序與廣度優(yōu)先增長策略計算最佳分割的算法EvaluateSplits() for each attribute A do traverse attribute list of A for each value v in the attribute list do find the corresponding

7、entry in the class list, and hence the corresponding class and the leaf node (say l) update the class histogram in the leaf l if A is a numeric attribute then compute splitting index for test (A = v) for leaf l if A is a categorical attribute then for each leaf of the tree do find subset of A with b

8、est split在這里，種類型字段使用類直方圖里面的信息，尋找達(dá)到最佳gini指標(biāo)的屬性子集在這里，數(shù)值型字段使用類直方圖里面的信息計算gini指標(biāo)，尋找最佳分割16進(jìn)行節(jié)點分裂的例子：正在掃描屬性表Salary List已經(jīng)完成對該表第一個節(jié)點的掃描正在掃描該表第二個節(jié)點172. SLIQ算法預(yù)排序與廣度優(yōu)先增長策略計算出最佳分割以后，就可以產(chǎn)生子節(jié)點了子節(jié)點聲稱以后，需要對類表進(jìn)行更新，使它指向原來節(jié)點的子節(jié)點更新類表的算法UpdateLabels() for each attribute A used in a split do traverse attribute list of A

9、 for each value v in the attribute list do find the corresponding entry in the class list (say e) find the new class c to which v belongs by applying the splitting test at node referenced from e update the class label for e to c update node referenced in e to the child corresponding to the class c18

10、2. SLIQ算法預(yù)排序與廣度優(yōu)先增長策略類表升級的例子192. SLIQ算法預(yù)排序與廣度優(yōu)先增長策略一個優(yōu)化策略有些節(jié)點會提前停止分裂，例如純節(jié)點，或者根據(jù)事先給定的策略停止分裂的節(jié)點把已經(jīng)停止分裂的節(jié)點包含的記錄從屬性表中刪除屬性表得到壓縮，從而后面的算法執(zhí)行速度會加快。202. SLIQ算法種類型字段的最佳子集生成方法種類型字段，最佳分裂型如 ，開銷主要是尋找最佳的子集折衷方案屬性可能的值的個數(shù) 小于MAXSETSIZE時，遍歷所有子集，尋找最佳分割屬性可能的值的個數(shù) 大于MAXSETSIZE時，使用貪心算法（Greedy Algorithm），尋找最佳分割的近似解。論文作者的MAXSETSIZE取10，2的10次方次被認(rèn)為可以接受212. SLIQ算法MDL剪枝MDL原理：對數(shù)據(jù)進(jìn)行編碼的最佳模型是使得用該模型描述數(shù)據(jù)和描述這個模型的帶價的和最小的模型算法中MDL剪枝的目的是：對于生成的初始樹，發(fā)現(xiàn)最好的描述訓(xùn)練集S的子樹T222. SLIQ算法MDL剪枝數(shù)據(jù)編碼代價定義為所有分類錯誤的總和模型編碼對樹編碼（Code1, Code2, Code3）分裂方案編碼數(shù)值型種類型232. SLIQ算