Содержание к диссертации
Введение
1 Последовательное обнаружение момента изменения среднего значения последовательности независимых случайных величин 12
1.1 Постановка задачи 13
1.2 Процедура обнаружения разладки 13
1.3 Расчет основных характеристик процедуры 17
1.3.1 Среднее время между ложными тревогами 18
1.3.2 Среднее время запаздывания 25
1.3.3 Результаты моделирования , 33
1.4 Исследование свойств процедуры 38
1.5 Сравнительный анализ процедуры обнаружения разладки для последовательности с неизвестным распределением со случаями известного распределения . 42
1.5.1 Случай неизвестного распределения 43
1.5.2 Случаи известного распределения -45
1.5.3 Моделирование 50
1.6 Среднее время запаздывания в стационарном режиме 53
1.7 Асимптотические соотношения для среднего времени запаздывания в стационарном режиме 61
1.8 Выводы 66
2 Обнаружение момента изменения среднего значения процесса авторегрессии первого порядка 68
2.1 Постановка задачи 69
2.2 Оценка параметров авторегрессионной части 69
2.3 Построение процедуры обнаружения 71
2.4 Расчет основных характеристик процедуры 72
2.4.1 Нахождение характеристик процедуры для случая неизвестного распределения шумов 85
2.4.2 Моделирование и анализ полученных результатов . 91
2.5 Выводы 97
3 Обнаружение момента разладки процесса авторегрессии р—того порядка 98
3.1 Постановка задачи 98
3.2 Оценка параметров авторегрессионной части 99
3.3 Построение процедуры обнаружения 100
3.4 Результаты моделирования 110
3.5 Выводы 111
Заключение 112
Литература 114
Приложения 126
- Среднее время между ложными тревогами
- Среднее время запаздывания в стационарном режиме
- Нахождение характеристик процедуры для случая неизвестного распределения шумов
- Построение процедуры обнаружения
Введение к работе
Данная диссертационная работа посвящена проблеме обнаружения разладки. Под обнаружением разладки понимается класс задач обнаружения изменения вероятностных характеристик случайной последовательности.
Впервые задача обнаружения разладки была сформулирована в 30-е годы XX века в работе Шыохарта [85] и с этого момента начала интенсивно развиваться. Первоначально задача получила применение в промышленном производстве, медицинских исследованиях, геофизике, задачах технической диагностики, обработке сигналов.
За прошедшие годы развитие науки и техники ставит все новые научные, технологические и сугубо прикладные задачи, о существовании многих их которых невозможно было даже подумать во время опубликования первых работ по данной тематике. Тем не менее оказывается, что многие из этих задач можно свести к задаче обнаружения разладки, воспользоваться уже существующим аппаратом. Кроме того, этот процесс стимулирует появление новых работ в данной области, исследующих всевозможные модификации существующих методов для новых приложений в зависимости от постановки конкретных задач. В качестве примера подобных новых приложений можно привести интернет-технологии. Развитие информационных технологий также сыграло важную роль в возникновении новых приложений. Необходимость автоматизации процессов накопления, обработки и ана-
. 4
лиза данных в науке, производстве и бизнесе предоставляет широкое поле для применения аппарата математической статистики, в том числе методов обнаружения разладки.
Таким образом, класс задач обнаружения разладки является очень широким. Эти задачи отличаются одна от другой предположениями о модели наблюдаемого процесса и подходами к ее решению. Существует два основных метода решения задачи разладки: методы апостериорного обнаружения по выборке фиксированной длины и последовательные методы обнаружения. В первом случае предполагается, что в имеющейся последовательности наблюдений в некоторый момент произошло изменение характеристик и на основе полученных наблюдений необходимо оценить момент изменений. При этом свойства получаемых оценок изучаются в асимптотической постановке при объеме наблюдений, стремящимся к бесконечности. Для различных моделей наблюдаемых процессов апостериорные методы обнаружения рассматривались Дарховским Б.С, Бродским Б.Е. [3, 5, 20] и др.
При последовательном обнаружении на каждом шаге при поступлении нового наблюдения гипотеза о наступлении разладки либо принимается и наблюдения прекращаются, либо отклоняется и наблюдения продолжаются дальше. Поскольку для принятия решения о наличии разладки необходимо получить определенное количество наблюдений, описываемых новой моделью, возможно возникновение запаздывания в обнаружении. Но возможна и другая ситуация, когда решение о наличии разладки принимается тогда, когда реально изменение еще не произошло, т.е. имеет место ложная тревога. Понятно, что на практике желательно свести к минимуму количество ложных тревог и время запаздывания. Ширяевым [54, 55] были введены показатели качества процедуры обнаружения: малое число ложных тревог
или, что то же самое, большое среднее время между ложными тревогами
и малое среднее время запаздывания. Требование одновременного выполне
ния этих условий является противоречивым, т.к. чем чувствительнее про-
щ цедура к возможным изменениям, тем больше вероятность возникновения
ложных тревог и наоборот, чем менее чувствителен детектор к шуму, тем
больше среднее время запаздывания в обнаружениях. Процедура обнару
жения считается оптимальной, если при фиксированном среднем времени
между ложными тревогами запаздывание в обнаружении минимально.
Хорошо изученной является задача обнаружения изменения раслределе-
*' ния в последовательности независимых случайных величин, для решения ко-
торой применяются методы скользящего среднего, например в работе Бродского Б.Е., Дарховского B.C. [6], метод экспоненциального сглаживания в работах таких авторов как Новиков А., Эргашев Б., [43, 44], Фишман М. [51], а также [70, 77] и др. Работы [55, 58, 76, 81, 86, 78] основаны на алгоритме кумулятивных сумм, предложенном Пейджем [79] и методе усредненного отношения правдоподобия Гиршика-Рубина-Ширяева [69, 58].
В работе Лордена [76] было установлено, что оптимальной в классе после-
* довательных процедур обнаружения (в смысле минимума среднего времени
запаздывания при заданном среднем времени между ложными тревогами)
является процедура кумулятивных сумм, представляющая собой многократ
но возобновляемую процедуру Вальда [7] с нулевым нижним порогом. Там
же было показано, что отношение среднего времени запаздывания к лога
рифму среднего времени между ложными тревогами стремиться к константе
* при стремлении среднего времени между ложными тревогами к бесконечно-
сти.
Многие работы, посвященные последовательному обнаружению разлад-
ки, рассматривают обнаружения изменения функции распределения в последовательности независимых случайных величин в предположении, что известны начальная и конечная модели процесса [59]. Большой интерес на практике представляют случаи, когда распределение наблюдаемого процесса до и после момента разладки не известно [21, 22, 46]. В работе [6] проводится сравнительный анализ различных непараметрических методов для обнаружения различных величин скачка среднего значения наблюдаемого процесса.
Даже в случае независимых наблюдений аналитическое исследование характеристик процедуры кумулятивных сумм является довольно трудной задачей. Подобные исследования описаны в работах Поллака, Зигмунда [83, 84], Якира [87, 88, 89], где получены асимптотические формулы для среднего времени между ложными тревогами и формулы для среднего времени запаздывания, содержащие неизвестные константы.
В работах таких авторов как Бассвиль, Бенвенист [63, 64], Бородкин, Моттль [2], Никифоров [40, 41, 42], Клигене [28, 29], Липейка [31, 32, 33], Липейкене [35, 36], рассмотрены процедуры обнаружения момента разладки случайных процессов с зависимыми значениями. В большинстве этих работ в качестве моделей наблюдаемых процессов чаще всего используются процессы авторегрессионного типа. Известны результаты, связанные с нахождением либо среднего времени между ложными тревогами [2], либо среднего времени запаздывания в обнаружении [37]. Аналитическое исследование качественных характеристик и свойств подобных процедур является очень сложной и порой невыполнимой задачей.
Широкое применение задача обнаружения изменения свойств наблюдаемого процесса получила в экономике и финансовом анализе. В работах
[66, 68, 71, 73, 74] предложено ее применение для анализа временных рядов, описываемых ARCH и GARCH моделями,
В последнее время интерес к этой проблеме не угасает, о чем свидетельствует большое количество работ в этой области [47, 48, 90, 72, 75, 67, 62, 66] и многие другие.
Таким, образом, актуальным является разработка последовательных методов обнаружения произвольного скачка среднего значения в последовательности независимых случайных величин с неизвестным законом распределения и процессов с зависимыми значениями, а также анализ предложенных методов.
Целью настоящей работы является построение последовательных процедур обнаружения разладки, позволяющих обнаруживать как увеличение, так и уменьшение среднего значения наблюдаемого процесса для последовательности независимых наблюдений с неизвестным законом распределения ипроцесса авторегрессии с неизвестными параметрами с возможностью аналитического исследования характеристик данной процедуры.
Методы исследования. При решении поставленной задачи использовался аппарат теории вероятностей, теории случайных процессов, теории аналитических функций, теории матриц и методы статистического моделирования.
Научная новизна. В данной работе построены последовательные процедуры обнаружения разладки, позволяющие обнаруживать как положительное, так и отрицательное изменение среднего значения наблюдаемого процесса для последовательности независимых наблюдений с неизвестным законом распределения и процесса авторегрессии с неизвестными параметрами. Получены формулы для расчета основных характеристик процедуры:
среднего времени между ложными тревогами и среднего времени запаздывания.
Практическая ценность. Полученные результаты могут применяться
Щ в медицинских исследованиях, в экономике и финансовом анализе, геофизи-
ке, задачах климато-экологического мониторинга; технической диагностике, обработке сигналов.
На защиту выносятся следующие основные положения:
Последовательная процедура обнаружения изменения среднего значения в последовательности независимых случайных величин с неизвестным законом распределения.
Последовательная процедура обнаружения изменения среднего значения устойчивого процесса авторегрессии первого порядка с нормальным и произвольным распределениями шумов.
Последовательная процедура обнаружения изменения среднего значения устойчивого процесса авторегрессии р—того порядка с нормальным распределением "шумов.
Аппробация и публикации.
Основные результаты диссертационной работы докладывались и обсуждались на следующих конференциях:
Третьем Сибирском конгрессе по прикладной и индустриальной матема-тике( ИНПРИМ - 98, Новосибирск, 1998);
Четвертой региональной научно - практической конференции студентов, аспирантов и молодых ученых "Научные основы АПК"(Томск, 2002);
Всероссийской научно - практической конференции "Информационные технологии и математическое моделирование"(Анжеро-Судженск, 2002);
Региональной научной конференции студентов, аспирантов и молодых
ученых "Наука. Техника. Инновации"(НТИ-2002, Новосибирск, 2002); ' Четвертом Всероссийском симпозиуме по Прикладной и промышленной математике (Обозрение прикладной и промышленной математики, Москва, 2003)
По теме диссертации опубликована две печатные работы, в том числе в академическом журнале:
Радиотехника и электроника, РАН'(2002, 47 (10), с. 1198-1203).
Структура диссертации.
Работа состоит из введения, трех глав, заключения и списка литературы.
В первой главе диссертации предлагается последовательная процедура обнаружения момента изменения среднего значения последовательности независимых случайных величин, построенная на основе алгоритма кумулятивных сумм. Получены формулы для нахождения основных характеристик процедуры: среднего времени между ложными тревогами и среднего времени запаздывания. Получены асимптотические соотношения для этих характеристик при неограниченном возрастании порога процедуры. Проведен анализ оптимальных (в смысле минимума среднего времени запаздывания при заданном среднем времени между ложными тревогами) процедур обнаружения изменения среднего для последовательностей с известным распределением (гауссовское, двойное экспоненциальное и распределение Коши) до и после момента разладки и сравнение с ними посторенной процедуры, когда распределение считается не известным. Приведены результаты численного моделирования. Найдено среднее время запаздывания в стационарном режиме. Результаты данной главы опубликованы в работах [10, 11, 12, 25].
Во второй главе решается задача обнаружения произвольного скачка среднего для устойчивого процесса авторегрессии первого порядка. Рассматрива-
ются два случая: случай нормального распределения шумов и случай, когда распределение шумов неизвестно. На первом этапе производится оценивание неизвестных (мешающих) параметров авторегрессионной части. Далее осуществляется преобразование наблюдаемого процесса с целью ослабления влияния этих параметров. Строится последовательная процедура обнаружения на основе алгоритма кумулятивных сумм. Получены формулы для среднего времени между ложными тревогами и среднего времени запаздывания в обнаружении разладки. Приведены результаты численного моделирования. Результаты этой главы опубликованы в работах [26].
В третьей главе результаты предыдущей главы распространяются на случай многомерного авторегрессионного процесса. Предлагается и исследуется аналогичная процедура обнаружения разладки, результаты иллюстрируются моделированием. Результаты главы опубликованы в работе [13].
[
Среднее время между ложными тревогами
Данная диссертационная работа посвящена проблеме обнаружения разладки. Под обнаружением разладки понимается класс задач обнаружения изменения вероятностных характеристик случайной последовательности.
Впервые задача обнаружения разладки была сформулирована в 30-е годы XX века в работе Шыохарта [85] и с этого момента начала интенсивно развиваться. Первоначально задача получила применение в промышленном производстве, медицинских исследованиях, геофизике, задачах технической диагностики, обработке сигналов.
За прошедшие годы развитие науки и техники ставит все новые научные, технологические и сугубо прикладные задачи, о существовании многих их которых невозможно было даже подумать во время опубликования первых работ по данной тематике. Тем не менее оказывается, что многие из этих задач можно свести к задаче обнаружения разладки, воспользоваться уже существующим аппаратом. Кроме того, этот процесс стимулирует появление новых работ в данной области, исследующих всевозможные модификации существующих методов для новых приложений в зависимости от постановки конкретных задач. В качестве примера подобных новых приложений можно привести интернет-технологии. Развитие информационных технологий также сыграло важную роль в возникновении новых приложений. Необходимость автоматизации процессов накопления, обработки и анализа данных в науке, производстве и бизнесе предоставляет широкое поле для применения аппарата математической статистики, в том числе методов обнаружения разладки.
Таким образом, класс задач обнаружения разладки является очень широким. Эти задачи отличаются одна от другой предположениями о модели наблюдаемого процесса и подходами к ее решению. Существует два основных метода решения задачи разладки: методы апостериорного обнаружения по выборке фиксированной длины и последовательные методы обнаружения. В первом случае предполагается, что в имеющейся последовательности наблюдений в некоторый момент произошло изменение характеристик и на основе полученных наблюдений необходимо оценить момент изменений. При этом свойства получаемых оценок изучаются в асимптотической постановке при объеме наблюдений, стремящимся к бесконечности. Для различных моделей наблюдаемых процессов апостериорные методы обнаружения рассматривались Дарховским Б.С, Бродским Б.Е. [3, 5, 20] и др.
При последовательном обнаружении на каждом шаге при поступлении нового наблюдения гипотеза о наступлении разладки либо принимается и наблюдения прекращаются, либо отклоняется и наблюдения продолжаются дальше. Поскольку для принятия решения о наличии разладки необходимо получить определенное количество наблюдений, описываемых новой моделью, возможно возникновение запаздывания в обнаружении. Но возможна и другая ситуация, когда решение о наличии разладки принимается тогда, когда реально изменение еще не произошло, т.е. имеет место ложная тревога. Понятно, что на практике желательно свести к минимуму количество ложных тревог и время запаздывания. Ширяевым [54, 55] были введены показатели качества процедуры обнаружения: малое число ложных тревог или, что то же самое, большое среднее время между ложными тревогами и малое среднее время запаздывания. Требование одновременного выполне ния этих условий является противоречивым, т.к. чем чувствительнее про щ цедура к возможным изменениям, тем больше вероятность возникновения ложных тревог и наоборот, чем менее чувствителен детектор к шуму, тем больше среднее время запаздывания в обнаружениях. Процедура обнару жения считается оптимальной, если при фиксированном среднем времени между ложными тревогами запаздывание в обнаружении минимально. Хорошо изученной является задача обнаружения изменения раслределения в последовательности независимых случайных величин, для решения ко торой применяются методы скользящего среднего, например в работе Бродского Б.Е., Дарховского B.C. [6], метод экспоненциального сглаживания в работах таких авторов как Новиков А., Эргашев Б., [43, 44], Фишман М. [51], а также [70, 77] и др. Работы [55, 58, 76, 81, 86, 78] основаны на алгоритме кумулятивных сумм, предложенном Пейджем [79] и методе усредненного отношения правдоподобия Гиршика-Рубина-Ширяева [69, 58].
Среднее время запаздывания в стационарном режиме
Сравнивая полученные константы (1.7.2) и (1.7.3) с константами в соотношении (1.4.5), определенными в (1.4.9) и (1.4.10), получаем, что среднее время запаздывания в стационарном и нестационарном режимах отличаются только на постоянную величину. 1. В первой главе построена последовательная процедура обнаружения разладки последовательности независимых случайных величин с неизвестным законом распределения, основанная на поочередном использовании двух АКС, направленных на обнаружение положительного и отрицательного сдвига среднего значения наблюдаемого процесса соответственно, переключение между которыми происходит в указанные моменты времени. 2. Найдены формулы для характеристик построенной процедуры: среднего времени между ложными тревогами (1.3.12) и среднего времени запаздывания (1.3.37) и (1.3.43). Моделирование показывает хорошее совпадение практических результатов с теоретическими. 3. Проведен анализ асимптотических свойств процедуры. Получено, что среднее время между ложными тревогами растет экспоненциально, а среднее время запаздывания линейно при неограниченном возрастании порога процедуры h, что характерно для оптимальных алгоритмов обнаружения разладки в последовательности независимых случайных величин с известным распределением. 4. Проведено сравнение построенной процедуры для случая, когда распределение наблюдаемой последовательности до и после момента разладки неизвестно, с аналогичными оптимальными процедурами обнаружения в случаях, когда распределение известно. Найдены значения констант для соотношения (1.5.1). 5. Найдено среднее время запаздывания в стационарном режиме (1.6.19) и (1.7.1), когда моменту разладки предшествует длительный период наблюдений.
Нахождение характеристик процедуры для случая неизвестного распределения шумов
Поскольку а = а(1 — А), то отрицательному значению параметра А соответствует большее значение сдвига, причем, чем больше А по модулю, тем сильнее будет разница между значениями а для положительного и отрицательного значений А. Анализируя полученные результаты, можно видеть, что чем больше а, тем лучше характеристики процедуры.
Таблицы 2.6, 2.7 показывают влияния параметра а (сдвига среднего значения наблюдаемого процесса) на характеристики процедуры. Остальные параметры выбирались следующим образом: А = 0.7, 5 = 0.1, =0.1
Из таблиц 2.6, 2.7 совместно с результатами работы модифицированной процедуры, представленными в таблице 2.1, видно, что чем больше а, то есть чем больше а, тем лучше характеристики построенной процедуры. При этом не имеет значения, в каком направлении, положительном или отрицательном происходит изменение среднего. Таким образом, построенное моделирование подтверждает работоспособность и качество предложенной процедуры и показывает влияние основных ее параметров на основные характеристики: среднее время между ложными тревогами и среднее время запаздывания. 1. Во второй главе диссертационной работы предложена процедура обнаружения момента изменения среднего значения процесса авторегрессии первого порядка с неизвестными параметрами. Показано, что для решения задачи обнаружения изменения может быть применена модифицированная процедура обнаружения изменения среднего значения в последовательности независимых случайных величин, построенная в первой главе. 2. Получены формулы для нахождения характеристик построенной процедуры (среднего времени между ложными тревогами) для двух случаев: гаус-совских шумов и шумов с неизвестным законом распределения. Проведено численное моделирование, иллюстрирующее влияние параметров на значения характеристик процедуры. 3. Проведен анализ асимптотических свойств процедуры. Получено, что среднее время между ложными тревогами растет экспоненциально, а среднее время запаздывания линейно при неограниченном возрастании порога процедуры h. Обнаружение момента разладки процесса авторегрессии р—того порядка
В данной главе рассматривается задача обнаружения момента сдвига среднего значения процесса авторегрессии с неизвестными.параметрами. На первом этапе производится оценивание неизвестных (мешающих) параметров авторегрессионной части. Далее осуществляется преобразование наблюдаемого процесса с целью ослабления влияния этих параметров. Предлагается последовательная процедура обнаружения на основе алгоритма кумулятивных сумм. Получены формулы для среднего времени между ложными тревогами и среднего времени запаздывания в обнаружении разладки.
Построение процедуры обнаружения
В третьей главе построена процедура обнаружения момента изменения среднего значения процесса авторегрессии р—го порядка с неизвестными параметрами. Предложенный подход позволяет контролировать статистические свойства процедуры, связанные как с ложными тревогами, так и с запаздыванием в обнаружении разладки. 2. Найдены характеристики процедуры: среднее время между ложными тревогами и среднее время запаздывания в обнаружении. 3. Проведенное численное моделирование подтверждает работоспособность предлагаемой процедуры и иллюстрирует влияние параметров процесса на значения характеристик процедуры. В данной диссертационной работе предложены последовательные процедуры обнаружения неизвестного скачка среднего наблюдаемого процесса. Исследованы свойства построенных процедур, полученные результаты проиллюстрированы численным моделированием. Основные результаты заключаются в следующем: 1. Построена последовательная процедура обнаружения как положительного так и отрицательного скачка среднего последовательности независимых одинаково распределенных случайных величин с неизвестным законом распределения, основанная на поочередном использовании двух АКС. 2. Получены формулы для расчета основных характеристик построенной процедуры: среднего времени между ложными тревогами и среднего времени запаздывания. . 3. Проведен анализ асимптотических свойств процедуры. Показано, что среднее время между ложными тревогами растет экспоненциально, а среднее время запаздывания линейно при неограниченном возрастании порога процедуры h. 4. Произведено сравнение построенной процедуры для случая, когда распределение наблюдаемой последовательности до и после момента разладки неизвестно, с аналогичными оптимальными процедурами обнаружения в случаях, когда распределение известно. 5. Найдено среднее время запаздывания в стационарном режиме. 6. Построена последовательная процедура обнаружения разладки, исследованы свойства и получены характеристики процедуры для случая, когда наблюдаемый процесс является устойчивым процессом авторегрессии первого порядка. 7. Построена и исследована процедура обнаружения момента изменения параметров процесса авторегрессии р—того порядка. 8. Полученные теоретические результаты проиллюстрированы и подтверждены результатами численного моделирования.
