Алгоритмические проблемы ДСМ-метода
ДСМ-метод используется для предсказания свойств объектов на основе информации о свойствах других объектов. Предполагается, что известна определенным образом задаваемая структура объектов, на них определена операция сходства и имеется неполная информация об их свойствах. ДСМ-метод состоит в отыскании причины свойств и предсказании того, обладают ли теми или иными свойствами объекты, относительно которых такая информация отсутствует.
В различных вариантах ДСМ-метода по-разному определяются гипотезы о причинах свойства, но в основе всех определений лежит принцип, утверждающий, что причиной свойства является общая часть обладающих свойством объектов. Если объекты задаются в виде множеств, а операция сходства интерпретируется как пересечение, то процедуры выдвижения гипотез будут основаны на поиске сходств максимального количества объектов, т. е. непустых пересечений с максимальным по мощности множеством образующих. Процесс порождения гипотез сводится, таким образом, к повторяющемуся процессу порождения пересечений на разных массивах объектов.
Проблема заключается в том, что максимальное количество таких пересечений равно (2n – 2 – m), где n – мощность универсума признаков объектов, а m – количество самих объектов, т.е. из количества всех подмножеств универсума признаков вычитается сам универсум, пустое множество и подмножества, соответствующие описаниям объектов. Другими словами, алгоритмы, порождающие пересечения будут иметь экспоненциальную сложность.
Связь ДСМ-метода с формальной теорией понятий
Основные термины формальной теории понятий:
Знак: знаком называется материальный объект, который для некоторого интерпретатора (субъекта) выступает в качестве представителя какого-то другого предмета.
Предмет: репрезентируемые знаками предметы могут иметь различную природу. Этот термин в логике употребляется предельно широко: "предметом" здесь называют все, что может стать объектом нашего рассмотрения.
Важнейшими характеристиками знаков являются смыслы и значения.
Значением знака (экстенсионалом) называется предмет, представляемый данным знаком.
Смыслом знака (интенсионалом) называют информацию о репрезентируемом предмете, которую содержит сам знак или которая связывается с этим знаком в процессе человеческого общения или познания.
В ФТП можно отождествить предмет с множеством признаков, которыми он обладает. Тогда можно установить связь между понятиями ФТП и ДСМ-метода, т.к. в последнем объекты тоже обычно характеризуются как множества признаков. Интенсионалу в таком случае будет соответствовать сходство (обычно пересечение объектов), а экстенсионалу – множество объектов, обладающих одним свойством.
Эта связь между ФТП и ДСМом позволила использовать при решении задач ДСМа быстрые алгоритмы, разработанные для ФТП.
Алгоритмы поиска минимальных пересечений
По словам Аншакова, нам объясняли только алгоритм Норриса, про него и надо рассказывать. Вчера (11.02.07) на наш ящик прислали его описание, так что повторяться не буду. Про алгоритмы Аншакова и Хазановского знать и рассказывать нас никто не обязывает, но можно упомянуть и их до кучи.
Алгоритм Аншакова
Имеется упорядоченное множество (массив) объектов X. Известно количество объектов. Нужно найти все возможные минимальные пересечения над X и их множества образующих.
Процедура поиска такова:
1) Последовательно пересекать первый объект со следующими, накапливая результат, при этом пропуская объекты, пересечение с которыми пусто, и считая объекты, участвующие в пересечении, запоминая их номера.
2) Если в образовании полученного пересечения участвовало не менее двух объектов, то считать его минимальным, а объекты исходного массива с запомненными номерами - его образующими.
3) Построить новый массив объектов вычитанием из имеющихся объектов полученного на первом шаге пересечения, считая количество непустых объектов.
4) Если непустых объектов, по крайней мере, два, повторить процедуру с шага 1, считая первым первый непустой объект.
5) Для каждого полученного минимального пересечения получить пересечения его образующих и в случае несовпадения результата с минимальным пересечением исключить последнее из множества минимальных пересечений.
Наличие пятого пункта, отсутствующего в первоисточнике, объясняется необходимостью очистить массив минимальных пересечений от чужеродных элементов, являющихся минимальными пересечениями объектов нового массива, получающегося на шаге 3, но не являющихся минимальными пересечениями объектов исходного массива. Например, для массива ({ a, b, c }, { a, b }, { a }) на шаге 1 мы получим пересечение { a }, образованное всеми тремя объектами массива. На шаге 3 получим новый массив ({ b, c }, { b }, {}), и, вернувшись к шагу 1, получим пересечение { b }, не являющееся минимальным над исходным массивом, так как, вообще, не являющееся пересечением никаких его элементов.
Утверждение: Данный алгоритм порождает все минимальные пересечения над заданным массивом объектов и только их.
Алгоритм Хазановского
Если стратегия поиска в алгоритме Аншакова основывается на последовательном пересечении элементов исходного массива, то объектом пристального внимания алгоритма Хазановского являются атомы универсума, каждый из которых проверяется на принадлежность гипотетическому минимальному пересечению, после чего исключается из дальнейшего рассмотрения. Поэтому алгоритм Хазановского в сравнении с алгоритмом Аншакова имеет дополнительный параметр, а именно универсум атомов, заданный в явном виде. (При компьютерной реализации этот параметр необязательно передавать на вход процедуре, осуществляющей данный алгоритм, заставив процедуру саму вычислить множество всех атомов, задействованных в рассматриваемых объектах, так как только они и имеют значение.)
Алгоритм состоит в следующем:
1) Объявить текущее пересечение равным универсуму, а «дополнение» к нему - пустым объектом.
2) Взять атом из универсума и проверить все объекты исходного массива на предмет нахождения в них этого атома; в случае положительного исхода проверки получить пересечение текущего пересечения и «проверенного» объекта и объявить полученное пересечение текущим, запомнив индекс объекта в массиве; иначе, присоединить атомы объекта к «дополнению» текущего пересечения.
3) Если в образовании текущего пересечения участвовало, по крайней мере, два объекта, и оно не пересекается со своим «дополнением», исключить атомы текущего пересечения из универсума и признать текущее пересечение минимальным, а объекты с запомненными индексами - его образующими; иначе, исключить из универсума рассматриваемый атом.
4) Если универсум не пуст, то перейти к шагу 1.
Утверждение. Данный алгоритм порождает все минимальные пересечения над заданным множеством объектов и только их.
Сложность алгоритмов порождения минимальных пересечений
Пусть N – мощность универсума атомов, а n – мощность множества объектов.
Алгоритм Аншакова.
На первом шаге мы производим не более n – 1 операции пересечения. Построив на шаге 3 новый массив изъятием из объектов исходного, по крайней мере, одного атома, мы возвращаемся к первому шагу и так далее до тех пор, пока все объекты, кроме, может быть, одного, не окажутся пустыми. Очевидно, что нам придется повторить всю процедуру не более N раз. Таким образом, к пятому шагу мы придем, выполнив не более N (n –1) операций пересечения (в точности эта цифра возникает, когда все элементы массива, кроме первого, одноэлементны и различны, а первый совпадает с универсумом атомов). На пятом шаге для каждого полученного якобы минимального пересечения нам нужно произвести на одну операцию пересечения меньше, чем число множеств, участвовавших в его образовании. Количество порожденных пересечений не больше N, мощность множеств их образующих не больше n. Потому сложность алгоритма Аншакова может быть оценена выражением: N (n – 1) + N (n – 1) = 2 N (n –1).
Алгоритм Хазановского.
Для каждого атома, выбранного на шаге 2, мы производим проверку всех исходных объектов на предмет нахождения в них этого атома, и затем, либо пересекаем объект с текущим пересечением, либо объединяем его с «дополнением» текущего пересечения. Таким образом, придется выполнить всего не более N × n операций пересечения и объединения.