摘 要：分類是數據挖掘、機器學習和模式識別中一個重要的研究領域。通過對當前數據挖掘中具有代表性的優秀分類算法進行分析和比較，總結出了各種算法的特性，為使用者選擇算法或研究者改進算法提供了依據。

1 概述

分類是一種重要的數據挖掘技術。分類的目的是根據數據集的特點構造一個分類函數或分類模型（也常常稱作分類器），該模型能把未知類別的樣本映射到給定類別中的某一個。分類和回歸都可以用于預測。和回歸方法不同的是，分類的輸出是離散的類別值，而回歸的輸出是連續或有序值。本文只討論分類。

構造模型的過程一般分為訓練和測試兩個階段。在構造模型之前，要求將數據集隨機地分為訓練數據集和測試數據集。在訓練階段，使用訓練數據集，通過分析由屬性描述的數據庫元組來構造模型，假定每個元組屬于一個預定義的類，由一個稱作類標號屬性的屬性來確定。訓練數據集中的單個元組也稱作訓練樣本，一個具體樣本的形式可為：（u1,u2,……un;c）；其中ui表示屬性值，c表示類別。由于提供了每個訓練樣本的類標號，該階段也稱為有指導的學習，通常，模型用分類規則、判定樹或數學公式的形式提供。在測試階段，使用測試數據集來評估模型的分類準確率，如果認為模型的準確率可以接受，就可以用該模型對其它數據元組進行分類。一般來說，測試階段的代價遠遠低于訓練階段。

為了提高分類的準確性、有效性和可伸縮性，在進行分類之前，通常要對數據進行預處理，包括：

(1) 數據清理。其目的是消除或減少數據噪聲，處理空缺值。

(2) 相關性分析。由于數據集中的許多屬性可能與分類任務不相關，若包含這些屬性將減慢和可能誤導學習過程。相關性分析的目的就是刪除這些不相關或冗余的屬性。

(3) 數據變換。數據可以概化到較高層概念。比如，連續值屬性“收入”的數值可以概化為離散值：低，中，高。又比如，標稱值屬性“市”可概化到高層概念“省”。此外,數據也可以規范化,規范化將給定屬性的值按比例縮放,落入較小的區間,比如[0,1]等。

2 分類算法的種類及特性

分類模型的構造方法有決策樹、統計方法、機器學習方法、神經網絡方法等。按大的方向分類主要有：決策樹，關聯規則，貝葉斯，神經網絡，規則學習，k－臨近法，遺傳算法，粗糙集以及模糊邏輯技術。

2.1 決策樹（decision tree）分類算法

決策樹是以實例為基礎的歸納學習算法。它從一組無次序、無規則的元組中推理出決策樹表示形式的分類規則。它采用自頂向下的遞歸方式，在決策樹的內部結點進行屬性值的比較，并根據不同的屬性值從該結點向下分支，葉結點是要學習劃分的類。從根到葉結點的一條路徑就對應著一條合取規則，整個決策樹就對應著一組析取表達式規則。1986年Quinlan提出了著名的ID3算法。在ID3算法的基礎上，1993年Quinlan又提出了C4.5算法。為了適應處理大規模數據集的需要，后來又提出了若干改進的算法，其中SLIQ (super-vised learning in quest)和SPRINT (scalable parallelizableinduction of decision trees)是比較有代表性的兩個算法。

(1) ID3算法

ID3算法的核心是：在決策樹各級結點上選擇屬性時，用信息增益（information gain）作為屬性的選擇標準，以使得在每一個非葉結點進行測試時，能獲得關于被測試記錄最大的類別信息。其具體方法是：檢測所有的屬性，選擇信息增益最大的屬性產生決策樹結點，由該屬性的不同取值建立分支，再對各分支的子集遞歸調用該方法建立決策樹結點的分支，直到所有子集僅包含同一類別的數據為止。最后得到一棵決策樹，它可以用來對新的樣本進行分類。

某屬性的信息增益按下列方法計算。通過計算每個屬性的信息增益，并比較它們的大小，就不難獲得具有最大信息增益的屬性。

設S是s個數據樣本的集合。假定類標號屬性具有m個不同值，定義m個不同類Ci(i=1,…,m)。設si是類Ci中的樣本數。對一個給定的樣本分類所需的期望信息由下式給出：

其中pi=si/s是任意樣本屬于Ci的概率。注意，對數函數以2為底，其原因是信息用二進制編碼。

設屬性A具有v個不同值{a1,a2,……,av}。可以用屬性A將S劃分為v個子集{S1,S2,……,Sv}，其中Sj中的樣本在屬性A上具有相同的值aj（j=1,2,……,v）。設sij是子集Sj中類Ci的樣本數。由A劃分成子集的熵或信息期望由下式給出：

