Diseño de Conjuntos moleculares balanceados para su aplicación en la teoría QSPR-QSAR (página 7)

Apéndice

I. Discriminación y Clasificación en
LDA

Si consideramos una matriz de atributos o variables
independientes para
cada objeto que pertenece a una clase G1 determinada, este
conjunto de muestras es el llamado conjunto de entrenamiento o
calibración. El problema consiste entonces en hallar una
buena predicción de la clase G1 de un objeto considerado,
con el uso de la misma distribución del conjunto de
entrenamiento, a través de los valores de las variables

La obtención de la función discriminante
incluye una serie de aproximaciones, a saber:

i. las funciones densidad de probabilidad, y son ambas distribuciones normales,
G1.

ii. si y
son los
parámetros media y covarianza de G1=0 y G1=1,
respectivamente, se supone que las covarianzas son
iguales.

Función Discriminante Lineal

Es posible encontrar una relación lineal que
caracterice a cada objeto según los valores de sus
atributos. De esta manera, si tenemos un conjunto de N
objetos de los que se conocen D variables explicativas,
y se observa que N1 de ellos pertenecen a la clase C1, y
los N2 restantes a la clase C2, con N1+N2=N, es
posible construir una función lineal en base a las
D variables y puede usarse para predecir si pertenece a
un grupo u otro con una probabilidad determinada. En la
función lineal:

(AI.1)

es una
variable clasificadora, es la i-ésima variable
atributo, y es su
coeficiente. El objetivo principal de tal función lineal
desde el punto de vista de la varianza consiste en responder a la
pregunta de si dos o más grupos son significativamente
distintos uno a otro respecto a la medida de una variable en
particular. Debe tenerse presente que si la media de una variable
es significativamente diferente en varios grupos, puede decirse
que esta variable discrimina bien entre grupos.

En caso de que sea posible identificar más de dos
grupos en los datos, pueden estimarse funciones discriminantes
múltiples, cada una de ellas similares a la presentada en
la Ec. (AI.1). Por ejemplo, cuando se tienen tres grupos, puede
estimarse: 1) una función para discriminar entre el grupo
1 y los grupos 2 y 3 combinados; y 2) otra función para
discriminar entre el grupo 2 y el grupo 3. Además, se
pueden considerar sólo las funciones discriminantes
múltiples que resulten más significativas: si se
observan los coeficientes estandarizados de las variables de cada
una de las funciones escogidas, cuanto mayor sean estos
coeficientes, más alta es la contribución a la
discriminación especificada. Finalmente, pueden
considerarse las medias de las funciones discriminantes
significativas para analizar entre cuales grupos éstas
discriminan.

II. Tipos de Medida de Distancia

Sea una matriz X (mxn) que es tratada como
m vectores fila x1, x2, …, xm. Varios
tipos de medida de distancia que son posibles definir para el par
de objetos r y s, con xr y
xs, se incluyen a continuación:

i. Distancia Euclídea: es la distancia entre dos
puntos que se mide en el espacio euclídeo, se define
como

(AII.1)

ii. Distancia Euclídea Estandarizada: cada
coordenada en la suma cuadrática se pesa inversamente por
la varianza muestral de esa coordenada.

(AII.2)

donde es
la matriz con elementos diagonales dados por vj2, que se refiere
a la varianza de la variable sobre los m objetos.

iii. Distancia Mahalanobis: es una forma de determinar
la similitud entre dos variables aleatorias multidimensionales. A
diferencia de la distancia Euclídea, esta medida tiene en
cuenta la correlación de las variables.

(AII.3)

donde es
la matriz de covarianza muestral.

iv. Distancia Manhattan: aquí la distancia entre
dos puntos es la suma de las diferencias (absolutas) de sus
coordenadas.

(AII.4)

v. Distancia Minkowski

(AII.5)

En el caso especial p=1, la distancia Minkowski
coincide con la distancia Manhattan, y para el caso especial
p=2, la distancia Minkowski coincide con la distancia
Euclídea.

vi. Distancia Coseno: uno menos del ángulo
incluido entre los puntos (en forma de vector).

