Методы и алгоритмы разведочного анализа данных, основанные на робастных модификациях боксплотов тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Андрэа Клитон

• Андрэа Клитон
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Андрэа Клитон

Содержание

Введение

1 Обзор литературы

1.1 Одномерные боксплоты

1.1.1 Классический боксплот Тьюки

1.1.2 Модификации одномерных боксплотов

1.2 Двумерные боксплоты

1.2.1 Ва§рк*

1.2.2 11аг^еАпс1ег боксплот

1.2.3 Ромбовидный двумерный боксплот

1.2.4 Ке1р1о1 и С)ие1р1о1

1.2.5 Двумерный боксплот Еаш

1.3 Аномалии в данных и методы их выявления

1.3.1 Типы аномалий

1.3.2 Методы отбраковки аномалий в одномерных данных

1.3.3 Методы отбраковки аномалий в многомерных данных

1.4 Сравнение методов отбраковки аномальных данных

2 Классические критерии качества отбраковки и Н-мера

2.1 Классические критерии сравнения методов отбраковки

2.1.1 Статистика результатов классификации

2.1.2 Сравнение классификаторов

2.2 Н-мера

2.3 Связь Н-меры с традиционными характеристиками качества классификации

2.4 Выводы

3 Одномерные робастные модификации боксплотов иа основе высокоэффективных оценок масштаба и обнаружение аномалий

3.1 Вводные замечания

3.2 Робастные оценки масштаба

3.3 Методы отбраковки по критерию Граббса

3.3.1 Метод Граббса и робастный Z-показатель

3.3.2 Правило отбраковки «А сигма»

3.4 Робастные боксплоты

3.5 Сравнительный анализ качества обнаружения выбросов в асимметричных моделях распределения данных

3.6 Засорения типа «всплеск» и методы их выявления

3.6.1 Выбор метода решения

3.6.2 Основные результаты

3.7 Выводы

4 Двумерные боксплоты

4.1 FQn — двумерный боксплот, основанный на .¿^„-оценках масштаба и коэффициента корреляции

4.2 Подбор параметров

4.3 Основные результаты

4.3.1 Воспроизведение эллиптической формы

4.3.2 Сравнительный анализ качества отбраковки аномалий в данных для FQn-боксплота и bagplot-a

4.4 Визуализация двумерного боксплота

4.5 Выводы

5 Методы отбраковки многомерных данных

5.1 Статистические методы отбраковки аномалий в многомерных данных

5.1.1 Метод Гаррета

5.1.2 PCOut

5.1.3 Методы интеллектуального анализа данных (data-mining)

5.2 Выбор метода решения

5.2.1 Метод проекций

5.2.2 Итеративный метод

5.3 Основные результаты

5.4 Выводы

6 Обнаружение аномалий в реальных данных с помощью скользящих боксплотов

6.1 Вводные замечания

6.2 Постановка задачи

6.3 Предварительная обработка данных

6.4 Скользящие боксплоты

6.5 Реализация алгоритма выявления точек разладки на R

6.6 Основные результаты

6.7 Выводы

Заключение

Список рисунков

Список таблиц

Литература

А Результаты моделирования

А.0.1 Вычисление оптимальных границ и Н-меры при засорении типа «сдвиг»

А.0.2 Экспериментальные результаты оптимальных по Н-мере

коэффициентов внешних границ боксплота Тьюки

коэффициентов внешних границ MAD-боксплота

коэффициентов внешних границ FQn-боксплота

А.0.5 Экспериментальные значения Н-меры для модели засорения Тьюки-Хьюбера одномерных данных. Степень засорения с = 0.05. Размер выборки п — 100

А.0.6 Результаты сравнения оценок моды

В Реализация алгоритмов в статистической среде программирования К

В.1 Алгоритм поиска оптимальных по Н-мере значений коэффициентов внешних границ боксплотов

В.2 Алгоритм построения БС)П боксплота

В.З Алгоритм скользящего боксплота для выявления точки разладки

Введение диссертации (часть автореферата) на тему «Методы и алгоритмы разведочного анализа данных, основанные на робастных модификациях боксплотов»

Введение

Актуальность работы. Разведочный анализ данных (РАД; Exploratory data analysis) - относительно новый раздел статистики, появление которого связано с развитием вычислительной аппаратуры и автоматизацией вычислений, сделавших возможным графическое представление больших объемов данных. Многие методы, лежащие в основе разведочного анализа данных, были известны задолго до появления работы Дж. Тьюки (J. W. Tukey) в 1977 году [1], по которой и был назван этот раздел статистики. Вместе с Дж. Тьюки свой вклад в развитие и в формирование РАД внесли Ф. Мостеллер (F. Mosteller) [2], Д. Хоаглин (D. Hoaglin), П. Веллеман (P. Velleman) [3]. В российской литературе этот раздел статистики был дополнен трудами С. А. Айвазяна, В. М. Бухштабера, И. С. Енюкова и JI. Д. Мешалкина [4-6]. Хотя и не существует строгого (точного) определения термина «разведочный анализ данных», основное назначение РАД заключается в следующем:

