http://git-wip-us.apache.org/repos/asf/incubator-madlib-site/blob/b5b51c69/docs/v1.11/group__grp__svd.html ---------------------------------------------------------------------- diff --git a/docs/v1.11/group__grp__svd.html b/docs/v1.11/group__grp__svd.html new file mode 100644 index 0000000..beec5ea --- /dev/null +++ b/docs/v1.11/group__grp__svd.html @@ -0,0 +1,411 @@ +<!-- HTML header for doxygen 1.8.4--> +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd";> +<html xmlns="http://www.w3.org/1999/xhtml";> +<head> +<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/> +<meta http-equiv="X-UA-Compatible" content="IE=9"/> +<meta name="generator" content="Doxygen 1.8.13"/> +<meta name="keywords" content="madlib,postgres,greenplum,machine learning,data mining,deep learning,ensemble methods,data science,market basket analysis,affinity analysis,pca,lda,regression,elastic net,huber white,proportional hazards,k-means,latent dirichlet allocation,bayes,support vector machines,svm"/> +<title>MADlib: Singular Value Decomposition</title> +<link href="tabs.css" rel="stylesheet" type="text/css"/> +<script type="text/javascript" src="jquery.js"></script> +<script type="text/javascript" src="dynsections.js"></script> +<link href="navtree.css" rel="stylesheet" type="text/css"/> +<script type="text/javascript" src="resize.js"></script> +<script type="text/javascript" src="navtreedata.js"></script> +<script type="text/javascript" src="navtree.js"></script> +<script type="text/javascript"> + $(document).ready(initResizable); +</script> +<link href="search/search.css" rel="stylesheet" type="text/css"/> +<script type="text/javascript" src="search/searchdata.js"></script> +<script type="text/javascript" src="search/search.js"></script> +<script type="text/javascript"> + $(document).ready(function() { init_search(); }); +</script> +<!-- hack in the navigation tree --> +<script type="text/javascript" src="eigen_navtree_hacks.js"></script> +<link href="doxygen.css" rel="stylesheet" type="text/css" /> +<link href="madlib_extra.css" rel="stylesheet" type="text/css"/> +<!-- google analytics --> +<script> + (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){ + (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o), + m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m) + })(window,document,'script','//www.google-analytics.com/analytics.js','ga'); + ga('create', 'UA-45382226-1', 'madlib.incubator.apache.org'); + ga('send', 'pageview'); +</script> +</head> +<body> +<div id="top"><!-- do not remove this div, it is closed by doxygen! --> +<div id="titlearea"> +<table cellspacing="0" cellpadding="0"> + <tbody> + <tr style="height: 56px;"> + <td id="projectlogo"><a href="http://madlib.incubator.apache.org";><img alt="Logo" src="madlib.png" height="50" style="padding-left:0.5em;" border="0"/ ></a></td> + <td style="padding-left: 0.5em;"> + <div id="projectname"> + <span id="projectnumber">1.11</span> + </div> + <div id="projectbrief">User Documentation for MADlib</div> + </td> + <td> <div id="MSearchBox" class="MSearchBoxInactive"> + <span class="left"> + <img id="MSearchSelect" src="search/mag_sel.png" + onmouseover="return searchBox.OnSearchSelectShow()" + onmouseout="return searchBox.OnSearchSelectHide()" + alt=""/> + <input type="text" id="MSearchField" value="Search" accesskey="S" + onfocus="searchBox.OnSearchFieldFocus(true)" + onblur="searchBox.OnSearchFieldFocus(false)" + onkeyup="searchBox.OnSearchFieldChange(event)"/> + </span><span class="right"> + <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a> + </span> + </div> +</td> + </tr> + </tbody> +</table> +</div> +<!-- end header part --> +<!-- Generated by Doxygen 1.8.13 --> +<script type="text/javascript"> +var searchBox = new SearchBox("searchBox", "search",false,'Search'); +</script> +</div><!-- top --> +<div id="side-nav" class="ui-resizable side-nav-resizable"> + <div id="nav-tree"> + <div id="nav-tree-contents"> + <div id="nav-sync" class="sync"></div> + </div> + </div> + <div id="splitbar" style="-moz-user-select:none;" + class="ui-resizable-handle"> + </div> +</div> +<script type="text/javascript"> +$(document).ready(function(){initNavTree('group__grp__svd.html','');}); +</script> +<div id="doc-content"> +<!-- window showing the filter options --> +<div id="MSearchSelectWindow" + onmouseover="return searchBox.OnSearchSelectShow()" + onmouseout="return searchBox.OnSearchSelectHide()" + onkeydown="return searchBox.OnSearchSelectKey(event)"> +</div> + +<!-- iframe showing the search results (closed by default) --> +<div id="MSearchResultsWindow"> +<iframe src="javascript:void(0)" frameborder="0" + name="MSearchResults" id="MSearchResults"> +</iframe> +</div> + +<div class="header"> + <div class="headertitle"> +<div class="title">Singular Value Decomposition<div class="ingroups"><a class="el" href="group__grp__datatrans.html">Data Types and Transformations</a> » <a class="el" href="group__grp__arraysmatrix.html">Arrays and Matrices</a> » <a class="el" href="group__grp__matrix__factorization.html">Matrix Factorization</a></div></div> </div> +</div><!--header--> +<div class="contents"> +<div class="toc"><b>Contents</b> <ul> +<li> +<a href="#syntax">SVD Functions</a> </li> +<li> +<a href="#output">Output Tables</a> </li> +<li> +<a href="#examples">Examples</a></li> +<li> +</li> +<li> +<a href="#background">Technical Background</a> </li> +</ul> +</div><p>In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix, with many useful applications in signal processing and statistics.</p> +<p>Let <img class="formulaInl" alt="$A$" src="form_42.png"/> be a <img class="formulaInl" alt="$mxn$" src="form_193.png"/> matrix, where <img class="formulaInl" alt="$m \ge n$" src="form_194.png"/>. Then <img class="formulaInl" alt="$A$" src="form_42.png"/> can be decomposed as follows: </p><p class="formulaDsp"> +<img class="formulaDsp" alt="\[ A = U \Sigma V^T, \]" src="form_195.png"/> +</p> +<p> where <img class="formulaInl" alt="$U$" src="form_51.png"/> is a <img class="formulaInl" alt="$m \times n$" src="form_50.png"/> orthonormal matrix, <img class="formulaInl" alt="$\Sigma$" src="form_196.png"/> is a <img class="formulaInl" alt="$n \times n$" src="form_197.png"/> diagonal matrix, and <img class="formulaInl" alt="$V$" src="form_53.png"/> is an <img class="formulaInl" alt="$n \times n$" src="form_197.png"/> orthonormal matrix. The diagonal elements of <img class="formulaInl" alt="$\Sigma$" src="form_196.png"/> are called the <em>singular values</em>.</p> +<p><a class="anchor" id="syntax"></a></p><dl class="section user"><dt>SVD Functions</dt><dd></dd></dl> +<p>SVD factorizations are provided for dense and sparse matrices. In addition, a native implementation is provided for very sparse matrices for improved performance.</p> +<p><b>SVD Function for Dense Matrices</b></p> +<pre class="syntax"> +svd( source_table, + output_table_prefix, + row_id, + k, + n_iterations, + result_summary_table +); +</pre><p> <b>Arguments</b> </p><dl class="arglist"> +<dt>source_table </dt> +<dd><p class="startdd">TEXT. Source table name (dense matrix).</p> +<p class="enddd">The table contains a <code>row_id</code> column that identifies each row, with numbering starting from 1. The other columns contain the data for the matrix. There are two possible dense formats as illustrated by the 2x2 matrix example below. You can use either of these dense formats:</p><ol type="1"> +<li><pre class="example"> + row_id col1 col2 +row1 1 1 0 +row2 2 0 1 + </pre></li> +<li><pre class="example"> + row_id row_vec +row1 1 {1, 0} +row2 2 {0, 1} + </pre> </li> +</ol> +</dd> +<dt>output_table_prefix </dt> +<dd>TEXT. Prefix for output tables. See <a href="#output">Output Tables</a> below for a description of the convention used. </dd> +<dt>row_id </dt> +<dd>TEXT. ID for each row. </dd> +<dt>k </dt> +<dd>INTEGER. Number of singular values to compute. </dd> +<dt>n_iterations (optional). </dt> +<dd>INTEGER. Number of iterations to run. <dl class="section note"><dt>Note</dt><dd>The number of iterations must be in the range [k, column dimension], where k is number of singular values. </dd></dl> +</dd> +<dt>result_summary_table (optional) </dt> +<dd>TEXT. The name of the table to store the result summary. </dd> +</dl> +<hr/> +<p> <b>SVD Function for Sparse Matrices</b></p> +<p>Use this function for matrices that are represented in the sparse-matrix format (example below). <b>Note that the input matrix is converted to a dense matrix before the SVD operation, for efficient computation reasons. </b></p> +<pre class="syntax"> +svd_sparse( source_table, + output_table_prefix, + row_id, + col_id, + value, + row_dim, + col_dim, + k, + n_iterations, + result_summary_table + ); +</pre><p> <b>Arguments</b> </p><dl class="arglist"> +<dt>source_table </dt> +<dd><p class="startdd">TEXT. Source table name (sparse matrix).</p> +<p>A sparse matrix is represented using the row and column indices for each non-zero entry of the matrix. This representation is useful for matrices containing multiple zero elements. Below is an example of a sparse 4x7 matrix with just 6 out of 28 entries being non-zero. The dimensionality of the matrix is inferred using the max value in <em>row</em> and <em>col</em> columns. Note the last entry is included (even though it is 0) to provide the dimensionality of the matrix, indicating that the 4th row and 7th column contain all zeros. </p><pre class="example"> + row_id | col_id | value +--------+--------+------- + 1 | 1 | 9 + 1 | 5 | 6 + 1 | 6 | 6 + 2 | 1 | 8 + 3 | 1 | 3 + 3 | 2 | 9 + 4 | 7 | 0 +(6 rows) +</pre> <p class="enddd"></p> +</dd> +<dt>output_table_prefix </dt> +<dd>TEXT. Prefix for output tables. See <a href="#output">Output Tables</a> below for a description of the convention used. </dd> +<dt>row_id </dt> +<dd>TEXT. Name of the column containing the row index for each entry in sparse matrix. </dd> +<dt>col_id </dt> +<dd>TEXT. Name of the column containing the column index for each entry in sparse matrix. </dd> +<dt>value </dt> +<dd>TEXT. Name of column containing the non-zero values of the sparse matrix. </dd> +<dt>row_dim </dt> +<dd>INTEGER. Number of rows in matrix. </dd> +<dt>col_dim </dt> +<dd>INTEGER. Number of columns in matrix. </dd> +<dt>k </dt> +<dd>INTEGER. Number of singular values to compute. </dd> +<dt>n_iterations (optional) </dt> +<dd>INTEGER. Number of iterations to run. <dl class="section note"><dt>Note</dt><dd>The number of iterations must be in the range [k, column dimension], where k is number of singular values. </dd></dl> +</dd> +<dt>result_summary_table (optional) </dt> +<dd>TEXT. The name of the table to store the result summary. </dd> +</dl> +<hr/> +<p> <b>Native Implementation for Sparse Matrices</b></p> +<p>Use this function for matrices that are represented in the sparse-matrix format (see sparse matrix example above). This function uses the native sparse representation while computing the SVD. </p><dl class="section note"><dt>Note</dt><dd>Note that this function should be favored if the matrix is highly sparse, since it computes very sparse matrices efficiently. </dd></dl> +<pre class="syntax"> +svd_sparse_native( source_table, + output_table_prefix, + row_id, + col_id, + value, + row_dim, + col_dim, + k, + n_iterations, + result_summary_table + ); +</pre><p> <b>Arguments</b> </p><dl class="arglist"> +<dt>source_table </dt> +<dd>TEXT. Source table name (sparse matrix - see example above). </dd> +<dt>output_table_prefix </dt> +<dd>TEXT. Prefix for output tables. See <a href="#output">Output Tables</a> below for a description of the convention used. </dd> +<dt>row_id </dt> +<dd>TEXT. ID for each row. </dd> +<dt>col_id </dt> +<dd>TEXT. ID for each column. </dd> +<dt>value </dt> +<dd>TEXT. Non-zero values of the sparse matrix. </dd> +<dt>row_dim </dt> +<dd>INTEGER. Row dimension of sparse matrix. </dd> +<dt>col_dim </dt> +<dd>INTEGER. Col dimension of sparse matrix. </dd> +<dt>k </dt> +<dd>INTEGER. Number of singular values to compute. </dd> +<dt>n_iterations (optional) </dt> +<dd>INTEGER. Number of iterations to run. <dl class="section note"><dt>Note</dt><dd>The number of iterations must be in the range [k, column dimension], where k is number of singular values. </dd></dl> +</dd> +<dt>result_summary_table (optional) </dt> +<dd>TEXT. Table name to store result summary. </dd> +</dl> +<hr/> +<p><a class="anchor" id="output"></a></p><dl class="section user"><dt>Output Tables</dt><dd></dd></dl> +<p>Output for eigenvectors/values is in the following three tables:</p><ul> +<li>Left singular matrix: Table is named <output_table_prefix>_u (e.g. ânetflix_uâ)</li> +<li>Right singular matrix: Table is named <output_table_prefix>_v (e.g. ânetflix_vâ)</li> +<li>Singular values: Table is named <output_table_prefix>_s (e.g. ânetflix_sâ)</li> +</ul> +<p>The left and right singular vector tables are of the format: </p><table class="output"> +<tr> +<th>row_id </th><td>INTEGER. The ID corresponding to each eigenvalue (in decreasing order). </td></tr> +<tr> +<th>row_vec </th><td>FLOAT8[]. Singular vector elements for this row_id. Each array is of size k. </td></tr> +</table> +<p>The singular values table is in sparse table format, since only the diagonal elements of the matrix are non-zero: </p><table class="output"> +<tr> +<th>row_id </th><td>INTEGER. <em>i</em> for <em>ith</em> eigenvalue. </td></tr> +<tr> +<th>col_id </th><td>INTEGER. <em>i</em> for <em>ith</em> eigenvalue (same as row_id). </td></tr> +<tr> +<th>value </th><td>FLOAT8. Eigenvalue. </td></tr> +</table> +<p>All <code>row_id</code> and <code>col_id</code> in the above tables start from 1.</p> +<p>The result summary table has the following columns: </p><table class="output"> +<tr> +<th>rows_used </th><td>INTEGER. Number of rows used for SVD calculation. </td></tr> +<tr> +<th>exec_time </th><td>FLOAT8. Total time for executing SVD. </td></tr> +<tr> +<th>iter </th><td>INTEGER. Total number of iterations run. </td></tr> +<tr> +<th>recon_error </th><td>FLOAT8. Total quality score (i.e. approximation quality) for this set of orthonormal basis. </td></tr> +<tr> +<th>relative_recon_error </th><td>FLOAT8. Relative quality score. </td></tr> +</table> +<p>In the result summary table, the reconstruction error is computed as <img class="formulaInl" alt="$ \sqrt{mean((X - USV^T)_{ij}^2)} $" src="form_198.png"/>, where the average is over all elements of the matrices. The relative reconstruction error is then computed as ratio of the reconstruction error and <img class="formulaInl" alt="$ \sqrt{mean(X_{ij}^2)} $" src="form_199.png"/>.</p> +<p><a class="anchor" id="examples"></a></p><dl class="section user"><dt>Examples</dt><dd></dd></dl> +<ol type="1"> +<li>View online help for the SVD function. <pre class="example"> +SELECT madlib.svd(); +</pre></li> +<li>Create an input dataset (dense matrix). <pre class="example"> +DROP TABLE IF EXISTS mat, mat_sparse, svd_summary_table, svd_u, svd_v, svd_s; +CREATE TABLE mat ( + row_id integer, + row_vec double precision[] +); +INSERT INTO mat VALUES +(1,'{396,840,353,446,318,886,15,584,159,383}'), +(2,'{691,58,899,163,159,533,604,582,269,390}'), +(3,'{293,742,298,75,404,857,941,662,846,2}'), +(4,'{462,532,787,265,982,306,600,608,212,885}'), +(5,'{304,151,337,387,643,753,603,531,459,652}'), +(6,'{327,946,368,943,7,516,272,24,591,204}'), +(7,'{877,59,260,302,891,498,710,286,864,675}'), +(8,'{458,959,774,376,228,354,300,669,718,565}'), +(9,'{824,390,818,844,180,943,424,520,65,913}'), +(10,'{882,761,398,688,761,405,125,484,222,873}'), +(11,'{528,1,860,18,814,242,314,965,935,809}'), +(12,'{492,220,576,289,321,261,173,1,44,241}'), +(13,'{415,701,221,503,67,393,479,218,219,916}'), +(14,'{350,192,211,633,53,783,30,444,176,932}'), +(15,'{909,472,871,695,930,455,398,893,693,838}'), +(16,'{739,651,678,577,273,935,661,47,373,618}'); +</pre></li> +<li>Run SVD function for a dense matrix. <pre class="example"> +SELECT madlib.svd( 'mat', -- Input table + 'svd', -- Output table prefix + 'row_id', -- Column name with row index + 10, -- Number of singular values to compute + NULL, -- Use default number of iterations + 'svd_summary_table' -- Result summary table + ); +</pre></li> +<li>Print out the singular values and the summary table. For the singular values: <pre class="example"> +SELECT * FROM svd_s ORDER BY row_id; +</pre> Result: <pre class="result"> + row_id | col_id | value + --------+--------+------------------ + 1 | 1 | 6475.67225281804 + 2 | 2 | 1875.18065580415 + 3 | 3 | 1483.25228429636 + 4 | 4 | 1159.72262897427 + 5 | 5 | 1033.86092570574 + 6 | 6 | 948.437358703966 + 7 | 7 | 795.379572772455 + 8 | 8 | 709.086240684469 + 9 | 9 | 462.473775959371 + 10 | 10 | 365.875217945698 + 10 | 10 | +(11 rows) +</pre> For the summary table: <pre class="example"> +SELECT * FROM svd_summary_table; +</pre> Result: <pre class="result"> + rows_used | exec_time (ms) | iter | recon_error | relative_recon_error + -----------+----------------+------+-------------------+---------------------- + 16 | 1332.47 | 10 | 4.36920148766e-13 | 7.63134130332e-16 +(1 row) +</pre></li> +<li>Create a sparse matrix by running the <a class="el" href="matrix__ops_8sql__in.html#a390fb7234f49e17c780e961184873759">matrix_sparsify()</a> utility function on the dense matrix. <pre class="example"> +SELECT madlib.matrix_sparsify('mat', + 'row=row_id, val=row_vec', + 'mat_sparse', + 'row=row_id, col=col_id, val=value'); +</pre></li> +<li>Run the SVD function for a sparse matrix. <pre class="example"> +SELECT madlib.svd_sparse( 'mat_sparse', -- Input table + 'svd', -- Output table prefix + 'row_id', -- Column name with row index + 'col_id', -- Column name with column index + 'value', -- Matrix cell value + 16, -- Number of rows in matrix + 10, -- Number of columns in matrix + 10 -- Number of singular values to compute + ); +</pre></li> +<li>Run the SVD function for a very sparse matrix. <pre class="example"> +SELECT madlib.svd_sparse_native ( 'mat_sparse', -- Input table + 'svd', -- Output table prefix + 'row_id', -- Column name with row index + 'col_id', -- Column name with column index + 'value', -- Matrix cell value + 16, -- Number of rows in matrix + 10, -- Number of columns in matrix + 10 -- Number of singular values to compute + ); +</pre> <a class="anchor" id="background"></a><dl class="section user"><dt>Technical Background</dt><dd>In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix, with many useful applications in signal processing and statistics. Let <img class="formulaInl" alt="$A$" src="form_42.png"/> be a <img class="formulaInl" alt="$m \times n$" src="form_50.png"/> matrix, where <img class="formulaInl" alt="$m \ge n$" src="form_194.png"/>. Then <img class="formulaInl" alt="$A$" src="form_42.png"/> can be decomposed as follows: <p class="formulaDsp"> +<img class="formulaDsp" alt="\[ A = U \Sigma V^T, \]" src="form_195.png"/> +</p> + where <img class="formulaInl" alt="$U$" src="form_51.png"/> is a <img class="formulaInl" alt="$m \times n$" src="form_50.png"/> orthonormal matrix, <img class="formulaInl" alt="$\Sigma$" src="form_196.png"/> is a <img class="formulaInl" alt="$n \times n$" src="form_197.png"/> diagonal matrix, and <img class="formulaInl" alt="$V$" src="form_53.png"/> is an <img class="formulaInl" alt="$n \times n$" src="form_197.png"/> orthonormal matrix. The diagonal elements of <img class="formulaInl" alt="$\Sigma$" src="form_196.png"/> are called the <em>singular values</em>. It is possible to formulate the problem of computing the singular triplets ( <img class="formulaInl" alt="$\sigma_i, u_i, v_i$" src="form_200.png"/>) of <img class="formulaInl" alt="$A$" src="form_42.png"/> as an eigenvalue problem involving a Hermitian matrix related to <img class="formulaInl" alt="$A$" src="form_42.png"/>. There are two possible ways of achieving this:</dd></dl> +</li> +</ol> +<ul> +<li>With the cross product matrix, <img class="formulaInl" alt="$A^TA$" src="form_201.png"/> and <img class="formulaInl" alt="$AA^T$" src="form_202.png"/></li> +<li>With the cyclic matrix <p class="formulaDsp"> +<img class="formulaDsp" alt="\[ H(A) = \begin{bmatrix} 0 & A\\ A^* & 0 \end{bmatrix} \]" src="form_203.png"/> +</p> + The singular values are the nonnegative square roots of the eigenvalues of the cross product matrix. This approach may imply a severe loss of accuracy in the smallest singular values. The cyclic matrix approach is an alternative that avoids this problem, but at the expense of significantly increasing the cost of the computation. Computing the cross product matrix explicitly is not recommended, especially in the case of sparse A. Bidiagonalization was proposed by Golub and Kahan [citation?] as a way of tridiagonalizing the cross product matrix without forming it explicitly. Consider the following decomposition <p class="formulaDsp"> +<img class="formulaDsp" alt="\[ A = P B Q^T, \]" src="form_204.png"/> +</p> + where <img class="formulaInl" alt="$P$" src="form_205.png"/> and <img class="formulaInl" alt="$Q$" src="form_206.png"/> are unitary matrices and <img class="formulaInl" alt="$B$" src="form_207.png"/> is an <img class="formulaInl" alt="$m \times n$" src="form_50.png"/> upper bidiagonal matrix. Then the tridiagonal matrix <img class="formulaInl" alt="$B*B$" src="form_208.png"/> is unitarily similar to <img class="formulaInl" alt="$A*A$" src="form_209.png"/>. Additionally, specific methods exist that compute the singular values of <img class="formulaInl" alt="$B$" src="form_207.png"/> without forming <img class="formulaInl" alt="$B*B$" src="form_208.png"/>. Therefore, after computing the SVD of B, <p class="formulaDsp"> +<img class="formulaDsp" alt="\[ B = X\Sigma Y^T, \]" src="form_210.png"/> +</p> + it only remains to compute the SVD of the original matrix with <img class="formulaInl" alt="$U = PX$" src="form_211.png"/> and <img class="formulaInl" alt="$V = QY$" src="form_212.png"/>. </li> +</ul> +</div><!-- contents --> +</div><!-- doc-content --> +<!-- start footer part --> +<div id="nav-path" class="navpath"><!-- id is needed for treeview function! --> + <ul> + <li class="footer">Generated on Tue May 16 2017 13:24:38 for MADlib by + <a href="http://www.doxygen.org/index.html";> + <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.13 </li> + </ul> +</div> +</body> +</html>
http://git-wip-us.apache.org/repos/asf/incubator-madlib-site/blob/b5b51c69/docs/v1.11/group__grp__svec.html ---------------------------------------------------------------------- diff --git a/docs/v1.11/group__grp__svec.html b/docs/v1.11/group__grp__svec.html new file mode 100644 index 0000000..50a6bc1 --- /dev/null +++ b/docs/v1.11/group__grp__svec.html @@ -0,0 +1,442 @@ +<!-- HTML header for doxygen 1.8.4--> +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd";> +<html xmlns="http://www.w3.org/1999/xhtml";> +<head> +<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/> +<meta http-equiv="X-UA-Compatible" content="IE=9"/> +<meta name="generator" content="Doxygen 1.8.13"/> +<meta name="keywords" content="madlib,postgres,greenplum,machine learning,data mining,deep learning,ensemble methods,data science,market basket analysis,affinity analysis,pca,lda,regression,elastic net,huber white,proportional hazards,k-means,latent dirichlet allocation,bayes,support vector machines,svm"/> +<title>MADlib: Sparse Vectors</title> +<link href="tabs.css" rel="stylesheet" type="text/css"/> +<script type="text/javascript" src="jquery.js"></script> +<script type="text/javascript" src="dynsections.js"></script> +<link href="navtree.css" rel="stylesheet" type="text/css"/> +<script type="text/javascript" src="resize.js"></script> +<script type="text/javascript" src="navtreedata.js"></script> +<script type="text/javascript" src="navtree.js"></script> +<script type="text/javascript"> + $(document).ready(initResizable); +</script> +<link href="search/search.css" rel="stylesheet" type="text/css"/> +<script type="text/javascript" src="search/searchdata.js"></script> +<script type="text/javascript" src="search/search.js"></script> +<script type="text/javascript"> + $(document).ready(function() { init_search(); }); +</script> +<!-- hack in the navigation tree --> +<script type="text/javascript" src="eigen_navtree_hacks.js"></script> +<link href="doxygen.css" rel="stylesheet" type="text/css" /> +<link href="madlib_extra.css" rel="stylesheet" type="text/css"/> +<!-- google analytics --> +<script> + (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){ + (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o), + m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m) + })(window,document,'script','//www.google-analytics.com/analytics.js','ga'); + ga('create', 'UA-45382226-1', 'madlib.incubator.apache.org'); + ga('send', 'pageview'); +</script> +</head> +<body> +<div id="top"><!-- do not remove this div, it is closed by doxygen! --> +<div id="titlearea"> +<table cellspacing="0" cellpadding="0"> + <tbody> + <tr style="height: 56px;"> + <td id="projectlogo"><a href="http://madlib.incubator.apache.org";><img alt="Logo" src="madlib.png" height="50" style="padding-left:0.5em;" border="0"/ ></a></td> + <td style="padding-left: 0.5em;"> + <div id="projectname"> + <span id="projectnumber">1.11</span> + </div> + <div id="projectbrief">User Documentation for MADlib</div> + </td> + <td> <div id="MSearchBox" class="MSearchBoxInactive"> + <span class="left"> + <img id="MSearchSelect" src="search/mag_sel.png" + onmouseover="return searchBox.OnSearchSelectShow()" + onmouseout="return searchBox.OnSearchSelectHide()" + alt=""/> + <input type="text" id="MSearchField" value="Search" accesskey="S" + onfocus="searchBox.OnSearchFieldFocus(true)" + onblur="searchBox.OnSearchFieldFocus(false)" + onkeyup="searchBox.OnSearchFieldChange(event)"/> + </span><span class="right"> + <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a> + </span> + </div> +</td> + </tr> + </tbody> +</table> +</div> +<!-- end header part --> +<!-- Generated by Doxygen 1.8.13 --> +<script type="text/javascript"> +var searchBox = new SearchBox("searchBox", "search",false,'Search'); +</script> +</div><!-- top --> +<div id="side-nav" class="ui-resizable side-nav-resizable"> + <div id="nav-tree"> + <div id="nav-tree-contents"> + <div id="nav-sync" class="sync"></div> + </div> + </div> + <div id="splitbar" style="-moz-user-select:none;" + class="ui-resizable-handle"> + </div> +</div> +<script type="text/javascript"> +$(document).ready(function(){initNavTree('group__grp__svec.html','');}); +</script> +<div id="doc-content"> +<!-- window showing the filter options --> +<div id="MSearchSelectWindow" + onmouseover="return searchBox.OnSearchSelectShow()" + onmouseout="return searchBox.OnSearchSelectHide()" + onkeydown="return searchBox.OnSearchSelectKey(event)"> +</div> + +<!-- iframe showing the search results (closed by default) --> +<div id="MSearchResultsWindow"> +<iframe src="javascript:void(0)" frameborder="0" + name="MSearchResults" id="MSearchResults"> +</iframe> +</div> + +<div class="header"> + <div class="headertitle"> +<div class="title">Sparse Vectors<div class="ingroups"><a class="el" href="group__grp__datatrans.html">Data Types and Transformations</a> » <a class="el" href="group__grp__arraysmatrix.html">Arrays and Matrices</a></div></div> </div> +</div><!--header--> +<div class="contents"> +<div class="toc"><b>Contents</b> <ul> +<li> +<a href="#usage">Using Sparse Vectors</a> </li> +<li> +<a href="#vectorization">Document Vectorization into Sparse Vectors</a> </li> +<li> +<a href="#examples">Examples</a> </li> +<li> +<a href="#related">Related Topics</a> </li> +</ul> +</div><p>This module implements a sparse vector data type, named "svec", which provides compressed storage of vectors that have many duplicate elements.</p> +<p>Arrays of floating point numbers for various calculations sometimes have long runs of zeros (or some other default value). This is common in applications like scientific computing, retail optimization, and text processing. Each floating point number takes 8 bytes of storage in memory and/or disk, so saving those zeros is often worthwhile. There are also many computations that can benefit from skipping over the zeros.</p> +<p>Consider, for example, the following array of doubles stored as a Postgres/Greenplum "float8[]" data type:</p> +<pre class="example"> +'{0, 33,...40,000 zeros..., 12, 22 }'::float8[] +</pre><p>This array would occupy slightly more than 320KB of memory or disk, most of it zeros. Even if we were to exploit the null bitmap and store the zeros as nulls, we would still end up with a 5KB null bitmap, which is still not nearly as memory efficient as we'd like. Also, as we perform various operations on the array, we do work on 40,000 fields that turn out to be unimportant.</p> +<p>To solve the problems associated with the processing of vectors discussed above, the svec type employs a simple Run Length Encoding (RLE) scheme to represent sparse vectors as pairs of count-value arrays. For example, the array above would be represented as</p> +<pre class="example"> +'{1,1,40000,1,1}:{0,33,0,12,22}'::madlib.svec +</pre><p>which says there is 1 occurrence of 0, followed by 1 occurrence of 33, followed by 40,000 occurrences of 0, etc. This uses just 5 integers and 5 floating point numbers to store the array. Further, it is easy to implement vector operations that can take advantage of the RLE representation to make computations faster. The SVEC module provides a library of such functions.</p> +<p>The current version only supports sparse vectors of float8 values. Future versions will support other base types.</p> +<p><a class="anchor" id="usage"></a></p><dl class="section user"><dt>Using Sparse Vectors</dt><dd></dd></dl> +<p>An SVEC can be constructed directly with a constant expression, as follows: </p><pre class="example"> +SELECT '{n1,n2,...,nk}:{v1,v2,...vk}'::madlib.svec; +</pre><p> where <code>n1,n2,...,nk</code> specifies the counts for the values <code>v1,v2,...,vk</code>.</p> +<p>A float array can be cast to an SVEC: </p><pre class="example"> +SELECT ('{v1,v2,...vk}'::float[])::madlib.svec; +</pre><p>An SVEC can be created with an aggregation: </p><pre class="example"> +SELECT madlib.svec_agg(v1) FROM generate_series(1,k); +</pre><p>An SVEC can be created using the <code>madlib.svec_cast_positions_float8arr()</code> function by supplying an array of positions and an array of values at those positions: </p><pre class="example"> +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) -- value at unspecified positions +</pre><p> For example, the following expression: </p><pre class="example"> +SELECT madlib.svec_cast_positions_float8arr( + array[1,3,5], + array[2,4,6], + 10, + 0.0) +</pre><p> produces this SVEC: </p><pre class="result"> + svec_cast_positions_float8arr +  ------------------------------ + {1,1,1,1,1,5}:{2,0,4,0,6,0} +</pre><p>Add madlib to the search_path to use the svec operators defined in the module.</p> +<p><a class="anchor" id="vectorization"></a></p><dl class="section user"><dt>Document Vectorization into Sparse Vectors</dt><dd>This module implements an efficient way for document vectorization, converting text documents into sparse vector representation (MADlib.svec), required by various machine learning algorithms in MADlib.</dd></dl> +<p>The function accepts two tables as input, dictionary table and documents table, and produces the specified output table containing sparse vectors for the represented documents (in documents table).</p> +<pre class="syntax"> +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 + ) +</pre><p> <b>Arguments</b> </p><dl class="arglist"> +<dt>output_tbl </dt> +<dd><p class="startdd">TEXT. Name of the output table to be created containing the sparse vector representation of the documents. It has the following columns: </p><table class="output"> +<tr> +<th>doc_id </th><td>__TYPE_DOC__. Document id. <br /> + __TYPE_DOC__: Column type depends on the type of <code>doc_id_col</code> in <code>documents_tbl</code>. </td></tr> +<tr> +<th>sparse_vector </th><td>MADlib.svec. Corresponding sparse vector representation. </td></tr> +</table> +<p class="enddd"></p> +</dd> +<dt>dictionary_tbl </dt> +<dd><p class="startdd">TEXT. Name of the dictionary table containing features. </p><table class="output"> +<tr> +<th>dict_id_col </th><td>TEXT. Name of the id column in the <code>dictionary_tbl</code>. <br /> + Expected Type: INTEGER or BIGINT. <br /> + NOTE: Values must be continuous ranging from 0 to total number of elements in the dictionary - 1. </td></tr> +<tr> +<th>dict_term_col </th><td>TEXT. Name of the column containing term (features) in <code>dictionary_tbl</code>. </td></tr> +</table> +<p class="enddd"></p> +</dd> +<dt>documents_tbl </dt> +<dd>TEXT. Name of the documents table representing documents. <table class="output"> +<tr> +<th>doc_id_col </th><td>TEXT. Name of the id column in the <code>documents_tbl</code>. </td></tr> +<tr> +<th>doc_term_col </th><td>TEXT. Name of the term column in the <code>documents_tbl</code>. </td></tr> +<tr> +<th>doc_term_info_col </th><td>TEXT. Name of the term info column in <code>documents_tbl</code>. The expected type of this column should be: <br /> + - INTEGER, BIGINT or DOUBLE PRECISION: Values directly used to populate vector. <br /> + - ARRAY: Length of the array used to populate the vector. <br /> + ** For an example use case on using these types of column types, please refer to the example below. </td></tr> +</table> +</dd> +</dl> +<p><b>Example:</b> <br /> + Consider a corpus consisting of set of documents consisting of features (terms) along with doc ids: </p><pre class="example"> +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} +</pre><ol type="1"> +<li>Prepare documents table in appropriate format. <br /> + The corpus specified above can be represented by any of the following <code>documents_table:</code> <pre class="example"> +SELECT * FROM documents_table ORDER BY id; +</pre> Result: <pre class="result"> + 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} +... +</pre></li> +<li>Prepare dictionary table in appropriate format. <pre class="example"> +SELECT * FROM dictionary_table ORDER BY id; +</pre> Result: <pre class="result"> + id | term + ----+---------- + 0 | am + 1 | before + 2 | being + 3 | bothered + 4 | corpus + 5 | document + 6 | i + 7 | in + 8 | is + 9 | me +... +</pre></li> +<li>Generate sparse vector for the documents using dictionary_table and documents_table. <br /> + <code>doc_term_info_col</code> <code></code>(count) of type INTEGER: <pre class="example"> +SELECT * FROM madlib.gen_doc_svecs('svec_output', 'dictionary_table', 'id', 'term', + 'documents_table', 'id', 'term', 'count'); +</pre> <code>doc_term_info_col</code> <code></code>(positions) of type ARRAY: <pre class="example"> +SELECT * FROM madlib.gen_doc_svecs('svec_output', 'dictionary_table', 'id', 'term', + 'documents_table', 'id', 'term', 'positions'); +</pre> Result: <pre class="result"> + gen_doc_svecs + -------------------------------------------------------------------------------------- + Created table svec_output (doc_id, sparse_vector) containing sparse vectors +(1 row) +</pre></li> +<li>Analyze the sparse vectors created. <pre class="example"> +SELECT * FROM svec_output ORDER by doc_id; +</pre> Result: <pre class="result"> + 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) +</pre></li> +</ol> +<p>See the file <a class="el" href="svec_8sql__in.html" title="SQL type definitions and functions for sparse vector data type svec ">svec.sql_in</a> for complete syntax.</p> +<p><a class="anchor" id="examples"></a></p><dl class="section user"><dt>Examples</dt><dd></dd></dl> +<p>We can use operations with svec type like <, >, *, **, /, =, +, SUM, etc, and they have meanings associated with typical vector operations. For example, the plus (+) operator adds each of the terms of two vectors having the same dimension together. </p><pre class="example"> +SELECT ('{0,1,5}'::float8[]::madlib.svec + '{4,3,2}'::float8[]::madlib.svec)::float8[]; +</pre><p> Result: </p><pre class="result"> + float8 + -------- + {4,4,7} +</pre><p>Without the casting into float8[] at the end, we get: </p><pre class="example"> +SELECT '{0,1,5}'::float8[]::madlib.svec + '{4,3,2}'::float8[]::madlib.svec; +</pre><p> Result: </p><pre class="result"> + ?column? + --------- +{2,1}:{4,7} +</pre><p>A dot product (%*%) between the two vectors will result in a scalar result of type float8. The dot product should be (0*4 + 1*3 + 5*2) = 13, like this: </p><pre class="example"> +SELECT '{0,1,5}'::float8[]::madlib.svec %*% '{4,3,2}'::float8[]::madlib.svec; +</pre> <pre class="result"> + ?column? + --------- + 13 +</pre><p>Special vector aggregate functions are also available. SUM is self explanatory. SVEC_COUNT_NONZERO evaluates the count of non-zero terms in each column found in a set of n-dimensional svecs and returns an svec with the counts. For instance, if we have the vectors {0,1,5}, {10,0,3},{0,0,3},{0,1,0}, then executing the SVEC_COUNT_NONZERO() aggregate function would result in {1,2,3}:</p> +<pre class="example"> +CREATE TABLE list (a madlib.svec); +INSERT INTO list VALUES ('{0,1,5}'::float8[]), ('{10,0,3}'::float8[]), ('{0,0,3}'::float8[]),('{0,1,0}'::float8[]); +SELECT madlib.svec_count_nonzero(a)::float8[] FROM list; +</pre><p> Result: </p><pre class="result"> +svec_count_nonzero + ---------------- + {1,2,3} +</pre><p>We do not use null bitmaps in the svec data type. A null value in an svec is represented explicitly as an NVP (No Value Present) value. For example, we have: </p><pre class="example"> +SELECT '{1,2,3}:{4,null,5}'::madlib.svec; +</pre><p> Result: </p><pre class="result"> + svec + ------------------ + {1,2,3}:{4,NVP,5} +</pre><p>Adding svecs with null values results in NVPs in the sum: </p><pre class="example"> +SELECT '{1,2,3}:{4,null,5}'::madlib.svec + '{2,2,2}:{8,9,10}'::madlib.svec; +</pre><p> Result: </p><pre class="result"> + ?column? +  ------------------------- + {1,2,1,2}:{12,NVP,14,15} +</pre><p>An element of an svec can be accessed using the <a class="el" href="svec__util_8sql__in.html#a8787222aec691f94d9808d1369aa401c">svec_proj()</a> function, which takes an svec and the index of the element desired. </p><pre class="example"> +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); +</pre><p> Result: </p><pre class="result"> ?column? + --------- + 7 +</pre><p>A subvector of an svec can be accessed using the <a class="el" href="svec__util_8sql__in.html#a5cb3446de5fc117befe88ccb1ebb0e4e">svec_subvec()</a> function, which takes an svec and the start and end index of the subvector desired. </p><pre class="example"> +SELECT madlib.svec_subvec('{2,4,6}:{1,3,5}'::madlib.svec, 2, 11); +</pre><p> Result: </p><pre class="result"> svec_subvec + ---------------- + {1,4,5}:{1,3,5} +</pre><p>The elements/subvector of an svec can be changed using the function <a class="el" href="svec__util_8sql__in.html#a59407764a1cbf1937da39cf39a2f447c">svec_change()</a>. It takes three arguments: an m-dimensional svec sv1, a start index j, and an n-dimensional svec sv2 such that j + n - 1 <= m, and returns an svec like sv1 but with the subvector sv1[j:j+n-1] replaced by sv2. An example follows: </p><pre class="example"> +SELECT madlib.svec_change('{1,2,3}:{4,5,6}'::madlib.svec,3,'{2}:{3}'::madlib.svec); +</pre><p> Result: </p><pre class="result"> svec_change + -------------------- + {1,1,2,2}:{4,5,3,6} +</pre><p>There are also higher-order functions for processing svecs. For example, the following is the corresponding function for lapply() in R. </p><pre class="example"> +SELECT madlib.svec_lapply('sqrt', '{1,2,3}:{4,5,6}'::madlib.svec); +</pre><p> Result: </p><pre class="result"> + svec_lapply + ---------------------------------------------- + {1,2,3}:{2,2.23606797749979,2.44948974278318} +</pre><p>The full list of functions available for operating on svecs are available in svec.sql-in.</p> +<p><b> A More Extensive Example</b></p> +<p>For a text classification example, let's assume we have a dictionary composed of words in a sorted text array: </p><pre class="example"> +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}'); +</pre><p> We have a set of documents, each represented as an array of words: </p><pre class="example"> +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}'); +</pre><p>Now we have a dictionary and some documents, we would like to do some document categorization using vector arithmetic on word counts and proportions of dictionary words in each document.</p> +<p>To start this process, we'll need to find the dictionary words in each document. We'll prepare what is called a Sparse Feature Vector or SFV for each document. An SFV is a vector of dimension N, where N is the number of dictionary words, and in each cell of an SFV is a count of each dictionary word in the document.</p> +<p>Inside the sparse vector library, we have a function that will create an SFV from a document, so we can just do this (For a more efficient way for converting documents into sparse vectors, especially for larger datasets, please refer to <a href="#vectorization">Document Vectorization into Sparse Vectors</a>):</p> +<pre class="example"> +SELECT madlib.svec_sfv((SELECT a FROM features LIMIT 1),b)::float8[] + FROM documents; +</pre><p> Result: </p><pre class="result"> + svec_sfv + ---------------------------------------- + {0,0,0,0,1,1,0,1,1,0,0,0,1,0,0,1,0,1,0} + {0,0,1,1,0,0,0,0,0,1,1,1,0,1,0,0,1,0,1} + {1,0,0,0,1,1,1,1,0,0,0,0,0,0,1,2,0,0,0} + {0,1,0,0,0,2,0,0,1,1,0,0,0,0,0,2,1,0,0} +</pre><p>Note that the output of madlib.svec_sfv() is an svec for each document containing the count of each of the dictionary words in the ordinal positions of the dictionary. This can more easily be understood by lining up the feature vector and text like this:</p> +<pre class="example"> +SELECT madlib.svec_sfv((SELECT a FROM features LIMIT 1),b)::float8[] + , b + FROM documents; +</pre><p> Result: </p><pre class="result"> + svec_sfv | b + ----------------------------------------+-------------------------------------------------- + {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,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} + {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} + {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} +</pre> <pre class="example"> +SELECT * FROM features; +</pre> <pre class="result"> + a + ------------------------------------------------------------------------------------------------------- +{am,before,being,bothered,corpus,document,i,in,is,me,never,now,one,really,second,the,third,this,until} +</pre><p>Now when we look at the document "i am the second document in the corpus", its SFV is {1,3*0,1,1,1,1,6*0,1,2}. The word "am" is the first ordinate in the dictionary and there is 1 instance of it in the SFV. The word "before" has no instances in the document, so its value is "0" and so on.</p> +<p>The function madlib.svec_sfv() can process large numbers of documents into their SFVs in parallel at high speed.</p> +<p>The rest of the categorization process is all vector math. The actual count is hardly ever used. Instead, it's turned into a weight. The most common weight is called tf/idf for Term Frequency / Inverse Document Frequency. The calculation for a given term in a given document is</p> +<pre class="example"> +{#Times in document} * log {#Documents / #Documents the term appears in}. +</pre><p>For instance, the term "document" in document A would have weight 1 * log (4/3). In document D, it would have weight 2 * log (4/3). Terms that appear in every document would have tf/idf weight 0, since log (4/4) = log(1) = 0. (Our example has no term like that.) That usually sends a lot of values to 0.</p> +<p>For this part of the processing, we'll need to have a sparse vector of the dictionary dimension (19) with the values </p><pre class="example"> +log(#documents/#Documents each term appears in). +</pre><p> There will be one such vector for the whole list of documents (aka the "corpus"). The #documents is just a count of all of the documents, in this case 4, but there is one divisor for each dictionary word and its value is the count of all the times that word appears in the document. This single vector for the whole corpus can then be scalar product multiplied by each document SFV to produce the Term Frequency/Inverse Document Frequency weights.</p> +<p>This can be done as follows: </p><pre class="example"> +CREATE TABLE corpus AS + (SELECT a, madlib.svec_sfv((SELECT a FROM features LIMIT 1),b) sfv + FROM documents); +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 BYdocnum); +SELECT * FROM weights; +</pre><p> Result </p><pre class="result"> +docnum | tf_idf + ------+---------------------------------------------------------------------- + 1 | {4,1,1,1,2,3,1,2,1,1,1,1}:{0,0.69,0.28,0,0.69,0,1.38,0,0.28,0,1.38,0} + 2 | {1,3,1,1,1,1,6,1,1,3}:{1.38,0,0.69,0.28,1.38,0.69,0,1.38,0.57,0} + 3 | {2,2,5,1,2,1,1,2,1,1,1}:{0,1.38,0,0.69,1.38,0,1.38,0,0.69,0,1.38} + 4 | {1,1,3,1,2,2,5,1,1,2}:{0,1.38,0,0.57,0,0.69,0,0.57,0.69,0} +</pre><p>We can now get the "angular distance" between one document and the rest of the documents using the ACOS of the dot product of the document vectors: The following calculates the angular distance between the first document and each of the other documents: </p><pre class="example"> +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; +</pre><p> Result: </p><pre class="result"> +docnum | angular_distance + -------+------------------ + 1 | 0 + 2 | 78.8235846096986 + 3 | 89.9999999882484 + 4 | 80.0232034288617 +</pre><p>We can see that the angular distance between document 1 and itself is 0 degrees and between document 1 and 3 is 90 degrees because they share no features at all. The angular distance can now be plugged into machine learning algorithms that rely on a distance measure between data points.</p> +<p>SVEC also provides functionality for declaring array given an array of positions and array of values, intermediate values betweens those are declared to be base value that user provides in the same function call. In the example below the fist array of integers represents the positions for the array two (array of floats). Positions do not need to come in the sorted order. Third value represents desired maximum size of the array. This assures that array is of that size even if last position is not. If max size < 1 that value is ignored and array will end at the last position in the position vector. Final value is a float representing the base value to be used between the declared ones (0 would be a common candidate):</p> +<pre class="example"> +SELECT madlib.svec_cast_positions_float8arr(ARRAY[1,2,7,5,87],ARRAY[.1,.2,.7,.5,.87],90,0.0); +</pre><p> Result: </p><pre class="result"> + 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) +</pre><p><a class="anchor" id="related"></a></p><dl class="section user"><dt>Related Topics</dt><dd></dd></dl> +<p>Other examples of svecs usage can be found in the k-means module, <a class="el" href="group__grp__kmeans.html">k-Means Clustering</a>.</p> +<p>File <a class="el" href="svec_8sql__in.html" title="SQL type definitions and functions for sparse vector data type svec ">svec.sql_in</a> documenting the SQL functions.</p> +</div><!-- contents --> +</div><!-- doc-content --> +<!-- start footer part --> +<div id="nav-path" class="navpath"><!-- id is needed for treeview function! --> + <ul> + <li class="footer">Generated on Tue May 16 2017 13:24:38 for MADlib by + <a href="http://www.doxygen.org/index.html";> + <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.13 </li> + </ul> +</div> +</body> +</html>
