Помогите с алгоритмом по сравнению предложений

Question

[Макс]

Коллеги, обращаюсь к вам за помощью. Имеем несколько тысяч предложений, среди них необходимо сгруппировать схожие по семантике. Как я вижу это сейчас: я разбиваю все предложения на слова, убираю служебные части речи, стемматизирую их и нахожу для каждого ключ soundex. Далее по этим кодам как-то нужно найти наиболее схожие предложения. Именно с последним этапом у меня сложности. Голова кипит. Буду рад подсказке куда копать дальше или другим идеям для реализации этого

Answer 1

[DemiurgeOrion]

Хм, я не специалист, но возможно вам поможет поиск нечетких дубликатов текстов?
habrahabr.ru/post/65944/

Comments

[Cyr]

Вот еще хорошая статья по нечеткому поиску: http://habrahabr.ru/post/114997/

[Cyr]

может еще копнуть в сторону алгоритмов Diff или Patching…

[Cyr]

Вот еще реализация алгоритмов нечеткого поисrа для MS SQL: http://anastasiosyal.com/POST/2009/01/11/18.ASPX

[Макс]

Спасибо!

[Cyr]

А вот для PHP: http://habrahabr.ru/post/115394/

Answer 2

[Алексей Акулович]

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

Answer 3

[Urevic]

То, что вы хотите называется кластеризацией. Есть много разных статей про методы кластеризации — погуглите. Я как-то делал нечто похожее на основе байесовской теоремы, но для этого надо вручную выделить категории документов и обучить фильтр на какой-то выборке — работало неплохо.

В использовании soundex что-то я особого смысла не вижу, вы же не слова похожие ищите, а тексты. Можно считать crc32 от слов — точность не сильно снижает, а расчеты ускоряются очень хорошо.

Comments

[Константин Канаев]

Согласен, с упомянутым выше, методом кластеризации. Но хотелось бы немного больше информации: в каком виде у вас хранятся эти предложения? Предложения направлены на одну предметную область?

[Макс]

Спасибо. По поводу возникших вопросов: язык русский, будем считать, что предметная область одна, как хранить не суть, пусть это будет MySQL

Answer 4

[sergeypid]

Попробуйте просто k-means кластеризацию по вашим ключам. Только надо задать априори количество классов.