（计算机应用技术专业论文）聚类分析中k均值方法的研究.pdf

哈尔滨r 稃大学硕士学位论文 摘要 数据挖掘是从庞大的数据集或数据库中提炼有用信息的科学。它汇集 了统计学、机器学习、数据库、模式识别、人工智能等学科的内容，是一 门新兴的交叉学科。 聚类分析是数据挖掘中的一个重要研究领域，是- , e e 数据划分或分组 处理的重要手段和方法。聚类的应用是非常广泛的，无论是在商务上、还 是在市场分析生物学、w e b 文档分类等领域中都得到了充分的应用。目 前，聚类算法大体上分为划分的方法、层次的方法、基于密度的方法、基 于网格的方法和基于模型的方法。这些算法存在如下的问题：符号属性问 题、算法的效率问题、初值的选择问题、对输入顺序的敏感性问题、最优 解问题、算法对输入参数的依赖性问题。 本文研究基于划分的聚类方法中有效选取初值的问题。主要工作如 下： 首先，概括介绍了聚类分析的基本原理，并对聚类分析中的基本数据 类型进行了描述。 其次，在对各种聚类算法进行简单描述后，提出了本文所涉及到的基 于划分的聚类算法，并提出了本文中的算法对聚类分析中普遍存在的初始 中心选择问题的处理方式。 最后，给出了改进的基于划分的聚类方法，以及其中涉及到的撮小生 成树算法的基本思想。并通过实验有效验证了算法的可行性。 关键词：数据挖掘：聚类；分析；算法；k - m e a n s 晗尔滨： 譬大学硕士学位论文 ；i i i i i i i i ii i ii _ a b s tr a c t d a t am i n i n g ，w h i c he x t r a c t su s e f u li n f o r m a t i o nf r o ml a r g ed a t as e t so r d a t a b a s e s ，i s ar i s i n gc r o s s s u b j e c t t h e c o n t e n t so fs t a t i s t i c s ，m a c h i n e l e a r n i n g ，d a t a b a s e ，p a t t e r nr e c o g n i t i o n ，a r t i f i c i a li n t e l l i g e n c e ，e t c a r e i n v o l v e d c l u s t e r i n gi sa ni m p o r t a n ta r e af o rr e s e a r c hi nd a t am i n i n g ，a n da l s oa n i m p o r t a n tm e t h o di nd a t ap a r t i t i o n o rd a t ag r o u p i n g c l u s t e r i n gh a sb e e n w i d e l yu s e di nc o m m e r c e ，m a r k e ta n a l y s i s ，b i o l o g y ，w e bc l a s s i f i c a t i o na n ds o o n 。u pt on o w , c l u s t e r i n ga l g o r i t h m s a r e m a i n l yc o n s i s t e d o ff i v ek i n d s ： p a r t i t i o na l g o r i t h m ，h i e r a r c h i c a la l g o r i t h m ，d e n s i t y b a s e da l g o r i t h m ，g r i d - b a s e d a l g o r i t h ma n d m o d e l b a s e da l g o r i t h m a n dt h e r es t i l le x i s t sm a n yp r o b l e m si n t h e s ec l u s t e r i n ga l g o r i t h m s ，s u c ha ss y m b o l i ca t t r i b u t e s ，e f f i c i e n c y ，s e l e c t i o no f i n i t i a lv a l u e s ，s e n s i t i v i t yo fi n p u ts e q u e n c e ，o p t i m a ls o l u t i o n s ，d e p e n d e n c eo n i n p u tp a r a m e t e r sa n d s oo n t h i sp a p e rr e s e a r c h e st h es e l e c t i o no fi n i t i a ld a t ai np a r t i t i o na l g o r i t h m + t h em a i nw o r ki sa sf o l l o w s ： f i r s t ，t h eb a s i cp r i n c i p l e so fc l u s t e r i n ga r ei n t r o d u c e da n dt h eb a s i cd a t a t y p e si nc l u s t e r i n ga r ed e s c r i b e di ng e n e r a l s e c o n d ，a f t e ra l lc l u s t e r i n ga l g o r i t h m sa r ed e s c r i b e di nb r i e f , t h ep a r t i t i o n a l g o r i t h mw h i c hi s r e l a t e dt ot h i s p a p e ri sp r o p o s e d ，a n d t h em e t h o do f s e l e c t i n gp r i m a r yc e n t e r si sa l s op r o p o s e d 。 l a s t ，t h ep a r t i t i o na l g o r i t h mw h i c hh a sb e e ni m p r o v e di sp r o p o s e d ， m e a n w h i l e ，t h eb a s i ci d e ao fm i n i m u mc o s ts p a n n i n gt r e e i sp r e s e n t e d + f u r t h e r , t h ef e a s i b i l i t yo ft h i sa l g o r i t h mi sp r o v e db ye x p e r i m e n t s 。 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 g ；a n a l y s i s ；a l g o r i t h m ；k - m e a n s 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：立趣 日期：缈7 年月x - 日 哈尔滨工程大学硕十学位论文 第1 章绪论 1 1 论文研究的背景及意义 随着计算机技术的迅猛发展以及网络技术的普及，人们有更多机会通 过网络与外界进行信息交流。然而，随着数据大量的涌入，增加了我们获 取有用信息的难度。如何从大量的类型各异数据中获取有价值的信息，采 用传统的数据库技术己显得无能为力。数据的迅速增加与数据的分析处理 方法滞后的矛盾越来越大，人们希望能够在对已有的大量数据分析的基础 上进行科学研究、商业决策或企业管理，数据挖掘正是在这一背景下诞生 的。数据挖掘( d a t a m i n i n g ) ，又称为数据库中的知识发现( 简称k n o w l e d g e d i s c o v e r yi nd a t a b a s e ) ，是从大量的、不完全的、有噪声的、模糊的、随机 的数据中，提取隐含的、未知的、有潜在应用价值的信息或模式的过程。 它是一门新兴的交叉学科，汇集了来自数据库技术、统计学、机器学习、 高性能计算、模式识别、神经网络、数据可视化、信息检索、图像与信号 处理和空间数据分析等各领域的研究成果。 聚类是数据挖掘中的一种重要技术，是分析数据并从中发现有用信息 的一种有效手段。基于“物以类聚”的朴素思想，它将数据对象分组成为 若干个类或簇，使得在同一个类中的对象之间具有较高的相似度，而不同 类中的对象差别很大，通过聚类，人们能够识别密集和稀疏的区域，发现 全局的分布模式以及数据属性之间有趣的相互关系。聚类分析在客户分 类、基因识别、w w w 文本分类、空间数据处理、卫星照片分析、医疗图 象自动检测等领域有着广泛的应用，而其本身的研究也是一个蓬勃发展的 领域，数据挖掘、统计学、机器学习、空问数据库技术，生物学和市场学 的发展推动着聚类分析研究的进展，使它已成为数据挖掘研究中的一个热 点。与其他数据挖掘方法不同，在进行聚类分析前用户一般并不知道数据 集的特征。因此，从某种角度看，聚类分析是一种无监督的学习过程，是 基于观察的学习而不是基于实例的学习。 作为数据挖掘中的一个模块，聚类分析可作为一个独立的工具来获取 哈尔滨1 ：稃大学硕十学位论文 数据分布的情况，观察每个类的特点，集中对特定的某些类做进一步分析。 如在商务上，聚类分析可以帮助市场分析人员从客户基本库中发现不同的 客户群，并且用购买模式来刻画不同的客户群的特征。聚类分析也可以作 为数据挖掘中其他算法( 如特征和分类等) 的预处理步骤，这些算法再在生 成的类上进行处理；此外它还可以完成孤立点挖掘。许多数据挖掘算法试 图使孤立点影响最小化，或者排除它们。然而孤立点本身可能是非常有用 的，如在欺诈探测中，孤立点有可能预示着欺诈行为。迄今为止，人们提 出了大量的聚类算法，算法的选择取决于数据的类型、聚类的目的和应用。 如果聚类分析用于描述或探索的工具，可以对同样的数据尝试多种算法， 以便发现数据可能隐含的规律与结果。 k - m e a n s 属于聚类分析中一种基本的划分方法，常采用误差平方和准 则函数作为聚类准则。主要优点是算法简单、快速而且能有效地处理大数 据集。然而这种算法依赖于初始值的选择以及数据的输入顺序。此外，由 于运用误差平方和准则函数测度聚类效果，如果各类的形状和大小差别很 大。为尽可能的优化初始值的选择，论文针对k m e a n s 算法对初值的依赖 性，基于最小生成树原理寻找最优初值的思想提出了一种新改进的 k - m e a n s 算法，实验结果表明，该算法聚类效果优于原始算法并具有较好 的稳定性。因此，本课题具有实用价值和理论意义。 1 2 相关领域内的研究动态 1 2 1 聚类分析概述 系统中聚类分析的基本思想是根据物以类聚的原理，对样本进行分 类。聚类是无监督的方式，因为和分类学习相比，分类学习的例子或数据 对象有类别标记，而要聚类的例子则没有标记，需要由聚类学习算法来自 动确定，即把所有样本作为未知样本进行聚类。因此分类问题和聚类问题 根本的不同点为：在分类问题中，知道训练样例的分类属性值，而在聚类 问题中，需要在训练样例中找到这个分类属性值。采用聚类分析技术，可 以把无标识数据对象自动划分为不同的类，并且可以不受人们的先验知识 的约束和干扰，从而获取属于数据集合中原本存在的信息。 2 哈尔滨t 稃人学硕十学位论文 1 1 1 聚类算法广泛应用在模式识别、图象处理、囊动控制等领域。聚类方 法包括统计方法、机器学习方法、神经网络方法和面向数据库的方法。 所谓聚类( c l u s t e r i n g ) 就是把数据分威不同的组( c l a s s ) 或类( c l u s t e r ) ， 并殿使得缀与组之间的相似度尽可能的小，而组内数据之间具有较高的桶 似艘。将一群( s 旬物理的域抽象的对象，根据它们之间的相似程度，分为 着午组，其中相似的对象构成一缀，这一遥程就称为聚类避程( c l u s t e r i n g ) ， 一个聚类( c l u s t e r i n g ，又称为簇) 就是由彼此相似的一组对象所构成的集 合，不同聚类中对象通常建不幅戗的。聚癸分轿就是获绘定的数据集中搜 索数据对蒙之间所存在的肖价值联系。与分类不问，在歼始聚类之l j i 用户 并不知道簧把数据分成凡缀，也不知道分缀的其体标准，聚类分耩对数掭 集仓的特征是未知的。聚类根据一定的聚类规则，将具有某种相同特征的 数键聚在一起，也称之为巍监督学习。丽分类，丽户鄹翔道数据霹分为尼 类，将要处理的数据按照分类标准分入不同的类别，也称为有监餐学习。 聚类分析的冀翟应嗣囊要有：在裔鼗方蓬，聚类分耩碍瑷帮瀚市场入 员发现客户群中所存在的不同特征的组群。在生物学方面，聚类分析可以 甭荣获取动纺或穰物静层次结构，瑟禳据蘩嚣臻魏对箕避纷分类叛获得辩 人群中所劂有的结构更深入的了解。聚类还可以从地球观测数据库中帮助 识羽翼有撩钕静主途使用拷浇静酝城。魏舛，还露鹾蘩韵分类谖稍互联麴 上的文档以便进行信息发现。作为数据挖掘的一项功能，聚类分析还可以 俸为一个攀独静王爨来使馐，它霹浚帮韵分耩数掇懿分蠢、了解各数蕹类 的特征、确定所感兴趣的数据类以便作进一步分析。聚类分析还可以作为 箕饿算法( 懿：努炎帮定援翔纳) 豹羧筵毽步骤。 聚类分析技术正在蓬勃地发展，有贡献的研究领域包括数掘挖掘，统 谤学、辊嚣学习、空润数据库技零、生物举，敬爱泰场蓉销。垂予数摇露 中收集了火量的数据，聚类分析已经成为数据挖掘研究领域中一个非常活 跃麴醣究谍题。 作为统计学【”】的一个分支，聚类分析已经被广泛地研究了许多年，童 要集孛在蒸手距蕊豹聚类分援。纂手k - m e a n s ( 平均僮) ，k - m e d o i d s ( k - 中心) 和其他一些方法的聚类分析工具已经被加入到许多统计分析软件龟 或蓉缓孛，翔s p l u s ，s p s s ，以及s a s 。在规嚣学习领域，聚类楚无监餐 哈尔溟r 秤人学硕十学仲论文 学习( u n s u p e r v i s e dl e a r n i n g ) 的一个例子。聚类和无监督学习不依赖预先定 义的类和训练样本。由于这个原因，聚类是通过观察学习，而不是通过例 子学习。在概念聚类( c o n c e p t u a lc l u s t e r i n g ) 中，一组对象只有当它们可以 被一个概念描述时才形成一个类。这不同于基于几何距离来度量相似度的 传统聚类。概念聚类由两个部分组成：( 1 ) 发现合适的类；( 2 ) 形成对每个 类的描述。在这里，追求较高类内相似度和较低类问相似度的指导原则仍 然适用。 1 2 2 聚类方法分类 聚类算法有很多种，需要根据应用所涉及的数据类型、聚类的目的以 及具体应用要求来选择合适的聚类算法。如果利用聚类分析作为描述性或 探索性的工具，那么就可以使用若干聚类算法对同一个数据集进行处理， 以发现数据集可能揭示的结果。 通常聚类分析算法可以划分为以下几类： ( 1 ) 划分方法( p a r t i t i o n i n gm e t h o d ) 给定一个n 个对象或元组的数据库，一个划分方法构建数据的k 个划 分每个划分表示一个聚类，并且k 玎。也就是说，它将数据划分为k 个组， 同时满足如下的要求：( i ) 每个组至少包含一个对象；( i i ) 每个对象必须属 于且只属于一个组，同时某些模糊划分技术中第二个要求可以放宽。 给定要构建的划分的数目k ，划分方法首先创建一个初始划分。然后 采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。一 个好的划分的一般准则是：在同一个类中的对象之间尽可能“接近”或相 关，而不同类中的对象之间尽可能“远离”或不同。还有许多其他划分质 量的评判准则。基于划分的聚类会要求穷举所有可能的划分以求达到全局 最优。实际上，绝大多数应用采用了以下两个比较流行的启发式方法： k - m e a n s 算法，在该算法中，每个类用该类中对象的平均值来表示； k - m e d o i d s ，在该算法中，每个类用接近聚类中心的一个对象来表示。 ( 2 ) 层次方法( h i e r a r c h i c a lm e t h o d ) 层次的方法对给定数据对象集合进行层次的分解。根据层次的分解如 何形成，层次的方法可以分为凝聚的和分裂的。凝聚的方法，也称为自底 4 哈尔滨翠人学硕十学何论文 向上的方法，一开始将每个对象作为单独的一个组，然后相继地合并相近 的对象或组，直到所有的组合并为一个( 层次的最上层) ，或者达到一个终 止条件。分裂的方法，也称为自顶向下的方法，一开始将所有的对象置于 一个聚类中。在迭代的每一步中，一个类被分裂为更小的类，直到最终每 个对象在单独的一个类中，或者达到一个终止条件。 层次方法的缺陷在于，一旦一个步骤( 合并或分裂) 完成，它就不能被 撤消。这个严格规定是有用的，由于不用担心组合数目的不同选择，计算 代价会比较小。但是，该技术的一个主要问题是它不能更正错误的决定。 有两种方法可以改进层次聚类的结果：( i ) 在每层划分中，仔细分析对象间 的“联接”( i i ) 综合层次凝聚和迭代的重定位方法。首先用自底向上的层 次算法，然后用迭代的重定位来改进结果。 为改进层次方法的聚类质量，可以考虑将层次聚类和其他的聚类技术 进行集成，形成多阶段聚类。第一个方法称为b i r c h ，它首先用树结构对 对象进行层次划分，然后采用其他的聚类算法对聚类结果进行求精。第二 个方法称为c u r e ，它采用固定数目的代表对象来表示每个类，然后依据 一个定义的分数向着聚类中心对它们进行收缩。第三个方法称为r o c k ， 基于类的互联性进行合并。第四个方法称为c h a m e l e o n ，在层次聚类中发 现动态模型。 ( 3 ) 基于密度的方法( d e n s i t y - b a s e dm e t h o d ) 绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发 现球状的类，而在发现任意形状的类上遇到了困难。随之提出了基于密度 的另一类聚类方法，其主要思想是：只要临近区域的密度( 对象或数据点 的数目) 超过某个阈值，就继续聚类。也就是说，对给定类中的每个数据 点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法可 以用来过滤“噪声”孤立点数据，发现任意形状的聚类。 d b s c a n t , i 是一个有代表性的基于密度的方法，它根据一个密度阈值 来控制类的增长。o p t i c s 是另一个基于密度的方法，它为自动的和交互 的聚类分析计算一个聚类顺序。 ( 4 ) 基于网格的方法( g r i d - b a s e dm e t h o d ) i s - 7 1 基于网格的方法把对象空间量化为有限数目的单元，形成了一个网格 哈尔滨下程大学硕十学位论文 结构。所有的聚类操作都在这个网格结构( 即量化的空间) 上进行。这种方 法的主要优点是它的处理速度很快，其处理时日j 独立于数据对象的数目， 只与量化空间中每一维的单元数目有关。具有代表性的方法有： 基于网格的方法；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 nc m d ) 是一个基于网格多分辨率的聚类方 法。它将空间划分为方形单元。不同层次的方形单元对应不同层次的分辨 率。这些单元构成了一个层次结构：高层次单元被分解形成一组低层次单 元。有关各网格单元属性的统计信息( 如：均值、最大、最小) 可以事先运 算和存储。这些信息将在某些查询处理中用到。与其它聚类方法相比， s t i n g 方法有以下几个优点：( 1 ) 基于网格计算由于描述网格单元数据统 计信息是存储在相应单元中，因此它与查询要求无关；( 2 ) 网格结构有助 于实现并行运算和增量更新；( 3 ) s t i n g 方法仅扫描一遍数掘库以获得各单 元的统计信息，因此它产生聚类的时间复杂度为o ( n ) ：其中n 为所有对象 数。在产生聚类后进行查询的实际复杂度为0 ( g ) 其中g 为在最底层的所有 网格数，它通常比1 1 要小许多。 基于网格方法：c l i q u e c l i q u e ( c l u s t e r i n gi nq u e s t ) 聚类方法，将基于密度方法与基于网格方 法结合在一起。它对处理大数据库中的高维数据比较有效。c l i q u e 方法 能自动发现最高维中所存在的密集聚类。它对输入数据元组顺序不敏感； 也不需要假设( 数据集中存在) 任何特定的数据分布。它与输入数据大小呈 线性关系；并当数据维数增加时具有较好的可扩展性。但是在追求方法简 单化的同时往往就会降低聚类的准确性。 ( 5 ) 基于模型的方法( m o d e l b a s e dm e t h o d ) 基于模型的聚类方法就是试图对给定数据与某个数学模型达成最佳 拟合。这类方法经常是基于数据都是有一个内在的混合概率分布假设来进 行的。基于模型聚类方法主要有两种：统计方法和神经网络方法。 统计方法： 机器学习中的概念聚类就是一种形式的聚类分析。给定一组无标记数 据对象，它根据这些对象产生一个分类模式。与传统聚类不同，后者主要 识别相似的对象；而概念聚类则更进一步，它发现每组的特征描述；其中 6 哈尔滨一l ：稃大学硕十学协论文 每一组均代表一个概念或类，因此概念聚类1 8 】过程主要有两个步骤：首先 完成聚类：然后进行特征描述。因此它的聚类质量不再仅仅是一个对象的 函数；而且还包涵了其它因素，如所获特征描述的普遍性和简单性。大多 概念聚类都采用了统计方法，也就是利用概率参数来帮助确定概念或聚 类。每个所获得的聚类通常都是由概率描述来加以表示。 c o b w e b 是一个常用的且简单的增量式概念聚类方法。它的输入对象 是采用符号量( 属性一值) 对来加以描述的。c o b w e b 方法采用分类树的形 式来创建一个层次聚类。c o b 、忱b 的局限性有以下几点：首先它是基于各 属性的概率分布均是相互独立的假设。由于属性问经常存在相互关联，因 此这种假设并不总是成立。同时聚类的概率分布表示使得它较难更新和存 储聚类。特别是在属性取值非常多的情况下。其原因就是计算时自j 和空间 复杂度并不仅依赖属性数目，而且也与属性耿值的个数相关。此外对于分 布异常的数据，所产生的分类树并不一定是平衡的，同时也会导致时| b j 和 空间复杂度急剧增大。 神经网络方法： 神经网络聚类方法是将每个聚类描述成一个例证( e x e m p l a r ) 。每个例 证作为聚类的一个“典型”；它不必与一个示例或对象相对应。可以根据 新对象与哪个例证最相似( 基于某种距离计算方法) 而将它分派到相应的 聚类中。可以通过聚类的例证来预测分派到该聚类的一个对象的属性。 神经网络聚类方法与脑处理具有较强的理论联系。但由于存在较长处 理时间和复杂数据中复杂关系问题，还需要做更多研究才能使这类方法适 合处理大数据库。 ( 6 ) 模糊聚类1 9 - o l 传统的聚类把每个样本严格地划分到某一类随着模糊集理论的提 出，传统聚类被推广为模糊聚类。在模糊聚类中，每个样本不再仅属于某 一类，而是以一定的隶属度属于每一类。换句话说，通过模糊聚类分析得 到了个样本属于各个类别的不确定性程度，即建立起了样本对于类别的不 确定性的描述，这样就更能准确地反映现实世界。 基于目标函数地模糊聚类方法首先由r u s p i n i 提出，但真正有效地算 法f c m 却是由d u n n 给出的。b e z d e k 将其进一步扩展，建立起了模糊聚 7 哈尔滨 程大学硕十学位论文 类理论。从此，该类模糊聚类蓬勃发展起来，目前已经形成了庞大地体系。 前四种聚类分析方法较为常见，下图展示了它们之间的层次关系： a l g o r i t h m ： 划分方法层次方法 密度方法网格方法 ，r 1 k k 中 分 汇 o p l l c s 心均裂聚 d b s c a nw a v ec l u s t e r 方 方 法 法 d e n c l u ec l i q u e 法 法 删晒c l u s t e r r 。一r c l i q u e 器li b 眦h ii c u r e i ：l a r a n s 图1 1 算法层次关系图 一些聚类算法集成了多种聚类方法的思想，所以有时将某个给定的算 法划分为属于某类聚类方法是困难的。此外，某些应用可能有特定的聚类 标准，要求综合多个聚类技术。 1 2 3 数据挖掘对聚类的要求 在数据挖掘领域，研究工作已经集中在为大数据量数据库的有效且高 效的聚类分析寻找适当的方法。活跃的研究主题集中在聚类方法的可伸缩 性，方法对聚类复杂形状和类型的数据的有效性，高维聚类分析技术，以 及针对大的数据库中混合数值和分类数据的聚类方法。 聚类是一个富有挑战性的研究领域，它的潜在应用提出了各自特殊的 要求。数据挖掘对聚类的典型要求如下： ( 1 ) 可伸缩性：许多聚类算法在小数据集合( 如：小于2 0 0 个数据对象) 哈尔滨1 ：稃人学硕十宁傍论文 上工作绲缀好；但怒，一个太规模数据库w 能包含成百上干万个对象，在 这样的大数据集合样本上：i 行聚类可能会蹲致有偏差的缩巢。我们需要具 有离度可搏绩蛙的浆类算法 l l 】。 ( 2 ) 处遵不同类型属性的能力：许多算法被设计用来聚类数值类型的 数据。但是，应用娜能要求聚类其他类型的数据，如：二既类型( b i n a r y ) ， 分类标称类型，序数垄( o r d i n a l ) 数据，或者这璧数据类型的混合。 ( 3 ) 发现任意形状的聚类：许多聚类算法基于欧几罩德或者曼哈顿距 离度量来决定聚类。基于这样静距离度量的算法趋匈子发残其有稽遥尺度 和密度的球状类。假是，个类可能是任意形状的。提出能发现任意形状 类的算法罴很重要的。 ( 4 ) 用鼍：决定输入参数的领域知识最小化【1 2 】：许多聚类算法在聚类分析 中瑟求用户输入一定的参数，饲翔希望产象的类麓数霞。凝类结累j c 孪手输 入参数十分敏感。参数通常很难确定，特别是对于包含高维对象的数据集 来说。这样不仅加蕊7 震户的负撵，也捷褥聚类的质量难戳控铡。 ( 5 ) 处理“噪声”( n o i s e ) 数据的能力；绝大多数现实中的数据库都包 含了孤立煮，缺失，或者锈误的数缀。一整累类冀法对予这样的数据敏感， 可能导致低质量的浆类结果。 ( 磅对予输入诡录静颓浮不敏黪：一骜浆类算法砖予输入数撂鲍j 羲穿 是敏感的。例如，间一个数掘集合，当以不同的顺序交给同一个算法时， 霉能釜成菱弱缀大能聚类绻莱。开发辩数瓣输入蹶彦不敏攥豹算法其存重 要的意义。 ( 7 商缳度( h i g hd i m e n s i o n a l i t y ) ：一令数据蓐袋者数撵仓痒霉缝包含 着千维或者属性。许多聚类算法擅长处理低维的数据，可能只涉及两到三 维。天类静蔽跨在簸多三绦蘸情魏下簸够缀好缝爨瑟聚类憝矮量。在裹缝 空间中聚类数据对象是非常有挑战性的，特别是考虑到这样的数椭可能分 毒津常稀骧，悉显蠢发镶豁。 ( 8 ) 基乎约束的聚类：现实世界的应用可能需癸在各种约束条件下进 嚣豢类。弦设稼静王终是在今辕枣孛秀绘定数鬟豹耋动提款援选搀安救 位鼹，为了做出决滗，你可以对住宅区进行聚类，同时考虑如城市的河流 露公路释，每令缝嚣戆客户要求等壤提。爨找到鼹潢足特定豹约慕，又具 9 哈尔滨t 程大学硕十学位论文 有良好聚类特性的数据分组是一项具有挑战性的任务。 ( 9 ) 可解释性和可用性：用户希望聚类结果是可解释的，可理解的， 和可用的。也就是说，聚类可能需要和特定的语义解释和应用相联系。应 用目标如何影响聚类方法的选择也是一个重要的研究课题。 1 2 4 聚类分析的新成果和发展趋势 在过去的几年中聚类分析发展方向有两个：加强现有的聚类算法和发 明新的聚类算法。现在已经有一些加强的算法用来处理大型数据库和高维 度数据例如小波变换使用多分辨率算法，网格从粗糙到密集从而提高聚类 类的质量。对于数据量大、维度高并且包含许多噪声的集合，要找到一个 全能的聚类算法是非常困难的。某些算法只能解决其中的- n 两个问题， 同时能解决三个问题的算法还没有。现在最大的困难是高维度( 同时包含 大量噪声) 数据的处理。 算法的可伸缩性是一个重要的指标。通过采用各种技术，一些算法具 有很好的伸缩性。这些技术包括：数据采样、信息浓缩、网格和索引。 c l a r a n s 是最早使用数据采样的算法，c u r e 使用优选的采样点。信息 浓缩技术在b i r c h 方法和d e c l u e 方法中得到应用。许多算法都使用 了索引技术，典型的有：b i r c h 方法、d b s c a n 方法、小波变换方法、 d e n c l u e 方法。d e n c l u e 方法、小波变换方法、s t i n g 方法和 c l i q u e 方法使用了网格技术。但是以上方法仍然不能很好地处理高维度 并且大数据量的集合。 近年来，出现了一些新的技术如：s t i n g + 方法引入了动态数据挖掘 触发器；m a f i a 方法引入间距尺寸自适应网格分割算法：o p t i g r i d 算法 使用迭代和网格等技术处理高维度数据。新技术的引进大大加强了聚类算 法的效能，尤其提升了处理高维度数据的能力。但是由于这些算法刚刚形 成，所以在某些地方还有待完善。 1 3 本文的主要工作及内容 本文阐述了数据挖掘中聚类分析方法的分类、主要问题与己有的解决 方案，在此基础上，着重对其中的基于k m e a n s 方法进行了改进。进行仞 l o 哈尔滨工程大学硕士学位论文 始中心点的选取，并在此基础上进行聚类。 本文主要研究工作，主要针对基于划分方法应用于聚类分析时所出现 的缺点和不足，借鉴基于贪心算法和基于最小生成树的方法【”1 ，对基于划 分方法中的k - m e a n s 算法进行了改进。新算法主要解决初始聚类中心点的 选择方面的问题，并进行了对比性试验，根据实验结果，分析了k 一均值 方法和新算法的优缺点，对研究工作进行了总结 哈尔滨t 程大学硕十学何论文 第2 章基于划分的聚类方法 2 1 划分聚类概述 划分聚类也叫分割聚类。给定一个n 个对象或元组的数据库，一个 划分方法通过优化一个评价函数构建数据的k 个划分，每个划分表示一个 聚类，并且k 竹。也就是说，它将数据划分为k 个组，同时满足( 1 ) 每个 组至少包括一个对象；( 2 ) 每个对象必须属于且只属于一个组。在某些模 糊划分技术中第二个要求可以放宽。一个好的划分的一般准则是：在同一 个类中的对象之间尽可能“接近”或相关，而不同类中的对象之间尽可能 “远离”或不同。为了达到全局最优，基于划分的聚类会要求穷举所有可 能的划分。目前，绝大多数应用采用了以下两个比较流行的启发式方法： ( 1 ) k - m e a n s 算法，在该算法中，每个类用该类中对象的平均值来表示。 ( 2 ) k - m e d o i d s 算法，在该算法中，每个类用接近聚类中心的一个对象来表 示。这些启发式聚类方法对在中小规模的数据库中发现球状类很适用。为 了对大规模的数据集进行聚类，以及处理复杂形状的聚类，基于划分的方 法需要进一步地扩展。 划分算法典型地采用两阶段反复循环过程：( 1 ) 指定聚类，即指定一 个数据对象到某一个聚类，使得它与这个聚类中心的距离比它与其它聚类 中心的距离要近；( 2 ) 修改聚类中心。算法的结束条件是不再有数据被重 新分配。可以选择一个反映聚类效果的目标函数，当函数达到最优解时满 足终止标准。这一类算法中，有的算法在对每一个数据对象的每一次指定 后就修改一次聚类中心( 如s o m 方法) ，有的算法当对所有的数据对象都 指定完后才修改一次聚类中心( 如k - m e a n s 、l b g 方法) ，所以对这一类 方法来说，存在两个基本问题，即：如何计算距离和如何修改聚类中心。 在计算距离时，对数值属性主要的方法是采用明考斯基距离l 中的欧氏距 离，而对符号属性则可以采用海明距离。 在数据规模比较小以及数据对象维数较低的情况下，传统的划分聚类 算法可以将数据全部读入到内存进行计算，而随着数据量地增加，需要和 哈尔滨【稃人宁硕十学能论文 磁擞进行多次数据交换，花费大量的i 0 时i 日j ；又由于划分聚类算法通常 霈黉犬鬃的距离计算( 数据对象之间以及窀们与聚类中心之间的) ，从而导 数邀行时间开销较大，效率较低。这崽接限制了它们在一些相关领域中的 嶷用性。如何对以惊人速度增长的数据爨进行聚类，如何提高算法的执行 效率以及可扩展性就成为了许多算法需要解决自勺闯题。 2 2 数据类型及相似度度量方法 2 。2 。l 聚类分毒厅孛酶数据类鍪 数据分析中的数据类蝥n 主要有两类。瑕设瓣个数据集进行聚类分 析，该数据集包含n 个对象，这些对象w 以怒入、树木、文件等等。基于 内存的聚类算法通常采用以下两种数据缡构： ( 1 ) 数据矩阵 数据矩阵是一个对象一属性结构，它其实趋一张关系表，每列代表对 象的一个属性，每行表示一个数据对象。舆肖m 个属性的1 1 个对象( 例如； 树术对象可以剩用n 1 个属性来描述，属设如：离度、种类等) 可以表示为 一个撑x r 矩阵来表示： a j l ： l ： + ：l k ， ( 2 ) 差异矩阵 麓异矩阵存储n 个对象两两之间的帽舜性。它是一个对象一对象结构， 熊液现形式是一个n 维矩阵。其中的撼个元素d ( ，_ ，) 表示对象i 和对 象j 之间的相异度。如下表示： o 矗( 3 ，2 ) 0 d ( n ，萄0 遴鬻骛嚣下，0 ) 是一令菲受数， 该数攥就越接近0 售；该数雍傻越大， 警露蒙i 箨黠象j 缓茂“接透”嚣， 虢震承瓣象i 和对象j 越不稳像。 d d 玲。眼m一讯 ，j。，。，k 哈尔滨f 程人学硕十宁何论文 由于有d ( i j ) = d ( j ，i ) ，且d ( i ，i ) = o ，因此，此矩阵可表示成下三角行列式的形 式。 通常，数据矩阵又可称为双模式( t w o m o d e ) 矩阵，差异矩阵则又可称 为单模式( o n e m o d e ) 矩阵。因为数据矩阵的行和列分别表示不同的实体， 而差异矩阵的行和列则表示的是同一实体。许多聚类算法都是基于差异矩 阵进行聚类分析的。如果数据是以数据矩阵的形式给出的，就要先将其转 换为差异矩阵，才能利用聚类算法对其进行处理。 2 2 2 聚类分析中的相似度度量方法 1 区间标度( i n t e r v a l s c a l e d ) 属性 所谓区间标度变量是一个线性标度的连续度量。典型的例子包括重量 和高度，经度和纬度坐标，以及大气温度。选用的度量单位将直接影响聚 类分析的结果。例如，将高度的度量单位由“米”改为“英尺”，或者将 重量的单位由“千克”改为“磅”，可能产生非常不同的聚类结构。一般 而言，所用的度量单位越小，变量可能的值域就越大，这样对聚类结果的 影响也越大。为了避免对度量单位选择的依赖，数据应当标准化a 标准化 度量值试图给所有的变量相等的权重。当没有关于数据的先验知识时，这 样做是十分有用的。但是，在一些应用中，用户可能想给某些变量较大的 权重。例如，当对篮球运动员进行聚类时，可能更愿意给高度变量较大的 权重。 实现度量值的标准化，一种方法是将原有度量值转换为无单位的值。 假设给定一个变量( 属性) f 的度量值，可以进行如下变换： ( 1 ) 计算平均的绝对偏差( m e a na b s o l u t ed e v i a t i o r l ) s l ： s z = ( i x i ，一m ，i + l x 2 f m i i + + i ，一m f i ) n ( 2 1 ) 此处的五，蜥是，的疗个度量值，竹是f 的平均值，即 m z = ( 毛，+ x 2 ，+ + 啼) 开 ( 2 2 ) ( 2 ) 计算标准化的度量值，或z s c o r e 值： 乃= ( 暂- m 1 ) s ( 2 3 ) 1 4 哈尔滨丁释大学硕十学位论文 其中，该平均值的绝对偏差s ，比标准的偏差具有更好的鲁棒性( 对含 有噪声的数据而言) 。在计算绝对偏差均值时，对均值的偏差ix f m ，i 并没 有进行平方运算，因此异常数据( 即孤立点) 的作用被降低。此外，还存在 一些更好的对偏差的度量方法，例如中值绝对偏差( m e d i a na b s o l u t e d e v i a t i o n ) ，但采用平均绝对偏差的优点在于孤立点的z s c o r e 值不会太 小，因此孤立点仍可被识别出来。 在标准化之后，或在无需标准化的特定应用中，由间隔数值所描述对 象之间的差异( 或相似) 程度可以通过计算相应两个对象之间距离来确定。 最常用的距离度量公式就是欧几里德距离( e u c l i d e a nd i s t a n c e ) ，具体定义 如下： d ( i ，) = ( i 薯l t 1 1 2 + l 五2 一x j 2 1 2 + + i x t 一x 胛1 2 ) 圹2 ( 2 4 ) 其中，i = “l ，而2 ，) ，_ ，= ( x f l ，x 脚，工，卅) ，分别表示一个m 一维的数 据对象。 另一个常用的距离计算方法就是曼哈坦( m a n h a t t a n ) 距离，它的具体计 算公式定义如下： d ( i ，j ) 爿x j l z 门l + l x j 2 一工，2 l + + i 】一x 肺j ( 2 5 ) 欧几里德和m a n h a t t a n 距离均满足距离函数的一些相关性质： d ( i ，_ ，) 2 0 ，表示数据对象之间距离为一个非负的数值。 d ( i ，_ ，) = 0 ，表示数据对象之间距离为0 。 d ( i ，_ ，) = d ( j ，f ) ，表示数据对象之间距离是对称函数。 d ( i ，歹) s d ( i ，矗) + d ( h ，) ，从数据对象i 到数据对象j 的直接距离小 于等于途经任何其他数据对象的距离( 三角不等式性质) 。其中，h 表示第三个数据对象。 而明考斯基( m i n k o w s k i ) 距离是欧几里德距离和曼哈坦距离的概化形 式，定义如下： d ( i ，) ；( i x j l x lr + i 2 一x ，2r + l 一x ，r ) l ，叮 ( 2 6 ) 此处的4 是一个正整数。显然，当q = 1 时，它表示曼哈坦距离；当a = 2 表示欧几里德距离。如果对每个变量( 属性) 根据其重要性赋予一个权重， 则得到如下计算公式： d ( i ，_ ，) = ( w l i 毛l z ，lr + lj 2 一x ，2r + i j 一x ，肿i 叮) ( 2 7 ) 哈尔滨t 程大学硕士学位论文 同理，对于m a n h a t t a n 距离和m i n k o w s k i 距离也可以引入权值表示属 性的重要性进行计算。 2 二元属性 二元属性仅取值0 或1 ，其中0 代表( 变量表示的) 状态不存在；l 代表相 应的状态存在。例如给定变量s m o k e r ，该属性( 变量) 描述了一个病人是否 吸烟情况。如：s m o k e r 为l 就表示病人吸烟，若s m o k e r 为0 ，就表示病人不 吸烟。如果按照间隔数值变量对二元变量进行处理，常常会导致错误的聚 类分析结果产生。因此需要采用特定方法计算二元属性所描述对象问的相 异度。 一种相异度计算方法就是根据二元数据计算差异矩阵。如果认为所有 的二元变量的权值均相同，那么就能得到一个2 x 2 条件表，如表2 1 所示。 表中q 表示在对象i 和对弱中均取l 的二元变量个数，r 表示在对象i 取1 而在 对象j 取0 的二元变量个数，s 表示在对象冲取0 而在对象j 中取i 的二元变量 个数，t 则表示在对象i 和对象j 中均取0 的二元变量个数。二元变量的总个数 为p ，那么就有：p 2 q + 7 + 5 + f 。 表2 12 x 2 条件表 1o合计 1 g ， 口+ r o sts + t 合计g + s ，+ fp 如果一个二元变量取0 或1 所表示的内容同样重要，那么该二元变量就 是对称的。如s m o k e r 就是对称变量，因为它究竟是用0 还是用1 来( 编码) 表 示个病人的吸烟( 状态) 并不重要。同样的基于对称二元变量所计算相应 的相似度称为恒定相似度( i n v a r i a n ts i m i l a r i t y ) ，无论如何对相应二元变量 进行编码并不影响到它们相似度的计算结果。对于恒定相似度的计算，最 常用的描述对象i 和对象j 之间相异度参数是简单匹配相关系数，它的具体 定义描述如下述公式所示。 1 6 哈尔滨工程大学硕十学位论文 iii i1 1 1 i i i e i # ；j i i i i i i i i i ；i i i i i i i i i i i 置 d ( i ，歹) = ( ，+ s ) ( q + r 十s + r ) ( 2 8 ) 如果一个二元变量取0 或1 所表示的内容的重要性是不一样的，那么就 称该：元变量是非对称的。例如：一种壤瘸的检查