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度量對于這類數據是合適的。