„Осъзнаване на големите данни“

Разопаковане на швейцарската ролка с дифузионни карти

Удивителният алгоритъм за намаляване на размерността, за който може би никога не сте чували

Алгоритмите за намаляване на размерността играят важна роля в инструментариума на всеки практикуващ данни. Те не само могат да се използват по време на етапа на проучване за визуализиране на данни и получаване на важни прозрения, прилагането на намаляване на размерността към набор от данни може също да подобри предсказващата сила на всеки алгоритъм за машинно обучение, който впоследствие се изпълнява върху него.

Популярните алгоритми включват анализ на основните компоненти (със и без ядра), Isomap, локално-линейни вграждания и t-SNE. В тази статия бих искал да представя един от любимите си алгоритми:дифузионни карти.

Дифузионните карти са нелинеен алгоритъм, което означава, че могат да се прилагат към проблеми, при които линейните методи като PCA са неуспешни. Те използват концепцията за случайни разходки, за да разкрият основната геометрична структура на нашия набор от данни. С напредването на (въображаемото) време тази случайна разходка интегрира локални характеристики на нашите данни, за да изгради глобална картина. Използването на тази техника позволява да се открият колектори с по-ниско измерение, както и несвързани клъстери в данните.

Алгоритъмът

Свързаност

Нека си представим нашите точки от данни като градове, свързани с пътища. Поставяме нашия произволен пътник, наричаме го Джо, във всеки град на тази карта и му казваме да започне да се движи. Джо произволно ще реши кои пътища да поеме, но тъй като е доста мързелив и винаги търси топла храна и легло, естествено ще предпочете да поеме по-кратки пътища, водещи до по-близки градове. Въпреки че във всеки момент Джо има информация само за непосредствената си близост — той пътува само по указателни табели — с течение на времето можем да анализираме пълния път, изминат от него, и по този начин да научим нещо за глобалното разпределение на градовете.

За да можем наистина да използваме тази идея, трябва да я изразим в математически термини. Нека наречем нашите градове (точки с данни) x1, x2, x3 и т.н. Можем да дефинираме връзката между два града като pij=p(xi,xj). Тази свързаност може да се тълкува като вероятността нашият произволен пътник да се премести от град xj до xi. Важно е да се отбележи, че тази вероятност не е симетрична, т.е. pij≠pji: За да определи pij, Джо трябва да претегли всички налични опции, докато е на xj. След като той достигне до xi, тези опции може да изглеждат напълно различни. Така че, докато вероятността за преминаване от xj към xi може да е висока, същото не е непременно вярно за движение в обратната посока.

Все още можем да дефинираме симетрично количество kij — често наричано ядро ​​— което зависи само от мярка за разстоянието между градовете. Едно популярно ядро ​​се дава от така наречената радиална базисна функция или гаусово ядро:

където d(xi,xj) обикновено се приема за евклидово разстояние, а ϵ е хиперпараметър, който определя обхвата на ефективното съседство на точка от данни. Придържайки се към нашата аналогия, ϵ може да се разглежда като желанието на Джо да пътува далеч, по-малко ϵ води до по-малко припокриване между далечни градове и по-мързелив Джо.

За да преминем от ядрото kij към свързаността pij, трябва да нормализираме първото:

с

Обобщавайки всички възможни дестинации xi, това съответства на нашия произволен пътник, който претегля всичките си опции, докато се намира на xj, както беше споменато по-рано.

Можем да запишем връзките pij под формата на матрица P. Ако имаме само два града, тази матрица ще изглежда по следния начин:

Читателят, който е по-склонен към математиката, може да разпознае това като преходната матрица на веригата на Марков за крайно пространство на състоянието. За нас P просто обобщава вероятността за преместване от едно място на друго за една времева стъпка. В нашия пример една времева стъпка може да означава един ден. Ами ако искаме да знаем къде е Джо след два дни? Можем да получим вероятностите, като умножим P със себе си

Интересното е, че не би трябвало да знаем умножението на матрицата, за да стигнем до този резултат. Достатъчно е да следвате всички възможни пътища и да ги сумирате. Вземете за пример първия ред и първата колона на P², което съответства на вероятността да започнете в град 1 и да завършите в град 1 след два дни. Случайният ходещ има две възможности да постигне това: той или просто остава в град 1 (p11p11), или се премества в град 2 и след това се връща (p12p21).

Дифузионно разстояние

