Algoritmo "O-Cluster"

El clustering es usado para segmentar datos en clusters naturales o para la asignación de nuevos datos a un cluster
Cluster es un algoritmo basado en la densidad el cual no usa formulas distantes. O-Cluster es un algoritmo propiedad de Oracle. Este algoritmo determina las áreas de densidad buscando en un “valle” separado por 2 “colinas” de densidad en la curva de distribución de un atributo.

O-Cluster permite la clusterización de tipos de datos numéricos y categóricos asi como la asignación de reglas de cluster que describen las características de cada uno de ellos.
Se debe escoger O-Cluster si:
*Se desea que el número de clusters sea determinado automáticamente
*Se tengan atributos numéricos y categoricos
*Se tienen mas de 20 atributos
*Se tienen mas de 1000 numeros de casos

El algoritmo O-cluster crea un modelo jerarquico de cluster que a su vez crea particiones paralelas en el espacio del atributo de entrada. Este algoritmo funciona recursivamente. El resultado de la estructura jerarquica representa una tabla irregular que representa como mosaico del espacio de los atributos en los clusters. Los clusters resultantes son descritos en intervalos a través de los ejes de los atributos y los centroides e histrogramas correspondientes. Solo las áreas con una densidad pico encima del nivel podrán ser identificados como clusters.

Algoritmo O cluster

1. Cargar el buffer: Si todos los datos no caben en el buffer un ejemplo aleatorio será utilizado. O clúster apunta del buffer inicial a la única partición activa root.

2. Computar histogramas de particiones activas: La meta es computar histogramas a través de las proyecciones unidimensionales ortogonales de cada una de las particiones.

3. Encontrar el mejor punto de separación para las particiones activas: Para cada histograma, O clúster pretende encontrar la mejor zona de corte si existe. Los algoritmos examinan de manera separada los grupos de atributos numéricos y nominales y selecciona el mejor.

4. Banderas ambiguas y particiones congeladas: Si no se encuentran puntos de separación, O clúster revisa si tiene un punto valido de separación a un nivel de menor confidencialidad, si es el caso las particiones se consideran ambiguas. Si no hay ambigüedad y no hay puntos de separación, la partición se considera “congelada”.

5. Particiones de separación activas: Si existe un separador valido, los datos son separados en el lugar del corte, y dos nuevas particiones activas son creadas de la partición original. Regresa al paso 2

6. Recargar el buffer: Este paso se lleva a cabo cuando la partición recursiva del buffer es completada. Si todas las particiones fueron congeladas y no hay más puntos de datos disponibles, el algoritmo termina. Por lo contrario si algunas particiones son marcadas como ambiguas y si existen registros de datos no vistos, O clúster procede con la recarga del buffer de datos.

Cuando hay nuevos registros leídos, solo los puntos de los datos que caen del lado de los ambiguos se colocan en el buffer. Los congelados no se agregan y son descartados. La carga de nuevos registros continua si 1) El buffer se llena de nuevo 2) Se alcanza el término del Data-Set o 3) Un número razonable de registros (igual al tamaño del buffer) han sido leídos, aunque el buffer no esté lleno y no haya más datos. La razón para esta última condición es que el buffer es relativamente grande y existen muchos puntos marcados para su borrado, y toma mucho tiempo llenar el buffer con datos de regiones ambiguas. Para evitar la recarga excesiva bajo estas circunstancias, este proceso se termina cuando es del tamaño del buffer. Una vez que la recarga del buffer es completada, el algoritmo procede al paso 2