客戶流失中數(shù)據(jù)挖掘常用算法

1、客戶流失分析中的常用數(shù)據(jù)挖掘算法摘要：數(shù)據(jù)挖掘技術(shù)為商業(yè)企業(yè)辨析客戶價(jià)值提供了重要支撐，本文首先對(duì)客戶流失的問題進(jìn)行闡述，然后列出了客戶流失分析中幾種常用數(shù)據(jù)挖掘算法。關(guān)鍵字：數(shù)據(jù)挖掘；客戶流失；算法在當(dāng)今的商業(yè)環(huán)境中，競(jìng)爭(zhēng)對(duì)手的增加、業(yè)務(wù)的多樣化和經(jīng)濟(jì)的全球化使企業(yè)之間的競(jìng)爭(zhēng)日益激烈。新經(jīng)濟(jì)時(shí)代的到來(lái)，使得客戶成為企業(yè)至關(guān)重要的成功因素和利潤(rùn)來(lái)源，誰(shuí)把握了客戶，誰(shuí)就擁有了市場(chǎng)。企業(yè)的戰(zhàn)略正從“以產(chǎn)品為中心”向“以客戶為中心”轉(zhuǎn)變。他們已經(jīng)意識(shí)到，只有不斷通過(guò)各種渠道加強(qiáng)與客戶之間的交流，并且不失時(shí)機(jī)地從中獲取有用信息，才能改善客戶關(guān)系，提高客戶滿意度，從而增強(qiáng)自身的核心競(jìng)爭(zhēng)力，在競(jìng)爭(zhēng)中立于不

2、敗之地。隨著數(shù)據(jù)挖掘技術(shù)的發(fā)展，數(shù)據(jù)挖掘在很多領(lǐng)域中所起的重要作用己經(jīng)被越來(lái)越多的人認(rèn)可，它是利用己知的數(shù)據(jù)通過(guò)建立數(shù)學(xué)模型的方法找出隱含的業(yè)務(wù)規(guī)則。在國(guó)外很多行業(yè)己經(jīng)具有成功的應(yīng)用。例如，電信行業(yè)的應(yīng)用領(lǐng)域主要有客戶關(guān)系管理，客戶欺詐分析，客戶流失分析，客戶消費(fèi)模式分析，市場(chǎng)推廣分析等。在國(guó)內(nèi)隨著對(duì)數(shù)據(jù)挖掘技術(shù)的重視，數(shù)據(jù)挖掘技術(shù)的應(yīng)用研究也越來(lái)越廣，其中對(duì)電信行業(yè)的客戶流失分析就是一大熱點(diǎn)?？蛻袅魇Х治鍪峭ㄟ^(guò)對(duì)以往流失客戶的歷史數(shù)據(jù)進(jìn)行分析，找出可能開用戶的特征，及時(shí)采取相應(yīng)措施，減少客戶流失的發(fā)生。這對(duì)企業(yè)降低運(yùn)營(yíng)成本，提高經(jīng)營(yíng)業(yè)績(jī)有著極為重要的意義。1 客戶流失分析(Customer

3、Churn Analysis)國(guó)外調(diào)查機(jī)構(gòu)的分析表明：每年有高達(dá)1/3左右的客戶流失到競(jìng)爭(zhēng)對(duì)手那里，而爭(zhēng)取、吸引一個(gè)新客戶的費(fèi)用是保住現(xiàn)有客戶費(fèi)用的515倍?？蛻袅魇б呀?jīng)成為商業(yè)企業(yè)最關(guān)注的問題之一。經(jīng)過(guò)客戶流失分析得出了一些結(jié)論：15%的客戶選擇離開是為了更低的價(jià)格，15%是因?yàn)楦玫漠a(chǎn)品，而高達(dá)70%的客戶離開是源于糟糕的服務(wù)。對(duì)于國(guó)內(nèi)某些行業(yè)如電信行業(yè)，由于近年來(lái)國(guó)內(nèi)電信行業(yè)的分割、電信體制的激烈變革，競(jìng)爭(zhēng)的急速加劇使得各電信企業(yè)忙于開拓市場(chǎng)、發(fā)展客戶，而對(duì)己有客戶的流失管理似乎大部分都重視不夠；或者是注意到了又找不到好的方法，顯得有點(diǎn)無(wú)能為力。一方面企業(yè)投入大量時(shí)間、人力、財(cái)力去發(fā)展新

