SUBCLU

SUBCLU es un algoritmo para agrupar datos de alta dimensión creado por Karin Kailing, Hans-Peter Kriegel y Peer Kröger. ^{[ 1 ]} Es un algoritmo de agrupamiento de subespacios que se basa en el algoritmo de agrupamiento basado en densidad DBSCAN . SUBCLU puede encontrar clústeres en subespacios paralelos a los ejes y utiliza una estrategia voraz de abajo hacia arriba para mantener la eficiencia.

SUBCLU utiliza criterios de monotonicidad : si se encuentra un clúster en un subespacio${\displaystyle S}$, entonces cada subespacio${\displaystyle T\subseteq S}$También contiene un clúster. Sin embargo, un clúster${\displaystyle C\subseteq DB}$en el subespacio${\displaystyle S}$no es necesariamente un grupo en${\displaystyle T\subseteq S}$, dado que se requiere que los clústeres sean máximos y se podrían contener más objetos en el clúster en${\displaystyle T}$que contiene${\displaystyle C}$. Sin embargo, un conjunto conectado por densidad en un subespacio${\displaystyle S}$es también un conjunto conectado por densidad en${\displaystyle T\subseteq S}$.

Esta propiedad de cierre descendente es utilizada por SUBCLU de manera similar al algoritmo Apriori : primero, todos los subespacios unidimensionales se agrupan. Todos los clústeres en un subespacio de dimensión superior serán subconjuntos de los clústeres detectados en este primer agrupamiento. SUBCLU produce recursivamente${\displaystyle k+1}$subespacios candidatos de dimensión mediante la combinación${\displaystyle k}$Subespacios de dimensión con clústeres que comparten${\displaystyle k-1}$atributos. Después de eliminar los candidatos irrelevantes, se aplica DBSCAN al subespacio candidato para determinar si aún contiene clústeres. Si es así, el subespacio candidato se utiliza para la siguiente combinación de subespacios. Para mejorar el tiempo de ejecución de DBSCAN , solo se utilizan los puntos que se sabe que pertenecen a clústeres en uno${\displaystyle k}$Se consideran subespacios de dimensión (que se elige para contener la menor cantidad posible de clústeres). Debido a la propiedad de cierre hacia abajo, otro punto no puede ser parte de un${\displaystyle k+1}$-clúster dimensional de todos modos.

SUBCLU toma dos parámetros,${\displaystyle \epsilon \!\,}$y${\displaystyle MinPts}$, que cumplen la misma función que en DBSCAN . En un primer paso, DBSCAN se utiliza para encontrar clústeres 1D en cada subespacio abarcado por un único atributo:

${\displaystyle {\mathtt {SUBCLU}}(DB,eps,MinPts)}$

${\displaystyle S_{1}:=\emptyset }$

${\displaystyle C_{1}:=\emptyset }$

${\displaystyle {\mathtt {para\,cada}}\,a\in Atributos}$

${\displaystyle C^{\{a\}}={\mathtt {DBSCAN}}(DB,\{a\},eps,MinPts)\!\,}$

${\displaystyle {\mathtt {si}}(C^{\{a\}}\neq \emptyset )}$

${\displaystyle S_{1}:=S_{1}\cup \{a\}}$

${\displaystyle C_{1}:=C_{1}\cup C^{\{a\}}}$

${\displaystyle {\mathtt {end\,if}}}$

${\displaystyle {\mathtt {fin\,para}}}$

// En un segundo paso,${\displaystyle k+1}$Los clústeres de -dimensiones se construyen a partir de${\displaystyle k}$-dimensionales:

${\displaystyle k:=1\!\,}$

${\displaystyle {\mathtt {while}}(C_{k}\neq \emptyset )}$

${\displaystyle {\mathtt {CandS}}_{k+1}:={\mathtt {GenerateCandidateSubspaces}}(S_{k})\!\,}$

${\displaystyle {\mathtt {para\,cada}}\,cand\in {\mathtt {CandS}}_{k+1}}$

