Рассчитайте частоту похожих векторов

Question

У меня есть список N 2-х векторов, и я хочу выяснить, какие из них k (= eg3) появляются чаще всего.

Векторы, разность которых (например, расстояние или которая была бы наилучшей «мерой подобия»?) Меньше порогового значения th, должны учитываться как одинаковые. Все сходные векторы могут быть агрегированы по их среднему значению.

Таким образом, моим желаемым выводом будет словарь k векторов с соответствующей частотой f.

Минимальный пример:

k = 1
input = [[1.0,2.0],[1.1,2.1],[3.0,4.0]]
output = {[1.05,2.05]:2}

Какой будет наиболее эффективный алгоритм для вычисления этого (неплохо было бы использовать псевдокод или python).

Редактировать: Векторы, которые идентичны, но с противоположными направлениями (например, (1, -1) и (-1,1)) следует считать одинаковыми;

Answer 1

Немного поздно, но я опубликую свое окончательное решение как ответ, может быть, кто-то заинтересован:

import json

def get_most_freq_k(arr,k):  
    d = dict() 
    # Traverse through array elements  
    # and count frequencies 
    for i in range(len(arr)): 
        key = json.dumps(arr[i])
        if key in d.keys(): 
            d[key] += 1
        else: 
            d[key] = 1          
    # return dict with the k most frequent elements
    mostFreqKeys = sorted(d, key=d.get, reverse=True)[:k]
    return {k: d[k] for k in set(mostFreqKeys)}

Answer 2

Рассчитайте меру сходства для каждого вектора (т.е. расстояние d=sqrt(x^2+y^2)) и затем отсортируйте список векторов по списку мер сходства. Сортировка списка по другому списку описана в Сортировка списка по значениям из другого списка?

Если вы не хотите сортировать по https://www.geeksforgeeks.org/count-frequencies-elements-array-o1-extra-space-time/, это O (n) алгоритм подсчета частоты или использование хеширования https://www.geeksforgeeks.org/counting-frequencies-of-array-elements/ (также O (n) сложность времени)