4、客戶，另一方面因客戶流失管理的不完善導(dǎo)致現(xiàn)有客戶由于不滿意而流失。所以，忽視現(xiàn)有客戶的保持，只注重發(fā)展新客戶，長(zhǎng)此以往，電信企業(yè)將會(huì)出現(xiàn)“增量不增收”的局面，即每月用戶人數(shù)不斷增加，但用戶每月人均話費(fèi)收入值卻在下降。1.1 客戶流失的原因客戶流失的原因主要有以下4種類型:(1)自然流失這種類型的客戶流失不是人為因素造成的，比如客戶的搬遷和死亡等。自然流失所占的比例很小。企業(yè)可以通過(guò)廣泛建立連鎖服務(wù)網(wǎng)點(diǎn)和經(jīng)營(yíng)分公司，或者提供網(wǎng)上服務(wù)等方式，讓客戶在任何地方、任何時(shí)候都能方便快捷地使用企業(yè)的產(chǎn)品和服務(wù)，減少自然流失的發(fā)生。(2)惡意流失惡意流失是指一些客戶為了滿足自己的某些私利而離開企業(yè)，比如很多

5、電信運(yùn)營(yíng)商的用戶在拖欠了大額通信費(fèi)用后離開這家電信運(yùn)營(yíng)商，選擇其他電信運(yùn)營(yíng)商提供的服務(wù)，從而達(dá)到不交費(fèi)用的目的。惡意流失在客戶流失中所占的比例也不大。企業(yè)可以通過(guò)客戶信譽(yù)管理制度和欺詐監(jiān)測(cè)來(lái)防止客戶的惡意流失行為。(3)競(jìng)爭(zhēng)流失由于企業(yè)競(jìng)爭(zhēng)對(duì)手的影響而造成的流失稱為競(jìng)爭(zhēng)流失。市場(chǎng)上的競(jìng)爭(zhēng)突出表現(xiàn)在價(jià)格戰(zhàn)和服務(wù)戰(zhàn)上。在當(dāng)前日益激烈的市場(chǎng)競(jìng)爭(zhēng)中，企業(yè)首先要考慮的是保留住自己現(xiàn)有的客戶，在此基礎(chǔ)上再去吸引和爭(zhēng)取新的客戶。通過(guò)市場(chǎng)競(jìng)爭(zhēng)分析，包括市場(chǎng)占有率分析、競(jìng)爭(zhēng)對(duì)手發(fā)展情況分析、供應(yīng)商行為分析、合作商行為分析等，可以防止部分流失的發(fā)生。市場(chǎng)占有率分析使市場(chǎng)人員能夠了解不同時(shí)間段內(nèi)、不同業(yè)務(wù)品牌的產(chǎn)品

6、或服務(wù)的市場(chǎng)占有率情況，了解市場(chǎng)中最有價(jià)值產(chǎn)品或服務(wù)，了解不同產(chǎn)品的主要競(jìng)爭(zhēng)對(duì)手是誰(shuí)，從而為市場(chǎng)經(jīng)營(yíng)提供指導(dǎo)。從競(jìng)爭(zhēng)對(duì)手客戶發(fā)展情況、競(jìng)爭(zhēng)對(duì)手客戶話費(fèi)收入情況、競(jìng)爭(zhēng)對(duì)手客戶呼叫行為、競(jìng)爭(zhēng)對(duì)手營(yíng)銷策略、競(jìng)爭(zhēng)對(duì)手服務(wù)質(zhì)量五個(gè)方面，對(duì)競(jìng)爭(zhēng)對(duì)手發(fā)展情況進(jìn)行分析預(yù)測(cè)。(4)過(guò)失流失上述3種情況之外的客戶流失稱為過(guò)失流失。這些流失都是由于企業(yè)自身工作中的過(guò)失引起客戶的不滿意而造成的，比如企業(yè)形象不佳、產(chǎn)品性能不好、服務(wù)態(tài)度惡劣等。過(guò)失流失在客戶流失總量中所占的比例最高，但同時(shí)也是企業(yè)可以通過(guò)采取一些有效手段來(lái)防止的。1.2 客戶流失預(yù)測(cè)客戶流失預(yù)測(cè)的任務(wù)是:(1)將客戶流失的基本模型與客戶描述中的客戶生命

