Диссертация (1137241), страница 4
Текст из файла (страница 4)
Решетка одновременно является и весьма удобным19моделью представления знаний, допускающим различные уровнидетализации, и весьма проработанным и развитым средством дляработы с данными.Эти свойства делают решетки весьма привлекательными в планеприменения к задачам обработки текста, поскольку уже существуют иизвестны самые разные способы и модели, позволяющие построитьформальное описание текста на синтаксическом и семантическомуровне.1.2.1 Частично упорядоченные множества и решеткиОпределение 1.1. Бинарное отношениемножествеSна некоторомназывается отношением (нестрогого) частичногопорядка, если для s, t, u S :1. ≤ (рефлексивность);2. Если ≤ и ≤ , то = (антисимметричность);3.
Если ≤ и ≤ , то ≤ (транзитивность).Множество S с определённым на нем отношением частичногопорядка ≤ (частично упорядоченное множество) обозначается S , .Если ≤ , то говорят, что элемент меньше, чем , или равен ему.Если для не существует , такого что ≤ , то называютмаксимальным элементом (относительно ≤). Если ≤ и s t , топишут < и говорят, что строго меньше, чем .Определение1.2.Пусть S , частично упорядоченноемножество. Элемент ∈ называется соседом снизу элемента ∈ ,если < и v S : l v u . В этом случае называется соседомсверху (обозначается ⪯ ).
Направленный граф отношения ⪯называется графом покрытия.20Графически конечное частично упорядоченное множество S , может быть представлено с помощью диаграммы частичного порядка[1]. Элементы изображаются в виде точек. Если ⪯ , то размещается«над»(вертикальнаякоординатабольшевертикальной координаты ), и две точки соединяются линией.Определение1.3.Верхнейграньюподмножествавупорядоченном множестве называется элемент ∈ , такой что ≥ для всех ∈ .Точнаяверхняяграньнаименьшейверхнейграньюмножестваили(называемаясупремумом)такжемножества(обозначается sup) есть верхняя грань такая, что ≤ 1 для любойверхней грани 1 подмножества .Двойственным образом (с заменой ≥ на ≤) определяется понятиеточной (наибольшей) нижней грани или инфимума inf.Определение 1.4.
Бинарная операция ⊓: × → называетсяполурешёточной, если для некоторого ∈ и любых , , ∈ :1. ⊓ = (идемпотентность);2. ⊓ = ⊓ (коммутативность);3. ( ⊓ ) ⊓ = ⊓ ( ⊓ ) (ассоциативность);4. ⊓ = .Для = {1, . . . , } ⊆ и ∈ N мы пишем ⊓ вместо 1 ⊓ . . .⊓ .Если = {}, то ⊓ = .Определение 1.5. Множество с определённой на немполурешёточной операцией ⊓ называется полурешёткой (,⊓).21Полурешёточная операция ⊓ задает два частичных порядка ⊑ и⊒ на (, ∈ ): ⊑ ⇔ ⊓ = и ⊒ ⇔ ⊓ = .Тогда множество с определённой на нем полурешёточнойоперацией (,⊓) будем называть нижней полурешёткой (относительночастичного порядка ⊑) и верхней полурешёткой (относительночастичного порядка ⊒).Определение 1.6.
Пусть (,⊓) — полурешётка. Множество ⊆ называется системой замыканий [16] или семейством Мура [1](относительно ⊓), если ∀, ∈ : ⊓ ∈ .Очевидно, что система замыканий (относительно ⊓) сопределённой на ней операцией, ∧: × → и ∧ = ⊓ ,образует полурешётку.Определение1.7.Упорядоченноемножество(,≤)сопределёнными на нем полурешёточными операциями ∧ и ∨называется решёткой, если (,∧) и (,∨) являются, соответственно,нижней и верхней полурешётками (относительно ≤).Операции ∧ и ∨ называют операциями взятия точной нижней иверхней грани в решётке или инфимума и супремума, соответственно.Определение1.8.Подрешёткойрешёткиназываетсяподмножество ⊂ такое, что если ∈ , ∈ , то ∧ ∈ и ∨ ∈ .Полурешёточные операции ∧ и ∨ удовлетворяют в решёткахследующему условию: ∧ ( ∨ ) = ∨ ( ∧ ) = (поглощение).Из любой конечной полурешётки можно получить решёткудобавлениемодного(максимальногозависимости от типа полурешетки) элемента.илиминимальногов22Решётка называется полной, если у каждого подмножества егоэлементов есть супремум и инфимум (всякая конечная решёткаявляется полной).Определение1.9.Пусть(,≤)и(,≤)—частичноупорядоченные множества.
Пара отображений : ↦ и : ↦ называется соответствием Галуа между частично упорядоченнымимножествами (,≤) и (,≤ ), если для любых ∈ и ∈ :1. 1 ≤ 2 ⇒ (2) ≤ (1);2. 1 ≤ 2 ⇒ (2) ≤ (1);3. ≤ (())4. ≤ (()).1.2.2 Анализ формальных понятийАнализ формальных понятий (АФП) [16] - это прикладная ветвьтеории решеток. Основные сущности АФП были формально описаныРудольфом Вилле в 1982 году. С точки зрения анализа данных,методы, основанные на анализе формальных понятий, относятся кметодам бикластеризации (объектно-признаковой кластеризации). ВАФП рассматриваются не кластеры объектов, оторванных отисходного описания, а группы объектов и признаков, сильносвязанных друг с другом.Определение 1.10.
Формальный контекст K есть тройка(G, M , I ) , где G - множество, называемое множеством объектов,M-множество,называемоеI G M - бинарное отношение.множествомпризнаков,23Отношение I интерпретируется следующим образом: для g G,m M gIm выполнено тогда и только тогда, когда объект g обладаетпризнаком m.Определение 1.11.
Для формального контекста K (G, M , I ) ипроизвольных A G, B M определена пара отображений:A m M | g Im g A , B g G | g Im m B .Эти отображения задают соответствие Галуа между частичноупорядоченными множествами (2G , ) и (2M , ) , а операторы ()являются операторами замыкания на G и M. Иными словами, дляпроизвольного A GA Mилиимеютместоследующиесоотношения [16]:1. A A (экстенсивность),2. A A (идемпотентность),3. если A C , то A C (изотонность).Определениеконтекста1.12.K (G, M , I )Формальноеестьпарапонятие(A,B),гдеформальногоA G, B M ,A B, B A.
Множество A называется объёмом, а B - содержаниемпонятия (A,B).Для двух формальных понятий (A,B) и (C,D) некоторогоконтекста(A,B)называетсяподпонятием(C,D),еслиAC(эквивалентно D B ). В этом случае (C,D) является надпонятием(A,B).Множество формальных понятий контекста K, упорядоченныхпо вложению объемов (содержаний), образует решетку формальныхпонятий ( K ) .241.2.3 Решетки замкнутых описанийАФП преобразует формальный контекст, представленный какбинарное отношение, в решетку формальных понятий, но во многихслучаях исследуемые «объекты» могут иметь более сложноеописание, чем множество некоторых наперед заданных признаков.Например,исследуямножествообъектов,возможнолиихисследовать без выделения специальных бинарных признаков?Узорные структуры (pattern structures) дают ответ на этот вопрос,являясь расширением АФП для работы со сложными данными [67],такимикакданные,описываемыечисленнымизначениями,множествами последовательностей или графов.⊓) ),Определение 1.13.
Узорная структура – это тройкагде–множество⊓)объектов,всевозможных описаний, а–полнаяполурешетка– функция, которая сопоставляеткаждому объекту из множестваего описание из .Полурешеточная операция ⊓ соответствует операции сходствамежду двумя описаниями.1.2.4 Проекции решеток замкнутых описанийПоскольку размер решетки узорных понятий может бытьсущественным, а сама решеточная операция – асимптотическисложной (например, для построения узорной структуры на графахнеобходимо вычислять изоморфизм подграфов), построение решеткиузорныхпонятийможетзаниматьсущественноевремя.Дляуменьшения этого времени были введены проекции узорных структур[67]. Проекция может быть рассмотрена как некоторый фильтрполурешеткиописаниясопределеннымиматематическимисвойствами. Эти свойства позволяют доказать, что существуетинъекция между понятиями спроецированной и исходной решеток.25Определение 1.14.
Проекция узорной структуры – это функция,котораяявляетсямонотонной) ⊑ ) и идемпотентной (сжимающей (( ⊑⇒)))⊑)),)) [67].Узорная структура проецируется следующим образом. Мыдолжны спроецировать функцию – описание объектов, а такжеполурешетку описаний:⊓) )))⊓ )и∀∈), где⊓)∈∈⊓ ).1.3 Прикладные онтологииПрикладные онтологии являются одной из наиболее удобныхмоделей для структурного представления знаний, извлеченных изтекста. Они позволяют хранить данные об именованных сущностях,семантических связях и свойствах текстовых фрагментов. В нашемисследовании они применяются в качестве исходных данных задачепостроения кореферентных связей в предобработанном тексте.Введем формальное определение прикладной онтологии [17].Определение 1.15.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
