<!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>