（计算机软件与理论专业论文）事务数据的多隶属聚类问题研究.pdf

独创性声明 本人郑重声明所呈交的论文是我个人在导师指导下进行研究工作所取得的成 果。尽我所知，除论文中特别标注的内容之外，论文中不包含其个人或集体已经 发表或撰写过的研究成果；也不包含为获得西北大学或其它教育机构的学位或证 书而使用过的材料。与我同工作的同志对本研究所做的任何贡献均已在论文中 做出了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者签字：旁岔笏爿匆 日期：二。三年四月一日 摘要 聚类是将数据分组成为簇或类。使得处于同一个簇中的数据之间相似度较高， 而处于不同簇的数据之间差别较大。人们对于聚类问题已经进行了深入的研究， 提出了很多的算法来解决各种各样的聚类问题。目前的算法大体上可以分为两类， 一类是硬聚类，在硬聚类中，一个数据元素只能属于一个簇。另外一类聚类是模 糊聚类，在模糊聚类中，一个数据元素可以同时属于多个簇，对于每一个簇有一 个相应的隶属度，其值介于0 和1 之间。通过将数据归大隶属度值最大的簇，模 糊聚类也可转化为硬聚类。 然而，在一些聚类问题中，一个数据元素是可以同时属于多个类或簇的，而 且对于每一个类或簇，其隶属度的值均可为1 。 本研究把这一类问题称为多隶属聚类问题。对于数据型数据，现有的模糊聚 类算法也能加以解决，但对于事务属性数据或分类属性数据的多隶属聚类问题， 目前尚无相关研究。 本研究针对事务属性数据的多隶属聚类问题，提出了三种算法，分别是基于 频繁项目集的多隶属聚类算法、基于小项大项比的多隶属聚类算方法以及基于连 接的多隶属聚类算法。对于分类属性数据，在进行变换后，也能用这三种聚类方 法产生多隶属聚类。 关键词：聚类；数据挖掘；多隶属聚类；事务数据；频繁项目集；小项大项比 连接 a b s t r a c t c l u s t e r i n gi st h ep r o c e s so fg r o u p i n gt h ed a t ai n t oc l a s s e so rc l u s t e r ss o t h a to b j e c t sw i t h i nac l u s t e rh a v eh i g hs i m i l a r i t yi nc o m p a r i s o nt oo n e a n o t h e r , b u ta r ev e r yd i s s i m i l a rt oo b j e c t si no t h e rc l u s t e r s c l u s t e r i n g a n a l y s i sh a sb e e ns t u d i e de x t e n s i v e l y , a n dm a n ym e t h o d sw e r ef o u n dt o s o l v ev a r i o u sk i n d so fp r o b l e m s c l u s t e r i n ga l g o r i t h m sc a nb ed i v i d e di n t o h a r do rf u z z y ah a r dc l u s t e r i n ga l g o r i t h ma l l o c a t e se a c hp a t t e r nt oas i n g l e c l u s t e rd u r i n gi t s o p e r a t i o na n di ni t so u t p u t a f u z z yc l u s t e r i n gm e t h o d a s s i g n sd e g r e e so fm e m b e r s h i pi ns e v e r a lc l u s t e r st oe a c hi n p u tp a t t e m s ， t h ed e g r e e so fm e m b e r s h i pa r eb e t w e e n0a n d1 af u z z yc l u s t e r i n gc a nb e c o n v e r t e dt oah a r dc l u s t e r i n gb ya s s i g n i n ge a c hp a t t e r nt ot h ec l u s t e rw i t h t h el a r g e s tm e a s u r eo fm e m b e r s h i p b u ti ns o m ec a s e s ，ap a t t e mc a nb ea l l o c a t e dt om o r et h a no n ec l u s t e r i nt h i st h e s i sw ec a l li tm u l t i s u b j e c t e dc l u s t e r i n g f o rn u m e r i c a ld a t a ， f u z z yc l u s t e r i n ga l g o r i t h m sc a nb eu s e dt os o l v et h i sk i n do fp r o b l e m s ，b u t n e w a l g o r i t h m s n e e dt ob e d e v e l o p e d t os o l v et h e p r o b l e m o f m u l t i - s u b j e c t e dc l u s t e r i n go nt r a n s a c t i o nd a t ao rc a t e g o r i c a ld a t a w i t hf o c u so nt r a n s a c t i o nd a t a ，t h r e ea l g o r i t h m sw e r ed e v e l o p e dt o s o l v em u l t i s u b j e c t e dc l u s t e r i n gp r o b l e m s t h e r ea r ef r e q u e n t - i t e m sb a s e d a l g o r i t h m ，s l r - b a s e da l g o r i t h m a n dl i n k - b a s e d a l g o r i t h m a l g o r i t h m s c a na l s ob eu s e do n c a t e g o r i c a l d a t ai ft h ed a t a t h e s e w e r e p r e p r o c e s s e d k e yw o r d s ：c l u s t e r i n g ；d a t am i n i n g ；m u l t i - s u b j e c t e dc l u s t e r i n g ； t r a n s a c t i o nd a t a ；矗e q u e n ti t e m s e t s ；s l r ；l i n k 事务数掂的多求属聚类问题 i j | _ 究 第一章引言 1 1 研究目的与动机 数据挖掘( d a t am i n i n g ) 也称为数据库中的知识发现( k d d ) ，是指从大数 据库中发现有用的，隐含的，事先不为人所知的知识的过程。数据挖掘从数据中 抽取出人们感兴趣的可用信息和知识，并将抽取出来的知识表示成概念、规则、 规律或模式。 数据挖掘的主要任务是概念( 或类) 描述、关联规则分析、分类和预测、聚 类分析、孤立点分析和演变分析。 聚类分析是按相似度将数据对象( 或模式) 分组成为多个类或簇( c l u s t e r ) 。直观 地讲，同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。 在机器学习领域，聚类是一种无导师的学习方法。在有导师学习的分类中，我们 面对的是一些已经有标号的模式，所要解决的问题是对新出现的模式分类，也就 是利用已经标号的模式来学习出该类的特征，从而利用这些信息来标记新的模式。 而聚类是要把未知类别的模式划分到一些有意义的簇中。从某种程度来说，也要 给分出的簇加上类标记，但这些分类标记是数据驱动的，也就是说，它们是从数 据中获取的。 聚类在许多探索性的模式分析、分组、决策，以及机器学习包括文档抽取、 图象分块和模式分类中都很有用。在商务上，聚类能帮助市场分析人员从客户信 息库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征，从而进 行购物推荐等。在生物学上，聚类能用于推导植物和动物的分类，对基因进行分 类，获得对种群中固有的结构的认识。聚类也能用于对w e b 上的文档进行分类， 以发现信息。在许多这样的问题中，我们所能得到的关于数据的先验知识( 如统 计模型) 很少，因而决策制定者必须给出尽可能多的关于数据的假设。正是由于 有这样的限制，聚类方法非常适合于探索数据之间的相互关系，从而估计出数据 的结构。此外。聚类分析也可以作为其它算法( 如特征描述和分类) 的预处理步骤， 这些算法再在生成的簇上进行处理。 鼾务数据的多隶属聚兴问题研究 对于聚类问题，人们已经进行了大量的研究，提出了很多的算法来解决各种 各样的聚类问题。目前的算法大体上可以分为两类，一类是硬聚类，硬聚类把数 据集x 分为k 个簇，这k 个簇中所包含的数据集分别设为c 。，c ：，q ，那么有 x = c u c ：u u gu e 。， c fn c ，= ( 其中i = 1 ，2 ，k ，o u t l i e r s ，j = 1 ，2 ，k ，o u t l i e r s ) - 其中c 。表示孤 立点数据( 或例外数据) 的集合。 简单地说，在硬聚类中，一个数据元素只能属于一个簇，也就是说，硬聚类 产生的是数据的一个划分。另外一类聚类是模糊聚类，在模糊聚类中，一个数据 元素可以同时属于多个簇，对于每一个簇有一个相应的隶属度，其值介于0 和1 之间。 目前大部分的聚类研究和算法都集中于以上两类问题。然而，在一些聚类问 题中，一个数据元素可以同时属于多个类或簇，而且对于每一个类或簇，其隶属 度的值均可为1 。 例如，在进行购物篮数据挖掘时，若要将购买进口商品( 如f r e n c h w i n e ，s w i s s c h e e s e ，i t a l i a no p a s t as a u c e ，b e l g i a nb e e r 等) 的交易( 或顾客) 分为一类( 这一类 顾客可能收入较高) ，将购买婴儿食品、尿布、小孩玩具的交易分为一类( 这类顾 客可能家里有小孩) ，那么既购买进口商品又购买婴儿用品的交易( 或顾客) 就可 能同时都属于这两个类；如果根据病人的症状将病人按所患疾病的不同进行聚类， 患疾病a 的人归为类a ，患疾病b 的人归为类b ，以此类推。那么，如果一个病 人同时患有几种疾病，将该病人同时归入几个类，且隶属度均为l 就可能是合理 的；分析学生对知识点的掌握情况，将未掌握某一知识点的学生归为一类，同样 也会出现一个学生同时属于几个类且隶属度均为1 的情况。 当然，从理论上说，也可以把同时属于几个类的数据归为新的一类，例如在 第一个例子中，可以产生一个既购买进口商品，又购买婴儿用品的一个类，但是， 现有的的聚类算法都要求聚类结果的每一个簇中所包含的数据不能过少，因而实 际上可能很难发现这样的簇或类。 基于以上分析，作者认为研究类似这样的聚类问题具有实际的意义。以下将 这一类问题称为多隶属聚类问题。对于数值型数据的多隶属聚类，可以采用现有 _ l f 务数据的多隶属聚类问题州究 的模糊聚类算法先产生每个数据元素列每个簇的隶属度，然后再用某种判别方法， 以产生多隶属聚类。但现有的模糊聚类算法都是针对数值型数据的，因此对于事 务型数据和分类属性数据，不能采用这样的处理方法。本文的研究主要针对事务 ( t r a n s a c t i o n ) 型数据，目的是要找到新的聚类方法，以产生事务数据的多隶属聚类。 1 2 聚类算法研究现状 聚类是把对象集合中的元素分组到不同的类中或簇中的过程，要求属于同一 个簇的对象之间有较高的相似度，而不同簇之间的元素区别较大。作为统计学的 一个分支，多年以来人们对聚类进行了深入的研究，不过研究主要集中于基于距 离的聚类分析。基于k 平均( k m e a n s ) ，k - 中心点( k m e d o i d s ) ，以及其它一些方法 的聚类工具已经被应用于许多统计分析软件包或系统中，如s - p l u s ，s p s s 以及 s a s 。聚类在机器学习领域是一种无导师学习方法，凶为它不依赖于预先定义的 类和已标号的训练样本。 主要的聚类方法可以分为：划分的方法，层次的方法，基于密度的方法，基 于网格的方法，基于模型的方法。 1 2 1 划分的方法 在数据挖掘 ；现之问，划分就是一种很流行的数据聚类算法。给定d 维空间 中n 个对象的集合n 和输入参数k ，一个划分的算法将对象组织到不同的簇中， 使得每个对象到它的所属的簇的簇中心或簇分布的偏离之和最小。偏离 ( d e v i m i o n ) 的计算在不同的算法中也不相同，大部分情况下把它叫做相似函数。 典型的划分方法是k - 平均方法和k 一中心点方法。两种方法表示簇的形式不一 样。k 平均方法用簇中对象的质心( 或平均值) 来作为簇的中心，而k 中心点方 法用处于簇的最中心的对象来表示簇。 k 平均方法随机地选择k 个对象，每个对象初始地代表了一个簇的平均值或 中心。对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇。然 事务数据的多隶属聚炎问题研究 后重新计算每个簇的平均值。这个过程不断地重复，直到判别函数收敛。通常采 用平方误差判别准则其定义为： e = ：，p 。c i l p 一卅，j 其中e 是所有对象的平方误差的总和，p 是数据空间中的点，表示给定的数 据对象，m 是簇c 的平均值。k 一平均方法只有在簇的平均值被定义的情况下才能 使用，对于分类属性数据，由于难以定义平均值，此方法并不适用。当结果簇是 密集的，而簇与簇之间区别明显时，它的效果较好。k 平均方法有很多的变体， 如k 模方法 h u a 9 8 和e m 方法 l a u 9 5 。 k 中心点方法首先为每个簇随意选择一个代表对象，剩余的对象根据其与代 表对象的距离分配给最近的一个簇，然后反复地用非代表对象来替代代表对象， 以改进聚类的质量。p a m ( p a r t i t i o n i n ga r o u n dm e d o i d s ) k r 9 0 是最早提出的k - 中 心点算法之一。 为处理大数据集，k a u f m a n 矛1 r o u s s e e u w 设计了一种叫做c l a r a ( c l u s t e r i n g l a r g ea p p l i c a t i o n s ) k r 9 0 的算法。它不是考虑所有的数据对象，而只是选择一 小部分数据来代表整个数据集。为了提高c l a r a 算法的质量和可伸缩性，提出了 一种新的聚类算法，叫做c l a r a n s ( c l u s t e r i n gl a r g ea p p l i c a t i o n sb a s e du p o n r a n d o m i z e ds e a r c h ) n h 9 4 。在寻找更好的中心点的递归重分配算法中 c l a r a n s 试图通过随机地选择k 个中心中的一个并用从其它( n k ) 个点中随机的选 出的对象来代替它。如果一定次数的尝试后找不到一个更好的解，就认为已经达 到了局部最优。 1 2 2 层次方法 层次方法对数据集产生一个层次分解，形成一个系统树匿 ( d e n d r o g r a m ) ：一 棵把数据库递归地分为小的子集的树。系统树图可以用两种方式来形成：自底向 上和自顶向下。自底向上的方法也称为凝聚的方法，它的开始是每一个对象构成 单独的一个组。它按一定的度量标准比如两个组的中心点之间的距离连续地将对 象或组进行合并，直到所有的组最后都归为一个( 层次结构的最高层) ，或者满 事务数据的多求属聚类问题州兜 足了终止条件。 早先的层次聚类方法如a g e n s 和d i a n a 【k r 9 0 】的不足之处在于用过于简单 的度量来分裂和合并簇，再加上每一次合并或分裂都是不能撇消的，所以这样的 方法往往导致发现错误的簇。 为了提高层次聚类算法的效率，近来的聚类方法采用了咀下的一种或两种处 理方式，第一种方式中，有代表性的算法如c u r e g r s 9 8 平ic h a m e l e o n 【k h k 9 9 】，它们在对簇进行合并或分裂时采用一种更复杂的原则。虽然这种处理 方式中簇的合并或分裂仍是不可撤消的，但由于采用了一种更好的方法来进行合 并和分裂，出错的可能性就比较小。 c u r e 用来产生高质量的簇的主要思想有两个。首先，不是采用单个的中心 点或对象来代表一个簇，而是使用一个固定数目的挑选出来的分散的对象来表示 每一个簇。第二，选出来的代表点通过一个定义在0 和1 之间的分数收缩因予a 向 它们的中心点收缩。在算法的每一步，代表点距离最近的两个簇将进行合并，由 于每个簇有多个代表点，可以选择使用所有的点或只使用中心点两种方法的折衷 来代表一个簇。这种方法使c u r e 可以适应几何形状非球形的簇。簇的收缩或浓 缩减少了孤立点( o u t l i e r s ) 的影响，因此，c u r e 对于孤立点更健壮，能发现非 球形的簇并且允许更宽的簇大小范围变化。在不牺牲质量的情况下，对于大的数 据库仍有很大的可伸缩性。为了能处理大型数据库，c u r e 采用了随机采样和划 分方法的综合：一个随机的样本首先进行划分，每一个划分单独地进行聚类。在 第二步中，这些部分簇再进行聚类以产生理想的簇。 c h a m e l e o n 是一个在层次聚类中采用动态模型的聚类算法，在它的聚类过 程中，如果两个簇问的互连性和近似度与簇内部对象间的互连性和近似度高度相 关，则合并这两个簇。它首先通过个图划分算法将数据对象聚类为大量相对较 小的子聚类，然后用一个凝聚的层次聚类算法通过反复地合并簇来找到真正的结 果簇。它即考虑了互连性，又考虑了簇间的近似度，特别是簇内部的特征，以确 定最相似的子簇，因此它不依赖于一个静态的用户提供的模型，能够自动地适应 被合并的簇的内部特征。 第二种方式的代表算法立n b i r c h ( b a l a n c e di t e r a t i v er e d u c i n ga n dc l u s t e r i n g u s i n gh i e r a r c h i e s ) z r l 9 6 是采用一种层次凝聚的方法来获得初始结果集，然后用 事务数掘的多求届聚类问题研究 递归重分配算法来对结果集进行求精。b i r c h 的主要思想是先把数据对象压缩成 许多小的子簇，然后在这些子簇上进行聚类。由于经过压缩后子簇的数量比数据 对象的数量要少得多，因此聚类操作可以在计算机的主存中进行，使该算法只需 要扫描数据库一次。 1 2 3 基于密度的方法 大部分划分的聚类方法是基于对象间的距离的。这种方法只能发现球形的簇， 要发现任意形状的簇的时候就有困难。因此，产生了一些其它的聚类的方法，它 们是基于密度的概念的。它们认为簇是一些高密度的区域，这些高密度区域被一 些低密度的区域分割开来。基于密度的方法可以过滤孤立点( 或o u t l i e r s ) ，发现 任意形状的簇。 d b s c a n ( d e n s i t y - b a s e ds p a t i a lc 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 ) 【e k s x 9 6 】是一个基于密度的聚类算法，它判断一个对象周围的密度是否足够的 标准是与该对象的距离为占的范围内数据点的数目是否超过最小支持点数 m i n p t s 。如果一个点p 的占- 邻域内包含多于m i n p t s 个点，则创建一个以p 作为 核心对象的新簇。然后，d b s c a n 反复地寻找从这些核心对象直接密度可达的对 象，这个过程可能涉及到一些密度可达的簇的合并，当没有新的点可以被添加到 任何簇时，该过程结束。 在d b s c a n 中，用户需要指定参数f 和m i n p t s ，但对于真实的高维数据而 言，参数的设置往往难以确定，而设置的细微不同就可能导致差别很大的聚类结 果。为解决这一问题，提出了o p t i c s 方法。o p t i c s ( o r d e r i n g p o i n t s t o i d e n t i f y t h e c l u s t e r i n gs t r u c t u r e ) 【a b k s 9 9 】是一种通过对象排序来识别聚类结构的方法。 o p t i c s 算法创建了数据库中对象的一个次序，额外存储了每个对象的核心距离 和一个适当的可达距离。已经提出了一种算法，基于o p t i c s 产生的次序信息来 抽取聚类。 d e n c l u e ( d e n s i t y - b a s e dc l u s t e r i n g ) h k 9 8 是一个基于一组密度分布函 数的聚类算法。该算法主要基于下面的思想：( 1 ) 每一个数据点的影响可以用一个 射务数据的多求属聚类问题 j f 究 数学函数来形式化地模拟，它描述了一个数据点在邻域内的影响，被称为影响函 数( i n f l u e n c ef u n c t i o n ) ；( 2 ) 数据空间的整体密度可以被模型化为所有的数据点的影 响函数的总和；( 3 ) 聚类可以通过密度吸引, 点( d e n s i t ya t t r a c t o r ) 来得到，这里的密度 吸引点是全局密度函数的局部最大。 1 2 4 基于网格的方法 基于网格的聚类方法采用一个多分辨率的网格数据结构。它将空间量化为有 限数目的单元，这些单元形成了网格结构，所有的聚类操作都在网格上进行。这 种方法的主要优点是处理速度快，其处理时间独立于数据对象的数目，仅依赖于 量化空间的每一维上的单元数日。 基于网格的方法的有代表性的例子包括：s t i n g w y m 9 7 ，它利用存储在网 格单元中的统计信息；w a v e c l u s t e r s c z 9 8 】，它用一种小波转换方法来聚类对象； c l i q u e a g g r 9 8 1 ，它是在高维数据空间中基于网格和密度的聚类方法。 s t i n g 是一种基于网格的多分辨率聚类技术，它将空问区域划分为矩形单 元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一 个层次结构：高层的每个单元被划分为多个低一层的单元。关于每个网格单元属 性的统计信息( 例如平均值、最大值和最小值) 被预先计算和存储。这些统计参数 对于相关的查询处理是有用的。 高层的统计参数可以很容易地从低层单元的计算得到。这些统计参数包括： 属性无关的参数c o u n t ( 计数) ；属性相关的参数m ( 平均值) ，s ( 标准偏差) ，m i n ( 最 小值) ，m a x ( 最大值) ，以及该单元中属性值遵循的分布( d i s t r i b u t i o n ) 类型，例如正 态分布、一致分布、指数分布或无( 如果分布未知) 。当数据被装载进数据库，底 层单元的参数c o u n t ，m ，s ，m i n 和m a x 直接进行计算。如果分布的类型事先知道， 分布的参数值可以由用户指定，也可以通过假设检验来获得。一个高层单元的分 布类型可以基于它对应的低层单元多数的分布类型，用一个阈值过滤过程来计算。 如果低层单元的分布彼此不同，闽值检验失败，高层单元的分布类型被置为n o n e 。 统计参数的使用可以按照自顶向下的基于网格的方法。首先，在层次结构中 选定一层作为查询处理的开始点。通常，该层包含少量的单元。对当前层次的每 舡务数据的多隶属聚类问题 i j f 究 个单元，计算置信度区间( 或者估算其概率范围) 用以反映该单元与给定查询的 关联程度。不相关的单元就不再考虑。低一层的处理就只检查剩余的相关单元。 这个处理过程反复进行，直到达到底层。此时，如果查询要求被满足，那么返回 相关单元的区域。否则，检索和进一步的处理落在相关单元中的数据，直到它们 满足查询要求。 由于s t i n g 采用了一个多分辨率的方法来进行聚类分析，s t i n g 聚类的质 量取决于网格结构的最低层的粒度。如果粒度比较细，处理的代价会显著增加； 但是，如果网格结构最低层的粒度太粗，将会降低聚类分析的质量。而且，s t i n g 在构建一个父单元时没有考虑孩子单元和其相邻单元之间的关系。因此，结果簇 的形状是i s o t h e t i c ，即所有的聚类边界或者是水平的，或者是垂直的，没有对角 的边界。尽管该技术有快速的处理速度，但可能降低簇的质量和精确性。 w a y e c l u s t e r 是一种多分辨率的聚类算法，它首先通过在数据空间上强加一个 多维网格结构来汇总数据，然后采用一种小波变换来变换原特征空间，在变换后 的空间中寻找密集区域。 在该方法中，每个网格单元汇总了一组映射到该单元中的点的信息。这种汇 总信息适合于在内存中进行多分辨率小波变换以及随后的聚类分析使用。 小波变换是一种信号处理技术，它将一个信号分解为不同频率的子波段。通 过应用一维小波变换1 1 次，小波模型可能应用于n 维信号。在进行小波变换时， 数据被变换以在不同的分辨率层次保留对象间的相对距离。这使得数据的自然聚 类变得更容易区别。通过在新的空间中寻找高密度的区域，可以确定聚类。 基于小波变换的聚类速度很快，计算复杂度为0 ( h ) 。其中n 是对象的数目。 算法的实现可以并行化。 w a v e c l u s t e r 是一个基于网格和密度的算法。它符合一个好的聚类算法的许多 要求：它能有效地处理大数据集合，发现任意形状的簇，成功地处理孤立点，对 于输入的顺序不敏感，不要求指定诸如结果簇的数目或邻域的半径等输入参数。 在实验分析中，w a v e c l u s t e r 在效率和聚类质量上优于b i r c h 。c l a r a n s 和 d b s c a n 。 c l i q u e ( c l u s t e r i n gi nq u e s t ) 聚类算法综合了基于密度和基于网格的聚类方 法。它对于大型数据库中的高维数据的聚类非常有效。c l i q u e 的主要思想如下： 舡务数据的多隶属聚类问题j i j | _ 究 给定一个多维数据点的大集合，数据点在数据空间中通常不是均镐分布的。 c l i q u e 区分空间中稀疏的和“拥挤”的区域，以发现数据集合的全局分布模式。 如果一个数据单元中包含的数据点超过了某个输入模型参数，则该单元是密 集的。在c l i q u e 中簇定义为相连的密集单元的最大集合。 c l i q u e 分两步进行多维聚类： 第一步，c l i q u e 将n 维数据空间划分为互不相交的长方形单元，识别其中 的密集单元。该工作对每一维进行。代表这些密集单元的相交子空间形成了一个 候选搜索空间，其中可能存在更高维度的密度单元。c l i q u e 将更高维密集单元 的搜索空间限制在子空间密集单元的交集中，这种候选搜索空间的确定采用类似 于关联规则挖掘中的先验性质。一般说来，该性质在搜索空间中利用数据项的先 验知识以裁减空间。c l i q u e 所采用的性质如下：如果一个k 维单元是密集的， 那么它在k 1 维空间上的投影也是密集的。也就是说，给定一个k 维候选密集单 元，检查它的k 1 维投影单元，如果发现任何一个不是密集的，那么就知道第k 维的单元也不可能是密集的。因此，可以从k - 1 维空间中发现的密集单元来推断 k 维空间中潜在的或候选的密集单元。通常，最终的结果空间比初始的空间要小 很多。最后检查密集单元决定聚类。 在第二步，c l i q u e 为每个簇生成最小化的描述。对每个簇，它确定覆盖相 连的密集单元的最大区域，然后确定最小的覆盖。 1 2 5 基于模型的方法 基于模型的聚类方法试图优化给定的数据和某些数学模型之间的适应性。这 样的方法通常是基于这样的假设：数据是根据潜在的概率分布生成的。基于模型 的方法主要有两类：统计学方法和神经网络方法。 概念聚类是机器学习中的一种聚类方法，给出一组未标记的对象，它产生对 象的一个分类模式。与传统的聚类不同，概念聚类除了确定相似对象的分组外， 还可为每组对象发现特征描述，即每组对象代表了一个概念或类。因此，概念聚 类是一个两步的过程：首先进行聚类，然后给出特征描述。在这里，聚类质量不 再只是单个对象的函数，而且加入了如导出的概念描述的简单性和一般性等因素。 事务数据的多隶属聚类问题研究 概念聚类的绝大多数方法采用了统计学的途径，在决定概念或聚类时使用概 率度量。概念描述用于描述导出的概念。主要的方法有c o b w e b f i s 8 7 】、 c l a s s i t g l f 8 9 和a u t o c l a s s c s 9 6 。 神经网络方法将每个簇描述为一个标本( e x e m p l a r ) 。标本作为聚类的“原型”， 不一定对应一个特定的数据实例或对象。根据某些距离度量，新的对象可以被分 配给标本与其最相似的簇。被分配给一个簇的对象的属性可以根据该簇的标本的 属性来预测。神经网络中比较著名的两个方法，一个是竞争学习( c o m p e t i t i v e l e a m i n g ) r z 8 5 】，另一个是自组织特征映射s o m k o h 8 2 】，这两种方法者涉及有竞 争的神经单元。 竞争学习采用了若干个单元的层次结构，它们以一种“胜者全取 ( w i n n e r - t a k e - a 1 1 ) ”的方式对系统当前处理的对象进行竞争。在一个簇中获胜的单 元成为活跃的，而其它是不活跃的。各层之间的连接是激发式的( e x c i t a t o r y ) - - 在 某个给定层次中的单元可以接收来自低一层次所有单元的输入。在一层中活动单 元的布局代表了高一层的输入模式。在某个给定层次中，一个簇中的单元彼此竞 争，对低一层的输入模式做出反应。一个层次内的联系是抑制式的( i n h i b i t o r y ) ， 以便在任何簇中只有一个单元是活跃的。获胜的单元修正它与簇中其它单元连接 上的权重。以便在未来它能够对与当前对象相似或一样的对象做出较强的反应。 如果我们将权重看作定义一个标本。那么新的对象被分配给具有最近标本的簇。 结果簇的数目和每个簇中单元的数目是输入参数。 在聚类过程结束时，每个簇可以被看作一个新的“特征”，它检测对象的某 些规律性。这样，产生的结果簇可以被看作一个低层特征向高层特征的映射。 使用自组织特征映射( s e l f - o r g a n i z i n gf e a t u r em a p ，s o m ) ，聚类也是通过若干个 单元竞争当前对象来进行的。权重向量最接近当前对象的单元成为获胜的或活跃 的单元。为了更接近输入对象，对获胜单元及其最近的邻居的权重进行调整。s o m 假设在输入对象中存在一些拓扑结构或顺序，单元将最终在空间中呈现这种结构。 单元的组织形成一个特征映射。s o m 被认为类似于大脑的处理过程，对在二维或 三维空间中可视化高维数据是有用的。 除以上这些聚类方法外，还有其它聚类技术，如考虑条件限制 ( c o n s t r a i n t - b a s e d ) 的聚类技术 t h h 0 1 ，t n l h 0 1 ，采用遗传算法( g e n e t i ca l g o r i t h m ) 事务数据的多隶属聚樊问题研究 的聚类技术等。但是，这些方法均未考虑到多隶属聚类问题本研究的目的，就 是要找到能产生多隶属聚类的一些方法。 1 3 本文主要内容 本文的主要研究内容是事务属性数据的多隶属聚类算法，所做的主要工作包 括三种产生事务数据多隶属聚类的算法：利用频繁项目集来产生多隶属聚类的算 法，先对事务数据库进行频繁项目集挖掘，然后利用频繁项目集来产生事务数据 的多隶属聚类；利用小项大项比来产生多隶属聚类的算法，将簇中事务中所包含 的项分为小项和大项，根据小项和大项来产生事务数据的多隶属聚类；基于连接 的事务数据的多隶属聚类算法，不是采用事务数据之间的距离，而是利用事务数 据之间的连接来产生多隶属聚类。 本文后面内容安排：第二章是基于频繁项目集的多隶属聚类方法，第三章是 基于小项大项比的多隶属聚类算法。第四章是基于连接的多隶属聚类算法，最后 是结束语。 事务数据的多隶属聚类问题研究 第二章基于频繁项目集的多隶属聚类算法 2 1 问题提出 针对聚类问题已有大量的研究成果，人们提出了很多算法来解决各种各样的 聚类问题。目前的算法大体上可以分为两类，一类是硬聚类，硬聚类把数据集x 分为k 个簇，这k 个簇中所包含的数据集分别设为c ，c ：，q ，那么有 x = c luc 2u u c iuc 0 川m ， c ff l c ，= ( 其中i = 1 ，2 ，k ，o u t l i e r s ，j = 1 ，2 ，k ，o u t l i e r s ) ，其中c 。k 。表示孤 立点( 或例外数据) 的集合。 简单地说，在硬聚类中，一个数据元素只能属于一个簇，硬聚类实际上是产 生数据的一个划分，簇与簇之间是不相交的。另外一类聚类是模糊聚类，在模糊 聚类中，一个数据元素可以同时属于多个簇，对于每一个簇有一个相应的隶属度， 其值介于0 和1 之间。 目前大部分的聚类研究和算法都集中于以上两类问题。然而，在一些聚类问 题中，一个数据元素是可以同时属于多个类或簇的，而且对于每一个类或簇，其 隶属度的值均可为l 。例如，如果根据病人的症状将病人按所患疾病的不同进行 聚类，患疾病a 的人归为类a ，患疾病b 的人归为类b ，以此类推。那么，如果 一个病人同时患有几种疾病。将该病人同时归如几个类，且隶属度均为l 就可能 是合理的；在学生成绩分析中，若要分析学生对知识点的掌握情况，将未掌握某 一或某几个知识点的学生归为一类，同样也会出现一个学生同时属于几个类且隶 属度均为1 的情况：在进行购物篮数据挖掘时，若要将购买进口商品( 如f r e n c h w i n e ，s w i s sc h e e s e ，i t a l i a ns a t l e e ，b e l g i a nb e e r 等) 的交易( 或顾客) 分为一类( 这 一类顾客可能收入较高) 将购买婴儿食品、尿布、小孩玩具的交易分为一类( 这 类顾客可能家里有小孩子) ，那么既购买进口商品又购买婴儿用品的交易( 或顾客) 事务数据的多隶属聚类问题研究 就可能同时都属于这两个类。 当然，从理论上说，也可以把同时属于几个簇或类的数据归为新的一类，不 过由于现有的聚类算法一般都要求一个簇中的对象必须达到一定的数目，因而 实际上可能很难发现这样的簇或类。 基于以上分析，研究类似这样的聚类问题具有实际的意义。以下将这一类问 题称为多隶属聚类问题。本研究只考虑事务( t r a n s a c t i o n s ) 数据的多隶属聚类问题。 多隶属聚类可描述如下： 多隶属聚类是要将数据集x 分为k 个簇，这k 个簇中所包含的数据集分别设 为c i ，c 2 ，c ，那么有 。r = c lu c 2u u c u e 。m 。 若加上条件c ，n c ，= 庐( 其中i = 1 ，2 ，k ，o u t l i e r s ，j = 1 ，2 ，k o u t l i e r s ) ，则变为 一般聚类问题。 2 2 基于频繁项目集的多隶属聚类算法 本节提出一种新的方法，即使用频繁项目集来产生事务属性数据的多隶属聚 类。此方法优点在于( 1 ) 它是基于频繁项目集的，由于频繁项目集在关联规则挖 掘领域已有深入的研究，因而此方法有坚实的理论基础；( 2 ) 算法简单，易理解： ( 3 ) 产生的聚类容易解释；( 4 ) 能产生多隶属的簇：( 5 ) 不需要指定簇的数目。 先回顾频繁项目集的概念。在事务数据库中，项的集合称为项集( i t e m s e t ) 。 包含k 个项的项集称为k 项集( k - i t e m s e t ) 。如( f r e n c hw i n e ，s w i s sc h e e s e ，i t a l i a n s a u c e ，b e l g i a nb e e r ) 是一个4 项集。项集的出现频率是包含项集的事务数，简称 为项集的频率、支持计数或计数。定义一个项集在所有事务中出现的概率为其支 持度，即s u p p o r t ( a ) = p ( a ) ，如果项集满足最小支持度( 一个设定的概率值) 则 称它为频繁项目集( f r e q u e n ti t e m s e t ) 。 事并数据的多j i 属聚兴问题研究 2 2 1 算法的基本思想 首先来看一个具体的例子下表是一个交易记录数据库 t i d 项集i d 列表 t 0 0 li l ，1 2 ，1 3 ，1 4 t 0 0 21 5 ，1 6 t 0 0 3i l ，1 2 。1 5 ，1 6 t 0 0 4 1 3 ，1 4 ，1 5 ，1 6 t 0 0 5i l ，1 2 表2 1 一个交易数据库 若将支持度定为3 ，则出现的频繁2 项集分别为( i l ，1 2 ) ( 支持度为3 ) 和( 1 5 ，1 6 ) ( 支持度为3 ) 。根据所发现的频繁2 项集，可以将交易记录分为 两类，一类是含有频繁2 项集( 1 1 ，1 2 ) 的，另一类是含有频繁2 项集( 1 5 ， 1 6 ) 的，这样，属于第一类的有t 0 0 1 ，t 0 0 3 ，t 0 0 5 ，属于第二类的有t 0 0 2 ， t 0 0 3 ，t 0 0 4 。这样我们就从交易记录中发现了两个簇( 或类) ，其中交易t 0 0 3 同时属于两个簇。 此算法的基本思想就是。先用频繁项目集生成算法找出频繁项目集，然 后根据所找出的频繁项目集将交易记录归到相应的类中，其中可能包含有一 个交易记录同时属于几个类的情况。生成一个簇的频繁项目集可以用来描述 该簇的特征。 2 2 2 基于频繁项目集的多隶属聚类算法 2 2 2 1 频繁项目集的产生 由于频繁项目集广泛应用关联规则的发现，因此频繁项目集的产生在关联规 则挖掘中有着大量的研究。a p d o r i 算法是一种最有影响的挖掘频繁项目集的算法 事务数据的多隶属聚类问题研究 a s 9 4 。a p r i o r i 算法利用了一个层次顺序搜索的循环方法来完成频繁项集的挖掘 工作。这一循环方法就是利用k - 项集来产生( k + 1 ) 项集。具体做法是：首先找出频 繁1 项集，记为厶，然后利用厶来产生频繁2 - 项集三：，不断如此循环下去直到 无法发现更多的频繁k - 项集为止。 为提高按层次搜索并产生相应频繁项集的处理效率，a p n o f i 算法利用了一个 重要的性质，即a p r i o r i 性质来帮助有效缩小频繁集的搜索空间。所谓a p r i o r i 性 质是指：频繁项集的所有非空子集都必须也是频繁的。a p r i o r i 性质基于如下观察： 根据定义，如果项集i 不满足最小支持阀值，则i 不是频繁的。如果项a 添加到 i 则结果集( 即，u a ) 也不可能是频繁的。因为结果集不可能比i 更频繁出现。 使用a p r i o r i 算法产生频繁项集，主要分为两步，一步称为连接步，另一步称为剪 枝步。 ( 1 ) 连接步：为找出l k ，能过丘一，与自己连接产生候选k 项集的集合。该 候选项集的集合记作为c 。设，和，：是丘一，中的项集，【，】表示，。的第j 项。 为方便描述，假定事务项集中的项按字典次序排序。执行连接k lp - 日厶_ l ，其 中l k 。的元素是可连接的条件是它们前( k 一2 ) 个元素相同也就是说，t 一，的 元素 ， 和 ，： 是可 连 接 的条件是 ( t d q - - i ：【l d ( 2 】= 屯 2 d “瞳一2 】= 如【七一2 d “【七一l 】 如k l d ，其中 “陋一i 】 ，：k l d 是简单地保证不产生重复。连接和，：产生的结果项集是 ( ，1 【1 】， 2 1 z 陆一l 】f ：陆一l d 。 ( 2 ) 剪枝步：设q 是厶的超集，也就是说，它的成员可以是也可以不是频 繁的，但所有的频繁k 项集都包含在c 。中。扫描数据库，确定g 中每个候选 项的计数，从而确定厶( 根据定义，计数值不小于最小支持度计数的所有候 选项是频繁的，而频繁的候选项属于厶) 。然而，c 。可能很大，这样所涉及 的计算量就很大。为压缩q ，可以用以下办法使用a p r i o r i 性质：任何频繁的 事务数据的多隶属聚类问题研究 ( k - 1 ) 项集都不可能是频繁k 项集的子集。因此，如果一个候选k - 项集的( k 1 ) 子集不在工。中，则候选集也就不可能是频繁的，从而可以由c 中删除。 a p r i o r i 的第一步是找出频繁1 - 项集的集合厶，然后在循环中，