（计算机应用技术专业论文）聚类融合算法及其在移动通信企业的应用.pdf

硕十学位论文摘要 摘要 聚类，作为数据挖掘技术研究的热点之一，受到越来越多的关注。 聚类的主要任务就是把数据集划分成有意义或有用的组。随着数据库 技术的飞速发展，各行各业中的信息数据也急剧地增长，而且数据的 类型也由单一的数值型、文本型逐渐转变成混合型，这就对聚类分析 技术提出了新的要求。从已有的文献来看，能有效处理混合型数据的 算法相对较少。基于这一现状，本文重点研究了面向混合型数据的聚 类融合算法，同时对其在移动通信行业中的应用进行了探讨。 本文对已有的算法进行了研究比较之后，提出了一种基于图的聚 类融合算法坷e 算法。该算法选取能处理混合型数据的 k - p r o t o t y p e s 算法和c b l 算法作为聚类成员进行融合，以图为基础， 利用图中顶点和边的权值设置来确定数据点之间的联系，通过数据点 之间共享最近邻数来确定融合函数。通过公共数据集上的实验，结果 表明该算法不仅能很好地处理混合型属性数据，而且得到比单一算法 更为优越的结果。此外，本文还分析了4 种聚类成员差异性度量与融 合准确度之间的关系，实验结果表明成员大小为1 5 到2 0 左右，待聚 类数据集有均匀簇分布时，各种差异性度量与融合方法性能间的相关 程度最高。 本文最后将此聚类融合算法成功应用于移动通信企业客户细分。 通过对用户资料、通话行为、服务行为等相关的属性进行数据挖掘， 分析了各用户群的通话行为特征与服务类型特征以及各用户群与收 益之间的关系，实验结果证实了该聚类算法的有效性。 关键字：数据挖掘，聚类融合，差异性度量，共享最近邻，客户细分 a bs t r a c t c l u s t e r i n g ，硒o n eo ft h eh o tp o i n t so fd a t am i n i n gr e s e a r c h ， b e c o m e sa ni n c r e a s i n g l yh o tt o p i c i t sm a j o rt a s ki st h ep r o c e s so f g r o u p i n gt h ed a t ai n t oc l a s s e so rc l u s t e r ss ot h a tt h eg r o u p sa r ev a l u a b l e i np a c ew i t hd e v e l o p m e n to fd a t a b a s et e c h n o l o g y , i n f o r m a t i o nd a t af r o m v a r i o u sw a l k so fl i f ei n c r e a s er a p i d l y m o r e o v e r ，t h ed a t at y p e sc h a n g e f r o mp u r en u m e r i c a lo rn o m i n a lt om i x e d ，t h a tc a u s em u c hd i f f i c u l t yf o r c l u s t e ra n a l y s i s m o s ta l g o r i t h m sc a nw o r kw e l lw h e nt h ed a t as h o u l db e p r o c e s s e di ss i n g l et y p e ，b u tt h ep e r f o r m a n c ea r ev e r yl o wi ft h ed a t ai s m i x e dt y p e i nt h i sp a p e r , w ep u te m p h a s i so nc l u s t e r i n gm e t h o d sf o r m i x e dd a t a a f t e rs t u d i n gt h ee x s i t i n gc l u s t e r t i n ga l g o r i t h m s ，w ep r o p o s ea c l u s t e r i n ge n s e m b l et h a tb a s e do ng r a p h i tg e t sc l u s t e r i n gm e m b e r sb y c h o o s i n gk - p r o t o t y p e sa l g o r i t h ma n dc b la l g o r i t h mt h a tc a nd e a lw i t h m i x e dd a t a t h ea l g o r i t h mb a s e do ng r a p hc h a n g e st h eo b j e c t sa t t r i b u t e s t og r a p hb a s e do nt h ec o n c e p t i o no fe d g e sa n dv e r t i c e si ng r a p h ，a n d g e n e r a t e sae n s e m b l ef u n c t i o n b a s e do nap r o p o s e dw e i g h t e ds h a r e d n e a r e s tn e i g h b o r sg r a p h e x p e r i m e n t ss h o wt h a tt h en e we n s e m b l e a l g o r i t h m i sn o to n l yd e a lw i t hm i x e dd a t ab e r e r b u ta l s om o r e e f f i c i e n t l yt h a nt h es i n g l ea l g o r i t h m a tt h es a m et i m e ，t h er e l a t i o n s h i p s b e t w e e nt h ef o u rm e a s u r e so fd i v e r s i t ya n dt h ea c c u r a c yo ft h ec l u s t e r i n g e n s e m b l e sa r ep r o p o s e d e x p e r i m e n t ss h o ww h e nc o n s t r u c t i n ge n s e m b l e s w i t hm o d e r a t ee n s e m b l es i z eb ys u i t a b l ec l u s t e r i n ga l g o r i t h m sf o rad a t a s e tw i t hu n i f o r mc l u s t e rd i s t r i b u t i o n ，t h ec o e l a t i o nc o e f f i c i e n t sb e t w e e n t h ed i v e r s i t ym e a s u r e sa n de n s e m b l ep e r f o r m a n c ea r er e l a t i v e l yh i g h s u c c e s s f u l l ya p p l y i n gt h ec o m b i n e da l g o r i t h mt os e g m e n tt e l e c o m c u s t o m e r s a n a l y z i n g t h ed a t ao ft h ec u s t o m e ri n f o r m a t i o n ， c o m m u n i c a t i o na c t i o n ，s e r v i c ea c t i o n ，e t c ，a n dt h er e l a t i o n s h i pb e t w e e n c o m m u n i c a t i o na c t i o nf e a t u r e so fc u s t o m e rs e g m e n t sa n ds e r v i c et y p e s ， a n db e t w e e nc u s t o m e rs e g m e n t sa n dp r o f i t ，t h ee x p e r i m e n tr e s u l tp r o v e s t h a tt h ec l u s t e r i n ge n s e m b l ea l g o r i t h mi se 珩c i e n t k e yw o r d s ：d a t am i n i n g ，c l u s t e r i n ge n s e m b l e ，d i v e r s i t ym e a s u r e ， s h a r e dn e a r e s tn e i g h b o r s ，c u s t o m e rs e g m e n t a t i o n l l 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：要隘 日期：上型t 年月丝日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：翌：隆导师签名邀 日期：骂一年月笪日 硕十学位论文 第一章绪论 第一章绪论 本章在介绍数据挖掘产生和发展的基础上，引出数据挖掘的定义，揭示其研 究意义，并在方法论、数据挖掘技术的应用以及未来的研究方向等方面进行综述， 随后简略介绍聚类分析的研究状况，描述其研究意义、优势和未来研究方向，并 着重分析了在处理混合型数据方面的一些研究进展。本章最后介绍本文的主要研 究内容和本文的结构。 1 1 数据挖掘研究综述 1 1 1 数据挖掘的研究背景和方法论 随着计算机硬件和软件的飞速发展，尤其是数据库技术与应用的同益普及， 人们面临着快速扩张的数据海洋，如何有效利用这一丰富数据海洋的宝藏为人类 服务，业已成为广大信息技术工作者的所重点关注的焦点之一。与同趋成熟的数 据管理技术与软件工具相比，人们所依赖的数据分析工具功能，却无法有效地为 决策者提供其决策支持所需要的相关知识，从而形成了一种独特的现象“丰富的 数据，贫乏的知识 。为有效解决这一问题，自二十世纪8 0 年代开始，数据挖掘 技术逐步发展起来，数据挖掘技术的迅速发展，得益于目前全世界所拥有的巨大 数据资源以及对将这些数据资源转换为信息和知识资源的巨大需求，对信息和知 识的需求来自各行各业，从商业管理、生产控制、市场分析到工程设计、科学探 索等。数据挖掘可以视为是数据管理与分析技术的自然进化产物【lj ，如图1 1 所 示。 自六十年代开始，数据库及信息技术就逐步从基本的文件处理系统发展为更 复杂功能更强大的数据库系统；七十年代的数据库系统的研究与发展，最终导致 了关系数据库系统、数据建模工具、索引与数据组织技术的迅速发展，这时用户 获得了更方便灵活的数据存取语言和界面；此外在线事务处理( o l t p ：o n l i n e t r a n s a c t i o np r o c e s s i n g ) 手段的出现也极大地推动了关系数据库技术的应用普及， 尤其是在大数据量存储、检索和管理的实际应用领域。 自八十年代中期丌始，关系数据库技术被普遍采用，新一轮研究与开发新型 与强大的数据库系统悄然兴起，并提出了许多先进的数据模型：扩展关系模型、 面向对象模型、演绎模型等；以及应用数据库系统：空间数据库、时序数据库、 多媒体数据库等；日前异构数据库系统和基于互联网的全球信息系统也已开始出 现并在信息工业中开始扮演重要角色。 被收集并存储在众多数据库中且正在快速增长的庞大数据，已远远超过人类 的处理和分析理解能力( 在不借助功能强大的工具情况下) ，这样存储在数据库 硕+ 学位论文第一章绪论 中的数据就成为“数据坟墓 ，即这些数据极少被访问，结果许多重要的决策不 是基于这些基础数据而是依赖决策者的直觉而制定的，其中的原因很简单，这些 决策的制定者没有合适的工具帮助其从数据中抽取出所需的信息知识。而数据挖 掘工具可以帮助从大量数据中发现所存在的特定模式规律，从而可以为商业活 动、科学探索和医学研究等诸多领域提供所必需的信息知识。数据与信息知识之 间的巨大差距迫切需要系统地开发数据挖掘工具，来帮助实现将“数据坟墓 中 的数据转化为知识财富。 图1 1 数据挖掘进化过程示意描述 数据挖掘是在大型数据存储库中，自动地发现有用的信息过程。数据挖掘技 术用来探查大型数据库，发现先前未知的有用模式。数据挖掘还具有预测未来观 测结果的能力，例如，预测一位新的顾客是否会在一家百货公司消费1 0 0 美元以 上。 数据挖掘是数据库中知识发现【2 1 ( 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 2 所示。该过程包括一系列转换步骤，从数据的预处理到数据挖掘结果的后处 理。 输入数据可以以各种形式存储，并且可以驻留在集中的数据存储库中，或分 2 硕十学位论文 第一章绪论 布在多个站点上。数据预处理的目的是将未加工的输入数据转换成适合分析的形 式。数据预处理涉及的步骤包括融合来自多个数据源的数据，清洗数据以消除噪 声和重复的观测值，选择与当前数据挖掘任务相关的记录和特征。由于收集和存 储数据的方式可能有许多种，数据预处理可能是整个知识发现过程中最费力、最 耗时的步骤。 输入数据信息 图i 2 数据库中知识发现( k d d ) 过程 数据挖掘起源 随着数据挖掘研究逐步走向深入，来自不同学科的研究者汇集到一起，开始 着手开发可以处理不同数据类型的更有效的、可伸缩的工具。这些工作建立在研 究者先前使用的方法学和算法之上，在数据挖掘领域达到高潮。特别地，数据挖 掘利用了来自如下一些领域的思想：( 1 ) 来自统计学的抽样、估计和假设检验； ( 2 ) 人工智能、模式识别和机器学习的搜索算法、建模技术和学习理论。数据 挖掘也迅速地接纳了来自其他领域的思想，这些领域包括最优化、进化计算、信 息论、信号处理、可视化和信息检索。 一些其他领域也起到重要的支撑作用。特别地，需要数据库系统提供有效的 存储、索引和查询处理支持。源于高性能( 并行) 计算的技术在处理海量数据集 方面常常是重要的。分布式技术也能帮助处理海量数据，并且当数据不能集中到 一起处理时更是至关重要。 图1 3 展示了数据挖掘与其他领域之间的联系。 数据库技术、并行计算、分布式计算 图1 3数据挖掘与其他学科的汇集 数据挖掘任务 通常，数据挖掘任务分为两大类： 硕士学位论文第一章绪论 预测任务。这些任务的目标是根据其他属性的值，预测特定属性的值。被预 测的属性一般称目标变量或因变量，而用来做预测的属性称说明变量或自变 量。 描述任务。这里，目标是导出概括数据中潜在联系的模式( 相关、趋势、聚 类、轨迹和异常) 。本质上，描述性数据挖掘任务通常是探查性的，并且常 常需要后处理技术验证和解释结果。 在实际应用中，往往根据模式的实际作用细分为：分类模式、回归模式、时 间序列模式、聚类模式、关联模式、序列模式等等。 数据挖掘功能 数据挖掘的功能用于指定数据挖掘任务中要找的模式类型。主要功能如下： 预测建模( p r e d i c t i v em o d e l i n g ) 涉及以说明变量函数的方式为目标变量建立模型。有两类预测建模任务：分 类( c l a s s i f i c a t i o n ) ，用于预测离散的目标变量；回归( r e g r e s s i o n ) ，用于预测连 续的目标变量。例如，预测一个w e b 用户是否会在网上书店买书是分类任务， 因为该目标变量是二值的。另一方面，预测某股票的未来价格是回归任务，因为 价格具有连续值属性。两项任务目标都是训练一个模型，使目标变量预测值与实 际值之间的误差达到最小。预测建模可以用来确定顾客对产品促销活动的反应， 预测地球生态系统的扰动，或根据检查结果判断病人是否患有某种特定的疾病。 关联分析( a s s o c i a t i o na n a l y s i s ) 用来发现描述数据中强关联特征的模式。所发现的模式通常用蕴涵规则或特 征子集的形式表示。由于搜索空间是指数规模的，关联分析的目标是以有效的方 式提取最有趣的模式。关联分析的应用包括找出具有相关功能的基因组、识别一 起访问的w 曲页面、理解地球气候系统不同元素之间的联系等。 聚类分析( c l u s t e ra n a l y s i s ) 旨在发现紧密相关的观测值组群，使得与属于不同簇的观测值相比，属于同 一簇的观测值相互之间尽可能类似。聚类可用来对相关的顾客分组、找出显著影 响地球气候的海洋区域以及压缩数据等。 异常检测( a n o m a l yd e t e c t i o n ) 识别其特征显著不同于其他数据的观测值。这样的观测值称为异常点或离群 点。异常检测算法的目标是发现真正的异常点，而避免错误地将正常的对象标注 为异常点。换言之，一个好的异常点检测器必须具有高检测率和低误报率。异常 检测的应用包括检测欺诈、网络攻击、疾病的不寻常模式、生态系统扰动等。 1 1 2 数据挖掘的应用和研究方向 数据挖掘是一种技术，它将传统的数据分析方法与处理大量数据的复杂算法 4 硕士学位论文第一章绪论 相结合。数据挖掘为探查和分析新的数据类型以及用新方法分析旧有数据类型提 供了令人振奋的机会。目前，在很多重要的领域，数据挖掘都可以发挥积极促进 的作用1 3 1 。其中包括以下一些应用： 在对客户进行分析方面：银行信用卡和保险行业，利用数据挖掘将市场 分成有意义的群组和部门，从而协助市场经理和业务执行人员更好地集中有促进 作用的活动和设计新的市场运动。 在客户关系管理方面：数据挖掘能找出产品使用模式或协助了解客户行 为，从而可以改进通道管理( 如银行分支和a t m 等) 。又如j 下确时间销售( r i g h t t i m em a r k e t i n g ) 就是基于顾客生活周期模型来实施的。 在零售业方面：数据挖掘用于顾客购货篮的分析可以协助货架布置，促 销活动时间，促销商品组合以及了解滞销和畅销商品状况等商业活动。通过对一 种厂家商品在各连锁店的市场共享分析，客户统计以及历史状况的分析，可以确 定销售和广告业务的有效性。 在产品质量保证方面：数据挖掘协助管理大数量变量之间的相互作用， 并能自动发现出某些不j 下常的数据分布，揭示制造和装配操作过程中变化情况和 各种因素，从而协助质量工程师很快地注意到问题发生范围和采取改正措施。 在远程通讯方面：基于数据挖掘的分析协助组织策略变更以适应外部世 界的变化，确定市场变化模式以指导销售计划。在网络容量利用方面，数据挖掘 能提供对客户聚集服务使用的结构和模式的了解，从而指导容量计划人员对网络 设施作出最佳投资决策。 在各个企事业部门，数据挖掘在假伪检测及险灾评估、失误回避、资源 分配、市场销售预测广告投资等很多方面，起着很重要作用。例如在化学及制药 行业，将数据挖掘用于巨量生物信息可以发现新的有用化学成分；在遥感领域针 对每天从卫星上及其它方面来的巨额数据，对气象预报、臭氧层监测等能起很大 作用。 当面临新的数据集提出的挑战时，传统的数据分析技术常常遇到实际困难。 下面是一些特定的挑战，它们引发了对数据挖掘的研列4 】。 可伸缩。由于数据产生和收集技术的进步，数吉字节、数太字节甚至数 拍字节的数据集越来越普遍。如果数据挖掘算法要处理这些海量数据集，则算法 必须是可伸缩的。可伸缩可能还需要实现新的数据结构，以有效的方式访问个别 记录。例如，当要处理的数据不能放进内存时，可能需要非内存算法。使用抽样 技术或开发并行和分布算法也可以提高可伸缩程度。 高维性。现在，常常遇到具有数以百计或数以千计属性的数据集，而不 是数十年前常见的只具有少量属性的数据集。在生物信息学领域，微阵列技术的 硕十学位论文 第一章绪论 进步已经产生了涉及数千特征的基因表达数据。具有时间或空间分量的数据集也 趋向于具有很高的维度。 异种数据和复杂数据。通常，传统的数据分析方法只处理包含相同类型 属性的数据集，或者是连续的，或者是分类的。随着数据挖掘在商务、科学、医 学和其他领域的作用越来越大，越来越需要能够处理异种属性的技术。近年来， 已经出现了更复杂的数据对象。这些非传统的数据类型的例子包括含有半结构化 文本和超链接的w e b 页面集、具有序列和三维结构的d n a 数据、包含地球表面 不同位置上的时间序列测量值的气象数据。 数据挖掘结果表达与可视化。数据挖掘应该能够用高水平语言、可视化 表示、或其它表示方式来描述所挖掘出的知识，以使用户更加容易地理解和应用 所挖掘出的知识。数据挖掘结果的可视化表示，对于交互式数据挖掘系统而言是 非常重要的，同时也要求系统采用多种表示形式，如：树、表格、规则、图、示 意图、矩阵、曲线来描述数据挖掘结果。 处理有噪声或不完整的数据。数据库中的数据或许反映有噪声、不完整、 以外的数据对象。因此当挖掘数据规律时，这些对象或许会使挖掘过程迷失方向 以致挖掘出一个不符合实际情况的模型。这时就需要数据清洗和数据分析方法以 处理这些有噪声的数据；有时也需要异类挖掘方法以帮助实现意外情况的挖掘与 处理。 并行、分布和增量更新算法。许多数据库中数据的巨大规模、广泛分布 的数据( 存储) 地点，以及一些数据挖掘算法的计算复杂性等，都极大地推动了 并行分布数据挖掘算法的研究与开发。这类算法将数据分为若干份进行并行处 理，然后将处理获得的结果合并在一起。此外一些数据挖掘过程所涉及的高昂代 价也促使了增量数据挖掘算法的发展，这类增量挖掘算法无需每次挖掘时均对整 个数据库进行挖掘而只需对数据库中的增量数据进行挖掘即可。 1 2 数据挖掘中的聚类分析 1 2 1 聚类分析的意义及研究现状 聚类分析是人类活动中的一个重要内容。早在儿童时期，一个人就是通过不 断完善潜意识中的分类模式，来学会识别不同物体，如：狗和猫，或动物和植物 等。通过聚类，人可以辨认出空旷和拥挤的区域，进而发现整个的分布模式，以 及数据属性之间所存在有价值的相关关系。因此它广泛应用于模式识别、数据分 析、图像处理和市场分析等许多领域，例如： ( 1 ) 在市场分析中，通过聚类分析能帮助决策者识别不同特征的客户群以及 各客户群的行为特征； 6 硕士学位论文第一章绪论 ( 2 ) 在生物工程研究中，聚类分析能够用于推导动植物的分类，按照功能对 基因进行划分并获取种群中的固有结构特征； ( 3 ) 在非关系数据库领域( 如空间数据库领域) ，聚类分析，能够识别具有相同 地理特征的区域以及该区域的环境和人的特征； ( 4 ) 在w e b 信息检索领域，聚类分析能够对w e b 文档进行分类，提高检索效 率。 此外，聚类分析的另一个研究价值在于将它作为其他分析模式( 如概念描述、 分类等) 的预处理技术能够提高其他模式的分析效果。例如，在建立概念层次树 时，聚类分析能够根据数据的分布自动生成或调整概念层次，消除了人为划分的 不合理因素，使得概念层次的划分更加科学合理。因而，聚类分析在数据挖掘领 域得到非常广泛的研究和应用【5 】。 聚类作为数据挖掘中一个重要的组成部分，主要用于在潜在的数据中发现有 价值的数据分布和数据模式，目前其研究已深入到数据库、机器学习、统计等领 域并取得了很大的成就。 聚类分析的研究主要是集中在对聚类算法的研究和改进上，许多传统的聚类 算法都是为特定的领域设计的，都有各自的特点和应用范围，每一个算法在算法 的伸缩性，可处理的数据类型，确定参数的领域知识，算法的稳定性等方面都存 在着自身的优点和局限，任何一种聚类算法都不可能在每个方面上都优越于其它 算法，在实际的应用中，很多研究者根据应用领域的需要对传统的算法进行改进， 试图对传统的聚类算法在这些方面的局限进行突破。 不同的聚类算法之间存在差异性，相同的聚类算法在不同的参数设定下也存 在者很大的差异性，也即对于相同的数据集，无论采用同一种聚类算法还是采用 不同的聚类算法，其得到的划分结果都很有可能不同，而且研究表明这些划分结 果之间存在互补信息，可以利用这种互补信息来提高识别性能，因此利用多个聚 类器进行聚类融合的技术近来也成为了聚类分析领域的研究热点之一。 1 2 2 混合型数据聚类问题 传统的聚类算法都只考虑数据是数值型的，并在多维几何空间中度量和表示 数据。还有一些概念型聚类算法单纯考虑数据是概念型的，它们采用信息理论中 的一些方法来度量点和类之间的相似性。但随着聚类分析的应用从科学领域、工 程领域发展到医学、商业和社会领域，大多数的数据由概念型和数值型属性来描 述，也就是说大多数的数据是混合型数据。要为混合型数据定义一个相似性度量 并不容易，因为概念型数据和数值型数据具有不同的特点。 1 9 8 7 年，d h f i s h e r 在文献1 6 j 中提出c o b w e b 算法，f i s h e r 使用来源于信 息理论的c a t e g o r yu t i l i t y ( c u ) 度量对概念型数据聚类。这个度量划分数据的目标 7 硕士学位论文 第一章绪论 是最大化所得簇中正确预测特征值的概率，这种方法只适合于概念型数据。为了 处理混合型数据，1 9 9 0 年，f i s h e r 在文献【7 】中提出c o b w e b 3 算法，第二年， 他在文献【8 】中进一步改进c o b w e b 3 ，提出e c o b w e b 算法。f i s h e r 假设数值 型特征值都是正态分布的，从而改变c u 度量使之能处理数值型属性。 c o b w e b 3 和e c o b w e b 算法在决定簇结构时都没有考虑对象间的距离。 1 9 9 6 年，e c h e e s e m a n 和j s t u t z 在文献【9 】中提出a u t o c l a s s 算法，它是 基于贝叶斯理论的一种非监督式分类算法。它假设混合数据集是由一个有限混合 分布模型产生的，在使用e m 算法得到模型参数的最大似然估计值后，再用贝叶 斯分类方法来导出最可能的类分布。类内混合概率分布函数是单个属性的概率分 布的乘积，或属性间的联合分布。a u t o c l a s s 算法假设概念型属性为柏努利 分布( b e r n o u l l id i s t r i b u t i o n s ) ，数值型属性为高斯分布。a u t o c l a s s 算法也有概 率模型的最大似然估计过拟合问题。 1 9 9 7 年，z h e x u eh u a n g 在文献【1o 】【】中提出k - p r o t o t y p e s 算法，它将k m e a n s 算法改进来处理混合型数据的聚类。k p r o t o t y p e s 算法首先将概念型属性与数值 型属性分开，以便分别使用适合概念型属性和数据值型属性的距离度量，然后将 两者结合起来表示混合型数据问的距离。它和k m e a n s 算法一样具有效率高的优 点，但同样也受初始化的影响，容易陷于局部极小值。 2 0 0 2 年，在文献【1 2 j 中c e nl i 和g a u t a mb i s w a s 提出了混合型数据聚类算法 s b a c ( s i m i l a r i t y b a s e da g g l o m e r a t i v ec l u s t e r i n g ) 。s b a c 算法是一种凝聚型层次 聚类算法，在度量对象问和类间的相似性时，采用了g o o d a l l 相似性度量。对于 概念型属性，g o o d a l l 相似性度量赋于不经常出现的值匹配更大的权值。对于数 值型属性，相似性度量不仅考虑特征值的差别大小，而且考虑值对出现的独特性。 值对出现的独特性通过位于此值对区间内的数据点数来度量。 近几年，廖志芳等人1 1 3 】利用格论中简单元组以及超级元组将对象属性转化 为格的模型建立，以对象间格的覆盖数量来衡量类间相似度，根据高覆盖数高相 似度的原则选择聚类中心进行聚类。通过实验及与其他经典算法比较，在不增加 空间复杂度的情况下有效的提高了混合属性数据聚类的质量。 关于混合型数据的聚类问题，虽然已经有了多种算法能够对其进行处理，但 总体上获得的效果并不是很好，而现实世界又大量存在该类型的数据，因此我们 有必要改进聚类算法，以达到我们的预期要求。 1 3 论文内容及结构安排 本文在深入研究数据挖掘、聚类分析以及对混合型数据处理研究的基础上， 参考多分类器融合的算法研究，提出了对于聚类融合算法的改进方法，并使用 8 硕十学位论文 第一章绪论 u c i 数据集进行实验仿真。完成算法改进的同时，将聚类融合改进算法应用于电 信行业客户分析。 本文具体结构组织如下： 第一章为绪论，对数据挖掘技术进行全面综述，从数据挖掘的产生和发展、 功能和任务、定义与过程模型、应用领域以及未来研究方向等方面展开；然后简 要介绍聚类分析的意义及研究现状，重点分析了聚类算法处理混合型属性的数据 的一些研究进展等； 第二章重点介绍聚类分析技术以及聚类融合算法，较为详细的描述聚类分析 算法的研究内容、发展现状、经典算法以及优缺点比较等；对于聚类融合算法的 介绍则从思想起源、算法步骤、研究现状和发展方向等方面进行展开； 第三章描述了一种新的基于图的聚类融合算法，该算法首先分析了聚类中存 在的一些不确定性，并提出了自己的解决思路，接着给出了聚类融合算法的关键 技术，包括聚类成员的产生、融合函数的设计以及结果评估的度量标准，最后选 用u c i 中分类用标准测试数据集进行算法验证，记录数据将算法与单一算法和 同类的融合算法的性能进行比较，最终得到了较好的结果，验证了新的算法的有 效性；最后一节对聚类融合差异性度量进行了分析； 第四章在详细了解移动通信行业客户细分需求的基础上，针对某省通信企业 同常业务数据进行客户细分数据挖掘。通过需求分析和数据预处理后，将聚类融 合算法应用到客户细分模型当中。实验证明，该算法不仅可以处理不同的数据类 型，而且将客户细分为比较明显的典型行为特征的集群，为决策者制定出有针对 性的营销策略提供依据，进一步证明了聚类融合算法的有效性。 第五章为总结与展望，总结己做工作内容，并对未来的研究方向进行展望。 1 4 小结 在本章中，首先对数据挖掘技术进行综述，介绍其发展背景、运行流程、各 项功能以及其各种应用领域。1 2 节则是对数据挖掘中的聚类分析进行概述。本 节首先描述了聚类分析的一些应用领域并指出了传统聚类算法的不足，随后提出 一个解决之道：聚类融合，同时概述了混合型数据聚类的发展现状。在1 3 节中 对本文的研究内容以及全文的结构安排进行介绍。 9 硕士学位论文 第二章聚类分析与聚类融合 第二章聚类分析与聚类融合 本章是聚类分析和聚类融合的导论。我们从概述聚类分析开始，包括聚类的 定义，聚类分析中的数据结构和数据类型的讨论。然后介绍了主要的聚类算法， 并比较了算法之间的优缺点。本章第二节则介绍聚类分析中的聚类融合技术。包 括聚类融合的定义、研究内容和主要进展，最后还专门讨论了聚类融合中的差异 性度量方法。 2 1 聚类分析 2 1 1 聚类的定义 将一组物理或抽象的对象，根据它们之间的相似程度，分为若干组( g r o u p ) ： 其中相似的对象构成一组，这一过程就称为聚类过程( c l u s t e r i n g ) 。一个聚类 ( c l u s t e r ) 就是由彼此相似的一组对象所构成的集合；不同聚类中对象是不相似 的。就是从给定的数据集中搜索数据项之间所存在的有价值联系。在许多应用， 一个聚类中所有对象常常被当作一个对象来进行处理或分析等操作。 数据聚类分析是一个正在蓬勃发展的领域。聚类分析所涉及的领域包括：数 据挖掘、统计学、机器学习、空间数据库技术、生物学和市场学等。由于各应用 数据库所包含的数据量越来越大，聚类分析已成为数据挖掘研究中一个非常活跃 的研究课题。 聚类分析是一个富有挑战的研究领域，有关每一个应用都提出了一个自己独 特的要求。以下就是对数据挖掘中的聚类分析的一些典型要求。 ( 1 ) 可扩展性。 ( 2 ) 处理不同类型属性的能力。 ( 3 ) 发现任意形状的聚类。 ( 4 ) 需要( 由用户) 决定的输入参数最少。 ( 5 ) 处理噪声数据的能力。 ( 6 ) 对输入记录顺序不敏感。 ( 7 ) 高维问题。 ( 8 ) 可解释性和可用。 2 1 2 聚类分析中的数据结构和数据类型 2 1 2 1 数据结构 聚类分析中的数据结构通常用两种有代表性的数据结构来表示： ( 1 ) 数据矩阵 数据矩阵是一个对象一属性结构。它是由n 个对象组成，如：人：这些对象 l o 硕士学位论文第二章聚类分析与聚类融合 是利用p 个属性来进行描述的，如：年龄、高度、重量等。数据矩阵采用关系表 形式或n xp 矩阵来表示，如式( 2 1 ) 所示。 x f ： x q - ： x n ( 2 1 ) ( 2 ) 相异度矩阵 相异度矩阵是一个对象一对象结构。它存放所有n 个对象彼此之间所形成的 差异。它一般采用n x n 矩阵来表示，如式( 2 2 ) 所示。 0 d ( 2 ，1 ) 0 d ( 3 ，1 ) d ( 3 ，2 ) 0 d ( n ，1 ) d ( n ，2 ) 0 ( 2 2 ) 其中d ( i j ) 表示对象i 和对象j 之间的差异( 或不相似程度) 。通常d ( i j ) 为一 个非负数；当对象i 和对象j 非常相似或彼此“接近”时，该数值接近o ；该数 值越大，就表示对象i 和对象j 越不相似。由于有d ( i j ) = d 0 ，i ) 且d ( i ，j ) = o ，因此就 有式( 2 2 ) 所示矩阵。 数据矩阵通常又称为是双模式矩阵；而相异度矩阵则称为是单模式矩阵。因 为前者行和列分别表示不同的实体；而后者行和列则表示的是同一实体。许多聚 类算法都是基于相异度矩阵进行聚类分析的。如果数据是以数据矩阵形式给出 的，那么就首先需要转换为相异度矩阵，方可利用聚类算法进行处理。 2 1 2 2 数据类型 数据挖掘的对象复杂多样，聚类过程中所面临的不仅有数值类型数据，更多 的是非数值类型和混合类型数据。在数据挖掘中，对象属性经常出现的数据类型 有：间隔数值属性变量，二元变量，标称型、序数型和比例标度型变量以及混合 类型的变量。 间隔数值属性变量 间隔数值属性就是基本呈直线比例的连续测量值。为帮助避免对属性测量单 位的依赖，就需要对数据进行标准化。所谓标准化测量就是给所有属性相同的权 值。这一做法在没有先验知识情况下是非常有用的。而在一些应用中，用户会有 意识地赋予某些属性更大权值以突出其重要性。 为了实现标准化测量，一种方法就是将初始测量值转换为无单位变量。给定 一个属性( 变量) f ，可以利用以下计算公式对其进行标准化： ， p p m ；知； 砌 h ；h ；h 硕士学位论文第二章聚类分析与聚类融合 计算绝对偏差均值s ， j ，= 去( i x 。，一朋，| + l x ：，一所，i + + i x 可一朋1 ) ( 2 3 ) 基中x l ，x 矽是变量f 的n 个测量值；所，为变量f 的均值，也就是 朋，2 = ( x l ，+ x 2 ，+ + 石) 。 然后计算标准化测量( z 分值) ： 一x 铲一m f 乃2 气 ( 2 4 ) 在标准化之后，或在无需标准化的特定应用中，由间隔数值所描述对象之间 的差异( 或相似) 程度可以通过计算相应两个对象之间距离来确定。最常用的距 离计算公式就是欧氏距离，具体公式内容如下： d ( i ，) = i t 。一x ，。1 2 + | t ：一x ，：1 2 + + l x 驷一嘞1 2 ( 2 5 ) 其中扛( x n ，x 加，) ；= ( x j l0 2 ，嘞) ；它们分别表示一个p 维数据对 象。 另一个常用的距离计算方法就是m a n h a t t a n 距离，它的具体计算公式定义如 下： d ( i ，) = i x n x j i i + l x 陀- - x 口i + + i x 垆一x 归i ( 2 6 ) 二元变量 二元变量只有两个状态：0 和l 。其中二元变量又分为对称的二元变量和不 对称的二元变量。前者是指变量的两个状态不具有优先权，后者对于不同的状态 其重要性是不同的。对于二元变量，度量两个变量的差异度由简单匹配系数( 对 于对称的情况) 和j a c c a r d 系数( 对于非对称情况) 决定。设两个对象x ，和z ，q 是 属性值在两个对象中都为1 的属性个数，r 是属性值在x ，中为l 而在x ，中为0 的 属性个数，s 是属性值在t 中为0 而在x ，中为1 的属性个数，t 是属性值在两个 对象中都为0 的属性个数则简单匹配系数： d ( i ，_ ，) ：生( 2 7 ) g 十，十s 十t j a c c a r d 相关系数： d ( i ，歹) ：旦 g + ，+ s ( 2 8 ) 标称型、序数型和比例标度型变量 ( 1 ) 标称变量 标称变量是二元变量的一个推广。标称变量可以对两个以上的状态进行描 1 2 硕士学位论文第二章聚类分析与聚类融合 述。对于标称变量，最常用的计算对象i 和对象j 之间差异( 程度) 的方法就是 简单匹配方法。它的具体定义描述如公式( 2 9 ) 所示。 d ( i ，) ：生竺( 2 9 ) p 其中n l 表示对象i 和对象j 中取同样状态的符号变量个数( 匹配数) ；p 为所 有的符号变量个数。 ( 2 ) 序数型变量 一个离散序数型变量与一个标称变量相似，不同的是( 对应m 个状态的) 的m 个序数值是具有按照一定顺序含义的。序数型变量在描述无法用客观方法 表示的主观质量评估时是非常有用的。 在计算对象间差异程度时，序数型变量的处理方法与间隔数值变量的处理方 法类似。假设变量f 为一组描述n 个对象序数变量中的一个。涉及变量f 的相异 度计算方法描述如下： 1 ) 第i 个对象的f 变量值标记为x f ，变量f 有个m ，有序状态，可以利用等 级l ，2 ，m 厂分别替换相应的h ，得到相应的o ，o 1 , 2 ，m j ； 2 ) 由于每个序数型变量的状态个数可能不同。因此有必要将每个顺序变量的 取值范围映射n o 1 】区间，以便使每个变量的权值相同。可以通过将第i 个对象 中的第f 个变量的。用以下所计算得到的值来替换： r ，一1 z 矿2 未j ( 2 1 0 m ) 二矿一 ，一1 ， 3 ) 这时可以利用前面所介绍有关间隔数值变量的任一个距离计算公式，来计 算用序数型变量描述的对象问距离；其中用乃来替换第i 个对象中的变量f 值。 ( 3 ) 比例标度型变量 一个比例数值变量就在非线性尺度上所获得的正测量值，如：指数比例，就 可以用以下公式近似描述： 么p 肼或彳p 嘲 ( 2 1 1 ) 这里的a 和b 是正的常数。典型的例子包括细菌数目的增长，或者放射性 元素的衰变。 混合类型变量 在实际数据库中，对象是由混合类型的变量描述的。在实际聚类分析中，是 将不同的类型属性组合在同一个相异度矩阵中进行计算的。设数据集包含p 个组 合类型变量，则对象i 和对象j 之间的距离d ( i j ) 就可以定义为： 硕士学位论文第二章聚类分析与聚类融合 = 鬻 亿埘 其中如果h 或x ，缺失，或者h = x f r = 0 ，且变量f 是不对称二元变量，则指 示项s y = 0 ，否则s y = 1 。 如果f 是二元变量或标称变量：如果= x r ，d 扩k o ；否则d v - - 1 。 l 一， i 如果f 是区间标度变量：d ：，) ：上生二z l 一，这里的h 遍取变量f 二 m a x hx 够一m m hx h ， 的所有非空缺对象。 如果f 是序数型或者比例标度型变量：将其转化为区间标度变量值对待。 2 1 3 主要聚类方法的分类及对比 2 1 3 1 聚类方法的分类 现有的主要聚类算法可以大致分为以下几种：划分方法、层次方法、基于密 度的方法、基于网格的方法以及基于模型的方法。下面对这些主要的聚类算法一 一进行介绍，并进行简单的分析和比较。 划分方法 对于一个给定的n 个数据对象的数据集，采用目标函数最小化的策略，通过 把数据分成k 个组，每个组为一个簇，这就是划分方法。可以看出，这种聚类方 法同时满足以下两个条件：( 1 ) 每个组至少包含一个数据对象；( 2 ) 每个数据对象 必须属于且仅属于一个组。当然，在有些情况下，如模糊聚类，条件( 2 ) 可以放 宽要求。最著名与最常用的划分聚类算法是k 一平均( k m e a n s ) t 1 4 , t 5 1 算法和k 中心 点( k m c d o i d s ) 算法，其他划分方法大都是这两种方法的变种。 层次方法 层次聚类算法按数据分层建立簇，形成一棵以簇为节点的树。如果按自底向 上进行层次分