Формализация процедуры структуризации области исследований

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

Российский экономический университет им. Г.В. Плеханова

Российская таможенная академия

Формализация процедуры структуризации области исследований

Козлова И.В., доцент, к.т.н.,

Васина Е.Н., доцент, к.т.н.

Аннотация

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

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

Kozlova I.V., Vasina E.N., Procedure formalization of researches area structurization

Abstract. In the article the approach using the axiomatic similarity theory and elements of graph theory for the solution of an objective is offered. The problem of terminological network splitting - a thematic area model is solved on separate components as a problem of allocation on tolerance classes by method of splitting the graph into the fullest subgraphs.

Keywords: structurization, researches area, thematic structure, axiomatic similarity theory, tolerance class, graph theory, clustering.

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

Удобным математическим аппаратом, описывающим сходство между объектами различной природы, является аксиоматическая теория сходства (АТС). В рамках АТС сходство объектов рассматривается как отношение между попарно сравниваемыми объектами - бинарное отношение локального сходства. В свою очередь локальное сходство рассматривается как отношение толерантности, обладающее свойствами рефлексивности и симметричности [4;5].

Для целей структуризации тематической области необходимо представить локальное сходство между терминами индексирования документов баз данных в формализованном виде. С позиций АТС, имеются два множества: T = {t₁, t₂, …,t_i,…t_n} - терминов индексирования и документов D = {d₁, d₂,…,d_j,…d_m} БД. На множестве Т задается набор признаков (свойств), т.е. одноместных предикатов P(t_i) = {0,1}. Множество признаков D - документы БД. В этом случае отображение f: T>D сопоставляет каждому t_i все документы, проиндексированные этим термином,- D(t_i), D(t_i)?D. Обратное отображение f^-1: D>T сопоставляет каждому признаку d_j множество T(d_j,)терминов, имеющих этот признак.

Отображение f является отношением, т.е. подмножеством R декартова произведения множеств TЧD. Используя отношение R на множестве TЧD, выразим отображения f (T) и f^-1(D)

- множество всех признаков термина t_i;

- множество всех терминов, обладающих свойством d_j

Отношение R можно изобразить в виде ориентированного графа

G (T, D, R), множество вершин которого совпадает с , а стрелки соединяют каждую вершину t_i ? T с вершинами d_{j i} ? D, для которых предикат P(t_i ) = 1.

Дальнейшие рассуждения основываются на важном понятии АТС - «карты»: С = < Т, D, R>, где T и D- множества терминов и документов, R - отношение на TЧD. Карта - это экспликация понятия «множество с признаками». Из свойства регулярности карты C вытекает [4]:

1. Отображение f (отношение R) определено на всем множестве T и отображает T на D, т.е. каждый термин обладает хотя бы одним признаком;

2. Если для двух признаков d₁ и d₂ множества прообразов совпадают, то признаки d₁ и d₂совпадают, разным признакам соответствуют разные множества терминов.

Вхождение множества Т в карту C позволяет определить на Т отношение локального сходства ф, называемое отношением толерантности (сходства) при выполнении следующих условий:

· рефлексивность t_i ф t_i , t_i ?Т;

· симметричность t_i ф t_j > t_j ф t_i , t_i ?Т, t_j ?Т;

· интранзитивность t_i ф t_j & t_i ф t_r not >, t_j ф t_k.

Термины t_i и t_j локально сходны, если: D(t_i )? D(t_j )?Ш

Из вышесказанного следует:

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

2. Для любой регулярной карты C = <T,D,R> на множестве терминов T можно ввести отношение сходства ф.

Множество T с заданным на нем отношением толерантности ф рассматривается как пространство толерантности T_ф = <T, ф>. T_ф можно изобразить неориентированным графом G (T, ф), в котором ребрами соединены вершины - термины индексирования, связанные отношением ф.

Отношение сходства между двумя терминами определяется их совместной встречаемостью в одних и тех же документах. Это свойство терминов широко применяется при статистическом анализе документальных информационных ресурсов, а также создании карт науки. Граф G (T,ф)представляет собой «терминологическую сеть», заданную на множестве терминов индексирования [2].

Для попарно толерантных терминов используем понятие «предкласса» толерантности:

· подмножество L ? T_ф называется предклассом в T_ф, если выполнено соотношение t_i ф t_j;

· подмножество К ? T_ф называется классом толерантности, если для любых t_i и t_j, принадлежащих этому классу t_i ф t_j, а для любого t_k , не принадлежащего К, найдется в K хотя бы один термин t_j , для которого t_k ф t_j не будет выполнено.

Отсюда следует, что:

· класс толерантности - максимальный (по включению) предкласс;

· если t_i и t_j, принадлежат одному классу, то t_i ф t_j ;

· если t_i ф t_j, то существует общий класс, содержащий t_i и t_j ;

· все классы толерантности в пространстве T_ф = <T, ф> однозначно определены.

Другими словами, для нашего случая класс толерантности - это максимальное множество взаимно толерантных терминов. Локальное сходство задается как покрытие множества терминов классами толерантности. Множество всех классов толерантности для данного отношения будем обозначать K, тогда пространство толерантности будет выражено:

Отметим, что в графе G (T, ф), класс толерантности образует максимальный полный подграф: все вершины, входящие в один класс, соединены ребрами.

Таким образом, задача выделения на графе G (T, ф) классов толерантности, рассматриваемая нами как задача разбиения терминологической сети, моделирующей тематическую область, на отдельные составляющие сводится к разбиению графа G (T, ф) на максимально полные подграфы.

Существует и другой путь разбиения терминологической сети G (T, ф), состоящий в установлении отношения транзитивного замыкания на множестве T_ф. Отношение сходства, заданное на множестве терминов, в общем случае не транзитивно, т.е.