• Максимальное «проникновение в данные»;

• Выявление основных структур данных;

• Обнаружение отклонений и аномалий в данных;

• Проверка основных гипотез о распределении данных;

• Разработка начальных моделей распределений данных.

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

Возможность сбора и хранения больших объемов информации в настоящее время требует применения эффективных методов первичного анализа и под-

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

В задачах статистической классификации оценка качества классификации связана со значениями критерия мощности и вероятности ложной тревоги согласно подходу Неймана-Пирсона. Проведение сравнения качества классификации исследуемых методов по двум параметрам затруднительно. Согласно подходу Неймана-Пирсона, для сравнения качества классификации разных методов необходимо обеспечить стабильно низкий уровень вероятности ложной тревоги. Такое требование автоматически позволяет сравнивать лишь оценки критерия мощности для того, чтобы интерпретировать полученные результаты, однако на практике по разным причинам не удается обеспечить одинаково стабильный уровень ложной тревоги одновременно для всех исследуемых методов. В задачах информационного поиска (Information Retrieval) одним из критериев оценки качества классификации является F-мера, комбинирующая оценку полноты (recall) и точности (precision). Но в литературе до сих пор нет исследований статистических методов классификации, оценка качества классификации которых являлась бы комбинацией критерия мощности и вероятности ложной тревоги. В данной работе вводится новая мера качества классификации Н-мера, с помощью которой проводится сравнение улучшенных и новых предложенных методов для одномерных, двумерных и многомерных данных.

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

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

Методы исследования. В работе использованы методы теории вероятностей, математической статистики, методы оптимизации и статистические методы, а также технологии параллельных и распределенных вычислений. Моделирование данных методом Монте-Карло позволило экспериментально проверить теоретически обоснованные алгоритмы. Для реализации алгоритмов использована статистическая среда программирования Я.

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

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

2. Исследовать и сравнить качество различных методов отбраковки аномальных значений данных.

3. Построить и исследовать двумерный боксплот на основе быстрых высокоэффективных робастных оценок масштаба и провести сравнение двумерных боксплотов.

4. Применить предложенный двумерный боксплот для обнаружения аномалий в многомерных данных.

5. Разработать программный комплекс, реализующий:

• алгоритмы вычисления критериев качества отбраковки аномалий в данных;

• алгоритмы визуализации на основе предложенных новых методов отбраковки аномальных данных;

• алгоритмы отбраковки аномалий в данных.

6. Применить предложенные методы к отбраковке реальных данных.

Основные положения, выносимые на защиту:

1. Оценка качества отбраковки аномалий в данных в виде Н-меры, ее свойства и интерпретация в терминах критериев мощности и вероятности ложной тревоги.

2. Выявление аномалий в данных робастными версиями одномерных бокс-плотов, основанных на высокоэффективных оценках параметра масштаба по Н-мере.

3. Двумерный РС)7г-боксплот: алгоритм построения; подбор параметров с помощью Н-меры. Сравнительный анализ воспроизведения эллиптической формы БС)п-боксгаютом и другими двумерными боксплотами. Выявление аномалий на плоскости применением РС>п-боксплота и сравнение с остальными двумерными методами. Визуализация данных с использованием БС)п-боксплота.

4. Многомерные методы выявления аномалий в данных и их сравнение по Н-мере. Использование двумерных боксплотов для выявления аномалий в многомерных данных.

5. Разработка алгоритмов для обнаружения точек разладки временных рядов.

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

Научная новизна:

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

2. Разработаны и исследованы новые модификации классических одномерных боксплотов Тьюки, основанные на робастных высокоэффективных оценках параметра масштаба.

3. Впервые исследован тип засорения «всплеск» и предложен метод спей-сингов для его отбраковки.

4. Предложен новый двумерный боксплот, ориентированный на отбраковку аномалий и визуализацию двумерных данных, распределенных по нормальному закону.

5. Разработаны методы отбраковки аномалий в многомерных данных, основанные на предложенном двумерном FQn-60Kcrai0Te.

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

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

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях:

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

• Симпозиум НЕПАРАМЕТРИКА - XIV, Томск, 1 - 3 июля 2012.

• Международная конференция по робастной статистике (International Conference on Robust Statistics - ICORS '11).

• 2013 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP).

