Reconocimiento de Patrones

J. Kittler (revisado y ampliado por GTI-IIE)

Revisi o n:0.9, Fecha: 1/09/2002

Notas del seminario de Reconocimiento de Patrones de Grupo de Tratamiento de Im agenes

del

Instituto de Ingeniera Electrica,

basado en las notas del curso del Prof. J. Kittler en la Univ. de
Surrey.

Indice
1. Modelo de Sistema de Reconocimiento de Patrones

1.1. Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2. Modelo de Sistema de Reconocimiento de Patrones . . . . . . . . . . . . . . . . . . . . . .

1.3. Modelo del Proceso de Generacio n de Patrones . . . . . . . . . . . . . . . . . . . . . . . .

1.3.1. Modelo Probabilstico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3.2. Relaciones Basicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3.3. Ejemplo: Un problema de reconocimiento de caracteres . . . . . . . . . . . . . . .

1.4. Reglas de Decision Estadstica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4.1. Regla del Mnimo Costo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4.2. Regla del Mnimo Error . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

de un Sistema de Reconocimiento de Patrones

2. Diseno

2.1. Problemas en el Diseno de un Sistema de Reconocimiento de Patrones . . . . . . . . . . . .

2.2. Reglas de Decision para Clases con Distribucio n Normal (Gaussiana) . . . . . . . . . . . .

2.2.1. Caso Particular 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.2. Caso Particular 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.3. Caso Particular 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2.4. Inferencia de los parametros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3. Evaluacion del Desempeno de un Sistema de Clasificacio n . . . . . . . . . . . . . . . . . .

3. Apendizaje no supervisado

3.1. Aprendizaje no supervisado y analisis de agrupamientos . . . . . . . . . . . . . . . . . . .

3.2. Medidas de Similitud y Criterios de Agrupamiento . . . . . . . . . . . . . . . . . . . . . .

10

3.3. Algoritmo de k-medias (k-means). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

1. Modelo de Sistema de Reconocimiento de Patrones

1. Modelo de Sistema de Reconocimiento de Patrones

1.1. Introduccion
El objetivo del procesamiento e interpretaci o n de datos sensoriales es lograr una descripci o n concisa y representativa del universo observado. La informaci o n de interes incluye nombres, caractersticas detalladas, relacionamientos, modos de comportamiento, etc. que involucran a los elementos del universo (objetos, fen o menos, conceptos)
Estos elementos se perciben como patrones y los procesos que llevan a su comprensi o n son llamados procesos
perceptuales. El etiquetado (clasificacio n, asignacion de nombres) de esos elementos es lo que se conoce
como reconocimiento de patrones. Por lo tanto, el reconocimiento de patrones es una herramienta esencial
para la interpretacion automatica de datos sensoriales.
El sistema nervioso humano recibe aproximadamente 10 9 bits de datos sensoriales por segundo y la mayora
de esta informacion es adquirida y procesada por el sistema visual. Analogamente, la mayora de los datos a
ser procesados automaticamente aparecen en forma de imagenes.
El procesamiento de imagenes de escenas complejas es un proceso en mu ltiples niveles que se ilustra en la
figura 1 mostrando la participacio n relativa de los dos tipos de metodologas necesarias:
Reconocimiento de patrones basado en atributos.
Reconocimiento de patrones basado en la estructura.

Pixel

Segmentos

Primitivas
de Objetos

Objetos

Grupos
de Objetos

Escena

Informacin Relacional
Informacin de Atributos

Figura 1: Distintos tipos de informacio n usada en diferentes niveles de procesamiento.

1.2. Modelo de Sistema de Reconocimiento de Patrones

Los procesos perceptuales del ser humano pueden ser modelados como un sistema de tres estados:
adquisicion de datos sensoriales
extraccion de caractersticas
toma de decisiones


INDICE

Universo
(Objetos, Conceptos)

Sensor

Extractor
Decisin
Caractersticas
Clasificador
de
Representacin Caractersticas
Patrn

