Classificação de clientes com aprendizagem automática

Adriana Loureiro Vilas Boas Lopes Classificação de clientes com aprendizagem automática março de 2021 UMinho | 2021 Adriana Lopes Classificação de clientes com aprendizagem automática Universidade do Minho Escola de Ciências Adriana Loureiro Vilas Boas Lopes Classificação de clientes com aprendizagem automática Dissertação de Mestrado em Matemática e Computação Trabalho efetuado sob a orientação do Professor Doutor Stéphane Louis Clain e do Professor Doutor Gaspar José Machado Universidade do Minho Escola de Ciências março de 2021 Direitos de Autor e Condições de Utilização do Trabalho por Terceiros Este é um trabalho académico que pode ser utilizado por terceiros desde que respeitadas as regras e boas práticas internacionalmente aceites, no que concerne aos direitos de autor e direitos conexos. Assim, o presente trabalho pode ser utilizado nos termos previstos na licença abaixo indicada. Caso o utilizador necessite de permissão para poder fazer um uso do trabalho em condições não previstas no licenciamento indicado, deverá contactar o autor, através do RepositóriUM da Universidade do Minho. Licença concedida aos utilizadores deste trabalho Atribuição CC BY http://creativecommons.org/licenses/by/4.0/ i Agradecimentos Embora este seja um trabalho individual feito por mim, por trás houve várias pessoas envolvidas que tornaram possível este feito. Esta dissertação acaba por ser fruto de um grande trabalho de equipa. Em primeiro lugar queria agradecer aos meus dois orientadores, Doutor Stéphane Louis Clain e Doutor Gaspar José Machado, por todo o apoio e ajuda que me deram, pela grande disponibilidade que sempre tiveram e por todo o incentivo e partilha de conhecimento. Quero também agradecer à empresa Yarilabs por tornar possível este projeto, ao seu representante Emanuel Mota e ao meu tutor da empresa Rui Fonseca que também estiveram sempre disponíveis para me ajudar e me proporcionaram as condições para a realização deste trabalho. Por fim, mas não menos importante, quero agradecer à minha família, ao meu namorado e aos meus amigos que me foram acompanhando durante o meu percurso académico. ii Declaração de Integridade Declaro ter actuado com integridade na elaboração do presente trabalho académico e confirmo que não recorri à prática de plágio nem a qualquer forma de utilização indevida ou falsificação de informações ou resultados em nenhuma das etapas conducente à sua elaboração. Mais declaro que conheço e que respeitei o Código de Conduta Ética da Universidade do Minho. iii Resumo As empresas querem obter informações sobre os seus clientes através das suas bases de dados que sejam vantajosas para o negócio. Um processo de o fazer é recorrer a técnicas de inteligência artificial. Neste trabalho o foco é a utilização de técnica de clustering, um método de aprendizagem automática não supervisionado, e a sua aplicação a uma base de dados específica, passando primeiro por bases de dados criadas artificialmente. Foram propostas diversas métricas adequadas ao contexto da empresa de café Pact Coffee inicialmente avaliadas em bases de dados sintéticas simples, aplicando-se o clustering hierárquico. Inseriu-se a questão temporal, ou seja, em vez de se aplicar o clustering para a base de dados inteira, primeiro dividiu-se esta por faixas de tempo e só depois se aplicou o clustering para cada uma. Depois criou-se uma continuidade entre as faixas, e identificaram-se trajetórias e clientes ao longo do tempo. Os dados sintéticos começaram então a obter resultados favoráveis e por isso aplicouse o mesmo método aos dados reais da empresa Pact Coffee. Palavras chave: Aprendizagem automática, Métricas , Clustering Hierárquico, Cluster dinâmico, Streaming Data. iv Abstract Companies want to obtain information about their customers through their databases that are beneficial to the business. One solution is to use artificial intelligence, which is what I intend to do. In this work the focus is on the use of clustering techniques, an unsupervised machine learning method, and its application to a specific database, passing first through artificially created databases. Several metrics were proposed, appropriate to the context of the coffee company Pact Coffee, which were evaluated using simple synthetic databases, applying hierarchical clustering. The time issue was inserted, that is, instead of applying the clustering to the entire database, it was first divided into time bands and only then was clustering applied to each one. Then there was a continuity between the bands, and trajectories and customers were identified over time. The synthetic data then began to obtain favorable results and therefore the same method was applied to the real data of the company Pact Coffee. Keywords: Machine learning, Metrics, Hierarchical clustering, Dinamic cluster, Streaming Data. v Conteúdo Direitos de Autor e Condições de Utilização do Trabalho por Terceiros i Agradecimentos ii Declaração de Integridade iii Resumo iv Abstract v Lista de Figuras ix Lista de Tabelas xvi 1 Introdução 1 1.1 Motivação do trabalho desenvolvido . . . . . . . . . . . . . . . . . . 1 1.2 AempresaYarilabs.......................... 2 1.3 Estrutura da dissertação . . . . . . . . . . . . . . . . . . . . . . . 3 2 Similaridade e Dissimilaridade 4 2.1 Definições .............................. 4 2.2 Métricas para dados numéricos . . . . . . . . . . . . . . . . . . . . 5 2.3 Métricas para dados nominativos . . . . . . . . . . . . . . . . . . . 6 vi 5.53 Exemplo 5 — Agglomerative Clustering com distância de Manhattan. 76 5.54 Exemplo 5 — Agglomerative Clustering com distância de Manhattan esingle linkage. .......................... 77 5.55 Exemplo 5 — Agglomerative Clustering com distância de Manhattan ecomplete linkage: 3 clusters. .................. 78 5.56 Exemplo 5 — Agglomerative Clustering com distância de Manhattan eaverage linkage. ......................... 79 5.57 Exemplo 5 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço. . . . . . . . . . . . . . . . . . . . . 80 5.58 Exemplo 5 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e single linkage: 2 clusters. . . . . . 81 5.59 Exemplo 5 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e complete linkage.......... 82 5.60 Exemplo 5 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e average linkage........... 83 5.61 Exemplo 5 — Agglomerative Clustering com a primeira tentativa de métrica. ............................... 84 5.62 Exemplo 5 — Agglomerative Clustering com a primeira tentativa de métrica e single linkage: 2 clusters. ................ 85 5.63 Exemplo 5 — Agglomerative Clustering com a primeira tentativa de métrica e complete linkage. .................... 86 5.64 Exemplo 5 — Agglomerative Clustering com a primeira tentativa de métrica e average linkage. ..................... 87 6.1 Faixas de divisão ao longo do atributo do tempo t............ 90 6.2 Elementos do exemplo 1. . . . . . . . . . . . . . . . . . . . . . . . 92 6.3 Trajetória dos clusters (single linkage) — exemplo 1. . . . . . . . . 93 6.4 Trajetória dos clusters (complete linkage) — exemplo 1. . . . . . . 94 xiii 6.5 Trajetória dos clusters (average linkage) — exemplo 1. . . . . . . . 94 6.6 Elementos do exemplo 2. . . . . . . . . . . . . . . . . . . . . . . . 95 6.7 Trajetória dos clusters (single linkage) — exemplo 2. . . . . . . . . 96 6.8 Trajetória dos clusters (complete linkage) — exemplo 2. . . . . . . 97 6.9 Trajetória dos clusters (average linkage) — exemplo 2. . . . . . . . 97 6.10 Elementos do exemplo 3. . . . . . . . . . . . . . . . . . . . . . . . 99 6.11 Trajetória dos clusters (single linkage) — exemplo 3. . . . . . . . . 99 6.12 Trajetória dos clusters (complete linkage 1ª versão) — exemplo 3. . 100 6.13 Trajetória dos clusters (complete linkage 2ª versão) — exemplo 3. . 101 6.14 Trajetória dos clusters (average linkage 1ª versão) — exemplo 3. . . 102 6.15 Trajetória dos clusters (average linkage 2ª versão) — exemplo 3. . . 102 6.16 Elementos do exemplo 4. . . . . . . . . . . . . . . . . . . . . . . . 104 6.17 Trajetória dos clusters (single linkage) — exemplo 4. . . . . . . . . 104 6.18 Trajetória dos clusters (complete linkage) — exemplo 4. . . . . . . 105 6.19 Trajetória dos clusters (average linkage) — exemplo 4. . . . . . . . 106 6.20 Elementos do exemplo 5. . . . . . . . . . . . . . . . . . . . . . . . 107 6.21 Trajetória dos clusters (single linkage) — exemplo 5. . . . . . . . . 108 6.22 Trajetória dos clusters (complete linkage) — exemplo 5. . . . . . . 109 6.23 Trajetória dos clusters (average linkage) — exemplo 5. . . . . . . . 110 6.24 Elementos do exemplo 6. . . . . . . . . . . . . . . . . . . . . . . . 111 6.25 Trajetória dos clusters (single linkage) — exemplo 6. . . . . . . . . 112 6.26 Trajetória dos clusters (complete linkage) — exemplo 6. . . . . . . 113 6.27 Trajetória dos clusters (average linkage) — exemplo 6. . . . . . . . 113 6.28 Elementos do exemplo 7. . . . . . . . . . . . . . . . . . . . . . . . 115 6.29 Trajetória dos clusters (single linkage) — exemplo 7. . . . . . . . . 116 6.30 Trajetória dos clusters (complete linkage) — exemplo 7. . . . . . . 116 6.31 Trajetória dos clusters (average linkage) — exemplo 7. . . . . . . . 117 xiv 6.32 Elementos do exemplo 8. . . . . . . . . . . . . . . . . . . . . . . . 118 6.33 Trajetória dos clusters (single linkage) — exemplo 8. . . . . . . . . 119 6.34 Trajetória dos clusters (complete linkage) — exemplo 8. . . . . . . 120 6.35 Trajetória dos clusters (average linkage) — exemplo 8. . . . . . . . 120 6.36 Elementos do exemplo 9. . . . . . . . . . . . . . . . . . . . . . . . 122 6.37 Trajetória dos clusters (single linkage) — exemplo 9. . . . . . . . . 123 6.38 Trajetória dos clusters (complete linkage 1ª versão) — exemplo 9. . 124 6.39 Trajetória dos clusters (complete linkage 2ª versão) — exemplo 9. . 125 6.40 Trajetória dos clusters (average linkage) — exemplo 9. . . . . . . . 126 6.41 Elementos do exemplo 10. . . . . . . . . . . . . . . . . . . . . . . 128 6.42 Trajetória dos clusters (single linkage) — exemplo 10. . . . . . . . . 129 6.43 trajetória dos clusters (complete linkage) — exemplo 10. . . . . . . 130 6.44 Trajetória dos clusters (average linkage) — exemplo 10. . . . . . . 130 6.45 Dendrogramas das faixas F5 2eF3(single linkage) — exemplo 1. . . 135 6.46 Trajetória dos clusters (single linkage) — exemplo 1. . . . . . . . . 136 6.47 Trajetória dos clusters (single linkage) — exemplo 5. . . . . . . . . 137 6.48 Trajetória dos clusters (single linkage) — exemplo 6. . . . . . . . . 137 7.1 Trajetórias dos clusters ao longo das faixas — primeiro benchmark. . 146 7.2 Trajetórias dos clusters ao longo das faixas — segundo benchmark. . 152 xv Lista de Tabelas 3.1 M(P(0))............................... 12 3.2 M(P(1))............................... 13 3.3 M(P(2))............................... 13 3.4 M(P(3))............................... 14 4.1 Basededados............................. 19 4.2 Matriz de dissimilaridade usando a nova métrica. . . . . . . . . . . . 20 5.1 Exemplo — métricas de qualidade com Ketiquetas.......... 24 5.2 Exemplo 1 — Agglomerative Clustering com distância de Manhattan ecomplete linkage: métricas de qualidade com Kclusters. . . . . 26 5.3 Exemplo 1 — Agglomerative Clustering com distância de Manhattan eaverage linkage: métricas de qualidade com Kclusters. . . . . . 27 5.4 Exemplo 1 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e single linkage: métricas de qualidade com Kclusters............................ 30 5.5 Exemplo 1 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e complete linkage: métricas de qualidade com Kclusters....................... 30 xvi 5.6 Exemplo 1 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e average linkage: métricas de qualidade com Kclusters....................... 31 5.7 Exemplo 1 — Agglomerative Clustering com a primeira tentativa de métrica e single linkage: métricas de qualidade com Kclusters. . . 33 5.8 Exemplo 1 — Agglomerative Clustering com a primeira tentativa de métrica e complete linkage: métricas de qualidade com Kclusters. 34 5.9 Exemplo 1 — Agglomerative Clustering com a primeira tentativa de métrica e average linkage: métricas de qualidade com Kclusters. . 35 5.10 Exemplo 2 — Agglomerative Clustering com distância de Manhattan esingle linkage: métricas de qualidade com Kclusters. ...... 38 5.11 Exemplo 2 — Agglomerative Clustering com distância de Manhattan ecomplete linkage: métricas de qualidade com Kclusters. . . . . 39 5.12 Exemplo 2 — Agglomerative Clustering com distância de Manhattan eaverage linkage: métricas de qualidade com Kclusters. . . . . 40 5.13 Exemplo 2 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e single linkage: métricas de qualidade com Kclusters............................ 42 5.14 Exemplo 2 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e complete linkage: métricas de qualidade com Kclusters....................... 43 5.15 Exemplo 2 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e average linkage: métricas de qualidade com Kclusters....................... 43 5.16 Exemplo 2 — Agglomerative Clustering com a primeira tentativa de métrica e single linkage: métricas de qualidade com Kclusters. . . 46 xvii 5.17 Exemplo 2 — Agglomerative Clustering com a primeira tentativa de métrica e complete linkage: métricas de qualidade com Kclusters. 47 5.18 Exemplo 2 — Agglomerative Clustering com a primeira tentativa de métrica e average linkage: métricas de qualidade com Kclusters. . 48 5.19 Exemplo 3 — Agglomerative Clustering com distância de Manhattan esingle linkage: métricas de qualidade com Kclusters. ...... 51 5.20 Exemplo 3 — Agglomerative Clustering com distância de Manhattan ecomplete linkage: métricas de qualidade com Kclusters. . . . . 52 5.21 Exemplo 3 — Agglomerative Clustering com distância de Manhattan eaverage linkage: métricas de qualidade com Kclusters. . . . . 53 5.22 Exemplo 3 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e single linkage: métricas de qualidade com Kclusters............................ 55 5.23 Exemplo 3 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e complete linkage: métricas de qualidade com Kclusters....................... 56 5.24 Exemplo 3 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e average linkage: métricas de qualidade com Kclusters....................... 57 5.25 Exemplo 3 — Agglomerative Clustering com a primeira tentativa de métrica e single linkage: métricas de qualidade com Kclusters. . . 59 5.26 Exemplo 3 — Agglomerative Clustering com a primeira tentativa de métrica e complete linkage: métricas de qualidade com Kclusters. 60 5.27 Exemplo 3 — Agglomerative Clustering com a primeira tentativa de métrica e average linkage: métricas de qualidade com Kclusters. . 60 5.28 Exemplo 4 — Agglomerative Clustering com distância de Manhattan esingle linkage: métricas de qualidade com Kclusters. ...... 64 xviii 5.29 Exemplo 4 — Agglomerative Clustering com distância de Manhattan ecomplete linkage: métricas de qualidade com Kclusters. . . . . 65 5.30 Exemplo 4 — Agglomerative Clustering com distância de Manhattan eaverage linkage: métricas de qualidade com Kclusters. . . . . . 66 5.31 Exemplo 4 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e single linkage: métricas de qualidade com Kclusters............................ 68 5.32 Exemplo 4 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e complete linkage: métricas de qualidade com Kclusters....................... 68 5.33 Exemplo 4 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e average linkage: métricas de qualidade com Kclusters....................... 69 5.34 Exemplo 4 — Agglomerative Clustering com a primeira tentativa de métrica e single linkage: métricas de qualidade com Kclusters. . . 71 5.35 Exemplo 4 — Agglomerative Clustering com a primeira tentativa de métrica e complete linkage: métricas de qualidade com Kclusters. 72 5.36 Exemplo 4 — Agglomerative Clustering com a primeira tentativa de métrica e average linkage: métricas de qualidade com Kclusters. . 73 5.37 Exemplo 5 — Agglomerative Clustering com distância de Manhattan esingle linkage: métricas de qualidade com Kclusters. ...... 77 5.38 Exemplo 5 — Agglomerative Clustering com distância de Manhattan ecomplete linkage: métricas de qualidade com Kclusters. . . . . 78 5.39 Exemplo 5 — Agglomerative Clustering com distância de Manhattan eaverage linkage: métricas de qualidade com Kclusters. . . . . 78 xix 5.40 Exemplo 5 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e single linkage: métricas de qualidade com Kclusters............................ 80 5.41 Exemplo 5 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e complete linkage: métricas de qualidade com Kclusters....................... 81 5.42 Exemplo 5 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e average linkage: métricas de qualidade com Kclusters....................... 82 5.43 Exemplo 5 — Agglomerative Clustering com a primeira tentativa de métrica e single linkage: métricas de qualidade com Kclusters. . . 85 5.44 Exemplo 5 — Agglomerative Clustering com a primeira tentativa de métrica e complete linkage: métricas de qualidade com Kclusters. 85 5.45 Exemplo 5 — Agglomerative Clustering com a primeira tentativa de métrica e average linkage: métricas de qualidade com Kclusters. . 86 6.1 Tabela de intersecção entre duas faixas. . . . . . . . . . . . . . . . . 91 6.2 Correspondência dos clusters (single linkage) — exemplo 1. . . . . . 93 6.3 Correspondência dos clusters (complete linkage) — exemplo 1. . . . 93 6.4 Correspondência dos clusters (average linkage) — exemplo 1. . . . 94 6.5 Correspondência dos clusters (single linkage) — exemplo 2. . . . . . 96 6.6 Correspondência dos clusters (complete linkage) — exemplo 2. . . . 96 6.7 Correspondência dos clusters (average linkage) — exemplo 2. . . . 97 6.8 Correspondência dos clusters (single linkage) — exemplo 3. . . . . . 99 6.9 Correspondência dos clusters (complete linkage 1ª versão) — exemplo3.................................. 100 6.10 Correspondência dos clusters (complete linkage 2ª versão) — exemplo3.................................. 100 xx 6.11 Correspondência dos clusters (average linkage 1ª versão) — exemplo 3.101 6.12 Correspondência dos clusters (average linkage 2ª versão) — exemplo 3.102 6.13 Correspondência dos clusters (single linkage) — exemplo 4. . . . . . 104 6.14 Correspondência dos clusters (complete linkage) — exemplo 4. . . . 105 6.15 Correspondência dos clusters (average linkage) — exemplo 4. . . . 105 6.16 Correspondência dos clusters (single linkage) — exemplo 5. . . . . . 108 6.17 Correspondência dos clusters (complete linkage) — exemplo 5. . . . 109 6.18 Correspondência dos clusters (average linkage) — exemplo 5. . . . 109 6.19 Correspondência dos clusters (single linkage) — exemplo 6. . . . . . 112 6.20 Correspondência dos clusters (complete linkage) — exemplo 6. . . . 112 6.21 Correspondência dos clusters (average linkage) — exemplo 6. . . . 113 6.22 Correspondência dos clusters (single linkage) — exemplo 7. . . . . . 115 6.23 Correspondência dos clusters (complete linkage) — exemplo 7. . . . 116 6.24 Correspondência dos clusters (average linkage) — exemplo 7. . . . 117 6.25 Correspondência dos clusters (single linkage) — exemplo 8. . . . . . 119 6.26 Correspondência dos clusters (complete linkage) — exemplo 8. . . . 119 6.27 Correspondência dos clusters (average linkage) — exemplo 8. . . . 120 6.28 Correspondência dos clusters (single linkage) — exemplo 9. . . . . . 122 6.29 Correspondência dos clusters (complete linkage 1ª versão) — exemplo9.................................. 124 6.30 Correspondência dos clusters (complete linkage 2ª versão) — exemplo9.................................. 125 6.31 Correspondência dos clusters (average linkage) — exemplo 9. . . . 126 6.32 Correspondência dos clusters (single linkage) — exemplo 10. . . . . 129 6.33 Tabela de critérios para escolha do número de clusters da faixa F5 2 (single linkage)—exemplo1. .................... 134 xxi 6.34 Tabela de critérios para escolha do número de clusters da faixa F3 (single linkage)—exemplo1. .................... 135 7.1 Percentagem aproximada de elementos de cada valor de cada atributo. 140 7.2 Representantes de cada trajetória — primeiro benchmark. . . . . . . 147 7.3 Compras de 5 clientes — primeiro benchmark............. 149 7.4 Representantes de cada trajetória — segundo benchmark. ...... 153 7.5 Compras de 5 clientes — segundo benchmark............. 155 xxii A=A1×A2× · · · × AI, em que Ai,i= 1, . . . , I, são conjuntos de dados nominativos (por exemplo, A1={vermelho,azul,branco},A2={vaca,gato},A3= {grande,médio,pequeno}). Sejam, então, x= (x1, . . . , xI)Tex0= (x0 1, . . . , x0 I)T dois elementos de A. A Distância de Hamming (ou Matching Distance) é dada por d(x, x0) = 1 I I X i=1 di(x, x0), em que di(x, x0) =      1se xi6=x0 i, 0caso contrário. Uma variante é considerar novamente métricas ponderadas usando o cardinal de cada atributo (i.e. o número de valores possíveis para cada atributo), como por exemplo d(x, x0) = 1 I I X i=1 ωidi(x, x0), onde ωi=|Ai|ou ωi= 1/|Ai|. 7 Capítulo 3 Partição e Clustering Seja dada uma base de dados constituída por eventos não rotulados em que se pretende determinar uma sua partição por forma a que os elementos dos elementos da partição sejam similares entre si mas dissimilares em relação aos elementos dos outros elementos da partição. Ao processo de criar a partição de uma base de dados chama-se clustering e aos elementos da partição (subconjuntos da base de dados) chama-se clusters. Formalmente, dada uma base de dados D, pretende-se criar uma sua partição com K(∈N)elementos, ou seja, P={C1, . . . , CK}tal que D= K [ k=1 Ck e Ck∩Ck0=∅,com k, k0= 1, . . . , K, k 6=k0. Existem muitas técnicas para a construção dos clusters, seguindo cada metodologia o seu conjunto de regras para definir a semelhança entre os elementos da base de dados. Dois dos grandes grupos de algoritmos de clustering são os algoritmos particionais e os algoritmos hierárquicos, que se introduzem nas duas secções seguintes. 8 3.1 Algoritmos particionais Os algoritmos particionais baseiam-se no que hoje em dia se chama “Algoritmo de Lloyd” e que foi introduzido em 1957 por Stuart P. Lloyd mas apenas publicado em 1982 [6]. O algoritmo de Lloyd, que surgiu no contexto da modulação por códigos de pulso, tinha por objetivo determinar um conjunto finito de valores que representam um domínio contínuo de valores. Como técnica de clustering, o algoritmo de Lloyd consiste em, dada uma base de dados De um conjunto M(0) = {m1, . . . , mK}com K(∈N)elementos do espaço dos atributos, aplicar iterativamente os seguintes dois passos até se atingir a convergência: Passo 1 —assignment (atribuição): determinar os Kclusters associados a M M(t) = {m1, . . . , mK} → P(t+ 1) = {C1, . . . , CK} Passo 2 — atualização: determinar os Knovos representantes associados a P P(t+ 1) = {C1, . . . , CK} → M(t+ 1) = {m1, . . . , mK} O algoritmo K-means, termo introduzido por James MacQueen em 1967 [7] é o mais conhecido algoritmo de clustering que se baseia no Algoritmo de Lloyd. O objetivo do Kmeans é minimizar a distância a que se encontram os pontos de um cluster do centróide desse cluster. O algoritmo é dado por: Passo 0 — inicialização D= (xn)N n=1, xn∈ A =RI:base de dados K∈N:número de clusters M(0) ← {m1, . . . , mk, . . . , mK}:Kpontos distintos de A d:dissemelhança (usualmente a distância euclidiana ou de Manhattan) t←0 9 Passo 1 —assignment M(t) = {m1, . . . , mk, . . . , mK} → P(t+ 1) = {C1, . . . , Ck, . . . , CK} Ck← {xn∈D:d(xn, mk)≤d(xn, mj), j ∈ {1, . . . , k −1, k + 1, . . . , K}} Passo 2 — atualização dos representantes P(t+ 1) = {C1, . . . , Ck, . . . , CK} → M(t+ 1) = {m1, . . . , mk, . . . , mK} mk←1 |Ck|X x∈Ck x Passo 3 — fim? terminar se P(t+ 1) = P(t) caso contrário, t←t+ 1 e regressar ao Passo 1 Num algoritmo de Loyd, o valor de Ké um meta-parâmetro indicado pelo utilizador, colocando-se a questão de se saber qual o seu melhor valor. A estratégia é quantificar a qualidade do clustering para cada valor de Kcom uma função de custo E(K). Obtémse, assim, uma curva K→E(K)que permite determinar o valor ótimo de K. 3.2 Algoritmos hierárquicos Os algoritmos hierárquicos, ao contrário dos particionais, não assumem um número pré-definido de clusters mas antes consideram uma estrutura hierárquica de partições tomando como ponto de partida um dos dois casos extremos: uma partição com tantos elementos quantos os elementos da base de dados nos chamados algoritmos hierárquicos aglomerativos, ou uma partição com um único elemento que é a própria base de dados nos chamados algoritmos hierárquicos divisivos. Além do mais, os algoritmos hierárquicos não precisam necessariamente de um representante dos clusters. Apenas algumas situações, tais como a utilização dos centróides para avaliar a distância entre clusters, pode 10 requerer um representante. Os algoritmos hierárquicos aglomerativos, mais eficientes que os algoritmos hierárquicos divisivos, vão ser os considerados neste trabalho. Um algoritmo hierárquico aglomerativo, dada uma base de dados D= (xn)N n=1 e uma dissemelhança d, considera P={C1, . . . , Cn, . . . , CN},Cn={xn}, como a partição inicial (cada evento da base de dados constitui um cluster), e repete os seguintes dois passos até existir um único cluster: Passo 1 — calcular todas as distâncias inter-clusters (matriz de distâncias) Passo 2 — agrupar os dois clusters cuja distância inter-clusters é menor Para calcular a distância entre dois clusters CeC0, operação necessária para calcular as distâncias inter-clusters no Passo 1 do algoritmo, irão ser consideradas neste trabalho as seguintes estratégias: •single linkage — a distância entre os clusters é dada pela distância dos dois elementos mais próximos dos dois clusters, ou seja, d(C, C0) = min x∈C,x0∈C0d(x, x0). •complete linkage — a distância entre os clusters é dada pela distância dos dois elementos mais afastados dos dois clusters, ou seja, d(C, C0) = max x∈C,x0∈C0d(x, x0). •average linkage — a distância entre os clusters é dada pela média das distâncias entre todos os pares dos dois clusters, ou seja, d(C, C0) = 1 |C||C0|X x∈CX x∈C0 d(x, x0). Para ilustrar o algoritmo, considere-se a base de dados com espaço de atributos A= R2dada por D=(0,1),(2,0),(1,2),(2,0.5),(1,2.75). 11 Consideremos da distância de Manhattan sendo a entrada (`, c)da matriz de dissimilaridade dada por M[`, c] = d(x`, xc)e o método Single linkage para calcular a dissimilaridade entre os clusters, i.e. seleciona-se o menor valor, que vamos denotar por Ee que representa a “energia de associação” para agrupar dois clusters na partição. •A partição inicial é P(0) = {x1},{x2},{x3},{x4},{x5}e a matriz de distâncias está representada na Tabela 3.1. Como a menor dissimilaridade é o valor da entrada (4,2), que é a distância entre o cluster {x2}e o cluster {x4}, tem-se que E= 0.5e o próximo passo é juntar estes dois clusters num único. Assim, a nova partição é dada por P(1) = {x1},{x2, x4},{x3},{x5}, com 4 clusters. Tabela 3.1: M(P(0)). x1x2x3x4x5 x10 3 2 2.5 2.75 x23 0 3 0.5 3.75 x32 3 0 2.5 0.75 x42.5 0.5 2.5 0 3.25 x52.75 3.75 0.75 3.25 0 •Recalcula-se a matriz, desta vez, associada à partição P(1). Para tal, quando se calcula a distância do cluster {x1}com o novo cluster {x2, x4}, tem de se seleccionar o min(d({x1},{x2}), d({x1},{x4})). O mesmo acontece, para calcular a distância entre os restantes clusters e o cluster {x2, x4}, obtendo-se a matriz de distâncias dada na Tabela 3.2. Atendendo a que E= 0.75, que é a distância entre os clusters {x3}e{x5}, estes dois clusters vão-se fundir num só cluster. Obtém-se assim, uma nova partição P(2) = {x1},{x2, x4},{x3, x5}. 12 Tabela 3.2: M(P(1)). x1x2, x4x3x5 x10 2.5 2 2.75 x2, x42.5 0 2.5 3.25 x32 2.5 0 0.75 x52.75 3.25 0.75 0 •A matriz das distâncias M(P(2)) associada à partição P(2) está representada na Tabela 3.3. Agora, tem-se E= 2, que é a distância entre os clusters {x1}e {x3, x5}, obtendo-se a partição P(3) = {x2, x4},{x1, x3, x5}. Tabela 3.3: M(P(2)). x1x2, x4x3, x5 x10 2.5 2 x2, x42.5 0 2.5 x3, x52 2.5 0 •Por fim, a matriz das distâncias M(P(3)) associada à partição P(3) está representada na Tabela 3.4. Assim, E= 2.5e já só resta um passo, que é juntar os dois clusters existentes, {x2, x4}e{x1, x3, x5}, obtendo-se assim a partição final que é constituída apenas por um cluster que inclui todos os pontos de D, P(4) = {x1, x2, x3, x4, x5}. 13 Tabela 3.4: M(P(3)). x2, x4x1, x3, x5 x2, x40 2.5 x1, x3, x52.5 0 Construídas todas as partições e as respectivas distâncias inter-clusters (energias de associação), através de uma curva que relaciona o número de clusters de cada partição e a sua energia de associação, é possível escolher o número de clusters ideal, visualizando nesta curva qual o ponto em que há uma subida mais abrupta tendo em consideração as variações da curva. Na Figura 3.1 apresentam-se as curvas de associação quando se considera o método Single linkage,Complete linkage eAverage linkage, a partir das quais se poderá concluir que o número ideal de clusters será 3. 12345 0 1 2 3 4 K E 12345 0 1 2 3 4 K E 12345 0 1 2 3 4 K E Figura 3.1: Curva de associação do clustering hierárquico para Single linkage (esquerda), Complete linkage (centro) e Average linkage (direita). 3.3 Avaliação da qualidade dos clusters Perante a necessidade de avaliar a qualidade dos clusters que se podem construir para uma certa base de dados, recorre-se ao uso de métricas de avaliação. Uma delas é a Inércia, que calcula a soma das distâncias que estão os pontos de um cluster ao 14 centróide desse mesmo cluster, ou seja, avalia a “distância intra-cluster”, que deve ser o mais baixa possível. Outra métrica é o Índice de Dunn, que para além de garantir o mesmo que a Inércia, assegura também que clusters distintos sejam tão diferentes um dos outros quanto possível. Assim, avalia-se a “distância inter-cluster” para além da “distância intra-cluster”. Este índice deve ser o mais alto possível, sendo a sua expressão dada por Índice de Dunn =min(distância inter-cluster) max(distância intra-cluster). Na caracterização da qualidade de um processo de clustering pode também contar o número de clusterscomo elemento de penalização. Por exemplo, se P={C1, . . . , CK} é uma partição da base de dados, considera-se a função custo E(P) = aKα+ K X k=1 V(Ck), onde a variância de um cluster é dada por V(Ck) = 1 |Ck|X x∈Ck kx−¯xk2 com ¯xa média dos elementos de Ckeaeαparâmetros do modelo. 15 Capítulo 4 Métrica de atributos temporais A componente temporal dos dados tem um papel diferente dos outros atributos e deve ser quantificada de uma maneira especifica. Assim, seja x= (id, t, y)um evento, onde id é a identificação do cliente que realizou esse evento, té a data em que o realizou e yrepresenta todos os outros atributos associados a este evento. Para a construção dos clusters irá ser preciso apenas considerar o par (t, y), ficando o atributo id de fora, ou seja, não contará como atributo. Uma métrica temporal separa o tempo tdos restantes atributos yintroduzindo uma ponderação dependente de t. Na literatura já existem algumas métricas que diferenciam o tempo dos outros atributos. Por exemplo, no modelo de janela amortecida, os atributos de um evento são afetados por um coeficiente que depende do tempo em que este ocorreu relativamente a um tempo referencial dado. Assim, quando um elemento é acrescentado à base dados é lhe atribuído o maior peso possível, sendo que esse peso diminui através de “funções de envelhecimento”, como por exemplo a função de decaimento exponencial f(t) = 2−λ|t−tr|, onde λé o factor de envelhecimento e tré o tempo de referência. Este modelo de janela amortecida não descarta completamente os elementos, simplesmente considera que os 16 •Precision: Diz o quão preciso é o modelo em relação aos dados previstos comparandoos com os dados inseridos, ou seja, compara todos os elementos de Pe vê se a sua etiqueta corresponde à etiqueta do mesmo elemento em Pex. Esta métrica é calculada para todas as diferentes etiquetas que existam na partição. •Recall: Diz quantas etiquetas reais o modelo encontrou, ou seja, compara todos os elementos de Pex e vê se a sua etiqueta corresponde à etiqueta do mesmo elemento na partição P. Esta métrica é calculada para todas as diferentes etiquetas que existam na partição. •Accuracy: Esta métrica ao contrário das outras duas, é feita para o resultado geral do modelo, e não para cada etiqueta. Basicamente, a accuracy calcula a percentagem de etiquetas que o modelo previu correctamente. Considere-se de seguida um pequeno exemplo para ajudar a entender estas métricas. Seja D={x1, x2, x3, x4, x5}uma base de dados e E= [0,1,2,2,2] as etiquetas associadas a cada elemento de D. Aplicou-se o clustering hierárquico aglomerativo e obteve-se um novo conjunto de etiquetas E0= [0,0,2,2,1]. Na Tabela 5.1 apresentamse os valores das três métricas de qualidade. Aprecision da etiqueta 0 é de 50% pois em Eapenas o elemento x1tem etiqueta 0, mas o modelo previu que tanto o elemento x1como o x2tem etiqueta 0, ou seja, dos elementos com etiqueta 0 que o modelo previu, apenas metade tem mesmo a etiqueta 0. Já em relação ao recall, todos os elementos que tinham realmente a etiqueta 0 (no caso apenas o x1), o modelo previu correctamente a etiqueta. Enquanto por exemplo em relação à etiqueta 2, havia 3 elementos, e o modelo previu apenas 2 deles, daí o recall ser apenas de 67%. A accuracy é de 60% porque o modelo apenas acertou 3 de 5 elementos. 23 Tabela 5.1: Exemplo — métricas de qualidade com Ketiquetas. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 3 0.60 0.50 1.00 0.00 0.00 1.00 0.67 5.3 Exemplo 1 5.3.1 Construção da base de dados A base de dados é constituída por 100 elementos e 3 clusters com 18, 40 e 42 elementos, respetivamente, cada um da forma (y1, y2, t). Os pontos de cada cluster pertencem a paralelepípedos que não se intersectam seguindo as seguintes leis probabilísticas uniformes: •cluster 1: y1∼U([0.1,0.3]),y2∼U([0.6,0.8]),t∼U([0,3]). •cluster 2: y1∼U([0.1,0.4]),y2∼U([0.05,0.4]),t∼U([0,3]). •cluster 3: y1∼U([0.6,0.9]),y2∼U([0.1,0.7]),t∼U([0,3]). Representa-se na Figura 5.1 a base de dados do Exemplo 1. Figura 5.1: Exemplo 1 — visualização 2D e 3D dos dados. 24 5.3.2 Clustering hierárquico com distância de Manhattan Apresentam-se os resultados para este exemplo nas Figuras 5.2, 5.3 e 5.4, e nas Tabelas 5.2 e 5.3. (a) Single linkage — curva do cotovelo (b) Single linkage — dendrograma (c) Complete linkage — curva do cotovelo (d) Complete linkage — dendrograma 25 (e) Average linkage — curva do cotovelo (f) Average linkage — dendrograma Figura 5.2: Exemplo 1 — Agglomerative Clustering com distância de Manhattan. Single linkage Quer considerando a curva do cotovelo, quer o dendrograma, não se consegue tirar grandes conclusões relativamente ao número ideal de clusters para o algoritmo. Complete linkage Quer considerando a curva do cotovelo, quer o dendrograma, K= 2 eK= 3 parecem ser os valores ideais para o número de clusters. Tabela 5.2: Exemplo 1 — Agglomerative Clustering com distância de Manhattan e complete linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 2 0.52 0.48 0.78 0.60 0.50 0.00 0.00 3 0.57 0.60 0.50 0.59 0.75 0.43 0.33 26 (a) 2 clusters (b) 3 clusters Figura 5.3: Exemplo 1 — Agglomerative Clustering com distância de Manhattan e complete linkage. Average linkage O número ideal será 2, no entanto, 3 também parece uma boa opção, pelo que se observa da curva do cotovelo e do dendrograma. Tabela 5.3: Exemplo 1 — Agglomerative Clustering com distância de Manhattan e average linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 2 0.46 0.44 0.78 0.52 0.36 0.00 0.00 3 0.51 0.53 0.68 0.52 0.36 0.45 0.50 27 (a) 2 clusters (b) 3 clusters Figura 5.4: Exemplo 1 — Agglomerative Clustering com distância de Manhattan e average linkage. Conclusão Neste caso verificou-se que o single linkage não permitiu retirar grandes conclusões. Nos outros dois métodos embora com 3 clusters aaccuracy seja ligeiramente melhor que usando 2, tanto um caso como o outro funciona bastante mal. 5.3.3 Clustering hierárquico com distância de Manhattan só para os atributos de espaço Apresentam-se os resultados para este exemplo nas Figuras 5.5, 5.6, 5.7 e 5.8, e nas Tabelas 5.4, 5.5 e 5.6. 28 (a) Single linkage — curva do cotovelo (b) Single linkage — dendrograma (c) Complete linkage — curva do cotovelo (d) Complete linkage — dendrograma (e) Average linkage — curva do cotovelo (f) Average linkage — dendrograma Figura 5.5: Exemplo 1 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço. 29 Single linkage. Pelo dendrograma e pela curva de cotovelo K= 3 é o número ideal de clusters. Tabela 5.4: Exemplo 1 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e single linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 3 1.00 1.00 1.00 1.00 1.00 1.00 1.00 Figura 5.6: Exemplo 1 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e single linkage: 3 clusters. Complete linkage Mais uma vez, K= 3 é o número ideal de clusters. Tabela 5.5: Exemplo 1 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e complete linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 3 1.00 1.00 1.00 1.00 1.00 1.00 1.00 30 Figura 5.7: Exemplo 1 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e complete linkage: 3 clusters. Average linkage K= 3 é o número ideal de clusters a ser usado. Tabela 5.6: Exemplo 1 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e average linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 3 1.00 1.00 1.00 1.00 1.00 1.00 1.00 Figura 5.8: Exemplo 1 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e average linkage: 3 clusters. 31 Conclusão Sem o atributo do tempo, o algoritmo consegue encontrar os clusters pretendidos. 5.3.4 Clustering hierárquico com a primeira tentativa de métrica Vai-se considerar para tempo de observação t= 3 eτ= 5. Apresentam-se os resultados para este exemplo nas Figuras 5.9, 5.10, 5.11 e 5.12, e nas Tabelas 5.7, 5.8 e 5.9. (a) Single linkage — curva do cotovelo (b) Single linkage — dendrograma (c) Complete linkage — curva do cotovelo (d) Complete linkage — dendrograma 32 Figura 5.15: Exemplo 2 — Agglomerative Clustering com distância de Manhattan e single linkage: 2 clusters. Complete linkage Considerando a curva do cotovelo e o dendrograma, K= 3 é o valor ideal para o número de clusters. Tabela 5.11: Exemplo 2 — Agglomerative Clustering com distância de Manhattan e complete linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 3 0.71 0.40 0.50 0.67 0.67 1.00 0.87 Figura 5.16: Exemplo 2 — Agglomerative Clustering com distância de Manhattan e complete linkage: 3 clusters. 39 Average linkage K= 2 parece uma boa opção, pelo que se observa da curva do cotovelo e do dendrograma. Tabela 5.12: Exemplo 2 — Agglomerative Clustering com distância de Manhattan e average linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 2 0.77 0.60 1.00 1.00 1.00 0.00 0.00 Figura 5.17: Exemplo 2 — Agglomerative Clustering com distância de Manhattan e average linkage: 2 clusters. Conclusão O modelo funciona mal nos três casos. 5.4.3 Clustering hierárquico com distância de Manhattan só para os atributos de espaço Apresentam-se os resultados para este exemplo nas Figuras 5.18, 5.19,5.20 e 5.21, e nas Tabelas 5.13, 5.14 e 5.15. 40 (a) Single linkage — curva do cotovelo (b) Single linkage — dendrograma (c) Complete linkage — curva do cotovelo (d) Complete linkage — dendrograma (e) Average linkage — curva do cotovelo (f) Average linkage — dendrograma Figura 5.18: Exemplo 2 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço. 41 Single linkage. Pelo dendrograma e pela curva de cotovelo tanto K= 2 como K= 3 podem ser o número ideal de clusters. Tabela 5.13: Exemplo 2 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e single linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 2 0.77 0.60 1.00 1.00 1.00 0.00 0.00 3 1.00 1.00 1.00 1.00 1.00 1.00 1.00 (a) 2 clusters (b) 3 clusters Figura 5.19: Exemplo 2 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e single linkage. Complete linkage Mais uma vez, tanto K= 2 como K= 3 são números ideais de clusters. 42 Tabela 5.14: Exemplo 2 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e complete linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 2 0.77 0.60 1.00 1.00 1.00 0.00 0.00 3 1.00 1.00 1.00 1.00 1.00 1.00 1.00 (a) 2 clusters (b) 3 clusters Figura 5.20: Exemplo 2 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e complete linkage. Average linkage K= 2 eK= 3 são um número ideal de clusters a ser usado. Tabela 5.15: Exemplo 2 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e average linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 2 0.77 0.60 1.00 1.00 1.00 0.00 0.00 3 1.00 1.00 1.00 1.00 1.00 1.00 1.00 43 (a) 2 clusters (b) 3 clusters Figura 5.21: Exemplo 2 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e average linkage. Conclusão Sem o atributo do tempo, o algoritmo consegue encontrar os clusters pretendidos, ao contrário de quando se utiliza o atributo t. 5.4.4 Clustering hierárquico com a primeira tentativa de métrica Vai-se considerar para tempo de observação t= 3 eτ= 5. Apresentam-se os resultados para este exemplo nas Figuras 5.22, 5.23,5.24 e 5.25, e nas Tabelas 5.16, 5.17 e 5.18. 44 (a) Single linkage — curva do cotovelo (b) Single linkage — dendrograma (c) Complete linkage — curva do cotovelo (d) Complete linkage — dendrograma (e) Average linkage — curva do cotovelo (f) Average linkage — dendrograma Figura 5.22: Exemplo 2 — Agglomerative Clustering com a primeira tentativa de métrica. 45 Single linkage O número ideal de clusters éK= 2 ou K= 3, pelo que se observa da curva do cotovelo e do dendrograma. Tabela 5.16: Exemplo 2 — Agglomerative Clustering com a primeira tentativa de métrica e single linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 2 0.77 0.60 1.00 1.00 1.00 0.00 0.00 3 1.00 1.00 1.00 1.00 1.00 1.00 1.00 (a) 2 clusters (b) 3 clusters Figura 5.23: Exemplo 2 — Agglomerative Clustering com a primeira tentativa de métrica esingle linkage. Complete linkage K= 2 eK= 3 parecem ser números ideais de clusters. 46 Tabela 5.17: Exemplo 2 — Agglomerative Clustering com a primeira tentativa de métrica e complete linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 2 0.77 0.60 1.00 1.00 1.00 0.00 0.00 3 1.00 1.00 1.00 1.00 1.00 1.00 1.00 (a) 2 clusters (b) 3 clusters Figura 5.24: Exemplo 2 — Agglomerative Clustering com a primeira tentativa de métrica ecomplete linkage. Average linkage Tanto K= 2 como K= 3 parecem ser um número ideal de clusters. 47 Tabela 5.18: Exemplo 2 — Agglomerative Clustering com a primeira tentativa de métrica e average linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 2 0.77 0.60 1.00 1.00 1.00 0.00 0.00 3 1.00 1.00 1.00 1.00 1.00 1.00 1.00 (a) 2 clusters (b) 3 clusters Figura 5.25: Exemplo 2 — Agglomerative Clustering com a primeira tentativa de métrica eaverage linkage. Conclusão Quando se usa K= 3 aaccuracy do modelo é melhor, uma vez que acertou em tudo. 5.4.5 Conclusões Também nesta base de dados se percebe a importância de separar os atributos de espaço do atributo do tempo, visto que usando a métrica criada no Capítulo 4 o modelo acertou totalmente, o que também aconteceu no caso do algoritmo ser usado apenas com os atributos de espaço. 48 Single linkage. Pelo dendrograma e pela curva de cotovelo tanto K= 2 como K= 3 podem ser o número ideal de clusters. Tabela 5.22: Exemplo 3 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e single linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 2 0.77 0.60 1.00 1.00 1.00 0.00 0.00 3 0.86 1.00 0.38 1.00 1.00 0.71 1.00 (a) 2 clusters (b) 3 clusters Figura 5.32: Exemplo 3 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e single linkage. Complete linkage Mais uma vez, tanto K= 2 como K= 3 são números ideais de clusters. 55 Tabela 5.23: Exemplo 3 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e complete linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 2 0.77 0.60 1.00 1.00 1.00 0.00 0.00 3 0.86 0.71 1.00 1.00 1.00 1.00 0.38 (a) 2 clusters (b) 3 clusters Figura 5.33: Exemplo 3 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e complete linkage. Average linkage Mais uma vez, tanto K= 2 como K= 3 são um número ideal de clusters. 56 Tabela 5.24: Exemplo 3 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e average linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 2 0.77 0.60 1.00 1.00 1.00 0.00 0.00 3 0.91 0.73 1.00 1.00 1.00 1.00 0.75 (a) 2 clusters (b) 3 clusters Figura 5.34: Exemplo 3 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e average linkage. Conclusão Embora o modelo não acerte a 100%, quando se aplica apenas aos atributos de espaço obtém uma accuracy razoavelmente boa. 5.5.4 Clustering hierárquico com a primeira tentativa de métrica Vai-se considerar para tempo de observação t= 3 eτ= 5. Apresentam-se os resultados para este exemplo nas Figuras 5.35, 5.36,5.37 e 5.38, e nas Tabelas 5.25, 5.26 e 5.27. 57 (a) Single linkage — curva do cotovelo (b) Single linkage — dendrograma (c) Complete linkage — curva do cotovelo (d) Complete linkage — dendrograma (e) Average linkage — curva do cotovelo (f) Average linkage — dendrograma Figura 5.35: Exemplo 3 — Agglomerative Clustering com a primeira tentativa de métrica. 58 Single linkage Embora apenas K= 2 pareça ser uma escolha ideal para o número de clusters, fez-se também o caso de K= 3. Tabela 5.25: Exemplo 3 — Agglomerative Clustering com a primeira tentativa de métrica e single linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 2 0.77 0.60 1.00 1.00 1.00 0.00 0.00 3 0.80 0.63 1.00 1.00 1.00 1.00 0.12 (a) 2 clusters (b) 3 clusters Figura 5.36: Exemplo 3 — Agglomerative Clustering com a primeira tentativa de métrica esingle linkage. Complete linkage Neste caso, também se fez para K= 2 eK= 3. 59 Tabela 5.26: Exemplo 3 — Agglomerative Clustering com a primeira tentativa de métrica e complete linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 2 0.77 0.60 1.00 1.00 1.00 0.00 0.00 3 0.91 0.73 1.00 1.00 1.00 1.00 0.75 (a) 2 clusters (b) 3 clusters Figura 5.37: Exemplo 3 — Agglomerative Clustering com a primeira tentativa de métrica ecomplete linkage. Average linkage K= 2 eK= 3 parecem ser um número ideal de clusters. Tabela 5.27: Exemplo 3 — Agglomerative Clustering com a primeira tentativa de métrica e average linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 2 0.77 0.60 1.00 1.00 1.00 0.00 0.00 3 0.91 0.73 1.00 1.00 1.00 1.00 0.75 60 (a) 2 clusters (b) 3 clusters Figura 5.38: Exemplo 3 — Agglomerative Clustering com a primeira tentativa de métrica eaverage linkage. Conclusão Quando se usa K= 3 aaccuracy do modelo é melhor, no entanto não foi perfeita. 5.5.5 Conclusões O que se pode concluir depois dos modelos aplicados a esta base de dados é que na verdade, o correto é existirem apenas dois clusters, uma vez que dois deles se intersectam e a distância ao cluster restante é bastante grande. E, mais uma vez, os modelos com melhores resultados foram os que usaram a métrica criada no Capítulo 4, seguidos dos que só usaram os atributos de espaço. 5.6 Exemplo 4 5.6.1 Construção da base de dados A base de dados é constituída por 65 elementos e 3 clusters com 25, 22 e 18 elementos, respetivamente, cada um da forma (y1, y2, t). Os pontos de cada cluster pertencem a cilindros, sendo que dois deles se intersectam, seguindo as seguintes regras: 61 •cluster 1: m= (m1, m2) = (0.5+0.4t, 0.1+0.2t) •cluster 2: m= (m1, m2) = (5.2−2.7t, 0.7+1.55t) •cluster 3: m= (m1, m2) = (1.8+0.5t, 7.3+1.2t) E de seguida para cada elemento de cada cluster, calculou-se: •t= 3rand() •r= 0.5rand() •θ= 2πrand() •y1=rcos(θ) + m1 •y2=rsin(θ) + m2 Representa-se na Figura 5.39 a base de dados do Exemplo 4. Figura 5.39: Exemplo 4 — visualização 2D e 3D dos dados. 5.6.2 Clustering hierárquico com distância de Manhattan Apresentam-se os resultados para este exemplo nas Figuras 5.40, 5.41,5.42 e 5.43, e nas Tabelas 5.28, 5.29 e 5.30. 62 (a) Single linkage — curva do cotovelo (b) Single linkage — dendrograma (c) Complete linkage — curva do cotovelo (d) Complete linkage — dendrograma (e) Average linkage — curva do cotovelo (f) Average linkage — dendrograma Figura 5.40: Exemplo 4 — Agglomerative Clustering com distância de Manhattan. 63 Single linkage Considerando a curva do cotovelo e o dendrograma, conclui-se que K= 2é o ideal. Tabela 5.28: Exemplo 4 — Agglomerative Clustering com distância de Manhattan e single linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 2 0.66 1.00 1.00 0.53 1.00 0.00 0.00 Figura 5.41: Exemplo 4 — Agglomerative Clustering com distância de Manhattan e single linkage: 2 clusters. Complete linkage Considerando a curva do cotovelo e o dendrograma, K= 3 é o valor ideal para o número de clusters. 64 (e) Average linkage — curva do cotovelo (f) Average linkage — dendrograma Figura 5.48: Exemplo 4 — Agglomerative Clustering com a primeira tentativa de métrica. Single linkage Embora apenas K= 2 pareça ser uma escolha ideal para o número de clusters, fez-se também o caso de K= 3. Tabela 5.34: Exemplo 4 — Agglomerative Clustering com a primeira tentativa de métrica e single linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 2 0.66 0.53 1.00 1.00 1.00 0.00 0.00 3 1.00 1.00 1.00 1.00 1.00 1.00 1.00 71 (a) 2 clusters (b) 3 clusters Figura 5.49: Exemplo 4 — Agglomerative Clustering com a primeira tentativa de métrica esingle linkage. Complete linkage Neste caso, fez-se apenas para K= 3. Tabela 5.35: Exemplo 4 — Agglomerative Clustering com a primeira tentativa de métrica e complete linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 3 0.86 1.00 0.59 1.00 1.00 0.74 1.00 Figura 5.50: Exemplo 4 — Agglomerative Clustering com a primeira tentativa de métrica ecomplete linkage: 3 clusters. 72 Average linkage K= 2 eK= 3 parecem ser um número ideal de clusters. Tabela 5.36: Exemplo 4 — Agglomerative Clustering com a primeira tentativa de métrica e average linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 2 0.66 0.53 1.00 1.00 1.00 0.00 0.00 3 0.69 0.56 1.00 1.00 1.00 1.00 0.09 (a) 2 clusters (b) 3 clusters Figura 5.51: Exemplo 4 — Agglomerative Clustering com a primeira tentativa de métrica eaverage linkage. Conclusão Apenas o single linkage acertou totalmente. 5.6.5 Conclusões Para esta base de dados, observa-se que quando se usa o modelo com a distância de manhattan só para os atributos de espaço ou o modelo com a métrica criada no Capítulo 4, o método que trabalha melhor é o single linkage, sendo que no segundo caso acerta 73 totalmente. No entanto, quando se aplica o modelo com distância de manhattan para todos os atributos, o single linkage é o pior método, mas os outros também não funcionam a 100%. Posto isto, verifica-se que o melhor resultado foi usando a métrica criada no Capítulo 4, embora tenha funcionado bem apenas para um caso, o que provavelmente estará relacionado com o linkage usado. 5.7 Exemplo 5 5.7.1 Construção da base de dados A base de dados é constituída por 3 clusters com 400 elementos cada um e da forma (y1, y2, t). Os clusters seguem as seguintes regras: •cluster 1: –t= rand() –θ=rand()2 π –r=ran() 6 –x= 4t(1 −t) –y=x –y1=x+rcos θ –y2=y+rsin θ •cluster 2: –t= rand() –θ= 2π.rand() –r= 0.1rand() 74 –x=t –y=1 1+5t –y1=x+rcos θ –y2=y+rsin θ •cluster 3: –t= 0.4+0.1 exp(−5rand()2) –y1= 0.5+0.1 exp(−5rand()2) –y2= 0.5+0.1 exp(−5rand()2) Representa-se na Figura 5.52 a base de dados do Exemplo 5. Figura 5.52: Exemplo 5 — visualização 2D e 3D dos dados. 5.7.2 Clustering hierárquico com distância de Manhattan Apresentam-se os resultados para este exemplo nas Figuras 5.53, 5.54,5.55 e 5.56, e nas Tabelas 5.37, 5.38 e 5.39. 75 (a) Single linkage — curva do cotovelo (b) Single linkage — dendrograma (c) Complete linkage — curva do cotovelo (d) Complete linkage — dendrograma (e) Average linkage — curva do cotovelo (f) Average linkage — dendrograma Figura 5.53: Exemplo 5 — Agglomerative Clustering com distância de Manhattan. 76 Single linkage Considerando a curva do cotovelo e o dendrograma, K= 2 eK= 3 parecem ser ambos uma boa opção. Tabela 5.37: Exemplo 5 — Agglomerative Clustering com distância de Manhattan e single linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 2 0.67 0.50 1.00 1.00 1.00 0.00 0.00 3 1.00 1.00 1.00 1.00 1.00 1.00 1.00 (a) 2 clusters (b) 3 clusters Figura 5.54: Exemplo 5 — Agglomerative Clustering com distância de Manhattan e single linkage. Complete linkage Neste caso, apenas k= 3 parece uma boa opção. 77 Tabela 5.38: Exemplo 5 — Agglomerative Clustering com distância de Manhattan e complete linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 3 0.70 0.58 1.00 0.69 0.42 1.00 0.67 Figura 5.55: Exemplo 5 — Agglomerative Clustering com distância de Manhattan e complete linkage: 3 clusters. Average linkage Neste caso, aplicou-se o algoritmo para K= 2 eK= 3. Tabela 5.39: Exemplo 5 — Agglomerative Clustering com distância de Manhattan e average linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 2 0.36 0.34 1.00 1.00 0.07 0.00 0.00 3 0.55 0.43 1.00 1.00 0.07 1.00 0.59 78 (a) 2 clusters (b) 3 clusters Figura 5.56: Exemplo 5 — Agglomerative Clustering com distância de Manhattan e average linkage. Conclusão O modelo funciona bastante mal. 5.7.3 Clustering hierárquico com distância de Manhattan só para os atributos de espaço Apresentam-se os resultados para este exemplo nas Figuras 5.57, 5.58,5.59 e 5.60, e nas Tabelas 5.40, 5.41 e 5.42. (a) Single linkage — curva do cotovelo (b) Single linkage — dendrograma 79 (c) Complete linkage — curva do cotovelo (d) Complete linkage — dendrograma (e) Average linkage — curva do cotovelo (f) Average linkage — dendrograma Figura 5.57: Exemplo 5 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço. Single linkage Aplicou-se o algoritmo apenas para K= 2. Tabela 5.40: Exemplo 5 — Agglomerative Clustering com distância de Manhattan só para os atributos de espaço e single linkage: métricas de qualidade com Kclusters. Ketiqueta 0 etiqueta 1 etiqueta 2 accuracy precision recall precision recall precision recall 2 0.33 0.33 1.00 1.00 0.00 0.00 0.00 80 (a) 2 clusters (b) 3 clusters Figura 5.64: Exemplo 5 — Agglomerative Clustering com a primeira tentativa de métrica eaverage linkage. Conclusão Os resultados não foram bons. 5.7.5 Conclusões Para este exemplo, apenas o algoritmo que tem em conta todos os atributos da mesma forma, com o single linkage obteve o resultado pretendido. De facto, esta base de dados era mais complexa e daí a probabilidade dos resultados serem bons ser menor. Aqui se percebeu que a métrica criada no Capítulo 4 não estava a funcionar como pretendido, uma vez que falhou em encontrar os clusters pretendidos. 5.8 Conclusões Foi feito um estudo intensivo de várias métricas, incluindo a proposta de métrica definida no Capítulo 4. As primeiras bases de dados obtiveram bons resultados, o que fez pensar que esta métrica era uma boa aposta. Foi elaborada uma base de dados mais sofisticada que fez com que as conclusões preliminares sobre esta métrica mudassem. Conclui-se assim que a aplicação da nova métrica obteve resultados bons apenas para 87 os dados sintéticos mais simples, ou seja, os que visualmente tinham clusters distintos. Verificou-se também que a métrica criada no Capítulo 4 estaria apenas a fazer uma projeção dos elementos no plano, daí os seus resultados comparados com os do algoritmo apenas com os atributos de espaço serem bastante semelhantes. Assim, estes resultados motivaram a uma criação de uma nova alternativa, que é apresentada no capítulo seguinte. 88 Capítulo 6 O método das faixas temporais 6.1 Princípios Este capítulo introduz um novo processo para a construção dos clusters de uma base de dados em que um dos atributos é o tempo. Seja, então, Duma base de dados constituída por elementos da forma x= (y, t), onde y= (y1, y2). Esta nova abordagem divide-se essencialmente em duas partes. Parte 1 Primeiramente, é necessário dividir a base de dados em faixas ao longo do tempo t que se intersectam. Sejam, assim, tm=mτ,m∈N0, e τa “altura” de cada faixa. Definem-se, então, as faixas primais por Fm=nx= (y, t)∈D:mτ −τ 2≤t≤mτ +τ 2o,com m∈N, e as faixas duais por Fm+1 2={x= (y, t)∈D:mτ ≤t≤mτ +τ},com m∈N0. Tem-se, então, que F1inclui a segunda metade entre t0= 0 et1=τe também a primeira metade entre t1=τet2= 2τ. Tal observa-se na Figura 6.1. 89 Figura 6.1: Faixas de divisão ao longo do atributo do tempo t. Para cada faixa é identificado uma partição Pn={Cn 1, Cn 2, . . . , Cn k}que é um conjunto de kclusters, sendo que nidentifica a faixa (primal ou dual). Aplica-se o clustering hierárquico aglomerativo com a distância de Manhattan, usando todos os atributos, para cada faixa. Um dos critérios definidos é que cada cluster numa faixa, deve ter pelo menos 5% dos elementos nessa faixa, de maneira a evitar a existência de outliers. Parte 2 Sempre que novos elementos são adicionados à base de dados não é necessário fazer oclustering para todas as faixas, uma vez que já tinha sido feito anteriormente, apenas se faz para a última e penúltima faixa de modo a estabelecer-se uma correspondência entre os clusters de uma faixa e outra, sendo que a penúltima já tem correspondência com todas as anteriores. A correspondência entre os clusters de duas faixas seguidas é feita tomando por base uma tabela de intersecção, ou seja, para cada cluster de uma faixa Fm−1 2faz-se a intersecção com cada cluster da faixa seguinte Fme deste modo consegue saber-se quais os clusters que tem mais elementos em comum, estabelecendo-se desta forma a correspondência entre uma faixa primal e uma faixa dual. Considere-se por exemplo, a tabela de correspondência entre as faixas F1 2eF1, 90 ambas com 3 clusters, dada na Tabela 6.1. Tabela 6.1: Tabela de intersecção entre duas faixas. Faixa F1 2 C 1 2 1C 1 2 2C 1 2 3 C1 17 1 0 C1 20 2 9 Faixa F1 C1 30 8 0 Como a faixa F1 2é mais antiga que a faixa F1, então a intersecção tem de ser vista por esta ordem. Desta tabela de intersecção, observa-se que o cluster C 1 2 1tem mais elementos em comum com o C1 1, pois C 1 2 1∩C1 1= 7, enquanto que C 1 2 1∩C1 2= 0 e C 1 2 1∩C1 3= 0. O que significa que o cluster C 1 2 1corresponde ao C1 1. Do mesmo modo, C 1 2 2corresponde ao C1 3eC 1 2 3corresponde ao C1 2. O mesmo é feito para as faixas seguintes. De seguida, para cada faixa calculam-se os centróides de cada cluster. Desta maneira, conseguimos saber a trajetória dos clusters fazendo a ligação dos seus centróides. Apresentam-se nas secções seguintes vários exemplos com a abordagem agora apresentada, testando-se novamente os métodos single linkage,complete linkage eaverage linkage. Note-se que em alguns exemplos aparecem duas versões, isto acontece quando se verificou ser possível obter bons resultados usando números de clusters diferentes. 6.2 Exemplo 1 Para este exemplo, foram criados 3 clusters em forma de cilindros, que não se intersectam. Cada um deles tem 200 elementos e são da forma (y1, y2, t). Os pontos de cada cluster seguem as seguintes regras: 91 •cluster 1: (m1, m2) = (0,0) •cluster 2: (m1, m2) = (2 3,1 3) •cluster 3: (m1, m2) = (3 4,2 3) E de seguida para cada elemento de cada cluster, calculou-se: •r= 0.05rand(0,1) •θ= 2πrand(0,1) •y1=rcos(θ) + m1 •y2=rsin(θ) + m2 •t= 3rand(0,1) Representa-se na Figura 6.2 a base de dados do Exemplo 1. Figura 6.2: Elementos do exemplo 1. Usou-se τ= 0.6. Single linkage Apresentam-se os resultados na Tabela 6.2 e na Figura 6.3. 92 Tabela 6.2: Correspondência dos clusters (single linkage) — exemplo 1. Índice da Faixa F1 2F1F3 2F2F5 2F3F7 2F4F9 2 C1C1C1C1C2C2C2C2C2 C2C2C3C2C3C1C1C3C1 Índice do Cluster C3C3C2C3C1C3C3C1C3 Figura 6.3: Trajetória dos clusters (single linkage) — exemplo 1. Complete linkage Apresentam-se os resultados na Tabela 6.3 e na Figura 6.4. Tabela 6.3: Correspondência dos clusters (complete linkage) — exemplo 1. Índice da Faixa F1 2F1F3 2F2F5 2F3F7 2F4F9 2 C1C2C2C2C2C2C2C2C1 C2C3C3C3C1C3C3C1C2 Índice do Cluster C3C1C1C1C3C1C1C3C3 93 Figura 6.4: Trajetória dos clusters (complete linkage) — exemplo 1. Average linkage Apresentam-se os resultados na Tabela 6.4 e na Figura 6.5. Tabela 6.4: Correspondência dos clusters (average linkage) — exemplo 1. Índice da Faixa F1 2F1F3 2F2F5 2F3F7 2F4F9 2 C1C2C2C2C2C2C2C2C1 C2C3C1C3C1C3C3C1C2 Índice do Cluster C3C1C3C1C3C1C1C3C3 Figura 6.5: Trajetória dos clusters (average linkage) — exemplo 1. Conclusão 94 Esta base de dados era simples — três clusters independentes que evoluem de forma constante ao longo do tempo. O objetivo com a estratégia das faixas é verificar isto mesmo, e de facto em cada faixa também foram encontrados três clusters. 6.3 Exemplo 2 Para este exemplo, foram criados 3 clusters, que não se intersetam, cada um limitado por um retângulo. O primeiro e o segundo cluster têm 250 elementos cada e o terceiro 350. Todos os elementos são da forma (y1, y2, t). Para cada cluster foram calculados y1ey2aleatórios que seguem as seguintes regras: •cluster 1: 0.1< y1<0.3e0.6< y2<0.8 •cluster 2: 0.1< y1<0.4e0.05 < y2<0.4 •cluster 3: 0.6< y1<0.9e0.1< y2<0.7 Para cada elemento foi calculado também um taleatório entre 0 e 3. Representa-se na Figura 6.6 a base de dados do Exemplo 2. Figura 6.6: Elementos do exemplo 2. Usou-se τ= 0.6. Single linkage 95 Apresentam-se os resultados na Tabela 6.5 e na Figura 6.7. Tabela 6.5: Correspondência dos clusters (single linkage) — exemplo 2. Índice da Faixa F1 2F1F3 2F2F5 2F3F7 2F4F9 2 C1C2C2C2C1C1C2C2C2 C2C1C1C3C3C2C1C1C3 Índice do Cluster C3C2C3C1C2C3C3C3C1 Figura 6.7: Trajetória dos clusters (single linkage) — exemplo 2. Complete linkage Apresentam-se os resultados na Tabela 6.6 e na Figura 6.8. Tabela 6.6: Correspondência dos clusters (complete linkage) — exemplo 2. Índice da Faixa F1 2F1F3 2F2F5 2F3F7 2F4F9 2 C1C2C1C2C1C1C1C1C1 C2C1C2C1C2C2C2C2C2 Índice do Cluster C3C3C3C3C3C3C3C3C3 96 Nesta base de dados, embora artificialmente se tenham criado três clusters, quando se observa a projeção parece haver apenas dois clusters. Neste caso, o objetivo da estratégia das faixas foi verificar realmente quantos clusters existem e de facto, verifica-se que na realidade o mais correto é haver apenas dois. No entanto algumas faixas também conseguiram encontrar três, só que não acontecia para todas as faixas. 6.5 Exemplo 4 Para este exemplo, foram criados três cluster, o primeiro com 85 elementos, o segundo com 82 e o terceiro com 88 e os elementos são da forma (y1, y2, t). Os pontos de cada cluster seguem as seguintes regras: •cluster 1: (m1, m2) = (0.5+0.4t, 0.1+0.2t) •cluster 2: (m1, m2) = (5.2−2.7t, 0.7+1.55t) •cluster 3: (m1, m2) = (1.8+0.5t, 7.3+1.2t) Para cada elemento de cada cluster, calculou-se: •t= 3rand(0,1) •r= 0.5rand(0,1) •θ= 2πrand(0,1) •y1=rcos(θ) + m1 •y2=rsin(θ) + m2 Representa-se na Figura 6.16 a base de dados do Exemplo 4. 103 Figura 6.16: Elementos do exemplo 4. Usou-se τ= 0.6. Single linkage Apresentam-se os resultados na Tabela 6.13 e na Figura 6.17. Tabela 6.13: Correspondência dos clusters (single linkage) — exemplo 4. Índice da Faixa F1 2F1F3 2F2F5 2F3F7 2F4F9 2 C1C3C1C1C1C1C1C2C2 C2C1C2C2C2C2C2C1C1 Índice do Cluster C3C2C3C3C3C3C3C3C3 Figura 6.17: Trajetória dos clusters (single linkage) — exemplo 4. 104 Complete linkage Apresentam-se os resultados na Tabela 6.14 e na Figura 6.18. Tabela 6.14: Correspondência dos clusters (complete linkage) — exemplo 4. Índice da Faixa F1 2F1F3 2F2F5 2F3F7 2F4F9 2 C1C1C1C1C1C1C1C1C1 C2C2C2C2C2C2C2C2C2 Índice do Cluster C3C3C3C3C3C3C3C3C3 Figura 6.18: Trajetória dos clusters (complete linkage) — exemplo 4. Average linkage Apresentam-se os resultados na Tabela 6.15 e na Figura 6.19. Tabela 6.15: Correspondência dos clusters (average linkage) — exemplo 4. Índice da Faixa F1 2F1F3 2F2F5 2F3F7 2F4F9 2 C1C1C1C1C1C1C1C1C1 C2C2C2C2C2C2C2C2C2 Índice do Cluster C3C3C3C3C3C3C3C3C3 105 Figura 6.19: Trajetória dos clusters (average linkage) — exemplo 4. Conclusão Nesta base de dados também foram criados 3 clusters que não se intersectam. Com a abordagem das faixas também foram encontrados 3 clusters. No entanto, isto só foi possível devido ao valor de τescolhido, se tivesse sido escolhido um valor de τmaior, talvez houvesse alguma ou algumas faixas onde existiriam apenas dois clusters, uma vez que pela projeção podemos ver que o cluster laranja está perto do azul. 6.6 Exemplo 5 Para este exemplo, foram criados três cluster, cada um com 400 elementos da forma (y1, y2, t). Os pontos de cada cluster seguem as seguintes regras: •cluster 1: –t= rand() –θ=rand()2 π –r=rand 6 –x= 4t(1 −t) –y=x 106 –y1=x+rcos θ –y2=y+rsin θ •cluster 2: –t= rand() –θ= 2πrand() –r= 0.1rand() –x=t –y=1 1+5t –y1=x+rcos θ –y2=y+rsin θ •cluster 3: –t= 0.4+0.1 exp(−5rand()2) –y1= 0.5+0.1 exp(−5rand()2) –y2= 0.5+0.1 exp(−5rand()2) Representa-se na Figura 6.20 a base de dados do Exemplo 5. Figura 6.20: Elementos do exemplo 5. 107 Usou-se τ= 0.2. Single linkage Apresentam-se os resultados na Tabela 6.16 e na Figura 6.21. Tabela 6.16: Correspondência dos clusters (single linkage) — exemplo 5. Índice da Faixa F1 2F1F3 2F2F5 2F3F7 2F4F9 2 C1C2C2C1C1C1C1C1C2 C2C1C1C2C2C2C2C2C1 Índice do Cluster C3C3 Figura 6.21: Trajetória dos clusters (single linkage) — exemplo 5. Complete linkage Apresentam-se os resultados na Tabela 6.17 e na Figura 6.22. 108 Tabela 6.17: Correspondência dos clusters (complete linkage) — exemplo 5. Índice da Faixa F1 2F1F3 2F2F5 2F3F7 2F4F9 2 C1C2C2C2 C2C1C1C1C2C1C1C2 C3C1 C3C2C2C1C1 Índice do Cluster C2 Figura 6.22: Trajetória dos clusters (complete linkage) — exemplo 5. Average linkage Apresentam-se os resultados na Tabela 6.18 e na Figura 6.23. Tabela 6.18: Correspondência dos clusters (average linkage) — exemplo 5. Índice da Faixa F1 2F1F3 2F2F5 2F3F7 2F4F9 2 C1C2C2C2 C2C1C1C1C2C1C1C2 C3C1 C3C2C2C1C1 Índice do Cluster C2 109 Figura 6.23: Trajetória dos clusters (average linkage) — exemplo 5. Conclusão Na projeção desta base de dados apenas se observa um único cluster, no entanto, quando se vê a evolução ao longo do tempo percebe-se que existem três clusters, dois do início do tempo até ao fim e outro que apenas aparece no meio. Com a abordagem das faixas, apenas o single linkage conseguiu encontrar estes três clusters. Os outros métodos encontraram bem no início, mas depois foram piorando. Isto pode estar relácionado com o linkage, mas também com o valor de τescolhido, se este fosse menor poderia ter funcionado bem para os três linkages. 6.7 Exemplo 6 A base de dados deste exemplo é constituída por 3 clusters bem separados sendo que cada um deles tem 105, 102 e 108 elementos, respetivamente, e são da forma (y1, y2, t). Os pontos de cada cluster pertencem a cilindros com alturas diferentes e que não se intersectam seguindo as seguintes regras: •cluster 1: m1= 0,m2= 0 eσ= 0.05 •cluster 2: m1=2 3,m2=1 3eσ= 0.05 110 •cluster 3: m1=3 4,m2=2 3eσ= 0.05 E de seguida para cada elemento de cada cluster, calculou-se: •r=σrand() •θ= 2πrand() •y1=rcos(θ) + m1 •y2=rsin(θ) + m2 •cluster 1: t= rand(0,1). •cluster 2: t= rand(0,2). •cluster 3: t= rand(1.5,3). Representa-se na Figura 6.24 a base de dados do Exemplo 6. Figura 6.24: Elementos do exemplo 6. Usou-se τ= 0.5. Single linkage Apresentam-se os resultados na Tabela 6.19 e na Figura 6.25. 111 Tabela 6.19: Correspondência dos clusters (single linkage) — exemplo 6. Índice da Faixa F1 2F1F3 2F2F5 2F3F7 2F4F9 2F5F11 2 C1C1C1C1C1C1C2C2 C2C2C2C2 Índice do Cluster C2C1C1C1C1C1 Figura 6.25: Trajetória dos clusters (single linkage) — exemplo 6. Complete linkage Apresentam-se os resultados na Tabela 6.20 e na Figura 6.26. Tabela 6.20: Correspondência dos clusters (complete linkage) — exemplo 6. Índice da Faixa F1 2F1F3 2F2F5 2F3F7 2F4F9 2F5F11 2 C1C1C1C1C1C1C2C2 C2C2C2C2 Índice do Cluster C2C1C1C1C1C1 112 Tabela 6.25: Correspondência dos clusters (single linkage) — exemplo 8. Índice da Faixa F1 2F1F3 2F2F5 2F3F7 2F4F9 2 C1C2C1C1C2 Índice do Cluster C2C1C2 C1C1C1C1C2C1 Figura 6.33: Trajetória dos clusters (single linkage) — exemplo 8. Complete linkage Apresentam-se os resultados na Tabela 6.26 e na Figura 6.34. Tabela 6.26: Correspondência dos clusters (complete linkage) — exemplo 8. Índice da Faixa F1 2F1F3 2F2F5 2F3F7 2F4F9 2 C1C1C1C1C1C2 Índice do Cluster C2C2C2 C1C1C1C2C2C2 119 Figura 6.34: Trajetória dos clusters (complete linkage) — exemplo 8. Average linkage Apresentam-se os resultados na Tabela 6.27 e na Figura 6.35. Tabela 6.27: Correspondência dos clusters (average linkage) — exemplo 8. Índice da Faixa F1 2F1F3 2F2F5 2F3F7 2F4F9 2 C1C1C1C1C1C2 Índice do Cluster C2C2C2 C1C1C1C2C2C2 Figura 6.35: Trajetória dos clusters (average linkage) — exemplo 8. Conclusão 120 Nesta base de dados existem dois clusters que se cruzam num certo momento, formando apenas um cluster nesse exato tempo. Mais tarde, voltam a separar-se em dois clusters. Também com a abordagem das faixas isto se verificou. 6.10 Exemplo 9 A base de dados deste exemplo é constituída por 3 clusters em forma de hélice, que não se intersetam. Os três têm 400 elementos cada e são da forma (y1, y2, t). Os pontos de cada cluster seguem as seguintes regras: •cluster 1: (m1, m2) = (0.2,0.2) e(r1, r2) = (0.05,0.01) •cluster 2: (m1, m2) = (0.8,0.2) e(r1, r2) = (0.05,0.01) •cluster 3: (m1, m2) = (0.5,0.8) e(r1, r2) = (0.1,0.03) E de seguida para cada elemento de cada cluster, calculou-se: •t= rand(0,4π) •r=r1+r2rand(−1,1) •θ= 2πrand(0,1) •y1=rcos(t) + m1 •y2=rsin(t) + m2 Representa-se na Figura 6.36 a base de dados do Exemplo 9. 121 Figura 6.36: Elementos do exemplo 9. Usou-se τ= 1. Single linkage Apresentam-se os resultados na Tabela 6.28 e na Figura 6.37. Tabela 6.28: Correspondência dos clusters (single linkage) — exemplo 9. Índice da Faixa F1 2F1F3 2F2F5 2F3F7 2F4 C1C2C2C2C2C2C1C2 C2C1C3C3C3C3C2C3 Índice do Cluster C3C3C1C1C1C1C3C1 F9 2F5F11 2F6F13 2F7F15 2F8 C1C1C1C2C1C1C1C1 C3C3C3C1C3C3C3C3 C2C2C2C3C2C2C2C2 F17 2F9F19 2F10 F21 2F11 F23 2F12 F25 2 C2C1C2C2C2C1C1C1C1 C3C3C3C3C3C3C3C3C3 C1C2C1C1C1C2C2C2C2 122 Figura 6.37: Trajetória dos clusters (single linkage) — exemplo 9. Complete linkage 1ª versão Apresentam-se os resultados na Tabela 6.29 e na Figura 6.38. 123 Tabela 6.29: Correspondência dos clusters (complete linkage 1ª versão) — exemplo 9. Índice da Faixa F1 2F1F3 2F2F5 2F3F7 2F4 C1C2C1C1C2C1C1C1 C2C3C2C3C3C2C2C2 Índice do Cluster C3C1C3C2C1C3C3C3 F9 2F5F11 2F6F13 2F7F15 2F8 C2C1C1C2C2C1C1C1 C2C3C2C3C3 C1C3C2 C1C1C3C2C2 F17 2F9F19 2F10 F21 2F11 F23 2F12 F25 2 C2C1C2C2C2C2C2C2C3 C2C3C1C1C1 C1C3C1C3 C1C3 C1C1C2 Figura 6.38: Trajetória dos clusters (complete linkage 1ª versão) — exemplo 9. 124 2ª versão Apresentam-se os resultados na Tabela 6.30 e na Figura 6.39. Tabela 6.30: Correspondência dos clusters (complete linkage 2ª versão) — exemplo 9. Índice da Faixa F1 2F1F3 2F2F5 2F3F7 2F4F9 2 C1C1C1C1C1C1C1C1C1Índice do Cluster C2C2C2C2C2C2C2C2C2 F5F11 2F6F13 2F7F15 2F8F17 2 C1C1C1C1C1C1C1C1 C2C2C2C2C2C2C2C2 F9F19 2F10F21 2F11F23 2F12F25 2 C1C1C1C1C1C1C1C1 C2C2C2C2C2C2C2C2 Figura 6.39: Trajetória dos clusters (complete linkage 2ª versão) — exemplo 9. Average linkage Apresentam-se os resultados na Tabela 6.31 e na Figura 6.40. 125 Tabela 6.31: Correspondência dos clusters (average linkage) — exemplo 9. Índice da Faixa F1 2F1F3 2F2F5 2F3F7 2F4 C1C2C1C2C2C2C1C2 C2C1C3C1C3C1C2C1 Índice do Cluster C3C3C2C3C1C3C3C3 F9 2F5F11 2F6F13 2F7F15 2F8 C1C1C2C1C2C1C1C1 C2C3C3C3C1C3C3C2 C3C2C1C2C3C2C2C3 F17 2F9F19 2F10 F21 2F11 F23 2F12 F25 2 C2C1C2C1C1C2C1C2C2 C1C3C1C3C3C1C3C3C3 C3C2C3C2C2C3C2C1C1 Figura 6.40: Trajetória dos clusters (average linkage) — exemplo 9. Conclusão Nesta base de dados existem três clusters bem separados, só que em forma de 126 hélice. Mais uma vez, a abordagem das faixas conseguiu distinguir bem os clusters tanto no single linkage como no average. No entanto, o complete linkage apenas encontrou 2 clusters, o que poderia ter resultado melhor se tivesse sido usado um valor de τmais pequeno. 6.11 Exemplo 10 A base de dados deste exemplo é constituída por 3 clusters em forma de hélice com o mesmo eixo mas desfasadas. Os três têm 400 elementos cada e são da forma (y1, y2, t). Os pontos de cada cluster seguem as seguintes regras: •cluster 1: t0= 0 •cluster 2: t0=2π 3 •cluster 3: t0=4π 3 E de seguida para cada elemento de cada cluster, calculou-se: •(m1, m2) = (0.5,0.5) •(r1, r2) = (0.05,0.01) •tfinal = 4π •t= rand(0, tfinal) •r=r1+r2rand(−1,1) •y1=m1+rcos(t−t0) •y2=m2+rsin(t−t0) 127 Representa-se na Figura 6.41 a base de dados do Exemplo 10. Figura 6.41: Elementos do exemplo 10. Usou-se τ= 1. Single linkage Apresentam-se os resultados na Tabela 6.32 e na Figura 6.42. 128