Лекция 9. Кластерный анализ
9 Иерархические кластер-структуры
В статистических исследованиях группировка первичных данных является основным приемом решения задачи классификации. Обычно эта задача решается так. Из множества признаков, описывающих объект, отбирается один, наиболее информативный с точки зрения исследователя, и проводится группировка в соответствии со значениями данного признака. Если требуется провести классификацию по нескольким признакам (по степени важности), то сначала производится классификация по первому признаку, затем каждый из полученных классов разбивается на подклассы по второму признаку и т.д.
Задача классификации при наличии нескольких признаков может быть решена и другими методами, одним из которых является метод кластерного анализа.
Пусть исследуется совокупность n объектов, каждый из которых характеризуется по k замеренным на нем признакам X, то есть исходными данными служит таблица:
.
Требуется разбить эту совокупность на однородные в некотором смысле группы (классы). Полученные в результате разбиения группы называются кластерами. Методы нахождения кластеров называются кластер-анализом.
Основным этапом решения задачи поиска кластеров является выбор способа вычисления расстояний или близости между объектами или признаками.
Так может быть использовано обычное евклидово расстояние:
,
где
– величинаl-ой
компоненты у i-ого
признака (j-ого)
объекта l=1,2,…,k,
i,j=1,2,…,n.
Расстояние между группами элементов особенно важно в так называемых иерархических кластер-процедурах.
Принцип работы иерархических процедур состоит в последовательном объединении различных групп элементов сначала самых близких (далеких), а затем все более отдаленных (близких) друг от друга.
Расстояние между кластерами Sl и S(m,q) можно найти по формуле:
.
Существуют и другие формулы для нахождения расстояний между элементами и кластерами.
При реализации алгоритма иерархической классификации предусматривается графическое представление классификации в виде дендрограммы.
Пример.Провести классификацию 6 объектов, каждый из которых характеризуется двумя признаками.
|
номер объекта |
1 |
2 |
3 |
4 |
5 |
6 |
|
хi1 |
5 |
6 |
5 |
10 |
11 |
10 |
|
хi2 |
10 |
12 |
13 |
9 |
9 |
7 |
Решение.Расстояние между объектами будем вычислять, как обычное евклидово.
.
Очевидно, что р11=0.
Аналогично находим расстояния между остальными объектами и строим матрицу расстояний:
R1=p(xi,xj)=
.
Из этой матрицы расстояний следует, что наиболее близки четвертый и пятый объект (4,5)=1 и поэтому их объединяем в один кластер. После объединения имеем пять кластеров:
|
№ кластера |
1 |
2 |
3 |
4 |
5 |
|
Состав кластера |
(1) |
(2) |
(3) |
(4,5) |
(6) |
Расстояние между кластерами будем определять по указанной выше формуле. Так расстояние между объектом S1 и кластером S(4,5):
.
Таким образом, расстояние
равно расстоянию от объекта 1 до ближайшего
к нему объекта, входящего в кластерS(4,5),
то есть
.
В этом случае говорят, что расстояние
между кластерами определяем по принципу
«ближайшего соседа».
Следующая матрица расстояний имеет вид:
R2=
.
Здесь наименьшее расстояние
,
то есть объекты 2,3 объединяем в кластерS(2,3)
и получаем четыре кластера
S(1), S(2,3), S(4,5), S(6).
Находим вновь матрицу расстояний, используя матрицу R2. Например:
=
.
После расчетов, получим матрицу расстояний:
R3=
.
Здесь
наименьшее расстояние
.
Объединяем эти элементы в один кластер.
В результате получаем три кластера:
S(1), S(2,3), S(4,5,6).
Для этих кластеров матрица расстояний имеет вид:
R4=
.
В этой матрице наименьшее
расстояние
.
Объединяем кластерыS(1)
и S(2,3).
Получаем два кластера
S(1,2,3), S(4,5,6).
Результаты такой иерархической классификации объектов можно представить в виде дендрограммы:
5
4
3
2
1
1 2 3 4 5 6