數(shù)據(jù)挖掘-分類(lèi)

1、1,數(shù)據(jù)挖掘-主要內(nèi)容,分類(lèi)和預(yù)測(cè) 貝葉斯分類(lèi)、神經(jīng)網(wǎng)絡(luò)分類(lèi) 預(yù)測(cè),2,Classification 主要用于對(duì)離散的數(shù)據(jù)進(jìn)行預(yù)測(cè) 分為兩步： 根據(jù)訓(xùn)練集，構(gòu)造分類(lèi)模型（訓(xùn)練集中每個(gè)元組的分類(lèi)標(biāo)號(hào)事先已經(jīng)知道） 估計(jì)分類(lèi)模型的準(zhǔn)確性，如果其準(zhǔn)確性可以接受的話(huà)，則利用它來(lái)對(duì)未來(lái)數(shù)據(jù)進(jìn)行分類(lèi) Prediction： 構(gòu)造、使用模型來(lái)對(duì)某個(gè)樣本的值進(jìn)行估計(jì)，例如預(yù)測(cè)某個(gè)不知道的值或者缺失值 主要用于對(duì)連續(xù)或有序的數(shù)據(jù)進(jìn)行預(yù)測(cè) Typical applications 信譽(yù)評(píng)估 醫(yī)學(xué)診斷 性能預(yù)測(cè),Classification vs. Prediction,3,ClassificationA Two-

2、Step Process,模型構(gòu)造階段: describing a set of predetermined classes 假定每個(gè)元組/樣本都屬于某個(gè)預(yù)定義的類(lèi)，這些類(lèi)由分類(lèi)標(biāo)號(hào)屬性所定義 用來(lái)構(gòu)造模型的元組/樣本集被稱(chēng)為訓(xùn)練集（training set） 模型一般表示為：分類(lèi)規(guī)則, 決策樹(shù)或者數(shù)學(xué)公式 模型使用階段: for classifying future or unknown objects 估計(jì)模型的準(zhǔn)確性 用一些已知分類(lèi)標(biāo)號(hào)的測(cè)試集和由模型進(jìn)行分類(lèi)的結(jié)果進(jìn)行比較 兩個(gè)結(jié)果相同所占的比率稱(chēng)為準(zhǔn)確率 測(cè)試集和訓(xùn)練集必須不相關(guān) 如果準(zhǔn)確性可以接受的話(huà), 使用模型來(lái)對(duì)那些不知道分類(lèi)標(biāo)

3、號(hào)的數(shù)據(jù)進(jìn)行分類(lèi)。,4,Classification Process (1): Model Construction,Training Data,Classification Algorithms,IF rank = professor OR years 6 THEN tenured = yes,Classifier (Model),5,Classification Process (2): Use the Model in Prediction,Classifier,Testing Data,Unseen Data,(Jeff, Professor, 4),Tenured?,6,分類(lèi)和預(yù)測(cè)相

4、關(guān)問(wèn)題 (1): 數(shù)據(jù)預(yù)處理,數(shù)據(jù)清洗 對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，去掉噪聲，對(duì)缺失數(shù)據(jù)進(jìn)行處理（用某個(gè)最常用的值代替或者根據(jù)統(tǒng)計(jì)用某個(gè)最可能的值代替） 相關(guān)分析 (特征選擇) 去掉某些不相關(guān)的或者冗余的屬性 數(shù)據(jù)轉(zhuǎn)換 對(duì)數(shù)據(jù)進(jìn)行概括（如將連續(xù)的值離散成若干個(gè)區(qū)域，將街道等上升到城市） 對(duì)數(shù)據(jù)進(jìn)行規(guī)范化，將某個(gè)屬性的值縮小到某個(gè)指定的范圍之內(nèi),7,分類(lèi)和預(yù)測(cè)相關(guān)問(wèn)題 (2): 對(duì)分類(lèi)方法進(jìn)行評(píng)價(jià),準(zhǔn)確性: 分類(lèi)準(zhǔn)確性和預(yù)測(cè)準(zhǔn)確性 速度和可伸縮性 構(gòu)造模型的時(shí)間 (訓(xùn)練時(shí)間) 使用模型的時(shí)間 (分類(lèi)/預(yù)測(cè)時(shí)間) 魯棒性 能夠處理噪聲和缺失數(shù)據(jù) 可伸縮性 對(duì)磁盤(pán)級(jí)的數(shù)據(jù)庫(kù)有效 易交互性 模型容易理解，具有較

