Abordagem heurística baseada em Busca em Vizinhança Variável … · 2017-10-20 · de acordo com experimentos realizados nesta pesquisa. Os experimentos computacionais mostram

UNIVERSIDADE DO RIO GRANDE DO NORTEFEDERAL

UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE

CENTRO DE TECNOLOGIA

PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA E

DE COMPUTAÇÃO

Abordagem heurística baseada em Busca emVizinhança Variável para o Agrupamento

Balanceado de Dados pelo Critério da SomaMínima das Distâncias Quadráticas

Leandro Rochink Costa

Orientador: Prof. Dr. Daniel Aloise

Dissertação de Mestrado apresentada aoPrograma de Pós-Graduação em EngenhariaElétrica e de Computação da UFRN (área deconcentração: Engenharia de Computação)como parte dos requisitos para obtenção dotítulo de Mestre em Ciências.

Número de ordem PPgEEC: M472Natal, RN, Agosto de 2016

Resumo

Após vários avanços na tecnologia de captação e armazenamento de dados e do cres-cimento de aplicações que provêm novas informações, o número de elementos informa-cionais disponíveis é enorme tanto em volume quanto em variedade. Com esse aumentona quantidade de informações, a necessidade de entendê-los e resumi-los se tornou cadavez mais urgente. O Agrupamento Balanceado de Dados, do inglês Balanced Clustering,visa encontrar grupos de entidades similares que possuam aproximadamente o mesmo ta-manho. Neste trabalho, é proposta uma nova abordagem heurística baseada na metaheu-rística Busca em Vizinhança Variável, do inglês Variable Neighborhood Search (VNS),e na metodologia Menos é mais, do inglês Less is more approach, para o problema deagrupamento de dados usando o critério da soma mínima das distâncias quadráticas comrestrição de balanceamento dos grupos. Os algoritmos encontrados na literatura não sãoescaláveis ao passo que aumentamos o tamanho do problema para além de 5000 elementosde acordo com experimentos realizados nesta pesquisa. Os experimentos computacionaismostram que o método proposto supera o atual estado da arte neste problema.

Palavras-chave: Agrupamento de dados, Otimização, Mineração de dados.

Abstract

After advances in collecting and storing data and the growth in applications that pro-vide new information, the number of data elements available is huge in both volume andvariety. With this increase in the quantity of information, the need to understand them andsummarize them has become increasingly urgent. The Balanced Clustering seeks to findgroups of similar entities that have approximately the same size. In this dissertation, wepropose a new heuristic approach based on metaheuristic Variable Neighborhood Search(VNS) and methodology "Less is More Approach"(LIMA) to data clustering problemusing the criterion of the minimum sum-of-squared distances applying balancing restric-tion for the groups. The algorithms found in the literature are not scalable, while theproblem of increased size in addition to elements 5000 in accordance with experimentsperformed in this study. The computational experiments show that the proposed methodoutperforms the current state of the art for the problem.

Keywords: Clustering, Optimization, Data mining.

Sumário

Sumário i

Lista de Figuras iii

Lista de Tabelas iv

Lista de Algoritmos v

Lista de Abreviaturas e Siglas vi

1 Introdução 11.1 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.1.1 Objetivos Específicos . . . . . . . . . . . . . . . . . . . . . . . . 41.2 Organização e Estrutura do Texto . . . . . . . . . . . . . . . . . . . . . . 4

2 Revisão da Literatura 52.1 Minimum Sum-of-squares Clustering - MSSC . . . . . . . . . . . . . . . 52.2 k-Means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.3 Modelos Matemáticos para o Agrupamento Balanceado de Dados . . . . 82.4 Algoritmos de Agrupamento Balanceado de Dados baseados no k-Means 102.5 Problemas de Otimização Combinatória . . . . . . . . . . . . . . . . . . 142.6 Algoritmos de Busca Local . . . . . . . . . . . . . . . . . . . . . . . . . 152.7 Variable Neighborhood Search - VNS . . . . . . . . . . . . . . . . . . . 162.8 Metodologia Less is more approach - LIMA . . . . . . . . . . . . . . . . 18

3 Método de Pesquisa 193.1 Formulação Matemática . . . . . . . . . . . . . . . . . . . . . . . . . . 193.2 Solução Inicial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.3 Vizinhança de Troca de Pares de Pontos . . . . . . . . . . . . . . . . . . 223.4 Pertubação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.5 Busca local . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

i

4 Resultados 284.1 Experimentos Computacionais . . . . . . . . . . . . . . . . . . . . . . . 284.2 Melhor Aprimorante vs Primeiro Aprimorante . . . . . . . . . . . . . . . 294.3 Influência de kmax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.4 Comparação com o Estado da Arte . . . . . . . . . . . . . . . . . . . . . 314.5 Justificativa do Uso da Metodologia LIMA . . . . . . . . . . . . . . . . . 36

5 Considerações Finais 40

Bibliografia 42

Lista de Figuras

1.1 Exemplo de agrupamento balanceado de dados. . . . . . . . . . . . . . . 3

2.1 Ilustração da estratégia VNS [Hansen & Mladenovic 2009]. . . . . . . . . 17

3.1 Criação de uma solução inicial. . . . . . . . . . . . . . . . . . . . . . . . 213.2 Exemplo de vizinhos de uma solução na vizinhança de troca de um par de

pontos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.3 Procedimento de pertubação através da troca de pares de pontos. . . . . . 23

4.1 Gráfico de tempo em segundos até o alvo dos algoritmos Balanced k-means e VNS LIMA para a instância Water treatment plant. . . . . . . . 33

4.2 Gráfico de tempo em segundos até o alvo dos algoritmos Balanced k-means e VNS LIMA para a instância Vehicle. . . . . . . . . . . . . . . . 33

4.3 Gráfico de tempo em segundos até o alvo dos algoritmos Balanced k-means e VNS LIMA para a instância Vowel recognition. . . . . . . . . . 34

4.4 Gráfico de tempo em segundos até o alvo dos algoritmos Balanced k-means e VNS LIMA usando as instâncias Multiple features. . . . . . . . 34

4.5 Funcionamento da pertubação por problema de alocação. . . . . . . . . . 37

iii

Lista de Tabelas

2.1 Variação nos tempos médios de execução do Balanced k-means. . . . . . 12

3.1 Nomenclatura usada nos Algoritmos 8 e 9. . . . . . . . . . . . . . . . . . 26

4.1 Instâncias usadas no experimentos computacionais. . . . . . . . . . . . . 284.2 Plataforma utilizada nos experimentos. . . . . . . . . . . . . . . . . . . . 294.3 Desvio percentual da melhor solução encontrada quando as estratégias

melhor aprimorante e primeiro aprimorante são usadas. . . . . . . . . . . 304.4 Desvio percentual da melhor solução encontrada quando kmax = 5; 10;

15; 20; 25. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.5 Desvio percentual da melhor solução encontrada pelos métodos Balanced

k-means e VNS LIMA. . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.6 Percentual médio da melhora feita pelo VNS LIMA a partir das soluções

do Balanced k-means. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364.7 Desvio percentual a partir do valor da melhor solução conhecida obti-

dos pelos algoritmos Balanced k-means, VNS LIMA e VNS com s =

{10;25;50;100} para cada instância. . . . . . . . . . . . . . . . . . . . . 38

iv

Lista de Algoritmos

1 k-Means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 Constrained k-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Algoritmo Húngaro. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 Balanced k-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 Algoritmo da Busca Local com a estratégia melhor aprimorante. . . . . . 166 Algoritmo da Busca Local com a estratégia primeiro aprimorante. . . . . 167 Metaheurística Variable Neighborhood Search . . . . . . . . . . . . . . . 188 Algoritmo da Busca Local com a estratégia melhor aprimorante. . . . . . 269 Algoritmo da Busca Local com a estratégia primeiro aprimorante. . . . . 27

v

Lista de Abreviaturas e Siglas

LIMA Less is more approach

LNS Large Neighborhood Search

MSSC Minimum Sum-of-Squares Clustering

TTTPlots Time-to-target Plots

VNS Variable Neighborhood Search

vi

Capítulo 1

Introdução

Após vários avanços na tecnologia de captação e armazenamento de dados e do cres-cimento de aplicações que provêm novas informações, o número de elementos informaci-onais disponíveis é enorme tanto em volume quanto em variedade. Com esse aumento naquantidade de informações, a necessidade de entendê-los e resumi-los se tornou cada vezmais urgente. A melhoria nas técnicas aplicadas na análise de clusters, do inglês cluster

analysis, se tornou imprescindível [Jain 2010].A análise de clusters atua no processamento desses dados com o fim de extrair ca-

racterísticas. Em outras palavras, ela têm como objetivo descobrir grupos naturais dentreum conjunto de entidades. De acordo com Jain (2010), esse processo de classificar podeser operacionalmente definido da seguinte forma: dada a representação de n entidadesdeve-se encontrar K grupos baseados na medida de similaridade entre eles de modo queelementos de um mesmo grupo tenham similaridade alta entre si e baixa para elementosde grupos diferentes.

Existe na literatura uma distinção entre as classes de modelos de aprendizagem. Osmodelos de classificação fazem uso de técnicas de processamento de dados supervisio-nado. Essas técnicas são definidas assim devido ao fato de precisar que nós as ensinemos,através de um conjunto de dados de treinamento, como devem decidir a respeito de qualgrupo um elemento deve pertencer. Este conjunto é formado por entidades já rotuladascom os grupos aos quais devem ser designadas. Através disso, os outros conjuntos dedados são processados. Os modelos de agrupamento de dados usam técnicas não super-visionadas e semi supervisionadas para realizar as suas tarefas. Quando são utilizadastécnicas não supervisionadas, só é fornecido o conjunto de dados que deve ser agrupadoe então o algoritmo reúne esses dados seguindo somente o critério de semelhança entreentidades escolhido.

Pode-se encontrar na literatura várias aplicações de agrupamento de dados, mas ge-ralmente todas o usam com um dos três propósitos[Jain 2010]: conhecimento implícito;

CAPÍTULO 1. INTRODUÇÃO 2

classificação natural; e compressão. Em aplicações com o propósito de conhecimento im-plícito, os dados são agrupados em clusters com o objetivo de os compreender, gerar hi-póteses, detectar anomalias e identificar características relevantes que não são facilmentepercebidas. As aplicações que buscam a classificação natural agrupam os dados com ofim de determinar o grau de similaridade entre formas e organismos. Quando aplicaçõestem como objetivo a compressão dos dados, eles são organizados e resumidos através daformação de clusters.

Há situações nas quais precisa-se não somente agrupar dados mas fazê-lo de modoequilibrado quanto ao número de elementos por cluster. O agrupamento balanceado dedados, do inglês Balanced Clustering, visa encontrar grupos de entidades que possuamaproximadamente o mesmo tamanho. A Figura 1.1 é um exemplo de agrupamento ba-lanceado de dados. Neste trabalho, definimos agrupamento balanceado de dados como oproblema de formar subconjuntos de entidades em que o número de elementos entre elesseja igual ou que difira no máximo em uma unidade.

Métodos restringidos pelo balanceamento são necessários quando para um problemaé importante agrupar elementos semelhantes em um mesmo cluster e manter a quantidadede elementos por cluster igual. Por exemplo, agrupar dados de modo balanceado é impor-tante para algumas aplicações como protocolos de comunicação entre sensores wireless

