В статье рассматривается вариант задачи конструирования решетки формальных понятий и обсуждаются особенности алгоритма ее решения. Для повышения эффективности алгоритма предлагается использовать метод экспертной классификации.

Анализ формальных понятий (англ. Formal Concept Analysis; FCA) – отрасль интеллектуального анализа данных, в которой предполагается переход к понятийным структурам проблемных областей. Методология конструирования понятий из неколичественных данных составляет предмет и главную задачу FCA. В работе рассматривается разновидность главной задачи FCA, решение которой сводится к последовательности, вообще говоря, дорогостоящих итераций. На каждой итерации обрабатывается предварительно построенное множество кандидатов в понятия, и для некоторых из них принимаются положительные или отрицательные классификационные решения; процесс завершается, когда классификационные решения приняты для всех кандидатов. В интересах сокращения числа итераций в работе предлагается использовать метод экспертной классификации, позволяющий переносить классификационные решения, принятые для одних кандидатов на подмножества других кандидатов.

Систематическому изложению FCA и экспертной классификации посвящены монографии [1-4], здесь же приводится минимально необходимый набор сведений из FCA (п. 1), а также адаптированные под конкретную задачу (п. 2) основы экспертной классификации (п. 3). Результатом совмещения двух родственных методов стали новые подходы к обработке формальных понятий (п. 4) и постановки новых задач.

FCA исходит из весьма общей модели данных, именуемой формальным контекстом. По определению, Формальный контекст есть тройка множеств (G, M, I), в которой элементы G называются объектами, элементы M называются признаками, а I есть подмножество пар из G × M. Если (g,m) ∈ I, то говорят "объект g обладает признаком m" либо, что тоже самое, "признак m встречается в описании объекта g".

Для конечных множеств G и M – а в дальнейшем изложении рассматривается именно такой случай – эквивалентным представлением контекста K = (G, M, I) является объектно-признаковая таблица Tab(K), в которой именами столбцов служат признаки из M, кодами строк – объекты из G, а на пересечении строки g и столбца m стоит [×], если (g,m) ∈ I.

Формальный контекст K = (G, M, I) порождает формальные понятия. Пара непустых подмножеств (A,B), где A ⊆ G и B ⊆ M, называется формальным понятием, если (a) каждый объект из A обладает всеми признаками из B, и (b) никакая другая пара (A ∪ A ′,B ∪ B ′) не удовлетворяет требованию (а). Кроме того, пары множеств (∅,M) и (G,∅) являются формальными понятиями по определению. Если (A,B) – формальное понятие, A называется объемом понятия, B – его содержанием. Далее используются только формальные понятия и формальные контексты, а потому указания на их формальные статусы опускаются.

Множество C(K) всех понятий контекста K образует полную решетку, с отношением частичного порядка (A₁,B₁) « (A₂,B₂) ⇔ B₁ ⊇ B₂
Решеткой также является множество содержаний S(K) = { B | (A,B) ∈ C(K) } с отношением частичного порядка ⊇. Решетки C(K) и S(K) изоморфны, однако решетка S(K) более удобна, так как охватывает все понятия контекста, но не зависит от наличия в контексте объектов-дубликатов, которым в Tab(K) соответствуют строки, отличающиеся только кодами.

Контексты без объектов-дубликатов будем называть простыми контекстами. Не ограничивая общности, можно полагать, что в простом контексте (G, M, I) каждый объект g из G однозначно описывается подмножеством признаков¹, а I = φ(G) ≡ {(g,m) | g ∈ G,  m ∈ g }. При таком подходе для задания простого контекста достаточно перечислить описания его объектов.

Независимо от особенностей того или иного контекста K = (G, M, I) для S(K) всегда можно указать некоторое объемлющее его подмножество U(K) элементов из 2^M. В простейшем случае U(K) = 2^M. S(K) ⊆ U(K) ⊆ 2^M. Ценность множества U(K) состоит в том, что его элементы являются кандидатами в содержания формальных понятий. Кандидаты, не относящиеся к S(K), образуют множество S^o(K) = U(K) \ S(K). В свою очередь, элементы S^o(K) подразделяются на запреты и все прочие.

Для контекста K = (G, M, I) собственное подмножество признаков H, H ⊂ M, будем называть запретом, если в описаниях объектов признаки из H вместе никогда не встречаются: ∀ g ∈ G  ∃ b ∈ H :  (g,b) ∉ I. Множество всех запретов контекста K обозначим P(K). Кроме того, обозначим P^o(K) множество S^o(K) \ P(K). Таким образом, для произвольного кандидата A из U(K) возможны следующие классификационные решения:

• либо A ∈ S(K),
• либо A ∈ S^o(K) и дополнительно:
  • либо A ∈ P(K),
  • либо A ∈ P^o(K).

Наличие дополнительной классификации элементов S^o(K) позволяет более тонко анализировать кандидатов в содержания.

