没有，也不会有单一的最佳聚类算法，但是我们仍然希望能够确定那些在某些任务类型上表现出色并过滤掉系统令人失望的人。传统上，使用内部或外部有效性度量评估聚类算法。内部度量量化了所获得的分区的不同方面，例如簇紧凑性或点可分离性的平均程度。然而，他们的有效性是值得怀疑的，因为他们促进的聚类有时可能毫无意义。另一方面，外部措施将算法的输出与专家提供的基础真相分组进行了比较。常规的经典分区相似性分数，例如归一化的互信息，福克斯 - 马洛或调整后的兰德指数，可能没有所有期望的特性，例如，它们无法正确识别病理边缘病例。此外，它们不能很好地解释：很难说出0.8的分数。它的行为也可能随着真实簇的数量的变化而有所不同。这使得在许多基准数据集中比较聚类算法变得困难。为了解决这个问题，我们提出并分析了一种新措施：最佳设置匹配精度的不对称版本。它可以纠正机会和集群大小的不平衡性。

内部群集有效性度量（例如Calinski-Harabasz，Dunn或Davies-Bouldin指数）经常用于选择适当数量的分区数量，应将数据集分为二。在本文中，我们考虑如果将这些索引视为无监督学习活动中的客观功能会发生什么。关于轮廓指数的最佳分组是否真的有意义？事实证明，许多群集有效性指数促进了聚类，这些聚类与专家知识相匹配。我们还引入了邓恩指数的一个新的，表现出色的变体，该变体是建立在OWA操作员和接近邻居图的基础上的，因此，无论其形状如何，都可以更好地相互分离。

可以通过在各种基准问题上运行聚类算法的评估，并将其输出与专家提供的参考，地面真实分组进行比较。不幸的是，许多研究论文和研究生论文仅考虑少数数据集。同样，很少有这样的事实，即可以考虑许多同样有效的方法来集中给定的问题集。为了克服这些局限性，我们开发了一个框架，其目的是引入一致的方法来测试聚类算法。此外，我们已经在整个机器学习和数据挖掘文献中汇总，抛光和标准化了许多聚集基准电池，其中包括不同维度，尺寸和群集类型的新数据集。交互式数据集资源管理器，Python API的文档，对与其他编程语言（例如R或MATLAB）互动的方式的描述，以及其他详细信息，以及其他详细信息，都在https://clustering-benchmarks.gagolewski.com上提供。

应用分层聚类算法所需的时间最常由成对差异度量的计算数量主导。对于较大的数据集，这种约束使所有经典链接标准的使用都处于不利地位。但是，众所周知，单个连锁聚类算法对离群值非常敏感，产生高度偏斜的树状图，因此通常不会反映出真正的潜在数据结构 - 除非簇分离良好。为了克服其局限性，我们提出了一个名为Genie的新的分层聚类链接标准。也就是说，我们的算法将两个簇链接在一起，以至于选择的经济不平等度量（例如，gini-或bonferroni index）的群集大小不会大大增加超过给定阈值。提出的基准表明引入的方法具有很高的实际实用性：它通常优于病房或平均链接的聚类质量，同时保持单个连锁的速度。 Genie算法很容易平行，因此可以在多个线程上运行以进一步加快其执行。它的内存开销很小：无需预先计算完整的距离矩阵即可执行计算以获得所需的群集。它可以应用于配备有差异度量的任意空间，例如，在实际矢量，DNA或蛋白质序列，图像，排名，信息图数据等上。有关R。另请参见https://genieclust.gagolewski.com有关新的实施（GenieClust） - 可用于R和Python。

We review clustering as an analysis tool and the underlying concepts from an introductory perspective. What is clustering and how can clusterings be realised programmatically? How can data be represented and prepared for a clustering task? And how can clustering results be validated? Connectivity-based versus prototype-based approaches are reflected in the context of several popular methods: single-linkage, spectral embedding, k-means, and Gaussian mixtures are discussed as well as the density-based protocols (H)DBSCAN, Jarvis-Patrick, CommonNN, and density-peaks.

