胡澤亮

?

使用Oracle工具構(gòu)建用戶離網(wǎng)的決策樹模型

胡澤亮

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

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

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

1 概述

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

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

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

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

2 決策樹算法

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

2.1 信息熵

式中：S代表樣本集合；m代表結(jié)果分類數(shù)量；Pi代表數(shù)據(jù)集中每個結(jié)果類別所占樣本總數(shù)的比例。變量的不確定性越大，熵就越大；一個系統(tǒng)越是有序，信息熵就越低。對于二分類問題，熵在[0，1]之間，如果所有樣本都屬于同一類，熵為0，這個時候給定一個樣本，類別就是確定的。如果不同的樣本各占一半，熵為1=1/2+1/2，這個時候如果給定一個樣本來分類，就完全無法確定了。

2.2 劃分信息熵

A分類為離散類型，有k個不同取值，k個不同取值將S劃分為k個子集{S1，S2，…，Sk}，|Si|表示第i個子集包含的樣本個數(shù)，|S|表示總集合的樣本個數(shù)。

2.3 信息熵增益

Gain(S,A)=Entropy(S)-EntropyA(S)

信息增益表示按屬性A劃分集合S的信息增益Gain(S,A)等于樣本集S的熵減去按屬性A劃分S后樣本子集的熵。

2.4 分裂信息

C4.5算法中導(dǎo)入分裂信息用來克服ID3算法傾向于多值屬性的問題，避免存在唯一屬性分類，雖然增益最大但是對分類毫無意義。

2.5 信息熵增益率

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

3 構(gòu)建模型

以下我們根據(jù)一個簡單的用戶離網(wǎng)樣本數(shù)據(jù)存儲表temp作為樣例構(gòu)建決策樹。

表1

用戶在網(wǎng)是否一年（A）欠費（B）使用量（C）套餐價格（D）月底是否離網(wǎng)（E） 1否是長高是 2否是短高否 3是否短低否 4否是長低是 5否是短高是 6是否長低否 7否是長高否 8否是短低否 9否是長低是 10是是短高否 11是否短高否 12否是短高否 13是否長低否 14是否短低否 15否是長高是 16否是長高否

數(shù)據(jù)樣本如表1所示，共16個用戶，每個用戶有4個屬性，分別是在網(wǎng)時長、是否欠費，使用量，套餐價格，最后一列作為結(jié)果表示是用戶月底是否離網(wǎng)。同時我們建立一個計算結(jié)果表result存放計算結(jié)果。

接下來我們使用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變量得出所有列屬性的信息熵增益率，計算結(jié)果表保存在result表，見表2。

可以看到增益率最大的屬性是A列在網(wǎng)時長，將在網(wǎng)時長作為決策樹的第一層決策節(jié)點，按照降序columnB、columnC、columnD分別是第二層、第三層、第四層決策節(jié)點。通過遞歸關(guān)系初步構(gòu)建決策樹。

4 修正模型

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

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

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

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

根據(jù)以上原則處理后最終得到的根據(jù)離網(wǎng)樣本構(gòu)建的決策樹變得更加簡練。

圖1

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

5 結(jié)語

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

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

[1]楊學(xué)兵，張俊. 決策樹算法及其核心技術(shù)[J]. 計算機技術(shù)與發(fā)展，2007，17（1）：43-45.

[2]唐華松，姚耀文. 數(shù)據(jù)挖掘中決策樹算法的探討[J].計算機應(yīng)用研究，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