Prévia do material em texto
Inserir Título Aqui
Inserir Título Aqui
Algoritmos para
Análise de Dados
Visão Geral de Algoritmos para Análise de Dados
Responsável pelo Conteúdo:
Prof. Dr. Alberto Messias
Revisão Textual:
Prof. Ms. Luciano Vieira Francisco
Nesta unidade, trabalharemos os seguintes tópicos:
• Introdução ao Tema
• Orientações para Leitura Obrigatória
• Material Complementar Fonte: iStock/Getty Im
ages
Objetivos
• Compreender as definições iniciais sobre os algoritmos para análise de dados.
• Compreender alguns conceitos iniciais, tais como similaridade, algoritmos de criação de
regras de associação e técnica de detecção de outliers.
Caro Aluno(a)!
Normalmente com a correria do dia a dia, não nos organizamos e deixamos para o
último momento o acesso ao estudo, o que implicará o não aprofundamento no material
trabalhado ou, ainda, a perda dos prazos para o lançamento das atividades solicitadas.
Assim, organize seus estudos de maneira que entrem na sua rotina. Por exemplo, você
poderá escolher um dia ao longo da semana ou um determinado horário todos ou alguns
dias e determinar como o seu “momento do estudo”.
No material de cada Unidade, há videoaulas e leituras indicadas, assim como sugestões
de materiais complementares, elementos didáticos que ampliarão sua interpretação e
auxiliarão o pleno entendimento dos temas abordados.
Após o contato com o conteúdo proposto, participe dos debates mediados em fóruns de
discussão, pois estes ajudarão a verificar o quanto você absorveu do conteúdo, além de
propiciar o contato com seus colegas e tutores, o que se apresenta como rico espaço de
troca de ideias e aprendizagem.
Bons Estudos!
Visão Geral de Algoritmos
para Análise de Dados
UNIDADE
Visão Geral de Algoritmos para Análise de Dados
Introdução ao Tema
Visão Geral de Algoritmos para Análise de Dados
Minerar dados é o processo de descobrir informações relevantes como padrões, asso-
ciações, mudanças, anomalias e estruturas, em grandes quantidades de dados armazena-
dos em bancos de dados, depósitos de dados ou outros depósitos de informação. A mine-
ração de dados fornece percepções dos dados, descobrindo padrões e relacionamentos
ocultos em grandes bancos de dados e inferindo regras a partir desses, a fim de prever
comportamentos futuros (ZAKI; MEIRA, 2014).
O reconhecimento de padrões é uma disciplina da Ciência que tem como objetivo
classificar objetos em um número de categorias ou classes, conforme observado por
Theodoridis e Koutroumbas (2008). Dependendo da aplicação, esses objetos podem
ser, por exemplo, imagens, sinais de ondas de rádio, ou qualquer tipo de medida que se
deseja classificar.
Observa-se ainda que com as técnicas de reconhecimento de padrões pode-se, por
exemplo (DOUGHERTY, 2012):
• Estimar valores;
• Selecionar atributos relevantes para classificação;
• Reconhecer pontos “fora da curva”, chamados de outliers;
• Agrupamento de instâncias;
• Classificação de instâncias; ou
• Análise de textos.
Essas técnicas ou algoritmos possuem diversas aplicabilidades e em distintos segmentos
de mercado. Os algoritmos são aplicados em tecnologias para big data, mineração de
dados e business intelligence. Segue uma Tabela que mostra quais tipos de problemas
cada uma das técnicas se aplica ou qual problema resolve:
Tabela 1
Problema que a técnica endereça Tipo de técnica
Desejo agrupar item dadas as suas similaridades.
Quero encontrar estruturas comuns em um conjunto de dados. Clustering.
Quero encontrar relacionamentos entre ações ou itens. Regras de associação.
Quero encontrar o relacionamento ou valor específico de uma variável dada uma entrada. Regressão.
Desejo inserir uma marcação ou categoria a objetos. Classificação.
Desejo analisar um conjunto de textos ou documentos. Análise de textos.
Desejo encontrar anomalias no meu conjunto de dados. Detecção de outlier.
6
7
Seguem alguns exemplos de aplicabilidade das técnicas (THEODORIDIS;
KOUTROUMBAS, 2008):
• Detecção de outlier – comumente aplicado em análise de operações de compras
com cartão de crédito, onde se percebe fraude, caso ocorra;
• Técnicas de classificação de clientes mediante o perfil de compra e crédito;
• Técnicas de clustering, ou seja, de agrupamentos, podendo ser aplicadas para
a criação de grupos e separação de indivíduos ou criação de categorias, como de
documentos, por exemplo; além da análise de dados de postagens em redes sociais;
• Estimação de valores – estimar leituras de sensores quando há falhas na leitura ou
comunicação entre uma aplicação e o sensor;
• Seleção de atributos – compreender quais são as características que melhor defi-
nem o comportamento de uma espécie;
• Análise de textos – aplicação que caracteriza um perfil social dadas as suas
postagens em uma rede social de textos.
E alguns exemplos de aplicabilidade de técnicas de reconhecimento de padrões:
• Reconhecimento de fala;
• Reconhecimento de textos;
• Identificação por impressão digital ou íris;
• Identificação de sequência de DNA;
• Avaliação de risco de crédito;
• Detecção de anomalias em leituras de sensores;
• Busca de água em imagens de satélite retiradas de Marte;
• Categorização automática de documentos e filmes.
Note que um aspecto importante para qualquer uma das técnicas é a seleção correta
dos atributos, limpeza adequada dos dados, certo conhecimento do domínio de aplicação,
percepção de ruídos nos dados e validação do modelo de análise proposto pela técnica
ou execução do algoritmo, além de saber aplicar a técnica adequada para o tipo de
domínio e de dados a serem analisados.
Algoritmos com Regras de Associação
Regras de associação representam um padrão de relacionamento entre itens de da-
dos no domínio da aplicação, que ocorrem com determinada frequência nas bases de
dados. Uma regra de associação demonstra a presença de determinado conjunto que
implica na apresentação de algum outro conjunto distinto de itens.
7
UNIDADE
Visão Geral de Algoritmos para Análise de Dados
As regras de associação podem ser definidas formalmente como: dado um con-
junto de itens I = {i1, i2... im}, sendo D um conjunto de transações, enquanto cada
transação T é um conjunto de itens tal que I ⊇ T, onde cada transação está associada
a um identificador único, tal que T ⊇ X, I ⊇ X. Assim, a regra associativa equivale a
uma implicação na forma X → Y, enquanto X é o antecedente e Y é o consequente
(GILLMEISTER; CAZELLA, 2007).
O algoritmo mais conhecido para a criação de regras de associação é o apriori,
proposto por Agrawal, em 1994, com o objetivo de encontrar regras associativas em
grandes e complexas bases de dados. Constitui-se em um dos algoritmos mais difundidos
em regras associativas, tendo originado muitos outros, dado que seu grande diferencial
está em sua simplicidade.
A abrangência de uma regra constitui-se no número de instâncias que são preditas
corretamente, de modo que tal característica é chamada de suporte. A precisão da
regra associativa é conhecida como confiança, onde se faz uma proporção das ins-
tâncias corretamente preditas sobre todas as instâncias analisadas (GILLMEISTER;
CAZELLA, 2007).
O algoritmo gera todos os conjuntos de itens – chamados de itemsets candidatos
– e testa qual a relevância daquele conjunto na base de dados. Quando o conjunto
não é muito relevante, este e os outros conjuntos dos quais são subconjuntos ficam
excluídos dos itemsets candidatos. A relevância dos conjuntos deve ser medida por meio
de critérios, ou medidas que possam identificar quais das possíveis regras de associação
são mais interessantes. Para isso, são introduzidas as medidas de interesse.
Assim, considerando uma regra X → Y, onde X é o conjunto de itens do antecedente
da regra, Y é o conjunto de itens de seu consequente e X ∪ Y é o conjunto de todos
os itens presentes no antecedente e no consequente, tem-se as seguintes medidas de
interesse aplicadas sobre a regra: considerando P(X) igual ao número de transações
contendo os itens de X divididospelo número total de transações da base de dados.
Ademais, seguem algumas definições de termos que serão constantemente utilizados:
• Confiança – foi introduzida na mineração de dados por meio do modelo su-
porte-confiança, desenvolvido por Agrawal, Imielinski e Srikant, em 1993.
Esta medida indica a ocorrência de transações em que todos os itens da regra
aparecem em relação às transações em que os itens do antecedente estão pre-
sentes, ou seja:
• Suporte – em um itemset X em I, denotado como sup(X), é o número das transa-
ções que contêm X, este dividido pelo número total de transações, ou seja:
sup X
t X t
I
j j( ) =
⊆{ }:
8
9
Um itemset é frequente se o seu suporte é maior que o suporte limiar, que é uma
entrada para o algoritmo apriori, dado como suporte mínimo que o itemset pode ter
para continuar aceito pelo algoritmo.
A partir da escolha de uma medida de interesse, cada regra de associação possível de
ser gerada é avaliada e aquelas que não atendem a um valor mínimo definido e passadas
como parâmetros para o algoritmo são descartadas.
A parametrização normalmente é feita com um suporte mínimo e uma confiança
também mínima.
Inicialmente, o algoritmo apriori faz diversas passagens sobre os dados para selecionar
todos os conjuntos de itens frequentes, sendo que em cada um destes passos gera,
primeiramente, um conjunto de itens candidatos e, então, percorre a base de dados para
determinar se os candidatos satisfazem o suporte mínimo estabelecido pelo parâmetro.
Segue um exemplo de criação das regras de associação, com a formação dos itemsets
e valores de suporte:
Tabelas 2, 3 e 4 – Exemplo de base de dados com itens
Fonte: Acervo do Conteudista
Este exemplo mostra uma tabela com alguns itens referentes a compras em um
supermercado. Considerando um suporte mínimo de 25%, o algoritmo analisa os itens
e verifica os mais frequentes; em seguida, monta outra tabela e despreza os itens que
não atendem ao suporte mínimo; adiante, varre a mesma base, desprezando então
os itens menos frequentes e analisando agora a frequência para 2 itemsets, fazendo a
mesma análise, enquanto que os itens menos frequentes são desprezados.
9
UNIDADE
Visão Geral de Algoritmos para Análise de Dados
Tabelas 5, 6, 7 e 8 – Exemplo de base de dados com itens
Fonte: Acervo do Conteudista
Neste caso é realizada a mesma iteração com três itens e depois com quatro, satisfa-
zendo, assim, o suporte mínimo, de modo que temos uma regra de associação simples:
pessoas que compram leite normalmente compram também ovos, café e açúcar.
No algoritmo apriori, com os conjuntos frequentes de tamanho três, geram-se can-
didatos de tamanho quatro, realizando-se a poda e calculando seus valores de suporte.
Em seguida, com os conjuntos frequentes de tamanho quatro, são obtidos os conjuntos
candidatos de tamanho cinco, e assim por diante, até que não seja mais possível gerar
candidatos k a partir dos conjuntos frequentes de tamanho k - 1.
Após a conclusão da etapa de obtenção dos conjuntos de itens frequentes na base de
dados, devem ser geradas as regras de associação no formato X → Y. Esta nova etapa
é crítica, tendo em vista que podem ter sido obtidos muitos conjuntos frequentes e, para
cada um dos quais, pode-se obter várias regras por meio das combinações de seus itens
no antecedente e consequente de cada regra.
Tendo em vista que para um conjunto frequente de tamanho k podem ser geradas
k! regras diferentes, o número de regras possíveis pode se tornar muito grande,
principalmente quando se tem muitos conjuntos frequentes de tamanho superior a dois,
inviabilizando qualquer análise por parte dos usuários de mineração de dados.
10
11
Segue o pseudocódigo do algoritmo apriori:
Quadro 1 – Algoritmo apriori
Fonte: Adaptado de Gillmeister e Cazella, 2007
No início, L1, que é o conjunto com somente um elemento, é gerado. Na sequência,
tem-se um laço com k passos, neste serão desenvolvidas duas tarefas: a primeira é a
geração do grupo de itens candidatos Ck, por meio dos itens gerados no passo anterior
(conjunto de Lk-1) e utilizando-se da função apriori-gen para isto; a segunda tarefa
executada no laço k consiste em outro laço para contagem do suporte dos itens do
grupo candidato Ck, onde cada transação da base de dados é analisada. Neste momento,
o algoritmo apriori utiliza uma função estruturada na forma de uma hash-tree, onde cada
nó folha contém uma lista de itens ou o endereçamento para uma tabela hash. Assim,
torna-se possível encontrar, de forma ágil, todos os candidatos contidos na transação t.
Cada candidato c terá no final o seu suporte calculado e no próximo passo k, os itens
que não obtiveram o suporte mínimo estabelecido serão excluídos.
A função apriori-gen apresenta duas finalidades: a primeira consiste em formar a
união dos conjuntos frequentes; a segunda gera o conjunto de candidatos Ck. Assim, os
itens do conjunto candidato formado estarão ordenados lexicograficamente, eliminando
aqueles que possuírem itens iguais, conforme se vê no seguinte Quadro:
11
UNIDADE
Visão Geral de Algoritmos para Análise de Dados
Quadro 2 – Função apriori-gen
Fonte: Adaptado de Gillmeister e Cazella, 2007
Outro objetivo da função apriori-gen é fazer a poda do conjunto de itens candidatos,
usando o princípio de que cada subconjunto de um conjunto de itens frequentes também
deve ser frequente. Tal regra é utilizada para reduzir o número de candidatos a serem
comparados com cada transação na base de dados (GILLMEISTER; CAZELLA, 2007).
Todos os candidatos gerados que contenham algum subconjunto que não seja frequente,
serão podados pela função apriori-gen.
O algoritmo apriori apresenta muitas derivações, as quais consistem em pequenas
alterações, adicionando vantagens em relação ao tempo de execução, alocação de
memória e geração de regras mais concisas e confiáveis.
As seguintes derivações do algoritmo apriori serão apresentadas:
• Fast apriori;
• Predictive apriori;
• TID apriori;
• Apriori hybrid;
• Apriori group.
Similaridade e Medidas de Distância
Conforme se observa em Theodoridis e Koutroumbas em (2008), uma medida de
similaridade ou dissimilaridade expressa, em valor real, a similaridade ou diferença entre
dois vetores ou instâncias; a fim de se medir esses valores, podem ser utilizadas medidas
de distância entre dois pontos. As medidas de distância comumente utilizadas são a
euclidiana, de Mahalanobis e de Manhattan.
12
13
A distância de Mahalanobis foi introduzida em 1936 pelo matemático indiano
Prasanta Chandra Mahalanobis, baseando-se nas correlações entre as variáveis.
A distância de Manhattan é uma forma de geometria que se baseia na soma das
diferenças absolutas de todas as coordenadas entre um ponto e outro. Em outras pala-
vras, assemelha-se à distância calculada em um software de Global Positioning System
(GPS), ou seja, que não trata como uma linha reta entre os dois pontos, mas sim a soma
de todas as distâncias entre cada rua ou esquina que se passa. Essa distância tem esse
nome tendo em vista a analogia feita ao cálculo da distância que um táxi percorre em
Manhattan para ir de um ponto a outro nessa cidade. Assim, o cálculo da distância entre
o ponto P1 com valores (x1, y1) e o ponto P2 em (x2, y2) é |x1 - x2| + |y1 - y2|.
Ademais, neste momento nos concentraremos na distância euclidiana, que é uma das
mais utilizadas. Essa medida de distância mede, na verdade, o comprimento de uma reta
entre dois pontos no espaço euclidiano, o que é a menor distância entre dois pontos
quaisquer em um plano.
A seguinte Figura ilustra uma comparação entre as duas medidas de distância, a
euclidiana e a de Manhattan:
Figura 1 – Comparação entre as distâncias de Manhattan e euclidiana
Note que a distância euclidiana calcula a reta entre os dois pontos, enquanto
que a distância de Manhattan é a soma de todas as esquinas e ruas percorridas.
Assim, o cálculo da distância euclidiana entre o ponto P1 com valores (x1, y1) e
o ponto P2em x y é x x y y2 2 1 2 1 2, ² ² .(( ) ( ) ) ( ) − −√ +
Neste caso, a distância euclidiana é calculada em um plano de duas dimensões, ou
com dois atributos, porém, pode ser calculada para qualquer quantidade de dimensões
ou atributos. A equação para o cálculo da distância euclidiana entre os pontos Pi e Pj é:
d p pik jk
k
n
= −( )
=
∑
2
1
Onde n é o número de atributos ou dimensões, a distância é, então, raiz quadrada da
soma das diferenças entre os atributos das duas instâncias Pi e Pj, elevada ao quadrado.
13
UNIDADE
Visão Geral de Algoritmos para Análise de Dados
Segue um exemplo A (3, 5, 8) e B (1, 4, 3), em que a distância euclidiana é:
d x x y y z zb a b a b a= −( ) + −( ) + −( ) =
= −( ) + −( ) + −( ) =
= −( ) +
2 2 2
2 2 2
2
1 3 4 5 3 8
2 −−( ) + −( ) = + + =
= ≈
1 5 4 1 25
30 5 477225575051661
2 2
.
Técnica de Detecção de Outilier
Segundo Zaki e Meira (2014), uma anomalia ou um outlier ocorre quando uma
instância ou um conjunto de instâncias é considerado diferente do restante do conjunto
de dados. A detecção de outliers tem importantes aplicações para a constatação de
fraudes em cartões de crédito, em sistemas de telecomunicações, além da detecção de
falhas, redes de sensores, de intrusos, de spam em e-mail, diagnósticos médicos ou
aplicações em marketing.
Há três tipos de técnicas elencadas na literatura para a detecção de outliers: baseadas
em distância, densidade ou estatísticas (ZAKI; MEIRA, 2014).
Destaca-se a técnica baseada em distância, na qual dada instância é considerada
um outlier caso uma fração, onde p(0 < p < 1), de instâncias em uma base de dados
esteja fora do raio de uma vizinhança O. Caso esse limiar seja muito grande, pontos que
deveriam ser considerados outliers não o serão; caso esse limiar seja muito pequeno,
grande parte dos pontos será erroneamente considerada como outlier.
Abordagens mais simples para a detecção de outliers utilizam os valores de quartil no
conjunto de dados que, por sua vez, emprega a medida de mediana. Trata-se do valor
que separa a metade menor da metade maior da população ou do conjunto de dados; ou
seja, em uma série de números, por exemplo: {1, 1, 2, 3, 5, 6, 6, 7, 8, 9, 10}, o valor
central é 6; caso o conjunto de dados tenha a quantidade par de números e não houver
um valor central na média entre os valores do par central, tratar-se-á da mediana, por
exemplo: {1, 2, 3, 3, 5, 5, 6, 7, 8, 9, 10, 11}, onde o par central é {5, 6} e a média
entre esses é 5,5, logo, sua mediana.
Uma técnica simples para a detecção de outliers é o uso dos valores de mediana e
quartis do conjunto de dados. Segue um exemplo prático:
• Dado o conjunto com valores de salários de vendedores em determinado mês, neste
caso há um vendedor que possui um salário muito díspar do conjunto {1, 2, 2, 3,
5, 5, 6, 7, 8, 9, 10, 12, 40};
• Calcula-se a mediana do conjunto total: {1, 2, 2, 3, 5, 5, 6, 7, 8, 9, 10, 12, 40},
neste caso o valor 6, destacado;
• Calcula-se a mediana do conjunto obtido com valores menores ao da primeira
mediana, de modo que o conjunto obtido é: {1, 2, 2, 3, 5, 5, 6}, neste caso o valor
3, destacado;
14
15
• Calcula-se a mediana do conjunto obtido com valores maiores ao da primeira
mediana, de modo que o conjunto obtido é: {6, 7, 8, 9, 10, 12, 40}, neste caso o
valor 9, destacado;
• Temos, assim, os seguintes conjuntos e divisões – conforme o exemplo de criação
dos conjuntos para análise de outlier:
• A partir desses valores, calcula-se o valor denominado Inter-Quartil (IQR), que
é dado pela diferença entre as medianas dos quartis 3 e 1. Observe o seguinte
intervalo IQR:
• O tamanho desse IQR é dado por 9 - 3 = 6;
• Para determinar um valor de outlier, multiplica-se esse valor por 1,5; logo, o valor
será 6 x 1,5 = 9;
• Assim, um outlier é um número cuja diferença com Q1 é menor que 9, ou a
diferença com Q3 é maior que 9. Ou seja, qualquer valor menor que Q1 = 3 - 9 =
-6; e qualquer valor maior que Q3 = 9 + 9 = 18;
• Ademais, qualquer valor menor que -6 e maior que 18 deve ser considerado um
outlier, de modo que em nosso exemplo, o valor 40 é um outlier.
Existem outras técnicas e algoritmos para a detecção de outlier, sendo essa a mais
simples. No Material complementar é sugerido um artigo que mostra outra técnica
utilizando algoritmo de clustering e processamento com big data.
15
UNIDADE
Visão Geral de Algoritmos para Análise de Dados
Orientações para Leitura Obrigatória
Segue a indicação de leitura do item 3.4.3.1, sobre o algoritmo de detecção de outlier
usando big data e o algoritmo de clustering kmeans, assunto presente na tese de
Doutorado intitulada Uma nova arquitetura para internet das coisas com análise e
reconhecimento de padrões e processamento com big data:
https://goo.gl/z4heTy
Leia também o artigo intitulado An outlier detect algorithm using big data proces-
sing and internet of things architecture, que define a técnica e o algoritmo utilizado
na leitura anterior:
https://goo.gl/z1k7DE
Finalmente, segue também a indicação de leitura do relatório técnico que ilustra muito
bem o algoritmo para a geração de regras de associação apriori, trata-se do quarto
capítulo, intitulado Mineração de dados e regras de associação:
https://goo.gl/Htb9xp
16
17
Material Complementar
Indicações para saber mais sobre os assuntos abordados nesta Unidade:
Sites
UCI – Machine Learning Repository
Segue a indicação do site com o repositório de bases de dados públicas para experimentos
em análise de dados:
https://goo.gl/xvrdyL
Software Weka
Assim como o site do software Weka, que traz inúmeras bases públicas para experimentos
em análise de dados:
https://goo.gl/a0uvXW
17
UNIDADE
Visão Geral de Algoritmos para Análise de Dados
Referências
DEZA, M. M.; DEZA, E. Encyclopedia of distances. Berlin, Germany: Heidelberg, 2009.
DOUGHERTY, G. Pattern Recognition and Classification: An Introduction. 2013. ed.
[S.l.]: Springer, 2012.
GILLMEISTER, P. R. G.; CAZELLA, S. C. Uma análise comparativa de algoritmos
de regras de associação: minerando dados da indústria automotiva. Rio Grande do
Sul: Unisinos, 2007.
SOUZA, A. M. da C. Uma nova arquitetura para internet das coisas com análise e
reconhecimento de padrões e processamento com big data. 2015. Tese (Doutorado
em Sistemas Eletrônicos) - Escola Politécnica da Universidade de São Paulo, São Paulo,
2015. Disponível em: <http://www.teses.usp.br/teses/disponiveis/3/3142/tde-
20062016-105809>. Acesso em: 7 mar. 2017.
THEODORIDIS, S.; KOUTROUMBAS, K. Pattern recognition 4th ed. [S.l.]: Academic
Press, 2008.
ZAKI, M. J.; MEIRA JR. W. Data mining and analysis: fundamental concepts and
algorithms. New York: Cambridge University, 2014. Disponível em: <http://www.
dataminingbook.info/pmwiki.php/Main/BookPathUploads?action=downloadman&up
name=book-20160121.pdf>. Acesso em: 7 mar. 2017.
18