МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ РАДІОЕЛЕКТРОНІКИ

Тітова Олена Вітольдіївна

УДК 004.8:004.93

МЕТОДИ ПОБУДОВИ ТА ОЦІНКИ АГРЕГОВАНИХ АСОЦІАТИВНИХ ПРАВИЛ В ІНТЕЛЕКТУАЛЬНИХ БАЗАХ ДАНИХ

05.13.23 – Системи та засоби штучного інтелекту

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

кандидата технічних наук

Харків – 2006

Дисертацією є рукопис.

Робота виконана в Харківській державній академії культури Міністерства культури і туризму України.

Науковий керівник: | кандидат технічних наук, доцент

Ситніков Дмитро Едуардович,

Харківська державна академія

культури, завідувач кафедри

інформаційно-документних систем.

Офіційні опоненти:

доктор технічних наук, професор Любчик Леонід Михайлович, Національний технічний університет "Харківський політехнічний інститут", завідувач кафедри комп'ютерної математики та математичного моделювання, м. Харків;

кандидат технічних наук, старший науковий співробітник Феклістов Андрій Олександрович, Об’єднаний науково-дослідний інститут Збройних Сил, старший науковий співробітник відділу військової стандартизації та якості продукції оборонного призначення, м. Харків.

Провідна установа:

Донецький державний інститут штучного інтелекту НАН України, кафедра системного аналізу та моделювання.

Захист відбудеться “11” жовтня 2006 р. о 13 годині на засіданні спеціалізованої вченої ради Д 64.052.01 в Харківському національному університеті радіоелектроніки, за адресою: пр. Леніна, 14, м. Харків, 61166; факс (0572) 409113.

З дисертацією можна ознайомитись у бібліотеці Харківського національного університету радіоелектроніки за адресою: пр. Леніна, 14, м. Харків, 61166.

Автореферат розісланий “_8__”_вересня_2006 р.

Вчений секретар спеціалізованої вченої ради Чалий С.Ф.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

Саме системи формування знань на основі аналізу та узагальнення даних (Data Mining та Knowledge discovery) в останні роки набувають бурного розвитку. Дійсно, на даний момент у світі накопичено величезний об’єм інформації з різних галузей, наприклад: результати наукових експериментів, моніторингу земної поверхні, бізнес-дані, дані медичного характеру та ін. Стало ясно, що без продуктивного аналізу потоки даних складають нікому не потрібну купу, але напроти, при наявності такого аналізу ці дані можуть стати безцінним джерелом нової інформації і нових знань. В різних галузях – медицині, генній інженерії, банківській та страховій справах існує велика потреба у цих технологіях. Безумовно, велику роль зіграє розвиток технологій систем управління базами даних, здешевлення носіїв інформації, що дає можливість аналізувати величезні масиви інформації.

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота зв'язана з розробкою алгоритмів обробки інформації в інтелектуальних базах даних згідно НДР "Супровід БД "Стандарти і нормативи" згідно НКПУ на 2003-2005 роки (ДР №013U007083), з дослідженнями згідно планів НДР Наукового центру Військ ППО (НДР "Дуель" (ДР № )), заданих Головнокомандувачем Військами ППО Збройних Сил України на 2000-2004 роки, а також з навчальним процесом при підготовці бакалаврів по спеціальності "Документознавство та інформаційна діяльність" Харківської державної академії культури.

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

Поставлена мета обґрунтувала такі задачі дослідження:–

аналіз існуючих методів формування знань з даних та генерації асоціативних правил;–

подальший розвиток методу побудови логічних залежностей між небінарними ознаками об’єктів в базах даних у вигляді агрегованих асоціативних правил;–

проведення порівняльного аналізу характеристик простих і агрегованих асоціативних правил;–

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

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

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

реалізація результатів, що отримано, у вигляді програмної системи побудови узагальнених асоціативних правил.

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

Предметом дослідження є методи генерації й характеристики асоціативних правил в базах даних.

Методи дослідження. Для досягнення поставленої в роботі мети використовувалися методи математичної логіки для побудови агрегованих асоціативних правил в базах даних; методи математичної статистики й теорії інформації для аналізу стандартних характеристик асоціативних правил й розробці системи характеристик для оцінки асоціативних залежностей.

Наукова новизна результатів дисертаційної роботи. Вирішення поставлених задач дозволило автору одержати такі результати:

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

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

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

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

