決策樹技術在網上書店系統中的應用

[摘要] 數據挖掘技術是在大量的數據中發現未知知識的數據分析技術，利用數據挖掘技術分析客戶數據，發現其中的規律，從而為商務決策提供依據。本文對決策樹技術進行了相關分析，并應用于網上書店系統，實現對客戶數據的挖掘。

[關鍵詞] ID3算法 決策樹 數據挖掘 網上書店

目前，據《電腦商情報》通過最近的調查研究得出的結果顯示，截至去年6月，我國的網上書店數量已經達到300家以上，比前年同期增長25.8%。同行之間的競爭日益激烈，特別是客戶是商家爭奪的焦點。

網上書店的業務系統每天都要產生大量的業務數據，這些業務數據記錄了各類客戶在網上書店相關業務的信息和客戶的基本信息，這些數據用數據庫保存起來。在競爭日益激烈的知識經濟環境下，數據庫不再只是用于查詢、輸出報表等一般的用途，還要在眾多的數據中挖掘出有用的知識以便作為決策支持。這些數據中的一部分是需要經過一番分析形成知識后才能被決策所利用。數據挖掘技術在網上購書系統中起著重要作用，使用數據挖掘技術進行訂單數據的挖掘， 通過決策樹技術得到客戶進行分析，發現客戶所處的生命周期，針對處于不同客戶生命周期的客戶，采取個性化的策略，實現向其推薦書籍和客戶保持，提高客戶滿意度，進而建立忠誠度。從而實現客戶的保持，防止客戶流失。

一、決策樹技術基本概述

決策樹基本思想是：選取一個最能區分不同類別樣本的屬性，讓其作為樹根，并把訓練樣本集分為相應的幾塊，接下來再依次在每一塊樣本集中選出區分度最大的屬性，作為樹的第二層結點。依此類推，直到所有的葉結點都只包含一類樣本時終止，這樣構建起來的一棵樹就稱作決策樹。然后進行驗證，就可得出結果。因此在分析客戶流失情況時，將己有的客戶信息的統計作為基礎數據，選擇好的屬性，構造決策樹，決策樹技術可以清晰的顯示哪些字段比較重要，對挽留客戶指明了方向。

決策樹是應用非常廣泛的分類方法，目前有多種決策樹方法，如ID3、CN2、SLIQ、SPRINT等。

二、ID3算法及其在網上書店中的應用

ID3算法是Quinlan提出的一個著名決策樹生成方法。它的基本概念是決策樹中每一個非結點對應著一個非類別屬性，樹枝代表這個屬性的值。一個葉結點代表從樹根到葉結點之間的路徑對應的記錄所屬的類別屬性值。每一個非葉結點都將與屬性中具有最大信息量的非類別屬性相關聯。采用信息增益來選擇能夠最好地將樣本分類的屬性。

ID3選擇具有最高信息增益的屬性作為當前結點的測試屬性。該屬性使得對結果劃分中的樣本分類所需的信息量最小，并反映劃分的最小隨機性或“不純性”。這種信息理論方法使得對一個對象分類所需的期望測試數目達到最小，并盡量確保找到一棵簡單的樹來刻畫相關的信息。

設S是s個數據樣本的集合，假定類標號屬性具有m個不同值，定義m個不同類Ci（i =1，2，…，m）設si是Ci類中的樣本數，對一個給定的樣本分類所需的期望信息由下式給出：

其中，Pi是任意樣本屬于Ci的概率，并用si/s估計。

