k-Nearest Neighbour Classification of Datasets with a Family of Distances
k-Nearest Neighbour Classification of Datasets with a Family of Distances
复制标题
具有距离族的数据集的 k 最近邻分类
DOI：
10.20381/ruor-3989
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Stan Hatko
中科院分区：
文献类型：
--
作者：
Stan Hatko
$k$-最近邻 ($k$-NN) 分类器是用于分类数据集的最古老且最重要的监督学习算法之一。传统上，欧几里得范数用作 $k$-NN 分类器的距离。在本文中，我们研究了 $k$-NN 分类器的替代距离的使用。
我们首先介绍统计机器学习的一些背景概念。我们定义 $k$-NN 分类器并讨论 Stone 定理以及 $k$-NN 在赋范空间 $R^d$ 上普遍一致的证明。然后，如果我们从满足特定有界条件的范数族中获取一系列随机范数（独立于样本和查询），则证明 $k$-NN 是普遍一致的。我们通过用基于满足某些条件的均匀局部 Lipschitz 函数的距离替换范数来扩展这个结果。我们讨论斯通引理和斯通定理的局限性，特别是在拟范数和基于标记样本自适应选择 $k$-NN 距离方面。我们展示了两阶段 $k$-NN 类型分类器的普遍一致性，其中我们根据分割标记样本和查询自适应地选择距离。最后，我们给出了一些使用上述技术提高对各种数据集分类准确性的示例。
The $k$-nearest neighbour ($k$-NN) classifier is one of the oldest and most important supervised learning algorithms for classifying datasets. Traditionally the Euclidean norm is used as the distance for the $k$-NN classifier. In this thesis we investigate the use of alternative distances for the $k$-NN classifier.
We start by introducing some background notions in statistical machine learning. We define the $k$-NN classifier and discuss Stone's theorem and the proof that $k$-NN is universally consistent on the normed space $R^d$. We then prove that $k$-NN is universally consistent if we take a sequence of random norms (that are independent of the sample and the query) from a family of norms that satisfies a particular boundedness condition. We extend this result by replacing norms with distances based on uniformly locally Lipschitz functions that satisfy certain conditions. We discuss the limitations of Stone's lemma and Stone's theorem, particularly with respect to quasinorms and adaptively choosing a distance for $k$-NN based on the labelled sample. We show the universal consistency of a two stage $k$-NN type classifier where we select the distance adaptively based on a split labelled sample and the query. We conclude by giving some examples of improvements of the accuracy of classifying various datasets using the above techniques.