5、好的洞察力,2020年10月10日星期六,8,Visualization of a Decision Tree in SGI/MineSet 3.0,9,Supervised vs. Unsupervised Learning,Supervised learning (classification) Supervision: The training data (observations, measurements, etc.) are accompanied by labels indicating the class of the observations New data is clas

6、sified based on the training set Unsupervised learning (clustering) The class labels of training data is unknown Given a set of measurements, observations, etc. with the aim of establishing the existence of classes or clusters in the data,10,簡(jiǎn)單例子,分類(lèi) 兩歲寶寶，給他看幾個(gè)水果，并告訴他：紅的圓的是蘋(píng)果，橘黃的圓的是橘子 （建模型） 拿一個(gè)水果問(wèn)寶寶：

7、這個(gè)水果，紅的圓的，是什么？（用模型） 聚類(lèi) 兩歲寶寶，給他一堆水果，告訴他：根據(jù)顏色分成兩堆。寶寶會(huì)將蘋(píng)果分成一堆，橘子分成一堆。假如告訴他：根據(jù)大小分成3堆，則寶寶會(huì)根據(jù)大小分成3堆，蘋(píng)果和橘子可能會(huì)放在一起。,11,主要內(nèi)容,分類(lèi)和預(yù)測(cè) 貝葉斯分類(lèi)、神經(jīng)網(wǎng)絡(luò)分類(lèi) 預(yù)測(cè),12,Bayesian Classification,是一種基于統(tǒng)計(jì)的分類(lèi)方法，用來(lái)預(yù)測(cè)諸如某個(gè)樣本屬于某個(gè)分類(lèi)的概率有多大 基于Bayes理論 研究發(fā)現(xiàn)， Nave Bayes Classifier在性能上和Decision Tree、Neural Network classifiers 相當(dāng)。在應(yīng)用于大數(shù)據(jù)集時(shí)，具有較

8、高的準(zhǔn)確率和速度 Nave Bayes Classifier假設(shè)屬性值之間是獨(dú)立的，因此可以簡(jiǎn)化很多計(jì)算，故稱(chēng)之為Nave 。當(dāng)屬性值之間有依賴(lài)關(guān)系時(shí)，采用Bayesian Belief Networks進(jìn)行分類(lèi)。,13,Bayesian Theorem: Basics,假設(shè)X是未知分類(lèi)標(biāo)號(hào)的樣本數(shù)據(jù) H代表某種假設(shè)，例如X屬于分類(lèi)C P(H|X): 給定樣本數(shù)據(jù)X，假設(shè) H成立的概率 例如，假設(shè)樣本數(shù)據(jù)由各種水果組成，每種水果都可以用形狀和顏色來(lái)描述。如果用X代表紅色并且是圓的，H代表X屬于蘋(píng)果這個(gè)假設(shè)，則P(H|X)表示，已知X是紅色并且是圓的，則X是蘋(píng)果的概率。,14,Bayesian

9、Theorem: Basics,P(H): 拿出任一個(gè)水果，不管它什么顏色，也不管它什么形狀，它屬于蘋(píng)果的概率 P(X):拿出任一個(gè)水果，不管它是什么水果，它是紅色并且是圓的概率 P(X|H) : 一個(gè)水果，已知它是一個(gè)蘋(píng)果，則它是紅色并且是圓的概率。,15,Bayesian Theorem: Basics,現(xiàn)在的問(wèn)題是，知道數(shù)據(jù)集里每個(gè)水果的顏色和形狀，看它屬于什么水果，求出屬于每種水果的概率，選其中概率最大的。也就是要算： P(H|X) 但事實(shí)上，其他三個(gè)概率， P(H)、 P(X)、 P(X|H) 都可以由已知數(shù)據(jù)得出，而P(H|X)無(wú)法從已知數(shù)據(jù)得出 Bayes理論可以幫助我們：,16

