聚类分析中相似性测量方法的研究

第７卷第２期　２００２年４月　株洲师范高等专科学校学报　Ｊ０ＵＲ　ＡＩ　ＯＦ　ＺＨＵＺＨ０Ｕ　ＴＥＡＣＨＥＲＳ　Ｃ０ＬＬＥＧＥ　ｖ０Ｌ　７　Ｎｏ．Ｚ　ＡＤｒ　２００２　聚类分析中相似性测量方法的研究　易华容　（抹洲师范高等专科学校计算机系，湖南抹洲４１２００７）　摘要：采类是数据挖掘中的主要方法．讨话了在太多数采类算法中的相似性测量方法．并咀属　性的妻型作为选择相似性的标准．阐述了用于数值属性，符号属性厦混合属性相韫性剥量方法．　美量词：信息技术ｌ采妻分析；相似性剥量；数据把掘　中圈分类号：ＴＰ２０１．６　文献标识符：Ａ　文章编号：１００９—１４３２（２００２｝０２—００４３－－０４　Ｒｅｓｅａｒｃｈｅｓ　ｉｎｔｏ　ｔｈｅ　Ｍｅｔｈｏｄｓ　ｏｆ　Ｓｉｍｉｌａｒｉｔｙ　Ｍｅａｓｕｒｅｍｅｎｔ　ｉｎ　ｔｈｅ　Ｃｌｕｓｔｅｒｉｎｇ　Ａｎａｌｙｓｉｓ　Ｙ１　Ｈｕａ—ｒｏｎｇ　（Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ－Ｚｈｕｚｈｏｕ　Ｔｅａｃｈｅｒｓ　Ｃｏｌｌｅｇｅ．Ｚｈｕｚｈｏｕ，Ｈｕｎ，ａｎ　４１２００７．Ｃｈｉｎａ）　Ａｈｓｌｒｕｅｔ：Ｃｌｕｓｔｅｒｉｎｇ　ｉｓ　ａ　ｍａｊｏｒ　ｍｅｔｈｏｄ　ｏｆ　ｄａｔａ　ｍｉｎｉｎｇ．Ｔｈｉｓ　ｐａｐｅｒ　ｄｉｓｃｕｓｓｅｓ　ｔｈｅ　ｍｅｔｈｏｄｓ　ｏｆ　ｓｉｍｉｌａｒｉｔｙ　ｍｅａｓ—　ｕｒｅｍｅｎｔ　ｏｆ　ｎ￣ｏｓｔ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍｓ－ａｎｄｔａｋｉｎｇｔｈｅｔｙｐｅ　ｏｆ　ａｔｔｒｉｂｕｔｅ　Ｂ８　Ｂ　ｓｔａｎｄａｒｄ　ｏｆ　ｃｈｏｏｓｉｎｇ　ｓｉｍｉｌａｒｉｔｙ．　ｉｔ　ｅｘｐｏｕｎｄｓ　ｔｈｅ　ｍｅｔｈｏｄｓ　ｕｓｅｄ　ｔｏ　ｍｅａｓｕｒｅ　ｎｕｍｅｒｉｃａｌ　ａｔｔｒｉｂｕｔｅ．ｃａｔｅｇｏｒｉｃａｌ　ａｔｔｒｉｂｕｔｅ　ａｎｄ　ｍｉｘｅｄ　ａｔｔｒｉｂｕｔｅ．　Ｋｅｙｗｏｒｄ：ｉｎｆｏｒｍａｔｉｏｎ　ｔｏ：ｈｎｏｌｏｇｙ　ｃｌｕｓｔｅｒｉｎｇ　ａｎａｌｙｓｉｓ　Ｆ　ｓｉｍｉｌａｒｉｔｙ　ｍｅａｓｕｒｅｍｅｎｔ　ｄａｔａ　ｍｉｎｉｎｇ　引言　近年来，数据挖掘引起信息产业界的极大关注，其主要原因是存在大量数据可以广泛使　用，并且迫切需要将这些数据转换成有用的信息和知识，广泛地应用于各领域，包括商务管　理、生产控制、市场分析、工程设计和科学探索等．数据挖掘是信息技术自然演化的结果，是　从大量数据中提取或“挖掘”知识，被称为数据库中的知识发现（ＫＤＤ）．作为数据挖掘的一　个功能，聚类分析能作为一个独立的工具来获得数据分布的情况，观察每个聚类的特点，集　中对特定的某些聚类做进一步的分析．何谓聚类呢？聚类就是将物理或抽象对象的集合分　组成为由类似的对象组成的多个类的过程，其原则是将对象根据最大的组内相似性和最小　的组间相似性进行聚类或分组．因此，相似性测量这一标准定义的好坏将直接影响聚类算法　收稿日期：２００１　ｌ２一ｌ２　作者简介：易华客（１　９７６），女，湖南敢县＾，株洲师专计算机系教师，湘潭＾学计算机应用硬士研究　生ｔ王要从事计算机专业教学及数据挖掘研究．　４３　维普资讯 http://www.cqvip.com

