（计算机应用技术专业论文）面向电子商务的数据挖掘中聚类算法的研究.pdf

重庆邮电大学硕士论文 摘要 摘要 在信息和知识经济时代伴随着计算机技术和网络技术的不断发展，企 业纷纷建立自己的商务网站，开展电子商务活动，日积月累网站上生成了 大量的与客户有关的记录信息，这些信息对企业来说应该是一笔非常宝贵 的财富，如果能得到充分挖掘，发现背后蕴涵的有用知识，为企业业务决 策和战略发展服务，企业将会在市场竞争中占据有利地位，应运而生的数 据挖掘技术给出了有效的解决方法，它能够对大量的、不完全的、有噪声 的、模糊的、随机的数据进行挖掘，提取隐含在其中的、事先不知道但又 是潜在有用的信息和知识。而聚类分析是数据挖掘技术中重要的组成部 分，从技术角度讲，它的主要目的是将数据空间中的数据点划分到若干个 类中。其中，将距离相近的数据点划分到相同的类中，而将距离较远的数 据点划分到不同的类中。 目前，已经提出了很多的聚类算法，它们基本上可以分为以下几种方 法：划分方法、层次方法、基于密度、基于网格和混合方法等方法，这些 方法各有优缺点。本文通过分析基于网格与基于密度的聚类算法特征，提 出了一种基于网格和密度的混合聚类算法，通过分阶段聚类并选取代表单 元中的种子对象来扩展类，从而减少区域查询次数，实现快速聚类。该算 法保持了基于密度的聚类算法可以发现任意形状的聚类和对噪声数据不 敏感的优点，同时保持了基于网格的聚类算法的高效性，适合对大规模数 据的挖掘，并且实验数据分析验证了算法的有效性。 在聚类分析领域中另一个长期困扰研究者的典型问题就是聚类参数 的设置问题。只有合理的设置聚类参数才能聚类出高质量的聚类结果。然 而被聚类的数据集分布情况在聚类前往往是未知的，所以难以设置合理的 聚类参数。而设置不合理的聚类参数又使得聚类结果质量变低。所以聚类 参数设置问题应该首先被解决好。本文对网格聚类算法进行了深入地分析 研究。在研究了传统网格聚类算法的基础上，针对网格聚类算法对参数敏 感的问题，提出了一种基于网格的参数自动化聚类算法，该算法使用参数 自动化技术解决了算法对参数敏感的问题。并在综合数据集和真实数据集 上进行测试，最后给出实验结果，同时分析了该算法的时间复杂度和空间 复杂度。 关键词：数据挖掘，聚类，网格聚类，密度单元，参数自动化 重庆邮电大学硕士论文摘要 a b s t r a c t i nt h ee r ao fi n f o r m a t i o na n dk n o w l e d g e - b a s e de c o n o m y ，a l o n gw i t ht h e c o n s t a n t d e v e l o p m e n t o f c o m p u t e r a n dn e t w o r k t e c h n o l o g y b u s i n e s s e n t e r p r i s e s h a v es e tu pt h e i ro w nw e b s i t e s ，d i de c o m m e r c ea c t i v i t i e s a c c u m u l a t ew e b s i t eg e n e r a t e dal o to fi n f o r m a t i o na n dr e c o r d sr e l a t i n gt o c l i e n t s i n f o r m a t i o no nt h e s ee n t e r p r i s e ss h o u l db ea ne x t r e m e l yv a l u a b l ea s s e t i ft h a tc a nb ef u l l yt a p p e d i m p l i c a t i o nf o u n db e h i n dt h eu s e f u lk n o w l e d g ef o r d e c i s i o n - m a k i n ga n ds t r a t e g i cb u s i n e s sd e v e l o p m e n ts e r v i c e s ，w i l lb e i na f a v o r a b l ep o s i t i o ni nm a r k e tc o m p e t i t i o n ，t h er e q u i r e m e n to ft h ed a t am i n i n g t e c h n o l o g yg i v e sa ne f f e c t i v es o l u t i o n i ti sc a p a b l eo fl a r g e 、i n c o m p l e t e 、 n o i s y 、f u z z y 、r a n d o md a t at od od a t am i n i n g ，e x t r a c tt h ei m p l i c i t 、p r e v i o u s l y u n k n o w n 、b u tp o t e n t i a l l yu s e f u li n f o r m a t i o na n dk n o w l e d g e t h e nc l u s t e r a n a l y s i s i sa p r i m a r ym e t h o df o rd a t am i n i n g t h em a i nt a s ko fc l u s t e r a 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 lc l u s t e r s d a t ap o i n t st h a ta r e c 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 dd a t ap o i n t st h a tf a r f 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 el a s s i f i e d i n t os 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 ，d e n s i t y b a s e dt y p e ， g r i d b a s e dt y p e a n dm i x e d t y p ee t c t h e y h a v et h e i ro w nv i r t u e sa n d d i s a d v a n t a g er e s p e c t i v e l y g r o u n d i n g o nt h e a n a l y s i s o ff e a t u r e so f g r i d b a s e d a n d d e n s i t y b a s e dc l u s t e r i n g m e t h o d s ，ah y b r i d c l u s t e r i n g a l g o r i t h mb a s e do ng r i da n dd e n s i t yw a sp r e s e n t e d b yc l u s t e r i n gi nt w o p h a s e sa n du s i n go n l yas m a l ln u m b e ro fs e e do b j e c t si nr e p r e s e n t a t i v eu n i t s t oe x p a n dt h ec l u s t e r ，t h ef r e q u e n c yo fr e g i o nq u e r yc a nb ed e c r e a s e d ，a n d c o n s e q u e n t l yt h ec o s to ft i m ei sr e d u c e d a ne q u i v a l e n tr u l ew a sp r o p o s e dt o m a k es m o o t hc o n v e r s i o nb e t w e e n c l u s t e r i n gp a r a m e t e r s i nt h a tt w o p h a s e s t h ea l g o r i t h mk e e p sg o o df e a t u r e o fb o t h d e n s i t y b a s e d a n d g r i d b a s e dc l u s t e r i n gm e t h o d s i tc a nd i s c o v e rc l u s t e r sw i t ha r b i t r a r ys h a p e w i t hh i g he f i c i e n c ya n di si n s e n s i t i v et on o i s e s oi ti s a p p l i c a b l ef o rd a t a m i n i n go nl a r g ed a t a b a s e t h ea p p l i c a t i o no ft h eh y b r i da l g o r i t h mi nd a t a a n a l y s i so fa c e e l e r o m e t e rd e m o n s t r a t e si t se f e c t i v e n e s s i 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 tis v e r yh a r dt ot u n ec l u s t e r i n g 重庆邮电大学硕士论文 摘耍 p 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 eo 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 r i t i tw i l l o u t p u t al o wq u a l i t y c l u s t e r i n g r e s u l ti fu s e rs e tu n s u i t a b l e p a r a m e t e r sb e f o r ec l u s t e r i n go p e r a t i o n s 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 s t 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 i nt h i st h e s i s ，t h ea u t h o rp r e s e n t st h et h e o r yo fd a t am i n i n g ，a n dd e e p l y a n a l y z e st h ea l g o r i t h m so fg r i dc l u s t e r i n g b a s e d0 nt h a tt h eg r i dc l u s t e r i n g a l g o r i t h mi s s e n s i t i v et op a r a m e t e r s w ea d v a n c eag r i d - b a s e dc l u s t e r i n g a l g o r i t h mw i t ht h ep a r a m e t e ra u t o m a t i z a t i o n ( p a g ) t h a tc a ns o l v et h ep r o b l e m t h a tt h eg r i dc l u s t e r i n ga l g o r i t h mi ss e n s i t i v et op a r a m e t e r s t h ee x p e r i m e n t h a sd o n eo nt h es y n t h e t i cd a t a s e t sa n dr e a ld a t a s e t ，a n dt h i st h e s i sh a sg i v e st h e e x p e r i m e n t a lr e s u l t sa n dt h et i m ec o m p l e x i t ya n dt h es p a c ec o m p l e x i t yo f t h ea l g o r i t h m 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 g ，g r i dd l u s t e r i n g ，d e n s i t yu n i t ， p a r a m e t e ra u t o m a t i z a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得重迭自g 曳太堂或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：伍苘刍移 签字日期：1 仂刁年月h 日 学位论文版权使用授权书 本学位论文作者完全了解重麽由e 电太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权重麽邮电态堂可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：经商笔己 导师签名： 斟内喜 签字日期铂1 年6 月阳签字日期吱卞( ) 月1 2 日 重庆邮电大学硕士论文第一章绪论 第一章绪论 1 1 电子商务中数据挖掘的必要性 近年来，随着互联网的普及和电予商务的迅猛发展，人类已进入了信 息社会和网络经济时代，我们的社会越来越依赖于信息。每天在我们的日 常生活中都产生海量的数据，但是这些数据绝大部分都没有被提炼为知 识，“数据丰富，知识贫乏”的现象广泛存在。对于这些数据，需要有一 个强有力的工具来对其进行分析，并从中提取出有用的知识，以帮助企业 决策、科学研究等。数据挖掘( d a t am i n i n g ，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 ) ，简称知识发现【3 1 。 人们把原始数据看作是形成知识的源泉，就像从矿石中采矿一样。数 据挖掘所依赖的原始数据来源多种多样，可以是常用的关系数据库、事务 数据库、文本数据库、多媒体数据库等，主要取决于用户的目的及所处的 领域。目前，数据挖掘的数据主要取自关系数据库与数据仓库。原始数据 可以是结构化的，如关系数据库中的数据，也可以是半结构化的，如文本、 图形、图像数据，甚至是分布在网络上的异构型数据。发现知识的方法可 以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发现 的知识可以被用于信息管理、查询优化、决策支持、过程控制等，还可以 用于数据自身的维护。 统计数据证明：数据挖掘能够给企业构建竞争优势并带来巨大的经济 效益，过去的几年里，在关系数据库中的知识发现取得了丰硕的成果，己 经开发了很多数据挖掘系统，如：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 a 等己经在大型的数据库和数据仓库系 统中使用的软件。数据挖掘是一个应市场需求而生的学科，又是一个多学 科相互融合相互渗透而产生的交叉学科。数据库技术、机器学习、统计技 术、信息科学的发展为数据挖掘的诞生奠定了理论基础，不可限量的市场 需求为数据挖掘的发展提供了广阔的空间。 特别指出的是，数据挖掘技术从一开始就是面向应用的。它不仅是面 向特定数据库的简单检索查询调用，而且要对这些数据进行微观或宏观的 重庆邮电大学硕士论文第一章绪论 统计、分析、综合和推理，以指导实际问题的求解，企图发现事件间的相 互关联，甚至利用已有的数据对未来的活动进行预测。例如，加拿大b c 省电话公司要求加拿大s i m o nf r a s e r 大学数据挖掘研究组，根据其拥有的 十多年的客户数据，总结、分析并提出新的电话收费和管理办法，制定既 有利于公司又有利于客户的优惠政策。美国n b a 的著名篮球队的教练， 利用i b m 公司提供的数据挖掘技术，临场决定替换队员，一度在数据库领 域中传为佳话。这样一来，就把人们对数据的应用，从低层次的末端查询 操作，提高到为各级经营决策者提供决策支持。 当今电子商务的数据库容量己经达到上万亿的水平。在这些大量数据 的背后隐藏了很多具有决策意义的信息，那么怎么得到这些“知识 昵? 计算机科学对这个问题给出的最新回答就是数据挖掘，在“数据矿山 中 找到这些蕴藏的“知识金块 ，为各级经营决策者提供决策支持。 1 2 典型数据挖掘过程及系统描述 随着信息技术的迅速发展，需要分析和管理的数据迅速增多，这种趋 势己经渗透到数据挖掘领域中。数据挖掘就是从大量的、不完全的、有噪 声的、模糊的随机数据中，提取隐含在其中的、人们事先不知道的、但又 是潜在有用的信息和知识。 数据挖掘的整个过程( 如图1 1 ) 可以粗略地分为：按需选择数据、 数据集成、数据预处理、数据转换、挖掘过程以及模式评估和知识表示等。 ( 1 ) 数据选择 从数据源中检索与分析任务相关的数据。 ( 2 ) 数据集成 。 建立目标数据集。根据数据挖掘目标，从原始数据中选择相关数据集， 并将不同数据源中的数据集成起来，以确定数据挖掘的操作对象，需要解 决平台、操作系统和数据类型不同产生的数据物理格式差异。 ( 3 ) 数据预处理 数据集中不可避免地存在着不完整、不一致、不精确和重复的数据， 这些数据统称为脏数据。数据抽取之后需利用领域专门知识对脏数据进行 清洗。通常采用基于规则的方法、神经网络方法和模糊匹配技术分析多数 据源数据之间的联系，然后再对它们实施相应的处理。 ( 4 ) 数据转换 根据分析任务目标，选用关键特征表示数据，并将数据通过汇总或聚 2 重庆邮电大学硕士论文第一章绪论 集等操作转换为适于数据挖掘处理的形式。 ( 5 ) 挖掘算法 使用智能方法提取数据模式。这些方法包括概括、分类、回归和聚类 等。 ( 6 ) 模式评估 采用有关方法对数据挖掘发现的模式进行评价，根据某种兴趣度度 量，识别表示知识的真正兴趣的模式。 图1 1 数据挖掘的过程 ( 7 ) 知识表示 使用可视化和知识表示技术，向用户提供挖掘的知识，帮助用户理解 发现的模式。 由上述过程可知，整个挖掘过程是一个不断反馈的过程。比如，用户 在挖掘途中发现选择的数据不太好，或使用的挖掘技术产生不了期望的结 果，这时，用户需要重复先前的过程，甚至从头重新开始。 基于这种观点，加拿大华裔科学家j i a w e ih a n 提出典型的数据挖掘系 统具有以下主要成分( 如图1 2 ) ( 1 ) 数据库、数据仓库或其它信息库 这是一个或一组数据库、数据仓库、电子表格或其它类型的信息库。 可以在数据上进行数据清理和集成。 ( 2 ) 数据库或数据仓库服务器 服务器根据用户的数据挖掘请求，数据库或数据仓库服务器负责提取 相关数据。 重庆邮电大学硕士论文第一章绪论 ( 3 ) 知识库 这是领域知识，用于指导搜索，或评估结果模式的兴趣度。这种知识 可能包括概念分层，用于将属性或属性值组织成不同的抽象层。用户信念 方面的知识也可以包含在内。可以使用这种知识，根据意外性评估模式的 兴趣度。领域知识的其它例子有兴趣度限制或阀值和元数据。 ( 4 ) 数据挖掘引擎 这是数据挖掘系统的基本部分，由一组功能模块组成，用于特征化、 关联、分类、聚类分析以及演变和偏差分析。 ( 5 ) 模式评估模块 通常此成分使用兴趣度度量，并与数据挖掘模块交互，以便将搜索聚 焦在有趣的模式上。它可能使用兴趣度阀值过滤发现的模式。模式评估模 块也可以与挖掘模块集成在一起，这依赖于所用的数据挖掘方法的实现。 对于有效的数据挖掘，建议尽可能深地将模式评估推进到挖掘过程之中， 以便将搜索限制在有兴趣的模式上。 ( 6 ) 图形用户界面 本模块在用户和数据挖掘系统之间通信，允许用户与系统交互，指定数据 挖掘的任务，提供信息、帮助搜索聚焦，根据数据挖掘的中间结果进行探 索式数据挖掘。此外，此成分还允许用户浏览数据库和数据仓库模式或数 据结构，评估挖掘的模式，以不同的形式对模式可视化【5 】。 教糍 图1 2 典型的数据挖掘系统结构 4 重庆邮电大学硕士论文第一章绪论 1 3 聚类在数据挖掘中的重要地位 数据挖掘已经成为一个热门的研究方向，而聚类( c l u s t e r i n g ) 作为 数据挖掘的主要方法之一，也引起了人们越来越多的关注。所谓聚类，是 指将若干对象的集合分组成为由类似的对象组成的多个类的过程。简单的 说，就是识别出一组聚类规则，将数据分成若干类；使同一类中对象的相 似性尽可能最大，而不同类中对象的相似性尽量达到最小。聚类增强了人 们对客观现实的认识。 现今，聚类已经广泛地应用在许多领域中。在商业上，聚类可以帮助 市场分析人员从他们的消费者数据库中区分出不同的消费群体来，并且概 括出每一类消费者的消费模式或者说习惯：在生物学中，它可以被用来辅 助研究动、植物的分类，可以用来分类具有相似功能的基因，还可以用来 发现人群中的一些潜在的结构等等。聚类还可以用来从地理数据库中识别 出具有相似土地用途的区域；可以从保险公司的数据库中发现汽车保险中 具有较高索赔概率的群体；也可以从一个城市的房地产信息数据库中，根 据房型、房价及地理位置分成不同的类；还可以用来从万维网上分类不同 类型的文档等。此外，聚类可以作为其他算法的预处理步骤，这些算法在 聚类结果基础上进行处理阳9 3 。 目前，聚类己经成为数据挖掘研究领域中一个非常活跃的研究课题。 聚类作为一种重要的决策分析工具，对其研究与实现具有重要的理论与现 实意义。 1 4 聚类算法研究面临的挑战及存在的问题 聚类算法研究是一个具有很强挑战性的研究领域，它的一些潜在应用 对聚类算法提出了特别的要求： ( 1 ) 可伸缩性( ( s c 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 ) 能够处理不同类型的属性 现实中的数据对象己远远超出关系型数据的范畴，比如空间数据、多 媒体数据、遗传学数据、时间序列数据、文本数据、万维网上的数据、以 及目前逐渐兴起的数据流。这些数据对象的属性类型往往是由多种数据类 型综合而成的。 ( 3 ) 能够发现任意形状的簇。 ( 4 ) 尽量减少用于决定输入参数的领域知识。 ( 5 ) 能够处理噪声数据及孤立点。 ( 6 ) 对输入数据记录的顺序不敏感。 ( 7 ) 高维性( h i g h d i m e n s i o n a l ) 一个数据集可能包含若干个维。较高的维数给聚类分析带来两个问 题：首先，不相关的属性削弱了数据会聚的趋势，使得数据分布非常稀疏。 尽管这种情况在低维空间中并不多见，但是随着维数的增加，不相关属性 的出现概率及数量也会增加，最后导致数据空间中几乎不存在簇。其次， 高维使得在低维中很有效的区分数据的标准在高维空间中失效了。譬如在 高维空间中，数据点到最近邻点的距离与到其他点的距离没有多少分别， 从而导致最近邻查询在高维空间中不稳定，此时若根据接近度来划分簇， 结果是不可信的。 ( 8 ) 能够根据用户指定的约束条件进行聚类。 ( 9 ) 聚类结果具有可解释性和可用性。 上述的要求使目前聚类算法研究的热点集中到了研究有效适用于大 型数据库的可伸缩性聚类算法、能够识别复杂形状的簇的聚类算法、高维 聚类分析算法以及针对大型数据库中混合数值的聚类算法【1 1 1 。 聚类目前所采用的方法主要有：划分方法、层次方法、基于网格的方 法、基于模型的方法、基于密度的方法这几类，目前数据库中的数据是高 维的和任意形状的，同时，数据量也是非常大的。以上的这几种传统方法 各有优缺点，但是没有一种能同时满足数据挖掘对聚类可伸缩性、处理不 同类型属性的能力、发现任意形状的聚类、用于决定输入参数的领域知识 最小化、处理噪声数据的能力、对于输入记录的顺序不敏感、高维性、基 于约束的聚类以及聚类结果的可解释性和可用性的要求。要想得到一个很 好的聚类效果就需要将几种聚类方法融合在一起。 6 重庆邮电大学硕士论文第一章绪论 1 5 本文主要的研究内容与思路 针对上面的分析，本文主要就以下内容进行了研究： 1 ) 提出基于网格、基于密度的混合聚类算法 d b s c a n 算法将具有足够高密度的区域划分为簇，并可以在带有“噪声” 的空间数据库中发现任意形状的聚类，但计算量大，参数的试探选定困难。 c l i q u e 算法有快速的处理速度，当数据维数增加时具有良好的可伸缩性， 但是不能发现任意形状的聚类，聚类结果的质量和精确性可能较低。针对 上述问题，提出一种基于网格和密度的混合算法c b d g 。该算法保持了基于 密度的聚类算法可以有效处理噪声点和发现任意形状的聚类的优点，同时 保持了基于网格的聚类算法的高效性，适合对大规模数据的挖掘。我们的 理论分析和实验结果也证明了上述结论。 2 ) 提出基于网格的参数自动化聚类算法 由于传统的网格聚类算法需要人为的输入参数，这就使得聚类结果很 大程度上依赖于参数的选择，聚类算法对参数的依赖性很大。针对这个问 题，提出了基于网格的参数自动化聚类算法，并在综合数据集和真实数据 集上进行测试，最后给出实验结果，同时分析了该算法的时间复杂度和空 间复杂度。 1 6 本文的组织与结构 本文共分五章，具体组织如下： 第一章主要对面向电子商务的数据挖掘进行概要介绍，并提出了本文 重点研究内容一一基于网格、基于密度的混合聚类算法和基于网格的参数 自动化聚类算法。 第二章概要的介绍了聚类算法的几大基本类型：划分方法、层次方法、 基于网格的方法、基于模型的方法、基于密度的方法及其代表算法。特别 对基于网格与密度的混合算法作了较为详细的介绍，并分析了这些算法的 优点和缺点。 第三章针对d b s c a n 算法能发现任意形状的聚类但计算量大、参数的试 探选定困难；而c l i q u e 算法速度快、可伸缩性良好但是不能发现任意形状 的聚类等特点提出了一种基于网格和密度的混合算法。该算法的主要思想 概要如下：首先，将n 维数据空间划分为互不相交的有限数目的单元，识 7 重庆邮电大学硕士论文第一章绪论 别其中的密集单元，通过相连密集单元的融合形成各个簇的大致划分。其 次，对各个簇的边缘区域进行“剪枝”得到簇的核心区域。然后，通过一 定等效规则得到由密集单元识别转换到密度可达对象搜索的参数。最后， 选取核心区域中的代表单元搜索密度可达对象，最终的聚类为核心区域中 的对象和基于密度可达性的最大密度相连对象的集合。并对该算法明显优 于d b s c a n 署i c l i q u e 的方面进行了阐述。 第四章在研究了传统网格聚类算法对参数依赖性的基础上，提出基于 网格的参数自动化的聚类算法，并将该算法在综合数据集和网络入侵真实 数据集上进行测试，最后给出实验结果，同时分析了算法的时间复杂度和 空间复杂度。 第五章对已完成的研究工作进行了总结，并提出了后续的研究思路。 8 重庆邮电大学硕士论文 第二章聚类算法概述 第二章聚类算法概述 聚类分析是数据挖掘技术中重要的组成部分，它能够在潜在的数据中 发现令人感兴趣的数据分布模式。从技术角度讲，它的主要目的是将数据 空间中的数据点划分到若干个类中，其中将距离相近的数据点划分到相同 的类中，而将距离较远的数据点划分到不同的类中。它是在无监督的情况 下根据一定的相似性或距离计算函数自动的将数据集分成若干类。聚类所 采用的方法主要有划分方法、层次方法、基于网格的方法、基于模型的方 法、基于密度的方法这几类，以及以上这几种方法中两种甚至两种方法的 混合算法。 2 1 聚类的含义 所谓聚类( c l u s t e r i n g ) 就是将物理或抽象对象的集合分组成为由类似 的对象组成的多个类的过程。由聚类生成的类是一组数据对象的集合，这 些对象与同一个类中的对象彼此相似，与其它类中的对象相异。相异度是 根据描述对象的属性值来计算的，距离是经常采用的度量方式。 在数据挖掘中，聚类分析( 无监督分类) 与分类分析( 有监督分类) 之间是 有联系的也是有区别的。它们都是将未知模式的数据集分成若干个类。但 通常，为有监督分类提供若干己标记的对象( 预分类过) ，需要解决的问题 是为一个新遇到的但无标记的对象进行标记。在典型的情况下，先将给定 的无标记的模式用来学习( 训练) ，反过来再用来标记一个新模式。聚类需 要解决的问题是将己给定的若干无标记的对象聚集起来使之成为有意义 的聚类。从某种意义上说，标记也与聚类相关，但这些类型的标记是由数 据驱动的，也就是说，只是从数据中得到这些标记。聚类与数据挖掘中的 分类不同，在分类模块中，对于目标数据库中存在哪些类是知道的，要做 的就是将每一条记录分别属于哪一类标记出来，与此相似但又不同的是， 聚类是在预先不知道目标数据库到底有多少类的情下，希望将所有的记录 组成不同的类，并且使得在这种分类情况下，以某种度量为标准的相似性， 在同一聚类之间最小化，而在不同聚类之间最大化【1 7 】。 聚类在以下几个领域中是非常有用的：模式分析的浏览、聚集、决策 制定及机器学习，还包括数据挖掘、文件恢复、图像分割及模式分类。但 9 重庆邮电大学硕士论文第二章聚类算法概述 在这些问题中，几乎没有有关数据的先验信息( 如统计模型) 可用，而用户 又要求尽可能地对数据的可能性少进行假设。在这些限制条件下，聚类方 法特别适合于查看数据点中的内在关系以对它们的结构进行评估。 聚类在商业、生物学、保险业以及房地产等等方面都有极其广泛的用 途。同时，聚类分析作为数据挖掘中的一个模块，它可以作为一个单独的 工具以发现数据库中数据分布的一些深层的信息，并且概括出每一类的特 点，或者把注意力放在某一个特定的类上以作进一步的分析；聚类分析也 可以作为数据挖掘算法中其他分析算法的一个预处理步骤。但大部分涉及 聚类的实际问题是多维的，直观地去解释多维空间嵌入的数据是非常困难 的问题。 2 2 聚类算法的分类 聚类分析的算法基本的可以分以下几大类：划分方法、层次方法、基 于密度的方法、基于网格的方法和基于模型的方法等。 ( 1 ) 划分方法( p a r t i t i o n i n gm e t h o d ) 、 给定一个有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 ) 这种方法对给定的数据集进行层次的分解，直到某种条件满足为止。 具体又可分为“自底向上 和“自顶向下 两种方案。代表算法有：b i r c h 算法、c u r e 算法、c h a m e l e o n 算法、c a c t u s 算法等。 ( 3 ) 基于网格的方法( 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 算法。 ( 4 ) 基于模型的方法( m o d e l b a s e dm e t h o d ) 基于模型的方法给每一个聚类假定一个模型，然后去寻找能够很好的 1 0 重庆邮电大学硕士论文 第二章聚类算法概述 满足这个模型的数据集。这样一个模型可能是数据点在空间中的密度分布 函数或者其他。它的一个潜在的假定就是：目标数据集是由一系列的概率 分布所决定的。通常有两种方法：统计的方法和神经网络的方法。 ( 5 ) 基于密度的方法( d e n s i t y b a s e dm e t h o d ) 基于密度的方法与其他方法的一个根本区别是：它不是基于各种各样 的距离的，而是基于密度的，这样就能克服基于距离的算法只能发现球型 聚类的缺点。这个方法的指导思想就是只要一个区域中的点的密度大过某 个阀值，就把它加到与之相近的聚类中去。代表算法有：d b s c a n 算法和 o p t i c s 算法等。 以上介绍的这五种方法各有优缺点，但还没有一种聚类算法能全部满 足对聚类分析所提出的九项要求。大多数据类算法只是针对聚类中的一个 或某几个问题进行解决的。 2 2 1 划分方法 给定一个包含n 个数据对象的数据库，以及要生成的类的数目k ，一 个划分类的算法将数据对象组织为k 个划分( k 力) ，其中每个划分代表一 个类。也就是说，他将数据划分为k 个组，同时满足如下要求：( a ) 每个组 至少包含一个对象；( b ) 每个对象必须属于且只属于一个组。 给定要构建的划分的数目k ，划分方法首先创建一个初始划分。然后 采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。通 常一个划分准则( 相似度函数) ，例如距离，以便在同一个类中的对象是“相 似的”，而不同类中的对象是“相异的”。 一个好的划分的一般标准是：在同一个类中的对象之间尽可能“接 近 或相关，而不同类中的对象之间尽可能“远离 或不同。为了达到全 局最优，基于划分的聚类会要求穷举所有可能的划分【2 0 1 。 最著名与最常用的划分方法是k m e a n s 。 k m e a n s 算法的目标是根据输入参数k ，将数据集划分成k 个簇。算法 采用迭代更新的方法：在每一轮中，依据k 个参照点将其周围的点分别组 成k 个簇，而每个簇的质心( 即簇中所有点的平均值，也就是几何中心) 将 被作为下一轮迭代的参照点。迭代使得选取的参照点越来越接近真实的簇 质心，所以聚类效果越来越好。 k m e a n s 算法的处理流程如下。首先，随机的选择k 个对象，每个对 象初始的代表了一个类的平均值或中心。对剩余的每个对象，根据其与各 重庆邮电大学硕士论文第二章聚类算法概述 个类中心的距离，通常，采用平方误差准则，其定义如下： e - e i p 一圳 ( 2 1 ) 这里的e 是数据库中所有对象的平方误差的总和，p 是空间中的一点， 表示给定的数据对象，砚是类q 的平均值( p 和以都是多维的) 。这个准则试 图使生成的结果类尽可能的紧凑和独立。k m e a n s 过程的概述如下： ( 1 ) 任意选择k 个对象作为初始的类中心； ( 2 ) r e p e a t ； ( 3 ) 根据类中对象的平均值，将每个对象( 重新) 赋给最类似的值； ( 4 ) 更新类的平均值，即计算每个类中对象的平均值； ( 5 ) u n t i l 不再发生变化。 这个算法尝试找出使平方误差函数至最小的k 个划分。当结果类是密 集的，而处于类之间区别明显时，它的效果较好。对处理大数据集，该算 法是相对可伸缩的和高效率的，因为它的复杂度是o ( t k n ) ，其中n 是数据 的总数，k 是聚类的个数，t 是算法循环的次数，通常有k m i n p t s 。 在第( 2 ) 种条件下，p 满足核心点条件，因为周围有足够的点围绕着它。 直接密度可达对于核心点来说是对称的，然而，一个核心点与被其包含在 内的边界点之间的直接密度可达关系就不是对称的。图2 1 就显示了这种 情况。图2 1 ( a ) 中，p 为边界点，q 为核心点。但从图2 1 ( b ) 中可以看出 p 从q 直接密度一可达，而q 从p 就不是直接密度可达。， o q o o - 0 ( b ) 图2 1 核心点与边界点 运用直接密度可达的定义，我们可以通过传递关系定义出密度可达。 定义2 3 ( 密度可达) 对于给定的e p s 和m i n p t s ，点p 从点q 处密度可 达，当且仅 当存在这样 一个点的 序列 ； p 。，p ：，p n , a = g ，p n = p ，其中勘+ 。从勘处直接密度- 可达。 定义2 4 ( 密度一连接) 对于给定的e p s 和m i n p t s ，点p 和点q 密度连接， 当且仅当存在这样一个点0 ，点p 和点q 均与点0 密度可达。 密度- 可达是可传递的，但不是对称的。对于核心点来说密度可达关 系是对称的。图2 2 描述了一些点间的关系。在图中，迕到p 是密度可达， 而p 到q 不是密度可达。密度连接是一个对称关系。图2 2 中，r 与s 1 7 重庆邮电大学硕士论文第二章聚类算法概述 通过o 点互为密度连接关系。 警二一一 图2 2 密度可达与密度一连接 定义2 5 ( 类) 假定d 是具有距离定义的数据库。 m i n p t s ，某一类c 就是满足以下条件的非空子集； 坳，q ，如果p c 并且对于给定的e p s 和m i n p t s ， 可达，那么qe c 。 对于给定的e p s 和 点q 从点p 处密度一 坳，q c ，对于给定的e p s 和m i n p t s ，点p 和点q 密度连接。 基于上述类的定义，对于给定的e p s 和m i n p t s ，d b s c a n 算法从任意 一个密集点出发，反复地按照定义5 的要求扩展该类。为了支持磁盘处理， 所有被标上属于某一类的点将不会再对其进行计算。因此，算法的计算时 间复杂度为o ( n * l o g ( n ) ) 。然而，由于算法本身在整个聚类过程中使用固 定的参数e p s 和m i n p t s ( e s t e r 提供了一种自动求得参数的方法) ，使得对于 真实环境数据集的聚类，往往其聚类的效果不好。主要一点原因就是由于 其定义的密度的传递性质，往往将绝大多数的数据点都聚集在非常少的几 类中( 通常是一类) 。 在d b s c a n 中，发现一个类的过程是基于这样的事实：一个类能够 被其中的任意一个核心对象所确定。为了发现一个类，d b s c a n 先从d 中 找到任意一对象p ，并查找d 中关于e p s 和m i n p t s 的从p 密度可达的所有 对象。如果p 是核心对象，也就是说，半径为e p s 的点p 的邻域中包含的 对象数不少于m i n p t s ，则根据算法可以找到一个关于参数e p s 和m i n p t s 的类。如果p 是一个边界点，即半径为e p s 的p 的邻域包含的对象数小于 m i n p t s ，则没有对象从p 密度可达，p 被暂时标注为噪声点。然后，d b s c a n 处理数据库中的下一个对象。密度可达对象的获取是通过不断执行区域查 询来实现。一个区域查询返回指定区域中的所有对象。 假定输入参数为e p s 和m i n p t s ，d b s c a n 的算法描述如下： ( 1 ) 从数据集中任意选取一个点p ，并对其进行区域查询； 1 8 重庆邮电大学硕士论文 第二章聚类算法概述 ( 2 ) 如果p 是核心点，则寻找所有从p 密度可达的点，最终形成一个包 含p 的簇； ( 3 ) 否则，p 被暂时标注为噪声点； ( 4 ) 访问数据集中的下一个点，重复上述过程，直到数据集中所有的点 都被处理。 2 2 5 基于网格的方法 基于网格的方法采用一个多分辨率的网格数据结构。它将空间化为有 限数目的单元，这些单元形成了网格结