На правах рекламы:
ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Авторитетность издания

ВАК - К1
RSCI, ядро РИНЦ

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

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

4
Ожидается:
09 Сентября 2024

Вычислительные процедуры обработки неточной временной информации

Imprecise temporal information processing
Дата подачи статьи: 01.07.2016
УДК: 519.68
Статья опубликована в выпуске журнала № 3 за 2016 год. [ на стр. 29-35 ]
Аннотация:В статье представлены результаты обширного исследования, обусловленного практической потребностью повышения эффективности методов представления, алгоритмов извлечения, обработки нечетких темпоральных данных. Акцент делается на онтологических моделях процессов прогнозирования и интерпретации при взаимодействии с неточной временной информацией. Предлагаются методология хранения данных, а также модели и унифицированные процедуры извлечения нечеткой информации. Непосредственно затрагивается вопрос о прагматике алгоритмов представления темпоральных данных через новый инструмент так называемой возможностной темпоральной информации в аналитических системах, где параметры неточности и оперативности являются критическими условиями в принятии бизнес-решений. Предлагаются решения проблем хранения и извлечения неточной временной информации за счет построения модели обработки нечетко-темпоральных отношений между временными точками и/или интервалами. Представлена концепция анализа и представления нечеткой темпоральности в рамках развития модели темпоральных реляционных БД с учетом критериев неточности, неоднозначности, неопределенности. Разработана алгебра возможностных отношений точек и/или интервалов, в ее рамках определены понятия возможностной временной точки и возможностного интервала, введены соответствующие значения возможностных временных точек и интервалов. Представлен фрагмент формализованного алгоритма реализации алгебры на примере расширения одного из отношений. Предлагается подход к разработке и моделированию нечеткого темпорального домена и отношений между возможностными интервалами и моментами времени. Дано описание реализованной библиотеки алгоритмов обработки отношений возможностных временных точек и/или интервалов, а также соответствующих процедур и функций на платформе стандарта SQL. Представлены результаты внедрения библиотеки алгоритмов при реализации коммерческого проекта аналитической системы для телекоммуникационной компании, а также определены направления дальнейшего развития прикладного инструментария, основанного на теории нечетко-темпоральной модели.
Abstract:The article presents the results of extensive research resulting from a practical need in improving the effectiveness of representation methods, extraction algorithms, processing fuzzy temporal data. The authors focus on ontological models of prediction and interpretation during interaction with imprecise temporal information. They propose a data storage methodology as well as models and unified procedures for extracting fuzzy information. The pragmatic of temporal data representation algorithms is considered using a new so-called possibilistic temporal information in analytical systems, where the parameters of inaccuracy and efficiency are crucial for making business decisions. The article proposes solutions for the problems of imprecise temporal information storage and retrieval by constructing a model of processing fuzzy temporal relations between time points and/or intervals. The concept of fuzzy temporal information analysis and presentation is described within development of temporal relational databases framework taking into account the criteria of inaccuracies, ambiguity and uncertainty. The authors developed he algebra of possibilistic relations between points and/or intervals. It defines the concept of possibilistic time point, possibilistic interval and corresponding values of possibilistic time points and intervals. The example of extension of one of the relations describes the fragment of a formalized algorithm of algebra implementation. The authors propose an approach to design and modeling a fuzzy temporal domain as well as the relations between possibilistic intervals and time points. The article describes an implemented library of algorithms for processing relations between possibilistic time points and/or intervals, as well as corresponding procedures and functions on SQL platform. At the end, the article describes the results of integration of the library of algorithms in a commercial project of analysis system for a telecommunication company. It also describes areas for further development of application tools based on the theory of a fuzzy-temporal model.
Авторы: Фомин В.В. (v_v_fomin@mail.ru) - Российский государственный педагогический университет им. А.И. Герцена (профессор), Санкт-Петербург, Россия, доктор технических наук, Мальцев С.В. (maltsevsergey@live.com) - Российский государственный педагогический университет им. А.И. Герцена (аспирант), Санкт-Петербург, Россия
Ключевые слова: темпоральные бд, временная неопределенность, программы и алгоритмы
Keywords: temporal databases, temporal uncertainty, programs and algorithms
Количество просмотров: 8904
Версия для печати
Выпуск в формате PDF (6.81Мб)
Скачать обложку в формате PDF (0.36Мб)

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

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

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

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

Теоретические достижения и значимость исследований в области обработки нечетко-темпоральных данных отражены в научно-технических публикациях [2–4]. Прикладные системы обработки нечетко-темпоральных данных востребованы в различных прикладных областях [5–8] и являются одной из индустриальных задач информационных технологий.

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

