吳學(xué)輝 張月琴

(1.運(yùn)城學(xué)院計算機(jī)科學(xué)與技術(shù)系，山西運(yùn)城 044000;2.太原理工大學(xué)計算機(jī)與軟件學(xué)院，太原 030012)

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，電子商務(wù)逐漸改變著傳統(tǒng)經(jīng)營模式，特別是企業(yè)與客戶之間的關(guān)系。企業(yè)最關(guān)心的是:誰是最有價值的客戶，如何實現(xiàn)這些客戶價值最大化等，這些都需要進(jìn)行客戶價值分析。通過分析可以為客戶提供個性化的服務(wù)，使企業(yè)以最小化的投入獲得最大的回報。當(dāng)前許多企業(yè)的網(wǎng)站服務(wù)器端記錄著大量的客戶特征信息和行為信息，但是對這些信息缺乏深層次的分析。決策樹是數(shù)據(jù)挖掘中的一種重要的數(shù)據(jù)分析方法，它主要用來進(jìn)行數(shù)據(jù)的分類和預(yù)測，其主要優(yōu)點是分類速度快，效率高［1-2］。缺點是當(dāng)屬性比較多時，分類能力較差，難以發(fā)現(xiàn)有用的規(guī)則。粗糙集也是一種處理不完備信息的有效工具，因為它不需要先驗知識，所以適合處理不確定性問題。粗糙集已經(jīng)廣泛應(yīng)用在數(shù)據(jù)預(yù)處理、消除冗余信息等方面［3-4］。

本文以數(shù)據(jù)挖掘中的決策樹和粗糙集理論為基礎(chǔ)，將二者有機(jī)結(jié)合，提出了一種基于粗糙集屬性依賴度的決策樹算法，并將此算法應(yīng)用于電子商務(wù)客戶價值分析，提取相關(guān)規(guī)則，為企業(yè)決策提供實質(zhì)性的建議和指導(dǎo)。

1 基本概念

1.1 決策樹算法

決策樹是數(shù)據(jù)挖掘中的一種分類方法，決策樹算法的主要思想是:以信息論為基礎(chǔ)，找出具有最大信息增益的屬性字段，以該屬性字段的不同取值構(gòu)造決策樹分支，然后在每個分支中遞歸構(gòu)建決策樹。在最終構(gòu)建的決策樹中，每一條從根節(jié)點到葉節(jié)點的路徑對應(yīng)著一條規(guī)則。因此，它在數(shù)據(jù)挖掘中應(yīng)用非常廣泛。

決策樹算法中，最經(jīng)典的是ID3算法，該算法以信息論中的信息熵和信息增益度為標(biāo)準(zhǔn)，實現(xiàn)對數(shù)據(jù)的歸納分類。由于ID3算法只能處理離散型屬性，所以它的應(yīng)用受到一些限制，在它之后的C4.5、CART、SLIQ、SPRINT都是對ID3算法進(jìn)行了相關(guān)改進(jìn)［5］。

1.2 粗糙集理論

1982年，波蘭教授 Pawlak Z提出了粗糙集(Rough Set)的概念。粗糙集的基本思想是利用已存在的知識庫，將不精確或不確定的知識用已知的知識庫中的知識來近似刻畫。它是一種處理不確定信息的方法［6-8］。本文研究中所涉及的粗糙集相關(guān)理論如下:

定義1 粗糙集S= ＜U，R，V，F(xiàn) ＞，X?U為U上的一個概念，∪{［x］R∈U/R|［x］R∩X≠?}也是一個概念，當(dāng)X是屬性子集R所確定的U上的不分明集的并時，即X是R可定義的，R的可定義集即為R的精確集，否則X是R不可定義的，R的不可定義集即為R的非精確集或粗糙集。

定義2 (不可分辨關(guān)系)S= ＜ U，R，V，F(xiàn) ＞，設(shè)P?R，P≠?，P上的不可分辨關(guān)系定義為P中所有等價關(guān)系的交集。也記為IND(P):

定義3 (上近似、下近似)令X?U，則RX和RX稱為X關(guān)于R的上近似和下近似。

定義4 (邊界、正域、負(fù)域)集合BNG(X)=RX-RX稱為X的R邊界;POSR(X)=RX稱為X的R正域;BNG(X)=U-RX稱為X的R負(fù)域。

定義5 (關(guān)系獨(dú)立、關(guān)系依賴)設(shè)S=＜U，R，V，F(xiàn) ＞ ，屬性 P ∈ R，IND(R)=IND(R-{P}}，則稱P在R中是可缺的，否則稱P在R中是不可缺的，如果R中的每個知識都是不可缺的，則稱R是獨(dú)立的，否則就是依賴的。

