python - 按范围按浮点值分组

Question

假设我有一个看起来像这样的数据框:

Result
0.001
0.000
-0.001
0.005
0.002
0.003
0.004
0.001
3.400
3.401
3.405
3.402
0.003
0.004
0.001
4.670
-0.001
4.675
4.672
0.003
3.404

我想按某个间隔对值进行分组(比方说从第一个“尚未存在”的值开始±0.005)，所以在这里我将其分组为:

Result GROUP_AVG
0.001  0.003
0.000  0.003
-0.001  0.003
0.005  0.003
0.002  0.003
0.003  0.003
0.004  0.003
0.001  0.003
3.400  3.403
3.401  3.403
3.405  3.403
3.402  3.403
0.003  0.003
0.004  0.003
0.001  0.003
4.670  4.673
-0.001  0.003
4.675  4.673
4.672  4.673
0.003  0.003
3.404  3.403

现在，我这样做效率很低:

1. 检查 row_value 是否在 averages_set["value"] 中的任何项目的 ±0.005 范围内
2. 如果否，则在 averages_set 中创建新实体，其中 "value": row_value, "average": row_value, count: 1
3. 如果是，更新averages_set[i]["average"]=(average * count + row_value)/(count+1)，还有count=count+1
4. 在迭代所有行后，将列添加到基本数据集并根据其到 averages_set[i]["value"] 的距离为每一行更改它，更改行的新列值使用 averages_set[i]["average"] 因为无论如何我都需要平均值才能进行进一步的操作。并且平均值实际上可以被视为离散值，而不会为进一步的操作带来更大的问题。

我以前使用过 pandas.groupby，它对离散值非常有用。有没有办法，例如，基于浮点值分组，考虑到例如与出现的第一个新值相差 ±0.5？它比我的算法效率高得多，而且我可以轻松计算出每个组的平均值(而不仅仅是)。

Answer 1

您的问题很难以最佳方式解决(即找到最少的组数)。如评论中所述，您的方法取决于顺序:[0, 0.006, 0.004] 会产生两组 ([0, 0.005]) 而 [ 0, 0.004, 0.006] 会产生一个 ([0.0033..])。此外，它是一种贪婪的凝聚分组，它切割了许多可能的组，通常包括最优组。

这是一种使用凝聚聚类的方法。对于 n 点，它在 O(n log n) 和 O(n^2) 之间:对于 1K 点大约 61ms，但是 3.2s在我的机器上获得 5K 点。它还需要稍微改变定义:我们用“中心”(边界框的中心)而不是平均质心来表示组。

我们使用 linkage='complete' 链接类型(因此集群的总直径是决定性指标)并将最大距离(该直径)设置为您的“公差”的两倍。

示例

from sklearn.cluster import AgglomerativeClustering

def quantize(df, tolerance=0.005):
    # df: DataFrame with only the column(s) to quantize
    model = AgglomerativeClustering(distance_threshold=2 * tolerance, linkage='complete',
                                    n_clusters=None).fit(df)
    df = df.assign(
        group=model.labels_,
        center=df.groupby(model.labels_).transform(lambda v: (v.max() + v.min()) / 2),
    )
    return df

在您的数据上，它需要 4.4 毫秒并产生以下 df:

>>> quantize(df[['Result']], tolerance=0.005)
    Result  group  center
0    0.001      0  0.0020
1    0.000      0  0.0020
2   -0.001      0  0.0020
3    0.005      0  0.0020
4    0.002      0  0.0020
5    0.003      0  0.0020
6    0.004      0  0.0020
7    0.001      0  0.0020
8    3.400      2  3.4025
9    3.401      2  3.4025
10   3.405      2  3.4025
11   3.402      2  3.4025
12   0.003      0  0.0020
13   0.004      0  0.0020
14   0.001      0  0.0020
15   4.670      1  4.6725
16  -0.001      0  0.0020
17   4.675      1  4.6725
18   4.672      1  4.6725
19   0.003      0  0.0020
20   3.404      2  3.4025

可视化

您可以使用 scipy.cluster.hierarchy.dendrogram 可视化相应的树状图:

from scipy.cluster.hierarchy import dendrogram, linkage
from scipy.spatial.distance import pdist

Z = linkage(pdist(df[['Result']]), 'complete')
dn = dendrogram(Z)
plt.axhline(2 * tolerance, c='k')
plt.ylim(0, 2.1 * tolerance)

2 * tolerance 指示的阈值以下有三个簇。

速度

linkage='complete' 的层次聚类一般是O(n^2)。但在某些情况下，由于 distance_threshold，可能会节省一些时间。要查看此效果，我们使用 perfplot并探索 df 的性能与大小:

import perfplot

tolerance = 0.005
base2_max = int(np.round(np.log2(20_000)))
o = perfplot.bench(
    setup=lambda n: pd.DataFrame(np.random.uniform(0, tolerance * n, size=n), columns=['Result']),
    kernels=[quantize],
    n_range=[2 ** k for k in range(8, base2_max + 1)],
)

时间在 n log(n) 以上，但显然不完全是 n^2:

k_ = o.n_range
t_ = o.timings_s[0]

fig, axes = plt.subplots(ncols=3, figsize=(10, 3), tight_layout=True)
axes = iter(axes)
ax = next(axes)
ax.loglog(k_, t_)
ax.set_title('time')
ax.set_xlabel('n')

ax = next(axes)
ax.semilogx(k_, t_ / (np.log(k_) * k_))
ax.set_title('relative to $\mathcal{O}(n\log{}n)$')
ax.set_xlabel('n')
ax.axes.get_yaxis().set_visible(False)

ax = next(axes)
ax.semilogx(k_, t_ / k_ ** 2)
ax.set_title('relative to $\mathcal{O}(n^2)$')
ax.set_xlabel('n')
ax.axes.get_yaxis().set_visible(False)