автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Классификация и оценивание параметров временных рядов с многократными "разладками"

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

МЕЛЬНИКОВА ЕЛЕНА НИКОЛАЕВНА

КЛАССИФИКАЦИЯ И ОЦЕНИВАНИЕ ПАРАМЕТРОВ ВРЕМЕННЫХ РЯДОВ С МНОГОКРАТНЫМИ "РАЗЛАДКАМИ"

Специальность 05.13.16 - применение вычислительной техники,

математического моделирования и математических ' методов в научных исследованиях

Автореферат диссертации на соискание ученой степени кандидата физико-математический наук

Минск - 1992

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

Научный руководитель:

доктор физико-математических наук, профессор Ю.С.Харин

Официальные оппоненты:

доктор физико-математических наук, профессор Г.А.Медведев

кандидат технических, наук Ю.Г.Приходько

Ведущая организация:

Институт проблем управления АН РФР

Защита диссертации состоится •".

26

июня

_1992 года в

Ю часов на заседании специализированного совета К 056.03.14 при Белгосуниверситете ( 220080, г. Минск, проспект Ф.Скорины, 4, Университетский городок )

С диссертацией мокно ознакомиться в библиотеке Белорусского государственного университета

■Автореферат разослан мая_1992 г.

Ученый секретарь ' специализированного Совета профессор

¡.М.Скрипник

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

■Актуальность темы. Решение широкого класса прикладных задач в естественнонаучных исследованиях, технике, экономике связано с анализом временных рядов, характеризующих динамику исследуемого объекта (явления). Традиционным является предположение, что статистические свойства наблюдаемого ряда не меняются на анализируемом промежутке времени. Однако,во многих приложениях это предположение нарушается¡характеристики анализируемого временного ряда претерпевают скачкообразные изменения, происходящие в неизвестные моменты времени (получившие.названия моментов "разладки"). При анализе подобных временных рядов возникает необходимость обнаружить произошедшие изменения(установить факты "разладок") и, если установлено, что "разладки" произошли, оценить моменты их наступления; опреде- ■ лить точность получаемых оценок и их вероятностные свойства. Ис- ' следования в этом направлении связаны с именами ученых: А.Н. Ширяев, Л. Телькснис, И.В.Никифоров, Н.Клигене, А.П.Трифонов, В.В.Конев, Ю.С.ХарИН, E.S.Page, D.Y.Hlnkley, U.Baaeeville И Др.

В зависимости от количества скачкообразных изменений характеристик временного ряда на интервале наблюдения различают задачи обнаружения однократной "разладки" и задачи обнаружения многократных "разладок". Основное внимание в литературе уделялось именно обнаружению однократных "разладок". Однако, на практике часто возникает необходимость исследования временных рядов с многократными "разладками". Среди таких задач большой теоретический и практический интерес представляет задача о многократных "разладках" при заданном числе ¿ > 2 моделей (классов) случайной последовательности, актуальная при построении алгоритмов контроля за состоянием систем управления, при разработке адаптивных процедур идентификации сложных нестационарных динамических систем и явлений с фиксированным, известным числом l состояний или режимов функционирования, каждый из которых описывается собственной вероятностной моделью. В каждом режиме система может находиться в течение некоторого, вообще говоря, случайного промежутка времени с переходом в моменты "разладок" в один из l-i альтернативных.режимов»

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

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

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

Цель работы - построение и исследование эффективности решающих правил (РП) классификации и оценивания параметров векторных временных рядов с многократными "разладками" при заданном числе моделей (классов) случайных наблюдений; разработка и программная реализация алгоритмов классификации на основе полученных решающих правил в условиях параметрической и непараметрической априорной неопределенности.

Поставленная цель определила следующие основные задачи:

1. Построение и описание математических моделей векторных временных рядов с многократными "разладками".

2. Исследование эффективности оптимального' РП обнаружения многократных "разладок" и классификации при известных вероятностных характеристиках временного ряда.

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

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

5. Синтез основанных на статистических оценках функционала межклассового расстояния параметрических и непараметрических РП обнаружения "разладок" и классификации; исследование их эффектив-

-2 -

ности и программная реализация.

Методы исследования, применяемые в настоящей работе, включают метода теории вероятностей и математической статистики, статистической теории распознавания образов и многомерного статистического анализа, методы оптимизации, теории матриц, а также метод статистического моделирования на ЭВМ.

Новые научные результаты.

В рамках параметрической вероятностной модели наблюдений:

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

2. Построено простое в вычислительном отношении двухэтапное РП: на первом этапе оцениваются моменты "разладок" и их число; на втором этапе осуществляется классификация с использованием модифицированной иерархической процедуры кластер-анализа со специальным функционалом близости.

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

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

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

