1、按性別和種族申請這所學(xué)校的原因，例2:沃爾瑪?shù)匿N售和供應(yīng)商關(guān)心哪些產(chǎn)品賣得好，第二章決策樹(ID3分類算法)，產(chǎn)品名稱，產(chǎn)品型號，產(chǎn)品價格，銷售地點和日期，例1:首先，提出分類問題。為了解決上述問題，分類是數(shù)據(jù)挖掘中的一種主要分析方法。分類的任務(wù)是學(xué)習(xí)數(shù)據(jù)集，構(gòu)造具有預(yù)測功能的分類模型，用于預(yù)測未知樣本的類別標(biāo)簽。例如，根據(jù)瓦斯?fàn)顩r、開采技術(shù)條件、煤層賦存狀況等。對危害進(jìn)行分類和評估，根據(jù)核磁共振的結(jié)果區(qū)分腫瘤是惡性還是良性，根據(jù)星系的形狀進(jìn)行分類，將交易分類為合法或欺詐，將新聞分類為金融、天氣、娛樂和體育等。主要分類方法決策樹分類方法貝葉斯分類方法K-最近鄰分類方法神經(jīng)網(wǎng)絡(luò)分類方法支持向量機(jī)

2、組合學(xué)習(xí)方法評價回歸方法不平衡數(shù)據(jù)分類問題分類模型，舉例說明分類任務(wù)，測試來自樹根的數(shù)據(jù)。從樹根學(xué)習(xí)算法。訓(xùn)練數(shù)據(jù)，模型：決策樹，決策樹示例，婚姻狀況，住房，年收入，是，否，否，是，否，已婚，單身，離婚，80K，80K，決策樹示例，歸納，推理，從根測試數(shù)據(jù)，如何在適當(dāng)?shù)奈恢帽M管任何屬性都可以用來劃分?jǐn)?shù)據(jù)集，但是最終的決策樹將會非常不同。有必要找到一種合適的方法來選擇屬性。屬性選擇是決策樹算法中的一個重要步驟。常見的屬性選擇標(biāo)準(zhǔn)包括信息增益和基尼系數(shù)。信息增益是決策樹中常見的分支準(zhǔn)則。具有最高信息增益的屬性被選為樹的每個節(jié)點處的當(dāng)前節(jié)點的分區(qū)屬性?；嵯禂?shù)是一種不純函數(shù)，用于衡量數(shù)據(jù)集中數(shù)據(jù)相對

3、于類別的純度。1.ID3分類算法：由昆蘭在1986年提出，它使用信息增益作為屬性的選擇標(biāo)準(zhǔn)。首先檢測所有屬性，選擇信息增益最大的屬性生成決策樹節(jié)點，并根據(jù)屬性值的不同建立分支。然后，對每個分支的子集遞歸調(diào)用該方法，以建立決策樹節(jié)點的分支，直到所有子集僅包含相同類別的數(shù)據(jù)。最后，得到?jīng)Q策樹，該決策樹可用于對新樣本進(jìn)行分類。2.與2相關(guān)的基本概念。ID3分類算法：1)信息熵2)信息增益，熵用來衡量一個屬性的信息量。假設(shè)s是一個訓(xùn)練集，s的目標(biāo)屬性C有m個可能的類標(biāo)簽值，C=C1，C2，Cm。假設(shè)訓(xùn)練集s中所有樣本的Ci頻率為(i=1，2，3，m)，則訓(xùn)練集s中包含的信息熵定義為：熵越小表示樣本對目

4、標(biāo)屬性的分布越純，而熵越大表示樣本對目標(biāo)屬性的分布越多。，信息熵示例演示考慮數(shù)據(jù)集天氣如下，找到數(shù)據(jù)集天氣的熵關(guān)于目標(biāo)屬性打球。目標(biāo)屬性，答案：讓天氣數(shù)據(jù)集為s，其中有14個樣本，目標(biāo)屬性play ball有兩個值C1=是，C2=否C2=否.14個樣本的分布如下：9個樣本的類別標(biāo)簽為是，5個樣本的類別標(biāo)簽為否，C1=是出現(xiàn)在所有樣本S中的概率為9/14，C2=否出現(xiàn)在所有樣本S中的概率為5/14。因此，數(shù)據(jù)集的熵為：信息增益為樣本數(shù)據(jù)集劃分前后的不純凈度(熵)之差。假設(shè)劃分前的樣本數(shù)據(jù)集為S，樣本集為S除以屬性A，S除以屬性A的信息增益增益(S，A)為樣本集S的熵減去S除以屬性A后樣本子集的熵

5、。S除以屬性A后樣本子集的熵定義如下：假設(shè)屬性A有k個不同的值，S被劃分為k個樣本子集，S2 S1， SK，則根據(jù)屬性a劃分為S的樣本子集的信息熵為：其中|Si|(i，=1，2，k)是樣本子集Si中包含的樣本數(shù)，而|S|是樣本集S中包含的樣本數(shù).信息增益越大，屬性A劃分的樣本子集越純，越有利于分類。以天氣數(shù)據(jù)集為例，假設(shè)數(shù)據(jù)集為S，假設(shè)S除以屬性風(fēng)，求出S對屬性風(fēng)的信息增益。解決方法：(1)首先，根據(jù)前面的例子計算出數(shù)據(jù)集s的熵值為0.94；(2)屬性風(fēng)有弱、強(qiáng)兩個可能值，將S分為兩個子集：S1、S2、S1是風(fēng)屬性值弱的樣本子集，共8個樣本；S2是大風(fēng)屬性樣本的子集，共有6個樣本；樣本子集S1

