modelos de clasificación

CURSO

Modelos de Clasificacion

Javier Trejos ZelayaCIMPA, Universidad de Costa Rica,

E-Mail: [email protected]

Indice

1. Introduccion 2

2. Medidas de Semejanza 32.1. Distancias y disimilitudes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2. Similitudes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.3. Disimilitudes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3. Clasificacion Jerarquica 93.1. Jerarquıas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.2. Clasificacion jerarquica ascendente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.3. Algoritmos ascendentes acelerados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.4. Aproximaciones por ultrametricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.5. Clasificacion jerarquica descendente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.6. Observaciones sobre la clasificacion jerarquica . . . . . . . . . . . . . . . . . . . . . . . . . 15

4. Clasificacion por Particiones 164.1. Problema combinatorio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164.2. Criterio de la inercia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164.3. Metodo de k-medias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174.4. Metodos de nubes dinamicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194.5. Metodo de Fisher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214.6. Uso de heurısticas modernas de optimizacion . . . . . . . . . . . . . . . . . . . . . . . . . 22

5. Metodos Arboreos No Jerarquicos 235.1. Arboles aditivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235.2. Piramides . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

6. Otros Metodos 256.1. Clasificacion bimodal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256.2. Clasificacion difusa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276.3. Clasificacion neuronal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286.4. Clasificacion probabilıstica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

7. Validacion de Resultados 317.1. Descripcion de una particion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317.2. Numero de clases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317.3. Pruebas de hipotesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

1

2 Javier Trejos

1. Introduccion

La clasificacion automatica tiene por objetivo reconocer grupos de individuos homogeneos, de talforma que los grupos queden bien separados y bien diferenciados. Estos individuos pueden estar descritospor una tabla de datos de individuos por variables, con variables cuantitativas o cualitativas, o por unatabla de proximidades.

Lo que se entiende por individuos homogeneos es que los individuos que pertenezcan a un mismogrupo tengan, ya sea caracterısticas iguales o similares en el caso de que sean descritos por una tablacon variables, o bien que esten proximos unos de otros en el caso de que sean descritos por una tabla deproximidades. Es decir, dos individuos de una misma clase deben parecerse mas entre sı, que parecerse aun individuo de otra clase.

La clasificacion automatica tambien es conocida bajo otros nombres, como por ejemplo analisis degrupos, analisis tipologico, analisis de conglomerados, analisis de agrupaciones (en ingles, se usa normal-mente el termino cluster analysis). Nosotros preferimos el termino de clasificacion automatica porque elobjetivo es buscar una clasificacion (o varias clasificaciones, segun sea el metodo usado) de los individuosu objetos a agrupar, y como esta clasificacion es desconocida a priori, el metodo debe hacer la clasi-ficacion automaticamente sin que intervenga ningun agente externo. Contrariamente, la discriminaciontrata de clasificar a los individuos en grupos dados a priori, por lo que la clasificacion no es automaticasino supervisada (se trata de que la regla de asignacion a los grupos dados minimice los posibles erroresa clases incorrectas).

Existe gran cantidad de metodos de clasificacion automatica, entre los que podemos distinguir lossiguientes:

los metodos jerarquicos, que buscan una serie de particiones encajadas de tal manera que puedanrepresentarse mediante un arbol;

los metodos piramidales, que como los jerarquicos buscan particiones encajadas, pero que permitena una clase de nivel inferior estar contenida en dos clases de nivel superior;

los metodos de particionamiento, que buscan una sola particion del conjunto de individuos;

los metodos de clasificacion no exclusiva, que buscan grupos en los datos de tal manera que unindividuo pueda pertenecer a varios grupos al mismo tiempo;

los metodos de clasificacion difusa, que buscan grupos homogeneos de individuos pero que danel grado de pertenencia difusa (en el intervalo [0, 1]) de cada individuo a cada clase;

los metodos de clasificacion cruzada, que tratan de hacer la clasificacion simultaneamente sobredos conjuntos de individuos (o uno de individuos y uno de variables).

En este curso veremos inicialmente los metodos mas usados, que son los jerarquicos y los de parti-cionamiento. Ası, abordaremos los metodos llamados de clasificacion jerarquica ascendente y los de nubesdinamicas, por ser los mas populares y faciles de usar. Tanto los metodos jerarquicos como algunos deltipo nubes dinamicas estan implementados en la mayorıa de los paquetes estadısticos.

modelos de clasificacion 3

2. Medidas de Semejanza

Los metodos de clasificacion automatica usan ampliamente el concepto de similitud o disimilitud entrelos individuos. Por lo tanto, en un primer momento abordaremos este tema antes de pasar a describir losmetodos de clasificacion propiamente dichos. A lo largo del capıtulo denotaremos con Ω al conjunto deindividuos a clasificar, y supondremos que posee n elementos.

2.1. Distancias y disimilitudes

Las similitudes y disimilitudes son los conceptos basicos que nos permitiran determinar si dos indi-viduos u objetos son parecidos o diferentes. La similitud tiene el sentido de medir cuan similares son dosindividuos, por lo tanto entre mayor sea su valor mayor sera el parecido entre los individuos, y entre mascercano a cero menor sera este parecido. La disimilitud, por el contrario, mide cuan diferentes son dosindividuos, como es el caso de las distancias que todos conocemos; por lo tanto entre mas cercana a cerosea la disimilitud menos diferentes seran los individuos (es decir, es mas posible que pertenezcan a unamisma clase) y entre mayor sea esta mas diferentes seran.

2.2. Similitudes

Una similitud es una funcion s : Ω × Ω −→ R+ tal que:

1. para cada i ∈ Ω, se tiene s(i, i) = maxs(i, j)/j ∈ Ω;

2. para cada i, j ∈ Ω, hay simetrıa: s(i, j) = s(j, i).

Con solo estos dos requisitos se pueden construir funciones que den una idea de la similitud entre indi-viduos. Ahora bien, la definicion de una similitud dependera de como es la descripcion de los individuos,es decir, que tipo de variables son las que los describen.

2.2.1. Caso de variables binarias

Un caso frecuente para usar similitudes es cuando los individuos estan descritos por variables binarias,es decir, variables de presencia-ausencia que toman solo los valores 0 y 1 dependiendo de si el individuopresenta o no la variable. Si un individuo tiene un valor de 1 en la variable se dice que “posee el atributo”,que describe esa variable. Por ejemplo, podemos considerar que la variable: “el estudiante posee beca”,es una variable binaria, o bien “el estudiante es repitente”. En biologıa tambien aparecen con frecuenciaeste tipo de variables, como por ejemplo: “el animal posee alas”, o bien “la planta esta presente en laparcela”.

En este contexto, dados dos individuos i y j en Ω, antes de medir su similitud se pueden contar lossiguientes elementos:

pij : es el numero de atributos que poseen al mismo tiempo tanto i como j

qij : es el numero de atributos que presenta solo uno de los dos

p: es el numero total de atributos (numero de variables).

Existe una serie de ındice de similitud basados en los elementos anteriores. Daremos a continuacionsolamente los dos ındices mas usados, dejando para la consulta de abundantes referencias los otros ındices[12, 15, 16, 19, 28, 29, 22, 27, 48, 40]. Los ındices de similitud mas usados para datos binarios son:

el ındice de Jaccard:s(i, j) =

pij

pij + qij

4 Javier Trejos

el ındice de Russel y Rao:

s(i, j) =pij

p

Observese que, cuando los individuos i y j coinciden en todos sus atributos, el ındice de Jaccard alcanzasu valor maximo que es 1, mientras que el de Russel y Rao alcanza como valor maximo el cociente entreel numero de atributos que coinciden y p. Solo en el caso en que tanto i como j posean todos los atributosel valor del ındice de Russel y Rao sera 1.

Ejemplo 1 Supongase que se tienen 6 individuos a, b, c, d, e, f descritos por 4 variables binarias v1,v2,v3,v4.Los datos son:

v1 v2 v3 v4

a 1 0 1 1b 0 1 1 1c 0 0 0 0d 1 0 1 1e 0 1 0 0f 1 1 1 1

Al calcular el numero de atributos para los que coinciden (con presencia) las parejas de individuos opara los que son diferentes, se obtienen los valores de pij y qij dados a continuacion:

pij b c d e fa 2 0 3 0 3b 0 2 1 3c 0 0 0d 0 3e 1

qij b c d e fa 2 3 0 4 1b 3 2 2 1c 3 1 4d 4 1e 3

Al calcular los ındices de Jaccard y de Russel & Rao, se obtiene:

Jaccards(i, j) a b c d e f

a 1 0,5 0 1 0 0,75b 1 0 0,5 0,33 0,75c 1 0 0 0d 1 0 0,75e 1 0,25f 1

Russel&Raos(i, j) a b c d e f

a 1 0,5 0 0,75 0 0,75b 1 0 0,5 0,25 0,75c 1 0 0 0d 1 0 0,75e 1 0,25f 1

En la tabla de datos original se puede ver que los individuos a y d coinciden en todos sus valores.El valor de 1 para s(i, j) calculado con el ındice de Jaccard refleja este hecho, lo cual no se aprecia conel ındice de Russel & Rao. por otra parte, el individuo a es el opuesto de e, el valor de 0 para s(i, j)calculado con ambos ındices refleja este hecho.

2.2.2. Similitudes entre variables

Generalmente, cualquier ındice de asociacion entre variables sirve como similitud entre variables. Ası,para parejas de variables cuantitativas x,y observadas sobre n objetos, se tiene el coeficiente de correlacionlineal

r(x,y) =∑n

i=1(xi − x)(yi − y)sxsy


donde sx, sy son las desviaciones estandar de x y y, respectivamente. En general, cualquier ındice de cor-relacion servirıa como similitud entre variables, solo se debe tener cuidado con la manera de normalizarlopara su uso en clasificacion. Por ejemplo, para el caso del coeficiente de correlacion lineal se suele usar

d(x,y) = 1 − |r(x,y)|

como ındice de disimilitud, en el caso de tomar como fuerte asociacion el caso r(x,y) ≈ −1, o bien

d(x,y) = 2 − r(x,y)

en el caso contrario.Para parejas de variables cualitativas x,y observadas sobre n objetos y con p, q modalidades respec-

tivamente, se suele tomar el ındice de asociacion de chi-cuadrado como similitud

χ2(x,y) =p∑

j=1

q∑

k=1

1n

(nnjk − nj·n·k)2

nj·n·k

donde njk es la frecuencia en la tabla de contingencia que resulta de cruzar x y y, y nj·, n·k son losmargenes. Ahora bien, el ındice de χ2 tiene el inconveniente de no estar normalizado y no permitecomparar ındices para modalidades observadas sobre distinto numero de objetos, ni con diferente numerode modalidades. Por ello, se suele usar mas bien el ındice T 2 de Chuprov, normalizado en el intervalo[0, 1]:

T 2(x,y) =χ2(x,y)

n(p − 1)(q − 1).

2.3. Disimilitudes

Una disimilitud es una funcion d : Ω × Ω −→ R+ tal que:

1. para cada i ∈ Ω se tiene d(i, i) = 0

2. para cada i, j ∈ Ω, hay simetrıa: d(i, j) = d(j, i)

Si a la definicion anterior uno le anade:

3. d(i, j) = 0 ⇔ i = j

4. la desigualdad triangular: para cada i, j, k ∈ Ω d(i, j) ≤ d(i, k) + d(k, j)

entonces la disimilitud es lo que llamamos una distancia.

2.3.1. Caso cuantitativo

La disimilitud mas usada es la distancia euclıdea clasica:

d(i, j) =

√√√√p∑

k=1

(xki − xk

j )2

Recuerdese de lo estudiado en el capıtulo 2 que una distancia euclıdea puede ser definida a partirde una metrica, esto es, de una matriz simetrica definida y positiva M . En tal caso, se podrıa ponerd2(i, j) = ||xi − xj ||M = (xi − xj)tM(xi − xj). Ası, la distancia euclıdea clasica coincide con el caso enque se usa como metrica la identidad de orden p.

