數(shù)據(jù)挖掘中的分類算法綜述

◆魏茂勝

?

數(shù)據(jù)挖掘中的分類算法綜述

◆魏茂勝

(中國(guó)礦業(yè)大學(xué)(北京)機(jī)電與信息工程學(xué)院 北京 100083)

隨著網(wǎng)絡(luò)數(shù)據(jù)爆炸式增長(zhǎng)，數(shù)據(jù)庫(kù)規(guī)模日益擴(kuò)大，越來(lái)越多的人開(kāi)始研究數(shù)據(jù)挖掘，作為數(shù)據(jù)挖掘中關(guān)鍵技術(shù)的分類算法也同樣受到了廣泛關(guān)注。對(duì)數(shù)據(jù)挖掘中典型分類算法的總結(jié)和比較，有利于開(kāi)發(fā)者高效地選擇算法，也有利于研究者對(duì)算法改進(jìn)提高。

數(shù)據(jù)挖掘；分類算法；綜述

0 概述

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

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

1 分類算法

分類算法有很多，本文將重點(diǎn)介紹決策樹(shù)、貝葉斯、遺傳、人工神經(jīng)網(wǎng)絡(luò)、基于關(guān)聯(lián)規(guī)則分類算法。

1.1決策樹(shù)分類算法

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

決策樹(shù)通過(guò)對(duì)實(shí)例集的分析歸納進(jìn)行學(xué)習(xí)，具備多概念學(xué)習(xí)的能力，使用簡(jiǎn)便快捷，應(yīng)用領(lǐng)域廣泛。對(duì)用無(wú)結(jié)構(gòu)的屬性-值對(duì)表示的大規(guī)模實(shí)例數(shù)據(jù)進(jìn)行分類學(xué)習(xí)時(shí)，決策樹(shù)算法是較優(yōu)的選擇。目前使用較多的決策樹(shù)學(xué)習(xí)算法有ID3、C4.5[2]、SLIQ[3]和SPRINT[4]。

ID3作為一種決策樹(shù)學(xué)習(xí)算法，可以便捷地描述概念屬性-值的信息結(jié)構(gòu)，算法簡(jiǎn)單容易實(shí)現(xiàn)且分類速度快。目前許多的被人熟知的決策樹(shù)算法都是由該核心算法演變而來(lái)，例如C4.5算法。該算法通過(guò)由上而下的貪心算法構(gòu)造決策樹(shù)進(jìn)行學(xué)習(xí)。構(gòu)造過(guò)程由選擇確定在根節(jié)點(diǎn)測(cè)試的屬性開(kāi)始，依據(jù)最大的信息增益和最小熵的標(biāo)準(zhǔn)來(lái)選擇決策樹(shù)上每個(gè)節(jié)點(diǎn)的被測(cè)試屬性，對(duì)象集則由測(cè)試結(jié)果劃分。多次進(jìn)行該過(guò)程直至某一子樹(shù)的葉子節(jié)點(diǎn)與分類標(biāo)準(zhǔn)為同一類為止。

1.2貝葉斯分類算法

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

樸素貝葉斯分類算法是應(yīng)用最為廣泛的一種基礎(chǔ)貝葉斯算法，方法簡(jiǎn)單，運(yùn)算速度快。但因?yàn)樨惾~斯定理的成立依賴于嚴(yán)格的屬性值獨(dú)立性假設(shè)前提，而此假設(shè)前提在實(shí)際應(yīng)用中常常是錯(cuò)誤的，因此這種分類算法的準(zhǔn)確率會(huì)降低。其他降低獨(dú)立性假設(shè)要求的貝葉斯算法相繼被研究者提出，例如TAN算法[5]。

1.3遺傳算法

遺傳算法是由生物進(jìn)化理論演變而來(lái)的高效搜索和隨機(jī)優(yōu)化算法，是自然科學(xué)和計(jì)算機(jī)算法相結(jié)合的一個(gè)重要突破。該算法借助自然進(jìn)化原理，把求解問(wèn)題的過(guò)程轉(zhuǎn)變成根據(jù)染色體上的基因?qū)ふ疫m應(yīng)度高的染色體的過(guò)程。該算法綜合了定向搜素與隨機(jī)搜索的優(yōu)點(diǎn)從而具有良好的全局搜索能力，避免了大多數(shù)優(yōu)化方法容易陷入局部最優(yōu)的缺點(diǎn)。

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

1.4人工神經(jīng)網(wǎng)絡(luò)算法

神經(jīng)網(wǎng)絡(luò)是一種由許多神經(jīng)元節(jié)點(diǎn)按照某些特定規(guī)則連接構(gòu)成的信息處理網(wǎng)絡(luò)。該算法可以模擬人腦的功能對(duì)訓(xùn)練樣本進(jìn)行學(xué)習(xí)分類，它從輸出節(jié)點(diǎn)反向傳播由誤差引起的權(quán)值調(diào)整，其中網(wǎng)絡(luò)的信息分布式存儲(chǔ)于網(wǎng)絡(luò)各個(gè)單元之間的連接權(quán)系數(shù)中。目前主要的神經(jīng)網(wǎng)絡(luò)有自組織網(wǎng)絡(luò)、前向神經(jīng)網(wǎng)絡(luò)和后向神經(jīng)網(wǎng)絡(luò)，分類算法主要采用前向神經(jīng)網(wǎng)絡(luò)。BP網(wǎng)絡(luò)由于其良好的非線性逼近能力與分類能力而被廣泛地應(yīng)用。

BP神經(jīng)網(wǎng)絡(luò)屬于多層前向網(wǎng)絡(luò)，該網(wǎng)絡(luò)從輸入節(jié)點(diǎn)經(jīng)過(guò)各個(gè)隱含層向輸出層正向傳遞信號(hào)，如果輸出結(jié)果未達(dá)到期望值，則由輸出節(jié)點(diǎn)反向傳播誤差，進(jìn)行權(quán)值修正直至得到期望輸出。其中每層節(jié)點(diǎn)的輸出由上層節(jié)點(diǎn)決定，同層節(jié)點(diǎn)間沒(méi)有耦合。只要有足夠多的隱含層單元就能保證以任意的精度逼近任意的函數(shù)。

1.5基于關(guān)聯(lián)規(guī)則的分類算法

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

Apriori算法是一種通過(guò)迭代方法尋找所需頻繁項(xiàng)集的基礎(chǔ)算法。該算法可分為三步實(shí)現(xiàn)：首先，找到出現(xiàn)的頻繁性大于等于預(yù)定義的最小支持度的所有項(xiàng)集來(lái)組成頻繁項(xiàng)集；接著，通過(guò)頻繁項(xiàng)集，以最小支持度和最小可信度為標(biāo)準(zhǔn)生成強(qiáng)關(guān)聯(lián)規(guī)則;最后，使用之前得到的頻集生成右部只有一項(xiàng)的規(guī)則，生成的這些規(guī)則只能包含集合項(xiàng)。通過(guò)這些產(chǎn)生的規(guī)則就可以留下可信度大于給定的最小可信度的規(guī)則。

2 結(jié)語(yǔ)

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

[1]程建華.數(shù)據(jù)挖掘分類算法研究綜述[J].中國(guó)高新技術(shù)企業(yè)，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.