數(shù)據(jù)挖掘經(jīng)典算法研究

光峰,姚程寬,盧燦舉,曹立勇,詹喆

(1.安慶醫(yī)藥高等?？茖W(xué)校 公共基礎(chǔ)部，安徽　安慶 246003;2.合肥電子工程學(xué)院，安徽　合肥 230037)

?

數(shù)據(jù)挖掘經(jīng)典算法研究

光峰1,姚程寬1,盧燦舉2,曹立勇1,詹喆1

(1.安慶醫(yī)藥高等專科學(xué)校 公共基礎(chǔ)部，安徽安慶 246003;2.合肥電子工程學(xué)院，安徽合肥 230037)

摘要：數(shù)據(jù)挖掘是近年來(lái)計(jì)算機(jī)科學(xué)領(lǐng)域非常熱門的研究方向之一，是由數(shù)據(jù)倉(cāng)庫(kù)技術(shù)和機(jī)器學(xué)習(xí)發(fā)展而來(lái).數(shù)據(jù)挖掘是指從海量的數(shù)據(jù)中找出隱藏的關(guān)系，是數(shù)據(jù)分析的高級(jí)階段.在對(duì)數(shù)據(jù)挖掘的算法研究中，涌現(xiàn)出了很多優(yōu)秀的算法.本文選擇了IEEE評(píng)選出的十大經(jīng)典算法，對(duì)其中的每個(gè)算法的原理、背景、發(fā)展、優(yōu)缺點(diǎn)、應(yīng)用領(lǐng)域等做了深入淺出的介紹，為相關(guān)專業(yè)領(lǐng)域的學(xué)習(xí)及研究提供參考.

關(guān)鍵詞：數(shù)據(jù)挖掘；大數(shù)據(jù)；聚類；分類；預(yù)測(cè)；關(guān)聯(lián)規(guī)則

數(shù)據(jù)挖掘的英文全稱為Data Mining，目前數(shù)據(jù)挖掘的應(yīng)用領(lǐng)域很廣泛，涉及金融、電信、網(wǎng)絡(luò)、工業(yè)、農(nóng)業(yè)等眾多行業(yè).在過(guò)去20多年的發(fā)展中，很多的科研人員對(duì)于數(shù)據(jù)挖掘的算法研究和改善做出了杰出的貢獻(xiàn)，使得后續(xù)的科研人員可以較為方便的使用這些成果.其中的很多算法在數(shù)據(jù)挖掘的研究中做出了巨大的成就，產(chǎn)生了深遠(yuǎn)的影響.IEEE(電子電器工程師協(xié)會(huì))在2006年經(jīng)過(guò)投票，評(píng)選出數(shù)據(jù)挖掘的10大算法，其中的每個(gè)算法都可以稱為數(shù)據(jù)挖掘領(lǐng)域的經(jīng)典算法[1-2]，下面將逐一介紹這10種算法.

1經(jīng)典算法

1.1C4.5算法

C4.5算法屬于決策樹算法的一種，是由ID3算法改進(jìn)而來(lái).從數(shù)據(jù)分析從而得到?jīng)Q策樹的方法就是通常所說(shuō)的決策樹算法，簡(jiǎn)稱為決策樹或決策樹學(xué)習(xí).ID3誕生于20世紀(jì)70年代，是構(gòu)造決策樹的一種算法，準(zhǔn)確說(shuō)是屬于分類預(yù)測(cè)的貪心算法.由于算法自身的一些缺陷，J.Ross Quinlan對(duì)ID3算法進(jìn)行了改進(jìn)，提出了C4.5算法[3].

C4.5算法不僅保留了ID3算法的全部?jī)?yōu)點(diǎn)，同時(shí)，改進(jìn)了ID3的兩個(gè)主要缺點(diǎn)：

(1)在對(duì)分支屬性決策時(shí)，ID3使用信息增益這一指標(biāo)進(jìn)行度量，導(dǎo)致選擇偏向于取值多的屬性，很多情況下，這些屬性是無(wú)效數(shù)據(jù).而C4.5則使用的是信息增益率這個(gè)指標(biāo)，客服了這一缺陷.

(2)ID3算法只能取離散數(shù)據(jù)，C4.5屬性值可以是既可以是離散值也可以是連續(xù)值，因?yàn)镃4.5能夠?qū)B續(xù)數(shù)據(jù)進(jìn)行離散化處理.

