Пружна карта

Порівняння нелінійного методу головних різноманіть і лінійного методу головних компонент (МГК) [1] для візуалізації даних генетичних чіпів по експресії генів в раку грудей: a) Розташування вузлів карти і двовимірна головна поверхню, спроектована на тривимірне лінійне різноманіття перших трьох головних компонент. Розподіл точок даних викривлення і не може бути адекватно апроксимувати двовимірної головною площиною; b) Розподіл проекцій точок даних у внутрішні координати двовимірної нелінійної головної поверхні (ELMap2D) разом з оцінкою щільності точок; c) Те ж, що і b), але для лінійного двовимірного головного різноманіття (PCA2D). "Базальний" ("basal") підтип раку грудей візуалізується більш адекватно на нелінійному відображенні ELMap2D, а також деякі особливості розподілу точок даних (такі як, невеликі локальні згущення щільності) краще відображені в порівнянні з PCA2D. Головні різноманіття побудовані з використанням методу пружних карт. Дані про експресії генів взяті з [2]. Програмне забезпечення доступне для вільного некомерційного використання. [3] [4]

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

За побудовою, пружна карта являє собою систему пружних пружин, вкладену в багатомірний простір даних [1] [5]. Ця система апроксимується двовимірне різноманіття. Зміна коефіцієнти пружності системи дозволяє користувачеві перемикатися від абсолютно неструктурованої кластеризації методом K-середніх (в межі нульовий пружності) до різноманіття близьким до лінійним різноманіття головних компонент (в межі дуже великих модулів вигину і малих модулів розтягування). У проміжному діапазоні значень коефіцієнти пружності, система ефективно апроксимується деякий нелінійне різноманіття. Даний підхід грунтується на аналогії з механікою: головне різноманіття, що проходить через "середину" даних, може бути представлено як пружна мембрана або пластинка. Метод був розроблений проф., Д.ф.-м.н. А. Н. Горбанем, к.т.н. А. Зінов'євим і к.т.н А. Пітенко в 1996-2001 рр..


1. Пружна енергія карти

Нехай набір даних буде представлений безліччю векторів S в скінченновимірних евклідових просторів. "Пружна карта" представлена ​​набором її вузлів W_j в тому ж просторі. Для кожної точки даних s \ in S , Визначається вузол-"господар" (host) як найближчий до точки вузол карти W_j (Якщо виявиться, що найближчих вузлів декілька, то вибирається просто вузол з найменшим порядковим номером). Набір даних S ділиться на класи-таксони K_j = \ {s \ | \ W_j \ mbox {is a host of} s \} .

Енергія апроксимації є попросту середньоквадратичне ухилення від вузлів карти

D = \ frac {1} {2} \ sum_ {j = 1} ^ k \ sum_ {x \ in K_j} \ | x-W_j \ | ^ 2,

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

Необхідно ввести наступну додаткова структуру на безлічі вузлів. Деякі пари вузлів, (W_i, W_j) , З'єднані пружними зв'язками-ребрами. Позначимо набір ребер графа як E . Крім того, будемо об'єднувати деякі трійки вузлів, (W_i, W_j, W_k) в "ребра жорсткості". Позначимо набір ребер жорсткості як G .

Енергія розтягування пружною карти визначається як U_ {E} = \ frac {1} {2} \ lambda \ sum_ {(W_i, W_j) \ in E} \ | W_i-W_j \ | ^ 2;
Енергія згину пружною карти визначається як U_G = \ frac {1} {2} \ mu \ sum_ {(W_i, W_j, W_l) \ in G} \ | W_i-2W_j + W_l \ | ^ 2;

де \ Lambda і \ Mu є коефіцієнти пружності на розтяг і згин відповідно.

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

Енергія пружної карти визначена як U = D + U_E + U_G.

Ми вимагаємо від вкладення карти того, щоб карта перебувала б в механічному рівновазі: карта повинна мінімізувати енергію пружності U .


2. Алгоритм максимізації очікування ( EM-алгоритм)

Для заданого розбиття набору даних S на класи K_j , Мінімізація квадратичного функціонала U зводиться до задачі розв'язання системи лінійних рівнянь з розрідженою матрицею коефіцієнти. Цілком аналогічно ітеративного алгоритму побудови головних компонент або алгоритмом методу K-середніх, може бути використаний прийом "розщеплення":

  • Для заданого положення вузлів \ {W_j \} знаходимо \ {K_j \} ;
  • Для заданого розбиття \ {K_j \} мінімізуємо U і знаходимо \ {W_j \} ;
  • Якщо конфігурація вузлів мало змінюється, завершити процес, інакше повторити ітерацію.

