Алгоритмы кластерного анализа

Алгоритмы выделения кластеров делятся на три класса: адаптивные, агломеративные и с оптимизацией критерия.

Адаптивные алгоритмы основаны на использовании простых настраивающихся эвристических правил классификации, агломеративные (от англ. слова agglomerate – собирать) – на последовательном слиянии двух «наиболее близких» кластеров в один.

Примером адаптивного алгоритма является алгоритм гиперсфер. При применении данного алгоритма число кластеров заранее не фиксируется, но задается радиус гиперсферы – R*.

1-й шаг. Формируется первый кластер. Берется гиперсфера радиуса R*с центром в произвольной точке (первый объект), и все объекты, которые попали внутрь гиперсферы, относятся к кластеру № 1.

2-й шаг. Вычисляется новый центр кластера № 1 как центр тяжести всех точек (объектов), входящих в кластер. Центр гиперсферы радиуса R* переносится в новый центр кластера № 1.

3-й шаг. Уточняется состав точек, входящих в новую гиперсферу.

Если состав точек не изменился, то формирование 1-го кластера завершается, в противном случае повторяются шаги 2 и 3.

После выделения первого кластера переходят к формированию следующего аналогичным образом, пока все точки не войдут в какие-либо кластеры.

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

Примером агломеративного алгоритма является метод корреляционных плеяд, использующий матрицу расстояний между объектами

D = || ρ ( i, j) ||.

При применении этого алгоритма задаются произвольным порогом U₀и формируют матрицу близости U следующим образом:

U_ij= 1, если ρ(i; j) £ U₀;

U_ij= 0, если ρ(i; j) > U₀.

Матрица U порождает некоторый граф (рисунок), на котором "близкие" объекты ( U_ij= 1 ) соединяются дугами. В результате применения такого подхода все множество объектов разбивается на несвязанные друг с другом дугами кластеры.

Количество выделенных кластеров зависит от принятой величины U₀:

– если U₀< min ρ (i; j),

i,j

выделится n кластеров (каждый объект будет образовывать самостоятельный кластер);

- если U₀> max ρ (i; j) ,

ij

все объекты попадут в один кластер.

Поэтому величина U₀должна лежать в следующем диапазоне:

min ρ (i; j) < U₀< max ρ (i; j).

i,j i,j

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

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

Для решения проблемы выхода из процедуры кластеризации воспользуемся критерием

где = – мера близости объектов i и j;

– число сочетаний из элементов по 2;

n – общее количество рассматриваемых объектов.

Критерий (2.13) представляет собой разность между средней мерой близости объектов внутри кластеров и средней мерой близости между объектами разных кластеров. Наилучшим вариантом кластеризации считается тот, при котором значение этого критерия максимально. Проведенные исследования показали, что значение критерия возрастает на начальном этапе объединения объектов в кластеры, достигает максимума при некотором количестве кластеров k , а далее начинает уменьшаться.

К алгоритмам с оптимизацией критерия относится алгоритм ISODATA и ряд других алгоритмов. Их основной недостаток – зависимость результата от начального разбиения объектов. Кроме того, оптимизационные алгоритмы предполагают априорное задание количества классов – k, так как меры качества разбиения объектов на кластеры (2.11) и (2.12) являются убывающими функциями числа классов.

Приведем пример агломеративного иерархического алгоритма. На первом шаге каждое наблюдение X_i (i = 1, 2,...,n) рассматривается как от­дельный кластер. В дальнейшем на каждом шаге работы алгоритма проис­ходит объединение двух самых близких кластеров, и, с учетом принятого расстояния, по формуле пересчитывается матрица расстояний, размер­ность которой, очевидно, снижается на единицу. Работа алгоритма закан­чивается, когда все наблюдения объединены в один класс. Большинство программ, реализующих алгоритм иерархической классификации, преду­сматривает графическое представление классификации в виде дендро-граммы.

Пример 1

Провести классификацию n=6 объектов, каждый их которых харак­теризуется двумя признаками (табл.1).

Т а б л и ц а 1. Значения признаков

Номер объекта i
xi1
xi2

Расположение объектов в виде точек на плоскости показано на рис.1.

15 X₂

13 *

12 *

10 *

9 * *

7 *

6 X₁

1 2 3 4 5 6 7 8 9 10 11 12

Рис.1. Расположение объектов

Решение

Воспользуемся агломеративным иерархическим алгоритмом классифи­кации. В качестве расстояния между объектами возьмем обычное евклидо­во расстояние. Тогда согласно формуле (2.2) расстояние между первым и вторым объектами

𝛒₁₂ = = 2,24, а между первым и третьим объектами

𝛒₁₃= = 3.

Очевидно, что

𝛒₁₁=0.

Аналогично находим остальные расстояния между шестью объектами и строим матрицу расстояний.

