<!-- 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.10"/>
<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: Principal Component Analysis</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);
  $(window).load(resizeHeight);
</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.net');
  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.net"><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.9.1</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.10 -->
<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__pca__train.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">Principal Component Analysis<div class="ingroups"><a class="el" href="group__grp__datatrans.html">Data Types and Transformations</a> &raquo; <a class="el" href="group__grp__pca.html">Dimensionality Reduction</a></div></div>  </div>
</div><!--header-->
<div class="contents">
<div class="toc"><b>Contents</b> </p><ul>
<li class="level1">
<a href="#train">Training Function</a> </li>
<li class="level1">
<a href="#examples">Examples</a> </li>
<li class="level1">
<a href="#notes">Notes</a> </li>
<li class="level1">
<a href="#background_pca">Technical Background</a> </li>
<li class="level1">
<a href="#literature">Literature</a> </li>
<li class="level1">
<a href="#related">Related Topics</a> </li>
</ul>
</div><p>Principal component analysis (PCA) is a mathematical procedure that uses an orthogonal transformation to convert a set of observations of possibly correlated variables into a set of values of linearly uncorrelated variables called principal components. This transformation is defined in such a way that the first principal component has the largest possible variance (i.e., accounts for as much of the variability in the data as possible), and each succeeding component in turn has the highest variance possible under the constraint that it be orthogonal to (i.e., uncorrelated with) the preceding components.</p>
<p>See the <a class="el" href="group__grp__pca__train.html#background_pca">Technical Background</a> for an introduction to principal component analysis and the implementation notes.</p>
<p><a class="anchor" id="train"></a></p><dl class="section user"><dt>Training Function</dt><dd>The training functions have the following formats: <pre class="syntax">
pca_train( source_table,
           out_table,
           row_id,
           components_param,
           grouping_cols,
           lanczos_iter,
           use_correlation,
           result_summary_table
         )
</pre> and <pre class="syntax">
pca_sparse_train( source_table,
                  out_table,
                  row_id,
                  col_id,
                  val_id,
                  row_dim,
                  col_dim,
                  components_param,
                  grouping_cols,
                  lanczos_iter,
                  use_correlation,
                  result_summary_table
                )
