欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

维度灾难--通过Python理解高维空间欧氏距离与余弦相似度失效

程序员文章站 2022-05-18 19:21:33
代码链接:github代码维度灾难维数灾难(Curse of Dimensionality):通常是指在涉及到向量的计算的问题中,随着维数的增加,计算量呈指数倍增长的一种现象。维数灾难涉及数字分析、抽样、组合、机器学习、数据挖掘和数据库等诸多领域。此处讨论高维情况下,距离函数的计算是否具有意义。欧氏距离与余弦相似度区别欧氏距离衡量的是空间各点的绝对距离,跟各个点所在的位置坐标直接相关;而余弦距离衡量的是空间向量的夹角,更加体现在方向上的差异,而不是位置。欧氏距离能够体现个体数值特征的绝对差异,所...

代码链接:github代码

维度灾难

维数灾难(Curse of Dimensionality):通常是指在涉及到向量的计算的问题中,随着维数的增加,计算量呈指数倍增长的一种现象。维数灾难涉及数字分析、抽样、组合、机器学习、数据挖掘和数据库等诸多领域。

此处讨论高维情况下,距离函数的计算是否具有意义。

欧氏距离与余弦相似度区别

欧氏距离衡量的是空间各点的绝对距离,跟各个点所在的位置坐标直接相关;而余弦距离衡量的是空间向量的夹角,更加体现在方向上的差异,而不是位置。

欧氏距离能够体现个体数值特征的绝对差异,所以更多的用于需要从维度的数值大小中体现差异的分析,如使用用户行为指标分析用户价值的相似度或差异。

余弦距离更多的是从方向上区分差异,而对绝对的数值不敏感,更多的用于使用用户对内容评分来区分兴趣的相似度和差异,同时修正了用户间可能存在的度量标准不统一的问题(因为余弦距离对绝对数值不敏感)。

实验

实现从2维到50维分别计算欧氏距离和余弦相似度下的最大最小距离之间的差距 :
维度灾难--通过Python理解高维空间欧氏距离与余弦相似度失效
并且对最后的结果取lg,即 ,做出差距随维数的变化图像如下图所示:
维度灾难--通过Python理解高维空间欧氏距离与余弦相似度失效
由上图可知,随着维数增加,差距逐渐减小,即“维数灾难”,数据维数增加,最大最小距离,最大最小相似度趋近于零,无法判别,距离函数和余弦相似度函数在高维环境下失去其意义。

import random
import math
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

plt.rcParams['font.sans-serif'] = ['SimHei']  # 指定默认字体
plt.rcParams['axes.unicode_minus'] = False  # 解决保存图像是负号'-'显示为方块的问题

def euclidien_distence(x, y):
    """计算两个向量x和y的欧氏距离"""
    vec1, vec2 = np.mat(x), np.mat(y)
    return np.sqrt(np.sum(np.square(vec1 - vec2)))

def cosine_similarity(x, y, norm=False):
    """ 计算两个向量x和y的余弦相似度 """
    assert len(x) == len(y), "len(x) != len(y)"
    if len(x) == 1:
        return 1
    zero_list = [0] * len(x)
    if x == zero_list or y == zero_list:
        return float(1) if x == y else float(0)

    res = np.array([[x[i] * y[i], x[i] * x[i], y[i] * y[i]] for i in range(len(x))])
    cos = sum(res[:, 0]) / (np.sqrt(sum(res[:, 1])) * np.sqrt(sum(res[:, 2])))

    return 0.5 * cos + 0.5 if norm else cos  # 归一化到[0, 1]区间内

def generate_data(dim):
	"""生成dim维的500个数据,数据格式:500*dim"""
	data = [[] for _ in range(500)]
	for i in range(500):
	for j in range(dim):
	    num = random.random()
	    data[i].append(num)
	return data

def main():
	euc_diff_list = [] # 存储欧氏距离下最大最小距离之间的距离
	cos_diff_list = [] # 存储余弦相似度下最大最小相似度之间的距离
	for dim in range(2, 51): # 由于1维情况,无法计算余弦相似度,故从2-50维
	    data = generate_data(dim)
	    euc_distence_list = []
	    cos_distence_list = []
	    for i in range(499):
	        for j in range(i+1, 500):
	            euc_distence_list.append(euclidien_distence(data[i], data[j]))
	            cos_distence_list.append(cosine_similarity(data[i], data[j]))
	    euc_diff_list.append(math.log((max(euc_distence_list) - min(euc_distence_list))/min(euc_distence_list), 10))
	    cos_diff_list.append(math.log((max(cos_distence_list) - min(cos_distence_list))/min(cos_distence_list), 10))

	"""绘图"""
	x = list(range(2, 51))
	plt.plot(x, euc_diff_list, label = '欧氏距离')
	plt.plot(x, cos_diff_list, label = '余弦相似度')
	plt.title('Curse of Dimensionality')
	plt.xlabel('维度')
	plt.ylabel('lg(dif)')
	plt.legend(loc = 'upper right')

if __name__ =="__main__":
	main()

代码链接:github代码

如果感觉对你有所帮助,不妨点个赞,关注一波,激励博主持续更新!

本文地址:https://blog.csdn.net/t949500898/article/details/107433419