1、數據挖掘數據挖掘分類算法綜述專 業：計算機科學與技術專業學 號：S20100451姓 名：張靖指導教帥：陳俊杰時 間：2011年08月21日TAWJAN WIVEBSm OF TECHNOLOGY數據挖掘分類算法綜述數據挖掘出現丁20世紀80年代后期，是數據庫研究中最有應用價值的新領 域之一。它最早是以從數據中發現知識（KDD , Knowledge Discovery in Database）研究起步，所謂的數據挖掘（Data Mining，簡稱為DM），就從大量的、不完全的、 有噪聲的、模糊的、隨機的、實際應用的數據中提取隱含在其中的、人們不知道 的但乂有用的信息和知識的過程。分類是一種重

2、要的數據挖掘技術。分類的目的是根據數據集的特點構造一個 分類函數或分類模型（也常常稱作分類器）。該模型能把未知類別的樣本映射到給 定類別中的一種技術。1.分類的基本步驟數據分類過程主要包含兩個步驟：第一步，建立一個描述已知數據集類別或概念的模型。如圖1所示，該模型是通過對數據庫中各數據行內容的分析而獲得的。每一數據行都可認為是屆丁一 個確定的數據類別，其類別值是由一個屆性描述 （被稱為類別屆性）。分類學習方 法所使用的數據集稱為訓練樣本集合，因此分類學習乂可以稱為有指導學習（learning by example）。它是在已知訓練樣本類別情況下，通過學習建立相應模型， 而無指導學習則是在訓練樣

3、本的類別與類別個數均未知的情況下進行的。通常分類學習所獲得的模型可以表示為分類規則形式、決策樹形式或數學公 式形式。例如，給定一個顧客信用信息數據庫，通過學習所獲得的分類規則可用 丁識別顧客是否是具有良好的信用等級或一般的信用等級。分類規則也可用丁對今后未知所屆類別的數據進行識別判斷，同時也可以幫助用戶更好的了解數據庫 中的內容。圖 1 數據分類過程中的學習建模第二步，利用所獲得的模型進行分類操作。首先對模型分類準確率進行估計， 例如使用保持（holdout）方法。如果一個學習所獲模型的準確率經測試被認為是可 以接受的，那么就可以使用這一模型對未來數據行或對象（其類別未知）進行分類。例如，在圖

4、2中利用學習獲得的分類規則（模型）。對已知測試數據進行模型nameageincomeCredit_ratingSandy Jones也lowfairBill lee冬0lowexcellentCourtney fox3140highexcellentSusan lake40medfairClaire phips 40medfairAndre beau3140high.excellent訓練數據分類規則If age= 31-40 ” andincome=high Thencredit_rating=excellent準確率的評估，以及對未知類別的新數據進行分類預測。圖 2 數據分類過程中的分類測

5、試分類的具體規則可描述如下：給定一組訓練數據的集合T(Training set),由一 條條的數據庫記錄(Record)組成的，T的每一條記錄包含若干條屆性(Attribute)組 成一個特征向量，用欠量X =(x1,x2,.,xn)表示，其中x1壬in)對應各非類別 屆性，可以有不同的值域，當一屆性的值域為連續域時，該屆性為連續屆性(Numerical Attribute)，否則為離散屆性(Discrete Attribute)，用c表示類別屆性c = (G,C2,.,cQ ,即數據集有k個不同的類別，那么，T就隱含了一個從欠量X到 類別屆性的映射函數H : f (X)Tc。分類的目的就是分

6、析輸入數據，通過在訓練 集中的數據表現出來的特性，為每一個類找到一種準確的描述或者模型，采用該種方法C莫型)將隱含函數表示出來。構造分類模型的過程一般分為訓練和測試兩 個階段，在構造模型之前，要求將數據集隨機地分為訓練數據集和測試數據集。 在訓練階段，使用訓練數據集通過分析有屆性描述的數據庫元組來構造模型。在測試階段，使用測試數據集，來評估模型的分類準確率，如果認為模型的準確率 可以接受，就可以用該模型對其它數據元組進分類，一般來說，測試階段的代價遠遠低丁訓練階段。2.分類數據的預處理為了提高分類的準確性、有效性和可伸縮性，在進行分類之前通常要對數據 進行預處理，包括以下幾方面：(1)數據活理

7、大多數數據預處理是數據活理的一種形式， 其目的是消除或減少數據噪聲和 處理缺失數據的信息。噪聲代表屆性值中的隨機錯誤。在所有大的數據集中噪聲 以各種形式和排列方式出現，對噪聲數據通常關心的問題如下：1發現重復記錄。2查找錯誤的屆性值。在分類數據中尋找錯誤是大型數據集所面臨的一個 問題。一些數據挖掘工具提供了頻率值或分類屆性的預測能力值的匯nameageincomeCredit_ratingSandy Jones0lowfairBill lee40medfairClaire phips 40medfairAndre beau-3140.highexcellent.| John Henri |30

