（系统工程专业论文）面向混合属性的数据与数据流聚类算法研究.pdf

浙江工业大学硕士学位论文 面向混合属性的数据与数据流聚类算法研究 摘要 数据挖掘是数据库研究、开发和应用中最活跃的分支之一。近年来出现了一 种称为数据流挖掘的新应用，这种应用中的数据是以流的形式产生的，如传感器 数据、网页点击流、实时监控系统等。这些数据流的特点是按时间顺序的、快速 变化的、海量的和潜在无限的。由于数据流具有上述特点，需要开发单遍扫描的， 联机的，多层的，多维的数据流挖掘方法。 学术界已经对数据流聚类问题进行了不少的有价值的研究工作，但是还存在 许多问题尚待解决。本文研究了基于密度的数据流聚类问题，主要做了以下几个 方面的改进： l 、改进了密度聚类算法。d b s c a n 算法是一种基于密度的聚类算法，针对 该算法在处理混合属性数据上的不足，采用面向维度的距离的思想，改进了混合 属性数据的相似度度量方法，提出了一种新的适合混合属性数据聚类的算法 m d b s c a n 。仿真表明新算法有效解决了d b s c a n 算法无法处理混合属性数据 的缺点。 2 、设计了一种数据流情况下的混合属性密度聚类算法。为了克服数据流聚 类框架c l u s t r c a m 算法不能处理混合属性数据流的缺陷，提出了基于密度的混合 属性数据流聚类算法m c s t r c a m 。本文在微聚类中使用面向维度的距离来度量对 象之间的相似度，在宏聚类中是使用改进的密度聚类算法m 。d b s a 气n 来对微簇 进行聚类。实验结果表明，m c s t r c a m 算法能快速有效地处理混合属性数据流聚 类问题。 关键词：数据挖掘，数据流，聚类，密度 浙江工业大学硕士学位论文 r e s e a r c h0 nd a t aa n dd a t as t r e a mc l u s t e r i n g a l g o r i t h m sf o rm i x e da t t r i b u t e s a b s t r a c t d a t am i n i n gi so n eo ft h em o s ta c t i v ep a r t si nd a t a b a s er e s e a r c hn o w i nr e c e n t y e a r st h e r eh a sb e e nan e wd a t am i n i n ga p p l i c a t i o nk n o w n a st h ed a t as t r e a mm i n i n g ， s u c ha p p l i c a t i o nd e a lw i t ht h ed a t aw h i c hg e n e r a t e di nt h ef o r mo fs t r e a m i n gd a t a , s u c ha ss e n s o rd a t a , t h ew e b s i t ec l i c ks t r e a m ，r e a l - t i m em o n i t o r i n gs y s t e m s t h ed a t a s t r e a mi sc h a r a c t e r i z e db yc h r o n o l o g i c a lo r d e r , r a p i d l yc h a n g i n g ，a n dt h em a s so f u n l i m i t e dp o t e n t i a l a st h ed a t as t r e a mw i t ht h e s ec h a r a c t e r i s t i c s ，an e wd a t am i n i n g m e t h o d sn e e dt ob ed e v e l o p e dw h i c hi ss i n g l e - p a s ss c a n n i n g ，o n - l i n e ，m u l t i - l a y e r e d a n dm u l t i - d l i m e n s i o n a l a g r e a tm a n ym e t h o d so ns t r e a mc l u s t e r i n gh a v eb e e np r o p o s e d , h o w e v e rt h e r e a r es t i l lm a n yp r o b l e m sn e e dt ob er e s e a r c h e da n dr e s o l v e d i nt h i sp a p e r , w es t u d y t h ep r o b l e mo fd a t as t r e a mc l u s t e r i n g ，t h i sa r t i c l em a d et h ef o l l o w i n gi m p r o v e m e n t s ： 1 i m p r o v et h ed e n s i t yc l u s t e r i n gf o rn o r m a ld a t a d b s c a ni s ac o m m o n d e n s i t yb a s e dc l u s t e ra l g o r i t h m ，i no r d e rt oa v o i d i t ss h o r t c o m i n gw h i c hc a n tb eu s e d i nm i x e dn u m e r i c a la n dc a t e g o r i c a la t t r i b u t ed a t a , an e wm i x e d a t t r i b u t ec l u s t e r a l g o r i t h mn a m e dm - d b s c a nw a sp r e s e n t e dw h i c hu s et h ed i m e n s i o n - o r i e n t e d d i s t a n c et om e a s u r et h ed i f f e r e n c eb e t w e e nt w od a t ao b j e c t s t h es i m u l a t i o n s i l l u s t r a t et h a tt h ef l e wa l g o r i t h mc a ns o l v et h em i x e d - a t t r i b u t ed a t ac l u s t e rp r o b l e m e f f i c i e n t l y 2 d e s i g nad e n s i t yb a s e dd a t as t r e a mc l u s t e r i n ga l g o r i t h mf o rm i x e d - a t t r i b u t e d a t as e t s c l u s t r e a ma l g o r i t h mi sn o tc a p a b l ee n o u g ht oh a n d l em i x e dn u m e r i c a la n d c a t e g o r i c a ld a t a , i no r d e rt oa v o i dt h i ss h o r t c o m i n g ，an e wd a t as l r e a mc l u s t e r a l g o r i t h mn a m e dm c s t r e a mw a sp r e s e n t e dw h i c h u s et h ei d e ao fd i m e n s i o n - o r i e n t e d t i 浙江工业大学硕士学位论文 d i s t a n c e t h es i m u l a t i o n ss h o wt h a tt h en e wa l g o r i t h mc 卸c l u s t e rt h em i x e d a t t r i b u t e d a t as t r e a me f f i c i e n t l ya n dq u i c k l y k e yw o r d s ：d a t am i n i n g ，d a t as t r e a m s ，c l u s t e r i n g ，d e n s i t y - 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行 研究工作所取得的研究成果。除文中已经加以标注引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的研究成果，也不含为获得浙江 工业大学或其它教育机构的学位证书而使用过的材料。对本文的研究作出 重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本声明的 法律责任。 作者签名：渠乎珐五 日期珈涉年2 月2 汐日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权浙江工业大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密仞。 ( 请在以上相应方框内打“妒) 作者签名： 导师签名： 曼泛啦 日期咖形年- - i z 月矽e 1 日期沙谚年月7 e t 浙江工业大学硕士学位论文 1 1 数据挖掘的意义 第1 章绪论 半个世纪以来，计算机与信息技术的高度发展，人类已经由工业化社会进入 了信息化社会。随着计算机的普及和数据采集技术的进步，人们获取了大量的数 据，而由于廉价大容量存储器出现，网络技术的大范围应用，使数据库的应用规 模、广度和深度都不断扩大，人们保存的数据在以指数方式的速度增长。 有统计表明，早在八十年代，全世界存储在数据库的数据量就在以每二十个 月翻一翻的速度增长【l 】。在九十年代，美国一个中等规模企业每天要就要产生 1 0 0 m b 以上的来自各个方面的商业数据。美国政府部门一个典型大型数据库每 天要接受5 t b 的数据流，存档的数据达到1 5 - 1 0 0 p b 。到2 0 0 6 年为止，专业收 集研究世界各个行业数据的f o r t u n e5 0 0 公司的数据库中，已经拥有了4 1 0 千字节( 约合3 8 1 4 7 0 0 0 g ) 的数据。在科学研究方面，科学机构也保存了大量的 数据。美国国家航天局( n a s a ) 每天要从卫星下载3 - - 4 1 1 3 的数据，为了研究的 需要，这些数据要保存7 年之久。数据量的增长也符合摩尔定律。据统计，全球 拥有的数据量每2 0 个月就可以翻一番。 在这个信息世界里，不同的群体都面临如何有效使用大量数据的问题。“我 们正在被数据所淹没弦，- 信息爆炸一和“数据过剩给了我们巨大的压力。例如， 如何从有关数据中获益? 怎样用历史数据为产生数据的过程建模? 怎样对某一 过程的行为进行预测或预报? 对数据库中的数据作何种解释、如何分类等等。据 估计，目前仅有5 一l o 的商业数据库被加以分析利用t 2 1 。 人类的各项活动都是基于人类的智慧和知识，需要通过观察和了解外部世界 来做出正确的判断，才能做出正确的行动。数据仅仅是进行决策的基础，我们需 要对这些数据进行加工和提炼，寻找到其中的信息。人类贪婪的收集着数据，但 是我们对这些数据的掌握和理解却无法赶上数据获得的速度，导致“数据丰富而 浙江工业大学硕士学位论文 信息缺乏 的现象发生。人们很早就意识到“谁最先从外部世界获得有用信息并 加以利用，谁就可能成为赢家，我们对能够及时有效地在这些海量数据中得到 有用的信息和知识的要求越来越迫切。面对如此巨大的数据资源，人们迫切需要 一种新技术和自动工具，以便能够利用智能技术帮助我们将这巨大数据资源转换 为有用的知识与信息资源，从而可以帮助我们科学地进行各种决策。 1 2 数据挖掘的发展 计算机技术的发展史，也是数据和信息加工技术的发展历程。 早期一般采用人工方法进行统计分析和用批处理程序进行汇总和提出报告， 而后随着应用的深入，把多数据源的不同类型的数据统一的集中到一个机构内， 就形成了数据仓库( d a mw a r e h o u s i n g ) 。在数据仓库的基础上，为了更深入的分 析数据，人们提出了能实时分析和产生相应报表的在线分析工具o l a p ( o nl i n e a n a l y t i c a lp r o c e s s i n g ) ，o l a p 是由用户指导的信息分析和知识发现过程，为了 能发现数据中隐藏的丰富的信息和知识，就需要智能化的自动化工具，来帮助挖 掘隐藏在数据中的各类知识。 新的需求启发了新的技术，九十年代中期以来，在传统的数据库技术、统计 学的方法的基础上，融合了人工智能、机器学习、知识工程、面向对象的方法、 信息检索、高性能计算以及数据可视化等最新成果，提出了一门多学科的交叉研 究领域擞据挖掘。 数据挖掘( d a mm i n i n g ) ，又称数据库中的知识发现( k n o w l e d g ed i s c o v e r y f r o md a t a b a s e ，简称i d ) ，它是一个采用有效算法，从大量的、不完全的、 有噪声的、模糊的、随机的数据中挖掘或抽取隐含在其中、有效的、事先未知的、 新颖的、但又是潜在的有价值的乃至最终可以理解的模式或知识的复杂非平凡过 程。这个定义包括以下四个层次的含义： ( 1 ) 数据源必须是真实的、大量的、含噪声的； ( 2 ) 发现的是用户感兴趣的知识； ( 3 ) 发现的知识是可接受、可理解、可运用的，最好能用自然语言表达发 现结果； ( 4 ) 并不是要求发现放之四海皆准的知识，也不是要去发现崭新的自然科 浙江工业大学硕士学位论文 学定理和纯数学公式，更不是什么机器定理证明，所有发现的知识都是相对的， 是有特定前提和约束条件、面向特定领域的。 人工管理阶段 ( 加世纪5 0 年代) 1 数据不保存 2 人工管理数据 3 数据不共享 4 程序数据不独立 文件系统阶段 ( 2 0 世纪6 0 年代) 1 数据长期保存 2 文件多样化，结构化 3 文件系统管理 4 数据独立性差 数据库管理系统阶段 ( 2 0 世纪7 0 年代8 0 年代) 1 数据整体结构化 2 数据共享性高 3 数据独立性高，冗余度低，易扩充 4d b m s 软件系统 5 关系数据库理论 6 关系数据库标准语言s q l 7 联机事务处理o l t p 先进数据库系统阶段 ( 2 0 世纪8 0 年代中期至今) 1 面向对象的数据库0 0 d b 2 多媒体数据库 3 空间数据 4 时态数据 5 复合数据 分布式数据库与i n t e r n e t ( 2 0 世纪8 0 年代中期至今) l 数据分布存储分布处理 2w e b 数据库应用服务 数据仓库与数据挖掘 ( 2 0 世纪8 0 年代后期至今) l 数据仓库与o l a p 2 数据挖掘与知识发现 图1 1 数据挖掘技术的发展历程 这些规则蕴含了数据库中一组对象之间的特定联系，揭示出一些有用的信 息，为经营决策、市场策划、商业预测、工业控制等提供依据。通过数据挖掘， 有价值的知识、规则或高层次的信息就能从数据库的相关数据集合中抽取出来， 并从不同角度显示，从而使大型数据库作为一个丰富可靠的资源为知识归纳服 3 浙江工业大学硕士学位论文 务。这些知识可能是概念、模式、规则、规律、可视化、线性方程、聚类、树图、 或者特殊的数据等。 数据挖掘最重要的应用就是在商业上，最著名的数据挖掘的例子就是“啤酒 与尿布”的故事。为了分析那些商品顾客最有可能一起购买，零售商公司采用数 据挖掘的方法，对销售数据库中的海量数据进行了分析，发现跟尿布一起购买最 多的商品中竟然包含了啤酒。两件看似毫不相关的商品之间居然会有联系，令人 感到非常不可思议。经过进一步的分析，发现原来太太们常叮嘱丈夫下班后为小 孩买尿布，而丈夫在买尿布后会顺手带回几瓶啤酒。当把尿布和啤酒摆放在一起 时，两种商品的销量都会有大大的增长。 这个例子体现了数据挖掘技术的多个主要特征。首先发现的知识是隐含的， 预先未知的，单这种规律经过分析是非常符合实际的，是有存在的道理的。其次， 这些知识是从大规模的数据库中发现的，一个商业数据中的数据非常庞大，而且 每天都在增加，在海量数据中发现知识最能体现挖掘的含义。再次，发现的规律 是用户感兴趣的，对于一个商场超市来说，如何提高利润，满足客户需求是永远 不变的要求，而数据挖掘得到的啤酒和尿布的关系正好是商场所需要的。最后， 数据挖掘所得到的知识对决策是有价值的，当商场发现啤酒与尿布的关系后就可 以对这两种商品的摆放做出调整，促进两种商品的销售量。 表1 1 数据挖掘的发展 进化阶段商业问题支持技术产品厂家 产品特点 数据搜集。过去五年中我的计算机、磁带和磁 i b m 、c d c 提供历史性的、 6 0 年代总收入是多少? ”盘 静态的数据信息 数据访问。在新英格兰的分关系数据库 o r a c l e 、s y b a s e 、 在记录级提供历 8 0 年代部去年三月的销售( i b m s ) ，结构i n f o r m i x 、i b m 、史性的、动态数 额是多少? ”化查询语言m i c r o s o f t据信息 ( s q l ) ，o d b c 数据仓库“在新英格兰的分联机分析处理 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 年代额是多少? 波士顿数据库、数据仓库 m i c r o s t r a t e g y的数据信息 据此可得出什么结 论? ” 数据挖掘。下个月波士顿的高级算法、多处理p i l o t 、l o c k h e e c l 、 提供预测性的信 正在流行 销售会怎么样? 为器计算机、海量数m m 、s g i 、其他息 什么? ” 据库 初创公司 浙江工业大学硕士学位论文 作为一个新兴的研究领域，数据挖掘得到了研究者的广泛关注【3 ，4 】，形成了 一个包括计算性能【5 】、数据库f 6 】、统计学 7 1 、模式识别【8 】、知识发现【9 】、最优化技 术、粗糙集、并行计算、机器学习、神经网络、数据可视化、信息检索、图像与 信号处理和空间分析等方面的众多学科交叉相融合的学科，是一个有广泛前景的 研究领域。 1 3 国内外研究现状 数据挖掘的概念首次出现在1 9 8 9 年8 月在美国底特律召开的第十一届国际人 工智能联合会议的专题讨论会上，并首次提出了k d d ( 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 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 d d a t a e n g m e e r i n g 会刊率先在1 9 9 3 年出版了k d d 技术专刊。并行计算、计算机网络和 信息工程等其他领域的国际学会、学刊也把数据挖掘和知识发现列为专题和专刊 讨论，甚至到了脍炙人口的程度。到目前为止，由美国人工智能协会主办的k d d 国际研讨会己经召开了9 次，由i e e e 主办的k d d 国际会议召开了5 次，规模由原 来的专题讨论会发展到国际学术大会，研究重点也逐渐从算法研究转向系统应 用，注重多种知识发现策略和应用技术的集成，以及与其他相关学科之间的相互 渗透。 数据挖掘是目前国际上数据库和信息决策领域的最前沿研究方向之一，也引 起了工业界的广泛关注，比较典型的数据库的结构如图1 2 所示。 世界上许多软件公司、数据库公司参与了数据挖掘软件的开发，比较有影响 的典型数据挖掘系统有： 市场份额而言是最大的数据挖掘产品产商s a s 公司推出的数据挖掘产品 s a s e n t e r p r i s em i n e r 。s a se n t e r p r i s em i n e r 是一种通用的数据挖掘工具，按照“抽 样探索转换一建模评估修的方法进行数据挖掘。可以与s a s 数据仓库和 o l a p 集成，实现从提出数据、抓住数据到得到解答的“端到端知识发现。 s p s s 公司主要的数据挖掘产品有a n s w e r t r e e 和c l e m e n t i n e 。a n s w e r t r e e 能创 建图形化决策树( 主要的四种算法是：c h a i d 、e x h a u s t i v ec h a i d 、分类和回归 树( c & i 玎) 以及q u e s t ) ，很容易分析各群体的响应率、发现影响响应率的属性， 浙江工业大学硕士学位论文 找到和确定有价值的客户群体。c l e m e n t i n e 是一个开放式数据挖掘工具，曾两次 获得英国政府s m a r t 创新奖，它不但支持整个数据挖掘流程，从数据获取、转 化、建模、评估到最终部署的全部过程，还支持数据挖掘的行业标准c 砌s p d m 。 使用c l e m e n t i n e 的可视化数据挖掘使得“思路分析成为可能，即将集中精力在 要解决的问题本身，而不是局限于完成一些技术性工作( 比如编写代码) 。提供 了多种图形化技术，有助理解数据与数据之间的关键性联系，指导用户以最便捷 的途径找到问题的最终解决办法。 图1 - 2 典型的数据库挖掘系统 a n g o s s 数据挖掘的核心产品包括：挖掘工作站k n o w l e d g es t u d i o 和挖掘引 擎服务器k n o w l e d g es e r v e r 。k n o w l e d g es t u d i o 包含了全面而先进的数据挖 掘算法，使商业分析师和高级用户在习惯的工作流程环境中都能进行广泛的分 析。k n o w l e d g es t u d i o 支持8 种决策树，3 种神经网络，2 种时间序列，2 种聚类， l o g i s t i c 回归和线性回归，协方差分析算法。 浙江工业大学硕士学位论文 由i b m 公司开发的数据挖掘软件i n t e l l i g e n tm i n e r 是一种分别面向数据库和 文本信息进行数据挖掘的软件系列，它包括i n t e l l i g e n tm i n e rf o rd a t a 和i n t e l l i g e m m i n e rf o rt e x t 。i n t e l l i g e n tm i n e rf o rd a t a 可以挖掘包含在数据库、数据仓库和数 据中心中的隐含信息，帮助用户利用传统数据库或普通文件中的结构化数据进行 数据挖掘。它已经成功应用于市场分析、诈骗行为监测及客户联系管理等； i n t e l l i g e n tm i n e rf o rt e x t 允许企业从文本信息进行数据挖掘，文本数据源可以是 文本文件、w e b 页面、电子邮件、l o t u sn o t e s 数据库等等。 o r a c l e 公司发布的o r a c l e 9 i 包含有基于关联的数据挖掘算法，其最新版本 o r a c l e1 0 9 q b 包括了更多的数据挖掘工具和算法。另! g b o r a c l e 也参与了j a v ad a t a m i n i n ga p i 的开发。 m i c r o s o f t 是第一个在关系型数据库中提供数据挖掘功能的数据库产商。2 0 0 0 年9 月发布的s q ls e r v e r2 0 0 0 包括了两个主要专利数据挖掘算法：m i c r o s o f t 决策 树算法和m i c r o s o f t 聚类算法，另外还应用了一个数据挖掘的业界a p i 标准o l e d bf o rd a t am i n i n g 。s q ls e r v e r2 0 0 5 在数据挖掘方面提供了更为丰富的模型、工 具以及扩展空间，包括可视化的数据挖掘工具与导航、8 种数据挖掘算法集成、 d m x 、) ( j 沮以、第三方算法嵌入支持等等。 除了上述通用的数据挖掘系统外，还有一些特定领域的数据挖掘工具，针对 某个特定领域的问题提供解决方案。在设计算法的时候，充分考虑到数据、需求 的特殊性，并作了优化。例如，m 公司的a d v a n c e d s c o u t 系统针对n b a 的数 据，帮助教练优化战术组合；加州理工学院喷气推进实验室与天文科学家合作开 发的s k i c a t 系统，帮助天文学家发现遥远的类星体；芬兰赫尔辛基大学计算机 科学系开发的t a s a ，帮助预测网络通信中的警报等。 与国外相比，国内对数据挖掘和知识发现的研究稍晚，没有形成整体力量。 1 9 9 3 年国家自然科学基金首次支持我们对该领域的研究项目。目前，国内的许 多科研单位和高等院校竟相开展知识发现的基础理论及其应用研究，这些单位包 括清华大学、中科院计算技术研究所、空军第三研究所、海军装备论证中心等。 其中，北京系统工程研究所对模糊方法在知识发现中的应用进行了较深入的研 究，北京大学也在开展对数据立方体代数的研究，华中理工大学、复旦大学、浙 江大学、中国科技大学、中科院数学研究所、吉林大学等单位开展了对关联规则 浙泛工鼗大学硬士学馒论文 开采算法的优化和改造：南京大学、四川联合大学和上海交通大学等单位探讨、 研究了菲结构化数据的知识发现以及w e b 数据挖掘。 最近，咨询公司g a r t n e rg r o u p 的一次高级技术调查将数据挖掘和人工智能 列为露未来三到五年内将对王业产生深远影响的五大关键技术之首，并且还将 并行处理体系和数据挖掘列为未来五年内投资焦点的十大新兴技术前两位。根据 最近g m 电n e r 的h p c ! 澜研究表明，随着数据捕获、传输和存储技术的快速发展， 大型系统用户将更多地需要采用新技术来挖掘市场以外的价值，采用更为广阔的 并行处理系统来剑建新的商业增长点。撑 重4 数据挖掘的步骤 知识发现( ) d ) 的这个过程包括在指定的数据库中用数据挖掘算法提取 模型，以及围绕数据挖掘所进行的预处理和结果表达等一系列的步骤，数据挖掘 是这个步骤的核心。整个知识发现是由多个步骤组成，如图1 3 所示，其主要的 步骤有： 数据集成( d a mi n t e g r a t i o n ) ，将多个文件或多数据库中提取并集成数据， 解决语义二义性问题，消除脏数据等： 数据选择( d a t as e l e c t i o n ) ，辨别出需要分析的数据集合，缩小处理范恩， 提高数据挖掘的质量； 霍磊国磊回露懊 圈1 - 3 数据挖撬静步骤 预处理( p r e - a n a l y s i s ) ，将数据转换为数据挖掘工具所需要的格式； 数据挖握，它是知识挖掘的一个基本步骤，其箨用就是利用智能方法挖撅数 据模式或规律知识； 表述( p r e s e n t a t i o n ) ，将数据挖掘得到的售息( 模式) 鞋便于用户理解的和 观察的方式呈现给用户； 浙江工业大学硕士学位论文 评价( a s s e s s ) ，根据最终用户的决策目的，对所提取的信息或发现的模式 进行分析。 1 5 数据挖掘的任务 在通常情况下，数据挖掘任务可以分为两大类：描述和预测。描述性数据挖 掘指挖掘数据中的一般性质，预测性数据挖掘指使用当前数据进行推断，以做出 预测。典型的数据挖掘任务有聚类分析、概念描述、关联分析、分类与预测、孤 立点分析、时序模式分析等。 1 5 1 聚类分析 聚类分析是指将物理或抽象对象的集合分为相似的对象类的过程，要使同一 类的对象之间的差别尽可能小，而不同类别上的差别尽可能大。在这个过程中不 使用任何先验知识的指导，只依靠对象之间的相似性作为划分类别的标准，属于 无监督学习的范畴。 1 5 2 概念描述 概念描述本质上就是对某类对象的内涵特征进行概括。概念描述分为特征化 描述和区别性描述。前者描述目标类数据的一般特征和特性的汇总，后者是将目 标类对象的一般特性与一个或多个对比类对象的特性比较【1 1 1 。获得概念描述的方 法主要有两种：( 1 ) 利用更为广义的属性，对所分析数据进行概要总结，其中被 分析的数据就称为目标数据集；( 2 ) 对两类所分析的数据特点进行对比并对对比 结果给出概要性总结，而其中两类被分析的数据集分别被称为目标数据集和对比 数据集。 1 5 3 关联分析 关联是反映一个事件和其他事件之间的依赖或关联。数据库中的数据关联是 现实世界中事物的表现，但是数据之间的关联是复杂和隐蔽的。关联规则挖掘的 目的就是在数据中找到隐藏的关联关系。 关联分析广泛应用于购物篮或事务数据分析。关联规则挖掘是关联知识发现 浙江工业大学硕士学位论文 的最常用方法，其中最为著名的是a g r a w a l 等提出的a p r i o r i 及其改进算法，关 联挖掘的目的就是从数据库中挖掘出满足最低支持度和最低可信度的关联规则。 关联规则的研究和应用是数据挖掘中比较活跃和深入的分支，已经提出了许多关 联规则挖掘的理论和算法。 1 5 4 分类和预测 分类是数据挖掘中的一个重要的目标和任务。目前的研究在商业上应用最 多。分类就是找出描述并区分数据类或概念的模型，以便能够使用模型预测类标 记未知的对象类。分类的目的是学会一个分类函数或分类模型，也常常称作分类 器。要构造这样一个分类器，需要有一个训练样本数据作为输入。分类器的作用 就是能够根据数据的属性将数据分派到不同的组中。这样我们就可以利用该分类 器来分析已有数据，并预测新数据将属于哪一个组，即数据对象的类标记，然而， 在某些应用中，人们可能希望预测某些空缺的或不知道的数据值，而不是类标记。 当被预测的是数值数据时，通常称之为预测。分类模式可以采用多种形式表示， 如分类规则，判定树，数学公式或神经网络。分类知识挖掘的一些有代表性的技 术有：决策树、贝叶斯分类、神经网络、遗传算法与进化理论、类比学习、粗糙 集和模糊集等方法。 1 5 5 时序模式分析 时间序列的分析是数据挖掘中的一个重要的研究部分，在各个行业有着广泛 的应用价值。近年来在宏观经济预测、市场营销、客流量分析、降水量、水流量、 股票价格等领域有着众多的应用。时间序列挖掘指从序列中发现相对时间或其他 顺序所出现的高频子序列，通过对过去历史的客观分析，揭示其内在规律，进而 完成预测未来行为等决策性工作。 1 5 6 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致，这 些数据对象是孤立点。在挖掘正常类知识时，通常总是把它们作为噪音来处理。 因此以前许多数据挖掘方法都在正式进行数据挖掘之前就将这类孤立点数据作 浙江工业大学硕士学位论文 为噪声或者意外而将其排出在数据挖掘的分析处理范围之外。然而在一些应用场 合中，如信用欺诈、入侵检测等小概率发生的事件往往比经常发生的事件更有挖 掘价值。因此当人们发现这些数据可以为某类应用提供有用信息时，就为数据挖 掘提供了一个新的研究课题，即孤立点分析。孤立点探测和分析对于欺诈探测、 定制市场、医疗分析及许多其他的任务是非常有用的。发现和检测孤立点的方法 主要有基于概率统计、基于距离和基于偏差等检测技术的三类方法。 1 6 论文内容和组织结构 本文首先介绍了数据挖掘的概念和国内外的研究现状，着重介绍数据挖掘中 基于密度的聚类算法，分析了常见密度聚类算法的优缺点，在基于密度的聚类算 法的基础上，对d b s c a n 算法处理对象相似度的过程进行了改进，提出了一个 改进的能处理混合属性数据的密度聚类算法。 然后提出可以在数据流聚类中使用本混合属性的思想，提出了混合属性数据 流聚类情况中相似度的计算，定义了对象之间、对象与簇之间和簇与簇之间的相 似度，并提出算法处理簇的出现、移动、合并和消失的情况。最后对混合属性演 化的数据流聚类算法进行了仿真。 本文由五个章节组成，具体组织如下： 第一章是绪论。介绍了课题研究的背景和意义，然后阐述了数据挖掘的基本 概念、国内外研究现状、数据挖掘步骤、数据挖掘任务和应用并给出论文的主要 内容和结构。 第二章介绍聚类算法。从聚类算法的概念开始，介绍了聚类的数学描述，主 要的聚类算法和聚类的要求，分析了不同聚类算法的优缺点。 第三章介绍混合属性密度聚类算法。首先介绍了密度聚类算法的优点与不 足，分析了实际应用中常见的数据类型和对象相似性的定义。然后提出了混合属 性数据相似度的定义，提出了改进的混合属性密度聚类算法。最后在仿真的基础 上，说明新算法的优点。 第四章介绍数据流聚类算法。首先介绍了数据流的概念和数据流挖掘，并介 绍了数据流聚类框架c l u s t r e a m 算法。然后提出混合属性对象相似度的定义可以 应用到数据流挖掘中，解决数据挖掘中常见算法无法处理混合属性数据的问题。 浙江工业大学硕士学位论文 最后对c l u s t r e a m 算法进行了改进，提出改进的数据流聚类算法，并给原算法进 行比较。 第五章总结了本文在聚类算法方面的研究成果，指出了改进算法的不足和缺 陷，并对下一步的工作做出了展望。 最后附上参考文献和致谢。 1 7 本章小结 本章作为本文的绪论，首先介绍了本项研究的背景：数据挖掘的概念和特点。 接着重点介绍了目前国内外数据挖掘方面的研究进展情况和进行数据挖掘研究 的重要意义，然后介绍了数据挖掘的一般步骤和任务，最后给出了本文的组织结 构。 浙江工业大学硕士学位论文 2 1 聚类概述 第2 章聚类算法 聚类( c l u s t e r i n g ) 是一个将数据集划分为若干簇( c l u s t e r ) 的过程【1 1 】，并 使得同一个簇内的数据对象具有较高的相似度；而不同簇中的数据对象相似度较 ， 低。相似或不相似的描述是基于数据描述属性的取值来确定的。 搿人以类聚，物以群分一，聚类分析是一项人类认识世界的重要活动。在孩 提时代，人们便自发而不断的完善大脑中对物体的识别模式，用于区分如猫和狗， 动物和植物等。通过自动聚类能够识别对象空间中稠密和稀疏的区域，从而发现 全局分布模式和数据属性之间的有趣的相关。在生物科学研究中，可以通过对基 因的聚类研究，找出功能相似的基因，获得对生物种群的认识；在地理信息系统 中，聚类可以识别有相似使用情况的土地区域；在互联网上，可以对网页信息进 行分类识别；在电子商务上，聚类分析可以帮助市场人员确定相对固定的顾客群， 便于商家有针对性的指定销售方案、保留旧的客户群；在信息检索中，对文档信 息进行聚类可以加快信息检索的效率，从而提高工作效率；在气象预报领域，对 历史空气的温度、湿度等天气信息进行聚类，可以预测未来气候的变化；在医疗 分析中，可以对一组新型疾病聚类，得到每一类疾病的特征描述，就可以对这些 疾病的正确识别，提高治疗的效果；在天文学上，研究人员利用聚类来分析观测 到的数据，可以发现新型天体系统，对了解黑洞的形成和宇宙的进化提供帮助。 在2 0 世纪7 0 年代，聚类分析己经有了比较深入的研究1 1 2 , 1 3 , 1 4 , 1 5 。聚类的方法 主要有统计学方法和机器学习的方法： 2 2 聚类问题的数学描述和最优化模型 聚类严格的数学描述如下： 浙江工业大学硕士学位论文 一个集合阢u 含有挖个数据对象 墨，五，以) ，每个对象有有删个属 性，即数据对象可以表示为x ，= ( 五。，置：，；k ) 。聚类就是将一个数据集合u 按照数据对象相似度或相异度度( 距离) 的标准，划分为k 个簇：c l ，c 2 ， q ，并且满足下列条件： ( 1 ) e 0i - - - 1 ，j ( 2 ) c f nc j = f 3i , j = l ，2 ，七f j 七 ( 3 ) l j e = u v ( 2 1 ) ( 2 - 2 ) ( 2 3 ) 确定弘 c 1 ，c 2 ，q ) 的过程可描述为确定j 个分类中心的过程，即确 定g 的中心z ：f ，= - 1 ，2 ，3 ，七。对样本集合治 五，五，以) ，类g 是如 下确定的： i c i = x ，1 8 一一z ，8 k z p 8 ，p p = l ，2 ，七，x s u ) ( 2 - 4 ) 其中l i i i 是任意的范数，也就是说g 是离乙最近的点的集合。 这样，就可以把聚类问题看成寻找七个分类的中心 z l ，z 2 ，乙) ，使得所有 样本点船到它最临近中心点的距离之和取极小的最优化问题 h 蜀男善蹬8 置一乙 z j ，知，磊智1 s 脚l i ，“ ( 2 5 ) 选区不同的范数就可以得到不同的聚类问题的最优化模型。 2 3 主要聚类算法 常见的聚类算法可以分为以下几大类：划分方法、层次方法、基于密度的方 法、基于的网格方法和基于模型的方法。 2 3 1 划分方法( p a r t i t i o n i n gm e t h o d ) 划分方法算法简单明了，易于实现，因此研究的较多。对于一个给定的刀 个数据对象的数据集，采用目标函数最小化的策略，通过把数据分成七个组，每 浙江工业大学硕士学位论文 个组为一个簇，这就是划分方法。可以看出，这种聚类方法同时满足以下两个条 件：( 1 ) 每个组至少包含一个数据对象；( 2 ) 每个数据对象必须属于且仅属于一 个组。在有些模糊聚类技术中，条件( 2 ) 可以放宽要求。最著名的划分聚类算 法是k 咖e 锄s f l 5 】算法和k - m e d o i d s f l 6 】算法。 k - m e a n s 算法是最基本的划分聚类算法，k - m e a n s 算法以k 为参数，把聆个 对象分为k 个簇，使得结果簇内的相似度高，而簇间的相似度低。簇的相似度是 关于簇中对象的均值度量，可以看做簇的质心或重心。k m e a n s 算法随机地选择 k 个对象，每个对象代表一个簇的初始均值或中心，对以剩余的每个对象，根据 其与各个簇均值的距离，将它指派到最相似的簇，然后计算每个簇的新均值。这 上 个过程不断反复，直到准则函数收敛。通常采用平方误差准则e = ei p - m , 1 2 。 i 簟lp e q k - m e a n s 算法尝试找出使平方误差函数值最小的k 个划分。当结果簇是密集 的，而簇与簇之间区别明显时，它的效果较好。面对大规模数据集，该算法是相 对可扩展的，并且具有较高的效率。算法的复杂度为0 ( n a ) ，其中，刀为数据 集中对象的数目，k 为期望得到的簇的数目，t 为迭代的次数。通常情况下，缸嘞， 且f ，z 。算法可以终止于局部最优解。 但是，k - m e a n s 方法只有在簇的平均值被定义的情况下才能使用。这可能不 适用于某些应用，例如涉及有分类属性的数据。其次，这种算法要求事先给出要 生成的簇的数目k ，显然，这在某些应用中是不实际的。另外，k - m e a n s 方法不 适用于发现非凸面形状的簇，或者大小差别很大的簇。还有，它对于噪音和孤立 点数据是敏感的，少量的该类数据能够对平均值产生极大的影响。 人们对k m e a n s 算法初始簇的选择、对象的划分、相似度的计算、簇中心的 计算等方面进行改进【l s - 2 s 。 k - m e d o i d s 的过程和上述的k m e a n s 方法过程类似，唯一不同之处就是： k - m e d o i d s 方法用簇中最靠近中心的一个对象来代表该簇，而k - m e a n s 方法用质 心来代表簇。在k - m e a n s 方法中，对噪声和孤立点数据非常敏感，因为一个极大 的值会对质心的计算带来很大的影响。而k - m e d o i d s 方法中，通过用中心点来代 替质心，可以有效地消除这种影响。各种不同的k - m e d o i d s 算法中，较为常见的 有p a m 算法、c l a r a 算法、c l a r a n s 算法等。 浙江工业大学硕士学位论文 2 3 2 层次方法( h i e r a r c h i c a lm e t h o d ) 层次聚类算法把数据分层建立簇，形成一棵以簇为节点的树。如果按自底向 上进行层次分解，则称为凝聚的( a g g l o m e r a t i v e ) 层次聚类；而按自项向下的进 行层次分解，则称为分裂的( d i v i s i v e ) 层次聚类。 凝聚的层次聚类：这种自底向上的策略首先将每个对象作为一个簇，然后合 并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者某个终结条 件被满足。绝大多数层次聚类方法属于这一类，它们只是在簇间相似度的定义上 有所不同。 分裂的层次聚类：这种自顶向下的策略与聚合的层次聚类相反，它首先将所 有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇， 或者达到了某个终结条件，例如达到了某个希望的簇数目，或者两个最近的簇之 间的距离超过了某个闽值。 层次方法存在一个明显的缺陷是在进行分解或合并之后无法回溯，使得该方 法无法纠正自身的错误决策。但这一点也有一个可用之处，就是在进行合并或分 解是无需考虑不同选择所造成的组合爆炸问题。 将循环再定位与层次方法相结合使用是很有效的，c u r e i 2 6 1 、b i r c h | 2 7 1 、 c h a m e l e o n t 6 5 】等具有可扩展性的聚类算法就是采用这种组合方法进行设计 的。该组合方法是首先利用自下而上的层次方法，然后再利