Построение сложных классификаторов для объектов в многомерных пространствах

Аннотация

А.М. Крашенинников, Н.И. Гданский, М.Л. Рысин

Дата поступления статьи: 15.04.2013

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

Ключевые слова: распознавание, классификация, пространство признаков, геометрический метод

05.13.01 - Системный анализ, управление и обработка информации (по отраслям)

Принцип линейной нормальной классификации объектов в многомерных пространствах признаков может быть использован для построения классификаторов в случае множеств сложной структуры, неразделимые в общем случае одной гиперплоскостью. В таких случаях предложено использовать совокупность иерархически связанных нормальных разделяющих гиперплоскостей, которая названа иерархическим нормальным классификатором (ИНК).
Для каждого распознаваемого множества ИНК содержит совокупность нормальных гиперплоскостей , заданных множествами их коэффициентов . Все гиперплоскости   разделены на слои. Число слоев обозначим . Число гиперплоскостей в слое с номером s обозначим через . Набор коэффициентов гиперплоскости из совокупности в слое с номером s, имеющей номер k, будем обозначать как. Для упрощения выражений наряду с вектором координат точек  будем использовать однородные  векторы , у которых на начальной позиции к  добавлена единица.
Алгоритм проверки включения заданной точки пространства  в множество с использованием ИНК, содержащего  слоев, в каждом из которых (с номером s) хранится  гиперплоскостей , заключается в том, что производится перебор по всем слоям s ИНК  от 1 до . Для каждого слоя  s последовательно производится подстановка координат однородного вектора,  во все уравнения плоскостей слоя. При получении первого же неотрицательного значения в скалярном произведении
       (1)
делается вывод о вхождении точки  в множество, выходим из алгоритма с ответом: . Если же во всех скалярных произведениях для гиперплоскостей первого слоя выполняется условие , то проверку необходимо продолжать в следующем слое. После подстановки в условие (1) коэффициентов гиперплоскостей последнего слоя Li проверку завершаем. Если при этом ни одного неотрицательного значения в скалярных произведенияхне было получено, то отсюда следует, что:.
Применение ИНК позволяет решать задачу разделения множеств для совокупностей множеств любой структуры, имеющих сложное относительное расположение в пространстве признаков.ИНК каждого множества  предложено определять путем его разделения с остальными множествами. Поскольку с точки зрения включения точек в  все другие множества одинаковы, то после объединения их можно считать  одним множеством. Таким образом, для практического решения задачи построения ИНК отдельного множества достаточно разработать алгоритм только для пары множеств.
         Для решения задачи построения ИНК отдельного множества в алгоритме для пары множеств предложено использовать две дополнительные операции по разделению множеств – отсечение и бинарную кластеризацию.