8、41 high |總，可以認為預測能力值接近于0的屆性值可能是錯誤的。3數據平滑。數據平滑是一個數據活理和數據轉換的過程。一些數據平滑 技術努力減少數值屆性值的維數。一些分類器，如神經網絡，有在分類 過程中用函數完成數據平滑的功能。當數據平滑在分類過程中完成時， 則稱為是內部數據平滑。外部數據平滑是在分類以前進行的，舍入和計 算平均值是兩種簡單的外部數據平滑技術。當我們想使用不支持數值數據的分類器，并想保留數值屆性值的原始信息時，用平均值平滑就很合 適。在這種情況下，所有的數值屆性值被相應的中值所替代。在處理缺失數據時，因為在訓練階段和分類過程本身，缺失數據值會導致一 些問題，訓練數據中的缺失

9、值會產生不準確的結果，所以必須進行處理。分類方法必須能夠處理一個要被分類的元組中的缺失數據， 有許多種處理缺失數據的方 法。1忽略缺失數據。一些數據挖掘算法，包括神經網絡和貝葉斯分類器采用 了這種方法。2丟棄含有缺失值的記錄。當記錄只有一小部分缺失數據并且我們可以確 定缺失值表示信息丟失時，應用這種方法非常合適。3對于實值數據，用中值代替缺失值。在大多數情況下這是處理數值屆性 的一種理想的方法。4對缺失數據給定一個假設的值，這可能需要使用某種方法預測這個值是 什么。5用其它相似樣本中的屆性值代替某個樣本缺失的屆性值。(2)相關性分析由于數據集中的許多屆性可能與分類任務不相關， 若包含這些屆性將

10、減慢和 可能誤導學習過程。相關性分析的目的就是刪除這些不相關或冗余的屆性。(3)數據變換數據可以概化到較高層概念。比如，連續值屆性“收入”的數值可以概化為 離散值：低、中、高。此外數據也可以規范化，規范化將給定屆性的值按比例縮 放落入較小的區間，比如0, 1等。3.分類算法數據挖掘有多種經典分類算法，這些算法基于不同的分類思想，例如基于距 離的KNN算法、基于歸納的決策樹算法、基于統計的貝葉斯算法等等，本文主 要介紹以下幾種經典分類算法。3.1決策樹分類在求解分類問題的方法中決策樹學習是應用最廣的歸納推理算法之一。它是一種逼近離散函數值的方法，分類精度高，操作簡單，并且對嗓聲數據有很好的 健壯

11、性，因而成為實用的并且比較流行的數據挖掘算法。它的最大優點是，在學 習過程中不需要使用者了解很多背景知識,只要訓練樣本集能夠用“屆性值”的方式表達出來就能使用決策樹學習算法分類。決策樹是最為經典的決策樹學習系統，它采用自頂向下不回溯策略，能保證找到一個簡單的樹。(1)基本思想決策樹方法是挖掘分類規則的有效方法，通常包括兩個部分：1樹的生成開始時所有的數據都在根節點，然后根據設定的標準選擇測試屆性，用不 同的測試屆性遞歸進行數據分割。2樹的修剪就是除去一些可能是噪首或異常的數據。基于信息炳的ID3算法、C4. 5算法都能有效地生成決策樹，建決策樹的關鍵在于建立分支時對記錄字段 不同取值的選擇。選

12、擇不同的字段值使劃分出來的記錄子集不同，影響決策樹生長的快慢及決策樹的結構，從而可尋找到規則信息的優劣。可見，決策樹算法的技術難點就是選擇一個好的分支取值。利用好的取值產生分支可加快決策樹的生長，更重要是產生好結構的決策樹，并可得到較好的規 則信息。相反，若根據一個差的取值產生分支，不但減慢決策樹的生長速度，而 且使產生的決策樹分支過細、結構差，從而難以發現有用的規則信息。隨著訓練樣本集中樣本個數的不斷增多(即樣本集規模不斷擴大)，訓練樣本 集在主存中換進換出就耗費了大量的時間， 嚴重影響了算法效率。因此使算法能 有效處理大規模的訓練樣本集已成為決策樹算法研究的一個重要問題，也是目前國內對決策

