（计算机应用技术专业论文）多层高维频繁序列挖掘算法研究.pdf

重庆人学硕士学位论文 中文摘要 摘要 面对“信息爆炸”的现实，人们所遭遇的窘境是难于从海量数据中迅速地获 取有用的信息。数据挖掘技术的产生和发展为人们摆脱这种窘境提供了强有力的 工具。数据挖掘本质上说是让数据说明自身的价值，即按照既定的业务目标，对 大量的数据进行探索、揭示隐藏在其中的规律并将之模型化的先进、有效的方法。 在整个数据挖掘的研究中，算法的研究占有特别重要的地位。这是因为， 数据挖掘面对大数据集( 又称海量数据) ，则算法的效率将对其应用起关键作用； 同时我们面对的计算机系统在其性能上不能满足对大数据集进行快速处理的要 求。所以，对现有的数据挖掘算法进行研究和改进意义重大。考虑到实际的事物 数据库中通常包含项目信息和维( 地点) 信息。有关多层高维频繁序列的知识数 据挖掘显得十分必要和具有实用价值。 本文对数据挖掘中的序列挖掘算法作了较深入的研究。由于类a p r i o r i 算法需 要观多次扫描数据库的缺点，降低了算法的效率而且产生的候选集偏多，从而限 制了其在商业中的应用；f p - t r e e 算法是对类a p r i o r i 算法的一次革命，该算法只需 要扫描两次数据库，但由于采用的是统一的支持度，也使该算法丧失一些优势。 典型的数据挖掘算法采用的是统一的支持度阀值，这样会造成两种不良的后果： 其一，丢失有用的频繁序；其二，对频繁序列产生有瓶颈效应。 本文提出了一种扩展的f p g r o w t h 算法来解决多层高维频繁序列的挖掘问题， 我们称之为e f p 。为了提高e - f p 算法的效率，我们在挖掘过程中采用了可变支持 度阀值。我们提出的e f p 算法不仅可以在层内部产生频繁序列而且可以产生跨层 的频繁序列，同时我们还考虑了维的信息。实验证明我们的e f p 算法比以往的算 法更适合于多层高维频繁序列的挖掘。 聚类分析出于其应用较为广泛，已经成为数据挖掘、数理统计等学科的一个 活跃的研究领域。聚类技术可以应用于模式识别、数据分析、图像处理、网页挖 掘、电子商务等。以往的聚类分析都没有考虑现实世界存在的物体障碍问题从而 影响聚类结果。本文对有障碍物体聚类问题进行了初步的探讨，并且提出了一种 称之为改进的变色龙( a d p c h a m e l e o n ) 的算法来解决有障碍物体聚类问题。 关键词：数据挖掘，f p t r e e 算法，多层高维序列，e f p 算法，聚类 重庆大学硕士学位论文英文摘要 a b s t r a c t w h a ti st h et m u b l ew h e nt l l ep e o p l ef a c et ot h e “i n f o r m a t i o nb o m b ”? i ti sd i 衔c u l t t og e tu s e f u li n f o r m a t i o n sf r o mt h es e ao ft h ed a t aq u i c k l y k d dc o m i n gf o rt h en e e d h a sb e c o m eo n eo ft h es t r o n g e s tw e a p o n st h a tp e o p l ec a nu s et os o l v et h ep a r a d o x i c a l p r o b l e m d a t am i n i n gi st h en o n t r i v i a lp r o c e s so fi d e n t i f y i n gv a l i d ，n o v e l ，p o t e n t i a l l y u s e f u l ，a n du l t i m a t e l yu n d e r s t a n d a b l ep a t t e r n si nd a t a a l g o r i t h mi st h ek e yp a r ti nk d d ，b e c a u s ei t i sc r u c i a lt oe f f i c i e n to fk d d o no n e h a n d ，d a t am i n i n gi su s e dt op r o c e s sl a r g ed a t a b a s e ，a n ds ot h ee f f i c i e n c yo fa l g o r i t h mi s t h em o s ti m p o r t a n t ；o nt h eo t h e rh a n dt h ec o m p u t e ri nu s ei sn o ts a t i s f i e dt ot h e p r o c e s s i n go fl a r g ed a t a b a s e c o n s e q u e n t l y , w es h o u l dm o d i f yp r e s e n ta l g o r i t h mt of i t t h en e e dw h i c hw er e f e ra b o v e n l i sp a p e rs t u d i e st h es e q u e n c em i n i n g a l g o r i t h md e e p l y a p r i o f i b a s e d a l g o r i t h mn e e d s c a nd a t a b a s em a n yt i m e s ，w h i c hd e c r e a s e st h e e f f i c i e n c yo f a p r i o r i b a s e da l g o r i t h m a tt h es a m et i m e ，a p r i o r i - b a s e da l g o r i t h mp r o d u c e sal a r g e n u m b e ro fc a n d i d a t es e t s f p - t r e ea l g o r i t h mi sar e v o l u t i o no f a p r i o r i b a s e da l g o r i t h m ， b e c a u s ei to n l yn e e ds c a l ld a t a b a s et w ot i m e s b u tf p - t r e ea l g o r i t h mp u s h e su n i f o r m m i n i m u ms u p p o r t ，w h i c hl o s s e st h ea d v a n t a g eo ft h ea l g o r i t h m u s u a l l y , r e a ll i f e t r a n s a c t i o nd a t a b a s ec o n t a i nb o t hi t e mi n f o r m a t i o na n dd i m e n s i o ni n f o r m a t i o n k n o w l e d g ea b o u tm u l t i - - l e v e la n dm u l t i - - d i m e n s i o n a l 行e q u e n ti t e m s e ti si n t e r e s t i n ga n d u s e f u l n l cc l a s s i cf r e q u e n ti t e m s e tm i n i n ga l g o r i t h m sb a s e do nau n i f o r mm i n i m u m s u p p o r t ，e i t h e rm i s si n t e r e s t i n gp a t t e r n so fl o ws u p p o r to rs u f f e rf r o mt h eb o t t l e n e c ko f i t e m s e tg e n e r a t i o n i nt h i sp a p e r , w ee x t e n df p - g r o w t ht oa t t a c kt h ep r o b l e mo fm u l t i - l e v e l m u l t i - d i m e n s i o n a lf r e q u e n ti t e m s e tm i n i n g w ec a l li te fp t oi n c r e a s et h ee f f i c i e n c y , w ep u s hv a r i o u ss u p p o r tc o n s t r a i n t si n t ot h em i n i n gp r o c e s s o u re f pa l g o r i t h mc a n d i s c o v e rb o t hi n t e r - l e v e l 行e q u e n ti t e m s e ta n di n t r a - l e v e lf r e q u e n ti t e m s e t m o r e o v e r , w e t a k ed i m e n s i o ni n t oa c c o u n ti no u re f pa l g o r i t h m w es h o wt h a to u re f pa l g o r i t h mi s m o r ef l e x i b l ea tc a p t u r i n gd e s i r e dk n o w l e d g et h a np r e v i o u ss t u d i e s c l u s t e r i n ga n a l y s i sh a sb e e nav e r ya c t i v ea r e ao f r e s e a r c h 。i th a sb e e na p p l i e di n d a t am i n i n g ，w e bm i n i n g ，e c o m m e n c ee t c h o w e v e r , m o s ta l g o r i t h m si g n o r et h ef a c t t h a tp h y s i c a lo b s t a c l e se x i s ti nt h er e a lw o r l da n dc o u l da f f e c tt h er e s u l to fc l u s t e r i n g d r a m a t i c a l l y i nt h i sp a p e r , w ew i l le x p l o r et h ep r o b l e mo fc l u s t e r i n gi nt h ep r e s e n c eo f i l 重庆大学硕士学位论文英文摘要 o b s t a c l e s w ep r o v i d ea l la l g o r i t h mc a l l e da d p c h a m e l e o nt os o l v ei t k e y w o r d s ：d a t am i n i n g ，f p t r e ea l g o r i t h m ，m u l t i l e v e lm u l t i - d i m e n s i o n a li t e m s e t ， e f pa l g o r i t h m ，c l u s t e r i n g i i l 重庆大学硕士学何论文1 绪论 1 绪论 1 1 选题的意义 随着科技的不断创新，各式各样的数据库系统得到了研究与开发，如：时间数 据库、空问数据库、多媒体数据库、工程数据库等。这些数据库系统的开发和应 用使得更多的数据以前所未有的速度及规模存储于用户计算机中。从信息处理的 角度，人们更希望计算机帮助我们分析数据、理解数据、应用数据，帮助我们基 于丰富的数据作出决策，做人力所不能及的事情。于是数据挖掘从大量数据 中用非平凡的方法发现有用的知识就成为一种自然的需求。正是这种需求引 起了广大研究人员的极大兴趣，导致了数据挖掘技术研究的蓬勃开展。 零售业每天从收银机中获取大量数据，据调查显示，这些大量的数据仅仅是用 于做一些报表统计，而一些所谓的决策分析系统也只不过是进行数据统计，浪费 了大量的数据，而且并不能给商家带来经济效益，然而就是在这些看似无用的数 据中隐藏了无限的商机。我们可以运用数据挖掘技术从这些看似无用的数据中发 现规律，找到商机。零售业的利润和风险是共存的，为了保证利润的最大化和风 险的最小化，必须对有关顾客的数据进行科学的整理、分析和归类。采取相应的 优惠措施来留住能给商家带来较大经济效益的顾客群，或者根据顾客的消费模式 预测何时为客户提供何种服务或商品。所以，数据挖掘技术在零售业中得到了广 泛的应用，通过挖掘商家的历史数据如：商品、顾客、销售时间、销售地点以及 商品摆放位置，对这些数据进行分析，发现其数据模式及特征，然后可能发现某 类顾客、消费群体的消费兴趣和习惯，并可预测消费市场的变化趋势。 美国a u t o t r a d e r c o m 是世界上最大的汽车销售站点，每天都会有大量的用户 对网站上的信息点击，寻求信息，该公司运用了s a s 软件进行数据挖掘，每天对 数据进行分析，找出用户的访问模式，对产品的喜好程度进行判断，并设立了特 定服务，取得了商业上的成功。 r e u t e r e s 是世界著名的金融信息服务公司，该公司利用的数据大都是外部的数 据，这样数据的质量就是公司生存的关键所在，所以必须从数据中检测出错误的 成分。r e u t e r e s 用s p s s 的数据挖掘工具s p s s c l e m e n t i n e ，建立数据挖掘模型，极 大地提高了错误数据的检测准确度，保证了信息的正确性和权威性。 b a s se x p o r t 是世界最大的啤酒进出口商之一，在海外8 0 多个市场从事交易， 每个星期传送2 3 0 0 0 份定单，这就需要了解每个客户的习惯，如品牌的喜好等， b a s se x p o r t 用i b m 的i n e e l l i g e n tm i n e r 很好地解决了上述问题。 数据挖掘的目的是否能够达到很大程度上由数据挖掘系统所采用的挖掘算法 重庆大学硕士学位论文1 绪论 决定，一些算法限制了挖掘的复杂度和挖掘的精度，因此，算法在数据挖掘过程 中起了至关重要的作用。本论文主要是研究数据挖掘中的多层高维序列挖掘算法， 针对f p g r o w t h 算法的不足，提出了一种序列挖掘算法一多层高维频繁序列挖掘 算法，通过不同的“阀值”获取更有意义候选集的数量、从而提高挖掘的效率。 本文还就目前研究比较活跃的聚类技术及聚类算法进行了一些研究和探讨，针 对以往绝大部分算法没有考虑有障碍物体聚类问题，提出了改进的c h a m e l e o n ( 变 色龙) 算法，用以解决此类问题。 1 2 数据挖掘技术产生的背景 人类迫切需要将身边的海量的数据转换成有用的信息和知识，使获取的知 数据收集和数据库创建 ( 2 0 世纪6 0 年代和更早) 一原始文件处理 数据库管理系统( 7 0 年代) 一层次关系和网状数据库系统 一关系数据库系统 一数据建模工具：实体一联系模型等 一索引和数据组织技术：b 树，散列等 一查询语言：s q l 等 一用户界面：表单、报告等 查询处理和查询优化 一事务管理恢复和并发控制等 一联机事务处理( o l r p ) 厂、 高级数据库系统 ( 8 0 年代中期现在) 一高级数据模型： 扩充关系、面向对象、 对象关系、演绎 一面向应用： 空间的、时间的、多媒体的、主 、动的、科学的、知识库 厂 、 数据仓库和数据挖掘 ( 8 0 年代后期现在) 一数据仓库和o l a p 技术 一数据挖掘和知识发现 基于w e b 的数据库系统 ( 9 0 年代现在) 一基于x m l 的数据库系统 一w 曲挖掘 图1 1 数据库技术的演化 f i g 1 1t h ee v o l u t i o no f d a t a b a s et e c h n o l o g y 2 重庆大学硕士学位论文1 绪论 识和信息可以广泛应用于商务管理、生产控制、市场分析、工程设计和科学探索 等。随着数据库应用技术和决策支持技术的发展，随着人们对信息和知识需求水 平的提高，数据仓库技术和数据库知识发现技术越来越受到学术界和产业界的广 泛关注。数据库中的知识发现( k d d ) 是近年来随着数据库和人工智能技术的发 展而出现的，它是从大量数据中提取出可信的、新颖的、有效的并能被人理解的 模式的高级处理过程。在过去的3 0 年中，计算机硬件稳定的、令人吃惊的进步使 得功能强大的计算机、数据收集和存储介质的供应成为可能。这些技术极大推动 了数据库和信息产业的发展。 1 2 1 什么是数据挖掘 数据挖掘( d a t a m i n i n g ，简称d m ) ，又称为数据库中的知识发现( k n o w l e d g e d i s c o v e r yd a t a b a s e ，简称k d d ) 1 2 2 1 ： 指从大型数据库或数据仓库中提取隐含的、未知的、非平凡的及有潜在应用价 值的信息或者模式。 例如，商品销售商需要从大量日积月累的原始数据中发现其内在的规律以供预 测未来趋势以及提供更好的服务。数据挖掘其实是一种决策支持过程，它融合了 数据库、人工智能、数理统计等多个领域的理论和技术，高度自动化地分析企业 原始数据，作出归纳性的推理，从中挖掘出潜在的规律，帮助企业作出正确的决 策。 1 2 2 数据挖掘产生的必然性 数据挖掘技术并不是一项全新的技术，它的出现与发展有着其自身的必然性。 随着公司数据库记录的猛增，特别是数据仓库的出现，原有的数据库工具已经无 法满足用户的需求，用户不仅需要一般的查询工具和报表工具，更需要的是那些 能够帮助他们从浩瀚的数据海洋中提取出高质量知识的工具。数据挖掘使数据库 技术进入一个更高级的阶段，它不仅能对过去的数据进行查询和遍历，并且能够 找出过去数据之间潜在的联系，从而促进信息的传递，所以数据挖掘的出现正符 合这一时代和科技的发展潮流。 同时随着数据挖掘技术的三种基础技术( 海量数据搜索、强大的多处理器计算 机、数据挖掘算法) 已经发展成熟，也为数据挖掘的出现奠定了坚实的技术基础。 从数据库技术的起步到到数据挖掘技术的出现、发展，数据库技术的演化过程 如图1 1 。 1 2 3 数据挖掘的进化历程 重庆火学硕士学位论文1 绪论 进化阶段商业问题支持技术产品厂家产品特点 j 数据搜集“过去五年中我的提供历史性的、 计算机、磁带和磁盘i b m ，c d c r 6 0 年代)总收a 是多少? ” j f 漕 态的数据信息 关? 紊数据库 数据访问“在新英格兰的分部去年 ( r d b m s ) 结 = ；i 化查询巨；( m a c l e 、s y b 8 s e 、| | 在记录级 语言( s q l ) ，o d b c 5 i l n f o r m i x 、 。i b m 。、缸供历史性的、 ( 8 0 年代1 三月的销售额是多少? ” o r a c l e 、s y b a s e , i n f o r m i x 、；v l i e r o s o t t动态数据信息 i b m 、m i s o f t “在新英格兰的分在各种层 数据仓库；联机分析处理 p i l o t 、c o m s h a r e 、 都去年三月的销售额是 _ 漩上提供回溯 决策支持( o l a p ) 、多维数据库。a r b o r 、c o g n o s 、 多少? 波士顿据此可得韵、动态的数据 ( 9 0 年代1数据仓库m i c r o s t r a t e g y l 出什么结论? ”： 信息 数据挖掘| - 下个月波士顿的销售会l 高级算法、多处理器计算争n o t 、l o c i d a e e d 、i b m 、 j提供预测性信息 ( 正在流行) i 怎么样? 为什么? ”l 机、海量数据库i s g i 其他初创公司 1 3 数据挖掘的研究对象及目前的研究情况 1 3 1 数据挖掘的研究对象 数据挖掘中分析的数据的范围非常广泛，从自然科学、社会科学、生命科学到 科学处理产生的数据或卫星观测得到的空间数据等。它们的数据表示形式也是各 种各样，有关系型，也有层次型、网状型。由于关系数据库应用广泛，具有规范 统一的组织结构，规范通用的查询语言，特别是关系之间及属性之间具有平等性 的优点，使得关系数据库得以成为数据库系统的主流。因此，目前k d d 的主要研 究对象仍然是关系数据库。 1 3 2 国外数据挖掘研究情况 “知识发现”( k d d ) 一词是1 9 8 9 年在美国底特律市召开的第一届k d d 国际 学术会议上正式形成的。历次会议所讨论的主题包括：定性知识与定量知识的发 现；数据汇总；知识发现的方法 数据依赖关系的发现与分析；发现过程中知识 的应用；集成的交互式的知识发现系统；知识发现的应用等。随着k d d 在学术界 和工业界的影响越来越大，国际k d d 组委会于1 9 9 5 年把专题讨论会更名为国际 会议，在加拿大蒙特利尔市召开了第一届知识发现与数据挖掘国际学术会议，以 后每年召开一次。 目前，国外数据挖掘的发展趋势其研究方面主要有：对知识发现方法的研究， 4 重庆大学硕士学位论文 1 绪论 如近年来注重对b a y e s ( 贝叶斯) 方法以及b o o s t i n g 方法的研究和提高；传统的统 计学回归法在k d d 中的应用；k d d 与数据库的紧密结合。 1 3 3 国内数据挖掘研究情况 国内从事数据挖掘研究的人员主要在大学，也有部分在研究所或公司。所涉及 的研究领域很多，一般集中于学习算法的研究、数据挖掘的实际应用以及有关数 据挖掘理论方面的研究。目前，国内k d d 的研究主要集中在k d d 与空间地理信 息的紧密结合从而应用于国土规划、农业生产、疾病预报( 如2 0 0 3 年的s a r s ) 。 目前进行的大多数研究项目是由政府资助进行的，如国家自然科学基金、8 6 3 计划、 “九五”计划等。 1 4 数据挖掘系统的主要成分 我们采用比较广泛的观点：数据挖掘是从存放在数据库、数据仓库或其他信息 库中的大量数据中挖掘有趣知识的过程。基于这种观点，典型的数据挖掘系统具 有以下主要成分( 见图1 2 ) ： 数据库、数据仓库或其他信息库：这是一个或一组数据库、数据仓库、电子 表格或其他类型的信息库。可以在数据上进行清理和集成。 数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据仓库服 务器负责提取相关数据。 知识库：该部分是领域知识，用于指导搜索，或评估结果模式的兴趣度。这种 知识可能包括概念分层，用于将属性或属性值组织成不同的抽象层。用户确信方 面的知识也可以包含在内。可以使用这种知识，根据非期望性评估模式的兴趣度。 数据挖掘引擎：该部分是数据挖掘系统的基本部分，由一组功能模块组成，用 于特征化、关联、分类、聚类分析以及演变和偏差分析。 模式评估模块：此部分使用兴趣度度量，并与数据挖掘模块交互，以便将搜索 重点放在有趣的模式上。它可能使用兴趣度阀值过滤发现的模式。模式评估也可 以与挖掘模块集成在一起，这依赖于所用的数据挖掘方法的实现。对于有效的数 据挖掘，应尽可能有效地将模式评估加入到挖掘过程中，以便将搜索限制在有兴 趣的模式上。 图形用户界面：本模块在用户和数据挖掘系统之间通信，允许用户与系统交互， 指定数据挖掘查询或任务，提供信息、帮助搜索聚焦，根据数据挖掘的中问结果 进行探索式数据挖掘。此外，此部分还允许用户浏览数据库和数据仓库模式或数 据结构，评估挖掘的模式，以不同的形式对模式可视化。 重庆大学硕士学位论文 lf j 巫巫互 曰囝 图1 2 典型的数据挖掘系统结构 f i g 1 2 t h es t r u c t u r eo f t y p i c a ld a t am i n i n gs y s t e m 1 5 数据挖掘的应用领域以及发展情况i l j 数据挖掘在社会科学研究领域的应用前景也被越来越多的人所认识。从大量的 历史数据中得出社会发展的规律，预测社会发展的趋势；或从人类的社会行为变 化中寻求对人类行为规律的答案，应用于各种社会问题的求解。数据挖掘工具的 出现，让人们已经意识到数据挖掘技术能够给人们带来广阔的应用前景，它的主 要应用体现在以下几个方面： 市场行销 通过条形码、编码系统、销售管理系统、客户资料管理及其它业务数据中，可 以收集到关于商品销售、客户信息、货存单位及店铺信息等信息资料。从各种应 用系统中采集数据，经过条件分类，放进数据仓库，允许高级管理人员、分析人 员、采购人员、市场人员和广告客户访问，利用d m 工具对这些数据进行分析，为 他们提供高效的科学决策。如对商品进行购物篮分析，分析那些商品是顾客最有 重庆大学硕士学位论文 1 绪论 希望一起购买的。如被业界和上界传诵的经典一一w a l m a r t 的“啤酒和尿布”， 就是数据挖掘透过数据找出人与物之间规律的典型。在零售业应用领域，利用d m 会在很多方面有卓越表现： 了解销售全局：通过分类信息按商品种类、销售数量、商店地点、价格和 日期等了解每天的运营和财政情况，对销售的每一点增长、库存的变化以及通过 促销而提高的销售额都可了如指掌。零售商店在销售商品时，随时检查商品结构 是否合理是十分重要的，如每类商品的经营比例是否大体相当。调整商品结构时 应考虑季节变化导致的需求变化、同行竞争对手的商品结构调整等因素。 商品分组布局：分析顾客的购买习惯，考虑购买者在商店里所穿行的路线、购 买时间和地点、掌握不同商品一起购买的概率；通过对商品销售品种的活跃性分 析和关联性分析，采用主成分分析方法，建立商品设置的最佳结构和商品的最佳 布局。 降低库存成本：通过数据挖掘系统，将销售数据和库存数据集中起来，通过数 据分析，以决定对各个商品各色货物进行增减，确保合适的库存。数据仓库系统 还可以将库存信息和商品销售预测信息，通过电子数据交换( e d i ) 直接送到供应 商那里，这样省去商业中介，而且由供应商负责定期补充库存，零售商可减少自 身负担。 市场和趋势分析：利用数据挖掘工具和统计模型对数据仓库的数据仔细研究， 以分析顾客的购买习惯、广告成功率和其它战略性信息。利用数据仓库通过检索 数据库中近年来的销售数据，作分析和数据挖掘，可预测出季、月销售量，对商 品品种和库存的趋势进行分析。还可确定降价商品，并对数量和运作作出决策。 有效的商品促销：可以通过对一种厂家商品在各连锁店的市场共享分析，客户 统计以及历史状况的分析，来确定销售和广告业务的有效性。通过对顾客购买偏 好的分析，确定商品促销的目标客户，以此来设计各种商品促销的方案，并通过 商品购买关联分析的结果，采用交叉销售和向上销售的方法，挖掘客户的购买力， 并实现准确的商品促销。 科学研究 从科学研究方法学的角度看，随着先进的科学数据收集工具的使用，如观测卫 星、遥感器、d n a 分子技术等，数据都是海量的，传统的数据分析工具已经无能 为力，因此必须借助于强大的智能型自动数据分析工具才行。 数据挖掘在天文学上有一个非常著名的应用系统：s k i c a t ，它是美国加州理 工学院喷气推进实验室( 即设计火星探测器漫游者号的实验室) 与天文科学家合 作开发的用于帮助天文学家发现遥远的类星体的一个工具。s k i c a t 既是第一个获 得相当成功的数据挖掘应用，也是人工智能技术在天文学和空间科学上第一批成 重庆大学硕士学位论文 功应用之一。利用s k l c a t ，天文学家己发现了1 6 个新的极其遥远的类星体。 数据挖掘在生物学上的应用主要集中于分子生物学特别是基因工程的研究上。 近几年，通过用计算生物分子系列分析方法，尤其是基因数据库搜索技术已在基 因研究上作出了很多重大发现。 金融投资 典型的金融分析领域有投资评估和股票交易市场预测，分析方法一般采用模型 预测法( 如神经网络或统计回归技术) 。数据挖掘可以通过对已有数据的处理， 找到数据对象之间的关系，然后利用学习得到的模式进行合理的预测。这方面的 系统有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 l 公司用k a t e 发现工具开发的) ，己用于诊断和预测在制造波音飞机制造过程中可能出现的问 题。 通信网络管理 在通信网络运行过程中，会产生一系列警告，这些警告有的可以置之不理，而 有的如果不及时采取措施则会带来不可挽回的损失。数据挖掘可以通过分析已有 的警告信息的正确处理方法以及警告之间的前后关系的记录，得到警告之间的关 联规则，这些有价值的信息可用于网络故障的定位检测和严重故障的预测等任务 中。这方面的系统有：芬兰h e l s i n k i 大学与一家远程通信设备制造厂家合作的t a s a 8 重庆大学硕十学位论文1 绪论 系统。 i n t e r n e t 应用 w w w 是一个大型的分布式超媒体信息系统。随着w e b 网上信息资源的急剧 膨胀，为了能够有效地控制、查询和利用这些信息，人们对w w w 上的信息资源 发现问题给予了极大的兴趣和关注。 网络信息挖掘是数据挖掘技术在网络信息处理中的应用。从用户的点击信息中 挖掘出w e b 用户访问模式，这样可以有助于理解w e b 上的用户访问模式，从而有 以下好处：辅助改进分布式网络系统的设计性能，如在有高度相关的站点间提供 快速有效的访问通道；能帮助更好地组织设计w e b 主页；帮助改善市场营销决策， 如把广告放在适当的w e b 页上或更好地理解客户的兴趣。 自1 9 9 4 年以来，短短几年间已有一批w e b 资源发现系统或工具投入了实际的 应用，例如：a i t a v i s t a 、l n f o s e e k 、y a h o o 、h o t b o t 、o p e n t e x t 等等1 9 j 。 另外，现代电子商务中提出个性化服务，即在进行网上交易时将所有的客户看 成单个的个体，针对每个客户提供不同的界面。而个性化服务的核心是推荐系统 ( r e c o m m e n d e rs y s t e m ) ，推荐系统中一部分的算法也需要利用数据挖掘技术。推 荐算法利用顾客a 以往购买商品或项目的记录，获得该顾客对所有项目的兴趣、 爱好。然后根据顾客的兴趣、爱好给顾客提出n 个最有可能购买的项目作为推荐 项目33 1 。 疾病预报 利用各地医疗机构提供的疾病发生的数据包括时间、地点、年龄、工作性质、 生活环境、接触史等信息对疾病尤其是传染性疾病进行预报。如，中国科学院2 0 0 3 年针对s a r s 流行的地区和人群对疾病的发生和流行进行预报，取得了较好的实际 效果。 1 6 现有的数据挖掘系统 数据挖掘技术所表现出的广阔应用前景吸引了众多的研究和商业机构，一批数 据挖掘系统被开发出来，并在商业、金融、经济、管理、生命科学等领域都取得 了显著的成果。主要的数据挖掘系统有： ( 1 ) q u e s t 系统。i b m a l m a d e n 研究中心、k d d 的先驱r a g r a w a l 等人开发研制， 它能发现多种知识，关联规则，时序模式，分类规则，模式匹配与分析等等。 ( 2 ) i n t e l l i g e n tm i n e r 。i b m 在w i n d o w sn t3 5 商品化的数据挖掘系统，也是 q u e s t 系统在w i n d o w sn t 环境下的缩影。该系统界面友好，功能强大。 ( 3 ) k e f i r 系统。由k d d 先驱p i a t e t s k ys h a p i r o 等在g t e 实验室开发的，从健 康数据采掘相关知识。 重庆大学硕士学位论文 1 绪论 ( 4 ) s k i c a t 系统。喷气推进实验室开发，用于天体数据的分类。 ( 5 ) d b m i n e r 。这是加拿大西蒙佛瑞斯大学，华人学者韩加炜( j a w e ir a n ) 教授开 发，w i n d o w s9 5 n t 平台上运行，需6 4 m 内存，能够采掘多数据源、多个层 次的知识，特征规则、分类规则、关联规则，分类规则的采掘。该系统界面 友好，功能较多，有可接受的速度。 ( 6 ) i m a c s 。a t & tb r a c h m a n 等人开发，较复杂的知识表达方式。 同时还有其它一些挖掘系统，如s i l i c o ng r a p h i c s ：m i n e s e t 、s a si n s t i t u t e ： e n t e r p r i s em i n e r 、i n t e g r a ls o l u t i o n sl t d ：c l e m e n t i n e 等等。 1 7 数据挖掘未来的发展方向 当前，数据挖掘技术研究正方兴未艾。g a r t n e rg r o u p 的一次高级技术调查将 数据挖掘和人工智能列为“未来三到五年内将对工业产生深远影响的五大关键技 术”之首，并且还将并行处理体系和数据挖掘列为未来五年内投资焦点的十大新 兴技术前两位。预计在2 1 世纪还会形成更大的高潮，研究焦点可能会集中到以下 几个方面： 研究专门用于知识发现的数据挖掘语言，也许会像s q l 语言一样走向形式化 和标准化；寻求数据挖掘过程中的可视化方法，使得知识发现的过程能够被用户 理解，也便于在知识发现过程中的人机交互； 研究在网络环境下的数据挖掘技术，特别是在i n t e m e t 上建立d m k d 服务器， 与数据库服务器配合，实现数据挖掘：加强对各种非结构化数据的挖掘，如文本 数据、图形图像数据、多媒体数据。 但是，无论需求怎样牵引，市场驱动是永恒的，d m k d 将首先满足信息时代 用户的急需，大量基于d m k d 的决策支持软件工具产品将会问世。 1 8 论文的主要研究内容和结构安排 目前，序列模式挖掘算法主要是以下几类算法： 1 ) 以a p r i o r i 为基础的序列模式挖掘算法，该类算法的最大缺点是需要多次 扫描数据库，同时采用哈希树作为主要存储结构，这样造成算法的时间和空间复 杂度较大，同时挖掘的效率也很低。 2 ) 以f p g r o w t h 为代表的非a p r i o r i 类算法。这类算法主要是针对以a p r i o f i 为基础的序列模式算法中多次扫描数据库的缺点来改进的，它只需要对数据库扫 描两次。 f p g r o w t h 的缺点是没有将商品运用概念层次分层，同时也忽略了特殊商品与 一般商品的频率差别。因此，对f p g r o w t h 算法要将其广泛的运用于实际中，仍需 重庆人学硕士学位论文 1 绪论 要加以改进。因此，本文针对这个问题，提出了以f p g r o w t h 算法为基础，结合 m l t 2 d i 中产生候选集的方法的新的序列挖掘算法。多层高维频繁序列算法减少 了候选集产生数量，提高了频繁序列挖掘的效率。 同时我们还注意到现有的聚类算法几乎没有考虑有障碍物体聚类问题，因此我 们提出了改进的变色龙算法来解决此类问题。 论文的结构由以下几部分构成： 第一章绪论，主要阐述了选题的意义，同时介绍数据挖掘的现状、趋势，最 后简单介绍了论文的工作和论文的内容安排。 第二章数据挖掘及聚类技术，本章主要讲述了数据挖掘及聚类技术的相关知 识：数据挖掘的主要内容、体系结构以及数据挖掘的几种模式和常用方法；聚类 技术的常用方法，同时介绍了本人对有障碍物体聚类的初步研究。 第三章序列模式挖掘算法。介绍了序列挖掘算法的两个主流，a p r i o r i 算法和 非a p r i o r i 算法，其中非a p r i o r i 算法以f p g r o w t h 算法作为代表。比较了各种算法 的优缺点。 第四章多层高维频繁序列算法。本章详细阐述了本人提出的一个新的序列挖掘 算法多层高维频繁序列算法。 第五章实验数据和性能评价。通过数据实验，比较了a p r i o r i 类算法和多层高 维频繁序列算法运行时间和候选集数量。最后使用数据集进行挖掘来验证多层高 维频繁序列算法算法的正确性和有效性。 第六章总结了本文的工作，并且提出了以后的研究方向。 重庆大学硕士学位论文2 数据挖掘及聚类技术 2 数据挖掘及聚类技术 2 1 数据挖掘研究内容和本质 随着数据挖掘( d m ) 的研究逐步走向深入，研究数据挖掘和知识发现的三大 技术支柱数据库、人工智能和数理统计已经形成。目前d m 的主要研究内容 包括基础理论、发现算法、数据仓库、可视化技术、定性定量互换模型、知识表 示方法、发现知识的维护和再利用、半结构化和非结构化数据中的知识发现以及 网上数据挖掘等。 数据挖掘所发现的知识最常见的有以下五类： 广义知识( g e n e r a l i z a t i o n ) ：广义知识指类别特征的概括性描述知识。根据数 据的微观特性发现其表征的、带有普遍性的、较高层次概念的、中观和宏观的 知识，反映同类事物共同性质，是对数据的概括、精炼和抽象。 关联知识( a s s o c i a t i o n ) ：它反映一个事件和其他事件之间依赖或关联的知识。 如果两项或多项属性之间存在关联，那么其中一项的属性值就可以依据其他属 性值进行预测。 分类知识( c l a s s i f i c a t i o n c l u s t e r i n g ) ：它反映同类事物共同性质的特征型知 识和不同事物之间的差异型特征知识。 预测型知识( p r e d i c t i o n ) ：它根据时间序列型数据，由历史的和当前的数据去 推测未来的数据，也可以认为是以时间为关键属性的关联知识。 偏差型知识( d e v i a t i o n ) ：偏差型知识是对差异和极端特例的描述，揭示事物偏 离常规的异常现象，如标准类外的特例，数据聚类外的离群值等。 2 2 数据挖掘过程的步骤”4 1 数据挖掘是一个高级的处理过程，它从大量的数据集中识别出以模式来表示的 知识。高级的处理过程是指一个多步骤的处理过程，多步骤之间相互影响、反复 调整，形成一种螺旋式上升过程，如图2 1 所示。在这五个步骤中，模式化是数据 挖掘的核心，用得最广泛又最为经典的模式化方法是数理统计分析，一般情况下， 在数据库或数据仓库字段之间存在两种关系：函数关系( 能用函数公式表示的确 定关系) 和相关关系( 不能用函数公式表示，但仍是相关确定关系) ，对它们可进 行回归分析、相关分析、主成分分析。下面我们分别介绍这五个步骤： 选取数据样本( 抽样) 数据挖掘的处理对象是海量数据，这些数据一般存储在数据库系统中，是长期 积累的结果。这些数据不仅是该系统的内部数据，同时也包括相关的外部数据， 数据越全面，挖掘的效果越好，可信度也越大。 1 2 重庆人学硕士学位论文2 数据挖掘及聚类技术 图2 ，1 数据仓库挖掘流程 f i g 2 1 t h ep r o c e s so f d a t aw a r e h o u s em i n i n g 数据探索 数据探索就是通常所进行的对数据深入调查的过程，从样本数据集中找出规 律和趋势，用聚类分析区分类别，最终要达到的目的就是搞清楚多因素相互影响 的复杂的关系，发现因素之间的相关性。 数据重组 在现实世界中的数据一般是有噪声的、不一致和不完整的，所以数据采集的数 据往往不适合直接进行知识挖掘。因此，在进行数据挖掘之前我们必须对现实数 据进行数据清理( d a t ac l e a n i n g ) 。数据清理通过填写空缺的值，平滑噪声数据，识 别、删除孤立点，并解决不一致以达到“清理”数据的目的。 数据预处理技术可以改进数据的质量，从而有助于提高其后的挖掘过程的精 度和性能。由于高质量的决策依赖于高质量的数据，因此数据预处理是数据挖掘 的重要步骤。检测数据异常、调整数据、并规约待分析的数据，将在决策过程得 重