Авторы: Кроль Татьяна Яковлевна, Харин Максим Алексеевич

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

Опубликовано в Молодой учёный №6 (29) июнь 2011 г.

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

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

Кроль Т. Я., Харин М. А. Методы решения задачи кластеризации и прогнозирования в электронном архиве // Молодой ученый. — 2011. — №6. Т.1. — С. 135-137. — URL https://moluch.ru/archive/29/3349/ (дата обращения: 18.12.2017).

Электронные архивы позволяют предприятиям в структурированном виде накапливать информацию, содержащуюся в документах. Занесение документов осуществляется по схеме, описанной в статье [1], при этом документ проходит через этапы сканирования, распознавания, верификации и собственно занесения в архив. В статье [2] описаны методы решения задачи поиска ассоциаций в электронном архиве. Это помогает ускорить процесс верификации документов, соответственно, уменьшить время занесения в архив. Накопленные же документы можно использовать не только в повседневной работе организации, но и для выявления некоторых тенденций и составления прогнозов развития. В данной статье рассмотрим методы решения задачи прогнозирования, используя некоторую кластеризацию архива.
Итак, в архиве накоплено некоторое количество документов, атрибуты которых принимают значения разных типов: число, дата/время, строка и др. Необходимо предсказать значения атрибутов для будущих документов. Например, имеются данные о суммах в договорах, необходимо выявить тенденцию и предположить значения сумм последующих договоров. Для этого можно использовать методы аппроксимации и экстраполяции. Но сначала необходимо разбить исходное множество документов на группы, то есть произвести кластеризацию. Рассмотрим этот момент подробнее.
Во-первых, первоначальное разбиение на группы уже выполнено в архиве делением документов на типы. Однако к одному типу может относиться довольно большое количество документов, поэтому необходим дополнительный признак. В статье [2] описаны методы создания справочника значений – таблицы наиболее часто встречающихся пар значений атрибутов. Строго говоря, справочник – это некоторый набор экземпляров правил вида «Если , то с вероятностью ». Здесь и - некоторые атрибуты, и - значения атрибутов, - численное значение вероятности. Для получения справочника можно использовать следующие методы:
  • метод полного вероятностного справочника, описывающий вероятности всех встречающихся пар значений;
  • метод складывающихся столбцов, являющийся более быстрым, но менее точным за счет использования некоторых средних значений;
  • метод ограничивающей выборки, комбинирующий два предыдущих.
Рассмотрим пример. Пусть в некотором документе имеются поля «Организация» и «Адрес организации». Часто бывает, что одна и та же организация в разных документах обозначается по-разному, например, в результате сокращений и аббревиатур (ОАО «ЭЦМ» и ОАО «Электроцентромонтаж»). В таком случае, если адрес записан одинаково (не считая разных регистров букв и знаков препинания), он может однозначно идентифицировать организацию.
Итак, выберем некий атрибут как основной и применим один из предложенных методов для создания справочника. На его основе начнем создавать кластер. Выберем некоторое значение атрибута , еще не использованное в каких-либо кластерах, и включим его в множество (англ. consequence - следствие). Следующее действие назовем шагом кластеризации:
Для всех элементов множества найдем в наборе все экземпляры правил, в которых значение атрибута равно , то есть правила вида «Если , то с вероятностью », где – некоторый номер значения. Все значения включим в множество (англ. premise - посылка). Далее для всех элементов из множества найдем все экземпляры правил, в которых значение атрибута равно , то есть правила вида «Если , то с вероятностью ». Все значения включим в множество . Это и есть шаг кластеризации. Будем проводить его до тех пор, пока на каком-либо шаге множество не останется неизменным, то есть новых элементов добавлено не было. Соответственно в кластер объединяются те документы, для которых выполняется равенство , где - элемент множества . При составлении следующего кластера элементы множества в рассмотрении не участвуют. Кластеры составляются до тех пор, пока есть значения атрибута, не вошедшие ни в один кластер.
Возвращаясь к примеру, поясним. Справочник представляет собой некоторую таблицу пар «Наименование организации – Адрес организации». Начинаем работу с некоторого конкретного адреса. Найдем все наименования организации, соответствующие этому адресу. Затем всем этим наименованиям найдем соответствующие адреса, которые могут не совпадать по написанию с ранее учтенными. Если был найден новый вариант адреса, то повторим процедуру. В результате в кластер отбираются все варианты наименований и адресов одной и той же организации.
Таким образом, исходное множество документов типа оказывается разбитым на подмножества согласно значениям некоторого атрибута . Далее расположим документы по возрастанию даты, минимальную дату примем за начало отсчета. Затем на оси времени, обозначим ее , будем откладывать некоторый период, принимаемый за единицу. В качестве такого периода можно взять, например, 1 день, 1 месяц, 1 год или другое значение. Далее выберем числовой атрибут, значения которого необходимо предсказать. Таким образом, каждое подобное подмножество представляет некоторую функцию, которую следует аппроксимировать. Формально каждую такую функцию можно записать в виде таблицы значений . Необходимо найти значение функции при некотором . Для этого можно использовать методы экстраполяции, например, следующие:
  1. Формула Ньютона для экстраполяции вперед [3]. Эта формула используется, когда значения функции известны в узлах сетки с постоянным шагом. Этот шаг обозначим через . Тогда верна следующая формула

