Диссертация (1137259), страница 8
Текст из файла (страница 8)
Тогда()◇ = { ∈ | () ⊑ ()} = ∪ , где некоторое, возможнопустое, подмножество . Тогда ()◇◇ = ( ∪ )◇ = ◇ ⊓ ◇ ⊑ ◇ =, то есть ()◇◇ ⊑ .Утверждение 6. Пусть , ∈ , () → () и () = , тогда → .Доказательство. По свойствам проекции () ⊑ , тогда ()◇ ⊇◇ , следовательно, → (). Если () → () и () = , тогда → согласно транзитивности импликации.12.4Узорные структуры для процессовМногие процессы могут быть рассмотрены как последовательности, в которых одно состояние сменяется другим.
Если описание самого состояние содержит различные компоненты, то такие явленияотносятся к процессам с состояниями сложной структуры. В качестве примера рассмотрим истории госпитализаций пациентов, которые является важной задачей, позволяющей оптимизировать процесслечения больных [34].1Доказательство полностью повторяет [40].44Пациент123История госпитализаций⟨[1 , {}]; [1 , {, }]; [1 , {, }]; [1 , {}]⟩⟨[2 , {, }]; [3 , {, }]; [3 , {, }]⟩⟨[4 , {, }]; [4 , {}]; [4 , {}]; [4 , {, }]⟩Таблица 2.3: Выборка историй госпитализаций пациентов2.4.1Рабочий примерВ качестве примера рассмотрим Таблицу 2.3, в которой множество последовательностей описывает реализации процесса госпитализации пациентов. Каждый пациент посещает больницы поразличным причинам в разном порядке.
В данной выборке каждаягоспитализация представлена именем больницы, в которую пациент был помещён, и множеством медицинских процедур, которыеон прошёл во время госпитализации. В этой выборке – три пациента, первый из которых имел 4 госпитализации в одной и той жебольнице 1 с разными наборами процедур в течение госпитализаций. Для данной выборки существует 4 медицинских процедуры = {1 , 2 , 3 , 4 }, а на именах больниц определена иерархия, определяющая принадлежность больницы к определенному типу, = {1 , 2 , 3 , 4 , , , *}, где, 1 и 2 являются государственными больницами (), а 3 и 4 – частными клиниками().
Общий тип для двух больниц ℎ1 , ℎ2 ∈ обозначается какℎ1 ⊓ ℎ2 , например 1 ⊓ 2 = . Упорядоченное множество характеристических подпоследовательностей госпитализаций являетсяиерархической моделью процесса госпитализации. Такие подпоследовательности могут быть найдены посредством выделение наиболее важных понятий в решётке узорных понятий на последовательностях.
В дальнейшем будут подробно рассмотрены узорные структуры на последовательностях, здесь же мы только отметим, что решётка узорных понятий, соответствующая нашему примеру, показана на Рисунке 2.5.452.4.2Частичный порядок на последовательностях и соответствующая полурешёткаРеализация процесса моделируется последовательностью. Последовательность состоит из элементов, которые принадлежат некоторому множеству, называемому алфавитом. В простейшем случае взадаче нахождения подпоследовательностей на алфавит не накладывается каких-либо специальных свойств.
В дальнейшем понятиеподпоследовательности было обобщено на случай алфавита, в котором элементы являются подмножеством некоторого базового множества [24], а также на случай алфавита с многокомпонентными и многоуровневыми элементами [99]. Здесь предлагается обобщение наслучай алфавита, являющегося произвольной полурешёткой2 . Данный подход допускает произвольные последовательности, не имеющие связей между элементами одной последовательности, кромепоследовательной связи, включая данные представленные в подразделе 2.4.1. В частности, если на элементах введён некоторый частичный порядок, он может быть несложно преобразован в соответствующую полурешётку.
При моделировании процессов с состояниям сложной структуры, каждая реализация такого процесса являетсяпоследовательностью со сложными элементами, для простоты называемая сложной последовательностью. При этом соответствующаяузорная структура задаёт иерархическую модель процесса.Определение 17. Пусть дана полурешётка (, ⊓), называемая алфавитом, тогда последовательностью элементов сложной структурыназывается любой упорядоченный список элементов из .
Такая последовательность обозначается как = ⟨1 , . . . , ⟩.В алфавите (, ⊓) существует нижний элемент ⊥, который может соответствовать любому другому элементу алфавита. Формально, нижний элемент – это такой элемент, что для всех ∈ выполняется ⊥ = ⊥ ⊓ . Такой элемент необходим согласно определению2Стоит отметить, что эта полурешётка отличается от полурешётки, используемой в определенииузорных структур46решётки, но не содержит никакой полезной информации. Значит, такой элемент не может входить в результат.
В работах по анализупоследовательностей ⊥ соответствует пустому множеству, котороеникогда не является элементом последовательности [9].Определение 18. Последовательность = ⟨1 , . . . , ⟩ является доdпустимой, если для любого , ̸= ⊥, где ⊥ =.∈Определение 19. Последовательность = ⟨1 ; ...; ⟩ является подпоследовательностью для последовательности = ⟨1 ; ...; ⟩, чтообозначается как ≤ , тогда и только тогда, когда ≤ и существуют 1 , .. такие, что 1 ≤ 1 < 2 < ... < ≤ , а также длялюбого ∈ {1, 2, ..., }, ⊑ .С таким определением подпоследовательностей задача поискамаксимальных подпоследовательностей может оказаться вычислительно сложной, поэтому для упрощения данной задачи только“сплошные” подпоследовательности (или подстроки) принимаютсяво внимание.
Под ними понимаются только подпоследовательностибез пропусков (формально, для всех > 1 = −1 + 1). Для упрощения все примеры данной главы приведены именно для сплошныхпоследовательностей. Тем не менее все результаты этой главы остаются верными и в общем случае.В нашем примере (Раздел 2.4.1) алфавитом последовательностейявляется = × ℘( ), на которой решёточная операция задаётсякак (ℎ1 , 1 )⊓(ℎ2 , 2 ) = (ℎ1 ⊓ℎ2 , 1 ∩2 ), где ℎ1 , ℎ2 ∈ – имена больниц, а 1 , 2 ∈ ℘( ) – множества применённых медицинских процедур. Таким образом, последовательность 1 в Таблице 2.4 являетсяподпоследовательностью первого пациента (1 в Таблице 2.3) потому что для = + 1 (Определение 19) 11 ⊑ 11 (‘CH’ является более общим описанием чем больница 1 , и при этом {, } ⊆ {, }),12 ⊑ 12 (одна и та же больница и {} ⊆ {, }), 13 ⊑ 13 (‘*’ означает любую больницу и является более общим описание, чем больница1 , {} ⊆ {}).47)︁}︁(︁{︁1 , 2 , 3 ; 4 , 5)︁}︁(︁{︁1 , 2 ; 2 , 3)︁}︁(︁{︁1 , 3 ; 11 , 12)︁}︁(︁{︁2 , 3 ; 6 , 7 , 8)︁(︁{︁ }︁1 ; 1)︁(︁{︁ }︁2 ; 2)︁(︁{︁ }︁3 ; 3(∅; *)Рисунок 2.5: Решётка узорных понятий для узорной структуры напоследовательностях заданной Таблицей 2.3.
Содержания понятийссылаются на последовательности из Таблиц 2.3 и 2.4.123456789101112Последовательности⟨[, {, }]; [1 , {}]; [*, {}]⟩⟨[, {, }]; [*, {}]; [*, {}]⟩⟨[, {}]; [*, {}]; [*, {}]⟩⟨[*, {, }]; [*, {}]⟩⟨[*, {}]⟩⟨[*, {, }]; [, {}]; [, {}]⟩⟨[, {}]; [, {}]⟩⟨[, {}]; [, {, }]⟩⟨[, {, }]⟩⟨[, {}]; [, {}]⟩⟨[*, {, }]; [*, {}]⟩⟨[*, {}]; [*, {}]⟩Таблица 2.4: Некоторые подпоследовательности историй госпитализаций из Таблицы 2.3.Как было отмечено в предыдущем разделе, для произвольного частичного порядка может быть задана соответствующая полурешётка.В этом разделе был задан частичный порядок на последовательностях со сложными элементами, а значит и соответствующая полурешётка.
На Рисунке 2.5 показана решётка узорных понятий, соответствующая узорной структуре на последовательностях, заданныхв Таблице 2.4. В дальнейшем для обозначения узорных структур напоследовательностях будет использоваться аббревиатура УСП.482.4.3Проекции узорных структур на последовательностяхРешётка узорных понятий может быть трудновычислимой и, более того, среди всех понятий такой решётки только малая часть является полезной для анализа исследуемой выборки. Проекции позволяют уменьшить размер решётки, и при правильно заданной проекциииз результирующей решётки могут быть исключены только те понятия, которые не могут являться “интересными” для решаемой задачианализа.
Ниже приводятся некоторые виды проекций, которые могутбыть полезны для анализа с помощью УСП.Во многих случаях эксперт может быть заинтересован в нахождении достаточно длинных подпоследовательностей, так например,последовательности длины 1, как правило, не представляют интереса, так как не содержат “последовательных” зависимостей. Для такого проецирования узорной структуры необходимо заменить каждыйэлемент полурешётки описаний на элемент, из которого удалены всекороткие последовательности.
Формально данная проекция задаётсяопределением 20. В дальнейшем такие проекции УСП называютсяПроекциями Минимальной Длины или ПМД-проекциями.Определение 20. Проекция минимальной длины (ПМД) ℓmin узорнойструктуры на сложных последовательностях задаётся следующейфункцией:() = { ∈ | || ≥ ℓmin и (@ ∈ )( ≥ ∧ || > ℓmin )},где ∈ – любой элемент полурешётки описания на сложных последовательностях.Второе условие в определении 20 требуется потому, что необходимо, чтобы в () для каждой последовательности ∈ (), все еёподпоследовательности входили также в ().
Поэтому, если в этомножество входит короткая последовательность, но которая меньше49}︁ )︁(︁{︁1 , 2 , 3 ; ∅)︁}︁(︁{︁1 , 2 ; 2 , 3)︁(︁{︁ }︁1 ; 1)︁(︁{︁ }︁2 ; 2}︁ )︁(︁{︁1 , 2 , 3 ; ∅)︁}︁(︁{︁2 , 3 ; 6)︁}︁(︁{︁1 , 2 ; 9)︁(︁{︁ }︁3 ; 3)︁(︁{︁ }︁1 ; 1(∅; *)a: ПМД-проекция.)︁}︁(︁{︁2 , 3 ; 7 , 8 , 10)︁(︁{︁ }︁2 ; 2)︁(︁{︁ }︁3 ; 3(∅; *)b: Проекция алфавита (удаленыописания с больницей ‘*’)Рисунок 2.6: Два вида проекций УСП, заданной Таблицей 2.3. Узорное содержание ссылается на Таблицы 2.3 и 2.4.некоторой длинной из этого множества, то её удалять из множества() нельзя.Пример 1.
Если эксперт считает, что интересны только последовательности длины 3 и более, то между пациентами 2 и 3 из Таблицы 2.3 есть только одна максимальная подпоследовательность6 = ⟨[*, {, }]; [, {}]; [, {}]⟩ из Таблицы 2.4.Пример 2. Рисунок 2.5a показывает спроецированную решёткуузорных понятий, соответствующую УСП, заданной Таблицей 2.3при ПМД-проекции при длине допустимых в узоре последовательностей от 3 и более.Докажем, что функция заданная определением 20 является функцией проекции и, таким образом, может быть использована для проецирования узорных структур на последовательностях.Утверждение 7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
