數(shù)據(jù)挖掘算法培訓(xùn)講義分類和預(yù)測(cè)

1、DM算法-1分類和預(yù)測(cè)(yc)出處：數(shù)據(jù)挖掘：概念與技術(shù)Jiawei Han and Micheline Kamber2022/7/251數(shù)據(jù)挖掘：概念與技術(shù)(jsh)（翻譯 張磊）共六十八頁DM算法-1 分類(fn li)和預(yù)測(cè)什么(shn me)是分類? 什么(shn me)是預(yù)測(cè)?關(guān)于分類與預(yù)測(cè)的問題通過決策樹歸納來分類貝葉斯分類通過反向傳播來分類基于關(guān)聯(lián)規(guī)則挖掘的概念來分類其它分類方法預(yù)測(cè)分類準(zhǔn)確率總結(jié)2022/7/252數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁分類: 預(yù)測(cè)分類標(biāo)簽基于訓(xùn)練集和分類屬性值(分類標(biāo)簽)構(gòu)造分類模型，然后用該模型分類新數(shù)據(jù)預(yù)測(cè): 對(duì)連續(xù)函數(shù)建模, 即預(yù)測(cè)

2、未知的或缺失的數(shù)據(jù)典型應(yīng)用信用審核目標(biāo)營銷醫(yī)療診斷治療(zhlio)效果分析分類(fn li)與預(yù)測(cè)2022/7/253數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁分類(fn li)兩步驟過程 建立一個(gè)模型: 描述預(yù)定的數(shù)據(jù)類或概念集假定每個(gè)元組/樣本可以通過類標(biāo)簽屬性來確定它屬于某個(gè)預(yù)定義的類用于創(chuàng)建模型的元組集合: 訓(xùn)練集模型可以用分類規(guī)則, 決策樹, 或數(shù)學(xué)公式來表達(dá)使用模型: 對(duì)未知(分類標(biāo)簽的)對(duì)象進(jìn)行分類模型估計(jì)準(zhǔn)確率已知測(cè)試樣本的分類標(biāo)簽, 將其和模型的分類結(jié)果比較模型在給定(i dn)測(cè)試集上的準(zhǔn)確率是正確被模型分類的測(cè)試樣本的百分比測(cè)試集應(yīng)獨(dú)立于訓(xùn)練集, 否則可能導(dǎo)致過度擬合

