Posibniki.com.ua Інформатика Прикладні системи штучного інтелекту Тема 8. МЕТОДИ КЛАСИФІКАЦІЇ ПРОЦЕСУ ПРИЙНЯТТЯ РІШЕНЬ


< Попередня  Змiст  Наступна >

Тема 8. МЕТОДИ КЛАСИФІКАЦІЇ ПРОЦЕСУ ПРИЙНЯТТЯ РІШЕНЬ


ПЕРЕЛІК ЗНАНЬ ТА НАВИЧОК

Після опанування теми студент має знати:

• екстенсіональні та інтенсіональні аспекти класифікації;

• таксономію і мерономію;

• типи класифікацій;

• комбінативні (фасетні) класифікації;

• структуру булевої алгебри; має вміти:

• аналізувати деревовидні класифікації;

• застосовувати програмні засоби для пошуку закономірностей між пов’язаними подіями;

• наводити приклади стосовно сфери застосування дерев рішень;

• застосовувати метод побудови дерева.

ЗМІСТ ПИТАНЬ З ТЕМИ

8.1. Екстенсіональні та інтенсіональні аспекти класифікації

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

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

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

Класифікаційні структури спільно з ієрархією агрегації забезпечують розгляд сутності ПРГ з двох взаємодоповнюючих поглядів: з позиції взаємозв’язків понять, утворених для глобального опису ПРГ (зовнішні зв’язки сутності); з позиції внутрішньої будови сутності (локальні зв’язки).

Класифікація — це виділення на основі істотних ознак з деякої множини понять універсального класу всіх підмножин (підкласів), які входять до нього, і встановлення між виділеними підмножинами відношення порядку. Ознаки, на основі яких проводиться виділення з універсального класу всіх його підкласів, називаються класифікаційними. Якщо K

0 деякий клас, а K

1 , K

2 , ..., K n — його підкласи, то == = ji n j i KKKKI U ,

0 ?.

1

Проте в загальному випадку не обов’язково, щоб виконувалося співвідношення K i ? K j = ?.

Кожний із класів K i , у свою чергу, може бути підданий подальшому розбиттю на підкласи K j , так що ,

1 U i n j i ji KK = = = i q i p KKI? і т. д. У результаті виникає певна структура взаємозв’язків між

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

0 …

Одержана структура класів повністю характеризується їх екстенсіоналами, оскільки визначається входженням сутності ПРГ в класи і їх взаємозв’язками один з одним. Це екстенсіональний аспект класифікації. На екстенсіональному рівні класифікацію можна розглядати як алгебру K = (K i ?) з теоретико-множинною операцією включення. Правила побудови впорядкованої системи класів спираються на сукупність тих ознак, якими володіють поняття, що класифікуються, тобто використовують інформацію, вміщену в інтенсіонал понять.

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

8.2. Таксономія і мерономія

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

Таксономія і мерономія тісно пов’язані між собою. З одного боку, ознаки сутності служать для розділення і розпізнавання сутності, а з другого — для групування схожої сутності в класи (таксони).

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

Архетип — це деяка внутрішня структура, яку можна виявити в усій сутності відповідного таксона.

класами, яка містить важливу семантичну інформацію про ПРГ. Зокрема, між класами встановлюється відношення порядку i ji KKK??

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

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

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

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

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

Структура таксонів характеризує екстенсіональний аспект класифікаційної системи, а структура меронів — інтенсіональний, що дозволяє визначити клас як трійку де arhK, taxK і shmK відповідно позначають архетип таксон і схему даного класу.

К = < arhK, taxK, shmK >,

К = < arhK, taxK, shmK >,

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

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

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

Рис. 2. 19. Діаграма теоретико-множинних зв’язків між класом і поняттями (для простоти при встановленні зв’язків між схемами класів і понять не врахована можливість уведення власних характеристичних ознак класів)

Рис. 2. 19. Діаграма теоретико-множинних зв’язків між класом і поняттями (для простоти при встановленні зв’язків між схемами класів і понять не врахована можливість уведення власних характеристичних ознак класів)

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

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

8.3. Типи класифікацій

Як уже зазначалося, між таксонами існують певні взаємозв’язки. Найбільш простий зв’язок між двома таксонами — відношення включення. Таксон Т i міститься в таксоні T j , якщо всі види таксона Т i належать таксону T j . Крім того, таксони можуть бути пов’язані відношенням перетину.

Якщо таксони Т i і T j мають непорожній перетин і один з них міститься в другому, то класифікаційна структура таксонів стосовно до включення є деревовидною. Кожен таксон у цій структурі належить певному рівню в дереві (рис. 2.20). Структура алгебри архетипів може бути як деревоподібною, так і мати складнішу будову.

