2.3 数据的相似性和相异性在线视频

数据的相似性和相异性是

两个非常重要的概念

在许多数据挖掘技术中都会使用

如聚类 最近邻分类和异常检测等

在许多情况下

一旦计算出数据的相似性或相异性

就不再需要原始数据了

这种方法可以看作先将数据变换到

相似性或相异性空间

然后再进行分析

相似性是对两个对象相似程度的度量

数值越大表明相似性越大

通常取值范围为0到1之间

相异性是对两个对象不相似程度的度量

数值越小表明相似性越大

相异性的最小值通常为0

相异性的最大值根据不同情况而不同

相似性和相异性统称为邻近性

数据矩阵或称对象属性结构

这种数据结构用关系表的形式

或m×n矩阵存放m个数据对象

数据矩阵如图所示

图中

每一行对应一个对象

每一列对应一个属性

数据矩阵由两种实体或者事物组成

即行代表对象

列代表属性

因此

数据矩阵经常被称为二模矩阵

相异性矩阵或称对象 对象结构

它存放n个对象两两之间的邻近度

通常用一个n×n矩阵表示

相异性矩阵如图所示

其中

d(i,j)是对象i和j之间

相异性的量化表示

通常为非负值

两个对象越相似或越接近

其值越接近0

反之其值越大

相异性矩阵满足对称性

即d(i,j)=d(j,i)

其中对角线上的数据d(i,i)=0

相异性矩阵只包含一类实体

因此被称为一模矩阵

通常

邻近性度量（特别是相似度）

被定义为区间[0,1]中的值

或变换到闭区间[0,1]中的值

这样做的目的是

由邻近性度量的值来表明

两个对象之间的

相似（或相异）程度

这种变换通常是比较直观的

标称属性是具有两个或多个状态的属性

比如说表示衣服的颜色

可以用红色 黄色 蓝色 绿色等表示

具有标称属性的

两个对象i和j之间的相异性

可以根据不匹配率来计算

如公式所示

d(i,j) = p-m/p=1- m/p

其中 p是对象的属性总数

m是匹配的属性数目

即对象i和j状态相同的属性数

也就是说

对象i和对象j之间的相异性等于

不匹配的属性数除以属性总数

即1减去匹配的属性数

除以属性总数的商

具有标称属性的两个对象i和j之间的

相似性计算如公式所示

Sim(i, j)=1- d(i, j) = m/p

即对象i和对象j的相似性

等于1减去两者的相异性

也就是匹配的属性数除以属性总数

例 标称属性的相异性矩阵的计算

标称属性对象数据如表所示

此例中Test属性是标称属性

标称属性总数p=1

根据公式可以分别计算

两个对象之间的相异性

如对象2和对象1之间

匹配的属性数是0

两者之间的相异性d(2,1)=1-0/1=1

类似可以计算出其他两对象之间的相异性

构建出的相异性矩阵如图所示

二元属性只有两种状态

通常表示为0或1

0表示属性不出现

1表示属性出现

二元属性又称布尔属性

用false和true表示

具有对称属性的对象i和对象j的

相异性计算如公式所示

其中m是对象i和j都取1的属性数

n是在对象i中取1

在对象j中取0的属性数

p是在对象i中取0

在对象j中取1的属性数

而q是对象i和j都取0的属性数

即对象i和对象j

取值不相同的属性总数

除以所有情况下属性总数

具有非对称属性的对象i和对象j的

相异性计算如公式所示

在非对称二进制属性中

一般认为两个对象在该属性上

都取值1的情况比两个都取值0的情况

更有意义

此时q是不重要的

因此在计算时被忽略

二进制属性的相似性计算如公式所示

即对象i和对象j的相似性

等于1减去两对象的相异性

例 二进制属性的相异性的计算

居民家庭情况调查数据如表所示

其中

婚否 买房否 买车否三个属性为

对称的二进制属性

根据公式计算的两者之间的相异性

如公式所示

数值属性的相异性主要通过距离来度量

包括欧几里得距离 曼哈顿距离

闵可夫斯基距离和切比雪夫距离

欧几里得距离又称直线距离

令i和j是两个被p个数值属性

描述的对象

对象i和j之间的欧几里得距离

如公式所示

