时间戳

首页 > 解决方案 > 高效计算邻接矩阵

python - 高效计算邻接矩阵

问题描述

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

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

NaN特定用户尚未查看的项目在哪里。以上是熊猫数据框的形式。我想根据预定义的距离度量从中构造一个邻接矩阵。我有一个工作功能：

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

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

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

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

标签： pythonpandasnumpy

解决方案

所以看起来你想要一个平均绝对距离度量，虽然这不是你写的（因为你不是通过交集的大小而是更小的向量的大小进行归一化）。如果你想要平均绝对距离，它很简单：

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

然后，您可以将该指标与scipy.spatial.distance.pdistandsquareform

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

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

一个更好的方法是通过nans 并使用它们来制作你的邻接矩阵。

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

推荐阅读