• Eficiencia computacional: La detección de patrones en bases de datos es una tarea eminentemente práctica. En consecuencia, los algoritmos que se diseñen para este fin deben ser capaces de dar respuesta a los problemas que se planteen, más allá de cuál sea el tamaño particular de la base de datos sobre la que se vaya a aplicar el algoritmo. Dicho de otro modo, un algoritmo que funcione bien (es decir, que sea capaz de detectar patrones en un tiempo razonable) en bases de datos de reducido tamaño (con unas pocas decenas de filas y unas pocas columnas) pero fracase en bases de datos reales (por presentar tiempos de ejecución muy elevados) no resultará aceptable. De forma más precisa, debe exigirse que un algoritmo de detección de patrones sea eficiente desde el punto de vista computacional. Son muchas las formas de medir la eficiencia de un algoritmo pero, quizás, la más extendida sea la evaluación de su complejidad-temporal. La complejidad-temporal de un algoritmo es una expresión del tiempo de ejecución (o del número de operaciones) que precisa dicho algoritmo en función del tamaño del problema (medido, por ejemplo, a partir del número de filas o columnas de la base de datos analizada). Para expresar la complejidad-temporal de un algoritmo suele recurrirse a la llamada “notación de Landau” (o notación de la O mayúscula). Se dice que un problema es tratable cuando el algoritmo más eficiente para resolverlo tiene complejidad temporal polinómica o inferior, es decir, cuando la función que pone en relación el tiempo (o número de operaciones) que requiere el algoritmo para resolver el problema con el tamaño de éste pertenece a con . Este requisito es, en realidad, bastante laxo ya que complejidades polinómicas pueden suponer (si el grado del polinomio es alto) tiempos de ejecución que hoy en día (a pesar del rápido incremento en la velocidad de los procesadores) resultan inaceptables. Lamentablemente, muchos de los algoritmos que se diseñan para la detección de patrones presentan complejidades-temporales superiores a la polinómica y son, por tanto, intratables desde el punto de vista de la teoría de la complejidad algorítmica.
• Robustez: Cualquier base de datos, y en mayor medida si es de gran tamaño, es susceptible de contener valores erróneos. En ocasiones, estos valores erróneos serán detectados (y convenientemente corregidos) por los procedimientos de detección de outliers, pero en ocasiones, aun a pesar de los mayores esfuerzos por parte de los analistas, los datos erróneos escaparán esta criba preliminar y pondrán en peligro la calidad de los análisis que se realicen tomando como materia prima la base de datos en la que se encuentran. Las fuentes de las que pueden provenir estos datos erróneos (a las que se les suele llamar fuentes de errores sistemáticos) son muchas y de diversa naturaleza. Entre otras cabe citar los problemas en los mecanismos de obtención de los datos (por ejemplo, errores en los instrumentos de medida, que pueden no estar correctamente calibrados), errores en la transmisión de los datos de unos soportes a otros (por ejemplo, al teclear manualmente los datos de un cuestionario en papel a una base de datos electrónica) o también errores en la preparación de los datos previa a la realización de algún análisis. Sin ninguna duda, el mejor antídoto contra este tipo de errores es un cuidado exquisito por parte del encargado de alimentar o manipular la base de datos en cada uno de los pasos descritos, pero, a pesar de los mejores esfuerzos por su parte, es imposible evitarlos por completo. De este modo, resulta evidente que una característica muy deseable en los algoritmos automáticos de detección de patrones es que éstos sean relativamente insensibles a la presencia de una cierta proporción de datos erróneos. A esta propiedad se le llama robustez. Así, se dice que un algoritmo de detección de patrones es robusto cuando los patrones detectados en una base de datos no se ven alterados (o al menos no de forma notable) cuando en ésta existe una proporción pequeña de datos erróneos. Lamentablemente, esta propiedad de robustez entra en conflicto con otra propiedad deseable: la sensibilidad, por la que un algoritmo debe detectar patrones diferentes en bases de datos diferentes.
• Estabilidad: Si entendemos una base de datos como una manifestación concreta (particular) de un determinado mecanismo generador de datos, es cuando el concepto de estabilidad de un algoritmo cobra todo su significado. Dicho brevemente: los algoritmos de detección de patrones deberían detectar pautas en los mecanismos generadores de datos y no en la base de datos concreta que están analizando. Dicho de otra forma: diremos que un algoritmo de detección de patrones es estable si obtenidas dos bases de datos alternativas mediante el mecanismo generador (llamémoslas B1 y B2), el algoritmo detecta los mismos patrones en B1 y en B2. Así, un algoritmo estable es aquél que detecta los patrones que corresponden al mecanismo generador de los datos y que deja de lado las particularidades específicas de la base de datos que se está analizando.