El uso de la distancia clasica tiene sentido cuando las variables observadas sobre los individuos soncuantitativas, pues en este caso tienen sentido las operaciones expresadas en la formula de la distancia. Hayque mencionar que esta distancia tiene un inconveniente si se usa sin precaucion: debido a que cada termino

6 Javier Trejos

de la sumatoria es elevado al cuadrado, la distancia euclıdea tiene tendencia a magnificar las grandesdiferencias entre las observaciones, por lo que si hay un dato aberrante este comportamiento atıpicose traducira en un valor muy grande dela distancia. Por ello, antes de cualquier analisis multivariado,siempre se recomienda hacer un estudio univariado de cada variable; en particular una caja de dispersiondeberıa indicar la presencia de valores aberrantes y ası el analista puede tomar las medidas necesarias.

Algunos autores prefieren usar una distancia como la siguiente, llamada “city-block”1:

d(i, j) =p∑

k=1

|xki − xk

j |

Otra distancia usada en ocasiones, es la llamada distancia de Chebychev:

d(i, j) = max|xki − xk

j |/k = 1, . . . , p

Ejemplo 2 Supongase que se tiene 4 individuos a, b, c, d descritos por 5 variables v1, v2, v3, v4, v5, segunse muestra en la tabla siguiente:

v1, v2 v3 v4 v5

a 2 3,5 0 4 7b 4 3 1,5 5 6c 0 6 4 2 3d 3 3 1 4 77

El calculo de las distancias euclıdea clasica, city-block y de Chebichev son:

Euclıdead(i, j) a b c d

a 0 2,915 6,801 70,02b 0 7,018 71,02c 0 74,21d 0

City-blockd(i, j) a b c d

a 0 6 14,5 72,5b 0 15,5 73,5c 0 85d 0

Chebychevd(i, j) a b c d

a 0 2 4 70b 0 4 71c 0 74d 0

De los cuatro individuos de la tabla de datos, se puede apreciar que a y b tienen valores muy parecidospara las cinco variables, y su cercanıa es reflejadapor el bajo valor de las distancias. Por su parte, dtambien tiene valores cercanos a a y b en las cuatro primeras variables, aunque para la quinta tenga unagran diferencia; si se supone que esta gran diferencia es debida a un valor “aberrante”, como por ejemplodebido a un error de un digitador a la hora de pasar los datos del papel a la computadora (supongase queel dato real era 7 y no 77, como aparece en la tabla), entonces puede apreciarse que las tres distanciasmostradas son muy sensibles a los valores de estos casos atıpicos.

1Este nombre proviene del hecho que para medir la distancia entre dos puntos de una ciudad como el centro de San Jose,donde las calles y avenidas son paralelas y se cruzan perpendicularmente entre sı, hay que medir las distancias recorriendolas calles pasando por las esquinas, y no en lınea recta


2.3.2. Caso binario

Se puede definir una disimilitud facilmente a partir de una similitud en el caso de tener variablesbinarias. Por ejemplo, considerando una similitud s cuyo valor maximo sea 1, entonces se define d(i, j) =1 − s(i, j). Ası, se definen la disimilitud de Jaccard:

d(i, j) = 1 − qij

pij + qij

usando las notaciones de la seccion 2.2.1, y la disimilitud de Russel & Rao:

d(i, j) =p − pij

p

Ejemplo 3 Usando los datos del ejemplo 1, tendrıamos los siguientes valores para las disimilitudes deJaccard y de Russel & Rao:

Jaccardd(i, j) a b c d e f

a 0 0,5 1 0 1 0,25b 0 1 0,5 0,66 0,25c 0 1 1 1d 0 1 0,25e 0 0,75f 0

Russel&Raod(i, j) a b c d e f

a 0 0,5 1 0,25 1 0,25b 0 1 0,5 0,75 0,25c 0 1 1 1d 0 1 0,25e 0 0,75f 0

2.3.3. Caso cualitativo

Se podrıa plantear la medida de la disimilitud entre dos individuos descritos por p variables cualitati-vas, usando las definiciones de disimilitudes para datos binarios y la tabla de datos en forma disyuntivacompleta, esto es, con las indicatrices (0 y 1) de las modalidades de las variables cualitativas. En estecaso, se podrıan usar las disimilitudes de Jaccard y Russel & Rao vistas anteriormente. Sin embargo, lousual es usar adaptaciones especiales de las distancias euclıdeas, como la distancia euclıdea clasica y ladistancia de χ2 (chi-cuadrado).

La distancia euclıdea clasica entre dos individuos i y j descritos por p variables cualitativas x1, x2, . . . , xp

es:

d(i, j) = 2p∑

k=1

δkij

donde δkij =

1 si xk

i 6= xkj

0 si xki 6= xk

j.

La distancia de χ2 es:

d(i, j) =1p2

p∑

k=1

(1

s(xki )

+1

s(xkj )

)δkij

donde δkij se define como antes y s(xk

i ) es el numero de veces que la modalidad xki esta presente para la

variable xk.

2.3.4. Agregaciones

Los metodos de clasificacion automatica usan generalmente una nocion de proximidad entre gruposde elementos, para medir la separacion entre las clases que se buscan. Para ellos, se introduce el conceptode agregacion, que no es mas que una disimilitud entre grupos de individuos: sean A, B ⊂ Ω, entonces laagregacion entre A y B es:

δ(A, B)

tal que δ es una disimilitud en el conjunto de partes P(Ω):

8 Javier Trejos

i) δ(A, A) = 0 para todo A ∈ P(Ω)

ii) δ(A, B) = δ(B, A) para todo A, B ∈ P(Ω)

Usualmente, la medida de agregacion esta basada en la disimilitud d medida sobre Ω. En efecto,denotando A yB dos subconjuntos de Ω, las agregaciones mas usadas son:

1. Agregacion del salto mınimo o del vecino mas cercano:

δmın(A, B) = mınd(a, b)|a ∈ A, b ∈ B

2. Agregacion del salto maximo:

δmax(A, B) = maxd(a, b)|a ∈ A, b ∈ B

3. Agregacion del salto promedio:

δprom(A, B) =1

card(A) + card(B)

∑

a∈Ab∈B

d(a, b)

En el caso cuantitativo se tiene ademas:

4. Agregacion de Ward:

δward(A, B) =card(A)card(B)

card(A) + card(B)||g(A) − g(B)||2 = I(A ∪ B) − I(A) − I(B)

donde g(A) es el centro de gravedad del conjunto A, || · || es una norma euclıdea e I(A) es lainercia del conjunto A, es decir I(A) =

∑xi∈A pi||xi − g(A)||2. Esta agregacion, tambien llamada

del incremento de la inercia, solo tiene sentido cuando se esta en un contexto euclıdeo, es decir,cuando se dispone de variables cuantitativas.

Existen otras agregaciones tambien citadas en la literatura, como por ejemplo la distancia entre loscentros de gravedad o la inercia I(A∪B). Sin embargo, la mayorıa de estas tienen el defecto de producirinversiones en el algoritmo de clasificacion jerarquica ascendente que veremos en la siguiente seccion.


3. Clasificacion Jerarquica

3.1. Jerarquıas

Generalmente, los metodos de particionamiento –como los de nubes dinamicas que presentaremos enel proximo capıtulo– encuentran en cada ejecucion una sola particion en un numero dado a priori declases. Ahora bien, este numero de clases puede no “representar” el numero real de clases que se formanen la configuracion de los datos.

Por ejemplo, considerese la siguiente configuracion de puntos en R2:

r rrr r r

r rr rrrrrr r rrrr

Puede apreciarse que de forma natural se forman 3 clases de individuos segun la cercanıa de los puntos.Ahora bien, si el usuario no conoce esta configuracion (para efectos de simplificacion la hemos dado en dosdimensiones, pero el lector puede pensar que se trata de una configuracion en muchas mas dimensiones),entonces puede suceder que se trate de obtener clasificaciones en numeros de clases diferentes de 3, porejemplo en 2 clases o en 5 clases.

Para paliar este problema, uno puede plantearse la posibilidad de crear clasificaciones para variosnumeros de clases al mismo tiempo, y escoger luego la que mas conviene segun las necesidades. Unamanera de abordar este problema, es tratar de obtener un arbol jerarquico de clasificaciones, tal como semuestra en la figura 1 para un conjunto Ω = a, b, c, d, e.

a b c d e

Figura 1: Ejemplo de arbol jerarquico

Una arbol jerarquico tiene la ventaja de que es de facil interpretacion. En efecto, para el arbol de lafigura 1, se interpreta que los individuos mas cercanos son los que se unen a un nivel mas bajo del arbol,esto es a y b. Enseguida, los dos individuos que siguen en similitud son d y e, luego el grupo a, b conel individuo c, y finalmente se obtiene el grupo total Ω.

El procedimiento para construir el arbol jerarquico, trata de encontrar los dos individuos mas cercanosen el sentido de la disimilitud d definida sobre Ω. Una vez que se han unido, se consideran las distancias

10 Javier Trejos

entre los individuos restantes, y entre ellos y el nuevo grupo formado. Para esto ultimo, necesitamosescoger una agregacion δ.

Un arbol jerarquico representa lo que se conoce como una jerarquıa.Una jerarquıa sobre Ω es un subconjunto H de P(Ω) tal que:

1. Ω ∈ H ,

2. ∀i ∈ Ω, i ∈ H ,

3. ∀i, i′ ∈ H : h ∩ h′ 6= φ ⇒ h ⊂ h′ o h′ ⊂ h.

Puede observarse que una jerarquıa tiene asociado un arbol, llamado arbol jerarquico, donde cadanodo del arbol es un elemento de H y las hojas del arbol son los elementos de Ω. Ademas, el arbol tieneuna raız que es Ω mismo. Si este arbol es binario se dice que la jerarquıa es binaria.

La clasificacion jerarquica consiste en construir una jerarquıa sobre Ω, de tal forma que los individuosmas parecidos formen nodos, y los grupos de individuos mas similares tambien formen nodos.

Se puede asociar un ındice f a la jerarquıa, tal que:

1. f(h) ≥ 0,

2. ∀i ∈ Ω : f(i) = 0,

3. ∀h, h′ ∈ H : h ⊂ h′ ⇒ f(h) ≤ f(h′).

Se dice entonces que (H, f) es una jerarquıa indexada.

Pueden consultarse las siguientes referencias como una introduccion a estos conceptos: [6, pp. 119–138,tomo 1], [12, pp. 544–558], [19, pp. 74–76], [28, pp. 105–108]. De las referencias anteriores, quizas la masaccesible sea [19].

3.2. Clasificacion jerarquica ascendente

El algoritmo general de clasificacion jerarquica ascendente (CJA) construye, en cada pasouna particion en k clases, que denotaremos Pk , mediante la fusion de los dos conjuntos de la particionanterior (Pk−1 en k − 1) clases que sean mas cercanos en el sentido de δ. El algoritmo procede de lasiguiente manera:

1. k := 0; ∀i ∈ Ω, i ∈ H ; Pk := i|i ∈ Ω;

2. k := k + 1 ;

3. escoger h1, h2 ∈ Pk tales que δ(h1, h2) sea mınimo; sea h := h1∪h2; sea Pk := (Pk−1∪h)−h1, h2;sea H := H ∪ h;

4. calcular f(h) y δ(h, h′), para todo h′ ∈ H ;

5. mientras k < n − 1 ir al paso 2;

6. H = H ∪ Ω;

El H obtenido es la jerarquıa deseada. Se define un ındice f , como una funcion f : H −→ R+ definidapor:

f(h) =

0 si h es un conjunto unitarioδ(h1, h2) si h1, h2 se fusionaron en el algoritmo para formar h

Esta indexacion hace que el arbol de clasificacion sea mas facilmente interpretable, pues da la idea de laaltura de los nodos del arbol: entre mas bajos sean los nodos mas parecidos son los objetos que estandebajo del nodo.


3.2.1. Ejemplos didacticos

Ejemplo 4 Supongase que se tiene los siguientes valores de una disimilitud sobre Ω = a, b, c, d:

a b c da 0 1 3 5,5b 0 2 4,5c 0 2,5d 0

