PLearn 0.1
|
This class provides a simple N-class classifier based upon an enclosed K-nearest-neighbors finder (derived from GenericNearestNeighbors; specified with the 'knn' option). More...
#include <KNNClassifier.h>
Public Member Functions | |
KNNClassifier () | |
Default constructor. | |
virtual void | build () |
Simply calls inherited::build() then build_(). | |
virtual void | makeDeepCopyFromShallowCopy (CopiesMap &copies) |
Transforms a shallow copy into a deep copy. | |
virtual string | classname () const |
virtual OptionList & | getOptionList () const |
virtual OptionMap & | getOptionMap () const |
virtual RemoteMethodMap & | getRemoteMethodMap () const |
virtual KNNClassifier * | deepCopy (CopiesMap &copies) const |
virtual void | setTrainingSet (VMat training_set, bool call_forget=true) |
Overridden to call knn->setTrainingSet. | |
virtual int | outputsize () const |
Returns the size of this learner's output, (which typically may depend on its inputsize(), targetsize() and set options). | |
virtual void | forget () |
Forwarded to knn. | |
virtual void | train () |
Forwarded to knn. | |
virtual void | computeOutput (const Vec &input, Vec &output) const |
Computes the output from the input. | |
virtual void | computeCostsFromOutputs (const Vec &input, const Vec &output, const Vec &target, Vec &costs) const |
Computes the costs from already computed output. | |
virtual TVec< std::string > | getTestCostNames () const |
Returns the names of the costs computed by computeCostsFromOutpus (and thus the test method). | |
virtual TVec< std::string > | getTrainCostNames () const |
Returns the names of the objective costs that the train method computes and for which it updates the VecStatsCollector train_stats. | |
Static Public Member Functions | |
static string | _classname_ () |
static OptionList & | _getOptionList_ () |
static RemoteMethodMap & | _getRemoteMethodMap_ () |
static Object * | _new_instance_for_typemap_ () |
static bool | _isa_ (const Object *o) |
static void | _static_initialize_ () |
static const PPath & | declaringFile () |
Public Attributes | |
PP< GenericNearestNeighbors > | knn |
The K-nearest-neighbors finder to use (default is an ExhaustiveNearestNeighbors with a GaussianKernel, sigma=1) | |
int | nclasses |
Number of classes in the problem. | |
int | kmin |
Minimum number of neighbors to use (default=5) | |
real | kmult |
Multiplicative factor on n^kpow to determine number of neighbors to use (default=0) | |
real | kpow |
Power of the number of training examples to determine number of neighbors (default=0.5) | |
bool | use_knn_costs_as_weights |
Whether to weigh each of the K neighbors by the kernel evaluations, obtained from the costs coming out of the 'knn' object (default=true) | |
Ker | kernel |
If use_knn_costs_as_weights is false, use this kernel to weight the observations. | |
TVec< int > | multi_k |
This can be used if you wish to simultaneously compute the costs for several values of k, efficiently, while doing neighbors search a single time. | |
Static Public Attributes | |
static StaticInitializer | _static_initializer_ |
Static Protected Member Functions | |
static void | declareOptions (OptionList &ol) |
Declares this class' options. | |
Protected Attributes | |
Vec | knn_output |
Internal use: temporary buffer for knn output. | |
Vec | knn_costs |
Internal use: temporary buffer for knn costs. | |
Vec | class_weights |
Internal use: temporary buffer for cumulating class weights. | |
Mat | multi_k_output |
Internal use: this is used when a multi_k option is provided to temporarily store the outputs the classifier would give for all values of k given in multi_k. | |
Vec | multi_k_input |
Internal use to remember the input used in computeOutput when using multi_k option. | |
Private Types | |
typedef PLearner | inherited |
Private Member Functions | |
void | build_ () |
This does the actual building. |
This class provides a simple N-class classifier based upon an enclosed K-nearest-neighbors finder (derived from GenericNearestNeighbors; specified with the 'knn' option).
The target variable (the class), is assumed to be coded an integer variable (the class number, from 0 to C-1, where C is the number of classes); the number of classes is specified with the option 'nclasses'. The structure of the learner output is a vector of probabilities for each class (even if numclasses==2, which is NOT collapsed into a probability of the positive class).
The class contains several options to determine the number of neighbors to use (K). This number always overrides the option 'num_neighbors' that may have been specified in the GenericNearestNeighbors utility object. Basically, the generic formula for the number of neighbors is
K = max(kmin, kmult*(n^kpow)),
where 'kmin', 'kmult', and 'kpow' are options, and 'n' is the number of examples in the training set.
The costs output from this class are:
If the option 'use_knn_costs_as_weights' is true (by default), it is assumed that the costs coming from the 'knn' object are kernel evaluations for each nearest neighbor. These are used as weights to determine the final class probabilities. (NOTE: it is important to use a kernel that computes a SIMILARITY MEASURE, and not a DISTANCE MEASURE; the default EpanechnikovKernel has the proper behavior.) If the option is false, an equal weighting is used (equivalent to square window).
The weights originally present in the training set ARE TAKEN INTO ACCOUNT when weighting each observation: they serve to multiply the kernel values to give the effective weight for an observation.
Definition at line 94 of file KNNClassifier.h.
typedef PLearner PLearn::KNNClassifier::inherited [private] |
Reimplemented from PLearn::PLearner.
Definition at line 96 of file KNNClassifier.h.
PLearn::KNNClassifier::KNNClassifier | ( | ) |
Default constructor.
Definition at line 97 of file KNNClassifier.cc.
string PLearn::KNNClassifier::_classname_ | ( | ) | [static] |
Reimplemented from PLearn::PLearner.
Definition at line 95 of file KNNClassifier.cc.
OptionList & PLearn::KNNClassifier::_getOptionList_ | ( | ) | [static] |
Reimplemented from PLearn::PLearner.
Definition at line 95 of file KNNClassifier.cc.
RemoteMethodMap & PLearn::KNNClassifier::_getRemoteMethodMap_ | ( | ) | [static] |
Reimplemented from PLearn::PLearner.
Definition at line 95 of file KNNClassifier.cc.
Reimplemented from PLearn::PLearner.
Definition at line 95 of file KNNClassifier.cc.
Object * PLearn::KNNClassifier::_new_instance_for_typemap_ | ( | ) | [static] |
Reimplemented from PLearn::Object.
Definition at line 95 of file KNNClassifier.cc.
StaticInitializer KNNClassifier::_static_initializer_ & PLearn::KNNClassifier::_static_initialize_ | ( | ) | [static] |
Reimplemented from PLearn::PLearner.
Definition at line 95 of file KNNClassifier.cc.
void PLearn::KNNClassifier::build | ( | ) | [virtual] |
Simply calls inherited::build() then build_().
Reimplemented from PLearn::PLearner.
Definition at line 186 of file KNNClassifier.cc.
References PLearn::PLearner::build(), and build_().
{ inherited::build(); build_(); }
void PLearn::KNNClassifier::build_ | ( | ) | [private] |
This does the actual building.
Reimplemented from PLearn::PLearner.
Definition at line 168 of file KNNClassifier.cc.
References kmin, knn, PLearn::TVec< T >::length(), multi_k, nclasses, and PLERROR.
Referenced by build().
{ if (!knn) knn=new ExhaustiveNearestNeighbors(new GaussianKernel(), false); if (nclasses <= 1) PLERROR("KNNClassifier::build_: the 'nclasses' option must be specified and >= 2"); if (kmin <= 0) PLERROR("KNNClassifier::build_: the 'kmin' option must be strictly positive"); for(int k=0; k<multi_k.length()-1; k++) if(multi_k[k]>multi_k[k+1]) PLERROR("values in option multi_k *must* be in increaisng order"); }
string PLearn::KNNClassifier::classname | ( | ) | const [virtual] |
Reimplemented from PLearn::Object.
Definition at line 95 of file KNNClassifier.cc.
void PLearn::KNNClassifier::computeCostsFromOutputs | ( | const Vec & | input, |
const Vec & | output, | ||
const Vec & | target, | ||
Vec & | costs | ||
) | const [virtual] |
Computes the costs from already computed output.
Implements PLearn::PLearner.
Definition at line 319 of file KNNClassifier.cc.
References PLearn::argmax(), PLearn::TVec< T >::length(), multi_k, multi_k_input, multi_k_output, pl_log, PLWARNING, and PLearn::TVec< T >::resize().
{ int n_multi_k = multi_k.length(); costs.resize(2*(1+n_multi_k)); int t = int(target[0]); int sel_class = argmax(output); costs[0] = sel_class != t; costs[1] = -pl_log(1e-10+output[t]); if(n_multi_k>0 && input!=multi_k_input) PLWARNING("In computeCostsFromOutputs: input appears different from multi_k_input. " "This probably means that computeOutput was called on a different input " "before calling computeCostsFromOutputs. As a consequence, the extra costs " "requested through the multi_k option will be incorrect"); for(int k=0; k<n_multi_k; k++) { Vec output_k = multi_k_output(k); int sel_class = argmax(output_k); costs[2+2*k] = sel_class != t; costs[3+2*k] = -pl_log(1e-10+output_k[t]); } }
Computes the output from the input.
< not used by knn
< safety net
< account for training weight
Reimplemented from PLearn::PLearner.
Definition at line 248 of file KNNClassifier.cc.
References PLearn::TVec< T >::begin(), class_weights, std::copy(), PLearn::TVec< T >::data(), PLearn::TVec< T >::end(), PLearn::TVec< T >::fill(), PLearn::TMat< T >::fill(), i, PLearn::PLearner::inputsize(), kernel, knn, knn_costs, knn_output, PLearn::TVec< T >::length(), multi_k, multi_k_input, multi_k_output, n, nclasses, outputsize(), PLASSERT, PLERROR, PLearn::TMat< T >::resize(), PLearn::TVec< T >::resize(), PLearn::TVec< T >::size(), use_knn_costs_as_weights, and w.
{ output.resize(outputsize()); // The case where a user-specified kernel complicates the situation const int inputsize = input.size(); Vec knn_targets; knn->computeOutputAndCosts(input, knn_targets, knn_output, knn_costs); real* output_data = knn_output.data(); int n_multi_k = multi_k.length(); if(n_multi_k>0) { // First remember the input so we can verify computeCostsFromOutputs is called on the same multi_k_input.resize(input.length()); multi_k_input << input; // Then initialize the multi_k_output matrix. multi_k_output.resize(n_multi_k, outputsize()); multi_k_output.fill(0); // TODO: need to sort the knn output ?... } // Cumulate the class weights. Compute the kernel if it's required. class_weights.resize(nclasses); class_weights.fill(0.0); real total_weight = 0.0; for (int i=0, n=knn->num_neighbors, multi_pos=0 ; i<n ; ++i) { real w = -1.0; if (kernel) { Vec cur_input(inputsize, output_data); w = kernel(cur_input, input); output_data += inputsize; } else if (use_knn_costs_as_weights) w = knn_costs[i]; else w = 1.0; int nn_class = int(*output_data++); if (nn_class < 0 || nn_class >= nclasses) PLERROR("KNNClassifier::computeOutput: expected the class to be between 0 " "and %d but found %d", nclasses-1, nn_class); w *= *output_data++; PLASSERT( w >= 0.0 ); class_weights[nn_class] += w; total_weight += w; if(multi_pos<n_multi_k && multi_k[multi_pos]==i+1) // we want to keep the output for k==i+1 { if (total_weight >= 1e-6) { Vec output_k = multi_k_output(multi_pos); output_k << class_weights; output_k *= 1/total_weight; } ++multi_pos; } } // If the total weight is too small, output zero probability for all classes if (total_weight < 1e-6) { output.fill(0.0); return; } // Now compute probabilities for (int i=0, n = nclasses; i<n ; ++i) class_weights[i] /= total_weight; // And output them copy(class_weights.begin(), class_weights.end(), output.begin()); }
void PLearn::KNNClassifier::declareOptions | ( | OptionList & | ol | ) | [static, protected] |
Declares this class' options.
Reimplemented from PLearn::PLearner.
Definition at line 107 of file KNNClassifier.cc.
References PLearn::OptionBase::buildoption, PLearn::declareOption(), PLearn::PLearner::declareOptions(), kernel, kmin, kmult, knn, kpow, multi_k, nclasses, and use_knn_costs_as_weights.
{ declareOption( ol, "knn", &KNNClassifier::knn, OptionBase::buildoption, "The K-nearest-neighbors finder to use (default is an\n" "ExhaustiveNearestNeighbors with a GaussianKernel, sigma=1)"); declareOption( ol, "nclasses", &KNNClassifier::nclasses, OptionBase::buildoption, "Number of classes in the problem. MUST be specified."); declareOption( ol, "kmin", &KNNClassifier::kmin, OptionBase::buildoption, "Minimum number of neighbors to use (default=5)"); declareOption( ol, "kmult", &KNNClassifier::kmult, OptionBase::buildoption, "Multiplicative factor on n^kpow to determine number of neighbors to\n" "use (default=0)"); declareOption( ol, "kpow", &KNNClassifier::kpow, OptionBase::buildoption, "Power of the number of training examples to determine number of\n" "neighbors (default=0.5)"); declareOption( ol, "use_knn_costs_as_weights", &KNNClassifier::use_knn_costs_as_weights, OptionBase::buildoption, "Whether to weigh each of the K neighbors by the kernel evaluations,\n" "obtained from the costs coming out of the 'knn' object (default=true)"); declareOption( ol, "kernel", &KNNClassifier::kernel, OptionBase::buildoption, "Disregard the 'use_knn_costs_as_weights' option, and use this kernel\n" "to weight the observations. If this object is not specified\n" "(default), and the 'use_knn_costs_as_weights' is false, the\n" "rectangular kernel is used."); declareOption( ol, "multi_k", &KNNClassifier::multi_k, OptionBase::buildoption, "This can be used if you wish to simultaneously compute the costs for\n" "several values of k, efficiently, while doing neighbors search a\n" "single time. Specify in increasing order, the values of k (number \n" "the number of neighbors) you are interested in. This will result \n" "in computing and making available extra costs in addition to \n" "class_error and neglogprob. For each such specified k, \n" "there will be a class_error_k and neglogprob_k.\n" "Note that these will however only be computed correctly for values\n" "of k that are less or equal to the global K determined by the other\n" "options. So if you specify a multi_k list, you should probably set \n" "kmin to the last and largest k of the list.\n" "On a technical note, these costs will be computed correctly \n" "only if the call to computeCostsFromOutputs follows the \n" "computeOutput corresponding to the same input (this is usually\n" "the case, and a warning is issued if it isn't)."); // Now call the parent class' declareOptions inherited::declareOptions(ol); }
static const PPath& PLearn::KNNClassifier::declaringFile | ( | ) | [inline, static] |
Reimplemented from PLearn::PLearner.
Definition at line 174 of file KNNClassifier.h.
:
//##### PLearner Methods ####################################################
KNNClassifier * PLearn::KNNClassifier::deepCopy | ( | CopiesMap & | copies | ) | const [virtual] |
Reimplemented from PLearn::PLearner.
Definition at line 95 of file KNNClassifier.cc.
void PLearn::KNNClassifier::forget | ( | ) | [virtual] |
Forwarded to knn.
Reimplemented from PLearn::PLearner.
Definition at line 235 of file KNNClassifier.cc.
OptionList & PLearn::KNNClassifier::getOptionList | ( | ) | const [virtual] |
Reimplemented from PLearn::Object.
Definition at line 95 of file KNNClassifier.cc.
OptionMap & PLearn::KNNClassifier::getOptionMap | ( | ) | const [virtual] |
Reimplemented from PLearn::Object.
Definition at line 95 of file KNNClassifier.cc.
RemoteMethodMap & PLearn::KNNClassifier::getRemoteMethodMap | ( | ) | const [virtual] |
Reimplemented from PLearn::Object.
Definition at line 95 of file KNNClassifier.cc.
TVec< string > PLearn::KNNClassifier::getTestCostNames | ( | ) | const [virtual] |
Returns the names of the costs computed by computeCostsFromOutpus (and thus the test method).
Implements PLearn::PLearner.
Definition at line 344 of file KNNClassifier.cc.
References PLearn::TVec< T >::length(), multi_k, and PLearn::tostring().
{ int n_multi_k = multi_k.length(); TVec<string> costs(2*(1+n_multi_k)); costs[0] = "class_error"; costs[1] = "neglogprob"; for(int k=0; k<n_multi_k; k++) { string kstr = tostring(multi_k[k]); costs[2+2*k] = "class_error_"+kstr; costs[3+2*k] = "neglogprob_"+kstr; } return costs; }
TVec< string > PLearn::KNNClassifier::getTrainCostNames | ( | ) | const [virtual] |
Returns the names of the objective costs that the train method computes and for which it updates the VecStatsCollector train_stats.
Implements PLearn::PLearner.
Definition at line 359 of file KNNClassifier.cc.
{
return TVec<string>();
}
void PLearn::KNNClassifier::makeDeepCopyFromShallowCopy | ( | CopiesMap & | copies | ) | [virtual] |
Transforms a shallow copy into a deep copy.
Reimplemented from PLearn::PLearner.
Definition at line 193 of file KNNClassifier.cc.
References class_weights, PLearn::deepCopyField(), kernel, knn, knn_costs, knn_output, PLearn::PLearner::makeDeepCopyFromShallowCopy(), multi_k, multi_k_input, and multi_k_output.
{ deepCopyField(knn_output, copies); deepCopyField(knn_costs, copies); deepCopyField(class_weights, copies); deepCopyField(multi_k_output,copies); deepCopyField(multi_k_input, copies); deepCopyField(knn, copies); deepCopyField(kernel, copies); deepCopyField(multi_k, copies); inherited::makeDeepCopyFromShallowCopy(copies); }
int PLearn::KNNClassifier::outputsize | ( | ) | const [virtual] |
Returns the size of this learner's output, (which typically may depend on its inputsize(), targetsize() and set options).
Implements PLearn::PLearner.
Definition at line 207 of file KNNClassifier.cc.
References nclasses.
Referenced by computeOutput().
{ return nclasses; }
Overridden to call knn->setTrainingSet.
Reimplemented from PLearn::PLearner.
Definition at line 213 of file KNNClassifier.cc.
References PLearn::PP< T >::isNotNull(), kernel, kmin, kmult, knn, knn_costs, knn_output, kpow, PLearn::VMat::length(), PLearn::max(), n, PLASSERT, PLearn::pow(), PLearn::TVec< T >::resize(), and PLearn::PLearner::setTrainingSet().
{ PLASSERT( knn ); inherited::setTrainingSet(training_set,call_forget); // Now we carry out a little bit of tweaking on the embedded knn: // - ask to output targets only // - set number of neighbors // - set training set (which performs a build if necessary) int n = training_set.length(); int num_neighbors = max(kmin, int(kmult*pow(double(n),double(kpow)))); knn->num_neighbors = num_neighbors; knn->copy_input = kernel.isNotNull(); knn->copy_target = true; knn->copy_weight = true; knn->copy_index = false; knn->setTrainingSet(training_set,call_forget); knn_costs.resize(num_neighbors); // Changed for compatibility with HyperLearner //knn_costs.resize(knn->nTestCosts()); knn_output.resize(knn->outputsize()); }
void PLearn::KNNClassifier::train | ( | ) | [virtual] |
Forwarded to knn.
Implements PLearn::PLearner.
Definition at line 241 of file KNNClassifier.cc.
References knn, PLASSERT, and PLearn::PLearner::train_set.
Reimplemented from PLearn::PLearner.
Definition at line 174 of file KNNClassifier.h.
Vec PLearn::KNNClassifier::class_weights [mutable, protected] |
Internal use: temporary buffer for cumulating class weights.
Definition at line 106 of file KNNClassifier.h.
Referenced by computeOutput(), and makeDeepCopyFromShallowCopy().
If use_knn_costs_as_weights is false, use this kernel to weight the observations.
If this object is not specified (default), the rectangular kernel is used. Disregard the 'use_knn_costs_as_weights' option, and use this kernel to weight the observations. If this object is not specified (default), and the 'use_knn_costs_as_weights' is false, the rectangular kernel is used.
Definition at line 152 of file KNNClassifier.h.
Referenced by computeOutput(), declareOptions(), makeDeepCopyFromShallowCopy(), and setTrainingSet().
Minimum number of neighbors to use (default=5)
Definition at line 130 of file KNNClassifier.h.
Referenced by build_(), declareOptions(), and setTrainingSet().
Multiplicative factor on n^kpow to determine number of neighbors to use (default=0)
Definition at line 134 of file KNNClassifier.h.
Referenced by declareOptions(), and setTrainingSet().
The K-nearest-neighbors finder to use (default is an ExhaustiveNearestNeighbors with a GaussianKernel, sigma=1)
Definition at line 124 of file KNNClassifier.h.
Referenced by build_(), computeOutput(), declareOptions(), forget(), makeDeepCopyFromShallowCopy(), setTrainingSet(), and train().
Vec PLearn::KNNClassifier::knn_costs [mutable, protected] |
Internal use: temporary buffer for knn costs.
Definition at line 103 of file KNNClassifier.h.
Referenced by computeOutput(), makeDeepCopyFromShallowCopy(), and setTrainingSet().
Vec PLearn::KNNClassifier::knn_output [mutable, protected] |
Internal use: temporary buffer for knn output.
Definition at line 100 of file KNNClassifier.h.
Referenced by computeOutput(), makeDeepCopyFromShallowCopy(), and setTrainingSet().
Power of the number of training examples to determine number of neighbors (default=0.5)
Definition at line 138 of file KNNClassifier.h.
Referenced by declareOptions(), and setTrainingSet().
This can be used if you wish to simultaneously compute the costs for several values of k, efficiently, while doing neighbors search a single time.
(see corresponding declareOption in .cc for more detailed info).
Definition at line 157 of file KNNClassifier.h.
Referenced by build_(), computeCostsFromOutputs(), computeOutput(), declareOptions(), getTestCostNames(), and makeDeepCopyFromShallowCopy().
Vec PLearn::KNNClassifier::multi_k_input [mutable, protected] |
Internal use to remember the input used in computeOutput when using multi_k option.
Definition at line 117 of file KNNClassifier.h.
Referenced by computeCostsFromOutputs(), computeOutput(), and makeDeepCopyFromShallowCopy().
Mat PLearn::KNNClassifier::multi_k_output [mutable, protected] |
Internal use: this is used when a multi_k option is provided to temporarily store the outputs the classifier would give for all values of k given in multi_k.
These outputs are computed by the computeOutput method, for consumption by the computeCostsFromOutputs method (whuch must be called right after).
Definition at line 114 of file KNNClassifier.h.
Referenced by computeCostsFromOutputs(), computeOutput(), and makeDeepCopyFromShallowCopy().
Number of classes in the problem.
Definition at line 127 of file KNNClassifier.h.
Referenced by build_(), computeOutput(), declareOptions(), and outputsize().
Whether to weigh each of the K neighbors by the kernel evaluations, obtained from the costs coming out of the 'knn' object (default=true)
Definition at line 142 of file KNNClassifier.h.
Referenced by computeOutput(), and declareOptions().