4

我已经实现了 k-means 聚类来确定 300 个对象中的聚类。我的每个对象都有大约 30 个维度。距离是使用欧几里得度量计算的。

我需要知道

  1. 我如何确定我的算法是否正常工作？我不能有一个图表来说明我的算法的正确性。
  2. 欧几里得距离是计算距离的正确方法吗？如果我有 100 维而不是 30 怎么办？
4

4 回答 4

11

OP 中的两个问题是不同的主题（即答案中没有重叠），因此我将尝试一次回答一个问题，并盯着列表中的第 1 项。

我如何确定我的 [聚类] 算法是否正常工作？

与其他无监督机器学习技术一样，k-means 缺乏很好的诊断测试选择来回答诸如“k-means 返回的集群分配对 k=3 还是 k=5 更有意义？”之类的问题。

尽管如此，还是有一种被广泛接受的测试可以产生直观的结果并且可以直接应用。这个诊断指标就是这个比率：

质心间分离 /簇内方差

随着该比率值的增加，聚类结果的质量也会提高。

这是直观的。这些指标中的第一个是每个集群与其他集群的距离有多远（根据集群中心测量）？

但是仅质心间分离并不能说明全部情况，因为两种聚类算法可以返回具有相同质心间分离的结果，尽管一种显然更好，因为聚类“更紧密”（即半径更小）；换句话说，簇边缘有更多的分离。第二个指标——集群内方差——解释了这一点。这只是每个集群计算的平均方差。

总之，质心间分离与聚类内方差的比率是一种快速、一致且可靠的技术，用于比较不同聚类算法的结果，或者比较相同算法在不同变量参数下运行的结果——例如，迭代次数、距离度量的选择、质心数（k 值）。

期望的结果是紧密的（小）集群，每个都远离其他集群。

计算很简单：

对于质心间分离：

  • 计算聚类中心之间的成对距离；然后

  • 计算这些距离的中位数。

对于集群内方差：

  • 对于每个集群，计算给定集群中每个数据点与其集群中心的距离；下一个

  • （对于每个集群）从上述步骤计算距离序列的方差；然后

  • 平均这些方差值。

这是我对第一个问题的回答。这是第二个问题：

欧几里得距离是计算距离的正确方法吗？如果我有 100 维而不是 30 怎么办？

首先，一个简单的问题——随着维度/特征的增加，欧几里得距离是一个有效的度量吗？

欧几里得距离是完全可扩展的——适用于二维或两千维。对于任何一对数据点：

  • 逐元素减去它们的特征向量，

  • 将该结果向量中的每个项目平方，

  • 将结果相加，

  • 取该标量的平方根。

在这一系列计算中，没有任何地方涉及规模。

但是，欧几里得距离是否适合您的问题的相似性度量，取决于您的数据。例如，它是纯数字的（连续的）吗？或者它是否也有离散（分类）变量（例如，性别？M/F）如果您的维度之一是“当前位置”并且在 200 个用户中，100 个具有值“旧金山”而其他 100 个具有“波士顿”，你不能真的说，平均而言，你的用户来自堪萨斯州的某个地方，但这就是欧几里德距离会做的事情。

无论如何，由于我们对此一无所知，我只会给您一个简单的流程图，以便您可以将其应用于您的数据并确定适当的相似性度量。

要根据您的数据确定适当的相似性指标：

在此处输入图像描述

于 2011-11-14T12:33:16.823 回答
1

  1. 当尺寸可比较且在相同的尺度上时，欧几里得距离是好的。如果一个维度代表长度，另一个维度代表项目的重量，则欧几里得应该用加权替换。

  2. 将其制作为 2d 并显示图片 - 这是一个很好的选择，可以直观地查看它是否有效。或者您可以使用一些健全性检查 - 例如找到集群中心并查看集群中的所有项目都不是太远离它。

于 2011-11-13T06:52:38.737 回答
1

你不能试试 sum |xi - yi| 而是 if (xi - yi)^2 在你的代码中，看看它是否有很大的不同？

我不能有一个图表来说明我的算法的正确性。

几种可能性：

顺便说一句，scipy.spatial.cKDTree 可以很容易地给你说每个点的 3 个最近邻居，在 p=2（欧几里德）或 p=1（曼哈顿，L1）中查看。它的速度快到 ~ 20 天，即使在 128 天也可以使用早期截止。

补充：我喜欢高维度的余弦距离；请参阅euclidean-distance-is-通常-not-good-for-sparse-data了解原因。

于 2011-11-23T10:52:15.353 回答
1

欧几里得距离是连续变量之间直观且“正常”的距离。如果噪声太大或数据具有非高斯分布，则可能不合适。

您可能想尝试对其稳健的曼哈顿距离（或城市街区）（请记住，稳健性总是有代价的：在这种情况下，会丢失一些信息）。

对于特定问题，还有许多进一步的距离度量（例如计数数据的 Bray-Curtis 距离）。您可能想尝试从 python 模块 scipy.spatial.distance 在 pdist 中实现的一些距离。

于 2018-07-16T11:31:47.417 回答