автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Механизмы выбора квазитурного типа и их применение в задачах индуктивного обучения по примерам

Г? О & 1 -3

государственный комитет по делам науки и высшей школы ростовский ордена трудового красного знамени государственной университет

Региональный специализированный созет К 063.52.12 по техническим наукам

На правах рукописи

Чуез Николай Викторович

УДК 519.83

МЕХАНИЗМЫ ВЫБОРА КВАЗИТУРН0Г0 ТИПА И ИХ ПРИМЕНЕНИЕ В ЗАДАЧАХ ИНДУКТИВНОГО ОБУЧЕНИЯ ПО ПРИМЕРАМ

05.13.16-применение вычислительной техники, математического моделирования и математических методов о научных исследованиях (по отраслям науки)

Азфторе^зрат диссертации на соискание ученой степ-гни кандидата физико-математических наук

РОСТОВ-НА-ДОНУ 1991

ГОСУДАРСТВЕННЫЙ КОМИТЕТ ПО ДЕЛАМ НАУКИ И ВЫСШЕЙ ШКОЛЫ РОСТОВСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Региональный специализированный совет К 063.52.12 по техническим наукам

На правах рукописи

ЧУЕВ Николай Викторович

УДК 519.83

МЕХАНИЗМЫ ВЫБОРА КВАЗИТУРНИРНОГО ТИПА И ИХ ПРИМЕНЕНИЕ В ЗАДАЧАХ ИНДУКТИВНОГО ОБУЧЕНИЯ ПО ПРИМЕРАМ

05.13.16 - применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Ростов-на-Дону 1991

- г -

Работа выполнена во Всесоюзном научно-исследовательском" институте по разработке программных средств вычислительной техники и в Ордена Трудового Красного Знамени Ростовском государственном университете.

Научный руководитель - кандидат физико-математических наук

Абрамович С.М.

Официальные оппоненты: доктор физико-математических наук

Яновская Е.Б., кандидат технических наук Алескеров Ф.Т.

Ведущая организация - Вычислительный центр АН СССР

Защита состоится •• 1Ъ" фе&рсл.их. 1991 г. в _ час. на

заседании специализированного совета К 063.52.12 по присуждению ученой степени кандидата наук в Ростовском государственном университете по адресу: 344104, Ростов-на-Дону, пр. Стачки, 200/1, корпус 2, Вычислительный центр РГУ.

С диссертацией можно ознакомиться в научной библиотеке РГУ по адресу: ул. Пушкинская, 148.

Автореферат разослан "9.3" ^¿{С&ь'рл

1991 г.

Ученый секретарь специализированного совета,

кандидат технических наук Х.Д. Дженибалаев

ОБЩАЯ ХАРАКТЕРНО! ¡чКА РАБОТ«'

Актуальность темы. Во многих задачах упразднил ссцшльг-ь-":! у экономическими системами возникает сеобхпп^лость ¿-¿бора .пу^зих вариантов в ситуации, когда исходной информацией о "кглестгэ" вариантов являются результаты парных сравнений. Такие скгуагг/л возникают в задачах планирования, проектирования, анализа слепших экономических и социальных систем и т.д.

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

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

Для достижения этой цели необходимо решить следующие

выделить классы функции выбора, порождаемые рассматриваемыми механизмами выбора и установить соотношения между этими классами;

- исследовать различные операции над функциями выбора из рассматриваемых классов;

провести анализ выполнения условий классической рациональности выбора для функций из рассматриваемых классов;

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

Методы исследования. При решении сформулированных выше задач были использованы методы теории исследования операций и теории множеств.

Научная новизна. В работе получены следующие результаты, имеющие научную новизну;

- предложено обобщение ряда известных процедур выбора по результатам парных сравнений вариантов, получившее название механизмов выбора квазитурнирного типа;

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

- показано, что имеется всего три класса неэквивалентных механизмов квазитурнирного типа, установлены соотношения между этими классами, а также их сужениями;

- исследована замкнутость классов квазитурнирных функций выбора относительно операций пересечения, объединения и суперпозиции, доказано существование верхней аппроксимации

квазитурнирными функциями выбора и рззр^птан з-тгоп-тг* •, о-ъ построения;

- построены прииеры' ряда "Сильных" ?прушснйЗ усл;..л;хй классической рациональности выбора дда таазштркнрк!.' *уккц-.:г;

- сформулирован критерий принадявнности производной фуггкцж выбора подклассу нетривиальных аппроксимаций и с его цомоць» исследованы подклассы тривиальных и нетривиальных верхних аппроксимаций в классах квазитурнирных функций.

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

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

2) Обосновать применение того или иного квазитурнирного механизма выбора в конкретных классах прикладных задач.

