嚴(yán) 熙

摘 要:針對(duì)決策樹的經(jīng)典算法(ID3)計(jì)算比較復(fù)雜的問題,提出利用條件概率等知識(shí)來改進(jìn)決策樹的構(gòu)造。分別利用這兩種方法建立客戶關(guān)系管理模型,并根據(jù)結(jié)果發(fā)現(xiàn),改進(jìn)后的方法在計(jì)算效率方面有所提高。

關(guān)鍵詞:CRM;ID3;條件概率;數(shù)據(jù)描述

中圖分類號(hào):TP311.5文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1004-373X(2009)20-134-03

Advanced Algorithm Based on Calculation of ID3 in CRM

YAN Xi

(Jiangsu University of Science and Technology,Zhenjiang,212003,China)

Abstract:For the reason of that the calculation of ID3 is complex,an advanced way referring condition probability and other knowledge to improve the structure of the decision tree is proposed.These two methods are used to build two CRM models,the results show that advanced way really improved the efficiency of calculation.

Keywords:CRM;ID3;condition probability;data description

0 引 言

客戶關(guān)系管理(Customer Relationship Management,CRM)起源于西方的市場(chǎng)營銷理論。近年來,信息技術(shù)的長足發(fā)展為市場(chǎng)營銷管理理念的普及和應(yīng)用開辟了廣闊的空間。以客戶為中心,視客戶為資源,通過客戶關(guān)懷實(shí)現(xiàn)客戶滿意度?？蛻魧?duì)企業(yè)的好感和忠誠不僅來自于企業(yè)提供的商品,更來自于服務(wù)和經(jīng)驗(yàn)等非實(shí)體因素。企業(yè)要了解客戶的喜好,管理每一個(gè)客戶的關(guān)系,從每個(gè)客戶身上獲取最大利潤,降低市場(chǎng)營銷費(fèi)用,并減少由于客戶離去和無效的營銷策略產(chǎn)生的浪費(fèi)。用客戶關(guān)系管理的方法,即CRM方法可以使這些希望成為現(xiàn)實(shí)[1-4]。而數(shù)據(jù)挖掘方法可以從客戶數(shù)據(jù)庫中挖掘出有價(jià)值的信息,并且這些信息可以處理已有的和潛在的客戶關(guān)系,企業(yè)可以不斷改善適合每個(gè)客戶的個(gè)性化服務(wù)。

數(shù)據(jù)挖掘是一門廣義的交叉學(xué)科[5],融合了數(shù)據(jù)庫、數(shù)理統(tǒng)計(jì)、機(jī)器學(xué)習(xí)、人工智能、高性能計(jì)算、可視化等多個(gè)領(lǐng)域的理論和技術(shù),是一個(gè)利用各種分析工具在海量數(shù)據(jù)中發(fā)現(xiàn)模型和數(shù)據(jù)之間關(guān)系的過程。使用這種模型和關(guān)系可以進(jìn)行預(yù)測(cè),它幫助決策者尋找數(shù)據(jù)之間潛在的關(guān)聯(lián),發(fā)現(xiàn)被忽略的因素,因而被認(rèn)為是解決當(dāng)前數(shù)據(jù)爆炸時(shí)代所面臨信息貧乏問題的一種有效方法。

1 數(shù)據(jù)的描述與分析

客戶關(guān)系管理主要的目標(biāo)是將客戶分成兩類:只簽訂一張訂單的客戶和簽訂多張訂單的客戶。二值變量(用Y表示)可以用變量Total Number of Orders推導(dǎo)出。設(shè)定當(dāng)Total Number of Orders等于1時(shí),Y=0,表示客戶不忠誠;當(dāng)Total Number of Orders大于1時(shí),Y=1,表示客戶忠誠。根據(jù)經(jīng)驗(yàn),探索性變量的選取如下:

Instalment:表示第一次購買是否是分期付款的二值變量,使用分期付款為1,未使用分期付款為0。它表示客戶和企業(yè)保持聯(lián)系的時(shí)間長短。如果一個(gè)人使用分期付款,與企業(yè)的合同就會(huì)延長一些時(shí)間;

First Amount Spent:表示客戶第一次購物所花費(fèi)的金額是否是可觀的二值變量,如果第一次購物的金額大于或等于300 000美元,則令其為1,否則為0;

Number of Products at first Order(Numb):表示客戶第一次購物的數(shù)量是否是可觀的二值變量,如果第一次購物的數(shù)量大于或等于6件,則令其為1,否則為0;

Age:如果客戶的年齡小于或等于50歲,則Age取值為1,否則為0;

