对数据的认识(二)详解程序员

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

·数据矩阵（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.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）之外，所有对象都互不相似。

或者，相似性可以用下式计算：

例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最可能患类似的疾病。

最流行的距离度量是欧几里得距离（即，直线或“乌鸦飞行”距离）。令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）¹。注意非负性被其他三个性质所蕴含。

闵可夫斯基距离（Minkowski distance）是欧几里得距离和曼哈顿距离的推广，定义如下：

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

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

L∞范数又称一致范数（uniform norm）。

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

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

“如何处理序数属性？”在计算对象之间的相异性时，序数属性的处理与数值属性的非常类似。假设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)。

文档用数以千计的属性表示，每个记录文档中一个特定词（如关键词）或短语的频度。这样，每个文档都被一个所谓的词频向量（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距离，它经常用在信息检索和生物学分类中。