<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>3.4. Nearest Neighbors — scikits.learn v0.6.0 documentation</title>
<link rel="stylesheet" href="../_static/nature.css" type="text/css" />
<link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
<script type="text/javascript">
var DOCUMENTATION_OPTIONS = {
URL_ROOT: '../',
VERSION: '0.6.0',
COLLAPSE_INDEX: false,
FILE_SUFFIX: '.html',
HAS_SOURCE: true
};
</script>
<script type="text/javascript" src="../_static/jquery.js"></script>
<script type="text/javascript" src="../_static/underscore.js"></script>
<script type="text/javascript" src="../_static/doctools.js"></script>
<link rel="shortcut icon" href="../_static/favicon.ico"/>
<link rel="author" title="About these documents" href="../about.html" />
<link rel="top" title="scikits.learn v0.6.0 documentation" href="../index.html" />
<link rel="up" title="3. Supervised learning" href="../supervised_learning.html" />
<link rel="next" title="3.5. Feature selection" href="feature_selection.html" />
<link rel="prev" title="3.3. Stochastic Gradient Descent" href="sgd.html" />
</head>
<body>
<div class="header-wrapper">
<div class="header">
<p class="logo"><a href="../index.html">
<img src="../_static/scikit-learn-logo-small.png" alt="Logo"/>
</a>
</p><div class="navbar">
<ul>
<li><a href="../install.html">Download</a></li>
<li><a href="../support.html">Support</a></li>
<li><a href="../user_guide.html">User Guide</a></li>
<li><a href="../auto_examples/index.html">Examples</a></li>
<li><a href="../developers/index.html">Development</a></li>
</ul>
<div class="search_form">
<div id="cse" style="width: 100%;"></div>
<script src="http://www.google.com/jsapi" type="text/javascript"></script>
<script type="text/javascript">
google.load('search', '1', {language : 'en'});
google.setOnLoadCallback(function() {
var customSearchControl = new google.search.CustomSearchControl('016639176250731907682:tjtqbvtvij0');
customSearchControl.setResultSetSize(google.search.Search.FILTERED_CSE_RESULTSET);
var options = new google.search.DrawOptions();
options.setAutoComplete(true);
customSearchControl.draw('cse', options);
}, true);
</script>
</div>
</div> <!-- end navbar --></div>
</div>
<div class="content-wrapper">
<!-- <div id="blue_tile"></div> -->
<div class="sphinxsidebar">
<div class="rel">
<a href="sgd.html" title="3.3. Stochastic Gradient Descent"
accesskey="P">previous</a> |
<a href="feature_selection.html" title="3.5. Feature selection"
accesskey="N">next</a> |
<a href="../genindex.html" title="General Index"
accesskey="I">index</a>
</div>
<h3>Contents</h3>
<ul>
<li><a class="reference internal" href="#">3.4. Nearest Neighbors</a><ul>
<li><a class="reference internal" href="#classification">3.4.1. Classification</a></li>
<li><a class="reference internal" href="#regression">3.4.2. Regression</a></li>
<li><a class="reference internal" href="#efficient-implementation-the-ball-tree">3.4.3. Efficient implementation: the ball tree</a></li>
</ul>
</li>
</ul>
</div>
<div class="content">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body">
<div class="section" id="nearest-neighbors">
<h1>3.4. Nearest Neighbors<a class="headerlink" href="#nearest-neighbors" title="Permalink to this headline">¶</a></h1>
<p>The principle behind nearest neighbor methods is to find the k
training points closest in euclidean distance to x0, and then classify
using a majority vote among the k neighbors.</p>
<p>Despite its simplicity, nearest neighbors has been successful in a
large number of classification problems, including handwritten digits
or satellite image scenes. It is ofter successful in situation where
the decision boundary is very irregular.</p>
<div class="section" id="classification">
<h2>3.4.1. Classification<a class="headerlink" href="#classification" title="Permalink to this headline">¶</a></h2>
<p>The <tt class="xref py py-class docutils literal"><span class="pre">Neighbors</span></tt> estimators implements the nearest-neighbors
classification method using a vote heuristic: the class most present in
the k nearest neighbors of a point is assigned to this point.</p>
<div class="figure align-center">
<a class="reference external image-reference" href="../auto_examples/plot_neighbors.html"><img alt="auto_examples/images/plot_neighbors.png" src="auto_examples/images/plot_neighbors.png" /></a>
</div>
<div class="topic">
<p class="topic-title first">Examples:</p>
<ul class="simple">
<li><a class="reference internal" href="../auto_examples/plot_neighbors.html#example-plot-neighbors-py"><em>Nearest Neighbors</em></a>: an example of classification
using nearest neighbor.</li>
</ul>
</div>
</div>
<div class="section" id="regression">
<h2>3.4.2. Regression<a class="headerlink" href="#regression" title="Permalink to this headline">¶</a></h2>
<p>The <tt class="xref py py-class docutils literal"><span class="pre">NeighborsBarycenter</span></tt> estimator implements a nearest-neighbors
regression method using barycenter weighting of the targets of the
k-neighbors.</p>
<div class="figure align-center">
<a class="reference external image-reference" href="../auto_examples/plot_neighbors_regression.html"><img alt="auto_examples/images/plot_neighbors_regression.png" src="auto_examples/images/plot_neighbors_regression.png" /></a>
</div>
<div class="topic">
<p class="topic-title first">Examples:</p>
<ul class="simple">
<li><a class="reference internal" href="../auto_examples/plot_neighbors_regression.html#example-plot-neighbors-regression-py"><em>k-Nearest Neighbors regression</em></a>: an example of regression
using nearest neighbor.</li>
</ul>
</div>
</div>
<div class="section" id="efficient-implementation-the-ball-tree">
<h2>3.4.3. Efficient implementation: the ball tree<a class="headerlink" href="#efficient-implementation-the-ball-tree" title="Permalink to this headline">¶</a></h2>
<p>Behind the scenes, nearest neighbor search is done by the object
<tt class="xref py py-class docutils literal"><span class="pre">BallTree</span></tt>, which is a fast way to perform neighbor searches in data
sets of very high dimensionality.</p>
<p>This class provides an interface to an optimized BallTree
implementation to rapidly look up the nearest neighbors of any point.
Ball Trees are particularly useful for very high-dimensionality data,
where more traditional tree searches (e.g. KD-Trees) perform poorly.</p>
<p>The cost is a slightly longer construction time, though for repeated
queries, this added construction time quickly becomes insignificant.</p>
<p>A Ball Tree reduces the number of candidate points for a neighbor search
through use of the triangle inequality:</p>
<div class="math">
<p><span class="math">|x+y| \leq |x| + |y|</span></p>
</div><p>Each node of the <tt class="xref py py-class docutils literal"><span class="pre">BallTree</span></tt> defines a centroid, C, and a radius r such
that each point in the node lies within the hyper-sphere of radius r,
centered at C. With this setup, a single distance calculation between
a test point and the centroid is sufficient to determine a lower bound
on the distance to all points within the node. Carefully taking
advantage of this property leads to determining neighbors in O[log(N)]
time, as opposed to O[N] time for a brute-force search.</p>
<p>A pure C implementation of brute-force search is also provided in
function <tt class="xref py py-func docutils literal"><span class="pre">knn_brute()</span></tt>.</p>
<div class="topic">
<p class="topic-title first">References:</p>
<ul class="simple">
<li><a class="reference external" href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.8209&rep=rep1&type=pdf">“Five balltree construction algorithms”</a>,
Omohundro, S.M., International Computer Science Institute
Technical Report</li>
</ul>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="clearer"></div>
</div>
</div>
<div class="footer">
<p style="text-align: center">This documentation is relative
to scikits.learn version 0.6.0<p>
© 2010, scikits.learn developers (BSD Lincense).
Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 1.0.5. Design by <a href="http://webylimonada.com">Web y Limonada</a>.
</div>
</body>
</html>
distrib
>
Mandriva
>
2010.2
>
i586
>
media
>
contrib-backports
>
by-pkgid
>
e578866d55cd81fdb23827cdf3cec911
>
files
>
713
