數(shù)據(jù)挖掘中常用分類算法的分析比較＊

丁 浩

（安徽工商職業(yè)學院 國際貿(mào)易系，安徽 合肥231131）

1 數(shù)據(jù)挖掘中的分類問題及其研究現(xiàn)狀

從本質(zhì)上來說，數(shù)據(jù)挖掘（Data Mining）就是“從大量數(shù)據(jù)中獲取有效的、潛在有用的并且最終可理解的知識或模式的非平凡過程”［1］．可以這樣理解，就是從大量的數(shù)據(jù)里提取或者“挖掘”知識．數(shù)據(jù)挖掘涉及統(tǒng)計學、數(shù)據(jù)庫、人工智能和機器學習等多個領(lǐng)域，是一門交叉學科．其工作的簡要過程，如圖1所示．

圖1 數(shù)據(jù)挖掘的一般過程

數(shù)據(jù)挖掘的主要任務有分類、預測、關(guān)聯(lián)分析、聚類、時序模式分析及偏差分析等．數(shù)據(jù)分類是數(shù)據(jù)挖掘中一項非常重要的技術(shù)，一直是研究的熱點之一．由于不同的分類算法會產(chǎn)生不同的分類器，而分類器的好壞又會直接影響到分類結(jié)果的準確性和數(shù)據(jù)挖掘的效率，因而當對大規(guī)模的海量數(shù)據(jù)進行分類時，選擇最合適的分類算法是非常關(guān)鍵的．

近年來，國內(nèi)外對數(shù)據(jù)挖掘分類算法的研究主要集中在以下兩個方面：一是直接將傳統(tǒng)的分類算法或者組合應用到實際案例中，開發(fā)出各種應用系統(tǒng)；二是對傳統(tǒng)分類算法進行改進或在小數(shù)據(jù)集上驗證各種改良算法．而對各種分類算法進行深入的對比研究的并不多［2］．本文對各種分類算法進行深入的分析比較，總結(jié)了各自的優(yōu)缺點及適用情境，為今后各種分類方法的選擇應用提供參考和借鑒，也便于相關(guān)研究者明確算法的改進點和研究方向．

2 常用分類算法的分析比較

目前數(shù)據(jù)挖掘中使用頻率最高的分類算法主要有三類：①基于決策樹的分類算法，如ID3、C4．5等；②基于神經(jīng)網(wǎng)絡的分類算法，如人工神經(jīng)網(wǎng)絡；③基于統(tǒng)計學的分類算法，如樸素貝葉斯、貝葉斯網(wǎng)絡等．

2．1 基于決策樹的分類算法

決策樹（Decision Tree，DC）分類法是一種以數(shù)據(jù)集為基礎(chǔ)，從一組無次序、無規(guī)則的樣本數(shù)據(jù)中推理出分類規(guī)則的歸納學習算法．是將構(gòu)成決策方案的有關(guān)因素以樹形圖的方式表現(xiàn)出來，并據(jù)以分析和選擇決策方案的一種系統(tǒng)分析分類方法，能夠形象地顯示出整個決策問題在不同階段及各時間節(jié)點上的決策過程，層次分明，邏輯清晰，形象直觀，表示出來很像一棵樹［3］．例如，一個年輕女孩在別人給她介紹男友時，是否去見面的決策過程（圖2），就是一個簡單的決策樹．

圖2 決策樹示意圖

常用的決策樹算法有ID3算法、C4．5算法以及它們的升級版ID4、C5．0算法等．

與其他分類算法相比，決策樹算法有如下優(yōu)點：①易于理解和實現(xiàn)：對數(shù)據(jù)挖掘使用者來說，這種易理解性是一個非常顯著的優(yōu)點．②速度快：計算量相對較小，且容易轉(zhuǎn)化成分類規(guī)則．③準確性高：使用決策樹分類法可以得出準確率很高的分類規(guī)則，而且可以清楚地看出哪些字段是比較重要的．

