分類算法綜述

1、TAIYUANUNIVERSITYOFTECHNOLOGY數(shù)據(jù)挖掘數(shù)據(jù)挖掘分類算法綜述專業(yè)：計算機(jī)科學(xué)與技術(shù)專業(yè)學(xué)號：S20100451姓名：張靖指導(dǎo)教師：陳俊杰時間：2011年08月21日數(shù)據(jù)挖掘分類算法綜述數(shù)據(jù)挖掘出現(xiàn)于20世紀(jì)80年代后期，是數(shù)據(jù)庫研究中最有應(yīng)用價值的新領(lǐng)域之一。它最早是以從數(shù)據(jù)中發(fā)現(xiàn)知識（KDD,KnowledgeDiscoveryinDatabase）研究起步，所謂的數(shù)據(jù)挖掘（DataMining,簡稱為DM）,就從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的、實際應(yīng)用的數(shù)據(jù)中提取隱含在其中的、人們不知道的但又有用的信息和知識的過程。分類是一種重要的數(shù)據(jù)挖掘技術(shù)。分類的

2、目的是根據(jù)數(shù)據(jù)集的特點構(gòu)造一個分類函數(shù)或分類模型（也常常稱作分類器）。該模型能把未知類別的樣本映射到給定類別中的一種技術(shù)。1.分類的基本步驟數(shù)據(jù)分類過程主要包含兩個步驟：第一步，建立一個描述已知數(shù)據(jù)集類別或概念的模型。如圖1所示，該模型是通過對數(shù)據(jù)庫中各數(shù)據(jù)行內(nèi)容的分析而獲得的。每一數(shù)據(jù)行都可認(rèn)為是屬于一個確定的數(shù)據(jù)類別，其類別值是由一個屬性描述（被稱為類別屬性）。分類學(xué)習(xí)方法所使用的數(shù)據(jù)集稱為訓(xùn)練樣本集合，因此分類學(xué)習(xí)又可以稱為有指導(dǎo)學(xué)習(xí)（learningbyexample）。它是在已知訓(xùn)練樣本類別情況下，通過學(xué)習(xí)建立相應(yīng)模型，而無指導(dǎo)學(xué)習(xí)則是在訓(xùn)練樣本的類別與類別個數(shù)均未知的情況下進(jìn)行的。

3、通常分類學(xué)習(xí)所獲得的模型可以表示為分類規(guī)則形式、決策樹形式或數(shù)學(xué)公式形式。例如，給定一個顧客信用信息數(shù)據(jù)庫，通過學(xué)習(xí)所獲得的分類規(guī)則可用于識別顧客是否是具有良好的信用等級或一般的信用等級。分類規(guī)則也可用于對今后未知所屬類別的數(shù)據(jù)進(jìn)行識別判斷，同時也可以幫助用戶更好的了解數(shù)據(jù)庫中的內(nèi)容。訓(xùn)練數(shù)據(jù)nameageincomeCredit_ratingSandyJones芻0lowfairBilllee毯0lowexcellentCourtneyfox3140highexcellentSusanlake>40medfairClairephips>40medfairAndrebeau3140

4、highexcellentIfage="31-40”andincome=highThencredit_rating=excellent圖1數(shù)據(jù)分類過程中的學(xué)習(xí)建模第二步，利用所獲得的模型進(jìn)行分類操作。首先對模型分類準(zhǔn)確率進(jìn)行估計，例如使用保持（holdout）方法。如果一個學(xué)習(xí)所獲模型的準(zhǔn)確率經(jīng)測試被認(rèn)為是可以接受的，那么就可以使用這一模型對未來數(shù)據(jù)行或?qū)ο螅ㄆ漕悇e未知）進(jìn)行分類。例如，在圖2中利用學(xué)習(xí)獲得的分類規(guī)則（模型）。對已知測試數(shù)據(jù)進(jìn)行模型準(zhǔn)確率的評估，以及對未知類別的新數(shù)據(jù)進(jìn)行分類預(yù)測。nameageincomeCredit_ratingSandyJones封0lowfai

5、rBilllee90lowexcellentCourtneyfox3140highexcellentSusanlake>40medfairClairephips>40medfairAndrebeau31-40.highexcellent|JohnHenri|3041high|圖2數(shù)據(jù)分類過程中的分類測試分類的具體規(guī)則可描述如下：給定一組訓(xùn)練數(shù)據(jù)的集合T(Trainingset),由一條條的數(shù)據(jù)庫記錄(Record)組成的，T的每一條記錄包含若干條屬性(Attribute)組成一個特征向量，用矢量X=區(qū)2，,4)表示，其中Xi(14iwn)對應(yīng)各非類別屬性，可以有不同的值域，當(dāng)一屬性