• Международная конференция по робастной статистике (International Conference on Robust Statistics - ICORS '13).

• 10th International Conference on Computer Data Analysis & Modeling 2013 (CDAM ' 13).

Публикации. Основные результаты по теме диссертации изложены в 6 печатных изданиях [7-12], 2 из которых изданы в журналах, рекомендованных

ВАК [9,12], 4 — в тезисах и трудах российских и международных конференций [7,8,10,11].

Объем и структура работы. Диссертация состоит из введения, шести глав, заключения и двух приложений. Полный объем диссертации составляет 164 страницы с 60 рисунками и 22 таблицами. Список литературы содержит 88 наименований.

Глава 1

Обзор литературы

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

1.1 Одномерные боксплоты

Одним из эффективных и наиболее наглядных способов графического представления данных в статистике является боксплот (Ьохр1о1). До сегодняшнего дня в русскоязычных источниках не существует устоявшегося термина для определения боксплотов. Различные сайты и форумы, посвященные статистической обработке данных, предлагают огромное количество вариантов перевода термина ЬохрЫ на русский язык. В большинстве случаев используют термин боксплот, а также ящик с усами и коробчатая диаграмма (график). В единичных случаях описанные диаграммы именуются ящичковыми диаграммами, коробами с усами, ящиковыми графиками, диаграммами размаха и

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

1.1.1 Классический боксплот Тьюки

Одномерный боксплот был предложен Дж. Тьюки в 1977 г. [1] и до сегодняшнего дня считается очень удобным средством описания распределений одномерных данных, так как он предоставляет информацию о параметрах положения, масштаба, асимметрии, - хвостах и выбросах распределения, более того, на данный момент он доступен для использования в различных статистических пакетах. Первоначальный вариант построения боксплотов, предложенный Дж. Тьюки [1], использует 5-числовые сводки.

5-числовая сводка - это 5 чисел, которые характеризуют рассматриваемую выборку:

• крайние значения выборки х^ и х(п), где х^ - 1-я порядковая статистика

• выборочная медиана

Использование именно этих характеристик обусловлено быстротой и простотой подсчета, а также более очевидным способом сравнения различных выборок в случае, когда анализируются лишь эти характеристики. Одномерный боксплот на Рис. 1.1 состоит из внутренней области, усов и выбросов. Внутренняя область представляет собой коробку с границами, равными нижним и верхним квартилям, которая содержит 50% центральных значений выборки, то есть ближайших к выборочной медиане. Внутренняя часть этой коробки

п = 2к + 1

п = 2 к

(1.1)

• нижний и верхний выборочные квартили:

Щ = Я([„/4]). = Ж(п_[а]+1)

(1.2)

известна как интерквартильная область (1(^11) и определяется следующим образом:

= (1.3)

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

3

хь = тах{х(1), ЬС2 -

3

хи = т1п{х(п),и(2 +-ЩЛ} (1.4)

^ Выброс Хи

Верхний квартило Медиана

Нижний нваотило XI

Рис. 1.1: Построение боксплота

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

1.1.2 Модификации одномерных боксплотов

В работе [13] предложена модификация боксплота, позволяющая включить — в графическое представление информацию о плотности распределения дан-

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

На базе боксплота, в графической структуре которого отображена информация о плотности распределения, были, в свою очередь, разработаны другие виды боксплотов [14-16].

Notched (зазубренный) боксплот

Боксплот [17], графическое представление которого содержит информацию о доверительном интервале параметра сдвига, - медиане (1.1) - что обеспечивает возможность сравнения качества оценки медианы нескольких выборок.

\

/_J Z1A

W (

>-< Г

v

С

-гт:—н-з—xrzr-—«3-с——пз-п—-г~

Y « г s Lived in Chicago

Рис. 1.2: Зазубренные боксплоты.

Histplot

Данная модификация боксплота [14] основывается на упрощенном подходе отображения плотности распределения. Оценка плотности распределения проводится по трем точкам: по медиане и по двум квартилям. Ширина коробки меняется прямо пропорционально значениям оценки плотности распределения. Прямоугольная коробчатая конструкция превращается в объединение двух трапеций с общим большим основанием (см. Рис. 1.3).

о

Рис. 1.3: Histplot

Vaseplot

Нл81р1о! [14] выявляет важные характеристики модели распределения по трем главным квантилям генеральной выборки. Необходимость расширить возможности визуализации такого боксплота обусловлена риском пропустить отличные от квантилей области с наивысшей плотностью распределения. Уазер1о1 является более утонченной версией №з1р1о1:-а. Информация о плотности распределения в Уазер1о^е отображается на всем диапазоне от нижнего до верхнего квартиля (см. Рис. 1.4).

Percentile боксплот

Percentile боксплот [18] отображает информацию об эмпирической функции распределения для всех процентных точек распределения. Vaseplot пред-

Рис. 1.4: Vaseplot

ставляет собой урезанную версию percentile боксплота, так как ограничивается отображением лишь 50% центральных данных. Percentile боксплот отличается от Vaseplot-a не только диапазоном визуализации данных, но и способом вычисления оценок распределения выборки. На каждой точке до медианы вычисляются значения процентных точек. Начиная с медианы ширине бокс-плота присваиваются значения разности расстояния от процентной точки до единицы. Значения квартилей и медианы отмечаются поперечными линиями. Стороны percentile боксплота симметричны.

Рис. 1.5: Варианты боксплотов, включающие информацию о плотности распределения а) Перцентильный боксплот б) Violinplot

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

1.2 Двумерные боксплоты

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

I

а)

б)

В этом разделе описываются некоторые варианты двумерных боксплотов. Основное внимание уделяется bagplot, несмотря на более позднее его появление.

1.2.1 Е^рШ

Ва§р1о1:-ы, предложены в работе [19]. Они также состоят из внутренней, внешней областей и выбросов. Для построения 1^р1о1-а используется понятие глубины полупространства.

Глубина полупространства МерЬН(9. Z) [20] в некоторой точке в - это наименьшее значение г^ из Z — 21, г2,.... гп, содержащееся в любой замкнутой полуплоскости, граница которой проходит через в.

Эффективный алгоритм, реализующий функцию МерИг(6, 2), был предложен авторами работы [19].

I 1 I I

98 100 102 104

Рис. 1.6: Bagplot

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

Внешняя область

Медиана Тьюни

область (50% точек)

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

1.2.2 Rangefinder боксплот

Простейшим вариантом двумерного боксплота является Rangefmder бокс-плот, который был предложен в работе [21]. В этом случае 5-числовые сводки рассчитываются для выборки по каждой переменной. На границах графика изображаются прямые линии вдоль интерквартильной области для каждой переменной (как в одномерном случае). Пересечением двух центральных линий является перекрестное среднее значение.

На Рис. 1.7 представлен Rangefinder boxplot, пример реализации которого был взят из работы [22]. Данные, которые использовались при построении указанного Rangefinder боксплота, являются подмножеством данных экономии топлива ЕРА (U.S. Environmental Protection Agency) и на Рис. 1.7 отображается отношение пройденных магистральных миль на галлон топлива от пройденных городских миль на галлон топлива.

о т

Ol

Э- о

t гг1

f? J

Ol (м

X

о оо

ООО ООО

о

с»-

о -е-

о о о о о о о о о о о

о

ООО О О О с> О О о о оо о о о о

ООО ООО О i)0 О О

о < о < оо < о ®о с

10

~г-

15

-г~

20

~~Г"

25

~Г"

30

—Г

35

40

Citv mpg

Рис. 1.7: Rangeflnder боксплот

Rangeflnder ЬохрЫ является довольно простой реализацией двумерного боксплота, однако имеет неоспоримый минус - он не отображает корреляцию между переменными. Другой подход к построению боксплотов подразумевает

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

1.2.3 Ромбовидный двумерный боксплот

В работе Tongkumchum [23] предложен двумерный боксплот, ромбовидная структура которого отражает величину коэффициента корреляции. Основная идея этого двумерного боксплота (см. Рис. 1.8) заключается в построении ро-бастной (устойчивой) прямой, которое происходит следующим образом:

Обозначим точки данных как (xf, yi)

1. Все точки разбиваются на три не пересекающихся по оси Ох области таким образом, чтобы все области содержали приблизительно равное количество элементов.

2. Вычисляются медианы значений по оси Ох и Oy во внешних областях, {%в,Ув) и (хт,ут) соответственно.

3. Наклон линии (6), соединяющей точки (хв-,ув) и (%т-,Ут)> вычисляется следующим образом:

Ъ = (Ут- ув)/{хт - хв)

4. Конец линии (а) рассчитывается как

а - med (jji — bxi)

5. Таким образом, робастная линия имеет следующее представление

у'(х) = а + Ьх

Внутренняя область состоит из 50% центральных значений проекций данных на робастную линию. Линии квартилей и внешней области рисуются па-

У А

о

о

(О, 0) X

Рис. 1.8: Ромбовидный двумерный боксплот

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

1.2.4 ЬЫрЫ и <2ие1р1о1

В работе [24] были предложены два способа построения двумерных бокс-плотов, которые носят названия ге1р1о1 и quelplot. Оба способа основываются на том, что оптимальным доверительным интервалом для двумерного нормального распределения является эллипс. Поэтому для построения двумерного обобщения боксплотов используют эллипсы, которые, кроме того, наилучшим образом учитывают симметрию данных.

Яе1р1о1 представляет собой робастный эллиптический график, то есть использует концентрические эллипсы полностью. При построении ге1р1о1 используется робастная оценочная функция, варианты которой подробно описаны в [24]. В качестве примера, на Рис. 1.9 приведен ге1р1о^ построенный для данных из работы [25]. Выборка представляет собой возраст и заработную плату (в фунтах) 375 опрошенных студентов и выпускников Института инженеров-электриков в Великобритании на 1974 год.

С)ие1р1о1 использует так называемые дие1-и для обеспечения непрерывности и гладкости на всем графике. С>ие1-и представляют собой четверти эллипсов, соответствующие их большим и малым полуосям. Как и в предыдущих

tn T>

с о

СП

Э

о

SI I—

£• о о t/1

20 25 30 35

Age (Years)

Рис. 1.9: Relplot: возраст и заработная плата (в фунтах) 375 опрошенных студентов и выпускников Института инженеров-электриков на 1974 год.

вариантах, внутренняя область содержит 50% центральных значений, а граница внешней области отделяет потенциальные выбросы. Местоположение и размеры обозначаются пересекающимися отрезками на больших и малых полуосях эллипсов. На Рис. 1.10 приведен пример quelplot-a для выборки, которая рассматривалась в случае replot-a.

1.2.5 Двумерный боксплот Zani

Более эффективный в вычислительном отношении вариант двумерного боксплота представлен в работе [26]. Внутренняя область для данного бокс-плота строится путем последовательного отслаивания выпуклых оболочек с целью получить конечный вид центральной части данных. Обозначим за (1 - а)%-оболочку наибольшую оболочку, содержащую не более (1 - а)% данных (при этом точки на границе оболочки принадлежат этому множеству). Обычно даже если наиболее удаленные оболочки принимают различные формы и подвержены влиянию выбросов, 50%-оболочка в состоянии показать наличие корреляции двух переменных. В случае, когда выборка мала, 50%-оболочка может не быть гладкой. Во избежание этого авторы предлагают использовать 50%-оболочку, построенную с использованием кривой В-сплайна. В-сплайн представляет собой кубическую гладкую кривую, то есть кривую

Relplot

-1—1—1—1—1—г

г

о

20 25 30 35

Age (Years)

Рис. 1.10: Quelplot: возраст и заработная плата (в фунтах) 375 опрошенных студентов и выпускников Института инженеров-электриков на 1974 год.

с непрерывными старшими производными до n-ой степени, составленную из дуг полиномов третьей степени, где п - порядок сплайна. Отсюда следует, что внутренняя область есть та, которая была образована точками, лежащими внутри и на границе кривой В-сплайна, нанесенного на 50%-оболочку. Центр двумерного боксплота может быть найден как центр внутренней оболочки, или пересечение линий регрессий. Другой вариант нахождения центра - с помощью критерия минимизации нормы М)- Также центром мож-

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

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

