Propiedades de un enfoque difuso para particionamiento con datos bimodales

´ tica: Teor´ıa y Aplicaciones 2009 16(2): 241–254 Revista de Matema cimpa – ucr issn: 1409-2433

propiedades de un enfoque difuso para particionamiento con datos bimodales William Castillo∗

Javier Trejos†

Recibido/Received: 21 Jan 2009 — Aceptado/Accepted: 12 May 2009

Resumen Se presenta un nuevo criterio de particionamiento difuso con datos bimodales y se formula un algoritmo para su optimizaci´ on. Se estudian las propiedades de convergencia del m´etodo. El m´etodo fue probado con datos reales. De los resultados se dedujo que algunas veces con este nuevo m´etodo se pueden obtener mejores particiones bimodales que las encontradas por otros m´etodos. Palabras clave: partici´ on bimodal, algoritmo, clase difusa, minimizar, varianza explicada. Abstract It is presented a new fuzzy partitioning criterion for two-mode data and an algorithm is formulated for its optmization. We study the convergence properties of the method. The method was tested on real data. It is deduced that better results can be obtained with this new method than with other methods. Keywords: Two-mode partition, algorithm, fuzzy cluster, minimization, variance accounted for. Mathematics Subject Classification: 91C20, 03E72.

1

Introducci´ on

En clasificaci´on no jer´arquica unimodal se busca usualmente una partici´on de un conjunto finito, que minimiza un criterio de clasificaci´on. En el caso cuantitativo, este criterio es ∗

CIMPA, Escuela de Matem´ atica, Universidad de Costa Rica, 2060 San Jos´e, Costa Rica. E-Mail: [email protected] † Misma direcci´ on que W. Castillo. E-Mail: [email protected].

241

242

W. Castillo – J. Trejos

Rev.Mate.Teor.Aplic. (2009) 16(2)

muchas veces del tipo m´ınimo cuadr´atico. Es decir, L(P, V ) =

K X X

pik kxi − vk k2 ,

(1)

k=1 i∈I

donde: • P = (pik )p×K es la matriz cuya columna k ´esima es la funci´on indicadora de la k ´esima clase de la partici´on P del conjunto I, con K clases. • Para cada i ∈ I, xi ∈ IRh es la i ´esima fila de la matriz de datos X, p × h, de individuos por variables continuas. • Para cada k ∈ {1, . . . , K}, vk ∈ IRh es un vector representativo de la k ´esima clase de P , por ejemplo su centro de gravedad. V es la matriz K × h cuyas filas son los K vectores vk . Los m´etodos usuales de particionamiento que minimizan el criterio L(P, V ) son los llamados k-medias, nubes din´amicas e ISODATA. Estos m´etodos est´an basados en b´ usqueda local de particiones que mejoran iterativamente el criterio hasta estabilizarse en un m´ınimo local. En la secci´on siguiente se introduce el m´etodo de clasificaci´on difusa unimodal con el criterio propuesto por Bezdek, J.C. ([2], [3] y [4]) el cual es una generalizaci´on del criterio (1). En la secci´on 3 se propone un m´etodo de clasificaci´on difusa con datos bimodales.

2

Clasificaci´ on unimodal difusa no jer´ arquica

Cuando se usan clases difusas se modifica el criterio de clasificaci´on, y el m´etodo de minimizaci´on requiere, igual que en el caso cl´asico, la definici´on de un algoritmo que converja. El siguiente criterio de clasificaci´on difusa fue propuesto por ([2], [3] y [4]): L(P, V, s) =

K X X

psik kxi − vk k2 ,

k=1 i∈I

donde s ≥ 1 y la matriz P satisface las siguientes propiedades: 1. Para todo i,

K X

pik = 1.

k=1

2. Para todo i, k; pik ∈ [0, 1]. 3. Para todo k,

n X i=1

pik > 0.

(2)

enfoque difuso para particionamiento con datos bimodales

243

