HAWQ + MADlib 玩转数据挖掘之（三）——向量
HAWQ + MADlib 玩转数据挖掘之（三）——向量
一、定义
这里不讨论向量严格的数学定义。在Madlib中，可以把向量简单理解为矩阵。矩阵是Madlib中数据的基本格式，当矩阵只有一维时，就是向量，1行n列的矩阵称为行向量，m行1列的矩阵称为列向量，1行1列的矩阵称为标量。
二、线性代数函数
Madlib的线性代数模块（linalg module）包括基本的线性代数操作的实用函数。利用线性代数函数可以很方便地实现新算法。这些函数操作向量（1维FLOAT8数组）和矩阵（2维FLOAT8数组）。注意，这类函数只接受FLOAT8数组参数，因此在调用函数时，需要将其它类型的数组转换为FLOAT8[]。
1. 函数概览
Madlib中的线性代数函数主要包括范数、距离、矩阵、聚合几类。表1列出了相关函数的简要说明。
表1
线性代数函数的完整列表，参见“linalg.sql_in File Reference”
2. 函数示例
（1）范数与距离函数
创建包含两个向量列的数据库表，并添加数据。
drop table if exists two_vectors;
create table two_vectors(
id integer,
a float8[],
b float8[]);
insert into two_vectors values
(1, '{3,4}', '{4,5}'),
(2, '{1,1,0,-4,5,3,4,106,14}', '{1,1,0,6,-3,1,2,92,2}');范数函数。
select id,
madlib.norm1(a),
madlib.norm2(a)
from two_vectors;结果：
id | norm1 | norm2
----+-------+------------------
1 | 7 | 5
2 | 138 | 107.238052947636距离函数。
select id,
madlib.dist_norm1(a, b),
madlib.dist_norm2(a, b),
madlib.dist_pnorm(a, b, 5) as norm5,
madlib.dist_inf_norm(a, b),
madlib.squared_dist_norm2(a, b) as sq_dist_norm2,
madlib.cosine_similarity(a, b),
madlib.dist_angle(a, b),
madlib.dist_tanimoto(a, b),
madlib.dist_jaccard(a::text[], b::text[])
from two_vectors;结果：
id | dist_norm1 | dist_norm2 | norm5 | dist_inf_norm | sq_dist_norm2 | cosine_similarity | dist_angle | dist_tanimoto | dist_jaccard
----+------------+------------------+------------------+---------------+---------------+-------------------+--------------------+--------------------+-------------------
1 | 2 | 1.4142135623731 | 1.14869835499704 | 1 | 2 | 0.999512076087079 | 0.0312398334302684 | 0.0588235294117647 | 0.666666666666667
2 | 48 | 22.6274169979695 | 15.585086360695 | 14 | 512 | 0.985403348449008 | 0.171068996592859 | 0.0498733684005455 | 0.833333333333333
(2 rows)（2）矩阵函数
创建包含矩阵列的数据库表。
drop table if exists matrix;
create table matrix(
id integer,
m float8[]);
insert into matrix values
(1, '{{4,5},{3,5},{9,0}}');调用矩阵函数。
select madlib.get_row(m, 1) as row_1,
madlib.get_row(m, 2) as row_2,
madlib.get_row(m, 3) as row_3,
madlib.get_col(m, 1) as col_1,
madlib.get_col(m, 2) as col_2
from matrix;结果：
row_1 | row_2 | row_3 | col_1 | col_2
-------+-------+-------+---------+---------
{4,5} | {3,5} | {9,0} | {4,3,9} | {5,5,0}
(1 row)（3）聚合函数
创建包含向量列的数据库表。
drop table if exists vector;
create table vector(
id integer,
v float8[]);
insert into vector values
(1, '{4,3}'),
(2, '{8,6}'),
(3, '{12,9}');调用聚合函数。
select madlib.avg(v),
madlib.normalized_avg(v),
madlib.matrix_agg(v)
from vector;结果：
avg | normalized_avg | matrix_agg
-------+----------------+----------------------
{8,6} | {0.8,0.6} | {{4,3},{8,6},{12,9}}
(1 row)三、稀疏向量
1. Madlib稀疏向量简介
Madlib实现了一种稀疏向量数据类型，名为“svec”，能够为包含大量重复元素的向量提供压缩存储。浮点数组进行各种计算，有时会有很多的零或其它缺省值，在科学计算、零售优化、文本处理等应用中，这是很常见的。每个浮点数在内存或磁盘中使用8字节存储，例如有如下float8[]数据类型的数组：
'{0, 33,...40,000 zeros..., 12, 22 }'::float8[]这个数组会占用320KB的内存或磁盘，而其中绝大部分存储的是0值。即使我们利用null位图，将0作为null存储，还是会得到一个5KB的null位图，内存使用效率还是不够高。何况在执行数组操作时，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个浮点数类型构成数组存储。除了节省空间，这种RLE表示也很容易实现向量操作，并使向量计算更快。SVEC模块提供了相关的函数库。Madlib 1.10版本仅支持float8稀疏向量类型。
2. 创建稀疏向量
（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;（3）使用聚合函数创建一个SVEC
select madlib.svec_agg(v1) from generate_series(1,10) v1;（4）利用madlib.svec_cast_positions_float8arr()函数创建SVEC
select madlib.svec_cast_positions_float8arr(
array[n1,n2,...nk], -- positions of values in vector
array[v1,v2,...vk], -- values at each position
length, -- length of vector
base);例如下面的表达式：
select madlib.svec_cast_positions_float8arr(
array[1,3,5],
array[2,4,6],
10,
0.0);生成的SVEC为：
svec_cast_positions_float8arr
-------------------------------
{1,1,1,1,1,5}:{2,0,4,0,6,0}（5）使用SVEC模块中定义的操作符
SVEC模块中除定义了众多函数，还定义了自己的操作符。为了使用SVEC的操作符，需要将将madlib模式添加到search_path中。SVEC操作符有：
-------------------------------------------------------
madlib | %*% | double precision[] | double precision[] | double precision |
madlib | %*% | double precision[] | svec | double precision |
madlib | %*% | svec | double precision[] | double precision |
madlib | %*% | svec | svec | double precision |
madlib | * | double precision[] | double precision[] | svec |
madlib | * | double precision[] | svec | svec |
madlib | * | svec | double precision[] | svec |
madlib | * | svec | svec | svec |
madlib | *|| | integer | svec | svec |
madlib | + | double precision[] | double precision[] | svec |
madlib | + | double precision[] | svec | svec |
madlib | + | svec | double precision[] | svec |
madlib | + | svec | svec | svec |
madlib | - | double precision[] | double precision[] | svec |
madlib | - | double precision[] | svec | svec |
madlib | - | svec | double precision[] | svec |
madlib | - | svec | svec | svec |
madlib | / | double precision[] | double precision[] | svec |
madlib | / | double precision[] | svec | svec |
madlib | / | svec | double precision[] | svec |
madlib | / | svec | svec | svec |
madlib | < | svec | svec | boolean |
madlib | <= | svec | svec | boolean |
madlib | <> | svec | svec | boolean |
madlib | = | svec | svec | boolean |
madlib | == | svec | svec | boolean |
madlib | > | svec | svec | boolean |
madlib | >= | svec | svec | boolean |
madlib | ^ | svec | svec | svec |
madlib | || | svec | svec | svec |3. 将文档向量化为稀疏矩阵
madlib.gen_doc_svecs函数提供一种高效的文档向量化方法，将文本转化为稀疏向量表示（MADlib.svec），这是MADlib机器学习算法经常需要的操作。该函数接收两个输入表，字典表和文档表，生成一个包含表示文档表中文档稀疏向量输出表。
（1）语法
madlib.gen_doc_svecs(output_tbl,
dictionary_tbl,
dict_id_col,
dict_term_col,
documents_tbl,
doc_id_col,
doc_term_col,
doc_term_info_col
);（2）参数
output_tbl：TEXT类型，输出表的名称。输出表具有下面的列：
- doc_id：__TYPE_DOC__类型，文档ID。__TYPE_DOC__列类型依赖于documents_tbl中doc_id_col的类型。
- sparse_vector：MADlib.svec，文档对应的稀疏矩阵表示。
dictionary_tbl：TEXT类型，包含特征的字典表名称。
dict_id_col：TEXT类型，dictionary_tbl中id列的名称。id是INTEGER或BIGINT类型。注意，id值必须是连续的，从0到字典中元素总数减1。
dict_term_col：TEXT类型，dictionary_tbl中包含特征条目的列名。
documents_tbl：TEXT类型，文档表的名称。
doc_id_col：TEXT类型，documents_tbl中id列的名称。
doc_term_col：TEXT类型，documents_tbl中条目列的名称。
doc_term_info_col：TEXT类型，documents_tbl中条目信息列的名称。条目信息列的类型应该是：
- INTEGER、BIGINT或DOUBLE PRECISION，值被直接用于生成向量。
- ARRAY，数组长度用于生成向量。
（3）示例
假设有如下文档，第一列是文档id，第二列是特征条目。
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}上面的数据可以用两种方式表示，如表documents_table可以有如下数据：
select * from documents_table order by id;结果：
id | term | count id | term | positions
----+----------+------- ----+----------+-----------
1 | is | 1 1 | is | {1}
1 | in | 1 1 | in | {4}
1 | one | 1 1 | one | {2}
1 | this | 1 1 | this | {0}
1 | the | 1 1 | the | {5}
1 | document | 1 1 | document | {3}
1 | corpus | 1 1 | corpus | {6}
2 | second | 1 2 | second | {3}
2 | document | 1 2 | document | {4}
2 | corpus | 1 2 | corpus | {7}
. | ... | .. . | ... | ...
4 | document | 2 4 | document | {1,7}
...下面的脚本分别使用两种表示创建文档表并生成数据。
drop table if exists documents_table1;
create table documents_table1
(id int,
term varchar(100),
count int);
insert into documents_table1 values
(1,'is',1), (1,'in',1), (1,'one',1), (1,'this',1), (1,'the',1), (1,'document',1), (1,'corpus',1),
(2,'i',1), (2,'am',1), (2,'the',2), (2,'second',1), (2,'document',1), (2,'corpus',1), (2,'in',1),
(3,'being',1), (3,'third',1), (3,'never',1), (3,'really',1), (3,'bothered',1), (3,'me',1), (3,'until',1), (3,'now',1),
(4,'the',2), (4,'document',2), (4,'before',1), (4,'me',1), (4,'is',1), (4,'third',1);
drop table if exists documents_table2;
create table documents_table2
(id int,
term varchar(100),
positions int[]);
insert into documents_table2 values
(1,'is','{1}'), (1,'in','{4}'), (1,'one','{2}'), (1,'this','{0}'), (1,'the','{5}'), (1,'document','{3}'), (1,'corpus','{6}'),
(2,'i','{0}'), (2,'am','{1}'), (2,'the','{2,6}'), (2,'second','{3}'), (2,'document','{4}'), (2,'corpus','{7}'), (2,'in','{5}'),
(3,'being','{0}'), (3,'third','{1}'), (3,'never','{2}'), (3,'really','{3}'), (3,'bothered','{4}'), (3,'me','{5}'), (3,'until','{6}'), (3,'now','{7}'),
(4,'the','{0,5}'), (4,'document','{1,7}'), (4,'before','{2}'), (4,'me','{3}'), (4,'is','{4}'), (4,'third','{6}');执行下面的语句创建字典表，注意字典表中的数据的顺序影响生成的稀疏向量输出表。
drop table if exists dictionary_table;
create table dictionary_table
as
select rn-1 id, term
from (select row_number() over (order by term) rn, term
from (select distinct term from documents_table1 order by term) t) t;使用dictionary_table和documents_table生成文档的稀疏向量，生成两种表示对应的输出表。
-- doc_term_info_col为count
drop table if exists svec_output1;
select * from madlib.gen_doc_svecs('svec_output1', 'dictionary_table', 'id', 'term',
'documents_table1', 'id', 'term', 'count');
-- doc_term_info_col为positions
drop table if exists svec_output2;
select * from madlib.gen_doc_svecs('svec_output2', 'dictionary_table', 'id', 'term',
'documents_table2', 'id', 'term', 'positions');查询创建的稀疏向量，两个输出表的结果相同。
select * from svec_output1 order by doc_id;
select * from svec_output2 order by doc_id;结果：
doc_id | sparse_vector
--------+-------------------------------------------------
1 | {4,2,1,2,3,1,2,1,1,1,1}:{0,1,0,1,0,1,0,1,0,1,0}
2 | {1,3,4,6,1,1,3}:{1,0,1,0,1,2,0}
3 | {2,2,5,3,1,1,2,1,1,1}:{0,1,0,1,0,1,0,1,0,1}
4 | {1,1,3,1,2,2,5,1,1,2}:{0,1,0,2,0,1,0,2,1,0}
(4 rows)在后面的稀疏向量扩展示例中，还会对本例的输出表含义及文档向量化的应用场景做更多说明。
4. 稀疏向量示例
（1）简单示例
对svec类型可以应用<、>、*、**、/、=、+、SUM等操作和运算，并且具有典型的向量操作的相关含义。例如，加法（+）操作是对两个向量中相同下标对应的元素进行相加。
-- 将madlib模式添加到搜索路径中
set search_path="$user",public,madlib;
-- 稀疏向量相加
select ('{0,1,5}'::float8[]::madlib.svec + '{4,3,2}'::float8[]::madlib.svec)::float8[];结果：
float8
---------
{4,4,7}
(1 row)如果最后不转换成float8[]：
select ('{0,1,5}'::float8[]::madlib.svec + '{4,3,2}'::float8[]::madlib.svec);结果：
?column?
-------------
{2,1}:{4,7}
(1 row)两个向量的点积（%*%）结果是float8类型，如(0*4 + 1*3 + 5*2) = 13：
select '{0,1,5}'::float8[]::madlib.svec %*% '{4,3,2}'::float8[]::madlib.svec;结果：
?column?
----------
13
(1 row)有些聚合函数svec对也是可用的，如SVEC_COUNT_NONZERO函数统计svec中每一列非0元素的个数，返回计数的svec。
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);
select madlib.svec_count_nonzero(a)::float8[] from list;结果：
svec_count_nonzero
--------------------
{1,2,3}
(1 row)svec数据类型中不应该使用null，因为null会显式表示为NVP（No Value Present）。
select '{1,2,3}:{4,null,5}'::madlib.svec;结果：
svec
-------------------
{1,2,3}:{4,NVP,5}
(1 row)含有null的svec相加，结果中显示NVP。
select '{1,2,3}:{4,null,5}'::madlib.svec + '{2,2,2}:{8,9,10}'::madlib.svec;结果：
?column?
--------------------------
{1,2,1,2}:{12,NVP,14,15}
(1 row)可以使用svec_proj()函数访问svec的元素，该函数的参数为一个svec和一个元素下标。
select madlib.svec_proj('{1,2,3}:{4,5,6}'::madlib.svec, 1) + madlib.svec_proj('{4,5,6}:{1,2,3}'::madlib.svec, 15);结果：
?column?
----------
7
(1 row)通过svec_subvec()函数可以访问一个svec的子向量，该参数的参数为一个svec，及其起止下标。
select madlib.svec_subvec('{2,4,6}:{1,3,5}'::madlib.svec, 2, 11);结果：
svec_subvec
-----------------
{1,4,5}:{1,3,5}
(1 row)svec的元素/子向量可以通过svec_change()函数进行改变。该函数有三个参数：一个m维的svec sv1，起始下标j，一个n维的svec sv2，其中j + n - 1 <= m，返回类似sv1的svec，但子向量sv1[j:j+n-1]被sv2所替换。
select madlib.svec_change('{1,2,3}:{4,5,6}'::madlib.svec,3,'{2}:{3}'::madlib.svec);结果：
svec_change
---------------------
{1,1,2,2}:{4,5,3,6}
(1 row)还有处理svec的高阶函数。例如，svec_lapply对应R语言中的lapply()函数。
select madlib.svec_lapply('sqrt', '{1,2,3}:{4,5,6}'::madlib.svec);结果：
svec_lapply
-----------------------------------------------
{1,2,3}:{2,2.23606797749979,2.44948974278318}
(1 row)svec相关函数的完整列表参见“svec.sql_in File Reference”。
（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}');现在有了字典和文档，我们要对每个文档中的出现单词的数量和比例应用向量运算，将文档进行分类。在开始处理前，需要找到每个文档中出现的字典中的单词。我们为每个文档创建一个稀疏特征向量（Sparse Feature Vector，SFV）。SFV是一个N维向量，N是字典单词的数量，SFV中的每个元素是文档中对每个字典单词的计数。
在svec中有一个函数可以从文档创建SFV（将文档转换为稀疏向量更为高效的方法，尤其对于大数据集而言，参见前面的“将文档矢量化为稀疏矩阵”）：
select madlib.svec_sfv((select a from features limit 1),b)::float8[]
from documents;结果：
svec_sfv
-----------------------------------------
{0,0,0,0,1,1,0,1,1,0,0,0,1,0,0,1,0,1,0}
{1,0,0,0,1,1,1,1,0,0,0,0,0,0,1,2,0,0,0}
{0,0,1,1,0,0,0,0,0,1,1,1,0,1,0,0,1,0,1}
{0,1,0,0,0,2,0,0,1,1,0,0,0,0,0,2,1,0,0}
(4 rows)注意，madlib.svec_sfv()函数的输出是每个文档一个向量，元素值是相应字典顺序位置上单词在文档中出现的次数。通过对比特征向量和文档，更容易地理解这一点：
select madlib.svec_sfv((select a from features),b)::float8[], b
from documents;结果：
svec_sfv | b
-----------------------------------------+--------------------------------------------------
{0,0,0,0,1,1,0,1,1,0,0,0,1,0,0,1,0,1,0} | {this,is,one,document,in,the,corpus}
{1,0,0,0,1,1,1,1,0,0,0,0,0,0,1,2,0,0,0} | {i,am,the,second,document,in,the,corpus}
{0,0,1,1,0,0,0,0,0,1,1,1,0,1,0,0,1,0,1} | {being,third,never,really,bothered,me,until,now}
{0,1,0,0,0,2,0,0,1,1,0,0,0,0,0,2,1,0,0} | {the,document,before,me,is,the,third,document}
(4 rows)可以看到文档"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 / Inverse Document 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。
对于这部分处理，我们需要一个具有字典维数（19）的稀疏向量，元素值为：
log(#documents/#Documents each term appears in)整个文档列表对应单一上述向量。#documents是文档总数，本例中是4，但对于每个字典单词都对应一个分母，其值为出现该单词的文档数。这个向量再乘以每个文档SFV中的计数，结果即为tf/idf权重。
drop table if exists corpus;
create table corpus as
(select a, madlib.svec_sfv((select a from features),b) sfv
from documents);
drop table if exists weights;
create table weights as
(select a docnum, madlib.svec_mult(sfv, logidf) tf_idf
from (select madlib.svec_log(madlib.svec_div(count(sfv)::madlib.svec,madlib.svec_count_nonzero(sfv))) logidf
from corpus) foo, corpus order by docnum);
select * from weights;结果：
docnum | tf_idf
--------+----------------------------------------------------------------------------------------------------------------
------------------------------------------
1 | {4,1,1,1,2,3,1,2,1,1,1,1}:{0,0.693147180559945,0.287682072451781,0,0.693147180559945,0,1.38629436111989,0,0.287682072451781,0,1.38629436111989,0}
2 | {1,3,1,1,1,1,6,1,1,3}:{1.38629436111989,0,0.693147180559945,0.287682072451781,1.38629436111989,0.693147180559945,0,1.38629436111989,0.575364144903562,0}
3 | {2,2,5,1,2,1,1,2,1,1,1}:{0,1.38629436111989,0,0.693147180559945,1.38629436111989,0,1.38629436111989,0,0.693147180559945,0,1.38629436111989}
4 | {1,1,3,1,2,2,5,1,1,2}:{0,1.38629436111989,0,0.575364144903562,0,0.693147180559945,0,0.575364144903562,0.693147180559945,0}
(4 rows)现在就可以使用文档向量的点积的ACOS，获得一个文档与其它文档的“角距离”。下面计算第一个文档与其它文档的角距离：
select docnum, 180. * ( acos( madlib.svec_dmin( 1., madlib.svec_dot(tf_idf, testdoc) / (madlib.svec_l2norm(tf_idf)*madlib.svec_l2norm(testdoc))))/3.141592654) angular_distance
from weights,(select tf_idf testdoc from weights where docnum = 1 limit 1) foo
order by 1;结果：
docnum | angular_distance
--------+------------------
1 | 0
2 | 78.8235846096986
3 | 89.9999999882484
4 | 80.0232034288617
(4 rows)可以看到文档1与自己的角距离为0度，而文档1与文档3的角距离为90度，因为它们之间没有任何相同的单词。
前面已经提到，SVEC提供了从给定的位置数组和值数组声明一个稀疏向量的功能。下面再看一个例子。
select madlib.svec_cast_positions_float8arr(array[1,2,7,5,87],array[.1,.2,.7,.5,.87],90,0.0);第一个整数数组表示第二个浮点数数组的位置，即结果数组的第1、2、5、7、87下标对应的值分别为0.1、0.2、0.5、0.7、0.87。位置本身不需要有序，但要和值的顺序保持一致。第三个参数表示数组的最大维数。小于1最大维度将被忽略，此时数组的最大维度就是位置数组中的最大下标。最后的参数表示没有提供下标的位置上的值。
结果：
svec_cast_positions_float8arr
-----------------------------------------------------
{1,1,2,1,1,1,79,1,3}:{0.1,0.2,0,0.5,0,0.7,0,0.87,0}
(1 row)