DeepECT: El árbol de clústeres integrado en profundidad

Evaluamos nuestro método propuesto DeepECT en cuatro conjuntos de datos de aprendizaje profundo de uso común: MNIST, USPS, Fashion-MNIST y Reuters. La tabla 1 muestra las estadísticas de todos los conjuntos de datos utilizados en los experimentos. MNIST y USPS son conjuntos de datos de imágenes que contienen dígitos escritos a mano. El conjunto de datos Fashion-MNIST contiene imágenes de productos de moda, como imágenes de ropa, zapatos y bolsos. El conjunto de datos de Reuters contiene artículos de noticias en cuatro categorías principales, y usamos la misma representación que se describe en .

Configuración experimental

Centramos nuestros experimentos en la evaluación de nuestra nueva capa de clustering. Por lo tanto, nos abstenemos de utilizar arquitecturas de autoencoder más elaboradas. En su lugar, usamos el mismo diseño genérico de autoencoder completamente conectado para todos los experimentos, como se usa en . Como se mencionó anteriormente, esperamos que todos los métodos se beneficien por igual de arquitecturas más sofisticadas y específicas del dominio. Sin embargo, una arquitectura de autoencoder estándar es suficiente para mostrar la viabilidad de DeepECT en comparación con los competidores de referencia. Por lo tanto, utilizamos la misma arquitectura genérica de autoencoder, como se propone en y que también se utiliza con el propósito de agrupar el espacio embebido. El codificador de alimentación en esta arquitectura tiene las dimensiones d-500–500–2000–10, y la red de decodificadores tiene un diseño reflejado. Usamos activaciones ReLU y la pérdida de reconstrucción de error cuadrado medio de la Ec. (1).

Entrenamos previamente diez autoencodificadores para cada conjunto de datos y utilizamos estas mismas redes preentrenadas para todos los experimentos y métodos de comparación. El uso de estos autoencodificadores preentrenados garantiza que cada método tenga las mismas condiciones de inicio para el espacio incrustado y que las variaciones en la calidad de agrupación no se deriven simplemente de autoencodificadores cualitativamente diferentes. La configuración de pre-entrenamiento es similar a la descrita en . Entrenamos previamente a los autoencoders como autoencoders de eliminación de ruido con una tasa de corrupción del 20%. En primer lugar, realizamos un pre-entrenamiento en capas con abandono después de cada capa (con una tasa de 20%) y 20,000 pasos por capa. Luego, ajustamos toda la red para 50,000 pasos sin deserción. Utilizamos input corruption solo para la formación previa y no para la optimización real de DeepECT y sus métodos de referencia. Para todos los experimentos, usamos Adam (tasa de aprendizaje \({\hbox {}}=0.0001\), \(\beta _1 = 0.9, \beta _2 = 0.999\)) como algoritmo de optimización y un mini-lote de 256 muestras. Para la optimización combinada, entrenamos para 50.000 iteraciones adicionales para garantizar la convergencia.

Para DeepECT, nuestros experimentos iniciales con datos sintéticos mostraron que dividir el árbol cada 500 pasos de optimización produce resultados prometedores y tamaños de pasos más extendidos no aumentaron aún más el rendimiento. Por esta razón, mantenemos este horario sin ajustarlo para los experimentos en conjuntos de datos del mundo real. Lo mismo se aplica al umbral de poda mencionado en el art. 2.7. Para MNIST, Fashion-MNIST y USPS, cultivamos los árboles hasta que contienen veinte nodos de hojas. Para el conjunto de datos de Reuters, establecemos el número máximo de nodos hoja en doce porque tiene menos clústeres de verdad de tierra. De esta manera, tenemos dos y tres veces el número real de grupos. Consideramos que estos valores son suficientes para capturar las estructuras esenciales de los conjuntos de datos seleccionados para el propósito de este artículo. Usamos el mismo número de nodos hoja para los métodos de línea de base jerárquica.

Las gráficas muestran una muestra de dígitos MNIST originales y una versión aumentada aleatoriamente

