python - 大量列表列表的快速比较

Question

列表的比较列表之前已经发布过，但是我正在使用的 python 环境不能完全集成 numpy 中的所有方法和类。我也不能导入 Pandas 。

我正在尝试比较一个大列表中的列表，并得出大约 8-10 个列表，这些列表与大列表中的所有其他列表相近。

如果我在大列表中有 <50 个列表，我所采用的方法就可以正常工作。但是，我正在尝试比较至少 20k 个列表，最好是 100 万个以上。我目前正在研究 itertools。在不使用 numpy 或 pandas 的情况下，对于大型数据集最快、最有效的方法是什么？

我可以使用 numpy 中的一些方法和类，但不是全部。例如，numpy.allclose 和 numpy.all 不能正常工作，这是因为我工作的环境。

    global rel_tol, avg_lists
    rel_tol=.1 
    avg_lists=[]
    #compare the lists in the big list and output ~8-10 lists that approximate the all the lists in the big list
    for j in range(len(big_list)):

        for k in range(len(big_list)):

            array1=np.array(big_list[j])
            array2=np.array(big_list[k])
            if j!=k:
            #if j is not k:  

                diff=np.subtract(array1, array2)
                abs_diff=np.absolute(diff)

                #cannot use numpy.allclose
                #if the deviation for the largest value in the array is < 10%
                if np.amax(abs_diff)<= rel_tol and big_list[k] not in avg_lists:

                    cntr+=1
                    avg_lists.append(big_list[k])

Answer 1

从根本上说，您的目标似乎是聚类操作(即通过 K < N 聚类中心表示一组 N 个点)。我建议 K-Means clustering方法，您增加 K 直到集群的大小低于您想要的阈值。

我不确定您所说的“无法完全集成 numpy 中的所有方法和类”是什么意思，但是如果 scikit-learn 可用，您可以使用它的 K-means estimator .如果这不可能，K-means 算法的一个简单版本是 relatively easy to code from scratch ，你可能会用到它。

这是使用 scikit-learn 的 k-means 方法:

# 100 lists of length 10 = 100 points in 10 dimensions
from random import random
big_list = [[random() for i in range(10)] for j in range(100)]

# compute eight representative points
from sklearn.cluster import KMeans
model = KMeans(n_clusters=8)
model.fit(big_list)
centers = model.cluster_centers_
print(centers.shape)  # (8, 10)

# this is the sum of square distances of your points to the cluster centers
# you can adjust n_clusters until this is small enough for your purposes.
sum_sq_dists = model.inertia_

从这里您可以例如找到每个簇中最接近其中心的点并将其视为平均值。如果没有您要解决的问题的更多细节，则很难确定。但是像这样的聚类方法将是解决您在问题中提到的问题的最有效方法。