Кластерный анализ данных и выбор объектов-эталонов в задачах распознавания с учителем

Вычислительные технологии

Том 20, № 6, 2015

Кластерный анализ данных и выбор объектов-эталонов в задачах распознавания с учителем

Н.А. Игнатьев

Национальный университет Узбекистана, Ташкент *Контактный e-mail: n_ignatev@rambler.ru

Рассматривается метод разбиения обучающей выборки на непересекающиеся группы объектов на базе свойства связанности их по определяемому подмножеству граничных объектов классов. Разбиение на группы используется для поиска покрытия выборки объектами-эталонами. Описывается формирование нового признакового пространства для представления объектов путем нелинейного отображения непересекающихся наборов признаков на числовую ось.

Ключевые слова: распознавание образов, логические закономерности, кластерный анализ данных, оболочка классов, объекты-эталоны.

Введение

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

Проблема формирования подмножеств информативных объектов и признаков, которые отражают закономерности обучающей выборки лучше, чем наборы исходных объектов и признаков, затрагивалась в [2]. Предлагалось для описания классов набором эталонных объектов ("столпов") использовать функции конкурентного сходства (Fris-функции). Каждый столп защищал свою часть выборки — кластер, который определялся по значению функции конкурентного сходства относительно ближайшего объекта из противоположного класса.

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

© ИВТ СО РАН, 2015

признаков не нашла отражения в демонстрации монотонности неубывания ее (оценки) значений при снижении размерности признакового пространства и невозрастании числа объектов-эталонов (столпов) классов.

На исследование структуры выборки с целью обнаружения логических закономерностей ориентирован геометрический подход на основе локальных метрик [3]. Отображения исходного признакового пространства в пространство размерности не выше к (к < 3) относительно определяемых экспертами центров позволяет получать визуальные представления отношений между объектами выборки. По результатам визуализации эксперты могут проводить селекцию выборки путем удаления шумовых объектов, делать выводы относительно устойчивости обнаруженных логических закономерностей. Анализ геометрической структуры данных методом локальной геометрии не имеет готовых шаблонов и реализуется известными методами и алгоритмами, использующими геометрическое описание данных [4].

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

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

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

1. О покрытии обучающей выборки объектами-эталонами

Рассматривается задача распознавания в стандартной постановке. Считается, что задано множество Е0 = {¿1,..., Sm} объектов, разделенное на 1(1 > 2) непересекающихся

i

подмножеств (классов) К1,... , К\, Е0 = У Ki. Описание объектов производится с помо-

г=1

щью набора из п разнотипных признаков X(п) = (х1,..., хп), £ из которых измеряются в интервальных шкалах, (п — £) — в номинальной. На множестве объектов Е0 задана метрика р(х, у).

Обозначим через L(E0, р) подмножество граничных объектов классов, определяемое на Е0 по метрике р(х, у). Объекты Si, Sj Е Kt, t = 1,... ,1, считаются связанными между собой (Si О Sj), если

{S Е L(Eo, р) | p(S, Si) < гг and p(S, S,) < r3} = 0,

где Ti(rj) — расстояние до ближайшего от Si(Sj) объекта из CKt (CKt = Е0\Kt) по метрике р(х,у). Множество Gtv = {SV1,... , SVc}, с > 2, Gtv С Kt, v <| Kt |, представляет

область (группу) со связанными объектами в классе Kt, если для любых SUi ,SVj Е Gtu существует путь SVi О SVk О • • • О SVj. Требуется определить:

— минимальное число групп из связанных объектов по каждому классу Kt, t =

— минимальное покрытие множества Е0 объектами-эталонами для алгоритмов распознавания по прецедентам.

Минимальное число групп связанных объектов классов определяется на основе предобработки данных. Предобработка данных заключается:

— в выделении оболочки — подмножества граничных объектов классов L(E0,p) по заданной метрике р [5];

— описании объектов каждого класса по своей системе бинарных признаков.

Для выделения оболочки классов для каждого Si Е Kt, t = 1,... ,1, построим упорядоченную по р(х,у) последовательность

Si0 ,sh,..., Sim_1, Si = Si0.

Пусть Siß Е CKt — ближайший к Si объект из (1), не входящий в класс Kt. Обозначим через O(Si) окрестность радиуса Ti = p(Si,Siß) с центром в Si, включающую все объекты, для которых p(Si,SiT) < Ti,T = 1,... ,ß — 1. В O(Si) всегда существует непустое подмножество объектов

