使用Oracle工具构建用户离网的决策树模型
2018-08-04胡泽亮
胡泽亮
使用Oracle工具构建用户离网的决策树模型
胡泽亮
中国电信河北分公司，河北 石家庄 050000
通过一步步说明信息熵增益率的计算过程及决策树的构建，介绍了如何使用Oracle工具构建基于C4.5算法的离网模型。
决策树建模；C4.5算法；Oracle
1 概述
决策树算法是一种逼近离散函数值的方法。它是一种分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。决策树模型呈树形结构，表示基于特征对实例进行分类的过程。它可以认为是定义在特征空间与类空间上的条件概率分布。
决策树算法中如何构造精度高、规模小的决策树是决策树算法的核心内容。决策树构造可以分两步进行。第一步，决策树的生成：由训练样本集生成决策树的过程。一般情况下，训练样本数据集是根据实际需要有历史的、有一定综合程度的，用于数据分析处理的数据集。它由决策节点、分支和叶节点三个部分组成。决策节点代表一个样本测试，通常代表待分类样本的某个属性，在该属性上的不同测试结果代表一个分支；分支表示某个决策节点的不同取值。每个叶节点代表一种可能的分类结果。第二步，决策树的剪枝：决策树的剪枝是对上一阶段生成的决策树进行检验、校正和修下的过程，主要是用新的样本数据集（称为测试数据集）中的数据校验决策树生成过程中产生的初步规则，将那些影响预衡准确性的分枝剪除。
决策树方法最早产生于20世纪60年代。70年代末出现ID3算法。此算法的目的在于减少树的深度，但是忽略了叶子数目的研究。C4.5算法在ID3算法的基础上进行了改进，对于预测变量的缺值处理、剪枝技术、派生规则等方面做了较大改进，既适合于分类问题，又适合于回归问题。
本文就是基于C4.5算法构建一套用户离网模型，并使用功能强大的Oracle平台实现，有利于在日常生产中进行数据的采集和分析存储。
2 决策树算法
本文1948年，香农提出了“信息熵”概念。一条信息的信息量大小和它的不确定性有直接的关系。C4.5使用信息增益率而不是信息增益作为决策树的属性选择标准。以下介绍如何计算信息增益率及相应的公式。
2.1 信息熵
式中：S代表样本集合；m代表结果分类数量；Pi代表数据集中每个结果类别所占样本总数的比例。变量的不确定性越大，熵就越大；一个系统越是有序，信息熵就越低。对于二分类问题，熵在[0，1]之间，如果所有样本都属于同一类，熵为0，这个时候给定一个样本，类别就是确定的。如果不同的样本各占一半，熵为1=1/2+1/2，这个时候如果给定一个样本来分类，就完全无法确定了。
2.2 划分信息熵
A分类为离散类型，有k个不同取值，k个不同取值将S划分为k个子集{S1，S2，…，Sk}，|Si|表示第i个子集包含的样本个数，|S|表示总集合的样本个数。
2.3 信息熵增益
Gain(S,A)=Entropy(S)-EntropyA(S)
信息增益表示按属性A划分集合S的信息增益Gain(S,A)等于样本集S的熵减去按属性A划分S后样本子集的熵。
2.4 分裂信息
C4.5算法中导入分裂信息用来克服ID3算法倾向于多值属性的问题，避免存在唯一属性分类，虽然增益最大但是对分类毫无意义。
2.5 信息熵增益率
信息增益率将分裂信息作为分母，属性取值数目越大，分裂信息值越大，从而部分抵消了属性取值数目所带来的影响。我们的目的就是选取信息熵增益率最高的集合分类作为决策树的分裂节点。
3 构建模型
以下我们根据一个简单的用户离网样本数据存储表temp作为样例构建决策树。
表1
用户在网是否一年（A）欠费（B）使用量（C）套餐价格（D）月底是否离网（E） 1否是长高是 2否是短高否 3是否短低否 4否是长低是 5否是短高是 6是否长低否 7否是长高否 8否是短低否 9否是长低是 10是是短高否 11是否短高否 12否是短高否 13是否长低否 14是否短低否 15否是长高是 16否是长高否
数据样本如表1所示，共16个用户，每个用户有4个属性，分别是在网时长、是否欠费，使用量，套餐价格，最后一列作为结果表示是用户月底是否离网。同时我们建立一个计算结果表result存放计算结果。
接下来我们使用SQL语言实现C4.5算法的5个公式。
3.1 信息熵
declare
v_num number;
v_result number;
v_entropy number :=0;
v_s number;
v_si number;
cursor c1 is
select distinct columnE from temp t ;
begin
for rec in c1 loop
select count(1) into v_s from temp ;
select count(1) into v_si from temp where columnE=rec.columnE ;
select -v_si/v_s*log(2,v_si/v_s)
into v_result
from dual ;
v_entropy:=v_entropy+v_result ;
END LOOP;
update result set entropy=v_entropy ;
COMMIT;
end;
3.2 划分信息熵
declare
v_columnA varchar2(30);
v_result number :=0;
v_entropyi number :=0;
v_entropya number :=0;
v_s number;
v_p number;
v_pi number;
cursor c1 is
select distinct columnA from temp t ;
cursor c2 is
select distinct columnE from temp t where columnA=v_columnA ;
begin
for rec1 in c1 loop
select count(1) into v_s from temp;
v_columnA:=rec1.columnA;
表2
v_entropyi:=0 ;
for rec2 in c2 loop
select count(1) into v_p from temp where columnA=rec1.columnA ;
select count(1) into v_pi from temp where columnA=rec1.columnA and columnE=rec2.columnE ;
select -v_pi/v_p*log(2,v_pi/v_p)
into v_result
from dual ;
v_entropyi:=v_entropyi+v_result ;
END LOOP;
v_entropya:=v_entropya+(v_p/v_s)*v_entropyi ;
end loop;
update result set entropya=v_entropya where temp_column='columnA' ;
COMMIT;
end;
3.3 信息熵增益
update result set gain=entropy-entropya ;
3.4 分裂信息
declare
v_result number;
v_splite number :=0;
v_s number;
v_si number;
cursor c1 is
select distinct columnA from temp t ;
begin
for rec in c1 loop
select count(1) into v_s from temp ;
select count(1) into v_si from temp where columnA=rec.columnA;
select -v_si/v_s*log(2,v_si/v_s)
into v_result
from dual ;
v_splite:=v_splite+v_result ;
END LOOP;
update result set split=v_splite where temp_column='columnA';
COMMIT;
end;
3.5 信息熵增益率
update result set gainratio=gain/split;
以上是计算A列属性信息熵增益率的程序，替换其中的columnA变量得出所有列属性的信息熵增益率，计算结果表保存在result表，见表2。
可以看到增益率最大的属性是A列在网时长，将在网时长作为决策树的第一层决策节点，按照降序columnB、columnC、columnD分别是第二层、第三层、第四层决策节点。通过递归关系初步构建决策树。
4 修正模型
初步构建的决策树共有4个分别有2个分裂值的决策点，画出来的逻辑图有4层16个叶节点。我们知道逻辑复杂度与计算效率存在指数关系，因此有必要进行简化。
（1）简化原则1：去掉无结果的叶节点。
（2）简化原则2：分裂值下的所有叶节点相同，省略该分裂值下的所有分支和决策节点。
（3）简化原则3：只有一个分裂值的决策节点可以省略。
根据以上原则处理后最终得到的根据离网样本构建的决策树变得更加简练。
图1
我们发现两个叶节点的结果不是纯净的，即集合内的元素不属于同一类别，在实际生产中代表提取样本的属性不足。这种情况下有两个解决方案：一是增加样本的属性直到样本结果纯净；二是根据现有的叶节点中元素占比计算新数据在该叶节点的元素概率。
5 结语
通过以上这个简单样例我们构建出基于样本的离网决策树，但是在实际生产中影响离网的因素还有很多，需要不断收集大量样本训练才能构建符合实际情况的决策树模型。
由于C4.5算法中连续变量需要划分成离散变量容易出现过拟合，在实际应用中通常是结合CART、随机森林、GBM等其他算法分别建模，将多个模型均预测为离网用户的目标用户选出来作为最终的目标用户。
[1]杨学兵，张俊. 决策树算法及其核心技术[J]. 计算机技术与发展，2007，17（1）：43-45.
[2]唐华松，姚耀文. 数据挖掘中决策树算法的探讨[J].计算机应用研究，2001，18（8）：18-19.
Building Oracle’s Decision Tree Model Off-Grid Using Oracle Tools
Hu Zeliang
China Telecom Hebei Branch, Hebei Shijiazhuang 050000
The paper introduces how to use the Oracle tool to construct the off-grid model based on C4.5 algorithm by step by step to explain the calculation process of information entropy gain rate and the construction of decision tree.
decision tree modeling; C4.5 algorithm; Oracle
TP18；F626
A
