PA_full (1127144), страница 28
Текст из файла (страница 28)
множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать400 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация по прецедентам: постановка задачи401 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация по прецедентам: постановка задачи1Множество объектов X разделено на несколько подмножеств(классов).401 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация по прецедентам: постановка задачи1Множество объектов X разделено на несколько подмножеств(классов).2Информация о таком разбиении содержится только в указаниио принадлежности к данным классам элементов конечнойобучающей последовательности (выборки) из X , элементыкоторой называют прецедентами.401 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация по прецедентам: постановка задачи1Множество объектов X разделено на несколько подмножеств(классов).2Информация о таком разбиении содержится только в указаниио принадлежности к данным классам элементов конечнойобучающей последовательности (выборки) из X , элементыкоторой называют прецедентами.3Объекты имеют описание на некотором формальном языке,указывающем степень обладания объектами конечным числомпризнаков из множества M = {x1 , .
. . , xn }.401 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация: пространство объектовРис. 15. Информационная модель классификации402 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация: признаковая матрицаЧасто используется описание в виде объектно-признаковой(0, 1)-матрицы M, в которой объектам соответствуют строки,признакам � столбцы, а элементы матрицы кодируютналичие/отсутствие признаков у объектов.Класс KiОбъект 1Объект 2Объект 3...Объект mix1101...0x2011...1..................xn110...0� для каждого из классов K1 , .
. . , Ks , s > 2. Далее s = 2.403 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация: язык описания и решающее правилоЗадача обученияПо матрице M сформулировать решающее правило, котороепо описанию нового объекта из X указывало бы имя класса,его содержащего.404 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация: язык описания и решающее правилоЗадача обученияПо матрице M сформулировать решающее правило, котороепо описанию нового объекта из X указывало бы имя класса,его содержащего.Решающее правило должно максимизировать некоторойфункционал, определяющей качество классификации.404 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация: язык описания и решающее правилоЗадача обученияПо матрице M сформулировать решающее правило, котороепо описанию нового объекта из X указывало бы имя класса,его содержащего.Решающее правило должно максимизировать некоторойфункционал, определяющей качество классификации.Таким функционалом в подавляющем числе случаев являетсяминимум (не абсолютный!) числа ошибок классификации,однако может также учитываться, например, и доля отказов.404 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация: подходы к решению задачиметрические методы (NN, ...);разделяющие поверхности (SVM, ...);потенциальные функции;логические методы;коллективные решающие правила (области компетенции,голосование, алгебраический подход);структурные методы;...реляционный подход (АФП (FCA), ...)405 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация: подходы к решению задачиметрические методы (NN, ...);разделяющие поверхности (SVM, ...);потенциальные функции;логические методы;коллективные решающие правила (области компетенции,голосование, алгебраический подход);структурные методы;...реляционный подход (АФП (FCA), ...)Wille R., Ganter B.
Formal concept analysis. Berlin; Heidelberg;New York: Springer-Verl., 1999.405 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииСоответствия Галуа: определениеДалее запись отображений:f (a) записывается как af ,f (A) записывается как f A .406 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификации406 / 432Соответствия Галуа: определениеДалее запись отображений:f (a) записывается как af ,f (A) записывается как f A .ОпределениеПусть P и Q � ч.у.
множества. Пара отображений (',' : P ! Q,: Q ! P, удовлетворяющая свойствам12' и антиизотонны;x' > p и y ' > q (' иP и Q соответственно).' � операторы замыкания (наназывается соответствием Галуа между P и Q.Справедливы и более сильные соотношенияp6q, q 6 p'и),' = ' ',=' .Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПонятие: философское отступление...Понятие � это ...... целостная совокупность суждений, утверждающих оботличительных признаках вещи407 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПонятие: философское отступление...Понятие � это ...... целостная совокупность суждений, утверждающих оботличительных признаках вещиПримеры:искусство, наука, ...407 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПонятие: философское отступление...Понятие � это ......
целостная совокупность суждений, утверждающих оботличительных признаках вещиПримеры:искусство, наука, ...Объём понятия � это ...... совокупность всех вещей, обладающих зафиксированными вданном понятии признаками407 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПонятие: философское отступление...Понятие � это ...... целостная совокупность суждений, утверждающих оботличительных признаках вещиПримеры:искусство, наука, ...Объём понятия � это ......
совокупность всех вещей, обладающих зафиксированными вданном понятии признакамиПримеры:искусство: литература, живопись, архитектура,...наука: биология, физика, химия...407 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПонятие: философское отступление...Понятие � это ...... целостная совокупность суждений, утверждающих оботличительных признаках вещиПримеры:искусство, наука, ...Объём понятия � это ......
совокупность всех вещей, обладающих зафиксированными вданном понятии признакамиПримеры:искусство: литература, живопись, архитектура,...наука: биология, физика, химия...407 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПонятие: философское отступление...Содержание понятия � это ...... совокупность свойств, присущих всем объектам данногопонятия408 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПонятие: философское отступление...Содержание понятия � это ...... совокупность свойств, присущих всем объектам данногопонятияПримеры:искусство: результат отражения действительности в формечувственных образов, создание выразительных форм, ...наука: познавательная деятельность, объективность,систематичность, ...408 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификации409 / 432Закон обратного отношения между содержанием и объёмомпонятия:Большее по объёму понятие имеет меньшее содержаниеАнтимонотонность соответствий Галуа отражает этот законПрикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификации410 / 432Классификация: положительные и отрицательные примерыРассматриваются задачи, в которых множество X разбитона два непересекающихся класса:X + (положительный) иX (отрицательный)относительно обладания/необладания их объектами некоторымцелевым признаком z 62 M .Прецеденты из данных классов называются, соответственно,положительными и отрицательными примерами.Имеем 2 класса и z = ”x 2 X + ”Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииАФП: формальный контекстПусть G и M � множества, называемые соответственномножествами объектов и признаков, а I � соответствие междуG и M отношением иницидентности.gIm означает, что объект g 2 G обладает признаком m 2 M .ОпределениеТройка K = (G, M, I) называется формальным контекстом.В конечном случае контекст может быть задан в видеобъектно-признаковой (0, 1)-матрицы.411 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииСоответствия Галуа в АФП и нотацияУтверждениеЕсли для произвольных A ✓ G и B ✓ M ввести отображения' : 2G ! 2M и : 2M ! 2G такие, чтоA' = { m ✓ M | 8 g 2 A (gIm) } = A0 ,B= { g ✓ G | 8 m 2 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+ ) 2 K+ называетсяположительным.A+ � положительный формальный объём,B+ � положительное формальное содержание.Аналогично определяются отрицательные формальные объём исодержание для контекста K .415 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииГипотезыОпределениеПоложительное формальное содержание B+ положительногопонятия (A+ , B+ ) называется:416 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииГипотезыОпределениеПоложительное формальное содержание B+ положительногопонятия (A+ , B+ ) называется:положительной (+) предгипотезой, если8(A , B ) 2 K (B+ 6= B ), т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