3、2022/7/254數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁分類過程 (1): 模型(mxng)創(chuàng)建訓(xùn)練數(shù)據(jù)分類(fn li)算法IF rank = professorOR years 6THEN tenured = yes 分類器(模型)2022/7/255數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁分類過程 (2): 使用(shyng)模型來預(yù)測(cè)分類器測(cè)試數(shù)據(jù)新數(shù)據(jù)(Jeff, Professor, 4)Tenured?2022/7/256數(shù)據(jù)挖掘：概念(ginin)與技術(shù)（翻譯 張磊）共六十八頁有指導(dǎo)(zhdo)的 vs. 無指導(dǎo)的學(xué)習(xí)有指導(dǎo)的學(xué)習(xí) (分類(fn li)指導(dǎo): 模型的

4、學(xué)習(xí)在被告知每個(gè)訓(xùn)練樣本屬于哪個(gè)類的“指導(dǎo)”下進(jìn)行基于訓(xùn)練集對(duì)新數(shù)據(jù)進(jìn)行分類無指導(dǎo)的學(xué)習(xí) (聚類)訓(xùn)練數(shù)據(jù)的類標(biāo)簽是未知的給定一組樣本, 試圖建立分類或數(shù)據(jù)的聚類2022/7/257數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁DM算法-1 分類(fn li)和預(yù)測(cè)什么是分類? 什么是預(yù)測(cè)?關(guān)于分類與預(yù)測(cè)的問題通過(tnggu)決策樹歸納來分類貝葉斯分類通過反向傳播來分類基于關(guān)聯(lián)規(guī)則挖掘的概念來分類其它分類方法預(yù)測(cè)分類準(zhǔn)確率總結(jié)2022/7/258數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁分類與預(yù)測(cè)相關(guān)(xinggun)問題 (1): 數(shù)據(jù)準(zhǔn)備數(shù)據(jù)清洗數(shù)據(jù)準(zhǔn)備是為了減少噪聲數(shù)據(jù), 并處理(ch

5、l)缺失值相關(guān)分析 (特征選取)刪除無關(guān)屬性和冗余屬性數(shù)據(jù)轉(zhuǎn)換數(shù)據(jù)的泛化和歸一化2022/7/259數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁分類與預(yù)測(cè)(yc)的相關(guān)問題 (2): 分類方法的評(píng)估預(yù)測(cè)準(zhǔn)確率速度和擴(kuò)展能力創(chuàng)建模型所需時(shí)間應(yīng)用模型所需時(shí)間健壯性可以處理噪聲和缺失值擴(kuò)展能力在大型數(shù)據(jù)庫上的處理能力可解釋性模型能否增強(qiáng)用戶對(duì)數(shù)據(jù)的理解(lji)和洞察力是否良好的規(guī)則決策樹的大小分類規(guī)則的簡潔程度2022/7/2510數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁DM算法-1 分類(fn li)和預(yù)測(cè)什么是分類? 什么是預(yù)測(cè)?關(guān)于(guny)分類與預(yù)測(cè)的問題通過決策樹歸納來分類貝葉斯分

6、類通過反向傳播來分類基于關(guān)聯(lián)規(guī)則挖掘的概念來分類其它分類方法預(yù)測(cè)分類準(zhǔn)確率總結(jié)2022/7/2511數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁通過決策樹歸納(gun)進(jìn)行分類決策樹 類似于流程圖的樹型結(jié)構(gòu)內(nèi)部節(jié)點(diǎn)代表對(duì)某個(gè)屬性(shxng)的一次測(cè)試分支代表測(cè)試的輸出結(jié)果葉節(jié)點(diǎn)代表分類標(biāo)簽或分布決策樹的生成包括兩個(gè)階段樹的創(chuàng)建首先, 所有訓(xùn)練樣本都位于根節(jié)點(diǎn)遞歸地基于選擇屬性來劃分樣本集樹的修剪識(shí)別并刪除那些反映噪聲或孤立點(diǎn)的分支應(yīng)用決策樹: 對(duì)未知樣本進(jìn)行分類在決策樹上測(cè)試樣本的各個(gè)屬性值2022/7/2512數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁訓(xùn)練(xnlin)數(shù)據(jù)集接下來是Qu

7、inlans ID3算法(sun f)示例2022/7/2513數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁輸出: 預(yù)測(cè)(yc)“是否會(huì)購買計(jì)算機(jī)”的決策樹age?overcaststudent?credit rating?noyesfairexcellent40nonoyesyesyes30.402022/7/2514數(shù)據(jù)挖掘：概念(ginin)與技術(shù)（翻譯 張磊）共六十八頁決策樹歸納(gun)算法基本算法(貪婪算法)樹的創(chuàng)建是一種自頂向下遞歸的分而治之方法首先, 所有訓(xùn)練樣本都位于根節(jié)點(diǎn)屬性都是類別(libi)型變量 (若為連續(xù)值, 則需先離散化)基于選擇的屬性, 對(duì)樣本進(jìn)行遞歸劃分通過啟

8、發(fā)式搜索或統(tǒng)計(jì)量來選取測(cè)試屬性 (例如, 信息增益)停止劃分的條件對(duì)于某個(gè)給定節(jié)點(diǎn), 所有樣本都屬于同一分類沒有剩余屬性可供進(jìn)一步劃分 按照少數(shù)服從多數(shù)的原則來確定葉節(jié)點(diǎn)的分類所有樣本都已分類完畢2022/7/2515數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁屬性(shxng)選取的度量信息增益 (ID3/C4.5)所有屬性應(yīng)為類別型變量可以通過改進(jìn)來處理連續(xù)值屬性Gini索引 (IBM IntelligentMiner)所有屬性應(yīng)為連續(xù)值變量對(duì)于(duy)每個(gè)屬性, 假定已存在若干可能的切分點(diǎn)可能需要其它工具(如聚類)的輔助來獲取切分點(diǎn)可以通過改進(jìn)來處理類別型屬性2022/7/2516數(shù)據(jù)

9、挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁信息(xnx)增益 (ID3/C4.5)選取具有最高信息增益的屬性假定存在兩個(gè)(lin )分類, P 和N樣本集S中包含p個(gè)樣本屬于類別P, n個(gè)樣本屬于類別N用于判別S中任意樣本屬于類別P 或N 的信息量, 定義為2022/7/2517數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁決策樹歸納(gun)中的信息增益假定通過屬性A可以將樣本集S劃分為多個(gè)集合S1, S2 , , Sv 如果Si 包含pi 個(gè)P 類樣本和ni 個(gè)N 類樣本, 熵, 或?qū)所有子樹中的對(duì)象進(jìn)行(jnxng)分類所需的期望信息i 定義為在A上分枝將獲得的編碼信息是2022/7/25

