數(shù)據(jù)挖掘大作業(yè)

1、深圳大學(xué)研究生課程論文 題目 數(shù)據(jù)挖掘作業(yè) 成績(jī) 專(zhuān)業(yè) 軟件工程 課程名稱(chēng)、代碼 161023050015 年級(jí) 2015 級(jí) 姓名 文 成 學(xué) 號(hào) 2150230509 時(shí)間 2015 年 12 月 任課教師 黃哲學(xué) 、王熙照 一、期末課程試題 針對(duì)一個(gè)離散屬性二分類(lèi)問(wèn)題，表 1 給出了包含 15 個(gè)樣本的訓(xùn)練集，其輸 入特征為 A1，A2，A3，A4，A5，類(lèi)標(biāo)簽為1,2。表 2 給出了包含 2 個(gè)測(cè)試樣 本的測(cè)試集，其分類(lèi)未知。請(qǐng)回答下述問(wèn)題： 表 1. 訓(xùn)練樣本 A3 A4 2 2 2 2 2 1 2 2 1 2 2 1 2 2 1 1 2 2 2 1 2 2 2 1 2 1 1 2

2、2 1 表 2. 測(cè)試樣本 A3 A4 1 1 1 2 Samples 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A1 1 2 1 2 1 2 1 2 1 1 1 2 2 1 2 A2 3 1 3 1 3 1 2 1 2 3 1 2 3 2 3 A5 2 1 1 3 2 1 2 1 3 3 3 1 1 2 3 Class 2 2 1 1 2 1 2 1 2 2 1 1 1 2 1 Smaples 1 2 A1 2 1 A2 2 1 A5 1 1 Class ? ? 問(wèn)題 1. 基于表 1 中給出的訓(xùn)練集，給出分別使用極小熵和極大熵選擇擴(kuò)展屬性 所生成的兩棵決策樹(shù)。

3、然后給出你對(duì)樹(shù)的大小的理解，并比較兩種方法生成的決 策樹(shù)那個(gè)小，那個(gè)大。 問(wèn)題 2. 分別將兩個(gè)決策樹(shù)轉(zhuǎn)換成兩組 IF-THEN 規(guī)則。 問(wèn)題 3.分別給出此兩組規(guī)則對(duì)表 2 給出的兩個(gè)測(cè)試樣本的預(yù)測(cè)類(lèi)別。 問(wèn)題 4. 那組結(jié)果你認(rèn)為更可信？闡述你的理由。 問(wèn)題 5. 利用極小熵生成的決策樹(shù)是否是“最小決策樹(shù)”？給出你的證明或反例 問(wèn)題 6. 如果第一個(gè)屬性 A1 為數(shù)值屬性，其取值為 0,1區(qū)間的實(shí)數(shù)，如表 3、 表 4 所示。 此時(shí)如何處理？進(jìn)一步請(qǐng)按你的方法基于表 3 給出的訓(xùn)練集產(chǎn)生一棵 決策樹(shù)（用極小熵選擇擴(kuò)展屬性），并給出表 4 中的測(cè)試樣本的預(yù)測(cè)類(lèi)別。 表 3. 訓(xùn)練樣本 A3

4、A4 2 2 2 2 2 1 2 2 1 2 2 1 2 2 1 1 2 2 2 1 2 2 2 1 2 1 1 2 2 1 表 4. 測(cè)試樣本 A3 A4 1 1 1 2 Samples 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A1 0.60 0.90 0.35 0.15 0.50 0.95 0.20 0.12 0.68 0.95 0.05 0.02 0.08 0.45 0.14 A2 3 1 3 1 3 1 2 1 2 3 1 2 3 2 3 A5 2 1 1 3 2 1 2 1 3 3 3 1 1 2 3 Class 2 2 1 1 2 1 2 1 2 2

5、 1 1 1 2 1 Smaples 1 2 A1 0.10 0.98 A2 2 1 A5 1 1 Class ? ? 二、解答 問(wèn)題 1 基于表 1 中給出的訓(xùn)練集， 給出分別使用極小熵和極大熵選擇擴(kuò)展屬性所 生成的兩棵決策樹(shù)。然后給出你對(duì)樹(shù)的大小的理解，并比較兩種方法生成的決策 樹(shù)那個(gè)小，那個(gè)大。 答 幾個(gè)概念和求熵的方法： 熵是數(shù)據(jù)中的不確定性、突發(fā)性或隨機(jī)性的程度的度量。 決策樹(shù)是一個(gè)樹(shù)結(jié)構(gòu)。其每個(gè)非葉節(jié)點(diǎn)表示一個(gè)特征屬性上的測(cè)試，每個(gè)分 支代表這個(gè)特征屬性在某個(gè)值域上的輸出，而每個(gè)葉節(jié)點(diǎn)存放一個(gè)類(lèi)別。 設(shè)數(shù)據(jù)集為 D， 類(lèi)標(biāo)號(hào)屬性”Class”有兩個(gè)屬性： 1 和 2,因此有不同的兩