Para los conjuntos de datos de imágenes, también experimentamos con la extensión de aumento DeepECT + Aug . Empezamos con el mismo pre-entrenados autoencoders como en los otros experimentos. Además, seguimos el mismo programa de optimización descrito anteriormente para los experimentos con las versiones no aumentadas de DeepECT. En cada iteración, utilizamos el mini-lote original y su contraparte aumentada para optimizar la función de pérdida en la ecualización. 9, en lugar de la pérdida no aumentada en la Ec. 6. Creamos la versión aumentada de cada imagen de un mini-lote, aplicando sobre la marcha una transformación afín aleatoria. La transformación afín rota aleatoriamente y corta la imagen en el rango de \ ( \ ) grados. Además, mueve el dígito aleatoriamente hasta dos píxeles en cualquier dirección. La Figura 5 muestra un ejemplo de este aumento para el MNIST.

Métodos de evaluación

Evaluamos la jerarquía de clústeres de DeepECT con la medida de pureza del dendrograma (DP) y pureza de la hoja (LP). Describimos ambos a continuación. Además, evaluamos el árbol de clústeres contra métodos de línea de base plana. Para ello, utilizamos la conocida información mutua normalizada (NMI) y la precisión de agrupamiento (ACC) . Los incluimos para que estén completos y para demostrar que DeepECT también es competitivo en escenarios en los que se espera una estructura de clústeres plana y se conoce el número real de clústeres en el conjunto de datos. Para determinar una partición de clúster k a partir de un árbol de clúster, utilizamos las asignaciones a los nodos k que eran nodos hoja después de las primeras divisiones \(k-1\).

Pureza del dendrograma

La medida de pureza del dendrograma se puede utilizar para evaluar el árbol de racimo contra una partición de verdad de tierra plana. Es la pureza esperada del subárbol dada por el nodo ancestro menos común para dos puntos de datos muestreados aleatoriamente de la misma clase. Es 1.0 si y solo si todos los puntos de datos pertenecientes a una clase en la verdad de tierra se asignan a algún subárbol puro, y se aproxima a 0 para árboles generados aleatoriamente.

La fórmula explícita se define en como:

donde \(C_1, \dots, C_K\) son los conjuntos de puntos de datos correspondientes a las clases de verdad del suelo, \({\text {lca}} (x,y)\) es el nodo antepasado menos común de x e y en el árbol del clúster, \({\text {dan}} (z)\) es el conjunto de puntos de datos asignados al nodo z en el árbol del clúster, \({\text {pur}} (S,T) = |S \cap T| / | S|\) es la medida de pureza, y \({\mathcal {P}} = \{(x ,y) \mid \ exists C \ in \{C_1, \dots, C_K\}: x, y \ in C \ wedge x \ ne y\}\) es el conjunto de todos los pares de puntos de datos que pertenecen a la misma clase. La pureza del dendrograma se puede calcular de manera eficiente y precisa en una recursión ascendente en el árbol de racimo.

Pureza de la hoja

Además de usar pureza de dendrograma, introducimos otra medida que llamamos pureza de la hoja (LP). Es la pureza media ponderada de los nodos hoja w. r. t. a la clase mayoritaria de los objetos asignados a un nodo hoja, dada por la fórmula:

donde \({{\mathcal {L}}} _{{\mathcal {D}}}\) es el conjunto de los conjuntos que contienen los datos de los puntos asignados a los nodos hoja.

La dependencia de la Altura de los árboles de las Medidas de pureza

La comparación del dendrograma y la pureza de las hojas de dos árboles en racimo solo es directamente posible si ambos árboles tienen el mismo número de nudos foliares. Sin embargo, los subarboles siempre se pueden colapsar en nodos de hojas para cumplir con este requisito. Por lo tanto, colapsamos los árboles de enlace de abajo hacia arriba de los métodos de línea de base, en el orden de enlace, comprimiendo subarboles en nodos de hojas hasta que tengamos el mismo número de pasos de fusión que los nodos divididos en los árboles de arriba hacia abajo de DeepECT y Bisecting-K-means. Este proceso garantiza que ambos métodos sean comparables con las medidas de evaluación jerárquicas.

Líneas de base de agrupamiento jerárquico