Т-1-1--|—--1-г1

2 4 6 8 10 12

Percentage of infant population

Рис. 1.11: Двумерный боксплот Zani: количество семей (в процентах) с одним

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

1.3 Аномалии в данных и методы их выявления

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

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

Причины пронумерованы в соответствии с вероятностью их воздействия: наиболее вероятной причиной является персонал, наименее вероятной - оборудование. В каждой категории также выделено несколько причин второго уровня, которые более подробно описывают возможные ситуации. Так, например, в категории «персонал» определено две причины второго уровня: непреднамеренные ошибки, которые могут возникать на этапах наблюдения процесса, измерения величин, регистрации и ввода данных и заведомо неверная регистрация данных. Следует отметить, что это наиболее вероятные причины появления выбросов по мнению авторов [27]. Весь диапазон возможных причин появления выбросов значительно шире представленного и анализ следует проводить в каждом случае индивидуально.

Список литературы диссертационного исследования кандидат наук Андрэа Клитон, 2013 год

Литература

1. Tukey J. W. Exploratory Data Analysis. Reading, MA: Addison-Wesley, 1977.

2. Mosteller F., Tukey J. W. Data Analysis and Regression. 1977.

3. Velleman R, Hoaglin D. The ABC's of EDA: Applications, Basics, and Computing of Exploratory Data Analysis. Duxbury Press, 1981. P. 354.

