決策樹(shù)資料專(zhuān)業(yè)知識(shí)講座

主要內(nèi)容決策樹(shù)基本概念決策樹(shù)算法決策樹(shù)研究問(wèn)題主要參照文獻(xiàn)第1頁(yè)第6章決策樹(shù)決策樹(shù)算法計(jì)數(shù)年紀(jì)收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)假定公司搜集了左表數(shù)據(jù)，那么對(duì)于任意給定客人（測(cè)試樣例），你能幫助公司將這位客人歸類(lèi)嗎？即：你能預(yù)測(cè)這位客人是屬于“買(mǎi)”計(jì)算機(jī)那一類(lèi)，還是屬于“不買(mǎi)”計(jì)算機(jī)那一類(lèi)？又：你需要多少有關(guān)這位客人信息才能回答這個(gè)問(wèn)題？決策樹(shù)用途第2頁(yè)第6章決策樹(shù)計(jì)數(shù)年紀(jì)收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)誰(shuí)在買(mǎi)計(jì)算機(jī)？年紀(jì)？學(xué)生？信譽(yù)？買(mǎi)青中老否是優(yōu)良不買(mǎi)買(mǎi)買(mǎi)不買(mǎi)決策樹(shù)用途決策樹(shù)算法第3頁(yè)第6章決策樹(shù)計(jì)數(shù)年紀(jì)收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)誰(shuí)在買(mǎi)計(jì)算機(jī)？年紀(jì)？學(xué)生？信譽(yù)？買(mǎi)青中老否是優(yōu)良不買(mǎi)買(mǎi)買(mǎi)不買(mǎi)決策樹(shù)用途決策樹(shù)算法第4頁(yè)第6章決策樹(shù)決策樹(shù)算法決策樹(shù)表達(dá)決策樹(shù)基本組成部分：決策結(jié)點(diǎn)、分支和葉子。年紀(jì)？學(xué)生？信譽(yù)？買(mǎi)青中老否是優(yōu)良不買(mǎi)買(mǎi)買(mǎi)不買(mǎi)決策樹(shù)中最上面結(jié)點(diǎn)稱(chēng)為根結(jié)點(diǎn)。是整個(gè)決策樹(shù)開(kāi)始。每個(gè)分支是一個(gè)新決策結(jié)點(diǎn)，或者是樹(shù)葉子。每個(gè)決策結(jié)點(diǎn)代表一種問(wèn)題或者決策.一般對(duì)應(yīng)待分類(lèi)對(duì)象屬性。每個(gè)葉結(jié)點(diǎn)代表一種也許分類(lèi)成果在沿著決策樹(shù)從上到下遍歷過(guò)程中，在每個(gè)結(jié)點(diǎn)都有一種測(cè)試。對(duì)每個(gè)結(jié)點(diǎn)上問(wèn)題不一樣測(cè)試輸出造成不一樣分枝，最后會(huì)達(dá)成一種葉子結(jié)點(diǎn)。這一過(guò)程就是利用決策樹(shù)進(jìn)行分類(lèi)過(guò)程，利用若干個(gè)變量來(lái)判斷屬性類(lèi)別第5頁(yè)第6章決策樹(shù)計(jì)數(shù)年紀(jì)收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)決策樹(shù)算法第6頁(yè)第6章決策樹(shù)計(jì)數(shù)年紀(jì)收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)第1步計(jì)算決策屬性熵決策屬性“買(mǎi)計(jì)算機(jī)？”。該屬性分兩類(lèi)：買(mǎi)/不買(mǎi)S1(買(mǎi))=641S2（不買(mǎi)）=383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740I(S1,S2)=I(641,383)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9537決策樹(shù)算法第7頁(yè)第6章決策樹(shù)計(jì)數(shù)年紀(jì)收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)第2步計(jì)算條件屬性熵條件屬性共有4個(gè)。分別是年紀(jì)、收入、學(xué)生、信譽(yù)。分別計(jì)算不一樣屬性信息增益。決策樹(shù)算法第8頁(yè)第6章決策樹(shù)計(jì)數(shù)年紀(jì)收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)第2-1步計(jì)算年紀(jì)熵年紀(jì)共分三個(gè)組：青年、中年、老年青年買(mǎi)與不買(mǎi)百分比為128/256S1(買(mǎi))=128S2（不買(mǎi)）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183決策樹(shù)算法第9頁(yè)第6章決策樹(shù)計(jì)數(shù)年紀(jì)收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)第2-2步計(jì)算年紀(jì)熵年紀(jì)共分三個(gè)組：青年、中年、老年中年買(mǎi)與不買(mǎi)百分比為256/0S1(買(mǎi))=256S2（不買(mǎi)）=0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0決策樹(shù)算法第10頁(yè)第6章決策樹(shù)計(jì)數(shù)年紀(jì)收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)第2-3步計(jì)算年紀(jì)熵年紀(jì)共分三個(gè)組：青年、中年、老年老年買(mǎi)與不買(mǎi)百分比為257/127S1(買(mǎi))=257S2（不買(mǎi)）=127S=S1+S2=384P1=257/384P2=127/384I(S1,S2)=I(125，127)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9157決策樹(shù)算法第11頁(yè)第6章決策樹(shù)計(jì)數(shù)年紀(jì)收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)第2-4步計(jì)算年紀(jì)熵年紀(jì)共分三個(gè)組：青年、中年、老年所占百分比青年組384/1024=0.375中年組256/1024=0.25老年組384/1024=0.375計(jì)算年紀(jì)平均信息盼望E（年紀(jì)）=0.375*0.9183+0.25*0+0.375*0.9157=0.6877G（年紀(jì)信息增益）=0.9537-0.6877=0.2660（1）決策樹(shù)算法第12頁(yè)第6章決策樹(shù)計(jì)數(shù)年紀(jì)收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)第3步計(jì)算收入熵收入共分三個(gè)組：高、中、低E（收入）=0.9361收入信息增益=0.9537-0.9361=0.0176(2)決策樹(shù)算法第13頁(yè)第6章決策樹(shù)計(jì)數(shù)年紀(jì)收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)第4步計(jì)算學(xué)生熵學(xué)生共分二個(gè)組：學(xué)生、非學(xué)生E（學(xué)生）=0.7811年紀(jì)信息增益=0.9537-0.7811=0.1726（3）決策樹(shù)算法第14頁(yè)第6章決策樹(shù)計(jì)數(shù)年紀(jì)收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)第5步計(jì)算信譽(yù)熵信譽(yù)分二個(gè)組：良好，優(yōu)秀E（信譽(yù)）=0.9048信譽(yù)信息增益=0.9537-0.9048=0.0453（4）決策樹(shù)算法第15頁(yè)第6章決策樹(shù)計(jì)數(shù)年紀(jì)收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)第6步計(jì)算選擇節(jié)點(diǎn)年紀(jì)信息增益=0.9537-0.6877=0.2660（1）收入信息增益=0.9537-0.9361=0.0176（2）年紀(jì)信息增益=0.9537-0.7811=0.1726（3）信譽(yù)信息增益=0.9537-0.9048=0.0453（4）決策樹(shù)算法第16頁(yè)第6章決策樹(shù)計(jì)數(shù)年紀(jì)收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)64青中是優(yōu)買(mǎi)年紀(jì)青年中年老年買(mǎi)/不買(mǎi)買(mǎi)買(mǎi)/不買(mǎi)葉子決策樹(shù)算法第17頁(yè)第6章決策樹(shù)計(jì)數(shù)年紀(jì)收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)64青中是優(yōu)買(mǎi)青年買(mǎi)與不買(mǎi)百分比為128/256S1(買(mǎi))=128S2（不買(mǎi)）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183決策樹(shù)算法第18頁(yè)第6章決策樹(shù)計(jì)數(shù)年紀(jì)收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)64青中是優(yōu)買(mǎi)假如選擇收入作為節(jié)點(diǎn)分高、中、低條件熵就是E： E(收入）=0.3333*0+0.5*0.9183+0.1667*0=0.4592Gain(收入)=I(128,256)-E(收入)=0.9183–0.4592=0.4591Gain就是計(jì)算信息增益I(0,128)=0百分比:128/384=0.3333I(64,128)=0.9183百分比:192/384=0.5I(64,0)=0百分比:64/384=0.1667注意決策樹(shù)算法第19頁(yè)第6章決策樹(shù)計(jì)數(shù)年紀(jì)收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)132老中是良買(mǎi)64青中是優(yōu)買(mǎi)32中中否優(yōu)買(mǎi)32中高是良買(mǎi)63老中否優(yōu)不買(mǎi)1老中否優(yōu)買(mǎi)年紀(jì)青年中年老年學(xué)生買(mǎi)信譽(yù)葉子否是優(yōu)良買(mǎi)不買(mǎi)買(mǎi)/不買(mǎi)買(mǎi)葉子葉子葉子決策樹(shù)算法第20頁(yè)第6章決策樹(shù)ID3決策樹(shù)建立算法1決定分類(lèi)屬性；2對(duì)目前數(shù)據(jù)表，建立一種節(jié)點(diǎn)N3假如數(shù)據(jù)庫(kù)中數(shù)據(jù)都屬于同一種類(lèi)，N就是樹(shù)葉，在樹(shù)葉上標(biāo)出所屬類(lèi)4假如數(shù)據(jù)表中沒(méi)有其他屬性能夠考慮，則N也是樹(shù)葉，按照少數(shù)服從多數(shù)標(biāo)準(zhǔn)在樹(shù)葉上標(biāo)出所屬類(lèi)別5不然，根據(jù)平均信息盼望值E或GAIN值選出一種最佳屬性作為節(jié)點(diǎn)N測(cè)試屬性6節(jié)點(diǎn)屬性選定后，對(duì)于該屬性中每個(gè)值：從N生成一種分支，并將數(shù)據(jù)表中與該分支有關(guān)數(shù)據(jù)搜集形成份支節(jié)點(diǎn)數(shù)據(jù)表，在表中刪除節(jié)點(diǎn)屬性那一欄假如分支數(shù)據(jù)表非空，則利用以上算法從該節(jié)點(diǎn)建立子樹(shù)。決策樹(shù)算法第21頁(yè)第6章決策樹(shù)決策樹(shù)數(shù)據(jù)準(zhǔn)備姓名年紀(jì)收入學(xué)生信譽(yù)電話地址郵編買(mǎi)計(jì)算機(jī)張三234000是良281-322-03282714Ave.M77388買(mǎi)李四342800否優(yōu)713-239-78305606HollyCr78766買(mǎi)王二701900否優(yōu)281-242-32222023BellBlvd.70244不買(mǎi)趙五18900是良281-550-0544100MainStreet70244買(mǎi)劉蘭342500否優(yōu)713-239-7430606HollyCt78566買(mǎi)楊俊278900否優(yōu)281-355-7990233RiceBlvd.70388不買(mǎi)張毅389500否優(yōu)281-556-0544399SugarRd.78244買(mǎi)。。。。。。。。原始表決策樹(shù)算法第22頁(yè)第6章決策樹(shù)計(jì)數(shù)年紀(jì)收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低是良買(mǎi)64老低是優(yōu)不買(mǎi)64中低是優(yōu)買(mǎi)128青中否良不買(mǎi)64青低是良買(mǎi)。。。整頓后數(shù)據(jù)表決策樹(shù)數(shù)據(jù)準(zhǔn)備Datacleaning 刪除/減少noise，補(bǔ)填missingvaluesDatatransformation 數(shù)據(jù)標(biāo)準(zhǔn)化（datanormalization） 數(shù)據(jù)歸納（generalizedatatohigher-levelconceptsusingconcepthierarchies） 例如：年紀(jì)歸納為老、中、青三類(lèi) 控制每個(gè)屬性也許值不超出七種（最佳不超出五種）Relevanceanalysis 對(duì)于與問(wèn)題無(wú)關(guān)屬性：刪 對(duì)于屬性也許值大于七種又不能歸納屬性：刪決策樹(shù)算法第23頁(yè)第6章決策樹(shù)決策樹(shù)數(shù)據(jù)準(zhǔn)備決策樹(shù)算法處理連續(xù)屬性值決策樹(shù)算法比較適合處理離散數(shù)值屬性。實(shí)際應(yīng)用中屬性是連續(xù)或者離散情況都比較常見(jiàn)。在應(yīng)用連續(xù)屬性值時(shí)，在一種樹(shù)結(jié)點(diǎn)能夠?qū)傩訟i值劃分為幾個(gè)區(qū)間。然后信息增益計(jì)算就能夠采取和離散值處理同樣辦法。標(biāo)準(zhǔn)上能夠?qū)i屬性劃分為任意數(shù)目標(biāo)空間。C4.5中采取是二元分割（BinarySplit）。需要找出一種合適分割閾值。參照C4.5算法Top10algorithmsindataminingKnowledgeInformationSystem202314:1–37第24頁(yè)第6章決策樹(shù)決策樹(shù)算法ID3算法小結(jié)ID3算法是一種典型決策樹(shù)學(xué)習(xí)算法，由Quinlan于1979年提出。ID3算法基本思想是，以信息熵為度量，用于決策樹(shù)節(jié)點(diǎn)屬性選擇，每次優(yōu)先選用信息量最多屬性，亦即能使熵值變?yōu)樽钚傩?，以?gòu)造一顆熵值下降最快決策樹(shù)，到葉子節(jié)點(diǎn)處?kù)刂禐?。此時(shí)，每個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)實(shí)例集中實(shí)例屬于同一類(lèi)。第25頁(yè)第6章決策樹(shù)決策樹(shù)算法ID3算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（1）通過(guò)ID3算法來(lái)實(shí)現(xiàn)客戶流失預(yù)警分析，找出客戶流失特性，以幫助電信公司有針對(duì)性地改善客戶關(guān)系，避免客戶流失利用決策樹(shù)辦法進(jìn)行數(shù)據(jù)挖掘，一般有如下步驟：數(shù)據(jù)預(yù)處理、決策樹(shù)挖掘操作，模式評(píng)定和應(yīng)用。電信運(yùn)行商客戶流失有三方面含義：一是指客戶從一種電信運(yùn)行商轉(zhuǎn)網(wǎng)到其他電信運(yùn)行商，這是流失分析重點(diǎn)。二是指客戶月平均消費(fèi)量減少，從高價(jià)值客戶成為低價(jià)值客戶。三、指客戶自然流失和被動(dòng)流失。在客戶流失分析中有兩個(gè)關(guān)鍵變量：財(cái)務(wù)原因／非財(cái)務(wù)原因、積極流失／被動(dòng)流失?？蛻袅魇軌?qū)?yīng)分為四種類(lèi)型：其中非財(cái)務(wù)原因積極流失客戶往往是高價(jià)值客戶。他們會(huì)正常支付服務(wù)費(fèi)用，并容易對(duì)市場(chǎng)活動(dòng)有所響應(yīng)。這種客戶是電信公司真正需要保住客戶。第26頁(yè)第6章決策樹(shù)決策樹(shù)算法ID3算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（2）數(shù)據(jù)預(yù)處理數(shù)據(jù)挖掘處理對(duì)象是大量數(shù)據(jù)，這些數(shù)據(jù)一般存放在數(shù)據(jù)庫(kù)系統(tǒng)中（該顧客有關(guān)數(shù)據(jù)存放在其CRM中），是長(zhǎng)期積累成果。但往往不適合直接挖掘，需要做數(shù)據(jù)預(yù)處理工作，一般包括數(shù)據(jù)選擇(選擇有關(guān)數(shù)據(jù))、凈化(消除冗余數(shù)據(jù))、轉(zhuǎn)換、歸約等。數(shù)據(jù)預(yù)處理工作準(zhǔn)備是否充足，對(duì)于挖掘算法效率乃至正確性都有關(guān)鍵性影響。該公司通過(guò)數(shù)年電腦化管理，已有大量客戶個(gè)人基本信息(文中簡(jiǎn)稱(chēng)為客戶信息表)。在客戶信息表中，有很多屬性，如姓名顧客號(hào)碼、顧客標(biāo)識(shí)、顧客身份證號(hào)碼(轉(zhuǎn)化為年紀(jì))、在網(wǎng)時(shí)間（完工時(shí)間）、地址、職業(yè)、顧客類(lèi)別、客戶流失（顧客狀態(tài)）等等，數(shù)據(jù)準(zhǔn)備時(shí)必須除掉表中某些無(wú)須要屬性，一般可采取面向?qū)傩詺w納等辦法去掉不有關(guān)或弱有關(guān)屬性。第27頁(yè)第6章決策樹(shù)決策樹(shù)算法ID3算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（3）屬性刪除：將有大量不一樣取值且無(wú)概化操作符屬性或者可用其它屬性來(lái)替代它較高層概念那些屬性刪除。例如客戶信息表中顧客標(biāo)識(shí)、身份證號(hào)碼等，它們?nèi)≈堤嗲覠o(wú)法在該取值域內(nèi)找到概化操作符，應(yīng)將其刪除，得到表1。

