Алгоритм SRT (Structural Regression Tree) [12] был создан как попытка соединить подходы статистического построения регрессионных деревьев и индуктивного логического программирования (ИЛП), и тем самым научиться решать задачу «реляционной регрессии» - построение теории для прогнозирования численных величин на основе реляционных данных и, возможно, существующих знаний в данной предметной области. Метод TIPT (Tree Induction for Predictive Toxicology) [22] является приложением известного алгоритма построения деревьев решений C4.5 [23] к предложенной задаче. ИЛП алгоритм PROGOL [17] реализует принцип обратного следования (inverse entailment) для генерализации множества положительных примеров относительно теории. Обучающие примеры задаются в виде дефинитных дизъюнктов.

Прогноз LRD выполнен с помощью алгоритма Distill [24], который представляет собой объединение метода DiVS (Disjunctive Version Space) со стохастическим согласованием. Прогноз OUCL-2 сделан с помощью дерева, построенного системой C4.5. Каждое вещество было описано значениями 417 атрибутов, причём некоторые наборы атрибутов основаны на правилах, построенных ИЛП-системами PROGOL и WARMR (W. Association Rules over Multiple Relations) [25]. Прогноз OAI построен на независимом прогнозе двумя методами - C4.5rules и неким простым байесовским классификатором - и последующем голосовании. Прогноз LEU3 сделан при помощи алгоритма ICL (Inductive Constraint Logic) [26] с использованием теории для мутагенеза, построенной ранее системой PROGOL. Прогноз LEU2 выполнен системой MACCENT (MAximum ENTropy modeling with Clausal Constraints) [27] с использованием ассоциативных правил, найденных методом WARMR.

В целом, анализ построенных моделей показывает, что они скорее выделяют наиболее значимые сопутствующие признаки (в виде результатов краткосрочных тестов, как, например, результат теста на мутагенез бактерий Salmonella, которому придаётся большой вес практически в каждой модели), чем выявляют структурные причины канцерогенеза. Принимая это во внимание, организаторы конкурса PTC 2000-2001 предложили использовать в качестве обучающих только данные, касающиеся химической структуры веществ непосредственно.

Модель VINITI [28] была получена ДСМ-системой исследования задач «структура-активность» с использованием представления химических соединений в виде ФКСП (фрагментарный код суперпозиции подструктур) [30]. ДСМ-метод автоматического порождения гипотез (АПГ) [29] является логико-комбинаторным методом, основанным на формализации важного класса правдоподобных рассуждений [19] и реализующим синтез познавательных процедур - индукции, аналогии и абдукции. Модели LEU* получены с помощью алгоритма Tilde [31] построения логических деревьев решений, основанного на алгоритме C4.5. Модель WAI1 [32] представляет собой набор семи независимых линейных классификаторов, каждый из которых использует свой набор атрибутов - один из семи, предоставленных различными группами исследователей, принимавшими участие в конкурсе. Соединение считалось канцерогенным, если хотя бы один из классификаторов голосовал за это. Модель GONS для прогноза MR была построена с помощью системы обучения понятиям SubdueCL [33], основанной на системе обнаружения подструктур в структурных данных Subdue. Обе системы используют представление реляционных данных в виде графа для нахождения повторяющихся образцов (в виде подграфов).

Раздел 1.3.2 посвящён задачам ИАД в медицине. Эта область стала одним из главных полигонов испытания и применения методов ИАД с самых ранних этапов их развития. Можно выделить два класса методов ИАД, отвечающих главным аспектам применения таких методов в медицине [34]:

1. Методы абстракции данных (data abstraction), призванные поддерживать принятие решений посредством извлечения полезных абстракций (обобщений) из «сырых», по большей части числовых, данных.

2. Методы собственно анализа данных (data mining), предназначенные для извлечения знаний, сокрытых в массивах данных, в понятной «символической» форме.

Основными особенностями применения ИАД в медицине являются следующие:

· «Добытые» закономерности должны быть выражены в терминах, понятных медицинскому эксперту, и подкреплены конкретными примерами - только при этих условиях они могут быть взяты на вооружение и использоваться в повседневной практике.

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

· Наличие неполных и зашумлённых данных, снижающих надёжность прогноза.

