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

Основные типы задач кластер - анализа и основные типы кластер -процедур

Типы задач:

В зависимости от n - объёма классифицирования наблюдений Х1,…Хn задачи кластер-анализа подразделяются на 2 типа:

Б1: n- не более нескольких десятков наблюдений (классификация макрообъектов: страны, города, предприятия, технологические процессы и т.д.).

Б2: n - несколько сотен или тысяч многомерных наблюдений (классификация индивидуумов, семей, изделий, промышленных и технологических микрообъектов).

В зависимости от априорной информации от кластеров, на которые требуется разбить совокупность объектов, окончательно задачи подразделяются на 3 тапа:

(а)- число классов задано

(б)- число классов неизвестно и подлежит определению

(в)- число классов неизвестно, но его определение не входит в задачу исследователя

(требуется построить иерархическое дерево или дендрограмму). Под иерархическим деревом понимается последовательность пар

Перечислим коротко алгоритмы:

II.1. Алгоритм, связанный с функционалами качества (например, алгоритм непоследовательного переноса точек из класса в класс).

Начальное разбиение S(0) =(S1(0),…,Sk(0)), вычисляем Q(S(0)).

Затем каждое из наблюдений начинают перемещать из класса в класс и оставляют в том положении, для которого Q(S) экстремально.

II.2. Алгоритм использует понятие эталонных множеств

Если |Еi|=1, то имеем k эталонных точек, затем остальные наблюдения начинают

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

III) Последовательные кластер - процедуры.

Если n велико (от нескольких сотен и более), то применение процедур иерархических и параллельных типов практически невозможно.

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

Основными средствами являются меры близости или расстояния, порог, эталонные точки, функционалы качества.

1. Простейший пример такого алгоритма с использованием понятия порога:

1) Наблюдение Х1 объявляется центром е1 1-й группы.

2) Рассмотрим точку Х2, если (Х2, е1) < C, то Х2 присоединяется к первой группе,

если (Х2, е1) > C, то Х2 объявляется центром е2 2-й группы.

На l – ом шаге, когда имеются r групп точка Хl относится к группе еj,

если найдется (Хl, еj) < C, (1 < j < r) или становится центром (r+1) - ой группы и так далее.

2. Метод k - средних при известном числе классов.

Х = {X₁,…,Х_n} требуется разбить на заданное число классов k << n.

Смысл алгоритма в последовательном уточнении эталонных точек

 = 0,1,2,... с учетом приписывания им весов

Е⁽⁰⁾ строится с помощью случайно выбранных k точек исследованной совокупности.

Не ограничивая общности, можно сказать

Затем извлекается точка Хk+1 и выясняется к какому из эталонов еi она ближе

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

тяжести старого эталона и присоединенной к нему точки Хk+1 (с увеличением на

единицу соответствующего ему веса).

Таким образом, пересчет эталонов на-м шаге (при извлечении точки

Хk+v) происходит по следующему правилу:

Если для нескольких значений i выполняется

то по договорённости точку Хk+v относят к одному из этих эталонов.

При достаточно больших v и n и весьма широких ограничениях пересчёт эталонных точек практически не приводит к их изменению, то есть имеет место «сходимость» при , n → ∞.

3) Имеет место обобщение изложенного выше метода k-средних на случай, значение k – неизвестно.

Задаётся константами Ф0 и 0.

Работа алгоритма состоит в последовательном построении эталонных точек

и весов:

но число классов k() может меняться от итерации к итерации.

На нулевом этапе берётся любое значение k(0) > 1 и полагается

Затем производится процедура огрубления эталонных точек, если

