Changeset 1142

Timestamp:

Feb 25, 2008, 3:32:35 PM (16 years ago)

Author:

Markus Ringnér

Message:

Refs #335, fixed for NCC, working on KNN

Location:

trunk

Files:

• test/knn_test.cc (modified) (4 diffs)
• test/ncc_test.cc (modified) (1 diff)
• yat/classifier/KNN.h (modified) (7 diffs)
• yat/classifier/KNN_ReciprocalDistance.h (modified) (1 diff)
• yat/classifier/KNN_ReciprocalRank.h (modified) (1 diff)
• yat/classifier/KNN_Uniform.cc (modified) (1 diff)
• yat/classifier/KNN_Uniform.h (modified) (1 diff)
• yat/classifier/NCC.h (modified) (3 diffs)

trunk/test/knn_test.cc

@@ -124 +124 @@
   ////////////////////////////////////////////////////////////////
   *error << "test of predictions using weighted training and test data\n";
+  *error << "... uniform neighbor weighting" << std::endl;
   weights1(0,1)=0;
   utility::Matrix weights2(3,4,1.0);
@@ -146 +147 @@
   // A test of reciprocal ranks weighting with training and test both weighted 
   ////////////////////////////////////////////////////////////////
+  *error << "... reciprokal rank neighbor weighting" << std::endl;
   utility::Matrix data2(data1);
   data2(1,3)=7;
@@ -166 +168 @@
   }
 
-
+  
   ////////////////////////////////////////////////////////////////
   // A test of reciprocal distance weighting with training and test both weighted 
   ////////////////////////////////////////////////////////////////
+  *error << "... reciprokal distance neighbor weighting" << std::endl;
   classifier::KNN<statistics::EuclideanDistance,classifier::KNN_ReciprocalDistance> 
     knn4(mlw2,target1);
@@ -175 +178 @@
   knn4.train();
   knn4.predict(mlw3,prediction1); 