A este respecto resulta muy apropiado el comentario de John Allen Paulos en su obra Innumeracy (traducida al español como El Hombre Anumérico) quien cita a Plutarco cuando afirma “It is not great wonder if, in the long process of time, while fortune takes her course hither and thither, numerous coincidences should spontaneously occur”. Se trata de una advertencia sobre el riesgo de lo que dos mil años más tarde se ha dado en llamar overfitting: el riesgo de que un algoritmo de detección de patrones se ajuste en exceso a la realidad concreta de una base de datos detectando, de este modo, pautas que no corresponden al mecanismo generador de los datos sino que son particulares de la base de datos y, por tanto, no generalizables.

El mismo Paulos pone de manifiesto (en un ejemplo que luego recogen Christianini y Shawe-Taylor) cómo la única forma de protegerse del riesgo de overfitting es mediante la limitación de los patrones que cabe esperar encontrar en la base de datos. Si el analista de los datos está dispuesto a encontrar cualquier patrón y diseña el algoritmo con este criterio es seguro que encontrará algún patrón sorprendente: “The paradoxical conclusion is that it would be very unlikely for unlikely events not to occur”. El ejemplo al que recurren los mecionados autores para ilustrar este fenómeno es la muy conocida Paradoja del cumpleaños, que pone de manifiesto cómo son suficientes 23 personas reunidas en una sala para que al menos dos cumplan años en una misma fecha (una fecha cualquiera del año) mientras que son necesarias 253 personas para que alguna cumpla años en una fecha concreta establecida a priori. La clave está en el espacio de patrones que se está dispuesto a encontrar (un día concreto es mucho más restrictivo que cualquier día del año).

Otro ejemplo puede ayudar a ilustrar la idea de overfitting. En efecto, imaginemos que contamos con n parejas (xi,yi) de observaciones tales que todos los valores del primer elemento de la pareja son distintos . Imaginemos que buscamos un patrón que prediga el valor de y en función del valor de x. Pues bien, si el espacio de patrones es el conjunto de polinomios de grado k y estamos dispuestos a incrementar cuanto sea necesario el valor de k, será posible encontrar un patrón (un polinomio de grado n-1) que prediga de forma perfecta cada uno de los valores y en función del correspondiente x. Ahora bien, si mediante el mismo mecanismo de generación de datos obtuviéramos otro conjunto de observaciones y aplicáramos el patrón aprendido en la base original para tratar de efectuar predicciones en la nueva base, los resultados serían mucho menos espectaculares. El conjunto de patrones susceptible de ser analizado era excesivamente grande y, por tanto, ha ocurrido el fenómeno de overfitting.

En aprendizaje estadístico, la llamada complejidad de Rademacher mide la riqueza de una familia de funciones (posibles patrones), entendiendo esta riqueza como la capacidad de la familia de funciones a adaptarse (y detectar) ruido aleatorio. Cuanto mayor sea la complejidad de Rademacher de una familia de funciones, mayor es el riesgo de overfitting que se deriva de su utilización.

Como se ha mencionado ya, la única vía para evitar el problema del overfitting es a través de la limitación o restricción del espacio de búsqueda de posibles patrones. Con este fin, es necesario contar con conocimiento experto en la disciplina a la que se refiere la base de datos analizada. Sólo un experto en el ámbito de estudio (apoyado por el diseñador del algoritmo) puede decidir de manera informada cuál es la naturaleza de los patrones que cabe detectar en su ámbito de conocimiento así como señalar qué patrones no son razonables. De esta manera, el diseñador del algoritmo estará en las mejores condiciones para poder adaptar el algoritmo al ámbito al que se refiere la base de datos analizada. En este sentido, los algoritmos deben ser parametrizables para, a partir de una misma base, adaptarse a problemas de distinta naturaleza.

