數據挖掘中的分類算法綜述

◆魏茂勝

?

數據挖掘中的分類算法綜述

◆魏茂勝

(中國礦業大學(北京)機電與信息工程學院 北京 100083)

隨著網絡數據爆炸式增長，數據庫規模日益擴大，越來越多的人開始研究數據挖掘，作為數據挖掘中關鍵技術的分類算法也同樣受到了廣泛關注。對數據挖掘中典型分類算法的總結和比較，有利于開發者高效地選擇算法，也有利于研究者對算法改進提高。

數據挖掘；分類算法；綜述

0 概述

基于數據庫的知識發現是伴隨著人工智能和數據庫的快速發展而被提出的計算機技術，它通過某種算法從大量的數據中搜索其中隱藏的有用信息，機器學習、模式識別、統計學、知識獲取、智能數據庫、專家系統和高性能計算等眾多領域都與該技術息息相關[1]。數據挖掘(Data Mining)是基于數據庫的知識發現中的關鍵步驟，通常將其中的知識學習階段稱為數據挖掘。

分類(Classification)算法是數據挖掘的關鍵技術，它通過對數據訓練集的分析研究，發現分類規則，從而具備預測新數據類型的能力。分類算法主要包括兩個階段:構建模型階段:通過分析學習已知的訓練數據集，訓練并構建一個準確率可以接受的模型，該模型用于描述特定的數據類集;使用模型階段:使用訓練后的模型對未知的數據對象進行分類。目前許多分類算法已被各領域研究者提出，不同的分類算法適用于不同的情況，這使得開發者對分類算法的選擇存在諸多困惑。本文介紹了幾種經典的數據分類算法，并分析了各自的特性，以便于開發者和研究者對分類算法的選擇和研究。

1 分類算法

分類算法有很多，本文將重點介紹決策樹、貝葉斯、遺傳、人工神經網絡、基于關聯規則分類算法。

1.1決策樹分類算法

決策樹(Decision Tree)是由一系列節點和分支組成的樹狀圖，其中分支由節點和子節點組成。節點表示學習或決策過程中需要考慮的屬性，不同的分支則由不同的屬性構成。利用某事例的屬性值，從決策樹的樹根節點往下搜索，直至葉子節點，便可對該事例進行學習，做出決策。學習或決策的最終結果由葉子節點表示。

決策樹通過對實例集的分析歸納進行學習，具備多概念學習的能力，使用簡便快捷，應用領域廣泛。對用無結構的屬性-值對表示的大規模實例數據進行分類學習時，決策樹算法是較優的選擇。目前使用較多的決策樹學習算法有ID3、C4.5[2]、SLIQ[3]和SPRINT[4]。

ID3作為一種決策樹學習算法，可以便捷地描述概念屬性-值的信息結構，算法簡單容易實現且分類速度快。目前許多的被人熟知的決策樹算法都是由該核心算法演變而來，例如C4.5算法。該算法通過由上而下的貪心算法構造決策樹進行學習。構造過程由選擇確定在根節點測試的屬性開始，依據最大的信息增益和最小熵的標準來選擇決策樹上每個節點的被測試屬性，對象集則由測試結果劃分。多次進行該過程直至某一子樹的葉子節點與分類標準為同一類為止。

1.2貝葉斯分類算法

貝葉斯(Bayes)分類算法在貝葉斯公式的基礎上提出，是一種利用概率統計知識進行分類的算法。該分類算法在先驗概率與類條件概率已知的情況下，通過貝葉斯定理計算一個類別未知的給定樣本屬于各個類別的概率，并且選擇其中概率最大的類別作為該樣本的確定類別。

樸素貝葉斯分類算法是應用最為廣泛的一種基礎貝葉斯算法，方法簡單，運算速度快。但因為貝葉斯定理的成立依賴于嚴格的屬性值獨立性假設前提，而此假設前提在實際應用中常常是錯誤的，因此這種分類算法的準確率會降低。其他降低獨立性假設要求的貝葉斯算法相繼被研究者提出，例如TAN算法[5]。

1.3遺傳算法