10、,Nave Bayes Classifier,每個(gè)數(shù)據(jù)樣本用一個(gè)n維特征向量表示，描述由屬性對(duì)樣本的n個(gè)度量。 假定有m個(gè)類(lèi)。給定一個(gè)未知的數(shù)據(jù)樣本X（即，沒(méi)有類(lèi)標(biāo)號(hào)），分類(lèi)法將預(yù)測(cè)X屬于具有最高后驗(yàn)概率（條件X下）的類(lèi)。即，樸素貝葉斯分類(lèi)將未知的樣本分配給類(lèi)Ci ，當(dāng)且僅當(dāng)： 這樣，我們最大化 。其最大的類(lèi)Ci稱(chēng)為最大后驗(yàn)假定。根據(jù)貝葉斯定理:,17,Nave Bayes Classifier,由于P(X) 對(duì)于所有類(lèi)為常數(shù)，只需要 最大即可。如果類(lèi)的先驗(yàn)概率未知，則通常假定這些類(lèi)是等概率的；即， 。并據(jù)此只對(duì) 最大化。否則，我們最大化 。類(lèi)的先驗(yàn)概率可以用 計(jì)算；其中，si是類(lèi)C中的訓(xùn)練樣

11、本數(shù)，而s是訓(xùn)練樣本總數(shù)。,18,Nave Bayes Classifier,給定具有許多屬性的數(shù)據(jù)集，計(jì)算 的開(kāi)銷(xiāo)可能非常大。為降低計(jì)算的開(kāi)銷(xiāo)，可以樸素地假設(shè)屬性間不存在依賴(lài)關(guān)系。這樣， 概率 , , 可以由訓(xùn)練樣本估計(jì)，其中， (a)如果Ak是分類(lèi)屬性，則 ；其中sik 是在屬性Ak 上具有值xk 的類(lèi)Ci 的訓(xùn)練樣本數(shù)，而si 是Ci中的訓(xùn)練樣本數(shù) (b)如果是連續(xù)值屬性，則通常假定該屬性服從高斯分布。因而， 其中，給定類(lèi)Ci的訓(xùn)練樣本屬性Ak的值， 是屬性Ak的高斯密度函數(shù)，而 分別為平均值和標(biāo)準(zhǔn)差。,19,Nave Bayes Classifier,為對(duì)未知樣本X分類(lèi)，對(duì)每個(gè)類(lèi)Ci，

12、計(jì)算 。樣本X被指派到類(lèi)Ci，當(dāng)且僅當(dāng)： 換言之，X被指派到其 最大的類(lèi)Ci。,20,Training dataset,Class: C1:buys_computer= yes C2:buys_computer= no Data sample X =(age=30, Income=medium, Student=yes Credit_rating= Fair),21,Nave Bayesian Classifier: An Example,Compute P(X|Ci) for each class P(buys_computer=“yes”) = 9/14=0.643 P(buys_comp

13、uter=“no”) = 5/14=0.357 P(age=“30” | buys_computer=“yes”) = 2/9=0.222 P(age=“30” | buys_computer=“no”) = 3/5 =0.6 P(income=“medium” | buys_computer=“yes”)= 4/9 =0.444 P(income=“medium” | buys_computer=“no”) = 2/5 = 0.4 P(student=“yes” | buys_computer=“yes)= 6/9 =0.667 P(student=“yes” | buys_computer

14、=“no”)= 1/5=0.2 P(credit_rating=“fair” | buys_computer=“yes”)=6/9=0.667 P(credit_rating=“fair” | buys_computer=“no”)=2/5=0.4 X=(age=30 , income =medium, student=yes, credit_rating=fair) P(X|Ci) : P(X|buys_computer=“yes”)= 0.222 x 0.444 x 0.667 x 0.667 =0.044 P(X|buys_computer=“no”)= 0.6 x 0.4 x 0.2

15、x 0.4 =0.019 P(X|Ci)*P(Ci ) : P(X|buys_computer=“yes”) * P(buys_computer=“yes”)=0.044 x 0.643=0.028 P(X|buys_computer=“no”) * P(buys_computer=“no”)= 0.019 x 0.357=0.007 Therefore, X belongs to class “buys_computer=yes”,22,Nave Bayesian Classifier: Comments,優(yōu)點(diǎn) 易于實(shí)現(xiàn) 多數(shù)情況下結(jié)果較滿(mǎn)意 缺點(diǎn) 假設(shè): 屬性間獨(dú)立, 丟失準(zhǔn)確性 實(shí)際上,