</pre></dd></dl>
<p><b>Arguments</b> </p><dl class="arglist">
<dt>source_table </dt>
<dd><p class="startdd">TEXT. Name of the input table containing the data for PCA training. The input data matrix should have <img class="formulaInl" alt="$ N $" src="form_219.png"/> rows and <img class="formulaInl" alt="$ M $" src="form_174.png"/> columns, where <img class="formulaInl" alt="$ N $" src="form_219.png"/> is the number of data points, and <img class="formulaInl" alt="$ M $" src="form_174.png"/> is the number of features for each data point.</p>
<p>A dense input table is expected to be in the one of the two standard MADlib dense matrix formats, and a sparse input table should be in the standard MADlib sparse matrix format.</p>
<p>The two standard MADlib dense matrix formats are </p><pre>{TABLE|VIEW} <em>source_table</em> (
    <em>row_id</em> INTEGER,
    <em>row_vec</em> FLOAT8[],
)</pre><p> and </p><pre>{TABLE|VIEW} <em>source_table</em> (
    <em>row_id</em> INTEGER,
    <em>col1</em> FLOAT8,
    <em>col2</em> FLOAT8,
    ...
)</pre><p>Note that the column name <em>row_id</em> is taken as an input parameter, and should contain a continguous list of row indices (starting at 1) for the input matrix.</p>
<p>The input table for sparse PCA is expected to be in the form:</p>
<pre>{TABLE|VIEW} <em>source_table</em> (
    ...
    <em>row_id</em> INTEGER,
    <em>col_id</em> INTEGER,
    <em>val_id</em> FLOAT8,
    ...
)</pre><p>The <em>row_id</em> and <em>col_id</em> columns specify which entries in the matrix are nonzero, and the <em>val_id</em> column defines the values of the nonzero entries. </p>
<p class="enddd"></p>
</dd>
<dt>out_table </dt>
<dd><p class="startdd">TEXT. The name of the table that will contain the output. The output is divided into three tables.</p>
<p>The primary output table (<em>out_table</em>) encodes the principal components with the <em>k</em> highest eigenvalues where <em>k</em> is either directly provided by the user or computed according to the proportion of variance. The table has the following columns: </p><table  class="output">
<tr>
<th>row_id </th><td>Eigenvalue rank in descending order of the eigenvalue size.  </td></tr>
<tr>
<th>principal_components </th><td>Vectors containing elements of the principal components.  </td></tr>
<tr>
<th>std_dev </th><td>The standart deviation of each principal component.  </td></tr>
<tr>
<th>proportion </th><td>The proportion of variance covered by the principal component.  </td></tr>
</table>
<p>The table <em>out_table</em>_mean contains the column means. This table has just one column: </p><table  class="output">
<tr>
<th>column_mean </th><td>A vector containing the column means for the input matrix.  </td></tr>
</table>
<p>The optional table <em>result_summary_table</em> contains information about the performance of the PCA. The contents of this table are described under the <em>result_summary_table</em> argument. </p>
<p class="enddd"></p>
</dd>
<dt>row_id </dt>
<dd><p class="startdd">TEXT. Column name containing the row IDs in the input source table. The column needs to be of type that can be cast to INT and should only contain values between 1 and <em>N</em>. For dense matrix format, it should contain all continguous integers from 1 to <em>N</em>.</p>
<p class="enddd"></p>
</dd>
<dt>col_id </dt>
<dd><p class="startdd">TEXT. Column name of containing the col IDS in sparse matrix representation (sparse matrices only). The column should be of type that can be cast to INT and contain values between 1 and <em>M</em>.</p>
<p class="enddd"></p>
</dd>
<dt>val_id </dt>
<dd><p class="startdd">TEXT. Name of 'val_id' column in sparse matrix representation (sparse matrices only). </p>
<p class="enddd"></p>
</dd>
<dt>row_dim </dt>
<dd><p class="startdd">INTEGER. The number of rows in the sparse matrix (sparse matrices only). </p>
<p class="enddd"></p>
</dd>
<dt>col_dim </dt>
<dd><p class="startdd">INTEGER. The number of columns in the sparse matrix (sparse matrices only). </p>
<p class="enddd"></p>
</dd>
<dt>components_param </dt>
<dd><p class="startdd">INTEGER or FLOAT. The parameter to control the number of principal components to calculate from the input data. If 'components_param' is INTEGER, it is used to denote the number of principal components (<em>k</em>) to compute. If 'components_param' is FLOAT, the algorithm will return enough principal vectors so that the ratio of the sum of the eigenvalues collected thus far to the sum of all eigenvalues is greater than this parameter (proportion of variance). The value of 'components_param' must be either a positive INTEGER or a FLOAT in the range (0.0,1.0]</p>
<dl class="section note"><dt>Note</dt><dd>The difference in interpretation between INTEGER and FLOAT was introduced to maintain backward campatibility after the proportion of variance feature was introduced. A special case to be aware of: 'components_param' = 1 (INTEGER) will return 1 principal component, but 'components_param' = 1.0 (FLOAT) will return all principal components, i.e., proportion of variance of 100%.</dd></dl>
</dd>
<dt>grouping_cols (optional) </dt>
<dd><p class="startdd">TEXT, default: NULL.</p>
<dl class="section note"><dt>Note</dt><dd><em>Not currently implemented. Any non-NULL value is ignored. Grouping support will be added in a future release. </em> The parameter is planned to be implemented as a comma-separated list of column names, with the source data grouped using the combination of all the columns. An independent PCA model will be computed for each combination of the grouping columns.</dd></dl>
</dd>
<dt>lanczos_iter (optional) </dt>
<dd><p class="startdd">INTEGER, default: minimum of {k+40, smallest matrix dimension}. The number of Lanczos iterations for the SVD calculation. The Lanczos iteration number roughly corresponds to the accuracy of the SVD calculation, and a higher iteration number corresponds to greater accuracy but longer computation time. The number of iterations must be at least as large as the value of <em>k</em>, but no larger than the smallest dimension of the matrix. If the iteration number is given as zero, then the default number of iterations is used.</p>
<dl class="section note"><dt>Note</dt><dd>If both 'lanczos_iter' and proportion of variance (via the 'components_param' parameter) are defined, 'lanczos_iter' will take precedence in determining the number of principal components (i.e. the number of principal components will not be greater than 'lanczos_iter' even if the target proportion had not been reached).</dd></dl>
</dd>
<dt>use_correlation (optional) </dt>
<dd><p class="startdd">BOOLEAN, default FALSE. Whether to use the correlation matrix for calculating the principal components instead of the covariance matrix. Currently <em>use_correlation</em> is a placeholder for forward compatibility, and this value must be set to false.</p>
<p class="enddd"></p>
</dd>
<dt>result_summary_table (optional) </dt>
<dd><p class="startdd">TEXT, default NULL. Name of the optional summary table. When NULL, no summary table is generated.</p>
<p class="enddd">This sumary table has the following columns: </p><table  class="output">
<tr>
<th>rows_used </th><td>INTEGER. Number of data points in the input.  </td></tr>
<tr>
<th>exec_time (ms) </th><td>FLOAT8. Number of milliseconds for the PCA calculation to run.  </td></tr>
<tr>
<th>iter </th><td>INTEGER. Number of iterations used in the SVD calculation.  </td></tr>
<tr>
<th>recon_error </th><td>FLOAT8. The absolute error in the SVD approximation.  </td></tr>
<tr>
<th>relative_recon_error </th><td>FLOAT8. The relative error in the SVD approximation.  </td></tr>
<tr>
<th>use_correlation </th><td>BOOLEAN. Indicates if the correlation matrix was used.  </td></tr>
</table>
</dd>
</dl>
<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 PCA training function. <pre class="example">
SELECT madlib.pca_train();
</pre></li>
<li>Create the sample data. <pre class="example">
DROP TABLE IF EXISTS mat;
CREATE TABLE mat (
    row_id integer,
    row_vec double precision[]
);
COPY mat (row_id, row_vec) FROM stdin DELIMITER '|';
1|{1,2,3}
2|{2,1,2}
3|{3,2,1}
\.
</pre></li>
<li>Run the PCA function for a fixed number of components: <pre class="example">
DROP TABLE IF EXISTS result_table;
DROP TABLE IF EXISTS result_table_mean;
SELECT pca_train( 'mat',
                  'result_table',
                  'row_id',
                  3
                );
