3.3.2. Обобщение по признакам

На признаковых структурах решаются обычно задачи классификации и формирования понятий.

Постановка задач

Задача классификации по признакам

Пусть имеется некоторое множество Zобъектов и множество П = {_i}, il.n, признаков. Для каждого признака_iП, il.n, задана область его определенияDi.Каждый объект sZ однозначно определяется вектором П_sзначений его признаков: П_sD₁X ...XDn.Известно, что классыK.₁, К.₂,...,К.тявляются подмножествамиZ.Для каждогоKj,jl,m, задана информацияI_jв виде обучающей выборки <v_j+,v_j->множеств положительных и отрицательных примеров: v_j+K_j,v_j-K_j=. Требуется построить решающие правила_j,j1,m,позволяющие определить принадлежность произвольного объекта sZ классамKj.

Задача формирования понятий

Требуется по обучающей выборке vZпо тем или иным критериям выделить совокупность классов{Kj}и построить для них решающие правила_j. В общем случае каждый объект обучающей выборки можно представить точкойn-мерного признакового пространства; тогда классы будут являться областями этого пространства.

Методы построения решающих правил:

1. Метод разделения. Применяется, когда признаки _iявляются измеримыми (количественными признаками). Решающие правила_jпри этом являются разделяющими функциями, ограничивающими фигуры пространства признаков. Разделяющие функции, как правило, выбираются линейными, квадратичными или кусочно-линейными.

2. Метод потенциальных функций. Также применим для измеримых признаков. Решающие функции _jпри этом называются потенциальными и описываются так, чтобы их экстремум находился на множестве sKj.

3. Кластерный анализ. Большая группа методов автоматической классификации и формирования понятий, применяемых в условиях отсутствия априорного разбиения на классы.

4. Метод голосования (качественных оценок). Применяется при наличии качественных (неизмеримых) признаков. Производится сравнение значений признаков со значениями признаков эталонных объектов. Мера близости объекта эталону определяется по мажоритарному принципу (путем голосования по признакам).

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

3.3.3. Структурно-логические методы обобщения

3.3.3.1. Методы индуктивного вывода в формальных исчислениях

Данные методы разработаны на основании теории исчисления предикатов. Их различия заключаются в применении различных схем вывода. Наиболее известны следующие методы:

1. Схема индуктивной резолюции. А также множество аналогичных методов, использующих некоторые другие методики логического вывода.

2. Метод "звезды". Особенность заключается в применении эвристик для выбора наиболее перспективных гипотез.

3. ДСМ-метод.

4. GUHA-метод (авторы – коллектив Гаека). Особенность заключается в применении теории вероятностей и математической статистики. В логический вывод вводится элемент случайности и вероятностная мера.

3.3.3.2. ДСМ-метод

В основу метода положены следующие принципы индукции:

1. Принцип единственного различия. «Если после введения какого-либо фактора появляется (или после его удаления исчезает) известное явление, причем мы не вводим и не удаляем никакого другого обстоятельства, которое могло бы иметь влияние, то указанный фактор составляет причину явления.»

2. Принцип единственного сходства. «Если все обстоятельства явления, кроме одного, могут отсутствовать, не уничтожая этим явления, то это обстоятельство является причиной данного явления.»

3. Принцип единственного остатка. «Если вычесть из какого-либо явления ту его часть, которая является следствием известных причин, то остаток явления есть следствие остальных причин.»

В приведенном примере полученное правило подлежит дополнительной проверке при помощи первых двух принципов в целях выяснения, является причина комплексной или простой.

Применение схем Милля требует репрезентативности выборки.

Суть ДСМ-метода.

Пусть задано множество причин A={A₁,A₂, …,A_p}, множество следствийB={B₁,B₂, …,B_m} и множество оценокQ={q₁,q₂, …,q_r}. Выражение видаA_iB_jназывается положительной гипотезой с оценкой достоверностиq_k. Обратная гипотеза называется отрицательной. Положительные гипотезы обозначимh⁺_i,j,k, отрицательные –h^-_i,j,k. Гипотезы с оценкамиq_k= 0 иq_k= 1 рассматриваются как явления с установленной истинностью (ложностью).q_kнаходится как доля примеров, подтверждающих гипотезу.

Обобщенный алгоритм ДСМ-метода

1. На основе исходного множества положительных и отрицательных примеров формируется набор гипотез в виде матриц M⁺иM^-:

Основным способом формирования гипотез является использование принципов единственного сходства и единственного различия.

2. К исходному множеству примеров добавляются новые наблюдения, которые могут либо подтверждать выдвинутые гипотезы, либо опровергать их, при этом оценки гипотез (и матрицы M⁺иM^-) изменяются.

3. В случае невыполнения условий окончания вывода переход к шагу 2.

В качестве условий окончания вывода используются близость q_kк 0 или 1, а также ограничения (времени, количества примеров и пр.).

3.3.3.3. Методы обобщения на сетях

Пусть Z- множество объектов. Каждый объект sZ представляется сетью, называемой семантическим графом (СГ), который включает вершины двух типов: объектные и предикатные. Объектной вершине приписывается имя объекта, имя базового класса объекта и вектор его признаков; предикатной вершине—имя отношения, выполняющегося между объектами. СГ, предназначенный для представления объекта sZ, распадается на иерархически упорядоченное множество двухуровневых р-подграфов, служащих для представления объекта s, его «частей» (р-потомков), частей его частей и т. д.; p-подграф содержит на первом уровне объектную вершинуv_s, связанную отношением р (целое—часть) с объектными вершинами второго уровня, которые связаны между собой отношениями через предикатные вершины.

Обобщенный семантический граф (ОСГ) также представляется в виде набора обобщенных р-подграфов (ор-подграфов). Каждый ор-подпраф g предназначен для представления множестваM=m(g)объектов.

Для решения задачи обобщения рассматривают наложимость op-подграфаgна некоторый частичный подграфg. Обобщенное представление искомого классаКищется по обучающей выборке <v+,v->в виде покрывающей совокупности ОСГg_i, iI_k, таких, что