Диссертация (1137259), страница 7
Текст из файла (страница 7)
Таким образом, задано несколько признаков одного гена, соответствующих условиям и имеющие численные значения. Такая узорная структура может выглядеть как в Таблице 2.2, где 1 , 2 , 3 соответствуют условиям, а интервалы – изменчивости экспрессии определенного гена.37123123[1, 3] [3, 5] [2, 4][5, 7] [4, 6] [2, 5][1, 9] [2, 7] [6, 6]Таблица 2.2: Узорная структура на интервалах.({1 , 2 , 3 } ; ⟨[1, 9], [2, 7], [2, 6]⟩)({1 , 2 } ; ⟨[1, 7]; [3, 6]; [2, 5]⟩)({1 } ; ⟨[1, 3]; [3, 5]; [2, 4]⟩)({2 } ; ⟨[5, 7], [4, 6], [2, 5]⟩)({3 } ; ⟨[1, 9], [2, 7], [6, 6]⟩)(∅; *)Рисунок 2.3: Решётка узорных понятий для узорной структуры изТаблицы 2.2.Решёточная операция для подобных узорных структур определяетсякак покомпонентное нахождения минимальных интервалов, покрывающих соответствующие интервалы аргументов.
Решётка соответствующая узорной структуре из Таблицы 2.2 показана на Рисунке 2.3.Узорная структура может быть построена на основе произвольного частичного порядка. Во многих задачах на описаниях данных существует некоторый частичный порядок, соответствующий отношениям “часть–целое”, “подкласс–класс”. Например, для данных, описываемых графами, естественный частичный порядок соответствует отношению “подграф–граф” и может быть применён для анализа молекулярных графов молекул, основанного на анализе подструктур [42; 76]. Пусть дан некоторый частичный порядок (, ≤), тогдасоответствующая ему решётка (, ⊓) задаётся как множество подмножеств таких, что если ∈ принадлежит элементу решётки ∈ , то все меньшие элементы также принадлежат этому элементурешётки, ∀ ∈ , @ ∈ , ≤ : ∈/ .
При этом решёточной операцией является теоретико-множественная операция пересечения.При такой работе с узорными понятиями доказательство утверждения 1 следует из того факта, что полурешёточная операция со-38ответствует теоретико-множественной операции пересечения. Этоутверждение нам потребуется в дальнейшем для работы с узорными структурами на последовательностях.Утверждение 1. Пусть (, ⊓) – полурешётка, соответствующаячастично упорядоченному множеству (, ≤), т.е.
⊆ 2 с описанными выше свойствами. Тогда для любых , ∈ верно, что ⊑ тогда и только тогда, когда для всех ∈ существует ∈ такое, что ≤ .Нетрудно заметить, что применение такой операции к 1 , 2 ∈ даёт некоторый элемент из . Стоит отметить, что на практике множество ∈ может иметь существенный размер и поэтому его эффективнее представлять максимальными элементами данного множества, ˜ = { ∈ | @ ∈ : > }. Более того, во многих случаяхтакое представление позволяет эффективнее реализовывать решёточную операцию.2.3Проекции как средство приближенного анализаКак мы уже видели, количество формальных понятий в решётке, построенной по формальному контексту, может быть экспоненциальным от количества объектов.
Формальный контекст являетсячастным случаев узорных структур и поэтому количество узорныхпонятий в решётке, построенной для некоторой узорной структуры,может быть экспоненциальным от количества объектов в множестве. Таким образом, время построения решётки узорных понятий может занимать существенное время. Более того, большинство найденных узорных понятий не представляют интереса для дальнейшегоиспользования, но при этом занимают существенную часть временивычислений.
В случае, когда сама решёточная операция является вычислительно сложной, построение решётки узорных понятий можетстать невозможным. Например, в качестве решёточной операции наузорной структуре на графах нужно определять изоморфизм подграфу [76], что является NP-полной задачей. Для сокращения времени39работы алгоритмов построения узорных решёток были введены проекции узорных структур [40]. Проекция может быть рассмотрена какспособ фильтрации полурешётки описаний с определенными математическими свойствами. Эти свойства позволяют задать связь между понятиями в спроецированной и начальной узорных структурах.Определение 14.
Проекция полурешётки (, ⊓) – это функция : → , которая является оператором ядра [40], т.е. для любыхдвух , ∈ верно:∙ ⊑ ⇒ () ⊑ () (монотонность)∙ () ⊑ (сжимаемость)∙ (()) = () (идемпотентность)Определение 15. Проекция узорной структуры ((, (, ⊓), ))– это узорная структура с модифицированной функцией :((, (, ⊓), )) = (, (, ⊓), ∘ ).Определение 15 проекции узорной структуры дано по [40], закоторым авторы приводят следующие свойство проекций со ссылкойна [35]:Утверждение 2.
Любая проекция полной полурешётки (, ⊓) сохраняет полурешёточную операция ⊓, то есть для любых , ∈ :( ⊓ ) = () ⊓ ()(2.1)Определение 15 проекции узорной структуры имеет два существенных недостатка: во-первых, утверждение 2 является неверным,во-вторых, данное определение ограничивает виды проекций, которые могут быть применены, так как в независимости от функции ,изменения в спроецированной решётке коснутся только элементов,входящих в область значений функция . Рассмотрим эти моментыподробнее.40Для того чтобы показать ошибочность утверждения 2, рассмотрим следующий контрпример. На рисунке 2.4 показана нижняя полурешётка (, ⊓). Здесь – это множество элементов {, , , ˜, ˜, ˜}.Решёточная операция ⊓ здесь показана диаграммой для соответствующего частичного порядка на полурешётке: ≤ ⇔ ⊓ = .Пунктирными стрелками из вершины в вершину на рисунке обозначен результат применения проекции к данной вершине.
Например, () = ˜. Отметим, что ⊓ = , ˜ ⊓ ˜ = , () = ˜, () = ˜и () = ˜. Тогда˜ = () = ( ⊓ ) = () ⊓ () = ˜ ⊓ ˜ = .(2.2)Но ̸= ˜, и значит утверждение 2 неверно. Данное противоречие может быть устранено добавлением дополнительного условия к определению проекции. Так по [2] к определению проекции следует добавить:∀, ∈ , ∃ ∈ : ⊑ () ⇒ = ().(2.3)Данное условие означает, что если в узор что-то было спроекцировано, то все менее точные узоры должны проецироваться в себя.Это условие исправляет ошибку при построении спроецированнойрешётки согласно [40].˜˜˜Рисунок 2.4: Контрпример к утверждению 2.Тем не менее часто такое определение является недостаточным.Например, для интервальной узорной структуры бывает необходимо ограничить максимальный размер интервала по какой-либо ком41поненте [59], скажем, интервал не должен превышать .
Соответствующая проекция могла бы выглядеть следующим образом:(⟨· · · , [ , ], · · · ⟩) = ⟨. . . , [] ([ , ]), . . . ⟩, где [] ([, ]) = [, ] для − < и [] ([, ]) = [− inf, + inf], если − ≥ . Несложно заметить, что данное преобразование является монотонным, сжимающими идемпотентным, но не удовлетворяет условию (2.3). Возможно лиисправить определение проекции таким образом, чтобы его свойства, введенные в [40], оставались верными, но при этом можнобыло избежать условия (2.3)? Для этого в этой работе вводитьсяопределение 16.Определение 16.
Проекция узорной структуры, полученная из узорной структуры (, (, ⊓), ) с помощью проекции – это такаяузорная структура ( , ( , ⊓ ), ), в которой = , =() = { ∈ | = ()}, с полурешёточной операцией ⊓ такой,что ∀, ∈ , ⊓ := ( ⊓ ), а = ∘ .По сравнению с определением 15, это определение также меняетполурешётку описаний в проекции узорной структуры. Это позволяет проецировать не только начальное описание объектов, но и полурешёточную операцию сходства. Необходимо показать, что определение 16 корректно.
Проекция узорной структуры должна являтьсяузорной структурой в смысле определения 13, то есть ( , ⊓ ) должна являться полурешёткой.Утверждение 3. Пусть дана полурешётка (, ⊓) и проекция , тогда для всех , ∈ выполняется ( ⊓ ) = (() ⊓ ).Доказательство. Из определения проекции следует, что () ⊑ ; ⊑ ⇒ () ⊑ () и (()) = (), тогда:1. , ⊒ ( ⊓ ) ⊒ (() ⊓ ) ⊒ (() ⊓ )2. ( ⊓ ) ⊒ (() ⊓ )3. ( ⊓ ) ⊓ () ⊓ ( ⊓ ) ⊓ =(⊓)⊑()=( ⊓ ),(⊓)⊑тогда (()⊓) ⊒ (⊓) и (()⊓) ⊒ ((⊓)) = (⊓)42Из (2) and (3) следует, что ( ⊓ ) = (() ⊓ )Следствие 1. 1 ⊓ 2 ⊓ · · · ⊓ = (1 ⊓ 2 ⊓ · · · ⊓ )Следствие 2.
Пусть дана полурешётка (, ⊓) и проекция , тогда ( , ⊓ ), заданная определением 16, является полурешёткой, тоесть ⊓ является коммутативной, ассоциативной и идемпотентной операцией.Доказательство. Коммутативность и ассоциативность следуют изследствия 1 и из коммутативности и ассоциативности операции ⊓.Идемпотентность следует из того, что для любого ∈ верно() = .С новым определением проекции узорной структуры выполняются все свойств проекций, введённых в [40], кроме теоремы 2. Неверность данной теоремы также доказана для случая старого определения проекции в работе [58], поэтому здесь мы её не будем рассматривать. Далее следуют утверждения по [40], доказательства которыхприводятся в соответствии с определением 16.Утверждение 4.
() ⊑ () ⇔ () ⊑ ∘ ()Доказательство. () ⊑ () ⇒ () = (()) ⊑ (())) поидемпотентности. С другой стороны () ⊑ ∘ () ⇒ () ⊑ (),так как проекция – сжимающая операция.1Утверждение 5. Для каждого понятия в (, ( , ⊓ ), ) существует понятие в (, (, ⊓), ) с таким же объёмом. Если являетсясодержанием в (, (, ⊓), ), тогда () является содержанием в(, ( , ⊓ ), ), при этом ()◇◇ ⊑ .Доказательство. Пусть (, ) является понятием в (, ( , ⊓ ), ).Предположим, что не существует понятия в (, (, ⊓), ), чей объём равен .
Тогда ◇◇ ̸= , то есть существует ˜ ∈ , не входящееddв , ˜ ̸∈ , такое что() = ( ()) ⊓ (˜ ). Тогда, применив∈∈43проекцию к обоим частям равенства, по утверждению 3 получаddем: ( ∘ ()) = (( ∘ ()) ⊓ ∘ (˜ )) . Следовательно, по∈∈ddследствию 1: = () = ( ()) ⊓ (˜ ) = ⊓ (˜ ). Но то∈◇◇∈гда множество ̸= в (, ( , ⊓ ), ). Получили противоречие,значит в (, (, ⊓), ) существует понятие, чей объём равен .Теперь, пусть (, ) является понятием в (, (, ⊓), ), то естьdd() = . Тогда по утверждению 3 получаем () = ( ∘∈∈dd()) = ∘ () = (), то есть () является содержанием в∈∈(, ( , ⊓ ), ).Для всех объектов ∈ верно следующее () ⊑ ⊑ ().
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