熵值越小，子集劃分的純度越高。對于給定的子集Sj，其信息期望為

其中pij=sij/sj 是Sj中樣本屬于Ci的概率。在屬性A上分枝將獲得的信息增益是

Gain(A)= I(s1, s2, …,sm)-E(A)

ID3算法的優點是：算法的理論清晰，方法簡單，學習能力較強。其缺點是：只對比較小的數據集有效，且對噪聲比較敏感，當訓練數據集加大時，決策樹可能會隨之改變。

(2) C4.5算法

C4.5算法繼承了ID3算法的優點，并在以下幾方面對ID3算法進行了改進：

1) 用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足；

2) 在樹構造過程中進行剪枝；

3) 能夠完成對連續屬性的離散化處理；

4) 能夠對不完整數據進行處理。

C4.5算法與其它分類算法如統計方法、神經網絡等比較起來有如下優點：產生的分類規則易于理解，準確率較高。其缺點是：在構造樹的過程中，需要對數據集進行多次的順序掃描和排序，因而導致算法的低效。此外，C4.5只適合于能夠駐留于內存的數據集，當訓練集大得無法在內存容納時程序無法運行。

(3) SLIQ算法

SLIQ算法對C4.5決策樹分類算法的實現方法進行了改進，在決策樹的構造過程中采用了“預排序”和“廣度優先策略”兩種技術。

1) 預排序。對于連續屬性在每個內部結點尋找其最優分裂標準時，都需要對訓練集按照該屬性的取值進行排序，而排序是很浪費時間的操作。為此，SLIQ算法采用了預排序技術。所謂預排序，就是針對每個屬性的取值，把所有的記錄按照從小到大的順序進行排序，以消除在決策樹的每個結點對數據集進行的排序。具體實現時，需要為訓練數據集的每個屬性創建一個屬性列表，為類別屬性創建一個類別列表。

2) 廣度優先策略。在C4.5算法中，樹的構造是按照深度優先策略完成的，需要對每個屬性列表在每個結點處都進行一遍掃描，費時很多，為此，SLIQ采用廣度優先策略構造決策樹，即在決策樹的每一層只需對每個屬性列表掃描一次，就可以為當前決策樹中每個葉子結點找到最優分裂標準。

SLIQ算法由于采用了上述兩種技術，使得該算法能夠處理比C4.5大得多的訓練集，在一定范圍內具有良好的隨記錄個數和屬性個數增長的可伸縮性。

然而它仍然存在如下缺點：

1)由于需要將類別列表存放于內存,而類別列表的元組數與訓練集的元組數是相同的,這就一定程度上限制了可以處理的數據集的大小。

2) 由于采用了預排序技術，而排序算法的復雜度本身并不是與記錄個數成線性關系，因此，使得SLIQ算法不可能達到隨記錄數目增長的線性可伸縮性。

(4) SPRINT算法

為了減少駐留于內存的數據量，SPRINT算法進一步改進了決策樹算法的數據結構，去掉了在SLIQ中需要駐留于內存的類別列表，將它的類別列合并到每個屬性列表中。這樣，在遍歷每個屬性列表尋找當前結點的最優分裂標準時，不必參照其他信息，將對結點的分裂表現在對屬性列表的分裂，即將每個屬性列表分成兩個，分別存放屬于各個結點的記錄。

SPRINT算法的優點是在尋找每個結點的最優分裂標準時變得更簡單。其缺點是對非分裂屬性的屬性列表進行分裂變得很困難。解決的辦法是對分裂屬性進行分裂時用哈希表記錄下每個記錄屬于哪個孩子結點，若內存能夠容納下整個哈希表，其他屬性列表的分裂只需參照該哈希表即可。由于哈希表的大小與訓練集的大小成正比，當訓練集很大時，哈希表可能無法在內存容納，此時分裂只能分批執行，這使得SPRINT算法的可伸縮性仍然不是很好。

貝葉斯分類是統計學分類方法，它是一類利用概率統計知識進行分類的算法。在許多場合，樸素貝葉斯(Na?ve Bayes，NB)分類算法可以與決策樹和神經網絡分類算法相媲美，該算法能運用到大型數據庫中，且方法簡單、分類準確率高、速度快。由于貝葉斯定理假設一個屬性值對給定類的影響獨立于其它屬性的值，而此假設在實際情況中經常是不成立的，因此其分類準確率可能會下降。為此，就出現了許多降低獨立性假設的貝葉斯分類算法，如TAN(tree augmented Bayes network)算法。
? ? ? ?