4. Прикладная статистика: Основы моделирования и первичная обработка данных / С.А. Айвазян, В.М. Бухштабер, И.С. Енюков [и др.]. Москва: Финансы и статистика, 1983.

5. Прикладная статистика: Исследование зависимостей / С.А. Айвазян,

B.М. Бухштабер, И.С. Енюков [и др.]. Москва: Финансы и статистика, 1985.

6. Прикладная статистика: Классификация и снижение размерности /

C.А. Айвазян, В.М. Бухштабер, И.С. Енюков [и др.]. Москва: Финансы и статистика, 1989.

7. Fast low-complexity bivariate boxplots based on highly efficient and robust estimates of dispersion and correlation / G. Shevlyakov, K. Andrea, G. Lavren-tyeva et al. // ICORS' 11. 2011.

8. Визуализация данных двумерными FQn-боксплотами / К. Андреа, Г.М. Лаврентьева, П. О. Смирнов [и др.] // Высокие технологии, образование, промышленность. Сборник трудов. Под редакцией А. П. Кудинова. 2011.

9. Андреа К., Смирнов П. О., Шевляков Г. Л. Двумерный боксплот на основе высокоэффективных робастных оценок масштаба и корреляции // Вест-

ник Томского Государственного Университета. Управление, вычислительная техника и информатика. 2013. Т. 22, № 1. С. 25-31.