決策樹算法也存在一些缺點：首先，對于連續(xù)型變量必須離散化才能被學習和分類．其次，對于有時間順序的數(shù)據(jù)，需要進行很多預處理，從而加大了工作量．還有，當類別太多時使用決策樹算法，錯誤的可能性就會增加得比較快．

為此，有人提出了一些改進的決策樹算法，如SLIQ（監(jiān) 督學 習 任務，super－vised lear ning in quest）算法．該算法在決策樹的構(gòu)造過程中隨記錄個數(shù)和屬性個數(shù)增長，采用了預排序以及廣度優(yōu)先增長策略［3］．因此在一定程度上具有良好的可擴展性．但仍然存在著一些不足：一是該算法需要將類別列表存放于內(nèi)存，能夠處理的數(shù)據(jù)集大小必然就受到限制；二是采用了預排序，但排序算法的復雜度本身就是一個問題．因此，SLIQ算法幾乎不可能達到隨記錄數(shù)增長的線性可擴展性．于是又有學者提出SPRINT（可擴展并行感應決策樹，scalable parallelizable induction of decision trees）算法，以減少駐留內(nèi)存的數(shù)據(jù)量，并且使尋找每個結(jié)點的最優(yōu)分裂標準變得更簡單，但該算法對非分裂屬性的處理又很困難［3］．

2．2 基于神經(jīng)網(wǎng)絡的分類算法

神經(jīng)網(wǎng)絡（Neural Net wor k，NN），全稱人工神經(jīng)網(wǎng)絡，是模擬人腦結(jié)構(gòu)和功能、由大量的“神經(jīng)元”（或稱節(jié)點）相互聯(lián)接構(gòu)成的一種可以進行分布式、并行動態(tài)信息處理的數(shù)學模型．一個神經(jīng)網(wǎng)絡由一個多層神經(jīng)元結(jié)構(gòu)組成，每一層神經(jīng)元擁有輸入和輸出（同時也是后一層的輸入）．如一種常見的多層結(jié)構(gòu)的前饋網(wǎng)絡由三個層次結(jié)構(gòu)組成：輸入層、隱含層和輸出層［4］，如圖3所示．

圖3 神經(jīng)網(wǎng)絡模型

神經(jīng)網(wǎng)絡的優(yōu)點很多：①分類精度高；②良好的魯棒性；③較強的自主學習和記憶能力；④超強的容錯能力；⑤可用于求解一些非常復雜的問題，因為神經(jīng)網(wǎng)絡具有很強的非線性擬合能力，甚至可以通過對變量反復多次進行線性組合后再進行非線性變換，從而可映射任意復雜的非線性關(guān)系．因此，在非線性問題的處理上神經(jīng)網(wǎng)絡堪為首選．

但是，神經(jīng)網(wǎng)絡算法也有其不足之處：其最突出問題是，要真正建立一個好的神經(jīng)網(wǎng)絡其實非常困難，工作量很大，時間周期也很長；另一個不足之處是對網(wǎng)絡的解釋，難以從網(wǎng)絡中提取規(guī)則．這些使得神經(jīng)網(wǎng)絡在其出現(xiàn)初期曾經(jīng)一度不被看好．為此，有學者提出在提取規(guī)則之前對網(wǎng)絡進行前剪枝，以刪除那些對分類準確性影響極小或者幾乎沒有影響的鏈枝和神經(jīng)元，從而簡化生成的網(wǎng)絡．后來又出現(xiàn)了一些用訓練過的神經(jīng)網(wǎng)絡提取規(guī)則的算法，“使得神經(jīng)網(wǎng)絡用于數(shù)據(jù)挖掘逐漸顯示出其強大的生命力”［4］．但是神經(jīng)網(wǎng)絡算法對海量數(shù)據(jù)處理時仍存在時間效率問題，因而需要同其他方法結(jié)合使用，方可達到理想的效果．

