Локально-аппроксимационные алгоритмы классификации траекторий

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ЛОКАЛЬНО-АППРОКСИМАЦИОННЫЕ АЛГОРИТМЫ КЛАССИФИКАЦИИ ТРАЕКТОРИЙ

Гимаров В.А., Гимаров В.В., Дли М.И.

Аннотация

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

Ключевые слова: динамические ряды, локальная аппроксимация, нечеткая логика, алгоритм нечетких c-средних, кластеризация, центры кластеров.

Annotation

LOCAL APPROXIMATION CLASSIFICATION ALGORITHM PATHS

Gimarov V. A., Gimarov V. V., Dli M. I.

Currently, the analysis of dynamic rows is an urgent problem for many areas, such as medical research, analysis of socio- economic processes, diagnostics of complex technical systems, and others. Algorithms for analyzing such data are varied and are built on structural and pointwise comparison trajectories reflecting the dynamic rows. The article describes the author's proposals on the use of local approximation procedures for solving the problem of trajectory classification based on the criteria of point similarity. The essence of the method is presented in the rows representation in the form of matrix data sets and application of the algorithm of fuzzy c- means for their further clustering.

Key words: time series, local approximation, fuzzy logic algorithm fuzzy c-means, clustering, cluster centers.

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

Основы классификационного анализа динамических данных рассмотрены в работах отечественных и зарубежных ученых [1,2].

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

В работе [1] классификация траекторий основана на применении аппарата нечеткой логики и предполагает выделение двух типов схожести траекторий:

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

точечное сходство: чем меньше расстояние между точками двух траекторий, тем большее сходство наблюдается между ними.

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

Как представляется, для решения задачи классификации траекторий с использованием критериев точечного сходства, может быть применен алгоритм c-means и методы локальной аппроксимации, основные положения которых изложены в работах [5,6]. Применение процедур локальной аппроксимации для решения задачи классификации траекторий включает следующие этапы [4]:

1) Построение локально-аппроксимационных моделей, описывающих траектории изменения состояний системы, которые представляют собой наборы строковых данных вида .

Для получения таких данных применяется процедура [3]:

1. Проведение эксперимента с фиксацией значений и создание исходной матрицы U с количеством строк, большим М.

2. Ввод нового значения . Расчет прогнозируемой величины по формуле:

задача алгоритм матричный аппроксимация

где F - матрица размера , строками которой являются

Анализ истинности неравенства:

где d - некоторая заданная константа, предопределяющая показатель точности модели.

Если неравенство верно, в матрицу U дополнительно включается строка . В противном случае матрица U не изменяется.

4. Анализ выполнения условий прерывания работы алгоритма (общее число значений , используемых для формирования матрицы U может быть как фиксированным или переменным); например, условием останова процесса обучения может быть невыполнение неравенства, приведенного на этапе 3 раз подряд. При его неисполнении осуществляется переход к этапу 2, в противном случае - переход к пункту 4.

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

В результате, любая из анализируемых траекторий изменения состояний системы представляется в виде набора данных (матрицы) U. Для проведения кластеризации траекторий на определенное (заданное заранее) количество подмножеств (кластеров), в каждом из которых анализируемые объекты схожи между собой, целесообразно применять метод нечетких c-средних.

2) На каждом этапе стандартного алгоритма нечетких С-средних в соответствии со следующей формулой рассчитывается значение функции принадлежности объекта i к классу j:

где Х_i i-ый объект (траектория), V_j и V_k центры кластеров j и k, с число кластеров, m степень размытости кластеров.

Выражение d(X,V) используется для представления меры близости между двумя векторами. Для определения данной меры используется предложенная автором методика.

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

Проводится поиск строк в наборах данных U, максимально близких друг к другу по значениям. Так, в локальной модели поиск близких строк будет выполняться в соответствии с выражением [6]:

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

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

, p - число кластеров

Перерасчет значений функций принадлежности:

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

Литература

1. Angstenberger L. Dynamic Fuzzy Pattern Recognition with Applications to Finance and Engineering. Boston: Kluwer Academic Publishers, 2001.

2. Бауман Е.В., Дорофеюк А.А. Классификационный анализ данных // Труды Международной конференции по проблемам управления. - Том 1. - М.: СИНТЕГ, 1999. - С. 62-77.

3. Гимаров В.А., Гимаров В.В., Дли М.И., Иванова И.В. Модели поведения агентов для мультиагентной системы управления телекоммуникационным предприятием // Научное обозрение. 2013. № 12. С. 223-226.

4. Гимаров В.А., Гимаров В.В., Иванова И.В. Построение динамической мультиагентной модели с использованием классификации трендов // Программные продукты и системы. 2011. № 3. С. 40.

5. Дли М.И., Круглов В.В., Осокин М.В. Локально-аппроксимационные модели социально-экономических систем и процессов. - М.: Наука. Физматлит, 2000.

6. Дли М.И. Обобщенная локально-аппроксимационная модель динамического объекта // Программные продукты и системы. - 1999. - №3. - С. 15-21.

7. Стоянова О.В., Иванова И.В., Багузова О.В. Интеллектуальная поддержка принятия решений по управлению сложными проектами // Вестник Российской академии естественных наук (Санкт-Петербург). 2012. № 1. С. 88-90.

Размещено на Allbest.ru