Помощь студентам в учебе
Исследование робастности кластеризации методами статистического и имитационного моделирования
|
Введение 4
Постановка задачи 9
Обзор литературы 14
Глава 1. Методы и критерии оценки устойчивости кластеризации 20
1.1. Процедура возмущения анализируемой выборки данных . . 20
1.2. Имитационный алгоритм 22
1.3. Bootstrapping множеств {Тк}кеК 24
1.4. Выбор устойчивой кластеризации на основе теории рисков . 27
1.5. Выбор устойчивой кластеризации на основе ожидаемого уровня сменяемости 29
Глава 2. Численный эксперимент и сравнение с существующими результатами 32
2.1. Расчет уровней сменяемости кластеризаций 34
2.2. Синтетические данные 35
2.3. Реальные данные 37
2.4. Сравнение результатов с другими индексами устойчивости
кластеризации 39
Глава 3. Приложение критериев устойчивости кластеризации к задаче о размещении хабов в сети 43
3.1. Описание задачи UMApHLP 44
3.2. Сравнение двух результатов решения задачи UMApHLP . . 46
3.3. Численный эксперимент 48
Заключение 50
Список литературы
Постановка задачи 9
Обзор литературы 14
Глава 1. Методы и критерии оценки устойчивости кластеризации 20
1.1. Процедура возмущения анализируемой выборки данных . . 20
1.2. Имитационный алгоритм 22
1.3. Bootstrapping множеств {Тк}кеК 24
1.4. Выбор устойчивой кластеризации на основе теории рисков . 27
1.5. Выбор устойчивой кластеризации на основе ожидаемого уровня сменяемости 29
Глава 2. Численный эксперимент и сравнение с существующими результатами 32
2.1. Расчет уровней сменяемости кластеризаций 34
2.2. Синтетические данные 35
2.3. Реальные данные 37
2.4. Сравнение результатов с другими индексами устойчивости
кластеризации 39
Глава 3. Приложение критериев устойчивости кластеризации к задаче о размещении хабов в сети 43
3.1. Описание задачи UMApHLP 44
3.2. Сравнение двух результатов решения задачи UMApHLP . . 46
3.3. Численный эксперимент 48
Заключение 50
Список литературы
В первой половине ХХ века кластерный анализ начинает свое развитие как отдельное от таксономии направление. Польским антропологом Яном Чекановски в 1911 году была опубликована одна из первых работ в области кластерного анализа [1]. В работе выдвигается идея о формировании групп близких элементов, что составляет основную цель кластерного анализа как инструмента анализа данных.
Развитие компьютерных технологий и вычислительных инструментов предоставляет возможность, а увеличение хранимой информации создает спрос на методы и подходы обработки данных. Кластерный анализ — одна из задач обучения без учителя — подразумевает, что по некоторому правилу определяется схожесть объектов и наиболее близкие объекты образуют группы или кластеры. Природа анализируемых данных может значительно отличаться в зависимости от решаемой задачи, области применения и набора параметров. Это приводит к тому, что нет универсального метода кластеризации или процедуры исследования, а кластерный анализ — это набор методов и алгоритмов для решения задач анализа данных, который непрерывно развивается.
Понятие «кластер» не имеет строгого математического описания, что предоставляет исследователям возможность разрабатывать методы и алгоритмы решения задач кластеризации, ориентируясь на специфику анализируемых данных, и предлагать критерии по оценке качества кластеризации. Можно выделить несколько задач кластерного анализа:
1. Выбор методов кластеризации. Алгоритмы формирования разбиения данных на группы, где объекты из одной группы близки, а объекты из разных групп отличаются.
2. Оценка качества кластеризации. Критерии оценки методов кластеризации для сравнения и выявления наиболее «правильной».
3. Оценка количества кластеров. Методы определения количества групп разбиения.
4. Выбор функции расстояния. Способ сравнения объектов и оценка их близости.
Обзор методов кластеризации, критериев качества кластеризации и функций расстояния представлен в работах [2;3].
В литературе [4] выделяют несколько целей кластеризации:
1. Сокращение объемов хранимых данных. Фиксирование одного представителя каждого кластера и удаление остальных. Используется в сжатии данных или для сокращения объемов исследуемых данных.
2. Определение объектов, не принадлежащих ни к одному кластеру. Задачи одноклассовой классификации или обнаружение новизны (англ. novelty detection).
3. Построение иерархического множества объектов (задачи таксономии).
4. Разбиение задачи обработки данных. Анализ данных внутри кластера вместо анализа всего набора данных.
В выпускной квалификационной работе (ВКР) исследуется одна из задач кластерного анализа — определение «правильной» кластеризации и, как следствие, определение «правильного» количества кластеров. В общем случае выбор количества кластеров зависит не только от методов кластеризации и функций расстояния между объектами, но и от методов сравнения результатов кластеризации. В настоящей работе предлагается концепция решения задачи о нахождении качественной кластеризации, основанная на стохастической устойчивости кластеризации. Применяются процедуры статистического и имитационного моделирования для реализации возможных изменений исследуемых данных или учета возможных ошибок (ошибки измерения, ошибки в представлении чисел в ЭВМ, шум, неполнота данных и т.п.), сравнения кластеризаций и определение уровня рисков отклонения кластеризаций.
Предметом исследования является кластерный анализ, а объектом исследования — алгоритмы определения устойчивой кластеризации.
Цель ВКР заключается в разработке критерия определения статистически устойчивой (надежной) кластеризации с использованием процедур статистического и имитационного моделирования.
Достижение поставленной цели требует решения следующих задач:
1. Задача разработки статистической процедуры анализа кластеризаций.
2. Задача повышения эффективности статистических процедур.
3. Задача оценки и выбора статистически устойчивой кластеризации.
Теоретическая новизна заключается в следующем:
1. Разработана процедура возмущения кластеризации на основе имитационного моделирования.
2. Разработаны 2 критерия определения устойчивой кластеризации основанных на теории рисков и математическом ожидании сменяемости кластеризации.
3. Разработана метрика сравнения близости кластеризаций.
Практическая значимость работы заключается в следующем:
1. Разработана программа ЭВМ для численного решения задачи нахождения устойчивого размещения хабов на основе процедур введенного критерия определения устойчивой кластеризации.
2. Разработана программа ЭВМ для определения устойчивой кластеризации на основе разработанных критериев. Проведено сравнение существующих критериев нахождения устойчивой кластеризации с предлагаемыми в настоящей ВКР.
Основные результаты ВКР были представлены и обсуждены на следующих конференциях:
1. XLVI Международная научная конференция аспирантов и студентов «Процессы управления и устойчивость», 6—9 апреля 2015 г., г. Санкт- Петербург;
2. 20th International Conference on Mathematical Modelling and Analysis, May 26-29, 2015, Sigulda, Latvia;
3. III Международная конференция «Устойчивость и процессы управления», посвященная 85-летию со дня рождения профессора, чл.-корр. РАН В. И. Зубова, 5—9 октября 2015 г., г. Санкт-Петербург;
4. XLIX Международная научная конференция аспирантов и студентов «Процессы управления и устойчивость», 2—5 апреля 2018 г., г. Санкт- Петербург;
5. XIV Международная научная конференция «Устойчивость и колебания нелинейных систем управления» (конференция Пятницкого), 30 мая — 1 июня 2018 г., г. Москва.
Публикации. Материалы диссертации опубликованы в 14 печатных работах, из них 6 тезисов докладов [5—10], 2 статьи в трудах конференций [11;12], индексируемых в РИНЦ, 1 статья в трудах конференции, индексируемом в библиографических базах данных Scopus и Web of Science [13], 1 статья в журнале РИНЦ [14], 1 статья в журнале, индексируемом в базе Web of Science [15], и 2 статьи в журналах, индексируемых в базах Scopus и Web of Science [16;17], 1 работа является магистерской диссертацией автора [18]. Получено свидетельство о государственной регистрации программы для ЭВМ [19].
Структура ВКР. ВКР состоит из введения, постановки задачи, обзора литературы, трех глав, выводов, заключения и списка литературы.
Во Введении отражена актуальность работы, поставлена цель исследования, обоснована научная новизна работы, кратко описаны полученные результаты, и показана их практическая ценность.
В постановке задачи введены основные обозначения и понятия, сформулирована задача кластерного анализа, зафиксирована постановка задачи, которая решается в настоящей работе.
В обзоре литературы приведена классификация методов и подходов к решению поставленной задачи, обсуждены основные принципы работы методов из каждого класса.
В Главе 1 представлены формулировка двух критериев устойчивой кластеризации и процедура их расчета.
В Главе 2 представлены результаты численного эксперимента на искусственных данных и реальных данных, проведено сравнение результатов с другими индексами устойчивости.
В Главе 3 представлены результаты применения критериев устойчивости к задаче о размещении хабов в сети, проведен численный эксперимент на реальных данных.
В заключении подведены итоги работы и сформулированы основные выводы.
Общий объем ВКР составляет 57 страниц, включая 3 рисунка и 10 таблиц. Список литературы включает 59 наименований.
Развитие компьютерных технологий и вычислительных инструментов предоставляет возможность, а увеличение хранимой информации создает спрос на методы и подходы обработки данных. Кластерный анализ — одна из задач обучения без учителя — подразумевает, что по некоторому правилу определяется схожесть объектов и наиболее близкие объекты образуют группы или кластеры. Природа анализируемых данных может значительно отличаться в зависимости от решаемой задачи, области применения и набора параметров. Это приводит к тому, что нет универсального метода кластеризации или процедуры исследования, а кластерный анализ — это набор методов и алгоритмов для решения задач анализа данных, который непрерывно развивается.
Понятие «кластер» не имеет строгого математического описания, что предоставляет исследователям возможность разрабатывать методы и алгоритмы решения задач кластеризации, ориентируясь на специфику анализируемых данных, и предлагать критерии по оценке качества кластеризации. Можно выделить несколько задач кластерного анализа:
1. Выбор методов кластеризации. Алгоритмы формирования разбиения данных на группы, где объекты из одной группы близки, а объекты из разных групп отличаются.
2. Оценка качества кластеризации. Критерии оценки методов кластеризации для сравнения и выявления наиболее «правильной».
3. Оценка количества кластеров. Методы определения количества групп разбиения.
4. Выбор функции расстояния. Способ сравнения объектов и оценка их близости.
Обзор методов кластеризации, критериев качества кластеризации и функций расстояния представлен в работах [2;3].
В литературе [4] выделяют несколько целей кластеризации:
1. Сокращение объемов хранимых данных. Фиксирование одного представителя каждого кластера и удаление остальных. Используется в сжатии данных или для сокращения объемов исследуемых данных.
2. Определение объектов, не принадлежащих ни к одному кластеру. Задачи одноклассовой классификации или обнаружение новизны (англ. novelty detection).
3. Построение иерархического множества объектов (задачи таксономии).
4. Разбиение задачи обработки данных. Анализ данных внутри кластера вместо анализа всего набора данных.
В выпускной квалификационной работе (ВКР) исследуется одна из задач кластерного анализа — определение «правильной» кластеризации и, как следствие, определение «правильного» количества кластеров. В общем случае выбор количества кластеров зависит не только от методов кластеризации и функций расстояния между объектами, но и от методов сравнения результатов кластеризации. В настоящей работе предлагается концепция решения задачи о нахождении качественной кластеризации, основанная на стохастической устойчивости кластеризации. Применяются процедуры статистического и имитационного моделирования для реализации возможных изменений исследуемых данных или учета возможных ошибок (ошибки измерения, ошибки в представлении чисел в ЭВМ, шум, неполнота данных и т.п.), сравнения кластеризаций и определение уровня рисков отклонения кластеризаций.
Предметом исследования является кластерный анализ, а объектом исследования — алгоритмы определения устойчивой кластеризации.
Цель ВКР заключается в разработке критерия определения статистически устойчивой (надежной) кластеризации с использованием процедур статистического и имитационного моделирования.
Достижение поставленной цели требует решения следующих задач:
1. Задача разработки статистической процедуры анализа кластеризаций.
2. Задача повышения эффективности статистических процедур.
3. Задача оценки и выбора статистически устойчивой кластеризации.
Теоретическая новизна заключается в следующем:
1. Разработана процедура возмущения кластеризации на основе имитационного моделирования.
2. Разработаны 2 критерия определения устойчивой кластеризации основанных на теории рисков и математическом ожидании сменяемости кластеризации.
3. Разработана метрика сравнения близости кластеризаций.
Практическая значимость работы заключается в следующем:
1. Разработана программа ЭВМ для численного решения задачи нахождения устойчивого размещения хабов на основе процедур введенного критерия определения устойчивой кластеризации.
2. Разработана программа ЭВМ для определения устойчивой кластеризации на основе разработанных критериев. Проведено сравнение существующих критериев нахождения устойчивой кластеризации с предлагаемыми в настоящей ВКР.
Основные результаты ВКР были представлены и обсуждены на следующих конференциях:
1. XLVI Международная научная конференция аспирантов и студентов «Процессы управления и устойчивость», 6—9 апреля 2015 г., г. Санкт- Петербург;
2. 20th International Conference on Mathematical Modelling and Analysis, May 26-29, 2015, Sigulda, Latvia;
3. III Международная конференция «Устойчивость и процессы управления», посвященная 85-летию со дня рождения профессора, чл.-корр. РАН В. И. Зубова, 5—9 октября 2015 г., г. Санкт-Петербург;
4. XLIX Международная научная конференция аспирантов и студентов «Процессы управления и устойчивость», 2—5 апреля 2018 г., г. Санкт- Петербург;
5. XIV Международная научная конференция «Устойчивость и колебания нелинейных систем управления» (конференция Пятницкого), 30 мая — 1 июня 2018 г., г. Москва.
Публикации. Материалы диссертации опубликованы в 14 печатных работах, из них 6 тезисов докладов [5—10], 2 статьи в трудах конференций [11;12], индексируемых в РИНЦ, 1 статья в трудах конференции, индексируемом в библиографических базах данных Scopus и Web of Science [13], 1 статья в журнале РИНЦ [14], 1 статья в журнале, индексируемом в базе Web of Science [15], и 2 статьи в журналах, индексируемых в базах Scopus и Web of Science [16;17], 1 работа является магистерской диссертацией автора [18]. Получено свидетельство о государственной регистрации программы для ЭВМ [19].
Структура ВКР. ВКР состоит из введения, постановки задачи, обзора литературы, трех глав, выводов, заключения и списка литературы.
Во Введении отражена актуальность работы, поставлена цель исследования, обоснована научная новизна работы, кратко описаны полученные результаты, и показана их практическая ценность.
В постановке задачи введены основные обозначения и понятия, сформулирована задача кластерного анализа, зафиксирована постановка задачи, которая решается в настоящей работе.
В обзоре литературы приведена классификация методов и подходов к решению поставленной задачи, обсуждены основные принципы работы методов из каждого класса.
В Главе 1 представлены формулировка двух критериев устойчивой кластеризации и процедура их расчета.
В Главе 2 представлены результаты численного эксперимента на искусственных данных и реальных данных, проведено сравнение результатов с другими индексами устойчивости.
В Главе 3 представлены результаты применения критериев устойчивости к задаче о размещении хабов в сети, проведен численный эксперимент на реальных данных.
В заключении подведены итоги работы и сформулированы основные выводы.
Общий объем ВКР составляет 57 страниц, включая 3 рисунка и 10 таблиц. Список литературы включает 59 наименований.
В разделе Постановка задачи сформулирована решаемая задача: нахождение устойчивой кластеризации к случайным изменениям данных. В обзоре литературы рассмотрены существующие концепции и методы решения задачи определения «правильной» кластеризации.
В первой главе ВКР формулируются два критерия устойчивости кластеризации. Один из критериев основывается на теории рисков, а именно Value at Risk, где устойчивой кластеризацией считается та, у которой наименьшее значение VaR — индекс отклонений кластеризаций при случайном возмущении исходной выборки данных. Второй критерий основан на оценке ожидания отклонений кластеризаций при многократных имитациях выборок данных случайным образом. Также в Главе1 представлены процедуры возмущения данных, bootstrap алгоритм генерации множества результатов для принятия статистических решений.
В Главе2 представлены результаты численного эксперимента на искусственных и реальных выборках данных. Устойчивые кластеризации по обоим критериям совпали во всех расчетах, но концепции критериев отличаются. Полученные результаты сравниваются с тремя индексами устойчивости кластеризации. Описанные в Главе1 критерии устойчивости получили лучшие результаты на выборках негауссовой структуры, на выборках гауссовой структуры и реальных данных результаты с существующими методами были схожими. Разработана программа для воспроизведения полученных результатов и представлена в открытом доступе.
В Главе3 критерии устойчивости кластеризации применены к задаче о размещении объектов в сети. Алгоритм определения устойчивой кластеризации адаптирован к нахождению устойчивой сети и количества хабов. Проведен численный эксперимент на реальных данных, где выявлено устойчивое количество хабов в результате решения 164 задач целочисленного программирования. Разработана программа ЭВМ для решения задачи устойчивого размещения хабов и определения устойчивого количества хабов.
В первой главе ВКР формулируются два критерия устойчивости кластеризации. Один из критериев основывается на теории рисков, а именно Value at Risk, где устойчивой кластеризацией считается та, у которой наименьшее значение VaR — индекс отклонений кластеризаций при случайном возмущении исходной выборки данных. Второй критерий основан на оценке ожидания отклонений кластеризаций при многократных имитациях выборок данных случайным образом. Также в Главе1 представлены процедуры возмущения данных, bootstrap алгоритм генерации множества результатов для принятия статистических решений.
В Главе2 представлены результаты численного эксперимента на искусственных и реальных выборках данных. Устойчивые кластеризации по обоим критериям совпали во всех расчетах, но концепции критериев отличаются. Полученные результаты сравниваются с тремя индексами устойчивости кластеризации. Описанные в Главе1 критерии устойчивости получили лучшие результаты на выборках негауссовой структуры, на выборках гауссовой структуры и реальных данных результаты с существующими методами были схожими. Разработана программа для воспроизведения полученных результатов и представлена в открытом доступе.
В Главе3 критерии устойчивости кластеризации применены к задаче о размещении объектов в сети. Алгоритм определения устойчивой кластеризации адаптирован к нахождению устойчивой сети и количества хабов. Проведен численный эксперимент на реальных данных, где выявлено устойчивое количество хабов в результате решения 164 задач целочисленного программирования. Разработана программа ЭВМ для решения задачи устойчивого размещения хабов и определения устойчивого количества хабов.