决策树算法.docx

决策树算法：顾名思义，以二分类问题为例，即利用自变量构造一颗二 叉树，将目标变量区分出来，所有决策树算法的关键点如下：
1•分裂属性的选择。即选择哪个自变量作为树叉，也就是在n个自变量 中，优先选择哪个自变量进行分叉。而采用何种计算方式选变量该怎样计算信息增益呢？只需将连续 型变 量由小到大递增排序，取相邻两个值的中点作为分裂点，然后按照离散型 变量计算信息增益的方法计算信息增益，取其中最大的信息增益作为最终的分裂 点。如求修 障时长的信息增益，首先将修障时长递增排序，、12、14、 16、18、20、22、23、24、25,取相邻两个值的中点，如10. 2和 12，中点即为
（+12）/2=,同理可得其他中点，、13、15、17、19、21、 22. 5、23. 5、24. 5。对每个中点都离散化成两个子集，如中点11. 1，可以离散 化为两个＜=＞，然后按照离散型变量的信息增益计算方式计 算其信息增益，：
—hz 1/1 Ik 9/4 4^ 5 5\
1就°燔膚时虽(満青度=77" (_T* <0S2g_g * 10g2gj = °'222+J
(修障时长)=1-=
中点13的信息增益计算过程如下：
Info〔满童度 I = ^log-. — # logz — =1>
' 7 10 210 1D " 10
+土 2 /I 1 1 1\ 8 / 4 4 4 4\
【就口 悔底旺艮(满意康 二力* (一亍* 10ga2 _ 2*10§22^ +10 * : - '：■ - -' * ^§2 g J = 1+J
(修障时长)=1-1=0
同理分别求得各个中点的信息增益，选取其中最大的信息增益作为分裂点，如取 。然后与故障原因和故障类型的信息增益相比较，取最大的信息增益 作为第一个树叉的分支，此例中选取了故障原因作为第一个分叉。按照同样的方 式继续构造树的分支。
总之，信息增益的直观解释为选取按某个自变量划分所需要的期望信息， 该期望信息越小，划分的纯度越高。因为对于某个分类问题而言，Info(D)都是 固定的，而信息增益 Gain(A)=Info(D)-InfoA(D) 影响信息增益的关键因素为： -InfoA(D)，即按自变量A进行划分，所需要的期望信息越小，整体的信息增益 越大，越能将分类变量区分出来。
算法的增益率：
由于信息增益选择分裂属性的方式会倾向于选择具有大量值的属性(即 自变量)，如对于客户ID,每个客户ID对应一个满意度，即按此变量划分每个 划分都是纯的(即完全的划分，只有属于一个类别)，客户ID的信息增益为最 大值1。但这种按该自变量的每个值进行分类的方式是没有任何意义的。为了克 服这一弊端，有 人提出了采用增益率(GaInRate)来选择分裂属性。计算方式 如下：
Pl% |DJ
SplitIfifoA(D)=-基 币厂 ^ga(—)+^
Gain (A)
Gain Rate. : Dj = /
A SplitInfoA
其中Gain(A)的计算方式与ID3算法中的信息增益计算方式