C4.5的分類準(zhǔn)確性高，缺點(diǎn)是算法的效率比較低.

1.2K-Means算法

K-Means算法是聚類算法的典型代表.算法簡(jiǎn)單，以距離為核心，在機(jī)器學(xué)習(xí)領(lǐng)域得到了極為廣泛的應(yīng)用.算法的主導(dǎo)思想為：距離近的，相似度高；距離遠(yuǎn)的，相似度低[4].

K-Means算法簡(jiǎn)單且易于理解，當(dāng)樣本類別的分界線明顯(區(qū)別較大)時(shí)，聚類效果好.且算法高效，適合處理大數(shù)據(jù).K-Means算法的缺點(diǎn)也很明顯，即算法開始時(shí)就要確定K(樣本類別數(shù))，而K恰恰是難以估計(jì)的，如果K取值不當(dāng)，算法會(huì)得不到有效聚類結(jié)果.可以采用遺傳算法、蟻群算法等解決這一問(wèn)題.

1.3SVM算法

SVM算法全稱是Support Vector Machine，中文翻譯成支持向量機(jī)，是一種高效的機(jī)器學(xué)習(xí)算法，是上世紀(jì)90年代由Vapnik提出.支持向量機(jī)立足于線性可分，對(duì)于線性不可分的樣本，通過(guò)一個(gè)非線性的映射，將樣本空間映射到高維的空間中，在高維空間中問(wèn)題就變成了線性可分的問(wèn)題.如從二維空間映射到三維空間就是一個(gè)從低維到高維的映射，二維空間中不能夠線性可分的問(wèn)題在三維空間中很容易線性可分[5].

從低維到高維的映射，一般會(huì)增加算法的復(fù)雜度，但是SVM使用了核函數(shù)有效解決了這一問(wèn)題，使得算法擁有較低的復(fù)雜度.SVM的缺點(diǎn)是核函數(shù)的參數(shù)要事先確定，而不同的核參數(shù)有時(shí)會(huì)產(chǎn)生差距較大的結(jié)果.同時(shí)，SVM在處理多類問(wèn)題時(shí)，效果不是很明顯.

1.4Apriori算法

Apriori算法是一種關(guān)聯(lián)規(guī)則算法，是上個(gè)世紀(jì)90年代由Agrawal和Ramakrishnan Srikant提出的.關(guān)聯(lián)規(guī)則就是在數(shù)據(jù)集中找出個(gè)體樣本之間的潛在關(guān)系，關(guān)聯(lián)規(guī)則的另一個(gè)代名詞早已是家喻戶曉：購(gòu)物籃分析(Market Basket Analysis)，這來(lái)源于一個(gè)非常成功的商業(yè)應(yīng)用案例，即：啤酒和尿布.目前的關(guān)聯(lián)規(guī)則應(yīng)用也非常廣泛，涉及商業(yè)、醫(yī)療、保險(xiǎn)、網(wǎng)絡(luò)和通訊等等[6].

Apriori算法分為兩個(gè)階段，是基于先驗(yàn)知識(shí)的上次頻繁項(xiàng)遞推生成本次頻繁項(xiàng).Apriori算法的缺點(diǎn)是只能處理類別標(biāo)示，不能直接處理數(shù)值型數(shù)據(jù).

1.5EM算法

EM算法的英文全稱是Expectation Maximization Algorithm，中文翻譯成最大期望值算法或期望最大化算法.EM算法是由Dempster，Laind，Rubin 于 上世紀(jì)70年代提出.EM算法是極大似然估計(jì)的一個(gè)特例，即：包含了隱變量(hidden variable).這一特性，使得EM算法在某些領(lǐng)域有著不可替代的作用，比如：數(shù)據(jù)不完整、數(shù)據(jù)有噪音、數(shù)據(jù)被截?cái)嗟萚7].

EM算法的過(guò)程只有兩步，但涉及的數(shù)學(xué)推理也很復(fù)雜.在某些特定情況下，EM算法的收斂速度會(huì)比較慢.

1.6PageRank算法

