`KMedoids()`

用于中心聚类的函数（每个簇的中心点都是真实存在的），支持三种 KMedoids、PAM（Partitioning Around Medoids）、PAMonce（PAM with a only-once）三种算法，三者原理、区别详见文档 KMedoids v.s. PAM (PAMonce)待补充。KMedoids 的所有参数均遵从 WeightedCluster::KMedoids。

Sequenzo 也实现了层次聚类，相关学习资料见视频层次聚类的树状图如何看？序列分析和回归分析如何结合？。

函数使用

仅包含必需参数的最小示例（足以满足大多数用例）：

python

clustering = KMedoids(
   diss=om,      # 相异矩阵（DataFrame 或 ndarray）
   k=5           # 聚类数量
)

具有所有可用参数的完整示例（用于高级定制）：

python

clustering = KMedoids(
   diss=om,                # 差异矩阵，来自 get_distance_matrix()
   k=5,                    # 聚类数量
   method='PAMonce',       # 聚类算法：'KMedoids'、'PAM' 或 'PAMonce'
   initialclust=None,      # 可选：medoid ID / 成员矩阵 / 链接矩阵
   npass=1,                # 遍历次数（重复优化循环）
   weights=None            # 可选：每个序列的权重（默认为 1）
)

入口参数

diss

即 “dissimilarity matrix”，必传，允许传入的数据类型是DataFrame，距离矩阵（由 get_distance_matrix 计算得到）。

k

必传，允许传入的数据类型是int，想要聚类的簇的数量。

method

可传，允许传入的数据类型是String，默认'PAMonce'，选择使用的聚类方法。

共支持三种方法：KMedoids、PAM（Partitioning Around Medoids）、PAMonce（PAM with a only-once），三种方法得到的簇中心都是真实存在的数据点。PAM 和 PAMonce 是 KMedoids 的一个变种，它们之间的区别见文档 [待补充]。

initialclust

即 “initial_cluster_assignment”（表示 “初始化的簇结构” 或 “初始簇分配方案”），可传，允许传入的数据类型是list、numpy.ndarray、linkage matrix，默认None。

初始化的簇结构：即，指定簇中心。由于一般簇中心 ≥ 2，传入的是一个list或numpy.ndarray。既表明划分了几个簇，也表示这些簇的初始中心点都是什么。
初始簇分配方案：即，隶属矩阵。表明所有的数据点都分配在了哪些簇，因此传入的是list/numpy.ndarray或linkage matrix。

每个聚类算法开始前，都需要先通过某种策略确定初始中心点。如果提供了initialclust参数，将直接/间接使用其中的数据得到初始中心。

为None时，程序在 [1, number_of_elements] 之内随机选择k个点作为初始中心点。
为list/numpy.ndarray时，可以是（1）用户选定的用于初始化的簇中心（里面的每个元素都是真实存在的数据id），程序会用指定的中心点作为初始中心点，此时list/numpy.ndarray里的元素个数必须等于k。也可以是（2）每个数据点的隶属矩阵（此时元素个数必须等于序列总数），程序会利用权重从给定的簇中选择初始中心点。如何选择，见 细节补充。
为linkage matrix时，程序先通过层次聚类cut_tree()得到隶属矩阵，然后再利用权重从得到的簇中选择初始中心点，同见 细节补充。

三个参数的选择场景如下：

参数	场景
`None`	用户想把初始化全权交给程序去做（程序默认随机选择`k`个数据点作为中心点，没有默认的隶属矩阵）
`list/numpy.ndarray`	【场景1：初始化的簇结构，即指定中心点】用户想自己指定中心点作为初始点，而不是由程序随机选择【场景2：初始化簇分配方案，即有隶属矩阵】用户已经有比较好的隶属矩阵了，想利用这个隶属矩阵让程序找到比较合适的初始中心点
`linkage matrix`	用户有表示层次聚类（Hierarchical Clustering）合并过程的连接矩阵，想利用连接矩阵让程序找到比较合适的初始中心点

我们发现，指定中心点用list表示的居多；隶属矩阵用numpy.ndarray表示的居多。

npass

即 “number of passes”，可传，允许传入的数据类型是int，默认1，数据点分配的过程会重复多少次。

一次数据分配的过程指（以 PAM 为例）：遍历每个簇，试图为其找到更优的中心点（“更优”的评判规则见 Details）。一次簇的全遍历，就是一次数据点重分配的过程。

npass就是这个过程会重复进行多少次。

