3

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

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

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

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

1、4、5、6、9

29、32、36

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

如果我只强加集群间距离下限，有哪些可能的集群方法？如果我只强加集群内 距离上限，有哪些可能的集群方法？

4

2 回答 2

6

如果我只强加集群间距离下限，有哪些可能的集群方法？

具有单链接的层次聚类：

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
于 2013-06-21T07:14:42.173 回答
3

这是一个可行的简单算法，从概念上解释（省略实现细节）：

  1. 确保您的列表已排序。
  2. 在每对分开的连续元素之间放置一个“标记” lower_bound。这些标记了所有可能的集群边界。
  3. 在列表开头之前和结尾之后包含一个标记。
  4. 按顺序遍历标记对，对于每一对left_markerand right_marker，检查紧邻 the 右侧的left_marker元素与紧邻 the 左侧的元素之间的距离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: 真
  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)
于 2013-06-21T06:45:40.750 回答