| 1 | // $Id: concepts.doxygen 1156 2008-02-26 08:46:49Z markus $ |
|---|
| 2 | // |
|---|
| 3 | // Copyright (C) 2008 Peter Johansson, Markus Ringnér |
|---|
| 4 | // |
|---|
| 5 | // This file is part of the yat library, http://trac.thep.lu.se/yat |
|---|
| 6 | // |
|---|
| 7 | // The yat library is free software; you can redistribute it and/or |
|---|
| 8 | // modify it under the terms of the GNU General Public License as |
|---|
| 9 | // published by the Free Software Foundation; either version 2 of the |
|---|
| 10 | // License, or (at your option) any later version. |
|---|
| 11 | // |
|---|
| 12 | // The yat library is distributed in the hope that it will be useful, |
|---|
| 13 | // but WITHOUT ANY WARRANTY; without even the implied warranty of |
|---|
| 14 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
|---|
| 15 | // General Public License for more details. |
|---|
| 16 | // |
|---|
| 17 | // You should have received a copy of the GNU General Public License |
|---|
| 18 | // along with this program; if not, write to the Free Software |
|---|
| 19 | // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA |
|---|
| 20 | // 02111-1307, USA. |
|---|
| 21 | |
|---|
| 22 | |
|---|
| 23 | /** |
|---|
| 24 | \page Concepts Concepts |
|---|
| 25 | |
|---|
| 26 | This page lists all the C++ concepts in the yat project. |
|---|
| 27 | |
|---|
| 28 | - \subpage concept_distance |
|---|
| 29 | - \subpage concept_neighbor_weighting |
|---|
| 30 | */ |
|---|
| 31 | |
|---|
| 32 | |
|---|
| 33 | /** |
|---|
| 34 | \page concept_distance Distance |
|---|
| 35 | |
|---|
| 36 | \section Description |
|---|
| 37 | |
|---|
| 38 | \ref concept_distance is a concept for classes implementing different |
|---|
| 39 | alternatives to calculate the distance between two points. |
|---|
| 40 | |
|---|
| 41 | \section Requirements |
|---|
| 42 | |
|---|
| 43 | Classes modelling the concept \ref concept_distance should implement |
|---|
| 44 | the following public function: |
|---|
| 45 | |
|---|
| 46 | \verbatim |
|---|
| 47 | template<typename Iter1, typename Iter2> |
|---|
| 48 | double operator() (Iter1 beg1, Iter1 end1, Iter2 beg2) const |
|---|
| 49 | \endverbatim |
|---|
| 50 | |
|---|
| 51 | This function should calculate and return the distance between |
|---|
| 52 | elements of two ranges. The first range is given by [\a beg1, \a end1) |
|---|
| 53 | and the second range starts with \a beg2 and has the same length as |
|---|
| 54 | the first range. The function should support iterators of the category |
|---|
| 55 | std::forward_iterator. The function should provide both a fast |
|---|
| 56 | calculation for unweighted iterators and a calculation for weighted |
|---|
| 57 | iterators. The latter correspond to the case where elements in a range |
|---|
| 58 | have both a value and a weight. The selection between unweighted and |
|---|
| 59 | weighted implementations should utilize |
|---|
| 60 | theplu::yat::utility::weighted_iterator_tag. Moreover |
|---|
| 61 | theplu::yat::utility::weighted_if_any2 should be utilized to provide a |
|---|
| 62 | weighted implementation if any of the two ranges is weighted, and an |
|---|
| 63 | unweighted implementation when both ranges are unweighted. |
|---|
| 64 | |
|---|
| 65 | \section Implementations |
|---|
| 66 | |
|---|
| 67 | Examples of classes modelling the concept \ref concept_distance |
|---|
| 68 | include theplu::yat::statistics::PearsonDistance and |
|---|
| 69 | theplu::yat::statistics::EuclideanDistance. |
|---|
| 70 | |
|---|
| 71 | */ |
|---|
| 72 | |
|---|
| 73 | /** |
|---|
| 74 | \page concept_neighbor_weighting Neighbor Weighting Method |
|---|
| 75 | |
|---|
| 76 | \section Description |
|---|
| 77 | |
|---|
| 78 | \ref concept_neighbor_weighting is a concept used in connection with |
|---|
| 79 | theplu::yat::classifier::KNN - classes used as the template argument |
|---|
| 80 | NeighborWeighting should implement this concept. |
|---|
| 81 | |
|---|
| 82 | \section Requirements |
|---|
| 83 | |
|---|
| 84 | Classes modelling the concept \ref concept_neighbor_weighting should |
|---|
| 85 | implement the following public function: |
|---|
| 86 | |
|---|
| 87 | \verbatim |
|---|
| 88 | void operator()(const utility::VectorBase& distance, const std::vector<size_t> k_sorted, |
|---|
| 89 | const Target& target, utility::VectorMutable& prediction) const |
|---|
| 90 | \endverbatim |
|---|
| 91 | |
|---|
| 92 | For a test sample, this function should calculate a total vote |
|---|
| 93 | (i.e. based on all k nearest neighbors) for each class. The vector \a |
|---|
| 94 | distance contains the distances from a test sample to all training |
|---|
| 95 | samples. The vector \a k_sorted contains the indices (for both \a |
|---|
| 96 | distance and \a target) to the k training samples with the smallest |
|---|
| 97 | distances to the test sample. The class for each training sample is |
|---|
| 98 | given by \a target, which is sorted in the same sample order as \a |
|---|
| 99 | distance. For each class the function calculates a total vote based on |
|---|
| 100 | the the nearest neighbors of the test sample that belong to the |
|---|
| 101 | class. The total vote for each class is stored in the vector \a |
|---|
| 102 | prediction. The function should be implemented such that nearest |
|---|
| 103 | neighbors with distance infinity do not vote. |
|---|
| 104 | |
|---|
| 105 | \section Implementations |
|---|
| 106 | |
|---|
| 107 | Examples of classes modelling the concept \ref |
|---|
| 108 | concept_neighbor_weighting include |
|---|
| 109 | theplu::yat::classifier::KNN_Uniform, |
|---|
| 110 | theplu::yat::classifier::KNN_ReciprocalDistance and |
|---|
| 111 | theplu::yat::classifier::KNN_ReciprocalRank. |
|---|
| 112 | |
|---|
| 113 | */ |
|---|