遺傳算法是由生物進化理論演變而來的高效搜索和隨機優化算法，是自然科學和計算機算法相結合的一個重要突破。該算法借助自然進化原理，把求解問題的過程轉變成根據染色體上的基因尋找適應度高的染色體的過程。該算法綜合了定向搜素與隨機搜索的優點從而具有良好的全局搜索能力，避免了大多數優化方法容易陷入局部最優的缺點。

與自然界相似，遺傳算法求解問題時并不需要對該問題有所了解，它的任務只是對算法過程中產生的所有染色體進行評價，然后根據適應度值的大小篩選染色體，其中適應度值高的染色體繁殖下一代的機會更大。染色體是遺傳算法中由隨機方式產生的若干個數字編碼，這些染色體組成了初始種群；適應度函數的作用是用數值大小來評價每個個體，適應度低的個體會被淘汰，適應度高的個體參加遺傳操作，通過交叉、變異等遺傳操作后的染色體組成下一代新的種群。再對這個新種群進行下一輪進化直到得出最優解或達到最大的迭代次數。

1.4人工神經網絡算法

神經網絡是一種由許多神經元節點按照某些特定規則連接構成的信息處理網絡。該算法可以模擬人腦的功能對訓練樣本進行學習分類，它從輸出節點反向傳播由誤差引起的權值調整，其中網絡的信息分布式存儲于網絡各個單元之間的連接權系數中。目前主要的神經網絡有自組織網絡、前向神經網絡和后向神經網絡，分類算法主要采用前向神經網絡。BP網絡由于其良好的非線性逼近能力與分類能力而被廣泛地應用。

BP神經網絡屬于多層前向網絡，該網絡從輸入節點經過各個隱含層向輸出層正向傳遞信號，如果輸出結果未達到期望值，則由輸出節點反向傳播誤差，進行權值修正直至得到期望輸出。其中每層節點的輸出由上層節點決定，同層節點間沒有耦合。只要有足夠多的隱含層單元就能保證以任意的精度逼近任意的函數。

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

基于關聯規則(Classification based on association rule，CBA)的分類算法的提出彌補了貝葉斯分類算法需要大量樣本的不足。CBA算法根據實例集中的關聯規則來構造分類器，該過程通常需要兩個步驟:首先，發現所有的右部為類別屬性值的類別關聯規則，這種規則稱為CAR;接著，在所有已找到的CAR中選擇置信度最高的關聯規則來覆蓋訓練集。該分類算法發現規則較為全面，所以其分類結果也較準確，是一種潛力很大的分類算法，Aprior是基于關聯規則的經典算法。

Apriori算法是一種通過迭代方法尋找所需頻繁項集的基礎算法。該算法可分為三步實現：首先，找到出現的頻繁性大于等于預定義的最小支持度的所有項集來組成頻繁項集；接著，通過頻繁項集，以最小支持度和最小可信度為標準生成強關聯規則;最后，使用之前得到的頻集生成右部只有一項的規則，生成的這些規則只能包含集合項。通過這些產生的規則就可以留下可信度大于給定的最小可信度的規則。

2 結語

數據挖掘技術的實用性和重要性程度日益提高，許多分類算法也相繼被提出，除了本文所介紹的幾種之外，常用的分類算法還有基于數據庫的分類算法、粗糙集分類算法、基于支持向量機的分類算法以及K-最近鄰分類算法等等。每種算法都有各自的特性，沒有一種算法可以適用于所有情況，了解每種算法的優缺點有助于我們更好地使用和研究。

[1]程建華.數據挖掘分類算法研究綜述[J].中國高新技術企業，2008.

[2]Quinlan J R.C4.5:programs for machine learning[M]. DBLP,1993.

[3]Chandra B,Varghese P P.Fuzzy SLIQ decision tree algorithm[J].IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics A Publication of the IEEE Systems Man & Cybernetics Society,2008.

[4]Shafer J C.Agrawal R.Mehta M. SPRINT: A Scalable Parallel Classifier for Data Mining[C]// Proceedings of the 22th International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc,2000.

[5]Liao Y,Zeng X,Song T,et al.Stock Price Forecast Using Tree Augmented Na?ve (TAN) Bayes[M]// Proceedings of The Eighth International Conference on Bio-Inspired Computing:Theories and Applications (BIC-TA),2013.