數(shù)據(jù)挖掘算法-分類數(shù)據(jù)挖掘資料

1、數(shù)據(jù)挖掘算法(sun f)分類(fn li)數(shù)據(jù)挖掘內容提要分類的概念及其應用分類挖掘的過程與方法基于決策樹的分類挖掘方法ID3方法原理1共二十五頁分類(fn li)（Classification）的概念分類是最常見的數(shù)據(jù)挖掘任務，也是人類眾多規(guī)則之一。學科分類生物分類（瑞典植物學家Carl Linnaeus發(fā)明）分成界、門、綱、目、科、屬、種。動物界，如有脊髓的動物被劃分為脊椎動物門；附加的特征用于將脊椎動物進一步細分為鳥、哺乳動物、爬行動物綱；這些綱進一步細分，直到分類學的最底層。同一種的成員在很多方面存在相似性。如形態(tài)、繁殖等新物種的發(fā)現(xiàn)北京時間12月12日消息(xio xi)，美國時代

2、周刊周二評選出2009年度十大新物種，其中“博薩維毛鼠”位居榜首，迷你霸王龍、重達1噸的史前巨蟒均榜上有名。 2共二十五頁分類(fn li)（Classification）的概念分類包括考察一個新出現(xiàn)的對象的特征，并歸類到已定義類中。在數(shù)據(jù)挖掘中，分類的對象通常是數(shù)據(jù)庫表或文件中的記錄分類工作(gngzu)首先要有一個清晰定義的類注意： 類的個數(shù)是確定的，預先定義好的其次，要有一系列已分類實例3共二十五頁分類(fn li)的應用分類實際上是先建立某種模型，即根據(jù)數(shù)據(jù)集的特點構造一個分類函數(shù)或分類模型。然后將其用于對未分類的數(shù)據(jù)進行分類，即此分類函數(shù)或模型能夠把未知類別的樣本映射到給定的類別之一

3、。分類與預測這是兩種數(shù)據(jù)分析的形式，用來找出模型以描述數(shù)據(jù)或預測未來的變化趨勢。常用于：信譽分析、目標市場、醫(yī)療診斷、性能預測等。如將信用卡申請者分為高、中、低風險發(fā)現(xiàn)欺詐性理賠申請(shnqng)將考生成績分成優(yōu)、良、中、差分類銀行信貸員需要分析資料，弄清楚哪些貸款申請是安全的，哪些是有風險的。故將貸款申請者分為“安全” 和 “有風險” 兩類。預測銀行信貸員需要預測貸款給某個客戶多少錢是安全的。4共二十五頁分類挖掘(wju)的方法要進行分類，就需要有一個分類的規(guī)則。分類的最終結果取決于分類規(guī)則分類的準確度取決于分類規(guī)則的優(yōu)略。規(guī)則很容易用語言表達交流語言（英語、漢語、)結構化語言 if th

4、en程序語言。如SQL在特定的類別(libi)中檢索記錄邏輯表達式分類規(guī)則也可以通過手工的方式辛苦地建立起來，也可以通過某種算法得到。5共二十五頁分類器的構造方法（1）統(tǒng)計方法常見(chn jin)的統(tǒng)計方法有knn算法kNN(k Nearest Neighbors) 假設每一個類包含多個樣本數(shù)據(jù)，而且每個數(shù)據(jù)都有一個唯一的類標記表示這些樣本是屬于哪一個分類， kNN就是計算每個樣本數(shù)據(jù)到待分類數(shù)據(jù)的距離，取與待分類數(shù)據(jù)最近的k各樣本數(shù)據(jù)，那么這個k個樣本數(shù)據(jù)中哪個類別的樣本數(shù)據(jù)占多數(shù)，則待分類數(shù)據(jù)就屬于該類別?；谑吕膶W習方法。6共二十五頁分類器的構造方法（2）機器學習方法決策樹法歸納法（

