Приветствую!

Блобом (blob) у нас называют сплошную фигуру в картинке. Скажем заполненный квадрат, кольцо и т.д. Фигура может быть произвольной.
Есть некоторая операция называется Blob Analysis результатом которой служит набор характеристик блобов, таких как например диаметр (расстояние между максимально удаленных друг от друга точек), т.н. compactness - насколько фигура близка к окружности и т.д. По этим характеристикам мне необходимо произвести кластеризацию всех блобов. Причем должна быть возможность установить вес для каждой характеристики. Иногда мне нужно произвести кластеризацию по размеру, иногда по "округлости" и т.д.

Какой алгоритм наиболее подойдет в этой ситуации? Есть ли какие готовые либы?

П.С. Есть реализация с алгоритмом K-means. Но она плохо работает. Может она не подходит в данном случае.

Это сообщение отредактировал(а) neutrino - 12.1.2009, 11:19

Достаточно ли точно формализованы эти процедуры с точки зрения строгой математики? Или там были какие-то допущения а-ля "инженерный подход"? 

podval, Блин, k сожалению не я писал и понятия не имею. Вот думаю стоит лi забираться в код или писать что-тo другое? 

Compactness и диаметр - это вполне строгие определения, так что основа вполне нормальная. Скорее всего, проблемы в выборе алгоритма кластеризации. Ну и, какие там еще есть параметры, тоже важно.


Конечно, стОит; даже если в результате будет написано что-то другое. Разве что ты уверен, что старый код писали полные дебилы. Несмотря на понятное нежелание копаться в чужом и, возможно, плохо написанном коде, пересиль себя: там наверняка можно найти какие-то полезные идеи.

Аксиома: Весь чужой код плохо написан.  

Earnest, Гы Вообще-то у меня много опыта по переписыванию кода. Серьезно много. И этот код писал не полный дебил, но он как-бы это сказать... is not engineered well.

Добавлено через 1 минуту и 18 секунд

Угу. Должно быть так.

Выбор зависит от конечной цели - для чего делается этот кластерный анализ. Ведь на основе анализа предполагается делать какой-то вывод?

И так, продолжаем разговор. Нашел некоторое количествo багов в алгоритме кластеризации. И еще вот такая штука: ключевой момент KMeans в начальном разбиении на кластеры. А оно там рандомальное   

Тo есть не случайное расположение центроидов а именно у каждой точки есть одинаковый шанс быть v любом из начальных кластеров. Если грубo говоря, плотность точеk равномерная и их количествo бесконечное, тo все центроиды будут v одной точке - центре (!!!!). Это есмъ БАГ.

И вот чтo я подумал сделать, чтобы "хорошо" изначально поделить на кластеры. Для простоты представим, что есть только две характеристики по которым необходимо классифицировать самплы. Для каждой из характеристик находим гистограмму (или как там ее по-русски), для нахождения распределения. У этой гистограммы нас интересуют точки максимума (не все, но выше некоторого уровня). И так на оси иксов у нас есть такие точки и на оси игреков. Теперь проводим линии соответствующим значениям максимумов и на их пересечении ставим изначальные центроиды. Центроидов может получиться больше чем нужно, тогда после работы алгоритма два ближайших объединяем (сколько нужно). Если центроидов слишком мало, надо уменьшить допустимый уровень для поиска максимумов.

Что думаете? Может что-нибудь получше придумаете?

Сув.

ПыСы. Я там отсеил много характеристик, которые только мешали кластеризации, т.к. были сильно взаимосвязаны с другими характеристиками. Но вот интересное дело. Я заметил, что на наших картинках одинаковые блобы обычно близко расположены друг к другу. Теперь я думаю добавить характеристику и взаимного расположения. Есть некоторые надумки но совсем зеленые. Не могу подкрепить мат аппаратом.

Если я правильно поняла, алгоритм уточняет кластеризации несколько раз, начиная с заданного начального распределения центроидов. Тогда начальный выбор центроидов действительно важен.