• El paradigma empírico. En los albores de la ciencia, ésta era puramente empírica y su objetivo no era otro que el de tratar de describir los fenómenos naturales. En particular, los científicos no pretendían generar modelos o leyes que rigieran comportamientos universales sino tan solo explicar aquello que veían.

• El paradigma teórico. La ciencia evolucionó y sus objetivos se tornaron más ambiciosos. La ciencia no se limitaba ya a tratar de explicar aquello que veía. Los científicos deseaban formular modelos de aplicación general: modelos universales. En otras palabras, a pesar de que la ciencia continuó siendo empírica, adquirió un carácter teórico. Las leyes de Kepler, las leyes de Newton o las ecuaciones de Maxwell son ejemplos apropiados de este estadio de la ciencia.

• El paradigma de la simulación. Los modelos teóricos universales que formulaban los científicos en su esfuerzo por explicar el funcionamiento de la realidad se fueron volviendo más y más complejos, hasta el punto de que pronto resultó evidente que estas formulaciones eran demasiado complicadas como para poder ser resueltas de modo analítico (exacto). Los científicos recurrieron entonces a la simulación. La Física, la Biología o la Química (en el ámbito de las Ciencias Experimentales) o la Economía y la Psicología (entre las Ciencias Sociales) son ejemplos de disciplinas que han adoptado la simulación (normalmente apoyada en el recurso intensivo a los ordenadores) con el fin de valorar el desempeño de sistemas excesivamente complejos para ser evaluados mediante un enfoque analítico.

• El paradigma intensivo en datos. En la actualidad, el progresivamente mayor recurso a la simulación ha generado grandes volúmenes de datos. A éstos se une el aluvión proveniente de las observaciones empíricas de las Ciencias Experimentales (que cuentan con instrumentos cada vez más precisos y potentes). Todos esos datos, captados o generados, se acumulan en bases de datos a la espera de ser analizados mediante potentes programas de ordenador que persiguen la detección de patrones o pautas de regularidad. Según este nuevo paradigma, estas pautas permitirán a los científicos aventurar nuevas conjeturas acerca de cómo funciona el mundo. Esta forma de entender la ciencia recibe el nombre de El Cuarto Paradigma.

Más información de cara a la organización de próximas jornadas aquí.

El modelo de ajuste correspondiente a este modelo teórico es

Este modelo de ajuste cumple

Este hecho se suele expresar diciendo que “el modelo de ajuste pasa por la media”. Este hecho resulta de gran utilidad práctica ya que permite el cálculo del término independiente en el caso de que el ajuste del modelo se esté efectuando mediante el método de datos centrados mediante el empleo de la siguiente fórmula:

Pero, ¿qué ocurre cuando al modelo teórico se le añaden restricciones lineales? ¿sigue pasando por la media? Dicho de otra forma: ¿se cumple la siguiente expresión?

Bajo ciertas condiciones, la respuesta es afirmativa y la demostración sumamente sencilla

Sabemos que

y por tanto

Para que debe ocurrir que

ya que

Consideremos la matriz

Demostraremos que, bajo ciertas condiciones muy generales, dicha matriz es nula y, en consecuencia, que

por lo que

En efecto,

donde es la matriz que proyecta los vectores de en la dirección del vector formado por unos.

El resultado de premultiplicar cualquier vector de por la matriz es un vector de cuyos componentes son todos iguales e iguales a la media de los componentes del vector original.

Consideremos ahora la matriz

Si premultiplicamos esta matriz por , el resultado es la matriz identidad, por lo que todas las columnas de excepto la primera son ortogonales al vector de formado por unos -la primera columna de la matriz -. Si no fuera así, no sería la matriz identidad, lo cual es absurdo. Dicho de otro modo, las sumas de los elementos de todas y cada una de las columnas de la matriz  -excepto la primera- son nulas y, en consecuencia, las medias son nulas.

Como consecuencia de este hecho,

es una matriz cuyos componentes son nulos salvo los de la primera columna.

¿Qué debe ocurrir para que la matriz sea nula?

