R中的距离聚类

Question

我有一个整数向量，我想把它划分成簇，使任意两个簇之间的距离大于一个下界，而在任何一个簇内，两个元素之间的距离小于一个上界。

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

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

并将上述下界和上界分别设为19和9，以下两个向量应是可能的结果：

1、4、5、6、9

29、32、36

感谢@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

Answer 2

以下是一个简单的算法，在概念上加以解释(省略了实现细节)：

1. 确保您的列表是排序的。
2. 在分隔超过lower_bound的每一对连续元素之间放置一个“标记”。这些标记了所有可能的集群边界。
3. 在列表开始之前和结束后包括一个标记。
4. 按照顺序遍历对标记，对于每对left_marker和right_marker，检查left_marker右侧的元素与right_marker左边的元素之间的距离是否小于upper_bound。
5. 如果上一步返回false，则群集是不可能的。
6. 否则，标记就形成了所需聚类的边界。

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

1. 排序: 1，4，5，6，9，26，29，32
2. 标记: 1、4、5、6、9- 26、29、32
3. 其他起始/结束标记：\x 1、4、5、6、9\x{e76f} 26、29、32 \x
4. 检查“上限”约束：(9-1) =8< 9: TRUE；(32-26)=6< 9: TRUE
5. 没有一个比较结果是假的。
6. 期望集群：(1，4，5，6，9)，(26，29，32)

编辑：原始海报放宽了问题的条件。

如果只想满足下限条件：

1. 确保您的列表是排序的。
2. 在分隔超过lower_bound的每一对连续元素之间放置一个标记。
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)