Сега, след като дефинирахме мярка за свързаност, бихме искали да установим понятието разстояние на дифузия. Всички сме запознати с евклидовото разстояние, което ефективно измерва дължината на нишка, необходима за свързване на две точки в пространството с права линия. Бихме искали обаче новото ни разстояние да използва идеята за свързаност. Дори ако две точки са далеч една от друга по отношение на евклидовото разстояние, тяхното дифузионно разстояние трябва да е малко, ако са добре свързани, т.е. ако има много точки от данни и следователно жизнеспособни пътища между тях.

Можем да запишем разстояние, което отговаря на този критерий, както следва:

Dt(xi,xj) е така нареченото разстояние на дифузия след t времеви стъпки (дни) между точките xi и xj. Ако това уравнение изглежда малко непосилно на пръв поглед, винаги е поучително да разгледаме няколко примера. Представете си, че нашите данни са организирани в два несвързани клъстера (Фигура вляво). За да опростим нашия анализ, ще разгледаме само случая t=1.

  1. ако и двете точки са еднакви xi=xj, Dt е нула. Това всъщност е задължително свойство за всеки показател за разстояние.
  2. ако xi и xj са в един и същи клъстер, pt(xi,xu) и pt(xj,xu) винаги ще имат подобна величина: Ако xu е в същия клъстер като xi и xj, и двете вероятности ще бъдат високи, ако е в отделен клъстер, и двата ще бъдат ниски. Следователно вероятностите винаги (почти) се унищожават и D1(xi,xj) ще бъде малък
  3. ако xi и xj са в отделни клъстери, pt(xi,xu) и pt(xj,xu) винаги ще имат различни величини: Без значение в кой клъстер е xu, една от вероятностите ще бъде висока, докато другата е ниска. Следователно всички членове в сумата са големи по величина, което води до голямо разстояние на дифузия D1(xi, xj)

Убедихме се, че Dt наистина осигурява добра мярка за разстоянието на дифузия между две точки от данни, но как да го изчислим? Нека започнем, като дефинираме векторите Yi като колекция от всички връзки, водещи до точка xi:

След това откриваме, че евклидовото разстояние ||⋅||E между тези вектори съответства на разстоянието на дифузия между нашите първоначални точки от данни

Евклидовото разстояние в дифузионното пространство (Y) съответства на дифузионното разстояние в пространството на данните (X)

Почти имаме работещ алгоритъм, така че имайте търпение тук. Последната стъпка, която трябва да разгледаме как се изчислява Pt. Вземането на мощности на матрици е непрактично, но се оказва, че ако първо диагонализираме матрицата, задачата се опростява значително:

If

като Λ е диагоналната матрица, изпълнена със собствени стойности на P, тогава

Ако оставим ψj да обозначи j’-тия (ляв) собствен вектор на Pt, тогава Yi може просто да се запише като

където ψ1,i е i-тият компонент на първия собствен вектор на P. Тук се случва магията: всички собствени стойности на P са между 0 и 1. Всъщност обикновено само няколко собствени стойности са близки до 1, докато всички други са изчезващо малки. Времето напредва и t се увеличава, тези малки и междинни собствени стойности бързо намаляват (вземането на степен на число, по-малко от 1, намалява неговата величина). Сега можем да твърдим, че за точното изчисляване на разстоянието на дифузия е достатъчно да се запазят членове с относително големи собствени стойности, всички останали могат безопасно да бъдат премахнати. Да кажем например, че само λ1, λ2, λ3 са със значителна величина, тогава можем да изхвърлим всички други членове и да получим вектор

живеещи в триизмерно намалено пространство, в което евклидовото разстояние е добро приближение на дифузионното разстояние в пълното пространство на данните. Затова разработихме алгоритъм за намаляване на размерността.

Алгоритъм (обобщение)

Дадено: Набор от данни X, състоящ се от редове xi

  1. Изчислете матрицата на ядрото K с елементи kij

2. Получаване на матрицата на преходите P чрез нормализиране на K

с

3. Диагонализиране на P и сортиране на собствените стойности и съответните леви собствени вектори в низходящ ред

4. (Скъсеният) набор от n собствени вектора ψ1,2,…,n обхваща пространство с намалена размерност (ако n ‹ N), в което наборът от данни може да бъде ефективно представен.

Примери

Сред многото приложения на този алгоритъм бих искал да очертая две: многообразно обучение и откриване на несвързани клъстери.

Разнообразно обучение

