python - 成对相似度/相似度矩阵计算优化

Question

问题定义

---

问题

如何优化计算大量向量的成对余弦相似度(估计适合)？

正式定义

对于两个集合(A，B)，需要为每个 a 和 b 生成包含向量 - 成对余弦相似度 sim(a_i, b_j)。 (余弦相似度矩阵也适合，因为它很容易从矩阵转换为成对矩阵。)

我为什么寻求帮助

---

这看起来是一个常见问题，因为在计算生物学、推荐系统等中需要计算这样的距离。但我还没有找到一些合理的解决方案。

我无法解决的问题

根据定义，这个问题的复杂度是 O(len_A * len_B * O(similarity_function))，因此 A 和 B 集中的 10^6 个向量往往会花费大量的运行时间

我对 future 方向的假设

看起来，我们在这里做了很多无用的工作，因为相似性不是独立的(如果我们计算出一百万个向量的 a_i 相似度，并且 b_j 与 a_i 非常相似 - 并且我们有 900k 的 b_j 相似度)计算出的向量我们可以估计 b_j 与其余 100k 个向量的相似度)。我假设这里可以使用索引之类的东西。

其他详细信息

---

1. A 和 B 不相交。
2. 向量维度已降至最小合理值。
3. 不需要简单的 for 循环优化。简单地说 - 这是简短的guide用于优化此 - 给出最简单的循环以清晰地说明算法。
4. 我很感兴趣是否有一种算法也可以进行估计，因此如果我们的相似度足够接近但与真实情况不完全相同也没关系。
5. 无需并行化。
6. 我知道生成的相似度矩阵会很大。
7. 我也很感兴趣，如果该算法允许从集合 B 中为集合 A 中的每个向量仅获取最相似的向量。

感谢您的参赛作品。

代码示例

---

要求

python==3.6
pandas==0.25.0
scikit-learn==0.21.3
numpy==1.17.1

生成虚拟数据

import pandas as pd
import numpy as np
from sklearn.metrics.pairwise import cosine_similarity 

df_1 = pd.DataFrame({'object_id_1': range(10),
                   'feature_0': np.random.uniform(0,1,10),
                   'feature_1': np.random.uniform(0,1,10),
                   'feature_2': np.random.uniform(0,1,10),
                   'feature_3':np.random.uniform(0,1,10)})

df_2 = pd.DataFrame({'object_id_2': range(10,20),
                   'feature_0': np.random.uniform(0,1,10),
                   'feature_1': np.random.uniform(0,1,10),
                   'feature_2': np.random.uniform(0,1,10),
                   'feature_3':np.random.uniform(0,1,10)})

相似度生成函数

def get_similarities(df_1: pd.DataFrame, df_2: pd.DataFrame, meaningful_features:list) -> pd.DataFrame:
    '''
    This function generates features based similarity scores, between two groups of objects
    
    Parameters
    ----------
    df_1: pandas.DataFrame
        DataFrame with features, and id_s of objects
    df_2: pandas.DataFrame
        DataFrame with features, and id_s of objects which has no id_s same to df_1
    meaningful_features: list
        Features columns to calculate similarity on
        
    Returns
    ----------
        similarities_of_objects: pandas.DataFrame
            DataFrame, with columns 'object_id_1', 'object_id_2', 'similarity', 
            where we have features similarity, for each object_1-object_2 pair. 
            Similarity - symmetric.  
    '''

    objects_1 = [] #  list of all objects from df_1
    objects_2 = [] #  list of all objects from df_2
    similarities = [] #  list of scores for object_1-object_2 pairs

    for object_1 in df_1['object_id_1'].unique():
        features_vector_1 = df_1[df_1['object_id_1'] == object_1][meaningful_features] # object_1 features vector
        
        for object_2 in df_2['object_id_2'].unique():
            features_vector_2 = df_2[df_2['object_id_2'] == object_2][meaningful_features] # object_2 features vector
            
            objects_1.append(object_1)
            objects_2.append(object_2)
            similarities.append(cosine_similarity(X = np.array(features_vector_1)
                                    ,Y = np.array(features_vector_2)).item()) # similarities of vectors 
    
    sim_o1_to_o2 = pd.DataFrame()

    sim_o1_to_o2['objects_1']= objects_1
    sim_o1_to_o2['objects_2']= objects_2
    sim_o1_to_o2['similarity']= similarities

    return sim_o1_to_o2

生成相似点

get_similarities(df_1,df_2, ['feature_0', 'feature_1', 'feature_2'])

Answer 1

使用Faiss

import faiss

dimension = 100

value1 = np.random.random((n, dimension)).astype('float32')
index = faiss.IndexFlatL2(d)
index.add(value1)

xq = value2
k= len(value1)
D, I = index.search(xq, k) 

请注意，这里 D 是距离，I 是值的索引。

此外，value1 和 value2 只是 NumPy 数组。

PS:先安装faiss。

pip install faiss