ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Публикационная активность

(сведения по итогам 2016 г.)
2-летний импакт-фактор РИНЦ: 0,493
2-летний импакт-фактор РИНЦ без самоцитирования: 0,389
Двухлетний импакт-фактор РИНЦ с учетом цитирования из всех
источников: 0,732
5-летний импакт-фактор РИНЦ: 0,364
5-летний импакт-фактор РИНЦ без самоцитирования: 0,303
Суммарное число цитирований журнала в РИНЦ: 5022
Пятилетний индекс Херфиндаля по цитирующим журналам: 355
Индекс Херфиндаля по организациям авторов: 499
Десятилетний индекс Хирша: 11
Место в общем рейтинге SCIENCE INDEX за 2016 год: 304
Место в рейтинге SCIENCE INDEX за 2016 год по тематике "Автоматика. Вычислительная техника": 11

Больше данных по публикационной активности нашего журнале за 2008-2016 гг. на сайте РИНЦ

Вход


Забыли пароль? / Регистрация

Добавить в закладки

Следующий номер на сайте

4
Ожидается:
16 Декабря 2017

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

Algorithms of conceptual modeling and text classification in the tuvan language corpus
Дата подачи статьи: 2017-06-15
УДК: 519.688:004.93
Статья опубликована в выпуске журнала № 3 за 2017 год. [ на стр. 487-495 ][ 25.08.2017 ]
Аннотация:Корпус языка это информационно-лингвистическая система, основанная на собрании оцифрованных текстов некоторого языка. На сегодняшний день корпус тувинского языка включает официально-деловые документы и произведения тувинской художественной литературы. Работы по расширению корпуса тувинского языка и углублению уровня обработки текстов продолжаются. Они приводят к необходимости решения задач анализа естестественно-языковых текстов. Основными из этих задач являются классификация по прецедентам и концептуальное моделирование. Для их решения в статье используется алгебраический подход, называемый анализом формальных понятий. Предлагаются алгоритмы и программы для построения концептуальной модели коллекции литературных произведений и решения задачи бинарной классификации по прецедентам. Указаны приемы снижения вычислительной сложности рассматриваемых алгоритмов. В работе представлены результаты вычислительных экспериментов, подтверждающие результативность предложенных приемов по снижению сложности вычислений. Приведены результаты концептуального моделирования и бинарной классификации произведений тувинского фольклора.
Abstract:The corpus is an information-linguistic system based on the collection of digitized texts in some language. Nowadays, the corpus of Tuvan language includes official and business documents and Tuvan literary works. Expanding of the Tuvan corpus and deepening of the text processing level are continuening. These works lead to the tasks of a natural language text analysis. The main tasks is classification by precedents and conceptual modeling. In order to solve these problems, the paper uses an algebraic approach, which is called the analysis of formal concepts. The paper proposes algorithms and programs for constructing a conceptual model of literary works collection and solving the problem of a binary classification by precedents. There are methods of reducing computational complexity of the considered algorithms. The paper presents the results of computational experiments, which confirm the effectiveness of the proposed methods for reducing computation complexity. Finally, there are the results of conceptual modeling and binary classification of Tuvan folklore works.
Авторы: Быкова В.В. (bykvalen@mail.ru) - Сибирский Федеральный университет, Красноярск, Россия, доктор физико-математических наук, Монгуш Ч.М. (mongushchod91@yandex.ru) - Сибирский федеральный университет, Тувинский государственный университет, Красноярск, Кызыл, Россия, Аспирант
Ключевые слова: алгоритмы снижения размерности контекстов, алгоритм классификации, концептуальные модели текстов, анализ формальных понятий, корпус языка
Keywords: algorithms of reducing a context dimension, classification algorithm, conceptual models of texts, formal concept analysis, corpus
Количество просмотров: 446
Статья в формате PDF
Выпуск в формате PDF (8.13Мб)
Скачать обложку в формате PDF (0.59Мб)

Размер шрифта:       Шрифт:

В настоящее время активно создаются корпусы языков народов Российской Федерации для сохранения национального литературного наследия и проведения научных исследований по изучению этих языков. Работа над созданием Национального корпуса тувинского языка ведется сотрудниками, аспирантами и студентами Тувинского государственного и Сибирского федерального университетов [1]. Под корпусом понимается информационно-лингвистическая система, основанная на собрании оцифрованных текстов. Корпус включает в себя различные типы текстов, представленных в языке, а также разметку – информацию о свойствах текстов. В рамках корпусов решаются многие задачи анализа естестественно-языковых текстов, возникающие в филологических и лингвистических исследованиях [2]. Основными из них являются  классификация по прецедентам и концептуальное моделирование. Классификация по прецедентам, как правило, направлена на установление жанра и автора текста, определение пространственно-временного периода написания произведения. Цель концептуального моделирования - структурное представление знаний, извлеченных из текстов произведений (например, особенности использования языковых клише и диалектных вариантов эпических выражений).

