Т І Завалій, Ю В Нікольський - Аналіз даних та прийняття рішень на основі теоріїнаближених множин - страница 1

Страницы:
1  2  3 

УДК 004.8

Т.І. Завалій, Ю.В. Нікольський

Національний університет "Львівська політехніка", кафедра інформаційних систем та мереж

АНАЛІЗ ДАНИХ ТА ПРИЙНЯТТЯ РІШЕНЬ НА ОСНОВІ ТЕОРІЇ

НАБЛИЖЕНИХ МНОЖИН

© Завалій Т.І., Нікольський Ю.В., 2008

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

The paper describes the theory of rough sets and application of this approach for mining rules from data tables. These rules serve as a classifier that can perform classification of new examples. The use of success rate and ROC curve for evaluation of classifier's quality is described.

1. Вступ

Задачі, пов'язані з інтелектуальним опрацюванням даних і видобуванням знань, є надзвичайно актуальними у зв'язку з постійним збільшенням обсягів інформації, доступної для людини. Застосуванням спеціальних методів видобування знань з баз даних (KDD, knowledge dіscovery іп databases), зокрема, інтелектуального аналізу даних (DM, data mining) можна розкрити неявну структуру даних, виявити взаємні впливи різних факторів та закономірності, присутні у масиві даних. Для цього успішно використовують різноманітні методи м'яких обчислень: нейронні мережі й генетичні алгоритми, розмиті та наближені множини [1, 2]. Із застосуванням цих методів отримують добрі результати розв' язання реальних задач, пов' язаних із обробкою великих обсягів зашумлених даних у разі моделювання складних предметних областей.

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

2. Аналіз останніх досліджень

2.1. Теорія наближених множин

Теорія наближених множин (rough sets) за останні два десятиліття набула значного поширення та застосування, зокрема у видобуванні знань з баз даних. Розвиток теорії наближених множин спричинив появу нейронаближеного числення [3], наближених розмитих систем [4], окремих розділів гранульного числення [5] тощо. Основи теорії уперше сформульовані Ж. Павлаком (Z. Pawlak) [6]. Вона стала гнучким математичним інструментом подолання суперечливостей у даних та виявлення в них прихованих закономірностей. У межах технології наближених множин застосовують метод логічного виведення (boolean reasoning) для редукування даних і побудови правил прийняття рішень. Кінцевим результатом є або набір логічних правил вигляду „якщо то", які здебільшого отримуються генеруванням матриць нерозрізненнності та редуктів, або шаблони даних, які можна застосувати для фільтрування та редукування даних.

Дані, що досліджують з використанням наближених множин, подають за допомогою прикладів, зібраних у таблицю прийняття рішень A=(UA^{d}), де U - непорожня скінченна множина прикладів, A - непорожня скінченна множина умовних атрибутів, d - атрибут прийняттярішення з доменом Vd, \Vd\ = к. Значення vi атрибута d відносить кожний приклад xeU до класу прийняття рішення Xi, де і = \,2,...,к. У загальному випадку, таблиця може мати більше одного класифікуючого атрибуту. У табл 1. наведено зразок таблиці прийняття рішень, яку можна було б сформувати, наприклад, у галузі кредитування.

Таблиця 1

Таблиця прийняття рішень з класифікуючим атрибутом "прогноз"

a

b

c

d

прогноз

задовільно

ні

так

10

негативний

добре

так

ні

10

позитивний

задовільно

ні

так

40

позитивний

задовільно

ні

так

10

негативний

добре

ні

так

10

негативний

На множині U прикладів таблиці визначають відношення нерозрізненності. Нехай BcA — підмножина всієї множини атрибутів таблиці A, x та yприклади таблиці. Тоді IND(B) = {(x,y)eUxU, \/aeB \ a(x)=a(y)}відношення B-нерозрізненності [7]. Якщо явно не задають множину B, то мають на увазі всю множину A атрибутів таблиці. Отже, приклади x та y нерозрізненні, якщо однаковими є відповідні значення їхніх атрибутів. Відношення нерозрізненності симетричне, рефлексивне й транзитивне, а, отже, є відношенням еквівалентності. Клас еквівалентності, отриманий на основі цього відношення, позначають через [X]B, де XcU. Приклади цього класу еквівалентні на множині атрибутів B.

