（计算机应用技术专业论文）基于相对熵的投影聚类算法研究.pdf

重庆邮电大学硕士论文 摘要 摘要 聚类就是将数据对象分组成为多个类或簇，在同一个簇中的对象之间 具有较高的相似度，而不同簇中的对象差别较大。相异度是根据描述对象 的属性值来计算的。距离是经常采用的度量方式。 技术进步使得数据收集变得更加简单和快速，从而产生了大量复杂的 高维数据。由于这种数据存在的普遍性，使得对高维聚类算法的研究有着 非常重要的意义。传统的聚类算法受“维灾”的影响在处理高维数据时变 的异常困难，主要表现为索引结果效率低、用于相似性度量的距离函数失 效、聚类描述中存在冗余的维以及算法执行效率低等问题，使得聚类算法 的应用受到很大的局限性。 发现高维空间中存在于不同子空间的聚类问题一般被称为投影聚类 问题。在已有投影聚类算法e p c h ( e f f i c i e n tp r o j e c t i v ec l u s t e r i n gt e c h n i q u e b y h i s t o g r a mc o n s t r u c t i o n ) 的基础上，本文提出了一种基于相对熵的改进算 法r e p c h ( r e l a t i v ee n t r o p yb a s e dp r o j e c t i v e c l u s t e r i n gb yh i s t o g r a m s c o n s t r u c t i o n ) 。在数据分布的特征空间中，将每一个d 维子空间划分成网 格结构。根据网格单元的密度构建每一个d 维子空间的直方图。直方图的 相对熵可以反映子空间中数据的实际分布与平均分布之间的相似度。相对 熵会随着密集区域的减少而单调递增，并逐渐趋近于1 。根据这个原理， 直方图中密集区域和稀疏区域可以被识别。 算法在人工数据集上进行了大量的实验，对算法的聚类质量、性能等 指标进行了测试。与原有的e p c h 算法相比，r e p c h 算法是一种有效的投 影聚类算法，且对数据量及维数有很好的可伸缩性，适用于高维数值数据 聚类。 关键词：聚类分析，高维数据，投影聚类，直方图，相对熵 重庆邮电大学硕士论文 a b s t r a c t a b s t r a c t c l u s t e r i n gi st od i v i d ed a t ao b j e c t si n t os e v e r a lc l a s s e so rc l u s t e r s d a t a o b j e c t sa r es i m i l a rt oo n ea n o t h e rw i t h i nt h es a m ec l u s t e ra n da r ed i s s i m i l a rt o t h eo b j e c t si no t h e rc l u s t e r s d i s s i m i l a r i t yi sc a l c u l a t e da c c o r d i n gt ot h e f e a t u r e so fd a t ao b j e c t s d i s t a n c em e a s u r e sa r ec o m m o n l yu s e df o rc o m p u t i n g t h ed i s s i m i l a r i t yo fo b j c o t s t e c h n o l o g ya d v a n c e s h a v e m a d ed a t ac o l l e c t i o ne a s i e ra n df a s t e r ， r e s u l t i n gi nl a r g e r , m o r ec o m p l e xd a t a s e t sw i t hm a n yo b j e c t sa n dd i m e n s i o n s t h eu n i v e r s a l i t yo f h i g h d i m e n s i o n a ld a t am a k e sr e s e a r c h e so n h i g h d i m e n s i o n a l c l u s t e r i n ga l g o r i t h m sv e r yi m p o r t a n t p r o c e s s i n gh i g h d i m e n s i o n a ld a t ai s e x t r a o r d i n a “l y d i f f i c u l tt ot r a d i t i o n a l c l u s t e r i n g a l g o r i t h m sb e c a u s eo ft h ec u r s eo fd i m e n s i o n a l i t y i ti sm a i n l yp r e s e n t e da s f o l l o w s i n d e xh a sl o wp e r f o r m a n c ef o rh i g h d i m e n s i o n a ld a t a s e t i r r e l e v a n t d i m e n s i o n se x i s ti nt h ec l u s t e r s d i s t a n c em e a s u r e sa r ei n e f f e c t i v e a n d b e c a u s eo fh i g hd i m e n s i o n a l i t y , t h et i m ec o m p l e x i t yo ft r a d i t i o n a lc l u s t e r i n g a l g o r i t h mi sv e r yh i g h t h e s el i m i tt h e i ru s ei na p p l i c a t i o n t od i s c o v e rc l u s t e r se x i s t i n gi nd i f f e r e n ts u b s e to fd i m e n s i o n si su s u a l l y k n o w na st h ep r o j e c t i v ec l u s t e r i n gp r o b l e m b a s e do ne x i s t e dp r o j e c t i v e c l u s t e r i n ga l g o r i t h me p c h ( e f f i c i e n tp r o j e c t i v ec l u s t e r i n gt e c h n i q u eb y h i s t o g r a mc o n s t r u c t i o n ) ，w ep r o p o s ea ni m p r o v e da l g o r i t h mr e p c h ( r e l a t i v e e n t r o p yb a s e dp r o j e c t i v ec l u s t e r i n gb yh i s t o g r a m sc o n s t r u c t i o n ) i nt h e f e a t u r es p a c eo fd a t a s e t ，e a c hs u b s p a c ew i t hdd i m e n s i o n si sd i v i d e di n t og r i d c e l l s t h eh i s t o g r a m so fe a c hdd i m e n s i o n a ls u b s p a c ea r ec r e a t e da c c o r d i n gt o t h ed e n s i t yo fe a c hc e l l t h ev a l u eo fr e l a t i v ee n t r o p yi saq u a n t i t a t i v e m e a s u r eo ft h es i m i l a r i t yb e t w e e nt h ea c t u a ld a t ad i s t r i b u t i o ni ns u b s p a c ea n d au n i f o r md i s t r i b u t i o nw i t ht h es a m en u m b e ro fp o i n t sa n dr a n g eo fv a l u e s t h e r e l a t i v ee n t r o p yo fe a c hh i s t o g r a mw i l li n c r e a s em o n o t o n o u s l ya n d a p p r o a c ht oo n ea l o n gw i t ht h ed e c r e a s eo fd e n s er e g i o n si nt h eh i s t o g r a m d e n s er e g i o na n ds p a r s er e g i o nc a nb er e c o g n i z e db a s e do nt h i sp r i n c i p l e t oe v a l u a t et h ec l u s t e r i n gq u a l i t ya n dp e r f o r m a n c eo fr e p c h ，w em a k e e x t e n s i v eo fe x p e r i m e n t so ns y n t h e t i cd a t a s e t s c o m p a r e dw i t he p c h ，t h e 重庆邮电大学硕士论文 c l u s t e r i n gr e s u l t s s h o wt h a tr e p c hi sa ne f f i c i e n ta n de f f e c t i v ep r o je e t i v e c l u s t e r i n ga l g o r i t h m ，a n dh a sg o o ds e a l a b i l i t yw i t ht h es i z ea n dd i m e n s i o n so f d a t a s e t s oi ti sg o o da tc l u s t e r i n gh i g hd i m e n s i o n a ln u m e r i c a ld a t a s e t s k e yw o r d s ：c l u s t e r i n ga n a l y s i s ，h i g h - d i m e n s i o n a ld a t a ，p r o j e c t e dc l u s t e r , h i s t o g r a m ，r e l a t i v ee n t r o p y i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重废 唑电太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 意。 学位论文作者签名：禹荡 签字日期：二w 7 年彳月te l 学位论文版权使用授权书 本学位论文作者完全了解重庆鲤鱼盍堂有关保留、使用学位论 文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权重庆邮鱼盍堂可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：高舌色 导师躲豫 签字日期：础夕年彳月扩日签字日期：五，叼年6 月j 1 3 重庆邮电大学硕士论文第一章绪论 1 1 研究背景 第一章绪论 随着数据库技术的成熟和数据应用的普及，我们产生和收集数据的能 力已经迅速提高。存储数据的爆炸性增长需要一种新的数据分析技术处理 大量数据，从中抽取有价值的潜在信息。因此，数据挖掘( d a t am i n i n g ) 技 术便应运而生。简单地说，数据挖掘就是从大量数据中提取或“挖掘”知 识【1 1 。 聚类分析是数据挖掘的重要组成部分，是一个在大型数据库中发现数 据集中有意义的子集的描述性任务。聚类算法在数据分析、图象处理、市 场研究和基因表达等领域有着广泛的应用。例如，在基于w e b 的应用中， w e b 日志记录用户对w e b 页的使用模式，通过聚类分析w e b 日志中的用户 规律，可以为电子商务识别潜在客户，提高终端用户的服务质量以及改善 w e b 服务器的性能。在医疗分析中，通过对一组新型疾病聚类，得到每类 疾病的特征描述，就可以对这些疾病进行识别，提高治疗的功效。在生物 学上，聚类应用于基因表达数据，基因表达数据是由基因芯片实验产生的。 如酵母基因芯片实验可产生6 2 2 3 种基因在7 9 种条件下的表达数据。这种 数据可以表示成一个矩阵，每个行对应一个基因，每一列表示一个条件。 每个数值表示一个基因在特定条件下的m r n a 的相对丰度。生物学家意在 通过这种数据找到在特定的条件组合下表现出强烈相似基因集合。聚类还 用于发现空间趋势，即空间数据库中一个或多个非空间属性的变化模式。 在天文学上，研究人员利用聚类分析宇宙仿真系统得到的数据，更好地理 解黑洞形成和进化的物理过程。在这些应用中，数据集合中的数据对象可 能有几十、几百或成千上万个属性。可以将这些对象表示成高维属性空间 中的点或向量，这样就把客观世界中的对象集用高维数据的集合来表示。 随着数据量的增大和维数的增多，传统的聚类算法受“维灾”的影响， 并不能很好的处理大量的高维数据。其中一个原因是，在高维数据集中， 对于确定的数据簇，可能只有很少的维度( 属性) 与之相关。簇内数据在子 空间内是相似的，但在全维空间下有可能无法确定其相似性。因此有必要 针对高维数据的特点和要求提出新的聚类方法。 重庆邮电大学硕士论文第一章绪论 1 2 研究内容 数据挖掘对高维聚类的典型要求可以简单地概括为如下几点：第一， 能发现不同子空间中任意维度的聚类；第二，聚类质量高；第三，具有可 伸缩性；第四，聚类结果是用户可理解的；第五，处理噪声数据的能力强； 第六，用户输入参数少。 本文分析了几种高维聚类算法存在的问题，并在已有高维聚类算法 e p c h 的基础上，提出了一种改进算法r e p c h ，能够更有效的处理高维数 值数据。主要的改进方向有以下四点： 1 ) 参数的相对稳定性。对于不同的数据集合大小，不同的数据分布， 算法中阈值参数值的设置应该相对固定，减少用户负担。 2 ) 密度阈值的设定。聚类中的数据对象无论是正态分布，还是均匀 分布，算法中采用的密度阈值都能够识别该聚类，且不易丢失密 度较小的聚类。 3 ) 冗余的维。算法应该能够识别聚类描述中存在的冗余的维。 4 ) 执行效率。算法的执行效率应该能够适用于大型数据集合。 1 3 论文结构 论文后续部分的组织结构如下： 第二章简要介绍了数据挖掘的定义和功能。对聚类的知识做了详细的 介绍，列举了数据挖掘对聚类算法的典型要求。并概括了目前聚类方法的 基本分类及相关算法。针对高维聚类的特点以及现有高维聚类算法存在的 问题，提出了本文的改进方案。 第三章提出了在原有算法e p c h 的基础上的改进算法r e p c h ( r e l a t i v ee n t r o p yb a s e dp r o j e c t i v ec l u s t e r i n gb yh i s t o g r a m s ) ，详细阐述了 算法的基本原理及其实现过程。 第四章实验分析。首先，对r e p c h 算法进行了有效性测试，包括聚 类结果的可视化以及有效性分析。其次，对r e p c h 算法与e p c h 算法进 行了性能测试，并对实验结果进行了比较分析。 第五章总结了本文所做工作，并探讨了进一步的研究方向。 2 重庆邮电大学硕士论文第二章高维数据聚类算法分析 第二章高维数据聚类算法分析 2 1 数据挖掘概述 2 1 1 数据挖掘的定义 数据挖掘就是从大量的，不完全的、有噪音的、模糊的、随机的实际 应用的数据集中整理或者说挖掘出有效的、新颖的、潜在有用的，以及最 终可理解模式的高级处理的过程【l 】。在上面的定义中涉及到几个需要进一 步解释的概念：“数据集”、“模式”、“过程”、“有效性”、“新颖性”、“潜在 有用性”、“最终可理解性”。数据集是一组事实f ( 如关系数据库中的记录) ； 模式是一个用语言l 来表示的一个表达式e ，它可以用来描述数据集f 的 某个子集f e ，e 作为一个模式要求它比对数据子集f e 的枚举要简单( 描述 的信息要少) ；过程在数据挖掘中通常指多阶段的数据处理，涉及数据准 备、模式处理挖掘、知识评价以及反复修改求精；有效性是指发现的模式 对于新的数据仍然保持一定的可信度；新颖性要求挖掘的模式是新的；潜 在有用性是指发现的知识将来有实际的效用，如用在决策支持系统里提高 经济效益：最终可理解性要求发现的模式能被用户理解，它主要体现在知 识的简洁性上。最后，有效性、新颖性、潜在的有用性和最终的可理解性 综合在一起称为兴趣性。 许多人把数据挖掘视为另一个常用术语数据库中的知识发现( k d d 。 k n o w l e d g e d i s c o v e r y f r o m d a t a b a s e ) 的同义词。相对来讲，数据挖掘主要 用于统计界、数据分析、数据库和管理信息系统界；而知识发现主要流行 于人工智能和机器学习。但是也有人把数据挖掘视为数据库中知识发现过 程的一个基本步骤。知识发现过程如图2 1 所示，由以下步骤组成： 1 ) 数据清理( 消除噪声或不一致数据) 2 ) 数据集成( 多种数据源可以组合在一起) 3 ) 数据选择( 从数据库中检索与分析任务相关的数据) 4 ) 数据变换( 数据变换或统一成适合挖掘的形式，如通过汇总或聚集 操作) 5 ) 数据挖掘( 基本步骤，使用智能方法提取数据模式) 6 ) 模式评估( 根据某种兴趣度度量，识别表示知识的真正有趣的模式) 重庆邮电大学硕士论文第二章高维数据聚类算法分析 7 ) 知识表示( 使用可视化和知识表示技术，向用户提供挖掘的知识) 数据挖掘步骤可以与用户或知识库交互。有趣的模式提供给用户，或 作为新的知识存放在知识库中。 图2 t 数据挖掘视为知识发现的一个步骤 2 1 2 数据挖掘的功能 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任 务一般可以分为两类：描述和预测。描述性挖掘任务刻画数据库中数据的 一般性。预测性挖掘任务在当前数据上进行推断，以进行预测。数据挖掘 任务主要是：类概念描述、关联分析、分类和预测、聚类分析。 1 1 类概念描述( c l a s s c o n c e p td e s c r i p t i o n ) ：用汇总的、简洁的、精确 的方式描述每个类和概念可能是有用的。其目的是对数据进行浓缩，给出 它的紧凑描述。 2 ) 关联分析( a s s o c i a t i o na n a l y s i s ) ：发现关联规则，这些规则展示属性 值频繁地在给定数据集中一起出现的条件。关联分析广泛用于购物篮或事 物数据分析。 4 重庆邮电大学硕士论文第二章高维数据聚类算法分析 3 ) 分类和预测( c l a s s i f i c a t i o n ，p r e d i c t i o n ) ：分类找出描述并区分数据类 或概念的模型( 或函数) ，以便能够使用模型预测类标记未知的对象类。分 类可以用来预测数据对象的类标记。然而，在某些应用中，人们可能希望 预测某些空缺的或不知道的数据值，而不是类标记。当被预测的值是数值 数据时，通常称之为预测。尽管预测可以涉及数据值预测和类标记预测， 通常预测限于值预测，并因此不同于分类。 4 1 聚类分析( c l u s t e r i n g ) ：与分类和预测不同，聚类分析数据对象，而 不考虑已知的类标记。一般情况下，训练数据中不提供类标记，因为不知 道从何开始。聚类，可以用于产生这种标记。对象根据最大化类内的相似 性，最小化类间的相似性的原则进行聚类或分组。即对象的簇( 聚类) 这 样形成，使得在一个簇中的对象具有很高的相似性，而与其他簇中的对象 很不相似。所形成的每个簇可以看作一个对象类，由它可以导出规则。 2 2 聚类分析简介 聚类( c l u s t e r i n g ) 的定义是将物理或抽象对象的集合分组成为由类似 的对象组成的多个类的过程。由聚类所生成的簇是一组数据对象的集合， 这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。在许多 应用中，可以将一个簇中的数据对象作为一个整体来对待。相异度是根据 描述对象的属性值来计算的。常见的度量方式有距离和密度。 聚类分析已经广泛地用在许多应用中，包括模式识别、数据分析、图 象处理、市场研究以及基因表达。通过聚类，人能够识别密集的和稀疏的 区域，因而发现全局的分布模式，以及数据属性之间有趣的相互关系。作 为一个数据挖掘的功能，聚类分析能作为一个独立的工具来获得数据分布 的情况，观察每个簇的特点，集中对特定的某些簇做进一步的分析。此外， 聚类分析可以作为其他算法( 如特征和分类等 的预处理步骤，这些算法再 在生成的簇上进行处理。 数据聚类有贡献的研究领域包括数据挖掘，统计学，生物学，机器学 习，空间数据库，生物学，以及市场营销。由于数据库中收集了大量的数 据，聚类分析已经成为数据挖掘研究领域中一个非常活跃的研究课题。 2 3 数据挖掘对聚类的典型要求 聚类分析是一个富有挑战性的研究领域，它的潜在应用提出了各自特 重庆邮电大学硕士论文 第二章高维数据聚类算法分析 殊的要求，数据挖掘对聚类的典型要求如下： 1 ) 可伸缩性 许多聚类算法在小于几千个数据对象的小数据集合上工作的很好；但 是，一个大规模数据库可能包含几百万个对象，在这样的大数据集合样本 上进行聚类可能会导致有偏差的结果。我们需要有高度可伸缩性的聚类算 法，其运行时间必须可预测且可接受的，时间复杂性为指数或多项式的算 法不具有实用价值。 2 ) 能发现任意形状的聚类 由于聚类的具体特征在分析前一般是未知的，聚类可能是球形的、凹 形的、中空的等任意复杂的形状和结构，这就要求聚类算法能发现任意形 状的聚类。 3 ) 处理噪声数据的能力 噪声在大规模的和高维德数据库中尤其普遍。许多领域要求聚类算法 具有识别噪声的能力。一些聚类算法对于这样的数据敏感，可能导致低质 量的聚类结果。在某些特殊应用中，噪声的识别甚至比聚类的发现更有实 际意义，例如在电子商务中发现非友善的恶意行为可以有效地减少损失。 4 1 对于输入记录的顺序不敏感 一些聚类算法对于输入数据的顺序是敏感的。对于同一个数据集合， 当以不同的顺序提交给同一个算法时，可能生成差别很大的聚类结果，例 如k 平均算法【2 1 和c l a r a n s 3 1 。开发对数据输入顺序不敏感的算法具有 重要的意义。 5 ) 用于决定输入参数的领域知识最小化 几乎所有的聚类算法都包含或多或少的参数，例如聚类的密度和个 数，结果的支持度、置信度等，这些预先给定的参数值在很大程度上决定 了聚类的结果。如果参数值不符合数据的分布特征，算法就不能获得好的 结果。而在实际应用中，合适的参数值很难确定。因此，用户希望算法能 依据某种原则或领域知识估计参数的最佳取值，尽量减少或不需要用户输 入参数。 6 ) 处理高维数据的能力 一个数据库或者数据仓库可能包含若干维或者属性。许多聚类算法擅 长处理低维的数据，可能只涉及两到三维。人类最多在三维的情况下能够 很好地判断聚类的质量。在高维空间中聚类数据对象是非常有挑战性的， 特别是考虑到这样的数据可能非常稀疏，而且高度偏斜。 7 ) 可解释性和可用性 6 重庆邮电大学硕士论文第二章高维数据聚类算法分析 用户希望聚类结果是可解释的，可理解的和可用的。也就是说，聚类 可能需要和特定的语义解释和应用相联系。应用目标如何影响聚类方法的 选择也是一个重要的研究课题。 2 4 聚类方法的分类及相关算法 聚类算法的选择取决于数据的类型、聚类的目的和应用，因而任何聚 类算法都不可能在每个标准上都优越于其它算法。如果聚类分析被用作描 述或探查的工具，可以对同样的数据尝试多种算法，以发现数据可能揭示 的结果。传统的聚类算法通常分为划分方法( p a r t i t i o n i n g 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 ) 。 2 4 1 划分方法 给定一个n 个对象或元组的数据库，一个划分方法构建数据的k 个划 分，每个划分表示一个聚簇，并且k s n 。即它将数据划分为k 个组，同时 满足下列条件：( a ) 每个组至少包含一个对象；( b ) 每个对象必须属于且只 属于一个组。 为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。实 际上，绝大多数应用采用了以下两个比较流行的启发式方法：( a ) k ，平均算 法，在该算法中，每个簇用该簇中对象的平均值来表示；( b ) k 中心点算法， 在该算法中，每个簇用接近聚类中心的一个对象来表示。因此，该类聚类 算法对在中小规模的数据库中发现球状簇很适用。比较有代表性的该类算 法有：k 平均、c l a r a n s 、e m ( e x p e c t a t i o nm a x i m i z a t i o n ，期望最大) 4 1 。 2 4 2 层次的方法 一个层次的聚类方法将数据对象组成一棵聚类的树。根据层次的分解 如何形成，层次的方法可以分为凝聚的和分裂的。凝聚的方法，也称为自 底向上的方法，一开始将每个对象作为单独的一个组，然后相继地合并相 近的对象或组，直到所有的组合并为一个，或者达到一个终止条件。分裂 的方法，也称为自顶向下的方法，一开始将所有的对象置于一个簇中。在 迭代的每一步中，一个簇被分裂为更小的簇直到最终每个对象在单独的 一个簇中，或者达到一个终止条件。比较有代表性的该类算法有：b i r c h 5 j 、 7 重庆邮电大学硕士论文第二章高维数据聚类算法分析 c u r e 6 1 、r o c k 7 1 、c h a m e l e o n i 引。 2 4 3 基于密度的方法 绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发 现球状的簇，而在发现任意形状的簇上遇到了困难。为了解决这个问题， 提出了基于密度的聚类方法，其主要思想是：只要邻近区域的密度( 对象 或数据点的数目) 超过某个阈值，就继续聚类。这样的方法可以用来过滤 “噪声”孤立点数据( n o i s e s ) ，发现任意形状的簇。有代表性的该类算法 有：d b s c a n t 9 1 、o p t i c s t 1 、d e n c l u e 1 1 1 。 2 4 4 基于网格的方法 基于网格的聚类方法首先将聚类空间离散化为有限数量的单元格，然 后在离散的空间上执行所要求的操作。包含的点多于特定阈值的单元格被 认为是密集的，将密集的单元格连接起来形成聚类。这种方法的主要优点 是处理速度快，其处理时间独立于数据对象的数目，仅依赖于量化空间中 每一维上的单元数目。 基于网格方法的有代表性的例子包括：s t i n g ”1 、w a v e c l u s t e r l l3 1 、 c l i q u e t l 4 1 。 2 5 高维聚类问题及方法 技术进步使得数据收集变得更加简单和快速，从而产生了大量的复杂 的高维数据。随着数据量的增大和维数的增多，我们需要一些新的技术来 处理数据，在保证聚类质量的同时提高效率。传统的聚类算法5 ，1 6 ，1 7 ，18 1 ， 受“维灾( c u r s eo fd i m e n s i o n a l i t y ) ”的影响在处理高维数据时存在以下问 题：( 1 ) 随着维数的升高，聚类算法中使用的索引结构的修剪效率会迅速 下降，当维数增加到一定时候时，采用索引结构还不如顺序扫描。( 2 ) 传 统的聚类算法考虑输入数据集的所有维( 属性) ，从而发现数据对象之间的 联系。在高维数据中，许多维通常是冗余的或不相关的，这些不相关的维 ( 属性) 使传统的聚类算法无法发现隐藏在噪声数据中的簇。( 3 ) 距离函数 难于定义。聚类操作的基础是数据对象之间相似性的度量，相似度高的对 象归为一类。低维空间中经常使用欧氏距离等距离函数来度量相似性，但 在高维情况下由于相似性没有传递性，距离函数失效。必须重新考虑新的 8 重庆邮电大学硕士论文第二章高维数据聚类算法分析 度量数据对象相似性的标准或准则。( 4 ) 基于距离的聚类方法，经常需要 计算簇的均值或邻近，但在高维情况下，按距离计算的簇的均值会很接近， 聚类操作由于无法明确区分簇的中心而无法进行。( 5 ) 由于维数很高，传 统聚类算法的计算复杂度会很高，其应用受到很大局限性。 高维聚类技术包括特征转换( f e a t u r et r a n s f o r m a t i o n ) 和特征选择 ( f e a t u r es e l e c t i o n ) 【1 9 】。对于高维数据，可以采用这两种技术，以减少数据 维度，然后利用传统的聚类算法在较低维的数据空间中完成聚类操作。所 谓特征转换，就是将原有特征空间中的属性相结合，生成包含较少维( 属 性) 的新的特征空间。其缺点是，降维后的噪音数据与正常数据之间的差 别缩小，聚类质量无法保障。另外，降维技术的使用虽然缩小了数据维度 空间，但其可解释性、可理解性较差，可能会丢失重要的聚类信息，其结 果的表达和理解存在着一定的难度。特征选择只选取数据集中最相关的 维，用来发现该子空间下存在的簇。其缺点是，特征选择难于发现存在于 不同子空间中的簇。 虽然在高维全空间中没有簇的存在，即在这样的高维空间中并不是所 有的维都与给定的簇相关。解决这个问题的方法之一就是首先选取密切相 关的维，然后在对应的子空间中再进行聚类。特征选择算法可用来确定相 关维，然而在典型的数据挖掘应用中，不同的簇可能对应不同的子空间， 并且每个子空间的维数也可能不同。因此不可能在一个子空间中发现所有 的簇。为了解决这个问题，对全空间聚类问题进行了推广，称为“子空间 聚类”或“投影聚类”。意在发现数据集中的所有的簇以及它所蕴涵的子 空间。投影聚类( p r o j e c t e dc l u s t e r ) 的正式定义为： 在某个多维空间中的一个数据集，一个投影聚类是由数据子集c 和维 的子集d 所构成，使得在子空间d 中数据子集c 中的数据对象之间具有 较高的相似度。 2 6 已有投影聚类算法存在的问题 在高维空问聚类算法中，c l i q u e 算法首次提出了子空问聚类问题。 它综合了基于密度和基于网格的聚类方法，可以发现高维数掘中平行于坐 标系的子空间聚类。其缺点是算法自始至终使用唯一的密度阈值用于发现 子空间中的聚类。由于数据对象间的稀疏度会随着数据对象所在子空间维 数的增加而增加，因此对于存在于不同子空间中的聚类，使用唯一的密度 闽值是不合理的。而且，算法容易丢失密度较小的聚类，执行效率较低。 重庆邮电大学硕士论文第二章高维数据聚类算法分析 e n c l u s 2 0 j 算法延伸了子空间聚类的思想，用熵( e n t r o p y ) 的概念来表 示密度( d e n s i t y ) 度量和覆盖度( c o v e r a g e ) ，因为包含聚类的子空间和不包 含聚类的子空间相比，拥有较小的熵值，从而进一步删除冗余的子空间。 e n c l u s 可以减少不相关聚类的数量，但是也可能删掉小的但有意义的聚 类，且算法随着聚类空间维度的变化可伸缩性不高。 p r o c l u s 2 i 】是第一个自上而下的投影聚类算法。首先，它采样数据， 然后选择七个中心点并迭代地改进聚类结果。聚类质量依赖于采样点与中 心点的平均距离。p r o c l u s 有如下缺点：( 1 ) 由于采用中心点迭代地发现 簇，它偏向于发现超球形的簇。( 2 ) 算法将聚类包含维的平均数量作为输 入参数，因此算法要求包含聚类的子空间要有相似的维数。( 3 ) 因为算法 使用采样技术，所以聚类结果可能会丢掉一些有意义的簇。( 4 ) 算法的聚 类效果对于输入参数特别敏感，用户在决定输入参数时比较困难。 o r c l u s 2 2 1 算法是p r o c l u s 的改进算法，它不仅能够发现轴平行子 空间的簇，而且能够发现非轴平行的子空间中存在的簇。o r c l u s 算法的 执行效率要低于p r o c l u s ，而且聚类的数量和子空间的维数要作为输入 参数预先指定。为了提高聚类效率和可伸缩性，o r c l u s 使用了随机采样 技术，这可能会丢掉较小的聚类。 e p c h t 2 3 】算法采用构建直方图发现密集区域的投影聚类算法，和上述 算法相比更加高效，且不需要较多的先前知识，因此更加灵活。算法采用 公式2 1 作为密度阈值，用于发现存在于直方图中的密集区域： + 乒 汜。， 其中，1 和o r 分别是当前直方图中数据分布的均值和方差，厂是密集区 。：f r i 域在直方图中所占的比例。 、， 作为输入参数对聚类效果影响很大， 而且在一次聚类过程中，对于特征空间中不同维构成的直方图采用相同的 c 值是不合理的。另外，无法识别聚类描述中冗余的维。 为解决以上问题，在研究中我们提出了在e p c h 基础上的改进算法， r e p c h ( r e l a t i v ee n t r o p yb a s e dp r o j e c t i v ec l u s t e r i n gb yh i s t o g r a m s c o n s t r u c t i o n ) 。将密度值转化为相对熵值，利用相对熵的特点，识别直方 图中的密集区域，能够更准确地发现包含聚类的子空问，而且对于不同的 数据集，默认参数的变化较小，方便了用户操作。此外，算法能够发现任 意形状的聚类，并有效的去除噪声数据对象。 1 0 重庆邮电大学硕士论文第二章高维数据聚类算法分析 2 7 本章小结 本章首先对数据挖掘、聚类分析、数据挖掘对聚类的典型要求以及聚 类方法的分类及相关算法做了简要的介绍。接着结合高维聚类需要解决的 问题及现有的技术，对目前比较有代表性的几种高维聚类算法进行了分 析。针对这些高维聚类算法中存在的不足，提出了改进方案。 重庆邮电大学硕士论文 第三章基于相对熵的投影聚类算法 第三章基于相对熵的投影聚类算法 3 1 信息熵在聚类算法中的应用 在通信领域，人们用信息熵月仞作为整个信源x 的总体信息测度【2 4 1 。 日( x ) = p ( a 1 ) ( q ) + p ( a 2 ) i c a 2 ) + p ( a ，) ， ，) = 一p ( a i ) l o g p ( a i ) 一p ( a 2 ) l o g p ( a 2 ) 一一p ( a ，) l o g p ( a ，) ( 3 1 ) 上 = 一艺p ( a f ) l o g p ( a f ) 比特，信源符号 i ；l 公式3 1 表示，信源x 每发一个符号( 不论发什么符号) 所提供的平均 信息量，它就是信源x 可能发出的各种不同符号a ，n = j ，2 ，) 含有的 自信息量t ( a 9 一= j 2 ，一，在信源的概率空间p 向，p ( a 2 ) ，p r 口j ) 中的 统计平均值。自信息量聊= 一l o g p ( a 9 一= j ，z ，0 表示信源符号a i 所含有 的全部信息量。它具有以下公理性条件：如信源符号a 1 和a j 的先验概率分 默为p ( a o 帮p a i ) ，a0 ( p ( a ) p ( a j ) p ( o i ) ，鼬i ( a 口( 1 ( a j ) 。 该公理性条件可理解为，某一事件发生的概率越大，即可能性越大，则这 一事件一旦发生，人们从中获取的信息量就越小，反之亦然。 算法 2 0 】将数据分布的特征空间划分成网格结构，通过定义网格区域 的熵反映不同区域密度的变化，如公式3 2 所示。其中，z 表示网格单元 的集合，d 例表示个单元格中包含的数据对象在整个数据集中所占的比 例。公式3 2 具有如下性质：熵值随着数据对象分布区域密度的增大而减 小，反之办然。当数据对象趋于平均分布，一个数据对象位于特征空间哪 一片区域的不确定性最大，熵值最大。相反，数据对象的分布越集中，一 个数据对象位于密集区域的可能性越大，因此不确定性越小，熵值越小。 因此在【2 0 】中，用户通过输入一个固定参数d 作为密度阂值，用来区分密 集区域和稀疏区域。 1 4 ( x ) = 一d ( x ) l o g ：d ( ( 3 2 ) j e 但是，算法 2 0 】中使用的熵值计算公式，具有一定的局限性。因为聚 类结果对于阈值参数。十分敏感，针对具有不同分布特征的高维数据集合 来说，参数。通常很难确定，这不仅加重了用户的负担，也使得聚类的质 2 重庆邮电大学硕士论文第三章基于相对熵的投影聚类算法 量难以控制。 通过对以上问题进行分析，我们认为公式3 2 是反映某一数据集分布 的绝对量。为了能够得到较理想的聚类结果，需要针对不同的数据集设定 不同的阈值。如果能够将公式3 2 转化为反映数据集分布的相对量，那么 设定相对稳定的阈值就能够适用于更多的数据分布。举例来讲，设有三个 一维数据集，其取值范围分别是 o ，l 0 0 1 、【o ，2 0 0 和【o ，3 0 0 】，划分有意义的 数据对象的阈值分别是2 0 、4 0 和6 0 。为了能够发现这些有意义的数据对 象，公式3 2 要分别取三次不同的阈值，而这三个阈值分别占各自取值范 围的2 0 。2 0 是一个相对量，可见，一个相对于自身变化的量要比绝对 量适用性更高。 在公式3 2 的基础上，我们使用了直方图上熵的比值的概念【2 5 1 ，定义 为相对熵，即数据在实际分布下的熵值跟相同的数据按平均分布下得到的 熵值的比值，如公式3 3 所示。直方图用于反映数据点的分布在子空间上 的投影。公式3 3 中，工表示单个直方图格( b i n ) ，d 俐表示直方图中一个直 方图格对应的区域所包含的数据对象在数据集中所占的比例，x 表示直方 图中格( b i n ) 的集合，圄f 弼表示数据对象在实际分布下直方图的熵。r 是直 方图中格的数量，则j 丁表示相同的数据集在平均分布下，每一个直方图 格包含的数据对象在数据集中所占的比例，乩。仞则表示相同的数据对象 在当前子空间下按平均分布得到的熵值。因此，n r ( x ) 表示在由当前直方图 对应的子空问下，数据对象的实际分布与其对应的平均分布之间的相似 度。日r 仞6 ( 0 ，1 】，数据对象的实际分布越接近于平均分布，研仞越接近 于l ，反之亦然。我们可以利用相对熵的这个特点，将相对熵值作为密度 度量，区分特征空间中的密集区域和稀疏区域。实际上，密集区域之间被 分布广泛的稀疏区域所间隔，在这片区域上，相对熵值较小。随着密集区 域的减少，由于稀疏区域的实际分布近似于平均分布，故相对熵值逐渐接 近于1 。 ：专-yd丁(x)log丁2d(x)l：器：器耵：i并p，og 日，( ) = 堕乞r _ t = 群= 三：，( r = i 并1 ) j ， 一yo ”9 2 1 “4 曙t “ 3 2r e p c h 算法 e p c h 算法需要用户输入唯一参数m d x r i o c l u s t e r ，即用户期望的最 大聚类数量。如果实际聚类的数量小于该值则算法将会返回所有发现的 重庆邮电大学硕士论文 第三章基于相对熵的投影聚类算法 聚类。反之，算法将返回它所发现的可能性最大的前m a x n o c l u s t e r 个聚 类。同时，算法中使用了两个带有默认值的参数，和k 。厂表示在每一个投 影子空间中，一个聚类占用空间比例的上限。k 用于提高聚类效率，根据 系统资源的使用情况，可以设置不同的k 值，只对舻m a x n o c l u s t e r 个聚 类候选项进行处理，得到最终的聚类结果。e p c h 算法共有5 部分组成， 即 1 ) 构建直方图 2 1 发现所有直方图的密集区域 3 1 产生签名链表 4 1 合并相似的签名项并产生聚类描述 5 1 关联数据对象到相应的聚类 以上步骤可以简单地概括为三部分操作。首先，发现直方图中的密集 区域。密集区域反映的是聚类在较低维子空间上的投影，密集区域的正确 识别是产生正确聚类描述的关键。其次，识别子空间中的聚类。最后，关 联数据对象到相应的聚类。r e p c h 算法是对e p c h 算法的改进，研究主要 集中在如何利用相对熵更有效地发现密集区域。 假设a = a j ，a2 ，a i ) 是有界、全部有序域的集合，s = a t x a 2 血是一个k 维数值空间，其中a ，a n ，a t ，表示s 的k 个