株堋师范高等专科学校学报　２００２年第２期（总第２５期）　的优越性　２聚类算法及其相似性测量分析　在数据挖掘中聚类分析的对象是实例（Ｉｎｓｔａｎｃｅ），每个实例由不同的属性构成，这些属　性主要分为数值属性（Ｎｕｍｅｒｉｃａｌ　Ａｔｔｒｉｂｕｔｅｓ）和符号属性（Ｃａｔｅｇｏｒｉｃａｌ　Ａｔｔｒｉｂｕｔｅｓ），并且，要　处理的往往是非常大量而复杂的数据集．因此，传统的聚类方法必须尽量满足如下要求：　（１）能同时处理数值属性和符号属性．　（２）面对数量繁多且仍在迅猛增长的数据集，算法要满足效率及增量性方面的要求…．　聚类的解决方法有两大类：空间分割方法（Ｋ—Ｃｌｕｓｔｅｒｉｎｇ）和层次聚类方法（Ｈｉｅｒａｒｅｈｉ—　ｅａｌ　Ｃｌｕｓｔｅｒｉｎｇ）．空间分割方法是将整个数据对象空间分解为一些小的子空间，每个子空间　对应一个确定的类，可以多个子空间同属于一个类；层次聚类方法则是将较小的数据对象子　集合依据相似程度进行合并，这些小的数据对象子集合逐渐合并成较大的数据对象子集合，　从而构成一个类的层次．　聚类算法大致可以分为划分算法、层次算法、基于密度的算法、基于网格的算法和基于　模型的算法　一．一般来说，它们所基于的相似性测量方法有三种，均用于数值属性的相似性　测量、符号属性相似性测量和同时用于数值属性和符号属性的混合性相似测量．　２．１数值属性的相似性测量方法　数值属性的相似性测量方法大多直接或问接依赖于欧几里德距离．常见的基于欧氏距　离的聚类算法有分割算法中的Ｋ—ＭＥＡＮＳ算法，Ｋ—ＮＮ算法以及分层算法中的ＢＩＲＣＨ　算法，ＣＵＲＥ算法以及基于密度的ＤＢＳＣＡＮ算法．首先我们给出几个基本概念．　定义１度量空间一个度量空间是指一个数据对象集ｘ和这个数据对象集合上的一　个距离函数Ｄ构成的二元组（ｘ，Ｄ），其中距离函数Ｄ是二元函数并满足以下条件：　ｉ）ｔＰ负性有０＜Ｄ（Ｘ，Ｙ）＜。。，ＸｖｅＹ，Ｄ（Ｘ，ｘ）＝０．　１＿）对称性Ｄ（Ｘ，Ｙ）－－Ｄ（Ｙ，ｘ），对于任意的ｘ，Ｙ属于ｘ都成立．　ｉｉｉ）三角不等式Ｄ（Ｘ，Ｙ）≤Ｄ（ｘ，ｚ）土Ｄ（ｚ，Ｙ）对于任意的ｘ，Ｙ，ｚ属于ｘ都成立．距离　函数一般由应用领域确定．　定义２相似性函数设（ｘ，Ｄ）是一度量空间，Ｓ是该度量空间中有限的数据对象集合，　设常数Ｃ＞Ｏ，两个单点相似性函数定义为Ｓｉｍｉｌａｒｉｔｙ（ｘ，Ｙ）＝Ｃ／（ｃ＋Ｄ（ｘ，Ｙ））．它也称　为相似度．显然它满足非负性Ｓｉｍｉｌａｒｉｔｙ（Ｘ，Ｙ）／＞０和对称性Ｓｉｍｉｌａｒｉｔｙ（ｘ，Ｙ）一ＳｉｍｌｌａⅢｉ　ｖ　（Ｙ．Ｘ）［　对于Ｎ维样本空间ｓ中的任意两个数据ｘ、Ｙ，它们的欧氏距离为：　Ｄ（Ｘ，Ｙ）　Ｃｒ“　一　“　）。＋Ｃｒ　）　＋－．－．．．＿＿（　而＝　丽　（１）　另一种常用的距离是曼哈顿距离，定义为：　Ｄ（Ｘ，Ｙ）＝ｌ（　一　㈩）　ｌ１＇ｌ（　㈣　）　ｌ＋……＋ｌ（　一　）　（２）　Ｍｉｎｋｏｗｓｋｉ距离将两种距离统一到一种形式中　维普资讯 http://www.cqvip.com