(1)

Здесь - конечная разность, определяемая выражением

(2)

Где - коэффициенты бинома Ньютона.
  1. Интерполяционный многочлен Лагранжа [4]. При применении этого метода узлы интерполяционной сетки не обязательно должны быть равноотстоящими, а могут быть произвольно заданными. Многочлен Лагранжа – это многочлен степени не выше , принимающий в заданных узлах значения, совпадающие со значениями функции . Такой многочлен определяется следующей формулой

(3)

Этот многочлен является единственным, и его затем можно использовать для вычисления значений в других точках.
  1. Методы рациональной интерполяции [5]. Интерполяция рациональными функциями заключается в представлении искомой функции в виде отношения двух многочленов:

(4)

Достоинствами такой интерполяции являются высокая точность и неподверженность проблемам, свойственным полиномиальной интерполяции. Однако одним из недостатков является то, что не для каждого набора точек можно построить рациональную функцию. Одним из алгоритмов для построения функции является алгоритм Флоатера-Хорманна. Итак, пусть даны точки и даны значения функции в них: . Пусть - порядок интерполяционной схемы Флоатера-Хорманна и пусть обозначает полином, интерполирующий функцию в точках . Тогда рациональный интерполянт Флоатера-Хорманна можно найти, используя формулы:

(5)

(6)

  1. Интерполяция сплайнами [6]. Одним из недостатков интерполирования многочленом Лагранжа или Ньютона на некотором отрезке с использованием большого количества узлов интерполяции является плохое приближение, вызванное сильным накоплением погрешностей в процессе вычислений. Кроме того, не всегда увеличение числа приводит к повышению точности вследствие расходимости процесса. Чтобы избежать больших погрешностей весь отрезок следует разбить на частичные отрезки и на каждом отрезке заменить функцию многочленом невысокой степени. Одним из способов интерполирования на всем отрезке является интерполирование с помощью сплайн-функций. Рассмотрим подробнее построение кубического сплайна.
Итак, на отрезке задана непрерывная функция , некоторые точки сетки и значения функции . Интерполяционный кубический сплайн, соответствующий данной функции и данным узлам , - это функция , удовлетворяющая следующим условиям:
  • на каждом сегменте , функция является многочленом третьей степени;
  • функция и ее первая и вторая производные непрерывны на ;
Такой сплайн существует и является единственным [6]. Рассмотрим способ построения кубического сплайна. На каждом из отрезков будем искать функцию в виде многочлена третьей степени:

(7)

Здесь - это коэффициенты, которые необходимо найти. Отметим, что . Из условий интерполирования получаем:

(8)

Далее обозначим . Тогда коэффициенты можно найти, решив систему уравнений:

(9)

Для нахождения коэффициентов и существуют следующие явные формулы:

(10)

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


Литература:

Кроль Т.Я. Схема наполнения электронного архива документами / Т.Я.Кроль, М.А.Харин, П.В.Евдокимов // Материалы первой международной конференции «Автоматизация управления и интеллектуальные системы и среды». Терскол, 20-27 дек. 2010. Т. IV. С. 53-56.
Кроль Т.Я. Методы создания справочника на основе электронного архива / Т.Я. Кроль, М.А.Харин, П.В.Евдокимов // Известия КБНЦ РАН. – 2011. – №1.
Сальвадори М.Дж. Численные методы в технике / М.Дж.Сальвадори. – М.: Издательство иностранной литературы, 1955. – 251с.
Ващенко Г.В. Вычислительная математика: основы алгебраической и тригонометрической интерполяции / Г.В. Ващенко.- Красноярск: СибГТУ, 2008. – 64с.
Бочканов С. Рациональная интерполяция [Электронный ресурс] / С. Бочканов, В.Быстрицкий. – Режим доступа: http://alglib.sources.ru/interpolation/rational.php, свободный.
Самарский А.А. Численные методы: Учеб. пособие для вузов / А.А.Самарский, А.В.Гулин. – М.: Наука. Гл. ред. физ-мат. лит., 1989. – 432с.
Основные термины (генерируются автоматически): решения задачи, значения функции, значение атрибута, значение атрибута равно, методы решения задачи, значения атрибутов, исходное множество документов, решения задачи прогнозирования, создания справочника, вида «Если, правила вида «Если, электронного архива, значения атрибута, значения функции известны, значения разных типов, значения сумм последующих, кубический сплайн, пар значений, количество документов, Численные методы.

Обсуждение

Социальные комментарии Cackle
Задать вопрос