10、18數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁通過計(jì)算信息(xnx)增益來選取屬性類別(libi)P: buys_computer = “yes”類別N: buys_computer = “no”I(p, n) = I(9, 5) =0.940計(jì)算屬性age的熵:因此同樣的2022/7/2519數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁Gini 索引(suyn) (IBM IntelligentMiner)如果數(shù)據(jù)集T 包含n種類別的樣本, gini index, gini(T) 定義如下 其中pj 是類別j 在T 中所占的百分比如果數(shù)據(jù)集T 被劃分為兩個(gè)子集T1 和T2 , 大小分別為N

11、1 和N2, 該劃分的gini index gini(T) 定義為選取具有最小ginisplit(T)的屬性, 對(duì)T進(jìn)行(jnxng)分裂 (對(duì)每個(gè)屬性, 需枚舉出所有可能的切分點(diǎn)).2022/7/2520數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁從樹中抽取(chu q)分類規(guī)則用IF-THEN規(guī)則來作為知識(shí)表示從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每條路徑, 對(duì)于于一條規(guī)則路徑上的每個(gè)(屬性-值)對(duì)被聯(lián)合起來(q li)葉節(jié)點(diǎn)給出了類別預(yù)測(cè)規(guī)則非常易懂示例IF age = “=30” AND student = “no” THEN buys_computer = “no”IF age = “40” AND c

12、redit_rating = “excellent” THEN buys_computer = “yes”IF age = “40” AND credit_rating = “fair” THEN buys_computer = “no”2022/7/2521數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁避免(bmin)分類中的過度訓(xùn)練生成的樹可能會(huì)過度擬合了訓(xùn)練數(shù)據(jù)分支太多, 某些分支其實(shí)反映的是特例(由噪聲數(shù)據(jù)或孤立點(diǎn)引起的)導(dǎo)致預(yù)測(cè)未知樣本的準(zhǔn)確率很差避免過度訓(xùn)練的兩種方法預(yù)修剪: 盡早(jn zo)中止樹的創(chuàng)建當(dāng)某個(gè)分裂會(huì)導(dǎo)致優(yōu)度度量低于給定閾值時(shí), 就不再分裂節(jié)點(diǎn)難于確定合適的閾值后修

13、剪: 從“已長成的” 樹中刪除分支得到多個(gè)修剪后的樹使用與訓(xùn)練數(shù)據(jù)不同的驗(yàn)證集來決定哪個(gè)是“最佳剪枝樹”2022/7/2522數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁決定最終樹大小(dxio)的方法將數(shù)據(jù)集的2/3作為訓(xùn)練集, 1/3作為測(cè)試集使用交叉驗(yàn)證, 例如, 10-fold交叉驗(yàn)證使用全部數(shù)據(jù)來訓(xùn)練但運(yùn)用統(tǒng)計(jì)檢驗(yàn)(例如, chi-square)來估計(jì)對(duì)某個(gè)節(jié)點(diǎn)的分裂或修剪是否能改善整體分布使用最小描述長度(chngd)(MDL)原則: 當(dāng)編碼量達(dá)到最小時(shí)停止樹的生長2022/7/2523數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁決策樹歸納(gun)的改進(jìn)允許處理連續(xù)值屬性動(dòng)態(tài)地對(duì)

