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. 其他开始/结束标记： 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. 在间隔超过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)