Диссертация (1137259), страница 6
Текст из файла (страница 6)
Ниже в даннойглаве мы рассмотрим, каким образом процессы образуют решётку.Такая решётка представляет собой естественную иерархическую модель сложного явления, основанную на сходстве между отдельнымиэлементами этого явления.На практике, решётки, моделирующие сложные явления, и, вчастности, процессы с состояниями сложной структуры, содержатмножество элементарных моделей. Поэтому ключевым разделомданной главы является описание проекций узорных структур. В этомразделе вводятся и исследуются обобщённые проекции, которые от30носятся к вкладу автора данной работы.
Обобщённые проекции позволяют вводить новые классы проекций, по сравнению с определением данным Гантером и Кузнецовым (2001).Через обобщённые проекции определяются проекция минимальной длины и алфавитная проекция – важные способы редуцированияиерархических моделей процессов с состояниями сложной структуры. Проекция минимальной длины позволяет исключить из моделикороткие закономерности.
Такие закономерности редко представляют интерес при моделировании, но существенно усложняют модельи время её построения. Алфавитная проекция позволяет гибко управлять той информацией, которая включается в модель для каждогосостояния процесса.Далее данная глава построена следующим образом: в разделе 2.2приводятся базовые определения теории решёток, анализа формальных понятий и узорных структур. Разделы 2.3 и 2.4 описывают вкладавтора этой главы.
В разделе 2.3 вводятся и исследуются обобщённые проекции, которые уточняют и обобщают определение введённое ранее, а в разделе 2.4 вводятся важные проекции для моделирования процессов с состояниями сложной структуры.2.22.2.1Базовые понятияЭлементы теории решётокЗдесь вводятся основные элементы теории решёток. Подробноерассмотрение этой теории может быть найдено в [28; 41; 1].Определение 1. Частичным порядком на множестве называется бинарное отношение ≤ такое, что для любых трёх элементов, , ∈ :∙ ≤ (рефлексивность)∙ ( ≤ ) ∧ ( ≥ ) → = (антисимметричность)∙ ( ≤ ) ∧ ( ≤ ) → ≤ (транзитивность)31Множество с определённым на нём частичным порядком называется частично упорядоченным множеством и обозначается (, ≤).Если для двух элементов , ∈ верно ≤ , то говорят, что меньше или равен .
Если же ≤ и ̸= , то говорят, что строгоменьше (или просто меньше) .Определение 2. Соседом снизу элемента частичноупорядоченного множества (, ≤) называется такой ∈ ,что < и не существует ∈ такого, что < < . Пишут,что ≺ . Аналогично определяется сосед сверху.Отношение ≺ на частично упорядоченном (, ≤) называется отношением покрытия. Частичный порядок удобно изображать диаграммой покрытия, которая соответствует графу ( = , ), где – это множество вершин, а – множество рёбер, при этом пара(, ) ∈ × принадлежит множеству тогда и только тогда, когда ≺ . Диаграмма покрытия рисуется таким образом, что, если ≺ , то вершина, соответствующая , рисуется ниже вершины .Определение 3.
Верхней гранью множества ⊆ (, ≤) называетсятакой элемент ∈ , что для любого ∈ верно ≤ . Точнойверхней гранью множества ⊆ называется верхняя грань ∈ множества такая, что не существует другой верхней грани ∈ множества меньшей . Аналогично определяется (точная)нижняя грань.Существует два способа задать полурешётку: как частичный порядок специального вида и как множество с, так называемой, полурешёточной операцией.Определение 4. Верхняя полурешётка – это частичный порядок(, ≤) такой, что для любых двух элементов , ∈ существуетединственная точная верхняя грань.Определение 5. Полурешёточной операцией на множестве , называется такая операция ⊓ : × , что для некоторого ∈ илюбых , , , ∈ верно:32∙ ⊓ = (идемпотентность)∙ ⊓ = ⊓ (коммутативность)∙ ( ⊓ ) ⊓ = ⊓ ( ⊓ ) (ассоциативность)∙ ⊓=Определение 6.
Полурешёткой называется множество с определённой на нём полурешёточной операцией ⊓, (, ⊓).В теории решёток доказывается, что определения 4 и 6 эквивалентны. При этом частичный порядок на полурешётке, заданнойопределением 6, задаётся как ≤ ⇔ ⊓ = . Полурешёточная операция в полурешётке, заданной определением 4, задаётся какточная верхняя грань двух элементов.Решётку можно также определить двумя эквивалентными способами через два введённых определения полурешётки.Определение 7.
Решёткой называется упорядоченное множество(, ≤), которое является верхней и нижней полурешёткой.Определение 8. Решёткой называется множество , на которомопределены две полурешёточные операции ⊓ и ⊔ такие, что∙ ⊔ ( ⊓ ) = ∙ ⊓ ( ⊔ ) = Данный раздел следует завершить определением соответствия Галуа, на котором основывается анализ формальных понятий и узорныеструктуры.Определение 9. Пусть (, ≤ ) и (, ≤ ) – частично упорядоченныемножества. Соответствием Галуа между этими множествами называется пара отображений: : ↦→ и : ↦→ такие, чтодля любых ∈ и ∈ верно:∙ 1 ≤ 2 ⇒ (1 ) ≥ (2 )33∙ 1 ≤ 2 ⇒ (1 ) ≥ (2 )∙ ≤ (() и ≤ (()2.2.2Анализ формальных понятий (АФП)АФП – это область прикладной теории решёток, методы которого используются для решения различных задач анализа и майнингаданных.
Приведём основные определения АФП согласно [41].Определение 10. Формальный контекст – это тройка (, , ), вкоторой – это множество объектов, – множество признаков, ⊆ × – бинарное отношение между и .В Таблице 2.1 дан пример формального контекста. Между множествами подмножеств объектов и признаков можно задать соответствие Галуа с помощью следующих отображений:′ = { ∈ | ∀ ∈ , (, ) ∈ },где ⊆ ′ = { ∈ | ∀ ∈ , (, ) ∈ }, где ⊆ Соответствие Галуа сопоставляет множеству объектов максимальноемножество признаков, каждый из которых находится в отношении скаждым объектом.
Аналогично для множества признаков. Например,{1 , 2 }′ = {4 }, в то время как {4 }′ = {1 , 2 , 4 }. СоответствиеГалуа лежит в основе формальных понятий и соответствующей решётки формальных понятий.Определение 11. Формальное понятие – это пара (, ), где –это подмножество объектов, ⊆ ; – признаков, ⊆ , причём ′ = , а = ′ . Множество объектов называют объёмом, а множество признаков – содержанием формального понятия (, ).Примером формального понятия для контекста в Таблице 2.1 является пара ({1 , 2 , 4 } , {4 }), которой соответствует максимальное34({1 , 3 , 2 , 4 } ; )({1 , 2 , 4 } ; {4 })({1 } ; {1 , 4 })(2 ; 4 ; {3 , 4 })({3 } ; {2 })(; {1 , 2 , 3 , 4 })Рисунок 2.1: Решётка понятий для контеста из Таблицы 2.1.подмножество объектов, обладающих признаком 4 , в то время какмы не можем расширить множество признаков, не изменив множество объектов, соответствующих ему.
Множество понятий упорядочено согласно теоретико-множественному включению объёмов илисодержаний. Например, ({1 } ; {1 , 4 }) ≤ ({1 , 2 , 4 } , {4 }), таккак {1 } ⊆ {1 , 2 , 4 }, или двойственно {4 } ⊆ {1 , 4 }. Данныйчастичный порядок является решёткой, то есть для любой пары понятий существуют верхняя и нижняя грани. Рисунок 2.1 показывает диаграмму решётки, соответствующей формальному контексту изТаблицы 2.1.12341 2 3 4xxxxxxxТаблица 2.1: Простой формальный контекст.Существует несколько алгоритмов для нахождения множестваформальных понятий, таких как ЗО (CbO) [70; 73], а также для нахождения решётки формальных понятий, таких какAddIntent [87].
Алгоритмическая сложность указанных алгоритмовсоставляет (||| ||| min(||, | |)), где || – количество объектов, | | – количество признаков, || - конечный размер решётки.Стоит отметить, что размер решётки может быть экспоненциальнымот числа объектов или признаков, точнее 2min(||,| |) . Действительно,35возьмём = и = {(1 , 2 ) ∈ × | 1 ̸= 2 }. Несложно заметить, что любое подмножество является понятием. Следовательноразмер решётки равен 2|| .2.2.3Узорные структурыАФП преобразует формальный контекст, представленный как бинарное отношение, в решётку формальных понятий, но во многихслучаях исследуемые “объекты” могут иметь более сложное описание, чем множество некоторых наперед заданных признаков.
Например, исследуя множество объектов, возможно ли их исследоватьбез выделения специальных бинарных признаков? Узорные структуры дают ответ на этот вопрос, являясь расширением АФП для работы со структурными данными [40], такими как данные, описываемые численными значениями, множествами последовательностейили графов.Определение 12. Узорная структура – это тройка (, (, ⊓), ),где – множество объектов, (, ⊓) – полная полурешётка всевозможных описаний, а : → – функция, которая сопоставляеткаждому объекту из множества его описание из .Полурешёточная операция ⊓ соответствует операции сходствамежду двумя описаниями.
Так, для описания формального контекста как узорной структуры, перепишем формальный контекст следующим образом (см. Рисунок 2.2): каждому объекту в качестве описания запишем множество признаков, с которыми данный объект связан отношением , и каждому уникальному множеству признаков дадим уникальное имя. Тогда соответствие между объектами и множествами признаков будет функцией , в то время как множество всехподмножеств множества признаков с операцией пересечения множеств является полурешёткой.Соответствие Галуа между подмножествами множества объектови множеством описаний для узорной структуры (, (, ⊓), ) запи3612341 2 3 4xxxxxxxКонтекст(, , )1234Description Name{1 , 4 }1{3 , 4 }2{2 }3{3 , 4 }2Узорная Структура(, (℘( ), ∩), ).Рисунок 2.2: Преобразование формального контекста в узорнуюструктуру.сывается следующим образом:◇ :=lгде ⊆ (),∈◇ := { ∈ | ⊑ ()}, где ∈ .Здесь, ⊑ – это отношение поглощения, однозначно задающееся черезполурешёточную операцию как: ⊑ ⇔ ⊓ = .Определение 13.
Узорное понятие узорной структуры (, (, ⊓), )– это пара (, ), в которой ⊆ – подмножество множестваобъектов, ∈ – одно из описаний из полурешётки, такие что◇ = и ◇ = ; называется узорным объёмом понятия, а – егоузорным содержанием.Как и в классическом случае, объём понятия – это максимальноемножество объектов, разделяющих одно описание, которое не можетбыть дальше уточнено.В качестве примера узорной структуры рассмотрим узорнуюструктуру на интервалах, которая была успешна применена для анализа экспрессии генов [60]. В этой задаче каждый ген описываетсястепенью своей экспрессии в определённых условиях.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
