分類算法綜述

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

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

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

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

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

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

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

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

9、處理。分類方法必須能夠處理一個(gè)要被分類的元組中的缺失數(shù)據(jù)，有許多種處理缺失數(shù)據(jù)的方法。忽略缺失數(shù)據(jù)。一些數(shù)據(jù)挖掘算法，包括神經(jīng)網(wǎng)絡(luò)和貝葉斯分類器采用了這種方法。丟棄含有缺失值的記錄。當(dāng)記錄只有一小部分缺失數(shù)據(jù)并且我們可以確定缺失值表示信息丟失時(shí)，應(yīng)用這種方法非常合適。對(duì)于實(shí)值數(shù)據(jù)，用中值代替缺失值。在大多數(shù)情況下這是處理數(shù)值屬性的一種理想的方法。對(duì)缺失數(shù)據(jù)給定一個(gè)假設(shè)的值，這可能需要使用某種方法預(yù)測(cè)這個(gè)值是什么。用其它相似樣本中的屬性值代替某個(gè)樣本缺失的屬性值。(2)相關(guān)性分析由于數(shù)據(jù)集中的許多屬性可能與分類任務(wù)不相關(guān)，若包含這些屬性將減慢和可能誤導(dǎo)學(xué)習(xí)過(guò)程。相關(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算法、基于歸納的決策樹(shù)算法、基于統(tǒng)計(jì)的貝葉斯算法等等，本文主要介紹以下幾種經(jīng)典分類算法。3.1 決策樹(shù)分類在求解分類問(wèn)題的方法中決策樹(shù)學(xué)習(xí)是應(yīng)用最廣的歸納推理算法之一。它是一種逼近離散函數(shù)值的方法，分類精度高，操作簡(jiǎn)單，并且對(duì)嗓聲數(shù)據(jù)有很好的健壯性，因而成為實(shí)用的并且比較流行的數(shù)據(jù)挖掘算法。它的最大優(yōu)點(diǎn)是，在學(xué)習(xí)

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

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

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

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

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

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

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

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