6、類(lèi)， 令 C1 對(duì)應(yīng)“1”，C2 對(duì)應(yīng)“2”，那么 C1 有 8 個(gè)樣本，C2 有 7 個(gè)樣本，所以數(shù) 據(jù)集 D 的熵為： 下面分別計(jì)算按各個(gè)屬性分裂后所得的諸子集的熵。 1.若以“A1”作為分裂屬值，則產(chǎn)生兩個(gè)子集(因?yàn)樵搶傩杂袃蓚€(gè)不同的取值， 所以 D 按照屬性“A1”劃分的 2 個(gè)子集的熵的加權(quán)和為 0.4327+0.2139=0.6466 2.如果用“A2”為分裂屬性 類(lèi)似的：如果用“A2”為分裂屬性 0.2406+0.2163+0.4=0.8569 3.如果用“A3”為分裂屬性 0.1057+0.7839=0.8896 4.如果用“A4”為分裂屬性 0.4339+0.4652=0.8

7、991 5.如果用“A5”為分裂屬性 0.2600+0+0.3237= 0.5837 根據(jù)以上結(jié)果得到使用極小熵生成的決策樹(shù)： 那么用 A5 作為分裂屬性，所得信息增益最大。 15 個(gè)訓(xùn)練集 A5=1 A5=2 A5=3 6 A4=1 A4=2 4 Class2 A2=1 A2=2 5 A2=3 5 Class1 1 Class2 2 Class1 1 A1=1 Class2 2 A1=2 1 Class2 1 Class1 使用極大熵生成的決策樹(shù)： 那么用 A4 作為分裂屬性，所得信息增益最小 15 個(gè)訓(xùn)練集 A4=1 A4=2 7 A1=1 A3=1 A1=2 8 A3=2 2 A5=3

8、A5=1 5 Class1 2 A2=1 Class2 A2=2 6 A2=3 1 Class1 1 Class2 A1=1 3 A1=2 2 Class2 1 Class2 1 Class1 A5=1 2 A5=3 1 Class2 1 Class1 從信息論知識(shí)中我們知道，期望信息越小，信息增益越大，從而純度越高。 構(gòu)造決策樹(shù)的核心思想就是以信息增益度量屬性選擇， 選擇分裂后信息增益最大 的屬性進(jìn)行分裂。所以樹(shù)的大小跟期望信息和信息增益有關(guān)。另一方面，構(gòu)造決 策樹(shù)的關(guān)鍵步驟是分裂屬性。分裂次數(shù)越多，樹(shù)深度會(huì)變大，從而樹(shù)就會(huì)更大。 所以極大熵生成的決策樹(shù)明顯要比極小熵生成的決策樹(shù)要高， 樹(shù)枝

9、也比極小熵生 成的決策樹(shù)要多，但生成過(guò)程也更繁瑣。 問(wèn)題 2. 分別將兩個(gè)決策樹(shù)轉(zhuǎn)換成兩組 IF-THEN 規(guī)則 答 使用極小熵生成的決策樹(shù)轉(zhuǎn)換成IF-THEN 規(guī)則： 規(guī)則1：IF A5=1 and A4=1 THEN Class為1； 規(guī)則2：IF A5=1 and A4=2 THEN Class為2； 規(guī)則3：IF A5=2 THEN Class為2； 規(guī)則4：IF A5=3 and A2=1 THEN Class為1； 規(guī)則5：IF A5=3 and A2=2 THEN Class為2； 規(guī)則6：IF A5=3 and A2=3 and A1=2 THEN Class為1； 規(guī)則7：I

10、F A5=3 and A2=3 and A1=1 THEN Class為2； 使用極大熵生成的決策樹(shù)轉(zhuǎn)換成IF-THEN 規(guī)則： 規(guī)則1：IF 規(guī)則2：IF 規(guī)則3：IF 規(guī)則4：IF 規(guī)則5：IF 規(guī)則6：IF 規(guī)則7：IF 規(guī)則8：IF 規(guī)則9：IF A4=1 A4=1 A4=1 A4=2 A4=2 A4=2 A4=2 A4=2 A4=2 and and and and and and and and and A1=2 A1=1 A1=1 A3=1 A3=2 A3=2 A3=2 A3=2 A3=2 THEN Class為1； and A5=1 THEN Class為1； and A5=3

11、THEN Class為2； THEN Class為2； and A2=2 THEN Class為2； and A2=3 THEN Class為2； and A2=1 and A1=1 THEN Class為1； and A2=1 and A1=2 and A5=1 THEN Class為2； and A2=1 and A1=2 and A5=3 THEN Class為1； 問(wèn)題 3.分別給出此兩組規(guī)則對(duì)表 2 給出的兩個(gè)測(cè)試樣本的預(yù)測(cè)類(lèi)別 答 極小熵構(gòu)造的決策樹(shù)對(duì)表2預(yù)測(cè)類(lèi)別： Smaples A1 A2 A3 A4 A5 Class 1 2 2 1 1 1 1 2 1 1 1 2 1 2 極

