[摘要]隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，很多領(lǐng)域?qū)Ψ诸惙椒ㄌ岢鲂碌囊?。分析、比較當(dāng)前具有代表性的分類算法，總結(jié)每種算法的優(yōu)缺點(diǎn)，便于使用者根據(jù)需要選擇合適的算法，也便于研究者對(duì)算法進(jìn)行研究改進(jìn)，提出性能更好的分類算法。

[關(guān)鍵詞]數(shù)據(jù)挖掘分類決策樹神經(jīng)網(wǎng)絡(luò)

中圖分類號(hào)：TP3文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1671－7597(2009)0210056－01

一、引言

分類技術(shù)是數(shù)據(jù)挖掘中應(yīng)用領(lǐng)域極其廣泛的重要技術(shù)之一。至今已提出了多種分類算法，主要有決策樹、關(guān)聯(lián)規(guī)則、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)和貝葉斯、k－臨近法、遺傳算法、粗糙集以及模糊邏輯技術(shù)等。大部分技術(shù)都是使用學(xué)習(xí)算法確定分類模型，擬合輸入數(shù)據(jù)中樣本類別和屬性集之間的聯(lián)系，預(yù)測(cè)未知樣本的類別。訓(xùn)練算法的主要目標(biāo)是建立具有好的泛化能力的模型，該模型能夠準(zhǔn)確地預(yù)測(cè)未知樣本的類別。

各種分類算法有其自身的優(yōu)劣，適合于不同的領(lǐng)域。目前隨著新技術(shù)和新領(lǐng)域的不斷出現(xiàn)，對(duì)分類方法提出了新的要求。下面對(duì)若干分類問(wèn)題進(jìn)行簡(jiǎn)要分析。

二、分類方法及優(yōu)缺點(diǎn)

(一)基于決策樹的分類

基于決策樹的分類算法是數(shù)據(jù)挖掘中最為典型的分類算法。決策樹是一個(gè)類似于流程圖的樹結(jié)構(gòu)，其每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試，每個(gè)分枝代表一個(gè)測(cè)試輸出，每個(gè)葉節(jié)點(diǎn)代表類或類分布。

1、決策樹算法基本思想。開始時(shí)所有的訓(xùn)練樣本在根部，基于最高信息增益自頂向下遞歸地劃分?jǐn)?shù)據(jù)集，生成決策樹。當(dāng)一個(gè)結(jié)點(diǎn)上所有樣本都屬于同一類或者沒(méi)有剩余屬性可以用來(lái)進(jìn)一步劃分樣本時(shí)停止劃分，形成一個(gè)葉結(jié)點(diǎn)。如果葉結(jié)點(diǎn)上的樣本不屬于同一類，則根據(jù)大多數(shù)樣本的分類來(lái)確定葉結(jié)點(diǎn)的類別。

創(chuàng)建決策樹時(shí)，因數(shù)據(jù)中存在噪聲和孤立點(diǎn)，許多分枝反映的是訓(xùn)練數(shù)據(jù)集中的異常。剪枝方法可以剪去不可靠的分枝，提高分類速度和分類的準(zhǔn)確度。常用的剪枝方法有：先剪枝和后剪枝。前者通過(guò)提前停止樹的構(gòu)造而對(duì)樹剪枝；后者在完全創(chuàng)建好的樹上剪去分枝。

2、典型的決策樹算法。最為典型的決策樹學(xué)習(xí)算法是ID3，它采用自頂向下不回溯策略，能保證找到一個(gè)簡(jiǎn)單的樹。算法c4.5和c5.0是ID3的擴(kuò)展，它們將分類領(lǐng)域從類別屬性擴(kuò)展到數(shù)值型屬性。常見的決策樹算法還有CART，CHAID，Quest和c5.0等。

在決策樹中，從根到樹葉的每條路徑以IF—THEN形式表示一條分類規(guī)則，沿著給定路徑上的每個(gè)屬性一值對(duì)形成規(guī)則前件的一個(gè)合取項(xiàng)，葉結(jié)點(diǎn)包含類預(yù)測(cè)，形成規(guī)則后件。

