Changeset 1112
 Timestamp:
 Feb 21, 2008, 3:59:30 PM (14 years ago)
 Location:
 trunk
 Files:

 6 added
 5 edited
Legend:
 Unmodified
 Added
 Removed

trunk/doc/concepts.doxygen
r1094 r1112 5 5 // This file is part of the yat library, http://trac.thep.lu.se/yat 6 6 // 7 // The yat library is free software; you can redistribute it and /or7 // The yat library is free software; you can redistribute it and./or 8 8 // modify it under the terms of the GNU General Public License as 9 9 // published by the Free Software Foundation; either version 2 of the … … 22 22 23 23 /** 24 24 \page Concepts Concepts 25 25 26 26 This page lists all the C++ concepts in the yat project. 27 27 28  \subpage concept_distance 28  \subpage concept_distance 29  \subpage concept_neighbor_weighting 29 30 */ 30 31 31 32 32 33 /** 33 \page concept_distance Distance 34 \section Description 35 Distance is a concept ... 36 \section Requirements 37 Classes implementing the concept Distance should fulfill ... 38 Examples include theplu::yat::statistics::PearsonDistance and theplu::yat::statistics::EuclideanDistance. 34 \page concept_distance Distance 35 36 \section Description 37 38 \ref concept_distance is a concept .. 39 40 \section Requirements 41 42 Classes modelling the concept \ref concept_distance should implement ... 43 44 Examples of classes modelling the concept \ref concept_distance 45 include theplu::yat::statistics::PearsonDistance and 46 theplu::yat::statistics::EuclideanDistance. 47 39 48 */ 49 50 /** 51 \page concept_neighbor_weighting Neighbor Weighting Method 52 53 \section Description 54 55 \ref concept_neighbor_weighting is a concept used in connection with 56 theplu::yat::classifier::KNN  classes used as the template argument 57 NeighborWeighting should implement this concept. 58 59 \section Requirements 60 61 Classes modelling the concept \ref concept_neighbor_weighting should 62 implement the following function: 63 64 \verbatim 65 void operator()(const utility::VectorBase& distance, const std::vector<size_t> k_sorted, 66 const Target& target, utility::VectorMutable& prediction) const 67 \endverbatim 68 69 For a test sample, this function should calculate a total vote 70 (i.e. based on all k nearest neighbors) for each class. The vector \a 71 distance contains the distances from a test sample to all training 72 samples. The vector \a k_sorted contains the indices (for both \a 73 distance and \a target) to the k training samples with the smallest 74 distances to the test sample. The class for each training sample is 75 given by \a target, which is sorted in the same sample order as \a 76 distance. For each class the function calculates a total vote based on 77 the the nearest neighbors of the test sample that belong to the 78 class. The total vote for each class is stored in the vector \a prediction. 79 80 Examples of classes modelling the concept \ref 81 concept_neighbor_weighting include 82 theplu::yat::classifier::KNN_Uniform, 83 theplu::yat::classifier::KNN_ReciprocalDistance and 84 theplu::yat::classifier::KNN_ReciprocalRank. 85 86 */ 
trunk/test/knn_test.cc
r1107 r1112 23 23 24 24 #include "yat/classifier/KNN.h" 25 #include "yat/classifier/KNN_ReciprocalDistance.h" 26 #include "yat/classifier/KNN_ReciprocalRank.h" 25 27 #include "yat/classifier/MatrixLookup.h" 26 28 #include "yat/classifier/MatrixLookupWeighted.h" … … 89 91 double slack_bound=2e7; 90 92 utility::matrix result1(2,4); 91 result1(0,0)=result1(0,1)=result1(1,2)=result1(1,3)=2.0 /3.0;92 result1(0,2)=result1(0,3)=result1(1,0)=result1(1,1)=1.0 /3.0;93 result1(0,0)=result1(0,1)=result1(1,2)=result1(1,3)=2.0; 94 result1(0,2)=result1(0,3)=result1(1,0)=result1(1,1)=1.0; 93 95 double slack = deviation(prediction1,result1); 94 96 if (slack > slack_bound  std::isnan(slack)){ … … 108 110 classifier::MatrixLookupWeighted mlw1(data1,weights1); 109 111 knn1.predict(mlw1,prediction1); 110 result1(0,0)=1.0 /3.0;111 result1(1,0)=2.0 /3.0;112 result1(0,0)=1.0; 113 result1(1,0)=2.0; 112 114 slack = deviation(prediction1,result1); 113 115 if (slack > slack_bound  std::isnan(slack)){ … … 119 121 120 122 //////////////////////////////////////////////////////////////// 121 // A test of training and test both weighted 123 // A test of training and test both weighted 122 124 //////////////////////////////////////////////////////////////// 123 125 *error << "test of predictions using weighted training and test data\n"; … … 130 132 knn2.train(); 131 133 knn2.predict(mlw1,prediction1); 132 result1(0,1)=1.0 /3.0;133 result1(1,1)=2.0 /3.0;134 result1(0,1)=1.0; 135 result1(1,1)=2.0; 134 136 slack = deviation(prediction1,result1); 135 137 if (slack > slack_bound  std::isnan(slack)){ … … 140 142 } 141 143 144 145 //////////////////////////////////////////////////////////////// 146 // A test of reciprocal ranks weighting with training and test both weighted 147 //////////////////////////////////////////////////////////////// 148 utility::matrix data2(data1); 149 data2(1,3)=7; 150 classifier::MatrixLookupWeighted mlw3(data2,weights2); 151 classifier::KNN<statistics::EuclideanDistance,classifier::KNN_ReciprocalRank> 152 knn3(mlw2,target1); 153 knn3.k(3); 154 knn3.train(); 155 knn3.predict(mlw3,prediction1); 156 result1(0,0)=result1(1,3)=1.0; 157 result1(0,3)=result1(1,0)=5.0/6.0; 158 result1(0,2)=result1(1,1)=1.0/2.0; 159 result1(0,1)=result1(1,2)=4.0/3.0; 160 slack = deviation(prediction1,result1); 161 if (slack > slack_bound  std::isnan(slack)){ 162 *error << "Difference to expected prediction too large\n"; 163 *error << "slack: " << slack << std::endl; 164 *error << "expected less than " << slack_bound << std::endl; 165 ok = false; 166 } 167 168 169 //////////////////////////////////////////////////////////////// 170 // A test of reciprocal distance weighting with training and test both weighted 171 //////////////////////////////////////////////////////////////// 172 classifier::KNN<statistics::EuclideanDistance,classifier::KNN_ReciprocalDistance> 173 knn4(mlw2,target1); 174 knn4.k(3); 175 knn4.train(); 176 knn4.predict(mlw3,prediction1); 177 slack = deviation(prediction1,result1); 178 if (!std::isinf(prediction1(0,0)) && !std::isinf(prediction1(0,1)) && 179 !std::isinf(prediction1(1,2)) && 180 fabs(prediction1(1,3)(1.0/3.67423461417))>slack_bound && 181 fabs(prediction1(1,0)(1.0/2.82842712475+1.0/2.44948974278))>slack_bound){ 182 *error << "Difference to expected prediction too large\n"; 183 ok = false; 184 } 142 185 143 186 if(!ok) { 
trunk/yat/classifier/KNN.h
r1107 r1112 27 27 #include "DataLookup1D.h" 28 28 #include "DataLookupWeighted1D.h" 29 #include "KNN_Uniform.h" 29 30 #include "MatrixLookup.h" 30 31 #include "MatrixLookupWeighted.h" … … 43 44 44 45 /// 45 /// @brief Class for Nearest Centroid Classification. 46 /// 47 48 49 template <typename Distance> 46 /// @brief Class for Nearest Neigbor Classification. 47 /// 48 /// The template argument Distance should be a class implementing 49 /// the concept \ref concept_distance. 50 /// The template argument NeigborWeighting should be a class implementing 51 /// the concept \ref concept_neighbor_weighting. 52 53 template <typename Distance, typename NeighborWeighting=KNN_Uniform> 50 54 class KNN : public SupervisedClassifier 51 55 { … … 74 78 75 79 /// 76 /// Default number of neighbo urs (k) is set to 3.77 /// 78 /// @return the number of neighbo urs80 /// Default number of neighbors (k) is set to 3. 81 /// 82 /// @return the number of neighbors 79 83 /// 80 84 u_int k() const; 81 85 82 86 /// 83 /// @brief sets the number of neighbo urs, k.87 /// @brief sets the number of neighbors, k. 84 88 /// 85 89 void k(u_int); … … 99 103 100 104 /// 101 /// For each sample, calculate the number of neighbo urs for each105 /// For each sample, calculate the number of neighbors for each 102 106 /// class. 103 107 /// … … 112 116 const DataLookup2D& data_; 113 117 114 // The number of neighbo urs118 // The number of neighbors 115 119 u_int k_; 116 120 117 121 Distance distance_; 122 123 NeighborWeighting weighting_; 124 118 125 /// 119 126 /// Calculates the distances between a data set and the training … … 123 130 /// 124 131 utility::matrix* calculate_distances(const DataLookup2D&) const; 132 125 133 void calculate_unweighted(const MatrixLookup&, 126 134 const MatrixLookup&, … … 134 142 // templates 135 143 136 template <typename Distance >137 KNN<Distance >::KNN(const MatrixLookup& data, const Target& target)144 template <typename Distance, typename NeighborWeighting> 145 KNN<Distance, NeighborWeighting>::KNN(const MatrixLookup& data, const Target& target) 138 146 : SupervisedClassifier(target), data_(data),k_(3) 139 147 { … … 141 149 142 150 143 template <typename Distance> 144 KNN<Distance>::KNN(const MatrixLookupWeighted& data, const Target& target) 151 template <typename Distance, typename NeighborWeighting> 152 KNN<Distance, NeighborWeighting>::KNN 153 (const MatrixLookupWeighted& data, const Target& target) 145 154 : SupervisedClassifier(target), data_(data),k_(3) 146 155 { 147 156 } 148 157 149 template <typename Distance> 150 KNN<Distance>::~KNN() 151 { 152 } 153 154 template <typename Distance> 155 utility::matrix* KNN<Distance>::calculate_distances(const DataLookup2D& test) const 158 template <typename Distance, typename NeighborWeighting> 159 KNN<Distance, NeighborWeighting>::~KNN() 160 { 161 } 162 163 template <typename Distance, typename NeighborWeighting> 164 utility::matrix* KNN<Distance, NeighborWeighting>::calculate_distances 165 (const DataLookup2D& test) const 156 166 { 157 167 // matrix with training samples as rows and test samples as columns … … 197 207 } 198 208 199 template <typename Distance >200 void KNN<Distance >:: calculate_unweighted(const MatrixLookup& training,201 202 209 template <typename Distance, typename NeighborWeighting> 210 void KNN<Distance, NeighborWeighting>::calculate_unweighted 211 (const MatrixLookup& training, const MatrixLookup& test, 212 utility::matrix* distances) const 203 213 { 204 214 for(size_t i=0; i<training.columns(); i++) { … … 212 222 } 213 223 214 template <typename Distance> 215 void KNN<Distance>:: calculate_weighted(const MatrixLookupWeighted& training, 216 const MatrixLookupWeighted& test, 217 utility::matrix* distances) const 224 template <typename Distance, typename NeighborWeighting> 225 void 226 KNN<Distance, NeighborWeighting>::calculate_weighted 227 (const MatrixLookupWeighted& training, const MatrixLookupWeighted& test, 228 utility::matrix* distances) const 218 229 { 219 230 for(size_t i=0; i<training.columns(); i++) { … … 221 232 for(size_t j=0; j<test.columns(); j++) { 222 233 classifier::DataLookupWeighted1D test1(test,j,false); 223 (*distances)(i,j) = distance_(training1.begin(), training1.end(), test1.begin()); 234 (*distances)(i,j) = distance_(training1.begin(), training1.end(), 235 test1.begin()); 224 236 utility::yat_assert<std::runtime_error>(!std::isnan((*distances)(i,j))); 225 237 } … … 228 240 229 241 230 template <typename Distance >231 const DataLookup2D& KNN<Distance >::data(void) const242 template <typename Distance, typename NeighborWeighting> 243 const DataLookup2D& KNN<Distance, NeighborWeighting>::data(void) const 232 244 { 233 245 return data_; … … 235 247 236 248 237 template <typename Distance >238 u_int KNN<Distance >::k() const249 template <typename Distance, typename NeighborWeighting> 250 u_int KNN<Distance, NeighborWeighting>::k() const 239 251 { 240 252 return k_; 241 253 } 242 254 243 template <typename Distance >244 void KNN<Distance >::k(u_int k)255 template <typename Distance, typename NeighborWeighting> 256 void KNN<Distance, NeighborWeighting>::k(u_int k) 245 257 { 246 258 k_=k; … … 248 260 249 261 250 template <typename Distance >262 template <typename Distance, typename NeighborWeighting> 251 263 SupervisedClassifier* 252 KNN<Distance>::make_classifier(const DataLookup2D& data, const Target& target) const 264 KNN<Distance, NeighborWeighting>::make_classifier(const DataLookup2D& data, 265 const Target& target) const 253 266 { 254 267 KNN* knn=0; 255 268 try { 256 269 if(data.weighted()) { 257 knn=new KNN<Distance >(dynamic_cast<const MatrixLookupWeighted&>(data),258 270 knn=new KNN<Distance, NeighborWeighting> 271 (dynamic_cast<const MatrixLookupWeighted&>(data),target); 259 272 } 260 273 else { 261 knn=new KNN<Distance >(dynamic_cast<const MatrixLookup&>(data),262 274 knn=new KNN<Distance, NeighborWeighting> 275 (dynamic_cast<const MatrixLookup&>(data),target); 263 276 } 264 277 knn>k(this>k()); 265 278 } 266 279 catch (std::bad_cast) { 267 std::string str = "Error in KNN<Distance>::make_classifier: DataLookup2D of unexpected class."; 280 std::string str = "Error in KNN<Distance, NeighborWeighting>"; 281 str += "::make_classifier: DataLookup2D of unexpected class."; 268 282 throw std::runtime_error(str); 269 283 } … … 272 286 273 287 274 template <typename Distance >275 void KNN<Distance >::train()288 template <typename Distance, typename NeighborWeighting> 289 void KNN<Distance, NeighborWeighting>::train() 276 290 { 277 291 trained_=true; … … 279 293 280 294 281 template <typename Distance >282 void KNN<Distance >::predict(const DataLookup2D& test,283 utility::matrix& prediction) const295 template <typename Distance, typename NeighborWeighting> 296 void KNN<Distance, NeighborWeighting>::predict(const DataLookup2D& test, 297 utility::matrix& prediction) const 284 298 { 285 299 utility::yat_assert<std::runtime_error>(data_.rows()==test.rows()); … … 287 301 utility::matrix* distances=calculate_distances(test); 288 302 289 // for each test sample (column in distances) find the closest290 // training samples291 303 prediction.resize(target_.nof_classes(),test.columns(),0.0); 292 304 for(size_t sample=0;sample<distances>columns();sample++) { 293 305 std::vector<size_t> k_index; 294 utility::sort_smallest_index(k_index,k_, 295 distances>column_const_view(sample)); 296 for(size_t j=0;j<k_index.size();j++) { 297 prediction(target_(k_index[j]),sample)++; 298 } 299 } 300 prediction*=(1.0/k_); 306 utility::VectorConstView dist=distances>column_const_view(sample); 307 utility::sort_smallest_index(k_index,k_,dist); 308 utility::VectorView pred=prediction.column_view(sample); 309 weighting_(dist,k_index,target_,pred); 310 } 301 311 delete distances; 302 312 } 
trunk/yat/classifier/Makefile.am
r1079 r1112 42 42 Kernel_SEV.cc \ 43 43 KernelLookup.cc \ 44 KNN_Uniform.cc \ 45 KNN_ReciprocalDistance.cc \ 46 KNN_ReciprocalRank.cc \ 44 47 MatrixLookup.cc \ 45 48 MatrixLookupWeighted.cc \ … … 77 80 Kernel_SEV.h \ 78 81 KNN.h \ 82 KNN_Uniform.h \ 79 83 MatrixLookup.h \ 80 84 MatrixLookupWeighted.h \ 
trunk/yat/classifier/NCC.h
r1098 r1112 56 56 /// @brief Class for Nearest Centroid Classification. 57 57 /// 58 58 /// The template argument Distance should be a class implementing 59 /// the concept \ref concept_distance. 60 /// 59 61 template <typename Distance> 60 62 class NCC : public SupervisedClassifier
Note: See TracChangeset
for help on using the changeset viewer.