光峰,姚程宽,卢灿举,曹立勇,詹喆

(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