4.3.2. Классификация на основе максимизации сходства внутри множества

В нашем первом методе, основанном на близости описаний, пространство деформируется так, чтобы минимизировать среднее квадрата расстояния между точками множества, т. е. Мы проиллюстрируем этот метод с помощью данных, относящихся к карьеру Парос. Исходные измерения показаны на рис. 4.6,а.

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

Оно гарантирует, что единичный гиперкуб будет иметь одинаковые объемы в и Для того чтобы удовлетворялось равенство (46) и в то же время мера была минимальной, пространство должно быть таким, чтобы множество X напоминало сферу, а не

Рис. 4.6. Преобразование множества Парос от исходного к наилучшему: X — известные данные, Y — неизвестные фрагменты. Обратите внимание на изменение масштабов.

эллипсоид. Соответствующий результат преобразования показан на рис. 4.6, б. Какая же матрица преобразования обеспечивает такую деформацию пространства

Как графически, так и алгебраически, рассматриваемое преобразование можно провести в два этапа. Они отражены на рис. 4.7, а — в, построенном на основе данных карьера Парос. Предполагается, что в пространстве точки скопления образуют эллипс. Первый этап — определение осей этого эллипса (прямые на рис. 4.7, а) и поворот осей к осям эллипса. Получившиеся в результате пространство и множество точек в нем показаны на рис. 4.7, б.

Очевидно, что при повороте объем не изменился. Меняя теперь масштаб по каждой из осей пространства мы просто сжимаем его вдоль одной оси и растягиваем вдоль другой. На рис. 4.7, в изображены это новое пространство и новое множество X, превратившееся из эллипса в окружность. Здесь важно подобрать растяжение и сжатие так, чтобы объем остался прежним.

Рассмотрим алгебраические операции, требуемые для преобразования пространства в Пусть множество X состоит из точек, и пусть нужно минимизировать Определим -матрицу задав ее элементы в виде

где средние значения соответственно компоне точек Отметим, что дисперсия измерения в множестве X равна

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

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

Чтобы перейти от к надо изменить масштабы, выполняя при этом требование постоянства объема. Изменение масштабов обеспечивается диагональной матрицей А, ненулевые элементы которой равны

В результате такого преобразования масштаб должен стать мелким по осям, где были небольшие отклонения между точками данного класса, и крупным — по осям, где отклонения были большими. Итак, поворот и последующее изменение масштабов описываются матрицей преобразования

На этом этапе распознавания образов для каждого класса объектов, представленных в выборке, определяется отдельное пространство. Пусть — пространство, соответствующее классу На этапе классификации предъявляется новый объект у, который отображается в каждое из пространств Расстояние от до определяющего множества рассматривается в том же пространстве. Иными словами, если для определения использовалось множество X, то вводится мера расстояния и точка у относится к классу тогда и только тогда, когда

Чтобы закончить иллюстрацию этого метода, подсчитаем соответствующие оценки сходства для всех фрагментов скульптур и всех образцов из карьеров, представленных Крейгами. Результаты приведены в табл. 4.2. Интересно сравнить эти классификации с классификациями, сделанными Крейгами, очевидно, на основе просто зрительного изучения рис. 4.6.