1.    Системы планирования и прогнозирования. Фиксирование нечеткой временной информации в календаре или в планировщике задач, в частности, фиксация/планирование/смещение задач с учетом погрешности во времени.

2.    Фиксирование исторических неточных фактов или данных.

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

Потребность в использовании темпоральной модели хранения данных актуализировалась с появлением темпоральной поддержки [9] в стандарте SQL:2011. С появлением стандарта разработчики аналитических систем стали активно добавлять в свои продукты темпоральную поддержку, реализация которой способствовала активному внедрению на предприятиях для решения задач, связанных с учетом времени. Темпоральная поддержка в стандарте SQL:2011 ограничивается в решении вопросов обработки нечетких темпоральных данных. Необходимость использования нечеткой логики в обработке темпоральной информации вызвана возможным наличием неточности в исходных данных, где периоды начала/завершения действия интервалов или событий могут быть неточно определены или не определены вообще. Расширенными возможностями, прорабатываемыми в новой модели, являются следующие:

-     рассмотрение и проработка не только исторических темпоральных фактов, но и фактов, которые могут наступить в предположительное время в будущем, от времени выполнения которых могут зависеть другие задачи;

-     изучение не только неточных интервалов, но и временных точек, принимающих множество значений;

-     рассмотрение погрешности во временных точках, а также в диапазонах значений интервалов;

-     изучение и проработка нетемпоральных периодов (например integer и string);

-     изучение применения неточности в нескольких временных измерениях;

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

Построение модели обработки неточной временной информации

В темпоральной модели данных выделяются следующие типы нечеткости [4].

Неопределенность. Какая-либо часть темпоральной информации неизвестна или определена неточно. Например, дата рождения Сократа – «около 469 год д.н.э.».

Субъективность, двусмысленность. Темпоральные события или периоды могут быть субъективно или неоднозначно определены. Например, «эпоха нового времени» или в сфере грузоперевозки «даты начала или завершения транспортировки груза».

Неясность, расплывчатость. События могут быть определены с различной гранулярностью или нечеткостью. Например, «доставка груза в течение дня».

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

Возможностная временная точка (pt) – предполагаемая временная отметка (или момент времени) на временной оси, значение которой неизвестно либо неточно определено.

Введем следующие значения возможностных временных точек.

1.    Значение определено с возможным отклонением. Предполагаемое значение временной точки принимает степень возможности 1, значения возможностного отклонения от времени наступления находятся в диапазоне [0, 1]. Вид: [pt, pt – α, pt + β], где pt ∈ T – возможностная временная точка, предполагаемый момент времени на временном отрезке T; α и β – значения возможностного отклонения от наступления (рис. 1).

Значения отклонения должны быть заданы с соответствующей гранулярностью α и β, то есть в единицах времени из существующих форматов: ss, mi, hh24, dd, mm, yyyy.

2.    Значение в диапазоне не определено. Значения в диапазоне имеют одинаковую степень возможности наступления PExtent.

Вид: [{ptx, pty}, PExtent], где {ptx, pty} ∈ T – диапазон значений возможностных временных точек предполагаемого момента времени на временном отрезке T; ptx и pty могут принимать пустое значение. В таком случае (рис. 2) предполагается диапа- зон значений в виде: [{ptx, ∞}, PExtent] ∨ [{∞, pty}, PExtent].

3.    Значение не определено. Любые значения имеют одинаковую степень возможности наступления = 0. Вид: [undefined, 0].

Возможностные отношения временных точек и интервалов

Одной из наиболее распространенных моделей учета временной неопределенности является темпоральная алгебра Аллена. Дж.Ф. Аллен определил набор из 13 качественных отношений, которые могут существовать между двумя временными интервалами [10]. Алгебра Аллена ограничивается использованием отношений между периодами (отрезками, интервалами) времени и характеризуется мерой длительности временных отрезков.

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

Для построения модели, рассматривающей возможностные отношения между точками и/или интервалами, темпоральная алгебра Аллена была расширена путем декомпозиции интервальных отношений до отношений между двумя точками, а также точками и интервалами. Введенные отноше- ния отражены в таблице 1.

На основании темпоральных отношений между точками и/или интервалами, а также введенных значений возможностных временных точек была разработана алгебра возможностных отношений точек и/или интервалов.

Рассмотрим фрагмент алгебры на примере расширения одного отношения «Перед» (Before) (табл. 1) до трех типов отношений (табл. 2).

