3.1 邻近度

MADlib的线性代数模块（linalg module）包括基本线性代数操作的实用函数，其中包括多种范式、距离、相似度、向量均值、矩阵聚合等函数。本节先讨论相似性和相异性的基本概念，然后对照概念说明MADlib的线性代数函数，并用简单示例描述这些函数的用法。

相似性和相异性是重要的概念，因为它们被许多机器学习技术所使用，如聚类、近邻分类和异常检测等。我们使用术语邻近度（proximity）表示相似性或相异性。两个对象之间的相似度（similarity）是指这两个对象相似程度的数值度量。两个对象越相似，它们的相似度就越高。通常，相似度是非负的，并常常在0（不相似）和1（完全相似）之间取值。两个对象之间的相异度（dissimilarity）是这两个对象差异程度的数值度量。对象越类似，它们的相异度就越低。术语距离（distance）经常用作相异度的同义词，用来表示特定类型的相异度。有时相异度在区间[0,1]中取值，但相异度在0和∞之间取值也很常见。

通常使用变换把相似度转换成相异度或相反，或者把邻近度变换到一个特定区间，如[0,1]。例如，我们可能有相似度，其值域从1到10，但是我们打算使用的算法或软件只能处理相异度，或只能处理[0,1]区间的相似度。这种变换相对独立于特定的邻近度度量方法。

3.1.1 MADlib的邻近度相关函数

1. 函数概览

利用MADlib提供的邻近度相关函数，可以很方便地实现新算法。这些函数操作的对象是向量（一维FLOAT8数组）和矩阵（二维FLOAT8数组）。注意，这类函数只接受FLOAT8数组参数，因此在调用函数时，需要将其他类型的数组转换为FLOAT8[]。表3-1列出了相关函数的简要说明。

表3-1 MADlib邻近度相关函数

2. 函数示例

（1）范数

select madlib.norm1('{1,-2,3}'),madlib.norm2('{1,-2,3}');

结果：

1范数的定义为向量各元素绝对值的和，2范数的定义是向量各元素平方和的平方根。根据定义下面的查询与范数函数的结果相同。

select sum(norm1) norm1, sqrt(sum(norm2)) norm2
  from (select abs(unnest('{1,-2,3}'::float[])) norm1 ,
               power(unnest('{1,-2,3}'::float[]),2) norm2) t;

（2）欧几里得距离（L2范数）

select madlib.dist_norm2('{1,-2,3}', '{4,-5,6}');

结果：

    dist_norm2
------------------
 5.19615242270663
(1 row)

2范数与欧几里得距离相对应。一维、二维、三维或高维空间中两个点x和y之间的欧几里得距离（Euclidean distance）d由如下公式定义：

其中，n是维数，而xk和yk分别是x和y的第k个属性值（分量）。

（3）闵可夫斯基距离（Lp范数）

select madlib.dist_pnorm('{1,-2,3}', '{4,-5,6}', 5);

结果：

欧几里得距离可以用闵可夫斯基距离（Minkowski distance）来推广：

其中r是标量参数。注意不要将参数r与维数（属性数）n混淆。欧几里得距离、曼哈顿距离和上确界距离是对n的所有值（1,2,3…）定义的，并且指定了将每个维（属性）上的差的组合成总距离的不同方法。

（4）曼哈顿距离（L1范数）

select madlib.dist_norm1('{1,-2,3}', '{4,-5,6}');

结果：

闵可夫斯基距离的r=1时称为曼哈顿距离，r=2时就是欧几里得距离。

（5）上确界距离（Lmax或L∞范数）

select madlib.dist_inf_norm('{1,-2,3}', '{4,-5,6}');

结果：

闵可夫斯基距离的r=∞时称为上确界距离。这是对象属性之间的最大距离。更正式地，L∞距离由下面的公式定义：

（6）平方欧几里得距离

select madlib.squared_dist_norm2('{1,-2,3}', '{4,-5,6}');

结果：

平方欧几里得距离即：

（7）Jaccard距离

select madlib.dist_jaccard('{1,-2,3}', '{4,-5,6}');

结果：

Jaccard距离的定义是1-Jaccard系数（Jaccard Coefficient）。Jaccard系数定义为A与B交集的大小与A与B并集的大小的比值。假定x和y是两个数据对象，代表两个事务。如果每个二元属性对应于商店的一种商品，1表示该商品被购买，而0表示该商品未被购买。由于未被顾客购买的商品数远远大于被购买的商品数，因此常常使用Jaccard系数来处理这种仅包含非对称二元属性的对象。Jaccard系数通常用符号J表示，由如下等式定义：

其中：

f00=x取0并且y取0的属性个数

f01=x取0并且y取1的属性个数

f10=x取1并且y取0的属性个数

f11=x取1并且y取1的属性个数

（8）Tanimoto距离

select madlib.dist_tanimoto('{1,-2,3}', '{4,-5,6}');

结果：

Tanimoto距离（谷本距离）定义为1-Tanimoto系数。Tanimoto系数又称广义Jaccard系数，可以用于文档数据，并在二元属性情况下归约为Jaccard系数。该系数用EJ表示，由下式定义：

