Н Б Шаховська - Аналіз задачі опрацювання відсутності та неповноти інформації у сховищі даних - страница 1

Страницы:
1  2 

УДК 004.652.4+004.827

Н.Б. Шаховська, Д.І. Угрин*

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

АНАЛІЗ ЗАДАЧІ ОПРАЦЮВАННЯ ВІДСУТНОСТІ ТА НЕПОВНОТИ ІНФОРМАЦІЇ У СХОВИЩІ ДАНИХ

© Шаховська Н.Б., Угрин Д.І., 2008

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

During realization of projects of construction of depositories given there is a row of general tasks which depend on the subject domain of information: planning of structure, actualization of aggregate values, dilution of hypercube, decline of quality of decisions. The ways of decision of these tasks and methods of realization of the simple and hierarchical measurings are possible in the articles considered.

Вступ

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

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

Практика розроблення і впровадження реляційних систем збирання даних показала, що через різні причини первинні дані збирають лише частково, а тому їх не завжди можна оптимально використовувати. Це приводить до необхідності застосування багатовимірних баз даних з част­ковою або слабкою заповненістю. При цьому створювані багатовимірні куби даних (гіперкуби -Data Hypercube) мають низьку щільність заповнення даними, а тому є розрідженими. Тому виникають такі проблеми:

• низька ефективність пошуку і витягання інформації з розрідженого гіперкуба даних;

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

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

1. Опис об'єкта дослідження

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

Враховуючи специфіку, до проектування сховищ даних зазвичай висуваються такі вимоги:

— повинні бути виділені статичні дані, що регулярно модифікуються;

— повинні бути спрощені вимоги до запитів з метою вилучення запитів, що могли б вимагати множинних запитів SQL у традиційних реляційних СУБД;

— повинна бути забезпечена підтримка складних запитів SQL, що вимагають послідовної обробки великої кількості записів.

Уведемо формальну модель сховища даних. Реляційною базою даних називають трійку

DB = (r, R, Z)

5

де r - множина відношень бази даних, R - множина їх схем, Z - множина обмежень цілісності. Тоді сховищем даних, побудованим на основі реляційної моделі, назвемо трійку

DW = { DB, rf, Rf, func)

5

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

rf - відношення, у якому зберігається агрегована інформація і за даними якого здійснюється прийняття рішень (відношення фактів).

Rf - схема відношення rf. func

J      - множина процедур прийняття рішень.

Тоді нові дані (або рішення) - це результат застосування функцій сховища даних над відношенням фактів:

Design = func(rf, user _ param)

де user_param - параметри користувача (або вимоги), які ставляться до рішення.

Оскільки відношення rf містить агреговану інформацію з відношень баз даних, то зв'язок між

ним і відношеннями баз даних DB приводить до утворення так званого гіперкуба даних (моделі багатовимірного подання даних) [3].

„ _ DB    V- : Universum(DB) тг

Виміром назвемо універсум відношень бази даних     1 -   1 v    lJ. Кожен вимір

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

(рівнів ієрархії).

Відношення між вимірами - деяке відношення, яке є зв' язком між вимірами.

V1,V2,...,Vn ->Rel.

Своєю чергою, Rel можуть бути параметрами для інших відношень між вимірами, і тим самим створювати ієрархію вимірів.

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

Формування відношення rf здійснюється на основі функції агрегування Agg [1]: rf : Agg (Re li,...,Re ln)

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

Розглянемо складові елементи гіперкуба.

Гіперкуб даних містить одне або більше вимірів і є впорядкованим набором комірок (рис. 1). Кожна комірка визначається одним і лише одним набором значень вимірів - атрибутів. Комірка може містити дані - виміру або бути порожньою.

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

Гіперкуб даних

Атрибути

-л21

^31

V3.

Т

^133

^233

^333

^123

^223

^323

null

Хізз\

^313

лмірки

Порожня комірка значення

Рис. 1. Гіперкуб даних

Отже, V - множина вимірів гіперкуба,  A\  = \Ali, A2,      Akt 1 i = 1

V

множина

атрибутів виміру   i, A = AVi U A2 U... U An - множина атрибутів гіперкуба, V' cz V - множина

фіксованих вимірів, A' cz A - множина фіксованих атрибутів.

Гіперкуб даних позначимо як множину комірок, що відповідає множинам V, A: rel(V,A).

Підмножина гіперкуба даних, що відповідає множині фіксованих значень, позначатимемо як rel f(VA).

Кожній комірці гіперкуба даних rel є ГЄІ відповідає єдино можлива множина атрибутів вимірів Arel cz A . Комірка може бути порожня (не містити даних) або містити значення показника.

Для отримання доступу до даних користувачу необхідно вказати множину необхідних вимірів V' cz V і значень атрибутів A ' cz A (фіксувати атрибути). Множина комірок, що відповідають відповідним атрибутам та вимірам, позначимо як relXVA') | rel cz ГЄІ.

Ключем виміру назвемо атрибут, який однозначно визначає кортеж (рядок) виміру гіперкуба.

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

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

Вижниця Хотин Путила турбаз

Рис. 2. Гіперкуб з трьома вимірами

Наявність добре розвиненої ієрархії агрегованих даних за рівнями агрегації є відмінною рисою сховища даних.

2. Постановка задачі

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

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

Зв'язок іж агрегованими та деталізованими даними подано на рис. 3.

Дуже часте використання

Рис. 3. Зв'язок між детальними та агрегованими даними у СД

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

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

• дослідження моделі даних і формалізація методів оцінки щільності гіперкуба даних;

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

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

