4.3.5. Нелинейная классификация

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

другого класса — по другую. Возвращаясь к данным Крейгов (рис. 4.5), сразу видим, что такие гиперплоскости можно провести между точками любой пары карьеров, кроме Наксоса и Пентели. Если нужная гиперплоскость существует, то классы, которые она отделяет, называются линейно отделимыми в пространстве описаний . В этом случае задача распознавания образов сводится к нахождению соответствующих гиперплоскостей. Если какая-то пара классов линейно неотделима, то любой из описанных методов будет неверно классифицировать некоторые объекты исходной выборки.

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

где К достаточно велико. Если известна пара линейно неотделимых классов в можно перейти от к новому пространству координаты в котором задаются всеми возможными функциями

Если граница между двумя классами в описывается функцией вида (61), то эти два класса будут линейно отделимы в Затем изложенные выше методы распознавания образов применяются к задаче в и вычисляется матрица тем самым определяется пространство которое есть не что иное, как образ пространства при линейном преобразовании (Себестиан, 1962, гл. 3).

Трудность этого метода в том, что может потребоваться большой объем вычислений. Размерность пространства растет экспоненциально с ростом а поскольку операции с матрицами требуют вычислений, сложность которых растет экспоненциально с ростом размеров матриц, проблема действительно серьезная. Конечно, на практике встречаются ситуации, в которых существенно нелинейные в пространстве задачи можно решить с довольно малым рис. 4.9 приведен пример, для которого Себестиан получил решение при Разумеется, можно было бы найти также и патологические примеры, где потребовались бы невообразимо большие значения

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

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

Рис. 4.9. Пространство разбито на области, определяемые перекрестными произведениями шестой степени (Себестиан, 1962, рис. 3.8.)

Хотя в распознавании образов обсуждался диалоговый подход (Гарнац и Хант, 1973), однако, неизвестно, применялся ли этот метод и насколько он был бы хорош. Одним из требований для его реализации должна быть разработка методов вывода на дисплей многомерных распределений в виде, удобном для восприятия человеком.

Вторая неформальная процедура состоит в исследовании классов преобразований пространства менее широких, чем множество линейных полиномов. Именно это обычно и делается в статистической классификации. Если известно, что начальные скопления точек не имеют формы эллипсоида, ищут преобразование, приводящее к эллипсоиду, а затем переходят к линейному методу. Это бывает полезно в тех случаях, когда есть какое-то представление о происхождении данных или когда распределение данных не имеет формы эллипсоида. Рассмотрим пример распределения (рис. 4.10, а), полученного равновероятным размещением точек по ординате и

экспоненциальным по абсциссе. На рис. 4.10, б показан результат следующего преобразования: единицей по ординате становится нормальное стандартное отклонение (Хоел, 1970), а по абсциссе — логарифм исходной единицы измерения. Форма скопления приближается к желаемой форме эллипса. Этот подход, основанный на разумном выборе преобразований, вообще принят в распознавании образов и статистике.

Рис. 4.10. (см. скан) Пример нелинейного преобразования: а — исходное распределение; б — преобразованное распределение.

Будучи менее общим методом, чем последовательное построение он может привести к нужным результатам со значительно меньшими затратами на вычисления. Если известна природа данных, нобходимо следить за тем, чтобы применяемое преобразование имело смысл. Этот вопрос тесно связан с упоминавшимся ранее вопросом относительно измерений: если известно происхождение данных, то какие преобразования допустимы?