14、連續(xù)屬性值離散化(劃分為若干區(qū)間)處理缺失的屬性值賦以最常見的屬性值計(jì)算各種取值的概率屬性創(chuàng)建基于樹中很少出現(xiàn)的那些屬性, 創(chuàng)建新的屬性(例如對(duì)類別型變量分組, 因?yàn)樾畔⒃鲆嫫蛴谌≈刀嗟膶傩?避免碎片(過細(xì)的分支), 重復(fù)(屬性在路徑上被多次測(cè)試)和復(fù)制(fzh)(出現(xiàn)相同子樹)2022/7/2524數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁大型(dxng)數(shù)據(jù)庫中的分類分類對(duì)于分類算法, 很多統(tǒng)計(jì)學(xué)家和機(jī)器學(xué)習(xí)研究者進(jìn)行了廣泛的研究擴(kuò)展性: 對(duì)于具有上百萬的樣本和數(shù)百個(gè)屬性類別的數(shù)據(jù)集, 分類所需時(shí)間可接受為什么要采用決策樹歸納?比較快的學(xué)習(xí)速度 (和其它分類方法相比)可以(ky)轉(zhuǎn)換為

15、簡單易懂的分類規(guī)則可以用SQL查詢來實(shí)現(xiàn)分類準(zhǔn)確率和其它方法相近2022/7/2525數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁DM算法-1 分類(fn li)和預(yù)測(cè)什么是分類? 什么是預(yù)測(cè)?關(guān)于分類與預(yù)測(cè)的問題通過決策樹歸納來分類貝葉斯分類通過反向(fn xin)傳播來分類基于關(guān)聯(lián)規(guī)則挖掘的概念來分類其它分類方法預(yù)測(cè)分類準(zhǔn)確率總結(jié)2022/7/2526數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁貝葉斯分類(fn li): 為什么?概率學(xué)習(xí): 計(jì)算假設(shè)的先驗(yàn)概率, 是處理某些學(xué)習(xí)問題的常見方法遞增的: 每個(gè)訓(xùn)練樣本可以逐步增加/降低假設(shè)正確的概率. 已有知識(shí)可以與觀察數(shù)據(jù)合并.概率預(yù)測(cè): 對(duì)

16、多個(gè)假設(shè)進(jìn)行預(yù)測(cè), 根據(jù)概率賦于不同權(quán)重標(biāo)志的: 盡管貝葉斯分類方法不容易實(shí)施, 它們依然可以提供決策制定的優(yōu)化標(biāo)準(zhǔn)(biozhn), 對(duì)其它方法進(jìn)行評(píng)估2022/7/2527數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁貝葉斯定理(dngl)給定訓(xùn)練數(shù)據(jù)(shj)D, 假設(shè)h 的后驗(yàn)概率, P(h|D) 滿足貝葉斯定理MAP (最大后驗(yàn)概率) 假設(shè)難以實(shí)施: 需要首先知道多個(gè)概率, 計(jì)算開銷大2022/7/2528數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁樸素(p s)貝葉斯分類器 (I)簡化假設(shè): 屬性間彼此條件獨(dú)立:極大(j d)減少了計(jì)算開銷, 只用統(tǒng)計(jì)類別分布即可2022/7/252

17、9數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁樸素(p s)貝葉斯分類器 (II)給定(i dn)一個(gè)訓(xùn)練集, 可以計(jì)算如下概率2022/7/2530數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁貝葉斯分類(fn li)分類問題被形式化為計(jì)算后驗(yàn)概率:計(jì)算P(C|X) = 元組X(=)屬于類別C的概率例如 P(類別=N | outlook=sunny,windy=true,)主要思想: 將樣本(yngbn)X分類到P(C|X)取最大值的類別標(biāo)簽C2022/7/2531數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁后驗(yàn)概率(gil)的估計(jì)貝葉斯定理:P(C|X) = P(X|C)P(C) / P(X

18、)對(duì)于所有類別來說, P(X)是不變的P(C) = 屬于類別C的樣本(yngbn)占總體的比率使得P(C|X)取最大值的類別C = 使得P(X|C)P(C)取最大值的類別C問題: 要計(jì)算P(X|C)并不容易!2022/7/2532數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁樸素(p s)貝葉斯分類樸素假設(shè): 屬性無關(guān)性P(x1,xk|C) = P(x1|C)P(xk|C)如果第i個(gè)屬性是類別型屬性:將P(xi|C)估計(jì)為類別C中第i個(gè)屬性取值為xi的樣本所占百分比如果第i個(gè)屬性是連續(xù)型屬性:將P(xi|C)估計(jì)為其高斯密度函數(shù)(hnsh)兩種情況下都容易計(jì)算出來2022/7/2533數(shù)據(jù)挖掘：