設屬性A具有v個不同值{a1，a2，…，av｝，可以用屬性A將S劃分為v個子｛Si，…，Sv｝，其中，Sj包含 S中這樣一些樣本，它們對應的屬性A的值為aj。如果A選作測試屬性（即最好的劃分屬性），則這些子集對應于由包含集合S的結點生長出來的分支。設sij是子集Sj中類Ci的樣本數。根據A劃分的子集的嫡或期望信息由下式給出：

充當第j個子集的權，并且等于子集(即A值為ai)中的樣本個數除以S中的樣本總數。

這次分類之后，還需要的分類信息量為：

Pij是Sj中的樣本屬于類Ci的概率。

對描述屬性的元素計算信息增益值：

選擇最高信息增益的創建一個結點，并以該屬性標記，對該屬性的每個值創建一個分支，并據此進行劃分。

網上書店分析客戶流失情況，決策樹技術中的是解決這一問題的有效途徑。ID3算法是一個著名決策樹生成方法。具體的過程如下：

1.構造訓練集

根據各種渠道收集的用戶信息以及日志文件創建了網上書店的數據倉庫，從中提取客戶活動信息。如下表:

表 訓練集

2.信息增益計算

將決策樹的算法應用在客戶保持中，生成決策樹算法的執行過程描述如下：

計算IfLost的期望信息：

類標號屬性IfLost有兩個不同值｛yes，no｝，因此有兩個不同的類（ｍ＝2）。設類C1對應于yes，而C2對應于no，類yes有6個樣本，類no有4個樣本。

根據公式，可得給定樣本分類所需的期望信息：

計算每個屬性的期望信息。從屬性業務種類（Online-time）開始，觀察Online-time的每個樣本的yes和no分布，可算出Online-time的期望信息：

對于Online_time＝“＜3小時”s11=2，s21=2

Online_time＝“≥3小時”s12=4，s22=2

根據公式(5-4），樣本按Online-time劃分，對一個給定的樣本計算Online-time的期望信息為:

同理，計算出屬性ContracType、IfInsales、Proression的期望信息。

因此，根據公式，計算出Online-time的信息增益是：

同理得到ContractType、IfInsales、Profession的信息增益：

Gain(ContractType)=0.44635

Gain(IfInsales)=0.12452

Gain(Profession)=0.13530

根據計算出的信息增益，對應最高信息增益的結點作為分枝結點，分枝結點ContractType在屬性中具有最高信息增益，選作測試屬性，創建一個屬性，用ContractType作標志，并對于每個屬性值，引出一個分支，樣本據此劃分，初始分枝點如圖1所示。

圖1 是否參加過促銷活動的分支

重復上述過程，直到樹不再生長。再對以上的兩個分支作為初始分裂點分別計算每個屬性的信息增益，選出測試屬性，創建結點繼續樹的生長，算法最終返回的決策樹如下圖2所示。

圖2 最后生成的決策樹

從上面對決策樹分析，結果表明：合同類型是決策樹分枝的最重要因素，其次為從事職業、在線時長、促銷活動等。結果表明：

易流失客戶為：與本網上書店未簽訂合同，每日上網時間長＜3小時的普通客戶；與本網上書店簽訂團體合同，行政機關；與本網上書店未簽訂合同，從事行政工作的公務員。

非流失客戶為：與本網上書店簽訂個人合同，從事教育工作的教育工作者；與本網上書店簽訂團體合同，從事教育事業的教育機構；與本網上書店未簽訂合同，每日上網時間長≥3小時的普通客戶；與本網上書店簽訂個人合同，從事行政工作的公務員。這些客戶是本網站的注冊者、常客、忠實客戶。

三、決策樹技術在網上書店中的應用

挖掘的目的是為了應用。因此，利用能夠實現分類回歸樹的算法的數據挖掘工具，可以精確獲得預測流失率，建立流失預測模型，分析客戶流失傾向，即可在客戶流失之前做出預警可能性的大小。業務人員也可以根據每個客戶的流失可能性對客戶從高到低排序，找出流失傾向較高的群體，并結合這些客戶對應的分群特征，采取相應的客戶挽留策略，以進行更加精細的客戶保有工作，提高客戶挽留的成功率。

四、結束語

利用決策樹技術可以挖掘大量的客戶信息為構建預測模型，較準確地找出符合離開因素的客戶，制定相應的方案。最大程度挽留他們。本文對決策樹技術的基本思想和決策樹生成方法ID3算法進行了詳細的分析，討論了網上書店系統業務信息的挖掘。本文中許多方法和思路在比如超市其他方面有一定的借鑒意義。

參考文獻：

[1]范云峰:客戶開發營銷[M].北京:中國對處經濟貿易出版社，2003.7

[2]毛國君段立娟:數據挖掘原理與算法[M].清華大學出版社，2005.7

[3]蘇新寧楊建林:數據倉庫和數據挖掘[M].清華大學出版社，2006.4

[4]中國人民大學統計學數據挖掘中心：數據挖掘中的決策樹技術入其應用[J].統計與信息論壇.2002.3

[5]費賢舉王文琴莊燕濱:基于關聯規則的數據挖掘技術在CRM中的應用研究[J].常州工學院學報.2005.4

[6]徐緒松：數據結構與算法導論[M].北京：電子工業出版社，1996