（计算机软件与理论专业论文）基于模式聚类的理论研究.pdf

摘要 摘要 在基因微序列分析等应用中，传统以距离为相似度计算依据的聚类方 式并不适用，因为有时对象与对象之间不具有相近的物理距离，但却存在 有相似的一致性模式。因此，基于模式的聚类方法( p a t t e r n - b a s e dc l u s t e r i n g ) 简称为“模式聚类”，被提出来解决此类问题。判断两个对象是否同属一 p c l u s t e r ，取决于他们属性中的子集是否具有一致性的模式。当前模式聚类 算法的研究只是停留在一般化描述，并没有上升到系统理论层次，缺乏严 格的形式化定义。另外，现阶段算法都是基于特定的等差或等比模式，而 对于其他模式却不能够很好的适用。 本文对模式聚类各种算法模型进行深入探讨与分析，总结其共性及特 性。在理论研究方面，首先从模式的多样化角度进行了分析，对模式出现 的类别及特征进行了概括总结，并提出了单模式模型及多模式模型的概念。 从模式的多样性和共性出发，总结了模式的通用定义和形式化表示方法。 引入了一个具有普遍意义的模式算子来表示模式，并从算子的角度归纳总 结各个模式聚类模型的一致性规则表示并进行分类。引入了同型算子和基 于算子的模式的概念，以算子的特性研究为基础，研究模式聚类各类运算 的性质和特征。在算法研究方面，本文提出了一种新的模式聚类改进算法 o s m 算法，与原有模式聚类算法比较，此算法具有更好的时间效率。 关键词数据挖掘；子空间聚类；模式聚类；模式算子；聚类 燕山大学工学硕士学位论文 a b s t r a c t f o r8 0 m ea p p l i c a t i o n ss u c ha sd n am i c r o a r r ya n a l y s i s t r a d i t i o n a l c l u s t e r i n gm e t h o d st h a tw o r k e do u tt h es i m i l a r i t yb yd i s t a n c ei s n o ts op r o p e r b e c a u s es o m e t i m e st h e r ed o e s n te x i s ta p p r o x i m a t ed i s t a n c eb u tac o h e r e n t p a t t e r n t h e r e f o r e ，ab r a n d - n e wc l u s t e r i n gm o d e l ：p a t t e r n - b a s e dc l u s t e r i n g ，w a s p r o p o s e dt o s l o v et h i sp r o b l e m t w oo b j e c t si nt h es a m ec l u s t e ri sd e c i d e d w h e t h e rt h es u b s e t st h e yb e l o n gt os h a r eac o h e r e n tp a t t e r mr e c e n t l yt h es t u a y o fp a t t e r n - b a s e dc l u s t e r i n gi sm e r e l yh a v ee c u m e n i c a ld e s c r i p t i o n sb u td i d n t h a v es y s t e mi n f oa n dl a c k sp r o p e rd e f m i t i o u s f u r t h e r m o r e ，c u r r e n tc l u s t e r i n g a l g o r i t h m sm o s t l yb a s e do l ls p e c i f i cs h j f t i n g o rs c a l i n gp a t t e r n s ，b u tc a nn o t c a p t u r eo t h e rp a t t e r n sp r o p e r l y t h i sp a p e rm a k e sd e e ps t u d ya n da n a l y s i so fd i f f e r e n tp a t t e r n b a s e d c l u s t e r i n gm o d e l s ，s u m m a r i z e st h e i rc o l l l n l o n n e s s a n dd i f f e r e n c e s f o rt h e s t u d yo ft h e o r y , f i r s to fa l l ，m a k e sm u l t i f o r t u i t ya n a l y s i so fd i f f e r e n tp a t t e r n s a n dt h e i re x p r e s s i o nf e a t h e r s ，t h e np r o p o s e dt h ed e f i n i t i o n so fs i n g l e p a t t e m m o d e l sa n dm u l t i - p a t t e r nm o d e l s f r o mt h ec o f m n o b n e s sa n dd i f f e r e n c e so f p a t t e r n s ，t h ee o n l m o nd e f i n i t i o n a n df o r m u l ad e s c r i p t i o no fp a r e r na l e s u m m a r i z e d t h e nag e n e r a ls y m m e t r i c a la r i t h m e t i co p e r a t o ri sp r o p o s e d b a s e do np r o p e r t i e so ft h i sa r i t h m e t i co p e r a t o r , as t u d yo fc l u s t e r i n go p e r a t e p r i n c i p l ei sp r o c e s s e d a tl a s t , f o rt h es t u d yo fa l g o r i t h m , w ep u r p o s e dan e w p a t t e r n - b a s e da l g o r i t h mc a l l e d0 - s m , w h i c hi sm o r ee f f i c i e n ta n dp r e c i s et h a n p r i o ra p p r o a c h e s k e y w o r d sd a t am i n i n g ；s u b s p a c cc l u s t e r i n g ；p a t t e r n - b a s e dc l u s t e r i n g ；p a t t e r n a r i t h m e t i co p e r a t o r ；c l u s t e r i n g i i 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于模式聚类的理论研 究，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研究工 作所取得的成果。据本人所知，论文中除已注明部分外不包含他人己发表 或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体，均 已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签字召名驽 日期：知1 年弓月泊 燕山大学硕士学位论文使用授权书 基于模式聚类的理论研究系本人在燕山大学攻读硕士学位期间在 导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所有，本 人如需发表将署名燕山大学为第一完成单位及相关人员。本人完全了解燕 山大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送交 论文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山大学， 可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部 分内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密阢 ( 请在以上相应方框内打“4 ”) 作者签名：马倘 日期：芸。司年) 月蛹 导师签名：日期：a 。1 年3 月f 珀 锋 第1 章绪论 第1 章绪论 随着电脑科技的发展与应用，数字化信息的积累非常快速。以往，虽 然可利用数据库管理系统来帮忙有效地查询与管理这些数据，但在一般情 况下，数据库管理系统却无法将既有的数据归纳或分析出有用的信息或知 识。因此，如何从数据库中挖掘有用的知识，便成为现今一个重要的课题。 其中最为广泛研究及应用的技术，即为数据挖掘技术( d a t am i n i n g t e c h n i q u e s ) 。数据挖掘融合了统计分析及模块化的方法，并加入了许多创 新且独具巧思的方法论，使其具有更广泛的应用价值，更容易找出隐藏在 大量数据集中的模式( p a r e n a ) 及关联性( r e l a t i o n s h i p s ) ，并可以进一步将这 些关系转化为有用的信息或知识。大致上，数据挖掘技术可被分为五大类； 分类( c l a s s i f i c a t i o n ) 、评估( e s t i m a t i o n ) 、预钡l j ( p r e d i c a t i o n ) 、关联分组( a f f i n i t y g f o u p i n g ) 和聚类( c l u s t e r i n g ) u j 。 聚类是数据挖掘中重要的技术之一，聚类的技术亦被广泛的应用在各 种领域上，如统计，机器学习，回归分析，图像处理及基因分析等。聚类 的主要做法是将数据集中的对象( o b j e c t s ) ，利用适当的聚类运算法比较对 象间的相似程度来分组成数个群( c l u s t e r s ) 的过程。聚类是一种非监督式的 学习过程，并没有预先设定的类别，所建立的模型也没有先决的特定目的， 只是将具有共同相似性特征的对象集合成群。 1 1 模式聚类简介 传统的聚类方法可分为：划分的方法( 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 ) 、基于网格 的方法( 鲥d b a s e d m c t h o d ) 和基于模型的方法( m o d e l - b 嬲e d m e t h o d ) 口埘。而本 课题所探讨的聚类方法有别于上述五个类别，称为基于模式的聚类方法 ( p a r e n a b a s e dm e t h o d ) ，简称为模式聚类。基于模式的聚类法最早在2 0 0 2 1 燕山大学工学硕士学位论文 年被提出，不同于以往以距离为计算基础的聚类法，它以平均平方差的公 式为主轴，计算出对象与对象在不同属性间的一致性( c o h e r e n t ) ，将具有一 致性的对象及属性自数据库中提取出来成为一个群，这样的群被称为 p a t t e r nc l u s t e r ( 简称为p c l u s t e r ) 。 近来，数据挖掘的重点放在了在大型数据库中，对有效及有效率的群 进行分析的方法上。很多活跃的研究都投入到了诸如聚类方法的可测量性 及多维聚类技术等领域上1 4 。】。 在多维空间上的聚类常常很棘手，在大量数据集中的聚类方法由于数 据复杂度高，每一对象或是属性值的改变都会造成聚类结果的巨大差异， 因此聚类的结果常带有些不确定性【7 l 。近来也有些研究【1 1 探讨对多维数 据库子空间中潜在的簇的发现，即子空间聚类的研究。 多数聚类模型，包括那些应用于子空间聚类的模型，往往利用每个维 或一组维的子集之间的距离来定义不同对象之间的相似性，常用的距离函 数包括欧几里德距离，余弦距离等。然而，距离函数在获取对象间相关性 并不是总能适用的。事实上，即使一组对象利用距离函数度量时距离彼此 相距很远，他们之间也可能存在强相关性。这可以在图1 1 ，图1 2 及图 1 3 的例子中表现出来。 8 0 6 0 罟 4 0 2 0 0 ab cdcf g h a 蛐m e s 图1 - i 三个对象在8 个属性上的表现数据 f i g 1 - 1r a wd a t a ：3o b j e c t sa n d8c o l u m n s 图1 1 中展现了有3 个对象和8 个属性的一组数据。从表面看，这3 个对象之间没有直接可见的模式存在。然而，如果取属性的一个子集，如 属性子集 3 0 2 0 1 0 0 ce g a t t d b u t e s 图1 2 图卜1 中三个对象在属性子集 a ，c ，e ，酚上表现出等差模式 f i g 1 - 2o b j e c t si nf i g u r e l 一1f o r mas h i f t i n gp a t t e r ni ns u b s p a c e a ，c ，e ，g 同样一组对象在不同属性上可以表现出不同的模式。在图1 3 中选取 了另外一组属性子集 b ，d ，f ，h ) 。这次，三条曲线没有了等差的关系，对象2 的属性的值比对象l 大了将近3 倍。对象3 的属性值又比对象2 大了将近 2 倍。如果考虑属性b , d ，f , h 作为不同的环境或条件，那么这种模式表明了， 这3 个对象对这些条件会表现出特定的一致性趋势。显然对象3 对刺激的 反映比其他两个更敏感。模式聚类的目标即是从像图1 1 中的源数据集合 中发现像这样等差或等比的模式。 7 0 6 0 5 0 4 0 3 0 2 0 1 0 0 bdfh a t t n b u t c s 图l - 3图l l 中三个对象在属性子集 b ，d ，f ，h 上表现出等差模式 f i g 1 - 3o b j e c t si nf i g u r e l 1f o r mas c a l i n gp a t t e mi ns u b s p a c e b ，d ，h 3 燕山大学工学硕士学位论文 模式聚类( p c l u s t e r ) 模型可以被应用在许多方面：如基因工程中，可找 出具有相同行为反应的基因组。或在电子商务中，分析出具有相同喜好的 顾客群等。而解决p c l u s t e r 这类问题最早的是由h a i x u nw a n g 等人在2 0 0 2 年所提出的p c l u s t e r i n g 法1 1 2 l 。 1 2 模式聚类的研究现状 模式聚类法最初是应d n a 序列分析的要求而产生的。c h e n g 等人在 2 0 0 0 年提出的b i c l u s t e r ”1 概念可说是p c l u s t e r 的前身。b i c l u s t e r 主要用来 度量在一个d n a 的子矩阵中对基因及条件的一致性。不同于以往以距离 为度量标准的聚类法，它使用了平均平方差的计算方式在作为聚类的基础。 一个随机算法被设计出来用以发现一个d n a 序列中的这些群。 y a n g 等人提出了一个更有效的算法： i - c l u s t e r 澍1 4 】，能够很快且有效 的找出b i c l u s t e r ，避免了b i c l u s t e r 无法找出群和群重叠的问题，也能同时 找出多个群。但是它们仍以平均平方差作为相似度计算标准，所找到的群 会有误差存在。 h a i x u nw a n g 等人在2 0 0 2 年提出了p c l u s t e r 概念，以p s c o r e 取代了 平均平方差的计算方式，有效解决了之前两个方法所遇到的问题，同时也 能够正确有效的找出所有隐藏在数据集中的p c l u s t e r 。p c l u s t e r i n g 法，主 要利用对象与对象间相互对比以及属性与属性间的相互对比，找出可能存 在的模式，再由对象和属性组合成一个群。这种方法必须对对象和属性进 行两两对比，在处理大型数据集时需要大量时间。 其后j i a np e i 等人在2 0 0 3 年提出了m a p l e 算澍”1 ，对p c l u s t e r 的缺 点进行了改进，进一步提高了算法的效率。 针对时间及空间上的节约问题，后来又有一系列的方法和算法被提 出，如s e q c l u s t e r 法i l6 j 等。 也有很多其他的不同模式聚类模型被提出：如l i u 和w a n g 等人利用 对属性在数值上以升序排序来定义模式1 1 。”。j i a n g 等人利用最小相关界限来 约束条件组中的一致性1 1 ”。 4 第1 苹绪论 当前的聚类研究成果有很多，但仍然存在着下列一些问题。 ( 1 ) 当前的模式聚类研究成果，算法的研究只是停留在一般化描述，并 没有上升到系统理论层次，缺乏一个严格的形式化定义。 ( 2 ) 虽然有一些聚类的思想和法则被提出，但是缺乏必要的形式化描述 和理论上的证明。 ( 3 ) 另外，现阶段算法都是基于特定的等差或等比模式，而对于其他模 式却不能够很好的适用。这就使得算法本身的改进和扩展方面有了很大的 局限性。 因此，一个通用的，系统的模式聚类理论模型需要被建立起来，以此 为模式聚类的继续研究提供必要的理论依据及描述标准。这也是本课题的 重点研究任务。 1 3 课题的主要研究内容及论文的组织结构 本课题要重点研究和解决的内容：定义一个具有普遍意义的对称性算 子来表示模式，以算子的特性研究为基础，探索研究具有通用性的模式聚 类的理论模型。 ( 1 ) 在之前的研究中，对模式聚类中最重要的“模式”的研究，只局限 于等差或等比的形式，或者单纯在数值上的差异，事实上，高维数据集中， 对象集可能在属性集上表现出许多其他类型的模式，而且可能多种类型的 模式在同一数据集上可以同时表现。而先前的研究，只考虑等差或等比类 型的模式，并且聚类算法只能处理一种单一的模式。将模式扩展开来，模 式多样化分析，是本课题研究的一个主要内容。 ( 2 ) 当前，对模式的相似性函数定义各个算法都有不同的描述。同时， 对于“模式”的描述和操作各个算法也是各自为政。不同的模式需要同一 的一个普遍和概化定义来描述，而且不是简单的一般化描述，而是系统的 形式化定义，要求这个定义具有普遍性，这是当前此研究领域的一个空白 点，也是本课题要做的第二个工作：对模式定义的通用的形式化描述。 ( 3 ) 本课题设计定义一个算子来表示“模式”，并对这个算子的性质进 5 燕山大学工学硕士学位论文 行系统化的分析证明，使得对模式的聚类操作在理论上更具有可行性，通 过对算子特征的分析，探索性建立模式聚类的系统理论模型。总结出一个 通用的，有效的聚类算法，是本课题要做的另一重要探索性尝试。 本文总体上分为5 章，从第2 章开始具体布局如下。 第2 章将介绍模式聚类的相关研究工作，包括对一些经典聚类模型如 b i c l u s t e r , p c l u s t e r i n g ，o p c l u s t e r i n g 的大略介绍和分析。 第3 章为模式聚类的理论方面研究，包括模式多样化分析，模式算子 定义，模式算子性质及模式聚类运算法则。 第4 章将提出一种新的模式聚类改进算法，o - s m 方法。 结论及未来研究方向。 6 第2 章相关研究 第2 章相关研究 传统的聚类方法多以距离作为相似度计算的基础，如果将这些方法用 来处理基于模式的聚类问题就显得不恰当，而找出的结果也会出现问题。 本章将重点探讨基于模式的聚类技术以及一些经典算法模型。 2 1b i c l u s t e r 及8 - c l u s t e r c h e n g 等人提出了b i c l u s t e r 【4 】的概念可说是p c l u s t e r 的前身。b i c l u s t e r 主要是在一个d n a 的阵列中找出具有一致性的基因及情况。而它使用了 平均平方差的计算方式作为聚类的基础。公式如2 一l 所示。 假设x 代表基因( 对象) ，y 代表各种试验情况( 属性) ，i 属于x ，j 属 于y ，如果h ( i ，j ) 6 ( 6 为界限值) ，则称a u 为符合一个b i c l u s t e r 条件的群。 y a n g 等人提出了一个有效的算法：8 - c l u s t e r 澍1 4 1 ，能够更快且更有效 率的找出b i c l u s t e r 。从一个随机选择的起点开始，不断的重复执行改善群 的品质，直至得到最佳聚类品质。避免了b i e l u s t e r 无法找出群跟群重叠的 问题能同时找出多个群，但仍是以平均平方差来作为相似度的计算，所以 当遇到数据中存在噪音( n o i s e ) 的情况，就使得聚类的结果不尽理想，同时 还需要预先输入聚类数为参数。 f - c l u s t e r 和b i c l u s t e r 所找的群会包含原本不属于此群的对象或属性， 若这些对象或是属性以平均平方差的公式验证，将无法满足小于等于界限 值6 的条件。换句话说，找出来的群会有误差存在，与本文所讨论的模式 聚类方法所得出的结果并不相同。 7 兰盱，招豢 眦 驴 燕山大学工学硕士学位论文 2 2 p c l u s t e r i n g h a n x a nw a n g 等人在2 0 0 2 年提出了p c l u s t e r 的概念，以p s e o r e 取代 了平均平方差的计算方式，有效的解决了之前两个方法所遇到的问题，如 噪音问题及群重叠问题，同时也能够正确的找出所有隐藏在数据集的 p c l u s t e r 。 设d 为一个对象集合，其中每个对象都被一个属性集a 描述。o 为数 据库中对象的子集，o 属于d 。t 为属性的子集，t 属于a 。元组( o ，t ) 为 一个子矩阵。给定x , y e o ，a , b t ，定义这个2 x 2 矩阵的p s c o r e 为： p s c o 旭( 乏2 州叱一如，一c 叱一如，l c z q 如果对于任何于一个( o ，t ) 中的2 x 2 的子矩阵x ，都有p s e o r e ( x ) ，砭0 ， 那么元组( o ，t ) 就形成一个6 - p c l u s t e r 。 基于p s c o r e 的定义，可见p c l u s t e r 模型有以下特点： ( 1 ) 如果( o ，t ) 是一个p c l u s t e r ，那么它的任何子矩阵( o ，t ) 也是 p c l u s t e r 。 ( 2 ) p s c o r e 的定义是对称的。两者的差异性由水平或垂直都可被测量。 定义中的等式相当于2 3 所示。 i ( 丸一九) 一( 叱一) l - i ( 屯一叱) 一( 如一叱) ( 2 3 ) p s c o r e c 隆甜 与b i c l u s t e r 的算法不同，p c l u s t e 血l g 可以同时发现多个适应用户指定门 槛数巧的群。更进一步讲，p c l u s t e r i n g 方法是确定的而非随机的，所以不会 漏掉任何有意义的p c l u s t e r 群。而b i c l u s t e r 的随机算法只能得至0 一个近似的 结果。 2 2 1m d s 发现 p c i u s t e r i n g 法的第一个步骤分别对所有对象及属性进行两两对比，产 8 第2 章相关研究 生m d s ( m a x i m u md i m e n s i o ns e t s ) ，即最大维组。m d s 方法可以有效率的 找出符合p s e o r e 条件的对象及属性集合。对对象进行m d s 分析所产生的 集合称为m d s o ，而对属性则产生m d s e 。 下例来说明m d s 法的作法：如表2 1 所示，r ，c ，t 分别代表p c l u s t e r 所需要的三个参数n r ( 群内最小对象个数) 、n e ( 决定成为一个群的个体间的 最小属性数) 和t c o s e o r e 的边界值) 。 表2 - 1 对象属性表现数据 t a b l e2 - 1a o b j e c t sa n d a t t r i b u t e sd a t a r ：3 ，c ；3 ，t ：1c oc 1 c a c ， 已 o o 9361 0 02 9 o i 1 0581 05 6 0 5 7 i565 3 0 3 2 0 01 92 22 47 0 0 4 3 2 7 - 8- 43 4 3 0 5 l l591 15 7 以o o 跟0 1 两个对象来看，首先将o o 与0 1 相减可以得到一个属性长 度的差值集合s ，排序此集合，将起始点( s t a r t ) 设为第一个值，而结束点( e n d l 设为第二个值，由结束点开始向后寻找，直至找到一个值与起始点值相减 大于t 的边界值。若其间所包含的属性长度大于c ，则输出成为一个m d s p a t t e m ，并将起始位置向后移一位。一直重复直至结束点的位置大于属性 的长度。如图2 1 的例，一开始起始位置在一2 7 ，而结束位置在2 ，将其相 减大于界线值l ，因此将起始值向后移至2 的位置并由其后的2 开始向后 寻找，最后可以得到一个m d s op a t t e r n ： ( 0 0 ，0 1 ) ，( c o ，c l ，c 2 ) ) 。 图2 - 1 表2 - 1 中m d s 范例 f i g 2 - 1ae x a m p l eo f m d so f t a b l e2 - 1 9 燕山大学工学硕士学位论文 下面为m d s 生成算法。 i n p u t ：x ，y ：t w oo b j e c t s ，t ：s e to fc o l u m n s ，n c ：m i n i m a ln u m b e ro f c o l u m n s 6 ：c l u s t e rt h r e s h o l d o u t p u t ：a l l6 - p c l u s t e r s 嘶t 1 1m o r et h a nn cc o l u m n s s + , i x d y ；+ i e ，s i h 屯一d y i f o re a c h i i n t + ， s o r ta r r a ys ； s t a r t _ 0 ；e n d - 1 ； n e wh t r u e ； 搴ab o o l e a nv a r i a b l e ，i ft r u e ，i n d i c a t e s a nu n t e s t e d c o l u m ni n 【s t a r t ，e n d 8 r e p e a t v 一s d s s t m ； i f i v i 曼6 t h e n pe x p a n d s5 - p c l u s t e rt oi n c l u d eo n em o r ec o l u m n s | e n d _ e n d + 1 ： n e w4 - - - t i u j e ： e l s e r e t u r n 5 - p c l u s t e r i fe n d s t a r t n ca n dn e w = t r u e ； s t a r t - s t a r t + 1 ： n e w 一f a l s e ； u n t i le n d 兰l t | ； r e t u r n5 - p c l u s t e rf ie n d s t a r t 三n ca n dn e w = t r u e ； 2 2 2m d s 的剪除 m d s 方法所产生的m d s op a t t e r n 及m d s cp a ：t t e r n 包含了整个数据集 中所有可能成为p c l u s t e r 的元素。但也包含了很多不必要，多余的元素。 因此必须对m d sp a a e m 进行剪除的操作。对m d sp a t t e r n 的剪除的过程可 说是p c l u s t e r i n g 算法的核心。 剪除的原则如下：假设t 0 表示对象x 与y 的m d sp a 仕e m ，o 曲为属 性a 和b 的m d s p a t t e r n ，对任何一个存在的m d s p a t t e r n ，k 当中的属性 1 0 第2 章相关研究 a 来说，计算当中包含有 x ，y ) 的o a b 个数。如果小于r e 1 ，则将属性a 从 1 k 中剪除。如果剪除的操作造成了i t x ，i n r - 1 ， o a b i 兰n r ) 。 图2 2 所示为p c l u s t e r i n g 的剪除范例。首先，对整个数据集产生m d s c p a t t e r n ，接着产生m d s op a t t e m ，并用m d s cp a t t e r n 来剪除m d s op a t t e m 。 在 ( 0 0 ，0 2 ) ，( c o ，c l ，c 2 ) 中，c 2 将被剪除。因为( o o ，0 2 ) 在所有包含c 2 的m d s c p a t t e r n 中，其个数只有1 个，小于n c 一1 。而剪除c 2 的操作造成了( 0 0 ，0 2 ) 的p a t t e m 长度小于n c ，故将( o o ，0 2 ) 的p a t t e r n 整个剪除。接着，依此类推 用剩余的m d s op a t t e r n 来剪除m d s cp a t t e r n ，如此重复直到没有任何元素 被剪除为止。 图2 - 2m d s 剪除范例( r t r = n g = 3 ，t = 1 ) f i g 2 - 2e x a m p l eo f m d sp r u n i n gw i t h ( n r 2 1 1 c = 3 ，t = 1 ) 2 2 3 前缀树( p r e f i xt r e e ) 的形成 在剪除完成后，需要将剩余的m d sp a t t e r n 填入一个名为p r e f i xt r e e ( 前 缀树) 的结构中，前缀树的每一个节点唯一地表示一个最大维组( m d s ) 。假 设a 中存在一个属性的总次序，比如：a b c 。 图2 3 是一个将两个对象的p c l u s t e r ( 0 ，t ) 插入前缀树的例子。首先， 对t 中的属性进行排序，使其成为有序组t 。然后，以属性为路径从树的 根开始向下走，将o 中的两个对象信息加入到最后所达到的节点中。例如， ( x ，y ) c ，0 ，以a o c - f 为其路径，将x ，y 的信息填入最终节点中。 当所有的对象被插入后，树中的每个节点都可以看成是一个p c l u s t c r 的候选者( 0 ，d 。下一个步骤是修剪0 中的对象元素，使其成为p c l u s t e r 。 1 1 燕山大学工学硕士学位论文 事实上，在0 中基于属性集t 聚类的对象同样意味着它们可由t 的子集t 聚类得到。设t 被另一个节点m 的路径所表示。从叶子节点开始。如叶子 节点n 表示一个候选p c l u s t e r 群( o ，t ) ，而且很显然在前缀树中不存在任何 节点的属性集能够包含t 的，就可以安全地将此节点中o 的对象剪除， 以发现所有的p c l u s t e r 群。 在完成这个操作后，将o 中的所有对象加到节点属性集为t ( t 属于 t ，并且i t p l t f 1 ) 的节点中。后序遍历此前缀树，对每个候选者进行m d s 操作并剪除多余的元素，重复操作直至不存在深度兰n c 的节点。最后得到 p c l u s t e r 的结果。 图2 - 3 前缀树范例( n r = r i o = 3 ，t = 1 ) f i g 2 - 3e x a m p l eo f p r e f i x t r e e p c l u s t e r i n g 的算法如下所示。 i n p u t ：d ：d a t as e t ，6 ：p c l u s t e rt h r e s h o l d ；n o ：m i n i m a ln u m b e ro fc o l u m n s ， n r - m i n i m a ln u m b e ro f r o w s o u t p u t ：a l lp c l u s t e r sw i t hs i z e 兰n rxn c f o re a c ha ，b a ，a = bd o f i n dc o l u m n - p a i r m d s s ：p a i r c l u s t e r ( a , b ，d ，n r ) ； f o re a c h x ，y d ，x = y d o f i n do b j e c t - p a i rm d s s ：p a l r c l u s t e r ( x ，y a ，n c ) ； r e p e a t f o re a c ho b j e c t - p a i rp c l u s t e r ( x ，y ，d ) d o u s ec o l u r a n p a i rm d s st op r u n ec o h a n n si nt 1 2 第2 章相关研究 e l i m i n a t em d s ( x ，y ) ，t ) i fi t l n o ； f o re a c hc o l u m n - p a i rp c l u s t e r ( a ，b ) ，o ) ) d o u s eo b j e c t - p a i rm d s st op r u n eo b j e c t si no ： e l i m i n a t em d s ( a ，b ，o ) i f l o l n r ； u n t i ln op r u n i n gt a k e sp l a c e ； i n s e r t a l lo b j e c t p a i r m d s s ( x ，y ) ，t ) i n t o t h ep r e f i x t r e e ： i n s e r t t r e e ( x ，y ，d ； m a k eap o s t o r d e rt m v e r s a lo f t h et r e e ； f o re a c hn o d ene n c o u n t e r e di nt h ep o s t - o r d e rt r a v e r s a ld o 0 ：= o b j e c t s i n n o d e n ： t ：2c o l u m n s r e p r e s e n t e db y n o d en ： f o re a c h 钆b t d o f i n dc o l u m n p a i rm d s s ：c = p a i r c l u s t e r ( a , b ，0 ，n r ) ； r e m o v ef r o mot h o s eo b j e c t sn o tc o n t a i n e di na n ym d sc c ： o u t p u t ( o ，t ) ； a d do b j e c t si nnt on o d e sw h i c hh a so n el e s sc o l u i i l nt h a nn ： 2 3 o p c l u s t e r p c l u s t e r 模型一个主要的局限在于它仅仅能挖掘出严格满足等差模式 或等比模式的群，而对其他的模式判断不足。事实上，在多维数据空间中， 还可能存在多种其他模式。因此，一个更灵活的聚类模型基于次序的 模式( o p c l u s t e r ) 此引入，它是基于一个对象在一组属性子集中的增减趋 势，而非严格的等差或等比模式。 2 3 1 o p c l u s t e r 模型 如图2 4 所示，3 个对象和1 0 个属性。在2 - 4 ( a ) 中的原始数据中，并 没有明显的模式。但是，如果选出其中的一组属性，如图2 4 f b ) 所示，就 可以发现以下事实：对于这三个对象每个属性上值的大小进行排列，结果 1 3 燕山大学工学硕士学位论文