pca.sql_in

Go to the documentation of this file.

/* ----------------------------------------------------------------------- *//**
 *
 * @file pca.sql_in
 *
 * @brief Principal Component Analysis
 *
 * @sa For a brief introduction to Principal Component Analysis, see the module
 *     description \ref grp_pca.
 *
 *//* ----------------------------------------------------------------------- */

m4_include(`SQLCommon.m4')

/**

@addtogroup grp_pca_train

<div class ="toc"><b>Contents</b>
<ul>
<li class="level1"><a href="#pca_train">About</a></li>
<li class="level1"><a href="#help">Online Help</a></li>
<li class="level1"><a href="#train">Training Function</a></li>
<li class="level1"><a href="#output">Output Tables</a></li>
<li class="level1"><a href="#examples">Examples</a></li>
<li class="level1"><a href="#seealso">See Also</a></li>
<li class="level1"><a href="#background_pca">Technical Background</a></li>
<li class="level1"><a href="#literature">Literature</a></li>
</ul>
</div>

@anchor pca_train
@about
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.

See the \ref background_pca "Technical Background" for an introduction to
 principal component analysis and the implementation notes.

@anchor help
@par Online Help
View short help messages using the following statements:
@verbatim
-- Summary of PCA projection
madlib.pca_train()
madlib.pca_train('?')
madlib.pca_train('help')

-- Training function syntax and output table format
madlib.pca_train('usage')

-- Summary of PCA projection with sparse matrices
madlib.pca_sparse_train()
madlib.pca_sparse_train('?')
madlib.pca_sparse_train('help')

-- Training function syntax and output table format
madlib.pca_sparse_train('usage')
@endverbatim

@anchor train
@par Training Function
The training functions have the following formats:
@verbatim
pca_project( source_table,  out_table, row_id,
    k, grouping_cols:= NULL,
    lanczos_iter := min(k+40, <smallest_matrix_dimension>),
    use_correlation := False, result_summary_table := NULL)
@endverbatim
and
@verbatim
pca_sparse_project(source_table, out_table,
    row_id, col_id, val_id, row_dim,  col_dim, k,
    grouping_cols := NULL,
    lanczos_iter := min(k+40, <smallest_matrix_dimension>),
    use_correlation := False, result_summary_table := NULL)
@endverbatim

\note Because of the centering step in PCA (see
\ref background_pca "Technical Background"), 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.

@par Arguments
\par
<DL class="arglist">
<DT>source_table</DT>
<DD>Text value.  Name of the input table containing the data for PCA training.
The input data matrix should have  \f$ N \f$ rows
and \f$ M \f$ columns, where \f$ N \f$ is the number of data points, and \f$ M
\f$ is the number of features for each data point.

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.

The two standard MADlib dense matrix formats are
<pre>{TABLE|VIEW} <em>source_table</em> (
    <em>row_id</em> INTEGER,
    row_vec FLOAT8[],
)</pre>
and
<pre>{TABLE|VIEW} <em>source_table</em> (
    <em>row_id</em> INTEGER,
    col1 FLOAT8,
    col2 FLOAT8,
    ...
)</pre>

Note that the column name <em>row_id</em> is taken as an input parameter,
 and should contain a list of row indices (starting at 0) for the input matrix.

The input table for sparse PCA is expected to be in the form:

<pre>{TABLE|VIEW} <em>source_table</em> (
    ...
    <em>row_id</em> INTEGER,
    <em>col_id</em> INTEGER,
    <em>val_id</em> FLOAT8,
    ...
)</pre>

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.
</DD>

<DT>out_table</DT>
<DD>Text value.  Name of the table that will contain the principal components of the input data.</DD>

<DT>row_id</DT>
<DD>Text value.  Column name containing the row IDs in the input source table.</DD>

<DT>col_id</DT>
<DD>Text value.  Name of 'col_id' column in sparse matrix representation (sparse matrices only). </DD>

<DT>val_id</DT>
<DD>Text value.  Name of 'val_id' column in sparse matrix representation (sparse matrices only). </DD>

<DT>row_dim</DT>
<DD>Integer value.  The number of rows in the sparse matrix (sparse matrices only). </DD>

<DT>col_dim</DT>
<DD>Integer value.  The number of columns in the sparse matrix (sparse matrices only). </DD>

<DT>k</DT>
<DD>Integer value.  The number of principal components to calculate from the input data.  </DD>

<DT>grouping_cols</DT>
<DD>Text value.  Currently <em>grouping_cols</em> is present as a placeholder for forward
   compatibility. 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. Default: NULL.</DD>

<DT>lanczos_iter</DT>
<DD>Integer value.  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.
  Default: minimum of {k+40, smallest matrix dimension}.</DD>

<DT>use_correlation</DT>
<DD>Boolean value.  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.  Default: False. </DD>

<DT>result_summary_table</DT>
<DD>Text value. Name of the optional summary table.  Default: NULL.</DD>
</DL>

@anchor output
@par Output Tables

The output is divided into three tables (one of which is optional).
The output table (<em>'out_table'</em> above) encodes the principal components with the

<em>k</em> highest eigenvalues. The table has the following columns:
\par
<DL class="arglist">
<DT>row_id</DT>
<DD>Eigenvalue rank in descending order of the eigenvalue size.</DD>

<DT>principal_components</DT>
<DD>Vectors containing elements of the principal components.</DD>

<DT>eigen_values</DT>
<DD>The eigenvalues associated with each principal component.</DD>
</DL>

In addition to the output table, a table containing the column means is also generated.
This table has the same name as the output table, with the string "_mean" appended to the end.
This table has only one column:
\par
<DL class="arglist">
<DT>column_mean</DT>
<DD> A vector containing the column means for the input matrix.</DD>
</DL>

The optional summary table contains information about the performance of the PCA.
This table has the following columns:
\par
<DL class="arglist">
<DT>rows_used</DT>
<DD> Number of data points in the input.</DD>
<DT>exec_time (ms)</DT>
<DD>Number of milliseconds for the PCA calculation to run.</DD>
<DT>iter</DT>
<DD>Number of iterations used in the SVD calculation. </DD>
<DT>recon_error</DT>
<DD>The absolute error in the SVD approximation. </DD>
<DT>relative_recon_error</DT>
<DD>The relative error in the SVD approximation. </DD>
<DT>use_correlation</DT>
<DD>Indicates if the correlation matrix was used. </DD>
</DL>

@anchor examples
@examp
-# Create the sample data.
@verbatim
sql> DROP TABLE IF EXISTS mat;
CREATE TABLE mat (
    row_id integer,
    row_vec double precision[]
);

sql> COPY mat (row_id, row_vec) FROM stdin;
0   {1,2,3}
1   {2,1,2}
2   {3,2,1}
\.

@endverbatim
-# Run the PCA function:
@verbatim
sql> drop table result_table;
sql> select pca_train(
    'mat',              -- name of the input table
    'result_table',     -- name of the output table
    'row_id',           -- column containing the matrix indices
    3                   -- Number of PCA components to compute
);
@endverbatim
-# View the PCA results:
@verbatim
sql> SELECT * from result_table;
 row_id |                     principal_components                     |     eigen_values
--------+--------------------------------------------------------------+----------------------
      0 | {0.707106781186547,0.408248290459781,-0.577350269192513}     |                    2
      2 | {-0.707106781186547,0.408248290459781,-0.577350269192512}    | 1.26294130828989e-08
      1 | {2.08166817117217e-17,-0.816496580931809,-0.577350269183852} |    0.816496580927726

@endverbatim

@anchor seealso
@sa File pca.sql_in documenting the SQL functions
@sa grp_pca_project

@anchor background_pca
@par Technical Background

The PCA implemented here uses an SVD decomposition implementation to recover
the principle components (as opposed to the directly computing the eigenvectors
 of the covariance matrix).  Let \f$ \boldsymbol X \f$ be the data matrix, and
  let \f$ \hat{x} \f$ be a vector of the column averages of \f$ \boldsymbol{X}\f$.
    PCA computes the matrix \f$ \hat{\boldsymbol X} \f$ as
\f[
\hat{\boldsymbol X} =  {\boldsymbol X} - \vec{e} \hat{x}^T
\f]
where \f$ \vec{e} \f$ is the vector of all ones.

PCA then computes the SVD matrix factorization
 \f[
\hat{\boldsymbol X} =  {\boldsymbol U}{\boldsymbol \Sigma}{\boldsymbol V}^T
\f]
where \f$ {\boldsymbol \Sigma} \f$ is a diagonal matrix.  The eigenvalues are
recovered as the entries of \f$ {\boldsymbol \Sigma}/(\sqrt{N-1}) \f$, and the principle
components are the rows of  \f$ {\boldsymbol V} \f$.


It is important to note that the PCA implementation assumes that the user will
 use only the principle 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,
  principle components with zero-valued eigenvalues are not guaranteed to be correct.
 Generally, this will not be problem unless the user wants to use the
 principle components for the entire eigenspectrum.




@anchor literature
@literature

[1] Principal Component Analysis. http://en.wikipedia.org/wiki/Principal_component_analysis

[2] Shlens, Jonathon (2009), A Tutorial on Principal Component Analysis

**/

-- -----------------------------------------------------------------------
--  PCA for Dense matrices
-- -----------------------------------------------------------------------
/*
@brief Compute principal components for a dense matrix stored in a
        database table
*/
CREATE OR REPLACE FUNCTION
MADLIB_SCHEMA.pca_train(
    source_table          TEXT,    -- Source table name (dense matrix)
    pc_table              TEXT,    -- Output table name for the principal components
    row_id                TEXT,    -- Column name for the ID for each row
    k                     INTEGER, -- Number of principal components to compute
    grouping_cols         TEXT,    -- Comma-separated list of grouping columns (Default: NULL)
    lanczos_iter          INTEGER, -- The number of Lanczos iterations for the SVD calculation (Default: min(k+40, smallest Matrix dimension))
    use_correlation       BOOLEAN, -- If True correlation matrix is used for principal components (Default: False)
    result_summary_table  TEXT     -- Table name to store summary of results (Default: NULL)
)
RETURNS VOID AS $$
PythonFunction(pca, pca, pca)
$$ LANGUAGE plpythonu;

-- Overloaded functions for optional parameters
-- -----------------------------------------------------------------------


CREATE OR REPLACE FUNCTION
MADLIB_SCHEMA.pca_train(
    source_table    TEXT,   -- Source table name (dense matrix)
    pc_table        TEXT,   -- Output table name for the principal components
    row_id          TEXT,   -- Column name for the ID for each row
    k               INTEGER,-- Number of principal components to compute
    grouping_cols   TEXT,   -- Comma-separated list of grouping columns
    lanczos_iter    INTEGER,-- The number of Lanczos iterations for the SVD calculation
    use_correlation BOOLEAN -- If True correlation matrix is used for principal components
)
RETURNS VOID AS $$
    SELECT MADLIB_SCHEMA.pca_train($1, $2, $3, $4, $5, $6, $7, NULL)
$$ LANGUAGE SQL;

CREATE OR REPLACE FUNCTION
MADLIB_SCHEMA.pca_train(
    source_table   TEXT,   -- Source table name (dense matrix)
    pc_table       TEXT,   -- Output table name for the principal components
    row_id         TEXT,   -- Column name for the ID for each row
    k              INTEGER,-- Number of principal components to compute
    grouping_cols  TEXT,   -- Comma-separated list of grouping columns
    lanczos_iter   INTEGER -- The number of Lanczos iterations for the SVD calculation
)
RETURNS VOID AS $$
    SELECT MADLIB_SCHEMA.pca_train($1, $2, $3, $4, $5, $6, False , NULL)
$$ LANGUAGE SQL;

CREATE OR REPLACE FUNCTION
MADLIB_SCHEMA.pca_train(
    source_table   TEXT,   -- Source table name (dense matrix)
    pc_table       TEXT,   -- Output table name for the principal components
    row_id         TEXT,   -- Column name for the ID for each row
    k              INTEGER,-- Number of principal components to compute
    grouping_cols  TEXT    -- Comma-separated list of grouping columns
)
RETURNS VOID AS $$
    SELECT MADLIB_SCHEMA.pca_train($1, $2, $3, $4, $5, 0, False , NULL)
$$ LANGUAGE SQL;


CREATE OR REPLACE FUNCTION
MADLIB_SCHEMA.pca_train(
    source_table   TEXT,   -- Source table name (dense matrix)
    pc_table       TEXT,   -- Output table name for the principal components
    row_id         TEXT,   -- Column name for the ID for each row
    k              INTEGER -- Number of principal components to compute
)
RETURNS VOID AS $$
    SELECT MADLIB_SCHEMA.pca_train($1, $2, $3, $4, NULL, 0, False, NULL)
$$ LANGUAGE SQL;


-- Information Functions
-- -----------------------------------------------------------------------

CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.pca_train(
     usage_string VARCHAR   -- usage string
)
RETURNS TEXT AS $$
PythonFunctionBodyOnly(`pca', `pca')
    return pca.pca_help_message(schema_madlib, usage_string)