19、概念與技術(shù)（翻譯 張磊）共六十八頁“去不去打網(wǎng)球”示例(shl): 估計(jì)P(xi|C)outlookP(sunny|p) = 2/9P(sunny|n) = 3/5P(overcast|p) = 4/9P(overcast|n) = 0P(rain|p) = 3/9P(rain|n) = 2/5temperatureP(hot|p) = 2/9P(hot|n) = 2/5P(mild|p) = 4/9P(mild|n) = 2/5P(cool|p) = 3/9P(cool|n) = 1/5humidityP(high|p) = 3/9P(high|n) = 4/5P(normal|p) = 6

20、/9P(normal|n) = 2/5windyP(true|p) = 3/9P(true|n) = 3/5P(false|p) = 6/9P(false|n) = 2/5P(p) = 9/14P(n) = 5/142022/7/2534數(shù)據(jù)挖掘：概念(ginin)與技術(shù)（翻譯 張磊）共六十八頁“去不去打網(wǎng)球”示例(shl): 對(duì)X分類未知樣本(yngbn)X = P(X|p)P(p) = P(rain|p)P(hot|p)P(high|p)P(false|p)P(p) = 3/92/93/96/99/14 = 0.010582P(X|n)P(n) = P(rain|n)P(hot|n)P(h

21、igh|n)P(false|n)P(n) = 2/52/54/52/55/14 = 0.018286樣本X被分類為類別n (不去打網(wǎng)球)2022/7/2535數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁無關(guān)(wgun)性假設(shè) 方便了計(jì)算(j sun) 當(dāng)假設(shè)滿足時(shí)可以得到最佳的分類器 但實(shí)際上該假設(shè)很難滿足, 因?yàn)閷傩?變量)常常是相關(guān)的克服限制的做法:貝葉斯網(wǎng)絡(luò), 將貝葉斯推理和屬性間的因果關(guān)系相結(jié)合決策樹, 每次僅對(duì)單個(gè)屬性進(jìn)行判斷, 首先考慮最重要的屬性2022/7/2536數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁貝葉斯信念(xnnin)網(wǎng)絡(luò) (I)家族(jiz)病史肺癌X光透視為+

