Побудова евристичного алгоритму розпізнавання

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

Розглянемо процес побудови такої моделі на прикладі формалізації принципу розділення. Суть його в тому, що там, де описи об’єктів задаються наборами значень числових ознак (об’єкти є точками n-мірного простору), такі описи, що належать різним класам, можуть бути розділені поверхнями достатньо простого виду.

Розглянемо одну з можливих формалізацій. Скористаємося найпростішим класом розділюючих поверхонь – гіперпрлощинами

(1)

Нехай множина допустимих об’єктів розділена на два класи .

Відомо, що об’єкти S₁, …, S_m належать К₁ , а об’єкти S_m+1, …, S_q до К₂. Ці об’єкти не рівнозначні, тому введемо їх числові характеристики γ(S_i)=г_i – вага об’єкта S_i, і=1, 2, …, m, m+1, q. Отже множина алгоритмів характеризується заданням параметрів а₁, …, а_n+1 – коефіцієнтів у рівнянні гіперплощини і г₁, …, г_q – вагою об’єктів, класифікація яких проведена раніше.

Процес розпізнавання для I(S)=(б₁, …, б_n) відбувається наступним чином.

Нехай

.

Розділимо об’єкти S₁, …, S_m на множини : якщо ; якщо .

Аналогічно розділимо об’єкти S_m+1, …, S_q на множини . Розглянемо величини

і аналогічно їм величини

тут .

Обчислюємо . Поставимо у відповідність S два число: – що відповідно значеннями функції незалежності S класам К₁, К₂.

Якщо , то

(2)

Якщо , то

(3)

По значенням приймається рішення про віднесення S в клас К₁ або К₂. Ця процедура задається рішаючим правилом.

Розглянемо клас рішаючих правил, які визначаються параметром d.

Якщо , тоді

Якщо , тоді

Якщо , тоді рішення не приймається, алгоритм відмовляється від класифікації S.

Це є реалізація однієї з можливих моделей, основаних на принципі розділення.

Основні гіпотези, які використано:

1) елементи класів К₁, К₂ розділяються гіперплощиною;

2) елементи класів не рівнозначні по важливості; міру цієї важливості можна виразити числом.

Реалізація гіпотез проведена при побудові моделей

М(а₁, … а_n+1, g₁, …, g_q, d),

-¥<g_i, a_i<+¥,

d³0.

Задання значень всіх параметрів моделі визначає її елемент – конкретний алгоритм розпізнання.