层次结构

层次聚类算法。

属性 dendrogram_ 给出树状图。

树状图是一个大小为 \((n-1) \times 4\) 的数组，表示节点的连续合并。每一行给出两个合并的节点、它们的距离以及合并后的聚类的大小。任何新的节点（合并的结果）都采用第一个可用的索引（例如，第一次合并对应于节点 \(n\)）。

巴黎

class sknetwork.hierarchy.Paris(weights: str = 'degree', reorder: bool = True)

基于节点相似度进行贪婪合并的凝聚聚类算法。

节点 \(i,j\) 之间的相似度为 \(\dfrac{A_{ij}}{w_i w_j}\)，其中

• \(A_{ij}\) 是边 \(i,j\) 的权重，

• \(w_i, w_j\) 是节点 \(i,j\) 的权重。

如果输入矩阵 \(B\) 是二部矩阵（即矩形），则该算法将应用于相应的邻接矩阵 \(A = \begin{bmatrix} 0 & B \\ B^T & 0 \end{bmatrix}\)

参数：

• weights (str) – 节点的权重。 'degree'（默认）或 'uniform'。

• reorder (bool) – 如果为 True（默认），则按高度非递减顺序重新排序树状图。

变量：

• dendrogram (np.ndarray) – 图的树状图。

• dendrogram_row (np.ndarray) – 二部图的行树状图。

• dendrogram_col (np.ndarray) – 二部图的列树状图。

• dendrogram_full (np.ndarray) – 二部图的行和列树状图，按此顺序索引。

示例

>>> from sknetwork.hierarchy import Paris
>>> from sknetwork.data import house
>>> paris = Paris()
>>> adjacency = house()
>>> dendrogram = paris.fit_predict(adjacency)
>>> np.round(dendrogram, 2)
array([[3.        , 2.        , 0.17      , 2.        ],
       [1.        , 0.        , 0.25      , 2.        ],
       [6.        , 4.        , 0.31      , 3.        ],
       [7.        , 5.        , 0.67      , 5.        ]])

备注

树状图的每一行 = \(i, j\)、距离、聚类 \(i + j\) 的大小。

另请参阅

scipy.cluster.hierarchy.linkage

参考资料

T. Bonald、B. Charpentier、A. Galland、A. Hollocou (2018)。使用节点对采样的层次图聚类。 图挖掘和学习研讨会。

fit(input_matrix: csr_matrix | ndarray, force_bipartite: bool = False) → Paris

使用最近邻链进行凝聚聚类。

参数：

• input_matrix (sparse.csr_matrix, np.ndarray) – 图的邻接矩阵或二部矩阵。

• force_bipartite – 如果为 True，则强制将输入矩阵视为二部矩阵。

返回：

self

返回类型：

巴黎

fit_predict(*args, **kwargs) → ndarray

将算法拟合到数据并返回树状图。与 fit 方法具有相同的参数。

返回：

dendrogram – 树状图。

返回类型：

np.ndarray

fit_transform(*args, **kwargs) → ndarray

将算法拟合到数据并返回树状图。它是 fit_predict 的别名。与 fit 方法具有相同的参数。

返回：

dendrogram – 树状图。

返回类型：

np.ndarray

get_params()

以字典形式获取参数。

返回：

params – 算法的参数。

返回类型：

dict

predict(columns: bool = False) → ndarray

返回算法预测的树状图。

参数：

columns (bool) – 如果为 True，则返回对列的预测。

返回：

dendrogram – 树状图。

返回类型：

np.ndarray

set_params(params: dict) → Algorithm

设置算法的参数。

参数：

params (dict) – 算法的参数。

返回：

self

返回类型：

Algorithm

transform() → ndarray

返回算法预测的树状图。

返回：

dendrogram – 树状图。

返回类型：

np.ndarray

Louvain

class sknetwork.hierarchy.LouvainHierarchy(resolution: float = 1, tol_optimization: float = 0.001, tol_aggregation: float = 0.001, shuffle_nodes: bool = False, random_state: RandomState | int | None = None, verbose: bool = False)

通过 Louvain（自下而上）进行层次聚类。

