2.1 向量

數學中的向量（vector，也稱為歐幾里得向量、幾何向量、矢量）是一個具有大小（magnitude）和方向（direction）的值，可以形象化地表示為帶箭頭的線段。箭頭所指代表向量的方向，線段長度代表向量的大小。圖2-1（a）給出了兩個向量：向量u長度為1、平行于y軸，向量v長度為2、與x軸夾角為45°。圖2-1（b）和圖2-1（c）分別以有向線段表示兩個向量的差與和。

圖2-1 兩個向量以及它們的和與差

2.1.1 MADlib中的向量操作函數

在MADlib中，一維數組與向量具有相同的含義。MADlib的數組運算模塊（array_ops）提供了一組用C實現的基本數組操作，是機器學習算法的支持模塊。數組運算函數支持以下數字類型：

?SMALLINT

?INTEGER

?BIGINT

?REAL

?DOUBLE PRECISION（FLOAT8）

?NUMERIC（內部被轉化為FLOAT8，可能丟失精度）

數組運算函數列表及功能描述如表2-1所示。

表2-1 MADlib數組運算函數

下面用具體的例子說明函數的含義及用法。

（1）建立具有兩個整型數組列array1和array2的數據庫表并添加數據。

drop table if exists array_tbl;
create table array_tbl
( id integer, array1 integer[], array2 integer[] );

insert into array_tbl values
( 1, '{1,2,3,4,5,6,7,8,9}','{9,8,7,6,5,4,3,2,1}' ),
( 2, '{1,1,0,0,1,2,3,99,8}','{0,0,0,-5,4,1,1,7,6}');

（2）查詢array1列的最小值及下標、最大值及下標、平均值和標準差。

select id, madlib.array_min(array1)min,
           madlib.array_max(array1) max,
           madlib.array_min_index(array1) min_idx,
           madlib.array_max_index(array1) max_idx,
           madlib.array_mean(array1) mean,
           madlib.array_stddev(array1) stddev
from array_tbl;

結果：

說明：

?MADlib的數組下標從1開始。

?標準差的計算公式為。其中，μ表示數組元素平均值。

可以執(zhí)行下面的查詢驗證標準差，結果同樣是32.4259840936932。

select sqrt(sum(power(a-avg_a,2))/(count(*)-1))
 from (select avg(a) avg_a
         from (select unnest(array1) a from array_tbl where id=2) t) t1,
      (select unnest(array1) a from array_tbl where id=2) t2;

（3）執(zhí)行數組加減運算。

select id, madlib.array_add(array1,array2), madlib.array_sub(array1,array2)
  from array_tbl;

結果：

與數的加法一樣，向量的加法也具有一些我們熟知的性質。如果u、v和w是3個向量，那么向量的加法具有如下性質：

?向量加法的交換律，加的次序不影響結果：u+v=v+u。

?向量加法的結合律，相加時向量分組不影響結果：(u+v)+w=u+(v+w)。

?向量加法單位元存在性，存在一個零向量（zero vector），簡記為0，是單位元。對于任意向量u，有u+0=u。

?向量加法逆元存在性，對于每個向量u，都存在一個逆向量-u，使得u + (-u)=0。

（4）數組乘以一個標量。

select id,
madlib.array_scalar_mult(array1,3), madlib.array_scalar_mult(array1,-3)
  from array_tbl;

結果：

標量乘改變向量的量值，若標量是正則方向不變，若標量為負則方向相反。假設u和v是向量、α和β是標量（數），向量的標量乘法具有如下性質：

?標量乘法的結合律。被兩個標量乘的次序不影響結果：α(βu) =(αβ)u。

select id,
       madlib.array_scalar_mult(madlib.array_scalar_mult(array1,3),2),
       madlib.array_scalar_mult(madlib.array_scalar_mult(array1,2),3)
  from array_tbl;

結果：

?標量加法對標量與向量乘法的分配率。兩個標量相加后乘以一個向量等于每個標量乘以該向量之后的結果向量相加：(α+β)u =αu +βu。

select id,
       madlib.array_scalar_mult(array1,5),
       madlib.array_add
       (madlib.array_scalar_mult(array1,2),madlib.array_scalar_mult(array1,3))
  from array_tbl;

結果：

