是否存在与集群或“反”集群相反的情况?

机器算法验证 分类 聚类
2022-04-08 01:55:42

在聚类中,我们希望找到最佳聚类 - 靠近在一起的数据点(通过定义的距离度量来衡量)。有没有“反”集群?我们有一组数据点,并希望找到“反”集群 - 具有尽可能远的数据点的子集(通过定义的距离度量,例如欧几里得距离)。

在一个具体的应用程序中,我有一组人,并希望将这些人分成n组,尽可能使用一些预定义的标准进行衡量(多样化意味着:每个组中每个标准的相同值尽可能少)。

我第一次想到这个似乎很直观,但我找不到任何方法来创建这些子集,也许我要专注于常规的聚类方法。对不起,如果这个问题太琐碎,但任何帮助将不胜感激!

4个回答

根据发布者在其中一个答案中的回复,我将重新表述问题陈述,因为它可以使用R我编写的包来解决:

任务是将一组元素划分为 K 个组,以使簇之间的距离最小化,而簇内的距离最大化。这在数学上与聚类相反,确实被称为反聚类;关于这种方法,有一些很少被引用的论文(Späth 1986;Valev 1998)。通常,反聚类会导致彼此相似的聚类。

如果你使用的是 R,你可以使用我的包 anticluster来解决 anticlustering 问题。例如,使用以下代码在经典鸢尾花数据集中创建三组相似的植物:

library(anticlust)
data(iris)

## Maximize the k-means criterion
anticlusters <- anticlustering(
  iris[, -5],
  K = 3,
  objective = "variance"
)

## Compare feature means by anticluster
by(iris[, -5], anticlusters, function(x) round(colMeans(x), 2))
#> anticlusters: 1
#> Sepal.Length  Sepal.Width Petal.Length  Petal.Width 
#>         5.84         3.06         3.76         1.20 
#> --------------------------------------------------------------------------------------- 
#> anticlusters: 2
#> Sepal.Length  Sepal.Width Petal.Length  Petal.Width 
#>         5.84         3.06         3.76         1.20 
#> --------------------------------------------------------------------------------------- 
#> anticlusters: 3
#> Sepal.Length  Sepal.Width Petal.Length  Petal.Width 
#>         5.84         3.06         3.76         1.20 

我的包可以最大化两个聚类目标:(a)经典的 k-means 目标,导致相似的特征均值;(b) 聚类编辑目标,它是聚类内成对距离的总和。在包中,您可以objective在“方差”(k-means)或“距离”(聚类编辑)之间改变参数。

Github 页面和包文档包含有关包中使用的方法和算法的更多信息。


Späth, H. (1986)。反聚类:最大化方差标准。控制与控制论,15(2),213–218。

Valev, V. (1998)。重新审视设置分区原则。在关于模式识别 (SPR) 和结构和句法模式识别 (SSPR) 中的统计技术的联合 IAPR 国际研讨会上(第 875-881 页)。

有几个相关的域:

  1. 异常值检测:发现异常点,而不是聚类中的典型代表。
  2. 分层抽样。选择一个随机样本,使样本对应于不同的类别。对于较大的集合,使类分布匹配。
  3. 原型分析。不是通过“平均”集群代表来总结数据,而是通过“绑定”集群的极端观察来总结数据。

但是您当然需要更明确地了解您所拥有的形式要求,一些模糊的直觉是不够的。

也许您仍然想要聚类 - kmeans 试图最小化聚类内方差,这意味着它最大化聚类之间的平方和。所以在一个好的kmeans聚类中,不在同一个聚类中的两个对象的典型平方偏差被最大化;聚类确实将数据划分为“尽可能不同”的分区。

它仍然是您想要的集群,因为您正在尝试将数据拆分为子集,这就是集群。

如果您的聚类算法基于距离度量,那么该度量的简单否定或反向应该完成您请求的子集。一些算法依赖于距离测量是正的,在这种情况下,逆向应该起作用。当然,您可以使用分数幂函数来软化逆。

建立在 Nick Cox 和其他人的有用评论和答案的基础上:

DBSCAN是一种聚类算法,它还可以识别不属于任何特定聚类的点,并将它们视为“噪声”。这可能是实现您所追求的一种方法,因为它可以识别距离集群足够远的点,从而使将它们组合在一起是有问题的。