Метод оцінки асоціативних правил з точки зору теорії інформації й оцінка "цікавості" асоціації використано при розробці алгоритмів обробки інформації в інтелектуальних базах даних автоматизованої системи "Стандарти та нормативи", про що свідчить акт реалізації ДП НДТІП від 05.06.2004 року.

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

Особистий внесок здобувача. Всі результати дисертації отримані автором самостійно. У роботі [3], яка виконана без співавторів, надається порівняльна характеристика параметрів простих і агрегованих асоціативних правил і пропонується метод розрахунку рівнів підтримки й довіри агрегованих асоціативних залежностей, який дозволяє отримувати ці параметри аналітичних шляхом (без сканування бази даних). У роботах, які опубліковані у співавторстві, автору належать: [1,7] – запропонування підходу до визначення найбільш інформативних ознак об’єктів з використанням апарату алгебри кінцевих предикатів; [2] – розробка методу отримання агрегованих асоціативних правил для небінарних ознак об’єктів; [4] – проведення обґрунтування системи характеристик асоціативних правил і отримання формули для розрахунку узагальненої характеристики асоціації – інформативності; [5] – проведення аналізу впливу стандартних характеристик асоціативного правила на його інформативність; [6] – розробка програми генерації агрегованих асоціативних правил.

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

Міжнародній науково-практичній конференції студентів, аспірантів та молодих вчених "Комп’ютери. Програми. Інтернет. 2003" (21-23 квітня 2003 р., м. Київ, КПІ) [8];

II-й (16-17 квітня 2003 р.) конференції молодих вчених ХВУ [9];

8-му Міжнародному молодіжному форумі "Радіоелектроніка і молодь в XXI столітті" (13-15 квітня 2004 р., м. Харків, ХНУРЕ) [10];

6-й Міжнародній науково-практичній конференції "Системний аналіз та інформаційні технології" (1-3 липня 2004 р., м. Київ, КПІ) [11];

5-й Міжнародній конференції "Штучний інтелект-2004" (20-25 вересня 2004 р., с. Кацивелі, ІПШІ, м. Донецьк) [12].

Публікації. За темою дисертаційної роботи опубліковано 12 науково-технічних публікацій, з них: 7 статей (1 без співавторів) у виданнях, включених до переліку видань ВАК України, у яких можуть публікуватися результати дисертаційних робіт на здобуття наукового ступеня доктора і кандидата технічних наук; 5 публікацій у збірниках праць і тез науково-технічних конференцій, форумів.

Структура та обсяг роботи. Дисертація складається зі вступу, чотирьох розділів, висновків, списку використаних джерел і додатків. Повний обсяг роботи – 148 сторінок, з них основного тексту – 123 сторінки. Дисертація містить 2 додатка на 15 сторінках, список використаних джерел з 106 найменувань на 10 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

Проаналізована деяка неясність в англомовній й російськомовній термінологіях, щодо процесу формування знань з даних (Data Mining та Knowledge Discovery). Наведено етапи процесу формування знань з даних – попередня обробка даних, виділення регулярностей (Data Mining), саме формування знань.

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

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

Наведено визначення асоціативного правила як виразу імплікативного виду XY, (XL, YL, де L=I1,I2,...,Im – множина ознак об’єктів в базі даних (БД)). Причому XY=. Зазначено, що асоціативне правило XY має рівень довіри (Confidence – скор. Conf(XY)) c, якщо c% записів в БД, які містять X, також містять Y. Правило XY має підтримку (Support – скор. Sup(XY)) s, якщо s% записів в БД містять XY. Таким чином, проблема пошуку асоціативних правил складається в генерації всіх асоціативних правил, які долають задані пороги підтримки й довіри, тобто мають Support ? minSupport и Confidence ? minConfidence.

Охарактеризовано загальний підхід до пошуку асоціативних правил в БД, що складається з двох етапів: знаходження великих наборів ознак, які долають заданий рівень підтримки (так званих покрить), і саме оформлення асоціативних правил, яке складається з розбиття покриття на підмножини (якщо S – покриття, то для кожних непустих S1S і S2=S–S1 асоціативним правилом є S1S2, якщо має необхідний рівень довіри). Найбільш складним етапом є знаходження покрить.

Проаналізовано відомі на теперішній час алгоритми знаходження асоціативних правил: AIS, Apriori, AprioriTid, AprioriHybrid, Sampling, PARTITION, які реалізують методи обмеженого перебору та алгоритми FP–growth і алгоритм Amir, засновані на методі побудови дерева покрить.