表1客戶信息表年紀(jì)學(xué)歷職業(yè)繳費(fèi)方式在網(wǎng)時(shí)長(zhǎng)費(fèi)用變化率客戶流失58大學(xué)公務(wù)員托收1310%NO47高中工人營(yíng)業(yè)廳繳費(fèi)942%NO26碩士公務(wù)員充值卡263%YES28大學(xué)公務(wù)員營(yíng)業(yè)廳繳費(fèi)52.91%NO32初中工人營(yíng)業(yè)廳繳費(fèi)32.3%NO42高中無(wú)業(yè)人員充值卡2100%YES68初中無(wú)業(yè)人員營(yíng)業(yè)廳繳費(fèi)92.3%NO第28頁(yè)第6章決策樹(shù)決策樹(shù)算法ID3算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（4）屬性概化：用屬性概化閾值控制技術(shù)沿屬性概念分層上卷或下鉆進(jìn)行概化。文化程度分為3類(lèi)：W1初中下列(含初中)，W2高中(含中專(zhuān))，W3大學(xué)(專(zhuān)科、本科及以上)；職業(yè)類(lèi)別：按工作性質(zhì)來(lái)分共分3類(lèi)：Z1一Z3；繳費(fèi)方式：托收：T1,營(yíng)業(yè)廳繳費(fèi)：T2,充值卡：T3。連續(xù)型屬性概化為區(qū)間值：表中年紀(jì)、費(fèi)用變化率和在網(wǎng)時(shí)間為連續(xù)型數(shù)據(jù)，由于建立決策樹(shù)時(shí)，用離散型數(shù)據(jù)進(jìn)行處理速度最快，因此對(duì)連續(xù)型數(shù)據(jù)進(jìn)行離散化處理，根據(jù)專(zhuān)家經(jīng)驗(yàn)和實(shí)際計(jì)算信息增益，在“在網(wǎng)時(shí)長(zhǎng)”屬性中，通過(guò)檢測(cè)每個(gè)劃分，得到在閾值為5年時(shí)信息增益最大，從而確定最佳劃分是在5年處，則這個(gè)屬性范圍就變?yōu)椋?lt;=5,>5：H1,H2｝。而在“年紀(jì)”屬性中，信息增益有兩個(gè)鋒值，分別在40和50處，因而該屬性范圍變?yōu)閧<=40,>40-<=50,>50}即變?yōu)閧青年，中年，老年：N1,N2,N3}；費(fèi)用變化率：指（（當(dāng)月話費(fèi)－近3個(gè)月平均話費(fèi)）/近3個(gè)月平均話費(fèi)）×％>0，F(xiàn)1:<＝30%，F(xiàn)2：30%-99%,F3:＝100%變?yōu)椋鸉1,F2,F3｝。

第29頁(yè)表2轉(zhuǎn)化后客戶信息表年紀(jì)學(xué)歷職業(yè)繳費(fèi)方式開(kāi)戶時(shí)間費(fèi)用變化率客戶流失N3W3Z1T1H2F1NON2W2Z2T2H2F2NON1W3Z1T3H1F2YESN1W3Z1T2H1F1NON1W1Z2T2H1F1NON2W2Z3T3H1F3YESN3W1Z3T1H2F1NO第6章決策樹(shù)決策樹(shù)算法ID3算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（5）第30頁(yè)YESNO年齡職業(yè)YES繳費(fèi)方式Y(jié)ESYESNOYSESNONO在網(wǎng)時(shí)長(zhǎng)NOF1F2F3N1N2N3T1T2T3Z1Z2Z3H1H2費(fèi)用變化率第6章決策樹(shù)決策樹(shù)算法ID3算法實(shí)際應(yīng)用-在電信行業(yè)應(yīng)用實(shí)例（6）在圖中，NO表達(dá)客戶不流失，YES表達(dá)客戶流失。從圖能夠看出，客戶費(fèi)用變化率為100%客戶肯定已經(jīng)流失；而費(fèi)用變化率低于30%客戶；即每個(gè)月資費(fèi)相對(duì)穩(wěn)定客戶一般不會(huì)流失，費(fèi)用變化率在30%～99%客戶有也許流失，其中年紀(jì)在40～50歲之間客戶流失也許性非常大，而年紀(jì)低于40歲客戶，用充值卡繳費(fèi)客戶和在網(wǎng)時(shí)間較短客戶容易流失；年紀(jì)較大客戶，則工人容易流失。第31頁(yè)主要內(nèi)容決策樹(shù)基本概念決策樹(shù)算法決策樹(shù)研究問(wèn)題主要參照文獻(xiàn)第32頁(yè)第6章決策樹(shù)決策樹(shù)研究問(wèn)題抱負(fù)決策樹(shù)有三種：(1)葉子結(jié)點(diǎn)數(shù)最少；(2)葉子結(jié)點(diǎn)深度最??；(3)葉子結(jié)點(diǎn)數(shù)最少且葉子結(jié)點(diǎn)深度最小。

