teorico_I

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