【正文】 否 優(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（收入） = 收入信息增益 = = (2) 決策樹(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) 第 4步計(jì)算學(xué)生的熵 學(xué)生共分二個(gè)組： 學(xué)生、非學(xué)生 E（學(xué)生） = 年齡信息增益 = = （ 3） 決策樹(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) 第 5步計(jì)算信譽(yù)的熵 信譽(yù)分二個(gè)組： 良好，優(yōu)秀 E（信譽(yù)） = 信譽(yù)信息增益 = = （ 4） 決策樹(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) 第 6步計(jì)算選擇節(jié)點(diǎn) 年齡信息增益 = = （ 1） 收入信息增益 = = （ 2） 年齡信息增益 = = （ 3） 信譽(yù)信息增益 = = （ 4） 決策樹(shù)算法 計(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 青 高 否 優(yōu) 不買(mǎi) 128 青 中 否 良 不買(mǎi) 64 青 低 是 良 買(mǎi) 64 青 中 是 優(yōu) 買(mǎi) 青年買(mǎi)與不買(mǎi)比例為 128/256 S1(買(mǎi) )=128 S2（不買(mǎi)） = 256 S=S1+S2=384 P1=128/384 P2=256/384 I(S1,S2)=I(128,256) =P1Log2P1P2Log2P2 =(P1Log2P1+P2Log2P2) = 決策樹(shù)算法 計(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) 如果選擇收入作為節(jié)點(diǎn) 分高、中、低 平均信息期望（加權(quán)總和）： E(收入） = * 0 + * + * 0 = Gain(收入 ) = I(128, 256) E(收入 )= – = I(0,128)=0 比例 : 128/384= I(64,128)= 比例 : 192/384= I(64,0)=0 比例 : 64/384= 注意 決策樹(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) 年齡 青年 中年 老年 學(xué)生 買(mǎi) 信譽(yù) 葉子 否 是 優(yōu) 良 買(mǎi) 不買(mǎi) 買(mǎi) / 不買(mǎi) 買(mǎi) 葉子 葉子 葉子 決策樹(shù)分類(lèi)規(guī)則提取 ? 決策樹(shù)所表示的分類(lèi)知識(shí)可以被抽取出來(lái)并可用IFTHEN 分類(lèi)規(guī)則形式加以表示。 信息增益的計(jì)算 設(shè) S是有 s個(gè)訓(xùn)練樣本數(shù)據(jù)的集合，類(lèi)標(biāo)號(hào)屬性具有 m個(gè)不同值，定義 m個(gè)不同類(lèi) Ci（i=1,2,…,m ）， si是類(lèi) Ci中的樣本數(shù)，則對(duì)一個(gè)給定的訓(xùn)練樣本分類(lèi)所需要的 期望信息為 ： ? ? ? ?????miiim ppsssI1221 l o g, ?其中 pi是任意樣本屬于 Ci的概率，可用 si/s來(lái)估計(jì) 決策樹(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ì)數(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) 決策屬性“買(mǎi)計(jì)算機(jī)？”。 ? 用信息增益這種 信息論 的理論方法，使得對(duì)一個(gè)對(duì)象分類(lèi)所需要的期望測(cè)試數(shù)目達(dá)到最小，并確保找到一棵簡(jiǎn)單的樹(shù)。 這個(gè)過(guò)程實(shí)際上是一個(gè)從數(shù)據(jù)中獲取知識(shí) ， 進(jìn)行機(jī)器學(xué)習(xí)的過(guò)程 。 收入 40000 高負(fù)債 工作時(shí)間 5年 是 否 是 否 “年收入大于￥ 40000”并且“高負(fù)債”的用戶(hù)被認(rèn)為是“高風(fēng)險(xiǎn)”； “年收入小于￥ 40000”但“工作時(shí)間大于 5年”的申請(qǐng)，是“低風(fēng)險(xiǎn)”； N Y Y N N Y 決策樹(shù) buys_puter的決策樹(shù)示意 Age? Credit_rating? student? yes no yes yes no =30? 40 30~40 yes no fair excellent 決策樹(shù) ? 決策樹(shù)（ decision tree） ? 1986年 Quinlan提出了著名的 ID3算法。它從一組無(wú)次序、無(wú)規(guī)則的元組中推理出決策樹(shù)表示形式的分類(lèi)規(guī)則。 輸出： 輸出類(lèi)別 c。每個(gè)樣本代表 n維空間的一個(gè)點(diǎn)。 ? 輸出：輸出類(lèi)別 c。 = x i y ii229。 ?相似性（距離）度量可以用來(lái)識(shí)別數(shù)據(jù)庫(kù)中不同成員之間的 “ 相似程度 ” 。 – 假正 : 判定 ti在 Cj中，實(shí)際上不在其中。 ? 通過(guò)分析訓(xùn)練數(shù)據(jù)集來(lái)構(gòu)造 分類(lèi)模型 ，可用分類(lèi)規(guī)則、決策樹(shù)或數(shù)學(xué)公式等形式提供。 ?為了識(shí)別乘客是否是潛在的恐怖分子或罪犯，機(jī)場(chǎng)安全攝像站需要對(duì)乘客的臉部進(jìn)行掃描并辨識(shí)臉部的基本模式（例如雙眼間距、嘴的大小及形狀、頭的形狀）， ?然后將得到的模式與數(shù)據(jù)庫(kù)中的已知恐怖分子或罪犯的 模式 進(jìn)行逐個(gè)比較，看看是否與其中的某一模式相匹配。 ?在分析測(cè)試數(shù)據(jù)之前，類(lèi)別就已經(jīng)被確定了，所以分類(lèi)統(tǒng)稱(chēng)被稱(chēng)作 有指導(dǎo)的學(xué)習(xí) 。 ?離散化的方法包括幾下幾種。 ?主成分分析（ PCA）：有損，能更好地處理稀疏數(shù)據(jù)。 ?逐步向前選擇 ?逐步向后刪除 ?向前選擇和向后刪除的結(jié)合 ?決策樹(shù)歸納 維度規(guī)約 ?維度歸約使用數(shù)據(jù)編碼或變換，以便得到原數(shù)據(jù)的歸約或“壓縮”表示。 ?其目標(biāo)是找出最小屬性集，使得數(shù)據(jù)類(lèi)的概率分布盡可能地接近使用所有屬性得到的原分布。 數(shù)據(jù)規(guī)約 數(shù)據(jù)歸約策略： （ 1）數(shù)據(jù)立方體聚集：對(duì)數(shù)據(jù)立方體做聚集操作 （ 2）屬性子集選擇：檢測(cè)并刪除不相關(guān)、弱相關(guān)或冗余的屬性和維。vev ??? 1139。 ?數(shù)據(jù)泛化（概化）：使用概念分層，用高層概念替換低層或“原始”數(shù)據(jù)。 ?人工再審查這些孤立點(diǎn) Regression ?通過(guò)構(gòu)造函數(shù)來(lái)符合數(shù)據(jù)變化的趨勢(shì)，這樣可以用一個(gè)變量預(yù)測(cè)另一個(gè)變量。 ? 分析客戶(hù)使用分銷(xiāo)渠道的情況和分銷(xiāo)渠道的容量 ；建立利潤(rùn)評(píng)測(cè)模型；客戶(hù)關(guān)系優(yōu)化；風(fēng)險(xiǎn)控制等 ? 電子商務(wù) ? 網(wǎng)上商品推薦；個(gè)性化網(wǎng)頁(yè)；自適應(yīng)網(wǎng)站 … ? 生物制藥、基因研究 ? DNA序列查詢(xún)和匹配； 識(shí)別基因序列的共發(fā)生性 … ? 電信 ? 欺詐甄別；客戶(hù)流失 … ? 保險(xiǎn)、零售 數(shù)據(jù)挖掘應(yīng)用 Debt10% of Ine Debt=0% Good Credit Risks Bad Credit Risks Good Credit Risks Yes Yes Yes NO NO NO Ine$40K Q Q Q Q I I 1 2 3 4 5 6 factor 1 factor 2 factor n 神經(jīng)網(wǎng)絡(luò) Neural Networks 聚類(lèi)分析 Clustering Open Ac’ t Add New Product Decrease Usage ??? Time 序列分析 Sequence Analysis 決策樹(shù)