Figura 2: Etapas en un sistema de reconocimiento de patrones.

Por lo tanto es conveniente dividir el problema del reconocimiento autom a tico de una manera similar
Sensor Su proposito es proporcionar una representacio n feasible de los elementos del universo a ser clasificados. Es un sub-sistema crucial ya que determina los lmites en el rendimiento de todo el sistema.
Idealmente uno debera entender completamente las propiedades fsicas que distinguen a los elementos
en las diferentes clases y usar ese conocimiento para dise n ar el sensor, de manera que esas propiedades
pudieran ser medidas directamente. En la practica frecuentemente esto es imposible porque:
no se dispone de ese conocimiento
muchas propiedades u tiles no se pueden medir directamente (medici o n no intrusiva)
no es economicamente viable
Extraccion de Caractersticas Esta etapa se encarga, a partir del patr o n de representacion, de extraer la
informacion discriminatoria eliminando la informaci o n redundante e irrelevante. Su principal prop o sito
es reducir la dimensionalidad del problema de reconocimiento de patrones.
Clasificador El la etapa de toma de decisiones en el sistema. Su rol es asignar a la categora apropiada los
patrones de clase desconocida a priori.

1.3. Modelo del Proceso de Generacion de Patrones

1.3.1. Modelo Probabilstico
Las diferencias en los patrones de una misma clase puede deberse a ruido, deformaciones, variabilidad
biologica, etc. Por lo tanto debemos asumir esta variabilidad en los patrones y el proceso asociado a la
generacion de patrones puede ser descripto adecuadamente mediante un modelo probabilstico.
De lo anterior podemos asumir que cada patro n
x = [x1 , x2 , , xn ]
es un vector aleatorio n-dimensional perteneciente a una de m posibles clases i i = 1, , m donde cada
clase i tiene una probabilidad de ocurrencia a priori igual a P ( i ). La distribucion de probabilidad del
vector patron x de la clase i se caracteriza por la funcio n densidad de probabilidad condicional para la
i-esima clase p(x|i ).
1.3.2. Relaciones Basicas
Notar que las probabilidades a priori de las clases suman uno, o sea
m
!

P (i ) = 1

i=1

La densidad conjunta o funcio n de densidad de probabilidad no condicional p(x) vienen dada por
p(x) =

m
!
i=1

p(x|i )P (i ).

1. Modelo de Sistema de Reconocimiento de Patrones

En la practica nos interesa calcular la probabilidad a posteriori (una vez observado el patr o n x) para cada
clase i , la cual viene dada por la Fo rmula de Bayes que relaciona probabilidades condicionales seg u n:
P (i |x) =

p(x|i )P (i )
p(x|i )P (i )
= "m
.
p(x)
j=1 p(x|j )P (j )

1.3.3. Ejemplo: Un problema de reconocimiento de caracteres

m = 26
n=8

numero de diferentes caracteres excluyendo los dgitos.

numero de medidas

xi i = 1 n distancia entre el centro de gravedad y el punto de intersecci o n mas lejano en la

semirrecta con origen en este centro y formando un a ngulo (i1)

con el eje 0x.
4
P (i )

probabilidad a priori de la ocurrencia del i-esimo caracter en un lenguaje dado.

x3
x2
x1

Figura 3: Atributos en reconocimiento de caracteres.

1.4. Reglas de Decision Estadstica

1.4.1. Regla del Mnimo Costo
Dadas las caractersticas del modelo probabilstico adoptado para el proceso de generaci o n de patrones; como
decidimos a que clase asignar el patro n x observado?
Para resolver este problema, definamos un costo de decisi o n ij 1 i, j n asociado con la decisio n de
asignar a la clase j un patron x que pertenece a la clase i .
Notar que
ii

ij

costo de una decision correcta, en general se define como 0

es en general diferente de ji

ij 0
Ejemplo: Verificacion de Firmas
En una aplicacion de deteccion de firmas falsas tendramos en principio dos clases
#
1 la firma es autentica
2 la firma ha sido falsificada

