Análise de Componente Principal em C#

For the english version, Principal Component Analysis in C#, click this link.

A Análise de Componente Principal (PCA) é uma ferramenta exploratória criada por Karl Pearson em 1901 para identificar tendencias desconhecidas em um conjunto de dados multidimensional. A análise envolve um procedimento matemático que transforma um conjunto de variaveis possivelmente correlatas em um grupo menor de variaveis incorrelatas de denominadas componentes principais. Os primeiros componentes principais correspondem a maior variabilidade possivel contida nos dados, enquanto os componentes posteriores correspondem ao restante da informacao, em ordem decrescente de variabilidade.

Visão Geral

A técnica PCA essencialmente rotaciona o conjunto de pontos ao redor de sua média objetivando seu alinhamento com os primeiros componentes principais. Isto move a maior parte da variancia possivel (usando uma transformação linear) para as primeiras dimensões. Os valores nas dimensoes restantes, portanto, tendem a ser altamente correlacionados e podem ser ignorados com perda mínima de informação.

Para uma explicação mais detalhada sobre PCA, leia o excelente texto Tutorial On Principal Component Analysis, por Lindsay Smith (2002).

AForge.NET Framework

Minha idéia inicial era implementar a PCA internamente no AForge.NET Framework. O AForge.NET é um excelente framework de Inteligência Artificial e Visão Computacional de código aberto escrito para .NET e desenvolvido principalmente por Andrew Kirillov.

No entanto, como isto envolveria muitas mudanças e adições ao framework, acredito que seria muito difícil rever todas mudanças requeridas para adicionar esta funcionalidade diretamente em seu código fonte.

Devido a isso, este novo, e mais limpo, código, foi implementado usando somente os binários do AForge como ponto de partida. Espero que este código ajude outros precisando realizar a Análise de Componente Principal em seus próprios projetos em C#.

Esta nova biblioteca, a que chamei de Accord.NET, extende o AForge.NET adicionando novas features como a Principal Component Analysis, decomposições numéricas e algumas outras poucas transformações matemáticas e ferramentas. Na verdade, esta extensão é muito mais como um campo de teste para novas features que eu gostaria de ver em versões futuras do AForge. Mas para maior simplicidade, omiti as partes não relacionadas com PCA e criei esta versão compacta apenas para suportar a análise.

Decisões de Implementação

Como pessoas que querem utilizar PCA em seus projetos geralmente já tem suas próprias classes de matrizes, decidi evitar usar implementações específicas para tornar o código mais flexível. Também tentei evitar dependencias em outros métodos sempre que possível, para tornar o código bastante independente. Acredito que isto também tenha tornado o código mais simples de se entender.

O código está dividido entre estes dois projetos:

Accord.Math, que fornece as ferramentas matemáticas, como decomposições e transfomações; e
Accord.Statistics, que fornece análises e ferramentas estatísticas.

Ambos dependem do núcleo do AForge.NET. Adicionalmente, sua estrutura e organização interna também tenta similar ao máximo a empregada no AForge sempre que possível.

O código fonte fornecido não inclui o código fonte na íntegra do Accord Framework, que permanece como um framework de testes do que seria interessante ver no AForge, mas inclui somente porções limitadas do código necessárias para suportar PCA.

Visão Geral do Código

