Самоорганізаційна карта

Самоорганізаційна карта Кохонена (англ. Self-organizing map — SOM) — нейронна мережа з некерованим навчанням, яка використовується для конструювання багатовимірного простору в простір з нижчою розмірністю (найчастіше, двовимірний). Створює дискретне представлення вхідних просторів навчальних вибірок, які називаються картою (англ. map), і тому використання цього типу нейронної мережі є методом для зниження розмірності. Самоорганізовані карти відрізняються від інших штучних нейронних мереж, оскільки вони застосовують конкурентне навчання, яке є протилежним до навчання з виправленням помилок (наприклад, метод зворотного поширення помилки з градієнтним спуском), і в тому сенсі, що вони використовують функцію сусідства для збереження топологічних властивостей вхідного простору.

Це робить самоорганізовані карти корисними для візуалізації шляхом створення маловимірних зображень багатовимірних даних, цей процес схожий на багатовимірне шкалювання. Штучна нейронна мережа, впроваджена фінським професором Теуво Кохоненом у 1980-х роках, іноді називають картою Кохонена або мережею Кохонена. Мережа Кохонена є зручною для обчислювання абстракцією, що ґрунтується на біологічних моделях нейронних систем з 1970-х років, та моделі морфогенезу, що були впроваджені ще Аланом Тюрінгом у 1950-х роках.

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

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

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

Широко використовується ^[en]. Значення U-матриці конкретного вузла — це середня відстань між ваговим вектором вузла та його найближчими сусідами. Наприклад, у квадратній сітці ми можемо розглядати найближчі 4 або 8 вузлів (окіл фон Неймана і Мура, відповідно) або шість вузлів у гексагональній сітці.

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

Структура та операції

Як і більшість штучних нейронних мереж, самоорганізаційні карти працюють у двох режимах: навчання та відображення (англ. mapping). «Навчання» створює карту використовуючи вхідні приклади (конкурентний процес, або ^[en]), тоді як «відображення» автоматично класифікує новий вхідний вектор.

Видимою частиною самоорганізаційні карти є простір карти, який складається з компонентів, які називаються вузлами або нейронами. Простір карти визначається заздалегідь, як правило, як скінчення двовимірна область, де вузли розташовані у правильній гексагональній або прямокутній сітці. Кожен вузол пов'язаний з «ваговим» вектором, який є позицією у вхідному просторі; тобто, цей вектор має таку ж розмірність, що і кожний вхідний вектор. Хоча вузли в просторі карти залишаються фіксованими, тренування полягає в переміщенні векторів ваги у напрямку вхідних даних (зменшення метрики відстані) без псування топології, індукованої з простору карти. Таким чином, самоорганізаційна карта описує відображення (англ. mapping) з багатовимірного вхідного простору до картографічного простору з меншою вимірністю. Після навчання карта може класифікувати вектор з вхідного простору, знаходячи вузол з найближчим (найменшою метричною відстанню) ваговим вектором до вхідного вектора простору.

Алгоритм навчання

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

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

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

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

Навчання використовує конкурентне навчання. Коли навчальний приклад подається в мережу, обчислюється її евклідова відстань до всіх векторів ваги. Нейрон, чий ваговий вектор найбільш схожий на вхідний, називається найкращим вузлом відповідності (НВВ, англ. best matching unit). Ваги цього вузла та нейронів, близьких до нього в сітці самоорганізаційної карти, коригуються до вхідного вектора. Величина зміни зменшується з часом та з відстанню сітки від найкращого вузла відповідності. Формула оновлення нейрона v з ваговим вектором W_v(s) має вигляд

${\displaystyle W_{v}(s+1)=W_{v}(s)+\theta (u,v,s)\cdot \alpha (s)\cdot (D(t)-W_{v}(s))}$,

де s — індекс кроку, t — індекс в навчальній вибірці, u — індекс НВВ для вхідного вектора ${\displaystyle D(t)}$, ${\displaystyle \alpha (s)}$ — коефіцієнт навчання, який монотонно зменшується; ${\displaystyle \theta (u,v,s)}$ — функція сусідства, яка дає відстань між нейроном u і нейроном v на етапі s. Залежно від реалізації, t може сканувати набір навчальних даних, що систематично вибирається випадковим чином з набору даних (статистичний бутстреп), або реалізувати інший метод вибірки (наприклад, складано-ножева перевибірка). (t = 0, 1, 2,…,T-1, потім повторюється, T — розмір навчальної вибірки).