Claramente en este contexto podemos cometer 2 tipos de errores de clasificaci o n que sin embargo implican
costos muy diferentes; de modo que se debera cumplir 21 12 .


INDICE

Denotaremos con j la region del espacio de observacio n tal que nuestra regla de decisio n asigna
x j

x j
o sea que la region j esta asociada con la clase j .

El costo medio de clasificar un patro n x j como perteneciente a la clase j es

rj (x) =

m
!

ij P (i |x)

i=1

Por lo tanto el costo para toda la regio n j se obtiene integrando sobre todos los valores posibles con sus
correspondientes probabilidades de observaci o n:
$
Rj =
rj (x)p(x)dx
j

Finalmente el costo total de nuestro sistema de decisi o n viene dado por

%m
&
m $
m
!
!
!
Rj =
ij P (i |x) p(x)dx
R=
j=1

j=1

i=1

De modo que podemos concluir que el costo total sera minimizado si el espacio de observacio n se particiona
de manera tal que si x j se tenga
m
!
i=1

ij P (i |x)

m
!

ik P (i |x) k = j

i=1

Hemos llegado por lo tanto a la llamada Regla de Decisi o n de Mnimo Costo de Bayes, que establece
Asignar x j

m
!

ij p(x|i )P (i ) = mn

1km

i=1

m
!

ik p(x|i )P (i )

i=1

donde en en la u ltima ecuacion hemos usado la identidad de Bayes: P (i |x)p(x) = p(x|i )P (i ).

1.4.2. Regla del Mnimo Error
Consideramos ahora un modelo de costos cero-uno, o sea
#
ii = 0 1 i m

ij = 1 1 i, j m, i = j

En este caso el lado derecho de la regla del mnimo costo queda

m
!
i=1

ik P (i |x) =

P (i |x) = 1 P (k |x)

1im
i=k

y la regla de decision correspondiente resulta:

Asignar x j

P (j |x) = m
ax P (k |x)
1km

Observar que si asumimos que se asigna x j , la probabilidad condicional de error (x) viene dada por
(x) = 1 P (j |x) .

 de un Sistema de Reconocimiento de Patrones

2. Diseno

Por lo tanto el error condicional sera mnimo si la clase j se elije usando la u ltima regla de decision. En este
caso el error medio
$
e=
(x)p(x)dx

se conoce como error de Bayes.

Integrando en cada region de decision este error se puede descomponer como

m '$
m
'$
(
(
!
!
P (j )
p(x|j )dx .
e=1
P (j |x)p(x)dx = 1
j=1

j=1

de un Sistema de Reconocimiento de Patrones

2. Diseno
de un Sistema de Reconocimiento de Patrones
2.1. Problemas en el Diseno
Si conocieramos totalmente las caractersticas estadsticas del modelo en el proceso de generaci o n de los
patrones, esto es si supieramos P (i ), p(x|i ) i; entonces podramos disenar el sistema de reconocimiento
de patrones (SRP) o ptimo mediante aplicacio n directa de la teora de decision de Bayes. Sin embargo en la
practica surgen los siguientes problemas:
el modelo no se puede conocer totalmente y/o
la complejidad del SRP a disen ar esta restringida por consideraciones econo micas (hardware, tiempo)
Por lo general la base de conocimiento disponible para el dise n o de un SRP es un conjunto de entrenamiento
constituido por observaciones, ya sea etiquetadas o no.
En el primer caso asumimos que para cada patro n o vector de observaciones xi i = 1, 2, , N en el
conjunto de entrenamiento, un experto asigna una etiqueta con la clase correcta i . El diseno de un sistema
basado en un conjunto de datos clasificados de antemano se conoce como aprendizaje supervisado.
Si no se dispone de conocimiento experto sobre el conjunto de datos, o si el etiquetado de los patrones de
entrenamiento es impracticable por razones practicas; entonces el problema de disen o implica la necesidad
de una primera etapa de analisis de los datos. Este proceso primario de analisis se conoce como una etapa de
aprendizaje no supervisado.
Por lo tanto, en el caso general, dado un conjunto de entrenamientos el dise n o del SRP implica:
1. Inferencia del modelo a partir de los datos (aprendizaje).
2. Desarrollo de reglas de decisio n practicas.
3. Simulacion y evaluacion del rendimiento del sistema.

2.2. Reglas de Decision para Clases con Distribucion Normal (Gaussiana)

Supongamos que las clases responden a distribuciones normales, o sea que las densidades de probabilidad
condicionales de cada clase tienen la forma
*
) 1
1
1
(x i )T
i = 1, , m .
p(x|i ) =
1 exp (x i )i
n
2
(2) 2 |i | 2
siendo
#
i = E [x|i ]

i = Cov[x|i ] = E (x i )(x i ) |i ]
T

