最近邻居中的度量有效

Question

kNN算法是否要求距离遵循距离公理？如果我应用一个失败的度量标准，会发生什么情况：

d(a,c) < d(a,b) + d(b,c) 

对于KMeans聚类，同样的问题？

Answer 1

kNN只需要一个接近度测量值，其中较小的值表示较近。这是因为kNN将新观察结果与训练示例进行比较，并找出k个最接近的（具有最低接近值的前k个）。 适用于kMeans use search。

编辑： 即使kNN的犯规需要的三角公式，它在O（n * m个）时间，其中n是训练集的大小，m是所评价的集合的大小延伸。优化通常需要至少三角方程来支持，尽管其中一些有更多的约束（例如：k-d树只能在欧几里得空间中工作）。有关更多信息，请参见this question。