Превод на проблема с групирането на езика на теорията на графите

Имам правоъгълна равнинна мрежа, като на всяка клетка е присвоено някакво цяло число. Търся алгоритъм за идентифициране на клъстери от 3 до 6 съседни клетки с по-високо от средното тегло. Тези петна трябва да имат приблизително кръгла форма.

За моя случай средното тегло на клетките, които не съдържат клъстер, е около 6, а това за клетките, съдържащи клъстер, е около 6+4, т.е. има „тегло на фона“ някъде около 6. Теглата се колебаят с Поасонова статистика.

За малки фонови алчни или заредени алгоритми се представят доста добре, но това се разваля, ако моите клъстерни клетки имат тегла, близки до колебания във фонов режим, т.е. те ще са склонни да намерят клъстер, въпреки че няма нищо. Освен това не мога да направя търсене с груба сила, преминавайки през всички възможни настройки, защото мрежата ми е голяма (нещо като 1000x1000) и смятам да правя това много често (10^9 пъти). Имам впечатлението, че може да има начини да се справим с това в теорията на графите. Чух за vertex-covers и cliques, но не съм сигурен как най-добре да преведа проблема си на техния език. Знам, че теорията на графите може да има проблеми със статистическото естество на входа, но ще ми е интересно да видя какви алгоритми могат да намерят оттам, дори ако не могат да идентифицират всеки клъстер.

Ето пример за изрязване: рамкираният регион има средно 10 записа на клетка, всички останали клетки имат средно 6. Разбира се, решетката се простира още повече.

| 8|  8|  2|  8|  2|  3| 
| 6|  4|  3|  6|  4|  4| 
        ===========
| 8|  3||13|  7| 11|| 7|
|10|  4||10| 12|  3|| 2|
| 5|  6||11|  6|  8||12|
        ===========
| 9|  4|  0|  2|  8|  7|

graph cluster-analysis
person Benjamin Bannier    schedule 17.04.2010    source източник
comment
Звучи като отдавна решен проблем в компютърното зрение. Например, опитвайки се да открия тъмни звезди на тъмен бг. Въпреки че астрономите може да имат много ресурси, те също не биха имали нищо против да го направят бързо. Подозирам, че проблемът ви е решен преди. Между другото, бих се придържал към матрична структура на данните. С него се работи по-бързо и има смисъл. Какво се опитваш да направиш?   -  person Hamish Grubijan    schedule 17.04.2010
comment
1000х1000 не е толкова много. Бихте могли: A) да използвате добра библиотека с бързи матрици. SciPy B) изчисляване на средната яркост. C) Повторете всяка клетка отляво надясно, след това отгоре надолу. Сега приемете квадратна форма 3x3. Изчислете средната плътност. Изглежда средно - продължавай. Изглежда по-високо от нормалното? Тогава проучете района. Проблемът може лесно да възникне, ако имате големи региони (помислете за облаци в небето до тъмни звезди). Тези облаци могат да объркат всичко. Човек трябва да направи предположения за това как изглеждат данните.   -  person Hamish Grubijan    schedule 17.04.2010
comment

Възможно ли е да се извика Server.Execute с .NET .aspx страница от класически ASP? Моите тестове досега показват, че това не работи, но все още съм донякъде убеден, че има начин.

  -  person Benjamin Bannier    schedule 17.04.2010
comment
Смятам да направя това милиард пъти.   -  person Benjamin Bannier    schedule 17.04.2010
comment
@honk, това дори не е добре дефиниран проблем. Спецификацията ви е слаба. По-специално: какво е по-високо от средното? 1 std (каквото и да означава това) разстояние? Почти всичко на теория е NP-пълен проблем. Практиците като тези в областта на компютърното зрение просто приемат реалността и се справят с нея по най-добрия начин, по който могат. Какво планирате да направите 1 милиард пъти? Трябва да обработите 1B изображения? Дайте ни предистория за това, което се опитвате да направите. Обработка на данни в реално време? Между другото вълничките може да са полезни, но не ги разбирам наистина.   -  person Hamish Grubijan    schedule 17.04.2010
comment
Търся различен начин за групиране на кули в калориметър, вижте напр. scholar.google.com/   -  person Benjamin Bannier    schedule 17.04.2010
comment
Е, вярвам, че теорията на графите е грешна посока. Преобразуването на тази матрица в графика едва ли ще ви купи нещо. Върховете ще имат същото тегло като клетките, но теглото на ръбовете е безсмислено. Освен това намирането на съсед е достатъчно лесно с обикновена матрица - просто погледнете директно Юг(Ю) Ю, Север(С), И, З, ЮИ, ЮЗ, СИ, СЗ. Вярвам, че този проблем е статистически по природа (харесва ви или не), например защото инструментите, които записват данните, са несъвършени; винаги има шум. Детерминираните алгоритми не се прилагат тук. Капакът на комплекта и клика са твърде теоретични за това.   -  person Hamish Grubijan    schedule 17.04.2010
comment
Това определено е кандидат за награда (след 2 дни).   -  person Hamish Grubijan    schedule 17.04.2010
comment
@Hamish Четете твърде много във въпроса ми: Не очаквам решение от никого, моля за превод от мрежа с тегла, преведени на възли и ръбове и тегла   -  person Benjamin Bannier    schedule 18.04.2010