Puede verse que el mınimo de la disimilitud se alcanza para la disimilitud entre a y b, cuyo valor es1. Por lo tanto, se agregan estos dos individuos y al usar la agregacion del salto mınimo δmın se obtienela nueva tabla:

a, b c da, b 0 2 4,5

c 0 2,5d 0

Ahora, el mınimo valor es para δ(a, b, c) = 2, por lo que se fusionan a, b y c, obteniendose lanueva tabla:

a, b, c da, b, c 0 2,5

d 0

De esta forma, se obtiene el arbol jerarquico que se muestra en la figura 2.

a b c d

1

2

3

Figura 2: Arbol de clasificacion obtenido al usar la agregacion del salto mınimo

Ejemplo 5 En caso de usarse la agregacion del salto maximo δmax sobre los datos anteriores, se obten-drıan sucesivamente las dos tablas siguientes:

a, b c da, b 0 3 5,5

c 0 2,5d 0

a, b c, da, b 0 5,5c, d 0

y el arbol de clasificacion serıa el presentado en la figura 3.

12 Javier Trejos

a b c d

1

2

3

4

5

Figura 3: Arbol de clasificacion opbtenido al usar la agregacion del salto maximo

Ejemplo 6 Por otra parte, si se usa la agregacion del salto promedio δprom sobre los datos anteriores,se obtienen las tablas:

a, b c da, b 0 2,5 5

c 0 2,5d 0

a, b, c da, b, c 0 4,16

d 0

Puede verse que en la primera tabla se alcanza el mınimo para dos valores diferentes: δ(a, b, c) = 2,5 =δ(c, d). Ante esta situacion, el usuario debe decidir cual de las dos posibles fusiones hara.2 Suponiendoque se fusionan a, b con c, se obtiene el siguiente arbol mostrado en la figura 4.

a b c d

1

2

3

4

Figura 4: Arbol de clasificacion obtenido al usar la agregacion del salto promedio

El lector puede comprobar que de haber escogido la fusion de c con d al arbol de clasificacion hubieratenido una forma diferente.

2En los programas de computacion, normalmente se decide automaticamente cual fusion se hara; por ejemplo, se sugierehacer aquella que involucre al menor ındice de individuo.


3.2.2. Formula de recurrencia

Segun los ejemplos mostrados anteriormente, puede apreciarse que luego de cada fusion deben calcu-larse algunos valores de la agregacion: aquellos que involucran al grupo recien creado, y que ademas sesuprime de la tabla a los elementos individuales que se fusionaron. Se acuerdo con la definicion de losındices de agregacion dados, todos ellos se calculan a partir de la tabla original de las disimilitudes, y noa partir de la tabla recien calculada. Para evitar hacer referencia siempre a la tabla original, y hacer estecalculo de actualizacion solamente a partir de la ultima tabla de que se dispone, es que se han encontradoformulas de recurrencia o actualizacion de las agregaciones. Estas formulas son especialmente utiles paralas agregaciones del salto promedio y la de Ward. Si denotamos a y b los dos elementos que se fusionanen una etapa, y h cualquier otro elemento, entonces las formulas de actualizacion para δprom y δward son:

δprom(h, a ∪ b) =card(a)δprom(h, a) + card(b)δprom(h, b)

card(a) + card(b)

δward(h, a ∪ b) =(card(h) + card(a))δward(h, a) + (card(h) + card(b))δward(h, b) − card(h)δward(a, b)

card(a) + card(b)

donde card(a), card(b), card(h) son respectivamente las cardinalidades de a, b y h.

Ejemplo 7 Considerese la siguiente tabla con los valores de una disimilitud:

a b c d ea 0 25 18 25 10b 0 30 40 34c 0 10 15d 0 18e 0

Usando la agregacion del salto promedio δprom, se obtiene la secuencia de tablas:

a b c, d ea 0 25 21,5 10b 0 35 34

c, d 0 16,5e 0

a, e b c, da, e 0 29,5 19

b 0 35c, d 0

a, c, d, e ba, c, d, e 0 32,25

b 0

y el arbol de clasificacion mostrado en la figura 5.

3.2.3. Inversiones

Se dice que una clasificacion jerarquica produce una inversion cuando se construye h = a ∪ b conf(h) < f(a) o f(h) < f(b). Diday [19] dio condiciones sobre los coeficientes de la formula de recurrenciapara que no se produzcan inversiones. Los cuatro ındices de agregacion no producen inversiones como sepuede verificar sobre el teorema de Diday, pero hay otros ındices que sı pueden producir, como el de ladistancia entre centros de gravedad δ(a, b) = ||ga − gb||2.

3.3. Algoritmos ascendentes acelerados

A partir de la investigaciones de Bruynooghe, se estudian algoritmos mas eficientes para construir lasjerarquıas. Existen dos enfoques, fundamentalmente: el de los vecindarios reducibles y el de los vecinosrecıprocos.

El primero establece que, dado un umbral r, cuando se cumple una propiedad llamada de vecindariosreducibles, en cada paso de la construccion jerarquica ascendente, solamente se examinan los vecinos

14 Javier Trejos

c d a e b

10

20

30

Figura 5: Arbol de clasificacion obtenido al usar la agregacion del salto promedio

mas cercanos de r de un grupo existente. Este criterio se puede encontrar en: [28, 171–194], [29, 368–380], Ademas, Diday [19, 91–96] dio condiciones sobre los coeficientes de la formula de recurrencia delanza & Williams, para caracterizar a los ındices de agregacion que cumplen la propiedad de vecindariosreducibles.

El segundo enfoque se debe a De Rham y se conoce como el principio de vecinos recıprocos: dos gruposa y b se llaman vecinos recıprocos si a es el grupo mas cercano de b y b el de a. La construccion jerarquicaascendente se puede simplificar si se fusionan, desde un primer paso, todos los vecinos recıprocos. Una vezhechas estas fusiones, se calculan los vecinos recıprocos de los grupos formados y se recomienza, alternandoeste paso de fusion con el desarrollo normal del algoritmo de clasificacion jerarquica ascendente. Puedeencontrarse una descripcion del procedimiento en [15, 176–177].

Existen demostraciones sobre la equivalencia de los resultados obtenidos con cualquiera de los dosenfoques acelerados anteriores y el algoritmo usual de clasificacion jerarquica ascendente.

3.3.1. Ejemplo de notas escolares

Consideramos el ejemplo de notas escolares, en que 10 estudiantes son descritos por las notas entre 0y 10 obtenidas en 5 materias: matematicas, ciencias, historia, espanol y educacion fısica.

La clasificacion jerarquica usando la agregacion de Ward con la distancia euclıdea, da como resultado:Lucıa

Marıa

Carlos

Andres

Luis

Sonia

Pedro

Ines

Ana

Jose

Puede verse que hay una clara clasificacion en tres clases, que es:


C1 = Lucıa,Marıa,Andres,Carlos,C2 = Luis,Sonia,C3 = Pedro,Ines,Ana,Jose.Si se quiere hacer una clasificacion en dos clases, entonces se unen C1 y C2.

El lector deseoso de consultar aplicaciones de la clasificacion jerarquica, puede encontrar 13 aplica-ciones en [6, pp. 321–538, tomo 1].

3.4. Aproximaciones por ultrametricas

Una propiedad esencial es que toda jeraquıa indexada tiene asociada una ultrametrica y viceversa.La demostracion de esta propiedad, llamada teorema de Johnson–Benzecri, puede consultarse en: [6, pp.138–142, tomo 1], [19, pp. 98–102], [28, pp. 111–114], [48, pp. 14–15].

La propiedad anterior puede inducir a pensar que, para poder obtener un jerarquıa, basta con encontrarun ultrametrica δ “similar” a la disimilitud d definida sobre Ω. Esta idea fue seguida por autores comoM. Roux, que propuso un algoritmo que hace modificaciones sobre d con el fin de ir obteniendo poco apoco la ultrametrica deseada. De hecho, el supremo de las ultrametricas inferiores a d es a su vez unaultrametrica, llamada la ultrametrica subdominante. Esta ultrametrica puede ser obtenida mediante laconstruccion de un arbol de longitud mınima sobre Ω3, usando por ejemplo los algoritmos de Prim o deKruskal. Tambien Roux habıa propuesto un algoritmo que examina todos los tripletes de elementos de Ω,construyendo cada vez un triangulo isosceles agudo (puede consultarse [12, pp. 568–569], [48, pp. 70–76]).

3.5. Clasificacion jerarquica descendente

Debe notarse que la construccion de un arbol de clasificacion podrıa tambien hacerse descendente-mente. Los algoritmos descendentes parten de Ω y buscan particionar cada grupo de dos (hacen dico-tomıas), hasta obtener los conjuntos unitarios formados por los individuos. Cada metodo difiere en elcriterio para hacer la dicotomıa. Los metodos mas conocidos son los de Williams & Lambert, de Hubert,de Roux y de Edwards & Cavalli–Sforza. Presentaciones de estos se pueden encontrar en [27, pp. 251–276], [43, pp. 85–92], [48, pp. 24–28]; con menos detalle hablan [6, pp. 85–92, tomo 1, sobre todo sobreun metodo usado por Lacoste y basado en el Analisis Factorial] [16, 126–127], [28, pp. 206–212], [22, pp.82–88].

3.6. Observaciones sobre la clasificacion jerarquica

La clasificacion jerarquica ascendente tiene dos defectos que ya hemos observado sobre los ejemplos ysobre los que hay que insistir:

En primer lugar, los resultados dependen de la agregacion que se escoja. Por ello, siempre serecomienda al usuario que haga una reflexion antes de aplicar el metodo, en el sentido de ensogerla agregacion que tenga un mejor sentido en el problema que se este tratando.

En segundo lugar, en el caso en que haya igualdad en el valor de la agregacion para dos parejasdiferentes, se debe escoger la pareja que se fusionara, escogencia que puede llevar a resultadosdiferentes.

Finalmente, se debe tomar en cuenta que la clasificacion jerarquica aproxima siempre una tabla de datosa una ultrametrica, lo cual puede significar en una perdida grande al hacer un ajuste demasiado burdo.

3Un arbol de longitud mınima sobre un conjunto Ω es un arbol tal que las aristas tienen valores, todos los nodos sonelementos de Ω, y la suma de los valores de las aristas es mınima entre todos los arboles con esas caracterısticas.

16 Javier Trejos

4. Clasificacion por Particiones

Los metodos de clasificacion por particiones buscan una sola particion de Ω, mediante la optimizacionde algun criterio. Existen basicamente dos tipos de metodos:

los que fijan a priori el numero de clases,

los que no fijan este numero.

Los primeros tienen la ventaja de la sencillez y rapidez, mientras que los segundos tienen la ventajaobvia de buscar el numero de clases. Sin embargo, estos ultimos tienen la gran desventaja de depender deun gran numero de parametros que deben ser estimados por el usuario y cuya manipulacion no es facilsin una adecuada experimentacion y practica. Ejemplos de estos metodos son Isodata y Wishart.

En este curso solo abordaremos los primeros metodos, que se puede agrupar en un esquema llamadode Nubes Dinamicas.

Los metodos de nubes dinamicas estan basados en el principio que una clase puede ser representada poralgun objeto, sea este un punto promedio, un individuo o grupo de individuos de la clase, un conjunto deparametros, etc; a este representante lo llamaremos nucleo. El primer algoritmo de este tipo fue propuestopor Forgy (1965), y luego fueron propuestos otros similares por McQueen, Diday, Jancey, etc.

La idea subyacente es:

asignar los individuos al nucleo mas cercano,

calcular los nucleos con las clases formadas en el paso anterior,

iterar los pasos anteriores hasta obtener estabilidad.

Se parte de una configuracion inicial de nucleos, y se puede probar que el metodo converge a unaparticion que no mejora el criterio. Dependiendo del contexto y del tipo de nucleo, se define un criterioa ser mejorado.

4.1. Problema combinatorio

