決策樹(shù)算法分析(編輯修改稿)
2024-07-23 10:13 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 象越來(lái)越突出，這也是決策樹(shù)技術(shù)面臨的困難問(wèn)題。(3)決策樹(shù)方法的遞增性。數(shù)據(jù)挖掘出來(lái)的知識(shí)，只是相對(duì)于某一時(shí)間的某些數(shù)據(jù)，新的數(shù)據(jù)可能使發(fā)現(xiàn)的新知識(shí)與原來(lái)的知識(shí)沖突。因此，設(shè)計(jì)具有遞增性決策樹(shù)挖掘方法，也是實(shí)用化的基本要求之一。第三章 決策樹(shù)算法 CLS算法CLS算法是早期的決策樹(shù)學(xué)習(xí)算法，是許多決策樹(shù)學(xué)習(xí)算法的基礎(chǔ)。CLS基本思想：從一棵空決策樹(shù)開(kāi)始，選擇某一屬性作為測(cè)試屬性。該測(cè)試屬性對(duì)應(yīng)決策樹(shù)中的決策結(jié)點(diǎn)。根據(jù)該屬性的值的不同，可將訓(xùn)練樣本分成相應(yīng)的子集，如果該子集為空，或該子集中的樣本屬于同一個(gè)類，則該子集為葉結(jié)點(diǎn)，否則該子集對(duì)應(yīng)于決策樹(shù)的內(nèi)部結(jié)點(diǎn)，即測(cè)試結(jié)點(diǎn)，需要選擇一個(gè)新的分類屬性對(duì)該子集進(jìn)行劃分，直到所有的子集都為空或者屬于同一類。例1：、頭發(fā)顏色與所屬人種之間的關(guān)系：人員眼睛顏色頭發(fā)顏色所屬人種1黑色黑色黃種人2藍(lán)色金色白種人3灰色金色白種人4藍(lán)色紅色白種人5灰色紅色白種人6黑色金色混血7灰色黑色混血8藍(lán)色黑色混血，選擇“眼睛顏色”為測(cè)試屬性。眼睛顏色[1,6][2,4,8][3,5,7]黑色藍(lán)色灰色根據(jù)“眼睛顏色”所劃分的子集中的樣本不屬于同一類，所以選擇新的測(cè)試屬性“頭發(fā)顏色”對(duì)各個(gè)子集進(jìn)行劃分，所得的樣本屬于同一類，決策樹(shù)構(gòu)建完成。眼睛顏色頭發(fā)顏色頭發(fā)顏色頭發(fā)顏色黑色藍(lán)色灰色白種人[4]白種人[2]混血[7]白種人[6]黃種人[1]混血[8]白種人[5]白種人[3]黑色金色金色紅色黑色金色紅色黑色 決策樹(shù) ID3算法ID3算法是決策樹(shù)學(xué)習(xí)算法中最具有影響和最為典型的算法，它的基本思想是，利用信息熵原理，選擇信息增益最大的屬性作為分類屬性。 信息量大小的度量Shannon1948年提出的信息論理論。事件ai的信息量I(ai)可如下度量：，其中p(ai)表示事件ai發(fā)生的概率。假設(shè)有n個(gè)互不相容的事件a1,a2,a3,……，an，它們中有且僅有一個(gè)發(fā)生，則其平均的信息量可如下度量：= ，在決策樹(shù)分類中，假設(shè)S是訓(xùn)練樣本集合，|S|是訓(xùn)練樣本數(shù)，樣本劃分為n個(gè)不同的類C1，C2，……Cn，這些類的大小分別標(biāo)記為|C1|，|C2|，……，|Cn|。則任意樣本S屬于類Ci的概率為：。假設(shè)屬性A的所有不同值的集合為XA，Sv是S中屬性A的值為v的樣本子集，在選擇屬性A后的每一個(gè)分支節(jié)點(diǎn)上，對(duì)該節(jié)點(diǎn)的樣本集Sv分類的熵為E(Sv)。選擇A導(dǎo)致的期望熵定義為每個(gè)子集Sv的熵的加權(quán)和，權(quán)值為屬于Sv的樣本占原始樣本S的比例,即期望熵為：,屬性A相對(duì)樣本集合S的信息增益Gain(S，A)定義為：，其中Gain(S，A)是指因知道屬性A的值后導(dǎo)致的熵的期望壓縮。Gain(S，A)越大，說(shuō)明選擇測(cè)試屬性A對(duì)分類提供的信息越多。ID3算法就是將每個(gè)節(jié)點(diǎn)選擇信息增益Gain(S，A)最大的屬性作為測(cè)試屬性。 ID3決策樹(shù)應(yīng)用舉例例2：，對(duì)于任意給定的客人，能否幫助公司將這位客人歸類。 誰(shuí)在買(mǎi)計(jì)算機(jī)計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買(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中中
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1