7、期價(jià)值結(jié)合，發(fā)現(xiàn)現(xiàn)有客戶中流失可能性大并且價(jià)值高的群體，作為下一步預(yù)防和控制流失策略的目標(biāo)客戶群體；(2)根據(jù)客戶流失的行為模型，跟蹤和發(fā)現(xiàn)客戶的流失趨勢(shì)，及早采取預(yù)防措施。1.3 客戶流失模型一般客戶流失模型的建立和應(yīng)用過(guò)程如下:(1)從企業(yè)的業(yè)務(wù)數(shù)據(jù)庫(kù)中收集整理原始數(shù)據(jù)，組建企業(yè)客戶的數(shù)據(jù)倉(cāng)庫(kù)系統(tǒng)；在客戶數(shù)據(jù)倉(cāng)庫(kù)中抽取適當(dāng)?shù)淖侄谓M成客戶分析數(shù)據(jù)庫(kù)，為客戶描述和客戶流失模型提供數(shù)據(jù)源；(2)將客戶分析數(shù)據(jù)庫(kù)分離為當(dāng)前客戶數(shù)據(jù)庫(kù)和流失客戶數(shù)據(jù)庫(kù)；(3)對(duì)流失客戶數(shù)據(jù)庫(kù)實(shí)施數(shù)據(jù)挖掘技術(shù)，發(fā)現(xiàn)客戶流失模型，包括基本特征模型和行為模式。(4)運(yùn)用客戶流失基本特征模型在當(dāng)前客戶數(shù)據(jù)庫(kù)中發(fā)現(xiàn)預(yù)測(cè)流失的群

8、體;運(yùn)用客戶流失行為模型對(duì)當(dāng)前客戶數(shù)據(jù)庫(kù)中客戶的行為進(jìn)行分析，預(yù)測(cè)流失趨勢(shì)；(5)從客戶流失模型中分析可能的流失原因，并結(jié)合(5),(6)中發(fā)現(xiàn)的預(yù)測(cè)流失群體和流失趨勢(shì)采取有效措施，來(lái)防止和減少客戶的流失。其分析過(guò)程如圖所示:業(yè)務(wù)數(shù)據(jù)庫(kù)1業(yè)務(wù)數(shù)據(jù)庫(kù)2業(yè)務(wù)數(shù)據(jù)庫(kù)n數(shù)據(jù)倉(cāng)庫(kù)客戶分析數(shù)據(jù)現(xiàn)有客戶數(shù)據(jù)流失客戶數(shù)據(jù)流失客戶基本特征流失客戶行為特征流失群體預(yù)測(cè)流失行為預(yù)測(cè)流失原因分析及對(duì)策客戶流失的分析流程圖2 常用數(shù)據(jù)挖掘算法數(shù)據(jù)挖掘(Data Mining)作為數(shù)據(jù)庫(kù)知識(shí)發(fā)現(xiàn)的核心技術(shù)，就是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的但又是潛在有用的信息或知識(shí)

9、的過(guò)程，提取的知識(shí)一般可表示為概念、規(guī)則、規(guī)律、模式等形式。確切地說(shuō)，數(shù)據(jù)挖掘過(guò)程是一種決策支持過(guò)程，主要基于人工智能、機(jī)器學(xué)習(xí)、統(tǒng)計(jì)學(xué)等技術(shù)，高度自動(dòng)化地分析生產(chǎn)業(yè)務(wù)中原有的數(shù)據(jù)，做出歸納性的推理，從中挖掘出潛在的模式，預(yù)測(cè)客戶的行為，幫助企業(yè)的決策者調(diào)整市場(chǎng)策略，減少風(fēng)險(xiǎn)，做出正確的決策。在目前商用數(shù)據(jù)挖掘軟件中一般對(duì)客戶分析的重點(diǎn)是首先對(duì)客戶行為及需求進(jìn)行分析,以及對(duì)客戶細(xì)分群進(jìn)行定義。在此客戶細(xì)分基礎(chǔ)上就可以建立周期價(jià)值分析模型,挽留響應(yīng)模型以及流失預(yù)測(cè)模型等。2.1 抽取數(shù)據(jù)與數(shù)據(jù)分析通常,數(shù)據(jù)庫(kù)中每位客戶的信息主要包括客戶基本信息，用戶賬務(wù)信息和客戶服務(wù)信息，每種信息都是由一系列客