（9）余弦相似度

select madlib.cosine_similarity('{1,-2,3}', '{4,-5,6}');

结果：

在介绍MADlib的稀疏向量时，曾经举了一个tf/idf算法的例子。当时我们使用了反余弦函数计算文档的角距离，从而以此判断文档的相似度（参见2.1.2小节）。文档的相似性度量不仅应当像Jaccard度量一样需要忽略0-0匹配，还必须能够处理非二元向量。文档相似性最常用的度量之一就是余弦相似度，其定义如下。若x和y是两个文档向量，则

其中，“·”表示向量点积，，‖x‖是向量x的长度，。

余弦相似度实际上是x和y之间夹角（余弦）的度量。这样，若余弦相似度为1，则x和y之间的夹角为0度，并且除大小（长度）之外，x和y是相同的；若余弦相似度为0，则x和y之间的夹角为90度，以文档为例，说明它们不包含任何相同的词（术语）。

余弦相似度公式可以写成下面的形式：

其中，x＇=x/‖x‖，y＇=y/‖y‖。x和y被它们的长度除，规范化成具有长度1。这意味着在计算相似度时，余弦相似度不考虑两个数据对象的量值。（当量值很重要时，欧几里得距离可能是一种更好的选择。）对于长度为1的向量，余弦度量可以通过简单地取点积计算。在需要大量对象之间的余弦相似度时，将对象规范化，使之具有单位长度可以减少计算时间。

（10）角距离

select madlib.dist_angle('{1,-2,3}', '{4,-5,6}');

结果：

角距离定义为余弦相似度上的反余弦函数：

dm=# select acos(madlib.cosine_similarity('{1,-2,3}', '{4,-5,6}'));
       acos
-------------------
 0.225726128552734
(1 row)

（11）取矩阵的行列

结果：

（12）求向量平均值

drop table if exists vector;
create table vector(id integer, v float8[]);
insert into vector values (1, '{4,1}'), (2, '{8,-6}'), (3, '{5,9}');
select madlib.avg(v) from vector;

结果：

平均值函数madlib.avg对一组向量分量求平均值，返回由分量平均值构成的结果向量。

（13）求向量的归一化平均值

select madlib.normalized_avg(v) from vector;

结果：

madlib.normalized_avg的计算过程为：

（1）将原数据中的向量做标准差归一化。

（2）对归一化后的数据求向量平均值。

（3）对结果向量再做一次标准差归一化，返回结果向量。

注意，madlib.normalized_avg函数只做归一化，不做中心化（均值不为0）。

（14）合并向量

select madlib.matrix_agg(v) from vector;

结果：

madlib.matrix_agg函数将参数中的一组向量合并为一个矩阵（二维数组）。

3.1.2 距离度量的中心化和标准化

距离度量的一个重要问题是当属性具有不同的值域时如何处理，这种情况通常称作“变量具有不同的尺度”。例如，基于年龄和收入两个属性来度量人之间的欧几里得距离，除非这两个属性是标准化的，否则两个人之间的距离将被收入所左右。

当属性具有不同值域（不同的方差）并且数据分布近似于正太分布时，需要标准化步骤对数据进行预处理。通过中心化和标准化处理，可以得到均值为0、标准差为1的服从正太分布的数据。

假设样本集X的均值（mean）为m，标准差（Standard Deviation）为s，那么X的标准化变量表示为：

假设有一组数值x1、x2、…、xn，其算术平均值为m，则标准差的计算公式为：

标准差是一组数据平均值分散程度的一种度量。标准差较大，表示大部分数值和其平均值之间差异较大；标准差较小，代表这些数值比较接近平均值。

通过简单的推导可得，两个向量x和y的标准化欧几里得距离的计算公式为：

其中，xk是向量x的第k个分量，yk向量y的第k个分量，sk是第k个分量上的标准差。这样，在计算距离时，不同特征的影响程度就一样了。如果将方差的倒数看成是权重，标准化欧氏距离公式也可以看作是一种加权欧氏距离。标准化欧几里得距离解决了不同属性的尺度（值域）不一致的问题。

3.1.3 选取正确的邻近度度量

邻近度度量的类型应该与数据类型相适应。对于稠密的、连续的数据，通常使用距离度量，如欧几里得距离。在机器学习中，取实数值的数据是连续的数据，而具有有限个值或无限但可数个值的数据称为离散数据。连续属性之间的邻近度通常用属性值的差来表示，并且距离度量提供了一种将这些差组合到总邻近性度量的良好的方法。尽管属性可能有不同的取值范围和不同的重要性，但这些问题通常可以使用标准化或加权的方法处理。

对于稀疏数据，常常包含非对称的属性，通常使用忽略0-0匹配的相似性度量。从概念上讲，这反映了如下事实：对于一对复杂对象，相似度依赖于它们共同具有的性质数目，而不是依赖于它们都缺失的性质数目。在特殊情况下，对于稀疏的、非对称的数据，大部分对象都只具有少量被属性描述的性质，因此如果考虑它们都不具有的性质，那么它们都高度相似。余弦、Jaccard和广义Jaccard度量对于这类数据是合适的。