Es necesario hacer notar que, cuando se quiere obtener una particion en K clases de un conjunto conn individuos, no tiene sentido examinar todas las posibles particiones del conjunto de individuos en Kclases. En efecto, se esta en presencia de un problema combinatorio muy complejo; solo para efectos deilustracion, mencionemos que el numero de particiones de un conjunto con 60 elementos en 2 clases esaproximadamente 1018, y para 100 elementos en 5 clases anda por 1068. De hecho, se puede probar que elnumero S(n, K) de particiones diferentes de un conjunto de n individuos en K clases, cumple la ecuacionde recurrencia

S(n, K) = S(n − 1, K − 1) + kS(n − 1, K)

Esto lleva a que

S(n, K) =1

K!

K∑

i=1

(−1)K−i

(Ki

)in

De lo anterior se deduce la necesidad de contar con metodos y algoritmos que den una solucionsatisfactoria del problema propuesto, aunque evidentemente puede que no se obtenga la mejor solucionen todos los casos.

4.2. Criterio de la inercia

Como se ha mencionado, se quiere obtener clases lo mas homogeneas posibles y tal que esten suficien-temente separadas. Este objetivo se puede concretar numericamente a partir de la siguiente propiedad:


supongase que se esta en presencia de una particion P = (C1, C2, . . . , CK) de Ω, donde g1,g2, . . . ,gK sonlos centros de gravedad de las clases:

gk =1n

∑

i∈Ck

xi,

g es el centro de gravedad total:

g =1n

n∑

i=1

xi.

Si se denota I = 1n

∑ni=1 ‖xi − g‖2 la inercia total de la nube de puntos,

B(P ) =K∑

k=1

|Ck|n

||gk − g||2 (1)

la inercia inter-clases, es decir la inercia de los centros de gravedad respecto al centro de gravedad total,y

W (P ) =K∑

k=1

I(Ck) =1n

K∑

k=1

∑

i∈Ck

‖xi − gk‖2 (2)

la inercia intra-clases, es decir la inercia al interior de cada clase, entonces se tiene la igualdad de Fisher:I = B + W. Observese que B mide precisamente la “separacion” de la nube de puntos, al medir lainercia entre los centros de gravedad; si esta inercia es grande se deduce que los centros de gravedad estanbastante separados (son dispersos). Por su parte, W mide la homogeneidad de las clases; en efecto, si Wes pequeno entonces cada I(Ck) es pequeno y ası la dispersion al interior de cada clase es pequena.

Como la inercia I es fija, dada la nube de puntos, entonces al minimizar B se maximiza automati-camente W . Por lo tanto, los dos objetivos (homogeneidad al interior de las clases y separacion entrelas clases) se alcanzan al mismo tiempo al querer minimizar W . Ası, el objetivo en el metodo de nubesdinamicas es encontrar una particion P de Ω y representantes de las clases, tales que W (P ) sea mınima.

Existen otros criterios de clasificacion, como por ejemplo det(W )/ det(B) → mın, o criterios de en-tropıa. Sin embargo, remitimos al lector a [38] para mas detalles en este aspecto.

4.3. Metodo de k-medias

Existe un poco de confusion en la literatura acerca del metodo de las k-medias, ya que hay dosmetodos distintos que son llamados con el mismo nombre. Originalmente, Forgy [24] propuso en 1965 unprimer metodo de reasignacion-recentraje que consiste basicamente en la iteracion sucesiva, hasta obtenerconvergencia, de las dos operaciones siguientes:

Representar una clase por su centro de gravedad, esto es, por su vector de promedios

Asignar los objetos a la clase del centro de gravedad mas cercano.

Poco despues, McQueen [37] propone un metodo muy similar, donde tambien se representan las clases porsu centro de gravedad, y se examina cada individuo para asignarlo a la clase mas cercana. La diferenciacon el metodo de Forgy es que inmediatamente despues de asignar un individuo a una clase, el centrode esta es recalculado, mientras que Forgy primero hacıa todas las asignaciones y luego recalculaba loscentros. Es claro que el metodo de McQueen depende del orden en que se presenten los datos. Este metodode McQueen ya habıa sido propuesto en Francia por S. Regnier en 1965 [41], pero en el contexto de labusqueda de una particion de consenso, llamada particion central. Variantes del metodo de Forgy sonpropuestas en Francia como Metodo de Nubes Dinamicas por E. Diday a partir de 1967 [17].

Es McQueen quien propone el nombre “k-means”, que se usa hasta la fecha, aun si estos metodostambien reciben nombres como nubes dinamicas, centros moviles, o reasignacion-recentraje.

18 Javier Trejos

4.3.1. Metodo de Forgy

Denotaremos Ω el conjunto de n individuos que queremos clasificar y supondremos que estan descritospor p variables cuantitativas x1, x2, . . . , xp.

En el caso en que se esta en presencia de variables cuantitativas, tiene sentido el calculo de promedios yde distancias euclıdeas. Por lo tanto, tambien tiene sentido que cada clase este representada por su centrode gravedad, esto es, por un individuo ficticio cuyas coordenadas son los valores promedio de las variablespara los individuos pertenecientes a la clase. Este es el caso mas simple y el usado mas corrientemente.Generalemente, se usara la distancia euclıdea clasica en este contexto.

Como se menciono anteriormente, el metodo de las k-medias consiste en:

1. Escoger una particion inicial, al azar o con base en algun otro criterio.

2. Calcular los centros de gravedad de la particion.

3. Asignar cada objeto a la clase del centro de gravedad mas cercano.

4. Repetir los pasos 2 y 3 mientras las clases en el paso 3 se modifiquen, esto es, hasta que se obtieneestabilidad en la particion.

Se prueba que efectivamente el metodo alcanza la estabilidad despues de unas pocas iteraciones [19].Conviene hacer notar que, en una implementacion computacional, la escogencia al azar es mas bien de

una muestra de K objetos iniciales que serviran de nucleos iniciales, y luego se asignan todos los demasobjetos a la clase del nucleo mas cercano, formandose entonces la particion inicial.

4.3.2. Ejemplo de las notas escolares

El resultado de la aplicacion del metodo de k-medias, dependera de la escogencia inicial de los nucleos.Por ello, se recomienda correr varias veces el metodo y escoger la mejor solucion obtenida en esas corridas.

Para la tabla de notas escolares, se aplico el paquete computacional PIMAD 25 veces, obteniendoseen 17 de ellas la solucion optima (que corresponde a la misma obtenida por el metodo jerarquico conagregacion de Ward). La tabla siguiente muestra los resultados obtenidos:

Particion Numero de veces W (P ) B(P )obtenida

C1 = Lucıa,Andres,Carlos,Marıa 17 0.75 4.97C2 = Luis,SoniaC3 = Pedro,Ines,Ana,JoseC1 = Lucıa,Andres,Carlos,Marıa,Luis,Sonia 3 2.48 3.24C2 = Pedro,InesC3 = Ana,JoseC1 = Lucıa,Andres,Carlos,Marıa,Luis,Sonia 2 2.52 3.20C2 = Ines,Ana,JoseC3 = PedroC1 = Lucıa,Andres,Carlos,Marıa,Luis,Sonia 1 2.55 3.17C2 = Ines,AnaC3 = Pedro,JoseC1 = Lucıa,Andres,Carlos,Luis,Sonia 1 2.72 3.00C2 = Pedro,InesC3 = Ana,Jose,MarıaC1 = Lucıa,Andres,Carlos,Marıa,Pedro,Ines,Ana,Jose 1 3.06 2.66C2 = LuisC3 = Sonia


4.3.3. Metodo de transferencias

Un segundo tipo de metodos de particionamiento son los algoritmos del tipo de transferencias , origi-nalmente propuestos por Regnier y por McQueen. Consisten en hacer la transferencia entre una clase yotra, de un unico elemento de Ω a la vez, haciendo mejorar algun criterio en cada iteracion.

El algoritmo general es como sigue (aquı W es un criterio general de clasificacion, no necesariamentela inercia intra-clases):

1. Se da una particion inicial P = (C1, C2, . . . , Ck) de Ω.

2. Se toma un elemento x ∈ Ω arbitrario, con x ∈ Ck. Llamamos Ckk′(x) la particion de Pk consistente

en transferir x de Ck hacia Ck′ en la particion P y dejar las demas clases iguales.

3. Sea P ∗ tal que W (P ∗) = mınW (Ckk′(x)) : k′ = 1, . . . , K. Entonces ponemos P := P ∗.

4. Se repiten los pasos 2 y 3 para todos los elementos x ∈ Ω.

5. Se detiene cuando al aplicar 4 no ocurre ninguna nueva transferencia.

En el caso Euclıdeo, se tiene n individuos descritos por p variables cuantitativos y Rp esta provisto deuna distancia euclıdea. Se busca la particion P = (C1, . . . , CK) de Ω que minimice la inercia inter-clasesW . Por tanto, al pasar x de Ck a Ck′ se debe minimizar

W (Ckk′ (x)) =

∑

h/∈k,k′

I(Ch) + I(Ck \ x) + I(Ck′ ∪ x).

En el caso general, Ω es arbitrario, con d un ındice de disimilitud sobre Ω. El criterio W que se definesobre la particion P toma en cuenta la relacion de equivalencia R asociada a P :

W (P ) = supd(i, j) : iRj; i, j ∈ Ω.

Si se tiene P = (C1, . . . , CK), con x ∈ Ck, para transferir x a Ck′ es necesario que:

supd(x, y) : y ∈ Ck′ < supd(x, y) : y ∈ Ck.

Debe observarse que, al igual que en el metodo de k-medias, aquı tambien la particion final P ∗ dependede la particion inicial. Ası mismo, el numero K de clases es dado a priori. Sin embargo las clases tambiense pueden vaciar en el transcurso del algoritmo. Igualmente, ese numero K puede no ser un numero“natural” de clases para Ω. Para dar las K clases iniciales en el caso euclıdeo, tambien se puede usar elmetodo de Polos de Atraccion [35].

4.4. Metodos de nubes dinamicas

Se quiere obtener una particion de Ω en K clases bien agregadas, bien separadas y de interseccionvacıa. El numero K de clases es dado a priori y los datos pueden ser de cualquier naturaleza.

Este metodo fue introducido por Diday [17], generalizando el metodo de k-medias de Forgy. Se basaen que cada clase debe tener una representacion (llamada nucleo), y luego se hace una busqueda iteradade nucleos y de particiones, hasta optimizar un cierto criterio.

En el metodo general de nubes dinamicas, cada clase estara representada por un nucleo, que sera unelemento representativo de los integrantes de la clase. El algoritmo general de Nubes Dinamicas es elsiguiente:

1. Se da una particion inicial de Ω.

2. Se calculan los nucleos, mediante una funcion de representacion.

3. Se forma una particion, asignando cada elemento al nucleo mas proximo, mediante una funcion deasignacion.

20 Javier Trejos

4. Se repiten los pasos 2 y 3 hasta que las clases se estabilicen.

La escogencia de los nucleos iniciales, se hace generalmente de manera aleatoria. En el caso general,se escoge K veces m elementos entre los individuos. Se usa un criterio aditivo del tipo

W (P ) =K∑

k=1

∑

xi∈Ck

D(xi, Nk)

donde Nk es el nucleo de Ck (formado por m objetos) y D es una medida de disimilitud (por ejemplo,una agregacion) entre los objetos xi y los nucleos Nk (que son conjuntos de objetos). El nucleo Nk sedefine como el subconjunto de Ck con m elementos que minimice

∑i∈Ck

D(xi, Nk).Se puede probar que [19] en cada iteracion se mejora W y ademas se converge a una clase estable.Es claro que el metodo de k-medias corresponde al metodo de nubes dinamicas cuando los nucleos

son centros de gravedad.

4.4.1. Variantes del metodo de nubes dinamicas

Existe una serie de variantes al metodo de nubes dinamicas. Basicamente, para cada una de ellasse debe definir el criterio a optimizar, los nucleos (funcion de representacion), y la forma de asignarelementos a las clases (funcion de asignacion).

Metricas adaptativas. El metodo de k-medias tiene la tendencia de formar clases esfericas con mis-ma cardinalidad. Por ello, no es util cuando se trata de identificar clases que tengan una mismaforma de dispersion, quiza no necesariamente esferica, pero con una o varias direcciones de pro-longamiento (sobre un eje discriminante, por ejemplo). Por tanto, en este caso se quita la restriccionde que la medida de distancia sea la misma durante todo el algoritmo. Mas bien se trata de buscariterativamente la distancia que mejor se adapte a los datos.

