（计算机应用技术专业论文）聚类分析及聚类结果评估算法研究.pdf

东北大学硕士学位论文 摘要 聚类分析及聚类结果评估算法研究 摘要 随着信息技术的迅速发展，需要分析和管理的数据迅速增多，这种趋势已经 渗透到数据挖掘领域中。数据挖掘就是用来从大量的、不完全的、有噪声的、模 糊的、随机数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的 信息和知识。聚类分析是数据挖掘技术中重要的组成部分，从技术角度讲，它的 主要目的是将数据空间中的数据点划分到若干个类中。其中，将距离相近的数据 点划分到相同的类中，而将距离较远的数据点划分到不同的类中。 目前，已经提出了很多的聚类算法，它们基本上可以分为以下几种方法：划 分方法、层次方法、混合方法和基于密度等方法，这些方法各有优缺点。每种算 法只有聚类与之相适合的数据集时才能形成比较理想的聚类结果，而且聚类结果 的质量很难定量评估。虽然已经提出一些聚类质量评估的方法，但是这些评估方 法却不能与聚类算法有机结台，并指导聚类算法进行调整和更新以产生更好的聚 类结果。在聚类分析领域中另一个长期困扰研究者的典型问题就是聚类参数的设 置问题。只有合理的设置聚类参数才能聚类出高质量的聚类结果。然而被聚类的 数据集分布情况在聚类前往往是未知的，所以难以设置合理的聚类参数。而设置 不合理的聚类参数又使得聚类结果质量变低。所以聚类参数设置问题应该首先被 解决好。 本文提出一种高效的聚类模块和一种新颖的聚类质量评估模块。其中聚类模 块包含两个取值范围有限的整形参数，通过遍历这两个聚类参数的全部取值，可 以对数据集进行多遍聚类，然后利用评估模块对全部聚类结果进行评估，找到聚 类质量最高的一个作为聚类算法的最终输出，这就是s e c d u 算法。该算虽然可 以找到最优聚类，但是它的效率很低。通过爬山算法对s e c d u 进行优化，可以 得到s e c d u f 算法。无论是s e c d u 算法还是s e c d u f 算法，它们对具有不同分 布特性的数据集都有非常好的适应性，能够输出理想的聚类结果。而且s e c d u f 算法还具有聚类速度快、聚类参数自行调整，无需人工干预等优点。 关键词：聚类；密度单元：聚类质量：评估；爬山算法 变些查兰翌主兰竺丝查 垒! ! ! ! 竺 s t u d y o i lc l u s t e r i n g a n a l y s i sa n dc l u s t e r i n g r e s u l te v a l u a t i n g a l g o r i t h m s a b s t r a c t w i t ht h ef a s td e v e l o p m e n ti ni t , t h en e e do fa n a l y s i sa n dm a n a g eat r e m e n d o u s a m o u n to fd a t ab e c o m e sm o r ea n dm o r ei n s t a n t t h es a m es i t u a t i o ne x i s t si nd a t a m i n i n gf i e l dd a t am i m n gi san o n t r i v i a le x t r a c t i o np r o c e s so fi m p l i c i t ，p r e v i o u s l y u n k l l o w n ，a n dp o t e n t i a l l yu s e f u li n f o r m a t i o n c l u s t e ra n a l y s i si sap r i m a r ym e t h o df o r d a t am i n i n gt h em a i nt a s ko fc l u s t e ra n a l y s i si st op a r t i t i o nd a t ap o i n t si n t os e v e r a l c l u s t e r s d a t ap o i n t st h a ta r ec l o s et oe a c ho t h e rw i l lb es e n tt ot h es a m ec l u s t e ra n d d a t ap o i n t st h a tf a rf r o me a c ho t h e rw i l lb es e n tt od i f f e r e n tc l u s t e r s m a n yc l u s t e r i n ga l g o r i t h m sh a v eb e e np r o p o s e d , a n dt h e ya r ec l a s s i f i e di n t o s e v e r a lt y p e s ：p a r t i t i o n i n gt y p e ，h i e r a r c h yt y p e ，m i x e dt y p ea n dd e n s i t y - b a s e dt y p e t h e yh a v et h e i ro w n v i r t u e sa n dd i s a d v a m a g er e s p e c t i v e l y e a c ha l g o r i t h mi so n l yf i t f o rc e r t a i nd a t as e ta n di ti s v e r yh a r dt oe v a l u a t ee a c hc l u s t e r i n gr e s u l t n o t w i t h s t a n d i n g ，s o m ec l u s t e r i n gr e s u l te v a l u a t i n ga l g o r i t h m sc a nm e a s u r et h eq u a l i t y o fc l u s t e r i n gr e s u l t ，t h e yc a n n o ta d j u s ta n du p d a t ec l u s t e r i n ga l g o r i t h mt op e r f o r ma b e t t e rc l u s t e r i n go p e r a t i o ni na d d i t i o n ，at y p i c a lp r o b l e mi st h a ti ti sv e r yh a r dt ot u n e c l u s t e r i n gp a r a m e t e r sa p p r o p r i a t e l y t h ef i g u r e o fd a t as e ti su n k n o w nb e f o r e c l u s t e r i n go p e r a t i o na n dd i f f e r e n td a t as e tn e e dd i f f e r e n tp a r a m e t e r st oc l u s t e ri t i tw i l l o u t p u tal o wq u a l i t yc l u s t e r i n gr e s u l ti f u s e rs e tu n s u i t a b l ep a r a m e t e r sb e f o r ec l u s t e r i n g o p e r a t i o ns oi ti sc r u c i a lf o rc l u s t e r i n ga n a l y s i st os e l e c ta p p r o p r i a t ep a r a m e t e r s t h i st h e s i sp r o p o s e sa ne f f e c t i v ec l u s t e r i n gm o d ea n dan o v e lc l u s t e r i n gr e s u l t e v a l u a t i n gm o d e t h ec l u s t e r i n gm o d e h a st w oi n t e g r a lp a r a m e t e r s ，w h i c ha r eb e t w e e n z e r oa n dc e r t a i ni n t e g e r t h ee v a l u a t i n gm o d ee v a l u a t e sc l u s t e r i n gr e s u l t sp r o d u c e db y c l u s t e r i n gm o d ea n dg i v e se a c ham a r k w ec a na s s i g np a r a m e t e r sd i f f e r e n tv a l u ep a i r s t oc l u s t e rd a t as e tr e p e a t e d l ya n de v a l u a t ee a c hc l u s t e r i n gr e s u l t f i n a l l y , c h o s ea c l u s t e r i n gr e s u l tt h a th a st h eh i g h e s tm a r ka m o n g a l lt h eo n e st h i sa l g o r i t h mi sc a l l e d s e c d u a l t h o u g hs e c d uc a ng e tt h eb e s tc l u s t e r i n gr e s u l t ，t h ee f f i c i e n c y , h o w e v e r , i sv e r yl o wb e c a u s et h e r ea r eal o to fr o u n d so fc l u s t e r i n go p e r a t i o n si n v o l v e da n i m p r o v e da l g o r i t h mn a m e ds e c u d fc a ns o l v et h i sp r o b l e m i tc a nr e d u c ec l u s t e r i n g o p e r a t i o nt i m e sg r e a t l yb ya p p l y i n g “h i l l - c l i m b i n ga l g o r i f l u n ”b o t hs e c d ua n d s e c d u fc a nt u n ep a r a m e t e r sa u t o m a t i c a l l ya n do u t p u th i g hq u a l i t yc l u s t e r i n gr e s u l t ，1 1 i 东北大学硕士学位论文 a b s t r a c t f o rd i f f e r e n td a t as e t si na d d i t i o n ，s e c d u fh a sah i g hc l u s t e r i n gs p e e d k e yw o r d s ：c l u s t e r i n ga n a l y s i s ；d e n s i t yu n i t ；q u a l i t yo fc l u s t e r i n gr e s u l t ；e v a l u a t i n g ； h i l l c l i b m i n ga l g o r i t h m 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 意。 学位论文作者签名： 诩，街岳 日期：“2 乃 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名 签字日期： 导师签名： 签字日期： 东北大学硕士学位论文 第一章引言 第一章引言 随着信息技术的迅速发展，需要分析和管理的数据迅速增多。同时，计算机 与信息技术经历了半个世纪的发展，给人类社会带来了巨大的变化与影响，人们 能够以更快速、更容易、更廉价的方式获取和存储数据，这就使得数据及其信息 量以指数方式增长。一个中等规模企业每天要产生1 0 0 m b 以上来自各生产经营等 多方面的商业数据。美国政府部门的一个典型大数据库每天要接收约5 t b 数据量， 在1 5 秒到1 分钟时间里，要维护的数据量达到3 0 0 t b ，存档数据达1 5 p b 1 0 0 p b 1 。 而且这些数据包含多方面的数据，如图像、空间等数据。然而，这些数据并未得 到充分的利用，要从这些数据中提取出有用的知识，并应用到现实生活中，单靠 统计等方法已显得力不从心。于是人们便希望能够利用计算机来处理这些数据， 提取出隐含在数据中的对人们有用的规律，一种新兴的学科便出现了，即数据挖 掘口，”。在这十几年的发展历程中，它取得了一定的成效，成果已经成功地运用在 各种商业系统中，帮助人们从海量的数据中提取出有用的信息来辅助管理和支持 决策，极大地提高了人们的生产效率。 股票经纪人需要从日积月累的大量股票行情变化的历史记录中发现其变化规 律，以供预测未来趋势；超级市场的经理人员希望能够从过去几年的销售记录中 分析出顾客的消费习惯和行为，以便及时变换营销策略；地质学家想通过分析地 球资源卫星发回的大量数据和照片来发现有开采价值的矿物资源等。有一个很普 通却很能说明数据挖掘如何产生效益的例子 4 1 ：美国加州某个超级连锁店通过数据 挖掘，从记录着每天销售信息和顾客基本情况的数据库中发现，在下班后前来购 买婴儿尿布的顾客多数是男性，而且往往也同时购买啤酒。于是这个连锁店的经 理当机立断，重新布置了货架，把啤酒类商品布置在婴儿尿布货架附近，并在二 者之间放上土豆之类的佐酒小食品，同时把男士们需要的日常生活用品也就近布 置。这样一来，上述几种商品的销量大增。 通过上面的例子可以看出，数据挖掘能为决策者提供重要的、极有价值的信 息或知识，从而产生不可估量的效益。因此，虽然数据挖掘产品尚不成熟，但其 市场份额却正日益扩大，越来越多的大中型企业开始利用数据挖掘来分析公司的 数据以辅助决策，数据挖掘正逐渐成为在市场竞争中立于不败之地的法宝。 1 1 什么是数据挖掘 数据挖掘( d m ，d a t a m i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、 随机数据中，提取隐含在其中的，人们事先不知道的、但又是潜在的有用信息和 知识的过程 5 o 人们把原始数据看作是形成知识的源泉，就像从矿石中采矿一样。数据挖掘 东北大学硕士学位论文 第一章 【言 所依赖的原始数据来源多种多样，可以是常用的关系数据库、事务数据库、文本 数据库、多媒体数据库等，主要取决于用户的目的及所处的领域。目前，数据挖 掘的数据主要取自关系数据库与数据仓库。原始数据可以是结构化的，如关系数 据库中的数据，也可以是半结构化的，如文本、图形、图像数据，甚至是分布在 网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的：可以 是演绎的，也可以是归纳的。发现的知识可以被用于信息管理、查询优化、决策 支持、过程控制等，还可以用于数据自身的维护。 统计数据证明：数据挖掘能够给企业构建竞争优势并带来巨大的经济效益”j 。 过去的几年里，在关系数据库中的知识发现取得了丰硕的成果，已经开发了很多 数据挖掘系统，如：i n t e l l i g e n tm i n e r ( q u e s t ) ，m i n e s e t ，d b m i n e r , i m a c s ，s k i c a t , e x p l o r e 等己经在大型的数据库和数据仓库系统中使用的软件h 一1 。数据挖掘是一个 应市场需求而生的学科，又是一个多学科相互融合相互渗透而产生的交叉学科。 数据库技术、机器学习、统计技术、信息科学的发展为数据挖掘的诞生奠定了理 论基础，不可限量的市场需求为数据挖掘的发展提供了广阔的空间口j 。 特别指出的是，数据挖掘技术从一开始就是面向应用的。它不仅是面向特定 数据库的简单检索查询调用，而且要对这些数据进行微观或宏观的统计、分析、 综合和推理，以指导实际问题的求解，企图发现事件闻的相互关联，甚至利用已 有的数据对未来的活动进行预测。例如，加拿大b c 省电话公司要求加拿大s i m o n f r a s e r 大学数据挖掘研究组，根据其拥有的十多年的客户数据，总结、分析并提出 新的电话收费和管理办法，制定既有利于公司又有利于客户的优惠政策。美国n b a 的著名篮球队的教练，利用m m 公司提供的数据挖掘技术，临场决定替换队员， 一度在数据库领域中传为佳话。这样一来，就把人们对数据的应用，从低层次的 末端查询操作，提高到为各级经营决策者提供决策支持。 当今数据库的容量己经达到上万亿的水平。在这些大量数据的背后隐藏了很 多具有决策意义的信息，那么怎么得到这些“知识”呢? 计算机科学对这个问题 给出的最新回答就是数据挖掘，在“数据矿山”中找到蕴藏的“知识金块”。数据 挖掘是一个利用各种分析工具在海量数据中发现模型和数据间关系的过程，这些 模型和关系可以用来做出预测。 数据挖掘的第一步是描述数据计算统计变量( 比如平均值、均方差等) ， 再用图表或图片直观地表示出来，进而可以看出一些变量之间的相关性。 单单是数据描述并不能为人们制定行动计划提供足够的依据，必须用这些历 史数据建立一个预言模型，然后再用另外一些数据对这个模型进行测试，一个好 的模型没必要与数据库中的数据1 0 0 的相符( 城市交通图也不是完全的实际交 通线路的等比缩小) ，但它在做决策时是一个很好的依据。 最后一步是验证模型。比如用所有对产品推广计划做出回应的人的数据库做 了一个模型，来预测什么样的人会对产品感兴趣。是在得到这个模型后就直接利 2 东北大学硕士学位论文第一章引言 用这个模型做出决策或采取行动呢? 还是更稳妥一点先对- 4 , 部分客户做一个实 际的测试，然后再决定。 数据挖掘是一个工具，而不是有魔力的权杖。它不会坐在数据库上一直监视 数据库，然后当它发现有意义的模型时发一封电子邮件。它仍然需要了解业务， 理解数据，弄清分析方法。数据挖掘只是帮助商业人士更深入、更容易地分析数 据，它无法告诉某个模型对企业的实际价值，而且数据挖掘中得到的模型必须要 在现实生活中进行验证。 1 2 数据挖掘功能 数据挖掘能够帮助企业确定客户的特点，从而可以为客户提供有针对性的服 务。通过数据挖掘，可以发现购买某一商品的客户的特征，从而可以向那些也同 样具有这些特征却没有购买的客户推销这个商品；若找到流失的客户的特征，就 可以在那些具有相似特征的客户还未流失之前，采取针对性的措施。 1 。2 1 客户细分 根据计费帐务系统中的用户资料及帐单信息，以预设用户模型为线索，整理出 用户的背景属性、行为属性、帐务属性、客户扩展属性等信息。采用客户分类模 型和客户价值评估模型通过分类分析法和聚类分析法对客户分群，同一群中的客 户具有最大的相似性，不同群的客户具有最大的差异性。通过分群，使企业对客户 总体构成有准确认识，对客户的服务和营销更具针对性。 12 2 交叉销售分析 根据计费帐务系统的用户资料信息、产品使用信息及业务使用信息，以用户 为线索，整理出用户的相关属性信息、各项产品使用与否的信息、各项业务是否零 业务量的信息等。采用交叉销售模型，以全部数据作为样本，分析各项产品与业 务的关联程度，挖掘发现用户使用各项业务产品的内在隐含关联关系，以便推出 各种交叉销售或者套餐服务策略，达到以低成本获得高收益的目标。 1 2 3 客户流失分析 客户流失特征分析：根据计费帐务系统的用户资料及帐单信息，以用户为线 索，分析拆机客户的资料，列出流失客户的通信量、抱怨情况、促销活动、渠道 及生命周期。采用响应度模型，抽样1 0 左右的数据作为样本，其中一半作为训 练模型使用，另一半用来检验模型的运算结果与实际情况是否接近，然后根据挖 掘结果，列出客户的流失率与增加率，分析发现将要拆机的客户及客户拆机的原 因。 流失客户特征分析：由于在市话、i p 电话、公共电话等业务领域的竞争激烈， 3 东北大学硕士学位论文 第一章引言 客户流失情况往往很严重，此时分析价值高而又容易流失的客户的特征，可以为 市场获得提供依据，以便分别采取不同的营销策略，从而提高自身竞争力和争夺 市场。根据计费帐务系统的用户资料及帐单信息、网间结算系统的i p 业务使用信 息，以用户为线索，整理出用户的相关属性信息、历史消费情况、历史相关业务 使用情况、本帐期业务量数据等，然后使用响应度模型和客户分类模型对客户流 失的可能性进行预测，最后抽取业务量大、流失可能性高的客户进行分析。 12 4 客户流失预测 以计费客户资料和结算话单为基础数据，结合o l a p 的客户流失分析的中间 结果，以及流失客户特征分析的结果，采用时间序列递归算法，使用不同大小的 时间窗e l 对算法模型进行训i 练，并用历史数据进行检验，最终确定合适的时间窗 口参数，从流失的客户总数、网上有效通话客户数、欠费客户数、零次客户数四 个方面，对客户流失情况进行分析预测。 1 2 5 竞争对手发展情况预测 以计费客户资料和结算话单为基础数据，结合o l a p 的用户数竞争分析的中 间结果，采用时间序列递归算法，使用不同大小的时间窗n 对算法模型进行训练， 并用历史数据进行检验，最终确定合适的时间窗口参数，从对手客户发展情况、 对手客户话费收入情况、对手客户呼叫行为三个方面，对竞争对手发展情况进行 分析预测，实现预测。 1 3 聚类算法研究面临的挑战 聚类算法研究是一个具有很强挑战性的研究领域，它的一些潜在应用对聚类 算法提出了特别的要求： ( 1 ) 可伸缩性( s e a l a b i l i t y ) ，实际应用要求聚类算法能够处理大数据集，且时 间复杂度不能太高( 最好是多项式时间) ，消耗的内存空间也有限。目 前，为了将算法拓展到超大数据库( v l d b ) 领域，研究人员己经进行了许 多有益的尝试，包括：增量式挖掘、可靠的采样、数据挤压( d a t as q u a s h i n g ) 等。其中，数据挤压技术首先通过扫描数据来获得数据的统计信息，然 后在这些统计信息的基础上进行聚类分析。比如b i r c h 算法中使用c f 树就是属于数据挤压技术。 ( 2 )能够处理不同类型的属性：现实中的数据对象己远远超出关系型数据的 范畴，比如空间数据、多媒体数据、遗传学数据、时间序列数据、文本 数据、万维网上的数据、以及目前逐渐兴起的数据流。这些数据对象的 属性类型往往是由多种数据类型综合而成的。 f 3 )能够发现任意形状的簇。 4 东北大学硕士学位论文第一章；i 言 ( 4 )尽量减少用于决定输入参数的领域知识。 ( 5 )能够处理噪声数据及孤立点。 ( 6 )对输入数据记录的顺序不敏感。 ( 7 ) 高维性( h i g h ，d i m e n s i o n a l ) ，一个数据集可能包含若干个维。较高的维数 给聚类分析带来两个问题：首先，不相关的属性削弱了数据会聚的趋势， 使得数据分布非常稀疏。尽管这种情况在低维空间中并不多见，但是随 着维数的增加，不相关属性的出现概率及数量也会增加，最后导致数据 空间中几乎不存在簇。其次，高维使得在低维中很有效的区分数据的标 准在高维空间中失效了。譬如在高维空间中，数据点到最近邻点的距离 与到其他点的距离没有多少分别，从而导致最近邻查询在高维空间中不 稳定，此时若根据接近度来划分簇，结果是不可信的。 ( 8 )能够根据用户指定的约束条件进行聚类。 f 9 )聚类结果具有可解释性和可用性。 上述的要求使目前聚类算法研究的热点集中到了研究有效适用于大型数据库 的可伸缩性聚类算法、能够识别复杂形状的簇的聚类算法、高维聚类分析算法以 及针对大型数据库中混合数值的聚类算法。 1 4 数据挖掘的分类 数据挖掘涉及的学科领域和方法很多，有多种分类法。根据挖掘任务，可分 为分类或预测模型发现、数据总结、聚类、关联规则发现、序列模式发现、依赖 关系或依赖模型发现、异常和趋势发现等。根据挖掘对象分，有关系数据库、面 向对象数据库、空间数据库、时态数据库、文本数据库、多媒体数据库、异构数 据库、遗产数据库以及w e b 。根据挖掘方法，可分为判定树( d e c i s i o nt r e e ) “、 c c a s ( “1 、贝叶斯分类算法f b a y e s i a nc l a s s i c a t i o n ) 、后向传播算法 f b a c k p r o p a g a t i o n ) ，k - 最临近分类算法( k - n e a r e s tn e i g h b o rc l a s s i f i e r s ) 、基于案 例的推理_ ( c a s e - b a s e dr e a s o n i n g ) 、遗传算法( g e n e t i ca l g o r i t h m s ) 1 1 2 1 粗糙集算法 ( r o u g hs e t a l g o r i t h m s ) 、模糊集算法( f u z z ys e t a p p r o a c h e s ) 、神经网络【l 等。另外， 挖掘也可根据其应用分类，例如，可能有些数据挖掘特别适合金融、电信、d n a 、 e 。m a i l ，等等。不同的应用通常需要集成对该应用特别有效的方法，普通的、全能 的数据挖掘可能井不适合特定领域的挖掘任务。 数据挖掘所能发现的知识有如下几种：广义型知识，反映同类事物共同性质 的知识；特征型知识，反映事物各方面的特征知识；差异型知识，反映不同事物 之间属性差别的知识：关联型知识，反映事物之间依赖或关联关系的知识；预测 型知识，根据历史的和当前的数据推测未来数据；偏离型知识，揭示事物偏离常 规的异常现象。所有这些知识都可以在不同的概念层次上被发现，随着概念树的 提升，从微观到宏观，以满足不同用户、不同层次决策的需要。例如，从一家超 5 东北大学硕士学位论文 第一章引言 市的数据仓库中，可以发现的一条典型关联规则可能是“买面包和黄油的顾客十 有八九也买牛奶”，也可能是“买食品的顾客几乎都用信用卡”，这种规则对于 商家开发和实施客户化的销售计划和策略是非常有用的。 14 1 分类分析 分类就是找出一组能够描述数据集合典型特征的模型，以便能够将未知的数 据进行归类。分类模型可以通过分类挖掘算法从一组训练样本数据中( 其类别归 属已知) 中学习获得。分类挖掘所获的分类模型可以采用多种形式加以描述输出， 其中主要方法有分类规则( i f t h e n ) 、决策树、数学公式和神经网络。决策树是 一个具有层次结构的树状结构。 例如，想获得人们的信誉程度( 良好、普通、较差) ，要对人们进行归类，则 可利用决策树方法先对预先归类的数据进行挖掘，找出其模式。一棵典型的决策 树如图1 1 所示。图中的每个分支对应一种情况，而分支的形态是由设计者决定的。 月收入 s 良好普通 图1 1 决策树举例 f i g u r e1 1s a m p l e - d e c i s i o nt r e e 决策树的特点如下：通过把实例从根节点排列到某个叶子节点来分类实例； 叶子节点即为实例所属的分类；树上每个节点说明了对实例的某个属性的测试； 节点的每个后继分支对应于该属性的一个可能值。决策树具有以下优点：可以生 成可以理解的规则：计算量相对来说不是很大；可以处理连续和种类字段；决策 树可以清晰的显示哪些字段比较重要。 决箫树往往可以与一段i f t h e n 代码相对应。表11 中描绘了图1 1 对应的条 件语句。 6 东北大学硕士学位论文 第一章引言 表1 1 决策树举例 t a b l e1ie x a m p l eo f d e c i s i o nt r e e 月收入 s 不是居住在a 城市 月收入 s 居住在a 城市 信誉较差 信誉普通 信誉良好 142 聚类分析 聚类用于从数据集中找出相似的数据并组成不同的组。对象根据最大化类内 的相似性、最小化类间的相似性的原则进行聚类或分组。即对象的类这样形成， 使得在一个类中的对象具有很高的相似性，而与其他类中的对象很不相似。与预 测模型不同，聚类中没有明显的目标变量作为数据的属性存在。有很多方法可使 数据分类，公认的常用方法包括k m e a n s 算法l l “”j 、分层凝聚法( h i e r a r c h i c a l a g g l o m e r a t i v em e o t h o d s ) 及采用估算最大值法 ( e s t i m a t i o nm a x i m i z a t i o n a l g o r i t h m ) 使适应数据可能的混合模型。 1 43 关联分析 在数据挖掘的研究领域，关联规则的挖掘有着广泛的应用背景，对于关联规 则挖掘的研究开展的比较积极和深入。关联规则最初起源于对超级市场的“购物 篮问题的研究”1 4 1 。关联规则是描述数据库中数据项之间某种潜在关联关系的规 则( 同时发生或者从一个对象推出另一个) 。 通常关联规则具有如下形式：x y ，即“a 1 a 2 a 一岛k a b n ”； 其中，a ，i 1 ，2 川，m 和b ， 1 ，2 ，n 为属性。关联规则x y 表 示事物数据库中满足条件x 的事物在某种程度上也满足条件y 。 该项应用最早挖掘出的关联规则就是“啤酒和尿布问题”： 年轻父亲+ 啤酒一尿布( s u p p o r t = 3 0 ，c o n f i d e n c e = 7 0 ) 上述规则表示：该商场中是年轻父亲，且同时购买啤酒和尿布的占3 0 ，年 轻父亲买啤酒的同时有7 0 的可能性买尿布。 关联规则就是辨别这些交易项目之间是否存在某种关联关系。这种关联规则 提供的信息可以用作商品销售目录设计、商场布置、生产安排、针对性的市场营 销等。 1 4 4 序列分析 描述行为随时间变化的对象的规律或趋势，并对其建模。序列分析和时间序 列说明数据中的序列信息和与时间相关的序列分析。其中包括时间相关数据的特 征化、区分、关联、分类或聚类，但这类分析的不同特点包括时间数据分析、序 7 东北大学硕士学位论文 第一章引言 列或周期模式匹配和基于相似性的数据分析。 145 孤立点分析 任何事物都要一分为二来看，正如一条一个人认为是垃圾的信息对另一个人 是如获至宝。孤立点是实际生活中的反常行为的写照。用距离的观点来看，孤立 点就是那些离密度较高的大部分点较远的点。孤立点分析可以使用统计试验检测 或基于偏差的方法。 1 5 数据挖掘的过程 数据挖掘的过程可粗略地分为：问题定义( t a s kd e f i n i t i o n ) 、数据收集和预 处理( d a t a p r e p a r a t i o na n d p r e p r o c e s s i n g ) 、数据挖掘( d a t a m i n i n g ) 算法执行以 及结果的解释和评估( i n t e r p r e t a t i o n a n d e v a l u a t i o n ) 。整个过程如图1 2 所示。 图12 数据挖掘过程 f i g u r e l2t h ep f o c e s so f d a t am i n i n g 1 5 1 问题定义 数据挖掘是为了在大量数据中发现有用的令人感兴趣的信息，因此发现何种 知识就成为整个过程中第一个也是最重要的一个阶段。在问题定义过程中，数据 挖掘人员必须和领域专家以及最终用户紧密协作，一方面明确实际工作对数据挖 掘的要求：另一方面通过对各种学习算法的对比进而确定可用的学习算法。后续 的学习算法选择和数据集准备都是在此基础上进行的。 1 52 数据收集和数据预处理 数据准备又可分为三个子步骤：数据选取( d a t as e l e c t i o n ) 、数据预处理( d a t a p r e p r o c e s s i n g ) 和数据变换( d a t a t r a n s f o r m a t i o n ) 。 数据选取的目的是确定发现任务的操作对象，即目标数据( t a r g e td a t a ) ，是 8 东北大学硕士学位论文 第一章引言 根据用户的需要从原始数据库中抽取的一组数据。数据预处理一般可能包括消除 噪声、推导和计算缺值数据、消除重复记录、完成数据类型转换( 如把连续值数 据转换为离散型的数据，以便于符号归纳，或是把离散型的转换为连续值型的， 以便于神经网络) 等。当数据挖掘的对象是数据仓库时，一般来说，数据预处理 已经在生成数据仓库时完成了。数据变换的主要目的是消减数据维数或降维 ( d i r a e n s i o n r e d u c t i o n ) ，即从初始特征中找出真正有用的特征，以减少数据挖掘 时要考虑的特征或变量个数。 15 3 数据挖掘 数据挖掘算法执行阶段首先根据对问题的定义明确挖掘的任务或目的，如分 类、聚类、关联规则发现或序列模式发现等。确定了挖掘任务后，就要决定使用 什么样的算法。选择实现算法有两个考虑因素：一是不同的数据有不同的特点， 因此需要用与之相关的算法来挖掘；二是用户或实际运行系统的要求，有的用户 可能希望获取描述型的( d e s c r i p t i v e ) 、容易理解的知识( 采用规则表示的挖掘方 法显然要好于神经网络之类的方法) ，而有的用户只是希望获取预测准确度尽可能 高的预测型( p r e d i c t i v e ) 知识，并不在意获取的知识是否易于理解。 15 4 结果解释和评估 数据挖掘阶段发现出来的模式，经过评估，可能存在冗余或无关的模式，这 时需要将其剔除：也有可能模式不满足用户要求，这时则需要整个发现过程回退 到前一阶段，如重新选取数据、采用新的数据变换方法、设定新的参数值，甚至 换一种算法等。另外，数据挖掘由于最终是面向人类用户的，因此可能要对发现 的模式进行可视化，或者把结果转换为用户易懂的另种表示，如把分类决策树 转换为“i ft h e n ”规则。 数据挖掘算法执行，仅仅是整个过程中的一个步骤。数据挖掘质量的好坏有 两个影响要素：一是所采用的数据挖掘技术的有效性；二是用于挖掘的数据的质 量和数量( 数据量的大小) 。如果选择了错误的数据或不适当的属性，或对数据 进行了不适当的转换，则挖掘的结果不会好的。整个挖掘过程是一个不断反馈的 过程。比如，用户在挖掘途中发现选择的数据不太好，或使用的挖掘技术产生不 了期望的结果，这时，用户需要重复先前的过程，甚至从头重新开始。 为了有效的数据挖掘，还需要考虑应用的数据挖掘系统所期望的特性，另外 要知道数据挖掘发展面i 临着一些挑战，如处理不同种类的数据、数据挖掘算法的 效率及扩展性，数据挖掘结果的可用性、确定性及可表达性，各种数据挖掘结果 的表达，多抽象层交互挖掘知识，从不同的数据源中挖掘信息，隐私保护及数据 安全等。 数据挖掘是由多种技术综台在一起实现的，互相依赖又互不相同。每一种数 9 东北大学硕士学位论文 第一章孑| 言 据挖掘的方法都有很多方面有待研究，而本文主要就聚类分析这一方面展开讨论。 1 0 东北大学硕士学位论文 第= 章研究现状 第二章研究现状 聚类分析是数据挖掘技术中重要的组成部分，它能够在潜在的数据中发现令 人感兴趣的数据分布模式【l “。从技术角度讲，它的主要目的是将数据空间中的数 据点划分到若干个类中，其中将距离相近的数据点划分到相同的类中，而将距离 较远的数据点划分到不同的类中。它是在无监督的情况下根据定的相似性或距 离计算函数自动的将数据集分成若干类。聚类所采用的方法主要有划分方法、层 次方法、基于网格的方法、基于模型的方法、基于密度的方法这几类。 2 1 问题定义 聚类( c l u s t e r i n g ) 就是将物理或抽象对象的集合分组成为由类似的对象组成 的多个类的过程。由聚类生成的类是一组数据对象的集合，这些对象与同一个类 中的对象彼此相似，与其它类中的对象相异u 。相异度是根据描述对象的属性值 来计算的，距离是经常采用的度量方式。 在数据挖掘中，聚类分析( 无监督分类) 与分类分析( 有监督分类) 之间是 有联系的也是有区别的。它们都是将未知模式的数据集分成若干个类。但通常， 为有监督分类提供若干己标记的对象( 预分类过) ，需要解决的问题是为一个新遇 到的但无标记的对象进行标记。在典型的情况下，先将给定的无标记的模式用来 学习( 训练) ，反过来再用来标记一个新模式。聚类需要解决的问题是将己给定的 若干无标记的对象聚集起来使之成为有意义的聚类。从某种意义上说，标记也与 聚类相关，但这些类型的标记是由数据驱动的，也就是说，只是从数据中得到这 些标记。聚类与数据挖掘中的分类不同，在分类模块中，对于目标数据库中存在 哪些类是知道的，要做的就是将每一条记录分别属于哪一类标记出来；与此相似 但又不同的是，聚类是在预先不知道目标数据库到底有多少类的情下，希望将所 有的记录组成不同的类，并且使得在这种分类情况下，以某种度量为标准的相似 性，在同一聚类之间最小化，而在不同聚类之间最大化。 聚类在以下几个领域中是非常有用的：模式分析的浏览、聚集、决策制定及 机器学习，还包括数据挖掘、文件恢复、图像分割及模式分类。但在这些问题中， 几乎没有有关数据的先验信息( 如统计模型) 可用，而用户又要求尽可能地对数 据的可能性少进行假设。在这些限制条件下，聚类方法特别适合于查看数据点中 的内在关系以对它们的结构进行评估。 聚类的用途是很广泛的。在商业上，聚类可以帮助市场分析人员从消费者数 据库中区分出不同的消费群体来，并且概括出每一类消费者的消费模式或者说习 惯；在生物学中，它可以被用来辅助研究动、植物的分类，可以用来分类具有相 似功能的基因，还可以用来发现人群中的一些潜在的结构等；聚类还可以用来从 东北大学硕士学位论文 第= 章研究现状 地理数据库中识别出具有相似土地用途的区域i 可以从保险公司的数据库中发现 汽车保险中具有较高索赔概率的群体；还可以从一个城市的房地产信息数据库中， 根据房型、房价及地理位置分成不同的类；还可以用来从万维网上分类不同类型 的文档等。同时，聚类分析作为数据挖掘中的一个模块，它可以作为一个单独的 工具以发现数据库中数据分布的一些深层的信息，并且概括出每一类的特点，或 者把注意力放在某一个特定的类上以作进一步的分析；聚类分析也可以作为数据 挖掘算法中其他分析算法的一个预处理步骤。但大部分涉及聚类的实际问题是多 维的，直观地去解释多维空间嵌入的数据是非常困难的问题。 2 2 聚类分析算法的分类 聚类分析的算法可以分以下几大类：划分法、层次法、基于密度的方法、基 于网格的方法和基于模型的方法等。 划分方法( p a r t i t i o n i n gm e t h o d ) 给定一个有n 个元组或者记录的数据集，划分方法将构造k 个分组，每一个 分组就代表一个聚类，k n 。而且这k 个分组满足下列条件： f 1 )每一个分组至少包含一个数据记录： ( 2 )每一个数据记录属于且仅属于一个分组。 对于给定的k ，算法首先给出一个初始的分组方法，以后通过反复迭代的方 法改变分组，使得每一次改进之后分组方案都较前一次好，而所谓“好”的标准 就是同一分组中的记录越近越好。而不同分组中的记录越远越好。使用这个基本 思想的算法有k - m e a n s 算法1 5 , 16 1 、k - m e d o i d s 算法【1 9 】、c l a r a n s 算法【2 0 】。 ( 1 )层次方法( h i e r a r c h i c a lm e t h o d ) 这种方法对给定的数据集进行层次的分解，直到某种条件满足位置。具体又 可分为“自底向上”和“自顶向下”两种方案。代表算法有：b i r c h 算法口1 i 、 c u r e 算法、c h a m e l e o n 算法1 2 ”、c a c t u s 算法【2 4 1 等。 f 2 )基于网格的方法( g r i d b a s e dm e t h o d ) 这种方法首先将数据空间划分成为有限个单元( c e l l ) 的网格结构，所有的 处理都是以单个单元为对象的。这样处理的一个突出的优点就是处理速度很快， 通常与目标数据库中记录的个数无关，它只与把数据空间分为多少个单元有关。 代表算法有：s t i n g 算法、c l i q u e 算法口”、w a v e c l u s i e r 算法【”1 。 ( 3 )基于模型的方法( m o d e l b a s e d m e t h o d ) 基于模型的方法给每一个聚类假定一个模型，然后去寻找能够很好的满足这 个模型的数据集口“。这样一个模型可能是数据点在空间中的密度分布函数或者其 他。它的一个潜在的假定就是：目标数据集是由一系列的概率分布所决定的。通 常有两种方法：统计的方法和神经网络的方法。 ( 4 1