距离度量优化与缓存技术——距离度量优化与缓存技术

假设你在处理一个拥有50万条文本数据的分类任务，使用KNN算法时，每次预测需要遍历所有样本计算余弦相似度——单次预测耗时超过20秒，用户等待时间足以让实时推荐系统崩溃。

核心矛盾：距离计算是KNN的核心操作，但也是性能瓶颈的主要来源。
本文将揭秘如何通过距离度量优化与缓存策略，将计算效率提升40倍，并给出文本分类与推荐系统的实战案例。

一、距离度量的效率博弈

1. 常见距离度量对比

度量方法	公式	计算复杂度	适用场景
欧式距离	√(Σ(x_i - y_i)²)	O(d)	低维稠密数据
曼哈顿距离	Σ\|x_i - y_i\|	O(d)	高维稀疏数据（如文本）
余弦相似度	(x·y)/(\|x\|\|y\|)	O(d)	高维稀疏、方向敏感
切比雪夫距离	max\|x_i - y_i\|	O(d)	网格结构数据

2. 计算优化技巧

向量化计算：利用NumPy矩阵运算替代循环，加速10~100倍。
避免冗余开方：比较距离时无需开方（如KNN仅需比较距离平方）。

代码对比：

# 低效写法：逐元素循环计算欧式距离  
def euclidean_slow(x, y):  distance = 0  for i in range(len(x)):  distance += (x[i] - y[i])**2  return distance**0.5  # 高效写法：NumPy向量化  
def euclidean_fast(x, y):  return np.sqrt(np.sum((x - y)**2))  # 终极优化：省略开方  
def euclidean_squared(x, y):  return np.sum((x - y)**2)

二、预计算与缓存策略

1. 预计算距离矩阵

适用场景：小型数据集（N<1万）且需多次查询。
内存管理：100万样本的float32距离矩阵占用约4TB内存（不可行），需分块存储或采样。

代码示例：

from sklearn.metrics.pairwise import pairwise_distances# 预计算所有样本间的余弦相似度  
cache = pairwise_distances(X_train, metric='cosine', n_jobs=-1)  # 多线程加速  # KNN查询时直接查表  
def knn_predict(query_idx, k=5):  nearest = np.argsort(cache[query_idx])[:k]  return mode(y_train[nearest])

2. 动态缓存热点数据

LRU缓存：缓存最近查询的邻居结果，避免重复计算。
分块缓存：将数据分块存储，缓存频繁访问的数据块。

代码实战：LRU缓存装饰器

from functools import lru_cache@lru_cache(maxsize=1000)  
def get_neighbors(query_vector_hash, k):  # 将查询向量哈希后作为缓存键  return model.kneighbors(query_vector)  # 查询时先哈希向量（需先转换为元组）  
query_hash = tuple(np.round(query_vector, 4))  # 保留4位小数作为哈希键  
indices = get_neighbors(query_hash, k=5)

三、案例实战1：文本分类中的TF-IDF+余弦加速

1. 场景描述

数据：20 Newsgroups数据集（1.8万文本，TF-IDF特征维度1万）。
痛点：原始KNN预测耗时15秒/样本。

2. 优化方案

from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.neighbors import NearestNeighbors# 使用余弦相似度+稀疏矩阵优化  
vectorizer = TfidfVectorizer(max_features=10000)  
X = vectorizer.fit_transform(texts)  # 稀疏矩阵  # 利用稀疏矩阵的余弦相似度快速计算  
model = NearestNeighbors(n_neighbors=5, metric='cosine', algorithm='brute')  
model.fit(X)# 查询加速（0.5秒/样本）  
query = vectorizer.transform(["new computer graphics technology"])  
distances, indices = model.kneighbors(query)

3. 性能对比

优化方法	耗时/样本	内存占用
原始欧式距离	15.2s	8GB
余弦+稀疏矩阵	0.5s	1.2GB

四、案例实战2：推荐系统的用户相似度缓存

1. 场景描述

数据：100万用户的行为向量（200维），每日需处理10万次查询。
优化目标：单次查询从2秒降至0.1秒。

2. 分块缓存实现

import numpy as np
from sklearn.neighbors import BallTree# 将用户数据分块（每块1万用户）  
blocks = [X[i:i+10000] for i in range(0, 1000000, 10000)]  
block_trees = [BallTree(block, metric='euclidean') for block in blocks]# 缓存最近访问的块  
from cachetools import LRUCache  
cache = LRUCache(maxsize=50)  def query_user(user_vector, k=10):  nearest_blocks = np.argsort([np.linalg.norm(user_vector - block.mean(axis=0)) for block in blocks])[:5]  candidates = []  for blk_id in nearest_blocks:  if blk_id in cache:  tree = cache[blk_id]  else:  tree = BallTree(blocks[blk_id])  cache[blk_id] = tree  dist, idx = tree.query(user_vector, k=k)  candidates.extend(zip(dist[0], blocks[blk_id][idx[0]]))  # 取全局Top-K  candidates.sort(key=lambda x: x[0])  return candidates[:k]

优化结果：