DECOMPOSIÇÃO POR VALORES SINGULARES

Prévia do material em texto

Universidade Federal de Minas Gerais 
Instituto de Ciências Exatas – Departamento de Ciência da Computação 
MARIA LAURA FONSECA SANTOS 
 
 
 
 
 
 
 
 
 
 
 
DECOMPOSIÇÃO POR VALORES SINGULARES 
 
 
 
 
 
 
 
 
 
Relatório apresentado à disciplina de Calculo Númerico. 
 
 
 
 
 
 
 
Universidade Federal de Minas Gerais 
Instituto de Ciências Exatas – Departamento de Ciência da Computação 
 
 
OBJETIVO: 
A partir da teoria apresentada pela disciplina, esse trabalho pretende realizar 
uma contextualização a respeito da decomposição por valores singulares 
(SVD), frequentemente empregue em métodos numéricos para mineração de 
dados. De forma mais específica, ambiciona-se fazer uso do algoritmo de SVD 
e de certos conceitos da álgebra linear para elaboração de um classificador a 
ser utilizado na recuperação de informações de um problema proposto, 
visando-se, também, uma discussão acerca dos resultados obtidos em cada 
segmento do texto. Finalmente, para a fundamentação prática desse trabalho, 
será utilizado o software iterativo MATLAB como ambiente de prototipagem. 
 
DISCUSSÃO: 
Decomposição em Valores Singulares é um tema relativamente recente na 
Matemática. Ela foi descoberta independentemente por Beltrami (1873), Jordan 
(1874) e Sylvester (1889), e trabalhos semelhantes foram feitos por Autonne 
(1915), Tagaki (1925), Williamson (1935), Eckart e Young (1939) e outros. 
 A princípio, a chamada decomposição por valores singulares (SVD) configura 
um método de fatoração numérica para uma matriz-problema de interesse, é 
um dos resultados mais importantes em Álgebra Linear, tanto computacional 
quanto teórica. No caso, essa decomposição é bastante utilizada em diversas 
áreas científicas, uma vez que tem extensiva aplicação na associação e na 
triagem de critérios de análise. 
 Na área de mineração de dados, a título de exemplo, temos a SVD, que 
assume um papel central, possibilitando a configuração de inúmeros 
mecanismos de busca on-line, cada dia mais presentes na pesquisa atual de 
informações. Essa fatoração possibilita uma grande otimização no tratamento 
de todo e quaisquer elementos computados, uma vez que está associada à 
compressão de dados. 
Nos últimos dez anos, com os avanços na capacidade e na velocidade de 
processamento foi possível sair de práticas manuais, que levavam tempo, 
sendo assim consideradas lentas para análises de dados rápidas, fáceis e 
automatizadas. Quanto mais complexos forem os dados coletados, mais 
potencial haverá para deles extrair informações importantes e relevantes. 
Hoje, varias empresas estão usando a mineração de dados. Toda essa 
definição de estudo é possível uma vez que a decomposição por valores 
singulares pode ser interpretada como uma cauterização das informações. Por 
conceito, a SVD de uma dada matriz-problema A é implementada a partir de 
três outras tabulações, T, S e D, de tal modo que A = T.S.DT. Logo, partindo-se 
de uma avaliação qualitativa simplificada, o algoritmo indica T como uma matriz 
Universidade Federal de Minas Gerais 
Instituto de Ciências Exatas – Departamento de Ciência da Computação 
de padrões de análise, e (S.D.T) como as combinações dos padrões de T que 
resultam em A. Sendo assim, a utilização da decomposição por valores 
singulares permite um alto controle dos dados. 
O banco de respostas para uma pesquisa arbitrária em um certo mecanismo de 
busca é dado por cinco documentos, onde as palavras chaves estão 
destacadas em negrito: 
1. The Google matrix P is a model of the Internet. 
 2. Pij is nonzero if there is a link from web page j to i. 
3. The Google matrix is used to rank all web pages. 
4. The ranking is done by solving a matrix eigenvalue problem. 
5. England dropped out of the top 10 in the FIFA ranking. 
Com base nessas informações, é possível construir uma tabela de termos por 
documento, computando-se as frequências absolutas das palavras-chave em 
relação aos textos. Desse modo, é possível encadear tal distribuição em uma 
matriz A ∈ 𝑅 10x5 em que cada coluna indica um respectivo documento, e cada 
linha assume a frequência de um termo (em ordem, eigenvalue, England, FIFA, 
Google, Internet, link, matrix, page, rank e web): 
 
Feito isso, cada documento pode ser entendido como um vetor, tal que cada 
valor computado indica a regularidade de um certo radical léxico no texto. Da 
mesma forma, esse procedimento pode ser feito para uma pesquisa arbitrária 
nesse banco de dados. Assumindo-se, por exemplo, que haja interesse em 
realizar uma consulta sobre o assunto “ranking of web pages”, essa query 
também pode ser definida por um vetor de frequência q ∈ R 10. Tem-se, pois, a 
seguinte construção: 
𝒒 = (0 0 0 0 0 0 0 1 1 1)T 
 A partir dessas definições, a comparação direta entre a consulta e o banco de 