то (E	()	,..., E	()	
i	j

заменяется их взвешенным средним с весом, равным сумме 2-х

соответствующих весов i и j.

В результате получаем k0 <k0 эталонных точек.

Процедура огрубления закончена.

Далее берётся точка Хk(0)+1 и вычисляется её расстояние до ближайшей эталонной

точки (после огрубления). Если это расстояние >, то точка Хk(0)+1 обьявляется новой

эталонной точкой с весом k0+1=1.Если это расстояние < то самый близкий эталон и точка Хk(0)+1 заменяется новым эталоном, являющимся их центром тяжести (как в обычном методе k-средних).

Далее снова огрубление и новый шаг алгоритма и так далее. Где-то процесс

остановится на константе k

Выбор констант Ф0 и 0 можно считать удачным, если окончательное разбиение

является оптимальным в смысле функционалов качества или с точки зрения экспертов.

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

Наиболее трудным и наименее формализованным в задаче кластер-анализа является момент, связанный с понятием однородности объектов. В общем случае однородность объектов определяется задание правила вычисления величины , характеризующее либо «расстояние» d_ij = d(O_i, O_j), либо степенью «близости» (сходства) s_ij = s(O_i, O_j).

Если задана функция d(O_i, O_j), то «близкие» в этом смысле объекты считаются однородными (т.е. принадлежащие одному классу). При этом возможно сопоставление величин d_ij с некоторым пороговым значением, определяемым в каждом конкретном случае.

При задании d_ij и s_ij следует помнить о соблюдении следующих естественных требований:

1) Требование симметрии:

2)

Требование максимального сходства объекта с самим собой: s_ii = s_ij

3) Требование монотонного убывания по, т.е.

4) Каждый объект О_i представлен вектором признаков X_i = ( (2.5). В дальнейшем будем писать вместо d(O_i, O_j) - d(X_i, X_j), вместо s(O_i, O_j) пишем s(X_i, X_j)

5) Таким образом, задача разбиения множества объектов {О₁,…,O_n} на кластеры сводится к задаче разбиения множества векторов Х = {X₁,…, X_n) на кластеры, где X_i задается (2.5)

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

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

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

Как и ранее мы отождествляем объект О_i и вектор признаков X_i (2.5), ему соответствующий. Тогда разбиение множества {О₁,…,O_n} сводится к разбиению векторов {Х₁,…,Х_n} = Х.

Пусть мы имеем одно из таких разбиений

, где

- вектор средних арифметических компонент векторов, входящих в S_m

1. Расстояние, измеряемое по принципу «ближнего соседа»:

(4.5)

2. Расстояние, измеряемое по принципу «дальнего соседа»:

(4.6)

3. Расстояние, измеряемое по «центрам тяжести» групп:

(4.7)

4. Расстояние, измеряемое по принципу «средней связи»:

(4.8)

5. обобщенное по Колмогорову расстояние между классами, включающее в себя в качестве частных случаев все предыдущие:

(4.9)

где r – неизвестный параметр

Исходное обобщение такого рода, предложенное А.Н. Колмогоровым, таково:

Пусть с₁,…,с_n – некоторые величины. F(U) – некоторая числовая функция, строго монотонная , F^-1-обратная функция

Обобщенное среднее компонент с₁,…,с_n вычисляется по формуле:

M_F (с₁,…,с_n) = F^-1

Для F(U)=U^r получаем степенное среднее:

M_r = M_r (с₁,…,с_n) = (4.10)

Можно показать, что при c_i > 0

- геометрическое среднее

- арифметическое среднее

Положив в (4.10) c_t = d(X_i, X_j), получаем (4.9). в силу вышеупомянутого из (4.10) имеем:

вид (4.5)

вид (4.6)

вид (4.8)

Расстояния d(X_i, X_j) в формулах (4.5) – (4.9) могут быть заданы любой из формул (4.1) – (4.4)

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

Пусть в результате кластеризации два кластера S_m и S_q были объединены в один S(m,q) = . Требуется найти расстояние по заданным расстояниям . Используется следующая формула:

(4.11)

где - численные коэффициенты, отражающие специфику процедуры.

Докажем, что при из (4.11) получается формула пересчета расстояний между кластерами, измеряемых по принципу «ближнего соседа» (4.5)

Действительно

поскольку

Аналогично можно показать, что при из (4.11) получаем формулу пересчета расстояния по принципу «дальнего соседа» (4.6)

При и , где n_l = |S_l|, n_m = |S_m|, n_q = |S_q|,

Из (4.11) получаем формулу пересчета расстояния, измеряемого по принципу «средней связи» (4.8)

Для доказательства последнего утверждения получим сначала формулу пересчета обобщенного Колмогоровского расстояния (4.9):

Отсюда при r = 1 получаем доказательство нашего утверждения относительно пересчета расстояния (4.8). Приведенные выше примеры расстояний между кластерами применяются при эвристическом и экстремальном подходах к проблеме кластер-анализа.

Дата добавления: 2015-07-24