Если для пары множестви  не существует единой нормальной разделяющей гиперплоскости, то предлагается выполнить разделение  и  путем повторного применения принципа нормального разделения не к целым множествам, а к их частям.
Нормальную по отношению к межосевому вектору  гиперплоскость, которая отделяет все точки из   и не содержит точек из , назовем отсекающей для  множества  ,а подмножество  - отсекаемым. Аналогично вводится отсекающая плоскость для множества ,. Практически построение отсекающих плоскостей производится перебором массива расстояний их точек до некоторой пробной нормальной плоскости.
Применение только одного нормального разделения и отсечения подмножеств в общем случае недостаточно для решения  задач нормальной классификации множеств сложного вида – как для вложенных множеств, так и в тех случаях, когда отсекаемые множества пусты.        Для преодоления данных затруднений предложено дополнительно применять близкое по назначению к кластеризации разбиение одного из множеств  и  на две части. Его задача - выделение пары максимально сгруппированных подмножеств. Назовем такой способ разбиения и получаемые подмножества для краткости бинарным. Обозначим бинарные подмножества выделенного множества А через .
 Поскольку качество кластеризации повышается с уменьшением радиусов кластеров R₁,R₂ и увеличением межцентрового расстояния  между ними, то в  качестве критерия сгруппированности подмножеств  и  предложено использовать ранее введенную степень разделимости подмножеств , а в качестве меры его оптимальности - максимум. Условие оптимальности получаемого разбиения принимает вид:
 /(,      (2)
В общем случае глобальный экстремум задачи (2) может достигаться не на единственной паре возможных подмножеств . Точное ее решение можно найти перебором всех возможных вариантов разбиения множества на пары непустых подмножеств  и вычислением для них значения  с последующим сравнением полученного значения с текущим максимумом . Обозначим через  число точек в исходном множестве .

Практически точный переборный алгоритм решения задачи (2) реализуется перебором всех кодовых чисел k из отрезка, описывающих все различные варианты разбиения  на подмножества . По k формируются и производится вычисление значения критерия . В качестве оптимального принимается тот вариант разбиения, при котором достигается максимум значений  .
Принимая в качестве характерного параметра задачи число точек  в разбиваемом множестве А, получим, что  сложность точного переборного алгоритма равна , т.е. является экспоненциальной. Поэтому использование точного алгоритма решения задачи бинарной кластеризации для обычных вычислительных устройств возможно только при относительно небольших разделяемых множествах, примерно для значений . 
Практически размер разделяемых множеств  может быть достаточно большим. Также в процессе решения общей задачи классификации данный алгоритм может применять десятки раз. Поэтому основной задачей точного алгоритма является решение тестовых задач, а на практике для бинарной классификации необходимо использовать приближенные алгоритмы, сочетающие более низкую сложность с получением решений, достаточно близких значений критерия качества. У данных алгоритмов условие глобальной оптимальности заменяется локальной оптимальностью, при которой получаемое решение может быть лучшим только для ограниченного подмножества общей области поиска.
Изучение оптимальных решений задачи бинарной кластеризации множеств показывает, что в получаемых оптимальных подмножествах всегда присутствуют по одной точке из какой-либо или из нескольких пар максимально удаленных точек.
Поэтому построение бинарных подмножеств предложено начать с размещения в них точек, между которыми достигается максимальное расстояние. Представители выделенной пары максимально удаленных точек, размещаемые вначале для подмножеств, обозначим через , и назовем начальными. Максимальная удаленность точек и позволяет сделать ряд заключений о местоположении всех других точек А и их возможном включении в подмножества  и . Они могут находиться только внутри пересечения сфер радиусов с центрами в,и.Наиболее простой вариант разделения реализуется с использованием нормальной гиперплоскости pn, проходящей через среднюю точку вектора (,,) (рис.1). Для точек этой гиперплоскости () выполняется условие . Вводя для краткости прямое и обратное отношения  и  представим условие () в виде:
.

Рис. 1. Возможное местоположение точек множества А

К подмножеству   относим те точки  множества А, которые лежат по одну сторону с его начальной точкой , в этом случае              (или .). К подмножеству относим те точки, которые ближе к, для них  (или).
Такой алгоритм разделения прост. Однако при его применении возникает неопределенность в отношении точек, лежащих на граничной плоскости , у которых  (). Также точки, лежащие достаточно близко границе , могут быть не оптимально включены в соответствующее подмножество из-за того, что они близки к другому подмножеству.
Для контроля подобных ситуаций предложено ввести предельную величину отклонения, которая позволяет априорно выделить:
а) множество точек, гарантированно входящих в оптимальное подмножество  при выполнении условия:   ; (либо)  и б) множество точек, гарантированно входящих в оптимальное подмножество , для которых выполняется условие:    ; (либо).
При введенном априорном пограничном значении   возникает пограничный слой, точки которого удовлетворяют условиям:
; .Для них невозможно сразу же сделать заключение о принадлежности к оптимальным множествам   и  . Рассмотрим оценку возможной величины априорного отклонения . Максимальные значения данного отклонения достигаются в модельной ситуации, когда:
- разделяемые точки множества А лежат в одной гиперплоскости (рис.2 а),
- есть две промежуточных группы с центрами и  и довольно большими числами точек N>> 1 на границах возможной области, симметрично расположенные слева и справа относительно крайней точки области , угловые отклонения точек и  соответственно от точек  и обозначим через .
Перейдем для сокращения обозначений к масштабированным координатам, значения которых разделены на величину  и введем в рассмотренной плоскости вспомогательную систему координат с центром в точке   и осью х, проходящей через точку . В ней координаты точек и  следующие:
.

