一種基于決策樹改進算法的客戶關系管理

嚴 熙

摘 要:針對決策樹的經典算法(ID3)計算比較復雜的問題,提出利用條件概率等知識來改進決策樹的構造。分別利用這兩種方法建立客戶關系管理模型,并根據結果發現,改進后的方法在計算效率方面有所提高。

關鍵詞:CRM;ID3;條件概率;數據描述

中圖分類號:TP311.5文獻標識碼:A

文章編號: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 引 言

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

數據挖掘是一門廣義的交叉學科[5],融合了數據庫、數理統計、機器學習、人工智能、高性能計算、可視化等多個領域的理論和技術,是一個利用各種分析工具在海量數據中發現模型和數據之間關系的過程。使用這種模型和關系可以進行預測,它幫助決策者尋找數據之間潛在的關聯,發現被忽略的因素,因而被認為是解決當前數據爆炸時代所面臨信息貧乏問題的一種有效方法。

1 數據的描述與分析

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

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

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

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

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

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

2 建立客戶關系管理模型

管戶關系是一個分類問題,響應變量是二值變量,目標是將客戶分成不忠誠和忠誠兩類。分別應用ID3方法和改進的方法建立客戶分類模型。

2.1 ID 3算法

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

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

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

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

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

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

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

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

ID3算法就是以I(A)作為測試屬性的選取標準,分割訓練實例集最終生成的決策樹。樣本各節點處的最大信息增益熵見表1,生成的決策樹見圖1。

表1 ID3算法結點處的最大信息增益熵

結點名稱 最大信息增益熵結點名稱 最大信息增益熵

結點1-10.731 0結點1-50.111 5

結點1-20.263 1結點1-60.001 7

結點1-30.800 1結點1-70.271 9

結點1-40.659 7

2.2 改進的算法

ID3算法是把信息熵作為選擇測試屬性的標準,即樹結點的選擇策略,但在計算基于屬性的信息熵時,公式比較復雜,計算量較大,相應的復雜度也高。在對于實例集中的每一個屬性,所提供的信息量是具有一定規律的,特別是當某個屬性發生時,其某例別結果發生的條件概率提供給屬性對某例的信息量,基于這個原因,可以考慮采用屬性對某例的條件概率提供的分類信息量構造決策樹。

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

圖1 ID3生成的決策樹

根據概率統計知識,設事件為A,B,稱P(B|A)為事件A發生時事件B會發生的概率,并稱這個條件概率P(B|A)為訓練實例集A發生后,事件B對訓練集中某例別的影響度。

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

對于實例集中的各個屬性,首先計算所有屬性值的影響度,然后進行比較可知影響度越大的屬性值對應的屬性所提供分類的信息量越大。依次比較,就可以確定屬性對分類的影響程度的大小,因此可以根據此大小來構造決策樹的生成算法。

具體算法如下:

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)計算出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 遞歸執行算法Advanced Tree

End

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

表2 改進算法結點處劃分的最大條件概率值

結點名稱最大條件概率值

結點2-10.457 1

結點2-20.046 0

結點2-30.142 9

結點2-40.714 3

生成的樹如圖2所示。

圖2 改進算法生成的決策樹

3 比較模型與分析

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

4 結 語

這里分別使用ID3算法和改進算法對客戶關系管理進行研究。實驗結果表明,改進的算法可以提高決策效率。利用這種方法對客戶關系進行管理,可全面掌握客戶偏好和客戶信息,了解客戶的需求和信用風險,可以更有針對性地開發和選擇金融產品,制定正確的營銷服務策略,將信息流的控制能力和快速反應能力轉化成競爭力,提高客戶滿意度,從而形成企業的核心競爭力。

參考文獻

[1]Alex Berson,Stephen Smith,Kurt Thearling.構建面向CRM的數據挖掘應用[M].賀奇,鄭巖,魏藜,等譯.北京:人民郵電出版社,2001.

[2]戴艷紅,賀紅燕.數據挖掘技術在客戶關系管理中的應用研究[J].商場現代化,2006(34):350-351.

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

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

[5]黃曉芳.數據挖掘中決策樹算法及其應用[J].兵工自動化,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].吉林師范大學學報:自然科學版,2008(3):136-137.

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

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

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