第21卷 第3期JO U RN A L OF HEBEI U N IV ERSI T Y OF V ol.21 N o.3总第54期 2000年SCI EN CE A N D T ECHN OL O GY Sum54 2000
文章编号:1008-1542(2000)03-0077-04
数据挖掘技术的主要方法及其发展方向
杨会志
(河北科技大学经济管理学院,河北石家庄 050018)
摘 要:论述了数据挖掘技术的通用算法模型、主要方法及今后的发展方向。
关键词:数据挖掘;通用算法;主要方法;发展方向
中图分类号:TP391 文献标识码:A
随着信息技术的高速发展,数据库应用的规模、范围和深度不断扩大,已经从点(单台机器)发展到面(网络),甚至到Inter net全球信息系统,使得无论是商业企业、科研机构或是部门,在过去若干年的时间里都积累了海量的、以不同形式存储的数据资料。由于这些资料十分繁杂,仅仅依靠数据库的查询检索机制和统计学方法已经远远不能满足现实需要了,它迫切要求自动地和智能地将待处理的数据转化为有用的信息和知识,从而达到为决策服务的目的。数据挖掘正是为迎合这种需要而产生并迅速发展起来的用于开发信息资源的一种新的数据处理技术。目前一种比较公认的定义是W.J.Fraw ley,G.Piatetsky-Shapiro[1]等人提出的:数据挖掘(Data M ining,DM)就是从大型数据库的数据中提取人们感兴趣的知识。这些知识是隐含的、事先未知的潜在有用信息,提取的知识表示为概念(Concepts)、规则(Rules)、规律(Regularities)、模式(Patterns)等形式。这种定义把数据挖掘的对象定义为数据库,而更广义的说法是:数据挖掘是在一些事实或观察数据的集合中寻找模式的决策支持过程,数据挖掘的对象不仅是数据库,也可以是文件系统,或其他任何组织在一起的数据集合。
1 数据挖掘技术的算法
数据挖掘算法是对数据挖掘方法的具体实现,一般由3个部分组成[2](下文中的模型是指从数据库中所发现的模型):
1)模型表示。用于描述要发现的模型是语言。如果语言的描述能力较强,就有助于发现精确的数学模型。但是,能力过强的描述语言却有可能导致所发现的模型过分一般化,降低了预测的精度。常用的模型表示方法有决策树、非线性回归、基于事例的推理、贝叶斯网络和归纳程序设计等方法。
2)模型评价标准。对1个所发现的模型在多大程度上符合发现目的和要求作出定量的评价。对预测类的模型,可以利用一些测试数据集来评价其精确度。对描述类的模型,可以在精确度、新
收稿日期:1999-12-16;修回日期:2000-03-10;责任编辑:李 穆
作者简介:杨会志(1969-),男,河北丰润人,副教授,博士。
78河北科技大学学报 2000年
颖性、实用性及可理解性等多个方面进行评价。
3)发现方法。分为参量发现和模型发现。在模型表示和模型评价标准被确定之后,数据挖掘就完全变成了一个优化任务,即从数据的描述中发现最适合评价标准的参量或模型。具体说来,参量发现就是在确定数据集和模型表示之后,寻找最适合模型评价标准的参量。模型发现是一个循环地试探过程,需要不断更改模型表示,最后确定出恰当数量的模型。
一般来说,不存在一个普遍适用的算法。一个算法在某个领域非常有效,但在另一个领域却可能不太合适。因此,在实际应用中,要针对特定的领域,精心选择有效的数据挖掘算法。换句话说,实际的开发工作往往变成对领域知识和发现任务的形式化,而不是对所选择的数据挖掘算法进行细节上的优化。
2 数据挖掘技术的主要方法
从不同的角度看,数据挖掘技术有多种分类方法,如根据发现的知识种类分类,根据挖掘的数据库类型分类,根据挖掘方法分类,根据挖掘的途径分类,根据所采用的技术分类[3,4]等等。目前常用的数据挖掘技术内容包括如下:
1)决策树方法。利用信息论中的互信息(信息增益)寻找数据库中具有最大信息量的字段,建立决策树的一个结点,再根据字段的不同取值建立树的分支;在每个分支子集中重复建立树的下层结点和分支的过程,即可建立决策树。国际上最有影响和最早的决策树算法是Quiulan研制的ID3方法,数据库越大它的效果越好。此后又发展了各种决策树方法,如IBLE方法使识别率提高了10%。
2)神经网络方法。它模拟人脑神经元结构,以M P模型和Hebb学习规则为基础,用神经网络连接的权值表示知识,其学习体现在神经网络权值的逐步计算上。目前主要有3大类多种神经网络模型。 前馈式网络。它以感知机、反向传播模型、函数型网络为代表,可用于预测、模式识别等方面。 反馈式网络。它以Ho pfield的离散模型和连续模型为代表,分别用于联想记忆和优化计算。 自组织网络。它以ART模型、Koholon模型为代表,用于聚类。
3)覆盖正例排斥反例方法。它是利用覆盖所有正例、排斥所有反例的思想来寻找规则。首先在正例集合中任选一个种子,到反例集合中逐个比较,与字段取值构成的选择子相容则舍去,相反则保留。按此思想循环所有正例种子,将得到正例的规则(选择子的合取式)。比较典型的算法有M ichalski的AQ11方法、洪家荣改进的AQ15方法以及他的AE5方法。
4)粗集(Rough Set)方法。在数据库中,将行元素看成对象,列元素看成属性(分为条件属性和决策属性)。等价关系R定义为不同对象在某个(或几个)属性上取值相同,这些满足等价关系的对象组成的集合称为该等价关系R的等价类。条件属性上的等价类E与决策属性上的等价类Y之间有3种情况:下近似:Y包含E;上近似:Y和E的交非空;无关:Y和E的交为空。对下近似建立确定性规则,对上近似建立不确定性规则(含可信度),对无关情况不存在规则。
5)概念树方法。对数据库中记录的属性字段按归类方式进行抽象,建立起来的层次结构称之为概念树。利用概念树提升的方法可以大大浓缩数据库中的记录。对多个属性字段的概念树进行提升,将得到高度概括的知识基表,然后可再将它转换成规则。
6)遗传算法。这是模拟生物进化过程的算法,由3个基本算子组成: 繁殖(选择)。是从1个旧种群(父代)选出生命力强的个体,产生新种群(后代)的过程。 交叉(重组)。选择2个不同个体(染色体)的部分(基因)进行交换,形成新个体。 变异(突变)。对某些个体的某些基因进行变异(1变0,0变1)。这种遗传算法可以起到产生优良后代的作用。这些后代需满足适应度值,经
过若干代的遗传,将得到满足要求的后代(问题的解)。遗传算法已在优化计算和分类机器学习方面显示了明显的优势。
7)公式发现。在工程和科学数据库(由实验数据组成)中,对若干数据项(变量)进行一定的数算,求得相应的数学公式。比较典型的BACON 发现系统完成了对物理学中大量定律的重新发现,其基本思想是:对数据项进行初等数算(加、减、乘、除等),形成组合数据项,若它的值为常数项,就得到了组合数据项等于常数的公式。
8)统计分析方法。在数据库字段项之间存在两种关系:函数关系(能用函数公式表示的确定性关系)和相关关系(不能用函数公式表示,但仍是相关确定关系)。对它们的分析采用如下方法:回归分析、相关分析、主成分分析。
9)模糊集方法。利用模糊集理论对实际问题进行模糊评判、模糊决策、模糊模式识别和模糊聚类分析。模糊性是客观存在的。系统的复杂性越高,精确化能力就越低,即模糊性就越强。这是Zadeh 总结出的互克性原理。
10)可视化技术。可视化数据分析技术拓宽了传统的图表功能,使用户对数据的剖析更清楚。例如,把数据库中的数据变成多种图形,这对揭示数据的状况、内在本质及规律性起了很大作用。
3 数据挖掘技术的研究方向
[5,6]目前,数据挖掘技术的研究还很不成熟,其应用还存在较大的局限性,成为其今后的发展方
向:1)数据输入形式的多样性。应用中经常需要对一些半结构化、非结构化的数据形式如文本、图形、数学公式、图象或WW W 资源进行挖掘操作,但目前的数据挖掘工具一般只能提供对数值型的结构化数据的处理,对数据中存在缺损或噪声的情况也没有有效的方法。
2)数据挖掘算法的有效性与可测性。数据挖掘的对象向更大型的数据库、更高的维数和属性之间更复杂的关系方向发展。更多的记录和属性意味着更大、更高维的搜索空间,从而导致组合爆炸;属性之间的关系变得更为复杂如表现为层次结构,会大大提高知识搜索的代价。从1个大型数据库中抽取知识的算法必须高效、可测量,即数据挖掘算法的运行时间必须可预测,且可接受,指数和多项式算法等复杂性的算法不具有实用价值。目前的研究发展到用并行处理或抽样的方法处理大规模数据以获得较高的计算效率,根据问题的定义和领域知识选择出需要的属性从而降低维数并有效处理属性之间的复杂关系等。
3)用户参与和领域知识。有效的决策过程往往需要多次交互和多次反复,使数据挖掘的结果准确地描述数据挖掘的要求,并易于表达,实现在多抽象层次上交互挖掘知识。目前许多知识发现系统和工具缺乏与用户的交互,难以有效利用领域知识。
4)证实技术的局限。数据挖掘使用特定的分析方法或逻辑形式发现知识,如归纳方法。但系统可能无法去交互证实所发现的知识的正确或正确的程度,使得发现的知识没有普遍性而不能成为有用的知识。
5)知识的表达和解释机制。许多应用中重要的是用户能够理解发现的知识。这要求知识的表达不仅限于数字或符号,而是更易于理解的方式,如图形、自然语言和可视化技术等。同时,只有当数据挖掘系统能提供更好的解释机制,用户才能更有效地评价这些知识,并且区分出哪些是真正有用的知识,哪些只是常识性的知识或异常情况。6)知识的维护和更新。新的知识发现可能导致以前发现的知识失效,因此知识需要动态维护79 第3期 杨会志 数据挖掘技术的主要方法及其发展方向
和及时更新。目前研究采用增量更新的方法、数据快照和时间戳等方法来维护已有的知识。
7)私有性和安全性。数据挖掘能从不同角度、不同抽象层次上观察数据,将影响到数据挖掘的私有性和安全性。通过研究数据挖掘导致的数据非法侵入,可改进数据库安全方法,以避免信息泄露。
8)支持的局限、与其他系统的集成。目前的数据挖掘系统尚不能支持多种平台。一些产品是基于PC的,一些是面向大型主机系统的,还有一些是面向客户机/服务器环境的。另外,由于方法功能单一的发现系统的适应范围的,要充分发挥系统的作用,应该和数据库、知识库、专家系统、决策支持系统、可视化工具、网络技术等进行有机集成。
参考文献:
[1] Piatetsk y-Shapiro G,Fayyad U,Smith P.From Data M ining to Know ledge Dis cover y:an overview[A].In:Fayyad U M,
Piatetsk y-Shapiro G,Lisa Lew in son,et al.Advances in Know ledge Discovery an d Data M inin g[C].Amer ica:AAA/M IT Press,1996.1-35.
[2] M an nila H,T oivonen H,Inkeri Verkamo A.Efficient Algorithms for Dis coverin g Ass ociation Rules[A].In:
Raghavan.Proceed ings of AAAI Works hop on Know ledge Discovery in Databas e[C].Am erica:AAA/M IT Press, 1994.181-192.
[3] Han J.Conference T utorial Notes:Data M ining T echniqu es[A].In:Arning A.Proceedings of ACM SIGM OD
In ternation al Conference'96on M anagement of Data(SIGOM D'96)[C].Canada:M on treal Press,1996.124-129.
[4] L u Hongju n,Rudy Setiono,Liu Huan.Effective Data M ining U sing Neur al netw orks[A].In:Grupe F H.IEEE
T ransactions on Know led ge an d Data En gineering[C].Am erica:AAA/M IT Pr ess,1996.957-961.
[5] Park J S,Ash ok S avasere.An Effective Hash-bas ed Algorithm for M ining Ass ociation Ules[A].In:
Heraklion.Proceedings of the ACM S IGM OD[C].Greece:Ctete Press,1995.175-186.
[6] H an J.M in ing Knowledge at M ultiple Con cept Levels[A].In:Proceeding s of the4th International Conference on
Information and Know ledge M anag ement(CIKM'95)[C].M arylan d:Baltimore Press,1995.19-24.
Primary Methods and Perspectives of Data Mining
YANG Hui-zhi
(College o f Economics and Management,Hebei Univer sity of Science and T echnology,Hebei Shijiazhuang050018,China)
Abstract:T his paper discusses the g eneral algo rithm mo del,pr imar y met ho ds and per spectiv es of data mining in the future.
Key words:data miniqdng;gener al alg or ithm;pr imar y m et hod;perspect ive下载本文
