python - 有效计算邻接矩阵

Question

我有一个推荐数据集，已将其转换为以下形式的矩阵:

           item1       item2     item3 ...
user1       NaN         2.3       NaN
user2       1.7         3.4       NaN
user3       NaN         1.1       2.6
...

其中 NaN 是特定用户尚未查看的项目。上面是 pandas 数据框的形式。我想根据预定义的距离度量构建一个邻接矩阵。我有一个工作功能:

def compute_adjacency_matrix(reccomender_matrix):
    # replace nan with 0
    rec_num = reccomender_matrix.fillna(value=0)

    # compute the distances between every two users
    result = np.array([[compute_distance(li[2:], lj[2:]) for lj in rec_num.itertuples()] for li in rec_num.itertuples()])
    adjacency_matrix = (result > 0.0).astype(int)

    return adjacency_matrix

问题是，对于大型矩阵，计算结果的行需要很长的时间。最有效的方法是什么，可以扩展到更大的数据集？

编辑:这是计算距离函数:

def compute_distance(vec1, vec2):
    rez =  sum(abs(v1[(v1>0)&(v2>0)] - v2[(v1>0)&(v2>0)]))
    norm = np.count_nonzero(v1) if np.count_nonzero(v1) < np.count_nonzero(v2) else np.count_nonzero(v2)
    norm_rez = rez / norm
    return norm_rez

Answer 1

所以看起来您想要一个平均绝对距离度量，尽管这并不完全是您所写的(因为您不是通过交集的大小而是通过较小向量的大小进行标准化)。如果您想要平均绝对距离，只需:

def compute_distance(vec1, vec2):
    return np.nanmean(np.abs(vec1 - vec2))

然后，您可以将该指标与 scipy.spatial.distance.pdist 和 squareform 结合使用

from scipy.spatial.distance import pdist, squareform
def compute_adjacency_matrix(reccomender_matrix):
    result = squareform(pdist(reccomender_matrix.values.T, metric = compute_distance))
    result = np.nan_to_num(result)
    adjacency_matrix = (result > 0.0).astype(int)

    return adjacency_matrix

正如我在评论中指出的，我认为您需要重新考虑您的指标和输出。该代码将使任何推荐相同项目的人相邻，无论他们给出什么分数 - 除非给出相同的分数，否则他们不会相邻。不确定这就是你想要的。

稍微好一点的方法是执行 nan 并使用它们来制作邻接矩阵。

def compute_adjacency_matrix(reccomender_matrix):
    result = squareform(pdist(reccomender_matrix.values.T, metric = compute_distance))
    adjacency_matrix = np.logical_not(np.isnan(result)).astype(int)
    return adjacency_matrix

如果你不需要距离，你可以用二元运算来完成:

def adjacency(x, y):
    return np.any(np.logical_and(x, y))

def compute_adjacency_matrix(reccomender_matrix):
        return squareform(pdist(np.isfinite(reccomender_matrix.values.T), 
                                metric = adjacency)).astype(int)

最后，如果速度太慢，您可以使用 numba 来完成这一切:

import numba as nb

@nb.njit
def compute_adjacency_matrix(reccomender_matrix):
    n, m = reccomender_matrix.shape
    out = np.zeros((m, m))
    count = np.zeros((m, m))
    dists = np.zeros((m, m))
    adj = np.zeros((m, m))
    for i in range(1, m):
        for j in range(i + 1, m):
            for k in range(n):
                if not(np.isnan(reccomender_matrix[k, i]) or \
                       np.isnan(reccomender_matrix[k, j])):
                    out[i, j]   += np.abs(reccomender_matrix[k, i] - reccomender_matrix[k, j])
                    count[i, j] += 1
    for i in range(m):
        for j in range(m):
            if i == j:
                dists[i, j] = 0.
            elif i < j:
                if count[i, j] != 0:
                    dists[i, j] = out[i, j] / count [i, j]
                    adj[i, j] = 1
                else:
                    dists[i, j] = 0.
            else:
                dists[i, j] = dists[j, i]
                adj[i, j] = adj[j, i]
    return dists, adj