En presencia de objetos descritos por variables cuantitativas, el criterio es

W (P ) =K∑

k=1

∑

i∈Ck

‖xi − gk‖2M

para el caso de una sola metrica M , o bien

W (P ) =K∑

k=1

∑

i∈Ck

‖xi − gk‖2Mk

para el caso en que se tiene una metrica Mk asociada a cada clase Ck .

En cada iteracion del algoritmo, se calcula no solo los centros de gravedad gk, sino tambien lasmetricas. En el primer caso M = det(V )1/pV −1, donde V es la matriz de varianzas intra-clases,mientras que en el segundo caso Mk = det(Vk)1/pV −1

k , donde Vk es la matriz de varianzas intra-clases de clase Ck.

Regresion tipologica. Se pretende detectar K comportamientos locales de regresion lineal y las rectasasociadas, de manera que se minimice un criterio de adecuacion de las muestras con sus representa-ciones lineales (criterio de mınimos cuadrados ) [18].

La idea es dar una particion del espacio Ω de n individuos a los que se han medido m variablesexplicativas Xj , y una variable a explicar y, ası como los hiperplanos de regresion asociados a cadauna de las clases de tal particion.

El nucleo de una clase es el vector de coeficientes de regresion Bk = (b1k, . . . , bm

k )t asociados a laregresion en Ck. El criterio a minimizar es

W (P ) =K∑

k=1

‖Y k − Xk Bk‖2Rnk =

K∑

k=1

nk∑

i=1

(yki − xk

i bik)


donde nk = |Ck |.Se asigna un individuo zi = (x1

i , . . . , xpi , yi) a la clase Ck que minimice d(zi, Bk) = (yi − xi Bk)2.

Mezclas de distribuciones. Se dispone de una muestra Ω cuyos elementos siguen distintas distribu-ciones de probabilidad. Se quiere estimar los parametros de tales distribuciones. Este es uno de losproblemas mas viejos de la Estadıstica Inferencial, que aquı se aborda desde el punto de vista de laClasificacion Automatica, en particular con el metodo de Nubes Dinamicas.

Se tiene una muestra Ω = x1, . . . ,xn de una variable aleatoria X en Rs, cuya ley admite ladensidad f(x) =

∑Kk=1 pk f(x, ak), donde pk > 0, ∀k,

∑pk = 1. Se supone que f(·, ak) es una

densidad que depende del parametro ak ∈ Rs (donde s es el numero de componentes del parametro),y pk es la probabilidad de que un punto de la muestra siga la ley f(·, ak). Se quiere estimar las Kcomponentes y los parametros desconocidos pk y ak. Tomamos pk = |Ck|/n como estimador de pk.

Como se busca una particion P = (c1, . . . , cK) tal que cada clase Ck sea asimilable a la ley f(·, ak),el nucleo de la clase k-esima es el parametro ak ∈ Rs. El criterio a maximizar es

W (P ) =K∑

k=1

ln V (Ck , ak),

donde V (Ck , ak) =∏

x∈Ckf(x, ak) es la funcion de verosimilitud de la submuestra Ck para la

ley f(·, ak). Un objeto x se asigna a la clase k que maximiza f(x, ak). El nucleo ak maximiza laverosimilitud del parametro de la densidad asociada a la muestra Ck. En el caso normal o Gaussiano,se tiene ak = (µk, Γk), donde:

µk =1

|Ck|∑

x∈Ck

x

Γk =1

|Ck|∑

x∈Ck

(x − µk) (x − µk)t.

Hay que hacer notar que, a pesar de que este metodo converge rapidamente, la precision es mejorcon los metodos clasicos de estimacion de parametros, por ejemplo con los algoritmos tipo EM ySEM [18].

Conceptos conjuntistas. Ilustramos este tipo de nucleo con el ejemplo mostrado en la figura 6.

-

6

1 2 3 4 5 6

12345

0

y

x

••

• •

••

•

•

•

•

••• •

•

••

••A C

B

Figura 6: Los nucleos son conceptos conjuntistas: A = [x < 4]; B = [x ≥ 4] [y < 3]; C = [x ≥ 4] [y ≥ 3].

Otros. El nucleo puede ser un plano factorial, un hiperplano discriminante, etc. [18]

4.5. Metodo de Fisher

El Metodo de Fisher [23] es optimo para particionar un conjunto descrito por una unica variablecuantitativa en K clases. Usa el criterio intra-clase y se fundamenta en el orden total asociado a la variablecuantitativa (o cualitativa-ordinal) inducido por esta sobre el conjunto de individuos. La particion optimadebera ser compatible con este orden.

22 Javier Trejos

Mas especıficamente, si v: Ω 7→ R es la variable, sean v1 < v2 < · · · < vm los m valores diferentesque toma v (m ≤ n). Naturalmente suponemos K < m, donde K es el numero de clases de la particionoptima buscada.

Si dos individuos ω, ω′ ∈ Ω son tales que v(ω) = v(ω′), estos deben quedar en una misma clase y, ypara efectos de clasificacion pueden considerarse como uno solo objeto. De esta manera, el problema sereduce a hallar una particion P = (C1, . . . , CK) de v1, . . . , vn que minimice la inercia intra-clase de P :

W (P ) =k∑

i=1

∑

vj∈Ci

pj(vj − g(Ci)) =k∑

i=1

I(Ci),

con pj el numero de individuos ω tales que v(ω) = vj , y g(Ci) el centro de gravedad del conjunto denumeros vj . Para simplificar, en lugar de v1, . . . , vn escribimos 1, . . . , m.

De manera recursiva se calcula una sucesion de particiones optimales Cil del conjunto inicial i, . . . , m

en l clases, para finalizar con C1K , la particion optima de Ω buscada.

El algoritmo de Fisher es como sigue:

1. Para i = 1, . . ., m, se define Ci1 = i, i + 1, . . . , n.

2. Para l = 2, . . ., K−1, se calcula la particion Cil = (i, i+1, . . . , j, Cj+1

l−1 ) de i, . . . , m, donde Cj+1l−1

ha sido calculada en el paso j−1 esimo, j ∈ i, . . . , m−l+1 y que minimice I(1, . . . , j)+W (Cj+1l−1 ).

3. Finalmente debe construirse una particion C1K = (1, . . . , i, Ci+1

K−1) y que minimice I(1, . . . , j) +W (Cj+1

K−1)

La demostracion de la optimalidad del algoritmo de Fisher descansa en los dos lemas que siguen, quepresentamos sin demostracion.

Lema 1 Una particion P ∗ que minimiza W esta formada por clases contiguas. Es decir, si dos individuosωi, ωj de una misma clase de P ∗ toman los valores v(ωi), v(ωj), entonces no hay individuos externos aesta clase que tomen su valor de v en el intervalo [v(ωi), v(ωj)].

Lema 2 Si una particion P ∗ = (C∗1 , C∗

2 , . . . , C∗K) optimiza W en Ω, entonces (C∗

2 , . . . , C∗K) optimiza W

en Ω \ C∗1 .

La siguiente proposicion, basada en los lemas anteriores asegura que tal algoritmo construye unaparticion optimal de Ω.

Proposicion 3 Para k = 1, . . ., K, P 1k es una particion de 1, . . . , m en k clases de inercia intra-clase

mınima.

No siempre tiene sentido el criterio cuando las contribuciones de cada clase son muy pequenas, com-portamiento que tienden a tener las cases formadas por muy pocos elementos. En este caso podrıa pedirseun mınimo de elementos por clase.

El algoritmo de Fisher es de complejidad (K −1)m2, y la solucion que da no es necesariamente unica.

4.6. Uso de heurısticas modernas de optimizacion

Debido a que los metodos de particionamiento encuentran optimos locales del criterio a optimizar, seha buscado mejorarlos con el uso de heurısticas modernas de optimizacion combinatoria. En otro docu-mento [50] se describe su uso e implementacion, para el caso de sobrecalentamiento simulado, busquedatabu, algoritmos geneticos, colonias de hormigas y enjambres de partıculas. Los resultados obtenidos sonsuperiores a los que se obtienen con los metodos descritos aquı, como k-medias o clasificacion jerarquicade Ward.


5. Metodos Arboreos No Jerarquicos

Existe una serie de metodos de clasificaci”on automatica que no construye arboles jerarquicos, sinootras estructuras, ya sea de arbol u otros grafos. A continuacion veremos dos de ellas: los arboles aditivosy las piramides.

5.1. Arboles aditivos

Un arbol ditivo es una representacion tipo grafo, en la que las hojas representan a los objetos aclasificar y hay una serie de nodos internos (algunos de ellos tambien pueden ser objetos, pero no es lomas comun), de manera que la distancia entre dos objetos sea la suma de las longitudes de las aristasque los unen.

Para ello, se introduce el concepto de distancia aditiva, que es la que corresponde a los arboles aditivos.

Definicion 1 Sea (H, L) un arbol valuado, con H = (S, A) donde S es el conjunto de nodos del arbol H,A es el conjunto de aristas y L es el conjunto de valores positivos asociados a las aristas. Una disimilitudaditiva dL sobre S es una disimilitud tal que

dL(s, t) = longitud del camino entre s y t.

Tal definicion es correcta, pues en un arbol hay un unico camino entre dos nodos.

Definicion 2 Una distancia arborea sobre Ω es una disimilitud d : Ω × Ω → R+ tal que:

i) ∀i ∈ Ω : d(i, i) = 0.

ii) ∀i, j ∈ Ω : d(i, j) = d(j, i).

iii) ∀i, j, k, l ∈ Ω : d(i, j) + d(k, l) ≤ Max[d(i, k) + d(j, l), d(i, l) + d(j, k)].

La desigualdad de (iii) se llama condicion de los cuatro puntos, o desigualdad cuadrangular.Vease que esta desigualdad es muy parecida a la que sirve para definir una ultrametrica. Como en esteultimo caso, habra dos terminos de la desigualdad que son iguales entre sı, y mayores o iguales al tercero.

Vease que una distancia arborea es una distancia (en el sentido corriente); esto es, tambien cumple ladesigualdad triangular. Ademas, toda ultrametrica es una distancia arborea.

Definicion 3 Un arbol aditivo sobre Ω es un arbol en el que todos los nodos terminales son elementosde Ω, y donde las aristas estan valuadas positivamente.

Debe notarse que en un arbol aditivo puede haber elementos de Ω que no son nodos terminales. Porejemplo, en la figura 7 se muestran dos arboles aditivos sobre Ω = p, q, r, s, t .

p

qr

s

tp

q

r

s

t

Figura 7: Ejemplos de arboles aditivos.

Es claro que se puede definir una distancia aditiva a partir de un arbol aditivo. Ademas, Zaretskii(1967) probo que, si d una disimilitud sobre Ω, entonces los valores de d se pueden representar como un

24 Javier Trejos

arbol aditivo si, y solo si, d verifica la condicion de los cuatro puntos. Esto es, hay una correspondenciabiunıvoca entre arboles aditivos y distancias aditivas.

Con base en el teorema anterior se puede plantear el problema de buscar algoritmos que encuentrenuna distancia arborea “proxima” a una disimilitud dada sobre Ω. M. Roux y G. Brossier han presentadoalgoritmos en este sentido. Los metodos del primero [44] se basan en tratar de obtener una distanciaarborea a partir de una disimilitud, haciendo modificaciones sucesivas en esta ultima, hasta que se con-verge. Por su parte, Brossier [11] propone obtener la distancia arborea mas proxima a un ındice dedisimilitud dado, basado en la descomposicion de toda cuadrangular como la suma de una ultrametricay una distancia con centro. De esta forma, la complejidad del algoritmo, que en general es del orden n4,se reduce al orden n2 o n3. Este algoritmo tambien se basa en el uso de la metrica

√d, con propiedades

muy interesantes.

5.2. Piramides