6、的值域為連續(xù)域時，該屬性為連續(xù)屬性(NumericalAttribute),否則為離散屬性(DiscreteAttribute),用c表示類別屬性c=(g,C2,Ck),即數(shù)據(jù)集有k個不同的類別，那么，T就隱含了一個從矢量X到類別屬性的映射函數(shù)H:f(X)tc。分類的目的就是分析輸入數(shù)據(jù)，通過在訓(xùn)練集中的數(shù)據(jù)表現(xiàn)出來的特性，為每一個類找到一種準(zhǔn)確的描述或者模型，采用該種方法(模型)將隱含函數(shù)表示出來。構(gòu)造分類模型的過程一般分為訓(xùn)練和測試兩個階段，在構(gòu)造模型之前，要求將數(shù)據(jù)集隨機(jī)地分為訓(xùn)練數(shù)據(jù)集和測試數(shù)據(jù)集。在訓(xùn)練階段，使用訓(xùn)練數(shù)據(jù)集通過分析有屬性描述的數(shù)據(jù)庫元組來構(gòu)造模型。在測試階段，使用測試

7、數(shù)據(jù)集，來評估模型的分類準(zhǔn)確率，如果認(rèn)為模型的準(zhǔn)確率可以接受，就可以用該模型對其它數(shù)據(jù)元組進(jìn)分類，一般來說，測試階段的代價遠(yuǎn)遠(yuǎn)低于訓(xùn)練階段。2 .分類數(shù)據(jù)的預(yù)處理為了提高分類的準(zhǔn)確性、有效性和可伸縮性，在進(jìn)行分類之前通常要對數(shù)據(jù)進(jìn)行預(yù)處理，包括以下幾方面：(1)數(shù)據(jù)清理大多數(shù)數(shù)據(jù)預(yù)處理是數(shù)據(jù)清理的一種形式，其目的是消除或減少數(shù)據(jù)噪聲和處理缺失數(shù)據(jù)的信息。噪聲代表屬性值中的隨機(jī)錯誤。在所有大的數(shù)據(jù)集中噪聲以各種形式和排列方式出現(xiàn)，對噪聲數(shù)據(jù)通常關(guān)心的問題如下：發(fā)現(xiàn)重復(fù)記錄。查找錯誤的屬性值。在分類數(shù)據(jù)中尋找錯誤是大型數(shù)據(jù)集所面臨的一個問題。一些數(shù)據(jù)挖掘工具提供了頻率值或分類屬性的預(yù)測能力值的匯總

8、，可以認(rèn)為預(yù)測能力值接近于0的屬性值可能是錯誤的。數(shù)據(jù)平滑。數(shù)據(jù)平滑是一個數(shù)據(jù)清理和數(shù)據(jù)轉(zhuǎn)換的過程。一些數(shù)據(jù)平滑技術(shù)努力減少數(shù)值屬性值的維數(shù)。一些分類器，如神經(jīng)網(wǎng)絡(luò)，有在分類過程中用函數(shù)完成數(shù)據(jù)平滑的功能。當(dāng)數(shù)據(jù)平滑在分類過程中完成時，則稱為是內(nèi)部數(shù)據(jù)平滑。外部數(shù)據(jù)平滑是在分類以前進(jìn)行的，舍入和計算平均值是兩種簡單的外部數(shù)據(jù)平滑技術(shù)。當(dāng)我們想使用不支持?jǐn)?shù)值數(shù)據(jù)的分類器，并想保留數(shù)值屬性值的原始信息時，用平均值平滑就很合適。在這種情況下，所有的數(shù)值屬性值被相應(yīng)的中值所替代。在處理缺失數(shù)據(jù)時，因為在訓(xùn)練階段和分類過程本身，缺失數(shù)據(jù)值會導(dǎo)致一些問題，訓(xùn)練數(shù)據(jù)中的缺失值會產(chǎn)生不準(zhǔn)確的結(jié)果，所以必須進(jìn)行

9、處理。分類方法必須能夠處理一個要被分類的元組中的缺失數(shù)據(jù)，有許多種處理缺失數(shù)據(jù)的方法。忽略缺失數(shù)據(jù)。一些數(shù)據(jù)挖掘算法，包括神經(jīng)網(wǎng)絡(luò)和貝葉斯分類器采用了這種方法。丟棄含有缺失值的記錄。當(dāng)記錄只有一小部分缺失數(shù)據(jù)并且我們可以確定缺失值表示信息丟失時，應(yīng)用這種方法非常合適。對于實值數(shù)據(jù)，用中值代替缺失值。在大多數(shù)情況下這是處理數(shù)值屬性的一種理想的方法。對缺失數(shù)據(jù)給定一個假設(shè)的值，這可能需要使用某種方法預(yù)測這個值是什么。用其它相似樣本中的屬性值代替某個樣本缺失的屬性值。(2)相關(guān)性分析由于數(shù)據(jù)集中的許多屬性可能與分類任務(wù)不相關(guān)，若包含這些屬性將減慢和可能誤導(dǎo)學(xué)習(xí)過程。相關(guān)性分析的目的就是刪除這些不相關(guān)

