说话人日志（Speaker Diarization，SD）系统的目标是解决“谁在什么时间说话”的说话人识别问题，是一种可以广泛应用于客服、会议等多轮对话场景的语音技术。无监督聚类一直是 Speaker Diarization (说话人日志) 任务中最核心的一环，通过无监督聚类的方法，可以确定一场会议或多人讨论中的全局关键信息，如：说话人数量、说话人声音特征的分布等。
Speaker diarization 任务中的无监督聚类，通常是对神经网络提取出的代表说话人声音特征的空间向量进行聚类。其中，K-means, Spectral Clustering, Agglomerative Hierarchical Clustering (AHC) 是在说话人任务中最常见聚类方法。在说话人日志中，一些工作常基于 AHC 的结果上使用 Variational Bayes Clustering (VBx) 进行优化。
本文基于达摩院语言AI的实际应用实践，对 Speaker Diarization 任务中常见的聚类方法进行探讨，以增加业界对聚类算法的关注。
K-means 聚类算法
K-means 是机器学习中最常见的一种聚类算法。在给定一个 k 值的条件下，根据每个点与类中心的相对距离，通过不断迭代类中心，将每一个点最终归入 k 个类别中。
优点：实现简单，计算复杂度低，可以处理大量数据集的聚类。
缺点：对初始化和 outlier 较为敏感，对 imbalanced data 和 nonconvex 的分布处理不好，以及需要提前估算 k 值。
Spectral Clustering 谱聚类算法
Spectral Clustering[1] 是基于图的概念基础上进行的聚类算法，通过构建 Laplacian 矩阵，并计算 Laplacian 矩阵分解的 eigenvalues和 eigenvectors 获得特征矩阵，并在此基础上进行聚类。
优点：相比于 k-means 算法，spectral clustering 在处理高维数据和稀疏数据上更加鲁棒。
缺点：与 k-means 一样都依赖于提前对 k 值的估算。
估算 k 值的方法
我们列举三篇估算 k 值方法的工作：
- Andrew Ng 的 On Spectral Clustering: Analysis and an algorithm[2] 通过最大连续重复的 eigenvalue 数量来进行判断。该方法较为简单易懂，但是在噪声较大且分布不均衡的数据集上，估算误差较大。
- Self-Tuning Spectral Clustering[3] 通过寻找梯度下降最优的 rotation 来恢复到由 eigenvectors 组成的矩阵，将恢复代价最小化的 column 数量定为类别数。
- 近两年在说话人日志领域较为常用Normalized Maximum Eigengap[4]，基于规整后的 eigenvalue 下降梯度，该方法简单实用，计算复杂度低，很快在 diarization 中得到广泛采用。
在说话人日志系统的实际应用中，上述基于 eigensolver 的方法在面对类别数较多时，有近似类别，数量分布不平衡，或者 noise 较多的场景，估算类别数量不准确，聚类效果不佳。主要原因是 eigensolver 难以从原始 Laplacian 矩阵中分解出多个能代表各个类别的正交的 eigenvector。
Agglomerative Hierarchical Clustering
另外一种常见的聚类方法是 Agglomerative Hierarchical Clustering (AHC)，通过不断将类别进行合并直至触发停止阈值。
优点：该方法基于类别之间的距离来做出决策，因此受到数据不平衡的影响较小。
缺点：对阈值的设定较为敏感，同时也更依赖 embedding 本身的区分性。
近两年的说话人日志中，有一些工作在 AHC 聚类的结果上进行了更有针对性的优化。比如，Variational Bayes Clustering (VBx) 以 AHC 结果作为初始化，建立了一个贝叶斯的 Hidden Markov Model (Bayes HMM) 来进行 embedding 的聚类[5]。
Uniform Manifold Approximation & Projection
说话人 embedding 模型是通过学习数千乃至数万个说话人标签的概率分布而得到，通过该模型获得的 embedding 通常包含大量冗余信息。
在 diarization 任务中，通常只需要对几个说话人进行区分，因此针对几个目标说话人数据的分布进行降维，映射到使目标说话人之间区分度最大的低维空间中，过滤其它冗余信息的干扰，可以获得更稳定的提升。
Uniform Manifold Approximation and Projection (UMAP) 降维算法基于流形拓扑结构，从样本中学习到从高维空间分布映射到低维空间分布，同时保留了高维空间中显著的拓扑结构[6]。
根据 Nerve Theorem，我们可以将复杂的拓扑结构，用 combinatorial 的方式进行表达，提供了可计算性。此外，UMAP 中的 Uniform 代表对数据均匀分布的要求，然而在实际的复杂拓扑流形中，数据分布往往是不均匀的。因此，UMAP 构建了一种黎曼度量使得数据在该度量下所构建的空间中呈现近似均匀分布。
UMAP 通过类似 cross entropy 损失函数，学习到使 cost 最小的方法将数据分布从高维空间映射到低维空间：
其中，该函数的前半部分，专注于数据分布的局部结构，确保近似的数据点在低维空间中能靠近对方；函数的后半部分，则是扮演了一种类似“相持力”的作用，两者的相互平衡，使得 UMAP 学习到的低维空间表达可以更完整地保留全局拓扑结构。
与其它常见的降维算法（如t-SNE，PCA等）相比，UMAP 更完整地保留了数据分布在高维空间的结构，尤其是全局结构。下图列举了几种主流降维算法在不同数据集上的可视化表达：
Source: [6]
此外，由于 UMAP 的计算效率显著优于 t-SNE，使得 UMAP 可以处理超高维度及超大量级数据的降维任务。下图正是 UMAP 对 30,000,000 个 180 万维的质数可整除性的二进制向量进行处理所得到的可视化结果，可以看到 UMAP 依然能保留其中一部分明显的分布特性。
- Source: [6]
在 Speaker Diarization 任务中，经过UMAP降维后的数据也被证明了具有更稳定的聚类效果，尤其是当说话人数量较多时（大于8人），其对人数判断的准确性，以及聚类效果的稳定性都要优于常见的 k-means, spectral, AHC, VBx 等算法。以下两篇工作都成功地利用 UMAP 显著提升了 speaker diarization 系统的性能[7][8]:
1. Reformulating Speaker Diarization as Community Detection With Emphasis On Topological Structure.
Authors：Siqi Zheng, Hongbin Suo
https://arxiv.org/pdf/2204.12112.pdf
2. PRISM: Pre-trained Indeterminate Speaker Representation Model for Speaker Diarization and Speaker Verification.
Authors：Siqi Zheng, Hongbin Suo, Qian Chen
https://arxiv.org/pdf/2205.07450.pdf
(请复制到浏览器中打开）
多次实验表明，以下几种聚类算法，在 UMAP 降维之后配合使用，效果较优：
- HDBSCAN
HDBSCAN[9] 是基于密度进行聚类的算法。而密度的表示来自于每个点的 core distance 的定义。该定义可以让稀疏的点更加稀疏，使 cluster 之间的分离度更加明显。利用 Minimum Spanning Tree 构建起所有sample的相互连接和层次结构。最后通过对层次的合并得到合适的聚类结果。 - Louvain
作为最常见的社群检测（Community Detection）算法之一，Louvain 通过 Modularity 来衡量和优化图中节点的社群划分[10]。该算法由于简单易懂，效果稳定，计算复杂度较低，很快得到较广泛应用。 - Leiden
Leiden 算法是基于 Louvain 的一次优化。Leiden 算法解决了 Louvain 结果中存在的社群内部 bad connected 的情况，同时 Leiden 在计算效率上较 Louvain 也有了明显提升[11]。
达摩院在会议产品应用实践中使用UMAP降维后加HDBSCAN聚类的算法，对说话人数量的判断以及聚类的准确率都取得了提升，用户体验得到明显改善。
>> 总结
总体而言，过去几年业界的关注点更加聚焦于网络结构的优化，提取更优的 speaker embedding，或是通过端到端的方法解决 diarization 问题，对于聚类算法本身的关注度较少。
实践应用中，聚类算法在 diarization 系统中依然占据重要地位，并且更优的聚类算法可以对说话人数量的判断，每个的片段的分类，以及最终的 DER 结果带来明显的提升。说话人领域的研究者对于聚类算法的更多关注将给该领域的研究带来收益。
Reference：
[1] Luxberg. A Tutorial on Spectral Clustering.
https://arxiv.org/pdf/0711.0189.pdf
[2] Ng, Jordan, Weiss, On Spectral Clustering: Analysis and an algorithm.
https://proceedings.neurips.cc/paper/2001/file/801272ee79cfde7fa5960571fee36b9b-Paper.pdf
[3] Zelnik-Manor, Perona, Self-Tuning Spectral Clustering. https://proceedings.neurips.cc/paper/2004/file/40173ea48d9567f1f393b20c855bb40b-Paper.pdf
[4] Park, Han, Kumar, Narayanan, Auto-Tuning Spectral Clustering for Speaker Diarization Using Normalized Maximum Eigengap.
https://arxiv.org/pdf/2003.02405.pdf
[5] Landini, Profant, Diez, Burget, Bayesian HMM clustering of x-vector sequences (VBx) in speaker diarization: theory, implementation and analysis on standard tasks.
https://arxiv.org/pdf/2012.14952.pdf
[6] McInnes, Healy, Melville, UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction.
https://arxiv.org/pdf/1802.03426.pdf
[7] Zheng, Suo. Reformulating Speaker Diarization as Community Detection With Emphasis On Topological Structure.
https://arxiv.org/pdf/2204.12112.pdf
[8] Zheng, Suo, Chen. PRISM: Pre-trained Indeterminate Speaker Representation Model for Speaker Diarization and Speaker Verification.
https://arxiv.org/pdf/2205.07450.pdf
[9] McInnes, Healy. Accelerated Hierarchical Density Clustering.
https://arxiv.org/pdf/1705.07321.pdf
[10] Blondel, Guillaume, Lambiotte, Lefebvre. Fast unfolding of communities in large networks.
https://arxiv.org/pdf/0803.0476.pdf
[11] Traag, Waltman, van Eck. From Louvain to Leiden: guaranteeing well-connected communities.