16、 屬性間存在依賴(lài) 處理依賴(lài) Bayesian Belief Networks,23,主要內(nèi)容,分類(lèi)和預(yù)測(cè) 貝葉斯分類(lèi)、神經(jīng)網(wǎng)絡(luò)分類(lèi) 預(yù)測(cè),24,神經(jīng)網(wǎng)絡(luò),神經(jīng)網(wǎng)絡(luò)是以模擬人腦神經(jīng)元的數(shù)學(xué)模型為基礎(chǔ)而建立的，它由一系列神經(jīng)元組成，單元之間彼此連接。,25,神經(jīng)網(wǎng)絡(luò),神經(jīng)網(wǎng)絡(luò)有三個(gè)要素：拓?fù)浣Y(jié)構(gòu)、連接方式、學(xué)習(xí)規(guī)則 可以從這三方面對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行分類(lèi),26,神經(jīng)網(wǎng)絡(luò)的拓?fù)?神經(jīng)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)：神經(jīng)網(wǎng)絡(luò)的單元通常按照層次排列，根據(jù)網(wǎng)絡(luò)的層次數(shù)，可以將神經(jīng)網(wǎng)絡(luò)分為單層神經(jīng)網(wǎng)絡(luò)、兩層神經(jīng)網(wǎng)絡(luò)、三層神經(jīng)網(wǎng)絡(luò)等 結(jié)構(gòu)簡(jiǎn)單的神經(jīng)網(wǎng)絡(luò)，在學(xué)習(xí)時(shí)收斂的速度快，但準(zhǔn)確度低。 神經(jīng)網(wǎng)絡(luò)的層數(shù)和每層的單元數(shù)由問(wèn)題的復(fù)雜程

17、度而定。問(wèn)題越復(fù)雜，神經(jīng)網(wǎng)絡(luò)的層數(shù)就越多。 例如，兩層神經(jīng)網(wǎng)絡(luò)常用來(lái)解決線(xiàn)性問(wèn)題，而多層網(wǎng)絡(luò)就可以解決多元非線(xiàn)性問(wèn)題,27,神經(jīng)網(wǎng)絡(luò)的連接,神經(jīng)網(wǎng)絡(luò)的連接：包括層次之間的連接和每一層內(nèi)部的連接，連接的強(qiáng)度用權(quán)來(lái)表示。 根據(jù)層次之間的連接方式，分為： 前饋式網(wǎng)絡(luò)：連接是單向的，上層單元的輸出是下層單元的輸入，如反向傳播網(wǎng)絡(luò) 反饋式網(wǎng)絡(luò)：除了單項(xiàng)的連接外，還把最后一層單元的輸出作為第一層單元的輸入，如Hopfield網(wǎng)絡(luò) 根據(jù)連接的范圍，分為： 全連接神經(jīng)網(wǎng)絡(luò)：每個(gè)單元和相鄰層上的所有單元相連 局部連接網(wǎng)絡(luò)：每個(gè)單元只和相鄰層上的部分單元相連,28,神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí),神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí) 根據(jù)學(xué)習(xí)方法分：

