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

Question

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

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

альтернативный текст http://img402.imageshack.us/img402/8121/curves.png

Answer 1

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

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

Answer 2

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

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

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

Answer 3

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