· Для принятия ответственных решений требуется очень детальное описание объектов анализа (состояния пациента и наблюдаемых симптомов), гораздо более детальное, чем обычно предоставляют деревья решений - традиционный инструмент диагностики - после «прореживания» с целью получения дерева большей общности и меньшего размера.

· Для увеличения шансов получения значимых результатов, такие методы должны уметь взаимодействовать с экспертом, который может «поделиться» существующими знаниями, предоставить необходимые данные и оценить результаты работы [34] (т.е. быть человеко-машинными [29]).

Раздел 1.3.3 подводит итоги сделанного обзора. Отмечаются следующие тенденции в развитии методов анализа данных:

· Всё более активное использование представления данных в виде отношений - «естественного» представления для реляционных БД - для работы в рамках систем извлечения знаний из баз данных.

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

· Наряду с разработкой чисто «реляционных» алгоритмов, делаются попытки адаптации существующих наработок в области «пропозиционального» анализа к анализу реляционных данных.

· Возрастает интерес к системам, строящим избыточные модели, которые позволяют эффективно работать в условиях неполных и зашумлённых данных.

Проведённый анализ предъявляемых требований и используемых методов ИАД позволяет описать системы типа ДСМ в терминах их отличительных особенностей.

· ДСМ-системы являются интеллектуальными в сильном смысле.

· Системы типа ДСМ выходят за рамки систем анализа данных; реализуя предварительное преобразование данных, они являются системами извлечения знаний.

· Кроме того, ДСМ-системы обладают способностью подсказывать исследователю вид объектов, которыми необходимо пополнить исходную базу фактов - способность уникальная, не упоминаемая в литературе.

· Логическая корректность ДСМ-гипотез выступает как альтернатива статистической доверительности, и, в отличие от последней, требовательна не к объему имеющихся данных, а именно к составу.

· Наличие 4^х типов истинностных оценок гипотез позволяет отказаться от правила «исключённого третьего» и увеличить точность и надёжность результатов за счёт распознавания ситуаций противоречивости или недостаточности имеющихся знаний или данных.

· Модели данных, создаваемые ДСМ-методом, избыточны в том смысле, что один объект-пример может попадать под действие нескольких результирующих гипотез (во многих системах это невозможно из-за требования минимальности описания). Эта избыточность позволяет выполнить последующий прогноз с большей полнотой и надёжностью.

· ДСМ-системы предоставляют чёткое обоснование сделанного прогноза в терминах подобъектов-«структурных причин», что роднит их с системами обучения, основанными на анализе ситуаций - case-based learning [35].

Проделанный анализ позволяет также наметить некоторые пути развития систем типа ДСМ как средства интеллектуального анализа данных и извлечения знаний из баз данных:

· Соединение логико-комбинаторного ДСМ-метода и численных статистических методов позволило бы учитывать как структурные, так числовые характеристики исследуемых объектов.

· ДСМ-метод, не использующий статистических критериев, может быть «введён в заблуждение» шумовыми данными (единичными «выбросами» неправильных данных) и в случае его применения для анализа данных в промышленных масштабах эта проблема должна быть адресована.

· Необходима интеграция с системами управления базами данных для хранения данных и знаний, а также реализация алгоритмов, способная работать с данными, находящимися не в оперативной памяти компьютера, а во внешней базе данных.

· Другой аспект систем извлечения знаний из баз данных - распараллеливание алгоритмов - также должен быть изучен (в применении к алгоритмам ДСМ-метода, например, алгоритму нахождения глобальных сходств).

В главе II предлагается подход к проблеме интеллектуального анализа гибридных (структурно-числовых) данных на примере ДСМ-системы прогнозирования контрпродуктивных свойств химических соединений. В разделе 2.1 приводится краткое описание логико-комбинаторного ядра системы - ДСМ-метода автоматического порождения гипотез, и используемых им аппарата квазиаксиоматических теорий (КАТ) [38] и бесконечнозначной логики [37]. Раздел 2.2 описывает специализированную ДСМ-систему прогнозирования контрпродуктивных свойств химических соединений, реализованную в отделении интеллектуальных систем ВИНИТИ и ставшую лауреатом международного конкурса Predictive Toxicology Challenge 2000 в трёх из четырёх категорий. В этой системе для представления химических соединений применялся язык ФКСП (фрагментарный код суперпозиции подструктур) [30], специально разработанный для задачи «структура-активность».

