yat/classifier/NCC.h

Code
Comments
Other
Rev Date Author Line
3554 03 Jan 17 peter 1 #ifndef _theplu_yat_classifier_ncc_
3554 03 Jan 17 peter 2 #define _theplu_yat_classifier_ncc_
454 16 Dec 05 markus 3
616 31 Aug 06 jari 4 // $Id$
505 02 Feb 06 markus 5
675 10 Oct 06 jari 6 /*
2119 12 Dec 09 peter 7   Copyright (C) 2005 Peter Johansson, Markus Ringnér
4359 23 Aug 23 peter 8   Copyright (C) 2006 Jari Häkkinen, Peter Johansson, Markus Ringnér
4359 23 Aug 23 peter 9   Copyright (C) 2007 Peter Johansson, Markus Ringnér
4359 23 Aug 23 peter 10   Copyright (C) 2008 Jari Häkkinen, Peter Johansson, Markus Ringnér
4359 23 Aug 23 peter 11   Copyright (C) 2010, 2017 Peter Johansson
616 31 Aug 06 jari 12
1437 25 Aug 08 peter 13   This file is part of the yat library, http://dev.thep.lu.se/yat
454 16 Dec 05 markus 14
675 10 Oct 06 jari 15   The yat library is free software; you can redistribute it and/or
675 10 Oct 06 jari 16   modify it under the terms of the GNU General Public License as
1486 09 Sep 08 jari 17   published by the Free Software Foundation; either version 3 of the
675 10 Oct 06 jari 18   License, or (at your option) any later version.
675 10 Oct 06 jari 19
675 10 Oct 06 jari 20   The yat library is distributed in the hope that it will be useful,
675 10 Oct 06 jari 21   but WITHOUT ANY WARRANTY; without even the implied warranty of
675 10 Oct 06 jari 22   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
675 10 Oct 06 jari 23   General Public License for more details.
675 10 Oct 06 jari 24
675 10 Oct 06 jari 25   You should have received a copy of the GNU General Public License
1487 10 Sep 08 jari 26   along with yat. If not, see <http://www.gnu.org/licenses/>.
675 10 Oct 06 jari 27 */
675 10 Oct 06 jari 28
925 02 Oct 07 markus 29 #include "MatrixLookup.h"
925 02 Oct 07 markus 30 #include "MatrixLookupWeighted.h"
680 11 Oct 06 jari 31 #include "SupervisedClassifier.h"
925 02 Oct 07 markus 32 #include "Target.h"
675 10 Oct 06 jari 33
931 05 Oct 07 markus 34 #include "yat/statistics/Averager.h"
931 05 Oct 07 markus 35 #include "yat/statistics/AveragerWeighted.h"
2334 15 Oct 10 peter 36 #include "yat/utility/concept_check.h"
2210 05 Mar 10 peter 37 #include "yat/utility/Exception.h"
1121 22 Feb 08 peter 38 #include "yat/utility/Matrix.h"
1483 09 Sep 08 peter 39 #include "yat/utility/MatrixWeighted.h"
1120 21 Feb 08 peter 40 #include "yat/utility/Vector.h"
925 02 Oct 07 markus 41 #include "yat/utility/yat_assert.h"
925 02 Oct 07 markus 42
2334 15 Oct 10 peter 43 #include <boost/concept_check.hpp>
2334 15 Oct 10 peter 44
2076 06 Oct 09 peter 45 #include <iterator>
454 16 Dec 05 markus 46 #include <map>
925 02 Oct 07 markus 47 #include <cmath>
454 16 Dec 05 markus 48
454 16 Dec 05 markus 49 namespace theplu {
680 11 Oct 06 jari 50 namespace yat {
3554 03 Jan 17 peter 51 namespace classifier {
454 16 Dec 05 markus 52
454 16 Dec 05 markus 53
1189 29 Feb 08 markus 54   /**
1189 29 Feb 08 markus 55      \brief Nearest Centroid Classifier
3554 03 Jan 17 peter 56
1189 29 Feb 08 markus 57      A sample is predicted based on its distance to centroids for each
1189 29 Feb 08 markus 58      class. The centroids are generated using training data. NCC
1189 29 Feb 08 markus 59      supports using different measures, for example, Euclidean
3554 03 Jan 17 peter 60      distance, to define distance between samples and centroids.
1189 29 Feb 08 markus 61
1189 29 Feb 08 markus 62      The template argument Distance should be a class modelling
1189 29 Feb 08 markus 63      the concept \ref concept_distance.
1189 29 Feb 08 markus 64   */
925 02 Oct 07 markus 65   template <typename Distance>
476 22 Dec 05 markus 66   class NCC : public SupervisedClassifier
454 16 Dec 05 markus 67   {
3554 03 Jan 17 peter 68
454 16 Dec 05 markus 69   public:
1189 29 Feb 08 markus 70     /**
1189 29 Feb 08 markus 71        \brief Constructor
3554 03 Jan 17 peter 72
3554 03 Jan 17 peter 73        Distance is initialized using its default constructor.
1189 29 Feb 08 markus 74     */
1157 26 Feb 08 markus 75     NCC(void);
3554 03 Jan 17 peter 76
1189 29 Feb 08 markus 77     /**
1189 29 Feb 08 markus 78        \brief Constructor using an initialized distance measure
1189 29 Feb 08 markus 79
1189 29 Feb 08 markus 80        This constructor should be used if Distance has parameters and
1189 29 Feb 08 markus 81        the user wants to specify the parameters by initializing
1189 29 Feb 08 markus 82        Distance prior to constructing the NCC.
1189 29 Feb 08 markus 83     */
1158 26 Feb 08 markus 84     NCC(const Distance&);
1157 26 Feb 08 markus 85
1158 26 Feb 08 markus 86
1189 29 Feb 08 markus 87     /**
1189 29 Feb 08 markus 88        Destructor
1189 29 Feb 08 markus 89     */
1157 26 Feb 08 markus 90     virtual ~NCC(void);
454 16 Dec 05 markus 91
1189 29 Feb 08 markus 92     /**
1189 29 Feb 08 markus 93        \brief Get the centroids for all classes.
1189 29 Feb 08 markus 94
1189 29 Feb 08 markus 95        \return The centroids for each class as columns in a matrix.
1189 29 Feb 08 markus 96     */
1121 22 Feb 08 peter 97     const utility::Matrix& centroids(void) const;
454 16 Dec 05 markus 98
1157 26 Feb 08 markus 99     NCC<Distance>* make_classifier(void) const;
3554 03 Jan 17 peter 100
1189 29 Feb 08 markus 101     /**
1189 29 Feb 08 markus 102        \brief Make predictions for unweighted test data.
1189 29 Feb 08 markus 103
1189 29 Feb 08 markus 104        Predictions are calculated and returned in \a results.  For
1189 29 Feb 08 markus 105        each sample in \a data, \a results contains the distances to
1189 29 Feb 08 markus 106        the centroids for each class. If a class has no training
1189 29 Feb 08 markus 107        samples NaN's are returned for this class in \a
1189 29 Feb 08 markus 108        results. Weighted distance calculations, in which NaN's have
1189 29 Feb 08 markus 109        zero weights, are used if the centroids contain NaN's.
3554 03 Jan 17 peter 110
1189 29 Feb 08 markus 111        \note NCC returns distances to centroids as the
1189 29 Feb 08 markus 112        prediction. This means that the best class for a sample has the
1189 29 Feb 08 markus 113        smallest value in \a results. This is in contrast to, for
1189 29 Feb 08 markus 114        example, KNN for which the best class for a sample in \a
1189 29 Feb 08 markus 115        results has the largest number (the largest number of nearest
1189 29 Feb 08 markus 116        neighbors).
1189 29 Feb 08 markus 117     */
1189 29 Feb 08 markus 118     void predict(const MatrixLookup& data, utility::Matrix& results) const;
3554 03 Jan 17 peter 119
1189 29 Feb 08 markus 120     /**
1189 29 Feb 08 markus 121        \brief Make predictions for weighted test data.
454 16 Dec 05 markus 122
1189 29 Feb 08 markus 123        Predictions are calculated and returned in \a results.  For
1189 29 Feb 08 markus 124        each sample in \a data, \a results contains the distances to
1189 29 Feb 08 markus 125        the centroids for each class as in predict(const MatrixLookup&
1189 29 Feb 08 markus 126        data, utility::Matrix& results). Weighted distance calculations
1189 29 Feb 08 markus 127        are used, and zero weights are used for NaN's in centroids.  If
1189 29 Feb 08 markus 128        for a test sample and centroid pair, all variables have either
1189 29 Feb 08 markus 129        zero weight for the test sample or NaN for the centroid, the
1189 29 Feb 08 markus 130        centroid and the sample have no variables with values in
1189 29 Feb 08 markus 131        common. In this case the prediction for the sample is set to
1189 29 Feb 08 markus 132        NaN for the class in \a results.
3554 03 Jan 17 peter 133
1189 29 Feb 08 markus 134        \note NCC returns distances to centroids as the
1189 29 Feb 08 markus 135        prediction. This means that the best class for a sample has the
1189 29 Feb 08 markus 136        smallest value in \a results. This is in contrast to, for
1189 29 Feb 08 markus 137        example, KNN for which the best class for a sample in \a
1189 29 Feb 08 markus 138        results has the largest number (the largest number of nearest
1189 29 Feb 08 markus 139        neighbors).
1189 29 Feb 08 markus 140     */
1189 29 Feb 08 markus 141     void predict(const MatrixLookupWeighted& data, utility::Matrix& results) const;
1157 26 Feb 08 markus 142
1189 29 Feb 08 markus 143     /**
1189 29 Feb 08 markus 144        \brief Train the NCC using unweighted training data with known
3554 03 Jan 17 peter 145        targets.
1157 26 Feb 08 markus 146
1189 29 Feb 08 markus 147        A centroid is calculated for each class. For each variable in
1189 29 Feb 08 markus 148        \a data, a centroid for a class contains the average value of
1189 29 Feb 08 markus 149        the variable across all training samples in the class.
1189 29 Feb 08 markus 150     */
1189 29 Feb 08 markus 151     void train(const MatrixLookup& data, const Target& targets);
1160 26 Feb 08 markus 152
1189 29 Feb 08 markus 153
1189 29 Feb 08 markus 154     /**
1189 29 Feb 08 markus 155        \brief Train the NCC using weighted training data with known
3554 03 Jan 17 peter 156        targets.
1189 29 Feb 08 markus 157
3554 03 Jan 17 peter 158        A centroid is calculated for each class as in
3554 03 Jan 17 peter 159        train(const MatrixLookup&, const Target&).
1189 29 Feb 08 markus 160        The weights of the data are used when calculating the centroids
1189 29 Feb 08 markus 161        and the centroids should be interpreted as unweighted
1189 29 Feb 08 markus 162        (i.e. centroid values have unity weights). If a variable has
1189 29 Feb 08 markus 163        zero weights for all samples in a class, the centroid is set to
1189 29 Feb 08 markus 164        NaN for that variable.
1189 29 Feb 08 markus 165     */
1189 29 Feb 08 markus 166     void train(const MatrixLookupWeighted& data, const Target& targets);
1189 29 Feb 08 markus 167
3554 03 Jan 17 peter 168
454 16 Dec 05 markus 169   private:
925 02 Oct 07 markus 170
1121 22 Feb 08 peter 171     void predict_unweighted(const MatrixLookup&, utility::Matrix&) const;
3554 03 Jan 17 peter 172     void predict_weighted(const MatrixLookupWeighted&, utility::Matrix&) const;
1033 05 Feb 08 markus 173
1173 27 Feb 08 markus 174     utility::Matrix centroids_;
1033 05 Feb 08 markus 175     bool centroids_nan_;
1050 07 Feb 08 peter 176     Distance distance_;
3554 03 Jan 17 peter 177   };
454 16 Dec 05 markus 178
925 02 Oct 07 markus 179   // templates
925 02 Oct 07 markus 180
925 02 Oct 07 markus 181   template <typename Distance>
3554 03 Jan 17 peter 182   NCC<Distance>::NCC()
1173 27 Feb 08 markus 183     : SupervisedClassifier(), centroids_nan_(false)
925 02 Oct 07 markus 184   {
2334 15 Oct 10 peter 185     BOOST_CONCEPT_ASSERT((utility::DistanceConcept<Distance>));
925 02 Oct 07 markus 186   }
925 02 Oct 07 markus 187
1158 26 Feb 08 markus 188   template <typename Distance>
3554 03 Jan 17 peter 189   NCC<Distance>::NCC(const Distance& dist)
1173 27 Feb 08 markus 190     : SupervisedClassifier(), centroids_nan_(false), distance_(dist)
1158 26 Feb 08 markus 191   {
2334 15 Oct 10 peter 192     BOOST_CONCEPT_ASSERT((utility::DistanceConcept<Distance>));
1158 26 Feb 08 markus 193   }
925 02 Oct 07 markus 194
1158 26 Feb 08 markus 195
925 02 Oct 07 markus 196   template <typename Distance>
3554 03 Jan 17 peter 197   NCC<Distance>::~NCC()
925 02 Oct 07 markus 198   {
925 02 Oct 07 markus 199   }
925 02 Oct 07 markus 200
1157 26 Feb 08 markus 201
925 02 Oct 07 markus 202   template <typename Distance>
1121 22 Feb 08 peter 203   const utility::Matrix& NCC<Distance>::centroids(void) const
925 02 Oct 07 markus 204   {
1173 27 Feb 08 markus 205     return centroids_;
925 02 Oct 07 markus 206   }
925 02 Oct 07 markus 207
3554 03 Jan 17 peter 208
925 02 Oct 07 markus 209   template <typename Distance>
3554 03 Jan 17 peter 210   NCC<Distance>*
3554 03 Jan 17 peter 211   NCC<Distance>::make_classifier() const
3554 03 Jan 17 peter 212   {
1164 26 Feb 08 markus 213     // All private members should be copied here to generate an
1164 26 Feb 08 markus 214     // identical but untrained classifier
1164 26 Feb 08 markus 215     return new NCC<Distance>(distance_);
925 02 Oct 07 markus 216   }
1157 26 Feb 08 markus 217
925 02 Oct 07 markus 218   template <typename Distance>
1157 26 Feb 08 markus 219   void NCC<Distance>::train(const MatrixLookup& data, const Target& target)
3554 03 Jan 17 peter 220   {
1173 27 Feb 08 markus 221     centroids_.resize(data.rows(), target.nof_classes());
1157 26 Feb 08 markus 222     for(size_t i=0; i<data.rows(); i++) {
1157 26 Feb 08 markus 223       std::vector<statistics::Averager> class_averager;
1157 26 Feb 08 markus 224       class_averager.resize(target.nof_classes());
1157 26 Feb 08 markus 225       for(size_t j=0; j<data.columns(); j++) {
1157 26 Feb 08 markus 226         class_averager[target(j)].add(data(i,j));
931 05 Oct 07 markus 227       }
1157 26 Feb 08 markus 228       for(size_t c=0;c<target.nof_classes();c++) {
1173 27 Feb 08 markus 229         centroids_(i,c) = class_averager[c].mean();
931 05 Oct 07 markus 230       }
925 02 Oct 07 markus 231     }
925 02 Oct 07 markus 232   }
925 02 Oct 07 markus 233
925 02 Oct 07 markus 234
925 02 Oct 07 markus 235   template <typename Distance>
1157 26 Feb 08 markus 236   void NCC<Distance>::train(const MatrixLookupWeighted& data, const Target& target)
3554 03 Jan 17 peter 237   {
1173 27 Feb 08 markus 238     centroids_.resize(data.rows(), target.nof_classes());
1157 26 Feb 08 markus 239     for(size_t i=0; i<data.rows(); i++) {
1157 26 Feb 08 markus 240       std::vector<statistics::AveragerWeighted> class_averager;
1157 26 Feb 08 markus 241       class_averager.resize(target.nof_classes());
3554 03 Jan 17 peter 242       for(size_t j=0; j<data.columns(); j++)
1157 26 Feb 08 markus 243         class_averager[target(j)].add(data.data(i,j),data.weight(i,j));
1157 26 Feb 08 markus 244       for(size_t c=0;c<target.nof_classes();c++) {
1157 26 Feb 08 markus 245         if(class_averager[c].sum_w()==0) {
1157 26 Feb 08 markus 246           centroids_nan_=true;
931 05 Oct 07 markus 247         }
1173 27 Feb 08 markus 248         centroids_(i,c) = class_averager[c].mean();
925 02 Oct 07 markus 249       }
931 05 Oct 07 markus 250     }
925 02 Oct 07 markus 251   }
925 02 Oct 07 markus 252
1157 26 Feb 08 markus 253
925 02 Oct 07 markus 254   template <typename Distance>
3554 03 Jan 17 peter 255   void NCC<Distance>::predict(const MatrixLookup& test,
1121 22 Feb 08 peter 256                               utility::Matrix& prediction) const
3554 03 Jan 17 peter 257   {
2210 05 Mar 10 peter 258     utility::yat_assert<utility::runtime_error>
1173 27 Feb 08 markus 259       (centroids_.rows()==test.rows(),
1013 01 Feb 08 markus 260        "NCC::predict test data with incorrect number of rows");
3554 03 Jan 17 peter 261
1173 27 Feb 08 markus 262     prediction.resize(centroids_.columns(), test.columns());
1007 29 Jan 08 markus 263
3555 03 Jan 17 peter 264     // If weighted training data has resulted in NaN in centroids:
3555 03 Jan 17 peter 265     // weighted calculations
3554 03 Jan 17 peter 266     if(centroids_nan_) {
1160 26 Feb 08 markus 267       predict_weighted(MatrixLookupWeighted(test),prediction);
925 02 Oct 07 markus 268     }
1160 26 Feb 08 markus 269     // If unweighted training data: unweighted calculations
1007 29 Jan 08 markus 270     else {
1160 26 Feb 08 markus 271       predict_unweighted(test,prediction);
1007 29 Jan 08 markus 272     }
925 02 Oct 07 markus 273   }
1160 26 Feb 08 markus 274
1160 26 Feb 08 markus 275   template <typename Distance>
3554 03 Jan 17 peter 276   void NCC<Distance>::predict(const MatrixLookupWeighted& test,
1160 26 Feb 08 markus 277                               utility::Matrix& prediction) const
3554 03 Jan 17 peter 278   {
2210 05 Mar 10 peter 279     utility::yat_assert<utility::runtime_error>
1173 27 Feb 08 markus 280       (centroids_.rows()==test.rows(),
1160 26 Feb 08 markus 281        "NCC::predict test data with incorrect number of rows");
3554 03 Jan 17 peter 282
1173 27 Feb 08 markus 283     prediction.resize(centroids_.columns(), test.columns());
1160 26 Feb 08 markus 284     predict_weighted(test,prediction);
1160 26 Feb 08 markus 285   }
1160 26 Feb 08 markus 286
3554 03 Jan 17 peter 287
1033 05 Feb 08 markus 288   template <typename Distance>
3554 03 Jan 17 peter 289   void NCC<Distance>::predict_unweighted(const MatrixLookup& test,
1121 22 Feb 08 peter 290                                          utility::Matrix& prediction) const
1033 05 Feb 08 markus 291   {
1142 25 Feb 08 markus 292     for(size_t j=0; j<test.columns();j++)
3554 03 Jan 17 peter 293       for(size_t k=0; k<centroids_.columns();k++)
3554 03 Jan 17 peter 294         prediction(k,j) = distance_(test.begin_column(j), test.end_column(j),
1174 27 Feb 08 peter 295                                     centroids_.begin_column(k));
1033 05 Feb 08 markus 296   }
3554 03 Jan 17 peter 297
1033 05 Feb 08 markus 298   template <typename Distance>
3554 03 Jan 17 peter 299   void NCC<Distance>::predict_weighted(const MatrixLookupWeighted& test,
3555 03 Jan 17 peter 300                                        utility::Matrix& prediction) const
1033 05 Feb 08 markus 301   {
1483 09 Sep 08 peter 302     utility::MatrixWeighted weighted_centroids(centroids_);
3554 03 Jan 17 peter 303     for(size_t j=0; j<test.columns();j++)
1173 27 Feb 08 markus 304       for(size_t k=0; k<centroids_.columns();k++)
3554 03 Jan 17 peter 305         prediction(k,j) = distance_(test.begin_column(j), test.end_column(j),
1142 25 Feb 08 markus 306                                     weighted_centroids.begin_column(k));
1033 05 Feb 08 markus 307   }
1033 05 Feb 08 markus 308
3554 03 Jan 17 peter 309
680 11 Oct 06 jari 310 }}} // of namespace classifier, yat, and theplu
454 16 Dec 05 markus 311
454 16 Dec 05 markus 312 #endif

Generated on Sat Oct 14 02:22:20 2023 (UTC) by svndigest 0.11.2pre (dev build 1672)