岛华寄：聚娄许析中相似性测量方法的研究　Ｄ（Ｘ．Ｙ）＝（１（　”　…）　ｌ一（　一Ｙ　）　ｌ＋……＋（　一Ｙ　）　１）“　由（３）可知，Ｍｉｎｋｏｗｓｋｉ距离在Ｑ－２时为欧氏距离，Ｑ－１时为曼哈顿距离．　（３）　有时为了突出一些数据的关键属性对聚类分析的重要作用，常采用加权形式的欧氏距离：　Ｄ（Ｘ，Ｙ）一￣／　１（ｚ“　一ｙ“　）。十毗（ｚ　一　）　十斗　实例一　）　（４）　以避免某些属性的值过大而屏蔽其它取值较小的属性对数据相似性测量的影响．　假如要对一个零售商的消费者信息库进行聚类分析，以方便该零售商调整针对　不同收入消费者的消费策略，每个顾客用其年龄和月收入表示，即Ｃｕｓｔｏｍｅｒ（ａｇｅ，ｉｎｃｏｍｅ），　这些变量使用不同的单位．考虑到个人的月收入比他或她的年龄要大很多，因此若直接用欧　氏距离度量两个消费者之间的相似性为：　Ｄ（Ｃ】，Ｃ２）＝　（ａｇｅ　Ｌ　ａｇｅ２）　＋（　。　ｌ一　∞ｍ　２）　．经过平方后，（ｉｎｃｏｍｅＩ—ｉｎ—　ｃｏｍｅ　）　＞＞（ａｇｅ　－－ａｇｅ　）　，因此，就得不到不同年龄段的消费者的聚类情况．为此，通常采　取一种较为简单直接的办法：对年龄加权，即　Ｄ（Ｃｌ，　）＝￣／Ａ（。ｇ　一ａｇｅ　）　＋（ｉｎｃｏｍｅ　一ｉｎｃｏ￣ｚｅ２）。．这样，不同的Ａ值将会导致不　同的聚类结果．　定义３聚类问题给定数据集合ｓ一｛ｚ　，ｚ　…“，ｚ　），ｚ．称为数据对象．求出一个分　类，ｓ对应根节点，每个子节点ｓ　对应所有它的分支所包含的数据对象，对于树的同一层的　所有节点Ｓ　需满足最优解条件Ｍａｘ｛Ｓｉｍｉｌａｒｉｔｙ（Ｓ．）一　）Ｓｉｍｉｌａｒｉｔｙ（非空集合Ｓ　）一Ｍａｘ　｛∑Ｓｉｍｉｌａｒｌｔｙ（Ｘ　，Ｘ　＋　）Ｉ完整的巡回ｓ　的所有可能路径）　．　２．２符号属性的相似性测量方法　针对欧氏距离不同直接应用于符号属性，Ｒａｌａｍｂｏｎｄｒａｍｙ提出一种将符号属性转换成　二进制属性的方法，用０或１表示一个符号存在或不存在，并在算法中把这些二进制属性当　成数值来处理，这种方法需要一个转换过程来处理符号属性，如果符号很多的话，转换后的　空间会很大．　Ｋ—ｍｏｄｅ算法中的公式被进一步一般化后，就形成了描述符号属性的悔明距离公式：　其中ｘ，Ｙ为具有几个符号属性的实侧对象，ｚ。，　是对应的属性：　Ｄ（Ｘ，Ｙ）一∑８（ｘ，，ｙ．）　）（５）　』【　五　１（　≠　．）　（６）　针对符号属性的一些特殊问题（畸变和裂变效应）Ｓｔｕｄｉｐｔｏ、Ｇｄｕｈａ等学者在Ｊａｃｃａｒｄ　置信度基础上提出了一种从全局考虑符号属性闯相似性的测量方法：对象联接度，其定义如　下几个部分组成：　（１）对象的邻点：一个实例对象Ｑ是另一个实例对象Ｐ的邻点，当且仅当：　ＳＩＭ（Ｐ，Ｑ）＞／０　（７）　其中０是一个用户自定义阀值，可由用户调节，ｓＩＭ（Ｐ，Ｑ）与特殊问题领域有关，可由领域　专家指出，无论ＳＩＭ为何种形式，它满足以下性质：　４５　维普资讯 http://www.cqvip.com