Las piramides fueron introducidas por E. Diday [20] para enriquecer la representacion jerarquica, demanera que un nodo puede estar contenido en dos nodos superiores, en lugar de solo uno como en unajerarquıa.

Una piramide induce una dismilitud mas cercana a los datos que la ultrametrica inducida por un arboljerarquico.

Un estudio cercano de las propiedades de las jeraquıas lleva al estudio de los ordenes sobre los datos,pasando por el estudio de las matrices de Robinson: matrices en las que los valores crecen conforme sealeja la fila o la columna de la diagonal principal.

Definicion 4 Sea Ω un conjunto finito y P un conjunto de partes de Ω. P es una piramide sobre Ω si

1. Ω ∈ P

2. ∀ω ∈ Ω, ω ∈ P .

3. ∀h, h′ ∈ P se tiene h ∩ h′ = ∅ o h ∩ h′ ∈ P .

4. Existe un orden θ tal que todo elemento de P es un intervalo segun θ.

Si se considera el conjunto de disimilitudes que no necesariamente convierten a todos los triengulosen isosceles (como las ultrametricas), pero para los cuales existe un orden compatible, se obtienen lasdisimilitudes piramidales, las cuales permiten construir las piramides.

Existe una biyeccion entre los conjuntos de matrices de Robinson y las parejas (d, θ) donde d es unadisimilitud piramidal y θ es un orden compatible con d. Se puede probar que las disimilitudes piramidalesa las cuales se les puede asociar un orden y los dendrogramas tipo piramidal estan tambien en biyeccion.

Se puede probar que los antecesores de un nodo en un arbol piramidal son a lo sumo dos (en una jer-arquıa es solo uno). El algoritmo de clasificacion piramidal ascendente consiste en agregar en cada etapalos dos grupos mas cercanos que aun no han sido agregados dos veces. A esto se le anaden algunas condi-ciones sencillas que permiten evitar la aparicion de un cruzamiento. Como en el caso de las jerarquıas, seusa una formula de recurrencia del tipo Lance & Williams adaptada a las piramides, usando agregacionesde salto mınimo, salto maximo, inercia mınima. Igualmente, tambien se puede usar un algoritmo del tipovecinos recıprocos.

Normalmente, una piramide debe ser simplificada ya sea reduciendo el numero de nodos y aristas,o bien enriqueciendo una jerarquıa dada anadiendo algunas aristas. Para saber mas sobre piramides,consultar [8] o [3].


6. Otros Metodos

La clasificacion automatica es una disciplina en constante evolucion, con multiples trabajos de in-vestigacion reportados cada ano. La revista especializada Journal of Classification es una de las mascitadas en el mundo cientıfico. El congreso de la international Federation of Classification Societies esmuy concurrido; tiene lugar cada dos anos y el proximo sera en julio de 2004 en Chicago.

A continuacion presentamos algunos aspectos menos conocidos de la clasificacion, mas recientes quelos que se han presentado hasta ahora. Se trata de la clasificacion bimodal, la clasificacion difusa, laclasificacion neuronal y la clasificacion neuronal.

6.1. Clasificacion bimodal

La clasificacion bimodal, tambien conocida como clasificacion cruzada, consiste en obtener particionessimultaneas de las filas y columnas de una tabla de datos, de manera que el resultado explique una relacionentre las clases-filas y las clases-columnas. Tambien existen metodos jerarquicos bimodales, o metodostrimodales o multimodales, pero por falta de espacio explicaremos unicamente de forma resumida losmetodos de particionamiento bimodales.

Sea X = (xij)n×m una matriz bimodal que cruza los modos I y J tales que |I | = n, |J | = m yI ∩ J = ∅. Las entradas de X son positivas y reflejan el grado de intensidad en la asociacion entre losmodos filay columna, de tal forma que entre mayor sea el valor de xij , mayor es la asociacion entre i yj; X puede ser, por ejemplo, una tabla de contingencia. Si P = Ak|k = 1, . . . , K es una particion delmodo I y Q = Bl|l = 1, . . . , L una particion del modo J , una clase bimodal de I × J tiene la formaAk × Bl y se dice que (P, Q) es una particion bimodal de I × J en K, L clases. Particiones P y Qpuedes ser caracterizadas por sus matrices indicadoras, que tambien seran denotadas P y Q, siendo elcontexto suficiente para distinguir cual de los conceptos es usado.

Dada una matriz biomdal X y fijando K y L, el problema es encontrar particiones P = (pik)n×K yQ = (qjl)m×L, y una matriz de asociacion W = (wkl)K×L tal que

Z(c, P, Q, W ) =∑

i∈I

∑

j∈J

(xij − c − xij)2

es mınimo, donde xij =∑

k

∑l pikqjlwkl. Se puede ver que en este modelo, llamado aditivo, xij es

representado por xij +c, y entonces hay un termino de error εij que supondremos que cumple∑

i,j εij = 0.Se supone que la constante c modela la parte “comun” de las entradas de X , esto es c = x = 1

pq

∑i,j xij ;

luego, se asume que c = 0 si los xij estan centrados (xij := xij − x).Por lo tanto, el criterio a minimizar es:

Z = Z(P, Q, W ) =∑

i∈I

∑

j∈J

(xij −

K∑

k=1

L∑

l=1

pikqjlwkl

)2

,

que puede ser escrito como:

Z = Z(P, Q, W ) =K∑

k=1

L∑

l=1

n∑

i=1

m∑

j=1

pikqjl(xij − wkl)2. (3)

Dadas P y Q, la matriz W que minimiza Z se obtiene para:

wkl =1

akbl

∑

i∈Ak

∑

j∈Bl

xij , (4)

donde ak = |Ak| y bl = |Bl| con los cardinales de las clases. Notamos que W puede ser interpretada comola matriz de centroides de las clases bimodales, y representa el grado de asociacion entre ambas clases.

26 Javier Trejos

En lo que sigue, escribimos Z(P, Q) en lugar de Z(P, Q, W ) y suponemos que, dadas P y Q, W secalcula segun (4).

La Varianza Explicada del modelo es usualmente reportada en los resultados comparativos, se definecomo

VAF = 1 −∑

i,j(xij − xij)2∑i,j(xij − x)2

. (5)

Es claro que maximizar VAF ∈ [0, 1] es equivalente a minimizar Z.

6.1.1. Metodos de particionamiento bimodal

La mayor parte de los metodos que buscan una particion bimodal esta basados en la transferencia deobjetos. Presentamos a continuacion brevemente algunos de ellos.

Denotamos Aki→ Ak′ la transferencia de la fila i de la clase Ak hacia la clase Ak′ , y analogamente

Blj→ Bl′ la transferencia de la columna j de la clase Bl a la clase Bl′ . Los metodos empiezan con

una particion bimodal inicial (P, Q), que puede ser generada al azar o puede ser el resultado de algunconocimiento previo. Se denota ∆Z la diferencia en el criterio (3) entre las particiones bimodales atnes ydespues de transferencia. Suponemos que los numeros de clases K y L son dados y fijados a lo largo delos algoritmos.

Intercambios Alternantes (Gaul & Schader (1996))

1. Initializar P, Q; calcular W de acuerdo con (4).

2. Alternar los siguientes pasos hasta que Z no mejora:

a) Hacer Aki→ Ak′ para i y k′ escogidos al azar; si ∆Z < 0 aceptar la transferencia, redefinir

P y calcular W usando (4).

b) Hacer Blj→ Bl′ para j y l′ escogidos al azar; si ∆Z < 0 aceptar la transferencia, redefinir

Q y calcular W usando (4).

k-medias (Govaert (1983), Baier et al. (1997))

1. Inicializar P 0, Q0; calcular W 0 de acuerdo con (4); sea t := 0.

2. Repetir los siguietes pasos hasta que Z no mejora:

a) Dados W := W t y Q := Qt, definir P por

Ak := i ∈ I |∑

l

∑

j∈Bl

(xij − wkl)2 → mınk′

∑

l

∑

j∈Bl

(xij − wk′l)2.

b) Dados W := W t y P := P t, definir Q por

Bl := j ∈ J |∑

k

∑

i∈Ak

(xij − wkl)2 → mınl′

∑

k

∑

i∈Ak

(xij − wkl′ )2.

c) Calcular W t de acuerdo con (4).d) Sean t := t + 1, P t := P , Qt := Q.

Se puede probar que la sucesion Zt := Z(P t, Qt) es decreciente.

Recocido Simulado (Trejos & Castillo (2000))El usuario escoge los parametros χ0 ∈ [0,80, 0,95], λ ∈ N, γ ∈ [0,8, 0,99].

1. Inicializar P, Q; calcular W de acuerdo con (4).

2. Estimar la temperatura inicial c0 usando la tasa de aceptacion inicial χ0.


3. Para t := 0 hasta λ hacer:

a) escoger al azar el modo (I o J) con probabilidad uniforme 1/2

b) hacer Aki→ Ak′ o Bl

j→ Bl′ de la siguiente manera:- escoger al azar i o j (segun el modo escogido);- escoger al azar k′ o l′, diferente de la clase actual de i o j, denotada k o l, dependiendo

del caso;- calcular ∆Z.

c) Aceptar la transferencia si ∆Z < 0, sino aceptarla con probabilidad exp(∆Z/ct).

4. Hacer ct+1 := γct y regresar al paso 1, hasta que ct ≈ 0.

Busqueda Tabu (Castillo & Trejos (2002))

1. Escoger maxnum y sizeneigh, el tamano de los vecindarios N(P, Q).Inicializar e = (P, Q) al azar; calcular W de acuerdo con 4.

2. Empezar la lista tabu con T := Z(P, Q). Sea eopt := e.

3. Repetit maxnum veces:

a) Generar el conjunto N(e) repitiendo sizeneigh veces:

- Escoger al azar el modo con probabilidad uniforme 0,5.- Escoger un objeto i o j uniformemente al azar en I o J con probabilidad 1

n o 1m ,

respectivamente (solo para clases no unitarias).- Escoger al azar una clase de P o Q, diferentes de la clase actual del objeto escogido

antes, conprobabilidad 1K−1 o 1

L−1 respectivamente, y transferir al objeto a la claseescogida.

b) Calcular Z(easp) = mın

Z(P ′, Q′)∣∣∣(P ′, Q′) ∈ N(e)

.

c) Si Z(easp) < Z(eopt) entonces e∗ = easp y eopt = e∗. Sino, sea e∗ tal que t Z(e∗) =

mınZ(P ′, Q′)

∣∣∣(P ′, Q′) ∈ N(e), Z(P ′, Q′) 6∈ T.

d) e := e∗.e) Actualizar T introduciendo el valor Z(e∗) y sacando el valor mas viejo.

En [50] se presentan resultados comparativos entre estos cuatro metodos.

6.2. Clasificacion difusa

La clasificacion difusa trata de relajar la restriccion de que un objeto pertenezca a una sola clase,introduciendo el concepto de funcion de pertenencia, la cual permita que un mismo objeto pertenezca adistintas clases, pero con una medida de pertenencia a cada una de ellas.

Para introducir la clasificacion difusa, haremos primero una presentacion distinta de la clasificacion porparticiones que hemos venido usando. Sea Ω = x1, . . . ,xn el conjunto de objetos a clasificar en K clases.Una particion (clasica o “dura”) P = (C1, . . . , CK) se puede representar por una matriz U = (u)n×K deindicadoras, tal que

1. uik ∈ 0, 1, para todo i ∈ 1, . . . , n y todo k ∈ 1, . . . , K.

2.∑K

k=1 uik = 1, para todo i ∈ 1, . . . , n.

3. 0 <∑n

i=1 uik < n, para todo k ∈ 1, . . . , K.

28 Javier Trejos

El criterio de inercia intra-clases a minimizar se puede escribir como

W (P ) =K∑

k=1

n∑

i=1

uik‖xi − gk‖2

donde gk son los centros de gravedad de las clases, puntos optimos de representacion de una clases segunel teorema de Huygens para este criterio y la distancia Euclıdea clasica.

Una particion difusa estara representada por una matriz de pertenencia U = (u)n×K tal que:

1. uik ∈ [0, 1], para todo i ∈ 1, . . . , n y todo k ∈ 1, . . . , K.