定義6 (屬性核)P和Q是論域U上的2個等價關(guān)系簇，若 Q? P是獨(dú)立的，且 IND(P)=IND(Q)，則稱Q是P的約簡，在每個約簡中都不可缺的關(guān)系集合稱為核，記為 COREQ(P)。其中COREQ(P)=∩REDQ(P)，P的所有Q約簡關(guān)系簇為REDQ(P)。

定義7 (Q的P正域)設(shè)論域U上的2個等價關(guān)系簇為P和Q，則Q的P正域記為POSP(Q)，定義為

2 一種基于粗糙集屬性依賴度的決策樹算法

傳統(tǒng)的決策樹算法如ID3存在一些不足，它偏向選擇取值較多的屬性，但該屬性并不一定就是最優(yōu)的屬性，還有它只能處理離散屬性，另外該算法假設(shè)訓(xùn)練集中的正例與反例的比例與實例相一致［9］。針對ID3算法的不足，結(jié)合粗糙集相關(guān)理論，本文提出一種基于粗糙集屬性依賴度的分類算法。

定義8(屬性依賴度)設(shè)K=(U，R)為一知識庫，且P，Q?R，當(dāng)ind(P)?ind(Q)，知識Q依賴于知識P，Q對P的依賴度的定義為:

式中:PosP(Q)—Q的P正域;Card—集合的基數(shù)，當(dāng)k=0時稱Q完全獨(dú)立于P，當(dāng)0＜k＜1時稱Q粗糙依賴于P，當(dāng)k=1時稱Q完全依賴于P。

依據(jù)2個屬性集合P，Q?R之間的相互依賴程度，當(dāng)屬性α加入Q后，對于分類U/P的重要程度可以定義為:SGF(α，Q，P)=rQ(P)-rQ-{α}(P)。

基于以上理論，算法描述如下:

(1)首先選擇條件屬性集中屬性重要性最大的那個屬性作為分支節(jié)點，如果所有條件屬性的屬性重要性相同，則選擇條件屬性中信息增益最大的屬性作為分支節(jié)點，如果屬性增益也相同，則選擇序號小的屬性作為分支節(jié)點。

(2)依據(jù)第一步選擇的屬性進(jìn)行分類，接著重復(fù)以上操作，直到分類中的決策屬性一致或條件屬性選擇后不能繼續(xù)分類或決策屬性為空，產(chǎn)生葉節(jié)點，條件屬性選擇后，在屬性集中要將其刪除，保證以后分支不再選擇該條件屬性。

(3)讀樹。從根節(jié)點到葉節(jié)點對應(yīng)一條規(guī)則。

通過該算法可以得到一個相對簡單的規(guī)則集，且效率很高。

3 實驗結(jié)果與分析

本文以某企業(yè)在客戶管理中積累的客戶數(shù)據(jù)進(jìn)行研究。為了方便說明，這里從大量客戶數(shù)據(jù)中抽取10組專家評價數(shù)據(jù)，具體數(shù)據(jù)見表1。

表1 電子商務(wù)客戶價值指標(biāo)統(tǒng)計決策表

3.1 決策表離散化

粗糙集處理的數(shù)據(jù)必須是離散的，由于表1中的數(shù)據(jù)本身就是離散的，為了處理方便，只需將字符型屬性的取值變換為數(shù)字型，將條件屬性中的好(或高)用1來表示，差(或低)用0來表示。將決策屬性中的高用1來表示，低用0來表示。同時將條件屬性分別用1—8來代替，決策屬性用d代替，最后得到的離散化后的統(tǒng)計數(shù)據(jù)見表2。

表2 離散化后的統(tǒng)計數(shù)據(jù)表

3.2 屬性約簡

屬性約簡就是在保持知識庫分類能力不變的條件下，刪除不重要或不相關(guān)的屬性。目前屬性約簡方法主要有盲目法和啟發(fā)式約簡算法。由于盲目法所需時間和空間代價較高，實際約簡中主要采用的是啟發(fā)式約簡算法。對表2采用啟發(fā)式約簡算法，約簡后的統(tǒng)計數(shù)據(jù)見表3。

表3 約簡后的統(tǒng)計數(shù)據(jù)表

從約簡結(jié)果可以看出，屬性4，6，7，8是冗余屬性，而屬性1，2，3，5 是核屬性。

3.3 構(gòu)建決策樹