Area of Residence:客戶所在地域位于北部到中部,則Area of Residence取值為0,客戶所在地域位于中部到南部,則Area of Residence取值為1。

2 建立客戶關(guān)系管理模型

管戶關(guān)系是一個(gè)分類問題,響應(yīng)變量是二值變量,目標(biāo)是將客戶分成不忠誠和忠誠兩類。分別應(yīng)用ID3方法和改進(jìn)的方法建立客戶分類模型。

2.1 ID 3算法

設(shè)訓(xùn)練實(shí)例集為X,將其分為n類,記為C={X1,X2,…,Xn},設(shè)第i類訓(xùn)練實(shí)例的個(gè)數(shù)是|Xi|,實(shí)例集X中的訓(xùn)練實(shí)例個(gè)數(shù)為|X|。若記一個(gè)實(shí)例屬于第i類的概率為P(Xi),則決策樹劃分C的不確定程度為H(X,C),可簡(jiǎn)記為H(X),且:

H(X)=-∑P(Xi)log2[P(Xi)](1)

選擇測(cè)試屬性A進(jìn)行測(cè)試。設(shè)A具有性質(zhì)a1,a2,…,al,在A=aj的情況下,屬于第i類的實(shí)例個(gè)數(shù)為|Xij|,A=aj的實(shí)例個(gè)數(shù)為|Xj|。記P(Xi|A=aj)為A取aj時(shí)屬于第i類的概率,則有P(Xi|A=aj)=|Xij|/|Xj|,設(shè)Yi為A=aj時(shí)的實(shí)例集,此時(shí)決策樹對(duì)劃分類的不確定程度就是實(shí)例集對(duì)屬性A的條件熵為:

H(X|A)=∑jP(A=aj)H(Yj)=

-∑i∑jP(A=aj)P(Xi|A=aj)?

log2[P(Xi|A=aj)](2)

屬性A對(duì)于分類提供的信息量,即屬性A的信息增益I(A)為:

I(A)=H(X)-H(X|A)(3)

ID3算法就是以I(A)作為測(cè)試屬性的選取標(biāo)準(zhǔn),分割訓(xùn)練實(shí)例集最終生成的決策樹。樣本各節(jié)點(diǎn)處的最大信息增益熵見表1,生成的決策樹見圖1。

表1 ID3算法結(jié)點(diǎn)處的最大信息增益熵

結(jié)點(diǎn)名稱 最大信息增益熵結(jié)點(diǎn)名稱 最大信息增益熵

結(jié)點(diǎn)1-10.731 0結(jié)點(diǎn)1-50.111 5

結(jié)點(diǎn)1-20.263 1結(jié)點(diǎn)1-60.001 7

結(jié)點(diǎn)1-30.800 1結(jié)點(diǎn)1-70.271 9

結(jié)點(diǎn)1-40.659 7

2.2 改進(jìn)的算法

ID3算法是把信息熵作為選擇測(cè)試屬性的標(biāo)準(zhǔn),即樹結(jié)點(diǎn)的選擇策略,但在計(jì)算基于屬性的信息熵時(shí),公式比較復(fù)雜,計(jì)算量較大,相應(yīng)的復(fù)雜度也高。在對(duì)于實(shí)例集中的每一個(gè)屬性,所提供的信息量是具有一定規(guī)律的,特別是當(dāng)某個(gè)屬性發(fā)生時(shí),其某例別結(jié)果發(fā)生的條件概率提供給屬性對(duì)某例的信息量,基于這個(gè)原因,可以考慮采用屬性對(duì)某例的條件概率提供的分類信息量構(gòu)造決策樹。

ID3算法是通過最大信息增益值選擇測(cè)試屬性,改進(jìn)的算法是通過最大條件概率值選擇測(cè)試屬性。

圖1 ID3生成的決策樹

根據(jù)概率統(tǒng)計(jì)知識(shí),設(shè)事件為A,B,稱P(B|A)為事件A發(fā)生時(shí)事件B會(huì)發(fā)生的概率,并稱這個(gè)條件概率P(B|A)為訓(xùn)練實(shí)例集A發(fā)生后,事件B對(duì)訓(xùn)練集中某例別的影響度。

P(B|A)=P(AB)/P(A)(4)

對(duì)于實(shí)例集中的各個(gè)屬性,首先計(jì)算所有屬性值的影響度,然后進(jìn)行比較可知影響度越大的屬性值對(duì)應(yīng)的屬性所提供分類的信息量越大。依次比較,就可以確定屬性對(duì)分類的影響程度的大小,因此可以根據(jù)此大小來構(gòu)造決策樹的生成算法。

具體算法如下:

Advanced Tree

Input:Attributes and Data

Output:A Tree

Start

