Автореферат (1137258), страница 3
Текст из файла (страница 3)
Для того, чтобы иметьвозможность обрабатывать такие данные за приемлемое время, необходимоввести проекции узорных структур, которые также помогают сократить количество ненужных элементарных моделей.Проекцией полурешётки описаний (, ⊓) называется функция : →, которая является оператором ядра: монотонной ( ⊑ ⇒ () ⊑ ()),сжимающей (() ⊑ ) и идемпотентной ((()) = ()).Определение 16. Проекция узорной структуры, полученная из узорной структуры (, (, ⊓), ) с помощью проекции – эта такая узорная структура( , ( , ⊓ ), ), в которой = , = () = { ∈ | = ()}, сполурешёточной операцией ∀, ∈ , ⊓ := ( ⊓ ), а = ∘ .По сравнению с классическим определением проекции узорной структуры(B.
Ganter & S.O. Kuznetsov, 2001) , определение 16 также меняет полурешётку описаний в спроецированной узорной структуре. Это позволяет проецировать не только начальное описание объектов, но и полурешёточную операцию12сходства. Что позволяет вводить более широкий класс проекций, имеющийважное прикладное значение.Здесь нам необходимо показать, что спроецированная узорная структура,является узорной структурой в смысле ранее ведённого определения, то естьчто ( , ⊓ ) является полурешёткой. Это следует из следующего утверждения.Утверждение 3. Пусть дана полурешётка (, ⊓) и проекция , тогда длявсех , ∈ выполняется ( ⊓ ) = (() ⊓ ).Следствие 2.
Пусть дана полурешётка (, ⊓) и проекция , тогда ( , ⊓ ),заданная определением 16, является полурешёткой, то есть ⊓ является коммутативной, ассоциативной и идемпотентной операцией.С новым определением спроецированной решётки выполняются все свойства проекций, введённых B. Ganter & S.O. Kuznetsov (2001).
В частности верно следующее утверждение, которое показывает связь между узорной структурой и её проекцией.Утверждение 5. Для каждого понятия в (, ( , ⊓ ), ) существует понятие в (, (, ⊓), ) с таким же объёмом. Если является содержанием в(, (, ⊓), ), тогда () является содержанием в (, ( , ⊓ ), ), при этом()◇◇ ⊑ .Введём теперь специальные проекции для узорных структур на последовательностях, имеющих важное прикладное значение при моделировании процессов с состояниями сложной структуры.Определение 20. Проекция минимальной длины (ПМД) ℓmin узорной структуры на сложных последовательностях задаётся следующей функцией:() = { ∈ | || ≥ ℓmin },где ∈ – любой элемент полурешётки описания на сложных последовательностях.13Проекция в определении 20 позволяет ограничить минимальную длинурассматриваемых последовательностей, что позволяет исключить из рассмотрения короткие, заведомо бесполезные последовательности.
Следующие определения 21 и 22 задают возможные изменения алфавита. В силу того, чтоалфавит является полурешёткой, к нему также можно применить проекцию.Такая проекция алфавита индуцирует проекцию узорной структуры на последовательностях. Алфавитная проекция позволяет упростить алфавит сложныхпоследовательностей. В частности, если в алфавите есть несколько компонент,то некоторые из них могут быть исключены из рассмотрения.Определение 21. Пусть даны алфавит (, ⊓), его проекция и последовательность = ⟨1 , · · · , ⟩, основанная на , то есть ∈ . Тогда алфавитной проекцией последовательности называется последовательность () = ⟨ (1 ), · · · , ( )⟩.Определение 22.
Пусть дана узорная структура (, (, ⊓), ) на сложныхпоследовательностях из , где множество всех последовательностей основанных на (, ⊓). Тогда алфавитной проекцией узорной структуры называется проекция, задаваемая следующей функцией от ∈ :() = { ∈ | – допустимая и ∃˜ ∈ : ≤ (˜)}.Определения 20 и 22 задают функции, являющиеся монотонными, расширяющими и идемпотентными, то есть задают проекции узорной структуры(Утверждения 7 и 8).Проекции узорных структур на последовательностях позволяют существенно уменьшить количество узорных понятий и повысить эффективностьвычислений, не теряя при этом в качестве, что позволяет моделировать процессы с состояниями сложной структуры за приемлемое время.
Однако, конечная иерархическая модель может содержать большое количество элементарных моделей, количество которых необходимо уменьшить для успешногоприменения этой модели при экспертном анализе.Третья глава посвящена мерам качества элементарных моделей. В нашемслучае каждое узорное понятие является простой моделью процесса, но количество понятий может быть большим. Поэтому необходимо выбирать наи14более важные понятия при создания модели процесса. В этой главе изучаетсямера качества по устойчивости и вводятся эффективные методы её оценки.Устойчивостью формального понятия Stab() называется отношение количества подмножеств объема понятия (Ext()), описание которых совпадаетс содержанием (Int()), к количеству подмножеств понятия.
Здесь и далее℘( ) означает множество всех подмножеств .|{ ∈ ℘(Ext()) | ◇ = Int()}|Stab() :=2|Ext()|(1)Устойчивость формального понятия показывает, насколько сильно содержание формального понятия зависит от выборки данных. Чем выше устойчивость, тем больше комбинаций объектов можно выбросить из формальногоконтекста, не меняя содержание узорного понятия. Также можно доказать, чтоустойчивость формального понятия может только увеличиться при проецировании узорной структуры.Утверждение 10. Пусть дана узорная структура (, (, ⊓), ), и её проекция .
Пусть также дано понятие в (, ( , ⊓ ), ), тогда существует понятие в (, (, ⊓), ), объём которого совпадает с объёмом ,Ext( ) = Ext() (смотри утверждение 5), при этом устойчивость понятия не превышает устойчивости понятия , Stab() ≤ Stab( ).Было показано ранее, что нахождение устойчивости для данного понятияявляется #P-полной задачей (С.О. Кузнецов, 1990). Более того, как показывают вычислительные эксперименты, нахождение индекса устойчивости можеттребовать существенно больше времени, чем вычисление самой решётки [5].Значит, эффективная оценка этого индекса является необходимой для применения индекса устойчивости.Утверждение 11.
Устойчивость формального понятия может быть оцененапо формуле:1−∑︁∈DD()12Δ(,)≤ Stab() ≤ 1 − max1∈DD() 2Δ(,)15,(2)где DD() – это множество всех прямых наследников понятия (наибольшихпонятий меньших ), а ∆(, ) := |Ext() ∖ Ext()| – разница в количествеобъектов между объёмами понятий и .Теоретическая временная сложность данного подхода совпадает со сложностью нахождения всех непосредственных наследников для данного понятия,то есть ( · 2 ). Данная оценка может быть применена для одного понятияи не требует нахождения всего множества понятий, что особенно важно длябольших решёток, в которых нахождение всех понятий не представляется возможным.
Назовём этот подход методом оценивания.Эксперименты показывают, что для больших понятий существует многопонятий с устойчивостью близкой к 1. Чтобы упростить анализ таких решёток, можно перевести устойчивость в логарифмическую шкалуLStab() = − log2 (1 − Stab())(3)Принимая во внимание (2), получаем следующее:− log2 (∑︁2−Δ(,) ) ≤ LStab() ≤ ∆min ().(4)∈DD()Здесь ∆min () = min ∆(, ).∈DD()По вышеприведённым оценкам устойчивости нельзя гарантировать наперёд заданную точность оценки, но зато она может быть эффективно вычислена.
Другая возможная оценка устойчивости приведена в работе М.А. Бабинаи С.О. Кузнецова (2012), где авторы оценивают устойчивость методом МонтеКарло. Этот метод позволяет гарантировать наперёд заданную точность, нопроцедура вычисления требует большого количество попыток для высокойточности. Эти методы могут быть объединены следующим образом, называемым комбинированным. Сначала устойчивость рассчитывается с помощьюоценочного метода, и если точность оказывается не ниже заданной, то задачаявляется решенной, иначе устойчивость оценивается методом Монте-Карлос требуемой точностью.
Как мы увидим, комбинированный метод оценкиустойчивости позволяет существенно уменьшить время вычисления оценки16201015MushPlntSflrNursθt = 5MushPlntSflrNurs5Устойчивость в базовой выборкеθt = 15010020050010005000Размер базовой и тестовой выборокРисунок 1: Порог устойчивости в базовой выборке, гарантирующий, что 99%понятий в тестовой выборке, похожих на устойчивые понятия базовой выборки, также устойчивы в тестовой для двух порогов = 1 и = 5.по сравнению с методом Монте-Карло, но в отличии от оценочного метода,комбинированный метод гарантирует требуемую точность оценки.Далее в данной главе исследуется поведение устойчивости.
В первом эксперименте доступные выборки данных разделяются случайным образом надве и исследуется, каким образом устойчивость в одной из выборок зависитот устойчивости в другой выборке. В частности, показывается, что устойчивость удобнее использовать в логарифмической шкале. В этом случае устойчивость для понятий с одинаковым содержанием, но порождённых по разнымвыборкам отличается несущественно. Мы также показываем, что понятия изразных выборок, упорядоченные по устойчивости, имеют схожий порядок, азначит, устойчивость может быть использована для ранжирования понятий.Ещё один вопрос, который решается этим экспериментом, – каким долженбыть порог устойчивости? Рисунок 1 показывает, каким должен быть порог впервой выборке, чтобы 99% устойчивых понятий в этой выборке были такжеустойчивы (по меньшему наперёд заданному порогу) во второй выборке.17Здесь стоит отметить несколько моментов.
Во-первых, для выборокнебольшого размера разброс данной зависимости от данных к данным может сильно отличаться. Но при этом, начиная примерно с 500-1000 объектовв выборке, пороги устойчивости начинают вести себя похожим образом внезависимости от данных. Так для того, чтобы содержание устойчивого понятияприсутствовало в тестовой выборке, необходимо установить порог устойчивости в 5-6. Если же мы хотим, чтобы понятие с этим содержанием былоустойчивым по порогу = 5, тогда порог устойчивости в базовой выборке должен быть равен 11.
Данные результаты предполагают, что устойчивостьимеет асимптотическое поведение, которое, возможно, может быть доказаноформально. На данный момент, насколько это известно, такого формальногоисследования не проводилось, и, таким образом, такое исследование можетстать интересным направлением будущих работ.Ещё одно направление исследования устойчивости – это сравнение полезности упорядочивания закономерностей с помощью устойчивости и с помощью других индексов полезности. Один из способов такого сравнения – этоисследование качества классификации в задаче обучения с учителем с помощью первых закономерностей, выделенных тем или иным методом. Такоесравнение может быть выполнено в рамках следующей методологии:1. Выбирается выборка данных .2. Стократно выборка разделяется на обучающую и тестовую подвыборкислучайным образом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
