Описание реализации алгоритма поиска от частного к общему

В программе «Поиск от частного к общему» алгоритм поиска реализован на примере, подобном описанному в [1, 9.2.2].

1. Класс exemplar. Она используется для описания гипотез и обучающих примеров.

Членами (полями) класса являются:

• 1) color типа string — цвет объекта;
• 2) size типа string — размер объекта;
• 3) shape типа string — форма объекта;
• 2. s_list типа ArrayList — список существующих гипотез;
• 3. n_list типа ArrayList — список для хранения отрицательных примеров;
• 4. p_list типа ArrayList — список для хранения положительных примеров;

goal типа string — цель обучения;

Работа программы разделена на два этапа. Сначала пользователь должен обучить систему новому понятию. Для этого предусмотрен режим обучения. Затем он может проверить качество обучения в режиме тестирования. До начала обучения пользователь должен сообщить программе изучаемое понятие.

Алгоритм поиска реализован с помощью двух процедур:

• 1. PartToGenSearch (с входным параметром positive тип bool — отображающий к какому виду примеров он относится) для осуществления по шагового отображения выполнения алгоритма;
• 2. PartToGenSearch_Auto для реализации автоматического режима выполнения алгоритма.

Замена гипотезы минимальным более общим понятием при обработке положительного примера происходит следующим образом. Последовательно просматриваются все поля гипотезы (цвет, размер, форма). Если в поле гипотезы стоит переменная (X, Y или Z), то это поле пропускается. Если же в поле гипотезы записана константа (например, красный), то это поле сравнивается с соответствующим полем заданного примера, и если они не равны, то в гипотезу записывается переменная. Если это поле характеризует цвет, то записывается X, если размер, то Y, а если форму, то Z.

Затем согласно алгоритму из множества гипотез удаляются все гипотезы, более общие, чем некоторые другие. Просматривая список гипотез, ищем гипотезу с двумя переменными. Если нашли такую гипотезу, то начинаем искать гипотезу с одной переменной, т.к. только такая гипотеза может быть более частной. Если найдена такая гипотеза. То проверяем, не является ли она более частной, чем ранее найденная гипотеза. Для этого берем гипотезу с двумя переменными и сравниваем ее поле, значение которого является константой с соответствующим полем гипотезы с одной переменной. Если эти поля равны, то это означает, что гипотеза с одной переменной является более частной. Тогда гипотеза с двумя переменными удаляется из списка.

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

Тестирование начинается тогда, когда пользователь считает, что он задал достаточно примеров для обучения системы. Если при этом все примеры были корректны, то в списке гипотез должны содержаться только гипотезы, точно описывающие изучаемое понятие. В режиме тестирования пользователь задает пример, выбирая свойства объекта из предложенных списков. Программа, просматривая список гипотез, сравнивает их с заданным примером. Если все поля гипотезы, содержащие константы равны соответствующим полям заданного примера, то это означает, что заданный пример описывает объект, соответствующий изучаемому понятию. И программа выдает сообщение, подтверждающее, что заданный пример есть изучаемое понятие. В противном случае программа выдает сообщение, что заданный пример не является изучаемым понятием.