Однако большинство моделей в данной задаче являются числовыми. В качестве примера, Раздел 2.3 приводит числовую модель канцерогенности полиароматических углеводородов (ПАУ), разработанную в НИИ экологии человека и гигиены окружающей среды им. А. Н. Сысина. В этой модели полагается, что контрпродуктивная - канцерогенная или мутагенная - активность ПАУ будет тем выше, чем ниже энергия образования соответствующего ему метаболита, т.е. вещества, получающегося в результате превращений, которые претерпевает исходное вещество в организме. В процессе эксплуатации этой модели были обнаружены соединения, выпадающие из общего ряда. Оказалось, что такие соединения имеют специфическую структуру, и качество результатов значительно повышается, если произвести предварительный отбор соединений по структуре, а уж затем применять регрессионный анализ. Таким образом, возникает задача анализа гибридных - структурно-числовых - данных. Первым шагом в этом направлении становится разработка квантовомеханического модуля, реализующего вышеупомянутую модель. Он использует метод Хюккеля [39] для извлечения из структуры ПАУ числовых характеристик, составляющих числовую компоненту описания объекта.

Раздел 2.4 посвящен следующей проблеме - адаптация ДСМ-метода к анализу многокомпонентных объектов. Описываемый здесь подход является первым приближением (в рамках ДСМ-метода) к проблеме анализа гибридных данных и состоит в попытке использования в анализе так называемых мульти-ДСМ-объектов, т.е. ДСМ-объектов, представляющих собой упорядоченный набор компонентов, каждый из которых в свою очередь представляет собой ДСМ-объект. Операции вложения и нахождения сходства для мульти-ДСМ-объекта определяются естественным образом через соответствующие операции для каждого из компонентов.

Раздел 2.5 посвящен проблеме формализации числовой величины как ДСМ-объекта. Здесь в качестве решения было выбрано введение алгебры интервалов [40].

В разделе 2.6 описываются эксперименты, проведенные с модернизированной ДСМ-системой прогнозирования контрпродуктивных свойств соединений. Первым отличительным результатом применения этой системы явилось то, что полученная система гипотез объясняла все обучающие примеры из тестового массива (т.е. выполнялся критерий достаточности оснований принятия этих гипотез), чего не удавалось достичь, рассматривая только структуру соединений. Кроме того, учёт числовой характеристики соединений сделал прогноз 3-х соединений более полным по числу доопределённых свойств и, таким образом, более точным по описанию свойств соединения в целом. В другой серии экспериментов была сделана попытка доопределить свойства 14-ти ещё не изученных соединений. Для 9-ти из них были получены прогнозы, причём они совпали с прогнозами, сделанными с помощью группы правил, предложенной экспертами в [41].

Раздел 2.7 подводит итоги данного этапа исследований. Наряду с преимуществами выявляется ряд недостатков данного подхода. Среди них отмечается значительное увеличение числа порождаемых гипотез, связанное с тем, что фактически сходство двух числовых ДСМ-объектов не бывает пусто. Указывается также, что система, в которой можно переопределить лишь операцию нахождения сходства (т.е. сходство 2-х объектов), не позволяет использовать статистические методы в полной мере и, таким образом, не вполне отвечает поставленной задаче совместного использования логико-комбинаторных и статистических методов в анализе данных. Дальнейшее развитие системы видится в изменении ее архитектуры в соответствии с новыми требованиями.

Глава III посвящена разработке новой архитектуры ДСМ-систем, предназначенных для анализа гибридных данных, а также реализации на основе этой архитектуры новой версии ДСМ-системы прогнозирования контрпродуктивных свойств химических соединений.

Попытка расширения существующей программной реализации ДСМ-метода [4] - интеллектуальной системы типа ДСМ (ИнтС-ДСМ) прогнозирования контрпродуктивных свойств химических соединений - выявила некоторые архитектурные недостатки данной реализации, которые стали препятствием для развития системы. Главными из них являются следующие:

· Структуры объектов и их сходств считаются одинаковыми. Однако это не так в случае статистического анализа, где объектами являются числовые векторы, а в качестве их сходства могут выступать всевозможные статистические модели - от кластеров до регрессии и факторов.

· Отсутствие возможности переопределения процедуры нахождения локального сходства нескольких объектов. Сейчас, при настройке ДСМ-системы на конкретную предметную область, происходит переопределение операции (попарного) сходства, т.е. предоставляется доступ к информации о не более чем двух объектах одновременно. В случае же применения статистических методов, для нахождения существенного сходства часто требуется иметь одновременный доступ к информации обо всех объектах-"родителях" сходства.

