Классификация документов в системе электронного документооборота | Статья в журнале «Молодой ученый»

Авторы: ,

Рубрика: Информатика

Опубликовано в Молодой учёный №10 (196) март 2018 г.

Дата публикации: 12.03.2018

Статья просмотрена: 247 раз

Библиографическое описание:

Плешкевич А. А., Королев И. Д. Классификация документов в системе электронного документооборота // Молодой ученый. — 2018. — №10. — С. 21-24. — URL https://moluch.ru/archive/196/48705/ (дата обращения: 19.04.2019).



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

Система электронного документооборота (СЭД) — организационно-техническая система, обеспечивающая процесс создания, управления доступом и распространения электронных документов в компьютерных сетях, а также обеспечивающая контроль над потоками документов в организации.

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

Теория конечных предикатов включает в себя ряд алгебр, из которых в интересах исследования выделим алгебру конечных предикатов и алгебру предикатных операций [1]. Авторами теории алгебра конечных предикатов позиционируется как универсальное средство формального описания любых объектов, наблюдаемых в мире, и выражения любого отношения. На языке алгебры предикатных операций предпочтительно выражаются действия над отношениями [1, 2].

Из работ Беклемишева Л. Д., Бондаренко М. Ф. и Кругликова Н. П. [1–3] известно, что отношения выражают внутреннее строение объектов, свойства объектов и связи между ними. Они представляют собой универсальное средство формального представления любых объектов. Никакие другие известные средства формального представления объектов свойством универсальности не обладают.

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

В данном примере в качестве категорий файлов будем использовать иерархию «раздел → дело». В каждом разделе имеется свой набор дел, к которым и будет приписываться классифицированный документ. Пусть множество исполненных документов D={d1,…,d|D|}, тогда множество разделов C={С1,…,Сn}:

С1 = {a11, a12,…,a1k1},

С2 = {a21, a22,…,a2k2},

Сn = {an1, an2,…,ankn},

где aijдело j из раздела Сi, а А = {a11,…,ankn} — множество всех дел. Представим алгоритм классификации документа следующим образом. Исполненный документ проверяется на соответствие каждому i-му разделу предикатом P(i, d). Если документ d соответствует описанию раздела Сi, предикат P(i, d), принимает значение «истина»:

Далее при помощи предиката Pv(i,j,d) проверяется соответствие d каждому j-му делу внутри раздела Сi:

Как только Pv(i,j,d) примет значение «истина» (будет определено тематическое соответствие документа делу), перебор останавливается.

Если документ не был классифицирован по разделам при первой проверке, параметры проверки изменяются, либо проверка останавливается и принимается отрицательный результат. Процесс классификации в виде дерева решений приведен на рисунке 1.

Рис. 1. Дерево решений формирования электронного дела

где — функция распределения документов

Как показано выше, для выбора определенного дела необходимо пройти по дереву решений, миновав другие узлы. Следовательно, при переборе узлов необходимо получить отрицательный результат (значение «ложь») предикатов предыдущих итераций. Тогда правило построения предиката определения функции распределения F(d):

Представим алгоритм классификации в виде блок-схемы в соответствии с теорией алгоритмов (рисунок 2).

Функция распознавания позволяет выполнять классификацию в одномерном массиве вместо двумерного [4]. Это позволяет ускорить обработку: двумерный — O(mk2), одномерный — O(mk). Вычисление пары классификаций для одного объекта с использованием конечного предиката производится единовременно, т. е. нет необходимости проходить каждый узел в отдельности, предикат позволяет проверить ветку за одну операцию (рисунок 2). В качестве дела выбирается первое подходящее в процессе перебора всех веток. Конечные предикаты обладают высокой абстракцией, это позволяет использовать близкие правила как для классификации, так и для распределения дел по признакам. Классификатор на основе предикатов позволяет легко расширять методику отбора. Такой подход позволит адекватно описывать объекты, их свойства и отношения между ними.

Рис. 2. Алгоритм отнесения документа к делу при помощи предикатов

При рассмотрении описываемой методики классификации важно отметить, как ее сложность зависит от объёма входных данных. В общем случае сложность алгоритма можно оценить по порядку величины [5]. Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N время выполнения алгоритма возрастает с той же скоростью, что и функция f(N). Если общее количество итераций внутреннего цикла равно N*N, это определяет сложность алгоритма O(N^2).

По представленному на рисунке 2 алгоритму можно определить уравнение сложности для него [6]. Использование предикатов при классификации позволяет остановить алгоритм при первом совпадении. Таким образом, ожидаемое количество итераций будет равно mk/2. При каждой итерации, проверяется соответствие документа одним предикатом, который сравнивает критерии и выдает однозначное решение (3 операции).

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

Таблица 1

Оценка времени выполнения алгоритмов для mk дел

Алгоритм

m*k = 10

m*k = 50

m*k = 100

m*k = 1000

m*k = 10000

Байес

O(mk2)

0,6 мс

15 мс

60 мс

6 с

10 мин

Деревья решений

O(2mk)

