摘 要：分類是數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)和模式識(shí)別中一個(gè)重要的研究領(lǐng)域。通過(guò)對(duì)當(dāng)前數(shù)據(jù)挖掘中具有代表性的優(yōu)秀分類算法進(jìn)行分析和比較，總結(jié)出了各種算法的特性，為使用者選擇算法或研究者改進(jìn)算法提供了依據(jù)。

1 概述

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

構(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)造模型，假定每個(gè)元組屬于一個(gè)預(yù)定義的類，由一個(gè)稱作類標(biāo)號(hào)屬性的屬性來(lái)確定。訓(xùn)練數(shù)據(jù)集中的單個(gè)元組也稱作訓(xùn)練樣本，一個(gè)具體樣本的形式可為：（u1,u2,……un;c）；其中ui表示屬性值，c表示類別。由于提供了每個(gè)訓(xùn)練樣本的類標(biāo)號(hào)，該階段也稱為有指導(dǎo)的學(xué)習(xí)，通常，模型用分類規(guī)則、判定樹或數(shù)學(xué)公式的形式提供。在測(cè)試階段，使用測(cè)試數(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)練階段。

為了提高分類的準(zhǔn)確性、有效性和可伸縮性，在進(jìn)行分類之前，通常要對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，包括：

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

(2) 相關(guān)性分析。由于數(shù)據(jù)集中的許多屬性可能與分類任務(wù)不相關(guān)，若包含這些屬性將減慢和可能誤導(dǎo)學(xué)習(xí)過(guò)程。相關(guān)性分析的目的就是刪除這些不相關(guān)或冗余的屬性。

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

2 分類算法的種類及特性

分類模型的構(gòu)造方法有決策樹、統(tǒng)計(jì)方法、機(jī)器學(xué)習(xí)方法、神經(jīng)網(wǎng)絡(luò)方法等。按大的方向分類主要有：決策樹，關(guān)聯(lián)規(guī)則，貝葉斯，神經(jīng)網(wǎng)絡(luò)，規(guī)則學(xué)習(xí)，k－臨近法，遺傳算法，粗糙集以及模糊邏輯技術(shù)。

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

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

(1) ID3算法

ID3算法的核心是：在決策樹各級(jí)結(jié)點(diǎn)上選擇屬性時(shí)，用信息增益（information gain）作為屬性的選擇標(biāo)準(zhǔn)，以使得在每一個(gè)非葉結(jié)點(diǎn)進(jìn)行測(cè)試時(shí)，能獲得關(guān)于被測(cè)試記錄最大的類別信息。其具體方法是：檢測(cè)所有的屬性，選擇信息增益最大的屬性產(chǎn)生決策樹結(jié)點(diǎn)，由該屬性的不同取值建立分支，再對(duì)各分支的子集遞歸調(diào)用該方法建立決策樹結(jié)點(diǎn)的分支，直到所有子集僅包含同一類別的數(shù)據(jù)為止。最后得到一棵決策樹，它可以用來(lái)對(duì)新的樣本進(jìn)行分類。

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

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

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

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

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

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

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

ID3算法的優(yōu)點(diǎn)是：算法的理論清晰，方法簡(jiǎn)單，學(xué)習(xí)能力較強(qiáng)。其缺點(diǎn)是：只對(duì)比較小的數(shù)據(jù)集有效，且對(duì)噪聲比較敏感，當(dāng)訓(xùn)練數(shù)據(jù)集加大時(shí)，決策樹可能會(huì)隨之改變。

(2) C4.5算法

C4.5算法繼承了ID3算法的優(yōu)點(diǎn)，并在以下幾方面對(duì)ID3算法進(jìn)行了改進(jìn)：

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

2) 在樹構(gòu)造過(guò)程中進(jìn)行剪枝；

3) 能夠完成對(duì)連續(xù)屬性的離散化處理；

4) 能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。

C4.5算法與其它分類算法如統(tǒng)計(jì)方法、神經(jīng)網(wǎng)絡(luò)等比較起來(lái)有如下優(yōu)點(diǎn)：產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。其缺點(diǎn)是：在構(gòu)造樹的過(guò)程中，需要對(duì)數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。此外，C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無(wú)法在內(nèi)存容納時(shí)程序無(wú)法運(yùn)行。

(3) SLIQ算法

SLIQ算法對(duì)C4.5決策樹分類算法的實(shí)現(xiàn)方法進(jìn)行了改進(jìn)，在決策樹的構(gòu)造過(guò)程中采用了“預(yù)排序”和“廣度優(yōu)先策略”兩種技術(shù)。

