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

Страницы:
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 

— приведение основных этапов идентификации деревьев решений в соответствие с решаемой зада­чей;

— создание правил преобразования деревьев ре­шений в лингвистические правила;

— сравнение разработанного подхода с суще­ствующими методами индукции лингвистических правил.

1. Постановка задачи

Пусть задана база лингвистических правил RB = [Я1,Я2...,RRN}, описывающая объекты обу­чающей выборки O = [O1,O2,...,ON}. Тогда на основе обучающей выборки объектов O требуется сформировать такую базу лингвистических правил RB* = {R1,R2,...,RRN*}, RN* <<RN , которая обе­спечивала бы приемлемое качество прогнозирова­ния экспертной системы, построенной на основе полученной базы лингвистических правил RB*:

Q(RB*) > Qlhreshold . где Q (RB *) — точность прогнозирования или клас­сификации по базе правил RB * ; Qlhreshoid мини­мально допустимая точность прогнозирования или классификации.

2. Деревья решений

Деревья решений представляют собой графовые интеллектуальные модели, во внутренних узлах которых расположены функции принятия реше­ний на основе значений входных переменных, а во внешних узлах (терминальных узлах, листьях) содержатся значения выходной переменной, соот­ветствующие условиям внутренних узлов [2, 6, 7].

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

БИОНИКА ИНТЕЛЛЕКТА. 2011. 3 (77). С. 126-130

ХНУРЭ

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

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

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

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

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

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

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

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

3. Индукция лингвистических правил на основе построения деревьев решений

Существующие методы построения деревьев решений [2—7] не учитывают особенностей задачи индукции лингвистических правил. В связи с этим разрабатывается новый метод построения деревьев решений для индукции правил. Подобно извест­ным методам построения дерева решений, предла­гаемый метод состоит из основных фаз: рост дерева и его сглаживание (сокращение), после чего вы­полняется преобразование дерева решений в линг­вистические правила. Наиболее важными аспек­тами предлагаемого метода являются следующие: использование модифицированной энтропии как оценочной меры, и использование сглаживания для отсечения.

Таким образом, предлагаемый метод состоит из следующих этапов:

— рост дерева;

— сглаживание дерева;

— преобразование дерева решений в лингвисти­ческие правила.

На этапе роста дерева предлагается использовать жадный подход. В каждом узле, соответствующем подмножеству Г обучающей выборки, выбирается признак f и значение v таким образом, что данные из Г разделяются на два подмножества Tjv и Tjv исходя из условий xif < v :Tj-v = {xt єT:xt f < v} и

Tjv = {x{ є T: > v}. Такое разбиение разделяет множество объектов обучающей выборки на такие, для которых значение признака fменьше значения v, и на те, для которых значение признака f больше значения v.

С целью разбиения дерева решений для каж­дого возможного разбиения (f, v) рассчитывается оценочная функция (1):

Q(f, v) = pf ,vg(p'f ,v ) + (1 - Ff ,v )g(Pj,v ), (1)

где pj v = P(yt = 1| xt є T/,v), pj,v = P(Уі = 11X є Tf]v) и pfv = P(x{ є Tf v | x, є T); g(p) модифицированная энтропия для вероятности отнесения выходной переменной y к рассматриваемому классу при усло­вии, что x больше или меньше значения v (p^f v и pjv соответственно):

g(p) = -r(p)ln(r(p)) - (1 - r(p))ln(1 - r(p)), (2) где r(p) преобразует оценку вероятности:

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

Г ( p):

-(1+ J 2 p -1 ),если p > 0,5; -(1 --JT—22p),если p > 0,5.

(3)

Таким образом, чем ближе значение вероятно­сти к 0,5, тем выше модифицированное значение, а чем дальше от 0,5, тем значение ниже.

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

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

Далее описывается подход, который вместо урезания полного дерева будет производить пере­оценку вероятности каждого листового узла путем усреднения оценки вероятности по пути следова­ния от корневого узла к листовому узлу. Для дости­жения данной цели была взята идея «утяжеления дерева» [8]. Если используется дерево для сжатия бинарного классового признака yi, основанного на xi, то в таком случае метод утяжеления дерева гарантирует, что коэффициент сжатия переоце­ненной вероятности не будет хуже, чем в успешно усечённом дереве. Так как предлагаемый метод применяется в большей степени к трансформиро­ванной оценке вероятности г(p), чем непосред­ственно к p, то теоретически результат может быть следующим: путем использования переоцененной вероятности можно достичь ожидаемую классифи­кацию обучающего множества с не худшим резуль­татом, чем у правильно усеченного дерева.

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

Пусть узлы T1 и T2 являются элементами одно­го уровня с общим родительским узлом T . Пусть p(T1), p(T2) и p(T) будут соответствующими оценками вероятности. Локальная переоценен­ная вероятность это wTp(T) + (1 - wT)p(T1) для T и wTp(T) + (1 - wT)p(T2) для T2. Локальная значи­мость wT и сопутствующая функция G(T) рассчи­тываются рекурсивно, основываясь на следующих формулах:

c exp(- |T | g (p(T)))

G (T ):

g(p(T)) +     log((1 + -)w— ), если Wt > 0,5, ]IG T1) + f G (T-) +

Страницы:
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 самых важных уроков библии

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

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

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

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