(AII.6)

vii. Distancia de Correlación: uno menos la
correlación entre los puntos (tratado como secuencias de
valores).

(AII.7)

donde y

viii. Distancia Hamming: es el porcentaje de coordenadas
que difieren.

(AII.8)

III. Métodos de Enlace o
Vinculación

En el método HCA, se utiliza una función
vinculante que crea un árbol de agrupamiento
jerárquico a partir de las distancias entre pares de
objetos previamente obtenidas. La función puede utilizar
diversos métodos de vinculación, los cuales
difieren en la forma que se calculan las distancias entre los
agrupamientos.

La solución que se obtiene en HCA es una matriz
(m-1)x3 llamada Q, donde m es
el número de observaciones en el conjunto original de
datos. Las primera y segunda columnas de Q contienen a los
índices de los agrupamientos vinculados de a pares, para
formar el árbol binario. La tercera columna contiene la
distancia de vinculación entre los agrupamientos
formados.

La siguiente notación se utiliza para describir
los distintos métodos de vinculación:

• Un agrupamiento r es formado a partir de
  los agrupamientos p y q

• nr es el número de objetos en el
  agrupamiento r.

• xir es el i-ésimo objeto en el
  agrupamiento r.

a. Vinculación individual,
también llamado vecino más cercano,
utiliza la menor distancia entre dos objetos en los dos
agrupamientos.

(AIII.1)

b. Vinculación completa, también
llamado vecino más lejano, utiliza la mayor distancia
entre dos objetos en los dos agrupamientos.

(AIII.2)

c. Vinculación promedio, utiliza la
distancia promedio entre todos los pares de objetos en cualquiera
de los dos agrupamientos.

(AIII.3)

d. Vinculación centroide, utiliza la
distancia Euclídea entre los centroides de los dos
agrupamientos.

(AIII.4)

donde y
se refiere a la
distancia Euclídea.

e. Vinculación media, utiliza la
distancia Euclídea entre los centroides ponderados de los
dos agrupamientos,

(AIII.5)

donde y
son los centroides
pesados para los agrupamientos r y s. Si el
agrupamiento r fue creado por la combinación de
los agrupamientos p y q, es definido recursivamente
como

f. Vinculación de Ward, utiliza la suma
incremental de los cuadrados, es decir, el incremento en la suma
total de los cuadrados dentro del agrupamiento, como resultado de
la unión de dos grupos. La suma de los cuadrados dentro
del agrupamiento es definida como la suma del cuadrado de las
distancias entre todos los objetos en el agrupamiento y el
centroide del agrupamiento. La distancia equivalente
es:

(AIII.6)

g. Promedio ponderado de vinculación,
utiliza una definición recursiva para la distancia entre
dos agrupamientos. Si el agrupamiento r fue creado
mediante la combinación de los agrupamientos p y
q, la distancia entre r y otro agrupamiento
s se define como el promedio de las distancias entre
p y s y la distancia entre q y
s:

(AIII.7)

IV. Eliminación de Mínimos Locales y
Descripción del Cálculo Iterativo en el
Método K-Medias.

Eliminación de mínimos
locales

Al igual que sucede en muchos otros problemas de
optimización numérica, la solución que se
alcanza con el método K-Medias depende a menudo del punto
de partida, en este caso la posición inicial del centroide
de cada agrupamiento. Es posible así alcanzar un
mínimo local, donde la reasignación de cualquier
punto a un nuevo agrupamiento debería incrementar la suma
total de distancias centroide-punto, pero donde puede existir
realmente una mejor solución. Para solucionar este
problema, es posible especificar en el método el
número de "réplicas", es decir, el número de
veces en que se repetirá el proceso de agrupación,
cada uno con un nuevo conjunto de posiciones iniciales del
centroide del agrupamiento. Por supuesto, la mejor
solución será aquella para la cual la suma de las
distancias centroide-punto para cada uno de los agrupamientos sea
mínima.

Descripción del algoritmo

El algoritmo consta de dos partes:

Primera fase. Cada iteración consiste en la
reasignación colectiva de elementos al centroide del
agrupamiento más cercano, todos a la vez, seguida de un
nuevo cálculo de las posiciones de los centroides. La
primera fase ocasionalmente converge a soluciones que son un
mínimo local; es más probable alcanzar un
mínimo global si se trabaja con pequeños grupos de
datos. La fase de actualización colectiva es
rápida, pero posiblemente sólo aproxime una
solución que sea el punto de partida de la segunda
fase.

Segunda fase. Los elementos son reasignados
individualmente si con ello se reduce la suma de distancias, y en
cada reasignación se calcula la ubicación del
centroide del agrupamiento. Cada iteración consiste en la
ubicación de todos los elementos. En esta fase la
solución converge a un mínimo local, aunque puede
haber otro mínimo local con menor suma total de
distancias. Generalmente el problema de hallar un mínimo
global puede ser resulto únicamente por medio de una
selección exhaustiva de los puntos de partida, aunque la
utilización de varias réplicas con puntos de
partida aleatorios generalmente converge a una solución
que es un mínimo global.

V. Definición del Parámetro
Silueta

La definición de los valores silueta es la
siguiente: dado un grupo G1 y un objeto i asignado a
éste, la disimilitud promedio de i para todos los
objetos j en G1 está dada por:

número de objetos en G1
(AV.1)

donde es
la distancia de cada objeto i a cada objeto j
en G1. La menor disimilitud correspondiente a i respecto
a cualquier otro agrupamiento, b(i), también es
calculada. Si i es más similar a los objetos en
un grupo G2 que a los del grupo G1, entonces:

número de objetos en G2
(AV.2)

Por lo tanto, el valor silueta s(i)
definido para un objeto i es:

(AV.3)

donde se
refiere al mayor valor entre y

VI. El Clasificador del Método K-Vecinos
Más Cercanos

Si se quiere conocer la clase a la que pertenece un
objeto dado, entre varias clases posibles, se introduce el
concepto de clasificador. Un clasificador es una función
que asigna un objeto a una clase determinada, para lo cual se
basa en el conocimiento de sus variables atributo. Existen dos
tipos de clasificadores:

• Paramétricos: asumen que la
  distribución estadística que sigue el conjunto
  de variables es conocido, y trata de estimar los
  parámetros de dicha distribución.

• No-paramétricos: no asume ninguna
  distribución en particular. El clasificador se
  construye únicamente con los datos del conjunto de
  entrenamiento.

Entre los clasificadores no-paramétricos, el
más conocido es el basado en el método K-vecinos
más cercanos: si Ki es el número de objetos que
pertenecen a la clase Gi entre los K vecinos más cercanos
al objeto considerado x, la probabilidad a
posteriori (la
probabilidad de que la clase sea Gi cuando x se describe
con el conjunto de variables d ) se estima como De esta manera, el
clasificador asigna x a la clase más frecuente
entre sus K vecinos más cercanos, según una cierta
medida de distancia.

VII. Algunos Algoritmos Utilizados en
Matlab

Algoritmo
clusterskmeans.m

Algoritmo clustersknn.m

Tabla de abreviaturas

Agradecimientos

A la Facultad de Ciencias Exactas (UNLP)
donde cursé mi carrera y realice el presente
trabajo.

A mis directores, Eduardo A. Castro y Pablo
R. Duchowicz por la confianza y constante ayuda.

A mis compañeros de carrera por su
compañía diaria.

A mis familiares y amigos, por su apoyo
constante y confianza a lo largo de mi carrera.

Esta tesina fue realizada en el Instituto de
Investigaciones Fisicoquímicas Teóricas y Aplicadas
(INIFTA). Departamento de Química, Facultad de Ciencias
Exactas, Universidad Nacional de La Plata, bajo la
dirección de los Dres. Eduardo A. Castro y Pablo R.
Duchowicz.

Autor:

Rafael Villamayor

Enviado por:

Eduardo Castro

Universidad Nacional de La Plata Facultad
de Ciencias ExactasDepartamento de Química

Marzo de 2011