[Gong et al. 2008, Liao et al. 2013, Xiaoyan et al. 2015, Shin et al. 2015], problemasde roteamento de veículos[He et al. 2009, Nallusamy et al. 2010], criação de equipesde estudantes[Desrosiers et al. 2005] e sistemas de distribuição dinâmica de recursos emaplicações SaaS(Software as a Service) com multiusuários[Su et al. 2015].

Em protocolos de comunicação entre sensores wireless e uma base que prolongam avida útil energética dos dispositivos de sua rede, o agrupamento balanceado de dados éusado para dividir os sensores em grupos de tamanho iguais e dessa forma, juntamentecom a metodologia do protocolo, equilibrar o tráfego de dados e o consumo de energiaem cada dispositivo.

Algumas soluções para o problema de roteamento de veículos tomam a decisão táticade dividir os clientes a serem visitados em grupos de tamanho iguais. Dessa forma paracada cluster, existe um problema de roteamento de veículos reduzido. Essa decomposi-ção do problema visa resolver de forma rápida, e com qualidade satisfatória, até mesmoinstâncias com grandes conjuntos de clientes.

Podemos também usar o agrupamento balanceado de dados para criar equipes equi-libradas de estudantes. Esse problema tem como objetivo formar grupos de estudanteslevando em consideração uma série critérios para que todas as equipes sejam semelhantesquanto às características e às habilidades de seus integrantes.


Uma aplicação mais específica do agrupamento balanceado de dados é feita em siste-mas de distribuição dinâmica de recursos em aplicações SaaS (Software as a service) commultiusuários. Nela os usuários são agrupados de acordo com a similaridade na quanti-dade de recursos necessários para garantir o nível mínimo de serviço por eles contratados.Dessa forma, os custos de transferir um usuário de uma instância do sistema de servido-res para outra e os custos de ativar novas máquinas virtuais para satisfazer a demanda derecursos são minimizados. A quantidade de clientes em cada grupo deve ser balanceada,pois o sistema processa as requisições dos usuários em fila, logo, se uma fila fica muitogrande o tempo de resposta ao cliente também fica podendo, inclusive, levar ao sistemanão atender os requisitos contratados pelos usuários.

Figura 1.1: Exemplo de agrupamento balanceado de dados.

Neste trabalho, é proposto um método heurístico baseado na metaheurística Variable

Neighborhood Search (VNS) e na metodologia Less is more approach - LIMA [Mladenovicet al. 2016] para realizar o agrupamento balanceado de dados restringido pelo balancea-mento. Esse método usa o critério da soma mínima das distâncias quadráticas, do inglêsminimum sum-of-squares clustering (MSSC), para agrupar os dados de forma balanceada.A tarefa de agrupar dados com o critério da soma mínima dos quadrados é um problemaNP-árduo [Aloise et al. 2009].


A nova abordagem proposta (VNS LIMA) se enquadra na categoria dos algoritmosrestringidos pelo balanceamento. Os experimentos computacionais mostram que a heu-rística VNS LIMA supera o atual estado da arte tanto em qualidade das soluções quantoem velocidade de processamento.

1.1 Objetivos

O objetivo principal deste trabalho consiste em criar um novo método heurístico ba-seado na metaheurística VNS e na metodologia LIMA que se enquadre na categoria dosalgoritmos restringidos pelo balanceamento e que seja capaz de obter rapidamente boassoluções.

1.1.1 Objetivos Específicos

Os seguintes objetivos específicos desta pesquisa são listados:

1. identificar formas simples e eficientes de se perturbar uma solução;2. identificar maneiras simples e precisas de se realizar a busca local;3. projetar e implementar o método heurístico proposto;4. testar empiricamente quais estratégias de funcionamento da busca local geram me-

lhores soluções; e5. analisar experimentalmente e justificar o potencial da metodologia LIMA;

1.2 Organização e Estrutura do Texto

Este trabalho segue a seguinte organização: no Capítulo 2, é feita a revisão da litera-tura; no Capítulo 3, o método heurístico baseado na metaheurística VNS e na metodologiaLIMA e as diferentes estratégias que vão ser adotadas para melhorar o seu desempenhosão expostas; no Capítulo 4, os experimentos computacionais são apresentados; e no Ca-pítulo 5, as considerações finais e conclusões são expostas.

Capítulo 2

Revisão da Literatura

2.1 Minimum Sum-of-squares Clustering - MSSC

O agrupamento de dados é uma ferramenta fundamental quando queremos extrairinformações úteis mas não óbvias de um conjunto de dados (ver §1). Os clusters sãoformados de acordo com critério de homogeneidade e/ou separação adotado. Vários sãoos critérios existentes e um dos mais usados é o critério da soma mínima das distânciaseuclidianas quadráticas.

O problema de agrupar dados através desse critério é conhecido na literatura por mi-

nimum sum-of-squares clustering e é um problema NP-árduo [Aloise et al. 2009], ou seja,não é conhecido um algoritmo que consiga dar a resposta ótima para estes problema emtempo polinomial. Dado n pontos, ele tem como objetivo encontrar K clusters de modoque o somatório das distancias quadráticas de cada um dos pontos com o centro do cluster

em que foi designada seja minimizado.O problema do MSSC pode ser expresso pelo seguinte modelo matemático:

minx,y

n

∑i=1

K

∑j=1

xi j�pi − y j�2 (2.1)

Sujeito a:K

∑j=1

xi j = 1 ∀ i = 1,2, ...,n (2.2)

xi j ∈ {0,1} ∀i = 1,2, ...,n;∀ j = 1,2, ...,K (2.3)

Neste modelo temos n pontos pertencentes a P = {p1, p2, ..., pn}, todos descritos noespaço Rs, para serem agrupados em K < n clusters. Todo cluster j possui um centrolocalizado em um ponto desconhecido y j ∈ Rs para j = 1,2, ...,K. A função objetivo

CAPÍTULO 2. REVISÃO DA LITERATURA 6

(2.1) determina que deve-se minimizar as distâncias euclidianas quadráticas (|| · ||) entrepontos e os centros dos clusters em que eles foram associados. A restrição (2.2) garanteque todo ponto p ∈ P seja designado a somente um cluster. Finalmente, a restrição (2.3)determina que as variáveis xi j sejam binárias. Desse modo, as variáveis de decisão xi j

assumem o valor 1, xi j = 1, se o ponto pi está designado ao cluster j, caso contrário, xi j

assume o valor 0.O agrupamento de dados pelo MSSC possui a propriedade de minimizar as distan-

cias intra-cluster ao mesmo tempo que maximiza as distancias inter-clusters. Dado P =1n ∑n

i=1 pi, um vetor constante ρ ∈ Rs e S j = ∑i∈ j xi j. Segundo Späth (1980),

n

∑i=1

� pi −ρ �2 =n

∑i=1

� pi − P �2 +n � P−ρ �2 (2.4)

Ao restringir o problema a um único cluster � com os seus respectivos S� pontos, notamosque P corresponde a y� em (2.4):

∑i∈�

� pi −ρ �2 = ∑i∈�

� pi − y� �2 +S� � y�−ρ �2 (2.5)

Se somarmos a Equação (2.5) de todos os K clusters teremos como resultado:

n

∑i=1

� pi −ρ �2 =K

∑j=1

∑i∈ j

� pi − y j �2 +K

∑j=1

S j � y j −ρ �2 (2.6)

A Equação2.6 considera todos os n pontos e P é constante, então, pode-se atribuir ρ = P.

n

∑i=1

� pi − P �2 =K

∑j=1

∑i∈ j

� pi − y j �2 +K

∑j=1

S j � y j − P �2 (2.7)

Uma vez que ∑ni=1 � pi − P �2 é constante, se a distância intra-cluster é minimizada con-

sequentemente a distância inter-clusters associada ao somatório ∑Kj=1 S j � y j − P �2 é ma-

ximizada.Além disso, o agrupamento de dados pelo MSSC possui outras propriedades. Dado

a alocação dos pontos, os centros dos clusters ficam localizados exatamente nos seuscentroides. Desse modo, os clusters tendem a ser esféricos. Dado a localização doscentroides, os pontos serão designados ao cluster com centroide mais próximo.

Existem vários métodos, exatos e heurísticos, para se agrupar dados pelo critério doMSSC. Contudo, o mais popular dentre eles é o algoritmo heurístico k-Means[MacQueen& et al 1967].


2.2 k-Means

O algoritmo k-means foi proposto MacQueen & et al (1967). Apesar de estar presentena literatura por tanto tempo, ele continua sendo importante. A sua simplicidade, efici-ência e facilidade de implementação são os motivos de ser o algoritmo mais usado pararesolver problemas de agrupamento de dados pelo MSSC.

O k-means requer algumas parâmetros iniciais especificados pelo usuário: número declusters K; posição inicial do centroide dos K clusters; e o conjunto de n pontos P =

{p1, p2, ..., pn} a ser processado.Este algoritmo possui as etapas de alocação e de atualização como os procedimentos

principais. O passo de alocação é responsável por atribuir todos os n pontos pertencentesa P ao cluster de centroide mais próximo de acordo com a distância euclidiana quadrática.O passo de atualização tem a tarefa de determinar a nova localização dos centroides dosclusters.

Uma vez que os dados iniciais forem definidos, o k-means irá vai executar sucessivasiterações, composta pelo passo de alocação seguido do passo de atualização, até que alocalização dos centroides dos clusters não mude mais. Quando os centroides não muda-rem, os algoritmo termina o seu funcionamento.

O k-means é determinístico e gera soluções em passos finitos. Só é possível atingirsoluções diferentes se for fornecido parâmetros diferentes, pois as soluções por ele gera-das são sempre ótimos locais. Devido a no passo alocação um ponto ser atribuído sempreao cluster de centroide mais próximo, a solução não pode piorar a cada iteração. Se oalgoritmo não melhora a solução, a configuração dos clusters não muda, consequente-mente, os centroides também não irão alterar e assim ele terá atingido um ótimo local.Isso também explica o porquê do critério de parada usado.

O k-means pode ser representado pelo Algoritmo 1.


Algoritmo 1 k-Means1: escolher as posições iniciais dos centroides yi∀i ∈ [1,K]2: repetir3: Passo de alocação:4: para i=1,...,n faça5: alocar pi ao centroide mais próximo6: fim para7:8: Passo de atualização:9: para i=1,...,n faça

10: calcular a posição do centroide yi11: fim para12: até que centroides não mudem

2.3 Modelos Matemáticos para o Agrupamento Balance-ado de Dados

O agrupamento balanceado de dados se preocupa em agrupar um conjunto P= {p1, p2,

..., pn} de n pontos em K clusters de acordo com as suas similaridades e de forma quecada cluster tenha aproximadamente a mesma quantidade de pontos. Contudo, diferentesmodelos matemáticos que descrevem essa tarefa foram propostos na literatura.

O modelo matemático usado por Bradley et al. (2000) realiza esse procedimento demodo que cada um dos clusters tenha no mínimo τ elementos. A ideia é fazer com quenão existam clusters muito pequenos na partição. Esse modelo é conhecido como agru-pamento de dados restrito e é expresso da seguinte forma:

Min:n

∑i=1

K

∑j=1

xi j�pi − y j�2 (2.8)

Sujeito a:K

∑j=1

xi j = 1 ∀ i = 1,2, ...,n (2.9)

n

∑i=1

xi j ≥ τ j ∀ j = 1,2, ...,K (2.10)

