計(jì)算機(jī)數(shù)學(xué)-樹(shù)課件

1、Chapter6樹(shù)Chapter6樹(shù)學(xué)習(xí)目標(biāo) 6.2節(jié) 掌握最小連接算法，會(huì)使用Kruskal算法和Prim算法求最小生成樹(shù)。 6.1節(jié) 理解樹(shù)的基本概念、樹(shù)的模型 6.3節(jié) 理解并掌握數(shù)據(jù)挖掘中決策樹(shù)算法樹(shù)是圖論中應(yīng)用最廣泛、最重要的子類(lèi)之一。1847年，Gustav Kirchhoff（古斯塔夫基爾霍夫，1824-1887）研究電網(wǎng)絡(luò)時(shí)發(fā)現(xiàn)了圖論的新應(yīng)用，在有關(guān)電網(wǎng)的著作中首次使用了樹(shù)。后來(lái)Arthur Cayley（亞瑟?jiǎng)P雷，1821-1895）在有機(jī)化學(xué)領(lǐng)域重新發(fā)展了樹(shù)，用樹(shù)去計(jì)數(shù)某些類(lèi)型的化合物。現(xiàn)在，計(jì)算機(jī)科學(xué)廣泛采用了樹(shù)的概念。比如，在數(shù)據(jù)庫(kù)系統(tǒng)中用樹(shù)來(lái)組織信息，在編繹程序中用樹(shù)

2、表示源程序的語(yǔ)法結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)中樹(shù)的存儲(chǔ)，數(shù)據(jù)挖掘中的決策樹(shù)等，在最優(yōu)化問(wèn)題的求解中樹(shù)也起著重要作用。學(xué)習(xí)目標(biāo) 6.2節(jié) 掌握最小連接算法，會(huì)使用Kruska6.1樹(shù)的概念與類(lèi)型6.1.1 樹(shù)的相關(guān)概念連通無(wú)回路的無(wú)向圖，稱(chēng)為無(wú)向樹(shù)，簡(jiǎn)稱(chēng)樹(shù)(Tree)，用T表示。T中度為1的結(jié)點(diǎn)稱(chēng)為樹(shù)葉，度大于1的結(jié)點(diǎn)稱(chēng)為分支點(diǎn)或內(nèi)點(diǎn)，每個(gè)連通分圖都是樹(shù)的非連通圖稱(chēng)為森林。樹(shù)的定義例6.1 圖(a)、(b)是樹(shù)，因?yàn)樗鼈冞B通又不包含回路。圖(c)、(d)均不是樹(shù)，圖（c）雖無(wú)回路，但不連通，而圖(d)雖連通，但有回路。圖(c)是森林。(a)(b)(c)(d)6.1樹(shù)的概念與類(lèi)型6.1.1 樹(shù)的相關(guān)概念連通無(wú)回

3、路的一個(gè)連通有回路的圖（如圖6-2）通過(guò)刪邊去掉回路，成為樹(shù)，如圖6-3,圖6-4。一個(gè)連通有回路的圖（如圖6-2）通過(guò)刪邊去掉回路，成為樹(shù)，如樹(shù)中結(jié)點(diǎn)數(shù)與邊數(shù)的關(guān)系定理 在(n,m)樹(shù)中必有n=m+1。樹(shù)中結(jié)點(diǎn)數(shù)與邊數(shù)的關(guān)系定理 在(n,m)樹(shù)中必有n樹(shù)的特性（1）一個(gè)無(wú)向圖是樹(shù)當(dāng)且僅當(dāng)在它的每對(duì)結(jié)點(diǎn)之間存在唯一的通路；（2）樹(shù)是邊數(shù)最多的無(wú)回路圖，樹(shù)是邊數(shù)最少的連通圖；（3）帶有n個(gè)結(jié)點(diǎn)的樹(shù)（稱(chēng)為n階樹(shù)）含有n-1條邊，且所有結(jié)點(diǎn)的度之和為2(n-1)。課堂練習(xí)6.1.11、設(shè)一棵樹(shù)有兩個(gè)結(jié)點(diǎn)度為2，一個(gè)結(jié)點(diǎn)度為3，三個(gè)結(jié)點(diǎn)度為4，其余結(jié)點(diǎn)度1，求它有幾個(gè)結(jié)點(diǎn)度為1？2、一棵樹(shù)有6片樹(shù)葉，

