Определение сходства между элементами в базе данных

Question

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

Запись X может содержать запись в журнале, например:

Изменение транзакции ABC123, назначенной серверу US91

И запись Y может содержать запись в журнале, например:

Изменение транзакции XYZ789, назначенной серверу GB47

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

То, что я пытаюсь определить, - это лучший способ сгруппировать подобные предметы вместе и сказать, что с уверенностью в XX% Record X и Record Y, вероятно, имеют одинаковую природу. Или, возможно, лучшим способом сказать, что система будет смотреть на Запись Y и говорить, основываясь на вашем контенте, вы больше всего похожи на Запись X в сравнении со всеми другими записями.

Я видел некоторые упоминания об обработке естественного языка и других способах нахождения сходства между строками (например, просто грубое вычисление некоторых вычислений Левенштейна) - однако для нас у нас есть две дополнительные проблемы:

1. Контент генерируется машиной, а не человеком
2. В отличие от подхода поисковой системы, где мы определяем результаты по заданному запросу - мы пытаемся классифицировать гигантское хранилище и группировать их по тому, насколько они похожи друг на друга.

Спасибо за ваш вклад!

Answer 1

Мне приходят на ум две основные стратегии:

1. специальный. Используйте подход поиска информации. Создайте индекс для записей журнала, в конечном итоге используя специальный токенизатор / анализатор, передав их в обычную систему текстового поиска . Я слышал, что люди делают это с Xapian и Lucene. Затем вы можете «искать» новую запись в журнале, и механизм поиска текста (будем надеяться) вернет некоторые связанные записи в журнале, чтобы сравнить ее с. Обычно подход «поиск информации» интересует только поиск 10 наиболее похожих результатов.

2. кластерный подход. Обычно вам необходимо преобразовать данные в числовые векторы (которые, однако, могут быть редкими), например как TF-IDF. Затем вы можете применить алгоритм кластеризации , чтобы найти группы тесно связанных линий (например, приведенный выше пример) и исследовать их природу. Возможно, вам придется немного подправить, так что это не будет, например. кластер на сервере с идентификатором.

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

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

Answer 2

Интересная проблема. Очевидно, здесь есть проблема масштаба, потому что вы не хотите начинать сравнивать каждую запись с каждой другой записью в БД. Я полагаю, что я посмотрел бы на рост списка «известных типов» и подсчет записей по типам в этом списке, чтобы увидеть, есть ли у каждой записи совпадение в этом списке.

Надеемся, что часть «скоринг» даст здесь хорошие ответы - ваша способность набирать очки против известных типов - ключ к тому, чтобы это работало хорошо, и я чувствую, что вы находитесь в лучшем положении, чем мы, чтобы получить это так. Может, какое-то совпадение с саундексом? Или, если вы можете выяснить, как «обнаружить», какие части новых записей изменяются, вы можете определить свои известные типы как выражения регулярных выражений.

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

Answer 3

Я бы предложил проиндексировать ваши данные с помощью механизма текстового поиска, например Lucene , чтобы разбить записи в журнале на термины. Поскольку ваши данные генерируются машиной, используйте также слова биграммы и тиграммы, даже n-граммы более высокого порядка. Биграмм - это просто последовательность последовательных слов, в вашем примере у вас будут следующие биграммы:

Change_Transaction, Transaction_XYZ789, XYZ789_Assigned, Assigned_To, To_Server, Server_GB47

Для каждого журнала готовьте запросы аналогичным образом, поисковая система может дать вам наиболее похожие результаты. Возможно, вам придется немного изменить функцию подобия, чтобы получить лучшие результаты, но я считаю, что это хорошее начало.

Answer 4

Звучит так, как будто вы могли бы использовать упомянутый выше подход lucene, а затем использовать его в качестве источника для входных векторов в библиотеке машинного обучения Mahout (http://mahout.apache.org/). Оказавшись там, вы можете обучить классификатор или просто использовать один из их алгоритмов кластеризации. .

Answer 5

Если у вас есть СУБД, взгляните на SOUNDEX ().