6、和S2的熵分別計算如下。對于樣本子集S1，有6個樣本玩球=是，2個樣本玩球=否，那么：對于樣本子集S2，有3個樣本玩球=是，3個樣本玩球=否，那么：S除以屬性風(fēng)后的熵為：數(shù)據(jù)集S除以屬性風(fēng)得到的信息增益值為：以天氣數(shù)據(jù)集為例。數(shù)據(jù)集有屬性：展望，溫度，濕度，風(fēng)。展望=晴天，陰天，雨溫度=熱，溫和，涼爽濕度=高，正常風(fēng)=弱。首先，計算所有屬性的總數(shù)據(jù)集的信息增益，并找到根節(jié)點的最佳分割屬性：gain (s，展望)=0.246gain (s，溫度)=0.029gain (s，濕度)=0.152gain (s)。Wind)=0.049很明顯，這里的outlook屬性具有最高的信息增益值，所以選擇它作

7、為根節(jié)點。將outlook作為根節(jié)點，并繼續(xù)下去：想法是用outlook的可能值構(gòu)建分支，并遞歸地為每個分支構(gòu)建子樹。因為outlook有三個可能的值，所以為根節(jié)點建立了三個分支“晴天”、“陰天”和“雨天”。那么，哪一個屬性被用來最好地劃分根節(jié)點的陽光分支？陰樹枝？雨樹枝？首先，為outlook的陽光樹枝創(chuàng)建一個子樹。在數(shù)據(jù)集中找出樣本子集S前景=晴天，然后依次計算樣本子集S的信息增益除以剩余的三個屬性：Gain (S陽光，濕度)=0.971 Gain (S陽光，溫度)=0.571gain(陽光，風(fēng))=0.371，顯然濕度具有最高的信息增益值，因此選擇它作為前景節(jié)點的晴天分支下的決策節(jié)點。用同

8、樣的方法，依次建立前景的陰枝和雨枝的子樹，最終得到一棵能夠預(yù)測未知類別標(biāo)簽樣本的決策樹。ID3決策樹預(yù)測未知樣本以下決策樹用于預(yù)測帶有未知類別標(biāo)簽的樣本X:X=雨、熱、正常、弱、ID3算法概述ID3算法是一種在所有可能的決策樹空間中自頂向下的貪婪搜索方法。ID3搜索的假設(shè)空間是一組可能的決策樹。搜索的目的是構(gòu)建一個與訓(xùn)練數(shù)據(jù)一致的決策樹。搜索策略是爬山法。決策樹由簡單到復(fù)雜構(gòu)建，信息熵作為爬山法的評價函數(shù)。ID3算法的核心是選擇決策樹中各級節(jié)點的屬性，并以信息增益作為屬性選擇的標(biāo)準(zhǔn)，這樣在測試每一個非葉節(jié)點時，可以得到關(guān)于被測數(shù)據(jù)的最大類別信息，并且在屬性將數(shù)據(jù)集劃分為子集后，系統(tǒng)的熵值最小。

9、優(yōu)點：理論清晰，方法簡單，學(xué)習(xí)能力強(qiáng)。缺點：(1)該算法只能處理分類屬性數(shù)據(jù)，不能處理連續(xù)數(shù)據(jù)；(2)該算法為測試屬性的每個值生成一個分支，并劃分相應(yīng)的數(shù)據(jù)樣本集，這將導(dǎo)致許多小的子集。隨著子集被劃分得越來越小，由于子集的小尺寸導(dǎo)致的統(tǒng)計特性不足，劃分過程將停止；(3)在3)ID3算法中，信息增益被用作選擇決策樹節(jié)點屬性的標(biāo)準(zhǔn)。由于類別值較多的屬性的信息增益計算結(jié)果大于類別值較少的屬性的信息增益計算結(jié)果，這將導(dǎo)致決策樹算法傾向于選擇具有較多分支的屬性，這可能導(dǎo)致過度擬合。在極端情況下，如果一個屬性對于訓(xùn)練集中的每個元組都有唯一的值，那么它被認(rèn)為是最好的，因為每個分區(qū)只有一個元組(因此它也是一個

10、類)。優(yōu)點：理論清晰，方法簡單，學(xué)習(xí)能力強(qiáng)。缺點：(1)該算法只能處理分類屬性數(shù)據(jù)，不能處理連續(xù)數(shù)據(jù)；(2)該算法為測試屬性的每個值生成一個分支，并劃分相應(yīng)的數(shù)據(jù)樣本集，這將導(dǎo)致許多小的子集。隨著子集被劃分得越來越小，由于子集的小尺寸導(dǎo)致的統(tǒng)計特性不足，劃分過程將停止；(3)在3)ID3算法中，信息增益被用作選擇決策樹節(jié)點屬性的標(biāo)準(zhǔn)。由于類別值較多的屬性的信息增益計算結(jié)果大于類別值較少的屬性的信息增益計算結(jié)果，這將導(dǎo)致決策樹算法傾向于選擇具有較多分支的屬性，這可能導(dǎo)致過度擬合。在極端情況下，如果一個屬性對于訓(xùn)練集中的每個元組都有唯一的值，那么它被認(rèn)為是最好的，因為每個分區(qū)只有一個元組(因此它也是一個類)。C4.5是基于ID3算法的缺點。昆蘭在1993年對其進(jìn)行了改進(jìn)，提出了改進(jìn)的決策樹分類算法c4.5。該算法繼承了ID3算法的優(yōu)點，并在以下幾個方