?標量乘法對向量加法的分配率。兩個向量相加之后的和與一個標量相乘等于每個向量與該標量相乘然后相加：α(u+v)=αu+αv。

select id,
       madlib.array_scalar_mult(madlib.array_add(array1, array2),3),
       madlib.array_add
       (madlib.array_scalar_mult(array1,3),madlib.array_scalar_mult(array2,3))
  from array_tbl;

結果：

?標量單位元的存在性。如果α=1，那么對于任何向量u都有αu=u。

由向量加法和標量與向量乘法引出了向量空間的概念。向量空間（vector space）是向量的集合，連同一個相關聯的標量集（如實數集），滿足上述性質，并且向量加法和標量與向量乘法是封閉的。封閉是指向量相加的結果、向量與標量相乘的結果都是原向量集中的向量。向量空間具有如下性質：任何向量都可以用一組稱作基（basis）的向量線性組合（linear combination）表示。更明確地說，如果u1，…，un是基向量，那對于任意向量v，都可以找到n個標量的集合{α1，…，αn}使得。我們稱基向量生成（span）了該向量空間。向量空間的維（dimension）是形成基所需要的最少向量數。通常，我們選取具有單位長度的基向量。

基向量通常是正交的（orthogonal）。向量正交是直線垂直的二維概念的推廣。從概念上講，正交向量是不相關的或獨立的。如果基向量是相互正交的，那么將向量表示成基向量的線性組合事實上把該向量分解成一些獨立分量（independent component）。

因此，n維空間的向量可以看作標量（數）的n元組。為了具體地解釋，考慮二維歐幾里得空間，其中每個點都與一個表示該點到原點的位移的向量相關聯。到任意點的位移向量都可以用x方向和y方向的位移和表示。這些位移分別是該點的x和y坐標。

我們使用記號v=(v1, v2, …, vn-1, vn)引述向量v的分量。注意，vi是向量v的一個分量，而vi是向量集中的一個向量。從向量的分量角度看，向量的加法變得簡單并易于理解。為了將兩個向量相加，我們只需要簡單地將對應的分量相加。例如，(2,3)+(4,2)=(6,5)。為了計算標量乘以向量，我們只需要用標量乘以每個分量即可，如3×(2,3)=(6,9)。

（5）數組乘除。注意，這里過濾掉id=2的行，否則查詢會因為除零錯誤而失敗。

select id,
madlib.array_mult(array1,array2), madlib.array_div(array1,array2)
  from array_tbl
 where 0 != all(array2);

結果：

參與計算的兩個數組都是整型，結果也是整型，因此除法運算的結果都被取整。與加法類似，數組乘除運算實際也就是向量分量上的乘除：

select array_agg(a * b), array_agg(a/b)
 from (select unnest(array1) a, unnest(array2) b
         from array_tbl where id=1) t;

結果：

（6）計算數組點積。

select id, madlib.array_dot(array1,array2)
  from array_tbl;

結果：

兩個向量u和v的點積u·v的定義為：。也就是說，兩個向量的點積用向量對應分量的乘積的和來計算，如下面的查詢結果為750。

select sum(a * b)
  from (select unnest(array1) a, unnest(array2) b
          from array_tbl where id=2) t;

由點積的定義來說明何謂兩個向量正交。在歐式空間中，可以證明兩個非零向量的點積為0當且僅當它們是垂直的。從幾何角度，兩個向量定義一個平面，并且它們的點積為0當且僅當這兩個向量在平面內的夾角等于90°。我們說這樣的兩個向量是正交的（orthogonal）。

（7）向量規(guī)范化。

select madlib.normalize(array1) from array_tbl;

結果：

點積也可以用來計算歐式空間中的向量長度：。向量長度又稱范數（norm），并記作‖u‖。給定一個向量u，我們可以通過用其長度除u的每個分量（通過計算u/‖u‖）找到一個向量，它與u指向相同的方向，但是具有單位長度。這稱作將該向量規(guī)范化，具有L2范數1。根據規(guī)范化的定義，下面的查詢與規(guī)范化函數結果相同：

select madlib.array_scalar_mult
(array1::float[],1/sqrt(madlib.array_dot(array1, array1)))
  from array_tbl;

并且可以使用下面的查詢驗證范數為1：

