Рассмотрим множество из m элементов wОW. Известно, что разбиением называется совокупность K попарно непересекающихся подмножеств W₁,...W_K, объединение которых образует исходное множество W. Пусть элементы w_i представлены векторами x_i = (x_i1,…x_in) в некотором n-мерном пространстве. В задачах кластер-анализа их называют объектами, расположенными в n-мерном пространстве признаков (измеренных характеристик). Объекты образуют строки матрицы X(m,n), а их разбиение называют кластеризацией (классификацией).

В задачах кластер-анализа признаков элементами являются признаки, расположенные в n-мерном пространстве объектов (актов измерений). Очевидно, что признаки образуют столбцы в той же матрице X(m,n). Здесь нам удобно будет считать, что признаки образуют строки другой матрицы X(m,n), полученной после транспонирования исходной матрицы и переобозначения ее размерностей. Разбиение признаков обычно называют группировкой.

Сходство пары объектов обычно оценивают евклидовым расстоянием между ними, а сходство пары признаков – их взаимной корреляцией. Пусть матрица D(m,m) является матрицей попарного сходства элементов w в соответствующем пространстве.

Пусть выполнено некоторое разбиение множества W. Обычно каждому подмножеству W_i можно сопоставить некоторый элемент v_i, который является наиболее типичным для него в некотором смысле. Назовем такой элемент представителем данного множества. В общем случае представитель v_i может и не совпадать ни с одним элементов из W_i. Например, в задаче кластеризации представителем часто назначается средний вектор z_i по подматрице X(m_i,n), а в некоторых задачах группировки (экстремальная группировка) таким представителем назначается первая главная компонента подматрицы D(m_i,m_i) – в этом случае компоненты представителя вычисляются немного сложнее.

• Вычисление представителя группы. Пусть a_i = (a_is, s=1,…m_i) – первая главная компонента, l_i – максимальное собственное число корреляционной матрицы D(m_i,m_i) группы признаков W_i. Тогда вектор (l_i)^1/2a_i определяет корреляции d(f_i,x_j) фактора группы f_i = (f_i1,…f_in) со своими признаками x_j = (x_j1,…x_jn). Корреляции фактора f_i с признаками других групп W₁,...W_i–1, W_i+1,…W_K определяются как d(f_i,x_j) = (1/n)f_ix_j^T = (l_i)^-1/2a_id_j^T, где d_j=(d_js, s = 1,…m_i) – часть строки j матрицы D(m,m), где сама строка соответствует признаку x_jПW_i, а ее элементы соответствуют признакам группы W_i. Обозначив корреляции фактора f_i со всеми признаками вектором g_i = (g_i1,…g_im), получим компоненты представителя как значения на оси этого фактора z_i = f_i = g_iX.

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

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

Теперь нам удобно сформулировать базовый алгоритм разбиения некоторого множества W на заранее заданное число K подмножеств W_i.

Алгоритм 1. Назначим некоторым способом K представителей, например, как K самых несходных друг с другом элементов. На очередном шаге s выполним разбиение, просматривая все элементы w и относя их к тому множеству W_i, с представителем которого они сходны более всего. Если разбиение оказалось смещенным, то назначим центры множеств W_i представителями и перейдем к шагу s=s+1. Алгоритм останавливается при несмещенном разбиении.

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

Заметим, что при K=2 представители в базовом алгоритме определяются наиболее просто – это пара элементов, соответствующая экстремальному значению в матрице сходства D (максимальное для расстояний и минимальное по модулю для корреляций значения). Построим неиерархический дивизимный алгоритм разбиения.

Алгоритм 2. На каждом шаге, начиная с K=1, возьмем наименее плотное подмножество W_k и назначим в нем представителями пару самых непохожих элементов. Алгоритмом 1 разобьем W_k на два подмножества, обозначив их как W_k и W_K+1. Для K+1 подмножеств в полученном разбиении назначим представителями K-1 ранее полученных представителей v₁,…v_k-1, v_k+1,…v_K и двух новых представителей v_k и v_K+1. Вновь разобьем все множество W на K+1 подмножеств алгоритмом 1. Перейдем к шагу K=K+1. Алгоритм останавливается при K=m.

Данный алгоритм строит полную последовательность разбиений, начиная с единственного множества W₁=W и заканчивая одноэлементными множествами W₁,...W_m. В общем случае не все разбиения в построенной последовательности являются иерархически вложенными. Очевидно, что два последовательных разбиения на K и K+1 подмножеств образуют иерархию, если разбиение наименее плотного подмножества W_k на два W_k и W_K+1 сразу дает несмещенное разбиение W₁,...W_K+1. В этом случае назовем предыдущее разбиение на K подмножеств устойчивым.

Рассмотрим элементы w как объекты. Очевидно, что на множестве W определен граф кратчайшего незамкнутого пути (минимальное покрывающее дерево). Если рассмотреть элементы w как признаки, то также очевидно, что на множестве W определен граф максимального незамкнутого корреляционного пути. Будем говорить, что на множестве W определен незамкнутый граф максимального сходства.

Теорема. Пусть неиерархическим дивизимным алгоритмом построено дерево разбиений. Тогда оно эквивалентно незамкнутому графу максимального сходства.

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

Очевидно также, что общую последовательность разбиений можно ограничить, отбросив разбиения с малонаполненными кластерами (группами), начиная с некоторого значения K, приближающегося к размеру выборки m. При малых K можно отбросить разбиения с рыхлыми кластерами. Например, в задаче кластеризации можно отбросить разбиения, у которых средняя дисперсия кластеров превышает дисперсию их центров. Аналогично следует поступить и в задаче группировки. Тогда оставшиеся разбиения будут представлять компактные кластеры, соответствующие одному из общепринятых эвристических определений.

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

Несложно построить и агломеративный вариант алгоритма неиерархических разбиений. Его свойства достаточно очевидны.

Ниже мы покажем применение метода неиерархических разбиений в другой важной задаче кластер-анализа – обработке пропусков в данных.

	часть 1 (RUS/ENG)  часть 2 (RUS/ENG)  часть 3 (RUS/ENG)  Пример