Análise de padrões de uso em grades
computacionais oportunistas
Danilo M. R. Conde
Visão geral






Grades computacionais
InteGrade
LUPA
Aprendizado Computacional
Análise de Agrupamentos
Implementação Atual do LUPA
Grades computacionais



Origem
Uso de vários computadores de baixo custo
resultando em grande poder de
processamento
Grades oportunistas: uso de computadores
não dedicados quando estão ociosos
InteGrade



IME-USP, PUC-Rio, UFMA, UFG, UFMS
CNPq, CAPES, IBM, Microsoft
Provê uma infra-estrutura que permite a
implantação de grades computacionais
oportunistas
InteGrade

Linhas de pesquisa
–
–
–
–
–
–
–
Tolerância a falhas
Identificação de padrões de uso
Gerenciamento de recursos entre aglomerados
Desenvolvimento de aplicações paralelas
Agentes móveis
Segurança
Desenvolvimento de aplicações para a grade
InteGrade



Orientado a objetos
Comunicação CORBA entre módulos
C++, Java, LUA
InteGrade – executando uma aplicação
na grade
LUPA


Local Usage Pattern Analyzer
Coleta dados sobre utilização dos recursos
–
–


CPU, memória, swap, uso de mouse e teclado
Privacidade
Analisa dados de forma a estabelecer
padrões de uso
Prediz uso futuro baseado no padrão de
utilização atual
LUPA
tarde livre
1 2
3 4
5 6 7
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
manhã livre
1
2
3
4
5
6
7
8
almoço e fim livres
dia inteiro sem aulas
1 2 3
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
Aprendizado Computacional



O processo de identificação dos padrões é
um processo de aprendizado.
Um sistema aprende quando altera sua
estrutura, algoritmos e dados de forma a
melhorar seu desempenho.
“Qualquer mudança num sistema que
melhore o seu desempenho na segunda vez
que ele repetir a mesma tarefa, ou uma
tarefa da mesma população” (Simon, 1983)
Aprendizado Computacional

Por que aprender ?
–
–
–
Algumas aplicações dependem de exemplos
Mineração de dados
Agentes que atuam em ambientes que não são
completamente conhecidos
Aprendizado Computacional

Supervisionado
–

Não-supervisionado
–

Presença de um tutor que fornece exemplos
Aprende relações e propriedades entre um
conjunto de objetos
Por reforço
–
Recompensa e punição
Análise de Agrupamentos


Análise de conglomerados, clustering,
cluster analysis
É uma técnica de aprendizado nãosupervisionado cujo objetivo é separar um
conjunto de objetos em grupos de objetos
semelhantes
Análise de Agrupamentos
Análise de Agrupamentos
Análise de Agrupamentos


Não se trata de um algoritmo, mas de uma
técnica com várias implementações
diferentes
O processo de aplicar a análise de
agrupamentos a um problema possui vários
elementos
Análise de Agrupamentos - Elementos
1.
2.
3.
4.
5.
6.
7.
Escolha dos dados a serem analisados
Seleção de variáveis
Homogeneização das variáveis
Medidas de semelhança
Escolha dos algoritmos e implementação
Número de agrupamentos
Interpretação dos resultados
Análise de Agrupamentos

Dois principais tipos de algoritmos:
–
–
Hierárquicos
De Partição
Análise de Agrupamentos - Algoritmos
hierárquicos aglomerativos
Preparação: Construa n agrupamentos, um com cada elemento
do conjunto de entrada, rotulando-os de 1 a n, e construa uma
matriz de similaridade entre os agrupamentos.
Algoritmo:
Repita os seguintes passos até haver apenas um agrupamento:
1. Encontre o par de agrupamentos p e q, p > q, com menor
distância entre si, ou seja, os dois elementos mais
semelhantes. Eles serão a entrada na matriz com o menor
valor.
2. Reduza o número de agrupamentos em um, transformando o
agrupamento q na fusão de p e q. Atualize matriz de
similaridade, removendo a linha e a coluna referentes a p e
calculando as novas distâncias para q.
3. Armazene que nesse passo os agrupamentos p e q foram
fundidos e qual era a distância entre eles antes da operação.
Análise de Agrupamentos - Algoritmos
hierárquicos aglomerativos
d4
d3
d2
d1
A
B
C
D
E
Análise de Agrupamentos - Algoritmos
hierárquicos aglomerativos

Formas de calcular as distâncias entre dois
agrupamentos
–
–
–
–
Centróide
Médias das distâncias
Single Linkage: d(A, B)  mind (i, j ) : i  A, j  B
Complete Linkage: d(A, B)  maxd (i, j ) : i  A, j  B
Análise de Agrupamentos – Algoritmo
k-Médias (k-means)


Número k de agrupamentos é pré-definido
Algoritmo:
1.
2.
3.
4.
Escolha k objetos e crie uma partição com cada um deles
Insira cada objeto que ainda não está em nenhuma
partição à partição da qual ele está menos distante.
Calcule a distância de cada objeto a cada uma das
partições. Se a partição mais próxima não for a que ele
está, mova-o para ela.
Repita o passo 3 até convergir, ou seja, não existir mais
nenhum objeto que precise trocar de partição.
Implementação Atual do LUPA





A única informação coletada é a utilização de CPU,
a cada 5 minutos
Usando intervalos de 48 horas
Atualmente não utiliza análise de agrupamentos
Infra-estrutura já está pronta, falta adicionar os
algoritmos mais sofisticados
Questões abertas:
–
–
Comportamento do sistema quando não possui dados para
identificar o padrão atual
Quando devem ser recalculados os padrões