Calculer le critère de clustering BIC (pour valider les clusters après K-means)

9

Je me demande s'il existe un bon moyen de calculer le critère de clustering basé sur la formule BIC, pour une sortie k-means dans R? Je suis un peu confus quant à la façon de calculer ce BIC afin de pouvoir le comparer avec d'autres modèles de clustering. Actuellement, j'utilise l'implémentation du package de statistiques de k-means.

UnivStudent
la source
Notez que ce critère est conçu pour être utilisé avec des k-moyennes. Sur les regroupements obtenus par différents algorithmes, cela peut être inapproprié (en particulier pour les algorithmes de regroupement basés sur la densité)
Has QUIT - Anony-Mousse

Réponses:

6

Pour calculer le BIC pour les résultats kmeans, j'ai testé les méthodes suivantes:

  1. La formule suivante est issue de: [ref2] entrez la description de l'image ici

Le code r pour la formule ci-dessus est:

  k3 <- kmeans(mt,3)
  intra.mean <- mean(k3$within)
  k10 <- kmeans(mt,10)
  centers <- k10$centers
  BIC <- function(mt,cls,intra.mean,centers){
    x.centers <- apply(centers,2,function(y){
      as.numeric(y)[cls]
    })
    sum1 <- sum(((mt-x.centers)/intra.mean)**2)
    sum1 + NCOL(mt)*length(unique(cls))*log(NROW(mt))
  }
#

le problème est que lorsque j'utilise le code r ci-dessus, le BIC calculé était en augmentation monotone. Quelle est la raison?

entrez la description de l'image ici

[ref2] Ramsey, SA et al. (2008). "Découvrir un programme de transcription des macrophages en intégrant les preuves de la numérisation des motifs et de la dynamique d'expression." PLoS Comput Biol 4 (3): e1000021.

  1. J'ai utilisé la nouvelle formule de /programming/15839774/how-to-calculate-bic-for-k-means-clustering-in-r

    BIC2 <- function(fit){
    m = ncol(fit$centers)
        n = length(fit$cluster)
    k = nrow(fit$centers)
        D = fit$tot.withinss
    return(data.frame(AIC = D + 2*m*k,
                      BIC = D + log(n)*m*k))
    }
    

Cette méthode a donné la valeur BIC la plus faible au cluster numéro 155. entrez la description de l'image ici

  1. en utilisant la méthode fournie @ttnphns, le code R correspondant comme indiqué ci-dessous. Cependant, le problème est quelle est la différence entre Vc et V? Et comment calculer la multiplication par élément pour deux vecteurs de longueur différente?

    BIC3 <- function(fit,mt){
    Nc <- as.matrix(as.numeric(table(fit$cluster)),nc=1)
    Vc <- apply(mt,2,function(x){
        tapply(x,fit$cluster,var)
     })
    V <- matrix(rep(apply(mt,2,function(x){
    var(x)
    }),length(Nc)),byrow=TRUE,nrow=length(Nc))
    LL = -Nc * colSums( log(Vc + V)/2 ) ##how to calculate this? elementa-wise multiplication for two vectors with different length?
    BIC = -2 * rowSums(LL) + 2*K*P * log(NRoW(mt))
    return(BIC)
    }
    