weights

可传，允许传入的数据类型是list/numpy.ndarray，默认None，每个数据点的权重。

为None时，默认所有序列的权重均为 1。

返回值

pandas.Series，一个隶属矩阵，指示每个 id 属于哪个簇。

细节补充

程序利用权重优化初始中心点的过程如下：

按照用户传入的中心点，使用cut_tree划分簇，得到初步的聚类结果。
对于同一个簇内的所有数据点，计算其与其他数据点的距离和。
$D (x) = \sum_{i \neq x}^{N} w_{i} * d i s s (x_{i}, x)$
选择距离和最小的点，作为该簇的中心点。
以此类推，得到所有簇的中心。

在算法的具体执行中，“更优”指的是：

遍历所有数据点，尝试让每一个数据点当作新的中心点；
比较新的中心点与当前簇的中心点：如果以 “新” 换 “旧” 的损失代价更小，则替换。计算损失代价的公式如下：
$L o s s = \sum_{x \in a l l}^{N} \sum_{i \in C_{j}}^{N} w_{x} * (d i s s (i, x) - d i s s (i, M_{j}))$

其中，x表示新的中心点。

Loss ＜ 0，损失为负，说明簇内平均距离与上次相比在变小；Loss ＞ 0，损失为正，说明簇内平均距离与上次相比在变大。直到损失代价大于 0，终止循环，停止寻找。

样例

下面是给出的使用示例。数据来源 Gapminder，是各个国家（共194个）从1800年到2022年的二氧排放的数据。此数据集已经内置在 Sequenzo 里，详情移步。

我们对其进行聚类，并对输出进行了 t-SNE 可视化，以便更直观地看到聚类效果。

Python

from sequenzo import *
from sequenzo.dissimilarity_measures import get_distance_matrix
from sequenzo.clustering.KMedoids import KMedoids

df = load_dataset('country_co2_emissions')

time = list(df.columns)[1:]
states = ['Very Low', 'Low', 'Middle', 'High', 'Very High']
sequence_data = SequenceData(df, time=time, id_col="country", states=states)
om = get_distance_matrix(sequence_data, method="OM", sm="TRATE", indel="auto")

centroid_indices = [0, 50, 100, 150, 190]
n_pass = 10

# 例1: 未指定中心点的 KMedoids 算法
clustering = KMedoids(diss=om,
                      k=5,
                      method='KMedoids',
                      npass=n_pass,
                      weights=weights)

# 例2: 指定中心点的 PAM 算法
clustering = KMedoids(diss=om,
                      k=5,
                      method='PAM',
                      initialclust=centroid_indices,
                      npass=n_pass,
                      weights=weights)
# 例3: 默认参数的 PAMonce 算法
clustering = KMedoids(diss=om,
                      k=5,
                      method='PAMonce',
                      npass=n_pass,
                      weights=weights)

输出

例1:

python

[>] SequenceData initialized successfully! Here's a summary:
[>] Number of sequences: 193
[>] Number of time points: 223
[>] Min/Max sequence length: 223 / 223
[>] States: ['Very Low', 'Low', 'Middle', 'High', 'Very High']
[>] Labels: ['Very Low', 'Low', 'Middle', 'High', 'Very High']
[>] Processing 193 sequences with 5 unique states.
[>] Transition-based substitution-cost matrix (TRATE) initiated...
  - Computing transition probabilities for: [Very Low, Low, Middle, High, Very High]
[>] Indel cost generated.

[>] Identified 175 unique sequences.
[>] Starting Optimal Matching(OM)...
[>] Computing all pairwise distances...
[>] Computed Successfully.
[>] Starting KMedoids...
[>] Computed successfully.

例2:

python

[>] Starting Partitioning Around Medoids (PAM)...
  - PAM loop over pass number  1
[>] Computed successfully.

例3:

python

[>] Starting Partitioning Around Medoids with a Once-Only Swap Pass (PAMonce)...
[>] Computed successfully.

作者

代码：李欣怡，邓诚

文档：李欣怡，曲思竹

编辑：梁彧祺

翻译、测试：曲思竹

KMedoids() ​

函数使用 ​

入口参数 ​

diss ​

k ​

method ​

initialclust ​

npass ​

weights ​

返回值 ​

细节补充 ​

样例 ​

输出 ​

作者 ​

`KMedoids()`

函数使用

入口参数

diss

k

method

initialclust

npass

weights

返回值

细节补充

样例

输出

作者