株洲师范高等专科学校学报　２００２年第２期（总第２５期）　１）当Ｐ—Ｑ时，ＳＩＭ（Ｐ，Ｑ）一１　２）当Ｐ＾Ｑ一由时，ＳＩＭ（Ｐ，Ｑ）＝０　（２）对象的联接度：两个对象之问公共邻点的个数为联接度ＬＩＮＫ（Ｐ．Ｑ）．由于联接度　考虑了聚类中其他点而不仅仅局限于两个数据之间局部相似性，因此聚类之间有强的联接　性，避免了两个完全不相干的对象被其他对象连接到同一聚类的现象．但是，它的ＳＩＭ函数　对不同领域有所不同．因此算法是面向特定问题的，通用性不强，另外，它也只能分析符号属　性，并且ＬＩＮＫ（Ｐ，Ｑ）的计算复杂，算法的复杂度为Ｏ（Ｎ。蛳Ｎ）［‘　．　２．３混合属性的相似性测量　对于混合属性的聚类有一种欧氏距离和海明距离组合在一起的Ｋ—ｐｒｏｔｏｔｙｐｅ算法，它　其实将Ｋ－－ｍｅａｎｓ与Ｋ－－ｍｏｄｅ算法结合起来提出下列相似性公式：　Ⅱ　Ｎ　Ｄ（Ｘ，Ｙ）一∑ｄ（ｘ　，　）＋∑ａ（ｘ　，　）　（８）　Ｉ一１　ｒ＝１　式中实例对象Ｘ，Ｙ其属性为Ａ１　，Ａ　，……ＡＰ　，Ａ…　，ＡＰ＋２　，……ＡＮ　，其中Ａｌ　，Ａ２　，　……Ａ　为数值属性，Ａ　＋　，Ａ　＋　，……Ａ　为符号属性．显然这是一种折中的算法．　３结论　本文讨论了数据挖掘的重要问题之一数据即聚类问题．在对现有聚类算法中的关键概　念——相似性测量作了深入的讨论和分析．对象间的距离或相似度是聚类的核心，我们常常　按照对象之间的相似性进行划分，划分的结果使某种表示聚类质量的评价函数最优　相似性　的度量方法很多，有的用于专门领域，也有的适用于特定类型的数据，选择相似性的一个重　要因素是属性的类型．如何选择相似性的度量方法是一个相当复杂的问题，需要进行深入的　研究．　参考文献：　［１］Ｈａｎ　Ｊｉａｗｅｉ．Ｋａｍｂｅｒ　Ｍ．Ｄａｔａ　Ｍｉｎｉｎｇ：Ｃｏｎｃｅｐｔｓ　ａｎｄ　Ｔｅｃｈｎｉｑｕｅｓ．Ｓｉｍｏｎ　Ｆｒａｓｅｒ　Ｕｎｉｖ．２０００．　［２］Ｈｏ　Ｔｕ　ｏ，ｅｔ　ａ１．Ｓｔｕｄｙ　ｏｆ　ａ　Ｍｉｘｅｄ　Ｓｉｍｉｌａｒｉｔｙ　Ｍｅａｓｕｆｅ　ｆｏｒ　Ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ａｎｄ　Ｃｌｕｓｔｅｒｉｎｇ．Ｉｎ：Ｍｅｔｈｏｄｏｌ—　ｏｇｉｅｓ　ｆｏｒ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｇ，ＰＡＫＫＤＤ－－９９，１９９９．　［３］Ｌｉ　Ｃ，Ｂｉｓｗａｓ　Ｇ．Ｕｎｓｕｐｅｒｖｉｓｅｄ　Ｃｌｕｓｔｅｒｉｎｇ　ｗｉｔｈ　Ｍｉｘｅｄ　Ｎｕｍｅｒｉｃ　ａｎｄ　Ｎｏｍｉｎａｌ　Ｄａｔａ—Ａ　Ｎｅｗ　Ｓｉｍｉｌａｒｉｔｖ　Ｂａｓｅ　Ａｇｇｌｏｍｅｒａｔｉｖｅ　Ｓｙｓｔｅｍ．Ｉｎ　ＫＤＤ：Ｔｅｃｈｎｉｑｕｅｓ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎ，Ｗｏｒｌｄ　Ｓｃｉｅｎｔｉｆｉｃ．１９９７．　［４］Ｓｎｄｉｐｔｏ　Ｇｕｈｅ．ｅｔ　ａ１．Ｃｌｕｓｔｅｒｉｎｇ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｃａｔｅｇｏｒｉｃａｌ　Ａｔｔｒｉｂｕｔｅｓ［Ｔｅｃｈｎｉｃａｌ　ｒｅｐｏｒｔ］．Ｂａｌｌ　Ｌａｂｏｒａｔｏ—　ｒｉｅｓｔ　Ｍｕｒｒａｙ　Ｈｉｌ１．１９９７．　［５　ＡＩＳ￣Ｍｉ　Ｋ．ｅｔ　ａ１．Ａｎ　Ｅｆｉｆｃｉｅｎｔ　Ｓｐａｃｅ－－Ｐａｒｔｉｉｒｏｎｉｎｇ　ａＢｓｄｅ　Ａｌｇｏｒｉｔｈｍ　ｏｆｒ　ｔｈｅ　Ｋ—Ｍｅａｎｓ　Ｃｌｕｓｔｅｒｉｎｇ．Ｉｎ：　Ｍｅｔｈｏｄｏｌｏｇｉｅｓ　ｆｏｒ　Ｋｎｏｗｌｄｅｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｇ，ＰＡＫＤＤ－－９９，１９９９．　（责任编辑：曾广慈英文译校：文爱军）　４６