${\displaystyle {\mathtt {bestSubspace:=}}\min _{s\in S_{k}\wedge s\subset cand}\sum _{C_{i}\in C^{s}}|C_{i}|}$

${\displaystyle C^{cand}:=\emptyset }$

${\displaystyle {\mathtt {para\,cada\,cluster}}\,cl\in C^{\mathtt {bestSubspace}}}$

${\displaystyle C^{cand}:=C^{cand}\cup {\mathtt {DBSCAN}}(cl,cand,eps,MinPts)}$

${\displaystyle {\mathtt {si}}\,(C^{cand}\neq \emptyset )}$

${\displaystyle S_{k+1}:=S_{k+1}\cup cand}$

${\displaystyle C_{k+1}:=C_{k+1}\cup C^{cand}}$

${\displaystyle {\mathtt {end\,if}}}$

${\displaystyle {\mathtt {fin\,para}}}$

${\displaystyle {\mathtt {fin\,para}}}$

${\displaystyle k:=k+1\!\,}$

${\displaystyle {\mathtt {fin\,mientras}}}$

${\displaystyle {\mathtt {end}}\!\,}$

El conjunto${\displaystyle S_{k}}$contiene todo el${\displaystyle k}$Subespacios de dimensión que se sabe que contienen cúmulos. El conjunto${\displaystyle C_{k}}$contiene los conjuntos de clústeres encontrados en los subespacios.${\displaystyle bestSubspace}$Se elige para minimizar las ejecuciones de DBSCAN (y el número de puntos que deben considerarse en cada ejecución) para encontrar los clústeres en los subespacios candidatos.

Los subespacios candidatos se generan de forma muy similar a como el algoritmo Apriori genera los candidatos a conjuntos de ítems frecuentes: pares de los${\displaystyle k}$Se comparan subespacios de dimensión y, si difieren en un solo atributo, forman un${\displaystyle k+1}$candidato de dimensión. Sin embargo, también se encuentran varios candidatos irrelevantes; contienen un${\displaystyle k}$Subespacio de dimensión que no contiene un clúster. Por lo tanto, estos candidatos se eliminan en un segundo paso:

${\displaystyle {\mathtt {GenerateCandidateSubspaces}}(S_{k})}$

${\displaystyle {\mathtt {CandS}}_{k+1}:=\emptyset }$

${\displaystyle {\mathtt {para\,cada}}\,s_{1}\in S_{k}}$

${\displaystyle {\mathtt {para\,cada}}\,s_{2}\in S_{k}}$

${\displaystyle {\mathtt {si}}\,(s_{1}\,{\mathtt {y}}\,s_{2}\,\,{\mathtt {difieren\,\,en\,exactamente\,\,un\,\,atributo}})}$

${\displaystyle {\mathtt {CandS}}_{k+1}:={\mathtt {CandS}}_{k+1}\cup \{s_{1}\cup s_{2}\}}$

${\displaystyle {\mathtt {end\,if}}}$

${\displaystyle {\mathtt {fin\,para}}}$

${\displaystyle {\mathtt {fin\,para}}}$

// Poda de subespacios candidatos irrelevantes

${\displaystyle {\mathtt {para\,cada}}\,cand\in {\mathtt {CandS}}_{k+1}}$

${\displaystyle {\mathtt {para\,cada}}\,k{\texttt {-elemento}}\,s\subset cand}$

${\displaystyle {\mathtt {si}}\,(s\not \in S_{k})}$

${\displaystyle {\mathtt {CandS}}_{k+1}={\mathtt {CandS}}_{k+1}\setminus \{cand\}}$

${\displaystyle {\mathtt {end\,if}}}$

${\displaystyle {\mathtt {fin\,para}}}$

${\displaystyle {\mathtt {fin\,para}}}$

${\displaystyle {\mathtt {end}}\,\!}$

En el marco de trabajo ELKI se encuentra disponible un ejemplo de implementación de SUBCLU .