vector medio para la i-esima clase

matriz de covarianza para la i-esima clase


INDICE

Si tomamos logaritmo a ambos lados de la regla de Bayes del mnimo error obtenemos:
Asignar x j

*
1)
T
n log(2) + log |j | + (x j )1
=
j (x j )
-2
.
*
1)
1
T
m
ax log P (k )
(1)
n log(2) + log |k | + (x k )k (x k )
1km
2

log P (j )

Multiplicando por 2, sacando para afuera de la expresi o n el signo de menos y agrupando los terminos que no
dependen de x resulta:
Asignar x j

T
(x j )1
n
j (x j ) Cj = m

1km

siendo

T
(x k )1
k (x k ) Ck

Ck = 2 log P (k ) (n log(2) + log |k |)

Observar que en el caso particular en que las probabilidades a priori son uniformes y las matrices de correlacion tienen determinante constante en las distintas clase, de modo que
P (k ) =

1
1 k m y
m

log |k | = log |k | 1 k = k m

la regla de Bayes del mnimo error se simplifica a:

Asignar x j

T
(x j )1
n
j (x j ) = m

1km

+
,
T
(x k )1
k (x k )

Si definimos para cada clase una norma a partir de su matriz de covarianza como sigue
2

T
x xk = x1
k x

1km

podemos escribir el criterio anterior como:

Asignar x j

x j j = mn x k k
1km

De modo que asignamos un patro n x arbitrario a la clase j tal que su vector medio j este mas cercano en
la distancia inducida por la norma asociada a esa clase.
2.2.1. Caso Particular 1
Supongamos que las probabilidades a priori y las covarianzas son constantes en las clases
i = j = y

P (i ) = P (j ) 1 i = j m

Definimos la norma y distancias asociadas a como antes:

2

x = x1 xT

d(x, x ) = x x

x, x

Esta distancia se conoce como distancia de Mahalanobis asociada a la covarianza . Notar que en el caso
particular que = I esta distancia coincide con la distancia cuadratica Euclidiana.
Por lo tanto la regla del mnimo error se reduce a asignar el patro n x a la clase cuyo vector medio sea el mas
cercano segun la distancia de Mahalanobis (Regla de decisi o n por media mas cercana):
Asignar x j

d(x, j ) = mn d(x k )
1km

 de un Sistema de Reconocimiento de Patrones

2. Diseno

d( x , 2 )
x

d( x , 1 )

d( x , 3 )

3
Figura 4: Regla de asignacio n por media mas cercana.
2.2.2. Caso Particular 2
Ahora analizaremos el problema general de decisi o n entre dos clases

m = 2,

1 = 2

Aplicando la regla de Bayes vemos que la ecuaci o n

f (x) = x 1 1 x 2 2 + C2 C1 = 0
define la superficie de separacio n, conocida como superficie discriminante, entre las regiones asociadas a
cada una de las clases 1 y 2 . En general esta superficie es cuadratica ya que su ecuacion resulta:
)
*
*
)
* ) T 1
1
1
T 1
xT 1
x 2xT 1
1 2
1 1 2 2 + 1 1 1 2 2 2 + C2 C1 = 0 .
/
01
2 /
01
2 /
01
2
constante

