| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Алгоритм группирования словосочетаний |
| Автор: nIkTo 25.1.2012, 12:08 |
| Необходим алгоритм группирования словосочетаний (максимально релевантных) по n словосочетаний в группе. Словосочетания хранятся в базе MySQL (MyISAM) Если кто знает, подскажите готовые решения, или тему в которой стоит покопаться .... В общем буду рад любым зацепкам. Спасибо. |
| Автор: _Y_ 25.1.2012, 12:12 |
| Непонятно что подразумевается под "максимально релевантных". Первое, что приходит в голову - копать на тему text mining |
| Автор: nIkTo 25.1.2012, 12:18 |
| _Y_, для моих целей: чем больше одинаковых слов встречается в двух словосочетаниях тем они более релевантны. |
| Автор: nworm 25.1.2012, 12:25 |
| кластеризация называется задача |
| Автор: Akina 25.1.2012, 12:26 |
| Следовательно, тебе потребуется формализация (словарь, сортированный список слов в словосочетании в таблице). также потребуется функция расчёта диаметра группы (суммарное количество уникальных слов в группе). Задача попахивает NP-полнотой - особенно если требуется распределить на группы ВСЕ имеющиеся словосочетания. |
| Автор: nIkTo 2.2.2012, 19:43 | ||
| Задача немного изменилась. Существует слово, которое встречается в каждом словосочетании. Читал про кластерный анализ и кластеризацию ... с теорией понятно:
Но вот формализовать данную задачу не могу, в общем помогите сдвинуться с мертвой точки ... |
| Автор: nworm 2.2.2012, 21:53 |
| Там по разному можно. Можно так. 1. Кластеризуется всё. 2. Классы переделываются. К маленьким классам добавляются объекты (те у которых метрика поближе к классу). Из больших классов объекты удаляются. Чтоб везде было по n объектов. Может ещё как-то лучше будет. Там переделать какой-нибудь алгоритм кластеризации чтоб он сразу на классы по n объектов разбивал. Длинная задача. И всё зависит от конкретных требований к алгоритму. |
| Автор: Mirkes 4.2.2012, 05:47 |
| Основная проблема в данной задаче отсутствие номальной метрики. И отсутствие не только метрики но и единого порядка на словосочетаниях - множество словосочетаний не является вполне упорядоченным, только частично упорядоченным. Если я правильно понимаю постановку, то формализацию можно проводить так. 1. Создаем словарь всех слов встречающихся в словосочетаниях. На этом щага решаем, работаем со словами или словоформами. Нпример, слово красный имеет кучу словоформ красная. красный красное.... 2. Произвольным образом нумеруем слова в словаре. 3. Для целей разбиения заменяем каждое словосочетание на множество номеров слов. При этом стоит отдавать себе отчет, что мы своими руками уничтожаем порядок слов - в множестве нет порядка между элементами и словосочетания красивая девушка и девушка красивая превратятся в одинаковое множество из номеров слов девушка и красивая. 4. Определяем расстояние между словосочетаниями как, например расстояние по Хаусдорфу или по Хеммингу. В данном случае проще по Хеммингу - два словосочетания тем ближе, чем больше в них одинаковых слов или чем больше мощность пересечения множеств, описывающих слова. Начиная с этого момента можно начинать строить какую-то классификацию. Отрицательный момент моей формализации. Можно получить такую цепочку "релевантных" словосочетаний красна девица, красная осень. золотая осень, золотой запас, хороший запас, хорошая хозяйка, девица хозяйка. |