在R中按距离进行聚类

Question

我有一个整数向量，希望将其分成簇，使得任意两个簇之间的距离大于下限，并且在任何一个簇内，两个元素之间的距离小于上限。

例如，假设我们有以下向量：

1, 4, 5, 6, 9, 29, 32, 36

并将上述下限和上限分别设置为19和9，则下面的两个向量应该是可能的结果：

1, 4, 5, 6, 9

29, 32, 36

---

感谢@flodel的评论，我意识到这种聚类可能是不可能的。因此，我想稍微修改一下问题：

如果仅强制执行簇间距离下限，可能的聚类方法有哪些？ 如果仅强制执行簇内距离上限，可能的聚类方法有哪些？

- qed

---

如果边界之间有距离，会发生什么？ - alexwhan

如果我将 20 添加到您的向量中，您的问题是否变得不可行？您不能同时满足两个条件。换句话说，您是否正在寻找一种算法，可以告诉您何时无法满足这两个条件，或者您并不知道这种可能性？在这种情况下，您可能需要重新考虑您的问题。 - flodel

Answer 1

如果我只强制执行簇间距离下限，可能的聚类方法有哪些？

采用单链接的分层聚类：

x <- c(1, 4, 5, 6, 9, 29, 32, 46, 55)
tree <- hclust(dist(x), method = "single")
split(x, cutree(tree, h = 19))

# $`1`
# [1] 1 4 5 6 9
# 
# $`2`
# [1] 29 32 46 55

---

如果我只设定群集内距离上限，可能有哪些聚类方法可用？

采用完全链接的分层聚类：

x <- c(1, 4, 5, 6, 9, 20, 26, 29, 32)
tree <- hclust(dist(x), method = "complete")
split(x, cutree(tree, h = 9))

# $`1`
# [1] 1 4 5 6 9
# 
# $`2`
# [1] 20
# 
# $`3`
# [1] 26 29 32

- flodel

Answer 2

这是一个简单的算法，概念上可以工作（实现细节被省略）：

1. 确保列表已排序。 2. 在每对连续元素之间放置一个“标记”，这些元素相隔大于“下限”。 这些标记标志着所有可能的聚类边界。 3. 在列表开始和结束前后包含一个标记。 4. 按顺序遍历标记对，并针对每个标记对left_marker和right_marker，检查left_marker右侧的元素和right_marker左侧的元素之间的距离是否小于“上限”。 5. 如果步骤4返回false，则聚类不可能。 6. 否则，标记形成所需聚类的边界。

将其应用于您的示例，我们得到：

1. 已排序：1、4、5、6、9、26、29、32 2. 标记：1、4、5、6、9 | 26、29、32 3. 额外的开始/结束标记︰| 1、4、5、6、9 | 26、29、32 | 4. 检查“上限”约束条件︰（9-1）=8 < 9︰TRUE；（32-26）= 6 < 9︰TRUE 5. 没有比较返回false 6. 所需聚类︰（1、4、5、6、9）、（26、29、32）

编辑：原帖子放松了问题的条件。

如果您只想满足下限条件︰

1. 确保列表已排序。 2. 在每对连续元素之间放置一个标记，这些元素相隔大于“下限”。 3. 在开头和结尾之前包含标记。 4. 这些标记形成所需聚类的边界。

假设您的向量已经排序，则以下内容将为您提供第2步。

# Given
vec <- c(1, 4, 5, 6, 9, 29, 32, 26)
lower_bound <- 19

f <- function(x) {
  return(vec[x+1] - vec[x] > lower_bound);
}
indices <- seq(length(vec)-1)
marker_positions <- Position(f, indices)

- Amit Kumar Gupta

---

谢谢。我已经为你的答案点赞了，它非常清晰和有帮助，但问题是在寻找R中的实际方法，如果已经存在函数或包可以完成它，那么推荐将会更加感激。另外，由于在某些情况下根据两个边界进行聚类可能是不可能的，我已经对问题进行了一些编辑，请您看一下？谢谢！ :) - qed

实际上，也许我没有理解您最初的问题。 9和26之间的距离仅为17，小于19。 这应该如何成为正确的聚类？ - Amit Kumar Gupta

@AmitKumarGupta 如果你在数字列表中加上20，那么你的算法还正确吗？ - agstudy

是的，在执行第三步之后，它将不会产生任何标记位置，这意味着你只会在起始点左侧和结束点右侧留下标记，也就是说，所有元素都属于一个等于整个原始向量的簇。 - Amit Kumar Gupta