Лекции по прикладной алгебре. v2.0 (1127112), страница 30

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 30)

оно не являетсяподмножеством содержания понятия какого-либоотрицательного примера g;416 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииГипотезыОпределениеПоложительное формальное содержание B+ положительногопонятия (A+ , B+ ) называется:положительной (+) предгипотезой, если∀(A− , B− ) ∈ K− (B+ 6= B− ), т. е. оно не являетсяформальным содержанием ни одного отрицательного понятия;положительной (+) гипотезой, если∀(g, g − ) ∈ K− (B+ 6⊆ g − ), т. е.

оно не являетсяподмножеством содержания понятия какого-либоотрицательного примера g;фальсифицированной положительной (+) гипотезой, если∃(g, g − ) ∈ K− (B+ ⊆ g − ).416 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииГипотезыОпределениеПоложительное формальное содержание B+ положительногопонятия (A+ , B+ ) называется:положительной (+) предгипотезой, если∀(A− , B− ) ∈ K− (B+ 6= B− ), т. е. оно не являетсяформальным содержанием ни одного отрицательного понятия;положительной (+) гипотезой, если∀(g, g − ) ∈ K− (B+ 6⊆ g − ), т. е. оно не являетсяподмножеством содержания понятия какого-либоотрицательного примера g;фальсифицированной положительной (+) гипотезой, если∃(g, g − ) ∈ K− (B+ ⊆ g − ).Отрицательные (−) предгипотезы, гипотезы,фальсифицированные гипотезы определяются аналогично.Гипотеза является также и предгипотезой.416 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация с помощью гипотезГипотезы используются для классификации новых объектов.417 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация с помощью гипотезГипотезы используются для классификации новых объектов.Простейшее решающее правилоПусть g 6∈ {G+ ∪ G− } — новый неопределённый объект.417 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация с помощью гипотезГипотезы используются для классификации новых объектов.Простейшее решающее правилоПусть g 6∈ {G+ ∪ G− } — новый неопределённый объект.Если его формальное содержаниеg 0 содержит хотя бы одну+-гипотезу и не содержит ни одной отрицательнойгипотезы, то он относится к положительному классу;−-гипотезу и не содержит ни одной положительнойгипотезы, то он относится к отрицательному классу.417 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииКлассификация с помощью гипотезГипотезы используются для классификации новых объектов.Простейшее решающее правилоПусть g 6∈ {G+ ∪ G− } — новый неопределённый объект.Если его формальное содержаниеg 0 содержит хотя бы одну+-гипотезу и не содержит ни одной отрицательнойгипотезы, то он относится к положительному классу;−-гипотезу и не содержит ни одной положительнойгипотезы, то он относится к отрицательному классу.Отказ от классификации происходит, если g 0 :либо не содержит никаких гипотез (недостаток данных);либо содержит как положительные, так и отрицательныегипотезы (противоречие в данных).417 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииМногозначные контекстыВ АФП предполагается двоичной информации о признаках.Для её получения из количественных и качественных признаковиспользуется процедура шкалирования.Многозначный контекст — это четвёрка (G, M, Z, I), гдеG, M, Z — множества объектов, признаков и значенийпризнаков соответственно,I — тернарное отношение I ⊆ G × M × Z, задающее значениеz ∈ Z признака m ∈ M объекта g ∈ G,причем отображение G × M → Z функционально.418 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииМногозначные контекстыВ АФП предполагается двоичной информации о признаках.Для её получения из количественных и качественных признаковиспользуется процедура шкалирования.Многозначный контекст — это четвёрка (G, M, Z, I), гдеG, M, Z — множества объектов, признаков и значенийпризнаков соответственно,I — тернарное отношение I ⊆ G × M × Z, задающее значениеz ∈ Z признака m ∈ M объекта g ∈ G,причем отображение G × M → Z функционально.Шкалирование — это представление многозначных контекстовдвузначными418 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификации419 / 432Пример «Фрукты»: постановка задачиЗадача:построить классификатор по целевому свойствуz = «являться фруктом» и следующей объектно-признаковойтаблице положительных и отрицательных примеров:№1234567G\Mяблокогрейпфруткивисливакубикяйцотеннисныймячцветжёлтоежёлтыйзелёноесиняязелёныйбелоебелыйжёсткийнетнетнетнетдаданетгладкийданетнетдададанетформакруглоекруглыйовальноеовальнаякубическийовальноекруглыйфрукт++++−−−Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификации420 / 432Пример «Фрукты»: результат шкалированияG\M1234567wy××gbf×××××f×××××××s×s××r××××××××××r×фрукт++++−−−G+ = {1, 2, 3, 4}, G− = {5, 6, 7} ⇒ отношение I+ представленоверхней частью таблицы, а отношение I− — нижней.Признаки означают:w — белый, y — жёлтый, g — зелёный, b — синий;f — твёрдый, f — мягкий, s — гладкий, s — шероховатый;r — круглый, r — некруглый.Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификации421 / 432Пример «Фрукты»: решётка B(K+ ) положительногоконтекста' [(G , {f })'''''''''' [[['''''['''''[[({3, 4}, {f , r})({1, 4}, {f , s})({2, 3}, {f , s})'' ({1,[2}, {f , r,'y})'''[''[[[''[[''[[[[ '''[[ '''[[ '''[[[[[[({3}, {g, f , s, r})({2}, {y, f , s, r})({4}, {b, f , s, r})({1}, {y, f , s, r})'''[''''[[ '''''''[[ '''['[''''+(∅, M )Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПример «Фрукты»: решётка 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 )422 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПример «Фрукты»: формирование гипотезФормальные содержания{f , r} (мягкий, некруглый),{f , r, y} (мягкий, круглый, жёлтый) и{f , s} (мягкий, гладкий) являются +-гипотезами;423 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПример «Фрукты»: формирование гипотезФормальные содержания{f , r} (мягкий, некруглый),{f , r, y} (мягкий, круглый, жёлтый) и{f , s} (мягкий, гладкий) являются +-гипотезами;{f , s} (мягкий, шероховатый) являетсяфальсифицированной +-гипотезой, т.к.

она — частьсодержания {w, f , s, r}отрицательного примера 7 (теннисный мяч);423 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПример «Фрукты»: формирование гипотезФормальные содержания{f , r} (мягкий, некруглый),{f , r, y} (мягкий, круглый, жёлтый) и{f , s} (мягкий, гладкий) являются +-гипотезами;{f , s} (мягкий, шероховатый) являетсяфальсифицированной +-гипотезой, т.к.

она — частьсодержания {w, f , s, r}отрицательного примера 7 (теннисный мяч);{w} (белый) и{f, s, r} (твёрдый, гладкий, некруглый) являются−-гипотезами.423 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПример «Фрукты»: классификацияНеопределённый объект gмирабель будет классифицирован как фрукт , т.к. егоформальное содержание жёлтый, мягкий, гладкий ({y, f , s})содержитположительную гипотезу {f , s} и не содержит ни одной изотрицательных гипотез;424 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПример «Фрукты»: классификацияНеопределённый объект gмирабель будет классифицирован как фрукт , т.к. егоформальное содержание жёлтый, мягкий, гладкий ({y, f , s})содержитположительную гипотезу {f , s} и не содержит ни одной изотрицательных гипотез;кусок сахара со свойствам белый, некруглый, твёрдый будетклассифицирован как не-фрукт ;424 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПример «Фрукты»: классификацияНеопределённый объект gмирабель будет классифицирован как фрукт , т.к.

егоформальное содержание жёлтый, мягкий, гладкий ({y, f , s})содержитположительную гипотезу {f , s} и не содержит ни одной изотрицательных гипотез;кусок сахара со свойствам белый, некруглый, твёрдый будетклассифицирован как не-фрукт ;брикет пломбира со свойствами белый, мягкий, некруглыйвызовет отказ от классификации, поскольку g τ = {w, f , r}содержит как положительную гипотезу {f , r}, так иотрицательную гипотезу {w}.424 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПример «Фрукты»: дополнениеЕсли считать, что теннисный мяч — зелёный, то 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 )425 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПример «Фрукты»: дополнение...При таком изменении свойств объекта № 7 изменятся толькоотрицательный контекст.Теперь{g} = {5, 7}0 является фальсифицированной −-гипотезой,поскольку она содержится в формальном содержании{g, f , s, r} положительного понятия {3}.{f, s, r} = {5, 6}0 является −-гипотезой.426 / 432Прикладная алгебраАлгебраические решёткиПрименение теории решёток к задаче классификацииПример «Фрукты»: дополнение...При таком изменении свойств объекта № 7 изменятся толькоотрицательный контекст.Теперь{g} = {5, 7}0 является фальсифицированной −-гипотезой,поскольку она содержится в формальном содержании{g, f , s, r} положительного понятия {3}.{f, s, r} = {5, 6}0 является −-гипотезой.Поэтомуобъекты со свойствами жёлтый, мягкий, гладкий и белый,мягкий, некруглый будет классифицированы как фрукт;на объекте с единственным свойством белый произойдётотказ от классификации.426 / 432Прикладная алгебраАлгебраические решёткиЧто надо знатьРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.

Коды ХэммингаГрупповые (линейные) коды427 / 432Прикладная алгебраАлгебраические решёткиЧто надо знатьРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств428 / 432Прикладная алгебраАлгебраические решёткиЧто надо знатьРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у.

множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать429 / 432Прикладная алгебраАлгебраические решёткиЧто надо знатьРешёточно упорядоченное множество, алгебраическиерешётки и их эквивалентность.

Характеристики

Список файлов лекций