PageRank算法是Google用來(lái)進(jìn)行網(wǎng)頁(yè)重要性排名的算法，是Google判斷網(wǎng)站等級(jí)的工具.PageRank算法的創(chuàng)始人是拉里·佩奇(Larry Page)，而拉里·佩奇本身就是Google的創(chuàng)始人之一.PageRank名字中的“Page”不是指網(wǎng)頁(yè)，而是指創(chuàng)始人Page(佩奇)，也就是用PageRank是用創(chuàng)始人的名字命名的[8].

PageRank之前的算法把網(wǎng)頁(yè)當(dāng)成獨(dú)立個(gè)體去研究，而PageRank把整個(gè)互聯(lián)網(wǎng)看成一個(gè)全局系統(tǒng)或一個(gè)整體，注重網(wǎng)頁(yè)之間的關(guān)系.PageRank本質(zhì)上是一個(gè)靜態(tài)算法，靜態(tài)查詢時(shí)的計(jì)算量較低，計(jì)算過(guò)程可離線完成.

1.7AdaBoost算法

AdaBoost算法屬于迭代算法的一種，由Boosting算法改進(jìn)而來(lái).AdaBoost算法由Freund和SchapireAdaBoost在上世紀(jì)90年代提出，改善了Boosting算法的許多不同之處.算法首先依次產(chǎn)生多個(gè)弱(子)分類器，最終由他們組合生成一個(gè)強(qiáng)分類器，其中每個(gè)弱分類器在強(qiáng)分類器中的權(quán)重是不同的，相當(dāng)于加權(quán)投票.子分類器的生成可以使用簡(jiǎn)單的方法，AdaBoost算法本身只是一個(gè)框架[9].

AdaBoost算法無(wú)需特征篩選，且分類精度高.AdaBoost算法的應(yīng)用主要是分類問(wèn)題，近年來(lái)也出現(xiàn)用于回歸問(wèn)題.

1.8KNN算法

KNN算法的英文全稱為K-NearestNeighbor，中文多數(shù)譯成K近鄰算法.KNN算法由NN(NearestNeighbor，近鄰)算法演變而來(lái).算法思想非常簡(jiǎn)單，每一個(gè)樣本都可以用它周圍最近的K個(gè)樣本來(lái)表示，這K個(gè)樣本中歸屬于哪個(gè)類別的樣本多，樣本就屬于該類別.可以用“近朱者赤、近墨者黑”來(lái)概括KNN的核心思想[10].

KNN算法與K-Means容易發(fā)生混淆，二者的異同之處見表1：

表1　KNN算法與K-Means算法的區(qū)別

1.10Cart算法

Cart算法的英文全稱為Classification And Regression Tree，中文翻譯成分類和回歸樹算法，最早由Breiman 等人提出.Cart算法屬于決策樹算法的一種，生成的二叉樹結(jié)構(gòu)簡(jiǎn)單，即每個(gè)非葉子節(jié)點(diǎn)都有兩個(gè)分支.Cart算法不斷生成葉子節(jié)點(diǎn)，直到終止時(shí)得到最終的決策樹，然后開始剪枝，最終留下的葉子節(jié)點(diǎn)才是樹葉[12].

Cart算法即可以生成分類樹，也可以生成回歸樹，但是只能是二叉樹，不能建多叉樹.

2總結(jié)和展望

經(jīng)過(guò)20多年的發(fā)展，數(shù)據(jù)挖掘已經(jīng)融合到了多個(gè)學(xué)科、多個(gè)領(lǐng)域.數(shù)據(jù)挖掘從這些領(lǐng)域的海量和異構(gòu)數(shù)據(jù)中所挖掘出的隱藏信息和關(guān)聯(lián)規(guī)則已經(jīng)得到了廣泛的應(yīng)用.隨著互聯(lián)網(wǎng)和大數(shù)據(jù)技術(shù)的不斷發(fā)展，海量數(shù)據(jù)分析的需求將會(huì)出現(xiàn)在更多的領(lǐng)域，數(shù)據(jù)挖掘技術(shù)也將會(huì)迎來(lái)更加廣闊的未來(lái).

參考文獻(xiàn)：

[1]Fayyad U M, Piatetsky-Shapiro G,Smyth P.Knowledge discovery and data mining：towards a unifying framework [C].Proceedings of KDD-96:International Conference on Knowledge Discovery and Data Mining.Portland, Oregon：AAAI Press,1996:82-88.