6. На основе параметрической оценки функционала межклассового расстояния построены РП обнаружения "разладок" и классификации наблюдаемого векторного временного ряда.

В рамках непараметрической вероятностной модели наблюдений:

1. Построена непараметрическая (ядерного типа) состоятельная статистическая оценка функционала межклассового расстояния в ьа -метрике.

2. Получено асимптотическое распределение состоятельной непараметрической оценки межклассового ьг- расстояния. Построен тест

проверки статистической значимости оценок моментов "разладки".

3. Найдены асимптотические разложения для моментов первого и второго порядка непараметрической оценки межклассовго ^расстояния.

4. Построены непараметрические РП выявления "разладок", их числа и классификации векторного временного ряда, использующие непараметрическую статистическую оценку межклассового ь2-расстояния.

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

Реализация результатов. Теоретические и практические результаты использованы и внедрены при выполнении НИР "Разработка методов, алгоритмов и программного обеспечения устойчивого (робастно-го) анализа данных для автоматизации научных исследований, математического моделирования на ЭВМ сложных систем в условиях априорной неопределенности" (ном.гос.per. 01890080962) в рамках Республиканской научно-технической программы "Информатика"; при выполнении НИР "Разработка теории устойчивого математического моделирования систем, логико-комбинаторных и вероятностно-статистических методов оптимизации и распараллеливания вычислительно-информационных процессов", (ном. гос. per. 0I9I0054943) по плану фундаментальных научных исследоваий БГУ; при выполнении в БГУ хоздоговорных НИР * 38745, № 38790. На основе предложенного метода разработана на языке Паскаль для ПЭВМ стандартная программа классификации векторных временных рядов с многократными "разладками" с использованием непараметрических статистических оценок функционала межклассового расстояния. Программа включена в Фонд алгоритмов и программ Бел-госуниверситета и Республиканский информационный фонд алгоритмов и программ (РФАП) Института математики АН РБ ( per. ном. РФАП 207I8I7.00379).

Апробация работы. Основные результаты диссертации докладывались на v Всесоюзном симпозиуме "Машинные методы обнаружения закономерностей" (Минск,1985), на ш Всесоюзной конференции "Перспективные методы планирования и анализа экспериментов при исследовании случайных полей и пррцессов" (Гродно,1988), на Всесоюзной научно-технической конференции "Методы представления и обработки

случайных сигналов и полей" (Харьков,1989), на Республиканской конференции молодых ученых и специалистов "Применение информатики и вычислительной техники при решении народнохозяйственных задач" (Минск,1989), на ш Всесоюзном семинаре "Обнаружение изменения свойств случайных процессов" (Воронеж,1990), на республиканской научно-технической школе-семинаре "Анализ и синтез систем массового обслуживания и сетей ЭВМ" ' (Одесса,1990), на республиканской научной конференции "Математическое и программное обеспечение анализа данных" (Минск, 1990), на межреспубликанской научно-технической конференции творческой молодежи вузов Прибалтики, Белоруссии, Молдавии "Актуальные проблемы информатики: математическое, програмное и информационное обеспечение" (Минск, 1990), на Минском городском научном семинаре "Математическое и программное обеспечение анализа данных", в Белгосуниверситете на семинарах кафедр математического моделирования и анализа данных, теории вероятностей и математической статистики, на конференциях молодых ученых БГУ (1985-1991).

Публикации.По теме диссертации опубликовано 10 печатных работ.

Основные результаты работы, выносимые на защиту:

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

2. Субоптимальное РП обнаружения "разладок" и классификации дискретных временных рядов, описываемых полиномиальными распределениями.

3. Стохастическое разложение параметрической статистической оценки функционала межклассового расстояния в условиях регулярности; тест проверки статистической значимости оценок моментов "разладок". .

4. Параметрические РП обнаружения "разладок", их числа и классификации временных рядов на основе оценок функционалов межклассовых расстояний.

5. Непараметрическая статистическая оценка функционала межклассового расстояния в ь2- метрике; асимптотические разложения моментов первого и второго порядка оценки межклассового-. ¿2-расстояния; непараметрический тест проверки статистической значимости оценок моментов "разладки".

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

функционала межклассового ¿а- расстояния.

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

Структура и объем работы. Работа состоит из введения, трех глав, заключения, списка литературы, включающего 119 наименований. Диссертация содержит 139 страниц, включая 8 рисунков.

. КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность темы диссертации,формулируется цель работы, приводится обзор литературы, кратко излагается основное содержание диссертации.

В главе I строятся математические модели временных рядов с многократными разладками при известном числе классов и рассматриваются задачи построения и исследования эффективности оптимальных решающих правил (ОРП) при заданных вероятностных характеристиках временного ряда..