Из матрицы расстояний следует, что четвертый и пятый объекты наи­более близки ρ₄,₅ =1,00 и поэтому объединяются в один кластер. После объединения объектов имеем пять кластеров (табл.2).

Т а б л и ц а 2. Состав кластеров

Номер кластера
Состав кластера	(1)	(2)	(3)	(4,5)	(6)

Расстояние между кластерами определим по принципу "ближайшего соседа".

Расстояние 𝛒_1,(4,5) равно расстоянию от объекта 1 до ближайшего к нему объекта, входящего в кластер S(4,5) т. е. 𝛒_1,(4,5) = 𝛒_1,4 =5,10. Тогда матрица расстояний

Объединим второй и третий объекты, имеющие наименьшее расстоя­ние 𝛒₂₃ = 1,41. После объединения объектов имеем четыре кластера:

S₍₁₎, S_(2,3), S_(4,5), S₍₆₎

Вновь найдем матрицу расстояний. Для того чтобы рассчитать рас­стояние до кластера S_(2,3) воспользуемся матрицей расстояний R₂. На­пример, расстояние между кластерами S_(4,5) и S_{( 2, 3)} равно 5.

Проведя аналогичные расчеты, получим

Объединим кластеры S_(4,5) и S₍₆₎, расстояние между которыми согласно матрице R₃ наименьшее ρ_(4,5),6=2,00. В результате получим три кластера S₍₁₎, S_(2,3), S_(4,5,6). Матрица расстояний будет иметь вид

Объединим теперь кластеры S₍₁₎ и S_(2,3), расстояние между которыми 𝛒_1,(2,3)= 2,24. В результате получим два кластера: S_(1,2,3) и S_(4,5,6), расстоя­ние между которыми, найденное по принципу "ближайшего соседа",

𝛒 _{(1,2,3), (4.5.6)} =5,00.

Результаты иерархической классификации объектов представлены на рис. 2 в виде дендрограммы.

На рис. 2 приводятся расстояния между объединяемыми на данном этапе кластерами (объектами). В нашем примере предпочтение следует отдать предпоследнему этапу классификации, когда все объекты объеди­нены в два кластера S_(1,2,3) и S_(4,5,6).

5,00

2,24 2,00

1,41

1 1,00

0 1 2 3 4 5 6

Рис. 2. Результаты классификации объектов

Пример 2. Автомагазином были опрошены следующие группы покупа­телей: молодые и пожилые бизнесмены, люди среднего и пожилого возраста с высоким и средним уровнем доходов.

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

Ответы обследуемых групп в кодированной записи (0 или 1) приведены в табл. 3.

Т а б л и ц а 3. Результаты опроса покупателей

Номер	Уровень	Состав	Характеристика
группы	дохода	группы
			Высок	Ино-	Экст.	Комфорта-	Экономич-	Безо-
			скор.	марка	вид	бельность	ность	пасность
	Высокий	Молодые бизнесмены
	-//-	Пожилые бизнесмены
		Люди среднего возраста
	-//-
	-//-	Люди пожилого возраста
	Средний	Молодые
		бизнесмены
	-//-	Пожилые бизнесмены
		Люди среднего возраста
	-//-
	-//-	Люди
		пожилого
		возраста

Матрица расстояний между группами покупателей, рассчитанная по формуле (2.6), приведена в табл. 4.

Т а б л и ц а 4. Матрица расстояний

Группа
	-
		-
			-
				-
					-
						-
							-
								-

Задаваясь пороговым значением Т=1 (т. е. не более одного несовпадающего требования), получим следующую матрицу близости (табл. 5).

Т а б л и ц а 5. Матрица близости

Группы
	-
		-
			-
				-
					-
						-
							-	1 .
								-

Исходя из табл. 5, построим граф взаимосвязи покупателей (рис. 3).

Рис. 3. Граф взаимосвязи покупателей

Таким образом, в результате использования алгоритма получено 3 кластера (S₁ ¸ S₃):

– 1-й кластер — молодые бизнесмены, независимо от уровня
дохода;

– 2-й кластер — пожилые бизнесмены и люди среднего и
пожилого возраста с высокими доходами;

– 3-й кластер — люди среднего и пожилого возраста со средними доходами.

3. ДИСКРИМИНАНТНЫЙ АНАЛИЗ

3.1. Теоретические основы дискриминантного анализа

Дискриминантный анализ как раздел многомерного статистического анализа включает в себя статистические методы классификации много­мерных наблюдений в ситуации, когда исследователь обладает так назы­ваемыми обучающими выборками ("классификация с учителем").

В общем случае задача различения (дискриминации) формулируется следующим образом. Пусть результатом наблюдения над объектом явля­ется реализация k-мерного случайного вектора x=(x₁,x₂,...,x_k)^T. Требуется установить правило, согласно которому по наблюденному значению век­тора x объект относят к одной из возможных совокупностей (i=1,2,...,m). Для построения правила дискриминации все выборочное пространство Rⁿ значений вектора х разбивается на области X_i (i=1,2,...,m) так, что при попадании х в X_i, объект относят к совокупности p_i.