Для учета эффекта неопределенности применяется функция принадлежности теории нечетких множеств, которая позволяет определить степень принадлежности элементов фундаментального множества пространства рассуждения нечеткому множеству. За основу меры степени принадлежности взяты введенные Л. Заде [1] вещественные числа в интервале от 0 до 1: 0 означает, что элемент не включен в нечеткое множество, 1 – описывает полностью включенный элемент. Значения между 0 и 1 характеризуют нечетко включенные элементы.

Данное отношение предназначено для определения признака наступления возможностной временной точки a до b и принимает следующий вид: PosBefore (a, b[, PExtent_IN]), где a и b – обязательные сравниваемые значения временных точек; PExtent_IN∈ [0, 1] (опционально) – степень, требуемая для выполнения условия.

Отношение возвращает (PExtent_OUT[, boo- lean]), где PExtent_OUT∈ [0, 1] – результирующая возможностная степень выполнения; boolean – признак выполнения: true, если PExtent_OUT ≥ ≥ PExtent_IN, или false, если PExtent_OUT < PExtent_IN.

Варианты использования отношения «Перед» для двух введенных значений возможностных временных точек.

1. Точное значение точки a.

1.1. Точное значение точки b:

1.2. Значение точки b определено с возможным отклонением:

Возможностная точка b с периодами возможного отклонения наступления b_α и b_β (рис. 3).

1.3. Значение точки b в диапазоне не определено.

Возможностная точка b с возможностным диапазоном времени наступления b_α и b_β и возможностной степенью b_PExtent_IN (рис. 4):

В случаях, когда b_α и/или b_β принимают пустое значение, для проведения корректных расчетов подставляются даты начала или завершения значениями по умолчанию (d_sd и d_ed), которые должны быть определены в соответствии с предметной областью.

При b_α = null и b_β<>null:

При b_α <>null и b_β = null:

При b_α = null и b_β = null:

1.4. Значение точки b не определено.

Возможностная точка b с неизвестным временем наступления.

Отношение возвращает исходное значение PExtent_IN, которое принимает значение 0.

2. Точка a – значение определено с возможным отклонением.

2.1. Точное значение точки b:

Возможностная точка a с периодами возможного отклонения наступления α и β (рис. 5).

2.2. Значение точки b определено с возможным отклонением.

Возможностная точка a с периодами возможного отклонения наступления a_α и a_β. Возможностная точка b с периодами возможного отклонения наступления b_α и b_β (рис. 6).

Для каждого a_x∈A, где A = {a, a_α, a_β}, выполняется следующий расчет степени pos_extent:

Степень возможности наступления а до b высчитывается при помощи среднего значения полученных pos_extent: PosBefore =AVG (pos_extent (a), pos_extent (a_α), pos_extent (a_β)).

2.3. Значение точки b в диапазоне не определено.

Возможностная точка a с периодами возможного отклонения наступления a_α и a_β. Возможностная точка b с возможностным диапазоном времени наступления b_α и b_β и возможностной степенью b_PExtent_IN (рис. 7).

Для каждого a_x∈A, где A = {a, a_α, a_β}, выполняется следующий расчет степени pos_extent:

Степень возможности наступления а до b высчитывается при помощи среднего значения полученных a_extent: PosBefore =AVG (pos_extent (a), pos_extent (a_α), pos_extent (a_β)).

2.4. Значение точки b не определено.

Возможностная точка b с неизвестным временем наступления.

Отношение возвращает исходное значение PExtent_IN, которое принимает значение 0.

3. Значение точки a в диапазоне не определено.

3.1. Точное значение точки b.

Возможностная точка a с возможностным диапазоном времени наступления a_α и a_β и возможностной степенью a_PExtent_IN (рис. 8):

3.2. Значение точки b определено с возможным отклонением.

Возможностная точка a с возможностным диапазоном времени наступления a_α и a_β и возможностной степенью a_PExtent_IN (рис. 9).

Возможностная точка b с периодами возможного отклонения наступления b_α и b_β.

Для каждого a_x∈A, где A = {a_α, a_β}, выполняется следующий расчет степени pos_extent:

Степень возможности наступления а до b высчитывается при помощи среднего значения полученных pos_extent:

PosBefore= AVG(pos_extent(a_α), pos_extent(a_β)).

3.3. Значение точки b в диапазоне не определено.

Возможностная точка a с возможностным диапазоном времени наступления a_α и a_β и возможностной степенью a_PExtent_IN. Возможностная точка b с возможностным диапазоном времени наступления b_α и b_β и возможностной степенью b_PExtent_IN (рис. 10).