接收器操作特性（ROC）曲线下的区域称为AUC，是监督学习域中众所周知的性能措施。由于其引人注目的功能，它已在许多研究中使用，以评估和比较不同分类器的性能。在这项工作中，我们在集群分析的背景下更具体地，我们将AUC作为无监督学习域中的性能措施。特别是，我们详细说明了AUC作为聚类质量的内部/相对测量，我们将其称为聚类曲线下的区域（AUCC）。我们表明给定候选聚类解决方案的AUCC在随机聚类解决方案的空模型下具有预期值，无论数据集的大小如何，更重要的是，无论在评估下的群集的数量或（IM）平衡如何。此外，我们详细阐述了在我们考虑的内部/相对聚类验证的背景下，AUCC实际上是Baker和Hubert（1975）的伽玛标准的线性转换，我们也正式得出了理论预期机会群集的价值。我们还讨论了这些标准的计算复杂性，并表明，对于集群分析的大多数真实应用，伽玛的普通实施可能是计算令人望而不容的，但对于大多数真实应用，其与AUCC的等价实际上推出了更有效的算法过程。我们的理论发现得到了实验结果的支持。这些结果表明，除了由AUCC提供的有效和稳健的定量评估之外，ROC曲线本身的目视检查对于进一步评估来自更广泛的，定性的透视的候选聚类解决方案也是有用的。

群集分析需要许多决定：聚类方法和隐含的参考模型，群集数，通常，几个超参数和算法调整。在实践中，一个分区产生多个分区，基于验证或选择标准选择最终的分区。存在丰富的验证方法，即隐式或明确地假设某个聚类概念。此外，它们通常仅限于从特定方法获得的分区上操作。在本文中，我们专注于可以通过二次或线性边界分开的群体。参考集群概念通过二次判别符号函数和描述集群大小，中心和分散的参数定义。我们开发了两个名为二次分数的群集质量标准。我们表明这些标准与从一般类椭圆对称分布产生的组一致。对这种类型的组追求在应用程序中是常见的。研究了与混合模型和模型的聚类的似然理论的连接。基于Bootstrap重新采样的二次分数，我们提出了一个选择规则，允许在许多聚类解决方案中选择。所提出的方法具有独特的优点，即它可以比较不能与其他最先进的方法进行比较的分区。广泛的数值实验和实际数据的分析表明，即使某些竞争方法在某些设置中出现优越，所提出的方法也实现了更好的整体性能。

我们为保留部分顺序的部分有序数据的基于相似性的分层群集提供了一个目标函数。也就是说，如果$ x \ le y $，如果$ [x] $和$ [y] $是$ x $和$ y $的相应群集，那么有一个订单关系$ \ LE' $群集$ [x] \ Le'| Y] $。该理论将本身与现有的理论区分开了用于统称有序数据的理论，因为顺序关系和相似性被组合成双目标优化问题，以获得寻求满足两者的分层聚类。特别地，顺序关系在$ [0,1] $的范围内加权，如果相似性和顺序关系未对齐，则订单保存可能必须屈服于群集。找到最佳解决方案是NP-HARD，因此我们提供多项式时间近似算法，具有$ O \左的相对性能保证（\ log ^ {3/2} \！\！\，n \右）$ ，基于定向稀疏性切割的连续应用。我们在基准数据集中提供了演示，显示我们的方法优于具有重要边距的顺序保留分层聚类的现有方法。该理论是划分分层聚类的Dasgupta成本函数的扩展。

