丁 浩

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

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

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

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

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

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

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

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

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

決策樹（Decision Tree，DC）分類法是一種以數(shù)據(jù)集為基礎(chǔ)，從一組無次序、無規(guī)則的樣本數(shù)據(jù)中推理出分類規(guī)則的歸納學(xué)習(xí)算法．是將構(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ī)則．③準(zhǔn)確性高：使用決策樹分類法可以得出準(zhǔn)確率很高的分類規(guī)則，而且可以清楚地看出哪些字段是比較重要的．

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

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

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

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

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

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

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

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

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

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

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

圖4 樸素貝葉斯模型

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

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

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

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

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

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

2．4 其他分類算法

基于數(shù)據(jù)庫的分類算法，如MIND（mining in database）算法，采用數(shù)據(jù)庫中用戶定義的函數(shù)實現(xiàn)發(fā)現(xiàn)分類規(guī)則．該算法分類準(zhǔn)確度高，執(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］．

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

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

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

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

4 結(jié)束語

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

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

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

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

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

［5］陶新民，郝思媛，張冬雪，等．不均衡數(shù)據(jù)分類算法的綜述［J］．重慶郵電大學(xué)學(xué)報：自然科學(xué)版，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．