W=An example

if W belong to a class X then

return N as a leave X

if attribute =NULL then

return N as a leave

for W do

for each attribute of class X do

利用公式(3)計(jì)算出attribute中具有最大條件概率值的屬性max attribute

V= max attribute//具有最大條件概率值的樣本集合

end for

end for

for each ai of max attribute do

grow a branch

end for

if V=Null then

add a leave

else 遞歸執(zhí)行算法Advanced Tree

End

該實(shí)驗(yàn)中所使用的樣本數(shù)據(jù)集按類別可分為不忠誠和忠誠兩類,分別記為C1和C2。P(1|Instalment)表示第一次購買使用分期付款的事件發(fā)生的概率;P(C1,1|Instalment)表示為第一次購買使用分期付款,且類別為C1的事件發(fā)生的概率;PC11|Instalment為第一次購買使用分期付款,且類別為C1的條件概率,其余類推。根據(jù)式(4)可以得到每個(gè)屬性對(duì)分類為C1的影響度,根據(jù)計(jì)算可得樣本各結(jié)點(diǎn)處最大條件的概率見表2。

表2 改進(jìn)算法結(jié)點(diǎn)處劃分的最大條件概率值

結(jié)點(diǎn)名稱最大條件概率值

結(jié)點(diǎn)2-10.457 1

結(jié)點(diǎn)2-20.046 0

結(jié)點(diǎn)2-30.142 9

結(jié)點(diǎn)2-40.714 3

生成的樹如圖2所示。

圖2 改進(jìn)算法生成的決策樹

3 比較模型與分析

使用ID3算法生成的決策樹有7個(gè)結(jié)點(diǎn)和8片葉子,使用改進(jìn)后的算法生成的決策樹有4個(gè)結(jié)點(diǎn)和5片葉子,減少了Area of Residence這一屬性,簡(jiǎn)化了決策過程,直接把屬性值和類別結(jié)果相聯(lián)系,降低了計(jì)算的復(fù)雜性,提高了計(jì)算效率。

4 結(jié) 語

這里分別使用ID3算法和改進(jìn)算法對(duì)客戶關(guān)系管理進(jìn)行研究。實(shí)驗(yàn)結(jié)果表明,改進(jìn)的算法可以提高決策效率。利用這種方法對(duì)客戶關(guān)系進(jìn)行管理,可全面掌握客戶偏好和客戶信息,了解客戶的需求和信用風(fēng)險(xiǎn),可以更有針對(duì)性地開發(fā)和選擇金融產(chǎn)品,制定正確的營銷服務(wù)策略,將信息流的控制能力和快速反應(yīng)能力轉(zhuǎn)化成競(jìng)爭(zhēng)力,提高客戶滿意度,從而形成企業(yè)的核心競(jìng)爭(zhēng)力。

參考文獻(xiàn)

[1]Alex Berson,Stephen Smith,Kurt Thearling.構(gòu)建面向CRM的數(shù)據(jù)挖掘應(yīng)用[M].賀奇,鄭巖,魏藜,等譯.北京:人民郵電出版社,2001.

[2]戴艷紅,賀紅燕.數(shù)據(jù)挖掘技術(shù)在客戶關(guān)系管理中的應(yīng)用研究[J].商場(chǎng)現(xiàn)代化,2006(34):350-351.

[3]何祖銀,李靜,馬宏偉.面向CRM的數(shù)據(jù)挖掘應(yīng)用[J].物流科技,2006(9):73-75.

[4]張新香.決策樹挖掘在CRM中的應(yīng)用[J].電腦開發(fā)與應(yīng)用,2007(4):52-54.

[5]黃曉芳.數(shù)據(jù)挖掘中決策樹算法及其應(yīng)用[J].兵工自動(dòng)化,2005(2):35-36.

[6]Wang X Z,Chen B,Qian G L,et al.On the Optimization of Fuzzy Decision Trees[J].Fuzzy Sets and Systems,2000,112:117-125.

[7]張桂杰,王帥.決策樹分類ID3算法研究[J].吉林師范大學(xué)學(xué)報(bào):自然科學(xué)版,2008(3):136-137.

[8]郭玉濱.決策樹算法研究綜述[J].電腦知識(shí)與技術(shù),2006(2):155-156.

[9]龐哈利,高政威,左軍偉,等.基于變精度粗糙集的分類決策樹構(gòu)造方法[J].系統(tǒng)工程與電子技術(shù),2008(11):2 160-2 163.

[10]白雪,段富.決策樹分類算法的研究及其在教學(xué)評(píng)估中的應(yīng)用[J].電腦開發(fā)與應(yīng)用,2007(2):24-26.