Интеллектуальный репозиторий проектных документов

Размещено на http://www.allbest.ru/

Интеллектуальный репозиторий проектных документов

Н.В. Корунова

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

Введение

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

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

1. Структурно-функциональное решение интеллектуального хранилища

Программная система, реализующая идеи интеллектуального хранилища, состоит из следующих подсистем: подсистема индексирования электронного информационного ресурса (ЭИР) (индексатор), подсистема кластеризации ЭИР на основе нейронной сети (нейросетевой кластеризатор), подсистема кластеризации на основе fuzzy-c-means метода (fcm-кластеризатор), подсистема кластеризации на основе генетического алгоритма и классификатор (Рис. 1).

Размещено на http://www.allbest.ru/

Рис. 1. Структура интеллектуального хранилища

На модуль индексации возложены задачи предобработки текстовых документов или аннотаций к ЭИР и построение частотных словарей встречающихся терминов. Сохранение частотных таблиц выполняется в СУБД MS SQL 2000. Далее, в рамках модуля кластеризации и классификации, на основе значений относительных частот должны создаваться предметно-ориентированные кластеры, которые организуются в виде иерархии. В процессе классификации выполняется задача соотнесения вновь заносимого ЭИР с определенным кластером.

Модуль индексации представляет собой отдельный модуль программы, предназначенный для предварительного анализа электронных информационных ресурсов (форматы: MS Word, RTF, простой текстовый формат и пр.) с целью формирования данных для проведения процессов кластеризации и информационного поиска.

Подсистема индексирования ЭИР

Индексатор позволяет пользователю:

интерактивно указать группу документов для анализа,

запустить процесс индексирования.

В процессе работы индексатор ведет журнал контрольных событий (выводит на экран и записывает в log-файл).

Для оценки значимости слов в индексаторе используется методы определения частот слов каждого документа и частот, рассчитанных по формуле Шеннона (сигнал-шум). [Наместников и др., 2007]

2. Подсистема нейросетевой кластеризации

Для кластеризации применяется нейронная сеть, использующая метод обучения без учителя (unsupervised learning) - самоорганизующие карты Кохонена (Self-Organizing Map - SOM).

Кластеризатор позволяет пользователю выполнить следующие действия:

интерактивно настроить параметры подключения и подключиться к базе данных,

интерактивно изменить параметры нейронной сети,

запустить процесс кластеризации,

сохранить полученный результат в базе данных.

В системе используются две основные процедуры настройки нейронной сети: инициализации весов нейронов случайным образом и самообучение сети Кохонена (алгоритм SOM).

Сеть SOM имеет набор входных элементов (частотные портреты текстовых документов, которые необходимо инициализировать из базы данных), и набор выходных элементов (иерархию кластеров), отображающихся в виде дерева результатов. Обучение нейронной сети происходит на каждом документе.

3. Подсистема fcm-кластеризации

интеллектуальный репозиторий кластеризация кроссовер

В качестве входных данных кластеризатор использует набор ресурсов с термами и весами этих термов в ЭИР. На выходе должно быть построено дерево кластеров.

Информация о ЭИР и термах запрашивается из БД MSSQL. После загрузки ресурсов формируется набор уникальных термов, из термов загруженных ресурсов, который будет характеризовать центры кластеров. Затем пользователь выбирает параметры кластеризации, на основе которых происходит формирование первоначальной матрицы принадлежности ресурсов кластерам.

Метод FCM не является иерархическим. Для иерархической кластеризации требуется участие пользователя. Если одного уровня кластеризации недостаточно, то после его завершения пользователь сам выбирает кластеры, которые требуется кластеризовать дальше. Для каждой кластеризации также задаются параметры. Программа позволяет выполнять одновременно несколько процессов кластеризаций на одном уровне иерархии.

4. Подсистема генетической кластеризации

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

Кодирование хромосом