3) Семейство алгоритмов построения решающих деревьев, разработанное в диссертации, может использоваться для решения широкого круга прикладных задач управления сложными социальны?»!, экономическими и организационными системами.

Апробация работы. Основные результаты работы докладывались и обсуждались на VI областной научно-технической конференции по применению вычислительной техники (Ростов-на-дону, 1887), на XI Всесоюзном совещании по проблемам управления (Ташкент, 1938), на III Всесоюзной школе-семинаре "Комбинаторно-статистические методы анализа и обработки информации, экспертное оценивание" (Олэг-гл. 1990), на Всесоюзной научно-практической конференции "Гибридные интеллектуальные системы" (Терскол, 1991), на IV Есесгзьног

- б -

школе-семинаре "Статистические и дискретные методы анализа данных и экспертное оценивание" (Одесса, 1991), на научных семинарах кафедры исследования операции (РГУ, механико-математический факультет) и лаборатории экспертных систем ВНИИ ПС.

Публикации. По теме диссертации опубликовано 8 печатных работ, имеется акт внедрения результатов.

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

В подразд. 1.1 проведен обзор подходов к исследованию процедур выбора по результатам парных сравнений вариантов и показано, что ряд простых и широко применяемых на практике процедур, таких как выбор по "сумме очков", по правилу Коупленда и по правилу внешне-внутренней медианы графа, не исследован

систематически с позиции теорш выбора.

В подразд. 1.2 приведены необходимые сведения о модели выбора (предложенной в работах H.a. A.B.

Малишевского), в рамках которой проводится тслздозаязз: А-конечное множество вариантов; Л°- семейство зеох зЕцуетаз; подмножеств множества А\ механизмом Еибора называется пара «т,<з:>, где а- структура, заданная на множестве А, правило выбора, указывающее, каким образом душ каждого предъявления неэти

множество УсХ выбранных из него вариантов. Соответствие Х->У описывается функцией выбора С{Х),Х€Л°. Множество механизмов выбора <z.%> = (<а,ю |стег},где z- множество однотипных структур, называется классом механизмов выбора. Множество функций выбора, генерируемых механизмами из класса <s,ic>, составляет класс Q функций выбора. Объединением, пересечением и суперпозицией двух функций выбора Ctvi Сг называется функция выбора G, определяемая для любого XtJL0 соответственно, как CfnC2<=»Cf <Х)П£?2<Х),

В подразд. 1.3 дается формальное определения механизмов выбора квазитурнирного типа. В качестве множества структур 2 рассматривается множество Т=Ш I Ii сЯ, £ =0, х.у^АУ

ху zy XX

квадратных матриц, а в качестве правил выбора - правила из семейства П={и:аЬ| |а|+|Ь|Д), а.ЬеН), где

%.: C(X)=Arg max Z(at+bt). ab xp ps

a R- множество всех вещественных чисел.

При а= 1 ,Ь=0 правило icab=itw - это известное правило "сум?Л! очков", при а=1,Ь=-1, j_; - правило Коуплендэ и при uab=1t»i ~ правило выбора внешне-внутренней медианы графа .

Механизмы выбора, определяемые структурами из множества Т к

- в -

правилами го семейства П, называны механизмами квазитурнирного типа, Различным значениям параметров а, Ъ, а', ь', отвечают, вообще говоря, различные классы и=<Т.%аЪ> и и'=<Т,%а,ъ,> механизмов выбора квазитурнирного типа и, соответственно, различные классы ЯаЬ и Са>ь>, порожденных ими функций выбора.

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