4、3個(gè)2度結(jié)點(diǎn)，其余結(jié)點(diǎn)度數(shù)為4，求這棵樹(shù)所含的邊數(shù)。樹(shù)的特性（1）一個(gè)無(wú)向圖是樹(shù)當(dāng)且僅當(dāng)在它的每對(duì)結(jié)點(diǎn)之間存在唯6.1.2 根樹(shù)根樹(shù)指定一個(gè)結(jié)點(diǎn)作為根并且每條邊的方向都離開(kāi)根的樹(shù)，即僅一個(gè)結(jié)點(diǎn)的入度為0，其余結(jié)點(diǎn)的入度為1的有向圖稱(chēng)為根樹(shù)(root)。入度為0的結(jié)點(diǎn)稱(chēng)為樹(shù)根，出度為0的結(jié)點(diǎn)稱(chēng)為樹(shù)葉，出度不為0的結(jié)點(diǎn)稱(chēng)為分支點(diǎn)（內(nèi)點(diǎn)）。6.1.2 根樹(shù)根樹(shù)指定一個(gè)結(jié)點(diǎn)作為根并且每條邊的方向都離開(kāi)根樹(shù)的模型（1）表示組織機(jī)構(gòu)：一個(gè)虛擬大學(xué)的行政結(jié)構(gòu)圖根樹(shù)的模型（1）表示組織機(jī)構(gòu)：一個(gè)虛擬大學(xué)的行政結(jié)構(gòu)圖（2）表示計(jì)算機(jī)的文件結(jié)構(gòu)（2）表示計(jì)算機(jī)的文件結(jié)構(gòu)（3）家族樹(shù)家屬關(guān)系的相關(guān)術(shù)語(yǔ)我們引用到根樹(shù)

5、中來(lái)表示結(jié)點(diǎn)之間的關(guān)系。（1）在根樹(shù)中，若u可達(dá)v且長(zhǎng)度大于或等于2，則稱(chēng)u是v的祖先，v是u的后代；若是根樹(shù)中的一條有向邊，則稱(chēng)u是v的父親，v是u的兒子；同一結(jié)點(diǎn)的兒子結(jié)點(diǎn)稱(chēng)為兄弟；父親在同一層的結(jié)點(diǎn)稱(chēng)為堂兄弟。（2）在根樹(shù)中，從樹(shù)根到任意結(jié)點(diǎn)u經(jīng)過(guò)的邊數(shù)稱(chēng)為結(jié)點(diǎn)u的層數(shù)，層數(shù)最大的結(jié)點(diǎn)的層數(shù)稱(chēng)為樹(shù)高。 有一位生物學(xué)家在研究家族遺傳問(wèn)題時(shí)，采用了“樹(shù)”形來(lái)描述家族成員的遺傳關(guān)系。家族樹(shù)用結(jié)點(diǎn)表示家族成員，用邊表示親子關(guān)系。如某家族祖宗a，有三個(gè)兒子b,c,d，b生了兩個(gè)兒子e,f，d生了兩個(gè)兒子g,h，e有三個(gè)兒子，i,j,k，g有兩個(gè)兒子l,m，j生了一個(gè)兒子n，這種家屬關(guān)系用根樹(shù)表示。

6、如右圖畫(huà)根樹(shù)時(shí)，把樹(shù)根畫(huà)在圖的頂端，邊的方向向下，形成一棵倒掛的樹(shù)。（3）家族樹(shù)家屬關(guān)系的相關(guān)術(shù)語(yǔ)我們引用到根樹(shù)中來(lái)表示結(jié)點(diǎn)之間課堂練習(xí)6.1.21、樹(shù)T如圖 ，指定b作根，畫(huà)出所形成的根樹(shù)，回答下列問(wèn)題（1）哪些結(jié)點(diǎn)是樹(shù)葉？（2）哪些結(jié)點(diǎn)是內(nèi)點(diǎn)？（3）a的祖先、a的父親是哪個(gè)結(jié)點(diǎn)？（4）e有沒(méi)有兄弟，兒子？ （5）樹(shù)高是多少？2、在組織機(jī)構(gòu)根樹(shù)中以下術(shù)語(yǔ)分別表示什么內(nèi)容？（1）一個(gè)結(jié)點(diǎn)的父親；（2）一個(gè)結(jié)點(diǎn)的兒子；（3）一個(gè)結(jié)點(diǎn)的兄弟；（4）一個(gè)結(jié)點(diǎn)的祖先；（5）一個(gè)結(jié)點(diǎn)的后代；（6）一個(gè)結(jié)點(diǎn)的層數(shù)；（7）樹(shù)的高度。課堂練習(xí)6.1.21、樹(shù)T如圖 ，指定b作根，畫(huà)出所形成的根6.1.3 二叉