10. Robust versions of the Tukey boxplots with their application to detection of outliers / G. Shevlyakov, K. Andrea, C. Lakshminarayan et al. // ICASSP' 13. 2013.

11. Andrea K., Shevlyakov G.L., Smirnov P.O. Detection of outliers with boxplots // Computer Data Analysis and Modeling: Theoretical and Applied Stochastics: Proc. of the Tenth Intern. Conf. / Belarussian State University. Т. 1. Publishing Center of BSU, 2013. September. C. 141-144.

12. Андреа К., Шевляков Г. JI. Обнаружение выбросов с помощью бокспло-тов, основанных на новых высокоэффективных робастных оценках масштаба // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. Информатика. Телекоммуникации. Управление. 2013. Т. 5, № 181. С. 39^15.

13. Methods for Presenting Statistical Information: The Box Plot / K. Potter, H. Hagen, A. Kerren et al. // Visualization of Large and Unstructured Data Sets. 2006. Vol. S-4. P. 97-106.

14. Benjamini Y. Opening the Box of a Boxplot // The American Statistician. 1988. Vol. 42, no. 4. P. 257-262.

15. Warren W. E., Banfield J. D. The Box-Percentile Plot // Journal of Statistical Software. 2003. 10. Vol. 8, no. 17. P. 1-14.

16. Hintze J. L., Nelson R. D. Violin Plots: A Box Plot-Density Trace Synergism // The American Statistician. 1998. Vol. 52, no. 2. P. 181-184.

17. McGill R., Tukey J. W., Larsen W. A. Variations of box plots // The American Statistician. 1978. Vol. 32. P. 12-16.

18. Esty W. W., Banfield J. D. The Box-Percentile Plot // Journal of Statistical Software. 2003. Vol. 8, no. 17. P. 1-14.

19. Rousseeuw P. J., Ruts I., Tukey J. W. The bagplot, a bivariate boxplot // The American Statistician. 1999. Vol. 53. P. 382-387.

20. Donoho D. L., Gasko M. Breakdown properties of location estimates based on halfspace depth and projected outlyingness // The Annals of Statistics. 1992. Vol. 20, no. 4. P. 1803-1827.

21. Becketti S., Gould W. Rangefinder Box plots: A note // The American Statistician. 1987. Vol. 149, no. 41. P. 149-149.

22. Stryjewski L. "40 years of boxplots-// The American Statistician. 2010.

23. Tongkumchum P. Two-dimensional box plot // Songklanakarin J. Sci. Technol. 2005. Vol. 27, no. 4. P. 859-866.

24. Goldberg К. M., Iglewicz B. Bivariate extensions of the boxplot // Technomet-rics. 1992. Vol. 34. P. 307-320.

25. Barnett V., Lewis T. Outliers in statistical data. Wiley series in probability and mathematical statistics: Applied probability and statistics. Wiley & Sons, 1994.

26. Zani S., Riani M., Corbellini A. Robust bivariate boxplots and multiple outlier detection // Computational Statistics & Data Analysis. 1998. September. Vol. 28, no. 3. P. 257-270.

27. Выбросы. Часть 2: как возникают выбросы? // Six Sigma online. 2012.

28. Pearson Ronald K. Mining imperfect data: dealing with contamination and incomplete records. SIAM, 2005. C. 305.

29. Grubbs F. E. Procedures for Detecting Outlying Observations in Samples // Technometrics. 1969. 2. Vol. 11, no. 1. P. 1-21.

30. Hawkins D. Identification of Outliers. London: Chapman and Hall, 1980.

31. Johnson R. Applied Multivariate Statistical Analysis. Prentice Hall, 1992.

32. Knorr E. M., Ng R. T. Finding Intesional Knowledge of Distance-Based Outliers. VLDB Conference. 1999.

33. Aggarwal С. C., Yu P. S. Outlier detection in High Dimensional Data. ACM SIGMOD Conference. 2001.

34. Aggarwal Charu C. Outlier Analysis. New York: Springer, 2013. C. 446.

35. Iglewicz В., Hoaglin D. How to detect and handle outliers. ASQC Quality Press (Milwaukee, Wis.), 1993. C. 87.

36. Grubbs F. E., Beck G. Extension of sample sizes and percentage points for significance tests of outlying observations // Technometrics. 1972. Vol. 14, no. 4. P. 847-854.

37. Лемешко Б. Ю., Лемешко С. Б. Расширение области применения критериев типа Граббса, используемых при отбраковке аномальных измерений // Измерительная техника. 2005. № 6.