В подразд. 1.5 вопрос о представимости произвольной выбора С квазитурнирным механизмом <||г^уИ.тс^ сводится к о разрешимости системы линейных уравнений и неравенств:

р€Х рСХ

1<а£ур+&гру)= У.«<?<*>. Х€А°.

рех Рех

где а, Ь, -а и -Ь - постоянные коэффициенты, а элементы

1К1у|| - переменные системы.

Затем в подразд. 1.5 формулируется ряд утверждений относительно свойств системы (1), оказывающихся в дальнейшем полезными при исследовании механизмов выбора квазитурнирного типа.

Обозначив через и - матрицу постоянных коэффициентов, соответствующую неравенствам системы (1), а через Е - матрицу постоянных коэффициентов, соответствующую уравнениям, систему (1) можно переписать в виде:

Uv>0, Еи=0, (2)

где вектор у представляет собой последовательно записанные строки

функции вопросу

(1)

матрицы

матрицы цгху||.

Известно, что система (2) неразрешима тогда и гдах когда система

<УтЕт}ю=0

имеет решение ш, удовлетворяющее условиям

ь

0,^0 У ю >0.

5

где к- число строк матрицы У. Строка матрицы У назван.:

"нарушающей", если ее номер равен номеру положительной компонента

некоторого решения системы (3), удовлетворяющего условиям (4).

Множество всех нарушающих строк матрицы У обозначено через Л(У).

Теорема 1. Функция выбора С порождается механизмом выбора

квазитурнирного типа тогда и только тогда, когда Л(У)=0.

Далее в подразд. 1.5 отмечено, что для двух функций выбора С?

и С2, ШПС2(Ю^0, ЧК^А0. системы (1) могут быть записаны таким

образом, что имеют одинаковые строки и различаются только знаками

равенств и неравенств. Для таких систем, названных согласованными,

имеют место следующие утверждения.

Г У, "I и )

Лемма 1. Пусть С}ПС2/0, а ^ ^ ^ и е сог'ласованныо

матрицы системы (2) для С(и С2 соответственно. Тогда

си

Следствие 1. Пусть С,<Х)=С_(Х), ЧКаА° 1

и,

согласованные матрицы системы (2) для С( и С2 соответственно. Тогда Е^Ег, а У2=У,.

Во второй главе свойства механизмов квазитурнирного тж.-

кследованы как свойства классов порождаемых ими функций выбора.

В подразд. 2.1 рассмотрен вопрос о соотношении классов свазитурнирных функций выбора. В случае произвольных матриц пар^<>:

сравнении, соотношение классов квазитурнирных функций устанавливает

Теорема 2. Имеют место следующие соотношения классов функций выбора, порожденных механизмами квазитурнирного типа: рг,0> |аИЬ|

1> Оаь=

Яп, а=Ъ

где С1 - функция тождественного выбора С(Х)=Х ЧХеА0.

Далее в подразд. 2.1 рассмотрены сужения классов квазитурнирных функций выбора, обусловленные сужением множества структур механизмов квазитурнирного типа. Рассмотрены условия:

ЧХ'У^А' <5>

ух

где через N обозначено множество натуральных чисел,

'*У=£УХ <6)

(7)

Чх.уа. (8)

жу

где через £ обозначено множество целых чисел, и условие

г 20 чх.уеА. (9)

Различные комбинации условии (5)-(9) выделяют во множестве Т содержательные подмножества матриц. Так, например:

- (5)&(8)&(9) - турнирных матриц;

- (б)&(7)&(9) - матрицы расстояний графов;

- (5)&(9) - матрицы "интенсивности предпочтений" экспертов;

- (5)&(7)&(8)&(9) - матрицы многокритериальных турниров. Через Т, и Т обозначим множества элементов из Т,

удовлетворяющих условию (5) и (6), соответственно, а через Т+ -условиям (7)-(9). Классы функций выбора, порожденные классами И +=<2гН,1г . >, и и .=<Т,% >> и и , > механизмов выбора,

аЬ 'аЬ аЬ а Ь аЬ г

+ ~

обозначим соответственно, через ЯаЬ , ЯаЬ и ЯаЬ-

Теорема 3. Классы СаЬ+ и ЯаЬ функция выбора совпадают пр-всех а,Ье{1,-1,0},|а|+|Ь|*0.

Теорема 4. Класс функций выбора совпадает с су^ниямл

Л» Л» »V

¡3)0 и , а класс Яп функций выбора совпадает с сукеЕНягг; С!,с и

