是否存在保序Hierarchical Agglomerative Clustering的Python实现？

存在可以满足需求的实现，你需要的是序列受限型凝聚层次聚类，仅允许相邻的簇或数据点合并，最终聚类结构完全保留原始输入的顺序，不会出现非相邻节点跨顺序合并的情况。

实现方案 #

方案1：scikit-learn 带邻接约束的凝聚聚类 #

通过自定义连通性矩阵，强制仅相邻索引的样本可以被合并，完全锁定原始顺序：

import numpy as np
from sklearn.cluster import AgglomerativeClustering

# X为输入特征矩阵，n_samples为样本总数
n_samples = X.shape[0]
# 构造仅相邻样本连通的邻接矩阵
connectivity = np.zeros((n_samples, n_samples))
for i in range(n_samples - 1):
    connectivity[i, i+1] = 1
    connectivity[i+1, i] = 1

# 初始化聚类模型
hac = AgglomerativeClustering(
    linkage="average", # 可根据需求替换为ward/complete/single
    connectivity=connectivity,
    n_clusters=None,
    distance_threshold=0 # 保留完整聚类树结构
)
hac.fit(X)

方案2：scipy 最优排序聚类树 #

scipy的层次聚类模块支持最优排序参数，会自动重排聚类树叶子节点，尽可能贴合原始输入顺序：

from scipy.cluster.hierarchy import linkage, to_tree

# 生成带最优排序的聚类树
Z = linkage(X, method="average", optimal_ordering=True)
# 转换为树结构用于后续格式化输出
tree = to_tree(Z, rd=False)

输出指定嵌套括号格式 #

通过递归遍历聚类树，即可生成你需要的格式：

def tree_to_nested_str(node, sample_labels=None):
    # 默认生成seg1、seg2格式的标签，可传入自定义标签列表
    if sample_labels is None:
        sample_labels = [f"seg{i+1}" for i in range(X.shape[0])]
    if node.is_leaf():
        return sample_labels[node.id]
    left_str = tree_to_nested_str(node.left, sample_labels)
    right_str = tree_to_nested_str(node.right, sample_labels)
    return f"({left_str}, {right_str})"

# 调用输出
print(tree_to_nested_str(tree))

输出示例：

(((seg1, seg2), (seg3, seg4)), seg5)

内容的提问来源于stack exchange，提问作者Vijaya