BIC-Clustering-Kriterium berechnen (um Cluster nach K-Mitteln zu validieren)

9

Ich frage mich, ob es eine gute Möglichkeit gibt, das Clustering-Kriterium basierend auf der BIC-Formel für eine k-Mittelwert-Ausgabe in R zu berechnen. Ich bin etwas verwirrt darüber, wie ich diesen BIC berechnen soll, damit ich ihn mit anderen Clustering-Modellen vergleichen kann. Derzeit verwende ich die Implementierung des Statistikpakets von k-means.

UnivStudent
quelle
Beachten Sie, dass dieses Kriterium für die Verwendung mit k-Mitteln ausgelegt ist. Auf Clusterungen durch verschiedene Algorithmen erhalten, kann es (insbesondere für die Dichte basierten Clustering - Algorithmen) ungeeignet sein
Hat VERL - Anony-Mousse

Antworten:

6

Um den BIC für die kmeans-Ergebnisse zu berechnen, habe ich die folgenden Methoden getestet:

  1. Die folgende Formel stammt von: [ref2] Geben Sie hier die Bildbeschreibung ein

Der r-Code für die obige Formel lautet:

  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))
  }
#

Das Problem ist, wenn ich den obigen r-Code verwende, war der berechnete BIC monoton ansteigend. Was ist der Grund?

Geben Sie hier die Bildbeschreibung ein

[Ref2] Ramsey, SA, et al. (2008). "Aufdeckung eines Makrophagen-Transkriptionsprogramms durch Integration von Beweisen aus dem Scannen von Motiven und der Expressionsdynamik." PLoS Comput Biol 4 (3): e1000021.

  1. Ich habe die neue Formel von /programming/15839774/how-to-calculate-bic-for-k-means-clustering-in-r verwendet

    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))
    }
    

Diese Methode hat den niedrigsten BIC-Wert bei Cluster-Nummer 155 angegeben. Geben Sie hier die Bildbeschreibung ein

  1. Verwenden Sie die von @ttnphns bereitgestellte Methode, um den entsprechenden R-Code wie unten aufgeführt zu verwenden. Das Problem ist jedoch, was der Unterschied zwischen Vc und V ist. Und wie berechnet man die elementweise Multiplikation für zwei Vektoren unterschiedlicher Länge?

    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
quelle
1
Wahrscheinlich hast du etwas anderes gemacht. In meinem "Pseudocode" wurde angegeben, dass Vces sich um eine P x ​​K-Matrix handelt, Vdie eine Spalte war, die dann K-mal in die Matrix gleicher Größe propagiert wurde. Also (Punkt 4 in meiner Antwort) können Sie hinzufügen Vc+V. Nehmen Sie dann den Logarithmus, dividieren Sie durch 2 und berechnen Sie die Spaltensummen. Der resultierende Zeilenvektor multipliziert (Wert für Wert, dh elementweise) mit der Zeile Nc.
ttnphns
1
Ich habe meiner Antwort selbst Formeln hinzugefügt, damit Sie vergleichen und sagen können, ob Sie das tun oder nicht.
ttnphns
3

Ich verwende R nicht, aber hier ist ein Zeitplan, der Ihnen hoffentlich dabei helfen wird, den Wert von BIC- oder AIC-Clustering-Kriterien für eine bestimmte Clustering-Lösung zu berechnen.

Dieser Ansatz folgt den zweistufigen SPSS-Algorithmen (siehe die dortigen Formeln, beginnend mit Kapitel "Anzahl der Cluster", und wechseln Sie dann zu "Log-Likelihood-Abstand", wo ksi, die Log-Likelihood, definiert ist). Der BIC (oder AIC) wird basierend auf dem Log-Likelihood-Abstand berechnet. Ich zeige die folgende Berechnung nur für quantitative Daten (die im SPSS-Dokument angegebene Formel ist allgemeiner und enthält auch kategoriale Daten; ich diskutiere nur den "Teil" der quantitativen Daten):

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.

AIC- und BIC-Clustering-Kriterien werden nicht nur beim K-Mittel-Clustering verwendet. Sie können für jede Clustering-Methode nützlich sein, bei der die Dichte innerhalb des Clusters als Varianz innerhalb des Clusters behandelt wird. Da AIC und BIC für "übermäßige Parameter" zu bestrafen sind, bevorzugen sie eindeutig Lösungen mit weniger Clustern. "Weniger Cluster mehr voneinander getrennt" könnte ihr Motto sein.

Es kann verschiedene Versionen von BIC / AIC-Clustering-Kriterien geben. Die hier Vcgezeigte verwendet Varianzen innerhalb des Clusters als Hauptbegriff für die Log-Wahrscheinlichkeit. Eine andere Version, die möglicherweise besser für das k-means-Clustering geeignet ist, basiert die Log-Wahrscheinlichkeit möglicherweise auf den Quadratsummen innerhalb des Clusters .

Die PDF-Version desselben SPSS-Dokuments, auf das ich mich bezogen habe.

Und hier sind schließlich die Formeln selbst, die dem obigen Pseudocode und dem Dokument entsprechen; Es stammt aus der Beschreibung der Funktion (Makro), die ich für SPSS-Benutzer geschrieben habe. Wenn Sie Vorschläge zur Verbesserung der Formeln haben, schreiben Sie bitte einen Kommentar oder eine Antwort.

Geben Sie hier die Bildbeschreibung ein

ttnphns
quelle
ttnphns, danke für deine antwort. Ich frage mich, ob Sie dies in Bezug auf die Zielfunktion erklären könnten, die die Summe der Quadrate innerhalb des Clusters minimiert.
UnivStudent
σe2VcVc+VVcVc=0
Mein Kopf bläst und ich kann nicht herausfinden, wie ich dies verwenden kann, um meine agglomerative hierarchische Clusterbildung zu stoppen. Ich benutze es für das Problem der Verknüpfung von Dokumentenclustern
MonsterMMORPG
@Monster, Es gibt mehr als 100 verschiedene interne Clustering-Kriterien . BIC ist einer von ihnen. Sie führen das Clustering bis zum Ende durch, speichern Clusterlösungen und die Clustermitgliedschaftsvariable bei jedem Schritt. Speichern Sie nur in den letzten 10 oder 20 Schritten, da Sie wahrscheinlich nicht viele kleine Cluster möchten. Vergleichen Sie die Lösungen anhand eines Clustering-Kriteriums und wählen Sie 1-3 "beste" aus. Vergleichen Sie sie auf Interpretierbarkeit. Erledigt. Siehe ein Beispiel .
ttnphns
@ttnphns das Problem hier Ich kann kein echtes Datenbeispiel für diese so genannten 100+ internen Cluster-Validierungsmaterial finden. Alles, was ich finden kann, sind einige mathematische Gleichungen, die ich nicht verstehen kann. Dies lässt mich auch nicht glauben, dass diese Algorithmen in der Realität existieren: D
MonsterMMORPG