Спосіб двокласової класифікації об’єктів на основі негативного відбору детекторів

Реферат: Спосіб двокласової класифікації об'єктів на основі негативного відбору детекторів полягає в тому, що задають охарактеризовану набором бінарних ознак навчальну вибірку екземплярів лише першого класу. Автоматично маскують біти, які відповідають ознакам з низькою значимістю та виключають їх з визначення продукційних правил. UA 72095 U (12) UA 72095 U UA 72095 U 5 10 15 20 25 30 35 40 45 50 55 60 Корисна модель належить до кібернетики й обчислювальної техніки і може бути використана для побудови і навчання моделі негативного відбору детекторів для проведення двокласової класифікації об'єктів. Процесом як об'єктом технології корисної моделі є сукупність дій з вимірювання параметрів (ознак) об'єктів, які класифікуються, перетворення даних про об'єкти для формування структури та визначення параметрів функціональних вузлів, а також керування процесом побудови моделі негативного відбору детекторів з метою автоматизації класифікації об'єктів. Продуктами, щодо яких у корисній моделі виконуються дії, є дані про значення параметрів об'єктів, що класифікуються. Продуктом, за допомогою якого у корисній моделі виконуються дії, є електроннообчислювальна машина (ЕОМ). Відомий спосіб двокласової класифікації об'єктів на основі негативного відбору детекторів [1], прийнятий за найближчий аналог, який полягає в тому, що детекторам задають охарактеризовану набором бінарних ознак навчальну вибірку екземплярів лише першого класу, формують набір поданих бінарними рядками кандидатів в детектори, визначають критерій відбору детекторів, формують набір детекторів, відбираючи кандидати в детектори за визначеним критерієм, формують набір продукційних правил на основі значень бітів детекторів з набору, невідомий екземпляр відносять до першого класу, якщо він не належить області детекторів, або до другого - якщо належить. Недоліками відомого способу є те, що він характеризується низькою швидкістю процесу класифікації об'єктів за рахунок того, що вимагає формування великої кількості кандидатів в детектори, щоб в результаті відбору за критерієм отримати необхідний набір детекторів, практично є доцільним для задач з невеликою кількістю ознак, не має узагальнюючих властивостей, оскільки передбачає повне відображення навчальної вибірки у структурі моделі, і як наслідок ставить високі вимоги до обчислювальних ресурсів та пам'яті ЕОМ. В основу корисної моделі поставлено задачу створення способу двокласової класифікації об'єктів на основі негативного відбору детекторів з метою підвищення швидкості процесу двокласової класифікації об'єктів за рахунок автоматизації побудови та навчання моделі негативного відбору детекторів. Поставлена задача вирішується тим, що у способі двокласової класифікації об'єктів на основі негативного відбору детекторів задають охарактеризовану набором бінарних ознак навчальну вибірку екземплярів лише першого класу, формують набір поданих бінарними рядками кандидатів в детектори, визначають критерій відбору детекторів, формують набір детекторів, відбираючи кандидати в детектори за визначеним критерієм, формують набір продукційних правил на основі значень бітів детекторів з набору, невідомий екземпляр відносять до першого класу, якщо він не належить області детекторів, або до другого - якщо належить. При цьому при формуванні кожного кандидата в детектори автоматично маскують біти, які відповідають ознакам з низькою значимістю та виключають їх з визначення продукційних правил. У порівнянні з найближчим аналогом відмінними ознаками є маскування незначимих ознак при визначеній комбінації відомих ознак у кандидата в детектори. Це дозволяє автоматично скоротити кількість елементів у визначеннях продукційних правил, що підвищує швидкість процесу класифікації об'єктів. У технічному рішенні, що заявляється, нові ознаки при взаємодії з відомими дають новий технічний результат, що дозволяє вирішити поставлену задачу. Спосіб двокласової класифікації об'єктів на основі негативного відбору детекторів працює наступним чином. Спочатку формують навчальну вибірку S екземплярів першого класу, які характеризуються n бінарними ознаками {0, 1}, для чого задають набір ознак, для якого кодують наявність чи відсутність ознак, що характеризують стан екземплярів, значеннями "1" та "0", відповідно: S={sij} де i=1, 2, ..., n, j=1, 2, ..., m, sij - значення i-ї ознаки j-го екземпляра навчальної вибірки, m - кількість екземплярів у навчальній вибірці. Задану навчальну вибірку екземплярів вводять до пам'яті ЕОМ. У пам'яті ЕОМ виділяють блок для зберігання набору детекторів D у вигляді масиву даних та n створюють замаскований кандидат в детектори d={Z} , що подають бінарним рядком, де Z символ маски, який відповідає будь-якому значенню біта {0, 1} у бінарному рядку. Далі для кожного екземпляра s з навчальної вибірки визначають його відповідність кандидату в детектори d за наступним критерієм: 1 UA 72095 U  n , 1 1   | di  Z  di  si   n matchd, s   i 1  0, у протилежному випадку. 5 10 15 20 Якщо s  S : matchd, s  0 , тоді кандидат в детектор d заносять до набору детекторів D  D  d, у протилежному випадку, коли існує принаймні один екземпляр з навчальної вибірки, якому відповідає кандидат в детектори d, випадковим чином вибирають його замаскований біт di=Z. До пам'яті ЕОМ записують інвертоване значення обраного біта: di=si. Після цього повторно здійснюють порівняння кандидата в детектори d з кожним із екземплярів навчальної вибірки s S . У тому разі, якщо у кандидата в детектори не залишилося жодного замаскованого біта, його видаляють з пам'яті та здійснюють генерацію нового замаскованого кандидата. В результаті отримують набір детекторів, які містять в своєму складі незамаскованими лише ті ознаки, які є значимими для класифікації об'єктів. Це також дозволяє зберігати у пам'яті ЕОМ лише значення незамаскованих бітів у детекторах. На основі сформованого набору детекторів отримують продукційні правила виду "якщо-то" таким чином, що усі незамасковані біти детектора входять до визначення правила. Використання запропонованого способу дозволяє проводити побудову і навчання моделі негативного відбору детекторів для проведення двокласової класифікації об'єктів. На основі запропонованого способу здійснювалася побудова моделі негативного відбору детекторів для вирішення завдання медичного діагностування повторних респіраторних захворювань у дітей. Вибірка складалася зі 197 екземплярів, що характеризувалися 42 бінарними ознаками про наявність або відсутність певних захворювань у дитини та її батьків. Фрагмент вибірки наведено у табл. 1. Таблиця 1 Значення ознак для екземплярів № 1 2 3 4 5 … 196 197 x1 1 1 1 0 0 … 1 0 х2 1 0 0 0 0 … 0 0 x3 0 0 0 0 0 … 0 0 x4 0 1 1 1 1 … 1 1 x5 0 0 0 0 0 … 0 0 x6 0 0 0 0 0 … 1 0 x7 1 1 1 1 1 … 0 1 x8 1 1 1 0 0 … 1 1 x9 0 0 0 0 0 … 0 1 x10 0 0 0 1 1 … 0 0 ... ... ... … … … … … … x39 1 0 0 1 0 … 1 0 x40 0 1 1 0 0 … 0 1 x41 0 0 0 0 1 … 0 0 x42 0 0 0 0 0 … 0 0 у 1 1 0 1 0 … 0 0 25 30 На основі даних про екземпляри навчальної вибірки було побудовано модель негативного відбору детекторів у вигляді набору продукційних правил з використанням запропонованого способу та з використанням найближчого аналогу. В табл. 2 наведено фрагмент моделі негативного відбору детекторів, де кожний рядок описує один детектор, символом "*" позначено замаскований біт детектора. 2 UA 72095 U Таблиця 2 Значення бітів детекторів № 1 2 3 4 5 ... 27 28 5 10 15 x1 0 1 1 0 1 ... * 0 x2 0 * * * * ... * * x3 * * 0 * * ... 0 * x4 * * * 1 * ... * * x5 * * * * * ... 0 * x6 * * * * 1 ... * * x7 * 1 * * * ... * * x8 * * * * * ... * * x9 * * * * * ... * * x10 * * * * * ... * 0 ... ... ... ... ... ... ... ... ... x39 * * * * * ... * * x40 1 * * * * ... * 1 x41 * * * * * ... * * x42 * * * * * ... * * Вирішення цього завдання запропонованим способом дозволило визначити схильність пацієнтів до повторних респіраторних захворювань з точністю 97 % (при використанні найближчого аналога - 81 %), для чого було сформовано всього 28 детекторів (при використанні найближчого аналогу - 42 детектори) і на їх основі отримано набір продукційних правил для двокласової класифікації об'єктів, що зменшує затрати пам'яті та машинного часу ЕОМ. Технічним результатом внаслідок використання запропонованого способу є: - підвищення швидкості процесу двокласової класифікації об'єктів за рахунок того, що непридатні детектори не вилучаються з моделі негативного відбору, а проходять стадію донавчання, і як наслідок, скорочується час на генерацію нових детекторів; - скорочення затрат пам'яті для проведення двокласової класифікації об'єктів за рахунок вилучення з кінцевого набору продукційних правил незначимих замаскованих бітів. Література: 1. Forrest S, Self-nonself discrimination in a computer / S. Forrest, A.S. Perelson, L. Allen, R. Cherukuri // Research in Security and Privacy: IEEE Computer Society Symposium, 16-18 May 1994, Oakland: proceedings. - Los Alamitos: IEEE Computer Society Press, 1994. - P. 202-212. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 20 25 Спосіб двокласової класифікації об'єктів на основі негативного відбору детекторів, який полягає в тому, що задають охарактеризовану набором бінарних ознак навчальну вибірку екземплярів лише першого класу, формують набір поданих бінарними рядками кандидатів в детектори, визначають критерій відбору детекторів, формують набір детекторів, відбираючи кандидати в детектори за визначеним критерієм, формують набір продукційних правил на основі значень бітів детекторів з набору, невідомий екземпляр відносять до першого класу, якщо він не належить області детекторів, або до другого - якщо належить, який відрізняється тим, що при формуванні кожного кандидата в детектори автоматично маскують біти, які відповідають ознакам з низькою значимістю та виключають їх з визначення продукційних правил. 30 Комп’ютерна верстка В. Мацело Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 3