Методы двухэтапной и многокритериальной кластеризации данных выборок больших объемов

• Автор: Киреев, Василий Сергеевич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 153 с. : ил.

Глава 1 Сравнительный анализ подходов к решению задачи кластерного анализа

1.1. Проблема кластеризации данных

1.1.1. Постановка задачи кластерного анализа

1.1.2. Измерение расстояния между объектами

1.1.3. Функционалы качества разбиения

1.1.4. Подходы к решению задачи кластеризации

1.2. Методы кластерного анализа

1.2.1. Методы, основанные на представлении выборки в виде графа

1.2.1.1. Метод КНП (кратчайшего наименьшего пути)

1.2.2. Иерархические методы

1.2.2.1. Агломеративные методы

1.2.2.2. Агломеративные методы на основе свойства редуктивности
1.2.2.3. Дивизимные методы
1.2.3. Параллельные итеративные методы
1.2.3.1. Метод FOREL
1.2.4. Последовательные итеративные методы
1.2.4.1. Кластеризация Expectation Maximization
1.2.4.2. Метод k-средних МакКуина
1.2.5. Нейросетевые методы
1.2.5.1. Сети Кохонена
1.2.5.2. Рекуррентные сети Хопфилда
1.3. Сравнительный анализ методов кластеризации
1.4. Постановка задачи диссертации
Выводы
Глава 2. Новые математические методы решения задачи кластеризации
2.1. Решение задачи таксономии
2.1.1. Постановка задачи
2.1.2. Теоретические основы метода «карманной» кластеризации
2.1.3. Зависимость кластерного решения от значений параметров метода
2.2. Кластеризация методом многоэкстремальной оптимизации
2.2.1. Постановка задачи
2.2.2. Теоретические основы метода Q-кластеризации
2.1.5. Зависимость кластерного решения от значений параметров метода
2.1.6. Применимость метода Q-кластеризации
Выводы
Глава 3. Кластеризация потребителей рынка банковских услуг в РФ
3.1. Задача кластеризации потребителей банковских услуг
3.2 Сокращение пространства признаков выборки
3.2.1. Поиск оптимального числа факторов
3.2.2. Интерпретация полученных факторов
3.3. Сегментация методом «карманной» кластеризации
3.3.1. Реализация метода «карманной» кластеризации
3.3.2. Построение кластерного решения
3.3.3. Построение профилей и интерпретация сегментов
3.3.4. Управленческие рекомендации по результатам сегментирования
Выводы
Глава 4. Исследование профессиональных компетенций ИКТ в рамках Федеральной целевой программы
4.1. Задача выделения пула учителей-инноваторов
4.2. Сокращение пространства признаков выборки
4.2.1. Поиск оптимального числа факторов
4.2.2. Интерпретация полученных факторов
4.3. Сегментация методом <2- кластеризации
4.3.1. Реализация метода (^-кластеризации
4.3. 2. Построение оптимального разбиения
4.3.3. Исследование качества полученного кластерного решения
4.3.4. Интерпретация сегментов
4.4. Результаты многофакторного анализа
4.5. Методы кластерного анализа для определения рейтинга студентов
Выводы
Заключение
Литература
Приложение 1. Элементы анкеты опроса респондентов исследования рынка
банковских услуг
Приложение 2. Анкета опроса участников программы повышения
квалификации в рамках Федеральной целевой программы
Приложение 3. Выходные формы программных реализаций метода
«карманной» кластеризации и (^-кластеризации
Приложение 4. Акты о внедрении
Актуальность.
Решение задачи кластеризации, то есть разбиения исходной совокупности объектов на группы со схожими в смысле какого-либо критерия свойствами, является актуальным для многих приложений, где возникает проблема анализа большого объёма информации - в экологических, медицинских, социологических, экономических и маркетинговых исследованиях.
Задача кластеризации или таксономии впервые была рассмотрена в 1930-х годах. Эту проблему в её различных аспектах изучали как зарубежные, так и отечественные исследователи, в том числе: МакКуин Д., Ланс У., Уильямс Д., Хартиган Д., Вонг М., Кохонен Т., Фрицке Б., и Колмогоров А.Н., Загоруйко Н.Г., Ёлкина В.Н., Айвазян С.А., Мхитарян B.C., Шумский С.А., и другие.
Кластеризация позволяет среди всей совокупности объектов и их свойств уловить определённые закономерности и тенденции. Разработка простых и быстрых методов кластеризации, не зависящих от параметров, значения которых редко можно знать априорно, имеет особую актуальность при решении практических задач в области социальных и экономических приложений, когда точность полученных кластерных решений имеет решающее значение.
Виды задачи разбиения отличаются от приложения к приложению, однако можно выделить несколько общих типов:
• задачи таксономии, в которых требуется построить не просто разбиение данных на кластеры, а иерархию вложенности кластеров друг в друга - таксономическое дерево или, иначе, дендрограмму;
• задачи выделения естественного расслоения исследуемой совокупности на кластеры, причём в такой трактовке задача

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

Неизвестным фактором является суммарное число итераций ^ /,, которые

требуются для стабилизации множества эталонов. Чтобы определить, зависит ли это число от указанных выше параметров, были проведены расчёты по первому этапу для модельных выборок различного объёма — от 1 ООО до 2000 наблюдений, с шагом в 50 наблюдений, для фиксированных значений I и к.
В силу того, что вычислительная сложность второго этапа метода «карманной» кластеризации определяется величиной Д = 1-А: + |о('+,)|, причём
в нашем случае |о(Л+|>| = геА-(-%) = 0, то были выбраны такие Р, чтобы Ръ было
сравнимо с N по порядку.
Для подтверждения гипотезы о наличии связи между изменением объёма выборки и числа итераций был использован дисперсионный анализ. В качестве уровней фактора были выбраны объёмы выборки (и т.д.), в качестве отклика — число итераций. Был использован специально разработанный генератор выборок, содержащих сферические кластеры для получения 200 случайных выборок с последовательно увеличивающимся объёмом (от 90 до 1800 наблюдений, по 10 выборок на каждый объём). По этим выборкам был проведён первый этап «карманной» кластеризации, и рассчитаны суммарные количества итераций и оценено их изменение от фактора - объёма выборок.
Таблица 2.1 Результаты однофакторного дисперсионного анализа
Сумма квадратов df Средний квадрат. F Р- значение
Межфупповая 36,695 19 1,931 1,915 0Д15
Внутригрупповая 181,500 180 1,008
Всего 218,195 199
Рассчитанные значения суммы итераций были нанесены на график, представленный далее (см. рис. 2.1). Из него видно, что число итераций колеблется в некоторых пределах, имеется выраженный пик. Данные