xi j ∈ {0,1} ∀ i = 1,2, ...,n, ∀ j = 1,2, ...,K (2.11)

A outra formulação matemática existente foi usada por Zhu et al. (2010). Este autorconsiderou que todo cluster devia ter um tamanho específico τ. Esses valores são estabe-


lecidos de acordo com o conhecimento prévio das boas soluções da instância de dados aser processada. O seguinte modelo representa o problema de agrupamento de dados porrestrições de tamanho tratado por Zhu et al. (2010).

Min:n

∑i=1

K

∑j=1

xi j�pi − y j�2 (2.12)

Sujeito a:K

∑j=1

xi j = 1 ∀ i = 1,2, ...,n (2.13)

n

∑i=1

xi j = τ j ∀ j = 1,2, ...,K (2.14)

xi j ∈ {0,1} ∀ i = 1,2, ...,n, ∀ j = 1,2, ...,K (2.15)

Finalmente, o modelo de agrupamento balanceado de dados considerado por Mali-nen & Franti (2014) tem como objetivo agrupar n pontos em K clusters de modo que asquantidades de pontos em cada um dos clusters difiram em no máximo uma unidade.

Min:n

∑i=1

K

∑j=1

xi j�pi − y j�2 (2.16)

Sujeito a:K

∑j=1

xi j = 1 ∀ i = 1,2, ...,n (2.17)

n

∑i=1

xi j =nK

∀ j = 1,2, ...,K (2.18)

xi j ∈ {0,1} ∀ i = 1,2, ...,n, ∀ j = 1,2, ...,K (2.19)

O número de pontos em cada cluster é determinado pela divisão n/K. Se n/K =

�n/K� = �n/K� então todo cluster terá n/K pontos. Caso contrário teremos n mod K

clusters com �n/K� pontos e K − (n mod K) clusters com �n/K�. Isso garante que osclusters tenham tamanhos iguais ou que difiram em no máximo uma unidade. Nota-seque este modelo é um caso específico do usado por Zhu et al. (2010).

Além disso, o modelo matemático considerado por Malinen & Franti (2014), expres-sado por (2.16)-(2.19), é o modelo tratado neste trabalho e serviu de base para o modeloequivalente apresentado no Capitulo 3.


2.4 Algoritmos de Agrupamento Balanceado de Dadosbaseados no k-Means

Devido a sua popularidade o k-Means serve como base para muitos algoritmos deagrupamento de dados. Não diferentemente, os principais algoritmos para os mode-los da seção anterior também tem como base o k-Means: Constraint k-Means[Bradleyet al. 2000]; Size Constraint Clustering[Zhu et al. 2010]; e Balanced k-Means[Malinen &Franti 2014].

O constrained k-means é capaz de usar qualquer um dos três modelos matemáticos daSeção 2.3: expressões (2.8)-(2.11); (2.12)-(2.15); e (2.16)-(2.19). Este algoritmo se con-centra em dois passos: alocação, do inglês assignment; e atualização, do inglês update. Opasso de alocação adotado no constrained k-means consiste em resolver um problema li-near de otimização. Quando proposto, o problema adotado foi o descrito pelas expressões(2.8)-(2.11). Uma vez que os centroides estão fixos no passo de alocação, o modelo (2.8)-(2.11) é linear. Neste modelo matemático K restrições são dedicadas a garantir o númeromínimo de τ j pontos em cada um dos j clusters ( j = 1, ...,K). O passo de atualização éresponsável por atualizar os valores dos centroides de todos os K clusters.

O Algoritmo 2 descreve o funcionamento do constrained k-means:

Algoritmo 2 Constrained k-means1: escolher as posições iniciais dos centros yi∀i ∈ [1,K]2: repetir3: Passo de alocação:4: Resolver o modelo (2.8 - 2.11) com centroides fixos5:6: Passo de atualização:7: para i=1,...,n faça8: calcular a posição do centroide yi9: fim para

10: até que centroides não mudam

O size constraint clustering, desenvolvido por Zhu et al. (2010), também é capazde trabalhar com os modelos matemáticos representados pelas expressões (2.8)-(2.11),(2.12)-(2.15) e (2.16)-(2.19). No entanto, este algoritmo foi proposto para usar o modelorepresentado pelas expressões (2.12)-(2.15). Essa heurística consiste em primeiro encon-trar uma solução Z através do k-Means, que não garante clusters com balanceamento detamanho, para então resolver o problema de programação não-linear:


min�ZZT −XXT� (2.20)

Sujeito a:K

∑j=1

xi j = 1 ∀i = 1,2, ...,n (2.21)

n

∑i=1

xi j = τ j ∀ j = 1,2, ...,K (2.22)

xi j ∈ {0,1} ∀i = 1,2, ...,n;∀ j = 1,2, ...,K (2.23)

Em seu trabalho, Zhu et al. (2010) tornou esse modelo linear para então resolvê-loe mais detalhes desse procedimento podem ser nele conferidos. Note que para utilizaralgum outro modelo de agrupamento de dados apresentado na Seção 2.3 basta substituiras expressões (2.22) pelas (2.10) ou (2.18). A função objetivo, Equação (2.20), faz usodo fato dos elementos da matriz n×n resultante da multiplicação ZZT serem iguais a umse dois pontos pi e p j estão no mesmo cluster em Z:

(ZZT )i j =

1 se pi e p j estão no mesmo cluster em Z

0 caso contrário.

De mesmo modo, isso também é válido para a multiplicação XXT . Dessa forma, a funçãoobjetivo (2.20) busca maximizar, ou seja priorizar, a concordância entre a solução nãobalanceada já existente Z, obtida pelo k-means, com a solução balanceada X através daminimização do valor na norma de Frobenius � ·�.

O Balanced k-Means, proposto por Malinen & Franti (2014), é o estado da arte dosalgoritmos para os modelos (2.12)-(2.15) e (2.16)-(2.19) e está disponível em http:

//www2.uef.fi/en/sipu/data-and-software. Quando proposto, ele obteve boas so-luções para o agrupamento balanceado de dados, mas não se mostrou escalável para con-juntos de dados com mais de 5000 pontos conforme pode ser verificado na Tabela 2.1.Nela vemos que o balanced k-means precisa de várias horas para processar um conjuntode dados com 5000 pontos.

Apesar do Balanced k-means ter sido desenvolvido para resolver o agrupamento ba-lanceado de dados seguindo o modelo composto pelas expressões (2.16)-(2.19), ele tam-bém pode agrupar os pontos de acordo com o modelo matemático (2.12)-(2.15). Isso épossível devido ao modelo (2.16)-(2.19) ser um caso específico do modelo (2.12)-(2.15).

1Apenas o item 4.mfeat-pix.


Tabela 2.1: Variação nos tempos médios de execução do Balanced k-means.

Instância(Elementos, Atributos ) Tempo de CPUIris(150, 4) 0.42sWine(178, 13) 0.6sGlass(214, 10) 2.54sThyroid(215, 5) 1.45sIonosphere(351, 34) 3.65sLibra(360, 90) 8.36sUser Knowledge(403, 5) 12.35sBody Measurements(507, 5) 10.51sWater Treatment Plant(527, 38) 24.04sBreast Cancer(569, 30) 22.12sSynthetic Control(600, 60) 16.98sVehicle(846, 18) 45.66sVowel Recognition(990, 10) 2min e 28.36sYeast(1484, 8) 6min e 34.09sMultiple Features(2000, 2401) 37min e 13.19sImage Segmentation(2310, 19) 30min e 27.98sWaveform(5000, 40) >24h

Este algoritmo também se concentra em dois passos: alocação e atualização. A fasede alocação é responsável por alocar os pontos nos clusters de acordo com a localizaçãodos seus centroides de modo que diminua ao máximo o valor da função objetivo. O passode atualização é responsável por atualizar as posições dos centroides.

O passo de alocação é o quê diferencia o balanced k-means do k-means tradicional.Enquanto que o k-means atribui cada ponto ao cluster com o centroide mais próximo, obalanced k-means resolve neste passo um problema de alocação para determinar a melhorconfiguração dos elementos nos grupos de acordo com a localização dos centroides nomomento e com as vagas disponíveis em cada cluster. O problema de alocação usadopelo balanced k-means pode ser descrito da seguinte forma. Dado dois conjuntos, A e S,de tamanhos iguais e uma função de pesos W : A× S → R. O seu objetivo é encontraruma função bijetiva f : A → S tal que a função de custo ∑a∈AW (a, f (a)) seja mínima.No contexto desse algoritmo, A e S correspondem, respectivamente, às vagas disponíveisnos clusters e aos pontos. O número de vagas em cada cluster é determinado pela divisãon/K. Teremos n mod K clusters com �n/K� vagas e K − (n mod K) clusters com �n/K�.Dessa forma, o número de pontos entre quaisquer dois clusters se diferenciará no máximoem uma unidade. O problema de alocação deste passo é resolvido com complexidadeO(n3) [Burkard et al. 2009] através do algoritmo Húngaro. Dado uma matriz de pesos D

que contêm os valores de W (i, j)∀i, j ∈ [1,n] ∈ Z, a implementação do algoritmo húngaro


[Kuhn 1955] possui 4 passos: Passo A - subtrair todos os elementos da matriz D pelo valordo menor elemento (h) de D. Essa operação gera uma matriz D1; Passo B - encontrar omenor conjunto de linhas L em D1 que englobe todos os zeros de D1. Se o número delinhas em L, n�, for igual a n então a solução foi encontrada; Passo C - Se n� < n, entãoencontre o valor do menor elemento (h1) de D1 que não esteja contido em L. Somar h1

a todos os elementos das linhas L e subtrair de h1 de todos os elementos de D1; e PassoD - repetir os passos A, B e C com D ← D1. Esses procedimentos são apresentados noAlgoritmo 3.

Algoritmo 3 Algoritmo Húngaro.1: repetir2: h ← valor do menor elemento de D3: D1(i, j)← D(i, j)−h ∀i, j ∈ [1,n] ∈ Z4: L ← menor conjunto de linhas de D1 que contêm todos os zeros de D15: se n� < n então6: h1 ← valor do menor elemento de {D1 −L}7: D1(i, j)← D1(i, j)+h1 ∀D1(i, j) ∈ {D1 −L}8: D1(i, j)← D(i, j)−h1 ∀i, j ∈ [1,n] ∈ Z9: D ← D1

10: fim se11: até que n� = n

A função de pesos W usa a distância euclidiana quadrática entre um elemento e umcentroide da seguinte forma. Sendo g o índice que identifica uma vaga, i o índice doelemento na instância e t a iteração do algoritmo.

W (g, i) = �pi − y t(g mod k)+1�2 ∀g ∈ [1,n] ∀i ∈ [1,n] (2.24)

O passo de atualização tem como função atualizar a localização dos centroides dosclusters após o passo de alocação. Isso é necessário, pois os elementos mudam de cluster,no passo anterior, logo os centroides também mudam. Quando após a atualização nenhumcentroide mudar, o algoritmo termina a sua execução, devido a não encontrar nenhumamelhoria. A atualização é feita seguindo a função:

ysj =

n

∑i=1

xi j pi

n

∑i=1

xi j

,∀ j (2.25)


Além desses passos, o balanced k-means inicializa os seus centroides de modo ale-atório. Isso é feito com o uso de um gerador de números uniformemente aleatórios daseguinte forma. Ao iniciar o algoritmo, os valores iniciais de cada uma das coordenadasde cada um dos centroides são atribuídos à valores randômicos.