3、優(yōu)缺點(diǎn)。決策樹很擅長(zhǎng)處理非數(shù)值型數(shù)據(jù)，從決策樹中可以方便地提取分類規(guī)則。其主要優(yōu)點(diǎn)是描述簡(jiǎn)單，分類速度快，特別適合大規(guī)模的數(shù)據(jù)處理。不足之處是ID3算法偏向于選擇屬性較多的屬性，而屬性較多的屬性往往不是最優(yōu)的屬性：學(xué)習(xí)簡(jiǎn)單的邏輯表達(dá)能力較差。

(二)基于統(tǒng)計(jì)的分類

貝葉斯分類算法是基于貝葉斯定理的一種統(tǒng)計(jì)學(xué)分類算法。它們可以預(yù)測(cè)類成員關(guān)系的可能性，如給定樣本屬于一個(gè)特定類的概率。如果出現(xiàn)類別重疊現(xiàn)象，貝葉斯分類算法采用兩種方法處理這種情況：一是選擇后驗(yàn)概率最大的類別，二是選擇效用函數(shù)最大(或損失最小)的類別。貝葉斯分類也是一種常用的分類方法，它是一種對(duì)屬性集和類變量的概率關(guān)系建模的方法。其理論基礎(chǔ)是貝葉斯定理，可用式2.1[2]表示。

p(c｜x)＝p(x｜c(diǎn))p(c)/p(x)

其中x是類標(biāo)號(hào)未知的數(shù)據(jù)樣本。設(shè)c為某種假定，如數(shù)據(jù)樣本I屬于某特定類民則P(c｜x)為c成立的概率，也稱為類c的先驗(yàn)概率；P(x)為x的支持度。P(c｜x)是規(guī)定數(shù)據(jù)樣本x，假定c成立的概率，稱作類c的后驗(yàn)概率。P(xvc)是假定c成立的情況下，樣本x的支持度，也稱為類條件概率。

準(zhǔn)確估計(jì)類標(biāo)號(hào)和屬性值的每一種可能組合的后驗(yàn)概率非常困難，因?yàn)榧幢銓傩詳?shù)目不是很大，仍然需要很大的訓(xùn)練集。此時(shí)，貝葉斯定理很有用，因?yàn)樗试S我們用先驗(yàn)概率P(c)、類條件概率P(x｜c(diǎn))和P(x)來(lái)表示后驗(yàn)概率。

在比較不同類c的后驗(yàn)概率時(shí)，分母P(x)總是常數(shù)，因此可以忽略。先驗(yàn)概率P(c)可以通過(guò)計(jì)算訓(xùn)練集中屬于每個(gè)類的訓(xùn)練記錄所占的比例很容易地估計(jì)。因此類c的后驗(yàn)概率P(x｜c(diǎn))的確定取決于對(duì)類條件概率P(x｜c(diǎn))的估計(jì)。對(duì)類條件概率P(x｜c(diǎn))的估計(jì)，常使用兩種貝葉斯分類方法來(lái)實(shí)現(xiàn)：樸素貝葉斯分類和貝葉斯信念網(wǎng)絡(luò)。

(三)基于神經(jīng)網(wǎng)絡(luò)的分類

1、基本思想。經(jīng)常用于分類的還有人工神經(jīng)網(wǎng)絡(luò)方法。神經(jīng)網(wǎng)絡(luò)[3]為解決大復(fù)雜度問(wèn)題提供了一種相對(duì)來(lái)說(shuō)比較有效的簡(jiǎn)單方法，它是模仿人腦神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)和某些工作機(jī)制而建立的一種非線形預(yù)測(cè)模型，經(jīng)過(guò)學(xué)習(xí)進(jìn)行模式識(shí)別的。其工作機(jī)理是通過(guò)學(xué)習(xí)改變神經(jīng)元之間的連接強(qiáng)度。神經(jīng)網(wǎng)絡(luò)有前向神經(jīng)網(wǎng)絡(luò)、反饋神經(jīng)網(wǎng)絡(luò)、自組織神經(jīng)網(wǎng)絡(luò)等，在神經(jīng)網(wǎng)絡(luò)中，由權(quán)重和網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)決定了它所能識(shí)別的模式類型。神經(jīng)網(wǎng)絡(luò)分類過(guò)程可以分為訓(xùn)練和分類兩個(gè)階段。在訓(xùn)練階段，首先定義網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，再對(duì)訓(xùn)練樣本中的每個(gè)屬性的值進(jìn)行規(guī)范化預(yù)處理，然后用神經(jīng)網(wǎng)絡(luò)對(duì)已預(yù)處理的輸入進(jìn)行學(xué)習(xí)。訓(xùn)練完畢后，用訓(xùn)練好的神經(jīng)網(wǎng)絡(luò)對(duì)標(biāo)識(shí)樣本進(jìn)行分類。

