數(shù)據(jù)挖掘中分類方法探究

[摘要]隨著計算機技術的飛速發(fā)展，很多領域對分類方法提出新的要求。分析、比較當前具有代表性的分類算法，總結每種算法的優(yōu)缺點，便于使用者根據(jù)需要選擇合適的算法，也便于研究者對算法進行研究改進，提出性能更好的分類算法。

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

中圖分類號：TP3文獻標識碼：A文章編號：1671－7597(2009)0210056－01

一、引言

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

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

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

(一)基于決策樹的分類

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

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

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

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

在決策樹中，從根到樹葉的每條路徑以IF—THEN形式表示一條分類規(guī)則，沿著給定路徑上的每個屬性一值對形成規(guī)則前件的一個合取項，葉結點包含類預測，形成規(guī)則后件。

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

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

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

p(c｜x)＝p(x｜c)p(c)/p(x)

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

準確估計類標號和屬性值的每一種可能組合的后驗概率非常困難，因為即便屬性數(shù)目不是很大，仍然需要很大的訓練集。此時，貝葉斯定理很有用，因為它允許我們用先驗概率P(c)、類條件概率P(x｜c)和P(x)來表示后驗概率。

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

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

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

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

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

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

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

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

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

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

(五)其他分類方法

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

1、基于案例的推理分類法?；诎咐耐评矸诸惙ㄊ腔谝蟮?，其存放的樣本是復雜的符號描述。當給定一個待分類的新案例時，基于案例的推理首先檢查是否存在一個同樣的訓練案例。如果找到一個，則返回附在該案例上的解。如果找不到同樣的案例，則基于案例的推理將搜索具有類似于新案例成分的訓練案例，這些訓練案例可視為新案例的鄰接者。

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

三、結語

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

作者簡介：

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