（计算机应用技术专业论文）基于高维空间的聚类技术研究.pdf

中北大学学位论文 摘要 随着计算机应用的普及，信息系统产生的数据量日益增大，迫切需要高效的 数据挖掘工具，从大量原始数据中寻找有价值的知识模式。聚类分析是数据挖掘 的重要工具之一。如何正确处理维度达到数百、数千的数据集合，如何从高维数 掘集中寻找潜在的、自然存在的聚类簇，这是当前聚类分析研究的热点。 本文针对聚类分析的热点和难点问题高维聚类展开研究，目的是寻求有 效的高维聚类算法，以及有效的高维数据离群点发现和聚类结果表达等技术。本 文研究了高维聚类分析的关键技术，主要工作有： l 、针对高维数据空间下聚类簇的分布特点，改进了一种基于子空间的映射 聚类算法。本文应用柏努利分布表示二元数据的分布特征，把基于有限混合柏努 利分布模型与e m ( e x p e c t a t i o n m a x i m i z a t i o n ) 算法相结合的高维二元数据映射聚 类方法，一方面发现各种子空间下的聚类簇，一方面为每个簇指定相应的属性子 集，实现了不同子空间下聚类簇的挖掘。 2 、从映射聚类算法出发，设计了一种高维空间离群点发现的算法。首先， 运用一种映射聚类的算法寻找数据点相对密集的子空间。为了尽快找到这些数据 簇及其相应的子空间，可以对数据进行二元处理，即把全部数据集转化为二元数 掘，然后运用二元数据映射聚类方法找到映射簇及相关联的属性集合；第二，根 据属性熵的定义，对每个属性集合的每属性判别其离散程度；第三，在离散程 度较大的属性集合中确定离群点：第四，进行簇间属性集合的交叉分析，发现跨 予窄j 剐的离群点。 3 、仔细研究基于粗集理论的高维聚类结果表达方法。认为聚类簇必须以有 效的方式加以表达，相对完整地传达聚类运算的结果，以利于人工交互，完成知 识发现的后续操作。因此，聚类结果的可表达性、可解释性是聚类算法必须考虑 的关键技术。本文运用粗集( r o u g hs e t ) 理论，引入属性空间上的粗糙集理论，考 虑数据在对象空间和属性空间的不同特性，使聚类结果特征从对象空间和属性空 间两个角度得到了综合反映，并以规则的形式表示聚类知识，既可全面表示数据 聚类结构，也可实现聚类增量计算。 关键词：数据挖掘高维聚类映射聚类离群点检测聚类结果表示粗集理论 中北大学学位论文 t h er e s e a r c h e s0 1 3r e l a t e dt ok e yt e c h n o l o g i e sa m o n g c l u s t e r i n gb a s e d o nh i g h d i m e n s i o n a ld a t as p a c e a b s t r a c t h e 、，a l ic h e nl i c h a o w i t ht h ew i d eu s a g eo fi n f o r m a t i o nt e c h n o l o g y , d a t ag e n e r a t e df r o mv a r i e s i n f o r m a t i o ns y s t e m sb e c o m em o r ea n dm o r e ，a n dt h eh i g h e re f f i c i e n c yd a t am i n i n g t o o l sw a sn e e d e dt of i n dv a l u a b l ek n o w l e d g ep a t t e r n s c l u s t e r i n ga n a l y s i si s a i m p o r t a n tm e t h o di nd a t am i n i n g i ti s ad i s c o v e r yp r o c e s st h a tg r o u p sas e to fd a t a s u c ht h a tt h ei n t r a c l u s t e rs i m i l a r i t yi sm a x i m i z e da n dt h ei n t e r - c l u s t e rs i m i i a r i t yi s m i n i m i z e d c l u s t e r i n go f d a t ai nal a r g ed i m e n s i o ns p a c ei so fag r e a ti n t e r e s ti nm a n y d a t am i n i n ga p p l i c a t i o n s w i t hh i 渗d i m e n s i o n a l i t yd a t as e t s ，h o wt of i n dt h el a t e n t a n dn a t u r ec l u s t e r si sm o r ed i m c u l ta n dn e e dt ob er e s o l v e d t h er e s e a r c h e so i tr e l a t e dt ok e yt e c h n o l o g i e sa m o n gc l u s t e r i n gb a s e do n h i g h d i m e n s i o n a ld a t as p a c ea r em a d ei nt h ed i s s e r t a t i o n i ti sf o c u s e do nt h eh i 曲 e f f i c i e n c yc l u s t e r i n ga l g o r i t h m s ，o u t l i n e rd e t e c t i n ga l g o r i t h m s ，c l u s t e r i n g r e s u l t p r e s e n t a t i o nm e t h o d s ，a n ds o0 n i t i st h eb a s i cw o r kt od e f i n et h es i m i l a r i t yf o r h i g h d i m e n s i o n a ld a t ao b j e c t s b a s e do nt h ei m p r m ，e ds i m i l a r i t rd e f i n i t i o nm e t h o d ， t h ek e yt e c t m o l o g i e sh a v eb e e ns t u d i e di nt h i sd i s s e r t a t i o n t h em o s t l ya n di n n o v a t i v e w o r ka sf o l l o w i n g ： 1 a i m e da tt h ed i s t r i b u t i o np r o p e r t yo ft h eh i g hd i m e n s i o n a ld a t a s e t s ，ap r o j e c t e d c l u s t e r i n gm e t h o di sp r o m p t e df o rs u b s p a c ec l u s t e r s + t h ep r o j e c t e dc l u s t e r i n gu s et h e d e f i n i t i o no fs u b s p a c ec l u s t e r i n g ，t of i n dn a t u r ec l u s t e r si na n yl o c a lo ff h l l d i m e n s i o n a ls p a c e t h eb e r n o u l l id i s t r i b u t i o n si su s e dt oi n t e r p r e tt h ep r o p e r t yo f t h e b i n a r yd a t as e t ，a n dap r o j e c t e dc l u s t e r i n ga l g o r i t h mi sp r o p o s e df o rb i n a r yd a t as e t 州t hl a r g ea t t r i b u t e sb a s e do nf i n i t em i x t u r e so f b e m o u l l id i s t r i b u t i o n sa n de m a l g o r i t h m t h i sa l g o r i t h mc a nf i n ds e r i e so f c l u s t e r si ns u b s p a c ea sw e t la ss u i t a b l e a t t r i b u t e ss u b s e t ，a c h i e v e st h eg o a lo fc l u s t e r i n gi nv a i l e ss u b s p a c e s 2 ao u t l i e rd e t e c t i n gm e t h o db a s e do nh i g hd i m e n s i o n a ld a t as p a c ei sa d v a n c e d f r o mt h ep r o j e c t e dc l u s t e r i n ga l g o r i t h m i ti si m p o r t a n tt od e t e c to u t l i e r si nm a n yd a t a m i n i n ga p p l i c a t i o n san e wp r o j e c t e do u t l i e rd e t e c t i n ga l g o r i t h mi sc o m b i n e dw i t ht h e i d e ao fs u b s p a c ec l u s t e r i n g f i r s t ，s u b s p a c ew i t hr e l a t i v e l yh i g hd e n s eu n i tw i l lb e f i n d e du s i n gap r o j e c t e dc l u s t e r i n gm e t h o d i tc a l lb es p e e du pf o rt h ec l u s t e r i n gs t e pi f 中北大学学位论文 t h eo r i g i n a ld a t ac a np r e p r o c e s s e d 轮b eb i n a r y s e c o n d , t h ed i s p e r s e dd e g r e eo f e a c h a t t r i b u t ei sc o m p u t e di ns u b s p a c eb a s e do nt h ed e f i n i t i o no ft h ea t t r i b u t ee n t r o p y n i f d t h ea t t r i b u t es e t st h a th a v em o r ed i s p e r s e dd e g r e ea r ei d e n t i f i e da n do u t l i e r p o i m s w i l lb ed e t e c t e dd e p e n do nt h e s ea t t r i b u t es e t s 。 3 ac l u s t e r i n gr e s u l tp r e s e n t a t i o nm e t h o di sp r o m p t s e df o rh i 曲d i m e n s i o n a ld a t a s p a c eb a s e do nt h et h e o r yo f r o u g hs e t s i n c et h ei n t e r n a ls t r u c t u r eo f d a t as e ti s u n k n o w nb e f o r ec l u s t e r i n g ，t h ec l u s t e r ss h o u l db ep r e s e n t e dp r o p e r l y , s ou s e rc a ng e t t h er e s u l tc o m p l e t e l ya n d a c c o m p l i s ht h et a s ko f k n o w l e d g ed i s c o v e r i n g j 强e p r e s e n t a t i o na n de x p l a n a t i o no ft h ec l u s t e r i n gr e s u l tp l a yai m p o r t a n tr o l ei nt h e t e c h n o l o g yo f c l u s t e r i n g 。b a s e do nt h es t u d yo f r o u g h s e t 。t h er o u g hs e tt h e o r yo n a t t r i b u t es p a c ei si m p o r t e da n dan e wc l u s t e r i n gr e s u l tp r e s e n t a t i o nm e t h o d si s a d v a n c e d ，w i t ht h ed i f f e r e n tp r o p e r t ye o n s i d e r a t i o no ft h eo b j e c ts p a c ea n da t t r i b u t e s p a c eo f h i 婶d i m e n s i o n a ld a t as e t 确i sm e t h o dc a l lp r o v i d er e l a t i v e l ys y n t h e s i s i n f o r m a t i o no fc l u s t e r i n gr e s u l tf r o mo b j e c ts p a c ea n da t t r i b u t es p a c e ，r e f l e c tt h e c l u s t e r i n gk n o w l e d g ew i t hr u l e s e n a b l e sr i s e r st oc a p t u r em o r eu s e f u lp a t t e r na n d r e h o l dt h ei n t e r n a ls t r u c t u r eo f d a t as e t s k e yw o r d s ：d a t am i n i n g h i g h d i m e n s i o n a lc l u s t e r i n g ，p r o j e c t e dc l u s t e r i n g ，o u t l i e r d e t e c t i n g ，p r e s e n t a t i o no fc l u s t e r i n gr e s u l t ，r o u g hs e t 本人声明 我声明，本论文及其研究工作是由本人在导师指导下独立完成的，在完成论文 时所利用的切资料均已在参考文献中列出。 签名：私支矾 日期：矽心；f g 中北大学学位论文 1 1 数据库知识发现 第一章高维聚类技术综述 1 1 1 数据库知识发现的产生与发展 6 0 年代术期以来，随着计算机应用的普及和数据处理在计算机应用中所占比重的上 升，数掘库技术得到了迅速发展。数据库技术与计算机网络通信已经成为当前计算机应 用中两个最重要的基础领域。计算机的一些重要应用，如管理信息系统、办公自动化技 术、计算机辅助设计、专家系统等，大都离不开这两个基本技术。 数据库技术是在传统文件技术的基础上发展起来的。数据库技术区别于传统文件技 术的特点有：数据共享性、数据独立性、数据操作和控制手段的一致性等。在当前流行 的数据库管理系统中，采用的数据模型主要有层次模型、网状模型和关系模型三种。7 0 年代中期，关系数据模型渐渐成为占主导地位的数据模型。由于关系数据库的模型结构 简单，逻辑物理界面清晰，具有较强的集合处理功能，使得数据库应用系统开发的效率 大大提高。 目前，数据库的应用己经触及到人类生活的各个方面，银行、交通、法律、商业、 工业、农业、教育、科技、军事、医疗卫生等各行各业都在应用着数据库。据统计1 9 8 9 年时全世界数掘库总量为5 0 0 万个，而且数量以每2 0 个月翻一番的速度增长着，但是 对数据库中数掘的丌发应用还主要是检索查询，效率很低，往往很多数据还没来得及分 析就己经过时了。9 0 年代地球探测卫星每天产生的数据，超过以前所有航测数据的总和， 即使一个人以最快的速度刻不停地工作，也要花费几年时间才能浏览卫星一天内产生 的图片，生物学领域研究的数以百万计的遗传基因，世界各国定期进行的人口普查，国 土资源地理信息，铁路动态调度控制，公安司法部门的案件处理，都涉及巨量的数据， 相当数量的数据具有很强的时效性，数据的价值随着时间的推移而迅速降低。 数据收集与维护的最终目的是为了供人们使用。简单的数据查询或统计虽然可以满 足某些低层次的需求，但人们更为需要的是从大量数掘资源中挖掘出对各类决策有指导 意义的般知识。它们是对大量数据的高度浓缩和抽象，是对数据整体的全面而深刻的 认识，这些经过智能分析和表示的数据才是有价值和竞争力的社会资源。 中北大学学位论文 k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ) 技术就是在这样一个时代背景下产生的。它 的宗旨就是在数据库中分析处理大量的数据，发现有用的知识，为用户提供所需问题的 答案。数据库知识发现比较公认的定义是：从数据集中识别出可信的、有效的、新颖的、 潜在有用的以及最终可理解模式的高级处理过程。“数据库知识发现”一词第一次出现 是1 9 8 9 年8 月在美国底特律召开的第1 1 届国际人工智能联合会议的专题研讨会上。1 9 9 1 年、1 9 9 3 年和1 9 9 4 年又分别举行过数据库知识发现专题研讨会。由于参加会议的人数 逐年增多，所以从1 9 9 5 年丌始，每年都要举办一次数据库知识发现国际会议。 1 j 2k d d 的一般机理和理论基础 1 一般机理 推理、联想和学习是人类智能活动的三大主要功能，推理和联想的功能必须通过学 习月能不断完善、充实，因而学习是一切智能活动的基础。使计算机系统具有某些程度 的学习能力，能够模拟人类的学习活动，一直是人工智能领域所追求的目标。 储存在数据库中的结构化数据，是对现实世界某种程度上的符号化和数据化的抽 象，是对现实世界事物某一程度、某一侧面的映射，所使用的抽象方式和抽象层次主要 取决于具体的应用模式。考虑到数据采集过程中可能引人误差，因而要求数据库至少能 够在总体上反映现实世界，否则数据库就不能使用了。数据库中的元组可以认为是一些 低抽象程度的判断。 2 主要研究方法的特点 k d d 的主要实施对象是关系数据库。这是因为关系数据库具有归化的组织结构、 一体化的查询语言、方便的用户接口、能进行集合处理的优点，而且在各行业中应用最 广泛。另外，关系数掘库中各关系之间、各属性之间都是平等的，有利于知识发现过程 中的并行计算。由于k d d 的研究对象比较特殊，一般都是大型数据库，其中的数据容 量往往是一般人工智能系统所不能比拟的，因此，k d d 的研究方法及技术策略就有其 鲜明的特色。 首先，在研究上遵循认识的基本过程，即实践一认识一再实践再认识。k d d 一改过 去以演绎逻辑为主的策略，在本质上以归纳逻辑为主，采用从个别到一股，从感性到理 性的知识抽象过程。当然，在知识发现过程中，也不能完全抛弃演绎，而是归纳和演绎 相结合。 中北大学学位论文 其次，k d d 的技术策略也有其特点。把握事物的规则性是人脑思维的重要功能， 精确数学就是这种功能的产物和表现。这种定量的分析和计算在以往的知识发现过程中 应用得较多，特别在统计学领域。但是，另一方面，在定量基础上的定性归纳有时也能 够深刻地反映问题的本质，并且用较少的代价就能传递足够的信息，对复杂事物做出高 效率的判断和推理。所以在知识发现过程中，把定性分析和定量分析相结合也是非常重 要的，既采用定量的计算来分析和处理数据，也充分重视定性思维和描述的作用。具体 来说，知识发现系统应该用语言值来把握过于复杂无法数值化的量的规则性，通过比较 束反映事物在量的规则性上的差异。 3 抽取知识的类型和表示 ( 1 ) 依赖关系：若其中一项的数据可以预测另一项的数据即a 一 b ，则称这两项存 在依赖关系。当确定的依赖关系不存在时，可以附加不确定度量：a ( 0 9 5 ) b 。这一 类知识可用于数掘库知识的归一化、查询优化，还可用于最小化决策树、搜索数据特例 等，甚至可以被系统中其它的发现算法使用。 ( 2 ) 分类知识：数据子类的标识知识。子类可由某一现有属性确定，也可由附加 的领域知识束定义，k d d 系统基于分类知识的发现任务促进了交互式新型聚类算法的 发展即处理器计算能力、用户知识及可视化工具的有机集成。 ( 3 ) 掐述性知识：关于类别特征的概括性描述。主要包括两类知识：特征描述知 识和区分性知识。特征描述知识是指本类数据所共有的；区分性知识是指本类区别于它 类的特性。 ( 4 ) 偏差性知识：关于类别差异的描述。包括：标准类中的特例；各类边缘外的 孤立点；时序关系上单属性值和集合取值的不同；实际观测值和系统预测值间的显著差 别等。 1 1 3k d d 系统的基本框架 k d d 系统的特点 ( 1 ) 正确理解用户的发现目标要求： ( 2 ) 帮助用户全面了解整个数据库的静态结构和已经具备的领域知识，导引用户 选择并补充新的与发现目标有关的领域知识和知识的解释； ( 3 ) 可以发现多种知识，能够满足用户复杂的发现要求； 中北大学学位论文 程 ( 4 ) 有较高的运行效率； ( 5 ) 用户能够随时了解发现过程的进展情况，可以在相当程度上动态控制发现过 ( 6 ) 能够以用户乐于接受的形式，表达与解释所发现的知识。 k d d 系统的基本框架( 如图1 1 ) 1 1 4k d d 的主要任务 图11k d d 系统框架 k d d 的核心部分是数据模式的抽耿，即通过数据挖掘完成各种模式的抽取。其主要 任务是：分类知i ： 发现、数掘总结、数掘聚类、关联规则发现、序列模式发现、依赖关 系或依赖模型发现、异常发现和趋势预测等。 分类知识发现是数掘挖掘中最常见的任务，其目的在于根据样本数据寻求相应的分 类规则，然后根据获得的规则来确定某一非样本个体或对象是否属于某一特定的组或 类。在这种分类知讨 发现中，样本个体或对象的类标记是己知的。数据挖掘的任务在于 从样本数据的属性中发现个体或对象分类的一般规则，从而根据该规则对非样本数据对 中北大学学位论文 象进行分类应用。 数据聚类是用于发现在数据库中未知的数据类。这种数据类划分的依据是叫勿以类 聚”，即按个体或数据对象日j 的相似性，将研究对象划分为若干类。由于在数据挖掘之 前，数据类划分的数量和类型均是未知的，因此在数据挖掘后需要对挖掘结果进行合理 的分析与解释。 关联规则发现是在数据库中寻找数据对象间的关联模式，例如“在购买个人电脑的 顾客中，有9 0 的顾客购买了打印机”就是一种关联模式。关联模式发现在研究和应用 的早期主要用于零售业交易数据分析，以便进行物品更台理的摆放，最终提高销售量。 因此，该方法有时也直接称为“购物篮分析”。 数据总结是将数据库中的大量相关数据从较低概念层次抽象到较高概念层次的过 程。计数、求和、求平均值、求最大值和最小值等计算都是数据总结的具体化。由于数 掘库中的数据所包含的信息往往是最原始的、最基本的信息，而有时人们需要从较高的 层次上浏览数掘，这就要求从不同的层次上对数据进行总结以满足分析需要。 序列模式发现是在数据库中寻找基于一段时间区间的关联模式，例如“在某一时间 购买个人电脑的所有顾客中，有6 0 的顾客会在三个月内购买应用软件”，这就是一个 序列模式。序列模式同关联模式非常相似，区别在于序列模式表述的是基于时间的关系， 而不是关于数掘对象间的关系。因此，有时也称为基于时间的关联规则发现。 依赖关系或依赖模型发现是通过列数掘库中数据的分析，获取数据间的某种因果联 系。这种因果联系既可能是内在的某种概率分布关系的描述，也可能是数据对象问存在 的确定的函数关系。 异常发现用于发现数据中存在的偏差或异常。趋势预测是根据数据库中的历史信息 对未来信启、做出估计。 】2 聚类分析 聚类分析( c l u s t e r i n g ) 是k d d 的主要任务之一，用于发现在数据库中未知的对象类。 通过聚类过程形成的每个组称为一个聚类簇( c l u s t e r ) 。在数据挖掘之前，对象类划分的 数据量与类型均是未知的，因此在数据挖掘后一般需要对数据挖掘结果进行台理的分析 与解释。聚类是现实世界中普遍存在的现象，其应用也非常广泛。据文献所载，在破产 预测、手写体字符的计算机识别、交通管理与塞车状况预测等方面都有过成功应用。 在2 0 世纪7 0 年代，对聚类分析已经有了比较深入的研究。聚类的方法主要有统计 中北大学学位论文 学方法和机器学习的方法。在统计学中，聚类一般称为聚类分析，主要研究基于几何距 离的聚类。在使用上，首先定义多维空间，在多维空间中计算对象间的距离，然后以距 离作为对象间的相似性判别标准。在机器学习中，聚类称为无监督学习( u n s u p e r v i s e d s t u d y ) ，主要体现在聚类学习的数据对象没有类别标记，需要由聚类学习算法自动计算。 近十年左右，随着k d d 技术的兴起，对聚类的研究掀起了新的热潮。除了统计学 和人工智能领域的研究人员以外，数据库领域的人员也加入了研究行列，并取得了可喜 的成果。从数据库知t 发现的角度，对聚类闽题的研究是从大量的数据集中智能地、自 动地抽取出有价值的聚类知识，本文称其为聚类知识发现。 1 2 1 聚类问题的描述及主要方法 所谓聚类，是指将数据对象分组成为多个类或簇( c l u s t e r ) ，在同一个类中的对象之 间具有较高的相似度，而不同类中的对象差别较大。聚类问题的一般描述是【1 ： 爿= ( 爿，一x 。) 是n 个数据对象的集合，c = ( c ，c 2 ，c 。) 是k 个数据对象 集合或组；c ，u c 2u u c = x 、cn c ，= o ( i ) ，c ，o ( i = 1 ，k ) ，即通过聚类算法， f v 个数据对象分别组成k 个数据组，每个组至少包含一个对象，每个对象必须属于且只 属于个组( 在模糊聚类中，上述条件有所不同) 。 聚类的结果可以表示为 u = ( ”a ) ”。k ，其中 “2 j 当值为1 时，指f 对象属于组k ，当值为0 时，f 不属于组k 。 * = 1 i = 1 , 2 矗a ，；七= 1 , 2 ，3 ，足 = l “，女 o ，1 ，i = l 、2 。n ；k = 1 , 2 ，k 聚类算法一般有四种： ( 1 ) 分割方法( p a r t i t i o n i n gm e t h o d ) 给定要构建的划分数目( 即分组的数目) k ， 分割方法根据一定的规则对所有对象确定个初始划分，然后采用一种迭代的重定位技 术，使数据对象在划分之间来回移动，以达到划分最优。k 一平均算法( k - m e a n s ) 和k 中心点算法f k m e d o i d ) 是划分方法的两个代表。 ( 2 ) 层次方法( h i e r a r c h i c a lm e t h o d )层次聚类又可分为两个方向，一是自底向上 的凝聚方法，初始把所有对象看作单独的分组，然后相继合并相近或相似的对象或组， 中北大学学位论文 直到符合一个终止条件为止；一是自顶向下的分裂方法，初始把所有对象看作一个分组， 然后逐步把大簇分裂为小簇，直到划分为足个组或符合其它终止条件为止。层次聚类方 法同分割聚类方法的不同之处在于：对于分割聚类方法，一般需要一种迭代控制策略， 使得整个聚类逐步优化；层次聚类方法并不是试图寻找最佳的聚类结果，而是按照一定 的相似性判断标准，合并最相似的部分，或者分割最不相似的两个部分。前者从每个对 象作为一个类丌始，逐层向上进行聚结；后者从所有的对象归属在惟一的一个类中开始， 迓层向下分解。c u r e 和b i r c h 算法是层次方法的两个代表。 ( 3 ) 基于密度的方法( d e n s i t y b a s e dm e t h o d )基于密度的聚类方法以局部数据特 征作为聚类的判断标准，其主要思想是，只要临近区域的密度( 对象或数据的数目) 超 过某个闽值，就继续聚类。类被看作是一个数据区域，在该区域内对象是密集的，对象 稀疏的区域将各个类分隔丌来。多数基于密度的聚类算法形成的聚类形状可以是任意 的，并且一个类中对象的分布也可以是任意的。基于密度的聚类方法研究是非常活跃的 一个领域，近几年提出了许多新的算法。如1 9 9 6 年提出的d b s c a n ( d e n s i t y b a s e d s p a t i a lc l u s t e r i n go fa p p l i c a t i o n sw i t hn o i s e ) 算法及其改进算法、1 9 9 8 年提出的 w a v e c l u s t e r 算法、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 ) 算法、cl i q u e ( c l u s t e r i n gi n q u e s t ) 算法和1 9 9 9 年提出的o p t i c s ( o r d e r i n gp o i n t st oi d e n t i f yt h ec l u s t e r i n gs t r u c t u r e ) 算法等。w a v e c l u s t e r 、d e n c l u e 和c l i q u e 算法在基于密度的同时，还基于网格。 ( 4 ) 基于网格的方法( g r i d - b a s em e t h o d ) 基于网格的方法把对象空间量化为有限数 目的单元，形成一个网格结构，把对数据对象的考察转化为对网格空间的考察，使其独 立于数据对象数目，处理速度很快。s t i n g 是基于网络方法的典型例子。 用于数据挖掘的聚类算法，一般从以下方面考察其特性： 能够处理的数据属性类型： 对大型数据库的扩展处理能力； 对高维数据的处理能力； 对不规则形状簇的发现能力： 对奇异点的处理能力： 时间复杂度； 对数据输入顺序的依赖性： 对象从属于聚类簇的模糊性； 7 中北大学学位论文 对先验知识和用户定义参数的依赖性： 聚类结果的可表达性。 就某个特定的聚类方法而言，往往是多种聚类思想融合的结果，可能在上述特性中 的若干项目较为突出，但无法满足所有特性要求。从类型上看，也不能简单将其归结为 上述某类别。而且，不同的聚类算法也可以进行结合，结台后的算法可能更有效。近几 年来随着对聚类知识发现研究的不断深入，新的聚类算法不断涌现，但每种方法都有 其优点和特色，同时也存在一定的不足和局限。实际的应用需求对聚类任务提出了更新 的要求，聚类方法的研究也面临着新的挑战。 1 2 2 高维聚类问题 近年来，随着聚类分析应用的领域扩展和深入，高维聚类问题成为当前聚类分析研 究的重点。典型的高维聚类应用如w e b 挖掘、文本聚类、搜索弓l 擎、客户分析等。 研究表明2 1 ，在数据维数高于2 0 时，传统聚类分析和索引方法的性能会急骤下降， 甚至无法完成聚类任务。比如，许多空问聚类算法会依赖于空间数据库的索引，以便于 快速搜索最近邻。索引的性能优劣直接受“维度困扰( d i m e n s i o n a l i t yc u r s e ) ”的影响。 在维度小于1 6 ( d 2 0 时，它们的性能会降低到顺序搜索的水平。高维数据聚类的难点在于 3 l ：距离函数难 于定义。聚类操作的基础是数据对象之删相似性的度量，相似度高的对象归为一类。低 维空叫中经常使用欧氏距离等距离函数柬度量相似性，但在高维情况下由于相似性没有 传递性，距离函数失效。必须重新考虑新的度量数据对象相似性的标准或准则。基于 距离的聚类方法，经常需要计算簇的均值或近邻，但在高维情况下，按距离计算的簇的 均值会很接近，聚类操作由于无法明确区分簇的中心而无法进行。由于维数很高，传 统聚类算法的计算复杂度会很高，其应用受到很大局限性。 对高维数据的聚类，主要有三类算法【2 】：属性转换；子空间聚类；协同聚类。 近年来，一些新的高维聚类研究成果逐步呈现，如基于超图技术和定义专门的稀疏特征 向量的算法。 1 、属性转换( d i m e n s i o n a l i t yt r a n s f o r m a t i o n s ) 对于高维数据，可以采用属性转换或属性约简方法，以减少数据维度，然后利用传 统的聚类算法在较低维的数据空间中完成聚类操作，如主成分分析( p c a ) f 4 】、多维缩 中北大学学位论文 放( m d s ) 1 5 、自组织映射网络( s o m ) n 小波分析 7 1 等，都是普遍应用的降维方法。 在多变量统计分析中，p c a 经常被采用以降低数据维度1 9 】1 1 0 1 。它首先计算原始数据的协 方差矩阵和该矩阵的前k 个特征向量，然后把原始数据映射这k 个主特征方向上，映射 后的数据维很低，可以应用传统聚类算法如k - m e a n s 、a u t o c l a s s 等。p c a 在确定k 值时 有较大的难度，若设得太小，将使数据丢失很多有用的信息；若设得太大，虽然可以保 留较多的特征信息，但对传统聚类算法来说维数太高，无法有效地聚类。另外，p c a 的 计算量大，内存需求高，均为o ( m 2 ) ，当m 值很大时，其算法复杂度无法接受。 在信息获取领域，经常用以减少维度的技术是奇异值分解( s i n g u l a rv a l u e d e c o m p o s i t i o n ，s v d ) 。类似p c a 的潜在语义分析( l a t e n ts e m a n t i ci n d e x i n g ，l s l ) 【8 l 是与p c a 类似的一种属性约简方法。与p c a 使用协方差矩阵的特征向量不同的是，l s i 直接使用原始数掘的奇异值分解技术。由于它不再计算协方差矩阵，其对内存和c p u 的需求比p c a 较少。 傅立叶低频调谐( l o w f r e q u e n c yf o u r i e rh a r m o n i c s ) 与帕赛伐尔理论f p a r s e v a l s t h e o r e m ) 相结合，以及小波变换等多种转换技术 ，已成功应用于时间序列的分析。 另较著名的方法是自组织映射网络s o f m ( t h ek o h o n e ns e l f - o r g a n i z i n gf e a t u r e m a p l ，它是种基于神经网络把高维数据映射到低维特征空闻的技术。其主要缺点是无 法确定其完成的属性转换是否有效，即无法进行质量评价。另外，当数据的维数非常高 时，训练网络的收敛速度极慢，影响f 常使用。 但是，降维后的噪音数据与正常数据之问的差别缩小，聚类质量无法保障。另外， 降维技术的使用虽然缩小了数据维度空削，但其可解释性、可理解性较差，可能会丢失 重要的聚类信息，其结果的表达和理解存在着一定的难度。总之，基于属性转换的降维 技术对极高维数据的处理有着很大的局限性，无法满足当前高维聚类应用的发展需要。 2 、子空问聚类( s u b s p a c ec l u s t e r i n g ) 子空间聚类是从另一角度处理高维数掘。由于直接在高维空间中寻找簇( c l u s t e r s ) 很困难，有些算法就把原始数据空间划分为不同的子空间，从子空间考察聚类的存在。 c l i q u e ( c l u s t e r i n gi nq u e s t ) 算 去1 1 2 1 是一种基于数值属性子空间聚类的高维聚类基 础算法。它的主要特征是：基于密度聚类与基于网格聚类相结合；采用与关联规则挖掘 中a p r i o r i 算法类似的维归约原理：采用m d l 规则选择适合的子空间：通过d n f 表示 法加强聚类结果的可表达性。其中心思想如下： 中北大学学位论文 多维数据点在数据空j 剞中通常是不均衡分布的。c l i q u e 区分空间中的稀疏和拥挤 区域，以发现数据集合的全局分布模式。如果一个区域中包含的数据点数超过了某个输 入参数，则认为该区域是密集的。相连的密集区域或单元的最大集合，定义为类或簇。 c l i q u e 能自动地发现高密度聚类存在的最大子空f 日j 。 c l i q u e 对数掘元组的输入顺序不敏感，无需假设任何规范的数据分布。它随输入 数据的大小线性扩展，当数据的维数增加时具有良好的可伸缩性。如果q 是候选空间的 最大维数，密集空间产生的复杂度是o ( c o n s t q + q n ) 。识别簇的工作量是密集单元数目的 二次平方。由于方法简化，聚类结果的精确性不是很高。 e n c l u s 算法继承了c l i q u e 算法的主要精神，但采用了一种不同的子空间选择 标准。这种标准来源于信息熵的理论：由属性4 ，爿。构成的子空间，如果其熵 h ( a ，a 。) 小于某个阈值u ，则认为该空问是好的，适合于产生聚类。由于 h ( a a 州) = h ( a a q ) 一h ( a q l a ，a 川) h ( a ，a 。) 则，好的予空删的任何子集同样是好的子空蒯。熵值低的子空间对应于一个区域密 度的倾斜分布。e n c l u s 的计算复杂度高于c l i q u e 。 m a f i a 算法【i 刮对c l i q u e 的改动比较大。它从对数据的遍历开始，在每一维建立 适应网格( a d a p t i v eg r i d s ) 。然后，m a f i a 通过向内存中整块读入数据，使用1 0 0 0 个箱 格计算网格直方，然后合并这些箱格，得到最后的簇或聚类。该算法使用一个称为聚类 优势因子的参数n ，选择数据列密度高于平均密度c t 倍的箱格。从q = l 候选密度区域 ( c a n d i d a t ed e n s eu n i t s ，c d u s ) 开始，该算法递归地向高维处理，每次都包含一次数据 的遍历。邻接的c d u s 被合并入簇，高维簇的适当子集被排除，以便进入下一轮的递归 计算。参数a 与c l i q u e 算法中的全局密度闽值相类似，其默认值为1 5 。研究指出， o 可以在一个单向区i 日j 范围内取一系列的值。如果q 是c d u 的最高维度，m a f i a 的计 算复杂度为0 ( c o n s t 4 + q ) 。 子空旧j 聚类算法中，还有o p t l g r i d 、p r o c l u s 、o r c l u s 等。子空间聚类最大 的弊端是计算的复杂度。当数据维数很高并且要求较精确的聚类结果时，子空间的数目 会急骤增长，对子空i 白j 中簇的搜索就会成为聚类操作的瓶颈，从而使算法失效。 3 、协同聚类( c o c l u s t e r i n g ) 与只进行数据点的聚类相对应，协同聚类从对象属性两个角度同时进行聚类操作， 存数掘点聚类和属性聚类之恻求得一种平衡。如果说前述各种算法只是对矩阵的行进行 中北大学学位论文 聚集的话，那么现在则主要讨论应用一种规范的二元点一属性数据结构对矩阵的列进行 聚集的问题。 假设x 是数据属性和数据对象构成的矩阵，一般称为影响矩阵、关系矩阵、频率矩 阵、可能性矩阵等，无负值元素，其典型应用如反映基因响应的强度、一个w e b 页面 的点击频率或一个仓库罩每项商品的销售数量等。g o v a e r t b 1 于1 9 9 5 年研究了可能性矩 阵表中行列块的同时聚类算法。d h i l l o n 于2 0 0 1 年提出了一种与文本挖掘相关的，基于 二部图( b i p a r t i t eg r a p h s ) 和它们的最小切割的协同代数聚类算法 4 。o y a n a g i 等学者 于2 0 0 1 年提出一种在稀疏二元矩阵中发现相应区域的简单p i n g p o n g 算法1 1 6 ，该算法 通过建立矩阵元素的横向联系重新分布列对行的影响，并反过来进行。 许多研究从属性相似性的度量方面展开对属性的分布式聚类。如果用于数据挖掘的 两个属性( 爿矩阵中的两列) 有相同的分布，则可以删除其中一列，以减少维度。如果 属性根据k u l l b a c k l e r b l e r (