K近邻的距离度量表示法-CDA数据分析师官网

热线电话：13121318867

K近邻的距离度量表示法

2014-11-29

K近邻的距离度量表示法

我们看到，K近邻算法的核心在于找到实例点的邻居，这个时候，问题就接踵而至了，如何找到邻居，邻居的判定标准是什么，用什么来度量。这一系列问题便是下面要讲的距离度量表示法。但有的读者可能就有疑问了，我是要找邻居，找相似性，怎么又跟距离扯上关系了？

这是因为特征空间中两个实例点的距离和反应出两个实例点之间的相似性程度。K近邻模型的特征空间一般是n维实数向量空间，使用的距离可以使欧式距离，也是可以是其它距离，既然扯到了距离，下面就来具体阐述下都有哪些距离度量的表示法，权当扩展。

1. 欧氏距离，最常见的两点之间或多点之间的距离表示法，又称之为欧几里得度量，它定义于欧几里得空间中，如点 x = (x1,...,xn) 和 y = (y1,...,yn) 之间的距离为：

(1)二维平面上两点a(x1,y1)与b(x2,y2)间的欧氏距离：

(2)三维空间两点a(x1,y1,z1)与b(x2,y2,z2)间的欧氏距离：

(3)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的欧氏距离：

　　也可以用表示成向量运算的形式：

其上，二维平面上两点欧式距离，代码可以如下编写：

	
			//unixfy：计算欧氏距离   
		
			double euclideanDistance(const vector<double>& v1, const vector<double>& v2)   
		
			{   
		
			     assert(v1.size() == v2.size());   
		
			     double ret = 0.0;   
		
			     for (vector<double>::size_type i = 0; i != v1.size(); ++i)   
		
			     {   
		
			         ret += (v1[i] - v2[i]) * (v1[i] - v2[i]);   
		
			     }   
		
			     return sqrt(ret);   
		
			 }