Виявлення залежностей даних
У статті описується розроблений алгоритм пошуку залежностей у підмножинах об’єктів досліджуваного набору даних. Даний алгоритм дозволяє ефективно виявляти асоціативні залежності за заданими критеріями якості. Застосування розробленого методу виявлення залежностей в даних можливе в багатьох предметни...
Збережено в:
| Опубліковано в: : | Математичні машини і системи |
|---|---|
| Дата: | 2012 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут проблем математичних машин і систем НАН України
2012
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/83972 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Виявлення залежностей даних / О.Ю. Пшеничний // Мат. машини і системи. — 2012. — № 1. — С. 89-97. — Бібліогр.: 4 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-83972 |
|---|---|
| record_format |
dspace |
| spelling |
Пшеничний, О.Ю. 2015-07-01T13:17:21Z 2015-07-01T13:17:21Z 2012 Виявлення залежностей даних / О.Ю. Пшеничний // Мат. машини і системи. — 2012. — № 1. — С. 89-97. — Бібліогр.: 4 назв. — укр. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/83972 004.9 У статті описується розроблений алгоритм пошуку залежностей у підмножинах об’єктів досліджуваного набору даних. Даний алгоритм дозволяє ефективно виявляти асоціативні залежності за заданими критеріями якості. Застосування розробленого методу виявлення залежностей в даних можливе в багатьох предметних галузях та дозволяє виявити нові закономірності в даних, що покращує роботу фахівців та якість прийнятих ними рішень. В статье описан разработанный алгоритм поиска зависимостей в подмножествах объектов исследуемого набора данных. Данный алгоритм позволяет эффективно выявлять ассоциативные зависимости в данных по заданным критериям качества. Использование разработанного метода поиска зависимостей в данных возможно в многих предметных областях и позволяет выявить новые закономерности в данных, что улучшает работу специалистов и качество принятых ими решений. The worked out algorithm of data search dependencies in the object subsets of investigated dataset is described in the article. This algorithm allows effectively reveal associative dependencies based on specified quality criteria. Application of developed data dependency detection method is possible in many specializations and allows finding new data patterns which improves work and decisions quality of specialists. uk Інститут проблем математичних машин і систем НАН України Математичні машини і системи Нові інформаційні і телекомунікаційні технології Виявлення залежностей даних Выявление зависимостей данных Data dependency detection Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Виявлення залежностей даних |
| spellingShingle |
Виявлення залежностей даних Пшеничний, О.Ю. Нові інформаційні і телекомунікаційні технології |
| title_short |
Виявлення залежностей даних |
| title_full |
Виявлення залежностей даних |
| title_fullStr |
Виявлення залежностей даних |
| title_full_unstemmed |
Виявлення залежностей даних |
| title_sort |
виявлення залежностей даних |
| author |
Пшеничний, О.Ю. |
| author_facet |
Пшеничний, О.Ю. |
| topic |
Нові інформаційні і телекомунікаційні технології |
| topic_facet |
Нові інформаційні і телекомунікаційні технології |
| publishDate |
2012 |
| language |
Ukrainian |
| container_title |
Математичні машини і системи |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| format |
Article |
| title_alt |
Выявление зависимостей данных Data dependency detection |
| description |
У статті описується розроблений алгоритм пошуку залежностей у підмножинах об’єктів досліджуваного набору даних. Даний алгоритм дозволяє ефективно виявляти асоціативні залежності за заданими критеріями якості. Застосування розробленого методу виявлення залежностей в даних можливе в багатьох предметних галузях та дозволяє виявити нові закономірності в даних, що покращує роботу фахівців та якість прийнятих ними рішень.
В статье описан разработанный алгоритм поиска зависимостей в подмножествах объектов исследуемого набора данных. Данный алгоритм позволяет эффективно выявлять ассоциативные зависимости в данных по заданным критериям качества. Использование разработанного метода поиска зависимостей в данных возможно в многих предметных областях и позволяет выявить новые закономерности в данных, что улучшает работу специалистов и качество принятых ими решений.
The worked out algorithm of data search dependencies in the object subsets of investigated dataset is described in the article. This algorithm allows effectively reveal associative dependencies based on specified quality criteria. Application of developed data dependency detection method is possible in many specializations and allows finding new data patterns which improves work and decisions quality of specialists.
|
| issn |
1028-9763 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/83972 |
| citation_txt |
Виявлення залежностей даних / О.Ю. Пшеничний // Мат. машини і системи. — 2012. — № 1. — С. 89-97. — Бібліогр.: 4 назв. — укр. |
| work_keys_str_mv |
AT pšeničniioû viâvlennâzaležnosteidanih AT pšeničniioû vyâvleniezavisimosteidannyh AT pšeničniioû datadependencydetection |
| first_indexed |
2025-11-24T03:47:58Z |
| last_indexed |
2025-11-24T03:47:58Z |
| _version_ |
1850839752104738816 |
| fulltext |
© Пшеничний О.Ю., 2012 89
ISSN 1028-9763. Математичні машини і системи, 2012, № 1
УДК 004.9
О.Ю. ПШЕНИЧНИЙ
ВИЯВЛЕННЯ ЗАЛЕЖНОСТЕЙ ДАНИХ
Анотація. У статті описується розроблений алгоритм пошуку залежностей у підмножинах
об’єктів досліджуваного набору даних. Даний алгоритм дозволяє ефективно виявляти асоціативні
залежності за заданими критеріями якості. Застосування розробленого методу виявлення залеж-
ностей в даних можливе в багатьох предметних галузях та дозволяє виявити нові закономірності
в даних, що покращує роботу фахівців та якість прийнятих ними рішень.
Ключові слова: залежність даних, набір даних, алгоритм, аналіз даних.
Аннотация. В статье описан разработанный алгоритм поиска зависимостей в подмножествах
объектов исследуемого набора данных. Данный алгоритм позволяет эффективно выявлять ассо-
циативные зависимости в данных по заданным критериям качества. Использование разработан-
ного метода поиска зависимостей в данных возможно в многих предметных областях и позволяет
выявить новые закономерности в данных, что улучшает работу специалистов и качество приня-
тых ими решений.
Ключевые слова: зависимость данных, набор данных, алгоритм, анализ данных.
Abstract. The worked out algorithm of data search dependencies in the object subsets of investigated da-
taset is described in the article. This algorithm allows effectively reveal associative dependencies based
on specified quality criteria. Application of developed data dependency detection method is possible in
many specializations and allows finding new data patterns which improves work and decisions quality of
specialists.
Keywords: data dependency, dataset, algorithm, data analysis.
1. Вступ
Аналіз результатів будь-яких досліджень чи спостережень є невід’ємною частиною проце-
су дослідження предметної області. Напрям аналізу інформації швидко зростає і поширю-
ється на нові й нові галузі науки і техніки. Водночас з галузевим поширенням методи ана-
лізу даних застосовуються до все більших наборів даних. Це потребує розробки нових під-
ходів та алгоритмів у даній галузі. Хоча на сьогодні наявні потужні методи та засоби ана-
лізу даних у деяких вузьких галузях, наприклад, CLASSIFI (Department of Pathology, UT
Southwestern Medical Center) [1], BiNGO (Department of Plant Systems Biology, VIB/Ghent
University) [2] та EASE (National Institute of Allergy and Infectious Diseases) [3], проте біль-
шість зібраної інформації не аналізується належним чином перш за все через недостатні
обчислювальні потужності для наявних алгоритмів і відсутність ефективніших методів
аналізу цих даних. Внаслідок цього багато залежностей предметних областей залишаються
невідомими експертам та аналітикам і це не дозволяє приймати правильні рішення у про-
блемних ситуаціях, що приносить великі збитки як економічні, так і екологічні, медичні та
ін. Тому розробка алгоритму, застосовного до широкого спектра схем даних, є надзвичай-
но актуальною задачею.
Метою даного дослідження є розробка ефективного алгоритму аналізу широкого
спектра даних, що дозволить фахівцям предметних областей краще зрозуміти залежності в
цих галузях та приймати правильні рішення у проблемних ситуаціях.
2. Основна частина
Аналіз великих обсягів даних потребує виявлення груп атрибутів, що утворюють функціо-
нальні залежності. Проте в реальних умовах значно частіше зустрічаються набори даних, в
90 ISSN 1028-9763. Математичні машини і системи, 2012, № 1
яких важливі залежності визначені тільки на деякій підмножині значень групи ключових
атрибутів. Називатимемо такі залежності частковими функціональними залежностями
(ЧФЗ).
Тобто, часткова функціональна залежність – це ФЗ в деякій селекції основного від-
ношення.
{ } { } ' ': , , , , :p i i j jF K a a A D a a A R R K D R= ∈ = ∈ ⊂ → . (1)
Багато залежностей також мають не чітко детермінований характер. Називатимемо
їх імовірнісними продукційними залежностями (ІПЗ).
Імовірнісна продукційна залежність – це продукційне правило в селекції основного
відношення, яке справджується для значущої кількості об’єктів цієї селекції. Поріг значу-
щості повинен визначатись експертним шляхом або виходячи з розрахунків імовірності
помилкового виділення цієї залежності.
{ } { } ( ): , , , ,:I i i j jF K a a A D a a A P k K d D p= ∈ = ∈ ∈ → ∈ = . (2)
Тут k та d – кортежі значень деяких груп атрибутів K та D відповідно.
Основним показником достовірності такої залежності є відношення кількості
об’єктів, для яких має місце така ФЗ, до кількості об’єктів у селекції:
( ) ( )
( )
k K d D
I
k K
R
P F
R
σ
σ
∈ ∧ ∈
∈
= . (3)
Позначатимемо ІЗ IF з використанням цієї величини як імовірність виконання про-
дукційного правила:
( )P k K d D p∈ → ∈ = . (4)
При потребі неважко розширити поняття до імовірності виконання довільних про-
дукційних правил. Але пошук складних продукційних правил у великих наборах даних є
дуже складною і обчислювально важкою операцією, тому вони використовуються рідко.
Введення поняття імовірнісних залежностей, на перший погляд, надлишкове, оскі-
льки з множини об’єктів, на яких визначена така залежність, завжди можна вибрати підм-
ножину, на якій визначена чітка часткова функціональна залежність. Але за умови, що
значення групи ключових атрибутів такої залежності мають змістовне сортування у пред-
метній області, опис залежностей може бути здійснений значно простіше та інформатив-
ніше. Для наочності розглянемо приклад:
Приклад 1.
Таблиця 1. Залежність типу вагона, в
якому їде людина, від дальності поїздки
i – номер
опитаного
L – дальність
поїздки,
x100км
T – клас вагона
1 1 3
2 1 2
3 1 3
4 3 1
5 2 1
6 1 3
7 2 1
8 2 2
9 3 1
З табл. 1 можна зробити висно-
вок.
Такі ЧФЗ:
( ){ }9..1, LTi → ,
{ }3TL → ,
{ }3LT → ,
( ) ( ) ( ){ }2;2,2;1, iTL → .
Розглядаються тільки максима-
льно розширені ЧФ, тобто, наприклад,
залежність ( ){ }3,2,1, LTi → не береться
ISSN 1028-9763. Математичні машини і системи, 2012, № 1 91
до уваги, оскільки перша ЧФ з вищенаведених повністю визначає її.
Ці залежності справджуються для всіх об’єктів, які мають вказану комбінацію ви-
значальних атрибутів залежності, але інформативність таких залежностей часто мала через
надмірний детермінізм – будь-який виняток зруйнує залежність і будь-який випадковий
шум даних може утворити нову залежність.
Розглянемо деякі ІПЗ з попереднього прикладу:
( ) ( )( ) 13;1;1 ==→= LTiP ,
( ) 75,031 ==→= TLP ,
{ } { }( ) 12,13,2 =∈→∈ TLP ,
{ }( ) 8,013,2 ==→∈ TLP ,
( ) 113 ==→= LTP ,
( ) 5,031 ==→= LTP .
Такі дані значно інформативніші і корисніші для аналізу. Вони захищені від шуму
та випадкових помилок і навіть дозволяють виявити ці помилки. Тому пошук саме таких
залежностей і є завданням сучасного аналізу даних. Задачу пошуку мінімального покриття
часто використовують в аналізі даних [4].
Ще одним важливим параметром ІПЗ є її достовірність – імовірність відхилення ве-
личини ( )IFP не більше, ніж на задане значення δ :
( ) ( )( )*
I IP P F P Fδ− ≤ , (5)
де ( )IFP* – справжнє значення виконання залежності IF .
Обчислення ( )IFP* напряму в більшості випадків неможливе, оскільки відсутня ін-
формація про всі можливі комбінації значень атрибутів об’єктів відношення. Але можна
оцінити достовірність залежності, виходячи з кількості об’єктів, для яких залежність вико-
нується, комбінацій задіяних атрибутів та інших параметрів.
Легко зауважити, що ЧФ є лише частковим випадком ІПЗ при ( ) 1=IFP . Тому за-
вдання пошуку залежностей у даних можна звести до пошуку ІПЗ.
У даній роботі пропонується метод виявлення ІПЗ в наборах даних, опираючись на
задані параметри імовірності виконання та достовірності цих залежностей.
Розглянемо для початку пошук простих залежностей типу
( )1 1 0P s s t t p= → = ≥ , (6)
де 0p – порогове значення імовірності виконання шуканих залежностей, s , t – деякі атри-
бути відношення, в якому здійснюється пошук залежностей.
Для обчислення необхідних імовірностей та пошуку таких ІПЗ необхідно перебрати
всі пари атрибутів ( ) AtAsts ∈∈ ,,; і для кожної комбінації здійснити прохід по об’єктах
відношення, заповнюючи для кожного значення атрибута s кількість його повторень в
об’єктах та словник відповідних значень атрибута t із вказанням кількості повторів. Після
таких операцій усі залежності виду (6) при 00 =p будуть збережені в описаній структурі
даних. Відбір потрібних ІПЗ з цієї структури для довільного 0p є тривіальною задачею
фільтрації. Складність описанного алгоритму – ( )nmO ⋅2 , де m – кількість атрибутів від-
ношення, n – кількість об’єктів у відношенні.
92 ISSN 1028-9763. Математичні машини і системи, 2012, № 1
Рис. 1. Графічне представлення
об’єднання ІЗ типу (7)
Хоча складність вищеописаного алгоритму і залежить не лінійно від кількості атри-
бутів відношення, проте переважно навіть дуже складні дані мають не більше декількох
сотень атрибутів. Окрім того, алгоритм має добрі дані розпаралелювання, тобто, його мо-
жна елементарно модифікувати для виконання на багатопроцесорних машинах, кластерах
чи грідах.
Розширимо задачу (6) до пошуку залежностей виду
( )1 0P s s t T p= → ∈ ≥ . (7)
Маючи дані про залежності виду (6), можна розв’язати дану задачу, аналізуючи ли-
ше підгрупу залежностей виду (6), що має спільну частину 1ss = . Це легко довести, вихо-
дячи з визначення ІПЗ та формули (3): будь-який об’єкт, для якого діє залежність
( ) pQqssP ≥∈→= 2 , не виконує залежність (7) і, відповідно, не змінює значення
( )TtssP ∈→= 1 . З іншої сторони, додавання чи вилучення об’єкта зі значенням 1ss = не-
одмінно впливає на імовірність ( )TtssP ∈→= 1 , якщо це значення більше нуля. Отже,
при пошуку залежностей виду (7) необхідно і достатньо розглянути всі залежності виду
(6), у яких умовна частина предиката співпадає з шуканою залежністю.
Щодо імовірності виконання залежності (7) на заданому наборі даних, то з (3) ви-
пливає, що
{ }( ) { } ( )
( )
( ) ( )
( )
( ) ( )
1 2 1 2
1 1
,
1 1 2
1 1 1 2
,
.
t t t t t t t
s s s s
R R R
P s s t t t
R R
P s s t t P s s t t
σ σ σ
σ σ
∈ = =
= =
+
= → ∈ = = =
= = → = + = → =
(8)
Тобто, об’єднання залежностей виду (6) у за-
лежності від виду (7) збільшить імовірність вико-
нання нової залежності. Для більш загального ви-
падку об’єднання двох залежностей виду (7) фор-
мула обчислення імовірності виконання агрегатив-
ної залежності буде трохи складнішою, оскільки
множини значень результуючої частини предиката
можуть перекриватись (рис. 1).
Відповідно, виразимо з (3) імовірність вико-
нання такої ІПЗ:
( )
( )
( )
( ) ( ) ( )
( )
1 2
1
1 2 1 2
1
1 1 2
t T T
s s
t T t T t T T
s s
R
P s s t T T
R
R R R
R
σ
σ
σ σ σ
σ
∈ ∪
=
∈ ∈ ∈ ∩
=
= → ∈ ∪ = =
+ −
=
.
Використовуючи зворотне перетворення формули (3), легко помітити, що
( )
( )
( )1
1
1 1
t T
s s
R
P s s t T
R
σ
σ
∈
=
= = → ∈ ,
( )
( )
( )2
1
1 2
t T
s s
R
P s s t T
R
σ
σ
∈
=
= = → ∈ ,
ISSN 1028-9763. Математичні машини і системи, 2012, № 1 93
( )
( )
( )1 2
1
1 1 2
t T T
s s
R
P s s t T T
R
σ
σ
∈ ∩
=
= = → ∈ ∩ ,
і утворене відношення можна переписати простіше:
( ) ( ) ( ) ( )1 1 2 1 1 1 2 1 1 2P s s t T T P s s t T P s s t T P s s t T T= → ∈ ∪ = = → ∈ + = → ∈ − = → ∈ ∩ . (9)
Враховуючи обчислені значення імовірностей всіх атомарних залежностей (6),
кон’юнкція та диз’юнкція довільних множин значень атрибута T не потребує нових склад-
них обчислень для знаходження імовірності виконання об’єднаної залежності.
Ще одним варіантом об’єднання ІПЗ виду (6) є залежності
( )1 0P s S t t p∈ → = ≥ . (10)
Обчислення імовірності такої агрегативної залежності трохи складніше, ніж у попе-
редньому випадку і неможливе, якщо спиратись тільки на значення ( )1ttssP i =→= . Для
цього потрібно залишати імовірності залежностей виду (6) у вигляді звичайних дробів –
відношення кількості об’єктів, для яких залежність виконується до загальної кількості
об’єктів, відібраних умовною частиною предиката ІПЗ, як і було запропоновано в алгори-
тмі пошуку ІПЗ виду (6). Тоді, виходячи з формули (3),
{ }( )
1
1
i
i
i
i
i
s s t t
P s s t t
s s
= ∧ =
∈ → = =
=
∑
∑
. (11)
І знову ж, використовуючи вищеописану структуру даних, ця формула обчислюєть-
ся без додаткових проходів по таблиці.
Розглянемо тепер загальний вигляд шуканих залежностей:
( ) 0P s S t T p∈ → ∈ ≥ . (12)
Обчислення імовірності виконання такої залежності ґрунтується на попередніх мір-
куваннях та можливості розкладу такої залежності на складові ІПЗ типу (11):
( ) ( )
i i
j i
j
i
t T t T j
j
s s t t
P s S t T P s S t t
s s∈ ∈
= ∧ =
∈ → ∈ = ∈ → = =
=
∑
∑ ∑
∑
. (13)
Позначення, що використовувались до цих пір у статті, досить громіздкі, тому вве-
демо алгебру залежностей, визначену над четвірками
( ); ; ; IS T s S t T s S F∈ ∧ ∈ ∈ = , (14)
операціями об’єднання (+) та розщеплення (-) залежностей. Для додаткового спрощення
позначень введемо операцію проекції трійки IF на її атрибути (назвемо їх відповідно Pr
(Predicate), PrS, PrT (дочірні атрибути предиката TtSs ∈→∈ – множини S та T),
PN(Probability nominator), PD (Probability Denominator) і позначатимемо операцію квадра-
тними дужками, наприклад, [ ]PrIF , [ ]SFI Pr ).
Для типів ІПЗ, описаних формулами (6), (7), (10), (12), введемо позначення відпові-
дно AF , BF , CF , DF . Тоді операції об’єднання та розщеплення над залежностями цих
типів будуть визначені таким чином:
94 ISSN 1028-9763. Математичні машини і системи, 2012, № 1
[ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ]( )
[ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ]( )
[ ] [ ] [ ] [ ]
1 1 2 1 2
1 1 2 1 2 1
1 2 1 2
1 2 1 2 1 1 2 1 2
1 2 1 2
, Pr Pr Pr Pr ,
Pr ; Pr Pr ; ; ,
Pr Pr Pr Pr ,
Pr Pr ; Pr ; ; ,
Pr Pr Pr Pr ,
A A A A A
B A A A A A A
A A A A
A A C A A A A A A A
A A A A
D
F якщоF S F S F T F T
F F S F T F T F PN F PN F PT
якщоF S F S F T F T
F F F F S F S F T F PN F PN F PT F PT
якщо F S F S F T F T
F
= ∧ =
= ∪ +
= ∧ ≠
+ = = ∪ + +
≠ ∧ =
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]( )
[ ] [ ]( ) [ ] [ ]( )
1 2 1 2 1 2 1 2
1 2 1 2
Pr Pr ; Pr Pr ; ; ,
Pr Pr Pr Pr ,
A A A A A A A A
A A A A
F S F S F T F T F PN F PN F PT F PT
якщо F S F S F T F T
= ∪ ∪ + +
≠ ∧ ≠
(15)
[ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ]( )
[ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]( )
[ ] [ ]
1
, Pr Pr Pr Pr ,
Pr ; Pr Pr ; ; ,
Pr Pr Pr Pr ,
Pr Pr ; Pr Pr ; ; ,
Pr Pr ,
B B A A B
B B B A B A B
B A B A A B
D B A B A B A B A
B A
F якщоF S F S F T F T
F F S F T F T F PN F PN F PT
F F якщоF S F S F T F T
F F S F S F T F T F PN F PN F PT F PT
якщоF S F S
= ∧ ∈
= ∪ +
+ = = ∧ ∉
= ∪ ∪ + +
≠
(16 )
[ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ]( )
[ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ]( )
[ ] [ ]( ) [ ] [ ]( )
[ ] [ ] [ ] [ ]
1
1
2
, Pr Pr Pr Pr ,
Pr Pr ; Pr ; ; ,
Pr Pr Pr Pr ,
Pr ; Pr Pr ; ; ,
Pr Pr Pr Pr ,
Pr Pr ; Pr Pr ;
C A C C A
C C A C C A C A
A C C A
C A D C С A C A С
A C С A
D C A С A
F якщоF S F S F T F T
F F S F S F T F PN F PN F PT F PT
якщо F S F S F T F T
F F F F S F T F T F PN F PN F PT
якщо F S F S F T F T
F F S F S F T F T
∈ ∧ =
= ∪ + +
∉ ∧ =
+ = = ∪ +
∈ ∧ ≠
= ∪ ∪ [ ] [ ] [ ] [ ]( )
[ ] [ ]( ) [ ] [ ]( )
; ,
Pr Pr Pr Pr ,
C A С A
A C С A
F PN F PN F PT F PT
якщо F S F S F T F T
+ +
∉ ∧ ≠
(17)
[ ] [ ]( ) [ ] [ ]( )
[ ] [ ] [ ] [ ] [ ] [ ]( )
[ ] [ ]( ) [ ] [ ]( )
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]( )
[ ] [ ]( )
1
2
, Pr Pr Pr Pr ,
Pr ; Pr Pr ; ; ,
Pr Pr Pr Pr ,
Pr Pr ; Pr Pr ; ; ,
Pr Pr .
D A D A D
D D D A D A D
D A A D A D
D D A D A D A D A
A D
F якщо F S F S F T F T
F F S F T F T F PN F PN F PT
F F якщо F S F S F T F T
F F S F S F T F T F PN F PN F PT F PT
якщо F S F S
∈ ∧ ∈
= ∪ +
+ = ∈ ∧ ∉
= ∪ ∪ + +
∉
(18)
Залежності типів BF , CF , DF можна представити у вигляді суми ІПЗ типу AF , ви-
разивши їх параметри зворотними перетвореннями формул (15)–(18). Тому наводити фор-
мули обчислення сум B CF F+ , D DF F+ та ін. тут немає сенсу.
Використовуючи (15)–(18), можна елементарно довести, що операція об’єднання
залежностей має властивості комутативності та асоціативності на множині ІПЗ.
Використовуючи (3) та (15)–(18), визначимо операцію розщеплення ІПЗ як оберне-
ну до операції об’єднання:
1 2 3 3 2 1F F F F F F+ = ⇒ − = . (19)
Таким чином, операції розширення та звуження множин значень умови та результа-
ту продукційного правила ІПЗ дозволяють гнучко модифікувати ці залежності без потреби
проведення додаткових складних обчислень. Необхідно тільки провести попередній аналіз
простих залежностей виду (6) вищеописаним алгоритмом.
ISSN 1028-9763. Математичні машини і системи, 2012, № 1 95
Наведені операції та алгоритм дозволяють виявити область визначення ІПЗ та знай-
ти залежності за заданою імовірністю виконання. Недоліком залишається знаходження
залежностей тільки виду (12) (вони включають (6), (7) та (10)), тобто ІПЗ, що мають лише
один атрибут в умовній частині предиката та один – у результуючій. Тобто, неможливий
пошук залежностей
( )1 1 2 2 1 1 2 2 0l l k kP s S s S s S t T t T t T p∈ ∧ ∈ ∧ ∧ ∈ → ∈ ∧ ∈ ∧ ∧ ∈ ≥K K . (20)
Для забезпечення пошуку таких ІПЗ введемо дві нові операції: введення нового ат-
рибуту в умовну частину предиката залежності та введення нового атрибуту в результую-
чу частину предиката. Позначимо їх ⊗ та ⊕ відповідно.
Для залежностей (20) розширимо поняття операцій [ ]PrIF , [ ]SFI Pr . Вони поверта-
ють множину значень кортежу атрибутів умови та результуючої частини предиката відпо-
відно. Ця множина значень є декартовим добутком множин допустимих значень окремих
атрибутів кортежу:
[ ]
[ ]
1 2
1 2
Pr ,
Pr .
I l
I k
F S S S S
F T T T T
= × × ×
= × × ×
K
K
(21)
Операції з ІПЗ тепер визначимо як
( ) ( )( ) ( )( )'
[Pr ] [Pr ] [Pr ][Pr ]; [Pr ] ; ;
I I II I I I x X k F S k F S d F TF x X F F S F T X R Rσ σ σ∈ ∈ ∈ ∧ ∈⊕ ∈ = = × , (22)
( ) ( )( ) ( )( )( )'
[Pr ] [Pr ] [Pr ][Pr ] ; [Pr ]; ; .
I I II I I I x X k F S x X k F S d F TF x X F F S X F T R Rσ σ σ σ∈ ∈ ∈ ∈ ∧ ∈⊗ ∈ = = × (23)
Тут ( )Pr Rσ – операція селекції по предикату Pr над відношенням R.
Поки не вдалось розробити ефективний метод обчислення множин
( )( )[Pr ]Ix X k F S Rσ σ∈ ∈ та ( )( )[Pr ] [Pr ]I Ix X k F S d F T Rσ σ∈ ∈ ∧ ∈ по наявних ( )[Pr ]Ik F S Rσ ∈ та
( )[Pr ] [Pr ]I Ik F S d F T Rσ ∈ ∧ ∈ (їх можна зберігати для кожної аналізованої залежності в ході обчис-
лень для спрощення побудови мультиатрибутних залежностей). Єдиним виходом залиша-
ється пряме виконання вказаних операцій селекції.
Отже, алгоритм пошуку ІПЗ розширюється додатковим кроком – пошуком мульти-
атрибутних залежностей. Для цього залежності з кроку 1 алгоритму аналізуються на наяв-
ність кореляцій з іншими атрибутами відношення. Повний перебір можливих розширень
ІПЗ до мультиатрибутних буде мати складність ( )2O z m sz⋅ ⋅ , де z – кількість знайдених
ІПЗ, m – кількість атрибутів відношення, sz – середній розмір множини кортежів відно-
шення R, на яких визначена ІПЗ.
Для оптимізації цього процесу можна перебирати пари залежностей виду (6) –
( )1 2;A AF F , які мають значне перекриття множин значень результуючої частини предиката:
[ ] [ ]
[ ] [ ]
1 2
1 2
Pr Pr
Pr Pr
A A
A A
F T F T
c
F T F T
∩
≥
∪
. (24)
Значення c визначається експертним шляхом, залежно від структури даних та типів зале-
жностей, які слід шукати.
Пари залежностей, що задовольняють умову (24), комбінуються операціями
об’єднання (якщо умовні частини предиката мають однакові атрибути) чи додавання атри-
буту в умову предиката (якщо умовні частини предиката мають різні атрибути), а утворені
залежності додаються у множину ІПЗ для подальшого агрегування.
96 ISSN 1028-9763. Математичні машини і системи, 2012, № 1
Використання умови (24) дозволяє значно скоротити перебір можливих мультиат-
рибутних залежностей і забезпечити складність виконання другого кроку алгоритму
( )( )2 *logO z sz z sz⋅ + ⋅ , де ∗z – кількість пар ІПЗ, що задовольняють умову (24). Обчислен-
ня формули (24) може бути виконано з використанням структури даних binomial heap або
Fibonacci heap зі складністю ( )( )logO sz . Таким чином, якщо кількість початкових залеж-
ностей не надто велика (порядку декількох тисяч), досягається прийнятний час аналізу
мультиатрибутних залежностей на сучасних обчислювальних системах. Контролювати
кількість одноатрибутних залежностей можна вибором порогового значення імовірності
0p , а перебір мультиатрибутних залежностей – зміною константи c з умови (24).
Таким чином, описаний у даній статті алгоритм дозволяє проводити ефективний
аналіз однотипних даних на наявність мультиатрибутних ІПЗ та ЧФ, сумарна складність
якого ( )( )2 2 *logO m n z sz z sz⋅ + ⋅ + ⋅ . При розумному виборі значень 0p та c на сучасних
обчислювальних центрах він дає змогу аналізувати набори даних з тисячами атрибутів та
мільйонами кортежів відношення.
Розглянемо продовження прикладу 1 для демонстрації пошуку мультиатрибутних
залежностей. Виберемо значення 0,7c = . Розглянемо одноатрибутні ІЗ
{ }( )1 2,3 1P L T= → ∈ = та { }( ) 2
1,2,3 3
3
P i T∈ → = = ; за формулою (24) обчислюємо їх пе-
рекриття:
[ ] [ ]
[ ] [ ]
1 2
1 2
Pr Pr 3
Pr Pr 4
A A
A A
F T F T
c
F T F T
∩
= ≥
∪
.
Отже, обчислюємо мультиатрибутну залежність, утворену додаванням атрибуту i
на множині значень { }3,2,1 в залежність { }( )1 2,3 1P L T= → ∈ = :
{ } { }( ) { } ( )( )
{ } { } ( )( )
11,2,3
1,2,3 1 2,3
3
1 1,2,3 2,3 1
3
Li
i L T
R
P L i T
R
σ σ
σ σ
=∈
∈ = ∧ ∈
= ∧ ∈ → ∈ = = = .
Таким чином, утворилась нова мультиатрибутна ІПЗ.
3. Висновки
Описаний у даній статті алгоритм дозволяє проводити аналіз великих обсягів даних, які
можуть бути представлені у вигляді відношення (на сучасних обчислювальних центрах за
кілька годин можна провести аналіз відношення з тисячами атрибутів та мільйонами запи-
сів). Алгоритм достатньо легко можна модифікувати для паралельного виконання на декі-
лькох обчислювальних машинах, що при потребі дозволить зменшити час аналізу до хви-
лин.
Система аналізу даних, яка використовуватиме вищеописаний алгоритм, дозволить
значно розширити межі застосування методів аналізу даних у напрямку розміру аналізова-
них відношень, що, у свою чергу, дозволить застосовувати їх до предметних галузей, в
яких накопичуються надзвичайно великі архівні бази даних, та виявити нові важливі зале-
жності в цих галузях.
Основним недоліком розробленого алгоритму є те, що він не використовує вже ная-
вних знань про специфіку предметної галузі і дозволяє виявити далеко не всі типи можли-
вих залежностей (його завданням є пошук імовірнісних продукційних залежностей). Ще
одним недоліком є недостатня ефективність пошуку мультиатрибутних залежностей і для
ISSN 1028-9763. Математичні машини і системи, 2012, № 1 97
оптимізації цього процесу доводиться вводити додатковий коефіцієнт, на якому базується
евристичний алгоритм пошуку таких залежностей.
І все ж, не зважаючи на описані недоліки, алгоритм дозволяє виявляти дуже широ-
кий клас залежностей у даних і може бути застосований у найрізноманітніших галузях на-
уки і техніки.
СПИСОК ЛІТЕРАТУРИ
1. Головний сайт департаменту патології, UT Southwestern Medical Center [Електронний ресурс]. –
Режим доступу: http://pathcuric1.swmed.edu/pathdb/classifi.html.
2. Опис утиліти BiNGO, сайт університету Гент [Електронний ресурс]. – Режим доступу
http://www.psb.ugent.be/cbd/papers/BiNGO/Home.html.
3. Офіційний сайт National Institute of Allergy and Infectious Diseases (NIAID), NIH [Електронний
ресурс]. – Режим доступу http://david.abcc.ncifcrf.gov/content.jsp?file=/ease/ease1.htm&type=1.
4. Мейер Д. Теория реляционных баз данных / Мейер Д.; пер. с англ. – М.: Мир, 1987. – 610 с.
Стаття надійшла до редакції 14.07.2011
|