Baixe o app para aproveitar ainda mais
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
Compartilhar