（计算机应用技术专业论文）投影聚类算法及其应用的研究.pdf

摘要 随着聚类分析的应用领域日益扩展，越来越多高维的、混合类型属性数据需要处理。 然而现有的大部分算法要么只能对低维数据有效，要么只能处理某一种特定类型的数 据。针对这两个矛盾，对高维的、三种混合类型( - - 元型，类别型，数值型) 属性数据 的聚类算法做了一些研究。 首先，基于密度的分组方法( d g m ) 将数据集中每一维的数值型数据分别离散化， 用区间标号替代其实际的数据值。然后，将数据集中所有有效数据统一编号，转化成一 个类别型数据集，去掉空缺值并添加事务标识符后成为一个事务数据库。在定义了最长 频繁闭项集( l f c i ) 的概念后，利用l f c i 的两个关键属性，即( 1 ) l f c i 最大地覆盖 了事务；( 2 ) l f c i 能够作为事务的描述，可将具有相同l f c i 的事务归为一簇。为了适 应聚类的要求，对传统的频繁模式树( f p 树) 从三个方面进行了改造，并详细叙述了 改造f p 树的创建。分析挖掘l f c i 的过程后，更新f p 树以降低空间复杂度；根据l f c i 的特点，导出无效树的剪切策略以降低时间复杂度，给出的l f c i - 增长方法挖掘出每个 事务的l f c i 。从事务的多个l f c i 中，选取一个作为该事务的描述，插入到定义的簇树 中。每一个从根节点到链接有事务标识符的节点即为一个簇，其路径中的项对应于相关 维，事务标识符对应于相关点。以上过程被总结成一个对高维混合属性数据的聚类框架， 它本质上是投影聚类方法。 为了验证聚类框架的性能，在模拟数据集上做了基于最长频繁闭项集的算法 ( c a l f c i ) 的伸缩性，对高维数据处理，对不同类型属性处理，健壮性等方面的实验。 仿真实验表明，c a - l f c i 具有较好的综合性能。另外，还将算法应用在两个真实数据 集v o t e s 和m u s h r o o m 上。结果表明，在算法的输入参数最小支持度小于2 2 的情 况下，对v o t e s 数据集，精确度保持在9 5 以上，最高可达9 8 6 2 ，运行时间少于o 7 1 秒；对m u s h r o o m 数据集，精确度保持在9 7 以上，最高可达9 9 8 ，运行时间少于5 5 秒。此外，结果是可用的和可解释的。 关键词：数据挖掘、聚类分析、高维数据、混合类型数据、最长频繁闭项集、 改造f p 树、最小支持度 m 江南大学硕士学位论文 a b s t r a c t w i t ht h ee x p a n s i o no ft h ea p p l i c a t i o nf i e l do fc l u s t e r i n ga n a l y s i s ，m o l ea n dm o r e h i g h - d i m e n s i o n a la n dm i x e d - t y p od a t an e e dt ob ep r o c e s s e d h o w e v e r , m a n ye x i s t i n g m e t h o d sa r co n l ye f f e c t i v ef o rc l u s t e r i n gl o w - d i m e n s i o n a ld a t a , a n d o rf o rs p e c i f i c - t y p ed a t a t os o l v et h e s et w op r o b l e m s ，t h i sp a p e rp r e l i m i n a r yd i s c u s s e sc l u s t e r i n gh i g h d i m e n s i o n a l a n dm i x e d - t y p o ( i n c l u d i n g b i n a r y , c a t e g o r i c a la n dn u m e r i c a lt y p e s ) d a t a s e t f i r s t l y , e a c hn u m e r i c a l - t y p ea t t r i b u t ei nt h ed a t a s e tw a sd e c r e t i z e db yt h ep r e s e n t e d m e t h o d ，d e n s i t y - b a s e dg r o u p i n gm e t h o d ( d o m ) r e s p e c t i v e l y , s u b s t i t u t i n gi t sf a c t u a lv a l u e t oai n t e r v a lt a b s e c o n d l y , t h ed a t a s e tw a st r a n s f o r m e dt oar a n s a c t o nd a t a b a s e ( t d b ) t h r o u g hn u m b e r i n ga l lt h ee f f e c t i v ed a t a , e l i m i n a 她t h em i s s i n gv a l u ea n da d d i n g u a n s a c t i o ni d e n t i f i c a t i o nf o re a c hp o i n t a f t e rd e f i n i n gt h ec , o n o p t i o no ft h el o n g e s t f r e q u e n tc l o s e di t e m s e t ( l f c i ) t h et r a n s a c t i o n sw i t ht h es 啦el f c lw mc l u s t e r e du t i l i z i n g t h et w ok e y p r o p e r t i e so fl f c i 。i e ( 1 ) i tc o v e r e dt h et r a n s a c t i o nm a x i m a l l y , a n d ( 2 ) i tw a s t h e d e s c r i p t i o no f t h ec o r r e s p o n d i n gt r a n s a c t i o n t oa c c o m m o d a t et h er e q u i r e m e n t so f c l u s t e r i n g , t h et r a d i t i o n a lf r e q u e n t - p a t t e r nt r e 圮( f p - t r c e ) w a sr c c e s t e d 丘o mt h r e ea s p e c t s t h e nt h e p r o c e d u r eo fb u i l d i n l n gt h ea d a p t e df p t r e ew a sd e s c r i b e dd e t a i l e d l y a f t e ra n a l y z i n gt h e p r o c e d u r eo fc o l x q h u c t i n ga d a p t e df p t r e e ，am e t h o dt ou p d a t ef p t r e ew a sp r e s e n t e dt o r e d u c et h es p a c ec o m p l e x i t y , a n das t r a t e g yt op i a l n et h ei n v a l i dt r e ew a se d u c e dt or e d u c et h e t i m ec o m p l e x i t ya c c o r d i n gt ot h ec h a r a c t e r i s t i c so fl f c i l f c i - g r o w t hw h i c hm i n e dt h e l f c i so fe a c ht r a n s a c t i o nw a sp r e s e n t e d a f t e rs e l e c t i n go n ef t o mm u l t i p l yl f c i so fe a c h t r a n s a c t i o na si t sd e s c r i p t i o n , t h ea l ls e l e c t e dl f c i sw e r ei n s e r t e di n t ot h ed e f i n e dc l u s t e rt r e e ac l u s t e ri n c l u d e dt h ea s s o c i a t e dd i m e n s i o n sa n dp o i n t s t h ef o r m e r ，e t h ei t e m si nt h e p a t hw h i c hw a sf t o mt h er o o tn o d et ot h ee n do n el i n k e dw i t h 恤$ a c t i o ni d e n t i f i c a t i o n s , a n d t h el a s tw e r et h el i n k e di d e n t i f i c a t i o n si nt h ee n dn o d eo f c l u s t e rt r e e s u m m a r i z i n gt h ea b o v e w h o l ep r o c e d u r et oaf i a m e w o f ko f c l u s t e r i n gh i g h - d i m e n s i o n a la n dm i x e d - t y p ed a t a , i tw a sa p r o j e c t e dc l u s t e r i n gm e t h o de s s e n t i a l l y t ov a l i d a t et h ep e r f o r m a n c eo fc l u s t e r i n ga l g o r i t h mb a s e do nt h el o n g e s tf r e q u e n t c l o s e di t e m s e t s ( c a - l f c i ) ，e x t e n s i v es i m u l a t e de x p e r i m e n t sd e m o n s t r a t et h a tc a - l f c ii s e f f e c t i v ea n de f f i c i e n tb a s i c a l l y i na d d i t i o n , c a - l f c iw a sa p p l i e a t e di nt w or e a ld a t a s 出$ v o t e sa n dm u s h r o o m t h er e s u l t ss h o wt h a t , f o rv o t e s ，a c c u r a c yi sh i g h e rt h a n9 5 , m a x i m a l t o9 8 6 2 t h er a n n i n gt i m ei sl e s st h a no 7 1s e c o n d s ；a n df o rm u s h r o o m , a c c u r a c yi sh i g h e r t h a n9 7 j n a x i m a lt o9 9 8 ，a n di t s 棚n n i n gt i m ei sl e s st h a n5 5s e c o n d s ，w h e ns e t t i n gt h e m p u tp a r a m e t e r , m i n i m a ls u p p o r tt ol e s st h a n2 2 f i n a l l y , t h er e s u l t sa r eu s a b l ea n d c o m p r e h e n s i v e k e y w o r d s ：d a t am i n i n g ，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 , m i x e d - t y p ed a t a , l o n g e s tf r e q u e n tc l o s e di t e m s e t , a d a p t e df p 1 h 峙m i n i n m ls u p p o r t i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意o 、 关于论文使用授权的说明 2 0 0 7 年月j 7 日 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名：速盔! 笠 导师签名： 日期： 第一章绪论 1 1 研究背景 第一章绪论 ( 一) 知识发现 在过去数十年中，收集和保存的数据以几何级数的速度增长，呈现出数据爆炸( d a t a e x p l o s i o n ) 的现象。例如，美国国家航空和宇宙航行局( n a t i o n a la e r o n a u t i c sa n ds p a c e a d m i n i s l r a t i o n , n a s a ) 对地观测系统( e a r t ho b s e r v i n gs y s t e m ，e o s ) 每天都要产生i t b 的图像数据；美国零售商系统w a l - m a r t 每天都会产生2 亿左右的交易数据；中国建成 的覆盖全国、全省的大型地理空间数据库和专题数据库的数据总量超过1 2 5 0 g b ，等等。 据统计，全球拥有的数据量每2 0 个月翻一番。因此，一方面，人们拥有极其庞大的数 据量，可以得到的信息越来越多，几乎要被数据所淹没；另一方面，人们又渴望获取隐 藏于这些类型越来越复杂、结构越来越多样的数据中的有用的知识。如果没有有效的方 法，由计算机及信息技术来提取有用信息和知识，人们就会感到面对信息海洋像大海捞 针一样束手无策。为此，基于数据库的知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ，简 称k d d ) 技术应运而生了，它随着现代社会信息化的发展，越来越显示出强大的生命 力。 人们给k d d 下过很多定义，内涵也各不相同，日前公认的定义是1 9 9 6 年f a y y a d 等人提出的【1 】： 知识发现是在数据库中提取有效的、新颖的、潜在有用的、最终可理解的模式的非 平凡过程。它是一个跨学科的、从大规模数据库中有效地提取有用知识的技术。主要是 以下步骤的交互式迭代过程： 选取( s e l e c t i o n ) ：从原始数据中选取一组数据和或属性以建立目标数据集。 预处理和转换( p r e p r o e e s s i n g & t r a n s f o r m a t i o n ) ：选取有用的特征以描述数据，例 如使用降维或转换方法减少属性数，或者找出数据集的代表数据。 数据挖掘( d a t am i n i n g ，简称d m ) - 在代表数据中查找有趣的模式( p a t t e r n s ) ，它 包括关联规则，类别树或类别规则，规约、簇等。 解释和评f d ( i n t e r p r e t a t i o n & e v a l u a t i o n ) ：应用可视化和知识代表技术获取模式， 如果结果不满意，可以返回到以前的步骤，直到得到所要的模式。 ( 二) 数据挖掘 数据挖掘【2 】是知识发现中的一步，在可计算的效率条件下，通过开发有效的算法对 数据进行分析和发掘，从而生成一组模式。它主要包括以下几个方面的研究： 关联分析( a s s o c i a t i o na n a l y s i s ) ：发掘关联规则( a s s o c i a t i o nr u l e s ) ，展示属性一值 频繁地发生在给定数据集中一起出现的条件。 分类和预测( c l a s s i f i c a t i o n & p r e d i c t i o n ) ：分类找出描述并区分数据类或概念的模 l 江南大学硕士学位论文 ， 型或函数，这个过程中其标记是已知的数据对象，使得在预测时能够将一个数 据对象映射、分类到某个预定义类中。 。 一聚类分析( c l u s t e r a n a l y s i o ：确定一组类或簇( c l u s t e r ) 来描述数据，它根据最大化 类内的相似性、最小化类间的相似性的原则进行聚类或分组。 特征化和区分( c h a r a c t e r i z a t i o n & d i s c r i m i n a t i o n ) ：数据特征化将目标类数据的一 般特征或特性汇总，然后数据区分将目标类对象的一般特性与一个或多个对比 类对象的一般特性比较。 孤立点分析( o u t l i e ra n a l y s i s ) ：挖掘出孤立点，即那些与数据的一般行为或模型 不一致的数据对象。 演化分析( e v o l u t i o na n a l y s i s ) ：描述数据对象随着时间变化的规律或趋势，并对 其建模。 知识发现过程中做的大部分工作是有关数据挖掘算法的研究，其核心步骤是数据挖 掘算法的应用。因此实际上，人们往往不严格区分数据挖掘和知识发现，很多时候把知 识发现和数据挖掘两者混淆使用。一般在科研领域中称为知识发现，而在工程领域则称 为数据挖掘。 ( 三) 聚类分析 近几年来，聚类( c l u s t e r i n g ) 作为数据挖掘的主要方法之一，越来越引起人们的关注 p 1 1 】。所谓聚类，就是将数据对象分组成多个类或簇，使得在同一个簇中的对象之间具 有较高的相似度，而不同簇中的对象差别较大。也就是说，形成簇之后，同一个簇内对 象具有很高的相似性，而且与不属于该簇的对象有迥然的差异( 即不相似) 。聚类与分类 相比，分类算法分析的是类别己知的数据集，而聚类算法则分析的是类别未知的数据， 换句话说，分类和预测是一种有指导的学习过程，每个训练样本是在告知属于哪个类的 “指导”下进行的；与之不同的是，聚类是一种无指导的学习过程，每个训练样本的类 标号是未知的，聚类输入的是一组未分类的记录，它要学习的类集合或数量也往往是事 先不知道的。 通过聚类分析，人们可以识别密集的和稀疏的区域，从而分析全局的分布模式，以 及数据属性之间有趣的相互关系。例如在生物信息学【1 2 1 中，要处理的数据主要有三类， 主要有d n a 蛋白质序列数据( d n a p r o t e i ns e q u e n c ed a t a ) ，大分子结构数据 ( m a c r o m o l e c u l a rs t r u c t u r ed a t a ) 和基因表达数据( g e n ee x p r e s s i o nd a t a ) 。其中应 用聚类分析最多的主要是基因表达数据，这是因为基因表达数据规模极其庞大，而生物 学里已知功能的基因相对很少。要利用相对很少的己知知识去推断未知的知识，分类方 法并不非常适合，因为用相对少的数据训练出来的模型不一定能代表整个数据空间的分 布。聚类是不需要先验知识，直接将具有相似表达性质的基因聚在一起，这对分析基因 的功能是一个非常简便有效的特性。通过聚类分析，相似的基因或者基因片断代表相似 的基因表达功能，这对于基因工程中的筛选基因、医学中的分析病变原理都有重要意义。 不同的聚类算法中，用于描述相似性的函数也有所不同，有的采用欧氏距离或马氏 距离，有的采用向量夹角的余弦，也有的采用其他的度量方法。当预先不知道簇数目， 2 苎二兰堕堡 或者用参数估计和非参数估计难以分辨不同类型的类概率密度函数时，就需要采用聚类 分析。有些聚类分析算法可以自动地确定簇数目，而不必提取知道，但有些算法是将簇 数目作为结束条件，即发现了预定数目的簇后，算法结束。若没有给定要发现的簇数目， 那么如何在聚类过程中自动地得出簇数，这是聚类分析中的一个关键问题。 聚类技术的研究包括许多领域，其中有统计学【13 1 ，模式识别【1 4 】，机器学习【1 5 】，数 据分析【阍，图像处理【1 7 】，购物篮分析f 1 8 】等，还可以作为其它处理方法f 1 9 】【2 0 1 ( 如特征和 分类) 的预处理步骤。 ( 四) 高维混合属性数据 随着聚类应用领域的不断扩展，人们经常会碰到一些数据对象，它们可能有几十、 几百甚至成千上万个属性，如果将这些对象的每一个属性看作是其中一维空间，则数据 对象存在于其属性空间内，这样数据对象可以表示成其高维属性空间中的点或向量。实 际上现实世界中的对象都可以采用一些属性的集合来描述。比如，“人”可以采用身高， 体重，性别，出生日期，肤色，国籍，受教育程度，工作等一系列的属性来刻画。可以 说，高维数据处处、时时都是存在的。 在数据挖掘领域，经常碰到的高维数据有购物篮数据，文档数据，基因表达数据， 用户评分数据，多媒体数据，时间序列数据，w e b 访问数据，医疗图像数据，分子生物 数据，计算机辅助设计数据等等。从这些数据的来源可以看出聚类的应用领域十分广泛。 数据的属性可以有多种类型，常见的数据类型有区间标度数据，二元数据，标称数 据，序数数据，比例标度数据等。在许多真实的数据库中，数据对象的属性类型是混合 型的，即数据对象的属性类型不止一个。例如，描述“人”的属性身高、体重是区间标 量类型，它是可以线性的连续度量的类型；性别是二元数据，它是只有两个状态的类型； 肤色是标称数据类型，它是二元数据的推广，可以有多于两个状态的类型，如黄，白， 黑，棕等；受教育程度是序数数据类型，它类似于标称数据，是按照一定意义序列排列 的标称数据，如文盲、初等、中等、高等教育等。 1 2 研究现状 统计学、机器学习、模式识别等领域中有关聚类的研究已经进行了很多年，在机器 学习中一个很相似的方法是无监督学习( u n s u p e r v i s e dl e a r n i n g ) ，然而，这种方法对于大 规模的数据集的聚类显得不是很有效，且要求所有的数据对象必须同时保持在内存中才 能得以分组。因此，聚类算法近年来在大规模数据集处理中大显身手。现有的聚类算法 粗略的可分为划分方法、分层方法、基于密度的方法、基于网格的方法、基于模型的方 法等几种方法。本文将在第二章介绍上述方法的几个典型的代表算法。 高维数据的普遍出现以及高维数据固有的内在特征，使得传统的对于低维数据聚类 有效的一些算法在处理大规模高维数据集时不那么有效了【3 1 1 ，因此研究的焦点转移到构 造对高维数据的聚类的算法上。近年来经过努力，广大科技工作者给出了很多处理高维 的方法，主要有属性空间选取 2 1 l t z 2 1 ( f c a u a 它s e l e c t i o n ) 、属性空间转化( f e a t u r e 3 ：坚堕奎兰堡主堂垡丝奎 缸a 珊f o 黝l i o n ) 两种方法，比如主成分分析法( p c a ) 】，k a r h u n e n - l o e v e 转换法等等。 目前，大多数算法是针对某一类型的数据所建立的算法，比如对二元数据集的算法， 对类别数据集的算法例，对数值型数据集的算法瞄】，却很少有能够将多种数据类型统 一起来处理的聚类算法嗍。 i 3 研究内容 本文针对目前算法的不足，给出一个针对大规模的、高维的、多种属性类型的数据 的聚类框架。在框架某些阶段的处理过程中，除了本文给出的处理方法外，其它的相关 工作者也可以添加已经存在或提出新方法，因此具有很好的可扩展性。 这个框架的主要思路是将数值型的数据在其属性空间中离散化，转换为类别数据 型，然后从第一维属性开始重新将数据值编号，从而得到一个完整的类别型的数据集， 可将这个数据集看作是一个事务数据库，通过改进已有的频繁模式的挖掘算法来确定簇 的相关维和相关点。 本文研究的主要内容如下： 介绍各种类型数据的相似性度量，阐述高维数据聚类中难点之所在，列出数据 挖掘对聚类算法的典型要求，综合阐述现有的聚类方法，并选取每种方法的代 表算法为例，分析它们各自的优缺点； 提出本文所要解决的问题，研究了一维空间中数值型数据的离散化方法，并给 出了分组方法；总结了混合类型属性的数据集向统一的类别型数据集的转换方 法，接着着重研究了类别数据集的聚类算法，它包括：回顾了挖掘频繁模式方 法的经典方法f p 增长算法，接着为了适应本文的需要，对传统f p 树的进 行了改造，定义了最长频繁闭项集的概念后，分析它的两个主要性质，且由此 详细地分析了挖掘最长频繁闭项集的过程，给出了挖掘过程的剪切策略以加速 算法，更新f p 树以节约内存；然后给出了基于最长频繁闭项集的聚类算法，最 后总结出对高维混合属性数据聚类的框架。 通过仿真实验验证本文给出的算法的性能，并应用在真实数据集中以了解所给 算法的实际应用性能。 1 4 论文基本结构 本文主要由以下三个部分组成： 第一部分：引言部分 该部分有第一、二章组成。第一章阐述了本课题的来源，技术背景，研究的对象， 简要概括了聚类算法的研究现状与不足，进而提出本文研究的内容；第二章介绍了聚类 算法的挑战以及要求，分析了高维数据的特点，介绍了已有的典型的聚类算法并分析其 优缺点。 4 蔓二兰丝堡 第二部分：对高维混合类型数据的聚类部分 这部分是本文的重点，由第三、四章组成。第三章详细阐述了本文给出的对高维混 合属性数据的聚类框架的设计与实现步骤；第四章通过仿真试验验证该框架中某些关键 步骤算法的性能，并展示了该聚类框架在实际数据集中应用的效能，进一步证实该框 架的实用性。 第三部分：结束语 最后，论文在这一部分结束，对全文作出总结，综述了论文的研究内容和主要贡献， 评价了该框架的优点和不足，并讨论了进一步的研究方向。 5 江南大学硕士学位论文 2 1 聚类的定义 第二章聚类分析 设彳= 似厶a 2 , 一。彳d 是一个属性的集合，8 = a j x a 2 x a d 是一个d 维的属性空间， 称4 j ，4 玉，o 山是s 的维( 同义词：特征，变量，分量，字段) 。数据集d s 由在属性空 间s 中的个数据点( 同义词：对象，元组，交易，实例坍组成，数据点p 产( p f j ，既” ， 每一个分量乃表示数据点b 第_ ，维的值，卢1 ：，且乃4 ，产l ：d 。只是一个d 二维特 征向量，这样，d s 可以看作是一个小维特征向量的数据库，也相当于是一个n x d 矩 阵。d 维属性空间s 的子空间u 指属性集合4 的任意子集组成的属性空间。即u 气4 ， a t 2 x 彳庸，这里量d ，并且如果f 呵，则t ，( t j 。属性的数据类型可以分为数值型、二 元型、类别型等。数值型属性的取值可以是任意的实数，二元型属性只有两种状态：0 和1 ，类别型数据可以看作二值型的推广，即类别型属性可以呈现多于两种的状态。 聚类就是将数据对象分组成多个类或簇，使得在同一个簇中的对象之间具有较高的 相似度，而不同簇中的对象差别较大。具体来说，如下表示【2 刀： 聚类把数据集d s 中的个数据点p i _ 1 ：回，划分为j | 个彼此不相交的集合c i ( 糟产1 ，2 ，勋，这些集合被称作是簇；同时可能有些数据点不属于这七个集合中任何一 个，它们单独被列出来，称作是噪声g ，属于这个集合中的数据点被称作是噪声数据 ( 点) 。即 j 叭2 沙二u ! c ；：2 脚 ( 2 1 ) 【 o n 0 2 0 ( i ，) 投影聚类( p r o j e , c t e dc 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 ) 的一种，它如下 定义网：投影聚类是要在数据集中找出七个集合对( c ，d ) ，其中c 表示数据点的集合， d 表示c 中的对象在空间d 内形成簇的维的集合。进而，c 称作是投影簇的相关点，d 称作是投影簇的相关维。投影聚类方法所要解决的问题是对高维数据集找出维空间d 中的相关数据点。 2 2 相似性度量 聚类按照较高簇内相似度和较低簇间相似度的原则分组，“相似度”通过距离来度 量。许多基于内存的聚类算法选择如下两种有代表性的数据结构： 数据矩阵( d a t am a t r i x ，或称为对象一变量结构) ：它用d 个属性( 也称变量或度量) 来表现个对象。这种数据结构是关系表的形式，或者看作n x d 的矩阵。 6 第三章高维混合属性数据的投影聚类框架 x l d ： x n d ( 2 2 ) 相异度矩阵( d i s s i i i l i l 撕够m a t r i x ，或称作对象一对象结构) ：存储个对象两两之 间的近似性，表现形式是一个n x n 的矩阵。 o d ( 2 ，1 ) 0 d ( 3 ，1 ) d ( 3 ，2 ) 0 ： d ( n ，1 ) d ( n ，2 ) 0 ( 2 3 ) 其中讯一是对象i 与对象，之间相异性的量化表示，通常它是一个非负的数值，当 对象f 和对象，越相似和越“接近”，嘶叨的值就越接近o ；反之，如果两个对象越不同 或相距“越远”，川劬的值就越大。显然d 倒司积砂，且m 妒= o ，因此可以得到形如( 2 3 ) 的矩阵。相异度矩阵是对象对象结构的一种数据表达方式。 不同的数据类型的距离度量的计算方法也不同，不过在数学上，距离函数应该满足 以下四个要求； ( 1 ) d p ，o ：距离是一个非负的数值； ( 2 ) 嘶，0 = o ：一个对象与自身的距离是o ； ( 3 ) d 一，司驴，矽：距离函数具有对称性； ( 4 ) d 一，j p d p ，砂喇伪，：距离函数要满足三角不等式，从对象i 到对象，的直接 距离不大于途径任何其它对象h 的距离。 下面分别介绍三种数据类型的相异度计算方法吲。 ( 一) 数值型数据相似( 异) 度的计算 数值型数据又称作是区间标度变量，它是一个粗略线性标度的连续度量。如重量， 身高等。计算数值型数据的相似度的度量有：欧几里得距离，曼哈坦距离，以及明考斯 基距离。其中最常用的欧几里得距离定义如下： 俐= i 一习- 1 2 + i 知z 一再z 1 2 + + i 肋- 枷1 2 ( 2 。4 ) 这里的( 蜀，渤，彩和( 劫，枷”o 励是两个d 维的数据对象。 另一个著名的度量方法是曼哈坦距离，它定义如下： d ( i j ) - - - 1 x t l 聊l + i 船2 一习2j + 4 - j 埘x j , t i ( 2 5 ) 明考斯基距离是欧几里得距离和曼哈坦距离的概化，它的定义如下： d ( i j ) = ( 1 翦i 再l i q + i 】眈一刁2 r + + i 】甜- 】缸r ) ”9 ( 2 6 ) 这里口是一个正整数。当q = l 是，它表示曼哈坦距离，当q = 2 时表示欧几里得距离。 7 h ；砀 江南大学硕士学位论文 ( 二) 二元型数据相似( 异) 度的计算 表2 - i 二元变量的可能性表 对象j 1 o求和 l g ， q + r 对象i o占r占+ ， 求和 g + s，+ fp 二元型数据的取值只有两个状态：0 或者l ，o 表示该数据为空，l 表示该数据非空。 显然，如果象处理数值数据那样来对待二元变量会误导聚类结果，所以要采用特定的方 法来计算其相异度。假设二元变量的两个状态有相同的权重，可以得到一个形如表2 1 的可能性表。在表中，g 表示对象i 和对象，值都为1 的变量的数目，表示对象i 为1 而对象，为o 的变量的数目，j 表示对象i 为0 而对象j 为1 的变量数日，t 表示对象f 和对象，均为0 的变量数目，变量的总数是p ，p = 鼋+ ，蜘+ f 。 二元变量可分为对称的二元变量和不对称的二元变量。如果变量的两个状态是同等 价值的，并具有相同的权重，那么该二元变量是对称的，也就是两个取值0 和1 没有优 先权。基于对称二元变量的相似度称作恒定的相似度。对恒定相似度来说，评价两个对 象i 和，之间相异度的最著名的系数是简单匹配系数，其定义如下： 俐2 石r 而+ s ( 2 7 ) 如果两个状态的输出不是同样重要，那么该二元变量是不对称的。基于不对称的二 元变量的相似度被称作是非恒定的相似度。对此最著名的评价系数是j a e e a r d 系数，如 式( 2 8 ) 在它的计算中，负匹配的数目t 被认为是不重要的，因此被忽略。 俐2 而r + s ( 2 8 ) ( 三) 类别型数据相似( 异) 度的计算 类别型数据又称作标称型数据，它是二元变量的推广，具有多于两个的状态值。例 如，我国的民族是一个类别型变量，它有5 6 个状态：汉，蒙，藏等等。假设一个类别 型变量的状态数目是m 。这些状态可以用字母、符号或者一组整数表示。要注意的是 这些整数只是一个代号，并不代表任何特定的顺序。 两个类别型变量f ，_ ，的相异度可以用如式( 2 9 ) 简单匹配方法来计算； d ( i i ) = 业 p ( 2 9 ) 这里m 是匹配的数目，即对象f 和，取值相同的变量的数目，而p 是全部变量的数目。 s 第三章高维混合属性数据的投影聚类框架 2 3 高维数据的内在特征及其对算法的影响 ( 一) 稀琉性 假设一个d 维的数据集d s 存在于一个超级立方体单元q = 【o ，1 】d 中，数据在空间中 均匀分布，并且各个维之间是独立的。对一个边长为j 的超级立方体范围，一个点在这 个范围内的概率为一，由于s ，a 3 = a ，b ，c ，西? ，a 6 = a ， b ，c ，? ，a s = f a ，b ，c ，? ；彳2 ，a 7 为二元型，其取值有三种o ，一，? ) ，表示数据 点的该属性值为“是”或“否”；a 4 ，如，a 9 ，a l o 为数值型，它们的取值是一个连续 的实数。数据集中“? ”表示空缺值。 表3 - 1 原始数据集 属性 序号 a a 2彳，4 4a 5彳6a 7a sa 9a l o 0 0 1d ) ， b4 01 0 0口 y 口 1 11 1 0 0 2 口以c?9 9口 y c1 35 0 0 0 3b 口4 19 8 f ， 1 2 6 0 0 0 4口 力 4 21 0 2 ， c86 1 0 0 5 以d1 0 03 06 力 b 96 2 0 0 6c y 口2 05 4c y 9 6 4 0 0 7c y b2 25 5 cn口76 6 0 0 8c y c1 85 66n口 3 07 本文对这种混合属性数据集聚类的大体思路是这样的：首先对数据集中的数值型属 性进行维内分组，也即离散化，使得具有相同或相近数值的数据点的属性取值转化为某 个共同的属性标识，用区间标号代替实际值；然后，将数据集中所有的属性取值进行全 局重新编号，使得数据集转化成为一个类别型数据集，接着转化成一个事务；最后对这 个事务数据库再进行处理。 3 2 数值型数据序列的离散化 3 2 1 数值型数据序歹q 分组的相关定义 设x 是力个数据样本( 或称元素) x j ，勋，x n 的集合( 或称序列) ，将这个集 江南大学硕士学位论文 合的元素划分成m 个组g j ，国，6 k ，第f 组内含有的元素个数为o ，标准差为o g i ， 使得这m 组的标准差之和最小即 m i n ( o o ) 喜阳舯：蜃面声，石霉为未啪们+ c f n + 表示正整数，本文后面的该符号同此意义。 数值型数据的离散化主要有以下几种方法【2 】：分箱、直方图分析、聚类分析、基于 熵的离散化和通过“自然划分”的数据分段，本文这里介绍一种基于密度的离散化方法。 它不同于典型的k - m e a n s 方法，要输入分组的个数k ，这个输入参数对结果影响很大， 而且在对未知数据进行分组前，不可能得出到底要将数据分多少个组最合适。 定义3 1r - 邻域 设，i c ，p x ，元素p 的，- 邻域表示为n ，劬，定义为n ，劬= 扛x l d 砂r ) 。 其中r + 表示正实数，后面该符号同此意义，d ( ，) 表示两个元素之间的距离。 定义3 - 2 核心元素 设，r + ，k e 旷，元素p e x 被称作是核心元素c o r e r ，t 劬，如果p 的，- 邻域内包 含至少七个元素，即：c o r e r ，i 劬1 n h 例i 觑 反之，则称为边界元素，即b o r d e r ，i 例营阱，例i 啦。 定义3 - 3 直接边界可达 设，r + ，k e ，p ，q e x ，元素p 是从g 直接边界可达的，如果目是核心元素， p 是边界元素，且p 是g 的r - 邻域中的一个元素，即： d m r e a c r k ，如，p ) 耸c o r e r , g q ) a b o r d e r , , g p ) a p e n g q ) 。 定义3 - 4 直接核心相连 ， 设，r ? ，k e 旷，p ，q e x ，核心元素p 与核心元素g 是直接核心相连的，如果p 是g 的，邻域中的一个元素，且q 是p 的，- 邻域中的一个元素，即： d m c o i f n e c r r , 朐，纠营c o r e , , _ 纠a c o r 胞j 恼n ，缈八g n ，劬 定义3 - 5 核心相连 设，r + ，七矿，p ，g x ，元素p 与元素g 是核心相连的，如果存在一个序列的 元素p l ，m ，西，p i 呵，办印，使得肼- l 是从a 直接核心相连的，i = i ，2 ，栉1 即：( m 哪，i 向，营 3 p t ，p 2 ，a i x ：p t = q a p , , = p a v f 1 ，2 ，n - l ：d m c o u h m c r , ，i 函i ，j ，f + 定义3 - 6 最大相连集合 设，r + ，k e 时，非空子集合y x 是最大相连集合，如果y 满足以下条件： 1 6 墨三兰壹丝望鱼墨丝墼堡塑墨里塞耋堡墨 ( 1 ) 最大性：对y 中任意一个元素p ，y 中存在一个核心元素g ，使得p 是从g 直接边 界可达，或者p 与q 核心相连； ( 2 ) 相连性：对y 中任意两个元素p ，q ，如果它们是核心元素，则它们一定是核心相 连的； ( 3 ) 可达性：对y 中任意一个边界元素p ，一定存在一个核心元素g ，使得p 一定可从 q 直接边界可达。即：m a x c o n s e t ，“y ) u ) m a x i m a l i t y ：v p y ，3 q e y , s t c o r e r 删a ( d i r r e a c h r 胸，v c o n n e t r ，g q ，纠) ； ( 2 ) c o n n e c t i v i t y ：v p ，g y ，c o r e 删a c o r f - ，删jc 1 ) n n 珥，d q ，力) ； 0 ) r e a c h a b i l i t y ：v p y ：b o r d e r 剁，j q y ，s t c o r e r ，蒯a d i r r e a c h r ，朐，。 3 2 2 基于密度的分组方法( 啊) 使用上述的概念，基于密度的分组方法( d e n s i t y - b a s e dg r o u p i n gm e t h o d ，简称d g m ) 经过对序列一次扫描，能够探测到数据序列中任意大小的组。d g m 首先找到一个核心 元素，然后找出这个核心元素的最大相连集合，计算最大相连集合的方法见图3 - 2 。在 序列中，本文首先要检查该元素是否已经被处理，即它的组标识是否为u n c l a s s i f i e d ， 如果未被处理，该元素才被送入查找最大相连集合的方法中，否则，则应该新建一个组， 即组号增1 ，该过程见图3 1 。在查找最大相连集合过程中，如果当前被送入的元素不 是核心元素，它不能作为扩展分组的开始元素，将之标识为孤立点或者边界点后返回 d g m ；如果它是核心元素，因为在同一个组中所有的核心元素都是核心相连的，基于 这个核心元素找出与它核心相连的核心元素从而形成种子核心元素，找出所