«и- ~

Теорема 5. Классы Q1_1 и С2П совпадают и состоят из однсг

функции товдественного выбора.

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

В подразд. 2.2 рассмотрена задача преобразования одних квазитурнирных функций выборе в другие. Изучение таких преобразований позволяет исследовать вопрос о сохранении свойств квазитурнирных функций выбора при различных операциях над ними. Формально это сводится к вопросу о замкнутости классов квазитурнирных функций относительно соответствующих преобразований.

Замкнутость классов квазитурнирных функций отностггельно операции пересечения устанавливает

Теорема 6. Пусть С1 и Сг - функции выбора, порожденные, соответственно, механизмами *Н.тс""> • тХ. '<П1* '2||.11 ,>• а

" ху " аЬ " ху " ао

С(Х)=С>(Х)ПС2(Х)?г0 ЧХеА0. Тогда функция выбора С порождается механизмом <11^' 1+1,.¿.ц,2!

Для исследования вопросов о замкнутости классов относительно операций объединения и суперпозиции используется

Теорема 7. Для того, чтобы произвольная функция выбора принадлежала классу 0 , или необходимо, а при |Л|=3 и

достаточно, чтобы он? \'дэзл?тзэряла соответственно условию:

или конъюнкции услов;-;,. .

[ЗуеС(Л') угсл ..

[ЗуеСШ Эхе* >);Нх,у}]=>[32€Х С({у,л>)={у>].

При |Л|=3, как следуе: из теоремы 7, классы <210 и , замкнуты относительно объединения и суперпозиции, в то время как класс С2() замкнут только относительно суперпозиции. При |А|>3, показано, что ни один из 1слассов квазигурнирных функция выбора не замкнут относительно операций объединения и суперпозиции.

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

С*еС, (10)

С*сС =» СеС ШЦ. (11)

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

каждом классе квазитурнирных функций верхней ашроксимащсн произвольной функции непустого выбора и несущзгт'зозакяз яггегол аппроксимации для произвольной функции выбора.

Для разработки алгоритма построения верхней аппрокс;кзцки 2 классах квазигурнирных функций использовано представление фуша'^д выбора с помощью системы (2).

Обозначим через

и* 'а и 'и

д Е

согласованные матрицы системы

линейных уравнений и неравенств, отвечающих функциям С*, С и С, соответственно. С учетом теоремы 1, леммы 1 и следствия 1 из нов, условия (10) и (11) можно заменить, соответственно, на эквивалентные условия:

' " Л([/)=0, (12)

м-™--

М-"*-

Л(1/)=0

=»Ю=£П. (13)

Теорема 8. Матрица и построенная алгоритмом:

1. ¿=0. ио=и\ Е0=Е*.

2. Е^,=Б_,иЛ(Б_,).

3. Если и^^и^ то Конец.

4. , перейти к шагу 2. удовлетворяет условиям (12) и (13).

В третьей главе для классов квазитурнирных функций проведен анализ нарушений условий классической рациональности выбора. Б теории выбора известно, что область пространства функций выбора, выделяемая условием константности (К)

Х-яХ, С(Х)Г\Х'/0 => С(Х')=С(Х)ПХ'. лежит строго внутри класса турнирных функций выбора и что дан функций турнирного выбора возможны нарушения любого из условий рациональности выбора:

- наследования (Н): Х'сХ=>С<Г )=С(Х)ПГ ,

- согласия (С): Х'ШС*=£»С(Г )ПС(Х*)=С(Х),

- отбрасывания (0): С(Х)сХ'еХ=>С(Г )=С(1).

В силу теорем 2-4 класс многокруговых турнирных функций выбора совпадает с классом Приведен также пример,

демонстрирующий нарушение условий Н, С и О для класса . Таким образом, показано что нарушение условий Н, С и 0 имеет место для любого класса квазитурнирных функций выбора.

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

1) вариант, выбираемый в каждом собственном подмножестве, не выбирается во всем множестве;