· Необходимость хранить в оперативной памяти компьютера все порождаемые гипотезы. Используемый алгоритм построения решётки понятий следует подходу "добавляй по одному" [36], в котором новые гипотезы порождаются пересечением всех существующих гипотез с новым объектом. При таком построении на каждом шаге необходимо иметь доступ ко всем порождённым гипотезам и нет возможности отложить "законченные" гипотезы в сторону (на диск) и освободить занимаемую ими память для новых гипотез. Как упоминалось, значительное увеличение числа порождаемых гипотез является одной из проблем интегрированной ДСМ-системы (в её текущей реализации), и необходимость экономить оперативную памяти становится актуальной.

· Программа останавливает свою работу после первого шага применения правил правдоподобного вывода (п.п.в.). В [42] были сформулированы необходимые и достаточные условия появления новых гипотез при добавлении к множеству исходных объектов данного класса нового объекта, приписанного к этому классу. (Этот объект может быть добавлен в систему экспертом или являться результатом классификации на предыдущем шаге). Тем самым была показана целесообразность перехода к последующим шагам применения п.п.в., и дело лишь за его реализацией.

· Программа не поддерживает дополнительные эмпирические зависимости (ЭЗ) и их комбинации (стратегии) как подключаемые модули, хотя это является важным элементом настройки ДСМ-системы. Ядро системы монолитно, что не позволяет использовать отдельные его элементы для реализации вариаций ДСМ-метода.

Предлагаемая архитектура призвана устранить эти недостатки и максимально облегчить модернизацию построенных на её основе ДСМ-систем. Это должно способствовать быстрому воплощению в программных системах достижений ДСМ-науки и тем самым способствовать её развитию, а также заложить основу для создания ДСМ-систем промышленного масштаба.

Раздел 3.1 посвящен вопросу обобщения понятия сходства для случая, когда структуры изучаемого объекта и искомых гипотез не совпадают. В этом случае предлагается использовать набор функций сходства ч={ч_ss, ч_sc, ч_cc}, областью значений которых является C (множество сходств), а областями определения - SЧS, SЧC и CЧC соответственно (где S - множество объектов). При этом функция ч_cc обладает свойствами операции сходства на множестве объектов C, а функции ч_ss и ч_sc - свойствами (квази)коммутативности и (квази)ассоциативности:

(1) ч_ss(s_i, s_j) = ч_ss(s_j, s_i), ч_sc(s_i, с_j) = ч_sc(с_j, s_i),

(2) ч_sc(s_i, ч_ss (s_j, s_k)) = ч_sc(ч_ss (s_i, s_j), s_k).

Проверка на сходства на пустоту («неинформативность») осуществляется не сравнением с эталонным «пустым» сходством, а более абстрактным образом - посредством специального предиката E(c). При этом должны выполняться следующие условия:

(3) ,

(4) ,

т.е. сходство с пустым сходством всегда пусто.

Отношение вложимости на множестве объектов обобщается до соответствия вложимости сходства в объект I(c, s) такого, что выполняются следующие условия:

(5) ,

т.е. сходство всегда вложимо в породившие его объекты;

(6) ,

т.е. пустое сходство вложимо в любой объект.

Раздел 3.2 подробно описывает архитектуру системы, её компоненты и взаимодействие между ними. Все компоненты архитектуры разделяются на структуры данных и алгоритмы. Это отражает то обстоятельство, что ядро системы (т.е. основные алгоритмы) не зависит от деталей данной конкретной предметной области (т.е. основных структур данных). При этом настройка на предметную область происходит с помощью вспомогательных алгоритмов, специфичных для предметной области.

На уровне языка программирования (C++), в качестве механизма настройки и расширения программной системы используется механизм шаблонов (templates), а не более часто употребляемый для этих целей механизм наследования классов (subclassing). Механизм шаблонов является более общим по сравнению с механизмом подклассов: достаточно объединить все методы, требуемые контрактом для некоторого шаблона, в один (абстрактный) класс, и создать экземпляр шаблона с использованием этого класса - и мы получаем класс, обладающий функциональностью исходного шаблона и поддерживающего механизм подклассов.

В целом, для настройки «быстроменяющихся» частей системы (т.е. тех, что могут меняться от запуска к запуску, например, набор искомых эмпирических зависимостей), следует использовать механизм наследования - в противном случае незначительное изменение параметров эксперимента потребует новой версии системы. Настройку же на конкретную предметную область (т.е. подключение структур данных для изучаемых объектов, искомых гипотез, а также вспомогательных алгоритмов) имеет смысл производить с помощью механизма шаблонов - для устранения недостатков механизма наследования, преимущества которого в данном случае всё равно не пользуются.

В разделе 3.2.1 обсуждаются структуры данных. Фундаментальными являются объект и сходство. Система позволяет, во-первых, использовать многокомпонентные описания объектов и сходств и, во-вторых, иметь независимые описания для объектов и для сходств. Всё это возможно, конечно, при условии, что операции нахождения сходства, предикат вхождения сходства в объект и критерий «пустоты» сходства (реализованные во вспомогательных алгоритмах) определены корректно.

К вспомогательным структурам данных относятся структуры представления множеств свойств и множеств идентификаторов объектов. Эти структуры независимы от предметной области и система предоставляет «стандартные решения» для них, но они могут быть легко заменены любым альтернативным решением. Такая необходимость может возникнуть при настройке системы на конкретную задачу в данной предметной области.

Наконец, при разработке библиотеки делались минимальные предположения о контейнерах данных, т.е. о способах хранения данных и доступа к ним. В экспериментальной системе используются контейнеры STL, которые хранят все данные в оперативной памяти. Однако, интерфейс (контракт) между ядром системы и контейнерами, а главное, разработанный алгоритм «поуровневого» построения решетки понятий, который исключает необходимость оперативного доступа одновременно ко всем порождённым гипотезам, позволяют применять контейнеры, использующие оперативную память лишь для кэширования, и хранящие основную массу данных на диске или в базе данных. К разряду контейнеров относится структура, используемая для хранения элементов отношений и , порождаемых в процессе работы системы. Её особенностью является «поуровневое» разбиение, при которой все элементы уровня k (т.е. порождённые с участием ровно k объектов) сгруппированы в отдельный контейнер. Это упрощает организацию эффективного кэширования данных.

Раздел 3.2.2 посвящен описанию программных компонентов ядра системы.

Обобщатель (Inductor) реализует этап порождения гипотез II^го рода (о причинах наличия свойств в объектах). Процесс состоит в (параллельном) применении Генератора I^го рода для построения отношений, соответствующих решающим предикатам сходства и , с последующим вызовом Управителя I^го рода, который порождает гипотезы, применяя п.п.в. I^го рода к элементам полученных отношений.

Генератор I^го рода (Generator I) строит отношение для решающего предиката сходства (для указанных шага n применения п.п.в., знака у и Усилителя x).

Фильтр (Rejecter) выполняет проверку наличия определённой ЭЗ для пары (сходство, свойства). В настоящее время реализованы фильтры (a) простого метода сходства и (4) «запрета на контрпримеры».

Усилитель (Enhancer) представляет собой набор Фильтров, соответствующих искомым эмпирическим зависимостям (ЭЗ). Расширение тривиального набора (включающего лишь ЭЗ простого метода сходства (a)) фактически приводит к усилению п.п.в. I^го рода, отсюда и название.

Управитель I-го рода (Ruler I) доопределяет отношение посредством применения п.п.в. I^го рода к элементам отношений и . Используемый в экспериментальной системе Управитель соответствует методу «ДСМ-АПГ без отношения порядка», но так как, во-первых, Генератор и Управитель разделены, и, во-вторых, Генератор уже поддерживает механизм усилителей, то для создания системы типа «ДСМ-АПГ с отношением порядка» достаточно модернизировать лишь логику Управителя.

Уточнитель (Analoger) реализует этап порождения гипотез I^го рода (о наличии свойств в объектах).

Контролёр (Abductor) реализует этап проверки выполнимости критерия достаточного основания принятия гипотез (к.д.о.п.г.) в полученной БЗ. Процесс состоит в попытке «доопределить» все фактические свойства объектов с помощью результирующего отношения .

Рассуждатель (Reasoner) объединяет все вышеописанные процедуры в итерационную процедуру ДСМ-рассуждения: Обобщатель и Уточнитель поочередно доопределяют соответствующие отношения, пока это возможно, а затем Контролер проводит проверку качества результатов работы.

