Иллюстрированный самоучитель по введению в экспертные системы



             

Алгоритм формирования дереврешений по обучающей выборке - часть 5


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

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

Недостатком эвристики, основанной на приросте количества информации, является то, что она отдает предпочтение процедурам с наибольшим количеством выходных значений {О1, O2, ..., Оn}. Возьмем, например, крайний случай, когда практически бесполезные тесты будут разделять исходную обучающую выборку на множество классов с единственным представителем в каждом. Это произойдет, если обучающую выборку с медицинскими данными пациентов классифицировать по именам пациентов. Для описанной эвристики именно такой вариант получит преимущество перед прочими, поскольку UT(S) будет равно нулю и, следовательно, разность Gs(T) = U(S) - UT(S) достигнет максимального значения.

Для заданной тестирующей процедуры Т на множестве данных S, которая характеризуется приростом количества информации GS{T), мы теперь возьмем в качестве критерия отбора относительный прирост НS(Т), который определяется соотношением

НS{Т) = GS(Т)/V(S),

где

V(S) = -Sumi=1,..., (|S|/|Si|) x log2(|S|/|Si|).

Важно разобраться, в чем состоит отличие величины V(S) от U(S). Величина V(S) определяется множеством сообщений {О1, О2,...,Оn] или, что то же самое, множеством подмножеств {S1 S2,...,Sn}, ассоциированных с выходными значениями тестовой процедуры, а не с множеством классов {С1 C2,...,Ck}.


Содержание  Назад  Вперед