AA3-5(Lattice) (1127143), страница 3
Текст из файла (страница 3)
Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификацииАФП: формальный контекстПустьG — множество объектов;M — множество признаков;I — соответствие между G и M называемоеотношением иницидентности, т.е. gIm означает,что объект g ∈ G обладает признаком m ∈ M .ОпределениеТройка K = (G, M, I) называется формальным контекстом.В конечном случае контекст может быть задан в видеобъектно-признаковой (0, 1)-матрицы.44 / 62ПРИКЛАДНАЯ АЛГЕБРА.
Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификацииСоответствия Галуа в АФП и нотацияУтверждениеЕсли для произвольных A ⊆ G и B ⊆ M ввести отображенияϕ : 2G → 2M и ψ : 2M → 2Gтакие, чтоAϕ = { m ∈ M | ∀ g ∈ A (gIm) } = A 0 ,Bψ = { g ∈ G | ∀ m ∈ B (gIm) } = B 0 ,то пара отображений (ϕ, ψ) будет соответствием Галуа междуч.у. множествами 2G и 2M ,упорядоченными по включению.45 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификацииФормальные объём и содержаниеОпределениеПусть дан контекст K = (G, M, I).Пара подмножеств (A, B), где A ⊆ G, B ⊆ M , и таких, чтоA 0 = B и B 0 = A, называется формальным понятием данногоконтекста с формальным объёмом A и формальнымсодержанием B.Если контекст представлен в виде объектно-признаковой(0, 1)-матрицы, то формальному понятию соответствуетмаксимальная её подматрица, заполненная единицами.Формальные объём и содержание — замкнутые,соответственно, относительно ϕψ и ψϕ множества.46 / 62ПРИКЛАДНАЯ АЛГЕБРА.
Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификацииРешётка формальных понятийТеорема (основная АФП)Множество всех формальных понятий данного контекста Kобразует полную решётку, обозначаемую B(K), относительноопераций ∨ (объединение) и ∧ (пересечение):(A1 , B1 ) ∨ (A2 , B2 ) = (B1 ∩ B2 )0 , B1 ∩ B2 ,(A1 , B1 ) ∧ (A2 , B2 ) = A1 ∩ A2 , (A1 ∩ A2 )0и называемую решёткой формальных понятий.(A1 , B1 ) v (A2 , B2 ) ⇒ (A1 ⊆ A2 ) N (B1 ⊇ B2 )У решётки B(K) формального контекста K = (G, M, I):единица ι — формальное понятие (G, G 0 );атомы — формальные понятия вида (g, g 0 );нуль o — формальное понятие (∅, M ) с пустым объёмом.47 / 62ПРИКЛАДНАЯ АЛГЕБРА.
Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификацииДва контекста: объём и содержаниеДанные для обучения классификации описываютсяположительным K+ = (G+ , M, I+ ) иотрицательным K− = (G− , M, I− ) контекстами.Операторы Галуа в этих контекстах обозначаютсясоответствующими верхними индексами: A+ , A− , B + и т.д.ОпределениеФормальное понятие (A+ , B+ ) ∈ K+ называетсяположительным.A+ — положительный формальный объём,B+ — положительное формальное содержание.Аналогично определяются отрицательные формальные объём исодержание для контекста K− .48 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификацииГипотезы формальных контекстовОпределениеПоложительное формальное содержание B+ положительногопонятия (A+ , B+ ) называется:положительной ⊕−предгипотезой, если∀(A− , B− ) ∈ K− (B+ 6= B− ), т.
е. оно не являетсяформальным содержанием ни одного отрицательного понятия;положительной ⊕−гипотезой, если∀(g, g − ) ∈ K− (B+ 6⊆ g − ), т. е. оно не являетсяподмножеством содержания понятия какого-либоотрицательного примера g;фальсифицированной положительной ⊕−гипотезой, если∃(g, g − ) ∈ K− (B+ ⊆ g − ).Отрицательные (−предгипотезы, ...) определяются аналогично.Гипотеза является также и предгипотезой.49 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация с помощью гипотезГипотезы используются для классификации новых объектовПростейшее решающее правилоПусть g 6∈ {G+ ∪ G− } — новый (неопределённый) объект.Если его формальное содержание g 0 содержит хотя бы одну⊕−гипотезу и не содержит ни одной отрицательнойгипотезы, то он относится к положительному классу;−гипотезу и не содержит ни одной положительнойгипотезы, то он относится к отрицательному классу.Отказ от классификации происходит, если g 0 :либо не содержит никаких гипотез (недостаток данных);либо содержит как положительные, так и отрицательныегипотезы (противоречие в данных).50 / 62ПРИКЛАДНАЯ АЛГЕБРА.
Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификацииМногозначные контекстыДля получения бинарной информации о признаках изколичественных и качественных признаков используетсяпроцедура шкалирования.Многозначный контекст — это четвёрка (G, M, Z, I), гдеG, M, Z — множества объектов, признаков и значенийпризнаков соответственно,I — тернарное отношение I ⊆ G × M × Z, задающеезначение z ∈ Z признака m ∈ M объекта g ∈ G,причем отображение G × M → Z функционально.Шкалирование — это представление многозначных контекстовдвузначными.51 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификации52 / 62Пример «Фрукты»: постановка задачиЗадача:построить классификатор по целевому свойствуz = «являться фруктом» и следующей объектно-признаковойтаблице положительных и отрицательных примеров:№1234567G\Mяблокогрейпфруткивисливакубикяйцотеннисныймячцветжёлтоежёлтыйзелёныйсиняязелёныйбелое(белый)жёсткий гладкий форманетдакруглоенетнеткруглыйнетнетовальноенетдаовальнаядадакубическийдадаовальноенетнеткруглыйz++++−−−ПРИКЛАДНАЯ АЛГЕБРА.
Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификации53 / 62Пример «Фрукты»: результат шкалированияG\M1234567wy××gbf×××××f×××××××s×s××r××××××××××r×z++++−−−G+ = {1, 2, 3, 4}, G− = {5, 6, 7} ⇒ отношение I+ представленоверхней частью таблицы, а отношение I− — нижней.Признаки означают:w — белый, y — жёлтый, g — зелёный, b — синий;f — твёрдый, f — мягкий, s — гладкий, s — шероховатый;r — круглый, r — некруглый.ПРИКЛАДНАЯ АЛГЕБРА.
Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификации54 / 62Пример «Фрукты»: решётка B(K+ )'''''[['''''[''[''''['''[''[{3, 4}, {f , r}{1, 2}, {f , r, y}{1, 4}, {f , s}{2, 3}, {f , s}''''''''[[[''[[[''[[[[[ '''[[ '''[[ '''[[[[[[{2}, {y, f , s, r}{4}, {b, f , s, r}{1}, {y, f , s, r}{3}, {g, f , s, r}''''[[ '''''''[''['[''''''[[' 'G+ , {f }(∅, M )ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификацииПример «Фрукты»: решётка B(K− )(G , ∅)AAAAAA({6, 7}, {w})({5, 6}, {f, s, r})AAAAAA{f, r, s, g}){7}, {w, f , s, r} ({6}, {r, f, s, w}) A({5},AAAAAA−(∅, M )55 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификацииПример «Фрукты»: формирование гипотезФормальные содержания{f , r} (мягкий, некруглый),{f , r, y} (мягкий, круглый, жёлтый) и{f , s} (мягкий, гладкий)— являются ⊕−гипотезами;{f , s} (мягкий, шероховатый)— является фальсифицированной ⊕−гипотезой, т.к.она — часть содержания {w, f , s, r} отрицательногопримера 7 (теннисный мяч);{w} (белый) и{f, s, r} (твёрдый, гладкий, некруглый)— являются −гипотезами.56 / 62ПРИКЛАДНАЯ АЛГЕБРА.
Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификацииПример «Фрукты»: классификацияНеопределённый объект gмирабель будет классифицирован как фрукт , т.к. егоформальноесодержание жёлтый, мягкий, гладкийy, f , s содержит ⊕−гипотезу f , s и не содержит ниодной из −гипотез);кусок сахара со свойствам белый, некруглый, твёрдыйбудет классифицирован как не-фрукт ;брикет пломбира со свойствами белый, мягкий,некруглыйвызоветотказ от классификации, поскольку0g = w, f , r содержит как положительную f , r , таки отрицательную {w} гипотезы.57 / 62ПРИКЛАДНАЯ АЛГЕБРА.
Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификацииПример «Фрукты»: дополнениеЕсли считать, что теннисный мяч — зелёный, то B(K− ):(G , ∅)AAAAAA({5, 6}, {f, s, r})({5, 7}, {g})AAAAAA{f, r, s, w}){7}, {g, f , s, r} ({5}, {r, f, s, g}) A({6},AAAAA−(∅, M )58 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиПрименение теории решёток к задаче классификацииПример «Фрукты»: дополнение...При таком изменении свойств объекта № 7 изменятся толькоотрицательный контекст. Теперь{g} = {5, 7}0 является фальсифицированной−гипотезой, поскольку она содержится в формальномсодержании {g, f , s, r} положительного понятия {3}.{f, s, r} = {5, 6}0 является −гипотезой.Поэтомуобъекты со свойствами жёлтый, мягкий, гладкий и белый,мягкий, некруглый будет классифицированы как фрукт;на объекте с единственным свойством белый произойдётотказ от классификации.59 / 62ПРИКЛАДНАЯ АЛГЕБРА.
Часть V: Алгебраические решёткиЧто надо знатьРазделы1Решётки: определение, основные свойства2Модулярные и дистрибутивные решётки3Применение теории решёток к задаче классификации4Что надо знать60 / 62ПРИКЛАДНАЯ АЛГЕБРА. Часть V: Алгебраические решёткиЧто надо знатьРешёточно упорядоченное множество, алгебраическиерешётки и их эквивалентность. Примеры.Гомоморфизмы решёток, связь порядкового и решёточногогомоморфизмов. Сечения Макнила.Идеалы решёток. Модулярные и дистрибутивные решётки.Критерии модулярности и дистрибутивности решётки.Неразложимые элементы решёток и представлениепроизвольных элементов решётки через неразложимые.Изоморфизм ч.у. множества и неразложимых элементоврешётки его порядковых идеалов.Фундаментальная теорема о конечных дистрибутивныхрешётках.Задача классификация по прецедентам. Закон обратногоотношения между содержанием и объёмом понятия.Соответствия Галуа.61 / 62ПРИКЛАДНАЯ АЛГЕБРА.
Часть V: Алгебраические решёткиЧто надо знатьАнализ формальных понятий (АФП). Формальные объёми содержание. Решётка формальных понятий.Гипотезы АФП. Простейшее решающее правилоклассификации.62 / 62.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