В § 1.Х определены математические модели временных рядов с многократными "разладками".В пространстве д* наблюдается случайный, векторный временной ряд х'=(х[:...: х^), элементы которого

являются наблюдениями из I г г классов П1.....п - длительность

наблюдаемого ряда. Определено некоторое семейство з>= (Р(х).х е вероятностных распределений, среди которых зафиксировано ъ ь 2 различных распределений V1(>),...,ти(•у. являющихся вероятностными моделями наблюдений из классов соответственно. Временной ряд хт порожден неизг эстной. случайной последовательностью номеров классов наблюдений т>°= ±....., состоящей из к° серий с неизвестными длинами .....т°к. :

.... = (<<>;:......кУг).

где а°к&е=<1.....и - неизвестный общий номер класса для л-й серии

в последовательности у°, ь = 1, к°. Так что временной ряд хт длительностью п также Состоит из к° независимых участков "однородности" (серий, фрагментов) неизвестной длины: хт=Сх* = ;• • • = + ■

к-1 к

__(I)

к = с.+ ^ »= = о.с = ■

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

щих распределение вероятностей Здесь е х - неизвест-

к

ный истинный номер класса, которому принадлежит х°т; т° - неизвестный момент времени, возможного перехода от класса к классу П.»

к к«-»

(в терминах теории обнаружения изменений свойств случайных процессов и динамических систем - к-й момент "разладки", если * ).

Относительно длин серий можно выделить такие ситуации: I) ...детерминированные величины со значениями из заданного множества д=(г.....т->. где т. (г ) - наибольшее (наименьшее)

Т — + т •

допустимое значение длин серий; 2) т^,... образуют последовательность <1°>. независимых в совокупности случайных величин с распределением вероятностей ■

Р <\=1)=:[ .0 >х л (Л = ТГГ). (2) .

+ хзг-с_

В модели (I) предполагалось, что начальный момент наблюдения временного ряда совпадает с началом первой серии, а конечный момент - с' концом последней серии. Однако, на практике первая и последняя серии могут наблюдаться не полностью. Тогда полагаем, что длины первой и последней серий т°, т£„ распределены по закону

г 1 5 т - V рст^ = ъ} = = | 0> в противном случае;

а распределения длин 2-й, 3-й,....(к°->)-й серий задаются (2).

Необходимо также учитывать случайный характер смены номеров классов при "разладке". При этом выделены две- ситуации.

Номера классов серий образуют не зависящую от (т^}