10、戶屬性構(gòu)成。用所有的屬性來(lái)構(gòu)造模型顯然是很繁瑣的，維數(shù)過(guò)多甚至?xí)臁熬S數(shù)災(zāi)難”。因此,我們需要通過(guò)整理客戶的自然屬性(姓名，性別，年齡，職業(yè)等) 和行為屬性(電信行業(yè)中如月均話費(fèi)，短信數(shù)量，套餐選擇等)，抽象出與客戶流失相關(guān)的屬性，從而建立模型。2.2 聚類概述聚類分析被廣泛地應(yīng)用于許多領(lǐng)域，包括模式識(shí)別、圖像處理和市場(chǎng)營(yíng)銷等。一般采用聚類的方法，對(duì)流失客戶的消費(fèi)行為進(jìn)行“細(xì)分”，以便對(duì)各個(gè)不同“細(xì)分客戶”采取有針對(duì)性的市場(chǎng)營(yíng)銷工作。目前存在著大量的聚類算法，大體可以分為：(1)基于劃分的方法，比如K平均值算法，K中心點(diǎn)算法等方法；(2)基于層次的方法，比如CURE算法和BIRCH算法；(3)

11、基于密度的方法，比如DBSCAN算法；(4)基于網(wǎng)格的方法，比如STING、CLIQUE算法；(5)基于模型的方法，比如COBWEB算法等。這些聚類算法都有其各自的特點(diǎn)，算法的選擇取決于數(shù)據(jù)的類型、聚類的目的和應(yīng)用。2.2.1 EM聚類算法EM聚類算法思想，本質(zhì)上是基于混合分布的參數(shù)估計(jì)，根據(jù)“極大似然”準(zhǔn)則，估計(jì)每個(gè)簇的分布參數(shù)。采用EM聚類建模之前，需要事先指定聚類的數(shù)目，為每個(gè)簇假定一個(gè)數(shù)據(jù)分布模型，比如高斯分布，泊松分布等，這里為簡(jiǎn)化起見，假定每個(gè)簇服從同一族概率分布。完成聚類建模之后，確定各個(gè)簇的具體分布，計(jì)算每個(gè)元素的隸屬于某個(gè)簇的概率，依據(jù)概率確定各個(gè)元素的劃分。與普通的聚類模型

12、相比，EM算法的聚類劃分，是基于“概率”和“距離”的劃分，一般來(lái)說(shuō)，將隸屬概率最大的簇作為該元素的隸屬簇。目前，常用的是基于高斯混合分布的EM聚類模型，需要指出的是，基于高斯混合分布的EM聚類模型與基于歐氏距離的K均值模型是一致的。與其他聚類模型相比，EM模型算法高效，在計(jì)算機(jī)實(shí)現(xiàn)改進(jìn)算法中，只需一次遍歷即可，減少了系統(tǒng)I/O操作，極大提高了運(yùn)行效率，適合基于“海量數(shù)據(jù)”的聚類分析。當(dāng)然，也存在一些不足之處，比如需要選擇適當(dāng)?shù)母怕史植寄Ｐ?，預(yù)先指定聚類的數(shù)目等。2.3 決策樹決策樹分類算法是應(yīng)用最廣的歸納推理算法之一。它是一種逼近離散值函數(shù)的方法，對(duì)噪聲數(shù)據(jù)有很好的健壯性并且能夠?qū)W習(xí)析取表達(dá)式

13、。在這種方法中學(xué)習(xí)到的函數(shù)被表示為一棵決策樹。學(xué)習(xí)得到的決策樹也能再被表示為多個(gè)If-Then的規(guī)則，該算法己經(jīng)被成功應(yīng)用到醫(yī)療診斷和商業(yè)智能等各個(gè)領(lǐng)域。決策樹是一個(gè)類似于流程圖的樹型結(jié)構(gòu)，其中每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試。每個(gè)分枝代表一個(gè)測(cè)試輸出，而每個(gè)葉子節(jié)點(diǎn)代表類或類的分布。樹的最頂層節(jié)點(diǎn)是根節(jié)點(diǎn)。下圖為一棵簡(jiǎn)單決策樹，它是一棵貸款申請(qǐng)的決策樹模型，從中我們可以看到?jīng)Q策樹的基本組成部分：決策節(jié)點(diǎn)、分支和葉子。收入>3000高負(fù)債工作時(shí)間高風(fēng)險(xiǎn)低風(fēng)險(xiǎn)低風(fēng)險(xiǎn)高風(fēng)險(xiǎn)是是是否否否決策樹模型 決策樹的建立建立決策樹的過(guò)程，即樹的生長(zhǎng)過(guò)程是不斷地把數(shù)據(jù)進(jìn)行切分的過(guò)程，每次切分對(duì)應(yīng)一個(gè)問題

