Changeset 1107

Timestamp:

Feb 19, 2008, 4:23:52 PM (16 years ago)

Author:

Markus Ringnér

Message:

Ticket #259 fixed for KNN

Location:

trunk

Files:

• test/knn_test.cc (modified) (3 diffs)
• yat/classifier/KNN.h (modified) (4 diffs)

trunk/test/knn_test.cc

@@ -23 +23 @@
 
 #include "yat/classifier/KNN.h"
+#include "yat/classifier/MatrixLookup.h"
 #include "yat/classifier/MatrixLookupWeighted.h"
 #include "yat/statistics/EuclideanDistance.h"
-#include "yat/statistics/PearsonDistance.h"
 #include "yat/utility/matrix.h"
 
@@ -38 +38 @@
 
 using namespace theplu::yat;
+
+double deviation(const utility::matrix& a, const utility::matrix& b) {
+  double sl=0;
+  for (size_t i=0; i<a.rows(); i++){
+    for (size_t j=0; j<a.columns(); j++){
+      sl += fabs(a(i,j)-b(i,j));
+    }
+  }
+  sl /= (a.columns()*a.rows());
+  return sl;
+}
 
 int main(const int argc,const char* argv[])
@@ -52 +63 @@
   *error << "testing knn" << std::endl;
   bool ok = true;
+
+  ////////////////////////////////////////////////////////////////
+  // A test of training and predictions using unweighted data
+  ////////////////////////////////////////////////////////////////
+  *error << "test of predictions using unweighted training and test data\n";
+  utility::matrix data1(3,4);
+  for(size_t i=0;i<3;i++) {
+    data1(i,0)=3-i;
+    data1(i,1)=5-i;
+    data1(i,2)=i+1;
+    data1(i,3)=i+3;
+  }
+  std::vector<std::string> vec1(4, "pos");
+  vec1[0]="neg";
+  vec1[1]="neg";
   
-  std::ifstream is("data/sorlie_centroid_data.txt");
-  utility::matrix data(is,'\t');
-  is.close();
+  classifier::MatrixLookup ml1(data1);
+  classifier::Target target1(vec1);
   
-  is.open("data/sorlie_centroid_classes.txt");
-  classifier::Target targets(is);
-  is.close();
+  classifier::KNN<statistics::EuclideanDistance> knn1(ml1,target1);
+  knn1.k(3);
+  knn1.train();
+  utility::matrix prediction1;
+  knn1.predict(ml1,prediction1);
+  double slack_bound=2e-7;
+  utility::matrix result1(2,4);
+  result1(0,0)=result1(0,1)=result1(1,2)=result1(1,3)=2.0/3.0;
+  result1(0,2)=result1(0,3)=result1(1,0)=result1(1,1)=1.0/3.0;
+  double slack = deviation(prediction1,result1); 
+  if (slack > slack_bound || std::isnan(slack)){
+    *error << "Difference to expected prediction too large\n";
+    *error << "slack: " << slack << std::endl;
+    *error << "expected less than " << slack_bound << std::endl;
+    ok = false;
+  }
+  
 
-  // Generate weight matrix with 0 for missing values and 1 for others.
-  utility::matrix weights(data.rows(),data.columns(),0.0);
-  utility::nan(data,weights);
+  ////////////////////////////////////////////////////////////////
+  // A test of training unweighted and test weighted
+  ////////////////////////////////////////////////////////////////
+  *error << "test of predictions using unweighted training and weighted test data\n";
+  utility::matrix weights1(3,4,1.0);
+  weights1(2,0)=0;
+  classifier::MatrixLookupWeighted mlw1(data1,weights1);
+  knn1.predict(mlw1,prediction1); 
+  result1(0,0)=1.0/3.0;
+  result1(1,0)=2.0/3.0;
+  slack = deviation(prediction1,result1);
+  if (slack > slack_bound || std::isnan(slack)){
+    *error << "Difference to expected prediction too large\n";
+    *error << "slack: " << slack << std::endl;
+    *error << "expected less than " << slack_bound << std::endl;
+    ok = false;
+  } 
 
-  classifier::MatrixLookupWeighted dataviewweighted(data,weights);
-  classifier::KNN<statistics::PearsonDistance> knn(dataviewweighted,targets);
-  *error << "training KNN" << std::endl;
-  knn.train();
-  
-  utility::matrix prediction;
-  knn.predict(dataviewweighted,prediction);
-  *error << prediction << std::endl;
-  
+  ////////////////////////////////////////////////////////////////
+  // A test of training and test both weighted
+  ////////////////////////////////////////////////////////////////
+  *error << "test of predictions using weighted training and test data\n";
+  weights1(0,1)=0;
+  utility::matrix weights2(3,4,1.0);
+  weights2(2,3)=0;
+  classifier::MatrixLookupWeighted mlw2(data1,weights2);
+  classifier::KNN<statistics::EuclideanDistance> knn2(mlw2,target1);
+  knn2.k(3);
+  knn2.train();
+  knn2.predict(mlw1,prediction1); 
+  result1(0,1)=1.0/3.0;
+  result1(1,1)=2.0/3.0;
+  slack = deviation(prediction1,result1);
+  if (slack > slack_bound || std::isnan(slack)){
+    *error << "Difference to expected prediction too large\n";
+    *error << "slack: " << slack << std::endl;
+    *error << "expected less than " << slack_bound << std::endl;
+    ok = false;
+  } 
+
+
   if(!ok) {
     *error << "knn_test failed" << std::endl;

trunk/yat/classifier/KNN.h

@@ -90 +90 @@
     
     ///
-    /// Train the classifier using the training data. Centroids are
-    /// calculated for each class.
+    /// Train the classifier using the training data. 
+    /// This function does nothing but is required by the interface.
     ///
     /// @return true if training succedeed.
@@ -99 +99 @@
     
     ///
-    /// Calculate the distance to each centroid for test samples
+    /// For each sample, calculate the number of neighbours for each
+    /// class.
+    ///
     ///
     void predict(const DataLookup2D&, utility::matrix&) const;
@@ -121 +123 @@
     ///
     utility::matrix* calculate_distances(const DataLookup2D&) const;
+    void calculate_unweighted(const MatrixLookup&,
+                              const MatrixLookup&,
+                              utility::matrix*) const;
+    void calculate_weighted(const MatrixLookupWeighted&,
+                            const MatrixLookupWeighted&,
+                            utility::matrix*) const;
   };
   
