Anais > Edição Atual > Anais do XV WCF 2019 > Revisão de Estratégias para a Aceleração do Algoritmo k-Means

Revisão de Estratégias para a Aceleração do Algoritmo k-Means

Autores: Marcelo Kuchar Matte, Maria do Carmo Nicoletti

O algoritmo k-Means é reconhecidamente um dos algoritmos de Aprendizado de Má-quina (AM) mais populares, dentre os algoritmos caracterizados como algoritmos de agrupamento. Como relatado em [Wikipedia 2019] o termo k-Means foi empregado pela primeira vez em 1967, por James MacQueen, em [MacQueen 1967], muito embora o procedimento descrito pelo algoritmo esteja ligado a Hugo Steinhaus desde 1956 [Stei-nhaus 1957]. O k-Means padrão, também referenciado como standard ou como básico, foi proposto em 1957 por Lloyd [Lloyd 1957], como uma técnica para a ondulação pul-se-code e não foi publicado fora do Latoratório Bell até 1982, quando então foi publi-cado em [Lloyd 1982]. Em 1965 E. W. Forgy publicou essencialmente o mesmo méto-do em [Forgy 1965], razão pela qual o algoritmo é também referenciado em algumas publicações como algoritmo Lloyd-Forgy. Uma versão mais eficiente foi proposta e publicada em Fortran, por Hartigan & Wong, em [Hartigan & Wong 1979]. Desde a sua proposta o k-Means, além de ter sido usado em um grande volume de aplicações nos mais variados domínios de conhecimento, tem também sofrido inúmeras críticas, com relação a algumas de suas características. Particularmente muitas tentativas de melho-ramento de sua fase de inicialização foram publicadas, como aquelas descritas em [Bradley & Fayyad 1998] [Maedeh & Suresh 2013] [Kahn & Ahmad 2004], bem como podem ser evidenciados inúmeros trabalhos que propõem estratégias com o objetivo de acelerar o tempo de execução do algoritmo.

DOCUMENTO COMPLETO

• Revisão de Estratégias para a Aceleração do Algoritmo k-Means