Вопрос или проблема
Я пытаюсь нечетко сопоставить два различных набора данных, которые довольно большие. (Один из них содержит примерно 1 миллион названий компаний, а другой около 30 тысяч).
Я хочу рассчитать коэффициент сходства на основе коэффициента Джаккара для n-грамм.
Вот что я реализовал до сих пор, что является довольно наивным подходом, который просто проходит по каждой строке набора данных, рассчитывая коэффициенты сходства один за другим.
# Начальное сопоставление с коэффициентом Джаккара > 0.5
matches = []
for idx_a, row_a in data_b.iterrows():
for idx_b, row_b in df_new.iterrows():
ngrams_a = ngrams(row_a['name_std'], n=5)
ngrams_b = ngrams(row_b['name_std'], n=5)
score = jaccard_similarity(ngrams_a, ngrams_b)
matches.append({
'permno_adj': row_a['permno_adj'],
'firm_name': row_b['name_std'],
'rec_name': row_a['name_std'],
'rec_id': row_b['rec_id'],
'similarity_score': score
})
matches_df = pd.DataFrame(matches)
matches_df.sort_values(by=['firm_name', 'similarity_score'], ascending=False, inplace=True)
Я просто начинаю цикл, выбирая строку из набора данных 1, а затем рассчитываю коэффициент сходства между этой строкой и остальными строками в наборе данных 2, и сохраняю результаты.
Этот процесс, по очевидным причинам, занимает слишком много времени, чтобы его выполнить. Исходя из текущей скорости, я ожидаю, что это займет неделю или две. Я ищу, есть ли возможность ускорить этот процесс.
Я ищу любые подсказки/отзывы. Заранее спасибо!
Ответ или решение
Чтобы ускорить вычисление коэффициентов схождения Жаккара для больших наборов данных, таких как ваш, можно использовать несколько стратегий оптимизации. Процесс, который вы реализовали, действительно требует много времени из-за вложенных циклов, что приводит к квадратичной временной сложности. Ниже представлены рекомендации, которые помогут значительно улучшить производительность вашего кода.
1. Параллелизация вычислений
Поскольку расчеты для различных пар строк независимы, вы можете использовать параллельные вычисления. Библиотека multiprocessing в Python позволит вам разделить нагрузку между несколькими процессами.
import pandas as pd
from multiprocessing import Pool
def compute_similarity(row):
matches = []
ngrams_a = ngrams(row['name_std'], n=5)
for idx_b, row_b in df_new.iterrows():
ngrams_b = ngrams(row_b['name_std'], n=5)
score = jaccard_similarity(ngrams_a, ngrams_b)
if score > 0.5: # Фильтруем только схождения выше 0.5
matches.append({
'permno_adj': row['permno_adj'],
'firm_name': row_b['name_std'],
'rec_name': row['name_std'],
'rec_id': row_b['rec_id'],
'similarity_score': score
})
return matches
if __name__ == '__main__':
with Pool(processes=4) as pool: # Настройте количество процессов в зависимости от вашей системы
results = pool.map(compute_similarity, [row for idx, row in data_b.iterrows()])
matches = [item for sublist in results for item in sublist] # Объединяем все результаты
matches_df = pd.DataFrame(matches)
matches_df.sort_values(by=['firm_name', 'similarity_score'], ascending=False, inplace=True)2. Улучшение структуры данных
Используйте структуры данных, которые обеспечивают более быстрый поиск. Например, вы можете использовать хэширование для хранения n-грамм и сравнения с помощью словарей.
from collections import defaultdict
def create_ngram_dict(data, n):
ngram_dict = defaultdict(list)
for idx, row in data.iterrows():
ngrams = ngrams(row['name_std'], n)
for ngram in ngrams:
ngram_dict[ngram].append(idx)
return ngram_dict
ngram_dict_a = create_ngram_dict(data_b, 5)
ngram_dict_b = create_ngram_dict(df_new, 5)3. Использование метода "обрезки"
Коэффициент Жаккара требует, чтобы общие элементы были посчитаны только один раз. Можно использовать "обрезку" для предварительного отбора строк, которые имеют хотя бы один общий n-gram. Если строка из одного набора не делит ни одно n-gram с другой строкой, их коэффициент схождения будет равен 0, и, таким образом, не нужно будет его вычислять.
4. Индексация строк
Если ваши данные могут быть индексированы, воспользуйтесь средствами индексирования для быстрого доступа к строкам с определенными критериям. Например, преобразуйте строковые значения в числовые векторы с использованием различных техник кодирования, таких как tf-idf или word embeddings, а затем используйте метрики расстояния для фильтрации.
5. Распараллеливание на уровне данных
Рассмотрите возможность резки наборов данных на несколько частей и распараллеливания на уровне обработки данных, например, с помощью Dask или Apache Spark, что часто намного эффективнее для работы с большими данными.
Заключение
Вероятно, что комбинация перечисленных подходов обеспечит значительное ускорение ваших вычислений. Особенно стоит обратить внимание на аспекты параллелизации и предварительной фильтрации, что позволит избавиться от избыточных вычислений. Использование правильных структур данных может также снизить временные затраты на доступ и обработку данных. На практике вы можете протестировать эти методы и оценить, какие из них наиболее эффективно работают в вашем случае.