lineal

cuadratico

2.2.3. Caso Particular 3

En este caso asumimos que tenemos 2 clases con la misma covarianza

m = 2,

1 = 2 =

Observando la ecuacion para el caso anterior, vemos que se anula el termino cuadratico y por lo tanto la
superficie discriminante resulta lineal como funci o n del patron vectorial x. La superficie de separacio n es un
hiperplano definido por:
)
*
xT 1 2 + cte = xT w + cte = 0

)
*
siendo w = 1 2 .

El resultado es un clasificador lineal se puede implementar como se muestra en la figura 5.

Esta estructura es identica a la de una importante familia de maquinas lineales usadas en sistemas de decisi o n,
entre las cuales podemos mencionar al Perceptr o n.
2.2.4. Inferencia de los parametros
La inferencia de los parametros i y i involucrados en las reglas de decisio n es directa a partir de los
conjuntos de entrenamiento
{xij

i = 1, , m; j = 1, , Ni } con xij i .


INDICE

xTw + cte = 0
2

Figura 5: Regla de asignacio n por media mas cercana.

El patron vectorial medio para la clase i se puede estimar como
i =

Ni
1 !
xij
Ni j=1

en tanto la matriz de covarianza se estima con

Ni
!
*T
)
*)
i = 1
i
i xij

xij
Ni j=1

de un Sistema de Clasificacion
2.3. Evaluacion del Desempeno
Supongamos que disponemos de un conjunto de patrones vectoriales x j j = 1, , N con sus correspondientes clases verdaderas j conocidas. Es importante notar que este conjunto de patrones debera tener
independencia estadstica con el conjuntos de patrones de entrenamiento del sistema.
Sean j las etiquetas asignadas a cada xj por el sistema de reconocimiento de patrones que estamos evaluando, e introduzcamos las variables aleatorias (x j ) definidas segun
#
0
si j = j
(xj ) =
1
si j = j
Notar que el valor esperado de (x) para un patr o n x elegido al azar es
$
$
E [] =
(1 (x) + 0 [1 (x)]) p(x)dx =
(x)p(x)dx = e

en tanto la varianza resulta

+
,
E ( e)2 =

(x)p(x)dx e2 = e(1 e) .

Podemos tambien deducir esto observando es una variable aleatoria de Bernoulli tal que la probabilidad
p{ = 1} es igual a la probabilidad media e de error del sistema.
Si hacemos N observaciones independientes de y definimos la nueva variable aleatoria e como
e =

N
1 !
j
N j=1

3. Apendizaje no supervisado

