Алгоритм побудови зростаючих пірамідальних мереж у паралельному обчиcлювальному середовищі

Розглянуто моделі та методи логіко-лінгвістичного аналізу складних об’єктів, в яких розширяються можливості зростаючих пірамідальних мереж за рахунок використання паралельного алгоритму побудови мережі. Рассмотрены модели и методы логико-лингвистического анализа сложных объектов, в которых расширяют...

Повний опис

Збережено в:

Бібліографічні деталі
Опубліковано в: :	Комп’ютерні засоби, мережі та системи
Дата:	2011
Автор:	Величко, В.Ю.
Формат:	Стаття
Мова:	Українська
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2011
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/46452
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Алгоритм побудови зростаючих пірамідальних мереж у паралельному обчиcлювальному середовищі / В.Ю. Величко // Комп’ютерні засоби, мережі та системи. — 2011. — № 10. — С. 50-57. — Бібліогр.: 6 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859475543617961984
author	Величко, В.Ю.
author_facet	Величко, В.Ю.
citation_txt	Алгоритм побудови зростаючих пірамідальних мереж у паралельному обчиcлювальному середовищі / В.Ю. Величко // Комп’ютерні засоби, мережі та системи. — 2011. — № 10. — С. 50-57. — Бібліогр.: 6 назв. — укр.
collection	DSpace DC
container_title	Комп’ютерні засоби, мережі та системи
description	Розглянуто моделі та методи логіко-лінгвістичного аналізу складних об’єктів, в яких розширяються можливості зростаючих пірамідальних мереж за рахунок використання паралельного алгоритму побудови мережі. Рассмотрены модели и методы логико-лингвистического анализа сложных объектов, в которых расширяются возможности растущих пирамидальных сетей за счет использования параллельного алгоритма построения сети. Models and methods of the logical-linguistic analysis of complex objects are considered. Models are constructed on the basis of growing pyramidal networks (GPN) and expand opportunities of the latter due to improvement of GPN construction procedures.
first_indexed	2025-11-24T11:41:27Z
format	Article
fulltext	Комп’ютерні засоби, мережі та системи. 2011, № 10 50 V.Yu. Velychko AN ALGORITHM OF GROWING PYRAMIDAL NETWORKS BUILDING IN PARALLEL COMPUTING ENVIRONMENT Models and methods of the logical- linguistic analysis of complex ob- jects are considered. Models are constructed on the basis of growing pyramidal networks (GPN) and expand opportunities of the latter due to improvement of GPN con- struction procedures. Key words: growing pyramidal net- works, complex objects. Рассмотрены модели и методы логико-лингвистического анализа сложных объектов, в которых расширяются возможности рас- тущих пирамидальных сетей за счет использования параллельного алгоритма построения сети. Ключевые слова: растущие пи- рамидальные сети, сложные объекты. Розглянуто моделі та методи ло- гіко-лінгвістичного аналізу склад- них об’єктів, в яких розширяють- ся можливості зростаючих піра- мідальних мереж за рахунок вико- ристання паралельного алгоритму побудови мережі. Ключові слова: зростаючі пірамі- дальні мережі, складні об’єкти.  В.Ю. Величко, 2011 УДК 681.3 В.Ю. ВЕЛИЧКО АЛГОРИТМ ПОБУДОВИ ЗРОСТАЮЧИХ ПІРАМІДАЛЬНИХ МЕРЕЖ У ПАРАЛЕЛЬНОМУ ОБЧИCЛЮВАЛЬНОМУ СЕРЕДОВИЩІ Вступ. Найбільш прийнятним типом моде- лей, що використовуються в інформаційно- аналітичних системах для обробки складних структур різнотипних даних і знань є логіко- лінгвістичні моделі, тобто такі моделі, у яких основними елементами є не числа і обчислю- вальні операції, а імена та логічні зв’язки. Характерним прикладом логіко-лінгвистич- них моделей є поняття, які відображають закономірності, притаманні класам об’єктів. Під поняттям будемо розуміти узагальнений логіковий опис ознакової моделі класу об’єк- тів. Однією з добре апробованих можливих реалізацій логіко-лінгвістичних моделей є організація пам’яті інформаційно-аналітич- них систем у вигляді зростаючих пірамідаль- них мереж (ЗПМ) [1]. Відмінною рисою ЗПМ є структурування інформації одночасно з її введенням. Зміни у структурі пам’яті відбуваються при взаємодії збереженої інформації з новими даними. В результаті здійснення процесів структуру- вання інформації встановлюються асоціатив- ні зв’язки між об’єктами, які відображають- ся і закріплюються у структурних змінах пам’яті. На основі сформованої інформацій- ної моделі множини об’єктів здійснюються операції виділення понять, які надалі вико- ристовуються для вирішення задач класи- фікації, діагностики та прогнозування влас- тивостей нових об’єктів, шляхом порівняння їх ознакових описів з поняттями виділеними у мережі. При індуктивному формуванні деякого поняття на основі атрибутивних мо- АЛГОРИТМ ПОБУДОВИ ЗРОСТАЮЧИХ ПІРАМІДАЛЬНИХ МЕРЕЖ У ПАРАЛЕЛЬНОМУ… Комп’ютерні засоби, мережі та системи. 2011, № 10 51 делей метою аналізу є пошук сукупності кон’юнкцій значень атрибутів, що визначають всі об’єкти цього поняття та не визначають жодного об’єкта інших понять. Побудова зростаючих пірамідальних мереж. У роботі [2] наведено модифіковані правила побудови ЗПМ, використання яких дозволяє позбутись негативного впливу порядку перегляду об’єктів з вибірки для навчання на результат побудови мережі. При обробці великих обсягів вхідних даних актуальним є питання розробки алгоритму паралельної побудови ЗПМ. Розглянемо більш детально такий алгоритм. Наведемо визначення основних термінів [3], які будуть використовуватись в описі алгоритму. Пірамідальною мережею Q називається ациклічний орієнтований граф  ,Q U E (U – множина вершин, E – множина дуг), в якому відсутні вершини, які мають одну дугу, що заходить. Вершини, які не мають дуг, що заходять, називаються рецепторами, інші вершини – концепторами. Рецептори відповідають окремим значенням ознак з описів об'єктів. Концептори відповідають комбінаціям значень ознак, що ідентифікують об'єкт у цілому, або відповідним спільним частинам описів декількох об'єктів. Множина вершин пірамідальної мережі – це множина  Q QU R C , де QR – множина рецепторів пірамідальної мережі, QC – множина концепторів пірамідальної мережі. Підграф пірамідальної мережі, що включає вершину a та всі вершини, з яких існує шлях до a , називається пірамідою вершини a . Вершини, що входять до піраміди вершини a утворюють її субмножину. Множина вершин, до яких існують шляхи з вершини a , називається її супермножиною. Множину вершин з субмножини вершини a , що безпосередньо зв’язані дугами з вершиною a , будемо називати 0-субмножиною a та позначати aF . На початковій стадії у мережі існують лише рецептори з множини QR , кожен з яких відповідає значенню ознаки та концептори з множини AC , які відповідають відомим об’єктам. Останні складають множину  AС A  1 2, , , , , i na a a a . AС – деяка підмножина множини A відомих об’єктів. Для кожного з об’єктів ia відома відповідна множина рецепторів iaR . Побудова мережі починається з виконання правила А1 [2]. Правило А1. Для кожного нового об’єкта ia , який додається до мережі, та об’єкта , 1, 1 ja j i , який вже існує у мережі, визначається множина рецепторів  l j ik a ac R R R , яка відповідає деякому концептору l kc . Якщо концептор l kc , який відповідає перетину множин рецепторів об’єктів, існує у мережі, то він додається до 0-субмножини об’єкта ia . В іншому випадку в мережу вводиться новий концептор l kc , який з'єднується дугами, що виходять з В.Ю. ВЕЛИЧКО Комп’ютерні засоби, мережі та системи. 2011, № 10 52 вершин множини l kc R та дугами, що заходять до вершин ia та ja . Дуги від рецепторів з 0-субмножини нового концептора, які безпосередньо йшли до вершин ia та ja розриваються. Для кожного концептора l kc визначається його рівень l у мережі, який дорівнює кількості рецепторів з його 0-субмножини ( ) l kc l Card R . На рис. 1 показано застосування правила А1 при побудові ЗПМ. Початковий стан ЗПМ показано на рис. 1, а. Після додавання до мережі нового об’єкта ia в мережі з’явиться новий концептор з номером 11 (рис. 1, б). 1 2 3 4 1 3 4 8 9 10 5 6 7 а 1 2 3 4 8 9 10 5 6 7 11 б 1a 2a ia ja ja ia 2 8c 1a 2 8c 3 11c РИС. 1. Правило А1 побудови пірамідальної мережі На другому етапі структурування мережі виконується перевірка пірамід концепторів з множини \Q AC C на вкладеність за множиною рецепторів [4]. При обробці кожного концептора l kc починаючи з рівня  2 al R до рівня 2l його рецептори l kc R переводяться в стан збудження –  l kc R . Збудження розповсюджується по мережі та для кожного частково збудженого концептора  1 ,0     n m a Qc l n R m C , який має шляхи до збуджених рецепторів, підраховується ступінь збудження за формулою  n mc R . Концептори, які входять до супермножини концептора l kc не розглядаються. Якщо ступінь збудження частково збудженого концептора n mc дорівнює l, концептор l kc додається до 0-субмножини концептора n mc . На цьому етапі використання асоціативних властивостей ЗПМ дозволяє зменшити кількість операцій порівнянь концепторів. Представимо вищенаведений алгоритм у вигляді блок-схеми з урахуванням паралельного виконання процедур порівняння об’єктів у зростаючій піра- мідальній мережі (рис. 2). АЛГОРИТМ ПОБУДОВИ ЗРОСТАЮЧИХ ПІРАМІДАЛЬНИХ МЕРЕЖ У ПАРАЛЕЛЬНОМУ… Комп’ютерні засоби, мережі та системи. 2011, № 10 53 Паралельна побудова концепторів проміжних вузлів , 1, 1  ja j i Так  Ai C ?   j ia aR R ? 1 i i Ні Так Додати новий концептор до мережі Визначити кількість доступних паралельних обчислювальних вузлів Розподілити дані QR та AC рівномірно за усіма процесами 1i П ар ал ел ь н а п о б у д о в а к о н ц еп то р ів п р о м іж н и х в у зл ів П ар ал ел ь н а п о б у д о в а к о н ц еп то р ів п р о м іж н и х в у зл ів 2 al R 0k Так Підрахувати ступінь збудження концепторів  1 ,0     n m a Qc l n R m C Підпорядкувати концептор l kc концептору n mc 1 k k Кінець Всі концептори рівня l розглянуто? 1 l l 2l ? Вибрати концептор l kc Ні Ні Cтупінь збудження n mc l ? Всі концептори n mc розглянуто? Так Ні Ні Так Так Ні Початок Концептор l kc існує? Ні Синхронізація стану мережі з паралельними процесами Так РИС. 2. Блок-схема алгоритму побудови ЗПМ Оцінимо максимальну обчислювальну складність алгоритму побудови ЗПМ. Відповідно до правила А1 загальна кількість порівнянь об’єктів розраховується за формулою  1 1 2 A AO . При виконанні порівнянь до мережі може бути додано не більше 1O концепторів. Таке можливо, якщо   j ia a R R для , 1, 1  ja j i та множини рецепторів жодного з нових концепторів l kc не збігаються. Максимальна кількість операцій порівнянь на другому етапі В.Ю. ВЕЛИЧКО Комп’ютерні засоби, мережі та системи. 2011, № 10 54 структурування мережі розраховується за формулою  2 1 1 21 O O O . Загальна кількість операцій порівнянь у мережі дорівнює          1 2 1 2 1 2 1 2 1 2        A A A A A AO O O 2 3 4 4 8  A A A . Тобто обчислювальна складність алгоритму зростає пропорційно четвертого степеня загальної кількості об’єктів мережі. У реальних задачах обчислювальна складність буде меншою за рахунок використання асоціативних властивостей ЗПМ та меншої кількості концепторів, які будуються за правилом A1. Пірамідальні мережі зручні для виконання різних операцій асоціативного пошуку [5, 6]. Наприклад, можна вибрати всі об'єкти, що включають задане поєднання значень ознак, простежуючи шляхи, що виходять з вершини мережі, яка відповідає цьому поєднанню. Для вибірки всіх об'єктів, описи яких перетинаються з описом заданого об'єкта, досить прослідкувати шляхи, що виходять з вершин піраміди цього об’єкта. Алгоритм побудови мережі забезпечує автоматичне встановлення асоціативної близькості між об'єктами за спільними елементами їх описів. Перехід від конвергованих представлень об'єктів (концепторів) до розгорнених (наборів рецепторів) здійснюється шляхом перегляду пірамід у різних напрямках (зверху вниз і у зворотному напрямку). Важливою властивістю пірамідальних мереж є їх ієрархічність, що дозволяє природним чином відображати структуру складених об'єктів і зв'язки типів рід- вид та об’єкт-властивість. Концептори мережі відповідають поєднанням значень ознак, що визначають окремі об'єкти і кон'юнктивні класи об'єктів. При включенні збуджених вершин у піраміду об'єкта здійснюється прив'язка об'єкта до класів, визначення яких представлено цими вершинами. Таким чином, при побудові мережі формуються кон'юнктивні класи об'єктів, тобто здійснюється класифікація без вчителя. Навчання ЗПМ полягає у формуванні в них структур, що представляють поняття [5]. Після побудови пірамідальної мережі утворюється структура, яка є представленням описів об'єктів вибірки для навчання. Кожна вершина мережі визначає кон’юнктивний клас об'єктів. Таким чином, об'єкт належить до всіх класів об'єктів, які визначаються вершинами, що входять до його піраміди, і також кожний об'єкт, піраміда якого містить в собі деяку вершину, належить класу об'єктів, який вона представляє. На основі аналізу мережі можна представити поняття у формі логікового виразу з використанням логікових операцій диз’юнкції, кон’юнкції та заперечення [5]. Подання поняття у вигляді логікового виразу є наочним, добре інтерпретується й може бути використано фахівцем з метою більш глибокого розуміння закономірностей, які притаманні предметній області. АЛГОРИТМ ПОБУДОВИ ЗРОСТАЮЧИХ ПІРАМІДАЛЬНИХ МЕРЕЖ У ПАРАЛЕЛЬНОМУ… Комп’ютерні засоби, мережі та системи. 2011, № 10 55 Алгоритм побудови поняття у вигляді логікового виразу. Блок-схема алгоритму побудови логікових виразів показана на рис. 3. Формування логікових виразів виконується послідовно для кожного класу, об'єкти якого представлені в вибірці для навчання. Сформовані логікові вирази записуються в текстовий файл формату rtf. Після настроювання на черговий клас аналізуються всі контрольні вузли [1] даного класу. Контрольні вузли поточного класу будемо називати «позитивними» контрольними вузлами, всі контрольні вузли інших класів вважаються «негативними» щодо поточного класу. Побудова логікового виразу починається з упорядкування позитивних контрольних вузлів у порядку убування m – кількості об’єктів класу до пірамід яких входить контрольний вузол. Кожен «позитивний» контрольний вузол є основою для формування відповідного диз'юнктивного члена логікового виразу, що представляє поняття поточного класу. Формування кожного диз'юнктивного члена починається із нерозглянутого контрольного вузла з найбільшим m. Насамперед у текстовий файл записується число m, що відповідає числу об'єктів вибірки для навчання, які належать до поточного класу й містять у своєму описі рецептори з субмножини обраного контрольного вузла. Потім у текстовий файл виписуються рецептори з піраміди обраного вузла, для чого вона проглядається в напрямку «зверху вниз». У текстовому файлі рецептори зв'язуються знаком кон'юнкції (&). Таку кон'юнкцію будемо називати базовою. Далі здійснюється формування так званих кон'юнкцій-виключень, для чого в супермножині позитивного контрольного вузла здійснюється пошук най- ближчих негативних контрольних вузлів, тобто таких, на шляху до яких від позитивного контрольного вузла не зустрічаються інші контрольні вузли. Як негативні контрольні вузли розглядаються вузли, що належать будь-якому іншому класу, крім поточного. Якщо таких у мережі немає, у текстовий файл записується знак диз'юнкції (V) і починається формування чергового диз'юнктивного члена. Якщо в супермножині позитивного контрольного вузла є негативні контрольні вузли, триває формування кон'юнкції-виключення шляхом виписування рецепторів, що входять у піраміду негативного контрольного вузла, але без урахування рецепторів, які належать до субмножини позитивного контрольного вузла. Рецептори, які виписуються, поєднуються знаком кон'юнкції (&), беруться в дужки й приєднуються до раніше сформованої частини логікового виразу через знаки кон'юнкції (&) і заперечення (). Аналіз негативних контрольних вузлів і формування відповідних кон'юнкцій- виключень також здійснюється в порядку вбування m, яке характеризує клас, що відповідає негативному контрольному вузлу. Формування диз'юнктивного члена закінчується після аналізу всіх контрольних вузлів, які є негативними щодо даного позитивного контрольного вузла. Після того, як всі позитивні контрольні вузли поточного класу проаналізовано вищенаведеним чином, здійснюється перехід до формування логікового виразу для наступного класу. В.Ю. ВЕЛИЧКО Комп’ютерні засоби, мережі та системи. 2011, № 10 56 Ні Так Ні Так Так i: = 1 Вибір i-го класу, формування заголовку в текстовому файлі j:=1 Вибір j-го контрольного вузла i-го класу з max mi Запис в текстовий файл mi Запис в текстовий файл рецепторів контрольного вузла Пошук найближчих контрольних вузлів інших класів у супермножині j-го контрольного вузла Чи є контрольні вузли інших класів? k: = 1 Вибір k-го контрольного вузла з max ml (l  i) Запис до текстового файлу рецепторів k-го контрольного вузла, крім тих, котрі підпорядковані контрольному вузлу i-го класу Запис до текстового файлу знаків“&” k: = k + 1 Усі контрольні вузли i-го класу розглянуті ? Запис до текстового файлу знака “V” k: = k + 1 Усі класи розглянуті ? i: = i+1 Ні Ні Так Всі контрольні вузли інших класів розглянуті ? Початок Кінець РИС. 3. Блок-схема алгоритму побудови логікових виразів АЛГОРИТМ ПОБУДОВИ ЗРОСТАЮЧИХ ПІРАМІДАЛЬНИХ МЕРЕЖ У ПАРАЛЕЛЬНОМУ… Комп’ютерні засоби, мережі та системи. 2011, № 10 57 Базова кон'юнкція кожного диз'юнктивного члена відповідає сполученню значень ознак, характерних для об'єктів поточного класу, кон'юнкція- виключення відповідає сполученню значень ознак, яким об'єкти інших класів відрізняються від схожих на них об'єктів поточного класу. Важливою особливістю методу формування понять у пірамідальних мережах є можливість введення в поняття кон’юнкцій-виключень, які не належать об'єктам досліджуваного класу. В результаті сформовані поняття мають більш компактну логічну структуру, що в принципі дає можливість підвищувати точність прогнозування. Висновки. У роботі розглянуто методи підвищення ефективності логіко- лінгвістичного аналізу складних об’єктів, які розширюють діапазон застосування зростаючих пірамідальних мереж за рахунок використання паралельного алгоритму побудови ЗПМ. Подальші дослідження орієнтовані на проведення експериментів, вдосконалення паралельних алгоритмів та процедур побудови ЗПМ. 1. Гладун В.П. Планирование решений. – Киев: Наукова думка, 1987. – 168 с. 2. Величко В.Ю., Палагін О.В. Методи підвищення ефективності застосування зростаючих пірамідальних мереж // Комп'ютерні засоби, мережі та системи. – 2010. – № 9. – С. 106–114. 3. Victor Gladun, Vitaly Velichko, Yurii Ivaskiv. Selfstructurized Systems // International J. "Infor- mation Theories & Applications". FOI ITHEA, Sofia. – 2008. – 15. – N 1. – P. 5 – 13. 4. Москалькова Н.М. Методи правдоподібного виведення на основі представлення атрибутивних моделей знань в семантичних мережах // Автореф. дис. … канд. техн. наук. – К.: Інститут кібернетики імені В.М. Глушкова НАН України, 2000. – 19 с. 5. Гладун В.П. Процессы формирования новых знаний. – София: СД «Педагог 6», 1994. – 189 с. 6. Гладун В.П. Партнерство с компьютером. Человеко-машинные целеустремленные системы. – Киев: Port-Royal, 2000. – 118 с. Отримано 20.10.2011
id	nasplib_isofts_kiev_ua-123456789-46452
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	1817-9908
language	Ukrainian
last_indexed	2025-11-24T11:41:27Z
publishDate	2011
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
record_format	dspace
spelling	Величко, В.Ю. 2013-06-30T06:47:38Z 2013-06-30T06:47:38Z 2011 Алгоритм побудови зростаючих пірамідальних мереж у паралельному обчиcлювальному середовищі / В.Ю. Величко // Комп’ютерні засоби, мережі та системи. — 2011. — № 10. — С. 50-57. — Бібліогр.: 6 назв. — укр. 1817-9908 https://nasplib.isofts.kiev.ua/handle/123456789/46452 681.3 Розглянуто моделі та методи логіко-лінгвістичного аналізу складних об’єктів, в яких розширяються можливості зростаючих пірамідальних мереж за рахунок використання паралельного алгоритму побудови мережі. Рассмотрены модели и методы логико-лингвистического анализа сложных объектов, в которых расширяются возможности растущих пирамидальных сетей за счет использования параллельного алгоритма построения сети. Models and methods of the logical-linguistic analysis of complex objects are considered. Models are constructed on the basis of growing pyramidal networks (GPN) and expand opportunities of the latter due to improvement of GPN construction procedures. uk Інститут кібернетики ім. В.М. Глушкова НАН України Комп’ютерні засоби, мережі та системи Алгоритм побудови зростаючих пірамідальних мереж у паралельному обчиcлювальному середовищі An algorithm of growing pyramidal networks building in parallel computing environment Article published earlier
spellingShingle	Алгоритм побудови зростаючих пірамідальних мереж у паралельному обчиcлювальному середовищі Величко, В.Ю.
title	Алгоритм побудови зростаючих пірамідальних мереж у паралельному обчиcлювальному середовищі
title_alt	An algorithm of growing pyramidal networks building in parallel computing environment
title_full	Алгоритм побудови зростаючих пірамідальних мереж у паралельному обчиcлювальному середовищі
title_fullStr	Алгоритм побудови зростаючих пірамідальних мереж у паралельному обчиcлювальному середовищі
title_full_unstemmed	Алгоритм побудови зростаючих пірамідальних мереж у паралельному обчиcлювальному середовищі
title_short	Алгоритм побудови зростаючих пірамідальних мереж у паралельному обчиcлювальному середовищі
title_sort	алгоритм побудови зростаючих пірамідальних мереж у паралельному обчиcлювальному середовищі
url	https://nasplib.isofts.kiev.ua/handle/123456789/46452
work_keys_str_mv	AT veličkovû algoritmpobudovizrostaûčihpíramídalʹnihmerežuparalelʹnomuobčiclûvalʹnomuseredoviŝí AT veličkovû analgorithmofgrowingpyramidalnetworksbuildinginparallelcomputingenvironment

Алгоритм побудови зростаючих пірамідальних мереж у паралельному обчиcлювальному середовищі

Репозитарії

Схожі ресурси