Топологический анализ данных (TDA)

[kaipa]

http://en.wikipedia.org/wiki/Topological_data_analysis

Никто не разбирался? Понимаю, что вряд ли, но вдруг? На уровне идеи кажется разумным. Есть даже компания Ayasdi в Пало-Альто, которая на основе TDA делает продукт.

Comments

[lzh]

Я теоретик и этим занимался с корыстной целью написать статью. Так что я пытался подобрать простые модельные задачи, на которых можно что-то понять про метод, - пока без особых успехов.

Если Вы поделитесь своей задачей (в той мере, в которой это не секрет), мне будет очень интересно, хотя я вряд ли смогу что-нибудь полезное сказать в ответ.

[ushastyi.livejournal.com]

Задача не секрет, она у многих возникает. Но, боюсь, не пощупав данные, с ней тяжело будет разобраться.

Но попробую дать ее в такой формулировке. Хотя в силу дискретности сложно формулировать математическим языком.

Есть набор X дискретных переменных (то есть каждая переменная принимает несколько дискретных значений). T(X, t) -- это некоторая последовательность во времени чисел (дискретных матриц чисел): то есть в момент t (на самом деле это не момент, а временной промежуток) для каждого значения переменной из X можно сопоставить некоторое значение. Чаще всего это значение -- 0. То есть всего может быть несколько миллионов возможных комбинаций, но не-нули около 1%. На всякий случай, dim T(X, t) = dim (X)

Есть другой набор Y дискретных переменных. И есть множество Z, каждый из элементов которого реализует некоторое значение Y (каждой из переменной).

I(T(X, t), Z, t) -- это некоторая "реализация" Z на T(X, t). В любой ячейке T(X, t) лежит какое-то число. I() описывает, как это число (количество) "расходуется" по разным Z. Для любой ячейки x из X, сумма по всем z из Z, I( T(x, t), z, t) = T(x, t). dim I = dim X

Далее, есть еще V(I) -- некоторый аналог функции цены, их может быть несколько.

Теперь, поскольку это описание малопонятно, в терминах предметной области:
X -- это описание параметров рекламных площадок (inventory),
T -- это трафик, который на них приходит
Y -- это описание параметров рекламных кампаний
Z -- описание самих кампаний (существующих, а не возможных)
I -- решение, о том, когда, где и в каком объеме каждую кампанию показывать
V -- измеренная эффективность кампании в данной ячейке трафика

У нас есть специальный адаптивный алгоритм, который вычисляет I на основании истории V(t<t0), чтобы максимизировать V(t0). Но возникает следующая задача. Пусть у нас есть новая кампания z1. Где ее лучше всего показывать? Проблема в том, что для нее нет еще истории, а набрать достаточно статистики и истории может быть очень дорого. Чтобы как-то подсказать алгоритму , нам надо понять, на какую кампанию или группу кампаний похожа новая. Иногда это можно сделать декларативно. Но иногда нет. Для проверки гипотезы "похожести" необходимо кластеризовать и факторизовать T или V. И там сразу все сложно и неприятно. В частности из-за разряженности матриц. Приходится отбрасывать некоторые переменные (уменьшать размерность, аналог проекции), чтобы уменьшить количество нулей. У меня возникла мысль, что топологический подход может дать что-то новое тут. Поскольку топология может позволить абстрагироваться от размерности. Но возможно, что я ошибаюсь.

[lzh]

Кажется, мне рассказывали похожую задачу в контексте управления складом в глобальной розничной сети. Если уж применять к ней "топологические" методы, я бы начал с manifold learning (кстати, ЖЖ-юзер misha-b является одним из ведущих теоретиков в этой области). Но мне кажется, правильнее пытаться явно ввести разумную структуру графа на Z и опираться на достижения спектральной теории графов и learning on graphs.

[ushastyi.livejournal.com]

Спасибо, подумаю.