Методика оценки эффективности методов кластеризации при построении интеллектуального репозитария

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

Ульяновский государственный технический университет

Методика оценки эффективности методов кластеризации при построении интеллектуального репозитария

Радионова Ю.А.

e-mail: julia-owl@mail.ru



Введение

Для организации интеллектуального репозитария электронной документации необходимо, прежде всего, создать систему разбиений документов по тематическим группам - классам. Существуют методы автоматических кластеризаций массива документов, основанные на индексировании текстов документов и использовании нейронных сетей для кластеризации проиндексированных документов. Осуществление поиска по тематическим группам значительно облегчает поиск необходимых документов в архиве. Но насколько приемлем подобный подход для технической документации проектной организации? Техническая и конструкторская документация имеет более жесткую структуру по сравнению с произвольными текстами и ряд особенностей, что затрудняет поиск документа только по индексированным текстам.

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



1. Экспертная классификация электронной документации

Первоначальным, уникальным и основным реквизитом технического документа является его децимальный номер. Децимальный номер определяется по жесткой схеме, регламентируемой ГОСТ и системой обозначения тематики работ на предприятии. Исходя из этого, метод экспертной классификации был разработан на основе лексического анализа децимального номера документа [2].

Были выделены четыре типа классификаций:

- по изделиям или тематике работ;

- по классам документации;

- по видам документов;

- по разделам документации.

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

Таким образом, получаем классификатор с базой знаний, накапливаемой в процессе классификации.



2. Теоретические аспекты кластеризации на основе нейронных сетей

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

Для оценки эффективности автоматической кластеризации были выбраны два алгоритма - на основе сетей Кохонена и fcm-алгоритм НЕЧЕТКОЙ кластеризации, реализации которых разработаны аспирантами кафедры «Информационные системы» УлГТУ [3, 5]. Для предварительной индексации текстов используется алгоритм индексации [4].



3. План экспериментов по оценке алгоритмов автоматических кластеризаций

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

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

Комплект документации классифицируется архивариусом-экспертом [2], при этом должно происходить накапливание базы знаний по различным типам классификации.

Далее тексты документов индексируются с помощью разработанного программного приложения «Индексатор» [4]. Результаты индексирования должны быть сохранены в базе данных для последующей кластеризации.

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

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

Документация индексируется и кластеризуется с параметрами, дающими оптимальные значения оценочной функции на первом этапе экспериментов. Вычисляются значения оценочной функции.

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



4. Математическая модель оценки качества кластеризации

Введем следующие обозначения:

- разбиение массива документов, полученное в результате экспертной классификации;

- разбиение того же массива документов, полученное в результате работы алгоритма автоматической кластеризации;

- множество документов, входящих в i-й кластер согласно экспертному делению; - номер кластера эксперта;

- множество документов, входящих в j-й кластер согласно автоматическому разбиению; - номер кластера автоматической системы.

Будем считать кластеризацию тем более качественной, чем ближе разбиение к разбиению .

Устанавливаем пары из расчета максимального совпадения элементов множеств и .

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

,

где и - редуцированные множества документов экспертной и автоматической кластеризаций, .

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

Для того чтобы убрать зависимость значения целевой функции от количества кластеров в эксперименте, значение целевой функции нормируем:

.



5. Структуры данных классификаций

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

5.1 Структура данных экспертной классификации

Экспертная классификация проводится по четырем признакам, наименования классов для которых накапливаются в процессе классификации и сохраняются в четырех таблицах-справочниках:

- clsDocuments (kod, abbreviatura, name) - виды документации;

- clsIzdelia (kod, dec_number, name) - изделия или тематика работ;

- clsClass_docum (kod, name) - классы документации;

- clsRazdel (kod, kod_zifra, name) - разделы документации.

Результаты экспертной интерактивной классификации сохраняются в виде двух таблиц:

- clsList_docum - список документов, в котором каждый документ определяется его децимальным номером (kod, dec_number);

- clsKlassifikator - классификатор документов - каждая строка представляет собой наименование классификации (name_klassification), код класса (kod_klass), к которому принадлежит в данной классификации документ, и код документа (kod_docum).

5.2 Структура данных кластеризации Кохонена

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

- inaIR (id, IRName) - список индексированных файлов;

- som_clusters (id, name) - список полученных в ходе эксперимента кластеров;

- som_cluster_res (res_id, cluster_id) - сопоставление списка документов (res_id) списку кластеров (cluster_id) В скобках указаны только те поля таблиц, которые необходимы для оценки эффективности алгоритма и подсчета значения целевой функции..

Для разделения таблиц различных экспериментов используется номер текущего эксперимента, например для эксперимента №001 таблицы имеют наименования som_cluster001 и som_cluster_res001.

5.3 Структура данных fcm-кластеризации

