（控制理论与控制工程专业论文）聚类融合算法研究及其在电信中的应用.pdf

瀣巍大学酸：l ：学位论文蒙类敲含算法磺究及其露电基中戆癍赐 摘要 聚类，作为数据挖掘技术研究的热点之一，受到了越来越多的关注。目前 已有很多比较成熟的聚类算法，如k - m e a n s 、k - m e d o i d s 、b i r c h 、c u r e 、 d b s c a n 、s t i n g 等。虽然其中有些算法已经得到广泛应用，但由于聚类分析 算法对于数据集有诸多限制，所以很难找到适合的方法迸行聚类分析。由此， 聚类磁合算法应运焉生。2 0 0 2 年，聚类融合算法一经提出就得到广泛关注。实 验证明，该方法能够得到比单一聚类算法更优的结果。但其自身并不成熟，仍 存在许多问题，如关键参数设定、“软“硬聚类的融合、共识函数的设计及 选择等。本文新做工作如下： 1 本文在深入了解聚类融合算法的基础上，重点考察了利用k - m e a n s 算 法产生聚类成员的聚类融合算法中各成员的聚类个数与最终融合质量的关系， 并提出了一种改进算法以提高聚类融合的精确度。首先，根据聚类成员之阀存 在差异度的思想，定义了一种差异度计算公式；其次，通过实验考察各个聚类 成员的聚类个数与目标聚类个数的差值对融合结果的影响，制定了加权函数的 计算公式。实验数据证明，改进算法在精确度方面谠予豢算法。 2 电信中客户细分模型多用k - m e a n s 算法来进行，但该方法在实际成用 中存在许多问题：需要专业人员指定聚类个数并对结果做出经验判断、划分结 果“过硬等。本文将聚类融合改进算法号l 入客户细分中，以某市电信公司小 灵通业务数据挖掘为背景，针对客户通话、短信等行为属性特征进行客户细分。 过程中使用聚类融合改进算法，能够有效解决上述问题并得出合理的聚类结果， 弼时通过对c o - a s s o c i a t i o n 矩阵的分析可以得到每个客户属予某一集群的概率， 达到了“软化划分结果的豳的，使数据挖掘更智能化。 关键词：数据挖掘、聚类、聚类融合、差异度、共识函数、电信、客户细分、 数据预处理 瀚江大学矮一 学使论文聚类融会算法礤究及其j 谯逝焦孛戆疲愿 a b s t r a c t c l u s t e r i n g , a so 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 n i n c r e a s i n g l yh o tt o p i c a tp r e s e n t ，m a n yc l u s t e r i n ga l g o r i t h m sa r ea v a i l a b l e ，s u c ha s k - m e a n s ，k - m e d o i d s ，b i r c h ，c h r e ，d b s c a n 、s t i n g , a n ds oo n a l t h o u g h s o m eo ft h e mh a v eb e e na p p l i e dw i d e l y , i ti sh a r df o rp e o p l et of i n d s u i t a b l e c l u s t e r i n ga l g o r i t h mf o rap r o p e rd a t as e t ，f o rt h e r ea l em a n yr e s t r i c t s o nt h o s ed a t a s e t sf r o mc l u s t e r i n g s o ，c l u s t e r i n ge n s e m b l ee m e r g e da st h et i m e sr e q u i r e i n2 0 0 2 ， c l u s t e r i n ge n s e m b l ea l g o r i t h mw a sp u t t e df o r w a r da n ds o o ng i v e ne x t e n s i v e a t t e n t i o n e x p e r i m e n t sp r o v e dt h a tt h r o u g ht h i sm e t h o dw ec a ng e tb e t t e rr e s u l tt h a n s i n g l ec l u s t e r i n ga l g o r i t h m b u tt h i sa l g o r i t h mi sf a rf r o mm a t u r e ，s u c h a st h e e n a c t m e n to fs o m ek e yp a r a m e t e r s ，t h ee n s e m b l eb e t w e e n s o f t c l u s t e r sa n d h a r d d u s t e r s , h o wt od e s i g na n dc h o o s et h ec o n s e n s u sf u n c t i o n s ，a n ds oo n t h em a i n w o r k si nt h i sp a p e ra r ed e s c r i b e da sf o l l o w s ， 1 o nt h eb a s i co fh a v i n gs t u d i e d c l u s t e r i n ge n s e m b l e st h o r o u g h l y , b y f o c u s i n go nr e v i e w i n gt h er e l a t i o n s h i p sb e t w e e nn u m b e r so fd u s t e r si ne v e r y e l u s t e r e ra n dt h eq u a l i t yo ft h ef i n a lr e s u l t ，a n da ni m p r o v e da l g o r i t h mt oi m p r o v e t h ea c c u r a c yo fc l u s t e r i n ge n s e m b l ew a sm a d e f i r s t ，a c c o r d i n gt ot h ei d e at h a tt h e r e a l ed i v e r s i t i e sa m o n gd u s t e r s , af o r m u l at om e a s u r et h i sd i v e r s i t yw a sd e f i n e d ； s e c o n d l y , w h e t h e rt h ed i f f e r e n c eb e t w e e nn u m b e r so fd u s t e r so fc l u s t e r e r sa n dt h e t a r g e tn u m b e rh a si n f e c to nt h ee n s e m b l er e s u l tt h r o u g he x p e r i m e n t sw a si n s p e c t e d ， t h e naf o r m u l at oc a l c u l a t et h ew e i g h 毽o i lc l u s t e r e r sw a sd e v e l o p e d e x p e r i m e n t a l d a t as h o wt h a ti m p r o v e da l g o r i t h mi ss u p e r i o rt ot h eo r i g i n a la l g o r i t h mo ra c c u r a c y 2 k - m e a n sa l g o r i t h mh a sa l w a y sb e e nu s e di nt e l e c o m m u n i c a t i o n sc u s t o m e r s e g m e n t a t i o nm o d e l ，b u t t h i sm e t h o dh a sm a n y p r o b l e m s ，s u c h a sn e e d s p r o f e s s i o n a l st od e s i g n a t et h en u m b e r st ob ec l u s t e r e da n dj u d g et h er e s u l t so nt h e i r e x p e r i e n c e ，t h ep a r t i t i o nr e s u l ti s “t o oh a r d , a n ds oo n i nt h i sp a p e r , i m p r o v e d c l u s t e r i n ge n s e m b l e0 c e ) a l g o r i t h mw a su s e d ，a n dt h ed a t am i n i n go np h s b u s i n e s s o fac e r t a i nc i t y st e l e c o m m u n i c a t i o n sc o m p a n yw a su s e da sb a c k g r o u n d , a i m sa t c u s t o m e rc a l l s ，m e s s a g e s ，a n do t h e ra t t r i b u t e so fc u s t o m e r s a c t i o n st od ot h e i 釜一 浙江大学硕j ：学位论文 聚类融合算法研究及】乓和电信中的廊用 s e g m e n t a t i o n i nt h i sp r o c e s s ，i c ea l g o r i t h mw a su s e d t os e t t l et h o s ep r o b l e m s m e n t i o n e da b o v ee f f e c t i v e l ya n dg o tar e a s o n a b l er e s u l t a n da tt h es a m et i m e ，t h e c o - a s s o c i a t i o nm a t r i xa l s ow a su s e dt os h o wt h ep r o b a b i l i t yo fe a c hc u s t o m e r b e l o n g i n gt oac l u s t e f i nt h i sw a y , t h ea i mt o “s o f t e n ”t h er e s u l tw a sa c h i e v e d ，a n d t h i sc a l lm a k ed a t am i n i n gm o r ei n t e l l i g e n t 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 l g o r i t h m ，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 y , c o n s e n s u sf u n c t i o n ，t e l e c o m m u n i c a t i o n ，c u s t o ms e g m e n t a t i o n ，d a t a p r e p r o c e s s l n g 一一 浙江大学矮“ 学整论文聚类戳会算法磷究菠j 在电蘩孛熊瘫焉 第1 章绪论 摘要：在介绍数据挖掘产生和发展的基础上，引出数据挖撅的定义，揭示其 研究意义，并在方法论、数据挖掘技术的应用以及未来麴研究方向等 方面进行综述。随后笱略介绍聚类融合算法的研究状况，描述其研究 意义、优势和未来可研究的方向。本章最后介绍本文的主要研究内容 和本论文结构。 关键词：数据挖掘、聚类、聚类融合、综述 1 1 数据挖掘研究综述 1 1 1 数据挖掘的研究背景 数据挖掘作为一个新兴的多学科交叉应用领域，在各行各业的决策支持活 动中扮演着越来越重要的焦色。随着计算机技术的飞速发展，产生了功能强大 的计算机、数据收集设备和存储设备。这些技术大大推动了数据库和信息产业 的发展，使得大量的数据库和信息的存储设备用于事务管理、信息提取和数据 分析。褥随着数据库容量的膨胀，联机分辑处理、决策支持以及分类、聚类等 复杂应用成为必然。面对这挑战，数据挖掘和知识发现技术应运丽生，并显 示出强大的生命力。 所谓“知识 ，可定义为售息块中的一组逻辑联系，其关系是通过上下文 或过程的贴近度发现的 【u 。从信息中理解其模式，即形成知识。置身如今的 市场经济，面向全球性的剧烈竞争，任何商家的优势不再单纯地取决于如产品、 服务、地区等方面因素，嚣孬是在于创薪。用知识作为创薪的孤动力，就麓够使 商家长期持续的保持竞争优势。因此，要能够及时迅速地从网积月累庞大的数 据库中以及互联网上获取与经营决策相关的知识，自然而然使得“如何对数据 与信息快速有效缝进行分橱加工提炼以获取所需知识成为计算机及信息技术 领域的重要研究课题。1 9 8 9 年第十一届国际人工智能联合会议首次提出“数据 库中的知识发现( k d d ：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 ) ；随后于1 9 9 1 年【2 l 、 1 9 9 3 年和1 9 9 4 年又相继召开了数k d d 为主题的研讨会。“数据挖掘( d 鹾：d a t a l 一 m i n i n g ) ”概念的提出是在1 9 9 5 年在美国召开的计算机年会上：从大量的、不 完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不 知道的，但又潜在、有用的信息和知识的过程。 数据挖掘是信息技术自然演化的结果。演化过程的见证是数据库业界开发 以下功能( 见图1 1 ) ：数据收集和数据库创建，数据管理( 包括数据存储和检 索，数据库事务处理) ，以及数据分析与理解( 涉及数据仓库和数据挖掘) 。促 进数据挖掘诞生j 发展、应用的主要因素有三：数据库系统的不断发展；计算 机技术的迅猛发展；对信息和知识的迫切需求。 图1 1数据库技术的演化 一2 一 瑟淀天学溪一l ：学位论文聚类融会雾法研究及其在电售孛鲢癍焉 数据库系统的不断发展 数据管理经历了人工管理、文件系统、数据库系统三个阶段。2 0 世纪6 0 年代后期，为实现计算机对数据的统一管理，达到数据共享的瞪的，发展了数 据库技术。数据库技术的主要莓的是有效豹管理和存取大量的数据资源，包括： 提高数据共享性、多用户同时访问数据库数据、减少数据冗余度等。1 9 6 4 年， 美国通用电气公司开发成功了世界上的第一个数据库系统一i d s ( i n t e g r a t e d d a t as t o r e ) 。i d s 奠定了网状数据库的基础，并且得到了广泛的发行和应用， 成为数据库系统发展史上的座丰碑。1 9 6 9 年，美国国际商用机器公司( 1 b m ) 也推出世界上第个层次数据库系统i m s ( i n f o r m a t i o nm a n a g e m e n ts y s t e m ) ， 同样在数据库系统发展史上占有重要的地位。7 0 年代初，e 。e c o 渊在总结层次、 网状数据库优缺点的基础上，提出了关系数据模型的概念以及关系代数和关系 演算。在整个7 0 年代，关系数据库系统无论从理论上还是实践上都取得了丰硕 的成果。在理论上，确立了完整的关系模型理论、数据依赖理论和关系数据库 的设计理论；在实践上，世界上出现了很多著名的关系数据库系统，比较著名 的如s y s t e m r ，i n g r e s ，o r a c l e 等。8 0 年代，随着科学技术的不断进步，各 个行业领域对数据库技术提出了更多的需求，关系型数据库同其他许多新技术 相结合( 如分布处理技术、并行计算技术、人工智能技术、多媒体技术、模糊 技术等) ，广泛应用于多个领域( 商业管理、g i s 、计划统计等) 。进入9 0 年代， 分布式数据库理论上趋于成熟，分布式数据库技术得到了广泛应用。大规模数 据库，尤其是数据仓库的出现，为数据挖掘技术的发展和应用提供了卓越的乎 厶 口。 计算机技术的迅猛发展 自1 9 4 6 年世界公认的第一台逶用电子数字计算祝诞生以来，计算机技术取 得了快速的发展。如今的计算机具有强大的运算能力、存储量、逻辑判断能力 等，将大量的管理人员从繁重的日常信息处理工作中解脱出来，使得他们有精 力、有篾力对激增的数据进行更高层次的分析和更有效的利用并从中寻找对企 业战略发展具有重要意义的商业规律和市场趋势。同时，计算机运算能力和运 算速度的不断提高，各种功能强大的软件的开发，使得许多复杂算法的实现成 为可麓。由此，迅猛发展的计算概技术戒为数据挖掘技术发展的一大保证。 一3 一 浙江犬学硕i ：学位论文聚类融合算法研究及j e 在i 乜信中的心用 对信息和知识的迫切需求 早在8 0 年代，人们在“物竞天择，适者生存”的大原则下，就认识到“谁 最先从外部世界获得有用信息并加以利用，谁就可能成为赢家 。一个企业要保 持竞争优势并不断获得企业盈利，关键是要决策科学化，可以从以下四个方面 入手：一，提高分析的速度和灵活性；二，集成企业范围内所有数据并将这些 数据转化成有用的信息；三，改进企业业务流程，促进或再创造商业进程；四， 明确顾客需求。在以知识经济为主导的社会中，对知识、信息的掌握已经成为 企业在竞争中取得胜利的最有效武器，这种强烈的需求极大地推动了数据挖掘 技术的发展。 1 1 2 数据挖掘研究方法论 数据挖掘的研究任务 随着数据挖掘研究逐步走向深入，数据挖掘和知识发现的研究已经形成了 三个强大的技术支柱：数据库、人工智能和数理统计。因此机器学习、模式识 别、人工智能领域的常规技术，如分类、聚判3 挪、决策树1 5 】、神经网络【6 , 7 1 、进 化计算【8 】以及模糊集、粗糙集1 9 l 等方法经过改进都可以应用于数据挖掘。但是， 数据挖掘系统通常面对的是大量的类型更加复杂的数据。因此，对现有技术的 改进，综合各种方法技术优点的有效的集成以及研究面向数据挖掘的新技术都 是数据挖掘的研究内容。 数据挖掘涉及多学科技术的集成，包括数据库技术、统计学、机器学习、 高性能计算、模式识别、神经网络、数据可视化、信息检索、图像与信号处理 和空间数据分析。数据挖掘技术的形成过程如图1 2 所示。通过数据挖掘，可 以从数据库中提取有趣的知识、规律或高层信息，并可以从不同角度进行观察 或浏览。发现的知识可以用于决策、过程控制、信息管理、查询处理等等。数 据挖掘的研究内容可以概括为：基础理论方面，包括数据库、数据仓库以及海 量数据的存储和调用等；发现算法，包括概括、分类、聚类、关联等针对特定 挖掘任务和知识的有效方法；只是表示方法和可视化技术；发现知识的维护和 再利用；半结构化和非结构化数据中的知识发现以及网络数据挖掘等。 一4 一 澎汪丈学醭士学位论文聚类黻会算法磷究及其在逛蔫孛的痤用 图1 2数据挖掘技术瞬形成 数据挖掘任务一般可以分两类：描述( d e s c r i p t i v e ) 和预测( p r e d i c t i v e ) 。 描述性挖掘任务刻画数据库中数据的一般特性，是对数据中存在的规则作一种 描述，或者根据数据的相似性把数据分组。预测性挖掘任务在当前数据上进行 推断以进行预测，所使用的数据都是可以骧确知道结果的。在实际应用中，往 往根据模式的实际作用细分为：分类模式、回归模式、时间序列模式、聚类模 式、关联模式、序列模式等等。分类模式和回归模式是使用最普遍的模式。分 类模式、回归模式、时闻序列模式也被认为是受监督知识，因为在建立模式兹 数据的结果是已知的，可以直接用来检测模式的准确性，模式的产生是在受监 督的情况下进行的。一般在建立这些模式时，使用一部分数据作为样本，粥另 部分数据来检验、矫正模式。聚类模式、关联模式、序鳓模式则是j # 监督知 识，因为在模式建立前结果是未知的，模式的产生不受任何监督。通过这些模 式，我们一般可以得到以下几类知识： ( 1 ) 广义知识( g e n e r a l i z a t i o n ) ( 2 ) 关联知识( a s s o c i a t i o n ) ( 3 ) 分类知识( c l a s s i f i c a t i o na n dc l u s t e r i n g ) ( 4 ) 预测型知识( p r e d i c t i o n ) ( 5 ) 偏差型知识( d e v i a t i o n ) 数据挖掘全过程 数据挖掘，又称为数据库孛知识发现( k n o w l e d g ed i s c o v e r yf r o md a t a b a s e ， 简称舶d ) ，它是一个从大量数据中抽取挖掘出未知的、有价值的模式或规律 等知识的复杂过程。数据挖掘的全过程定义描述如图1 3 所示： 一5 一 浙江大学硕士学位论文聚类融合算法研究及) e 在电信中的应用 图1 3知识挖掘全过程示意描述 由上图知，整个知识挖掘( k d d ) 过程是由若干挖掘步骤组成，而数据挖 掘仅是其中的一个主要步骤。整个知识挖掘的主要步骤有： 数据清洗( d a t ac l e a n i n g ) ：清除数据噪声和与挖掘主题明显无关的数据； 数据集成( d a t a i n t e g r a t i o n ) ：将来自多数据源中的相关数据组合到一起； 数据转换( d a t at r a n s f o r m a t i o n ) ：将数据转换为易于进行数据挖掘的数 据存储形式； 数据挖掘( d a t am i n i n g ) ：知识挖掘的一个基本步骤，其作用就是利用 智能方法挖掘数据模式或规律知识； 模式评估( p a t t e r ne v a l u a t i o n ) ：根据一定评估标准( i n t e r e s t i n gm e a s u r e s ) 从挖掘结果筛选出有意义的模式知识； 知识表示( k n o w l e d g ep r e s e n t a t i o n ) ：利用可视化和知识表达技术，向 用户展示所挖掘出的相关知识。 数据挖掘功能 数据挖掘的功能用于指定数据挖掘任务中要找的模式类型。现介绍数据挖 掘的主要功能如下： 概念描述( c o n c e p td e s c r i p t i o n ) 数据库中通常存放大量的细节数据，但用户通常希望能够以简洁的描述形 式观察汇总数据集。这种汇总的、简洁的、精确的描述方式成为类概念描述。 这种描述可以通过下述方法得到：1 ) 数据特征化，一般的汇总所研究类的数据； 一6 一 濒江大学醭学位论文聚类融合算法疆究及芟凌逛嚣孛豹应用 2 ) 数据区分，将目标类与一个或多个比较类进行比较；3 ) 数据特缝化和比较。 关联分析( a s s o c i a t i o na n a l y s i s ) 关联分析就是从大量数据中发现项集之间有趣的关联或褶关联系。关联分 析广泛鲍应用于购物篮或事物数据分析中，可以帮助商家制定许多荔务决策， 从而使得业界人士对于从他们的数据库中挖掘关联规则越来越感兴趣。 分类和预测( c l a s s i f i c a t i o na n df o r e c a s t ) 分类和颈测是两种数据分析形式。分类是找出描述并区分数据类或概念的 模型( 或函数) 以便能够使用模型预测类标记未知的对象类，可以用来预测数 据对象的类标记。但在某些应用中，人们希望预测某些空缺的或不知道的数据 值，磊不是类标记。当被预测的傻是数值数据时，通常称之为预测。预测可以 涉及数据值预测和类标记预测，但通常限于值预测并因此而不同予分类。预测 也包含基于可用数据的分布趋势识别。 聚类分析( c l u s l e f i n g ) 聚类分析的对象为数据对象，而不考虑己知的类标记。聚类，可以用于产 生这种标记。对象根据最大化类内的相似性、最小化类间的相似性的原则进行 聚类或分缰。 孤立点分析( o u t l i e ra n a l y s i s ) 数据库中可能存在一些与数据的一般行为或模型不一致的数据对象，这些 数据对象称为孤立点( o u t l i e r ) 。针对孤立点，一般的做法是将其视为嗓声或异 常面丢弃，但在某些应用( 如欺漤睑测) 中，孤立点本身可能是j 扛常重要的信 息。识别孤立点可以通过使用统计试验或通过基于偏差的方法。 演交分析( e v o l u t i o na n a l y s i s ) ， 数据演变分析描述行为随时阆变化的对象的规律或趋势，并对其建模。这 种分析包括时间序列数据分析、序列或周期模式匹配和基于类似性的数据分析。 借助这种分析，可以识别整个股票市场和特定公司的股票演变规律。这种规律 可以帮助蘸测股票市场价格的未来走向，在对股票微獭投资决策时提供帮助。 1 1 3 数据挖掘的应用和研究方向 数据挖掘技术从开始就是蕊囱应用的。毽前，在很多重要的领域，数据 挖掘都可以发挥积极促进的作用。尤其是在如银行、电信、保险、交通、零售 一? 浙江人学硕l ：学位论文聚类融合算法研究及0 ：i 乜箭中的应用 等商业应用领域。数据挖掘能够帮助解决许多典型的商业问题，其中包括：客 户群体划分( c u s t o m e rs e g m e n t a t i o n c l a s s i f i c a t i o n ) 、数据库营销( d a t a b a s e m a r k e t i n g ) 、背景分析( p r o f i l ea n a l y s i s ) 、交叉销售( c r o s s - s e l l i n g ) 等市场分 析行为，以及客户流失性分析1 1 0 l ( c h u ma n a l y s i s ) 、客户信用评分( c r e d i t s c o r i n g ) 、信用欺诈检测【1 l 】、股票价格分析与预测1 1 2 l 、金融风险分析1 1 3 】、购物 篮分析【1 4 l 等等。 在统计和机器学习领域中也有许多数据挖掘系统。另外，将数据仓库、 o l t p 、o l a p 和数据挖掘技术结合是近期数据库发展的一个趋势。数据仓库和 数据挖掘都可以完成对决策技术的支持，相互间有一定的内在联系，两者集成， 可以有效地提高系统的决策支持能力。目前，电信行业已经逐步建立起数据仓 库系统，在数据仓库的基础上将逐步建立如下数据挖掘专题：客户价值模型、 客户信用等级模型、客户流失预测模型、交叉销售模型、营销计划预演模型和 客户细分模型。其应用领域如图1 4 所示： 至) 臣习度要卫蜀 l二竺兰兰兰兰竺兰l 图1 4数据挖掘在电信行业的应用 数据挖掘在数据库之外的其它领域也有丰硕的成果，例如统计学中已发展 了许多用于数据挖掘的技术，演绎逻辑编程作为逻辑编程的一个迅速发展的分 支，与数据挖掘有密切联系。 数据、数据挖掘任务和数据挖掘方法的多样性给数据挖掘提出了许多挑战 性课题。数据挖掘语言的设计，高效而有用的数据挖掘算法和系统的开发，交 互和继承的数据挖掘环境的建立，以及应用数据挖掘技术解决大型应用问题， 一8 一 一一一一 ，圈豳蛰 一一一一 | i 爹 汪大学疆七学位论文聚类鞋仑雾法磷究及其在电戆孛懿斑耀 都是邂嚣数据挖掘研究人员、系统和废用开发人员所蘧临盼主要闯题。鬻蒋， 数据挖掘的研究方向主要有1 1 5 _ 1 7 l ： ( 1 ) 数据挖掘的应用研究； ( 2 ) 可 率缩的数据挖掘算法研究； ( 3 ) 数据挖掘与数据库、数据仓库和w e b 数据库系统的集成； ( 4 ) 数据挖掘语言的标准化研究； ( 5 ) 数据挖掘的可视纯研究； ( 6 ) 对于复杂数据类型进行挖撅的新方法研究； ( 7 ) 数据挖掘中的隐私保护与信息安全。 1 2 数据挖掘中的聚类融合算法研究 1 2 1 聚类融合算法研究背景 在机器学习中，聚类分析属于一种无( 教师) 监督的学习方法。与分类学 习不同，无( 教师) 监臀学习不依靠事先确定的数据类剐，以及标有数据类别 的学习训练样本集合。因此，聚类分柝又是一种通过观察进行学习方法 ( l e a r n i n gb yo b s e r v a t i o n ) ，而不是承例学习( l e a r n i n gb ye x a m p l e ) 。在数据 挖掘中，大多数工作都集中在发现能够有效、高效地对大数据库进行聚类分析 的方法上。相关豹研究课题包括：聚类方法的可扩展性、复杂形状和复杂数攒 类型的聚类分析的有效高效性、高维聚类技术，以及混合数值属性与符号属性 数据库中的聚类分析方法等。 数据对象分森多种多样，傻任何聚类算法都对数据集本身有定的预先假 设，根据“n of r e el u n c h 理论阳，如果数据集本身的分布并不符合预先的假 设，则算法的结果将毫无意义，甚至可以说该结果风是给出了一个错误的分布， 或是给数据集强加了一个虚构的分布。因此，面对特定的应用闯题，如何选择 合适的聚类算法是聚类分析研究中的一个重要课题。 1 2 2 国内外研究现状 聚类融合算法的提出给上述闯题带来了解决之道。融合方法将不同算法或 者同算法下使用不同参数得到的结果进行合并，从而得到比单一算法更为优 9 一 浙江火学硕l ：学位论文聚类融合算法研究及存电信中的心用 越的结果。在分类算法和回归模型中，正广泛而且成功地使用着融合方法，该 方法能克服分类、回归中的不稳定性，并给出较好的结果。在非监督机器学习 领域，由于缺乏数据集的先验知识，所以分类和回归中的融合方法就不能直接 用于聚类算法，这导致了该领域中对融合方法研究的起步较晚；近几年的研究 和实验表明，聚类融合方法能很好地提高聚类算法的鲁棒性、稳定性等性能。 聚类融合算法于2 0 0 2 年由a s t r e h l 和j g h o s h 正式提出，但在2 0 0 1 年 a l f r e d 就已经进行了类似的研究。其定义为：将多个对一组对象进行划分的 不同结果进行合并，而不使用对象原有的特征【2 8 l 。该算法一经提出就受到广泛 的关注，迅速成为聚类分析新的研究热点之一。纵观聚类融合算法研究近几年 来的发展，研究内容大致分为两部分：聚类成员的产生方法研究，共识函数的 设计和选择研究。 聚类成员产生方面：2 0 0 3 年a t o p c h y 等人研究了“软聚类组成的聚类 成员对聚类融合的影响；同年，x z f e m 提出将高维数据随机投影到低维空问 的方法产生聚类成员，随后又提出p c a 与随机抽样、p c a 与随机投影等方法； 2 0 0 4 年b m i n a e i b i d g o l i 等用随机抽样和b o o t s t r a p 的方法产生子样本集，并在 其上使用k m e a n s 算法产生聚类成员；a t o p c h y 则是提出了一种自适应的数据 成员产生方法，进一步提高了融合算法性能；l i k u n c h e v a 等人另辟蹊径，对 聚类成员之间的关系进行深入研究，发现存在差异度并制定了一些差异度的计 量公式，如r a n di n d e x ，j a c c a r di n d e x 等；2 0 0 5 年，s t h a d j i t o d o r o v 对差异度 进一步研究，考察差异度与最终融合质量的关系。 共识函数方面：2 0 0 2 年，一种基于m s t 的分级聚类算法被提出；2 0 0 3 年， c s p a , h g p a , m c i a 这三种基于超图的方法首先被提出，随后提出了一些在此 基础上的改进算法，如w s n n g 等；2 0 0 4 年，基于双元图的h b g f 方法以及基 于多项式分布的混合模型构建共识函数的方法也被提出。 聚类融合可以比单一聚类算法得到更好的结果，a t o p c h y 总结出了以下几 个方面【2 9 】： ( 1 ) 鲁棒性：在各领域和数据集中的平均性能更为优越； ( 2 ) 适用性：能找到单一聚类方法难以得到的聚类结果； ( 3 ) 稳定性：噪声、孤立点和抽样方法等对聚类结果的影响较小； 一1 0 一 添江犬学矮士学位论文聚类融合棼法臻究获其在| 莛浆孛酶癍耀 基予刚格聚类方法利用多维网格数据结构，将空间划分为有限数墨的单元， 以构成一个可以进行聚类分析的网格结构。这种方法的主要特点就是处理时间 与数据对象数目无关，但与每维空间所划分的单元数相关；其优点为处理速度 很快，处理时间独立予数据对象的数霸。此类算法不适用于高维情况，因为鼹 格单元的数目随着维数的增加丽呈指数增长。 所有基于网格的聚类算法都存在下列问题：一是如何选择合适的单元大小 和数酱，单元数霸太少时，精度就会穰低，褥单元数露太多时算法的复杂度就 会变大；二是怎样对每个单元中对象的信息进行汇总。 基于网格的有代表性的算法包括：s t i n g ( s t a t i s t i c a li n f o r m a t i o ng r i d ) 算 法，w a v ec l u s t e r 算法，c l i q u e ( c l u s t e r i n gi nq u e s t ) 算法等。 s t i n g 算法 s t i n g ( s t a t i s t i c a li n f o r m a t i o ng r i d b a s e dm e t h o d ) l s s l 是一种使用层次统计 信怠的基予丽格的聚类算法，它利用索雩l 结构中的聚类信息，将空闻区域翔分 为不同级别分辨率的矩形单元，这些单元形成一个层次结构，商层的低分辨率 单元被划分为多个低一层的较高分辨率单元。从最底层的网格开始逐渐向上计 算网格内数据的统计信息并存储。两格的建立完成螽，就可以用类似d b s c a n 的方法对网格进行聚类。 同其他聚类方法相比，s t i n g 算法的优点为：该算法由于描述网格单元数 据统计信息是存储在相应单元中而与查询要求无关；网格结构有助子实现并行 运算和增量更新；算法仅扫描遍数据库，因此运算时间复杂度为0 秘，。但由 于该算法是利用多分辨率来完成聚类分析的，因此其聚类质量就依赖于网格结 构的最低层细度。另外该算法没有考虑子女与其父单元相邻单元在空间中的相 互关系，因此所获褥的聚类形状是直方的，也就是所有聚类的边界是水平的或 是垂直的，没有对角边界。虽然处理速度很快，但会降低聚类的质量和准确性。 该算法采用了基于密度的方法来形成聚类，所以与d b s c a n 一样能够处理噪 声。尽管它能够处理大量的数据，并且对噪声不敏感，但是，在处理高维数据 一2 5 浙江大学硕士学位论文 聚类融合算法研究及j e 在电信中的应用 时，性能会急剧降低。 w a v ec l u s t e r 算法 w a v ec l u s t e r l 3 6 1 是一种多分辨率的聚类算法，它首先通过在数据空间上强 加一个多维网格结构来汇总数据，然后采用一种小波变换来变换原特征空间， 在变换后的空间中找到密集区域。算法复杂度为d 伽，但随着数据维数的增加 而呈指数增长。这是一个基于网格和密度的算法，符合一个好的聚类算法的许 多要求：能有效的处理大数据集合，发现任意形状的簇，成功的处理孤立点， 对输入的顺序不敏感，不要求指定诸如结果簇的数目或邻域的半径等输入参数。 实验证明，该算法能够处理多于2 0 维的数据。 c l i q u e 算法 c l i q u e 3 7 1 ( c l u s t e r i n gi nq u e s t ) 算法是i b ma l m a d e n 研究院的一个数据 挖掘研究项目，是一种对高维数据集进行聚类的算法，既采用了基于密度的思 想，也采用了基于网格的思想。它提供“对高维数据的自动子空间聚类”，对于 大型数据库中的高维数据的聚类非常有效。其中心思想为：给定一个多维数据 点的大集合，数据点在数据空间中通常不是均衡分布的；如果一个单元中包含 的数据点超过了某个输入模型参数，则该单元是密集的。 c l i q u e 算法不需要事先对数据集的了解，不过，需要两个输入参数。它 能够有效处理噪声。但是，如果密度阈值过小，就会使有些噪声被识别为聚类。 聚类结果用d n f 和最小边界的长方体来描述。 m a f i a 算法 m a f i a ( m e r g i n go f a d a p t i v ef i n i t ei n t e r v a l s ) 是对c l i q u e 算法的改进， 与c l i q u e 算法相比，速度更快，聚类质量更好。主要改进之处是去掉了用于 限制待检查子空间数目的修剪技术，而采用了自适应的间隔大小，根据一个维 度上数据的分布对该维度进行分割。m a f i a 算法的运行速度比c u q u e 快4 4 倍，并且能够处理大型数据集和高维数据集。 5 ) 基于模型的方法( m o d e l b a s e dm e t h o d ) 基于模型的聚类方法试图优化给定的数据和某些数学模型之间的适应性。 这样的方法经常是基于这样的假设：数据是根据潜在的概率分布生成的。基于 模型的方法主要有两类：统计学方法和神经网络方法。 - - 2 6 - - 濒江大学矮七学位论文聚类融会舅法臻究及其在电翁孛戆痰耀 概念聚类是机器学习中的一种聚类方法，给出一组未标记的对象，它产生 对象的一个分类模式。概念聚类的绝大多数方法采用了统计学的途径，在决定 概念或聚类时使用概率度量。概念聚类是一个两步的过程：首先进行聚类，然 后给出特征攒述。在这墨，聚类质量不再只是单今对象的函数，两是加入了如 导出的概念描述的简单性和一般性因素。 c o b w e b 算法 + c o b w e b l 3 霹是一静流行的简单增量概念聚类算法。它的输入对象用分类属 性值对来描述。它是种针对分类属性数据的增量概念聚类算法。该算法以 一个分类树的形式创建层次聚类，并用一个启发式估算度量一分类效用来指导树 的构建。c o b w e b 假设在每个属性上的概率分布是独立的，实际中这个假设 并不总是成立。此终，聚类的概率分布表示使得更新和存储聚类有相当大的代 价，尤其当属性有大量的取值时，这种情况更为严重。 神经网络算法 神经网络方法将每个簇描述为一个标本( e x e m p l a r ) 。标本作为聚类的“原 型”，不一定对应一个特定的数据实例或对象。根据某些距离度量，新的对象可 以被分配给标本与其最相似的簇。被分配给一个簇的对象的属性可以根据该簇 的标本的属性来预测。 神经网络聚类有两个比较著名的方法：竞争学习( c o m p e t i t i v el e a r n i n g ) 和 自组织特征影射f 竣嗍( s e l f - o r g a n i z i n gf e a t u r em a p ，s o m ) ，这两种方法都涉及 有竞争的神经单元。竞争学习采用了若干个单元的层次结构( 或人群神经元) ， 它们以一种“胜者全取( w i n n e r - t a k e a 1 1 ) ”的方式对系统当前处理的对象进行 竞争。使用自组织特征影射的聚类方法也是通过若干个单元竞争当前对象来进 行的，只是权重设置有所调整；为更接近输入对象，对获胜单元及其最近的邻 居的权中进行了调整。s o m 假设在输入对象中存在一些拓扑结果或顺序，单元 将最终在空间中呈现这种结构。s o m 被认为类似予大脑的处理过程，对在二维 或三维空间中可视纯高维数撂是有用的。神经嬲络聚类方法与实际的大脑处理 有很强的理论联系。由于较长的处理时间和数据的复杂性，需要进行进一步的 研究来使它适用于大型数据库。 6 ) 孤立点分析( o u t l i e ra n a l y s i s ) 一2 7 浙江大学硕t ：学位论文聚类融合算法研究及j e 在电信中的应用 数据集中经常存在一些不符合数据的一般模型的数据对象，我们称之为孤 立点。孤立点可能是度量或执行错误所致，也可能是固有的数据变异性的结果。 许多数据挖据算法试图使孤立点的影响最小化或排除它们。但由于噪声与信号 的相对性，孤立点本身有可能包含重要的信息，因此在某些情况下，如金融和 商业欺诈检测，网络入侵异常监测等，孤立点分析就显示出重要的作用。 基于计算机的孤立点分析方法分为三类：统计学方法、基于距离的方法和 基于偏离的方法。 基于统计的孤立点分析对给定的数据集合假设了一个分布或概率模型，然 后根据模型采用不一致检验来确定孤立点。该检验要求知道数据集参数、分布 参数和预期的孤立点数目。主要缺点是绝大多数检验是针对单个属性的，而实 际中往往要求在多维空间中发现孤立点。而且在多数情况下，数据的分布是不 可知的。当没有特定的检验时，统计学方法不能确保所有的孤立点被发现，或 者观察到的分布不能恰当的被任何标准的分布来模拟。 为解决统计学方法的限制，引入基于距离的孤立点概念：如果数据集合s 中对象至少有p 部分与对象0 的距离大于d ，则对象0 是一个带参数p 和d 的基 于距离的( d b ) 的孤立点，即d b ( p , 讲。与基于统计的方法相比，基于距离的 孤立点