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

Question

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

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

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

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

Изменить сделку XYZ789 Assigned To Server GB47

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

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

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

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

 
Change_Transaction, Transaction_XYZ789, XYZ789_Assigned, Assigned_To, To_Server, Server_GB47 

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

Answer 4

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

Answer 5

две основные стратегии приходят на мой взгляд, здесь:

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

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

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

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