7、樹(shù)有序樹(shù)、無(wú)序樹(shù)樹(shù)根樹(shù)的每個(gè)內(nèi)點(diǎn)的兒子都規(guī)定次序，則把此根樹(shù)稱(chēng)為有序樹(shù)。不考慮內(nèi)點(diǎn)兒子的次序，此根樹(shù)稱(chēng)為無(wú)序樹(shù)。二叉樹(shù)定義設(shè)T是一棵有序樹(shù)，若T的每個(gè)內(nèi)點(diǎn)至多有兩個(gè)子結(jié)點(diǎn)（兒子），則稱(chēng)T為二叉樹(shù)。二叉樹(shù)的子樹(shù)有左子樹(shù)和右子樹(shù)之分，其次序不能交換。6.1.3 二叉樹(shù)有序樹(shù)、無(wú)序樹(shù)樹(shù)根樹(shù)的每個(gè)內(nèi)點(diǎn)的兒二叉樹(shù)基本特征（1）每個(gè)結(jié)點(diǎn)最多只有兩棵子樹(shù)（以出度作為樹(shù)結(jié)點(diǎn)的度，則二叉樹(shù)不存在出度大于2的結(jié)點(diǎn)）；（2）左子樹(shù)和右子樹(shù)次序不能顛倒。下圖是兩棵不同的樹(shù)二叉樹(shù)基本特征（1）每個(gè)結(jié)點(diǎn)最多只有兩棵子樹(shù)（以出度作為樹(shù)結(jié)正則二叉樹(shù)每個(gè)內(nèi)點(diǎn)都恰有兩個(gè)兒子的二叉樹(shù)稱(chēng)為正則二叉樹(shù)（或稱(chēng)滿二叉樹(shù)）。例6.2 判斷圖

8、6-11(a),(b),(c)是否滿二叉樹(shù)？正則二叉樹(shù)每個(gè)內(nèi)點(diǎn)都恰有兩個(gè)兒子的二叉樹(shù)稱(chēng)為正則二叉樹(shù)（或稱(chēng)計(jì)算機(jī)數(shù)學(xué)-樹(shù)課件二叉排序樹(shù)各數(shù)據(jù)元素在二叉樹(shù)中按一定次序排列，這樣的二叉樹(shù)稱(chēng)為二叉排序樹(shù)。規(guī)定二叉排序樹(shù)中的每個(gè)結(jié)點(diǎn)的左子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字值都小于該結(jié)點(diǎn)的關(guān)鍵字值，而右子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵字值都大于該結(jié)點(diǎn)的關(guān)鍵字值。計(jì)算機(jī)使用中大部分用來(lái)排序和查找各種各樣的信息，排序和查找是數(shù)據(jù)處理中常見(jiàn)運(yùn)算。例6.3下圖中的二叉樹(shù)，哪些是二叉排序樹(shù)二叉排序樹(shù)各數(shù)據(jù)元素在二叉樹(shù)中按一定次序排列，這樣的二叉樹(shù)稱(chēng)例6.4 構(gòu)造關(guān)鍵碼集合red,green,yellow,white,black,grey,p

