最近鄰居中的度量有效

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。