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

胡澤亮

?

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

胡澤亮

中國(guó)電信河北分公司，河北 石家莊 050000

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

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

1 概述

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

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

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

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

2 決策樹算法

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

2.1 信息熵

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

2.2 劃分信息熵

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

2.3 信息熵增益

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

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

2.4 分裂信息

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

2.5 信息熵增益率

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

3 構(gòu)建模型

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

表1

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

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

接下來(lái)我們使用SQL語(yǔ)言實(shí)現(xiàn)C4.5算法的5個(gè)公式。

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;

以上是計(jì)算A列屬性信息熵增益率的程序，替換其中的columnA變量得出所有列屬性的信息熵增益率，計(jì)算結(jié)果表保存在result表，見(jiàn)表2。

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

4 修正模型

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

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

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

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

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

圖1

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

5 結(jié)語(yǔ)

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

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

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

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