Trouver des appartenances partielles avec l'algorithme de clustering KMeans

Question

Je peux calculer l'appartenance à une grappe avec KMeans assez facilement :

open System
open System.IO
open Utils
open Accord
open Accord.Math 
open Accord.MachineLearning

let vals = [|
    [|1.0; 2.0; 3.0; 2.0|]
    [|1.1; 1.9; 3.1; 4.0|]
    [|2.0; 3.0; 4.0; 4.0|]    
    [|3.0; 3.1; 2.0; 3.0|]
    [|2.0; 4.0; 3.0; 6.0|]
    [|1.0; 5.0; 5.0; 7.0|]
    [|4.0; 3.0; 6.0; 8.0|]
    [|5.0; 4.0; 3.0; 6.0|]
    [|6.0; 4.0; 8.0; 7.0|]
    [|5.0; 6.0; 5.0; 9.0|]
    [|4.0; 2.0; 7.0; 8.0|]
    [|8.0; 9.0; 3.1; 2.2|]
    [|8.0; 9.0; 2.0; 2.0|]
    [|10.0; 2.0; 3.0; 2.0|]
    [|10.1; 1.9; 3.1; 4.0|]
    [|20.0; 3.0; 4.0; 4.0|]
    [|22.0; 7.0; 2.0; 3.0|]
    [|21.0; 4.0; 3.0; 6.0|]
|]

let kmeans = new KMeans 5
let clusterModel = kmeans.Learn vals
let clusters = clusterModel.Decide vals

Puis-je calculer l'appartenance partielle à l'aide de la norme KMeans algorithme ? Un collègue a suggéré d'utiliser la moyenne et la variance des membres de la grappe pour déterminer l'appartenance proportionnelle et aujourd'hui, je me suis penché sur les ensembles flous et leurs implémentations pour le traitement des données. F# . Par exemple, Voici de la documentation sur l'implémentation d'Accord.net pour les ensembles flous. Je peux traduire/exécuter l'exemple pour F# mais à première vue, je ne vois pas de moyen facile d'obtenir les données de mon Kmeans ci-dessus pour s'adapter au format d'attribution de l'affiliation partielle.

Questions :

1. Comment utiliser la moyenne/variance des membres d'une grappe pour calculer l'appartenance partielle ?

2. Existe-t-il un moyen simple de calculer l'appartenance partielle avec KMeans avec la bibliothèque Accord.net ?

3. L'algorithme KMeans d'Accord.net est simple à mettre en œuvre ; devrais-je passer du temps à essayer d'apprendre cette méthode de regroupement/appartenance pour l'adapter à mon problème plutôt que d'essayer de forcer le regroupement Kmeans à répondre à mes besoins ?

Answer 1

Vous devriez pouvoir utiliser Accord.NET pour obtenir les "centroïdes" des groupes que l'algorithme K-means trouve. Il s'agit essentiellement des centres des différents groupes. Vous devriez alors pouvoir calculer la distance entre votre nouveau point de données et chacun des centroïdes pour voir lesquels sont proches de votre point. (L'algorithme Decide ne renvoie que la première).

Je n'ai pas essayé, mais il semble que KMeans expose Clusters qui est un KMeansClusterCollection et dispose de la Centroids (voir les docs ). Il expose également le Distance qui renvoie la fonction de calcul de la distance entre les points de données.

À l'aide de ces derniers, vous devriez être en mesure de comparer la distance de votre point de données avec les centroïdes de toutes les grappes et de décider de la proximité du point par rapport aux grappes individuelles.

L'implémentation de k-means à partir de zéro n'est pas si difficile (il existe une méthode d'implémentation de k-means). bon article de Mathias Brandewinder à ce sujet), mais il semble qu'Accord.NET expose toutes les informations dont vous avez besoin dans ce cas particulier - c'est donc peut-être tout ce dont vous avez besoin (obtenir tous les détails corrects dans une implémentation personnalisée est toujours la partie la plus difficile...).

Answer 2

Comme l'a indiqué Tomas, Accord.NET fournit déjà de nombreux éléments de base. En particulier, l'appel à clusterModel.Scores vous donne les distances (négatives) par rapport aux centroïdes des clusters, voir le code source

À partir des distances négatives, vous pouvez calculer un score approximatif d'appartenance à une classe en prenant des exponentielles, comme vous le feriez pour calculer un PDF gaussien. En F#, cela ressemblerait à ce qui suit :

// Scores returns the negative distances between each point
// and the cluster centroid
let negDistances = clusterModel.Scores vals
// Compute an estimated cluster assigment score
let clusterMembership =
    negDistances
    |> Array.map (fun distances ->
        // Take the Exponential of the (negative) distances,
        // as in computing a Gaussian pdf
        let expDist = distances |> Array.map Math.Exp
        let total = Array.sum expDist
        expDist
        |> Array.map (fun d -> d/total)
    )

Il y a quelques mises en garde à ce sujet :

• Le modèle KMeans standard d'Accord utilise les distances euclidiennes, ce qui signifie que chaque direction a le même poids. Selon la nature de vos données, cela peut ne pas conduire à des résultats raisonnables (image 2 clusters, chacun ayant la forme d'un long cigare).
• Le calcul de l'appartenance à une classe ci-dessus ne prend pas non plus en compte la covariance des grappes. Pour être plus proche de la vérité, il faudrait calculer la distance de Bhattacharyya, exponentialiser, puis mettre à l'échelle par l'inverse de la matrice de covariance. Cette méthode échouera dans le cas de grappes uniques.

En ce qui concerne votre troisième question : Je ne réimplémenterais pas. Cela peut sembler facile au départ, mais il y a généralement beaucoup de cas particuliers et de problèmes de stabilité que l'on ne rencontre qu'après un certain temps.