（计算机软件与理论专业论文）分类数据的增量聚类算法研究与应用.pdf

中山大学硕士学位论文摘要 摘要 聚类分析作为重要的数据挖掘技术，已在电信、市场、金融、医学、科研和 互联网等诸多领域得到广泛应用。聚类就是根据相似性把对象划分成组的过程。 聚类分析的数据可分为数值数据和分类数据等。传统聚类算法对数值数据研究得 比较多，涉及的聚类相似性度量也较简单，往往是基于数值数据固有的距离意义， 对分类数据聚类的效果并不明显。同时，传统聚类算法和现有针对分类数据的聚 类算法没有考虑属性以及属性值在聚簇的不平衡性，认为所有属性值对聚簇的形 成起同等决定作用。一个好的聚类结果应该满足相同聚簇的对象尽可能相似，不 同聚簇的对象尽可能相异，对于分类数据而言，在某聚簇占优的属性值，在其它 聚簇出现的概率应该相对较小。同时，聚簇的属性值是不平衡的，普遍出现在各 个聚簇的属性值是不重要的，计算聚类相似性时应赋予较小的权重。基于以上两 点，本文提出新的分类数据相似性度量。 现实中分类数据集不仅具有维度高、规模大的特点，而且还有动态增长和更 新的特点。对分类数据聚类宜采用增量的聚类方式，充分利用已有的聚类结果， 对新来数据进行聚类，而且增量性也是衡量现代聚类算法的重要指标。基于分类 数据相似性度量的新方法，本文设计的分类数据聚类算法响应增量性的要求，是 具有可伸缩的增量聚类算法。在u c i 数据集和人工合成数据集上的实验表明新 算法能取得很好的聚类效果和聚类效率。将新算法应用到亚健康数据的聚类分 析，结果表明新算法还具有很好的可解释性和可用性。 关键词：分类数据，属性不平衡，增量聚类，聚类分析，亚健康数据 中山大学硕士学位论文 a b s u a c t a b s t r a c t c l u s t e r i n ga n a l y s i sa sa l li m p o r t a n td a t am i n i n gt e c h n i q u eh a sb e e nw i d e l yu s e d i nm a n ya p p l i c a t i o nf i e l d ss u c ha st e l e c o m , m a r k e t , f i n a n c e ，m e d i c i n e ，s c i e n t i f i c r e s e a r c ha n di n t e r n e ta n ds o 0 1 1 c l u s t e r i n gi sa g g r e g a t i n go b j e c t s i n t og r o u p s a c c o r d i n gt ot h e i rs i m i l a r i t y d a t af o rc l u s t e r i n g a n a l y s i s c a i lb ed i v i d e di n t o n u m e r i c a ld a t aa n dc a t e g o r i c a ld a t aa n ds oo i l t r a d i t i o n a lc l u s t e r i n ga l g o r i t h m sw h i c h g e n e r a l l yd e a lw i ln u m e r i c a ld a t a , h a v i n gs i m p l es i m i l a r i t yl l l e l t s u r e $ b a s e do i lt h e i r i n h e r e n td i s t a n c em e a n i n g ，c a n ta t t a i l ld e s i r a b l er e s u l t sw h e nc l u s t e r i n gc a t e g o r i c a l d a t a a tt h es a m et i m e ，t r a d i t i o n a lc l u s t e r i n ga l g o r i t h m sa n de x i s t i n gc l u s t e r i n g a l g o r i t h m sf o rc a t e g o r i c a ld a t a , d on o tt a k et h ei m b a l a n c eo fa t t r i b u t e sa n da t t r i b u t e v a l u e si nc l u s t e r si n t ol l c c o u n t ，w h i c hc o n s i d e ra l la t t r i b u t ev a l u e sh a v et h es a m e c o n t r i b u t i o nt ot h ed u s t e r sf o r m a t i o n ag o o dc l u s t e r i n gr e s u l ts h o u l da c h i e v eo b j e c t s a l ei l l o r es i m i l a ri ns a m ec l u s t e r s ，m o r ed i s s i m i l a ri nd i f f e r e n tc l u s t e r s f o rc a t e g o r i c a l d a t a , w ee x p e c tt h a t0 1 1 ea t t r i b u t ev a l u ep r e d o m i n a t e si nac l u s t e ro c c u r r i n gi no t h e r c l u s t e r s 谢t 1 1l o w e rp r o b a b i l i t y m e a n w h i l e ，a t t r i b u t ev a l u e sa r cu n e q u a li nc l u s t e r s a t t r i b u t ev a l u es p r e a d i n go v e i c l u s t e r si sn o ti m p o r t a n t , a n ds h o u l dh a v el o w e r w e i g h t w h e nc a l c u l a t i n gc l u s t e r i n gs i m i l a r i t y b a s e do na b o v et w oo b s e r v a t i o n s ，t h i sp a p e r p r o p o s e sai l e ws i m i l a r i t ym e a s u r t of o rc a t e g o r i c a ld a t a c a t e g o r i c a ld a t as e t si nr e a lw o r l da l en o to n l yh i g h - d i m e n s i o n a la n dl a r g e s c a l e ， b u ta l s od y n a m i e l yi n c r e m e n t a la n du p d a t e d c l u s t e r i n gc a t e g o r i c a ld a t as h o u l db e i n c r e m e n t a l ，w h i c hc a nt a k ef u l la d v a n t a g eo fp r e s e n tc l u s t e r sr e s u l tw h e nc l u s t e r i n g l l e wc o m i n gd a t a m o r e o v e r , i n c r e m e n t a li sa l s oa l li m p o r t a n ti n d e xf o re v a l u a t i n g m o d e mc l u s t e r i n ga l g o r i t h m s i nt h i sp a p e r , b a s e do nt h en e ws i m i l a r i t ym e a s u r e p r o p o s e df o rc a t e g o r i c a ld a t a , ac l u s t e r i n ga l g o r i t h mf o rc a t e g o r i c a ld a t ai sd e s i g n e d b yr e q u e s to fi n c r e m e n t a l ，w h i c hi sas e a l a b l ei n c r e m e n t a lc l u s t e r i n ga l g o r i t h m e x p e r i m e n t so z lt h eu c i d a t as e t sa n ds y n t h e s i z e dd a t as e t ss h o wt h a tt h ea l g o r i t h m i i i 中山大学硕士学位论文分类数据的增量聚类算法研究与应用 c a na c h i e v eg o o dc l u s t e r i n ge f f e c t i v e n e s sa n d e f f i c i e n c y a p p l yt h i sn e wa l g o r i t h mf o r s u b h e a l t hd a t ac l u s t e r i n ga n a l y s i s ，a n dt h er e s u l ti n d i c a t e st h a tt h en e wa l g o r i t h m h a v ew e l li n t e r p r e t a b i l i t ya n du s a b i l i t y k e y w o r d s ：c a t e g o r i c a ld a t a , a t t r i b u t ei m b a l a n c e ，i n c r e m e n t a lc l u s t e r i n g ，c l u s t e r i n g a n a l y s i s ，s u b - h e a l t hd a t a i v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 学位论文作者签名：! 醢丑滏 日期： 丝丝：2 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：倔计泽 日期：纠。年月岁日 导师签名： 日期：f ，。年f 月乡日 中山大学硕士学位论文第l 章绪论 第1 章绪论 1 1 论文研究背景及选题意义 伴随着信息技术的快速发展和社会经济活动的日益频繁，各行各业都有大量 的数据产生，如金融证券每天的巨额交易数据；同时网络和数据库技术的迅速发 展，使得收集和存储数据更为方便快捷。从数据的海洋中获取有用信息或发现知 识，是当今行业竞争的迫切需要。传统数据分析工具只能做一些表层的数据处理 工作，很难从大规模的海量数据获取数据的内在关系和隐含信息，从而导致“数 据丰富，信息贫乏 的现象。因此，我们需要强而有力的数据分析工具，能够自 动智能地将数据转化为有用信息和知识。数据挖掘技术便是在这样的需求背景下 产生和发展。由于其巨大的商业应用价值，数据挖掘现已成为数据库和信息决策 领域最热门的研究方向，受到学术界和工业界的广泛关注。 数据挖掘又称数据库中的知识发现( 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 ， k d d ) 。它结合数据库、统计学、模式识别和机器学习等技术和学科理论，提出了 许多能从大量的、不规则的、不完整的、带噪声的数据集合中提取出隐含在其中 的，人们事先不知道的，但又是潜在有用的信息和知识，进而为行动决策提供依 据的有效方法【l 】。数据挖掘的主要方法是分类预测、聚类分析和关联规则挖掘； 基本步骤是数据预处理、数据挖掘、模式评估和知识表示，其中数据预处理主要 有数据清理、数据集成、数据选择和数据变换。 聚类( c l u s t e r i n g ) 就是根据相似性把对象划分成组的过程。将聚类所得到 的每个对象集合称为聚簇( c l u s t e r ) 。聚类划分对象的基本原则是聚簇内的对象 尽可能相似，聚簇间的对象尽可能相异。通过对数据进行聚类，分析数据聚簇的 特征，可以发现数据内在的相似性和分布聚集的规律。聚类分析作为数据挖掘重 要的数据分析技术，无论在图像处理和市场分析，还是在模式识别和离群点分析 等都有着广泛的应用，受到许多研究人员的热切关注并相继提出了许多聚类算 法。传统聚类算法可大体分为层次聚类算法、划分聚类算法、基于密度的聚类算 中山大学硕士学位论文分类数据的增量聚类算法研究与应用 法、基于模型的聚类算法和基于网格的聚类算法等【1 。2 1 。现今数据集不仅具有规 模大、维度高的特点，而且还具有动态增加和更新的特点。这对聚类算法提出了 不少挑战，它要求聚类算法不仅是可伸缩的，可以处理高维大规模数据，而且还 能够增量聚类的，针对静态数据集聚类的传统聚类算法显然是不合适的。 分类数据是指数据记录由分类属性即名词属性组成的非数值类型的数据，广 泛出现在心理学、市场调查等实际应用领域。传统聚类算法都是针对数值数据提 出来的聚类算法，聚类模型的建立是基于数值属性( 变量) 的连续性意义如采用 基于距离的相似性度量。分类数据则没有这些内在的距离含义，直接使用基于距 离的传统聚类算法对分类数据进行聚类，是值得怀疑和推敲的。如把颜色属性( 变 量) 中的红、绿、蓝对应为数值0 、l 、2 ，基于距离来度量相似性的聚类算法会 认为红色和绿色比红色和蓝色更相似，因为前者比后者的距离短，事实上任何一 种颜色和其它颜色都不相似。传统聚类算法对分类数据附加了距离信息从而导致 错误判断，因此，聚类的结果缺乏说服力。另外分类数据一般都是高维度的数据 如购物篮事务数据和w e b 访问数据，要求聚类算法在维度上具有可伸缩的 ( s c a l a b l e ) 能力。由于分类数据这些新特点和对聚类的新要求以及它的普遍性， 设计针对分类数据的聚类算法吸引了不少学者和应用人士的兴趣和关注【3 1 4 】。 在现实世界描述对象特征的属性是不平衡的，某些属性是重要的而其他属性 却显得没有那么重要。在聚类中属性的不平衡性主要表现在属性值在聚簇间分 布的不平衡性，不同属性值在聚簇中起得的作用不尽相同。聚簇所表现的性质 和特征往往由少数几个重要属性值来决定。一般聚类算法都是认为数据集中各 个属性是平等的、具有相同的权重，而且即使要考虑属性的不平衡性，聚类前也 可以先对数据集进行预处理，挑选出主要属性再进行聚类。但是这种观点认为数 据集是静态的，认为属性的主次关系不会因数据集的变化而变化的。增量聚类算 法所针对的数据集是动态增长的，而且数据规模往往很大，先进行特征选择等预 处理的方法是不可行的。虽然有聚类算法考虑到属性的不平衡性，在聚类过程中 实现对属性进行加权，但这些聚类算法都是针对静态数据集【l 6 】。 综上所述，分类数据普遍存在，而增量性又是聚类算法的现代要求，设计针 对分类数据的增量聚类算法具有重要的应用研究意义。同时现实数据中属性以及 属性值之间是不平衡的，当数据集是动态增长时，先通过特征选择等预处理再进 2 中山大学硕士学位论文第1 章绪论 行聚类的方式已经不可行，所以属性的不平衡性考虑应该融合到聚类算法本身。 结合以上三点的聚类算法具有较大的理论研究和应用意义，本文在这方面努力， 提出考虑属性不平衡性的分类数据的增量聚类算法，即i c a i c ( ! n c r e m e n t a l l u s t e r i n ga l g o r i t h mw i t h a t t r i b u t ei m b a l a n c ec o n s i d e r e df o rc a t e g o r i c a l d a t a ) 算法，而且还期望新算法具有数据规模和数据维度的可伸缩性，即要求新 算法的计算复杂度较低，接近线性复杂度。 健康是现代社会和谐生活的一个主题。世界卫生组织( w o r l dh e a l t h o r g a n i z a t i o n ，w h o ) 对健康作出了如下定义：健康是一种身体、精神和交往上 的完美状态而不只是身体无病。虽然这个定义带有鸟托邦的味道，但它指出了健 康包括身体、精神和社会交往三个方面，对亚健康研究起到了一定的指导意义。 亚健康作为介于健康与患病之间的第三种状态，主要表现有焦虑、健忘、抑郁、 易怒、头痛、疲劳和失眠等症状，对患者的工作生活产生较大的不良影响，甚至 严重者可向身心疾病发展而成为患病状态。目前在我国亚健康发生率高，未干预 的亚健康状态容易向身心疾病发展，及早发现自身亚健康状态是实现健康的首要 保证。通过结合传统中医理论与亚健康研究，建立亚健康状态的中医辨识和分类 具有重要的医学研究和卫生应用意义。广东省中医院亚健康研究课题组在全国范 围调查了八千多名亚健康患者，收集了大量的亚健康不同症状表现的数据。这些 数据不仅规模大，而且是高维度的分类数据，对聚类分析算法的聚类效果和聚类 效率等都提出了很大的挑战。因此，本文把分类数据增量聚类新算法应用到亚健 康数据挖掘的聚类分析中，让真实数据检验新算法在实际应用领域的聚类分析能 力，考察它的聚类结果是否可解释的，可理解的和可用的。 1 2 国内外研究现状 1 9 8 9 年第1 1 届国际联合人工智能学术会议( i n t e r n a t i o n a lj o i n t c o n f e r e n c eo na r t i f i c i a li n t e l l i g e n c e ，i j c a i ) ，首次提出数据库中知识发 现( k n o w l e d g ed is c o v e r yi nd a t a b a s e ，k d d ) 的概念，就是用机器学习的方法分 析存储在数据库管理系统的数据，发现隐藏在数据中的规则和知识。1 9 9 5 年美 国计算机协会( a s s o c i a t i o nf o rc o m p u t i n gm a c h i n e r y ，a c m ) ，首次提出数据 中山大学硕士学位论文分类数据的增量聚类算法研究与应用 挖掘的概念，数据挖掘( d a t am i n i n g ) 就是从数据库、数据仓库或其他的数据 集合中提取隐含的、事先未知而又潜在有用的规则和模式或更高层次知识的过 程。可以看出无论知识发现还是数据挖掘，目标都是从数据中发现潜在有用的数 据模式或知识，实际上这两个概念术语也常不加以区分。随着k d d 在学术界和工 业界的影响越来越大，1 9 8 9 年成立的k d d 专题讨论会于1 9 9 5 年更名为k d d 国际 学术会议，正式成为数据挖掘领域一年一度的项级会议，所收录论文水平质量高， 涵括理论研究和应用两个方面。除此之外著名的数据挖掘学术会议还有i c d m 、 p k d d 等，相关的还有v l d b 、i c d e 、i c m l 等；著名数据挖掘期刊有d m k d 、t k d e 、 a c mt r a n s o nk d d 等。 就国内而言，现在也有相当一部分人员从事数据挖掘方面的研究，并且发表 了不少顶级的学术论文。重要学术会议“全国数据库学术会议 和重要期刊计算 机学报、软件学报等都有一些高水平的数据挖掘领域的论文。在应用领域，百度、 腾讯和阿里巴巴等互联网企业纷纷成立自己的数据挖掘研究部门，把数据挖掘技 术推广应用到自家的产品和服务；移动、电信等通讯公司采用数据仓库和数据挖 掘技术建立经营分析系统实现数据运营；银行系统运用数据挖掘技术实现商业信 用评估和资金风险预警等。 可见近年来数据挖掘在研究和应用方面发展迅猛，尤其是在市场、金融、互 联网等领域的应用更为迅速，比研究的发展速度还要快。作为数据挖掘重要技术 之一的聚类分析，无论在图像处理和市场分析，还是在模式识别和离群点分析等 都有着广泛的应用。随着信息技术的发展，数据挖掘的数据对象也发生了变化。 比如从传统的关系数据库发展到时态数据库，从静态数据发展到动态的数据流， 从结构化的关系表数据发展半结构化的x m l 数据等等。数据挖掘的方法也相应地 有着不同程度的发展。 聚类作为数据挖掘领域的一个非常活跃的研究课题，聚类的主要方法和研究 方向如图卜1 所示。传统聚类算法主要有层次、划分、基于密度、基于网格和基 于模型等五种聚类方法。可伸缩的聚类主要涉及增量聚类，数据流聚类，数据概 括和抽样等内容。高维数据的聚类主要涉及特征选择和子空间聚类等研究内容， 谱聚类主要应用在图像处理的图像分割和图划分。使用信息论聚类的方法主要有 基于信息熵和信息瓶颈两类。此外还有集成聚类、支持向量聚类、双聚类、非负 4 中山大学硕士学位论文 第l 章绪论 矩阵分解和分布式聚类等。事实上聚类方法繁多并不限于这些，比如还有结合模 糊数学和智能算法的聚类算法等。 n o n - n e l 尊ti t h tr i 工，7 a c t o r i z t ti o n 蹦r o p t - 五l s e c li 啪m ti o n 如ttle r l e e k d c l u s te z i 】略 图1 - 1 聚类的主要方法 目前出现分类数据聚类算法研究方向，主要原因是传统聚类算法把注意力集 中在聚类的过程而非聚类的对象，没考虑到分类数据有许多与数值数据不同的特 点，而现今分类数据又普遍存在心理学、市场调查等诸多领域。因此，对分类数 据的聚类自然吸引了不少学者的兴趣和关注：1 9 9 7 年香港大学的黄哲学教授扩 展k - m e a n s 算法，将均值取代为众数，提出了k - m o d e s 算法【3 】。k - m o d e s 算法在 继承了划分聚类快速聚类优点的同时，也引入聚簇初始中心敏感的缺点。1 9 9 9 年s g u h a 等人在i c d e 会议上提出基于“链接数”的r o c k 算法【4 】。r o c k 算法是 分类数据的凝聚层次聚类算法，对噪声数据有很好的鲁棒性，但它计算时间复杂 是o ( n 2l o g n ) ，不适宜直接对大规模数据聚类，需要抽样技术的辅助。b a r b a r ad 等人于2 0 0 2 年提出c o o l c a t 算法 5 1 ，认为所有聚簇的熵越小则聚类结果越好， 聚类方式是增量的，但该算法在计算聚簇的熵时认为属性之间是相互独立的。 2 0 0 2 年哈尔滨工业大学何增有等人在计算机科学技术学报( 英文版) 上发表了 基于计算聚簇中属性值支持度( 实质是属性值的频数) 增量聚类的s q u e e z e r 算 法【6 】，该算法存在的主要问题是很难通过控制相似度阀值产生我们想要的聚簇个 数，另外它对数据的输入次序敏感。l i m b o 算法【刀由p a n d r i t s o s 等人在2 0 0 4 年提出，也是基于熵的分类数据聚类算法，将聚类归结为最小化信息损失。c l u c 5 中山大学硕士学位论文分类数据的增量聚类算法研究与应用 算法【8 】和f a v c 算法【9 】都是基于聚簇中属性值频数的分类数据的划分聚类算法。 2 0 0 7 年e u g e n i oc e s a r i o 等人提出无需用户输入参数的分类数据的分裂层次聚 类a t d c 算法f l o 】，而随后2 0 0 9 年厦门大学的熊腾科等人采用m c a ( m u l t i p l e c o r r e s p o n d e n c ea n a l y s i s ) 方法改进聚簇的分裂效率而提出d h c c 算法【1 1 】。以上 分类数据聚类算法都存在的不足是没有考虑属性以及属性值之间在聚簇的不平 衡性，因此本文从这个角度入手，开展分类数据的增量聚类算法研究。 1 3 本文的主要研究内容 分类数据是由分类属性即名词属性组成的数据。数值数据则是由数值属性组 成的数据。分类属性与数值属性的最大区别是分类属性没有距离的含义，如颜色 属性中红、绿、蓝等，我们不能说红与绿的距离比绿与蓝的距离近等。传统聚类 算法对数值数据研究得比较多，涉及的聚类相似性度量也比较简单，往往是基于 数值数据固有的距离意义。它们在分类数据上的聚类效果并不理想。而现今分类 数据又是普遍存在的，设计针对分类数据的聚类算法吸引了不少学者的兴趣。本 文深入分析分类数据与数值数据的本质区别，指出传统基于数值数据的聚类算法 在分类数据失效的原因，同时阐述现有主要分类数据的聚类算法的基本思想特点 和存在的不足。 传统聚类算法一般都是基于静态数据集的，即聚类是在整个数据集上进行 的，聚类过程中数据集是没有新数据加入或删除的；如果数据集发生了变化，则 聚类必须重头再来。然而现今大规模的数据集随处可见，在有限的内存空间不可 能一次性把所有数据读进内存，再作数据的聚类运算，而且数据集都是存于动态 增加和更新的过程，推倒重来对整个数据集进行重新聚类也是不可取的。这要求 聚类算法要具有增量性，可以利用原有的聚类结果。本文提出的分类数据聚类的 新算法满足增量性的要求，是以增量的方式进行聚类。新聚类算法分为初始步和 增量步两部分进行，初始步只需执行一次；数据集的每次动态增长，聚类只需执 行增量步。这就很好地利用已有聚类结果，提高对数据的聚类分析效率。 一般聚类算法都是认为数据集中各属性是平等的、具有相同的权重，而且即 使要考虑属性的不平衡性，聚类前也可以先对数据集进行预处理，挑选出主要属 6 中山大学硕士学位论文第1 章绪论 性再进行聚类。但是这种观点认为数据集是静态的，认为属性的主次关系不会因 数据集的变化而变化。增量聚类算法所针对的数据集是动态增长而且数据规模往 往很大，先进行特征选择等预处理的方法是不可行的。在聚类中，属性的不平衡 性主要表现在属性值在聚簇间分布的不平衡性，不同属性值在聚簇中所起的作 用不同。聚簇所表现的性质和特征往往由少数几个重要属性值所决定。本文通 过分析分类数据的聚类实质，提出新的计算数据点与聚簇相似性的度量方法，它 是基于属性值在聚簇的条件概率和属性值分布不平衡性加权的相似度计算方 法。基于这个新相似性度量，本文提出了新的分类数据的增量聚类算法。在u c i 数据和人工合成数据的实验表明新算法不仅聚类速度快，有很好的可伸缩性，而 且还能产生质量不错的聚类结果，特别是当数据集属性不平衡性比较明显的时 候，聚类效果和效率都优于同类算法。 广东省中医院亚健康课题研究组为研究辨别和分类亚健康状态收集了大量 数据，期望通过聚类分析，挖掘亚健康人群的潜在分布特征和规律，从数据分析 上支持亚健康的医学研究。该亚健康数据是分类数据构成的，是规模大维度高的 数据集。按照数据挖掘的方法流程，本文将新算法应用到亚健康数据的聚类分析 上，挖掘分析亚健康人群的聚簇特征和亚健康不同表现的关系。对亚健康数据的 聚类分析应用表明新算法具有很的可解释性和可用性。 1 4 论文的组织结构 论文共分5 章。首先是绪论，介绍论文研究背景及选题意义，国内外研究现 状，论文的主要研究内容和组织结构，接着是聚类分析基础的相关介绍，然后是 对本文所提出的分类数据增量聚类算法进行详细论述，通过实验说明新聚类算法 的聚类效果和聚类效率，并且把新聚类算法应用到亚健康数据的聚类分析，说明 新聚类算法具有很好的可解释性和可用性，最后是论文主要工作的总结和展望。 具体章节的主要内容如下： 第1 章为绪论。首先介绍论文的研究背景及选题的意义，接着对国内外研究 现状，主要研究内容和论文组织结构进行阐述。 第2 章为聚类分析基础。首先介绍聚类定义以及聚类算法要求，接着介绍聚 7 中山大学硕士学位论文 分类数据的增量聚类算法研究与应用 类算法的关键内容，聚类的相似性度量，然后对主要聚类算法分成六种介绍：基 于层次的聚类算法、基于划分的聚类算法、基于密度的聚类算法、基于模型的聚 类算法、基于网格的聚类算法和其它聚类算法，最后简单阐述聚类分析的主要应 用以及对本章内容进行小结。 第3 章为分类数据的增量聚类算法。首先对数据类型进行分类，并介绍分类 数据的主要聚类算法的基本思想特点以及不足，接着通过对分类数据聚类的实质 和聚簇中属性不平衡性的考察，提出基于新相似度的分类数据增量聚类算法 i c a i c ，并详细介绍i c a i c 算法的基本框架和计算复杂度，并在u c l 数据集和人 工合成数据集上，和其它分类数据聚类算法进行实验比较，结果说明i c a i c 算法 有很好的聚类效果和聚类效率，最后是本章内容小结。 第4 章为i c a i c 算法在亚健康数据的应用。论述亚健康数据聚类分析的目标， 说明亚健康数据内容和特点，介绍亚健康数据预处理的主要内容一数据清理、 数据选择和数据变换，使用i c a i c 算法对亚健康数据进行聚类并对结果进行分 析，表明i c a i c 算法不仅是高效的增量聚类算法，而且它还具有很好的可解释性 和可用性，最后对本章内容进行小结。 第5 章为总结与展望。对本文所做的主要工作进行总结并阐述下一步研究工 作的主要内容和方向。 8 中山大学硕士学位论文第2 章聚类分析基础 第2 章聚类分析基础 2 1 聚类定义及算法要求 聚类( c l u s t e r i n g ) 就是依相似性将对象划分成组的过程。聚类所得到的对 象集合称为聚簇( c l u s t e r ) 。聚类划分对象的基本原则是聚簇内的对象尽可能相 似，聚簇间的对象尽可能相异。自古以来，聚类便是人们认识世界和客观规律的 基本方法。正所谓“物以类聚，人以群分，通过把握事物这种相似与区别，对 事物进行分门别类，获取事物共性与个性特征，抽象成概念并进行比较学习，不 断深化对客观世界的认识。 聚类分析起源于分类学，随着科学技术的发展，现代聚类分析方法则结合了 统计学，机器学习，人工智能，分布式计算和高级数据库等多个学科和技术。按 照机器学习观点，聚类是一个无监督的学习过程，无需使用训练数据和训练学习， 倾向数据的自然划分，称为自动学习。通过聚类自动识别对象空间中稀疏和稠密 区域，发现数据属性与数据全局分布模式之间的关系。 聚类分析作为数据挖掘的工具，可以获得数据分布和聚簇的情况，确定感兴 趣的聚簇以便进一步分析研究。聚类分析已在许多领域得到应用，如模式识别， 图像处理，市场研究和数据分析。聚类用于数据的预处理，可以对数据光滑去噪、 填补缺失值和数值归约等。根据购买模式聚类顾客，刻画顾客群的特征，实现向 顾客推荐感兴趣商品。聚类分析可以检测数据中的离群点，在信用卡欺骗和网络 入侵检测得应用。 聚类是广泛应用的数据挖掘技术之一，同时也是一个富有挑战性的研究领 域，它的潜在应用都提出各自的要求。总的来说，对数据处理的聚类算法有如下 要求【1 】： 1 ) 可伸缩性：许多聚类算法在小规模数据工作得很好，但在大规模数据上 却出现聚类效果有偏差或者运算时间长计算效率低的问题。因此，要求 现代聚类算法具有高度的可伸缩性。 9 中山大学硕士学位论文分类数据的增量聚类算法研究与应用 2 ) 处理不同数据类型的能力：许多聚类算法都设计处理数值( n u m e r i c a l ) 数据类型的，但现实数据还有分类( c a t e g o r i c a l ) 数据类型和有序 ( o r d i n a l ) 数据类型等，以及这些数据类型的混合。 3 ) 发现任意形状的聚簇：传统基于距离度量相似性的聚类算法趋于发现球 状的聚簇，但聚簇可以是任意形状的。设计可以发现任意形状聚簇的聚 类算法也很重要。 4 ) 较少的用户输入参数考虑：很多聚类算法常常要求用户输入一定的参数， 如期望聚簇数目，数据相似性的阀值等。聚类结果是输入参数敏感，特 别是高维数据，参数通常难以确定，需用户有较多的专业领域知识。不 仅用户负担加重，聚类质量也难以控制。 5 ) 处理含噪声数据的能力：现实数据集是不完美的，数据值缺失、离群点 数据和错误数据通常存在。一些聚类算法对于这样的数据是敏感的，往 往聚类质量差，不尽入意。 6 ) 增量聚类和记录输入次序不敏感：一些静态聚类算法不能将新插入数据 合并到已有聚簇，需要重新进行聚类，所以不适合动态增长的数据集。 另外一些聚类算法对数据的输入次序敏感，按不同次序提供数据，生成 的聚类差别大。开发增量聚类算法和数据输入次序不敏感的聚类算法都 有重要的现实意义。 7 ) 处理高维数据的能力：高维数据普遍存在数据库和数据仓库中，处理高 维数据的聚类要求算法有克服“维度灾难 ，数据高度稀疏的本领。 8 ) 基于约束的聚类：现实聚类中有生成聚簇大小的限制和对象间的一些条 件约束，如住户聚类中要考虑河流公路等地理限制因素。 9 ) 可解释性和可用性：数据挖掘的目的是发现数据的潜在模式或规律，以 及利用这些数据模式或规律更好地指导实践，制定更有效的商业计划。 这就要求聚类分析的结果是可解释和可用的。 2 2 聚类的相似性度量 聚类定义说明了聚类的核心问题是对象相似性的度量，如何度量相似性是保 l o 中山大学硕士学位论文第2 章聚类分析基础 证聚类质量的重要问题。因此在讨论主要聚类算法前，有必要先介绍相似性的度 量方法。数据类型不同，采用的相似性度量不同。聚类分析的数据通常是一个数 据矩阵形式，每行是p 维的行向量，代表一个对象( c a s e ) ；每列是1 3 维的列向量， 代表一个变量( v a r i a b l e ) 或称属性。属性类型分为区间标度变量，二元变量， 分类变量，序数变量和比例标度变量，相应地这些变量的相似度测量也就不同。 区间标度变量是一种粗略线性的连续变量，比例标度变量则是非线性的连续变 量。有时把两者都统称数值( n u m e r i c a l ) 变量，因为它们都有距离和大小的含 义，可作除法运算求平均值等。二元变量也称布尔变量，是分类( c a t e g o r i c a l ) 变量的特例，序数变量性质则是介于数值变量与分类变量之间。关于三者区别和 联系第3 章第1 节有详细的讨论。 区间标度变量有距离含义，自然采用距离公式作为相似度测量。数据点的距 离越近，则相似度越高；相似度与距离成反比，相似度亦称为相异度，可通过求 倒数或乘负数相互转化。常用距离度量是欧氏距离，定义如下： m _ ，) = 1 1 薯一一1 1 5 = ( ( - x j l ) 2 ) “2 ( 2 一1 ) 此外还有曼哈顿距离和闵可夫斯距离，它们都满足三角不等式，分别称为l 2 范 数，l 1 范数和l q 范数。如对每个变量赋予一个权重，则加权的闵氏距离公式如 下： 媳) = ( ( - x j k ) 9 ) “9 ( 2 2 ) 二元变量只有0 、1 两种状态，0 表示该变量不出现，l 表示出现。两个二元 变量的相异度可以由简单的匹配度来计算，如： 蜊，= 面酱 3 ， 其中m 。表示对象f 值为1 且对象_ ，值为0 的变量的数目；m 。表示对象i 值为0 且对象歹值为1 的变量的数目。和m 。表示的意义类似。对象i 和对象，的 非对称二元相似度按下式计算【1 】： s i r a ( i , 舻瓦 ( 2 - 4 ) 中山大学硕士学位论文分类数据的增量聚类算法研究与应用 分类变量的相似度亦可以简单匹配的j a c c a r d 系数方法来计算如公式3 - 2 。 有序变量的相异性度量可以用公式2 5 来计算： 嘶= 吉喜掣 5 ， 其中变量值映射到o ，刀- 1 。 除了基本的简单匹配和基于距离来计算相似度( 相异度) 外，求向量的余弦 也可作为相似性的度量，它优点是不受向量绝对长度影响，适合高维空间数据对 象的相似度计算( 公式2 - 6 ) ，对象相似也就是相关的，相关系数的也可作为相 似度度量的方法( 公式2 7 ) ： 跏( x ：y ) 2 赢 2 6 ) 眦川= 等嚣铲 7 ， 其中d ( ) 是方差，e ( ) 是期望。 以上度量方法简单容易理解，实际上相似度或相异度的计算方法远远不止上 面几种，不同聚类算法都有自己灵活的计算相似性方法，如r o c k 算法引入共享 邻居数来衡量聚簇对象的相似性，d b s c a n 算法则采用密度相连性的概念来计算。 聚类对象的相似性度量方法是聚类算法的关键，也是聚类算法的特色。 2 3 主要聚类算法的分类 聚类分析是一门非常重要的数据挖掘和分析技术，也是一个相当活跃的研究 领域。现今跨学科交叉发展，许多结合其它领域技术和思想的聚类新算法不断出 现【2 】【1 1 8 1 ，本节主要介绍几种代表性的聚类算法以及其它一些新发展的聚类算 法。 2 3 1 基于层次的聚类算法 层次聚类( h i e r a r c h i c a lc l u s t e r i n g ) ，按聚类形成的过程可以分自项向下 1 2 中山大学硕士学位论文第2 章聚类分析基础 的分裂层次聚类和自底向上的凝聚层次聚类。分裂层次聚类( h i e r a r c h i c a l s p l i t t i n gc l u s t e r i n g ) 是首先将把整个数据集置于一个聚簇( c l u s t e r ) 中， 然后将它逐步细分更小的聚簇，重复该过程，直至每个数据对象自己成为一个聚 簇，或满足某种终止条件停止。凝聚层次聚类( h i e r a r c h i c a la g g l o m e r a t i v e c l u s t e r i n g ) 算法是首先把每个数据对象作为一个聚簇，然后逐步合并原予聚簇 成为更大的聚簇，重复该过程，直至最终形成一个大的聚簇，或满足某种终止条 件是停止。层次聚类方法存在的缺陷是一旦一步合并或分裂完成，就不能撤销它。 最经典的凝聚层次聚类算法是基于链接算法。单链接算法是基于聚簇间最小 距离来合并聚簇，如果把数据点看作为图的顶点，图的边则为它们的距离，单链 接算法实质是最小生成树的算法。全链接算法类似，只是根据聚簇间的最大距离 来合并聚簇，每个聚簇被看成是一个最大完全子图。算法空间复杂度都是o ( n 2 ) ， 时间复杂度是o ( n 2l o g n ) 。单链接算法只要两个聚簇具有相近的点，就将它们合 并，导致合并聚簇可能存在一些根本不相关的点，即所谓的链式效应【1 8 】，易受噪 声数据影响产生的聚簇质量不高【2 】。 b i r c h 算法【1 9 1 是综合多段阶层次聚类方法，主要包括两个阶段。第一阶段， 扫描数据库建立聚类特征c f 树，该树保留了数据的内在聚类结构，看作是数据 的多层压缩；第二阶段，选定特聚类算法，在c f 树上进行聚类。随着的数据对 象的插入，c f 树可以动态地构造，支持增量聚类，计算复杂度是d ( 力) 的。 r o c k 算法【4 】提出用共享邻居数来度量聚簇的相似性，计算时间复杂度为 o ( n 2 + n m 。朋口+ 刀2 l o g n ) ，其中聊肺，分别是近邻数目的最大值和平均值。 c h a m e l e o n 算法是层次聚类的方法，采用了动态建模来确定聚簇间的相似度， 在最坏情况下的计算时间复杂度是o ( n 2 ) ，可以发现任意形状的聚簇。 2 3 2 基于划分的聚类算法 划分聚类算法，对给定的后6 疗) ，把n 个对象的数据集，划分成k 个聚簇， 使得同一聚簇的对象相似，不同聚簇的对象相异。十大数据挖掘算法之一的 k - l e a n s ( k 均值) 算法便是划分聚类算法【2 0 】。 十m 大学硬# 论文 分樊数据的增量聚裳算法研究与应用 km e a n s 算法：首先随机选取k 个数据点分别作为1 个初始聚簇中心( 均值 点) ，接着将余下数据点划分到与聚簇均值点的距离最小的聚簇，然后重新计算 每个聚簇的均值；重复计算每个数据点与所有聚簇均值点的距离，重新调整它所 属的聚簇，重复执行该过程直至准则函数( 目标函数) 收敛或满足迭代次数。准 则函数( 目标函数) 常用平方误差准则。 k - m e a n s 算法是对初始中心点选择敏感的，图2 - 1 和图2 _ 2 演示3 个初始中 心点选择不同，聚类结果迥然不同的情况【2 l 】，其中加号表示聚接中心，相同颜色 的点表示同属于某个浆簇： 图2 - 1 初始中心点选择较好的k - m e a n s 算法聚类过程 i 均值算法的计算复杂度是o ( n ) ，因其算法简单易理解且具有相当可伸缩性，在 数据流和大型数据集上能得到有效应用也常用于文本聚类分析。 此外女均值有一些变种如k - m o d e ，p 删和c l a r a n s 等”j 。针对k 均值固有的 聚簇个数和初始聚簇中心敏感的不足，有结合遗传算法求全局最化解的方法，也 有加上惩罚过度拟台因子的凝聚f c m 算法口“。为了解决k - m e a n s 算法只适台数据 线性可分的局限， 2 3 提出全局的基于核运算将数据转到高维空间线性可分的 k - m e a n s 算法。 羲囊。 ”lllljjll1 w 簿黛 中m 大学颈学位论立 第2 章聚粪分析基础 1 4 4：缘， ”1 ? 7