替换循环加速推荐算法中LLR相似度计算的运行效率

核心优化：用矩阵运算替代循环遍历物品对 #

LLR计算的核心是列联表的四个统计值，完全可以通过用户-物品交互矩阵的矩阵乘法批量推导，彻底抛弃低效循环：

1. 将用户-物品交互数据转为稀疏矩阵（比如scipy.sparse.csr_matrix），记为user_item_mat——行代表用户，列代表物品，值为1表示存在交互（看过/购买）。
2. 计算物品共现矩阵cooccur_mat = user_item_mat.T.dot(user_item_mat)，矩阵中cooccur_mat[i,j]就是同时交互过物品i和j的用户数（对应列联表的n11）。
3. 提取每个物品的交互用户数向量item_counts = np.array(user_item_mat.sum(axis=0)).flatten()，这是列联表的n1.（物品i的总交互数）和n.1（物品j的总交互数）。
4. 总用户数total_users = user_item_mat.shape[0]，列联表其余三个值通过向量运算批量计算：
   • n01 = item_counts - cooccur_mat
   • n10 = item_counts[:, np.newaxis] - cooccur_mat
   • n00 = total_users - item_counts[:, np.newaxis] - item_counts + cooccur_mat
5. 将这些值代入LLR公式，用numpy向量化运算批量计算所有物品对的相似度，全程无需循环。

稀疏矩阵细节优化 #

• 用稀疏矩阵存储交互数据和共现矩阵，能大幅节省内存，尤其是物品数量较多的场景。
• scipy稀疏矩阵的乘法是底层优化的C实现，效率远高于Python循环。

并行化补充方案 #

如果物品数量极大，内存无法容纳全量共现矩阵：

• 分块处理：把物品分成若干块，每次计算一块内物品与其他块的相似度，用joblib或multiprocessing并行处理分块任务。
• 过滤无效计算：跳过交互数为0的物品，或只保留热门物品配对，减少无意义的计算量。

核心代码示例 #

import scipy.sparse as sp
import numpy as np

def calculate_llr_matrix(user_item_mat):
    # 转为稀疏矩阵格式
    if not sp.issparse(user_item_mat):
        user_item_mat = sp.csr_matrix(user_item_mat)
    
    total_users = user_item_mat.shape[0]
    item_counts = np.array(user_item_mat.sum(axis=0)).flatten()
    # 计算共现矩阵，物品过多时可保留稀疏格式避免内存溢出
    cooccur_mat = user_item_mat.T.dot(user_item_mat).toarray()
    
    # 向量化计算列联表四个值
    n11 = cooccur_mat
    n10 = item_counts[:, np.newaxis] - n11
    n01 = item_counts - n11
    n00 = total_users - item_counts[:, np.newaxis] - item_counts + n11
    
    # LLR公式的向量化实现
    def llr_term(x):
        return x * np.log(x) if x > 0 else 0
    
    llr_term_vec = np.vectorize(llr_term)
    total = llr_term_vec(n11 + n10 + n01 + n00)
    row_sum = llr_term_vec(n11 + n10) + llr_term_vec(n01 + n00)
    col_sum = llr_term_vec(n11 + n01) + llr_term_vec(n10 + n00)
    cell_sum = llr_term_vec(n11) + llr_term_vec(n10) + llr_term_vec(n01) + llr_term_vec(n00)
    
    llr_mat = 2 * (total - row_sum - col_sum + cell_sum)
    # 对角线设为0（物品自身相似度无意义）
    np.fill_diagonal(llr_mat, 0)
    return llr_mat

近似计算优化（可选） #

如果不需要精确的全量相似度，可采用局部敏感哈希（LSH）将相似物品分组，只计算组内物品对的LLR，能把计算复杂度从O(N²)降到O(N)级别，适配超大规模物品集。

内容的提问来源于stack exchange，提问作者Parseval