Originally, tangles were invented as an abstract tool in mathematical graph theory to prove the famous graph minor theorem. In this paper, we showcase the practical potential of tangles in machine learning applications. Given a collection of cuts of any dataset, tangles aggregate these cuts to point in the direction of a dense structure. As a result, a cluster is softly characterized by a set of consistent pointers. This highly flexible approach can solve clustering problems in various setups, ranging from questionnaires over community detection in graphs to clustering points in metric spaces. The output of our proposed framework is hierarchical and induces the notion of a soft dendrogram, which can help explore the cluster structure of a dataset. The computational complexity of aggregating the cuts is linear in the number of data points. Thus the bottleneck of the tangle approach is to generate the cuts, for which simple and fast algorithms form a sufficient basis. In our paper we construct the algorithmic framework for clustering with tangles, prove theoretical guarantees in various settings, and provide extensive simulations and use cases. Python code is available on github.

群集集群或共识群集已成为一种强大的工具，用于提高各种聚类方法的鲁棒性和结果的稳定性。加权聚类集群自然地从集群集群中产生。加权群集集合的参数之一是聚类集群中的元素（群集或集群）具有不同的质量，或者对象或特征具有不同意义的重要性。但是，不可能直接将加权机制从分类（监督）域中应用于群集（无监督）域，因为群集本质上是一个不存在的问题。本文通过讨论不同类型的权重，确定重量值的主要方法以及将加权聚类集合与复杂数据的应用程序的主要方法概述了加权集群集群集合概述。本文提出的统一框架将有助于聚类从业者为自己的问题选择最合适的加权机制。

我们解决了基于标签数据集基准群集技术的可靠性。外部聚类验证中的标准方案是基于每个类形成一个单一的，明显分离的群集的假设，将类标签用作地面真实群集。但是，由于这种集群标签匹配（CLM）的假设经常破坏，因此缺乏对基准数据集CLM的理智检查对外部验证的有效性产生怀疑。尽管如此，评估CLM的程度还是具有挑战性的。例如，内部聚类验证措施可用于量化同一数据集中的CLM以评估其不同的聚类，但并非旨在比较不同数据集的聚类。在这项工作中，我们提出了一种原则性的方法来生成数据集中的内部度量，以使CLM在数据集中进行比较。我们首先确定了数据集内措施之间的四个公理，并补充了Ackerman和Ben-David的数据库内公理。然后，我们提出了概括内部措施以实现这些新公理的过程，并使用它们扩展了广泛使用的Calinski-Harabasz索引，以进行数据库CLM之间的评估。通过定量实验，我们（1）验证了概括过程的有效性和必要性，（2）表明，所提出的数据与calinski-Harabasz索引索引准确地评估了整个数据集的CLM。最后，我们证明了在进行外部验证之前评估基准数据集的CLM的重要性。

模糊或柔软$ k $ -means目标是众所周知的$ k $ -means问题的流行泛化，将$ k $ -means扩展到不确定，模糊和否则难以群集的数据集的聚类能力。在本文中，我们提出了一个半监督的主动聚类框架，其中允许学习者与Oracle（域专家）进行交互，询问一组所选项目之间的相似性。我们研究了本框架中的聚类查询和计算复杂性。我们证明具有一些这样的相似性查询使得一个人能够将多项式时间近似算法获得到另外的辅助NP难题。特别是，我们提供了在此设置中的模糊聚类的算法，该算法询问$ O（\ mathsf {poly}（k）\ log n）$相似查询并使用多项式 - 时间复杂度运行，其中$ n $是项目的数量。模糊$ k $ -means目标是非渗透，$ k $ -means作为一个特殊情况，相当于一些其他通用非核解问题，如非负矩阵分解。普遍存在的LLOYD型算法（或交替的最小化算法）可以以局部最小粘在一起。我们的结果表明，通过制作一些相似性查询，问题变得更加易于解决。最后，我们通过现实世界数据集测试我们的算法，展示了其在现实世界应用中的有效性。