Допустим, есть некоторая метрика - расстояние между объектами (или центроидами), с учетом всех характеристик. И есть мера, которую не должен превышать диаметр кластера. Тогда можно попробовать выбрать за первый центроид любой объект, за второй - любой объект, лежащий дальше заданного от первого, за третий - любой, лежащий на заданном расстоянии от первых 2, и т.д.... До нужного начального числа. Можно ограничится и двумя начальными - тогда пусть они будут самыми дальними. Каждый объект, не попавший в существующие кластеры, начинает новый... И т.д. 

Earnest,  Да, это интересный метод. Есть правда недочет в том, что общее количество кластеров может оказаться меньше желаемого и теm самым ухудшить кластеризацию. Этот минус правдив и для моего метода.

Прочитал несколько статей по кластиризации. Инициализация кластеров - действительно больное место алгоритма K-Means и по сути задача такой же сложности как и сам K-Means. 

После некоторых умозаключений придумал следующее. В принципе нам необходимо найти максимумы поверхности (для кластеризации двух характеристик) построенной из гаусианов. Так давайте попробуем построить эту поверхность. Каждая точка пусть поднимет некоторую область вокруг нее. Причем реально поднимать именно маленькие гаусианчики, скажем с дисторсией в 0.001 (и средним значением в самой точке) для поля 1х1. Таким образом мы построим ландшафт или "бугры". Сумма всех гаусианчиков даст нам уравнение поверхности. Можно ее немного аппроксимировать, дабы упростить. В реале у меня несколько тысяч точек и иметь уравнение в несколько тысяч гаусианчиков как минимум неудобно. Далее мы находим К самых больших максимумов поверхности - это и есть начальные центроиды. Сложновато. 

Скажем так, есть ли быстрый и легкий способ аппроксимировать эту поверхность под гаусианы? Если да, то можно будет легко найти максимумы. Ладно, я попробую это реализовать и отпишусь. Советуйте, если есть что. Я постоянно буду сидеть в этой теме. 

Мне кажется, этот подход бесперспективен, т.к. плохо масштабируем. А если параметров больше двух? И с двумя-то слишком сложно получается... 
Я бы скорее вот о чем подумала (похожий метод применяется во всяких пространственных индексах). Опять будем говорить о 2 параметрах, для простоты. Эти параметры образуют плоскость, а объекты - точки на этой плоскости. делим все пространство пополам (по одной из 2 характеристик). Подсчитываем число точек в каждом прямоугольнике. Если число точек в прямоугольнике больше какого-то числа, делим его пополам, но уже по другому параметру. И т.д. - делим прямоугольники (каждый отдельно), до достижения в одном какого-то предельного числа точек. Или нужного числа кластеров - тогда делить начинаем самый большой... Ясно ведь, что разумное число кластеров зависит от числа точек. Я вроде где-то такую формулу видела.  Каждое полученное деление дает затравочный центроид - путем усреднения точек. Ну и дальше уточняем разбиение.

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

Пробовал - результат не очень. Иногда попатает хорошо. Но как правило плохо (сам K-Means не справляется с начальным разбиением).

Немного как бы теории без особых доказательств.

Есть n объектов (далее – точек), для каждого из которых измерено m числовых характеристик (далее – признаков).

Пусть задана некая «метрика» и полное разбиение n точек на K непересекающихся кластеров (кластеризация).
Почему «метрика», а не метрика? Потому что она задана не в пространстве признаков, а на конкретном множестве точек. Поясню разницу. 

Между любыми двумя точками можно вычислить обычное евклидово расстояние. Построим некий путь от точки xi к точке xj и найдем максимальное евклидово расстояние между двумя соседними точками на этом пути. Среди всех возможных путей выберем тот, для которого этот максимум минимален. Вот это значение и примем за расстояние между xi и xj. Легко доказать, что такое расстояние удовлетворяет неравенству треугольника. То есть оно как бы действительно расстояние. Но если мы добавим еще какую-нибудь точку в наше множество (или удалим), то очень может быть, что все посыплется: все расстояния придется пересчитывать.

Будем называть кластеризацию компактной, если для любой точки расстояние до любой точки внутри ее кластера меньше, чем до любой точки из любого чужого кластера. 
Если в заданной «метрике» для данного множества точек существует компактная кластеризация, то у алгоритма K-means есть хорошие шансы ее найти.

Пара простых утверждений.

