Uso da Álgebra Linear em Mineração de Dados

Prévia do material em texto

Ir p/ primeira página 
 
 
 
Marcos Augusto dos Santos 
DCC-UFMG 
 
 Uso da álgebra linear 
em mineração de dados – decomposição 
por valores singulares 
Ir p/ primeira página 
Contatos: 
 Prof. Marcos Augusto dos Santos: sala 4033 
 Profas. Mirlaine e Sílvia: 
 email: calculo2011D1D2@gmail.com 
 apresentações: 
 www.dcc.ufmg.br/~mirlaine 
 
Ir p/ primeira página 
Crescimento do volume de 
informação 
(Economist, Feb 24th, 2011) 
Ir p/ primeira página 
Sumário 
 Introdução 
 Recuperação de informação 
utilizando álgebra linear 
 Oráculos “perfeitos” 
 Conclusões 
Ir p/ primeira página 
Introdução 
 Decomposição por valores 
singulares 
 Propriedades fundamentais 
 Teoremas fundamentais 
Ir p/ primeira página 
Decomposição por valores 
singulares 
 Dada uma matriz A de m linhas por n 
colunas (m > n), a decomposição por 
valores singulares consiste em obter as 
matrizes T, S e D com algumas 
propriedades 
Ir p/ primeira página 
Propriedades 
 A = TSDT 
 TTT = I 
 S é uma matriz diagonal 
 DDT = I 
 T são os autovetores de AAT 
 D são os autovetores de ATA 
Ir p/ primeira página 
Teoremas fundamentais 
 
 
 Decomposição diálica de A (somatória de 
matrizes de posto 1): 
 
T
i
p
i
iii dtsA 


1
,
Ir p/ primeira página 
Teoremas fundamentais 
 
 
 Melhor aproximação de posto k para a matriz A: 
 
T
i
k
i
iiik dstAA 


1
,
onde ti e di representam a i-ésima coluna de T e 
D; si,i é o i-ésimo elemento da diagonal de S 
Ir p/ primeira página 
Exemplo - compactação de imagens 
 
 
 
Ir p/ primeira página 
 Aplicação da álgebra linear 
para a recuperação inteligente de 
informação 
Berry, Dumais, O´Brien, Using linear algebra for 
intelligent information retrieval, Siam Review (12) 1994 
Ir p/ primeira página 
Significado geométrico do produto escalar 
Ir p/ primeira página 
Significado geométrico do produto escalar 
Ir p/ primeira página 
Projetando um vetor q (querry) em SkDk
T 
 
 
qTqtil
T
k
 
onde Tk é a matriz com as 
k primeiras colunas de T 
Ir p/ primeira página 
Exemplo 
Ir p/ primeira página 
Construção da matriz A 
 
Ir p/ primeira página 
Redução de posto 
 Seja 
 
 As combinações lineares dos vetores 
singulares à esquerda, 
 
 
 
podem ser usadas para representar as 
relações entre os n documentos 
)( 22,2222,222
TT DSTDSTAA 
nT RDS ,222,2 
Ir p/ primeira página 
Ir p/ primeira página 
Ir p/ primeira página 
application, theory: B17, B3, B6, B16, B5, B7 
Ir p/ primeira página 
Decomposição por valores singulares 
Para uma matriz Am,n , de posto r, existe uma 
fatorização (singular value decomposition - svd) 
como se segue: 
 rdiagS  ...1
 
onde os valores singulares são os elementos 
da diagonal de S: 
 
TTSDA 
Ir p/ primeira página 
Exemplo de decomposição por valores singulares 
Seja 









 

01
10
11
A
então, m=3, n=2. A sua SVD é dada por: 





























2/12/1
2/12/1
00
30
01
3/16/12/1
3/16/12/1
3/16/20
Ir p/ primeira página 
Oráculos 
 Detectando processos 
 Oráculo perfeito 
 Construção de oráculos perfeitos 
 
Ir p/ primeira página 
Detectando processos 
 Caso 1 - distribuição uniforme 
 A = rand (50, 22) 
Ir p/ primeira página 
Ir p/ primeira página 
Ir p/ primeira página 
Detectando processos 
 Caso 2 distribuição normal 
A = randn(50, 22) 
Ir p/ primeira página 
Ir p/ primeira página 
Ir p/ primeira página 
Presença de ruídos fracos 
 A: distribuição uniforme 
 B: distribuição normal 
 C = A + B 
Ir p/ primeira página 
Ir p/ primeira página 
Ir p/ primeira página 
Ir p/ primeira página 
Ir p/ primeira página 
Presença de ruídos fortes 
 A: distribuição uniforme 
 B: distribuição normal 
 E = A + 20*B 
Ir p/ primeira página 
Ir p/ primeira página 
Construção dos oráculos 
 Caso 1 (queda abrupta dos valores 
singulares): oráculo “perfeito” 
 Caso 2 (queda suave): agrupar em 
conjuntos (clusters), formando um 
conselho de oráculos 
 
 
 
Ir p/ primeira página 
Agrupamentos 
 
Bloco 1 
Bloco 2 
… 
 
Bloco k 
0’s 
0’s 
 = blocos homogêneos. 
m 
termos 
n documentos 
Qual o posto desta matriz ? 
Ir p/ primeira página 
Agrupamentos 
Tópico 1 
Tópico 2 
Tópico 3 
Ir p/ primeira página 
Como construir um conselho de 
oráculos? 
 Algoritmos de clusterização 
 Uso da otimização 
 
Ir p/ primeira página 
Conclusões 
 Novos paradigmas 
 Aplicações em mineração de 
dados