Функція сусідства ${\displaystyle \theta (u,v,s)}$ залежить від відстані між найкращим вузлом відповідності (нейрон u) та нейрона v. У найпростішому випадку беруть 1 для всіх нейронів, достатньо близьких до НВВ, та 0 для інших, проте, натомість часто використовують функцію Гауса. Незалежно від функціональної форми, функція сусідства стискається з часом. На початку, коли сусідство є далеким, самоорганізація відбувається в глобальному масштабі. Коли окіл зменшується до декількох нейронів, ваги сходяться до локальних оцінок. У деяких реалізаціях коефіцієнт навчання ${\displaystyle \alpha }$ та функція сусідства ${\displaystyle \theta }$ неухильно зменшуються зі збільшенням s, в інших випадках (зокрема, коли t сканує набір даних навчання) вони зменшуються покроково, один раз на кожні T кроків.

Цей процес повторюється для кожного вхідного вектора для (зазвичай великого) числа циклів ${\displaystyle \lambda }$. Мережа зав'язує вихідні вузли з групами або шаблонами у наборі вхідних даних. Якщо ці шаблони можна назвати, їх імена можуть бути прикріплені до відповідних вузлів в натренованій мережі.

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

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

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

Змінні

• ${\displaystyle s}$ поточна ітерація,
• ${\displaystyle \lambda }$ ліміт ітерацій,
• ${\displaystyle t}$ індекс цільового вхідного вектора даних у вхідній множині ${\displaystyle \mathbf {D} }$,
• ${\displaystyle {D}(t)}$вектор цільових вхідних даних,
• ${\displaystyle v}$ індекс вузла на карті,
• ${\displaystyle \mathbf {W} _{v}}$поточний вектор ваги вузла ${\displaystyle v}$,
• ${\displaystyle u}$ індекс найкращого вузла відповідності на карті,
• ${\displaystyle \theta (u,v,s)}$ функція сусідства, а також
• ${\displaystyle \alpha (s)}$коефіцієнт навчання.

Алгоритм

1. Розташувати в довільному порядку вектори ваги вузла на карті
2. Випадковим чином вибирати вхідний вектор
3. Обійти кожен вузол на карті
   1. Використовуючи формулу евклідової відстані, для знаходження схожості між вхідним вектором і ваговим вектором вузла карти
   2. Запам'ятовуємо вузол, який має найменшу відстань (цей вузол є найкращим вузлом відповідності, BMU)
4. Оновити вагові вектори вузлів в околі BMU (включаючи сам BMU) шляхом наближення їх до вхідного вектора
   1. ${\displaystyle W_{v}(s+1)=W_{v}(s)+\theta (u,v,s)\cdot \alpha (s)\cdot (D(t)-W_{v}(s))}$
5. Збільшити ${\displaystyle s}$ та повторювати крок 2 поки ${\displaystyle s<\lambda }$

Або інший варіант алгоритму:

1. Розташувати в довільному порядку вектори ваги вузла на карті
2. Обійти кожен вхідний вектор із набору вхідних даних
   1. Обійти кожен вузол на карті
      1. Використовуючи формулу евклідової відстані, для знаходження схожості між вхідним вектором і ваговим вектором вузла карти
      2. Запам'ятовуємо вузол, який має найменшу відстань (цей вузол є найкращим вузлом відповідності, BMU)
   2. Оновити вагові вектори вузлів в околі BMU (включаючи сам BMU) шляхом наближення їх до вхідного вектора
      1. ${\displaystyle W_{v}(s+1)=W_{v}(s)+\theta (u,v,s)\cdot \alpha (s)\cdot (D(t)-W_{v}(s))}$
3. Збільшити ${\displaystyle s}$ та повторювати крок 2 поки ${\displaystyle s<\lambda }$

Ініціалізація самоорганізаційної карти Кохонена

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

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

Інтерпретація