• дослідження можливостей застосування різних методів візуалізації розріджених гіперкубів даних, зокрема з використанням ГІС-ТЕХНОЛОГІЇ, двовимірної і тривимірної машинної графіки [1,2].

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

-►

-►

розрідження гіперкуба даних

 

 

низька якість прийнятих рішень

 

 

неадекватність моделі даних

 

Рис. 4. Причини появи невизначеності у сховищі даних

Наповнення гіперкуба даними за недостатньої кількості початкових даних приводить до утворення порожніх комірок. Гіперкуби даних з великою кількістю порожніх комірок називають розрідженими [1,4].

Поняття агрегації в гіперкубі даних нерозривно пов'язане з поняттям ієрархічного виміру. Агрегація даних Ag - отримання значень, відповідних атрибутам деякого рівня ієрархічного виміру V на основі значень рівня 1-1. Отримується у результаті виконання операції згортки. Саме агрегація призводить до виникнення зв' язків між даними.

Розглянемо ієрархічні виміри Уз L рівнями (рис. 5). Первинні дані (факти) відповідають нижньому рівню ієрархії (l=0).

7=2

Ієрархія вимірів

1=1

1=0 К-сть агрегатів

N 0

N1

N2

Рис. 5. Агрегація гіперкуба даних. Одномірне представлення

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

формулою: Agj = 1 = Ag^ де - кількість фактів, що відповідають атрибутам, які є дочірніми

відносно атрибута j.

Узагальнюючи, одержимо формули обчислення агрегатів за методом підсумовування на решті рівнів ієрархії: Ag'j = 1= Ag'-1, l = 1,..., L; j = 1,..., N,

Вісь виміру У, що спочатку містить атрибути, відповідні нижньому рівню ієрархії (1=0), може бути доповнена атрибутами, відповідними рівням ієрархії, починаючи з l=1. Отже, відмінність між атрибутами, відповідними первинним даним і атрибутами, відповідними агрегатам, є умовною.

Операція згортки даних [9] у цьому випадку являє собою побудову зрізу гіперкуба даних, що

відповідає зміні мітки рівня агрегації l110 < 11 < L на рівень l2 |l1 < l2 < L . Операція деталізації відповідає зміні мітки рівня l111 < l1 < L на рівень l210 < l2 < l1.

L

Кількість агрегатів для одного виміру Ny = Ц Ni . Розглянемо випадок двох вимірів (рис. 6).

i=1

У2 t

Ag02

Ag      Область агрегації первинних даних виміру V2

Ag00

Область первинних даних

Ag12 Ag

Область агрегації агрегатів

Ag21

Ag10

Область агрегації первинних даних виміру V1

Ag20

Рис. 6. Агрегація гіперкуба даних. Двовимірне представлення

Кількість агрегатів, збережена в гіперкубі даних поряд з первинними даними, залежить від

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

У   випадку   двох   вимірів   кількість   агрегатів   становитиме   суму   значень областей:

Ag01, Ag02, Ag10, Agn, Ag12, Ag20, Ag21, Ag22. з іншого боку, кількість агрегатів можна обчислити як різницю кількості всіх значень гіперкуба і кількості значень, відповідних області первинних

00 . Кількість значень агрегата є добутком    0      0 .

даних

даних у двовимірному випадку становить:

NA =(n0 + N1 1    1 N1

Отже, кількість агрегатів гіперкуба

0 + N1 +... + Nl )x(n2 + N

L2

+ ... + .

L1 L2

IN1 х X N

n0 x n2

i=0

i=0

22

V

2

У Lj

На випадок довільної кількості вимірів V одержимо: NA = П\ Ц N-  П[ N0 , де V - к-ть

j=1 i=0

j=1

атрибутів i-го рівня ієрархії виміру, а Li - к-ть рівнів ієрархії виміру j [1-4, 6].

3. Основний матеріал

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

Ступінь агрегації куба обчислюється як:

a

а = a

де a - реальна кількість агрегованих значень показників, a* - максимально можлива кількість агрегатних значень вихідних даних куба [1].

На практиці, визначаючи, яку обрати з формул для a і a* спочатку розбирають прості випадки із двома-трьома вимірами, а потім, у разі великих неточностей, переходять до узагальненого варіанта. Те саме стосується й рівнів ієрархії у вимірах: спочатку розглядаються випадки простих вимірів (з одним рівнем), а потім на прикладі вимірів з декількома рівнями виводиться узагальнена формула. Такий підхід дає змогу легше зрозуміти процес одержання агрегованих значень показників. На рис. 7 представлений спрощений приклад виміру територіальних об'єктів, що має ієрархічну структуру. Спочатку база даних містить факти, що відповідають атрибутам нижнього рівня ієрархії (первинні дані). Суть процесу агрегації полягає в обчисленні значень, що відповідають атрибутам інших рівнів ієрархії на основі фактів нижнього рівня. Отримані в ході агрегації значення називаються агрегативами. Агрегативи використовуються при аналізі даних на різних рівнях деталізації й, як правило, обчислюються на етапі формування гіперкуба даних з метою скорочення часу відгуку на запит користувача [1,7].

Страницы:
1  2 


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

Н Б Шаховська - Аналіз задачі опрацювання відсутності та неповноти інформації у сховищі даних

Н Б Шаховська - Простори даних гносеологія концепції та тенденції розвитку

Н Б Шаховська - Методи усунення невизначеностей у базах знань побудованих на основі реляційного підходу

Н Б Шаховська - Технології інтеграції даних інформаційних систем національного університету львівська політехніка