Досліджується # Р-повна задача знаходження всіх формальних понять заданого формального контексту. Пропонується алгоритм, який на практиці дозволяє вирішувати це завдання за поліноміальний час. Алгоритм заснований на методі «безпечної» декомпозиції формального контексту на частини, названі боксами. При «безпечної» декомпозиції формального контексту на бокси жодне формальне поняття вихідного контексту не губиться і не виникають нові формальні поняття. Процес декомпозиції спрямований на послідовне зменшення розмірів боксів формального контексту і реалізується ітераційно. Встановлено правила зупинки процесу декомпозиції формального контексту на бокси, що гарантують поліноміальний час його роботи: завдання порогового значення на щільність боксів і числа ітерацій розкладання.

Анотація наукової статті з математики, автор наукової роботи - Монгуш Чодураа Михайлівна


Algorithm for "safety" decomposition of the formal context

The # P-complete problem of finding all formal concepts of a given formal context is investigated. An algorithm which we propose, allows in practice to solve this problem in a polynomial time. This algorithm is based on the method of "safety" decomposition of the formal context into parts called boxes. With "safety" decomposition of a formal context into boxes, no formal concept of the original context is lost and no new formal concepts arise. The decomposition process is aimed at consistently reducing the size of the boxes of the formal context and is implemented iteratively. The rules for stopping the process of decomposition of the formal context into boxes, which guarantee the polynomial time of the entire decomposition process, are established: setting the threshold value for the density of boxes and the number of iterations of the decomposition.


