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

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

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

3、號的數(shù)據(jù)進(jìn)行分類。,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,分類和預(yù)測相

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

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,簡單例子,分類 兩歲寶寶，給他看幾個水果，并告訴他：紅的圓的是蘋果，橘黃的圓的是橘子 （建模型） 拿一個水果問寶寶：

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

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

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

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

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

12、計(jì)算 。樣本X被指派到類Ci，當(dāng)且僅當(dāng)： 換言之，X被指派到其 最大的類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é)果較滿意 缺點(diǎn) 假設(shè): 屬性間獨(dú)立, 丟失準(zhǔn)確性 實(shí)際上,

16、 屬性間存在依賴 處理依賴 Bayesian Belief Networks,23,主要內(nèi)容,分類和預(yù)測 貝葉斯分類、神經(jīng)網(wǎng)絡(luò)分類 預(yù)測,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ò)有三個要素：拓?fù)浣Y(jié)構(gòu)、連接方式、學(xué)習(xí)規(guī)則 可以從這三方面對神經(jīng)網(wǎng)絡(luò)進(jìn)行分類,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)簡單的神經(jīng)網(wǎng)絡(luò)，在學(xué)習(xí)時收斂的速度快，但準(zhǔn)確度低。 神經(jīng)網(wǎng)絡(luò)的層數(shù)和每層的單元數(shù)由問題的復(fù)雜程

17、度而定。問題越復(fù)雜，神經(jīng)網(wǎng)絡(luò)的層數(shù)就越多。 例如，兩層神經(jīng)網(wǎng)絡(luò)常用來解決線性問題，而多層網(wǎng)絡(luò)就可以解決多元非線性問題,27,神經(jīng)網(wǎng)絡(luò)的連接,神經(jīng)網(wǎng)絡(luò)的連接：包括層次之間的連接和每一層內(nèi)部的連接，連接的強(qiáng)度用權(quán)來表示。 根據(jù)層次之間的連接方式，分為： 前饋式網(wǎng)絡(luò)：連接是單向的，上層單元的輸出是下層單元的輸入，如反向傳播網(wǎng)絡(luò) 反饋式網(wǎng)絡(luò)：除了單項(xiàng)的連接外，還把最后一層單元的輸出作為第一層單元的輸入，如Hopfield網(wǎng)絡(luò) 根據(jù)連接的范圍，分為： 全連接神經(jīng)網(wǎng)絡(luò)：每個單元和相鄰層上的所有單元相連 局部連接網(wǎng)絡(luò)：每個單元只和相鄰層上的部分單元相連,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)練樣本的類別是已知的，并在學(xué)習(xí)的過程中指導(dǎo)模型的訓(xùn)練 認(rèn)知器：無監(jiān)督的學(xué)習(xí)方法，訓(xùn)練樣本類別未知，各單元通過競爭學(xué)習(xí)。 根據(jù)學(xué)習(xí)時間分： 離線網(wǎng)絡(luò)：學(xué)習(xí)過程和使用過程是獨(dú)立的 在線網(wǎng)絡(luò)：學(xué)習(xí)過程和使用過程是同時進(jìn)行的 根據(jù)學(xué)習(xí)規(guī)則分： 相關(guān)學(xué)習(xí)網(wǎng)絡(luò)：根據(jù)連接間的激活水平改變權(quán)系數(shù) 糾錯學(xué)習(xí)網(wǎng)絡(luò)：根據(jù)輸出單元的外部反饋改變權(quán)系數(shù) 自組織學(xué)習(xí)網(wǎng)絡(luò)：對輸入進(jìn)行自適應(yīng)地學(xué)習(xí),29,基于神經(jīng)網(wǎng)絡(luò)的分類方法,神經(jīng)網(wǎng)絡(luò)經(jīng)常用于分類 神經(jīng)網(wǎng)絡(luò)的分類知識體現(xiàn)在網(wǎng)絡(luò)連接上，被隱式地存儲在連接的權(quán)值中。 神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)就是通過迭代算法，對權(quán)值逐步修改的優(yōu)化過程，學(xué)習(xí)的目標(biāo)就是通過改變權(quán)

19、值使訓(xùn)練集的樣本都能被正確分類。,30,基于神經(jīng)網(wǎng)絡(luò)的分類方法,神經(jīng)網(wǎng)絡(luò)特別適用于下列情況的分類問題： 數(shù)據(jù)量比較小，缺少足夠的樣本建立模型 數(shù)據(jù)的結(jié)構(gòu)難以用傳統(tǒng)的統(tǒng)計(jì)方法來描述 分類模型難以表示為傳統(tǒng)的統(tǒng)計(jì)模型,31,基于神經(jīng)網(wǎng)絡(luò)的分類方法,缺點(diǎn)： 需要很長的訓(xùn)練時間，因而對于有足夠長訓(xùn)練時間的應(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ò)的分類方法,優(yōu)點(diǎn)： 分類的準(zhǔn)確度高 并行分布處理能力強(qiáng) 分布存儲及學(xué)習(xí)能力高 對噪音數(shù)據(jù)有很強(qiáng)的魯棒性和容錯能力 最流行的基于神經(jīng)網(wǎng)絡(luò)的分類算法是80年代提出

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

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

22、，到第一個隱藏層（因此稱作后向傳播）。盡管不能保證，一般地，權(quán)將最終收斂，學(xué)習(xí)過程停止。 算法終止條件：訓(xùn)練集中被正確分類的樣本達(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）。 每個單元都設(shè)有一個偏置（bias），偏置也被初始化為小隨機(jī)數(shù)。 對于每一個樣本X，重復(fù)下面兩步： 向前傳播輸入 向后傳播誤差,40,向前傳播輸入,計(jì)算各層每個單元的輸入和輸出。 輸入層： 輸出=輸入=樣本X的屬性； 即，對于單

23、元j，Oj = Ij = Xj 隱藏層和輸出層： 輸入=前一層的輸出的線性組合, 即，對于單元j， Ij =wij Oi + j i 輸出=,41,向后傳播誤差,計(jì)算各層每個單元的誤差。向后傳播誤差，并更新權(quán)和偏置 計(jì)算各層每個單元的誤差。 輸出層單元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 類標(biāo)號為1,45,主要內(nèi)容,分類和預(yù)測 貝葉斯分類、神經(jīng)網(wǎng)絡(luò)分類 預(yù)測,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