Как ускорить расчет матрицы расстояний? - PullRequest
Новая
       14

Как ускорить расчет матрицы расстояний?

0 голосов
/ 27 октября 2018

Задача: Я новичок в python и в настоящее время работаю над задачей кластеризации, где вычисляю сходство между потоками кликов пользователей. Поэтому я использую индекс Джакарда для сравнения наборов кликов (потока кликов) каждого из двух пользователей, сохраняя результаты в матрице расстояний NxN, а затем выполняю алгоритм кластеризации Уорда на этой матрице расстояний.

Проблема: Опробовав все с данными за 1 день (около 85 идентификаторов сеансов / пользователей), это сработало как прелесть. Теперь с 949 уникальными пользователями вычисления занимают много времени, вероятно из-за моего неэффективного кода.

Вот снимок с моего df stack_dataframe: 9329 строк x 2 столбца

Вот мой код для вычисления матрицы расстояний: 

import itertools
import pandas as pd

# Method to compute Jaccard similarity index between two sets
def compute_jaccard(session1_vals, session2_vals):
    intersection = session1_vals.intersection(session2_vals)
    union = session1_vals.union(session2_vals)
    jaccard = len(intersection)/float(len(union))
    return jaccard


stID_keys = stack_dataframe.groupby(['Session ID']).groups.keys()
print("hallo1")
New_stack_df = stack_dataframe.pivot(columns="Session ID", values="Page")
print("hallo2")
sim_df = pd.DataFrame(columns=ID_keys, index=ID_keys)

# Iterate through columns and compute metric
test = 0
print("hallo3")
for col_pair in itertools.combinations(New_stack_df.columns, 2):
   print(test)
   test += 1
   u1= col_pair[0]
   u2 = col_pair[1]
   sim_df.loc[col_pair] = compute_jaccard(set(New_stack_df[u1].dropna()), 
   set(New_stack_df[u2].dropna()))


print(sim_df)

Любая помощь высоко ценится, спасибо!

1 Ответ

0 голосов
/ 27 октября 2018

Ваш метод крайне неэффективен. Неэффективность в основном обусловлена ​​двумя причинами:

  • Цикл O (n ^ 2) в itertools.combinations(..)
  • Использование тяжелых панд. Несмотря на простоту использования, панды немного неэффективны из-за большого количества счетов.

Мы решаем их по

  • Использование scipy distance.cdist (источник написан на c) для расчета расстояний между всеми парами.
  • Используйте numpy вместо панд
  • Jit скомпилирует функцию расстояния jaccard, так как она вызывается большое количество раз.

Итак, код: 

from __future__ import division
import time
import pandas as pd
import numpy as np
from scipy.spatial import distance
import numba as nb

def _make_2D_array(lis):
    n = len(lis)
    lengths = np.array([len(x) for x in lis])
    max_len = max(lengths)
    arr = np.zeros((n, max_len))
    for i in range(n):
        arr[i, :lengths[i]] = lis[i]
    return arr, lengths

@nb.jit(nopython=True, cache=True)
def compute_jaccard(session1, session2, arr, lengths):
    """Jited funciton to calculate jaccard distance
    """
    session1, session2 = session1[0], session2[0]
    intersection, union = 0, 0

    if(lengths[session2] > lengths[session1]):
        session1, session2 = session2, session1

    marked = np.zeros((lengths[session2],))

    for x in arr[session1][:lengths[session1]]:
        x_in_2 = arr[session2][:lengths[session2]] == x
        marked[x_in_2] = 1
        if(np.any(x_in_2)):
            intersection+=1
            union+=1
        else:
            union+=1

    union+=np.sum(marked==0)

    jaccard = intersection/union

    return jaccard

def calculate_sim_between(stack_dataframe):
    # get integer encodings for session ids and pages
    session_encode, sessions = pd.factorize(stack_dataframe["Session ID"])
    page_encode, pages = pd.factorize(stack_dataframe["Page"])

    # take unique pages in each session 
    pages_in_sessions = [np.unique(page_encode[session_encode==x]) for x in range(len(sessions))]

    # convert the list of lists to numpy array
    arr, lengths = _make_2D_array(pages_in_sessions)

    # make a dummy array like [[0], [1], [2] ...] to get the distances between every pair of sessions
    _sessions = np.arange(len(sessions))[:, np.newaxis]

    # get the distances
    distances = distance.cdist(_sessions, _sessions, compute_jaccard, arr=arr, lengths=lengths)

    sim_df = pd.DataFrame(distances, columns=sessions, index=sessions)
    return sim_df

Обратите внимание, что мы скомпилировали функцию compute_jaccard, чтобы вывести событие из цикла на один уровень. Если вы не хотите устанавливать numba, просто закомментируйте декоратор.

Тайминги:

На этом примере данных: 

from faker import Faker
fake = Faker()
stack_dataframe = pd.DataFrame({"Session ID":[fake.name() for i in range(200)], "Page":[fake.name() for i in range(200)]})

сроки

Ваш метод: 69,465 с

без джита: 0,374 с

С JIT (при втором запуске, чтобы сделать скидку на время компиляции): 0,147 с

P.S .: Поскольку мы используем фальшивые данные для запуска на большой выборке для наблюдения за ускорением, на ваших реальных данных профиль синхронизации может немного отличаться.

...