Задача SDX — предельный случай задач распознавания комбинированного типа
Описано задачі розпізнавання основних типів: автоматичної класифікації (S), вибору інформативних ознак (Х) і побудови вирішувальних правил (D). Подано методи розв’язання задач комбінованого типу, коли вимагається розв’язувати дві з цих трьох задач одночасно: задачі SD, SX і DX. Описано постановку і...
Gespeichert in:
| Veröffentlicht in: | Проблемы управления и информатики |
|---|---|
| Datum: | 2008 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/209123 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Задача SDX — предельный случай задач распознавания комбинированного типа / И.А. Борисова, Н.Г. Загоруйко // Проблемы управления и информатики. — 2008. — № 2. — С. 76-85. — Бібліогр.: 15 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860203667892731904 |
|---|---|
| author | Борисова, И.А. Загоруйко, Н.Г. |
| author_facet | Борисова, И.А. Загоруйко, Н.Г. |
| citation_txt | Задача SDX — предельный случай задач распознавания комбинированного типа / И.А. Борисова, Н.Г. Загоруйко // Проблемы управления и информатики. — 2008. — № 2. — С. 76-85. — Бібліогр.: 15 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Описано задачі розпізнавання основних типів: автоматичної класифікації (S), вибору інформативних ознак (Х) і побудови вирішувальних правил (D). Подано методи розв’язання задач комбінованого типу, коли вимагається розв’язувати дві з цих трьох задач одночасно: задачі SD, SX і DX. Описано постановку і метод розв’язання комбінованої задачі граничної складності — задачі SDX, коли потрібно обрати таку підмножину ознак Х, в просторі яких аналізовані об'єкти добре розділяються на кластери S за допомогою вирішувальних правил D. Істотну роль у розв’язанні таких задач грає використання запропонованої функції конкурентної схожості (FRiS-функції). Наводиться приклад розв’язання реальної задачі SDX.
Recognition problems of the basic types are described: an automatic classification (S), a choice of informative attributes (X) and constructions of decision rules (D). Methods of the combined problems solving when it is required to solve two of these three problems simultaneously are presented: problems SD, SX and DX. It is described a statement and a decision method for a combined problem of limiting complexity –— the SDX problems when it is necessary to choose such subset of attributes X in space of which analyzed objects are well divided into clusters S by means of the decision rules D. An essential role in such problems solving plays the use of the offered function of competitive similarity (FRiS-function). An example of a real SDX problem decision is given.
|
| first_indexed | 2025-12-07T18:11:55Z |
| format | Article |
| fulltext |
© И.А. БОРИСОВА, Н.Г. ЗАГОРУЙКО, 2008
76 ISSN 0572-2691
РАСПОЗНАВАНИЕ ОБРАЗОВ И КЛАСТЕРИЗАЦИЯ
УДК 519.95
И.А. Борисова, Н.Г. Загоруйко
ЗАДАЧА SDX — ПРЕДЕЛЬНЫЙ СЛУЧАЙ ЗАДАЧ
РАСПОЗНАВАНИЯ КОМБИНИРОВАННОГО ТИПА
Введение
В Институте математики Сибирского отделения РАН ученые более 40 лет
работают над проблемами, связанными с машинными методами обнаружения эм-
пирических закономерностей, и применением этих закономерностей для решения
задач распознавания и прогнозирования. Постановки многих задач, которыми за-
нимался и занимается коллектив распознавателей в Новосибирске, в свое время
были сформулированы А.Г. Ивахненко. К ним относятся и задачи, описываемые в
данной статье. Задача, которую сейчас принято называть кластерным анализом,
известна, например, еще со времен Демокрита, который в «Письме ученому дру-
гу» советовал разложить вещи на кучки по похожести характеристик, чтобы по-
нять их суть. Важно отметить, что среди первых работ с описанием идеи ма-
шинных алгоритмов «распознавания без учителя», «самопроизвольного разбие-
ния на классы» или «самоорганизации», наряду с работами Ф. Розенблатта,
были и работы А.Г. Ивахненко [1, 2]. Члены коллектива новосибирских распо-
знавателей считают себя его последователями.
1. Типовые задачи распознавания
К задачам распознавания основных типов отнесем следующие [3]:
— задачу автоматической классификации (S), которая состоит в разделении
объектов на классы (таксоны) по похожести описывающих характеристик;
— задачу выбора информативного подмножества характеристик (Х) из их
исходного множества;
— задачу построения решающего правила (D), по которому можно распо-
знавать принадлежность новых объектов к одному из известных классов.
Решение любой из этих задач заключается в поиске одного из трех элементов
в предположении, что два остальных заданы. Так, в задаче D строится решающее
правило для случая, когда классификация S и признаковое пространство Х фикси-
рованы. При выборе информативных признаков Х заданными являются классифи-
кация S и решающей функции D. Классификация S строится в заданном простран-
стве признаков Х и для фиксированного решающего правила D.
Задачи комбинированного типа возникают тогда, когда есть необходимость
одновременного выбора двух элементов из этих трех [3]. Хорошо известна задача
типа DX, в которой для заданной классификации S строятся решающие правила D
с одновременным выбором наиболее информативного подпространства X. Мето-
ды решения таких задач достаточно изучены. Например, логические решающие
правила и деревья служат примером решающих функций в избранном подпро-
странстве признаков. В задаче типа SX при заданном решающем правиле D ищет-
ся такое подпространство признаков X, в котором анализируемая выборка разде-
Проблемы управления и информатики, 2008, № 2 77
ляется на удаленные друг от друга группы S объектов, похожих между собой. За-
дача SD решается в заданном пространстве признаков X. При этом строится такая
классификация S и подбирается такое решающее правило D, которые должны ми-
нимизировать ошибки распознавания контрольных объектов.
Есть и более сложные ситуации, в которых для исследования предъявляется
множество из М объектов, описанных N характеристиками, и формулируется по-
желание такого рода: «Хорошо бы понять структуру этого множества, обнару-
жить (если они есть) компактные группы похожих друг на друга объектов (S),
отобрать наиболее существенные характеристики (Х) и выработать такое прави-
ло (D), чтобы оно позволяло в будущем угадывать, к какой из выделенных групп
лучше всего отнести тот или иной новый объект». Именно такие расплывчатые
задания стимулировали появление методов, развиваемых в рамках направления
Data Mining.
Первоначально надежды возлагались на последовательную схему решения
таких задач SDX. Для множества М объектов в исходном пространстве ∗X фор-
мировалась классификация S с ориентацией на класс решающих правил .∗D За-
тем из класса ∗D выбиралось конкретное правило распознавания D принадлеж-
ности М объектов к своим классам. Наконец, при фиксированных
классификации S и решающем правиле D решалась задача выбора из множества
∗X подмножества информативных признаков Х, которые обеспечивают
наибольшую надежность распознавания этих М объектов. Но такой подход обес-
печивает лишь локально оптимальные решения. Так, классификация, сделанная в
пространстве ,∗X может отличаться от классификации, которую можно получить
в подпространстве Х. Кроме того, необходимо обеспечить взаимную согласован-
ность методов решения основных задач. Если, например, классификация будет
делаться алгоритмом k-means, то классы будут разделяться произвольно ориенти-
рованными гиперплоскостями. Если после этого решающее правило выбирается
из класса логических решающих правил, то это правило представляет собой при-
ближение произвольных гиперплоскостей набором плоскостей, перпендикуляр-
ных осям координат.
Если затем информативность признаков оценивать по критерию Фишера, ко-
торый оперирует расстояниями между матожиданиями распределений и диспер-
сиями этих распределений, то ожидать получения решения, которое можно легко
интерпретировать и которое пригодно для дальнейшего использования, нельзя.
Нужно, чтобы классификация S строилась по тому же критерию, по которому
находится наилучшее решающее правило D и выбирается наиболее информатив-
ное подмножество признаков X.
В итоге возникла задача создания единого подхода к решению задач распо-
знавания разного типа. При этом нужно обеспечивать приемлемую трудоемкость
и высокую эффективность решения этих задач. В качестве такого единого подхо-
да в данной работе предлагается подход, основанный на использовании функции
конкурентного сходства, или FRiS-функции (Function of Rival Similarity).
2. Функция конкурентного сходства
Обратим внимание на то, что в нашем распоряжении имеется образец систе-
мы, которая замечательно решает все задачи распознавания образов (РО): и про-
стые, и сложные. Эта система — человек, ориентируясь в окружающей среде,
непрерывно классифицирует, распознает, выбирает важные признаки, прогнози-
рует и т.д. Скорее всего, при решении этих разных задач человек пользуется од-
ной и той же универсальной психофизиологической функцией.
Данная работа основана на двух гипотезах.
78 ISSN 0572-2691
1. Основная функция, используемая человеком при решении задач классифи-
кации, распознавания, выбора признаков, прогнозирования и т.д., состоит в опре-
делении меры сходства между объектами или явлениями.
2. Сходство является величиной не абсолютной, а относительной.
Мы хотим показать, что мера, воспроизводящая человеческий механизм
оценки меры относительного (конкурентного) сходства, позволяет строить для
решения задач РО разного типа единообразные и эффективные алгоритмы, инва-
риантные к степени обусловленности и видам распределения объектов в про-
странстве характеристик.
В литературе описаны десятки различных мер сходства, используемых в ал-
горитмах распознавания [4]. Как правило, в этих мерах сходство носит абсолют-
ный характер и зависит только от расстояний от распознаваемого объекта до этих
эталонов. Но легко убедиться, что человеческое восприятие похожести носит от-
носительный характер. Чтобы ответить на вопросы типа «Близко или далеко
пункт а находится от пункта b?», «Похож ли объект k на объект d?», нужно знать
ответ на вопрос «По сравнению с чем?».
Идеи, отражающие эту особенность человеческого восприятия сходства,
нашли отражение в некоторых методах распознавания. Так, в правиле ближайше-
го соседа )(kNN решение о принадлежности объекта Z к образу Si принимается
не в том случае, когда расстояние ir от Z до Si «мало», а когда оно меньше рас-
стояния jr от Z до конкурирующего образа Sj. Следовательно, чтобы оценить по-
хожесть объекта Z на образ Si, нужно сравнивать расстояния ir и jr в шкале по-
рядка. Проведенные нами сравнительные исследования показали, что эффектив-
ность решающих правил существенно повышается, если функцию сходства
измерять не в шкале порядка, а в шкале отношений. Для этого можно использо-
вать следующую величину:
)./()()/( jiij rrrrjiF +−= (1)
В дальнейшем будем называть ее FRiS-функцией [5]. Эта функция имеет относи-
тельный характер и хорошо согласуется с человеческими механизмами восприя-
тия сходства и различия. Значения функции F меняются в пределах от +1, когда
объект Z совпадает с эталоном образа Si, до –1, когда он совпадает с эталоном
конкурирующего образа Sj. Граница между образами проходит по точкам, в кото-
рых .0)/()/( == ijFjiF Здесь объект в равной степени похож и не похож на эти
конкурирующие образы.
Опыт работы с FRiS-функцией показал, что она может использоваться в ка-
честве базового элемента для решения различных задач РО. Начнем с задачи по-
строения решающих функций.
3. Построение решающих функций (алгоритм FRiS-Stolp)
Для распознавания образов необходимо выбрать объекты-эталоны, c которы-
ми будут сравниваться контрольные объекты. Выбор эталонов (столпов) для каж-
дого образа можно осуществить с помощью алгоритма FRiS-Stolp [6].
Пусть имеется K образов и решается задача распознавания двух образов в по-
становке «Образ Si против всех остальных». Проверяется вариант, при котором
первый случайно выбранный объект ail является единственным столпом образа Si,
а все другие образы в качестве столпов имеют все свои объекты.
1. Для всех объектов ,, lkaik ≠ образа Si находим расстояние klr до столпа
ila и расстояние ktr до ближайшего объекта tb чужого образа. По этим расстоя-
Проблемы управления и информатики, 2008, № 2 79
ниям вычисляем значения функции сходства )/( tiFk объектов ika со своим стол-
пом ila в конкуренции с объектами всех остальных образов. Находим те ml объ-
ектов образа Si, значение функции сходства )/( tiFk которых выше заданного по-
рога F*, например .0* =F Далее находим ∑
=
=
lm
k
kil tiFaF
1
)/()( — сумму значений
функций сходства всех ml объектов со столпом .ila Если ml=0, положим
.0)( =ilaF
2. Аналогичную процедуру повторяем, назначая на роль столпа все iM объ-
ектов образа Si по очереди.
3. Первым столпом первого кластера 1iC образа Si объявляем объект ,*
ina где
).(maxarg
,...,1
il
Ml
aFn
i=
=
4. Исключаем из образа iS столп *
ina и *
nm объектов, входящих в его кла-
стер. Для остальных объектов i-го образа находим следующий столп повторени-
ем пп. 1–3. Процесс останавливается, если все объекты образа iS оказались
включенными в свои кластеры.
5. Затем решаем задачу «Образ Sj против всех остальных» путем повторения
пп. 1–4.
6. Для всех остальных образов повторяем пп. 1–5.
7. Столпы каждого образа выбраны в условиях, когда им противостояли все
объекты конкурирующих образов. Теперь образы представлены только своими
столпами. Для уточнения состава кластеров в новых конкурентных условиях рас-
познаем принадлежность всех объектов к имеющимся кластерам. Составы кла-
стеров могут измениться.
8. В заключение нужно найти среднее значение функций сходства Fs всех
объектов со своими столпами. Величина Fs характеризует качество обучения си-
стемы и, как показали наши исследования, тесно связана с величиной ошибок, по-
лучаемых при распознавании контрольных объектов.
Отметим некоторые особенности алгоритма FRiS-Stolp. Если распределения
полимодальны и образы линейно неразделимы, столпы будут стоять в центрах
локальных мод. При нормальных распределениях в первую очередь будут выбра-
ны столпы, расположенные в точках математического ожидания. Следовательно,
при приближении к хорошо изученным нормальным распределениям решение за-
дачи построения решающих функций стремится к оптимальному.
Процесс распознавания с опорой на
столпы очень прост и состоит в оценке
функций конкурентного сходства кон-
трольного объекта Z со всеми столпами и
выбора образа Si, на чей столп объект Z
наиболее похож. На рис. 1 приведен пример
распознавания принадлежности объекта Z к
одному из двух образов, один из которых
представлен одним столпом, а другой —
тремя столпами.
Имеются и другие важные преимуще-
ства такого решающего правила [6].
Рис. 1
80 ISSN 0572-2691
4. Выбор информативных признаков (алгоритм FRiS-GRAD)
Для решения задачи выбора подмножества наиболее информативных призна-
ков Х из их большого исходного множества ∗X можно использовать любой алго-
ритм направленного перебора, например GRAD [7]. Он позволяет автоматически
указать как состав, так и наилучшее количество характеристик. Здесь мы не опи-
сываем этот алгоритм, а обращаем внимание на использование в нем нового кри-
терия информативности, основанного на использовании FRiS-функции [6].
Для оценки информативности признаков или их сочетаний обычно использу-
ется критерий в виде количества ошибок U распознавания обучающей выборки в
режиме скользящего экзамена. Главным недостатком этого критерия является то,
что он не учитывает надежность распознавания объектов, которые распознаны
правильно, и грубость ошибки для тех объектов, которые распознаны неправиль-
но. Мы показали, что учесть эти особенности можно, если использовать в каче-
стве критерия информативности Q среднее значение функции конкурентного
сходства Fs объектов с эталонами своих образов.
Преимущества критерия информативности Q перед критерием ошибок на
обучающей выборке U можно проиллюстрировать результатами их эксперимен-
тального сравнения. Исходные данные состояли из 200 объектов двух образов
(по 100 объектов каждого образа) в 100-мерном пространстве. Признаки генери-
ровались так, чтобы они обладали разной информативностью. Дополнительно
таблица искажалась шумами разной интенсивности, и при каждом уровне шума
(от 0,05 до 0,3) выбирались наиболее информативные подсистемы признаков
размерности n (от 1 до 22). При этом для обучения произвольно выбиралось по
35 объектов каждого образа. На контроль предъявлялись остальные 130 объектов.
Результаты сравнения критериев Q и U при разных уровнях шума показаны на
рис. 2 (результаты скользящего экзамена на обучающей выборке — тонкие линии,
результаты распознавания контрольной выборки — толстые линии, сравнение
критериев информативности Fs (сплошные линии) и U (пунктирные линии)). Ре-
зультаты контроля показывают, что критерий U формирует излишне оптимисти-
ческие ожидания.
По сравнению с критерием U критерий Q обладает значительно более вы-
сокими прогностическими свойствами и помехоустойчивостью и позволяет
решить проблему «пригодности» признаков, выдвинутую А.Н. Колмогоровым
в 1933 г. [8, 9].
0,6
0,65
0,7
0,75
0,8
0,85
0,9
0,95
1
0,05 0,1 0,15 0,2 0,25 0,3
шум
P
Fs
U
U
Fs
Рис. 2
5. Построение классификаций (алгоритм FRiS-Tax)
Автоматическая классификация объектов осуществляется с помощью алго-
ритма «FRiS-Tax» [10] в два этапа. На первом этапе алгоритм FRiS-Cluster выби-
Проблемы управления и информатики, 2008, № 2 81
рает объекты, находящиеся в центрах локальных плотностей объектов. Такие объ-
екты становятся эталонами (столпами) кластеров. На втором этапе с помощью ал-
горитма FRiS-Class происходит процедура укрупнения кластеров в классы (таксо-
ны) объединением некоторых соседних кластеров в один класс. Это позволяет со-
здавать классы произвольной формы, не обязательно линейно разделимые.
Кластеризация (алгоритм FRiS-Cluster). Условия использования функции
сходства в задаче построения классификации отличаются тем, что принадлеж-
ность объектов выборки к тому или иному классу неизвестна. Будем считать, что
все объекты принадлежат одному образу S. В связи с этим на первом этапе вво-
дится виртуальный образ-конкурент, ближайший столп которого удален от каж-
дого объекта выборки на фиксированное расстояние, равное .*
2r В результате бу-
дем использовать модификацию функции сходства, которая для любого объекта
из S равна
)./()( 1
*
21
*
2 rrrrFi +−=
Пользователь задает предельное число кластеров K, из которых он хотел бы
выбирать наилучший вариант кластеризации. Алгоритм ищет решения задач кла-
стеризации последовательно для всех значений ,,,2,1 Kk = выполняя следую-
щие операции.
1. Вначале все M объектов поочередно рассматриваются как эталон един-
ственного кластера. Для каждого из них в конкуренции с виртуальным столпом
вычисляется сумма функций сходства с ним всех остальных объектов. Столпом
первого кластера 1C назначается объект :*
1a
).(maxarg*
1 l
Sa
aFa
l∈
=
2. Затем для случая 2=k определяется, какой объект будет наилучшим вто-
рым столпом. Для этого на роль второго столпа по очереди назначаются все (M–1)
объектов, не совпадающих с первым столпом. Наличие двух реальных столпов и
одного виртуального позволяет отнести каждый объект к первому или второму
реальному кластеру. Вторым столпом *
2a выбирается такой объект, который в со-
четании с первым столпом *
1a обеспечивает максимальную сумму функций по-
хожести всех объектов на свои столпы. Объекты, присоединенные к каждому из
двух столпов *
1a и ,*
2a образуют кластеры 1C и .2C
3. Дальнейшее расширение списка столпов делается аналогично. В итоге будут
получены наилучшие варианты классификации для всех значений .,,2,1 Kk = На
этом первый этап кластеризации заканчивается.
Построение классификации (алгоритм FRiS-Class). Если кластер имеет
сложную форму, т.е. если он линейно не отделим хотя бы от одного-другого клас-
са, то этот класс будет состоять из нескольких кластеров. С учетом этого в алго-
ритме предусмотрен следующий механизм объединения нескольких кластеров в
один класс.
4. Расстоянием ijR между кластерами iC и jC считается минимальное рас-
стояние между двумя ближайшими объектами разных кластеров. Для этих объек-
тов a из iC и b из jC определяются расстояния )(aR и )(bR от каждого из них
до ближайшего своего соседа.
5. Кластеры iC и jC объединяются, если значения величин ,ijR )(aR и
)(bR мало отличаются один от другого.
82 ISSN 0572-2691
Важным преимуществом данного алгоритма является возможность автомати-
ческого выбора локально оптимального числа кластеров. Для этого можно исполь-
зовать значения качества кластеризации Fs при разных количествах кластеров.
Лучшим вариантам кластеризации соответствуют локальные максимумы величи-
ны Fs. На рис. 3 приводятся примеры результатов работы алгоритма FRiS-Tax в
двумерном случае.
Рис. 3
Преимущества предложенного алгоритма перед алгоритмами k-means [11, 12]
и FOREL [13] показаны на ряде модельных и прикладных задач [10].
6. Решение задачи комбинированного типа SDX
Перейдем к рассмотрению наиболее общей задачи распознавания комбини-
рованного типа SDX. Для ее решения используем все наработки, полученные нами
при решении более простых комбинированных задач: SD, DX и SX. Переход от
исходного множества М объектов к набору кластеров с эталонными образцами
(столпами) с помощью алгоритма FRiS-Tax обеспечит нас сразу и классификаци-
ей S и решающим правилом D для нее. Выбор же информативной подсистемы при-
знаков X будет ориентироваться на принципы естественной классификации [14].
Из принципов этой классификации вытекает следующее. Будем считать, что
подсистема *XX ⊆ из L )( NL < информативных признаков хорошо отражает
основное содержание исходной таблицы, если она не только обеспечивает хоро-
шее распознавание принадлежности объектов к своим образам, но еще и позволя-
ет предсказывать значения остальных )( LN − признаков, не вошедших в состав
информативных. В связи с этим, помимо решающих правил D, сокращенное опи-
сание выборки должно содержать систему индуктивных правил ,D ′′ устанавли-
вающих связь между этими двумя подмножествами признаков: X и ./* XXY =
В качестве индуктивных правил можно использовать регрессионные зависимости
между ними, а также и такие простые правила: значения неинформативных при-
знаков Y любого объекта образа Si приравниваются средним значениям этих при-
знаков у всех объектов данного образа или их значениям у эталона этого образа.
Для более строгой математической формулировки задачи SDX введем следу-
ющие обозначения. Множество анализируемых объектов будем обозначать
},,,,{ 21 MaaaA = множество исходных признаков — }.,,,{ 21 NxxxX =∗
Для фиксированного набора столпов ,AС ⊆ },,,,{ 21 KcccC = и некоторого
множества информативных признаков ,*XX ⊆ ,LX = | NL < определим каче-
ство Q, с которым выбранный набор данных 〉〈 XC, описывает исходный набор
,, 〉〈 ∗XA как
),,(),( ∗
∈
∗∑= caFXCQ X
Aa
где ).,(minarg* caFc X
Cc∈
= (2)
Проблемы управления и информатики, 2008, № 2 83
Здесь ∗XF и XF — величины функции сходства объектов a со «своими» столпа-
ми ∗c в пространстве ∗X и Х соответственно. Если информативные признаки X
коррелированны с оcтальными (Y), то вместе с уменьшением ошибок распознава-
ния по правилам D будут уменьшаться и ошибки предсказания по индуктивным
правилам .D ′′ Нужно найти такую пару ,, 〉〈 XC которая обеспечит максимальное
значение функционалу качества Q.
Заметим, что своего глобального максимума (наивысшей точности представления
исходных данных) функционал Q(C, X) достигает при AС = и ,*XX = т.е. в
случае отказа от сжатия информации в угоду сохранения точности ее представле-
ния. В связи с этим возникает необходимость в ограничениях на мощность отыс-
киваемого множества столпов С и набора признаков X. В итоге рассматриваемую
задачу можно записать в следующем оптимизационном виде:
,max),(
,
,
∗∗
∗
<⊆
<⊆
→
nXXX
mCAC
XCQ (3)
где ,1 nn <> ∗ mm <> ∗1 — величины, ограничивающие размер информативно-
го подпространства и количество столпов соответственно.
Теперь можно описать общую схему решения задачи SDX. Одной из извест-
ных процедур направленного перебора (например, алгоритмом AdDel, GRAD или
СПА [13]) организуется поочередное рассмотрение разных вариантов признако-
вых подпространств Х. В каждом подпространстве алгоритмом FRiS-Tax форми-
руется наилучшая классификация S с одновременным получением решающего
правила D. Качество получаемого при этом сочетания S, D и X оценивается по
критерию Q. В итоге сравнения выбирается наилучшее решение.
Таким образом, сложная комбинаторная задача SDX сводится к серии более
простых, решение которых позволяет представлять исходную выборку объектов в
виде их групп (S), формирует решающее правило (D) для отнесения новых объек-
тов к этим группам в информативном подпространстве признаков (Х).
Развитие этой идеи позволило решить и такую задачу SDX, в которой, по ана-
логии с задачей естественной классификации, делается не одноуровневая класси-
фикация, а многоуровневая иерархическая, представленная в виде дерева T [15].
Каждому разбиению некоторой внутренней вершины этого дерева соответствует
промежуточная классификация в своем собственном информативном подпро-
странстве. Каждая висячая вершина этого дерева — отдельный класс в создавае-
мой классификации. И ей ставится в соответствие свой эталонный образец (столп)
в объединенном пространстве признаков X, используемых на всех этапах класси-
фикации по дереву T. При распознавании нового объекта а по дереву T отыскива-
ется вершина (класс), в которую он попадает, и вычисляется функция конкурент-
ного сходства этого объекта со столпом этого класса (T(a)) в полном пространстве
признаков .∗X Оптимизируемым при построении дерева критерием качества в
этом случае является
)).(,()( aTaFTQ
Aa
XF ∑
∈
∗=
Приближенные решения для этой задачи отыскиваются за счет перехода к
серии задач, каждой из которых соответствует разбиение одной висящей вершины
в дереве, обеспечивающее максимальное увеличение итогового функционала ка-
чества QF.
84 ISSN 0572-2691
7. Экспериментальная проверка
Алгоритм FRiS-SDX построения иерархического решения задачи SDX при-
менялся для анализа следующей выборки. У образцов различных горных пород
были замерены их спектральные портреты. Каждый спектр представлял собой
1024-мерный вектор. При этом спектры 160 образцов обучающей выборки были
разделены экспертами по химическому составу на семь групп. Эффективность ал-
горитма оценивалась через величину однородности полученных таксонов с точки
зрения химического состава объектов, попавших в них. Подчеркнем, что знания о
химическом составе не учитывались в процессе решения задачи SDX, а использо-
вались только для оценки получаемых результатов.
Алгоритм дробил каждую вершину этого дерева на два класса, описываемых
двумя столпами. Информативное подпространство, в котором производилось раз-
биение, не должно было содержать больше шести признаков (т.е. спектральных
полос) из 1024. Дерево, полученное в результате работы алгоритма с заданными
ограничениями, изображено на рис. 4. Оно последовательно отделило четыре
класса химических веществ друг от друга, слив три других в один класс. Более
подробный анализ показал, что вещества, попавшие в один класс, идентичны по
химическому составу практически, и количество различающих их примесей
марганца и кобальта очень мало и фактически не проявляется в спектральных
портретах.
Fe+Ni+ (Mn, Co)
Fe+Se
Fe+Pb
Fe+Tl Fe+Mo
Рис. 4
Заключение
Описан универсальный подход к решению задач распознавания основного и
комбинированного типов, основанный на использовании функции конкурентного
сходства — FRiS-функции. На этой основе можно строить эффективные алгорит-
мы, инвариантные к соотношению числа объектов к числу признаков и к виду
распределения обучающей выборки. Показана возможность решения главной за-
дачи, породившей новое научное направление — интеллектуальный анализ дан-
ных или Data Mining — задачи комбинированного типа SDX одновременного вы-
бора классификации S, решающего правила D и информативного подмножества X
наблюдаемых объектов. Эти исследования ориентированы на развитие методов
решения все более сложных задач распознавания и прогнозирования.
І.А. Борисова, М.Г. Загоруйко
ЗАДАЧА SDX — ГРАНИЧНИЙ ВИПАДОК ЗАДАЧ
РОЗПІЗНАВАННЯ КОМБІНОВАНОГО ТИПУ
Описано задачі розпізнавання основних типів: автоматичної класифікації (S),
вибору інформативних ознак (Х) і побудови вирішувальних правил (D). Подано
методи розв’язання задач комбінованого типу, коли вимагається розв’язувати
дві з цих трьох задач одночасно: задачі SD, SX і DX. Описано постановку і ме-
тод розв’язання комбінованої задачі граничної складності — задачі SDX, коли
Проблемы управления и информатики, 2008, № 2 85
потрібно обрати таку підмножину ознак Х, в просторі яких аналізовані об'єкти
добре розділяються на кластери S за допомогою вирішувальних правил D. Іс-
тотну роль у розв’язанні таких задач грає використання запропонованої функції
конкурентної схожості (FRiS-функції). Наводиться приклад розв’язання реаль-
ної задачі SDX.
I.А. Borisova, N.G. Zagoruiko
PROBLEM SDX — AN ULTIMATE
CASE OF RECOGNITION PROBLEMS
OF THE COMBINED TYPE
Recognition problems of the basic types are described: an automatic classification
(S), a choice of informative attributes (X) and constructions of decision rules (D).
Methods of the combined problems solving when it is required to solve two of these
three problems simultaneously are presented: problems SD, SX and DX. It is
described a statement and a decision method for a combined problem of limiting
complexity –— the SDX problems when it is necessary to choose such subset of at-
tributes X in space of which analyzed objects are well divided into clusters S by
means of the decision rules D. An essential role in such problems solving plays the
use of the offered function of competitive similarity (FRiS-function). An example of
a real SDX problem decision is given.
1. Ивахненко А.Г. Кибернетические системы с комбинированным управлением. — Киев :
Техніка, 1966. — 321 с.
2. Ивахненко А.Г. Самообучающиеся системы распознавания и автоматического управления. —
Киев : Техніка, 1969. — 392 с.
3. Загоруйко Н.Г. Методы распознавания и их применение. — М. : Сов. радио, 1972. —
С. 135–147.
4. Воронин Ю.А. Начала теории сходства. — Новосибирск : Изд.-во ВЦ СОАН, 1989. — 120 с.
5. Zagoruiko N.G., Borisova I.A., Kutnenko O.A. Criteria of informativeness and suitability of a sub-
set of attributes, based on the similarity function // Proc. of 9th Intern. Conf. PRIP’2007, Minsk,
2007. — P. 257–261.
6. Борисова И.А., Дюбанов В.В., Загоруйко Н.Г., Кутненко О.А. Использование FRiS-функции
для построения решающего правила и выбора признаков (задача комбинированного типа
DX) // Материалы Всерос. конф. ЗОНТ-2007. — Новосибирск, 2007. — 1. — С. 37–44.
7. Загоруйко Н.Г., Кутненко О.А., Борисова И.А. Выбор информативного подпространства
признаков (Алгоритм GRAD) // Докл. 12-й Всерос. конф. Мат. методы распознавания обра-
зов (ММРО-12). — М., 2005. — С. 106–109.
8. Колмогоров А.Н. К вопросу о пригодности найденных статистическим путем формул про-
гноза // Заводская лаборатория. — 1933. — № 1. — С. 164–167.
9. Борисова И., Загоруйко Н., Кутненко О. Критерий информативности и пригодности под-
множества признаков // Proc. of 13th Intern. Conf. KDS’2007. — Varna, 2007. — P. 567–571.
10. Борисова И.А. Алгоритм таксономии FRiS-Tax // Науч. вестн. НГТУ. — 2007. — № 3(28). —
С. 3–12.
11. Шлезингер М.И. О самопроизвольном разделении образов // Читающие автоматы и распоз-
навание образов. — Киев : Наук. думка, 1965. — С. 46–61.
12. MacQueen J. Some methods for classification and analysis of multivariate observations // Proc. of
the 5th Berkley Sympos. on Mathematical Statistics and Probability. — University of California
Press, 1967. — 1. — P. 281–297.
13. Загоруйко Н.Г. Прикладные методы анализа данных. — Новосибирск : Изд-во ИМ СО
РАН, 1999. — 270 с.
14. Zagoruiko N., Borisova I. Principles of natural classification // Pattern Recognition and Image
Analysis. — 2005. — 15, N 1. — P. 27–29.
15. Борисова И.А., Загоруйко Н.Г. Естественная классификация // Сб. тр. ИАИ–2004. — Киев,
2004. — С. 33–42.
Получено 21.12.2007
Введение
1. Типовые задачи распознавания
2. Функция конкурентного сходства
3. Построение решающих функций (алгоритм FRiS-Stolp)
4. Выбор информативных признаков (алгоритм FRiS-GRAD)
5. Построение классификаций (алгоритм FRiS-Tax)
6. Решение задачи комбинированного типа SDX
7. Экспериментальная проверка
Заключение
|
| id | nasplib_isofts_kiev_ua-123456789-209123 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-07T18:11:55Z |
| publishDate | 2008 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Борисова, И.А. Загоруйко, Н.Г. 2025-11-14T10:40:35Z 2008 Задача SDX — предельный случай задач распознавания комбинированного типа / И.А. Борисова, Н.Г. Загоруйко // Проблемы управления и информатики. — 2008. — № 2. — С. 76-85. — Бібліогр.: 15 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/209123 519.95 10.1615/JAutomatInfScien.v40.i4.20 Описано задачі розпізнавання основних типів: автоматичної класифікації (S), вибору інформативних ознак (Х) і побудови вирішувальних правил (D). Подано методи розв’язання задач комбінованого типу, коли вимагається розв’язувати дві з цих трьох задач одночасно: задачі SD, SX і DX. Описано постановку і метод розв’язання комбінованої задачі граничної складності — задачі SDX, коли потрібно обрати таку підмножину ознак Х, в просторі яких аналізовані об'єкти добре розділяються на кластери S за допомогою вирішувальних правил D. Істотну роль у розв’язанні таких задач грає використання запропонованої функції конкурентної схожості (FRiS-функції). Наводиться приклад розв’язання реальної задачі SDX. Recognition problems of the basic types are described: an automatic classification (S), a choice of informative attributes (X) and constructions of decision rules (D). Methods of the combined problems solving when it is required to solve two of these three problems simultaneously are presented: problems SD, SX and DX. It is described a statement and a decision method for a combined problem of limiting complexity –— the SDX problems when it is necessary to choose such subset of attributes X in space of which analyzed objects are well divided into clusters S by means of the decision rules D. An essential role in such problems solving plays the use of the offered function of competitive similarity (FRiS-function). An example of a real SDX problem decision is given. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Распознавание образов и кластеризация Задача SDX — предельный случай задач распознавания комбинированного типа Задача SDX— граничний випадок задач розпізнавання комбінованого типу Problem SDX — an ultimate case of recognition problems of the combined type Article published earlier |
| spellingShingle | Задача SDX — предельный случай задач распознавания комбинированного типа Борисова, И.А. Загоруйко, Н.Г. Распознавание образов и кластеризация |
| title | Задача SDX — предельный случай задач распознавания комбинированного типа |
| title_alt | Задача SDX— граничний випадок задач розпізнавання комбінованого типу Problem SDX — an ultimate case of recognition problems of the combined type |
| title_full | Задача SDX — предельный случай задач распознавания комбинированного типа |
| title_fullStr | Задача SDX — предельный случай задач распознавания комбинированного типа |
| title_full_unstemmed | Задача SDX — предельный случай задач распознавания комбинированного типа |
| title_short | Задача SDX — предельный случай задач распознавания комбинированного типа |
| title_sort | задача sdx — предельный случай задач распознавания комбинированного типа |
| topic | Распознавание образов и кластеризация |
| topic_facet | Распознавание образов и кластеризация |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/209123 |
| work_keys_str_mv | AT borisovaia zadačasdxpredelʹnyislučaizadačraspoznavaniâkombinirovannogotipa AT zagoruikong zadačasdxpredelʹnyislučaizadačraspoznavaniâkombinirovannogotipa AT borisovaia zadačasdxgraničniivipadokzadačrozpíznavannâkombínovanogotipu AT zagoruikong zadačasdxgraničniivipadokzadačrozpíznavannâkombínovanogotipu AT borisovaia problemsdxanultimatecaseofrecognitionproblemsofthecombinedtype AT zagoruikong problemsdxanultimatecaseofrecognitionproblemsofthecombinedtype |