（管理科学与工程专业论文）数据流离群数据挖掘的研究与应用.pdf

数据流离群数据挖掘的研究与应用 摘要 离群数据可能隐藏着一些真实的、而又出乎人们意料的知识，需要研 究人员认真地对待。数据流由一系列有序到达的、趋于无限的、动态的数 据组成。在数据流上进行离群数据挖掘则是数据挖掘的一个新兴课题，在 同常工作中有广泛的应用。目前由于众多应用领域的需求，数据流挖掘正 逐渐成为数据库、机器学习、统计学等领域的研究热点，并已成为许多研 究领域的有用工具。当数据流这一数据模型在商业和个人信息中被广泛使 用时，一些现有的应用软件需要对快速变化的数据流进行在线分析和处 理。而现有数据流系统的局限性以及数据流的单遍特性，导致很难有效地 在海量的流数据中提取有用数据，并对其进行进一步操作。传统数据挖掘 算法在支持数据流挖掘时所表现出来的局限性已被广泛认识，这也促进了 对改进现有数掘挖掘算法和构建新的数据流挖掘算法的研究。 本文共分为六章。第一章“前言”简单介绍了数据流的基本概念、原 理和处理技术特点等，以及数据挖掘的基本概念、方法和分类等。第二章 “离群数据挖掘概述”是关于离群数据挖掘以及常用离群数据挖掘方法的 介绍。在第三章“数据流聚类分析”中，介绍了主要的数据流聚类方法及 其与数据流离群数据挖掘的紧密联系。第四章“基于分布式反向k 近邻算 法的数据流离群数据挖掘研究”是运用c l u s t r e a m 算法的结构提出一种适 用于数据流离群数据挖掘的算法，并将算法扩展到了分布式环境中进行数 据流数据离群数据的挖掘，最后描述了实验过程和实验结果。第五章“基 于数据流离群数据挖掘技术的农业气象灾害实时预警系统，将前几章的研 究内容应用到了农业气象领域，并设计了一个农业气象灾害实时预警系 统，详细分析了系统的体系结构和系统运行流程。最后一章是对全文工作 的总结以及对今后研究工作的展望。 关键字：数据流；离群数据挖掘；聚类；分布式数据挖掘 i l l r e s e a r c ha n d a p p l i c a t i o no nd a t a - s t r e a mo u t l i e rd a t a m i n i n g a b s t r a c t o u t l i e rd a t as h o u l db et r e a t e ds e r i o u s l y , f r o mw h i c hp e o p l ec a nd i s c o v e r s o m er e a la n du n e x p e c t e dk n o w l e d g e d a t a s t r e a mc o n s i s t so fas e r i e so f o r d i n a lc o m i n g ，b o u n d l e s s ，d y n a m i cd a t a o u t l i e rd a t am i n i n gi nd a t a s t r e a m i san e wt a s ko fd a t am i n i n g ，w h i c hh a sb e e nb r o a d l ya p p l i e di nd a i l yl i f e a t p r e s e n t ，d a t a s t r e a mm i n i n gi sb e c o m i n gah o tt o p i ci nt h ed o m a i n so f d a t a b a s e ，m a c h i n el e a r na n ds t a t i s t i c s ，a n dau s e f u lt o o li nm a n yr e s e a r c h f i e l d s w h e nt h ed a t am o d e 】o fd a t a s t r e a mi sb r o a d l yu s e di ni n d i v i d u a la n d c o m m e r c i a li n f o r m a t i o n ，s o m ee x i s t i n ga p p l i c a t i o ns o f t w a r en e e dt oa n a l y z e a n dd e a lw i t ht h e s ef l e e t l yc h a n g i n gd a t a b u tt h el i m i t a t i o no fe x i s t i n g d a t a - s t r e a ms y s t e ma n dt h eo n e - - p a s sc h a r a c t e ro fd a t a - s t r e a ml e a dt h a ti ti s h a r d l yt om i n eu s e f u li n f o r m a t i o ne f f e c t i v e l y ，a n dt od e a lw i t hi tm o r ef r o m h u g ed a t a s t r e a m t h ed i s a d v a n t a g e so ft r a d i t i o n a ld a t am i n i n ga l g o r i t h m si n m i n i n gd a t a s t r e a m i si n d i c a t e d b ym a n yr e s e a r c h e r s ，m e a n w h i l e ，t h e s e d i s a d v a n t a g e sa l s op r o m o t et h er e s e a r c h e so fi m p r o v i n go fe x i s t i n gd a t a m i n i n ga l g o r i t h m sa n dc r e a t i n gn e wd a t a s t r e a mm i n i n ga l g o r i t h m s t h i st h e s i si sd i v i d e di n t os i xc h a p t e r s t h ef i r s tc h a p t e r f o r e w o r d b r i e f l yi n t r o d u c e st h eb a s i cc o n c e p t i o n s ，t h e o r i e s ，a n ds o m ec h a r a c t e r so f m i n i n gt e c h n o l o g y ，e t e t h es e c o n dc h a p t e r , s u m m a r yo fo u t l i e rd a t am i n i n g ， i sa b o u tt h ep r e s e n t a t i o no fo u t l i e rd a t am i n i n ga n do u t l i e rd a t am i n i n g m e t h o d si nc o m m o nu s e t h et h i r dc h a p t e r , d a t a s t r e a mc l u s t e r i n ga n a l y s i s ， i n d i c a t e sm a i nd a t a - s t r e a mc l u s t e r i n gm e t h o d sa n dt h ec l o s er e l a t i o n s h i p b e t w e e nd a t a - s t r e a mc l u s t e r i n ga n dd a t a s t r e a mo u t l i e rd a t am i n i n g t h e f o u r t h c h a p t e rp r e s e n t s ar e v e r s ekn e a r e s t n e i g h b o r ( r k n n ) b a s e d d i s t r i b u t e dd a t a s t r e a mo u t l i e rd a t am i n i n ga l g o r i t h m t h i st h e s i se x p l o i t st h e f r a m eo f c l u s t r e a m ”a l g o r i t h m d e s i g n sa na l g o r i t h mb a s e d “c l u s t r e a m f o r d a t a s t r e a mo u t l i e rd a t am i n i n g ，a n de x t e n d st h ea l g o r i t h mt od i s t r i b u t e d d a t a s t r e a me n v i r o n m e n t a tl a s to ft h i sc h a p t e re x p e r i m e n t a lp r o c e s sa n d r e s u l t sa r eg i v e n t h ef i f t hc h a p t e rd e s i g n sa na g r i c u l t u r a lw e a t h e rd i s a s t e r s r e a l t i m ef o r e c a s t s y s t e m t h e r e s e a r c h e so ff o r m e r c h a p t e r s a b o u t d a t a s t r e a mo u t l i e rd a t am i n i n ga r eu s e di na g r i c u l t u r a lw e a t h e rf i e l d s ，a n dt o f r a m et h i ss y s t e m t h i sc h a p t e rd e t a i l e d l ya n a l y s e st h es y s t e ms t r u c t u r ea n d s y s t e mf l o w t h el a s tc h a p t e ri sas u m m a r ya b o u t t h i st h e s i sa n dap r o s p e c to f f u t u r es t u d y k e yw o r d ：d a t a s t r e a m ；o u t l i e rd a t am i n i n g ；c l u s t e r i n g ；d i s t r i b u t e dd a t a m i n i n g v 插图清单 图1 1k d d 发现过程8 图2 1 离群数据示意图1 8 图4 ，l 传统的基于数据仓库的数据挖掘框架3 0 图4 2 分御式数据挖掘体系结构3l 图4 3 反向k 近邻查询示例3 2 图4 4r k n n 与离群数据检测3 3 图4 5k n n 有向图3 4 图4 6r k n n 有向图3 4 图4 7 算法性能4 0 图4 8 连续处理的时间窗口个数与离群点的关系4 0 图4 9 分布式离群数据挖掘框架4 1 图5 1 数据处理过程4 6 图5 2 农业气象灾害实时预警系统的结构图4 7 图5 3 农业气象灾害实时预警系统的检索流程4 8 i x 独创性声明 本人卢明所呈交的学位论文是本人在导师指导下进行的研究i ：作及取得的研究成果。据 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得盒壁：! ：些厶堂 或其他教育机构的学位或证书而使用过的 材料。与我一同- 亡作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名： 王爿跫 签字日期：0 7 年脚且 学位论文版权使用授权书 本学位论文作者完全了解盒壁 ：、业盔堂有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权全理 工些厶堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 王超 签字日期：刃年2 - j j ，日一 学位论文作者毕业后去向： 1 ：作单位： 通讯地址： i i 导师签名：怛叫 签字日期：。7 年f v 月，日 电话： 邮编： 致谢 值此论文完成之际，我谨向所有关心、支持我的老师、同学、朋友和 家人致以最真挚的感谢。 我的导师倪志伟教授是一位治学严谨、知识渊博的老师。倪老师认真 的工作态度、严谨的治学精神一直以来都是智能管理所的老师和学生们工 作和学习中的榜样。论文从选题、实验到写作及最后的成稿付梓，灌注了 倪老师和智能管理所的所有老师、师兄、师姐、师弟、师妹的指导、帮助、 关心和支持，衷心感谢大家。感谢倪老师对我的指导和教诲，您刀：阔的思 维、敏锐的洞察力以及详细的修改意见一直给我很大的启发。 感谢黄玲师姐、伍章俊师兄、倪丽萍师姐、张威师兄、蔡博闻师兄、 忻凌师兄、陶亮师兄以及智能管理所的所有师弟师妹们在我学习、生活和 写作论文期间给与的帮助和支持。 感谢睡在我左右的兄弟：马晓伟，钱永珂，王高成。谢谢你们在学习 和生活上的帮助和支持。祝愿你们前程似锦，飞黄腾达，能够实现自己的 梦想。 感谢安徽省电力科学研究院的所有同事们在我近一年的实习期问给 与的帮助和关心。 感谢我的家人在我二十年的求学生涯中给与我的无私的关怀和支持， 我的每一个成功都有你们无私奉献的烙印。你们勤劳、淳朴、宽厚的性格 从小就教会了我要踏实做人、认真做事。既使用人间最华丽的词藻也不足 以形容我的感恩之情。 在母校良好的学习氛围和生活环境中，我度过了生命中最美好、最愉 悦的七年时光，祝愿母校在以后的日子罩取得更好的成绩，蒸蒸同上! 致谢是论文的最后一部分内容，同时也是我这一段生活的一个句号。 句号是结束的标志，也是一段新生活即将开始的启示。在对美好的新生活 展望之际，我要对智能管理所的同届的兄弟姐妹们送上我的真挚祝福。 祝愿：朱小虎、罗琴、虞娟、束建华、段蕾，生活万事如意，事业一 帆风顺。 v l 作者：王超 2 0 0 7 年1 2 月l 同 1 1 数据流概述 第一章前言 计算机网络技术与通信技术等信息技术的迅速发展与广泛应用，使得 各种数据j 下以一种惊人的速度堆积，这种现象为数据挖掘带来了新的发展 机遇，同时也提出了新的挑战。这一挑战就是设计出一种新的算法，使其 可以以增量方式处理各种数据及追踪其变化，而不需要对计算机内存和其 它处理资源产生新的要求，以做出更好的决策并挖掘出更有价值的知识。 随着计算机、通信、网络技术的迅猛发展，许多应用领域出现了海量、高 速、动态的数据，如交通工程和网络监控i l 2 1 、电信记录管理和分析【3 j 、 商业交易管理和分析【钔、金融信息监控15 1 、供应链工程和工业过程控制【6 1 、 传感器网络监控1 7 1 等，区别于传统数据库中相对静态的数据，这类海量、 持续、有序、快速和突变的数据，称之为数据流【6 ，8 】。如何对这种全新的 数据模型进行管理与分析，是一个严峻挑战。 1 1 1 数据流研究现状 目i j 数据流管理与挖掘的研究主要从以下三方面进行：理论方面 的研究，包括随机算法( r a n d o m i z e da l g o r i t h m s ) ，研究重点是算法的界 的讨论【8 ，1 1 1 。即在一定的误差范围内，合理设计近似算法、寻优算法， 实现内存消耗与查询速度的最佳平衡【l2 1 。联机算法的设计，即各种 流水线联接算法的实现，主要考虑在实际数据集合上的效率问题降，9 】。 数据流模型的研究。据不同的时序范围可以划分成多种子模型，如界标模 型( 1 a n d m a r km o d e l ) 1 15 】、滑动窗口模型( s l i d i n gw i n d o wm o d e l ) 1 7 , 1 3 1 和快照 模型( s n a p s h o t m o d e l ) 。其中，滑动窗口模型应用最为普遍，它关心当前 滑动窗口内最新的数据，随着数据的不断到达，窗口中的数据也不断平 移。不同的模型特点不同，故在不同的要求下采取合适的模型。数据流 是动念变化的，问题的重点是挖掘模型的及时修正【1 0 , 1 4 , 1 6 】。 1 1 2 数据流模型 数据流由一系列按序到达的数据组成，也可看作是信息传输过程中经 编码处理的数字信号串3 1 。令t 表示任一时间戳，口，表示在该时问戳到达 的数据，数据流可以表示成 ，q + q ，q 。) ，对应描述了一个隐函数 a ：【1 ，n 】斗r 2 。 根掘口对函数a 描述的不同，数据流模型可分为三类1 6 】：时间序列、 c a s hr e g i s t e r 、t u r n s t i l e 。 时问序列数据流，用来描述时间序列数据。如每分钟纳斯达克 ( n a s d a q ) 成交量、每五分钟所观测到的i p 流量。此时： a l = u 】， ( 1 ) 其中，i 对应着递增的时刻。 c a s hr e g i s t e r 数据流，是一类应用普遍的模型，类似收银机记录。 如对i p 地址的监控，同一i p 资源可对一地分时传送或向多个地址传送。 此时： 口f = ( ，i ) ，f o ，4 【刀= 4 一l 2 1 + 6 ( 2 ) t u r n s t i l e 数据流是由拥挤的地铁站中记录乘客出入的十字转门的启 发而得的。可有效研究动态的删除与插入操作，但很难得到有意义的界。 此时： q2 ( ，v i ) ，o ，4 u 】_ 4 一j j l + v i ( 3 ) 其中u ，可视作删除与插入符，数值可正可负。 上述三种流模型，前两种具有很好的实际意义，特别是时序数据流， 而t u r n s t i l e 模型具有较好的理论价值。 1 1 3 数据流处理技术及其特点 数据流与传统的数据库系统中存储的大小一定的、有限的和持久保存 的数据集不同，它具有以下特征： ( 1 ) 数据量十分的庞大，可能是潜在无限的； ( 2 ) 记录以非常快的速度到达，并且是在线到达的； ( 3 ) 无论是在一个数据流之内还是在多个数据流之间，系统都不能控 制流中数据元素到达和被处理的顺序； ( 4 ) 数据流中的元素一旦已被处理过，就被丢弃或者把它存档，不能 够再次检索该元素。除非该元素被显式地保存在内存中，但相对于数据 流的大小来说，被保存的元素数量一般是非常小的。 对这些数据进行处理的目的是挖掘其中潜在的模式和趋势、处理查询 或实时的计算数据流中的统计信息。数据流的上述这些特征导致数据流处 理也与传统的数据处理方法有很大的不同。数据流处理算法因此有如下特 点： ( 1 ) 不可能对快速的海量的数据流进行随机访问，只能按数据到达的 次序顺序访问，且对数据只能遍历一次，对每条记录最多检查一次，所 以需要对数据扫描多遍的算法是不可行的。 2 ( 2 ) 不管同前到达的记录总数有多少，算法存放汇总信息的内存空| 日j 是一定的、有限的。 ( 3 ) 数据流处理必须具有实时性，每条记录的处理时问必须很小，否 则跟不上数据流入的速度，算法可能来不及处理后续数据。 ( 4 ) 从数据流中得到精确的回答通常要付出很高的代价，因为很难用 有限的空间来精确计算海量的流数据，所以数据流挖掘算法得到的一般 是近似的答案，但近似的回答也是可以令人接受的【l “。 现在有些大的公司每天都会产生数以百万计的记录，比如，天中， w a l m a r t 会有2 千万条销售记录，g o o g l e 会处理7 千万次搜寻，a t & t 会 记录2 亿7 千5 百万条电话记录。此外，科学数据的采集( 如通过地球传 感卫星或宇航观测系统等) 一般每天会产生上g 字节的记录。上述这些数 据的容量非常庞大，无法把它们存放在内存罩，只能保存在二级以上存储 器中。这样获取特别是随机获取这些数据要花费很高的代价。因此，为了 便于管理，把这些数据建模成实时的数据流而不是建模成持久的关系表。 对于在线实时挖掘这种海量数据，要求算法必须是单遍的( 或者扫描的次 数很少) ，并且也可以接受近似值。 1 2 数据挖掘的研究背景 随着信息技术的发展，数据量急剧膨胀，数据的时效性和复杂性远远 超过了当前的数据处理能力。在信息化和全球化的推动下，近些年来，人 们产生和采集数据的能力大幅度地提高，从而使得数据获取和生产能力大 大超过数据处理的能力。目前，由于数据生产、传输能力与数据分析能力 的不平衡，人们已被淹没在数据的海洋中，寻找隐藏在其中的有价值的信 息无异于大海捞针。人们希望能够开发具有强大数据分析功能的数据挖掘 系统，并能够自动的、智能的在待处理的数据中挖掘出有价值的信息和知 识。数据挖掘和知识发现( 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 2 1 数据挖掘定义 ( 1 ) 技术角度的定义 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模 糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜 在有用的信息和知识的过程【17 , 1 8 1 。从上面的定义可以得出数据挖掘的三 个特点：首先，数据挖掘的数据量是巨大的，如何高效率的存储数据，设 计高效率的处理算法，都是数据挖掘要面对的难题；其次，数掘挖掘面临 的数据常常是不完全的、不确定的或模糊的，需要对这些数据进行预处理 以得到合适的挖掘数掘。未知性和不完全性将始终贯穿数据挖掘的全过 程；最后，判断一个新颖的算法是否有效的重要标准就是发现的知识必须 是可理解的和可运用的。 数据挖掘是知识发现过程的一个步骤，是知识发现中通过特定的算法 在可接受的计算效率限制内生成特定模式的一个步骤。知识发现是一个非 常广义的范畴，它包括：数据清洗，数据集成，数据选择，数据转换，数 据挖掘，模式生成和评估等一系列步骤。即知识发现是由一系列基本功能 构成的系统化协同工作系统，数据挖掘是这个系统中的关键部分。 ( 2 ) 商业角度的定义 数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库 中的大量业务数据进行抽取、转换、分析和其他模型化处理，挖掘出一些 概念、规则、模式和规律等一些关键性的数据，从而辅助决策者制定更加 合理的商业决策。 事实上，数据、信息和知识是数据在不同阶段的不同表现形式。由于 计算机网络技术的飞速发展，人们收集数据的范围和容量也在不断的扩 大。最终的结果导致了“数据丰富而信息贫乏( d a t ar i c h & i n f o r m a t i o n p o o r ) ”现象的产生。广义上说，信息和知识是指对人们有帮助的数据， 面对日益膨胀的数据如何才能找出这些有用的信息和知识，因此数据挖掘 作为一类深层次的数据分析方法应运而生。随着一个企业或行业业务数据 库的不断积累，通过一个人或某几个人从过去的销售情况预测将来的发展 趋势或做出正确的决策的时代已过去，面对大量复杂的数据，任何高智商 的人也无法进行深层次分析。因此，在纯机会的商业运作的需求下，数据 挖掘就是指通过各种数据分析技术对大量数据进行深层次的复杂数据分 析，获得有利于商业运作，提高竞争力的信息和知识，为商业决策提供真 正有价值的信息，进而获得利润。 1 2 2 数据挖掘的分类与方法 数据挖掘涉及的学科领域与方法很多，有多种不同的分类方法。从不 同角度看，数据挖掘技术有如下几种分类方法：根据挖掘对象的种类进行 分类、根据发现知识的种类进行分类和根据挖掘方法进行分类。 ( 1 ) 根据挖掘对象的种类进行分类，对于不同类型的数据对象要采用 不同的数据挖掘技术相对应。因此数据挖掘可以按照数据库系统的类型和 所处理的数据类型来划分，包括：空问数据库挖掘、时态数据库挖掘、异 4 质数据库挖掘、文本数据源挖掘、多媒体数据库挖掘、面向对象数据库挖 掘和关系型数据库挖掘等。 ( 2 ) 根掘数据挖掘所能发现的知识的种类进行分类，数据挖掘主要分 为以下几类7 1 ： 1 ) 挖掘广义型知识( g e n e r a l i z a t i o n ) ：挖掘描述类别特征的概括性知 识，根据数据的微观特性发现的带有普遍性、较高层次概念的宏观知识。 2 ) 挖掘类知识( c l a s s ) ：类知识主要包括：分类( c l a s s i f i c a t i o n ) 知 识，反映同类数据问共同性的知识和不同类数据间差异性的知识。聚类 ( c l u s t e r i n g ) 知识，指根据事物的属性对未分类的数据进行类别识别的 过程。 3 ) 挖掘关联型知识( a s s o c i a t i o n ) ：找出隐藏在数据库中反映不同事 物问的关联关系的知识。 4 ) 挖掘序贯模式( s e q u e n t i a lp a t t e r n s ) ：指在多个数据序列中发现数 据共同的行为模式。 5 ) 挖掘预测型知识( p r e d i c t i o n ) ：通过时间序列数据，由历史数据和 当前数据预测未来数据的趋势情况。 6 ) 挖掘偏差型知识( d e v i a t i o n ) ：通过分析数据，找出数据中所蕴含 的明显区别于其他数据的数据，例如聚类外的离群点，序列异常等，揭示 事物发生偏差的异常规律。 所有这些知识都可以在不同的概念层次上被发现，随着概念树的提 升，从微观到宏观，以满足不同用户、不同层次决策的需要。 ( 3 ) 根据采用的挖掘方法进行分类，最常采用的数据挖掘技术可分为 1 7 , 1 8 】： 1 ) 机器学习方法：机器学习方法的核心问题是从特殊的训练样本中归 纳出通用函数。机器学习方法可用于分类、聚类和预测等应用。机器学习 可细分为：归纳学习方法、基于范例学习、遗传算法等。 2 ) 统计方法：统计学方法可用于对数据的建模。统计方法可细分为： 回归分析、判别分析、聚类分析、探索性分析等。其中回归分析方法是用 一组独立变量和常量来估计一个因变量，主要有线性回归模型、非线性回 归模型和非线性多重回归模型。统计方法可用于分类、聚类和预测等应用。 3 ) 神经网络方法：它从结构上模仿生物的神经网络，是一种通过训练 数据集来学习的非线性预测模型。神经网络方法可以用于分类、聚类、特 征挖掘等多种应用。神经网络方法可细分为：反向神经网络、自组织神经 网络等。 4 ) 粗糙集方法：粗糙集理论是一种研究模糊、不完整、不确定知识和 数据的表达、学习、归纳的理论方法，主要用于分类挖掘，数据约简等。 5 ) 近似推理和不确定型推理方法：知识库是人工智能的核心，而知识 库中的知识既有规律性的一般原理，又有大量的不完全的专家知识，即知 识带有模糊性、随机性、不完全性、不可靠或不确定因素。世界上几乎没 有什么事情是完全确定的。不确定性推理即是通过某种推理得到问题的精 确判断。不确定推理方法在人工智能系统中通常是不够严谨的，但尚能解 决某些实际问题，符合人类专家的直觉，在概率上也可给出某种解释。 所有这些分类方法都从不同角度刻画了数据挖掘研究的策略与范畴， 它们是互相交叉和互相补充的。 1 2 3 数据挖掘的应用 数据挖掘以一种全新的概念改变着人类利用数据的方式。由于大型数 据系统的广泛使用和把大量数据转换成有价值的知识的迫切需要，数据挖 掘得到了前所未有的重视和广泛的应用。数据挖掘技术从一开始就是面向 应用的。目前，在很多领域，数据挖掘都是一个新兴的概念，尤其是在如 银行、电信、保险、交通、零售( 如超级市场) 等商业领域。 数据挖掘的目的是：提高市场决策能力；检测异常模式；在过去的经 验基础上预言未来趋势等。它不仅能用于控制成本，更重要的是能给企业 带来效益。以下是数据挖掘技术应用的几个例子： ( 1 ) 客户关系管理( c r m ) 。客户关系管理已成为目前企业管理决策 的重要部分，而数据挖掘技术为客户关系管理的实施提供了良好的支持。 很多企业都在利用数据挖掘技术帮助管理客户生命周期的各个阶段，包括 争取新的客户、在已有客户的身上赚更多的钱和留住有价值的客户。如果 能够确定有价值的客户的特点( 如性别、年龄、职业等) ，那么就能为客 户提供针对性的服务。找到流失的客户的特征就可以在那些具有相似特征 的客户还未流失之前采取针对性的弥补措施，因为留住一个客户要比争取 一个客户容易的多，代价也更小。 ( 2 ) 检测会融欺诈。银行是数据挖掘的重要领域，银行和信用卡公司 是用数据挖掘技术来检测欺诈行为的先行者。金融欺诈以信用卡欺诈、账 户欺诈和贷款欺诈为主要途径。欺诈检测( f r a u dd e t e c t i o n ) 已经成为一个 专门的研究和防范领域。以下数据挖掘方法常被用来建立模型来鉴别欺诈 交易和分析欺诈交易具有哪些特征：孤立点分析、主成分分析、聚类分析、 判别分析、关联分析、决策树分析、神经网络等。 ( 3 ) 在医疗领域中，数据挖掘技术可以用来预测外科手术、医疗试验 和药物治疗的效果。制药公司通过挖掘化学物质和基因对疾病影响的数据 库来判断哪些物质可能对治疗某种疾病产生效果。 6 ( 4 ) 超级市场的零售商更多的使用数据挖掘技术来解决每种商品在不 同地点的库存：了解消费者的消费模式，分析客户的忠诚度：进行销售、 信息、客户、产品、时间和区域的多维分析；利用数据挖掘技术对商业促 销行为进行分析，从而更灵活的使用各种促销和优惠手段，推荐相关产品。 ( 5 ) 在电信领域中数据挖掘技术的贡献有：设计和建立数据仓库，并 进行多维电信数据分析与数据挖掘；客户的信用分析；欺准模式分析与非 正常模式的确定与辨别；目标市场客户的聚类与分类分析；以及关联规则 及序列模式的分析等。 由于数据挖掘技术的良好的应用| j i 景，各大软件公司及大学研究机构 对此展开了深入的研究。许多数据挖掘系统被开发出来，其中比较有代表 性的有： ( 1 ) s a s 公司的s a se n t e r p r i s e m i n e r ，它包括回归、分类、统计分析， 其特点是有较强的统计分析功能。 ( 2 ) i b m 公司的i n t e l l i g e n t m i n e r ，它提供了较全面的数据挖掘算法， 良好的算法伸缩性，并为高级用户提供了a p i 接口，可以在不同的操作 系统上运行。 ( 3 ) a t t a rs o f t w a r e ，i n c 公司的x p o r t r u l em i n e r ，它提供了知识抽取 功能，顾客终端和服务器之间的远程通信协调办法，可以优化数据系统， 可以进行分类、聚类、预测、时间序列分析等。 其它产品还有t a n d e m 的r e l a t i o n a ld a t am i n e r ，a n g o s ss o f t w a r e 的 k n o w l e d g es e e d e r 等等。除了这些综合软件包外，还有许多专门用途的产 品。另外，也成立了许多专业于数掘挖掘的咨询公司。 1 2 4 知识发现的基本步骤 知识发现k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 的定义：k d d 是 从数据中辨别有效的、新颖的、潜在有用的、最终可理解的模式的过程【”1 。 k d d 是一种决策支持过程，它主要基于人工智能、机器学习、模式 识别、统计学等技术，高度自动化地分析大量的数据，从中挖掘出潜在的 规律，从而做出正确的决策。k d d 的过程可以简单的概括为：首先从数 据系统中选择目标数据对象，并按照数据挖掘所需要的格式组织数据；然 后利用数据挖掘技术，寻找有用的知识与信息；最后对生成的知识模式进 行评估，并利用正确的有价值的知识和信息辅助决策。 知识发现过程主要包括以下步骤【l8 】： ( 1 ) 问题定义：数据挖掘者要熟悉领域背景知识，清楚用户要求，确 定挖掘的目标； 7 ( 2 ) 数据抽取：选取相应的源数据，并根据具体的挖掘目标和任务抽 取相应的数据； ( 3 ) 数据预处理：对抽取的数掘进行再加工，包括数据清洗、数掘变 换，数据归约等功能： ( 4 ) 数据挖掘：k d d 的核心步骤，通过建立挖掘模型，实施相应的挖 掘算法来找出所需的知识模式； ( 5 ) 模式评估：根据某种兴趣度度量，识别表示知识的真j 下有价值的模式； ( 6 ) 知识表示：使用可视化和知识表示技术，向用户提供简洁的易于 理解的有价值的知识和信息。 幽1 1k d d 发现过程 数据挖掘是在大量数据源中，自动并智能的发现有价值的、先前未知 的知识和信息的过程，是知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ， k d d ) 过程中关键的一个步骤。如图1 1 所示，是k d d 将原始数据转化 为有用信息的整个过程【l 。 知识发现，是从数据中发现有效的、潜在的、有用的、可理解的结构。 数据指的是数据库中的数据，结构指的是模型。数据挖掘是k d d 的核心 步骤，为了使挖掘在人们可以接受的计算效率的极限内列出有意义的数据 模型，为了获得可用知识，要给出一些模型的选择标准。 ( 1 ) 有效性：通过更好的挖掘技术和预测方法，使人们得到有价值的 信息，并能够辅助决策获得更大效益。 ( 2 ) 确定性：确定性的数量表示可以通过准确率等表示。 ( 3 ) 可理解性：可以定义为简单化的模式，用户容易理解的模式。 ( 4 ) 兴趣度：新奇性的量化表示，兴趣度可以在挖掘静进行定义，通 过挖掘后对结果进行验证，如果结果不能令人满意，可以采用新的挖掘 方法重新挖掘或重新定义兴趣度。 由此可见，k d d 过程是一个以知识使用者为中心、人机交互的探索 过程。数据挖掘只是数据库中知识发现的个步骤，但又是最重要的一步。 8 1 3 数据流离群数据挖掘 信息技术的飞速发展，尤其是计算机网络和传感器网络的发展和广泛 应用，使得股票交易、天气预报、网络监控等一系列领域出现了海量的实 时快速到达数据一一数据流，如何在这种类型的数据中发现离群数据，将 是本文研究的核心问题。一般来说，数据流数据的挖掘大部分研究主要集 中在数据流聚类和数据流相关性、依赖关系的发现上，而对于数据流离群 数据挖掘的研究则相对较少。 1 3 1 数据流离群数据挖掘的研究背景 在数据流研究中，数据摘要或模型表示、趋势检测、异常检测是关键 技术。基于目f i 仃数据流挖掘的现状，以下方面的研究已经得到了广泛的关 注： ( 1 ) 数据流离群数据研究：研究针对数据流的高效异常挖掘算法，寻 找数据序列中在某一时自j 段里与其它数据很不相似或很不一致的数据， 找出其中的规律和蕴含的知识； ( 2 ) 数据流相似性研究：寻找新的适于数据流的数据结构和建模方法， 并针对数据流的高维时态混合属性的特点，提出有效度量数据相似性的 方法； ( 3 ) 数据流概念转移研究：研究数据流基于时间变化的特性，探索数 据流变化的表示与建模方法，挖掘数据进化和变化的趋势，研究数据流 的局部周期挖掘算法； ( 4 ) 数据流聚类分析：研究基于约束的数据流聚类分析，对实时的、 持续的、有序的流数据进行聚类操作。 本文就是研究针对数据流的高效异常挖掘算法。 数据流离群数据是指实时到达的数据序列中，在某一时间段里与其它 数据很不相似或很不一致的数据，它可能是由于人为错误或机器错误造成 的噪声数据，但也可能是事物本质的体现。对于噪声数据，我们要进行清 除，以免影响数据挖掘的结果。而对于蕴涵有真实知识的离群数据，如果 我们找出它们并进行分析，往往能得到意想不到的知识。 数据流就是大量连续到达的、潜在无限的数据有序序列，这些数据只 能按照顺序存取并读取一次。因此如何在这种数据形式上进行知识发现成 为了数据挖掘的一个新的难题。数据流离群数据挖掘是数据挖掘的一个新 的热点。由于数据流这种特殊的数据形式，完整的或者部分的存储历史数 9 据都是不现实的，因此过去的一些基于静态数掘集的离群数据挖掘算法都 变得不再适用，需要设计一种动态增量式的数据挖掘算法，在有限的内存 中快速的对数掘进行处理，但是这种算法往往需要以挖掘精度为代价柬换 取效率上的平衡。 离群数据挖掘已经在会融、网络安全、电信、零售、医疗卫生、天文 物理等行业和领域得到了应用，并且效果较好。但大部分都是基于静态数 据集，而且发展出了基于距离的方法、基于偏离的方法、基于规则的方法、 基于聚类的方法等众多的离群数据挖掘方法。而在数据流上进行的离群数 据挖掘研究尚不成熟，目前成功的应用还很少。 1 3 2 数据流数据挖掘的重要方法 与传统的静态数据不同，数据流数据具有数据量几乎无穷，且随着时 间动态增加等特点。这些都要求在数据流离群数据挖掘中，关键是解决两 个核心问题一是如何在有限的内存空间中处理连续的，大量的随着时间不 断增长的数据流数据，因此必须提高算法的处理效率，改进算法的复杂度。 二是由于数据量是“无限”的，因此不可能将所有的数据都存储起来，然 后再对数据进行多次扫描。这就要求算法能够只扫描数据一次或有限的几 次就能够发现离群数据。为了解决以上两个问题，必须在算法的精确性和 高效性上做出平衡。 数据流海量动态，而内存大小固定，故研究核心是设计高效的单遍扫 描算法( o n ep a s sa l g o r i t h m ) ，建立一种概要数据结构( s y n o p s e s d i g e s t s s t r u c t u r e ) 1 2 0 1 。典型方法有如下几种【l6 1 ： ( 1 ) 抽样方法( s a m p l i n g ) 【2 l ”】，即抽取数据集中小部分数据代表整 个数据集，包括精确抽样( c o n c i s es a m p l i n g ) 2 1 】、水库抽样( r e s e r v o i r s a m p l i n g ) 2 1 l 、总体抽样( u n i v e r s es a m p l i n g ) 、域抽样( d o m a i ns a m p l i n g ) 【2 3 】 等。以上方法可实现对c a s hr e g i s t e r 流数据的分位数计算、频繁项挖掘、 显著项个数的计算和聚类分析等，但无法兼顾一定的算法下界和复杂度。 随着流的延伸，若算法中所保存的样本丢失，则需重新取样，这在数据流 中是不可行的。 ( 2 ) 基于散列的技术( s k e t c h ) l lj ，即沿着某一维投影以实现维数约减 的方法，能够解决流上的很多问题，估计数据集的二阶矩大小、估计数据 集自连接的大小、获得数据集中热门元素的列表等。该方法主要适应于 t u r n s t i l e 模型1 2 4 ，且可以应用在直方图计算和数据流的图论算法中。 ( 3 ) 指数直方图( e x p o n e n t i a lh i s t o g r a m ，简称e h ) 方法 2 2 , 2 3 】，利用 分箱技术来近似数据分布，可直观、简洁地描述大数据集轮廓。分等宽直 t 0 方图( e q u i w i d t hh i s t o g r a m ) 、压缩直方图( c o m p r e s s e dh i s t o g r a m ) 、v - 优化 直方图( v - o p t i m a lh i s t o g r a m ) 等。 ( 4 ) 群测试方法1 2 4 1 ：比如在t u r n s t i l e 数据流中找出b 一频繁项、在 t u r n s t i l e 数据流判定最高b 阶h a a r 小波系数。 ( 5 ) 树模型【2 4 】：适合于时问序列模型，一般采用基于数据流的典型平 衡树。它的应用包括：在时序数据流中判定最高b 阶h a a r 小波系数、在 时序数据流中建立直方图、发现偏离点、构建一个基于数据流的分解树。 上述方法常与二进制搜索、贪婪算法、动态程序设计、分而制之策略 等结合使用。 1 4 本文组织及内容安排 本文主要的研究工作是数据流离群数据的挖掘方法与应用。在实际研 究中，我们发现流数据与传统的静态数据有很大的不同。主要表现在流数 据是实时到达，数据到达次序独立且不受应用系统控制，数据规模宏大且 不能预知其最大值。数据一经处理，除非特意保存，否则不能被再次取出 处理，或者再次提取数据代价昂贵【25 1 。这样就使得传统的离群数据挖掘 算法不再具有直接应用的可能，因此传统的离群数据挖掘方法不能很好的 适用于数据流数据。本文针对这一问题提出了一种基于c l u s t r e a m 算法框 架结构的m c l u s t r e a m 算法来解决数据流离群数据挖掘问题。 本文的第一部分先是介绍了数据流与数据挖掘的基本概念、方法以及 分类等。接着概述了离群数据挖掘的意义，数据流离群数据挖掘是近来数 据挖掘的新热