9、ink,purple,blue二叉排序樹(shù)，說(shuō)出查找關(guān)鍵字pink的過(guò)程。redgreenyellowwhiteblackgreypinkpurpleblue例6.4 構(gòu)造關(guān)鍵碼集合red,green,yell課堂練習(xí)6.1.31、判斷圖兩個(gè)二叉樹(shù)是否相同課堂練習(xí)6.1.31、判斷圖兩個(gè)二叉樹(shù)是否相同6.1.4決策樹(shù)設(shè)有一棵根樹(shù)，如果其每個(gè)分支點(diǎn)都會(huì)提出一個(gè)問(wèn)題，從根開(kāi)始，每回答一個(gè)問(wèn)題，走相應(yīng)的邊，最后到達(dá)一個(gè)葉結(jié)點(diǎn)，即獲得一個(gè)決策，這樣的根樹(shù)稱(chēng)為決策樹(shù)(Decision Tree)。下面我們用決策樹(shù)表示算法，并使得在最壞情形下花費(fèi)時(shí)間最少。例6.5 現(xiàn)有5枚外觀一樣的硬幣，只有1枚硬幣與其它

10、的重量不同。問(wèn)如何使用一架天平來(lái)判別哪枚硬幣是壞的，重還是輕？分析 用天平來(lái)稱(chēng)A和B兩枚硬幣，只有AB、A = B、AB三種可能的情形，因此可構(gòu)造3元決策樹(shù)來(lái)解決。6.1.4決策樹(shù)設(shè)有一棵根樹(shù)，如果其每個(gè)分支點(diǎn)都會(huì)提出一個(gè)C:DA:BA:EE,HE,LC:ED,LC,HC:ED,HC,LA:EB,HA,LA:EB,LA,H從根到葉就是一種求解過(guò)程，由于該樹(shù)有10片葉子，因此最多有10種可能的解。又由于該樹(shù)高為3，因此最壞情形下需要3次判別就能得到結(jié)論。C:DA:BA:EE,HE,LC:ED,LC,H課堂練習(xí)6.1.4課堂練習(xí)最小連接問(wèn)題6.2.1生成樹(shù)如果無(wú)向圖G的生成子圖T（

11、T與G的頂點(diǎn)相同）是一棵樹(shù)，則稱(chēng)T是G的生成樹(shù)。判斷下圖中的圖(b)、(c)、(d)、(e)是否是圖(a)的生成樹(shù)。abcdef(a)abcdef(b)abcdef(c)abcdef(d)bcdef(e)生成樹(shù)其實(shí)是刪除了原圖中能形成回路的邊之后所剩下的子圖，但并不是所有的圖都有生成樹(shù)。定理 圖G有一個(gè)生成樹(shù)T當(dāng)且僅當(dāng)G是連通的。6.2最小連接問(wèn)題6.2.1生成樹(shù)如果無(wú)向圖G的生成子圖求圖G=生成樹(shù)的方法破圈法和避圈法破圈法若圖G無(wú)回路，那么G的生成樹(shù)是其本身。若G有回路，任取一條回路，去掉回路中的一邊，直到圖中不含回路，剩下的圖就是原圖的生成樹(shù)，這種作法稱(chēng)為破圈法。 (n,m)圖每次刪除回路

12、中的一條邊，其刪除的邊的總數(shù)為m-n+1。例6.7 經(jīng)過(guò)地質(zhì)勘測(cè)某工業(yè)區(qū)可按照?qǐng)D6-17修建道路連接6個(gè)工廠。為厲行節(jié)約，問(wèn)至少鋪設(shè)幾條道路使6個(gè)工廠能夠相通，畫(huà)出圖。解 問(wèn)題即是找圖6-17的生成樹(shù)，圖中結(jié)點(diǎn)數(shù)n=6，邊數(shù)m=11，,其生成樹(shù)的邊數(shù)=6-1=5，用破圈法刪除6條邊。所以至少要鋪設(shè)5條道路才能使6個(gè)工廠有路相通。圖6-18是其中一種道路鋪設(shè)。避圈法每次選取G中一條與已選取的邊不構(gòu)成回路的邊，選取的邊的總數(shù)為n-1。求圖G=生成樹(shù)的方法破圈法和避圈法破圈法若圖G例6.8 分別用破圈法和避圈法求下圖的生成樹(shù)。 123456分析 分別用破圈法和避圈法依次進(jìn)行即可。用破圈法時(shí)，由于n