1) 預(yù)排序。對(duì)于連續(xù)屬性在每個(gè)內(nèi)部結(jié)點(diǎn)尋找其最優(yōu)分裂標(biāo)準(zhǔn)時(shí)，都需要對(duì)訓(xùn)練集按照該屬性的取值進(jìn)行排序，而排序是很浪費(fèi)時(shí)間的操作。為此，SLIQ算法采用了預(yù)排序技術(shù)。所謂預(yù)排序，就是針對(duì)每個(gè)屬性的取值，把所有的記錄按照從小到大的順序進(jìn)行排序，以消除在決策樹的每個(gè)結(jié)點(diǎn)對(duì)數(shù)據(jù)集進(jìn)行的排序。具體實(shí)現(xiàn)時(shí)，需要為訓(xùn)練數(shù)據(jù)集的每個(gè)屬性創(chuàng)建一個(gè)屬性列表，為類別屬性創(chuàng)建一個(gè)類別列表。

2) 廣度優(yōu)先策略。在C4.5算法中，樹的構(gòu)造是按照深度優(yōu)先策略完成的，需要對(duì)每個(gè)屬性列表在每個(gè)結(jié)點(diǎn)處都進(jìn)行一遍掃描，費(fèi)時(shí)很多，為此，SLIQ采用廣度優(yōu)先策略構(gòu)造決策樹，即在決策樹的每一層只需對(duì)每個(gè)屬性列表掃描一次，就可以為當(dāng)前決策樹中每個(gè)葉子結(jié)點(diǎn)找到最優(yōu)分裂標(biāo)準(zhǔn)。

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

然而它仍然存在如下缺點(diǎn)：

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

2) 由于采用了預(yù)排序技術(shù)，而排序算法的復(fù)雜度本身并不是與記錄個(gè)數(shù)成線性關(guān)系，因此，使得SLIQ算法不可能達(dá)到隨記錄數(shù)目增長(zhǎng)的線性可伸縮性。

(4) SPRINT算法

為了減少駐留于內(nèi)存的數(shù)據(jù)量，SPRINT算法進(jìn)一步改進(jìn)了決策樹算法的數(shù)據(jù)結(jié)構(gòu)，去掉了在SLIQ中需要駐留于內(nèi)存的類別列表，將它的類別列合并到每個(gè)屬性列表中。這樣，在遍歷每個(gè)屬性列表尋找當(dāng)前結(jié)點(diǎn)的最優(yōu)分裂標(biāo)準(zhǔn)時(shí)，不必參照其他信息，將對(duì)結(jié)點(diǎn)的分裂表現(xiàn)在對(duì)屬性列表的分裂，即將每個(gè)屬性列表分成兩個(gè)，分別存放屬于各個(gè)結(jié)點(diǎn)的記錄。

SPRINT算法的優(yōu)點(diǎn)是在尋找每個(gè)結(jié)點(diǎn)的最優(yōu)分裂標(biāo)準(zhǔn)時(shí)變得更簡(jiǎn)單。其缺點(diǎn)是對(duì)非分裂屬性的屬性列表進(jìn)行分裂變得很困難。解決的辦法是對(duì)分裂屬性進(jìn)行分裂時(shí)用哈希表記錄下每個(gè)記錄屬于哪個(gè)孩子結(jié)點(diǎn)，若內(nèi)存能夠容納下整個(gè)哈希表，其他屬性列表的分裂只需參照該哈希表即可。由于哈希表的大小與訓(xùn)練集的大小成正比，當(dāng)訓(xùn)練集很大時(shí)，哈希表可能無(wú)法在內(nèi)存容納，此時(shí)分裂只能分批執(zhí)行，這使得SPRINT算法的可伸縮性仍然不是很好。

貝葉斯分類是統(tǒng)計(jì)學(xué)分類方法，它是一類利用概率統(tǒng)計(jì)知識(shí)進(jìn)行分類的算法。在許多場(chǎng)合，樸素貝葉斯(Na?ve Bayes，NB)分類算法可以與決策樹和神經(jīng)網(wǎng)絡(luò)分類算法相媲美，該算法能運(yùn)用到大型數(shù)據(jù)庫(kù)中，且方法簡(jiǎn)單、分類準(zhǔn)確率高、速度快。由于貝葉斯定理假設(shè)一個(gè)屬性值對(duì)給定類的影響?yīng)毩⒂谄渌鼘傩缘闹担思僭O(shè)在實(shí)際情況中經(jīng)常是不成立的，因此其分類準(zhǔn)確率可能會(huì)下降。為此，就出現(xiàn)了許多降低獨(dú)立性假設(shè)的貝葉斯分類算法，如TAN(tree augmented Bayes network)算法。
? ? ? ?