高斯混合物模型（GMM）提供了一个简单而原则的框架，具有适用于统计推断的属性。在本文中，我们提出了一种新的基于模型的聚类算法，称为EGMM（证据GMM），在信念函数的理论框架中，以更好地表征集群成员的不确定性。通过代表每个对象的群集成员的质量函数，提出了由所需群集的功率组组成的组件组成的证据高斯混合物分布来对整个数据集进行建模。 EGMM中的参数通过特殊设计的预期最大化（EM）算法估算。还提供了允许自动确定正确数量簇的有效性指数。所提出的EGMM与经典GMM一样简单，但可以为所考虑的数据集生成更有信息的证据分区。合成和真实数据集实验表明，所提出的EGMM的性能比其他代表性聚类算法更好。此外，通过应用多模式脑图像分割的应用也证明了其优势。

The problem of comparing two different partitions of a finite set of objects reappears continually in the clustering literature. We begin by reviewing a well-known measure of partition correspondence often attributed to Rand (1971), discuss the issue of correcting this index for chance, and note that a recent normalization strategy developed by Morey and Agresti (1984) and adopted by others (e.g., Milligan and Cooper 1985) is based on an incorrect assumption. Then, the general problem of comparing partitions is approached indirectly by assessing the congruence of two proximity matrices using a simple cross-product measure. They are generated from cOrresponding partitions using various scoring rules. Special cases derivable include traditionally familiar statistics and/or ones tailored to weight certain object pairs differentially. Finally, we propose a measure based on the comparison of object triples having the advantage of a probabilistic interpretation in addition to being corrected for chance (i.e., assuming a constant value under a reasonable null hypothesis) and bounded between -4-I.

随机块模型（SBM）是一个随机图模型，其连接不同的顶点组不同。它被广泛用作研究聚类和社区检测的规范模型，并提供了肥沃的基础来研究组合统计和更普遍的数据科学中出现的信息理论和计算权衡。该专着调查了最近在SBM中建立社区检测的基本限制的最新发展，无论是在信息理论和计算方案方面，以及各种恢复要求，例如精确，部分和弱恢复。讨论的主要结果是在Chernoff-Hellinger阈值中进行精确恢复的相转换，Kesten-Stigum阈值弱恢复的相变，最佳的SNR - 单位信息折衷的部分恢复以及信息理论和信息理论之间的差距计算阈值。该专着给出了在寻求限制时开发的主要算法的原则推导，特别是通过绘制绘制，半定义编程，（线性化）信念传播，经典/非背带频谱和图形供电。还讨论了其他块模型的扩展，例如几何模型和一些开放问题。

同质性是描述边缘连接相似节点的趋势的图形属性。相反称为异性。尽管同质性对于许多现实世界网络是自然的，但也有没有此属性的网络。人们通常认为，标准消息的图形神经网络（GNNS）在非双性图形上表现不佳，因此此类数据集需要特别注意。尽管为异性图开发图表的学习方法已经付出了很多努力，但尚无普遍同意同质的措施。但是，在文献中使用了几种测量同质性的指标，但是，我们表明所有这些度量都有关键的缺点，以阻止不同数据集之间的同质级别比较。我们将理想的属性形式化，以进行适当的同质度量，并展示如何将有关分类绩效指标属性的现有文献与我们的问题联系起来。在这样做时，我们找到了一种措施，我们称调整后的同质性比现有同质措施更满足所需的特性。有趣的是，该措施与两个分类性能指标有关 - 科恩的kappa和马修斯相关系数。然后，我们超越了同质性的二分法，并提出了一种新的属性，我们称之为标签信息性（LI），该属性表征了邻居标签提供有关节点标签的信息的数量。从理论上讲，我们表明LI在具有不同数量的类和类大小平衡的数据集中相当。通过一系列实验，我们表明LI是对数据集上GNN的性能的更好预测指标，而不是同质性。我们证明了Li解释了为什么GNN有时可以在异性数据集上表现良好 - 这是文献中最近观察到的现象。

