AI - Aprendizado Não Supervisionado

Inteligência Artificial
Aprendizado Não Supervisionado - K-Means

Você está em: MarMSX >> Cursos >> AI Foi visto no capítulo anterior, que podemos ensinar ao computador como aprender determinados padrões para que posteriormente possa reconhecê-los. Entretanto, os métodos de aprendizado supervisionado têm sempre a necessidade da presença de um "professor" para ensinar ao computador a distinguir e reconhecer padrões.
Os algoritmos de aprendizado não supervisionados tem o objetivo de fazer com que o computador tenha a capacidade de descobrir padrões sozinho.
Por exemplo, seja o seguinte conjunto de dados:

Para nós, humanos, é simples e natural identificarmos dois agrupamentos ou classes de dados no gráfico anterior. Sem ensinar ao computador, como fazer com que ele possa identificar os agrupamentos de dados?
A idéia por trás dos algoritmos de aprendizado não supervisionado é agrupar dados com características semelhantes, conforme veremos na seção a seguir.
K-Means K-Means é um algoritmo de classificação iterativo, cujo objetivo é encontrar agrupamento de dados com informações similares (padrões).
A idéia básica é fazer o seguinte: para um dado conjunto de X

X = (x₁, x₂, ..., x_n)

criar K sub-conjuntos de X. Cada sub-conjunto é representado por um centróide C

C = (c₁, c₂, ..., c_k)

Em cada iteração do K-Means, ele irá:

Associar elementos aos centróides:
- Para cada elemento de X, associe-o ao sub-conjunto do centróide mais próximo.
Recalcular os centróides:
- Após as associações, calcular os novos valores de centróides baseado na média dos elementos de cada sub-conjunto.
O algoritmo é interrompido quando todos os centróides não se alterarem entre uma iteração e outra.

Valores iniciais dos centróides O conjunto X é uma massa de dados qualquer, onde nada sabemos a priori sobre os padrões existentes ali, e cujo objetivo é exatamente encontrá-los. Dado que nada sabemos sobre os padrões dos dados e dos agrupamentos, naturalmente os centróides são desconhecidos.
Para a solucionar esse problema, retiramos do conjunto X um número K de elementos aleatoriamente e atribuímos como valores iniciais dos centróides seus respectivos valores.
Outro problema, é que o número K de sub-conjuntos é desconhecido. Assim, o usuário deverá fornecer esse número. Para o problema apresentado no inicio desse capítulo, podemos atribuir o valor de K igual a 2, ou seja, há dois agrupamentos nos dados.
Sendo assim, escolhemos aleatoriamente 2 elementos do conjunto X como os valores iniciais dos centróides, conforme mostra a figura a seguir. O centróide 1 está assinalado em vermelho, enquanto que o centróide 2 está assinalado em verde.

Conforme o programa for rodando, os centróides serão ajustados até a posição correta deles. Veremos como a seguir.
Passo 1: associar elementos aos centróides Após determinarmos os valores iniciais dos centróides, devemos associar cada elemento X do conjunto de dados ao centróide mais próximo. Não importando quantas dimensões tiver cada elemento, ele será associado ao centróide pelo valor da distância até ele. O cálculo da distância é geralmente realizado através da Distância Euclidiana:

Onde:

i é o i-ésimo elemento de X.
j é o j-ésimo centróide de C.
d é a d-ésima dimensão de ambos.

A figura a seguir mostra a associação de dois elementos de X ao respectivo centróide mais próximo.

Passo 2: recalcular os centróides No passo anterior, criamos novos agrupamentos de dados. Dessa forma, o centro de massa ou o centróide dos grupos é modificado. Observe a figura a seguir os novos agrupamentos e que os centróides antigos (assinalados com círculos pretos) já não representam os novos agrupamentos.

Dessa forma, os novos valores dos centróides serão a média de cada dimensão (atributo) dos dados. O resultado do cálculo dos novos centróides pode ser visto a seguir, onde cada centróide é assinalado pela letra "X".

Acabou? Não! Repetimos os passos 1 e 2 até que os centróides não se movam mais.
Convergência Quando os valores de todos os centróides se repetirem de uma interação para a outra, houve convergência e o programa deverá parar.
Veja a evolução das classes e centróides durante as iterações do programa para classificar os dados do exemplo.

1a. iteração

2a. iteração

3a. iteração

E se os dados de cada grupo não fossem tão bem separados como no exemplo acima? Isto significa que os atributos (características) utilizados para classificar não são bons o suficiente para discriminar as classes. Nesse caso, procure por outros atributos.
Um exemplo em Basic MSX O programa em Basic a seguir utilizará os dados do repositório UCI [3] para a flor íris, onde iremos classificar com o K-Means os agrupamentos das flores íris do tipo setosa e versicolor através das medidas de comprimento e largura das pétalas.

