Redução de dados
Métodos Usados para
Redução e Sintetização de Dados
Em muitos casos, datasets possuem um número
elevado de atributos e de observações (objetos).
Análise de dados complexa (muitos atributos):
Pode ficar muito cara computacionalmente se todo o
conjunto de dados (dataset) for considerado;
Dependendo do tamanho do dataset, os algoritmos
podem não rodar satisfatoriamente.
Stanley Robson de M. Oliveira
Dados
Originais
Síntese
dos Dados
Solução ⇒ Sintetização de dados.
Redução de atributos e/ou objetos.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
Redução de dados …
Estratégias para redução de dados
Abordagem para redução de dados:
Obter uma representação reduzida do dataset que é
muito menor em volume, mas que produza os mesmos
(ou quase os mesmos) resultados analíticos.
Agregação.
Amostragem (Sampling).
Sintetização de dados.
Discretização e hierarquia de conceito.
A1 A2 A3 A4 A5 . . . A125
1
2
3
.
.
.
10800
MT-803: Tópicos em Matemática Aplicada – Aula 3.
2
A1 A2 A3 A4. . . A68
1
2
.
.
.
5425
3
MT-803: Tópicos em Matemática Aplicada – Aula 3.
4
Agregação
Agregação …
Combinar
Variação da Precipitação na Austrália
dois ou mais atributos (ou objetos)
em um atributo único (ou objeto).
Objetivo
Redução de dados:
Reduz o número de atributos ou objetos.
Mudança de escala (granularidade dos dados):
final:
Cidades agregadas em estados, regiões, países, etc.
Dados mais estáveis:
Agregação de tendências nos dados para reduzir a
variabilidade.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
Desvio padrão da precipitação
média mensal.
5
Dados agregados na Agricultura
MT-803: Tópicos em Matemática Aplicada – Aula 3.
6
Dados agregados na Agricultura ...
Na agricultura, muitos conjuntos de dados contêm variáveis
com valores diários, decendiais, mensais, entre outros.
Esse nível de detalhe em que os dados estarão disponíveis
para a análise chama-se granularidade.
Exemplo: transformação de dados relacionais em
multidimensionais para dados acumulados de chuva
(precipitação em mm), na Estação Granja São Pedro, RS.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
Desvio padrão da precipitação
média anual.
7
Exemplo de Cubo de Dados: forma de visualização e
interpretação dos dados no modelo multidimensional
para dados acumulados de chuva nos anos de 2003 a
2006, em algumas cidades do Rio Grande do Sul.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
8
Observações Importantes
Fatos
A metáfora denominada CUBO é apenas uma
aproximação da forma como os dados estão organizados.
Nós podemos representar um modelo tridimensional por
um cubo, mas um modelo multidimensional pode ter mais
de três dimensões – hipercubo.
Visualizar graficamente um hipercubo é muito difícil,
desta forma utiliza-se a palavra cubo como referência
para qualquer modelo multidimensional.
Um modelo multidimensional é formado por três
elementos:
9
Dimensões
Exemplos:
As vendas de cereais aumentaram em 20% nos últimos
dois anos.
O número de veranicos no RS aumentou em 6% nos
últimos 10 anos.
O consumo de bebidas alcóolicas aumentou, em SP, de
2005 a 2010.
Os índices de criminalidade aumentaram no ano atual 50%
sobre os últimos dois anos.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
10
Membros de uma Dimensão
São os elementos que participam de um fato (assunto
de negócio).
São as possíveis formas de visualizar os dados, ou seja,
são os “por” dos dados:
Fatos, dimensões e medidas.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
Fato é uma coleção de itens de dados (valores
numéricos) composta de medidas e de contexto.
Um fato é evolutivo; muda suas medidas com o tempo.
Uma dimensão pode conter muitos membros.
Hierarquia de uma dimensão é uma classificação de
dados dentro de uma dimensão.
Hierarquia 1
Hierarquia 2
Ano
Semana
Exemplo: “por mês”, “por país”, “por produto”.
As dimensões determinam o contexto de um assunto
de negócios.
Dimensões são unidades de análise com dados
agregados.
Trimestre
Dimensão tempo: dados agregados em dias, meses, anos.
Dimensão local: dados agrupados em cidade, estado, país.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
Mês
Dia
11
Trimestre
Mês
Dia
Dia
... ...
... ... ...
MT-803: Tópicos em Matemática Aplicada – Aula 3.
12
Medidas (Variáveis)
Exemplo – Modelo de Compras
São os atributos numéricos que representam
um fato.
Exemplo de medidas (métricas):
O número de enchentes na região Nordeste;
O número de unidades de produtos vendidas;
A quantidade em estoque;
O custo de venda;
Percentagem de lucro;
Número de veranicos, etc.
Uma estrela no centro representando um fato;
As pontas representando as dimensões.
Onde?
Quando?
Elementos participantes de
uma compra:
• Quando foi realizada a compra?
Compra
• Onde foi realizada a compra?
Quem?
O quê?
• Quem realizou a compra?
• O que foi comprado?
MT-803: Tópicos em Matemática Aplicada – Aula 3.
13
O Modelo Estrela (Star)
Quando analisamos compras, aplicamos o
princípio dos quatro pontos cardeais:
MT-803: Tópicos em Matemática Aplicada – Aula 3.
14
Modelo Snowflake (Floco de Neve)
Exemplo de um modelo estrela para o fato: vendas.
Dimensão
Tempo
O modelo snowflake é o resultado da decomposição de uma
ou mais dimensões que possuem hierarquias entre seus
membros.
Dimensão
Cidade
Dimensão
Tempo
Dimensão
Cliente
Dimensão
Estado
Dimensão
Localidade
Fatos de
Vendas
Dimensão
Cliente
Dimensão
Região
Fatos de
Vendas
Dimensão
Vendedor
MT-803: Tópicos em Matemática Aplicada – Aula 3.
Dimensão
Produto
Dimensão
Vendedor
15
MT-803: Tópicos em Matemática Aplicada – Aula 3.
Dimensão
Produto
16
Exercício
Estratégias para redução de dados
Uma empresa de produtos agropecuários necessita
avaliar a evolução de vendas mensal dos seus
clientes, nos últimos 5 anos. Considere as dimensões:
Tempo, Cliente, Produto e Local. As dimensões
Tempo e Local devem possuir uma hierarquia de 3
níveis (cada dimensão), enquanto a dimensão Produto
deve possuir uma hierarquia de 2 níveis. Pede-se:
Esboce o modelo estrela (hipercubo de dados) para
esta empresa.
Esboce o modelo floco de neve para esta empresa.
Elabore pelo menos oito perguntas distintas que esse
hipercubo de dados pode responder sobre a evolução de
vendas nos últimos 5 anos.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
17
Amostragem
É geralmente usada em investigações preliminares de dados e
também na análise final dos dados.
Estatísticos usam bastante as técnicas de amostragem
porque trabalhar com o conjunto de dados completo é
caro e demorado, computacionalmente.
Amostragem pode ser usada em mineração de dados
quando o conjunto de dados, sob análise, é grande (em
termos de objetos e atributos).
MT-803: Tópicos em Matemática Aplicada – Aula 3.
Agregação.
Amostragem (Sampling).
Sintetização de dados.
Discretização e hierarquia de conceito.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
18
Amostragem …
Amostragem é uma das principais técnicas empregadas
para a redução de dados.
19
O
princípio chave da amostragem eficaz:
Uma amostra produzirá resultados de qualidade
semelhantes aqueles produzidos pelo conjunto de
dados completos (se a amostra for representativa).
Uma amostra é representativa se ela tem
aproximadamente as mesmas propriedades (de
interesse) do conjunto de dados original.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
20
Tipos de Amostragem
Amostragem Aleatória Simples (Sampling without
replacement)
Existe uma probabilidade igual para a seleção de qualquer item.
Um item é selecionado e removido da população.
em
strag
Amo les
p
Sim
Amostragem com Reposição (Sampling with
replacement)
Amostragem Simples e c/ Reposição
Objetos não são removidos da população à medida em que são
selecionados para a amostra.
O mesmo objeto pode ser selecionado mais de uma vez.
Amo
st
com ragem
Repo
sição
Amostragem Estratificada (Stratified Sampling)
Separa os dados em diversas partições (estratos). Toma-se de
cada partição uma amostra percentual igual à porcentagem do
estrato em relação à população.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
21
Exemplo: Amostragem Estratificada
Para obter uma estatística de intenção de votos
para prefeito de um certo município, deseja-se uma
amostragem estratificada por bairro. No município
em questão 25% dos eleitores são de um bairro A.
Supondo uma amostra de 1000 eleitores, tomam-se
25% deles, ou seja, 250 do bairro A.
Para os demais bairros (B, C, D, ...), a seleção do
número de elementos por bairro (partição), segue a
mesma proporção.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
23
Conjunto de Dados
MT-803: Tópicos em Matemática Aplicada – Aula 3.
22
Amostragem Estratificada …
MT-803: Tópicos em Matemática Aplicada – Aula 3.
24
Amostragem Estratificada
Dados Brutos
Amostragem: Aspectos Importantes
Permite um algoritmo de mineração rodar em complexidade
que é potencialmente sub-linear com relação ao tamanho dos
dados (dataset).
Sugestões para o uso de amostragem:
Cluster/Amostra Estratificada
MT-803: Tópicos em Matemática Aplicada – Aula 3.
25
Estratégias para redução de dados
Amostragem aleatória simples pode ter uma performance muito
baixa se os dados tiverem uma distribuição assimétrica.
Amostragem estratificada:
Alternativa usada quando o conjunto de dados tem
distribuição assimétrica.
Pode ser usada na seleção de dados para o conjunto de
treinamento (Classificação), quando o número de elementos
por classe não é balanceado (Amostragem c/ Reposição
também pode ser usada).
MT-803: Tópicos em Matemática Aplicada – Aula 3.
Sintetização de Dados
Agregação.
O dataset pode ser reduzido por meio de uma
representação adequada para os dados.
Amostragem (Sampling).
Métodos Paramétricos:
Sintetização de dados.
Discretização e hierarquia de conceito.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
27
26
Um modelo ou função estimam a distribuição dos dados.
Regressão Linear: Os dados são modelados para estabelecer
uma equação matemática (reta) – relacionamento entre duas
variáveis.
Regressão Múltipla: uma variável dependente Y pode ser
modelada como uma função linear de um vetor multidimensional.
Métodos Não-paramétricos:
Não assume modelos;
Principais famílias: histogramas, clusterização, amostragem.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
28
Histogramas
Uma técnica popular
para redução de dados.
Divide os dados em
classes e armazena os
representantes de cada
classe (ex.: sum, count).
Clusterização (Agrupamento)
40
35
30
Particiona o conjunto de dados em classes (clusters).
Os representantes são os centróides e os outliers.
A eficácia depende da distribuição dos dados.
25
20
15
10
Outlier
5
0
10000
30000
50000
70000
90000
Outlier
MT-803: Tópicos em Matemática Aplicada – Aula 3.
29
Estratégias para redução de dados
Agregação.
Amostragem (Sampling).
MT-803: Tópicos em Matemática Aplicada – Aula 3.
Discretização e Hierarquia
Principais métodos para dados numéricos:
Particionamento ou Binning
Não-supervisionado
(tópico será coberto na aula de
laboratório).
Sintetização de dados.
30
Discretização e hierarquia de conceito.
Análise de Histogramas
Não-supervisionado
(tópico será coberto na aula de
laboratório).
Análise de Agrupamento
Não-supervisionado.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
31
Discretização baseado em Entropia
Supervisionado (com o uso do atributo meta ou classe)
MT-803: Tópicos em Matemática Aplicada – Aula 3.
Segmentação natural (sem o uso do atributo
32
Discretização baseada em entropia
Dado um conjunto de amostras S, se S é particionado em dois intervalos S1 e
S2 usando um valor (threshold) T, o ganho de informação é:
I (S ,T ) =
Discretização usando Classes
Método
baseado na entropia.
|S |
| S1 |
Entropy ( S 1) + 2 Entropy ( S 2 )
|S|
|S|
A entropia é calculada com base na distribuição de classes das amostras do
conjunto. Dadas m classes, a entropia de S1 é dada por:
m
Entropy ( S 1 ) = − ∑ p i log 2 ( p i )
i =1
onde pi é a probabilidade da classe i pertencer a S1
O valor de T que minimiza a função entropia sobre todos possíveis intervalos
é selecionado para a discretização binária.
O processo é aplicado recursivamente nas partições obtidas até que algum
critério de parada seja satisfeito.
O valor de T pode reduzir o tamanho dos dados e melhorar a precisão da
classificação.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
33
Discretização sem o uso de Classes
3 categorias para ambos x e y
MT-803: Tópicos em Matemática Aplicada – Aula 3.
Especificação de uma ordem parcial/total dos atributos
explicitamente por meio dos usuários ou especialistas:
Intervalos com mesmo tamanho
K-means
35
Ex.: somente Rua < Cidade, não outros atributos.
Geração automática de hierarquias (ou nível de
atributo) pela análise do número de valores distintos:
MT-803: Tópicos em Matemática Aplicada – Aula 3.
{Feagri, Unicamp, Barão Geraldo} < Campinas
Especificação de um conjunto parcial de atributos:
Rua < Cidade < Estado < País
Especificação de uma hierarquia para um conjunto de
valores através de agrupamento de dados:
Intervalos com mesma frequência
34
Geração de Hierarquia (categórico)
Dados Originais
5 categorias para ambos x e y
Ex.: para um conjunto de atributos: {Rua, Cidade, Estado, País}
MT-803: Tópicos em Matemática Aplicada – Aula 3.
36
Geração de Hierarquia (categórico)
Algumas hierarquias podem ser automaticamente
geradas com base na análise do número de valores
distintos por atributo no conjunto de dados.
O atributo com mais valores distintos é colocado no último
nível da hierarquia.
Exceções (Ex.: dia da semana, mês, semestre, ano) - ordem.
País
Estado
Cidade
Rua
Métodos para
Redução de Dimensionalidade
Stanley Robson de M. Oliveira
15 valores distintos
A1 A2 A3 A4 A5 . . . A250
365 valores distintos
1
2
3
.
.
.
10800
3.567 valores distintos
674.339 valores distintos
MT-803: Tópicos em Matemática Aplicada – Aula 3.
37
Aspectos Relevantes
Por que redução de dimensão?
Redução de dimensão:
Necessidade, motivação e aplicações.
Principais Abordagens:
Extração de atributos (não-Supervisionada);
Seleção de atributos (Supervisionada).
Muitas técnicas de aprendizado de máquina e
mineração de dados podem não ser eficientes
para dados com alta dimensionalidade:
A maldição da dimensionalidade.
A precisão e a eficiência de uma consulta degradam
rapidamente à medida em que a dimensão aumenta.
Métodos para extração de atributos (filtros):
Projeção Aleatória (Random Projection);
Análise de Componentes Principais (PCA);
Multidimensional Scaling (MS);
Decomposição do Valor Singular (SVD);
Latent Semantic Indexing (LSI).
MT-803: Tópicos em Matemática Aplicada – Aula 3.
A1 A2 A3 A4. . . A45
1
2
.
.
.
10800
39
A dimensão intrínseca pode ser menor.
Muitos atributos são irrelevantes.
Exemplo: o número de genes responsáveis por um
certo tipo de doença pode ser menor.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
40
Por que redução de dimensão? ...
Visualização: projeção de dados com alta
dimensionalidade em 2D ou 3D.
Compressão de dados: eficiência no
armazenamento e recuperação.
Remoção de ruído: efeito positivo na acurácia
de modelos e de consultas.
Motivação
Quando a dimensionalidade
aumenta, os dados tornam-se
progressivamente esparsos no
espaço em que ocupam.
Definição de distância entre
pontos, que é critica para
agrupamento e detecção de outliers,
torna-se menos significativa.
A análise de dados pode ficar muito
cara se todos os atributos forem
considerados.
• 500 pontos gerados aleatoriamente.
• Cálculo da diferença entre a distância
max e min para os pares de pontos.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
41
Relacionamento com clientes (CRM).
Mineração e/ou processamento de textos.
Melhorar a performance dos algoritmos de
aprendizado de máquina.
Recuperação de informação em banco de imagens.
Análise de dados de microarrays.
Simplificar os modelos de predição e reduzir o custo
computacional para “rodar” esses modelos.
Classificação de proteínas.
Reconhecimento de face.
Aplicações com dados meteorológicos.
Química combinatorial.
etc.
Os alvos principais do proceso de redução de
dimensionalidade são:
42
Aplicações
Motivação …
MT-803: Tópicos em Matemática Aplicada – Aula 3.
Fornecer um melhor entendimento sobre os
resultados encontrados, uma vez que existe um estudo
prévio sobre o relacionamento entre os atributos.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
43
MT-803: Tópicos em Matemática Aplicada – Aula 3.
44
Classificação de documentos
Outros exemplos de aplicações
Tarefa: classificar
documentos em categorias.
Desafio: milhares de termos.
Bibliotecas Digitais
Solução: aplicar técnicas de
redução de dimensão.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
45
Principais Abordagens
MT-803: Tópicos em Matemática Aplicada – Aula 3.
IDÉIA
Cria novos atributos a partir dos atributos originais.
Diferenças entre as duas abordagens.
GERAL: Processo que escolhe um
Objetivos:
Reduzir dimensionalidade e remover ruído.
Melhorar a performance da mineração de dados:
Aumenta
Melhora
Facilita
MT-803: Tópicos em Matemática Aplicada – Aula 3.
46
subconjunto ótimo de atributos de acordo com
uma função objetivo.
O assunto será estudado na próxima aula.
Extração de atributos (redução)
Reconhecimento de dígitos
manuscritos
Seleção de Atributos
Seleção de atributos
Reconhecimento de face
47
a velocidade do aprendizado.
a acurácia de modelos preditivos.
a compreensão dos resultados minerados.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
48
Extração de Atributos
Extração de Atributos ...
IDÉIA
GERAL: Ao invés de escolher um
subconjunto de atributos, define novas
dimensões em função de todos os atributos
do conjunto original.
Não
considera o atributo classe, somente
os atributos numéricos (vetores de dados).
MT-803: Tópicos em Matemática Aplicada – Aula 3.
49
Idéia:
Dado um conjunto de pontos no espaço d-dimensional,
Projetar esse conjunto de pontos num espaço de menor
dimensão, preservando ao máximo as informações dos dados
originais.
Em particular, escolher uma projeção que minimize o erro
quadrático na reconstrução dos dados originais.
Principais Métodos:
Projeção Aleatória (Random Projection);
Análise de Componentes Principais (PCA);
Multidimensional Scaling (MS);
Decomposição do Valor Singular (SVD);
Latent semantic indexing (LSI).
MT-803: Tópicos em Matemática Aplicada – Aula 3.
50
Seleção versus Extração (redução)
Extração de atributos:
Todos os atributos originais são usados.
Os novos atributos são combinação linear dos
atributos originais.
Seleção de atributos:
Análise de Componentes
Principais (PCA)
x2
Somente um subconjunto dos atributos originais são
selecionados.
2a. Componente
e Componente
1a.
Atributos contínuos versus discretos.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
51
x1
Análise de Componentes Principais
PCA: Idéia Geral
• A linha verde tem uma representação reduzida dos dados
originais que captura o máximo da variação original dos dados.
Método para transformar variáveis
correlacionadas em um conjunto de variáveis
não-correlacionadas que melhor explica os
relacionamentos entre os dados originais.
• A segunda linha (azul), perpendicular à primeira (verde), captura
menos variação nos dados originais.
Método para identificar as dimensões que exibem
as maiores variações em um conjunto de dados.
•Idéia geral: encontrar os autovetores da matriz de covariância
dos dados. Os autovetores definem o novo espaço.
x2
e
Método que possibilita encontrar a melhor
aproximação dos dados originais usando um
conjunto menor de atributos.
x1
MT-803: Tópicos em Matemática Aplicada – Aula 3.
53
54
Interpretação geométrica em ℜ2
Autovalores e Autovetores
Dado um operador linear T: V → V, estamos interessados em
um vetor v ∈ V e um escalar λ ∈ ℜ tais que T(v) = λv.
Neste caso T(v) será um vetor de mesma "direção" que v, ou
melhor, T(v) e v estão sobre a mesma reta suporte.
Um autovalor de uma matriz An×n é um escalar λ tal que existe
um vetor v (não-nulo), com Av = λv, onde v é chamado de
autovetor de A associado a λ.
Podemos encontrar os autovalores λ e autovetores v pela
função característica definida como:
p(λ) = det(A - λI)
MT-803: Tópicos em Matemática Aplicada – Aula 3.
• u é autovetor de T pois ∃ λ∈ ℜ / T(u) = λu.
• v não é autovetor de T pois ∃ λ∈ ℜ / T(v) = λv.
onde:
 p(λ) é chamado de polinômio característico de A;
 I é a matriz identidade.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
55
MT-803: Tópicos em Matemática Aplicada – Aula 3.
56
Redução de Dimensão: PCA …
Exemplo: Autovalores e Autovetores
 4 5
Calcular os autovalores e autovetores da matriz: A = 

 2 1
T: ℜ2 → ℜ2
(x, y) → (4x + 5y, 2x + y)
As componentes
principais são
vetores ortogonais.
Cálculo dos autovalores: det (A – λI) = 0
 4 5
5 
4 −λ
1 0 
 = det

det( A − λI ) = det  
− λ



1 − λ 
 2
0 1  
  2 1
det (A – λI) = 0 ⇔ (4 – λ )(1 – λ ) – 10 = 0 ⇔ λ2 – 5λ – 6 = 0
Os autovalores são λ1 = –1 e λ2 = 6.
Para cada autovalor encontrado, resolvemos o sistema linear (A –
λI)v = 0. Os respectivos autovetores são: v1 = (-1, 1) e
v2 = (5/2, 1).
Minimizar o erro
quadrático (Root
Mean Square).
RMS representa a
diferença entre os
pontos originais e os
novos pontos
calculados pela
transformação.
1a. Componente
5
57
PCA: Algoritmo
principal vetor
4
3
2
1
0
-1
-2
-3
2a. Componente
-4
-5
-5
MT-803: Tópicos em Matemática Aplicada – Aula 3.
1o
-4
-3
-2
-1
0
1
2
3
MT-803: Tópicos em Matemática Aplicada – Aula 3.
4
5
58
Algoritmo PCA no Matlab
% generate data
Data = mvnrnd([5, 5],[1 1.5; 1.5 3], 100);
figure(1); plot(Data(:,1), Data(:,2), '+');
Algoritmo PCA:
X Matriz de dados (N x d), em que cada linha é um
vetor xn.
X Em cada linha, subtrair a média x de cada
elemento do vetor xn em X.
%center the data
for i = 1:size(Data,1)
Data(i, :) = Data(i, :) - mean(Data);
end
DataCov = cov(Data); %covariance matrix
[PC, variances, explained] = pcacov(DataCov); %eigen
Σ matriz de covariância de X.
Encontrar os autovalores e autovetores de Σ.
PC’s os K autovetores com os maiores autovalores.
% plot principal components
figure(2); clf; hold on;
plot(Data(:,1), Data(:,2), '+b');
plot(PC(1,1)*[-5 5], PC(2,1)*[-5 5], '-r’)
plot(PC(1,2)*[-5 5], PC(2,2)*[-5 5], '-b’); hold off
% project down to 1 dimension
PcaPos = Data * PC(:, 1);
MT-803: Tópicos em Matemática Aplicada – Aula 3.
59
MT-803: Tópicos em Matemática Aplicada – Aula 3.
60
Qual é o número ideal de componentes?
Verifique a distribuição dos autovalores.
Selecione um número de autovetores que cubra 80 a
90% da variância.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
61
Resultado da Análise (Minitab)
MT-803: Tópicos em Matemática Aplicada – Aula 3.
62
Resultado da Análise (Minitab) …
É possível explicar aproximadamente 90% da variabilidade total observada nos
dados com apenas três componentes principais:
MT-803: Tópicos em Matemática Aplicada – Aula 3.
Exemplo: Dados sobre a eficiência de cana-de-açúcar para 20
municípios em SP, em 2002.
63
A Figura acima evidencia a importância das três primeiras componentes,
em relação às demais (quanto maior é o autovalor, maior será a
porcentagem de variação explicada pela componente correspondente).
MT-803: Tópicos em Matemática Aplicada – Aula 3.
64
Resultado da Análise (Minitab) …
Resultado da Análise (Minitab) …
A Figura acima ilustra geometricamente como as seis variáveis
do exemplo podem ser adequadamente representadas por duas
componentes principais (Z1 e Z2).
MT-803: Tópicos em Matemática Aplicada – Aula 3.
65
PCA: Descarte de Atributos
PCA: Descarte de Atributos ...
Dados N vetores no espaço n-dimensional, encontrar k ≤ n
vetores ortogonais (componentes principais) que podem
ser melhor usados para representar os dados.
Passos:
Normalizar dados originais: todos atributos ficam na mesma faixa
(intervalo).
Calcular k vetores ortogonais, i.e., componentes principais.
Cada vetor (original) é uma combinação linear dos k vetores
(componentes principais).
As componentes principais são ordenadas (ordem decrescente)
representando a “significância” ou “força”.
Como as componentes são ordenadas, o tamanho dos dados pode
ser reduzido eliminando-se as componentes fracas, i.e., aquelas
com baixa variância.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
As duas componentes descrevem, de uma forma geral, características
das cidades vizinhas que possuem climas e condições de cultivo
66
MT-803:
Tópicos em Matemática Aplicada – Aula 3.
semelhantes.
67
IDÉIA GERAL:
Executar PCA sobre uma matriz de correlação
com p variáveis.
Inicialmente, k variáveis são selecionadas
(retidas).
No final, (p – k) variáveis serão descartadas.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
68
PCA: Descarte de Atributos ...
PCA: Descarte de Atributos ...
Algoritmo:
A escolha de k (variáveis retidas):
Selecione o autovetor (componente) correspondente
ao menor autovalor;
Jolliffe (1972) recomenda o threshold λ0 = 0.70
depois de investigar vários conjuntos de dados;
Rejeite a variável com maior coeficiente (valor
absoluto) na componente.
Qualquer autovalor λ ≤ λ0 = 0.70 contribui muito
pouco para a explicação dos dados.
O processo continua até que os (p – k) menores
autovalores sejam considerados.
Princípio para descarte de variáveis: uma componente
com baixo autovalor é menos importante e, consequentemente, a variável que domina essa componente deve ser
menos importante ou redundante.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
69
Jolliffe, I. T. (1972). Discarding variables in principal
component analysis I: artificial data. Appl. Statist., 21,
160-173.
Jolliffe, I. T. (1973). Discarding variables in principal
component analysis II: real data. Appl. Statist., 22, 21-31.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
70
PCA: Descarte de Atributos ...
Dataset: IRIS
Projeção Aleatória
A1 A2 A3 A4 A5 . . . Ad
1
2
3
.
.
.
n
λi< 0.70
Projeção Aleatória de d para p dimensões, p << d
Variáveis descartadas: petallength, sepallength.
Variáveis retidas: sepalwidth, petalwidth.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
K1 K2 K3 K4. . . Kp
1
2
.
.
.
n
71
Projeção Aleatória
Projeção Aleatória ...
Fundamento do método:
Quando um vetor no espaço d-dimensional é projetado
em um subespaço aleatório k-dimensional (k << d), as
distâncias entre os pares de pontos são quase que
totalmente preservadas.
Projeção Aleatória de d para k dimensões:
 D é a matriz original;
 D’ é a matriz reduzida;
 R é a matriz aleatória.
Lema de Johnson e Lindenstrauss (1984).
Na prática: os pares de pontos não são distorcidos
mais do que um fator de (1 ± ε), para 0 < ε < 1, com
probabilidade O(1/n2), onde n é o número de pontos
(objetos) em análise.
A matriz R tem as seguintes características:
MT-803: Tópicos em Matemática Aplicada – Aula 3.
73
Projeção Aleatória ...
MT-803: Tópicos em Matemática Aplicada – Aula 3.
(R1): rij ~ N(0,1) e as colunas são normalizadas;
(R2): rij =
As colunas de R são compostas de vetores
ortonormais. Esses vetores têm comprimento (norma)
igual a um.
Os elementos rij de R têm média zero e variância um.
74
Projeção Aleatória ...
A matriz R é gerada da seguinte maneira:
D’ n× k = Dn× d • Rd× k (transformação linear), onde:
+ 1 com probabilid ade 1 / 6

3 ×  0 com probabilid ade 2 / 3
− 1 com probabilid ade 1 / 6

Passos:
Passo 1 – Separação dos atributos numéricos;
Passo 2 – Normalização de atributos;
Passo 3 – Redução de dimensão usando projeção
aleatória.
Passo 4 – Cálculo do erro que as distâncias (d-k)
sofrem:
2
Erro 2 = ( (dˆ − d ) 2 ) /( d )
∑
i, j
ij
ij
∑
ij
i, j
Onde: d ij é a distância entre os pontos i e j;
d̂ ij é a distância entre os pontos i e j no espaço reduzido.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
75
MT-803: Tópicos em Matemática Aplicada – Aula 3.
76
Projeção Aleatória ...
Aplicações de Projeção Aleatória
Vantagens:
Complexidade: O(m), onde m é o número de objetos;
Facilidade de implementação;
Baixo custo computacional.
Lema:
Uma projeção aleatória de d para k
dimensões, onde k << d, é uma transformação
linear não inversível.
Só pode ser aplicada para atributos numéricos.
Não é útil para as tarefas de classificação e
associação.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
weight
heart
rate
Int_def
Matriz Original
75
80
63
32
91
193
342
56
64
53
24
81
174
254
40
52
70
24
77
129
446
28
58
76
40
83
251
286
44
90
68
44
109
128
RP1
MT-803: Tópicos em Matemática Aplicada – Aula 3.
Wall, Michael E., Andreas Rechtsteiner, Luis M. Rocha. Singular
value decomposition and principal component analysis. In A
Practical Approach to Microarray Data Analysis. D.P. Berrar, W.
Dubitzky, M. Granzow, eds. pp. 91-109, Kluwer: Norwell, MA, 2003.
Papadimitriou CH, Tamaki H, Raghavan P, Vempala S. Latent
semantic indexing: a probabilistic analysis. In: Proceedings of the
17th ACM symposium on principles of database systems. Seattle, WA,
USA; June 1998. p. 159–68.
Jolliffe, I. T. Discarding Variables in a Principal Component
Analysis. In Applied Statistics, Vol. 21, No. 2 (1972), pp. 160-173.
Jolliffe, I. T. Principal Component Analysis: Springer-Verlag, New
York, 1986.
Amostra do dataset “cardiac arrhythmia”
(UCI Machine Learning Repository)
RP2
ID
Atr1
Atr2
Atr3
Atr1
Atr2
Atr3
123
-50.40
17.33
12.31
-55.50
-95.26
-107.93
342
-37.08
6.27
12.22
-51.00
-84.29
-83.13
254
-55.86
20.69
-0.66
-65.50
-70.43
-66.97
446
-37.61
-31.66
-17.58
-85.50
-140.87
-72.74
286
-62.72
37.64
18.16
-88.50
-50.22
-102.76
MT-803: Tópicos em Matemática Aplicada – Aula 3.
78
Referências para consulta
PR_int
123
Agrupamento (ou clusterização):
baseados em distância são
beneficiados com o uso de projeção aleatória.
77
QRS
de atributos representando os índices.
Algoritmos
Exemplo de Projeção Aleatória
age
Recuperação de Informação:
Redução
Desvantagens:
ID
Proteção de privacidade (mascarar dados):
Matriz Transformada
RP1: Matriz aleatória com base na
Distribuição Normal.
RP2: Matriz aleatória com base na
Distributição mais simples.
79
MT-803: Tópicos em Matemática Aplicada – Aula 3.
80
Referências para consulta ...
Kaski S. Dimensionality reduction by random mapping. In:
Proceedings of the international joint conference on neural
networks. Anchorage, Alaska; May 1999. p. 413–18.
Kruskal JB, Wish M. Multidimensional scaling. Beverly Hills, CA,
USA: Sage Publications; 1978.
Referências para consulta ...
Larsen B, Aone C. Fast and effective text mining using lineartime document clustering. In: Proceedings of the fifth ACM
SIGKDD international conference on knowledge discovery and data
mining. San Diego, CA, USA; August 1999. p. 16–22.
Faloutsos C, Lin K-I. FastMap: a fast algorithm for indexing,
datamining and visualization of traditional and multimedia
datasets. In: Proceedings of the 1995 ACM SIGMOD international
conference on management of data. San Jose, CA, USA; June
1995. p. 163–74.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
81
Referências para consulta ...
M.A. Hall. Correlation-based feature selection for machine
learning. PhD thesis, Department of Computer Science, University of
Waikato, Hamilto, New Zealand, 1998.
U. Fayyad and K. Irani. Multi-interval discretization of continuousvalued attributes for classification learning. Proceedings of the
13th International Joint Conference on Artificial Intelligence, pages
1022–1029, 1993.
H. Liu and R. Setiono. Chi2: Feature selection and discretization of
numeric attributes. Proceedings of the IEEE 7th International
Conference on Tools with Artificial Intelligence, pages 388–391,
November 1995.
T.M. Mitchell. Machine Learning. McGrawHill, USA, 1997.
P.J. Park, M. Pagano, and M. Bonetti. A non-parametric scoring
algorithm for identifying informative genes from microarray data.
Pacific Symposium on Biocomputing, pages 52–63, 2001.
MT-803: Tópicos em Matemática Aplicada – Aula 3.
Bingham E, Mannila H. Random projection in dimensionality
reduction: applications to image and text data. In: Proceedings of the
seventh ACM SIGKDD international conference on knowledge
discovery and data mining. San Francisco, CA, USA; 2001. p. 245–50.
Johnson WB, Lindenstrauss J. Extensions of Lipshitz mapping into
Hilbert space. In: Proceedings of the conference in modern analysis
and probability. Contemporary mathematics, vol. 26; 1984. p. 189–206.
Achlioptas D. Database-friendly random projections. In:
Proceedings of the 20th ACM symposium on principles of database
systems. Santa Barbara, CA, USA; May 2001. p. 274–81.
Fern XZ, Brodley CE. Random projection for high dimensional data
clustering: a cluster ensemble approach. In: Proceedings of the
20th international conference on machine learning (ICML 2003).
Washington DC, USA; August 2003
MT-803: Tópicos em Matemática Aplicada – Aula 3.
82
Referências para consulta ...
83
R. Sandy. Statistics for Business and Economics. McGrawHill, USA,
1989.
F. Wilcoxon. Individual comparisons by ranking methods.
Biometrics, 1:80–83, 1945.
E.P. Xing and R.M. Karp. Cliff: Clustering of high-dimensional
microarray data via iterative feature filtering using normalized
cuts. Proceedings of The Ninth International Conference on
Intelligence Systems for Molecular Biology, published on
Bioinformatics, 17(suppl):S306–S315, 2001.
Kenney, J. F. and Keeping, E. S. Mathematics of Statistics, Pt. 2, 2nd
ed. Princeton, NJ: Van Nostrand, 1951.
Weisstein, Eric W. Chi-Squared Test. From MathWorld – A Wolfram
Web Resource. http://mathworld.wolfram.com/Chi-SquaredTest.html
MT-803: Tópicos em Matemática Aplicada – Aula 3.
84