5. Эталонные точки

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

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

Во-первых, целесообразно подразделение всех задач кластер-анализа на два основных типа Б₁ и Б₂ в зависимости от объема п сово­купности классифицируемых наблюдений Х₁, Х₂, ..., Х_n.

К типу Б₁ отнесем задачи классификации сравнительно небольших по объему совокупностей наблюдений, состоящих, как правило, не более чем из нескольких десятков наблюдений. Сюда, по-видимо­му, могут быть отнесены задачи классификации некоторых макро­объектов, таких, как страны, города, фирмы, предприятия, типы тех­нологических процессов и т. п.

К типу Б₂ будем относить задачи классификации достаточно боль­ших массивов многомерных наблюдений (n — порядка нескольких сотен и тысяч; классификация индивидуумов, семей, изделий, неко­торых промышленных и технических микрообъектов). Подобнее разделение задач классификации на два типа хотя и условно, но весь­ма необходимо, и в первую очередь с точки зрения принципиально­го различия идей и методов, на основании которых конструируются кластер-процедуры в том и в другом случае. Например, для задач типа Б₂ целесообразно построение процедур последовательного типа, обладающих достаточно хорошими, хотя бы асимптотическими по n свойствами.

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

а) число классов априори задано;

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

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

Под иерархическим деревом понимается последовательность пар где , где ν_i - строго возрастающая или строго убывающая последовательность, S⁽ⁱ⁾ — разбиение объектов на классы, соответствующие уровню ν_i (i = 1, ...,t).

a) Рис.3.3 б)

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

а) алгомеративное дерево; б) дивизимное дерево

Иерархическое дерево может быть двух типов. Если S⁽¹⁾ — разбие­ние, состоящее из n одноэлементных классов, а каждый класс разбие­ния S⁽ⁱ⁺¹⁾ является объединением одного или более классов разбие­ния S^{i) и разбиение S^(t) содержит один класс, то иерархическое де­рево называется агломеративным. Если же S⁽¹⁾ — разбиение, состоящее из одного класса, совпадающего с мно­жеством всех исходных наблюдений, а каждый класс разбиения S^{i) является объединением одного или более классов разбиения S⁽ⁱ⁺¹⁾, то — дивизимное иерархическое дерево.

На рис. 3.3 схематически изображены два типа иерархических деревьев. Каждая вершина дерева изображает класс объектов.

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

— процедуры иерархические (агломеративные и дивизимные). Предназначены в основном для решения задач типа (в). Что касается объема классифицируемой совокупности, то формально иерархические процедуры применимы и для задач Б₁ и для задач Б₂. Однако поскольку эти процедуры основаны на переборе элементов матрицы расстоя­ний ρ(X_i,X_j) (или матрицы соответствующих мер близости), то конст­руктивно реализуемыми их можно признать лишь в пределах задач типа Б₁. Следует отметить, что иерархические процедуры применяются иногда и для решения задач типов Б_1а и Б_1б (см. ниже);

— процедуры параллельные. Предназначены для решения задач типов Б_1а и Б₁₀. Они реализуются с помощью итерационных алгорит­мов, на каждом шаге которых одновременно (параллельно) исполь­зуются все имеющиеся у нас наблюдения;

— процедуры последовательные. Предназначены в основном для решения задач типов Б_2а и Б_2б. Они реализуются с помощью итера­ционных алгоритмов, на каждом шаге которых используется лишь небольшая часть, например одно из исходных наблюдений, а также результат разбиения на предыдущем шаге.