最流行的神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法是后向傳播算法。后向傳播算法是在多層前饋神經(jīng)網(wǎng)絡(luò)上進(jìn)行學(xué)習(xí)的。這種神經(jīng)網(wǎng)絡(luò)具有一個(gè)輸入層和一個(gè)輸出層，在兩者之間可能包含多個(gè)中間層，這些中間層叫做隱藏層。后向傳播通過(guò)迭代地處理一組訓(xùn)練樣本，將每個(gè)樣本的網(wǎng)絡(luò)預(yù)測(cè)與實(shí)際知道的類標(biāo)號(hào)比較，進(jìn)行學(xué)習(xí)。對(duì)于每個(gè)訓(xùn)練樣本，修改權(quán)值，使得網(wǎng)絡(luò)預(yù)測(cè)和實(shí)際類之間的均方誤差最小。這種修改后向進(jìn)行，即由輸出層，經(jīng)由每個(gè)隱藏層，到第一個(gè)隱藏層。一般的，權(quán)將最終收斂，學(xué)習(xí)過(guò)程停止。算法的每一次迭代包括兩個(gè)階段：前向階段和后向階段。在前向階段，使用前一次迭代所得到的權(quán)值計(jì)算網(wǎng)絡(luò)中每一個(gè)神經(jīng)元的輸出值。計(jì)算是向前進(jìn)行的，先計(jì)算第k層神經(jīng)元的輸出，再計(jì)算第k＋1層的輸出。在后向階段，以相反的方向應(yīng)用權(quán)值更新公式，先更新k＋1層的權(quán)值，再更新第k層的權(quán)值。

2、優(yōu)缺點(diǎn)。神經(jīng)網(wǎng)絡(luò)法的優(yōu)點(diǎn)是有較強(qiáng)的抗噪能力，對(duì)未經(jīng)訓(xùn)練的數(shù)據(jù)也具有較好的預(yù)測(cè)分類能力。神經(jīng)網(wǎng)絡(luò)的主要缺點(diǎn)是用加權(quán)鏈連結(jié)單元的網(wǎng)絡(luò)所表示的知識(shí)很難被人理解、學(xué)習(xí)時(shí)間較長(zhǎng)，僅適用于時(shí)間容許的應(yīng)用場(chǎng)合；對(duì)于如網(wǎng)絡(luò)結(jié)構(gòu)等關(guān)鍵參數(shù)，通常需要經(jīng)驗(yàn)方能有效確定。

(四)基于源自關(guān)聯(lián)規(guī)則挖掘概念的分類

關(guān)聯(lián)規(guī)則聚類系統(tǒng)是基于聚類挖掘關(guān)聯(lián)規(guī)則，然后使用規(guī)則進(jìn)行分類。挖掘形如A_quan1∧A_quan2→A_cat的關(guān)聯(lián)規(guī)則；其中，A_quan1，A_quan2是在量化屬性區(qū)間上的測(cè)試，為給定訓(xùn)練數(shù)據(jù)的分類屬性指定一個(gè)類標(biāo)號(hào)。關(guān)聯(lián)規(guī)則畫在2-D柵

格上。算法掃描柵格，搜索規(guī)則的矩形聚類。由ARCS產(chǎn)生的聚類關(guān)聯(lián)規(guī)則用于分類，其準(zhǔn)確率與C4.5差不多，精確度比C4.5高一點(diǎn)。