Частина даних в таблиці може бути надмірною або суперечливою, зокрема, якщо певні приклади еквівалентні на множині умовних атрибутів, але мають різні значення атрибута прийняття рішення. Ці приклади неможливо однозначно класифікувати. Кажуть, що вони належать граничній області. Якщо гранична область непорожня, то множину U називають наближеною; у протилежному випадку вона точна. Суперечливі приклади, що належать граничній області, вилучають з таблиці в процесі наближення. Якщо X a Uпідмножина множини прикладів, то X можна наблизити на множині B атрибутів побудовою так званих B-нижнього та B-верхнього

наближень множини X.  Їх позначають  BX   та  BX, відповідно, де   BX = {x\ [ x]B a X} ,

BX = {x\ [ x]B о X Ф 0} , x є X . З множини B приклади з BX можна впевнено класифікувати як

елементи множини X, натомість, приклади з BX можна класифікувати лише як можливі елементи

X. Множину BNB (X ) = BX - BX називають B-граничною областю множини X. Вона містить

приклади, які неможливо однозначно віднести до множини X на підставі інформації з атрибутів B.

Множину U BX називають B-зовнішньою областю X: вона містить приклади, які можна однозначно класифікувати як такі, що не належать множині X. Ілюстрацією введених понять є рис. 1, на якому показано простір прикладів з таблиці прийняття рішень, фрагмент якої неведений у табл. 1. В кожному з квадратів на рисунку приклади нерозрізненні на множині атрибутів B={a,d}. На осі ординат відкладено значення атрибута a, на осі абсцис атрибута d. Приклади з множини X належать класу прийняття рішень з міткою "негативний".

Окрім видалення з таблиці прикладів, що належать граничній області, вилучають надмірні стовпці, значення в яких не впливають на класифікацію прикладів; для побудови правил залишають лише ті атрибути, від яких залежить розрізненність прикладів таблиці. Множину цих атрибутів називають редуктом. Іншими словами, редукт — це підмножина B a A атрибутів таблиці, яка забезпечує таку саму розрізненність всіх прикладів таблиці, як і вся множина A. Мінімальний набір атрибутів, значення яких дають змогу відрізнити один приклад від усіх інших прикладів таблиці,називають об 'єктно-залежним редуктом. З погляду кінцевого результату, ефективною є побудова так званих динамічних редуктів, які обчислюють на основі окремих частин таблиці. Для цього довільно формують набір з k підтаблиць, і серед знайдених для них редуктів відбирають той, який зустрічається найчастіше. Цей підхід більшою мірою враховує особливості розподілу даних в таблиці.

задовільно

■ приклади з множини X        О - приклади з множини {U - X}

|:||||;| - гранична область

■ нижнє наближення

Рис. 1. Множина Х, її верхнє та нижнє наближення на множині атрибутів B={a,d}

Редукт таблиці шукають за методом логічного виведення. Він полягає у побудові функції розрізнення (discernibility function) і її подальшому спрощенні. Функція розрізнення є булевою

функцією gA(a*,...,a*) = a{vc* |1 £ j £ i £ n,c* Ф 0}, де i,j = (1,2,- ,n), m - кількість атрибутів таблиці A, n - кількість прикладів, a*m - атрибут таблиці, c* - елемент спеціальної матриці розрізнення M(A) [7]. Елемент cij- є диз'юнкцією атрибутів, за значеннями яких відрізняються приклади xi та Xj з U . Ці приклади повинні мати різні значення атрибута прийняття рішення. Якщо приклади мають однакове значення атрибута прийняття рішення, то c* = 0 . Тобто

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

