Алгоритм AQ (AQ algorithm)

Разделы: Алгоритмы

В машинном обучении алгоритм AQ — это классификатор, работающий на основе обобщения. Строится на основе обучения с учителем (т.е. для обучения ему требуются обучающие примеры, для которых задана метка класса). Является разновидностью алгоритмов покрытия.

Алгоритм формирует классификатор, состоящий из набора продукционных правил вида «если [условие], то [класс]». Таким образом, одно правило формируется для одного класса. Правило может содержать несколько условий, тогда его результатом будет конъюнкция результатов каждого из них, например:

ЕСЛИ (Доход=низкий) И (Недвижимость=отсутствует) ТО «Отказать».

Алгоритм начинает работу со случайного выбора примера (зерна) из обучающего множества, для которого строится правило, покрывающее данный пример и примеры, относящиеся к тому же классу. Затем выбирается второе «зерно», и итерация повторяется. Пустое условие в правиле означает, что оно покрывает все примеры обучающего набора.

В алгоритме AQ новый пример классифицируется следующим образом:

• среди всех сформированных решающих правил ищется то, которое покрывает пример;
• если найдено только одно правило, то примеру присваивается значение класса, указанного в правиле;
• если пример покрывает несколько правил, то значение класса выбирается как наиболее вероятное среди всех примеров обучающего множества, которые покрываются найденными правилами;
• если ни одно из сформированных правил не покрывает пример, то значение класса выбирается как наиболее часто встречающееся среди всех примеров обучающего множества (значение класса по умолчанию).

На каждой итерации для выбора наилучшего правила вычисляется количество покрываемых этим правилом примеров и выбирается то, для которого покрытие наибольшее. Если для нескольких правил покрытие одинаковое, то предпочтение отдается наиболее короткому правилу (содержащему наименьшее число условий).

Недостатком алгоритма является случайный характер выбора примера (зерна), для которого строится начальное правило. От выбора начального примера зависит конечный вид модели и точность классификации.

Таким образом, в результате работы алгоритм AQ формирует множество правил покрытия, а также правило по умолчанию, которое будет использоваться, если объект не покрывается ни одним сформированным правилом.