（计算机软件与理论专业论文）一种改进的cobweb算法研究.pdf

3 l i c l a s s i f i e di n d e x ： u d c ： ad i s s e r t a t i o nf o rt h ed e g r e eo f m e n g r e s e a r c ho na ni m p r o v e dc o b w e b a l g o r i t h m c a n d i d a t e ： s u p e r v i s o r ： a c a d e m i cd e g r e e a p p l i e df o r ： s p e c i a l i t y ： d a t eo fs u b m i s s i o n ： d a t eo fo r a le x a m i n a t i o n ： u n i v e r s i t y ： y u y a n g p r o f z h a n gj i a n p e i m a s t e ro f e n g i n e e r i n g c o m p u t e rs o f t w a r ea n dt h e o r y j a n u a r y , 2 0 1 0 m a r c h ，2 0 1 0 h a r b i ne n g i n e e r i n gu n i v e r s i t y “叶 r 、 0 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：a 洱 日期： 0 年，月乡日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可乜在授予学位1 2 个月后口解 密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：百著 日期：w f 矿年月杉日 导师( 签字) 切f 口年；月日 t 公 b i 哈尔滨丁程大学硕士学侍论文 摘要 数据挖掘中的聚类分析一直是近年来应用极为广泛的技术之一。所谓聚 类，是物理或抽象对象的集合分成由类似的对象组成的多个类的过程。而随 着信息技术的发展，数据的形式也逐渐多样化，很多数据集中都包含有不确 定的属性，这类数据被称为不确定数据。在生物、医学等领域，这种不确定 数据更为常见。传统的模型聚类算法并不能提供一个有效的方法来处理此类 数据。本文针对经典的c o b w e b 算法，给出了一种基于不确定数据的聚类 算法来解决原算法不能处理不确定因素的问题。 本文首先分析研究了数据挖掘的相关理论与技术、数据挖掘中聚类分析 一般步骤和经典算法，特别针对基于模型的聚类算法进行认真研究和分析。 其次，在认真研究了原c o b w e b 算法的基础上，就其在应用过程中存在不 能处理不确定数据的问题，给出了一种改进算法。改进算法以不确定数据作 为输入源，采用经典的信息熵、欧氏距离和相似性度量理论改进了原算法的 分类效用函数，新函数对于实例有更全面的解释和表达，同时也模型化了新 分类树。最后通过仿真实验来对比两种算法，结果表明新算法能够有效地处 理不确定数据，而且在不降低时间复杂度的基础上提高了聚类的质量和聚类 准确率。 。关键词：数据挖掘；聚类分析；c o b w e b 算法；分类效用；相似性度量； ，t 一 t _ - a b s t r a c t c l u s t e r i n ga n a l y s i si sav e r yi m p o r t a n tm e t h o di n d a t am i n i n gr e s e a r c i l i n g a r e a t h es o c a l l e dc l u s t e r i n g ，i st h ep r o c e s so fd i v i d i n gr e l a t e dd a t ai n t oas a m e c l a s s i nr e c e n ty e a r s ，w i t ht h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y - , f o r m so f d a t ag r a d u a l l yi n t e n dt od i v e r s i f y m a n yr e a ld a t a s e t sh a v eu n c e r t a i nc m e g o f i c a l a t t r i b u t ev a l u e st h a ta r eo n l ya p p r o x i m a t e l ym e a s u r e do ri m p u t e d i nt h eb i o l o g i c a l ， n l e d i c a l 龇l do t h e rf i e l d s ，t h e s eu n c e r t a i nd a t aa r em o r ec o m m o n c u r r e n t l y , t r a d i t i o n a lc o n c e p t u a lc l u s t e r i n ga l g o r i t h m sc a l ln o tp r o v i d eac o n v e n i e n ta n d e f f e c t i v em e a n sf o rh a n d l i n gt h i st y p eo fu n c e r t a i n t y t h i sp a p e r e x t e n d s c o b w e ba l g o r i t h mt oe x p l i c i t l yh a n d l eu n c e r t a i n t yi nd a t av a l u e s ，a n dt h e n p r o p o s e s n e w c a t e g o r yu t i l i t y i n d e xf o r m e a s u r i n g t h e q u a l i t y o ft h e c h u s t e r i n g a t l a s ti t d e v e l o p si m p r o v e da l g o r i t h m s f o re f f i c i e n t l yc l u s t e r i n g u n c e r t a i nc a t e g o r i c a ld a t a ，b a s e do nc o b w e bc o n c e p t u a lc l u s t e r i n ga l g o r i t h m t h i sp a p e rg i v e sa ni n t r o d u c t i o no ft h et h e o r ya n dt e c h n o l o g yo fd a t am i n i n g ， g e n e r a ls t e p sa n dc l a s s i c a la l g o r i t h m si nc l u s t e ra n a l y s i s ，e s p e c i a l l yd o e ss o m e r e s e a r c ha n da n a l y s i so nt h ec l u s t e r i n ga l g o r i t h mb a s e do nm o d e l t h e nt h r o u g h t h ea n a l y s i so ft h eo r i g i n a lc o b w e ba l g o r i t h m ，t h i sp a p e rs t u d i e si t ss t e p sa n d w o r kp r o c e s s ，a n da l s oa n a l y s e st h ea d v a n t a g e sa n dd i s a d v a n t a g e so fi t t h e r ea r e s o m ed i s a d v a n t a g e s ：i tc a n th a n d l eu n c e r t a i nd a t a ，a n dt h ea l g o r i t h mn e e d sl a r g e s p a c ef o rs t o r a g e s ot h i s a r t i c l e f o c u s e so nt h eu n c e r t a i nd a t aa si n p u t ，a n d m o d i f i e st h eo r i g i n a la l g o r i t h m ，t h e nu s e st h ec l a s s i c a lt h e o r yo fi n f o r m a t i o n e n t r o p ya n ds i m i l a r i t ym e a s u r et oi m p r o v et h ec a t e g o r yu t i l i t yf u n c t i o n ，a n dt h i s n e wf u n c t i o nc a nc o m p l e t e l ye x p l a i na n dd e s c r i b et l l en e wi n s t a n c e ，a tt h es a m e t i m e ，i th a sm o d e l e dt h en e wc a t e g o r yt r e e t h ef i n a le x p e r i m e n tu s e sp r a c t i c a l t r a i n i n gd a t e s e t st oc o m p a r et h et w oa l g o r i t h m ，a n dt h er e s u l ts h o w s t h a tt h en e w a l g o r i t h md e a l sw i t ht h eu n c e r t a i nd a t am o r ee f f i c i e n t l ya n di m p r o v e st h eq u a l i t y a n da c c u r a c yo fc l u s t e r i n gw i t h o u ta n ys a c r i f i c eo ft i m e p - q 哈尔滨t 程大学硕十学位论文 k e yw o r d s ：d a t am i n i n g ；c l u s t e r i n ga n a l y s i s ；c o b w e ba l g o r i t h m ；c a t e g o r y u t i l i t y ；s i m i l a rm e a s u r e ； 气 ， k q 哈尔滨丁程大学硕士学位论文 - - _ _ 目i i t m li 1 - l 目录 第1 章绪论l 1 1 引言1 1 2 国内外研究现状2 1 3 论文的研究内容5 1 4 论文的组织结构6 第2 章数据挖掘及聚类分析。7 2 1 数据挖掘7 2 1 1 数据挖掘的定义7 2 1 2 数据挖掘的一般流程8 2 1 3 数据挖掘的意义9 2 2 聚类分析9 2 2 1 聚类分析的一般步骤1 0 2 2 2 传统聚类算法介绍1 l 2 2 3 不确定数据聚类介绍1 4 2 3 基于模型的聚类算法分析1 6 2 4 本章小结1 7 第3 章一种改进的c o b w e b 算法1 8 3 1c o b w e b 算法l 8 3 2 原算法总结分析2 3 3 3 不确定数据2 5 3 4 信息熵2 7 3 5 相似性度量2 9 3 6 基于不确定数据的新c o b w e b 算法提出3 l 3 7 算法分析3 7 哈尔滨t 程大学硕十学位论文 3 8 本章小结”3 7 第4 章仿真实验及分析3 8 4 1 实验环境3 8 4 2 聚类质量分析”3 9 4 2 1 聚类质量”3 9 4 2 2 聚类准确率对比”4 l 4 2 3 参数值对聚类准确率的影响”4 4 4 3 执行时间比较4 5 4 4 本章小结4 6 结论“4 7 参考文献4 8 攻读硕士学位期间发表的论文和取得的科研成果5 3 致谢一5 4 哈尔滨t 程大学硕十学位论文 1 1 引言 第1 章绪论 随着信息时代的来临，信息技术也蓬勃发展。信息化也被各行各业提 上了日程。面对如此庞大的信息量，如何能抓住信息中有用的部分为人们 服务也就成了一个新的挑战。在这样的应用背景下，数据挖掘技术应运而 生。尽管数据挖掘技术已经应用得十分广泛，但是数据流的出现又给这个 领域填上了更多的色彩。数据流是高速的、连续的、动态的、快速变化的、 海量的数据集合，它的出现受到了越来越多人的关注。这些数据的共同点 就是数据规模巨大，且数据快速持续到达，数据通常只能被读取一次。数 据流与一般数据的区别在于它的到达是快速的、无界的、时变的和不可预 测的，从而不可能将原始数据流中的数据完全存储。探究如何快速高效的 从包含大量数据的数据流中提取有价值信息的有效途径已成为数据挖掘方 向的客观需求，因而对数据流的分析和数据流挖掘在近几年快速兴起并已 发展成一个全新的研究领域。 在数据流飞速发展的大背景下，数据流聚类作为数据流挖掘的关键技 术，受到了越来越广泛关注和研究。首先，聚类( c l u s t e r i n g ) 是数据挖掘 中的重要组成部分，所谓聚类就是将数据对象分组成为多个类或簇 ( c l u s t e r ) ，最终目的是在同一个簇中的对象之间具有较高的相似度，而不 同簇中的对象差别较大。相似度是根据描述对象的属性来计算的，同时计 算相似度的方法也有很多，距离是经常采用的度量方式。从统计学的观点 出发，聚类是通过数据建模来简化数据的一种方法。很多经典的聚类方法 也被应用于统计软件包中进行实践，如业界应用广泛的s p s s 统计软件包。 聚类可以作为一个独立的工具来获得数据的分布情况，观察每一簇的数据 特征，集中对聚簇集合进行下一步的分析和操作。聚类受到很多关注的原 因主要有以下几点： 哈尔滨丁程大学硕士学何论文 一i i 萱宣| 宣昌宣i i 暑暑i 叠暑| 置| 昌宣| i | 皇暑i 皇胃置皇| 暑盲暑宣置皇i i 宣置i i i i i 暑置暑暑i 置i 嗣i 皇置i 宣暑i 暑置| 葺一 ( 1 ) 聚类是对整个数据集合处理方法中比较行之有效的方法，数据挖 掘所对应的数据并不像人们想象中的那样简单，所以聚类过程也不是一成 不变。在现实世界中，数据会以多种形式出现，当然更会发生一些概念漂 移，这使得原有的聚类方法根本不适用这些数据，也就无形中增加了研究 者的开发聚类算法难度。 ( 2 ) 聚类分析是针对数据集合的数据挖掘技术的先前步骤，它对于信 息的处理以及知识发现和规律总结都有着重要的作用。所以数据挖掘的结 果好坏很大程度上取决于聚类过程的效果，因此聚类分析重要性可见一斑。 总结聚类分析在一些领域中的应用结论，可以看出在现实世界中，更 多的数据是连续变化不定的，数据的广泛应用吸引了众多学者对数据挖掘 中聚类算法的深入研究。从硬件角度看，其内存或缓存等存储空间是极其 有限的，处理机只能对某些数据进行有限次数的顺序扫描，因而迫切需要 一种动态的增量式的聚类算法来处理形形色色的数据；时间复杂性方面， 某些数据到来的速度很快，多数应用要求在数据到来之时就需要进行一些 分析决策，这对聚类算法的处理时间也提出了更高的要求。所以，当今数 据的特性决定了聚类算法也要进行相应的改进才能满足现实要求心，。 1 2 国内外研究现状 针对现如今不断变化的数据，聚类问题在数据库、数据挖掘和统计等 领域得到了广泛研究。以下是对国内外基于模型的聚类算法相关研究工作 的介绍和国内外目前研究现状。 尽管已经提出了大量的算法和处理框架，聚类分析依然是个极富挑战 和快速发展的研究领域。目前，聚类技术已经取得了丰硕的成果，但还存 在着许多问题。本文研究的算法属于基于模型一类的聚类算法，该类算法 是给定好事先定义的模型，根据模型来应用算法处理数据，一般应用于动 态增量的数据流中，但是该类算法在处理现如今的动态高速数据流方面也 存在着明显不足。当然其本身模型的优点也使得逐渐有越来越多的人在关 注研究该类算法。 近年来，不少基于模型的新聚类算法被提出。2 0 0 1 年，m o o r e 提出一种 2 哈尔滨r 程大学硕七学位论文 i i 新方法，称之为m r k d t r e e 的结构，也就是一棵树状结构来衡量聚类。该树 的整体结构描述为：多维数据空间下，先对训练集实例化，所得的结果被 一棵二叉树所描述，二叉树的节点记录概念信息。算法是通过自上向下递 归划分数据集的过程构造而成的，这种方法类似于按层遍历的聚类算法， 进而可以减少存取数据的次数n ”。 s o o n 算法，该方法利用神经网络方面的技术，生成虚拟的网络空间。 在这个网络空间中，划分出多个稳定的且被结构化的簇，一些参数的设定 基于神经网络中自适应的方式得出的结果。s o o n 方法是采用逐步扩展方式 的发现算法，意图将相邻的且相似的对象看做是一个虚拟空间的产物，递 归的调用算法来争取更多的实例加入这个空间中，直至最后收敛。该算法 在时间和空间允许的条件下建立了一个相似空间模型，所以可以充分的处 理大数据集。 d b c l a s d n 2 ，混合算法是基于模型、密度、网格的方法于一体。其主要 思想为：算法优先选取密度的方法作为核心，也就是说稠密区域和稀疏区 域作为化为聚类的首要标准，稠密区域内的点集概率分布函数用来描述簇 的特征，也就是构造概率模型。算法也通过划定区域网格来增量地把邻近 点加入到初始簇扭- 。 基于模型的聚类分析的算法一般分为2 种，：统计学方法和神经网络方 法。统计学方法的算法是c o b w e b ，以及改进的c l a s s i t 算法以及 a u t o c l a s s 算法。c o b w e b i ”是一个通用且简单的概念聚类的方法，这里不 再过多赘述。当然也涌现出了很多类似于c o b w e b 的算法。比如， l a b y r i n t h 算法，该算法是i ：l ：l t h o m p s o n 和l a n g l e y 提出的，该算法针对 输入数据的属性和值对进行了更细致的划分和描述，算法亦是为了构造出 模型而假设一个结构化的部件，递归调用的方式逐个检测样本，执行操作 如下： ( 1 ) 将实例逐步聚类，概念模型化； ( 2 ) 生成的模型需要做出一个整体性的描述； ( 3 ) 最终整体性聚类概念可以用层次化的模型结构表达。 c l a s s i t 算法使用有类别标签的训练集实例，但是类别标签并未在整 个概念层次建构时加入，用这种机制，很像是要在整个层次树建立起来之 3 哈尔滨t 程大学硕十学位论文 后再加入类别标签来表示聚类，然后再使用测试时所预测的类别，以及产 生一个分类正确率的标准量测。该算法是用来处理连续性资料的渐增式聚 类结构，它在每个子节点中为每个属性储存一个连续的常态分配，并采用 一个修j 下的类别效用，该效用是连续属性上的积分。 c o b w e b 3 算法是c l a s s i t 算法的一个改进算法，这个算法对原算 法进行了延伸和补充，首先针对整体数据集合中的所有数值属性，假设都 是常态分配，在这个大条件下为了解决属性和值对的问题而增加了一些参 数，称之为新的精确度。该精确度也是为了描述簇的信息，衡量实例之间 的相似或相异程度。 a i c c 引算法是一种归纳概念形成的系统，它渐增的是属性而不是实例， 这样依然可以建立层次性的模型聚类。该算法考虑每个属性增加时，都会 执行一次合并和分裂的操作程序。在分裂程序执行时，会将新增加进来的 属性放到根节点下的子节点，并试探性的将子节点下的成员分裂后，计算 新的分类效用，若是新的分类效用大于原来的值，就会执行原有的分裂操 作。同样的也会让新增加的属性和每一个子节点进行试探性的合并，直到 所有的属性都加入到阶层树中。该算法经过实例验证其时间复杂度降低很 多，还可以对不重要的属性进行鉴别。对于属性挑选的资料库有了额外的 好处。 i t e r a t e t 町是b i s w a s 等人所设计的概念聚类系统，它主要改善下列 两个问题：解决次序相依性问题以及对实例进行迭代重新分配，以及阶层 实例重新排序的方式，使得聚类更加完美。该算法有三个步骤： ( 1 ) 依据数据结构中广度优先算法控制结构生成概念聚类树，并在一 个子树建立前，对实例的输入顺序进行一个启发式的不相似性的排序，依 据这个排序，整个能够表达全部概念信息的“模型树 也就建立起来。 ( 2 ) 模型树中计算分类效用函数，以分类效用值测量在层次中选择一 个概念的代表，并以此为一个初始的类别。也就是说，为了形成初始的簇， 需要计算数值束对整体进行评测。 ( 3 ) 扫描实例，按照逐个实例遍历的方法找到与其最相近的类别中， 并直到没有实例可以再更改类别为止。 该算法用三个步骤来达成上述目的，在第一阶段首先对实例库进行预 4 哈尔滨工程大学硕士学位论文 先的排序，第二阶段是以分类效用的测量找出一个初始的类别，第三阶段 是最佳化的步骤，以相似度的度量来对类别进行重新分配，找到最好的聚 类。 之后基于该算法继续提出了最佳化和简单化的原则，并以三种策略来 建立起高聚类品质以及低计算成本的算法： ( 1 ) 重新排序：在初始的层次聚类建好之后，其属性都是不相似的次 序倾斜着，故要执行区间迭代。由于分裂和合并操作相当繁琐，也要尽量 的避免，最好的方式是最前的几个实例都是属于不同簇的，所以其排序的 最佳方式还是随机排序。 ( 2 ) 单一实例的重新分配迭代：把单一的实例一个接一个的移动，直 到找到最佳的聚类。 ( 3 ) 再分配：对最佳聚类进行一次新的搜寻。这个搜寻过程可能会依 赖时问空间的客观条件，所以再分配过程实际上是对聚类的一次重新扫描。 故现有条件允许的情况下这是个不断完善聚类的最佳途径。 以上是一些现有的基于模型的聚类算法，可以看出这些算法都是围绕 一个概念来形成聚类，以适应渐增的数据流输入。c o b w e b 算法的衍生算 法也有很多，这些算法都是根据数据模型化出一个初始簇，根据c o b w e b 算法提供的思想进行相关的后续操作修改，但是在这方面这些修改都有自 己的局限性，也需要针对实际问题而分析，具体的衍生算法思想将在稍后 做出分析。 1 3 论文的研究内容 本文研究内容属于数据挖掘中聚类算法的改进。文章首先介绍了数据 挖掘，以及数据挖掘中的聚类算法。在这些算法中，本文所研究的是基于 模型的聚类算法中的c o b w e b 算法，该算法一直被应用在确定属性值对 的对象中，不满足于现实中不断变化的数据模型。故需要改进算法以适应 不同类型的数据，研究方向也就应运而生，总结有以下几点： ( 1 ) 原算法采用分类效用来处理数据，而这种数据是确定的，没有任 何“模糊色彩 的数据。现如今数据本身已经发生较大变化，所以需要更 5 哈尔滨t 程大学硕十学位论文 好的函数来处理数据。新改进的函数还要能描述整个聚类的全部信息，以 及簇的相关特征。 ( 2 ) 不确定数据处理方法有很多，选取适当的处理方法对之后的聚类 分析有着相当大的影响。故既要选用一些经典的相似度处理方法，也要结 合那些能处理该类数据的方法，使得多种方法结合下的相似度衡量更加具 有说服力。 ( 3 ) 新算法从适用范围，处理方式，相似度衡量等方面都对原有算法 进行了一些改进，这就需要在程序编写以及后续的实验验证环节更加缜密。 最后从聚类的质量以及聚类的准确率等方面进行对比，验证算法是否具有 更好的聚类效果。 1 4 论文的组织结构 本文的内容结构如下： 第1 章对本文研究领域进行了简要介绍，阐述了国内外的研究现状， 并介绍了本文所研究的主要内容和组织结构。 第2 章介绍了数据流的定义，数据流聚类算法，以及分析聚类算法中 的典型方法，阐述了现有算法及其改进算法的优点和不足。最后分析了与 本文相关的基于模型的聚类算法，研究其算法本质为下面改进算法打下良 好的基础。 第3 章针对首先分析了原c o b w e b 算法，得出优缺点。然后扩大算 法的适用范围，引入不确定数据以及相似性度量理论进而给出了基于不确 定数据的新c o b w e b 算法，介绍新算法的实现过程，最后通过实例化描 述新算法作用机理。 第4 章实验应用仿真训练集对原算法和新算法的性能进行了测试，并 对实验结果进行了分析。 最后一部分是全文的总结，对本文的研究工作进行了总体的概括，并 对未来的研究工作进行了展望。 6 哈尔滨- t 程大学硕十学位论文 第2 章数据挖掘及聚类分析 数据挖掘一直是机器学习研究领域的一个热点。顾名思义，是从现有 的数据中挖掘出对人们有用的信息。这些信息既要形成某种特定的规律， 又要对后续情况做出预测。当然现实世界情况复杂，数据、时间、空间等 因素都是数据挖掘成功与否的重要标志。本章主要目的在于介绍数据挖掘 的相关概念，介绍经典的聚类分析算法和相关改进。然后对现有的基于模 型的数据流聚类算法进行了阐述，分析了它们的优点与不足，抓住其算法 的优势，仔细分析其缺点，全面掌握这类算法的本质规律，这也有助于开 展下面的工作，为下一章打下坚实基础。 2 1 数据挖掘 2 1 1 数据挖掘的定义 数据挖掘随着时代的不同以及应用领域的差异，有着其不同的解释。 一般说来，数据挖掘和知识发现息息相关，都是将数据库中的对研究者有 用的信息发掘出来的过程。也就是说数据挖掘是从数据中提取出一种模型， 该模型会对今后的研究进行预测。有效地数据挖掘会记录数据库中的诸多 属性。 提起数据挖掘，最新涌现的数据流挖掘更受广泛关注。所谓数据流挖 掘，是指建立在数据流这个载体上的信息抽取过程。数据流的形式化定义 为“8 ：数据流是数据对象a ，彳，构成的实例集，该集合是时间依次排序的 产物。其中每个数据对象丘是一个包括疗维的多维数据记录。数学上用刀 维向量的形式来表示：4 = ( 4 ，4 2 厶) ，其中4 ，表示第f 个数据对象4 的第，维的值，- j ，2 ，疗。数据流与传统数据的区别主要在于：数据是动 态的，随机性变化性极强，不容易预测其下一步的趋势。数据的存储不方 7 哈尔滨工程大学硕士学位论文 誓暑| | 皇| 墨| 置置皇葺葺宣宣i 皇i 暑暑暑置嗣宣暑葺i 暑叠置宣暑i i i i i l i j , r 1 皇i 薯一 便，无限制的数据流不能全部存储在硬盘空间中以便研究“。数据流在现如 今的各行各业中出现频繁，电子商务、网络监测等都属于这个范畴，所以 研究数据流挖掘更具有现实意义。 2 1 2 数据挖掘的一般流程 数据挖掘一般分为四个步骤：数据筛选、数据变换、挖掘数据、解释 结果。现如今的数据挖掘更倾向于数据流的挖掘，而原有的数据挖掘过程 模型并不能完全应用于现在的数据流n 引。针对数据流的数据挖掘过程如图 2 1 所示。 图2 1 数据挖掘流程 ( 1 ) 数据筛选：第一步是分析数据源，然后收集有效数据的过程。在 数据流挖掘中，由于数据流本身的特殊性，截取数据流就显得十分重要。 这是因为在数据提取之前进行数据的筛选，同时预先找出构造规则是相当 复杂的事情，然后进一步要确定数据的一些属性和值域。 ( 2 ) 数据变换：将数据变换成特定的格式。这个步骤比较广泛，还包 括其中的数据预处理等，数据流的属性繁多，针对不同的形式需要用到不 同的数据预处理方法。 ( 3 ) 挖掘数据：前两步骤完成之后，就可以使用数据挖掘工具。需要 设计良好的算法来实现，这个步骤在数据流挖掘时要充分考虑到数据流的 动态性和不确定及不可预知性，所以对于算法要求也颇高。 ( 4 ) 解释结果：最后一个步骤是解释结果，也就是得出的结果需要一 个科学且客观的评价。数据流得出的模型解释更加复杂，由于所针对的仅 仅是被截取的部分，最终的知识和规律是否能够很好的解释整个数据流挖 掘也是需要研究者重点探讨的地方。 r 哈尔滨j t 程大学硕十学位论文 2 1 3 数据挖掘的意义 数据挖掘已经成为商务及软件杂志中许多文章的主题。随着科技日新 月异的发展，数据挖掘也有着其深远的意义和影响，主要体现在以下几个 方面： ( 1 ) 数据挖掘出现加速了多学科的融合，促进了各个学科的发展。数 据挖掘可以看成是多种技术的集成。统计学、数据库管理学、机器学习、 并行处理技术都是相互影响和支持数据挖掘的工具。来自计算机辅助领域 的诸多技术也逐渐向数据挖掘方向靠拢，总体来看，数据挖掘带来了更为 广阔的学科交流。 ( 2 ) 数据挖掘中的知识发现和决策系统对现如今的管理者来说是最好 的助手。经过算法总结出的知识和规律有助于企业进行决策。这种对数据 分析更为客观的决策也相应的形成诸多系统，如大家所熟知的地理信息系 统，联机分析处理系统等。 ( 3 ) 数据挖掘作为对数据最行之有效的处理方法，所获得信息是被大 家所共享的，也就是形成了信息链。信息时代处理信息的时效性和准确性 决定了行业的成败。 2 2 聚类分析 聚类分析是数据挖掘中一项重要技术，是探查数据结构的工具。聚类 分析的核心就是聚类，聚类分析聚类的数学描述如下：设样本集合空间d ， c 定义为d 的一个非空子集，即c cd 且c 西，那么数学角度出发所谓的 聚类集合是i w li ( 1 ) q u c u u q = d 。 ( 2 ) gr 、c ，= 矽( 对任意淳；，) 。 这种非监督学习作为数据挖掘中数据处理划分的关键步骤，日益成为 一个活跃的数据挖掘分支。聚类分析也有一些重要技术，并且被研究者广 为接受，：概略、直方图、抽样、滑动窗口、负载脱落技术。这些技术都是 9 哈尔滨工程大学硕士学位论文 一i 置叠i 宣置皇皇置鲁薯| 蕾叠置毒宣i 置皇暑葺i 宣萱暑i 暑宣i 置宣i 昌i 置i 暑i 置宣暑宣葺i 置宣暑置蕾宣i 宣置薯皇| i 置薯i | 置i 传统数据模型下的一些方法，如滑动窗口系列。在统计学上，通过数据建 模简化数据的方法是通过聚类分析来表达的，统计的方式也融入进了聚类 分析中，比如模糊学、贝叶斯算法等都成功地帮助聚类有效的建立相关模 型。在机器学习上，无监督的学习方法更是自适应数据集的观察学习，这 种自动搜索簇的过程不依赖对实例的预先标记。在商业上，效益的最大化 决定了某些运营模式的出现，但这种模式也是根据事先聚类分析做出的判 断。在生物学上，基因和病理上面的研究也离不开聚类分析，疾病的控制 和人群的特征都需要进行划分以便合理处理。 2 2 1 聚类分析的一般步骤 上述提到了现如今聚类分析应用的领域十分广泛，而在这些领域中， 聚类分析的过程一般由三个步骤组成，分为：数据准备阶段、聚类阶段、 评估和表示阶段。具体步骤如图2 2 所示。 1 数据准备阶段 2 聚类阶段3 评估和表不阶段 图2 2 聚类分析的一般步骤 ( 1 ) 数据准备阶段 该阶段主要是为所要进行的聚类分析打下基础，准备数据也称之为数 据预处理。需要对现有数据进行一些筛选，属性特征被抽取进行重新整合 而形成新的特征集合。这个集合便于针对属性开展的数据预处理操作，避 免了“维数灾难”。准备阶段如此重要更体现在对于噪声数据的处理，将i j i i 练集中的冗余元素去掉利于之后的聚类阶段。 ( 2 ) 聚类阶段 聚类阶段是应用聚类算法对训练集进行的相关操作，应用聚类算法进 行聚类要考虑到算法的适用性。例如当训练集为数据流片段时，传统的聚 l n 哈尔滨丁程大学硕十学位论文 类算法就可能不适用。所以聚类算法也要做到“随机应变”，能根据不同数 据类型进行聚类。 ( 3 ) 评估和表示阶段 聚类阶段结束后，会得出簇的结果，这些簇代表聚类特征。每个簇都 有该类的信息描述，如何评估和表示这些簇也就显得尤为重要。类内相似 性以及类间相异性表达也需要在这个阶段给出，研究者通常会根据这些表 达最终得出聚类分析的结果。 2 2 2 传统聚类算法介绍 下面介绍一下目前存在的传统聚类算法，可以分为划分聚类方法、层 次聚类方法、基于密度的聚类方法、基于网格的聚类方法和基于模型的聚 类方法。算法的选择取决于数据的类型、聚类的目的和应用。下面是这些 算法的一些介绍。 1 划分的方法 基于划分思想的是最早提出的聚类算法，此类算法的最大局限性是必 须事先给出聚类的数目。k - m e a n 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 d o i d s 算法时间复杂性方面要大大超过原来k m e a n s 算法，因此在实际应用中要 慎重考虑。 后来学者针对以上两种算法综合进行了一些改进，新的算法所用的仅 仅是单遍扫描，并且所需要的存储空间更少，并且所用的时间复杂度和空 间复杂度较原来的算法有了提高。针对g u h a 所提出的算法，后人加入直方 图的理念更加有利于簇的合并。接着更多的思想融汇贯通于该算法，例如 采用分而治之思想的新k m e a n s 算法，首先将数据分块，然后通过计算各 个小块的信息最后汇总达到最终目标。这种思想在处理大数据集合的聚类 算法中也应用的十分广泛。 l l 哈尔滨t 程大学硕七学位论文 2 层次的方法 基于层次的方法可以说是一种树状的架构。层次的方法对给定的数据 对象集合进行层次的分解。根据层次的分解如何形成，层次的方法可以分 为凝聚和分裂两种。凝聚和分裂两种模式分别是自下而上和自上而下的聚 类过程。图2 3 所表示的是一个实例，该实例描述了a b c d e 资料集合在凝 聚式和分裂式相对应的情况下的处理过程。 s t e p 0s t p1s t o p 2s t p 3s t e p 4 s t e p 0s 姊1s t , p 2s t p 3s l 印4 图2 3 基于层次的聚类算法举例 层次聚类方法虽然简单，但经常会遇到合并点或分裂点选择的困难， 同时这种聚类方法不具有很好的可伸缩性，因此人们提出众多改进的层次 聚类算法以改进传统方法的性能。一般来说有4 种方法是最近极为常用的t ( 1 ) b i r c h 算法】是由z h a n g 等人提出的算法，使用层次式的平衡迭 代化聚类思想，引入分群特征和分群特征树等概念，以各个分群特征动态 的创建一棵层次树，用这个树状结构来实现整个聚类的描述。由于分类特 征并不能存储所有的属性特点，只是存储子聚类中相对较重要的有关信息。 当资料信息逐渐增多，该特征分类树也将逐渐扩展，这样的方法支持渐增 式的输入，树中利用父节点来存储整个树的信息，创建一个平衡的树，并 考虑到所使用最少的i o 时间，从而在扫描的过程中提高聚类的品质。 ( 2 ) c u r e 算法心町是由g u h a 等人提出，代表点聚类以聚类之间相似度 为合并的依据。该算法首先选择c 个点来代表聚类，如果以一个点代表聚 类则聚类的效果不好；反之要是以所有点来代表聚类，那么将相当耗费时 间，接着将全部的代表点向中心收缩参数，参数值固定给出在0 1 之间， 以此将相似的聚类进行合并，直到所要的记录数为止。该算法适用于大型 的资料集合，可以辨认任何形状的聚类，对于离群值处理比较健全，但不 1 2 哈尔滨_ 丁程大学硕士学位论文 能处理类别属性资料。 ( 3 ) r o c k 算法m 也是由g u h a 等人提出，该算法使用链接聚类来处理 类别属性，基于互联度来合并两个聚类，当强调互联度时，忽略两个不同 聚类的相似程度。r o c k 算法强调不同聚类之间的链接关系。相比c u r e 算法来说，r o c k 算法更注重聚类之间的相似程度，这样能更好的达到聚 类效果。 ( 4 ) c h a m e l e o n 算法n 引是由k a r y p i s 等人提出的一种方法，这种算 法的特殊之处在于该算法是一种基于图划分的方法。被聚类的对象可以看 作是图的顶点集合，两个对象通过一个权重系数为正的无向边连接起来， 如果去掉一组边，该顶点和边集合将被划分成为互不相连的子图集合。 c h a m e l e o n 采用两个阶段算法寻找簇，第一个阶段将数据项划分成为大 量较小的子簇，子簇来表达聚类结果。但是有个潜在的要求是子簇之间的 链接要较子簇内部的链接稀疏，这样不相关系数越小的子簇越便于区分。 第二个阶段应用凝聚层次聚类算法反复结合这些子簇，最后得到真正的聚 类。这个过程最重要的是如何结合现有的子簇，算法设定了两种方案来实 现。一种是参数办法，控制期望簇的特征；另一种是函数方法，结合互联 性和相对紧密性来合并簇对。 3 基于密度的方法 基于密度的方法是应用较为广泛的算法之一。d b s c a n m l 是一个有代 表性的基于密度的方法，算法设定两个参数来控制簇，即邻居区域的半径 和点数，只要在这个半径下的邻居区域的点数超过了基本阈值，那么就将 该资料加入进聚类中。o p t i c sc 矧是另一个基于密度的方法，它为自动的和 交互的聚类分析提供一个聚类顺序。根据密度的原则，主观的定义了边界 点和核心点，这样聚类只需根据点性质的不同实现来划分。d b c l a s d 算 法，是前面已经提到，该算法既然是融合多种思想的产物也会受到客观环境 的影响。 4 基于网格的方法 基于网格的方法是很容易的增量实现和对于高维数据挖掘行之有效的 处理方法使得该类算法在数据挖掘领域一直非常活跃。基于网格的方法把 对象空间量化为有限数目的单元，由此形成一个网格结构，所有的聚类操 1 3 哈尔滨r t 程大学硕士学位论文 作都在这个网格结构上进行。s t i n g 算法依旧是基于网格方法的一个典 型例子，定义网格进而划分聚类，当然这也是牺牲一些聚类准确率而达到 的效果。c l i q u e i 圳既是基于网格的又是基于密度的，作为一种更为广泛的 子空间聚类算法，该算法可以任意的组合产生所谓的子空间，这个子空间 中拥有数据的一些投影。本算法可以发现任意形状的聚类，还可以处理高 维数据以及增量的数据集。 。5 基于模型的方法 ， 现如今，基于模型的聚类算法还是应用不多，主要因为基于模型的算 。 法本身思想的限制。基于模型的方法为每个簇假定了一个模型，寻找数据 对给定模型的最佳拟合。模型化解决聚类固然可行，但是这类模型的实用 性和可行性往往受到质疑，所以这类算法还亟待开发。经典的算法例如 p i z z u t i c l a r a 提出的p - a u t o c l a s s 和人工神经网络中的s o f m 、a r t 网络模 型等捌。 2 2 3 不确定数据聚类介绍 以上介绍了聚类分析的工作流程以