22、煙民肺氣腫呼吸困難LCLC(FH, S)(FH, S)(FH, S)(FH, S)0.80.20.50.50.70.30.10.9貝葉斯信念網(wǎng)絡(luò)肺癌(LungCancer)變量的條件概率2022/7/2537數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁貝葉斯信念(xnnin)網(wǎng)絡(luò)(II)貝葉斯信念網(wǎng)絡(luò)允許變量子集是條件無關(guān)的因果關(guān)系的圖模型在以下情況下訓(xùn)練貝葉斯信念網(wǎng)絡(luò)(權(quán)重的計(jì)算)給定網(wǎng)狀結(jié)構(gòu)和全部變量: 容易給定網(wǎng)狀結(jié)構(gòu)和部分變量(梯度下降方法(fngf)事先未知網(wǎng)狀結(jié)構(gòu)2022/7/2538數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁DM算法(sun f)-1 分類和預(yù)測(cè)什么(shn m

23、e)是分類? 什么(shn me)是預(yù)測(cè)?關(guān)于分類與預(yù)測(cè)的問題通過決策樹歸納來分類貝葉斯分類通過反向傳播來分類基于關(guān)聯(lián)規(guī)則挖掘的概念來分類其它分類方法預(yù)測(cè)分類準(zhǔn)確率總結(jié)2022/7/2539數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁神經(jīng)網(wǎng)絡(luò)優(yōu)點(diǎn)預(yù)測(cè)準(zhǔn)確率一般較高穩(wěn)定, 可以適應(yīng)包含臟數(shù)據(jù)的訓(xùn)練樣本可以輸出離散(lsn)值, 連續(xù)值, 或者由多個(gè)(離散或連續(xù))屬性組成的向量對(duì)訓(xùn)練好的模型可以快速評(píng)估缺點(diǎn)訓(xùn)練時(shí)間長模型(權(quán)重)難以理解難以結(jié)合領(lǐng)域知識(shí)2022/7/2540數(shù)據(jù)挖掘：概念與技術(shù)(jsh)（翻譯 張磊）共六十八頁神經(jīng)元通過向量(xingling)積和非線性函數(shù), 將n 維輸入向量x

24、映射到向量ymk-f加權(quán)求和輸入向量 x輸出 y激活函數(shù)權(quán)重向量 ww0w1wnx0 x1xn2022/7/2541數(shù)據(jù)挖掘：概念(ginin)與技術(shù)（翻譯 張磊）共六十八頁訓(xùn)練(xnlin)神經(jīng)網(wǎng)絡(luò)訓(xùn)練的最終目標(biāo)得到一組權(quán)重, 使得訓(xùn)練集中的絕大多數(shù)元組可以被正確分類 步驟用隨機(jī)數(shù)來初始化權(quán)重逐個(gè)處理元組, 作為(zuwi)神經(jīng)網(wǎng)絡(luò)的輸入層對(duì)于每個(gè)單元計(jì)算該單元全部輸入的線性組合, 作為其凈輸入使用激活函數(shù)來計(jì)算該單元的輸出值誤差的計(jì)算調(diào)整權(quán)重和偏置2022/7/2542數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁多層感知器輸出(shch) 層節(jié)點(diǎn)輸入(shr)層節(jié)點(diǎn)隱層節(jié)點(diǎn)輸出向量輸入向量

25、: xiwij2022/7/2543數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁網(wǎng)絡(luò)修剪(xijin)與規(guī)則抽取網(wǎng)絡(luò)修剪完全連接的網(wǎng)絡(luò)難以解釋N 個(gè)輸入節(jié)點(diǎn), h 個(gè)隱層節(jié)點(diǎn)和m 個(gè)輸出節(jié)點(diǎn)的網(wǎng)絡(luò)具有h(m+N) 個(gè)權(quán)重修剪: 刪除那些(nxi)對(duì)網(wǎng)絡(luò)分類準(zhǔn)確率影響很小的連接從訓(xùn)練好的神經(jīng)網(wǎng)絡(luò)中抽取規(guī)則對(duì)活躍值進(jìn)行離散化; 用聚類來替代單個(gè)活躍值, 同時(shí)保證一定的網(wǎng)絡(luò)準(zhǔn)確率根據(jù)這些活躍值來枚舉出全部輸出值, 從而可以總結(jié)出活躍值和輸出值間的關(guān)系發(fā)現(xiàn)輸入值和活躍值的關(guān)系綜合以上兩個(gè)步驟, 產(chǎn)生輸入值和輸出值之間的規(guī)則(關(guān)系)2022/7/2544數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁DM算

26、法-1 分類(fn li)和預(yù)測(cè)什么是分類? 什么是預(yù)測(cè)?關(guān)于分類與預(yù)測(cè)的問題通過決策樹歸納來分類貝葉斯分類通過反向傳播來分類基于關(guān)聯(lián)規(guī)則挖掘的概念(ginin)來分類其它分類方法預(yù)測(cè)分類準(zhǔn)確率總結(jié)2022/7/2545數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁其它(qt)分類方法K-近鄰分類器 (k-nearest neighbor classifier )基于案例的推理(tul) (case-based reasoning)遺傳算法 (Genetic algorithm)粗糙集方法 (Rough set approach)模糊集方法 (Fuzzy set approaches)2022/

27、7/2546數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁基于(jy)實(shí)例的方法基于實(shí)例的學(xué)習(xí): 保存訓(xùn)練樣本并延遲處理 (“懶惰的評(píng)估”), 知道需要對(duì)新的實(shí)例進(jìn)行分類時(shí)再進(jìn)行學(xué)習(xí)常見方法k近鄰方法用歐式空間(kngjin)中的點(diǎn)來代表實(shí)例局部加權(quán)回歸構(gòu)造局部估計(jì)值基于案例的推理使用符號(hào)表達(dá)方式和基于知識(shí)的推理2022/7/2547數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁K-近鄰(jn ln)算法所有實(shí)例都對(duì)應(yīng)于n維空間中的點(diǎn)根據(jù)歐式距離來定義(dngy)最近的鄰居目標(biāo)函數(shù)可以輸出離散值或連續(xù)值對(duì)于離散值, k-NN返回xq的k個(gè)近鄰中最常見的值Vonoroi圖: 決策面由某個(gè)典型訓(xùn)練集的

28、1-NN決定. . _+_xq+_+_+.2022/7/2548數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁k-NN算法(sun f)討論k-NN算法對(duì)連續(xù)值的處理計(jì)算k 近鄰的均值加權(quán)距離的近鄰算法根據(jù)每個(gè)鄰居和查詢點(diǎn)xq之間的距離予以加權(quán)越近的鄰居, 權(quán)重越大對(duì)于實(shí)數(shù)值的處理與之類似由于用k個(gè)近鄰來判別(pnbi), 因此在臟數(shù)據(jù)上表現(xiàn)穩(wěn)定維度的負(fù)面影響: 無關(guān)屬性可能會(huì)嚴(yán)重影響距離的準(zhǔn)確計(jì)算可以拉伸坐標(biāo)軸或者除去最不相關(guān)的屬性2022/7/2549數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁基于(jy)案例的推理(CBR)同樣采用: 懶惰評(píng)估 + 分析類似實(shí)例差異: 實(shí)例不再是 “歐式空

29、間中的點(diǎn)”示例: CADET中的水龍頭問題 (Sycara et al92)方法使用符號(hào)描述來表示實(shí)例 (例如, 功能圖)合并多個(gè)檢索出來的案例案例檢索, 基于知識(shí)的推理, 和問題解決的緊密耦合研究問題基于句法相似度的索引技術(shù), 如果解答之間出現(xiàn)不相容，可能需要(xyo)退回搜索其它解2022/7/2550數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁評(píng)論懶惰(lndu)學(xué)習(xí)和積極學(xué)習(xí)基于實(shí)例的學(xué)習(xí): 懶惰評(píng)估 決策樹和貝葉斯分類: 積極學(xué)習(xí)主要差異懶惰方法進(jìn)行決策時(shí)要在訓(xùn)練集D上對(duì)新實(shí)例xq查詢積極方法則不需要, 因?yàn)樗鼈円呀?jīng)有了全局估計(jì)效率: 懶惰學(xué)習(xí) - 訓(xùn)練時(shí)間短, 但預(yù)測(cè)所需時(shí)間長準(zhǔn)確