然而，洪家榮等人已經(jīng)證明了要找到這種最優(yōu)決策樹(shù)是NP難題。因此，決策樹(shù)優(yōu)化目標(biāo)就是要找到盡也許趨向于最優(yōu)決策樹(shù)。第33頁(yè)第6章決策樹(shù)有關(guān)過(guò)渡擬合上述決策樹(shù)算法增加樹(shù)每一種分支深度，直到正好能對(duì)訓(xùn)練樣例比較完美地分類(lèi)。實(shí)際應(yīng)用中，當(dāng)數(shù)據(jù)中有噪聲或訓(xùn)練樣例數(shù)量太少以至于不能產(chǎn)生目標(biāo)函數(shù)有代表性采樣時(shí)，該策略也許會(huì)遇到困難。在以上情況發(fā)生時(shí)，這個(gè)簡(jiǎn)單算法產(chǎn)生樹(shù)會(huì)過(guò)渡擬合訓(xùn)練樣例（過(guò)渡擬合：OverFitting）.決策樹(shù)研究問(wèn)題第34頁(yè)有關(guān)過(guò)渡擬合第6章決策樹(shù)對(duì)于一種假設(shè)，當(dāng)存在其他假設(shè)對(duì)訓(xùn)練樣例擬合比它差，但事實(shí)上在實(shí)例整個(gè)分布上（包括訓(xùn)練集合以外實(shí)例）體現(xiàn)得卻更加好時(shí)，則稱(chēng)該假設(shè)過(guò)度擬合訓(xùn)練樣例。過(guò)度擬合：給定一種假設(shè)空間H，一種假設(shè)h∈H，假如存在其它假設(shè)h1∈H,使得在訓(xùn)練樣例上h錯(cuò)誤率比h1小，但在整個(gè)實(shí)例公布上h1錯(cuò)誤率比h小，則稱(chēng)假設(shè)h過(guò)度擬合訓(xùn)練數(shù)據(jù)過(guò)度擬合產(chǎn)生原因：噪聲，訓(xùn)練樣例太小等決策樹(shù)研究問(wèn)題第35頁(yè)有關(guān)過(guò)渡擬合第6章決策樹(shù)對(duì)學(xué)習(xí)算法是否成功真正測(cè)試是看它對(duì)于訓(xùn)練中未見(jiàn)到數(shù)據(jù)執(zhí)行性能。訓(xùn)練過(guò)程應(yīng)當(dāng)包括訓(xùn)練樣本和驗(yàn)證樣本。驗(yàn)證樣本用于測(cè)試訓(xùn)練后性能。假如驗(yàn)證成果差，則需要考慮采取不一樣構(gòu)造重新進(jìn)行訓(xùn)練，例如使用更大樣本集，或者變化從連續(xù)值到離散值得數(shù)據(jù)轉(zhuǎn)換等。一般應(yīng)當(dāng)建立一種驗(yàn)證過(guò)程，在訓(xùn)練最后完成后用來(lái)檢測(cè)訓(xùn)練成果泛化能力。決策樹(shù)研究問(wèn)題第36頁(yè)有關(guān)過(guò)渡擬合第6章決策樹(shù)分類(lèi)模型誤差一般能夠?qū)⒎诸?lèi)模型誤差分為：