На основі проведеного аналізу визначено основні недоліки, існуючих методів. До таких треба віднести: по-перше, побудова асоціативних правил тільки виду A1A2...AiB1B2...Bj, тобто, у правій та лівій частинах знаходиться кон’юнкція ознак. У багатьох ситуаціях, існує потреба в знаходженні асоціативних правил іншого виду: (або – асоціації з запереченням однієї чи декількох ознак), а також (A11...A1n)(A21...A2k)...(B11...B1j), коли ознаки можуть приймати значення з множини можливих (тобто не є бінарними величинами, Ai{Ai1,Ai2,...Ain}). По-друге, більшість алгоритмів показує незадовільні результати при знаходженні покрить з малою підтримкою. Існує забагато прикладних задач, котрі потребують знаходження саме малих покрить: медичні випадки, причини відмови апаратури та ін. Одним з шляхів усунення цих недоліків є знаходження узагальнених асоціацій (агрегування ознак). По-третє, двох характеристик – Support і Confidence недостатньо для оцінки асоціативного правила. Зазначено, що розуміння цієї проблеми привело до того, що в літературі, присвяченій цьому питанню, стали пропонуватись додаткові й альтернативні характеристики асоціативних правил: "цікавість", кореляція, рівень покращення, очікуваний рівень ймовірності, узагальнена міра асоціації.

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

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

Для опису небінарних величин використано апарат алгебри кінцевих предикатів, тобто якщо ознака Xj об’єкту може приймати значення з множини A={a1,a2,...,an}, то така ознака може описуватись за допомогою кінцевого предикату наступним чином:

Зазначено, що мають місце наступні тотожності:

,

,

які дозволяють не використовувати окремі описи для асоціації з запереченням, тобто . У випадку бінарних ознак для їх опису використовується унарний предикат, що розрізняє два значення – 0 и 1: X0 и X1.

Для отримання дерева покрить, яке необхідне для роботи методу генерації узагальнених асоціативних правил, використовується модифікований алгоритм побудови дерева, який полягає у наступному (рис.1).

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

Дано опис методу генерації агрегованих асоціативних правил на основі об’єднання гілок дерева покрить, який полягає у наступному. Якщо потребується знайти узагальнені покриття, які містять значення ознаки и , то визначається список гілок дерева покрить з даними значеннями ознаки P. Ці гілки групуються наступним чином: в одну групу входять гілки, що містять ознаки на однакових ярусах дерева покрить. В цьому списку існують гілки, які мають однакові префікси: S11, S12,…S1i (такі гілки обов’язково існують, тому що всі гілки містять хоча б один загальний префікс – нульову строку ). У кожній групі можуть існувати гілки з різними загальними префіксами. Знаходимо S=max{Sj}, , де k – кількість різних однакових префіксів в даній групі гілок. Ці гілки об’єднуються по принципу: S(1+2+…+i). Рядок 1+2+…+i формується таким чином: між значеннями ознаки з одного ярусу ставиться знак . Отримана агрегована гілка додається в свою групу. Далі цей процес продовжується ітеративно до тих пір, поки існують гілки з однаковими префіксами. Рівень підтримки такого об’єднання дорівнює сумі рівнів підтримки гілок, що об’єднуються.

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

Таблиця 1

Фрагмент бази даних

Запис

Ознака | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10

X | a1 | a2 | a1 | a2 | a2 | a3 | a1 | a3 | a3 | a1

Y | b1 | b3 | b1 | b3 | b3 | b1 | b2 | b1 | b2 | b2

Z | c2 | c1 | c2 | c3 | c1 | c1 | c2 | c2 | c1 | c2

Цей фрагмент бази даних містить ознаку X, яка може приймати значення a1, a2, a3 (рік клієнта компанії мобільного зв’язку: до 30 років, від 30 до 50, більш 50), ознаку Y, яка приймає значення b1, b2, b3 (місце проживання клієнтів: м. Харків, м. Богодухів, м. Куп’янськ) та ознаку Z, яка відповідно приймає значення c1, c2, c3 (номери пакетів послуг, що надаються компанією).

Побудоване для даного фрагменту БД дерево показано на рис. 2.

Якщо рівень підтримки задано minSupport=3, то отримано наступні прості покриття: (Support=4), (Support=3), (Support=3), з яких можна отримати асоціативні правила типа:

1) (Sup=4; Conf=1) – "Якщо клієнту до 30 років, то він обирає пакет послуг № 2";

2) (Sup=3; Conf=0,75) –"Якщо клієнт житель м. Харкова, то він обирає пакет послуг № 2";

3) (Sup=3; Conf=0,6) – "Якщо клієнт обирає пакет послуг № 2, то він житель м. Харкова" та ін.

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

Для вищезазначеного фрагменту бази даних отримано наступні агреговані покриття для значень ознаки и :

1) , Support=4;

2) , Support=3;

3) , Support=7;

4) , Support=7.

Генерація агрегованих асоціативних правил проводиться згідно стандартній методиці. Наприклад, з покриття можуть бути отримані такі асоціативні правила:

1) (Sup=4; Conf=1) – "Якщо клієнту до 30 років і він обирає пакет послуг № 2, то він є жителем м. Харкова або м. Богодухова";

2) (Sup=4; Conf=0,8) – "Для тих клієнтів, які обирають пакет послуг № 2, характерна наступна залежність: їм не більш 30 років, й вони є переважно жителями м. Харкова або м. Богодухова";

3) (Sup=4; Conf=0,8) – "Клієнти, що є жителями м. Харкова або м. Богодухова й такими, що обирають пакет послуг № , переважно є людьми до 30 років" та ін.

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

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

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

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

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

Рівень довіри відповідно до запропонованого методу розраховується так:

1) ; 2) ;

таким чином: ;

3) ; 4) ;

таким чином: .

Остаточно: .

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

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

Доведено, що двох характеристик – підтримки й рівня довіри недостатньо для оцінки асоціації. Запропоновано у доповнення до підтримки й рівня довіри використовувати таку характеристику, як рівень покращення (Improvement – скор. Imp), яка визначається наступним чином:

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

Показано, що:

Sup(XY)=P(XY);

;

Визначено обмеження, що накладаються на характеристики асоціації:

1) 0 ? Sup(XY) ? 1;

2) Sup(XY) ? Conf(XY) ?1;

3)

.

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

;

де Pij=P((X~xi)(Y~yj)) – ймовірність того, що X знаходиться в стані xi, а Y – в стані yj;

pi= P (X~xi) – ймовірність того, що X знаходиться в стані xi;

rj= P(Y~yj) – ймовірність того, що Y знаходиться в стані yj.

Для асоціативних правил взаємна інформація буде визначатися як:

.

Доведено, що в окремому (бінарному) випадку ця характеристика може бути розрахована на основі трьох відомих характеристик: Sup, Conf, Imp.

Виведено формулу для отримання інформативності асоціативного правила:

.

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

Проаналізовано залежність інформативності асоціації від трьох параметрів – підтримки, рівня довіри й рівня покращення і доказано, що твердження про те, що чим параметри більше, тим асоціація краще, не відповідає дійсності [6]. Встановлено, що інформативність асоціативного правила прямо залежить від підтримки й рівня покращення, але не від рівня довіри. Показано, що при зростанні рівня довіри інформативність спочатку зменшується, а потім зростає (графік залежності інформативності від рівня довіри має мінімум в точці ). Наприклад, при Sup=0,3 і Imp=2 правило з Conf=0,6 буде нести більш інформації (IXY 0,4), чим правило з Conf=0,78 (IXY 0,3), хоч рівень довіри другого у 1,3 рази вище.

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

Зазначено, що такі показники асоціативного правила як рівень підтримки та рівень покращення Sup и Imp є "симетричними", тобто, Sup(XY)=Sup(YX) та Imp(XY)=Imp(YX). Таким чином, точніше буде говорити про рівень підтримки та покращення не асоціативного правила, як це прийнято в літературі, а асоціації. Те ж справедливо й про повну взаємну інформацію. Цим пояснюється той факт, що при збільшенні Sup та Imp зростає й інформативність – асоціація посилюється. Рівень довіри Conf є "направленим" параметром, тобто, Conf(XY)?Conf(YX) і характеризує саме асоціативне правило. Цим пояснюється непряма залежність інформативності от рівня довіри.