При угле , близком к, и приближении точек  и  к  оптимальным вариантом разбиения будет присоединение обеих промежуточных групп к одной из начальных точек, например, к  (рис.2 б). В этом случае параметры получаемых  множеств ,  и величина критерия будут следующие:
 ;
.
При меньшем угле y и более удаленном взаимном расположении точек  и  оптимальным вариантом разбиения будет присоединение точки  к , а к , (рис.2 в). При этом получим следующие параметры множеств ,  и величину критерия:
;


При пороговом положении точек  и  выполняется равенство: . Отсюда следует условие для порогового значения угла :

Перейдем для упрощения вида выражения к новой переменной :

Условие принимает вид:
.
Умножая обе части на знаменатель левой части и возводя обе части в квадрат, получим:
.
Перенося все слагаемые в левую части и приводя подобные слагаемые, получим кубическое уравнение относительно  :
.
Подстановкой     несложно проверить, что одним из корней будет значение  t= -1. Данное значение на входит в допустимый отрезок [0;4]. Разделив уравнение на (t +1), получим квадратное уравнение относительно  :
.
Его корни:. Условию  удовлетворяет корень        .
Подставляя выражение для  t, получим:
.
При данном значении угла . Ему соответствует теоретическое значение предельной величины отклонения . Поскольку данная величина найдена для предельных, в действительности  не реализуемых вариантов подмножеств точек в А, то для практических расчетов принята величина априорного отклонения  = 0,6. При этом условия априорного включения точки из множества А в подмножества А₁ и А₂ имеют вид, соответственно:
.
Данное правило также предложено применить для последующего после априорного расширения подмножеств А1 и А2. Только для тех точек, к которым  данное правило уже не применимо, применяется переборный принцип разделения.
Рассмотрим приближенный алгоритм решения задачи.