14、，也對(duì)應(yīng)著一個(gè)節(jié)點(diǎn)。對(duì)每個(gè)切分都要求分成的組之間的“差異”最大。決策樹的建立過(guò)程通常分為兩個(gè)階段:建樹和剪枝。決策樹歸納的基本算法是貪心算法，它以自頂向下遞歸的各個(gè)擊破方式構(gòu)造判定樹。下面描述了由訓(xùn)練樣本歸納判定樹的ID3的基本算法。建樹算法：Generate_decision_tree由給定的訓(xùn)練數(shù)據(jù)產(chǎn)生一棵判定樹。輸入：訓(xùn)練樣本samples，由離散值屬性表示；候選屬性的集合attributelist。輸出：一棵決策樹。方法：1)創(chuàng)建節(jié)點(diǎn)N；2)If samples都在同一個(gè)類C then；3)返回N作為葉節(jié)點(diǎn)，以類C標(biāo)記；4)If attribute_list為空，then；5)返回N作

15、為葉節(jié)點(diǎn)，標(biāo)記為Samples中的最普通的類；6)選擇attribut_list中具有最高信息增益的屬性test attribute；7)標(biāo)記節(jié)點(diǎn)N為test_attribute；8)for each test_attribute中的己知值ai ；9)由節(jié)點(diǎn)N長(zhǎng)出一個(gè)條件為test_attribute=ai的分枝；10)設(shè)S2是samples中test_attribute=a的樣本的集合；11)If S2為空then；12)加上一個(gè)樹葉，標(biāo)記為samples中最普通的類；13)else加上一個(gè)Generate_decision_tree(S1,attribute_list-test_attri

16、bute)。剪枝的目的是降低由于訓(xùn)練集的噪聲而產(chǎn)生的起伏。算法的基本策略如下：l 樹以代表訓(xùn)練樣本的單個(gè)節(jié)點(diǎn)開始(步驟1)。l 如果樣本都在同一個(gè)類，則該節(jié)點(diǎn)成為樹葉，并用該類標(biāo)記(步驟2和3)。l 否則，算法使用稱為信息增益的基于熵的度量作為啟發(fā)信息，選擇能夠 最好地將樣本分類的屬性(步驟6)。該屬性成為該節(jié)點(diǎn)的“測(cè)試”或“判定”屬性(步驟7)。在該算法中，所有的屬性都取離散值，連續(xù)值的屬性必須離散化。l 對(duì)測(cè)試屬性的每個(gè)已知值，創(chuàng)建一個(gè)分枝，并據(jù)此劃分樣本(步驟8-10)l 算法使用同樣的過(guò)程，遞歸地形成每個(gè)劃分上的樣本判定樹。一旦一個(gè)屬性出現(xiàn)在一個(gè)節(jié)點(diǎn)上，就不必考慮該節(jié)點(diǎn)的任何后代節(jié)點(diǎn)(

17、步驟13)。l 遞歸劃分步驟僅當(dāng)下列條件之一成立時(shí)停止：(a)給定節(jié)點(diǎn)的所有樣本屬于同一類(步驟2和3)；(b)沒有剩余屬性可以用來(lái)進(jìn)一步劃分樣本(步驟4)。在此情況下，使用多數(shù)表決(步驟5)。這涉及將給定的節(jié)點(diǎn)轉(zhuǎn)換成樹葉，并用samples中的多數(shù)所在的類標(biāo)記它。換一種方式，可以存放節(jié)點(diǎn)樣本的類分布。(c)分枝test_attribute=ai沒有樣本(步驟11)。在這種情況下，以samples中的多數(shù)類創(chuàng)建一個(gè)樹葉(步驟12) 屬性劃分的度量方法1 信息增益算法ID3和C4.5使用信息增益作為選擇屬性對(duì)節(jié)點(diǎn)進(jìn)行劃分的指標(biāo)。信息增益最高的劃分將被作為分裂方案。信息增益表示系統(tǒng)由于分類獲得的信

