聚类分析中的相似度研究.pdf

《聚类分析中的相似度研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第33卷第1／2期东北电力大学学报V0J．33．No．1／22013年4月JournalOfNortheastDianiiUniversityApr．，2013文章编号：1005—2992(2013)01／02—0156—06聚类分析中的相似度研究邓冠男(东北电力大学理学院，吉林吉林132012)摘要：针对聚类分析中相似度进行研究。首先，通过分析相似度的构造，将相似度划分为比较、综合及转换的过程，从而提出一般相似度的概念。其次，以一般相似度为基础上，分析了常见相似度的权重分配，并研究多类型混合数据的相似度

2、计算策略。关键词：聚类分析；相似度；一般相似度中图分类号：TP181文献标识码：A聚类，也称作无监督分类，是数据挖掘的重要组成部分，目前已经在很多领域取得了成功的应用。聚类分析的目的是通过将有限的数据集分成多个具有同质的“簇”(即不同的类)，来发现隐藏的、潜在于数据中的有用信息。其目标是要求同一类内的数据尽可能相近，而不同的类之间的数据尽可能相异。为了达到这一目标，必须考虑如何度量数据之间、数据与类之间或者类与类之间相似性这一基本而重要的问题。为了度量数据的相似性，人们提出相似度的概念，并提出许多相似度的

3、计算公式】。]。尽管很多时候没有明确说明，但是事实上，无论何种聚类算法，都是建立在事先假定某种相似性度量方式基础上的，比如K一均值算法假定数据之间、数据与类之间都使用欧式距离构造的相似度；基于图的聚类算法假定数据之间使用欧式距离构造的相似度，但是数据与类之间的相似度定义为数据该类所有元素相似度的最小值；EM算法利用某种概率密度函数来度量数据与类之间的相似度等等。在实际的聚类问题中，存在很多与相似度有关的问题。比如，当数据的属性具有不同权重时，如何计算相似度。如果没有任何关于属性重要性的先验信息，毫无疑问我

4、们会认为所有属性都应当平等对待，但是如果必须区别对待的话，我们必须考虑如何对属性进行加权。然而，从众多相似度的计算公式中，我们并不能看出或者明确给出权重如何分配给各个属性的。再如，如果数据混合有不同类型的数据(如布尔型、文本型、数值型等等)，如何计算其相似度，目前能够解决这一问题的相似度还是非常少的E4,5]。本文针对聚类分析中的相似度进行研究。首先，通过分析相似度的构成的过程，将相似度的构造分解为比较、综合及转换的过程，进而提出一般相似度的概念。之后，利用一般相似度分析常见相似度对权重的分配方式，同时提

5、出几种多类型混合数据相似度计算的策略。1相似度在一些文献中可以找到不同的相似度的公理化定义方式，这里我们给出其中一种简单的定义收稿日期：2012—09—14基金项目：国家自然科学基金(11226263，11201057)；东北电力大学博士科研启动基金(BSJXN一201019)作者简介：邓冠男(1979一)，男，吉林省农安县人，东北电力大学理学院副教授，博士，主要研究方向：模糊信息处理第1／2期邓冠男：聚类分析中的相似度研究157方式。定义1设X=XXX2×⋯XX为n维有限论域，对于V，Y∈X，如果映射s

6、：×X一[0，1]满足下列条件时：(1)非负性0≤s(，Y)≤1；(2)对称性s(x，Y)=s(y，)；(3)s(，)：1。则称s(x，Y)称为与Y之间的相似度。但是，需要注意的是，目前某些文献中给出的相似度的计算公式并不完全满足上述定义。针对不同的数据类型，目前有许多相似度的计算公式，下面列出常见的一些：(1)数值型数据的相似度数值型数据的相似度通常利用数据间的距离来构造，可以利用公式=)=e-d(x,y)或=l一，将距离转化为相似度，其中maxd表示数据集中数据之间的最大的距离。常用的距离公式有：◆M

7、inkowski距离d(，Y)：(l—yI)古，◆最大距d(，y)=I—yl，mln{xi，Yif／1n、÷◆Czekanowski距离d(，y)=1一———一，◆平均距d(x，)=【÷∑(—Yi))，(+Yk其中，V表示取大运算，对应的^表示取小运算。(2)二元数据的相似度二元数据是由二元变量构成。二元变量只能有两种取值状态：0或1，其中0表示该特征为空，l表示该特征存在。设=(，：，⋯，)、Y=(Y。，Y2m⋯，Y)为二元数据，常用0—0匹配表示=0且Y=0，同理可用0一l、1—0及1一l匹配表示i及

8、Y相应的取值。常见的计算其相似度的方法列举如下，其中表示集合{(，Y)I=i且Y=，k=1，2，⋯，n}的基数，i√∈{0，1}。◆简单匹配系数sMc=．皇，◆Jaccard系数．，=．，。~Rogers-TanimotoR卜l+o+1’．蔷，◆srensen5=◆Soka1．Sneath．aSa=21+0+l+’~Russell-RaoRR=，．-sneat丢+)．(3)其他相似度◆余弦相似度c。s(，y)首，其中y，i√2