Наприклад,  для таблиці  прийняття рішень,  поданої у табл.  1,  функція розрізнення gA (a, b, c, d) = (a v b v c) л (d) л (a v b v c) л (b v c) л (d) л (a v d).      Наступне спрощення

gA = (a v b v c) л (b v c) л (d) л (a v d) = (b v c) л (d) л (a v d) = (b v c) л (d) = (b л d) v (c л d)

утворює два рівноцінні редукти R ={b,d} та R2 ={c,d}.

Іншим методом спрощення функції розрізнення є жадібний алгоритм Джонсона [8]. Нехай R - множина атрибутів, які утворюють шуканий редукт, S - набір підмножин si атрибутів am за

значеннями яких відрізняються два приклади x та y з U, am є A , si tz A . Ці підмножини атрибутів

відповідають кон' юнктам функції розрізнення, яка будується при логічному виведенні. Тобто S є інакшим    способом    представлення    функції    gA.    Так,    для    прикладу    з    табл. 1

S = {{a,b,c},{d},{a,b,c},{b,c},{d},{a,d}},    (a,b,c,d A .   Для   кожної   підмножини siобчислюють коефіцієнт w (si), який позначає вагу si в S . У [9] пропонується приймати вагу

підмножини рівною кількості її повторень у S . Весь алгоритм пошуку редукту складається з п'яти кроків.

Крок 1. Покласти R = 0 .

Крок 2. Вибрати в S атрибут a, який максимізує значення ^ w (si) всіх si, які містять a . Крок 3. Додати a до R .

Крок 4. Видалити з S всі підмножини si, що містять a .

Крок 5. Якщо S = 0 , то R - шуканий редукт, кінець. Інакше - перехід до кроку 2.

Якщо на кроці 5 припинити побудову редукту тоді, коли з набору S вилучено не всі елементи, то ми отримаємо так званий наближений редукт. Цей редукт характеризується ступенем підтримки (HF, hitting fraction) - відсотком тих підмножин Sj від загальної кількості si, атрибути з

яких увійшли до редукту R (Sj о R ^0). Тобто, при побудові наближеного редукту враховуються

не всі підмножини Si , а лише заданий їх відсоток з більшою вагою w . У реальних наборах даних

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

На основі атрибутів, що увійшли до редукта генерують правила прийняття рішень вигляду a ®b, та розраховують їхні числові характеристики. Тут a - умова правила, В - наслідок. Таке правило відображає залежність, можливо, ймовірнісного характеру, між набором значень v атрибутів a та значенням vd атрибута прийняття рішення d . Елементарною частиною правила є дескриптор - вираз вигляду a = v , де a є A , v єУа . Умову правила утворює кон'юнкція дескрипторів a = v, а наслідком правила є дескриптор  d = vd . Наприклад, ^^'добрий") u

^^'так") u="ні") ® прогноз="позитивний". Інший спосіб запису - ЯКЩО ^^'добрий") і ^^'так") і ="ні") ТО (прогноз="позитивний"). Правила, які генерують на основі об'єктно-залежних редуктів мають різну довжину умови і називаються мінімальними правилами. Якість правила оцінюють такими числовими характеристиками [10]:

1. Підтримка. Цей параметр позначається support(a-^e) і вказує кількість прикладів з навчальної таблиці, для яких виконується як умова а правила, так і його наслідок р.

2. Точність. Точність правила - це відношення кількості навчальних прикладів, для яких виконується все правило, до кількості навчальних прикладів, для яких виконується лише умова правила:

support ® В)

accuracy ® В) = ——---— .

Support (а)

3. Покриття. Цей параметр показує відношення кількості навчальних прикладів, для яких виконується все правило, до кількості навчальних прикладів, для яких виконується наслідок правила:

Страницы:
1  2  3 


Похожие статьи

Т І Завалій, Ю В Нікольський - Аналіз даних та прийняття рішень на основі теоріїнаближених множин