$$ LANGUAGE plpythonu;


CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.pca_train()
RETURNS VARCHAR AS $$
BEGIN
  RETURN MADLIB_SCHEMA.pca_train('');
END;
$$ LANGUAGE plpgsql VOLATILE;

-- -----------------------------------------------------------------------
--  PCA for Sparse matrices
-- -----------------------------------------------------------------------
/*
@brief Compute principal components for a sparse matrix stored in a
        database table
*/
CREATE OR REPLACE FUNCTION
MADLIB_SCHEMA.pca_sparse_train(
    source_table         TEXT,     -- Source table name (dense matrix)
    pc_table             TEXT,     -- Output table name for the principal components
    row_id               TEXT,     -- Name of 'row_id' column in sparse matrix representation
    col_id               TEXT,     -- Name of 'col_id' column in sparse matrix representation
    val_id               TEXT,     -- Name of 'val_id' column in sparse matrix representation
    row_dim              INTEGER,  -- Number of rows in the sparse matrix
    col_dim              INTEGER,  -- Number of columns in the sparse matrix
    k                    INTEGER,  -- Number of eigenvectors with dominant eigenvalues, sorted decreasingly
    grouping_cols        TEXT,     -- Comma-separated list of grouping columns (Default: NULL)
    lanczos_iter         INTEGER,  -- The number of Lanczos iterations for the SVD calculation (Default: min(k+40, smallest Matrix dimension))
    use_correlation      BOOLEAN,  -- If True correlation matrix is used for principal components (Default: False)
    result_summary_table TEXT      -- Table name to store summary of results (Default: NULL)
)
RETURNS VOID AS $$
PythonFunction(pca, pca, pca_sparse)
$$ LANGUAGE plpythonu;


