有多少集群?
选择正确的聚类数量的方法
介绍
聚类是一种无监督的机器学习方法,可以从数据本身识别相似的数据点组,称为聚类。对于某些聚类算法,如K-means,需要事先知道有多少个聚类。如果集群的数量没有被正确地指定,那么结果就不是很有意义(参见图1)。
不幸的是,在许多情况下,我们没有<年代pan id="rmm">n我们的数据中有多少个集群。实际上,弄清楚有多少个集群可能是我们想要执行集群的首要原因。当然,数据集的领域知识可以帮助确定集群的数量。但是,这假设您知道目标类(或者至少知道有多少个类),而这在无监督学习中是不正确的。我们需要一种方法,可以在不依赖目标变量的情况下告知我们集群的数量。
确定正确集群数量的一种可能的解决方案是蛮力方法。我们尝试应用不同数量的聚类算法。然后,我们找到了优化聚类结果质量的神奇数字。在本文中,我们首先介绍两个常用的评估集群质量的指标。然后,我们将介绍三种方法来找到最优的聚类数量:
- 弯头的方法
- 轮廓系数的优化
- 统计的差距
聚类结果的质量
在使用不同的方法来确定最优的聚类数量之前,我们将看到如何定量地评估聚类结果的质量。想象以下场景。相同的数据集被聚成三个聚类(参见图2)。可以看到,左边的聚类定义得很好,而右边的聚类识别得很差。
这是为什么呢?请记住,聚类的目标是将数据点分组到聚类中,以便(1)聚类中的点尽可能相似,(2)属于不同聚类的点尽可能不同。这意味着,在理想的聚类中,群内变异很小,而群间变异很大。因此,一个好的聚类质量度量应该能够定量地总结(1)和/或(2)。
其中一个质量度量是惯性。这是作为数据点和它们所属的集群中心之间距离的平方和计算的。惯性量化了簇内的变化。
另一个流行的度量是剪影系数,它试图总结簇内和簇间的变化。在每个数据点上,我们计算到该数据点所属的集群中心的距离(称为一个),以及到第二最佳集群中心的距离(称为b).这里,第二个最佳集群指的是最近的集群,而不是当前数据点的集群。然后基于这两个距离一个和b,剪影年代该数据点的s=(b-a)/max(a,b)。
理想下聚,距离下聚一个与距离相比非常小吗b,导致年代接近1(见图3,左边)。如果聚类是次优的,那么距离一个和b可能不会有显著的差异(见图3中)。在这种情况下年代接近于0。如果聚集更糟糕,那么距离一个可能比距离还大b(见图3右)。在这种情况下,年代变成负的,接近-1。
一次年代计算所有数据点的平均值年代确定轮廓系数。可以为每个簇分别计算轮廓系数,也可以为所有数据点计算轮廓系数。当剪影系数接近1时,表明该聚类算法能够将数据划分为分离良好的聚类。
弯头的方法
惯性是群集数量的递减函数k.但在最佳聚类数以上或以下,其下降速率是不同的K.为k<K时,惯性下降迅速,而下降缓慢k>K.因此,通过绘制在某一范围内的惯性k,我们可以确定曲线在k处的弯曲或弯头。图4显示了图1示例中的惯性图。我们可以清楚地看到一个弯,或者说是肘部k= 6。
然而,这种方法有点主观,因为不同的人可能会在不同的位置识别肘部。在图4中的例子中,有些人可能会提出异议k=4是肘部。此外,肘部可能并不总是明显的,我们将在后面看到。
肘部方法的用例可以在一个自然语言问题中看到,用来确定社交网络中使用的最佳主题数量<一个class="ek ls" href="https://www.knime.com/software-overview?utm_source=medium&utm_medium=social&utm_term=&utm_content=&utm_campaign=Community" rel="noopener ugc nofollow" target="_blank">KNIME分析平台(见博客<一个class="ek ls" href="https://www.knime.com/blog/topic-extraction-optimizing-the-number-of-topics-with-the-elbow-method?utm_source=medium&utm_medium=social&utm_term=&utm_content=&utm_campaign=Community" rel="noopener ugc nofollow" target="_blank">主题提取:用肘部法优化主题数量).由于没有KNIME节点来计算惯量,因此<一个class="ek ls" href="https://kni.me/n/QNB4FsAPnEAgOMVh?utm_source=medium&utm_medium=social&utm_term=&utm_content=&utm_campaign=Community" rel="noopener ugc nofollow" target="_blank">Java代码片段Node在本例中用于计算惯性。下面是一个用于计算惯性的代码片段。
//初始化平方和
out_sum_squares = 0.0;
/*
列的前半部分属于原点的特征。
列的后半部分属于终端的特性。
每组列的顺序必须相同。
*/
int col_count = getColumnCount();
Int no_dimensions = col_count / 2;//循环特性列
for (int i = 0;我< no_dimensions;我+ +){
/*
检查特征i是否来自原点和
来自终端的特性I(即I +no_dimensions)
没有丢失,并且有相似的列名
*/
if(!isMissing(i) && isType(i, tDouble))
& & & & ! isMissing (i + no_dimensions)
的类型(i + no_dimensions tDouble) & &
getColumnName (i + no_dimensions) .contains (getColumnName (i))) {
//计算距离的平方并将其相加
out_sum_squares + =数学。战俘(getCell(我tDouble)
getCell (i + no_dimensions tDouble), 2);
}
}
轮廓的方法
轮廓系数可以为确定最优聚类数量提供更客观的手段。这是通过简单地计算轮廓系数的范围k,确定最佳峰K.KNIME组件<一个class="ek ls" href="https://kni.me/c/XCtuVNVeuqHSQkqk?utm_source=medium&utm_medium=social&utm_term=&utm_content=&utm_campaign=Community" rel="noopener ugc nofollow" target="_blank">优化k均值(剪影系数)就是这么做的。它在一个范围内执行K-Means聚类k,找到最优的K这将产生最大的剪影系数,并根据优化后的数据点分配给聚类K.图5显示了一个剪影系数图的例子,它来自图1中的例子数据。可以看出,轮廓系数在k=6,确定为最佳K值。
差距数据
为了讨论差距统计,让我们考虑没有任何聚类组织的随机数据集的聚类。假设一个随机数据集被聚成k尽管缺乏底层的集群组织,但被聚类的随机数据产生的惯性(惯性复数)稳步减少为k增加。这是因为集群中心越多,数据点到集群中心之间的距离就越小,产生了衰减的惯性。相反,正如我们在图4中已经看到的,惯性下降的速率会改变是否k是否低于或高于最佳集群数量K在一个具有集群组织的数据集中。当观察到的惯性和随机数据绘制在一起,变得明显的差异(见图7)。inertiae统计计算通过比较的差距(希望)集群数据集和相应的随机数据集合覆盖相同的范围在数据空间(Tibshirani et al .,(2001))。
在gap统计量的实际计算中,生成若干个随机样本,然后在一个范围内进行聚类k,则记录得到的惯量。这允许一些随机情况下的惯性。原始数据集也在一个范围内聚集k,导致一系列的惯性。差距统计,在k集群,计算为
Wk(i)是什么我-第一个随机样本(i=1,2,…,B)k聚类,而Wk是来自原始数据的惯量k集群。我们还计算其标准差为
然后我们找到最优的K是最小的k这满足条件
间隙统计量的计算涉及模拟。我们在R中调用函数,在KNIME工作流中使用一些R脚本计算间隙统计。特别是,调用clusGap()函数来计算不同的差距统计量k, maxSE()返回最优值K符合上述条件的。图8显示了图1中示例数据集的差距统计图B=每个迭代100次k.红线表示最优K这满足上面的条件。
应该指出的是,最优的K所确定的差距统计方法可能不一致。例如,当gap统计方法多次应用于我们的玩具数据时,结果是最优的K可能不同(参见图9)。
例如:MNIST手写体数字数据
现在,让我们在具有集群组织的真实数据集上检查上述三种方法。MNIST数据集由从0到9的手写数字灰度图像组成。在这个例子中,我们使用的是8x8像素的n=1797图像。图10显示了数据集的一些示例。使用上面描述的三种方法来确定最优的聚类数量。因为在这个数据集中有10个不同的数字,所以可以假设有10个集群,每个集群对应一个数字。然而,有些数字可能有多种写法。因此,实际上集群的数量不一定是10个。数据的2D散点图(通过tSNE投影到2D空间,见图11)显示,有些簇可能与其他簇很好地分开,而有些簇可能是接触或重叠的。此示例的工作流可以在KNIME Hub上找到<一个class="ek ls" href="https://kni.me/w/ACjm92qCUGbXsCX6" rel="noopener ugc nofollow" target="_blank">https://kni.me/w/ACjm92qCUGbXsCX6.
肘部方法的结果是不确定的,因为图中没有明显的肘部(图12,左)。情节中有一些微妙的转折(例如,9、12、20、24等),其中任何一个都可以选择作为集群的数量。
轮廓系数在k=12(右侧图12)。根据差距统计方法,k=12也被确定为最优的聚类个数(图13)。我们可以直观地比较k=9(根据肘部方法最优)和k=12(根据轮廓和间隙统计方法最优)的k- means聚类(见图14)。
结论
我们展示了三种选择最佳聚类数的方法,即弯头法、剪影系数和间隙统计量。虽然肘弯图的解释比较主观,但轮廓系数和间隙统计方法都能准确地确定簇数。然而,差距统计涉及模拟,它可能不总是产生相同的解决方案。
像许多机器学习方法一样,这里描述的方法并不适用于所有场景。由于这些方法量化了聚类中心和数据点之间的距离,因此它们适用于寻找凸聚类,例如在K-Means聚类中发现的聚类。
参考
- Robert Tibshirani, Guenther Walther, Trevor Hastie。通过差距统计估计数据集中的聚类数量。英国皇家统计学会学报,B辑,63:411-423(2001)。