Выбор модели для машинного обучения классификации данных всегда определяется условиями конкретной задачи и предполагает поиск компромиссного по различным критериям решения. Существующее многообразие методов и алгоритмов [1–4] достаточно полно покрывает пространство встречающихся задач, включающих, например, разработку новых лекарств [5–7], биометрическую идентификацию [8], оценку кредитоспособности [9], геостатистику [10, 11]. Тем не менее, совершенствование методологии и разработка новых идей, предполагающих получение оптимального при имеющихся ограничениях решения, являются актуальной задачей. Рассматриваемый в настоящей работе подход [12, 13] в некоторых случаях позволяет получать более предпочтительные модели, обладающие меньшей средней ошибкой распознавания.В общей постановке задачи обучению классификации требуется построить (обучить) математическую модель (классификатор), аппроксимирующую некоторую зависимость по известному набору данных (обучающему), заданному в виде пар                      (1)где  – d-мерный вектор пространства признаков (объектов) , отождествляемого здесь с Евклидовым пространством , а  – значение (класс) пространства ответов . Важно, чтобы с помощью полученного классификатора можно было бы с приемлемой точностью распознать не только данные обучающего набора, но также и неизвестные. В противном случае модель является бесполезной и называется «переобученной» или не способной к обобщению.  В дальнейшем изложении будет описываться предлагаемый подход на примере разделения двух классов, поскольку обучение модели для  ( больше или равно двум) классов сводится к построению  двухклассовых моделей по схеме «один против всех» – -й классификатор отделяет класс  от классов , где . Также отметим, что приведенные в статье иллюстрации поясняют текст на примерах двумерного пространства, но предлагаемые решения применимы для пространств произвольной размерности.Формализация задачи машинного обучения классификации образов может также интерпретироваться как задача реконструкции гиперповерхности, разделяющей классы в пространстве признаков. В отсутствии какой-либо априорной информации о распределении классов, предпочтительной более обоснованно можно считать равноудаленную от границ классов гиперповерхность. Учитывая недостаточную полноту обучающего набора, дающего возможно лишь приближенное представление об истинном распределении, такой выбор гарантирует наиболее уверенную классификацию объектов обоих классов. Вычисление данной гиперповерхности, обозначаемой здесь и далее , можно свести к задаче вычисления срединной оси (см. [14, 15]) незамкнутой фигуры, состоящей из гиперповерхностей границ классов (см. рисунок рис. 1).Для оценивания граничных гиперповерхностей классов, требуется установить некоторый критерий необходимой сложности их структуры, поскольку при излишней или недостаточной выбранной детальности представления, результирующий классификатор может оказаться не способным к обобщению. В такой постановке вопроса можно пытаться найти наиболее простую возможную форму описания, обеспечивающую максимальный отступ между ближайшими точками различных классов. Приближенное к такому представление может быть получено с помощью многомерной триангуляции Делоне (см. [14, 15]). Рис. 1. Незамкнутая фигура, образованная границами гиперповерхностей (линий) классов, и её срединная осьРассмотрим триангуляцию Делоне  для векторов  обучающей выборки. Симплексы (фигура в d-мерном пространстве, имеющая  вершин, не лежащих в одной гиперплоскости) этой триангуляции, имеющие среди своих вершин точки различных классов, очевидно, располагаются между классами (рис. Рис. 2а) и далее будут называться виртуальными (равно как и их ребра, имеющие вершины в точках различных классов). Предлагается совокупность их вершин считать вершинами гиперповерхностей границ классов, при этом для вычисления срединной оси, как целевой разделяющей гиперповерхности , с использованием такого представления можно применять соответствующие алгоритмы, основанные на триангуляции Делоне [16, 17]. Адаптированный с учетом специфики задачи алгоритм описывался в работе [12].Рис. 2. Представление незамнутой фигуры, образованной виртуальными симплексами триангуляции Делоне Разделяющая гиперповерхность задается в виде совокупности сегментов, где каждый сегмент является сечением виртуального симплекса гиперплоскостью, проходящей через середины виртуальных ребер этого симплекса. Виртуальные ребра симплекса определены множеством пар его вершин                         (2)то множество вершин соответствующего симплексу сегмента задается как (3)где  и  – вершины симплекса, являющиеся элементами первого и второго классов. Отдельно заметим, что общее число вершин, определяемое произведением  оценивается как                   (4)где  – целая часть значения, заключенного в скобки.В рассматриваемом подходе сегмент задается пересечением  полупространств , ограниченных проходящими через его стороны гиперплоскостями, с гиперплоскостью , в которой он лежит (Рисунок 3).Рис. 3. Представление сегмента:  –полупространства, проходящие через стороны сегмента,   – плоскость, в которой лежит сегмент Формально сегмент можно описать в виде множества точек (5)или, подставив соответствующие неравенства полупространств и уравнение гиперплоскости, и обозначив через   операцию скалярного произведения некоторых векторов  и : (6)где  – нормальные векторы гиперплоскости  и ограничивающих полупространства  гиперплоскостей  соответственно,  – смещение  от начала координат.Для вычисления параметров уравнения гиперплоскости  в d-мерном пространстве находятся  некомпланарных точек среди вершин сегмента. Для исключения полного перебора всех возможных вариантов, предлагается выбирать комбинацию из вершин сегмента, вычисленных из виртуальных ребер, множество концевых точек которых включает все вершины симплекса. В качестве гиперплоскостей, ограничивающих полупространства , выбираются гиперплоскости, проходящие через грани симплекса, и для определения параметров неравенств полупространств используются вершины этих граней.Рассмотрим применение разработанного метода для классификации объектов. Очевидно, что данная задача сводится к определению положения относительно гиперповерхности произвольной точки, для чего предлагается использовать адаптированный метод трассировки луча (even-odd rule) [14]. В отличие от оригинального алгоритма в измененной версии устанавливается, лежит ли распознаваемая точка  с той же стороны, относительно гиперповерхности, что и некоторая точка . Как следствие, если известно, к какому классу принадлежит , что можно обеспечить, выбрав её из обучающей выборки, можно указать и класс точки . Формально идея заключается в определении числа пересечений отрезка прямой линии  с сегментами гиперповерхности. При четном количестве пересечений или их отсутствии точка  находится с той же стороны, что и  (см. рис. Рис. 4(а) и Рис. 4(б)), при нечетном – с разных (рис. Рис. 4(в)).  Рис. 4. Идея определения положения точки  относительно разделяющей гиперповерхности: при четном количестве пересечений (а) или их отсутствии (в) точка  лежит с той же стороны, что и , а при нечетном (б), соответственно, по разные. Для проверки пересечения отрезка и сегмента вычисляется точка пересечения отрезка с плоскостью  сегмента, и, если она принадлежит полупространствам , принимается, что пересечение есть. Формально данное условие записано в  (5) и  (6). Отдельно следует обсудить случай, когда отрезок проходит через грань сегмента. Следуя общей рекомендации для классического алгоритма трассировки луча, выполняется малое смещение (поворот) рассматриваемого отрезка прямой линии в произвольную сторону так, чтобы было или явное пересечение, или его отсутствие. В целом такие действия не влияют на точность результата. В данной работе также предлагается смещать отрезок не в произвольном направлении, а в направлении нормали гиперплоскости, задающей грань, через которую проходит отрезок. Тем самым доставляется пересечение с сегментом, что повышает точность классификации в случае прохождения отрезка через краевые сегменты разделяющей гиперповерхности.Качество получаемого описанным методом классификатора сильно зависит от полноты и качества представленной для обучения выборки, поэтому существует вероятность получения модели, не способной к обобщению для распознавания неизвестных объектов. Эффективным статистическим подходом снижения такого риска является поиск модели, оптимальной по двум противоречивым критериям – количеству ошибок на обучающем наборе и её сложности [18, 19]. Второй критерий выбирается из априорных предположений о целевой функции, например, что она должна быть гладкой или, что её параметр по модулю не должен превышать некоторого значения. Поскольку в предлагаемом методе используется геометрический подход к построению классификатора, его трудно явно свести к такой постановке. Однако, применяя методы сглаживания поверхностей, использующие информацию о смежных точках, при различных конфигурациях параметров, можно получить более предпочтительное исходному решение. В настоящей работе для достижения поставленной цели рассматривается метод Лапласа (Laplacian smoothing) [20–22].Пусть поверхность задана в виде , где  содержит её вершины , а  определяет множества пар индексов связанных между собой точек (ребра), а также для каждой из вершин известны индексы смежных точек          (7)Обозначив исходный набор точек как , метод сглаживания Лапласа на итерации  можно формализовать в следующем виде:             (8) где   – операция определения числа элементов (мощности) множества, заключенного в скобки, а  и  – параметры сглаживания, определяющие количество итераций и величину (вес) смещения соответственно. Как видно, приведенные формулы .          (7) и             (8) не зависят от размерности поверхности сглаживания, поэтому их можно применять в пространствах произвольной мерности.Используемое представление разделяющей гиперповерхности не позволяет корректировать позиции вершин сегментов, поскольку, согласно                    (4) их может быть больше чем размерность пространства. Переместив какую-нибудь из них, возникнет неоднозначность при определении сегмента, так как его вершины будут лежать в разных гиперплоскостях. Поэтому предлагается сглаживать не разделяющую гиперповерхность, а граничные гиперповерхности классов, получаемые с помощью многомерной триангуляции Делоне (см. рис. 2). При этом также решается и задача нахождения смежных точек – точки одного класса, являющиеся вершинами виртуального симплекса, будут смежными друг другу. Подбор параметров сглаживания требует выполнения ряда тестов для получения приемлемого результата [13]. В ходе экспериментов установлено, что для многих задач достаточно 2-10 итераций сглаживания, а величина  лежит диапазоне   и обратно пропорциональна количеству итераций .Для определения практической значимости предложенного подхода разработана его программная реализация с использованием объектно-ориентированного языка программирования Java в свободно распространяемой среде программирования с открытым исходным кодом Eclipse IDE for Java Developers версии Luna Service Release 2 (4.4.2), предоставляющей широкие возможности и удобный интерфейс для решения поставленной задачи. Тестирование проводилось на реальных данных, доступных в базе данных UCI [23]. В силу существующих ограничений рассматриваемого метода выбирались наборы данных, имеющих до восьми признаков, описание которых отражено в таблице ниже. Таблица 1Используемые для тестирования наборы данных, доступные в базе UCIНаименованиеКоличество признаковКоличество классовРазмер выборкиТип данныхBalance Scale43625категориальныеBanknote Authentification421372вещественныеHaberman’s Survival32306целыеIris43150вещественныеQualitative Bankruptcy62250категориальныеSkin Segmentation32245057вещественныеBlood Transfusion Service Center42748вещественные   Из исходного набора данных 70% элементов использовались для обучения, а оставшиеся 30% для тестирования модели. В качестве аналогов использовались известные реализации различных моделей классификации, включенные в свободно распространяемые программные библиотеки WEKA [24] и LIBSVM [25]. В частности, применялись метод опорных векторов (SVM) с радиальной базисной функцией в качестве ядра, метод k-ближайших соседей (kNN), обучаемые алгоритмом C4.5 решающие деревья (J48), метод «Random forest» (RF), ансамблевый алгоритм (бустинг) AdaBoost. Оптимальные параметры, при которых достигалась наибольшая точность классификации для каждой модели подбирались экспериментально. Полученные результаты приведены в табл. Таблица 2.Как видно из таблицы на некоторых наборах данных точность модели, построенной предложенным методом, выше, чем у аналогов. Наибольшее преимущество достигается при распознавании классов, описываемых вещественными признаками.Рассмотренный выше подход наиболее близок к методу ближайшего соседа. Действительно, разбиение пространства признаков, полученное методом ближайшего соседа, соответствует двойственной триангуляции Делоне структуре – диаграмме Вороного (см. [14, 15]), использование которой для аппроксимации срединной линии и привело бы к идентичному методу (рис. 5).   Таблица 2Точность классификации различных алгоритмов на наборах реальных данных, доступных в базе UCIНаименованиеHSABJ48RFkNNSVMBalance Scale      Banknote Authentification      Haberman’s Survival      Iris      Qualitative Bankruptcy      Skin Segmentation      Blood Transfusion Service Center        Рис. 5. Разделение точек классов с помощью Диаграммы Вороного. Серая линия показывает разделение с помощью предлагаемого методаОднако, точность распознавания классификатора, получаемого выбранным способом, на разных выборках превышает точность метода ближайшего соседа и его обобщения – метод k ближайших соседей. Применяя метод сглаживания Лапласа можно избежать проблемы переобучения, хотя данная процедура требует проведения экспериментов для подбора параметров, что повышает время обучения.Область применения предложенного метода ограничена пространствами 2–8 измерений. Данное утверждение отталкивается от верхней оценки количества симплексов триангуляции  [26] (где  означает округление  к большему целому числу), откуда видно, что уже для 100 точек (которых может быть недостаточно для адекватной оценки существующей зависимости) в пространстве с девятью измерениями будет порядка  симплексов. Несмотря на указанное ограничение, метод может эффективно применяться в некоторых задачах классификации, включающих классы со сложными линейно неразделимыми конфигурациями их пространственных образов.