（计算机软件与理论专业论文）数据挖掘算法研究及其在旅游业中的应用.pdf

v ，6 1 8 3 8 7 摘要 1 摘要 作为一种高效、深层次的数据分析处理技术，数据挖掘目的是从大型数据库或 数据仓库中提取隐含的、未知的、非平凡的以及有潜在应用价值的信息或模式，这 些信息将为人们进行各种决策分析提供有力依据。序列模式挖掘是数据挖掘技术的 一个重要的研究方向，其作用是挖掘相对时间或其他模式出现频率高的模式。分类 分析是数据挖掘技术研究的又一个重要方向，常用的分类模型有决策树，神经网络， 遗传算法，粗糙集模型，统计模型等。当前数据挖掘已用于电信、金融、商业、气 象预报、d n a 序列分析、股票发展趋势分析、入侵检测等许多领域，而且正在探索 更多行业中的应用。 本课题主要研究了数据挖掘中的数据预处理、序列模式挖掘和决策树分类分析， 详细介绍如下： 第一，指出了课题的研究背景及其重要的研究意义；从数据挖掘的理论研究和 应用研究方面，对当前数据挖掘的国内与国外的研究动态进行分析。并就当前数据 挖掘研究重点问题作了详细介绍。 第二，深入研究了数据挖掘中序列模式分析技术。回顾了序列模式分析的研究 动态，详细介绍了当前序列模式分析的主要算法，分析比较了算法的优缺点，给出 了算法中存在的问题。 第三，详细深入的介绍了分类分析的基本概念和处理过程，给出了模型评价标 准，并详细分析了基于决策树的分类模型的研究动态，介绍了决策树分类分析的原 理及步骤，并对i d 3 算法进行了深入的研究分析。 第四，针对i d 3 算法中存在的问题，对其进行了改进，提出了i d 3n o w 算法， 有效地缩减了i d 3 算法处理过程中的数据量，使生成的决策树更加简洁、有效，并 且通过在产生决策树的节点时，同时记录下满足从该节点到根节点的路径的条件的 记录数，从而提高决策树的决策能力。并通过实际应用证明了算法的有效性。 第五，构建了旅游消费者数据分析系统。首先说明了研究旅游消费者数据的重 要意义；介绍了系统的主要功能：数据预处理、旅游消费者出行路线分析以及消费 者消费能力分析；详细分析了数据预处理模块所采用的预处理手段和方法，对旅游 消费者出行路线分析以及消费者消费能力分析中采用的算法进行了详细的描述，并 利用该系统对山东省旅游消费者数据进行分析，并对结果进行了评价。 最后，对研究工作出现的问题进行了讨论并对三年的研究工作进行了总结，指 明了今后进一步研究的课题。 关键词：数据挖掘序列模式分类分析决策树 a b s t r a o t a san e we f f i c i e n ta n dh i g h l e v e ld a t a a n a l y s i sa n dp r o c e s s i n gt e c h n o l o g y ， d a t a m i n i n g i s d e v e l o p e d f r o m1 9 8 0 s i ta i m st oe x t r a c tt h e i m p l i c i t ， p r e v i o u s l yu n k n o w n ，a n dp o t e n t i a l l y u s e f u l k n o w l e d g e f r o m v o l u m i n o u s ， n o n c o m p l e t e ，f u z z y ，s t o c h a s t i cd a t a s e q u e n t i a lp a t t e r n sm i n i n gi sa n i m p o r t a n tr e s e a r c hp r o b l e mi nt h ed a t am i n i n gd o m a i n ，w h i c ha i m st om i n i n g t h ef r e q u e n tp a t t e r n c 1 a s s i f i c a t i o ni sa n o t h e ri m p o r t a n tr e s e a r c hp r o b l e m a n dt h ec o m m o nc l a s s i f i c a t i o nm o d e l sa r ed e c i s i o n t r e e ， n e u r a ln e t w o r k g e n e t i ca l g o r i t h m ，r o u g hs e t ，s t a t i s t i c a lm o d e le t c n o w ，d a t am i n i n gh a s b e e nu s e di nt e l e c o m ，f i n a n c e ，b u s y n e s s ，w e a t h e rf o r e c a s t ，d n a ，s t o c km a r k e t a n di n t r u s i o nd e t e c t i o ne t c ，a n di ti se x p a n d i n gi t sa p p l i c a t i o na r e a i n t h i sp a p e rw em a i n l yr e s e a r c ht h ea l g o r i t h mo fs e q u e n t i a lp a t t e r n sm i n i n g a n dd e c i s i o nt r e ea l g o r i t h m ，t h ec o n t e n t sa r es h o w na sf o l l o w i n g ： f i r s t ，w ed e s c r i b e dt h eb a c k g r o u n do fr e s e a r c ha n dp o i n t e do u ti t s s i g n i f i c a n c e t h ed o m e s t i ca n df o r e i g ns i t u a t i o no fd a t am i n i n gr e s e a r c hw a s a n a l y z e df r o mt h e o r e t i c a la n da p p l y i n ga s p e c t s s e c o n d ，w ed e e p l yr e s e a r c ht h et e c h n i q u eo fs e q u e n t i a lp a t t e r n sm i n i n g a n dw er e v i e wt h ed e v e l o p m e n to ft h es e q u e n t i a lp a t t e r n sm i n i n g t h ec o n t e n t o ft h ea l g o r i t h m si s a n a l y z e d t h ed i s a d v a n t a g e sa n da d v a n t a g e so ft h e s e a l g o r i t h m sa r ec o m p a r e d t h i r d ，w e i n t r o d u c et h eb a s i c c o n c e p t i o n a n dt h e p r o c e s s i o no f c l a s s i f i c a t i o na n a l y s i sc l e a r l y a n dw ep r o v i d et h ea s s e s s m e n to ft h em o d e l o ft h ec l a s s i f i c a t i o na n 也r e v i e wt h ep r e s e n td e v e l o p m e n to fc l a s s i f i c a t i o n m o d e lb a s e do nd e c i s i o nt r e e t h ep r i n c i p l ea n ds t e p so fd e c i o nt r e ea n a l y s i s a r ec l e a r l yd i s c r i b e d a n dw ed e e p l yr e s e a r c ht h ea l g o r i t h mo fi d 3 f o r t h t h ei d 3a l g o r i t l l i i ii sa m e l i o r a t e df r o mt w oa s p e c t st oi m p r o v et h e e f f i c i e n c yo f t h ea l g o r i t h ma n dr e d u c et h e q u a n t i t yo ft h ed a t a t ob e p r o c e s s e da n de n h a n c et h ep r e d i c t i v ea b i l i t yo ft h ea l g o r i t h ma n di t i s a p p r o v e dt ob ee f f i c i e n c yt h r o u g har e a l w o r l da p p l i c a t i o n 。 f i f t h ，a t o u r i s tc o n s u m ed a t a a n a l y s i ss y s t e m i s d e s i g n e d t h e s i g n i f i c a n c et or e s e a r c ht h ec o n s u m i n gd a t ao ft h et o u r i s t si si n d i c a t e d t h e nt h ef u n c t i o n so ft h i s s y s t e m a r e e x p l a i n e d ，w h i c h i n c l u d ed a t a p r e p r o c e s s i n g ，t h eo u t g or o u t ea n a l y s i so ft h et o u rc o n s u m e r ，t h ec o n s u m e l a b i l i t y o ft h et o u r i s mc o n s u m e r t h e p r e p r o c e s s i n g m e t h o d so fd a t a p r e p r o c e s s i n gm o d u l ea r ed i s c u s s d a t am i n i n gt e c h n i q u e su s e di nt h eo u t g o r o u t ea n a l y s i so ft h et o u r i s mc o n s u m e ri ss e q u e n t i a lp a t t e r n sm i n i n ga n dt h e c o n s u m ea b i l i t yo ft h et o u r i s mc o n s u m e ri sc l a s s i f i c a t i o n t h ea l g o r i t h m s w h i c hw eu s ei nt h e s et e c h n i q u e s ，a r ed e p i c t e d f i n a l l y ，w ei m p l yt h es y s t e m o nt h et o u r i s mc o n s u m e ro fs h a n d o n ga n de s t i m a t et h er e s u l t f i n a l l y ，a l l t h er e s u l t sa r es u m m a r i z e d ，a n dt h es t u d yp r o s p e c ti s d i s c u s s e d k e y w o r d s ：d a t am i n i n g ：s e q u e n t i a lp a t t e r n sm i n i n g ：c 1 a s s i f i c a t i o n ：d e c i s i o n t r e e ： 2 第一章引言 分支，给开发满足这类要求的数据深度分析工具提供了坚实而丰富的理论和技术基 础。2 0 世纪9 0 年代中期以来，许多软件开发商，基于数理统计、人工智能“1 、机 器学习“埘、神经网络旧州、进化计算1 和模式识别o “等多种技术和市场需求，开 发了许多数据挖掘与知识发现软件工具，从而形成了近年来软件开发市场的热点。 目前数据挖掘工具已开始向智能化整体数据分析解决方案发展，这是从数据到知识 演化过程中的一个重要里程碑。 数据挖掘工具“”可以帮助从大量数据中发现所存在的特定模式规律，从而可以 为商业活动、科学探索和医学研究等诸多领域提供所必需的信息知识，而且数据挖 掘正在不断的探索更多领域的应用，我国有着丰富的旅游资源，早在一九七九年一 月六日邓小平同志同国务院负责人谈话的时候就说过“旅游事业大有文章可做，要 突出的搞，加快地搞。旅游赚钱多，来得快，没有还不起外债的问题，为什么不能 大搞呢? 要狠抓一下旅游和城市建设。改革开放以来，旅游业作为我国国民经济新 的增长点和许多地区的支柱产业，正在不断加快发展：旅游业作为综合性很强的产 业，产业链已经延伸到我国经济社会生活的诸多方面。1 9 9 8 年中央经济工作会议上 又正式提出旅游是国民经济新的增长点，要作为国民经济新的增长点来培育。从 1 9 9 8 年到现在5 年多时间了，可以说旅游作为国民经济新的增长点的培育任务已经 完成了，现在正发挥新的增长点的作用，进一步就是要培育新兴支柱产业。2 0 0 2 年 旅游总收入占g d p 的比重是5 4 4 ，收入额是5 5 6 6 亿元人民币，到2 0 2 0 年我们的 目标是要达到3 6 0 0 0 亿元人民币。3 6 0 0 0 亿元人民币如果以2 0 0 1 年作为基数基本上 是增长了8 倍，这2 0 年中年均增长速度要达到1 0 7 ，这是一个非常高的持续的增 长速度。因此本文把数据挖掘应用于旅游行业分析中具有很高的学术价值和广阔的 市场空间。 1 2 数据挖掘研究内容和本质 1 2 1 相关概念介绍 数据挖掘，又称为数据库中的知识发现( k n o w l e d g ed i s c o v e r yd a t a b a s e ，简 称k d d ) “1 ：指从大型数据库或数据仓库提取隐含的、未知的、非平凡的及有潜在应 用价值的信息或者模式。 1 2 2 数据挖掘产生的必然性 数据挖掘技术并不是一项全新的技术，它的出现与发展有着其自身的必然性。 2 第一章引言 随着公司数据库的猛增，特别是数据仓库的出现，原有的数据库工具已经无法满足 用户的需求。用户不仅需要一般的查询工具和报表工具，更需要的是那些能够帮助 他们从浩瀚的数据海洋中提取出高质量知识的工具。数据挖掘使数据库技术进入一 个更高级的阶段，它不仅能对过去的数据进行查询和遍历，并且能够找出过去数据 之间潜在的联系，从而促进信息的传递，所以d m 的出现正是符合这一发展潮流。 同时对数据挖掘技术进行支持的三种基础技术( 海量数据搜索、强大的多处理 器计算机、数据挖掘算法) 已经发展成熟，也为数据挖掘的出现奠定了基础。 1 2 3 数据挖掘过程的步骤 数据挖掘是一个高级的处理过程，它从大量的数据集中识别出以模式来表示的 知识。高级的处理过程是指一个多步骤的处理过程，多步骤之间相互影响、反复调 接，形成一种螺旋式上升过程，如图1 - 1 所示。 图l l 数据挖掘的步骤 数据挖掘的过程主要包括以下四个步骤： 数据采集 数据挖掘的处理对象是大量的数据，这些数据一般存储在数据库系统中，是长 期积累的结果。这些数据不仅是本系统的内部数据，同时也包括相关的外部数据， 数据越是全面，挖掘的效果越好；可信度也越大。 数据预处理 数据采集的数据往往不适合直接进行知识挖掘，因为这些数据实际上是一些 “脏数据”，这些“脏数据”有以下几个特点： i ) 杂乱性：因为各个系统的数据缺乏统一的标准和定义，数据结构差异较大。 i i ) 重复性；对同一客观事物在数据库中存在其两个或两个以上完全相同的物 第一章引言 理描述，有信息冗余的情况。 i i i ) 不完整性：由于实际系统设计时存在的缺陷以及一些使用过程中人为因素 所造成的影响，数据记录中可能会出现有些数据属性的值丢失或不确定的情况。 数据挖掘 数据挖掘是数据挖掘过程最关键的步骤，也是技术难点所在。研究数据挖掘的 研究人员中大部分都在研究挖掘技术，采用较多的技术有：决策树、分类、聚类、 粗糙集、关联规则、序列模式分析等等。数据挖掘根据知识发现的目标，选取相应 的算法和合适的参数，分析数据，得到可能形成知识的模式模型。 评价、解释模式模型 挖掘过程得到的模式模型，有可能是没有实际意义或没有实用价值的，也有可 能不能准确反映数据的真实意义，甚至在某些情况下是与事实相反的，因此需要评 估，确定哪些是有效的、有用的模式。评估可以根据用户多年的经验，有些模式也 可以直接用数据来检验其准确性。这个步骤还包括把模式以易于理解的方式呈现给 用户。 1 2 4 数据挖掘的体系结构 数据挖掘系统可以大致分为三层结构，如图1 - 2 所示第一层是数据源，包括 数据库、数据仓库。数据挖掘不一定要建立在数据仓库的基础上，但如果数据挖掘 与数据仓库协同工作，则将大大提高数据挖掘的效率第二层是数据挖掘器，利用 数据挖掘方法分析数据库中的数据，包括关联分析、序列模式分析、分类分析、聚 类分析等。第三层是用户界面，将获取的信息以便于用户理解和观察的方式反映给 用户，可以使用可视化工具。 图卜2 数据挖掘的体系结构 4 第一章引言 1 3 数据挖掘的主要模式 数据挖掘是数据挖掘过程中最核心、最重要的部分，它是采用机器学习、统计 等方法进行知识学习的阶段。 1 3 1 模式的相关知识 数据 数据是指一个有关事实( f ) 的集合( 如学生档案数据库中有关学生基本情况 的各条记录) ，它是用来描述事物有关方面的信息。一般说来这些数据应该是准确 无误的。 模式 模式是一个用语言l 来表示的一个表达式e ，它可以用来描述数据集f 中数据 的特性，e 所描述的数据是集合f 的一个子集f e 。 e 作为一个模式要求它比列举数据子集f e 中所有元素的描述方法简单。例如， “如果成绩在8 1 9 0 之间，则表示成绩优良”，这种描述可称为一个模式，而“如 果成绩为8 1 、8 2 、8 3 、8 4 、8 5 、8 6 、8 7 、8 8 、8 9 或9 0 ，则成绩优良”就不能称之 为是一个模式。 1 3 2 模式的种类 模式有很多种，其中按功能可分有两大类：预测型( p r e d i c t i v e ) 模式和描述 型( d e s c r i p t i v e ) 模式。 1 ) 预测型模式 预测型模式是可以根据数据项的值精确程度确定某种结果的模式。挖掘预：涣4 型 模式所使用的数据也都是可以明确知道结果的。例如，根据各种动物的资料，可以 建立这样的模式：凡是胎生的动物都是哺乳类动物。当有新的动物资料时，就可以 根据这个模式判别此动物是否是哺乳动物。 2 ) 描述型模式 描述型模式是对数据中存在的规则做一种描述，或者根据数据的相似性把数据 分组。描述型模式不能直接用于预测。例如，在地球上，7 0 的表面被水覆盖，3 0 是土地；拥有两辆汽车或者更多汽车且收入在6 8 万美元之间的家庭彼此非常 相似；体积和年龄是判断疾病x 存在的最重要因素等阅题。 第一章引言 1 3 3 挖掘模式的分类 分类模式 设有一个数据库和一组具有不同特征的类别( 标记) ，该数据库中的每一个记录 都赋予一个类别的标记，这样的数据库称为示例数据库或训练集分类分析就是通 过分析示例数据库中的数据，为每个类别做出准确的描述或建立分析模型或挖掘出 分类规则，然后用这个分类规则对其它数据库中的记录进行分类目前已有多种分 类分析模型得到应用，其中几种典型模型是决策树模型、遗传算法模型、神经网络 模型和粗糙集模型。 时间序列模式 时间序列模式根据数据随时间变化的趋势预测将来的值。这里时间具有广义坐 标的含义，既可以指按时间的先后顺序排列的数据，也可以指按空间的前后顺序排 列的随机数据。从经济到工程技术，从天文到地理气象，几乎在各种领域都会遇到 时间序列。在科技飞速发展的今天，越来越多的时间序列信息被存储在计算机上， 例如证券公司的计算机积累了大量的销售信息，人造卫星观测的气象信息和科学仪 器所检测到的大量生物、地矿等信息也都存在计算机中时间序列中包含有很多有用 的信息。因此，对时间序列进行分析具有很重要的价值。 聚类模式。 聚类是用于发现数据库中需要分类的对象集合中的对象类，其划分依据是把一 组个体按照相似性归成若干类别，即所谓的”物以类聚”，目的是使属于同一类的 个体之间的距离尽可能的小，而不同的类别的个体间的距离尽可能的大。 关联分析 利用关联规则进行数据挖掘在数据挖掘研究领域，对于关联分析的研究开展 得比较深入，人们提出了多种关联规则的挖掘算法，如a p r i o r i 、s t e m 、h i s 、d h p 等算法关联分析的目的是挖掘隐藏在数据间的相互关系，它能发现数据库中形如 “9 0 的顾客在一次购买活动中购买商品a 的同时购买商品b ”之类的知识。关联 规则挖掘的形式描述是： 设i = i 。，i2 ，”，i ) 是i n 个不同项目的集合，给定一个交易数据库d ，其中每一 个交易r 是，中一组项目的集合，即t ，一条关联规则就是形如x j y 的蕴涵 式，其中x c j ，y c ，z n y = 。如果d 中c 的包含x 的交易同时包含y ，则关 联规则x j y 在d 中置信度c 成立如果d 中s 的交易包含x u y ，则关联规则 6 第一章引言 xj y 在d 中具有支持度s 。在进行关联分析时、用户需要输入两个参数：最小置 信度和最小支持度关联分析就是生成所有具有用户指定的最小置信度和最小支持 度的关联规则 序列摸式 序列模式与关联模式相仿，其目的也是为了挖掘数据之间的联系，但是序列模 式分析的侧重点在于分析数据之间的前因后果。为了发现序列模式，不仅需要知道 事件是否发生，而且需要确定事件发生的时间。例如，在购买彩电的人们当中，6 0 的人会在3 个月内购买影碟机。 1 4 数据挖掘的研究对象及目前的研究情况 1 4 1 数据挖掘的研究对象 数据挖掘中要分析的数据的范围非常广泛，从自然科学、社会科学、商业数据， 到科学处理产生的数据或卫星观测得到的数据。它们的数据表示形式也是各种各 样，有关系型，也有层次型、网状型。由于关系数据库应用广泛，具有规整统一的 组织结构，规范通用的查询语言，特别是关系之间及属性之间具有平等性的优点。 因此，目前k d d 的主要对象仍然是关系数据库。 1 4 2 国外数据挖掘研究情况 从数据库中发现知识( 1 【d d ) 一词首次出现在1 9 8 9 年举行的第十一届国际联合 人工智能学术会议上。随后在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年都举行k d d 专题讨论会， 汇集来自各个领域的研究人员和应用开发者，集中讨论数据统计、海量数据分析算 法、知识表示、知识运用等问题。随着参与人员的不断增多，k d d 国际会议发展成 为年会。到目前为止，由美国人工智能协会主办的k d d 国际研讨会已经召开了8 次， 规模由原来的专题讨论会发展到国际学术大会，研究重点也逐渐从发现方法转向系 统应用，注重多种发现策略和技术的集成，以及多种学科之间的相互渗透。1 9 9 9 年，亚太地区在北京召开的第三届p a k d d 会议收到1 5 8 篇论文，空前热烈。i e e e 的k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊率先在1 9 9 3 年出版了k d d 技术专刊。并 行计算、计算机网络和信息工程等其他领域的国际学会、学刊也把数据挖掘和知识 发现列为专题和专刊讨论，甚至到了脍炙人口的程度。 数据挖掘在1 9 9 5 年召开了第一届知识发现与数据挖掘国际学术会议。该会议是 7 第一章引言 由1 9 8 9 年至1 9 9 4 年举行的四次数据库中知识发现国际研讨会发展来豹。数据挖掘 研究界于1 9 9 8 年建起了一个新的学术组织a c m - s i g k d d ，即 c m 下的数据库中知识 发现专业组( s p e c i a li n t e r e s t e dg r o u po nk n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 。 1 9 9 9 年a c m s i g k d d 组织了第五届知识发现与数据挖掘国际学术会议( k d d 9 9 ) 。专 题杂志d a t am i n i n ga n dk n o w l e d g ed i s c o v e r y 自1 9 9 7 年起有k l u w e r s 出版社出 版。a c m - s i g k d d 还出版了一种季刊电子通信s i g k d de x p l o r a t i o n s 。还有一些其他 国际或地区性的数据挖掘会议如“知识发现与数据挖掘太平洋亚洲会议”( p a k d d ) ， “数据库与知识发现原理与实践欧洲会议”( p k a d d ) 和“数据仓库与知识发现国际 会议”( d a w a l ( ) 。 涉及数据挖掘的研究成果已在许多数据库国际会议论文集发表，包括 “a c m - s i g m o d 数据管理国际会议”( s i g m o d ) ，“超大型数据库国际会议”( v l d b ) ， “a c m - s i g m o d - s i g a r t 数据库原理研讨会”( p o d s ) ，“数据工程国际会议”( i c d e ) ， “扩展数据库技术国际会议”( e d b t ) ，“数据库理论国际会议”( i c d t ) “信息与知 识管理国际会议”( c i k m ) ，“数据库与专家系统应用国际会议”( d e x a ) 和“数据库 系统高级应用国际会议”( d a s f 从) 。数据挖掘的研究也发表在主要数据库杂志上， 包括 i e e e 知识与数据工程汇刊( t k d e ) ，a 明数据库系统汇刊( t o d s ) ， a c m 杂志( j a c m ) 信息系统，v l d a 杂志，数据与知识工程，和智能信息系统 国际杂志( j i i s ) 。 此外，在i n t e r n e t 上还有不少k d d 电子出版物，其中以半月刊k n o w l e d g e d i s c o v e r yn u g g e t s 最为权威( h t t p ：w v 哪k d n u g g e t s c o m s u b s c r i b e h t m l ) 。在 网上还有许多自由论坛，如d me m a i lc l u b 等。至于d m k d 书籍，可以在任意家 计算机书店找到十多本。目前，世界上比较有影响的典型数据挖掘系统有：s a s 公 司的e n t e r p r i s em i n e r 、i b m 公司的i n t e l l i g e n tm i n e r 、s g i 公司的s e t m i n e r 、 s p s s 公司的c l e m e n t i n e 、s y b a s e 公司的w a r e h o u s es t u d i o 、r u l e q u e s tr e s e a r c h 公司的s e e 5 、还有c o v e r s t o r y 、e x p l o r a 、k n o w l e d g ed i s c o v e r yw o r k b e n c h 、d b m i n e r 、 q u e s t 等。读者可以访问h t t p ：孵w d a t a m i n i n g l a b c o m 网站，该网站提供了许多 数据挖掘系统和工具的性能测试报告。 1 4 3 国内数据挖掘研究情况 国内从事数据挖掘研究的人员主要在大学，也有部分在研究所或公司。所涉及 的研究领域很多，一般集中于学习算法的研究、数据挖掘的实际应用以及有关数据 挖掘理论方面的研究。目前进行的大多数研究项目是由政府资助进行的，如国家自 然科学基金、8 6 3 计划、“九五”计划等，但还没有关于国内数据挖掘产品的报道。 8 第一章引言 与国外相比，国内对数据挖掘的研究稍晚，没有形成整体力量。1 9 9 3 年国家自 然科学基金首次支持对该领域的研究项目。目前，国内的许多科研单位和高等院校 竟相开展知识发现的基础理论及其应用研究，如清华大学、中科院计算技术研究所、 空军第三研究所、海军装备论证中心等。北京系统工程研究所对模糊方法在知识发 现中的应用进行了较深入的研究，北京大学也在开展对数据立方体代数的研究：华 中理工大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉林大学 等单位开展了对关联规则挖掘算法的优化和改造；南京大学、四川联合大学和上海 交通大学等单位探讨、研究了非结构化数据的知识发现以及w e b 数据挖掘；我校数 据仓库与数据挖掘课题组在数据仓库与数据挖掘相结合方面的研究取得了较大的 进展，目前正积极推进研究成果在金融、统计、商业和制造业领域的应用。 1 5 数据挖掘的应用领域以及发展情况 数据挖掘工具的出现，让人们已经意识到数据挖掘技术带来的有利可图的应用 前景，它的主要应用体现在以下几个方面： 科学研究应用 从科学研究方法学的角度看，随着先进的科学数据收集工具的使用，如观测卫 星、遥感器、d n a 分子技术等，数据量非常大，传统的数据分析工具无能为力，因 此必须有强大的智能型自动数据分析工具才行。 数据挖掘在天文学上有一个非常著名的应用系统：s k i c a t ，它是美国加州理工 学院喷气推进实验室( 即设计火星探测器漫游者号的实验室) 与天文科学家合作开 发的用于帮助天文学家发现遥远的类星体的一个工具。s k i c a t 既是第一个获得相当 成功的数据挖掘应用，也是人工智能技术在天文学和空间科学上第一批成功应用之 一。利用s k i c a t ，天文学家已发现了1 6 个新的极其遥远的类星体。 数据挖掘在生物学上的应用主要集中于分子生物学特别是基因工程的研究上。 近几年，通过用计算生物分子系列分析方法，尤其是基因数据库搜索技术已在基因 研究上作出了很多重大发现。 市场行销 数据挖掘在行销业上的应用可分为两类：数据库行销( d a t a b a s em a r k e t i n g ) 和货篮分析( b a s k e ta n a l y s i s ) 。 数据库行销中，数据挖掘将用户进行分类，这样当一个新用户到来时，通过顾 客信息预测其购买的可能性，从而可以根据结果有针对性地对顾客进行推销。 货篮分析是分析市场销售数据以识别顾客的购买行为模式，例如：如果a 商品 被选购，那么b 商品被购买的可能性为9 5 ，从而帮助确定商店货架的布局排放以 9 第一章引言 促销某些商品，并且对进货的选择和搭配上也更有目的性。这方面的系统有； o p p o r t u n i t ye x p l o r e r ，它可用于超市商品销售异常情况的因果分析等；另外i b m 公司也开发了识别顾客购买行为模式的一些工具i n t e l l i g e n tm i n e r 和q u e s t 中 的一部分。 金融投资 典型的金融分析领域有投资评估和股票交易市场预测，分析方法一般采用模型 预测法( 如神经网络或统计回归技术) 。数据挖掘可以通过对已有数据的处理，找 到数据对象之间的关系，然后利用学习得到的模式进行合理的预测。这方面的系统 有f i d e l i t ys t o c ks e l e c t o r ，l b sc a p i t a lm a n a g e m e n t 。前者的任务是使用神经 网络模型选择投资，后者则使用了专家系统、神经网络和基因算法技术来辅助管理 多达6 亿美元的有价证券。 欺诈甄别 银行或商业上经常发生诈骗行为，如恶性透支等，这些给银行和商业单位带未 了巨大的损失。进行诈骗甄别主要是通过总结正常行为和诈骗行为之间的关系，得 到诈骗行为的一些特性，这样当某项业务符合这些特征时，可以向决策人员提出警 告。这方面应用非常成功的系统有：f a l c o n 系统和f a i s 系统。f a l c o n 是h n c 公 司开发的信用卡欺诈估铡系统；它已被相当数量的零售银行用于探测可疑的信用卡 交易；f a i s 则是一个用于识别与洗钱有关的金融交易的系统，它使用的是一般的政 府数据表单。 产品制造 在产品的生产制造过程中常常伴随有大量的数据，如产品的各种加工条件或控 制参数( 如时间、温度等控制参数) ，这些数据反映了每个生产环节的状态，不仅 为生产的顺利进行提供了保证，而且通过对这些数据的分析，得到产品质量与这些 参数之间的关系。这样通过数据挖掘对这些数据的分析，可以对改进产品质量提出 针对性很强的建议，而且有可能提出新的更高效节约的控制模式，从而为制造厂家 带来极大的回报。这方面的系统有c a s s i o p e e ( 由a c k n o s o f t 公司用k a t e 发现工具 开发的) ，已用于诊断和预测在制造波音飞机制造过程中可能出现的问题。 通信网络管理 在通信网络运行过程中，会产生一系列警告，这些警告有的可以置之不理，而 有的如果不及时采取措施则会带来不可挽回的损失。数据挖掘可以通过分析已有的 警告信息的正确处理方法以及警告之间的前后关系的记录，得到警告之间的序列模 式规则，这些有价值的信息可用于网络故障的定位检测和严重故障的预测等等任务 中。这方面的系统有：芬兰h e l s i n k i 大学与一家远程通信设备制造厂家合作的t a s a 系统。 i o 第一章引言 1 6 数据挖掘未来的发展方向 当前，d m k d 研究正方兴未艾，g a r t n e rg r o u p 的一次高级技术调查将数据挖掘 和人工智能列为“未来三到五年内将对工业产生深远影响的五大关键技术”之首， 并且还将并行处理体系和数据挖掘列为未来五年内投资焦点的十大新兴技术前两 位。预计在2 1 世纪还会形成更大的高潮，当前，d i v i k d 研究方兴未艾，其研究与开 发的总体水平相当于数据库技术在7 0 年代所处的地位，迫切需要类似于关系模式、 d b m s 系统和s q l 查询语言等理论和方法的指导，才能使d j i k d 的应用得以普遍推广。 预计在本世纪，d k i ) 的研究还会形成更大的高潮，研究焦点可能会集中到以下几个 方面： 1 ) 语言的形式化描述，即研究专门用于知识发现的数据挖掘语言，也许会像s q l 语言一样走向形式化和标准化； 2 ) 寻求数据挖掘过程中的可视化方法，使知识发现的过程能够被用户理解，也 便于在知识发现的过程中进行人机交互； 3 ) 性能问题。这其中包括效率、可扩展性和数据挖掘算法的并行化等问题。 数据挖掘算法的效率( e f f i c i e n t ) 与可扩展性( s c a l a b l e ) 。为了能够有效地 从数据库大量的数据中抽取模式知识，数据挖掘算法就必须是高效的和可扩展的。 算法的可扩展性表现在它的运行时间与所处理的数据规模呈线性关系，在假设挖掘 系统可利用的其它资源不变的情况下( 如：内存和硬盘空间等) ：这也就意味着当被 挖掘数据的规模确定后，相应数据挖掘算法的运行时间是可以预测的，当然也是可 以接受的。从数据库角度来要求知识发现算法、效率和可扩展性也是构造数据挖掘 系统的一个关键问题。前面所介绍的数据挖掘方法与用户交互中的许多问题也涉及 到效率与可扩展性的问题。 并行、分布和增量更新算法。数据库中数据的巨大规模、广泛分布的数据存储 地点、以及一些数据挖掘算法的计算复杂性等，都极大地推动了并行分布( p a r a l l e l a n dd i s t r i b u t e d ) 挖掘算法的研究与开发。这类算法将数据分为若干份 ( p a r t i t i o n s ) 进行并行处理，然后将处理获得结果和并在一起。此外，一些数据 挖掘过程所涉及的高昂代价也促使了增量式( i n c r e m e n t a l ) 数据挖掘算法的发展， 这类增量挖掘算法无需每次挖掘时均对整个数据库进行挖掘而只需对数据库中的 增量数据进行挖掘即可，当然增量挖掘算法需要对之前所挖掘获得的模式知识进行 增量式修改与完善。 4 ) 研究在网络环境下的数据挖掘技术( w e b m i n i n g ) ，特别是在因特网上建立 d m k d 服务器，并且与数据库服务器配合，实现w e b m i n i n g ； 5 ) 数据库类型多样化所涉及的问题“”“” 第一章引言 关系和复杂类型数据的处理。数据库与数据仓库的类型有许多种，期望一个数 据挖掘系统能够对所有类型的数据都能够很好地完成挖掘任务是不现实的。鉴于关 系数据库与数据仓库应用较广，研究设计高效有效地挖掘这类数据的数据挖掘系统 是必要的。然而其它数据库包含复杂数据对象，如：超文本( h y p e r t e x t ) 、多媒体数 据、空间数据、时间数据或交易数据，显然一个数据挖掘系统不可能满足挖掘不同 数据类型并完成不同挖掘任务的要求。因此需要根据特定的挖掘数据，构造相应的 数据挖掘系统。 异构数据库和全球信息系统的信息挖掘。本地和广域计算机网络系统( 如：互 联网) 将许多数据源连接在一起，从而构成了一个巨大的、分布的、异构 ( h e t e r o g e n e o u s ) 的数据库。如何从来自不同数据源( 具有不同数据语义) ，其中包 括：结构化( s t r u c t u r e d ) 、半结构( s e m i s m l c t u r e d ) 数据和无结构( u n s t r u c t u r e d ) 数 据，挖掘出所需要的模式知识是数据挖掘研究所面临巨大挑战。数据挖掘或许能够 帮助从多个异构数据库中挖掘高层次的数据规律，而这些数据规律是无法通过简单 查询系统就可获得的。由此甚至还可以帮助改善信息交换和异构数据库之间的互操 作性。 6 ) 交互式发现知识发现。目前很多数据挖掘研究工作的方向主要集中在算法的 效率上，大多数数据挖掘系统还没有充分考虑用户的参与而使得交互性较差。在我 们的研究过程中，发现数据挖掘与人工智能有密切的关系，背景知识、领域知识在 智能化、自动化的数据挖掘系统中居于很重要的地位，充分适用背景知识及领域知 识能使得在巨大的数据空间中的搜索更为有效、更有针对性。 7 ) 私有数据的保护与数据安全性 当我们可以在不同的角度和不同的层次看到数据库中的数据时，这与我们保护 数据的安全性和保护私人数据的目标相抵触因此对在什么情况下数据挖掘将会导 致对私有数据造成侵犯和采用何种措施来防止敏感信息的泄露的研究显得非常重 要 第二章序列模式挖掘算法的分析与比较 第二章序列模式挖掘算法的分析与比较 序列模式挖掘是在给定时间窗口内的序列集中挖掘所有最长频繁序列的过程， 它是数据挖掘技术中一个非常重要的研究课题和领域，它首先是由r a g r a w a la n d r s r i k a n t “”针对超市中购物篮数据的分析提出来的。序列模式的一个典型例子就 是”在一个月内，购买傲慢与偏见的顾客中有7 0 9 6 也购买基督山伯爵”， 书店可以利用这些模式进行促销、摆设柜台，等等。又例如，在一股票交易数据库 中，有可能挖掘出这样的信息：在某一段时问内( 几天或几周) 。股民购买”四川长 虹”，接着购买”南方摩托”，而后购买”青岛海尔”，如序列： ” 南方摩托”一 ”青岛海尔” 出现的频率较高，可以利用这一模式进行股市分析。 序列模式挖掘具有广阔的应用领域，主要有： 零售数据挖掘中识别顾客购买行为，发现顾客购买模式和趋势，按系统的方式 加以分析，得出顾客的消费或忠诚度的变化，据此对商品的价格和花样进行调整， 改进服务质量，取得更好的顾客保持力和满意程度；d n a 序列模式的研究，可以从 中找出导致各种疾病的基因序列模式；对于电信企业也可以利用序列模式挖掘的发 现来推动电信服务的发展，改进和拓展连带的特殊服务；w e b 日志序列模式挖掘可 以使网管员改善网站的页面组织，针对特定用户进行w e b 页面预取，对个体用户定 制w e b 服务，尽量为大多数访问者的衩9 览提供方便；在金融诈骗案中，也可以利用 序列模式分析工具，对一些异常的访问模式的特征加以分析，识别出一些重要的活 动关系和模式，有助于发现可疑线索，序列模式挖掘也可以帮助企业的用户服务部 门优化对于用户的服务策略，使维修服务效率达到最佳化，其它应用场合还包括客 户关系管理( c 蹦) 、疾病诊断、自然灾害预测等。 序列模式与关联模式相似，最明显的区别是在于它把数据之间的关联性与时间 联系起来，为了发现序列模式，不仅要知道事件是否发生，更确切地可能还需要确 定事件发生的时间或是在哪一段时间内可能出现，目前序列模式挖掘大多集中在下 面两个予过程：找出最大频繁序列生成规则。其中相对较为