Подходящие метрики сходства для нескольких наборов 2D-координат

У меня есть коллекция наборов 2D-координат (в масштабе 100–500 000 точек в каждом наборе), и я ищу наиболее эффективный способ измерить сходство одного набора с другим. Я знаю обычные: косинус, Жаккард/Танимото и т. д. Однако я надеюсь на некоторые предложения по любым быстрым/эффективным для измерения сходства, особенно те, которые могут группироваться по сходству.

Редактировать 1: изображение показывает, что мне нужно сделать. Мне нужно сгруппировать все красные, синие и зеленые цвета по их форме/ориентации и т.д.

замещающий текст http://img402.imageshack.us/img402/8121/curves.png< /а>


coordinates algorithm 2d similarity
person Mikos    schedule 20.01.2010    source источник
comment
Не могли бы вы дать дальнейшее определение сходства? Насколько я понимаю, у вас есть n наборов из m точек (где m порядка 100 тыс.). Какие критерии вы бы использовали, чтобы сказать, что любые 2 набора подобны? Будет ли это то, что они имеют большое подмножество идентичных точек (т. е. одинаковые координаты x, y) или наборы координат в двух наборах тесно перекрываются (т. е. разные координаты, описывающие геометрически похожие двумерные объекты).   -  person awesomo    schedule 20.01.2010
comment
Спасибо, я больше смотрел на последние, т.е. они описывают похожие 2D-объекты. Позвольте мне немного объяснить мой вариант использования: у меня есть несколько быстро меняющихся диаграмм рассеяния, и я хотел бы сгруппировать их по сходству. ГТН и ТИА   -  person Mikos    schedule 23.01.2010
comment
Поможет ли кросс-корреляция? Однако я смущен, как сделать его неизменным по размеру. Можно ли нормализовать по количеству координат? Любые идеи, ребята?   -  person Mikos    schedule 26.01.2010
comment
Почему зеленые (или красные) похожи? Они являются зеркальным отображением друг друга. Учет этого добавит сложности любому алгоритму, который вы выберете.   -  person Sparr    schedule 29.01.2010

Ответы (3)


arrow_upward
0
arrow_downward

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

Один алгоритм, который приходит на ум, состоит в том, чтобы начать с точки, ближайшей к центроиду, и пройти к ближайшим соседям. Сравните смещения этих соседей (от центроида) между сравниваемыми наборами. Продолжайте идти к следующим ближайшим соседям центроида или к ближайшим еще не сравненным соседям тех, которые были сравнены ранее, и отслеживайте совокупную разницу (возможно, среднеквадратичное значение?) между двумя фигурами. Кроме того, на каждом шаге этого процесса вычисляйте смещение вращения, которое приведет две фигуры к максимально близкому выравниванию [и влияет ли на это зеркальное отображение?]. Когда вы закончите, у вас будет три значения для каждой пары наборов, включая их прямое сходство, их относительное смещение вращения (в основном полезно, только если они близко совпадают после вращения) и их сходство после вращения.

person Sparr    schedule 29.01.2010
comment
Не совсем то, что я искал, но ваш ответ заставил меня начать в хорошем направлении. - person Mikos; 24.02.2010

arrow_upward
0
arrow_downward

Попробуйте алгоритм К-средних. Он динамически вычисляет центр тяжести каждого кластера, вычисляет расстояние до всех указателей и связывает их с ближайшим кластером.

person Boolean    schedule 20.01.2010
comment
Спасибо, к сожалению, k-средние не подходят, поскольку n заранее неизвестно. - person Mikos; 23.01.2010

arrow_upward
0
arrow_downward

Поскольку ваша кластеризация основана на метрике близости к форме, возможно, вам нужна какая-то форма маркировки связанных компонентов. UNION-FIND может дать вам быстрый базовый набор примитивов.

Для объединения только начните каждую точку в другом наборе и объедините их, если они соответствуют какому-либо критерию близости, на который влияет локальная коллинеарность, поскольку это кажется вам важным. Затем продолжайте слияние, пока не пройдете какое-то пороговое условие, определяющее сложность вашего слияния. Если вы относитесь к этому как к наращиванию строк (соединяйте элементы только на концах), то некоторые структуры данных упрощаются. Являются ли все ваши кластеры открытыми линиями и кривыми? Никаких замкнутых кривых, как круги?

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

person Liudvikas Bukys    schedule 05.02.2010