Хромосома представляет собой массив пар (документ, кластер). Длина такого массива всегда будет такой, сколько документов требуется разбить на кластеры. Соответственно, если стоит задача разбить информационные ресурсы на N кластеров, то его значения варьируются от 1 до N.

Селекция

Каждая хромосома оценивается мерой ее «приспособленности» (fitness-function). Наиболее приспособленные особи получают большую возможность участвовать в воспроизводстве потомства. Используется пропорциональный отбор.

Кроссовер

Используется как одноточечный, так и многоточечный кроссовер.

Мутация

После стадии кроссовера выполняется операция мутации, которая в данной задаче представляет собой обмен двух случайных номеров кластеров. Номера документов, для которых значения кластеров меняются местами, выбираются случайным образом.

Оценка приспособленности (Fitness-function)

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

Индексатор формирует список слов документа по принципу «каждое слово отделяется от другого пробелом». Для каждого термина рассчитывается его вес в данном информационном ресурсе, то есть для каждого документа мы можем определить его координату, состоящую из частот встречаемости терминов в информационном ресурсе. Координатными осями в данном случае выступают термины.

Функцию оптимальности рассчитаем как сумму евклидовых расстояний от информационных ресурсов до центров соответствующих кластеров (к которым они отнесены).

5. Алгоритм параллельного выполнения fcm-кластеризации

Для обоснования распараллеливания алгоритма выполним примерную оценку ее временной сложности.

Если записать структуру циклов для выполнения этапа вычисления центров кластеров на псевдокоде, получим:

Для каждого кластера{

Для каждого терма кластера{

Для каждого объекта{

}

}

}

Время выполнения линейно зависит от количества кластеров, количества термов и количества объектов. Для разбиения массива данных из 100 документов, 1000 уникальных термов на 10 кластеров потребуется 10·1000·100=1·106 итераций. Для разбиения на 15 кластеров для этого же набора объектов потребуется уже 15·1000·100=1.5·106 . Количество итераций возрастает линейно.

Структура циклов для этапа вычисления матрицы принадлежности:

для каждого объекта {

для каждого кластера {

для каждого кластера {

для каждого терма {

}

}

}

}

Как видно из этого кода, время его выполнения линейно зависит от количества объектов и термов и имеет квадратичную зависимость от числа кластеров. Для выполнения этого этапа необходимы вложенные циклы до третьего уровня. Таким образом, например, для разбиения массива данных из 100 документов, 1000 уникальных термов на 10 кластеров потребуется 1000·10·10·100=1·107 итераций. Для разбиения на 15 кластеров для этого же набора объектов потребуется уже 1000·15·15·100=2.25·107 . Количество итераций возрастает более чем в 2 раза.

И, наконец, вычисление целевой функции:

Для каждого кластера{

Для каждого ресурса{

Для каждого терма{

}

}

}

Время выполнения линейно зависит от количества кластеров, количества объектов.

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

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

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

6. Эксперимент

Исходные данные:

Документов: 265

Уникальных термов: 4713

Кластеров: 10

Итераций: 50

Табл. 1.

Как видно из результатов эксперимента последовательное выполнение занимает около 72 мин. в ОС Linux и около 74 в Windows XP. При этом параллельное выполнение в Linux сокращает время более чем в 2 раза.

Заключение

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

Список литературы

1. [Батыршин и др., 2007] Батыршин И. З., Недосекин А. О., Стецко А. А., Тарасов В. Б., Язенин А. В., Ярушкина Н. Г. Нечеткие гибридные системы. Теория и практика / Под ред. Н. Г. Ярушкиной. - М.: Физматлит, 2007.

2. [Наместников и др., 2007] Наместников А.М., Чекина А.В., Корунова Н.В. Интеллектуальный сетевой архив электронных информационных ресурсов// Программные продукты и системы. 2007, №4.

3. [Ярушкина, 2004] Ярушкина Н. Г. Основы теории нечетких и гибридных систем. - М.: Финансы и статистика, 2004.

Размещено на Allbest.ru