階層

階層式聚類演算法。

屬性 dendrogram_ 提供樹狀圖。

樹狀圖是一個大小為 \((n-1) \times 4\) 的陣列，用來表示節點的連續合併。每一列會提供兩個合併的節點、距離和所產生叢集的大小。任何從合併產生出的新節點會取得第一個可用的索引（例如：第一次合併對應到節點 \(n\)）。

Paris

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

傳回型態：

Paris

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)[source]

由 Louvain 階層聚類 (自底向上)。

每個層級對應 Louvain 演算法的聚合步驟。

參數:

resolution (float) – 解析度參數。
tol_optimization (float) – 進入新最佳化通道的目標函數的最低增加值。
tol_aggregation (float) – 進入新聚合通道的目標函數的最低增加值。
shuffle_nodes (布林值) – 如果 True，在最佳化之前洗牌節點。
random_state (整數) – 亂數產生器或亂數種子。如果 None，使用 numpy.random。
verbose (布林值) – 詳盡模式。

變數:

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: 布林值 = 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

預測(欄位: 布林值 = False) → ndarray

傳回由演算法預測的樹狀圖。

參數:: columns (bool) – 如果 True，則傳回欄位預測。
傳回：: dendrogram – 樹狀圖。
傳回型態：: np.ndarray

設定參數(參數: 字典) → 演算法

設定演算法參數。

參數:: params (dict) – 演算法參數。
傳回：: self
傳回型態：: Algorithm

轉換() → 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)[source]

對 Louvaino 的採用執行連續執行後，進行階層群集（自上而下）。

參數:

深度 (int) – 樹狀圖的深度。負值表示沒有限制（針對最大深度回傳樹狀圖）。
resolution (float) – 解析度參數。
tol_optimization (float) – 進入新最佳化通道的目標函數的最低增加值。
tol_aggregation (float) – 進入新聚合通道的目標函數的最低增加值。
n_aggregations (int) – 最大疊代次數。負值表示沒有限制。
shuffle_nodes (布林值) – 如果 True，在最佳化之前洗牌節點。
random_state (整數) – 亂數產生器或亂數種子。如果 None，使用 numpy.random。
verbose (布林值) – 詳盡模式。

變數:

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[source]

設定演算法搭配資料。

參數:

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'（預設）。

傳回：

分數 - 分數。

傳回型態：

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 – 樹狀圖。
權重 - 節點權重。 'degree'（預設值）或 'uniform'。
normalized - 若為 True，會將分數標準化（介於 0 和 1 之間）。

傳回：

分數 - 分數。

傳回型態：

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)。 Tree Sampling Divergence: An Information-Theoretic Metric for Hierarchical Graph Clustering. 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[來源程式碼]: 重新排序樹狀圖，使高度呈非遞減順序。