12、大熵構(gòu)造的決策樹(shù)對(duì)表2預(yù)測(cè)類(lèi)別： Smaples A1 A2 A3 1 2 2 1 2 1 1 1 A4 1 2 A5 1 1 Class 1 2 問(wèn)題 4. 那組結(jié)果你認(rèn)為更可信？闡述你的理由。 答 當(dāng)然，兩組結(jié)果都一樣的話(huà)最可信。 極小熵生成的決策樹(shù)更可信。因?yàn)樽兞康牟淮_定性越大，熵也就越大，一個(gè) 系統(tǒng)越是有序，信息熵就越低；反之，一個(gè)系統(tǒng)越是混亂，信息熵就越高，所以 每次采用極小熵進(jìn)行劃分等同于按照不確定性最小劃分，劃分的過(guò)程更加準(zhǔn)確， 可靠。反之，采用極大熵劃分所得到的決策樹(shù)會(huì)比較高，不夠直觀。 問(wèn)題 5. 利用極小熵生成的決策樹(shù)是否是“最小決策樹(shù)”？給出你的證明或反例 答 猜想：利用

13、極小熵生成的決策樹(shù)是“最小決策樹(shù)”。 反證法：假設(shè)利用極小熵生成的不是最小決策樹(shù)，那么一定存在一個(gè)更小的 決策樹(shù)，如果存在，那么極小熵生成的就不是最小決策樹(shù)。反之，找不出比這個(gè) 更小的樹(shù)，那么利用極小熵生成的決策樹(shù)就是“最小決策樹(shù)”。證不出來(lái)。 如果屬性比較少可以用窮舉法列舉決策樹(shù)，可以觀察一下極小熵生成的是不 是最小決策樹(shù)。但屬性多的話(huà)是一個(gè) NP hard 問(wèn)題，暫時(shí)不確定 問(wèn)題 6. 如果第一個(gè)屬性 A1 為數(shù)值屬性，其取值為 0,1區(qū)間的實(shí)數(shù)，如表 3、 表 4 所示。 此時(shí)如何處理？進(jìn)一步請(qǐng)按你的方法基于表 3 給出的訓(xùn)練集產(chǎn)生一棵 決策樹(shù)（用極小熵選擇擴(kuò)展屬性），并給出表 4 中的

14、測(cè)試樣本的預(yù)測(cè)類(lèi)別。 表 3. 訓(xùn)練樣本 A3 A4 2 2 2 2 2 1 2 2 1 2 2 1 2 2 1 1 2 2 2 1 2 2 2 1 2 1 1 2 2 1 Samples 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A1 0.60 0.90 0.35 0.15 0.50 0.95 0.20 0.12 0.68 0.95 0.05 0.02 0.08 0.45 0.14 A2 3 1 3 1 3 1 2 1 2 3 1 2 3 2 3 A5 2 1 1 3 2 1 2 1 3 3 3 1 1 2 3 Class 2 2 1 1 2 1 2 1 2 2

15、 1 1 1 2 1 Smaples 1 2 A1 0.10 0.98 A2 2 1 表 4. 測(cè)試樣本 A3 A4 1 1 1 2 A5 1 1 Class ? ? 答 將 A1 的概率值化成為在兩個(gè)區(qū)間范圍內(nèi)0-0.5和 0.5-1，也就是在 0-0.5為 1，(0.5-1為 2，則訓(xùn)練樣本就化為了表(1 表(1 Samples 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A1 2 2 1 1 1 2 1 1 2 2 1 1 1 1 1 A2 3 1 3 1 3 1 2 1 2 3 1 2 3 2 3 A3 2 2 2 2 1 2 2 1 2 2 2 2 2 1

16、 2 A4 2 2 1 2 2 1 2 1 2 1 2 1 1 2 1 A5 2 1 1 3 2 1 2 1 3 3 3 1 1 2 3 Class 2 2 1 1 2 1 2 1 2 2 1 1 1 2 1 接下來(lái)就是和上述一樣的畫(huà)出決策樹(shù)了 0.5875+0.2406=0.8281 參考上面的結(jié)果 得： 0.8569 0.8991 0.8896 0.5837 用極小熵選擇擴(kuò)展屬性得到?jīng)Q策樹(shù)： 初始一用15個(gè)訓(xùn)練集。 15 個(gè)訓(xùn)練樣本 A5=1 A5=2 A5=3 6 A1=1 A1=2 4 Class2 A1=1 5 A1=2 4 Class1 A4=1 2 A4=2 2 Class1 3 Class2 1 Class1 1 Class2 決策樹(shù)轉(zhuǎn)換成IF-THEN 規(guī)則： 規(guī)則1：IF 規(guī)則2：IF 規(guī)則3：IF 規(guī)則4：IF 規(guī)則5：IF 規(guī)則6：IF A5=