Область наук:

  • Математика

  • Рік видавництва: 2019


    Журнал: Прикладна дискретна математика. додаток


    Наукова стаття на тему 'АЛГОРИТМ 'БЕЗПЕЧНОЇ' декомпозиція формально КОНТЕКСТУ'

    Текст наукової роботи на тему «Алгоритм" БЕЗПЕЧНОЇ "декомпозиція формально КОНТЕКСТУ»

    ?6. Бурделєв А. В., Никонов В. Г., Лапиков І. І. Розпізнавання параметрів вузла захисту інформації, реалізованого порогової Ь-значної функцією // Праці СПІІРАН. 2016. №46. С. 108-127.

    7. Анашкина Н. В., Шурупів А. Н. Експериментальне порівняння алгоритмів Балаша і імітації відпалу в задачі розв'язання систем лінійних нерівностей // Прикладна дискретна математика. Додаток. 2014. №7. С. 151-153.

    8. Анашкина Н. В., Шурупів А. Н. Застосування алгоритмів локального пошуку до вирішення систем псевдобулевих лінійних нерівностей // Прикладна дискретна математика. Додаток. 2015. №8. С. 136-138.

    519.7 Б01 10.17223 / 2226308Х / 12/62

    АЛГОРИТМ «безпечної» декомпозиції формально КОНТЕКСТУ

    Ч. М. Монгуш

    Досліджується # Р-повна задача знаходження всіх формальних понять заданого формального контексту. Пропонується алгоритм, який на практиці дозволяє вирішувати це завдання за поліноміальний час. Алгоритм заснований на методі «безпечної» декомпозиції формального контексту на частини, названі боксами. При «безпечної» декомпозиції формального контексту на бокси жодне формальне поняття вихідного контексту не губиться і не виникають нові формальні поняття. Процес декомпозиції спрямований на послідовне зменшення розмірів боксів формального контексту і реалізується ітераційно. Встановлено правила зупинки процесу декомпозиції формального контексту на бокси, що гарантують поліноміальний час його роботи: завдання порогового значення на щільність боксів і числа ітерацій розкладання.

    Ключові слова: формальний контекст, формальне поняття, декомпозиція формального контексту, алгоритм декомпозиції.

    Вступ

    Об'єктно-признаковая таблиця - модель представлення даних деякої предметної області, в якій кожен стовпець відповідає певною ознакою, а кожен рядок визначає признаковая опис окремого об'єкта. Така модель часто використовується при вирішенні прикладних задач в інтелектуальному аналізі даних, в тому числі в аналізі формальних понять.

    Аналіз формальнийх понять (АФП) - прикладна галузь алгебраїчної теорії решіток Г. Біркгофа [1]. Основні ідеї АФП були сформульовані на початку 80-х років XX століття в роботах Р. Віллі і Б. Гантера і розвинені в дослідженнях С. О. Кузнєцова, С. А. Об'єдкова, Д. І. Ігнатова [2-4]. В рамках АФП об'єктно-признаковая таблиця представляється формальним контекстом, що відображає наявність або відсутність ознак, характерних для досліджуваного безлічі об'єктів, і моделюється 0,1-матрицею. У АФП формальні поняття визначаються за допомогою відповідностей Галуа і являють собою пари множин виду (обсяг, зміст).

    В даний час застосування методів АФП обмежується високою трудомісткістю процесу знаходження всіх формальних понять заданого формального контексту. У даній роботі пропонується алгоритм, який на практиці дозволяє розкласти цю задачу на підзадачі (зменшені копії початкового завдання) за поліноміальний час.

    1. Основні положення аналізу формальних понять

    Наведемо основні положення і позначення АФП [2, 3]. Нехай для предметної області визначені два непустих кінцевих безлічі О і М об'єктів і ознак (або властивостей) і задано непорожнє відношення інцидентності I З Про х М. Дане відношення містить інформацію про здійсненності властивостей з М на об'єктах з О, тобто (Д, т) € I означає, що об'єкт д має ознаку т, і навпаки - ознака т притаманний об'єкту д. Трійку К = (О, М, I) прийнято називати формальним контекстом.

    Будемо вважати, що множини О і М лінійно впорядковані (наприклад, лексикографічно). В цьому випадку формальний контекст К = (О, М, I) однозначно задається 0,1-матрицею Т = (? У):? У = 0 при (д ^, ту) Е I і? У = 1 при (д ^ , mj) € I (r = 1, 2, ..., | Про |; ^ = 1, 2, ..., | М |).

    Виберемо в К = (О, М, I) два довільних підмножини А З О і В С М і

    визначимо для них відображення (•) 'Галуа: А' = П д ', В' = П т ', де д' = {т € М:

    ^ Еа ТЕВ

    (Д, т) € I}; т '= {д € Про: (д, т) € I}. Згідно з цим визначенням, безліч А '- набір ознак, притаманних об'єктам з А, а безліч В' задає сімейство об'єктів, що володіють ознаками з В. Подвійне застосування (|) 'визначає оператор замикання (|)' 'на 2м в алгебраїчному сенсі. Безліч (В) '' можна трактувати як набір ознак, які незмінно з'являються в об'єктах формального контексту К = (О, М, I) разом з ознаками з В, причому це безліч є найбільшим по включенню в межах цього формального контексту. Якщо В = В '', то В називається замкнутим безліччю щодо оператора (|) ''.

    Пара множин (А, В), таких, що А З О, В С М, А '= В і В' = А, називається формальним поняттям формального контексту К = (О, М, I) з об'ємом А і змістом В. далі для стислості в ряді випадків визначення «формальний» перед словами «контекст» або «поняття» будемо опускати. Пара множин (А, В) є формальним поняттям тоді і тільки тоді, коли А = А '' і В = В ''. Очевидно, що будь-яке формальне поняття унікально в заданому контексті, т. Е. Відрізняється від інших формальних понять об'ємом та / або змістом. Якщо формальний контекст представлений 0,1-матрицею Т, то при А = 0 і В = 0 формальному поняттю (А, В) відповідає максимальна повна подматріца матриці Т.

    Позначимо через ^ З безліч всіх формальних понять формального контексту К = (О, М, I). Нехай (А1, В1), (А2, В2) € ^ С. Безліч ^ З частково впорядковано ставленням (А1, В1)? (А2, В2) ^ А1 С А2. Відзначимо, що останнім еквівалентно умові В2 С В1. Кожне формальне поняття (А, В) € ^ З визначає для досліджуваної предметної області сукупність однорідних об'єктів А зі своїм специфічним набором ознак В. Якщо (О, 0) € ^ С, (0, М) € ^ С, то формальні поняття ( О, 0), (0, М) називаються тривіальними.

    Визначимо на ^ З операції перетину П і об'єднання і через однойменні теоретико-множинні операції П і і в такий спосіб:

    (А1, В1) П (А2, В2) = (А1 П А2, (А1 П А2) '), (А1, В1) і (А2, В2) = ((В1 П В2)', В1 П В2).

    Тоді (^ С,?) Утворює повну решітку Ь = (^ С, П, і), звану в АФП гратами формальних понять контексту К = (О, М, I).

    2. Постановка завдання і метод «безпечної» декомпозиції

    В рамках АФП завдання знаходження всіх формальних понять формулюється в такий спосіб. Заданий формальний контексту К = (О, М, I). Потрібно для До най-

    ти безліч ^ С. На сьогоднішній день для визначення безлічі ^ З розроблено багато алгоритмів, в їх числі №х1С1озіге, С1ояе-Ьу-Опе, Иотв [3, 4]. Час їх виконання в гіршому випадку становить О (| ^ З | | | Про | 2 | | М |). Оскільки величина | ^ З | може експоненціально залежати від | Про | і | М |, час виконання даних алгоритмів також може бути експоненціальним. Підвищити продуктивність можна шляхом застосування методу «безпечної» декомпозиції формального контексту на бокси [5].

    Нехай д € О і т € М - довільні елементи контексту К = (О, М, I). Пари множин (д ", д ') і (т', т") утворюють формальні поняття, перше з яких назвемо об'єктним, а друге - признаковая формальним поняттям контексту К = (О, М, I). Позначимо через О = {(д '', д '): д € Про} З ^ З безліч всіх об'єктних формальних понять і через Б = {(т', т ''): т € М} З ^ З - безліч всіх прізнакових формальних понять контексту К = (О, М, I).

    Пара формальних понять (д '', д ') € О, (т', т '') € Б визначає бокс ш = (т ', д', 3) контексту К = (О, М, I), якщо ( д '', д ') Е (т', т ''), що еквівалентно д '' С т '(або т' 'З д'). Про такий бокс будемо говорити, що він утворений елементами д € О і т € М. Далі замість ш = (т ', д', 3) будемо коротко писати ш = (т ', д') або (т ', д' ).

    Затвердження 1 [6]. Для будь-якого формального контексту К = (О, М, I) і будь-яких (д '', д ') € О, (т', т '') € Б відношення порядку (д '', д ') Е (т' , т '') виконується тоді і тільки тоді, коли (д, т) € I.

    Затвердження 1 встановлює оцінку числа боксів, одержуваних на кожній ітерації розкладання: число різних боксів, породжуваних різноманітними елементами контексту К = (О, М, I), не перевищує ваги 0,1-матриці Т, т. Е. Величини || Т | | число одиничних елементів цієї матриці. Очевидно, що 1 ^ || Т || ^ | Про | | | М |.

    Будемо говорити, що формальне поняття (А, В) € ^ З вкладено в бокс (т ', д') контексту К = (О, М, I), і записувати (А, В) ^ (т ', д') , якщо А С т ', В С д'. Всякий бокс (т ', д') не є порожнім, оскільки, згідно з визначенням боксу, він завжди містить формальні поняття (д '', д ') € О і (т', т '') € Б.

    Затвердження 2 [6]. Будь-яке нетривіальне формальне поняття (А, В) контексту К = (О, М, I), яке вкладено в бокс (т ', д'), утворений елементами д € О і т € М, містить ці елементи і їх замикання, т . е. якщо (А, В) ^ (т ', д'), то д € А і т € В; д '' З А і т '' З У.

    Відповідно до твердження 2, пару (д '', т '') можна розглядати в якості типового представника не тільки боксу (т ', д'), але і всіх формальних понять контексту К = (О, М, I), вкладених в цей бокс. Перехід від боксів до їх типових представників в більшості випадків зменшує на практиці час виконання алгоритмів знаходження всіх формальних понять для заданого формального контексту. Відповідність між боксами і формальними поняттями контексту встановлює наступна теорема.

    Теорема 1 [6]. Для будь-якого формального контексту К = (О, М, I), безлічі ^ З усіх його формальних понять і будь-якої пари множин (А, В), 0 = А С О, 0 = В С М, справедливо:

    1) якщо (А, В) € ^ С, то в До існує бокс ш = (т ', д'), д € О і т € М, можливо, не єдиний, в який це формальне поняття вкладено;

    2) якщо (А, В) - формальне поняття деякого боксу ш = (т ', д') формального контексту К, то воно також належить ^ З.

    Згідно з теоремою 1, розкладання контексту K = (G, M, I) на бокси є «безпечним» для будь-якого формального поняття з FC [5]. Очевидно, що процес розкладання заданого контексту на бокси може бути організований ітераційно, оскільки кожен виявлений на першій ітерації бокс можна розглядати в якості вихідного контексту і знову піддавати декомпозиції. Визначимо складність процесу розкладання і правила його зупинки. Нехай | m '| • | g '| -розмір боксу (m ', g'), а IKm ^ g ')!) число його одиничних елементів. Щільністю боксу (m ', g') назвемо величину а (m ', g') = || (m ', g /) | / (| m / | • | g' |). Вірні природні межі 0 < а (m ', g') ^ 1.

    Затвердження 3 [6]. Всякий бокс (m ', g') з щільністю a (m ', g') = 1 містить рівно одне нетривіальне формальне поняття (A, B) контексту K = (G, M, I), що збігається з ним, т. Е . A = m 'і B = g'.

    З твердження 3 слід, що бокс (m ', g') з щільністю 1 вироджується в нетривіальне формальне поняття і не підлягає подальшому розкладанню. Зауважимо, що час формування одного боксу для формального контексту K = (G, M, I) становить O (| G | • | M |). В цілому, час, необхідний на одноразове розкладання цього контексту на бокси, в гіршому випадку становить O (а (G, M) | G | 2 • | Mг).

    3. Алгоритм «безпечної» декомпозиції формального контексту на бокси

    Алгоритм FindBoxes (алгоритм 1) реалізує метод «безпечної» декомпозиції формального контексту на бокси. Теоретичним обґрунтуванням цього алгоритму є теорема 1 і затвердження 1-3, вхідними даними служать вихідний контекст K = (G, M, I) і ціле позитивне число k - число ітерацій. Результат роботи алгоритму FindBoxes: П - безліч боксів і H - безліч типових представників боксів, що входять в П.

    Алгоритм FindBoxes включає наступні основні процедури: Boxes, Delete, SearchChains. Процедура Boxes розкладає заданий бокс ш, щільність якого відмінна від 1, на більш дрібні бокси і знаходить для них типових представників. Процедура Delete видаляє кратні бокси і бокси, збігаються з вихідним. Процедура SearchChains виявляє вкладені бокси, виконує побудова взаємно непересічних ланцюгів частково впорядкованої множини боксів П і знаходить для цих ланцюгів максимальні елементи. Дана процедура дозволяє зменшувати число боксів, одержуваних на кожній ітерації розкладання.

    Якщо число ітерацій процесу декомпозиції одно k, то розкладання можна здійснити за час про (| G | 2k • | M | 2fc); при k = 1 алгоритм FindBoxes виконується за

    час 0 (| G | 2 • | M | 2). Для додаткового обмеження числа частин, одержуваних на кожній ітерації, можна встановлювати порогове значення на щільність боксів, які підлягають подальшому розкладанню. Це досягається заміною на кроці 8 алгоритму FindBoxes умови а (ш) = 1 умовою а (ш) < ат, де ат - порогове значення щільності боксів, які підлягає подальшому розкладанню.

    Для оцінки результативності алгоритму FindBoxes проведені обчислювальні експерименти при k = 1 і без завдання обмеження на щільність боксів. Експерименти проводилися за допомогою програми FCACorpus [7], що здійснює знаходження всіх формальних понять. Використовувалися контексти, згенеровані випадковим чином. Для кожного контексту K = (G, M, I) здійснювалося знаходження безлічі FC всіх формальних понять без розбивки на бокси і з ітеративним розбивкою на бокси. Аналізувалися два випадки при перевірці вкладеності боксів: випадок 1-перевірка проводиться без типових представників боксів, випадок 2 -

    Алгоритм 1. FindBoxes

    Вхід: вихідний контекст K = (G, M, I), k - кількість ітерацій. Вихід: П - безліч боксів, H - безліч типових представників боксів з П.

    1: Hi: = (G, M, I) // безліч боксів, які підлягають подальшому розкладанню 2: П2: = 0 // безліч боксів, що не підлягають подальшому розкладанню 3: H1: = (G ", M") // безліч типових представників боксів, що входять в П1 4: H2: = 0 // безліч типових представників боксів, що входять в П2 5: Поки (k = 0 & Hi = 0) 6: Q: = 0, V: = 0. 7: Для всіх ш? П1 8: Якщо а (ш) = 1, то 9: Boxes (w, X, Y); Q: = Q U

    10: інакше

    11: П2: = П2 U ш; H2: = H2 U

    12: W1: = Q; H1: = R; Delete (П1 13: Якщо П1 = 0 то 14: SearchChains (n1, H1). 15: k: = k - 1. 16: П: = П1 U П2; H: = H1 U H2.

    за допомогою типових представників. Результати експерименту наведені в таблиці, де N - кількість освічених боксів; | FC | число знайдених формальних понять; t - час виконання програми. Експерименти виконувалися на комп'ютері з процесором Intel Core i7-720QM Processor (6M Cache, 1,60 ГГц) і ОЗУ розміром 4 Гбайт.

    Оцінка ефективності процесу декомпозиції формального контексту

    Випадки Характеристика вихідної контексту Результати

    | G | | M | IIT у a (G, M) N IFC | t, мс

    Без розкладання на бокси З розкладанням на бокси (випадок 1) З розкладанням на бокси (випадок 2) 100 20 1000 0,5 883 883 4962 4962 4962 145125 2878 2200

    Без розкладання на бокси З розкладанням на бокси (випадок 1) З розкладанням на бокси (випадок 2) 200 30 2940 0,49 2895 2895 10567 10567 10567 794520 97906 90908

    З таблиці видно, що значення | у випадках без розкладання і з розкладанням на бокси повністю збігаються; число боксів, утворених при розкладанні контексту, не перевищує величини || Т ||; алгоритм Е1 ^ Вохез дає значний виграш за часом: час виконання програми ЕСАСогріз при розкладанні контексту на бокси зменшується в кілька разів.

    висновок

    Представлений алгоритм Е1 ^ Вохез реалізує метод «безпечної» декомпозиції формального контексту і на практиці дозволяє розкласти завдання знаходження всіх формальних понять на підзадачі за поліноміальний час. Алгоритм також примі-

    X; R: = R U Y, H1.

    U П2, H1 U H2).

    ним для прискорення існуючих алгоритмів вирішення родинних завдань, пов'язаних з перебуванням максимальних повних підматриць 0,1-матриці.

    ЛІТЕРАТУРА

    1. Біркгоф Г. Теорія решіток. М .: Наука, 1984. 568с.

    2. Ganter B. and Wille R. Formal Concept Analyses: Mathematical Foundations. Springer Science and Business Media, 2012. 314 p.

    3. Ganter B. and Obiedkov S. A. Conceptual Exploration. Berlin; Heidelberg: Springer, 2016. 315 p.

    4. Kuznetsov S. O. and Obiedkov S. A. Comparing performance of algorithms for generating concept lattices // J. Exper. Theor. Artificial Intelligence. 2002. V. 14. No. 2. P. 189-216.

    5. Mongush Ch. M. and Bykova V. V. On decomposition of a binary context without losing formal concepts // J. Siberian Federal University. Mathematics and Physics. 2019. No. 3. P. 323-330.

    6. Бикова В. В., Монгуш Ч. М. Декомпозиційні підхід до дослідження формальних контекстів // Прикладна дискретна математика. 2019. №.44. С. 111-124.

    7. Монгуш Ч. М., Бикова В. В. Програма FCACorpus концептуального моделювання тувинських текстів методами аналізу формальних понять. Свід. про держ. реєстрації програми для ЕОМ № 2018618907, видано Федеральною службою з інтелектуальної власності РФ, 2018.

    519.7 DOI 10.17223 / 2226308X / 12/63

    ПРО ВИКОРИСТАННЯ ТЕХНОЛОГІЙ МАШИННОГО НАВЧАННЯ ДЛЯ ПЕРЕВІРКИ СТАТИСТИЧНИХ ВЛАСТИВОСТЕЙ симетрично КРИПТОГРАФІЧНИХ АЛГОРИТМІВ

    А. А. Перов

    Розглядається застосування технологій машинного навчання до завдань криптографії, зокрема проведення статистичного аналізу блокових шифрів. Викладена ідея адаптації шифртекст до алгоритму моделі нейронної мережі Inception V3. Наведено результати експериментів.

    Ключові слова: криптографія, машинне обучно, статистичний аналіз, раунд шифрування, ітеративні блокові шифри.

    Вступ

    Традиційно статистичний аналіз проводиться за допомогою тестів, що визначають ступінь випадковості вихідний послідовності [1] із застосуванням методів математичної статистики. Дослідження показують, що сучасні ітеративні алгоритми шифрування забезпечують задовільні статистичні властивості на меншому, ніж повне, зокрема раундів. Використання технологій машинного навчання для вирішення подібних завдань є новим напрямком. Для розробки методики проведення статистичного аналізу була використана нейронна мережа Inception v3, зазвичай застосовується для розпізнавання і класифікації графічних образів. Inception v3 є свёрточной нейронною мережею, що складається з 17 шарів, навченої на великій кількості зображень з бази ImageNet.

    1. Перетворення шифртекст

    Для вирішення завдання з навчання нейронної мережі для статистичного аналізу виконано перетворення зашифрованих повідомлень в формат графічних изображе-


    Ключові слова: ФОРМАЛЬНИЙ КОНТЕКСТ /формальне поняття /Декомпозиція формально КОНТЕКСТУ /АЛГОРИТМ декомпозиції /FORMAL CONTEXT /FORMAL CONCEPT /DECOMPOSITION OF FORMAL CONTEXT /ALGORITHM OF DECOMPOSITION

    Завантажити оригінал статті:

    Завантажити