HOOOS

Python实战：余弦相似度LSH算法实现与性能测试

0 33 AI派森小分队 LSH余弦相似度Python
Apple

局部敏感哈希（LSH）与余弦相似度：快速找到相似的“你”

在海量数据中，如何快速找到和你相似的“另一个你”？比如，在百万首歌曲中找到与你喜欢的歌曲风格最接近的那些，或者在亿万条微博中找到与你观点最相似的那些。传统的相似度计算方法，如计算余弦相似度，虽然准确，但在大数据面前却显得力不从心，因为它们需要两两比较，计算量巨大。

这时，局部敏感哈希（Locality-Sensitive Hashing，简称LSH）就派上用场了。LSH 是一种快速找到相似项的方法，它的核心思想是：将原始数据映射到新的空间，使得相似的数据在新的空间中仍然大概率相邻，而不相似的数据则大概率不相邻。这样，我们只需要比较相邻的数据，就能找到大部分相似项，大大减少了计算量。

而余弦相似度，则是衡量两个向量方向相似性的指标。它通过计算两个向量夹角的余弦值来判断它们的相似程度，值越接近1，表示两个向量越相似；值越接近0，表示两个向量越不相似。

本文将结合LSH和余弦相似度，用Python代码实现一个简单的LSH算法，并通过具体例子演示如何快速找到相似项，还会进行性能测试和比较。

1. 原理：LSH如何“缩小包围圈”？

想象一下，你是一个侦探，要在一座城市里找到和你拥有相同特征的人。如果挨家挨户地毯式搜索，那效率太低了。更好的办法是，先缩小范围，比如根据一些线索（如年龄、职业、爱好等）将城市划分为几个区域，然后重点搜索你认为最有可能的区域。

LSH的原理与此类似。它通过一系列哈希函数，将原始数据“分桶”，相似的数据更有可能被分到同一个桶里，而不相似的数据则更有可能被分到不同的桶里。这样，我们只需要在同一个桶里寻找相似项，就能大大减少搜索范围。

1.1 余弦相似度LSH的哈希函数

对于余弦相似度，LSH使用的哈希函数通常是随机超平面。具体来说，就是随机生成一个向量（超平面法向量），然后计算原始数据与这个向量的点积。点积大于0的数据被分到一类，点积小于等于0的数据被分到另一类。这样，我们就完成了一次“分桶”。

为什么随机超平面可以实现“分桶”呢？

  • 相似向量，点积大概率同号：想象两个方向相似的向量，它们与同一个随机向量的点积，大概率会同号（同为正或同为负）。
  • 不相似向量，点积大概率异号：想象两个方向不相似的向量，它们与同一个随机向量的点积，大概率会异号（一个为正，一个为负）。

通过多次“分桶”（使用多个随机超平面），我们就能更精确地找到相似项。

2. Python代码实现：动手搭建你的LSH

接下来，我们将用Python代码实现一个基于余弦相似度的LSH算法。为了方便演示，我们使用NumPy库来处理向量和矩阵。

import numpy as np

class CosineLSH:
    def __init__(self, num_planes, dimensions):
        """
        初始化CosineLSH。

        Args:
            num_planes: 哈希函数的数量（随机超平面的数量）。
            dimensions: 数据的维度。
        """
        self.num_planes = num_planes
        self.dimensions = dimensions
        self.planes = np.random.randn(num_planes, dimensions)

    def hash(self, vector):
        """
        计算向量的哈希值。

        Args:
            vector: 输入向量。

        Returns:
            一个字符串，表示向量的哈希值。
        """
        hashes = (np.dot(self.planes, vector) > 0).astype(int)
        return ''.join(hashes.astype(str))

    def index(self, data):
        """
        构建索引。

        Args:
            data: 一个二维数组，每一行表示一个向量。

        Returns:
            一个字典，键是哈希值，值是对应的数据索引列表。
        """
        index = {}
        for i, vector in enumerate(data):
            h = self.hash(vector)
            if h in index:
                index[h].append(i)
            else:
                index[h] = [i]
        return index

    def query(self, vector, index, k=10):
        """
        查询与输入向量相似的数据。

        Args:
            vector: 输入向量。
            index: 索引。
            k: 返回最相似的数据的数量。

        Returns:
            一个列表，包含最相似的数据的索引。
        """
        h = self.hash(vector)
        candidates = index.get(h, [])
        
        #如果桶内数据少于K，则返回桶内所有的. 
        if len(candidates) <= k:
            return candidates
        
        # 计算候选数据与查询向量的余弦相似度
        similarities = []
        for i in candidates:
            sim = np.dot(vector, data[i]) / (np.linalg.norm(vector) * np.linalg.norm(data[i]))
            similarities.append((sim, i))

        # 按照相似度排序，返回前k个
        similarities.sort(reverse=True)
        return [i for sim, i in similarities[:k]]

