Referencia técnica del algoritmo de clústeres de Microsoft

En el método de agrupación en clústeres EM, el algoritmo refina de forma iterativa un modelo de clústeres inicial para ajustar los datos y determina la probabilidad de que un punto de datos exista en un clúster. El algoritmo finaliza el proceso cuando el modelo probabilístico ajusta los datos. La función usada para determinar el ajuste es el logaritmo de la probabilidad de los datos dado el modelo.

Si durante el proceso se generan clústeres vacíos, o si la pertenencia de uno o varios de los clústeres cae por debajo del umbral especificado, los clústeres con poblaciones bajas se reinicializan en los nuevos puntos y vuelve a ejecutarse el algoritmo EM.

Los resultados del método de agrupación en clústeres EM son probabilísticos. Esto significa que cada punto de datos pertenece a todos los clústeres, pero cada asignación de un punto de datos a un clúster tiene una probabilidad diferente. Dado que el método permite que los clústeres se superpongan, la suma de los elementos de todos los clústeres puede superar la totalidad de los elementos existentes en el conjunto de entrenamiento. En los resultados del modelo de minería de datos, las puntuaciones que indican soporte se ajustan para tener en cuenta este hecho.

El algoritmo EM es el algoritmo predeterminado usado en los modelos de agrupación en clústeres de Microsoft. Este algoritmo se usa como algoritmo predeterminado porque proporciona numerosas ventajas comparado con la agrupación en clústeres mediana-K:

• Requiere examinar la base de datos como máximo una vez.

• Funciona incluso si la cantidad de memoria (RAM) es limitada.

• Tiene la capacidad de usar un cursor de solo avance.

• Sus resultados superan los obtenidos por los métodos de muestreo.

La implementación de Microsoft proporciona dos opciones: EM escalable y no escalable. De forma predeterminada, en EM escalable, los primeros 50.000 registros se usan para inicializar el examen inicial. Si esta operación se realiza correctamente, el modelo solo usa estos datos. Si el modelo no se puede ajustar con 50.000 registros, se leen otros 50.000. En EM no escalable, se lee el conjunto de datos completo independientemente de su tamaño. Este método puede crear clústeres más precisos, pero los requisitos de memoria pueden ser significativos. Dado que EM escalable funciona en un búfer local, recorrer los datos en iteración es mucho más rápido, y el algoritmo hace un mejor uso de la caché de memoria de la CPU que EM no escalable. Es más, EM escalable es tres veces más rápido que EM no escalable, incluso si todos los datos caben en la memoria principal. En la mayoría de casos, la mejora en el rendimiento no significa una reducción de la calidad del modelo completo.

Para obtener un informe técnico que describa la implementación de EM en el algoritmo de clústeres de Microsoft, vea el documento Scaling EM (Expectation Maximization) Clustering to Large Databases.

La agrupación en clústeres mediana-K es un método muy conocido para asignar la pertenencia al clúster que consiste en minimizar las diferencias entre los elementos de un clúster al tiempo que se maximiza la distancia entre los clústeres. El término "mediana" hace referencia al centroide del clúster, que es un punto de datos que se elige arbitrariamente y que se refina de forma iterativa hasta que representa la verdadera media de todos los puntos de datos del clúster. La "K" hace referencia a un número arbitrario de puntos que se usan para inicializar el proceso de agrupación en clústeres. El algoritmo mediana-K calcula las distancias euclidianas cuadradas entre los registros de datos de un clúster y el vector que representa la media de clústeres, y converge en un conjunto final de K clústeres cuando la suma alcanza su valor mínimo.

El algoritmo mediana-K asigna cada punto de datos a un solo clúster y no permite la incertidumbre en la pertenencia. En un clúster, la pertenencia se expresa como una distancia desde el centroide.

Normalmente, el algoritmo mediana-K se usa para crear clústeres de atributos continuos, donde el cálculo de la distancia a una media se realiza de manera sencilla. Sin embargo, la implementación de Microsoft adapta el método mediana-K a atributos discretos de clúster mediante el uso de probabilidades.  Para los atributos discretos, la distancia de un punto de datos desde un clúster determinado se calcula de la manera siguiente:

1 - P(punto de datos, clúster)

El algoritmo mediana-K proporciona dos métodos para realizar un muestreo en el conjunto de datos: mediana-K no escalable, que carga el conjunto de datos completo y realiza una pasada de agrupación en clústeres, y mediana-K escalable, donde el algoritmo usa los primeros 50.000 casos y lee más casos únicamente si necesita más datos para lograr un buen ajuste del modelo a los datos.

En SQL Server 2008, la configuración predeterminada del algoritmo de clústeres de Microsoft se cambió para usar el parámetro interno, NORMALIZATION = 1. La normalización se lleva a cabo usando estadísticas de puntuación-z y se supone una distribución normal. El propósito de este cambio en el comportamiento predeterminado es minimizar el efecto de los atributos que puedan tener grandes magnitudes y muchos valores atípicos. Sin embargo, la normalización puntuación-z puede alterar los resultados de los clústeres en distribuciones que no son normales (como las distribuciones uniformes). Como consecuencia de esta implementación, los clientes que migren soluciones de SQL Server 2005 Analysis Services a 2008 podrían observar que los modelos de agrupación en clústeres generan resultados diferentes. Para evitar la normalización y obtener el mismo comportamiento que el algoritmo de clústeres mediana-K de SQL Server 2005, puede usar el cuadro de diálogo Configuración de parámetros para agregar el parámetro personalizado, NORMALIZATION, y establecer su valor en 0.

En la tabla siguiente se describen los parámetros que se pueden usar con el algoritmo de clústeres de Microsoft. Estos parámetros afectan tanto al rendimiento como a la precisión del modelo de minería de datos resultante.

• CLUSTERING_METHOD
  Especifica el método de agrupación en clústeres que va a usar el algoritmo. Los métodos de agrupación en clústeres disponibles son:

  Identificador	Método
  1	EM escalable
  2	EM no escalable
  3	Mediana-K escalable
  4	Mediana-K no escalable

  El valor predeterminado es 1 (EM escalable).

• CLUSTER_COUNT
  Especifica el número aproximado de clústeres que será generado por el algoritmo. Si no se puede generar el número aproximado de clústeres a partir de los datos, el algoritmo genera tantos clústeres como sea posible. Si CLUSTER_COUNT se establece en 0, el algoritmo usa la heurística para determinar el mejor número de clústeres que debe generar.

  El valor predeterminado es 10.

• CLUSTER_SEED
  Especifica el número de inicialización usado para generar clústeres aleatoriamente para la fase inicial de generación del modelo.

  Cambiando este número, se puede cambiar la manera en que se generan los clústeres iniciales y, a continuación, comparar modelos que se han generado usando inicializaciones diferentes. Si se cambia la inicialización pero los clústeres hallados no cambian en gran medida, el modelo se puede considerar relativamente estable.

  El valor predeterminado es 0.

• MINIMUM_SUPPORT
  Especifica el número mínimo de casos requeridos para generar un clúster. Si el número de casos del clúster es inferior a este número, el clúster se trata como vacío y se descarta.

  Si se establece un número demasiado alto, se pueden perder clústeres válidos.

  Nota

  Si se usa EM, que es el método de agrupación en clústeres predeterminado, algunos clústeres pueden tener un valor de soporte más bajo que el valor especificado. Esto se debe a que cada caso se evalúa según su pertenencia a todos los clústeres posibles, y para algunos clústeres puede haber solo un soporte mínimo.

  El valor predeterminado es 1.

• MODELLING_CARDINALITY
  Especifica el número de modelos de ejemplo que se construyen durante el proceso de agrupación en clústeres.

  Reducir el número de modelos candidatos puede mejorar el rendimiento, pero se corre el riesgo de perder algunos modelos buenos.

  El valor predeterminado es 10.

• STOPPING_TOLERANCE
  Especifica el valor que se usa para determinar cuándo se alcanza la convergencia y el algoritmo termina de generar el modelo. La convergencia se alcanza cuando el cambio general de las probabilidades del clúster es inferior al resultado de dividir el parámetro STOPPING_TOLERANCE entre el tamaño del modelo.

  El valor predeterminado es 10.

• SAMPLE_SIZE
  Especifica el número de casos que el algoritmo usa en cada paso si el parámetro CLUSTERING_METHOD está establecido en uno de los métodos de agrupación en clústeres escalables. Si se establece el parámetro SAMPLE_SIZE en 0, todo el conjunto de datos se agrupará en clústeres en un único paso. Cargar el conjunto de datos completo en un paso único puede causar problemas de memoria y de rendimiento.

  El valor predeterminado es 50000.

• MAXIMUM_INPUT_ATTRIBUTES
  Especifica el número máximo de atributos de entrada que el algoritmo puede procesar antes de invocar la selección de características. Si se establece este valor en 0, se especifica que no existe un número máximo de atributos.

  Aumentar el número de atributos puede degradar significativamente el rendimiento.

  El valor predeterminado es 255.

• MAXIMUM_STATES
  Especifica el número máximo de estados de atributo admitido por el algoritmo. Si un atributo tiene más estados que el máximo permitido, el algoritmo usa los estados más conocidos y pasa por alto los estados restantes.

  Aumentar el número de estados puede degradar significativamente el rendimiento.

  El valor predeterminado es 100.

El algoritmo admite las marcas de modelado que se indican a continuación. Los marcadores de modelado se definen al crear la estructura de minería de datos o el modelo de minería de datos. Las marcas de modelado especifican cómo se procesan los valores de cada columna durante el análisis.

El algoritmo de clústeres de Microsoft admite las columnas de entrada y de predicción específicas que se enumeran en la tabla siguiente. Para obtener más información sobre lo que significan los tipos de contenido cuando se usan en un modelo de minería de datos, vea Tipos de contenido (minería de datos).