Раздел 3.2.3 посвящен описанию программных компонентов настройки системы.

Помощник предметной области (DomainHelper) предоставляет следующие процедуры:

· Нахождение локального сходства объектов (collate). Для этого процедуре передаётся два итератора - один по объектам-родителям, а другой - по «соседям снизу» искомого сходства (в смысле частично упорядоченного множества, образовываемого множествами объектов-родителей). Итератор по объектам-родителям универсален (например, итератор по «соседям снизу» пуст для уровня 2) и предоставляет непосредственный доступ к данным об объектах. С помощью же итератора по «соседям снизу» в некоторых случаях можно значительно ускорить процедуру (например, если объекты представлены множеством дескрипторов, то для нахождения сходства достаточно «пересечь» любые два «соседа снизу»). Ядро передаёт оба итератора, и тем самым даёт возможность использовать тот, который в данном конкретном случае более удобен.

· Нахождение сходства между объектом и сходством (collate_sc). Этот частный случай процедуры нахождения локального сходства объектов реализуется отдельно - из практических соображений (в силу потенциальной простоты его реализации). Кроме того, эту процедуру часто бывает удобно использовать в реализации предыдущей.

· Определение эквивалентности сходств (equal). Тривиальный в случае множеств, этот предикат может становиться довольно сложным в случае числовых моделей. Например, прямое сравнение действительных чисел чаще всего не имеет смысла - как минимум, нужно учитывать неточности, вносимые бинарным представлением чисел с плавающей точкой.

· Определение «пустоты» сходства (empty). В простых случаях «пустоту» можно определить как эквивалентность эталонному «пустому» сходству (например, пустому множеству дескрипторов), но в общем случае реализация этого предиката может включать вычисления (как, например, в случае со статистическими моделями, где мерой «неинтересности» может служить дисперсия).

· Определение вложимости сходства в объект (include). Хотя формально этот предикат можно было бы (неявно) реализовать через предикат эквивалентности сходств и операцию нахождения сходства между сходством и объектом, он реализуется явно - с тем, чтобы была возможность оптимизации.

Помощник для работы с множествами свойств (PropertiesHelper) уже реализован как часть библиотеки, но должен пересматриваться тогда, когда меняется внутреннее представление для множеств свойств. Существующая реализация - для представления в виде 32-битных полей, где каждому биту соответствует свойство и наличие/отсутствие бита означает наличие/отсутствие свойства. Это позволяет выполнять теоретико-множественные операции со скоростью побитовых операций, но накладывает ограничение на число свойств - не более 32 (что должно быть более чем достаточно для большинства практических задач). Этот помощник должен предоставлять процедуры для пересечения, объединения и разности множеств, а также определения равенства множеств и пустого множества.

В случае же множества идентификаторов (порядковых номеров) объектов ограничение на их число может быть существенным. Включенная в библиотеку реализация (основанная на представлении в виде 64-битного поля) поддерживает до 64 объектов, что может быть недостаточно для решения практических задач. Альтернативное решение может содержать либо фиксированное число 64-битных полей, либо их переменное число. Первый вариант гораздо проще и производительней второго, но такая реализация лишь смягчает ограничение (n полей позволяют анализировать до 64n объектов), а не устраняет его. Помощник для работы с множествами идентификаторов объектов (ExtentHelper), помимо теоретико-множественных операций и предикатов, позволяет преобразовывать идентификатор объекта во множество, состоящее из одного этого идентификатора, а также множество - в итератор по идентификаторам.

Раздел 3.2.4 подробно описывает алгоритм работы Обобщателя. Его распараллеливаемой частью является алгоритм построения решетки сходств. Сразу поясним, что рассматриваемые множества подмножеств (некоторого множества ) чаще всего не являются решетками в строгом смысле слова. Они представляют собой частично упорядоченные множества, которые становятся решетками, если к ним добавить элементы и . Тем не менее, для краткости мы будем называть их решетками.

Элементом множества порождаемых гипотез является тройка (E, С, P), где E - множество идентификаторов объектов-родителей гипотезы, С - их локальное сходство, P - структура, описывающая множество свойств, причиной наличия (или отсутствия) которых данное сходство является. В любой момент времени это множество является решеткой как множество всех подмножеств множества рассматриваемых объектов (т.е. в части E), и это его свойство используется для порождения новых элементов. В процессе работы множество «прореживается» с тем, чтобы в конечном итоге остались только элементы, в которых локальное сходство является также глобальным, и тогда эта решётка становится также решёткой понятий, как определяется в рамках анализа формальных понятий. При этом E исполняет роль объёма формального понятия, а (С, P) - его содержания [42].