代码解读：

  • __init__：初始化LSH对象，生成指定数量的随机超平面。
  • hash：计算输入向量的哈希值，将向量映射成一个由0和1组成的字符串。
  • index：构建索引，将数据按照哈希值分组，方便后续查询。
  • query：查询与输入向量相似的数据。先找到与输入向量哈希值相同的候选数据，然后计算它们与输入向量的余弦相似度，最后返回最相似的k个数据。

3. 演示：LSH如何找到相似电影？

假设我们有一个电影数据集，每部电影都用一个向量表示，向量的每个维度代表一个特征（如类型、演员、导演等）。现在，我们要找到与某部电影最相似的几部电影。

# 假设电影数据集如下：
data = np.array([
    [0.8, 0.2, 0.5, 0.1],
    [0.7, 0.3, 0.4, 0.2],
    [0.1, 0.9, 0.2, 0.8],
    [0.2, 0.8, 0.3, 0.7],
    [0.9, 0.1, 0.6, 0.3],
])

# 创建LSH对象
lsh = CosineLSH(num_planes=5, dimensions=4)

# 构建索引
index = lsh.index(data)

# 查询与第一部电影相似的电影
query_vector = data[0]
similar_movies = lsh.query(query_vector, index, k=2)

print(f"与第一部电影相似的电影索引：{similar_movies}")

运行结果可能如下：

与第一部电影相似的电影索引：[4, 1]

这表示，与第一部电影最相似的两部电影是第五部和第二部。当然，由于LSH的随机性，每次运行的结果可能会略有不同。

4. 性能测试：LSH vs 暴力搜索

为了验证LSH的性能优势，我们将其与暴力搜索（brute-force search）进行比较。暴力搜索就是计算查询向量与数据集中所有向量的余弦相似度，然后排序返回最相似的k个。

import time

# 生成更大的数据集
data = np.random.rand(1000, 100)

# 创建LSH对象
lsh = CosineLSH(num_planes=20, dimensions=100)

# 构建索引
index = lsh.index(data)

# 查询向量
query_vector = data[0]

# LSH查询
start_time = time.time()
lsh_results = lsh.query(query_vector, index, k=10)
lsh_time = time.time() - start_time

# 暴力搜索
start_time = time.time()
similarities = []
for i, vector in enumerate(data):
    sim = np.dot(query_vector, vector) / (np.linalg.norm(query_vector) * np.linalg.norm(vector))
    similarities.append((sim, i))
similarities.sort(reverse=True)
brute_force_results = [i for sim, i in similarities[:10]]
bf_time = time.time() - start_time

print(f"LSH查询时间：{lsh_time:.4f}秒")
print(f"暴力搜索时间：{bf_time:.4f}秒")

# 比较结果
common_results = set(lsh_results) & set(brute_force_results)
print(f"LSH和暴力搜索找到的相同结果数量：{len(common_results)}")

运行结果可能如下：

LSH查询时间：0.0013秒
暴力搜索时间：0.0055秒
LSH和暴力搜索找到的相同结果数量：8

可以看到，LSH的查询时间明显快于暴力搜索，而且找到的大部分结果是相同的。随着数据集的增大，LSH的性能优势会更加明显。

5. 总结与进阶

本文介绍了局部敏感哈希（LSH）和余弦相似度的基本原理，并通过Python代码实现了一个简单的LSH算法。我们演示了如何使用LSH找到相似项，并将其与暴力搜索进行了性能比较。

LSH是一种非常有用的技术，它可以应用于各种需要快速找到相似项的场景，如推荐系统、搜索引擎、图像检索等。

当然，LSH还有很多可以改进和扩展的地方，比如：

  • 调整哈希函数的数量：哈希函数的数量越多，LSH的精度越高，但计算量也越大。需要根据实际情况进行权衡。
  • 使用更复杂的哈希函数：除了随机超平面，还可以使用其他类型的哈希函数，如MinHash、SimHash等。
  • 结合其他技术：LSH可以与其他技术结合使用，如倒排索引、多级索引等，进一步提高搜索效率。

希望本文能帮助你入门LSH，并在实际应用中发挥它的作用。

点评评价

captcha
健康