每个级别对应于 Louvain 算法的聚合步骤。

参数：

• resolution (float) – 分辨率参数。

• tol_optimization (float) – 进入新的优化循环的最小目标函数增加量。

• tol_aggregation (float) – 进入新的聚合循环的最小目标函数增加量。

• shuffle_nodes (bool) – 如果为 True，则在优化之前对节点进行混洗。

• random_state (int) – 随机数生成器或随机种子。如果为 None，则使用 numpy.random。

• verbose (bool) – 详细模式。

变量：

• dendrogram (np.ndarray) – 图的树状图。

• dendrogram_row (np.ndarray) – 二部图的行树状图。

• dendrogram_col (np.ndarray) – 二部图的列树状图。

• dendrogram_full (np.ndarray) – 二部图的行和列树状图，按此顺序索引。

示例

>>> from sknetwork.hierarchy import LouvainHierarchy
>>> from sknetwork.data import house
>>> louvain = LouvainHierarchy()
>>> adjacency = house()
>>> louvain.fit_predict(adjacency)
array([[3., 2., 1., 2.],
       [4., 1., 1., 2.],
       [6., 0., 1., 3.],
       [5., 7., 2., 5.]])

备注

树状图的每一行 = 合并节点、距离、聚类的大小。

另请参阅

scipy.cluster.hierarchy.dendrogram, sknetwork.clustering.Louvain

fit(input_matrix: csr_matrix | ndarray, force_bipartite: bool = False) → LouvainHierarchy

将算法拟合到数据。

参数：

• input_matrix (sparse.csr_matrix, np.ndarray) – 图的邻接矩阵或二部矩阵。

• force_bipartite – 如果为 True，则强制将输入矩阵视为二部矩阵。

返回：

self

返回类型：

LouvainHierarchy

fit_predict(*args, **kwargs) → ndarray

将算法拟合到数据并返回树状图。与 fit 方法具有相同的参数。

返回：

dendrogram – 树状图。

返回类型：

np.ndarray

fit_transform(*args, **kwargs) → ndarray

将算法拟合到数据并返回树状图。它是 fit_predict 的别名。与 fit 方法具有相同的参数。

返回：

dendrogram – 树状图。

返回类型：

np.ndarray

get_params()

以字典形式获取参数。

返回：

params – 算法的参数。

返回类型：

dict

predict(columns: bool = False) → ndarray

返回算法预测的树状图。

参数：

columns (bool) – 如果为 True，则返回对列的预测。

返回：

dendrogram – 树状图。

返回类型：

np.ndarray

set_params(params: dict) → Algorithm

设置算法的参数。

参数：

params (dict) – 算法的参数。

返回：

self

返回类型：

Algorithm

transform() → ndarray

返回算法预测的树状图。

返回：

dendrogram – 树状图。

返回类型：

np.ndarray

class sknetwork.hierarchy.LouvainIteration(depth: int = 3, resolution: float = 1, tol_optimization: float = 0.001, tol_aggregation: float = 0.001, n_aggregations: int = -1, shuffle_nodes: bool = False, random_state: RandomState | int | None = None, verbose: bool = False)

通过连续的 Louvain 实例进行分层聚类（自上而下）。

参数：

• depth (int) – 树的深度。负值被解释为没有限制（返回最大深度的树）。

• resolution (float) – 分辨率参数。

• tol_optimization (float) – 进入新的优化循环的最小目标函数增加量。

• tol_aggregation (float) – 进入新的聚合循环的最小目标函数增加量。

• n_aggregations (int) – 聚合的最大数量。负值被解释为没有限制。

• shuffle_nodes (bool) – 如果为 True，则在优化之前对节点进行混洗。

• random_state (int) – 随机数生成器或随机种子。如果为 None，则使用 numpy.random。

• verbose (bool) – 详细模式。

变量：

• dendrogram (np.ndarray) – 图的树状图。

• dendrogram_row (np.ndarray) – 二部图的行树状图。

• dendrogram_col (np.ndarray) – 二部图的列树状图。

• dendrogram_full (np.ndarray) – 二部图的行和列树状图，按此顺序索引。

示例

