Data Dimensionality Reduction Flashcards
O que é a redução de dimensionalidade considerando dados estruturados como matriz ?
Muitas fontes de dados podem ser vistas como uma grande matriz
* a web pode ser representada como uma matriz de transição
* os sistemas de recomendação armazenam as preferências do usuário como uma matriz
Em muitas dessas aplicações de matriz, a matriz é resumida por encontrar matrizes “mais estreitas” próximas da original.
O processo de obtenção de uma matriz menor e próxima da original é chamado de redução de dimensionalidade
Por que precisamos de uma representação menor?
* custo computacional
* reduzir o tamanho do conjunto de dados
* evitar a maldição da dimensionalidade: à medida que o número de recursos (ou dimensões) aumenta, quase todos os pontos ficam à mesma distância uns dos outros, em termos práticos, o desempenho de um classificador aumenta à medida que o número de recursos aumenta até que um número máximo após o desempenho se degrade bastante do que melhorar
Matriz, Valores Próprios e Vetores Próprios
O rank de uma matriz M é o número de linhas (ou colunas) linearmente independentes de M
Normalmente quer-se bases ortonormadas, com norma 1
Ao aproximar uma matriz original por uma menor pode haver redundância dos dados
Um ponto é sempre uma combinação linear da base(matriz com diagonal 1)
Sendo M uma matriz quadrada, λ uma constante e v um vetor não nulo de norma unitaria:
λ é um valor próprio de M e v o respetivo vetor prórpio se Mv=vλ
o primeiro componente diferente de zero de um autovetor é positivo
SVD- Singular Value Decomposition
A decomposição em valores singulares (SVD) permite uma representação exata de qualquer matriz, como um produto de três matrizes.
M(de qualquer dimensão, não só quadradas) = U soma V transposta
- M m x n
- r: rank de M
- U é uma matriz ortonomada m x r densa
- V é uma matriz ortonomada n x r
densa
- somatório = r x r matriz diagonal
esparsa
(valores singular- apenas multiplica por uma coluna e uma linha)pode haver 0 na diagonal principal, esta é ordenada decrescente e todos as entradas são positivas
U e V com vetores ortonomais com norma unitaria e ortogonais entre si
UTU = I
VTV = I
∥U∥ = 1
∥V∥ = 1
SVD pode ser visto como a decomposição:
* Rotação
* Stretching (sticar ou encolher)
* Segunda rotação
meter 0 nos valores singulares mais baixos de forma a eliminar linhas e colunas até reter x% de energia
valor de energia = valor próprio ^ 2
Em vez de se guardar a matriz original, guarda-se apenas as duas + a de valores singulares poupando espaço
CUR decomposition
Em aplicações grandes, M é muito espars(com muitos 0’s).Ao aplicar o SVD, U e V serão densos, todos os valores vão ser diferentes de 0, então não se poupa nada. Não podemos lidar com matrizes densas que possuem milhões ou bilhões de linhas e/ou colunas.
ALTERNATIVA:
Usar outra decomposição
M = CUR
- C é feito de colunas de M (aleatoriamente) - esparso
- R é feito de linhas de M (aleatoriamente) - esparso
- U é calculado ∥M − CUR∥F de forma que seja pequeno - denso(mas pequeno)
- r é escolhido pelos usuários (é o número de “conceitos”)
Será sempre uma aproximação
PCA
Os componentes principais são novos tipos de variáveis que são construídas como combinações lineares ou misturas das variáveis iniciais.
Eles são não correlacionados e a maior parte da informação dentro das variáveis iniciais é “comprimida” nos primeiros componentes.
Isso permite reduzir a dimensionalidade sem perder muita informação. Os componentes principais representam as direções dos dados que explicam a quantidade máxima de variância, ou seja, as linhas que capturam a maior parte da informação dos dados.
1º Organizar um conjunto de dados como X, uma matriz de dimensão
m×n, onde m é o número de tipos de medição e n é o número de tentativas/amostras.
2º Subtrair a média para cada tipo de medição ou linha.
3º Calcular a Decomposição de Valores Singulares (SVD) da matriz de covariância. As linhas de P são compostas pelas colunas de V.
4º Calcular os autovetores da matriz de covariância. As linhas de P são os autovetores.
5ºPara reduzir o número de linhas de P:
No caso do SVD: tornar os valores singulares menores iguais a zero e remover as colunas correspondentes de V.
No caso dos valores próprios: não considerar os vetores próprios cujos valores próprios são pequenos.