10、或冗余的屬性。(3)數(shù)據(jù)變換數(shù)據(jù)可以概化到較高層概念。比如，連續(xù)值屬性“收入”的數(shù)值可以概化為離散值：低、中、高。此外數(shù)據(jù)也可以規(guī)范化，規(guī)范化將給定屬性的值按比例縮放落入較小的區(qū)間，比如0,1等。3 .分類算法數(shù)據(jù)挖掘有多種經(jīng)典分類算法，這些算法基于不同的分類思想，例如基于距離的KNN算法、基于歸納的決策樹算法、基于統(tǒng)計的貝葉斯算法等等，本文主要介紹以下幾種經(jīng)典分類算法。3.1 決策樹分類在求解分類問題的方法中決策樹學(xué)習(xí)是應(yīng)用最廣的歸納推理算法之一。它是一種逼近離散函數(shù)值的方法，分類精度高，操作簡單，并且對嗓聲數(shù)據(jù)有很好的健壯性，因而成為實用的并且比較流行的數(shù)據(jù)挖掘算法。它的最大優(yōu)點是，在學(xué)習(xí)

11、過程中不需要使用者了解很多背景知識，只要訓(xùn)練樣本集能夠用“屬性值”的方式表達(dá)出來就能使用決策樹學(xué)習(xí)算法分類。決策樹是最為經(jīng)典的決策樹學(xué)習(xí)系統(tǒng)，它采用自頂向下不回溯策略，能保證找到一個簡單的樹。(1)基本思想決策樹方法是挖掘分類規(guī)則的有效方法，通常包括兩個部分：樹的生成開始時所有的數(shù)據(jù)都在根節(jié)點，然后根據(jù)設(shè)定的標(biāo)準(zhǔn)選擇測試屬性，用不同的測試屬性遞歸進(jìn)行數(shù)據(jù)分割。樹的修剪就是除去一些可能是噪音或異常的數(shù)據(jù)。基于信息嫡的ID3算法、C4.5算法都能有效地生成決策樹，建決策樹的關(guān)鍵在于建立分支時對記錄字段不同取值的選擇。選擇不同的字段值使劃分出來的記錄子集不同，影響決策樹生長的快慢及決策樹的結(jié)構(gòu)，從而

12、可尋找到規(guī)則信息的優(yōu)劣?？梢?，決策樹算法的技術(shù)難點就是選擇一個好的分支取值。利用好的取值產(chǎn)生分支可加快決策樹的生長，更重要是產(chǎn)生好結(jié)構(gòu)的決策樹，并可得到較好的規(guī)則信息。相反，若根據(jù)一個差的取值產(chǎn)生分支，不但減慢決策樹的生長速度，而且使產(chǎn)生的決策樹分支過細(xì)、結(jié)構(gòu)差，從而難以發(fā)現(xiàn)有用的規(guī)則信息。隨著訓(xùn)練樣本集中樣本個數(shù)的不斷增多(即樣本集規(guī)模不斷擴(kuò)大)，訓(xùn)練樣本集在主存中換進(jìn)換出就耗費了大量的時間，嚴(yán)重影響了算法效率。因此使算法能有效處理大規(guī)模的訓(xùn)練樣本集已成為決策樹算法研究的一個重要問題，也是目前國內(nèi)對決策樹算法研究的熱點。(2)實現(xiàn)過程輸入：訓(xùn)練數(shù)據(jù)sample由離散值屬性表示；候選屬性的集合

13、attribute_list。輸出：一棵決策樹。創(chuàng)建結(jié)點N;/根結(jié)點IFsamples都在同一個類CTHEN返回N作為葉結(jié)點，以類C標(biāo)記；IFattribute_list為空THEN返回N作為葉結(jié)點，標(biāo)記為samples中最普通的類；選擇attribute_list中具有最高信息增益的屬性test_attribute；標(biāo)記結(jié)點N工test_attribute；/選取具有最高信息增益的屬性作為根結(jié)點FOReachtest_attribute中的已知值ai由結(jié)點N長出一個條件為test_attribute=ai分支；設(shè)s是samples中test_attribute=ai的樣本的集合；一個劃分IF

