ROSC：鲁棒谱聚类方法在多尺度数据上的有效性分析

1570ROSC：多尺度数据上的鲁棒谱聚类0Xiang Li �，Ben Kao �，Siqiang Luo �，Martin Ester †0� 香港大学，香港薄扶林道 † SimonFraser大学，加拿大Burnaby � {xli2, kao, sqluo}@cs.hku.hk† ester@sfu.ca0摘要0我们研究了谱方法在聚类多尺度数据中的有效性，即数据的聚类具有不同的大小和密度。我们回顾了现有的用于处理多尺度数据的谱方法，并提出了一种与现有方法正交的替代方法。我们提出了ROSC算法，它计算了一个亲和矩阵，该矩阵同时考虑了对象的特征相似性和可达性相似性。我们在真实和合成数据集上进行了大量实验，将ROSC与其他9种方法进行了比较。我们的结果表明，ROSC在与竞争对手的比较中表现出色。特别是，它非常鲁棒，因为它在所有测试数据集上始终表现良好。此外，它在高度多尺度的数据集上比其他方法表现出更好的性能。0关键词0谱聚类；鲁棒性；多尺度数据0ACM参考格式：Xiang Li �，Ben Kao �，Siqiang Luo �，Martin Ester†。2018年。ROSC：多尺度数据上的鲁棒谱聚类。在WWW2018：2018年网络会议上，2018年4月23日至27日，法国里昂。ACM，美国纽约，10页。https://doi.org/10.1145/3178876.318599301 引言0聚类分析是数据挖掘和机器学习中的核心技术。给定一组对象，聚类的一般思想是将相似的对象分组到同一聚类中，并将不相似的对象分开到不同的聚类中。在现有技术中，谱聚类已被证明非常有效，特别是在图像分割[28,36]和文本挖掘[7]领域。基于谱图理论，谱聚类方法将聚类问题转化为图分割问题。给定一组n个对象X ={x1,...,xn}和一个相似矩阵S，其中矩阵元素Sij捕捉到对象xi和xj的亲和性，谱聚类首先构建一个加权图G = (X,S)，其中X给出顶点集合，Sij给出连接xi和xj的边的权重。然后，图G被分割，目标是优化一个衡量分割质量的准则，如归一化割[28]。0本文发表在知识共享署名4.0国际许可证(CC BY4.0)下。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW2018，2018年4月23日至27日，法国里昂，© 2018IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可证发布。ACM ISBN978-1-4503-5639-8/18/04.. https://doi.org/10.1145/3178876.31859930相似矩阵S0图拉普拉斯矩阵L0特征向量0k-means0相似矩阵S0图拉普拉斯矩阵L0k-means0局部缩放相似矩阵0伪特征向量0相似矩阵S0图拉普拉斯矩阵L0特征向量0k-means0局部缩放相似矩阵0伪特征向量0TKNN图0修正的相似矩阵Z0(a)0(b)0(c)0PI0图1：(a)基本谱聚类的关键步骤；(b)带有局部缩放和PI的谱聚类；(c)ROSC0（a）数据集（b）NJW0图2：（a）一个多尺度数据集，（b）NJW聚类0图1(a)展示了基本谱聚类的关键步骤1。给定相似性矩阵S，我们首先从S计算出一个归一化的拉普拉斯矩阵L。然后，我们对L进行特征分解，得到k个最小的特征向量e1,...,ek。令M为一个k×n的矩阵，其第i行是ei。我们将M的第j列作为对象xj的特征向量，并对这些对象进行k均值聚类。简而言之，谱聚类方法使用k个最小的特征向量将对象映射到低维嵌入空间。尽管谱聚类取得了成功，但之前的研究指出谱方法在存在多尺度数据[24,37]时可能受到不利影响。多尺度数据被定义为01谱聚类方法有许多变体。我们这里的描述是基于NJW方法[26]的。更多细节将在第2节中介绍。2我们说一个特征向量ei小于另一个特征向量ej，如果ei的特征值小于ej的特征值。0Track: Intelligent and Autonomous systems on the Web WWW 2018, April 23-27, 2018, Lyon, France1580其对象簇具有各种大小和密度。作为一个说明性例子，图2(a)显示了一个包含三个簇的数据集：两个位于狭窄稀疏条纹簇上方的密集矩形簇。图2(b)显示了将标准谱聚类方法NJW应用于数据集的结果。我们可以看到，条纹簇被分割成了三个部分，其中两个部分与矩形簇错误地合并在一起。本文的目标是解决谱聚类中的多尺度数据问题。特别地，我们回顾了处理多尺度数据的现有方法，提供了解决这个问题的见解，并提出了我们的算法ROSC，它在聚类多尺度数据方面优于现有方法。解决多尺度数据问题有两种一般方法：一种是对相似性矩阵S进行缩放，另一种是应用幂迭代技术获得包含丰富簇分离信息的伪特征向量。回顾谱聚类方法将数据对象建模为图，并通过图分割进行聚类。因此，相似性矩阵S应该捕捉到对象的局部邻域信息。这样一个相似性函数的常见选择是02σ2，其中x（粗体）表示对象x的特征向量，σ是全局缩放参数。使用高斯函数对多尺度数据进行聚类的一个主要困难在于选择σ的值。如果σ设得很小，那么Sij将变小。稀疏簇中的对象（相对于密集簇中的对象而言，它们之间的距离较远）可能会被判断为不相似，导致簇的分割。另一方面，如果σ设得很大，Sij将变大。因此，附近的密集簇可能会被判断为相似，并且会被错误地合并。为了解决这个问题，ZP方法[37]应用了局部缩放0并将高斯相似度修改为Sij = exp(−||xi−xj||2)0σiσj0。0在这里，σi（以及σj）是对象xi的局部缩放参数。它被定义为xi与其第l个最近邻之间的距离，其中l是某个经验确定的值。如果xi位于一个稀疏的簇中，那么σi将会很大。这增加了xi和其相邻对象的相似性，从而避免了稀疏簇的分裂。另外，如果xi位于一个密集的簇中，σi将会很小。对象必须非常接近才能被视为相邻。这避免了附近密集簇的合并。之前的研究[1,35]表明，在处理多尺度数据时，使用比k个最小的特征向量更多的特征向量可以帮助捕捉更多的簇分离信息，从而改进谱聚类。一种称为幂迭代（PI）方法[27]被提出作为计算矩阵的主特征向量的高效方法。在[19]中观察到，可以截断迭代过程以获得一个中间的伪特征向量vt。研究表明，vt表示所有特征向量的加权线性组合，因此是标准谱聚类过程中通常使用的k个最小特征向量的非常有效的替代品。图1(b)展示了局部缩放方法（绿色框）和幂迭代方法（黄色框）如何集成到基本谱聚类方法中。本文采用了一种不同的方法来解决多尺度数据问题。核心思想是构建一个n×n系数矩阵0矩阵Z的条目Zij3反映了一个对象xi如何表征另一个对象xj的程度。我们的目标是得到这样一个具有“分组效应”的Z：如果两个高度相关的对象xi和xj（因此应该放入同一个聚类中），那么它们在Z中的对应系数向量zi和zj是相似的。我们要解决的有趣问题是如何找到这样一个Z。我们算法ROSC的主要特点如图1(c)中所示的红色框所示。ROSC不使用PI来获得对象的低维嵌入作为k-means的输入（图1(b)中的黄色框），而是使用嵌入来构建矩阵Z（红色框中的上路径）。我们注意到，属于同一个聚类的两个对象可能位于一个聚类的远端，它们的高相关性因此不能通过基于距离的相似性矩阵S来正确表达。为了捕捉同一聚类中远距离对象之间的高相关性，我们提出使用传递K最近邻（TKNN）图（红色框中的下路径）。如果存在一个对象序列，其中序列中的相邻对象是彼此的互相K最近邻，则对象xi和xj通过TKNN图相连。我们使用TKNN图来规范矩阵Z，使其具有所需的分组效应。然后将矩阵Z输入到谱聚类的流程中，取代相似性矩阵S的作用。我们的主要贡献包括：•我们解决了谱聚类中的多尺度数据问题，并提出了ROSC算法。ROSC使用PI来得到一个系数矩阵Z，该矩阵由TKNN图规范化。规范化的Z取代了谱聚类过程中的相似性矩阵S。•我们在数学上证明了规范化的Z具有分组效应。因此，它在改善聚类结果方面是有效的。•我们进行了大量实验来评估ROSC与其他9种聚类方法的性能。我们的结果表明，ROSC在与竞争对手的比较中表现得非常好。特别是，它在所有测试数据集上都表现出色，非常稳健。此外，对于高度多尺度的数据集，它比其他方法表现出更大的优势。本文的其余部分组织如下。第2节介绍相关工作并描述了一些关键的谱聚类算法。第3节介绍ROSC算法。第4节描述实验并呈现实验结果。最后，第5节总结本文。02相关工作0谱聚类是一个经过深入研究的主题。有关该方法的介绍和分析，请参见[13, 26,31]。基本方法有许多变体，其中一些在归一化图拉普拉斯矩阵D - S方面有所不同，其中D是对角矩阵，Dii = ∑jSij。例如，归一化割（NCuts）方法[28]使用基于随机游走的归一化D - 1（D -S），而Ng-Jordan-Weiss（NJW）方法[26]使用对称归一化D - 1。02。有许多先前的研究研究了谱聚类技术的各个方面。例如，有研究专注于谱聚类在不同数据特征下的性能[12, 32, 38]，计算效率[3, 4,6, 8, 9, 34]，以及方法的概率理论[15, 23, 25]。0给定一个矩阵M，我们使用一对下标来指定M的一个条目。0Track: Intelligent and Autonomous systems on the Web WWW 2018, April 23-27, 2018, Lyon, Francevt+1 =WvtWvt1,t ≥ 0.(1)v0 = c1e1 + c2e2 + ... + cnen,(2)=+++ nn= (c1λt1e1 + c2λt2e2 + ... + cnλtnen)/R=c1λt1Re1 + c2c1�λ2λ1�te2 + ... + cnc1�λnλ1�ten .(3)1590还有一些作品指出，当数据是多尺度[24]或嘈杂[17]时，谱聚类的有效性会降低。为了解决这些问题，已经提出了一些方法[2, 5, 17,37]。例如，自调谱聚类方法ZP[37]考虑了每个对象的局部统计信息，并构建了一个局部缩放的相似性矩阵，如我们在第1节中所述。此外，ZP通过将特征向量旋转到与规范坐标系最佳对齐的位置来估计聚类的数量。然后选择给出最小对齐成本的聚类数。标准谱聚类使用所谓的“最具信息量”的特征向量。从启发式的角度来看，通常将k个最小特征向量视为最具信息量的特征向量。然而，[19]指出，这些最小特征向量中的一些可能对应于数据中的一些特别显著的噪声，而其他非最小的向量则包含良好的聚类分离信息。这一观察引发了对谱聚类中如何选择特征向量的研究。例如，Xiang等人[33]通过测量特征向量在将数据分成不同聚类时的相关性来增强谱聚类，特别是在存在噪声的情况下。正如我们在第1节中提到的，幂迭代（PI）可以用来在谱聚类中找到伪特征向量。给定一个矩阵W，PI从一个随机向量v0开始迭代：0假设 W 具有特征值 λ 1  >  λ 2  > ... >  λ n，并具有相关的特征向量 e 1 ，e 2 ，...，e n 。我们将 v 0 表示为0其中 c 1 ，...，c n 是一些常数。令 R = � t − 1 i = 0 ∥ W v i  ∥1 ，我们有0v t  因此是特征向量的线性组合。此外，如果 v 0 在 e 1 的方向上有一个非零分量（即 c 1 ≠0），v t 收敛到主特征向量 e 1 的一个缩放版本。在谱聚类的背景下，我们设置 W = D − 1S。很容易看出，在NCuts中计算的 D − 1 ( D  − S ) 的 k 个最小特征向量等价于 W 的 k个最大特征向量。Lin等人[19]提出了功率迭代聚类（PIC）方法。PIC使用截断的幂迭代来获得一个中间伪特征向量 v t ，它被证明是所有特征向量的加权线性组合。v t 的第 j 个分量，vt [ j ]，被视为对象 x j 的特征。基于这些特征值，应用 k均值聚类来对对象进行聚类。PIC使用PI从中提取对象的特征值来获得一个单一的伪特征向量。然而，当聚类数目较大时，单个伪特征向量通常是不够的，因为会出现聚类冲突问题[18]。在[18]中，提出了PIC-k方法，它多次运行PI来获得多个伪特征向量。这些生成的伪特征向量提供了对象特征的更多维度，用于谱聚类中的k均值聚类步骤。然而，这些伪特征向量可能相互相似，因此是冗余的。在[29]中，提出了基于缩放因子的功率迭代聚类（DPIC）方法来解决冗余问题。DPIC应用舒尔补充生成多个正交伪特征向量以解决冗余问题。PIC方法的另一个问题是，主导特征向量在伪特征向量中贡献更高的权重（参见方程3）。它们因此掩盖了其他次要但不可或缺的特征向量，特别是在多尺度和噪声数据的情况下。为了解决这个问题，Huang等人[11]提出了多样化的功率迭代嵌入（DPIE）方法。在DPIE中，当生成一个新的伪特征向量时，会从新的伪特征向量中删除其他先前获得的伪特征向量的信息。此外，还明智地设置了一些阈值，以防止次要特征向量被掩盖。最近，提出了一种全谱聚类方法FUSE[35]。它首先生成 p > k个伪特征向量，然后使用独立成分分析（ICA）来旋转伪特征向量，使它们成为两两统计独立的。选择具有最大聚类分离信息的 k个旋转伪特征向量进行聚类。我们的算法ROSC在两个方面与这些先前的工作不同。首先，ROSC使用PI获得伪特征向量，而不是作为k均值聚类步骤的输入，而是构建一个系数矩阵Z，该矩阵表示一个对象如何由其他对象表征。其次，我们提出了TKNN图，它是从局部缩放相似性矩阵S导出的。TKNN图用于规范矩阵Z，使得Z具有分组效应。矩阵Z作为输入替代原始相似性矩阵S进入谱聚类流程。ROSC因此与谱聚类的其他现有技术正交。0谱聚类的k均值聚类步骤中使用的对象特征的更多维度。然而，这些伪特征向量可能相互相似，因此是冗余的。在[29]中，提出了基于缩放因子的功率迭代聚类（DPIC）方法来解决冗余问题。DPIC应用舒尔补充生成多个正交伪特征向量以解决冗余问题。PIC方法的另一个问题是，主导特征向量在伪特征向量中贡献更高的权重（参见方程3）。它们因此掩盖了其他次要但不可或缺的特征向量，特别是在多尺度和噪声数据的情况下。为了解决这个问题，Huang等人[11]提出了多样化的功率迭代嵌入（DPIE）方法。在DPIE中，当生成一个新的伪特征向量时，会从新的伪特征向量中删除其他先前获得的伪特征向量的信息。此外，还明智地设置了一些阈值，以防止次要特征向量被掩盖。最近，提出了一种全谱聚类方法FUSE [35]。它首先生成 p > k个伪特征向量，然后使用独立成分分析（ICA）来旋转伪特征向量，使它们成为两两统计独立的。选择具有最大聚类分离信息的 k个旋转伪特征向量进行聚类。我们的算法ROSC在两个方面与这些先前的工作不同。首先，ROSC使用PI获得伪特征向量，而不是作为k均值聚类步骤的输入，而是构建一个系数矩阵Z，该矩阵表示一个对象如何由其他对象表征。其次，我们提出了TKNN图，它是从局部缩放相似性矩阵S导出的。TKNN图用于规范矩阵Z，使得Z具有分组效应。矩阵Z作为输入替代原始相似性矩阵S进入谱聚类流程。ROSC因此与谱聚类的其他现有技术正交。03 算法0在本节中，我们描述了我们的ROSC算法。图1(c)显示了ROSC的流程图。ROSC遵循谱聚类的基本流程，只是它生成一个系数矩阵Z，并将其代替相似度矩阵S输入到聚类流程中。目标是找到具有分组效果的Z。为了实现这一点，ROSC使用PI从伪特征向量中获取Z的基本值。接下来，它生成TKNN图，用于修正Z。接下来，我们讨论如何从伪特征向量中获取Z，定义TKNN图，描述修正过程，并证明得到的Z具有所需的分组效果。0伪特征向量0给定相似度矩阵S，我们通过D−1S进行归一化，并应用PI来获取伪特征向量。与[35]类似，我们使用不同的随机初始向量多次运行PI，生成一组伪特征向量，将每个对象映射到低维嵌入中。注意，PI会收缩小的特征向量[19]。为了减轻小特征向量的收缩，我们采用[11]的方法，并随着获得更多的伪特征向量逐渐减少PI中执行的迭代次数。0论文题目：智能和自主系统在Web上的应用 WWW 2018，2018年4月23日至27日，法国里昂X = XZ + O.(5)minZ||X − XZ ||2F + α1||Z ||2F + α2||Z − W||2F ,(6)xixjZipZjp01pn.,∀1 ≤ i,p ≤ n.(8)2α1Z∗ip + 2α2(Z∗ip − Wip) = 0, which induces Equation 8.□|Z∗ip − Z∗jp | ≤ c(1 − r) + α2|Wip − Wjp |α1 + α2,(9)1 + α2||wp ||22 and r = xTi xj.1600由于伪特征向量近似最主要的特征向量，它们可能相似。为了减少这种冗余，使用白化[14]使伪特征向量不相关。此外，通过修正过程减少伪特征向量中的噪声，稍后将对此进行讨论。0传递K最近邻图0我们的目标是捕捉属于同一簇的对象之间的高相关性，即使这些对象可能位于簇的远端。这些相关性通过TKNN图来表达，该图用于规范系数矩阵Z。0定义1.（互K最近邻）设NK(x)是对象x的K个最近邻的集合。如果xi∈NK(xj)且xj∈NK(xi)，则称xi和xj是彼此的互K最近邻。0定义2.（可达性）如果存在一系列h≥2的对象{x1=xa1,...,xah=xj}，使得对于1≤r  0，α 2  ≥0是两个权重因子，用于调整构成目标函数的三个分量的相对权重。目标函数由三个项组成。第一项旨在减少噪声矩阵O（参见方程5），第二项是Z的Frobenius范数，第三项通过TKNN图对Z进行正则化。优化问题的闭合解Z�为：0Z� =  ( X T X  +  α 1 I  +  α 2 I ) − 1 ( X T X  +  α 2 W ). (7)0分组效应0对于一个对象x p ，令z p 为系数矩阵Z的第p列。我们将z p的条目解释为将x p表示为其他对象的线性组合的系数。之前的研究[10, 21,22]表明，如果Z具有分组效应，则基于Z的谱聚类将是有效的。直观地说，如果两个高度相关的对象x i 和x j，它们对其他对象的表征相似，则Z具有分组效应。现有的工作主要将对象之间的高相关性视为特征向量的高相似性。在ROSC中，我们将对象的相似性考虑为特征相似性和可达性相似性。特征相似性通过对象的特征向量来衡量，如矩阵X的列所示。可达性相似性通过矩阵W的列来衡量，每个列显示一个对象到其他所有对象的可达性。形式上，0定义4.（分组效应）。给定一组对象X = {x 1 , x 2 , ..., x n}，令w q为W的第q列。进一步，令x i  →  x j 表示条件：（1）x T i x j  →1，（2）∥w i  −  w j  ∥ 2  →  0。如果矩阵Z具有分组效应，则有：0我们的下一个任务是证明最优解Z�（如方程7所给出）具有分组效应。在接下来的讨论中，我们用z� q 表示Z�的第q列向量。0引理5. 给定一组对象X，矩阵X ∈Rp×n由伪特征向量组成，可达性矩阵W，以及方程6的最优解Z�，0Z� ip = x T i ( x p  −  X z � p )  +  α 2 Wip0证明. 对于1  ≤  p  ≤  n，令J(z p ) = || x p  −  X z p  || 2 2 +  α 1 || z p  || 2 2 + α 2 ||z p  −  w p  || 2 2。由于Z�是方程6的最优解，我们有∂ J0引理6. � 1  ≤  i ,  j , p  ≤  n，0其中c = �0证明。根据方程8，我们有0Z�ip−Z�jp = (xi−xj)(xp−Xz�p) + α2(Wip−Wjp)0α1 + α2。0Track：智能和自主系统在Web WWW 2018上，2018年4月23日至27日，法国里昂(10)1610这意味着0|Z�ip−Z�jp| ≤ |(xi−xj)(xp−Xz�p)| + α2|Wip−Wjp|0α1 + α20≤ ||xi−xj||2||xp−Xz�p||2 + α2|Wip−Wjp|0α1 + α20由于矩阵X的列向量已经归一化（即xiTxqxiq=1�1≤q≤n），我们有||02(1−r)，其中r = xiTxj。由于Z�是方程6的最优解，我们有0J(z�p) = ||xp−Xz�p||22 + α1||z�p||22 + α2||z�p−wp||220J(0) = ||xp||22 + α2||wp||22 = 1 + α2||wp||22. (11)01 + α2||wp||22 = c。方程10可以进一步简化为0|Z�ip−Z�jp| ≤ c02(1−r) + α2|Wip−Wjp|0α1 + α2。0□0引理7. 矩阵Z�具有分组效应。0证明。给定两个对象xi和xj，使得xi→xj，我们有，(1)xiTxj→1和(2)||wi−wj||22→0。这意味着r =xiTxj→1和|Wip−Wjp|→0。因此，方程9右侧的分子的两个项接近于0。因此，|Z�ip−Z�jp|→0，从而Z�具有分组效应。□0事实上，方程9展示了我们的算法ROSC如何增强多尺度数据上谱聚类的有效性。与传统方法相比，传统方法侧重于特征相似性，ROSC使用Z�将特征相似性（r）与可达性相似性（|Wip−Wjp|）进行整合。特别地，一个簇中的两个远离的对象xi和xj可能没有很强的特征相似性。这导致r较小，传统方法很可能将它们放入不同的簇中。相反，ROSC考虑对象的强可达性，得到|Wip−Wjp|的较小值，从而将它们保留在同一个簇中。此外，对于属于两个不同密集簇但在空间上接近的xi和xj（即xi和xj具有很强的特征相似性），传统方法可能会错误地将它们合并到同一个簇中。然而，ROSC通过发现它们的低可达性（通过互KNN关系）并得到|Wip−Wjp|的较大值来调整矩阵Z�0并避免了错误的合并。正如我们将在下一节中看到的，ROSC的方法极大地提高了聚类质量，并且在处理多尺度数据时比其他算法更加鲁棒。0我们注意到矩阵Z�可能是非对称的，它可能包含负值。为了构建对象相似性矩阵，一种常见的修复方法[20，22]是计算˜Z = (|Z�| +|(Z�)T|)/2。计算完˜Z后，ROSC使用˜Z作为相似性矩阵（代替S）执行标准的谱聚类方法（例如NCuts）。可以证明|Z�|，|(Z�)T|和因此˜Z都具有分组效应。由于篇幅限制，读者可以参考[16]中的证明。最后，ROSC的算法1总结如下。0算法 1  ROSC0输入：S，k。输出：C = {C1，...，Ck}1：计算TKNN图和可达性矩阵W 2：计算W = D−1S，其中Dii =�jSij 3：在W上应用PI并生成p个伪特征向量{vr}pr=1 4：X ={vT1;vT2;...;vTp}；X = whiten(X)05:将X的每个列向量x归一化，使xTx = 1 6:通过公式7计算系数矩阵Z�7:构造˜Z = (|Z�| + |(Z�)T|) / 28:运行标准谱聚类方法，例如NCuts，以˜Z作为相似性矩阵获得聚类C ={Cr}kr=1 9:返回C = {C1, ..., Ck}04 实验0我们进行了大量实验来评估ROSC的性能。本节总结了我们的结果。我们使用三个常用指标进行各种方法的比较，即纯度、调整互信息（AMI）和兰德指数（RI）。这些指标评估聚类质量，其值范围从0到1，较大的值表示更好的聚类质量。有关这三个指标的定义，请参阅[19, 30]。04.1 用于比较的算法0我们评估了ROSC和其他9种方法。这些方法分为以下四类。•（标准谱聚类方法）：NCuts和NJW是我们对比ROSC的两种标准方法。•（幂迭代（PI）方法）：这组包括PIC，PIC-k，DPIC和DPIE。它们在第2节中有描述。•（多尺度数据导向方法）：这组包括ZP和FUSE，它们专门处理多尺度数据。它们也在第2节中讨论过。请注意，ZP自动估计簇的数量。为了公平起见，我们修改了ZP，使其返回真实的簇数k。•（ROSC变体）：ROSC使用可达性矩阵对矩阵Z进行正则化。这是通过方程6中的项||Z−W||2F实现的。为了研究正则化效果，我们修改了ROSC，去掉了这个项。具体来说，ROSC-R（读作“ROSC减去可达性”）是没有可达性组件的ROSC。【实验设置】所有方法的参数根据它们原始论文进行设置。对于所有数据集，我们使用对象属性的欧氏距离来得到S，这些距离基于ZP的局部缩放过程进行局部缩放。对于ROSC，我们设置α1 = 1.0，α2 =0.01，并在构建TKNN图时设置K =4。所有方法都采用k-means作为最后一步返回聚类结果。对于这一步，我们随机选择起始质心运行100次k-means，并使用最频繁的聚类分配。对于ROSC，我们生成k个伪特征向量，起始向量是随机选择的，就像[29]中所做的那样。对于每种方法和数据集，我们运行实验50次并报告平均结果。04.2 性能结果0我们首先使用两个合成数据集来直观地说明各种方法的性能。之后，我们使用7个真实数据集对算法进行深入分析。0Track: Intelligent and Autonomous systems on the Web WWW 2018, April 23-27, 2018, Lyon, France1620【合成数据集】合成数据集旨在表示聚类中非常困难的情况，重点关注多尺度数据。图3(a)显示了合成数据集Syn1，它由三个不同大小和密度的簇组成。具体来说，有一个中等大小的稀疏矩形簇（蓝色），夹在一个小的密集圆形簇（品红色）和一个大的密集矩形簇（黄色）之间。这些簇在物理上非常接近。特别是，不同簇的两个对象之间的距离可能比属于同一簇的两个对象之间的距离更小。我们在Syn1上应用了所有10种方法。由于空间限制，对于每个方法类别，我们只显示表现最佳的方法。它们分别是NJW，PIC-k，FUSE和ROSC。它们的聚类结果分别显示在图3(b)-(e)中。从图中可以看出，NJW和PIC-k都能够识别出小的圆形品红色簇。然而，蓝色和黄色的矩形簇被切成了两半，并且这些半部分被错误地合并。FUSE对于这个数据集也失败了。特别地，大约1/3的黄色簇与蓝色簇合并，而大约一半的蓝色簇与品红色簇合并。在这四种方法中，ROSC是唯一能够恢复黄色簇的方法。这表明了TKNN图在关联大型延伸簇两端的对象方面的有效性。此外，虽然ROSC没有恢复完整的蓝色簇，但大多数蓝色对象被ROSC聚类为一个单独的组。相比之下，对于其他三种方法，所有蓝色对象要么与品红色簇的对象合并，要么与黄色簇的对象合并。图4(a)显示了另一个合成数据集Syn2，它由一个稀疏的环形簇（绿色）和两个密集的圆形簇（红色和蓝色）组成。4个类别中表现最佳的方法分别是NJW，PIC-k，ZP和ROSC。它们的聚类结果分别显示在图4(b)-(e)中。从图中可以看出，该数据集对现有方法来说是一个非常困难的情况。例如，使用NJW和ZP，绿色环形簇被分成了三个部分，其中两个部分与圆形簇错误合并。PIC-k也出现了类似的情况。相比之下，ROSC是唯一能够恢复几乎整个绿色簇的方法。它还能够正确识别出两个圆形簇，除了绿色环上的少数对象。表1和表2显示了10种方法在Syn1和Syn2数据集上的纯度、AMI和RI分数。从表中可以看出，ROSC的分数都比其他方法大得多。因此，在这两个困难的情况下，它明显优于其他方法。这两个表还显示了ROSC-R的分数，ROSC-R是ROSC不使用TKNN图或可达性矩阵进行正则化的方法。考虑到ROSC和ROSC-R之间的分数差距很大，我们可以看到可达性正则化的强正面效应。TKNN图和可达性的使用在这两个合成数据集中有显著效果，因为这两个数据集都由大型延伸簇（例如syn2中的绿色环）组成。这些簇中的对象彼此之间的距离很远，它们的相关性被ROSC使用的可达性矩阵有效捕捉到。我们进一步研究了各种方法如何处理多尺度数据，通过改变合成数据集中一些簇的大小和密度。在这里，我们展示一些代表性的结果。0具体来说，我们考虑Syn1中稀疏蓝色中间聚类（图3(a)），并进行两个改变：（1）在保持其大小不变的情况下增加其密度，（2）在保持其密度不变的情况下增加其大小。我们用∆d表示密度的变化（例如，∆d =100%表示聚类的密度增加一倍）。我们通过改变聚类的长度（使聚类变宽），同时保持高度不变来改变聚类的大小。我们用∆s表示大小的变化（例如，∆s =50%表示聚类的宽度是图3(a)中显示的聚类的1.5倍）。我们通过修改环状聚类的密度和大小来对Syn2进行类似的改变。具体来说，我们逐渐减小环的大小，从整个环（�，∆s = 0%）到下半环（�，∆s =-50%）。我们展示了将密度和大小的变化应用于Syn1（图5和图6）和Syn2（图7和图8）中的聚类时的10种方法的性能得分。从图中我们可以看出，ROSC在所有测试案例的整个范围内都表现出最佳和最稳定的性能。ROSC与其他竞争对手之间的性能差距也相当大。这表明ROSC在处理各种大小和密度的多尺度数据时非常稳健。【真实数据集】我们进一步使用7个真实数据集评估这些方法。它们是：MNIST0127（手写数字图像）、COIL20（图像）、Yale_5class（面部图像）、isolet_5class（语音，UCI数据仓库）、seg_7class（图像，UCI数据仓库）、Yeast_4class（生物数据，UCI数据仓库）、glass（UCI数据仓库）。表3总结了这些数据集。对于每个数据集，我们显示对象的数量、维度的数量和聚类的数量。此外，为了显示数据集是否是多尺度的，我们测量每个数据集中每个金标准聚类的大小和密度。具体而言，对于每个聚类，我们找到聚类中任意两个对象之间的最大距离。这个距离被视为聚类的直径，反映了聚类的大小。此外，对于每个聚类，我们找到聚类的所有对象对的平均距离ρ。然后，我们使用1/ρ作为密度的度量。这些聚类的大小和密度在表3的条形图中显示。显示的大小（密度）都是通过将相应数据集的最大（最密集）聚类的大小（密度）归一化到[0,1]范围内来标准化的。直观地说，图表中条形图的变化越大，表示相应的数据集越多尺度。从表3中，我们可以看出数据集COIL20是高度多尺度的。例如，聚类2（最大的聚类）比聚类15（最小的聚类）大5.6倍。然而，聚类15比聚类2密度高5.9倍。数据集glass是中度多尺度的，而Yale_5class相对均匀。数据集seg_7class很有趣，因为它有一个非常大且稀疏的聚类（聚类3）；其他6个聚类相当均匀。表4、5和6显示了10种方法应用于7个真实数据集时的纯度、AMI和RI得分。表中的每一行对应于一个（度量，数据集）组合，或者是10种方法之间的比赛。因此，有21个（3个度量×7个数据集）比赛。对于每个比赛，胜者的得分以粗体显示。对于ROSC，它在每个比赛中的排名在其得分旁边的括号中给出。可以通过跨越三个表的方法下的列来判断方法的性能。从表中，我们可以得出几个观察结果：0论文题目：智能和自主系统在Web WWW 2018上的研究，2018年4月23日至27日，法国里昂YellowMagentaBlueGreenBlueRed0510152000.510510152000.51123456700.51123456700.5112345600.5112345600.51123400.51123400.511234500.511234500.51123400.51123400.511234500.511234500.511630（a）SYN1（b）NJW（c）PIC-k（d）FUSE（e）ROSC0图3：Syn1上的聚类结果0（a）SYN2（b）NJW（c）PIC-k（d）ZP（e）ROSC0图4：Syn2上的聚类结果0度量NJW NCuts PIC PIC-k DPIC DPIE ZP FUSE ROSC-R ROSC0纯度 0.8000 0.8000 0.7262 0.7772 0.6663 0.6348 0.8000 0.7688 0.7594 0.85380AMI 0.4338 0.4256 0.3941 0.4686 0.2502 0.1381 0.4232 0.4873 0.4331 0.62550RI 0.6811 0.6817 0.6513 0.6901 0.5786 0.4707 0.6812 0.6837 0.6762 0.83540表1：Syn1数据集的纯度、AMI和RI得分0方法 NJW NCuts PIC PIC-k DPIC DPIE ZP FUSE ROSC-R ROSC0纯度 0.6775 0.6775 0.6541 0.6849 0.5196 0.5171 0.6875 0.6773 0.7002 0.83590AMI 0.4681 0.4679 0.4157 0.4740 0.2136 0.1320 0.4746 0.4554 0.4602 0.61780RI 0.6725 0.6724 0.6477 0.6789 0.4866 0.4392 0.6780 0.6683 0.6909 0.80560表2：Syn2数据集的纯度、AMI和RI得分0数据集 #对象 #维度 #簇大小 密度0COIL20 1440 1024 200seg_7class 210 19 70glass 214 9 60MNIST0127 1666 784 40isolet_5class 300 617 50Yeast_4class 1299 8 40Yale_5class 55 1024 50表3：7个真实数据集的统计数据0Track：智能和自主系统在Web WWW 2018上，2018年4月23日至27日，法国里昂0 20 40 60 80 100∆ d(%)00.20.40.60.8(a) AMINCutsNJWPICPIC-kDPICDPIEZPFUSEROSC-RROSC0 20 40 60 80 100∆ d(%)0.40.50.60.70.80.9(b) Purity0 20 40 60 80 100∆ d(%)0.40.50.60.70.80.9(c) RI0 20 40 60 80 100∆ s(%)00.20.40.