Como línea de base para evaluar las propiedades jerárquicas, agrupamos los datos incrustados con los algoritmos clásicos de agrupamiento jerárquico bisecting-k-means (AE + Bisecting), single-linkage (AE + Single) y complete-linkage (AE + Complete). Dado que ninguno de estos algoritmos clásicos puede optimizar el espacio embebido, también exploramos la simple idea de combinar el algoritmo de agrupamiento embebido plano IDEC con un enlace único y un enlace completo. IDEC es un método que combina la capa de agrupación de DEC con la pérdida de reconstrucción del autoencoder. En primer lugar, ejecutamos IDEC con el número de clústeres establecido en un valor mayor que el número esperado de clústeres, en nuestro caso, lo establecemos igual al número máximo de nodos hoja que usamos para DeepECT. A continuación, consideramos a estos centros de clústeres IDEC como representantes de los puntos de datos asignados e intentamos recuperar una estructura de clústeres jerárquicos realizando un enlace único y un enlace completo en los centros de clústeres (IDEC + Single e IDEC + Complete). Se propone una técnica similar para configuraciones clásicas no integradas con k-means en lugar de IDEC.

Líneas de base de clústeres planos

Como línea de base para evaluar el rendimiento de DeepECT en un entorno de clústeres planos, utilizamos k-means en los datos incrustados del autoencoder preentrenado (AE+k-means) y el IDEC . Si ignoramos las ventajas de arquitecturas de autoencoder más sofisticadas y específicas de dominio, IDEC es actualmente uno de los mejores métodos de agrupación en clústeres integrados. A diferencia de DeepECT, tenemos que establecer el número real de clústeres en la verdad de tierra durante la optimización para IDEC y k-means. Además, establecemos el hiperparámetro de IDEC para la pérdida de reconstrucción en 0.1 como se describe en .

Resultados generales

Los resultados generales-promediados sobre los diez autoencodificadores preentrenados-para la evaluación jerárquica utilizando medidas de pureza de dendrogramas y pureza de hojas para DeepECT y los algoritmos jerárquicos de línea de base se muestran en la Tabla 2. DeepECT produce constantemente árboles de racimo de alta calidad y es el algoritmo de mayor rendimiento por un amplio margen. También podemos ver que la extensión de aumento mejora aún más los resultados considerablemente para MNIST y USPS. Los resultados de DeepECT con y sin la extensión de aumento para el conjunto de datos Fashion-MNIST son similares porque los autores del conjunto de datos optaron por procesar previamente todas las imágenes de manera que cada elemento de moda tenga una representación normalizada. Los resultados de los métodos clásicos se pueden explicar por su incapacidad para mejorar la incrustación. Los valores de pureza de las hojas para DeepECT indican que el método es capaz de crear subpoblaciones homogéneas. Si comparamos los valores de pureza de las hojas de DeepECT y las variantes jerárquicas de enlace central IDEC + con los valores de pureza de las hojas de las otras líneas de base, podemos ver que la optimización combinada de la agrupación y el autoencoder—de ambos métodos—de hecho mejora la homogeneidad de las estructuras locales. Sin embargo, el enlace central IDEC + tampoco es capaz de extraer una estructura jerárquica coherente.

La tabla 3 muestra los resultados experimentales de los métodos de comparación de clusters planos basados en los mismos autoencoders preentrenados. Dado que utilizamos los mismos autoencoders preentrenados, podemos ver directamente la influencia del objetivo de agrupación respectivo. Tanto IDEC como DeepECT se benefician de la optimización combinada en comparación con k-means, que no puede optimizar la incrustación. En la tabla 4 se muestran los resultados de los métodos de agrupamiento más basados en centroides tomados de la publicación respectiva. Puede encontrar más detalles sobre estos métodos en la secta. 4. Podemos ver que DeepECT también funciona bien en comparación con estos métodos. Sin embargo, también podemos ver que la arquitectura de autoencoder influye considerablemente en el resultado de la agrupación en clústeres. Por ejemplo, DBC se diferencia de DEC solo por el uso de un autoencodificador convolucional, pero logra resultados superiores. Sin embargo, la arquitectura de autoencoder seleccionada es independiente de la capa de agrupación en clúster seleccionada.

