Подход к выявлению подмножеств похожих документов А. Антонов, С. Баглей, В. Мешков { alexa, baglei, galaktika.ru

Особенности поиска информации Пользователю сложно взаимодействовать с поисковой системой Пример реального запроса пользователя: Сергей Иванов и не (оборона или Путин или список или эстонский) не "Оренбурггазпром" и не волгоградская епархия и не "Минобороны" и не "газовик" не наш конкурс и не наш приз и не "матч" и не правильный ответ не "кардиология" и не сердце" не счетная палата и не "Севастополь" и не "севастопольский" не "шк" и не "гонщик" и гонка и неРусский банк и не "интернешнл" и не "ВИ"// не русские бабки и не"РЖД Результаты, выдаваемые по запросу, избыточны

Средства понижения информационной избыточности Совершенствование алгоритмов поиска Автоматическое структурирование результатов поиска Кластеризация и классификация результатов поиска

Преимущества системы Галактика-Zoom с точки зрения организации работы алгоритма Использование технологии Информационного Портрета системы Галактика-Zoom позволяет: Получить величины относительной значимости признаков для документа; Упорядочить признаки документа по принципу их относительной значимости в выборке.

ИнфоПортрет в системе Галактика-Zoom ИнфоПортрет – множество значимых слов и словосочетаний, которое составляет пространство признаков. Координатами точки являются величины значимости каждого элемента ИнфоПортрета для данного документа: вклад признака в близость ИнфоПортретов. Величина значимости признака задается формулой: x = M x D x f, где: M - основная составляющая вклада признака в близость ИнфоПортретов; D - невязка близости ИнфоПортретов; f - фильтрующий множитель.

Алгоритм построения подмножеств похожих документов: Шаг 1 Инициализация: построение ИП каждого документа из множества D l с сохранением в двоичном формате. Формирование и сохранение вектора S 1. Документы, у которых отсутствуют ИП, добавляются в список U 0.

Алгоритм построения подмножеств похожих документов: Шаг 2 Множество D l разбивается на два непересекающихся подмножества: D l + - документы, размер ИП которых не меньше наибольшего размера ИП в векторе и D l - - документы с меньшими размерами.

Алгоритм построения подмножеств похожих документов: Шаг 3 Если подмножество D l + не пустое, то формирование вектора S w из документов множества D l +, центроидов из подмножеств C похожих документов и из списка U уникальных документов. Применение алгоритма ППД к документам из множества D l + как возможным новым центроидам. Если центроид из C приписывается к новому подмножеству, то для всех документов похожих на него пересчитывается мера близости относительно нового центроида.

Алгоритм построения подмножеств похожих документов: Шаг 4 Если остались уникальные документы из подмножества D l + или подмножество D l - – не пустое, то формирование вектора S w из уникальных документов подмножеств D l +, D l -, и центроидов подмножеств похожих документов. Применение алгоритма ППД к уникальным документам из подмножества D l + и центроидам с возможным пополнением их новыми документами из D l -.

Алгоритм построения подмножеств похожих документов: Шаг 5 Если после выполнения шагов 3 и 4 остались уникальные документы из множества D l, то формирование вектора из всех оставшихся уникальных документов. Применение алгоритма ППД к каждому уникальному документу из множества D l.

Результат работы алгоритма Набор подмножеств похожих документов С l Список уникальных документов U l

Экспериментальная проверка: основные характеристики базы ПараметрКоличество Документов в базе 5000 Слов в базе Словомест в базе Словосочетаний в базе Мест словосочетаний в базе

Экспериментальная проверка: характеристики результатов Параметр Количество Количество подмножеств похожих документов 31 Количество документов в выборке523 Количество документов, включенных в подмножества 426 (82%) Количество документов, общих для подмножеств0 Минимальное число документов в подмножестве3 Максимальное число документов в подмножестве 21 Минимальное число объектов в подмножестве3 Максимальное число объектов в подмножестве10

Результаты применения алгоритма Обеспечена возможность разбиения множества документов на подмножества похожих Получены приемлемые параметры точности и полноты разбиения

Спасибо за внимание