DeepECT: L’arbre de cluster Deep Embedded

Nous évaluons notre méthode proposée DeepECT sur quatre ensembles de données d’apprentissage profond couramment utilisés: MNIST, USPS, Fashion-MNIST et Reuters. Le tableau 1 montre les statistiques de tous les ensembles de données utilisés dans les expériences. MNIST et USPS sont tous deux des ensembles de données d’images contenant des chiffres manuscrits. L’ensemble de données Fashion-MNIST contient des images de produits de mode, tels que des images de vêtements, de chaussures et de sacs. L’ensemble de données Reuters contient des articles de presse dans quatre catégories principales, et nous utilisons la même représentation que celle décrite dans.

Configuration expérimentale

Nous concentrons nos expériences sur l’évaluation de notre nouvelle couche de clustering. Par conséquent, nous nous abstenons d’utiliser des architectures d’autoencodeur plus élaborées. Au lieu de cela, nous utilisons la même disposition générique d’autoencodeur entièrement connecté pour toutes les expériences, telle qu’utilisée dans. Comme mentionné précédemment, nous nous attendons à ce que toutes les méthodes bénéficient également d’architectures plus sophistiquées et spécifiques à un domaine. Cependant, une architecture d’autoencodeur standard est suffisante pour montrer la viabilité de DeepECT par rapport aux concurrents de base. Par conséquent, nous utilisons la même architecture d’autoencodeur générique, telle que proposée dans et qui a également été utilisée dans le but de regrouper l’espace intégré. Le codeur de feedforward dans cette architecture a les dimensions d-500–500–2000–10 , et le réseau de décodeur a une disposition en miroir. Nous utilisons les activations ReLU et la perte de reconstruction d’erreur quadratique moyenne de Eq. (1).

Nous pré-entraînons dix auto-codeurs pour chaque jeu de données et utilisons ces mêmes réseaux pré-entraînés pour toutes les expériences et méthodes de comparaison. L’utilisation de ces autoencodeurs pré-entraînés garantit que chaque méthode a les mêmes conditions de démarrage pour l’espace intégré et que les variations de la qualité du clustering ne proviennent pas uniquement d’autoencodeurs qualitativement différents. La configuration de pré-formation est similaire à celle décrite dans . Nous pré-entraînons les autoencodeurs en tant qu’autoencodeurs débruitants avec un taux de corruption de 20%. Tout d’abord, nous effectuons un pré-entraînement par couche avec abandon après chaque couche (avec un taux de 20%) et 20 000 étapes par couche. Ensuite, nous peaufinons l’ensemble du réseau pour 50 000 étapes sans abandon. Nous utilisons la corruption d’entrée uniquement pour la pré-formation et non pour l’optimisation réelle de DeepECT et de ses méthodes de base. Pour toutes les expériences, nous utilisons Adam(learning\({\hbox{rate}}=0.0001\), \(\ beta _1 = 0,9, \beta _2 = 0,999\)) comme algorithme d’optimisation et une taille de mini-lot de 256 échantillons. Pour l’optimisation combinée, nous nous entraînons pour 50 000 itérations supplémentaires afin d’assurer la convergence.

Pour DeepECT, nos premières expériences avec des données synthétiques ont montré que le fractionnement de l’arbre toutes les 500 étapes d’optimisation donnait des résultats prometteurs et que des tailles de pas plus étendues n’augmentaient pas davantage les performances. Pour cette raison, nous conservons ce calendrier sans l’ajuster pour les expériences sur des ensembles de données du monde réel. Il en va de même pour le seuil d’élagage mentionné à la secte. 2.7. Pour MNIST, Fashion-MNIST et USPS, nous cultivons les arbres jusqu’à ce qu’ils contiennent vingt nœuds foliaires. Pour l’ensemble de données Reuters, nous avons défini le nombre maximal de nœuds feuilles à douze car il contient moins de clusters de vérité au sol. De cette façon, nous avons deux fois et trois fois le nombre réel de clusters. Nous considérons ces valeurs suffisantes pour saisir les structures essentielles des ensembles de données sélectionnés aux fins du présent article. Nous utilisons le même nombre de nœuds feuilles pour les méthodes de base hiérarchiques.

Les graphiques montrent un échantillon de chiffres MNIST originaux et une version augmentée aléatoirement