18、 感知器：有監(jiān)督的學(xué)習(xí)方法，訓(xùn)練樣本的類(lèi)別是已知的，并在學(xué)習(xí)的過(guò)程中指導(dǎo)模型的訓(xùn)練 認(rèn)知器：無(wú)監(jiān)督的學(xué)習(xí)方法，訓(xùn)練樣本類(lèi)別未知，各單元通過(guò)競(jìng)爭(zhēng)學(xué)習(xí)。 根據(jù)學(xué)習(xí)時(shí)間分： 離線(xiàn)網(wǎng)絡(luò)：學(xué)習(xí)過(guò)程和使用過(guò)程是獨(dú)立的 在線(xiàn)網(wǎng)絡(luò)：學(xué)習(xí)過(guò)程和使用過(guò)程是同時(shí)進(jìn)行的 根據(jù)學(xué)習(xí)規(guī)則分： 相關(guān)學(xué)習(xí)網(wǎng)絡(luò)：根據(jù)連接間的激活水平改變權(quán)系數(shù) 糾錯(cuò)學(xué)習(xí)網(wǎng)絡(luò)：根據(jù)輸出單元的外部反饋改變權(quán)系數(shù) 自組織學(xué)習(xí)網(wǎng)絡(luò)：對(duì)輸入進(jìn)行自適應(yīng)地學(xué)習(xí),29,基于神經(jīng)網(wǎng)絡(luò)的分類(lèi)方法,神經(jīng)網(wǎng)絡(luò)經(jīng)常用于分類(lèi) 神經(jīng)網(wǎng)絡(luò)的分類(lèi)知識(shí)體現(xiàn)在網(wǎng)絡(luò)連接上，被隱式地存儲(chǔ)在連接的權(quán)值中。 神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)就是通過(guò)迭代算法，對(duì)權(quán)值逐步修改的優(yōu)化過(guò)程，學(xué)習(xí)的目標(biāo)就是通過(guò)改變權(quán)

19、值使訓(xùn)練集的樣本都能被正確分類(lèi)。,30,基于神經(jīng)網(wǎng)絡(luò)的分類(lèi)方法,神經(jīng)網(wǎng)絡(luò)特別適用于下列情況的分類(lèi)問(wèn)題： 數(shù)據(jù)量比較小，缺少足夠的樣本建立模型 數(shù)據(jù)的結(jié)構(gòu)難以用傳統(tǒng)的統(tǒng)計(jì)方法來(lái)描述 分類(lèi)模型難以表示為傳統(tǒng)的統(tǒng)計(jì)模型,31,基于神經(jīng)網(wǎng)絡(luò)的分類(lèi)方法,缺點(diǎn)： 需要很長(zhǎng)的訓(xùn)練時(shí)間，因而對(duì)于有足夠長(zhǎng)訓(xùn)練時(shí)間的應(yīng)用更合適。 需要大量的參數(shù)，這些通常主要靠經(jīng)驗(yàn)確定，如網(wǎng)絡(luò)拓?fù)洹?可解釋性差。該特點(diǎn)使得神經(jīng)網(wǎng)絡(luò)在數(shù)據(jù)挖掘的初期并不看好。,32,基于神經(jīng)網(wǎng)絡(luò)的分類(lèi)方法,優(yōu)點(diǎn)： 分類(lèi)的準(zhǔn)確度高 并行分布處理能力強(qiáng) 分布存儲(chǔ)及學(xué)習(xí)能力高 對(duì)噪音數(shù)據(jù)有很強(qiáng)的魯棒性和容錯(cuò)能力 最流行的基于神經(jīng)網(wǎng)絡(luò)的分類(lèi)算法是80年代提出

20、的后向傳播算法。,33,后向傳播算法,后向傳播算法在多路前饋神經(jīng)網(wǎng)絡(luò)上學(xué)習(xí)。,34,定義網(wǎng)絡(luò)拓?fù)?在開(kāi)始訓(xùn)練之前，用戶(hù)必須說(shuō)明輸入層的單元數(shù)、隱藏層數(shù)（如果多于一層）、每一隱藏層的單元數(shù)和輸出層的單元數(shù)，以確定網(wǎng)絡(luò)拓?fù)洹?35,定義網(wǎng)絡(luò)拓?fù)?對(duì)訓(xùn)練樣本中每個(gè)屬性的值進(jìn)行規(guī)格化將有助于加快學(xué)習(xí)過(guò)程。通常，對(duì)輸入值規(guī)格化，使得它們落入0.0和1.0之間。 離散值屬性可以重新編碼，使得每個(gè)域值一個(gè)輸入單元。例如，如果屬性A的定義域?yàn)?a0 ,a1 ,a2)，則可以分配三個(gè)輸入單元表示A。即，我們可以用I0 ,I1 ,I2作為輸入單元。每個(gè)單元初始化為0。如果A = a0，則I0置為1；如果A = a