2) вариант, выбираемый во всем множестве, не выбирается ни в одном из его собственных подмножеств.

Для класса <210. построен пример (выбор на матрицах и приведенных на рис. 1, по правилу х)0) обоих нарушений, а для класса (выбор на матрице 13, приведенной на рис. 1, по правилу 1С,_,) - нарушения 1). Нарушение 2) для классов Я11 и <?п невозможно в силу теоремы 7. Из этой я© теоремы вытекает, что при |А|=3 нарушение 1) имеет место для любой функции Сев,,, не являющейся функцией тождественного выбора.

Матрица г(

Матрица г.

Матрица г.

У

г

У

У

О -М

-м

-2 О О

-2 О О

О

м м

2 О О.

М N От

М N N

р -М

О

О' р

о о

О р 2 О О

Рис.1. Матрицы и гз размерности |Л|*|А|, И=2.\А\-3, N=4+2

г

г

О

В силу теорем 2-4 класс совпадает с классом

многокруговых турнирных функций выбора. В случае однохруговогс турнира выполнено прямое условие Кондорсе: вариант, выбираемые но всех парных предъявлениях, выбирается и во всем множество, и, следовательно, случай 1) невозможен. Но как показывает вышеприведенный пример, при росте числа кругов (в данном случае для 2|Л|-1 кругов), становится возможной парадоксальная ситуация, которую в "игровых" терминах можно интерпретировать следующим образом: команда, побеждающая в любом подгурнире, не является победителем во всем турнире. Отметим, однако, что при интерпретации условий 1) и 2) в теоретико-графовых терминах ситуации, проиллюстрированные на рис. 1, отнюдь не яьляхлгся парадоксальными. Так, например, некоторая вершина может являться внешней медианой любого подграфа и не являться внешней медианой всего графа и т.д.

В заключение главы 3 рассмотрены .'«рушения классической ,

ст