Любой нетривиальный контекст K способен порождать некоторые производные контексты методом вычеркивания из Tab(K) отдельных строк-объектов и/или столбцов-признаков. Прямая задача построения контекстов, производных от заданного, затруднений не вызывает. Иначе обстоит дело с обратной задачей, которая (в несколько ослабленной формулировке) состоит в построении решетки S(K) неизвестного контекста K по заданным контекстам K₁ и K₂, производным от K. При всех различиях в дополнительных предположениях и целевых установках многие известные подходы [1, 5, 6] к решению задачи совмещения не претендуют на точное построение решетки S(K). Для случая простых контекстов строгое, хотя и трудоемкое решение задачи совмещения обеспечивает метод @FC [7,8]. Представим этот метод.

Назовем глобальным контекстом неизвестный простой контекст K = (G, M, φ(G)) Заданную проекцию множества G на фиксированное подмножество признаков M_T назовем локальным контекстом. Формально, локальный контекст K_T есть производный контекст вида K = (G_T, M_T, φ(G_T)),   где   G_T = { g ∩ M_T | g ∈ G }. На практике получение K_T может быть связано, например, со снаряжением дорогостоящей экспедиции к местам обитания изучаемых объектов G, причем исследовательские возможности экспедиции позволяют установить для этих объектов признаки из относительно ограниченного множества M_T.

Для глобального контекста K и пары локальных контекстов K₁ = (G₁, M₁, I₁ )   и   K₂ = (G₂, M₂, I₂ ) в случае M₁ ∪ M₂ = M метод @FC предлагает сначала построить множество кандидатов²

V = { B1 ∪ B2 | B1 ∈ S(K),   B2 ∈ S(K) },

(1)

а затем пошагово выделить из V элементы S(K). На каждом шаге построения принимается решение о запросе нового локального контекста³, и по итогам его специальной обработки для некоторых кандидатов принимаются классификационные решения. Процесс формирования S(K) заканчивается, когда классификационные решения приняты для всех кандидатов. Доказано, что S(K) ⊆ V, и метод @FC позволяет построить множество S(K) за конечное число шагов. Запрос нового локального контекста, оформленный в виде множества его признаков M_T, формируется автоматически или в диалоге с пользователем. При этом возможные варианты запросов рассчитываются заранее, и задача сводится к выбору лучшего варианта.

В части обработки локальных контекстов K_T метод @FC использует классификационные правила, которые позволяют относить элементы v множества V к классам S(K) или S^o(K). Типичные классификационные правила выглядят так:

(K1)   Если v  ∈  P(K_T),   и   v ∪ v ′  ∈  V  для нек.  v ′,   то   v ∪ v ′  ∈  P(K).
(K2)   Если v  ∈  P^o(K_T),   то   v  ∈  P^o(K).
(K3)   Если v  ∈  P^o(K_T),   и   v ∪ v ′  ∈  V  для нек.  v ′ из M \ M_T ,   то   v ∪ v ′  ∈  S^o(K).
(K4)   Если v  ∈  P^o(K_T),   { v ′ | v ∪ v ′ ∈ V } = { ∅, v ′ },   и   v  ∈  ≠ ∅,   то   v ∪ v ′  ∈  S(K).
(K5)   Если v  ∈  S(K_T),   и   { v ′ | v ∪ v ′ ∈ V } = { ∅ },   то v  ∈  S(K).

С одной стороны, классификационные правила представляют собой строго доказанные достаточные условия [8], а с другой стороны – они вполне пригодны для использования в программах. Обработка очередного локального контекста заканчивается, когда все правила классификации оказываются неприменимыми.

При высокой стоимости локальных контекстов возникает потребность в технологиях, позволяющих при их обработке классифицировать как можно больше кандидатов в содержания из V. Аналогичная потребность исследовалась в 1980-х научным коллективом под руководством О.И.Ларичева. Результатом этой работы стал метод экспертной классификации, позволяющий при незначительных дополнительных, но контролируемых предположениях существенно увеличить количество классификационных решений.

Метод экспертной классификации позволяет в диалоге с экспертом построить неизвестное множество объектов G^E некоторого целевого простого контекста (G^E, M, φ(G^E)). При этом множество признаков M, задействованных в описаниях объектов, считается (a) известным, (b) состоящим из k непересекающихся подмножеств и (c) порождающим универсум

UEk = ME1 × ... MEk

(2)

такой, что G^E ⊆ U^E_k. Собственно говоря, на эксперта возлагается обязанность последовательно относить предъявляемые ему элементы универсума либо к G^E, либо к U^E_k \ G^E.

В интересах скорейшего построения множества объектов метод экспертной классификации постулирует гипотезу, согласно которой элементы каждого множества M^E_i различаются по степени характерности для объектов G^E. Принимая эту гипотезу, эксперт способен заранее построить на элементах множества M^E_i асимметричное, антирефлексивное и транзитивное отношение характерности <_i; запись "m_i1 <_i m_i2" означает, что признак m_i1 менее характерен для объектов G^E, чем признак m_i2. Экспериментально установлено, что фраза "быть характерным для объектов G^E" понятна эксперту без разъяснений, и он вполне способен построить k штук отношений характерности – по одному для каждого множества M^E_i.