Por supuesto, esta comparación de los objetivos de clústeres planos y DeepECT es injusta con este último, porque a los métodos competidores se les da el número real de clústeres durante la optimización, mientras que para DeepECT, solo usamos esta información durante la evaluación. Sin embargo, podemos ver que la versión ordinaria de DeepECT puede mantenerse al día con estos métodos en términos de medidas NMI y ACC en bruto y que la extensión de aumento DeepECT + Aug muestra mejoras sustanciales sobre los resultados de DeepECT, porque puede ignorar invariancias conocidas dentro de los datos. Estos resultados muestran que DeepECT también es competitivo en escenarios en los que se espera una estructura de clúster plana, pero no conoce el número de clústeres e inspecciona el árbol de clústeres recursivamente.

Evaluación detallada

En esta sección, echamos un vistazo más de cerca a los árboles de efectos profundos resultantes para los conjuntos de datos anteriores. Dado que los hallazgos del conjunto de datos del USPS son comparables a los del MNIST, ya que ambos representan dígitos escritos a mano, omitimos estos resultados por brevedad.

Resultados MNIST

Un vistazo más de cerca a los árboles de efectos profundos resultantes para el conjunto de datos MNIST muestra algunas propiedades interesantes de diferentes subpoblaciones dentro de los dígitos escritos a mano. En la Fig. 6 y se puede encontrar en la extensión ordinaria y aumentada de DeepECT. La pureza de nodo de los subárboles representados para el dígito 7 ‘ es del 98% y contiene casi todas las instancias de esta clase. Contiene dos nudos foliares. Un nodo hoja muestra sietes con una barra transversal pequeña como se escribe comúnmente en Europa, el otro nodo hoja muestra este dígito como se escribe más comúnmente en los EE. El segundo subárbol contiene casi todas las instancias del dígito ” 2 ” con una pureza del 97%. Este subárbol también contiene dos nodos de hojas, cada uno con características específicas. El primer nodo de hoja contiene instancias que son más rizadas y tienen un bucle distintivo en la parte inferior. El segundo nodo de hoja contiene una versión más “aerodinámica” de este dígito, que se parece al carácter “Z”. Los subárboles mostrados construyen una jerarquía natural para el dígito respectivo, y uno puede imaginar fácilmente que estos hallazgos pueden ser de interés para un investigador. Otras agrupaciones de dígitos que dependen de la forma también se pueden encontrar en las partes inferiores del árbol, por ejemplo, las versiones escritas de los dígitos ‘4’ y ‘9’ comparten muchas características. En consecuencia, a menudo se pueden encontrar agrupados como un subárbol que contiene solo estos dos tipos de dígitos.

Las parcelas muestran dos subárboles extraídos de subpoblaciones interesantes del conjunto de datos del MNIST encontrado por DeepECT. Estos son los dígitos siete (con y sin barra transversal central) y dos (una versión rizada y “aerodinámica”, que se parece más al carácter “Z”). Los dígitos mostrados se muestrean aleatoriamente

Resultados de Reuters

El conjunto de datos de Reuters contiene cuatro categorías superiores desequilibradas (etiquetas de primer nivel) con la siguiente distribución de clases: Cooperar/Industrial con el 44%, Gobierno/Social con el 24%, Mercados con el 24% y Economía con el 8%. Este conjunto de datos se explica con más detalle en . Las categorías para cada artículo de noticias fueron elegidas a mano y, por lo tanto, son en cierta medida subjetivas. Además, cada categoría superior tiene varias subcategorías superpuestas adicionales (etiquetas de segundo nivel)-y subcategorías (etiquetas de tercer nivel)—con más del 96% de los artículos pertenecientes a dos o más subcategorías. La tabla 5 muestra un resultado de DeepECT para este conjunto de datos. Podemos ver que las dos primeras divisiones separan la mayor parte del subárbol Gubernamental/Social que comienza en el nodo 3 y del subárbol de Mercados que comienza en las categorías del nodo 5 de las otras dos categorías. El subárbol Gobierno / Social luego se diferencia en temas de las subcategorías, como deportes, guerra y crimen, política interna e internacional. La categoría de mercados también se diferencia en diferentes aspectos de las subcategorías respectivas. Por ejemplo, los nodos hoja de las dos últimas filas se refieren a diferentes subcategorías de las subcategorías de los Mercados de productos básicos. Los nodos hoja en el medio están principalmente relacionados con la Economía Corporativa / Industrial y Económica. No están tan bien separados como los otros dos subárboles. Sin embargo, incluso allí, podemos encontrar nodos de hojas interesantes. Por ejemplo, el nodo de la séptima hoja (fila) de la parte superior comparte artículos de noticias etiquetados con las subcategorías Desempeño (de Corporativo/Industrial) y Desempeño Económico (de Economía) y parece razonable esperar palabras relacionadas para esas dos subcategorías.

