5.4. АЛГОРИТМ

5.4.1. Напоминание сущности метода центра тяжести

Так называемый вариант «центра тяжести» метода динамических сгущений можно кратко объяснить следующим образом. Его цель — добиться такого разбиения облака на классов, при котором внутриклассовая инерция была бы минимальной. Чтобы это сделать, на базе некоторого начального разбиения строится последовательность разбиений, где каждое новое разбиение получают путем

отнесения каждой точки к классу с наименее удаленным от нее центром тяжести. Эта процедура итерируется до. сходимости критерия, т. е. последовательности

Реализация МДС на неполных количественных данных происходит по той же схеме.

5.4.2. Пространство представительств

Как и в случае варианта центра тяжести МДС на полных данных, пространством представительств здесь является пространство В самом деле, именно псевдоцентр тяжести каждого класса будет наилучшим образом «представлять» свой класс во всех случаях, когда этот центр будет вычислимым. Однако было уже показано, что по своей конструкции это есть элемент из откуда получаем

Чтобы окончательно снабдить структурой представительств, нам остается задать отображение пространства на неотрицательную числовую полуось (см. 1.2.2), которое будет служить мерой сходства между элементами пространств В интересующем нас случае это отображение определяется так:

Мы знаем, что Следовательно, есть элемент пространства С другой стороны, оправдывается название «мера сходства», поскольку мы видели, что речь идет об аппроксимации квадрата евклидова расстояния между

5.4.3. Критерий

Цель метода — найти разбиение на классов, которое наилучшим (в определенном смысле) образом разделяет классы. Мы видели (см. 5.3.4), что данному разбиению можно поставить в соответствие величину -межклассовую псевдоинерцию разбиения, которая является показателем взаимной удаленности классов друг от друга, а также величину внутриклассовую псевдоинерцию разбиения, которая есть показатель концентрации элементов одного класса вокруг своего псевдоцентра тяжести.

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

где полная псевдоинерция анализируемого облака, т. е. независимая от разбиения константа. Следовательно, минимизация эквивалентна максимизации В.

В дальнейшем условимся искать разбиение на классов, минимизирующее внутриклассовую псевдоинерцию Договорившись об этом,

определим критерий более точно. Чтобы вычислить необходимо иметь в наличии разбиение множества на классов, т. е. иметь один элемент пространства (которое определяет нам множество псевдоцентров тяжести и один элемент пространства раз).

Итак, можно рассматривать как вполне определенное отображение:

где классов, определенных разбиением псевдоцентры тяжести этих классов, -мера сходства, определенная в 5.4.2.

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

5.4.4. Функция представительства

Функция представительства определяется как отображение пространства разбиений в пространство представительств Другими словами, функция представительства это функция, которая каждому классу разбиения ставит в соответствие свой псевдоцентр тяжести.

Однако возникают сложности в связи с тем, что эти псевдоцентры тяжести не всегда вычислимы, т. е. некоторым разбиениям мы не сможем поставить в соответствие псевдоцентры тяжести, и метод нельзя реализовать; в этом случае алгоритм МДС останавливается. В 5.5 мы увидим, что это происходит очень редко.

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

5.4.5. Функция назначения

Функция назначения выражается так же, как при большинстве методов типа МДС, т.е. «назначает» элемент в класс тогда и только тогда, когда

Подобное задание отображения определяет классы единственным образом.

Напомним, что в силу 5.2.2.3 все псевдорасстояния, которые здесь сравниваются, сравнимы.

5.4.6. Сходимость

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

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

Так же как при обычном МДС, достигнутый оптимум есть локальный оптимум, и он зависит от начального разбиения.