kNN算法是否要求距离必须遵循距离公理？如果我使用了一个不满足以下条件的度量会发生什么：

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

同样的问题也适用于KMeans聚类吗？

回答：

kNN只需要一个接近度量，其中较小的值表示更接近。这是因为kNN将新观测值与训练样本进行比较，并找出k个最接近的样本（前k个具有最低接近度值的样本）。对于kMeans，请使用搜索。

编辑：尽管kNN不需要三角不等式，但它的运行时间为O(n*m)，其中n是训练集的大小，m是评估集的大小。优化通常至少需要三角不等式成立，尽管有些优化有更多的限制（例如：k-d树只能在欧几里得空间中工作）。更多信息请参见这个问题。