5、3）神經(jīng)網(wǎng)絡方法神經(jīng)網(wǎng)絡方法主要是BP算法粗糙集(rough set)知識表示是產(chǎn)生式規(guī)則通常，一個分類模型需要在準確度（Accuracy）和透明度之間進行權衡。在某些分類應用中，準確是唯一重要的如郵件分類。通常不關心該模型是如何工作的。在另一些應用中，透明度就顯得(xin de)格外重要。如考試不及格等7共二十五頁分類模型(mxng)的構造過程：兩個階段訓練階段在構造模型前，將數(shù)據(jù)集隨機地分為訓練集和測試數(shù)據(jù)集訓練階段使用訓練數(shù)據(jù)集，通過分析訓練數(shù)據(jù)集的屬性來構造模型假設每個元組屬于一個預定義類，由“類標號”屬性來確定。訓練集中的單個元組稱為訓練樣本, 一個具體樣本的形式可為:( V1, V

6、2, ., Vn; c );其中Vi表示屬性值,c表示類別。由于已提供每個訓練樣本的標號，故稱有指導的學習通常(tngchng)分類模型以分類規(guī)則、判定樹、數(shù)學公式等形式提供測試階段用于評估分類模型的準確率。如果一個分類模型的準確率是可接受的，就可以用此模型來對其他未知類別的元組進行分類8共二十五頁分類的兩個(lin )階段a.模型訓練階段 訓練集b.使用(shyng)模型 分類階段評估準確率（測試集）對類標號未知的新數(shù)據(jù)分類 9共二十五頁資料應用(yngyng)過程舉例訓練樣本婚姻年齡 收入否是否是未婚已婚3535低高否小康1.建立模型測試樣本2. 模型評估X錯誤率為 66.67%修改模型3

7、.使用模型10共二十五頁分類(fn li)的規(guī)范化描述給定數(shù)據(jù)集Dt1,t2,tn，元組tiD，類的集合CC1,Cm，分類問題(wnt)定義為從數(shù)據(jù)集到類集合的映射f：DC，即數(shù)據(jù)集中的元組ti分配到某個類Cj中，有Cj ti|f(ti) = Cj，1in，且tiD。11共二十五頁基于決策樹的分類(fn li)方法決策樹是一種常用的、有力的分類工具。決策樹是一種樹形結構，決策樹包含一系列規(guī)則。通過應用一些簡單的規(guī)則，將大型記錄集分割為小記錄集，通過每一次連續(xù)分割，結果集中的成員彼此變得越來越相似。如生物的分類。“二十問題”游戲就是典型(dinxng)的決策樹分類在游戲中，對第一個問題的回答決定

8、了后續(xù)的提問，前面的問題先創(chuàng)建具有許多成員的寬泛范疇，后續(xù)問題將寬泛范疇分割為越來越小的集合。如果精心挑選所問的問題，也許只需幾個問題就足以得到正確答案。一般情況下，很少超過20個提問。12共二十五頁基于決策樹的分類(fn li)方法“二十問題”游戲說明了用樹來對記錄分類的過程。在根節(jié)點進入然后(rnhu)運用一個規(guī)則來確定接下來進入哪個節(jié)點有很多方法可選，一般情況下，選最能判別的測試規(guī)則上述操作反復進行，直到給定的記錄進入葉節(jié)點為止。所有終結于該樹某個給定葉的記錄，在分類的路線上都是相同的；從根到每個葉只有唯一的路徑，這個路徑就是一個用于分類記錄規(guī)則的表達式需要注意的是，不同的葉可能產(chǎn)生相同

9、的分類，這樣就出現(xiàn)了分類規(guī)則的置信度問題。如蘋果、西紅柿、櫻桃可能被分為“紅色”。但也有綠蘋果、黃西紅柿。13共二十五頁決策樹的類型(lixng)多數(shù)情況下，樹是一個(y )非均勻深度的二元樹即每個葉節(jié)點有兩個子節(jié)點，且葉節(jié)點與根節(jié)點距離并不相同原理上，樹可以有多個分支，如SAS Enterprise Miner就提供多元分支14共二十五頁決策樹的類型(lixng)OutlookovercasthumiditywindyhighnormalfalsetruesunnyrainNNPPPovercast每個樣本有四個屬性，outlook、temperature、humidity和 windy，它

10、們(t men)都是分類屬性，即屬性的取值范圍都是離散值的集合，這里用字符串表示這些離散值。類標號用屬性 play表示，它的取值范圍也是離散值的集合。如果用 dom（A）表示屬性 A的取值范圍，那么，dom（ outlook）=sunny，overcast，rainydom（ temperature）=hot，mild，cooldom（ humidity）=high，normaldom（ windy）=true，falsedom（ play）=yes，no分類算法的目的就是根據(jù)這些訓練樣本建立一棵決策樹，用來預測在各種天氣狀況下是出門玩耍（play=yes），還是呆在家里（play=no）。1

