Диссертация (1137259), страница 10
Текст из файла (страница 10)
Болеетого, мера устойчивости часто применяется на практике, где показалахорошую эффективность [53].В данной главе понятие устойчивости будет введено для узорныхструктур. Тем не менее экспериментальная апробация устойчивостибудет осуществлено только для формальных контекстов, то есть длядвоичного объектно-признакового представления.
Это связано с тем,что в открытых источниках, можно найти существенно больше двоичных выборок данных, на которых можно проводить эксперименты, чем для данных, представленных последовательностями. Болеетого, как это показано в [40], для каждой узорной структуры существует эквивалентное объектно-признаковое представление, и такимобразом достаточно исследовать поведение устойчивости только наформальных контекстах.3.23.2.1Устойчивость формальных понятийОпределение устойчивостиВ данной работе используется упрощённое определение устойчивости, согласно [77; 103], которое на практике совпадает с устойчивостью по [74; 75] с точностью до пренебрежимо малой разницы.При этом рассматриваемое определение является более простым.Определение 23. Устойчивостью формального понятия Stab(),называется отношение количества подмножеств объема понятия(Ext()), описание которых совпадает с содержанием (Int()), к количеству подмножеств понятия. Здесь и далее ℘( ) означает множество всех подмножеств множества .Stab() :=|{ ∈ ℘(Ext()) | ′ = Int()}|2|Ext()|56(3.1)Пример 4.
Формальный контекст и соответствующая решётка показаны в Таблице 3.1 и на Рисунке 3.1. Для упрощения на рисунке для большинства понятий показаны только объёмы. Содержание выделенного понятия Ext() = {1 , 2 , 3 , 4 }, соответственно существует 24 подмножеств для данного объёма. Описание (результат операции (·)′ ) следующих 5 подмножеств объёма отличается от содержания рассматриваемого понятия: {1 } , . . . , {4 }и ∅. Оставшиеся подмножества этого объёма описываются темже содержанием, что и рассматриваемое понятие, таким образом4= 0.69.Stab() = 2 2−54123451 2 3 4 5 6xxxxxxxxxТаблица 3.1: Формальный контекст для демонстрации устойчивости.({1 , 2 , 3 , 4 , 5 } ; *)[0.47]( {g1 , g2 , g3 , g4 } ; {m6 })[0.69]({1 } ; *)[0.5]({2 } ; *)[0.5]({3 } ; *)[0.5]({4 } ; *)[0.5]({5 } ; *)[0.5](∅; *)[1.0]Рисунок 3.1: Решётка формальных понятий для контекста из Таблицы 3.1.
Для каждого понятия указан соотвествующая мера устойчивости.Другими словами, мера устойчивости показывает, насколько данное понятие зависит от выборки, по которой построен контекст.Чем больше мера устойчивости, тем больше уверенность в том, чтопри изменении выборки содержание рассматриваемого понятия будет присутствовать в конечной решётке. То есть более вероятно, что57содержание устойчивого понятия является характеристикой исследуемых объектов, а не случайным совпадением в выборке. Формально,данное поведение устойчивости зафиксировано в следующем утверждение, приведённом по [103].Утверждение 9.
Пусть даны формальный контекст K = (, , )и формальное понятие этого контекста, тогдаStab() =|{ ⊆ | Int() замкнуто в K }|2||(3.2)где K = (, , ), при = ∩ × .Вышеприведённые определение и утверждение приведены дляслучая классического анализа формальных понятий. Для использования устойчивости при анализе узорных структур, данные определение и утверждение могут быть использованы практически без изменений, так как они не полагаются на конкретный вид сущностей,используемых для описания объектов. Более того, при использованиепроекций узорных структур устойчивость формального понятий, задаваемого множеством объектов в объёме, не может уменьшиться.Утверждение 10.
Пусть дана узорная структура (, (, ⊓), ), иеё проекция . Пусть также дано понятие в (, ( , ⊓ ), ),тогда существует понятие в (, (, ⊓), ), чей объём совпадает с объёмом , Ext( ) = Ext() (см.утверждение 5), при этомустойчивость понятия не превышает устойчивости понятия ,Stab() ≤ Stab( ).Доказательство. Понятия и имеют одинаковый объём, тогдасогласно определению 23, для того чтобы доказать, что Stab() ≤Stab( ), необходимо доказать, что для любого подмножества ⊆ Ext(), если ◇ = Int() в исходной узорной структуре(, (, ⊓), ), тогда ˜◇ = Int( ) в спроецированной узорной структуре (, ( , ⊓ ), ). В этом доказательстве операция (·)˜◇ относитсяк спроецированной узорной структуре (, ( , ⊓ ), ). Докажем этоот противного.58Предположим, что ∃ ⊂ Ext(), такое что ◇ = Int(), нопри этом ˜◇ ̸= Int( ).
Тогда существует – наследник (Ext( ) ⊂ Ext( )) такой, что ˜◇ = Int( ), то есть ⊆ Ext( ).В таком случае, согласно утверждению 5, существует понятия в (, (, ⊓), ), такое что Ext() = Ext( ). Следовательно, ⊆Ext( ) = Ext() ⊂ Ext( ) = Ext(). Но тогда ◇ ̸= Int(). Получили противоречие, что и завершает доказательство.Таким образом, если среди понятий спроецированной узорнойструктуры, найти устойчивые по некоторому уровню , то есть такие,что Stab() ≥ .
То среди них будут все понятия исходной узорнойструктуры, устойчивые по этому же уровню и присутствующие вспроецированной узорной структуре.Стоит также отметить, что, как было показано ранее, нахождениеустойчивости для данного понятия является #P-полной задачей [74;75]. Один из лучших алгоритмов [103] для нахождения устойчивостиможет её находить только для всей решётки и имеет алгоритмическую сложность, в худшем случае квадратичную от размера решётки,(|ℒ|2 ). Напомним, что размер решётки может быть экспоненциальным от количества объектов, |ℒ| ∼ (2|| ). Данная теоретическаяоценка является более сложной для вычисления, чем теоретическаяоценка построения решётки формальных (узорных) понятий. Болеетого как показывают вычислительные эксперименты, нахождение меры устойчивости может требовать существенно большего времени,чем вычисление самой решётки [21].
Кроме того, известные алгоритмы нахождение точного значения устойчивости требуют построениядиаграммы решётки формальных понятий, и, таким образом, предъявляют высокие требования к памяти и вычислительной мощностиЭВМ. Значит, эффективная оценка этой меры является необходимойдля её применения.593.2.2Оценки устойчивостиДля понятия и его соседа снизу (Ext() ⊂ Ext()), верноследующее (∀ ⊆ Ext())(′′ ⊆ Ext() ∧ ′ ⊇ Int() ⊃ Int()),то есть ′ ̸= Int(). Следовательно, подмножество объёма любогососеда снизу не может входить в числитель формулы (3.1) при вычислении устойчивости для понятия . С другой стороны, все подмножества объёма понятия , которые не являются подмножествами какого-либо соседа снизу данного понятия, будут описыватьсяпризнаками из Int().
Соответственно, такие подмножества должнывключаться в числитель формулы 3.1. Следовательно, если исключить из числителя все подмножества объёмов всех соседей снизупонятия , мы получим оценку снизу, так как некоторые подмножества могут быть исключены дважды. С другой стороны, исключение подмножеств только одного соседа снизу, исключает лишниеподмножества Ext() единожды, но часть лишних подмножеств небудет исключена. Таким образом, мы получаем утверждение 11 дляоценки устойчивости формального понятия.Утверждение 11.
Устойчивость формального понятия лежит в следующих границах:1−∑︁∈DD()12Δ(,)≤ Stab() ≤ 1 − max1∈DD() 2Δ(,),(3.3)где DD() – это множество всех соседей снизу данного понятия врешётке, а Δ(, ) := |Ext() ∖ Ext()| – разница в количествеобъектов между объёмами понятий и .Нахождение данной оценки может быть реализовано с помощьюалгоритма 1. Теоретическая сложность данного подхода совпадает сосложностью нахождения всех соседей снизу для данного понятия, тоесть (|| · | |2 ), для простого формального контекста (, , ).Данная оценка может быть применена для одного понятия и не требует нахождения всего множества понятий, что особенно важно для60больших решёток, в которых нахождение всех понятий не представляется возможным. Назовём этот подход методом оценивания.Пример 5.
Согласно формуле (3.3) для нахождения всех понятий сустойчивостью не меньше 0.97 следует выбрать только понятия, для которых Δmin () = min Δ(, ) превышает 5 (Δmin () ≥∈DD()− log(1 − 0.97) = 5.06).Function FindStabilityBoundsData: Формальный контекст K = (, , ), понятие .Result: < , ℎ > – пара оценок снизу и сверху дляустойчивости понятия . ← 1;ℎ ← 1;ℎ ← FindChildren(K, ) ; /* (| | · | |2 */ ← ∞;foreach ℎ ∈ ℎ do/* не больше (| |)итераций */ ← |Ext() ∖ Ext(ch)|; ← min( , ); ← − 2− ;ℎ ← 1 − 2− ;return < , ℎ >;Algorithm 1: Алгоритм, вычисляющий устойчивость формального понятия согласно (3.3) .Известно, что для данного контекста, количество наследников уформального понятия не может превышать количество признаковв контексте (, , ). Каждое слагаемое нижней оценки в формуле (3.3) не превышает 2−Δmin () .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