(1)

аксиоматический сходство граф терминологический сеть

Принято считать термины сходными по смыслу, если сходны их окружения, т.е. связь терминов t_i и t_k осуществляется через термин t_j. Эта связь терминов может быть получена с помощью композиции отношения ф.

Обозначим композицию отношения ф с самим собой:

ф⁽²⁾ = ф ф (2)

Условие существования отношения ф ⁽²⁾ имеет вид:

(3)

Формула (3) основана на существовании косвенной связи между терминами t_i и t_k через термин t_j.

Транзитивное замыкание отношения ф будем обозначать через . Соотношение t_i t_j, выполнено, если существует цепочка элементов из T_ф: z₀ = t_i, z₁…,z_n = t_j такая, что между соседними элементами этой цепочки выполнено отношение ф:

z₀ ф z₁, z₁ ф z₂,…z_n-1 ф z_n (4)

В частном случае эта цепочка может состоять только из двух элементов (n = 1): z₀ = t_i и z₁ = t_j. Если выполнено t_i ф t_j , т.е. z₀ ф z₁ , то выполнено и соотношение t_i t_j . Это можно записать в виде . Если цепочка состоит из трех элементов (n = 2), то t_i ф t_j и t_j ф t_k . Следовательно,

t_i ф°ф t_k и t_i t_j только в том случае, если выполнено хотя бы одно соотношение вида:

t_i ф°ф°ф… °ф t_j или t_i ф⁽ⁿ⁾ t_j (5)

Используя операцию объединения множеств, отношение транзитивного замыкания можно представить в виде:

(6)

т.е. транзитивное замыкание отношения ф - это объединение всех степеней данного отношения.

Представление отношения ф в виде графа G (Т, ф) позволяет отождествить задачу поиска транзитивного замыкания отношения ф с задачей о достижимости вершин графа, т.е. поиска произведения ребер, соединяющего вершины графа t_i и t_k. Иначе говоря, эта задача эквивалентна разбиению графа G (Т, ф) на связные компоненты, т.е. такие подграфы, в которых каждая пара вершин связана некоторым путем [9]. При этом из терминологической сети выделяются подграфы, включающие максимально возможные подмножества пар терминов, последовательно присоединяемых к исходной паре терминов с использованием связи через посредника. Каждый такой подграф моделирует отдельное тематическое направление данной области исследований.

В формализованном виде задача выделения тематических направлений в заданной области исследований выглядит следующим образом. Имеется множество документов D = {d₁, d₂,…d_i,…d_M}- фрагмент БД, являющееся информационной моделью тематической области. Осуществляется отображение

f: D>T, что приводит к заданию на множестве T отношения сходства ф в виде графа G (Т, ф) [6;7].

В качестве тематического направления принимаются следующие виды подграфов:

1. подграф графа G (Т, ф), являющийся классом толерантности G_k (Т, ф') и удовлетворяющий условиям:

а), (8)

где

b) - максимальный полный подграф, в котором выходная степень вершины t_i - kf(t_i) равна входной степени вершины t_i - bf(t_i) и равна числу вершин подграфа - 1:

kf(t_i) = bf(t_i) = n-1 (9)

2. подграф графа G (Т, ф), полученный как транзитивное замыкание отношения сходства ф и удовлетворяющий условиям:

a) (10)

где (11)

b) - связная компонента графа G (Т, ф):

kf(t_i) = bf(t_i) = 2.

Таким образом, задача разбиения графа G (Т, ф) на подграфы эквивалентна задаче разбиения множества терминов Т на классы в соответствии с некоторым критерием сходства. Это позволяет рассматривать задачу выделения тематических направлений как задачу автоматической классификации и использовать для ее решения методы кластерного анализа [8;10;11].

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

Литература

1. Васина Е.Н., Козлова И.В. Методы структурно-тематического анализа документальной информации // Научные труды Вольного экономического общества России. - 2014. - Т. 186, №186. - С. 358-364.

2. Васина Е.Н., Козлова И.В. Построение тематических структур предметных областей // Современные проблемы науки и образования. 2013. №6. - С. 208.

3. Васина Е.Н., Козлова И.В. Проблема структуризации современных информационных ресурсов // Вестник Российского экономического университета им. Г.В. Плеханова. - 2014. - №4 (70). - С. 78-89.

4. Шрейдер Ю. А. Алгебра классификации // НТИ. Сер. 2. 1974. - №9. С. 3-6.

5. Гусакова С.М., Финн В.К. О формализации локального и глобального сходств // НТИ. Сер. 2. - 1986. - №6. - С.16-18.

6. Козлова И.В. О подходах к созданию карт науки // Международный научно-исследовательский журнал. - 2015. - №10-2 (41). - С. 76-77.

7. Козлова И.В. Структурно-тематический анализ документальных информационных ресурсов // Международный научно-исследовательский журнал. - 2016. - №1-2 (43). - С. 38-40.

8. Миркин Б.Г. Методы кластер-анализа для поддержки принятия решений. - М.: Изд. дом Национального исследовательского университета «Высшая школа экономики», 2011. - 88 с.

9. Оре О. Теория графов. - Изд. 2-е, стереотипное.- М.: Наука, 1980. - 336 с.

10. Сагинов Ю.Л., Феоктистова Н.А. Использование нейросетевой технологии для количественной оценки многопараметрических объектов и процессов в экономике и бизнесе // Вестник Российского экономического университета им. Г.В. Плеханова.- 2015. - №3-4 (12). - С. 42-57.

11. Телюк М.С. Доходы населения в соотношении с производством и потреблением региона // Вестник Российского экономического университета им. Г.В. Плеханова. Вступление. Путь в науку. - 2014. - №3-4. - С. 19-23.

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