Implements k-Nearest Neighbor classifier. More...

#include <classifier_knn.hpp>

Inheritance diagram for FST::Classifier_kNN< RETURNTYPE, DATATYPE, IDXTYPE, DIMTYPE, SUBSET, DATAACCESSOR, DISTANCE >:

Classes
class	Neighbour
	Holds information on distance and data-class membership of neighbors processed in Classifier_kNN. More...

Public Types
typedef Classifier< RETURNTYPE, DIMTYPE, SUBSET, DATAACCESSOR >	parent
	the immediate abstract base
typedef Clonable_Impl< Classifier_kNN, parent >	parent_impl
	implements clone(); sharing/stateless_clone throw in Classifier
typedef std::shared_ptr< DATAACCESSOR >	PDataAccessor
	shared pointer to the data accessor supplying train/test blocks
typedef std::shared_ptr< SUBSET >	PSubset
	shared pointer to the feature subset being trained/evaluated on
typedef DATAACCESSOR::PPattern	PPattern
	one data sample as exposed by DATAACCESSOR (a raw pointer to its feature vector)
Public Types inherited from FST::Classifier< RETURNTYPE, DIMTYPE, SUBSET, DATAACCESSOR >
typedef std::shared_ptr< DATAACCESSOR >	PDataAccessor
	shared pointer to the data accessor supplying train/test blocks
typedef std::shared_ptr< SUBSET > const	PSubset
	shared pointer to the (fixed, non-reassignable) feature subset being evaluated
typedef DATAACCESSOR::PPattern	PPattern
	one data sample as exposed by DATAACCESSOR (a raw pointer to its feature vector)

Public Member Functions
void	set_k (const DIMTYPE k)
	sets the number of nearest neighbours collected and voted over; `k` must be > 0
DIMTYPE	get_k () const
	the k set by set_k() (default 1)
virtual bool	classify (DIMTYPE &cls, const PPattern &pattern) override
virtual bool	classify_scores (std::vector< RETURNTYPE > &scores, const PPattern &pattern) override
virtual bool	train (const PDataAccessor da, const PSubset sub) override
virtual std::ostream &	print (std::ostream &os) const override
	writes a human-readable identification of the object; base default writes nothing
Public Member Functions inherited from FST::Clonable_Impl< Classifier_kNN< RETURNTYPE, DATATYPE, IDXTYPE, DIMTYPE, SUBSET, DATAACCESSOR, DISTANCE >, Classifier< RETURNTYPE, DIMTYPE, SUBSET, DATAACCESSOR > >
Classifier< RETURNTYPE, DIMTYPE, SUBSET, DATAACCESSOR > *	clone () const override
	dispatches to the DEEP_KIND mechanism (default CLONE_DEEP: Derived's copy-constructor)
Classifier< RETURNTYPE, DIMTYPE, SUBSET, DATAACCESSOR > *	sharing_clone () const override
	dispatches to the SHARING_KIND mechanism (default CLONE_INHERIT: defers to Base, which throws by family convention)
Classifier< RETURNTYPE, DIMTYPE, SUBSET, DATAACCESSOR > *	stateless_clone () const override
	dispatches to the STATELESS_KIND mechanism (default CLONE_INHERIT: defers to Base, which throws by family convention)
Public Member Functions inherited from FST::Classifier< RETURNTYPE, DIMTYPE, SUBSET, DATAACCESSOR >
virtual bool	train (const PDataAccessor da, const PSubset sub)=0
	learns from designated training part of data
virtual bool	test (RETURNTYPE &result, const PDataAccessor da)
virtual bool	test_confusion (std::vector< RETURNTYPE > &confusion, DIMTYPE &classes, const PDataAccessor da)
virtual bool	test_scores (std::vector< std::pair< RETURNTYPE, DIMTYPE > > &scores, const PDataAccessor da)
virtual bool	test_scores_matrix (std::vector< RETURNTYPE > &scores, std::vector< DIMTYPE > &labels, DIMTYPE &classes, const PDataAccessor da)
virtual bool	test_metric (RETURNTYPE &result, const PDataAccessor da, const Metric_Spec< RETURNTYPE > &spec)
Public Member Functions inherited from FST::Clonable
bool	is_clone () const
bool	is_sharing () const
	true if this instance is a sharing_clone() result (referencing, not owning, the source's structures)
bool	is_sharing_clone () const
	true if this instance is BOTH a clone and sharing – i.e. specifically a sharing_clone() result, not a clone()/stateless_clone() one

Protected Member Functions
void	collect_neighbours (const PPattern &pattern)
void	sort_in (const RETURNTYPE value, const DIMTYPE cls)
Protected Member Functions inherited from FST::Clonable
void	set_cloned (const bool cloned=true)
	marks/unmarks this instance as a clone; call from clone()/stateless_clone() overrides (Clonable_Impl does this automatically)
void	set_sharing (const bool sharing=true)
	marks/unmarks this instance as sharing (see is_sharing())
void	set_sharing_cloned (const bool cloned=true, const bool sharing=true)
	sets both flags at once; call from sharing_clone() overrides (Clonable_Impl does this automatically)

Protected Attributes
DIMTYPE	_k
	number of nearest neighbours voted over; set by set_k()
DIMTYPE	_nns_max_size
	cap on _nns's size while collecting neighbours: k, the number voted over
std::list< Neighbour >::iterator	iter
	scratch iterator used internally by sort_in() to walk _nns during insertion
std::list< Neighbour >	_nns
	implemented descending ... the closest neighbour is the last
std::vector< RETURNTYPE >	_cs_sc
	classify() score scratch (member to avoid per-pattern allocation)
std::unique_ptr< DISTANCE >	_distance
	distance metric narrowed to the trained subspace; allocated/renarrowed by train()
PDataAccessor	_da_train
	training data accessor cached by train() (kNN has no real training step); enumerated as neighbours by collect_neighbours()

Private Member Functions
	Classifier_kNN (const Classifier_kNN &cknn)
	copy-constructor (clones _distance if allocated; _nns/_k/_nns_max_size are value-copied)

Private Attributes
friend	parent_impl
	grants Clonable_Impl access to the copy-constructor

Detailed Description

template<class RETURNTYPE, typename DATATYPE, typename IDXTYPE, typename DIMTYPE, class SUBSET, class DATAACCESSOR, class DISTANCE>
class FST::Classifier_kNN< RETURNTYPE, DATATYPE, IDXTYPE, DIMTYPE, SUBSET, DATAACCESSOR, DISTANCE >

Implements k-Nearest Neighbor classifier.

The decision rule: collect the k training patterns nearest to the classified pattern under the supplied DISTANCE, count the class votes among them, and take the argmax; the first maximum wins, i.e. ties are resolved in favour of the lowest class index. classify() and classify_scores() implement the same rule - classify() is the argmax of the vote fractions classify_scores() returns - so accuracy, the confusion matrix and the ranking metrics (AUC, ROC) all describe one and the same classifier.

Examples: demo10.cpp, demo52t.cpp, and demo55.cpp.