Аналіз ефективності застосування частотного критерію в алгоритмі послідовного відсіювання неінформативних аргументів
В статті аналізуються властивості частотного критерію в задачі оцінювання рівня інформативності аргументів. На основі виконаних експериментів обґрунтовано доцільність та ефективність застосування цього критерію в алгоритмі послідовного відсіювання неінформативних аргументів. В статье анализируются с...
Збережено в:
| Опубліковано в: : | Індуктивне моделювання складних систем |
|---|---|
| Дата: | 2012 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2012
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/45972 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Аналіз ефективності застосування частотного критерію в алгоритмі послідовного відсіювання неінформативних аргументів / О.А. Самойленко, В.С. Степашко // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2012. — Вип. 4. — С. 198-205. — Бібліогр.: 7 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859612387982704640 |
|---|---|
| author | Самойленко, О.А. Степашко, В.С. |
| author_facet | Самойленко, О.А. Степашко, В.С. |
| citation_txt | Аналіз ефективності застосування частотного критерію в алгоритмі послідовного відсіювання неінформативних аргументів / О.А. Самойленко, В.С. Степашко // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2012. — Вип. 4. — С. 198-205. — Бібліогр.: 7 назв. — укр. |
| collection | DSpace DC |
| container_title | Індуктивне моделювання складних систем |
| description | В статті аналізуються властивості частотного критерію в задачі оцінювання рівня інформативності аргументів. На основі виконаних експериментів обґрунтовано доцільність та ефективність застосування цього критерію в алгоритмі послідовного відсіювання неінформативних аргументів.
В статье анализируются свойства частотного критерия в задаче оценивания уровня информативности аргументов. На основании выполненных экспериментов обоснована целесообразность и эффективность применения этого критерия в алгоритме последовательного отсеивания неинформативных аргументов.
Properties of a frequency criterion in the task of arguments informativity level estimation are analyzed in the article. Expediency and efficiency of this criterion use in the algorithm of successive sifting of uninformative arguments is justified based on the made experiments.
|
| first_indexed | 2025-11-28T15:00:51Z |
| format | Article |
| fulltext |
Аналіз ефективності застосування частотного критерію
Індуктивне моделювання складних систем, випуск 4, 2012 198
УДК 681.513
АНАЛІЗ ЕФЕКТИВНОСТІ ЗАСТОСУВАННЯ ЧАСТОТНОГО
КРИТЕРІЮ В АЛГОРИТМІ ПОСЛІДОВНОГО ВІДСІЮВАННЯ
НЕІНФОРМАТИВНИХ АРГУМЕНТІВ
О.А. Самойленко В.С. Степашко
Міжнародний науково-навчальний центр інформаційних технологій
та систем НАН України, Київ, пр-т Академіка Глушкова, 40
soa0pga@gmail.com
В статті аналізуються властивості частотного критерію в задачі оцінювання рівня
інформативності аргументів. На основі виконаних експериментів обґрунтовано
доцільність та ефективність застосування цього критерію в алгоритмі послідовного
відсіювання неінформативних аргументів.
Ключові слова: індуктивне моделювання, МГУА, критерій інформативності аргументів.
Properties of a frequency criterion in the task of arguments informativity level estimation are
analyzed in the article. Expediency and efficiency of this criterion use in the algorithm of
successive sifting of uninformative arguments is justified based on the made experiments.
Key words: inductive modeling, GMDH, criterion of arguments informativity.
В статье анализируются свойства частотного критерия в задаче оценивания уровня
информативности аргументов. На основании выполненных экспериментов обоснована
целесообразность и эффективность применения этого критерия в алгоритме
последовательного отсеивания неинформативных аргументов.
Ключевые слова: индуктивное моделирование, МГУА, критерий информативности
аргументов.
Вступ
Алгоритм повного перебору моделей COMBI [1, 2], розроблений в рамках
методології МГУА, ефективно розв’язує задачі моделювання за вибірками
даних з відносно невеликою кількістю аргументів – за наявності понад 30
аргументів повний перебір стає неможливим.
В [3-6] для вирішення цієї проблеми запропоновано використовувати різні
процедури послідовного відсіювання найменш інформативних аргументів,
причому рівень інформативності оцінюється за допомогою так званого
частотного критерію. Метою цієї роботи є обґрунтування доцільності та
ефективності використання цього критерію в задачах великої розмірності.
1. Постановка задачі
Будемо вважати, що задано вибірку даних ),( yXW = , mnX ×=dim , а
залежність вихідної змінної y від входів Х є лінійною:
θξξθ XyyXy
oo Δ
=+=+= , , (1)
Самойленко О.А., Степашко В.С.
Індуктивне моделювання складних систем, випуск 4, 2012 199
де θ – вектор, що складається з m невідомих істинних параметрів, з яких тільки
ms ≤0 ненульові, ξ – випадковий вектор шуму. Існує точна (істинна) модель
об’єкта виду 0θ
oo
Xy = , де 0sn
o
RX ×∈ , причому всі вектор-стовпці j
o
x , 0,...,1 sj = ,
містяться в матриці X, а 0θ – невідомий істинний вектор параметрів, який
складається тільки з тих компонент вектора θ , які не дорівнюють нулю і
визначають інформативні змінні (від яких залежить істинний вихід
o
y ). Набір з
s векторів XX s ∈ , що входять в певну модель, будемо називати структурою
цієї моделі, а кількість s цих векторів – складністю моделі. В такому випадку
задача структурної ідентифікації має полягати у визначенні найкращого
наближення до невідомих значень 00 ,θs при одночасному розділенні вхідних
змінних матриці X на інформативні та неінформативні.
Загалом задача ідентифікації полягає в формуванні за даними вибірки W
деякої множини ℑ моделей різної структури виду ),( ff Xfy θ
)
= та відшукання
оптимальної моделі за мінімумом заданого критерію )(⋅CR :
)),(,(minarg* f
f
XfyCRf θ
)
ℑ∈
= , (2)
де оцінки параметрів fθ
)
для кожної ℑ∈f , що вказують на набір ненульових
компонент (структуру), визначаються за умовою
),,,(minarg f
R
f XyQ
fs
f
θθ
θ ∈
=
)
(3)
де )()( ⋅≠⋅ CRQ – критерій якості розв’язку задачі параметричної ідентифікації
кожної часткової моделі, згенерованої в задачі структурної ідентифікації (2).
В задачах побудови моделей використовуються різні критерії рівня
інформативності аргументів для визначення тих векторів, що можуть входити
до структури істинної моделі. В алгоритмах послідовного відсіювання [4, 5, 6]
використовується частотний критерій, запропонований в [3]. Відповідно до
цього підходу поетапно серед певної кількості моделей, побудованих
алгоритмом МГУА, відбирається F найкращих моделей за заданим критерієм,
які складають множину Fℑ . Рівень інформативності кожного аргумента
визначається частотою його присутності в цих кращих моделях і визначається
за формулою:
F
q
FC j
j = (4)
Тут jq – кількість моделей з множини Fℑ , які містять j -й аргумент.
Розглянемо детальніше цей критерій у поєднанні з процедурами
послідовного відсіювання неінформативних аргументів та застосуємо чисельні
Аналіз ефективності застосування частотного критерію
Індуктивне моделювання складних систем, випуск 4, 2012 200
експерименти на тестових задачах для обґрунтування доцільності та
ефективності його застосування.
2. Дослідження ефективності частотного критерію
Для проведення чисельних експериментів і досліджень, пов’язаних з
частотним критерієм, розглянемо два штучно згенерованих тестових приклади
побудови оптимальних моделей.
Приклад 1. Нехай 20=m , 250=n , 100 =s . Сформуємо вибірку X ,
,20250dim ×=X що складається з векторів 20,...,1, =jx j . Кожному jx
відповідає певна функція )( kj tf (табл. 1). Вектори 5,...,1, =ktk генеруються за
допомогою генератора випадкових рівномірно розподілених чисел.
Таблиця 1
Залежність змінних x від kt
x: 1x 2x 3x 4x 5x 6x 7x 8x 9x 10x 11x 12x 13x 14x 15x 16x 17x 18x 19x 20x
:)(tf 1t 2t 3t 2
1t 21tt 31tt 41tt 2
2t 32tt 2
3t 4t 5t 51tt 42tt 52tt 43tt 53tt 2
4t 54tt 2
5t
Задамо вектор T]1;1;2;1;3;1;1;5;3;3[0 −−−−−=θ параметрів істинної
моделі, а її структурний вектор у вигляді такої послідовності нулів і одиниць:
[ ]00000000001111111111=d – тобто перші 10 аргументів є істинними,
від яких залежить вихідна змінна, а інші – надлишкові. Використовуючи
формулу (1) і шум ξ (рівень шуму в даному прикладі складає 2% від істинного
виходу
o
y ), обчислимо вихідну величину:
.23533 109876543210 ξξθ +++−++−−+−−=+= xxxxxxxxxxXy
o
(5)
Тут ,1dimdim ×== ny ξ ,dim 0snX ×=
ο
,1dim 00 ×= sθ 100 =s , а jx ,
0,...,1 sj = – вектор-стовпці матриці .
ο
X
Приклад 2. Виконаємо експерименти на вибірці, розглянутій у прикладі 1,
але для ускладнення задачі пошуку істинної моделі доповненій до 200
аргументів зайвими векторами, які не входять в істинну модель. Таким чином,
обидва масиви даних відповідно з 20 та 200 аргументами відповідають одній і
тій же істинній моделі.
Самойленко О.А., Степашко В.С.
Індуктивне моделювання складних систем, випуск 4, 2012 201
Тепер задача полягає у відновленні вектора 0θ за допомогою пошуку
оптимальної моделі 0θ
oo
Xy = на всій вибірці ),( yXW = за деяким критерієм
)(⋅CR , яким у нашому випадку буде критерій регулярності AR [2, 7].
Для знаходження кращих моделей в [5, 6] в поєднанні з частотним
критерієм застосовувались наступні два багатоетапні підходи: FSS (Forward
Successive Selection) і BSS (Backward Successive Selection).
Кожен етап методу FSS містить такі кроки:
Крок 1: На вибірці W з m аргументами будуються всі можливі моделі
складності від 1 до максимально прийнятного (за часовими затратами) maxs .
Кількість таких моделей дорівнює ∑=
=
max
max 1
s
j
j
ms CP . Максимальна складність
моделей maxs визначається нерівністю: maxmax
PPs ≤ , де maxP – максимальна
кількість моделей, які можна побудувати за прийнятний час. Для побудови цих
моделей може використовуватись комбінаторний алгоритм з обмеженням
складності COMBIS [1].
Крок 2: За значеннями критерію АR відбираються кращі моделі для
формування множини Fℑ .
Крок 3: Кожен аргумент множини Fℑ оцінюється за частотним критерієм
FC оцінки рівня інформативності.
Крок 4: Перед початком наступного етапу за допомогою відсіювання
найменш інформативних аргументів формується нова вибірка W зі зменшеною
кількістю аргументів.
Вказані дії виконуються доти, поки кількість аргументів m, що залишились
у вибірці W на певному етапі, не дозволить виконати повний перебір.
В цьому підході ми оцінюємо значущість аргументів на моделях малої
складності та на кожному етапі, зменшуючи кількість аргументів на вибірці W,
намагаємось, наскільки можливо, збільшити складність.
Метод BSS розглядає моделі не малої складності, як це було
запропоновано в FSS, а великої. На відміну від методу FSS, який будує моделі
на підматрицях dX , що складаються з векторів jx , max,...,1 sj = , метод BSS
розглядає моделі на підматрицях dX з векторами jx , msmj ,...,max−= , що
доповнюють підматриці dX до матриці X . Структурний вектор d є
інвертованим по відношенню до вектора d , тобто кожна одиниця в d
відповідає нулю в d і кожен нуль в d відповідає одиниці в d . До того ж
кількість моделей, що розглядаються на кожному етапі в FSS, дорівнює
кількості моделей з інвертованими структурними векторами, побудованими на
Аналіз ефективності застосування частотного критерію
Індуктивне моделювання складних систем, випуск 4, 2012 202
кожному етапі в BSS (
maxmax sms PP −= ). На відміну від FSS, в методі BSS прохід
по моделям виконується від моделей більшої складності до моделей з меншою
кількістю вхідних змінних x (складність змінюється від m до maxsm − ).
Результати застосування методів BSS i FSS з використанням частотного
критерію FC при розв’язанні раніше розглянутих задач наведені в табл. 2.
Метод FSS при розв’язанні задачі 1 з 20 аргументами знаходить ту ж
модель, що і метод повного перебору COMBI, тільки значно швидше. При
розв’язанні задачі з 200 аргументами на першому ж етапі втрачаються 5
істинних аргументів: 109754 ,,,, xxxxx , що мають мінімальне значення FC = 0.05
серед усіх змінних (Рис. 1).
Таблиця 2
Порівняння ефективності роботи методів FSS і BSS з COMBI при розв’язанні
задач з числом аргументів m=20 та m=200
Методи
Кількість
аргументів
у вибірці
(m)
Кількість
істинних
аргументів у
кращій моделі
Кількість
побудованих
моделей
Час
виконання, c. AR
Помилка
моделі на
контрольних
даних %
COMBI 20 10 1 048 575 21 2.36 2.8
FSS 20 10 125 994 1 2.36 2.8
BSS 20 10 125 994 3 2.36 2.8
FSS 200 5 508 664 4 439.2 44.8
BSS 200 10 10 427 22 1.89 1.4
Рис. 1. Значення FC для кожного
аргумента jx , визначене на моделях
складності 2,1=s при F = m = 200
Рис. 2. Значення FC для кожного
аргумента jx , визначене на моделях
складності 3,2,1=s , при F = m = 200
Самойленко О.А., Степашко В.С.
Індуктивне моделювання складних систем, випуск 4, 2012 203
Рис. 3. Значення FC для кожного
аргумента jx , визначене на моделях
складності 6,...,1=s , при F = m=20
Рис. 4. Значення FC для кожного
аргумента jx , визначене на моделях
складності mss ,...,0= , при F = m = 20
Аналізуючи результати, подані на рис. 1-4, можна припустити, що
значення критерію FC залежать від складності відповідних моделей. Крім
того, з рис. 4 бачимо, що при розгляді моделей складності 0ss > всі істинні
аргументи мають максимальне значення критерію FC . Це може означати, що
моделі, які містять всі істинні аргументи, є кращими за критерієм AR .
Для підтвердження цієї гіпотези розглянемо залежність значення критерію
AR від присутності всіх істинних аргументів в побудованій моделі.
Розіб'ємо всю множину ℑ на підмножини mss ,...,1, =ℑ , моделей
однакової складності s . Кожну множину sℑ розіб'ємо ще на підмножини s'ℑ і
~
sℑ , що складаються відповідно з моделей ssf '' ℑ∈ , які включають всі істинні
аргументи, та моделей ~~
ssf ℑ∈ , які не містять хоча б одного істинного
аргумента.
Використовуючи приклад 1, в якому перші 10 аргументів істинні та
20=m , побудуємо всі множини s'ℑ і ~
sℑ . На кожній множині s'ℑ знайдемо
мінімальне і максимальне значення критерію регулярності AR для моделей
ssf '' ℑ∈ , а на множині ~
sℑ – мінімальне значення критерію АR для моделей
~~
ssf ℑ∈ для кожного 1,...,0 −= mss (Рис. 5).
Аналіз ефективності застосування частотного критерію
Індуктивне моделювання складних систем, випуск 4, 2012 204
Рис. 5. Залежність критерію оцінки моделей від включення в модель всіх
істинних аргументів
Наведені на рис. 5 графіки показують, що максимальні значення критерію
АR для всіх моделей ssf '' ℑ∈ значно менші від мінімальних значень критерію
AR для всіх моделей ~~
ssf ℑ∈ . Це підтверджує висловлену вище гіпотезу про
найбільш часте включення істинних аргументів до кращих моделей і
обґрунтовує доцільність використання частотного критерію для оцінювання
ступеня інформативності аргументів.
Крім того, це дає підставу вважати, що при пошуку істинної моделі
необхідно враховувати не парну і не часткову кореляцію групи аргументів з
вихідною величиною (рис. 1-3), а множинну кореляцію всієї групи істинних
аргументів з вихідною змінною (рис. 4).
На відміну від FSS, в методі BSS частотний критерій визначається на
моделях, що містять усі істинні аргументи. Тим самим враховується кореляція
всієї групи істинних аргументів з вихідною величиною, що забезпечує високу
надійність визначення рівня інформативності аргументів.
Висновки
У процесі досліджень виконано низку експериментів, які показують
доцільність використання частотного критерію FC для оцінювання рівня
інформативності аргументів. Врахування множинної кореляції всієї групи
істинних аргументів з вихідною величною підвищує якість визначення
інформативності аргументів, що забезпечується застосуванням частотного
критерію FC в поєднанні з методом BSS.
Проведені експерименти підтвердили ефективність використання
частотного критерію в методах послідовного відсіювання аргументів. Метод
BSS із застосуванням частотного критерію дозволяє за допомогою неповного
Самойленко О.А., Степашко В.С.
Індуктивне моделювання складних систем, випуск 4, 2012 205
перебору знаходити на вибірках великої розмірності моделі, якість яких не
поступається якості моделей, знайдених за допомогою повного перебору. При
цьому процес знаходження оптимальних моделей радикально прискорюється.
Література
1. Степашко В.С. Комбинаторный алгоритм МГУА с оптимальной
схемой перебора моделей // Автоматика. – 1981. – №3. – С. 31 – 36.
2. Ивахненко А.Г., Степашко В.С. Помехоустойчивость моделирования. –
Киев: Наук. думка, 1985. – 216 с.
3. Степашко В.С., Коппа Ю.В. Опыт применения системы АСТРИД для
моделирования экономических процессов по статистическим данным //
Кибернетика и выч. техника, 1998. - Вып.117. – С. 24-31.
4. Samoilenko O.A., Stepashko V.S. Combinatorial GMDH algorithm with
successive selection of arguments. – Proceedings of the II International
Workshop on Inductive Modelling IWIM-2007, 19-23 September 2007,
Prague, Czech Republic. – Prague: Czech Technical University, 2007. – P.
139-143.
5. Самойленко О.А., Степашко В.С. Оптимізація структури моделей
методом послідовного відсіювання аргументів. – Матеріали
міжнародної конференції „Інтелектуальні системи прийняття рішень та
проблеми обчислювального інтелекту”, Євпаторія, 19-23 травня 2008
р.: – Херсон: Вид-во ХНТУ, 2008. – Том 3, Частина 2. – С. 83-86.
6. Samoilenko O., and Stepashko V. A method of Successive Elimination of
Spurious Arguments for Effective Solution of the Search-Based Modelling
Tasks. – Proceedings of the II International Conference on Inductive
Modelling ICIM-2008, 15-19 September 2008, Kyiv, Ukraine. – Kyiv:
IRTC ITS NANU, 2008. – P. 36-39.
7. Ivakhnenko A.G., Ivakhnenko G.A., Savchenko E.A., and Wunsch D.
Problems of Further Development of GMDH Algorithms: Part 2 // Pattern
Recognition and Image Analysis , Vol. 12, № 1, 2002, pp. 6-18.
|
| id | nasplib_isofts_kiev_ua-123456789-45972 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0044 |
| language | Ukrainian |
| last_indexed | 2025-11-28T15:00:51Z |
| publishDate | 2012 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| record_format | dspace |
| spelling | Самойленко, О.А. Степашко, В.С. 2013-06-21T09:20:43Z 2013-06-21T09:20:43Z 2012 Аналіз ефективності застосування частотного критерію в алгоритмі послідовного відсіювання неінформативних аргументів / О.А. Самойленко, В.С. Степашко // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2012. — Вип. 4. — С. 198-205. — Бібліогр.: 7 назв. — укр. XXXX-0044 https://nasplib.isofts.kiev.ua/handle/123456789/45972 681.513 В статті аналізуються властивості частотного критерію в задачі оцінювання рівня інформативності аргументів. На основі виконаних експериментів обґрунтовано доцільність та ефективність застосування цього критерію в алгоритмі послідовного відсіювання неінформативних аргументів. В статье анализируются свойства частотного критерия в задаче оценивания уровня информативности аргументов. На основании выполненных экспериментов обоснована целесообразность и эффективность применения этого критерия в алгоритме последовательного отсеивания неинформативных аргументов. Properties of a frequency criterion in the task of arguments informativity level estimation are analyzed in the article. Expediency and efficiency of this criterion use in the algorithm of successive sifting of uninformative arguments is justified based on the made experiments. uk Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Індуктивне моделювання складних систем Аналіз ефективності застосування частотного критерію в алгоритмі послідовного відсіювання неінформативних аргументів Article published earlier |
| spellingShingle | Аналіз ефективності застосування частотного критерію в алгоритмі послідовного відсіювання неінформативних аргументів Самойленко, О.А. Степашко, В.С. |
| title | Аналіз ефективності застосування частотного критерію в алгоритмі послідовного відсіювання неінформативних аргументів |
| title_full | Аналіз ефективності застосування частотного критерію в алгоритмі послідовного відсіювання неінформативних аргументів |
| title_fullStr | Аналіз ефективності застосування частотного критерію в алгоритмі послідовного відсіювання неінформативних аргументів |
| title_full_unstemmed | Аналіз ефективності застосування частотного критерію в алгоритмі послідовного відсіювання неінформативних аргументів |
| title_short | Аналіз ефективності застосування частотного критерію в алгоритмі послідовного відсіювання неінформативних аргументів |
| title_sort | аналіз ефективності застосування частотного критерію в алгоритмі послідовного відсіювання неінформативних аргументів |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45972 |
| work_keys_str_mv | AT samoilenkooa analízefektivnostízastosuvannâčastotnogokriteríûvalgoritmíposlídovnogovídsíûvannâneínformativnihargumentív AT stepaškovs analízefektivnostízastosuvannâčastotnogokriteríûvalgoritmíposlídovnogovídsíûvannâneínformativnihargumentív |