Рис. 2.20. Структура алгебри таксона в деревоподібній класифікації

Рис. 2.20. Структура алгебри таксона в деревоподібній класифікації

Можлива і протилежна ситуація: архетипи утворюють структуру типу дерево, а множина усіх таксонів організовано не у вигляді дерева, а дещо складніше. Наприклад, цими властивостями володіє рубрикатор наукових журналів. Так, випуск «Теоретична кібернетика» входить як у розділ «Математика», так і в розділ «Автоматика і телемеханіка», тобто деревоподібність таксонів не виконується, проте архетипи організовані у вигляді деревоподібної структури.

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

Це фактично задає на початковій множині подвійне відношення порядку: «зверху вниз» і «з низу до верху», що дозволяє встановити глибокий зв’язок між таксономією і мерономією, властивою класифікаційним схемам даного типу. Простими класифікаційними структурами даного типу є булеві класифікації. До іншого типу таксономічної структури належать фасетна або комбінативна класифікації. Як фасети (аспектів) такої класифікації виступають ознаки понять, що мають різні імена. Кожна ознака визначає розбиття множини сутностей на непересічні підмножини першого рівня. Попарні перетини таксонів першого рівня, які задаються ознаками з різними іменами, утворюють таксони другого рівня, потрійні перетини — таксони третього рівня і т. д. У результаті таксон може бути взаємозв’язаний з двома і більше таксонами верхнього рівня.

Отже, комбінативна класифікаційна структура не є деревовидною. Як і у випадку булевих класифікацій, структура алгебри комбінативних класифікацій є решіткою.

8.4. Деревоподібні класифікації

Проведемо зіставлення різних типів класифікаційних схем шляхом порівняння структур їх таксономічних решіток стосовно до теоретико-множинного включення до них таксонів. Відношення включення є на множині таксонів також і відношенням порядку. Проста класифікаційна схема — деревоодібна ієрархія. Порядок називається деревовидним, якщо для двох таксонів Т i і T j , або Т i ? Т j , або Т i ? T j .

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

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

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

8.5. Булеві класифікації Іншим видом класифікаційної схеми є ситуація, коли таксони утворюють структуру булевої алгебри. У цьому випадку на виділеній системі класів K i задаються теоретико-множинні операції об’єднання (?), перетини (?) і різниці (/). Тоді початкова система класів перетворюється на булеву алгебру

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

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

1 , d

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

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

Структура таксонів за включенням антиізоморфна структурі всіх підмножин множини дескрипторів {d4 }. Дійсно, включення таксона Т i ? T j означає, що таксон Т i визначається якимись додатковими дескрипторами, тобто якщо таксону Т i зіставити архетип arhK i , а таксону T j — архетип arhK j , то виконуватиметься співвідношення arhK i ? arhK j .

Рис. 2.22. Антиізоморфна структура архетипів пошукових зразків документів

Рис. 2.22. Антиізоморфна структура архетипів пошукових зразків документів

8.6. Комбінативні класифікації

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

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

Для виділення таксонів кожен фасет, у свою чергу, піддається додатковому діленню на основі використання значень ознак. Так, якщо є ознаки А, В, С, то в комбинативній класифікації можна виділити три фасети першого рівня — F A , F B , F C ; три фасети другого рівня — F AB , F AC , F BC і один фасет третього рівня F ABC . Таксони першого рівня T

A A A B B C

1 , T

2 ,…, n T, T

1 ,..., m T, T

1 ,... утворюються шляхом ділення кожної з фасет F A , F B , F C на основі значень ознак. Таксони другого рівня можуть бути одержані шляхом попарних перетинів таксонів першого рівня і т. д. Кількість таксонів на першому рівні визначається сумарною потужністю доменів значень ознак:

213

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

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

Рис. 2.23. Фасетна класифікаційна система

Рис. 2.23. Фасетна класифікаційна система

Архетипи класів комбінативної класифікації є підмножиною безлічі пар (){} i ji aA, імен і значень ознак. Для розглянутого вище прикладу архетипами класів другого рівня будуть множини:

Як приклад розглянемо комбінативну класифікацію множини сутностей {e

Як приклад розглянемо комбінативну класифікацію множини сутностей {e

1 , e

2 , е

3 , e

4 , e

5 , e

6 , e

7 , e

8 }, що містить ознаки з іменами

214

Тоді класифікаційні мережі даної ПРГ можуть бути представлені у вигляді, поданому на рис. 2.24. На першому рівні знаходяться таксони, які визначаються одиночними значеннями ознак; на другому вони визначаються парними комбінаціями ознак, на третьому — трійками значень ознак.

Рис. 2.24. Приклад класифікаційних мереж гіпотетичної ПРГ

Рис. 2.24. Приклад класифікаційних мереж гіпотетичної ПРГ

Таксон Т

0 містить сутність, що належить усій ПРГ, оскільки на нього не накладається жодних обмежень, а таксон T ABCD порожній унаслідок того, що в ПРГ відсутня сутність, що володіє всіма допустимими значеннями ознак одночасно.

Зазначимо також, що в класифікаційних решітках немає класів сутності першого рівня із значеннями властивостей b

1 і b

2 , оскільки про множину об’єктів {e

1 , e

2 } і {е

3 , e

5 } можна зробити точніше ствердження, ніж таке, що ті класи сутності володіють властивостями b

1 і b

2 .

Дійсно, таксон AB T

1 містить сутність, що володіє як ознакою b

1 , так і ознакою a

1 , а таксон BC T

1 — сутність, що має ознаки b

2 і C

1 . Множини {e

1 , e

2 } і {е

3 , е

5 }, виділені на підставі тільки однієї ознаки b

1 або b

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

Зауважимо, що третій рівень класифікаційних мереж фактично містиь інформацію, що збігається з ознаками ПРГ, за винятком таксона Т

6 , в який потрапила сутність e

6 і e

8 , не помітні на підставі класифікаційних ознак з іменами А, В і С, але мають різ-

6 має властивість d

4 , а сутність e

8 — ознака d

2 .

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

З рис. 2.24 видно, що як класси-утворювачі для класифікаційних решіток необхідно взяти таксони T

A C C B A AB BC

1 , T

1 , T

2 , T

1 , T

2 , T

1 , T

1 .

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

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

8.7. Дерева рішень

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

Основними поняттями теорії дерев рішень є:

об’єкт — приклад, шаблон, спостереження;

атрибут — ознака, незалежна змінна, властивість;

мітка класу — залежна (цільова) змінна, ознака, що визначає клас об’єкта;

вузол — внутрішній вузол дерева, вузол перевірки;

лист — кінцевий вузол дерева, вузол рішення;

перевірка (test) — умова у вузлі.

Перші ідеї створення дерев рішень запропоновано у роботах П. Ховленда (P. Hoveland) та Е. Ханта (E. Hunt) наприкінці 50-х років XX століття.

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

Опис даних: дерева рішень дозволяють зберігати дані про об’єкти в компактній формі.

ні характеристичні ознаки: сутність e

Класифікація: дерева рішень відмінно справляються із задачами класифікації, тобто з віднесенням об’єктів до одного із заздалегідь відомих класів. Цільова змінна повинна мати дискретні значення.

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

Нехай нам задана деяка навчальна множина T, що містить об’єкти (приклади), кожний з яких характеризується m атрибутами, причому один з них указує на приналежність об’єкта до визначеного класу. Тоді дерево рішень може бути побудоване в результаті виконання таких дій.

Нехай через C

1 , C

2 ,...,C k позначено класи (значення міток класів), тоді існують три ситуації:

— множина T містить один або більше прикладів, що належать до одного класу C k . Тоді дерево рішень для Т — це лист, що визначає клас C k ;

— множина T не містить жодного прикладу, тобто порожня множина. Тоді це знову лист, і клас, асоційований з листом, вибирається з іншої множини відмінного від T, скажімо, із множини, асоційованої з батьком;

— множина T містить приклади, що належать до різних класів.

У цьому випадку варто розбити множину T на деякі підмножини. Для цього вибирається одна з ознак, що має два і більше відмінних одне від одного значень O

1 , O

2 ,...,O n . T розбивається на підмножини T

1 , T

2 ,...,T n , де кожна підмножина T i містить усі приклади, що мають значення O i для обраної ознаки. Ця процедура буде рекурсивно продовжуватися доти, поки кінцева множина не буде складатися з прикладів, що належать до одного й того самого класу.

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


< Попередня  Змiст  Наступна >
Iншi роздiли:
Частина 3. МЕТОДИ КЛАСИФІКАЦІЇ ПРОЦЕСУ ПРИЙНЯТТЯ РІШЕНЬ
8.8. Програмні засоби для пошуку закономірностей між пов’язаними подіями
Частина 2. Програмні засоби для пошуку закономірностей між пов’язаними подіями
Тема 9. УПРАВЛІННЯ ПРОЦЕСОМ РОЗВ’ЯЗАННЯ ЗАДАЧІ
9.2. Моделі евристичного пошуку рішень
Дисциплiни

Медичний довідник новиниКулінарний довідникАнглійська моваБанківська справаБухгалтерський облікЕкономікаМікроекономікаМакроекономікаЕтика та естетикаІнформатикаІсторіяМаркетингМенеджментПолітологіяПравоСтатистикаФілософіяФінанси

Бібліотека підручників та статтей Posibniki (2022)