d(i, j)=√(xi1-xj1)^2+(xi2-x2) ^2+…(xip-xip) ^2

曼哈顿距离又称城市块距离

令i和j是两个被p个数值

属性描述的对象

对象i和j之间的曼哈顿距离为

d(i, j)=[xi1-xj1] +[xi2-xj2]+…+[xip-xjp]

欧几里得距离和曼哈顿距离

都满足如下数学性质

一 非负性d(i, j)大于等于0

即 距离是一个非负的数值

二 同一性d(i, i)等于0

即对象到自身的距离为0

三 三角不等式d(i,j) 小与等于d(i,k)+(k,j)

即从对象i到对象j的直接距离

不会大于途经任何其他对象k的距离

闵可夫斯基距离是

衡量数值点之间距离的

一种常见的方法

令i和j是两个被p个数值属性

描述的对象

对象i和j之间的闵可夫斯基距离

如公式所示

d(i, j)=h√[xi1-xj1]^h+[xi2-xj2]^h+…+[xip-xjp]^h

其中h是实数

h大于等于1

当h=1时

即为曼哈顿距离

当h=2时

即为欧几里得距离

切比雪夫距离又称上确界距离

定义两个对象之间的距离

为其各坐标数值差的最大值

如公式所示

例 数值属性的相异性计算

给定两个对象分别用元组2 8 7 4

和1 5 3 0描述

计算这两个对象之间的欧几里得距离

曼哈顿距离 闵可夫斯基距离（h=4）

以及切比雪夫距离

欧几里得距离的计算为

d(i,j)等于6.48

曼哈顿的距离等于12

闵可夫斯基距离为约等于4.94

切比雪夫距离等于4

序数属性的值之间

具有有意义的序或排位

序数属性可以通过把数值属性的

值域划分成有限个类别

对数值属性离散化得到

这些类别组织成排位

即数值属性的值域可以映射到

具有Mf个状态的序数属性f

其中序数属性可能的状态数为M

这些有序的状态定义了一个排位1…Mf

因此

序数属性的相异性计算可以使用

数值属性的距离相异性度量方法

假设f是用于描述n个对象的序数属性

关于f的相异性计算步骤如下

第一步第i个对象的f值为xif

属性f有Mf个有序的状态

表示排位1, ... ,Mf

用对应的排位rif∈{1,...,Mf}取代xif

第二步 由于每个序数属性

都可以有不同的状态数

所以通常需要将每个属性的值域

映射到［0.0,1.0］上

以便每个属性都有相同的权重

通过用zif代替第i个对象的rif来实现

数据规格化

其中

zif=rif-1/mf-1

第三步 相异性可以用

任意一种数值属性的距离

度量计算

使用zif作为第i个对象的f值

例 序数属性的相异性计算

有序数属性的对象数据如表所示

其中test属性为序数属性

Test有三个状态ordinary

good和excellent

则Mf=3

第一步

把Test的每个值替换为它的排位

则4个对象的排位值分别为3 2 1 3

第二步

通过将排位1映射为0.0

排位2映射为0.5

排位3映射为1.0

来实现对排位的规格化

第三步

使用欧几里得距离得到相异性矩阵

如图所示

通过计算可以看出

对象1与对象3最不相似

对象3与对象4也不相似

对象1与对象4是相似的

这符合其原始数值之间的关系

余弦相似性又称余弦相似度

是基于向量的

它利用向量空间中

两个向量夹角的余弦值

作为衡量两个个体间差异的大小

令向量x和y

是两个被p个分量描述的向量

两个向量的余弦相似性定义为

其中x范数定义为

√x1^2+x2^2+...xp^2

同理 y的范数定义为

√y1^2+y2^2+...+yp^2

该度量计算向量x和y之间夹角的余弦

余弦值为0意味两个向量呈90°夹角

即正交 没有匹配

余弦值越接近于1

夹角越小

向量之间的匹配越大

例 余弦相似度的计算

给定两个向量x和y

两个向量的余弦相似度计算如公式所示

结果为0.87

余弦相似性经常用于计算文本相似度

两个文本根据关键词建立两个向量

计算这两个向量的余弦值

就可以知道这两个文本

在统计学方法中的相似度情况

如果余弦值为1

则说明两篇文档完全相同

如果余弦值为0

则说明两篇文档完全不同