Comments 26
«измерений набора параметров» — лучше звучит, имхо — «векторов обучающей выборки»… т.к. на слово измерений у меня сразу ассоциация с размерностью почему-то :) Ну и про решение в меньшее количество строк кода: здеся — только вот насчет быстрой скорости, я не уверен.
По ссылке, как я понял — метод основанный на нейронных сетях. Исходный код — не на C, а на «супер-пупер» neurolab и Python, поэтому количество строк сравнивать довольно трудно. Думаю, если его расписать без библиотеки на С++/#/дельфи и т.п., то получится многомильёновтыщ листов А1 :-)
Хотя, конечно, использование такой коротенькой сетки и результаты меня, например, впечатлили.
Хотя, конечно, использование такой коротенькой сетки и результаты меня, например, впечатлили.
О, знакомый код. На самом деле, всё ещё проще: newc в neurolab это реализация самоорганизующейся карты Кохонена (сейчас это действительно называется нейросетью, но когда Кохонен её придумывал, он этого не знал), которая, если разобраться, реализует банальное итеративное вычисление среднего арифметического. Это ровно одна формула, а программно — строчек двадцать. И вам можно сделать это даже проще, чем реализовано в Neurolab, поскольку вы точно знаете, что у вас один центр сгущения (а кластеризация самоорганизующейся картой обычно предполагает множество центров).
Формула: w(k+1) = w(k) + a * |x(k)-w(k)|, где k — это номер итерации, w — найденная точка центра, x — очередное наблюдение, a — настроечный параметр, может уменьшаться с ростом k, ещё часто берут a = 1/(N+1), где N — число наблюдений. |x(k)-w(k)| — это расстояние между очередным наблюдением и вычисленной на текущий момент точкой центра в любой удобной вам метрике.
Это «банальное вычисление среднего арифметического» работает в подавляющем большинстве случаев и ломается только на крутых, бессовестных и многичесленных выбросах. Ваши картинки, впрочем, не производят такого впечатления, но если что — и на это есть приёмчики.
И не могли бы вы рассказать, как вы такие красивые примеры делаете? Я тоже хочу на них поэксперементировать.
Формула: w(k+1) = w(k) + a * |x(k)-w(k)|, где k — это номер итерации, w — найденная точка центра, x — очередное наблюдение, a — настроечный параметр, может уменьшаться с ростом k, ещё часто берут a = 1/(N+1), где N — число наблюдений. |x(k)-w(k)| — это расстояние между очередным наблюдением и вычисленной на текущий момент точкой центра в любой удобной вам метрике.
Это «банальное вычисление среднего арифметического» работает в подавляющем большинстве случаев и ломается только на крутых, бессовестных и многичесленных выбросах. Ваши картинки, впрочем, не производят такого впечатления, но если что — и на это есть приёмчики.
И не могли бы вы рассказать, как вы такие красивые примеры делаете? Я тоже хочу на них поэксперементировать.
Я тоже начинал с нескольких случайно выбранных точек (будущих центров сгущения) и объединением пришедшей точки с ближайшим из них. Сломался на двух вещах:
— во-первых, как искать ближайший центр, если их перебирается штук 20. Для линейного поиска многовато, а организовывать их в деревья вроде бы еще рано. Сделал линейный поиск, но это было долго, особенно с учетом следующего пункта.
— во-вторых, как принимать решение о создании нового центра и объединении двух имеющихся. Написал, что объединять надо два ближайших друг к другу центра, если расстояние между ними меньше, чем расстояние от точки до ближайшего, но при слишком большом фоне это работать не будет: в 5-мерном пространстве любая точка фона, скорее всего, окажется «далеко» от любого небольшого конечного множества. В общем, плюнул, и решил подойти совсем с другой стороны.
Примеры делаются просто.
x=frand(); y=frand();
dx=a*x*x*(1-x); dy=a*y*y*(1-y);
swicth(alg){
case 0: x-=dx; y-=dy; break;
case 1: x-=dy; y-=dx; break;
case 2: x+=dy; y-=dx; break;
}
if(x>=0 && x<1 && y>=0 && y<1) AddPoint(x,y);
Параметр a выбирается где-то между 2 и 3.5 (в случае alg=1 — между 2 и 3, иначе возникает противная полоса перехлеста в районе x+y=0.25).
— во-первых, как искать ближайший центр, если их перебирается штук 20. Для линейного поиска многовато, а организовывать их в деревья вроде бы еще рано. Сделал линейный поиск, но это было долго, особенно с учетом следующего пункта.
— во-вторых, как принимать решение о создании нового центра и объединении двух имеющихся. Написал, что объединять надо два ближайших друг к другу центра, если расстояние между ними меньше, чем расстояние от точки до ближайшего, но при слишком большом фоне это работать не будет: в 5-мерном пространстве любая точка фона, скорее всего, окажется «далеко» от любого небольшого конечного множества. В общем, плюнул, и решил подойти совсем с другой стороны.
Примеры делаются просто.
x=frand(); y=frand();
dx=a*x*x*(1-x); dy=a*y*y*(1-y);
swicth(alg){
case 0: x-=dx; y-=dy; break;
case 1: x-=dy; y-=dx; break;
case 2: x+=dy; y-=dx; break;
}
if(x>=0 && x<1 && y>=0 && y<1) AddPoint(x,y);
Параметр a выбирается где-то между 2 и 3.5 (в случае alg=1 — между 2 и 3, иначе возникает противная полоса перехлеста в районе x+y=0.25).
А зачем вам сливать/порождать центры, если известно, что он только один? Вы просто берёте, например, случайную точку (вообще случайную или наблюдение) и говорите «это центр», а потом подаёте наблюдения по одному и двигаете центр по формуле, которую я описал выше. Согласно этой формуле, каждое наблюдение «тянет» центр в свою сторону, в итоге он двигается в направлении, где наблюдений больше, а если их достаточно много, то оказывается в их центре тяжести. Важно, что центр является независимой точкой в том же пространстве, что и наблюдения, а не привязывается к какому-то из наблюдений, как в вашем алгоритме. Возможно, в вашей задаче это допустимо, но в общем случае довольно притянуто: я не раз сталкивался с кольцами и прочими тороидами в данных, центр которых лежал в пустоте.
Ваш подход изящен, но численно всё-таки тяжелее. Кроме того, у него есть недостаток, который мне видится крайне существенным: хотя вы говорите в требованиях об одном проходе по всем данным, алгоритм, насколько я понял, работает только после сортировки данных, что является довольно сильным допущением и само по себе уже требует и прохода, и хранения в памяти. А если данные подаются вам в реальном времени в процессе измерений?
За алгоритм генерации выборки спасибо, так просто, а так красиво =)
Ваш подход изящен, но численно всё-таки тяжелее. Кроме того, у него есть недостаток, который мне видится крайне существенным: хотя вы говорите в требованиях об одном проходе по всем данным, алгоритм, насколько я понял, работает только после сортировки данных, что является довольно сильным допущением и само по себе уже требует и прохода, и хранения в памяти. А если данные подаются вам в реальном времени в процессе измерений?
За алгоритм генерации выборки спасибо, так просто, а так красиво =)
Мне не известно, что центр один. Точки приходят не очень в случайном порядке, у «неуспешных» измерений могут быть свои точки сгущения, а кроме того, пространство результатов, в действительности, зациклено, причем форму фундаментальной области и топологию склейки вычислить сложно (а ущерб от ошибки в вычислениях этой формы может быть слишком велик). Поэтому, если центр окажется близко к краю фундаментальной области, то с других сторон могут появиться «побочные» центры. Мне сгодится любой из них, но методу усреднения они помешают.
Входные данные целиком я не храню, беру от них только старшие биты. На реальное время алгоритм, конечно, не рассчитан. Хотя его можно применить для инициализации множества центров: собрать информацию о первом миллионе точек, найти (довольно быстро) области сгущения, а потом использовать их в итеративных алгоритмах. Но плохо будет, если в первый миллион измерений попал только шум, а полезный сигнал пошел потом.
Ну, и можно сделать так:
— заполнили массив
— отсортировали
— взяли каждую вторую точку, не заботясь об уникальности выборшенных точек
— заполнили освободившуюся половину массива
— перешли к шагу 2.
После сортировки собираем и показываем текущее состояние точек сгущения.
Насчет того, что результатом оказывается точка — вторую половину алгоритма я планирую переделать на метод «скользящего среднего». Жаль только, что точки придется распаковывать. Но если куб, выбранный в качестве области усреднения, окажется меньше, чем дырка в кольце, то центр, конечно, не найдут — остановятся где-то на краю кольца. И тут, в самом деле, зависит от задачи — какой ответ будет более адекватным.
Входные данные целиком я не храню, беру от них только старшие биты. На реальное время алгоритм, конечно, не рассчитан. Хотя его можно применить для инициализации множества центров: собрать информацию о первом миллионе точек, найти (довольно быстро) области сгущения, а потом использовать их в итеративных алгоритмах. Но плохо будет, если в первый миллион измерений попал только шум, а полезный сигнал пошел потом.
Ну, и можно сделать так:
— заполнили массив
— отсортировали
— взяли каждую вторую точку, не заботясь об уникальности выборшенных точек
— заполнили освободившуюся половину массива
— перешли к шагу 2.
После сортировки собираем и показываем текущее состояние точек сгущения.
Насчет того, что результатом оказывается точка — вторую половину алгоритма я планирую переделать на метод «скользящего среднего». Жаль только, что точки придется распаковывать. Но если куб, выбранный в качестве области усреднения, окажется меньше, чем дырка в кольце, то центр, конечно, не найдут — остановятся где-то на краю кольца. И тут, в самом деле, зависит от задачи — какой ответ будет более адекватным.
Я, наверное, недостаточно ясно выразился — у вас, конечно, могут быть локальные сгущения и, например, концентрации выбросов — но вам нужен только один, настоящий центр, а значит только его вы и рассчитываете. Формула, которую я дал, найдёт центр тяжести всей выборки. Если в выборке будет два равновесных сгущения («гантеля»), точка ляжет посередине между ними, если просто есть достаточно массивное сгущение, то точка в какой-то степени сдвинется в его сторону от настоящего центра. Но если выбросы распределены нормально, то точка гарантировано найдёт правильный центр. Никакого слияния/разделения сгущений выполнять не придётся, потому что сгущения только «тянут» на себя центр, но не детектируются непосредственно.
Ну и плюс алгоритм может работать в реальном времени и не боится дырок в данных. Попробуйте, это же просто. Ну или я на выходных попробую на ваших красивых картинках =)
Если же проблема выбросов действительно велика (есть концентрации или, наоборот, очень большой диапазон… то есть, обобщая, они распределены ненормально), то нужны так называемые робастные алгоритмы. Я готов обсудить это в личке, как раз сейчас над этим работаю. Тема, увы, слишком обширна для комментариев.
Ну и плюс алгоритм может работать в реальном времени и не боится дырок в данных. Попробуйте, это же просто. Ну или я на выходных попробую на ваших красивых картинках =)
Если же проблема выбросов действительно велика (есть концентрации или, наоборот, очень большой диапазон… то есть, обобщая, они распределены ненормально), то нужны так называемые робастные алгоритмы. Я готов обсудить это в личке, как раз сейчас над этим работаю. Тема, увы, слишком обширна для комментариев.
Последнее время столько всего говорят про всякие «облачные веб технологии», что уже начинает тошнить :-) Было приятно обнаружить, что топик к этому не относится.
По сабжу:
Для таких наглядных задач, хотелось бы увидеть какие-нибудь иллюстрации, пусть не в 4Д, но хоть в 2Д. Примеры «облаков» и найденные центры. Примеры, когда алгоритм показывает локальные аномалии какие-нибудь, и, когда находит так, как хочется. Может удалось бы четко сформулировать, в каких задачах алгоритм находит четко то, что надо. Еще неплохо бы проиллюстрировать сам ход алгоритма, а то человеку с плохим пространственным воображением, типа меня, читать не так наглядно.
Но, в целом, автору спасибо :-). Интересно было узнать про k-d дерево, и пример его применения. Код не комментирую, т.к. далек от С#.
По сабжу:
Для таких наглядных задач, хотелось бы увидеть какие-нибудь иллюстрации, пусть не в 4Д, но хоть в 2Д. Примеры «облаков» и найденные центры. Примеры, когда алгоритм показывает локальные аномалии какие-нибудь, и, когда находит так, как хочется. Может удалось бы четко сформулировать, в каких задачах алгоритм находит четко то, что надо. Еще неплохо бы проиллюстрировать сам ход алгоритма, а то человеку с плохим пространственным воображением, типа меня, читать не так наглядно.
Но, в целом, автору спасибо :-). Интересно было узнать про k-d дерево, и пример его применения. Код не комментирую, т.к. далек от С#.
Простите, что в нескольких комментариях, зацепила интересная задачка. Подумал тут еще, что хотелось бы услышать четкую формулировку задачи. Что такое — «точка сгущения» в данном случае? Ведь общепринятое математическое определение сюда не подходит т.к. множество точек в данной задаче — не непрерывное вааще :-)
Так что это тут? Точка, в радиусе 5 см которой, находится максимум точек? Или 10 см? Или это что-то другое? В данном облаке, на картинке, какая из точек — точка сгущения?
А, вокруг которой много-много точек, но не большой плотности, или Б, вокруг которой всего 5 точек, но они очень близко?
Так что это тут? Точка, в радиусе 5 см которой, находится максимум точек? Или 10 см? Или это что-то другое? В данном облаке, на картинке, какая из точек — точка сгущения?
А, вокруг которой много-много точек, но не большой плотности, или Б, вокруг которой всего 5 точек, но они очень близко?
Да, без четкого определения тяжело. С другой стороны, любое разумное определение делает задачку намного более сложной для решения: описанная здесь эвристика для решения четко поставленной задачи явно не предназначена.
Но если пофантазировать:
Ясно, что для разделения случаев A и B нужен какой-то масштаб (или просто заданный внешним образом параметр). Например:
— задаем количество точек, и ищем наименьший круг, содержащий это количество точек;
— задаем размер круга, и ищем такое его положение, чтобы в него попало наибольшее количество точек;
— задаем какую-нибудь функцию N(d) (зависимость числа точек от радиуса круга) и ищем такой круг, чтобы для его радиуса r и количества попавших в него точек K отношение K/N® было максимальным
— Выбираем какой-нибудь параметр sigma, и ищем точку нашей области x0, для которой величина
sum(exp(-dist(x_i,x0)^2/sigma^2)) по всем точкам выборки x_i была бы максимальной.
При большом числе точек/размере области/параметре sigma в первом, втором и 4-м случаях будет выбран вариант A, а при малом — вариант B. В третьем случае результат будет зависеть от поведения функции N(d) вблизи нуля.
К сожалению, решение всех описанных задач требует хранения положений всех точек. Плюс быстрой навигации по пространству, в котором они находятся.
Но если пофантазировать:
Ясно, что для разделения случаев A и B нужен какой-то масштаб (или просто заданный внешним образом параметр). Например:
— задаем количество точек, и ищем наименьший круг, содержащий это количество точек;
— задаем размер круга, и ищем такое его положение, чтобы в него попало наибольшее количество точек;
— задаем какую-нибудь функцию N(d) (зависимость числа точек от радиуса круга) и ищем такой круг, чтобы для его радиуса r и количества попавших в него точек K отношение K/N® было максимальным
— Выбираем какой-нибудь параметр sigma, и ищем точку нашей области x0, для которой величина
sum(exp(-dist(x_i,x0)^2/sigma^2)) по всем точкам выборки x_i была бы максимальной.
При большом числе точек/размере области/параметре sigma в первом, втором и 4-м случаях будет выбран вариант A, а при малом — вариант B. В третьем случае результат будет зависеть от поведения функции N(d) вблизи нуля.
К сожалению, решение всех описанных задач требует хранения положений всех точек. Плюс быстрой навигации по пространству, в котором они находятся.
Я попытался, у меня не получилось, но мне кажется, что все-таки это возможно, придумать четкую формулировку, для которой придуманный вами алгоритм подходит :-)
Наверное, можно. Но на последнем этапе алгоритм ищет «самую высокую песчинку на очень ровной, хотя и не гладкой вершине горы». В некоторых случаях это годится, а в остальных надо, хотя бы, запустить градиентный спуск по формуле с гауссовым весом. Кстати, это не очень сложно. Но время работы или сложность структур увеличит :(
Зато «полностью оформленную» задачу можно защищать уже, как хороший дипломный проект. А если учеба давно позади, как страшный сон — можно отдать, как почти готовый диплом, другу или продать за мильён студенту из кембриджа :-)
Друг полазит по сети и скажет, что этот велосипед изобрели уже тыщу раз. А мне лень, проще его еще раз придумать.
И, кстати, не думаю, что я бы засчитал это студенту за диплом. За курсовую еще туда-сюда.
Вы, наверное, очень требовательны =)
По сути же можно додумать все, что нужно для научного подхода, план работы:
1. постановка задачи, формулировка цели
2. выработка показателя эффективности нахождения точки… ляляля
3. Обзор существующих способов
4. Разработка собственного способа
5. Разработка красивой такой программы с графиками и точечками и окружностями, реализующая свой способ и некоторые другие.
6. Оценка степени достижения поставленной цели.
/садись пять :-)
По сути же можно додумать все, что нужно для научного подхода, план работы:
1. постановка задачи, формулировка цели
2. выработка показателя эффективности нахождения точки… ляляля
3. Обзор существующих способов
4. Разработка собственного способа
5. Разработка красивой такой программы с графиками и точечками и окружностями, реализующая свой способ и некоторые другие.
6. Оценка степени достижения поставленной цели.
/садись пять :-)
Формулировка, к которой подходит мой алгоритм, довольно очевидна (если хорошо подумать): я ищу точку сгущения на канторовом множестве. К сожалению, практической пользы от этого не очень много.
Кстати, про пользу, вы не упомянули, зачем это вам понадобилось, нахождение точки сгущения вот в таком виде. Очень интересно было бы услышать :-)
Принимается многочастотный сигнал, между фазами на разных частотах должны быть определенные соотношения. А они не выполняются, поскольку фазовые задержки на разных частотах различны. Надо эти задержки компенсировать, чтобы для «хорошего» сигнала соотношения выполнялись. Алгоритм будет искать наиболее вероятные сдвиги фаз для компенсации.
Из того, как сформулирована исходная задача, я бы сказал что формула может быть похожа на:
где нужно найти такие x,y при которых сумма некоторой функции от четырех параметров (xi, yi, x, y) по всем точкам множества минимальна.
А сама функция f, например может быть расстоянием: f = SQRT( (xi-x)^2 + (yi-y)^2).
Также надо рассмотреть поведение алгоритма для конфигураций типа Гантели.
Особенно симметричной гантели — будет два равнозначных места сгущений.
Было бы лучше, если бы алгоритм выдавал список сгущений с их мощностью (и/или плотностью).
Т.е. все точки нужно разбить на группы сгущения и при оценке сгущения группы (по формуле см.выше) не учитывать точки из других групп.
В качестве идеи по разбитию на группы можно предложить такой алгоритм: ищем все не соприкасающиеся треугольники с минимальной суммой длин сторон. Иными словами для любой точки возможно найти две ближайшие точки сумма расстояний между тремя точками будет минимальна.
Как только мы нарисуем все такие треугольники, мы можем выделить группы соприкасающихся треугольников. Назовем точки входящие в такие группы группами скопления. Для каждой такой группы можно определить мощность (скажем кол-во точек, площать (минимальный круг включающий все точки группы) и плотность).
где нужно найти такие x,y при которых сумма некоторой функции от четырех параметров (xi, yi, x, y) по всем точкам множества минимальна.
А сама функция f, например может быть расстоянием: f = SQRT( (xi-x)^2 + (yi-y)^2).
Также надо рассмотреть поведение алгоритма для конфигураций типа Гантели.
Особенно симметричной гантели — будет два равнозначных места сгущений.
Было бы лучше, если бы алгоритм выдавал список сгущений с их мощностью (и/или плотностью).
Т.е. все точки нужно разбить на группы сгущения и при оценке сгущения группы (по формуле см.выше) не учитывать точки из других групп.
В качестве идеи по разбитию на группы можно предложить такой алгоритм: ищем все не соприкасающиеся треугольники с минимальной суммой длин сторон. Иными словами для любой точки возможно найти две ближайшие точки сумма расстояний между тремя точками будет минимальна.
Как только мы нарисуем все такие треугольники, мы можем выделить группы соприкасающихся треугольников. Назовем точки входящие в такие группы группами скопления. Для каждой такой группы можно определить мощность (скажем кол-во точек, площать (минимальный круг включающий все точки группы) и плотность).
Треугольники — это из триангуляции Делане?
Проблема в том, что для построения всех треугольников (а в 5-мерном пространстве это будут, вероятно, симплексы) нам придется, во-первых, хранить координаты всех точек (а значит, как-то их упаковывать — больше 8 байт на точку я выделить не могу), а во-вторых, поддерживать структуру разбиения пространства на симплексы. В 2D треугольников примерно вдвое больше, чем точек, в 3D тетраэдров уже в 6 раз больше, а что происходит в 4D и 5D, я даже боюсь представить. Можно предположить, что симплексов в разбиении множества из 16 млн точек окажется около 2 миллиардов. В память точно не влезут.
И не очень вероятно, что алгоритмы, работающие с «треугольниками», будут достаточно быстрыми. Сейчас у меня 16 миллионов трехмерных точек обрабатывается чуть больше секунды, и еще есть ресурсы для оптимизации.
Про поиск нескольких точек сгущения надо подумать. К счастью, у меня такой задачи не стоит. Вероятно, после определения масштаба сгущения (минимального размера области, содержащей K точек) можно будет обрезать дерево на уровне этого размера, и искать в нем связные области. Но это уже будет многомерная геометрия, которой мне пока удалось избежать.
Проблема в том, что для построения всех треугольников (а в 5-мерном пространстве это будут, вероятно, симплексы) нам придется, во-первых, хранить координаты всех точек (а значит, как-то их упаковывать — больше 8 байт на точку я выделить не могу), а во-вторых, поддерживать структуру разбиения пространства на симплексы. В 2D треугольников примерно вдвое больше, чем точек, в 3D тетраэдров уже в 6 раз больше, а что происходит в 4D и 5D, я даже боюсь представить. Можно предположить, что симплексов в разбиении множества из 16 млн точек окажется около 2 миллиардов. В память точно не влезут.
И не очень вероятно, что алгоритмы, работающие с «треугольниками», будут достаточно быстрыми. Сейчас у меня 16 миллионов трехмерных точек обрабатывается чуть больше секунды, и еще есть ресурсы для оптимизации.
Про поиск нескольких точек сгущения надо подумать. К счастью, у меня такой задачи не стоит. Вероятно, после определения масштаба сгущения (минимального размера области, содержащей K точек) можно будет обрезать дерево на уровне этого размера, и искать в нем связные области. Но это уже будет многомерная геометрия, которой мне пока удалось избежать.
Строго говоря в N-мерном пространстве треугольники останутся треугольниками (имеется ввиду декартово пространство). Мера «расстояния» между двумя точками — это некоторая функция F (я привел ее для плоскости, т.е. двухмерного пространства).
К сожалению, если исходить из моих уточнений к исходной формулировке Вашей задачи, мне в голову не приходит ни одного решения (алгоритма), кроме простого перебора: O(N^3) на поиск треугольников + O(N^2) на поиск групп точек по треугольникам O(N) на поиск наиболее подходящих скоплений.
16 млн ^ 3 — выглядит, как некоторая бесконечность :)
К сожалению, если исходить из моих уточнений к исходной формулировке Вашей задачи, мне в голову не приходит ни одного решения (алгоритма), кроме простого перебора: O(N^3) на поиск треугольников + O(N^2) на поиск групп точек по треугольникам O(N) на поиск наиболее подходящих скоплений.
16 млн ^ 3 — выглядит, как некоторая бесконечность :)
А найти N наиболее сгущённых точек, отсортировав их по степени сгущения, или все, уровень сгущения которых не меньше заданного этот алгоритм может помочь?
Sign up to leave a comment.
Еще раз о поиске наибольшего сгущения в облаке точек