无参数聚类算法的研究及性能提升

8934基于第一近邻关系的无参数聚类算法M. Saquib Sarfraz1，2，Vivek Sharma1，RainerStiefeldinger11卡尔斯鲁厄理工2戴姆勒TSS，德国{firstname.lastname}@ kit.edu摘要我们提出了一种新的聚类方法的形式，一个单一的聚类方程，能够直接发现分组的数据。主要的命题是，每个样本的第一个邻居是发现大链和找到数据中的组所与大多数现有的聚类算法相比，该算法属于家庭的分层凝聚方法。该技术具有非常低的计算开销，易于扩展，适用于大型实际问题。对来自不同领域的1077到810万个样本的知名数据集的评估显示，与现有的聚类技术相比，性能有了很大的提高。[代码发布]1. 介绍事实上，在所有科学领域都需要发现数据中的自然分组。尽管在设计聚类技术方面进行了五年的研究，但仍然没有通用的解决方案，即1。可以以高准确度/纯度自动确定真实（或接近真实）聚类;2.）不需要超参数或数据的先验知识;3.）在不同的数据域中进行一般化; 4.）可以很容易地扩展到非常大的（数百万个样本）数据，而不需要过高的计算资源。聚类本质上建立在相似性的概念上。所有的聚类技术都试图通过设计一个标准来捕捉这种相似性的概念，该众所周知的基于中心的方法（例如，Kmeans）迭代地将点分配给基于它们到聚类中心的直接距离而选择的数目的聚类凝聚聚类方法基于预定义的距离阈值合并点。最近的方法构建相似性图（例如，谱聚类技术），并通过使用这些距离作为边权重并将采样点作为节点。所有现有的聚类技术都使用某种形式的先验知识/假设来定义相似性目标，以获得数据中的特定分组。这种先验知识以预先设置聚类的数量或设置距离阈值或其他超参数的形式出现，这些超参数呈现用户定义的相似性概念以用于获得分组。这些选择是主观的，并且必须随着基础数据的变化而变化。这意味着这些参数并不稳定，需要针对每个数据集进行调整这使得聚类问题非常困难，因为没有标准的解决方案可以用于不同的问题。在本文中，我们描述了一个有效的和完全无参数的无监督聚类算法，不遭受任何上述问题。通过我们所提出的方法的主要由于如此获得的分组不依赖于任何预定义的相似性阈值或其他特定目标，因此该算法可能具有发现数据中的自然聚类的潜力所提出的方法具有低的计算开销，是非常快的，处理大数据，并提供有意义的分组的数据与高纯度。2. 相关工作书中已经写了无数的聚类技术指导[12]。代表性的算法可以大致分为三个方向，质心/分割算法（例如，Kmeans，Affinity Prop agation）、分层凝聚/分裂方法以及将聚类视为图划分问题的方法（例如，谱聚类方法）。对于基于中心的聚类，已知Kmeans对初始K个质心的选择敏感。亲和传播算法[13]通过将每个样本视为8935我样本，然后采用有效的消息解析机制，直到出现一组好的样本及其对应的聚类这种基于分区的方法通常也通过选择目标函数，然后开发近似优化该目标的算法来实现[29，1，32]。谱聚类（SC）及其变体最近越来越受欢迎[36]。大多数谱聚类算法需要计算全相似图的拉普拉斯矩阵，且具有二次复杂度，严重限制了谱聚类算法对大数据集的可扩展性已经提出了一些近似算法[39，23]来缩放谱方法。一个重要的聚类方向已经通过学习稀疏子空间来接近这些谱方案，其中数据点被更好地分离，参见Elhamifar和Vidal其目的是减少高维特征空间中距离意义最近，许多方法也使用低秩约束来估计这样的子空间，参见Vidal等人。[35]以及Brbic和Kopriva最近的工作[4]。在他们卓越的经典作品中，Jarvis Patrick [17]提出了共享最近邻的重要性，以定义点之间的相似性这个想法植根于观察到两个点相似的程度，他们的第一个k-邻居匹配。 这样得到的相似度是比标准欧几里德度量更好的点间距离度量。使用邻居来定义点之间的相似性已用于基于分区的分层和谱聚类技术[27，5，44]。我 们 的 论 文 与 已 被 广 泛 研 究 的 层 次 凝 聚 聚 类（HAC）方法密切相关[30]。分层聚类的流行源于这样一个事实，即它产生一个聚类树，提供了有意义的方法来解释不同粒度级别的数据出于这个原因，社区中有很多兴趣开发和研究层次聚类方法的理论最近的一些工作建立了广泛使用的分层算法的自然目标函数的保证[25，9]。在凝聚方法中，每个输入样本点都以一个聚类开始。然后，迭代地，对相似的集群合并，根据一些度量的相似性，通过研究联动方案。最常见的基于链接的算法（单一，平均和完全链接）通常基于Kruskals最小生成树算法[20]。连锁方法根据样本的成对距离合并两个聚类。链接方案可以通过基于最小化簇内方差的总和来链接簇的目标函数来更好地接近，沃德[37]。这种方法通常会产生直接得到最优树。它启动了一系列开发算法的工作，明确优化这些对象[31，7，25，9]。最近，聚类也被用于联合学习样本的非线性嵌入这可以通过基于深度学习的方法来实现，例如，采用自动编码器通过使用现有的聚类方法[40，38，15，18]来优化和学习特征。这些基于深度学习的方法主要是使用现有聚类方法作为生成伪标签的手段[6]或作为训练神经网络的目标的特征表示现有的聚类方法几乎都是直接对样本的距离值这使得这些方法很难扩展到大数据，因为它们需要访问存储为浮点数的完整距离除此之外，所有当前的聚类方法都需要某种形式的监督/专家知识，从要求指定聚类的数量到设置相似性阈值或其他算法特定的超参数。我们的建议是一个重大转变，从这些方法中，我们不需要任何这样的先验知识，不需要保持访问完整的成对距离浮动。3. 提出的聚类方法从历史上看，聚类方法通过解释数据点之间的直接距离来获得数据分组位于高维空间中的数据在这些距离方面具有较少的接近度信息旨在描述超空间的均匀体积的方法可能会失败，因为源样本很难均匀分布在目标流形内。另一方面，语义关系（即，谁是你最好的朋友/或朋友的朋友）可能不受此影响，因为他们依赖于间接关系而不是确切的距离。我们的建议是直观地发现在数据中的分组的语义关系我们观察到，每个点的第一个邻居是一个足够的统计数据，以发现数据中的链接链。因此，可以实现将数据合并到聚类中，而不需要在所有数据点之间保持完整的距离矩阵。此外，使用这种方法，不必设置阈值或其他超参数我们捕捉这个观察建议的聚类方程，然后详细描述了完整的算法。3.1. 聚类方程给定每个数据点的第一近邻的整数索引，我们直接定义一个邻接连接矩阵.1，如果j=κ1或κ1=i或κ1=κ1比单一或平均链接方案更好的合并。Dasgupta [10]最近提出了一个目标函数opti-A（i，j）=I j0否则i j（1）层次聚类其中κ1表示点i的第一个邻居。的8936我J我J123456789123456（一）789（b）第（1）款（c）第（1）款图1.集群方程演练：集群在我们的太阳系行星（a）行星和它们的第一个邻居。（b）邻接链接矩阵方程1。（c）使用（b）的邻接矩阵的有向图FINCH发现了3个簇，显示为有向图每个行星都由[ www.example.com ]中描述的前15个属性表示https://nssdc.gsfc.nasa.gov/planetary/factsheet/。邻接矩阵通过金星将每个点i连接到它的第一个邻居 这是j=κ1，通过κ1=i和链接点也是为什么这些邻居能形成连锁的基础注意I j（i，j）与κ1有相同的邻居=κ1。等每个邻接条件如何导致链接步骤1返回一个对称稀疏矩阵，直接指定一个图，其我们可以看到，在其惊人的简单性，集群方程星球例如，邻接条件j = κ1简单地将所有行星与它们的第一个邻居联系起来。 条件κ1=κ1将水星-火星和地球-月球连接在一起I j在不依赖于任何阈值或进一步分析的情况下提供数据中的聚类。通过使用有向或无向图G=（V，E），可以从邻接矩阵有效地获得连通分量，其中V是节点（要聚类的点）的集合，并且边E连接节点A（i，j）= 1。直观地，等式1中的条件是组合1-最近邻（1-nn）和共享最近邻（SNN）图。然而，请注意，所提出的聚类方程直接提供聚类，而不解决图分割问题。更准确地说，从建议的聚类方程得到的邻接矩阵具有绝对链接。我们不需要使用任何距离值作为边权重，并且需要解决图划分。这是使其独特的原因，因为通过仅使用第一邻居的整数索引，等式1指定并发现语义关系并直接递送聚类。计算邻接矩阵在计算上也是非常有效的，因为它可以很容易地通过简单的稀疏矩阵乘法和加法运算获得为了理解方程1的机制，并了解它如何在数据中链接大量样本，让我们首先看一个简单的太阳系行星聚类的例子。我们可以将行星聚集在已知测量的空间中，质量、直径、重力、密度、日长、轨道周期和轨道速度等。我们通过从NASA的行星情况说明书中获取的前15个测量值来描述每颗行星。每个行星在这个空间中的第一个邻居是具有最小距离的那个，通过计算成对的欧几里得距离获得图1（a）显示了9个样本（8颗行星和月球）及其第一个邻居。有了这些信息，形成9×9的邻接矩阵（见图1）。1（b））根据等式1。一个重要的观察是，邻居是对称的，例如，地球是地球的第一个邻居因为它们有相同的第一邻居。条件κ1=i强制对称并桥接链中缺失的环节地球通过这种条件与金星相连图1(c)显示了这个邻接矩阵的有向图。请注意，九颗行星中有五颗是直接连在一起的，而对称的邻居则形成了两个独立的星团。这段简短的讲解解释了发现了三个星系团的方程1的机制。有趣的是，天文学家还将这些行星分为三组，岩石行星（水星，金星，地球，月球和火星）在一组，气体行星（木星，土星）在较大的尺寸方面与金属核心相似，而冰巨星（天王星，海王星）由于类似的大气层与岩石核心而被分组在一起。3.2. 建议的层次聚类对于所发现的集群是否确实是数据中的真实分组，没有明显的答案。这是因为人们认为正确的聚类概念是观察者的主观意见。Balcan等人已经很好地研究了寻找真实聚类的问题。[2]，其中他们表明，应该首选分区列表或层次结构，而不是单个平面分区。在这样一组分组中，他们表明，已知单个或平均链接算法可以在相似性函数的某些属性下可证明地恢复地面实况聚类。等式1将数据的平坦分区传递到一些自动发现的集群中。以聚合方式递归地向上跟随它可以提供以不同粒度级别捕获底层数据结构的该分区的进一步由于等式1可以快速链接大量样本，我们证明，只需几次递归，就可以获得一个有意义的小部分集合，并且恢复的可能性非常高第一个邻居1汞月亮2金星地球3地球火星4月亮火星5火星月亮6木星土星7土星木星8天王星海王星9海王星天王星0001100000010000000101100001010100001011000000000001000000010000000000010000000108937算法1建议算法1：输入：样本集S={1，2，···，N}，S∈RN×d，其中N为样本总数，每个样本点由d个属性或特征维度表示2：输出：分割集L={Γ1，Γ2，· · ·，ΓL}，其中每个分割Γi={C1，C2，···，CΓi|CI >CΓi+1<$i∈L}是S的一个有效聚类.3：FINCH算法：4：计算第一邻居整数向量κ1∈RN×1通过精确距离或快速近似最近邻方法.5：给定κ1，通过等式1得到具有CΓ1簇的第一分区Γ1。CΓ1是在部分Γ1中的簇的总数。6：当在Γi中至少有两个簇时，7：给定输入数据S及其分区Γi，计算clus。TER意味着（聚类中所有数据向量平均值）。准备新的数据矩阵M={1，2，···，CΓi}，其中MCΓi×d。第八章：计算第一邻整数向量κ1∈RCΓi×1M中的点。9：给定κ1，通过等式1得到Γi的分区ΓM，其中ΓM⊇ Γi十：如果ΓM有一个簇，则11：休息12：其他13：更新Γi中的聚类标签：ΓM→Γi14：如果结束15：结束while精确的地面实况聚类或非常接近它的分区。由于仅通过使用第一整数N个邻居索引，我们可以产生C聚类Hiquery，我们将我们的算法称为（FINCH）。FINCH算法所提出的算法的主要流程是直接的。在计算出第一个partition之后，我们希望递归地合并这些集群。为此，等式1需要这些集群中的每一个的第一邻居。找到这些邻居需要计算集群之间的距离。这也与所有的链接方法有关，例如，分层聚集交互聚类中的平均链接使用两个聚类中所有点之间的成对距离的平均值。然而，在此之后，计算上非常昂贵，时间复杂度为O（N）。因此，它不能容易地扩展到数百万个样本，并且它需要保持完整的距离矩阵在记忆里使用我们的方法，对于大规模数据，我们不需要计算完整的成对距离矩阵，因为我们可以通过快速近似最近邻方法（如k-d树）获得第一邻居。相反，我们对每个聚类中的数据样本进行平均，并使用这些均值向量算法2所需群集数模式1：输入：样本集S={1，2，···，N}，S∈RN×d，以及来自算法1的输出的分区Γi。2：输出：用所需数量的簇划分r3：对于步长=Cri-Crdo4：给定输入数据S及其分区Γi，计算clus。TER意味着（聚类中所有数据向量平均值）。准备新的数据矩阵M={1，2，···，CΓi}，其中MCΓi×d。第五章：计算第一邻整数向量κ1∈RCΓi×1M中的点。6：给定κ1，计算等式1的邻接矩阵7：A（i，j）= 1保持一个具有最小距离d（i，j）的对称链路A（i，j），并将所有其他链路设置为零.8：更新ri中的聚类标签： 合并对应（i，j）簇第九章： 端计算第一个邻居。这简化了计算，并保持复杂度为O（Nlog（N）），因为我们在每次递归时合并这些集群与标准HAC算法相比，我们的聚类方程直接提供了一个平均值-在每次迭代中对数据进行有效分区。它提供了一个分层结构，作为一个小的分区集，其中每个连续的分区是前面分区的超集得到的分区集提供了对所发现的数据分组的从细到粗的视图完整的算法步骤在算法1中描述。概述的过程的质量在不同大小的不同数据的实验部分中得到了证明。我们表明，它的结果是非常接近的地面真相集群的分区。对于某些应用程序，通常需要获得特定数量的数据聚类。由于我们的算法返回一个层次树，我们可以使用简单的机制来细化一个封闭的分区，一次一个合并，以提供所需的集群。然而，FINCH返回，所需的集群数量显然是由第一个分区的大小限定的对于完备性，我们在算法2中概述了一个简单的过程。为了更清楚，我们在图中展示了概述的FINCH算法的质量。2使用经典的2D Gestalt [41]和Aggregation [14]数据，这些数据代表了很好理解的聚类问题，并提供了对聚类方法性能的良好定性研究。在运行FINCH算法1之后，我们获得了一组聚类部分。在这里，为了在真实聚类上评估FINCH，我们可以采取比真实聚类更大的分区，并使用Algo2对其进行优化。例如，在具有399 2D的完形数据上点，Algo1提供具有{91，23，5和2}簇的总共4个分区我们使用Algo2对23个聚类分区进行地面真实评估6个聚类。显然，我们可以观察到8938K均值：88%光谱：81% HAC：92% SSC：74%FINCH：98%Kmeans [1]：72%光谱[27]：75% HAC [37]：73% SSC [11]：67%FINCH：85%图2.可视化聚合[14] 7个集群（顶部）和完形[41] 6个集群（底部），每种方法的NMI评分FINCH很好地维护了合并，并且比考虑的基线更好地聚类这些数据。4. 实验我们在具有挑战性的数据集上展示了FINCH，这些数据集涵盖了生物数据，文本，数字，面部和对象等领域。我们首先介绍了数据集和聚类度量，然后通过所提出的方法的算法，估计自动使用超参数设置的集群进行彻底的比较我们还在第4.2节中比较了FINCH与最先进的深度聚类方法。数据集。数据集总结见表1。不同数据集中数据的维数从77到4096不等小鼠蛋白质[16]包括在8类对照和三体基因型中测量的77种蛋白质的表达水平，可从[32]获得。REUTERS[22]由800000篇路透社新闻专线文章组成。我们使用了从[38]中获得的10000篇文章的样本子集，分为四类。TF-IDF特征具有2000维。STL-10[8]是一个用于无监督学习的图像识别数据集BBTs 01（第1季，第1至6集）和BFs 05（第5季，第1至6集）是具有挑战性的视频人脸识别/聚类数据集。 他们是情景喜剧与小演员名单，对于BBTs01：5个主要演员，和BFs05：6主要演员BBTS 01和BFS 05的数据由[3]提供MNIST [21]：我们使用MNIST手写体的三种变体-十位数，它们包括：10 K测试集（MNIST 10 k）、70 K（训练+测试）（MNIST 70 k）和8.1M [24]（MNIST8 M）样本分为10类。我们对STL-10、BBTs 01、BFs05使用CNN特征，对MNIST数据集使用CNN特征和有关使用的功能和数据集设置的更多详细信息，请参见补充资料。评估指标。我们使用最常用的聚类评价指标归一化互信息（NMI）和无监督聚类精度（ACC）作为评价聚类质量的指标。AC其中L1是基础事实标签，C1是通过该方法获得的聚类分配，并且m在聚类和标签之间的所有可能的一对一映射中的范围内。基线。我们比较FINCH现有的聚类方法（包括经典和最近的建议），涵盖了整个频谱的代表聚类方向。我们包括11个基线，分类为聚类算法的两种变体：（1）在给定某些输入超参数/阈值设置的情况下，自动估计聚类数的算法。这些算法包括亲和传播（AP）[13]，Jarvis-Patrick（JP）[17]，秩序（RO）[44]和最近提出的鲁棒连续聚类（RCC）[32];以及（2）需要聚类数量作 为 输 入 的 算 法 。 这 些 算 法 是 ： Kmeans ++（Kmeans）[1]、Birch（BR）[42]、Spectral（SC）[27]、稀疏子空间聚类（SSC）[11]、具有ward链接的层次聚集聚类（HAC Ward）[37]和具有平均链接的HAC（HAC Avg）以及最近的方法多视图低秩稀疏子空间聚类（MV-LRSSC）[4]。补充资料中提供了基线的参数设置。4.1. 与基线的比较小规模数据集的比较：在本节中，我们考虑对多达70k个样本的数据集进行聚类。考虑到BBTS 01（199k）样本的大小，全距离矩阵占用约148 GB RAM。存储器不同算法的消耗不是线性的而是指数的，并且样本数量和特征维度参数负面地影响它们的时间效率和计算成本。出于这个原因，我们将需要存储二次内存使用的算法分开。对需要计算全距离矩阵的算法进行了评价在本节中：小规模（≤70k：36.5 GB），而大规模（≥199k：148 GB）单独评估。在表2中，我们将FINCH的性能与目前的聚类方法。数据集上的结果：MICE蛋白，路透社，STL-10，MNIST 10 k和MNIST 70 k在表2中使用匪I测量报告。 我们比较nmax1{li=m（ci）}[38，15，18]并计算为i=1M n针对FINCH的算法，需要、8939小鼠蛋白路透社STL-10BBTs01 BFs05MNIST类型生物文本对象面临数字#C84105 610#S107710k13k199346 20625410k70k8.1MDim.77200020482048 20484096/7844096/784256/784LC/SC（%）13.88/9.7243.12/8.1410/1033.17/0.633 9 . 9 8 /0.6111.35/8.9211.25/9.0111.23/9.03表1.实验中使用的数据集#S表示样本的数量，#C表示类/聚类的真实数量，最大类（LC）/最小类（SC）是给定数据的类平衡百分比数据集True #C #S小鼠蛋白51.6459.1055.991.7565.9242.6640.3955.1351.3537.6541.9451.31估计#C86730238881077路透社44.8836.2322.9736.7628.3241.7538.777.9738.4012.383.1941.27估计#C41073165699373584410kSTL-1085.0557.1851.7033.3781.5685.5980.972.6280.952.5781.2574.44估计#C105894780435814101013kMNIST 10k97.5569.9735.9749.8777.7481.9280.7897.4389.0563.8696.6393.67估计#C101165139950149101010kMNIST 70k98.84−24.204.0186.5981.0284.5098.7787.6147.08−−估计#C10−5722531120101070k表2. FINCH的小规模聚类结果，使用精确距离获得最近邻。我们将FINCH与自动估计聚类的算法进行比较-给定输入超参数/阈值，以及需要#聚类作为输入的算法对于需要聚类数量作为输入的算法，我们使用FINCH估计的#clusters−表示内存不足集群作为输入：Kmeans、BR、SC、HAC、SSC和MV-LRSSC。为了与这些算法进行公平的时间比较，我们还计算用于获得第一邻居的完整的成对距离矩阵为了证明FINCH所做的合并的质量，我们使用FINCH估计的聚类作为这些算法的输入。在这些数据集上，FINCH已经将地面实况聚类估计为其分区之一，参见图3和第5节中的讨论。为了与给定一些超参数（AP、JP、RO和RCC）提供固定平坦划分的算法进行比较在这里，我们遵循以前的方法[28，32，33]，这些方法倾向于仅基于NMI测量进行比较，而不是基于估计的聚类数量在表2中，按照相同的程序，我们简单地评估了每个方法的最佳参数设置下我们观察到，FINCH不仅能找到有意义的数据分区，而且在大多数数据集上都能始终如一地实现高性能。大规模数据集的比较：由于FINCH只需要第一近邻索引，对于大规模数据集，我们使用[ 26 ]中的随机k-d树算法获得第一近邻，从而避免了昂贵的O（N 2）距离矩阵计算成本和二次记忆存储. 例如，计算单精度MNIST 8M的全距离矩阵需要244416.3 GBRAM。在我们考虑的所有基线中，只有Kmeans和RCC能够扩展。我们在BBTs01和BFs05数据集上将FINCH与Kmeans和RCC进行关于百万表3. BBTS 01和BFS 05（约200k）。数据集NMIFinchKmeansMNIST 8M CNN（@Estim.#C=13）96.5593.33MNIST 8M CNN（@True #C=10）99.54 97.39MNIST 8M PIXELS（@Estim. #C=11） 46.4940.17MNIST 8 M像素（@True #C=10）63.84 37.26表4. MNIST 8M（8.1M）。规模（810万个样本）MNIST 8M数据集，我们只能运行Kmeans。对于BBTS 01和BF 05，存在大量的工作，从利用视频级约束[34]到通过MRF [43]的动态聚类约束，以及最新的基于链接的聚类[19]。与这些工作相比，我们使用来自其他数据集上的预训练模型的特征，而没有任何数据特定的传输或考虑任何其他视频级别的聚类约束。FINCH在这些数据集上与以前发表的方法相比表现得更好这些比较结果可在补充资料中找到。表3中的结果和表5中的运行时间表明，使用近似最近邻，FINCHNMI评分自动估计#C的算法@FINCH估计#C芬奇APJPRORCCKmeansBRSCHAC病房HAC平均值SSCMV-LRSSC公司简介估计#C82.4646.707 52371.857BFs05（@True#C=6）83.64 −76.15NMI数据集芬奇RCCKmeansBBTs0189.792.5671.82估计#C676BBTs01（@True#C=5）91.57−83.398940数据集#S迪门芬奇Kmeans SCHAC病房 HAC平均值AP JP RO BR RCCSSCMV-LRSSC小鼠蛋白10777737ms115ms 220ms40ms668ms700Ms00：01 00：02 90ms 84ms00时08分00：02路透社10k2000 00时05分00时18分 五点五十四分00：3100：4301时53分2019 - 01 - 15 00：00：00时间01：27：3652：53STL-1013k2048 00：0300时19分 08时03分00：4201：1002：422019 - 02 - 15 00：00：0002：41：1402：04：52MNIST 10k 10k4096 上午10时00时19分 02时39分01时05分01：3102：232019 - 01 - 15 00：00：0001：35：2538时42分MNIST 70k 70k4096 00：5402时19分 五十八分四十五秒二十九点二十八分三十分十七秒-2019 -09 - 2200：00：00−−BBTs01199346 2048 01时06分02：17 −−−--−−公司简介206254 2048 01：0901：33 −−−--−−MNIST 8M 8.1M256十八点二十三分56：41 −−−- −−−框架MATLABPython Python MATLAB MATLAB Python MATLABC++PythonPythonMATLABMATLAB表5.FINCH与Kmeans、SC、HAC、AP、JP、RO、BR、RCC SSC和MV-LRSSC的运行时比较我们以HH：MM：SS和MM：SS报告运行时间−表示内存不足。实现了三种方法中最好的运行时间和最好的性能。在表4中可以观察到非常大规模MNIST 8M数据集的类似行为4.2. 深度聚类：无监督学习许多最近的方法提出使用给定的聚类算法作为目标来学习特征表示，或者作为提供弱标签/伪标签用于训练深度模型（通常是自动编码器）的手段[40，38，15，18，6]。FINCH自然适合这项任务，因为它提供了包含自动发现的自然数据分组的分区的层次结构，并且不需要指定用户定义的簇的数目来训练网络。为了证明这一点，并能够与深度聚类方法进行比较，我们采用了一种类似的方法，如最近在[6]中使用的，即使用聚类标签来训练一个小型网络来学习无监督的特征嵌入。我们在MNIST 70 K PIXELS（28 x28 =784-dim），REUTERS-10 kTF-IDF（2000-dim）和STL-10ResNet 50（2048-dim）特征作为输入。请注意，我们使用与以前方法相同的特征来训练它们的嵌入，参见Jianget al。[18 ]第10段。我们训练了一个简单的MLP，其中有两个隐藏层，用于分类模式下在FINCH返回的分区中，在等式1的第一遍或之后的一遍获得的分区包含最大数量的簇，并且也是最纯的，因为后续递归将这些合并我们使用第二个分区的估计聚类作为伪标签，用softmax训练我们的网络。我们逐步进行训练，使用FINCH标签初始化训练，并在20个epoch后重新聚类最后一层嵌入以更新标签。在每个标签更新步骤中，我们将学习率除以10，并训练60-100个epoch。对于所有的实验，我们的网络结构是固定的，两个隐藏层设置为512个神经元。我们使用minibatch SGD训练网络，批量大小为256，初始学习率为0.01。最后一层512维嵌入以这种方式训练，并用于报告在地面实况聚类处的聚类性能如表6所示，FINCH有效地训练了一个无监督的嵌入，在这个学习空间中聚类得更好。有趣的是，在STL-10上，我们有ResNet 50准确度（ACC %）方法MNIST 70k像素路透社-10 KSTL-10GMM [18]53.7354.7272.44AE+GMM [18]82.1870.1379.83VAE+GMM [18]72.9469.5678.86[第38话]84.3072.1780.62IDEC [15]88.0676.05-[18]第十八话94.4679.8384.45FINCH on base功能74.0066.1485.28使用FINCH进行91.8981.4695.248941表6.使用FINCH的无监督深度聚类：与真实聚类的最新深度聚类方法进行比较。特征，FINCH直接聚类这些基本特征，具有更好的准确性，因为比较方法在训练深度模型后实现在我们的FINCH驱动的深度集群之后，我们能够将STL-10上的聚类性能提高到95%，比现有的最先进的深度聚类方法提高了近10%4.3. 计算优点在表5中，我们报告了所有数据集的每个算法的运行时间。相应的定时是算法执行的完整时间，包括计算样本之间的成对距离，或使用kd树获得最近邻居，以及每个算法的运行时间。我们可以观察到，FINCH实现了显著的时间效率，并且不受样本数量和/或特征维度的支配 除了时间效率，FINCH是非常高效的存储器，因为它只需要保持整数（N×1）个第一邻居索引和数据。性能是在配备AMD Ryzen Threadripper 1950X 16核处理器和192（128+64交换）GB RAM的工作站上测量的对于大型数据集超过70k的样本，大多数算法会中断，或者需要超过192 GB的RAM。所以FINCH的内存需求是O（N）vsO（N2）。 该计算机-FinCH的时间复杂度是O（Nlog（N）），而谱方法的时间复杂度为O（N3），基于层次凝聚连接的方法的时间复杂度为O（N2log（N））。5. 讨论我们对FINCH进行了大量不同数据（图像像素、生物测量、文本）的894210710651009080101041031021011000 1 2 34706050403020105 6 7 8 9 10（一）步骤（b）第（1）款集群图3. FINCH步骤/分区和聚类质量。(a)算法收敛：聚类与算法步骤，每个步骤产生一个数据分区。(b)合并质量：每个步骤产生的簇数及其相应的纯度/准确度频率和CNN特征）表示在77到4096维特征空间中。有趣的是，许多现有的流行聚类方法即使在数据在特征空间中具有良好分离的不同聚类的情况下也不能很好地执行。在我们的算法中的递归方案，converges在非常少的步骤，提供一个有效的分区的数据在每一步的指数率。在图3（a）中，我们绘制了FINCH算法每一步获得 的聚类。可 以看到，对 于不同的 数据大小（1077个样本到810万个样本），我们的算法在4-10个步骤中收敛，每个步骤提供一个有效的分区在每个分区处形成的聚类的准确度在图3（b）中描绘。人们可以评估发现的集群和连续合并的质量，因为它在每个步骤中都能很好地保持非常大的合并的准确性。对应于图3（a），图3（b）的x轴描绘了在所有绘制的数据集的算法的每个步骤处获得的#聚类。例如，对于具有1077个样本的最小数据集，FINCH在运行的6个步骤中总共提供6个分区。从1077个样本，在等式1的第一遍中下降到351个聚类，然后在连续递归中下降到106、24、8、4和3个聚类，在算法的步骤4发现8个聚类的真实聚类。对于图3（b）中的其他数据集，可以在FINCH的每个步骤中解释相应的聚类纯度和聚类数量与HAC需要N-1步才能收敛的链接方案，N个样本，FINCH收敛（步数）不取决于N，并由等式1控制。研究这种行为并找到解释这种行为的理论界限是非常有趣的一个有趣的观察结果是表2中MNIST 10k和MNIST 70k数据集的结果。由于这些特征是使用地面实况标签在数据上学习的，因此这些特征已经很好地分离了10特征空间中的聚类。尽管如此，没有一个基线算法（甚至是那些需要指定聚类数量的算法）执行得如此准确。FINCH在第5步（对于MNIST 10k）和第6步（对于MNIST 70k）停止其递归合并，提供精确的10个聚类，准确度超过请注意，这与训练的CNN模型在这些特征上提供的分类精度相同由于地面实况聚类被很好地分离，算法1正好在这里停止，因为这个10个聚类分区的另一个通道将它们合并到1个聚类。这表明FINCH可以很好地恢复数据中的全局结构。我们还包括补充中每个数据集的步骤和相应聚类的数量以及准确性。注意，由于等式1的定义，FINCH不能发现单例（具有1个样本的聚类）。这是因为我们将每个样本与其第一个邻居联系起来，而没有考虑它们之间的距离因此，单例将始终与其最近的样本点配对这为FINCH设置了大小为2的最小集群的限制最后，我们提出了一种算法，从流行的身体的聚类方法，需要保持成对距离矩阵，并需要用户定义的超参数。它以聚类方程的形式提供了一个唯一而简单的解，并提供了一个有效的聚类合并过程。它带来的优势是完全无参数，并且可以以最小的计算费用轻松扩展到大数据，这可能对许多应用程序有用我们已经展示了无监督特征表示学习的一个这样的应用以这种方式自动发现有意义的聚类在许多科学领域都是需要的，因为这些领域对数据的结构一无所知例如，它可能具有非常令人兴奋的应用，从发现奇异粒子到基于它们的光谱的恒星/星系。MNIST_8M_CNN：8MBF 05：206254MNIST_70k：70kMNIST_10k：10kREUTERS：10kMICEProtein：1077MNIST_8M_CNN：8MBF 05：206254MNIST_70k：70kMNIST_10k：10k路透社：10kMICEProtein：1077集群ACC（%）201530569452516137133217291501149369456830189118371753169913623573553513102622201067565535024171310874328943引用[1] 大卫·亚瑟和谢尔盖·瓦西里茨基。k-means++：谨慎播种的优势在ACM-SIAM。工业与应用数学学会，2007年。[2] Maria-Florina Balcan，Avrim Blum和Santosh Vempala。通过相似性函数聚类的判别框架。ACM STOC，2008年。[3] 马丁·巴乌姆、马卡兰德·塔帕斯维和莱纳·圣·伊·埃弗里。多媒体数据中人员识别的带约束的半监督学习CVPR，2013。[4] Maria Brbic和Ivica Kopriva。多视点低秩稀疏子空间聚类。模式识别，2018年。[5] 巴 斯 蒂 安 · 布 贝 克 和 乌 尔 里 克 在 勒 克 斯 堡 。NearestNeighborclustering最近邻聚类：一种用于任意目标函数的一致聚类的基线方法。JMLR，2009年。[6] Mathilde Caron，Piotr Bojanowski，Armand Joulin，andMatthijs Douze.用于视觉特征的无监督学习的深度聚类在ECCV，2018。[7] Moses Charikar和Vaggos Chatziafratis。基于稀疏分割和扩散度量的近似拓扑聚类。在ACM SIAM，2017年。[8] Adam Coates，Andrew Ng，and Honglak Lee.无监督特征学习中单层网络的分析。载于AISTATS，2011年。[9] Vincent Cohen-Addad ， Varun Kanade ， and FrederikMallmann-Trenn.最坏情况下的层次聚类。在NIPS，2017年。[10] 桑乔伊·达斯古普塔基于相似性的层次聚类的代价函数在ACM STOC，2016年。[11] Ehsan Elhamifar和Rene Vidal。稀疏子空间聚类：算法、理论与应用。PAMI，2013年。[12] Brian S Everitt，Sabine Landau，Morven Leese和DanielStahl。聚类分析，第五版。Wiley-Blackwell，2011年。[13] 布兰登·J·弗雷和德尔伯特·杜克。通过在数据点之间传递消息进行聚类。Science，2007.[14] Aristides Gionis ， Heikki Mannila ， and PanayiotisTsaparas.聚类