AA3-5(Lattice) (1127143), страница 2
Текст из файла (страница 2)
Часть V: Алгебраические решёткиМодулярные и дистрибутивные решёткиКритерий дистрибутивности решёткиНедистрибутивность M3 , оказывается ключевой: справедливаТеоремаМодулярная решётка является дистрибутивной, iff никакая еёподрешётка не изоморфна ромбу M3 .Следствие (критерий дистрибутивности решётки)Решётка дистрибутивна, iff никакая её подрешётка неизоморфна ни пятиугольнику N5 , ни ромбу M3 .24 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиМодулярные и дистрибутивные решётки25 / 62Дистрибутивность решётки J(P)ЛеммаJ(P) 6 h P(P), ∪, ∩ i ⇒ решётка J(P) дистрибутивна.cO[[[a[[[b[[[ ha, bicbaOO∅Z3 ,J(Z3 )ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиМодулярные и дистрибутивные решёткиНеразложимые элементы решётокВ конечных дистрибутивных решётках важную роль играют неатомы (например, в конечной цепи всего один атом), анеразложимые в объединение элементы.ОпределениеЭлемент z 6= o решётки назовём неразложимым, если изz = x t y следует либо z = x, либо z = y.Пример123Атомы любой решётки неразложимы, и в атомной булевойалгебре нет других неразложимых элементов.В решётке h N, | i неразложимы только степени простыхчисел.В цепи ни один элемент не является разложимым.26 / 62ПРИКЛАДНАЯ АЛГЕБРА.
Часть V: Алгебраические решёткиМодулярные и дистрибутивные решёткиНеразложимые элементы решёток...ЛеммаВ конечной решётке каждый ненулевой элемент может бытьпредставлен в виде объединения неразложимых элементов.ДоказательствоЕсли элемент b неразложим, то b = b t b.Пусть b = b1 t b2 и b1 6= b 6= b2 .Если и b1 , и b2 неразложимы, то лемма доказана.В противном случае представляем b1 и/или b2 в видеобъединения строго содержащихся в них элементов, и т.д.В силу конечности решётки указанный процесс закончится,и исходный элемент b будет представлен в видеобъединения неразложимых элементов.27 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиМодулярные и дистрибутивные решёткиПредставление произвольных элементов решётки черезнеразложимыеОбозначения для подмножеств элементов(дистрибутивной) решётки LIrr L — множество неразложимых в объединениеэлементов L;Irr(x) = { y ∈ Irr L | y 6 x } — множество неразложимыхэлементов L, содержащихся в x.Доказанная лемма утверждает, что в конечной решётке каждыйненулевой элемент x допускает представление:Gx =a.a ∈ Irr(x)28 / 62ПРИКЛАДНАЯ АЛГЕБРА.
Часть V: Алгебраические решёткиМодулярные и дистрибутивные решёткиИзоморфизм ч.у. множества и неразложимых элементоврешётки его порядковых идеаловЛеммаЕсли P — ч.у. множество, то Irr J(P) ∼= P.ДоказательствоПусть P — ч.у. множество и тогда J(P) — дистрибутивнаярешётка его порядковых идеалов. Порядковый идеал решёткинеразложим, iff он является главным:Irr J(P) ∼= J0 (P) = { xO | x ∈ P }.Ранее был установлен изоморфизм между ч.у. множеством исовокупностью его главных идеалов:ϕ : P → J(P ), ϕ(x) = xO ,поэтому P ∼= J0 (P ) = Irr J(P ).29 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиМодулярные и дистрибутивные решётки30 / 62Irr J(P) ∼= P: примерcOc[[[a[[[b[[[ ha, bibaOO∅Z3 ,множество Irr J(Z3 ) выделеноПРИКЛАДНАЯ АЛГЕБРА.
Часть V: Алгебраические решёткиМодулярные и дистрибутивные решёткиФундаментальная теорема о конечных дистрибутивныхрешёткахТеорема (ФТКДР, Г. Биркгоф)Всякая конечная дистрибутивная решётка L изоморфнарешётке порядковых идеалов ч.у. множества её неразложимыхэлементов: L = J(Irr L).Доказательство (набросок)Пусть L = h L, t, u i — конечная дистрибутивная решётка иJ(Irr L) — решётка порядковых идеалов ч.у. множества Irr L.Рассмотрим отображение ψ : L → J(Irr L) , ψ(x) = Irr(x).Отображение ψ есть биекция.x 6 y ⇔ Irr(x) ⊆ Irr(y) ⇔ ψ(x) ⊆ ψ(y).∴ ψ — (порядковый) изоморфизм между L и J(Irr L).31 / 62ПРИКЛАДНАЯ АЛГЕБРА.
Часть V: Алгебраические решёткиМодулярные и дистрибутивные решётки32 / 62ФТКДР L = J(Irr L): иллюстрацияιOι[[[ι [a[ba[[[[[ oLaObIrr L[[[b[[[ ha, bicO∅J(Irr L)ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификацииРазделы1Решётки: определение, основные свойства2Модулярные и дистрибутивные решётки3Применение теории решёток к задаче классификации4Что надо знать33 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация по прецедентам: постановка задачи1Множество объектов X разделено на несколько подмножеств(классов).2Информация о таком разбиении содержится только в указаниио принадлежности к данным классам элементов конечнойобучающей последовательности (выборки) из X , элементыкоторой называют прецедентами.3Объекты имеют описание на некотором формальном языке,указывающем степень обладания объектами конечным числомпризнаков из множества M = {x1 , .
. . , xn }.34 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация: пространство объектов35 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификации36 / 62Классификация: признаковая матрицаЧасто используется описание в виде объектно-признаковой(0, 1)-матрицы M, в которой объектам соответствуют строки,признакам — столбцы, а элементы матрицы кодируютналичие/отсутствие признаков у объектов.Класс KiОбъект 1Объект 2Объект 3...Объект mix1101...0x2011...1..................xn110...0— для каждого из классов K1 , .
. . , Ks , s > 2. Далее s = 2.ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация: язык описания и решающее правилоЗадача обученияПо матрице M сформулировать решающее правило, котороепо описанию нового объекта из X указывало бы имя класса,его содержащего.Решающее правило должно максимизировать некоторойфункционал, определяющей качество классификации.Таким функционалом в подавляющем числе случаев являетсяминимум (не абсолютный) числа ошибок классификации,однако может также учитываться, например, и доля отказов.37 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация: подходы к решению задачиметрические методы (NN, ...);разделяющие поверхности (SVM, ...);потенциальные функции;логические методы;коллективные решающие правила (области компетенции,голосование, алгебраический подход);структурные методы;...реляционный подход (АФП (FCA), ...)Wille R., Ganter B.
Formal concept analysis. Berlin; Heidelberg;New York: Springer-Verl., 1999.38 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификацииСоответствия Галуа: определениеДалее запись отображений:f (a) записывается как af , а f (A) записывается как Af .ОпределениеПусть P = h P, vP i и Q = h Q, vP i — ч.у. множества.Пара отображений (ϕ, ψ), ϕ : P → Q, ψ : Q → P ,удовлетворяющая свойствам1ϕ и ψ антиизотонны;2pϕψ w p и qψϕ w q, p ∈ P, q ∈ Q ( ϕψ и ψϕ —операторы замыкания на P и Q соответственно).называется соответствием Галуа между P и Q.Справедливы и более сильные соотношенияp v qψ ⇔ q v pϕиϕ = ϕψϕ, ψ = ψϕψ.39 / 62ПРИКЛАДНАЯ АЛГЕБРА.
Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификацииПонятие: философское отступление...Понятие — это ...... целостная совокупность суждений об отличительныхпризнаках вещей и отношений между нимиПримеры:искусство, наука, ...Объём понятия — это ...... совокупность всех вещей, обладающих зафиксированными вданном понятии признакамиПримеры:искусство: литература, живопись, архитектура,...наука: биология, физика, химия...40 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификацииПонятие: философское отступление...Содержание понятия — это ...... совокупность свойств, присущих всем объектам данногопонятияПримеры:искусство: результат отражения действительности в формечувственных образов, создание выразительных форм, ...наука: познавательная деятельность, объективность,систематичность, ...41 / 62ПРИКЛАДНАЯ АЛГЕБРА.
Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификации42 / 62Закон обратного отношения между содержанием и объёмомпонятия:Бо́льшее по объёму понятие имеет меньшее содержаниеАнтимонотонность соответствий Галуа отражает этот законПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификации43 / 62Классификация: положительные и отрицательные примерыРассматриваются задачи, в которых множество X разбитона два непересекающихся класса:X + (положительный) и X − (отрицательный)относительно обладания/необладания их объектами некоторымцелевым признаком z 6∈ M .Прецеденты из данных классов называются, соответственно,положительными и отрицательными примерами.Имеем 2 класса и z = ”x ∈ X + ”ПРИКЛАДНАЯ АЛГЕБРА.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