Правило дискриминации выбирается в соответствии с определенным принципом оптимальности на основе априорной информации о совокуп­ности p_i вероятностей извлечения объекта из p_i. При этом следует учитывать размер убытка от неправильной дискриминации. Априорная информация может быть представлена как в виде некоторых сведений о функции k-мерного распределения признаков в каждой совокупности, так и в виде выборок из этих совокупностей. Априорные вероятности р_i могут быть либо заданы, либо нет. Очевидно, что рекомендации будут тем точнее, чем полнее ис­ходная информация.

С точки зрения применения дискриминантного анализа наиболее важ­ной является ситуация, когда исходная информация о распределении представлена выборками из них. В этом случае задача дискриминации ставится следующим образом.

Пусть выборка из совокупности , i=1,2,...,m; причем каждый j-й объект выборки представлен k-мерным век­тором параметров

.

Произведено дополнительное наблюдение x=(x₁,...,x_k)^T над объектом, принадлежащим одной из совокуп­ностей . Требуется построить правило отнесения наблюдения х к одной из этих совокупностей.

Наиболее изучен случай, когда известно, что распределение векторов признаков в каждой совокупности нормально, но нет информации о пара­метрах этих распределений. Здесь естественно заменить неизвестные па­раметры распределения их наилучшими оценками. Правило дискриминации можно основывать на отношении правдоподобия.

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

В параметрических методах эти точки используются для оценки па­раметров статистических функций распределения. В параметрических ме­тодах построения функции как правило используется нормальное распре­деление, т. е. обычно имеют место следующие предположения:

1) имеются разные классы объектов;

2) каждый класс имеет нормальную функцию плотности от к перемен­ных

(x-

где – вектор математических ожиданий переменных размерности k;

– ковариационная матрица размерности k*k;

– обратная матрица.

В случае если параметры известны, дискриминацию можно провести, например, следующим образом.

Имеются функции плотности нормально рас­пределенных классов. Задана точка х в пространстве к измерений. Предпо­лагая, что f_i(x) имеет наибольшую плотность, отнесем точку х к i-му классу. Существует доказательство, что если априорные вероятности для определяемых точек каждого класса одинаковы и потери при неправиль­ной классификации i-й группы в качестве j-й не зависят от i и j, то решаю­щая процедура минимизирует ожидаемые потери при неправильной клас­сификации.

Приведем пример оценки параметра многомерного нормального рас­пределения μ и Σ..

μ и Σ могут быть оценены по выборочным данным: и для клаcсов. Задано l выборок

; (i=1,…,m)

из некоторых классов. Математические ожидания могут быть оценены средними значениями

.

(3.1)

Несмещенные оценки элементов ковариационной матрицы Σ есть

.

(3.2)

Следовательно, можно определить и по l выборкам в каждом классе при помощи (3.1), (3.2). Получив оценки, точку х отнесем к клас­су, для которой функция f(х) максимальна. Класс, к которому должна принадлежать точка х, можно определить на основе неравенства

f_i(x)>f_j(x).

3.2. Метод потенциальных функций

Будем рассматривать детерминистическую постановку. Пусть . Через K(x,y) будем обозначать потенциал, создаваемый точкой в точке . Функция K(x,y) должна удовлетворять следующим условиям:

а) K(x,y) >0 для всех ;

б) ;

в) если точка удаляется от , то значение K(x,y) убывает.

Приведем пример функции K(x,y). Пусть . Тогда можно, например, положить , где . График функции K(x,y) при фиксированном представляет собой холм с вершиной над точкой .

Пусть . Определим – сумму холмов над точками из А; – сумму холмов над точками из В. Тогда функцию можно интерпретировать как разделяющую два множества А и В.

3.3. Статистический подход в теории распознавания образов

Если рассматривать векторное представление образов, то в общем случае вектор признаков состоит из признаков, каждый из которых и вся совокупность в целом характеризуют образ с той или иной степенью неопределенности. Эта неопределенность может, в частности, носить и вероятностный характер. Другими словами, каждый вектор признаков образа представляет собой многомерную случайную величину. Появление того или иного образа является случайным событием и вероятность этого события можно описать с помощью закона распределения вероятностей этой многомерной случайной величины в той или иной форме, например в форме плотности распределения вероятностей. Вид и параметры функции плотности определяются конкретной ситуацией, в которой работает система распознавания. По обучающей выборке можно восстановить все вероятностные характеристики.

Основными вероятностными характеристиками являются:

– плотность распределения вероятностей появления образа f(x);

–условные вероятностипринадлежности некоторого образа заданным классам ;

– вероятности появления классов ;

– условные плотности распределения вероятностей внутри классов ,

Будем предполагать, что события появления классов образуют полную группу событий. Тогда справедлива формула полной вероятности

и формула Байеса

.