Regroupement basé sur des scores de similitude

18

Supposons que nous avons un ensemble d'éléments E et une similitude ( non loin ) fonction SIM (ei, ej) entre deux éléments ei, ej ∈ E .

Comment pourrions-nous (efficacement) regrouper les éléments de E , en utilisant sim ?

k -moyen, par exemple, nécessite un k donné , Canopy Clustering nécessite deux valeurs de seuil. Et si nous ne voulons pas de tels paramètres prédéfinis?

Notez que sim n'est pas nécessairement une métrique (c'est-à-dire que l'inégalité du triangle peut ou peut ne pas tenir). De plus, peu importe si les clusters sont disjoints (partitions de E ).

clustering algorithms similarity vefthym
la source
2
Je me demande pourquoi vous avez souligné que vous n'avez pas de distance. Je ne suis pas un expert ici, mais je me demande s'il ne devrait pas être possible de convertir une telle similitude en distance, si nécessaire, essentiellement en considérant son inverse. Indépendamment de cela, je doute qu'il existe des algorithmes de clustering qui sont complètement exempts de paramètres, donc un réglage sera très probablement nécessaire dans tous les cas. Lorsque vous avez considéré k-Means, peut-on supposer que vous avez des propriétés à valeur réelle (en particulier, que vous pouvez prendre la "moyenne" de plusieurs éléments)?
Marco13
4
Vous n'avez pas besoin de connaître k pour effectuer k moyens. Vous pouvez regrouper avec k variable et vérifier la variance de cluster pour trouver l'optimal. Alternativement, vous pourriez penser à opter pour des modèles de mélange gaussiens ou d'autres processus de restauration comme des choses pour vous aider à vous regrouper.
cwharland
2
J'ai posé les questions pour une raison précise: si vous pouviez appliquer k-Means, mais que le seul problème était de trouver le "k" initial, alors vous pourriez envisager une en.wikipedia.org/wiki/Self-organizing_map comme alternative. Il a de belles propriétés et se comporte fondamentalement "similaire" à k-Means, mais ne nécessite pas la définition du "k" initial. Ce n'est probablement pas une solution prête à l'emploi, car elle a des paramètres de réglage supplémentaires (et la formation peut être coûteuse en calcul), mais vaut quand même le coup d'œil.
Marco13
2
Le choix initial de k influence les résultats du regroupement, mais vous pouvez définir une fonction de perte ou plus probablement une fonction de précision qui vous indique pour chaque valeur de k que vous utilisez pour regrouper, la similitude relative de tous les sujets de ce regroupement. Vous choisissez le k qui minimise la variance de cette similitude. GMM et d'autres processus dirichlet s'occupent assez bien du problème de non-connaissance-k. L'une des meilleures ressources que j'ai jamais vues à ce sujet est le didacticiel d'Edwin Chen .
cwharland
4
Juste une pensée: si votre score de similitude est normalisé à 1 , alors 1-sim(ei, ej) = Distance. Avec la métrique de distance, vous pouvez par exemple appliquer un clustering hiérarchique. En descendant de la racine, vous verrez à quel niveau de grappes de granularité aurait un sens pour votre problème particulier.
Olexandr Isayev

Réponses:

9

  1. Je pense qu'un certain nombre d'algorithmes de clustering qui utilisent normalement une métrique, ne reposent pas réellement sur les propriétés métriques (autres que la commutativité, mais je pense que vous auriez cela ici). Par exemple, DBSCAN utilise des voisinages epsilon autour d'un point; il n'y a rien là-dedans qui indique spécifiquement que l'inégalité du triangle est importante. Vous pouvez donc probablement utiliser DBSCAN, même si vous devrez peut-être faire une sorte d'index spatial non standard pour effectuer des recherches efficaces dans votre cas. Votre version d'Epsilon-quartier sera probablement sim> 1 / epsilon plutôt que l'inverse. Même histoire avec k-means et les algorithmes associés.

  2. Pouvez-vous construire une métrique à partir de votre similitude? Une possibilité: dist (ei, ej) = min (sim (ei, ek) + sim (ek, ej)) pour tous les k ... Alternativement, pouvez-vous fournir une borne supérieure telle que sim (ei, ej) <sim (ei, ek) + sim (ek, ej) + d, pour tout k et une constante positive d? Intuitivement, de grandes valeurs de simulation signifient un rapprochement: la simulation 1 / sim est-elle de type métrique? Et 1 / (sim + constant)? Qu'en est-il de min (1 / sim (ei, ek) + 1 / sim (ek, ej)) pour tous les k? (ce dernier est garanti être une métrique, btw)

  3. Une construction alternative d'une métrique consiste à effectuer une incorporation. Dans un premier temps, vous pouvez essayer de mapper vos points ei -> xi, de telle sorte que xi minimise la somme (abs (sim (ei, ej) - f (dist (xi, xj))), pour une fonction appropriée f et métrique dist. La fonction f convertit la distance dans l'incorporation en une valeur similaire à la similitude; vous devrez expérimenter un peu, mais 1 / dist ou exp ^ -dist sont de bons points de départ. Vous devrez également expérimenter sur le meilleur dimension pour xi. À partir de là, vous pouvez utiliser le clustering conventionnel sur xi. L'idée ici est que vous pouvez presque (dans le meilleur des cas) convertir vos distances dans l'incorporation en valeurs de similarité, afin qu'elles se regroupent correctement.

  4. Sur l'utilisation de paramètres prédéfinis, tous les algorithmes ont un certain réglage. DBSCAN peut trouver le nombre de clusters, mais vous devez quand même lui donner quelques paramètres. En général, le réglage nécessite plusieurs exécutions de l'algorithme avec des valeurs différentes pour les paramètres réglables, ainsi qu'une fonction qui évalue la qualité du clustering (soit calculée séparément, fournie par l'algorithme de clustering lui-même, soit simplement oculaire :) Si le caractère de vos données ne changent pas, vous pouvez régler une fois puis utiliser ces paramètres fixes; s'il change, vous devez régler pour chaque exécution. Vous pouvez le découvrir en ajustant pour chaque exécution, puis en comparant la façon dont les paramètres d'une exécution fonctionnent sur une autre, par rapport aux paramètres spécialement ajustés pour cela.