Подібний алгоритм максимізації очікування гарантує збіжність до локального мінімуму U . Для того, щоб поліпшити апроксимації, можуть бути використані різні додаткові методи: наприклад, стратегія "розм'якшення". Згідно цьому прийому, ми повинні почати побудову карти з дуже жорсткої системи (малі довжини ребер, малі вигини і великі значення коефіцієнти пружності \ Lambda і \ Mu ), А завершувати побудова "гнучкої" системою (малі значення \ Lambda і \ Mu ). Навчання карти проходить у декілька етапів, причому кожен етап характеризується своєю пружністю.

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


3. Застосування

Приклад використання головної кривої, побудованої методом пружних карт: Нелінійний індекс якості життя [6]. Тут точки являють собою дані про 171 країнах в 4-мірному просторі сформованому значеннями чотирьох показників: валовий дохід на душу населення, очікувана тривалість життя, дитяча смертність, захворюваність туберкульозом. Різні форми і кольору точок відображають різні географічні розташування. Товста червона лінія зображує "головну криву", апроксимується набір даних.

Головні застосування метод знайшов в біоінформатики [7] [8], для розвідувального аналізу та візуалізації багатовимірних даних, для візуалізації даних в економіці, соціології та політології [9], як допоміжний метод для візуалізації даних різної природи, прив'язаних до географічній сітці. Останнім часом метод був адаптований як засіб для систем підтримки прийняття рішень для відбору, оптимізації та організації біржових кошиків. [10]


Примітки

  1. 1 2 AN Gorban, AY Zinovyev, Principal Graphs and Manifolds - arxiv.org/abs/0809.0490, З: Handbook of Research on Machine Learning Applications and Trends: Algorithms, Methods and Techniques, Olivas ES et al Eds. Information Science Reference, IGI Global: Hershey, PA, USA, 2009. 28-59.
  2. Wang, Y., Klijn, JG, Zhang, Y., Sieuwerts, AM, Look, MP, Yang, F., Talantov, D., Timmermans, M., Meijer-van Gelder, ME, Yu, J. et al.: Gene expression profiles to predict distant metastasis of lymph-node-negative primary breast cancer. Lancet 365, 671-679 (2005); Набір даних у мережі - www.ihes.fr/ ~ zinovyev/princmanif2006 /
  3. A. Zinovyev, ViDaExpert - bioinfo-out.curie.fr/projects/vidaexpert / - Multidimensional Data Visualization Tool (free for non-commercial use). Institut Curie, Paris.
  4. A. Zinovyev, ViDaExpert overview - www.ihes.fr/ ~ zinovyev / vida / ViDaExpert / ViDaOverView.pdf, IHES - www.ihes.fr ( Institut des Hautes tudes Scientifiques), Bures-Sur-Yvette, le-de-France.
  5. 1 2 А. Ю. Зінов'єв. Візуалізація багатовимірних даних - www.ict.edu.ru/ft/003892//index.html. Красноярськ: Вид-во КДТУ, 2000. - 168 с.
  6. AN Gorban, A. Zinovyev, Principal manifolds and graphs in practice: from molecular biology to dynamical systems - arxiv.org/abs/1001.1122, International Journal of Neural Systems - www.worldscinet.com/ijns/, Vol. 20, No. 3 (2010) 219-232.
  7. AN Gorban, B. Kegl, D. Wunsch, A. Zinovyev (Eds.), Principal Manifolds for Data Visualisation and Dimension Reduction - pca.narod.ru / contentsgkwz.htm, LNCSE 58, Springer: Berlin - Heidelberg - New York, 2007. ISBN 978-3-540-73749-0
  8. M. Chacn, M. Lvano, H. Allende, H. Nowak, Detection of Gene Expressions in Microarrays by Applying Iteratively Elastic Neural Net - pca.narod.ru / ElNetChakon.pdf, In: B. Beliczynski et al. (Eds.), Lecture Notes in Computer Sciences, Vol. 4432, Springer: Berlin - Heidelberg 2007, 355-363.
  9. A. Zinovyev, Data visualization in political and social sciences - arxiv.org/abs/1008.1188, In: SAGE - www.uk.sagepub.com/books/Book231996 " International Encyclopedia of Political Science - www.sage-ereference.com/abstract/ intlpoliticalscience/n129.xml ", Badie, B., Berg-Schlosser, D., Morlino, LA (Eds.), 2011.
  10. M. Resta, Portfolio optimization through elastic maps: Some evidence from the Italian stock exchange - www.springerlink.com/content/6416210h727016t5/, Knowledge-Based Intelligent Information and Engineering Systems, B. Apolloni, RJ Howlett and L. Jain (eds.), Lecture Notes in Computer Science, Vol. 4693, Springer: Berlin - Heidelberg, 2010, 635-641.