18、息量，由系統(tǒng)熵的減少值來(lái)定量描述。將數(shù)據(jù)集S用屬性A劃分后的信息增益作為數(shù)據(jù)集S劃分前后的熵差：選擇屬性對(duì)節(jié)點(diǎn)進(jìn)行劃分的標(biāo)準(zhǔn)是劃分屬性應(yīng)具有最高信息增益。熵是一個(gè)衡量信息混亂程度的統(tǒng)計(jì)量。熵越大，表示系統(tǒng)越混亂。分類的目的是提取系統(tǒng)信息，使系統(tǒng)向更加有序，有規(guī)則組織的方向發(fā)展。所以，最佳的劃分方案是使熵減少量最大的劃分方案。劃分后熵的減少量就是信息增益，所以，選擇屬性對(duì)節(jié)點(diǎn)進(jìn)行劃分的標(biāo)準(zhǔn)就是選取信息增益最大的屬性。通常，決策樹是“貪心算法+深度優(yōu)先搜索”得到的。2 增益比率信息增益度量存在一個(gè)內(nèi)在偏置，它偏袒具有較多值的屬性。避免這個(gè)不足的一種方法是用其它度量而不是信息增益來(lái)選擇決策屬性。一個(gè)

19、可以選擇的度量標(biāo)準(zhǔn)是增益比率。增益比率通過(guò)加入一個(gè)被稱作分裂信息的項(xiàng)來(lái)衡量屬性分裂數(shù)據(jù)的廣度和均勻性：其中，S1到Sc是c個(gè)值的屬性A分割S而形成的c個(gè)樣例子集。注意分裂信息實(shí)際上就是S關(guān)于屬性A的各值的熵。增益比率度量是用前面的增益度量和這里的分裂信息度量來(lái)共同定義的，即：使用增益比率代替增益來(lái)選擇屬性產(chǎn)生的一個(gè)實(shí)際問題是，當(dāng)某個(gè)|=|時(shí)，分母可能為0或非常小。若某個(gè)屬性對(duì)于S的所有樣例有幾乎同樣的值，這樣要么導(dǎo)致增益比率未定義，要么增益比率非常大。為了避免選擇這種屬性可以采用一些啟發(fā)式規(guī)則，比如先計(jì)算每個(gè)屬性的增益，然后僅對(duì)那些增益高于平均值的屬性應(yīng)用增益比率測(cè)試。算法C5.0采用了這種方

20、法。3 基尼指數(shù)如果決策樹是二叉樹，常用基尼指數(shù)作為劃分的標(biāo)準(zhǔn)。CART算法首先采用了基尼指數(shù)作為選擇屬性對(duì)節(jié)點(diǎn)進(jìn)行劃分的標(biāo)準(zhǔn)。設(shè)數(shù)據(jù)集S的分類屬性C有m個(gè)不同的離散屬性值c1，cm ，即S中的記錄有m個(gè)類別，那么其基尼指數(shù)就是：，其中Pi是類別ci出現(xiàn)的頻率。如果用屬性A將數(shù)據(jù)集S分成兩部分S1，S2 。那么這個(gè)劃分的基尼指數(shù)就是：選擇基尼指數(shù)最小的屬性對(duì)節(jié)點(diǎn)數(shù)據(jù)進(jìn)行劃分。決策樹是二叉樹時(shí)，設(shè)離散型屬性A有v個(gè)屬性值，則屬性A可有2v種劃分?jǐn)?shù)據(jù)集S的方法，其中一種劃分方法的基尼指數(shù)最小，稱之為屬性A的最佳劃分方法。在選擇節(jié)點(diǎn)最佳劃分時(shí)，首先找出每個(gè)屬性的最佳劃分方法，再比較所有屬性的最佳劃分

21、方法，從中選出基尼指數(shù)最小者，最后選出節(jié)點(diǎn)的最佳劃分。4 用數(shù)值型屬性劃分節(jié)點(diǎn)方法在分類應(yīng)用中，分類屬性必須是離散型屬性，其他屬性可以為數(shù)值型屬性。決策樹算法中如何利用數(shù)值型屬性來(lái)劃分節(jié)點(diǎn)呢？設(shè)A為數(shù)值型屬性，A最多可能有n個(gè)屬性值(n為數(shù)據(jù)集S的全部記錄數(shù))。數(shù)值型屬性A將數(shù)據(jù)集S劃分為兩組。對(duì)應(yīng)的條件為A<=a 和A>a。如何選擇A呢？可以先對(duì)數(shù)據(jù)集S按字段A的值遞增排序，設(shè)A的屬性值排序后的結(jié)果為V1,V2，Vn， 從小到大依次取不同的分裂點(diǎn)，取信息增益最大(基尼指數(shù)最小)的一個(gè)就是A的最佳劃分。若V1為最佳分裂點(diǎn)，通常取a=( Vi+Vi-1 )/2。建樹時(shí)，在每個(gè)節(jié)點(diǎn)上都

