Software & Systems

В настоящее время активно создаются корпусы языков народов Российской Федерации для сохранения национального литературного наследия и проведения научных исследований по изучению этих языков. Работа над созданием Национального корпуса тувинского языка ведется сотрудниками, аспирантами и студентами Тувинского государственного и Сибирского федерального университетов [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

Как видно из таблицы 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

Таблица 3

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

Table 3

The context K+ of Tuvan heroic epic works

Заметим, что контекст 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

В решетке 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.