Added README.md

[clueless-kmeans.git] / clusterer.cc

diff --git a/clusterer.cc b/clusterer.cc
index d4a70a6..965b7ba 100644 (file)
--- a/clusterer.cc
+++ b/clusterer.cc
@@ -1,17 +1,17 @@
 /*
- *  clueless-kmean is a variant of k-mean which enforces balanced
+ *  clueless-kmeans is a variant of k-means which enforces balanced
  *  distribution of classes in every cluster
  *
  *  Copyright (c) 2013 Idiap Research Institute, http://www.idiap.ch/
  *  Written by Francois Fleuret <francois.fleuret@idiap.ch>
  *
- *  This file is part of clueless-kmean.
+ *  This file is part of clueless-kmeans.
  *
- *  clueless-kmean is free software: you can redistribute it and/or
+ *  clueless-kmeans is free software: you can redistribute it and/or
  *  modify it under the terms of the GNU General Public License
  *  version 3 as published by the Free Software Foundation.
  *
- *  clueless-kmean is distributed in the hope that it will be useful,
+ *  clueless-kmeans is distributed in the hope that it will be useful,
  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  *  General Public License for more details.
@@ -154,7 +154,8 @@ scalar_t Clusterer::baseline_lp_cluster_association(int nb_points, scalar_t **po
 
 scalar_t Clusterer::uninformative_lp_cluster_association(int nb_points, scalar_t **points,
                                                          int nb_classes, int *labels,
-                                                         scalar_t **gamma)  {
+                                                         scalar_t **gamma,
+                                                         int absolute_proportion)  {
   // N points
   // K clusters
   // dist(n,k) distance of samples n to cluster k
@@ -170,8 +171,8 @@ scalar_t Clusterer::uninformative_lp_cluster_association(int nb_points, scalar_t
   // under
   //
   // (A) \forall n, k, \gamma(n, k) >= 0
-  // (B) \forall n, \sum_k \gamma(n,k) = 1
-  // (C) \forall k, \sum_n \gamma(n,k) = N/K
+  // (B) \forall n, \sum_k \gamma(n, k) = 1
+  // (C) \forall k, \sum_n \gamma(n, k) = N/K
 
   glp_prob *lp;
 
@@ -180,7 +181,13 @@ scalar_t Clusterer::uninformative_lp_cluster_association(int nb_points, scalar_t
 
   // ** GLPK USES INDEXES STARTING AT 1, NOT 0. **
 
-  int nb_coeffs = nb_points * _nb_clusters + nb_points * _nb_clusters;
+  int nb_coeffs;
+
+  if(absolute_proportion) {
+    nb_coeffs = nb_points * _nb_clusters + nb_points * _nb_clusters;
+  } else {
+    nb_coeffs = nb_points * _nb_clusters + nb_points * nb_classes * _nb_clusters;
+  }
 
   int *coeff_row = new int[nb_coeffs + 1];
   int *coeff_col = new int[nb_coeffs + 1];
@@ -253,16 +260,33 @@ scalar_t Clusterer::uninformative_lp_cluster_association(int nb_points, scalar_t
   // gammas for this cluster and this class is equal to the number of
   // sample of that class, divided by the number of clusters
 
-  for(int k = 1; k <= _nb_clusters; k++) {
-    for(int c = 1; c <= nb_classes; c++) {
-      int row = nb_points + (k - 1) * nb_classes + c;
-      scalar_t tau = nb_samples_per_class[c-1] / scalar_t(_nb_clusters);
-      glp_set_row_bnds(lp, row, GLP_FX, tau, tau);
-      for(int n = 1; n <= nb_points; n++) {
-        if(labels[n-1] == c - 1) {
+  if(absolute_proportion) {
+    for(int k = 1; k <= _nb_clusters; k++) {
+      for(int c = 1; c <= nb_classes; c++) {
+        int row = nb_points + (k - 1) * nb_classes + c;
+        scalar_t tau = nb_samples_per_class[c-1] / scalar_t(_nb_clusters);
+        glp_set_row_bnds(lp, row, GLP_FX, tau, tau);
+        for(int n = 1; n <= nb_points; n++) {
+          if(labels[n-1] == c - 1) {
+            coeff_row[n_coeff] = row;
+            coeff_col[n_coeff] = (k-1)  * nb_points + n;
+            coeff_wgt[n_coeff] = 1.0;
+            n_coeff++;
+          }
+        }
+      }
+    }
+  } else {
+    for(int k = 1; k <= _nb_clusters; k++) {
+      for(int c = 1; c <= nb_classes; c++) {
+        int row = nb_points + (k - 1) * nb_classes + c;
+        glp_set_row_bnds(lp, row, GLP_FX, 0.0, 0.0);
+        for(int n = 1; n <= nb_points; n++) {
           coeff_row[n_coeff] = row;
           coeff_col[n_coeff] = (k-1)  * nb_points + n;
-          coeff_wgt[n_coeff] = 1.0;
+          coeff_wgt[n_coeff] =
+            (labels[n-1] == c - 1 ? 1.0 : 0.0)
+            - scalar_t(nb_samples_per_class[c-1]) / scalar_t(nb_points);
           n_coeff++;
         }
       }
@@ -357,18 +381,23 @@ void Clusterer::train(int mode,
     switch(mode) {
 
     case STANDARD_ASSOCIATION:
-    total_distance =
-      baseline_cluster_association(nb_points, points, nb_classes, labels, gammas);
+      total_distance =
+        baseline_cluster_association(nb_points, points, nb_classes, labels, gammas);
       break;
 
     case STANDARD_LP_ASSOCIATION:
-    total_distance =
-      baseline_lp_cluster_association(nb_points, points, nb_classes, labels, gammas);
+      total_distance =
+        baseline_lp_cluster_association(nb_points, points, nb_classes, labels, gammas);
       break;
 
     case UNINFORMATIVE_LP_ASSOCIATION:
-    total_distance =
-      uninformative_lp_cluster_association(nb_points, points, nb_classes, labels, gammas);
+      total_distance =
+        uninformative_lp_cluster_association(nb_points, points, nb_classes, labels, gammas, 0);
+      break;
+
+    case UNINFORMATIVE_LP_ASSOCIATION_ABSOLUTE:
+      total_distance =
+        uninformative_lp_cluster_association(nb_points, points, nb_classes, labels, gammas, 1);
       break;
 
     default: