IT虾米网

对数据的认识(二)详解

luoye 2018年07月04日 程序员 115 0
四、度量数据的相似性和相异性
1、数据矩阵和相异性矩阵
假设我们有n个对象(如人、商品或课程),被p个属性(又称维或特征,如年龄、身高、体重或性别)刻画。这些对象是x1=(x11,x12,…,x1p),x2=(x21,x22,…,x2p),等等,其中xij是对象xi的第j个属性的值。为简单计,以后我们称对象xi为对象i。这些对象可以是关系数据库的元组,也称数据样本或特征向量。

通常,主要的基于内存的聚类和最近邻算法都在如下两种数据结构上运行:

·数据矩阵(data matrix)或称对象-属性结构:这种数据结构用关系表的形式或n×p(n个对象×p个属性)矩阵存放n个数据对象:

 

每行对应于一个对象。在记号中,我们可能使用f作为遍取p个属性的下标。

·相异性矩阵(dissimilarity matrix)或称对象-对象结构:存放n个对象两两之间的邻近度(proximity),通常用一个n×n矩阵表示:

 

其中d(i,j)是对象i和对象j之间的相异性或“差别”的度量。一般而言,d(i,j)是一个非负的数值,对象i和j彼此高度相似或“接近”时,其值接近于0;而越不同,该值越大。注意,d(i,i)=0,即一个对象与自己的差别为0。此外,d(i,j)=d(j,i)。(为了易读性,我们不显示d(j,i),该矩阵是对称的。)相异性度量的讨论遍及本章的余下部分。

相似性度量可以表示成相异性度量的函数。例如,对于标称数据

                  sim(i,j)=1-d(i,j)(2.10)

其中,sim(i,j)是对象i和j之间的相似性。本章的其余部分,我们也对相似性度量进行讨论。


2、标称属性的邻近性度量
    两个对象i,j的相异性计算公式(根据不匹配率来计算):
         
 其中,m是匹配的数目(即i和j取值相同状态的属性数),而p是刻画对象的属性总数。

例2.17 标称属性之间的相异性。假设我们有表2.2中的样本数据,不过只有对象标识符和属性test-1是可用的,其中test-1是标称的。(在后面的例子中,我们将会用到test-2和test-3。)让我们来计算相异性矩阵,即(2.9)式


 

由于我们只有一个标称属性test-1,在(2.11)式中,我们令p=1,使得当对象i和j匹配时,d(i,j)=0;当对象不同时,d(i,j)=1。于是,我们得到


 

由此,我们看到除了对象1和4(即d(4,1)=0)之外,所有对象都互不相似。


 

或者,相似性可以用下式计算:

            





3、二元属性的邻近性度量
 
q ,r ,s ,t 是表示两个对象在1,0下的 属性个数(若某属性是i=1,j=1,则个数q+1)p=q+r+s+t 所有属性之和。
对称的二元属性两个对象i j的相异性:

有时候,可以忽略两个对象均为0时的属性(无意义),则称为 非对称的二元属性 的相异性计算公式:
相似性即为:

互补地,我们可以基于相似性而不是基于相异性来度量两个二元属性的差别。例如,对象i和j之间的非对称的二元相似性可以用下式计算:
  (2.15)式的系数sim(i,j)被称做Jaccard系数,它在文献中被广泛使用。

例2.18 二元属性之间的相异性。假设一个患者记录表(见表2.4)包含属性name(姓名)、gender(性别)、fever(发烧)、cough(咳嗽)、test-1、test-2、test-3和test-4,其中name是对象标识符,gender是对称属性,其余的属性都是非对称二元的。


 

对于非对称属性,值Y(yes)和P(positive)被设置为1,值N(no或negative)被设置为0。假设对象(患者)之间的距离只基于非对称属性来计算。71根据(2.14)式,三个患者Jack、Mary和Jim两两之间的距离如下:


 

这些度量显示Jim和Mary不大可能患类似的疾病,因为他们具有最高的相异性。在这三个患者中,Jack和Mary最可能患类似的疾病。


4、数值属性的相异性:闵可夫斯基距离、欧几里得距离、曼哈顿距离

最流行的距离度量是欧几里得距离(即,直线或“乌鸦飞行”距离)。令i=(xi1,xi2,…,xip)和j=(xj1,xj2,…,xjp)是两个被p个数值属性描述的对象。对象i和j之间的欧几里得距离定义为:

 

另一个著名的度量方法是曼哈顿(或城市块)距离,之所以如此命名,是因为它是城市两点之间的街区距离(如,向南2个街区,横过3个街区,共计5个街区)。其定义如下:

 

欧几里得距离和曼哈顿距离都满足如下数学性质:

非负性:d(i,j)≥0:距离是一个非负的数值。

同一性:d(i,i)=0:对象到自身的距离为0。

三角不等式:d(i,j)≤d(i,k)+d(k,j):从对象i到对象j的直接距离不会大于途经任何其他对象k的距离。

满足这些条件的测度称做度量(metric)1。注意非负性被其他三个性质所蕴含。

闵可夫斯基距离(Minkowski distance)是欧几里得距离和曼哈顿距离的推广,定义如下:


 