Below is the main code behind the PCA.

        <span>/// &lt;summary&gt;Computes the Principal Component Analysis algorithm.&lt;/summary&gt;</span><br />        <span>public</span> <span>void</span> Compute()<br />        {<br />            <span>int</span> rows = sourceMatrix.GetLength(0);<br />            <span>int</span> cols = sourceMatrix.GetLength(1);<br /><br />            <span>// Create a new matrix to work upon</span><br />            <span>double</span>[,] matrix = <span>new</span> <span>double</span>[rows, cols];<br /><br /><br />            <span>// Prepare the data, storing it in the new matrix.</span><br />            <span>if</span> (<span>this</span>.analysisMethod == AnalysisMethod.Correlation)<br />            {<br />                <span>for</span> (<span>int</span> i = 0; i &lt; rows; i++)<br />                    <span>for</span> (<span>int</span> j = 0; j &lt; cols; j++)<br />                        <span>// subtract mean and divide by standard deviation (convert to Z Scores)</span><br />                        matrix[i, j] = (sourceMatrix[i, j] - columnMeans[j]) / columnStdDev[j];<br />            }<br />            <span>else</span><br />            {<br />                <span>for</span> (<span>int</span> i = 0; i &lt; rows; i++)<br />                    <span>for</span> (<span>int</span> j = 0; j &lt; cols; j++)<br />                        <span>// Just center the data around the mean. Will have no effect if the</span><br />                        <span>//  data is already centered (the mean will be zero).</span><br />                        matrix[i, j] = (sourceMatrix[i, j] - columnMeans[j]);<br />            }<br /><br /><br /><br />            <span>// Perform the Singular Value Decomposition (SVD) of the matrix</span><br />            SingularValueDecomposition singularDecomposition = <span>new</span> SingularValueDecomposition(matrix);<br />            singularValues = singularDecomposition.Diagonal;<br /><br /><br />            <span>// Eigen values are the square of the singular values</span><br />            <span>for</span> (<span>int</span> i = 0; i &lt; singularValues.Length; i++)<br />            {<br />                eigenValues[i] = singularValues[i] * singularValues[i];<br />            }<br /><br /><br />            <span>//  The principal components of 'Source' are the eigenvectors of Cov(Source). Thus if we</span><br />            <span>//  calculate the SVD of 'matrix' (which is Source standardized), the columns of matrix V</span><br />            <span>//  (right side of SVD) will be the principal components of Source.                        </span><br /><br /><br />            <span>// The right singular vectors contains the principal components of the data matrix</span><br />            <span>this</span>.eigenVectors = singularDecomposition.RightSingularVectors;<br /><br />            <span>// The left singular vectors contains the scores of the principal components</span><br />            <span>this</span>.resultMatrix = singularDecomposition.LeftSingularVectors;<br /><br /><br />            <span>// Calculate proportions</span><br />            <span>double</span> sum = 0;<br />            <span>for</span> (<span>int</span> i = 0; i &lt; eigenValues.Length; i++)<br />                sum += eigenValues[i];<br />            sum = (1.0 / sum);<br /><br />            <span>for</span> (<span>int</span> i = 0; i &lt; eigenValues.Length; i++)<br />                componentProportions[i] = eigenValues[i] * sum;<br /><br /><br />            <span>// Calculate cumulative proportions</span><br />            <span>this</span>.componentCumulative[0] = <span>this</span>.componentProportions[0];<br />            <span>for</span> (<span>int</span> i = 1; i &lt; <span>this</span>.componentCumulative.Length; i++)<br />            {<br />                <span>this</span>.componentCumulative[i] = <span>this</span>.componentCumulative[i - 1] + <span>this</span>.componentProportions[i];<br />            }<br /><br /><br />            <span>// Creates the object-oriented structure to hold the principal components</span><br />            PrincipalComponent[] components = <span>new</span> PrincipalComponent[singularValues.Length];<br />            <span>for</span> (<span>int</span> i = 0; i &lt; components.Length; i++)<br />            {<br />                components[i] = <span>new</span> PrincipalComponent(<span>this</span>, i);<br />            }<br />            <span>this</span>.componentCollection = <span>new</span> PrincipalComponentCollection(components);

