Алгоритмы, порождающие разбиения

Среди алгоритмов, производящих кластеризации типа разбиений, положительно зарекомендовавших себя при обработке естественнонаучных данных, в литературе отмечаются итеративные методы. Приведенное ниже описание этих методов дано в соответствии с работами (Мандель, 1988, Факторный, дискриминантный и кластерный анализ, 1989).

Большинство итеративных методов группировки работает следующим образом.

1. Начать с исходного разбиения данных на некоторое заданное число кластеров; вычислить центры тяжести этих кластеров.

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

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

4. Шаги 2 и 3 повторяются до тех пор, пока не перестанут меняться кластеры.

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

Несмотря на свои привлекательные черты, итеративные методы группировки имеют две существенные особенности, если не сказать недостатка: а) необходимость задавать число кластеров; б) зависимость результата кластеризации от начального разбиения.

Есть два основных способа начать итеративный процесс: определить начальные точки или подобрать подходящее начальное разбиение. Начальные точки – это центры тяжести кластеров на первой итерации. Когда используются начальные точки, то при первом просмотре точки данных приписываются к ближайшим центрам тяжести кластеров. Задание начального разбиения требует детального распределения данных по кластерам. В этой процедуре центр тяжести каждого кластера определяется как многомерное среднее объектов кластера. Начальные разбиения могут выбираться случайным образом или же задаваться каким-либо образом самим пользователем (например, пользователь может взять в качестве исходного разбиения решение, совпадающее с одним из уровней иерархической кластеризации). Вряд ли стоит подробно обсуждать ситуацию, когда начальное разбиение задаётся случайным путём. Более предпочтительно задавать центры тяжести ожидаемых кластеров из числа наиболее «типичных» объектов тех классов, которые хотелось бы выделить.

 

7. Заполнение пропусков в таблицах

Среди существующих алгоритмов решения этой задачи можно (с известной долей условности) выделить два больших класса:

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

2) основанных на применении аппарата «классических» теории вероятностей и математической статистики.

В первом классе в случае одиночного пропуска эта задача может решаться, например, сведением к решению задач (а-в) (Машинные методы …, 1976). К какой именно задаче целесообразно сводить, определяется типом шкалы измерения признака. Так, если признак бинарный, то заполнение одиночного пропуска может быть сведено к решению задачи распознавания с двумя классами обучения; если ранговый или количественный – к решению задачи упорядочения. Если признак номинальный и число принимаемых им значений «не слишком велико» – к решению задачи распознавания с числом классов, большим двух. При этом учитывается вся информация, содержащаяся в таблице. Точно такая же ситуация имеет место, когда все пропуски сосредоточены в одном столбце.

В случае нескольких пропусков, расположенных в различных столбцах, свести к решению типовых задач (а-в) без удаления из таблицы объектов или признаков с пропусками невозможно. Поэтому для такого случая разработаны специальные алгоритмы заполнения нескольких пропусков с учётом всей информации, содержащейся в таблице. Причём эти алгоритмы не используют предположений о существовании и виде функций распределения. По крайней мере у некоторых из них не просматривается очевидной связи с методами, предназначенными для решения типовых задач (а-в) (см., например, (Методы анализа данных…, 1985) и др.)).

Ко второму классу относятся алгоритмы, целиком основанные на применении «классического» аппарата теории вероятностей и математической статистики. С одной стороны, предлагаются, например, откровенно примитивные приёмы типа заполнения пропусков средним значением признака на анализируемой выборке (такой приём реализован, в частности, в программном продукте Statistica for Windows). С другой стороны, в теории вероятности и математической статистике есть направление, в рамках которого разработаны методы и алгоритмы, основанные на предположениях о существовании и конкретном виде многомерных вероятностных распределений значений признаков на исследуемом множестве объектов (Литтл, Рубин, 1990). Приведём в упрощённом виде типичную для этого направления постановку. На бесконечной генеральной совокупности S признаки X₁, X₂ имеют двухмерное нормальное распределение. Дана выборка S₁,…,S_m из этой совокупности. Для некоторых пар X₁(S_i),X₂(S_i), где 1≤i≤ m, не известны значения X₁(S_i) либо X₂(S_i) (т.е. у одних пар известны оба значения, у других известно только значение X₁, у третьих – только значение X₂). Требуется заполнить эти пропуски.