1.  Исходные данные:
1) n - размерность пространства U,
2) nе -  число точек в множестве А, (n1≥2),
3)  А[1:nе][1:n] - массив координат точек множества  А.
2. Решаемые задачи:
1) определение чисел элементов n1, n2 и массивов координат точек в квазиоптимальной паре бинарных подмножеств А₁ и А₂, у которых значение критерия λ(А₁,А₂) близко к глобальному максимуму λ _max;
2) определение центров тяжести C₁,C₂  найденных квазиоптимальных бинарных подмножеств А₁ и А₂.
Приближенный алгоритм бинарной кластеризации (ПАБК).
Шаг 1. Предварительный анализ относительного положения точек  А. Построение матрицы расстояний.Определение min и max расстояний.  Формирование  списка PR[1:P] всех пар максимально удаленных точек. Введение начального значения критерия текущего оптимального разбиения:KR_MIN := 2ρ_max.
Шаг 2. Перебор всех P пар  максимально удаленных точек.  Цикл по параметру s (1≤ s ≤ P) по всем парам максимально удаленных точек.
Шаг 2.1. Начальные присваивания:
а) номера очередных максимально удаленных точек:  m1:= PR[s][1]; m2:= PR[s][2]; 
б) засылка точек m1и m2 в  текущие множества А_1т и А_2т  и центры тяжести`С<sub>1т</sub> и `С_2т;
в) формирование начального  списка координат точек невключенных вершин AN, а также списков расстояний RC1 и RC2 точек  m1и m2 до точек из AN.
   Шаг 2.2. Циклическое наращивание текущих множеств А_1т и А_2т  за счет включения в них близких точек. Во внутреннем цикле просмариваются все невключенные точки. Для них определяется соотношение  D12=RC1[i]/RC2[i]. Если D12<=0.6, то точка из AN включается в А_1т; если D12>=1.67, то точка из AN включается в А_2т. Иначе точка остается в множестве AN.Если произошло включение новых точек в множество А_1т, то корректируется его центр тяжести`С_1т и  список расстояний RC1. Аналогично, если  произошло включение новых точек в множество А_2т, то корректируется его центр тяжести  и  список расстояний RC2.
Шаг 2.3. Оценка результатов наращивания текущих множеств А_1т и А_2т  за счет включения в них близких точек.
Если все точки из AN включены  в  А_1т и А_2т  (решение задачт бинарной кластеризации получено), то запись полученных данных и выход из алгоритма.
Если не все точки из AN включены  в  А_1т и А_2т , то разделение оставшихся выполняется путем перебора вариантов по аналогии с точным решением.
Завершение работы алгоритма.
         Моделирование точного и приближенного алгоритмов производилось на широком наборе множеств. Как правило, результат работы приближенного алгоритма совпадает с разбиением, полученным по точному алгоритму. В специальных модельных случаях значения критерия у приближенного метода хуже, чем у точного примерно на 15 %.
В частности, для модельного множества А ={{0;0}; {1;0};{1;1};{0;1};{0;0,8}; {0,2;1}; {0,25;0,25}; {1,00;0,5}} (рис.3а) в двумерном пространстве признаков точное решение (рис.3 б) дает значение критерия, равное λ_max=1.097.  
Решение: n₁ = 5,  А1 = {{1.0,0.0}; {1,00;0,5};{0.0,0.0};{1.0,1.0}; {0.25,0.25};n₂ = 3, А₂ = {{0.0,1.0},{0.0,0.8},{0.2,1.0}}, полученное по приближенному методу, дает значение критерия λ_max=0.930, что на 15% хуже, чем глобально оптимальное значение.
Применение дополнительных операций отсечения и бинарной кластеризации позволяет построить общий алгоритм разделения множеств произвольной структуры со сложным относительным пространственным положением путем построения иерархических нормальных классификаторов соответствующих множеств.

Литература:

1.  Н.И. Гданский, А.М. Крашенинников. Бинарная кластеризация объектов  в многомерных пространствах признаков   [Текст] // Труды Социологического конгресса. РГСУ. 2012.  –  94-98 с.
2. Н.И. Гданский, М.Л. Рысин, А.М.  Крашенинников, Линейная классификация объектов с использованием нормальных гиперплоскостей [Электронный ресурс] // «Инженерный вестник Дона», 2012, №4 – Режим доступа: http://ivdon.ru/magazine/archive/n4p1y2012/1324 (доступ свободный) - Загл. С экрана. – Яз. рус.
3.  Н.И. Гданский, А.В. Карпов, А.А. Бугаенко. Оптимальное интерполирование типовых динамик в задаче управления с прогнозированием  [Электронный ресурс] // «Инженерный вестник Дона», 2012, №3 – Режим доступа: http://ivdon.ru/magazine/archive/n3y2012/936  (доступ свободный) - Загл. С экрана. – Яз. рус.
4. Л. Г. Комарцова, А. В. Максимов.  Нейрокомпьютеры // Изд-во МГТУ им. Н.Э. Баумана, 2002. — С. 320.
5. Н.И. Гданский, А.М. Крашенинников. Сравнение эффективности методов бинарной кластеризации множество точек-прецендентов [Текст] // Математический методы и приложения: Труды двадцать вторых математических чтений РГСУ. АПКиППРО. 2013. – 59-67 с.
6. Л.Н. Ясницкий. Введение в искусственный интеллект. — 1-е. // Издательский центр «Академия», 2005. — С. 176.
7. Н.И. Гданский, М.Л. Рысин, А.М.  Крашенинников. Применение современных информационных технологий в учебном процессе высшей школы [Текст]: монография // Изд-во РГСУ, 2012, ISBN 978-5-905675-31-7. – С.150.
8. Н.И. Гданский, А.М. Крашенинников, Е. А. Слюсарев. Использование геометрического подхода при построении классификаторов в системах искусственного интеллекта [Текст] // Математическое моделирование в проблемах рационального природопользования. Сборник научных трудов Всероссийской молодежной конференции. РГСУ. 2012. – с.36-43.
9. Structure of  Decision. The Cognitive Maps of Political Elites // Ed. by R. Axelrod. – Princeton: Princeton University Press, 1976. -  405 p.
10. Shapiro M.J., Bonham G.M. Cognitive processes and foreign policy decision-making // International Studies Quarterly. 1973. – P. 147–174.