30、率懶惰方法可以有效利用一個(gè)更廣闊的假設(shè)空間, 因?yàn)椴捎昧硕鄠€(gè)局部線性函數(shù)來構(gòu)造出目標(biāo)(mbio)函數(shù)的全局估計(jì)積極方法: 必須對(duì)整個(gè)實(shí)例空間提交單個(gè)假設(shè), 來覆蓋整個(gè)空間2022/7/2551數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁遺傳算法GA: 基于對(duì)生物進(jìn)化的模擬每個(gè)規(guī)則用位串(string of bits)表達(dá)創(chuàng)建一個(gè)由隨機(jī)產(chǎn)生的規(guī)則組成的初始群體例如, 規(guī)則”IF A1 and Not A2 then C2”, 可被編碼為100 根據(jù)適者生存的原則, 形成由當(dāng)前群體中最適合的規(guī)則組成新的群體, 以及這些規(guī)則的子女規(guī)則的適應(yīng)程度, 用它對(duì)訓(xùn)練樣本集的分類準(zhǔn)確率評(píng)估(pn )子女通過使

31、用諸如交叉和變異等遺傳操作來創(chuàng)建2022/7/2552數(shù)據(jù)挖掘：概念與技術(shù)(jsh)（翻譯 張磊）共六十八頁粗糙集方法(fngf)粗糙集用于近似地(粗糙地)定義等價(jià)類給定類C的粗糙集定義用兩個(gè)集合近似：C的下近似(確定為C類)和C的上近似(不能判斷它不屬于C類)找出最小屬性子集 (用于特征選取) 是NP-難處理的, 但可以使用識(shí)別矩陣(j zhn)存放每對(duì)數(shù)據(jù)樣本屬性值之間的差別, 以降低計(jì)算復(fù)雜度2022/7/2553數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁模糊集方法(fngf)模糊邏輯使用0.0和1.0之間的真值(truth value)表示一個(gè)特定的值屬于給定類的程度，而不是用類或集