針對表3，用前面介紹的基于屬性依賴度的決策樹算法進(jìn)行處理，過程如下:

首先計算各條件屬性的依賴度。

PosC(D)={1，2，3，4，5，6，7，8}

對于條件屬性1:U/ind(C-1)={{1，5}，{2}，{3}，{4}，{6}，{7，8}}

PosC-1(D)={2，3，4，6}

rC-1(D)=card((PosC-1(D))/card(U)=1/2

SGF(1，C，D)=rC(D)-rC-1(D)=1-1/2=1/2

同理，對于條件屬性 2，SGF(2，C，D)=1/4;條件屬性 3，SGF(3，C，D)=1/4;條件屬性 5，SGF(5，C，D)=1/4。因此，條件屬性1將作為決策樹的根節(jié)點，分類屬性1為0時，它的分類集合為{1，3，7}，其決策屬性為一類，就停止選擇屬性。分類屬性1為1 時，它的分類集合為{2，4，5，6，8}，由于它的決策屬性不為一類，繼續(xù)選擇屬性分類，此時條件屬性集合中有2，3，5。采用上面的方法，分別計算屬性2，3，5 的重要性，結(jié)果為:SGF(2，C-1，D)=SGF(3，C-1，D)=SGF(5，C-1，D)=2/5。依據(jù)上面提出的基于粗糙集屬性依賴度的決策樹算法，則選擇條件屬性中信息增益最大的屬性作為分支節(jié)點。經(jīng)過計算，屬性2的信息增益為:Gain(2)=0.02。屬性3的信息增益為:Gain(3)=0.42。屬性5的信息增益為:Gain(5)=0.32。屬性3的信息增益最大，選擇屬性3作為分類節(jié)點，以此類推，最終構(gòu)造出的決策樹如圖1所示。

圖1 構(gòu)造出的決策樹

3.4 規(guī)則提取

由構(gòu)造出的決策樹可以得到如下的分類規(guī)則:

(1)IF單位毛利潤=“低”THEN客戶價值=“低”。

(2)IF單位毛利潤=“高”AND總服務(wù)成本=“低”THEN客戶價值=“高”。

(3)IF單位毛利潤=“高”AND總服務(wù)成本=“高”AND總購買量=“低”THEN客戶價值=“低”。

(4)IF單位毛利潤=“高”AND總服務(wù)成本=“高”AND總購買量 =“高”AND興趣度“低”THEN客戶價值=“低”。

(5)IF單位毛利潤=“高”AND總服務(wù)成本=“高”AND總購買量 =“高”AND興趣度“高”THEN客戶價值=“高”。

4 結(jié)語

提出了一種改進(jìn)的基于粗糙集屬性依賴度的決策樹算法。將其用于電子商務(wù)客戶價值分析，挖掘出有用的規(guī)則，企業(yè)可以將這些規(guī)則存入知識庫，將新客戶信息與這些規(guī)則進(jìn)行匹配，即可判斷新客戶屬于高價值還是低價值客戶，并針對不同客戶制定不同策略，最終為企業(yè)提供決策支持。

［1］Quinlan J R.Induction of Decision Trees［J］.Machine Learning，1986(1):81-106.

［2］王熙照，楊晨曉.分支合并對決策樹歸納學(xué)習(xí)的影響［J］.計算機(jī)學(xué)報，2007，30(8):1251-1258.

［3］Ziarko W.Variable Precision Rough Set Model［J］.Journal of Computer and System Sciences，1993，46(1):39-59.

［4］高雋.智能信息處理方法導(dǎo)論［M］.北京:機(jī)械工業(yè)出版社，2004:254-255.

［5］翟俊海，王熙照，張滄生.基于粗糙集技術(shù)的決策樹歸納［J］.計算機(jī)工程與應(yīng)用，2009，45(11):45-47.

［6］周玉敏.基于Rough集的數(shù)據(jù)挖掘在教學(xué)評價中的應(yīng)用［J］.重慶郵電大學(xué)學(xué)報，2008，11(3):155-156.

［7］吳尚智.粗糙集和信息熵的屬性約簡算法及其應(yīng)用［J］.計算機(jī)工程，2011，37(7):56-61.

［8］何明.一種改進(jìn)的粗糙集屬性約簡啟發(fā)式遺傳算法［J］.西安石油大學(xué)學(xué)報，2004，19(3):80-86.

［9］黃宇穎.基于粗糙集的決策樹算法在體檢系統(tǒng)中的研究［J］.計算機(jī)工程與應(yīng)用，2008，44(25):78-80.