pengchy
la source
1
Vous faisiez probablement quelque chose de différent. Il a été indiqué dans mon "pseudocode" qui Vcest une matrice P x ​​K et Vétait une colonne puis se propageait K fois dans la même matrice de taille. Donc (point 4 dans ma réponse), vous pouvez ajouter Vc+V. Ensuite, prenez le logarithme, divisez par 2 et calculez les sommes des colonnes. Le vecteur ligne résultant se multiplie (valeur par valeur, c'est-à-dire élément par élément) par ligne Nc.
ttnphns
1
J'ai ajouté des formules elles-mêmes dans ma réponse, vous pouvez donc comparer et dire si ce que vous faites est ou non cela.
ttnphns
3

Je n'utilise pas R mais voici un calendrier qui, je l'espère, vous aidera à calculer la valeur des critères de clustering BIC ou AIC pour une solution de clustering donnée.

Cette approche suit les algorithmes SPSS Une analyse de cluster en deux étapes (voir les formules, à partir du chapitre "Nombre de clusters", puis passer à "Distance de vraisemblance log" où ksi, la log-vraisemblance, est définie). Le BIC (ou AIC) est calculé sur la base de la distance log-vraisemblance. Je montre ci-dessous le calcul pour les données quantitatives uniquement (la formule donnée dans le document SPSS est plus générale et incorpore également des données catégoriques; je ne parle que de sa "partie" de données quantitatives):

X is data matrix, N objects x P quantitative variables.
Y is column of length N designating cluster membership; clusters 1, 2,..., K.
1. Compute 1 x K row Nc showing number of objects in each cluster.
2. Compute P x K matrix Vc containing variances by clusters.
   Use denominator "n", not "n-1", to compute those, because there may be clusters with just one object.
3. Compute P x 1 column containing variances for the whole sample. Use "n-1" denominator.
   Then propagate the column to get P x K matrix V.
4. Compute log-likelihood LL, 1 x K row. LL = -Nc &* csum( ln(Vc + V)/2 ),
   where "&*" means usual, elementwise multiplication;
   "csum" means sum of elements within columns.
5. Compute BIC value. BIC = -2 * rsum(LL) + 2*K*P * ln(N),
   where "rsum" means sum of elements within row.
6. Also could compute AIC value. AIC = -2 * rsum(LL) + 4*K*P

Note: By default SPSS TwoStep cluster procedure standardizes all
quantitative variables, therefore V consists of just 1s, it is constant 1.
V serves simply as an insurance against ln(0) case.

Les critères de classification AIC et BIC ne sont pas utilisés uniquement avec la classification K-means. Ils peuvent être utiles pour toute méthode de clustering qui traite la densité intra-cluster comme une variance intra-cluster. Parce que AIC et BIC doivent pénaliser les "paramètres excessifs", ils ont tendance à préférer sans ambiguïté les solutions avec moins de clusters. "Moins de clusters plus dissociés les uns des autres" pourrait être leur devise.

Il peut exister différentes versions des critères de clustering BIC / AIC. Celui que j'ai montré ici utilise Vcles variances intra-grappes comme terme principal de la log-vraisemblance. Une autre version, peut-être mieux adaptée au clustering k-means, pourrait baser la vraisemblance logarithmique sur les sommes des carrés intra-cluster .

La version pdf du même document SPSS auquel j'ai fait référence.

Et voici enfin les formules elles-mêmes, correspondant au pseudocode ci-dessus et au document; il est tiré de la description de la fonction (macro) que j'ai écrite pour les utilisateurs SPSS. Si vous avez des suggestions pour améliorer les formules, veuillez poster un commentaire ou une réponse.

entrez la description de l'image ici

ttnphns
la source
ttnphns, merci pour votre réponse. Je me demande si vous pourriez expliquer cela par rapport à la fonction objectif qui minimise la somme des carrés intra-cluster?
UnivStudent du
Vous pouvez voir que la formule est presque la même que la seconde dans le wiki . Là, LL est basé sur la variance d'erreur qui est dans ma notation (la variance regroupée au sein du cluster). est utilisé au lieu de simplement contre le cas où un cluster a un objetσe2VcVc+VVcVc=0
ttnphns
ma tête souffle et je n'arrive pas à comprendre comment puis-je l'utiliser pour arrêter mon regroupement hiérarchique agglomératif. Je l'utilise pour un problème de liaison d'enregistrements de regroupement de documents
MonsterMMORPG
@Monster, Il existe plus de 100 critères de clustering [validation] internes différents . BIC en fait partie. Vous effectuez le clustering jusqu'à la fin, en enregistrant les solutions de cluster, la variable d'appartenance au cluster à chaque étape. Eh bien, économisez uniquement sur les 10 ou 20 dernières étapes, car vous ne voulez probablement pas beaucoup de petits clusters. Comparez les solutions selon un critère de regroupement et sélectionnez 1 à 3 «meilleures». Comparez-les pour leur interprétabilité. Terminé. Voir un exemple .
ttnphns
@ttnphns le problème ici, je ne trouve aucun exemple de données réelles de ces soi-disant 100+ trucs de validation de clustering interne. Tout ce que je peux trouver, ce sont des équations mathématiques que je ne peux pas comprendre. cela me fait aussi ne pas croire que ces algorithmes existent en réalité: D
MonsterMMORPG