Эффективно вычислить матрицу смежности

Question

У меня есть набор данных с рекомендациями, который я преобразовал в матрицу вида:

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

, где NaN - это элементы, которые конкретный пользователь еще не просмотрел. Выше приведено в виде pandas кадра данных. Я хочу построить из этого матрицу смежности, основанную на предопределенном расстоянии metri c. У меня есть рабочая функция:

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

Answer 1

Похоже, вы хотите получить среднее абсолютное расстояние метри c, хотя это не совсем то, что вы написали (поскольку вы нормализуетесь не по размеру пересечения, а по размеру меньшего вектора). Если вы хотите получить среднее абсолютное расстояние, это просто:

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

Затем вы можете использовать этот показатель c с 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 s и использовать их для построения матрицы смежности.

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