-  slack = deviation(prediction1,result1); 
-  if (!std::isinf(prediction1(0,0)) && !std::isinf(prediction1(0,1)) && 
-      !std::isinf(prediction1(1,2)) && 
-      fabs(prediction1(1,3)-(1.0/3.67423461417))>slack_bound &&
-      fabs(prediction1(1,0)-(1.0/2.82842712475+1.0/2.44948974278))>slack_bound){
-    *error << "Difference to expected prediction too large\n";
-    ok = false;
-  }
+  if (!(std::isinf(prediction1(0,0)) && std::isinf(prediction1(0,1)) && 
+        std::isinf(prediction1(1,2)) && 
+        fabs(prediction1(1,3)-(1.0/3.67423461417))<slack_bound &&
+        fabs(prediction1(1,0)-(1.0/2.82842712475+1.0/2.44948974278))<slack_bound)){
+    *error << "Difference to expected prediction too large\n";
+    ok = false;
+  }
+
+
+  ////////////////////////////////////////////////////////////////
+  // A test of when a class has no training samples, should give nan
+  // in predictions. Also tests that k is reduced if not enough
+  // training samples.
+  ////////////////////////////////////////////////////////////////
+  //Keep only the second class in the training samples
+  std::vector<size_t> ind(2,2);
+  ind[1]=3;
+  classifier::Target target2(target1,utility::Index(ind));
+  classifier::MatrixLookupWeighted mlw4(data1,weights2,utility::Index(ind),false);
+  classifier::KNN<statistics::EuclideanDistance> knn5(mlw4,target2);
+  knn5.k(3);
+  knn5.train();
+  knn5.predict(mlw3,prediction1); 
+  if (!(std::isnan(prediction1(0,0)) && std::isnan(prediction1(0,1)) && 
+        std::isnan(prediction1(0,2)) && std::isnan(prediction1(0,3)) &&
+        fabs(prediction1(1,0)-2.0)<slack_bound &&
+        fabs(prediction1(1,1)-2.0)<slack_bound &&
+        fabs(prediction1(1,2)-2.0)<slack_bound &&
+        fabs(prediction1(1,3)-2.0)<slack_bound)) {
+    *error << "Difference to expected prediction too large\n";
+    ok = false;
+  }
+
+  ////////////////////////////////////////////////////////////////
+  // A test of when a test sample has no variables with non-zero
+  // weights in common with training samples: should give nan distance
+  ////////////////////////////////////////////////////////////////
+  *error << "test of predictions with nan distances\n";
+  weights1.all(1);
+  weights1(1,0)=weights1(1,1)=weights1(2,0)=weights1(2,1)=0.0;
+  weights2.all(1);
+  weights2(0,0)=0.0;
+  classifier::KNN<statistics::EuclideanDistance> knn6(mlw1,target1);
+  knn6.k(3);
+  knn6.train();
+  knn6.predict(mlw3,prediction1); 
+  // std::cout << "train:\n" << mlw1 << std::endl;
+  // std::cout << "test:\n" << mlw3 << std::endl;
+  // std::cout << "pred:\n" << prediction1 << std::endl;
+
 
   if(!ok) {

trunk/test/ncc_test.cc

@@ -159 +159 @@
 
   //////////////////////////////////////////////////////////////////////////
+  // A test of predictions when a centroid has nan for all variables that a
+  // test sample has non-zero weights for.
+  //////////////////////////////////////////////////////////////////////////
+  *error << "test of predictions using nan centroids and weighted test data\n";
+  *error << "... using EuclideanDistance" << std::endl;
+  weights1(0,0)=weights1(2,0)=0;
+  classifier::NCC<statistics::EuclideanDistance> ncc3(mlw2,target1);
+  ncc3.train();
+  ncc3.predict(mlw1,prediction1); 
+  if(!std::isnan(ncc3.centroids()(1,0))) {
+    ok=false;
+    *error << "Training failed: expected nan in centroid" << std::endl;
+  }
+  if(!(std::isnan(prediction1(0,0)) &&
+       fabs(prediction1(1,0)-sqrt(3.0))<slack_bound &&
+       fabs(prediction1(0,1)-sqrt(3.0))<slack_bound &&
+       fabs(prediction1(1,1)-sqrt(15.0))<slack_bound &&
+       fabs(prediction1(0,2)-sqrt(27.0))<slack_bound)) {  
+    ok=false; 
+    *error << "Test failed: predictions incorrect" << std::endl;
+  }
+  *error << "... using PearsonDistance" << std::endl;;
+  classifier::NCC<statistics::PearsonDistance> ncc4(mlw2,target1);
+  ncc4.train();
+  ncc4.predict(mlw1,prediction1); 
+  if(!std::isnan(ncc4.centroids()(1,0))) {
+    ok=false;
+    *error << "Training failed: expected nan in centroid" << std::endl;
+  }
+  if(!(std::isnan(prediction1(0,0)) &&
+       std::isnan(prediction1(0,2)) &&
+       std::isnan(prediction1(1,0)) &&
+       fabs(prediction1(0,1))<slack_bound &&
+       fabs(prediction1(1,2))<slack_bound &&
+       fabs(prediction1(1,3))<slack_bound &&  
+       fabs(prediction1(0,3)-2.0)<slack_bound &&
+       fabs(prediction1(1,1)-2.0)<slack_bound)) {
+    ok=false; 
+    *error << "Test failed: predictions incorrect" << std::endl;
+  }
+
+
+  //////////////////////////////////////////////////////////////////////////
   // A test of predictions using Sorlie data
   //////////////////////////////////////////////////////////////////////////

trunk/yat/classifier/KNN.h

@@ -85 +85 @@
 
     ///
-    /// @brief sets the number of neighbors, k.
-    ///
-    void k(u_int);
+    /// @brief sets the number of neighbors, k. If the number of
+    /// training samples set is smaller than \a k_in, k is set to the number of
+    /// training samples.
+    ///
+    void k(u_int k_in);
 
 
@@ -144 +146 @@
     : SupervisedClassifier(target), data_(data),k_(3)
   {
+    utility::yat_assert<std::runtime_error>
+      (data.columns()==target.size(),
+       "KNN::KNN called with different sizes of target and data");
+    // k has to be at most the number of training samples.
+    if(data_.columns()>k_) 
+      k_=data_.columns();
   }
 
@@ -152 +160 @@
     : SupervisedClassifier(target), data_(data),k_(3)
   {
+    utility::yat_assert<std::runtime_error>
+      (data.columns()==target.size(),
+       "KNN::KNN called with different sizes of target and data");
+    if(data_.columns()>k_) 
+      k_=data_.columns();
   }
   
@@ -232 +245 @@
         (*distances)(i,j) = distance_(training1.begin(), training1.end(), 
                                       test1.begin());
-        utility::yat_assert<std::runtime_error>(!std::isnan((*distances)(i,j)));
       }
     }
@@ -255 +267 @@
   {
     k_=k;
+    if(k_>data_.columns())
+      k_=data_.columns();
   }
 
@@ -295 +309 @@
                                                  utility::Matrix& prediction) const
   {   
-    utility::yat_assert<std::runtime_error>(data_.rows()==test.rows());
+    utility::yat_assert<std::runtime_error>(data_.rows()==test.rows(),"KNN::predict different number of rows in training and test data");
 
     utility::Matrix* distances=calculate_distances(test);
@@ -308 +322 @@
     }
     delete distances;
+
+    // classes for which there are no training samples should be set
+    // to nan in the predictions
+    for(size_t c=0;c<target_.nof_classes(); c++) 
+      if(!target_.size(c)) 
+        for(size_t j=0;j<prediction.columns();j++)
+          prediction(c,j)=std::numeric_limits<double>::quiet_NaN();
   }
 

