Алгоритмы построения партитивной классификации понятий онтологии

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

Способ построения партитивной классификации

Данный способ включает следующие алгоритмы:

• –    стратификация;

• –    поиск фрагментов;

• –    выявление связей.

Процедура «Стратификация» предназначена для построения иерархической структуры понятий онтологии по отношению «Часть–Целое». Процедура «Поиск фрагментов» направлена на выявление атомарных и неатомарных фрагментов онтологии, а также фрагментов, содержащих термины первого яруса партитивной стратификации. Процедура «Выявление связей» позволяет строить цепочки связей между двумя произвольными терминами.

Алгоритм стратификации . Партитивная стратификация – это иерархически организованная структура представления терминов с отношением «Часть–Целое» в онтологии. Первый ярус иерархии составляют термины, имеющие пустое множество терминов в слоте «Целое», и непустое множество терминов в слоте «Часть». Далее, термины, составляющие множество «Часть» терминов первого яруса, образуют второй ярус. Таким образом продолжается итеративное иерархическое построение каждого яруса. Алгоритм партитивной стратификации включает следующие основные шаги:

• –    перебор всех терминов, не имеющих «Целое», но имеющих «Часть»;

• –    добавление термина в первый ярус;

• –    перебор «Частей» исходного термина;

• –    добавление термина в следующий ярус и стратификация для данного термина.

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

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

• -    в строках и столбцах находятся термины онтологии;

• -    на пересечении – связывающее их отношение.

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

Таблица 1

Обозначение отношений

Отношение онтологии	Числовое обозначение
«Является частью»	1
«Является целым»	2
«Является видом»	3
«Является родом»	4
«Является коррелятом»	5
«Является синонимом»	6
«Является инструментом»	7
«Является субъектом или объектом»	8
«Является метаязыковым представлением»	9
«Является термином другого языка»	10
«Является действием»	11
«Является способом представления»	12
«Является сущностью»	13
«Является величиной»	14

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

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

Дан граф G = ( V , Е ), где V – множество вершин графа; Е – множество его ребер. Каждой вершине v ∈ V ставится в соответствие метка visited [ v ], которая принимает значение true , если вершина v пройдена, и false – в противном случае. В начальный момент считаем, что все вершины графа не пройдены. Пусть поиск начинается с некоторой вершины v из множества всех непомеченных вершин. Алгоритм включает следующие основные шаги.

Шаг 1. Отметить вершину v как пройденную visited [ v ] =true , назначить текущей.

Шаг 2. Если вершина u смежна с текущей u ∈ List [ v ] и является непройденной visited [ u ] =false , то считать вершину u текущей , иначе перейти к предыдущей вершине.

Шаг 3. Добавить вершину v в подграф предшествования р [ u ] = v , для вершин, у которых предшественников нет, положим р [ u ] = -1.

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

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

Алгоритм находит путь минимального веса для двух заданных вершин v и u во взвешенном графе G= ( V, E ). Предполагается, что все элементы весовой матрицы W неотрицательны ( w ij ≥0 ). На каждом шаге этого алгоритма исследуются все непомеченные вершины и определяется ближайшая к v вершина х и соответствующий кратчайший путь из v в х . Вершина х помечается. Алгоритм включает следующие основные шаги.

Шаг 1. Всем вершинам назначить вес d ( x ) =∞ , кроме вершины d(v)=0 , назначить текущей y=v .

Шаг 2. Всем вершинам назначается метка m(x)=0 , кроме вершины m(v)=1 .

Шаг 3. Для каждой непомеченной вершины x вычислить новое значение величины d(x) по формуле d(x)=min{d(x), d(y)+w(y,x)} .

Шаг 4. Выбрать непомеченную вершину x , для которой величина d(x) является наименьшей. Если для всех непомеченных вершин d(x)=∞ , то прекратить вычисления, так как в графе отсутствует путь из v в u .

Шаг 5. Найденную вершину x c минимальным весом полагаем текущей y=x и помечаем m(x)=1 .

Шаг 6. Если y=u , то найден путь веса d(u) , иначе перейти к шагу 3.

После нахождения первого кратчайшего пути между вершинами u и v по алгоритму Дейкстры производится поиск других кратчайших путей, которые должны отличаться от найденного хотя бы одним ребром. Алгоритм Йена включает следующие основные шаги.

Шаг 1. Найти первый кратчайший путь P 1 по алгоритму Дейкстры.

Шаг 2. Установить k = 2, добавить кратчайший путь P 1 в результирующий список.

Шаг 3. Выполнить k – 1 раз шаги с 4 по 7.

Шаг 4. Min = количество ребер исходного графа. Новый путь P j = ∅ .

Шаг 5. Для каждого ребра е кратчайшего пути P 1 построить граф, полученный из исходного удалением текущего ребра.

Шаг 6. Найти кратчайший путь P i в полученном графе.

Шаг 7. Если длина найденного пути P i ≤ min , то min = P i и P j = P i и удаленное ребро считать текущим.

Шаг 8. Записать новый путь P j в результирующий список.

Шаг 9. Удалить из графа ребро е .

Шаг 10. Кратчайший путь P i считать новым P j .

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

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

Для апробации представленного способа разработано программное обеспечение, на котором были проведены вычислительные эксперименты. В качестве исходной онтологии была использована онтология по предметной области «Предпринимательство». Результаты вычислительных экспериментов показаны в таблицах 2 и 3.

Таблица 2 Количество изолированных, слабосвязанных и сильносвязанных терминов онтологии по предметной области «Предпринимательство»

Тип термина	Изолированные термины	Слабосвязанные термины		Сильносвязанные термины
		со всеми терминами	со смежными терминами	со всеми терминами	со смежными терминами
Количество	509	637	871	293	56

Только из того, что изолированных вершин достаточно много, можно сделать вывод, что данная онтология недостаточного качества.

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

Таблица 3

Фрагменты партитивной классификации по отношению «Часть-Целое»

№ фрагмента	Количество терминов во фрагменте	Наименование корневого термина фрагмента
1	43	Консорциум
2	41	Долгосрочный кредит
3	24	Коносамент с оговорками
4	20	Бухгалтерский баланс
5	20	Вексельный портфель
6	18	Валовый доход
7	7	Договорная маркетинговая система
8	6	Грузовой список

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

Заключение

Партитивная классификация обеспечивает возможность определения разделов и тем предметной области. В статье рассмотрен способ, позволяющий построить партитивную классификацию по отношению «Часть–Целое». Положительные результаты экспериментов показали корректность разработанных алгоритмов и подтвердили гипотезу о возможности семантического анализа множества понятий онтологий с помощью их партитивной классификации. Данный подход использован для анализа понятий онтологии по родовидовому отношению, по которому также получены положительные результаты. Такая возможность особенно важна при автоматическом построении онтологии на основе извлечения знаний из научных текстов.