(1) 樸素貝葉斯算法

設每個數據樣本用一個n維特征向量來描述n個屬性的值，即：X={x1，x2，…，xn}，假定有m個類，分別用C1, C2,…，Cm表示。給定一個未知的數據樣本X（即沒有類標號），若樸素貝葉斯分類法將未知的樣本X分配給類Ci，則一定是

P(Ci|X)>P(Cj|X) 1≤j≤m，j≠i

根據貝葉斯定理

由于P(X)對于所有類為常數，最大化后驗概率P(Ci|X)可轉化為最大化先驗概率P(X|Ci)P(Ci)。如果訓練數據集有許多屬性和元組，計算P(X|Ci)的開銷可能非常大，為此，通常假設各屬性的取值互相獨立，這樣

先驗概率P(x1|Ci)，P(x2|Ci)，…，P(xn|Ci)可以從訓練數據集求得。

根據此方法，對一個未知類別的樣本X，可以先分別計算出X屬于每一個類別Ci的概率P(X|Ci)P(Ci)，然后選擇其中概率最大的類別作為其類別。

樸素貝葉斯算法成立的前提是各屬性之間互相獨立。當數據集滿足這種獨立性假設時,分類的準確度較高，否則可能較低。另外，該算法沒有分類規則輸出。

(2) TAN算法

TAN算法通過發現屬性對之間的依賴關系來降低NB中任意屬性之間獨立的假設。它是在NB網絡結構的基礎上增加屬性對之間的關聯(邊)來實現的。

實現方法是：用結點表示屬性，用有向邊表示屬性之間的依賴關系，把類別屬性作為根結點，其余所有屬性都作為它的子節點。通常，用虛線代表NB所需的邊，用實線代表新增的邊。屬性Ai與Aj之間的邊意味著屬性Ai對類別變量C的影響還取決于屬性Aj的取值。

這些增加的邊需滿足下列條件：類別變量沒有雙親結點，每個屬性有一個類別變量雙親結點和最多另外一個屬性作為其雙親結點。

找到這組關聯邊之后，就可以計算一組隨機變量的聯合概率分布如下：

其中ΠAi代表的是Ai的雙親結點。由于在TAN算法中考慮了n個屬性中(n-1)個兩兩屬性之間的關聯性，該算法對屬性之間獨立性的假設有了一定程度的降低，但是屬性之間可能存

在更多其它的關聯性仍沒有考慮，因此其適用范圍仍然受到限制。

2.3 基于關聯規則的分類算法

關聯規則挖掘是數據挖掘研究的一個重要的、高度活躍的領域。近年來，數據挖掘技術己將關聯規則挖掘用于分類問題，取得了很好的效果。

ARCS(Association Rule Clustering System)基于聚類挖掘關聯規則，然后使用規則進行分類。將關聯規則畫在2-D柵格上，算法掃描柵格，搜索規則的矩形聚類。實踐發現，當數據中存在孤立點時，ARCS比C4.5稍微精確一點。ARCS的準確性與離散化程度有關。從可伸縮性來說，不論數據庫多大，ARCS需要的存儲容量為常數。

CBA(classification based on association)是基于關聯規則發現方法的分類算法。該算法分兩個步驟構造分類器。第一步：發現所有形如xi1∧x => Ci 的關聯規則，即右部為類別屬性值的類別關聯規則(classification association rules，CAR)。第二步：從已發現的CAR中選擇高優先度的規則來覆蓋訓練集，也就是說，如果有多條關聯規則的左部相同，而右部為不同的類，則選擇具有最高置信度的規則作為可能規則。文獻[4]對該過程進行了較深入的研究，使得算法在此步驟不需要對訓練數據集進行過多的掃描。

CBA算法的優點是其分類準確度較高，在許多數據集上比C4.5更精確。此外，上述兩步都具有線性可伸縮性。

CBA(Classification Based on Association)是關聯分類。此算法把分類規則挖掘和關聯規則挖掘整合到一起。與CART和C4.5只產生部分規則不同的是,CBA產生所有的類關聯規則CARs(Class Association Rules)，然后選擇最好的規則去覆蓋訓練集。另外，在此算法的框架中，數據庫可以駐留在磁盤中

CAEP使用項集支持度挖掘HV露模式(Emerging Pattern), 而EP用于構造分類。CAEP找出滿足給定支持度和增長率閾值的EP。己經發現，在許多數據集上，CAEP比C4.5和基于關聯的分類更精確。一種替代的、基于跳躍的HV露模式JEP(Jnmping Emerging Pattern)是一種特殊類型的EP，項集的支持度由在一個數據集中的0陡峭地增長到另一個數據集中的非0。在一此大的多維數據庫中，JEP性能優于CAEP, 但在一些小型數據庫中，CAEP比JEP優，這二種分類法被認為是互補的。

