El algoritmo de fuzzy c-means clustering  Presentación |
Este algoritmo de agrupamiento es una variante del algoritmo k-means clustering. La diferencia entre ambos radica en que en este último cada dato pertenece a un único grupo (identificado como 1 en la matriz de pertenencias u), el algoritmo de fuzzy c-means permite la existencia de pertenencia parcial de un dato a más de un grupo. Otra diferencia radica en el método de actualizar los centroides. Para mostar el principio del algoritmo, supóngase que se dispone del siguiente conjunto de datos: >> z=[1 1 1 2 3 4 5 5 5; 1.5 2 2.5 2 2 2 1.5 2 2.5] Si se desean obtener dos centroides (c=2), estos pueden inicializarse dentro del intervalo de definición de los datos: >> v=[1 2.25; 5 1.25];
tal y como muestra la siguiente figura
La pertenencia de los datos a cada centroide se calcula utilizando la siguiente ecuación para lo que se puede utilizar el siguiente programa % Datos de entrada
x=[1 1 1 2 3 4 5 5 5]';
y=[1.5 2 2.5 2 2 2 1.5 2 2.5]';
z=[x, y];
% Centroides iniciales
v=[1 2.25; 5 1.25];
% Condiciones iniciales
m=2; c=2;
% Tamaño de matriz de datos
[L,D]=size(z);
% Se calcula los grados de pertenencia
for l=1:L
for j=1:c
%Suma de distancias
suma(j)=sum((z(l,1)-v(j,1))^2+(z(l,2)-v(j,2))^2);
end
for j=1:c
sumaa(j)=0;
for i=1:c
sumaa(j)=sumaa(j)+suma(j)/suma(i);
end
% Matriz de pertenencias
u(l,j)=1/sumaa(j)
end
end |
Los grados de pertenecia resultan
>>u'
u=
0.9662 0.9962 0.9965 0.9000 0.5290 0.1471 0.0038 0.0338 0.0887
0.0338 0.0038 0.0035 0.1000 0.4710 0.8529 0.9962 0.9662 0.9113 Lo cual puede interpretarse como que los cinco primeros valores pertenecen al grupo o centroide 1 y los restantes 4 al centroide 2. Una vez que se calcula los grados de pertenencia de cada valor de la matriz de datos a cada centroide, se deben actualizar el valor de los centroides, para lo que se aplica la siguiente ecuación lo que puede implementarse a través del siguiente programa % Determinar el nuevo valor de los centroides
for j=1:c
vn(1)=0; vn(2)=0;
vd(1)=0; vd(2)=0;
for l=1:L
%Primer término del centroide
vn(1)=vn(1)+u(l,j)^2*z(l,1);
vd(1)=vd(1)+u(l,j)^2;
% Segundo término del centroide
vn(2)=vn(2)+u(l,j)^2*z(l,2);
vd(2)=vd(2)+u(l,j)^2;
end
v(j,1)=vn(1)/vd(1);
v(j,2)=vn(2)/vd(2);
end |
lo cual actualiza el nuevo valor de los centroides a:
v =
1.3641 2.0083
4.6756 1.9781
Si se vuelve a recalcular la matriz de pertenencia resulta >> u'
0.9723 0.9903 0.9736 0.9465 0.5120 0.0617 0.0242 0.0079 0.0273
0.0277 0.0097 0.0264 0.0535 0.4880 0.9383 0.9758 0.9921 0.9727 y reactualizar los valores que representan a los centroides v =
1.3560 2.0003
4.6576 1.9992 El resultado se muestra en la siguiente figura Función cmeans en Matlab El toolbox de fuzzy logic en Matlab tiene una función que calcula directamente el algoritmo aquí expuesto. Esta función responde a:
[CENTER, U] = FCM(DATA,N_CLUSTER,OPTIONS)
donde:
CENTER: Coordenadas de los centroides
U: Matriz de pertenencia
OPTIONS(1): Exponente de la matriz U (implícito: 2.0)
OPTIONS(2): máximo número de iteraciones (implícito: 100)
OPTIONS(3): Diferencia entre variaciones de centroides deseado (implícito: 1e-5)
OPTIONS(4): mostrar las iteraciones (implícito: 1)
Un ejemplo de su aplicación se muestra a continuación % Datos de entrada x=[0 0 0 1 1 1 2 3 4 5 5 5 6 6 6]';
y=[1 2 3 1.5 2 2.5 2 2 2 1.5 2 2.5 1 2 3]';
x1=x+7;
y1=y.*2;
x2=x1+7;
y2=y.*(-2);
x=[x; x1; x2];
y=[y; y1; y2];
z=[x, y];
[v]=fcm(z,2); % Ejecuta el algoritmo
% Dibuja
figure
plot(z(:,1),z(:,2),'p');
hold on;
plot(v(:,1),v(:,2),'s'); |
El resultado se muestra en la siguiente figura
|
Otras funciones Matlab de utilidad son: findcluster: Interfaz gráfica de usuario
genfis3: Sistema de inferencia borroso Referencias:
Yen, J.; Langari, R.:”Fuzzy Logic: Intelligence, Control and Information”. Prentice Hall. 1999.
|