Методы многомерной классификации

Основные понятия

Классификация – разделение рассматриваемой совокупности объектов или явлений на однородные,

Пусть каждый i-ый из анализируемых объектов характеризуется значениями определенного набора признаков

Результат

1. если число классов k и их смысл известны заранее, то

Если в начале располагают не только классифицируемыми данными, но и обучающими

Кластерный анализ

Постановка задачи.
Пусть исследуется совокупность n объектов, каждый из которых характеризуется

Расстояние между объектами и мера близости

Понятие однородности объектов
задается либо введением правила

x2

x1

Расстояние между объектами и мера близости

обычное евклидово расстояние;
xil – значение l-го

Расстояние между объектами и мера близости (продолжение)

«взвешенное» евклидово расстояние;
Каждой компоненте xl

Расстояние между объектами и мера близости (продолжение)

хеммингово расстояние;
Используется как мера различия

Расстояние между кластерами

Пусть Si – i-я группа (кластер), состоящая из ni

Расстояние между кластерами

расстояние по принципу «дальнего соседа»:
расстояние между центрами тяжести классов
где

Расстояние между кластерами

расстояние по принципу «средней связи»:
- среднее арифметическое всех попарных

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

Агломеративные иерархические процедуры классификации на первом шаге рассматривают каждое из классифицируемых

Иерархические процедуры классификации

ПРИМЕР
По приведенным данным провести классификацию 5 семей по двум

Иерархические процедуры классификации

x2

x1

Иерархические процедуры классификации

РЕШЕНИЕ
1.1. Евклидова метрика. Принцип «ближнего соседа».

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
Имеем: S1, S2, S3, S4,5

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
Расстояние между кластерами S1 и S4,5 равно:

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
Имеем: S1,2, S3, S4,5

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
Расстояние между кластерами S1,2 и S4,5 равно:

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
Имеем: S1,2,3, S4,5

Иерархические процедуры классификации

Иерархические процедуры классификации

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
1.2. Принцип «дальнего соседа».
Имеем: S1, S2, S3, S4,5

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
Расстояние между кластерами S1 и S4,5 равно:

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
Имеем: S1,2, S3, S4,5

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
Расстояние между кластерами S1,2 и S4,5 равно:

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
Имеем: S1,2, S3,4,5

Иерархические процедуры классификации

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
1.3. Принцип «центра тяжести».
Имеем: S1, S2, S3, S4,5

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
Кластер S4,5 характеризуется центром тяжести:
Расстояние между кластерами S1

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
Имеем: S1,2, S3, S4,5

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
Кластер S1,2 характеризуется центром тяжести:
Расстояние между кластерами S1,2

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
Имеем: S1,2,3, S4,5

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
Кластер S1,2,3 характеризуется центром тяжести:
Расстояние между кластерами S1,2,3

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
1.4. Принцип «средней связи».
Имеем: S1, S2, S3, S4,5

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
Расстояние между кластерами S1 и S4,5 равно:

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
Имеем: S1,2, S3, S4,5

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
Расстояние между кластерами S1,2 и S4,5 равно:

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
Имеем: S1,2,3, S4,5

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
Расстояние между кластерами S1,2,3 и S4,5 равно:

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
2.1. Взвешенное евклидово расстояние. Принцип «ближнего соседа».
w1=0,05

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
Имеем: S1, S2,3,S4, S5

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
Имеем: S1, S2,3, S4,5

Иерархические процедуры классификации

РЕШЕНИЕ (продолжение)
Имеем: S1,,4,5, S2,3

СТЭФ-2017

Метод

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

Метод К-средних предназначен для разбиения многомерных наблюдений на заданное число К

Метод К-средних обычно используется при достаточно больших объемах n классифицируемых данных

Имеем нулевое приближение:
, i = 1, 2, …, k
После «извлечения» новой

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

2-й этап метода K-средних посвящен соответственно процедуре классификации.
Окончательное разбиение S исследуемой

СТЭФ-2017

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