/// <summary>Computes the Principal Component Analysis algorithm.</summary> public void Compute() { int rows = sourceMatrix.GetLength(0); int cols = sourceMatrix.GetLength(1); // Create a new matrix to work upon double[,] matrix = new double[rows, cols]; // Prepare the data, storing it in the new matrix. if (this.analysisMethod == AnalysisMethod.Correlation) { for (int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) // subtract mean and divide by standard deviation (convert to Z Scores) matrix[i, j] = (sourceMatrix[i, j] - columnMeans[j]) / columnStdDev[j]; } else { for (int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) // Just center the data around the mean. Will have no effect if the // data is already centered (the mean will be zero). matrix[i, j] = (sourceMatrix[i, j] - columnMeans[j]); } // Perform the Singular Value Decomposition (SVD) of the matrix SingularValueDecomposition singularDecomposition = new SingularValueDecomposition(matrix); singularValues = singularDecomposition.Diagonal; // Eigen values are the square of the singular values for (int i = 0; i < singularValues.Length; i++) { eigenValues[i] = singularValues[i] * singularValues[i]; } // The principal components of 'Source' are the eigenvectors of Cov(Source). Thus if we // calculate the SVD of 'matrix' (which is Source standardized), the columns of matrix V // (right side of SVD) will be the principal components of Source. // The right singular vectors contains the principal components of the data matrix this.eigenVectors = singularDecomposition.RightSingularVectors; // The left singular vectors contains the scores of the principal components this.resultMatrix = singularDecomposition.LeftSingularVectors; // Calculate proportions double sum = 0; for (int i = 0; i < eigenValues.Length; i++) sum += eigenValues[i]; sum = (1.0 / sum); for (int i = 0; i < eigenValues.Length; i++) componentProportions[i] = eigenValues[i] * sum; // Calculate cumulative proportions this.componentCumulative[0] = this.componentProportions[0]; for (int i = 1; i < this.componentCumulative.Length; i++) { this.componentCumulative[i] = this.componentCumulative[i - 1] + this.componentProportions[i]; } // Creates the object-oriented structure to hold the principal components PrincipalComponent[] components = new PrincipalComponent[singularValues.Length]; for (int i = 0; i < components.Length; i++) { components[i] = new PrincipalComponent(this, i); } this.componentCollection = new PrincipalComponentCollection(components);

Usando o Código

Para realizar uma análise simples, você pode simplesmente instanciar um novo objeto PrincipalComponentAnalysis passando seu conjunto de dados e chamar seu método Compute para computar o modelo. Então você pode simplesmente chamar o método Transform para projetar os dados no espaço dos componentes principais.

Abaixo está um exemplo de código demonstrando seu uso.

            <span>// Creates the Principal Component Analysis of the given source</span><br />            PrincipalComponentAnalysis pca = <span>new</span> PrincipalComponentAnalysis(sourceMatrix,<br />                PrincipalComponentAnalysis.AnalysisMethod.Correlation);<br />    <br /><br />            <span>// Compute the Principal Component Analysis</span><br />            pca.Compute();<br /><br />            <span>// Creates a projection considering 80% of the information</span><br />            <span>double</span>[,] components = pca.Transform(sourceMatrix, 0.8f, <span>true</span>);

// Creates the Principal Component Analysis of the given source PrincipalComponentAnalysis pca = new PrincipalComponentAnalysis(sourceMatrix, PrincipalComponentAnalysis.AnalysisMethod.Correlation); // Compute the Principal Component Analysis pca.Compute(); // Creates a projection considering 80% of the information double[,] components = pca.Transform(sourceMatrix, 0.8f, true);

Demonstração

Para demonstrar o uso da Análise de Componente Principal, criei uma simples aplicação Windows Forms que efetua uma análise de dados simples e as transformações PCA em planilhas Excel.

The application can open Excel workbooks. Here we are loading some random Gaussian data, some random Poisson data, and a linear multiplication of the first variable (thus also being Gaussian).

Simple descriptive analysis of the source data, with a histogram plot of the first variable. We can see it fits a Gaussian distribution with 1.0 mean and 1.0 standard deviation.

Here we perform PCA by using the Correlation method (actually the transformation uses SVD on the standardized data, not the correlation matrix, but the effect is the same). Because the third variable is a linear multiplication of the first, the analysis detected it was totally irrelevant, thus having zero importance level.

Now we can make a projection of the source data using only the first two components.

Nota: Os componentes principais não são únicos porque a decomposição em valor singular não é única. Além do mais, os sinais na matriz de rotação são arbitrários, e portanto podem difererir entre diferentes programas para PCA.

junto com a aplicação de demonstração vem uma planilha Excel contendo vários exemplos de dados. O primeiro exemplo é o mesmo utilizado por Lindsay em seu Tutorial on Principal Component Analysis. Outros exemplos incluem dados Gaussianos, dados não correlacionados e combinações lineares de dados Gaussianos para exemplificar melhor a análise.

Bem, novamente, espero que alguém ache este código útil! 😛

2 Comments

Gabriel de Oliveira says:

May 4, 2010 at 11:39 am

Parabéns pela iniciativa, eu estava procurando exemplos que utilizassem imagens, encontrar o padrão em uma imagem. Se puder ajudar: gabrielnhrs@gmail.com

Pingback: Principal Component Analysis in C# | ~/cesarsouza/blog

César Souza