trunk/yat/classifier/KNN_ReciprocalDistance.h

@@ -3 +3 @@
 
 // $Id$
+
+/*
+  Copyright (C) 2008 Markus Ringnér
+
+  This file is part of the yat library, http://trac.thep.lu.se/yat
+
+  The yat library is free software; you can redistribute it and/or
+  modify it under the terms of the GNU General Public License as
+  published by the Free Software Foundation; either version 2 of the
+  License, or (at your option) any later version.
+
+  The yat library 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.
+
+  You should have received a copy of the GNU General Public License
+  along with this program; if not, write to the Free Software
+  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+  02111-1307, USA.
+*/
+
 
 #include <vector>

trunk/yat/classifier/KNN_ReciprocalRank.h

@@ -3 +3 @@
 
 // $Id$
+
+/*
+  Copyright (C) 2008 Markus Ringnér
+
+  This file is part of the yat library, http://trac.thep.lu.se/yat
+
+  The yat library is free software; you can redistribute it and/or
+  modify it under the terms of the GNU General Public License as
+  published by the Free Software Foundation; either version 2 of the
+  License, or (at your option) any later version.
+
+  The yat library 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.
+
+  You should have received a copy of the GNU General Public License
+  along with this program; if not, write to the Free Software
+  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+  02111-1307, USA.
+*/
 
 

trunk/yat/classifier/KNN_Uniform.cc

@@ -18 +18 @@
                                utility::VectorMutable& prediction) const
   {           
-    std::vector<size_t>::size_type k=k_sorted.size();
-    for(size_t j=0;j<k;j++) 
+    for(size_t j=0;j<k_sorted.size();j++) 
       prediction(target(k_sorted[j]))+=1.0;           
   }

trunk/yat/classifier/KNN_Uniform.h

@@ -3 +3 @@
 
 // $Id$
+
+/*
+  Copyright (C) 2008 Markus Ringnér
+
+  This file is part of the yat library, http://trac.thep.lu.se/yat
+
+  The yat library is free software; you can redistribute it and/or
+  modify it under the terms of the GNU General Public License as
+  published by the Free Software Foundation; either version 2 of the
+  License, or (at your option) any later version.
+
+  The yat library 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.
+
+  You should have received a copy of the GNU General Public License
+  along with this program; if not, write to the Free Software
+  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+  02111-1307, USA.
+*/
+
 
 #include <vector>

trunk/yat/classifier/NCC.h

@@ -198 +198 @@
           if(class_averager[c].sum_w()==0) {
             centroids_nan_=true;
-            (*centroids_)(i,c) = std::numeric_limits<double>::quiet_NaN();
           }
-          else {
-            (*centroids_)(i,c) = class_averager[c].mean();
-          }
+          (*centroids_)(i,c) = class_averager[c].mean();
         }
       }
@@ -262 +259 @@
                                          utility::Matrix& prediction) const
   {
-    MatrixLookup unweighted_centroids(*centroids_);
-    for(size_t j=0; j<test.columns();j++) {       
-      DataLookup1D in(test,j,false);
-      for(size_t k=0; k<centroids_->columns();k++) {
-        DataLookup1D centroid(unweighted_centroids,k,false);            
-        utility::yat_assert<std::runtime_error>(in.size()==centroid.size());
-        prediction(k,j) = distance_(in.begin(), in.end(), centroid.begin());
-      }
-    }
-  }
-
+    MatrixLookup centroids(*centroids_);
+    for(size_t j=0; j<test.columns();j++)
+      for(size_t k=0; k<centroids_->columns();k++) 
+        prediction(k,j) = distance_(test.begin_column(j), test.end_column(j), 
+                                    centroids.begin_column(k));
+  }
+  
   template <typename Distance>
   void NCC<Distance>::predict_weighted(const MatrixLookupWeighted& test, 
@@ -278 +271 @@
   {
     MatrixLookupWeighted weighted_centroids(*centroids_);
-    for(size_t j=0; j<test.columns();j++) {       
-      DataLookupWeighted1D in(test,j,false);
-      for(size_t k=0; k<centroids_->columns();k++) {
-        DataLookupWeighted1D centroid(weighted_centroids,k,false);
-        utility::yat_assert<std::runtime_error>(in.size()==centroid.size());
-        prediction(k,j) = distance_(in.begin(), in.end(), centroid.begin());
-      }
-    }
+    for(size_t j=0; j<test.columns();j++) 
+      for(size_t k=0; k<centroids_->columns();k++)
+        prediction(k,j) = distance_(test.begin_column(j), test.end_column(j), 
+                                    weighted_centroids.begin_column(k));
   }