Moda-Resultados MNIST

El diagrama muestra un árbol de clústeres para el conjunto de datos Fashion-MNIST. Cada nodo de hoja muestra objetos muestreados aleatoriamente asignados a él. Las etiquetas son interpretaciones de los autores. Las áreas de color resaltan los tres subarboles dominantes que representan tres tipos de objetos que se encuentran en el conjunto de datos: bolsos, ropa y zapatos

El Fashion-MNIST contiene diez clases diferentes de ropa, zapatos y bolsos, a saber, camiseta/top, pantalones, jersey, vestido, abrigo, sandalia, camisa, zapatilla, bolso y botín. Un árbol de conglomerados resultante de nuestro método se muestra en la Fig. 7. Los nodos hoja se representan como objetos muestreados aleatoriamente asignados a ellos. Las etiquetas de cada nodo son nuestra interpretación basada en los objetos asignados al nodo respectivo. Podemos ver que DeepECT encontró una jerarquía de aspecto completamente natural dentro de este conjunto de datos. Primero, las imágenes se dividen en tres categorías: ropa, zapatos y bolsos. Destacamos estos subarboles con áreas coloreadas. Dentro de cada sub-árbol, podemos encontrar jerarquías naturales. La categoría de bolsos distingue entre bolsos sin correa/asa visible, bolsos con asas pequeñas y bolsos con correa para el hombro. La verdad sobre el terreno no distingue entre estos tipos de bolsas y las asigna a todas a la misma clase. La categoría de ropa se divide primero en pantalones y ropa para la parte superior del cuerpo. Estos se dividen de nuevo en mangas cortas y largas. Aquí, la longitud de la manga debe verse en relación con la longitud total de la prenda respectiva, ya que cada artículo está normalizado para que aparezca del mismo tamaño dentro de la imagen, p. ej., los vestidos y las camisas parecen ser del mismo tamaño. La categoría de calzado también muestra algunas características interesantes. En primer lugar, se distinguen los zapatos más pequeños y los más grandes. Los zapatos más pequeños se dividen en sandalias y zapatillas de deporte. Los zapatos más grandes tienen suela plana, tacón pequeño o tacón alto. La construcción de la jerarquía basada en estas características se ejecuta en contra de las clases de verdad de zapatillas, sandalias y botines. Sin embargo, desde el punto de vista de la apariencia, es una jerarquía válida e informativa para los zapatos.

Aplicabilidad para tareas de predicción en MNIST

También evaluamos DeepECT en una tarea de predicción. Por lo tanto, mantenemos los autoencoders y el procedimiento de optimización de clústeres como se describió anteriormente. A diferencia de la evaluación experimental anterior, solo usamos las primeras 50.000 muestras (conjunto de entrenamiento) del conjunto de datos MNIST durante la optimización del árbol de clústeres. Después de la optimización, evaluamos el rendimiento del clúster del árbol de clústeres en los 20.000 puntos de datos restantes (conjunto de pruebas) que no se habían visto anteriormente.

En este experimento, obtenemos para el conjunto de prueba una pureza de dendrograma de \(0.73\pm 0,08\) y una pureza de hoja de \(0,85\pm 0,06\), que es una ligera caída en comparación con los valores de la Tabla 2. Sin embargo, el resultado es lo suficientemente robusto como para permitir predicciones de etiquetas limitadas de puntos de datos no vistos previamente directamente por el árbol de clústeres. Sin embargo, en la mayoría de los casos, entrenaríamos un clasificador basado en las estructuras de clúster encontradas. Lo mismo se aplica a la incrustación en sí, donde podemos utilizar, por ejemplo, la pérdida de autoencodificador supervisada para mejorar la incrustación encontrada.

Resumen de experimentos

En resumen, creemos que los experimentos mostrados en cuatro conjuntos de datos del mundo real muestran claramente la utilidad y eficacia del árbol de clústeres de DeepECT. Encontrar este tipo de estructuras y seleccionar el nivel de detalle a analizar hacen de DeepECT un método valioso para los científicos de datos.