рациональности выбора отдельно для каждого го подклассов (¿йЬ ' -

нетривиальных верхних аппроксимаций и ЯаЪ - "чэ^уэльных вер/них

аппроксимаций. Подкласс О117 нетривиальных аппрогсимг.:гий содорж;гп

все функции из классг. у, -г.гпгг: .-.а -орхними аппр:''. ".нациями

функций, не принадлежащих Ц, а йт=0\0Н1.

нт т

Для анализа подклассов ЯаЬ и <ЗаЬ сформулирован лтадута/я общий критерий принадлежности функции к подклассу нстр;:;иальных аппроксимаций.

Теорема 9. Пусть Я - произвольный класс, а - его подкласс нетривиальных аппроксимаций. Тогда для того, чтобы ,

необходимо и достаточно выполнения условия: ЗС*£<3 для

верхней аппроксимации, и условия: ВС*=>С, для нижней.

Установленные с помощью теоремы 9 соотношения между нт т

подклассами (ЗаЬ и ЯаЬ , приведены в табл.1

Таблица 1

ш =3 >3

0 аЬ «и в,-, «и «10

0"т чаЬ 0 {С1} «п ¿0 &

с?т аЬ 0 0 ¿0 ¿0

Для каждого из подклассов тривиальных и нетривиальных верхних аппроксимаций в классах квазитурнирных функций построены примеры одновременных нарушений условий Н, С и 0. Таким образом, показано, что условия классической рациональности не выполнены не только для каждого из классов квазитурнирных функций выбора, но и для всех их подклассов тривиальных и нетривиальных верхних аппроксимаций.

В четвертой главе рассматривается применение механизма выбора квазитурнирного типа в задачах индуктивного обучения по примерам.

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

Исходные данные задачи обучения представляют собой множество Е° объектов. Каждый объект описан значениями признаков множества I и помечен некоторым классом из множества С. Выявляемые в результате применения процедуры индуктивного обучения на множестве Е° закономерности представляются в виде решающего дерева, внутренние вершины которого помечены признаками £еГ, каждой дуге, выходящей из вершины, помеченной признаком £, соответствует одно из значений j€.Vl, а листьевые вершины, помечены классами множества

G. Для предсказания класса нового объекта, в caorsz,cthi'ja о наблюдаемыми у него значениями признаков, пркядкгзотс.. --гго гт корневой вершины дерева до некоторого его лио*га.

В подразд. 4.2 задача построения решающего дзрэБа psccrovppv: i как задача выбора лучших вариантов. На оснозэ анализа рзо-.и, посвященных вопросам построения решающих деревьев, выделен р:~*„, наиболее употребительных критериев оценки деревьев. В качэе^ характеристики "наглядности" дерева используется критерия количества листьевых вершин. В качестве характеристики "точности" предсказаний решающим деревом классов новых объектов наиболее часто используется критерий числа ошибок на дополнительной выборке. Наряду с "точностью" предсказания, в некоторых приложениях существенную роль могут также играть ожидаемое время предсказания деревом класса нового объекта, ожидаемая стоимость предсказания и другие- характеристики, связанные с процессами измерений признаков.

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

Далее в подразд. 4.2 предлагается процедура BIST построения решающих деревьев, в которой понятие оптимальности деревьев формулируется на языке функции выбора. Для записи процедуры BIS1' введем следующие обозначения.

Каждому подмножеству объектов Е обучающей выборки Е° поставим

в соответствие множество Х=Х(Е) порождаемых по нему деревьев.

Через Xi обозначим подмножество всех деревьев в X с корневой

вершиной i€l. а через XQ - подмножество деревьев-листьев,

помеченных классами множества G. Очевидно, что X=U X.UX„. Через

i€I 1 G

X{j, JiVl обозначим множество деревьев, порождаемых по примерам из E{j. Зафиксируем произвольный элемент (xi1,...,xlk), fe=|7{| декартова произведения П X.и определим операцию

"подсоединения" х{=Н>Ф(х{>.....где -СО— корневая вершина,

помеченная признаком {, a i(£ - дерево с корневой вершиной {О, в котором к дуге JçV{ присоединено поддерево x{J. Определим также операцию "подсоединения" вершины {О к произвольному подмножеству №=ПХ,,: и>Ф№=Ш}фш,ше№>. Очевидно, что Х.={ОфП X.., а

jcv. j€v. tj

Х=11(Шф П X..)UX_. Через G( • ) обозначим функцию непустого выбора. iex j€vitJ и

заданную на семействе предъявлений U Г2К(Е).

ВСЕ

С учетом принятых обозначений процедура построения множества "лучших" деревьев может быть записана следующим образом. Процедура BIST(E)

Если все объекты множества Е одного класса, то множество В состоит из дерева-листа, помеченного этим классом.

Иначе

Для кавдого tel

Для каждого JçVt

Выделить подмножество Е{^сЕ объектов с J-м

значением í-ro признака

Если EtJcE построить процедурой BEST(E{^)

множество Blj

Возвратить множество В=С( U С(ШФ П В )UC(X )).

iCI J€V J

Теорема 10. Если функция выбора С удовлетвсрлат услс--;:!^.: наследования и отбрасывания, а также для всех ЕгЗ° условия

С(Г)Е{{}ОПС(Х..), Ш. '14>

г

то множество В0 деревьев, построенное процедурна ВЕ51 {£'';• Г совпадает со множеством С(Х°).

В теории выбора известно, что функции выбора, удовлетворяв?;® условиям наследования и отбрасывания порождаются механизма?"! совокупно-экстремального выбора. Другие содержательные подоблзсп: области НПО пространства функция выбора, Еыделяекые условиями согласия и константности, также реализуются критериальные! механизмами выбора. В подразд. 4.3. показано, что условие 04) выполнено для механизмов совокупно-экстремального выбора, выбора по Парето, лексикографического выбора, а также для некоторых других способов выбора по многим критериям, учитывающим информацию о предпочтениях лица, принимающего решения. В качестве критериев оценки решающих деревьев рассматривались критерии вида: ф(г)= 2 т , Х€Х°, где Ъ(х) - множество листьевых вершин дерева

1€Ь(х)1

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

В подразд. 4.4 предложен и сопоставлен с критериальны.^ механизмами квазитурнирный механизм выбора решающих деревьев.

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

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

Такой выбор может бьггь осуществлен механизмом квазитурнирного типа. Положим t™ равным 1, если деревья х к у множества X предсказывают объекту w контрольной выборки Et один и тот же класс и равным 0, в противном случае. Величина 2 tw равна количеству

PCX

деревьев, предсказывающих объекту w тот же класс, что и дерево х,

а величина in® характеризует среднее число деревьев, . xv

р€Х

предсказывающих произвольному объекту w тот же класс, что и дерево х. Механизм квазитурнирного типа <|| 2 t"" ¡,it,_> выбирает в данном

. ху IV

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

Далее-в подразд. 4.4 анализирутся возможность' применения процедуры BEST для выбора из множества Х° лучших деревьев рассматриваемым квазитурнирным механизмом. Матрица || Е t^j

удовлетворяет условию (6) и, согласно теореме 4, данный механизм

принадлежит классу ¿/)Г. Проведения в главе 3 зяализ з^-рт^эьт^ условий классической разиональности выбора показывает, что уелоз:.. НПО для функций класса Qn может быть нарушено. Таким сбрзьом, согласно теореме 10 процедура BEST не может использоваться дл" выбора решающих деревьев механизмом <|| £ t" J,к10>-

tags*

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

ЗАКЛЮЧЕНИЕ

Основные результаты работы заключаются в следующем.

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

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

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

исследовании свойств квазитурнирных функций выбора.

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

Проведан анализ выполнения условий классической рациональности выбора для классов квазитурнирных функций, а также их подклассов тривиальных и нетривиальных верхних аппроксимаций. Построены и проанализирован^! примеры "сильных" нарушений условий классической рациональности, а также примеры одновременных нарушений условий наследования, отбрасывания и согласия.

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

Список публикаций по теме диссертации

1. Наумов Г.Е., Чуев Н.В. Условие представимости одиночного

выбора многокруговым турниром // Тез. докл. VI сбластней научно-технической конференции по применения вычислительно* техники. - Ростов-на-Дону, 1987.

2. Наумов Г.Е., Чуев Н.В. Механизм выбора кзззитурнирного типа // Тез. докл. XI Всесоюзного совещания по проблемам управления. - Ташкент, 1989.

3. Чуев Н.В. Критерий принадлежности функции выбора подклассу нетривиальных аппроксимаций // Тез. докл. III Всесоюзной школы-семинара "Комбинаторно-статистические методы анализа v обработки информации, экспертное оценивание" - Одесса, 1990.

4. Наумов Г.Е., Чуев Н.В. Механизмы выбора квазитурнирного типа I // АиТ. 1990. № 9. С. 109-117.

5. Наумов Г.Е., Чуев Н.В. Механизмы выбора квазитурнирного типа II // АиТ. 1990. №11. С. 135-143.

6. Наумов Г.Е., Чуев Н.В. Анализ нарушений условий классической рациональности выбора для классов квазитурнирных функций // АиТ. 1991. № 1. С. 98-104.

7. Наумов Г.Е., Чуев Н.В. Подход к индуктивному обучению по примерам, основанный на теории принятия решений // Тез. докл. Всесоюзной научно-практической конференции "Гибридные интеллектуальные системы" - Терскол, 1991.

8. Наумов Г.Е., Чуев Н.В. Процедура построения оптимальных решающих деревьев // Тез. докл. IV всесоюзной школы-семинара "Статистические и дискретные метода анализа данных и зкспортнсз оценивание" - Одесса, 1991.