【Paper Note】Support Vector Clustering 论文翻译（未完待续）

偏执的太偏执、 2022-06-12 01:40 204阅读 0赞

## Abstract ##

我们提出了使用支持向量机的新颖的聚类方法，数据点通过高斯核映射到一个高位的特征空间，在这个空间中，我们搜索最小簇，当映射回数据空间，这个簇可以分成几个组件，每个组件包含了一个点集。我们提出了一个简单的算法来定义这些簇，高斯核的宽度控制着探测数据的规模，而soft margin常数有助于处理异常值和重叠簇。通过改变两个参数来研究一个数据集的结构，保持最小的支持向量以确保平滑的簇边界。我们演示了算法在几个数据集上的性能。

关键词：聚类，支持向量机，高斯核

## Introduction ##

聚类算法根据各种标准对数据点进行分组，如Jain and Dubes(1998)，Fukunaga(1990)，Duda et al.(2001)。聚类可以像MacQueen(1965)的k-means算法那样根据一些参数进行，或者像层次聚类那样根据一些距离或相似度测量进行分组。其他方法包括图论方法、如Shamir and Sharan(2000)，物理动量算法，如Blatt et al.(1997)，和基于密度测量的方法，如Roberts(1997)和Fukunaga(1990)。这篇Paper中，我们提出了一种基于Vapnik(1995)支持向量机的非参数聚类方法。在Schölkopf等人（2000，2001），Tax和Duin（1999）使用支持向量算法来表征高维度分布的支持。作为算法的副产品，可以计算一组包围数据点的轮廓。这些轮廓被我们解释为Ben-Hur等人的簇边界。 （2000年）。这里我们详细讨论一种允许系统搜索聚类解决方案而不对其数量或形状做出假设的方法，首先在Ben-Hur等人介绍（2001年）。

在我们的支持向量聚类（SVC）中，使用高斯内核将数据点从数据空间映射到高维特征空间。在特征空间中，我们寻找包围数据图像的最小球体。该球体被映射回数据空间，其中它形成一组包围数据点的轮廓。这些轮廓被解释为簇边界。每个单独轮廓所包围的点与相同的集群相关联。随着高斯核的宽度参数的减小，数据空间中不连续轮廓的数量增加，导致簇数越来越多。由于轮廓可以解释为描述潜在概率分布的支持，所以我们的算法可以被看作是在该概率分布中识别谷的一个。

SVC可以通过使用允许特征空间中的球体不包围所有点的软边界常数来处理异常值。对于此参数的大值，我们还可以处理重叠的集群。在这个范围内，我们的算法类似于Roberts（1997）的尺度空间聚类方法，该方法基于具有高斯核函数的概率密度的Parzen窗口估计。

在下一节中，我们定义SVC算法。在第3节中，它适用于有或没有异常值的问题。我们首先描述一个没有异常值的问题来说明通过改变高斯核的规模获得的聚类边界和聚类解的类型。然后，我们继续讨论需要调用异常值以获得平滑聚类边界的问题。这些问题包括两个标准的基准示例。

## The SVC Algorithm ##

### ClusterBoundaries ###

按照Schölkopf等人（2000）和Tax and Duin（1999），我们制定了一个数据集的支持向量描述，用作我们的聚类算法的基础。令\{xi\}⊆χ是N点的数据集，χ⊆IRd，数据空间。使用从χ到一些高维特征空间的非线性变换Φ，我们寻找半径为R的最小包围球体。这由约束描述：