關(guān)聯(lián)分類挖掘形如condset→y的規(guī)則，condset是項(xiàng)屬性一值對(duì)的集合，y是類標(biāo)號(hào)。若給定數(shù)據(jù)集中的樣本s％包含condset并且屬于類y，則規(guī)則的支持度為s。若規(guī)則滿足預(yù)先指定的最小支持度，則該規(guī)則是頻繁；若給定數(shù)據(jù)集中包含conset的樣本c％屬于類y，則規(guī)則的置信度為c；若滿足最小置信度，則該規(guī)則是精確的。如果一個(gè)規(guī)則項(xiàng)集具有相同的condset，則選擇具有最高置信度的規(guī)則作為可能規(guī)則，代表該集合。

關(guān)聯(lián)分類方法由兩步組成。第一步是找出所有頻繁的、精確的PR集合。算法使用迭代方法，類似Apriori。第二步使用一種啟發(fā)式方法構(gòu)造分類，發(fā)現(xiàn)的規(guī)則按支持度和置信度遞減的優(yōu)先次序組織，用滿足新樣本滿足該樣本的第一個(gè)規(guī)則對(duì)其分類。CBA是關(guān)聯(lián)分類的經(jīng)典算法，該方法比c4.5更精確。

(五)其他分類方法

用于數(shù)據(jù)分類的方法還有：基于案例的推理分類法、遺傳算法等。

1、基于案例的推理分類法?；诎咐耐评矸诸惙ㄊ腔谝蟮模浯娣诺臉颖臼菑?fù)雜的符號(hào)描述。當(dāng)給定一個(gè)待分類的新案例時(shí)，基于案例的推理首先檢查是否存在一個(gè)同樣的訓(xùn)練案例。如果找到一個(gè)，則返回附在該案例上的解。如果找不到同樣的案例，則基于案例的推理將搜索具有類似于新案例成分的訓(xùn)練案例，這些訓(xùn)練案例可視為新案例的鄰接者。

2、遺傳算法。遺傳算法結(jié)合了自然進(jìn)化的思想。遺傳學(xué)習(xí)開始時(shí)創(chuàng)建了一個(gè)由隨機(jī)產(chǎn)生的規(guī)則組成的初始群體，每個(gè)規(guī)則可以用一個(gè)二進(jìn)制位串表示。根據(jù)適者生存的原則，形成由當(dāng)前群體中最適合的規(guī)則組成的新群體，以及這些規(guī)則的后代。后代通過(guò)使用諸如交叉和變異等遺傳操作來(lái)創(chuàng)建。由先前的規(guī)則群體產(chǎn)生新的規(guī)則群體的過(guò)程繼續(xù)進(jìn)化，直到群體中每個(gè)規(guī)則滿足預(yù)先指定的適合度值。

三、結(jié)語(yǔ)

基于分類關(guān)聯(lián)規(guī)則的關(guān)聯(lián)分類算法CBA，1998年由新加坡國(guó)立大學(xué)的Liu等人，在紐約舉行的數(shù)據(jù)庫(kù)知識(shí)發(fā)現(xiàn)國(guó)際會(huì)議上提出，成為關(guān)聯(lián)分類的經(jīng)典算法。該算法使用類Apriori方法產(chǎn)生分類關(guān)聯(lián)規(guī)則，使用關(guān)聯(lián)規(guī)則進(jìn)行分類和預(yù)測(cè)，Liu等人在UCI的26個(gè)數(shù)據(jù)集上實(shí)驗(yàn)，并c4.5、貝葉斯等分類方法進(jìn)行了比較。在26個(gè)數(shù)據(jù)集上CBA算法分類的平均錯(cuò)誤率為15.2％，比其他幾種算法的錯(cuò)誤率要低。結(jié)果表明該方法具有較好的分類準(zhǔn)確率。

作者簡(jiǎn)介：

劉紅梅，女，湖北荊州人，講師，碩士，現(xiàn)主要從事算法與數(shù)據(jù)結(jié)構(gòu)方面的教學(xué)與研究工作。