Поручиков М.А. Анализ данных. А. поручиков

• Название: А. поручиков
• Дата: 25.10.2022
• Размер: 2.76 Mb.
• Имя файла: Поручиков М.А. Анализ данных.docx
• Тип: Анализ; #753011
• страница: 16 из 20

КЛАСТЕРНЫЙ АНАЛИЗ

Общие сведения

Кластерный анализ – (кластеризация) выявление групп (кластеров) объектов в выборке данных.

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

Набор неклассифицированных объектов


Кластерный анализ
Классы объектов

Рис. 40. Схема кластерного анализа
Выборка данных в общем случае представляет собой таблицу (табл. 22).
Таблица 22. Шаблон набора данных

Наименование объекта	Свойство 1	Свойство 2	…	Свойство M
Объект 1
Объект 2
…
Объект N

Метод к-средних

Существует большое число методов кластерного анализа [22, 23], а наиболее известным является метод (алгоритм) к-средних.

Принцип: расчет средневзвешенного расстояния в нормированном эвклидовом пространстве свойств объектов (рис. 41).

Рис. 41. Метод к-средних
Метод к-средних представляет собой следующую последовательность операций:

1. 
   Пользователь задает количество кластеров.
   
2. 
   Производится первоначальное случайное распределение объектов из выборки данных по кластерам.
   
3. 
   Вычисляются коодинаты центров кластеров.
   
4. 
   Вычисляются расстояния от каждого объекта до центров соответствущих кластеров.
   
5. 
   Рассчитывается функция штрафа – сумма всех расстояний.
   
6. 
   Каждый из объектов «прикрепляется» к тому кластеру, расстояние до центра которого наименьшее.
   

Шаги 3 – 6 повторяются до тех пор, пока не перестанут изменяться координаты центров кластеров.

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

Рассмотрим пример использования метода к-средних. Пусть имеется набор объектов, имеющих два свойства (табл. 23).
Таблица 23. Объекты и их свойства

Объект	Свойство 1	Свойство 2
1	10	7
2	12	5
3	35	2
4	45	4

Проведем нормализацию исходных данных, т.е. приведение их к диапазону 0..1 по каждому свойству (измерению) (табл. 24).
Таблица 24. Объекты и их нормализованные свойства

Объект	Свойство 1	Свойство 2
1	0,00	1,00
2	0,06	0,60
3	0,71	0,00
4	1,00	0,40

Последовательно применив алгоритм метода k-средних, получим следующие результаты (табл. 25).
Таблица 25. Варианты распределения объектов по кластерам

Шаг	Распределение по кластерам					R2
	Объект 1	Объект 2	Объект 3	Объект 4
1	1	1	1	2	0,822
2	1	1	2	1	0,817
3	1	2	1	1	1,037
4	2	1	1	1	0,654
5	1	2	2	1	1,076
6	1	1	2	2	0,202

Шаг 6 иллюстрирует следующая диаграмма (рис. 42). При этом найденное на этом шаге значение R² является минимальным, что свидетельствует о наилучшем распределении объектов по кластерам на этом шаге.

Свойство 2
9
8
7
6
5
4
3
2
1
0

0 10 20 30 40 50

Свойство 1
Рис. 42. Вариант распределения объектов по кластерам
Таким образом, найдено следующее оптимальное распределение объектов по кластерам (табл. 26).
Таблица 26. Распределение объектов по кластерам

Объект	Свойство 1	Свойство 2	Кластер
1	10	7	1
2	12	5	1
3	35	2	2
4	45	4	2

Метод к-средних не дает ответа на вопрос о количестве кластеров в выборке данных. Для определения количества кластеров можно воспользоваться так называемым методом локтя (Elbow Method). Метод локтя предполагает выполнение следующих шагов:

1. 
   Выполняется кластеризация методом к-средних, при этом рассчитывается и записывается значение функции штрафа.
   
2. 
   Строится график зависимости функции штрафа от заданного числа кластеров.
   
3. 
   В качестве решения выбирается число кластеров, при котором происходит наибольший перегиб графика.
   

Программноеобеспечениеkmeans

Метод к-средних реализован в программном обеспечении kmeans. ПО kmeans предназначено для кластеризации набора объектов, имеющих два свойства и представлено в виде исполняемого файла для ОС Windows. Программное обеспечение имеет однооконный интерфейс (рис. 43).




Рис. 43. Интерфейс программного обеспечения k-means
Основные функции управления реализованы в панелях «Исходные данные» и «Управление экспериментом» (рис. 44).

Панель «Исходные данные»:

• 
  кнопка «Загрузить данные» предназначена для загрузки исходных данных для кластерного анализа;
  
• 
  параметр «Число объектов» показывает количество объектов в загруженном файле данных;
  
  • 
    показатель «Число кластеров» предназначен для задания числа кластеров, по которым будет производиться разбивка объектов.
    

Панель «Управление экспериментом»:

• 
  выключатель «Ограничение по времени»;
  
• 
  кнопка «Старт» предназначена для запуска процедуры кластеризации. Кластеризация будет происходить, пока не перебраны все возможные варианты или не закончилось время, отпущенное на эксперимент;
  
• 
  показатель «Время эксперимента» показывает длительность эксперимента;
  

показатель «Число вариантов» показывает сколько вариантов разбиения объектов по кластерам было исследовано на данный момент;

• 
  показатель «Варианты распределения по кластерам» показывает число вариантов распределения объектов по кластерам.
  

Рис. 44. Панели «Исходные данные» и «Управление экспериментом»
График функции штрафа (рис. 45) показывает изменение функции штрафа со временем в процессе кластеризации.

Диаграмма распределения по кластерам (рис. 46) показывает расположение объектов в декартовой системе координат и принадлежность объекта к тому или иному кластеру. Горизонтальной оси соответствует первый показатель из исходного

файла данных, вертикальной оси – второй. Отображение диаграммы регулируется следующими элементами управления:




Рис. 45. График функции штрафа

• 
  выключатель «Наименования объектов» позволяет подписать объекты на диаграмме;
  
• 
  выключатель «Лучи “центры-объекты”» позволяет отобразить лучи от центра кластеров до всех объектов кластера;
  
• 
  выключатель «Центры кластеров» позволяет отобразить условные центры кластеров;
  
• 
  выключатель «Граница» позволяет отобразить условные границы кластеров. Граница представляет собой ломаную линию, объединяющую все объекты каждого кластера;
  
• 
  кнопка «Сохранить диаграмму» записывает диаграмму в графический файл в формате PNG;
  
• 
  кнопка «Сохранить кластеры» создает файл, cодержащий номера кластеров, координаты их центров и количество объектов в кластерах.
  

Рис. 46. Диаграмма распределения по кластерам
Анализ данных с использованием ПО kmeansпроводится по следующей схеме (рис. 47).

Исходные данные
Параметры эксперимента

Классифицированные

Программное обеспечение im_rec.exe	объекты
	Параметры классов

Рис. 47. Схема эксперимента
Исходные данные должны быть представлены в файле в формате CSV «Текст, разделенный». В файле должно быть три столбца:

1. 
   Наименования объектов.
   
2. 
   Значение первого свойства.
   

3. 
   Значение второго свойства.
   

Первая строка файла должна содержать подписи свойств объектов. Подготовку исходных данных удобно производить в Microsoft Excel (рис. 48). После подготовки данных файл необходимо сохранить в формате CSV (разделители – запятые).





Рис. 48. Представление исходных данных в Microsoft Excel
Убедиться в корректности подготовленного файла можно, открыв его в блокноте Windows (рис. 49).





Рис. 49. Представление исходных данных в блокноте Windows