Заметим, что в оригинальном описании экспертной классификации предполагается линейность всех отношений характерности. В настоящей работе вместо линейного порядка предполагается наличие частичного порядка, что сказывается на методе хранения данных и на организации диалога с экспертом при извлечении знаний об отношениях характерности.

Совокупность построенных экспертом отношений характерности <₁, ..., <_k порождает рефлексивное, антисимметричное и транзитивное отношение доминирования ≤ на всевозможных элементах универсума U^E_k. По определению, пара подмножеств u₁ и u₂ связана отношением u₁ ≤ u₂, если для любого i = 1, ..., k выполняется одно из двух:
либо   u₁ = u₂,
либо   m_i1 <_i m_i2,   где   u₁ ∩ M^E_i = { m_i1 },   u₂ ∩ M^E_i = { m_i2 }.

Если отношение доминирования удается построить, то механизм переноса классификационных решений, полученных для некоторого объекта g из U^E_k, описывается двумя вполне разумными правилами:
(П1)   Если g ∈ G^E,   и   g ≤ u,   то   u ∈ G^E;
(П2)   Если g ∈ U^E_k \ G^E,   и   u ≤ g,   то   g ∈ U^E_k \ G^E.

Метод @FC решения задачи совмещения простых контекстов оперирует локальными контекстами K₁ = (G₁, M₁, I₁ )   и   K₂ = (G₂, M₂, I₂ ) в интересах построения решетки S(K) неизвестного глобального контекста K. Дополнительно потребуем

M1 ∩ M2 = ∅

(3)

и положим   M^E₁ = S(K₁)   и   M^E₂ = S(K₂).

Между множеством кандидатов в содержания V и формально построенным универсумом U^E₂ = M^E₁ × M^E₂ (см. формулы (1) и (2) при k = 2) существует взаимно однозначное соответствие Ψ(v) = (v ∩ M₁, v ∩ M₂).
С учетом требования (3) отображение Ψ представляет собой утверждение о возможности однозначной раскраски всех кандидатов из V двумя цветами: признаки из M₁ окрашиваются, скажем, красным цветом, а признаки M₂ – зеленым.

При таком подходе отношение доминирования ≤, построенное для целевого простого контекста ( S^E, M^E₁ × M^E₂, φ(S^E)), где S^E = Ψ(S(K)), оказывается весьма полезным для решения задачи совмещения. Сконструированное экспертом/экспертами на универсуме U^E₂ отношение ≤ естественным образом порождает отношение доминирования ≤ на множестве V, а также модификации правил П1 и П2:
v₁ ≤ v₂ ⇔ Ψ(v₁) ≤ Ψ(v₂),
(П1м)   Если v ′ ∈ S(K),   и   v ′ ≤ v,   то   v ∈ S(K);
(П2м)   Если v ∈ S^o(K),   и   v ′ ≤ v,   то   v ′ ∈ S^o(K).
Вновь полученные классификационные правила П1м и П2м расширяют области действий правил типа K1 - K5. Так, в случае исполнения правила К3 все кандидаты из
{ x | x ≤ v ∪ v ′ } зачисляются в S^o(K). Аналогично, в случае срабатывания правила К5 все кандидаты из { x | v ≤ x } зачисляются в S(K).

Замечание 1. Успех описанного подхода к усовершенствованию метода @FC за счет привлечения правил П1м и П2м находится в прямой зависимости от количества экземпляров отношений характерности <₁ и <₁, выявленных экспертом на множествах S(K₁) и S(K₂).

Замечание 2. Задача построения отношения характерности <₁, определенного на S(K₁), осложняется большим⁴ количеством элементов в S(K₁), а также сложно устроенными описаниями этих элементов. В связи с этим наиболее перспективным "лобовым" подходом к построению отношений характерности является метод балльных оценок, выставляемых элементам S(K₁).

Замечание 3. Если множество признаков M₁ допускает разбиение на M₁¹ ∪ ... ∪ M₁^m подклассы значений некоторых однозначных атрибутов, то отношение характерности <₁, определенное на S(K₁), можно сконструировать из отношения доминирования ≤₁, определенного на M₁¹ × ... × M₁^m, путем удаления из ≤₁ всех пар вида u ≤₁ u. Замечания 2 и 3 в равной степени относятся к отношению <₂, определенному на S(K₂).

Замечание 4. В ходе решения задачи совмещения контекстов помимо первоначально построенного отношения доминирования ≤, полученного при посредничестве универсума U₂^E, могут появиться и другие пригодные для использования отношения доминирования. Организация непротиворечивого сосуществования двух и более отношений доминирования составляет предмет самостоятельной задачи.

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