O algoritmo balanced k-means pode ser descrito pelo Algoritmo 4.

Algoritmo 4 Balanced k-means1: inicializar os centroides aleatoriamente2: t ← 03: repetir4: Passo alocação:5: Calcular W (a, i) ∀a ∈ [1,n] ∀i ∈ [1,n]6: Resolver o problema de alocação de acordo com W7: Passo atualização:8: Calcular centroides y t+1

9: t ← t +110: até que centroides não mudem

2.5 Problemas de Otimização Combinatória

A classe de problemas de otimização combinatória está presente em várias aplicações.Uma dessas aplicações é o agrupamento balanceado de dados uma vez que estamos inte-ressados em analisar qual combinação de pontos reunidos em clusters gera a solução demenor custo.

A otimização combinatória é usada quando precisa-se tomar decisões no espaço dis-creto através da busca de uma solução ótima dentre de um conjunto finito ou contavel-mente infinito de alternativas. A otimalidade está associada a um critério de custo queprove uma medida quantitativa da qualidade de cada solução. Muitos desses problemassão classificados como NP-árduos[Garey & Johnson 1979] não sendo conhecido algo-ritmo capaz de encontrar a solução exata em tempo polinomial, consequentemente, existemuito interesse em meios de se encontrar boas soluções para esses problemas de modoaproximado [Lenstra 1997].

Um problema de otimização combinatória é especificado por um conjunto de ins-tâncias de um problema. Essas instâncias são definidas como um par (X, f ) sendo X oconjunto das soluções viáveis existentes; f a função de custo que mapeia f : X→ R. Oseu objetivo é encontrar o ótimo global X∗ ∈ X de modo que f (X∗) ≤ f (i)∀i ∈ X sendof ∗ = f (X∗) o custo ótimo global, X∗ = {X ∈ X| f (X) = f ∗} o conjunto das soluçõesglobalmente ótimas e X o conjunto das variáveis de decisão que compõem uma solução.


Segundo Lenstra (1997) a vizinhança de uma solução pode ser definida da seguintemaneira. Seja (X, f ) uma instância de um problema de otimização combinatória. Umavizinhança N é uma função que define para cada solução X ∈ X um conjunto N(X) ⊆ Xde soluções ditas próximas a X . O conjunto N(X) é denominado vizinhança de X e cadasolução pertencente a N(X) é chamado de vizinho de X .

A vizinhança de uma solução depende do problema que está sendo abordado e ne-nhuma regra geral pode ser adotada. Além disso, até para um mesmo problema váriasvizinhanças podem ser aplicadas e encontrar uma que eficientemente leve um algoritmoa uma bom ótimo local é um dos desafios da matemática discreta. Um ótimo local podeser definido como uma solução �X ∈ X de uma vizinhança N se f (�X)≤ f (X)∀X ∈ N(�X).

2.6 Algoritmos de Busca Local

Métodos de busca local são muito usados para resolver problemas de otimização com-binatória NP-difíceis (§ver 2.5) através de uma abordagem genérica. O objetivo dessesmétodos é encontrar uma solução ótima uma vez que ela apresenta o menor valor conside-rando um problema de minimização de custos. Para usar esses métodos deve-se escolherqual estrutura de vizinhança e de solução serão usadas.

No geral, um método de busca local começa a sua busca a partir de uma solução inicialX criada por um outro algoritmo ou gerada randomicamente. A partir de X , ele busca nosseus vizinhos N(X) uma solução melhor X �. Uma vez encontrada, a busca continua agorana vizinhança de N(X �) e assim por diante até que seja encontrado X � = �X .

Essa metodologia tem sido aplicada com sucesso em muitos problemas e muitas es-tratégias de busca podem ser usadas. Por exemplo: a estratégia melhor aprimorante, doinglês best improvement, sempre busca a melhor solução da vizinhança investigada; e aestratégia primeiro aprimorante, do inglês first improvement, busca a primeira solução davizinhança investigada que melhore o valor da função objetivo.

Os Algoritmos 5 e 6 descrevem de modo geral o funcionamento das estratégias melhore primeiro aprimorante respectivamente. Sendo argmin( f (X �)) a função que retorna asolução X � que minimiza o valor da função objetivo f (); uma vizinhança N(X) igualao conjunto de soluções {X1,X2, ...,X|N(X)|}; e |N(X)| o número de soluções contidas navizinhança N(X).


Algoritmo 5 Algoritmo da Busca Local com a estratégia melhor aprimorante.1: função Melhor(X)2: enquanto X �= �X faça3: i ← 14: X � ← X5: para i ≤ |N(X)| faça6: se f (Xi)< f (X �)) então7: X � ← Xi8: fim se9: fim para

10: X ← X �11: fim enquanto12: fim função

Algoritmo 6 Algoritmo da Busca Local com a estratégia primeiro aprimorante.1: função Primeiro(X)2: enquanto X �= �X faça3: i ← 14: enquanto f (Xi)≥ f (X) ou i < |N(X)| faça5: i ← i+16: fim enquanto7: X ← Xi8: fim enquanto9: fim função

2.7 Variable Neighborhood Search - VNS

Metaheurística é um algoritmo criado para resolver de forma aproximada problemasde otimização de forma genérica, ou seja, sem se adaptar para um problema específico.Ela pode ser vista como um algoritmo heurístico de alto nível [Boussaïd et al. 2013].

A principal ideia da metaheurística Variable Neighborhood Search [Mladenovic &Hansen 1997] é explorar diferentes vizinhanças sucessivas de forma que seja mais difícilpara o método ficar preso a um ótimo local. Quando usamos métodos de busca local emproblemas de otimização combinatória, ela é capaz de melhorar uma solução inicial a cadaiteração até que um ótimo local seja atingido. A grande contribuição da metaheurísticaVNS foi criar um procedimento simples e sistêmico de busca em vizinhanças variáveispara contornar o problema da busca local atingir um ótimo local de qualidade ruim.

A metaheurística VNS não segue uma trajetória específica, mas explora vizinhançasgradualmente distantes da melhor solução encontrada até o momento. Dessa maneiracaracterísticas favoráveis da solução atual tendem a ser mantidas e usadas para se ob-ter novas vizinhanças promissoras. Esse procedimento é o que permite encontrar novos


ótimos locais de qualidade superior mais facilmente.Esta metaheurística tem o seguinte funcionamento. Primeiramente, o conjunto de

vizinhanças a serem utilizadas Nk deve ser definido, uma solução inicial deve ser geradae o algoritmo inicializado. Em seguida, deve-se perturbar a solução atual de acordo como parâmetro k que determina qual vizinhança de Nk será usada. Logo após, devemosrealizar a busca local para melhorar a solução originada a partir da pertubação. Se a buscalocal melhorar a solução então ela deve ser atualizada e o parâmetro k reiniciado, casocontrário, k deve ser atualizado. Esses procedimentos são repetidos até que k atinja ovalor de um máximo kmax. Após isso, se o critério de parada não for atingido, então, k éreiniciado e esse procedimento começa a partir da etapa de pertubação da solução atual.

Figura 2.1: Ilustração da estratégia VNS [Hansen & Mladenovic 2009].

A Figura 2.1 ilustra o funcionamento da metaheurística VNS. Após as vizinhanças ea condição de parada serem definidas, a solução inicial x é criada. A pertubação com aprimeira vizinhança N1 é feita em x e uma nova solução x� é selecionada dentro do espaçopertencente a N1. Em seguida, a busca local é feita a partir de x� e uma nova solução x�� éobtida. Uma vez que x�� é melhor que x, a metaheuristica atualiza x, ou seja, x�� é atribuídaa x. Com um novo melhor ótimo local combinatório x, o algoritmo aplica a pertubaçãode acordo com Nk e consecutivamente a busca local é feita afim de encontrar uma novamelhor solução. Verificamos nesse exemplo que esses dois passos, pertubação mais buscalocal, são realizados três vezes e três vizinhanças - N1, N2 e N3 - são usadas até que umanova melhor solução seja encontrada. Com um novo x, a metaheurística volta a usar avizinhança N1 na pertubação. O algoritmo segue o seu funcionamento até que a condição


de parada seja alcançada.O Algoritmo 7 descreve o funcionamento da metaheurística VNS.

Algoritmo 7 Metaheurística Variable Neighborhood Search1: Selecionar o conjunto de vizinhanças a serem usadas Nk com k = 1, ...,kmax2: x ← soluçãoInicial()3: repetir4: k ← 15: repetir6: x� ← pertubarSolução(Nk,x)7: x�� ← buscaLocal(x�)8: se x�� < x então9: x ← x��

10: k ← 111: senão12: k ← k+113: fim se14: até que k > kmax15: até que critério de parada

2.8 Metodologia Less is more approach - LIMA

A metodologia "Menos é mais", do inglês Less is more approach (LIMA), foi recente-mente proposta por Mladenovic et al. (2016) e vai de encontro com a crescente tendênciana literatura de metaheurísticas híbridas. Estes algoritmos híbridos combinam várias es-tratégias e paradigmas metaheurísticos em um único método para resolver um problemaespecífico.

Ao combinar vários paradigmas de metaheurísticas diferentes em um único método,pode-se perder o controle do quê está atuando melhor ao procurar uma solução e desper-diçar tempo de processamento em estratégias não eficientes.

A metodologia LIMA se concentra em usar o menor conjunto possível de estratégiase metaheurísticas simples para obter a melhor solução. Ao prezar pela simplicidade, estametodologia também ganha em facilidade de implementação.

Isso pode ser verificado para o problema da mínima dispersão diferencial, do inglêsMinimum differential dispertion problem,[Mladenovic et al. 2016] onde uma heurísticabaseada na metaheurística VNS, usando tanto na pertubação quanto na busca local tro-cas de elementos, superou o antigo estado da arte[Duarte et al. 2015] que combinava asmetaheurísticas GRASP, VNS e Exterior path relinking.

Capítulo 3

Método de Pesquisa

Os novos métodos heurísticos propostos neste trabalho adaptam a metaheurística VNS(ver §2.7) seguindo a metodologia LIMA (ver §2.8) para resolver instâncias de agrupa-mento balanceado de dados. Tendo o Algoritmo 7 como base, o seguintes procedimentossão propostos.

3.1 Formulação Matemática

O modelo matemático base do agrupamento balanceado de dados para este trabalhofoi exposto na seção 2.3 e é exibido abaixo:

Min:n

∑i=1

K

∑j=1

xi j�pi − y j�2 (3.1)

Sujeito a:K

∑j=1

xi j = 1 ∀ i = 1,2, ...,n (3.2)

n

∑i=1

xi j =nK

∀ j = 1,2, ...,K (3.3)

xi j ∈ {0,1} ∀ i = 1,2, ...,n, ∀ j = 1,2, ...,K (3.4)

Do teorema de Huygens [Edwards & Cavalli-Sforza 1965] podemos definir matema-ticamente o agrupamento balanceado de dados através de um problema não-linear inteiro.

O teorema de Huygens prova que a soma das distâncias quadráticas de todos os pontosde um dado cluster para o seu centroide é igual a soma das distâncias quadráticas entre ospares de pontos desse cluster dividido pela sua cardinalidade:

CAPÍTULO 3. MÉTODO DE PESQUISA 20

n

∑i=1

xi j�pi − y j�2 =

n−1

∑i=1

n

∑l=i+1