Для оценки результатов автоматической классификации fcm-методом необходимо сохранить пять таблиц базы данных:

- inaIR - список индексированных файлов (id-идентификатор файла, IRName - наименование файла);

- fcm_experiment - список экспериментов (id - идентификатор эксперимента, description - краткое описание эксперимента);

- fcm_model - список моделей (id - идентификатор модели, experiment_id - идентификатор эксперимента из fcm_experiment);

- fcm_cluster - список полученных в ходе эксперимента кластеров (fcm_model_id - идентификатор модели из fcm_model, id - идентификатор кластера, name - наименование кластера);

- fcm_res_cluster - сопоставление списка документов списку кластеров (res_id - идентификатор документа, cluster_id - идентификатор кластера, grade - степень вероятности принадлежности документа кластеру).

Таблица inaIR - результат индексирования массива электронных текстов - одна на все эксперименты (как Кохонена, так и fcm), в таблицах fcm_experiment, fcm_model, fcm_cluster, fcm_res_cluster накапливаются результаты всех экспериментов fcm-методом. В поле description таблицы fcm_experiment при проведении экспериментов сохраняем порядковый номер эксперимента для его дальнейшей оценки.

5.4 Преобразование данных в единую структуру

Первым этапом производится процесс «подгонки» структур таблиц экспертной классификации к структуре таблиц автоматических кластеризаций - для построения матриц соответствия.

На основе таблицы clsKlassifikator создается таблица resClusterExp.

select distinct name_klassification,kod_klass

into resClusterExp from clsKlassifikator

В таблицу добавляется поле id, содержащее уникальный идентификатор записи.

Создается таблица соответствия полученного списка кластеров списку документов.

select clsList_docum.kod as kod_docum,resClusterExp.id as kod_cluster into resClusterisatorExp

from clsList_docum,clsKlassifikator,resClusterExp

where (clsList_docum.kod=clsKlassifikator.kod_docum) and (clsKlassifikator.name_klassification= resClusterExp.name_klassification)

and (clsKlassifikator.kod_klass=resClusterExp.kod_klass)

Таблица inaIR сохраняется как resList_docum, в которую добавляется поле dec_number, заполняемое децимальным номером документа, выделенным из наименования файла и приведенным к стандартному «архивному» виду.

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

select kod as kod_exp,id as kod_avt

into resDocuments from clsList_docum,resList_docum

where clsList_docum.dec_number=resList_docum.dec_number

5.5 Преобразование структуры данных экспериментов Кохонена

Таблицы som_clustersNNN и som_clusters_resNNN сохраняются под именами resClustersNNN и resClusterisatorNNN, где NNN номер текущего эксперимента.

5.6 Преобразование структуры данных fcm-экспериментов

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

Сначала формируем список кластеров, принадлежащих эксперименту NNN: репозитарий электронный нейронный

select id,name into resFcmClustersNNN from fcm_cluster