2．3 基于統(tǒng)計學的分類算法

基于統(tǒng)計學的分類算法，其最大特點是用概率來表示所有形式的不確定性，推理或?qū)W習都用概率規(guī)則來進行．換言之，就是在各種條件存在不確定而僅知其出現(xiàn)概率的情況下完成推理和決策任務．

樸素貝葉斯（Naive Bayes，NB）分類是統(tǒng)計學分類算法中最經(jīng)典的一種，算法也十分簡單：“對于給定的待分類項，求解在此項出現(xiàn)的條件下各個類別出現(xiàn)的概率，然后看哪個最大，就認為此待分類項屬于哪個類別”［1］．樸素貝葉斯分類算法基于獨立性假設，也就是設在給定類別C的條件下，所有的屬性xi（i＝1，2，…n）相互獨立．即：

從而建立一種相對簡單的分類模型——樸素貝葉斯模型，如圖4所示．模型中各個屬性變量xi獨立地作用于類變量C．

圖4 樸素貝葉斯模型

樸素貝葉斯分類算法的主要特點和優(yōu)勢有：①算法邏輯簡單，易于實現(xiàn)；②時間、空間開銷較小，占用的系統(tǒng)資源較少，因而速度快；③有堅實的數(shù)學基礎(chǔ)，分類精度較高；④性能穩(wěn)定，即具有良好的魯棒性．

盡管是帶著一些樸素思想和過于簡單化的假設，但樸素貝葉斯分類器在很多復雜的現(xiàn)實問題的處理中仍能夠取得相當好的效果．對各種分類法比較的有關(guān)研究表明：樸素貝葉斯分類法在分類性能上并不遜色于決策樹和神經(jīng)網(wǎng)絡等其他方法．實踐證明，在處理大規(guī)模數(shù)據(jù)庫時，樸素貝葉斯分類的運算性能和分類準確性甚至優(yōu)于其他方法［5］．因而在實際應用中，樸素貝葉斯分類被廣泛采用．

當然其缺點也顯而易見，就是必須以獨立性假設為前提，因為該限制在現(xiàn)實中往往很難滿足，從而可能會導致分類準確率下降，這在一定程度上限制了樸素貝葉斯算法的適用范圍．

于是，又就出現(xiàn)了一些降低獨立性要求的貝葉斯算法，如貝葉斯網(wǎng)絡（Bayes Net wor k，BN），允許在變量子集間定義類條件獨立性，采用一種帶有概率注釋的有向無環(huán)圖來描述變量之間關(guān)系．如描述Smoking（吸煙）、l ung Cancer（肺癌）、Br onchitis（支氣管炎）、X－ray（需照X光）以及Dyspnea（呼吸困難）之間的因果關(guān)系的貝葉斯網(wǎng)絡（圖5）．

圖5 貝葉斯網(wǎng)絡模型

此外，改進的貝葉斯分類算法還有樹擴展樸素貝葉斯TAN（Tree Aug mented Naive Bayes）算法等．但是，所有基于統(tǒng)計學的貝葉斯分類算法在處理非線性樣本數(shù)據(jù)和含噪聲或孤立點數(shù)據(jù)時，其分類準確性仍存在問題．

2．4 其他分類算法

基于數(shù)據(jù)庫的分類算法，如MIND（mining in database）算法，采用數(shù)據(jù)庫中用戶定義的函數(shù)實現(xiàn)發(fā)現(xiàn)分類規(guī)則．該算法分類準確度高，執(zhí)行速度快，有良好的可伸縮性，缺點是參數(shù)取值需用戶完成等．

基于關(guān)聯(lián)規(guī)則的分類算法，如CBA（classification based on association）算法．該算法分兩步：①搜索所有右部為類別屬性值的類別關(guān)聯(lián)規(guī)則；②選擇具有最高置信度的規(guī)則作為可能規(guī)則．這兩步都具有線性可伸縮性．基于關(guān)聯(lián)規(guī)則的分類算法還有CAEP、JEP、CMAR等［6］．