</pre></li>
<li>View the PCA results: <pre class="example">
SELECT * FROM result_table;
</pre> Result <pre class="result">
 row_id |                     principal_components                     |       std_dev        |      proportion      
--------+--------------------------------------------------------------+----------------------+----------------------
      1 | {-0.707106781186547,-1.6306400674182e-16,0.707106781186547}  |     1.41421356237309 |    0.857142857142245
      2 | {-1.66533453693773e-16,1,5.55111512312578e-17}               |    0.577350269189626 |    0.142857142857041
      3 | {-0.707106781186548,1.11022302462516e-16,-0.707106781186547} | 1.59506745224211e-16 | 1.09038864737157e-32
</pre></li>
<li>Run the PCA function for a proportion of variance: <pre class="example">
DROP TABLE IF EXISTS result_table;
DROP TABLE IF EXISTS result_table_mean;
SELECT pca_train( 'mat',
                  'result_table',
                  'row_id',
                  0.9
                );
</pre></li>
<li>View the PCA results: <pre class="example">
SELECT * FROM result_table;
</pre> Result <pre class="result">
 row_id |                     principal_components                     |      std_dev      |    proportion     
--------+--------------------------------------------------------------+-------------------+-------------------
      1 | {-0.707106781186548,-3.46944695195361e-17,0.707106781186548} |   1.4142135623731 | 0.857142857142245
      2 | {2.22044604925031e-16,-1,1.11022302462516e-16}               | 0.577350269189626 | 0.142857142857041