其中,h是实数,h≥1。(在某些文献中,这种距离又称Lp范数(norm),其中p就是我们的h。我们保留p作为属性数,以便于本章的其余部分一致。)当p=1时,它表示曼哈顿距离(即,L1范数);当p=2表示欧几里得距离(即,L2范数)。

上确界距离(又称Lmax,L∞范数和切比雪夫(Chebyshev)距离)是h→∞时闵可夫斯基距离的推广。为了计算它,我们找出属性f,它产生两个对象的最大值差。这个差是上确界距离,更形式化地定义为:


 

L∞范数又称一致范数(uniform norm)。


如果对每个变量根据其重要性赋予一个权重,则加权的欧几里得距离可以用下式计算:

 

加权也可以用于其他距离度量。


5、序数属性的邻近性度量

“如何处理序数属性?”在计算对象之间的相异性时,序数属性的处理与数值属性的非常类似。假设f是用于描述n个对象的一组序数属性之一。关于f的相异性计算涉及如下步骤:

1.第i个对象的f值为xif,属性f有Mf个有序的状态,表示排位1,…,Mf。用对应的排位rif∈{1,…,Mf}取代xif。

2.由于每个序数属性都可以有不同的状态数,所以通常需要将每个属性的值域映射到[0.0,1.0]上,以便每个属性都有相同的权重。我们通过用zif代替第i个对象的rif来实现数据规格化,其中

 

3.相异性可以用2.4.4节介绍的任意一种数值属性的距离度量计算,使用zif作为第i个对象的f值。

例2.21 序数型属性间的相异性。假定我们有前面表2.2中的样本数据,不过这次只有对象标识符和连续的序数属性test-2可用。test-2有三个状态,分别是fair、good和excellent,也就是Mf=3。第一步,如果我们把test-2的每个值替换为它的排位,则4个对象将分别被赋值为3、1、2、3。第二步,通过将排位1映射为0.0,排位2映射为0.5,排位3映射为1.0来实现对排位的规格化。第三步,我们可以使用比如说欧几里得距离((2.16)式)得到如下的相异性矩阵:

因此,对象1与对象2最不相似,对象2与对象4也不相似(即,d(2,1)=1.0,d(4,2)=1.0)。这符合直观,因为对象1和对象4都是excellent。对象2是fair,在test-2的值域的另一端。

序数属性的相似性值可以由相异性得到:sim(i,j)=1-d(i,j)。




7、余弦相似性:是一种度量,它可以用来比较文档,或针对给定的查询词向量对文档排序。

文档用数以千计的属性表示,每个记录文档中一个特定词(如关键词)或短语的频度。这样,每个文档都被一个所谓的词频向量(term-frequency vector)表示。例如,在表2.5中,我们看到文档1包含词team的5个实例,而hockey出现3次。正如计数值0所示,coach在整个文档中未出现。这种数据可能是高度非对称的。


 

词频向量通常很长,并且是稀疏的(即,它们有许多0值)。使用这种结构的应用包括信息检索、文本文档聚类、生物学分类和基因特征映射。对于这类稀疏的数值数据,本章我们研究过的传统的距离度量效果并不好。例如,两个词频向量可能有很多公共0值,意味对应的文档许多词是不共有的,而这使得它们不相似。我们需要一种度量,它关注两个文档确实共有的词,以及这种词出现的频率。换言之,我们需要忽略0匹配的数值数据度量。

余弦相似性是一种度量,它可以用来比较文档,或针对给定的查询词向量对文档排序。令x和y是两个待比较的向量,使用余弦度量作为相似性函数,我们有


 

其中,‖x‖是向量x=(x1,x2,…,xp)的欧几里得范数,定义为。从概念上讲,它就是向量的长度。类似地,‖y‖是向量y的欧几里得范数。该度量计算向量x和y之间夹角的余弦。余弦值0意味两个向量呈90°夹角(正交),没有匹配。余弦值越接近于1,夹角越小,向量之间的匹配越大。注意,由于余弦相似性度量不遵守2.4.4节定义的度量测度性质,因此它被称做非度量测度(nonmetric measure)。

例2.23 两个词频向量的余弦相似性。假设x和y是表2.5的前两个词频向量。即x=(5,0,3,0,2,0,0,2,0,0)和y=(3,0,2,0,1,1,0,1,0,1)。x和y的相似性如何?使用(2.23)式计算这两个向量之间的余弦相似性,我们得到:


 

因此,如果使用余弦相似性度量比较这两个文档,它们将被认为是高度相似的。

当属性是二值属性时,余弦相似性函数可以用共享特征或属性解释。假设如果xi=1,则对象x具有第i个属性。于是,x·y是x和y共同具有的属性数,而xy是x具有的属性数与y具有的属性数的几何均值。于是,sim(x,y)是公共属性相对拥有的一种度量。

对于这种情况,余弦度量的一个简单的变种如下:


 

这是x和y所共有的属性个数与x或y所具有的属性个数之间的比率。这个函数被称为Tanimoto系数或Tanimoto距离,它经常用在信息检索和生物学分类中。


发布评论

分享到:

IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

对数据的认识(一)详解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。