Построение описаний для классов примеров методами конструктивной индукции
В задачах практического уровня сложности возникает проблема выбора «точки слияния» для построения описания класса. Если с теоретической точки зрения можно полагать, что
когда такая точка для некоторого типа маршрута существует, то она единственна, то понятно, что при достаточно сложных практических задачах таких точек может быть не одна и при этом каждая из них будет являться «точкой слияния» не всего множества примеров, а некоторого его подмножества.
Таким образом, необходим некоторый критерий выбора такой точки. Кроме того, множество примеров может содержать некоторый шум. порождённый ошибками описания или классификации. В частности, примеры могут быть не полностью описаны — не содержать некоторых признаков.Среди существующих методов описания классов примеров важное место занимают методы так называемой конструктивной индукции. Основой этого метода являются примеры и некоторые базовые знания, а результатом является общее описание множества примеров. Как примеры, так и само общее описание описываются своими свойствами, которые отделяют их от других описаний. Методы конструктивной индукции направлены на создание таких структур символьных данных, преобразования которых, да и сами структуры легко интерпретируемы пользователем и удовлетворяют так называемому принципу воспринимаемости [32].
Первая задача, возникающая на этом пути, является задачей выбора средств представления концептов, примеров и базовых знаний. Для описания первых двух структур данных используются языки представления. Одним из подходов к языкам описания концептов является так называемая атрибутивная логика. Основная идея атрибутивной логики состоит в том, что концепты и примеры характеризуются атрибутами из предварительно заданных множеств. Отличие от исчисления высказываний состоит в том, что атрибуты здесь являются переменными и могут принимать различные значения из соответствующих множеств.
Примеры в атрибутивной логике часто представляются в виде таблиц, в которых каждая строка содержит описание некоторого примера, а каждая колонка — множество значений некоторого атрибута. Среди атрибутов могут быть булевы, численные, символьные и смешанно-значные атрибуты, а области их значений могут быть ограничены базовыми знаниями.
Как язык описания атрибутивная логика является значительно более пригодной для задач реального уровня сложности, нежели исчисление высказываний. По этой причине атрибутивная логика привлекла внимание разработчиков ряда индуктивных методов машинного обучения, таких как алгоритм TDIDT [33] или AQ [34]. Один из таких алгоритмов, TDIDT, будет рассмотрен ниже.
4.5.1.