-- Overloaded functions for optional parameters
-- -----------------------------------------------------------------------
CREATE OR REPLACE FUNCTION
MADLIB_SCHEMA.pca_sparse_train(
    source_table    TEXT,     -- Source table name (dense matrix)
    pc_table        TEXT,     -- Output table name for the principal components
    row_id          TEXT,     -- Column name for the ID for each row
    col_id          TEXT,     -- Name of 'col_id' column in sparse matrix representation
    val_id          TEXT,     -- Name of 'val_id' column in sparse matrix representation
    row_dim         INTEGER,  -- Number of rows in the sparse matrix
    col_dim         INTEGER,  -- Number of columns in the sparse matrix
    k               INTEGER,  -- Number of principal components to compute
    grouping_cols   TEXT,     -- Comma-separated list of grouping columns
    lanczos_iter    INTEGER,  -- The number of Lanczos iterations for the SVD calculation
    use_correlation BOOLEAN   -- If True correlation matrix is used for principal components
)
RETURNS VOID AS $$
    SELECT MADLIB_SCHEMA.pca_sparse_train($1, $2, $3, $4, $5, $6, $7, $8, $9, $10, $11, NULL)
$$ LANGUAGE SQL;

CREATE OR REPLACE FUNCTION
MADLIB_SCHEMA.pca_sparse_train(
    source_table  TEXT,     -- Source table name (dense matrix)
    pc_table      TEXT,     -- Output table name for the principal components
    row_id        TEXT,     -- Column name for the ID for each row
    col_id        TEXT,     -- Name of 'col_id' column in sparse matrix representation
    val_id        TEXT,     -- Name of 'val_id' column in sparse matrix representation
    row_dim       INTEGER,  -- Number of rows in the sparse matrix
    col_dim       INTEGER,  -- Number of columns in the sparse matrix
    k             INTEGER,  -- Number of principal components to compute
    grouping_cols TEXT,     -- Comma-separated list of grouping columns
    lanczos_iter  INTEGER   -- The number of Lanczos iterations for the SVD calculation
)
RETURNS VOID AS $$
    SELECT MADLIB_SCHEMA.pca_sparse_train($1, $2, $3, $4, $5, $6, $7, $8, $9, $10, False , NULL)
