三种计算样本欧氏距离的方法——样本数据表示为矩阵
背景
近期在看CS231n课程，作业中有关于计算图像样本间Kmeans距离的代码编写，涉及到的距离例如为欧氏距离，计算的三种方法效率由低到高，在学习的过程中令我收益匪浅。
假设图像大小为32*32*3=3072，提供5000个训练样本，500个测试样本，将图像矩阵展开为一维向量，则训练样本为5000*3072矩阵，测试样本为500*3072矩阵。
训练样本的标签已知，现要求计算每个测试样本与每个训练样本的欧氏距离，作为测试样本的分类依据，将计算的距离结果存放在dist矩阵中，dist[i][j]表示第i个测试样本与第j个训练样本的欧氏距离。
方法一：双循环逐个计算
对于500个测试样本，5000个训练样本，可以简单的通过两个嵌套的循环遍历计算样本之间的欧氏距离。这是最直观简单的想法，也最容易实现。
def cal_dist_two_loops(train, test):
"""
使用两层循环计算欧氏距离
train为训练样本矩阵，大小为5000*3072
test为测试样本矩阵，大小为500*3072
dist为存放样本间距离的矩阵，dist[i][j]表示测试样本i与训练样本j之间的距离
"""
num_train = train.shape(0) # 本文中为5000
num_test = test.shape(0) # 本文中为500
for i in range(num_test):
for j in range(num_train):
dist[i][j] = np.sqrt(np.sum(np.square(test[i]-train[j])))
return dist
在上述代码中，每次取train和test的一行进行相减，实际是1*3072向量每个对应位置的元素相减，之后平方求和即为欧氏距离。
方法二：单循环+部分向量化
单循环即只用到一次循环，部分向量化其实是利用了python中矩阵运算的性质。
def cal_dist_one_loop(train, test):
"""
使用一层循环计算欧氏距离
变量同cal_dist_two_loops
"""
num_train = train.shape(0)
num_test = test.shape(0)
for i in range(num_test):
dist[i] = np.sqrt(np.sum(np.square(train - test[i]), axis=1))
return dist
在上述代码中，train是一个5000*3072的矩阵，test[i]是1*3072的矩阵(向量)，两者大小不同进行相减，在python中会先将test[i]扩展至5000*3072，即一行复制5000份，之后对应位置元素相减，同样平方求和开方得到欧氏距离。
注意：这里一次循环就计算了单个测试样本分别与5000个训练样本之间的距离，axis=1在水平(一行)方向求和，列数化为1，结果为5000*1的向量，赋值给dist[i]。
方法三：不使用循环+纯向量化计算
使用循环计算的效率远不如矩阵运算，因此应尽量使用矩阵运算代替循环。对于每一个3072单位大小的图像样本，欧氏距离就是每个像素值相减平方求和再开方，我们将该数学式展开，这样反而有利于我们利用矩阵计算。
(
x
1
−
y
1
)
2
+
(
x
2
−
y
2
)
2
+
.
.
.
+
(
x
3072
−
y
3072
)
2
\sqrt{(x_1-y_1)^2+(x_2-y_2)^2+...+(x_{3072}-y_{3072})^2}
(x1−y1)2+(x2−y2)2+...+(x3072−y3072)2
x
1
2
+
x
2
2
+
.
.
+
y
1
2
+
y
2
2
+
.
.
.
−
2
x
1
y
1
−
2
x
2
y
2
−
.
.
.
\sqrt{x_1^2+x_2^2+..+y_1^2+y_2^2+...-2x_1y_1-2x_2y_2-...}
x12+x22+..+y12+y22+...−2x1y1−2x2y2−...文章来源：https://www.toymoban.com/news/detail-407517.html
def cal_dist_no_loop(train, test):
"""
不使用循环计算欧氏距离
"""
num_train = train.shape(0)
num_test = test.shape(0)
dist += np.sum(np.square(test),axis=1).reshape(num_test, 1)
dist += np.sum(np.square(train), axis=1).reshape(1, num_train)
dist -= 2 * np.dot(test, train.T)
dist = np.sqrt(dist)
return dist
-
np.sum(np.square(test),axis=1)对应测试样本的平方项求和，reshape(500, 1)，此时dist大小为500*1，每一个元素都是单样本的3072个平方项和。 -
np.sum(np.square(train), axis=1)对应训练样本的平方项求和，reshape(1,5000)，每个元素都是单样本的3072个平方项求和，与dist相加，同样利用python中矩阵相加，大小不一致先扩展，相加后dist大小为500*5000。 - 之后减去两倍交叉项，利用矩阵乘法得到交叉项乘积和，最后求平方根。
总结
利用矩阵的性质进行计算，能够大大提高计算的效率。而如何深入理解矩阵运算，就不得不提到线性代数的重要性了，同时矩阵在python中的运算也有其特点，加以了解并运用才能更好地达成我们的目的。
文章来源地址https://www.toymoban.com/news/detail-407517.html
到了这里，关于【三种计算样本欧氏距离的方法——样本数据表示为矩阵】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
