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