�pi − pl�2xi jxl j

n

∑i=1

xi j

∀ j = 1, ...,K. (3.5)

Definimos C como o conjunto dos índices dos n mod K clusters com �n/K� pontose F como o conjunto dos índices dos K − (n mod K) clusters com �n/K�. Dessa forma,temos o seguinte problema equivalente:

Min:1

�n/K� · ∑j∈C

n−1

∑i=1

n

∑l=i+1

�pi − pl�2xi jxl j +1

�n/K� · ∑j∈F

n−1

∑i=1

n

∑l=i+1

�pi − pl�2xi jxl j

(3.6)

Sujeito a:K

∑j=1

xi j = 1 ∀ i = 1,2, ...,n (3.7)

n

∑i=1

xi j = �n/K� ∀ j ∈C (3.8)

n

∑i=1

xi j = �n/K� ∀ j ∈ F (3.9)

xi j ∈ {0,1} ∀ i = 1,2, ...,n, ∀ j = 1,2, ...,K (3.10)

A equação (3.6) realiza o calculo da função objetivo respeitando o teorema de Huy-gens. A garantia de que todo ponto estará em um único cluster é assegurada pelas equa-ções (3.7). As expressões (3.8) e (3.9) restringem os tamanhos dos clusters a serem iguaisa �n/K� e �n/K� respectivamente. Finalmente, (3.10) definem as variáveis de decisãocomo binárias.

3.2 Solução Inicial

O procedimento adotado para gerar uma solução inicial foi o aleatório. Cada um dospontos do conjunto de dados é selecionado Aleatóriamente através de uma distribuiçãouniforme e alocada em um cluster. No entanto, tomamos precauções para que os tama-nhos dos clusters não violem as restrições que limitam estes números.


Sempre escolhemos o cluster inicial de um ponto de acordo com o a expressão i

mod K, sendo i o contador do número de pontos já inseridos e K o número de clusters.Dessa forma, os clusters selecionado são preenchidos de modo alternado. Por exemplo,se temos 3 clusters, então, eles serão preenchidos na ordem: cluster 1 - cluster 2 - cluster

- 3 - cluster 1 - cluster 2 e assim por diante até que todos os pontos sejam alocados.Esse procedimento pode ser verificado na Figura 3.1 em que pontos escolhidos alea-

toriamente são vinculados a um cluster por vez. Primeiramente, um ponto é designadoao cluster vermelho. Feito isso, outro ponto, selecionado randomicamente, é atribuídoao cluster verde. Da mesma forma, outro ponto é designado ao grupo azul. Finalmente,volta-se a alocar um ponto ao cluster vermelho e assim se segue até que todos os pontossejam designados a um cluster.

Figura 3.1: Criação de uma solução inicial.


3.3 Vizinhança de Troca de Pares de Pontos

Como visto na Seção 2.5 definir uma vizinhança é fundamental para as técnicas usadasnos métodos propostos. A vizinhança de troca de pares de pontos Ni pode ser definidacomo todas as soluções que podemos encontrar a partir de uma solução X através da trocaentre si dos clusters de i pares de pontos.

Figura 3.2: Exemplo de vizinhos de uma solução na vizinhança de troca de um par depontos.

Na Figura 3.2 podemos verificar exemplos de vizinhos encontrados a partir de umasolução X usando a vizinhança de troca de um par de pontos N1(X). Os clusters podemser diferenciados por cor (vermelho e verde) e forma (círculos e losangos).

3.4 Pertubação

A pertubação na solução atual é feita através da troca de pares de pontos escolhidosaleatoriamente de forma uniforme e depende da vizinhança ativa no momento. Esta éregida pela variável k que indica à heurística qual vizinhança deve ser usada e é limi-tada pelo parâmetro kmax. Dessa forma o número de vizinhanças disponíveis depende doparâmetro kmax uma vez que k ∈ [2,kmax]. Consideramos esse intervalo, pois se k = 1trocaríamos somente um par de pontos, logo, a busca local poderia vir a somente desfazera alteração feita pela perturbação não contribuindo na busca de novas boas soluções.

Como prega a simplicidade da metodologia LIMA, uma vizinhança só difere de outra


quanto ao número de trocas de pares de pontos feitas. Quanto maior a ordem de umavizinhança, ou seja, quanto maior o valor de k mais trocas ela faz. Por exemplo, parak = 2 devemos realizar duas trocas de pares, para k = 3, três trocas e assim por diante.

A Figura 3.3 exemplifica o funcionamento do procedimento de pertubação da solução.Partindo de uma solução, pares de pontos de clusters diferentes são selecionados aleatori-amente, representados pelos losangos vazados, para terem os seus clusters trocados entresi, procedimento identificado pelos losangos preenchidos. Nessa figura, a pertubação éexecutada seguindo a segunda vizinhança (k = 2), logo, dois pares de pontos tem os seusclusters trocados entre si.

Figura 3.3: Procedimento de pertubação através da troca de pares de pontos.

3.5 Busca local

A busca local segue a ideia simples de procurar por pares de pontos de clusters dife-rentes em que a troca de clusters entre elas resulte em melhoria na função objetivo, istoé, que o movimento seja aprimorante. Duas estratégias foram empregadas nesse procedi-mento: melhor aprimorante; e primeiro aprimorante. Na estratégia melhor aprimorante,todas as possibilidades de trocas entre pares de pontos são verificadas e o melhor movi-mento aprimorante é feito. Na estratégia primeiro aprimorante, o primeiro movimento


aprimorante encontrado é realizado.Independente da estratégia em vigor, após uma troca ser feita a busca local é reinici-

ada partindo dessa nova solução. A busca local só é concluída quando não existe maisnenhuma troca entre um par de pontos que aperfeiçoe a função objetivo, em outras pala-vras, que um ótimo local tenha sido alcançado.

Para o problema de agrupamento de dados pelo critério da soma mínima das distânciasquadráticas, a atualização dos centroides e do valor de uma solução, após a alteração docluster de um ponto, pode ser feita usando formulas matemáticas [Späth 1980].

Considerando que o ponto pi pertence ao cluster � e será designada ao cluster m, asEquações (3.11), (3.12) e (3.13) podem ser usadas para definir a mudança no valor dafunção objetivo vi,�m e corrigir as coordenadas dos centroides y� e ym respectivamente.Note que S representa a cardinalidade de um cluster. Por exemplo, S� é a quantidade depontos do cluster �.

vi,�m =Sm

Sm +1||pi − y j||2 −

S�S�+1

||pi − y�||2 (3.11)

y� =S�y�− pi

S�−1(3.12)

ym =S�y�+ pi

S�+1(3.13)

Essas fórmulas podem ser aplicadas ao problema de agrupamento balanceado de da-dos se esse procedimento for realizado duas vezes. Se trocarmos os clusters de um parde pontos pi e p j entre si, esses cálculos devem ser feitos para os dois pontos e tem com-plexidade O(d) sendo d a dimensão dos pontos e dos centroides. No entanto, já temos asolução atualizada e nenhuma outra alteração necessita ser executada.

Na busca local, toda vez que se é necessário conferir se um movimento é aprimoranteprecisa-se de O(d) operações, logo, esse procedimento pode se tornar desvantajoso já queé computacionalmente custoso. Por exemplo, ao usar a estratégia melhor aprimorantetemos a ordem de O(n2) operações para verificar todos de pares de pontos, então, essemétodo terá complexidade O(n2d).

Uma vez que transformamos a formulação matemática do problema alvo usando oteorema de Huygens (ver seção § 3.1) e calculamos previamente as distâncias euclidianasquadrádicas entre todos os pontos pi ∈ P e p j ∈ P, podemos acelerar a busca local apli-cando uma estrutura de dados, β, já utilizada por Fiduccia & Mattheyses (1982). Comesta estrutura, somos capazes de identificar um movimento aprimorante com complexi-


dade O(1) ao invés de O(d).Considerando a solução representada por Xt = (a1,a2, ...,an) em que ai indica o clus-

ter no qual o ponto pi está designado, β será uma matriz n×K. Um elemento bi j ∈ βserá a soma das distâncias quadráticas entre o ponto pi e todos os pontos pertencentes aocluster j:

bi j = ∑�:a�= j

�pi − p��2 (3.14)

Essa matriz β necessita de O(n2) operações para ser construída. No entanto, isso sóprecisa ser feito uma única vez durante a execução da heurística, pois é possível atualizá-la em cada alteração da solução com complexidade O(n) conforme veremos a seguir.

Dado um par de pontos pi e p j com os seus clusters identificados respectivamente emai e a j, a variação na função objetivo com as atribuições de pi ao cluster a j e de p j aocluster ai pode ser calculada pela expressão:

Δi j =

�bia j

Sa j

− biai

Sai

�+

�b jai

Sai

−b ja j

Sa j

�− �pi − p j�2

Sai

− �pi − p j�2

Sa j

(3.15)

Se pi é removido do cluster ai então as distâncias quadráticas entre pi e todas osoutros pontos pertencentes ao cluster ai devem ser removidas, ou seja, subtrair biai dafunção objetivo, e as distâncias quadráticas entre pi e todos os pontos de a j devem seradicionadas, em outras palavras, adicionar à função objetivo bia j . Similarmente, o mesmodeve ser feito para p j. As adições de bia j e b jai na função objetivo fazem com que adistância quadrática entre pi e p j seja adicionada duas vezes, contudo, pi e p j não estão nomesmo cluster, logo, deve ser subtraído duas vezes da função objetivo esta distância. Asdivisões pelas cardinalidades dos clusters são feitas com o intuito de respeitar o teoremade Huygens.

Toda vez que alteramos a configuração dos clusters através de uma troca, devemosatualizar alguns elementos da matriz β referentes a esses clusters. Com esse objetivo,dado m = 1, ...,n e assumindo que ai e a j possuem os valores anteriores a troca entre side clusters entre os pontos pi e p j basta adicionar a distância euclidiana quadrática entrepm e p j e subtrair aquela entre pm e pi nas colunas bmai e adicionar a distância euclidianaquadrática entre pm e pi e subtrair a entre pm e p j nas colunas bma j . Isso é expresso pelasEquações (3.16) e (3.17).


bmai ← bmai +�pm − p j�2 −�pm − pi�2 ∀ m = 1, ...,n (3.16)

bma j ← bma j +�pm − pi�2 −�pm − p j�2 ∀ m = 1, ...,n (3.17)

O Algoritmo 8 resume como funciona a busca local usando a política do melhor apri-morante e a estrutura β. A tabela 3.1 lista a nomenclatura usada pelos Algoritmos 8 e9.

Tabela 3.1: Nomenclatura usada nos Algoritmos 8 e 9.

Termo Significado

X solução.�X ótimo local.ai indica o cluster em que i está designado.Δi j variação no valor da função objetivo causada pela troca de clusters do par i e j.δ valor do menor Δi j.ι valor i para se obter δ.ϕ valor j para se obter δ.

Algoritmo 8 Algoritmo da Busca Local com a estratégia melhor aprimorante.1: função BLMelhor(X,β)2: enquanto X �= �X faça3: δ ← 04: para i ← 1 to n−1 faça5: para j ← i+1 to n faça6: se ai �= a j então

7: Δi j ←�

bia jSa j

− biaiSai

�+

�b jaiSai

− b ja jSa j

�− �pi−p j�2

Sai− �pi−p j�2

Sa j

8: se Δi j < δ então9: δ ← Δi j

