分類器的定義：輸入的數據含有千萬個記錄，每個記錄又有很多個屬性，其中有一個特別的屬性叫做類（例如信用程度的高，中，低）。分類器的目的就是分析輸入的數據，并建立一個模型，并用這個模型對未來的數據進行分類，應用于信用確認，醫療診斷等。
運用在決策樹上的分類器��
SLIQ
。一：樹的建立。
- 預分類：為訓練集中的每個屬性建立一個屬性表，每個屬性表包含屬性值和索引，每個索引對應一個記錄，而特殊的屬性��類中還包含枝節點。
- 節點的分割過程：
a,
選取哪個屬性來分割。
b,
對于選取的屬性，確定分割標準。在
SLIQ
里采用的是
gini
分割系數的方法。具體到每個
node
的分割又包括矩形類圖的的更新和類表的更新。
以上介紹的是連續值的屬性的分割方法，對于分類屬性的值（例如地區屬性）：
S
代表
A
所有可能的值的集合（有
2
的
n
次方個），
S’
是
S
的子集。如果
n
小于某個門限時，就對每個
S’
都估算一遍，否則就采用一種叫做
greedy algorithrm
的方法。
二：樹的修剪。
SLIQ
采用了
MDL
（最小敘述長度）的方法來修剪樹。
COST(M,D)=COST(D|M)+COST(M);
COST(D|M)
是指對于
Data
的編碼的“費用”，定義為分類器錯誤個數的總和。
COST(M)
包含兩部分：
a,
樹的編碼的“費用”，有
code1
，
code2
和
code3
三種?！?/font>
b,
分割方法的編碼的“費用”。有連續值屬性的（每一個判斷定為
L(test)=1
）和分類屬性（
L(test)=lnAi,
其中樹中所有采用類屬性分割的方法的總和）的兩種。上述公式又可分成四種情況：
如果該節點是一個葉子，
Cleaf(t)= L(t)+Errorst;
如果該節點有兩個孩子，
Cboth(t)=L(t)+Ltest+C(t1)+C(t2);
如果該節點只有左邊有一個孩子，
Cleft(t)=L(t)+Ltest+C(t1)+C’(t2);
如果該節點只有右邊有一個孩子，
Cright(t)=L(t)+Ltest+C’(t1)+C(t2);
這里
C’
（
ti
）指的是：被修剪了的那個枝里的記錄用母節點里的統計方法來編碼所用的“費
用”。根據上面的敘述，可以采用三種策略來進行修剪。
Full:
采用這種方法，只是考慮第一和第二種情況，也就是如果
Cleaf
計算下來比
Cboth
小的話就將這個節點變為一片葉子。這樣樹的編碼“費用”里就只用了一個比特。
Partial:
這種方法將四種情況都考慮了進去，比較四種計算“費用”的大小，選擇“費用”最小的那種作為修剪的方法。
3, Hybrid
（混合的）
:
這種方法包含兩個過程，第一步先用
Full
的策略來得到一個比較小的
樹，然后再考慮后三種的計算方法來修剪樹。三：綜述：
SLIQ
采用了
Pre-sorting,breadth-first
和
MDL
的方法來建立和修剪決策樹，它能夠對大量的數據進行處理，突破了傳統分類器的只能處理
700KB
數據的瓶頸。
凡是有該標志的文章，都是該blog博主Caoer（草兒）原創，凡是索引、收藏
、轉載請注明來處和原文作者。非常感謝。