分类器的定义：输入的数据含有千万个记录，每个记录又有很多个属性，其中有一个特别的属性叫做类（例如信用程度的高，中，低）。分类器的目的就是分析输入的数据，并建立一个模型，并用这个模型对未来的数据进行分类，应用于信用确认，医疗诊断等。
运用在决策树上的分类器��
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
三种。
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（草儿）原创，凡是索引、收藏
、转载请注明来处和原文作者。非常感谢。