13、= 6，m = 9，所以m-n+1 = 4，故要?jiǎng)h除的邊數(shù)為4，因此只需4步即可。用避圈法時(shí)，由于n = 6，所以n-1 = 5，故要選取5條邊，因此需5步即可。 破圈法例6.8 分別用破圈法和避圈法求下圖的生成樹(shù)。 12345避圈法由于生成樹(shù)的形式不惟一，故上述兩棵生成樹(shù)都是所求的。 破圈法和避圈法的計(jì)算量較大，主要是需要找出回路或驗(yàn)證不存在回路。 123456123456避圈法由于生成樹(shù)的形式不惟一，故上述兩棵生成樹(shù)都是所求的。 6.2.2最小生成樹(shù)及其算法最小生成樹(shù) 設(shè)G是無(wú)向連通賦權(quán)圖，在G的全部生成樹(shù)中，如果生成樹(shù)T所有邊的權(quán)和最小，則稱(chēng)T是圖G的最小生成樹(shù)。如在n個(gè)城市之間鋪設(shè)光纜

14、，要使這 n 個(gè)城市的任意兩個(gè)之間都可以通信，同時(shí)使得鋪設(shè)光纜的總費(fèi)用最低。鋪設(shè)光纜的費(fèi)用很高，且各個(gè)城市之間鋪設(shè)光纜的費(fèi)用不同，這就需要找到帶權(quán)的最小生成樹(shù)。最小生成樹(shù)問(wèn)題就是賦權(quán)圖的最優(yōu)化問(wèn)題，也稱(chēng)為最小連接問(wèn)題。最小生成樹(shù)算法避圈法避圈法的主要思想是：首先選一條權(quán)最小的邊，以后每一步，在未選的邊中，選擇一條權(quán)最小且與已選的邊不構(gòu)成圈的邊。每一步中，如果有兩條或兩條以上的邊都是權(quán)值最小的邊，則從中任選一條，此時(shí)最小生成樹(shù)不唯一。避圈算法主要分為兩種： Kruskal算法和Prim算法。6.2.2最小生成樹(shù)及其算法最小生成樹(shù) 設(shè)G是無(wú)向連通賦權(quán)圖Kruskal算法（1956年克魯斯卡爾提出的

15、）Kruskal算法（1956年克魯斯卡爾提出的）例6.9 用Kruskal算法求圖中賦權(quán)圖的最小生成樹(shù)。4655761f923adbcimjkehg343446587582345k1fech34a3i5dm2g2bj4解 n=12，按算法要執(zhí)行n-1=11次，w(T) = 36。 例6.9 用Kruskal算法求圖中賦權(quán)圖的最小生成樹(shù)。4在Prim算法的步驟2中，若滿足條件的最小權(quán)邊不止一條，則可從中任選一條，這樣就會(huì)產(chǎn)生不同的最小生成樹(shù)。 在Prim算法的步驟2中，若滿足條件的最小權(quán)邊不止例6.10 用Prim算法求圖中賦權(quán)圖的最小生成樹(shù)。 5f102dbce7g64582a7ge2f5b

16、42cad5解 n = 7，按算法要執(zhí)行n-1 = 6次，w(T) = 25。 由Prim算法可以看出，每一步得到的圖一定是樹(shù)，故不需要驗(yàn)證是否有回路，因此它的計(jì)算工作量較Kruskal算法要小。 例6.10 用Prim算法求圖中賦權(quán)圖的最小生成樹(shù)。 5計(jì)算機(jī)數(shù)學(xué)-樹(shù)課件6.3 數(shù)據(jù)挖掘中的決策樹(shù)簡(jiǎn)介6.3.1 數(shù)據(jù)挖掘基本認(rèn)識(shí)數(shù)據(jù)挖掘就是從海量的數(shù)據(jù)中淘金。數(shù)據(jù)挖掘：就是從海量的數(shù)據(jù)中采用自動(dòng)或半自動(dòng)的建模算法，尋找隱藏在數(shù)據(jù)中的信息，如趨勢(shì)（Trend）、模式（Pattern）及相關(guān)性（Relationship），提取人們事先不知道的、有價(jià)值的、可實(shí)用的信息和知識(shí)的過(guò)程。6.3 數(shù)據(jù)挖掘中

