2.2. Міри подібності (близькості) кількісних та якісних ознак.

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

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

Міри подібності, які використовуються на практиці відрізняються великим різноманіттям властивостей, проте можна сформулювати загальні вимоги, яким повинна задовольняти використовувана міра подібності, тобто:

.

Переважно використовують три типи мір подібності:

1) коефіцієнти подібності (або квантифіковані коефіцієнти зв’язку);

2) коефіцієнти зв’язку (кореляції);

3) показники відстані в метричному просторі.

Коефіцієнти подібності. Будь-який вектор , елементи якого дійсні цілі числа – номера градацій відповідних ознак, завжди можна записати в двійковому коді. Тоді, можемо вважати, що будь-який об’єкт описується вектором , кожна з компонент якого приймає значення 0 або 1, тобто ознака є булавою. Для побудови вимірювачів подібності між об’єктами та введемо наступні позначення частот: – число співпадаючих одиничних ознак у обох об’єктів (пар 1, 1); – число співпадаючих нульових ознак в обох об’єктів (пар 0, 0); – число співпадаючих одиничних ознак в -го і нульових в -го об’єктів (пар 1, 0); – число співпадаючих нульових ознак в -го і одиничних в -го об’єктів (пар 0, 1); , – число одиничних ознак в -го і в -го об’єктів відповідно; , – число нульових ознак в -го і в -го об’єктів відповідно; – загальне число співпадаючих ознак, тобто ; – загальне число неспівпадаючих ознак, тобто ; – загальне число ознак, за якими здійснюється порівняння.

До найбільш вживаних вимірювачів подібності відносять наступні, які для зручності і наочності зведені в таблицю.

Назва	Формула	Примітка
Загальноприйнятої назви немає		Застосовується в тих випадках, припускається “рівноважливість” нульових та одиничних ознак
Коефіцієнт Рао
Коефіцієнт Хаммана		При
Назва	Формула	Примітка
Коефіцієнт Роджерса і Танімото
Коефіцієнт Джекарда
Коефіцієнт Дейка		Надає вдвічі більшу вагу співпадаючим одиничним ознакам
Загальної назви немає		Надає більшу вагу неспівпадаючим ознакам
Коефіцієнт композиційної подібності		Модифікація коефіцієнта Роджерса-Танімото. Відрізняється включенням співпадіння нульових ознак.

Ці показники називаються коефіцієнтами подібності і позначаються переважно . В даному випадку .

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

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

і т.д. ці нові величини використовуються у виразах для коефіцієнтів подібності замість аналогічних величин, які розраховуються для бінарних ознак. Очевидно, що різні коефіцієнти подібності, будучи розрахованими для одних і тих же об’єктів та , будуть різними за величиною. Вибір того чи іншого коефіцієнта визначається характером розв’язуваної задачі (відносною важливістю нульових і одиничних ознак, важливістю порозрядного співпадіння або неспівпадіння) і досить суб’єктивним. Наприклад, в задачах класифікації, які розв’язуються з метою побудови системи автоматичної діагностики в медицині або техніці, можлива ситуація, коли наявність відхилення від норми того чи іншого параметра (ознаки) позначається символом “ 1 “, а відсутність цього ефекту – “ 0 “. Зрозуміло, що в одну групу необхідно об’єднати об’єкти з відхиленнями, а в другу – нормальні об’єкти. Для підсилення контрастності об’єктів при порівнянні в даному випадку краще скористатися коефіцієнтом Дейка, ніж звичайним відношенням числа співпадаючих ознак до їх загального числа, – коефіцієнтом, який використовується при припущенні про рівнозначність нульових і одиничних ознак.

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

відстань Хеммінга розглядають як квадрат евклідової відстані в просторі бінарних змінних, які відповідають категоріям (класам) початкових даних, тобто

, (5)

де – номер початкової змінної; – номер категорії (класу); – число категорій -ої змінної. Величини можуть приймати лише значення “1” або “0”.

В найскладнішому для обробки емпіричних даних випадку, коли описи обєктів представлені в одинаково впорядкованій символьній послідовності (символами імен, понять, означень) т.з. “кендалівський ряд кореляції”.

, (8)

де коефіцієнти непарного порівняння між собою всіх компонент опису обєктів задаються відношенням порядку у вигляді:

(9)

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

Наприклад, нехай опис деякого об’єкта заданий послідовністю ознак: , тоді, у відповідності з (9)

В останньому випадку поняття “велике” і “гарне” визначають різні властивості і тому не можуть бути співставленими одна з одною, тобто в цьому сенсі мінімальне значення рівне 0, оскільки це значення відстань Кендала має для об’єктів, описи яких впорядковані одинаково (велике для розмірів, а гарне – для красоти).

Наприклад, у випадку числового опису обєкта і є одинаковими і відстань Кендала між ними рівна 0, оскільки , і з (8) маємо .

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

,

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

Характеристики мір.

Якщо відстань між об’єктами природно трактувати як міру відмінності об’єктів, то обернену величину можна розглядати як міру подібності (близькості) об’єктів.

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

, (4)

де та – значення компонент в опису 1-го та 2-го об’єктів, – розмірність простору ознак .

2. Широко використовується лінійна метрика (метрика міських кварталів або манхетенська метрика) яка задає відстань

, (5)

а також sup- норма , яка визначає чебишевську відстань

. (6)

На рис. 1. показано зміст цих відстаней.

- довжина відрізка АС;

- сума довжин відрізків АВ і ВС;

- довжина більшого з відрізків АВ і ВС, тобто АВ.

Рис.1. Ілюстрація змісту відстаней .

Очевидно, що з ростом розмірності манхетенська відстань підкреслює, а чебишевська злагоджує відмінності між об’єктами. Відстані визначаються для тих описів , в яких ознаки виражені кількісними шкалами і є по-суті частинними випадками узагальнення степеня відстані

Мінковського , для яких отримуються при . Існує досить велика різноманітність мір, але на практиці ці міри є найуживанішими.

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

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

Якщо ознаки представляються в якісних шкалах, зокрема в шкалах найменувань та порядку, використовують відстань Хеммінга

для якої відмінності виражаються числом неспівпадінь властивостей порівнюваних об’єктів. У випадку якісних шкал ознаки розглядаються як бінарні, тобто такі, що можуть приймати лише два значення “ 0 “ та “ 1 “. Відстань Хеммінга є максимальною і рівна 1 для об’єктів з протилежними за значеннями описами, тобто елементи одного опису є протилежними до відповідних елементів опису другого об’єкту. Для об’єктів, всі ознаки яких (з числа включених в опис) співпадають, .

ЛЕКЦІЯ К-3.