Análise de Componente Principal (PCA) e Classificação através de Clustering
Publicado em 09 de junho de 2011 por Daniela Justiniano de Sousa
1. INTRODUÇÃO - ANÁLISE DE COMPONENTES PRINCIPAIS (PCA) e
CLUSTERINGS
A Análise de Componentes Principais, conhecida como Principal Component Analysis (PCA) é uma técnica estatística utilizada para reduzir a dimensionalidade de um conjunto de dados onde há um grande número de variáveis inter-relacionadas. Essa redução se dá pela obtenção de um novo e reduzido conjunto de variáveis não correlacionadas, chamadas componentes principais. Tais componentes são então ordenados de forma que os primeiros guardam a maior parte da variância presente nas
variáveis originais. Trata-se de um extrator de característica não supervisionado, usado para identificar características entre classe que não têm uma definição prévia. Cluster é uma forma de agrupar dados em uma base de dados de forma a criar classes com elementos que se aproximam o máximo possível entre os elementos de uma mesma classe e são distante o máximo possível dos elementos de outra classe. Existem
alguns algoritmos que podem ser utilizados para criação de clusters, por exemplo, o algoritmo K-means. O K-means define pontos conhecidos como centróides em um conjunto de dados e a partir desses centróides são criadas classes. Por exemplo, para um conjunto de dados são definidos 2 centróides, então nesse conjunto busca-se os elementos que mais se
aproximam do centróide 1 e os que mais se aproximam de centróide 2, formando assim duas classes distintas, após isso é feita a média dos elementos pertencentes ao centróide 1 e também para centróide 2, os valores das médias serão os novos centróides. Com os novos centróides definidos calcula-se novamente a distancia de todos os elementos em
relação cada centróide e definem-se novas classes. Novos centróides são definidos até que os elementos de cada classe não se alterem, ou até que seja alcançado um critério de parada.
2. PROBLEMA
O presente trabalho visa solucionar um problema da área de Recuperação da Informação, no que se refere à classificação de dados. O objetivo é reduzir o esforço computacional e tempo de pesquisa para classificação de uma nova informação. Este problema pode ser percebido em técnicas como Eigenfaces, onde dada uma imagem de entrada a ser classificada em uma base, esta é comparada a cada uma das imagens da base de dados utilizada, de forma a encontrar as que mais se aproximam da
imagem de pesquisa. Neste caso, imaginando-se uma base de dados muito grande, o esforço e o tempo para a pesquisa é considerado alto.
Pensando em solucionar este problema foi proposto neste trabalho um préprocessamento da base utilizando PCA e agrupamento dos dados através de clusters, o que favoreceria este cenário. Por exemplo, em uma base contendo 30 imagens de duas classes diferentes, utilizando a técnica Eigenfaces uma imagem de entrada a ser classificada seria comparada as 30 imagens da base. Já utilizando a clusterização esta base seria dividida em dois clusters que representaria as duas classes existentes. Para
cada um dos clusters seriam definidos centróides, e uma nova imagem a ser classificada seria comparada apenas a cada um dos centróides, reduzindo assim o número de comparações de 30 para 2. Para solução do problema exposto o trabalho apresenta uma possível solução abordando as técnicas PCA e Cluster. Sendo assim, segue uma implementação em
programa Matlab que refere-se à classificação de dados a partir da técnica PCA e do processo de clusterização, partindo de uma base composta por 40 imagens, divididas em 2 classes distintas, sendo: 20 imagens da classe CARRO e 20 imagens da classe ORQUÍDEA. A fim de solucionar o problema, aplicou-se inicialmente o PCA no banco de imagens, objetivando reduzir a dimensionalidade dos dados e facilitar o processo de classificação. Posteriormente realizou-se a clusterização das imagens através do algoritmo K-means, o que possibilitou o agrupamento das imagens em dois grupos distintos, de acordo com a respectiva proximidade.
3. JUSTIFICATIVA/ SIGNIFICÂNCIA
A implementação do projeto é útil para auxiliar estudiosos a compreenderem a aplicação de PCA na tarefa de extração das características principais de imagens. Com foco em classificação de dados, o trabalho também contribui com informações enriquecedoras, referentes à temática Clusterização e algoritmo K-means. As técnicas aqui abordadas são temas de variados estudos da área de Pesquisa e
Desenvolvimento acadêmico, desta forma o trabalho apresentado é bastante relevante.
4. APLICAÇÃO
É possível encontrar a implementação de PCA em diversos problemas reais, existentes principalmente na área de Aprendizado de Máquina. Sua aplicação destaca-se na área de processamento de imagens. O processo de clusterização é um método muito utilizado para classificação de
informações, sendo bastante implementado na área de Recuperação da Informação.
5. METODOLOGIA
O presente projeto foi realizado em duas fases principais: aplicação de PCA e clusterização.
5.1. Utilização do PCA
Objetivando uma demonstração prática dos temas abordados foi implementado o algoritmo PCA e K-means para clusterização no programa Matlab 7. Para aplicação da técnica foram utilizadas 40 imagens, divididas em 2 classes distintas, sendo: 20 imagens da classe CARRO e 20 imagens da classe ORQUÍDEA. Para utilização no sistema desenvolvido as imagens foram pré-configuradas.
5.2. Clusterização
O processo de clusterização se resume na divisão de um conjunto de dados em grupos com características distintas sendo que cada um dos grupos possuem um protótipo que o representa, no caso um centróide. Nesse processo pode-se utilizar, por exemplo, o algoritmo K-means.
Para definir qual classe um cluster representa verifica-se a qual classe o maior numero de item do cluster esta relacionado, por exemplo, na Figura 4, existem 3 clusters. É possível observar que no cluster 1 tem itens de duas classes. No caso, X e círculos, no entanto, existem mais X, portanto este cluster representa a classe dos elementos X.
6. CÓDIGO
O código presente trabalho é referente ao desenvolvimento de um sistema em Matlab 7, abordando a implementação dos algoritmos PCA e K-means.
O sistema desenvolvido retrata a classificação de imagens entre duas classes distintas, Orquídeas e Carros. Inicialmente o sistema extrai as características principais das imagens através do PCA, e posteriormente classifica uma nova imagem à sua classe correta, utilizando clusterização K-Means. O objetivo principal ao desenvolver o sistema foi facilitar o entendimento da solução proposta (utilização de PCA e K-Means) ao problema deste estudo (grande esforço computacional e tempo de pesquisa no processo de classificação). Por fim, o sistema desenvolvido visa demonstrar o funcionamento prático das temáticas abordadas
pelo trabalho.
CONCLUSÃO
Para fins deste estudo, a técnica PCA foi utilizada no presente projeto visando reduzir a quantidade de dados contidos nas imagens e buscando um novo conjunto de dados com informações relevantes, ou seja, dados realmente úteis para a análise e construção do sistema. A análise de cluster foi utilizada para agrupar as imagens da base em dois grupos com conteúdo homogêneo. O método utilizado para a clusterização foi o
K-means, baseado na distância euclidiana, tendo como critério de agregação, o centróide.
CLUSTERINGS
A Análise de Componentes Principais, conhecida como Principal Component Analysis (PCA) é uma técnica estatística utilizada para reduzir a dimensionalidade de um conjunto de dados onde há um grande número de variáveis inter-relacionadas. Essa redução se dá pela obtenção de um novo e reduzido conjunto de variáveis não correlacionadas, chamadas componentes principais. Tais componentes são então ordenados de forma que os primeiros guardam a maior parte da variância presente nas
variáveis originais. Trata-se de um extrator de característica não supervisionado, usado para identificar características entre classe que não têm uma definição prévia. Cluster é uma forma de agrupar dados em uma base de dados de forma a criar classes com elementos que se aproximam o máximo possível entre os elementos de uma mesma classe e são distante o máximo possível dos elementos de outra classe. Existem
alguns algoritmos que podem ser utilizados para criação de clusters, por exemplo, o algoritmo K-means. O K-means define pontos conhecidos como centróides em um conjunto de dados e a partir desses centróides são criadas classes. Por exemplo, para um conjunto de dados são definidos 2 centróides, então nesse conjunto busca-se os elementos que mais se
aproximam do centróide 1 e os que mais se aproximam de centróide 2, formando assim duas classes distintas, após isso é feita a média dos elementos pertencentes ao centróide 1 e também para centróide 2, os valores das médias serão os novos centróides. Com os novos centróides definidos calcula-se novamente a distancia de todos os elementos em
relação cada centróide e definem-se novas classes. Novos centróides são definidos até que os elementos de cada classe não se alterem, ou até que seja alcançado um critério de parada.
2. PROBLEMA
O presente trabalho visa solucionar um problema da área de Recuperação da Informação, no que se refere à classificação de dados. O objetivo é reduzir o esforço computacional e tempo de pesquisa para classificação de uma nova informação. Este problema pode ser percebido em técnicas como Eigenfaces, onde dada uma imagem de entrada a ser classificada em uma base, esta é comparada a cada uma das imagens da base de dados utilizada, de forma a encontrar as que mais se aproximam da
imagem de pesquisa. Neste caso, imaginando-se uma base de dados muito grande, o esforço e o tempo para a pesquisa é considerado alto.
Pensando em solucionar este problema foi proposto neste trabalho um préprocessamento da base utilizando PCA e agrupamento dos dados através de clusters, o que favoreceria este cenário. Por exemplo, em uma base contendo 30 imagens de duas classes diferentes, utilizando a técnica Eigenfaces uma imagem de entrada a ser classificada seria comparada as 30 imagens da base. Já utilizando a clusterização esta base seria dividida em dois clusters que representaria as duas classes existentes. Para
cada um dos clusters seriam definidos centróides, e uma nova imagem a ser classificada seria comparada apenas a cada um dos centróides, reduzindo assim o número de comparações de 30 para 2. Para solução do problema exposto o trabalho apresenta uma possível solução abordando as técnicas PCA e Cluster. Sendo assim, segue uma implementação em
programa Matlab que refere-se à classificação de dados a partir da técnica PCA e do processo de clusterização, partindo de uma base composta por 40 imagens, divididas em 2 classes distintas, sendo: 20 imagens da classe CARRO e 20 imagens da classe ORQUÍDEA. A fim de solucionar o problema, aplicou-se inicialmente o PCA no banco de imagens, objetivando reduzir a dimensionalidade dos dados e facilitar o processo de classificação. Posteriormente realizou-se a clusterização das imagens através do algoritmo K-means, o que possibilitou o agrupamento das imagens em dois grupos distintos, de acordo com a respectiva proximidade.
3. JUSTIFICATIVA/ SIGNIFICÂNCIA
A implementação do projeto é útil para auxiliar estudiosos a compreenderem a aplicação de PCA na tarefa de extração das características principais de imagens. Com foco em classificação de dados, o trabalho também contribui com informações enriquecedoras, referentes à temática Clusterização e algoritmo K-means. As técnicas aqui abordadas são temas de variados estudos da área de Pesquisa e
Desenvolvimento acadêmico, desta forma o trabalho apresentado é bastante relevante.
4. APLICAÇÃO
É possível encontrar a implementação de PCA em diversos problemas reais, existentes principalmente na área de Aprendizado de Máquina. Sua aplicação destaca-se na área de processamento de imagens. O processo de clusterização é um método muito utilizado para classificação de
informações, sendo bastante implementado na área de Recuperação da Informação.
5. METODOLOGIA
O presente projeto foi realizado em duas fases principais: aplicação de PCA e clusterização.
5.1. Utilização do PCA
Objetivando uma demonstração prática dos temas abordados foi implementado o algoritmo PCA e K-means para clusterização no programa Matlab 7. Para aplicação da técnica foram utilizadas 40 imagens, divididas em 2 classes distintas, sendo: 20 imagens da classe CARRO e 20 imagens da classe ORQUÍDEA. Para utilização no sistema desenvolvido as imagens foram pré-configuradas.
5.2. Clusterização
O processo de clusterização se resume na divisão de um conjunto de dados em grupos com características distintas sendo que cada um dos grupos possuem um protótipo que o representa, no caso um centróide. Nesse processo pode-se utilizar, por exemplo, o algoritmo K-means.
Para definir qual classe um cluster representa verifica-se a qual classe o maior numero de item do cluster esta relacionado, por exemplo, na Figura 4, existem 3 clusters. É possível observar que no cluster 1 tem itens de duas classes. No caso, X e círculos, no entanto, existem mais X, portanto este cluster representa a classe dos elementos X.
6. CÓDIGO
O código presente trabalho é referente ao desenvolvimento de um sistema em Matlab 7, abordando a implementação dos algoritmos PCA e K-means.
O sistema desenvolvido retrata a classificação de imagens entre duas classes distintas, Orquídeas e Carros. Inicialmente o sistema extrai as características principais das imagens através do PCA, e posteriormente classifica uma nova imagem à sua classe correta, utilizando clusterização K-Means. O objetivo principal ao desenvolver o sistema foi facilitar o entendimento da solução proposta (utilização de PCA e K-Means) ao problema deste estudo (grande esforço computacional e tempo de pesquisa no processo de classificação). Por fim, o sistema desenvolvido visa demonstrar o funcionamento prático das temáticas abordadas
pelo trabalho.
CONCLUSÃO
Para fins deste estudo, a técnica PCA foi utilizada no presente projeto visando reduzir a quantidade de dados contidos nas imagens e buscando um novo conjunto de dados com informações relevantes, ou seja, dados realmente úteis para a análise e construção do sistema. A análise de cluster foi utilizada para agrupar as imagens da base em dois grupos com conteúdo homogêneo. O método utilizado para a clusterização foi o
K-means, baseado na distância euclidiana, tendo como critério de agregação, o centróide.