17、的決策樹(shù)簡(jiǎn)介6.3.1 數(shù)據(jù)挖掘基本認(rèn)33數(shù)據(jù)挖掘應(yīng)用在性別 年齡種族家庭人口家庭收入申請(qǐng)?jiān)撔Ｔ蚣彝プ≈?學(xué)校錄取部門(mén)的困擾：新生錄取以后會(huì)不會(huì)來(lái)報(bào)到？33數(shù)據(jù)挖掘應(yīng)用在性別 學(xué)校錄取部門(mén)的困擾：新生錄取以后34產(chǎn)品名稱(chēng)產(chǎn)品型號(hào)產(chǎn)品價(jià)格生產(chǎn)廠家生產(chǎn)國(guó)家出售地點(diǎn)出售日期Wal-Mart的銷(xiāo)售與供應(yīng)商34產(chǎn)品名稱(chēng)Wal-Mart的銷(xiāo)售與供應(yīng)商尿片啤酒是一個(gè)經(jīng)典的購(gòu)物籃問(wèn)題購(gòu)物籃問(wèn)題可以推廣到另外的問(wèn)題應(yīng)用上：哪些產(chǎn)品可以捆綁促銷(xiāo)？讀者購(gòu)買(mǎi)書(shū)籍時(shí)，推薦他可能感興趣的其他書(shū)籍？網(wǎng)頁(yè)信息欄的設(shè)置應(yīng)考慮哪些相關(guān)網(wǎng)頁(yè)相鄰，使得點(diǎn)擊量增加？當(dāng)一些安全因素出現(xiàn)時(shí)，導(dǎo)致另一些因素或結(jié)果出現(xiàn)的可能性多大？“啤酒”

18、和“尿布”兩個(gè)看上去沒(méi)有關(guān)系的商品擺放在一起進(jìn)行銷(xiāo)售、并獲得了很好的銷(xiāo)售收益，這種現(xiàn)象就是賣(mài)場(chǎng)中商品之間的關(guān)聯(lián)性，研究“啤酒與尿布”關(guān)聯(lián)的方法就是購(gòu)物籃分析，購(gòu)物籃分析是沃爾瑪秘而不宣的獨(dú)門(mén)武器，購(gòu)物籃分析可以幫助我們?cè)陂T(mén)店的銷(xiāo)售過(guò)程中找到具有關(guān)聯(lián)關(guān)系的商品，并以此獲得銷(xiāo)售收益的增長(zhǎng)！尿片啤酒是一個(gè)經(jīng)典的購(gòu)物籃問(wèn)題購(gòu)物籃問(wèn)題可以推廣到另外的問(wèn)36姓名年齡收入學(xué)生信譽(yù)電話地址郵編買(mǎi)計(jì)算機(jī)張三234000是良281-322-03282714 Ave. M77388買(mǎi)李四342800否優(yōu)713-239-78305606 Holly Cr78766買(mǎi)王二701900否優(yōu)281-242-32222000

19、 Bell Blvd.70244不買(mǎi)趙五18900是良281-550-0544100 Main Street70244買(mǎi)劉蘭342500否優(yōu)713-239-7430606 Holly Ct78566買(mǎi)楊俊278900否優(yōu)281-355-7990233 Rice Blvd.70388不買(mǎi)張毅389500否優(yōu)281-556-0544399 Sugar Rd.78244買(mǎi)你能判定他/她買(mǎi)計(jì)算機(jī)的可能性大不大嗎？36姓名年齡收入學(xué)生信譽(yù)電話地址郵編買(mǎi)計(jì)算機(jī)張三23400037數(shù)據(jù)挖掘簡(jiǎn)介1我們擁有什么: Huge amount of data (GTE:1TB/day)2.我們需要什么: Inform

