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)