Файл: Методыискусственногоинтеллекта.pdf

224
Гл. 5. Приобретение знаний и машинное обучение
Алгоритм заканчивает работу, когда все подмножества помечены,
либо отсутствуют атрибуты, разделяющие непомеченные множества.
Теперь выясним, что такое лучший атрибут и как его найти. До- статочно разумная эвристика основана на подсчете количества классов
C
k в каждом из подмножеств, порожденных различными значениями атрибутов. Более точно, функция, используемая для выбора каждого очередного атрибута — кандидата A
i
, должна увеличивать (по срав- нению с исходной ситуацией) информацию о классах, помечающих обучающие выборки при разбиении рассматриваемого множества S на подмножества S
1
, S
2
, ..., S
n в соответствии со значением атрибута A
i
Эта функция реализуется некоторой индуктивной процедурой. Общая цель этих действий состоит в том, чтобы построенное дерево было минимальным, насколько это возможно без потери точности.
В частности, для оценки «качества» признака можно использовать информационную функцию полезности.
Пусть p
C
k j
— вероятность того, что случайно взятый из S
j пример есть C
k
. Она может быть оценена относительной частотой p
C
k j
= n
C
k j
/n j
, где n
C
k j
— число примеров C
k в S
j и n j
— число классов в S
j
. Энтропия (по Шеннону) подмножества S
j вычисляется по следующей формуле:
H(S
j
) = −
X
k p
C
k j
× log
2
p
C
k j
Пусть значения атрибута A
i расщепляют множество S примеров на подмножества S
j
. Тогда энтропия семейства подмножеств S
j
, порож- денных значениями A
i
, есть
H(S, A
i
) =
X
j
P (S
j
) × H(S
j
),
где P (S
j
) есть вероятность принадлежности некоторого примера S
j к множеству S и оценивается отношением мощностей подмножеств S
j к мощности S:
P (S
j
) =
|S
j
|
|S|
Увеличение информации при таком расщеплении происходит благодаря уменьшению энтропии:
IG(S, A
i
) = H(S) − H(S, A
i
),
где H(S) есть априорная (до расщепления) энтропия S.

5.3. Приобретение знаний из примеров
225
мерами, являющимися «шумными» в том смысле, что значимость при- знака выбрана ошибочным образом. Вторая связана с тем, что если число признаков велико, дерево может содержать ветви, порожден- ные случайными свойствами, являющиеся нерелевантными корректной классификации. Наконец, очень большие деревья трудно интерпрети- ровать, и для пользователя они будут «черными ящиками».
По всем указанным причинам иногда может быть полезно сократить построенное дерево, отсекая некоторые ветви. В принципе, возможны два подхода к отсечению ветвей: он-лайновый интерактивный и пост- сокращение. Он-лайновое отсечение ветвей не позволяет дереву расти,
когда значение функции полезности, связанное с разделением набора примеров, падает ниже некоторого порога. Постсокращение позволяет отсечь некоторые ветви дерева после завершения его построения.
Один из наиболее известных подходов к сокращению был раз- работан в 1986 г. [111]. Авторы предложили отсекать ветви таким образом, чтобы минимизировать полную ожидаемую ошибку класси- фикации на новых примерах. Для этой цели ошибка классификации подсчитывается для каждого узла в дереве. В листьях дерева для оценки ошибки используются методы теории вероятностей. Например,
можно использовать формулу Лапласа.
Для узлов, не являющихся листьями дерева решения, ошибка клас- сификации вычисляется как взвешенная сумма ошибок классификации поддеревьев каждого из узлов. Вес полагается равным относительной частоте примеров, «передаваемых» из узла в соответствующие подде- ревья. Далее ошибка классификации в «нелиственном» узле оцени- вается для случая отсечения ветвей, исходящих из него, так что он становится листом. Если эта оценка меньше, чем предыдущая, то со- ответствующие поддеревья отсекаются. Этот процесс распространяется от основания дерева к его листьям до тех пор, пока оценки ошибки уменьшаются.
Преимущества постсокращения по сравнению с интерактивными методами состоят в том, что при постсокращении можно учесть гло- бальные свойства дерева классификации, в то время как при интер- активном отсечении ветвей минимум ошибки может оказаться локаль- ным. Возможны и комбинированные подходы.
Другие подходы к упрощению дерева.
На рис. 5.3. показан еще один тип упрощения дерева: на этот раз целью является выполнение некоторой конструктивной индукции.
Обучающаяся система пытается создать новые атрибуты, представля- ющие собой логические выражения над атрибутами, предоставленны- ми учителем. Конструктивная индукция может быть полезна в тех ситуациях, когда поддерево повторяется в дереве в более чем одной позиции — см. рисунки 5.4. и 5.5.
8 Г. С. Осипов

226
Гл. 5. Приобретение знаний и машинное обучение
Рис. 5.3. Конструктивная индукция в деревьях решений. Строится новый ат- рибут, at4
Рис. 5.4. Проблема дублирования поддеревьев в деревьях решений