$$ LANGUAGE SQL;

CREATE OR REPLACE FUNCTION
MADLIB_SCHEMA.pca_sparse_train(
    source_table  TEXT,     -- Source table name (dense matrix)
    pc_table      TEXT,     -- Output table name for the principal components
    row_id        TEXT,     -- Column name for the ID for each row
    col_id        TEXT,     -- Name of 'col_id' column in sparse matrix representation
    val_id        TEXT,     -- Name of 'val_id' column in sparse matrix representation
    row_dim       INTEGER,  -- Number of rows in the sparse matrix
    col_dim       INTEGER,  -- Number of columns in the sparse matrix
    k             INTEGER,  -- Number of principal components to compute
    grouping_cols TEXT      -- Comma-separated list of grouping columns
)
RETURNS VOID AS $$
    SELECT MADLIB_SCHEMA.pca_sparse_train($1, $2, $3, $4, $5, $6, $7, $8, $9, 0, False , NULL)
$$ LANGUAGE SQL;

CREATE OR REPLACE FUNCTION
MADLIB_SCHEMA.pca_sparse_train(
    source_table  TEXT,     -- Source table name (dense matrix)
    pc_table      TEXT,     -- Output table name for the principal components
    row_id        TEXT,     -- Column name for the ID for each row
    col_id        TEXT,     -- Name of 'col_id' column in sparse matrix representation
    val_id        TEXT,     -- Name of 'val_id' column in sparse matrix representation
    row_dim       INTEGER,  -- Number of rows in the sparse matrix
    col_dim       INTEGER,  -- Number of columns in the sparse matrix
    k             INTEGER   -- Number of principal components to compute
)
RETURNS VOID AS $$
    SELECT MADLIB_SCHEMA.pca_sparse_train($1, $2, $3, $4, $5, $6, $7, $8, NULL, 0, False, NULL)
$$ LANGUAGE SQL;


-- -----------------------------------------------------------------------
-- Information Functions
-- -----------------------------------------------------------------------

CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.pca_sparse_train(
     usage_string VARCHAR   -- usage string
)
RETURNS TEXT AS $$
PythonFunctionBodyOnly(`pca', `pca')
    return pca.pca_sparse_help_message(schema_madlib, usage_string)
$$ LANGUAGE plpythonu;


CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.pca_sparse_train()
RETURNS TEXT AS $$
BEGIN
  RETURN MADLIB_SCHEMA.pca_sparse_train('');
END;
$$ LANGUAGE plpgsql VOLATILE;