Структура P, описывающая множество свойств, представляет массив структур, приписывающих истинностные значения на каждом шаге применения п.п.в. То есть, n-ный элемент массива P есть набор множеств свойств A_<н,n> таких, что формула CA_<н,n> имеет истинностное значение , где . Это позволяет хранить данные, необходимые обоим решающим предикатам - и - без дублирования общих данных, и обрабатывать положительные и отрицательные примеры единым образом.

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

Тот же подход применялся при разработке алгоритма - делая минимум предположений относительно предметной области, перенести как можно больше вычислений на внутренние структуры данных - те, которые мы можем оптимизировать независимо от "пользовательских" структур данных, и тем самым контролировать эффективность алгоритма в смысле времени работы и требуемой памяти. Основным является предположение, что операция сходства является дорогой (в смысле времени выполнения), гораздо дороже операции пересечения множеств (тем более что множества могут быть представлены посредством битовых масок со всеми вытекающими преимуществами). Поэтому, прежде чем вычислять сходство для некоторой гипотезы, проверяется необходимое условие того, что оно не пусто, а именно, то, что все её соседи снизу не пусты. (Соседи снизу/сверху определяются посредством отношения частичного порядка на множествах E, естественным образом связанным с операциями объединения и пересечения; именно здесь используются решеточные свойства множества множеств E). Точнее, на уровне l алгоритм пытается найти l+1 элементов, которые являются соседями снизу некоторого элемента (по построению, уровень содержит только непустые элементы, т.е. фактически ищутся l+1 непустых соседей снизу); в случае успеха вычисляется сходство соответствующих l+1 объектов, и если оно не пусто, на уровень l+1 помещается новая гипотеза. При этом перебираются все возможные сочетания (числом , где n_l - число элементов на уровне l) и тем самым гарантируется, что все непустые элементы уровня l+1 будут рассмотрены. Как видно, при таком подходе достаточно иметь оперативный доступ лишь к элементам уровней l и l+1.

Эксперименты показали, что гораздо эффективнее разделять построение (+) и (-) решеток, чем пытаться формировать конечную решетку за один проход. Возможное дублирование выполнения операции сходства с лихвой окупается возможностью немедленного исключения неверных гипотез из дальнейшего рассмотрения (в случае же одного прохода гипотеза будет исключена, только если она «неверна» сразу по обоим знакам). Кроме того, разделение этих двух шагов позволяет выполнять их параллельно.

Раздел 3.2.5 подробно описывает алгоритм работы Уточнителя. В этом алгоритме также существенно используется частичная упорядоченность множества гипотез II-го рода. А именно, поиск сходств-кандидатов осуществляется поуровнево, начиная с самого верхнего уровня, и перед проверкой вложения сходства в объект проверяется, не было ли неудачных проверок для «соседей сверху» данного сходства. Отсутствие таких неудачных проверок является необходимым условием успешной проверки для текущего сходства: каждое сходство из «соседних сверху» вкладывается в текущее сходство, и если хотя бы одно из них не вложилось в данный объект, то и текущее сходство не вложимо в него. С целью выполнения этой проверки, для каждого объекта хранится список сходств (с предыдущего уровня), которые в него не вкладываются. Каждое сходство идентифицируется множеством идентификаторов объектов-родителей. В итоге, проверка состоит в поиске среди элементов этого списка сходств, являющихся «соседями сверху» данного (в смысле множества идентификаторов объектов).

Таким образом, операция определения вложимости сходства в объект (вычислительная сложность которой в общем случае может превышать сложность процедуры нахождения сходства между сходством и объектом) заменяется несколькими (до n-k на уровне k) операциями пересечения множеств идентификаторов объектов. Эта замена имеет смысл в случае, когда операция определения вложимости существенно дороже операции пересечения множеств. Это и было основополагающим предположением при разработке данного алгоритма. Оно должно быть подкреплено эффективной программной реализацией операции пересечения множеств. Множество идентификаторов объектов, являющихся родителями сходства и однозначно идентифицирующих элемент решетки сходств, называется координатами сходства.