20、ation and knowledge3. 我們應(yīng)該怎么辦: Data Mining 37數(shù)據(jù)挖掘簡(jiǎn)介1我們擁有什么: 38Neural Networks 計(jì)算機(jī)神經(jīng)網(wǎng)絡(luò)Decision trees決策樹(shù)Regression methods Predicate logic各八顯仙神過(guò)通海數(shù)據(jù)挖掘技術(shù)38Neural Networks 各八顯仙神過(guò)通海數(shù)據(jù)挖掘數(shù)據(jù)挖掘的過(guò)程數(shù)據(jù)挖掘的過(guò)程一般可分為3個(gè)階段1、數(shù)據(jù)預(yù)處理階段：為后續(xù)階段提供高質(zhì)量的輸入數(shù)據(jù)。包括數(shù)據(jù)清理、數(shù)據(jù)集成、數(shù)據(jù)轉(zhuǎn)化、數(shù)據(jù)規(guī)約。數(shù)據(jù)清理：清除數(shù)據(jù)中不正確、不完整、不一致或者不符合要求的數(shù)據(jù)；數(shù)據(jù)集成：將多個(gè)數(shù)據(jù)源的數(shù)據(jù)進(jìn)行同

21、一存儲(chǔ)；數(shù)據(jù)轉(zhuǎn)化：對(duì)數(shù)據(jù)進(jìn)行轉(zhuǎn)換，滿足分析要求；數(shù)據(jù)規(guī)約：消減數(shù)據(jù)量或降低數(shù)據(jù)維數(shù)，以提高數(shù)據(jù)挖掘的效率和質(zhì)量。2、模式發(fā)現(xiàn)階段：首要工作是確定挖掘任務(wù)，然后根據(jù)挖掘任務(wù)選擇合適的挖掘算法。常用挖掘算法：關(guān)聯(lián)規(guī)則算法、分類(lèi)規(guī)則算法、聚類(lèi)規(guī)則算法、時(shí)間序列分析。3、挖掘結(jié)果階段：將第2階段發(fā)現(xiàn)的規(guī)則和模式可視化，即挖掘結(jié)果以一種直觀的、容易理解的方式呈現(xiàn)給用戶。數(shù)據(jù)挖掘得到的結(jié)果可能不理想，不能滿足用戶需求的情況，就需要對(duì)挖掘結(jié)果進(jìn)行評(píng)估。剔除無(wú)關(guān)模式或模式的冗余，對(duì)不滿足要求的模式，重新選擇數(shù)據(jù)，再進(jìn)行數(shù)據(jù)挖掘，直到符合用戶需求。一般可分為3個(gè)階段41決策樹(shù)的用途決策樹(shù)是數(shù)據(jù)挖掘的有力工具之一

22、推薦閱讀：決策樹(shù)的原理與構(gòu)建圍繞一個(gè)實(shí)例展開(kāi)41決策樹(shù)的用途決策樹(shù)是數(shù)據(jù)挖掘的有力工具之一推薦閱讀：決42決策樹(shù)的用途計(jì)數(shù)年齡收入學(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)題？

23、決策樹(shù)可以幫助你解決好這個(gè)問(wèn)題42決策樹(shù)的用途計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高43決策樹(shù)的用途計(jì)數(shù)年齡收入學(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ī)？他/她會(huì)買(mǎi)計(jì)算機(jī)嗎？年齡？學(xué)生？信譽(yù)？買(mǎi)青中老否是優(yōu)良不買(mǎi)買(mǎi)買(mǎi)不買(mǎi)43決策樹(shù)的用途計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高44計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60

24、老中否良買(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ù)收入？學(xué)生？青中否是高低中信譽(yù)？良優(yōu)年齡？不買(mǎi)買(mǎi)買(mǎi)不買(mǎi)44計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)6445 決策樹(shù)建立的關(guān)鍵計(jì)數(shù)年齡收入學(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ù)根？建立

25、一個(gè)好的決策樹(shù)的關(guān)鍵是決定樹(shù)根和子樹(shù)根的屬性45 決策樹(shù)建立的關(guān)鍵計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？6ID3 信息量大小的度量決策樹(shù)算法Shannon1948年提出的信息論理論。事件ai的信息量I（ ai ）可如下度量：其中p(ai)表示事件ai發(fā)生的概率。假設(shè)有n個(gè)互不相容的事件a1,a2,a3,.,an,它們中有且僅有一個(gè)發(fā)生，則其平均的信息量可如下度量：ID3 信息量大小的度量決策樹(shù)算法Shannon1948年ID3 信息量大小的度量決策樹(shù)算法上式，對(duì)數(shù)底數(shù)可以為任何數(shù)，不同的取值對(duì)應(yīng)了熵的不同單位。通常取2，并規(guī)定當(dāng)p(ai)=0時(shí) =0公式1ID3 信息量大小的度量決策樹(shù)算法上式，

