（计算机应用技术专业论文）混合属性聚类算法研究.pdf

摘要 数据聚类是数据挖掘中的一个重要分支，目前已有的数据聚类算法大部分局限于处 理只具有连续属性的数据，另外有少量的算法局限于处理只具有标称属性的数据，如果 只处理一类属性，在混合属性条件下必然损失数据信息，影响数据挖掘的质量。如何进 行混合属性数据的聚类，目前还是一个充满着挑战性的领域。 本文的主要研究工作包括以下几个方面： 1 先介绍了k - p r o t o t y p e s 算法，然后提出了2 种针对k - p r o t o t y p e s 的改进方法， 第一种是在k - p r o t o t y p e s 算法和模糊k - p r o t o t y p e s 算法的基础上设计了一种新的算法 类属性分解法，这种方法能够克服原有方法的不足，并可以产生较好的聚类结果。 第二种是在k - p r o t o t y p e s 算法基础上设计的一种基于分组选择初始点的改进算法，并 且通过遗传算法对分组做进一步的改进。 2 提出了一种基于b i r c h 算法的混合属性的聚类算法，在u c i 数据集上的实验表明， 文中提出的算法具有较好的性能。 3 提出了一种基于改进的d b s c a n 算法的混合属性的聚类算法，给出了相关描述， 并指出了这种算法的优点。 4 给出了一种基于聚类融合的混合属性聚类算法( c e m c ) ，在进行混合属性数据聚类 时采用了聚类融合的方法体系，并且推广了聚类融合方法，混合属性数据聚类时通过使 用聚类融合理论来求解问题，在本文对这个问题的探讨中，建立了算法框架，进行了求 解，提出了目标函数和算法，最后在实际数据中检验了本算法的效果。 关键字：聚类；混合属性；b i r c h 算法；数据挖掘；d b s c a n 算法；数据融合 a b s t r a c t t h ed a t ac l u s t e ri sa ni m p o r t a n tb r a n c hi nd a t am i n i n g a tp r e s e n tt h ed a t ac l u s t e r a l g o r i t h m sw eh a v ea r em a jo r i t yc o n f i n e dt od e a lw i t ht h ed a t aw h i c ho n l yh a v et h ec o n t i n u a l a t t r i b u t e s ；m o r e o v e raf e wa l g o r i t h m sa r ec o n f i n e dt od e a lw i t ht h ed a t aw h i c ho n l yh a v et h e n o m i n a la t t r i b u t e s i fw eo n l yd e a lw i t ho n ek i n do fa t t r i b u t e ，d a t am e s s a g em u s t1 0 s ei n c o n d i t i o n so fm i xa t t r i b u t e s ，e f f e c tt ot h eq u a l i t yo fd a t am i n i n g h o wt oc a r r yo nt h ec l u s t e r o fm i xa t t r i b u t e si ss t i l lac h a l l e n g i n gd o m a i na tp r e s e n t 肠em a i nr e s e a r c hw o r ki nt h i sa r t i c l ei n c l u d ef o l l o w i n gs e v e r a la s p e c t s ： 1 f i r s ti n t r o d u c e dt h ek p r o t o t y p e sa l g o r i t h m ，a n dt h e np r o p o s e d2k i n d si m p r o v e m e n t m e a n sa i ma tt h ek - p r o t o t y p e s ，t h ef i r s tk i n di san e wa l g o r i t h mn a m e dc v a d ( c a t e g o r i c a l v a l u ea t t r i b u t e sd e c o m p o s e ) ，w h i c hb a s e do n k p r o t o t y p e sa l g o r i t h ma n dt h ef u z z y k - p r o t o t y p e sa l g o r i t h m ，t h i sm e t h o dc a no v e r c o m et h ei n s u f f i c i e n c yo fo r i g i n a lm e t h o d ，a n d c a nw o r ko u tb e t t e rc l u s t e rr e s u l t t h es e c o n dk i n di sak i n do fi m p r o v e m e n ta l g o r i t h mb a s e d o nc h o o s e si n i t i a lp o i n t sb yg r o u p ，w h i c hb a s e do nk - p r o t o t y p e sa l g o r i t h m ，a n dm a d et h e f u r t h e ri m p r o v e m e n tt oc h o o s eg r o u p st h r o u g ht h eg e n e t i ca l g o r i t h m 2 p r o p o s e dak i n do fm i xa t t r i b u t e sc l u s t e ra l g o r i t h mb a s e do nt h eb i r c ha l g o r i t h m ； t h ea l g o r i t h mp r o p o s e di nt h ea r t i c l eh a sg o o dp e r f o r m a n c et h a ti n d i c a t e di nt h eu c id a t as e t e x p e r i m e n t 3 p r o p o s e dak i n do fm i xa t t r i b u t e sc l u s t e ra l g o r i t h mb a s e do nt h ei m p r o v e m e n t d b s c a na l g o r i t h m ，g a v et h ec o r r e l a t i o nd e s c r i p t i o n ，a n dp o i n t e do u tt h em e r i to ft h i s a l g o r i t h m 4 p r o p o s e dak i n do fm i xa t t r i b u t e sc l u s t e ra l g o r i t h mb a s e do nt h ec l u s t e rf u s i o n ( c l u s t e re n s e m b l e b a s e dm i x e da t t r i b u t ec l u s t e r , c e m c ) 。i n t r o d u c et h ec l u s t e rf u s i o n m e t h o ds y s t e mi n t ot h em i xa t t r i b u t e sd a t ac l u s t e rp r o b l e m ，p r o m o t e dt h ec l u s t e rf u s i o n m e t h o d ，c a r r i e do nt h em i xa t t r i b u t e sd a t ac l u s t e rp r o b l e mw i t ht h ec l u s t e rf u s i o nt h e o r y , e s t a b l i s h e dt h ea l g o r i t h mf r a m e ，p r o p o s e dt h eo b j e c t i v ef u n c t i o na n dt h ea l g o r i t h m ，t e s t e dt h e a l g o r i t h mv a l i d i t yi nt h ea c t u a ld a t a k e y w o r d s ：d a t am i n i n g ；c l u s t e r ；m i xa t t r i b u t e ；b i r c ha l g o r i t h m ；d b s c a n a l g o r i t h m ；d a t af u s i o n i i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名孝缝日期：少d 年占月多e l 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密冈。 ( 请在以上相应方框内打“ ) 作者签名： 导师签名： 日期：纱p 年石月多e t 日期：圳口年( 月多日 炎 歹店委 1 1 研究的背景和意义 第一章绪论 近年来，数据库技术迅速发展，数据库管理系统得到广泛应用，人们积累的数据越 来越多。这些激增的数据背后隐藏着许多重要的信息，人们有必要对数据进行分析，就 能挖掘出其中的关系和规则。数据挖掘技术在这种背景下应运而生，目前数据库和信息 决策领域中，它是最前沿的研究方向之一。数据库知识发现技术和数据挖掘技术在迅速 发展，数据聚类技术是数据挖掘的重要技术之一，广泛应用于诸如市场分析、金融投资、 医疗卫生等实际应用领域。将物理或抽象对象的集合分组成为由类似的对象组成的多个 类的过程被称为聚类。当前主要的聚类算法有：( 1 ) 基于划分的方法，如k 平均算法 和k 中心点算法嘲；( 2 ) 基于层次的方法，如c u r e 3 1 和b i r c h 州n 0 1 ( 3 ) 基于密度的方法， 如d b s c a n n l l n 2 1 和o p t i c s 1 3 1 n 引；( 4 ) 基于网格的方法，如s t i n g n5 1 、c l i q u e 1 6 1 和 w a v e c l u s t e r n7 1 ；( 5 ) 基于模型的方法，如c o b w e b n 邮等。目前已有的数据聚类算法大部 分只能处理只具有连续属性的数据，有少量的算法只能处理只具有标称属性的数据。所 谓连续属性是指属性的取值是连续数值，像长度、重量；所谓标称属性是指属性的取值 是有限的状态，像颜色、职业。在现实世界中，大多数据流同时具有连续属性和标称属 性，如网络数据包。假如只处理一类属性，在混合属性条件下必然损失数据信息，影响 数据挖掘的质量。如何进行这种混合属性数据的聚类，目前还是一个充满着挑战性的领 域。z h u a n g 提出的k - m o d e s 算法n 町和k - p r o t o t y p e s 啪r 2 明算法推广了k - m e a n s 方法，使 之可以对类属性和混合型属性的对象集进行聚类。但用以上方法对类属性和混合型属性 的对象集进行聚类时，存在结果不稳定、随机性大、准确性不够高等缺点。尤其是初始 点对最后的聚类结果存在着很大的影响，如果初始点的选择不好聚类结果将会变得很难 接受。z y u 提出了一种混合属性聚类融合算法r 衄1 ，将聚类融合的方法体系引入混合属 性数据聚类问题中，推广了聚类融合方法，将混合属性数据聚类问题用聚类融合理论进 行求解，在聚类的稳定性，精确性，运行速度方面取得了一定的效果。 目前越来越多数据都是以混合属性方式出现，但是目前总体来说对混合属性聚类的 算法的研究也充分，如何进一步提高聚类稳定性，精确程度，运行速度值得我们深入去 研究。 1 2 数据挖掘概述 1 2 1 数据挖掘的发展背景 近年来，计算机性能提高、成本下降、数据管理技术成功运用，各部门内部的信息 化程度也越来越高，造成了大量数据的积累。“数据丰富，知识贫乏”。怎样从这些海量 数据中发现有用的信息，怎么理解已有的历史数据并用它对未来的行为进行预测，怎样 快速、准确地获取有价值的网络服务和网络信息，为用户提供一些未知的、重要的信息 和知识，把客观存在的一些数据变为人们所能认识的知识，我们用这些数据指导企业的 决策和政府的决策，获取更大的社会效益和经济效益，这些都迫使我们去寻找更有效、 更新的一些分析数据的手段，有效挖掘各种“数据矿藏”进行以发挥它们的应用潜能。 2 0 世纪8 0 年代后期到现在，高级数据分析数据挖掘( d m ) 和数据库中的知识发现 ( 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 ) 。简单地讲，k d d 表示从 抽象低层客观的数据到高层可识别的知识的整个过程。通过数据库中的知识发现，人们 能从数据库的数据及相关数据集中抽象出有用的知识、数据的高层及规律性的信息。本 质上，数据挖掘( d m ) 与数据库中的知识发现( k d d ) 是不同的，但也有人把k d d 和d m 混 为一谈，其实d m 不过是k d d 其中的一个步骤。 数据挖掘是一个交叉的学科，包括统计学、机器学习、数据库技术、可视化和信息 科学等。数据挖掘中采用的主要技术是归纳逻辑、遗传算法、粗糙集理论、模糊理论、 神经网络等。我们不仅可以通过数据挖掘从数据集中发现有趣的信息规律和知识、，还 可以从不同的角度观察、浏览、理解，我们将所发现的知识用于过程控制、查询处理、 信息管理、决策等等。因此，在当今信息技术学科最前沿的领域占有重要地位。 数据挖掘按照功能可分为：( 1 ) 演变分析；( 2 ) 聚类；( 3 ) 孤立点分析；( 4 ) 分类； ( 5 ) 关联规则。 2 1 2 2 数据挖掘的研究现状 知识发现、数据挖掘是近年比较活跃的研究领域之一。数据库的知识发现( k d d ) 一 词最早在1 9 8 9 年第十一届国际联合人工智能学术会议( i j c a i ) 提出。此后五年举行了四 次k d d 的国际研讨会。并在此基础上，第一届知识发现与数据挖掘的国际学术会议于 1 9 9 5 年召开，9 7 年k l u w e r s 出版社出版了专题杂志 d a t am i n i n ga n dk n o w l e d g e d i s c o v e r y ，次年建立了新的学术组织a c m s i g k d d ，也就是a c m 下的数据库中的知识发 现专业组( s p e c i a li n t e r e s t e dg r o u p o nk 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 ) 。第五届 知识发现与数据挖掘国际学术会议便是由a c m s i g k d d ( k d d 9 9 ) 召开的。 此外，还有一些如“a c m s i g m o d 数据管理国际会议( s i g m o d ) ”、“知识发现与数 据挖掘太平洋亚洲会议( p a k d d ) 、“数据库中的知识发现原理与实践欧洲会议( p k d d ) 、 “数据仓库与知识发现国际会议( d a w a k ) ”等各种数据挖掘会议。近几年数据挖掘的研 究重点从实验室原型走向商品化阶段，从算法研究向具体应用过渡。目前，国际上从事 数据挖掘产品研发的软件公司已从1 9 8 9 年的几个猛增为上千家，每年都推出若干软件 产品。 对于数据挖掘的研究，国内与国外相比起步较晚，直到2 0 世纪术才开始，初步形 成了数据挖掘的基本框架。计算机学报、计算机研究与发展、软件学报、人工 智能与模式识别等杂志才陆续出现了一些研究成果。随着数据挖掘的迅速发展，许多 学术会议如数据库学术会议、机器学习会议等也都开始把知识发现与数据挖掘列为重要 的研究领域，国际自然科学基金于9 3 年首次支持该领域的项目，目前，数据挖掘的研 究的研究重点已经开始转向系统应用方向，同时还注重各种技术和方法的集成以及交叉 学科问的相互融合与渗透。 1 3 聚类概述 1 3 1 聚类的发展背景 将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚 类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他 簇中的对象相异。 在自然界与人类生活中存在着许许多多分类问题，并有“物以类聚，人以群分 一 说，在数据挖掘中定义的类就是指相似元素的集合。聚类分析最早源于分类学，是( 样 品或指标等) 分类问题中统计分析的一种研究方法，也称群分析。与分类不容的是，聚 类是一种无监督学习方法，即划分的类是未知的。以往的分类主要是依靠经验和专业知 识来实现的，几乎没有任何数学工具利用于定量的分类中。随着科学技术的高速发展， 人类对分类要求的不断提高，通过将数学工具才开始引入到分类学从而形成了数值分类 学，之后多元分析技术的发展，并成功应用于数值分类学形成也就形成了今天的聚类分 析。聚类分析种类繁多，有聚类预报法、系统聚类法、图论聚类法、模糊聚类法、动态 聚类法、有序样品聚类法等等。 聚类已经广泛应用到各个领域，在商务领域中，聚类能协助市场分析人员从客户信 息数据中发现不同的客户群，并可用购买模式描述客户群的特征；在生物学领域，聚类 分析用于动植物以及基因的分类，从而进一步认识种群内在结构；在汽车保险领域，聚 类对保险持有者分类；另外，聚类还用于w e b 文档分类，在地球观测数据库中，确定相 似地区并根据房子的地理位置、类型和价值对城区房屋分类有一定作用。 1 3 2 聚类的分类 传统的聚类分析可大致分为以下几类： ( 1 ) 基于划分的方法( p a r t i t i o n i n gm e t h o d s ) ：给定一个聚类，其包含n 个元组， 采用分裂法构造出k 个类，其中k n ，每一个类表示一个聚类，且每个类都满足以下条 件：每个数据样本属于且唯一属于某一个类；每个类中至少包含一个数据样本( 注 意：在某些模糊聚类中这个条件可以放宽) 。假设给定k 值，基于划分的聚类算法随机 对元组进行初始划分，然后反复迭代改变元组的划分使每一次迭代之后的划分结果都要 比前一次好，好衡量的标准就是：同一聚类中的元组越近越好，而不同聚类之间的元组 越远越好。采用这一基本思想的主要算法有：k - m e a n s 算法、k - m e d o i d s 算法、c l a r a n s 算法。 ( 2 ) 基于层次的方法( h i e r a r c h i c a lm e t h o d s ) ：对特定的数据集，该方法进行反 复的层次分解，直到满足某种约定条件。主要有两种形式：一是“自底向上”。自底向 上方法初始化时每一个数据表示一个单独的聚类，迭代时把相互邻近的聚类并成一个聚 类，直到所有的元组合并到一个分组或满足某个条件为止；二是“自顶向下 。基于划 分的方法的主要算法有：c u r e 、b i r c h 、c h a m e l e o n 等。 ( 3 ) 基于网格的方法( g r i d - b a s e dm e t h o d s ) ：首先在数据空间中划分成为若干个 单元( c e l l ) 的网格结构，所有的计算在基于网格的方法中都是以单元为基本单位，这 4 样做更快的处理，且使算法计算与数据库样本与个数无关，而只与换分数据空间的单元 个数相关。主要算法有：c l i q u e 算法、s t i ng 算法、w a v e c l u s t e r 算法。 ( 4 ) 基于密度的方法( d e n s i t y - b a s e dm e t h o d s ) ：与其它方法相比，基于密度的方 法的根本不同就是：该方法不是基于距离的，而是以密度为度量单位。从而能够有效地 避免基于距离方法只能发现“类圆形聚类的缺陷。在该算法中，一旦某一区域的样本 密度大于某一设定的阀值，就将其合并到与之相近的聚类中。该方法的主要代表算法有： o p t i c s 算法、d b s c a n 算法、d e n c l u e 算法等。 ( 5 ) 基于模型的方法( m o d e l b a s e dm e t h o d s ) ：该方法对给定的每个聚类对应假定一 个模型，然后寻找满足这个模型的数据集。方法中涉及的模型可以是样本在数据空间的 密度分布函数等等。该方法的一个潜在前提就是：数据集是一系列的概率分布决定的。 传统的研究方案有：统计方案和人工神经网络方案。 此外，聚类算法还有：传递闭包，布尔矩阵脚1 ，直接聚类口等等。 1 4 混合属性聚类概述 1 4 1 混合属性聚类的发展背景 目前已有的数据聚类算法大部分受到只具有连续属性的数据的局限，另外有少量的 算法受到处理只具有标称属性的数据的局限，其中所说的连续属性是指属性的取值为连 续数值，如重量、长度；所谓的标称属性是指属性的取值是有限的状态，如职业、颜色。 现实世界中的大多数据流同时具有两种属性，如网络数据包等。如果只处理一类属性， 在混合属性条件下必然损失数据信息，影响数据挖掘的质量。如何进行这种混合属性数 据的聚类，目前还是一个充满着挑战性的领域。然而对于单一类型的属性目前很多学者 已经做了大量的研究，有着很多现存的，性能优良的聚类算法以及很多理论基础，这让 我们必然形成这样一个思路研究这些现存的处理方法并将其推广到混合属性聚类，然后 如何推广现存的处理方法到混合属性聚类，应当注意些什么问题，性能如何就成了在这 一领域研究的众多学者的主要研究的热点问题。 1 4 2 混合属性聚类的研究现状 聚类的意义在于将聚类数据，以便找到感兴趣的类别。例如客户关系管理中，银行或 证券公司根据客户的个人属性、资产情况、交易行为等，对客户进行风险评估和客户价 值分析。绝大部分现实数据是海量数据集，并且数据属性包括数值属性和类属性两类。 5 现有的算法几乎都不能有效处理这些数据集。最早且最简单的聚类方法由m a c q u e e n 提 出，但它只能聚类数值属性的对象集，不能聚类类属性和混合型属性的数据集。类属性的 值域是无序的，所以将类属性数据转化为数值属性数据的方法并不总能得到有效的结 果。z h u a n g 推广了k - m e a n s 方法，提出的k - m o d e s 算法和k - p r o t o t y p e s 算法，使之可 以聚类类属性和混合型属性的对象集。不过用以上方法聚类类属性和混合型属性的对象 集时，存在结果不稳定、随机性大、准确性不够高等缺点。z y u 提出了一种混合属性聚 类融合算法，将聚类融合的方法体系引入混合属性数据聚类问题中，推广了聚类融合方 法，将混合属性数据聚类问题用聚类融合理论进行求解，在聚类的稳定性，精确性，运 行速度方面取得了一定的效果。 1 4 3 混合属性数据聚类存在的问题 ( 1 ) 算法执行效率的问题 由于混合属性的数据往往属性维度都比较高，很容易遇到“维度灾难”的问题，导 致处理海量数据时算法的效率根本不能接受，如何在保证聚类准确程度的情况下根据混 合属性这一特点提高算法的执行效率就是一个值得研究的具体问题。 ( 2 ) 任意形状的簇问题 对于单一属性的聚类有些算法f l 口b i r c h 算法，数据分布形态对聚类结果存在很大的影 响，同样在将这些原来用于处理单一属性的聚类的这些算法推广到混合属性同样会遇到 这个问题，如何处理好这个问题，保证聚类结果的稳定性也是一个值得研究的具体问题。 ( 3 ) 初始点的问题 对于单一属性的聚类有些算法f l n k m e a n 算法，初始的数据点对最后的聚类结果的准 确程度有着很大的影响，同样在将这些原来用于处理单一属性的聚类的这些算法推广到 混合属性同样会遇到这个问题，如何处理好这个问题，如何去选择能得到更好结果的初 始点也是一个值得研究的问题。 ( 4 ) 聚类准确程度 对单一属性的聚类算法在推广到混合属性时聚类准确程度是我们时刻要考察的一个 重要指标，但是对于不同的数据情况可能有着不同准确程度，我们无法一概而论这种算 法一定优于那种算法，但我们仍然需要对这一指标进行考察，得出一些有意义的结论。 6 1 5 本文的工作 ( 1 )介绍tk - p r o t o t y p e s 算法，然后提出了2 种针对k p r o t o t y p e s 的改进方法， 第一种是在k p r o t o t y p e s 算法和模糊k - p r o t o t y p e s 算法的基础上设计了一种新的算法 类属性分解法，这种方法能够克服原有方法的不足，并可以产生较好的聚类结果。 第二种是在k p r o t o t y p e s 算法基础上设计的一种基于分组选择初始点的改进算法，并且 通过遗传算法对分组做进一步的改进。 ( 2 ) 基于b i r c h 的混合属性数据聚类的研究，对含有连续属性和标称属性的混合 属性数据聚类一个重要的课题。b i r c h 有着较高的处理效率和较小的存储规模，适合处 理大规模的数据。而混合属性聚类由于属性多，计算往往十分复杂，如何将b i r c h 算法 应用于混合属性聚类，以解决时间，空间效率问题。 ( 3 )基于d b s c a n 的混合属性数据聚类的研究，基于b i r c h 的混合属性数据聚类有 一个不可回避的问题：聚类结果呈球状分布，这是由于b i r c h 算法本身不具备较好的伸 缩性导致，为了实现对任意形状的样本集聚类，提出一种基于d b s c a n 的混合属性数据聚 类。 ( 4 ) 基于混合属性数据融合的研究，混合属性数据融合是从数据融合的角度来处 理混合属性聚类问题，不同于其他单一属性数据聚类方法，不再从数据与数据间的距离 来考虑聚类问题，而是用若干独立的聚类器分另q 对原始数据进行聚类，然后对这些结果 进行组合，最终获得对原始数据的聚类结果，这种方法可以进行分布计算，在一些其他 方面也有着相当的优势，本文对这种方法做了详细的讨论。 1 6 本文的组织 第一章阐述了本文的研究意义和背景，介绍了数据挖掘和聚类及混合属性聚类的国 内外研究现状及研究中存在的问题，最后对本文的主要研究内容进行了介绍。 第二章介绍t k - p r o t o t y p e s 算法，然后提出了2 种针对k - p r o t o t y p e s 的改进办法， 第一种是在k - p r o t o t y p e s 算法和模糊k - p r o t o t y p e s 算法的基础上提出一种新的算法一 类属性分解法，这种方法能够克服原有方法的不足，并可以产生较好的聚类结果。第二 种是在k - p r o t o t y p e s 算法基础上的一种基于分组选择初始点的改进算法，并且通过遗传 算法对分组做进一步的改进。 第三章先介绍了b r i c h 算法，然后根据b r i c h 算法的特点提出了一种基于b i r c h 算 7 法的混合属性的聚类算法；在u c i 数据集上的实验表明，文中提出的算法具有较好的性 能。 第四章先介绍了d b s c a n 算法，然后根据d b s c a n 算法的特点给出了一种基于改进的 d b s c a n 算法的混合属性的聚类算法，并指出了这种算法的优点，给出了相关描述。 第五章给出出了一种基于聚类融合的混合属性聚类算法( c e m c ) ，提出了目标函数 和算法，建立了算法框架，推广了聚类融合方法，聚类融合的方法体系引入混合属性数 据聚类问题中，通过混合属性数据聚类问题用聚类融合理论进行求解，最后我们在实际 数据中检验了算法的有效性。 第六章总结了本文的研究工作，阐明其难点和创新点，并提出进一步研究的方向。 8 第二章k - p r o t o t y p e s 算法及其改进方法 2 1 k - p r o t o t y p e s 算法介绍 2 1 1 相异度度量 设数据对象x 的分类属性为m ( x 。，x ：x 。) 维，同时数据对象y 的分类属性为 m ( x 。，x ：x 。) 维，假定以相同的几率出现属性中的属性值，我们把x 、y 之间的相异度定 义为对象x 、y 之间分类属性值不相等的属性的数量，表示为d ( x ，y ) 。，则相异度定义如 ( 2 1 ) 属性j 包含的属性值x j ，y j 的数量为n x j ，n 撕，当x j y j 时，6 ( x j ，y j ) = 1 。由定义2 1 可 知，在对象问如果相异度越高，则意味着不相等的属性值个数越多，对象越不相似。 2 1 2 成本函数 我们通过一个叫成本函数的来表示对象间的近似程度。这个成本函数是的计算策略 以k m e a n s 的成本函数的计算策略为基础，为了能够计算含有数值型与离散型混合属性 数据我们改进了成本函数。设存在包含1 1 个对象的一个数据集x = x 。，x ：，x 。 ，且有一 个m 维的对象x ；= i x ”x ，x 妇】，即包含m 了个属性值， k 为正整数。用较广泛的定义 计算成本函数表示如下： 定义2 2 ： kn e = y 日d ( x i ，q j ) ( 2 2 ) 其中相似度我们用d 来表示表示度量值，g - 【g g ，：，9 1 m 】表示类i 的初始型，划分 矩阵e 。中的一个元素我们用表示，y 有以下的特点 9 紫 ：m 州 、j 色 丫 ：义 k 下定 文 k ( 1 ) o - y u 1 ；均= 1 j = l 是硬划分，还是模糊划分我们用虼 0 ，1 ) 来判断。其中对象z 划分到i 类我们用= 1 表 示。硬划分作为本章的算法的主要考虑。定义2 2 的公式e = e y u d ( x j ，g ) 表示x 划分到 i = l 类i 的总成本。 如初始型q 与类i 中所有对象总的偏离量巨最小，即 1 击 q u 。i 乙y u x u 7 0 信1 其中代表类i 对象的数用乃= 。引入相仿的度量值来表示x 中的分类属性， 耽 l i e d ( 置，g ) = ( 一g ；) 2 + 7 万( 巧，巧) ( 2 3 ) ( 2 4 ) 式中万( x ；，圬) 使用用式2 1 ，x ；，q ：是类i 与对象i 数值属性值，而，g ；是类i 和对象i 初始型的分类属性值。我们表示数值型属性的数量用m ，、离散型属性的数量用m c 表示， 类i 的离散型属性权重用y 表示，对式2 4 进一步改进，得出了总的成本函数 n m r hm r 岛= 肌( 吻r g ：) 2 + 7 y u 万( ，圬) = 耳+ 耳 当y = o 时，k - p r o t o t y p e s 算法就退化成- j k m e a n 算法。 2 1 3k - p r o t o t y p e s 算法的不足 ( 2 5 ) k - m e a n s 的不足通过k - p r o t o t y p e s q b 的相异度测量法可以很好地弥补，这样就可以 合理处理分类数据，但该算法是随机选择确定初始点，在初始点选择上存在随机性，这 样做会致使聚类的最终结果离真实情况有差距，虽然说这样做简单且快速。为此，我们 给出一种改进分组选择初始点的算法是很有必要的。 i o 2 2 对k - p r o t o t y p e s 算法的改进及类属性分解算法 2 2 1 举例分析在原有方法的不足之处 为了分析以上算法在聚类对混合型属性和类属性集时的不足我们举一个例子来。假 如把一个数据集分成2 个类： ，用k - p r o t o t y p e s 聚类这一个这样的混合型属性的数据集合。 表2 1 混合型属性的对象集表 编号 次数进入渠道语义范畴 12 多层动物 23 多层动物 33 多层 动物 42 单层文字 52 单层文字 6 3单层文字 7 3 单层文字 83 单层文字 p，” 通过距离公式d ( x ，y ) = ( _ - y j ) 2 + y 8 ( x j ，y j ) 七旧 取7 = 4 ，成本函数：e = 丑，d ( x t , c 7 ) ，；lt = i ( 2 6 ) ( 2 7 ) 为了来完成聚类，我们通过寻找使成本函数达到最小的聚类方法，。经过计算， c l a s s l 1 ，2 ，3 ) 、c l a s s 2 4 ，5 ，6 ，7 ，8 ) 的成本函数值为1 8 6 7 ，小于之前的 c l a s s 2 4 ，5 ，6 ，7 ，8 ) 、c l a s s l 1 ，2 ，3 ) 的3 2 。但是，如果初始化的类别为c l a s s l 1 ，2 ，3 ) 、 c l a s s 2 4 ，5 ，6 ，7 ，8 ) ，那么我们可以计算出则初始型集为：z 1 2 ，单层，文字) ；z 2 3 ， 单层，文字) ，继续循环，直至明显的距离类l 较近时，2 、3 距离类2 比较近，循环终 止时就是当我们发现初始集不再改变时。这种结果显然我们不满意。这是因为传统方法 中，类属性“语义范畴 和“进入渠道中的属性值“动物和“单层 数量较少，在 没有初始好的情况下很容出现丢失属性值。如果初始分成c l a s s l l ，2 ，3 、 c l a s s 2 4 ，5 ，6 ，7 ，8 或c l a s s l 1 ，2 ，8 ) 、c l a s s 2 3 ，4 ，5 ，6 ，7 能出现正确的结果。为了使 得原算法不受对象集中对象排列顺序和初始化的影响，我们需要改进原有算法使得聚类 结果稳定合理， 2 2 2 新方法 把有n 种不同值的类属性视为是一个n 维的属性，例如“语义范畴有“文字”、“动 物”2 个维，将每个类属性看成一个n 维的属性，“进入渠道”看成有“单层”、“多层 2 个维。 回到刚才的例子，如果初始化为c l a s s 2 4 ，5 ，6 ，7 ，8 、c l a s s l 1 ，2 ，3 ，那么第一次 循环计算出的初始型为： z 1 2 ， 1 3 ( 多层) ，2 3 ( 单层) ) ， 1 3 ( 动物) ，2 3 ( 文字) ) ； z 2 3 ， 2 5 ( 多层) ，3 5 ( 单层) ) ， 2 5 ( 动物) ，3 5 ( 文字) ) ) ； 使用曼哈坦距离口2 1 计算类距离，以下给出一例，将初始点l 改写为 2 ， 1 ( 多层) ， 0 ( 单层) ) ， 1 ( 动物) ，0 ( 文字) ) 。 取厂24 ，此时，初始点z l 对于1 的距离为： d ( 1 ，z 1 ) 2 ( 2 - 2 ) 2 + r 搴 f 1 1 3 + 0 - 2 3 1 + 1 1 3 i + 1 0 - 2 3 1 1 = p 8 3 = 1 0 6 6 7 初始点z 2 对于1 的距离为： d ( 1 ，z 2 ) = ( 2 3 ) 2 + r 乖 【| l 一2 5 1 + 1 0 3 5 1 + 1 2 5 + 0 3 5 i = l + r 卡1 2 5 = 1 0 6 d ( 1 ，z 1 ) 所以，将初始点1 归入c 2 中，虽然以“文字 、“单层”在初始型z 2 ，z 1 中的类 属性中居多，但该方法并不是除去出现少量出现的属性值而简单的取出现最多的属性 值，它可以保留较少出现的“多层”、“动物”的属性值。 继续循环，产生合理的类别为：c l a s s l 1 ，2 ，3 ) 、c l a s s 2 4 ，5 ，6 ，7 ，8 。 上述方法就是类属性分解法，此方法它适用于混和属性数据集，比模糊 k - p r o t o t y p e s 法和k - p r o t o t y p e s 有更高的可靠性和稳定性， 2 2 3 类属性分解算法 对应于模糊k - p r o t o t y p e s 算法和k - p r o t o t y p e s 算法口3 r 啪3 ，类属性分解法可详细分 为：模糊k - p r o t o t y p e s 类属性分解法和k - p r o t o t y p e s 类属性分解法。我们会分别给出 k - p r o t o t y p e s 类属性分解法和模糊k - p r o t o t y p e s 类属性分解法的例子。 在加入类属性分解算法后而改进了k - p r o t o t y p e s 算法和模糊k - p r o t o t y p e s 算法， 基本流程是相同。 k - p r o t o t y p e s 中使用类属性分解法后如下描述： 1 2 s t e p l 对x 中的类属性进行区别规划； s t e p 2 初始化数据集x ，拟定k 为聚类数量，随机分为k 类，转到s t e p 4 ；或者任意 去k 个初始点作为仞始的p r o t o t y p e s ，转到s t e p l 。 s t e p 3 为了将其分入那个类中，需要计算x 中的每个初始点离最近的类是哪个，更 新类的p r o t o t y p e s ； s t e p 4 重新计算每个初始点与当前p r o t o t y p e s 的距离。如果当前的p r o t o t y p e s 不 是距离初始点最近的p r o t o t y p e s ，重新划分该初始点到最近的p r o t o t y p e s 的类，更新 类的初始型。 s t e p 5s t e p 4 不断循环执行，直到分类不再做任何改变。 2 2 4 模糊k - p r o t o t y p e s 类属性分解法 算法描述如下： s t e p l 对x 中的类属性进行区别规划； s t e p 2 初始化数据集x ，确定聚类数量k 以及循环控制常量占，任选k 个初始点作 为初始p r o t o t y p e s ，或者随机分为k 类； s t e p 3 计算各个初始点对于每个p r o t o t y p e s 的归属度，使成本函数f ( 人，z “) 取 得最小。设i = l ； s t e p 4 计算各个p r o t o t y p e sz m ，使成本函数f ( a ，z “) 取得最小。如果 i f ( 人“，z 。+ 1 ) 一f ( 人。，z 。) l 占则循环结束； s t e p 5 对于各个初始点计算每个的p r o t o t y p e s 的归属度人”n ，让成本函数达到最 小，如果i f ( 人“n ，z 件1 ) 一f ( 人n ，z 件1 ) l s 则结束循环；否则( 人，z ) ：( 人( 川) ，z ( m ) 。将 i 增加1 ，转到步骤s t e p 4 。 2 。2 5 实例分析 使用一个有1 4 个对象的数据集，使用两种方法将此数据集聚类分别为聚类模糊 k - p r o t o t y p e s 法和模糊k - p r o t o t y p e s 类属性分解法，他们参数相同，这两种方法的稳 定性和可靠性区别如下： 数据集为表2 2 所示： 表2 21 4 个对象的数据集表 编号次数渠道语义范畴 12 单层食品 23 多层食品 33 多层植物 42 单层植物 55 多层文字 63单层食品 71 单层植物 8 5单层文字 9 2 多层植物 1 0 4单层文字 1 l 5 单层 文字 1 2 5 单层艺术 1 35 单层食品 1 45 单层文字 聚类数量：3 模糊系数口= 2 平衡参数厂2 4 初始化1 ：c 1 1 ，2 ，3 ，4 ；c 2 5 ，6 ，7 ，8 ，9 ) ；c 3 1 0 ，1 1 ，1 2 ，1 3 ，1 4 ) 初始化2 ：c 1 1 ，4 ，7 ，1 0 ，1 3 ) ；c 2 2 ，5 ，8 ，1 1 ，1 4 ) ；c