Alex I
la source
8

Alex a fait un certain nombre de bons points, bien que je devrais peut-être revenir un peu sur son implication selon laquelle DBSCAN est le meilleur algorithme de clustering à utiliser ici. Selon votre implémentation, et si vous utilisez ou non des indices accélérés (de nombreuses implémentations ne le font pas), votre complexité en temps et en espace sera O(n2), ce qui est loin d'être idéal.

Personnellement, mes algorithmes de clustering go-to sont OpenOrd pour le clustering gagnant-prend-tout et FLAME pour le clustering flou. Les deux méthodes sont indifférentes à savoir si les métriques utilisées sont la similitude ou la distance (FLAME en particulier est presque identique dans les deux constructions). L'implémentation d'OpenOrd dans Gephi est O(nlogn)et est connue pour être plus évolutive que n'importe lequel des autres algorithmes de clustering présents dans le package Gephi.

FLAME, d'autre part, est idéal si vous recherchez une méthode de clustering floue. Bien que la complexité de FLAME soit un peu plus difficile à déterminer car il s'agit d'un processus itératif, il s'est avéré être sub-quadratique et similaire en termes de vitesse d'exécution à knn.

indico
la source
5

DBSCAN (voir aussi: DBSCAN généralisé) ne nécessite pas de distance. Tout ce dont il a besoin, c'est d'une décision binaire . Généralement, on utiliserait "distance <epsilon" mais rien ne dit que vous ne pouvez pas utiliser "similarité> epsilon" à la place. Les inégalités triangulaires, etc. ne sont pas nécessaires.

La propagation d'affinité, comme son nom l'indique, utilise des similitudes.

Le regroupement hiérarchique, à l'exception peut-être de la liaison Ward, ne fait aucune hypothèse. Dans de nombreuses implémentations, vous pouvez simplement utiliser des distances négatives lorsque vous avez des similitudes, et cela fonctionnera très bien. Parce que tout ce qui est nécessaire est min, max et <.

Le k-means du noyau pourrait fonctionner SI votre similitude est une bonne fonction du noyau. Considérez-le comme le calcul de k-moyennes dans un espace vectoriel différent, où la distance euclidienne correspond à votre fonction de similitude. Mais alors vous devez savoir k.

PAM (K-medoids) devrait fonctionner. Attribuez chaque objet au médoïde le plus similaire, puis choisissez l'objet ayant la similitude moyenne la plus élevée comme nouveau médoïde ... aucune inégalité de triangle nécessaire.

... et probablement beaucoup plus. Il existe littéralement des centaines d'algorithmes de clustering. La plupart devraient fonctionner à mon humble avis. Très peu semblent exiger des propriétés métriques. K-means a probablement les exigences les plus fortes: il minimise la variance (pas la distance ou la similitude), et vous devez être capable de calculer les moyennes.

Anony-Mousse -Reinstate Monica
la source
4

L'analyse des données topologiques est une méthode explicitement conçue pour le paramètre que vous décrivez. Plutôt qu'une métrique de distance globale, elle ne repose que sur une métrique locale de proximité ou de voisinage. Voir: Topologie et données et Extraire des informations de la forme de données complexes à l'aide de la topologie . Vous pouvez trouver des ressources supplémentaires sur le site Web d'Ayasdi.

MrMeritology
la source