encontramos que e tiene distribucio n Binomial con valor medio e (como se ve calculando la esperanza) y por
lo tanto e es un estimador insesgado del error medio e.
La desviacion estandar de este estimador se calcula como
3
) + ,
*1
e] = E e2 e2 2
e = Var [
Sustituyendo e y desarrollando resulta
Var [
e] =

N N
1 + 2, N 1 2
1
1 !!
E +
e e2 =
e(1 e)
E [j k ] e2 =
N 2 j=1
N
N
N
k=1

de donde la desviacion del estimador sera

e =

e(1 e)
1
.
N
2 N

Resumiendo, hemos visto que podemos estimar el error medio de clasificaci o n e presentandole a nuestro sistema de clasificacion un conjunto de patrones que pertenecen a clases conocidas. El error se estima contando
el numero de discrepancias entre la clase verdadera y la etiqueta de clase asignada por el sistema, y dividiendo
finalmente este resultado entre el nu mero de muestras en la prueba.
Notar que si el error medio del sistema es peque n o, digamos de 1 %, vamos a necesitar de un nu mero
grande de muestras de prueba para verificar este valor de desempe n o con una razonable confianza relativa.

3. Apendizaje no supervisado
Es comun encontrarse con situaciones en las que el sistema de clasificaci o n de patrones debe disenarse partiendo de un conjunto de patrones de entrenamiento {x j ; j = 1, 2, , N } para los cuales no conocemos
sus etiquetas de clase i
Estas situaciones se presentan cuando no disponemos del conocimiento de un experto o bien cuando el etiquetado de cada muestra individual es impracticable. Esto u ltimo ocurre por ejemplo en el caso de aplicaciones
con sensores remotos, como ser imagenes satelitales de terrenos donde sera muy costoso o imposible recoger
informacion real del tipo de suelo sensado en cada punto de las imagenes. En estos casos el proceso de disen o
requiere una primera etapa de analisis de las estructuras presentes en los datos de entrenamiento.

3.1. Aprendizaje no supervisado y analisis de agrupamientos

Dado un conjunto de entrenamiento suficientemente grande podemos inferir la funci o n densidad de probabilidad conjunta p(x) y recordando que
p(x) =

m
!

P (i )p(x|i )

i=1

podemos deducir que si la densidad conjunta es multimodal cada uno de los modos debera corresponderse
con la distribucion condicional de cada una de las clases presentes. Por lo tanto identificando estos modos en
p(x) sera en principio posible particionar el espacio de observaci o n en regiones disjuntas i , i = 1, , m
asociadas con cada una de las clases presentes.
Si las distribuciones condicionales de cada clase son normales cabria la posibilidad de recuperar los par a metros de cada distribucion a partir del conjunto de entrenamiento. A partir de esto podramos seguir con el
diseno del clasificador como se vio en la seccio n anterior. Sin embargo podemos conformarnos con recobrar


INDICE

10

p(x)

Figura 6: Distribucion conjunta multimodal y regiones asociadas a cada clase..

directamente las regiones i lo cual es suficiente para nuestros intereses ya que esto puede usarse directamente para la clasificacio n de nuevos datos simplemente usando el criterio:
Asignar x a j x j
Un opcion alternativa seria usar este u otro criterio para clasificar los patrones en el conjunto de entrenamiento
y luego usar estas etiquetas para disen ar el sistema de reconocimiento de patrones usando un aprendizaje
supervisado. En la practica ocurre que determinar explicitamente las regiones i implicara estimar la funcion
de densidad conjunta y luego analizarla en un espacio de dimensi o n n lo que generalmente es impracticable
por su complejidad computacional. Ademas como vimos, solo necesitamos de un metodo indirecto que nos
permita etiquetar automaticamente los patrones de entrenamiento. Entonces lo que queremos es alguna forma
de hacer una particion del conjunto de entrenamiento en clases con una misma etiqueta y esto es lo que se
conoce como metodos de agrupamiento o clustering.
Intuitivamente podemos anticipar que las modas en la funci o n de densidad conjunta p(x) estaran asociadas a regiones con alta densidad de muestras en el espacio de observaci o n. El proposito de las tecnicas de
agrupamiento sera justamente detectar y agrupar estos enjambres de puntos.

3.2. Medidas de Similitud y Criterios de Agrupamiento

El proposito de los metodos de agrupamiento sera analizar y extraer la estructura presente en un conjunto de
patrones o muestras de entrenamiento. Diremos que un conjunto de datos est a bien estructurado si contiene
varios enjambres de patrones cercanos entre si, o sea regiones de alta densidad, separados por otras regiones
relativamente vacias o con poca densidad.
Vemos que los puntos de un mismo agrupamiento apareceran mas proximos entre ellos que a puntos en otros
agrupamientos. Esta observacio n nos lleva a concluir que si queremos decidir si un punto x pertenece o no a
un agrupamiento necesitaremos una medida de proximidad o similitud. Se han sugerido y estudiado un gran
numero de tales medidas, pero probablemente las mas comunmente usadas son las medidas de distancia y en
particular la distancia Euclideana.
La afinidad de un punto a un agrupamiento se puede determinar ya sea midiendo su similitud con otros
puntos en el agrupamiento o bien con un modelo definido para el agrupamiento. El ejemplo m a s sencillo de
esto u ltimo es representar un agrupamiento i por su vector medio i ; en este caso la afinidad entre un puntox
y el agrupamiento se puede cuantificar con la distancia Euclideana al cuadrado
+
,
d(x, i ) = (x i )T (x i )

3. Apendizaje no supervisado

11

Figura 7: Datos structurados vs. no estructurados.

Pero para particionar un conjunto de puntos en agrupamientos de una manera o ptima no nos alcanza con una
medida de afinidad o similitud sino que ademas necesitamos algun criterio de agrupamiento que nos permita
definir cuantitativamente cuando una partici o n es mejor que otra. Obviamente tanto el criterio de agrupamiento que definamos tanto como el algoritmo de agrupamiento asociado, estar a n intimamente relacionados
con la medida de similitud usada y se definiran a partir de esta.
En la siguiente seccion veremos algunos ejemplos de metodos de agrupamiento que se basan en los conceptos
anteriores.

3.3. Algoritmo de k-medias (k-means).

Supondremos que el conjunto de datos X contiene k agrupamientos y que cada uno de estos subconjuntos
Xi puede representarse adecuadamente con su valor medio i . Como se menciona anteriormente, en este
caso podemos usar la distancia Euclideana como una medida de similitud. Se deduce que un criterio de
agrupamiento adecuado en este caso es considerar la suma total sobre el conjunto de entrenamiento de la
distancia cuadratica de cada punto al vector valor medio de su agrupamiento.
El objetivo del algoritmo de agrupamiento sera encontrar entre todas las particiones de X en k conjuntos
{Xi ; i = 1, 2, , k} aquella que minimice el criterio de agrupamiento elegido.
Dicho formalmente, queremos encontrar los agrupamientos {X i } que minimizan la funcion
J=

k
!
i=1

Ji =

Ni
k !
!
i=1 j=1

d(xij , i ) siendo xij Xi , Ni = #Xi

entre todas las posibles particiones de X en k subconjuntos.

Un algoritmo para minimizar J puede deducirse considerando el efecto de un cambio minimal o at o mico en
la configuracion de agrupamientos, que consiste en sacar un punto x que este en el agrupamiento X l para
pasarlo a otro agrupamiento Xr .


INDICE

12

Claramente esta reasignacio n afectara solo a los agrupamientos l y r cuyos valores medios pasar a n a ser

l = l +

1
(l x)
Nl 1

y
r = r

1
(r x)
Nr + 1

respectivamente.
Para deducir la primera ecuacio n calculamos el valor medio de Xi antes y despues de la reasignacio n

Nl
N
Nl
l 1
!
1 !
1
1 !
l =
xj =
xj x
xj

l =
Nl j=1
Nl 1 j=1
Nl 1 j=1
donde hemos asumido que el punto reasignado es el u ltimo en la sumatoria. De aqui resulta que
(Nl 1)
l = Nl l x

l =

1
Nl
l
x
Nl 1
Nl 1

l = l +

1
(l x)
Nl 1

y analogamente se verifica la segunda identidad.

Por lo tanto para calcular el cambio global en el valor de J bastar a calcular los cambios en las contribuciones
de Jl y Jr . Para el nuevo agrupamiento l-esimo tendremos
Jl =

N
l 1
!

d(xj , mul ) =

j=1

j=1

Nl
!
j=1

Jl

N
l 1
!

xj l +

(xj l )T (xj l ) =

l x *T )
l x * )
l x *T )
l x *
xj l +
x l +
x l +
=
Nl 1
Nl 1
Nl 1
Nl 1

Nl
!
2
Nl
Nl2
T
(xj l ) +
(l x)
(

x)
(

x)
+
(l x)T (l x)
l
l
2
2
Nl 1
(N

1)
(N

1)
l
l
j=1
/
01
2
0

de donde luego de agrupar concluimos que

Jl = Jl

Nl
Nl
(l x)T (l x) = Jl
d(x, l )
Nl 1
Nl 1

y analogamente para el agrupamiento r se obtiene

Jr = Jr +

Nr
Nr
(r x)T (r x) = Jr +
d(x, r )
Nr 1
Nr 1