PLearn 0.1
Public Member Functions | Static Public Member Functions | Public Attributes | Static Public Attributes | Static Protected Member Functions | Protected Attributes | Private Types | Private Member Functions
PLearn::KNNClassifier Class Reference

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>

Inheritance diagram for PLearn::KNNClassifier:
Inheritance graph
[legend]
Collaboration diagram for PLearn::KNNClassifier:
Collaboration graph
[legend]

List of all members.

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 OptionListgetOptionList () const
virtual OptionMapgetOptionMap () const
virtual RemoteMethodMapgetRemoteMethodMap () const
virtual KNNClassifierdeepCopy (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 PPathdeclaringFile ()

Public Attributes

PP< GenericNearestNeighborsknn
 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< intmulti_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.

Detailed Description

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.


Member Typedef Documentation

Reimplemented from PLearn::PLearner.

Definition at line 96 of file KNNClassifier.h.


Constructor & Destructor Documentation

PLearn::KNNClassifier::KNNClassifier ( )

Default constructor.

Definition at line 97 of file KNNClassifier.cc.

    : 
      nclasses(-1),
      kmin(5),
      kmult(0.0),
      kpow(0.5),
      use_knn_costs_as_weights(true),
      kernel()
{ }

Member Function Documentation

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.

bool PLearn::KNNClassifier::_isa_ ( const Object o) [static]

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_().

Here is the call graph for this function:

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");

}

Here is the call graph for this function:

Here is the caller graph for this function:

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]);
    }
}

Here is the call graph for this function:

void PLearn::KNNClassifier::computeOutput ( const Vec input,
Vec output 
) const [virtual]

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());
}

Here is the call graph for this function:

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);
}

Here is the call graph for this function:

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.

References knn, and PLASSERT.

{
    PLASSERT( knn );
    knn->forget();
}
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;
}

Here is the call graph for this function:

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.

Here is the call graph for this function:

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;
}

Here is the caller graph for this function:

void PLearn::KNNClassifier::setTrainingSet ( VMat  training_set,
bool  call_forget = true 
) [virtual]

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());
}

Here is the call graph for this function:

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.

{
    PLASSERT( knn );
    knn->distance_kernel->train(train_set);
    knn->train();
}

Member Data Documentation

Reimplemented from PLearn::PLearner.

Definition at line 174 of file KNNClassifier.h.

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().

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().

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().


The documentation for this class was generated from the following files:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines