2

我很难理解 OPTICS 聚类算法中排序的概念。

如果有人对排序给出合乎逻辑和直观的解释，并解释res$order以下代码中的作用以及可重复性图是什么（可以通过命令“plot(res)”获得），我将不胜感激。

library(dbscan)

set.seed(2)
n <- 400

x <- cbind(
  x = runif(4, 0, 1) + rnorm(n, sd=0.1),
  y = runif(4, 0, 1) + rnorm(n, sd=0.1)
  )

plot(x, col=rep(1:4, time = 100))


res <- optics(x, eps = 10,  minPts = 10)
res

res$order
plot(res)

res$order 给出以下输出：

[1] 1 363 209 349 337 301 357 333 321 285 281 253 253 241 177 177 153 57 257 29 77 169 105 293 293 229 145 181 385 393 377 377 377 381 381 381 381 381 185 33 [33] 157 345 213 205 97 49 33 41 193 149 17 83 389 25 121 329 5 161 341 217 [65] 189 141 85 53 53 225 313 313 313 289 289 261 261 221 173 69 61 297 61 297 125 81 125 81 133 129 197 191 203 379 399 375 [97] 351 311 235 231 227 71 11 299 271 291 291 147 55 23 323 23 323 219 275 47 263 3 367 33175 87 339 339 339 339 319 319 251 251 247 171 247 171 111 111 223 51 223 51 229] 343 51 63 [129] 283 215 143 131 115 99 31 183 43 243 199 79 27 295 67 347 255 239 195 187 139 107 39 119 179 [161] 395 371 201 123 159 91 211 355 103 327 95 7 167 35 267 155 387 383 335 315 259 135 15 113 279 373 4 353 265 127 45 37 [193] 19 276 224 361 260 288 336 368 348 292268 268 252 120 108 96 88 32 16 340 156 388 372 372 372 356 332 304 220 188 168 168 136 124 56 236 [225] 28 244 392 184 392 184 380 232 100 232 100 116 116 112 256 112 256 72 256 72 80 280 64 52 208 172 208 172 152 152 152 152 152 152 152 152 152 152 148 352 144 352 144 352 144 284 216 48 84 92 36 20 [257] 212 272 264 200 128 80 180 364 196 12 132 40 324 308 176 164 68 316 312 384 300 300 344 328 248 248 204 140 296 240 296 24 320 228 60 44 [289] 163 104 396 307 75 14 325 269 262 234 382 294 206 198 374 310 362 318 386 358 330 278 210 298 282 122 98 [321] 34 26 174 142 46 6 62 118 190 202 114 322 286 38 242 394 342 266 162 130 30 182 2 74 314 290 246 194 170 126 158 378 [353] [353] 350 254 226 214 70 18 10 366 354 186 150 86 150 86 306 102 338 346 134 250 138 94 78 94 78 390 274 58 42 258 42 258 42 258 42 258 66 90 146 370 222 222 218 [385] 326 82 110 270 334 178 166 398 22 50 238 106 154 302 230 5488 32 16 340 156 388 372 372 332 304 220 188 168 168 136 124 56 236 [225] 28 244 392 184 392 184 76 380 232 100 232 100 116 112 256 112 256 72 80 280 64 52 208 172 208 172 152 148 36 20 [257] 212 272 264 200 128 80 180 364 196 12 132 40 324 308 176 164 68 316 312 384 300 344 328 248 248 204 204 140 296 24 320 228 60 44 [289] 233 65 400 14 325 269 262 234 382 294 206 198 374 318 310 313 312 318 386 358 3333330 278 278 210 298 282 122 122 98 [321] 34 26 174 174 142 46 6 62 118 190 190 202 114 202 114 322 114 322 114 322 286 386 382 386 382 394 394 394 394 394 394 342 2662 2662 162 162 162 162 162 162 162 162 162 162 162 162 162 162 162 130 32 74 290 246 194 170 126 158 378 [353] 350 254 226 214 70 18 10 366 354 186 150 86 306 102 338 346 134 250 138 94 78 390 274 58 42 258 66 90 146 370 222 218 [385] 326 82 110 270 334 178 166 398 22 50 238 106 154 302 230 5488 32 16 340 156 388 372 372 332 304 220 188 168 168 136 124 56 236 [225] 28 244 392 184 392 184 76 380 232 100 232 100 116 112 256 112 256 72 80 280 64 52 208 172 208 172 152 148 36 20 [257] 212 272 264 200 128 80 180 364 196 12 132 40 324 308 176 164 68 316 312 384 300 344 328 248 248 204 204 140 296 24 320 228 60 44 [289] 233 65 400 14 325 269 262 234 382 294 206 198 374 318 310 313 312 318 386 358 3333330 278 278 210 298 282 122 122 98 [321] 34 26 174 174 142 46 6 62 118 190 190 202 114 202 114 322 114 322 114 322 286 386 382 386 382 394 394 394 394 394 394 342 2662 2662 162 162 162 162 162 162 162 162 162 162 162 162 162 162 162 130 32 74 290 246 194 170 126 158 378 [353] 350 254 226 214 70 18 10 366 354 186 150 86 306 102 338 346 134 250 138 94 78 390 274 58 42 258 66 90 146 370 222 218 [385] 326 82 110 270 334 178 166 398 22 50 238 106 154 302 230 54220 188 168 136 124 56 236 [225] 28 244 392 184 76 380 232 100 116 112 256 72 256 72 8 280 64 52 208 172 172 152 152 152 148 360 352 192 160 144 284 284 284 284 284 216 48 84 84 92 36 20 [257] 80 180 364 196 12 132 40 324 308 176 164 68 316 316 312 384 300 344 328 248 248 204 140 296 24 320 228 60 44 [289] 233 65 400 376 240 163 240 163 104 163 104 396 396 396 396 307 75 310 362 318 386 358 330 278 210 298 282 122 98 [321] [321] 34 26 174 142 46 6 62 118 190 202 114 322 286 386 38222222222223842 394 342 342 342 266 162 162 162 162 130 30 182 274 30 182 2 74 314 314 314 314 290 246 194 294 170 294 170 126 158 378 378 378 378 378 378 350 254 226 214 70 18 10 366 354 186 150 86 306 102 338 346 134 250 138 94 78 390 274 58 42 258 42 258 66 90 146 370 222 218 [385] 54220 188 168 136 124 56 236 [225] 28 244 392 184 76 380 232 100 116 112 256 72 256 72 8 280 64 52 208 172 172 152 152 152 148 360 352 192 160 144 284 284 284 284 284 216 48 84 84 92 36 20 [257] 80 180 364 196 12 132 40 324 308 176 164 68 316 316 312 384 300 344 328 248 248 204 140 296 24 320 228 60 44 [289] 233 65 400 376 240 163 240 163 104 163 104 396 396 396 396 307 75 310 362 318 386 358 330 278 210 298 282 122 98 [321] [321] 34 26 174 142 46 6 62 118 190 202 114 322 286 386 38222222222223842 394 342 342 342 266 162 162 162 162 130 30 182 274 30 182 2 74 314 314 314 314 290 246 194 294 170 294 170 126 158 378 378 378 378 378 378 350 254 226 214 70 18 10 366 354 186 150 86 306 102 338 346 134 250 138 94 78 390 274 58 42 258 42 258 66 90 146 370 222 218 [385] 548 8 280 64 52 208 172 152 148 360 3352 192 160 144 284 284 216 48 84 92 36 20 [257] 212 272 264 200 128 80 180 180 180 180 364 196 12 132 40 324 308 308 176 164 308 164 68 316 316 384 384 384 300 300 344 344 328 248244 328 248 204 324 204 204 204 140 296 296 24 320 228 60 44 [289] 233 65 400 376 240 163 104 396 307 75 14 325 269 269 262 262 234 382 294 206 198 374 374 318 374 310 310 318 386 358 3330 330 278 330 278 278 278 278 278 210 298 282 118 190 202 114 322 286 38 242 394 342 266 162 162 130 30 30 182 2 74 314 290 246 194 170 126 158 378 [353] 274 58 42 258 66 90 146 370 222 218 [385] 326 82 110 270 334 178 166 398 22 50 238 106 154 302 230 548 8 280 64 52 208 172 152 148 360 3352 192 160 144 284 284 216 48 84 92 36 20 [257] 212 272 264 200 128 80 180 180 180 180 364 196 12 132 40 324 308 308 176 164 308 164 68 316 316 384 384 384 300 300 344 344 328 248244 328 248 204 324 204 204 204 140 296 296 24 320 228 60 44 [289] 233 65 400 376 240 163 104 396 307 75 14 325 269 269 262 262 234 382 294 206 198 374 374 318 374 310 310 318 386 358 3330 330 278 330 278 278 278 278 278 210 298 282 118 190 202 114 322 286 38 242 394 342 266 162 162 130 30 30 182 2 74 314 290 246 194 170 126 158 378 [353] 274 58 42 258 66 90 146 370 222 218 [385] 326 82 110 270 334 178 166 398 22 50 238 106 154 302 230 54384 300 344 328 248 204 140 296 24 320 228 60 44 [289] 233 65 400 376 240 163 104 396 307 75 14 325 14 325 269 262 262 262 234 382 294 382 294 374 206 198 374 374 318 318 318 318 318 318 318 318 3386 3386 3386 3333333330 278 278 278 278 278 278 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 32 98 [3222222298] 3298 [3298] ] 34 26 174 142 46 6 62 118 190 202 114 322 286 38 242 394 394 394 342 266 162 130 30 182 2 74 314 290 246 194 170 170 126 158 378 [353] 338 346 134 250 138 94 78 390 274 58 42 258 66 90 146 370 222 218 [385] 326 82 110 270 334 178 166 398 22 50 238 106 106 10454 302 3384 300 344 328 248 204 140 296 24 320 228 60 44 [289] 233 65 400 376 240 163 104 396 307 75 14 325 14 325 269 262 262 262 234 382 294 382 294 374 206 198 374 374 318 318 318 318 318 318 318 318 3386 3386 3386 3333333330 278 278 278 278 278 278 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 298 32 98 [3222222298] 3298 [3298] ] 34 26 174 142 46 6 62 118 190 202 114 322 286 38 242 394 394 394 342 266 162 130 30 182 2 74 314 290 246 194 170 170 126 158 378 [353] 338 346 134 250 138 94 78 390 274 58 42 258 66 90 146 370 222 218 [385] 326 82 110 270 334 178 166 398 22 50 238 106 106 10454 302 3[353] 350 254 226 214 70 18 10 366 354 186 150 86 306 102 338 346 134 250 134 250 138 94 78 390 274 58 42 258 42 258 66 90 146 370 22222222222 218 [385] 154 302 230 54[353] 350 254 226 214 70 18 10 366 354 186 150 86 306 102 338 346 134 250 134 250 138 94 78 390 274 58 42 258 42 258 66 90 146 370 22222222222 218 [385] 154 302 230 54