1、訓(xùn)練誤差（TrainingError）；2、泛化誤差（GeneralizationError）決策樹(shù)研究問(wèn)題第37頁(yè)有關(guān)過(guò)渡擬合第6章決策樹(shù)分類(lèi)模型誤差訓(xùn)練誤差是在訓(xùn)練統(tǒng)計(jì)上誤分類(lèi)樣本百分比；泛化誤差是模型在未知統(tǒng)計(jì)上盼望誤差；一種好模型不但要能夠較好地?cái)M合訓(xùn)練數(shù)據(jù)，并且對(duì)未知樣本也要能夠精確地分類(lèi)。一種好分類(lèi)模型必須具有低訓(xùn)練誤差和泛化誤差。由于一種具有低訓(xùn)練誤差模型，其泛化誤差也許比具有較高訓(xùn)練誤差模型高。（訓(xùn)練誤差低，泛化誤差高，稱(chēng)為過(guò)渡擬合）決策樹(shù)研究問(wèn)題第38頁(yè)有關(guān)過(guò)渡擬合第6章決策樹(shù)模型過(guò)渡擬合潛在原因（1）噪聲造成過(guò)渡擬合；

錯(cuò)誤類(lèi)別值/類(lèi)標(biāo)簽，屬性值等（2）缺乏代表性樣本所造成過(guò)渡擬合