Традиционными подходами для решения задачи классификации являются методы машинного обучения и математической статистики, основанные на количественных мерах близости рассматриваемых текстов [3]. В этом случае, как правило, се- мантическая составляющая анализируемых тек- стов не рассматривается. Для построения концептуальных моделей текстов обычно используются концептуальные графы и решетки понятий [3]. Однако существует формализованный подход, известный в литературе как анализ формальных понятий, который позволяет выполнять классификацию, концептуальное моделирование и решать многие другие задачи анализа текстов на основе алгебраической теории решеток [4, 5]. В рамках этого подхода тексты анализируются на семантическом уровне, моделируются и представляются бинарными контекстами, отражающими наличие или отсутствие признаков, характерных для исследуемых произведений. Использование методов анализа формальных понятий позволяет не включать в ПО корпусов пакеты программ, ориентированные на решение отдельных задач анализа данных.

Анализ формальных понятий (АФП) является прикладной ветвью алгебраической теории решеток, в рамках которой возможна формализация терминов «понятие» и «иерархия понятий».

Основные идеи АФП были сформулированы в работе Р. Вилле и Б. Гантера [6] и развиты в исследованиях С.О. Кузнецова, Д.И. Игнатова, С.И. Гурова [5, 7]. В АФП формальные понятия определяются с помощью соответствий Галуа и представляют собой пары множеств вида (объем, содержание). Основным достоинством такого определения является абсолютное соответствие традиционной трактовке термина «понятие», используемого в гуманитарных науках [8].

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

Основные термины и обозначения

Приведем термины и обозначения, применяемые в АФП [6].

Пусть для некоторой предметной области определены два непустых конечных множества G и M объектов и признаков соответственно (от немецких слов Gegenstände – объект, Merkmale – признак). Пусть также задано отношение инцидентности между множествами G и M: I Í G ´ M. Существование в I пары (g, m), g Î G и m Î M, означает, что объект g имеет признак m и, наоборот, признак m присущ объекту g. Тройка K = (G, M, I) называется формальным контекстом (или кратко контекстом) для рассматриваемой предметной области. Если множества G и M линейно упорядочены (например лексикографически), то контекст можно однозначно (с точностью до «материальной» природы объектов и признаков) задать бинарной матрицей T, отражающей отношение инцидентности I.

Выберем два произвольных элемента g Î G и m Î M. Определим для них отображения j и y:

j(g) = {m Î M | (g, m) Î I} – множество признаков, присущих объекту g Î G;

y(m) = {g Î G | (g, m) Î I} – множество объектов, обладающих признаком m Î M.

Отображения j и y можно обобщить на произвольные A Í G и B Í M следующим образом:

φ(A) = {m Î M | " g Î A  (g, m) Î I},

ψ(B) = {g Î G | " m Î B  (g, m) Î I}.

Здесь φ(A) - множество признаков, общих для всех объектов из A, а ψ(B) - множество объектов, обладающих всеми признаками из B. При этом считается, что j(Æ) = M и y(Æ) = G, то есть пустому множеству объектов присущи все признаки из M, и каждый объект рассматриваемого контекста обладает пустым множеством признаков. Отображения j и y определены так, что для любых A1, A2 Í G и B1, B2 Í M верны равенства:

j(A1 È A2) = j(A1) Ç j(A2),

y(B1 È B2) = y(B1) Ç y(B2).

Обычно в анализе формальных понятий для отображений j и y применяется единое обозначение (×)¢, а приведенные выше формулы для j(A), y(B) записываются так:

A¢ = Ç g Î A g¢ = {m Î M | "g Î A  (g, m) Î I}, (1)

B¢ = Ç m Î B m¢ = {g Î G | "m Î B  (g, m) Î I}. (2)

Если g Î G и m Î M, то обозначения g¢ и m¢ служат сокращенной формой записи множеств j(g) = {g}¢ и y(m) = {m}¢ соответственно. Отображения «¢» удовлетворяют свойствам, вытекающим из их определения и вполне реалистичного и постулируемого в анализе данных положения: расширение (сокращение) множества признаков уменьшает (увеличивает) число объектов, обладающих этими признаками. Формально эти свойства можно выразить в виде следующих утверждений.

Утверждение 1. Для всякого контекста K = (G, M, I) и любых B1, B2 Í M верны свойства:

- антимонотонность:

если B1 Í B2, то (B2)¢ Í (B1)¢;

- экстенсивность:

B1 Í (B1)¢¢, где (B1)¢¢ = ((B1)¢)¢ Í M.

Утверждение 2. Для всякого контекста K = (G, M, I) и любых A1, A2 Í G верны свойства:

- антимонотонность:

если A1 Í A2, то (A2)¢ Í (A1)¢;

- экстенсивность:

A1 Í (A1)¢¢, где (A1)¢¢ = ((A1)¢)¢ Í G.

Множество (B1)¢¢ = j(y(B1)) можно трактовать как набор признаков, которые всегда появляются в объектах контекста K = (G, M, I) вместе с признаками из B1, причем это множество является наибольшим по включению в пределах этого контекста. Множество (A1)¢¢ = y(j(A1)) можно интерпретировать как наибольшее по включению множество объектов, которые обладают всеми признаками, характерными для объектов A1. Согласно утверждениям 1 и 2, отображения j и y составляют пару соответствий Галуа между множествами 2G и 2M, частично упорядоченными по включению [9]. Здесь традиционно 2G и 2M – совокупность всех подмножеств рассматриваемых множеств G и M соответственно. Двойное применение отображения «¢» определяет оператор замыкания «¢¢» на 2G или 2M в алгебраическом смысле [9].

Множество признаков B Í M, для которого B = B¢¢, называется замкнутым в контексте K = (G, M, I). Принято говорить, что множество B¢¢ является замыканием для B Í M в контексте K = (G, M, I). Исходя из (1) и (2), при B¢ ¹ Æ замыкание для B Í M можно вычислить по формуле

B¢¢ = Ç g Î G {g¢ | B Í g¢}.                                   (3)

Если B¢ = Æ, то всегда B¢¢ = j(y(B)) = j(Æ) = M. Важно отметить, что применение формулы (3) позволяет за один просмотр контекста K = (G, M, I) найти замыкание для заданного множества признаков.

Концептуальное моделирование и АФП

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

Для описания концептуальных моделей используются различные средства, но в основном гра- фические (диаграммы «сущность–связь», концептуальные графы, решетки понятий). В системах обработки текстовых данных применяются преимущественно концептуальные графы и решет- ки [3]. Анализ формальных понятий позволяет не только представить (описать и визуализировать) концептуальную модель, но и построить ее, исходя из формальных контекстов. Формальный контекст является абстрактной моделью исследуемой предметной области, отражающей отношение инцидентности между объектами и их свойствами. Имея в наличии формальный контекст, с помощью математических методов АФП можно выявить основные понятия предметной области, установить между ними отношение частичного порядка и объединить формальные понятия в решетку. Такая решетка понятий – математическое описание концептуальной модели, допускающее ее исследование математическими методами.

Дадим определение решетки формальных понятий. Пусть для некоторой предметной области задан формальный контекст K = (G, M, I), где G - множество объектов; M - множество признаков; I - отношение инцидентности между множествами G и M. Пара (A, B), A Í G, B Í M, такая, что A¢ = B и B¢ = A, называется формальным понятием с объемом A и содержанием B. Другими словами, пара множеств (A, B) является формальным понятием для контекста K = (G, M, I) тогда и только тогда, когда A = A¢¢ и B = B¢¢, то есть когда A, B -  замкнутые множества относительно оператора «¢¢». Если контекст K = (G, M, I) представлен матрицей T, то формальному понятию (A, B) соответствует ее максимальная подматрица, заполненная единицами. Строки этой подматрицы отвечают элементам из A, а столбцы - элементам из B.

Пусть FCK - множество всех формальных понятий контекста K = (G, M, I). Введем на FCK  отношение частичного порядка ⊑ следующим образом:

(A1, B1) ⊑ (A2, B2), если A1 Í A2 (или B2 Í B1), (4)

где A1, A2 Í G и B1, B2 Í M. Заметим, что в высказывании (4) достаточно указать лишь одно из двух включений A1 Í A2 или B2 Í B1, поскольку в силу антимонотонности отображений «¢» из одного из них всегда следует другое. Согласно (4), если (A1, B1) ⊑ (A2, B2), формальное понятие (A2, B2) можно считать более общим, чем понятие (A1, B1), поскольку оно имеет меньший набор характерных признаков, а значит, большее число объектов, обладающих этими признаками.

Определим на FCK операции пересечения ⊓ и объединения ⊔ через одноименные теоретико-множественные операции Ç и È следующим образом:

(A1, B1) ⊓ (A2, B2) = (A1 Ç A2, (A1 Ç A2)¢),            (5)

(A1, B1) ⊔ (A2, B2) = ((B1 Ç B2)¢, B1 Ç B2).            (6)

Тогда частично упорядоченное множество (FCK, ⊑) образует решетку LK = (FCK , ⊓, ⊔). Операции ⊔ и ⊓, установленные соотношениями (5) и (6), удовлетворяют всем необходимым для решеток законам ассоциативности, коммутативности, идемпотентности и поглощения [9]. Эта решетка называется решеткой формальных понятий контекста K = (G, M, I). Известно, что LK является полной решеткой [6]. Нулем решетки LK является формальное понятие (M¢, M), содержащее все признаки контекста K = (G, M, I), а единицей - формальное понятие (G, G¢), в котором объем - множество всех объектов рассматриваемого контекста.

Решетка LK связывает все элементы частично упорядоченного множества FCK в определенную иерархическую структуру. Чем выше уровень расположения формального понятия в LK, тем более общим по отношению к формальным понятиям, находящимся ниже в LK, оно является. Таким образом, решетка LK – это формализованное представление множества формальных понятий и связей между ними в смысле отношения (4). Причем каждое формальное понятие этой решетки определяет множество однородных объектов исследуемой предметной области со своим специфичным набором признаков. На основе решетки формальных понятий и методов АФП можно решать задачу бинарной классификации по прецедентам.

Задача бинарной классификации по прецедентам и алгоритм ее решения

Известны различные формулировки задачи классификации [3, 7]. Задача бинарной классификации по прецедентам традиционно формулируется следующим образом. Пусть задано конечное множество объектов G, разделенное на два класса G+ и G-, G+ Ç G– = Æ, G+ È G– = G. Такое разбиение определено с помощью некоторой обучающей выборки и целевого бинарного признака z. Элементы множеств G+ и G– называют положительными и от- рицательными прецедентами соответственно. Все объекты из G описаны через конечное множество признаков M, которое задается (0, 1)-матрицей T, кодирующей наличие или отсутствие признака m Î M для объекта g Î G. Пусть задан некоторый объект x Ï G. Считается, что он обладает множеством признаков Mx Í M. Требуется найти решающее правило, которое для объекта x определяет класс принадлежности. Решающее правило должно приводить к отказу от классификации, когда принадлежность объекта x к тому или иному классу не может быть однозначно определена.

Для описания данной задачи в терминах АФП достаточно лишь уточнить вид представления классов G+ и G-. С этой целью сопоставим классу G+ положительный контекст K+ = (G+, M, I+), а классу G- - отрицательный контекст K– = (G-, M, I-). Существование в I+ пары (g, m) означает, что объект g Î G+ имеет признак m Î M. Аналогично принадлежность пары (g, m) к I- говорит о том, что объекту g Î G- присущ признак m Î M. Таким образом, бинарная матрица T разбивается на две подматрицы, соответствующие отношениям инцидентности I+ и I-.

Существуют различные алгоритмы классификации на основе АФП. К ним относятся алгоритмы Rulearner, GALOIS, GRAND, CITREC, CLNN & CLNB и LEGAL, использующие всю решетку понятий или ее некоторое подмножество [10], и алгоритмы, основанные на гипотезах [7]. В данной статье задача бинарной классификации по прецедентам решается с помощью гипотез.

Гипотезой называется некоторый набор признаков, который присутствует в описании объектов одного класса и не присутствует в описании объектов другого класса. Гипотезы извлекаются из решеток формальных понятий LK+ и LK-, построенных для контекстов K+ и K– соответственно. Содержание B+ формального понятия (A+, B+) Î LK+ называется положительной гипотезой, если не существует такого формального понятия (A-, B-) Î LK-, что B+ Í B-. В противном случае множество признаков B+ называется фальсифицированной положительной гипотезой. Аналогичным образом опреде- ляются отрицательные гипотезы и фальсифицированные отрицательные гипотезы: содержание B- формального понятия (A-, B-) Î LK- считается отрицательной гипотезой, если не существует такого формального понятия (A+, B+) Î LK+, что B- Í B+, иначе B- является фальсифицированной отрицательной гипотезой.

Решающее правило бинарной классификации по прецедентам для объекта x можно сформулировать следующим образом [7]:

- объект x относится к классу G+, если множество Mx включает хотя бы одну положительную гипотезу и не включает ни одной отрицательной гипотезы; в противном случае объект x относится к классу G-;

- отказ от классификации происходит, если Mx не включает в качестве подмножеств ни положительные, ни отрицательные гипотезы, или если Mx включает как положительные, так и отрицательные гипотезы.

Процесс решения задачи бинарной классификации на основе гипотез состоит из пяти этапов:

1-й этап – предобработка исходных контекстов;

2-й этап – нахождение формальных понятий в K+ и K–;

3-й этап – построение решеток LK+ и LK-;

4-й этап – выявление гипотез;

5-й этап – применение решающего правила бинарной классификации для объекта x Ï G.

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

Случай 1 (дубликаты строк).

Пусть в K+ = (G+, M, I+) существует множество объектов A = {g1, g2}, таких, что g1¢ = g2¢ = B. Тогда A¢¢ = (g1¢ Ç g2¢)¢ = (B Ç B)¢ = (B)¢ = A, то есть A является замкнутым множеством. Следовательно, объект g2 можно удалить из K+ и не учитывать при вычислении положительных формальных понятий. При построении решетки LK+ объект g2 необходимо добавить в объемы тех формальных понятий, в которые вошел объект g1.

Случай 2 (нулевые строки и столбцы).

Если в K+ = (G+, M, I+) существует такой объект g, что g¢ = Æ, то g¢¢ = (g¢)¢ = (Æ)¢ = G+. Аналогично, если в K+ = (G+, M, I+) имеется признак m Î M, такой, что m¢ = Æ, то m¢¢ = (m¢)¢ = (Æ)¢ = M. Поэтому на момент вычисления положительных формальных понятий объект g и признак m следует отбросить, а затем при построении LK+ объект g добавить в единицу, а признак m – в ноль этой решетки.

Случай 3 (единичные строки и столбцы).

Если в контексте K+ = (G+, M, I+) существует такой объект g Î G+, что g¢ = M, то g¢¢ = (g¢)¢ = = (M)¢ = g. Поэтому объект g надо опустить при нахождении формальных понятий, но затем добавить в решетку LK+ новое формальное понятие (g, M), а объемы всех ранее полученных положительных формальных понятий пополнить объектом g. Аналогично, если имеется такой признак m, что m¢ = G+, m вначале необходимо опустить и потом добавить в содержание всех формальных понятий решетки LK+.

На втором и третьем этапах выявляются формальные понятия в исходных контекстах K+ и K–, прошедших предобработку. Простейшим спосо- бом осуществления этих действий является пере- бор всех различных подмножеств множества признаков (их число, как правило, значительно меньше числа объектов) с вычислением для каждого из них замыкания по формуле (3). Затем на основе (4)–(6) строятся решетки LK+ и LK- для контекстов K+ и K– соответственно.

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

Проблема построения решетки формальных понятий и приемы снижения сложности вычислений

Рассмотренные выше задачи концептуального моделирования и бинарной классификации опираются на решетки формальных понятий. Известно, что задача порождения для заданного контекста всех формальных понятий и построения решетки формальных понятий является NP-трудной. Обоснование этого факта дано в [5]. Высокая вычислительная сложность данной задачи объясняется тем, что число формальных понятий может экспоненциально зависеть от размера контекста. Например, это имеет место для контекстов вида K = (G, M, ¹). Поэтому время, необходимое на выявление формальных понятий в контексте K = (G, M, I) и построение решетки, в худшем случае составляет O(|FCK| × |G|2 × |M|), где |FCK| - число формальных понятий. Далее предлагаются два приема снижения вычислительной сложности этого процесса.

Прием 1: уменьшение размера величин |G| и |M| с помощью алгоритмов обработки случаев 1–3.

Эти случаи описаны выше, там же доказана корректность их применения. Время реализации приема 1 составляет O(|G| × |M|).

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

Введем понятие бокса через объектные и признаковые формальные понятия контекста K = (G, M, I). Назовем объектным понятием формальное понятие вида (g¢¢, g¢), где g Î G, а признаковым понятием - формальное понятие вида (m¢, m¢¢), где m Î M. Таким образом, каждому объекту из G соответствует одно объектное понятие, и каждому признаку из M - одно признаковое понятие. Сле- довательно, для контекста K = (G, M, I) число объектных понятий равно |G|, а число признаковых понятий составляет |M|. Заметим, что объектное понятие (g¢¢, g¢) имеет самое большое по размеру содержание g¢ среди других формальных понятий, имеющих в объеме объект g, а признаковое понятие (m¢, m¢¢) – самый большой объем m¢ среди других понятий, имеющих в содержании признак m. Это следует из антимонотонности соответствий Галуа, указанных в утверждениях 1 и 2.

Обозначим через OK = {(g¢¢, g¢) | " g Î G} Í FCK множество всех объектных понятий и через SK = {(m¢, m¢¢) | " m Î M} Í FCK  множество всех признаковых понятий контекста K = (G, M, I). Заметим, что множества OK и SK могут иметь непустое пересечение. Выберем два формальных понятия (g¢¢, g¢) Î OK и (m¢, m¢¢) Î SK. Если для них верно отношение порядка (g¢¢, g¢) ⊑ (m¢, m¢¢) или, то же самое, выполняются условия

g¢¢ Í m¢ и m¢¢ Í g¢,                                               (7)

то пару (m¢, g¢) назовем боксом контекста K = (G, M, I), образованным элементами g Î G и m Î M. Пусть формальное понятие (A, B) Î FCK вложено в бокс (m¢, g¢) контекста K = (G, M, I), если A Í m¢ и B Í g¢. Всякий бокс (m¢, g¢) не является пустым, поскольку согласно (7) в него всегда вложены формальные понятия (g¢¢, g¢) Î OK и (m¢, m¢¢) Î SK.

Рассмотрим некоторый бокс (m¢, g¢), образованный элементами g Î G и m Î M контекста K = (G, M, I). Очевидно, что данный бокс определяет некоторую подматрицу матрицы T и образует подконтекст (G, M, C) контекста K = (G, M, I), где C Í I. При этом (x, y) Î C, если и только если x Î m¢ и y Î g¢. Соответствие между боксами и формальными понятиями контекста K = (G, M, I) устанавливает утверждение 3 [11], подтверждающее корректность приема 2.

Утверждение 3. Для всякого контекста K = (G, M, I) и любой пары множеств (A, B), где Æ ¹ A Í G, Æ ¹ B Í M, справедливы высказывания:

а) если (A, B) – формальное понятие контекста K = (G, M, I), то всегда в этом контексте существует бокс (m¢, g¢), образованный элементами g Î G и m Î M, причем, возможно, не единственный, в который это формальное понятие вкладывается;

б)  если (A, B) – формальное понятие подкон- текста (G, M, C), соответствующего некоторому боксу (m¢, g¢) контекста K = (G, M, I), то оно также является формальным понятием контекста K = (G, M, I).

Если в контексте K = (G, M, I) имеются формальные понятия (G, Æ) и (Æ, M), то для них невозможно установить признаковые и объектные понятия, поэтому они не вкладываются ни в один из боксов данного контекста. Их наличие необходимо просто учитывать при построении решеток.

Однократное формирование боксов для контекста K = (G, M, I) включает в себя следующие действия: нахождение всех объектных и признаковых понятий; проверка условия (7) для каждой пары таких формальных понятий и формирование боксов. Число анализируемых пар, проверок и полученных боксов всегда не более чем |I| = |G| × |M|. Поэтому время формирования боксов составляет O(|I| × (|G| + + |M|)). В худшем случае может быть найден только один бокс, совпадающий с исходным контекстом, и тогда декомпозиция контекста на боксы не дает эффекта. Это возможно, например, для контекста, полностью заполненного единицами. Однако реальные контексты, как правило, разлагаются на разумное число боксов. Важно отметить, что процесс разбиения контекста на боксы может быть организован итерационно, ведь каждый выявленный бокс может быть вновь разбит на боксы. Но если данный процесс продолжать до тех пор, пока все боксы выродятся в формальные понятия, это может привести к экспоненциальному числу боксов, а значит, и к экспоненциальному времени их построения. Для получения полиномиального числа боксов рекомендуется ограничиваться константным числом итераций.

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

Рассмотренные выше алгоритмы решения задач концептуального моделирования и бинарной классификации по прецедентам, а также приемы  снижения вычислительной сложности этих алгоритмов реализованы в программе FCACorpus (язык программирования Delphi). Функция визуализации решеток формальных понятий не была включена в программу FCACorpus, так как ее применение целесообразно только для контекстов сравнительно небольших размеров. Визуализировать решетку можно всегда с помощью специальных програм- мных средств [12].

Для оценки результативности приемов снижения сложности вычислений, реализованных в программе FCACorpus, были выполнены вычислительные эксперименты. Использовались контексты с числом объектов 15, 18, 20 и числом признаков 15. Эти контексты были сформированы на основе паспортов фольклорных произведений, взятых из Национального корпуса тувинского языка. Для каждого контекста K = (G, M, I) осуществлялся поиск множества FCK всех формальных понятий без разбиения и с однократным разбиением этого контекста на боксы. Результаты вычислительных экспериментов приведены в таблице 1, где |G| - количество объектов контекста; |FCK| - число найденных формальных понятий; N - количество образованных боксов; t – время выполнения программы. Вычислительные эксперименты выполнялись на компьютере с процессором IntelÒ Coreä i7-720QM Processor (6M Cache, 1.60 GHz) и ОЗУ размером 4 ГБ.

Таблица 1

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

Table 1

The experimental results

Вычисление  всех формальных понятий контекста

|G|

|FCK|

N

t, мс

Без разбиения на боксы

15

36

-

480

С разбиением на боксы

36

12

66

Без разбиения на боксы

18

73

-

12480

С разбиением на боксы

73

23

120

Без разбиения на боксы

20

98

-

30519

С разбиением на боксы

98

40

150

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

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

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

В таблице 3 представлен бинарный контекст K+ = (G+, M, I+) для четырех фольклорных произведений, где G+ = {«Арзылаӊ-Кара аъттыг Хунан-Кара», «Мөрүн-Хүлүк», «Өлээдей-Мерген», «Элестей ашак»}; M = {s1, s2, s3, s4, a1, a2, q1, q2, c1, c2, c3, t1, t2, t3}; I+ - отношение инцидентности между G+ и M.

Известно, что все произведения из G+ относятся к жанру тувинского героического эпоса [13]. В таблице 3 названия произведений заменены их поряд- ковыми номерами. Единичный (нулевой или пу- стой) элемент этой таблицы указывает на то, что соответствующее литературное произведение обладает (не обладает) тем или иным признаком.

Таблица 2

Паспорт произведения тувинского фольклора

Table 2

Passport of a Tuvan folklore work

Идентификатор признака

Значение признака

s1

Сказитель Кашкак

s2

Сказитель Хертек

s3

Сказитель Ооржак

s4

Другой сказитель или народ

a1

Горный ареал

a2

Степной ареал

q1

Есть богатырь

q2

Нет богатыря

c1

Сюжет «Сватовство»

c2

Сюжет «Сестра добывает брату суженую»

c3

Другой сюжет

t1

Зачин «Эрте шагныӊ эктинде, бурун шагныӊ мурнунда»

t2

Зачин «Шыянам, эрте бурунгу шагда»

t3

Зачин «Шыянам, эртенгиниӊ эртезинде бурунгунуӊ мурнунда»

     

Таблица 3

Контекст K+ произведений тувинского героического эпоса

Table 3

The context K+ of Tuvan heroic epic works

s1

s2

s3

s4

a1

a2

q1

q2

c1

c2

с3

t1

t2

t3

1

   

1

 

1

 

1

 

1

   

1

   

2

1

       

1

1

 

1

     

1

 

3

 

1

   

1

 

1

   

1

     

1

4

   

1

 

1

 

1

   

1

 

1

   

Заметим, что контекст K+ допускает предобработку согласно описанным выше случаям 2 и 3. Всего контекст K+ порождает 10 формальных поня- тий, которые образуют решетку LK+  (рис. 1). Еди- ницей этой решетки является формальное понятие (G+, {q1}), а нулем - (Æ, M).

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

1. Для произведений, относящихся к жанру тувинского героического эпоса, характерно прежде всего наличие богатыря, так как единицей решетки LK+ является формальное понятие (G+, {q1}). Это понятие – самое общее по отношению ко всем другим формальным понятиям этой решетки. Ведь по определению решетки, чем выше уровень расположения формального понятия в LK+, тем более общим по отношению к формальным понятиям, находящимся ниже в LK+, оно является.

2. Произведениям тувинского героического эпоса присущи признаки Горный ареал или Сюжет «Сватовство». Эти признаки входят в содержание формальных понятий ({1, 3, 4}, {a1, q1}), ({1, 2}, {q1, c1}), расположенных в решетке LK+ уровнем ниже, чем формальное понятие  (G+, {q1}), и выше всех других понятий.

3. Согласно формальному понятию ({1, 4}, {s3, a1, q1, t1}), для произведений героического эпоса, сказителем которых является Ооржак, специфичным является зачин «Эрте шагныӊ эктинде, бурун шагныӊ мурнунда».

Экспертами установлено, что указанные выводы соответствуют действительности, то есть являются филологически правильными. Каждый из указанных выводов – определенные знания о произведениях тувинского героического эпоса, представленных в K+. Очевидно, что увеличение числа произведений в K+ углубляет эти знания.

Рассмотрим теперь задачу бинарной классификации по прецедентам. Для этого сформируем отрицательный контекст K– = (G-, M, I-), состоящий из трех литературных произведений, которые не относятся к жанру тувинского героического эпоса (табл. 4). Здесь G- = {«Чечен-Маанай и Тенек-Тулун», «Караты-Хаан биле Алдын-кыс», «Кыс-Халыыр»} или с использованием порядковых номеров произведений G- = {5, 6, 7}. Следует отметить, что контекст K– также допускает предобработку. Контекст K- порождает 7 формальных понятий, которые образуют решетку LK-  (рис. 2). Единицей этой решетки является формальное понятие (G-, {s4}), а нулем - (Æ, M).

Контексты K+ = (G+, M, I+), K– = (G-, M, I-) соответствуют двум классам G+ и G– произведений, разделенных по целевому бинарному признаку z = «произведение относится (не относится) к жанру героического эпоса». Пусть задано новое произведение х с множеством признаков Mx = {s2, a1, q1, с2, t1}. Требуется для x определить класс, к которому его можно отнести.

Таблица 4

Контекст K- произведений тувинского фольклора

Table 4

The context K- of Tuvan folklore works

s1

s2

s3

s4

a1

a2

q1

q2

c1

c2

с3

t1

t2

t3

5

     

1

 

1

 

1

   

1

 

1

 

6

     

1

1

 

1

 

1

     

1

 

7

     

1

 

1

 

1

   

1

   

1

В решетке LK+ множества признаков {s3, a1, q1, t1}, {a1, q1, c2}, {s1, a2, q1, c1, t2}, {s3, a1, q1, c1, t1}, {s2, a1, q1, c2, t3}, {s3, a1, q1, c2, t1} являются положительными гипотезами, а {q1}, {a1, q1}, {q1, c1} - фальсифицированными положительными гипотезами. В решетке LK- множества признаков {s4}, {s4, t2}, {s4, a2, q2, c3}, {s4, a2, q2, c3, t3}, {s4, a1, q1, c1, t2}, {s4, a2, q2, c3, t2} определяют отрицательные гипотезы. По правилу бинарной классификации произведение x с набором признаков Mx = {s2, a1, q1, с2, t1} будет отнесено к классу G+, то есть к жанру героического эпоса, так как Mx включает положительную гипотезу {a1, q1, c2} и не содержит отрицательных гипотез. Если Mx = {s4, t2}, то произведение x будет отнесено к классу G–. При Mx = {q1} произойдет отказ от классификации. Применение метода скользящего контроля к используемому алгоритму классификации показало его вполне удовлетворительное качество [14].

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

Литература

1.     Салчак А.Я., Байыр-оол А.В. Электронный корпус тувинского языка: состояние, проблемы // Мир науки, культуры, образования. 2013. № 6. С. 408–409.

2.     Бавуу-Сюрюн М.В. Вопросы создания электронных ресурсов тувинского языка: некоторые итоги, неотложные задачи и перспективы // Новые исследования Тувы. 2016, № 4. URL: http://nit.tuva.asia/nit/article/view/610 (дата обращения: 14.06.2017).

3.     Барсегян А.А., Куприянов М.С., Степаненко В.В., Холод И.И. Технологии анализа данных: Data Mining, Visual Mining, Text Mining, OLAP. СПб: БХВ-Петербург, 2008. 384 с.

4.     Богатырев М.Ю., Нуриахметов В.Р., Вакурин В.С. Методы анализа формальных понятий в информационных системах технической поддержки // Изв. ТулГУ: Технич. науки. 2013. Вып. 2. С. 25–36.

5.     Кузнецов С.О. Автоматическое обучение на основе анализа формальных понятий // Автоматика и телемеханика. 2001. № 10. С. 3–27.

6.     Ganter B., Wille R. Formal concept analyses: mathematical foundations. Springer Science and Business Media, 2012, 284 p.

7.     Гуров С.И., Онищенко А.А. Классификация на основе АФП и бикластеризации: возможности подхода // Прикладная математика и информатика: тр. факульт. ВМК МГУ. 2011. Т. 38. С. 77–87.

8.     Vlasov D.V. The methods of forming the theoretical concepts. Jour. of the Buryat State Univ., 2009, no. 6, pp. 37-41.

9.     Биргоф Г. Теории решеток. М.: Наука, 1984. 568 с.

10.   Meddouri N., Meddouri M. Classification methods based on formal concept analysis. CLA 2008, pp. 9-16.

11.   Bykova V.V., Mongush Ch.M. On Algebraic Approach of R. Wille and B. Ganter in the Investigation of Texts. Jour. of Siberian Federal Univ.: Math. and Physics. 2017, no. 3, pp. 372–384.

12.   Евтушенко С.А. Система анализа данных CONCEPT EXPLORER // КИИ-2000: сб. тр. VII Национальн. конф. по искусств. интеллекту М.: Физматлит, 2000. С. 127-134.

13.   Орус-оол С.М. Тувинские героические сказания (текстология, поэтика, стиль). М.: МАКС Пресс, 2001. 422 с.

14.   Воронцов К.В. Комбинаторный подход к оценке качества обучаемых алгоритмов // Математические вопросы кибернетики. М.: Физматлит, 2004. T. 13. С. 5–36.


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=4320&lang=
Статья в формате PDF
Выпуск в формате PDF (8.13Мб)
Скачать обложку в формате PDF (0.59Мб)
Статья опубликована в выпуске журнала № 3 за 2017 год. [ на стр. 487-495 ]

Назад, к списку статей

Хотите оценить статью или опубликовать комментарий к ней - зарегистрируйтесь