1. Для любой кластеризации можно задать «метрику», в которой заданная кластеризация  будет компактной.
Утверждение тривиально. Для любых двух точек задаем расстояние равное
0 - точки совпадают
1 – точки принадлежат одному кластеру
2 – точки принадлежат разным кластерам.

2. Для любой «метрики» на конечном множестве из n точек можно сконструировать евклидово пространство, евклидова метрика которого на данном множестве будет в точности совпадать с заданной.
Это утверждение не так тривиально, как предыдущее.
Дело в том, что по заданной «метрике» на n точках можно построить некую неотрицательно определенную симметричную матрицу n*n, спектральное разложение которой и дает искомый базис евклидова пространства, при этом можно учитывать только собственные вектора с ненулевыми собственными числами.
Мало этого. Можно отбросить и часть векторов с положительными собственными числами. В этом случае евклидова метрика уже не будет совпадать с заданной «метрикой». Вопрос в том, насколько сильны искажения. Чем меньше собственное число отбрасываемого вектора, тем меньше искажения. Мы можем отбрасывать вектора в порядке возрастания собственных чисел до тех пор, пока будет сохраняться свойство компактности заданной кластеризации. 
Если заданная «метрика» - это то, что описано в утверждении 1, то результирующее число векторов может получиться великоватым (зависит не только от K, но и от максимального объема кластера). Но это другой вопрос. Из того, что можно делать так, как описано в утверждении 1, не следует, что мы обязаны действовать именно так.

Ладно. Но что со всем этим делать? Ведь мы не умеем сосчитать координаты нового объекта в сконструированном нами пространстве.
Не совсем так. В некоторых случаях можем научиться.

У нас есть два множества векторов в n-мерном евклидовом пространстве.
Во-первых, только что сконструированное нами множество.
Во-вторых, те самые m измеренных на n точках признаков.
Попробуем представить вектора из первого множества в виде линейной комбинации векторов из второго множества.
Опять таки нам не требуется точное представление. Мы можем быть вполне удовлетворены, если возможные искажения не приведут к потере свойства компактности кластеризации.
Получится? Может получиться. В этом случае можно праздновать промежуточную победу.
Не получается? В этом случае так и подмывает сделать заявление о том, что измеренные признаки не содержат в себе достаточно информации о нужной нам кластеризации. Это не совсем верно, так как мы эту информацию использовали только в линейных операциях. Если есть серьезные основания полагать, что нужная информация представлена сильно нелинейно, то можно в исходное множество признаков добавить производные признаки, получаемые из исходных нелинейными преобразованиями (добавлять линейные преобразования типа сумм – совершенно бессмысленно).

Все выше написанное относится к случаю так называемой кластеризации с обучением.
А если мы не знаем желаемой кластеризации на обучающем множестве?
Тут же на ум приходит «магическое» словосочетание «естественная классификация».
Идея как бы в том, то ничего не навязывая, проанализировать имеющееся множество точек на наличие сгущений. И, должен сказать, что не только идея. В свое время было целое цунами всяких работ, посвященных поиску «наилучшего» алгоритма «естественной классификации».

Выражусь грубо: муть все это. Обычно привожу такой, как мне кажется, тривиальный пример.
Рисуем девять точек на равномерной решетке 3х3.
Смотрим и видим: все девять точек самым «естественным» образом представляют один кластер.
Растянем ось X. Совершенно «очевидно», что у нас имеется три кластера в виде трех вертикальных столбиков.
Вернем ось X в исходное состояние и растянем ось Y. Совершенно «очевидно», что у нас имеется три кластера в виде трех горизонтальных линий.
Стоит, так же добавить, что сей пример ни разу ни кого не убедил.

В качестве подведения черты.
Я полагаю, что главное в вопросах кластеризации – формирование пространства признаков. Алгоритм кластеризации тоже имеет значение. Но ...

Дo самой кластеризации я обрабатываю данные определенным образом. Также нормализую их и логарифмирую. Этo специфика моей здачи. Само пространствo признаков выбрано совершенно неверно. Я уже многое поменял и получил гораздo более удовлитворительные результаты. Были несколько признаков линейно зависимых между собой этo приводило к совершенно неверной кластеризации. Нo и саm алгоритм тоже не ахти.