Es suficiente con que la primera columna de la matriz sea nula. En ese caso, al postmultiplicar por se obtendrán combinaciones lineales de columnas de ceros, ya que la primera columna de -la única que puede no tener ceros- no forma parte de las combinaciones lineales.

¿Cómo podemos expresar la idea de que la primera columna de la matriz sea nula de una forma más intuitiva? La primera columna de la matriz recoge los coeficientes del término independiente en las restricciones lineales que se añaden al modelo teórico. Decir que la primera columna de es nula es lo mismo que decir que las restricciones añadidas al modelo teórico no involucran al término independiente.

En resumen, hemos demostrado que si las restricciones lineales que se añaden a un modelo teórico no incluyen al término independiente -lo que, en la práctica es la situación más habitual- entonces el modelo de ajuste con restricciones “pasa por la media”, es decir, satisface la ecuación

Finalmente, este hecho resulta de gran utilidad práctica para calcular el término independiente en el modelo de ajuste con restricciones si es que se está trabajando con datos centrados ya que se cumple que

Esto me reafirma en mi opinión de que el equipo de agrocampus ouest sigue siendo el mejor en lo que a análisis multivariante se refiere. Ahora “amenazan” con mejorar su paquete FactoMineR incluyendo en él funciones que permiten realizar análisis cluster jerárquicos a partir de los resultados obtenidos de un análisis de componentes principales.

Estaré atento a la publicación de la nueva versión.

Entre otras cosas, el autor critica la omnipresencia en las ciencias sociales de la distribución normal -y de la media aritmética-. En su opinión, en muchas ocasiones es una mejor opción la distribución log-normal y la media geométrica. El autor nos proporciona unos consejos prácticos para seleccionar la media que mejor se adapta a los datos de que disponemos. Cito:

Geometric means often express the central tendency better than arithmetic means. For the same reason, lognormal data fits often are called for, instead of desperate attempts to fit data into a Procrustean normal distribution. The following advice applies, with some reservations.

• In the absence of any other information, if a variable can range from minus to plus infinity, a normal distribution is our best  bet, implying that the arithmetic mean is close to the median. (In the presence of further information, the bet may be off.)
• In the absence of any other information, if a variable can have only positive values, a lognormal distribution is among our best bets, implying that the geometric mean is close to the median. (In the presence of further information, the bet may be off-we may have a gamma distribution or something else.)
• However, if one tries a normal fit and standard deviation turns out less than one-half of the mean, then one might use this normal distribution. If standard deviation exceeds one-half of the mean, the normal fit should be abandoned in favor of lognormal.
• If negative values are conceptually excluded but zero values do ocurr, then neither distribution can fit. Neither mean adequately reflects the median, but a pseudo-geometric mean might approximate it.
• When there are grounds to hesitate between the arithmetic and geometric means, using the median might be the safest way, although it is awkward to calculte.

A este respecto resulta muy interesante el artículo de Limpert et al. (2001) de título Lognormal Distributions across the Sciences: Keys and Clues.

Trataremos en este post el caso de la clasificación, es decir, la situación en la que la variable dependiente es cualitativa, con dos o más modalidades.

En esencia, el método CART parte de un nodo raíz o nodo inicial, que contiene al conjunto de todos los individuos, y establece una partición de dicho conjunto en dos subconjuntos -llamados nodos hijos- siguiendo el criterio de minimizar la heterogeneidad interna de dichos nodos -lo que supone maximizar la heterogeneidad entre ellos-. Este paso se repite con cada uno de los nodos hijos y así sucesivamente hasta satisfacer el criterio de parada -por ejemplo, porque se ha obtenido un nodo completamente homogéneo o de un tamaño menor que un umbral previamente establecido-. Así, el resultado final de esta primera fase del método CART es un árbol binario -cada nodo padre se divide en dos nodos hijos- de nombre árbol máximo.

El conjunto de nodos terminales del árbol máximo constituye una partición del conjunto inicial de individuos. A cada uno de dichos nodos terminales se le asigna una etiqueta igual a la moda en dicho nodo de la variable cualitativa dependiente. Supongamos, por ejemplo, que la variable dependiente analizada es el sexo, con dos modalidades, H y M. Se asignaría la etiqueta H a aquellos nodos terminales en los que haya más H que M y la etiqueta M a los demás. La asignación de la etiqueta a los nodos terminales supone la existencia de un error de clasificación debido a la presencia en nodos terminales de individuos cuya modalidad en la variable dependiente no coincide con la etiqueta asignada a dicho nodo terminal. Naturalmente, el árbol máximo es el árbol con el mínimo error de clasificación.