Для a_x∈A, где A = {a_α, a_β}, выполняется следующий расчет степени pos_extent:

Степень возможности наступления а до b высчитывается при помощи среднего значения полученных pos_extent:

PosBefore =AVG (pos_extent (a_α), pos_extent (a_β)).

3.4. Значение точки b не определено.

Возможностная точка b с неизвестным временем наступления.

Отношение возвращает исходное значение PExtent_IN, которое принимает значение 0.

По аналогии с представленным отношением «Перед» формализованы все заданные отношения интервалов Аллена [10] и расширенные отношения в таблице 1.

Библиотека алгоритмов

Алгебра отношений возможностных временных точек и/или интервалов была реализована в виде библиотеки алгоритмов на основе средств языка pl/sql. Разработанная библиотека алгоритмов дополняет и расширяет возможности языка SQL для обработки информации на базе реляционных моделей данных в развитие теории темпоральных моделей данных. В перспективе разработка отдельного инструментария систем управления БД для работы с темпоральными БД.

Апробация библиотеки алгоритмов возможностных временных точек и/или интервалов проводилась в телекоммуникационной компании. Библиотека была интегрирована в модуль анализа работы биллинговых систем оператора связи и их взаимодействия со смежными системами. Модуль позволяет выявлять процессы, в которых присутствуют неопределенность и неточность в информации, связанной с временными показателями.

Разработанная библиотека алгоритмов возможностных временных точек и/или интервалов была применена в системе мониторинга работы биллинговой системы при решении задачи управления программами лояльности, в том числе:

-     прогнозирование и фиксирование предполагаемых дат оплаты счетов абонентами на основании показателей прошлых периодов;

-     анализ временных периодов внесения платежей абонентами и их сопоставление с возможностными датами оплаты непогашенных счетов;

-     прогнозирование предполагаемой даты завершения биллингового расчетного периода – сбора счетов и платежей абонентов за предыдущий месяц;

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

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

В дальнейшем исследовании планируется продолжить развитие нечетко-темпоральной модели:

-     расширить класс возможных отношений между возможностными временными точками и интервалами;

-     интегрировать в модель возможностные нетемпоральные периоды и применение нескольких возможностных временных осей в одном отношении;

-     реализовать процедурную модель для языков определения и манипулирования данными.

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

Литература

1.     Заде Л. Понятие лингвистической переменной и его применение к принятию приближенных решений. М.: Мир, 1976. 162 с.

2.     Burney A., Mahmood N., Jilani T., Saleem H. Conceptual fuzzy temporal relational model (ftrm) for patient data. WSEAS Transactions on Information Science and Applications, 2010, vol. 7, no. 5, рp. 725–734.

3.     Garrido C., Marin N., Pons O. Fuzzy intervals to represent fuzzy valid time in a temporal relational database. Int. Journ. of Uncertainty, Fuzziness and Knowlege-Based Systems, 2009, vol. 17 (suppl. 1), pp. 173–192.

4.     Nagyp´al G., Motik B. A fuzzy model for representing uncertain, subjective, and vague temporal knowledge in ontologies. On The Move to Meaningful Internet Systems 2003: CoopIS, DOA, and ODBASE, OTM Confed. Int. Conf., 2003, pp. 906–923.

5.     Pons J., Billiet C., Pons O., De Tré G. Aspects of dealing with imperfect data in temporal databases. Flexible approaches in data, information and knowledge management. Springer Int. Publ., Swetzerland, 2014, vol. 497, part. 3, pp. 189–220.

6.     Galindo J., Urrutia A., Piattini M. Fuzzy databases: modeling, design and implementation. Idea Group Publ., Hershey, USA, 2006, pp. 150–151.

7.     Pons J.E. Fuzzy temporal information treatment in relational databases. Thesis, Granada, Univ. Granada, 2014, 257 p.

8.     Snodgrass R.T. Developing time-oriented database applications in SQL. Morgan Kaufmann Publ., Inc., SF, 1999, 504 p.

9.     Kulkarni K.G., Michels J.-E. Temporal features in SQL: 2011. ACM SIGMOD Record, 2012, vol. 41, no. 3, pp. 34–43.

10.  Allen J.F. Maintaining Knowledge about Temporal Intervals. Commun. ACM, 1983, vol. 26, no. 11, pp. 832–843.


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=4174
Версия для печати
Выпуск в формате PDF (6.81Мб)
Скачать обложку в формате PDF (0.36Мб)
Статья опубликована в выпуске журнала № 3 за 2016 год. [ на стр. 29-35 ]

Возможно, Вас заинтересуют следующие статьи схожих тематик: