Алгоритм поиска часто встречающихся шаблонов, сопровождаемых набором текстовых сообщений

Question

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

msg1 = "Rahul, Your New Delhi (NDLS) - Agra Cantt (AGC) train booking is confirmed.\nPNR: 1234567890\nBooking ID: ABCDE123456789012\nView your Trip Here: https://xyz.app.link/A0b1cDEFGH\nFor any queries please write to some_url.com.\n\nHappy with our service? Rate us 5 stars: https://xyz.app.link/e/5stars"
msg2 = "Shyamu, Your Tenali Jn (TEL) - Secunderabad Jn (SC) train booking is confirmed.\nPNR: 2345678901\nBooking ID: ABCDE123456789011\nView your Trip Here: https://xyz.app.link/Ab0cdEFGHI\nFor any queries please write to some_url.com.\n\nHappy with our service? Rate us 5 stars: https://xyz.app.link/e/5stars"
msg3 = "Ramu, Sorry! Booking for your Jammu Tawi (JAT) - Kurukshetra Jn (KKDE) train with Booking ID: ABCDE123456789013 could not be confirmed due to payment failure.If money has been deducted from your account, your money will automatically be refunded to your account within 5 days.\nRe-book your ticket https://xyz.app.link/a0B1cDEFGH"

Вы можете видеть, что msg1 и msg2 используют один и тот же шаблон / шаблон (см. Ниже), а msg3 отличается (могут быть другие шаблоны обмена сообщениями с msg3).Мое требование - найти такие часто встречающиеся шаблоны в моих данных.Для приведенного выше примера шаблон / шаблон будет выглядеть следующим образом:

"<> Your <> - <> train booking is confirmed.\nPNR: <> ID: <> your Trip Here: <> any queries please write to some_url.com.\n\nHappy with our service? Rate us 5 stars: https://xyz.app.link/e/5stars"

Я попытался выполнить следующее:

1. Использовал CountVectorizer для векторизации текстовых данных.
2. Использовал DBSCANКластеризация для поиска всех кластеров и сортировки по размеру кластера.

3. Для 20 лучших кластеров:

   i) Выберите 10 случайных сообщений.

   ii) Найдите шаблонза ними следуют некоторые строковые манипуляции.

Вышеописанный метод работал, но кластеризация кажется узким местом и занимает значительное время.(около 10 минут для 100000 сообщений в моей системе)

Функция Python для поиска кластеров:

from sklearn.cluster import DBSCAN
import collections

def find_cluster(M_vector):
    # M_vector: Vectorized messages
    dbscan = DBSCAN(eps = 2, min_samples = 5)
    cls = dbscan.fit_predict(M_vector)
    count_dict = collections.Counter(cls)
    count_dict = sorted(count_dict.items(), key = lambda kv:(kv[1], kv[0]), reverse = True)
    return cls, count_dict

У меня такое ощущение, что проблему можно решить без использования машинного обучения, но яне знаю, как действовать для достижения результатов за меньшее время.В худшем случае сложность времени DBSCAN, по-видимому, составляет O(n^2) (в среднем O(nlog(n))).

Я предполагаю, что использование алгоритма Вагнера-Фишера приведет к увеличению времени, так как в нем будут вычисления для каждого сообщения с каждым другим сообщением (O(n^2) сложность времени).

Answer 1

На таких данных индексы в sklearn не помогут, и вы действительно получите O (n²) время выполнения. Вы должны использовать инвертированный индекс с текстом! Вы можете найти похожие документы гораздо эффективнее.

Для генерации шаблонов я бы использовал другой подход. Используйте minhash, метод поиска близких к дубликатам веб-страниц, но настройте его параметры так, чтобы они были более терпимыми. Затем проверьте хэши, которые встречаются очень часто. Они соответствуют общим словам, встречающимся во многих текстах.

Это будет иметь только O (n) время выполнения.

Answer 2

Поскольку у вас есть все данные, и данные имеют закрытый набор, ваша проблема закрытый мир против открытый мир .Я бы не использовал нейронную сеть для проблемы закрытого мира.

Если бы это была моя проблема, я бы

1. изолировал разделители.Исходя из вашего примера ввода это выглядит просто пробел .
2. Разобрать каждый вход на основе разделителей в токены и поместить соединения токенов в граф с количеством каждого токена.Я думаю, что это должен быть DAG на основе данных выборки.
3. Затем найдите на графике абстрактный синтаксис (AST).Я знаю, что это требует большего объяснения, но я не хочу тратить часы на этот ответ;давать это лучше, чем не давать.:)
4. Замените токены, которые различаются в AST, на идентификаторы переменных, как вы отметили в своем вопросе, например, <>

Поскольку я использую Пролог вседень с DCG , эта проблема кажется мне интуитивно понятной, но для некоторых без этого проблема может показаться пугающей .

Также сделайте несколько примеров вручную с ручкойи бумаги, чтобы вы поняли это, прежде чем писать код.Нет смысла писать код и взламывать его по ходу дела, когда вы можете получить общую картину и детали в уме, проводя время только с ручкой и бумагой.

Если это для домашней работы, поговорите с учителем ово-первых, поскольку они могут не принять это как ответ, потому что это будет то, что кричит о вашей помощи.