1 мс

18,7 м

40 лет

---

---

Предикаты

O(mk)

0,03 мс

0,15 мс

0,3 мс

3 мс

30 мс

Таким образом, алгоритм классификации, построенный на основе предикатов, оказался на порядки быстрей других рассматриваемых алгоритмов (O(N) < O(N2) < O(2N)).

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

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

Литература:

  1. Бондаренко М. Ф., Кругликова Н. П. Об алгебре одноместных предикатов. // Бионика интеллекта информация, язык, интеллект. Научно-технический журнал № 2 (73) 2010г. — С. 62–68.
  2. Бондаренко М. Ф., Шабанов-Кушнаренко Ю. П. Нормальные формы формул алгебры конечных предикатов. // Бионика интеллекта информация, язык, интеллект. Научно-технический журнал № 3 (77) 2011г. — С. 62–68.
  3. Беклемишев Л. Д.. Введение в математическую логику. // Мех-мат МГУ, 1-й курс, весна 2008г. Конспект лекций 5 и 6 / Л. Д. Беклемишев.
  4. Шитиков В. К., Мастицкий С. Э. Классификация, регрессия и другие алгоритмы Data Mining с использованием R / В. К. Шитиков, С. Э. Мастицкий -: Тольятти, Лондон — 2017г.
  5. Галиев Ш. И. Математическая логика и теория алгоритмов. / Ш. И. Галиев — Казань: Издательство КГТУ им. А. Н. Туполева. 2002. -270 с.
  6. Алексеева В. А. Использование методов машинного обучения в задачах бинарной классификации. // Автоматизация процессов управления № 3 (41) 2015г. — С. 58–63.
Основные термины (генерируются автоматически): предикат, дело, электронный документооборот, документ, дерево решений, алгоритм классификации, алгоритм, отрицательный результат, универсальное средство, автоматическая классификация.


Похожие статьи

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

С точки зрения классификации бустинг деревьев решений считается одним из наиболее эффективных методов. Данный алгоритм строит модель в виде суммы деревьев: (1). где h0 — начальное приближение, v — параметр...

Метод автоматической классификации документов в задаче...

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

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

Сравнительный анализ алгоритмов нейронной сети и деревьев...

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

Анализ эффективности применения методов классификации

Основные термины (генерируются автоматически): SVM, объем данных, наивный байесовский классификатор, простота реализации, метод дерева принятия решений, задача классификации, дерево принятия решений, данные, алгоритм, случайный лес.

Сравнение методов оценки тональности текста | Статья в журнале...

Существует множество методов классификации текстовых документов.

Оценка результатов классификации. Как оценивать качество алгоритма?

Анализ тональности текста — Википедия: [Электронный ресурс].

Алгоритмы распознавания объектов | Статья в сборнике...

Существует такой подход к решению задач распознавания (классификации) как усиление простых классификаторов.

Работа алгоритма Viola Jones [Электронный ресурс].

Основные термины (генерируются автоматически): область, алгоритм, изображение, классификатор...

Метод определения весов параметров из набора входящих...

Ключевые слова: классификация, деревья принятия решений, отсутствующие значения, веса параметров, C4.5.

Одним из главных направлений их использования является решение задач классификации [1]. C4.5 —алгоритм построениядеревьев решений, разработанный...

Семантический поиск документов, классифицированных...

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

Необходимо построить алгоритм, который сопоставит каждому документу ровно один лист, принадлежащий дереву [2].

Похожие статьи

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

С точки зрения классификации бустинг деревьев решений считается одним из наиболее эффективных методов. Данный алгоритм строит модель в виде суммы деревьев: (1). где h0 — начальное приближение, v — параметр...

Метод автоматической классификации документов в задаче...

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

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

Сравнительный анализ алгоритмов нейронной сети и деревьев...

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

Анализ эффективности применения методов классификации

Основные термины (генерируются автоматически): SVM, объем данных, наивный байесовский классификатор, простота реализации, метод дерева принятия решений, задача классификации, дерево принятия решений, данные, алгоритм, случайный лес.

Сравнение методов оценки тональности текста | Статья в журнале...

Существует множество методов классификации текстовых документов.

Оценка результатов классификации. Как оценивать качество алгоритма?

Анализ тональности текста — Википедия: [Электронный ресурс].

Алгоритмы распознавания объектов | Статья в сборнике...

Существует такой подход к решению задач распознавания (классификации) как усиление простых классификаторов.

Работа алгоритма Viola Jones [Электронный ресурс].

Основные термины (генерируются автоматически): область, алгоритм, изображение, классификатор...

Метод определения весов параметров из набора входящих...

Ключевые слова: классификация, деревья принятия решений, отсутствующие значения, веса параметров, C4.5.

Одним из главных направлений их использования является решение задач классификации [1]. C4.5 —алгоритм построениядеревьев решений, разработанный...

Семантический поиск документов, классифицированных...

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

Необходимо построить алгоритм, который сопоставит каждому документу ровно один лист, принадлежащий дереву [2].

Задать вопрос