A branch-and-cut SDP-based algorithm for minimum sum-of-squares clustering

AUTOR(ES)

Aloise, Daniel, Hansen, Pierre

FONTE

Pesquisa Operacional

DATA DE PUBLICAÇÃO

2009-12

RESUMO

Clusterização por soma mínima de distâncias quadráticas consiste em particionar um dado conjunto de n pontos em k clusters a fim de minimizar a soma das distâncias quadráticas entre os pontos e o centróide de seus respectivos clusters. Recentemente, Peng & Xia (2005) estabeleceram a equivalência entre o problema e programação semidefinida 0-1. Neste artigo, um algoritmo branch-and-cut é proposto para o modelo baseado em programação semidefinida 0-1. O algoritmo obtém soluções exatas para instâncias reais de grande porte em tempos computacionais comparáveis àqueles do melhor método exato proposto na literatura.

ASSUNTO(S)

clusterização soma de distâncias quadráticas programação semidefinida

Documentos Relacionados

• O problema de coleta e entrega com janelas de tempo na indústria petrolífera: modelos e métodos branch-and-cut
• ScottKnott: a package for performing the Scott-Knott clustering algorithm in R
• Optimal image quantization, perception and the median cut algorithm
• A new clustering algorithm for tridimensional gene expression data
• ALGORITHM RELAX-AND-CUT FOR THE 0-1 QUADRATIC KNAPSACK PROBLEM