Розширено поняття R-"цікавості" асоціативного правила, яке використовується для фільтрації отриманих залежностей з метою скорочення їх кількості і визначається як перевищення у R разів рівня довіри або підтримки над очікуваними. Очікувані значення розраховуються для асоціацій, що мають дві чи більш ознак у лівій частині правила з припущенням про їх статистичну незалежність. Інформативність дозволяє оцінити "цікавість" у випадку, коли, наприклад, Sup правила в R1 разів більш очікуваної, а Conf в R2 разів менш і навпаки. "Цікавість" асоціації визначається як перевищення інформативності асоціації над очікуваною інформативністю. Це дозволяє розглядати інформативність як узагальнення поняття R-"цікавості" асоціативного правила.

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

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

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

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

ВИСНОВКИ

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

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

В дисертації отримано наступні основні результати:

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

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

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

4. Запропонований метод оцінки інформативності асоціації на основі стандартних характеристик асоціативного правила дозволяє завдати лінійний порядок в трьохмірному просторі Support-Confidence-Improvement і скоротити розмірність задачі оцінювання асоціації. Ця характеристика враховує всі загальноприйняті характеристики асоціативного правила та її обґрунтованість не викликає сумніву з теоретичної точки зору, так як в основі її побудови лежать фундаментальні принципи математичної теорії інформації. Інформаційна характеристика асоціації може використовуватися також для фільтрації отриманих асоціативних правил – відбракування залежностей, інформативність яких нижче за зазначений рівень. Це спрощує процес відбору й очистки отриманих правил.

5. Результати дисертаційної роботи впроваджені та довели свою ефективність при розробці алгоритмів обробки інформації в інтелектуальних базах даних автоматизованої системи управління електронними документами "Стандарти та нормативи" науково-дослідного інституту (акт реалізації ДП НДТІП від 05.06.2004 р.), а також при виявленні логічних залежностей в базах даних при проведенні науково-дослідної роботи "Дуель" Харківського військового університету (акт реалізації Наукового центру Військ ППО від .02.2004 р.).

Результати дисертаційної роботи було використано в навчальному процесі Харківської академії культури під час проведення лекційних занять.

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

СПИСОК ОПУБЛІКОВАНИХ АВТОРОМ ПРАЦЬ

ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Ситников Д.Э., Титова Е.В. Описание минимальных наборов признаков в приближенных множествах // Радиоэлектроника и информатика. – 2003.–№ 1(22). – С.137-140.

2. Ситников Д.Э., Титова Е.В. Метод поиска обобщенных ассоциативных зависимостей между дискретными признаками // Системи обробки інформації. – Харьков: НАНУ, ПАНМ, ХВУ. – 2002. – Вип. № 6(22). – С. .

3. Титова Е. В. Сравнительная характеристика простых и расширенных ассоциативных правил для признаков объектов в базах данных // Системи обробки інформації – Харьков: НАНУ, ПАНМ, ХВУ. – 2003. – № . – С. 31-37.

4. Ситников Д.Э., Титова Е.В. Полная взаимная информация как обобщенный показатель качества ассоциативных зависимостей с бинарными признаками // Системи обробки інформації. – Харьков: НАНУ, ПАНМ, ХВУ. – 2004. – Вип. № 2. – С. .

5. Ситников Д. Э., Титова Е. В. Влияние стандартных параметров ассоциативного правила на его информативность // Системи обробки ін-формації – Харьков: НАНУ, ПАНМ, ХВУ. – 2004. – № 4. – С. .

6. Ситников Д.Э., Титова Е.В., Романенко О.А. Система поиска обобщенных ассоциативных правил в базах данных // Збірник наукових праць Інституту проблем моделювання в енергетиці НАН України. – К.: НАН України. – 2004. – Вып. 25. – С. .

7. Ситников Д.Э., Вильчинская О.С., Кравец Н.С., Титова Е.В. Определение минимального набора признаков, адекватно описывающих нечеткое множество // Вестник национального технического университета "ХПИ". – Харьков: ХНИУ ХПИ. – 2002.-№20. – С.65-70.

8. Титова Е.В. Метод генерации расширенных ассоциативных правил для признаков объектов в базах данных // Збірка тез доповідей учасників Міжнародної науково-практичній конференції студентів, аспірантів та молодих вчених "Комп'ютери. Програми. Інтернет. 2003". – К.: Політехніка. – 2003. – С. 62.

9. Тітова О.В. Виведення асоціативних правил для групи ознак об’єктів у базах даних // Збірник тез доповідей ІІ наукової конференції молодих вчених ХВУ. – Харьков: ХВУ, 2003. – Ч.1. – С. .