5 ' K-Means - MarMSX 2020
10 SCREEN 0:COLOR 15,0,0:WIDTH 40:KEY OFF
20 PRINT"Preparando dados ...":GOSUB 700
40 PRINT"Iniciando ajuste ..."
50 R=1
100 '
101 ' Clusters iniciais
102 '
110 C1=18 : C2=19
120 C(1,1)=P(C1,1):C(1,2)=P(C1,2)
130 C(2,1)=P(C2,1):C(2,2)=P(C2,2)
200 '
201 ' K-Means - classificacao
202 '
205 PRINT"Rodada:";R
210 FOR I=1 TO 100
220 DMIN=500
230 FOR CL=1 TO 2
240 D=SQR((P(I,1)-C(CL,1))^2 + (P(I,2)-C(CL,2))^2)
250 IF D<DMIN THEN DMIN=D : MC=CL
260 NEXT CL
270 P(I,3)=MC
280 NEXT I
300 '
301 ' K-Means - novos clusters
302 '
310 CB(1,1)=C(1,1):CB(1,2)=C(1,2):CB(2,1)=C(2,1):CB(2,2)=C(2,2)
320 N(1)=0:N(2)=0:C(1,1)=0:C(1,2)=0:C(2,1)=0:C(2,2)=0
330 FOR I=1 TO 100
340 N(P(I,3)) = N(P(I,3))+1
350 C(P(I,3),1) = C(P(I,3),1) + P(I,1)
360 C(P(I,3),2) = C(P(I,3),2) + P(I,2)
370 NEXT I
380 C(1,1) = C(1,1)/N(1) : C(1,2) = C(1,2)/N(1)
390 C(2,1) = C(2,1)/N(2) : C(2,2) = C(2,2)/N(2)
400 '
401 ' Avalia convergencia
402 '
410 IF C(1,1)<>CB(1,1) OR C(1,2)<>CB(1,2) OR C(2,1)<>CB(2,1) OR C(2,2)<>CB(2,2) THEN R=R+1: GOTO 205
420 PRINT"Convergiu":PRINT"Avaliando resultados ..."
500 '
501 ' Avalia resultados
502 '
510 TE=0
520 FOR I=1 TO 100
530 IF P(I,3)=2 AND I<51 THEN TE=TE+1
540 IF P(I,3)=1 AND I>50 THEN TE=TE+1
550 NEXT I
560 PRINT"Total de erros:";TE
570 PRINT:PRINT"Centroide 1:";C(1,1);",";C(1,2)
580 PRINT"Centroide 2:";C(2,1);",";C(2,2)
590 PRINT:PRINT"Tecle algo para ver graficamente ..."
600 A$=INPUT$(1)
610 GOTO 1000
700 '
701 ' Define 100 pontos - IRIS setosa/versicolor
702 '
710 NP=100
720 DIM P(NP,3)
730 FOR I=1 TO NP
740 READ P(I,1),P(I,2)
750 NEXT I
760 RETURN
800 DATA 1.4,0.2,1.4,0.2,1.3,0.2,1.5,0.2,1.4,0.2,1.7,0.4
810 DATA 1.4,0.3,1.5,0.2,1.4,0.2,1.5,0.1,1.5,0.2,1.6,0.2
820 DATA 1.4,0.1,1.1,0.1,1.2,0.2,1.5,0.4,1.3,0.4,1.4,0.3
830 DATA 1.7,0.3,1.5,0.3,1.7,0.2,1.5,0.4,1.0,0.2,1.7,0.5
840 DATA 1.9,0.2,1.6,0.2,1.6,0.4,1.5,0.2,1.4,0.2,1.6,0.2
850 DATA 1.6,0.2,1.5,0.4,1.5,0.1,1.4,0.2,1.5,0.2,1.2,0.2
860 DATA 1.3,0.2,1.4,0.1,1.3,0.2,1.5,0.2,1.3,0.3,1.3,0.3
870 DATA 1.3,0.2,1.6,0.6,1.9,0.4,1.4,0.3,1.6,0.2,1.4,0.2
880 DATA 1.5,0.2,1.4,0.2,4.7,1.4,4.5,1.5,4.9,1.5,4.0,1.3
890 DATA 4.6,1.5,4.5,1.3,4.7,1.6,3.3,1.0,4.6,1.3,3.9,1.4
900 DATA 3.5,1.0,4.2,1.5,4.0,1.0,4.7,1.4,3.6,1.3,4.4,1.4
910 DATA 4.5,1.5,4.1,1.0,4.5,1.5,3.9,1.1,4.8,1.8,4.0,1.3
920 DATA 4.9,1.5,4.7,1.2,4.3,1.3,4.4,1.4,4.8,1.4,5.0,1.7
930 DATA 4.5,1.5,3.5,1.0,3.8,1.1,3.7,1.0,3.9,1.2,5.1,1.6
940 DATA 4.5,1.5,4.5,1.6,4.7,1.5,4.4,1.3,4.1,1.3,4.0,1.3
950 DATA 4.4,1.2,4.6,1.4,4.0,1.2,3.3,1.0,4.2,1.3,4.2,1.2
960 DATA 4.2,1.3,4.3,1.3,3.0,1.1,4.1,1.3
1000 '
1001 ' Plota resultado
1002 '
1010 SCREEN 2:FX=255/6:FY=191/2
1020 FOR I=1 TO 100
1030 X=P(I,1)*FX : Y=191-P(I,2)*FY
1040 IF P(I,3)=1 THEN C=2 ELSE C=5
1050 PSET(X,Y),C
1060 NEXT I
1070 GOTO 1070

Referências

1. K-Means Clustering, Wikipedia. Em http://en.wikipedia.org/wiki/K-means_clustering
2. Otimização da Paleta de Cores, Artigo. Em: http://marmsx.msxall.com/artigos.
3. Iris, Repositório de dados da UCI. Em http://archive.ics.uci.edu/ml/index.php

<< Anterior

Próxima >>