А, = {Я Е 0

m

По (2) принадлежность объектов к оболочке классов определяется как L(E0, р) = У Aj.

i=1

Множество объектов оболочки из KtC\L(E0, р) обозначим как Lt(E0, р) = {$1,... , S"}, к > 1. Значение к = 1 однозначно определяет вхождение всех объектов класса в одну область. При к > 2 преобразуем описание каждого объекта Si Е Kt в Si = (уi1,... ), где

J 1, p

Пусть по (3) получено описание объектов класса Kt в новом (бинарном) признаковом пространстве, П = Kt; 9 — число не пересекающихся между собой групп объектов; Si V Sj, Si Л Sj — соответственно операции дизъюнкции и конъюнкции по бинарным признакам объектов Si, Sj Е Kt. Приведем пошаговое выполнение алгоритма разбиения объектов Kt на непересекающиеся группы G\,..., Ge.

Шаг 1. в = 0.

Шаг 2. Выделить объект S Е П, в = в + 1, Z = S, Ge = 0.

Шаг 3. Выполнять Выбор S Е П and SЛZ = true, П = Q\S, Ge = GeUS, Z = ZVS,

пока {S Е П | S Л Z = true] = 0.

Шаг 4. Если П = 0, то идти 2.

Шаг 5. Конец.

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

проводится с целью упорядочения процесса отбора объектов-эталонов минимального покрытия и цензурирования обучающей выборки.

Цензурирование обучающей выборки необходимо для определения обобщающей способности алгоритмов распознавания. Улучшение качества решающих правил возможно через селекцию объектов оболочки классов и обновление ее состава. Детальное исследование обобщающей способности распознающих алгоритмов в данной работе не рассматривается.

Обозначим через Rs = p(S, S) расстояние от объекта S Е Kt до ближайшего объекта S из противоположного к Kt класса (S Е CKt и S = S), через 5 — минимальное число групп из связанных объектов в Е0. Для поиска минимального покрытия объектами-эталонами обучающей выборки упорядочим объекты каждой группы Gu П Kt, u = 1,... ,5, t = 1,... ,1, по множеству значений {Rs}seG„. В качестве меры близости между S Е Gu, и = 1,...,5, и произвольным допустимым объектом S' используется взвешенное расстояние d(S,S') = p(S,S')/Rs. Решение о принадлежности S' к одному из классов К\,... ,Ki принимается по правилу: S' Е Kt, если

d

^ sueEo И

Согласно принципу последовательного исключения, используемому в процессе поиска покрытия, выборка Е0 делится на два подмножества: множество эталонов Ee(i и контрольное множество Е^, Е0 = Ее^ U Е^ .В начале процесса Ее^ = Е0, Е^ = 0. Упорядочение по значениям отступа {Rs}sec„, и = 1,... ,5, используется для определения кандидата на удаление из числа объектов-эталонов по группе Gu. Идея отбора заключается в поиске минимального числа эталонов, при котором алгоритм распознавания по (4) остается корректным (без ошибок распознающим объекты) на Е0.

Будем считать, что нумерация групп из связанных между собой объектов отражает порядок | G\ |> • • • >| G$ | и по группе Gp, р = 1,..., 5, не производился отбор эталонных объектов. Кандидаты на удаление из Ee(i последовательно выбираются начиная с S Е Gp с минимальным значением Rs. Если включение S Е Ek нарушает корректность решающего правила (4), то S возвращается во множество Ее<ц..

2. О нелинейном отображении наборов признаков на числовую ось

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

Правило для объединения признаков на каждом шаге иерархической группировки рассчитано на обучающую выборку с двумя непересекающимися классами, объекты которых описываются с помощью набора X(п) из п количественных признаков. Для удобства изложения обозначим классы как А\ и А2, множество исходных номеров количественных признаков — как I, признаки, полученные на р-м шаге иерархической агломеративной группировки, — как хЕ г,р > 0. При р = 0 I = {1,... ,п}. Если число классов I > 3, то к разбиению на два класса можно перейти, рассматривая объекты класса А\ как А\ = Kt, t = 1,... ,1, и А2 — как А2 = CKt.

Упорядоченное множество значений признака хр,] Е I ,р > 0, объектов из Е0 разделим на два интервала [с!Р,с2Р], (с2Р,СзР], каждый из которых рассматривается как градация номинального признака. Критерий для определения границы с^ основывается на проверке гипотезы (утверждения) о том, что каждый из двух интервалов содержит значения количественного признака объектов только из класса А1 или А2.

Пусть и1, и2 — количество значений признака хр,] Е I, класса Аг, г = 1, 2, соответственно в интервалах [с^, с^], (сХР , с3], | Аг |> 1, V — порядковый номер элемента упорядоченной по возрастанию последовательности ,... ,rjv,... , значений ^р у объектов из Е0, определяющий границы интервалов как с[р = , с^ = г^, с3 = . Критерий

( Е «К«.1 - 1)+ - 1Л

г=1

V

г=1

/

^=1г=1

V

/

тах

4р<4р<с.

„]Р -3

позволяет вычислять оптимальное значение границы между интервалами [с"[р, с2] и (с2Р,с3Р]. Выражение в левых скобках (5) представляет внутриклассовое сходство, в правых — межклассовое различие.

Экстремум критерия (5) используется в качестве веса и^ (0 < < 1) признака хРр. При тр = 1 значения признака хр у объектов из классов А1 и А2 не пересекаются между собой.

Значение комбинации из двух признаков Ьрг^ объекта вг = {ор,у}ие1, Е Е0, по паре (хР, хрЛ, 0 < р < п, г,] Е 1,г = ], вычисляется как

Ьр

'Пи

(

- сГ) + Ьыр(др. - с2Р) +

(4Р - О

(сзр - ¿?р) :

г,3 Е г, Ьц,и,Ьу Е {-1,1}, Е [0,1],

где тР,щР, — веса признаков, определяемые по (5) соответственно по множеству значений признаков жр, хр и их произведению х^х?; значения ^Е {-1,1}, Е [0,1] выбираются по экстремуму функционала

тт Ьр^ — тах Ь,

яг екх

еК2 ггз

тах Ьргр - тт Ьргр

тах

% е{-1,1},^ е[о,1]

Экстремум функционала (6) интерпретируется как отступ между объектами классов А1 и А2 по множеству значений по паре признаков (хр,хр), 0 < р < п, %,] Е I, г = ].

Обозначим через {^Р}г^е1, Р > 0, квадратную матрицу размера (п - р) х (п - р), значение элемента гР которой при р = 0 определяется как

р 7--

{

р

Щ;,

значению (5) по }™=1,

г = 3, г = Ь

через Гч,'ц > 0, — подмножество номеров признаков из X(п). Приведем пошаговую реализацию алгоритма иерархической агломеративной группировки.

Шаг 1. р = 0, Хс = 0, ц =1. Выполнять Гч = {г/}, Marginv = -2, ^ = ^ + 1, пока rq < п.

Шаг 2. Вычислить значения элементов матрицы {z^}ijej по (7). Шаг 3. Выделить Ф = {zUv | zUv > max(wIUand u = v,u,v E I}. Если Ф = 0, то идти 9.

Шаг 4. Вычислить Хп = max zUv. Выделить А = {(s,t),s,t E I | zpst = Xn and s < t}.

Определить пару {i,j}, i < j как

} ^ {s,t}, (s,t) E А and <p(p,s,t) > max <p(p,u,v).

Шаг 5. Если Хп > Хс или Хп = Хс и Магдгщ < <р{р,г,]), то ^ = Г и Г, Г = 0, Магдгпг = <р{р,г,]), идти 7.