where fcm_model_id=(select id from fcm_model

where experiment_id= (select id from fcm_experiment where description like `NNN'))

И список соответствия документов кластерам для данного эксперимента:

select * into fcm_res_clustersNNN from fcm_res_cluster

where (cluster_id in (select id from resFcmClustersNNN))

Далее для эксперимента NNN определяем список документов, с максимальными вероятностями:

select res_id,max(grade) as max_grade into max_grade_tmp

from fcm_res_clusterNNN group by res_id

И на основе этого списка определяем список соответствия документов кластерам для эксперимента NNN:

select max_grade.res_id as kod_docum,

fcm_res_clusterNNN.cluster_id as kod_cluster

into resFcmClusterisatorNNN from max_grade

inner join fcm_res_clusterNNN

on max_grade.res_id = fcm_res_clusterNNN.res_id

and max_grade.max_grade = fcm_res_clusterNNN.grade



6. Алгоритм построения оценочной функции

Таким образом, получаем таблицы:

- общие для всех экспериментов:

- resDocuments (kod_exp, kod_avt) - соответствие кодов документов экспертной классификации и автоматических кластеризаций;

- экспертной классификации:

- resClusterExp (id, name_klassification, kod_klass) - список классов;

- resClusterisatorExp (kod_docum, kod_cluster) - соответствие документов классам;

- кластеризации Кохонена:

- resClustersNNN (id, name) - список кластеров;

- resClusterisatorNNN (kod_docum, kod_cluster) - соответствие документов кластерам;

- fcm-кластеризации:

- resFcmClustersNNN (id, name) - список кластеров;

- resFcmClusterisatorNNN (kod_docum, kod_cluster) - соответствие документов кластерам.

Далее формируются таблицы - матрицы соответствий (NNN - номер эксперимента) - Таблица 1.

Таблица 1

Типы экспертных классификаций	Кластеризация Кохонена (матрицы)	Fcm-кластеризация (матрицы)
классы документации	resMatrixClass_documNNN	resFcmMatrixClass_documNNN
виды документов	resMatrixDocumentsNNN	resFcmMatrixDocumentsNNN
тематика работ	resMatrixIzdeliaNNN	resFcmMatrixIzdeliaNNN
разделы документации	resMatrixRazdelNNN	resFcmMatrixRazdelNNN

Структура матриц соответствия определяется следующими полями:

- kod_exp - код кластера экспертной классификации;

- kod_avt - код кластера автоматической классификации;

- count_eq - количество документов принадлежащих обоим кластерам;

- exp_all - количество документов, принадлежащих кластеру экспертной классификации;

- avt_all - количество документов, принадлежащих кластеру автоматической классификации.

Каждая строка матрицы формируется для кластера экспертной кластеризации N (кластеры выбираются из resClusterExp для соответствующего типа классификации) и кластера автоматической кластеризации M (кластеры выбираются из resClustersNNN или resFcmClustersNNN). Количество одинаковых документов, попавших в класс N экспертной классификации и кластер M автоматической кластеризации, определяется как количество строк запроса:

select distinct resClusterisatorExp.kod_docum

from resClusterisatorExp INNER JOIN resDocuments ON

resClusterisatorExp.kod_docum=resDocuments.kod_exp

CROSS JOIN resClusterisatorNNN

WHERE (resClusterisatorExp.kod_cluster=N) AND

(resDocuments.kod_avt IN (select kod_docum from resClusterisatorNNN where resClusterisatorNNN.kod_cluster=M))

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

select count(kod_docum) as count1

from resClusterisatorExp where kod_cluster=N

select count(kod_docum) as count2

from resClusterisatorNNN where kod_cluster=M

Текст sql-запросов приведен для случая кластеризации Кохонена. Для fcm-кластеризации таблица resClusterisatorNNN заменяется на resFcmClusterisatorNNN.

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

select sum((0.5*(exp_all-count_eq)+0.5*(avt_all-count_eq))/(exp_all*avt_all)) as res_function

from resMatrix<name_klassif><NNN>

select sum((0.5*(exp_all-count_eq)+0.5*(avt_all-count_eq))/(exp_all*avt_all)) as res_function

from resFcmMatrix<name_klassif><NNN>

где name_klassif - тип экспертной классификации, NNN - номер эксперимента кластеризации. В данном случае коэффициент важности критерия выбран 0,5, а вместо значения, максимального из количества документов экспертного класса и кластера автоматического алгоритма, берется произведение обоих количеств. Для получения значения целевой функции для эксперимента в целом значения целевой функции для каждой пары «класс - кластер» суммируются.



7. Инструментарий оценки эффективности методов автоматических кластеризаций

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

Приложение разработано в среде Borland Delphi 7.0 и использует базу данных klassification в формате MS SQL Server 2000.

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

Процесс классификации можно запустить как для всего списка документов, так и для отдельного текущего документа.

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

В процессе классификации программа проверяет наличие соответствующих классов в справочниках классификатора. Если класс найден, то он присваивается документу по данному типу классификации. Иначе программа формирует запрос к оператору на ввод нового класса данного типа.

Рис. 1. Справочники экспертного классификатора

Результат классификации можно просмотреть как для каждого отдельного документа, так и для всей совокупности документов - на вкладке «Дерево классификации» - (рис. 2).

Рис. 2. Древовидная структура классификатора

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

На вкладке «Результаты» можно просмотреть значения оценочных функций для всех типов экспертной классификации и экспериментов автоматических кластеризаций, а также матрицы соответствия и списки документов, содержащихся в различных кластерах и совпавших для конкретных кластеров экспертной и автоматической кластеризаций (рис. 3).

Заключение

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

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

Рис. 3. Результаты экспериментов

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

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



Литература

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

2. Радионова Ю.А., Селяев А.Г. Применение лексического анализа для решения задач автоматической классификации электронной документации. - Программные продукты и системы. - 2008. - № 4(84). Тверь: НТП «Фактор». - С.71-73.

3. Островский А.А., Радионова Ю.А. Кластеризация набора электронных информационных ресурсов // Автоматизация процессов управления. - 2008. - №1(11). Ульяновск: ФНПЦ ОАО «НПО «Марс». - С.101-104.

4. Селяев А.Г. Взвешивание терминов в процессах индексирования электронных информационных ресурсов // Автоматизация процессов управления. - 2007. - №2(10). Ульяновск: ФНПЦ ОАО «НПО «Марс». - С.93-96.

5. Корунова Н.В. Кластеризация документов проектного репозитария на основе нейронной сети Кохонена. - Программные продукты и системы. - 2008. - № 4(84). Тверь: НТП «Фактор». - С.60-61.

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

...