http://npc-news.ru/

Построение описаний для классов примеров методами конструктивной индукции

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

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

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

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

Как язык описания атрибутивная логика является значи­тельно более пригодной для задач реального уровня сложно­сти, нежели исчисление высказываний. По этой причине ат­рибутивная логика привлекла внимание разработчиков ряда индуктивных методов машинного обучения, таких как алгоритм TDIDT [33] или AQ [34]. Один из таких алгоритмов, TDIDT, будет рассмотрен ниже.


Комментарии закрыты.