Para un objeto i, los K n´ umeros pik representan el grado de pertenencia de i a la clase k. La matriz P se llama partici´ on difusa, con K clases difusas. Cada columna de P representa una clase difusa. Si α ∈]0, 1[ es un umbral, entonces Ak = {i ∈ I |pik ≥ α} es la clase difusa que, en adelante, se la identifica con la columna k-´esima de P . Puede notarse que el criterio (2) es una generalizaci´on del criterio (1), puesto que las funciones indicadoras satisfacen las condiciones 1., 2. y 3. Valores grandes del exponente s (s = 2 ´o 3) tienen el efecto de agrandar la diferencia (con respecto, por ejemplo, a s = 1) de la ponderaci´on entre t´erminos del criterio (2), afectados por valores grandes de pik y los afectados por valores peque˜ nos. Por otra parte, un valor de pik pr´oximo a 1 (por ejemplo, pik ≥ 0.75) indica que el objeto i se encuentra cerca de vk , y un valor peque˜ no indicar´ıa que i se encuentra cerca de la “frontera” de la k ´esima clase difusa. O quiz´as, “entre” dos o m´as clases difusas. As´ı entonces, el exponente s act´ ua como un factor diferenciador de estas distintas situaciones. La elaboraci´on de un algoritmo para minimizar el criterio (2) se hace con base en las siguientes condiciones necesarias de minimizaci´on del criterio de clasificaci´on: 1. Para una partici´ on difusa fija P se minimiza el criterio (2) con respecto a V : h Min L(P, V, s) vk ∈ IR . La soluci´on del problema es la matriz Ve con filas vek definidas por: p X psik xi vek =

i=1 p X

; k = 1, . . . , K.

(3)

psik

i=1

2. Sea s > 1, V fija y Mf r el conjunto de las particiones difusas con K clases. Se miniP miza el criterio (2) con respecto a P = (pik ), sujeto a las p restricciones: K k=1 pik = 1 para todo i. Usando multiplicadores de Lagrange, se deducen condiciones necesarias para un m´ınimo local condicionado de f (P ) = L(P, V, s): Pe = (e pik ) donde: −2

kxi − vk k s−1 peik = K X −2 kxi − vl k s−1

(4)

l=1

siempre que para todo i ∈ I, kxi − vk k > 0 para todo k. En caso de que existan singularidades, es decir; existe i ∈ I tal que kxi − vk k = 0 para alg´ un k, entonces se define X peik = 1 y (kxi − vk k > 0 ⇐⇒ peik = 0) (5) k∈Ii

donde Ii = {k ∈ {1, . . . , K} | peik 6= 0 }.

244

W. Castillo – J. Trejos

Rev.Mate.Teor.Aplic. (2009) 16(2)

Observaciones 1. Sea P ∈ Mf r que satisface la condici´on necesaria de m´ınimo condicionado de f , dada por (4). Y sea Pe la correspondiente partici´on difusa definida por las f´ormulas (4) y (5). el racional de la f´ormula (5) se explica porque al anularse los t´erminos PK Entonces s kx − v k2 = 0 del criterio de clasificaci´ p e on donde ocurren singularidades, se i k k=1 ik e tiene: f (P ) ≤ f (P ). 2. La partici´on difusa Pe no es u ´ nica, salvo si Ii 6= ∅ ⇒ |Ii | = 1. Si s > 1, un algoritmo “natural” para minimizar el criterio (2) es1 : 1. Dar una partici´on difusa inicial P 0 (por ejemplo generada al azar). 2. Repetir (a) y (b) hasta que P n se estabilice o se alcance un n´ umero m´aximo de iteraciones. Para n = 0, 1, . . . n ) , de acuerdo con la f´ (a) Usar P n para calcular V n = (vkl ormula (3). n n+1 (b) Usar V para calcular P , de acuerdo con (4) y (5).

H.H. Bock prob´o, usando un argumento probabil´ıstico, que la sucesi´on L(P n , V n , s) es decreciente (ver [5]). Luego la sucesi´on converge, puesto que es inferiormente acotada. Es decir, el algoritmo converge. Sea Ve definida de acuerdo con la f´ormula (3). Se sabe que cada matriz P ∗ que minimiza la funci´on f : Mf r → [0, +∞[ tal que f (P ) = L(P, Ve , 1), es una partici´on (ver [5]). Este resultado dice que es posible obtener particiones ´optimas, aplicando el algoritmo anterior con s > 1 y s ≈ 1. En lo que sigue de este documento, se formula un m´etodo de clasificaci´on difusa con datos bimodales.

3

Un m´ etodo de clasificaci´ on bimodal difusa

Sea X = (xij )p×q una matriz de similitudes entre objetos de de dos modos I y J, I ∩J = ∅, con p = |I| y q = |J|. Los elementos de X reflejan la interacci´on o asociaci´on entre los dos modos. Esto es, mientras m´as fuerte es la relaci´on entre los objetos i ∈ I y j ∈ J, m´as grande es xij y rec´ıprocamente. Los m´etodos para obtener clasificaciones del tipo P × Q donde P y Q son particiones de I y J con K y L clases respectivamente, se llaman m´etodos de particionamiento bimodal. Entre ellos se tienen los m´etodos inspirados en el modelo aditivo x bij = c +

L K X X

pik qjl vkl

k=1 l=1

1 El algoritmo es conocido en la literatura especializada con el nombre de algoritmo ISODATA difuso (fuzzy ISODATA algorithm, en ingl´es).

enfoque difuso para particionamiento con datos bimodales

245

donde el problema es hallar P , Q y V = (vkl )K×L de modo que el criterio L(P, Q, V ) =

p X q X i=1 j=1

(xij − x bij )2

sea m´ınimo. Este criterio asume una forma simple: L(P, Q, V ) =

p X q L X K X X

pik qjl (xij − vkl )2

(6)

k=1 l=1 i=1 j=1

A partir de lo anterior se desarrollaron los m´etodos siguientes: intercambios alternantes de Gaul, W. y Schader, M. ([8]), un m´etodo de tipo k means de Baier, D.; Gaul, W. y Schader, M. ([1]) y un m´etodo de sobrecalentamiento simulado aplicado al esquema de intercambios alternantes propuesto por Trejos, J. y Castillo, W. ([13]) y Castillo, W. ([6]). Para el caso de clases con intersecciones (overlapping clustering) tambi´en se han propuesto m´etodos para mimimizar el criterio (6), ver por ejemplo [1] y [8]. Con el prop´osito de formular un m´etodo de clasificaci´on bimodal difusa definimos, en lo que sigue, un criterio de clasificaci´on y un algoritmo para minimizarlo.

3.1

El criterio

Sea s ≥ 1 y F = (fijkl ). Se dice que F es una partici´on difusa bimodal si: 1. Para todo i, j, k, l; fijkl ∈ [0, 1]. 2. Para todo i ∈ I y j ∈ J;

L K X X

fijkl = 1.

k=1 l=1

3. Para todo k, l;

p X L X

fijkl > 0.

i=1 j=1

En esta definici´on fijkl es el grado de pertenencia de (i, j) a la clase bimodal difusa Ak × Bl determinada por un cierto umbral. Sea adem´as, la matriz V = (vkl ) donde cada vkl es representativo de la clase bimodal difusa Ak × Bl . Se propone el siguiente criterio de clasificaci´on bimodal difusa: L(F, V, s) =

p X q L X K X X

s fijkl (xij − vkl )2 .

(7)

k=1 l=1 i=1 j=1

Puede notarse que el criterio (7) es una generalizaci´on del criterio (6), tomando s = 1 y fijkl = pik qjl . Con el fin de disminuir el n´ umero de par´ametros por estimar se asumir´a, en lo que sigue, una hip´otesis adicional: fijkl = pik qjl donde, P = (pik ) y Q = (qjl ) son particiones unimodales difusas de I y J con K y L clases, respectivamente. Esto es,

246

W. Castillo – J. Trejos

Rev.Mate.Teor.Aplic. (2009) 16(2)

• Para todo i, j, k, l; pik , qjl ∈ [0, 1]. • Para todo i, j;

• Para todo k, l;

r X

pik = 1 =

L X

qjl .

k=1

l=1

p X

L X

pik > 0 y

i=1

qjl > 0.

j=1

Los par´ameros pik y qjl vienen a ser los grados de pertenencia de i y j a las clases unimodales difusas Ak y Bl asociadas a las columnas k y l de P y Q respectivamente. En este sentido lo que se asume es similar a una hip´otesis de “independencia” del grado de pertenencia. El criterio (7) se escribe entonces como L(P, Q, V, s) =

q p X L X K X X

s psik qjl (xij − vkl )2 .

(8)

k=1 l=1 i=1 j=1

3.2

Actualizaci´ on de los promedios

La f´ormula de actualizaci´on de V se deduce minimizando la funci´on ϕ(V ) = L(P, Q, V, s), dadas las particiones difusas P y Q : sea MK×L el conjunto de matrices K ×L con entradas en IR, entonces, min {ϕ(V ) | V ∈ MK×L } se alcanza en Ve definida por p X q X

vekl =

s psik qjl xij

i=1 j=1 p X q X

.

(9)

s psik qjl

i=1 j=1

Este resultado se obtiene verificando que Ve es un punto estacionario de ϕ. Se nota que Ve es una matriz de promedios ponderados de las entradas xij .

3.3

Actualizaci´ on de las particiones difusas

Las f´ormulas de actualizaci´on de las particiones difusas P y Q se consiguen al identificar condiciones necesarias de m´ınimo para ciertas funciones. P q PL s 2 Definici´ on 1 Sean dik = j=1 l=1 qjl (xij − vkl ) con i ∈ I y k ∈ {1, . . . , K} y P p PK s ejl = i=1 k=1 pik (xij − vkl )2 con j ∈ J y l ∈ {1, . . . , L}. Se dice que i ∈ I (j ∈ J resp.) es una singularidad si dik = 0 (ejl = 0 resp.) para alg´ un k ∈ {1, . . . , K} (l ∈ {1, . . . , L} resp.).

enfoque difuso para particionamiento con datos bimodales

3.3.1

247

Actualizaci´ on de P

Sean Q y V fijos, y φ(P ) = L(P, Q, V, s) con s > 1. Se identificar´an condiciones PKnecesarias de m´ınimo condicionado del problema minP φ(P ) sujeto a las p restricciones k=1 pik = 1. h i Pp PK El lagrangiano de la funci´on φ es φ(P ) + i=1 λi −1 + k=1 pik . Derivando parcialmente con respecto a pik e igualando su derivada, Pel lagrangiano P Pq PaL cero s−1 s 2 = 0. Sea d = s (x − v )2 y se llega a, λi + s qj=1 L p q (x − v ) q kl ik kl l=1 ik l=1 jl ij jl ij j=1 supongamos que i no es una singularidad, entonces despejando pik de la anterior ecuaci´on se consigue,   1 −1 −λi s−1 s−1 pik = dik . (10) s  1  1   −1 P −λi s−1 P s−1 −λi s−1 Luego, h pih = 1 = o sea = P 1 −1 . Finalmente, sustih dih s s h

s−1 dih

tuyendo esto en (10) se tiene, −1

pik =

s−1 dik

K X

.

(11)

−1 s−1

dih

h=1

Sea i una singularidad. Es decir, existe i, tal que dit = 0 para alg´ un t. Se define X para todo k ∈ Ii , pik > 0, pik = 1 y (dik > 0 ⇐⇒ pik = 0)

(12)

k∈Ii

donde Ii = {k ∈ {1, . . . , K} | dik = 0 }. Finalmente, es claro que P definida por las f´ormulas (11) y (12) es una partici´on difusa. Adem´as, no es u ´ nica, salvo si Ii 6= ∅ ⇒ |Ii | = 1. 3.3.2

Actualizaci´ on de Q

Por un procedimiento an´alogo al anterior se deducen las f´ormulas de actualizaci´on de la partici´on difusa Q. P P s 2 Sea ejl = pi=1 K k=1 pik (xij − vkl ) y supongamos que ejl > 0 para todo l, entonces −1

qjl =

ejls−1 L X

.

(13)

−1 s−1

ejh

h=1

Si existe j, tal que ejl = 0 para alg´ un l, entonces se define X para todo j ∈ Jj , qjl > 0, qjl = 1 y (ejl > 0 ⇐⇒ qjl = 0) l∈Jj

donde Jj = {l ∈ {1, . . . , L} | ejl = 0 }.

(14)

248

3.4

W. Castillo – J. Trejos

Rev.Mate.Teor.Aplic. (2009) 16(2)

Minimizaci´ on num´ erica del criterio L(P, Q, V, s)

Utilizando las f´ormulas deducidas en las secciones anteriores se formula un algoritmo para minimizar el criterio L(P, Q, V, s) con s > 1. Luego se prueba que este algoritmo converge. 3.4.1

El algoritmo

1. Dar las particiones difusas iniciales P 0 y Q0 (por ejemplo generadas al azar). Calcular V 0 de acuerdo con la f´ormula (9). 2. Repetir (a), (b) y (c) hasta que 1 − LLn0 > umb, donde Ln = L(P n , Qn , V n , s) y umb ∈ [α, 1[ con α ≈ 1; o se alcance un n´ umero m´aximo de iteraciones. Para n = 0, 1, . . .: (a) Usar Qn y V n para calcular P n+1 = (pn+1 ik ) , de acuerdo con (11) y (12). n+1 (b) Usar P n+1 y V n para calcular Qn+1 = (qjl ), de acuerdo con (13) y (14). n+1 (c) Usar P n+1 y Qn+1 para calcular V n+1 = (vkl ), de acuerdo con (9).

3.4.2

Convergencia del algoritmo

Proposici´ on 1 Sea Ln = L(P n , Qn , V n , s). El algoritmo reci´en definido tiene las siguientes propiedades: (a) Para todo n = 0, 1, . . .; Ln ≥ Ln+1 . Por lo tanto la sucesi´ on (Ln ) converge. (b) Sea n tal que Ln = Ln+1 , entonces para todo i y j que no son singularidades se n = q n+1 para todo k ∈ {1, . . . , K} y l ∈ {1, . . . , L}. tiene: pnik = pn+1 y qjl ik jl ´ n: La propiedad (a) se obtiene probando las desigualdades Demostracio Ln ≥ L(P n+1 , Qn , V n , s) ≥ L(P n+1 , Qn+1 , V n , s) ≥ Ln+1 . para lo cual se usar´a un argumento probabil´ıstico (ver [5]). Primero se demostrar´a que ∀ n, Ln ≥ L(P n+1 , Qn , V n , s). Es suficiente probar, para todo i ∈ I, K X

(pnik )s dnik ≥

k=1

K X

pn+1 ik


s

dnik

k=1

P q PL  n  s n )2 . donde dnik = (xij − vkl Si i es una singularidad, entonces j=1 l=1 qjl
PK s 0 = k=1 pn+1 dnik y vale la desigualdad anterior para este i. En cualquier otro caso, ik −1

sustituyendo

pn+1 ik

=

(dnik ) s−1 PK

h=1

−1

(dnik ) s−1

, en el lado derecho de la desigualdad anterior, vemos

enfoque difuso para particionamiento con datos bimodales

que ´este es igual a

hP

−1 K n s−1 k=1 (dik )

K X

i1−s

249

. Por lo tanto es suficiente probar que, para todo i,

(pnik )s dnik ≥

k=1

"

K X

(dnik )

−1 s−1

#1−s

.

(15)

k=1

Sea para todo k, yk = (pnik )s−1 dnik . Se define la variable aleatoria Y tal que para todo −1

k, Pr(Y = yk ) = pnik . Teniendo en cuenta que la funci´on h(y) = y s−1 es convexa y estrictamente decreciente para y > 0, resulta f´acil deducir lo siguiente: 1. E [Y ] =

K X

(pnik )s dnik .

k=1

2. E [h(Y )] =

K X

−1 (dnik ) s−1

=h [

k=1

K X

−1 (dnik ) s−1 ]1−s

!

.

k=1

Por la desigualdad de Jensen se tiene h(E [Y ]) ≤ E [h(Y )]. Es decir, " #1−s  K K X X −1 . h( (pnik )s dnik ) ≤ h  (dnik ) s−1 k=1

k=1

Como h es estrictamente decreciente y continua (y por tanto biyectiva), en ]0, +∞[, entonces, #1−s "K K X X −1 (pnik )s dnik ≥ (dnik ) s−1 k=1

k=1

que es la desigualdad (15). La desigualdad L(P n+1 , Qn , V n , s) ≥ L(P n+1 , Qn+1 , V n , s) se prueba de manera similar. Finalmente, L(P n+1 , Qn+1 , V n , s) ≥ Ln+1 es consecuencia de n+1 n+1 Ln+1 = minV L(P ,Q , V, s). Para demostrar la propiedad (b), se observa en particular que Ln = L(P ( n + 1), Qn , V n , s) es consecuencia de la hip´otesis Ln = Ln+1 . En virtud de esto y de la desigualdad (15), se obtiene para todo i que no es una singularidad,la igualdad #1−s "K K X X −1 (pnik )s dnik = (dnik ) s−1 . k=1

k=1

Es decir, h(E [Y ]) = E [h(Y )]. En consecuencia la variable aleatoria Y es constante2 . Esto −1 1 es, para todo k, (pnik )s−1 dnik = c > 0. O sea, pnik = c s−1 (dnik ) s−1 . 2

En el caso general, Y = c con probabilidad 1. En nuestro caso particular, h es estrictamente convexa y derivable en E[Y ] ∈ ]0, +∞[. Al considerar la recta tangente a la gr´ afica de h por el punto (E[Y ], h(E[Y ])) se puede deducir que Y es constante si y solo si E[h(Y )] = h(E[Y ]).

250

W. Castillo – J. Trejos

Por otra parte,

de acuerdo con (11),

Rev.Mate.Teor.Aplic. (2009) 16(2)

−1

α=

3.5

P

−1 K n s−1 l=1 (dil )

−1

−1

c s−1 . Como

PK

n k=1 pik

pn+1 ik

=

(dnik ) s−1 −1 PK n s−1 l=1 (dil )

=

αpnik

con

= 1 entonces α = 1.

An´ alisis del caso s = 1

Sea la funci´on ψ(P ) = minV L(P, Q, V, 1) con Q fija. Identificamos la matriz P de tama˜ no pr p × K con el vector (p1 , . . . , pp ) ∈ IRn , donde pi es la fila i de la matriz P . Seano S PK y T los conjuntos definidos por3 S = P ∈ IRpr para todo i, pi ≥ 0 y y k=1 pik = 1 o n P L T = Q ∈ IRqm para todo j, qj ≥ 0 y l=1 qjl = 1 . En lo que sigue se prueba que la funci´on ψ alcanza su m´ınimo en una partici´on P ∗ ∈ S (proposici´on 5) y que si Φ(P, Q) = minV L(P, Q, V, 1) alcanza su m´ınimo en (P ∗ , Q∗ ) ∈ S × T , entonces P ∗ y Q∗ son particiones (ver proposici´on 6). Proposici´ on 2 S es un poliedro4 acotado. ´ n: Sean 1p y 0pr las columnas de unos y ceros, de longitud p y pr respectivaDemostracio mente. S es la intersecci´on de los poliedros {x ∈ IRpr |Ax ≤ 1p }, {x ∈ IRpr |−Ax ≤ −1p } y {x ∈ IRpr |−Bx ≤ 0pr } donde A y B son, respectivamente, las matrices de coeficientes P de los sistemas K k=1 pik = 1, i = 1, . . . , p y pik = 0 , i = 1, . . . , p, k = 1, . . . , K. Luego S es un poliedro. Por otra parte, es claro que S ⊆ [0, 1]pr . Luego S es acotado. Proposici´ on 3 P es un extremo5 de S si y s´ olo si P es una partici´ on. ´ n: Sea P ∈ S una partici´on que no es un extremo de S. Razonemos por Demostracio contradicci´on. Existen P 0 6= P 00 y α ∈ ]0, 1[ tales que P = αP 0 +(1−α)P 00 con P 0 , P 00 ∈ S. Entonces existe k 0 tal que para todo k 6= k 0 , pik = αp0ik + (1 − α)p00ik = 0; luego para todo k 6= k 0 , p0ik = p00ik = 0 y p0ik0 = p00ik0 = 1. Es decir P 0 = P 00 , lo cual es una contradicci´on. Por otro lado, sea P ∈ S. Se prueba que si P no es una partici´on entonces P no es un extremo. En efecto, como P = (pik ) no es una partici´on, existen i y Ki ⊂ {1, . . . , K} tales que • |Ki | ≥ 2, pik ∈ ]0, 1[ para todo k ∈ Ki , y • si Ki 6= {1, . . . , K} entonces pik = 0 para todo i ∈ / Ki . 3

Esta definici´ on admite posibles clases difusas vac´ıas para P ∈ S. Un poliedro en IRn es la intersecci´ on de un n´ umero finito de semiespacios cerrados de IRn . Un semiespacio en IRn es un conjunto de la forma {x ∈ IRn |Ax ≤ b } donde A y b son matrices fijas p × n y p × 1 respectivamente. 5 Por definici´ on P ∈ S es un extremo del convexo S si no existen P 0 6= P 00 y α ∈ ]0, 1[ tales que P = αP 0 + (1 − α)P 00 con P 0 , P 00 ∈ S. 4

enfoque difuso para particionamiento con datos bimodales

Es claro que P =

P

(k) donde P (k) = k∈Ki pik P



(k)

pis



251

es igual a P excepto por las p×K

(k)

entradas pis , que se definen as´ı: (k) pis

Sean α =

P

k∈Ki −{k 0 } pik

=

yP =



P

1 si s = k. 0 en caso contrario.

pik (k) k∈Ki −{k 0 } α P

0

∈ S. Es claro que P = pik0 P (k ) + (k 0 )

0

αP con {pik0 , α} ⊂ ]0, 1[ y pik0 + α = 1. Adem´as, P (k ) 6= P , puesto que pik0 = 1 y
P (k) P ik0 = k∈Ki −{k0 } pαik pik0 = 0. Luego P no es un extremo de S. Proposici´ on 4 ψ es c´ oncava en S. ´ n: sea α ∈ [0, 1] y P 0 , P 00 ∈ S, entonces Demostracio ψ(αP 0

+ (1 −

α)P 00 )

q p X L X K X X

=

minV

=

k=1 l=1  i=1 j=1 p X q L K XX X

min  vkl

k=1 l=1 p X q X

+

≥

α

i=1 j=1 L K X X

+ (1 − α)

i=1 j=1

vkl

p X q X



p0ik qjl (xij − vkl )2

i=1 j=1

L K X X k=1 l=1

=

αp0ik qjl (xij − vkl )2

(1 − α) p00ik qjl (xij − vkl )2 

min

k=1 l=1


αp0ik + (1 − α) p00ik qjl (xij − vkl )2

min vkl

q p X X

p00ik qjl (xij − vkl )2

i=1 j=1

αψ(P 0 ) + (1 − α)ψ(P 00 ).

Proposici´ on 5 Existe una partici´ on P ∗ ∈ S tal que ψ(P ∗ ) = minP ∈S ψ(P ). ´ n: La funci´on ψ es c´oncava (por proposici´on 4) y acotada inferiormente Demostracio sobre el poliedro acotado S. Luego ψ alcanza su m´ınimo global en P ∗ ∈ S y P ∗ es un punto extremo de S (ver [12])6 . Por la proposici´on 3, P ∗ es una partici´on. Proposici´ on 6 Si la funci´ on Φ(P, Q) = minV L(P, Q, V, 1) alcanza su m´ınimo en (P ∗ , Q∗ ) ∈ S × T , entonces P ∗ y Q∗ son particiones. 6 El teorema que se est´ a aplicando aparece en la p´ agina 125 del libro de Roberts, A.W. y Varberg D.E. ([12]), como “Theorem E”.

252

W. Castillo – J. Trejos

Rev.Mate.Teor.Aplic. (2009) 16(2)

´ n: Sea ψ(P ) = minV L(P, Q∗ , V, 1) entonces Demostracio ψ(P ∗ ) = Φ(P ∗ , Q∗ ) ≤ Φ(P, Q∗ ) = ψ(P ) para todo P ∈ S. Luego P ∗ es una partici´on (por la proposici´on 5). De manera similar, si ϕ(Q) = minV L(P ∗ , Q, V, 1) entonces ϕ(Q∗ ) = Φ(P ∗ , Q∗ ) ≤ Φ(P ∗ , Q) = ϕ(Q) para todo Q ∈ T . Luego Q∗ es una partici´on.

4

Algunos resultados comparativos

Con el prop´osito de investigar la eficacia del nuevo m´etodo difuso (MD), ´este fue programado con Mathematica y evaluado a partir de c´alculos efectuados con datos que han sido objeto de investigaci´on con otros m´etodos. De acuerdo con la proposici´on 6 demostrado en la secci´on anterior, escogiendo s ≈ 1, el MD puede ser usado para detectar particiones eventualmente ´optimas. Con esta idea se abord´o la presente investigaci´on comparativa. El conjunto de datos usado corresponde a una tabla de ochenta y dos filas y veinticinco columnas y se ubica en un estudio de mercado para introducir un nuevo producto de la l´ınea de sanitarios ecol´ogicos (ver [1])7 . Cada entrada xij ∈ {1, . . . , 11} de esta tabla expresa la intenci´on de compra del cliente potencial i, con base en el nivel j de un atributo del producto. Se tomaron en cuenta cinco atributos (como precio, reciclado, etc.) cada uno con cinco niveles. La siguiente tabla contiene el mejor valor encontrado de la varianza explicada V E definida PK PL p q (x −b x )2 1 Pp Pq k=1 Pq ik jl ij 2 ij por V E = 1− Pp l=1 donde x = pq etodo i=1 j=1 xij . Se comparan el m´ (x −x) i=1

j=1

ij

de tipo k-means, el de intercambios alternantes (IA) y MD. K=L 3 4

k-means 0.3234 0.3729

IA 0.3234 0.3729

MD 0.3559 0.4000

En el caso del m´etodo MD se us´o s = 1.01. En [1] se reportan los mismos valores de V E como los mejores valores encontrados por el m´etodo k-means en cincuenta inicios al azar. Los valores de V E obtenidos con el m´etodo MD son significativamente mayores que los obtenidos con los otros m´etodos, no obstante que el criterio opti optimizado por MD no es el de la varianza explicada. El m´etodo MD tambi´en fue aplicado con valores peque˜ nos de s a unos datos sobre bebidas gaseosas, obteni´endose la misma partici´on en tres clases de Eckes & Orlick ([7]). Con los datos Cigarrilos 1, Cigarrillos 2 y Co˜ nac, se encontraron los mismos resultados conocidos y reportados en [6] y [8], para K = L = 3 y K = L = 4. Se realizaron pruebas para valores grandes de s (s = 1.5, 2, por ejemplo) con los datos de sanitarios y los datos de conductas versus situaciones analizados en [7] y en [11]. Sin embargo el algoritmo fall´o en la detecci´on de clases difusas. 7

Agradecemos a los autores de este art´ıculo por enviarnos los datos

enfoque difuso para particionamiento con datos bimodales

253

Actualmente, estamos realizando experimentaciones por medio de simulaciones de Monte Carlo [10] para evalkuar el m´etodo con una variante que hace disminuir el valor de s, y se hacen comparaciones con otros cuatro m´etodos.

Referencias [1] Baier, D.; Gaul, W.; Schader, M. (1997) “Two-mode overlapping clustering with applications to simultaneous benefit segmentation and market structuring”, in: R. Klar & O. Opitz (Eds.), Classification and Knowledge Organization. Springer, Heidelberg, 557–566. [2] Bezdek, J.C. (1980) “A convergence theorem for the fuzzy ISODATA clustering algorithms”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2(1): 1–8. [3] Bezdek, J.C. (1981) Pattern Recognition with Fuzzy Objective Function Algorithms. Plenum Press, New York and London. [4] Bezdek, J.C.; Hathaway, R.J.; Sabin, M.J.; Tucker, W.T. (1987) “Convergence theory for fuzzy c-means: counterexamples and repairs”, IEEE Transactions on Systems, Man and Cybernetics, 17(5): 873–877. [5] Bock, H.H. (1979) “Fuzzy clustering procedures”, in: R. Tomassone (Ed.) Analyse des Donn´ees et Informatique, INRIA, Paris: 205–218. [6] Castillo, W. (1999) M´etodos de Particionamiento Bimodal y Trimodal. Tesis de Maestr´ıa, Universidad de Costa Rica. [7] Eckes, T.; Orlik, P. (1993) “An error variance approach to two-mode hierarchical clustering”, Journal of Classification 10, 51-74. [8] Gaul, W.; Schader, M. (1996) “A new algorithm for two-mode clustering”, in: H.H. Bock & W. Polasek (Eds.) Data Analysis and Information Systems. Springer, Heidelberg, 15–23. [9] Groenen, P.J.F.; Jajuga, K. (2001) “Fuzzy clustering with squared Minkowski distances”, Fuzzy Sets and Systems 120(2): 227–237. [10] Groenen, P.J.F.; Rosmalen, J. van; Trejos, J.; Castillo, W. (2009) “Optimization strategies for two-mode partitioning”, aceptado en Journal of Classification. [11] Mirkin, B.G.; Arabie, P.; Hubert, L.J. (1995) “Additive two-mode clustering: the error-variance approach revisited”, Journal of Classification 12(2): 243–263. [12] Roberts, A.W.; Varberg, D.E. (1973) Convex Functions. Academic Press, New York.

254

W. Castillo – J. Trejos

Rev.Mate.Teor.Aplic. (2009) 16(2)

[13] Trejos, J.; Castillo, W. (2000) “Simulated annealing optimization for two-mode partitioning”, in: W. Gaul & R. Decker (Eds.) Classification and Information at the Turn of the Millenium. Springer-Verlag, Berlin: 133–142.