26、對(duì)數(shù)底數(shù)可以為任何在決策樹(shù)分類(lèi)中，假設(shè)S是訓(xùn)練樣本集合，|S|是訓(xùn)練樣本數(shù)，樣本劃分為n個(gè)不同的類(lèi)C1,C2,.Cn，這些類(lèi)的大小分別標(biāo)記為|C1|，|C2|，.,|Cn|。則任意樣本S屬于類(lèi)Ci的概率為：ID3 信息量大小的度量決策樹(shù)算法Entropy（S，A）=（|Sv|/|S|）* Entropy（Sv）公式2 是屬性A的所有可能的值v,Sv是屬性A有v值的S子集|Sv|是Sv 中元素的個(gè)數(shù)；|S|是S中元素的個(gè)數(shù)。在決策樹(shù)分類(lèi)中，假設(shè)S是訓(xùn)練樣本集合，|S|是訓(xùn)練樣本數(shù)，樣ID3 信息量大小的度量決策樹(shù)算法Gain（S，A）是屬性A在集合S上的信息增益Gain（S，A）= Entrop

27、y（S） -Entropy（S，A） 公式3Gain（S，A）越大，說(shuō)明選擇測(cè)試屬性對(duì)分類(lèi)提供的信息越多ID3 信息量大小的度量決策樹(shù)算法Gain（S，A）是屬性計(jì)數(shù)年齡收入學(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ì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64老低

28、是良買(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))=641 S2（不買(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ù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)

29、算機(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è)。分別是年齡、收入、學(xué)生、信譽(yù)。分別計(jì)算不同屬性的信息增益。決策樹(shù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高計(jì)數(shù)年齡收入學(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青中是

30、優(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ì)算年齡的熵年齡共分三個(gè)組： 青年、中年、老年青年買(mǎi)與不買(mǎi)比例為128/256S1(買(mǎi))=128 S2（不買(mǎi)）= 256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183決策樹(shù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高計(jì)數(shù)年齡收入學(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中低是

31、優(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ì)算年齡的熵年齡共分三個(gè)組： 青年、中年、老年中年買(mǎi)與不買(mǎi)比例為256/0S1(買(mǎi))=256 S2（不買(mǎi)）= 0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0決策樹(shù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)60老中否良買(mǎi)64

32、老低是良買(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ì)算年齡的熵年齡共分三個(gè)組： 青年、中年、老年老年買(mǎi)與不買(mǎi)比例為125/127S1(買(mǎi))=125 S2（不買(mǎi)）=127S=S1+S2=252P1=125/252P2=127/252I(S1,S2)=I(125，127) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9157決策樹(shù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青

33、高否良不買(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ì)算年齡的熵年齡共分三個(gè)組： 青年、中年、老年所占比例青年組 384/1024=0.375中年組 256/1024=0.25老年組 384/1024=0.375計(jì)算年齡的平均信息期望E（年齡）=0.375*0.9183+ 0.25*0+ 0.375*0.9157 =0.6877G（年齡信息增益） =0.9537-0.6877 =0.2660 （1）決策樹(shù)算法計(jì)數(shù)年齡收

34、入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高計(jì)數(shù)年齡收入學(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ù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高否優(yōu)不買(mǎi)128中高否良買(mǎi)

35、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年齡信息增益=0.9537-0.7811 =0.1726 （3）決策樹(shù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高計(jì)數(shù)年齡收入學(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)

36、買(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ù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高計(jì)數(shù)年齡收入學(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) 年齡信息增益=0.9537-0.6877 =0.2660 （1）收入

37、信息增益=0.9537-0.9361 =0.0176 （2）學(xué)生信息增益=0.9537-0.7811 =0.1726 （3）信譽(yù)信息增益=0.9537-0.9048 =0.0453 （4）決策樹(shù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高計(jì)數(shù)年齡收入學(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)買(mǎi)買(mǎi)/不買(mǎi)葉子決策樹(shù)算法計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類(lèi)：買(mǎi)計(jì)算機(jī)？64青高否良不買(mǎi)64青高計(jì)數(shù)年齡收入學(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))=128 S2（不買(mǎi)）= 256S=S1