（计算机应用技术专业论文）基于相关性的数据流聚类及其应用研究.pdf

基于相关性的数据流聚类及其应用研究 摘要 上世纪末，为适应网络监控、入侵检测、情报分析、商业交易管理和分析 等应用的要求，数据流技术应运而生。数据流是以连续的、有序的“流”的形 式输入数据，有时效性、实时性、无限性和瞬时性等特点。典型的数据流有网 络点击流、实时监控数据流、股票数据流、超市的销售数据流等。对数据流的 分析主要包括分类、聚类和频繁模式挖掘三个方面，其中都用到了一些新的技 术和方法，如滑动窗口、一次性扫描算法等。本文在介绍数据流及数据流挖掘 关键算法的基础上，针对超市的销售数据流进行分析，提出了一种度量商品之 间相关性的算法，进而提出了一种基于相关性的数据流聚类算法，对商品进行 聚类分析。 本文的研究主要集中在以下几个方面： ( 1 ) 概述了数据挖掘及数据流的概念、数据流挖掘的关键技术及典型算法， 重点分析了数据流分类算法v f d t 和c v f d t 、数据流聚类算法s t r e a m 和 c l u s t r e a m 、数据流频繁模式挖掘算法f p s t r e a m 等。 ( 2 ) 针对超市中商品之间的相关性问题，提出一种基于数据流的相关性度 量算法，以计算出商品间相关性的大小，利用数据流的一些方法，在有限的时 间和空间里动态计算出基于持续到来的销售数据流的商品之间的相关性。实验 显示，该算法能以较小的代价有效地度量超市中商品之间的相关性。 ( 3 ) 针对超市中商品之间的聚类问题，提出一种基于相关性的数据流聚类 算法，在前面计算出的商品之间相关性的基础上对商品进行聚类。该算法是一 个动态更新的算法，实验显示，该算法能有效地对超市的商品进行聚类，得到 了非常有价值的聚类结果。 关键词：数据流数据流挖掘相关性聚类 4 r e s e a r c ho nd a t as t r e a mc l u s t e r i n ga n di t s a p p l i c a t i o n sb a s e do nc o r r e l a t i o n s a b s t r a c t s i n c et h ee n do fl a s tc e n t u r y , d a t as t r e a mt e c h n i q u e sh a v eb e e na d v a n c e dt om e e t t h er e q u i r e m e n t so fn e t w o r km o n i t o r i n g ，i n b r e a kd e t e c t i n g ，i n f o r m a t i o na n a l y z i n g ， b u s i n e s st r a n s a c t i o nm a n a g e m e n ta n da n a l y z i n g ，e t c i n p u td a t ao ft h es t r e a m i n g d a t ai s “s t r e a m i n g ”o fc o n t i n u a la n do r d e r l y , d a t as t r e a m sh a v ec h a r a c t e ro f e f f e c t i v e n e s sf o rt i m e ，r e a lt i m e ，i m m e n s i t ya n di n s t a n t a n e o u s ，e t c r e p r e s e n t a t i v e e x a m p l e sa r en e t w o r kc l i c kf l o w , m o n i t o r i n gd a t as t r e a m s ，s t o c kd a t as t r e a m sa n d s e l l i n gd a t as t r e a m so fs u p e r m a r k e t s ，e t c a n a l y s e st o d a t as t r e a m si n c l u d e c l a s s i f i c a t i o n ，c l u s t e r i n g a n df r e q u e n t p a t t e r nm i n i n g t h e r e f o r e ，s o m en e w t e c h n o l o g i e sa n dm e t h o d sa r eu s e d t oa n a l y s ed a t as t r e a m s ，s u c ha s s l i d i n g w i n d o w s ，o n e - p a s sa l g o r i t h m sa n ds oo n b a s e do ni n t r o d u c t i o nt od a t as t r e a m sa n d k e ya l g o r i t h m s o fd a t as t r e a mm i n i n g ，a n a l g o r i t h mo fc o r r e l a t i o n sb e t w e e n c o m m o d i t i e si sp r o p o s e d ，a n dt h e nad a t as t r e a mc l u s t e r i n ga l g o r i t h mb a s e do n c o r r e l a t i o n si sp r o p o s e dt oc l u s t e rc o m m o d i t i e s t h er e s e a r c hc o n t e n t so ft h i sd i s s e r t a t i o na r eb e l o w ： ( 1 ) i n t r o d u c t i o nt od a t am i n i n g ，d a t as t r e a m sa n dk e yt e c h n o l o g ya n da l g o r i t h m s o fd a t as t r e a mm i n i n g ，i n c l u d i n gd a t as t r e a mc l a s s i f i c a t i o na l g o r i t h m sv f d ta n d c v f d t c l u s t e r i n ga l g o r i t h m ss t r e a ma n dc l u s t r e a ma n df r e q u e n tp a t t e r nm i n i n g a l g o r i t h m sf p s t r e a m ，e t c ( 2 ) a na l g o r i t h mo fc o r r e l a t i o n sb a s e do nd a t as t r e a m si sp r o p o s e dt op r o c e s s c o r r e l a t i o n sb e t w e e nc o m m o d i t i e si ns u p e r m a r k e t s t h ca l g o r i t h mc a nc a l c u l a t et h e c o r r e l a t i o n sb e t w e e nc o m m o d i t i e sq u a n t i t a t i v e l y i tc a nd ot h i si nl i m i t e dt i m ea n d m e m o r ya n dp r o c e s st h ee n d l e s sd a t as t r e a m sb a s e do nt h em e t h o d so fd a t as t r e a m s t h ee x p e r i m e n ts h o w st h a tt h ea l g o r i t h mc a nm e a s u r ec o r r e l a t i o n sb e t w e e n c o m m o d i t i e si ns u p e r m a r k e t se f f e c t i v e l yb a s e do ns m a l lc o s t ( 3 ) ad a t as t r e a mc l u s t e r i n ga l g o r i t h mb a s e do nc o r r e l a t i o n si sp r o p o s e dt o p r o c e s st h ep r o b l e mo fc l u s t e r i n gc o m m o d i t i e si ns u p e r m a r k e t s i tc a nc l u s t e rc o m m o d i t i e sb a s e do nt h e i rc o r r e l a t i o n sw h i c hh a v eb e e nc a l c u l a t e d t h ea l g o r i t h m i s d y n a m i c t h ee x p e r i m e n ts h o w st h a tt h ea l g o r i t h mc a nc l u s t e rc o m m o d i t i e s e f f e c t i v e l y , a n dm o s tv a l u a b l er e s u l t sa r ea c q u i r e di nt h ee x p e r i m e n t k e y w o r d s ：d a t as t r e a m ；d a t as t r e a mm i n i n g ；c o r r e l a t i o n ；c l u s t e r i n g 5 插图清单 图1 1数据挖掘的实施过程2 图2 1s t r e a m 算法聚类过程示意图1 2 图2 2 金字塔时间窗口中存储的快照序列图1 3 图2 3使用a p r i o r i 算法产生频繁项集的例子示意图1 7 图2 4基于非平衡时间窗口的频繁模式1 8 图2 5t 3 时刻的频繁模式及f p t r e e 。1 8 图2 6 嵌入非均衡时间窗口表的f p t r e e 1 8 图4 1熵值变化曲线3 4 图4 2聚类增量更新算法3 6 图4 3聚类结果树状图3 8 9 表格清单 表2 1典型传统聚类算法的比较1 0 表2 2购物篮事务例子1 6 表3 1 不同的属性类型2 1 表3 2简单属性的相似度和相异度2 2 表3 3两个对象x i ，x i 的属性匹配表2 4 表3 4商品之间的相似度3 0 l o 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得 金罡王些友堂 或其他教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示谢意 学位敝储躲始段签字帆母钿7 目 学位论文版权使用授权书 本学位论文作者完全了解 金世王些太堂 有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权 金魍王些盍堂 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影 印、缩印和扫描等复制手段保存、汇编学位论文 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：- = 多乏参增 祥嗍：印“月7 日 学位论文作者毕业后去向： 黧鬟佩始南 通讯地址： 3 导师签名： 签字日期 电话；葫。b 弧 脯：苎? t 川 | 日 致谢 本文是在导师胡学钢教授的悉心指导下完成的，在此谨表示最诚挚的敬意 和最衷心的感谢! 胡院长充沛的精力、豪爽的性格、卓越的学识、严谨的治学 态度和诲人不倦的工作作风，给我留下了深刻的印象，特别是胡院长高尚的师 者风范更是深深地影响着我，将让我终生受益 同时，真诚感谢计算机与信息学院的全体老师，他们的教诲为本文的研究 提供了理论基础，并给我创造了许多必要条件和学习机会。 感谢铜陵学院计算机系的文太宝书记、钟志水主任、李武主任和全体老师 对我的支持和帮助，他们为我来工大学习创造了条件并给予了足够的关怀。 在论文撰写过程中，胡为成老师、王刚老师和程转流老师与我共同讨论了 很多问题，并提出了许多中肯的建议，对我的帮助很大，在此表示感谢。 感谢我的母亲和岳母辛勤的劳动和对我时时刻刻的关心，在她们的支持和 理解下，我才能完成学业。 特别感谢我的夫人王明芳女士，不论是在平时的工作还是在工大的学习期 间，她始终心甘情愿地照顾着家和孩子，奉献着她的全部精力与热情，没有她 的付出就没有我的成功，在此说声：你辛苦了! 最后还要感谢我的小宝宝史天秀，她的到来为我的家庭增添了无限的欢乐， 也给予了我无穷的动力，祝愿她健康、快乐地成长。 6 作者：史金成 2 0 0 7 年5 月 第一章绪论 本章主要从数据挖掘、数据流、数据流挖掘和数据流挖掘在超市中的应用 等几个方面介绍本文的研究背景和国内外的研究现状，接着阐述本文的主要研 究内容，最后介绍本文的内容组织结构。 1 1 问题提出 当今社会，零售业特别是超市零售业的发展非常迅速，现在的超市尤其是 大型超市都开始了信息化建设。伴随着超市信息化建设和应用进程的加快，大 量的信息技术如条码、电子收款机和p o s 系统在各大超市已是随处可见，便产生 了大量的销售数据。于是，人们便利用数据挖掘技术对这些数据进行分析，得 出哪些商品好卖、哪些客户适宜哪些商品、商品之间如何搭配、如何进行打折 促销等有趣而又非常有意义的结论，最典型的例子就是“啤酒和尿布”这一则 津津乐道的故事。但是，我们发现，对一些大型超市来说，由于数据量太大、 而且数据产生的速度太快，如果仍然按传统的数据库应用模式来处理这些数据， 则要付出非常巨大的时间和空间代价，会导致这样的任务无法完成。近些年来， 开始出现数据流及数据流挖掘技术。数据流挖掘技术将数据看成是动态的流的 形式，对它们进行处理时，采用采样、分而治之、一趟扫描、滑动窗口等技术， 这大大节省了时间和空间。因此，研究如何利用数据流及数据流挖掘技术对超 市的销售数据进行挖掘，通过对超市中商品之间的相关性的分析，进而对商品 进行聚类，从而进行商品的分组，商品打折促销等决策，有着很大的现实意义 和经济意义。 1 2 研究背景 1 2 1 数据挖掘 数据挖掘( d a t am i n i n g ) 是从9 0 年代初兴起的一门新的数据库技术。所谓 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据 中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的 过程卜i 随着信息技术的高速发展，人们积累的数据量急剧增长，动辄以t b 计。 如何从海量的数据中提取有用的知识成为当务之急。数据挖掘就是为顺应这种 需要应运而生发展起来的数据处理技术，是知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e s ) 的关键步骤。 与数据挖掘相近的同义词有数据融合、数据分析和决策支持等。这个定义 包括好几层含义：数据源必须是真实的、大量的、含噪声的；发现的是用户感 兴趣的知识；发现的知识一定要可接受、可理解、可运用；并不要求发现放之 四海皆准的知识，仅仅支持特定的发现问题。 何为知识? 从广义上理解，数据、信息也是知识的表现形式，但是人们更 把概念、规则、模式、规律和约束等看作知识。人们把数据看作是形成知识的 源泉，好像从矿石中采矿或淘金一样。原始数据可以是结构化的，如关系数据 库中的数据；也可以是半结构化的，如文本、图形和图像数据；甚至是分布在 网络上的异构型数据发现知识的方法可以是数学的，也可以是非数学的：可 以是演绎的，也可以是归纳的。发现的知识可以被用于信息管理、查询优化、 决策支持和过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门 交叉学科，它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘 知识，提供决策支持。在这种需求牵引下，汇聚了不同领域的研究者，尤其是 数据库技术、人工智能技术、数理统计、可视化技术、并行计算等方面的学者 和工程技术人员，投身到数据挖掘这一新兴的研究领域，形成新的技术热点。 这里所说的知识发现，不是要求发现放之四海而皆准的真理，也不是要去 发现崭新的自然科学定理和纯数学公式，更不是什么机器定理证明。实际上， 所有发现的知识都是相对的，是有特定前提和约束条件，面向特定领域的，同 时还要能够易于被用户理解，最好能用自然语言表达所发现的结果。数据挖掘 技术是人们长期对数据库技术进行研究和开发的结果。起初各种商业数据是存 储在计算机的数据库中的，然后发展到可对数据库进行查询和访问，进而发展 到对数据库的即时遍历。数据挖掘使数据库技术进入了一个更高级的阶段，它 不仅能对过去的数据进行查询和遍历，并且能够找出过去数据之间的潜在联系， 从而促进信息的传递。现在数据挖掘技术在商业应用中已经可以马上投入使用， 因为对这种技术进行支持的三种基础技术已经发展成熟，它们是：海量数据搜 集、强大的多处理器计算机和数据挖掘算法。 ( 1 ) 数据挖掘过程 数据挖掘过程如图1 1 所示弘l ，它一般由3 个主要阶段组成：数据准备、挖掘 图1 i 数据挖掘的实施过程 2 数据准备阶段包括数据选择和样本数据预处理。首先根据数据挖掘方法 和工具的要求选择合适的数据( 样本、训练集、测试集等) ，并对选择的数据进 行预处理( 离散化、连续化、编码等) 。 挖掘操作包括规则发现和规则分析及建模。首先将确定的数据挖掘算法 在预处理后的数据中执行，得到相应的结果( 规则) ，再对结果进行辨证分析并 将其用于预测、预报等建模工作中。 结果的表述和解释阶段是将建模的结果以用户容易理解的、能够接受的 形式一信息可视化技术展现给用户，为其提供满意的决策支持。 ( 2 ) 数据挖掘方法分类 从数据挖掘的目标来看，数据挖掘的方法可以分成以下几类： 特征( c h a r a c t e r i z a t i o n ) 。从与学习任务相关的一组数据中提取出关于这些 数据的特征式，这些特征式表达了该数据集的总体特征。 区分( d i s c r i m i n 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 ) 。将数据划分或分割成相交或不相交的群组或簇的过程。 除了类别没有预先定义而由数据决定之外，聚类与分类很相似。聚类一般是指 无指导学习。通过确定数据之间在预先指定的属性上的相似性可以完成聚类任 务。 关联规则( a s s o c i a t i o nr u l e ) 。也称作关联分析，是指揭示数据之间相互关 系，而这种关系在数据中没有直接表示。 1 2 2 数据流简介 近年来，随着硬件技术的高速发展，人们获取数据的能力得到了很大的提 高。经常会出现这样的情况：大量需要处理的数据以很快的速度产生。例如， 一个网站一天的点击次数可以达到几千万次，电话公司的大型交换机每天可以 记录高达几千万条的通话记录。由于数据量太大、而且数据产生的速度太快， 如果仍然按传统的数据库应用模式来处理这些数据，则这样的任务将是不可能 完成的。于是，一种新型的解决方案应运而生，其最大特点是，待处理的数据 以一种动态、流式的形式出现( h p 数据流，d a t as t r e a m ) ，对数据流中的数据只能 按顺序进行一次或有限次的访问。如今，数据流尤其是数据流挖掘已成为新一 代计算理论与应用的研究热点之一。 数据流就是大量连续到达的、潜在无限的数据的有序序列1 , 4 1 。我们日常生 活中有很多数据流的例子，如超市的商品销售数据、股票交易所的股票价格信 息，环境温度的监测数据，电信部门的通话记录，网站的点击记录以及传感器 3 网络中的监测数据等。和传统数据库中相对静态的数据不同，数据流有时效性、 实时性、无限性和瞬时性等特点p ，o j 。人们在处理传统数据时，可以完整、详细 地收集数据，且将它们全部存储在数据库中，然后再由计算机来处理，传统的 商务和事务型数据库管理系统强调维护数据的完整性和一致性，追求的目标是 系统吞吐量和平均响应时间，而不是系统的自适应性和查询服务质量，更加不 注重数据处理的时空限制。由于数据流的特殊性。短时间内有大量数据连续到 达，这些数据具有随时间动态变化的趋势，要求快速即时响应，且这些数据往 往又是高维的，所以在处理数据流时，必须注重时空限制，对数据流中的数据 通常采取的是单一扫描的线性算法，用精度换时间，尽量在对数据的一次访问 中获得较优的解和有用的信息。一些数据库应用中常用的操作，如排序、找最 大值或最小值、计数等b l o c k i n g 操作在数据流的处理中都是行不通的，且一般 的数据流算法是不可回溯的。 要想对数据流进行处理，首先必须建立相应的数据流模型j 。数据流d 可 以看作是由不断到达的数据组成的动态增长数据集，即d = a b a 2 ，a i ，a j ， ， 其中a i 为数据，如果j i ，则a i 先于a j 到达；如果u i l = l ，则a i 与a j 相邻。 根据a i 的描述的不同，数据流模型可以分为以下3 类： ( 1 ) 时间序列数据流。用来描述时间序列数据，如每分钟n a s d a q 成交量、 每2 分钟所观测到的i p 流量。这里的a i 可以定义为： a i = ( j ，i i ) ， 其中，i i 为i 时刻产生的数据。 ( 2 ) c a s hr e g i s t e r 数据流。这种模型应用非常普遍，如超市的收银机记录、 对i p 地址的监控记录。这里的a i 可以定义为： a i = ( j ，i i ) ， 其中，1 2 0 ，为新产生的数据，很显然有：a i d = a i i u + i i a ( 3 ) t u r n s t i l e 数据流。这种模型可以记录动态的插入和删除操作，如记录拥 挤的地铁站中乘客的人数。这里的a i 可以定义为： a i = ( j ，u i ) ， 其中，u i 可以大于0 ，也可以小于0 。很显然有， a i d 】- a i 1 【j 】+ u i 。 1 2 3 数据流挖掘 对于静止的数据，数据挖掘过程可以分成两个部分：先把数据收集起来存 储在数据库中，然后在数据库上应用各种挖掘技术进行挖掘。而对于数据流， 它的收集过程和挖掘过程是同时进行的，我们必须以最快的速度，从不断到来 的数据中挖掘出感兴趣的模式( i n t e r e s t i n gp a t t e r n ) ，来响应用户的实时查询。 基于数据库的传统数据挖掘都要求数据分析处理的精确性，但是对于流数 据，由于数据收集时间的有限性，分析处理速度的有限性，我们无法在精确度 上做过多要求，使得挖掘结果的近似性( a p p r o x i m a t i o n ) 成了不同于传统数据挖掘 4 的一个特点。 数据流挖掘的特点决定了它比传统的数据挖掘要复杂，因此一般我们在数 据流挖掘中要解决以下一些主要问题： ( 1 ) 设计低内存消耗的挖掘算法。由于数据流中的数据是连续产生的，需 要的内存很大，所以只能实时地处理数据流，因此在设计挖掘算法时必须充分 利用有限的内存，使得一次能处理更多的数据； ( 2 ) 设计计算高效的挖掘算法。在数据流挖掘过程中，内存中储存的数据 始终都是最新产生的数据，必须在这些数据还没被后来的数据替代前，完成对 它们的处理。这就要求在设计算法时必须考虑算法的效率，如何在最短的时间 内完成对数据的处理； ( 3 ) 设计一趟挖掘算法。因为数据流是连续不停地产生的，我们也没有任 何可以暂时阻塞数据流的操作，所以对所有的数据都只能扫描一趟，必须设计 一趟挖掘算法。 目前，数据流挖掘的成果主要集中在数据流的聚类、分类及频繁模式挖掘 上，已经出现了一些典型的数据流挖掘算法。 1 2 4 超市销售数据流挖掘 现代超市特别是大型超市的零售商品种类极其丰富，消费者需要处理的信 息量急剧增加。消费者平均要以每秒几十件的速度从几万件商品中挑选出几件 商品。研究表明，当消费者面对种类繁多的商品时，并不会因为可选择的丰富 多样性而得到满足。但是，消费者却能够因为超市对其商品选择的引导丽感到 满意。超市引导顾客的一个有效办法就是合理的商品布货。就是说，哪些商品 可以摆放在一起，而哪些商品又应当分别摆放。问题是，超市进行布货的依据 是什么? 另一方面，我们可以观察到商场和超市经常进行各种促销，其中最常 见的促销方式是打折，而且，常常是全场打折。这样的打折往往不是超市最优 的选择。因为，消费者在购买某些商品的时候，会同时购买另一些商品，而不 管它们是否打折。在这种情况下，只要这两种商品之一处于打折状态，而另一 种也极有可能受到刺激而销售量大增。如果是这样，超市只需要对一种商品打 折就可以达到促销两种商品的目的，从而可以大大提高超市的效益。那超市安 排商品打折的依据又是什么? 因此，了解消费者究竟如何在多商品类目间进行 同时购买( s i m u l t a n e o u sp u r c h a s e ) 对于超市如何有效地引导消费者和提高效益 意义重大。 针对上述问题，我们可以利用数据流挖掘技术对超市商品销售数据流进行 动态挖掘，研究商品之间的相关性，对超市的商品布货和打折促销提供决策建 议，从而提高超市的销售收入和利润。 i 3 国内外研究现状 1 3 1 数据挖掘 数据挖掘是一个新兴的领域，从9 0 年代初开始兴起，在短短几年内得到了 迅速的发展。在国际上，k d d 会议已经成为具有相当影响力的会议，它代表了 k d d 领域的最高水平从1 9 9 5 起，每年至少举办一次，有时举办两次，每一届 会议上都有许多高水平的论文发表，提出一些新的数据挖掘方法。重要的会议 还有v l d b 、s i g m o d 、i c d e 、c i k m 、p a k d d 等，重要的杂志有a c m 的t k d e 。 国外已有许多专门的工作组，从事数据挖掘领域的研究。比较著名的有 r a g r a w a l 领导下的i b m a l m a d e n 实验室，还有j h a n 带领下的工作组。他们提 出了许多好的数据挖掘算法，为该领域的发展奠定了一定的基础。在国内，目 前也有许多科研人员从事数据挖掘方面的研究，如上海复旦大学的施伯乐、周 傲英，清华大学的陆玉昌，中国科技大学的蔡庆生等等。国内比较重要的会议 有“全国数据库学术会议”，重要的杂志有计算机学报、软件学报等。此外，近年 来出现了许多数据挖掘系统，如q u e s t 、d b m i n e r 、k d w 、e x p l o r a 、s k i c a t 、 i m a c s 等，还有许多包含在数据仓库中的数据挖掘系统。一直以来，人们致力 于提出高效、高质量、低内存的数据挖掘算法。已提出的数据挖掘算法涵盖了 很多知识类型，比如关联规则、聚类、分类等。 1 3 2 数据流 数据流在最近几年成为研究的热点。在国外，已形成了很多数据流研究小 组，在开发多个研究项目和原型系统的过程中。涉及到了数据流的管理、查询、 挖掘等各方面的内容。例如s t a n f o r d 大学开发的s t r e a m ( 一个通用的数据流 管理系统) 、b r o w n 与m i t 合作开发的a u r o r a ( 用于监测的数据流处理系统) 、 o g i 与w i s c o n s i n 合作开发的n i g a r “用于提取、查询、监测x m l 数据) 、b e r k e l e y 大学开发的t e l e g r a p h ( 自适应的数据流系统) 、c o r n e l l 开发的c o u g a r 、a t t 开发的h a n c o c k 、g e o r g i at e c h 开发的o p e n c q 、x e r o x 开发的t a p e s t r y 、b e l l c o r e 开发的t r i b e c a 等等。另外，在数据库领域的国际会议上出现了一些与数据流相 关的论文，i c d e 0 2 举办了一个数据流讨论组( p a n e l ) 。在s i g m o d p o d s 0 2 会议上有关于数据流的指南、讨论组、论文单元，r a j e e vm o t w a n i 还做了重要发 言。除此之外，数据流会议已经举办了多次，会上探讨了数据流领域中的各方 面问题。在国内，目前还没有大规模研究数据流问题的研究小组。已有的数据 流处理技术包括抽样，直方图，小波、滑动窗口和统计技术等，这些技术可以 用于数据流挖掘。 6 1 3 3 数据流挖掘 目前，大多数与数据流相关的研究项目主要集中在数据流管理及查询处理方 面，而在数据流挖掘方面的研究项且还不多见，j h a n 领导下的小组正在做这方 面的工作。但是，在数据流挖掘算法方面已经有一些研究成果出现，如数据流 分类【8 , 9 1 、数据流聚类1 1 0 1 引、数据流频繁模式挖掘【1 3 1 7 】等等。在国内，也在这 方面开始了一些探索，如复旦的周傲英等人在数据流分析方面已取得一定的成 果，近几年的全国数据库学术会议上也有一些数据流挖掘方面的论文。然而， 在数据流挖掘领域还有很多有趣的问题值得探索。比如，适于数据流的数据结 构和建模方法；有效度量数据流中数据相关性的方法；针对数据流的高效异常 挖掘算法；数据流基于时间变化的特性；数据流变化的表示与建模方法；数据 流中数据进化和变化的趋势；数据流基于约束的聚类分析算法；数据流的局部 周期挖掘算法等。 1 3 4 数据挖掘在超市中的应用 国外对消费者同时购买行为最深入的数量研究，应该属于m a n c h a n d a 、 a n s a r i 和g u p t a 等人。他们提出了一个基于随机效用函数( r a n d o mu t i l i t y t h e o r y ) 的多种类同时购买决策( m u l t i c a t e g o r yp u r c h a s ei n c i d e n c ed e c i s i o n ) 模型 l j s l 。该模型通过贝叶斯多维p r o b i t 模型( b a y e s i a nm u l t i v a r i a t ep r o b i tm o d e l ) ， 精细地刻画了各个消费者的同时购买行为特征，并同时考虑到了消费者异质性 ( h e t e r o g e n e i t y ) 的影响。 由于此类模型充分地考虑了消费者的异质性，因此有可能被用来为面向消 费者的个性化的营销决策( c u s t o m i z e dm a r k e t i n gd e c i s i o n ) 服务。但是，该模 型的优点也恰恰是他的缺点。首先，对消费者异质性的精细刻画使得该模型所 需要的计算量非常巨大。该计算量主要来源于贝叶斯方法所需要的m c m c ( m a r k o vc h a i nm o n t ec a r l o ) 算法。例如，m a n c h a n d a 、a n s a r i 和g u p t a 的原始 文章只考虑了4 种产品种类，这显然远远不能够满足现实的需要，也就是说， 此类方法不适用于高维的数据流。其次，此类模型通常需要能够对一给定消费 者的重复购买行为予以准确跟踪。换句话说，研究者必须能够从数据辨认同一 消费者在不同时间的购买纪录。这通常意味着该超市必须有完善的会员制度， 以及详细准确的会员信息。这对很多超市，特别是大量的本土新兴连锁超市来 说，是一个巨大的，短时期内难以克服的困难。 1 4 本文的研究内容和结构 本文的研究内容主要有：首先，深入细致地研究数据流挖掘技术和算法， 然后提出一种计算超市商品相关性的算法，定量地计算出商品的相关性，接着 提出一种基于数据流的动态增量更新聚类算法，根据前面计算出的商品的相关 性对商品进行聚类，并用实验进行验证。 7 本文主要分为以下几个部分： 第一章绪论，主要介绍了本文的研究背景和国内外的研究现状。 第二章数据流挖掘算法，主要介绍常用的数据流挖掘算法，为后面的相 关性分析和聚类分析提供基本的算法支持。 第三章数据流的相关性分析与计算，提出一种基于数据流的计算超市商 品相关性的算法，对超市的商品进行相关性度量，并用实验对该算法有效性和 优越性进行验证。 第四章数据流的聚类，提出一种基于高维数据流的动态增量更新聚类算 法，根据前面计算出的商品的相关度对商品进行聚类，并将该算法应用实际中， 然后对聚类结果进行分析。 第五章总结与展望，总结本文所做的研究工作，并对后续工作进行展望。 1 5 本章小结 数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数 据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识 的过程，而数据流是大量连续到达的、潜在无限的数据的有序序列。本章主要 介绍了本文的研究背景、国内外的研究现状和主要研究内容，同时介绍了本文 的内容组织结构。 8 第二章数据流挖掘算法 本章主要介绍一些典型的基于数据流的聚类、分类和频繁模式挖掘算法 数据挖掘受下面三个方面的限制：时间、内存和样本的大小。特别是在数据流 的挖掘算法中，要在准确性和存储空间上有一个合适的折中，也就是说，得到的是 近似而不是准确的结果。采样、滑动窗口和分而治之等是数据流挖掘中常用的 技术和方法。目前，已经出现许多针对数据流的挖掘算法，这些算法大多集中 在对数据流进行聚类分析、分类和挖掘数据流的频繁模式上，例如，c a g g a r w a l 等人提出了一种数据流聚类算法c l u s t r e a mh u l t e n 等人提出一种用c v f d t 在 变化的数据流上建造决策树的算法，这种算法能有效地对数据流进行分类； g i a n n e l l a 等人设计了一个叫做基于时问窗口模型的流数据关联挖掘算法 f p s t r e a m 。 2 1 聚类( c l u s t e r i n g ) 算法 2 1 1 概述 聚类分析引也称无监督学习，其任务是将数据划分成有意义或有用的组 ( 簇) 。从空间x 中给定一个有限的取样点集( 或从数据库中取得有限例子的集 合) ，聚类的目标是将数据聚集成类，使得类间的相似性尽量小，而类内的相似 性尽量大。 聚类分析的结果主要是经验性的，使用不同的聚类分析法可以有极不相同 的结果，对所做出的结果重复性也差，特别是从统计理论上难以判断某个分类 结果是否正确。 目前，聚类分析己经成为数据挖掘和知识发现领域中的主要课题之一。在 商务上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并且用 购买模式来刻画不同的客户群特征。在生物学上，聚类能用于推导植物和动物 的分类，对基因进行分类，获得对种群中固有结构的认识。聚类在地球观测数 据库中相似地区的确定，汽车保险单持有者的分组，及根据房子的类型、价值 和地理位置对一个城市中房屋的分组上也可以发挥作用。聚类也能用于对w e b 上的文档进行分类，以发现信息。作为一个数据挖掘的功能，聚类分析能作为 一个独立的工具来获得数据分布的情况，观察每个簇的特点，集中对特定的某 些簇做进一步的分析。此外，聚类分析可以作为其他算法( 如特征和分类等) 的预处理步骤，用这些算法在生成的簇上进行再处理。 聚类算法可以分成划分方法( p a r t i t i o n i n gm e t h o d ) 、基于层次的方法 ( h i e r a r c h i c a lm e t h o d ) 和基于密度的方法( d e n s i t y b a s e dm e t h o d ) 等几类，算法的选 择取决于数据的类型、聚类的目的和应用。然而数据流的聚类算法不同于传统 数据的聚类算法，必须是增量式的，对聚类的表示要简洁，对新数据的处理要 快速，对噪音和异常数据必须是稳健的。因此，基于数据流的聚类算法要在一 9 个相对较小的内存空间上，对数据流进行一遍扫描后，把数据集合分为一个个 簇集。 2 1 2 传统的聚类算法 许多聚类算法都是为特定的领域设计的，都有各自的特点和应用范围，因 而任何聚类算法都不可能在每个方面上都优越于其它算法传统的聚类算法主 要分为基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法 及基于模型的方法。这些算法的性能比较分析如表2 1 1 9 l 所示。 表2 1典型传统聚类算法的比较 类 聚类可伸聚类 输入敏 噪声 数据 别 典型算法算法基本思想 感性 处理 质量缩性形状 能力 类型 基 k 平均暇k 个中值作为类表示一般差球状是差数值 于 c l a r a n s 选择一小部分作为数据的样本用队m 选择中 一般好球状是好数值 心点 划 k 平均扩展，新的平均值基于加权的度量值 分 e m一般 好球扶是差数值 计算 b i r c h 用树结构对象进行层次划分，采用其他算法 好好球状不是好数值 基 对聚类结果求精 于甩固定数目的代表对象来表示簇，依据定义 c u r e 好好任意不是好数值 层 的分数向类心对它们进行收缩 次 r o c k 基于簇间的互联性进行合并 好 好任意不是 好 分类 c h a m c l c o n芷层次聚类中发现动态模型铰好好任意不是好数值 将高密度的区域划分簇，定义簇为密度相连 基 d b s c a n好好任意不是好数值 的点的级大集合 于 密 0 p t l c s 没有显示产生一个簇，而为自动和交互计算 好好任意不是好数值 一个簇次序，包含一个宽广的参数设置范围 度 d e n c l u e基于一组密度分布函数的聚类 较好一般任意 不是 好数值 将区域划分为不同级别的分辨宰的矩形单 s t i n 元，根据单元格中的预先计算的统计信息生一般好任意不是好数值 基 成类 于 网 c l i q u e 网格与密度的结合，用 p r i o r i 生成多维稠密 一般 好任意不是好数值 单元 格 在数据空间上加多维网络结构，采用小波变 w a v e c l u s t e r 一般好任意不是好数值 换原空同，在变换后的空间中找密集区域 基 简单增t 概念聚类算法，以一个分类树的形 c o b w e b好差特定不是好分类 于 式创建层次聚类 模 c l a s s t t对c o b w e b 的扩展，处理数据好差特定不是好 数值 型 a u t o c l a s s采用贝叶斯统计分析来估算结果簇的数据好差特定不是好数值 l o 2 1 3 数据流聚类算法 g u h a 在2 0 0 0 年提出针对数据流聚类的l o c a l s e a r c h 算法。该算法的基 本思想是基于分治的思想，也就是使用一个不断的迭代过程实现在有限空间内 对数据流进行k m e a n s 聚类。随后，o c a l l a g h a n 发展了l o c a l s e a r c h 算法的 思想。他于2 0 0 2 年提出了s t r e a m 算法，并利用s s q 证明了在多种情况下，s t r e a m 算法的聚类效果都比b r i c h 算法要好。但l o c a l s e a r c h 和s t r e a m 方法都有一个缺点，即只能提供对当前数据流的一种描述，而不能反映流数据的 变化情况。于是，2 0 0 3 年，b a r b a r d 总结了数据流聚类算法的要求，并对一些可能 适用于数据流的聚类算法做了一次总结。他认为在数据流中聚类需要满足3 个 要求：( 1 ) 压缩的表达；( 2 ) 快速、增长地处理新的数据点；( 3 ) 快速、清晰地判断 异常点。a g g a r w a l 在2 0 0 3 年提出了c l u s t r e a m 算法，这是一个解决数据流聚类 问题的框架。它使用了两个过程来处理数据流聚类问胚：首先，使用一个在线 的m i c r o - c l u s t e r 过程对数据流进行初级聚类，并按一定的时间跨度将 m i c r o c l u s t e r 的结果按一种称为p y r a m i dt i m ef r a m e ( 金字塔时间窗口) 的结构储 存下来。同时，使用另一个离线的m a c r o c l u s t e r 过程，根据用户的具体要求对 m i c r o c l u s