>>> from sknetwork.hierarchy import LouvainIteration
>>> from sknetwork.data import house
>>> louvain = LouvainIteration()
>>> adjacency = house()
>>> louvain.fit_predict(adjacency)
array([[3., 2., 1., 2.],
       [4., 1., 1., 2.],
       [6., 0., 1., 3.],
       [5., 7., 2., 5.]])

备注

树状图的每一行 = 合并节点、距离、聚类的大小。

另请参阅

scipy.cluster.hierarchy.dendrogram, sknetwork.clustering.Louvain

fit(input_matrix: csr_matrix | ndarray, force_bipartite: bool = False) → LouvainIteration

将算法拟合到数据。

参数：

• input_matrix (sparse.csr_matrix, np.ndarray) – 图的邻接矩阵或二部矩阵。

• force_bipartite – 如果为 True，则强制将输入矩阵视为二部矩阵。

返回：

self

返回类型：

LouvainIteration

fit_predict(*args, **kwargs) → ndarray

将算法拟合到数据并返回树状图。与 fit 方法具有相同的参数。

返回：

dendrogram – 树状图。

返回类型：

np.ndarray

fit_transform(*args, **kwargs) → ndarray

将算法拟合到数据并返回树状图。它是 fit_predict 的别名。与 fit 方法具有相同的参数。

返回：

dendrogram – 树状图。

返回类型：

np.ndarray

get_params()

以字典形式获取参数。

返回：

params – 算法的参数。

返回类型：

dict

predict(columns: bool = False) → ndarray

返回算法预测的树状图。

参数：

columns (bool) – 如果为 True，则返回对列的预测。

返回：

dendrogram – 树状图。

返回类型：

np.ndarray

set_params(params: dict) → Algorithm

设置算法的参数。

参数：

params (dict) – 算法的参数。

返回：

self

返回类型：

Algorithm

transform() → ndarray

返回算法预测的树状图。

返回：

dendrogram – 树状图。

返回类型：

np.ndarray

指标

sknetwork.hierarchy.dasgupta_cost(adjacency: csr_matrix, dendrogram: ndarray, weights: str = 'uniform', normalized: bool = False) → float

Dasgupta 的层次结构成本。

由随机边采样（层次结构中两个节点的最近祖先）引起的集群的预期大小（权重 = 'uniform'）或预期体积（权重 = 'degree'）。

参数：

• adjacency – 图的邻接矩阵。

• dendrogram – 树状图。

• weights – 节点的权重。'degree' 或 'uniform'（默认）。

• normalized – 如果为 True，则为标准化成本（介于 0 和 1 之间）。

返回：

cost – 成本。

返回类型：

float

示例

>>> from sknetwork.hierarchy import dasgupta_score, Paris
>>> from sknetwork.data import house
>>> paris = Paris()
>>> adjacency = house()
>>> dendrogram = paris.fit_transform(adjacency)
>>> cost = dasgupta_cost(adjacency, dendrogram)
>>> np.round(cost, 2)
3.33

参考资料

Dasgupta, S. (2016)。基于相似度的层次聚类的成本函数。ACM 理论计算研讨会论文集。

sknetwork.hierarchy.dasgupta_score(adjacency: csr_matrix, dendrogram: ndarray, weights: str = 'uniform') → float

层次结构的 Dasgupta 得分（质量度量，介于 0 和 1 之间）。

定义为 1 - 归一化的 Dasgupta 成本。

参数：

• adjacency – 图的邻接矩阵。

• dendrogram – 树状图。

• weights – 节点的权重。'degree' 或 'uniform'（默认）。

返回：

score – 分数。

返回类型：

float

示例

>>> from sknetwork.hierarchy import dasgupta_score, Paris
>>> from sknetwork.data import house
>>> paris = Paris()
>>> adjacency = house()
>>> dendrogram = paris.fit_transform(adjacency)
>>> score = dasgupta_score(adjacency, dendrogram)
>>> np.round(score, 2)
0.33

参考资料

Dasgupta, S. (2016)。基于相似度的层次聚类的成本函数。ACM 理论计算研讨会论文集。

sknetwork.hierarchy.tree_sampling_divergence(adjacency: csr_matrix, dendrogram: ndarray, weights: str = 'degree', normalized: bool = True) → float

层次结构的树采样差异（质量度量）。

参数：

• adjacency – 图的邻接矩阵。

• dendrogram – 树状图。

• weights – 节点的权重。 'degree'（默认）或 'uniform'。

• normalized – 如果 True，则为归一化得分（介于 0 和 1 之间）。

返回：

score – 分数。

返回类型：

float

示例

>>> from sknetwork.hierarchy import tree_sampling_divergence, Paris
>>> from sknetwork.data import house
>>> paris = Paris()
>>> adjacency = house()
>>> dendrogram = paris.fit_transform(adjacency)
>>> score = tree_sampling_divergence(adjacency, dendrogram)
>>> np.round(score, 2)
0.05

参考资料

Charpentier, B. & Bonald, T. (2019). 树采样差异：一种用于层次图聚类的信息论度量。 IJCAI 论文集。

切分

sknetwork.hierarchy.cut_straight(dendrogram: ndarray, n_clusters: int | None = None, threshold: None | float = None, sort_clusters: bool = True, return_dendrogram: bool = False) → ndarray | Tuple[ndarray, ndarray]

切分树状图并返回相应的聚类。

参数：

• dendrogram (np.ndarray) – 树状图。

• n_clusters (int) – 聚类数量（可选）。如果树状图中存在相等的高度，聚类数量可能会大于 n_clusters。

• threshold (float) – 高度的阈值（可选）。如果 n_clusters 和 threshold 都为 None，则 n_clusters 设置为 2。

• sort_clusters (bool) – 如果 True，则按聚类大小递减顺序对聚类进行排序。

• return_dendrogram (bool) – 如果 True，则返回从聚类到根的树状图。

返回：

• labels (np.ndarray) – 每个节点的聚类。

• dendrogram_aggregate (np.ndarray) – 从聚类开始的树状图（叶节点 = 聚类）。

示例

>>> from sknetwork.hierarchy import cut_straight
>>> dendrogram = np.array([[0, 1, 0, 2], [2, 3, 1, 3]])
>>> cut_straight(dendrogram)
array([0, 0, 1])

sknetwork.hierarchy.cut_balanced(dendrogram: ndarray, max_cluster_size: int = 20, sort_clusters: bool = True, return_dendrogram: bool = False) → ndarray | Tuple[ndarray, ndarray]

使用对聚类大小的约束切分树状图并返回相应的聚类。

参数：

• dendrogram (np.ndarray) – 树状图

• max_cluster_size (int) – 每个聚类的最大大小。

• sort_clusters (bool) – 如果 True，则按聚类大小递减顺序对标签进行排序。

• return_dendrogram (bool) – 如果 True，则返回从聚类到根的树状图。

返回：

• labels (np.ndarray) – 每个节点的标签。

• dendrogram_aggregate (np.ndarray) – 从聚类开始的树状图（叶节点 = 聚类）。

示例

>>> from sknetwork.hierarchy import cut_balanced
>>> dendrogram = np.array([[0, 1, 0, 2], [2, 3, 1, 3]])
>>> cut_balanced(dendrogram, 2)
array([0, 0, 1])

树状图

sknetwork.hierarchy.aggregate_dendrogram(dendrogram: ndarray, n_clusters: int = 2, return_counts: bool = False) → ndarray | Tuple[ndarray, ndarray]

聚合树状图以获得一定数量的叶节点。输出树状图中的叶节点对应于输入树状图中的子树。

参数：

• dendrogram (np.ndarray) – 要聚合的输入。

• n_clusters (int) – 要保留的聚类（或叶节点）数量。

• return_counts (bool) – 如果 True，则返回一个计数数组，对应于合并子树的大小。计数的总和等于输入树状图中的样本数量。

返回：

• new_dendrogram (np.ndarray) – 聚合的树状图。节点从 0 重新索引。

• counts (np.ndarray) – 对应于 new_dendrogram 中每个叶节点的子树大小。

sknetwork.hierarchy.reorder_dendrogram(dendrogram: ndarray) → ndarray

按高度非递减顺序对树状图进行重新排序。