数据挖掘基础:度量数据的相似性和相异性
数据矩阵(data matrix)或称对象-属性结构:这种数据结构用关系表的形式或n×p(n个对象×p个属性)矩阵存放n个数据对象:?
相异性矩阵(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)。 相似性度量可以表示成相异性度量的函数。例如,对于标称数据 sim(i,j)=1-d(i,j) 标称属性的邻近性度量 “如何计算标称属性所刻画的对象之间的相异性?”两个对象i和j之间的相异性可以根据不匹配率来计算:
? 其中,m是匹配的数目(即i和j取值相同状态的属性数),而p是刻画对象的属性总数。我们可以通过赋予m较大的权重,或者赋给有较多状态的属性的匹配更大的权重来增加m的影响。 二元属性的邻近性度量
“那么,如何计算两个二元属性之间的相异性?”一种方法涉及由给定的二元数据计算相异性矩阵。如果所有的二元都被看做具有相同的权重,则我们得到一个两行两列的列联表——表2.3,其中q是对象i和j都取1的属性数,r是在对象i中取1、在对象j表2.3 二元属性的列联表对象i对象j中取0的属性数,s是在对象i中取0、在对象j中取1的属性数,而t是对象i和j都取0的属性数。属性的总数是p,其中p=q+r+s+t。
? 回忆一下,对于对称的二元属性,每个状态都同样重要。基于对称二元属性的相异性称做对称的二元相异性。如果对象i和j都用对称的二元属性刻画,则i和j的相异性为
? 对于非对称的二元属性,两个状态不是同等重要的;如病理化验的阳性(1)和阴性(0)结果。给定两个非对称的二元属性,两个都取值1的情况(正匹配)被认为比两个都取值0的情况(负匹配)更有意义。因此,这样的二元属性经常被认为是“一元的”(只有一种状态)。基于这种属性的相异性被称为非对称的二元相异性,其中负匹配数t被认为是不重要的,因此在计算时被忽略,如下所示:
? 互补地,我们可以基于相似性而不是基于相异性来度量两个二元属性的差别。例如,对象i和j之间的非对称的二元相似性可以用下式计算:
? (2.15)式的系数sim(i,j)被称做Jaccard系数,它在文献中被广泛使用。 闵可夫斯基距离 计算数值属性刻画的对象的相异性的距离度量,包括欧几里得距离、曼哈顿距离和闵可夫斯基距离。 最流行的距离度量是欧几里得距离(即,直线或“乌鸦飞行”距离)。令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。注意非负性被其他三个性质所蕴含。
(1) 闵氏距离的定义 ?????? 两个n维变量a(x11,x12,…,x1n)与 b(x21,x22,x2n)间的闵可夫斯基距离定义为: ? 其中p是一个变参数。 当p=1时,就是曼哈顿距离 当p=2时,就是欧氏距离 当p→∞时,就是切比雪夫距离 ?????? 根据变参数的不同,闵氏距离可以表示一类的距离。 (2)闵氏距离的缺点 闵氏距离,包括曼哈顿距离、欧氏距离和切比雪夫距离都存在明显的缺点。 举个例子:二维样本(身高,体重),其中身高范围是150~190,体重范围是50~60,有三个样本:a(180,50),b(190,50),c(180,60)。那么a与b之间的闵氏距离(无论是曼哈顿距离、欧氏距离或切比雪夫距离)等于a与c之间的闵氏距离,但是身高的10cm真的等价于体重的10kg么?因此用闵氏距离来衡量这些样本间的相似度很有问题。 ?????? 简单说来,闵氏距离的缺点主要有两个:(1)将各个分量的量纲(scale),也就是“单位”当作相同的看待了。(2)没有考虑各个分量的分布(期望,方差等)可能是不同的。 序数属性的邻近性度量
“如何处理序数属性?”在计算对象之间的相异性时,序数属性的处理与数值属性的非常类似。假设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)。 混合类型属性的相异性
一种这样的技术将不同的属性组合在单个相异性矩阵中,把所有有意义的属性转换到共同的区间[0.0,1.0]上。 假设数据集包含p个混合类型的属性,对象i和j之间的相异性d(i,j)定义为:
其中,指示符δ(f)ij=0,如果xif或xjf缺失(即对象i或对象j没有属性f的度量值),或者xif=xjf=0,并且f是非对称的二元属性;否则,指示符δ(f)ij=1。属性f对i和j之间相异性的贡献 根据它的类型计算:f是数值的: ?,其中h遍取属性f的所有非缺失对象。f是标称或二元的:如果xif=xjf,则 ?=0;否则=1。f是序数的:计算排位rif和 ?,并将zif作为数值属性对待。上面的步骤与我们所见到的各种单一属性类型的处理相同。唯一的不同是对于数值属性的处理,其中规格化使得变量值映射到了区间[0.0,1.0]。这样,即便描述对象的属性具有不同类型,对象之间的相异性也能够进行计算。 例2.22 混合类型属性间的相异性。我们来计算表2.2中对象的相异性矩阵。现在,我们将考虑所有属性,它们具有不同类型。在例2.17到例2.21中,我们对每种属性计算了相异性矩阵。处理test-1(它是标称的)和test-2(它是序数的)的过程与上文所给出的处理混合类型属性的过程是相同的。因此,在下面计算(2.22)式时,我们可以使用由test-1和test-2所得到的相异性矩阵。然而,我们首先需要对第3个属性test-3(它是数值的)计算相异性矩阵。即,我们必须计算d(3)ij。根据数值属性的规则,我们令maxhxh=64,minhxh=22。二者之差用来规格化相异性矩阵的值。结果,test-3的相异性矩阵为:
|