数据挖掘分类算法研究与探讨

摘要：数据挖掘技术是一个年轻且充满希望的研究领域，商业利益的强大驱动力将会不停地促进它的发展。随着数据库应用的不断深化，数据库的规模急剧膨胀，数据挖掘已成为当今研究的热点，每年都有新的数据挖掘方法和模型问世，特别是其中的分类问题，引起了越来越多的关注。

关键词：数据挖掘；分类；算法

中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)35-2339-02

Research and Discuss the Classification Algorithm of Data Mining

SUN Juan

(Department of Information science and Technology, Jiujiang University, Jiujiang 332005, China)

Abstract: That the data mining a technology is that one is young and is full of the go into field hoping, commerce benefit driving force big and powerful will may keep on promoting development of it. Applicative ceaselessness deepens with the data base, the data base scale expands rapidly, the data mining the hot spot already becoming a nowadays studying , the new data mining of it both method and the model every year coming out, Classification problem especially among them, has aroused more and more attention.

Key words: data mining; classification; algorithm

随着计算机技术特别是数据库技术的迅猛发展，以及人类活动范围的扩展、生活节奏的加快，人们能以更快速更容易更廉价的方式获取和存储数据，这就使得数据及其信息量以指数方式增长。面对这些极度膨胀的数据，人们受到“信息爆炸”和“数据过剩”(Data Glut)的巨大压力。这些海量数据如果不能有效利用起来，将只会成为“数据垃圾”。对人类社会进步起到巨大作用的是知识。 数据挖掘就是从大量数据中发现潜在规律、提取有用知识的方法和技术[1]。数据挖掘包含的内容很多，其中很重要的一个方面是分类规则挖掘。

分类技术在很多领域都有应用，例如可以通过客户分类构造一个分类模型来对银行贷款进行风险评估；当前的市场营销中很重要的一个特点是强调客户细分。客户类别分析的功能也在于此，采用数据挖掘中的分类技术，可以将客户分成不同的类别，比如呼叫中心设计时可以分为：呼叫频繁的客户、偶然大量呼叫的客户、稳定呼叫的客户、其他，帮助呼叫中心寻找出这些不同种类客户之间的特征，这样的分类模型可以让用户了解不同行为类别客户的分布特征；其他分类应用如文献检索和搜索引擎中的自动文本分类技术；安全领域有基于分类技术的入侵检测等等。机器学习、专家系统、统计学和神经网络等领域的研究人员已经提出了许多具体的分类预测方法。下面对几种主要的分类方法作简要的研究与探讨：

1 基于判定树的归纳分类

判定树是一个类似流程图的树结构，其中每个内部节点表示在一个属性上的测试，每个分支代表一个测试输出，而每个树叶节点代表类或类分布。树的最顶层节点是根节点。由判定树可以很容易得到“IF-THEN”形式的分类规则。方法是沿着由根节点到树叶节点的路径，路径上的每个属性-值对形成“IF”部分的一个合取项，树叶节点包含类预测，形成“THEN”部分。一条路径创建一个规则。判定树归纳的基本算法是贪心算法。

算法描述如下：判定树归纳分类[2]是一种从训练样本集中推理出判定树表示形式的分类规则的方法。它采用自顶向下的递归方式，判定树的最顶节点是根结点，树的内部结点表示在一个属性上的测试，从该结点向下的每个分支代表一个测试输出，在树的叶结点得到分类预测。从根到叶结点的一条路径就对应着一条合取规则，整棵判定树就对应着一组析取表达式规则。判定树的优点在于它的直观性和易理解性，判定树方法不仅能做出分类和预测，而且它的生成过程、分类、预测以及从判定树所提取的分类规则都具有很强的可理解性。

算法策略如下：①判定树以代表训练样本的单个节点开始；②如果样本都在同一个类，则该节点成为树叶，并用该类标记；③否则，基于启发式或统计式策略选择能够最好地将样本分类的属性，将样本分类；④对测试属性的每个已知的值，创建一个分枝，并以此为根据划分样本；⑤使用同样的过程，递归地形成每个划分上的样本判定树。

停止划分的条件：给定节点的所有样本属于同一类：没有剩余属性可以用来进一步划分样本，此时使用多数表决(用训练集中的多数所在的类标记它)；没有样本剩余。

2 KNN法(K-Nearest Neighbor)

KNN(K Nearest Neighbors)算法[3]又叫K最临近方法，总体来说KNN算法是相对比较容易理解的算法之一，假设每一个类包含多个样本数据，而且每个数据都有一个唯一的类标记表示这些样本是属于哪一个分类，KNN就是计算每个样本数据到待分类数据的距离，取和待分类数据最近的K各样本数据，那么这个K个样本数据中哪个类别的样本数据占多数，则待分类数据就属于该类别。

KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

该方法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。另外还有一种Reverse KNN法，能降低KNN算法的计算复杂度，提高分类的效率。

该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

3 VSM法