Pour les jeux de données d’images, nous avons également expérimenté l’extension d’augmentation DeepECT + Aug. Nous commençons avec les mêmes autoencodeurs pré-entraînés que dans les autres expériences. De plus, nous nous en tenons au même calendrier d’optimisation que décrit ci-dessus pour les expériences avec les versions non augmentées de DeepECT. À chaque itération, nous utilisons le mini-lot d’origine et son homologue augmenté pour optimiser la fonction de perte en égalisation. 9, au lieu de la perte non augmentée dans Eq. 6. Nous créons la version augmentée de chaque image d’un mini-lot, en appliquant à la volée une transformation affine aléatoire. La transformation affine tourne aléatoirement et cisaille l’image dans la plage de \(\) degrés. En outre, il déplace le chiffre de manière aléatoire jusqu’à deux pixels dans n’importe quelle direction. La figure 5 montre un exemple de cette augmentation pour MNIST.

Méthodes d’évaluation

Nous évaluons la hiérarchie des grappes de DeepECT avec la mesure de la pureté du dendrogramme (DP) et de la pureté des feuilles (LP). Nous décrivons les deux ci-dessous. De plus, nous évaluons l’arbre de cluster par rapport aux méthodes de base plate. Pour cela, nous utilisons les informations mutuelles normalisées (NMI) et la précision de clustering (ACC) bien connues. Nous les incluons pour être exhaustifs et pour montrer que DeepECT est également compétitif dans les scénarios, où l’on s’attend à une structure de cluster plate et connaît le nombre réel de clusters dans l’ensemble de données. Pour déterminer une partition de cluster k à partir d’une arborescence de cluster, nous utilisons les affectations aux k nœuds qui étaient des nœuds feuilles après les premières divisions \(k-1\).

Pureté du dendrogramme

La mesure de pureté du dendrogramme peut être utilisée pour évaluer l’arbre de grappes par rapport à une partition de vérité au sol plate. C’est la pureté attendue du sous-arbre donnée par le nœud ancêtre le moins commun pour deux points de données échantillonnés aléatoirement de la même classe. C’est 1.0 si et seulement si tous les points de données appartenant à une classe dans la vérité au sol sont affectés à un sous-arbre pur, et il s’approche de 0 pour les arbres générés aléatoirement.

La formule explicite est définie dans as:

où \(C_1, \dots, C_K\) sont les ensembles de points de données correspondant aux classes de vérité au sol, \({\text{lca}}(x,y)\) est le nœud ancêtre le moins commun de x et y dans l’arborescence du cluster, \({\text{dan}}(z)\) est l’ensemble de points de données attribués au nœud z dans l’arborescence du cluster, \({\text{pur}}(S, T) =|S\cap T///S/\) est la mesure de pureté, et \({\mathcal{P}} = \{(x, y)\mid\exists C\in\{C_1,\dots, C_K\}: x, y\in C\wedge x\ne y\}\) est l’ensemble de toutes les paires de points de données appartenant à la même classe. La pureté du dendrogramme peut être calculée efficacement et avec précision dans une récursivité ascendante sur l’arborescence du cluster.

Pureté des feuilles

En plus d’utiliser la pureté du dendrogramme, nous introduisons une autre mesure que nous appelons la pureté des feuilles (LP). C’est la pureté moyenne pondérée des nœuds feuilles par rapport à la classe majoritaire des objets affectés à un nœud feuille, donnée par la formule:

où \({{\mathcal{L}}} _{{\mathcal{D}}}\) est l’ensemble des ensembles contenant les points de données affectés aux nœuds feuilles.

Mesure de la pureté en fonction de la hauteur des arbres

La comparaison du dendrogramme et de la pureté des feuilles de deux arbres en grappes n’est directement possible que si les deux arbres ont le même nombre de nœuds foliaires. Cependant, les sous-arbres peuvent toujours être réduits en nœuds de feuilles pour répondre à cette exigence. Par conséquent, nous réduisons les arbres de liaison ascendants des méthodes de base – dans l’ordre de liaison – en compressant les sous—arbres en nœuds feuilles jusqu’à ce qu’il reste le même nombre d’étapes de fusion que les nœuds divisés dans les arbres descendants de DeepECT et Bissecting—K-means. Ce processus garantit que les deux méthodes sont comparables aux mesures d’évaluation hiérarchiques.

Lignes de base de Clustering hiérarchique

Comme référence pour évaluer les propriétés hiérarchiques, nous regroupons les données intégrées avec les algorithmes de clustering hiérarchique classiques bissecting-k-means (AE +Bissecting), single-linking (AE + Single) et complete-linking (AE +Complete). Étant donné qu’aucun de ces algorithmes classiques ne peut optimiser l’espace intégré, nous explorons également l’idée simple de combiner l’algorithme de clustering intégré plat IDEC avec une liaison unique et une liaison complète. IDEC est une méthode qui combine la couche de clustering de DEC avec la perte de reconstruction de l’autoencodeur. Tout d’abord, nous exécutons IDEC avec un nombre de clusters défini sur une valeur supérieure au nombre attendu de clusters — dans notre cas, nous le définissons égal au nombre maximal de nœuds feuilles que nous utilisons pour DeepECT. Ensuite, nous considérons ces centres de cluster IDEC comme des représentants des points de données assignés et essayons de récupérer une structure de cluster hiérarchique en effectuant une liaison unique et une liaison complète sur les centres de cluster (IDEC + Single et IDEC + Complete). Une technique similaire est proposée pour les paramètres classiques non intégrés avec k-means au lieu d’IDEC.

Lignes de base de clustering plat

En tant que ligne de base pour évaluer les performances de DeepECT dans un paramètre de clustering plat, nous utilisons k-means sur les données intégrées de l’autoencodeur pré-entraîné (AE + k-means) et IDEC. Si nous ignorons les avantages d’architectures d’autoencodeur plus spécifiques à un domaine et sophistiquées, IDEC est actuellement l’une des meilleures méthodes de clustering intégré. Contrairement à DeepECT, nous devons définir le nombre réel de clusters dans la vérité au sol lors de l’optimisation pour IDEC et k-means. De plus, nous définissons l’hyperparamètre d’IDEC pour la perte de reconstruction à 0,1 comme décrit dans.

Résultats généraux

Les résultats généraux — moyennés sur les dix autoencodeurs pré-entraînés – pour l’évaluation hiérarchique en utilisant des mesures de pureté de dendrogramme et de pureté de feuille pour DeepECT et les algorithmes de base hiérarchiques sont présentés dans le tableau 2. DeepECT produit systématiquement des arbres de grappes de haute qualité et est l’algorithme le plus performant par une large marge. Nous pouvons également voir que l’extension d’augmentation améliore encore considérablement les résultats pour MNIST et USPS. Les résultats de DeepECT avec et sans l’extension d’augmentation pour l’ensemble de données Fashion-MNIST sont similaires car les auteurs de l’ensemble de données ont choisi de pré-traiter toutes les images de sorte que chaque élément de mode ait une représentation normalisée. Les résultats des méthodes classiques peuvent s’expliquer par leur incapacité à améliorer l’intégration. Les valeurs de pureté des feuilles pour DeepECT indiquent que la méthode est capable de créer des sous-populations homogènes. Si nous comparons les valeurs de pureté des feuilles de DeepECT et les variantes hiérarchiques de liaison centrale IDEC + aux valeurs de pureté des feuilles des autres lignes de base, nous pouvons voir que l’optimisation combinée du clustering et de l’autoencodeur – des deux méthodes — améliore en effet l’homogénéité des structures locales. Cependant, la liaison centrale IDEC+ est également incapable d’extraire une structure hiérarchique cohérente.

Le tableau 3 montre les résultats expérimentaux pour les méthodes de comparaison de clusters plats basées sur les mêmes autoencodeurs pré-entraînés. Puisque nous utilisons les mêmes autoencodeurs pré-entraînés, nous pouvons voir directement l’influence de l’objectif de clustering respectif. IDEC et DeepECT bénéficient tous deux de l’optimisation combinée par rapport à k-means, qui ne peut pas optimiser l’intégration. Le tableau 4 montre les résultats de méthodes de regroupement plus centroïdes tirées de la publication respective. Plus de détails sur ces méthodes peuvent être trouvés dans la secte. 4. Nous pouvons voir que DeepECT fonctionne également bien par rapport à ces méthodes. Cependant, nous pouvons également voir que l’architecture d’autoencodeur influence considérablement le résultat du clustering. Par exemple, DBC ne diffère de DEC que par l’utilisation d’un autoencodeur convolutif, mais obtient des résultats supérieurs. Pourtant, l’architecture d’autoencodeur sélectionnée est indépendante de la couche de clustering sélectionnée.

Bien sûr, cette comparaison des objectifs de clusters plats et de DeepECT est injuste envers ces derniers, car les méthodes concurrentes reçoivent le nombre réel de clusters lors de l’optimisation, alors que pour DeepECT, nous n’utilisons ces informations que lors de l’évaluation. Néanmoins, nous pouvons voir que la version ordinaire de DeepECT peut suivre ces méthodes en termes de mesures NMI et ACC brutes et que l’extension d’augmentation DeepECT + Aug montre des améliorations substantielles par rapport aux résultats de DeepECT, car elle peut ignorer les invariances connues dans les données. Ces résultats montrent que DeepECT est également compétitif dans les scénarios, où l’on s’attend à une structure de cluster plate, mais ne connaît pas le nombre de clusters et inspecte l’arborescence de cluster de manière récursive.

Évaluation détaillée

Dans cette section, nous examinons de plus près les arbres de profondeur résultants pour les ensembles de données ci-dessus. Étant donné que les résultats de l’ensemble de données USPS sont comparables à ceux de MNIST — car les deux représentent des chiffres manuscrits — nous omettons ces résultats par souci de concision.

Résultats MNIST

Un examen plus approfondi des arbres DeepECT résultants pour l’ensemble de données MNIST montre certaines propriétés intéressantes de différentes sous-populations dans les chiffres manuscrits. Deux exemples illustratifs sont représentés à la Fig. 6 et peut être trouvé dans l’extension ordinaire et augmentée de DeepECT. La pureté des nœuds des sous-arbres représentés pour le chiffre 7′ est de 98% et contient presque toutes les instances de cette classe. Il contient deux nœuds foliaires. Un nœud feuille montre sept avec une petite barre transversale comme il est couramment écrit en Europe, l’autre nœud feuille montre ce chiffre comme il est plus couramment écrit aux États-Unis. Le deuxième sous-arbre contient presque toutes les instances du chiffre ‘2’ avec une pureté de 97%. Ce sous-arbre contient également deux nœuds foliaires, chacun avec des caractéristiques spécifiques. Le premier nœud feuille contient des instances qui sont plus bouclées et ont une boucle distinctive dans la partie inférieure. Le deuxième nœud feuille contient une version plus “simplifiée” de ce chiffre, ressemblant au caractère “Z”. Les sous-arbres représentés établissent une hiérarchie naturelle pour le chiffre respectif, et on peut facilement imaginer que ces résultats peuvent intéresser un chercheur. D’autres groupes de chiffres selon la forme peuvent également être trouvés dans les parties inférieures de l’arbre, par exemple, les versions écrites des chiffres ‘4’ et ‘9’ partagent de nombreuses caractéristiques. Par conséquent, ils peuvent souvent être regroupés sous la forme d’un sous-arbre contenant uniquement ces deux types de chiffres.

Les graphiques montrent deux sous-arbres extraits de sous-populations intéressantes de l’ensemble de données MNIST trouvé par DeepECT. Ce sont les chiffres sept (avec et sans barre transversale du milieu) et deux (une version bouclée et une version “simplifiée”, ressemblant davantage au caractère “Z”). Les chiffres affichés sont échantillonnés aléatoirement

Résultats Reuters

L’ensemble de données Reuters contient quatre catégories supérieures déséquilibrées (étiquettes de premier niveau) avec la répartition des classes suivante: Coopératif / Industriel avec 44%, Gouvernement / Social avec 24%, Marchés avec 24% et Économie avec 8%. Cet ensemble de données est expliqué plus en détail dans . Les catégories de chaque article d’actualité ont été choisies à la main et sont donc, dans une certaine mesure, subjectives. En outre, chaque catégorie supérieure comporte plusieurs sous-catégories supplémentaires qui se chevauchent (étiquettes de deuxième niveau) – et sous—sous-catégories (étiquettes de troisième niveau) – avec plus de 96% des articles appartenant à deux sous-catégories ou plus. Le tableau 5 présente un résultat DeepECT pour cet ensemble de données. Nous pouvons voir que les deux premières divisions séparent la majeure partie de la sous—arborescence Gouvernementale / sociale à partir du nœud 3 et de la sous-arborescence des marchés à partir du nœud 5 des deux autres catégories. Le sous-arbre gouvernemental / social se différencie ensuite davantage en sujets des sous-catégories tels que les sports, la guerre et le crime, la politique intérieure et internationale. La catégorie des marchés se différencie également en différents aspects des sous-catégories respectives. Par exemple, les nœuds feuilles des deux dernières lignes concernent différentes sous-sous-catégories des marchés de produits de base de la sous-catégorie. Les nœuds foliaires au milieu sont principalement liés à l’Entreprise / à l’industrie et à l’économie. Ils ne sont pas aussi bien séparés que les deux autres sous-arbres. Pourtant, même là, nous pouvons trouver des nœuds de feuilles intéressants. Par exemple, le septième nœud feuille (ligne) du haut partage des articles de presse étiquetés avec les sous-catégories Performance (de l’Entreprise / Industrielle) et Performance économique (de l’Économie) et il semble raisonnable de s’attendre à des mots connexes pour ces deux sous-sous-catégories.

Résultats Mode – MNIST

Le diagramme montre une arborescence de cluster pour l’ensemble de données Fashion-MNIST. Chaque nœud feuille montre des objets échantillonnés aléatoirement qui lui sont affectés. Les étiquettes sont des interprétations des auteurs. Les zones colorées mettent en évidence les trois sous-arbres dominants représentant trois types d’objets trouvés dans l’ensemble de données : sacs, vêtements et chaussures

Le créateur de mode contient dix classes différentes de vêtements, chaussures et sacs, à savoir T-shirt / haut, pantalon, pull, robe, manteau, sandale, chemise, sneaker, sac et bottine. Un arbre de cluster résultant de notre méthode est illustré à la Fig. 7. Les nœuds feuilles sont représentés comme des objets échantillonnés aléatoirement qui lui sont affectés. Les étiquettes de chaque nœud sont notre interprétation basée sur les objets assignés au nœud respectif. Nous pouvons voir que DeepECT a trouvé une hiérarchie entièrement naturelle dans cet ensemble de données. Tout d’abord, les images sont divisées en trois catégories: vêtements, chaussures et sacs. Nous avons mis en évidence ces sous-arbres avec des zones colorées. Dans chaque sous-arbre, nous pouvons trouver des hiérarchies naturelles. La catégorie des sacs distingue les sacs sans sangle / poignée visible, les sacs avec de petites poignées et les sacs avec une bandoulière. La vérité du sol ne fait pas de distinction entre ces types de sacs et les attribue tous à la même classe. La catégorie des vêtements est d’abord divisée en pantalons et vêtements pour le haut du corps. Ceux-ci sont ensuite à nouveau divisés en manches courtes et longues. Ici, la longueur de la manche doit être vue par rapport à la longueur totale du vêtement respectif car chaque article est normalisé pour apparaître de la même taille dans l’image, i.e., les robes et les chemises semblent être de la même taille. La catégorie de chaussures présente également des caractéristiques intéressantes. Tout d’abord, les chaussures plus petites et plus grandes sont distinguées. Les chaussures plus petites sont ensuite divisées en sandales et baskets. Les chaussures les plus grandes ont soit une semelle plate, un petit talon, soit des talons hauts. Construire la hiérarchie basée sur ces caractéristiques va à l’encontre des classes de vérité au sol des baskets, des sandales et des bottines. Néanmoins, il s’agit — du point de vue de l’apparence — d’une hiérarchie valide et informative pour les chaussures.

Applicabilité pour les tâches de prédiction sur MNIST

Nous évaluons également DeepECT dans une tâche de prédiction. Ainsi, nous conservons les autoencodeurs et la procédure d’optimisation du clustering comme décrit ci-dessus. Contrairement à l’évaluation expérimentale ci-dessus, nous n’utilisons que les 50.000 premiers échantillons (jeu d’entraînement) du jeu de données MNIST lors de l’optimisation de l’arborescence du cluster. Après optimisation, nous évaluons les performances de clustering de l’arborescence du cluster sur les 20.000 points de données restants inédits (ensemble de tests).

Dans cette expérience, nous obtenons pour l’ensemble de test une pureté de dendrogramme de \(0.73\pm 0,08\) et une pureté de feuille de \ (0,85\pm 0,06\), ce qui représente une légère baisse par rapport aux valeurs du tableau 2. Néanmoins, le résultat est suffisamment robuste pour permettre des prédictions d’étiquettes limitées de points de données inédits directement par l’arborescence du cluster. Cependant, dans la plupart des cas, nous formerions un classificateur basé sur les structures de grappes trouvées. Il en va de même pour l’intégration elle-même, où nous pouvons utiliser, par exemple, la perte d’autoencodeur supervisée pour améliorer l’intégration trouvée.

Résumé des expériences

En résumé, nous pensons que les expériences présentées sur quatre ensembles de données du monde réel montrent clairement l’utilité et l’efficacité de l’arbre de cluster DeepECT. Trouver ce type de structures et sélectionner le niveau de détail à analyser font de DeepECT une méthode précieuse pour les data scientists.