Шаг 6. Вывод номеров признаков из Г, Г = 0, I = I \ {г}, идти 3. Шаг 7. р = р +1, I = I \ тах(г,]), к = тгп(г,]), Хс = Хп. Заменить значения признаков в описании объекта вг = {арг-1}ие1, г = 1,... ,ш, на

ар =

а^-1, u E I \ к, tf^i j, u = к.

Шаг 8. Для каждой пары (u,v), u,v E I определить значение

zU~1, U E I \{k}, V E I,

{

zU =

uv 1 значению (5) на }™=1, u = k, v E I.

Если п — р > 1, то идти 3.

Шаг 9. Конец.

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

3. Вычислительный эксперимент

Вычислительный эксперимент основывается на данных, приведенных в работе [6], о 147 пациентах, полученных из Центрального военного госпиталя Министерства обороны Республики Узбекистан. Для описания клинических и функциональных параметров каждого пациента (объекта) было использовано 29 количественных признаков. Диагностировались две группы (класса) пациентов: 111 практически здоровые (К\) и 36 больные артериальной гипертонией (К2).

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

объектов-эталонов покрытия. Подтверждением истинности этого утверждения служат данные из табл. 2, в которой приводится число объектов-эталонов (в скобках) по каждой идентифицированной группе. Общее число объектов-эталонов по взвешенному расстоянию в (4) на базе метрики Чебышева 9, оно больше числа 6 по аналогичному расстоянию на базе метрики Хэмминга.

