Информационная система "Конференции"

IV Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям

Красноярск, Академгородок, 3-5 ноября 2003 года

Тезисы докладов

Вычислительная математика и математическое моделирование

Применение кластерного анализа для математического моделирования информационно поисковых систем

Половикова О.Н.

Алтайский государственный университет (Барнаул)

Поиск (информационный поиск)– одна из ключевых операций информационно-поисковых систем (ИПС). ИПС согласно правилам перевода с естественного языка на информационно-поисковый преобразует потребности потребителя для выполнения поиска, затем система осуществляет обратный перевод результатов поиска на естественный язык.

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

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

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

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

Выбор признаков ресурсов – признаков сходства, по значениям которых можно судить о сходстве (близости) между ресурсами, зависит от определения понятия «тематический раздел». Тематический раздел – совокупность информационных ресурсов из определенной области знаний. Таким образом, в качестве признаков сходства можно использовать наборы ключевых слов.

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

Для того чтобы добиться точности идентификации запроса или нового ресурса в совокупности тематических разделов, следует информационные разделы сформировать максимально «непохожими», а ресурсы одного раздела максимально «похожими». Поэтому характеристическая функция критерия качества разбиения должна зависеть от сходства ресурсов (объектов) внутри каждого кластера и от различия между кластерами (при попарном сравнении).

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

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

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

Предположение о разделимости объектов на кластеры, исходя из сопоставлений O-расстояний между объектами, полностью вписываются в сделанные раннее построения по классификации информационных ресурсов. Рассмотрим выводы, подтверждающие это предположение. Сопоставление объектов происходит по совпадению соответствующих им значений признаков близости, например, по совпадению множеств из ключевых слов: чем больше совпадений по ключевым словам, тем объекты расположены ближе друг к другу в признаковом пространстве.

Те объекты (ресурсы), которые при попарном сопоставлении имеют относительно (сравнивая с другими объектами) большее число совпадений по значениям признаков (ключевым словам) образуют в пространстве признаков компактные сгустки. Определим кластер как совокупность объектов с большим (относительно сравнения с другими объектами) совпадением значений признаков при попарном сопоставлении. При таком определении кластер отображается в пространство признаков как сгусток точек.

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

Результатом пременения данного алгоритма было выполнено 32 шага кластеризации. Построенная целевая функция критерия качества кластеризации достигает максимального значения на 29 -ом шаге, чему соответствует 221 тематический раздел (кластер).

Промежуточные данные, полученные при выполнении кластеризации 1-ого подмножества, а также нулевой шаг кластеризации отражены на динамической странице http://dbs.asu.ru/pon.knp.write_kl.

Дополнительные материалы: HTML
Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]