相似度计算及其在数据挖掘中的应用

    李俊磊　滕少华

    

    

    

    摘要：相似度是描述两个对象之间相似程度的一种度量，依据对象不同，相似度计算方法亦不同。相似度计算被广泛应用于数据挖掘算法中，它是对象分类的基础。该文将数据对象划分为数值型、非数值型和混合型三种，并根据数据对象的类型，探讨了相应的相似度计算方法，最后，通过实例描述了相似度计算在数据挖掘中的应用。

    关键词：对象；相似度计算；数据挖掘；数据类型

    中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2016）13-0014-04

    Abstract： The Similarity is a measure of similarity between two objects， according to different objects， similarity calculation method is also different. Similarity calculation is widely used in data classification， is the basis for object classification. In this paper， the data objects were divided into three kinds： numeric type， non-numeric type and mixed type. And the similarity calculation methods of different types are discussed. Finally， we illustrated the application of similarity in the data mining.

    Key words： object； similarity calculation； data mining； data type

    伴随数据挖掘技术的应用领域发展，对象之间的相似性计算已成为一个非常重要的研究课题。相似度度量是衡量对象间相互关系强弱、联系紧密程度的重要手段。

    在数据挖掘的方法中，诸如数据分类和预测[1-2]、数据聚类[1-2]、关联分析[1-2]、序列模式[1-2]、依赖关系与依赖模型[1-2]、异常检测和趋势分析[1-2]等都离不开对象之间的相似度分析。尤其是在考察对象间同异度关系时，相似度度量和计算方法将直接影响最终的数据挖掘结果，相似度计算又是衡量对象间差异的基础，在分类应用中，相似度计算是分类的依据。因而，依据不同的实际应用和数据对象，研究相似度计算方法，对数据分类有重要意义。

    首先描述了相似度概念，进而将数据对象分为三种类型：数值型、非数值型和混合型，然后按不同数据对象分别给出了相应的相似度计算公式，最后通过实例对相似度计算进行了说明。

    1 相似度概念

    在数据挖掘、模式识别和机器学习等计算机应用领域中，两个对象的相似度是描述这两个对象之间相似程度的一种度量，两者越相似，它们的相似度就越高，相似度是一个非负数值，其值介于0和1之间[2]。数据挖掘的很多算法都涉及计算对象间的相似度，相似度计算方法依赖于数据对象的类型，数据对象的类型不同其相似度计算方法不同。例如，数值型数据的相似度可用欧氏空间的距离来描述其邻近程度；两个标称型数据对象的相似度与用来计算相似度的属性的值域有关。

    依据参与相似度计算的数据类型，本文将数据对象分为数值型、非数值型和混合型[1-2]三种。

    1.1 数值型

    数值型数据被用来描述连续型或定量型数据，即两个不同数值之间有无穷多个数值。使用实数或度量衡单位计量相似度值，如温度、身高等。数值型量可分为区间标度量和比例标度量，其中区间标度量是一个线性的标度量，而比例标度量一般是非线性的。

    1.2 非数值型

    其取值是定性的、而非定量的数据。如人的性别，成绩优良等级等。通常这类对象属性的取值可通过有限个状态（字母/序数）来描述。非数值型数据又可分为标称型、二元和序数型数据等。标称型数据之间是无序的，序数型是有序的。

    1.3 混合型

    由数值型数据和非数值型数据混合组成。

    2 相似度计算

    2.1 数值型数据

    数值型数据可分为区间标度型和比例数值型数据。

    2.1.1 区间标度型数据

    区间标度型：是一个粗略线性标度的连续量，这种量的值是有序的，可以为正数、负数或0。典型的例子有重量、高度、大气温度等。具体计算时，区间型数据的相似度通常转换成相异度计算。常用的计算方法是先将这种量标准化，消除度量单位对分析结果的影响，然后，采用距离来计算对象间的相异度。距离是一个非负数，距离的大小代表着2个对象之间的差异程度，距离越大，2个对象相异度就越大，距离越小，2个对象之间的相似度越高。这里给出常见的相异度计算方法[3]。

    设 p=（p1， p2， …， pn）T， q=（q1， q2， …， qn）T 为N维空间中的两个对象，pi是对象p对应的第i个属性所取的值，是对象P的所有属性值的平均值。qi是对象q对应的第i个属性所取的值，是对象q的所有属性值的平均值。

    曼哈顿、欧氏和闵可夫斯基距离等计算公式分别如下：

    1）曼哈顿距离

    曼哈顿距离又称为城市街区距离，是使用在几何度量空间的几何学用语，用以表明2个点在标准坐标系上的绝对轴距总和[4]，对n维空间的曼哈顿距离表示如下：

    2个n维向量p（p1， p2， …， pn）与q（q1， q2， …， qn）间的曼哈顿距离：

    2）欧氏距离

    欧式距离也称为欧几里得距离，是通常采用的距离，它是在n维空间中2个点之间的真实距离，用来表示各个数据对象之间的距离。欧式距离与对象的量纲有关，从统计的角度看，使用欧氏距离要求各个坐标对欧式距离的贡献是同等的且变差大小也是相同的[5]。

    2个n维向量p（p1， p2， …， pn）与q（q1， q2， …， qn）间的欧氏距离：

    （2）

    3）切比雪夫距离

    切比雪夫距离是一种最大距离。在向量空间中，2个向量间的切比雪夫距离，就是将其沿着任意坐标尺寸的最大值[6]。二维和n维空间的切比雪夫距离如下：

    2个n维向量空间向量p（p1， p2， …， pn）与q（q1， q2， …， qn）间的切比雪夫距离：

    4）闵可夫斯基距离

    闵科夫斯基距离是欧氏距离和曼哈顿距离的推广[7]，定义如下：

    当x=1时，为曼哈顿距离，当x=2时为欧氏距离。

    5）马氏距离

    马氏距离 [3]是一种常用的距离度量方式，能够充分考虑模式特征参数的大小以及特征间的相关性，在模式识别中其性能通常比欧式距离好。马氏距离是欧式距离的改进，是欧式空间中非均匀分布的归一化距离，它对于一切线性变换是不变的[8]。

    6）Canberra距离

    Canberra距离是一种相对马氏距离，不受量纲的影响，同样没有考虑多重相关性，Canberra距离对微小变化很敏感[9]。

    7）相关系数

    相关系数是对向量做标准差、标准化后的夹角余弦，表示两个向量的线性相关程度[10]。当两个向量方向相近时，夹角余弦值越大，反之越小。特别地，当两个向量平行时，夹角余弦值为1，而正交时余弦值为0。

    2.1.2 比例型数据

    比例型数据一般是通过非线性尺度取得的测量值。计算这类对象的相似度有三种方法：转换为区间标度型数据、转换为连续的序数数据、取对数。

    2.2 非数值型数据

    许多数据挖掘方法只能处理数值型数据，因此需要将非数值型数据转为数值型数据。可建立非数值型量的不同状态值或利用离散数据建立其与对象之间的对照表。非数值型数据又可细分为标称数据、二元数据和序数型数据等。

    2.2.1 标称数据

    标称数据又称为类别数据，标称型属性的值可以是一些符号或事物的名称。每个值代表某种类别、编码或状态等。标称型属性的值之间没有顺序关系。例如：设hair_color（头发颜色）是一个描述实体人的属性。它取值可以为黑色、棕色、淡黄色、红色、赤褐色、灰色和白色等。因此，hair_color是标称属性。

    通常，可以用数字表示这些符号或名称，例如对于hair_color，可以指定数字0表示黑色，1表示棕色，2表示淡黄色等。

    两个标称型对象i和j之间的相异度可以用简单匹配方法来计算：

    其中p为对象的属性的个数，m为对象i和j取值相同的属性个数，我们可以通过赋权重来增加m的影响，或者赋给有较多状态的变量匹配以更大的权重。

    对于标称数据，欧氏距离等不能直接应用于其数据的特点，Ralambondramy提出了一种该类型转换成二进制属性的方法，用0和1表示一个属性是否存在，并把这些二进制属性当做数值来处理[11]。

    通过这种方法也很容易描述分类属性的海明距离公式：

    2.2.2 二元型数据

    二元数据是一种特殊的标称数据，只有二个类别或状态（0和1）构成，0表示该属性不出现，1表示出现。

    设x = （x1， x2， …， xn）， y = （y1， y2， …， yn） 为二元数据，常用0-0、0-1、1-0、1-1匹配表示xi及yi相应的取值。其中fij表示集合{（xk， yk）| xk = i且yk = j， k = 1， 2， …， n}的基数，[12]。计算二元型数据相似度的方法比较多，由于篇幅原因，只列如下几种：

    1.简单匹配系数（对象的变量是对称时）

    2.Jaccard系数

    （11）

    3.Rogers-Tanimoto

    4.Srensen

    2.3 序数型数据

    序数型属性变量分为分类和连续两种。分类序数属性与标称属性类似，不同的是，分类序数值表示不同的状态，将其状态可按一定的次序排列。例如，职称就是一个分类序数，按照助教、讲师、副教授、教授的顺序排列的；人的年龄段可按儿童、少年、青年、中年、老年顺序排列。一个连续序数型数据看上去就像一组未知范围的连续数据，值之间的相对顺序是重要的，而其实际的大小则不重要。在计算对象的相异度时，对序数型数据的处理方式与区间标度数据非常类似。

    假设f是用于描述n个对象的一组序数型属性之一，若序数属性f有mf个状态，关于f的相异度计算包括如下步骤：

    1）属性f有mf个有序状态，第i个对象的属性f的取值为xf，将属性值xf替换为相应的等级rf，rf{1，2，3，....，mf}。

    2）将序数属性等级做变换，映射到区间[0，1]上。

    3）利用数值属性的任一种距离计算公式来计算相异性。

    2.4 字符串型数据

    海明距离是专门针对字符串数据而设计，用来衡量两个字符串之间的相似度，其计算公式如下所示：

    其中，表示两个字符串。而，，分别表示字符串中各个位置上的字符。count（ ）函数用于获取两个字符串中对应字符值不同的个数，海明距离是分析文本等字符型数据之间相似度的常用方法，在文本分类等领域得到了广泛应用。

    2.5 文档向量型

    通常，文档用向量表示，向量的每个属性代表一个特定的词（关键词）或短语的频度。每个文档都被一个所谓的词频向量来表示。词频向量通常很长，并且稀疏。使用这种结构的应用包括信息检索、文本文档聚类、生物学分类和基因特征映射。对于这类稀疏的数值数据，常采用余弦相似性来计算两个文档间的相似性。

    2.6 其他非数值型数据

    在实际的应用中，对象的某些属性数据值与我们研究的结果毫无关系，则可忽略，不需考虑在内。

    3 混合型数据

    当对象的属性是由多种数据类型组成时，此时对象之间的相异度计算变得比较复杂了，目前有四种方法来处理：按单个属性独立计算、按类型分组独立计算、通过相异度矩阵计算、采用摘要信息方式计算等，由于篇幅有限，摘要信息方式计算在文中就不具体列举了。

    3.1 按单个属性计算

    将对象的每个属性单独进行考虑，按照一般正规相似度的定义方式进行计算，也就是先度量单个属性之间的相似度，然后利用综合函数得出整体相似性。但是一般在计算数据相似度时会归约到同一形式上[12]。

    3.2 按类型分组计算

    将属性按数据类型分组，将每种数据类型的属性分成一组，利用相应的相似度计算公式来计算不同类型属性的相似度，之后利用综合函数得到整体相似度，这种方法将同种类型的属性看成整体进行考虑。如果这些分析得到兼容结果，则这种方法可行，但在实际的数据应用中，每种属性类型分别分析得到兼容结果的可能性不大，所以这种方法的可行性不大。

    3.3 通过相异度矩阵计算

    将所有的数据一起处理，只进行一次分析。将不同类型的数据组合在单个相异度矩阵中，所有有意义的数据转换到共同的值域区间[0， l]上[13]。

    假设数据集中包含p个不同的类型的属性，对象i和j之间的相异度定义为：

    其中，如果或缺失（即对象i或对象j没有属性f的度量值），或者，且属性f是不对称的二元型数据，则指示项；否则，指示项。

    对象i和j之间相异度的计算方式与属性f的具体数据类型有关：

    如果f是二元型数据或标称型数据：如果，则；否则。

    如果f是标度型数据：这里的取值是属性的所有非空缺对象。

    如果是序数型或者比例标度型数据，计算排序位和，并将作为区间标度型数据对待。

    4 相似度计算的应用

    4.1应用

    对象间的相似度计算在数据挖掘中涉及面很广，如K最近邻分类（KNN）、聚类和异常检测等技术。

    K最近邻（KNN）分类算法通过计算给定的检验对象与训练对象之间的相似度，找出检验对象的K个“最近邻”[27]。“邻近性”用相似度来度量。因此，如何选择相似度计算方法在KNN最邻近算法中对分类效果有着直接影响。若对象的属性是数值型数据，则直接用对象间的距离来度量，对每个属性的值进行规范化，变换到[0，1]区间，防止较大初始域的属性权重过大而影响结果。若属性是标称型数据，常比较对象x1和x2中对应属性的值，若两者相同者取0，反之则取1。

    聚类，也称作无监督分类。聚类分析的目的是把数据对象划分成多个组或簇（即不同的类），来发现隐藏的、潜在于数据中的有用信息。其目标是使得同一簇内的对象具有较高的相似性，而簇间的对象尽可能相异。众多聚类算法都是建立在事先假定某种相似度度量方式基础上，因此聚类算法的基本出发点都是根据对象间相似度将对象划分为不同的簇。

    在实际的数据挖掘应用中，如果涉及相似性度量，首先应分析对象的数据类型是否是单一，是数值型的数据还是是非数值型的或者是混合型的数据类型。然后根据相应类型的相似度的计算公式进行处理。

    4.2 计算实例

    下面用KNN算法和k-summary算法应用的两个实例来介绍相似度的计算。

    实例1.数据集weather如下表所示，测试样本X=（rain，hot，normal，weak，？）， k取3，下面根据KNN最邻近方法预测该样本的类符号。

    由于outlook的值有三个，属于标称型数据类型，为了便于区别它们之间的差异性，在此将其值对应转化为序数型数据。sunny=1，overcast=2，rain=3；同理temperature的hot=1，mild=2，cool=3。

    首先计算样本X到14个记录的距离（取曼哈顿距离）分别为：

    Distance（X，p1）=3，Distance（X，p2）=3，Distance（X，p3）=2，Distance（X，p4）=1.5，Distance（X，p5）=1，Distance（X，p6）=2，Distance（X，p7）=2.5，Distance（X，p8）=2.5，Distance（X，p9）=2，Distance（X，p10）=0.5，Distance（X，p11）=2.5，Distance（X，p12）=3，Distance（X，p13）=0.5，Distance（X，p14）=2.5；

    根据KNN的概念可知，K=3，在这里取3个距离最小的值，分别为Distance（X，p10）=0.5，Distance（X，p13）=0.5，Distance（X，p5）=1。所以取离样本X最近的3个近邻为p5，p10，p13。而这3个最邻近对应的类标号都为yes，因此样本X的类标号被预测为yes。

    5 结论

    论文对相似性的概念进行了介绍，然后对数据类型进行了分类，并对不同数据类型对象的相似度的衡量方式进行了分析。不同的数据类型具有不同的相似性处理方式，相似性的计算方法有很多，有的适用于专门的领域，同时也有适用于特定类型数据的限制，选择相似性的一个重要的因素就是属性的类型。在进行非数值型数据时，有时会因为将其化为标称类型，但是这样的转换并不能很好地了解属性间的差异性，而将其进行序数化，再进行相似度计算，更能体现数据之间的差异性。

    参考文献：

    [1] Jiawei Han， Micheline Kamber， Jian Pei.Data Mining Concepts and Technologyes[M].3rd ed.China Machine Press，2012.

    [2] 蒋盛益，李霞，郑琪.数据挖掘原理与实践[M].北京：电子工业出版社，2013.

    [3] 黄彧.相似度度量的研究及其在数据挖掘中的应用[D].福州：福建师范大学，2009.

    [4] Yano Y.Associative Memory with Fully Parallel Nearest-Manhattan-Distance Search for Low-Power Real-Time Single-Chip Applications[C]. Proc. Of IEEE ASP-DAC， 2004：543-544.

    [5] Hua-Kai Chiou， Gia-Shie Liu.Multiple Objective Compromise Optimization Method to Analyze the Strategies of Nanotechnology in Taiwan[C]. Symposia and Workshops on Ubiquitous， Autonomic and Trusted Computing，2009：172-177.

    [6] de Souza R M C R ， de Carvalho F A T. Dynamic clustering of interval data based on adaptive Chebyshev distances[J]. Electronics Letters， 2004， 40（11）.

    [7] Ryotaro Kamimura， Osamu Uchida. Greedy Network-Growing by Minkowski Distance Functions[C]. IEEE Transaction on Neural Networks， 2004：2837-2842.

    [8] Chunhua Shen， Junae Kim， Lei Wang. Scalable Large-Margin Mahalanobis Distance Metric Learning[J].IEEE Transactions on Neural Networks， 2010， 21（ 9）： 1524-1530.

    [9] Sheng-Yijiang.Efficient Classification Method for Large Dataset [C]. Proceeding of the Fifth International Conference on Machine Learning and Cybernetics， Dalian， 2006：13-16.

    [10] Xing E P， Ng A Y， Jordan M I，et al. Distance metric learning， with application to clustering with side-information[C]. proc Adv Neural Inf Process Sys.， 2003：505-512.

    [11] 陈韡.基于划分的混合属性聚类算法研究[D].长沙：湖南大学，2010.

    [12] 邓冠男.聚类分析中的相似度研究[J].东北电力大学学报，2013，33（1/2）：156-161.

    [13] 李桂林，陈晓云.关于聚类分析中相似度的讨论[J].计算机工程与应用，2004，40（31）： 64-65.