根據(jù)少許訓(xùn)練統(tǒng)計(jì)作出分類(lèi)決策模型容易受過(guò)渡擬合影響。由于訓(xùn)練樣本缺乏代表性樣本，在沒(méi)有多少訓(xùn)練統(tǒng)計(jì)情況下，學(xué)習(xí)算法仍然繼續(xù)細(xì)化模型就會(huì)造成過(guò)渡擬合。決策樹(shù)研究問(wèn)題第39頁(yè)有關(guān)過(guò)渡擬合第6章決策樹(shù)模型過(guò)渡擬合潛在原因名稱(chēng)體溫胎生4條腿冬眠哺乳動(dòng)物蠑螈冷血NYYN虹鳉冷血YNNN鷹恒溫NNNN弱夜鷹恒溫NNYN鴨嘴獸恒溫YYYY哺乳動(dòng)物分類(lèi)訓(xùn)練樣例體溫恒溫冷血冬眠NYNN4條腿YNNY名稱(chēng)體溫胎生4條腿冬眠哺乳動(dòng)物人恒溫YNNY大象恒溫YYNY鴿子恒溫NNNN哺乳動(dòng)物分類(lèi)訓(xùn)練樣例按照訓(xùn)練模型。人和大象都不是哺乳動(dòng)物。決策樹(shù)作出這樣判斷是由于只有一種訓(xùn)練樣例具有這些特點(diǎn)（鷹，恒溫，不冬眠）被劃分為非哺乳動(dòng)物。該例清楚表白，當(dāng)決策樹(shù)葉節(jié)點(diǎn)沒(méi)有足夠代表性時(shí)，也許會(huì)預(yù)測(cè)錯(cuò)誤。決策樹(shù)研究問(wèn)題第40頁(yè)有關(guān)過(guò)渡擬合第6章決策樹(shù)處理過(guò)度擬合伎倆：1及早停頓樹(shù)增加；2后修剪法。決策樹(shù)研究問(wèn)題第41頁(yè)有關(guān)過(guò)渡擬合第6章決策樹(shù)1及早停頓樹(shù)增加