14、s為空THEN加工一個樹葉，標(biāo)記為samples中最普通的類；ELSE力口上一個由Generate_decision_tree(i,attribute_list-test_attribute)返回的結(jié)點；3.2基于距離的分類(1)算法思想基于距離的分類算法的思路比較簡單直觀。假定數(shù)據(jù)庫中的每個元組為數(shù)值向量，每個類用一個典型數(shù)值向量來表示，則能通過分配每個元組到它最相似的類來實現(xiàn)分類。給定一個數(shù)據(jù)庫D=ti,t2,，tn和一組類C=Cl,，Cm。假定每個元組包括一些數(shù)值型的屬性值：ti=ti1,ti2,tik,每個類也包含數(shù)值性屬性值：Cj=Cj1,Cj2,，Cjk,則分類問題是要分配每個ti

15、到滿足如下條件的類Cj：sim(ti,Cj)>=sim(ti,Ci),vCKC,Cip,(2-1)其中，sim(ti,Cj)表示相似性。在實際的計算中，往往用距離來表征，距離越近，相似性越大，距離越大，相似性越小。為了計算相似性，需要首先得到表示每個類的向量。計算方法有多種，例如代表每個類的向量可以通過計算每個類的中心來表示。另外，在模式識別中，一個預(yù)先定義的圖像用于代表每個類，分類就是把待分類的樣例與預(yù)先定義的圖象進(jìn)行比較。(2)實現(xiàn)過程輸入：每個類的中心C1,，Cm；待分類的元組to輸出：輸出類別cdist=°°距離初始化FORi:=1tomDOIFdis(ci,

16、t)<distTHENBEGINci；dist-dist(i,t)；END.3.3規(guī)則歸納規(guī)則歸納是采用規(guī)則的形式來建立分類器，規(guī)則，是指通過學(xué)習(xí)數(shù)據(jù)，歸納總結(jié)出的該領(lǐng)域數(shù)據(jù)所遵守的規(guī)律。和其余分類方法相比，分類器采用規(guī)則形式表達(dá)具有易理解性。通常，采用規(guī)則表示的分類器構(gòu)造方法有很多種，可以采用規(guī)則歸納技術(shù)直接生成規(guī)則，也可以利用決策樹方法先生成決策樹，然后把決策樹轉(zhuǎn)換為規(guī)則，還可以使用粗糙集方法或者遺傳算法中的分類器技術(shù)生成規(guī)則等。(1)規(guī)則歸納的策略規(guī)則歸納有四種策略：減法、加法，先加后減、先減后加。減法策略：以具體例子為出發(fā)點，對例子進(jìn)行推廣或泛化，推廣即減除條件(屬性值)或減除合

17、取項(為了方便，我們不考慮增加析取項的推廣)，使推廣后的例子或規(guī)則不覆蓋任何反例。加法策略：起始假設(shè)規(guī)則的條件部分為空(永真規(guī)則)，如果該規(guī)則覆蓋了反例，則不停地向規(guī)則增加條件或合取項，直到該規(guī)則不再覆蓋反例。先加后減策略：由于屬性間存在相關(guān)性，因此可能某個條件的加入會導(dǎo)致前面加入的條件沒什么作用，因此需要減除前面的條件。先減后加策略：道理同先加后減，也是為了處理屬性間的相關(guān)性。(2)規(guī)則歸納算法典型的規(guī)則3納算法有AQ、CN2和FOIL等。以AQ為例簡要說明，AQ算法在歸納過程中使用的是“種子”和“星”的概念，種子即是一個正例，星是覆蓋種子而同時排除所有反例的概念描述或規(guī)則。AQ獲取星的方法

18、是通過在星中增加析取或者去掉合取項，使其包含新的正例，然后又在該星中增加合取項，使其包含新的正例，然后又在該星中增加合取項使其排除所包含的反例。上面的過程反復(fù)進(jìn)行，直到所有的正例都被覆蓋。除了上述描述的多種分類算法之外，還有一些其他分類算法，比如貝葉斯分類算法、后向傳播分類、基于案例的推理、遺傳算法、粗糙集和模糊集方法等等。4.結(jié)束語本文對目前比較優(yōu)秀的各種分類算法進(jìn)行了介紹、分析和比較。事實上，上述這些算法的準(zhǔn)確度差別不大，在當(dāng)今數(shù)據(jù)量急劇增長的時代，算法的執(zhí)行速度、可伸縮性以及輸出結(jié)果的可理解性等特性更為重要。止匕外，由于分類的效果一般和數(shù)據(jù)的特點有關(guān)，目前還不存在能適合各種不同數(shù)據(jù)的優(yōu)良分類方法，一種各方面特性都很好的分類算法仍有待進(jìn)一步研究。參考文獻(xiàn)1IanH.Witten,EibeFrank.數(shù)據(jù)挖掘?qū)嵱脵C(jī)器學(xué)習(xí)技術(shù).北京：