（计算机软件与理论专业论文）基于聚类技术的qmp模型建立与知识发现.pdf

英文摘要 abs tract d a t a m i n i n g i s n u mb e r . i t i s a l s o v a l u a b l e , u n k n o w n , a k i n d o f t e c h n o l o g y u s e d t o f i n d , o r m i n e , k n o w l e d g e t h r o u g h d a t a i n l a r g e c a l l e d k n o w l e d g e d i s c o v e r y i n d a t a b a s e s ( k d d ) , a p r o c e s s t o f i n d h i d d e n , p o t e n t i a l a n d u s e f u l i n f o r m a t i o n c l u s t e r i n g i s a s i g n i f i c a n t t e c h n o l o g y i n d a t a t m i n i n g . i t c l a s s i f i e s d a t a o b j e c t s , a c c o r d i n g t o t h e i r s i m i l a r it ie s , i n t o s e v e r a l c l u s t e r s s o t h a t d a t a o b j e c t s i n t h e s a m e c l u s t e r a r e m o r e a l i k e t h a n t h o s e f r o m d i f f e r e n t c l u s t e r s i n t h e t h e s i s , w e d i s c u s s t h e i m p l e m e n t a t i o n s o f d a t a m i n i n g . n e w i n f o r m a t i o n a n a ly s i s m e t h o d s a r e i n t r o d u c e d a n d e x p a n d e d . s o m e s o l u t i o n s t o i m p le m e n t a t i o n a r e g i v e n i n d e t a i ls . t h e ma i n r e s e a r c h r e s u l t s a r e l i s t e d a s f o l l o ws . t o q u a n t it a t i v e a t t r i b u t e s i n t i m e s e r i e s d a t a b a s e , a n e w m o d e l , q u a n t i t a t i v e m o v e m e n t p a t t e r n ( q m p ) m o d e l , i s p r e s e n t e d . t h i s k i n d o f m o d e l i s u s e d t o e x p l a i n t h e r e l a t i o n s a m o n g m o v e m e n t t r e n d s o f q u a n t i t a t i v e a tt r i b u t e s . t h e t h e s i s i n t r o d u c e s t h e i m p l e m e n t s t e p s , u n f o ld s t h e r e l i a b i l i t y a n d t h e e f f i c i e n c y o f t h e i m p l e m e n t . w e i m p r o v e t h e c l u s t e r i n g m e t h o d s , p r e s e n t a n t e c h n o l o g y c l u s t e r i n g d a t a o b j e c t s w i t h c l i q u e f i r s t , m e a n w h i l e , d e t e r m i n i n g t h e v a l u e o f k , t h e n , u s i n g c l a s s i c a l a l g o r it h m o n t h e d a t a o b j e c t s . i n t h i s w a y , h e n c e , w e g e t r i d o f t h e s h o rt c o m i n g s o f t h e d e p e n d e n c e o n o u t l i e r s o f t h e o r ig i n a l a lg o r i t h m a n d , a l s o ， t h e s e n s i b i l i t y o n t h e u s e r s i n p u t o f t h e v a l u e o f k . i n t h i s p a p e r , w e a l s o i n c l u d e a n o v e rv i e w o f a p r o t o t y p e , w h i c h c o n s i s t s o f t h e f o l l o w i n g p a rt s : d a t a p r e p r o c e s s i n g , q mp m o d e l c o n v e r s i o n , d a t a m i n i n g a n a l y s i s , r e s u lt v e r i f y i n g . t h e p r o t o t y p e s y s t e m h a s e x c e l l e n t a p p l i c a t i o n m a r k e t a s w e l l a s i t s a c a d e m i c v a l u e . i t c a n b e u s e d b y n o r m a l u s e r s , a n d c a n b e e x t e n d e d a s a l i n k b e t w e e n d a t a m i n i n g a n d m o v e m e n t p r e d i c t io n . k e y w o r d s : d a t a m i n i n g , c l u s t e r i n g , p r o t o t y p e , m o v e m e n t m i n i n g , q u a n t i t a t i v e m o v e m e n t p a t t e rn m o d e l , 1 ! 第一章 绪论 ， . ， 问题的提出 随着计算机技术的迅速发展， 人们手中的数据急速膨胀。对于海量的数据，人们难以用有 效的 方 法得到感兴 趣的知识， 从而 形成数据丰富而 知识 缺乏的 状况。而在 数据和知识之间， 建 立有效的转换，使这些得到的大量数据利用起来，形成有价值的知识资源，就是一个迫切的问 压。数据挖掘技术，就是在这种背景下发展起来的。 数据挖掘在目前是国际上数据库和信息决策领域的热点。其研究的主要目 标是要发展有关 的理论、 方法以 及工具，从那些大量的数据中，发现人们需要的知识。 在各种数据中，含有数量型属性的时序数据库在经济领域以及科学决策领域中 应用很广。 传统的时间序列方面的研究都是针对序列的形状，来发现形状相同或类似的序列。再利用知识 挖掘的方法，来发现序列形状中所蕴涵的知识。它主要应用于以下的方面: .发现哪些公司具有类似发) 函 奋 吠; ，行 .确定哪些商品具有类似的销售模式: .找到具有类似的价格增减情况的股票。 在所有的数据挖掘问 题中，从大型数据库中发现关联规则无疑是本领域中很重要的一种方 法。 关联规 则中， 最常用到的 就是针对超级市 场的 大型 事务型数据库的市场篮 分析 ( m a r k e t b a s k e t a n a l y s i s ) 。 利用这种方式 我 们可以 发 现这样的 规则: r i : 有8 0 %购买面包的顾客也购买牛奶 ( 面包= ) 牛奶( 2 0 %, 8 0 %) ) 在这里，8 0 %就是规则的置信度而2 0 %就是规则的支持度，表刁 、 本规则适用的概率。 同样的概念也可以应用于其他地方。例如，预测股票市场的移动趋势，可以用这样的方法 来建立一个事务型数据库:数据库中的每条记录 ( 事务)代表一个交易日，并记录当日上涨超 过一定程度的股票。这样，利用关联规则，就可以得到这样的规则: r 2 : 当i b m和s u n的股票上涨的时候，微软的股票有8 0 %的可能性在同一天也上涨。 r 2可能反映了一些价格的关系，但这种规则在价格预测上的作用也十分有限。 由于 这种价格数据也可以称为时间序列型数据，因此，也可以用时间序列的方式来解决。 为了 应用时间序列方法，可以将数据库这样组织:将每支股票处理为一个顾客，这里的事务就 处理成上涨或下跌。这样我们就能得到这样的规则: r 3 : 8 0 %股票在下跌_个交易n后会 l 升 而这也小是我们想要的规则。 h o n g j u n . l u , 提出了 一 种方 式。 这种方 式， 利用n 维数 据的关联规则对于 本问 题进行了 探 讨，1 卜 提出了一种解决方法 这种方法的主要思想是将数据库中的数据按照一定的规则分段，之后， 将关心的信息处 f il l 成事务。f f i 在该n维空问中。下页图是在2 维情况下的一个小例: 第一章 绪论 r311 一 ” : 73 j ” : 黝n;r(下 1; : 一rna ，i - u to “t i莎n 5 et 爹 7 8砂 f1 7 .赢 r .0 i一r一 t 澎 丁 j沙r 浮j “ 鬓 之后。再 每个模式中 找到一个基本位置， 并用关联规则的a p r i o r i 发现方法.来 对模式进行 拓展，最终发现最大n 维关联模式。从而产生如下形式的规则: r 4 : 如果i b m和s u n的股价上涨。则微软的估价很可能 ( 以8 0 %的可能性)在下一天上 涨。 通过这种方式可以得到一定的有用信息，但是。为了使用关联规则，本方法将上涨处理得过 为简单。而使得信息在针对本方法使用前所做的预处理时候，就有了一定的丢失，从而在某些 情况下反而不利于知识的发现. 例如:前止个交易日，a股票均上升i %，而下一个交易日a股票下降5 %，这样的序列在 挖掘和预测的过程中，如果进行事务化， 将被处理成上升的结果。但事实显然并非如此。 表画上看，这种缺点可以用这样的方法来解决:在原方法中，只将达到一定规模的上涨处 理为上涨事务。这可能能很好地解决上面的例子 ( 如:将上涨事务阐值处理为5 %)。但是， 实际上. 这样只是部分地改变了问 题 对于大规模同比 例的情况，该缺点依然存在。而且这样 将一些对总体上升趋势有一定贡献的情况反而忽略掉了，这不是我们希望看到的。 ， . 2 解决方案 针对上 述问 题， 我们提出了 一种用于 表征 趋势移 动模式的q u a n t it a t i v e m o v e m e n t p a tt e rn ( q m p ) 模型。利用该 模型，我们可以将问题的表述更加实用， 而避免了为了使用关联规则而对 信息的损失。 这种方法并小只限于关联规则，在模型建立之后，可以对该模型进行各种数据挖掘分析， 从而得出需要的结果。 利用这种模塑，可以产生这样的结果: r 5 : 过去、当天的各种参数，具有某种形式的股票，在将来的6 0 个交易日内，将最高上涨 3 0 %。上涨时间为2 3 天，其间的最大跌幅可能是 1 0 %. 这里所说的 “ 过去、当天的各种参数具有某种形式”是指该股票参与运算的各种数据， 加上q m p 模型处理过后的一 些参数 ( 包括历史上 涨情况) 实际上，它的形式不同于以上 几 种规则的原因也是，它并没有为了使用关联规则方法，而将数据表征简化。 第一章 绪论 基于 这种模型， 我们建立了 基于该 模型的q m p 数 据挖掘系 统( q m p d m s ) 。 它除了 实现 q m p 的 主要功能外， 还有数据挖掘、 结果 验证 功能，并 附带针对股票 应用的 数 据处理工 具 1 . 3 论文的组织结构 本文对v.个系统做了轶体介绍，给出了原型系统的模块划分和框架流程设计。并对其中的 q m p 模型建立 和实现，以 及q m p 模型在聚类分析上的应用进行了详细的介绍。 文章的整休结构如下: 第一章简要说明了 本文所涉及工 作，即q m p d m s ，产生的原因，提出本系统的必要性。 第 _ 章介绍了 构建原型系统所涉及到的计算机技术:数据挖掘、 聚类分析等， 分别叙述了 这些技术涉及的概念定义，以及常用的方法等。 第二 章给出了q m p 模型的设 计， 实现 算法以 及算法可 靠性证明。 第四章介绍了整个系统的实现和系统结构。 1 ti . 章详细介绍q m p 模型转换部分的实现 第六章中则是基于q m p 模型转换的聚类分析实现研究。 第七章给出了一些实验评测数据以及今后的展望以及研究重点。 第二章系统实现的背景知识 2 . 1引言 本文提出的q m p 模型上的聚类分析是建立在数据挖掘相关知识基础上的，它结合了 聚类分析技术、 数据预处理以及时序挖掘等多 种信息处理技术，从趋势变化的角度分析在 时间上 变化的数据， 提供趋势变化信息知识。 本章将对数据挖掘技术、数据预处理、时序 挖0 1 1聚类分析以 及关联规则分别进行概括性介绍， 给出 它们的基本概念、以及己有的 研 究等，以帮助参考者理解本论文的其他部分。 2 . 2 数据挖掘技术 数据挖掘是从大量数据中提取或 “ 挖掘”知识。i i i 数据挖掘有时也被称为数据库中的 知 识 发 现( k n o w le d g e d is c o v e ry in d a t a b a s e s ， 简写 为k d d ) : 它是 指 提 取隐 含的、 有 价 值 的、事先未知的、潜在的有用信息的处理过程。 数据挖掘的方法有多种，其中比较典型的有: 关联分析 关联分析，是利用关联规则进行数据挖掘。在数据挖掘研究领域。对于 关联分析的研 究开 展的比 较深入， 人们提出了 多 种关 联规则的 挖掘算 法，如a p r io r i . s t e m. a i s . d h p 等算法。关联分析的目 的是挖掘隐藏在数据间的相互关系， 它能发现数据库中形如 “ 6 0 0f 的 顾客在一次购买活动中，购买商品a的同时有8 0 %的可能会购买商品b ” 之类的知识。 序列模式分析 序列模式分析和关联分析相似，其目 的也是为了 挖掘数据之间的联系， 但序列模式分 析的侧重点在 于 分析数据间的前后序列关系。它能发现数据库中形如 “ 在某一段时间内， 顾客购买商品a ,接着购买商品b ，而后购买商品c ，即序列a -b - - c出现的频度较高” 之类的知识。 分类技术 分类在数据挖掘中是一项 i 卜 常it i 要的任务，目前在商业上应川最多 分类的日的是学 会 个分类函数或分类模型 ( 也常常称作分类器)，该模j ， 能把数据库中的数据项映射到 给定类别中的某一个。要构造分类器，需要有一个训练样本数据集作为输入。分类分折就 是通过分析训练集中的数据，为侮个类别做出准确的描述:或建立分析模型或挖掘出分 类规则，然后i i i 这个分类规则对其它数据库中的记录进行分类。 聚类技术 聚类是把一组个体按照相似性归成若干类别，即 “ 物以类聚”。它的日的是使得属7 几 同类别的个体之间的距离尽可能的小，而不同类别上的个体间的距离尽可能的人。聚类 为法包括统计方法、机器学习方法、神经网络力法和而向数据斤的方法采用不同的聚类 第二章 系统实现的背最知识 方法， 对于 相同的记录集合可能有不同的划分结果。 和分类学习相比，分类学习的例子或数据对象 ( 即样本集中的实例) 有类别标记，而 要 聚 类的 例 子则 没 有标记， 需 要由 聚 类学习 算 法 来自 动确 定， 因 此在 机 器 学习中 聚 类 也称 作无监督或无教师归纳。 决策树 利用信息论中的信息增益寻找数据库中具有最大信息量的字段， 建立决策树的一个结 点， 再根据字段的不同取值建立树的分支;在每个分支子集中，重复建立树的下层结点和 分 支的 过程，即 可建立决策树.国际 上最有影响和 最早的 决策树方法是由j . r . q u i n l a n 研 制的i d 3 方法，后人又发展了各种决策树方法，如i b l e 方法能使识别率提高1 0 %. 人工神经网络 模拟人脑神经元方法，以m p模型和 h e b b学习规则为基础，建立了三类多种神经网 络模型:前馈式网络、反馈式网络、自 组织网络。人工神经网络是非线形预测模型，它具 有学习的功能。 遗传算法 模拟生物进化过程的算法，由繁殖 ( 选择)、交又 ( 重组)、 变异 ( 突变)三个基本 算子组成。 遗传算法己在优化计算、分类、机器学习等方面发挥了显著作用。 粗集 ( r o u g h s e t ) 方法 在数据库中 将行元素看成对象， 将列元素看成属性 ( 分为条件属性和决策属性)。等 价关系r 定义为不同对象在某个或几个属性上取值相同， 满足等价关系的 对象组成的集合 被称为等价关系r的等价类。 条件属性上的等价类e 与决策属性上的等价类y之间的关系 分三种情况: ( 1 )下近似，y包含e 。 对下近似建立确定性规则。 ( 2 ) 上近似， y和e 的交非空。 对上近似建立不确定性规则 ( 含可信度)。 ( 3 ) 无关，y 和e 的交为空。 无关 情况不存在规则。 2 . 3 聚类分析 2 . 3 . 1 聚类分析的基本问 题 、聚类的概念 t h e p r o c e s s o f g r o u p i n g a s e t o f p h y s i c a l o r a b s tr a c t o b j e c t s i n t o c l a s s e s o f s i m i l a r o b j e c t s i s c a l l e d c l u s t e r i n g . ( 将物理或抽象对象的 集合分组 成为由 类似的 对象组成的 多个 类的 过 程被称为聚类。)川 对于 一个数据对象集合 ( 例如数据库中的元组集合)，在没有任何指导分类原则的 情 况 卜 ，将数据进行分类 ( 通常是用统计学手段)，就是聚类的主要内容。聚类后的结果是 标注了 类别的各个数据对象。在数据挖掘中 通常使用这些类别信息来进行进一步的处理以 达到发现知识的目的。 聚类的概念包含以下两个关键内涵: ( 一)、聚类，是无指导的 情况卜 将数据对象进行分类。它在概念上不同于分类的最 人地方就是:自不依赖于任何预先定义好的类和实例，而只是根据数据对象本身的特性进 第二章 系 统实现的背景知识 行分类。然而，分类，则是根据预先给定的 类别 ( 人为的或是实验的， 但一定在本次数据 处理之前)分析出数据对象特性和类别的关系，从而达到分析或预测的目的。 ( _)、聚类，是根据数据对象的 特性将类似的对象分为一类，而 将差异程度人的对 象区分到不同的 类中。这样被分为同一类的 数据对象将在特性的意义上具有相似性，而不 同种类的对象在特性上也会有较大的差异。这在处理聚类问题以及评价聚类的结果上都是 有重要参考价值的。 、聚类的应用 聚类作为一个统计学分支，已 经在如卜 领域广泛使用:模式识别、数据分析、图象处 理以及经济科学。 例如，聚类分析可以 应用在，商业上，可以根据顾客的购买数据，总结出购买偏好、 习 惯，以方便经营决策。在地图 观测数据库中分析区域地形的划分。基因工 程中相似基因 片段的提取。期货、股票、外汇市场的分析预测。 三、聚类分析的评价 评价聚类，包含两个概念，一是对聚类分析结果的评价，另一个就是针对应用对聚类 分析本身的评价。卜 面先来讨论聚类结果的评价。 1 .聚类结果评价: 首先，如前所述，聚类分析是将数据对象分类，而分类就意味着，一个类中的数据对 象之间的相似度最人，分属两类的数据对象之间的相似度就要小。因此，一个好的聚类结 果就要达到最大的类内相似度以及最小的类间相似度。 其次，聚类结果的质量还依赖于所用的相似度衡量标准以及具体实现。 最后，聚类的结果发现隐藏模式的能力是最具说服力的标准。 以一 f 是聚类中使用的几种常用的相似度衡量标准: ( 一)、距离: 在很多场合中， 我们使用距离来描述对象之间的差异， 这在直观上是容易理解的，最 常使用的是: 欧几里得距离 ( e u c l i d e a n d i s t a n c e ) :也就是点与点的 距离，下 面是它的严格定义: 设x = (xi, x 2 , . . + x ) 与y - ( y i , y 2 ， 二 ，, y ) 是两个n 维数据对象。 x 与y 之间的欧儿里得距离 d ( x , y ) = ( ix 一 y j z + ix z 一 y iz + + 、 一 y x ) v a 另一种也非常有名的度量方 法是曼哈坦距离 ( m a n h a tt a n d i s t a n c e ) :也就是对应维差的 绝 对值的和，严格定义如 卜 : 设x = ( x i , x 2 , . . ， x . ) 与y = ( y i , y z , . ， y . ) 是两个n 维数据对象。 x 与y 之间的曼 哈坦距离 d ( x , y ) = ix , - y l + ix , 一 y 十. . + ix n 一 y ,j 明考斯基距离 ( mi n k o w s k i d i s t a n c e ) ,是从以上两种距离总结出的概化形式: 设x = ( x i , x 2 ,， 、 ) 与y = ( y i , y z , . . . ， y d是两个n 维数据对象。 x 与夕 之间的明考斯基距离 d ( x , y ) = ( ix , 一 y “ + ix z 一 y 2 i ” + . . . + ix一 y n i i , 9 e n 也可以白己定义距离函数，但要注意距离要满足的条刊: k it 仟( n l ;i f 离和仟意合法的数据对象x . v , z ，有: 第二章 系统实现的背景知识 d (x , y ) - 0 ; d (x , x ) = 0 ; d (x , y ) = d ( y , x ) :以 及二角不等 式: d ( x , y ) + d ( y , z ) % d (x , z ) 。 在实际 应用中，对于 各种数值型属性， 度量单位的选取和具体值的分布可能对对象之 间的距离造成很大的影响 具体内容就不在此处讨论了 为了减少这种不利因素，可以在之前进行标准化。限于篇幅， ( 一)、簇中心距与簇直径: 这两个参数主要是用于评价簇的好坏的: 簇中 心 距( c e n t r o id d is t a n c e ) : 簇中 各 对象与中 心点 的 距离的平均 值。 设c ; 是第i 簇， c 为该 簇中 心点， 则c . 的 簇中 心距为: a v g ( d (p , c ) i p e c . ) ) 簇直径:簇中对象的最远距离。 ix c ; 是 第1 簇，则c . 的 簇直 径为: m a x ( d (p l , p 2 ) i p l , p 2 e c , ) 以上两个参数值越大，表明该簇之间相似程度越低。 2 .聚类分析评价的几个方面: 一 般地讲， 对于 一个聚类方法的 好坏， 可以 从以 下方向给予衡量: t ) . 可伸缩性:一个好的聚类方法， 应该可以 在大数据量的时候具有较好的时间复杂度 井保持聚类结果的有效性。 2 ) . 处理不同 类型属性的能力:基于非数值类型 属性的数据在现实生活中是常有的，而 一个 好的聚类方法应该能处理多种类型的数据。 3 ) . 发 现任意形状的聚类:实际 应用中 有时需 要发 现非圆 形 ( 多维球型) 的 簇， 所以 聚 类方法发现此种簇的能力在某些情况卜 也是十分重要的。 4 ) . 用于 决定输入参数的领域知识最小化:不光是聚类，也包括其他数据挖掘部分，应 该作到用户的 最小参与， 具体讲有两个方面:一、要求用户对聚类的具体知识尽可能少; 二、 要求算法或结果不要对用户参与的数据过于敏感。 5 ) . 处理躁声数据的能力:由于 孤立点的出 现，有时会影响某些聚类算法的结果，这个 能力就是衡最聚类方法屏蔽躁声的能力。 6 ) . 对于 输入记录的顺序不敏感:由于 聚类的对象之间不应该有序，也就是说， 无论哪 些数据对象先处理，哪些数据对象后处理，所得出的聚类结果应该是基本相同的。好的聚 类方法不应该对对象的处理顺序过于敏感。 7 ) . 高 维 性: 聚类方法在多 维 情况下 应该依 然保持结果有效性。 8 ) . 基于 约束的聚类:聚类方法能够处理根据具体的应用加入约束的数据，并在该约束 卜 产生聚类结果。 9 ) . 可解释性和可用性:聚类甚至数据挖掘所得的结果应该是为了帮助发现知识， 所以 聚类结果的可解释和可用就是最实际的指标。 2 . 3 . 2 主要聚类技术 土要的聚类算法分为以f 儿类:划分方法、层次的方法、基于 密度的方法、基于网格 的方 法、基于 模型的方法。由丁 本部分土要是为了 给后文做知识基础铺垫， 其中与 后文关 系不大的方法只是简单介绍。 、划分方法 划分方法基本思想是给定类数目k .采用某种相似度做为划分原则，使得类内相似度 址r ; 而类外相似度最低。 第二章 系统实现的背景 知识 在其中比较经典的k - m e a n s 算法中， 代表一个类的是簇对象中的平 均值。其结果使平 方误差准则最小。 1 . k - m e a n s 方法: 卜 面是k - m e a n s 算法的步骤: 1 ) . 随机选择k 个初始簇中心对象; 2 ) . 将每个对象和它最相似的 簇中心归属为一类; 3 ) . 重新计算每簇的中 心，再 根据簇中 对象的 平均 值， 进行上一步，直 到 不再 发生变化。 它的缺点是:k 的确定需要用户参与、存在数值型局限、复杂度大、以 及对孤立点敏 感 针对以上缺点k - m e a n s 又产生了许多变种，另外，针对不同的需要， 对k - m e a n s 的改 进也可以是下 面三个方向: 初始k 个平均值的 选择、相异度的计算、计算聚类平均值的策 略。 先用层次的凝聚算法决定结果簇的数日 ，并找到一个初始的 聚类，然后用迭代重定位 来改进聚类结果。 ( 也可以用密度方法确定数目) 它是解决k 问题的一种方法。 2 .k 一 中心点方法: k 一 中心点方法改善了 新中 心，从而减轻了 对孤立点的 敏感性。下面是k 一 中 心点方法的 简单描述: i )随机选择k 个初始簇中心对象; 2 ) 将每个对象和它最相似的簇中心归属为一类: 4 ) 随机地选择一 个新的中 心点 a o m 5 ) 计 算 用o . a o m 代 替q的 总 代 价s ; 6 ) 如 果s 0 ， 让o - a o m 替 换q ， 形 成 新的k 个 中 心 点 ; 7 ) 重复步骤2 )，直到不再变化; 心 ， 较 好 其中的s 为平方一 误差值。 o是考虑被替换的中心) 在k 一 中心点算法替换后， 。这种算法的一个实例是 点的归属原则 ( 总是归属于近的中 p a m. k 中心点的特点是聚类效果 ，受孤立点影响较小，但复杂度较大 3 . c l a r a和 c l a r a n s 方法 c l a r a和c l a r a n s 是为了 解决复杂度问 题而提出的，主要是针对大型数据库的应 用。 它们的主要思想是利用样本来降低计算的基数。 c l a r a是对多 个样本使用p a m算 法，再 选抒效果最好的一个结果作为输出。而c l a r a n s 则是在每一步针对一个不同的打 本，再通过一个轮廓系数，定义对象属于某簇的概率，这样就能发现更加 “ 自 然”的结果 簇数 目。 为了解决k - m e a n s 系的复杂度问 题，也有内存处理措施:思想是，密集点可以压缩 而稀疏点可以废弃，这样就只在内存中保留那些既不可废弃又不可压缩的点 、层次方法 层次方法将数据对象按树的方法进行处理，按照处理次序的不同，分为凝聚的层次聚 类以及分裂的层次聚类 第_章 系统实现的背景知识 凝聚的层次聚类:先将每个数据对象作为簇，自 底向上，合并原子簇为更大的簇，直到所 有对象都在一个簇中，或者某个终结条件被满足。 分裂的层次聚类:先将所有数据对象作为一个簇，自 顶向卜 ， 细分直到对象白 成一簇，或 达到某 个终结条州为i i : ( 例如， 簇数目， 或两个最近的簇之间的 距离 超过某个ip-m j 值) 。 b i r c h方法 层次聚类的一个代表算法是b i r c h .在b i r c h中， 使用一种c f - t r e e 的结构。 c f =倒， l s , s s ) 其中: n是子类中点的数目， l s 是n个点的线性和，s s 是数据点的平方和。 b i r c h的构建止是依据c f 中信息对簇的代表性:利用子簇核算主簇时，信息的完备 胜;以及新点加入时， c f 树中的信息对新点分支的指导性设计的。以下是b i r c h方法的 步骤: 阶段一:建立一个存放于内存的c f 树，它可以被看作数据的多层压缩;扫描数据库，增 量构造c f 树，试图保留数据内在的聚类结构。当叶子节点中的子聚类直径大于1a 7 值，则 采取分裂措施。直径根据内存需要计算。分裂和树的维护依据r * 树 ( 一种多维空间索引方 法) 来进行。当内存超出时， ( 通常约为内存的一半) 将定义一个较小的阂值来重建c f 树。重建的过程只需要从旧 树的叶子节点进行， 而不需要重读所有的 对象 ( 因为信息已 经 收集过)。 阶段福:采用某种聚类算法对c f 树的叶节点进行聚类。 在 b i r c 日中，还有一些处理孤立点和改进c f 树质量的方法。比如，增长比较慢的 c f ij 点，会被放弃或是放到外存中。之后再根据情况进行调入处理。 b i r c h方法的主要缺点是，簇必须是球型或近似球型。 三、基于密度的方法 因为聚类结果簇都是有多 个点存在的密集区域，因此，基于密 度的方法，可以发现高 密度区，并将其或其的联合定义为簇。它可以发现非球型的区域。 1 . d b s c a n方法 d b s c a n ( d e n s i t y - b a s e d s p a t i a l c l u s t e r i n g o f a p p l i c a t i o n s w i t h n o i s e ) 可以在带有“ 噪 声”的空间数据库中发现任意形状的聚类。这里的簇定义为密度相连的点的最大集合。 先来看一些基于 密度的定义: p 数据对象周围半 径e 内 的区 域称为该 对象的。 一 邻域( 。n e ig h b o r h o o d ) o 命 如 果一 个对 象的: 邻域包含超过m in p t s 个 对象， 则 称该 对象为核心对象( c o r e 0 衍 e c t ) o 个 对于 一 个对象的 集合d ， 如果p 是在。 的。 邻域中 ，且。 是一个核心对象， 我们说对 象p 从 对象。 出发是直 接密 度可 达的。 o 如果 存在对 象p i, p a , -1 n , p i- 0 , n n p ， 对p + 属于d , ( 1 i - m i n p t s 否则，c o r e - d i s t a n c e , ,m ,n 1 , ( p ) 无定义。 这里的 n e ( p ) 指落在n e ( p ) 中的 对象数目 。 设p 与。 为 数据库d的 一个对 象， n ,( o ) 是。 的。 一 邻域， m in p t : 是一个自 然数， 一个 对 象p 关于。 的 可达距离 r e a c h a b i l it y - d i s t a n c e ,m ,p tt( p , o ) = m a x ( c o r e - d is ta n c e , , ; , ( o ) , d i s ta n c e ( o , p ) ) ， 如果 c a r d ( n e ( p ) ) )mm p t s 否则， r e a c h a b il i t y - d i s t a n c e , ,m ; m ( p , o ) 无定义 。 o p t i c s 根据上述两个指标对数据库中对象按照次序进行处理。额外存储了侮个对象 的核心距离和一个适当的可达距离。再 根据o p t i c s 产生的次 序信息来抽取聚类。这样， 就可以优先处理那些密度大的部分，而将相关的对象首先聚成簇。 四、基于网格的方法 / 基于网格的方法的主要思想是将多维空间划分成为网格单元，根据其中的数据单元数 目进行处理。主要有以下方法: 1 . s t i n g统计信息网格: 将空间分成正方体，侮个低分辨率的高层正方体单元再分成高分辨率的低层正方体单 元之后，计算并利用每个正方体中数据对象的统计信息，将相关单元归类，如果无法归 类将按照某种规则新建该类。 2 . c l i q u e ( c l u s t e r i n g i n q u e s t ) c l i q u e 将基手 密 度和基手 网 格的 聚类方 法综 合起来， 特点是 速度快。 它的思想为: 给定一个多 维数据点的大集合，数据点 在数据空间中通常不是均衡分布的。 c l i q u e 区分空间中稀疏的和 “ 拥挤的”区域，以发现数据集合的全局分布模式。 如果一 个单元中的包含数据点超过了 某个输入模型参数，则该单元是密集的。在 c l i q u e 中， 簇被定义为相连的密集单 元的最大集合。 . 第章 系统实现的背景知识 c l i q u e 方法的r 作步骤: 1 ) . 将n 维数据空间 划分为长 方体单 元， 在侮一 维找到 其中的 密集单元。以 这些密 集单元 的相交子空间形成的候选搜索空间维基础，查找高维密集单元。 2 ) .为每个簇生成最小化的描述。 在步骤 i 中 维必是密集的。 ， c l i q u e 所依据的先验 ( a p r i o r i ) 性质是:在k 维上的密集区域，在k - 1 由于 这条 先验性质 使 得c l i q u e 和关联规则 挖掘方法有 着类似 之处， 但 它们还是有所不同的:c l i q u e由于 是聚类方法，不需要预先的数据离散化辅助。 五、基于模型的方法 模型的方法认为数据是按照某种潜在的概率分布形成的。 这种方法一般是通过优化数 据与模型间的适应性来实现聚类。主要分两类:统计学方法与神经网络方法。 1 .统计学方法: c o b we b 是一种统计学方法。 它用一种基于概率的分类效用函 数来划分节点，再根 据类内相似性以及类间相异性来判断新成员的类属。 2 .神经网络方法: s o m是一种神经网络方法。在s o m中，单元之间互相竞争，最终存活 ( 激活)的组 成的是要分出的簇，其他的视为散点。这种方法被认为是模拟大脑的处理过程。 第三章 q mp 模型研究 3 . 1 问题的提出 含有数量i l 属性的时序数据库在经济领域以及科学决策领域中应用很 一 。传统的时间 序列方面的 研究都是针对序列的形 状， 来发 现形状相同 或类似的 序列，再利用知识挖掘的 方法，来发现序列形状中所蕴涵的知识。它主要应用于以下的方面:l i l 2 3 i .发现哪些公司具有类似发展模式; . 确定哪些商品具有类似的销售模式; .找到具有类似的价格增减情况的股票。 而在实际应用中，人们时常关心的是时 序数据的 趋势以 及时序数据在某段时间的 变化 幅度，如果采用前面的方式，对时间序列进行过于细致的描述，就会丢失某些趋势的相似 关系，并且也会造成资源的浪费。 在h . l u 的论文中， 提到了 一种发现知识的方法， 它将各 种序列上的增长 和非增长处理成事件，例如:a增长，为事件a发生，b不增长，为事件 b 不发 生 15 1!6 1。而 这样描述， 又 对趋 势的 描述过于 粗糙。 针对上 述问 题， 我们提出了 一 种新 型的 模型q m p ， 它可以 表征时间 序列中 的数据变 化 趋势，在此模型上利用现有的数据挖掘方法可以 挖掘出数据变化趋势模式之间的关系。 q m p 的土要思想是: 对于 在时间序列中的一个元素，求出它对于之前， 之后的最值 ( 四个)的改变幅度，这样做的好处在于: .如果对每个元素直接求与固定距离位置元素的改变幅度，而不考虑一段时间区 间的效果，对于某些数据， 不能够表达序列中元素的真正的增长幅度。而采取 了q m p 中的方法，由于 是发现其中的最值， 就不会受到这种干扰。 . 求出的改变幅度的同时，还可以求出 元素与 这些最值间的距离，也可以 根据这 些最值的位置， 在原始数据库中，同时计算出 这个元素与最值间其他属性的改 变情况，以用于知识的发现。 .可以对于 某一个时间粒度，找出大的趋势，自 动排除小的波动的干扰。 .变成涨跌幅后，各种不同数量级的数据之间就有了可比性，可以发现其中潜在 的规律。 3 . 2 q m p模型描述 在时序数据库中， 挖掘布尔型 属性 ( 或通过分类、聚类等手段转化成布尔型属性) 之 问相互关系的研究己有许多成熟的技术和方法，而对于挖掘数量型属性数值变化趋势相互 关系 的 研究 却很少见。以卜 提出了 一 种 数量型 属性变化趋 势的 研究 模型q m p ( q u a n t i t y 第二章 q m p 模型研究 也就是说，如果同时存在多 个等值的最小值， 所取到的最小元素， 将是它们中间那个 在序列中位置最靠后的一个。 3 .2 .4 模型实现的算法研究 、朴素的原始算法 为了寻找m ( i ) ， 人们很容易想到这样一种原始算法: 既 然rq 个m ( i ) 都是搜索窗口 中的 最小 值， 那么 对于 每一 个 搜索窗口 ， m ( i ) 就是 它的 最小 值 所在的元素。因此，可在每个元素的搜索窗口中查找最小元素， 它的时间复杂度为o ( w ) 对于长 度为n 的 序列s ,总 共的时 间复杂 度就是。 ( 。 、 ) 。 这个算法的缺点在于:它忽视了搜索窗口 之间的关联性。当搜索窗口向前滑动的时候，人 量己 经比较过的元素会再次被当作新的元素进行重新比较， 这样就减低了效率。 实际上相邻的搜索窗口 。 - h w( i ) 与 。 - h w( i + l ) 之间存在这样的关系: w - h w ( i ) 2 ,w = c o - h w ( i + 1 ) l ,w - i , 因此，从、 到i + 1 搜索窗口实际上经历了这样一种变化:将搜索窗口的首元素去掉，而在它 的末尾加上新的元素。很显然，这样的操作可以由一个这样的队列来表示:搜索窗口的 序 列 靠近f i r s t ( cil - h w ( i ) ) 的一 方是队列 的头， 元素 从这里 被取出 队 列 而靠 近la s t ( ca - h w ( i ) ) 的 一方则充当 队列的 尾， 元素 被从 这里 加进 来。下 面的m in - s in g l e 算 法就是 采用该 种处理方 式 二、 m in - s i n g l e 算法 该算 法的主要思想是:在处理。 - h w ( i ) 时先计算出 最小 值并记录它在队列中的位置，当 队 列更新时，先比较新加入的结点和原最小值:如果新加入的结点大于原最小值，并且原最 小 值没有被移出队列的话， 新的搜索窗口 的最小值就不用更新; 如果新加入的元素确实小 于 或者等于 原来的最小值，那么， 新来的元素将成为新的最小值，我们称其为最小元更 新。在某些情况下，会出现连续多个搜索窗口 使用同一个最小元，而不发生最小元的更 新， 甚至到这个共同的最小元要被移出搜索窗口 的时候， 最小元仍不会更新，我们称其为 最小元死亡。当最小元死亡的时候，必须重新计算搜索窗口中的最小元。 这种方法的优点是，如果最小元在死亡之前能够及时地被更新，对于每一个搜索窗口，时 间复杂 度仅为o ( 1 ) 。 但是当 最小元没有及时地被更新， 而发生了 最小元死亡的时候，就必 须重新计算搜索窗口中的最小元，它的时间复 杂度是。 ( 。 ) 。所以，这种算法的平均复杂度 为: o ( n * ( p * w + ( i - p ) ) ) ， ( 设最小元死亡的概 率为p , n 是要处理的 搜索窗口 数) 。 而 最坏的时间复杂 度是o ( n * ( o ) ， 即p = 1 时。 此时和原始算 法的复 杂度一样。 上述算法的缺点在于，每次当最小元死亡的时候，需要重新计算最小