An adaptive nearest neighbor rule for classification
An adaptive nearest neighbor rule for classification
复制标题
DOI：
--
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Akshay Balsubramani;S. Dasgupta;Y. Freund;S. Moran
中科院分区：
文献类型：
--
作者：
Akshay Balsubramani;S. Dasgupta;Y. Freund;S. Moran
我们介绍了$ k $ neart的邻居分类器的一种变体，其中$ k $适用于每个查询，而不是作为参数提供。 $ K $的选择取决于每个社区的属性，因此在不同点之间可能会大不相同。 （例如，该算法将使用较大的$ k $来预测嘈杂区域的点标签。）我们提供的理论和实验表明该算法的性能相当，有时比$ k $ nn具有最佳的$ k $ -nn $ k $的选择。特别是，我们在分类器的收敛速率上得出了界限，该分类器取决于我们称之为“优势”的局部数量，这比以前的收敛率证明中使用的LIPSCHITZ条件明显弱。这些泛化边界铰接在由于Vapnik和Chervonenkis引起的精液均匀收敛定理的变体上。这种变体涉及条件概率，并且可能具有独立的兴趣。
We introduce a variant of the $k$-nearest neighbor classifier in which $k$ is chosen adaptively for each query, rather than supplied as a parameter. The choice of $k$ depends on properties of each neighborhood, and therefore may significantly vary between different points. (For example, the algorithm will use larger $k$ for predicting the labels of points in noisy regions.) We provide theory and experiments that demonstrate that the algorithm performs comparably to, and sometimes better than, $k$-NN with an optimal choice of $k$. In particular, we derive bounds on the convergence rates of our classifier that depend on a local quantity we call the `advantage' which is significantly weaker than the Lipschitz conditions used in previous convergence rate proofs. These generalization bounds hinge on a variant of the seminal Uniform Convergence Theorem due to Vapnik and Chervonenkis; this variant concerns conditional probabilities and may be of independent interest.