当前位置:   article > 正文

K-近邻算法介绍与python代码实现计算两个矩阵之间的欧式距离_两个矩阵之间的距离计算

两个矩阵之间的距离计算

KNN介绍

简介
  • k近邻法(k-nearest neighbors)是由Cover和Hart于1968年提出的,它是懒惰学习(lazy learning)的著名代表。
  • k近邻算法是一种基本分类和回归方法。本篇作为学习笔记,暂时只讨论分类问题的k近邻法。
  • 距离衡量的标准有很多,常见的有:Lp距离、切比雪夫距离、马氏距离、巴氏距离、余弦值等。
算法步骤概述
  1. 给定一个测试样本
  2. 计算测试样本中每个点到训练样本中每个点的距离
  3. 取离测试样本最近的k个训练样本
  4. 选出在这k个样本中出现最多的类别,就是预测的结果

在这里插入图片描述
根据上面的流程简要做个概述:

  1. 中心点的绿色为测试样本,一共有两种类型,分为红色的三角形和蓝色的正方形
  2. 计算绿色到其他点的距离
  3. 选取距离测试样本最近的K个点。当K=3时,红色三角形数量多,分类结果为红色三角形。当K=5时,蓝色正方形数量多,分类结果为蓝色正方形。
欧式距离计算概述
双重循环
import numpy as np
def cal_l2_distance_two_loops(test_X, train_X):
    """
    计算L2距离,两层循环
    :return:
    """
    num_test = test_X.shape[0]
    num_train = train_X.shape[0]
    dists = np.zeros((num_test, num_train))
    for i in range(num_test):
        for j in range(num_train):
            test_line = test_X[i]
            train_line = train_X[j]
            temp = np.subtract(test_line, train_line)
            temp = np.power(temp, 2)
            dists[i][j] = np.sqrt(temp.sum())
    return dists
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
一层循环
import numpy as np
def cal_l2_distances_one_loop(test_X, train_X):
    """
    计算L2距离,一层循环
    :return:
    """
    num_test = test_X.shape[0]
    num_train = train_X.shape[0]
    dists = np.zeros((num_test, num_train))
    for i in range(num_test):
        dists[i] = np.sqrt(np.sum(np.square(train_X - test_X[i]), axis=1)).T
    return dists
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
通过矩阵计算

运算效率最高的算法是将训练集和测试集都使用矩阵表示,然后使用矩阵运算的方法替代之前的循环操作。但此操作需要我们对矩阵的运算规则非常熟悉。接下来着重记录如何计算两个矩阵之间的欧式距离。

记录测试集矩阵P的大小为MD,训练集矩阵C的大小为ND(测试集中共有M个点,每个点为D维特征向量。训练集中共有N个点,每个点为D维特征向量)

P i P_i Pi是P的第i行,记 P i P_i Pi是C的第j行
P i = [ P i 1 P i 2 ⋯ P i D ] P_i = [ P_{i1}\quad P_{i2} \cdots P_{iD}] Pi=[Pi1Pi2PiD] C j = [ C j 1 C j 2 ⋯ C j D ] C_j = [ C_{j1} C_{j2} \cdots \quad C_{jD}] Cj=[Cj1Cj2CjD]

首先计算 P i P_i Pi C j C_j Cj之间的距离dist(i,j)
d ( P i , C j ) = ( P i 1 − C j 1 ) 2 + ( P i 2 − C j 2 ) 2 + ⋯ + ( P i D − C j D ) 2 = ( P i 1 2 + P i 2 2 + ⋯ + P i D 2 ) + ( C j 1 2 + C j 2 2 + ⋯ + C j D 2 ) − 2 × ( P i 1 C j 1 + P i 2 C j 2 + ⋯ + P i D C i D ) = ∥ P i ∥ 2 + ∥ C j ∥ 2 − 2 × P i C j T d(P_i,C_j) = \sqrt{(P_{i1}-C_{j1})^2+(P_{i2}-C_{j2})^2+\cdots+(P_{iD}-C_{jD})^2}\\ =\sqrt{(P_{i1}^2+P_{i2}^2+\cdots+P_{iD}^2)+(C_{j1}^2+C_{j2}^2+\cdots+C_{jD}^2)-2\times(P_{i1}C_{j1}+P_{i2}C_{j2}+\cdots+P_{iD}C_{iD})}\\=\sqrt{\left \| P_i\right \|^2+\left\|C_j\right\|^2-2\times P_iC_j^T} d(Pi,Cj)=(Pi1Cj1)2+(Pi2Cj2)2++(PiDCjD)2 =(Pi12+Pi22++PiD2)+(Cj12+Cj22++CjD2)2×(Pi1Cj1+Pi2Cj2++PiDCiD) =Pi2+Cj22×PiCjT