</pre></li>
</ol>
<p><a class="anchor" id="notes"></a></p><dl class="section user"><dt>Notes</dt><dd></dd></dl>
<ul>
<li>Table names can be optionally schema qualified (current_schemas() would be searched if a schema name is not provided) and all table and column names should follow case-sensitivity and quoting rules per the database. (For instance, 'mytable' and 'MyTable' both resolve to the same entity, i.e. 'mytable'. If mixed-case or multi-byte characters are desired for entity names then the string should be double-quoted; in this case the input would be '"MyTable"').</li>
<li>Because of the centering step in PCA (see <a class="el" href="group__grp__pca__train.html#background_pca">Technical Background</a>), sparse matrices almost always become dense during the training process. Thus, this implementation automatically densifies sparse matrix input, and there should be no expected performance improvement in using sparse matrix input over dense matrix input.</li>
<li>For the parameter 'components_param', INTEGER and FLOAT are interpreted differently. A special case to be aware of: 'components_param' = 1 (INTEGER) will return 1 principal component, but 'components_param' = 1.0 (FLOAT) will return all principal components, i.e., proportion of variance of 100%.</li>
<li>If both 'lanczos_iter' and proportion of variance (via the 'components_param' parameter) are defined, 'lanczos_iter' will take precedence in determining the number of principal components (i.e. the number of principal components will not be greater than 'lanczos_iter' even if the target proportion had not been reached).</li>
</ul>
<p><a class="anchor" id="background_pca"></a></p><dl class="section user"><dt>Technical Background</dt><dd></dd></dl>
<p>The PCA implemented here uses an SVD decomposition implementation to recover the principal components (as opposed to the directly computing the eigenvectors of the covariance matrix). Let <img class="formulaInl" alt="$ \boldsymbol X $" src="form_220.png"/> be the data matrix, and let <img class="formulaInl" alt="$ \hat{x} $" src="form_221.png"/> be a vector of the column averages of <img class="formulaInl" alt="$ \boldsymbol{X}$" src="form_222.png"/>. PCA computes the matrix <img class="formulaInl" alt="$ \hat{\boldsymbol X} $" src="form_223.png"/> as </p><p class="formulaDsp">
<img class="formulaDsp" alt="\[ \hat{\boldsymbol X} = {\boldsymbol X} - \vec{e} \hat{x}^T \]" src="form_224.png"/>
</p>
<p> where <img class="formulaInl" alt="$ \vec{e} $" src="form_225.png"/> is the vector of all ones.</p>
<p>PCA then computes the SVD matrix factorization </p><p class="formulaDsp">
<img class="formulaDsp" alt="\[ \hat{\boldsymbol X} = {\boldsymbol U}{\boldsymbol \Sigma}{\boldsymbol V}^T \]" src="form_226.png"/>
</p>
<p> where <img class="formulaInl" alt="$ {\boldsymbol \Sigma} $" src="form_227.png"/> is a diagonal matrix. The eigenvalues are recovered as the entries of <img class="formulaInl" alt="$ {\boldsymbol \Sigma}/(\sqrt{(N-1)} $" src="form_228.png"/>, and the principal components are the rows of <img class="formulaInl" alt="$ {\boldsymbol V} $" src="form_229.png"/>. The reasoning behind using N − 1 instead of N to calculate the covariance is <a href="https://en.wikipedia.org/wiki/Bessel%27s_correction">Bessel's correction</a>.</p>
<p>It is important to note that the PCA implementation assumes that the user will use only the principal components that have non-zero eigenvalues. The SVD calculation is done with the Lanczos method, with does not guarantee correctness for singular vectors with zero-valued eigenvalues. Consequently, principal components with zero-valued eigenvalues are not guaranteed to be correct. Generally, this will not be problem unless the user wants to use the principal components for the entire eigenspectrum.</p>
<p><a class="anchor" id="literature"></a></p><dl class="section user"><dt>Literature</dt><dd></dd></dl>
<p>[1] Principal Component Analysis. <a href="http://en.wikipedia.org/wiki/Principal_component_analysis">http://en.wikipedia.org/wiki/Principal_component_analysis</a></p>
<p>[2] Shlens, Jonathon (2009), A Tutorial on Principal Component Analysis</p>
<p><a class="anchor" id="related"></a></p><dl class="section user"><dt>Related Topics</dt><dd></dd></dl>
<p>File <a class="el" href="pca_8sql__in.html" title="Principal Component Analysis. ">pca.sql_in</a> documenting the SQL functions</p>
<p><a class="el" href="group__grp__pca__project.html">Principal Component Projection</a> </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 Sep 20 2016 11:27:01 for MADlib by
    <a href="http://www.doxygen.org/index.html">
    <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.10 </li>
  </ul>
</div>
</body>
</html>