Existe-t-il un algorithme de type arbre de décision pour le clustering non supervisé?

J'ai un ensemble de données composé de 5 fonctionnalités: A, B, C, D, E. Ce sont toutes des valeurs numériques. Au lieu de faire un clustering basé sur la densité, ce que je veux faire, c'est grouper les données d'une manière d'arbre de décision.

L'approche que je veux dire est quelque chose comme ceci:

L'algorithme peut diviser les données en X grappes initiales en fonction de la caractéristique C, c'est-à-dire que les grappes X peuvent avoir de petites valeurs C, moyennes C, grandes C et très grandes C, etc. Ensuite, sous chacun des nœuds de grappe X, l'algorithme divise davantage les données en grappes Y basées sur la caractéristique A. L'algorithme continue jusqu'à ce que toutes les fonctionnalités soient utilisées.

L'algorithme que j'ai décrit ci-dessus est comme un algorithme d'arbre de décision. Mais j'en ai besoin pour un clustering non supervisé, au lieu d'une classification supervisée.

Mes questions sont les suivantes:

1. De tels algorithmes existent-ils déjà? Quel est le nom correct pour un tel algorithme
2. Existe-t-il un package / bibliothèque R / python qui a une implémentation de ce type d'algorithmes?

Vous voudrez peut-être envisager l'approche suivante:

• Utilisez n'importe quel algorithme de clustering adapté à vos données
• Supposons que le cluster résultant soit des classes
• Former un arbre de décision sur les clusters

Cela vous permettra d'essayer différents algorithmes de clustering, mais vous obtiendrez une approximation de l'arbre de décision pour chacun d'eux.

Le premier article qui me vient à l'esprit est le suivant: Clustering Via Decision Tree Construction https://pdfs.semanticscholar.org/8996/148e8f0b34308e2d22f78ff89bf1f038d1d6.pdf

Comme un autre l'a mentionné, «hiérarchique» (de haut en bas) et «agglomération hiérarchique» (de bas en haut) sont toutes deux des techniques bien connues conçues à l'aide d'arbres pour effectuer des regroupements. Scipy a ça.

Si vous êtes d'accord avec le code personnalisé parce que je ne connais aucune bibliothèque, il y a deux techniques que je peux recommander. Soyez averti que ceux-ci ne sont pas techniquement en cluster en raison de la mécanique sur laquelle ils s'appuient. Vous pourriez appeler ce pseudo clustering.

1) Supervisé: Ceci est quelque peu similaire à l'article (mérite d'être lu). Construisez un modèle d'arbre de décision unique pour apprendre une cible (vous décidez ce qui a du sens). La cible peut être une colonne générée aléatoirement (nécessite de répéter et d'évaluer quelle itération était la meilleure, voir ci-dessous). Définissez chaque chemin complet de l'arborescence comme un "cluster" car les points qui tombent à travers cette série de branches sont techniquement similaires en ce qui concerne la cible. Cela ne fonctionne bien que sur certains problèmes, mais il est efficace à grande échelle. Vous vous retrouvez avec K clusters (voir ci-dessous).

2) Semi-supervisé (sorte de non supervisé, mais supervisé mécaniquement), en utilisant # 1: vous pouvez essayer de construire des arbres pour prédire les colonnes dans un modèle de sortie. c'est-à-dire si le schéma est [A, B, C], construisez 3 modèles [A, B] -> C, [A, C] -> B, [B, C] -> A. Vous obtenez des clusters KN (voir ci-dessous). N = len (schéma). Si certaines de ces fonctionnalités ne sont pas intéressantes ou trop déséquilibrées (dans le cas des catégories), ne les utilisez pas comme cibles.

Résumé: Le modèle sélectionnera les fonctionnalités dans l'ordre en fonction des informations ou de la pureté et les clusters seront basés sur quelques fonctionnalités plutôt que sur toutes. Il n'y a pas de concept de distance dans ces grappes, mais vous pourriez certainement en concevoir une basée sur les centres.

Avantages: facile à comprendre et à expliquer, formation et inférence rapides, fonctionne bien avec quelques fonctionnalités puissantes, fonctionne avec les catégories. Lorsque vos fonctionnalités sont essentiellement hétérogènes et que vous disposez de nombreuses fonctionnalités, vous n'avez pas à passer autant de temps à décider lequel utiliser dans la fonction de distance.

Inconvénients: non standard, doit être écrit, biais naïf, la colinéarité avec la cible provoque de mauvais résultats, avoir 1000 caractéristiques tout aussi importantes ne fonctionnera pas bien (KMeans avec une distance euclidienne est mieux ici).

Combien de clusters obtenez-vous? Vous devez, vous devez absolument limiter le modèle DT pour ne pas trop grandir. Par exemple, définir des échantillons minimum par feuille, des nœuds foliaires maximum (préféré) ou la profondeur maximale. Vous pouvez éventuellement définir des contraintes de pureté ou d'entropie. Vous devez vérifier le nombre de clusters que cela vous a donné et évaluer si cette méthode est meilleure qu'un clustering réel.

Les techniques et les paramètres ont-ils bien fonctionné pour vous? Quel était le meilleur? Pour le savoir, vous devez effectuer une évaluation de cluster: des mesures de performance pour évaluer l'apprentissage non supervisé

Ce que vous recherchez est un algorithme de clustering diviseur.

Les algorithmes les plus courants sont agglomérés, qui regroupent les données de manière ascendante - chaque observation commence lorsque son propre cluster et les clusters fusionnent. Le regroupement diviseur est de haut en bas - les observations commencent dans un cluster qui est progressivement divisé.

Le désir de ressembler à un arbre de décision limite les choix car la plupart des algorithmes opèrent sur des distances dans l'espace de données complet plutôt que de diviser une variable à la fois.

DIANA est le seul algorithme de clustering diviseur que je connaisse, et je pense qu'il est structuré comme un arbre de décision. Je serais étonné qu'il n'y en ait pas d'autres.

Vous pouvez utiliser un algorithme d'arbre de décision standard si vous modifiez la règle de fractionnement en une métrique qui ne prend pas en compte une variable dépendante définie, mais utilise plutôt une métrique de qualité du cluster.

Une idée à considérer est de supposer que vous avez k caractéristiques et n points. Vous pouvez créer des arbres aléatoires en utilisant la fonction (k-1) et 1 fonction comme variable dépendante. Y. Vous pouvez sélectionner une hauteur h après laquelle vous aurez des points de données dans les racines. Vous pouvez prendre différents types d'arbres avec droit de vote. Juste une pensée.