數(shù)據挖掘-分類

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

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

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

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

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

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

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

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

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

12、計算 。樣本X被指派到類Ci，當且僅當： 換言之，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)點 易于實現(xiàn) 多數(shù)情況下結果較滿意 缺點 假設: 屬性間獨立, 丟失準確性 實際上,

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

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

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

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

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

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

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

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

24、 nodes,Input nodes,Hidden nodes,Output vector,Input vector: xi,wij,2020年10月10日星期六,44,Example,設學習率為0.9。訓練樣本X = 1,0,1 類標號為1,45,主要內容,分類和預測 貝葉斯分類、神經網絡分類 預測,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