Формальна постановка задача класифікації

Задача розпізнавання образІв

Предмет розпізнавання образів

Розпізнавання образів ─ це наукова дисципліна, метою якої є класифікація об'єктів за декількома категоріями або класами. Об'єкти називаються образами.

Класифікація грунтується на прецедентах. Прецедент ─ це образ, правильна класифікація якого відома. Прецедент ─ раніше класифікований об'єкт, що приймається як зразок при розв’язанні задач класифікації.

Будемо вважати, що усі об'єкти розбиті на кінцеве кількість класів. Для кожного класу відоме і визначене кінцеве кількість об'єктів-прецедентів. Задача розпізнавання образів полягає в тому, щоб віднести новий об'єкт, що розпізнається, до деякого класу.

Розпізнавання образів є основним в більшості інтелектуальних систем. Розглянемо приклади інтелектуальних комп'ютерних систем.

Машинний зір. Це системи, призначення яких полягає в отриманні зображення через камеру і складання його опису в символьному вигляді (які об'єкти присутні, в якому взаємному відношенні знаходяться і т.д.).

Символьне розпізнавання (розпізнавання букв або цифр): Optical Character Recognition (OCR); введення і зберігання документів; Pen Computer; обробка чеків в банках; обробка пошти.

Діагностика в медицині: мамографія, рентгенографія; постановка діагнозу по історії хвороби; електрокардіограма.

Геологія.

Розпізнавання мови.

Розпізнавання в дактилоскопії (відбитки пальців), розпізнавання особи, підпису, жестів.

Ознаки і класифікатори

Виміри, що використовуються для класифікації образів, називаються ознаками. Ознака ─ це деякий кількісний вимір об'єкту довільної природи. Сукупність ознак, що відносяться до одного образу, називається вектором ознак. Вектори ознак набувають значень в просторі ознак. У рамках задачі розпізнавання вважається, що кожному образу ставиться у відповідність єдине значення вектора ознак і навпаки: кожному значенню вектора ознак відповідає єдиний образ.

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

В процесі розробки необхідно вирішити наступні питання.

1. Як вибрати вектори ознак? Задача генерації ознак ─ це вибір тих ознак, які з достатньою повнотою описують образ.

2. Які ознаки найбільш суттєві для розподілу об'єктів різних класів? Задача селекції ознак ─ відбір найбільш інформативних ознак для класифікації.

3. Як побудувати класифікатор? Задача побудови класифікатора - вибір вирішального правила, по якому на підставі вектора ознак здійснюється віднесення об'єкту до того або іншого класу.

4. Як оцінити якість побудованої системи класифікації? Задача кількісної оцінки системи (вибрані ознаки + класифікатор) з точки зору правильності або помилковості класифікації.

Класифікація з навчанням і без навчання

Залежно від наявності або відсутності прецедентної інформації розрізняють задачі розпізнавання з навчанням і без навчання. Задача розпізнавання на основі наявної множини прецедентів називається класифікацією з навчанням (чи з учителем).

Якщо є множина векторів ознак, отриманих для деякого набору образів, але правильна класифікація цих образів невідома, виникає задача розподілу цих образів на класи по схожості відповідних векторів ознак. Ця задача називається кластеризацією або розпізнаванням без навчання.

Формальна постановка задача класифікації

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

Ω ─ множина об'єктів розпізнавання (простір образів).

ω: ω Ω─ об'єкт розпізнавання (образ).

g(ω) : Ω → М, М = {1,2,.., m} - індикаторна функція, що розбиває простір образів на Ω на m класів Ω¹, Ω², …, Ω^m, що не перетинаються. Індикаторна функція невідома спостерігачеві.

X - простір спостережень, що сприймаються спостерігачем (простір ознак).

х(ω) : Ω → X ─ функція, що ставить у відповідність кожному об'єкту ω точку х(ω) в просторі ознак. Вектор х(ω) ─ це образ об'єкту, що сприймається спостерігачем. У просторі ознак визначена множина точок K_i Х, що не перетинаються, i = 1,2,..., m і відповідають образам одного класу.

gˆ(x): X → М - вирішальне правило ─ оцінка для на основі , тобто gˆ(x) = gˆ(х(ω)).

Нехай х_j = х(ω_j), j = 1,2,..., N - доступна спостерігачеві інформація про функції g(ω)і х(ω), але самі ці функції спостерігачеві невідомі. Тоді (g_j, x_j), j = 1,2.., N – є множиною прецедентів.

Задача полягає в побудові такого вирішального правила gˆ(x), щоб розпізнавання проводилося з мінімальною кількістю помилок.

Звичайний випадок ─ вважати простір ознак Евклідовим, тобто X = R¹. Якість вирішального правила вимірюють частотою появи правильних рішень. Зазвичай його оцінюють, наділяючи множинb об'єктів Ω деякою імовірнісною мірою. Тоді задача записується у вигляді P {gˆ(х(ω)) ≠ g(ω)}.