Картографічне зображення самоорганізуючої карти (U-матриці) на основі даних статей Вікіпедії (частота слів). Відстань обернено пропорційно подібності. «Гори» є краями між кластерами. Червоні лінії є посиланнями між статтями.

Одновимірний аналіз SOM та аналіз головних компонент (МГК) для наближення даних. SOM — це червона лінія з квадратами, 20 вузлів. Перша головна компонента представлена блакитною лінією. Точки даних — маленькі сірі кола. Для МГК, частка невідповідностей, що не пояснюється в цьому прикладі, становить 23,23 %, для SOM — 6,86 %. Principal Component Analysis and Self-Organizing Maps: applet, University of Leicester, 2011</ref>

Існує два способи інтерпретації самоорганізаційної карти Кохонена. Оскільки в фазі тренування ваги околиці всіх сусідів переміщуються в одному напрямку, подібні предмети мають тенденцію збуджувати сусідні нейрони. Таким чином, самоорганізаційна карта утворює семантичну карту, де схожі приклади зображаються близькими один до одного, а несхожі — протилежними. Це може бути візуалізовано U-матрицею (евклідова відстань між ваговими векторами сусідніх клітин) SOM..

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

Самоорганізаційну карту можна вважати нелінійним узагальненням методу головних компонент (МГК). Було показано що SOM має багато переваг, при використанні як штучних, так і реальних геофізичних даних над звичайними методами вилучення ознак, такими як емпіричні ортогональні функції (МЕОФ) або МГК.

Спочатку SOM не була сформульована як розв'язання проблеми оптимізації. Однак, було зроблено кілька спроб змінити визначення SOM і сформулювати задачу оптимізації, яка дає подібні результати. Наприклад, ^[en] використовують механічну метафору еластичності для наближення основних різновидів аналогією є еластична мембрана та пластина.

Альтернативи

• ^[en] (англ. generative topographic map, GTM) є потенційною альтернативою самоорганізованої карти Кохонена. У тому сенсі, що ПТК явно вимагає плавного та безперервного відображення від вхідного простору до простору карти, це збереження топології. Проте в практичному сенсі ця міра топологічного збереження відсутня.
• (англ. time adaptive self-organizing map, TASOM) є розширенням базової самоорганізованої карти Кохонена. TASOM використовує адаптивні навчальні оцінки та функції сусідства. Вона також включає параметр масштабування, щоб зробити мережу інваріантною до масштабування, переміщення та обертання вхідного простору. TASOM та його варіанти використовувалися в декількох застосуваннях, включаючи адаптивну кластеризацію, багаторівневе обмеження, апроксимація вхідного простору та активне моделювання контуру. Крім того, було запропоновано двійкове дерево TASOM або BTASOM, що нагадує бінарне натуральне дерево, що має вузли, що складаються з мереж TASOM, де кількість його рівнів та кількість його вузлів адаптивні до його середовища.
• ^[en] (англ. growing self-organizing map, GSOM) — це зростаючий варіант самоорганізуючої карти. GSOM була розроблена для розв'язання питання визначення відповідного розміру карти в SOM. Вона починається з мінімального числа вузлів (зазвичай чотирьох) і створює нові вузли в межі на кордоні на основі евристики. Використовуючи значення, що називається коефіцієнтом розповсюдження, аналітик даних має можливість контролювати зростання GSOM.
• Підхід ^[en] запозичує зі сплайн-інтерполяції ідею мінімізації ^[en]. У процесі навчання він мінімізує суму квадратичної енергії вигину та розтягування з помилкою апроксимації найменших квадратів.
• Конформний підхід, що використовує конформне відображення для інтерполяції кожного навчального прикладу між вузлами сітки на безперервній поверхні. У цьому підході можливе плавне відображення «один в один».
• (OS-Map) узагальнює функцію сусідства та вибір переможця. Однорідна функція сусідства Гауса замінена експоненціальною матрицею. Таким чином можна задати орієнтацію або в просторі карти, або в просторі даних. Самоорганізаційна карта Кохонена має фіксований масштаб (= 1), так що карти «оптимально описують область спостереження». Але як щодо карти, що охоплює домен двічі або в n-разів? Це тягне за собою концепцію масштабування. OS-Map розглядає масштаб як статистичний опис кількості найкращих узгоджувальних вузлів на карті.

Використання