基于類比學習的K－最臨近分類算法，是一種懶散的學習法，由于要存儲所有訓練樣本，因而在大的數(shù)據(jù)集上學習會出現(xiàn)困難．

此外，還有一些方法在商業(yè)化數(shù)據(jù)挖掘中較少用于分類，但隨著時代進步和新技術(shù)的不斷發(fā)展似乎也變得日趨流行，如基于案例的推理分類法CBR、遺傳算法、粗糙集和模糊集方法等等．和前面幾種相對成熟的分類算法相比，這些方法在分類準確率、時間效率、魯棒性、可解釋性及可伸縮性等方面都存在一定的差距，筆者不再一一分析介紹．

3 分類技術(shù)發(fā)展展望

雖然現(xiàn)在分類算法已有很多，有的還很成熟，但通過各種算法比較分析以及從國內(nèi)外研究與應用的實際效果來看，尚未發(fā)現(xiàn)一種方法絕對優(yōu)于其他方法．如今已進入大數(shù)據(jù)時代，面對海量數(shù)據(jù)，各種算法在準確性、時間效率、魯棒性等方面都或多或少地出現(xiàn)了一些問題．因此，近年來越來越多的人采取將各種方法有機結(jié)合，取長補短，組合應用到數(shù)據(jù)挖掘中，取得了較好的效果．為了解決目前數(shù)據(jù)挖掘分類中出現(xiàn)的新問題，一些學者甚至已經(jīng)開始嘗試將人工智能領(lǐng)域最新技術(shù)——混合智能系統(tǒng)引入，進行模型整合．但是，與數(shù)據(jù)挖掘分類算法怎樣結(jié)合以及模型整體結(jié)構(gòu)、算法參數(shù)選取等［7］又成為需要解決的富有挑戰(zhàn)性的新問題．

4 結(jié)束語

本文在對數(shù)據(jù)挖掘中分類算法的研究現(xiàn)狀進行分析的基礎(chǔ)上，對目前三種使用頻率最高的分類算法，即決策樹算法、神經(jīng)網(wǎng)絡算法和貝葉斯算法進行了詳細的分析討論，總結(jié)了各種算法的優(yōu)點、缺陷和適用情境．對其他分類算法也作了一些簡單的分析介紹．此外，還對數(shù)據(jù)挖掘分類技術(shù)的未來發(fā)展進行了展望．以期為今后各種分類方法在實際問題中的選擇應用提供一些參考和借鑒，以便更有效地解決相關(guān)問題．同時也希望可以有助于相關(guān)研究者進一步明確各種算法的改進點和今后研究的努力方向．

［1］范明，孟小峰．數(shù)據(jù)挖掘概念與技術(shù)［M］．北京：機械工業(yè)出版社，2007．

［2］王明星．數(shù)據(jù)挖掘算法優(yōu)化研究與應用［D］．合肥：安徽大學，2014．

［3］張曼，邵明文，史鴻戩．基于包含度的決策樹分類算法的改進［J］．電子技術(shù)與軟件工程，2015（9）：212－214．

［4］覃梅．數(shù)據(jù)挖掘分類算法在信用卡風險管理中的應用［J］．現(xiàn)代計算機：專業(yè)版，2013（19）：13－16．

［5］陶新民，郝思媛，張冬雪，等．不均衡數(shù)據(jù)分類算法的綜述［J］．重慶郵電大學學報：自然科學版，2013，25（1）：102－110．

［6］LI Xiang，LI Tao．Classification Algorithm of Kernelbased In Adaboost［J］．Co mputer Knowledge and Technology，2011，7（28）：6970－6979．

［7］ZHU Ming，TAO Xin min．The SV M Classifier For Unbalanced Data Based on Combination of RU－Undersample And SMOTE［J］．Inf or mation Technology，2012（1）：39－41．