如何判断数据是否足够“聚类”以使聚类算法产生有意义的结果?

机器算法验证 聚类 k-均值
2022-01-31 22:56:42

您如何知道您的(高维)数据是否表现出足够的聚类,从而使 kmeans 或其他聚类算法的结果实际上是有意义的?

特别是对于 k-means 算法,集群内方差应该减少多少才能使实际的聚类结果有意义(而不是虚假的)?

当绘制数据的降维形式时,聚类是否应该很明显,如果聚类无法可视化,kmeans(或其他方法)的结果是否毫无意义?

4个回答

具体关于 k-means,您可以使用 Gap 统计信息。基本上,这个想法是基于与参考分布相比的平均离散度来计算聚类度量的优度,以用于越来越多的集群。更多信息可以在原始论文中找到:

Tibshirani, R.、Walther, G. 和 Hastie, T. (2001)。通过 gap statistic 估计数据集中的簇数JR统计学家。社会党。B,63(2):411-423。

我为相关问题提供的答案突出了其他一般有效性指标,这些指标可用于检查给定数据集是否表现出某种结构。

如果您不知道如果只有噪声会发现什么,一个好的方法是使用重采样并研究集群稳定性。换句话说,重新采样您的数据(通过引导程序或通过向其添加小噪声)并计算结果分区的“接近度”,如Jaccard相似性所衡量的那样。简而言之,它允许估计在数据中恢复类似集群的频率。这种方法在fpc R 包中很容易获得,因为clusterboot(). 它将原始数据或距离矩阵作为输入,并允许应用广泛的聚类方法(分层、k-means、模糊方法)。该方法在链接的参考文献中进行了讨论:

Hennig, C. (2007)集群稳定性的集群评估计算统计和数据分析,52,258-271。

Hennig, C. (2008)溶出点和隔离稳健性:一般聚类分析方法的稳健性标准多元分析杂志,99,1154-1176。

下面是一个关于 k-means 算法的小演示。

sim.xy <- function(n, mean, sd) cbind(rnorm(n, mean[1], sd[1]),
rnorm(n, mean[2],sd[2]))
xy <- rbind(sim.xy(100, c(0,0), c(.2,.2)),
            sim.xy(100, c(2.5,0), c(.4,.2)),
            sim.xy(100, c(1.25,.5), c(.3,.2)))
library(fpc)
km.boot <- clusterboot(xy, B=20, bootmethod="boot",
                       clustermethod=kmeansCBI,
                       krange=3, seed=15555)

在这个人工(且结构良好)的数据集中,结果是非常积极的,因为三个集群krange

以下是 20 个自举样本的结果。可以看出,统计单位倾向于保持分组到同一个集群中,对于介于两者之间的那些观察结果几乎没有例外。

在此处输入图像描述

当然,您可以将此想法扩展到任何有效性指数:通过引导程序(带替换)选择一系列新的观察结果,计算您的统计数据(例如,轮廓宽度、共生相关性、休伯特伽玛,在平方和内)聚类数(例如,2 到 10),重复 100 或 500 次,然后查看统计量的箱线图作为聚类数的函数。

这是我使用相同的模拟数据集得到的结果,但使用了 Ward 的层次聚类并考虑了共生相关性(评估距离信息在结果分区中再现的程度)和轮廓宽度(评估集群内同质性和相互间的组合度量)集群分离)。

cophenetic 相关范围从 0.6267 到 0.7511,中值为 0.7031(500 个引导样本)。当我们考虑 3 个集群时,轮廓宽度似乎最大(中位数 0.8408,范围 0.7371-0.8769)。

在此处输入图像描述

快速可视化高维数据是否表现出足够聚类的一种方法是使用 t-Distributed Stochastic Neighbor Embedding ( t-SNE )。它将数据投影到一些低维空间(例如 2D、3D),并且在保持集群结构(如果有的话)方面做得很好。

例如MNIST 数据集

在此处输入图像描述

Olivetti 面临的数据集:

在此处输入图像描述

当然,在可绘制的维数中视觉识别集群的能力是集群算法有用性的一个值得怀疑的标准,特别是如果这种降维是独立于集群本身进行的(即:徒劳地试图找出是否集群将起作用)。

事实上,聚类方法在寻找人眼/大脑无法看到的聚类方面具有最高价值。

简单的答案是:进行聚类,然后找出它是否有效(使用您感兴趣的任何标准,另请参阅@Jeff 的回答)。

结果什么时候有意义特别是k-means结果?

事实上,k-means 优化了某个数学统计量。没有与此相关的“有意义”。

特别是在高维数据中,第一个问题应该是:欧几里得距离还有意义吗?如果不是,请不要使用 k-means。欧几里得距离在物理世界中是有意义的,但是当你有其他数据时它很快就失去了意义。特别是当你人为地将数据转换为向量空间时,有什么理由应该是欧几里得?

如果您采用经典的“老忠实”数据集并对其运行 k-means而不进行归一化,但使用纯欧几里得距离,它已经不再有意义。EM,实际上使用某种形式的“集群本地”马氏距离,效果会好很多。特别是,它适应具有非常不同比例的轴。

顺便说一句,k-means 的一个关键优势在于它实际上总是对数据进行分区,无论它看起来如何。您可以使用 k-means 将均匀噪声划分为 k 个集群可以说很明显,k-means 集群没有意义。或者可以接受这一点:用户希望对数据进行分区以最小化平方欧几里得距离,而不要求集群是“有意义的”。