5.3. Приобретение знаний из примеров
227
Рис. 5.5. Упрощенная версия дерева с предыдущего рисунка
Работа с численными данными. До сих пор наш анализ огра- ничивался символьными атрибутами. Однако деревья вывода можно
Рис. 5.6. Дерево решений для численных атрибутов строить и по численным атрибутам.
Один из возможных путей состоит в том, чтобы ввести дополнитель- ный шаг — преобразование числен-
ных атрибутов в двоичную форму,
т. е. разделение множеств их число- вых значений с помощью некоторо- го порога на пары подынтервалов,
которые можно считать символами.
На рис. 5.6 показано дерево реше- ния, построенное по числовым дан- ным. В каждой вершине значение со- ответствующего атрибута сравнива- ется с порогом T
i
Положение порога на множестве значений можно, опять-таки, опреде- лить через энтропию. Предположим,
требуется дискретизировать множество значений атрибута at1. Сна- чала мы упорядочим все примеры по значению at1 и проследим за классифицирующими значениями. В случае, описанном на рис. 5.7,
классифицирующие значения (+) и (–) разбивают множество из 80
примеров на 4 области (на практике таких областей обычно бывает больше). Предполагаемые точки разбиения лежат на границах обла- стей. Затем для каждой из этих точек вычисляется информативность
8*

228
Гл. 5. Приобретение знаний и машинное обучение
Рис. 5.7. Примеры, упорядоченные по значениям некоторого атрибута; s1, s2
и s3 — предполагаемые точки разбиения
(ранее объяснялось, как это делается) и выбирается точка с наиболь- шей информативностью.
Таким образом, числовая версия алгоритма TDIDT выглядит следу- ющим образом.
Алгоритм TDIDT для численных данных:
1. Используя меру энтропии, найти оптимальную точку разбиения для каждого численного атрибута.
2. Найти атрибут, чья точка разбиения максимально увеличивает энтропию и разбивает множество примеров по значению этого атрибута на два подмножества.
3. Если терминальный критерий не выполнен, повторять процедуру рекурсивно для каждого подмножества.
Заметим, что с каждым новым поддеревом необходимо пересчи- тывать точки разбиения. Скорей всего, оптимальное положение точки разбиения в разных подмножествах примеров будет разным.
5.3.4. Последовательное покрытие: AQ-обучение. AQ-обуче- ние основывается на идее постепенного покрытия обучающих данных с помощью последовательно порождаемых правил. Этот подход исполь- зуется целым семейством методов, основанных на алгоритме, который впервые был опубликован в работе Михальского в 1969 г. [112].
Суть метода заключается в поиске множества правил (конъюнкций пар атрибут–значение или, в общем случае, произвольных предикатов),
которое покрывает все (+) примеры и ни одного (–) примера. Вместо разбиения множества примеров AQ-алгоритм шаг за шагом обобщает описания выбранных положительных примеров, называемых опорными примерами.
AQ-алгоритм. Для демонстрации основного принципа
AQ-обуче- ния рассмотрим упрощенный вариант AQ-алгоритма. Предположим,
цель — обнаружить минимальное множество правил, характеризующих заданный концепт. Правила будут иметь вид:
если A
1
и A
2
и ... и A
n
то C

5.3. Приобретение знаний из примеров
229
где C — концепт, а условия A
i могут быть записаны в обычной атри- бутной форме at i
= V или иметь более общий вид: at i
= v
1
∨ v
2
∨ v
3
...,
где атрибут может принимать одно из нескольких значений (связанных внутренними дизъюнкциями).
Собственно алгоритм имеет следующий вид:
1. Разделить все примеры на подмножества P E положительных примеров и NE отрицательных примеров.
2. Выбрать из P E случайным образом или по каким-то соображе- ниям один пример, который будет считаться опорным примером.
3. Найти множество максимально общих правил, характеризующих опорный пример. Предел обобщения определяется множеством
N E: обобщенное описание опорного примера не должно удовле- творять ни одному объекту из NE. Полученное таким образом множество правил называется опорным множеством.
4. Используя некоторый критерий предпочтения, выбрать лучшее правило в опорном множестве.
5. Если это правило вместе с ранее порожденными таким образом правилами покрывает все объекты из P E, то конец. Иначе — най- ти другой опорный пример среди неохваченных примеров в P E
и перейти к 3.
Шаг 3 выполняется специальной процедурой порождения опорно- го множества правил. Критерий предпочтения для выбора правил на шаге 4 определяется характером решаемой задачи. В качестве тако- го критерия может выступать комбинация различных элементарных критериев, таких как требование максимального числа положительных примеров, описываемых правилом минимального числа используемых атрибутов, максимальной оценки степени общности, т. е. отношения числа положительных примеров, покрываемых правилом, к числу всех примеров, минимальных затрат на измерение значений атрибутов и т. п.
Кроме того, можно использовать критерии выбора атрибутов, как в обу- чении деревьям решений, такие как энтропия, информационная функ- ция полезности и т. д. Алгоритм позволяет также строить множество правил с различными отношениями между отдельными правилами.
Проиллюстрируем работу алгоритма на простом примере.
Пример.
Примеры, описанные в табл. 5.14 в терминах атрибутов at1, at2
и at3, изображены на рис. 5.8. В табл. 5.14 каждая строка соответ- ствует одному вектору значений атрибутов. Строки, соответствующие положительным примерам, помечены (+), а строки, соответствующие отрицательным примерам, помечены (–). Предположим, критерий пред- почтения рекомендует выбирать правила, охватывающие максимально возможное число положительных примеров и условия правил могут пересекаться друг с другом.

230
Гл. 5. Приобретение знаний и машинное обучение
Т а б л и ц а 5.14. Спецификация обучающего множества
Пример at1
at2
at3
Классификация
P E
e1
y n
r
(+)
e2
x m
r
(+)
e3
y n
s
(+)
e4
x n
r
(+)
N E
f 1
x m
s
(–)
f 2
y m
t
(–)
f 3
y n
t
(–)
f 4
z n
t
(–)
f 5
z n
r
(–)
f 6
x n
s
(–)
Программа, ведущая к выявлению правил из приведенных приме- ров, будет состоять из следующих шагов:
1. Выбрать первый опорный пример: e1.
2. Для построения опорного множества примера e1 (т. е. мно- жества максимально общих описаний e1), начать с построения множества всех описаний e1, которым не удовлетворяют отрица- тельные примеры.
Для этого обобщим какой либо атрибут опорного примера,
например, at1, получив at1 = x ∨ y, т. е. R1 : at1 = (x ∨ y) & at2 =
= n) & (at3 = r).
Далее займемся вторым атрибутом, получив в результате пра- вило
R1
′
: at1 = (x ∨ y) & (at2 = n ∨ m) & (at3 = r).
Попытки дальнейшего обобщения этого описания приводят к тому, что ему (дальнейшему обобщению) начинают удовлетво- рять и отрицательные примеры. Например, обобщение атрибута at3 следующим образом: at3 = r ∨ s, приводит к тому, что полу- ченному правилу удовлетворяют примеры f1 и f6.
Таким образом,
R1
′
: at1 = (x ∨ y) & (at2 = n ∨ m) & (at3 = r)
и возможности такого обобщения опорного примера e1 исчер- паны.
Однако если мы начнем с атрибута at3, то применяя изло- женные соображения, получим правило R2
′
: (at1 = y) & (at2 =
= n ∨ m) & (at3 = r ∨ s). Исключая атрибут at2, так как в обоих правилах используется все множество его значений, получим следующие результаты:
R1
′
: (at1 = x ∨ y) & (at3 = r),

5.3. Приобретение знаний из примеров
231
R2
′
: (at1 = y) & (at3 = r ∨ s).
3. Это опорное множество правил для e1. Предположим, что кри- терий предпочтения рекомендует выбрать из опорного множества правило, которое охватывает наибольшее число положительных примеров. Будет выбрано R1
′
, так как оно охватывает три приме- ра, тогда как R2
′
— только два. Следующий шаг — выбор нового опорного примера из положительных примеров, которые пока не охвачены. Есть только один такой пример — это e3.
4. Выбрать следующий опорный пример: e3.
• Построить опорное множество для нового опорного примера.
Порождаются два правила R3 : (at1 = y ∨ z) & (at3 = s) и
R4 : (at1 = y) & (at3 = r ∨ s).
• Правило, удовлетворяющее большему числу положительных примеров, совпадает с R2
′
• Поскольку неиспользованных примеров больше не осталось,
выбранные нами правила R1
′
и R2
′
составляют полное и непротиворечивое описание искомого концепта, полученное благодаря использованному критерию предпочтения:
R1
′
(at1 = x ∨ y) & (at3 = r),
R2
′
(at1 = y) & (at3 = r ∨ s).
В обучающиеся системы, основанные на алгоритме AQ, можно легко интегрировать базовые знания, поскольку такие знания часто представляются в виде систем правил. Мы, однако, на этой особенно- сти останавливаться не будем, так как использование базовых знаний более свойственно обучающимся системам, основанным на логике пре- дикатов, и о них мы поговорим позднее.
Двухфазный подход. Для обучения в условиях недоопределенного контекста и с зашумленными данными был предложен двухфазный подход. Этот подход облегчает также обработку контекста и снижает сложность получения результата в AQ-парадигме.
Принципиальная идея состоит в расщеплении описания концепта на две части: базовое представление концепта (БПК), содержащее экспли- цитную характеристику концепта, хранящуюся в памяти обучающейся системы, и механизм сопоставления с концептом на основе вывода
(СКВ), содержащий множество правил вывода, которые применяются на этапе сопоставления примеров с БПК.
Продемонстрируем это на примере. Пусть БПК содержит правило
если A
1
и A
2
и ... и A
n
то X