dados pode-se mostrar um método bastante intuitivo para averiguar as 
conexões entre a pesquisa e as suas possíveis respostas. Desse modo, a 
princípio, o primeiro documento parece completamente irrelevante para a 
demanda inicial, visto que sua coluna correspondente não compartilha termos 
Universidade Federal de Minas Gerais 
Instituto de Ciências Exatas – Departamento de Ciência da Computação 
com o vetor q. Essa análise trivial pode ser verificada pelo cosseno formado 
entre os vetores do documento e da query, que é uma medida de similaridade 
entre os elementos, sendo obtidos os seguintes valores: 
𝑐𝑜𝑠 𝜃 = (0 0.6667; 0.7746; 0.3333; 0.3333) 
Desse modo, conclui-se a independência entre o primeiro documento e a 
query, uma vez que a distância cosseno é nula. No entanto, esse diagnóstico é 
bastante superficial, em virtude de que a metodologia considera unicamente os 
vínculos diretos entre a pesquisa e os documentos, não expressando possíveis 
relações entre os próprios documentos que poderiam interessar à demanda 
inicial. 
Tendo isso em vista, é relevante a utilização da decomposição por valores 
singulares da matriz A, que é capaz de apontar essas medidas de similaridade 
inicialmente ocultas. 
Como já fora dito, a SVD associada à matriz A é definida a partir do produto 
entre três outras matrizes, T, S e D. Por conceito, estabelece-se S como uma 
matriz diagonal em que seus elementos são os valores singulares de A, 
estando organizados em ordem decrescente de módulo. Essa configuração 
indica qual das palavras-chave é mais relevante para o banco de dados, isto é, 
apresenta maior conexão entre os documentos. A figura a baixo representa o 
gráfico plotado a partir dos cinco valores singulares computados na matriz S: 
 
Gráfico feito utilizando o comando plot (sdv(A)) 
 Dispondo-se apenas dos dois maiores valores singulares da matriz, é possível 
determinar uma aproximação para A de posto igual a 2. Esse é um artifício 
interessante da decomposição, visto que são desconsideradas certas 
particularidades dos documentos, avaliando-se somente dois modelos de 
organização. 
As novas matrizes computadas na fatoração, T2, S2 e D2, agora indicam a 
formação de clusters de interesse e as respectivas distribuições dos dados, 
que serão avaliadas em relação à query. 
Pois então, é possível obter um algoritmo mais preciso para a recuperação de 
informações, compreendendo-se não só as correspondências diretas query-
documento. A interpretação de Lars Eldén (Numerical linear algebra in data 
Universidade Federal de Minas Gerais 
Instituto de Ciências Exatas – Departamento de Ciência da Computação 
mining, 2006) para a decomposição por valores singulares, refere-se à matriz 
(S.DT) como a combinação dos padrões formalizados em T de modo a 
computar A. 
Sendo assim, o produto S2.D2
T pode ser visualizado como um mapeamento 
dos padrões de T2, o que permite a projeção das informações no gráfico 
abaixo: 
 
No caso, cada sinal em azul representa um documento da amostra, 
caracterizado por valores na base auxiliar S2.D2
T. 
Para finalizara modelagem do mecanismo de busca e ter acesso aos 
resultados que melhor atendem à demanda inicial, é necessário incorporar o 
vetor da query no espaço de modelagem. Uma vez definida a matriz T2 como 
os parâmetros de cada um dos documentos, o vetor-coordenada de q no 
ambiente de análise corresponde à solução do sistema de equações lineares 
T2.x = q. Por conseguinte, plotando-se o resultado, obtém-se a seguinte 
posição da query em relação aos documentos, apontada em vermelho: 
 
Por fim, averiguando-se a distância cosseno entre o vetor-coordenada da query 
em relação a cada coluna de T2, tem-se o seguinte: 
𝑐𝑜𝑠 𝜃2 = (0.7857 0.8332 0.9670 0.4873 0.1819) 
Considerando-se esse novo resultado, é constatada uma alta correlação entre 
a pesquisa e o primeiro documento, mostrando-se como a terceira maior 
Universidade Federal de Minas Gerais 
Instituto de Ciências Exatas – Departamento de Ciência da Computação 
correspondência, o que não foi expresso na sondagem anterior. Ainda assim, 
ambos os ensaios concordam quanto ao documento mais relevante para a 
query fornecida. 
 
CONCLUSÃO: 
Utilizando-se de certos conhecimentos da álgebra linear e de métodos 
numéricos de resolução de problemas, foi possível realizar uma 
contextualização geral acerca do funcionamento de um mecanismo de busca. 
Por meio da decomposição em valores singulares, erigiu-se um classificador de 
documentos bastante eficiente. Dada uma query específica, foram traçadas as 
pertinências de cada elemento do banco de dados. Dessa forma, obteve-se 
sucesso no objetivo desse trabalho.