Uma diferença importante entre as técnicas de agrupamento é se essas geram ou não grupos aninhados. Em outras palavras, se o agrupamento é hierárquico ou particional. No agrupa- mento hierárquico, apresentado na subseção (2.4.1) anterior, o agrupamento funde ou partici- ona os grupos a cada iteração, resultando em uma hierarquia de grupos. Já no agrupamento particional, os dados são divididos diretamente em um número K de grupos não havendo uma
2.4 - Técnicas de Agrupamento 17
hierarquia entre os grupos (Xu & Wunsch, 2005). Em termos teóricos, para encontrar o melhor particionamento dos dados, poderia ser listada todas as possibilidades de agrupamento e tomar o melhor deles segundo algum critério específico. Entretanto, o custo computacional para cal- cular e analisar todas as possibilidades é extremamente alto (Liu, 1968). Por exemplo, tomando um conjunto de dados composto por 30 objetos onde se deseja particiona-lo em 3 grupos, o número de possibilidades de agrupamento é 2 ⇥ 1014. Assim, algoritmos heurísticos foram
desenvolvidos para tentar encontrar boas soluções aproximadas.
O objetivo do agrupamento de dados é encontrar uma partição dos dados de tal forma que os objetos que formam os grupo sejam homogêneos entre si e os dados de grupos diferentes estejam bem separados (Xu & Wunsch, 2005). Essa homogeneidade e separação podem ser avaliadas por uma função objetiva. Uma das funções mais conhecidas é a soma dos erros quadrados. Supondo que o conjunto de dados seja formado por xj 2 <d, j = 1, . . . , N e
deseja-se particiona-los em K grupos C = {C1, . . . , CK}, então, a soma dos erros quadrados
pode ser definida pela Equação 2.2:
Js(Γ, M ) = K X i=1 N X j=1 γij k xj− mi k2 = K X i=1 N X j=1 γij(xj− mi)T(xj − mi) (2.2)
onde Γ = {γij} é a matriz de particionamento tal que
γij = ( 1 se xj 2 ao grupo i 0 caso contrário sendo que K X i=1 γij = 18j
e M = [m1, . . . , mK] é a matriz de centróides onde cada centróide mi é definido pela Equação
2.3. mi = 1 Ni N X j=1 γijxj (2.3)
A partição que minimiza a função da soma dos erros quadrados é considerada ótima. Essa função objetiva é apropriada para grupos compactos e bem separados. Entretanto, essa fun- ção pode ser sensível a outliers fazendo com que grupos grandes sejam quebrados em grupos menores e agrupados de forma errada.
K-Médias
O algoritmo K-Médias (Forgy, 1965; Macqueen, 1967; Bock, 2007) é um dos mais conhe- cidos algoritmos de agrupamento de dados. O algoritmo busca o melhor particionamento dos dados tentando minimizar iterativamente a função das somas dos erros quadrados (Eq. 2.2). Inicialmente o K-Médias posiciona de forma aleatória K centróides que representam os centros de cada grupo. Cada ponto xi é associado ao centróide Clmais próximo e o conjunto de pontos
associados a cada centróide representa um grupo. Então, cada centróide é movido em direção ao ponto central (média dos pontos) de cada conjunto e as associações de pontos aos centróides são refeitas. O processo de mover os centróides pára quando todos os pontos não mudam suas associações ou apenas uma pequena parcela deles mudem. O Algoritmo 2 descreve o K-Médias em passos.
Algoritmo 2: K-Médias
1 Posicionar K centróides aleatoriamente, ou seja, iniciar a matriz M aleatoriamente; 2 repita
3 Associe cada ponto ao centróide mais próximo;
4 Recalcular a posição dos k centróides;
5 até até que os grupos não mudem;
A Figura 2.6 ilustra um exemplo de iteração do algoritmo K-Médias para um conjunto de dados. Inicialmente, na Figura 2.6(a), são posicionados três centróides de forma aleatória e cada ponto é associado ao centróide mais próximos. Cada centróide é representado pelo símbolo ‘+’ e os grupos são representados por pontos de mesmo desenho. As iterações seguintes são ilustradas pelas Figuras 2.6(b), 2.6(c) e 2.6(d), nessa ordem, sendo possível observar ao longo da execução as mudanças das associações e o reposicionamento dos centróides. Na última iteração tem-se o resultado do agrupamento onde cada centróide está localizado no ponto médio de cada grupo.
(a) (b) (c) (d)
Figura 2.6: Exemplo de iterações para o algoritmo K-Médias. A Figura (a) exibe o posicionamento inicial aleatório dos centróides. Cada centróide é representado pelo símbolo ‘+’ e os grupos por pontos de mesmo símbolo. As Figuras (b), (c) e (d), nessa ordem, mostram as iterações seguinte do algoritmo, onde é possível observar o reposicionamento dos centróides e a reassociação dos pontos. Na última iteração cada centróide está localizado no ponto médio de cada grupo (Tan et al., 2005).
2.4 - Técnicas de Agrupamento 19
O algoritmo K-Médias não garante que seja encontrado o ótimo global da função das somas dos erro quadrados, mas é provado que, pelo menos, converge para um mínimo local (Selim & Ismail, 1984). Isso implica que a maneira a qual são iniciados os centróides influencia na convergência do algoritmo. Em outras palavras, a escolha inicial dos centróides pode fazer com que esses convirjam para pontos diferentes. Isso faz com que uma boa escolha inicial dos pon- tos leve a um bom particionamento dos dados. Entretanto, não existe um método universal e eficiente para determinar os centróides iniciais (Xu & Wunsch, 2008). Para tentar solucionar esse problema, alguns métodos foram desenvolvidos. Krishna & Narasimha Murty (1999) pro- puseram o algoritmo GKA que integra o K-Médias com algoritmo genético na tentativa de fazer uma busca global e diminuir o tempo de convergência.
Outra importante questão sobre o algoritmo K-Médias está relacionado ao número desejado de grupos K. Esse algoritmo supõem que o usuário saiba a priori o número de agrupamentos de dados, entretanto, isso na maioria das vezes não ocorre. Para resolver o problema de encontrar o número de grupos K também não existe um método universal e eficiente para todos os casos. Algumas heurísticas foram utilizadas para tentar resolver esse problema. Ball & Hall (1967) propuseram o algoritmo ISODATA, que estima K agrupando ou fundindo grupos de acordo com um parâmetro limitante. Um grupo é dividido de acordo com a variabilidade dos dados de um grupo. Grupos são fundidos de acordo com a distância de seus centróides. Assim, a cada iteração desse algoritmo, encontra-se um K que é utilizado para encontrar o K da próxima iteração.
Quanto a robustez, o K-Médias é sensível a ruído e outliers. Para calcular o ponto médio são utilizados todos os pontos do grupo, incluindo os outliers. Mesmo que um objeto esteja longe do centróide ele é forçado a pertencer à aquele grupo e isso pode atrapalhar o algoritmo a encontra a forma correta do grupo. O algoritmo ISODATA trata os outliers eliminando os grupos que tenham menos elementos que um dado valor passado pelo usuário e, devido ao seu processo de fusão, não permite a possibilidade de grupos de forma muito alongadas. O algoritmo PAM (Kaufman & Rousseeuw, 1990) também trata outliers utilizando o conceito de medóide, que é um ponto real do conjunto de dados que tenha a menor distância média para todos os outros pontos do grupo.