38. Rosner В. Percentage points for a generalized ESD many-outlier procedure // Technometrics. 1983. Vol. 25, no. 2. P. 165-172.

39. Willems G., Joe H., Zamar R. Diagnosing multivariate outliers detected by robust estimators // Journal of Computational and Graphical Statistics. 2009. Vol. 18, no. 1. P. 73-91.

40. Rousseeuw P. G., Zomeren V. Unmasking multivariate outliers and leverage points // Journal of the American Statistical Association. 1990. Vol. 85, no. 411. P. 633-651.

41. Hubert Mia, Rousseeuw Peter J., Verdonck Tim. A DETERMINISTIC ALGORITHM FOR THE MCD: Tech. Rep.: TR-10-01: KATHOLIEKE UNIVERSITEIT LEUVEN, 2010. URL: http://wis.kuleuven.be/stat/.

42. Rousseeuw P.J., Leroy A.M. Robust Regression and Outlier Detection. Wiley Series in Probability and Statistics. New York: Wiley, 1987. URL: http://books.google.com/books?id=woaH_73s-MwC.

43. Davies P. Asymptotic behaviour of S-estimates of multivariate location parameters and dispersion matrices // The Annals of Statistics. 1987. Vol. 15, no. 3. P. 1269-1292.

44. Friedman J. H., Tukey J. W. A Projection Pursuit Algorithm for Exploratory Data Analysis // IEEE Transactions on Computers. 1974. Vol. 23, no. 9. P. 881-890.

45..- Кендалл M., Стьюарт А. Статистические выводы и связи. Москва: Наука.

46. Marzban С. The ROC Curve and the Area Under it as a Performance Measure // Weather and Forecasting. 2004. Vol. 19, no. 6. P. 1106-1114.

47. Satchell S., Xia W. Analytic Models of the ROC Curve: Applications to Credit Rating Model Validation // The analytics of risk model validation / под ред. G. Christodoulakis, S. Satchell. London: Academic Press.

48. Faraggi D., Reiser B. Estimation of the area under the ROC curve // Statistics in Medicine. 2002. Vol. 21, no. 20. P. 3093-3106.

49. van Rijsbergen C. J. Information Retrieval. London: Butterworths, 1979.

50. Fawcett T. ROC graphs: Notes and practical considerations for data mining researchers: Tech. Rep.: HPL-2003-4. Palo Alto, CA, USA: HP Laboratories, 2003.

51. Huber P. J. Robust Statistics. Wiley series in probability and mathematical statistics. Probability and mathematical statistics. John Wiley & Sons, 1981.

52. Robust statistics: the approach based on influence functions / F. R. Hampel, E. M. Ronchetti, P. J. Rousseeuw et al. Wiley series in probability and mathematical statistics. Probability and mathematical statistics. Wiley, 1986.

53. Donoho D. L., Huber P. J. The notion of breakdown point // A Festschrift for Erich L. Lehmann in Honor of His Sixty-fifth Birthday / Ed. by P. J. Bickel, K. A. Doksum, J. L. Hodges. Statistics Probability Series. Belmont, CA: Wadsworth, 1983. P. 157-184.

54. Jureckova J., Picek J. Robust statistical methods with R. FL, USA: Chapman & Hall, 2005.

55. Rousseeuw P. J., Croux C. Alternatives to the Median Absolute Deviation // Journal of the American Statistical Association. 1993. Vol. 88, no. 424. P. 1273-1283.

56. Shevlyakov G. L., Smirnov P. O. On Approximation of the Qn — estimate of Scale by Fast M — estimates II Int. Conf. on Robust Statistics. Parma, Italy: 2010.

57. Box G., Cox D. An analysis of transformations // Journal of the Royal Statistical Society. 1964. Vol. Series B, no. 26. P. 211-252.

58. Applied Linear Statistical Models / M. Kutner, C. Nachtsheim, J. Neter [h pp.]. Homewood, IL: McGraw Hill/Irwin, 2004.

59. Kimber A. C. Exploratory data analysis for possibly censored data from skewed distributions//Applied Statistics. 1990. Vol. 11, no. 1. P. 21-30.

60. Hubert M., Vandervieren E. An adjusted boxplot for skewed distributions // Computational Statistics & Data Analysis. 2008. Vol. 52, no. 12. P. 51865201.

61. Grenander U. Some direct estimates of the mode // The Annals of Mathematical Statistics. 1965. no. 36. P. 131-138.

62. Shevlyakov G. L., Vilchevski N. O. Robustness in data analysis: criteria and methods. Modern Probability and Statistics. Walter de Gruyter, 2001.

63. Masse J.-C., Plante J.-F. A Monte Carlo study of the accuracy and robustness often bivariate location estimators // Computational Statistics & Data Analysis. 2003. Vol. 42. P. 1-26.

64. Liu R. On a notion of data depth based on random simplices // Ann. Statist. 1990. Vol. 18. P. 405-414.

