Комбінаторна оцінка впливу зменшення інформаційного покриття класів на узагальнюючу властивість 1NN алгоритмів класифікації

У статті запропоновано комбінаторний підхід до визначення впливу зменшення розмірності класів на ймовірність правильного розпізнавання при застосуванні 1NN вирішуючого правила. Результати розпізнавання для кожного контрольного об’єкта вважаються відомими до пониження розмірів класів бази даних. Р...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2008
Hauptverfasser:	Капустій, Б.О., Русин, Б.П., Таянов, В.А.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут проблем штучного інтелекту МОН України та НАН України 2008
Schlagworte:	Алгоритмическое и программное обеспечение интеллектуальных систем
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/6543
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Комбінаторна оцінка впливу зменшення інформаційного покриття класів на узагальнюючу властивість 1NN алгоритмів класифікації / Б.О. Капустій, Б.П. Русин, В.А. Таянов // Штучний інтелект. — 2008. — № 1. — С. 49-54. — Бібліогр.: 11 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-6543
record_format	dspace
spelling	irk-123456789-65432010-03-10T12:01:41Z Комбінаторна оцінка впливу зменшення інформаційного покриття класів на узагальнюючу властивість 1NN алгоритмів класифікації Капустій, Б.О. Русин, Б.П. Таянов, В.А. Алгоритмическое и программное обеспечение интеллектуальных систем У статті запропоновано комбінаторний підхід до визначення впливу зменшення розмірності класів на ймовірність правильного розпізнавання при застосуванні 1NN вирішуючого правила. Результати розпізнавання для кожного контрольного об’єкта вважаються відомими до пониження розмірів класів бази даних. Розв’язано задачу визначення ймовірності того, що правильне розпізнавання збережеться після пониження розмірності класів, а неправильне стане правильним. В работе предложен комбинаторный подход к определению влияния уменьшения размерности классов на вероятность правильного распознавания при использовании 1NN решающего правила. Результаты распознавания для каждого контрольного объекта считаются известными до понижения размеров классов базы данных. Решена задача определения вероятности того, что правильное распознавание сохранится после понижения размерности классов, а неправильное станет правильным. In this paper the combinatorial approach for definition of the class size reduction influence on correct recognition probability when one uses 1NN classifier. The recognition results are familiar before database class size reduction for every test object. The probability that recognition system has peculiarity to retain the recognition rate after class size reduction has been determined. The probability definition task that negative recognition results after class size reduction will become positive has also been solved. 2008 Article Комбінаторна оцінка впливу зменшення інформаційного покриття класів на узагальнюючу властивість 1NN алгоритмів класифікації / Б.О. Капустій, Б.П. Русин, В.А. Таянов // Штучний інтелект. — 2008. — № 1. — С. 49-54. — Бібліогр.: 11 назв. — укр. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/6543 004.93+519.2 uk Інститут проблем штучного інтелекту МОН України та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Алгоритмическое и программное обеспечение интеллектуальных систем Алгоритмическое и программное обеспечение интеллектуальных систем
spellingShingle	Алгоритмическое и программное обеспечение интеллектуальных систем Алгоритмическое и программное обеспечение интеллектуальных систем Капустій, Б.О. Русин, Б.П. Таянов, В.А. Комбінаторна оцінка впливу зменшення інформаційного покриття класів на узагальнюючу властивість 1NN алгоритмів класифікації
description	У статті запропоновано комбінаторний підхід до визначення впливу зменшення розмірності класів на ймовірність правильного розпізнавання при застосуванні 1NN вирішуючого правила. Результати розпізнавання для кожного контрольного об’єкта вважаються відомими до пониження розмірів класів бази даних. Розв’язано задачу визначення ймовірності того, що правильне розпізнавання збережеться після пониження розмірності класів, а неправильне стане правильним.
format	Article
author	Капустій, Б.О. Русин, Б.П. Таянов, В.А.
author_facet	Капустій, Б.О. Русин, Б.П. Таянов, В.А.
author_sort	Капустій, Б.О.
title	Комбінаторна оцінка впливу зменшення інформаційного покриття класів на узагальнюючу властивість 1NN алгоритмів класифікації
title_short	Комбінаторна оцінка впливу зменшення інформаційного покриття класів на узагальнюючу властивість 1NN алгоритмів класифікації
title_full	Комбінаторна оцінка впливу зменшення інформаційного покриття класів на узагальнюючу властивість 1NN алгоритмів класифікації
title_fullStr	Комбінаторна оцінка впливу зменшення інформаційного покриття класів на узагальнюючу властивість 1NN алгоритмів класифікації
title_full_unstemmed	Комбінаторна оцінка впливу зменшення інформаційного покриття класів на узагальнюючу властивість 1NN алгоритмів класифікації
title_sort	комбінаторна оцінка впливу зменшення інформаційного покриття класів на узагальнюючу властивість 1nn алгоритмів класифікації
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
publishDate	2008
topic_facet	Алгоритмическое и программное обеспечение интеллектуальных систем
url	http://dspace.nbuv.gov.ua/handle/123456789/6543
citation_txt	Комбінаторна оцінка впливу зменшення інформаційного покриття класів на узагальнюючу властивість 1NN алгоритмів класифікації / Б.О. Капустій, Б.П. Русин, В.А. Таянов // Штучний інтелект. — 2008. — № 1. — С. 49-54. — Бібліогр.: 11 назв. — укр.
work_keys_str_mv	AT kapustíjbo kombínatornaocínkavplivuzmenšennâínformacíjnogopokrittâklasívnauzagalʹnûûčuvlastivístʹ1nnalgoritmívklasifíkacíí AT rusinbp kombínatornaocínkavplivuzmenšennâínformacíjnogopokrittâklasívnauzagalʹnûûčuvlastivístʹ1nnalgoritmívklasifíkacíí AT taânovva kombínatornaocínkavplivuzmenšennâínformacíjnogopokrittâklasívnauzagalʹnûûčuvlastivístʹ1nnalgoritmívklasifíkacíí
first_indexed	2025-07-02T09:26:51Z
last_indexed	2025-07-02T09:26:51Z
_version_	1836526770001543168
fulltext	«Штучний інтелект» 1’2008 49 1К УДК 004.93+519.2 Б.О. Капустій1, Б.П. Русин2, В.А. Таянов2 1Національний університет “Львівська політехніка”, м. Львів, Україна 2Фізико-механічний інститут ім. Г.В. Карпенка НАН України, м. Львів, Україна rusyn@ipm.lviv.ua, vtayanov@ipm.lviv.ua Комбінаторна оцінка впливу зменшення інформаційного покриття класів на узагальнюючу властивість 1NN алгоритмів класифікації У статті запропоновано комбінаторний підхід до визначення впливу зменшення розмірності класів на ймовірність правильного розпізнавання при застосуванні 1NN вирішуючого правила. Результати розпізнавання для кожного контрольного об’єкта вважаються відомими до пониження розмірів класів бази даних. Розв’язано задачу визначення ймовірності того, що правильне розпізнавання збережеться після пониження розмірності класів, а неправильне стане правильним. Вступ У процесі розв’язування задач розпізнавання, а також при розробці відповідних алгоритмів доцільно зменшувати складність математичних моделей алгоритмів розпізнавання з метою досягнення більшої ефективності при застосуванні цих алгоритмів на практиці. Такого можна досягти шляхом вибору підмножини найбільш інформативних ознак, застосування більш простих класифікаторів, а також зменшення розмірності класів еталонів. На сьогоднішній день проблема вибору найбільш інформативних ознак порівняно добре досліджена [1-4]. Суть селекції найбільш інформативних ознак полягає у застосуванні певного критерію, який повинен максимізувати (мінімізувати) певний показник при використанні навчаючої вибірки. Задача екстремалізації показника критерію вирішується на основі узагальненого ковзаючого контролю (cross-validation test) [5-7], який продовжує вдосконалюватися у даний час. Досліджуються також підходи, які враховують вплив кожної ознаки на внутрішню композицію алгоритму, що дає змогу більш ефективно визначати вплив сукупності ознак на узагальнюючу властивість алгоритмів розпізнавання [2]. Надалі буде розглянута задача розпізнавання з класами, що попарно не перетинаються, а процес навчання здійснюватиметься на основі прецедентної інформації [8]. У подібних випадках часто застосовують класифікатори на основі функції відстані (метричні класифікатори). В загальному ними є kNN класифікатори, зважені kNN класифікатори та класифікатори з використанням потенційних функцій [9]. Ці класифікатори більш прості і швидкісні порівняно з іншими. Сумісна процедура оптимізації метрики та найбільш інформативного набору ознак досліджена на основі різних критеріїв в [10], [11], а в [11] розроблено підхід для порівняння 1NN та kNN класифікаторів. В [10] на основі послідовного аналізу запропоновано підхід до визначення мінімального розміру класу, що забезпечує задані помилки класифікації 1-го та 2-го родів. Необхідно відзначити, що дослідження, на які орієнтована дана робота, стосується здебільшого біометричних СР, хоча розроблювані підходи мають достатньо загальний характер, щоб їх застосовувати і для видів СР. Капустій Б.О., Русин Б.П., Таянов В.А. «Искусственный интеллект» 1’2008 50 1К Формулювання задачі Задача пониження інформаційного покриття класів є цільовою задачею. По-перше, при зменшенні інформаційного покриття класів підвищується швидкість процесу розпізнавання, а значить, і ефективність роботи відповідної системи. По-друге, зменшення інформаційного опису класів дає можливість зменшити вплив такого негативного явища, як перенавчання. В класичному розумінні під перенавчанням розуміється різниця оцінок результатів розпізнавання на контрольній вибірці і під час навчання. По-третє, при пониженні інформаційного покриття класів змен- шується інформаційне покриття чужих класів, що виникають лише під час процесу розпізнавання і заважають його успішному здійсненню. Може трапитися ситуація, коли при пониженні інформаційного покриття результати правильного роз- пізнавання будуть кращими, ніж до його пониження. Це пояснюється тим, що при зменшенні інформаційного опису класів-еталонів з’являється достатньо велика ймовірність того, що образи-еталони з чужих класів, які призводили до негативних результатів розпізнавання, будуть вилучені з бази даних. Вказаний ефект також призводитиме до перенавчання алгоритму розпізнавання. Тому для побудови більш точних оцінок імовірності правильного розпізнавання необхідно проводити усеред- нення ймовірностей такого розпізнавання для різних розмірів класів еталонів. При пониженні інформаційного покриття класів-еталонів можливі два варіанти. Перший передбачає правильне, а другий неправильне розпізнавання до пониження інформаційного покриття і потребують оцінки його успішності після такого пониження. Оцінка правильності розпізнавання після пониження інформаційного покриття обумовлюється співвідношенням вказаних випадків. Формалізація та постановка задачі Нехай X – простір об’єктів; Y – множина імен класів; YXy →∗ : – цільова функція, значення якої відомі лише на об’єктах скінченої навчаючої вибірки YXyxX l iii l ×⊂= =1),( , )( ii xyy ∗= [5]. У базі даних існують класи еталонів iC , ni ,1= , причому \|\| ii Cs = – розміри класів. Передбачається, що розміри is всіх класів однакові і рівні s . Оскільки існує вибірка контрольних образів U , що подаються на розпізнавання, то загальна кількість образів, що беруть участь у процесі розпізнавання, дорівнюватиме \|\|Usn +∗ . Нехай оцінена частота помилок алгоритму класифікації )( lXa µ= на навчаючій вибірці Ll XX ⊆ : ∑ ∈ ∗≠= Ux uyua U Ua )]()([ \|\| 1),(ν . Задача полягає в оцінюванні величини ∑ ∈ ∗≠= Ux uyua U Ua )]()(~[ \|\| 1),( ~ν при пониженні інформаційного покриття \|\| iC класів-еталонів, де ) ~ (~ lXa µ= – алгоритм, побудований на основі вибірки розміру .~l Як алгоритм класифікації використаємо найбільш простий серед метричних алгоритмів 1NN алгоритм. При такій постановці задачі найбільш придатним підходом, який можна використати для її вирішення, є комбінаторний підхід. Очевидно, що в кожному конкретному випадку пониження інформаційного покриття класів буде проводитись не обов’язково оптимальним чином, однак Комбінаторна оцінка впливу зменшення інформаційного покриття класів… «Штучний інтелект» 1’2008 51 1К загальна статистика всіх можливих понижень класів та результатів таких понижень дасть відповідь на питання про ефективність пониження інформаційного покриття класів-еталонів у цілому. Розв’язання задачі Представимо дані, що подаються на класифікатор a , у вигляді двійкової послідовності },1,0{ посортованої за мінімумом відстаней об’єктів бази даних від тестового об’єкта, де 1 ставляться у відповідність образам, які підтримують правильне розпізнавання (образи свого класу), а 0 – образам, які заважають такому розпізнаванню (образи чужих класів). Приклад такої послідовності поданий на рис. 1. 1 2 31 2 3 { , } 1111111111000111001111000111...1111...000... n nl k k k km m m m k m Рисунок 1 – Модель розпізнавання при заданні початкового розміру классу у вигляді двійкової послідовності Із наведеного рисунка видно, що послідовність образів, які підтримують розпізнавання, має розмірність kl + . Однак різні образи суттєво відрізняються між собою за можливостями цієї підтримки. Дійсно, при використанні 1NN правила видалення 1−l образів з класу-еталону не змінить результатів розпізнавання. З іншого боку, якою б довгою не була послідовність з k образів, вона не зможе підтримати розпізнавання за відсутності стратегічної послідовності розміром l і присутності послідовності розміром m . При пониженні інформаційного покриття класу потрібно враховувати той факт, що якщо послідовність розміром l присутня у початковому класі, то у класі з меншим інформаційним покриттям ∗s вона може зникнути, і навпаки, якщо її не було, то може з’явитися, однак з іншим розміром ∗l . Розглянемо 1NN правило. Визначальною перевагою даного правила є простота реалізації, а до недоліків можна віднести наступні [9]: − нестійкість до похибок, створених викидами у навчаючій вибірці (викидом називають об’єкт певного класу, який знаходиться в оточенні об’єктів чужих класів); − повну залежність алгоритму від метрики між об’єктами та відсутність параметрів для налаштування за навчаючою вибіркою методами ковзаючого контролю або іншими; − низька якість класифікації. Попри вказані недоліки, 1NN правило може мати суттєво кращу стійкість до ефекту пониження інформаційного покриття класів. Це пов’язано з тим, що даний алгоритм менш чутливий до розміру класів, ніж kNN. Отже, можливі два випадки розпізнавання: початкове розпізнавання пра- вильне або неправильне, і потрібно визначити ймовірність його успішності після пониження інформаційного покриття класів. Тобто для першого випадку потрібно визначити ймовірність того, що розпізнавання залишиться правильним, а для другого – Капустій Б.О., Русин Б.П., Таянов В.А. «Искусственный интеллект» 1’2008 52 1К ймовірність переходу розпізнавання з категорії неправильного в категорію правиль- ного. Подамо ймовірність правильного розпізнавання при застосуванні 1NN правила як відношення подій, які підтримують успішне розпізнавання, до загальної кількості подій:      ≥ +− −+ = +− −+ −= − = ∗ ∗ ∗ ∗∗ ∗∗ + + ∗ ∗∗ .,1 ; , )!()!( )!(! )!()!(! )!(!!1 ),,( випадкуіншому в sk klsk sklk klsks sklsk C CC slkP s kl s k s kl (1) Пояснимо обчислення ймовірностей (1). Якщо k s∗< і початкове роз- пізнавання було правильним, то пониження інформаційного покриття не призведе до погіршення результатів розпізнавання, тобто 1)1)(\|( ==< ∗ sPskP . Вираз (1) означає ймовірність того, що розпізнавання буде успішним незалежно від того, яким чином буде зменшене інформаційне покриття своїх і чужих класів. Таким чином, ця ймовірність буде оцінкою зверху для точного (в сенсі комбінаторики) значення ймовірності правильного розпізнавання. Сам принцип оцінок зверху ймовірності успішного розпізнавання полягає в тому, що обчислення точного значення відповідної ймовірності вимагає застосування багатокрокового ітераційного процесу. Уточнити значення ймовірності (1) можна шляхом введення ще однієї оцінки зверху ймовірності того, що перед послідовністю { }ik ( i i k k=∑ ) після пониження інформаційного покриття класів бази даних не буде знаходитись послідовність { },j j m j i<∪ ( mm i i =∑ ). Після виключення з моделі (рис. 1) стратегічної послідовності вона транс- формується до такого вигляду: 1 2 31 2 3 { , } 000111001111000111...0001111... nnk k k km m m m k m Рисунок 2 – Модель розпізнавання у вигляді двійкової послідовності при ∅≠}{l Таким чином, задача зводиться до визначення ймовірності успішного роз- пізнавання після пониження інформаційного покриття класів для випадків, коли початкове розпізнавання було неправильним. Ці ймовірності обчислюються n разів для пар послідовностей { }, , 1,i im k i n= . Отже, на даному етапі вихідною послідовністю з усіх одиниць буде послідовність розміром k . Означення. Показником виживання підпослідовності { },i im k можна вважати ймовірність того, що в результаті можливих комбінацій входжень об’єктів з цієї підпослідовності в інші у ній залишиться хоча б один об’єкт з вихідної підпослідовності. Вказану ймовірність можна записати у вигляді:       ≥−≥−        −=∅= ∗∗ + − + −+ ∗ ∗ ∗ ∗ .1 ;,,1)}{,,( випадкуіншому в, smmskk C C C C lkmP iis kl s kk s lk s mlk ii ii (2) Комбінаторна оцінка впливу зменшення інформаційного покриття класів… «Штучний інтелект» 1’2008 53 1К Якщо всі образи із свого класу в результаті їх сортування за величинами відстаней до тестового образу попали в межі списку { , }m k , то вираз (2) означає ймовірність того, що в цьому списку будуть знаходитись такі образи із свого і такі з чужих класів, що розпізнавання пройде успішно. Ця ймовірність обчислюється рекурсивно- ітераційним способом на основі підпослідовностей :},{ ii mk ( ) ( ) ( ) ( ) 1 1 1 2 1 2 1 1 1 1 1 1 1 2 1 2 1 2 1 2 { } ,{ } ,{ } { } ,{ } ) ({ } 1 , , ; { } ,{ } ,{ } ,{ } ,{ } { } ,{ } ,{ } ) ({ } ,{ } 1 s s l k m k k s s l k l k s s l k m m k k k s l k P l k m P l k P m C C k k s m m s C C P l k k m m P l k k P m m C C C ∗ ∗ ∗ ∗ ∗ ∗ + − − ∗ ∗ + + + − − − − + ≠ ∅ ≠ ∅ =∅ = ≠ ∅ ≠∅ =∅ =    − − ≥ − ≥     ≠ ∅ ≠ ∅ ≠∅ =∅ =∅ = ≠ ∅ ≠∅ ≠∅ =∅ =∅ = − ( ) ( ) 1 2 1 2 1 1 1 1 , ( ) , ( ) ; ............................................................................................... { } ,{ } ,{ } { } ,{ } ) ({ } s l k n n n n i i i i i i i i l k k k s m m m s C P l k m P l k P m C ∗ ∗ ∗ ∗ + = = = = +     − + ≥ − + ≥     ≠ ∅ ≠ ∅ =∅ = ≠ ∅ ≠∅ =∅ = 1 , , . i i i i s s k m k k i is s i il k l k C k k s m m s C C ∗ ∗ ∗ ∗ − − ∗ ∗ + +   ∑ ∑  − − ≥ − ≥      ∑ ∑ (3) У формулі (3) значення n визначається умовами ∗≥−− ∑ skls i i та ∗≥−∑ sms i i , оскільки всі подальші ймовірності )(⋅P дорівнюватимуть 1. Добуток усіх імовір- ностей (3) є глобальною ймовірністю правильного розпізнавання. Висновки На основі запропонованого комбінаторного підходу можна всебічно дослідити найпростіший із метричних класифікаторів – 1NN класифікатор. Потенційно можливий ступінь стиску класу визначається результатами розпізнавання початкового (нестис- нутого) класу. Тому за допомогою комбінаторного підходу можна оцінити вірогідність коректної роботи алгоритму розпізнавання як здатності зберігати свої параметри при зменшенні інформаційного покриття класів. Вказаний підхід не враховує ймовірності отримання тих чи інших початкових результатів розпізнавання, а працює лише на основі зареєстрованих апріорних даних. Література 1. Ивахненко А.Г., Юрачковский Ю.П. Моделирование сложных систем по экспериментальным данным. – М.: Радио и связь, 1987. – 120 c. 2. Jiang Li, Michael T. Manry, Pramod L. Narasimha, and Changhua Yu, Feature Selection Using a Piecewise Linear Network // IEEE Transactions on Neural Network. – 2006. – Vol. 17, № 5, September. – P. 1101-1115. 3. Levner I., et al. Automated Feature Extraction for Object Recognition // In Proceedings of the Image and Vision Computing New Zealand Conference. – 2003. – P. 653-655. Капустій Б.О., Русин Б.П., Таянов В.А. «Искусственный интеллект» 1’2008 54 1К 4. Osborne M.R., Presnell B., and Turlach B.A. A new approach to variable selection in least squares problems // IMA Journal of Numerical Analysis. – 2000. – № 20. – P. 389-404. 5. Воронцов К.В. Комбинаторный подход к оценке качества обучаемых алгоритмов // Математические вопросы кибернетики / Под ред. О.Б. Лупанова. – М.: Физматлит, 2004. – Т. 13. – С. 5-36. 6. Kohavi R. A study of cross-validation and bootstrap for accuracy estimation and model selection // IJCAI. – 1995. – P.1137-1145. 7. M., Sukthankar R. Complete cross-validation for nearest neighbor classifiers // Proceedings of Interna- tional Conference on Machine Learning. – 2000. – P. 639-646. 8. Гуров С.И. Оценка надёжности классифицирующих алгоритмов. – М.: Издательский отдел ф-та ВМиК МГУ, 2003. – 45 с. 9. Режим доступу: http:// www.ccas.ru/voron/teaching.html 10. Капустий Б.Е., Русын Б.П., Таянов В.А. Оптимизация классификаторов в условиях малых выборок // Автоматика и вычислительная техника. – 2006. – Вып. 5. – С. 25-32. 11. Капустий Б.Е., Русын Б.П., Таянов В.А. Математическая модель систем распознавания с малыми базами данных // Проблемы управления и информатики. – 2007. – № 5. – С.142-151. Б.Е. Капустий, Б.П. Русын, В.А. Таянов Комбинаторная оценка влияния уменьшения информационного покрытия классов на обобщающую особенность 1NN алгоритмов классификации В работе предложен комбинаторный подход к определению влияния уменьшения размерности классов на вероятность правильного распознавания при использовании 1NN решающего правила. Результаты распознавания для каждого контрольного объекта считаются известными до понижения размеров классов базы данных. Решена задача определения вероятности того, что правильное распознавание сохранится после понижения размерности классов, а неправильное станет правильным. B.Ye. Kapustii, B.P. Rusyn, V.A. Tayanov In this paper the combinatorial approach for definition of the class size reduction influence on correct recognition probability when one uses 1NN classifier. The recognition results are familiar before database class size reduction for every test object. The probability that recognition system has peculiarity to retain the recognition rate after class size reduction has been determined. The probability definition task that negative recognition results after class size reduction will become positive has also been solved. Стаття надійшла до редакції 14.01.2008.

Комбінаторна оцінка впливу зменшення інформаційного покриття класів на узагальнюючу властивість 1NN алгоритмів класифікації

Institution

Ähnliche Einträge