Често е разумно да се приеме, че високомерните данни от реалния живот се намират в по-нискомерен колектор (Ако сте объркани от математическия термин „колектор“, просто мислете за него като за различна дума за „форма“. Грубо казано, многообразието не е нищо повече от обобщаване на повърхност към по-високи измерения).

Представете си следния пример: Снимки на ваза са направени от различни ъгли и с различно осветление. Тези снимки се съхраняват на компютър в разделителна способност 30x30 пиксела, всяка от които може да приеме непрекъсната стойност. Технически, данните живеят в 900-измерно пространство, което ще представлява голямо предизвикателство за повечето алгоритми за машинно обучение поради „проклятието на размерността“. Вглеждайки се по-отблизо обаче, разбираме, че всяка снимка е на една и съща ваза и проблемът наистина се свежда до 4-измерен: три стойности за ъглите, от които е направена снимката, и една за силата на осветяване. Ако знаем тези четири стойности, можем да реконструираме всяко изображение в набора от данни.

Следователно ключово предизвикателство е да се дестилира съответният колектор от данни с голямо измерение. Дифузионните карти, способни да разпознават глобални структури, като същевременно поддържат локален ред, са особено подходящи за тези видове проблеми:

Разбира се, изображенията по-горе показват само набори от данни за играчки, които вече са с ниска размерност за илюстративни цели. Ключовото послание е, че алгоритъмът ще работи и в много по-високи измерения, при условие че данните се намират на подколектор.

Откриване на несвързани клъстери

Освен колектори за обучение, или по-скоро като негово разширение, можем да използваме дифузионни карти, за да открием дали има несвързани клъстери в нашия набор от данни. Отново използвайки набори от данни за играчки, получаваме следните резултати:

Разбира се, алгоритъмът ще работи и при проблеми с по-високи измерения, за които не можем да различим отделни клъстери, като просто гледаме данните.

Има две ключови прозрения:

На първо място, както казахме преди, евклидовото разстояние след прилагане на дифузионната карта съответства на дифузионното разстояние преди прилагането на алгоритъма. Следователно несвързаните клъстери, за които разстоянието на дифузия по дефиниция е голямо, ще бъдат картографирани на отделни места. Точките в рамките на един клъстер имат изчезващо малко разстояние на дифузия и следователно ще бъдат нанесени върху една точка.

Второто прозрение е, че спектърът на собствените стойности всъщност може да ни даде информация за наличието на клъстери в нашите данни. По-конкретно, броят на собствените стойности, които са равни на 1, съответства на броя на (съвършено) несвързани клъстери. Един от начините да разберете това е както следва: Собствените стойности λn проследяват как разстоянието на дифузия се развива с течение на времето (t се увеличава). При по-голямо t вероятността за прескачане между отдалечени точки се увеличава, което означава, че разстоянието им на дифузия става по-малко. Това се улавя от факта, че λt+1›λt във всички случаи с изключение на λ=1. Като разширение всяка собствена стойност, която не е равна на единица, ще отиде до нула при t→∞. Наличието на λ=1 собствени стойности показва, че има пътища, които остават непроменени в границата на големи t, т.е. пътища между клъстери, чиято свързаност винаги е нула.

Заключение

Надявам се, че успях да ви убедя, че дифузионните карти са мощен алгоритъм, който трябва да бъде част от инструментариума на всеки практикуващ данни. Струва си да се отбележи, че няма решение „един размер за всички“. В крайна сметка всеки алгоритъм трябва да бъде внимателно подбран, за да съответства на данните, с които се работи. Дифузионните карти са мощни, когато става въпрос за откриване на нискоразмерни многообразия и нелинейни връзки във вашите данни. Те изискват много малко настройка (само един хиперпараметър) и за разлика от много други алгоритми за намаляване на размерността, те са много устойчиви на отклонения. Една характеристика на дифузионните карти, която ме очарова, е, че те — ако се използват правилно — запазват топологията на вашия набор от данни (дупките се картографират в дупки, както в нашия пример с швейцарско руло). Това доведе до голям интерес в общността на физиците към използването на дифузионни карти за откриване на топологични фази на материята (вижте например тук).

Ако ви е харесала тази статия, моля, не се колебайте да ме последвате тук, в twitter или се свържете в LinkedIn.

Препратки

[1] J. de la Porte, B. M. Herbst, W. Hereman, S. J. van der Walt, Въведение в дифузионните карти

[2] Р. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner и S. W. Zucker, Геометрични дифузии като инструмент за хармоничен анализ и дефиниране на структура на данни: дифузионни карти, PNAS 24 май, 2005 102 (21) 7426–7431