From: Francois Fleuret <francois@fleuret.org>
Date: Wed, 3 Dec 2014 13:50:01 +0000 (+0100)
Subject: Added a new "non-absolute" criterion that enforces the proportions of classes in... 
X-Git-Url: https://www.fleuret.org/cgi-bin/gitweb/gitweb.cgi?p=clueless-kmeans.git;a=commitdiff_plain;h=0820b707fe47acf03faf6a7a23f22ac269e8d8de

Added a new "non-absolute" criterion that enforces the proportions of classes in each cluster.
---

diff --git a/clueless-kmeans.cc b/clueless-kmeans.cc
index 14e5b92..d71a3cf 100644
--- a/clueless-kmeans.cc
+++ b/clueless-kmeans.cc
@@ -83,12 +83,14 @@ int main(int argc, char **argv) {
       mode = Clusterer::STANDARD_LP_ASSOCIATION;
     } else if(strcmp(argv[1], "clueless") == 0) {
       mode = Clusterer::UNINFORMATIVE_LP_ASSOCIATION;
+    } else if(strcmp(argv[1], "clueless-absolute") == 0) {
+      mode = Clusterer::UNINFORMATIVE_LP_ASSOCIATION_ABSOLUTE;
     } else {
       cerr << "Unknown association mode " << argv[1] << endl;
       exit(EXIT_FAILURE);
     }
   } else {
-    cerr << "Usage: " << argv[0] << " standard|clueless" << endl;
+    cerr << "Usage: " << argv[0] << " standard|clueless|clueless-absolute" << endl;
     exit(EXIT_FAILURE);
   }
 
diff --git a/clusterer.cc b/clusterer.cc
index 5bf04aa..965b7ba 100644
--- a/clusterer.cc
+++ b/clusterer.cc
@@ -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:
diff --git a/clusterer.h b/clusterer.h
index 584828e..6fa5382 100644
--- a/clusterer.h
+++ b/clusterer.h
@@ -31,9 +31,16 @@ class Clusterer {
 public:
 
   enum {
+    // Standard k-mean
     STANDARD_ASSOCIATION,
+    // Same, implemented as a LP problem for sanity check
     STANDARD_LP_ASSOCIATION,
-    UNINFORMATIVE_LP_ASSOCIATION
+    // Criterion forcing to have the same distribution of classes in
+    // all clusters
+    UNINFORMATIVE_LP_ASSOCIATION,
+    // Criterion forcing to have the same number of samples of each
+    // class in all clusters
+    UNINFORMATIVE_LP_ASSOCIATION_ABSOLUTE
   };
 
   const static int max_nb_iterations = 10;
@@ -66,7 +73,8 @@ public:
 
   scalar_t uninformative_lp_cluster_association(int nb_points, scalar_t **points,
                                                 int nb_classes, int *labels,
-                                                scalar_t **gamma);
+                                                scalar_t **gamma,
+                                                int absolute_proportion);
 
   void update_clusters(int nb_points, scalar_t **points, scalar_t **gamma);
 
diff --git a/result-clueless-absolute.png b/result-clueless-absolute.png
new file mode 100644
index 0000000..9b53240
Binary files /dev/null and b/result-clueless-absolute.png differ
diff --git a/result-clueless.png b/result-clueless.png
index 9b53240..a879786 100644
Binary files a/result-clueless.png and b/result-clueless.png differ
diff --git a/test.sh b/test.sh
index a81b888..64b69ee 100755
--- a/test.sh
+++ b/test.sh
@@ -52,8 +52,14 @@ EOF
 
 make -j -k
 
+echo "Baseline k-mean"
 ./clueless-kmeans standard
 make_graph result-standard.png
 
+echo "Clueless k-mean"
 ./clueless-kmeans clueless
 make_graph result-clueless.png
+
+echo "Clueless-absolute k-mean"
+./clueless-kmeans clueless-absolute
+make_graph result-clueless-absolute.png