2.∑K

k=1 uik = 1, para todo i ∈ 1, . . . , n.

3. 0 <∑n

i=1 uik < n, para todo k ∈ 1, . . . , K.

Es decir, la pertenencia a una clase es realmente un porcentaje de pertenencia, y un objeto puede pertencera varias clases simultaneamente. El criterio a minimizar es la inercia difusa intra-clases:

W (U , G) =K∑

k=1

n∑

i=1

(uik)m‖xi − gk‖2 (6)

donde G = (g1, . . . , gK) es una matriz de “centros”, cuya forma se dara enseguida.Aquı los xi con alto grado de pertenencia en Ck, tienen una gran influencia sobre gk, lo cual es

fortalecido con m. La funcion de m es reducir la influencia de los xi muy alejados de gk en el calculo delos gk.

Dada U , una condicion necesaria para que W sea mınima es:

gk =∑n

i=1(uik)mxi∑ni=1(uik)m

(7)

y dada G, una condicion necesaria es

uik =

(1

‖xi−gk‖2

)1/(m−1)

∑Kl=1

(1

‖xi−gl‖2

)1/(m−1)(8)

El algoritmo de k-medias difuso propuesto por Bezdek [9] es como sigue:

1. Inicializar U con el metodo de k-medias.

2. Calcular G usando (7).

3. Calcular U usando (8). En el caso de que algun xi coincide con un gk se defin uik = 1 si k = i yuik = 0 si no.

4. Si U entre esta iteracion y la anterior es “muy” similar (de acuerdo con una norma matricial y unumbral ε), entonces detener el algortimo: si no, volver al paso 2.

Usualmente se toma m = 2; los valores grandes de m tienden a bajar los valores de uik.

6.3. Clasificacion neuronal

Una red neuronal es una grafo dirigido donde cada nodo es llamado una neurona, las aristas estanvaluadas y cada neurona realiza operaciones, generalmente una transformacion de los valores de lasneuronas conectadas a ella. Estas redes se han usado para modelar multiples problemas, y han tenidomucho exito en problemas no lineales de discriminacion o regresion a traves de la llamada retropropagaciondel gradiente. Para una introduccion a las redes neuronales, se puede consultar [39]. En clasificacionautomatica, veremos algunos de los modelos propuestos.


6.3.1. Aprendizaje competitivo: algoritmo de Rumelhart

La red propuesta por Rumelhart y Zipser [45] es una red multicapas y al interior de cada capa hayclases que contienen neuronas. Las neuronas de una clase inhiben a las otras neuronas de la misma clase.

uee e

eeuue

-

-

-

Capa de entrada

-

-

-

Capa 2 Capa 3

ee ue ueeue euee eeeu

Figura 8: Red de aprendizaje competitivo.

Los pesos ωji que conectan las neuronas i a la neurona j deben cumplir∑

i ωji = 1 y las entradas delsistema son sucesiones binarias. Si denotamos sik el estado de la neurona i durante la presentacion delejemplo xk (1 si i esta activa, 0 si no), entonces la competencia consiste en encontrar, para cada clase deuna capa, la neurona j que maximiza αjk =

∑i ωjisik . Entonces el nuevo estado de j sera 1 si j gana en

su clase, 0 si no.La ley de aprendizaje es:

ωji(t + 1) =

ωji(t) + η[ sik

nk− ωji(t)] si j gana al presentarse xk,

ωji(t) sino., donde η > 0 y nk =

∑i cik.

Se ve que una neurona aprende traspasando parte del peso de las entradas inactivas a las activas.La neurona pierde una proporcion η de su peso, que es luego distribuida entre los pesos de las entradasactivas.

6.3.2. Algoritmo de Grossberg

Este modelo tambien usa un tipo de aprendizaje competitivo, pero la estructura de la red es distintade las anteriores. Ademas, se usa la inhibicion lateral entre las neuronas. El modelo esta basado en elfuncionamiento del algoritmo MaxNet, que consiste en escoger la neurona que responde mas fuerte a unestımulo. La capa de entrada tiene p neuronas y cada entrada x = (x1, . . . , xp) es un vector binario. Haydos capas escondidas, cada una con m neuronas. La estructura de la red MaxNet es ilustrada en la figura9.

sx1 ccssxi

xp

-

-

-

1

j

m

...

QQ

QQs?6

?6

Entrada 2a capa Capa MaxNet

-

-

-

s1

sj

sm

Salida

∑

i

wjixi -

HHHHjHHHHj

1

xi

wji σj

6

?−ε ujk = −ε

ujj = 1-f sj

Figura 9: Red MaxNet.

Si y es el prototipo (binario) de la clase C, el ejemplo x pertenecera a la clase C∗ que minimizad(x, y∗), donde d es la distancia de Hamming: d(x, y) = p −

∑i xiyi.

Esto se implementa en la red MaxNet al definir la salida de las neuronas de la segunda capa comoσj =

∑i ωjixi. Si ωjk es el peso entre las neuronas j, k de la capa MaxNet, se define ujk = 1 si j = k y

ujk = −ε si j 6= k, donde ε < 1/m.

30 Javier Trejos

Se define entonces la salida de la neurona j como sj = f(σj − ε

∑k 6=j σk

), donde f es una funcion

sigmoide, y se dira que hay convergencia cuando solo un nodo tiene salida distinta de cero. Los vectores-individuos se presentan sucesivamente y reiteradamente hasta que se haya encontrado la clase a la quepertenece cada ejemplo. Esta clase sera la dada por el prototipo mas cercano segun la distancia deHamming.

El algoritmo dado por Grossberg para encontrar una particion esta basado en la utilizacion de lared MaxNet. No daremos los detalles de este algoritmo, solo haremos notar que, ademas de la inhibicionlateral (simbolizada por los pesos ujk) se definen pesos “hacia atras”que van de la capa MaxNet a lacapa de entrada y que permitiran verificar que un ejemplo pertenece a una clase, segun un cierto gradode tolerancia τ . Ademas, τ jugara el papel de parametro para determinar el numero de clases (que no esfijado a priori). El problema con este metodo es que puede haber ejemplos que nunca se clasifiquen, porlo que habrıa que crear clases para ellos solos.

6.3.3. Clasificacion usando el modelo de Hopfield

En el algoritmo de Adorf & Murtagh [1], se dispone de una matriz de distancias o disimilitudes y sequiere minimizar las disimilitudes intraclases: es decir, obtener clases lo mas homogeneas posibles.

Se considera una red de n neuronas, que representan a los individuos a clasificar, totalmente conectada,tal que los estados son binarios y cuyos pesos sinapticos ωji representan las disimilitudes. Las salidas sj

denotan la asignacion de clases de los objetos. Siendo a un vector de dimension n se considera la funcionde energıa H = −1/2

∑j,i ωjisjsi −

∑k skak que es minimizada usando el sobrecalentamiento simulado.

Si f es una funcion sigmoide, se hace sj = f(∑

i ωjisi + aj). Al principio del algoritmo se puede forzar elprimer ejemplo a pertenecer a la primera clase, si se toma a = (a1, 0, . . . , 0)T , con a1 muy grande respectoa las disimilitudes.

6.3.4. Clasificacion usando el modelo de Kohonen

Similar al modelo anterior, este modelo [33] consiste en escoger la neurona que tenga la respuesta masfuerte, ante la presencia de un estımulo. Dados los xi que forman el vector x, se procede como sigue:1) encontrar c tal que ‖x − ωc‖ = mınj=1,...,n ‖x − ωj‖ donde ωj = (ωj1, . . . , ωjn)T son los pesos de lasneuronas que se conectan hacia la neurona j;

2) segun el vecindario Vc alrededor de c, calcular:

si j ∈ Vc ⇒ sj = 1si j 6∈ Vc ⇒ sj = 0

3) actualizar los pesos: ωji(t + 1) = ωji(t) + k(t)[xi − ωji(t)],donde k(t) 6= 0 si i ∈ Vc y k(t) = 0 si i 6∈ Vc.

El vecindario Vc es un conjunto de neuronas “cercanas” a c, segun alguna medida de proximidadestablecida; este radio ira disminuyendo conforme avancen las iteraciones.

6.4. Clasificacion probabilıstica

Varios autores han estudiado el marco general probabilıstico de la clasificacion, considerando variablesaleatorias cualesquiera definidas sobre muestras de una poblacion. Los datos pueden ser vectores aleatoriosX1, . . . , Xn ∈ Rp o disimilitudes aleatorias (Dij). Por ejemplo, se puede tomar Xi ∼ Np(µk , σ2Ip) parai ∈ Ck.

H.-H. Bock [10] propone una serie de modelos, entre los que destaca el modelo de particion fija deltipo nubes dinamicas, con parametros o nucleos a estimar, en el espacio continuo (caso del metodo de lask-medias). TAmbien se proponen metodos en los se estiman hiperplanos de separacion, con estimaciontipo proyeccion ‘pursuit’, clasificacion tipo regresion logıstica para parejas de datos binarios y explica-tivos, metodos log-lineales para clasificacion de maxima verosimilitud en la descomposicion de tablas decontingencia, modelos de mezclas de probabilidad y clasificacion difusa.


7. Validacion de Resultados

7.1. Descripcion de una particion

Si se aplica un metodo de particionamiento que minimice la inercia intra-clases W o que maximice lainercia inter-clases B, se puede usar una serie de ındices que describir la particion obtenida y ası juzgarsobre la calidad de la misma e interpretar los resultados a la luz de los datos originales.

7.1.1. Indice global

Para medir la calidad global de la particion P , se usa el cociente R(P ) = B(P )/I , donde I es lainercia total y B la inercia inter-clases. Entonces, si R es cercano a 1 se dira que la clasificacion es buenay si R es cercano a 0, se dira que es mala. Este ındice permite comparar dos clasificaciones de Ω en unmismo numero de clases.

7.1.2. Contribucion global de cada variable

La contribucion de una variable xj a la particion P sera dada por el ındice cor(j) = varxj1,...,xj

Kvar(xj)

donde xjk es el valor promedio de xj en la clase Ck. Este ındice corresponde al cociente de correlacion

η que mide la asociacion entre xj y la variable cualitativa que describe a la particion; ademas mide elpoder discriminante de xj : si cor(j) > R entonces la variable j contribuye mas que el promedio de lasotras variables a la inercia.

7.1.3. Descripcion de las clases

Para cada clase Ck, se compara la variacion de las p variables dentro de la clase respecto a la variacionglobal, esto es con:

Bk =varx1

k, . . . , xpk

By Wk =

p∑

j=1

∑

xi∈Ck

1n

(xij − xjk)2

donde xij es el valor de la variable j sobre el objeto i .Bk mide la posicion de Ck respecto a g, si Bk es grande es porque Ck es una clase mas excentrica que

las demas. Por su parte, Wk mide la concentracion de Ck, ası si Wk es pequeno es porque Ck esta bastanteconcentrado. Estas medidas Bk y Wk se pueden ver como las contribuciones de la clase Ck a B y W ,respectivamente, en el caso en que la metrica M sea una matriz diagonal.

7.1.4. Descripcion de las clases por variable

Para medir la capacidad de la variable xj para describir a la clase Ck, se usa el ındice

cor(j, k) =µk(xj

k − xj)2

var(xj)

que compara la variacion de xj sobre la clase respecto a la variacion total. Ası, si cor(j, k) es grande esporque xj es homogenea sobre Ck.

7.2. Numero de clases

No existe un criterio uniforme para determinar el numero de clases en particionamiento ni para elcorte de un arbol jerarquico. Sin embargo, es comun usar el metodo del codo en ambos casos. En unmetodo jerarquico, este consiste consiste en la graficacion del nivel del arbol versus el numero de clases,y se sugiere cortar el arbol cuando hay una estabilizacion de los valores. Si wn−1, . . . , w2 son las inercias(caso del criterio de Ward) de cada nivel de la jerarquıa y si ∆wk = wk − wk−1 el cambio de inercia del

32 Javier Trejos

nivel hk−1 al nivel hk, entonces el metodo del codo sugiere tomar el nivel k∗ que maximiza ∆wk/∆wk−1,para k ∈ 2, . . . , n − 1. Hay autores que sugieren tomar simplemente el k que maximiza ∆wk, pero sinmayor formalismo.

Jambu [29] propone elegir el nivel k∗ tal que∑k∗

k=1wk

I ≥ γ, donde I es la inercia total de la tablade datos y γ es un valor fijo, que representa un porcentaje de varianza acumulada a partir del nivel masalto. Mojena propone seleccionar el primer nivel k del arbol tal que wk > w + tσw, donde w y σw es elpromedio y la desviacion estandar de w1, . . . , wn−1; Mojena sugiere tomar t entre 2.75 y 3.5, mientrasque Miligan & Cooper proponen t = 1,25.

En el caso de particionamiento, tambien se hace un grafico para varias corridas del metodo tomandosela mejor solucion, y se grafica este valor versus el numero de clases, aplicando un criterio del codo. Ahorabien, en los metodos de particionamiento, por obtener optimos locales del criterio, se suele hacer muchascorridas del metodo antes de escoger la mejor solucon. Incluso, se puede estudiar la independencia deesas corridas de la particion inicial (por ejemplo, estudio de las formas fuertes [19]).

Hartigan [27] propone el siguiente test, bajo la hipotesis de normalidad, para determinar el numerode clases:

F (K) = (n − K − 1)W (P ∗

K)W (P ∗

K+1)∼ Fisher(1, n − K − 1)

donde la hipotesis nula es que se tienen K clases.En el caso de la clasificacion difusa, se estudia el grado de difusidad de una particion, por ejemplo

con el ındice N(F”) = KF”−1K−1 , donde 2F” =

∑ni=1

uxi

n + mınxiuxi, y uxi = maxui1, ui2, . . . , uiK.Si las clases (C1, . . . , CK) estan muy separadas entonces uxi ≈ 1, con lo que F” ≈ 1 y entonces

N(F”) ≈ 1. El peor caso es si max uik ≈ 1K ya que se tendrıa F” ≈ 1

K y N(F”) ≈ 0. El mınxi uxi

evidencia el grado de traslape o separacion entre las clases.

7.3. Pruebas de hipotesis

Existen diversas pruebas de hipotesis para determinar cuales son las variables significativas para unaparticion P = (C1, . . . , CK) dada en K clases.

Caso continuo Se compara Xk la media de una variable X en la clase Ck con la media general X y semide la desviacion teniendo en cuenta la varianza S2

k(X) de esta variable en la clase. El valor testes la cantidad

tk(X) =X − X

sk(X)con s2

k(X) =n − nk

n − 1s2(X)

nk

donde s(X) es la desviacion estandar empırica de X . Bajop la hipotesis nula de un tiraje al azarsin reposicion de los nk individuos de la clase Ck, la variable Xk tiene media X y varianza teoricas2

k(X). Se ve que tk(X) ∼ N (0, 1) y que este test se puede hacer solo para una variable que no hayaparticipado en el analisis (es decir, una variable suplementaria), para satisfacer la independenciaentre la variable y la particion P . Entre mayor sea el valor test (menor es la probabilidad), masdiscutible es la hipotesis de que los n valores de X sean extraıdos al azar entre los valores posibles.Ahora bien, los valores test siempre se pueden usar sobre las variables activas para ordenarlas conrespecto a la caracterizacon de cada clase.

Caso discreto Se compara las proporciones nkj

nk(el numero de individuos que tienen la modalidad j

entre los individuos de la clase Ck, sobre el total de individuos de Ck) con nj

n (el numero deelementos que poseen la modalidad j entre el total de individuos). La hipotesis nula serıa que los nk

individuos de la clase Ck son extraıdos al azar sin reposicion entre la poblacion de los n individuos,por lo que deberıa tenerse nkj/nk ≈ nj/n. El numero N de objetos de Ck que tienen la modalidadj es una variable aleatoria que sigue una ley hipergeometrica con parametros (nj , nk, n). Se calculaentonces la probabilidad pk(j) = Prob(N ≥ nkj), entre menor sea pk(j), mas difıcil de aceptar es lahipotesis de un tiraje al azar. Se usa esta probabilidad para ordenar las modalidades caracterısticasde una clase (la mas caracterıstica es aquella que tiene menor probabilidad).


Referencias

[1] Adorf F., Murtagh F. (1988) “Clustering based on neural network processing”, en: Compstat’88, IASC,Physica–Verlag, Heidelberg.

[2] Anderberg, M.R. (1973) Cluster Analysis for Applications. Academic Press, New York.

[3] Batbedat, A. (1990) Les Approches Pyramidales dans la Classification Aroboree. Masson, Paris.

[4] Barthelemy, J.P.; Guenoche, A. (1988) Les Arbres et la Representation des Proximites. Masson, Parıs.

[5] Benzecri, J.-P. (1965) Problemes et methodes de la taxinomie. Cours ISUP, Paris – Rennes.

[6] Benzecri, J.-P. y colaboradores (1982) L’Analyse des Donnees. Tomo I: La Taxinomie, Tomo II: Correspon-dances. 4a. edicion. Dunod, Parıs.

[7] Benzecri, J.P. (1985) “Demonstration de l’equivalence des resultats des algorithmes acceleres a ceux del’algorithme de base en CAH”, Les Cahiers de l’Analyse de Donnees, Vol. X, No.3

[8] Bertrand, P.; Diday, E. (1990) “Une generalisation des arbres hierarchiques: les representations pyramidales”,Revue de Statistique Appliquee XXXVIII (3): 53–78.

[9] Bezdek, J.C. (1981) Pattern Recognition with Fuzzy Objetive Function Algorithms. New York, London.

[10] Bock, H.-H. (1974) Automatische Klassifikation. Vandenhoeck & Ruprecht, Gottingen.

[11] Brossier, G. (1986) Problemes de Representation par des Arbres. These de Doctorat, Universite de HauteBretagne.

[12] Cailliez, F.; Pages, J.P. (1976) Introduction a l’Analyse des Donnees. SMASH, Parıs.

[13] Castillo, W. (1989) “Metodos y resultados en clasificacion automatica”, Revista de Ciencia y Tecnologıa,XIII (1–2): 105–116.

[14] Castillo, W.; Trejos, J. (2002) “Two-mode partitioning: review of methods and application of tabu search”,in Classification, Clustering, and Data Analysis, K. Jajuga et al. (eds.), Springer, Berlin: 43–51.

[15] Celeux G., Diday E., Govaert G., Lechevallier Y., Ralambondrainy H.(1989) Classification Automatique desDonnees: Environnement Informatique et Statistique. Dunod, Parıs.

[16] Chandon, J.L.; Pinson, S. (1981) Analyse Typologique: Theorie et Applications. Masson, Parıs.

[17] Diday, E.(1972) “Optimisation en classification automatique et reconnaissance des formes”, Note ScientifiqueIRIA No. 6.

[18] Diday, E. et coll. (1980) Optimisation en Classification Automatique. INRIA, Le Chesnay.

[19] Diday, E.; Lemaire, J.; Pouget, J.; Testu, F. (1982) Elements d’Analyse des Donnees. Dunod, Parıs.

[20] Diday, E. (1986) “Une representation visuelle des classes empietantes: les pyramides”, R.A.I.R.O.–APII20(5): 475–526.

[21] Dubes, R.; Jain, A.K. (1980) “Clustering methodologies in exploratory data analysis”, Advances in Comput-ers, Vol. 19, pp. 113–228.

[22] Everitt, B.S. (1993) Cluster Analysis. 3a edicion. Edward Arnold, London.

[23] Fisher, W.D. (1958) “On grouping for maximum homogeneity”, J. Amer. Stat. Assoc. 53.

[24] Forgy, E.W. (1965) “Cluster analysis of multivariate data: efficiency versus interpretability of classifications”,Biometrics 21.

[25] Govaert, G. (1975) Classification automatique et distances adaptatives. These de Doctorat de 3eme cycle,Universtie Paris VI.

34 Javier Trejos

[26] Govaert, G. (1983) Classification Croisee. These de Doctorat es Sciences, Universite Paris VI.

[27] Hartigan (1974) Clustering Algorithms. John Wiley & Sons, Nueva York.

[28] Jambu M. (1978) Classification Automatique pour l’Analyse des Donnees. Tomo 1. Dunod, Parıs.

[29] Jambu M. (1989) Exploration Informatique et Statistique des Donnees. Dunod, Parıs.

[30] Jardine, N.; Sibson, R. (1971) Mathematical Taxonomy. John Wiley & Sons, New York.

[31] Johnson, S.C. (1967) “Hierarchical clustering schemes”, Psychometrika 32(3).

[32] Kauffman, A.; Roosseeuw, P. (1990) Finding Groups in Data: An Introduction to Cluster Analysis. JohnWiley & Sons, New York.

[33] Kohonen, T. (1984) Self-Organization and Associative Memory. (2a edicion), Springer–Verlag, Berlin.

[34] Lance, G.N.; Williams, W.T. (1967) “A general theory of classification sorting strategies. I. Hierarchicalsystems”, Computer Journal 9(4); “II. Clustering systems”, Computer Journal 10(3).

[35] Lerman, I.C. (1981) Classification et Analyse Ordinale des Donnees. Dunod, Parıs.

[36] Libert, G.; Roubens, M. (1983) “New experimental results in cluster validity of fuzzy clustering algorithms”,in New Trends in Data Analysis and Applications, J. Janssen, J.-F. Marcotorchino, J.-M. Proth (eds.),Elsevier Science Publ. B. V. (North–Holland), Amsterdam, 205–217.

[37] McQueen, J.B. (1967) “Some methods for classification and analysis of multivariate observations”, Proc. 5thBerkeley Symposium on Math. Statistics and Probability, Vol. 1.

[38] Os, B.J. van (2000) Dynamic Programming for Partitioning in Multivariate Data Analysis. Universal Press,Leiden University.

[39] Pao, Y.H. (1989) Adaptive Pattern Recognition and Neural Nets. Addison-Wesley, Reading, Mass.

[40] Piza E. (1988) “Clasificacion automatica jerarquica aglomerativa” Revista de Ciencias Economicas, VII(1):95–111.

[41] Regnier, S. (1965) “Sur quelques aspects mathematiques des problemes de classification automatique”, ICCBulletin 4 & Math. Sci. Hum 82 (1983).

[42] Rizzi, A. (1982) Analisi dei Gruppi. La Goliardica, Roma.

[43] Roux M. (1985) Algorithmes de Classification. Masson, Parıs.

[44] Roux, M. (1985) “Representation d’une distance par un arbre aux aretes aditives”, Journees d’Analyse desDonnees et Informatique, INRIA, Versailles.

[45] Rumelhart, D. E.; McClelland, J. L., editores (1986) Parallel distributed processing. Vol. 1: Foundations. Vol.2: Exploration in the microstructure of cognition. The MIT Press, Cambridge, Massachussets.

[46] Schektman, Y. (1978) Estadıstica descriptiva (analisis lineal de datos multidimensionales, I parte. En: Memo-rias I Simposio Metodos Matematicos Aplicados a las Ciencias, J. Badia, Y. Schektman y J. Poltronieri (eds.),Universidad de Costa Rica, San Pedro: 9–67.

[47] Sokal, R.R.; Sneath, P.H. (1963) Principles of Numerical Taxonomy. W. H. Freeman & Co., San Francisco.

[48] Trejos, J. (2003) Clasificacion Automatica: Metodos para el Analisis de Grupos. Notas de curso, Universidadde Costa Rica, San Jose.

[49] Trejos, J. (1995) “Presentacion de las redes neuronales: aplicaciones al analisis de datos”, en Memorias VIIy VIII Simposio Metodos Matematicos Aplicados a las Ciencias, W. Castillo y J. Trejos (eds.), Editorial dela Universidad de Costa Rica, San Pedro, pp.: 117–148.

[50] Trejos, J. (2003) “Metodos modernos de optimizacion en clasificacion por particiones”, XVIII Foro Nacionalde Estadıstica, Asociacion Mexicana de Estadıstica.

modelos de clasificación

Education