Класифікація функціональних даних за допомогою сплайнів з вільними вузлами

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2014
Автор:	Коршунова, І.А.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2014
Назва видання:	Системні дослідження та інформаційні технології
Теми:	Нові методи в системному аналізі, інформатиці та теорії прийняття рішень
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/85504
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Класифікація функціональних даних за допомогою сплайнів з вільними вузлами / І.А. Коршунова // Системні дослідження та інформаційні технології. — 2014. — № 2. — С. 115-124. — Бібліогр.: 11 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-85504
record_format	dspace
spelling	irk-123456789-855042015-08-07T03:02:15Z Класифікація функціональних даних за допомогою сплайнів з вільними вузлами Коршунова, І.А. Нові методи в системному аналізі, інформатиці та теорії прийняття рішень У багатьох прикладних задачах дані, що були отримані на основі вимірювань певного процесу, концептуально можна розглядати як функції неперервного аргументу. Аналіз таких даних, що прийнято називати «функціональними», значно ускладнюється порівняно з аналізом багатовимірних даних. Функціональні дані за допомогою відображення у вектори вільних вузлів апроксимуючих сплайнів практично без втрати інформації можна звести до вигляду, зручного для традиційних статистичних алгоритмів. Знаходження вільних вузлів сплайна є складною задачею оптимізації, для вирішення якої в цій роботі представлено новий евристичний метод. Не менш важливим етапом є вибір кількості параметрів апроксимаційної моделі, для чого було розроблено підхід на основі багатокритеріальної оптимізації за часом обчислення вузлів та точності апроксимації. Застосування сплайнів для класифікації функціональних даних було продемонстровано на задачі діагностики артриту за формою кісток. Во многих прикладных задачах, которые были получены на основе измерений определенного процесса концептуально можно рассматривать как функции непрерывного аргумента. Анализ таких данных, которые принято называть «функциональными», значительно усложняется по сравнению с анализом обычных многомерных данных. Функциональные данные при помощи отображения в векторы свободных узлов аппроксимирующих сплайнов практически без потери информации можно привести к виду, удобного для традиционных статистических алгоритмов. Нахождение свободных узлов является сложной задачей оптимизации, для решения которой в данной работе представлен новый эвристический метод. Не менее важным этапом есть выбор количества параметров аппроксимационной модели, для чего был разработан подход на основе многокритериальной оптимизации по времени вычисления узлов и точности аппроксимации. Применение сплайнов для классификации функциональных данных было продемонстрировано на задаче диагностики артрита по форме костей. Data, obtained through measurements of some process, in many problems, can be treated as functions of a continuous argument. An analysis of such "functional" data is much more complicated than multivariate data analysis. Functional data can be reflected into an appropriate form for traditional statistical algorithms with the help of free -knot splines, which causes almost no loss of information. Finding the free knots of spline is a complex optimization problem, so this paper presents a new heuristic method in order to solve it. An equally important step is to select the parameters of the approximation model. To deal with it, we developed a new approach, which is based on multi-objective optimization of computation time and the accuracy of approximation. The use of splines for classification of functional data was demonstrated on the problem of diagnosis of arthritis based on the bone shapes. 2014 Article Класифікація функціональних даних за допомогою сплайнів з вільними вузлами / І.А. Коршунова // Системні дослідження та інформаційні технології. — 2014. — № 2. — С. 115-124. — Бібліогр.: 11 назв. — укр. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/85504 519.21 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	2014
topic_facet	Нові методи в системному аналізі, інформатиці та теорії прийняття рішень
url	http://dspace.nbuv.gov.ua/handle/123456789/85504
citation_txt	Класифікація функціональних даних за допомогою сплайнів з вільними вузлами / І.А. Коршунова // Системні дослідження та інформаційні технології. — 2014. — № 2. — С. 115-124. — Бібліогр.: 11 назв. — укр.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT koršunovaía klasifíkacíâfunkcíonalʹnihdanihzadopomogoûsplajnívzvílʹnimivuzlami
first_indexed	2025-07-06T12:46:50Z
last_indexed	2025-07-06T12:46:50Z
_version_	1836901739932942336
fulltext	 І.А. Коршунова, 2014 Системні дослідження та інформаційні технології, 2014, № 2 115 УДК 519.21 КЛАСИФІКАЦІЯ ФУНКЦІОНАЛЬНИХ ДАНИХ ЗА ДОПОМОГОЮ СПЛАЙНІВ З ВІЛЬНИМИ ВУЗЛАМИ І.А. КОРШУНОВА У багатьох прикладних задачах дані, що були отримані на основі вимірювань певного процесу, концептуально можна розглядати як функції неперервного аргументу. Аналіз таких даних, що прийнято називати «функціональними», значно ускладнюється порівняно з аналізом багатовимірних даних. Функціо- нальні дані за допомогою відображення у вектори вільних вузлів апроксимую- чих сплайнів практично без втрати інформації можна звести до вигляду, зруч- ного для традиційних статистичних алгоритмів. Знаходження вільних вузлів сплайна є складною задачею оптимізації, для вирішення якої в цій роботі представлено новий евристичний метод. Не менш важливим етапом є вибір кі- лькості параметрів апроксимаційної моделі, для чого було розроблено підхід на основі багатокритеріальної оптимізації за часом обчислення вузлів та точ- ності апроксимації. Застосування сплайнів для класифікації функціональних даних було продемонстровано на задачі діагностики артриту за формою кісток. ВСТУП Нині існує велика кількість прикладів з різних галузей науки (біометрики, економетрики, хемометрики, метеорології тощо), спостереження, які отри- мано, представляються або можуть бути змодельовані гладкими кривими. Класифікація таких даних є складною задачею з точки зору алгоритмів штуч- ного інтелекту. Для формулювання проблеми в термінах статистичної кла- сифікації в роботі [1] було запропоновано відобразити функції у вектори вузлів апроксимуючого сплайна. Вузли в цьому випадку розглядались як вільні параметри, що значно покращує якість апроксимації. Але їх знахо- дження є багатовимірною, нелінійною та мультимодальною задачею опти- мізації з обмеженнями. Для розв’язку цієї задачі було розроблено ряд детер- міністичних методів [2], однак їх основними недоліками є залежність результату від вибору початкового вузлового вектора а також обмеження на порядок гладкості функцій. Ефективнішими за часом обчислення та точніс- тю апроксимації виявились метаевристики на основі генетичних алгоритмів [3] та методу рою часток [4]. Останній метод неможливо відтворити, оскіль- ки автори не надали ключових деталей для його реалізації. Нестача дієвих підходів слугує потребою в розробці нових, тому в цій статті буде запропо- новано спосіб знаходження вільних вузлів на основі методу диференціаль- ної еволюції. Вибір цього методу обрано за його кращою результативністю для більшості тестових функцій порівняно з еволюційними алгоритмами та методом рою часток [5] а також малою кількістю параметрів. Методи аналізу функціональних даних, які є аналогами класичних ста- тистичних методів, детально описані в монографії [6]. В цій роботі буде проведено порівняння результатів класифікації, отриманих методом функціо- нального дискримінантного аналізу [7] та методом з використанням сплай- нів з вільними вузлами для виявлення артриту за формою кісток. І.А. Коршунова ISSN 1681–6048 System Research & Information Technologies, 2014, № 2 116 Мета роботи — розробити ефективний метод знаходження вузлів ап- роксимуючих сплайнів, а також удосконалили спосіб, у який сплайни з віль- ними вузлами використовуються для класифікації функціональних даних. АПРОКСИМАЦІЯ СПЛАЙНАМИ З ВІЛЬНИМИ ВУЗЛАМИ Нехай маємо дані ,},{ ii yx для абсцис }{ ix яких виконується умова bxxxxa mii   ...... 11 , та }{ iy є зашумленими вимірами функції iiii xfyxf  )(:)( , ).,...,1( mi  Мірою точності апроксимації функції сплайном s є .))(( 1 2   m i ii xsy (1) Функція s може бути вибрана з n-вимірного простору ,,tkS який складається з усіх поліноміальних сплайнів s порядку 1k з послідовністю вузлів }{ jtt , де knnnkk ttbttatt   ......... 111 (2) та nm  . Сплайн s може бути представлений у вигляді лінійної комбінації В-сплайнів:    n j jkjBs 1 ,  , де kjB , — послідовність нормалізованих B-плайнів порядку k для заданої послідовності вузлів .t kjB , можуть бути обраховані за рекурсивною формулою Кокса-де Бура:       випадках,іншихв0 ,якщо,1 )( 1 1, jj j ttt tB )()()( 1,1 1 1, 1 , tB tt tt tB tt tt tB kj jkj kj kj jkj j kj            Введемо наступні позначення: матриця спостережень B ,))(( ,...,1 ,,...,1, nj miikj xB   вектор коефіцієнтів сплайну njj ,...,1)(  α , вектор зна- чень функції miiy ,...,1)( y , враховуючи які формулу (1) можна переписати як: 2 )(),( αtByαt  . (3) Для фіксованої послідовності вузлів задача мінімізації виразу (2) є лінійною: }:)(),({min 2 nR ααtByαt . (4) Якщо вузли є вільними параметрами, то отримуємо нелінійну мультимодаль- ну задачу оптимізації з обмеженнями на значення вузлів за нерівністю (2): },~,:)~(),~({min 2 tααtByαt ln RR  (5) де lT lpp tt R ),...,(~ )()1(t — вектор вільних вузлів з індексами ))((1),...,( lppp , які задовольняють нерівність 1)()1(  nlp...pk . Остання умова означає, що лише вузли nk tt ,...,1 можуть бути вільними, оскільки інтервал ];[ ba задано від початку. Класифікація функціональних даних за допомогою сплайнів з вільними вузлами … Системні дослідження та інформаційні технології, 2014, № 2 117 Задача (4) називається повною апроксимаційною задачею, яка є еквіва- лентною до спрощеної задачі [2]: }~:)~()~(()~({min 2 tytBtBIt l) R  (6) де було виконано підстановку ytBα  )~( . ,)~( tB що в даному випадку означає псевдоінверсію Мура-Пенроуза матриці .B МЕТОД ДИФЕРЕНЦІАЛЬНОЇ ЕВОЛЮЦІЇ Метод диференціальної еволюції призначено для знаходження глобального оптимуму недиференційованих, нелінійних, мультимодальних функцій ба- гатьох змінних. Цей метод належить до класу метаевристик, тому не існує гарантії знаходження оптимального розв’язку. Але, як свідчать експеримен- тальні розрахунки [8], для багатьох проблем він є робастним та у більшості випадках швидко збігається до оптимуму. Нехай max,,x ,...,0,1,...,0),( ggNpiP gig  x — популяція з номе- ром g з D-вимірних точок (векторів) .1,...,0),(x ,,,  Djx gijgi Розмір по- пуляції — Np. Першим кроком алгоритму є генерування початкової популяції 0,xP , на якому координати кожної точки ініціалізуються наступними значеннями: ,1,...,0,1,...,0,))(1,0(rand ,,,0,,  DjNpibbbx LjLjUjij де Ujb , та Ljb , — верхня та нижня межі j-тої координати. Нове покоління векторів генерується у такий спосіб: для кожної точки gi,x зі старого покоління g вибираються три різні випадкові точки gr ,0x , gr ,1x , ,x ,2 gr що не дорівнюють gi,x , та генерується мутантний вектор за формулою: ),xx(xv ,2,1,0gi, grgrgr F  (7) де ]1,0(F — масштабний множник диференціального вектора. Над мутантним вектором (7) виконується операція «схрещування», яка полягає в заміщенні його координат відповідними координатами з початко- вого вектора gi,x (кожна координата заміщається з деякою ймовірністю Cr, але хоча б одна змінюється завжди):       випадкуіншомув або)1,0(randякщо, u ,, rand,, ,,gi, gij jgij gij x jjCrv u . (8) Отриманий після схрещування вектор ui,g називається пробним векто- ром. Якщо його значення цільової функції краще, то в новому поколінні вектор gi,x замінюється на пробний вектор: .випадкуіншомув )()(якщо, , ,,, 1,      gi gigigi gi x xfufu x (9) І.А. Коршунова ISSN 1681–6048 System Research & Information Technologies, 2014, № 2 118 БАГАТОКРИТЕРІАЛЬНА ОПТИМІЗАЦІЯ Багатокритеріальна оптимізація — це процес одночасної оптимізації двох або більше конфліктуючих цільових функцій у заданій області визначення. Задача формулюється наступним чином:  )(),...,(),(min 21 xfxfxf k  , де ,Sx  .,...,2,: KkRRf n k  Вона полягає в пошуці оптимального за Па- рето вектора цільових змінних, тобто такого ,* Sx   що не існує ,Sx  для якого виконується )()( xfxf kk   при Kk ,...,1 та )()( xfxf kk   для бо- дай одного .k Множину оптимальних за Парето розв’язків називають Парето-фронтом. Цю множину, як показано в [8], можна знайти методом диференціальної еволюції, де умову (9) замінено на:         випадку.іншомув ),x()u(:,...,1якщо, x , ,,, 1, gi gikgikgi gi x ffKku РОЗРОБЛЕНИЙ МЕТОД Найголовнішим етапом роботи є пошук вільних вузлів сплайна, тобто зна- ходження розв’язку задачі (6). Бажано, щоб метод їх обрахунку був нечут- ливим до похибок виміру вхідних даних, мав невеликий час роботи та збіга- вся до точки глобального оптимуму. На жаль, останню умову виконати найважче, тому що цільова функція зазвичай має велику кількість локальних мінімумів. Для розв’язку задачі (6) в порівнянні з класичним методом диференціа- льної еволюції у зв’язку з необхідністю виконання умови (2) було введено наступні зміни:  Точки початкової популяції ініціалізуються значеннями лише з до- пустимої області, що відповідає виконанню нерівності (2).  Під час генерації мутантного вектора враховуються межі зміни абсцис:          .якщо, ,якщо),)(1,0(rand ,якщо),)(1,0(rand v ,,,, ,,,0,,0, ,,,0,,0, ,,, bvav bvxbx avxax v gijgij gijgrjgrj gijgrjgrj gijgi  У разі виходу мутантної або пробної точки за межі допустимої області відбувається симетричне відображення відносно площини gix ,,0 .,,1,,1 giDgi xx    Масштабний множник та ймовірність схрещування на кожній ітера- ції змінюються за наступними формулами [9]: , )(max min constbest best F f,f )f,(f F gg gg , )max( min constbest 1 best best 1 best Cr ,ff ),f(f Cr gg gg   де best 1 best , gg ff — найкраще значення цільової функції в g-ій та (g-1)-й попу- ляції, gf — середнє значення функції в g-ій популяції. constconst , CrF — ста- Класифікація функціональних даних за допомогою сплайнів з вільними вузлами … Системні дослідження та інформаційні технології, 2014, № 2 119 лі значення параметрів класичної диференціальної еволюції обрані з [10] залежно від розмірності задачі. Критерієм закінчення пошуку є  worstbest gg ff , де worst gf — найгір- ше значення цільової функції в g-й популяції, а .710  e ЕКСПЕРИМЕНТАЛЬНІ РОЗРАХУНКИ Тестування методу диференціальної еволюції для знаходження вільних вуз- лів проводилось на наборі функції [4] наведених на рис. 1, які можуть місти- ти точки розриву (функції № 2, 6) та каспи (функція № 3). Аналітичні вира- зи функції наведено в табл. 1. В усіх випадках функція вимірювалась в 201 точці та область визначен- ня зводилась до [0;1]. Похибка вимірів (шум)  розподілений за нормальним законом ),0( 2N . Наведена в табл. 1 кількість вільних вузлів є оптималь- ною згідно роботи [4] при порядку сплайна 4. Цільовою функцією виступав інформаційний критерій Байеса (BIC): )12)(ln()(ln  klmmBIC  , де m — кількість вимірів функції,  — значення цільової функції, l — кількість вільних вузлів, k — порядок сплайна. Отримані усереднені за 30 дослідів значення BIC для тестових функцій: ,1134)( 1 fBIC ,1129)( 2 fBIC ,1133)( 3 fBIC ,36)( 4 fBIC )( 5fBIC ,15 .280)( 6 fBIC Час обчислення вузлів в середньому становить 2с (CPU 2,4 GHz). Графічні результати апроксимації сплайнами з вільними вузлами, що знаходяться за допомогою розробленого методу, наведено на рис. 2. Рис. 1. Графік тестових функцій f1(x) f2(x) f4(x) f5(x) f6(x) x x x x x x f3(x) І.А. Коршунова ISSN 1681–6048 System Research & Information Technologies, 2014, № 2 120 Т а б л и ц я 1 . Аналітичні вирази тестових функцій та контрольні параметри Вираз функції Область визначення N(0, 2 ) Кількість вузлів )4,0(1001 1 90 )(   te tf ]1;0[t 1 4         2 2 2 )65,0(015,0 1 )3,0(01,0 1 )( t ttf 6,00  t 16,0  t 1 8 500 )510(100 )( 2 5103    t e tf t ]1;0[t 1 5 230 4 2)(sin)( tettf  ]2;2[t 06,0 5 22)2(sin)( 216 5   tettf ]2;2[t 06,0 6            2 2 2 6 )1( 3 16 2 3 )7104( 3 4 )43(4 )( tt ttt tt tf 175,0 5,05,0 5,00    t t t 03,0 4 Оскільки метою роботи є аналіз функціональних даних, то проілюстру- ємо алгоритм на конкретному прикладі класифікації пацієнтів за формою мищелка стегнової кістки на два класи: хворих на артрит та здорових [7]. Перші кроки алгоритму, що детально описані в [7], включають параме- тризацію за довжиною кривої початкових даних (рис. 3). Результат на рис. 4 ілюструє отримані рівномірно розподілені по довжині контуру точки пара- метричної функції )}.(),({)( tytxtz  f1(x) f2(x) f3(x) f4(x) f5(x) f6(x) x x x x x x Рис. 2. Графічні результати апроксимації сплайнами з вільними вузлами (розташу- вання вузлів та їх кратність позначено точками під графіком) Класифікація функціональних даних за допомогою сплайнів з вільними вузлами … Системні дослідження та інформаційні технології, 2014, № 2 121 З рис. 4 очевидно, що функція є неоднозначною, тому її безпосередня сплайн-апроксимація неможлива. Варіантом вирішення цієї проблеми є ап- роксимація )(tx та )(ty окремо (їх приклади наведено на рис. 5 та рис. 6 відповідно). Щоб визначити кількість параметрів моделі — число вільних вузлів та порядок сплайну було проведено багатокритеріальну оптимізацію за конф- ліктуючими критеріями — часом обрахунку та значеннями BIC для середніх кривих )(tx та ).(ty Це дозволяє знайти найбільш просту модель з оптималь- ним для нас часом обрахунку, що важливо для великих наборів даних. Для обох випадків кількість вузлів було обрано рівною 6, а порядок сплайну для )(tx та )(ty — 4 та 3 відповідно. Класифікація контурів кісток відображених у вектори вільних вузлів апроксимуючих сплайнів здійснювалась методом k найближчих сусідів. Для оцінки точності класифікатора було проведено перехресну перевірку. Тес- товий набір складає 96 екземплярів, з яких 21 — хворий. Кращі результати було отримано під час врахування лише вільних вузлів функцій )(tx та при кількості найближчих сусідів .4k Рис. 5. Параметризовані абсциси y x Рис. 6. Параметризовані ординати y x Рис. 3. Початкові дані y x y x Рис. 4. Параметризовані дані І.А. Коршунова ISSN 1681–6048 System Research & Information Technologies, 2014, № 2 122 Для оцінки якості класифікації доцільним є використання кореляційно- го коефіцієнту Метью (у термінах прикладної статистики — фі-коефіцієнт) [11]: ))()()(( FNTNFPTNFNTPFPTP FNFPTNTP MCC    , де TP (true positives) та TN (true negatives) — кількість істиннопозитивних та істиннонегативних результатів класифікації, FP (false positives) та FN (false negatives) — кількість помилок першого та другого роду відповідно. На ос- нові перелічених показників можна порахувати наступні характеристики класифікатора, які зазвичай застосовуються для оцінки медичних тестів:  TPR (True Positive Rate) — ймовірність позитивного результату (наявність артриту), якщо пацієнт хворий;  TNR (True Negative Rate) — ймовірність негативного результату (відсутність артриту), якщо пацієнт не хворий;  PPV (Positive Predictive Value) — ймовірність наявності хвороби при позитивному результаті тесту;  NPV (Negative Predictive Value) — ймовірність відсутності хвороби при негативному результаті тесту. Оскільки метод пошуку вузлів належить до метаевристик, то збіжність до одного мінімума при неоднократному перерахунку не гарантовано. Цей факт впливає на результати класифікації. За результатами 100 експеримен- тів основні статистичні показники розподілу ймовірності MCC, TPR, TNR, PPV та NPV наведено в табл. 2. Т а б л и ц я 2 . Статистичні показники характеристик класифікатора Характеристики класифікатора Медіана Мінімум Максимум Перша квартиль Третя квартиль Викиди TPR 0,429 0,286 0,571 0,381 0,476 __ TNR 0,92 0,84 0,973 0,893 0,933 0,84, 0,853 PPV 0,588 0,4 0,8 0,529 0,667 0,8 NPV 0,848 0,815 0,885 0,841 0,864 0,885 MCC 0,397 0,133 0,638 0,304 0,466 __ ПОРІВНЯННЯ З ІНШИМИ РОБОТАМИ Для порівняння ефективності розробленого методу знаходження вільних вузлів сплайна було обрано лише ті алгоритми, що можуть працювати з усі- ма наведеними тестовими функціями. Як свідчать результати з табл. 3, модифікований метод диференціальної еволюції переважно має кращі пока- зники ніж генетичний алгоритм, але гірші за метод рою часток. Однак, як вже зазначалось, наведені в [4] результати складно відтворити, оскільки ав- тори не надали детальний опис методу. Класифікація функціональних даних за допомогою сплайнів з вільними вузлами … Системні дослідження та інформаційні технології, 2014, № 2 123 Т а б л и ц я 3 . Порівняння методів знаходження вільних вузлів апрокси- муючого сплайна Автор та посилання Основа методу Кількість ітерацій Значення BIC Час обчислення Yoshimoto [3] Генетичні алгоритми 200–300 11701150),,( 321 fffBIC 193)( 4 fBIC 49)( 5 fBIC 231)( 6 fBIC Десятки секунд Galvez [4] Метод рою часток 10 1101)( 1 fBIC 1027)( 2 fBIC 1012)( 3 fBIC 279)( 4 fBIC 63)( 5 fBIC 340)( 6 fBIC 10-1 – 1 с. Розроблений метод (2012) Метод диференціа- льної еволюції 50 1134)( 1 fBIC 1129)( 2 fBIC 1133)( 3 fBIC 36)( 4 fBIC 15)( 5 fBIC 280)( 6 fBIC 1-4 с. Наведемо результати перехресної перевірки отримані методом дискри- мінантного аналізу на основі 6 головних компонент [7]: MCC = 0,360, TPR = = 0,667, TNR = 0,747, PPV = 0,424, NPV = 0,889. На рис. 7 візуально проде- монстровані характеристики класифікатора на основі вільних вузлів апрок- симуючих сплайнів (результати з роботи [7] відмічено лініями). З наведених даних не випливає однозначної оцінки розробленого кла- сифікатора. Завдяки високому TNR класифікатор є більш специфічним, тоб- Рис. 7. Графіки статистичних показників результатів класифікації І.А. Коршунова ISSN 1681–6048 System Research & Information Technologies, 2014, № 2 124 то він краще діагностує достеменно хворих. Наприклад, це важливо у ви- падку, коли гіпердіагностика пацієнтів небажана. Також отримане середнє значення MCC на 10% краще за попередній результат. ВИСНОВКИ В роботі представлено метод класифікації функціональних даних на основі вільних вузлів апроксимуючих сплайнів. Описаний підхід є універсальним для даних представлених не лише гладкими кривими але й такими, що міс- тять точки розриву або каспи. Це узагальнення стало можливим внаслідок розробки нового методу пошуку вільних вузлів. На цей час це один із неба- гатьох методів, який може впоратись із подібною задачею за порівняно не- великий час та досягти високої точності. Однак за результативністю він уступає методу рою часток, тому потребує подальшої доробки. Напрямком удосконалення методу є підбір оптимальних параметрів диференціальної еволюції, значення яких значно впливають на час та точність обчислення. Варто відмітити, що порівняно з попередніми роботами, де кількість вузлів та порядок сплайна підбирались лише з мінімізації BIC, у цьому до- слідженні здійснювався вибір цих параметрів із урахуванням також часу обчислення. Як один з етапів аналізу функціональних даних за допомогою сплайнів з вільними вузлами, запропонований спосіб розрахунку кількості параметрів апроксимаційної моделі є доцільним, оскільки він здійснюється одноразово для типового представника з набору даних і зменшує час вико- нання найбільш трудомісткого процесу — апроксимації. ЛІТЕРАТУРА 1. Molinari N. Free Knot Splines for Supervised Classifcation // Journal of Classica- tion. — 2007. — № 24. — P. 221–234. 2. Schwetlick H., and Schutze T. Least squares approximation by splines with free knots // BIT Numerical mathematics. —1995. — № 35. — Р. 361–384. 3. Yoshimoto F., Harada T., Yoshimoto Y. Data fittingwith a spline using a real-coded algorithm // Journal Computer-Aided Design. — 2003. — № 35. — P. 751–760. 4. Galvez A., Iglesias A. Efficient particle swarm optimization approach for data fitting with free knot B-splines // Journal Computer-Aided Design. — 2011. — № 43. — P.1683–1692. 5. Vesterstrom J., Thomsen R. A comparative study of differential evolution, particle swarm optimization, and evolutionary algorithms on numerical benchmark prob- lems // Evolutionary Computation, 2004. CEC2004. Congress on. — 2004. — № 2. — P. 1980–1987. 6. Ramsay J.O., Silverman B.W. Functional Data Analysis // NY: Springer, 2005. 7. Ramsay J.O., Silverman B.W. Applied functional data analysis: methods and case studies // New York: Springer-Verlag, 2002. — P. 115–130. 8. Price K., Storn R.M., Eds. Differential Evolution. A practical approach to global op- timization // Germany: Springer-Verlag Berlin, 2005. 9. Guo Zhenyu, Cheng Bo, Eds. Self-Adaptive Chaos Differential Evolution // Lecture Notes in Computer Science. — 2006. — № 4221. — Р. 972–975. 10. Pedersen M. Good Parameters for Differential Evolution // Hvass Laborato- ries,Technical Report no. HL1002. — 2010. 11. Cramer H. Mathematical Methods of Statistics // Princeton: Princeton University Press, 1946. — P. 282. Надійшла 22.05.2012

Класифікація функціональних даних за допомогою сплайнів з вільними вузлами

Репозитарії

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