一种有效的贝叶斯近邻算法
Giuseppe Nuti
摘要
K近邻（K-NN）是一种流行的分类和回归算法，但它的主要局限性之一是邻域数目的选择困难。我们提出了一个贝叶斯算法，在不使用马尔可夫链蒙特卡罗（MCMC）方法或模拟的情况下，有效地计算数据集中给定目标点k的后验概率分布，同时给出指数族分布的精确解。中心思想是，我们目标周围的数据点是由相同的概率分布生成的，向外扩展到适当的、尽管未知的邻居数量上。一旦数据被投影到选择的距离度量上，我们就可以将k的选择转化为一个变化点检测问题，对此有一个有效的解决方案：当我们向目标移动时，我们递归地计算最后一个变化点的概率，因此，事实上计算了k上的后验概率分布。将这种方法应用于分类和回归UCI数据集，我们比较好，最重要的是，通过消除模拟的需要，我们能够准确快速地计算k的后验概率。例如，与使用MCMC方法时的几个小时相比，Ripley数据集的计算时间是几毫秒。
K近邻·非参数分类·贝叶斯分类 数学学科分类（2010）62F15贝叶斯推理·60G25预测理论
1.介绍及相关工作
许多作者探索了贝叶斯k-NN算法的思想，如Cucala等人。（2008），郭和脉轮（2010），和最初（霍姆斯和亚当斯2002）。k-NN的简单性和优雅性至少在直觉上有助于贝叶斯设置，其目的是允许邻居的数量根据数据而变化（如Ghosh（2006）所强调的）。
实际上，所有的工作都依赖于某种形式的马尔可夫链蒙特卡罗方法；模拟的使用避免了对任何目标的数据和邻域数目的全联合概率分布建模的需要。为了避免使用模拟，Ji和Friel（2013）中的作者已经逼近了似然函数，尽管这样做的代价是回归问题的准确性和可移植性。最近，作为另一种方法，Tomasev等人探讨了Huness的概念。（2011年）。
在贝叶斯统计的一个有点不同的分支中，许多研究都集中在估计数据的变化点概率上，假设生成过程随时间而变化。最初的工作集中在整个数据集的分区分析上，通常使用MCMC模拟：Smith（1975），Stephens（1994），Green（1995）（有趣的是，这与使用基于模拟的方法估计k的后验概率的计算复杂性有松散的联系）。然而，直到Prescott Adams和MacKay（2007）的作者提出了贝叶斯变化点估计的在线版本（具有O（n）计算复杂性），变化点问题才变得容易估计。 正如Manocha和Girolami（2007）详细讨论的那样，最近邻算法中k的概率视图优于标准交叉验证方法，尽管实践者通常由于依赖MCMC估计方法而避免使用概率方法。利用Prescott-Adams和MacKay（2007）提出的算法，对目标坐标距离排序的数据，我们可以计算特定于目标点的k的精确概率分布。
2.有效贝叶斯近邻
将邻域的数量与数据进行校准的想法是围绕这样一个概念：在适当的邻域内，数据点是相似的，或者换句话说，它们是由相同的过程生成的。事实上，我们的目标是确定有多少k个邻居代表着这样合适的邻居。
2.1数据生成过程
如果我们使用针对目标点的选择距离度量对数据进行排序，那么我们已经将我们的假设转化为这样一种想法，即对于靠近目标的前k个点，数据生成过程是共享的。因此，从最远的点向我们的目标移动，生成数据的底层进程可以随着已知的概率而变化，并且，当发生变化时，该进程是从已知的先验分布绘制的。我们的目的是确定这种变化点发生在邻居之间的不同间隔的概率-一旦我们达到了我们的目标数据。
该公式相当于Prescott Adams和MacKay（2007）中的变化点分析：我们可以递归地跟踪历史变化点概率，直到我们达到目标点。在距离目标的k个点处发生变化点的概率，实际上是k是正确邻域数的概率。
2.1.1一个简单的例子
作为一个简单的二维分类问题，假设我们有图1所示的基于欧几里德距离的具有各自顺序的数据，如图2所示。
图1两类数据示例；k=5很可能是目标点（I）的正确楔子，kge;10的
任何选择都可能导致错误分类，而目标点（II）的图片不太明显.
在这种情况下，目标点（I）的适当邻居数为5。查看k的选择的另一种本地方法是按数据点到目标点的距离（图2，x轴下方）对数据点进行排序。我们注意到每个k（在看到任何数据之前）作为虚线的先验概率，这只是一个pgamma;=0.05的几何分布。为了计算k的后验概率（图2中的蓝色实线），我们可以从最右边的点开始，向目标移动：即数据生成过程发生变化的概率（假设参数B为数据生成的beta;先验概率（alpha;=10，beta;=10））。在pgamma;=0.05的任意两个邻域之间发生变化点的概率，也就是说，我们关于相邻波数的先验值是k=20）。相反，我们并不确信目标（II）的合适k值，因为我们可以从后面看到分布，这给出了一个相当复杂的观点。 注意，beta;分布的选择是二元随机变量参数的标准共轭先验。选择pgamma;=0.05是该方法的关键部分。具体到这个例子，我们隐式地假设，当我们以0.05的概率离开目标点时，数据将发生变化。换句话说，危险函数是无记忆的.
图2最近邻计数的概率分布（数据按x轴以下的欧氏距离排序）。通过观察数据如何影响我们对目标（I）左侧和目标（II）右侧k个邻居的选择，将先验概率更新为后验概率.
2.2算法
第一步是将数据表示成一个有序列表，该列表由与目标点1的距离驱动。如果我们将目标点定义为xtau;，我们将所有可用的训练数据排序为x0，hellip;，xtau;-1（定义为x0:tau;-1），其中x0是距目标最远的点。我们假设数据xt是某个概率分布P（xt |eta;rho;）的分区rho;上的i.i.d.，其中eta;rho;表示数据生成分布的参数。最后，我们假设对于所有分区，eta;rho;也是已知先验分布的i.i.d（其中，rho;=1，hellip;，n和nle;tau;）。现在我们准备使用Prescott Adams和MacKay（2007）中提出的算法，应用于预测数据2。
我们的目标是计算到达目标点后每个邻居的概率：p（ktau;=i | x0，hellip;，tau;-1）i=0，hellip;，tau;-1和tau;-1的总数据点。注意，ktau;中的下标tau;表示从xtau;（即目标点）的角度，我们表示适当数量的邻域。从最远的点开始，初始化在初始点之前发生变化点的概率为1.0，我们设置初始条件3：
|
p(k0 = 0) = 1.0 |
(1) |
|
eta;0 = eta;pr ior |
(2) |
首先，我们注意到，当我们观察到一个新的数据，靠近我们的目标时，同一分区内的邻居kt的数量可以增加一个，概率为1-pgamma;，或者终止于一个新的分区。
|
pgamma; |
if kt = 0 |
||
|
p(kt |kt minus;1) =1 |
minus; pgamma; |
if kt = kt minus;1 1 |
(3) |
|
0 |
otherwise |
||
Prescott Adams和MacKay（2007）中算法的一个关键优势是，我们可以通过跟踪每个k和数据的联合概率p（kt1，x0，hellip;，xt1），递归地计算相邻数p（kt）上的概率，因为我们观察到一个新的数据xt，它与给定数量的邻居，pi;t = p(xt |kt minus;1, eta;t minus;1).
|
p(kt = kt minus;1 1, x0, ..., xt ) = p(kt minus;1, x0, ..., xt minus;1) pi;t pgamma; |
(4) |
|
|
p(kt = 0, x0, ..., xt ) = |
p(kt minus;1, x0, ..., xt minus;1) pi;0 (1 minus; pgamma; ) |
(5) |
kt minus;1
最后，我们定义了符号eta;rho;xt，以表明我们使用标准贝叶斯更新规则4（见Fink（1997）中指数族内的共轭先验更新）用基准xt更新了eta;rho;的分布参数。
2.2.1实施说明
（a） 危险函数不必是常数；pgamma;=f（）。有趣的是，可以取决于点之间的距离，或者当前的运行长度（即，不是内存不足）.
（b） 初始化更改点概率：我们不必在第一个数据点之前将其设置为1.0。为了加快分析速度，我们可以在距离目标点m点的地方启动算法（其中m可以设置为使改变点的先验概率
在m低于预先设定的阈值之前发生，并且m n）。在这种情况下，作为替代，我们可以用pgamma;的先验分布来初始化m之前的变化点的概率。
（c） 对于指数族中的分布，通常可以有效地计算定义为“”的贝叶斯更新。其他可能更复杂的分布可能需要求积或模拟方法。
（d） 对于大数据集，为了保持数值稳定性，我们采用对数变换联合概率。
图3 Ripley的训练数据（左）和测试数据（右）
3结果
为了批判性地评价这种方法，我们将分析基准放在普遍存在的用于分类的Ripley数据集（图3）上，并且，对于回归问题，放在Kaya等人的核电厂输出上。（2012年）。与使用全局最优邻域数（作为手动过程）得到的结果进行比较。换言之，当应用于所有训练数据点时，我们将此方法与k的最佳选择进行比较。这里的关键思想是，最佳k值取决于同一数据集中的特定目标点。除了基于各种k值（通过其可能性加权）的a预测之外，我们现在有了关于我们的预测的确定性度量。在图4中，我们给出了使用训练数据计算的分类概率。
Cucala等人基于MCMC的贝叶斯分析。（2008）获得了0.087的错误分类率，这与我们的结果类似，这并不奇怪。我们也注意到我们的图4和研究中的图之间的相似性。事实上，我们并不是提出用贝叶斯方法来估计邻居的数量，而是一种有效的方法。使用该算法，计算Ripley数据集中测试点k上的后验分布的时间平均为每个测试点3毫秒（对于标准PC），而Cucala等人的MCMC实现中使用的路径为50000。（2008年）。值得注意的是，与MCMC方法的全局分析不同，我们的方法导致了k的局部贝叶斯分析，即特定于所查询的数据点。
最后，在表1的右栏中，我们展示了如何通过将分类问题中的Beta分布的先验值与正态分布（因为我们只假设平均值是未知的）切换，来获得对电厂输出数据的改进结果。一个有趣的观察是，如果我们绘制数据的最大后验概率w.r.t.绝对误差（在图5中），我们可以观察k-NN算法的极限。具有较大绝对误差的数据点发生的概率显然非常小，尽管我们在所有可能的k上都显示了最大的可能性；换句话说，这些是与chosen6的距离度量有关的真实异常值。
图4使用里普利分类法传输数据
4结论性意见
本文提出了一种不依赖MCMC仿真的k-NN算法中邻域数贝叶斯分析的有效算法，适用于分类和回归。这就产生了更好的预测和对k的全概率观点。然而，k-NN算法面临的最大挑战可能是距离度量和差异化输入尺度的选择（如Weinberger和Saul 2009所强调的）。当然，对于多维问题，挑战在于如
剩余内容已隐藏，支付完成后下载完整资料
Methodology and Computing in Applied Probability (2019) 21:1251–1258 https://doi.org/10.1007/s11009-018-9670-z
An Efficient Algorithm for Bayesian Nearest Neighbours
Giuseppe Nuti1
Received: 21 August 2017 /
Accepted: 3 September 2018 / Published online: 27 September 2018 copy; The Author(s) 2018
Abstract
K-Nearest Neighbours (k-NN) is a popular classification and regression algorithm, yet one of its main limitations is the difficulty in choosing the number of neighbours. We present a Bayesian algorithm to compute the posterior probability distribution for k given a tar-get point within a data-set, efficiently and without the use of Markov Chain Monte Carlo (MCMC) methods or simulation—alongside an exact solution for distributions within the exponential family. The central idea is that data points around our target are generated by the same probability distribution, extending outwards over the appropriate, though unknown, number of neighbours. Once the data is projected onto a distance metric of choice, we can transform the choice of k into a change-point detection problem, for which there is an effi-cient solution: we recursively compute the probability of the last change-point as we move towards our target, and thus de facto compute the posterior probability distribution over k. Applying this approach to both a classification and a regression UCI data-sets, we compare favourably and, most importantly, by removing the need for simulation, we are able to com-pute the posterior probability of k exactly and rapidly. As an example, the computational time for the Ripley data-set is a few milliseconds compared to a few hours when using a MCMC approach.
Keywords K-nearest neighbour · Non-parametric classification · Bayesian classification
Mathematics Subject Classification (2010) 62F15 Bayesian Inference · 60G25 Prediction Theory
1 Introduction amp; Related Work
Various authors have explored the idea of Bayesian k-NN algorithms, e.g. Cucala et al. (2008), Guo and Chakraborty (2010), and originally (Holmes and Adams 2002). The simplicity and elegance of k-NN lends itself, at least intuitively, to a Bayesian setting where the aim is to allow the number of neighbours to vary depending on the data (as highlighted in Ghosh (2006)).
Primarily at UBS Securities LLC, 1285 Ave. of the Americas, New York, NY 10019
Giuseppe Nuti ucacnut@ucl.ac.uk
- Department of Computer Science, University College London, Gower Street, London, WC1E 6BT, UK
1252 Methodology and Computing in Applied Probability (2019) 21:1251–1258
Practically all of the work has relied on Markov Chain Monte-Carlo methods in some form or other; the use of simulation circumvents the need to model the full joint probability distribution of the data and the number of neighbours for any target. In an attempt to avoid the use of simulation, the authors in Ji and Friel (2013) have approximated the likelihood function, albeit at the expense of accuracy and portability to regression problems. More recently, as an alternative approach, the idea of hubness is explored in Tomasev et al. (2011).
In a somewhat distinct branch of Bayesian statistics, numerous studies have focused on estimating change-point probabilities for data where the generating process is presumed to vary over time. Initial works were focused on partition analysis for the entire data-set, often using MCMC simulation: Smith (1975), Stephens (1994), Green (1995) (which, interest-ingly, is loosely connected with the computational complexity of estimating the posterior probability of k using approaches based on simulation). Yet it was not until the authors in Prescott Adams and MacKay (2007) presented an on-line version of Bayesian change-point estimation (with an O (n) computational complexity), that change-point problems become easily estimated.
As discussed in detail by Manocha and Girolami (2007), a probabilistic view of k in nearest neighbour algorithms outperforms standard cross-validation approaches, though practitioners often avoid the probabilistic approach due to its reliance on MCMC methods of estimation. By using the algorithm presented in Prescott Adams and MacKay (2007) applied to the data ordered by distance to our target coordinates, we can compute the exact probability distribution for k specific to our target point.
2 Efficient Bayesian Nearest Neighbour
The idea of calibrating the number of neighbours to the data is centered around the notion that, within the appropriate neighbourhood, data points are similar, or, in other words, they are generated by the same process. It is indeed our goal to determine how many k neighbours represent such appropriate neighbourhood.
2.1 Data Generating Process
If we order the data using a distance measure of choice with respect to a target point, we have transformed our assumption into the idea that the data-generating process is shared for the first k points closets to the target. As such, moving from the most distant point towards our target, the underlying process generating the data can vary with a known probability and, when a change occurs, such process is drawn
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[273933]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
