Особливості інтелектуальних методів кластеризації у реляційних базах даних

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

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2010
1. Verfasser: Клічук, О.
Format: Artikel
Sprache:Ukrainian
Veröffentlicht: Інститут проблем штучного інтелекту МОН України та НАН України 2010
Schriftenreihe:Штучний інтелект
Schlagworte:
Online Zugang:http://dspace.nbuv.gov.ua/handle/123456789/56118
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Особливості інтелектуальних методів кластеризації у реляційних базах даних / О. Клічук // Штучний інтелект. — 2010. — № 1. — С. 25-31. — Бібліогр.: 5 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-56118
record_format dspace
spelling irk-123456789-561182014-02-12T03:10:21Z Особливості інтелектуальних методів кластеризації у реляційних базах даних Клічук, О. Системы и методы искусственного интеллекта У статті досліджується методика проведення кластерного аналізу у реляційних базах даних на основі функціонального програмування. Описано функції на основі рекурентних нейронних мереж та самоорганізованих карт Коханена для проведення кластерного аналізу. В статье исследована методика проведения кластерного анализа в реляционных базах данных с использованием функционального программирования. Описаны функции на основе реккурентных нейронных сетей и самоорганизующихся карт Коханена для проведения кластерного анализа. 2010 Article Особливості інтелектуальних методів кластеризації у реляційних базах даних / О. Клічук // Штучний інтелект. — 2010. — № 1. — С. 25-31. — Бібліогр.: 5 назв. — укр. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/56118 631.3.07 uk Штучний інтелект Інститут проблем штучного інтелекту МОН України та НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Ukrainian
topic Системы и методы искусственного интеллекта
Системы и методы искусственного интеллекта
spellingShingle Системы и методы искусственного интеллекта
Системы и методы искусственного интеллекта
Клічук, О.
Особливості інтелектуальних методів кластеризації у реляційних базах даних
Штучний інтелект
description У статті досліджується методика проведення кластерного аналізу у реляційних базах даних на основі функціонального програмування. Описано функції на основі рекурентних нейронних мереж та самоорганізованих карт Коханена для проведення кластерного аналізу.
format Article
author Клічук, О.
author_facet Клічук, О.
author_sort Клічук, О.
title Особливості інтелектуальних методів кластеризації у реляційних базах даних
title_short Особливості інтелектуальних методів кластеризації у реляційних базах даних
title_full Особливості інтелектуальних методів кластеризації у реляційних базах даних
title_fullStr Особливості інтелектуальних методів кластеризації у реляційних базах даних
title_full_unstemmed Особливості інтелектуальних методів кластеризації у реляційних базах даних
title_sort особливості інтелектуальних методів кластеризації у реляційних базах даних
publisher Інститут проблем штучного інтелекту МОН України та НАН України
publishDate 2010
topic_facet Системы и методы искусственного интеллекта
url http://dspace.nbuv.gov.ua/handle/123456789/56118
citation_txt Особливості інтелектуальних методів кластеризації у реляційних базах даних / О. Клічук // Штучний інтелект. — 2010. — № 1. — С. 25-31. — Бібліогр.: 5 назв. — укр.
series Штучний інтелект
work_keys_str_mv AT klíčuko osoblivostííntelektualʹnihmetodívklasterizacííurelâcíjnihbazahdanih
first_indexed 2025-07-05T07:22:00Z
last_indexed 2025-07-05T07:22:00Z
_version_ 1836790706621906944
fulltext «Штучний інтелект» 1’2010 25 1К УДК 631.3.07 Олег Клічук Чернівецький національний університет імені Юрія Федьковича, Україна Особливості інтелектуальних методів кластеризації у реляційних базах даних У статті досліджується методика проведення кластерного аналізу у реляційних базах даних на основі функціонального програмування. Описано функції на основі рекурентних нейронних мереж та самоорганізованих карт Коханена для проведення кластерного аналізу. Сучасні досягнення в інформаційних технологіях конкретизуються у практично- му їх втіленні, що підтверджує прикладне значення і застосування штучного інтелекту. Прогрес у технологічних засобах очевидний. Проте є ряд проблем, які потребують детальнішого аналізу та уточнення, що обумовлено їх практичним використанням. До сфери таких проблем можна віднести використання інтелектуальних методів клас- теризації даних у інформаційних системах. Проблеми кластерного аналізу розглянуто у Манделя [1], [2]. Ці дослідження переважно теоретичного характеру, а саме: містять прикладне значення кластеризації даних, основні алгоритми проведення кластеризації. Інтелектуальні методи обчислень набули розвитку в сучасній науковій думці, зок- рема у працях [3], [4]. Основою таких обчислень є нейронні мережі, генетичні алго- ритми та інші методи. Окремі дослідження у методах обробки реляційних баз даних є, але їх практич- не застосування не має системного характеру. У розвитку сучасних інформаційних систем спостерігається активний пошук нових методів обробки баз даних, тому що в основі кожної інформаційної системи присутня реляційна база даних. Класифікація об’єктів по осмислених групах – кластеризація – є важливою проце- дурою у сфері економічних, соціологічних, психологічних досліджень і фундаменталь- ним процесом наукової практики, тому що системи класифікацій містять поняття, необхідні для розробки теорій у науці. Отже, метою даного дослідження є пошук та аналіз методів обробки даних у реляційних базах даних. Це полегшить звичайним ко- ристувачам використання потужних інтелектуальних методів обробки даних. Кластерний аналіз – загальна назва множини обчислювальних процедур, які ви- користовуються при створенні класифікації. У результаті роботи з процедурами утво- рюються «кластери» або групи дуже подібних об’єктів. Більш точно, кластерний метод – багатомірна статистична процедура, яка виконує збір даних, які містять інформацію про вибірку об’єктів, а після – упорядковуює об’єкти у порівняно однорідні групи. Кількісна оцінка подібності побудована на понятті метрики. При цьому підході кожен об’єкт множини позначається точками координатного простору, при цьому по- мічені подібності і відмінності між точками знаходяться у відповідності з метрични- ми відстанями між ними. Розмірність простору визначається кількістю змінних, які використовуються для опису подій. Використовують такі стандартні властивості критеріїв, яким повинні відповідати міри подібності, щоб бути метрикою: – симетрія; Клічук Олег «Искусственный интеллект» 1’2010 26 1К – нерівність трикутника; – відмінність неоднакових об’єктів; – відсутність відмінностей ідентичних об’єктів. Найбільш широковживаними функціями відстаней між об’єктами є: – евклідова відстань: d2 ( Xi , Xj ) = [ ∑ = p k 1 ( xki – xkj )2 ]1/2; (1) – l1 – норма: d1 ( Xi , Xj ) = [ ∑ = p k 1 | xki – xkj | ]; (2) – супремум-норма: d∞ ( Xi , Xj ) = sup { | xki – xkj | }, k = 1, 2, 3, …p; (3) – lp – норма: dp ( Xi , Xj ) = [ ∑ = p k 1 | xki – xkj |p ]1/p; (4) – віддаль Махаланобіса: D2 ( Xi , Xj ) = ( Xi – Xj )T W -1 ( Xi – Xj ). (5) Проблема вимірювання близькості об’єктів постійно виникає при будь-яких тлу- маченнях кластерів та різних методах класифікації. Основними труднощами при цьому є неоднозначність вибору способу нормування і знаходження віддалі між об’єктами. Незважаючи на важливість евклідової та інших метрик, вони мають значні не- доліки, з яких найбільш суттєвий полягає у тому, що оцінка подібності дуже залежить від відмінностей у зсувах даних. Змінні, у яких наявні одночасно великі абсолютні зна- чення і стандартні відхилення, можуть подавити вплив змінних з меншими абсолютними значеннями та стандартними відхиленнями. Більш того, метричні відстані змінюються під дією перетворення шкали вимірювання змінних, при яких не зберігається ранжуван- ня за евклідовою віддаллю. Вибір змінних у кластерному аналізі є одним з найбільш важливих кроків у про- цесі дослідження, але і одним з найменш розроблених. Основна проблема полягає у тому, щоб знайти ту сукупність змінних, яка оптимальним чином відображає понят- тя подібності та описує об’єкти. В ідеалі змінні повинні вибиратися у відповідності з чітко сформульованою теорією, яка лежить в основі класифікації. В інформаційних сис- темах такими змінними є властивості об’єктів. Вони можуть мати як кількісне, так і якісне значення. Тому при проведенні обчислень виникає необхідність перетворення якісних даних у числові. Також у більшості видів аналізу дані, звичайно, підлягають нормуванню певним способом. У тому випадку якщо дані виміряні у різних масштабах, нормування, зви- чайно, проводиться таким чином, щоб середнє арифметичне дорівнювало нулю, а дис- персія – одиниці. Нормування являє собою перехід до певного однозначного опису для всіх ознак, до введення нової умовної одиниці вимірювання, яка допускає формальне співстав- лення об’єктів. Такі процедури у реляційних базах даних можна проводити за допомо- гою підсумкових операцій, декартового добутку та обчислень на основі функціональ- ного програмування. Найбільш поширеним способом нормування властивостей є: – обчислення підсумковою функцією середнього арифметичного xr ; – обчислення підсумковою функцією середньоквадратичного відхилення �; Особливості інтелектуальних методів кластеризації у реляційних базах даних «Штучний інтелект» 1’2010 27 1К – обчислення підсумковою функцією максимального значення xmax; – обчислення підсумковою функцією мінімального значення xmin; – проведення операції декартового множення з відношеннями даних, максимально- го, мінімального, середнього арифметичного значення і середньоквадратичного від- хилення; – знаходження нормованого значення за допомогою функції нормування: x’ =(x– xr ) / � / (xmax – xmin ) Такий підхід забезпечує просту та зручну організацію додаткових засобів оброб- ки інформації у готових базах даних. Незважаючи на відсутність чіткого означення, кластери володіють деякими влас- тивостями, найважливішими з яких є густина, дисперсія, розміри, форма і відокрем- леність. Основні кластерні методи можна поділити на такі групи: – ієрархічні агломеративні методи; – ієрархічні дивизімні методи; – ітеративні методи групування; – методи пошуку модальних значень густини; – факторні методи; – методи згущень; – методи, які використовують теорію графів. Ці групи методів відповідають різним підходам до створення кластерів, і вико- ристання різних методів до одних і тих же даних може привести до суттєво відмін- них результатів. У конкретних галузях науки найчастіше застосовують характерні групи методов кластеризації. Так, ієрархічні агломеративні методи частіше за все викорис- товуються у біології, тоді як факторні аналітичні методи з великим успіхом викорис- товуються у психології. При виборі методу кластеризації необхідно враховувати від- повідність цього методу до очікуваного характеру класифікації, використаних ознак і міри подібності. Найбільш відомими групами кластерних методів, які використовую- ться у соціальних науках, є ієрархічні агломеративні, ієрархічні дивизімні і факторні. Основними причинами розробки та використання спеціальних методів статистич- ного аналізу багатомірних даних є необхідність розуміння закономірностей функціо- нування недостатньо вивчених складних соціально-економічних процесів і явищ, а також використаннях цих методів як інструменту управління, який призначений для аналізу багатомірних реальних, швидкозмінних ситуацій. Основою сучасних інформа- ційних систем управління є реляційні бази даних. При обробці реляційних баз даних необхідно враховувати методику зберігання та доступу до інформації у них. Вона полягає у відокремленості записів у відношенні і проведенні обчислень поступово за кожним записом. Такі обмеження вимагають про- ведення пошуку специфічних методів обробки. Тобто з одного боку – простий метод доступу до даних у відношеннях, з іншого – обмеженість у використанні даних з різ- них записів відношення. Перераховані вище методи кластеризації вимагають одночас- ного порівняння кількох об’єктів. У звязку з відсутністю залежностей між записами реляційних баз даних та об- меженістю операцій реляційної алгебри сукупний аналіз інформації повинен бути за- безпечений функцією проведення кластеризації. Одним із перспективних методів є використання функціонального програмуван- ня. Суть його полягає у проведенні обчислень на основі тільки функцій [5]. У даному випадку аргументами функції є значення полів. Клічук Олег «Искусственный интеллект» 1’2010 28 1К Найпростішими функціями пошуку кластера можуть бути функції, які містять дані про центр розміщення кластера та його форму. Послідовний підхід у побудові ал- горитму кластеризації полягає в явному формулюванні певного цільового функціо- нала якості з наступною його мінімізацією. Найпростішим функціоналом якості є су- марна віддаль по всіх зразках до кожного об’єкта до центра найближчого від нього кластера у вибраній метриці. Цей функціонал можна визначити для умови, коли число кластерів відомо наперед. Змінними пошуку є координати центрів кластерів. Мінімі- зація функціонала якості повинна проводитися за всіма можливими перестановками об’єктів по кластерах. Це і визначає фундаментальну складність задачі кластеризації. Більш потужні функції кластеризації можна побудувати на основі нейронних ме- реж. Для розв’язування будь-якої задачі з використанням штучних нейронних мереж необхідно спочатку зпроектувати структуру мережі, адекватну поставленій задачі. Це передбачає вибір кількості шарів мережі і нейронів у кожному шарі, а також визна- чення необхідних зв’язків між шарами. Підбір кількості нейронів у вхідному шарі обумовлений розмірністю вхідного век- тора, у даному випадку – кількістю полів відношення. Подібна ситуація із вихідним шаром: у випадку з кластеризацією це, як правило, одне значення. Складним питан- ням залишається підбір кількості прихованих шарів і кількості нейронів у кожному з них. Теоретичний розв’язок цієї задачі у сенсі умови достатності був запропонований математиками, які вивчають апроксимацію функцій декількох змінних. У досліджуваному напрямку варто звернути увагу на окрему групу нейронних мереж зі зворотнім зв’язком між різними шарами нейронів. Це – так звані рекурентні мережі. Їх загальна ознака полягає у передачі сигналів із вихідного, або схованого, ша- ру у вхідний шар. Основна особливість, яка виділяє ці мережі серед інших нейронних мереж, – динамічна залежність на кожному етапі функціонування. Зміна стану одного нейрона відображається на всій мережі внаслідок зворотнього зв’язку типу «один до багатьох». У мережі виникає певний перехідний процес, який завершується формуванням стійко- го стану, який відрізняється у загальному випадку від попереднього. Ці стани можна позначати кластерами, які відповідають таким множинам об’єктів. Якщо функцію активації нейрона позначити f(u), де u – це зважена сума його збу- дження, то стан нейрона можна визначити вихідним сигналом yi = f(ui) = f ( ∑ = N j 1 wij xj ). Беручи до уваги те, що при зворотньому зв’язку типу «один до багатьох» роль збуджених імпульсів для нейрона відіграють вихідні сигнали інших нейронів, зміну його стану можна описати системою диференціальних нелінійних рівнянь: buuwdu iij N ijj ij i i f dt −−= ∑ ≠= )( ,1 τ (6) для i = 1, 2, …, N, де bi є пороговим значенням, заданим зовнішнім джерелом. Коефі- цієнт τ i – числова константа, яка описує динамічний стан. Стан нейрона розраховує- ться розв’язком такого рівняння, як yi = f(u). При певному рівні збудження нейронів, який описується значеннями їх вихідних сигналів yi, з рекурентною мережею можна співставити енергетичну функцію Ляпунова: E = 1 , 1 10 1 1 ( ) . 2 iN N ij ii j i i i i j i i j i ii x y y f y dy yw bR − ≠ = = − + +∑∑ ∑ ∑∫ (7) Особливості інтелектуальних методів кластеризації у реляційних базах даних «Штучний інтелект» 1’2010 29 1К Вона пов’язана з кожним збудженим станом мережі і має тенденцію зменшува- тися з часом. Зміна стану кожного нейрона ініціюється зміною енергетичного стану всієї мережі у напрямі мінімуму її енергії, аж до його досягнення. Звичайно, існує ба- гато локальних мінімумів, кожен з яких являє собою один зі станів системи, який ви- значається структурою мережі. У просторі станів локальні енергетичні мінімуми енергії подані точками стабільності, які називаються атракторами через тяжіння до них най- ближчого оточення. Однією з найбільш досліджених рекурентних мереж є мережа Хопфілда. Узагаль- нена структура цієї мережі являє собою систему з безпосереднім зворотнім зв’язком виходу з входом. Характерною особливістю такої системи є те, що вихідні сигнали нейронів є одночасно вхідними сигналами мережі. У класичній системі Хопфілда від- сутні зв’язки нейрона з власним виходом, це полегшує процес її налаштування. Процес навчання мережі формує зони притягання (кластери) точок рівноваги. Най- частіше нейрони мережі Хопфілда мають функцію активації типу signum зі значення- ми ±1. Це означає, що вихідний сигнал і-го нейрона визначається функцією yi = sgn(∑ = N j 0 wijxj + bi), (8) де N – кількість нейронів; wij – матриця синоптичних зв’язків, bi – коефіцієнти векто- ра зсуву. Механізм модифікації синаптичних зв’язків запропонований математичною мо- деллю Хебба. Для опису правила Хебба у математичних термінах розглянемо синап- тичний зв’язок нейрона k з передсинаптичним та післясинаптичним сигналами xj та yk. Зміну величини синаптичного зв’язку у момент часу n можна записати у вигляді: ∆wkj(n) = F(yk(n), xj(n)), (9) де F( ) – певна функція, яка залежить від передсинаптичних та післясинаптичних сиг- налів. Ця формула може бути записана у наступній формі: ∆wkj(n) = η yk(n) xj(n), (10) де η – додатня константа, яка визначає швидкість навчання. Для навчання без учителя можна використати правило конкурентного навчан- ня. Наприклад, можна використати нейронну мережу, яка складається з двох шарів – вхідного та вихідного. Вхідний шар отримує доступні дані. Вихідний складається з нейронів, які конкурують між собою за право відклику на ознаки, які містяться у вхід- них даних. У найпростішому випадку нейронна мережа працює за принципом «пере- можець отримує все». При такій стратегії нейрон з найбільшим сумарним вхідним сигналом «перемагає» у змаганні і переходить в активний стан, при цьому всі інші ней- рони відключаються. Для проведення кластеризації можна використовувати функції, які побудовані на основі алгоритмів самоорганізованого навчання. Метою цих алгоритмів є виявлен- ня у множині вхідних даних суттєвих ознак об’єктів. Для цього алгоритм реалізує правила локальної природи, що дозволяє проводити навчання обчислення відображе- ного вхідного сигналу на вихідний з потрібними властивостями. Під терміном «локаль- ний» розуміють заміну синаптичних ваг тільки безпосередніми сусідами цього нейрона. Моделі мереж, які навчаються на основі принципів самоорганізації, відображають властивості нейробіологічних структур. Архітектура самоорганізованих систем може Клічук Олег «Искусственный интеллект» 1’2010 30 1К приймати багато різних форм. Процес навчання полягає у періодичній зміні синаптич- них ваг всіх зв’язків у системі у відповідь на подачу вхідних зразків у відповідності з призначеними правилами для отримання відповідної конфігурації системи. Алгоритм, відповідальний за формування самоорганізуючих карт, починається з ініціалізації синаптичних ваг мережі. Звичайно це відбувається із призначенням си- наптичним вагам малих значень, які сформовані генератором випадкових чисел. При такому формуванні карта ознак початково не має якого-небудь порядку ознак. Після ко- ректної ініціалізації мережі для формування карти самоорганізації запускаються три наступні основні процеси: – конкуренція (competition) – для кожногo вхідногo зразка нейрони мережі обчис- люють відносні значення дискримінантної функції, ця функція є основою конкурен- ції серед нейронів; – кооперація (cooperation) – нейрон, який переміг, визначає простір положення топо- логічного околу нейронів, який забезпечує базис для кооперації між цими нейронами; – синаптична адаптація (synaptic adaptation) – цей механізм дозволяє збудженим ней- ронам збільшувати власні значення дискримінантних функцій по відношенню до вхід- них образів за допомогою відповідних коpектувань синаптичних ваг, зміна проводиться таким чином, щоб відклик нейрона-переможця на наступні аналогічніні приклади по- силювався. Математична модель процесу конкуренції наступна. Нехай m – розмірність вхідного простору, а вхідний вектор вибирається з цього вхідного простору випадко- во і позначається як: X = [ x1, x2,…,xm ]T. Вектор синаптичних ваг кожногo з нейронів мережі має таку саму розмірність, що і вхідний простір. Позначимо синаптичну вагу нейрона j: W = [ wj1, wj2,…,wjm ]T, j = 1, 2, …, l, де l – загальна кількість нейронів мережі. Для того щоб підібрати найкращий вектор Wj, який відповідає вхідному вектору Х, необхідно порівняти скалярні добутки Wj T × X для j = 1,2,...,l і вибрати найбільше значення. Таким чином, вибравши нейрон з найбіль- шим скалярним добутком, ми в результаті визначаємо місцезнаходження, яке повинне стати центром топологічного околу збужденогo нейрона. Для проведення операції кооперації необхідно визначити окіл збудженого нейро- на. Типовим прикладом обчислення цієї відстані є функція Гаусса: hj,i(x) = exp(– d2 j,i / (2σ2)), (11) де dj,i – латеральна віддаль (lateral distance) між нейроном-переможцем (і) та вторин- но збужденим нейроном (j); σ – параметр, який визначає рівень, до якого нейрони з топологічного околу нейрона-переможця приймають участь у процесі навчання. Для тогo щоб мережа могла caмоорганізовуватися, вектор синаптичних ваг нейро- на повинен змінюватися у відповідності до вхідного вектора. Основна проблема по- лягає у тому, як зміна повинна проходити. Враховуючи правило Хебба про те, що синаптична вага повинна підсилюватися при одночасному виникненні предсинаптич- ної і постсинаптичної активності та складової забування (forgetting term), зміна синап- тичних ваг має вигляд: ∆wj(n) = η(n) hj,i(x)(n) (x – wj(n)), (12) Особливості інтелектуальних методів кластеризації у реляційних базах даних «Штучний інтелект» 1’2010 31 1К де η – параметр швидкості навчання (1earning-rate parameter) алгoритму. Цей вираз викристовується для всіх нейронів решітки, які лежать у топологичному околі ней- рона-переможця. Він має ефект переміщення вектора синаптичних ваг нейрона-пере- можця у бік вхідного вектора. Висновки У роботі досліджено методику кластеризації реляційних баз даних на основі функ- ціонального програмування. У ролі засобів функціонального програмування запропоновано функції на основі рекурентних нейронних мереж та самоорганізаційних карт Коханена. Література 1. Мандель И.Д. Кластерный анализ / Мандель И.Д. – М. : Финансы и статистика, 1988. – 176 с. 2. Дюран Б. Кластерный анализ / Б. Дюран, П. Оделл ; [пер. с англ. Е.З. Демиденко ; под ред. А.Я. Бояр- ского]. – М. : Статистика, 1977. – 128 с. 3. Осовский С. Нейронные сети для обработки информации / С. Осовский ; [пер. с польского И.Д. Ру- динского]. – М. : Финансы и статистика, 2002. – 344 с. 4. Бэстенс Д.-Э. Нейронные сети и финансовые рынки: принятие решений в торговых операциях / Бэс- тенс Д.-Э., ван ден Берг В.-М., Вуд Д. – М. : ТВП, 1997. – 236 с. 5. Клічук О. Обробка реляційних баз даних засобами функціонального програмування / О. Клічук // Искусственный интеллект. – 2009. – № 2. – С. 57-63. Олег Кличук Особенности интеллектуальных методов кластеризации в релятивных базах данных В статье исследована методика проведения кластерного анализа в реляционных базах данных с использованием функционального программирования. Описаны функции на основе реккурентных нейронных сетей и самоорганизующихся карт Коханена для проведения кластерного анализа. Стаття надійшла до редакції 19.01.2010.