数据挖掘的方法分类研究

摘要:通过对数据挖掘技术进行全面的分析和研究,依据其功能、任务的不同以及所处角度对分类方法的影响,侧重于应用数据挖掘技术得出结果的形式,同时还克服了传统数据挖掘分类方法的局限性和模糊性,最终提供了一种更为合理清晰的分类思路和方法。该方法的有效区分使得数据挖掘的应用更为方便易行,为正确的运用合适的数据挖掘方法进行知识的发掘提供导向。

Abstract: By an overall analysis and research on data mining technique, according to the different function and task and the influence of perspective on sorting method, emphasizing particularly on the form of results which is made by data mining technique, and overcoming the limitation and illegibility of canonical sorting method, then finally a kind of sorting method and approach is present. The effective distinction of this method makes it more feasible and convenient, and it offers guidance for applying proper data mining method to discover knowledge in a right way.

关键词:数据挖掘;方法;分类

Key words: data mining; method; sort

中图分类号:TP392文献标识码:A文章编号:1006-4311(2010)26-0146-02

0引言

数据挖掘是一门多学科交叉的综合性学科[1],其方法也融合了各学科方法的思想,主要是由人工智能、机器学习的方法发展而来,并与传统的统计分析方法、模糊数学方法结合而形成的,如图1所示。正因为如此,对它进行合理的分类十分重要,但同时却也不太容易。这里将它分为:信息论方法、集合论方法、神经网络方法、遗传算法、公式发现。

1信息论方法

信息论方法是利用信息论的原理建立决策树。由于该方法最后获得的知识表示形式是决策树,又称它为决策树方法。典型的信息论方法有两类。

1.1 ID3等方法ID3(Iterative Dichotomiser 3)[2]方法由J.R.Quinlan首创,其前身是CLS(Concept Learning System)。ID3方法检验所有的特征,选择信息增益(互信息)最大的特征点产生决策树结点,由该特征的不同取值建立分支,对各分支的实例子集递归,用该方法建立决策树节点和分支,直到某一子集中的例子属同一类。这种方法对愈大的数据库效果愈好。ID3方法在国际上影响很大,ID3方法以后又陆续开发了ID4、ID5、C4.5等。

1.2 IBLE方法IBLE(Information-based Learning from Examples)[3]方法是利用信息论中信道容量的概念作为对实体中选择重要特征的度量。寻找数据库中信息量从大到小的多个字段的取仅建立决策树的一个结点,根据该结点中指定字段取值的权值之和与两阈值的比较,建立左、中、有三个分枝,在各分枝子集中重复建树结点和分枝的过程。IBLE方法比ID3方法在识别率上提高了10%。

2集合论方法

集合论方法是开展较早的方法。近年来,由于粗糙集理论的发展使集合论方法得到了迅速的发展。这类方法中包括:覆盖正例排斥反例方法、概念树方法和粗糙集(rough set)方法。关联规则挖掘也属于集合论方法。

2.1 覆盖正例排斥反例方法覆盖正例排斥反例方法是从已知的正例和反例中归纳出能够描述正例而排斥反例的一般规则,它在机器学习中称为示例学习(也称为通过例子学习)。在学习的过程中,它既需要正例集又需要反例集,数据库中的元组集合可以被视为示例集合。当要发现某一类而排斥其余类的一般规则时,可以将某一类元组作为正例集,其余类所有的元组作为反例集,这样依次指定正例集和反例集便可以发现描述知识基表中某一类元组而排斥其余类的一般规则,即分类规则。比较典型的有AQ[4]算法及其改进算法,洪家荣的AE5方法[5]。

2.2 概念树方法在数据库中,许多属性都是可以进行数据归类的,以形成概念汇聚点,各属性值和概念依据抽象程度不向可以构成一个层次结构,概念的这种层次结构通常称为概念树。概念树一般由领域专家提供,概念树与数据库定的属性有关,它将各个层次的概念按一般到特殊的顺序排列。基于概念树的知识发现方法其实是一个几组合并的处理过程,用这种方法从数据库中发现规则知识的核心是执行基本的和面向各属性的归纳。其基本思想是:①一个同性的较具体的值被该属性的概念树中的父概念所替代。②对知识基表中出现的相同元组进行合并,构成更宏观的元组,并计算宏元组所覆盖的元组数目,如果数据库记录生成的宏元组数目仍然很大,那将用这个属性的概念树中更一般的父概念去替代或者根据另一个属性进行概念树的提升操作。③生成覆盖面更广、数量更少的宏元组,并归纳所得的最后结果转换成逻辑规则。

2.3 粗糙集方法粗糙集理论中的一些概念和方法可以用来从数据库中发现分类规则,其基本思想是将数据库中行元素视为元组,列元素视为属性(条件属性和决策属性)。等价关系R定义为不同元组在某个(或几个)属性上取值相同,这些满足等价关系的元组组成的集合称为该等价关系R的等价类。条件属性上的等价类E与决策属性上的等价类Y之间有3种情况[6]:①下近似:Y包含E。②上近似:Y和E的交为非空。③无关:Y和E的交为空。对下近似建立确定性规则,对上近似建立不确定性规则,无关情况不存在规则。

2.4 关联规则挖掘关联规则挖掘是在事务数据库中,挖掘出不同项集的关联关系。关联规则挖掘在事务数据库D中寻找那些不同项集(如A和B两个商品)同时出现的概率(即P(A∪B))大于最小支持度(min_sup),且在包含一个项集(如A)的所在事务中,同时也包含月一个项集(如B)的条件概率(即P(B|A))大于最小置信度(min_conf)时。则存在关联规则(即A=>B)。

3神经网络方法

神经网络是由大量的处理单元(神经元)互相连接而成的网络[7]。它是仿生学的一大成果,最早由生物学家McCulloch和数理学家Pitts提出[8]。神经网络的主要部分是神经元(如图2),它具有以下生物特征:是一个多输入、单输出的元件;是具有非线性的元件;具有可塑性,传递强度可变的特征;其输出是每个输入综合的结果。

在神经网络中,知识与信息的存储表现为神经元之间分布式的物理联系。它分散地表示和存储于整个网络内的各神经元及其连线上。每个神经元及其连线只表示一部分信息,而不是一个完整具体概念。只有通过各神经元的分布式综合效果才能表达出特定的概念和知识。由于人工神经网络中神经元个数众多以及整个网络存储信息容量的巨大,使得它具有很强的不确定性信息处理能力。即使输入的信息不完全、不准确或模糊不清,神经网络仍然能够通过联想思维,展示存在于记忆中事物的完整图像。只要输入的模式接近于训练样本,系统就能给出正确的推理结论。同时神经元的处理输出不是随意的,只有当神经元对所有的输入信息的综合处理结果超过某一阈值后才输出一个新的信息。

神经网络方法,以MP模型和Hebb学习规则为基础,建立了三大类多种神经网络模型,即:前馈式网络,以感知机、BP反向传播模型和函数型网络为代表,此类网络可用于预测、模式识别等方面;反馈式网络,Hopfield的离散模型和连续模型为代表,分别用于联想记忆和优化计算;自组织网络,ART模型、Kohonen模型为代表,用于聚类。

4遗传算法

遗传算法将问题的求解的过程看成一个在候选解空间寻找满足问题要求的解或最优近似解的搜索过程,其重点在适应规划和适应度量方面。遗传算法的适应规划用于指导算法怎么样在空间进行搜索,一般采用遗传算子(或称遗传操作)诸如交叉和变异等,以及模拟自然过程的选择机制,而适应度量采用计算适应值的方法来评估一个候选解的优劣。

典型遗传算法求解问题的过程如图3所示。

①首先生成一组初始的候选解群体(假设为M个候选解个体),称为第0代;②计算群体中各个候选解的适应值;③如果有候选解满足算法终止条件,算法终止,否则继续;④根据概率,将候选解群体中的个体随机两两配对,进行操作以生成新的候选解;⑤根据变异概率,对步骤④中生成的候选解群中的每个个体进行变异操作;⑥使用选择机制形成新一代候选解,转②。

从上面的算法可以看出,遗传算法的3个重要步骤为选择、交叉和变异。①选择(繁殖):从一个旧种群(父代)选择出生命力强的个体产生新种群(后代)的过程。②交叉(重组):选择两个不同个体(染色体)的部分(基因)进行交换,形成新个体。③变异(突变):对某些个体的某些基因进行变异(1变0,0变1)。

这种遗传算法起到产生优良后代的作用。这些后代需要满足适应值,经过若干代的遗传.将得到满足要求的历代(问题的解)。遗传算法已在优化计算和分类机器学习方面发挥了显著的效果。

5统计分析方法

数据挖掘思想和统计学紧密相连,有着一个类似的目标,即发现数据中的结构。目前采用的很多数据挖掘方法是根据统计学的分析方法发展出来的,需要用到例如随机变量、样本、假设检验、回归等一系列统计学概念和原理。把这类数据挖掘方法归称为统计分析方法,统计分析方法主要有以下几种。

5.1 常用统计用样本数据集中的频次、频率描述样本数据结构的基本特征;用茎叶图与直方图对刻度级样本数据作描述;用样本众数、中位数、均值对数据中心作描述;用极值、四分点与百分位点对样本数据离散特征作点状描述;用极差、四分位距与离差对样本数据离散特征作区间描述;用样本方差对离散状的统计值描述以及用箱形图对样本数据特征作综合表述等。

5.2 各种回归技术回归又包括线性回归和非线性回归。

5.2.1 线性回归线性回归是最简单的回归形式。双变量回归是将一个随机变量y(称作响应变量)看作另一个随机变量x(称为预测变量)的线性函数。

5.2.2 非线性回归即变量间的关系是曲线性式(即非线性的)的关系。非线性回归主要存在以下七种模型:双曲线模型,二次曲线模型,对数模型,三角函数模型,指数模型,幂函数模型,修正指数增长曲线。

6结语

数据挖掘技术因在海量数据的知识发掘方面发挥着巨大的作用而被越来越多的应用到实际当中。选择合适的数据挖掘方法,则是能否成功得以应用并取得高效结果的关键步骤。因此,数据挖掘技术的方法分类是先决条件,分类的好坏决定了应用的成败。

参考文献:

[1]Jiawei Han, Micheline Kamber著.范明.孟小峰译.数据挖掘概念与技术[M].机械工业出版社,2007.

[2]Quinlan. J. R. Induction of Decision Tree[J].Machine Learining,1986(1):81-106.

[3]陈文伟,黄金才,赵新昱等.数据挖掘技术[M].北京工业大学出版社,2002.

[4]R. S. Michalski, I. Mozetic, J. Hong. The multi purpose incremental learning system AQ15 and its testing application to three medical domains. In. Proc AAAI,USA,1986,1041~1045.

[5]洪家荣.示例学习及多功能学习系统AE5[J].计算机学报,1989,12(2):98~105.

[6]晏伟峰.基于Rough Set的属性约减算法研究[D].华中科技大学硕士学位论文,2006.

[7]杨建刚.人工神经网络实用教程[M].浙江大学出版社,2001.

[8]Mc Culloch W S, Pittes W H. A Logical Calculus of the Ideas Immanent neuron Activity, Bulletin Mathematical Biophysics, V.5,1943:115~133.