计算相似向量的频率

Question

我有一个 N 二维向量的列表，我想找出最常出现的 k（=e.g.3）向量。

差异（例如距离，或最佳 "similarity measure"？）小于阈值 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

计算每个向量的相似性度量（即距离d=sqrt(x^2+y^2)），然后对向量列表w.r.t进行排序。相似性度量列表。正在对列表进行排序 w.r.t。 Sorting list based on values from another list?

中描述了另一个列表

如果不想按https://www.geeksforgeeks.org/count-frequencies-elements-array-o1-extra-space-time/ is a O(n) algorithm for frequency counts or use hashing https://www.geeksforgeeks.org/counting-frequencies-of-array-elements/排序（也是O(n)时间复杂度）

Answer 2

有点晚了，但我会 post 我的最终解决方案作为答案，也许有人感兴趣：

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)}

计算相似向量的频率

Calculate Frequency of similar vectors

python

algorithm

search

vector

pseudocode