VSM法即向量空间模型(Vector Space Model)法，由Salton等人于60年代末提出。这是最早也是最出名的信息检索方面的数学模型。其基本思想是将文档表示为加权的特征向量：D=D(T1,W1;T2,W2;…;Tn,Wn)，然后通过计算文本相似度的方法来确定待分样本的类别。当文本被表示为空间向量模型的时候，文本的相似度就可以借助特征向量之间的内积来表示。

在实际应用中，VSM法一般事先依据语料库中的训练样本和分类体系建立类别向量空间。当需要对一篇待分样本进行分类的时候，只需要计算待分样本和每一个类别向量的相似度即内积，然后选取相似度最大的类别作为该待分样本所对应的类别。

由于VSM法中需要事先计算类别的空间向量，而该空间向量的建立又很大程度的依赖于该类别向量中所包含的特征项。根据研究发现，类别中所包含的非零特征项越多，其包含的每个特征项对于类别的表达能力越弱。因此，VSM法相对其他分类方法而言，更适合于专业文献的分类。

4 Bayes法

Bayes法是一种在已知先验概率与类条件概率的情况下的模式分类方法，待分样本的分类结果取决于各类域中样本的全体。

设训练样本集分为M类，记为C={c1,…,ci,…cM}，每类的先验概率为P(ci)，i=1,2,…,M。当样本集非常大时，可以认为P(ci)=ci类样本数/总样本数。对于一个待分样本X，其归于cj类的类条件概率是P(X/ci)，则根据Bayes定理，可得到cj类的后验概率P(ci/X)：

P(ci/x)=P(x/ci)・P(ci)/P(x) （1）

若 P(ci/X)=MaxjP(cj/X)，i=1,2,…,M，j=1,2,…,M，则有x∈ci（2）

（2）式是最大后验概率判决准则，将（1）式代入（2）式，则有：

若P(x/ci)P(ci)=Maxj[P(x/cj)P(cj)]，i=1,2,…,M,j=1,2,…,M，则x∈ci，这就是常用到的Bayes分类判决准则。经过长期的研究，Bayes分类方法在理论上论证得比较充分，在应用上也是非常广泛的。

Bayes方法的薄弱环节在于实际情况下，类别总体的概率分布和各类样本的概率分布函数(或密度函数)常常是不知道的。为了获得它们，就要求样本足够大。另外，Bayes法要求表达文本的主题词相互独立，这样的条件在实际文本中一般很难满足，因此该方法往往在效果上难以达到理论上的最大值。

5 神经网络

人工神经网络的研究至今已有60多年的历史。1943年，心理学家McCulloch和数学家Pitts合作，提出了形式神经元的数学模型，即MP模型[4]，从此，神经网络引起了许多科学家的兴趣。但随着对感知机为代表的神经网络的功能和局限性的深入分析等原因，使神经网络的研究陷入低潮。但是仍有一些学者坚持研究，并取得了一些成果，出现了Grossberg的ART模型和Kohonen的SOM模型。1982年，通过引入能量函数的概念，Hopfied研究了网络的动力学性质，并用电子线路设计出相应的网络，进而掀起了神经网络新的研究高潮。1986年，Rumellhart和McCllel-land等提出了PDP理论，尤其是发展了多层前向网络的BP算法，成为迄今应用最普遍的学习算法。

神经网络可解决目前数据挖掘存在几个方面的问题：

1) 数据的量度和维度，面对大量复杂、非线性、时序性与噪音普遍存在的数据；

2) 数据分析的目标具有多样性，使其在表述和处理上都涉及到领域知识；

3) 在复杂目标下，对海量数据集的分析，目前还没有现成的且满足可计算条件的一般性理论的方法。然而，神经网络在对噪声数据的高承受能力以及对未经训练的数据分类模式的能力方面有很大优势。因此设计出基于神经网络的数据挖掘方法，并将其用于真实世界问题，是可行且也是必要的。

人工神经网络可用于数据挖掘的分类、聚类、特征挖掘、预测和模式识别等方面，因此，人工神经网络在数据挖掘中占有举足轻重的作用。

总之，数据挖掘技术是一个年轻且充满希望的研究领域，商业利益的强大驱动力将会不停地促进它的发展。每年都有新的数据挖掘方法和模型问世，人们对它的研究正日益广泛和深入。尽管如此，数据挖掘技术仍然面临着许多问题和挑战：如数据挖掘方法的效率亟待提高，尤其是超大规模数据集中数据挖掘的效率；开发适应多数据类型、容噪的挖掘方法，以解决异质数据集的数据挖掘问题；动态数据和知识的数据挖掘；网络与分布式环境下的数据挖掘等；另外，近年来多媒体数据库发展很快，面向多媒体数据库的挖掘技术和软件今后将成为研究开发的热点。

参考文献：

[1] 范明,孟小峰.数据挖掘：概念与技术[M].北京：机械工业出版社,2001.

[2] 王旅,彭宏,胡劲松.基于判定树归纳分类的土质分类定名方法[J].计算机工程与设计,2006,27(11):1929-1931.

[3] 王燕,李睿,李明.数据挖掘技术应用研究[J].甘肃科技,2001,17(1):49-50.

[4] 毛国君,段立娟,王实,等.数据挖掘原理与算法[M].北京：清华大学出版社,2007.