последовательность.(а°> независимых в совокупности случайных величин с распределением вероятностей ь

Р (&°=3>=% > О. 3 е X (к = 1, К") , У 1С. = 1 . (4)

■ Другой, более общей ситуацией является ситуация, когда после-доЁательность есть реализация однородной цепи Маркова с начальным распределением вероятностей

р = (> = %{ е х (б)

1 О к

и матрицей вероятностей одношаговых переходов р = стс. ^), где

р <■ <С» = = 1} = (6)

Число серий неизвестно: к°е лк = ск_,..'. где к^)-наибольшее (наименьшее) допустимое число серий:

ъ < < 1п/т_э + I. сп/т^! ( Су1 - целая часть числа у).

Обозначим т° = (т°) - вектор моментов "разладки"(ъ=1,к°- 1): D°= ( ) - вектор номеров классов серий (j = 1,к°).

Задача классификации и оценивания параметров временного ряда с многократными "разладками" заключается в восстановлении последовательности v° номеров классов наблюдений по реализации временного ряда я* длительностью п, что эквивалентно построению РП для нахождения оценок к. г. d числа серий к? векторов т° d° соответственно, а также в анализе эффективности определения указанных характеристик.

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

В § 1.2 поставлена экстремальная задача нахождения ОРП при заданных вероятностных характеристиках временного ряда. Для определенности рассмотрен случай абсолютно-непрерывных распределений. Задано семейство N-мерных плотностей з> = (р(х). х е в котором

зафиксировано ъ различных известных плотностей р°( •).....) е з>.

Временной ряд хт длительностью п состоит из к° независимых серий с длинами ... образующими последовательность независимых в совокупности случайных величин с распределением вероятностей (2). Номера классов серий d°.....d°„ образуют последовательность независимых случайных величин с распределением вероятностей (4).

Обозначим к, т=сту) (k=i.к-i). n=(d.) 1,к> -возможные значения числа серий it. векторов т°, в° соответственно. Для произвольных к е ак, \.....хк е ат, моментов возможной "разладки" гк=

=гк_1+ iv (Ь = ТТк; то= о. тк= п) "разобьем" наблюдаемый временной ряд хт (аналогично (I) ) на к серий:*т= (х[: ... :

Теорема 1.2Л. Если р°го.....vZ(,) € р известны и число серий к равномерно распределено на множестве ак, то минимальная вероятность ошибка .оценивания к°. т°. в° достигается, оптимальным решающим правилом:

к = are mas l2 (Х\К), X = Are пах lí(X\K,T),

кед т = < т, >

К к

к к-1

cL = агв тп&х I tn 1С. + ) Чтъ |х I

^ ieJf [ М 1 1 vXJ

t = i

( к.= 1. К .: То = О. = п ), ° к

ГДв К-2

гг(х\к) = тах г1СХ|К.Г;; г1(х\к.т) = У ,

Т= < Т, > , '

к к = »

а для функций Фк г•; приведены явные выражения. Оптимизация по г осуществляется с помощью эффективной процедуры динамического программирования, вычислительная сложность которой имеет порядок ©((V т;_)г(<- к!)). .

В § 1.3 проведено исследование эффективности ОРП. Для оценки потенциальной точности классификации рассмотрен случай, когда число серий к° и вектор г° (длины серий ... .т°„) известны (определены безошибочно).

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

п к*

О4 = п 1 2* С\* = "" 1 < Р <>■

X =-1 к = 1

Когда длины серий являются случайными величинами с известным одинаковым распределением вероятностей, точность классификации характеризуется средним относительным числом ошибочных решений (.за промежуток времени длительностью пк„ • с фиксированным числом к° полных серий):

о4 = в <д4> = п^ к° е | р (а* }.

В случае двух равновероятных классов, в асимптотике растущих длин серий (г_> <*>) и "сближающихся" классов для ОРП получены асимптотические выражения характеристик

В § 1.4 рассматривается оптимальная классификация гауссовских временных рядов с многократными "разладками". В случае двух равновероятных классов, когда длины серий = 1 + где т)к - случайная величина, имеющая распределение Пуассона с параметром Я, показано, что учет "серийной" структуры временного ряда при его классификации приводит к существенному выигрышу в эффективности по сравнению с "поточечной" классификацией. На рис.1 приведены графики зависимости сз4от А, и расстояния Махаланобиса' Л: чем больше средняя длина серии иК и чем больше Д, тем точность классификации выше (¡э меньше). При использовании "поточечной" классификации ( без учета "серийной" структуры ) средняя относительная доля ошибок Оо= Фс-А/г; существенно больше.

0,4

0,3 0,2 0,1

\\ \ V \ , V V ^

ч N ч

¿Ul4 S N *

0,5

Д,5 Рис.1

2,5

Глава II посвящена построению РП классификации и оценивания параметров векторных временных рядов с многократными "разладками" в условиях, когда у -семейство распределений, зависящих от т-вектора параметров бе/. В этом смысле у является т-параметрическим семейством распределений, а строящиеся_ РП - параметрическими.

В §2.1 строятся РП, основанные на применении принципа максимального правдоподобия. Рассматривается случай, когда з>'= <р(х; в), х е iF: 6 б е £ к") - m-параме трич в сков семейство плотностей распределения вероятностей, удовлетворяющее условиям регулярности Чибисова; (6°.....с 9 - подмножество ь г г различных неизвестных значений параметра. Временной ряд хт длительностью п состоит

из к° независимых серий. Длины серий .....^»-i е ^т шеют

распределение (2), а длина к°-ой серии г°. является случайной величиной с распределением (3). Номера классов серий d°.....а°ко

имеют распределение (4). п

Обозначим: В = arg гшх Е гп p(xt; 8; - оценка максималь-е«е- t = i т

ного правдоподобия параметра 6 при условии, что временной ряд х -

однородный; ß(®; I; = v0 in Р(х; -Q)|e_g - m-вектор-столбец частных

производных первого порядка; чся; 6) = v* in р(х; 9;je=g - ы х mj-симметрическая матрица частных производных второго порядка;

. к

бУл

-Е

7<Ч

е л

-ю -

а(Х) = I In p(xt; в)

Теорема 2.1.1. Если ? - семейство плотностей, удовлетворяющее условиям регулярности Чибисова, и рассматривается случай "сближающихся" классов: |9° - 0°| = осеj. е + о « Х), то в в-окрестности точек (6°> логарифмическая функция правдоподобия допускает представление

UX; К. T. D. CGt >J> = 1(Х: К. Т. D. +*(E2).

к

l(.) = <X(X) + У fin C1Cd qk(Tk- Г^» + bTfric_1,rk;f8J - 9j +

dk

+ I Г0 - «гг^. Tkj fe - ej). k k '

Оценки для к". т°, d°. находятся из условия:

lt(X; К, Т. Г) = тая 1(Х; К, Т. D. fftjj > max max .

fe.ee> 1 t,u к

Для совместного оценивания к°. т°, d° определено семейство субоптимальных РП вида: к-р

У ®ьСТ,. ...... Т. : d......d. ) пах max .

, i k k-1 k + p k . k«-p

k=l T,D К

где p - параметр семейства, i < p < к - t. выбираемый исходя из компромисса между точностью решений, ресурсами машинного.времени и оперативной памятью; а для функций Фк(0 привздены явные выражения. Вычислительная сложность процедуры динамического программирования при максимизации по т имеет порядок

0(LP*' )р (\-t_f ( (К^-р)3-(К_-р)Я j).

Предложено более простое в вычислительном отношении двухэтап-ное РП для нахождения оценок к. Ь: сначала строятся оценки к. а затем Ь. Для совместного оценивания т°, к° определено семейство субоптимальных РП вида:

К-р-2 . .

Z,. СТ.. .:. .Т. »- max max , 4i 4 J" т к

где p - параметр семейства, i < p< к - з , а для функций f.(-) приведены явные выражения.

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

О (ст, -т_+1 )р ст. / с гк4 -Р ск_ -Р;3;). • В § 2.2 решается 'задача классификации дискретного временного ряда д\ состоящего из к° серий-наблюдений, являющихся независимыми дискретными случайными ^-мерными векторами г1=

N _

1и е 3(т + 1) = {0.1. ... . т), Е ®и= т. Ь - 1. п. Рассмотрен

I = »

случай, когда у - семейство полиномиальных распределений вероятностей порядка N с индексом т и вектором элементарных вероятностей V = (V......и,;:

ч

н

\P(z;v), z = (zi) е s" Cm + 1), Е zt = т: ■ 1 1

! N z. N 1

P(z; v) = —- П и/. 2 О. E vi =

П 2i'

V-1 1=1

1=1

(6°.....в°> с e с s" - подмножество l > 2 различных неизвестных значений вектора элементарных вероятностей. Длины серий ... « аг имеют распределение (2), а т°„ - случайная величина с распределением (3). Номера классов серий .....d°„ образуют последовательность (<%>. представляющую собой реализацию однородной цепи Маркова с начальным распределением вероятностей (Б) и матрицей вероятностей одношаговых переходов (6).

Оценки для к°, т°. Ь° по критерию максимального правдоподобия определяются из решения экстремальной задачи:

I (Xi К, Т. ю = Шах КХ; К. Т. D, (9.» max max , <е. ев> т, d к

V

где К') - логарифмическая функция правдоподобия. Как и в § 2.1, для совместного оценивания к° т°. г>° определяется, семейство субоптимальных РП вида:

К-р-1

) Т......I. : d......d. ) * max max .

¿11 J-p*» J i+p** T D K '

где p - параметр семейства, 1 s p £ к - г; для функций Ф. (■) приведены явные выражения.

В § 2.3 предложен другой подход к построению РП классификации временных рядов с многократными "разладками". В его основе лежит применение функционалов межклассового расстояния в пространстве вероятностных распределений.

Пусть х°т. ^ к < г £ к°) - две произвольные серии наб-

людений с длинами т;°.т;01. принадлежащие классам , ( здесь и

далее используется краткая запись вместо П о, Q о ). Определим

ak ai

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

Рн = РГРк 'РГ > = V К (х)• р° (х) } <7>

N

*

где р°(•) - вероятностное распределение наблюдений 'из класса П.п « гг) > о - дважды непрерывно дифференцируемая

симметричная функция ¡аргументов х±. гг > о такая, что Сг1,гг) = = о ** = гг; /2(у) ^ о - монотонно возрастающая функция аргумента у г о,- гг(у) = о «» у = о. Частными олучаями функционала (7) в пространстве вероятностных, плотностей являются: расстояние в ь2-метрике, расстояние Бхаттачарья, дивергенция Кульбака.

Рассматривается случай, когда з> - т-парамётрическое (т < семейство плотностей, удовлетворяющее условиям регулярности Чиби-сова. Длины серий х°.....е ат образуют случайную последовательность с двумерным распределением вероятностей ч2с т.-г; =

= рсх° = т. т°+1= а*;, х, х- е ат (к = i, к" - D; частным случаем является случай независимых одинаково распределенных длин серий: O/X.X'J = qifX;xqiCt' ), q^l) = PiT^ t « Ar(k = ITH').

Обозначим: pifB)t,eiJ = pCpf.; 9kJ. p( ■; 9tJ). 9k. 9te 0 s дт; оператор вычисления набора mJ частных производных порядка j по бел"1; 0 - символ Кронекера.

JfG; = - J- СУд In р(х; 9)) р(х; д) dx -м

R

информационная матрица Фишера порядка m 6ке 9 - оценка максимального правдоподобия параметра 0°, вычисленная по сер™ наблюдений х°к! Ры= Pif^k,®i-) ~ статистическая оценка межклассового расстояния p°L по сериям х°т. Определим гипотезу однородности к - й и 1-й серий яоИ= d°.

Теорема 2.3.1. Если р - семейство плотностей, удовлетворяющее условиям регулярности Чибисова, верна гипотеза ям и

7е о Pt(0k.0i)

j

= (-1 B(Q°). i,j e {к.г).

е.= 9 = е° , k

k I к .

v

где в(вк) - некоторая положительно определенная симметрическая матрица порядка т, то в асимптотике растущих длин серий <"Г_*-справедливо стохастическое разложение статистики рн:

Т

Рн= I ♦ 1/хр еу-"2 (0°)] все") .г"2 сер ? ♦ орсхГ2).

где обозначена матрица, такая что (У/2<'9°;)т/''2('0°; =

= .'"(•6°;; £ = (£а) е нт - гауссовский вектор с т независимыми

компонентами, имеющими стандартное нормальное распределение nt(o: 1), а о - остаточный член порядка х"3'2,

сходящийся к нулю по вероятности.

Следствие 2.3.1. Если в(в°j = (2/о) где о - константа

(о =8 для расстояния Бхаттачарья, о = 1 для дивергенции КульОака), то нормированная оценка межклассового расстояния •и = К- гГ-,- = ° < < << + Р« асимптоти-

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

Следствие 2.3.2. Пусть 71 f«o - квантиль уровня 1 - а хи-квадрат распределешя с m степенями свободы. В условиях следствия 2.3.1 асимптотический гт * «о размер теста.

n™nmu««„a / вСЛИ С

принимается < _

I яок1. если гЬ1 s

совпадает с заданным уровнем значимости а е со. п.

Для произвольных к е лк. xit ... . тк е atî моментов возмож-

ной "разладки" тк = гк1 + тк (ь = 1. к г то= о. тк= п) построим статистики (г.,>. а также функционал

я = ягк.т; = '■к.к^^к-!'^-^-^^-

ка»

где я - усредненная (с весами) по всем к - 1 "разладкам" величина межклассового расстояния. Оценки й. определяются при решении экстремальной задачи

И (К,Т) —пах тах .

. т к _

К-а

Я«. Т) ш <К- I)-1 £ 9к(Тк. Т^.

Для функций ®к(.) приведены явные выражения. С помощью следствия 2.3.2 может быть проверена статистическая значимость каждого момента возможной "разладки": является а-значимым моментом "разладки", если гкк+1 & \_а(п).

Для нахождения оценки Ь при уже найденных оценках к . т применяется иерархическая процедура кластер-анализа, основанная на критерии » л А ■

»<к<1<К

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

Параграф 2.4 посвящен анализу мощности построенного в § 2.3 теста проверки гипотезы однородности нок1.

В дополнение к вм определена е-близкая альтернативная гипотеза неоднородности я1к1: , 0°= ьк + еч, сч. е * о. Доказана теорема 2.4Л, в которой при истинности гипотезы д1к1 в асимптотике растущих длин серий и "сближающихся" классов: т-* «>, е = © гт"1'2; -*- о получено стохастическое разложение статистики рн. В условиях следствия 2.3.1 показано, что статистика гк1 теста однородности при истинности альтернативы я1к1 асимптотически' распределена по нецентральному закону хи-квадгат с т степенями свободы и параметром нецентральности к2, для которого получено аналитическое выражение. Приведены графики зависимости мощности ш теста однородности от параметров: уровня значимости а, размерности т параметрического пространства, параметра нецёнтральности А,2.

В § 2.5 приведены результаты вычислительных экспериментов. Методом статистического моделирования на ЭВМ проведено исследование точности: двухэтапного РП классификации, описанного в § 2.1, для случая гауссовского семейства плотностей и двух равновероятных классов; РП, описанного в §2.2', для семейства полиномиальных распределений, а также РП, описанного в §2.3 и основанного на параметрической статистической оценке межклассового расстояния Бхаттачарья для гауссовского семейства плотностей. Численная эффективность алгоритмов, использующих указанные РП, характеризуется средней относительной частотой rv несовпадения элементов и V, а также показателем эффективности гт, определящим суммарное минимальное смещение оценок моментов "разладки"; найдены точечные гт и интервальные оценки для этих характеристик. Приведены таблицы и графики зависимости г, гт от расстояния Махаланобиса А, иллюстрирующие эффективность предложенных РП.

Глава 3 посвящена построению РП классификации векторных временных рядов с многократными "разладками", не использухзоцбс априорных сведений о параметрической модели распределений наблюдв1. Лив этом смысле являющихся непараметрическими.

В § 3.1 развивается предложенный в § 2.3 подход, основанный на использовании статистических оценок межклассовых расстояний в случае, когда р=(р(х). - непараметрическое семейство трижды

непрерывно дифференцируемых N - мерных плотностей, ограниченных

вместе со своими производными, причем

А (р) = / р'(х)Ох <00 ,3=1,2.3. N

в

Построена состоятельная непараметрическая оценка межклассового х2- расстояния

Рц= Ри^к-!-^- г1-1':гГ-) = 5 <-К(х> ~ ¿о . где

N

Н

о I.

V

= С^Г* £ СГН~* Гх-а:4 х е { е (к, I) -

1-1

шараметрическая оценка Розенблатт'а-Парзена для плотности р^х). iчиcлeннaя по серии к(у) = (2%)~ыугехр (-уту/2) - я-мерное .•ауссовское ядро; я.= а.1ае - диагональная матрица порядка ы; к > о - коэффициент сглаживания, н = ^ гт° - т°_1)'а (а. > о,

bj > о, J = ТГю. Получен явный вид статистики рк1:

Ра= Чк+ «и^ 2 "

тк Ti

«ki- к К+ " Y. ZK +

t =T • tl t'=T" »1 k-i l-i

Определим гипотезу однородности серий x°T.x°T(r i ь < г < к°),

Теорема 3.1 Л. Если , р°со « у, верна гипотеза яок1 и

(н + 4)~1 < а < n'1 , то при ■ -»- о» справедливы асимптотические разложения для моментов первого и второго порядка статистики pkl:

j-2tNa+ яг^)"1 " (8)

крк1> -ггх^У1-" В-ЧЦР:

1<5<к,1>

/• л "I N в

х (( <%1)-3а+ с^Г") /г ) + в = пьг

Решающие правила строятся также, как было предложено в § 2.3. Оценки числа серий к и вектора т ищутся из условия

R(K, Т) тах пах , т к

где

R(K.T)=(K-1)-iKfqi(Tk- Tk_t)4i(тк + 1- (Т^.^.Т^Т^).

к = 1

Для нахождения оценки в применяется иерархическая' процедура кластер,-анализа, основанная на критерии

| l^k <l ^К

Вычислительная сложность процедуры динамического программирования при максимизации по г имеет порядок %_)2aâ -к3_)).

В § 3.2 рассмотрена задача обнаружения- многократных "разладок" векторных временных рядов, состоящих из к° фрагментов двух чередующихся классов сь = г): если наблюдения ь-го фрагмента принадлежат классу Qd„, то (k + п -й фрагмент состоит из наблюдений к

класса fl3_d.. е <1.2). k=i, к3. Так же как и в §3.1, з> - непараметрическое семейство трижды непрерывно дифференцируемых плотностей р(х). х g п", ограниченных вместе со своими производными.

Используется непараметрическая статистическая оценка межклассового ъг- расстояния. Для фиксированного а е сг,з.....строится

k-e "s-OKHO" T3Ot): Ta(k) = 1.....г"^ ^ (к = 77к°-а + 1),

а также ь-й "з-фрагмент" (k):

х-(к) = Ь c,= (v«;-!v }•

i = l k-1 kta-1-»

Параметр а определяет размер "з-окна" -г"(Ь) и число наблюдений, входящих в "s-фрагмвнт" х"(Ъ). Также, кйк и в §§2.3, 3.1, определен функционал межклассового расстояния р" для классов , о2 по ь-ому "s-фрагменту" х"(к), для которого построена состоятельная

непараметрическая оценка р°= т°.....Построение

р° осуществляется с использованием для плотности непараметрической оценки Розенблатта-Парзена с многомерным гауссовским ядром, вычисленной по xs(k). Приведен явный вид статистики р", а также асимптотические разложения для моментов первого вср"> и вторс^;о Жр'} порядка. Вид этих разложений такой же, как и (8), но построены они с привлечением большего числа наблюдений; это позволяет увеличивая а , увеличивать точность РП.

Построение РП осуществляется таким же способом, как было предложено в § 2.3, 3.1. Зафиксируем значение параметра а и построим статистики < р® у и функционал

Н(К.Т;е) = ..... Тк»а-1 ) .....

к=1

«"^к-х..... гк*.-») = Пч»^«-*- ткн-2 ) .

Оценки к. т находятся как решение задачи

Д (К, Г;, в) -» тах пах т к

Вычислительная сложность процедуры динамического программирования в задаче максимизации по г имеет порядок

В § 3.3 получено асимптотическое распределение состоятельной непараметрической оценки рк1 межклассового х2- расстояния, построенного в § 3.1.

Теорема 3.3.1. Если р°с;, р°С) е з>, верна гипотеза нок1, то при « оценка межклассового расстояния Рк1 асимптотически распределена по нормальному закону с математическим ожиданием е <рк1) и дисперсией и <"рк1 >, определяемыми по формулам (8).

Следствие 3.3.2. Пусть квантиль уровня 1-а/2 стан-

дартного нормального распределения. Асимптотический (%_ - размер теста

Г нок1, если |г° | <* , принимается 4 ^

I Н . , , еСЛИ I г° I 2:« ,

. о к I " 1 к1 1 2 *

совпадает с заданным уровнем значимости а <= (о,г). Здесь гк1=

= фк1 - й{"рк1})/ Увсрк1 у -. нормированная непараметрическая оценка межклассового расстояния.

Теорема 3.3.1 и ее следствие являются обоснованием использования статистик гк1 при проверке статистической а - значимости каждого момента возможной "разладки".

В § 3.4. .описаны результаты статистического моделирования, проведенного для исследования эффективности алгоритма классификации, основанного на непараметрической статистической оценке межклассового ьл- расстояния и описанного в § 3.1, для гауссовского семейства плотностей и двух классов. Приведены графики зависимости показателей эффективности rv, гт от расстояния Махаланобиса Д, иллюстрирующие эффективность предложенных решающих правил.

В заключении сформулированы основные результаты работы.

ОСНОоШЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

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

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

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

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

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

жения для моментов первого и второго порядка. На основе построенной оценки разработано решающее правило и алгоритм классификации наблюдаемого временного ряда.

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

8. Параметрические РП, разработанные на их основе алгоритмы и программное обеспечение использовались при выполнении хоздоговорных НИР Л 38745, * 38790.

Основные результаты диссертации опубликованы в работах:

1. Мельникова E.H. Харин Ю.С. Распознавание случайных серий наблюдений // Методы и программное обеспечение обработки информации и прикладного статистического анализа данных на ЭВМ. -Минск, 1985. - 0. 164 - 165.

2. Мельникова E.H., Харин Ю.С. О классификации серий многомерных наблюдений при случайной длине серий // Вестник БГУ. Сер. I, * 2, 1988. - С. 43 - 48.

3. Мельникова E.H. Классификация временных рядов с помощью статистик Бхаттачарья // 3 Всесоюзная конференция "Перспективные методы планирования и анализа экспериментов при исследовании случайных процессов и полей": Тез. докл. - Гродно, 1988. - С.158-159.

4. Мельникова Ь.Н. О классификации дискретных временных рядов // Республиканская конференция молодых ученых' и специалистов "Применение информатики и вычислительной техники при решении народнохозяйственных задач": Тез. докл. - Минск, 1989. - С. 91.

5. Мельникова E.H. О применении статистических оценок межклассовых расстояний в анализе временных рядов с многократными разладками // Актуальные проблемы информатики: математическое, программное и информационное обеспечение": Тез.докл. - Минск, БГУ, 1989. - С. 63 - 64.

6. Мельникова Е,.Н., Харин Ю.С. Статистическая классификация кусочно-стационарных временных рядов // Всесоюзная научно-техническая конференция "Методы представления и рбработки случайных сигналов и полей": Тез.докл.- Харьков, 1989. С. 140.

7. Мельникова E.H., Харин Ю.С. Использование статисти-

ческих оценок межклассовых расстояний для анализа временшйс рядов с многократными разладками // Статистические проблемы управления, вып. 89, - Вильнюс, 1991. - С. 188 - 196.

8. Мельникова E.H. О статистическом анализе потоков со скачкообразными изменениями в СМО // Республиканская научно-техническая школа-семинарj"Анализ синтез систем массового обслуживания и сетей ЭВМ", ч. 2. - Одесса, 1990. - С. 101 - 105.

9. Мельникова E.H. О выявлении многократных "разладок" временных рядов в случав двух классов: - В сб.: Проблемы компьютерного анализа данных и моделирования. - Минск, 1991. - С. 124 - 129.

10. Мельникова E.H., Харин Ю.С. Обнаружение многократных "разладок" и классификация временных рядов с помощью статистических оценок межклассовых расстояний // Автоматика и телемеханика, 1991, № 12. - С. 7G - 84.

Подписано к печати 22.05.92 г. Формат 60x84/16 Объем 1.0 п.л. Тираж 100 окп. Закат № Ъ<&4

Отпечатано на ротапринте Белгосуниверситетэ. 220080, г. Мчигк, ул.Бобруйская, 7