（计算机软件与理论专业论文）三角不等式原理对聚类算法的改进.pdfVIP

摘要 聚类分析是数据挖掘中的一个重要研究领域，面对大规模的、高维的数据， 如何建立有效的聚类算法是一个研究热点。聚类将数据对象分组成若干个类或 簇，使得在同一个簇中的对象尽可能相似，而不同簇中的对象尽可能相异，是一 种无监督的分类方法。对聚类算法的进一步优化研究不仅有助于算法理论的完 善，更有助于算法的推广和应用。 顺序聚类算法不需要提前确定聚类个数，并且是一种非常直接和快速的算 法。但是当处理海量数据时，时间效率仍然有待提高。针对此问题，本文在两个 阈值的顺序聚类算法t t s a s 的基础上，提出一种新的顺序算法t it t s a s 。该算 法应用三角不等式原理，避免了t t s a s 算法中冗余的距离计算。实验结果证明 t it t s a s 算法相对于t t s a s 算法，在效率上有很大程度的提高，尤其对于高维 的大规模数据集，效果更是显著，随着聚类个数的增加，t l r r s a s 算法更有优 越性。并且聚类效果保持了t t s a s 算法的准确性。 三角不等式原理不仅可以改进顺序算法，只要基于欧式距离度量不相似性的 聚类算法，都可以通过三角不等式原理避免冗余的距离计算。k - m e a n s 是一种基 于划分的聚类算法，本文同样利用三角不等式原理节省了运行时间。实验结果证 明，该原理对k - m e a n s 算法的改进效果更是显著。 关键字三角不等式原理聚类算法顺序聚类t t s a s 卫皿s a s k - m e a n s a b s t r a c t c l u s t e ra n a l y s i si sa ni m p o r t a n tr e s e a r c hf i e l di nt h ed a t am i n i n g ，i ti sar e s e a r c h f o c u sh o wt os e tu pe f f e c t i v ec l u s t e ra l g o r i t h mi nt h ef a c eo ft h el a r g e - s c a l e ， h i g h - d i m e n s i o n a ld a t a s e t s c l u s t e rg r o u p st h ed a t a s e ti n t oc l a s s e so rc l u s t e r ss ot h a t o b j e c t sw i t h i nac l u s t e rh a v eh i g hs i m i l a r i t yi nc o m p a r i s o nt oo n ea n o t h e r , b u ta l e v e r yd i s s i m i l a rt oo b j e c t si no t h e rc l u s t e r s t h ef u r t h e ro p t i m i z a t i o no fc l u s t e r s a l g o f i t h r an o tm e r e l yf a c i l i t a t e st h ec o m p l e t i o n o ft h e o r yo fa l g o r i t h m ，b u ta l s o f a c i l i t a t e sp o p u l a r i z a t i o na n da p p l i c a t i o no f t h ea l g o r i t h m s e q u e n t i a la l g o r i t h md o e sn o tn e e dt oc o n f i r mc l u s t e r sn u m b e ra h e a do ft i m e ， a n di sak i n do fv e r yd i r e c ta n df a s tc l u s t e ra l g o r i t h m b u tw h e nh a n d l i n gt h el a r g e n u m b e r so fd a t a ，t h ee f f i c i e n c ys t i l ln e e d st oi m p r o v e t ot h i s ，o nt h eb a s i so ft h e t w o - t h r e s h o l ds e q u e n t i a l a l g o r i t h ms c h e m e i r s a s ，w ep u tf o r w a r d an e w s e q u e n t i a la l g o r i t h mt i - _ r r s a s t h i sa l g o r i t h m a v o i d s u n n e c e s s a r y d i s t a n c e c a l c u l a t i o n sb ya p p l y i n gt h et r i a n g l ei n e q u a l i t y e x p e r i m e n t ss h o wt h a tt h en e w a l g o r i t h mi sm o l ee f f e c t i v ef o rd a t a s e t so fm o r ed i m e n s i o n s ，a n db e c o m e sm o r ea n d m o r ee f f e c t i v ea st h en u m b e ro f c l u s t e r si n c r e a s e s t h er e s u l t sh a v ek e p tt h ea c c u r a c y o f i r s a sa l g o r i t h m t h et r i a n g l ei n e q u a l i t yp r i n c i p l en o to n l ym a yi m p r o v et h es e q u e n t i a la l g o r i t h m ， a l lt h ea l g o r i t h m st h a tm e a s u r ed i s s i m i l a r i t yb a s e do ne u c l i d i a nd i s t a n c e ，t h e r e x l t m d a n e yo fd i s t a n c ec o m p u t a t i o n sm a y b ea v o i d e dt h r o u g ht h et r i a n g l ei n e q u a l i t y p r i n c i p l e k - m e a n si sap o p u l a rp a r t i t i o nc l u s t e ra l g o r i t h m ，t h ea r t i c l ea v o i d sm a s s i v e d i s t a n c ec o m p u t a t i o n st os a v et h er u n n i n gt i m eb yu s i n gt h em a n g l ei n e q u a l i t y p r i n c i p l e ，s i m i l a r l y t h ee x p e r i m e n t a l r e s u l tp r o v e dt h a t , t h ei m p r o v e m e n tt ot h e k - m e a n sa l g o r i t h mi sr e m a r k a b l e k e y w o r d st r i a n g l ei n e q u a l i t y c l u s t e ra l g o r i t h m s e q u e n t i a la l g o r i t h m t t s a st ir r s a s 原刨性声翡 本人郑重声明：本入所星交的学位论文，是在导j j 曰j 的指导下独立 进行研究所取得的成果。学位论文中凡弓 用他人已经发表或来发 表的成果、数据、观点等，均已明确注明出处。除文中已经注明 弓【用的内容外，不包含任何其他个人或集体已经发表或撰写过的科研 成果。对本文的研究成果做出重要贡献的个人和集体，均已在文中以 明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：五榔 日 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：危酾岛醢一导师签名： ， 日期：皂! b 番竹文掌 三角不等式原理对聚类算法的改进 第一章绪论 1 1 本文选题背景及研究意义 聚类是一种重要的数据分析技术，搜索并识别一个有限的种类集合或簇集 合，从而描述数据。聚类分析也已经广泛地应用到诸多领域中，包括模式识别、 数据分析、图像处理以及市场研究【l 】。特别是随着国际互联网和基于h t t p 协议 的w e b 技术的飞速发展，网上文本信息的激增，搜索引擎，文本挖掘，信息过 滤和信息检索等的研究出现了前所未有的高潮。而聚类作为一种知识发现的重 要方法，也日益广泛和中文信息处理技术相结合，应用于网络信息处理中以满足 用户方便快捷地从互联网获得自己需要的信息资源n 在商务上，聚类能帮助市场分析人员从客户基本信息库中发现不同的客户 群，并且用购买模式来刻画不同的客户群的特征。在生物学上，聚类能用于推 导植物和动物的分类，对基因进行分类，获得对种群中固有结构的认识。聚类 在地球观测数据库中相似地区的确定，汽车保险单持有者的分组，及根据房屋 的类型、价值和地理位置对一个城市中房屋的分组上也可以发挥作用。 “物以类聚，人以群分”，聚类技术的出发点也是如此，把大数据集合中相 似度较高的对象聚集在一起，而把相似度较低的对象区分开来。从而使得获得的 聚类结果与人们的判断相一致。聚类需要解决的问题是，将已给定的若干无标记 的模式聚集起来使之成为有意义的聚类 3 1 。但是，如果人们对信息聚类处理的方 式依然依靠人工方式，根本无法完成。所以利用计算机和聚类技术处理数据势在 必行，在现实生活中有着很重要的意义。 1 2 聚类分析 聚类分析是一种重要的人类行为，通过聚类，人能够识别密集的和稀疏的区 域，因而发现全局的分布模式，以及数据属性之间的有趣的相互关系。作为一个 数据挖掘的功能，聚类分析能作为一个独立的工具来获得数据分布的情况，观察 蔺哪文， 三角不等式原理对聚类算法的改进 每个簇的特点，集中对特定的某些簇进行特定的分析。此外，聚类分析可以作为 其他算法，如特征和分类等的预处理步骤，这些算法再在生成的簇上进行处理。 在数据挖掘领域，研究工作已经集中在为大型数据库寻找有效的分析方法，聚类 分析已经成为该领域中一个非常活跃的研究课题。 1 2 i 聚类的定义 聚类( c l u s t e r i n g ) 是一种常见的数据分析工具，简单地说，就是将物理或 抽象对象的集合分组成为由类似的对象组成的多个类或簇( c l u s t e r ) 的过程。 由聚类所生成的类是对象的集合，这些对象与同一个类中的对象彼此相似，与 其它类中的对象相异。在许多应用中，可以将一个类中的数据对象作为一个整 体来对待。 我们做数学描述如下 4 ；l ：设x 是数据集，即x = 而，x ：，l ，x n ) ，我们定义， 将x 分割成m 个集合，也就是m 个聚类c l ，c 2 ，lc m ，使其满足下面三个条件： 1 e o ，f = l ，2 ，l ，m 2 u c 。= x h l 3 q ic j = o ，i j , i ，j = 1 ，l 册 由前两个条件可知，数据集中的每个数据必定属于某一个类；由第三个条 件可知，数据集x 中的每个数据最多只属于一个类，这种聚类类型称为硬的或 脆的。 在模糊集中，有另一种定义，模糊隶属函数值具有集合的数学特性，事例 中的聚类可能没有精确的定义。每一个向量同时属于多个聚类而达到某种程度， 与某个类的隶属程度高表示与该类相似，隶属程度低表示不相似。 2 魂哪土掌 三角不等式原理对聚类算法的改进 1 2 2数据挖掘对聚类的要求 聚类是一个富有挑战性的研究领域，活跃的研究主题集中在聚类方法的可 伸缩性，方法对聚类复杂形状和类型的数据的有效性，高维聚类分析技术，以 及针对大型数据库中混合数值和分类数据的聚类方法。用户希望聚类结果是可 解释的、可理解的、可用的。也就是说，聚类可能需要和特定的语义解释和应 用相联系。应用目标如何影响聚类方法的选择也是一个重要的研究课题。 那么一个好的聚类方法应该满足什么条件呢? 现在通用的聚类标准都是从 几个方面来衡量，而没有完全使用量化的客观标准。下面给出了六条关于聚类 的主要标准”： 1 处理大的数据集合的能力； 2 处理任意形状，包括有间隙的和嵌套的数据的能力； 3 算法处理的结果与数据输入的顺序是否相关，也就是说算法是否独立于数 据输入顺序； 4 处理数据噪音的能力； 5 需不需要预先知道聚类个数，需不需要用户给出领域知识； 6 算法处理有很多属性的数据的能力，也就是对数据维数是否敏感。 对于一个聚类算法的优劣可以从这几个方面综合衡量。 1 3 聚类分析中的数据类型 在数据挖掘领域，聚类分析中的数据呈现多样性。经常出现的数据类型有区 间标度变量、二元变量、标称型、序数型和比例标度型变量，或这些变量类型的 组合等。对于不同的类型，对象间的相异度有着不同的度量方法。 1 3 1 区间标度变量 区间标度变量是一个粗略线性标度的连续度量。如重量和高度，经度和纬度 坐标以及大气温度等。为了避免对度量单位选择的依赖，数据应当标准化。标准 化度量值试图给所有的变量相等的权重。可以进行如下变换： 两_ 土， 三角不等式原理对聚类算法的改进 1 计算平均的绝对偏差s ： s = 击( i 一一m 屯一朋i + l + l 矗一m i ) 其中而，屯，l 矗是n 个度量值，m 是它们的平均值，即 m ：三( 而+ x 2 + l + 靠) l l 2 计算标准化的度量值，z - s c o r e ： 2x i - - m s 平均的绝对偏差比标准差对于孤立点具有更好的鲁棒性。在标准化处理后， 当然在某些应用中不需要标准化，对象间的相似度是基于距离来计算的。最常见 的距离度量方法是欧几里德距离，它的定义如下： d ( i ，舻、厩i 丁而j 哥五可而 这里的f - 嘛。，而：，l ，靠) 和，= ( 。，_ 2 ，l ，b ) 是两个h 维的数据对象。 另一个著名的度量方法是曼哈坦距离，其定义如下： d ( f ，) 爿h 一0 i i + l 耳2 一x j 2 i + l + i 一b 这两种距离度量方法都满足对距离函数的如下要求：距离是一个非负的数 值：一个对象与自身的距离是0 ；距离函数具有对称性；从一个对象到另一个对 象的距离不会大于途经任何其他对象的距离，即三角不等式原理，距离的这个性 质很重要，本论文对聚类算法的改进也是基于该性质减少距离计算次数的，从而 减少运行时间，提高速度的。 明考斯基距离是欧几里得距离和曼哈坦距离的概化，其定义如下： 4 硇竹土， 三角不等式原理对聚类算法的改进 d ( i ，- ，) = ( 1 葺z 一1 1 9 + i 而2 一一2r + l + l 靠一br ) ”9 这里g 是一个正整数。当g = 1 时，表示曼哈坦距离，当g = 2 时，表示欧几里得 距离。 还有特殊领域的距离表示，如字符串处理领域的基于最小数目原子操作的 编辑( e d i t ) 距离和基于词根的全纯( h o l o m o r 州c ) 距离【6 1 。 1 3 2 二元变量 一个二元变量只有两个状态：o 或1 ，0 表示该变量为空，1 表示该变量存在。 二元变量分为对称二元变量和非对称二元变量。 对称二元变量的两个状态是等权重的。如性别变量，1 表示男人，0 表示女人。 评价两个对象f 和- ，之间相异度的最著名的系数是简单匹配系数，其定义如下： 删) = 羔t g + ，+ j + 其中g 是对象f 和_ ，值都为1 的变量数目，r 是对象f 值为1 而对象- ，值为0 的变 量数目，s 是对象i 值为o 而对象_ ，值为l 的变量数目，f 是对象f 和，值都为0 的 变量数目。 非对称二元变量的两个状态是不对称的。如h i v 检测结果，l 表示阳性，0 表 示阴性。评价两个对象f 和，之间相异度的最著名的系数是j a c c a r d 系数，在它的 计算中，负匹配的数目，被认为是不重要而忽略，其定义如下： m 舻再r + i s 5 准| 土宰 三角不等式原理对聚类算法的改进 1 3 3 标称型、序数型和比例标度型变量 1 标称变量 标称交量是二元变量的推广，它可以具有多个状态值。如m a p - c o l o r 是一个 标称变量，它可能有五个状态：红色、黄色、绿色、粉红色和蓝色。两个对象f 和 _ ，之间的相异度可以用简单匹配方法，其定义如下： d ( i ，) ：生兰 p 其中m 是f 和，取值相同的变量数目，p 是全部变量的数目。 2 序数型变量 离散的序数型变量类似标称变量，但其状态的排序是有意义的，如比赛中的 排名：金牌、银牌和铜牌。其相异度计算包括如下步骤： ( 1 ) 将变量值用l m 替代，其中m 为有序状态的个数。 ( 2 ) 将每个变量的值域映射到 o ，l 】上，使每个变量有相同的权重。 ( 3 ) 采用区间标度变量的相异度计算方法。 3 比例标度型变量 比例标度型变量在非线性的标度取正的度量值。典型的例子包括细菌数目的 增长、放射性元素的衰交。根据实际情况将比例标度型变量变换成区间标度型变 量，再计算相异度。 1 3 4 混合类型的变量 在许多真实的数据库中，对象是被混合类型的变量描述的。假设数据集包含 p 个不同类型的变量，对象f 和_ ，之间的相异度d ( i ，d 定义为： 6 ，枷 | r 三角不等式原理对聚类算法的改进 圭毛t ，也t 力 d ( i ，) = 型了一 岛， f - 1 如果靠或b 缺失，或者勺= h = o ，且变量，是不对称得二元变量，则指 示项岛门= o ；否则，指示项岛力= l 。略门根据其具体类型计算。 上述几种数据类型存在于以结构化数据为主的关系数据库，事务数据库，和 数据仓库中。随着数据处理工具、先进数据库技术以及万维网( w w w ) 技术的 迅猛发展，大量形式各异的复杂类型的数据不断涌现。如空间数据、多媒体数据、 时间序列数据、文本数据和w e b 数据。这些数据通常需要采用各种不同的方法 将其转化为上述五种数据类型后，再进行聚类分析。 1 4 目前主要聚类算法及其存在问题 目前在文献中存在大量的聚类算法，算法的选择取决于数据的类型、聚类的 目的和应用。以下将讨论在数据挖掘领域中得到广泛应用的一些聚类方法，大体 上可以分为五大类。 1 4 1 划分方法( p a r t i t i o n i n gm e t h o d ) 给定一个包含n 个数据对象的数据集，一个划分方法构建数据的k ( k 以) 个 划分，每个划分表示一个类，也就是说，它将数据划分为k 个组，同时满足如下 的要求：每个组至少包含一个对象；每个对象必须属于一个组。给定要构建的划 分的数目k ，划分方法首先创建一个初始划分。然后采用一种迭代的重定位技术， 尝试通过对象在划分间移动来改进划分。为了达到全局最优，基于划分的聚类要 求穷举所有可能的划分。实际上，绝大多数应用采用了以下两个比较典型的划分 方法：k - m 既, m s 和k - m o d e s 。 k - m e a n s 算法：这是实际中使用最多的算法，而且由于算法的简单性和很 7 跏 亨 三角不等式原理对聚类算法的改进 好的空间时间复杂度而在处理大数据的领域得到极大应用。k - m e a n s 算法以每 个聚类的算术平均点为聚类的中心来计算平方误差 ，故此得名。 k - m o d e s 方法，每个类用接近该类中心的对象来表示，因此称之为k m o d c s 方 法。k - m o d e s 方法可以看作是k - m e a n s 方法的改进方法，因为中心点不像平均值那 么容易被极端数据影响，所以当存在噪声和孤立点数据时，k - m o d e s 方法比 k - m e a n s 方法更强壮。但是，k - m o d e s 方法也要求用户提前指定聚类数目k ，并且 该方法的执行代价比k m e a n s 方法高。 1 4 2 层次方法( h i e r a r c h i c a lm e t h o d ) 对给定的数据对象集合进行层次的分解。根据层次的分解如何形成，层次的 方法可以分为凝聚和分裂两大类。凝聚的方法，也称为自底向上的方法，一开始 将每个对象作为单独的一个类，然后相继地合并相近的类，直到所有的类合并为 一个，或者达到一个终止条件。分裂的方法，也称为自顶向下的方法，一开始将 所有的对象置于一个类中。在迭代的每一步中，类被分裂为更小的类，直到每个 类只包含一个对象为止，或者达到一个终止条件。在凝聚或者分裂层次聚类方法 中，通常以用户定义希望得到的类的数目作为结束条件。 层次聚类方法虽然简单，但经常会遇到合并或分裂点选择的困难。这样的决 定是非常关键，因为一旦一组对象被合并或者分裂，下一步的处理将在新生成的 类上进行。已做的处理不能被撤销，类之间也不能交换对象。如果在某一步没有 很好地作出合并或分裂的决定，可能会导致低质量的聚类结果。而且，这种聚类 方法不具有很好的可伸缩性，因为合并或分裂的决定需要检查或估算大量的对象 或簇。 因此人们提出众多改进的层次聚类算法以改进层次聚类方法的性能。 b i r c h l 8 1 是一种综合的方法，首先建立存放于内存的c f ( c l u s t e rf e a t u r e ) 树， 再采用某个聚类算法对c f 树的叶结点进行聚类。c u r e 嘲( c l u s t e r i n gu s i n g r e p r e s e n t a t i v e s ) 方法不用单个中心或对象来代表一个类，而是选择数据空间中 固定数目的具有代表性的点代表一个类，可以识别复杂形状和大小不同的类，而 两坩 宰 三角不等式原理对聚类算法的改进 且能很好地过滤孤立点。在c u r e 方法的基础上，又提出了适用于分类数据的 r o c k 1 0 1 方法。基于对c u r e 和r o c k 缺点的观察，提出了采用动态模型的 c h a m e l e o n 川方法，其同时考虑对象问的互连性和类间的近似度，在发现高质量 的任意形状的聚类方面有更强的能力。 上述层次聚类方法虽然有效提高了算法的聚类能力，但大大延长了算法的执 行时间，因此人们又提出新的算法，但都是对算法执行效率和聚类能力的折中， 为提高算法效率而降低了聚类结果的精确性。 1 4 3 基于密度的方法( d e n s i t y - b a s e dm e t h o d ) 绝大多数划分方法基于对象之间的距离进行聚类，这样的方法只能发现球状 的类，而在发现任意形状的类上遇到困难。因此，出现了另一类基于密度的聚类 方法，其主要思想是：只要邻近区域的密度，即，数据点的数目，超过某个闺值， 就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域内必 须至少包含某个数目的点。这样的方法可以过滤“噪声”数据，发现任意形状的 类。代表算法有d b s c a n 算法【1 2 l ，o p t i c s 算法和d e n c l u e 算法1 4 肄。 d b s c a n 算法将密度足够大的那部分记录组成类，使用了e p s 和m i n p t s 两个 全局变量，d b s c a n 需要由用户主观来选择参数，从而影响了最终的聚类结果。 如果采用了空间索引，d b s c a n 的计算复杂度是o ( n l o g n ) ，这里一是数据库中 对象的数目，否则计算复杂度为o ( n 2 ) 。 对于参数的设置通常是依靠经验，难以确定。尤其是对于真实的高维数据集 合而言。o p t i c s 算法克服了d b s c a n 算法的缺点，是一种顺序聚类的方法。 o p t i c s 没有显式地产生一个数据集合，它为自动和交互的聚类分析计算一个类 秩序。这个秩序代表了数据的基于密度的聚类结构。它包含的信息，等同于从一 个宽广的参数设置范围所获得的基于密度的聚类。 d e n c l u e 是一个基于一组密度分布函数的聚类算法，该算法主要基于下面 的想法：每个数据点的影响可以用一个数学函数来形式化地模拟，它描述了一个 9 蔺啊 孽 三角不等式原理对聚类算法的改进 数据点在邻域内的影响，被称为影响函数；数据空间的整体密度可以被模型化为 所有数据点的影响函数的总和；然后聚类可以通过确定密度吸引点来得到，这 里的密度吸引点是全局密度函数的局部最大。 基于密度的方法与其他方法的一个根本区别是，它不是基于各种各样的距 离，而是基于密度，这样就能克服基于距离的算法只能发现类圆形的聚类的缺点。 但算法计算复杂度高，而且对于密度分布不均的数据集，往往得不到满意的聚类 结果：多数基于密度的聚类方法对参数都很敏感，参数设置的细微不同可能导致 差别很大的聚类结果。 1 4 4 基于网格的方法( g r i d b a s e dm e t h o d ) 基于网格的方法把对象空间量化为有限数目的单元，形成一个网格结构。所 有的聚类操作都在这个网格上进行。这种方法的主要优点是它的处理速度很快， 其处理速度独立于数据对象的数目，只与量化空间中每一维的单元数目有关。但 这种算法效率的提高是以聚类结果的精确性为代价的。 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 ) 算法【l5 l 是一种基于网格的多分辨率方法。 它将空间区域划分成为矩形单元，针对不同级别的分辨率，通常存在多个级别的 矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层 的单元。关于每个网格单元属性的统计信息被事先计算和存储。这些统计参数对 于查询处理是有用的。该种方法效率高，而且网格结构有利于并行处理和增量更 新，但其降低了聚类的质量和精确性。 w a v e c l u s t e r 1 6 】是一个多分辨率的基于网格和密度的算法，它首先通过在数 据空间上强加一个多维网格结构来汇总数据，然后采用一种小波变换来变换原特 征空间，在变换后的空间中找到密集区域。w a v e c l u s t e r 符合一个好的聚类算法 的许多要求：速度很快，计算复杂度是0 ( 九) ，能有效地处理大数据集合，发现 任意形状的簇，成功地处理孤立点，对于输入顺序不敏感，不要求指定诸如聚类 数目或邻域半径等输入参数。 两州 | r 三角不等式原理对聚类算法的改进 c l i q u e ( c l u s t e r i n gi nq u e s t ) 旧综合了基于密度和基于网格的聚类方法， 对于大型数据库中的高维数据的聚类非常有效，对数据的输入顺序不敏感，无需 假设任何规范的数据分布，对数据的维数和规模有良好的可伸缩性；但由于方法 大大简化，聚类结果的精确性可能会降低。 1 4 5 基于模型的方法( m o d e l b a s e dm e t h o d ) 基于模型的方法为每个类假定一个模型，寻找数据对给定模型的最佳拟合。 基于模型的方法主要有两类：统计学方法和神经网络方法。 ( 1 ) 统计学方法 概念聚类是机器学习中的一种聚类方法，给出一组未标记的对象，它产生对 象的一个分类模式。与传统的聚类不同，概念聚类除了确定相似对象的分组外， 还向前走了一步，为每组对象发现了特征描述，即每组对象代表了一个概念或类。 因此，概念聚类是一个两步的过程：首先进行聚类，然后给出特征描述。在这里， 聚类质量不再只是单个对象的函数，而且加入了如导出的概念描述的简单性和一 般性等因素。常用方法包括c o b w e b 18 1 ，c l a s s i t 1 9 1 ，及a u t o c l a s s 2 0 喀。 ( 2 ) 神经网络方法 神经网络方法将每个簇描述为一个标本。标本作为聚类的原形，不一定对应 一个特定的数据实例或对象。根据某些距离度量，新的对象可以被分配给标本与 其最相似的簇。被分配给一个簇的对象的属性可以根据该簇的标本的属性来预 测。神经网络聚类的两个比较著名的方法为：竞争学习和自组织特征映射【2 2 。 竞争学习采用若干个单元的层次结构，它们以一种“胜者全取 ( w i n n e r - t a k e - a 1 1 ) ”的方式对系统当前处理的对象进行竞争。自组织特征映射 ( 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 ) ，以其所具有的诸如拓朴结构保持、概 率分布保持、无导师学习及可视化等特征，广泛应用于聚类分析之中。传统的 s o m 网络存在着许多不足，如网络结构固定、训练时间长等缺点。为此，人们 提出了多种在训练过程中动态确定网络形状和单元数目的解决方案，对s o m 网 硇_ ， 三角不等式原理对聚类算法的改进 络的聚类性能都有较大的改善。另外也有很多模型，其结构不仅动态生成，而且 构成了树形层次结构，可以发现不同类间的层次信息。 除了上述五大类方法以外，在各种文献中还存在着大量的聚类方法。如本文 下面重点研究的顺序聚类算法；基于遗传算法的聚类方法；基于粗糙集的聚类算 法【2 3 l ；模糊聚类方法：处理高维数据的聚类方法：处理大规模数据的聚类方法； 处理动态数据的聚类方法：以及将基本聚类方法与各种新技术相结合的聚类方法 等。 聚类分析具有极其广泛的应用，故而成为数据挖掘领域中的一个研究热点， 各种各样的聚类算法不断出现在大量文献中，有的文献对各种算法进行比较研 究，有的对原算法的聚类质量进行改进，希望能得到更满意的聚类结果，有的对 聚类算法时间复杂度进行研究，希望提高运行效率等。 1 5 本文的研究内容 本文研究了数据挖掘领域中的聚类算法，具体内容如下： 第一章为本文绪论部分。首先分析了本文的选题背景以及研究意义；然后简 单介绍了什么是聚类分析，聚类的定义、数据挖掘对聚类的要求、聚类分析中的 数据类型；全面介绍了几种主要的聚类算法以及目前的研究进展，并指出其中存 在的问题：最后总结了本文的主要研究工作。 第二章为本文重点内容，提出用三角不等式原理改进两个阈值的顺序聚类算 法t t s a s ，我们将改进的t t s a s 算法命名为1 1 。首先介绍了三种顺序聚_ttsas 类算法的基本思想，并说明要对其改进的理由；然后详细阐述了三角不等式原理， 针对应用，提出相应定理以及推论，并对其作了严格证明；接着应用以上定理、 推论，给出了t i j 盯s a s 算法的核心步骤，并对其做了详细解析；之后以实验结 果证明改进算法的优越性；最后说明该算法仍然存在的局限性，并对外来工作做 了展望。 第三章论述了用三角不等式原理改进的k - m e r e s 算法。首先概述了划分聚类 趣竹土， 三角不等式原理对聚类算法的改进 以及其中的k m e a n s 算法原理，接着指出k - m e a n s 算法目前存在的三大问题，尤其 第三个问题，即处理大规模数据集时，算法的时间开销相当大，所以应用三角不 等式原理对k m e a n s 算法作了改进，试验结果证明，改进算法相对于原算法具有 很强的优越性，运行速度提高了许多倍。 第四章总结全文并展望。本章对本文所做的主要工作进行了总结，并对研究 中存在的问题和有待于进一步研究的问题进行了分析，在此基础上对数据挖掘中 聚类问题的研究前景进行了展望。 蔫一土宰 三角不等式原理对聚类算法的改进 第二章用三角不等式对顺序聚类算法 t t s a s 的改进 2 1 顺序聚类算法 2 1 1 顺序聚类算法三种模式 顺序聚类算法是一种非常直接和快速的算法，基本顺序聚类算法( b s a s ) ， 需要用户定义不相似性阈值口以及允许的最大聚类数g 。算法的基本思想是， 考虑每个新向量，根据向量到已经形成聚类的距离，将它分配到一个已有聚类 中，或者一个新生成的聚类中。所以，对于向量的分配是在最后的聚类形成之 前决定的，而最后的聚类是在所有的向量都处理后才形成的。为克服这个缺点， 便对b s a s 做了改进，即m b s a s 口“，该算法分两个阶段，第一阶段将那些到 已经形成聚类的距离小于不相似性阈值占的向量分配到聚类中形成类，即该阶 段决定了聚类数并冻结；第二阶段，将那些到已经形成聚类的距离大于不相似 性阈值口而没有分配的向量第二次参与算法，并分配到适当的类中，这样，对 每个向量作决定时考虑了所有的聚类。 显然，b s a s 和m b s a s 都依赖于不相似性阈值口，该值直接影响聚类数量， 日选得太小，会生成不必要的聚类，选得太大，聚类的数量又会不够，这两种 情况，都会产生对数据集无意义的聚类结果。还有一个重要的依赖因素就是向 量参与算法的顺序，不同的向量顺序会导致完全不同的聚类结果。为解决这些 问题，通过使用两个阈值b 和嚷来定义一个“灰度”区域。如果向量z 和最近 的聚类c 的不相似性d 沁c ) 小于b ，n x 被分配到类c ；如果d ( x ，c ) 大于岛，则 新生成一个聚类，x 分配到其中。否则，如果最s d ( x ，c ) s 岛，即x 处于灰度区 域，存在不确定性，其分配延迟到有足够的信息后再决定，这样，该算法对数 据的参与顺序不再非常敏感。这就是两个闽值的顺序聚类算法( t t s a s ) 【4 2 5 1 。 1 4 硇_ 文掌 三角不等式原理对聚类算法的改进 2 1 2 对t t s a s 算法改进的理由 顺序聚类算法至少将所有特征向量使用一次或几次，且不需要提前给定聚 类个数【45 1 。但是对于大规模的数据集，该算法的速度仍然比较慢，本文主要 的贡献是对t t s a s 算法在时间效率上进行了改进，使得其能更有效地处理高维 的大数据集。如果一个数据点远离一个聚类，就没必要计算这两者之间的精确 距离，以确定该点不属于这个类。要对一个数据集进行准确的聚类，就必须处 理其中的每个数据点，将它聚入与其最相近的类中。而在此过程中，标准的 t t s a s 算法的许多数据点和类的不相似性的计算是冗余的，本文利用三角不等 式原理减少这些冗余计算，提出t it t s a s 算法，使得速度相对于原算法有很 大程度的提高，尤其对于高维的大数据集，效果更是明显。t it t s a s 算法的 核心思想是：对于一个待处理的数据点，没必要计算出其与所有已形成类的距 离，而是应用三角不等式原理，通过类间距离以及某些聚类和该点间距离的关 系，避免该点和其他聚类间距离的计算。当数据集相当大并且数据的维数较高 时，节省的时间是相当可观的，因此可以大大提高t t s a s 算法的时间效率。并 且t it t s a s 算法保持了t t s a s 在聚类效果上的准确性。 我们希望在保持t r s a s 算法聚类效果的基础上，提高时间效率。因此，我 们需要提高算法的速度，但是必须满足下边三个特性：第一，任何一个点都可 以作为初始中心。第二，只要不相似性阈值不变，总能产生与原算法同样的聚 类结果。第三，算法可以使用任何距离的度量标准，不局限于欧几里德距离。 事实上，我们的算法完全满足上述第二个条件：对于任何数据集，只要阈值不 变，我们的算法总能产生与标准t r s a s 算法相同的聚类结果，并且聚类中心的 位置也完全一致。因为各个领域都有特定的距离度量标准，因此第三个条件也 是非常重要的。在本文中采用欧式距离，两个向量x , y 的欧式距离一般记为 d ( x ，力。 和土掣 三角不等式原理对聚类算法的改进 2 2 三角不等式原理 2 2 1 公理