22、需要對(duì)數(shù)值型字段排序以便計(jì)算信息增益(或基尼指數(shù))。 剪枝在建樹過(guò)程中，由于訓(xùn)練集中的噪聲，孤立點(diǎn)以及某個(gè)節(jié)點(diǎn)的數(shù)據(jù)量太小，決策樹的許多分枝反映出訓(xùn)練集中的異常。這就是決策樹的過(guò)度擬合(OverFitting)問題。它表現(xiàn)為用某些分類規(guī)則對(duì)訓(xùn)練集預(yù)測(cè)十分準(zhǔn)確，而對(duì)測(cè)試集預(yù)測(cè)卻誤差極大。過(guò)分適應(yīng)問題是影響決策樹準(zhǔn)確率的關(guān)鍵問題，剪去決策樹的冗余分枝是解決過(guò)分適應(yīng)問題的重要方法。剪枝常常利用統(tǒng)計(jì)學(xué)方法，去掉最不可靠，可能是噪音的一些分枝。2.3.3.1 剪枝的分類在構(gòu)建決策樹的過(guò)程中，對(duì)決策樹進(jìn)行剪枝是非常有必要的。通常情況下，剪枝方法可以分為兩大類：1)事前剪枝(Pre一Pruning)該方法通

23、過(guò)提前停止分枝生成過(guò)程。即通過(guò)在當(dāng)前節(jié)點(diǎn)上就判斷是否需要繼續(xù)劃分該節(jié)點(diǎn)所含訓(xùn)練樣本集來(lái)實(shí)現(xiàn)。一旦停止分枝，當(dāng)前節(jié)點(diǎn)就成為一個(gè)葉節(jié)點(diǎn)。該葉節(jié)點(diǎn)中可能包含多個(gè)不同類別的訓(xùn)練樣本。在建造一棵決策樹時(shí)，可以利用統(tǒng)計(jì)上的重要檢測(cè)x2檢驗(yàn)或信息增益等來(lái)對(duì)分枝生成情況(優(yōu)劣)進(jìn)行評(píng)估。如果在一個(gè)節(jié)點(diǎn)上劃分樣本集時(shí)，會(huì)導(dǎo)致(所產(chǎn)生的)節(jié)點(diǎn)中樣本數(shù)少于指定的閩值，那么就要停止繼續(xù)分解樣本集合。但確定這樣一個(gè)合理的閾值常常比較困難。閾值過(guò)大會(huì)導(dǎo)致決策樹過(guò)于簡(jiǎn)單化，而閾值過(guò)小時(shí)又會(huì)導(dǎo)致多余樹枝無(wú)法修剪。2)事后剪枝(Post一Pruning)先建樹，后修剪。讓樹“完全生長(zhǎng)”，然后采用一定的標(biāo)準(zhǔn)評(píng)估每個(gè)內(nèi)部節(jié)點(diǎn)下的分枝是否是冗余分枝，若是，剪掉冗余分枝使內(nèi)部節(jié)點(diǎn)成為一個(gè)最有，叮能的葉節(jié)點(diǎn)。.2 剪枝的標(biāo)準(zhǔn)無(wú)論是通過(guò)事前剪枝還是事后剪枝來(lái)得到正確規(guī)模的樹，一個(gè)關(guān)鍵的問題是使用什么樣的標(biāo)準(zhǔn)來(lái)確定最終正確的樹的規(guī)模。剪枝的標(biāo)準(zhǔn)有如下兩種：1) 期望錯(cuò)誤率最小原則：選擇期望錯(cuò)誤率最小的子樹進(jìn)行剪枝，對(duì)樹中的內(nèi)部節(jié)點(diǎn)計(jì)算其剪枝和不剪枝可能出現(xiàn)的期望錯(cuò)誤率，比較后加以取舍；2) 最小描述長(zhǎng)度原則；最簡(jiǎn)單的解釋是最期望的，對(duì)決策樹二進(jìn)位編碼，編碼所需二進(jìn)位最少的樹即為最佳剪枝樹。2.4 人工神經(jīng)網(wǎng)絡(luò)人工神經(jīng)網(wǎng)絡(luò)(Artifi