select id,sum(a)
  from(select id,power(unnest(madlib.normalize(array1)),2) a from array_tbl)t
group by id;

給定向量范數，向量的點積也可以寫成：

u·v=‖u‖‖v‖cos(θ)

其中，θ是兩個向量之間的夾角。把項分組并重新排列，上式可以改寫成：

u·v=(‖v‖cos(θ))‖u‖=vu‖u‖

其中，vu= ‖v‖cos(θ)表示向量v在u的方向上的長度，如圖2-2所示。如果u是單位向量，那么該點積是v在u方向上的分量，稱為v在u上的正交投影（orthogonal projection）。當然，如果v是單位向量，那么該點積也是u在v方向上的投影。

圖2-2 向量v在向量u方向的正交投影

一個與正交性密切相關的概念是線性獨立性（linear independent）。如果一個向量集中的每個向量都不能表示成該集合中其他向量的線性組合，那么該集合是線性獨立的。如果一個向量集不是線性獨立的，那么它們是線性依賴的（linear dependent）。我們希望基中每個向量都不線性依賴于其余的基向量。如果選擇相互正交（獨立的）基向量，就會自動得到一個線性獨立的基向量集，因為任意兩個向量都正交的向量集是線性獨立的。

（8）構造一個9個元素的數組并將數組元素的值設為1.3。

select madlib.array_fill(madlib.array_of_float(9), 1.3::float);

結果：

array_of_float函數構造一個包含9個元素的數組，初始值為0。array_fill填充數組元素值。array_fill函數中第一個參數的數組元素數據類型需要與第二個參數的數據類型相同。

（9）過濾掉數組中的指定元素。

select madlib.array_filter(array1),
       madlib.array_filter(array1,2),
       madlib.array_filter(array1,20)
  from array_tbl;

結果：

在沒有給出第二個參數的情況下，madlib.array_filter函數默認過濾掉數組中的0元素，如果給出了第二個元素，就從第一個參數指定的數組中過濾掉該值。如果值在數組中不存在，就返回原數組。

（10）將二維數組列展開為一維數組集合。

array_unnest_2d_to_1d是MADlib 1.11版本新增的函數，用于將二維數組展開為一維數組。1.10版本并無此函數，但可以創(chuàng)建一個UDF實現。

之后就可以調用函數展開二維數組：

結果：

2.1.2 稀疏向量

有些數據集具有非對稱特征，一個對象的大部分屬性值都為0，在許多情況下，非零項還不到1%。實際上，稀疏性（sparsity）是一個優(yōu)點，因為只有非零值才需要存儲和處理，這將節(jié)省大量的計算時間和存儲空間。此外，有些機器學習算法僅適合處理稀疏數據。

1. MADlib的稀疏向量

MADlib的svec模塊實現了一種稀疏向量數據類型，能夠為包含大量重復元素的向量提供壓縮存儲。浮點數組可進行各種計算，有時會有很多的零或其他默認值，在科學計算、零售優(yōu)化、文本處理等應用中是很常見的。每個浮點數在內存或磁盤中占用8字節(jié)，節(jié)省多個零值的存儲空間通常是有益的，而且跳過零值對于很多向量計算也會提升性能。

MADlib 1.10版本僅支持FLOAT8稀疏向量類型。例如，有如下float8[]數據類型的數組：

'{0, 33,...40000個0..., 12, 22 }'::float8[]

這個數組會占用320KB的內存或磁盤，而其中絕大部分存儲的是0值。即使我們利用null位圖將0作為null存儲，還是會得到一個5KB（40000/8）的null位圖，內存使用效率還是不夠高。何況在執(zhí)行數組操作時，40000個零列上的計算結果并不重要。為了解決這個向量存儲問題，svec類型使用行程長度編碼（Run Length Encoding, RLE），即用一個數–值對數組表示稀疏向量。上面的數組以這種方式被存儲為：

'{1,1,40000,1,1}:{0,33,0,12,22}'::madlib.svec

就是說1個0、1個33、40000個0等，只使用5個整型和5個浮點數類型構成數組存儲。除了節(jié)省空間，這種RLE表示也很容易實現向量操作，并使向量計算更快。svec模塊提供了稀疏向量數據類型相關的函數庫。

2. 創(chuàng)建稀疏向量