10: ι ← i11: ϕ ← j12: fim se13: fim se14: fim para15: fim para16: trocar(X ,β, ι,ϕ)17: fim enquanto18: fim função

O Algoritmo 9 descreve o funcionamento da busca local com a estratégia primeiroaprimorante e utilizando a estrutura β.


Algoritmo 9 Algoritmo da Busca Local com a estratégia primeiro aprimorante.1: função BLPrimeiro(X,β)2: enquanto X �= �X faça3: para i ← 1 to n−1 faça4: para j ← i+1 to n faça5: se ai �= a j então

6: Δi j ←�

bia jSa j

− biaiSai

�+

�b jaiSai

− b ja jSa j

�− �pi−p j�2

Sai− �pi−p j�2

Sa j

7: se Δi j < 0 então8: trocar(X ,β, i, j) e ir para linha 29: fim se

10: fim se11: fim para12: fim para13: fim enquanto14: fim função

Capítulo 4

Resultados

4.1 Experimentos Computacionais

Foram escolhidas um total de 16 instâncias para compor o nosso benchmark. Todaselas foram retiradas do endereço http://archive.ics.uci.edu/ml/datasets.html.A Tabela 4.1 lista essas instâncias assim como as suas características.

Tabela 4.1: Instâncias usadas no experimentos computacionais.

Instância Elementos Atributos clustersIris 150 4 3Wine 178 13 3Glass 214 10 7Thyroid 215 5 3Ionosphere 351 34 2Libra 360 90 15User Knowledge 403 5 4Body Measurements 507 5 2Water treatment plant 527 38 13Breast Cancer 569 30 2Synthetic Control 600 60 6Vehicle 846 18 6Vowel Recognition 990 10 11Yeast 1484 8 10Multiple Features 2000 2401 7Image Segmentation 2310 19 7

As colunas da Tabela 4.1 fornecem as seguintes informações:

• coluna "Instância": o nome da instância;• coluna "Elementos": o número de pontos da instância;

1Apenas o item 4.mfeat-pix.

CAPÍTULO 4. RESULTADOS 29

• coluna "Atributos": número de atributos (i.e. dimensão) de um ponto; e• coluna "clusters": número de clusters em que a instância deve ser agrupada.

Todos os experimentos foram realizados na plataforma descrita na Tabela 4.2 e sempreusaram as mesmas soluções iniciais.

Tabela 4.2: Plataforma utilizada nos experimentos.

Arquitetura: 64 bitsProcessador: Intel i7 2.5Ghz x4Memória RAM: 16 GbSistema Operacional Linux Mint 17.1 Cinnamon

4.2 Melhor Aprimorante vs Primeiro Aprimorante

Com o intuito de determinar qual política de verificação dos pares de pontos gera osmelhores resultados, experimentos usando as instâncias Glass, User Knowledge, Yeast

e Multiple Features foram feitos. Para kmax = 20 e utilizado como critério de parada otempo indicado em parenteses, obtemos os dados apresentados na Tabela 4.3.

A Tabela 4.3 exibe os valores do desvio percentual entre uma solução e a melhorsolução conhecida dentre os algoritmos da tabela para uma dada instância. Sendo fm ovalor da melhor solução e fx o valor de uma outra solução, o desvio é calculado de acordocom a seguinte expressão.

Desvio =fx − fm

fm·100 (4.1)

As informações contidas na tabela 4.3 são:

• coluna "Instância": o nome da instância com o tempo máximo de execução emparênteses;

• coluna "Melhor encontrado": valor da função objetivo da melhor solução encon-trada pelos algoritmos da tabela;

• coluna "Melhor": valor do desvio percentual da melhor solução de um dado algo-ritmo em 10 execuções;

• coluna "Média": valor médio do desvio percentual de um dado algoritmo em 10execuções; e

• coluna "Tempo de CPU": tempo de CPU médio gasto por um dado algoritmo.


Tabela 4.3: Desvio percentual da melhor solução encontrada quando as estratégias melhoraprimorante e primeiro aprimorante são usadas.

Instância Desvio(%) Tempo de CPU

Nome(Condição de parada) Melhor encontradoMelhor Aprim. Primeiro Aprim.

Melhor Aprim. Primeiro Aprim.Melhor Média Melhor Média

Glass(20s) 5.047503e+02 0.74 1.40 0.00 1.22 4.22 0.55User Knowledge(30s) 7.021806e+01 0.00 0.81 0.00 0.37 16.95 5.63Yeast(420s) 5.323385e+01 0.21 0.76 0.00 0.21 388.63 267.71Multiple Features(1800s) 1.949141e+06 0.05 0.51 0.00 0.08 1759.56 1283.78

Ao analisar a Tabela 4.3, observa-se que a estratégia primeiro aprimorante atingiu osmelhores resultados em relação à estratégia melhor aprimorante em todas as instânciasque fazem parte do experimento. A estratégia primeiro aprimorante obteve os melhoresresultados tanto na melhor solução encontrada quanto no valor médio das soluções, alémde ser mais rápida para encontrar boas soluções. Esses resultados corroboram o trabalhode Hansen & Mladenovic (2006) para o problema de agrupamento balanceado de dados.Hansen & Mladenovic (2006) mostraram que para o problema do caixeiro viajante, doinglês Travel salesman problem, a estratégia primeiro aprimorante obtêm melhores resul-tados do quê a melhor aprimorante partindo de uma solução inicial aleatória.

4.3 Influência de kmax

O valor ideal de kmax foi determinado executando o método VNS proposto utilizandoas instâncias: Glass; Libra; User knowledge; Water treatment plant; Vowel Recognition;Yeast; Multiple Features; e Image Segmentation. Na busca local foi usada a estratégiaprimeiro aprimorante e as condições de parada para cada conjunto de dados foram ostempos máximo indicados em parênteses. Além disso, os valores do desvio percentualexidos na Tabela 4.4 seguem a Equação 4.1.

Tabela 4.4: Desvio percentual da melhor solução encontrada quando kmax = 5; 10; 15; 20;25.

Instância Desvio(%)

Nome(Condição de parada) Melhor encontrado kmax = 5 kmax = 10 kmax = 15 kmax = 20 kmax = 25Melhor Média Melhor Média Melhor Média Melhor Média Melhor Média

Glass(30s) 5.047503e+02 0.00 1.22 0.00 1.22 0.00 1.21 0.00 1.22 0.00 1.21Libra(30s) 6.384554e+07 0.01 0.25 0.01 0.25 0.00 0.21 0.12 0.21 0.08 0.21User Knowledge(30s) 7.020935e+01 0.02 0.65 0.02 0.55 0.01 0.35 0.02 0.38 0.00 0.35Water Treatment Plant(30s) 7.746106e+09 0.00 1.30 0.00 1.28 0.00 1.28 0.00 1.28 0.00 1.28Vowel Recognition(180s) 1.965948e+03 0.13 0.52 0.00 0.41 0.10 0.43 0.16 0.44 0.00 0.42Yeast(420s) 5.323385e+01 0.02 0.44 0.05 0.27 0.03 0.24 0.00 0.21 0.03 0.23Multiple Features(1800s) 1.949141e+06 0.00 0.06 0.00 0.08 0.00 0.09 0.00 0.08 0.00 0.08Image Segmentation(1500s) 2.107784e+07 0.00 1.02 0.00 0.97 0.00 1.02 0.00 1.01 0.00 1.00

Média 0.02 0.68 0.01 0.63 0.02 0.60 0.04 0.60 0.01 0.60


Os dados da Tabela 4.4 não indicam grandes diferenças nos resultados quando kmax

assume os valores 15, 20 e 25. Ao analisar de forma mais criteriosa, pode-se concluir queo melhor desempenho foi alcançado quando kmax = 25, pois obteve melhores resultadosnos quesitos melhor solução e média das soluções.

Pode-se observar que esse valor de kmax só não gerou a melhor solução para as instân-cias Libra e Yeast, entretanto, essas soluções só estão 0.08% e 0.03% distantes da melhorrespectivamente. Quanto ao desvio percentual das médias das soluções, essa configu-ração obteve os melhores resultados para 4 das 8 instâncias. Para estas instâncias Vowel

Recognition, Yeast, Multiple Features e Image Segmentation, os seus desvios não são maisdistantes do quê 0.02% da melhor média dentre todos os valores usados de kmax.

4.4 Comparação com o Estado da Arte

O código do Balanced k-means de Malinen & Franti (2014) encontra-se em http:

//www2.uef.fi/en/sipu/data-and-software. Além disso, as instâncias listadas naTabela 4.1 foram as usadas nos experimentos computacionais de comparação com o es-tado da arte.

Com base nas Seções 4.2 e 4.3, o método proposto, VNS LIMA, faz uso da pertubaçãopor troca de k pares de pontos com kmax = 25 e da busca local através da troca de paresde pontos usando a estratégia primeiro aprimorante.

Nos experimentos computacionais de comparação com o estado da arte, foi usadocomo critério de parada do VNS LIMA o mesmo tempo de CPU gasto pelo Balanced k-means em cada uma das 10 execuções de cada instância. Além disso, os dois algoritmospartiram das mesmas 10 soluções iniciais para cada instância do benchmark.

Ao confrontar a heurística proposta frente ao estado da arte (Tabela 4.5), os valoresdos desvios percentuais, que seguem a equação 4.1, evidenciam que o VNS LIMA detêmos melhores resultados nos quesitos melhor solução e média das melhores soluções empraticamente todas as instâncias. O Balanced k-means só atinge valores superiores emdois casos: na melhor solução de Vowel recognition; e na média das melhores soluçõesde Water treatment plant. Em ambos, eles não se distanciam mais do que 0,2% dosresultados do método proposto.

A rapidez com que os métodos heurísticos encontram boas soluções pode ser ve-rificada pelos gráficos de tempo até um valor alvo, do inglês time-to-target plots[Aiexet al. 2007]. O valor alvo é determinado ao executar 200 vezes cada um dos métodosBalanced k-means e VNS LIMA para então selecionar o valor da pior de todas as solu-ções. Uma vez determinado o valor alvo, coletamos o tempo ti necessário para que cada


Tabela 4.5: Desvio percentual da melhor solução encontrada pelos métodos Balancedk-means e VNS LIMA.


Nome(no elem.) Melhor encontradoBK-means VNS LIMA

Melhor Média Melhor MédiaIris(150) 8.136720e+01 0.00 0.00 0.00 0.00Wine(178) 3.767275e+06 0.00 0.80 0.00 0.64Glass(214) 5.047503e+02 0.02 1.73 0.00 1.22Thyroid(215) 3.441325e+04 0.00 2.99 0.00 0.11Ionosphere(351) 2.433977e+03 0.00 0.06 0.00 0.03Libra(360) 6.395595e+07 1.48 2.69 0.00 0.17User Knowledge(403) 7.022118e+01 0.00 1.26 0.00 0.54Body(507) 1.136299e+05 0.00 0.08 0.00 0.03Water Treatment Plant(527) 7.746106e+09 0.06 1.08 0.00 1.28Breast Cancer(569) 1.375244e+08 0.00 0.20 0.00 0.09Synthetic Control(600) 1.001825e+06 0.00 0.58 0.00 0.07Vehicle(846) 2.894321e+06 0.00 0.36 0.00 0.00Vowel Recognition(990) 1.965884e+03 0.00 0.60 0.20 0.51Yeast(1484) 5.324765e+01 0.03 0.42 0.00 0.19Multiple Features(2000) 1.949141e+06 0.02 0.43 0.00 0.05Image Segmentation(2310) 2.107874e+07 0.59 1.51 0.00 1.01