由于決策樹(shù)學(xué)習(xí)要從候選集合眾選擇滿足給定標(biāo)準(zhǔn)最大化屬性，并且不回溯，也就是我們常說(shuō)爬山策略，其選擇往往會(huì)是局部最優(yōu)而不是全局最優(yōu)。樹(shù)構(gòu)造越復(fù)雜，則過(guò)渡擬合發(fā)生也許性越大。因此，要選擇簡(jiǎn)單模型。Occan法則（又稱(chēng)Occan剃刀OccanRazor）:具有相同泛化誤差兩個(gè)模型，較簡(jiǎn)單模型比復(fù)雜模型更可取。決策樹(shù)研究問(wèn)題第42頁(yè)有關(guān)過(guò)渡擬合第6章決策樹(shù)后修剪法（后剪枝法）

在訓(xùn)練過(guò)程中允許對(duì)數(shù)據(jù)過(guò)渡擬合，然后再對(duì)樹(shù)進(jìn)行修剪該辦法稱(chēng)為后剪枝法。決策樹(shù)研究問(wèn)題第43頁(yè)有關(guān)過(guò)渡擬合第6章決策樹(shù)后修剪法（后剪枝法）例AB負(fù)C正正負(fù)YYYNNN一棵通過(guò)訓(xùn)練集合學(xué)好決策樹(shù)決策樹(shù)研究問(wèn)題第44頁(yè)有關(guān)過(guò)渡擬合第6章決策樹(shù)后修剪法（后剪枝法）例AB負(fù)C正正負(fù)YYYNNN實(shí)例ABC類(lèi)別錯(cuò)分類(lèi)1YYY+2YYY+3YYY+4YYY+5YYY+6YYN-*7YYN-*8YYN-*9YNY+10YNY+11YNY+12YNY+13YNN+*14YNN+*15YNN-16YNN-17YNN-18NNN-19NYN-20NYY-對(duì)以上決策樹(shù)通過(guò)右側(cè)驗(yàn)證集合進(jìn)行測(cè)試，發(fā)覺(jué)其有5個(gè)錯(cuò)分類(lèi)。決策樹(shù)研究問(wèn)題第45頁(yè)有關(guān)過(guò)渡擬合第6章決策樹(shù)后修剪法（后剪枝法）例AB負(fù)C正正負(fù)YYYNNN{18，19，20}{1，2，3，45，6，7，8}{9，10，11，12}{13，14，15，16，17}錯(cuò)分類(lèi)5個(gè)，6，7，8，13，14決策樹(shù)研究問(wèn)題第46頁(yè)有關(guān)過(guò)渡擬合第6章決策樹(shù)后修剪法（后剪枝法）例第1步將決策樹(shù)規(guī)則化規(guī)則1IFA=YANDB=YTHEN+規(guī)則2IFA=YANDB=NANDC=YTHEN+規(guī)則3IFA=YANDB=NANDC=NTHEN–規(guī)則4IFA=NTHEN-

AB負(fù)C正正負(fù)YYYNNN決策樹(shù)研究問(wèn)題第47頁(yè)有關(guān)過(guò)渡擬合第6章決策樹(shù)后修剪法（后剪枝法）例規(guī)則1IFA=YANDB=YTHEN+規(guī)則2IFA=YANDB=NANDC=YTHEN+規(guī)則3IFA=YANDB=NANDC=NTHEN–規(guī)則4IFA=NTHEN-

規(guī)則分類(lèi)正確數(shù)目分類(lèi)錯(cuò)誤數(shù)目精度1535/82404/43323/54303/3第2步規(guī)則精度計(jì)算決策樹(shù)研究問(wèn)題第48頁(yè)規(guī)則2與規(guī)則4精度為100%，保存有關(guān)過(guò)渡擬合第6章決策樹(shù)后修剪法（后剪枝法）例規(guī)則分類(lèi)正確數(shù)目分類(lèi)錯(cuò)誤數(shù)目精度1535/82404/43323/54303