Объединение и расщепление.
Основной алгоритм можно оиищить, введя в него процедуру образования и разрушения классов в ходе итерационного процесса. Можно или объединить два класса в один класс, или расщепить класс на два разных класса. Объединение и расщепление классов используется в хорошо известном алгоритме автоматической классификации, получившем наименование ISODATA [Болл, 1965а, б]. На каждой итерации этого алгоритма вначале происходит перебрасывание объектов из класса в класс без изменения числа классов. Затем к имеющимся на данный момент классам применяется процедура объединения или расщепления. Процедура объединения объединяет в один класс каждую пару классов, средние векторы которых находятся друг от друга на расстоянии, меньшем заданного порога. Процедура расщепления расщепляет или не расщепляет каждый класс в зависимости от плотности его заполнения и свойств выборочной матрицы коварнации.
Процедуры объединения и расщепления чередуются от итерации к итерации.
Само собой разумеется, что этот алгоритм является эвристическим. Его достоинство заключается в его эффективности и в том, что вмешательство человека в его работу сводится к минимуму.
Многократная дихотомия.
В некотором отношении более предпочтительными являются методы, зависящие целиком лишь от критерия классификации 
Один такой метод предложен в [Ватанабе, 1969] и состоит в следующем.
Предположим, что при 
имеется несколько разных классификаций, дающих почти минимальное значение 
Если эти классификации отличаются лишь классификацией нескольких объектов, то нет причины предполагать наличие белее чем двух классов. Однако, если классификации отличаются намного, то очевидно, что в действительности имеется несколько классов.
На рис. 11.1 показаны две возможные дихотомии множества объектов, состоящего из трех классов 
Первая дихотомия делит объекты на два класса 
вторая — на классы 
Таким образом, видно, что 
— это три разных класса (через А здесь обозначено дополнение множества А).
Рассмотрим теперь более общий случай, когда имеется к дихотомий совокупности объектов, состоящей из М классов. Каждая дихотомия разделяет эти объекты на две группы. Пусть 
— множество всех объектов, отнесенных к группе 
в результате 
дихотомии 
. Предположим, что выполняются следующие два условия:
а) дихотомия относит каждый класс целиком в одну группу, т. е. классы нерасщепляются дихотомией;
б) для каждой пары классов имеется по крайней мере одна дихотомия, которая не относит оба класса к одной и той же группе.
Выберем по одной группе из каждой дихотомии и образуем подмножество С, являющееся пересечением всех к групп. По условию а), если подмножество С содержит один объект, то оно должно содержать все объекты того же класса. По условию б) для любого другого класса имеется по крайней мере одна из к выбранных групп, такая, что этот класс к ней не принадлежит. Поэтому, если С непусто, то С содержит один и только один класс. Следовательно, для того, чтобы построить все М классов, необходимо рассмотреть 
подмножеств вида
где каждое 
принимает значения 1 или 2. Каждое непустое множество С есть класс. Возвращаясь к нашему примеру, имеем
таким образом,
что согласуется с нашим предыдущим рассуждением.
Рис. 11.1. Многократная дихотомия трех классов объектов.
Метод многократной дихотомии имеет более прочную теоретическую основу, чем процедура объединения и расщепления. Кроме того, он не использует никакого другого численного критерия, кроме 
Однако практическая реализация метода многократной дихотомии может оказаться трудной, особенно в тех случаях, когда истинное число классов велико. Эта трудность может быть отчасти преодолена путем организации иерархической структуры на множестве классов. Объекты делятся на небольшое число классов, каждый класс делится в свою очередь, и т. д. При использовании этой стратегии не возникает необходимости
находить все возможные дихотомии всей совокупности объектов.
В этом месте мы отклонились от рассмотрения алгоритма автоматической классификации. Очевидно, это рассмотрение не закончено, однако основа для построения процедур автоматической классификации у нас уже есть. Нам недостает лишь той уверенности в правильности нашего метода, которая была у нас при решении задач распознавания образов с учителем. Обратимся поэтому к детальному рассмотрению критериев качества классификации.
— множество всех классификаций 
объектов на М классов. Наш алгоритм автоматической классификации осуществляет поиск только среди классификаций 
Для большинства критериев 
алгоритм генерирует М непустых классов независимо от выбора М. Поэтому представляется необходимым иметь какой-либо метод выбора числа классов. К сожалению, единой общепринятой теории для определения М не существует. Поэтому нам остается довольствоваться описанием предложенных в разное время эвристических методов решения этой задачи.