可以利用以下四種方式創(chuàng)建稀疏向量。

（1）直接使用常量表達式構建一個svec。

select'{n1,n2,...,nk}:{v1,v2,...vk}'::madlib.svec;

其中n1、n2、…、nk分別指定值v1、v2、…、vk的個數，例如：

（2）將一個float數組轉換成svec。

select('{v1,v2,...vk}'::float[])::madlib.svec;

例如：

dm=# select ('{2,4,4,4,6,6,6,6,6}'::float[])::madlib.svec;
      svec
-----------------
 {1,3,5}:{2,4,6}
row)

（3）使用聚合函數創(chuàng)建一個svec，例如：

（4）利用madlib.svec_cast_positions_float8arr()函數創(chuàng)建svec，例如：

此查詢語句的含義是，生成一個10個元素的svec向量，其中1、3、5位置上的值分別是2、4、6，其他位置的值為0。svec模塊的svec_cast_positions_float8arr函數提供了從給定的位置數組和值數組聲明一個稀疏向量的功能。下面再看一個例子：

第一個整數數組表示第二個浮點數數組的位置，即結果數組的第1、2、5、7、87下標對應的值分別為0.1、0.2、0.5、0.7、0.87。位置本身不需要有序，但要和值的順序保持一致。第三個參數表示數組的最大維數。小于1最大維度將被忽略，此時數組的最大維度就是位置數組中的最大下標。最后的參數表示沒有提供下標的位置上的值。

3. 稀疏向量示例

（1）簡單示例

對svec類型可以應用<、>、*、**、/、=、+、SUM等操作和運算，并且具有典型的向量操作的相關含義。例如，加法（+）操作是對兩個向量中相同下標對應的元素進行相加。為了使用svec模塊中定義的運算符，需要將madlib模式添加到search_path中。

dm=# -- 將madlib模式添加到搜索路徑中
dm=# set search_path="$user",public,madlib;
SET
dm=# -- 稀疏向量相加
dm=# select ('{0,1,5}'::float8[]::madlib.svec
dm(#        +'{4,3,2}'::float8[]::madlib.svec)::float8[];
 float8
---------
 {4,4,7}
(1 row)

如果最后不轉換成float8[]，結果就是一個svec類型：

兩個向量的點積（%*%）結果是FLOAT8類型，如(0*4+1*3+5*2)=13：

有些聚合函數對svec也是可用的，如svec_count_nonzero。

drop table if exists list;
create table list (a madlib.svec);
insert into list values
('{0,1,5}'::float8[]::madlib.svec),('{10,0,3}'::float8[]::madlib.svec),
('{0,0,3}'::float8[]::madlib.svec),('{0,1,0}'::float8[]::madlib.svec);

svec_count_nonzero函數統(tǒng)計svec中每一列非0元素的個數，返回計數的svec。

svec數據類型中不應該使用NULL，因為NULL會顯式表示為NVP（No Value Present）。

dm=# select'{1,2,3}:{4,null,5}'::madlib.svec;
       svec
-------------------
 {1,2,3}:{4,NVP,5}
(1 row)

含有NULL的svec相加，結果中顯示NVP。

可以使用svec_proj()函數訪問svec元素，該函數的參數為一個svec和一個元素下標。

通過svec_subvec()函數可以訪問一個svec的子向量，該函數的參數為一個svec及其起止下標。

svec的元素／子向量可以通過svec_change()函數進行改變。該函數有三個參數：一個m維的svec sv1，起始下標j，一個n維的svec sv2，其中j+n-1≤m，返回類似sv1的svec，但子向量sv1[j:j+n-1]被sv2所替換。

還有處理svec的高階函數，如svec_lapply對應R語言中的lapply()函數。這里的所謂高階函數，可以簡單理解為函數（svec_lapply）的參數是函數名（sqrt）。

（2）擴展示例

下面的示例是稀疏向量的一個具體應用，說明如何將文檔轉化為稀疏向量，并進一步對文檔歸類。假設有一個由若干單詞組成的文本數組：

drop table if exists features;
create table features (a text[]);
insert into features values
      ('{am,before,being,bothered,corpus,document,i,in,is,me,
         never,now,one,really,second,the,third,this,until}');

同時有一個文檔集合，每個文檔表示為一個單詞數組：

drop table if exists documents;
create table documents(a int,b text[]);
insert into documents values
      (1,'{this,is,one,document,in,the,corpus}'),
      (2,'{i,am,the,second,document,in,the,corpus}'),
      (3,'{being,third,never,really,bothered,me,until,now}'),
      (4,'{the,document,before,me,is,the,third,document}');

如果忽略詞的順序，文檔就可以用詞向量表示，其中每個詞是向量的一個分量（屬性），而每個分量的值對應詞在文檔中出現的次數。文檔集合的這種表示通常稱作文檔–詞矩陣（document-term matrix）。文檔是矩陣的行，詞是矩陣的列。實踐應用時，僅存放稀疏數據矩陣的非零項。

現在有了字典和文檔，我們要對每個文檔中出現單詞的數量和比例應用向量運算，將文檔進行分類。在開始處理前，需要找到每個文檔中出現的字典中的單詞。我們?yōu)槊總€文檔創(chuàng)建一個稀疏特征向量（Sparse Feature Vector, SFV）。SFV是一個N維向量，N是字典單詞的數量，SFV中的每個元素都是文檔中對每個字典單詞的計數。svec模塊中有一個函數可以從文檔創(chuàng)建SFV：