Отговори (4)


arrow_upward
1
arrow_downward

За решения на теорията на графите има няколко изречения в wikipedia, но вие сте вероятно най-добрата публикация в MathOverflow. Този въпрос също може да бъде полезен.

Традиционният метод (и вероятно най-добрият предвид повсеместното му разпространение) в компютрите за решаване на тези проблеми е растерният анализ - добре познат в света на ГИС и дистанционното наблюдение, така че има редица инструменти, които осигуряват реализации. Ключовите думи, които да използвате, за да намерите тази, която е най-подходяща за вашия проблем, биха били растер, най-близък съсед, повторна дискретизация и клъстериране. Библиотеката GDAL често е основа за други инструменти.

напр. http://clusterville.org/spatialtools/index.html

Можете да опитате да проверите библиотеката и изходния код на GDAL, за да видите дали можете да го използвате във вашата ситуация или да видите как е внедрен.

За проверка за кръгли форми можете да конвертирате останалите стойности в многоъгълници и да проверите получената функция

http://www.gdal.org/gdal_polygonize.html

person geographika    schedule 17.04.2010
comment
Благодаря за линковете geographica. Тъй като сигналът ми е много слаб, не бих искал да отхвърля фона (това така или иначе отваря друг набор от проблеми с колебанията). А за формата, не ме интересува, просто искам да намеря петна. В крайна сметка тези идеи все пак ще (трябва) да вървят по линията на алчни или заредени алгоритми, за които е известно, че имат проблеми тук. Затова търся различни подходи. - person Benjamin Bannier; 17.04.2010
comment
Благодаря отново за насоките. Но както писах, вече съм наясно с тези инструменти и търся напълно различна посока, за да атакувам това (предполагам най-вече да не свиквам с ограниченията на мисленето в техните термини). Предполагам, че въпросът е просто зле формулиран или му липсва фокус. - person Benjamin Bannier; 21.04.2010

arrow_upward
0
arrow_downward

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

A[i,j] = Сума[Сума[p[u,v], {u, 0, i}, {v, 0, j}]];

Тогава средната яркост на правоъгълна (a,b), (c,d) област е

(A[c,d] - (A[c,b] + A[a,d]) + A[a,b])/((c-a)(d-b))

Overflow вероятно не е ваш приятел, ако имате големи числа в клетките си.

person Justin    schedule 12.05.2010
comment
Бихте ли обяснили как това може да бъде полезно за идентифициране на петното? Проблемът наистина е, че сигналът е много близо до фона. - person Benjamin Bannier; 13.05.2010
comment
Вместо да изчислявате средната стойност в k околност на пиксел (което изисква k*k достъпа до паметта и добавяния), можете да използвате 4 достъпа до памет и 4 добавяния. - person Justin; 13.05.2010
comment
Този тип неща може да работят добре, ако сте започнали с по-големи региони на изображението и сте се опитали рекурсивно да намерите области с подобно съотношение сигнал/шум, след което приложите вашия филтър за осредняване на площта. - person Justin; 14.05.2010

arrow_upward
0
arrow_downward

Използване на алгоритъма за намиране на съюз за клъстериране? Много е бързо.

Предполагам, че графиката ще бъде резултат от разглеждането на всяка двойка свързани съседни клетки с висока стойност. Използвайте алгоритъма за намиране на обединение, за да намерите всички клъстери и да приемете всички тези над определен размер, може би и с ограничения на формата (напр. въз основа на средно квадратно разстояние от центъра на клъстера спрямо размера на клъстера). Това е тривиален вариант на алгоритъма за намиране на обединение за събиране на статистически данни, които ще ви трябват за това, докато вървите (броене, сума от x, сума от x^2, сума от y, сума от y^2).

person Paul Harrison    schedule 18.05.2010

arrow_upward
0
arrow_downward

Ако просто търсите начин да преведете проблема си в проблем с графика, ето какво можете да направите.

От всяка точка погледнете всичките си съседи (това може да са 8-те съседни квадрата или 4-те съседни в зависимост от това, което искате). Потърсете съседа с максималната стойност, ако е по-голям от вас, тогава се свържете с този квадрат. ако е по-малък, не правете нищо.

след това ще имате гора или евентуално дърво (въпреки че си представям, че това е малко вероятно). Това е един възможен превод на вашата матрица в графика. Не съм сигурен дали това е най-полезният превод.

person luke    schedule 18.05.2010
comment
Това звучи като много интересен подход. Бих ли създал допълнително дърво за отчитане на колебанията? - person Benjamin Bannier; 18.05.2010
comment
Това, което описахте в отговора си, групира клетки към съседа с най-висок брой. Този брой може да варира, така че комбинацията може да не принадлежи към един и същи клъстер. - person Benjamin Bannier; 19.05.2010