我们可以推广到距离矩阵的第i行的计算公式
d i s t [ i ] = ( ∥ P i ∥ 2 ∥ P i ∥ 2 ⋯ ∥ P i ∥ 2 ) + ( ∥ C 1 ∥ 2 ∥ C 2 ∥ 2 ⋯ ∥ C N ∥ 2 ) − 2 × P i ( C 1 T C 2 T ⋯ C N T ) = ( ∥ P i ∥ 2 ∥ P i ∥ 2 ⋯ ∥ P i ∥ 2 ) + ( ∥ C 1 ∥ 2 ∥ C 2 ∥ 2 ⋯ ∥ C N ∥ 2 ) − 2 × P i C T dist[i]=\sqrt{(\left\|P_i\right\|^2\quad \left\|P_i\right\|^2 \cdots \left\|P_i\right\|^2)+(\left\|C_1\right\|^2 \quad \left\|C_2\right\|^2 \cdots \left\|C_N\right\|^2)-2\times P_i(C_1^T \quad C_2^T \cdots C_N^T)}\\=\sqrt{(\left\|P_i\right\|^2\quad \left\|P_i\right\|^2 \cdots \left\|P_i\right\|^2)+(\left\|C_1\right\|^2 \quad \left\|C_2\right\|^2 \cdots \left\|C_N\right\|^2)-2\times P_iC^T} dist[i]=(Pi2Pi2Pi2)+(C12C22CN2)2×Pi(C1TC2TCNT) =(Pi2Pi2Pi2)+(C12C22CN2)2×PiCT
注意:这里公式中的第二项为什么是 ∥ C j ∥ 2 \left\|C_j\right\|^2 Cj2呢,因为算的是i行的距离。即测试样本的第i行到训练样本中每一个点的距离。如果对这个不是很清楚的同学,可以看看下面参看文章中的第三个链接。

继续将公式推广为整个距离矩阵
d i s t = ( ∥ P 1 ∥ 2 ∥ P 1 ∥ 2 ⋯ ∥ P 1 ∥ 2 ∥ P 2 ∥ 2 ∥ P 2 ∥ 2 ⋯ ∥ P 2 ∥ 2 ⋮ ⋮ ⋱ ⋮ ∥ P M ∥ 2 ∥ P M ∥ 2 ⋯ ∥ P M ∥ 2 ) + ( ∥ C 1 ∥ 2 ∥ C 2 ∥ 2 ⋯ ∥ C N ∥ 2 ∥ C 1 ∥ 2 ∥ C 2 ∥ 2 ⋯ ∥ C N ∥ 2 ⋮ ⋮ ⋱ ⋮ ∥ C 1 ∥ 2 ∥ C 2 ∥ 2 ⋯ ∥ C N ∥ 2 ) − 2 × P C T dist=\sqrt{

(P12P12P12P22P22P22PM2PM2PM2)
+
(C12C22CN2C12C22CN2C12C22CN2)
-2\times PC^T} dist=P12P22PM2P12P22PM2P12P22PM2+C12C12C12C22C22C22CN2CN2CN22×PCT
通过矩阵计算两个之前的欧式距离的代码,参看博客中的代码好像都有问题,下面是我根据下面的公式,自己写的一个。

import numpy as np
def cal_l2_distances_no_loops(test_X, train_X):
	"""
	计算L2距离,通过矩阵运算
	:return:
	"""
	
	first = np.sum(np.square(test_X), axis=1)
	second = np.sum(np.square(train_X), axis=1).T
	# 注意这里的np.dot(test_X, train_X.T)中的test_X, train_X位置是和公式中的顺序保持一致的
	three = -2 * np.dot(test_X, train_X.T)
	
	dists = np.sqrt(first + second + three)
	return dists
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
代码合在一起
import numpy as np


class MatrixDistance(object):
    """计算两个矩阵之的L2距离(欧式距离)"""

    def __init__(self, train_X, test_X):
        self.train_X = train_X
        self.test_X = test_X

    def cal_l2_distance_two_loops(self):
        """
        计算L2距离,两层循环
        :return:
        """
        num_test = self.test_X.shape[0]
        num_train = self.train_X.shape[0]
        dists = np.zeros((num_test, num_train))
        for i in range(num_test):
            for j in range(num_train):
                test_line = self.test_X[i]
                train_line = self.train_X[j]
                temp = np.subtract(test_line, train_line)
                temp = np.power(temp, 2)
                dists[i][j] = np.sqrt(temp.sum())
        return dists

    def cal_l2_distances_one_loop(self):
        """
        计算L2距离,一层循环
        :return:
        """
        num_test = self.test_X.shape[0]
        num_train = self.train_X.shape[0]
        dists = np.zeros((num_test, num_train))
        for i in range(num_test):
            dists[i] = np.sqrt(np.sum(np.square(self.train_X - self.test_X[i]), axis=1)).T
        return dists

    def cal_l2_distances_no_loops(self):
        """
        计算L2距离,通过矩阵运算
        :return:
        """

        first = np.sum(np.square(self.test_X), axis=1)
        second = np.sum(np.square(self.train_X), axis=1).T
        # 注意这里的np.dot(self.test_X, self.train_X.T)中的test_X, train_X位置是和前面的顺序保持一致的
        three = -2 * np.dot(self.test_X, self.train_X.T)

        dists = np.sqrt(first + second + three)
        return dists


if __name__ == '__main__':
    train_x = np.matrix(np.arange(12).reshape(3, 4))
    test_x = np.matrix(np.arange(2, 14).reshape(3, 4))

    d = MatrixDistance(train_x, test_x)
    print(d.cal_l2_distance_two_loops())
    print(d.cal_l2_distances_one_loop())
    print(d.cal_l2_distances_no_loops())

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63

参考文章:
计算两个矩阵之间的欧式距离
k近邻算法
K-近邻算法介绍与代码实现

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/羊村懒王/article/detail/703108
推荐阅读
相关标签
  

闽ICP备14008679号