uma das 200 execuções de cada um dos algoritmos consiga gerar uma solução de custoigual ou inferior ao valor alvo. Ao i-ésimo menor tempo ti está vinculada a probabilidadeΩi = (i− 1

2)/200 e os pontos zi = (Ωi, ti) são plotados.Os gráficos das Figuras 4.1, 4.2, 4.3 e 4.4 mostram a probabilidade cumulativa dos

algoritmos em atingir o valor da solução alvo ao decorrer do tempo. Os métodos VNSLIMA e Balanced k-means são identificados pela curva de quadrados (azuis) e de xis(vermelhos) respectivamente.


Tempo até a solução alvo

10 -2 10 -1 10 0 10 1 10 2

Pro

ba

bili

da

de

cu

mu

lativa

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1Water Treatment Plant

bk-means

VNS-LIMA

Figura 4.1: Gráfico de tempo em segundos até o alvo dos algoritmos Balanced k-means eVNS LIMA para a instância Water treatment plant.


10 -1 10 0 10 1 10 2 10 3

Pro

ba

bili

da

de

cu

mu

lativa

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1Vehicle

bk-means

VNS-LIMA

Figura 4.2: Gráfico de tempo em segundos até o alvo dos algoritmos Balanced k-means eVNS LIMA para a instância Vehicle.



10 -1 10 0 10 1 10 2 10 3

Pro

ba

bili

da

de

cu

mu

lativa

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1Vowel Recognition

bk-means

VNS-LIMA

Figura 4.3: Gráfico de tempo em segundos até o alvo dos algoritmos Balanced k-means eVNS LIMA para a instância Vowel recognition.


10 0 10 1 10 2 10 3 10 4

Pro

ba

bili

da

de

cu

mu

lativa

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1Multiple Features

bk-means

VNS-LIMA

Figura 4.4: Gráfico de tempo em segundos até o alvo dos algoritmos Balanced k-means eVNS LIMA usando as instâncias Multiple features.

Os gráficos, nas Figuras 4.1, 4.2, 4.3 e 4.4, exibem a curva da probabilidade cumu-lativa do VNS LIMA sempre à esquerda da curva do Balanced k-means nas instânciasanalisadas. Portanto, ao permitir a mesma quantidade de tempo de CPU aos dois algo-ritmos o VNS LIMA sempre é mais rápido em encontrar boas soluções. Nota-se que aheurística proposta é mais ágil inclusive nas instâncias em que ela não obteve os melhores


resultados: Water treatment plant; e Vowel recognition.Também foram realizados experimentos para determinar o quanto se pode melhorar

as soluções geradas pelo Balanced k-means. Ao defini-las como as soluções iniciais eentão executar o VNS LIMA, obtemos os dados da Tabela 4.6.

Nela são listados os percentuais médios de melhoria sobre as soluções do Balancedk-means em 10 execuções e os valores médios desse dado. Além disso, esses resultadosforam coletados após 10, 60 e 300 segundos.

Sendo fBkm,i o valor da solução do Balanced k-means na execução i, fvns,i o valor dasolução do VNS LIMA, obtida a partir da solução do Balanced k-means, na execução i, opercentual médio de melhora foi calculado de acordo com a equação:

Percentual médio de melhora =∑10

i=1( fbkm,i− fvns,i)

fbkm,i

10·100 (4.2)

A tabela 4.6 mostra que o método heurístico proposto é capaz de melhorar as solu-ções do Balanced k-means em várias instâncias. Algumas observações podem ser feitas:em alguns casos, Thyroid e Libra, o percentual de melhora ultrapassou os 2,60%; em 9instâncias não foi possível melhorar a solução ou o ganho foi marginal; em 7 instâncias amelhora foi pequena; e que a maior porção das melhorias foram feitas nos primeiros 10segundos.

Ao analisar as tabelas 4.5 e 4.6, notamos que o algoritmo proposto não conseguiumelhorar em grande escala as soluções do Balanced k-means e que ele foi capaz de obtersoluções ainda melhores quando executado a partir de soluções iniciais aleatórias. Aocruzar as informações contidas nas duas tabelas (4.5 e 4.6), pode-se concluir que muitasvezes a heurística Balanced k-means não é capaz de percorrer uma trajetória no espaçode solução que a leve a uma região de boas soluções se comparada ao VNS LIMA. Porexemplo, ao analisar os dados da instância Wine, o VNS LIMA não consegue melhorara solução do Balanced k-means, ou seja, ambos atingem o desvio percentual médio de0.8%. No entanto, o VNS LIMA obtêm desvio percentual médio de 0.64% partindo deuma solução randômica, portanto, ele percorreu uma trajetória no espaço de busca melhorquando partiu de uma solução aleatória, pois este desvio percentual médio é menor. Omesmo acontece para as instância Thyroid, Ionosphere, User Knowledge, Body, Breast

Cancer, Vehicle, Multiple Features e Image Segmentation.


Tabela 4.6: Percentual médio da melhora feita pelo VNS LIMA a partir das soluções doBalanced k-means.

Instância Melhoria%Nome(no elem.) Após 10s Após 60s Após 300sIris(150) 0.00 0.00 0.00Wine(178) 0.00 0.00 0.00Glass(214) 0.78 0.78 0.80Thyroid(215) 2.62 2.62 2.62Ionosphere(351) 0.00 0.00 0.00Libra(360) 2.52 2.70 2.82UserKnowledge(403) 0.69 0.74 0.74Body(507) 0.00 0.00 0.00WaterTreatmentPlant(527) 0.06 0.06 0.06BreastCancer(569) 0.00 0.00 0.00SyntheticControl(600) 0.49 0.54 0.56Vehicle(846) 0.35 0.35 0.35VowelRecognition(990) 0.02 0.12 0.16Yeast(1484) 0.08 0.18 0.24MultipleFeatures(2000) 0.00 0.01 0.03ImageSegmentation(2310) 0.01 0.01 0.01Média 0.47 0.51 0.52

4.5 Justificativa do Uso da Metodologia LIMA

Para justificar o uso da metologia LIMA, experimentos computacionais são necessá-rios e um algoritmo híbrido baseado nas metaheurísticas VNS e Busca em VizinhançaLarga[Shaw 1998], do inglês Large Neighborhood Search (LNS), foi desenvolvido paraque seus resultados sejam comparados frente ao VNS LIMA. Essa heurística usa além dométodo de pertubação abordado na seção 3.4 outro método para perturbar uma solução,mas utiliza a mesma busca local da abordagem LIMA. Desse modo, busca-se através deum algoritmo mais complexo, porém competitivo, evidenciar as vantagens dessa metolo-gia.

O outro método de pertubação é inspirado em Malinen & Franti (2014), pois resolveum problema de alocação (ver seção 2.4) reduzido e aplica o método destruir e reparar,do inglês destroy and repair, da metaheurística LNS. Esse método tem como objetivocriar uma nova vizinhança ao destruir parte da solução, geralmente com auxílio de umelemento estocástico, para logo em seguida repará-la através de um algoritmo guloso.

Dada a ordem da vizinhança a ser aplicada, determinada pelo valor k, removemos ale-atoriamente, seguindo uma distribuição uniforme, k pontos da solução (destruir). Uma


vez removidos, os centroides dos clusters são recalculados e um problema de alocação,envolvendo esses pontos e os seus antigos clusters, é resolvido de modo ótimo pelo Algo-ritmo Húngaro com complexidade O(n3). A solução desse problema é então usada paradeterminar os novos clusters de cada um dos k pontos removidos.

Com o fim de não violar a restrição de balanceamento, esses pontos só podem seralocados nos novos clusters de acordo com as vagas neles disponíveis. Por exemplo, seno método de pertubação removemos dois pontos do cluster 1 e dois do cluster 2, sópodemos designar esses quatro pontos aos clusters 1 e 2, pois, são os que possuem vagasdisponíveis.

Esse procedimento pode ser conferido detalhadamente na Figura 4.5 em que é mos-trado o funcionamento para a vizinhança com k = 3. Primeiramente, três pontos sãoselecionados aleatoriamente sendo identificados pelos losangos vazados. Posteriormente,esses pontos são desvinculados dos seus atuais clusters (círculos brancos) e os centroidesdos clusters com vagas disponíveis são recalculados (círculos coloridos vazados). Parasolucionar o problema de alocação reduzido, as distâncias quadráticas entre os pontossem cluster e os clusters com vagas são computadas (setas coloridas). Após a resolu-ção do problema de alocação, esses pontos são designados aos clusters de maneira ótima(losangos preenchidos).

Figura 4.5: Funcionamento da pertubação por problema de alocação.

A heurística criada para justificar o uso da metodologia LIMA contem um parâmetros que dita a proporção do uso dos métodos de pertubação usados além do parâmetrokmax. Dessa forma, pode-se controlar a proporção de uso de cada um desses métodosde pertubação. Por exemplo, se s tem valor 0.10 em 10% das vezes a pertubação porresolução de problema de alocação é usada e 90% das vezes a pertubação por trocasaleatórias de pares de pontos é feita. A ordem de execução desses métodos é randômica.


Nos experimentos realizados, foram usadas todas as instâncias da Tabela 4.1, o parâ-metro kmax assumiu o valor 25 e s os valores: 10%; 25%; 50%; e 100%.

A tabela 4.7 reúne os desvios percentuais do valor da melhor solução (mel.) e dovalor da média das melhores soluções (méd.) de um algoritmo em 10 execuções a partirda melhor solução conhecida para cada instância. O valor de s usado é exibido ao ladodo nome "VNS"quando aplicável. O mesmo tempo de CPU gasto pelo Balanced k-meansem cada uma das 10 execuções de cada instância foi usado como critério de parada.

Tabela 4.7: Desvio percentual a partir do valor da melhor solução conhecida obtidospelos algoritmos Balanced k-means, VNS LIMA e VNS com s = {10;25;50;100} paracada instância.


Nome Melhor conhe. BK-means VNS LIMA VNS 10% VNS 25% VNS 50% VNS 100%Mel. Méd. Mel. Méd. Mel. Méd. Mel. Méd. Mel. Méd. Mel. Méd.

Iris 8.136720e+01 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00Wine 3.767275e+06 0.00 0.80 0.00 0.64 0.00 0.64 0.00 0.64 0.00 0.64 0.00 0.49Glass 5.047503e+02 0.02 1.73 0.00 1.22 0.00 1.22 0.00 1.22 0.00 1.22 0.07 1.24Thyroid 3.441325e+04 0.00 2.99 0.00 0.11 0.00 0.11 0.00 0.11 0.00 0.11 0.00 0.09Ionosphere 2.433977e+03 0.00 0.06 0.00 0.03 0.00 0.03 0.00 0.03 0.00 0.03 0.00 0.04Libra 6.382877e+07 1.69 2.90 0.20 0.37 0.04 0.38 0.03 0.34 0.00 0.26 0.19 0.60User Knowledge 7.021558e+01 0.01 1.27 0.01 0.55 0.01 0.45 0.01 0.44 0.00 0.27 0.25 0.96Body 1.136299e+05 0.00 0.08 0.00 0.03 0.00 0.03 0.00 0.03 0.00 0.03 0.00 0.01Water Treatment Plant 7.746106e+09 0.06 1.08 0.00 1.28 0.00 1.28 0.00 1.29 0.00 1.28 0.01 0.84Breast Cancer 1.375244e+08 0.00 0.20 0.00 0.09 0.00 0.09 0.00 0.09 0.00 0.09 0.00 0.09Synthetic Control 1.001825e+06 0.00 0.58 0.00 0.07 0.00 0.06 0.00 0.06 0.00 0.04 0.00 0.07Vehicle 2.894321e+06 0.00 0.36 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.48Vowel Recognition 1.965884e+03 0.00 0.60 0.20 0.51 0.18 0.60 0.08 0.50 0.04 0.52 0.32 1.70Yeast 5.324765e+01 0.03 0.42 0.00 0.19 0.00 0.21 0.01 0.18 0.00 0.21 0.12 0.94Multiple Features 1.949141e+06 0.02 0.43 0.00 0.05 0.00 0.05 0.00 0.06 0.00 0.06 0.02 0.33Image Segmentation 2.107789e+07 0.60 1.52 0.00 1.02 0.00 1.01 0.00 1.01 0.00 1.02 0.02 1.31