13、樹算法研究的熱點。(2)實現過程輸入：訓練數據sample由離散值屆性表示；候選屆性的集合attribute_list。 輸出：一棵決策樹。1創建結點N；根結點2IF samples都在同一個類C THEN返回N作為葉結點，以類C標記；3IF attribute_list為空THEN返回N作為葉結點，標記為samples中最普 通的類；4選擇attribute_list中具有最高信息增益的屆性test_attribute；5標記結點N test_attribute；選取具有最高信息增益的屆性作為根結點6FOR each test_attribute中的已知值ai由結點N長出一個條件為test_

14、attribute=ai分支；7設s是samples中test_attribute =ai的樣本的集合；一個劃分8IF s為空THEN加i一個樹葉，標記為samples中最普通的類；9ELSE加上一個由Generate_decision_tree(i, attribute_list-test_attribute)返回的結點；3.2基于距離的分類(1)算法思想基于距離的分類算法的思路比較簡單直觀。 假定數據庫中的每個元組為數值 向量，每個類用一個典型數值向量來表示， 則能通過分配每個元組到它最相似的 類來實現分類。給定一個數據庫D=ti,t2,，tn和一組類C=Cl,，Cm。假定每個 元組包括一

15、些數值型的屆性值：ti= til ,ti2,，tik,每個類也包含數值性屆性 值：Cj=Cj1,Cj2,，Cjk，則分類問題是要分配每個ti到滿足如下條件的類Cj：sim(ti,Cj)=sim(ti,Ci) , vCi C, CiCj,(2-1)其中，sim(ti,Cj)表示相似性。在實際的計算中，往往用距離來表征，距離越近，相似性越大，距離越大， 相似性越小。為了計算相似性，需要首先得到表示每個類的向量。計算方法有多種，例如代表每個類的向量可以通過計算每個類的中心來表示。另外，在模式識別中，一個預先定義的圖像用丁代表每個類， 分類就是把待分類的樣例與預先定義的圖象 進行比較。(2)實現過程輸

16、入：每個類的中心C1,，Cm；待分類的元組to輸出：輸出類別Co1dist=8；距離初始化2FOR i:=1 to m DO3IF dis(ci, t)dist THEN BEGIN4c i；5dist dist(i, t)；6END.3.3規則歸納規則歸納是采用規則的形式來建立分類器，規則，是指通過學習數據，歸納 總結出的該領域數據所遵守的規律。和其余分類方法相比， 分類器采用規則形式 表達具有易理解性。通常，采用規則表示的分類器構造方法有很多種，可以采用 規則歸納技術直接生成規則，也可以利用決策樹方法先生成決策樹， 然后把決策 樹轉換為規則，還可以使用粗糙集方法或者遺傳算法中的分類器技術生

17、成規則 等。(1)規則歸納的策略規則歸納有四種策略：減法、加法，先加后減、先減后加。1減法策略：以具體例子為出發點，對例子進行推廣或泛化，推廣即減除 條件(屆性值)或減除合取項(為了方便，我們不考慮增加析取項的推 廣)，使推廣后的例子或規則不覆蓋任何反例。2加法策略：起始假設規則的條件部分為空(永真規則)，如果該規則覆蓋了反例，則不停地向規則增加條件或合取項，直到該規則不再覆蓋反 例。3先加后減策略：由丁屆性問存在相關性，因此可能某個條件的加入會導致前面加入的條件沒什么作用，因此需要減除前面的條件。4先減后加策略：道理同先加后減，也是為了處理屆性問的相關性。(2)規則歸納算法典型的規則歸納算法

18、有AQ、CN2和FOIL等。以AQ為例簡要說明，AQ算法在歸納過程中使用的是“種子”和“星”的概念，種子即是一個正例，星是 覆蓋種子而同時排除所有反例的概念描述或規則。AQ獲取星的方法是通過在星中增加析取或者去掉合取項，使其包含新的正例，然后乂在該星中增加合取項， 使其包含新的正例，然后乂在該星中增加合取項使其排除所包含的反例。上面的過程反復進行，直到所有的正例都被覆蓋。除了上述描述的多種分類算法之外， 還有一些其他分類算法，比如貝葉斯分 類算法、后向傳播分類、基于案例的推理、遺傳算法、粗糙集和模糊集方法等等。4.結束語本文對目前比較優秀的各種分類算法進行了介紹、分析和比較。事實上，上述這些算法的準確度差別不大，在當今數據量急劇增長的時代，算法的執行速度、 可伸縮性以及輸出結果的可理解性等特性更為重要。此外，由于分類的效果一般和數據的特點有關，目前還不存在能適合各種不同數據的優良分類方法，一種各方面特性都很好的分類算法仍有待進一步研究。參考文獻1 Ian H.Witten,Eibe Frank.數據挖掘實用機器學習技術.北京：機械工業出版社，20062 邵峰晶.數據挖掘原理與算