• Метеорологія та океанографія
• Визначення пріоритетів та відбір проектів
• Аналіз сейсмічних фацій для розвідки нафти і газу
• ^[en]
• Створення ілюстрації

Див. також

• Нейронна мережа Кохонена

Примітки

1. Kohonen, Teuvo; Honkela, Timo (2007). Kohonen Network. Scholarpedia.
2. Kohonen, Teuvo (1982). Self-Organized Formation of Topologically Correct Feature Maps. Biological Cybernetics. 43 (1): 59—69. doi:10.1007/bf00337288.
3. Von der Malsburg, C (1973). Self-organization of orientation sensitive cells in the striate cortex. Kybernetik. 14 (2): 85—100. doi:10.1007/bf00288907. PMID 4786750.
4. Turing, Alan (1952). The chemical basis of morphogenesis. Phil. Trans. R. Soc. 237 (641): 37—72. doi:10.1098/rstb.1952.0012.
5. Ultsch, Alfred; Siemon, H. Peter (1990). . У Widrow, Bernard; Angeniol, Bernard (ред.). Proceedings of the International Neural Network Conference (INNC-90), Paris, France, July 9–13, 1990. Т. 1. Dordrecht, Netherlands: Kluwer. с. 305—308. ISBN . Архів оригіналу за 13 червня 2013. {{}}: Cite має пустий невідомий параметр: |1= ()
6. Ultsch, Alfred (2003); U*-Matrix: A tool to visualize clusters in high dimensional data, Department of Computer Science, University of Marburg, Technical Report Nr. 36:1-12
7. Ultsch, Alfred (2007). Emergence in Self-Organizing Feature Maps. У Ritter, H.; Haschke, R. (ред.). Proceedings of the 6th International Workshop on Self-Organizing Maps (WSOM '07). Bielefeld, Germany: Neuroinformatics Group. ISBN .
8. Jaakko Hollmen (9 березня 1996). Self-Organizing Map (SOM). .
9. Haykin, Simon (1999). 9. Self-organizing maps. Neural networks - A comprehensive foundation (вид. 2nd). Prentice-Hall. ISBN .
10. Kohonen, Teuvo (2005). Intro to SOM. SOM Toolbox. Процитовано 18 червня 2006.
11. Kohonen, Teuvo; Honkela, Timo (2011). Kohonen network. Scholarpedia. Процитовано 24 вересня 2012.
12. T. Kohonen, Self-Organization and Associative Memory. Springer, Berlin, 1984.
13. A. Ciampi, Y. Lechevallier, Clustering large, multi-level data sets: An approach based on Kohonen self organizing maps, in D.A. Zighed, J. Komorowski, J. Zytkow (Eds.), PKDD 2000, Springer LNCS (LNAI), vol. 1910, pp. 353—358, 2000.
14. Akinduko, A.A.; Mirkes, E.M.; Gorban, A.N. (2016). SOM: Stochastic initialization versus principal components. Information Sciences. 364—365: 213—221. doi:10.1016/j.ins.2015.10.013.
15. Saadatdoost, Robab, Alex Tze Hiang Sim, and Jafarkarimi, Hosein. «Application of self organizing map for knowledge discovery based in higher education data.» Research and Innovation in Information Systems (ICRIIS), 2011 International Conference on. IEEE, 2011.
16. Yin, Hujun; Learning Nonlinear Principal Manifolds by Self-Organising Maps, in ; Kégl, Balázs; Wunsch, Donald C.; and Zinovyev, Andrei (Eds.); Principal Manifolds for Data Visualization and Dimension Reduction, Lecture Notes in Computer Science and Engineering (LNCSE), vol. 58, Berlin, Germany: Springer, 2008,
17. Liu, Yonggang; Weisberg, Robert H (2005). . Journal of Geophysical Research. 110 (C6): C06003. Bibcode:2005JGRC..110.6003L. doi:10.1029/2004JC002786. Архів оригіналу за 9 травня 2009. Процитовано 16 квітня 2019.
18. Liu, Yonggang; Weisberg, Robert H.; Mooers, Christopher N. K. (2006). . Journal of Geophysical Research. 111 (C5): C05018. Bibcode:2006JGRC..111.5018L. doi:10.1029/2005jc003117. Архів оригіналу за 21 квітня 2009. Процитовано 16 квітня 2019.
19. Heskes, Tom; Energy Functions for Self-Organizing Maps, in Oja, Erkki; and Kaski, Samuel (Eds.), Kohonen Maps, Elsevier, 1999
20. ; Kégl, Balázs; Wunsch, Donald C.; and Zinovyev, Andrei (Eds.); Principal Manifolds for Data Visualization and Dimension Reduction, Lecture Notes in Computer Science and Engineering (LNCSE), vol. 58, Berlin, Germany: Springer, 2008,
21. Kaski, Samuel (1997). Data Exploration Using Self-Organizing Maps. Mathematics, Computing and Management in Engineering Series No. 82. Espoo, Finland: Finnish Academy of Technology. ISBN . {{}}: Проігноровано |journal= ()
22. Shah-Hosseini, Hamed; Safabakhsh, Reza (April 2003). TASOM: A New Time Adaptive Self-Organizing Map. IEEE Transactions on Systems, Man, and Cybernetics—Part B: Cybernetics. 33 (2): 271—282. doi:10.1109/tsmcb.2003.810442. PMID 18238177.
23. Shah-Hosseini, Hamed (May 2011). Binary Tree Time Adaptive Self-Organizing Map. Neurocomputing. 74 (11): 1823—1839. doi:10.1016/j.neucom.2010.07.037.
24. A. N. Gorban, A. Zinovyev, Principal manifolds and graphs in practice: from molecular biology to dynamical systems, , Vol. 20, No. 3 (2010) 219—232.
25. Liou, C.-Y.; Kuo, Y.-T. (2005). Conformal Self-organizing Map for a Genus Zero Manifold. The Visual Computer. 21 (5): 340—353. doi:10.1007/s00371-005-0290-6.
26. Liou, C.-Y.; Tai, W.-P. (2000). Conformality in the self-organization network. Artificial Intelligence. 116 (1–2): 265—286. doi:10.1016/S0004-3702(99)00093-4.
27. Hua, H., 2016. Image and geometry processing with Oriented and Scalable Map. Neural Networks, 77, pp.1-6.
28. Liu, Y., and R.H. Weisberg (2011) A review of self-organizing map applications in meteorology and oceanography. In: Self-Organizing Maps-Applications and Novel Algorithm Design, 253—272.
29. Zheng, G. and Vaishnavi, V. (2011) "A Multidimensional Perceptual Map Approach to Project Prioritization and Selection, " AIS Transactions on Human-Computer Interaction (3) 2, pp. 82-103
30. Taner, M. T.; Walls, J. D.; Smith, M.; Taylor, G.; Carr, M. B.; Dumas, D. (2001). Reservoir characterization by calibration of self-organized map clusters. SEG Technical Program Expanded Abstracts. 2001: 1552—1555. doi:10.1190/1.1816406.
31. Chang, Wui Lee; Pang, Lie Meng; Tay, Kai Meng (March 2017). Application of Self-Organizing Map to Failure Modes and Effects Analysis Methodology. Neurocomputing. PP: 314—320. doi:10.1016/j.neucom.2016.04.073.
32. ANNetGPGPU CUDA Library with examples [1] GPU accelerated image creation

Література

• Осовский С. Нейронные сети для обработки информации. — М.: Финансы и статистика, 2002. — 244 с.
• Хайкин С. Нейронные сети: полный курс. — М.: Вильямс, 2006. — 1104 с.
• Паклин Н. Б., Орешков В. И. Бизнес-аналитика: от данных к знаниям. — СПб.: Питер, 2013. — 704 с.
• Матвійчук А. В. Штучний інтелект в економіці: нейронні мережі, нечітка логіка: монографія. / А. В. Матвійчук. — К. : КНЕУ, 2011.– 439 с.
• Кохонен Т. Самоорганизующиеся карты. — М.: БИНОМ. Лаборатория знаний, 2008. — 655 с.
• T. Kohonen, «Self-Organizing Maps», Springer, 1995.
• Trevor Hastie, Robert Tibshirani, Jerome Friedman. Chapter 14.4 Self-Organizing Maps // The Elements of Statistical Learning. — 2009. — С. 528-534.