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

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

Таблица 19.1. Примеры результатов измерения проводимости образцов материалов

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

Листинг 19.3. Алгоритм поиска минимального совместимого определения

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

<< В начало < Предыдущая 1 2 Следующая > В конец >>