Мера близости в (4) определяет локальные метрики с весом относительно каждого объекта выборки. Использование локальных метрик позволяет выделять области в признаковом пространстве, которые защищают (притягивают) объекты-эталоны (столпы по терминологии из [2]) покрытия. Число объектов-эталонов покрытия является одним из показателей компактности обучающей выборки, выражаемой через устойчивость логических закономерностей в форме гипершаров. Значение устойчивости гипершара с центром в объекте-эталоне в Е К1, £ = 1,...,/, вычисляется через мощность множества Из = {5"г Е | ¿(Бг, Б) < }, где — расстояние до ближайшего от Б объекта из СК1 по локальной метрике из (4).

Для доказательства того, что от снижения размерности признакового пространства повышается компактность выборки, было использовано нелинейное отображение значений из наборов (непересекающихся групп) признаков в описании объектов на числовую ось. Алгоритм иерархической агломеративной группировки формирует наборы в порядке, определяемом отношением по значениям (5) и (6). Селекцию признаков можно проводить путем удаления наборов (латентных признаков в новом пространстве) в порядке, обратном их формированию. Зависимость между числом объектов-эталонов покрытия и размерностью пространства при селекции признаков приводится в табл. 3. В скобках указано число исходных признаков, включенных в наборы.

Сравнительный анализ результатов покрытия обучающей выборки по табл. 2 и 3 показывает на значительное уменьшение числа объектов-эталонов при использовании нелинейного отображения определяемых наборов признаков на числовую ось. Число объектов-эталонов покрытия, обеспечивающих корректное распознавание на обучающей выборке, монотонно не возрастает при уменьшении размерности признакового пространства. Удаление шумовых объектов в процессе селекции выборки служит препят-

Таблица 1. Число групп объектов по классам

Метрика Классы

Здоровые Больные

Хемминга 1

Чебышева 1

Таблица 2. Число объектов-эталонов покрытия в группах

Взвешенное расстояние Классы

на базе метрики Здоровые Больные

Хемминга 1

Чебышева 1

Таблица 3. Число объектов-эталонов покрытия при селекции признаков

Взвешенное расстояние Размерность пространства

на базе метрики 6

Хемминга 5 4 4 2 2

Чебышева 3 3 3 3 2

Таблица 4. Разбиение на группы по метрике Журавлева

Класс Число

групп объектов-эталонов

Здоровые 1 4

Больные 5 9

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

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

Для демонстрации группировки объектов с описанием в разнотипном признаковом пространстве 14 количественных признаков (с 16 по 29) исходной выборки преобразуем в номинальные, используя разбиение их значений на непересекающиеся интервалы по критерию (5). В номинальной шкале градации каждого из 14 перечисленных признаков определяются номерами интервалов, к которым принадлежат их исходные значения. В нашем случае номера для градаций могут выбираться из {0,1} или {1, 2}. Для сглаживания влияния масштабов измерений на вычисление расстояния между объектами значения количественных признаков с 1 по 15 нормируются в [0..1]. Результаты использования метрики Журавлева на модифицированных данных для разбиения на группы по свойству связанности объектов через оболочки классов приводятся в табл. 4.

Анализ результатов вычислительного эксперимента из табл. 1, 2 и 4 показывает, что число групп разбиения и объектов-эталонов покрытия классов с описанием в разнотипном признаковом пространстве увеличилось по сравнению с аналогичными показателями при описании объектов количественными признаками.

Унификация шкал (путем сведения к единой шкале) измерений для разнотипных признаков позволяет использовать нелинейное отображение их в описании объектов на числовую ось. Достигается это за счет расширения размерности признакового пространства. Наличие или отсутствие значения градации номинального признака в описании объекта отображается в значение из {0,1} и рассматривается как отдельный признак.

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

Список литературы / References

[1] Субботин С.А. Комплекс характеристик и критериев сравнения обучающих выборок для решения задач диагностики и распознавания образов // Математичш машини i си-стеми, 2010. № 1. С. 25-39.

Subbotin, S.A. The complex characteristics and comparison criteria of training sets for diagnostics and pattern recognition//Matematichni mashini i sistemi. 2010. No. 1. P. 25-39.

[2] Загоруйко Н.Г., Кутненко О.А., Зырянов А.О., Леванов Д.А. Обучение распознаванию образов без переобучения // Машинное обучение и анализ данных. 2014. Т. 1, № 7. С. 891-901.

Zagoruiko, N.G., Kutnenko, O.A., Zyryanov, A.O., Levanov, D.A. Learning to recognition without overfitting // Machine Learning and Data Analysis. 2014. Vol. 1, No. 7. P. 891-901.

[3] Дюк В.А. Формирование знаний в системах искусственного интеллекта: геометрический подход // Вестн. Акад. техн. творчества. СПб. 1996. № 2. С. 46-67.

Dyuk, V.A. Creation of knowledge in artificial intelligence systems: geometric approach // Vestnik Akademicheskogo Tekhnicheskogo Tvorchestva. SPb. 1996. No. 2. P. 46-67.

[4] Берестнева О.Г., Муратова Е.А., Янковская А.Е. Анализ структуры многомерных данных методом локальной геометрии // Изв. Томского политехн. ун-та. 2003. Т. 306, № 3. С. 19-23.

Berestneva, O.G., Muratova, E.A., Yankovskaya, A.E. Analysis of the structure of multidimensional data by the local geometry // Bulletin of the Tomsk Polytechnic University. 2003. Vol. 306, No. 3. P. 19-23.

[5] Игнатьев Н.А. Обобщенные оценки и локальные метрики объектов в интеллектуальном анализе данных. Ташкент: Университет, 2014. 72 с.

Ignat'ev, N.A. The generalized estimations and local metrics of objects in data mining. Tashkent: Universitet, 2014. 72 p.

[6] Ignat'ev, N.A., Adilova, F.T., Matlatipov, G.R., Chernysh, P.P. Knowledge discovering from clinical data based on classification tasks solving. Medinfo. Amsterdam: Ios press, 2001. P. 1354-1358.

Поступила в 'редакцию 1 апреля 2015 г., с доработки — 26 октября 2015 г.

Cluster analysis and choice of standard objects in supervised pattern recognition problems

Ignat'ev, Nikolay A.

National University of Uzbekistan, Tashkent, 100174, Uzbekistan Corresponding author: Ignat'ev, Nikolay A., e-mail: n_ignatev@rambler.ru

Purpose: Search for solutions of the following problems:

— to find the minimum cover of a training set E0 = Si,..., Sm by standard objects. The set E0 is divided into 1(1 > 2) of disjoint subsets (classes) Ki,..., Ki. The objects are described by a set of features X(n) = (xi,..., xn);

— a reduction of the dimension of the features space by constructing groups from

the disjoint sets of features X(ki),..., X(kp), ki +-----+ kp < n and nonlinear mapping

of their values on the real axis in the description of objects.

Methodology: The method of partitioning the training set E0 into disjoint groups of objects using the property of their connectivity through the subset of boundary objects (shell) of classes L(E0,p) on a metric p(x,y) was developed. The set Gtv = Svi,..., SUc, c > 2, Gtv C Kt, v < lKtl presents an area (group) with the constrained objects in the class Kt, if for any SVi, Sv- £ Gtv the pathway SVi o SVk o    o

© ICT SB RAS, 2015

will exist. The standard objects of minimum covering of training set E0 are selected for each group Gtv separately.

The rule of hierarchical clustering of features offers for the nonlinear mapping of their values on the real axis. The use of this rule allows:

— to form a new space from latent features;

— to produce the ordered selection of informative features.

Findings: It is proved, that the number of standard objects for covering which ensures the correct recognition on precedents in the training set, does not increase monotonously when the number of features with low value of information are reduced.

Originality/value: Complex use of methods of cluster analysis for both group objects and features allows to reduce the volume of training sets and to increase the stability of the internally defined logical regularities.

Keywords: pattern recognition, logical regularity, cluster analysis of data, shell of classes, standard objects.

Received 1 April 2015 Received in revised form 26 October 2015