source: trunk/doc/concepts.doxygen @ 2338

Last change on this file since 2338 was 2338, checked in by Peter, 11 years ago

adding an archetype class for distance concept and use that class in KNN and NCC. Adding CopyConstructible? to requirement for Distance concept

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 13.8 KB
Line 
1// $Id: concepts.doxygen 2338 2010-10-16 05:00:12Z peter $
2//
3// Copyright (C) 2008 Jari Häkkinen, Peter Johansson, Markus Ringnér
4// Copyright (C) 2009, 2010 Peter Johansson
5//
6// This file is part of the yat library, http://dev.thep.lu.se/yat
7//
8// The yat library is free software; you can redistribute it and/or
9// modify it under the terms of the GNU General Public License as
10// published by the Free Software Foundation; either version 3 of the
11// License, or (at your option) any later version.
12//
13// The yat library is distributed in the hope that it will be useful,
14// but WITHOUT ANY WARRANTY; without even the implied warranty of
15// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16// General Public License for more details.
17//
18// You should have received a copy of the GNU General Public License
19// along with yat. If not, see <http://www.gnu.org/licenses/>.
20
21
22/**
23\page Concepts Concepts
24
25This page lists all the C++ concepts in the yat project.
26
27- \subpage concept_container_2d
28- \subpage concept_data_iterator
29- \subpage concept_distance
30- \subpage concept_mutable_container_2d
31- \subpage concept_neighbor_weighting
32- \subpage concept_weighted_iterator
33*/
34
35
36/**
37\page concept_container_2d Container2D
38
39\section Description
40
41\ref concept_container_2d is a <a
42href="http://www.sgi.com/tech/stl/Container.html">Container</a> that
43stores elements in a two-dimensional array (columns and rows). It
44provides element access of a specific row and column, as well
45as iterators that can be used to iterate over a specific column or
46row.
47
48\section Requirements
49
50A \ref concept_container_2d provides the following:
51
52\subsection Types
53
54<table cellspacing=0 border=1>
55<tr><td>Value type</td><td><tt>X::value_type</tt></td>
56<td>Type of element stored in Container.</td>
57</tr>
58<tr><td>Const reference type</td><td><tt>X::const_reference</tt></td>
59<td>A type that behaves as const reference to the \ref
60concept_container_2d 's value type.</td>
61</tr>
62<tr>
63<td>Const iterator type</td>
64<td><tt>X::const_iterator</tt></td> 
65<td>
66A read-only iterator that can be used to iterate over the entire \ref
67concept_container_2d. Typically the iterator iterates along a
68row, and when the end of one row is reached it jumps to the
69beginning of the next row.
70</td>
71</tr>
72<tr>
73<td>Const column iterator type</td>
74<td><tt>X::const_column_iterator</tt></td> 
75<td>
76A read-only iterator that can be used to examine the elements in one
77column of the \ref concept_container_2d.
78</td>
79</tr>
80<tr>
81<td>Const row iterator type</td>
82<td><tt>X::const_row_iterator</tt></td> 
83<td>
84A read-only iterator that can be used to examine the elements in one
85row of the \ref concept_container_2d.
86</td>
87</tr>
88</table>
89
90\subsection public_functions Public Functions
91
92<table cellspacing=0 border=1>
93<tr>
94<th>Name</th><th>Expression</th><th>Precondition</th><th>Return type</th>
95<th>Postcondition</th>
96</tr>
97<tr>
98<td>Beginning of range</td>
99<td><tt>a.begin()</tt></td>
100<td>&nbsp;</td>
101<td><tt>const_iterator</tt></td>
102<td>&nbsp;</td>
103</tr>
104<tr>
105<td>Beginning of column</td>
106<td><tt>a.begin_column(size_t column)</tt></td>
107<td><tt>0 &lt;= column &lt; a.columns()</tt></td>
108<td><tt>const_column_iterator</tt></td>
109<td>&nbsp;</td>
110</tr>
111<tr>
112<td>Beginning of row</td>
113<td><tt>a.begin_row(size_t row)</tt></td>
114<td><tt>0 &lt;= row &lt; a.rows()</tt></td>
115<td><tt>const_row_iterator</tt></td>
116<td>&nbsp;</td>
117</tr>
118<tr>
119<td>End of range</td>
120<td><tt>a.end()</tt></td>
121<td>&nbsp;</td>
122<td><tt>const_iterator</tt></td>
123<td>&nbsp;</td>
124</tr>
125<tr>
126<td>End of column</td>
127<td><tt>a.end_column(size_t column)</tt></td>
128<td><tt>0 &lt;= column &lt; a.columns()</tt></td>
129<td><tt>const_column_iterator</tt></td>
130<td>&nbsp;</td>
131</tr>
132<tr>
133<td>End of row</td>
134<td><tt>a.end_row(size_t row)</tt></td>
135<td><tt>0 &lt;= row &lt; a.rows()</tt></td>
136<td><tt>const_row_iterator</tt></td>
137<td>&nbsp;</td>
138</tr>
139<tr>
140<td>Columns</td>
141<td><tt>a.columns()</tt></td>
142<td>&nbsp;</td>
143<td><tt>size_t</tt></td>
144<td>&nbsp;</td>
145</tr>
146<tr>
147<td>Rows</td>
148<td><tt>a.rows()</tt></td>
149<td>&nbsp;</td>
150<td><tt>size_t</tt></td>
151<td>&nbsp;</td>
152</tr>
153<tr>
154<td>Element Access</td>
155<td><tt>a(size_t row, size_t column)</tt></td>
156<td><tt>0 &lt;= row &lt; a.rows()</tt> and
157<tt>0 &lt;= column &lt; a.columns()</tt></td>
158<td><tt>const_reference</tt></td>
159<td>&nbsp;</td>
160</tr>
161</table>
162
163\section Implementations
164
165Examples of concept \ref concept_container_2d include:
166  - theplu::yat::classifier::MatrixLookup,
167  - theplu::yat::classifier::MatrixLookupWeighted
168  - theplu::yat::classifier::KernelLookup.
169
170*/
171
172/**
173\page concept_mutable_container_2d Mutable Container2D
174
175\section Description
176
177\ref concept_mutable_container_2d is a \ref concept_container_2d that
178also provides non-const access to its elements.
179
180\section Requirements
181
182In addition to the requirements defined in \ref concept_container_2d,
183a \ref concept_mutable_container_2d also provides the following:
184
185\subsection Types
186
187<table cellspacing=0 border=1>
188<tr><td>Reference type</td><td><tt>X::reference</tt></td>
189<td>A type that behaves as reference to the \ref
190concept_mutable_container_2d 's value type.</td>
191</tr>
192<tr>
193<td>Iterator type</td>
194<td><tt>X::iterator</tt></td> 
195<td>
196
197A mutable iterator similar to Const iterator type, which can be used to
198iterate over the \ref concept_mutable_container_2d (and modify the
199elements). Typically the iterator iterates along a row, and when the
200end of one row is reached it jumps to the beginning of the next row.
201
202</td>
203</tr>
204<tr>
205<td>Column iterator type</td>
206<td><tt>X::column_iterator</tt></td> 
207<td>
208A mutable iterator that can be used to modify the elements in one
209column of the \ref concept_mutable_container_2d.
210</td>
211</tr>
212<tr>
213<td>Row iterator type</td>
214<td><tt>X::row_iterator</tt></td> 
215<td>
216A mutable iterator that can be used to modify the elements in one
217row of the \ref concept_mutable_container_2d.
218</td>
219</tr>
220</table>
221
222\subsection public_functions Public Functions
223
224<table cellspacing=0 border=1>
225<tr>
226<th>Name</th><th>Expression</th><th>Precondition</th><th>Return type</th>
227<th>Postcondition</th>
228</tr>
229<tr>
230<td>Beginning of range</td>
231<td><tt>a.begin()</tt></td>
232<td>&nbsp;</td>
233<td><tt>iterator</tt></td>
234<td><tt>iterator</tt> is derefenceable, unless <tt>a</tt> is empty</td>
235</tr>
236<tr>
237<td>Beginning of column</td>
238<td><tt>a.begin_column(size_t column)</tt></td>
239<td><tt>0 &lt;= column &lt; a.columns()</tt></td>
240<td><tt>column_iterator</tt></td>
241<td><tt>column_iterator</tt> is derefenceable, unless <tt>a</tt> is empty</td>
242</tr>
243<tr>
244<td>Beginning of row</td>
245<td><tt>a.begin_row(size_t row)</tt></td>
246<td><tt>0 &lt;= row &lt; a.rows()</tt></td>
247<td><tt>row_iterator</tt></td>
248<td><tt>row_iterator</tt> is derefenceable, unless <tt>a</tt> is empty</td>
249</tr>
250<tr>
251<td>End of range</td>
252<td><tt>a.end()</tt></td>
253<td>&nbsp;</td>
254<td><tt>iterator</tt></td>
255<td>&nbsp;</td>
256</tr>
257<tr>
258<td>End of column</td>
259<td><tt>a.end_column(size_t column)</tt></td>
260<td><tt>column&lt;a.columns()</tt></td>
261<td><tt>column_iterator</tt></td>
262<td>&nbsp;</td>
263</tr>
264<tr>
265<td>End of row</td>
266<td><tt>a.end_row(size_t row)</tt></td>
267<td><tt>row&lt;a.rows()</tt></td>
268<td><tt>row_iterator</tt></td>
269<td>&nbsp;</td>
270</tr>
271<tr>
272<td>Element Access</td>
273<td><tt>a(size_t row, size_t column)</tt></td>
274<td><tt>0 &lt;= row &lt; a.rows()</tt> and
275<tt>0 &lt;= column &lt; a.columns()</tt></td>
276<td><tt>reference</tt></td>
277<td>&nbsp;</td>
278</tr>
279</table>
280
281\section Implementations
282
283Examples of concept \ref concept_mutable_container_2d include:
284  - theplu::yat::utility::Matrix,
285  - theplu::yat::utility::MatrixWeighted
286
287*/
288
289/**
290\page concept_distance Distance
291
292\section Description
293
294\ref concept_distance is a concept for classes implementing different
295alternatives to calculate the distance between two points.
296
297\section Requirements
298
299Classes modelling the concept \ref concept_distance should have a copy
300constructor
301
302\verbatim
303Distance(const Distance& d);
304\endverbatim
305
306and also implement the following public function:
307
308\verbatim
309template<typename Iter1, typename Iter2>
310double  operator() (Iter1 beg1, Iter1 end1, Iter2 beg2) const
311\endverbatim
312
313This function should calculate and return the distance between
314elements of two ranges. The first range is given by [\a beg1, \a end1)
315and the second range starts with \a beg2 and has the same length as
316the first range. The function should support iterators of the category
317std::forward_iterator. The function should provide both a fast
318calculation for unweighted iterators and a calculation for weighted
319iterators. The latter correspond to the case where elements in a range
320have both a value and a weight. The selection between unweighted and
321weighted implementations should utilize
322theplu::yat::utility::unweighted_iterator_tag and
323theplu::yat::utility::weighted_iterator_tag. Moreover
324theplu::yat::utility::weighted_if_any2 should be utilized to provide a
325weighted implementation if any of the two ranges is weighted, and an
326unweighted implementation when both ranges are unweighted.
327
328\section Implementations
329
330Examples of classes modelling the concept \ref concept_distance
331include theplu::yat::statistics::PearsonDistance and
332theplu::yat::statistics::EuclideanDistance.
333
334\see \ref weighted_distance
335
336*/
337
338/**
339\page concept_neighbor_weighting Neighbor Weighting Method
340
341\section Description
342
343\ref concept_neighbor_weighting is a concept used in connection with
344theplu::yat::classifier::KNN - classes used as the template argument
345NeighborWeighting should implement this concept.
346
347\section Requirements
348
349Classes modelling the concept \ref concept_neighbor_weighting should
350implement the following public function:
351 
352\verbatim   
353void operator()(const utility::VectorBase& distance,
354                const std::vector<size_t>& k_sorted,
355                const Target& target,
356                utility::VectorMutable& prediction) const
357\endverbatim
358
359For a test sample, this function should calculate a total vote
360(i.e. based on all k nearest neighbors) for each class. The vector \a
361distance contains the distances from a test sample to all training
362samples. The vector \a k_sorted contains the indices (for both \a
363distance and \a target) to the k training samples with the smallest
364distances to the test sample. The class for each training sample is
365given by \a target, which is sorted in the same sample order as \a
366distance. For each class the function calculates a total vote based on
367the the nearest neighbors of the test sample that belong to the
368class. The total vote for each class is stored in the vector \a
369prediction.  The function should be implemented such that nearest
370neighbors with distance infinity do not vote.
371
372\section Implementations
373
374Examples of classes modelling the concept \ref
375concept_neighbor_weighting include
376theplu::yat::classifier::KNN_Uniform,
377theplu::yat::classifier::KNN_ReciprocalDistance and
378theplu::yat::classifier::KNN_ReciprocalRank.
379
380*/
381
382/**
383\page concept_weighted_iterator Weighted Iterator
384
385\section Description
386
387Most functionality in yat come in two versions: one optimized for
388speed and one weighted version allowing for missing value (see \ref
389weighted_statistics). For example, weighted containers such as
390theplu::yat::utility::MatrixWeighted and
391theplu::yat::classifier::MatrixLookupWeighted allow an easy way to
392handle missing values. Iterators that iterate over such weighted
393containers are by definition \ref concept_weighted_iterator. This
394concept is orthogonal against other iterator concepts such as Random
395Access Iterator.
396
397\section Requirements
398
399When implementing a new iterator that may be a \ref
400concept_weighted_iterator, there are a few things to concider.
401
402\subsection weighted_iterator_traits
403
404To decide whether an iterator is weighted, there exists a
405meta-function
406theplu::yat::utility::weighted_iterator_traits<Iterator>::type that
407will return either theplu::yat::utility::weighted_iterator_tag or
408theplu::yat::utility::unweighted_iterator_tag. The default
409implementation of this meta-function works in most cases, including on
410all std::iterators, but if you implement a new iterator make sure it
411behaves as you desire, or you need to create a specialization.
412
413\subsection iterator_traits
414
415Sometimes it is useful to have unweighted iterators behaving as though
416they were weighted. For instance,
417theplu::yat::statistics::EuclideanDistance calculates the distance
418between two ranges. If both ranges are unweighted the unweighted
419version is used, and when any of the two ranges is weighted the
420weighted version kicks in. In order to make this work also when
421comparing weighted and unweighted ranges, there must a mechanism to
422let the unweighted iterator behave as though it were weighted.
423
424This can be accomplished through
425theplu::yat::utility::iterator_traits, which enables access to data
426value as well as to weight value. For unweighted iterators the weight
427value is always equal to 1.0 and is not mutable. The default
428implementation works for most iterators including all unweighted, but
429if you implement a new weighted iterator you need to check that the
430default implementation will work for you (see class
431documentation). Otherwise, you will need to implement a
432specialization. Note that the default implementation requires that, if
433\c iterator is a weighted iterator, its \c reference must have
434member functions data() and weight(). This should not be a problem as
435long as \c reference is theplu::yat::utility::DataWeight or
436theplu::yat::utility::DataWeightProxy, but could potentially be a
437problem when creating weighted iterators with other \c reference.
438
439*/
440
441/**
442\page concept_data_iterator Data Iterator
443
444\section Description
445
446\ref concept_data_iterator is an iterator that comes in two shapes:
447
448  - it is either a \ref concept_weighted_iterator with value type
449convertible to theplu::yat::utility::DataWeight
450  - it is an unweighted iterator with value type
451convertible to \c double.
452
453\section Implementations
454
455Examples of concept \ref concept_data_iterator include:
456  - theplu::yat::utility::Matrix::iterator,
457  - theplu::yat::utility::MatrixWeighted::iterator,
458  - theplu::yat::classifier::MatrixLookup::const_iterator,
459  - theplu::yat::classifier::MatrixLookupWeighted::const_iterator
460*/
Note: See TracBrowser for help on using the repository browser.