使用Oracle工具構建用戶離網的決策樹模型

胡澤亮

?

使用Oracle工具構建用戶離網的決策樹模型

胡澤亮

中國電信河北分公司，河北 石家莊 050000

通過一步步說明信息熵增益率的計算過程及決策樹的構建，介紹了如何使用Oracle工具構建基于C4.5算法的離網模型。

決策樹建模；C4.5算法；Oracle

1 概述

決策樹算法是一種逼近離散函數值的方法。它是一種分類方法，首先對數據進行處理，利用歸納算法生成可讀的規(guī)則和決策樹，然后使用決策對新數據進行分析。本質上決策樹是通過一系列規(guī)則對數據進行分類的過程。決策樹模型呈樹形結構，表示基于特征對實例進行分類的過程。它可以認為是定義在特征空間與類空間上的條件概率分布。

決策樹算法中如何構造精度高、規(guī)模小的決策樹是決策樹算法的核心內容。決策樹構造可以分兩步進行。第一步，決策樹的生成：由訓練樣本集生成決策樹的過程。一般情況下，訓練樣本數據集是根據實際需要有歷史的、有一定綜合程度的，用于數據分析處理的數據集。它由決策節(jié)點、分支和葉節(jié)點三個部分組成。決策節(jié)點代表一個樣本測試，通常代表待分類樣本的某個屬性，在該屬性上的不同測試結果代表一個分支；分支表示某個決策節(jié)點的不同取值。每個葉節(jié)點代表一種可能的分類結果。第二步，決策樹的剪枝：決策樹的剪枝是對上一階段生成的決策樹進行檢驗、校正和修下的過程，主要是用新的樣本數據集（稱為測試數據集）中的數據校驗決策樹生成過程中產生的初步規(guī)則，將那些影響預衡準確性的分枝剪除。

決策樹方法最早產生于20世紀60年代。70年代末出現(xiàn)ID3算法。此算法的目的在于減少樹的深度，但是忽略了葉子數目的研究。C4.5算法在ID3算法的基礎上進行了改進，對于預測變量的缺值處理、剪枝技術、派生規(guī)則等方面做了較大改進，既適合于分類問題，又適合于回歸問題。

本文就是基于C4.5算法構建一套用戶離網模型，并使用功能強大的Oracle平臺實現(xiàn)，有利于在日常生產中進行數據的采集和分析存儲。

2 決策樹算法

本文1948年，香農提出了“信息熵”概念。一條信息的信息量大小和它的不確定性有直接的關系。C4.5使用信息增益率而不是信息增益作為決策樹的屬性選擇標準。以下介紹如何計算信息增益率及相應的公式。

2.1 信息熵

式中：S代表樣本集合；m代表結果分類數量；Pi代表數據集中每個結果類別所占樣本總數的比例。變量的不確定性越大，熵就越大；一個系統(tǒng)越是有序，信息熵就越低。對于二分類問題，熵在[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 信息熵增益率

信息增益率將分裂信息作為分母，屬性取值數目越大，分裂信息值越大，從而部分抵消了屬性取值數目所帶來的影響。我們的目的就是選取信息熵增益率最高的集合分類作為決策樹的分裂節(jié)點。

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語言實現(xiàn)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列在網時長，將在網時長作為決策樹的第一層決策節(jié)點，按照降序columnB、columnC、columnD分別是第二層、第三層、第四層決策節(jié)點。通過遞歸關系初步構建決策樹。

4 修正模型

初步構建的決策樹共有4個分別有2個分裂值的決策點，畫出來的邏輯圖有4層16個葉節(jié)點。我們知道邏輯復雜度與計算效率存在指數關系，因此有必要進行簡化。

（1）簡化原則1：去掉無結果的葉節(jié)點。

（2）簡化原則2：分裂值下的所有葉節(jié)點相同，省略該分裂值下的所有分支和決策節(jié)點。

（3）簡化原則3：只有一個分裂值的決策節(jié)點可以省略。

根據以上原則處理后最終得到的根據離網樣本構建的決策樹變得更加簡練。

圖1

我們發(fā)現(xiàn)兩個葉節(jié)點的結果不是純凈的，即集合內的元素不屬于同一類別，在實際生產中代表提取樣本的屬性不足。這種情況下有兩個解決方案：一是增加樣本的屬性直到樣本結果純凈；二是根據現(xiàn)有的葉節(jié)點中元素占比計算新數據在該葉節(jié)點的元素概率。

5 結語

通過以上這個簡單樣例我們構建出基于樣本的離網決策樹，但是在實際生產中影響離網的因素還有很多，需要不斷收集大量樣本訓練才能構建符合實際情況的決策樹模型。

由于C4.5算法中連續(xù)變量需要劃分成離散變量容易出現(xiàn)過擬合，在實際應用中通常是結合CART、隨機森林、GBM等其他算法分別建模，將多個模型均預測為離網用戶的目標用戶選出來作為最終的目標用戶。

[1]楊學兵，張俊. 決策樹算法及其核心技術[J]. 計算機技術與發(fā)展，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