ADT(Association Decision Trec)分二步實現以精確度驅動為基礎的過度適合規則的剪枝。第一步，運用置信度規則建立分類器。主要是采用某種置信度的單調性建立基于置信度的剪枝策略。第二步，為實現精確性，用關聯規則建立一種平衡于DT(Dccision Tree)歸納的精確度驅動剪枝。這樣的結果就是ADT(Association Based Decision Trec)。它聯合了大量的關聯規則和DT歸納精確性驅動剪枝技術。

基于多維關聯規則的分類算法CMAR(Classification Based on Multiple Class-Association Rules)是利用FP-Growth算法挖掘關聯規則，建立類關聯分布樹FP－樹。采用CR－樹(Classification Rulc Trcc)結構有效地存儲關聯規則。基于置信度、相關性和數據庫覆蓋來剪枝。分類的具體執行采用加權廠來分析。與CBA和C 4.5相比，CMAR性能優異且伸縮性較好。但CMAR優先生成的是長規則，對數據庫的覆蓋效果較差;利用加權x2統計量進行分類，會造成x2統計量的失真，致使分類值的準確程度降低。CPAR(Classification Based on Predictive Association Rules)整合了關聯規則分類和傳統的基于規則分類的優點。為避免過度適合，在規則生成時采用貪心算法，這比產生所有候選項集的效率高;采用一種動態方法避免在規則生成時的重復計算;采用頂期精確性評價規則，并在預測時應用最優的規則，避免產生冗余的規則。另外，MSR(Minimnm Set Rule)針對基于關聯規則分類算法中產生的關聯規則集可能太大的問題，在分類中運用最小關聯規則集。在此算法中，CARS并不是通過置信度首先排序，因為高置信度規則對噪聲是很敏感的。采用早期剪枝力方法可減少關聯規則的數量，并保證在最小集中沒有不相關的規則。實驗證實，MSR比C45和CBA的錯誤率要低得多。

雖然數據挖掘的創始人主要是數據庫領域的研究人員，然而提出的大多數算法則沒有利用數據庫的相關技術。在分類算法中，致力于解決此問題的算法有MIND （mining in database）和GAC-RDB（grouping and counting-relational database）。

(1) MIND算法
MIND 算法是采用數據庫中用戶定義的函數(user-defined function，UDF)實現發現分類規則的算法。MIND采用典型的決策樹構造方法構建分類器。具體步驟與SLIQ類似。其主要區別在于它采用數據庫提供的UDF方法和SQL語句實現樹的構造。簡而言之，就是在樹的每一層，為每一個屬性建立一個維表，存放各屬性的每個取值屬于各個類別的個數以及所屬的結點編號。根據這些信息可以為當前結點計算每種分裂標準的值，選出最優的分裂標準，然后據此對結點進行分裂，修改維表中結點編號列的值。在上述過程中，對維表的創建和修改需要進行多次，若用SQL實現，耗時很多，因此用UDF實現。而分類標準的尋找過程則通過創建若干表和視圖，利用連接查詢實現。

該算法的優點是通過采用UDF實現決策樹的構造過程使得分類算法易于與數據庫系統集成。其缺點是算法用UDF完成主要的計算任務，而UDF一般是由用戶利用高級語言實現的，無法使用數據庫系統提供的查詢處理機制，無法利用查詢優化方法，且UDF的編寫和維護相當復雜。此外，MIND中用SQL語句實現的那部分功能本身就是比較簡單的操作，而采用SQL實現的方法卻顯得相當復雜。

(2) GAC-RDB算法
GAC -RDB算法是一種利用SQL語句實現的分類算法。該算法采用一種基于分組計數的方法統計訓練數據集中各個屬性取值組合的類別分布信息，通過最小置信度和最小支持度兩個閾值找出有意義的分類規則。在該算法中，首先利用SQL語句計算每個屬性進行類別判定的信息量，從而選擇一個最優的分裂屬性，并且按照信息量的大小對屬性進行排序，隨后重復地進行屬性的選擇、候選分類表的生成、剪裁以及分類誤差的計算，直到滿足結束條件為止，比如，直到小于誤差閾值和誤差沒有改變為止。

該算法的優點是具有與現有的其他分類器相同的分類準確度，執行速度有較大提高，而且具有良好的伸縮性，應用程序易于與數據庫系統集成。其缺點是參數的取值需用戶完成等。