Тема: Кластеризация временных рядов

В связи с ростом вычислительных мощностей и возможностей со­бирать и хранить данные, одна из наиболее актуальных областей совре­менного мира — это анализ данных. Активное развитие получили методы машинного обучения, так как они способны «учиться» на тестовых данных и призваны решать самые разнообразные задачи: классификация данных, прогнозирование (в частности, построение регрессионной модели), класте­ризация, поиск аномалий и др. Люди всегда стремились предсказывать будущее или поведение других людей по имеющимся данным, особенно актуальна эта задача в области страхования и финансов. Однако сегодня методы машинного обучения используются в диагностике заболеваний, при изучении био-физических особенностей организма, в распознавании изоб­ражений и речи, автоматизации труда и т.д.
Наиболее сложными являются методы, которые работают «без учи­теля». В таких задачах нет тестовой выборки, по которой можно подо­брать параметры или проверить результат. Кластеризация данных отно­сится именно к этой группе. Задача состоит в распределении объектов (дан­ных) по группам таким образом, чтобы внутри каждой группы оказались объекты, обладающие высокой степенью сходства в некотором отношении, которое является принципиально важным для рассматриваемой задачи, а между различными группами обнаруживались бы существенные разли­чия. Для выделения кластеров используются только сами данные, количе­ство кластеров является неизвестной величиной. Процедура распределения по кластерам (подход) может проходить по разному. Здесь выделяют ве­роятностные, теоретико-графовые, иерархические, нечеткие подходы, эта классификация условная, существуют и другие алгоритмы. Результат бу­дет зависеть не только от выбора подхода, но и от способа определения количества кластеров и выбора метрики.
Работа посвящена кластерному анализу временных рядов, который выделен из общей задачи кластеризации в связи с тем, что даннвхе зави­сят от времени. Это требует подбора специалвнвхх метрик, учитвхвающих временнвхе особенности. Ввхбор темвх обусловлен не толвко ее актуальноствю, но и наличием практической задачи, рассмотрение которой также приводится в работе. Постановка проблемах и данные предоставлены меди­цинским информационно-аналитическим центром.
В области кластеризации временных рядов была проделана боль­шая работа: описано применение алгоритма динамической трансформа­ции шкалы в кластерном анализе [1], [2]; этот же алгоритм, но с помо­щью теории скрытых марковских моделей предложен в [3]; использование коэффициентов автокорреляции, спектральных характеристик, вейвлет- коэффициентов отмечено в работах [4], [5], более полный обзор существу­ющих методов представлен в статье [6].
В первой главе дан обзор существующих метрик и приведено опи­сание новой метрики, разработанной для кластеризации коротких времен­ных рядов. Во второй главе показан кластерный анализ районов Санкт- Петербурга по показателю заболеваемости с 1999 по 2014 гг., получено несколько моделей, по которым построены стабильные кластеры. В том числе, рассмотрен многомерный анализ. В третьей главе рассмотрен метод работы с объектами, которые потенциально могут относиться к нескольким кластерам, работа алгоритма показана на примере детской заболеваемости.
Купить

Задача кластеризации временных рядов выделена отдельно в свя­зи с тем, что применение классических метрик приводит к потере важных корреляций между наблюдениями. Чтобы определить являются ли вре­менные рядвх схожими, нужно учитвхватв не толвко их геометрическую отдаленноств, но и характер динамики и изменчивости ряда. В области поиска нужнвхх метрик проделана болвшая работа, описание наиболее ис- полвзуемвхх расстояний представлено в Главе 1. Эти методах показывают хорошие результаты при кластеризации больших данных, однако на корот­ких временных рядах они работают хуже. В связи с этим предложена новая метрика для кластеризации временных рядов, которая находит расстояние между характеристиками ряда (геометрическими, динамическими и харак­теристиками изменчивости). Эксперименты на искусственных и реальных данных показывают целесообразность использования алгоритма.
В следующем разделе представлено применение методов кластерно­го анализа временных рядов в решении прикладной задачи. Медицинским информационно - аналитическим центром предоставлены данные по забо­леваемости жителей Санкт-Петербурга в возрастной разбивке: дети (до 14 лет), подростки (15-17 лет), взрослые (старше 18 лет) за период с 1999 по 2014 гг. Стоит вопрос являются ли районы города схожими относитель­но изменения показателя заболеваемости. В работе представлен анализ как одномерных временных рядов, так и многомерных. Задача многомер­ной кластеризации временных рядов является особенно сложной. Методы условно делятся на два подхода: алгоритмы первой группы учитывают кор­реляции между переменными, но являются сложными для интерпретации, большая часть из них основана на методе главных компонент; алгоритмы второй группы агрегируют информацию, которая получена при кластери­зации каждой переменной отдельно.
Применение разных метрик и подходов кластеризации приводит к противоречивым резулвтатам, поэтому в Главе 2 получена карта «стабиль­ных» кластеров, то еств тех районов, которые оказалисв в одной группе при исполвзовании различнвхх методов. Однако существуют объектах, ко­торые могут быть отнесены к нескольким кластерам. Для решения проблем такого рода обычно используют индексы, которые показывают на сколь­ко ближе оказываются объекты, принадлежащие одному кластеру, относи­тельно объектов, взятых из разных кластеров. Но при выборе модели по индексу качества кластеризации также можно столкнуться с противоречи­ем, так как их большое количество. Поэтому в Главе 3 предложен новый эвристический метод, позволяющий однозначно распределить объекты по кластерам. Идея алгоритма состоит в том, что выбор нужного кластера — это игра голосования, где кандидатами являются различные варианты рас­пределения объектов, а голосующими — критерии качества кластеризации, которые формулируются для каждой задачи отдельно.
Таким образом, в работе представлен обзор современных методов кластерного анализа временных рядов и предложены новые, описаны экс­перименты на искусственных и реальных данных и рассмотрена приклад­ная задача по выявлению однородных групп районов Санкт-Петербурга по уровню заболеваемости.
Купить