數據挖掘經典算法研究

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

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

?

數據挖掘經典算法研究

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

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

摘要：數據挖掘是近年來計算機科學領域非常熱門的研究方向之一，是由數據倉庫技術和機器學習發展而來.數據挖掘是指從海量的數據中找出隱藏的關系，是數據分析的高級階段.在對數據挖掘的算法研究中，涌現出了很多優秀的算法.本文選擇了IEEE評選出的十大經典算法，對其中的每個算法的原理、背景、發展、優缺點、應用領域等做了深入淺出的介紹，為相關專業領域的學習及研究提供參考.

關鍵詞：數據挖掘；大數據；聚類；分類；預測；關聯規則

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

1經典算法

1.1C4.5算法

C4.5算法屬于決策樹算法的一種，是由ID3算法改進而來.從數據分析從而得到決策樹的方法就是通常所說的決策樹算法，簡稱為決策樹或決策樹學習.ID3誕生于20世紀70年代，是構造決策樹的一種算法，準確說是屬于分類預測的貪心算法.由于算法自身的一些缺陷，J.Ross Quinlan對ID3算法進行了改進，提出了C4.5算法[3].

C4.5算法不僅保留了ID3算法的全部優點，同時，改進了ID3的兩個主要缺點：

(1)在對分支屬性決策時，ID3使用信息增益這一指標進行度量，導致選擇偏向于取值多的屬性，很多情況下，這些屬性是無效數據.而C4.5則使用的是信息增益率這個指標，客服了這一缺陷.

(2)ID3算法只能取離散數據，C4.5屬性值可以是既可以是離散值也可以是連續值，因為C4.5能夠對連續數據進行離散化處理.

C4.5的分類準確性高，缺點是算法的效率比較低.

1.2K-Means算法

K-Means算法是聚類算法的典型代表.算法簡單，以距離為核心，在機器學習領域得到了極為廣泛的應用.算法的主導思想為：距離近的，相似度高；距離遠的，相似度低[4].

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

1.3SVM算法

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

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

1.4Apriori算法

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

Apriori算法分為兩個階段，是基于先驗知識的上次頻繁項遞推生成本次頻繁項.Apriori算法的缺點是只能處理類別標示，不能直接處理數值型數據.

1.5EM算法

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

EM算法的過程只有兩步，但涉及的數學推理也很復雜.在某些特定情況下，EM算法的收斂速度會比較慢.

1.6PageRank算法

PageRank算法是Google用來進行網頁重要性排名的算法，是Google判斷網站等級的工具.PageRank算法的創始人是拉里·佩奇(Larry Page)，而拉里·佩奇本身就是Google的創始人之一.PageRank名字中的“Page”不是指網頁，而是指創始人Page(佩奇)，也就是用PageRank是用創始人的名字命名的[8].

PageRank之前的算法把網頁當成獨立個體去研究，而PageRank把整個互聯網看成一個全局系統或一個整體，注重網頁之間的關系.PageRank本質上是一個靜態算法，靜態查詢時的計算量較低，計算過程可離線完成.

1.7AdaBoost算法

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

AdaBoost算法無需特征篩選，且分類精度高.AdaBoost算法的應用主要是分類問題，近年來也出現用于回歸問題.

1.8KNN算法

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

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

表1　KNN算法與K-Means算法的區別

1.10Cart算法

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

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

2總結和展望

經過20多年的發展，數據挖掘已經融合到了多個學科、多個領域.數據挖掘從這些領域的海量和異構數據中所挖掘出的隱藏信息和關聯規則已經得到了廣泛的應用.隨著互聯網和大數據技術的不斷發展，海量數據分析的需求將會出現在更多的領域，數據挖掘技術也將會迎來更加廣闊的未來.

參考文獻：

[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]羅森林,馬俊,潘麗敏.數據挖掘理論與技術[M].北京：電子工業出版,2013：126-126.

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

[4]朱燁行,李艷玲,夢天,楊獻文.一種改進K-means算法的聚類算法CARDBK[J].計算機科學,2015,42(3):201-205.

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

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

[7]徐廷學,王浩偉,張鑫.EM 算法在 Wiener 過程隨機參數的超參數值估計中的應用[J].系統工程與電子技術,2015,37(3):707-712.

[8]陳誠, 戰蔭偉, 李鷹.基于網頁鏈接分類的PageRank并行算法[J].計算機應用，2015,31(1):48-52.

[9]屈鑒銘,劉志鏡,賀文驊.結合場景運動模式的有向加權AdaBoost目標檢測[J].西安電子科技大學學報(自然科學版),2015,42(3):67-72.

[10]陳飛彥,田宇馳, 胡亮物.聯網中基于 KNN 和 BP 神經網絡預測模型的研究[J].計算機應用與軟件,2015,32(6):127-127.

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

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

[責任編輯：王軍]

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

中圖分類號：TP311.12

文獻標識碼：A

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

通訊作者：姚程寬 (1974-)，男，安慶醫藥高等專科學校副教授，碩士，主要從事人工智能，模式識別，文本挖掘的研究.

基金項目：安徽省教育廳2016年高校優秀中青年骨干人才國外訪學研修重點項目(No.337)；安徽省教育廳2014年省級重點教學研究項目(翻轉課堂教學模式實踐與研究—以《高等數學》教學為例，No.2014jyxm462)；安徽省教育廳2013年省級質量工程—精品資源共享課程(《高等數學》，No.2013gxk113)支持.

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