21、1，I1置1；如此下去。 一個(gè)輸出單元可以用來(lái)表示兩個(gè)類(lèi)（值1代表一個(gè)類(lèi)，而值0代表另一個(gè)）。如果多于兩個(gè)類(lèi)，則每個(gè)類(lèi)使用一個(gè)輸出單元。,36,定義網(wǎng)絡(luò)拓?fù)?隱藏層單元數(shù)設(shè)多少個(gè)“最好” ，沒(méi)有明確的規(guī)則。 網(wǎng)絡(luò)設(shè)計(jì)是一個(gè)實(shí)驗(yàn)過(guò)程，并可能影響準(zhǔn)確性。權(quán)的初值也可能影響準(zhǔn)確性。如果某個(gè)經(jīng)過(guò)訓(xùn)練的網(wǎng)絡(luò)的準(zhǔn)確率太低，則通常需要采用不同的網(wǎng)絡(luò)拓?fù)浠蚴褂貌煌某跏紮?quán)值，重復(fù)進(jìn)行訓(xùn)練。,37,后向傳播算法,后向傳播算法學(xué)習(xí)過(guò)程： 迭代地處理一組訓(xùn)練樣本，將每個(gè)樣本的網(wǎng)絡(luò)預(yù)測(cè)與實(shí)際的類(lèi)標(biāo)號(hào)比較。 每次迭代后，修改權(quán)值，使得網(wǎng)絡(luò)預(yù)測(cè)和實(shí)際類(lèi)之間的均方差最小。 這種修改“后向”進(jìn)行。即，由輸出層，經(jīng)由每個(gè)隱藏層

22、，到第一個(gè)隱藏層（因此稱(chēng)作后向傳播）。盡管不能保證，一般地，權(quán)將最終收斂，學(xué)習(xí)過(guò)程停止。 算法終止條件：訓(xùn)練集中被正確分類(lèi)的樣本達(dá)到一定的比例，或者權(quán)系數(shù)趨近穩(wěn)定。,38,后向傳播算法,后向傳播算法分為如下幾步： 初始化權(quán) 向前傳播輸入 向后傳播誤差,39,后向傳播算法,初始化權(quán) 網(wǎng)絡(luò)的權(quán)通常被初始化為很小的隨機(jī)數(shù)（例如，范圍從-1.0到1.0，或從-0.5到0.5）。 每個(gè)單元都設(shè)有一個(gè)偏置（bias），偏置也被初始化為小隨機(jī)數(shù)。 對(duì)于每一個(gè)樣本X，重復(fù)下面兩步： 向前傳播輸入 向后傳播誤差,40,向前傳播輸入,計(jì)算各層每個(gè)單元的輸入和輸出。 輸入層： 輸出=輸入=樣本X的屬性； 即，對(duì)于單

23、元j，Oj = Ij = Xj 隱藏層和輸出層： 輸入=前一層的輸出的線(xiàn)性組合, 即，對(duì)于單元j， Ij =wij Oi + j i 輸出=,41,向后傳播誤差,計(jì)算各層每個(gè)單元的誤差。向后傳播誤差，并更新權(quán)和偏置 計(jì)算各層每個(gè)單元的誤差。 輸出層單元j，誤差 Oj是單元j的實(shí)際輸出，而Tj是j的真正輸出。 隱藏層單元j，誤差 wjk是由j到下一層中單元k的連接的權(quán) Errk是單元k的誤差,42,向后傳播誤差,更新權(quán)和偏差，以反映傳播的誤差。 權(quán)由下式更新： 其中，wij是權(quán)wij的改變。l是學(xué)習(xí)率，通常取0和1之間的值。 偏置由下式更新： 其中，j是偏置j的改變。,后向傳播算法,Output

24、 nodes,Input nodes,Hidden nodes,Output vector,Input vector: xi,wij,2020年10月10日星期六,44,Example,設(shè)學(xué)習(xí)率為0.9。訓(xùn)練樣本X = 1,0,1 類(lèi)標(biāo)號(hào)為1,45,主要內(nèi)容,分類(lèi)和預(yù)測(cè) 貝葉斯分類(lèi)、神經(jīng)網(wǎng)絡(luò)分類(lèi) 預(yù)測(cè),46,What Is Prediction?,Prediction is similar to classification First, construct a model Second, use model to predict unknown value Major method for prediction: regression Linear and multiple regression Non-linear regression Prediction is differ