Автор неизвестен - Бионика интелекта информация язык интеллект№ 3 (77) 2011научно-технический журналоснован в октябре 1967 г - страница 64

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 

|T|

|T|

+—log((1 + c)(1 - iwT)), впротивном случае.

Параметр с устанавливается априорно и пока­зывает Байесову «оценку» разбиения. Для листово­го узла Тустанавливается: G(T) = g(p(T)) и wT =1.

После вычисления значимостей wT для каждого узла рекурсивным методом (используется нисхо­дящая рекурсия) необходимо рассчитать глобаль­ную оценку вероятности для каждого узла дерева сверху вниз. Данный этап усредняет все оценки r(p) от корневого узла T0 к узлу Th по пути T0, Th, основываясь на значимости wT. Следует отметить, что значимость wT является лишь локально важ­ной. Это означает то, что глобальная значимость узла Th является wT * = Пі<k (1 - wi )wk на всём пути.

По определению, ^ h=1 wi = 1 для любого направле­ния, ведущему к листу. По следующим рекурсив­ным формулам вычисляется глобальная переоцен­ка подчиненных узлов T1 и T2 в родительском узле T:

wT (1 - wT),

г *(T) = г *(T) + w—w—r (p(Ti)),

(4)

(5)

1 -wt   exp(-1T1 |G(71)- |T-|G(T-)) '

где r(p(T)) преобразование по формуле (3) из оценки вероятности p(T) в узле T. В корневом узле устанавливается: w = 1. После вычисления г *(Th) для листового узла Th в качестве оценки вероятности можно использовать следующее: гч(Th)). Метка класса для Ti будет равна единице, если г(Ti) > 0,5 , в противном случае нулю. Усечение дерева вы­полняется, начиная с основания по направлению вверх путем проверки идентичности узлов одного уровня. Если идентичность узлов выявлена, то они удаляются и используется значение родительского узла. Данная процедура будет продолжаться до тех пор, пока она не станет невозможной. Метод сгла­живания последовательно улучшает работу дерева. Оценка временной сложности O(M), где M количество узлов неусеченного дерева.

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

1. Любому человеку легче понять и изменить набор правил, чем понять и изменить дерево ре­шений. Потребность в таком изменении очевид­на. Например, может возникнуть ситуация, когда имеется некоторое несоответствие между обучаю­щей выборкой и реальной системой, что требует

1-8

ИНДУКЦИЯ ЛИНГВИСТИЧЕСКИХ ПРАВИЛ С ИСПОЛЬЗОВАНИЕМ ДЕРЕВЬЕВ РЕШЕНИЙ

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

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

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

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

1. Проверка условий ">" и "<" во всех прави­лах с целью устранения избыточности в описании условий правил. Таким образом, выполняется, на­пример, следующее преобразование: (x < 3) n (x < 5) заменяется на (x < 3).

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

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

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

Предложенный метод индукции лингвистичес­ких правил с использованием деревьев решений был программно реализован на языке программи­рования C#.

Для экспериментов использовались тестовые данные, которые были взяты из общедоступных репозиториев [9]. Экспериментальные исследова­ния проводились на основании выборки, которая содержала информацию об эхокардиограммах па­циентов с сердечными приступами. Выборка со­держала информацию о 132 пациентах, каждый из которых характеризовался 12 признаками. Кроме того, для каждого пациента указывалось, жив он или умер.

Предложенный метод индукции нечётких пра­вил сравнивался с мультиагентным методом и каноническим методом эволюционного поиска. Исходя из проведенных экспериментов, были по­лучены базы лингвистических правил, характери­зующиеся следующим качеством классификации пациентов: 81,3%, 79,1% и 92,7% для мультиаген-тного, эволюционного и предложенного методов, соответственно.

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

Выводы

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

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

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

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

Список литературы: 1. Субботін, С. О. Подання й обробка знань у системах штучного інтелекту та підтримки прий­няття рішень : навч. посібник [Текст] / С. О. Субботін. — Запоріжжя: ЗНТУ, 2008. — 341 с. 2. Encyclopedia of artificial intelligence / Eds.: J. R. Dopico, J. D. de la Calle, A. P. Sierra. New York : Information Science Reference, 2009. — Vol.

Е. А. Гофман, А. А. Олейник, С. А. Субботин

1—3. — 1677 p. 3. Rokach L. Data Mining with Decision Trees. Theory and Applications / L. Rokach, O. Maimon. London : World Scientific Publishing Co, 2008. — 264 p. 4. Quinlan J. R. Induction of decision trees / J. R. Quinlan // Machine Learn­ing. — 1986. — № 1. — P. 81—106. 5. Quinlan J. R. Decision trees and decision making / J. R. Quinlan // IEEE Transac­tions on Systems, Man and Cybernetics. — 1990. — № 2 (20).

P. 339—346. 6. Liu X. A decision tree solution considering the decision maker's attitude / X. Liu, Q. Da / / Fuzzy Sets and Systems. — 2005. — № 152 (3). — P. 437—454. 7. Clas­sification and regression trees / L. Breiman, J. H. Friedman, R. A. Olshen, C. J. Stone. California : Wadsworth & Brooks, 1984. — 368 p. 8. Willems F. M. J. The Context Tree Weighting Method: Basic Properties / F. M. J. Willems, Y. M. Shtarkov, T. J. Tjalkens // IEEE Transactions on Information Theory.

— 1995. — № 3. — P. 653—664. 9. UCI Machine Learning Re­pository [electronic resource] / Center for Machine Learning and Intelligent Systems. Access mode : http://archive.ics. uci.edu/ml/datasets.html.

Поступила в редколлегию 20.06.2011

УДК 004.93

Індукція лінгвістичних правил з використанням дерев рішень / Є. О. Гофман, А. О. Олійник, С. О. Субботін // Біоніка інтелекту: наук.-техн. журнал. — 2011. — № 3 (77). — С. 126-130.

Розглядається завдання індукції лінгвістичних пра­вил. Розроблено метод ідентифікації дерев рішень для індукції лінгвістичних правил. Створено програмне за­безпечення на основі запропонованого методу.

Бібліогр.: 9 найм.

UDC 004.93

Linguistic Rules Induction with Decision Trees / Ye. A. Gof-man, A. O. Oliinyk, S. A. Subbotin // Bionics of Intelligense: Sci. Mag. — 2011. — № 3 (77). —P. 126-130.

The problem of linguistic rules induction is considered in this paper. A method of decision trees identification for the linguistic rules induction is developed. The software based on the proposed method is created.

Ref.: 9 items.

УДК 004.93

intelligence

С.А. Зайцев1, С.А. Субботин2

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

Автор неизвестен - Беседы на книгу бытие

Автор неизвестен - Беседы на шестоднев

Автор неизвестен - Богословие

Автор неизвестен - Божественность христа