注意，madlib.svec_sfv()函數的輸出是每個文檔一個向量，元素值是相應字典順序位置上單詞在文檔中出現的次數。通過對比特征向量和文檔，更容易理解這一點：

可以看到文檔"i am the second document in the corpus"的SFV為{1,3*0,1,1,1,1,6*0,1,2,3*0}。單詞“am”是字典中的第一個單詞，并且在文檔中只出現一次。單詞“before”沒有出現在文檔中，所以值為0，以此類推。函數madlib.svec_sfv()能夠將大量文檔高速并行轉換為對應的SFV。

分類處理的其余部分都是向量運算。實際應用中很少使用實際計數值，而是將計數轉為權重。最普通的權重叫作tf/idf，對應術語是Term Frequency / InverseDocument Frequency（詞頻–逆文檔頻率）。對給定文檔中給定單詞的權重計算公式為：

{#Times in document} * log {#Documents /#Documents the term appears in}

例如，單詞“document”在文檔A中的權重為1* log (4/3)，而在文檔D中的權重為2*log (4/3)。在每個文檔中都出現的單詞的權重為0，因為log(4/4)=log(1)=0，僅出現在一個文檔中的詞具有最大權重log（文檔數量）。TF-IDF是一種統(tǒng)計方法，用以評估一個詞對于一個文件集或一個資料庫其中一個文檔的重要程度。詞的重要性隨著它在文檔中出現的次數成正比增加，但同時會隨著它在資料庫中出現的頻率成反比下降。簡單來說就是一個詞在一篇文檔中出現的次數越多，同時在所有文檔中出現的次數越少，越能夠代表該文章。

對于這部分處理，我們需要一個具有字典維數（19）的稀疏向量，元素值為：

log(#documents/#Documents each term appearsin)

整個文檔列表對應單一上述向量。#documents是文檔總數，本例中是4，但對于每個字典單詞都對應一個分母，其值為出現該單詞的文檔數。這個向量再乘以每個文檔SFV中的計數，結果即為tf/idf權重。

查詢權重：

盡管文檔具有數以百千計或數以萬計的屬性（詞），但是每個文檔向量都是稀疏的，因為它具有相對較少的非零屬性值。這樣，相似性不能依賴共享0的個數，因為任意兩個文檔多半不會包含許多相同的詞，如果統(tǒng)計0-0匹配，那么大多數文檔都會與其他大部分文檔非常類似。因此文檔的相似性度量需要忽略0-0匹配，而且必須能處理非二元向量。下面定義的余弦相似度（cosinesimilarity）就是文檔相似性最常用的度量之一。如果x和y是兩個文檔向量，則：

其中，“·”表示向量點積，，‖x‖是向量x的長度，。

現在就可以使用文檔向量點積的ACOS獲得一個文檔與其他文檔的“角距離”。下面計算第一個文檔與其他文檔的角距離：

可以看到文檔1與自己的角距離為0度，而文檔1與文檔3的角距離為90度，因為它們之間沒有任何相同的單詞。