65. Oja H. Descriptive statistics for multivariate distributions // Statistical Probability Letters. 1983. Vol. 1. P. 327-332.

66. Small C. A survey of multidimensional medians // International Statistical Review. 1990. Vol. 58. P. 263-277.

67. Chakraborty B., Chaudhuri P. A note on the robustness of multivariate medians // Statistics & Probability Letters. 1999. Vol. 45. P. 269-276.

68. Vardi Y., Zhang C.-H. The multivariate LI-median and associated data depth // Proceedings of the National Academy of Sciences of the United States of America. 2000. Vol. 97, no. 4. P. 1423-1426.

69. Shevlyakov G., Smirnov P. Robust Estimation of the Correlation Coefficient: An Attempt of Survey // Austrian Journal of Statistics. 2011. Vol. 40, no. 1,2. P. 147-156.

70. Garret R. G. The chi-square plot: A tool for multivariate outlier recognition // Journal of Geochemical Exploration. 1989. Vol. 32, no. 1-3. P. 319 - 341.

71. Filzmoser P. A multivariate outlier detection method // Proceedings of the Seventh International Conference on Computer Data Analysis and Modeling / Ed. by S. Aivazian, P. Filzmoser, Y. Kharin; Belarusian State University. Vol. 1. Minsk: 2004. P. 18-22.

72. Filzmoser P., Maronna R., Werner M. Outlier identification in high dimensions // Computational Statistics & Data Analysis. 2008. Vol. 52, no. 3. P. 1694-1711.

73. Pena D., Prieto F. J. Multivariate Outlier Detection and Robust Covariance Matrix Estimation//TECHNOMETRICS. 2001. Vol. 43, no. 3. P. 135-149.

74. Rocke D. M., Woodruff D. L. Identification of Outliers in Multivariate Data // Journal of the American Statistical Association. 1996. Vol. 91, no. 435. P. 1047-1061.

75. Knorr E. M., Ng R. T. Distance-based outliers: algorithms and applications // The International Journal on Very Large Data Bases. 1998. Vol. 8. P. 237-253.

76. Knorr E. M., Ng R. T. Algorithms for mining distance-based outliers in large datasets. Proc. 24th Int. Conf. Very Large Data Bases (VLDB). 1998. P. 392403.

77. Acuna E., Rodriguez C. Meta analysis study of outlier detection methods in classification: Tech. Rep.: Mayaguez, Puerto Rico 00680: Department of Mathematics, University of Puerto Rico at Mayaguez, 2004.

78. Ramaswamy S., Rastogi R., Shim K. Efficient algorithms for mining outliers from large data sets // SIGMOD Rec. New York, NY, USA, 2000. may. Vol. 29, no. 2. P. 427^138. URL: http://doi.acm.org/10.1145/335191.335437.

79. Kaufman L., Rousseeuw P. J. Finding Groups in Data: An Introduction to Cluster Analysis. New York: Wiley, 1990.

80. Daniel Barbara, Chen Ping. Using the fractal dimension to cluster datasets // Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining. KDD '00. New York, NY, USA: ACM, 2000. C. 260-264.

81. A density-based algorithm for discovering clusters in large spatial databases with noise. / M. Ester, H.-P. Kriegel, J. Sander et al. // KDD. 1996. Vol. 96. P. 226-231.

82. Kriminger E., Principe J., Lakshminarayan C. Mixture of designer experts for multi-regime detection in streaming data // Signal Processing Conference (EU-SIPCO), 2012 Proceedings of the 20th European. 2012. P. 410^114.

83. Kriminger E., Principe J., Lakshminarayan C. Nearest Neighbor Distributions for imbalanced classification // Neural Networks (IJCNN), The 2012 International Joint Conference on. 2012. P. 1-5.

84. Lakshminarayan Choudur, Alvarado Alexander Singh, Principe Jose C. [и др.]. Anomaly detection in streaming data. 2013. 04. URL: http://www.patentlens.net/patentlens/patent/US_7062320.

85. Real Life Data Statistical Analysis: Time Series Processing and Anomaly Detection: Tech. Rep.: / G. L. Shevlyakov, K. Andrea, C. Lakshminarayan et al.: HP Labs Project Report, 2012.

86. Магнус Я. P., Катышев П. К., Пересецкий А. А. Эконометрика. Москва.

87. Chandola V., Banerjee A., Kumar V. Anomaly detection: A survey // ACM Comput. Surv. New York, NY, USA, 2009. Vol. 41, no. 3. P. 1-58. URL: http://d0i.acm.0rg/l 0.1145/1541880.1541882.

88. Прыткова А. В. Сравнительный анализ эффективности применения статистических и нейронных алгоритмов для решения задачи разладки во временных рядах: Магистерская диссертация: Санкт-Петербургский государственный политехнический университет. 2013.