10. Титова Е.В. Оценка качества ассоциативных правил с точки зрения теории информации // Материалы 8-го Международного молодежного форума "Радиоэлектроника и молодежь в XXI веке". – Харьков: ХНУРЭ, 2004. – Ч.2. – С. .

11. Титова Е.В. Информативность ассоциативных правил – критерий оценки качества логических зависимостей между признаками объектов в базе данных // Тези доповідей учасників VI Міжнародної науково-практичної конференції студентів, аспірантів та молодих вчених "Системний аналіз та інформаційні технології". – К.: КПІ. – 2004. – С. .

12. Ситников Д.Э., Титова Е.В. Информативность – интегральный показатель качества ассоциативных правил в базах данных // Материалы Международной научно-технической конференции "Искусственный интеллект. Интеллектуальные и многопроцессорные системы". – Таганрог: Изд-во ТРТУ. – 2004. – С. .

АНОТАЦІЯ

Тітова О. В. Методи побудови та оцінки агрегованих асоціативних правил в інтелектуальних базах даних. – Рукопис.

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

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

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

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

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

АННОТАЦИЯ

Титова Е.В. Методы построения и оценки агрегированных ассоциативных правил в интеллектуальных базах данных. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.23 – Системы и средства искусственного интеллекта. – Харьковский национальный университет радиоэлектроники, Харьков, 2006.

Диссертация посвящена вопросам автоматизированного формирования знаний из данных, распознаванию скрытых закономерностей (образов, паттернов) и моделированию принципов их представления на основе формальных логик.

В диссертационной работе получил дальнейшее развитие метод генерации агрегированных ассоциативных правил на основе объединения ветвей дерева покрытий. Это позволяет находить логические закономерности в данных для небинарных признаков. Проведен сравнительный анализ характеристик простых и агрегированных ассоциативных правил и показано, что агрегированные ассоциации обладают более высоким уровнем поддержки и доверия. Благодаря этому, количество агрегированных ассоциативных правил, получаемых в процессе генерации логических зависимостей в данных не меньше (больше), чем простых. Таким образом, эффективность нахождения ассоциативных правил в базах данных увеличивается.

Предложен метод расчета характеристик агрегированных ассоциативных правил, позволяющий рассчитывать их на основе характеристик простых ассоциаций путем декомпозиции. Это значительно упрощает процесс оценки обобщенных ассоциативных правил и не требует дополнительного сканирования базы данных. Показано, что декомпозиция агрегированного ассоциативного правила может осуществляться в любом направлении. В работе сформулированы и доказаны теоремы, которые легли в основу этого метода.

Проанализированы характеристики ассоциативных правил – уровень поддержки, уровень доверия и уровень улучшения и показано, что для всесторонней и полной оценки ассоциации нужны три параметра. Предложен метод оценки информативности ассоциации, позволяющий рассчитывать интегральную характеристику ассоциации, тем самым эффективно сократить размерность задачи оценивания ассоциации, что упрощает процесс отбора и очистки полученных правил. Интегральная характеристика ассоциативной зависимости – полная взаимная информация рассчитывается на основе трех общепринятых характеристик и позволяет сравнивать между собой ассоциативные правила с разными значениями уровней доверия и поддержки, устанавливая линейный порядок при оценке полученных зависимостей. Кроме того, данная характеристика может быть рассчитана при любых значениях параметров ассоциации.

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

Расширено понятия "интересности" обобщенного ассоциативного правила, как превышения реальной информативности ассоциации над ожидаемой. Это позволяет более эффективно фильтровать полученные логические зависимости с целью выделения из них наиболее информативных и значимых.

На основании предложенных методов разработана программа построения ассоциативных правил, которая позволила провести исследования по выделению логических зависимостей в интеллектуальных базах данных "Стандарты и нормативы", разрабатываемых Научно-исследовательским технологическим институтом приборостроения, и в базах данных, содержащих информацию по вооружению и военной технике в Научном центре войск противовоздушной обороны при Харьковском военном университете.

Приведены данные тестирования разработанной программы и показаны ее преимущества перед существующими программными продуктами. Показано, что время работы растет нелинейно с увеличением количества обрабатываемых записей в базе данных, что связано с особенностями работы алгоритма, реализующего предложенные методы.

Ключевые слова: искусственный интеллект, формирование знаний из данных, база знаний, логические закономерности в данных, паттерн, агрегированные ассоциативные