Диссертация (1137259), страница 9

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

ПМД-проекция – это монотонная, сужающая иидемпотентная функция на полурешётке описаний.Доказательство. Идемпотентность и сжатие следуют сразу из определения. Покажем монотонность.Если ⊑ , то ⊆ , так как и – множества последовательностей. Если ∈ короткая последовательность, котораядолжна быть “удалена” проекцией , т.е. || ≥ ℓmin и (@ ∈ )( ≥50∧|| > ℓmin ).

А так как (∀ ∈ ) ∈ , то (@ ∈ )( ≥ ∧|| > ℓmin ),а значит должна быть также “удалена” из проекцией . Тогда() ⊆ ( ) и, следовательно () ⊑ ( ).Следующим важным видом проекций на сложных последовательностях является проекция, получаемая из некоторой проекции алфавита , являющегося также полурешёткой. Определения 21 и 22 задают данный вид проекции. Таким образом, чтобы спроекцироватьнекоторое множество последовательностей следует спроецироватькаждый элемент каждой последовательности, и затем для получившихся последовательностей выбрать максимальные допустимые.Определение 21. Пусть даны алфавит (, ⊓), его проекция ипоследовательность = ⟨1 , · · · , ⟩, основанная на , то есть ∈.

Тогда алфавитной проекцией последовательности называетсяпоследовательность () = ⟨ (1 ), · · · , ( )⟩.При таком способе задания проекции, элементы () могутстать равными ⊥, что в частности означает, что – недопустимаяпоследовательность и не может входить в описание ∈ . Такимобразом, алфавитная проекция должна “удалять” все недопустимыепоследовательности из .Определение 22. Пусть дана узорная структура (, (, ⊓), ) насложных последовательностях из , где множество всех последовательностей основанных на (, ⊓). Тогда алфавитной проекциейузорной структуры называется следующая функция на :() = { ∈ | – допустимая и ∃˜ ∈ : ≤ (˜)}.Пример 3.

Эксперт хочет найти, как пациент меняет больницы взависимости от процедур, которые он хочет пройти. В этом случаелюбой узор, в котором нет информации о больнице является бесполезным (тип больницы – ‘*’), тогда можно ввести проекцию алфавита, в которой любой элемент полурешётки, содержащий больницу ‘*’, должен быть спроецирован на ⊥. Все остальные элементы51остаются без изменений. Так для описанной проекции алфавита, решётка узорных понятий примет вид, показанный на Рисунке 2.6Покажем, что функция задаваемая определением 22 задаёт проекцию в смысле определения 14.Утверждение 8.

Проекция алфавита узорной структуры на сложных последовательностях является монотонной, сужающей и идемпотентной функцией на полурешётке описаний.Доказательство. Сжатие. Для любого ∈ и любого ∈ ()существует ∈ такое, что ≤ () ≤ . Тогда по утверждению 1получаем () ⊑ .Идемпотентность. ∀ ∈ , ∀ ∈ (), ∃ ∈ : ≤ (). Тогдасуществует максимальное ∈ () такое, что ≤ ≤ ().

Согласно определению 19, существуют 1 ≤ 1 , · · · , || ≤ | ()| такие, чтодля всех ∈ {1, · · · , ||} верно ⊑ () . Так как максимальныйэлемент, то = () . Значит ( ) = , т.е. () = . А значит, что для всех ∈ () существует ∈ () такое, что ∃ ≤ ().Следовательно, (∀ ∈ )(()) = ().Монотонность. Согласно утверждению 1, для любых , ∈ таких, что ⊑ верно ∀ ∈ , ∃ ∈ : ≤ . Тогда для всех ∈ существует ∈ такое, что () ≤ () согласно монотонностипроекции на алфавите . Тогда любая ∈ () принадлежит ( ) и значит () ⊑ ( ).2.4.4Алгоритмрасчётарешёточнойоперациинасплошных последовательностяхТеперь мы покажем как полурешёточные операции сходства и поглощения (⊓, ⊑) могут быть реализованы для сплошных последовательностей.

Именно эта полурешёточная операция будет в дальнейшем использоваться при проведении экспериментов, так как сплошные последовательности, позволяют выделить последовательные со52стояния важные для нашей задачи, и при этом позволяют существенно упростить вычисления.Пусть есть два множества последовательностей = {1 , ... } и = {1 , ..., }. Пересечение ⊓ можно вычислить путём поиска максимальных последовательностей из всех максимальных общихподпоследовательностей для всех пар и .Для нахождения всех общих подпоследовательностей между двумя последовательностями можно заметить что, если = ⟨1 ; ...; ⟩является подпоследовательностью = ⟨1 ; ...; ⟩ при = + (см.определение 19) и является подпоследовательностью =⟨1 ; ...; ⟩ при = + , то для любого индекса ∈ {1, 2, ..., }, ⊑ ( ⊓ ). Таким образом, для нахождения всех максимальных подпоследовательностей для двух последовательностей можновыровнять эти последовательности всеми возможными способами,и затем для каждого выравнивания необходимо выполнить операцию решёточного пересечения над выровненными элементами алфавита.

Например, если алфавитом последовательностей является(2{,,,} , ∩), то последовательности 1 and 2 могут быть выровнены следующим образом:1 = ⟨{} ; {, } ; {, }; {} ⟩2 =⟨{, };{, }; {, }⟩ =⟨ ∅ ; {} ⟩1 = ⟨{} ; {, };{, }; {} ⟩2 =⟨{, };{, };{, }⟩ =⟨{, }; {} ; {} ⟩При этом, результат пересечения для левого выравнивания не является максимальной общей подпоследовательностью, так как ономеньше правого , которое является одной из максимальных общих подпоследовательностей.Также необходимо отметить, что проекции узорных структур напоследовательностях могут быть реализованы вместе с данной операцией.

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

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

Вследующей главе мы рассмотрим способы построения значимых моделей, которые основываются на фильтрации моделей, предложенных в этой главе.54Глава 3Меры качества моделей и их применение3.1ВведениеВ предыдущей главе рассматривался подход к созданию иерархической модели процессов с состояниями сложной структуры наоснове узорных структур. Такой подход порождает решётку узорных понятий. Каждое понятие является элементарной моделью такого процесса и отражает одну из сторон его протекания. Количествотаких порождаемых элементарных моделей может быть велико. Более того, многие из них могут быть артефактами множества описаний реализаций процесса, а не самого процесса.

Также элементарныемодели могут частично дублировать друг друга. Всё это порождаетнеобходимость выбора наиболее важных моделей из всего множестваузорных понятий.Такие модели могут выбираться различными мерами качества. Ванализе формальных понятий введено несколько таких мер, которыемогут быть применены к двоичным данным [13; 63; 74; 75; 77; 103].В это работе мы опираемся на меру устойчивости модели, котораяможет быть просто обобщена для узорных структур. Действительно, эта мера качества моделей опирается только на объём понятия,то есть на множество реализаций процесса, описываемых одной элементарной моделью. Таким образом мера устойчивости не опираетсяна структуру самой модели и поэтому может быть использована дляизмерения её качества.55При сравнение с некоторыми другими мерами качества показано,что устойчивость лучше противостоит шуму в данных [63] и, какследствие, позволяет выбрать лучшие элементарные модели.

Характеристики

Список файлов диссертации