并且“情节”产生了一个我无法发布的可达性情节，因为这是我在 StackExchange 上的第一个问题......但如果你运行 R 代码，你可以很容易地得到它。

4

3 回答 3

1

它是数据集的重新排序（排列），因此附近的点通常在顺序上很接近。

于 2018-11-26T21:39:44.570 回答
1

R 包中包含详细说明。

library("dbscan")
vignette("dbscan")

请参阅第2.2 节。光学：识别聚类结构的订购点

OPTICS 提供了增强的排序。该算法从一个点开始并像 DBSCAN 一样扩展它的邻域，但它按核心距离从最低到最高的顺序探索新点。探索点的顺序以及每个点的核心距离和可达距离是算法的最终结果。

于 2018-11-29T15:16:23.773 回答
1

我在同样的问题上苦苦挣扎，经过一些研究，我想我终于明白了它是如何工作的。

基本理念：

我现在将添加 Wikipedia 提供的伪代码，由我评论以稍微解释一下：

OPTICS(DB, eps, MinPts)
for each point p of DB
   p.reachability-distance = UNDEFINED
for each unprocessed point p of DB
   N = getNeighbors(p, eps)
   mark p as processed
   output p to the ordered list          # ordered list = final result
   # if p is a core point (has at least minPts in the specified radius)
   if (core-distance(p, eps, Minpts) != UNDEFINED)
      Seeds = empty priority queue
      # update the reachability-distance for every neighbour
      update(N, p, Seeds, eps, Minpts)
      # seeds will have the neighbours wich reachability-distance was updated
      # with the selected core point
      for each next q in Seeds
         N' = getNeighbors(q, eps)
         mark q as processed
         output q to the ordered list          # ordered list = final result
         # if the neighbor is a core point, grow the cluster as DBSCAN does
         if (core-distance(q, eps, Minpts) != UNDEFINED)
            update(N', q, Seeds, eps, Minpts)


update(N, p, Seeds, eps, MinPts)
coredist = core-distance(p, eps, MinPts)
# for every neighbor
for each o in N
   if (o is not processed)
      new-reach-dist = max(coredist, dist(p,o))
      if (o.reachability-distance == UNDEFINED) // o is not in Seeds
          o.reachability-distance = new-reach-dist
          Seeds.insert(o, new-reach-dist)
      else               // o in Seeds, check for improvement
          if (new-reach-dist < o.reachability-distance)
             o.reachability-distance = new-reach-dist
             Seeds.move-up(o, new-reach-dist)

从该伪代码中，我得到以下信息：

  • 您将需要一个有序列表（表示可达性图）
  • 集群将像在 DBSCAN 算法中一样增长
  • 与 DBSCAN 的不同之处在于，现在，当您获得核心点的邻域时，您必须为每个邻域计算所谓的可达距离；如果邻居没有，只需保存您获得的那个并将该点放在有序列表中的核心之一旁边；如果已经有了，就将旧的与核心点处理时得到的进行比较，然后选择较小的。如果那个恰好是新的，则必须在有序列表中进行更新以适应靠近核心点的点。

可达距离

现在，了解什么是可达距离至关重要。此外，从Wikipedia中，我们有：

在此处输入图像描述

据我所知，可达距离是每个点到其最近核心点的距离。

可达性图中山谷和尖峰的含义

如果我们看一下伪代码，现在就很清楚了：当一个点的最终可达距离超大时，这意味着该点离最近的核心点很远，所以它不属于任何一个簇。这就是可达性图中的尖峰表示集群之间的分离的原因......这些尖峰表示异常值。实际上，异常值是可达距离大于指定 epsilon 的那些点（它们不在任何核心点邻域中）。

至于为什么山谷代表星团，那得看星团的生长方式；记住 DBSCAN 是如何工作的，在一系列直接连接的核心点之后增长一个集群......使用 OPTICS 也是如此，同时考虑到我们跟踪我们添加到当前集群的每个点的可达距离。想想集群的形成方式，以了解山谷的含义。

于 2019-10-16T01:48:50.503 回答