[2]羅森林,馬俊,潘麗敏.數(shù)據(jù)挖掘理論與技術(shù)[M].北京：電子工業(yè)出版,2013：126-126.

[3]苗煜飛,張霄宏.決策樹C4.5算法的優(yōu)化與應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2015,51(13)：255-258.

[4]朱燁行,李艷玲,夢(mèng)天,楊獻(xiàn)文.一種改進(jìn)K-means算法的聚類算法CARDBK[J].計(jì)算機(jī)科學(xué),2015,42(3):201-205.

[5]姚程寬,許建華.雙正則化參數(shù)的L2-SVM參數(shù)選擇[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(8):99-102.

[6]錢慎一,朱艷玲,朱顥東.基于K-Means和Apriori算法的多層特征提取方法[J].華中師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，2015,49(3):357-362.

[7]徐廷學(xué),王浩偉,張?chǎng)?EM 算法在 Wiener 過(guò)程隨機(jī)參數(shù)的超參數(shù)值估計(jì)中的應(yīng)用[J].系統(tǒng)工程與電子技術(shù),2015,37(3):707-712.

[8]陳誠(chéng), 戰(zhàn)蔭偉, 李鷹.基于網(wǎng)頁(yè)鏈接分類的PageRank并行算法[J].計(jì)算機(jī)應(yīng)用，2015,31(1):48-52.

[9]屈鑒銘,劉志鏡,賀文驊.結(jié)合場(chǎng)景運(yùn)動(dòng)模式的有向加權(quán)AdaBoost目標(biāo)檢測(cè)[J].西安電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,42(3):67-72.

[10]陳飛彥,田宇馳, 胡亮物.聯(lián)網(wǎng)中基于 KNN 和 BP 神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)模型的研究[J].計(jì)算機(jī)應(yīng)用與軟件,2015,32(6):127-127.

[11]張紅蕊, 張永,于靜雯.云計(jì)算環(huán)境下基于樸素貝葉斯的數(shù)據(jù)分類[J].計(jì)算機(jī)應(yīng)用與軟件,2015,32(3):27-30.

[12]張亮,寧芊.CART決策樹的兩種改進(jìn)及應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì),2015,36(5):1209-1213.

[責(zé)任編輯：王軍]

The research on classic algorithms in data mining

GUANG Feng1,YAO Chengkuan1, LU Canju2,CAO Liyong1,ZHAN Zhe1

(1.Department of Common Basic ,Anqing Medical and Pharamaceutical College, Anqing 246003, China;2.Hefei Electronic Engineering Institute ,Hefei 230037, China)

Abstract:Data mining is a very popular research direction in the field of computer science in recent years.Data mining is developed by the data warehouse technology and machine learning.Finding the hidden relationship in the vast amounts of data is the purpose of data mining.Data mining is the advanced stage of data analysis.Many excellent algorithms were appeared in the research on the algorithm of data mining.Ten classical algorithms selected by IEEE are put forward in this paper.Every one of the ten algorithms is introduced simply and clearly in the aspects of the principle, the background, the development , the advantages, the disadvantages and the application field, which provides a reference for related study and research in the relevant field .

Key words:data mining; big data; clustering; classifying; predicting; association rules

中圖分類號(hào)：TP311.12

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1672-3600(2016)03-0044-04

通訊作者：姚程寬 (1974-)，男，安慶醫(yī)藥高等?？茖W(xué)校副教授，碩士，主要從事人工智能，模式識(shí)別，文本挖掘的研究.

基金項(xiàng)目：安徽省教育廳2016年高校優(yōu)秀中青年骨干人才國(guó)外訪學(xué)研修重點(diǎn)項(xiàng)目(No.337)；安徽省教育廳2014年省級(jí)重點(diǎn)教學(xué)研究項(xiàng)目(翻轉(zhuǎn)課堂教學(xué)模式實(shí)踐與研究—以《高等數(shù)學(xué)》教學(xué)為例，No.2014jyxm462)；安徽省教育廳2013年省級(jí)質(zhì)量工程—精品資源共享課程(《高等數(shù)學(xué)》，No.2013gxk113)支持.

收稿日期：2015-10-12；修回日期： 2015-10-19