A partir del árbol máximo comienza el llamado proceso de poda del árbol. Hemos comentado que el árbol máximo tiene un error de clasificación muy pequeño pero sólo a costa de una gran complejidad -un elevado número de nodos-. En la mayoría de las situaciones merece la pena incrementar en pequeña medida el error de clasificación para simplificar la estructura del árbol binario obtenido. Se obtiene de este modo un árbol llamado árbol óptimo -al menos desde el punto de vista del coste-complejidad-.

Es muy importante recordar que el error de clasificación calculado para el árbol óptimo tiende a sobrevalorar el verdadero poder explicativo de las variables independientes para explicar la variable dependiente. La práctica habitual es la de destinar una parte de la muestra total de individuos a “aprender el árbol” y otra parte de la muestra a contrastar la calidad del árbol.

Naturalmente, R dispone de paquetes que permiten la aplicación del método CART. Por ejemplo, el package rpart.

El estilo del profesor Strang es directo. Los capítulos consisten en una breve -brevísima- presentación teórica seguida de un ejemplo, que se exprime de forma obsesiva hasta sacarle todo su jugo y, en particular, hasta poder formular conjeturas que, finalmente, son demostradas.

El índice es el siguiente:

1. Introduction to Vectors
2. Solving Linear Equations
3. Vector Spaces and Subspaces
4. Orthogonality
5. Determinants
6. Eigenvalues and Eigenvectors
7. Linear Transformations
8. Applications
9. Numerical Linear Algebra
10. Complex Vectors and Matrices

Para comprender bien los fundamentos del análisis multivariante es crucial un dominio del contenido de los capítulos 1 a 6 de este texto -los capítulos 7 a 10 pueden dejarse para un segundo curso de álgebra lineal-.

Además del libro, recomiendo los vídeos de la asignatura Linear Algebra 18.06 impartida en el MIT por el profesor Strang en otoño de 1999.

Con dynGraph es posible:

• Mostrar sólo los individuos que superen una cierta suma de cosenos cuadrados.
• Mover las etiquetas de individuos y variables de forma que no se solapen.
• Establecer el tamaño de los individuos en función de su contribución o del valor que toman en alguna variable cuantitativa.

En resumen, el paquete permite un tratamiento adicional de los gráficos básicos que nos proporciona R.

Se trata de un análisis de componentes principales en el que los individuos son los distintos municipios de Euskadi y las variables son los porcentajes de votos obtenidos por cada uno de los partidos que, finalmente, obtuvieron algún escaño en el Parlamento. Los individuos están ponderados en función del censo electoral del municipio.

El gráfico de las variables -el círculo de correlación-, que se presenta más arriba, sitúa en la parte derecha a los partidos de ámbito nacional y a la izquierda a los partidos de ámbito regional. Podemos interpretar este primer eje como una oposición entre nacionalismo español -a la derecha- frente a nacionalismo vasco -a la izquierda-. Dado que este es el eje principal de inercia podemos entender que es, precisamente, esta oposición la que en mayor medida caracteriza las diferencias electorales entre los municipios del País Vasco. En cuanto al segundo eje de inercia -que se presenta en vertical- se observa fácilmente que opone a los partidos nominalmente “de izquierdas” -en la parte superior del gráfico- a los partidos “de derechas” -situados en la parte inferior-, con la excepción de Eusko Alkartasuna.

En lo que se refiere al gráfico de los individuos -municipios en este caso-, estos se presentan coloreados según el territorio histórico al que pertenecen. Se observa cómo los territorios históricos se pueden concebir como unidades de destino en lo electoral. Dicho de otra forma, se observa una gran homogeneidad interna en los territorios históricos:

• Los municipios alaveses -en color negro- están relacionados con los partidos de ámbito nacional y de derechas.
• Los municipios guipuzcoanos -en color rojo- están relacionados con los partidos de ambito regional y de izquierdas.
• Vizcaya -en color verde- aparece en una posición intermedia.

¿Comentarios?