Média 0.15 0.94 0.03 0.39 0.01 0.39 0.01 0.37 0.00 0.36 0.06 0.57

Os dados mostram que as heurísticas com s = 10 e s = 50 e VNS LIMA são as maiseficientes. Numericamente, quando usa-se o método baseado na VNS e com s = 50 se ob-têm os melhores resultados tanto nas melhores soluções quanto nas médias das melhoressoluções de 10 execuções.

No entanto, percebemos que as diferenças nas soluções dessas abordagens são mar-ginais e muitas vezes são iguais: Iris; Wine; Glass; thyroid; Ionosphere; Body; Water

treatment plant; Breast cancer; e Vehicle. O algoritmo VNS LIMA é até melhor quandocomparados os valores médios das melhores soluções para as instâncias Vowel recogni-

tion, Yeast e Multiple features.Esses dados revelam a importância de se aplicar a metodologia LIMA para soluções de

problemas de modo heurístico, pois com um menor conjunto de estratégias e com métodos


mais simples foi possível alcançar bons resultados. Além disso, dada a simplicidade deseus procedimentos, a metodologia origina heurísticas muito mais fáceis e rápidas deserem implementadas, logo, tornando-a amigável para diversos tipos de usuários e deaplicações.

Capítulo 5

Considerações Finais

Esta dissertação de mestrado com título: "Abordagem heurística baseada em Buscaem Vizinhança Variável para o Agrupamento Balanceado de Dados pelo critério da somaminima das distâncias quadráticas"contou com o apoio da Coordenação de Aperfeiçoa-mento de Pessoal de Nível Superior - CAPES e teve como objetivo principal criar umnovo método heurístico baseado na metaheurística VNS e na metodologia LIMA que seenquadre na categoria dos algoritmos restringidos pelo balanceamento e que seja capazde obter rapidamente boas soluções.

Detre os objetivos específicos temos: identificar formas simples e eficientes de se per-turbar uma solução; identificar maneiras simples e precisas de se realizar a busca local;projetar e implementar o método heurístico proposto; testar empiricamente quais estraté-gias de funcionamento da busca local geram melhores soluções; e analisar experimental-mente e justificar o potencial da metodologia LIMA.

O novo método heurístico, baseado na metaheurística VNS e na metodologia LIMA,proposto é capaz de gerar boas soluções para o problema de agrupamento balanceado dedados com o critério da soma mínima das distâncias quadráticas.

Quando confrontado face ao algoritmo estado da arte, Balanced k-means, o métodoproposto foi superior tanto em qualidade das soluções encontradas quanto em velocidade.

Os experimentos computacionais também indicam que a estratégia primeiro aprimo-rante gera soluções melhores do que as soluções obtidas quando utilizamos a metodologiado melhor aprimorante.

Ao comparar a heurística desenvolvida com outra mais complexa, o uso da metodo-logia Less is More Approach - LIMA foi justificado devido aos bons resultados obtidos.Além disso, a metodologia LIMA preservou a simplicidade dos métodos aplicados semtornar difícil a sua implementação.

Os seguintes direcionamentos futuros são propostos. Primeiro, deve-se investigar no-vos paradigmas de representação das soluções para o problema alvo e aplicá-los no mé-

CAPÍTULO 5. CONSIDERAÇÕES FINAIS 41

todo proposto. Segundo, devemos aplicar novas estratégias de verificação de pares depontos na busca local visando o aperfeiçoamento da heurística proposta. Finalmente, éinteressante estender os métodos propostos para o problema de agrupamento balanceadode dados por restrições de tamanho modelado pelas expressões (2.12)-(2.15).

Referências Bibliográficas

Aiex, Renata M, Mauricio GC Resende & Celso C Ribeiro (2007), ‘Ttt plots: a perlprogram to create time-to-target plots’, Optimization Letters 1(4), 355–366.

Aloise, Daniel, Amit Deshpande, Pierre Hansen & Preyas Popat (2009), ‘Np-hardness ofeuclidean sum-of-squares clustering’, Machine Learning 75(2), 245–248.

Boussaïd, Ilhem, Julien Lepagnot & Patrick Siarry (2013), ‘A survey on optimization me-taheuristics’, Information Sciences 237, 82 – 117. Prediction, Control and Diagnosisusing Advanced Neural Computations.

Bradley, PS, KP Bennett & Ayhan Demiriz (2000), ‘Constrained k-means clustering’,Microsoft Research, Redmond pp. 1–8.

Burkard, Rainer E, Mauro Dell’Amico & Silvano Martello (2009), Assignment Problems,

Revised Reprint, Siam.

Desrosiers, J., N. Mladenovic & D. Villeneuve (2005), ‘Design of balanced mba studentteams’, Journal of the Operational Research Society 56(1), 60–66.URL: http://dx.doi.org/10.1057/palgrave.jors.2601775

Duarte, Abraham, Jesús Sánchez-Oro, Mauricio G.C. Resende, Fred Glover & RafaelMartí (2015), ‘Greedy randomized adaptive search procedure with exterior path re-linking for differential dispersion minimization’, Information Sciences 296, 46 – 60.URL: http://www.sciencedirect.com/science/article/pii/S0020025514009906

Edwards, A. W. F. & L. L. Cavalli-Sforza (1965), ‘A method for cluster analysis’, Biome-

trics 21(2), 362–375.URL: http://www.jstor.org/stable/2528096

Fiduccia, C. M. & R. M. Mattheyses (1982), A linear-time heuristic for improvingnetwork partitions, em ‘Design Automation, 1982. 19th Conference on’, pp. 175–181.

42

REFERÊNCIAS BIBLIOGRÁFICAS 43

Garey, Michael R & David S Johnson (1979), ‘A guide to the theory of np-completeness’,WH Freemann, New York .

Gong, Yanlin, Gong Chen & Liansheng Tan (2008), A balanced serial k-means basedclustering protocol for wireless sensor networks, em ‘Wireless Communications,Networking and Mobile Computing, 2008. WiCOM ’08. 4th International Confe-rence on’, pp. 1–6.

Hansen, Pierre & Nenad Mladenovic (2006), ‘First vs. best improvement: An empiricalstudy’, Discrete Applied Mathematics 154(5), 802–817.

Hansen, Pierre & Nenad Mladenovic (2009), Encyclopedia of Optimization, Springer US,Boston, MA, pp. 3975–3989.

He, Ruhan, Weibin Xu, Jiaxia Sun & Bingqiao Zu (2009), Balanced k-means algorithmfor partitioning areas in large-scale vehicle routing problem, em ‘Intelligent Infor-mation Technology Application, 2009. IITA 2009. Third International Symposiumon’, Vol. 3, pp. 87–90.

Jain, Anil K. (2010), ‘Data clustering: 50 years beyond k-means’, Pattern Recognition

Letters 31(8), 651 – 666. Award winning papers from the 19th International Con-ference on Pattern Recognition (ICPR)19th International Conference in Pattern Re-cognition (ICPR).

Kuhn, Harold W (1955), ‘The hungarian method for the assignment problem’, Naval

research logistics quarterly 2(1-2), 83–97.

Lenstra, Jan Karel (1997), Local search in combinatorial optimization, Princeton Univer-sity Press.

Liao, Yifan, Hongsheng Qi & Wenyuan Li (2013), ‘Load-balanced clustering algorithmwith distributed self-organization for wireless sensor networks’, Sensors Journal,

IEEE 13(5), 1498–1506.

MacQueen, James & et al (1967), Some methods for classification and analysis of mul-tivariate observations, em ‘Proceedings of the fifth Berkeley symposium on mathe-matical statistics and probability’, Vol. 1, Oakland, CA, USA., pp. 281–297.

Malinen, Mikko I. & Pasi Franti (2014), Balanced K-Means for Clustering, em Franti,P and Brown, G and Loog, M and Escolano, F and Pelillo, M, ed., ‘STRUCTU-

REFERÊNCIAS BIBLIOGRÁFICAS 44

RAL, SYNTACTIC, AND STATISTICAL PATTERN RECOGNITION’, Vol. 8621de Lecture Notes in Computer Science, pp. 32–41.

Mladenovic, Nenad, Raca Todosijevic & Dragan Urosevic (2016), ‘Less is more: Basicvariable neighborhood search for minimum differential dispersion problem’, Infor-

mation Sciences 326, 160 – 171.URL: http://www.sciencedirect.com/science/article/pii/S0020025515005526

Mladenovic, N. & P. Hansen (1997), ‘Variable neighborhood search’, Computers & Ope-

rations Research 24(11), 1097 – 1100.

Nallusamy, R, K Duraiswamy, R Dhanalaksmi & P Parthiban (2010), ‘Optimization ofnon-linear multiple traveling salesman problem using k-means clustering, shrinkwrap algorithm and meta-heuristics’, International Journal of Nonlinear Science

9(2), 171–177.

Shaw, Paul (1998), Using constraint programming and local search methods to solve vehi-cle routing problems, em ‘International Conference on Principles and Practice ofConstraint Programming’, Springer, pp. 417–431.

Shin, Heewook, Sangman Moh, Ilyong Chung & Moonsoo Kang (2015), ‘Equal-size clus-tering for irregularly deployed wireless sensor networks’, Wireless Personal Com-

munications 82(2), 995–1012.

Späth, Helmuth (1980), Cluster analysis algorithms for data reduction and classification

of objects, Vol. 4, Halsted Pr.

Su, Wenbo, Jie Hu, Chuang Lin & Sherman Shen (2015), Sla-aware tenant placementand dynamic resource provision in saas, em ‘Web Services (ICWS), 2015 IEEEInternational Conference on’, IEEE, pp. 615–622.

Xiaoyan, Kui, Wang Jianxin, Zhang Shigeng & Cao Jlannong (2015), ‘Energy balancedclustering data collection based on dominating set in wireless sensor networks.’,Adhoc and Sensor Wireless Networks 24(3/4), 199 – 217.

Zhu, Shunzhi, Dingding Wang & Tao Li (2010), ‘Data clustering with size constraints’,Knowledge-Based Systems 23(8), 883 – 889.URL: http://www.sciencedirect.com/science/article/pii/S095070511000095X

Documents

Abordagem heurística baseada em Busca em Vizinhança Variável … · 2017-10-20 · de acordo com experimentos realizados nesta pesquisa. Os experimentos computacionais mostram