（计算机软件与理论专业论文）基于枚举树的最大子空间聚类算法研究.pdf

基于枚举树的最大子空间聚类算法研究 计算机软件与理论 硕士生：黄志兰 指导教师：印鉴教授 摘要 子空间聚类是一种专门处理高维数据的方法，它可以有效地从高维数据中发 现聚类。自底向上的子空间聚类算法如c l i q u e 、e n c l u e s 等，几乎可以找出 子空间中的所有聚类。然而，由于密度的向下闭包特性，高维子空间中的聚类会 被转录到低维子空间中，使得算法的聚类结果具有很高的冗余度，不利于用户理 解。针对此问题，j i n z el i u 等人提出了合并相似聚类以生成最大子空间聚类的方 法，该方法大大减少了聚类的冗余度，但是作为一种后处理算法，其精度和处理 速度严重受制于c l i q u e 等聚类算法。针对这一问题，本文提出了一种新的基 于枚举树的最大子空间聚类算法m s c ( m a x i m a ls u b s p a c ec l u s t e r i n g ) ，算法在聚 类的过程中，直接生成最大子空间中的聚类。m s c 用枚举树表示子空间，根据 子空间中聚类分布的单调性，对枚举树进行剪枝和回溯，通过集合的交运算生成 聚类。在合成数据集上的对比实验测试表明m s c 具有聚类速度快，精度高，结 果好理解等优点，其精度和效率优于c l i q u e 算法。 关键词：聚类，予空间聚类，最大子空间聚类，枚举树 r e s e a r c ho nm a x i m a ls u b s p a c ec l u s t e r i n ga l g o r i t h mb a s e do n e n u m e r a t i o nt h e c o m p u t e rs o f t w a r ea n dt h e o r i e s n a m e ：h u a n g z l a i l a n s u p e r v i s o r ：y mj i a np r o f e s s o r a b s t r a c t s u b s p a c ec l u s t e r i n gi so n eo ft h eb e s ta p p r o a c h e sf o rd i s c o v e r i n gm e a n i n g f u l c l u s t e r si nh i g hd i m e n s i o n a ls p a c e b o t t o m u ps u b s p a e ec l u s t e r i n ga l g o r i t h m ss u c ha s c l i q u ea n de n c l u s t e n dt of i n dm o s to ft h ec l u s t e r si nt h es u b s p a c e s h o w e v e r , b e c a u s eo ft h ed o w n w a r dc l o s u r ep r o p e r t yo fd e n s i t y , c l u s t e r si nh i g hd i m e n s i o n a l s p a c em a yb et r a a r i b e do n t om u l t i p l ed i s t i n c tm a x i m a lc l u s t e r sb yp r o j e c t i n go n t o d i f f e r e n ts u b s p a c e s 。t h u s , t h e s ea l g o r i t h m su s u a l l yp r o d u c ec l u s t e r so fg r e a t r e d u n d a n c y j i n z el i ua n dh i sp a r t n e r sp r o p o s e dan e wa p p r o a c ht or e v e a lt r u e s u b s p a c ec l u s t e r si nh i g hd i n l e n s i o u s t h r o u g hm e r g i n gc l u s t e r sg e n e r a t e db ye x i s t i n g s u b s p a c ec l u s t e r i n ga l g o r i t h m sl i k ec l q u e ，t h e i ra l g o r i t h mo n l yg e n e r a t e sd u s t e r si n m a x i m a ls u b s p a c e s t h u s ，r e d u n d a n c i e sa r er e m o v e da n dt h er e s u l t i n gc l u s t e r sa r e m u c hm o r eu n d e r s t a n d a b l e h o w e v e r , 船ap o s t - p r o c e s s i n gm e t h o d t h i sa l g o r i t h m s a c c u r a c ya n de f f i c i e n c ya r eg r e a t l ya f f e c t e db yt h ep r e - c l u s t e r i n ga l g o r i t h m s i nt h i s p a p e rw ep r o p o s ean e ws u b s p a c ec l u s t e r i n ga l g o r i t h mm s c ( m a xs u b s p a c e c l u s t e r i n g ) w h i c hi sb a s e do ne n u m e r a t i o nt r e ea n do n l yf m d sm a x i m a ls u b s p a e e c l u s t e r s b ye n u m e r a t i n ga l ls u b s p a e e s m s cc a nf i n da l ld u s t e r si nm a x i m a l m b s p a c e se f f i c i e n t l y a n di tn e e d st os c a i ld a t a b a s eo n l yo n c e t h u st h ea l g o r i t h mi s v e r ye f f i c i e n ta n dw i t hh i g ha c c u r a c y e x p e r i m e n t so ns y n t h e t i cd a t a s e th a v ep r o v e d t h a tm s cd e f e a t sc l i q u ei nb o t ha c c u r a c ya n de f f i c i e n c y k e yw o r d slc l u s t e r i n g , s u b s p a c ec l u s t e r i n g , m a x i m a ls u b s p a c ec l u s t e r i n g ， e n u m e r a t i o nt r e e 引言 子空间聚类是一种专门用于处理高维数据的聚类分析方法，它能够有效地挖 掘出隐藏在高维数据中的聚类及其所在的子空问。作为聚类分析中的一个重要分 支，子空间聚类方法已经被广泛研究了十几年。目前已经形成了许多有效的子空 问聚类算法，按照搜索策略，这些算法可以分为自顶向下和自底向上两种。自项 向下予空间聚类算法形成对输入数据的划分，一个数据对象只能属于一个子空间 中的聚类。自底向上子空问聚类算法则形成重叠的聚类，即一个数据对象可以同 时属于一个或多个子空间中的聚类，对许多应用而言这种聚类结果更有意义。 自底向上的子空间聚类算法如c l i q u e 1 、e n c l u e s 2 等几乎可以发现子 空间中的所有聚类，因此通常具有比较高的精度。然而，由于密度的向下闭包特 性，高维子空间中的聚类会被转录到低维子空间中，使得算法的聚类结果具有很 高的冗余度，不利于用户理解。为了减少聚类的冗余度，j i n z el i u 等人在文献【3 】 中提出了一种通过贪心搜索策略合并相似聚类以生成最大子空间聚类的方法，该 方法对c l i q u e 等子空间聚类算法的结果进行处理，是一种后处理方法，因此 其精度和处理速度都严重受制于c l i q l r e 等子空间聚类算法。 针对这一问题，借用数据挖掘技术中查找最大频繁项目集的思想，本文提出 了一种新的基于集合枚举树的最大子空间聚类算法m s c ( m a x i m a ls u b s p a c e c l u s t e r i n g ) 。m s c 算法在聚类的过程中，直接生成最大子空间中的聚类。它用 枚举树表示子空间，根据子空间中聚类分布的单调性，对枚举树进行剪枝和回溯， 通过集合的交运算生成聚类。在合成数据集上的对比实验表明m s c 具有聚类速度 快，精度高，结果好理解等优点，其精度和效率优于c l i q u e 算法。 本文的研究意义在于：研究了自底向上子空间聚类算法中聚类结果的冗余问 题：考察了国内外对该问题的研究现状，分析了对该问题解决的不足之处；结合 集合枚举树和子空间聚类的特性，提出了基于枚举树的最大子空间聚类算法 ( m s c ) ，该算法在聚类过程中对结果进行筛选以降低聚类冗余度；最后在合成数 据集上对m s c 和c l i q u e 算法进行了对比试验，证明了m s c 无论在运行效率还是 在最终结果上都优于c l i q u e 。 本文以下章节的内容安排如下：第一章为绪论，简要介绍了课题的相关技术 和国内外研究现状；第二章简要介绍了传统的聚类算法，分析了高维数据中聚类 的问题，介绍了子空间聚类的基本原理和方法；第三章分析了自底向上子空间聚 类算法中聚类的冗余度问题，提出了仅挖掘最大子空间聚类的m s c 算法；第四章 给出了i t s c 算法和c l i q u e 算法的对比实验结果及分析；第五章为总结和下一步 工作。 第1 章绪论 数据挖掘是一种新兴的智能数据分析技术，它能从海量的实际应用数据中发 现隐藏于其中的有用的信息和知识，并供决策者使用。作为一个多学科的交叉应 用领域，数据挖掘技术在各行各业的决策支持活动中，都扮演着重要的角色。本 章将对数据挖掘以及数据挖掘中的关键技术聚类分析进行简单的介绍，并分 析了聚类中的特殊问题高维聚类，以及国内外对高维聚类的研究现状。 1 1 数据挖掘概述 信息技术和数据库技术的迅猛发展，使得人们可以方便的搜集和存储大量的 数据，各领域的信息量也因此而急速地膨胀着。面对大规模的海量数据，传统的 数据分析工具如数据库查询、统计分析等，无法有效的获得数据之间的内在关系 和隐含的信息，人们正逐步陷入“数据丰富，知识贫乏”的尴尬境地 4 。为了 摆脱这一境地，人们迫切需要一种技术，它能够将巨大数据资源转换为有用的知 识和信息资源，以帮助进行各种科学决策。这种对强有力数据分析工具的迫切需 求使得数据挖掘技术应运而生。数据挖掘( d a t am i n i n g ) 就是从大量的、不完全 的、有噪声的、模糊的、随机的实际应用数据中提取隐含在其中的、人们事先不 知道的、但又是潜在有用的信息和知识的过程 5 。它是一门跨学科的技术，统 计学、数据库技术、机器学习、模式识别、人工智能、可视化技术都在其中起着 重要作用。数据挖掘作为一个新兴的多学科交叉应用领域，正在各行各业的决策 支持活动中扮演着越来越重要的角色 6 。 数据挖掘又称为数据库中的知识发现( k n o w l e d g ed i s c o v e r yf r o m d a t a b a s e ，简称l ( d d ) ，是一个从大量数据中挖掘出未知的、有价值的模式或规 律等知识的复杂过程 7 。它对数据进行分析，并在此基础上建立对数据特性和 数据之问关系进行描述的模式。数据挖掘是一个包含多个处理步骤的知识发现全 过程，一般包括5 个步骤：数据集成与清洗、选择与转换、数据挖掘、模型的评 估、知识表示 4 数据集成( d a t ai n t e g r a t i o n ) 将多文件或多数据库运行环境中的数据进 行合并；数据清洗删除数据中的噪声和不一致数据； 数据选择( d a t as e l e c t i o n ) 将与分析任务相关的数据从数据库中抽取出 来； 数据转换( d a t at r a n s f o r m a t i o n ) 通过执行概括或聚集等操作将数据转 换成适合于挖掘的格式； 数据挖掘( d a t am i n i n g ) 步骤运用适当的方法从数据中抽取模式； 2 基于枚举树的最大子空间聚类算法研究 模式评估( p a t t e r ne v a l u a t i o n ) 基于一些趣味性标准识别真正有趣的代 表知识的模式； 知识表示( k n o w l e d g ep r e s e n t a t i o n ) 利用可视化技术和知识表现技术将 从数据中挖掘到的知识呈现给用户。 数据集成、数据清洗、数据选择、数据转换是数据挖掘过程中的数据准备阶 段。整个知识挖掘的全过程如图1 - 1 所示。由图中可看出，狭义数据挖掘只是整 个知识挖掘过程( 1 【d d ) 中的一个主要步骤，然而目前在工业界、媒体、数据库 研究领域中，数据挖掘已经被广义地用来表示整个知识挖掘的过程 6 。 图1 - 1 知识挖掘全过程示意图 数据挖掘所处理的数据种类繁多，它们的主要来源是：关系数据库里的结构 化数据；文本、图像、视频等非结构化或半结构化数据；以及分布在网络上的异 构型数据等 4 。而数据挖掘的结果就是我们所说的知识，这些知识必须是用户 感兴趣的、可接受的、可理解的、可运用的、并支持特定发现的问题。数据挖掘 所获得的知识类型包括：定性概念描述、定性对比概念描述、关联规则、分类规 则、聚类知识、趋势描述知识以及偏差分析知识等 6 。一个成熟的数据挖掘系 统通常提供多种数据挖掘的知识。 经过几十年来不断的发展，数据挖掘技术已经逐渐成熟，出现了许多有效的 算法。常用的数据挖掘方法，主要分为统计方法、机器学习方法、神经网络方法 和数据库方法i s 。 统计学的方法是数据挖掘的经典方法，也是数据挖掘中最成熟的一种方 法，它包括回归分析、判别分析、聚类分析、探索性分析等。用户可以 基于枚举树的最大子空间聚类算法研究 利用这些统计分析技术检测异常数据，然后利用各种统计模型和数学模 型对这些数据进行解释，从而发现隐藏在这些数据背后的市场规律和商 业机会。例如，可以使用统计分析工具寻求最佳商业机会，增加市场份 额和利润；利用全面质量管理程序，提高产品或服务的质量，使客户更 加满意；通过对流水线产品制造的调整或企业业务过程的重整，增加利 润 6 。目前，统计方法己经在数据挖掘中得到广泛的应用。 机器学习方法中包括归纳学习、基于范例学习、遗传算法、粗糙集等。 神经网络方法具有处理非线性数据和含噪声数据的能力，最早由心理学 家和神经生物学家提出，旨在寻求开发和测试神经的计算模拟。典型的 神经网络模型主要分三大类，其中以感知机、b p 反向传播模型、函数型 网络为代表的前馈式神经网络模型，主要用于分类、预测和模式识别。 神经网络的最大优点是它能精确地对复杂问题进行预测，使用神经网络 的预测技术在金融市场和制造业被广泛采用。 数据库方法主要是多维数据分析或0 l a p 方法 4 1 2 数据挖掘中的聚类分析 聚类分析是数据挖掘领域的一项重要任务，在许多领域有广泛的应用，包括 模式识别、数据分析、图像处理以及市场研究等。聚类分析是根据“使各聚类簇 ( c l u s t e r ) 内部数据对象问的相似度最大化和各聚类簇间对象相似度最小化”的 基本聚类分析原则，以及度量数据对象间相似度的计算公式，将物理或抽象的集 合分组成为由类似的对象组成的多个类的过程。由聚类所生成的簇是一组数据对 象的集合，这些对象与同一个簇中的对象彼此相似，与其它簇中的对象彼此相异 4 。聚类分析所获得的聚类簇可以视为由归属同一类别的数据对象所构成的集 合。通过聚类，人们能够识别密集的和稀疏的区域，因而发现全局的分布模式， 以及数据属性之间的有趣的相互关系。例如：通过对在一个商场具有较大购买力 的顾客的居住地进行聚类分析，可以帮助商场主管针对相应顾客群采取有针对性 的营销策略 4 。 经过多年的研究，目前已经形成了许多经典、有效的聚类算法。这些聚类算 法大致可以分为五种：划分方法、层次方法、基于密度的方法、基于网格的方法 和基于模型的方法。在进行聚类分析时，需要根据实际应用所涉及的数据类型、 聚类的耳的以及具体的应用要求来选择合适的聚类算法。通常认为，若利用聚类 分析作为描述性或探索性的工具，则可以使用若干聚类算法对同一个数据集进行 处理，以观察可能获得的有关( 数据特征) 描述 4 】。 传统聚类算法在数据处理时需要用到全部的维，通常用基于数据集所有维的 4 基于枚举树的最大子空间聚类算法研究 各种距离函数作为对象间相似性的度量。而在高维数据集中，由于数据矩阵的稀 疏性，数据对象间的距离几乎是相同的，导致以距离为相似性度量的传统聚类算 法完全失效，这就是所谓“高维诅咒”现象。此外，在处理大规模高维数据时， 数据通常无法一次性读入内存，计算机内存容量也成为许多算法的瓶颈。 “高维诅咒”现象的存在和计算机内存容量的限制，使得传统的聚类算法无 法有效处理高维数据。高维聚类问题也开始成为人们广泛关注的问题。后来人们 发现，在高维数据中聚类总是存在于由一部分属性构成的属性子集里，这些属性 子集或称维子集就是子空间。由于高维数据中，聚类可能分布在相同的子空间中， 也可能分布在不同的子空间中，子空间聚类的主要任务就是挖掘存在于子空间中 的聚类和聚类所在的属性集。予空间聚类可以看成是传统聚类的一个扩展，但不 同于传统的聚类算法，子空间聚类算法一般具有的两个目标：寻找隐藏在子空间 中的簇和其所在的子空间。 1 3 国内外研究现状 虽然聚类分析具有很长的历史，但是国际上对高维聚类算法的研究相对较 晚，大致起始于2 0 世纪9 0 年代中期，较早的研究成果是 9 中提出的一种基于 超图划分的聚类方法，此外是一些基于网格的方法和基于小波变换的方法。然而， 在众多人员的共同努力下，经过十几年的研究，目前已经形成了许多各不相同的 子空间聚类算法。按照不同的技术，子空间聚类算法大致可以分为：基于网格的 聚类算法，如c l i q u e e l 、e n c l u e s 2 、m a f i a 1 0 、d 0 c 1 1 ；基于投影的聚类 算法，如p r 0 c l u s 1 2 、o r c l u s 1 3 、p r e d e c o n 1 4 ；基于模式的子空间聚类算 法，如p c l u s t e r 1 5 、m a p l e 1 6 根据不同的搜索策略，目前的子空间聚类算法大致可以分为自顶向下算法和 自底向上算法两种 1 7 。自底向上的子空间聚类算法如c l i q u e 、e n c l u e s 、m a f i a 、 c b f 1 8 、f i n d i t 1 9 等，主要是基于网格的聚类算法，它们利用子空间聚类中 密度的向下闭包特性，从低维到高维逐步搜索子空间中的聚类，它们几乎可以找 出子空间中的所有聚类。自顶向下子空间聚类算法如p p r o c l u s 、o r c l u s ，p r e d e c o n 等，主要是通过迭代搜索的办法，对聚类的权重进行调整，最终形成对数据集的 k + 1 个划分。自底向上子空间聚类算法产生重叠的聚类即；一个数据点可以同 时属于多个聚类，对许多应用而言，这种结果远比对数据集进行划分有意义。例 如，一个基因可能有多个功能，每个功能可能由一个特定的新陈代谢方法表现， 因此发现一个基因属于多个基因聚类在生物上是有意义的 3 。 由于密度的向下闭包特性，在自底向上子空间聚类方法中，高维子空间中的 聚类通常会被转录到低维子空间中，使得算法的聚类结果具有很高的冗余度，不 基于枚举树的最大子空间聚类算法研究 利于用户理解。针对这一问题。j i n z el i u 等人在 3 中提出了合并聚类，以生 成最大子空间聚类的方法，该方法大大减少了聚类的冗余度，但是作为一种后处 理算法，其精度和处理速度严重受制于c l i q u e 等聚类算法。因此，它是一个有 效但并不优秀的解决方法。 针对这一闯题，借用数据挖掘技术中查找最大频繁项目集的思想，本文提出 了一种新的基于集合枚举树的最大子空间聚类算法m s c ( _ m a x i m a ls u b s p a c e c l u s t e r i n g ) 。m s c 算法在聚类的过程中，直接生成最大子空间中的聚类。它用 枚举树表示子空间，根据子空间中聚类分布的单调性，对枚举树进行剪枝和回溯， 通过集合的交运算生成聚类。 1 4 本章小结 在这一章中，我们对课题的相关技术进行了简要的介绍。首先简要介绍了数 据挖掘技术，接着对数据挖掘中的关键技术聚类分析进行简单的介绍，分析 了聚类中的特殊问题高维聚类，以及国内外对高维聚类的研究现状，最后文 章分析了自底向上子空间聚类算法中存在的聚类冗余度问题以及国内外对该问 题的研究现状。 第2 章聚类和子空间聚类概述 经过多年的研究，聚类分析已经成为数据挖掘领域一项较为成熟的技术，但 是传统聚类算法在进行聚类时需要用到基于全维空间的距离函数作为数据对象 间的相似性度量，当数据维数很高时，数据点间的距离几乎相同，导致传统聚类 算法在处理高维数据时完全失效。因此，亟需一种新的技术来对高维数据进行聚 类。子空间聚类技术就是在这样的背景下被广泛研究起来的，它专门用于处理高 维数据。通过不同的搜索策略，子空间聚类算法能有效的挖掘出隐藏在高维数据 中的聚类及其所在的子空间。在本章，本文将对聚类技术和子空间聚类技术进行 概括性的介绍，重点说明子空间聚类的背景、原理和常用算法。 2 1 聚类概述 2 1 1 聚类的定义 聚类是数据挖掘中用来发现数据分布和模式的一项重要技术，在许多领域包 括统计学、生物学和机器学习等都有研究和应用。通过聚类，人们能够识别密集 的和稀疏的区域，因而发现全局的数据分布模式，以及数据属性之间有趣的相互 关系 4 。利用这些模式和相互关系，人们可以在许多领域里发现新事物、创造 新价值。例如：在商务上，聚类能帮助市场分析人员从客户信息中发现不同的客 户群，并用购买模式来刻画不同的客户群的特征；在生物学上，聚类能用于推导 植物和动物的分类，对基因进行分类，获得对种群中固有结构的认识。随着对聚 类研究的不断深入，聚类分析的重要意义也越来越为人们所认识。 在数据挖掘中，聚类是将一群( s e t ) 物理的或抽象的对象，根据它们之间的 相似程度，分为若干组( g r o u p ) ，使得相似的对象构成一组的过程。它的形式化 定义如下： 定义2 1 给定一个数据集合v v l , v 2 ，v n ，v i ( i f f i l , 2 ，舢为数据点，根据 数据点间的相似度将数据集合分成k 组： c i ，c 2 ，c d ，使得c i = v j j l ，v f ，v 缸i ( i - l ，2 ，固，且ij ：! g = v 的过程称为聚类。c i ( i = l , 2 ，妁称为簇。 在许多应用中，一个聚类中所有对象常常被当作一个对象来进行处理。通常， 进行聚类分析前用户并不知道数据集的特征，因此聚类分析是一种无指导的 ( u n s u p e r v i s e d ) 学习过程。在一个广义的数据挖掘过程中，聚类分析往往被作为最 初的步骤，用于获得对数据分布和聚集特性的初步了解，以在此基础上进行其他 数据挖掘和规则发现的处理。当然，聚类分析也可以作为一个单独使用的工具， 来帮助分析数据的分布、了解各数据类的特征、确定所感兴趣的数据类以便作进 7 基于枚举树的最大子空间聚类算法研究 一步的分析。 2 1 2 聚类的相似性度量 由上节给出的聚类定义可以看出，相似性度量是聚类定义中的一个核心概 念，它是数据聚类的根本依据，决定了数据点之间在性态上的亲疏远近关系，对 聚类的最终形态起着决定性作用。因此，为了使聚类过程在定量的范畴上得以实 现，同时保证聚类结果的正确性，必须恰当地对数据点之问的相似性度量加以选 择。在聚类分析中，相似性度量的选择主要依据输入数据的变量类型，不同类型 的变量适用不同的相似性度量。数据变量主要有以下几种类型：区间标度变量， 二元变量，标称型变量，序数型变量，比例标度型变量和混合类型的变量【4 】。 区间标度是最常见的变量类型，许多变量如序数型变量都可转换成区间标度 型变量，因此人们对区间标度型变量的相似性度量方法研究得最为广泛。有两种 常用的区间标度型变量相似性度量方法，分别是基于相似系数的和基于距离的相 似性度量。基于相似系数的相似性度量描述数据点之间的相似程度，而基于距离 的相似性度量则描述数据点之间的差异程度。 基于相似系数的相似性度量通常具有如下三个特点：取值在1 和l 之间；具 有反对称性；数据点与其自身的相似性最大。这类度量方法主要有余弦相似性度 量( c o s i n es i m i l a r i t y ) 、相关系数( c o r r e l a t i o n ) 和皮尔逊相关系数( p e a r s o n c o r r e l a t i o n ) 三种，它们各有其优缺点和适用范围。余弦相似性度量仅与向量的 方向有关，对向量空间的旋转保持不变，随向量空间的线性转换而改变【2 0 】，它 常用来描述概念型数据点之间的相似性关系。相关系数是关于向量标准差的夹角 余弦，表示两个向量线性相关的程度。皮尔逊相关系数主要是评价两个变量线性 关系的强弱，它从相关系数中派生而来，适用与r 型聚类 2 0 】 基于距离的相似性度量将数据集映射到一个线性空间上，通过对空间赋予某 种距离概念而在两个数据对象之间建立适当的距离关系，这些距离关系通常满足 如下条件：非负性、对称性和三角不等式。常用的基于距离的度量主要包括欧几 里德距离、曼哈坦距离、明考斯基距离、马氏距离、兰氏距离和海明距离等。最 常用的是欧几里德距离，但是它趋向于形成超球面形状的聚类；明考斯基距离受 数据集量纲影响，有着较大取值和取值变化大的属性趋向于支配其他属性【2 0 ； 曼哈坦距离则趋向于形成超矩形形状的聚类；海明距离定义了两个等长的字符串 间的相似性，常用于文本聚类问题。 可见，各相似性度量方法都有其特点，聚类时应充分考虑数据集的具体特点 和相似性度量的特点及其适用情况，进行合理的选择。当然也可以同时采用多种 距离进行对比实验，选结果最佳的作为度量方法。 基于枚举树的最大子空间聚类算法研究 2 1 3 传统的聚类算法 目前存在着大量的聚类算法，常用的聚类算法大致可以分为以下几种：划分 方法( p a 击t i 啦m 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 ) 、基于网格的方法( g r i d - b a s e dm e t h o d ) 和基于模型的方 法( m o d e l - b a s e dm e t h o d ) 。这些方法各有其优缺点和适用范围，没有哪一种可以 取代另一种，具体算法的选择主要取决于数据的类型、聚类的目的和应用。 划分方法是在数据挖掘出现以前就已经很流行的聚类算法。对给定的数据集 d 及要生成聚类数目k ，划分方法通过迭代复位技术将数据集划分为k 个子集， 其中每个子集代表一个聚类( k 如) ，这些聚类满足如下要求；每个聚类至少包含 一个数据点；每个数据点必须且只能属于某一个聚类；属于相同聚类簇中的数据 点最相似；属于不同聚类簇的数据点最不相似。根据对聚类簇描述方法的不同， 划分方法可以分为两种：以质心代表簇的k - m e a n s 算法和以聚类中最靠近聚类中 心的对象来代表簇的k - m e d o i d s 算法。k - m e a n s 算法采用质心代表聚类簇，聚类 结果易被噪声数据( 孤立点) 扭曲。k - m e a d o i d s 用有代表性的对象代表簇，可 以解决噪声数据对聚类结果的扭曲。比较著名的k - m c d o i d s 算法有p a m 2 1 、 c l a r a 2 2 及c l a r a n s 2 3 】。划分方法具有算法简单、易于理解、收敛速度快 等优点，但是它倾向于识别凸形分布且大小相近密度相近的聚类，而不能发现分 布形状比较复杂的聚类。此外，算法要求输入聚类数目k ，需要用户合理地估计， 初始中心的选择和噪声数据也对聚类结果有很大的影响。 层次聚类方法使用连续的嵌套划分，按照一定的相似性判断标准对给定的数 据集进行层次的分解，并最终将数据对象组成一棵聚类的树。根据分解方向，层 次聚类方法可以分为凝聚的( 自底向上) 和分裂的( 自顶向下) 的两种类型【4 】。 层次聚类算法简洁，易于理解和应用。但是它们仅适用于大小相似且对象分布为 球形的聚类，因为类大小和对象的分布形状会影响聚类结果，在对象分布形状比 较特殊的情况下，算法可能会产生错误的结果。此外，算法每一次类的合并或分 解都是不可逆的，并直接影响着下一步的合并或分解，即：一旦一个合并或分裂 被执行，就不能修正。这样，如果某一步的合并或分解不理想，最终形成聚类结 果的质量就可能很低。最近的研究主要集中于综合优化的多阶段聚类技术，以及 凝聚层次聚类和迭代复位方法的集成等。主要的层次聚类算法有b i r c h 2 4 、 c u r e 2 5 、r o c k 2 6 和c h a m e l e o n 2 7 等。 基于密度的聚类方法以局部数据特征作为聚类的判断标准，把聚类簇看成是 数据空间中被低密度区域分隔开的高密度区域。由于采用密度而非相似度来刻画 数据集的形状，基于密度的聚类方法可以发现任意形状的聚类，并且一个聚类中 对象的分布也可以是任意的，它还能够有效去除数据集中的嗓声。常见的基于密 度的聚类算法有d b s c a n 2 8 】、o p t i c s 2 9 和d e n c l u e 3 0 等。 基于枚举树的最大子空间聚类算法研究 基于网格的聚类方法通过一个网格结构，将数据空间量化成为有限数目的单 元，聚类的操作均在网格上进行，因此处理速度快，且处理时间独立于数据对象 的数目。s r n , i o 3 1 、w a v e c l u s t e r 3 2 和c l i q u e 是典型的基于网格的聚类算法， 它们也是最早的子空间聚类算法。 基于模型的聚类方法试图将给定数据与某个数学模型进行最佳拟合，它们通 常假设数据是根据潜在的概率分布生成的【6 】。基于模型的聚类方法主要有统计 学方法和神经网络方法两种。统计学方法通过概率参数来确定聚类，并用概率描 述来表示聚类。神经网络聚类方法则将每个聚类描述成一个标本，标本作为聚类 的原型不一定对应于具体的数据对象，算法根据某些距离度量，将新的数据对象 分配到标本与其最相似的簇。神经网络聚类方法效率较低且极为复杂，不宜直接 用于大型数据库。 2 2 子空间聚类的背景 2 2 1 高维聚类问题 随着聚类分析技术在w e b 挖掘、空间数据库、基因分析、文本聚类和客户 分析等领域的应用不断深入，高维数据空间中的聚类问题逐渐被人们所认识和重 视，高维聚类问题也成为当前聚类分析研究的重点。虽然聚类分析具有很长的历 史，但是对高维聚类算法的研究起步相对比较晚，目前还停留在研究阶段，并未 得到广泛应用，高维聚类算法也有许多亟待完善的地方。 与普通数据相比，高维数据中描述数据特征的属性集通常很大，少则包含几 十个属性，多则包含数百个，文本数据甚至包含几千个属性。当维数很高时，数 据的分布规律经常会呈现出反常的特征：如噪声增多、数据稀疏、距离定义不再 有效等，这种高维异常现象在数据挖掘中被称为“高维诅咒( c u r s eo f d i m e n s i o n a l i t y ) ”【3 3 。高维诅咒现象的出现，使得许多在低维数据空间中性能优 越的传统聚类算法不再有效。这是因为，在低维数据空间中有效的聚类算法一般 都使用欧氏距离等距离函数作为相似性度量，由于相似性在高维情况下不具有传 递性，使得距离函数失效。例如基于距离的k m e a n s 聚类方法，需要计算簇的均 值，但在高维情况下，按距离公式计算的簇的均值很接近，聚类操作由于无法明 确区分簇的中心而无法进行。此外，传统聚类算法一般都是基于某种空间层次数 据结构、数据分割或分区等，它们在空间维数较低时才具有较高的存取效率，当 维数很高时存取效率会显著下降，传统聚类算法的性能也会下降。例如，基于数 据分区的索引结构在高维空间中性能急剧下降，使得采用这种结构的聚类算法 ( 如d b s c a n ) 效率明显下降甚至不能运行。研究表明【3 3 】，在数据维数高于2 0 时，索引结构的性能下降，基于索引方法的传统聚类算法在性能上还不如顺序扫 基于枚举树的最大子空问聚类算法研究 描的处理方法。 高维数据的这些特点引起了人们的广泛关注，也为聚类分析技术带来了新的 挑战和目标。如何从这些海量的高维数据里寻找出有意义的聚类，并用一种可解 释的且有意义的方式把它们表示出来，成为高维聚类问题的主要任务。 2 2 2 高维聚类技术 高维数据的异常使人们相信，维数过高是致使高维聚类成为难题的罪魁祸 首。针对这问题，人们提出了利用特征选择和特征抽取等数据降维技术对高维 数据进行处理的方法，如 3 4 儿3 5 。 特征抽取试图通过将数据集的原始属性进行线性组合，以实现在较少维上对 数据集的汇总。常用的特征抽取方法有p c a ( p r i n c i p l ec o m p o n e n ta n a l y s i s ) 3 6 和s 、，d ( s i n g u l a rv a l u ed e c o m p o s i t i o n ) 3 t 。特征抽取可以保持原始数据集中 数据对象间的相对距离，因此可以有效地发现数据集中的松散结构。特征抽取通 常作为高维聚类的预处理步骤，它通过创建原始属性的线性组合来创建新的属 性，从而实现数据降维，将传统的聚类算法用在降维后的数据集上即可完成高维 数据聚类。由于特征抽取并没有移除数据集中的不相关属性，在处理聚类被大量 不相关属性隐藏了的数据集时，特征抽取方法往往失效。再者。特征抽取使用了 属性组合的方式来形成新的属性，导致聚类结果难以解释。 特征选择试图查找数据集中与挖掘任务最为相关的属性子集，它是数据降维 问题中一种被广泛采用的有效技术。特征选择通过一定的策略搜索属性子集，并 采用一定的标准对属性子集进行评价，最终给出对挖掘任务而言最优或次优的属 性子集。对属性子集进行搜索的最常用策略是贪心的顺序搜索策略，包括前向搜 索和后向搜索两种 3 5 。特征选择的属性子集评价标准主要有两种基本模型，分 别是w r a p p e r 模型和f i l t e r 模型。w r a p p e r 模型用最终要使用的数据挖掘算法 对特征选择后的数据集进行评价，而f i l t e r 模型则先于数据挖掘，通过检查数 据的内在特性来评价属性子集。在无指导的聚类分析中，基于f i l t e r 模型的特 征选择通常选用信息熵作为属性子集的评价标准，认为在包含聚类的数据空间 中，信息熵总是比较低的。用特征选择方法对数据进行预处理虽然可以降低维数， 但是它也会导致许多信息的丢失。此外，特征选择方法为整个数据集选定一个属 性子集，对许多数据集而言，不同的聚类簇可能会与一组不同的维相关，因此特 征选择不可能在不丢失信息的情况下同时剪去大量的维。下面的例子将充分说明 特征选择在高维聚类时的限制。图2 - l 是一个三维空间的两个不同交叉投影 1 2 ，在数据集中有两个模式，第一个模式对应于x - y 投影中密集的点构成的集 合，第二个投影则对应于x - z 投影中密集点构成的集合。由于数据集的每一维都 至少与一个聚类相关，传统的特征选择算法没有办法选取出一个包含所有聚类的 属性子集，而在全部属性上的聚类并不能发现这两个模式，因为它们总会在某一 基于枚举树的最大子空间聚类算法研究 维上被分散，因此特征选择方法不能有效地对这些数据进行处理。 y 犯“ x 蜘x d 曲 a 数据集的x y 投影b 数据集的x _ z 投影 图2 - 1 特征选择方法的反例 特征抽取和特征选择方法的这些弱点促使了人们对高维聚类的进一步研究。 后来人们发现，在高维数据中聚类簇总是存在于由一部分相关属性构成的属性子 集里，这些属性子集或维子集通常被称为子空间。不同的聚类簇可能分布在相同 的子空间中，也可能分布在不同的子空间中。这样在高维数据中，聚类分析的主 要任务就被“简化”成为：挖掘存在于子空间中的聚类簇和聚类簇所在的子空间。 为实现这个任务，人们提出了被称为子空间聚类的高维聚类分析技术。子空间聚 类方法是特征选择方法的扩展，它试图寻找在不同子空间中的聚类。与特征选择 相同，子空间聚类算法也需要一个搜索策略和一个评价标准，它通过一定的搜索 策略在数据集的不同子空间中搜索聚类簇。经过多年的研究，目前已经形成了许 多子空间聚类算法，这些子空间聚类算法能有效的处理高维数据。在本章的以下 几节，我们将对子空间聚类进行介绍。 2 3 子空间聚类的原理 子空间聚类是在数据集的不同子空间中搜索聚类簇的过程，子空间聚类的结 果包括搜索到的聚类簇及其所在的子空间。与传统聚类算法一样，子空间聚类算 法也是一个搜索的过程。但是子空间聚类算法需要进行两个搜索过程，一个是搜 索聚类簇所在的子空间，即相关属性的集合；另一个则是要搜索存在于子空间中 的簇集。在高维数据中，由于可能的子空间数目通常很大，要求高效的搜索算法。 对搜索策略的不同选择，将产生不同的聚类偏差，同时也将影响聚类算法对数据 分布的假设。因此，搜索策略是子空间聚类方法中的一个重要因素。根据不同的 子空间搜索策略，现有的子空间聚类算法可以分为自底向上子空间搜索算法和自 顶向下子空间搜索算法两种e 1 7 1 。 自底向上算法也称为基于密度的子空间聚类算法，它把数据空间中的每一维 基于枚举树的最大子空问聚类算法研究 划分成一定数量的网格，使用支持度( 落到某子空间中的点的比例) 来表示子空 间的密度，仅挖掘密度超过指定阈值的子空间。自底向上算法利用密度的向下闭 包性质来缩小搜索空间，采用类似a p r i o r i 算法的搜索方法。密度的向下闭包性 质是：如果k 维子空间中存在稠密区域，那么在投影到该子空间的所有k 1 维 子空间中，也一定存在稠密区域；相反，如果给定的k 1 维子空间中不存在稠密 区域，则其任意的k 维空间也不存在稠密区域。算法首先按一定的策略( 如相 等间隔等) 为每一维创建一个柱形图，然后选取密度超过某一个阈值的分箱( 间 隔) 作为稠密单元。候选k - 维子空间由具有稠密单元的k 1 维子空间构造。当 没有新的稠密单元被发现时，算法停止。最后将相邻的稠密单元连接起来，就形 成了子空间中的聚类簇。根据分箱的策略，自底向上子空间聚类算法可以进一步 划分为基于静态网格的算法和基于自适应网格的算法。基于静态网格的算法没有 考虑每一维的具体数据分布情况，而直接将每一维划分为大小相同的间隔。最早 的静态网格聚类算法是c aa g r a w a l 等人在 1 】中提出的c l i q u e 算法，e n c l u s 也是一种经典的静态网格聚类算法。基于自适应网格的聚类算法，使用数据驱动 策略决定每一维分箱的割点，考虑每一维各自的数据分布特点，以形成较少分箱 数目，进而加快聚类过程。因此，自适应网格的聚类算法可以看作是对静态网格 聚类算法的改进。m a f i a 和c b f 是这类算法的两个经典代表。 自底向上算法会产生重叠的结果簇集，每个对象都可以同时属于零个或多个 结果簇中。聚类结果对分箱个数和密度阈值很敏感，对没有先验知识的用户来说， 这两个参数通常是很难设置的。此外，算法在聚类过程中可能会将一个大聚类错 误的分解成多个小聚类，因此聚类精度比较低。 自顶向下算法也称基于投影的子空间聚类算法，它们采用的是迭代搜索的办 法，对不同聚类簇赋予不同的权重。算法首先在全空间给出对聚类划分的一个初 始近似，并对各个聚类簇赋予相同的权重，然后为每个聚类簇的每一维赋予一个 权重，通过迭代对权重进行更新，更新后的权重将在下一次迭代时用于生成新的 聚类。由于算法通常需要进行多次迭代，并且每一次迭代都要在全维空间中对数 据集进行聚类，因此需要很大时空开销。这类算法通常会采用抽样技术以降低算 法的时空复杂性。c c a g r a w a l 等人在【1 2 】中提出的p r o c l u s 算法，是第一个 自顶向下的子空间聚类算法。c o s a l 3 8 算法是另外一种不同的自顶向下子空间 聚类算法，它采取不同的策略，利用每一个对象的k 个最近邻居，来决定该对象 每一维的权重。 自项向下算法最终形成对原始数据集的k + 1 个划分( k 个聚类簇和一个 o