我们提出了对学度校正随机块模型（DCSBM）的合适性测试。该测试基于调整后的卡方统计量，用于测量$ n $多项式分布的组之间的平等性，该分布具有$ d_1，\ dots，d_n $观测值。在网络模型的背景下，多项式的数量（$ n $）的数量比观测值数量（$ d_i $）快得多，与节点$ i $的度相对应，因此设置偏离了经典的渐近学。我们表明，只要$ \ {d_i \} $的谐波平均值生长到无穷大，就可以使统计量在NULL下分配。顺序应用时，该测试也可以用于确定社区数量。该测试在邻接矩阵的压缩版本上进行操作，因此在学位上有条件，因此对大型稀疏网络具有高度可扩展性。我们结合了一个新颖的想法，即在测试$ K $社区时根据$（k+1）$ - 社区分配来压缩行。这种方法在不牺牲计算效率的情况下增加了顺序应用中的力量，我们证明了它在恢复社区数量方面的一致性。由于测试统计量不依赖于特定的替代方案，因此其效用超出了顺序测试，可用于同时测试DCSBM家族以外的各种替代方案。特别是，我们证明该测试与具有社区结构的潜在可变性网络模型的一般家庭一致。

Graph clustering is a fundamental problem in unsupervised learning, with numerous applications in computer science and in analysing real-world data. In many real-world applications, we find that the clusters have a significant high-level structure. This is often overlooked in the design and analysis of graph clustering algorithms which make strong simplifying assumptions about the structure of the graph. This thesis addresses the natural question of whether the structure of clusters can be learned efficiently and describes four new algorithmic results for learning such structure in graphs and hypergraphs. All of the presented theoretical results are extensively evaluated on both synthetic and real-word datasets of different domains, including image classification and segmentation, migration networks, co-authorship networks, and natural language processing. These experimental results demonstrate that the newly developed algorithms are practical, effective, and immediately applicable for learning the structure of clusters in real-world data.

统计推断中的主要范式取决于I.I.D.的结构。来自假设的无限人群的数据。尽管它取得了成功，但在复杂的数据结构下，即使在清楚无限人口所代表的内容的情况下，该框架在复杂的数据结构下仍然不灵活。在本文中，我们探讨了一个替代框架，在该框架中，推断只是对模型误差的不变性假设，例如交换性或符号对称性。作为解决这个不变推理问题的一般方法，我们提出了一个基于随机的过程。我们证明了该过程的渐近有效性的一般条件，并在许多数据结构中说明了，包括单向和双向布局中的群集误差。我们发现，通过残差随机化的不变推断具有三个吸引人的属性：（1）在弱且可解释的条件下是有效的，可以解决重型数据，有限聚类甚至一些高维设置的问题。 （2）它在有限样品中是可靠的，因为它不依赖经典渐近学所需的规律性条件。 （3）它以适应数据结构的统一方式解决了推断问题。另一方面，诸如OLS或Bootstrap之类的经典程序以I.I.D.为前提。结构，只要实际问题结构不同，就需要修改。经典框架中的这种不匹配导致了多种可靠的误差技术和自举变体，这些变体经常混淆应用研究。我们通过广泛的经验评估证实了这些发现。残留随机化对许多替代方案的表现有利，包括可靠的误差方法，自举变体和分层模型。

尽管在机器学习的方法论核心中是一个问题，但如何比较分类器仍未达成一致的共识。每个比较框架都面临着（至少）三个基本挑战：质量标准的多样性，数据集的多样性以及选择数据集选择的随机性/任意性。在本文中，我们通过采用决策理论的最新发展，为生动的辩论增添了新的观点。我们最终的框架基于所谓的偏好系统，通过广义的随机优势概念对分类器进行排名，该概念强大地绕过了繁琐的，甚至通常是自相矛盾的，对聚合的依赖。此外，我们表明，可以通过解决易于手柄的线性程序和通过适应的两样本观察随机化测试进行统计测试来实现广泛的随机优势。这确实产生了一个有力的框架，可以同时相对于多个质量标准进行分类器的统计比较。我们在模拟研究和标准基准数据集中说明和研究我们的框架。