Лекции по прикладной алгебре. v2.0 (1127112), страница 29
Текст из файла (страница 29)
Пара отображений (ϕ, ψ),ϕ : P → Q, ψ : Q → P, удовлетворяющая свойствам12ϕ и ψ антиизотонны;xϕψ > p и yψϕ > q (ϕψ и ψϕ — операторы замыкания (наP и Q соответственно).называется соответствием Галуа между P и Q.Справедливы и более сильные соотношенияp 6 qψ ⇔ q 6 pϕиϕ = ϕψϕ, ψ = ψϕψ .406 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПонятие: философское отступление...Понятие — это ...... целостная совокупность суждений, утверждающих оботличительных признаках вещи407 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПонятие: философское отступление...Понятие — это ...... целостная совокупность суждений, утверждающих оботличительных признаках вещиПримеры:искусство, наука, ...407 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПонятие: философское отступление...Понятие — это ......
целостная совокупность суждений, утверждающих оботличительных признаках вещиПримеры:искусство, наука, ...Объём понятия — это ...... совокупность всех вещей, обладающих зафиксированными вданном понятии признаками407 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПонятие: философское отступление...Понятие — это ...... целостная совокупность суждений, утверждающих оботличительных признаках вещиПримеры:искусство, наука, ...Объём понятия — это ...... совокупность всех вещей, обладающих зафиксированными вданном понятии признакамиПримеры:искусство: литература, живопись, архитектура,...наука: биология, физика, химия...407 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПонятие: философское отступление...Понятие — это ...... целостная совокупность суждений, утверждающих оботличительных признаках вещиПримеры:искусство, наука, ...Объём понятия — это ......
совокупность всех вещей, обладающих зафиксированными вданном понятии признакамиПримеры:искусство: литература, живопись, архитектура,...наука: биология, физика, химия...407 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПонятие: философское отступление...Содержание понятия — это ......
совокупность свойств, присущих всем объектам данногопонятия408 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПонятие: философское отступление...Содержание понятия — это ...... совокупность свойств, присущих всем объектам данногопонятияПримеры:искусство: результат отражения действительности в формечувственных образов, создание выразительных форм, ...наука: познавательная деятельность, объективность,систематичность, ...408 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификации409 / 432Закон обратного отношения между содержанием и объёмомпонятия:Большее по объёму понятие имеет меньшее содержаниеАнтимонотонность соответствий Галуа отражает этот законПрикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификации410 / 432Классификация: положительные и отрицательные примерыРассматриваются задачи, в которых множество X разбитона два непересекающихся класса:X + (положительный) иX − (отрицательный)относительно обладания/необладания их объектами некоторымцелевым признаком z 6∈ M .Прецеденты из данных классов называются, соответственно,положительными и отрицательными примерами.Имеем 2 класса и z = ”x ∈ X + ”Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииАФП: формальный контекстПусть G и M — множества, называемые соответственномножествами объектов и признаков, а I — соответствие междуG и M отношением иницидентности.gIm означает, что объект g ∈ G обладает признаком m ∈ M .ОпределениеТройка K = (G, M, I) называется формальным контекстом.В конечном случае контекст может быть задан в видеобъектно-признаковой (0, 1)-матрицы.411 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииСоответствия Галуа в АФП и нотацияУтверждениеЕсли для произвольных A ⊆ G и B ⊆ M ввести отображенияϕ : 2G → 2M и ψ : 2M → 2G такие, чтоAϕ = { m ⊆ M | ∀ g ∈ A (gIm) } = A0 ,Bψ = { g ⊆ G | ∀ m ∈ B (gIm) } = B 0 ,то пара отображений (ϕ, ψ) являетсясоответствием Галуа между ч.у.
множествами 2G и 2M ,упорядоченными по включению.412 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииФормальные объём и содержаниеОпределениеПусть дан контекст K = (G, M, I). Пара подмножеств (A, B),где A ⊆ G, а B ⊆ M , и таких, что A0 = B и B 0 = A,называется формальным понятием данного контекстас формальным объёмом A и формальным содержанием B.Если контекст K представлен в виде объектно-признаковой(0, 1)-матрицы, то формальному понятию соответствуетмаксимальная её подматрица, заполненная единицами.Формальные объём и содержание — замкнутые,соответственно, относительно ϕψ и ψϕ множества.413 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииРешётка формальных понятийТеорема (основная АФП)Множество всех формальных понятий данного контекста Kобразует полную решётку, обозначаемую B(K), относительноопераций ∨ (объединение) и ∧ (пересечение):(A1 , B1 ) ∨ (A2 , B2 ) = (B1 ∩ B2 )0 , B1 ∩ B2 ,(A1 , B1 ) ∧ (A2 , B2 ) = A1 ∩ A2 , (A1 ∩ A2 )0и называемую решёткой формальных понятий.414 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииРешётка формальных понятийТеорема (основная АФП)Множество всех формальных понятий данного контекста Kобразует полную решётку, обозначаемую B(K), относительноопераций ∨ (объединение) и ∧ (пересечение):(A1 , B1 ) ∨ (A2 , B2 ) = (B1 ∩ B2 )0 , B1 ∩ B2 ,(A1 , B1 ) ∧ (A2 , B2 ) = A1 ∩ A2 , (A1 ∩ A2 )0и называемую решёткой формальных понятий.(A1 , B1 ) 6 (A2 , B2 ) ⇒ (A1 ⊆ A2 ) N (B1 ⊇ B2 )414 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииРешётка формальных понятийТеорема (основная АФП)Множество всех формальных понятий данного контекста Kобразует полную решётку, обозначаемую B(K), относительноопераций ∨ (объединение) и ∧ (пересечение):(A1 , B1 ) ∨ (A2 , B2 ) = (B1 ∩ B2 )0 , B1 ∩ B2 ,(A1 , B1 ) ∧ (A2 , B2 ) = A1 ∩ A2 , (A1 ∩ A2 )0и называемую решёткой формальных понятий.(A1 , B1 ) 6 (A2 , B2 ) ⇒ (A1 ⊆ A2 ) N (B1 ⊇ B2 )У решётки B(K) формального контекста K = (G, M, I):единица ι — формальное понятие (G, G 0 );атомы — формальные понятия вида (g, g 0 );нуль o — формальное понятие (∅, M ) с пустым объёмом.414 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииДва контекста: объём и содержаниеДанные для обучения классификации описываютсяположительным K+ = (G+ , M, I+ ) и отрицательнымK− = (G− , M, I− ) контекстами.Операторы Галуа в этих контекстах обозначаютсясоответствующими верхними индексами: A+ , A− , B + и т.д.ОпределениеФормальное понятие (A+ , B+ ) ∈ K+ называетсяположительным.A+ — положительный формальный объём,B+ — положительное формальное содержание.Аналогично определяются отрицательные формальные объём исодержание для контекста K− .415 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииГипотезыОпределениеПоложительное формальное содержание B+ положительногопонятия (A+ , B+ ) называется:416 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииГипотезыОпределениеПоложительное формальное содержание B+ положительногопонятия (A+ , B+ ) называется:положительной (+) предгипотезой, если∀(A− , B− ) ∈ K− (B+ 6= B− ), т.
е. оно не являетсяформальным содержанием ни одного отрицательного понятия;416 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииГипотезыОпределениеПоложительное формальное содержание B+ положительногопонятия (A+ , B+ ) называется:положительной (+) предгипотезой, если∀(A− , B− ) ∈ K− (B+ 6= B− ), т. е. оно не являетсяформальным содержанием ни одного отрицательного понятия;положительной (+) гипотезой, если∀(g, g − ) ∈ K− (B+ 6⊆ g − ), т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