11、5共二十五頁樹的生成(shn chn)盡管目前決策樹的生成算法很多，同一算法也有許多變體，但都基本過程是相同的。相對于目標變量而言，沒有新生節(jié)點比起原生節(jié)點有更高的純度，通過這樣形式，把數(shù)據(jù)重復地拆分為越來越小的群組。建樹的首要任務就是確定哪一個特征（屬性）會產(chǎn)生最佳拆分。最佳拆分是指：能夠把記錄很好地分割為不同的群組，使每個群組里的單個類成為(chngwi)主導。16共二十五頁為了尋找對樣本進行分類的最優(yōu)方法，我們要做的工作就是使對一個樣本分類時需要問的問題最少（即樹的深度最?。Ｒ虼?，我們需要某種函數(shù)來衡量哪些問題將提供(tgng)最為有效的劃分衡量最佳拆分的指標信息增益：Informat

12、ion gain（ID3）增益比率：Gain ration（C4.5）基尼指數(shù)：Gini index (SLIQ，SPRINT)屬性選擇(xunz)度量標準分支指標17共二十五頁ID3的基本(jbn)思想Quinlan于 1979年提出了著名的 ID3方法。以ID3為藍本的C4.5是一個能處理連續(xù)屬性的算法。其他決策樹方法還有ID3的增量版本ID4和ID5等。在此主要介紹 ID3算法。基本思想：在決策樹的各級節(jié)點上選擇屬性時，用信息增益作為選擇標準，以便在對每個非葉節(jié)點進行測試時，獲得最大的類別信息。具體方法檢查所有的屬性，選擇信息增益最大的屬性產(chǎn)生(chnshng)決策樹節(jié)點，由此屬性的不同

13、取值建立分支再對各分支的子集重復上述操作，建立下一層分支，直到所有子集僅包含同一類別的數(shù)據(jù)為止。最后會得到一棵決策樹，用于對新樣本進行分類18共二十五頁信息量設是訓練樣本數(shù)據(jù)集，中類別標識屬性有個獨立的取值，也就是說定義(dngy)了個類C，=，。設S是C類（子集）中樣本數(shù)。集合在分類中的期望信息量為19共二十五頁熵可見，樣本的概率分布越均衡，它的信息量（熵）就越大，樣本集的混雜程度也越高。因此，熵可以作為訓練集的不純度（impurity）的一個度量，熵越大，不純度就越高。這樣，決策樹的分支原則就是使劃分后的樣本的子集(z j)越純越好，即它們的熵越小越好。 設屬性A具有n個取值a1，a2，,

14、an ，可以用屬性A將S劃分(hu fn)為n個子集S1，S2，Sn，設Sij是子集Sj中屬于類Ci的樣本數(shù)，由A劃分成子集的熵20共二十五頁信息(xnx)增益Gain（A）I（S1，S2，,Sm）-E(A)21共二十五頁天氣溫度濕度風況運動晴8585無不適合晴8090有不適合多云8378無適合有雨7096無適合有雨6880無適合有雨6570有不適合多云6465有適合晴7295無不適合晴6970無適合有雨7580無適合晴7570有適合多云7290有適合多云8175無適合有雨7180有不適合實例(shl)122共二十五頁使用信息(xnx)增益進行屬性選擇類C1運動“適合(shh)”，類C2對運動“不適合”I(s1, s2) = I(9, 5) =0.940計算屬性天氣的熵:23共二十五頁決策樹天氣(tinq)?overcast濕度(shd)?風況?75無有天晴有雨不適合不適合不適合適合適合多云24共二十五頁內容摘要數(shù)據(jù)挖掘算法。分類是最常見的數(shù)據(jù)挖掘任務，也是人類眾多規(guī)則之一。附加的特征用于將脊椎動物進一步細分為鳥、哺乳動物、爬行動物綱。分類包括考察一個新出現(xiàn)的對象的特征，并歸類到已定義類中。先建立某種模型(mxng)，