@@ -151 +159 @@
       new utility::matrix(data_.columns(),test.columns());
     
+    
     // unweighted test data
     if(const MatrixLookup* test_unweighted = 
        dynamic_cast<const MatrixLookup*>(&test)) {      
-      for(size_t i=0; i<data_.columns(); i++) {
-        for(size_t j=0; j<test.columns(); j++) {
-          classifier::DataLookup1D test(*test_unweighted,j,false);
-          classifier::DataLookup1D tmp(data_,i,false);
-          (*distances)(i,j) = distance_(tmp.begin(), tmp.end(), test.begin());
-          utility::yat_assert<std::runtime_error>(!std::isnan((*distances)(i,j)));
-        }
-      }
+      // unweighted training data
+      if(const MatrixLookup* training_unweighted = 
+         dynamic_cast<const MatrixLookup*>(&data_)) 
+        calculate_unweighted(*training_unweighted,*test_unweighted,distances);
+      // weighted training data
+      else if(const MatrixLookupWeighted* training_weighted = 
+              dynamic_cast<const MatrixLookupWeighted*>(&data_)) 
+        calculate_weighted(*training_weighted,MatrixLookupWeighted(*test_unweighted),
+                           distances);              
+      // Training data can not be of incorrect type
     }
     // weighted test data
+    else if (const MatrixLookupWeighted* test_weighted = 
+             dynamic_cast<const MatrixLookupWeighted*>(&test)) {      
+      // unweighted training data
+      if(const MatrixLookup* training_unweighted = 
+         dynamic_cast<const MatrixLookup*>(&data_)) {
+        calculate_weighted(MatrixLookupWeighted(*training_unweighted),
+                           *test_weighted,distances);
+      }
+      // weighted training data
+      else if(const MatrixLookupWeighted* training_weighted = 
+              dynamic_cast<const MatrixLookupWeighted*>(&data_)) 
+        calculate_weighted(*training_weighted,*test_weighted,distances);              
+      // Training data can not be of incorrect type
+    } 
     else {
-      const MatrixLookupWeighted* data_weighted = 
-        dynamic_cast<const MatrixLookupWeighted*>(&data_);
-      const MatrixLookupWeighted* test_weighted = 
-        dynamic_cast<const MatrixLookupWeighted*>(&test);               
-      if(data_weighted && test_weighted) {
-        for(size_t i=0; i<data_.columns(); i++) {
-          classifier::DataLookupWeighted1D training(*data_weighted,i,false);
-          for(size_t j=0; j<test.columns(); j++) {
-            classifier::DataLookupWeighted1D test(*test_weighted,j,false);
-            utility::yat_assert<std::runtime_error>(training.size()==test.size());
-            (*distances)(i,j) = distance_(training.begin(), training.end(),
-                                          test.begin());
-            utility::yat_assert<std::runtime_error>(!std::isnan((*distances)(i,j)));
-          }
-        }
-      }
-      else {
-        std::string str;
-        str = "Error in KNN::calculate_distances: Only support when training and test data both are either MatrixLookup or MatrixLookupWeighted";
-        throw std::runtime_error(str);
-      }
+      std::string str;
+      str = "Error in KNN::calculate_distances: test data has to be either MatrixLookup or MatrixLookupWeighted";
+      throw std::runtime_error(str);
     }
     return distances;
   }
+
+  template <typename Distance>
+  void  KNN<Distance>:: calculate_unweighted(const MatrixLookup& training,
+                                             const MatrixLookup& test,
+                                             utility::matrix* distances) const
+  {
+    for(size_t i=0; i<training.columns(); i++) {
+      classifier::DataLookup1D training1(training,i,false);
+      for(size_t j=0; j<test.columns(); j++) {
+        classifier::DataLookup1D test1(test,j,false);
+        (*distances)(i,j) = distance_(training1.begin(), training1.end(), test1.begin());
+        utility::yat_assert<std::runtime_error>(!std::isnan((*distances)(i,j)));
+      }
+    }
+  }
+  
+  template <typename Distance>
+  void  KNN<Distance>:: calculate_weighted(const MatrixLookupWeighted& training,
+                                           const MatrixLookupWeighted& test,
+                                           utility::matrix* distances) const
+  {
+    for(size_t i=0; i<training.columns(); i++) {
+      classifier::DataLookupWeighted1D training1(training,i,false);
+      for(size_t j=0; j<test.columns(); j++) {
+        classifier::DataLookupWeighted1D test1(test,j,false);
+        (*distances)(i,j) = distance_(training1.begin(), training1.end(), test1.begin());
+        utility::yat_assert<std::runtime_error>(!std::isnan((*distances)(i,j)));
+      }
+    }
+  }
+
   
   template <typename Distance>