32、合的精確截?cái)?(例如使用模糊關(guān)系圖)屬性值被轉(zhuǎn)換為模糊值例如, 將連續(xù)屬性”收入”的值映射(yngsh)到離散分類low, medium, high上, 并計(jì)算模糊成員關(guān)系或真值一個(gè)給定值可以對(duì)應(yīng)多個(gè)模糊值每個(gè)可用規(guī)則對(duì)樣本的分類進(jìn)行投票組合上面得到的和, 得到一個(gè)系統(tǒng)返回的值2022/7/2554數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁DM算法-1 分類(fn li)和預(yù)測(cè)什么是分類? 什么是預(yù)測(cè)?關(guān)于分類與預(yù)測(cè)的問題通過決策樹歸納來分類貝葉斯分類通過反向傳播來分類基于關(guān)聯(lián)規(guī)則挖掘的概念來分類其它(qt)分類方法預(yù)測(cè)分類準(zhǔn)確率總結(jié)2022/7/2555數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共

33、六十八頁什么(shn me)是預(yù)測(cè)?預(yù)測(cè)和分類相似(xin s)首先, 建立一個(gè)模型然后, 使用模型來預(yù)測(cè)未知值主要的預(yù)測(cè)方法是回歸線性和多元回歸非線性回歸預(yù)測(cè)和分類不同分類用于預(yù)測(cè)類別標(biāo)簽預(yù)測(cè)對(duì)連續(xù)函數(shù)建模2022/7/2556數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁建立預(yù)測(cè)模型: 預(yù)測(cè)數(shù)據(jù)的取值, 或者是基于(jy)數(shù)據(jù)庫中的數(shù)據(jù)建立泛化的線性模型只能預(yù)測(cè)值域或類別分布一般步驟: 最小的泛化 屬性相關(guān)分析 創(chuàng)建泛化的線性模型 預(yù)測(cè)識(shí)別出對(duì)預(yù)測(cè)產(chǎn)生影響的主要因子數(shù)據(jù)相關(guān)分析: 不確定性度量, 熵分析, 專家判斷, 等待多層次預(yù)測(cè): 下鉆和上卷分析數(shù)據(jù)庫中建立(jinl)預(yù)測(cè)模型2022/

34、7/2557數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁線性回歸: Y = + X兩個(gè)參數(shù), 和決定一條直線. 可以根據(jù)數(shù)據(jù)估計(jì)出這兩個(gè)參數(shù)的值在已知數(shù)據(jù)Y1, Y2, , X1, X2, 上使用最小二乘法求解多元回歸: Y = b0 + b1 X1 + b2 X2.很多非線性函數(shù)可轉(zhuǎn)換為上述(shngsh)形式對(duì)數(shù)-線性模型:通過低階表的乘積來近似出聯(lián)合概率多路表概率: p(a, b, c, d) = ab acad bcd預(yù)測(cè)中的回歸分析(fnx)和對(duì)數(shù)-線性模型2022/7/2558數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁局部(jb)加權(quán)回歸在查詢(chxn)實(shí)例xq附近的局部區(qū)域創(chuàng)

35、建f 的顯式近似局部加權(quán)線性回歸:在xq附近用線性函數(shù)來近似目標(biāo)函數(shù)f : 最小化平方誤差: 距離遞減的權(quán)重 K梯度下降訓(xùn)練法:大多數(shù)情況下, 目標(biāo)函數(shù)被近似為常數(shù)、線性函數(shù)或二次函數(shù)2022/7/2559數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁預(yù)測(cè)(yc): 數(shù)值型數(shù)據(jù)2022/7/2560數(shù)據(jù)挖掘：概念與技術(shù)(jsh)（翻譯 張磊）共六十八頁預(yù)測(cè)(yc): 類別型數(shù)據(jù)2022/7/2561數(shù)據(jù)挖掘：概念與技術(shù)(jsh)（翻譯 張磊）共六十八頁DM算法-1 分類(fn li)和預(yù)測(cè)什么是分類? 什么是預(yù)測(cè)?關(guān)于分類與預(yù)測(cè)的問題(wnt)通過決策樹歸納來分類貝葉斯分類通過反向傳播來分類基于關(guān)聯(lián)規(guī)則挖掘的概念來分類其它分類方法預(yù)測(cè)分類準(zhǔn)確率總結(jié)2022/7/2562數(shù)據(jù)挖掘：概念與技術(shù)（翻譯 張磊）共六十八頁分類(fn li)準(zhǔn)確率: 錯(cuò)誤率的估計(jì)劃分(hu fn)數(shù)據(jù)集: 訓(xùn)練和測(cè)試使用兩個(gè)獨(dú)立的數(shù)據(jù)集, 例如: 訓(xùn)