Методи кластер-аналізу

Кластер-аналіз (класифікаційний аналіз, навчання без учителя, таксономія, самонавчання) розв’язує такі основні задачі:

- факторний кластер-аналіз, що полягає у визначенні нового класу для відкритого алфавіту класів розпізнавання , де - символ відкритості множини, елементи якої не є скінченними.

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

- самонавчання, яке розв’язує задачу традиційного кластер-аналізу за умови зміни потужності відкритого словника , тобто самонавчання передбачає розв’язання таких задач як оцінка інформативності ОР та оптимізація словника ознак.

До теперішнього часу проблема кластер-аналізу (тобто розбиття простору ознак розпізнавання за апріорною навчальною вибіркою) залишається не вирішеною.

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

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

Класичним представником таких методів є метод FOREL. Ідея цього методу полягає в побудові в просторі ознак гіперсфери радіуса .

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

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

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

Методом кластер-аналізу, який базується на критеріях зв’язності є критерій KRAB. В основу метода покладено обчислення інтегрованого критерію якості таксономії:

, (2.8.1)

де - середня довжина ребер, що з’єднують таксони:

,

Тут - довжина ребер одного таксона:

,

де – довжина -го ребра -го таксона;

– кількість точок в таксоні.

Параметри і у виразі (2.8.1) визначаються відповідно за формулами

,

де - кількість точок -го таксона;

- загальна кількість усіх точок;

.

Якщо довжина - го ребра , а довжина найближчого примикаючого до нього ребра , то чим менше буде , тим більше є причин вважати що саме по ребру здовжиною пройде межа між таксонами, тобто

,

де - довжина найближчого примикаючого ребра.

І нарешті, параметр визначається за формулою

,

тобто це усереднена по всім таксонам міра близькості точок, де

– усереднена міра близькості в середині - го таксона.

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

Розділ 3.Статистичні методи ТРО

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

3.1. Байесівський класифікатор

Параметричні методи реалізуються на базі байєсівського класифікатора (вирішальних правил) за відповідними статистичними критеріями теорії прийняття рішень [3].

Класифікатор називається байєсівським тому, що теоретичною основою його створення є класична формула Байєса, яка дозволяє обчислити апостеріорну умовну імовірність через апріорні умовні імовірності, наприклад, для двохальтернативних рішень за формолою

:

, (3.1.1)

де – безумовна ймовірність належності -ої реалізації класу ; – апріорна умовна ймовірність прийняття гіпотези за умови, що мала місце апріорна гіпотеза .

Розглянемо основні статистичні критерії.

Критерій максимальної апостеріорної умовної імовірності. За цим критерієм, якщо відомо, наприклад, відношення апостеріорних умовних імовірностей

,

то приймається рішення, що .

Якщо виконується принцип Бернуллі-Лапласа ( ), то можна використовувати відношення правдоподібності

, (3.1.2)

За допомогою відношення правдоподібності (3.1.2) в статистичній теорії прийняття рішень реалізується критерій максимуму правдоподібності[3], який дозволяє мінімізувати повну ймовірність помилкового рішення:

. . (3.1.3)

При цьому алгоритм розпізнавання такий: якщо

то , інакше .

Вимоги практичного застосування байєсівських класифікаторів сприяли розвитку непараметричного підходу в ТРО, у рамках якого, наприклад, запропоновано функцію умовного середнього ризику:

, (3.1.4)

де - функція штрафів (втрат) при прийнятті гіпотези .

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

На практиці широке застосування знайшов статистичний критерій Неймана-Пірсона, який дозволяє мінімізувати вираз (3.1.3) при заданих обмеженнях на одну із помилок. Звичайно приймається . Тоді за поріг класифікації приймається величина

3.2. Визначення мінімального обсягу репрезентативної

навчальної вибірки

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

Оскільки вибірки випадкових величин є скінченними, то це обумовлює наявність статистичної похибки, яка є основним критерієм репрезентативності навчальної вибірки:

,

де – імовірність знаходження - ої ознаки розпізнавання в своєму контрольному полі допусків ; – емпірична частота.

При цьому –граничне значення емпіричної частоти.

За теоремою Муавра-Лапласа встановлено, що має місце співвідношення

),

де – функція Лапласа; – рівень значущості, який дорівнює будь-якому малому додатньому числу, але рекомендується вибирати із такого ряду чисол: Q=00,5; 0,01; 0,001; – обсяг навчальної вибірки.

Оскільки графік функції Лапласа має вигляд, показаний на рис. 2.9.1, то можна прийняти, що .

Рисунок 3.2.1

Тоді , звідки

. (3.2.1)

На рис 3.2.2 наведено графічний приклад визначення мінімального обсягу репрезентативної навчальної вибірки . При цьому графік залежності статистичної похибки від обсягу вибірки побудовано за формулою (3.2.1), а графік довірчого інтервалу ймовірності побудовано за формулою

. (3.2.3)

Рисунок 3.2.2

За рис. 3.2.2 як вибирається випробування, при якому заданий інтервал , де , повністю покриває довірчий інтервал (2.9.3).

Таким чином, при гарантується, що статистична похибка буде менше максимальної і далі буде мати місце статистична стійкість. Застосування навчальних вибірок обсягу є ефективним при використанні статистичних логарифмічних інформаційних критеріїв (Шеннона, Кульбака, Фішера та інших).

Основною заслугою статистичного підходу до розпізнавання образів є започаткування розвитку теорії машинного навчання, основи якої закладено у працях [8,10,14]. При цьому модельність статистичних методів автоматичної класифікації так само становить певну методологічну цінність, оскільки дозволяє дослідити механізм прийняття рішень.