我很难理解OPTICS聚类算法中的订购概念 [英] I am having a hard time understanding the concept of Ordering in OPTICS Clustering algorithm
问题描述
我很难理解OPTICS聚类算法中的订购概念。
如果有人能对订购和订购提供逻辑和直观的解释，我将不胜感激。还说明了以下代码中 res $ order 的功能以及可获取性图（可以通过命令 plot（res）获得）。
库（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）
）
图（x，col = rep（1：4，time = 100））
res <-光学（x，eps = 10，minPts = 10）
res
res $ order
图（res）
res $ order给出以下输出：
[1] 1363 209 349 337 301 357 333 321 285 281 253 241 241 177 153 57 257 29 77 169 105 293 229 145 145 181 385 393 377 317 381 185 117
[33] 101 9 73 237 397 369 3 65273305245249249309157345213213205 97 4933 4119314914983 83389 25121329 5161341217
[65] 189 141 85 53225313289289261221221173 69 61297125 81 133 129 197 109 137 59 93 165 89 21 13 277 191 203 379 399 375 375
[97] 351 311 235 231 227 71 11 299 271 291 147 55 23 323 219 275 47 263 3 367 331 175 87 339 319 251 251 247 171 111 223 51 63
[129] 343 303 207 151 391 359 359 287 283 215 143 131 115 99 31 183 43 243 199 199 79 27 295 67 347 255 239 195 195 187 139 107 39 119 179
[161] 39537120112315991211 355 103327327 95 7167 3526726715538738333531531525913513513279279373435326526512745 37
[193] 19276224361260260288336336368348348292268 252120108 96 88 32 16340 156 388 372 356 332 304 220 188 168 136 124 56 236
[225] 28 244 392 184 76 380 232 100 116 112 256 72 8 280 64 52 208 172 152 148 360 352 192 160 144 284 216 48 84 92 36 20
[257] 212 272 264 200 128 80 180 364 196 1 2 132 40 324 308 176 164 68 316 312 384 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 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 130 182 2 74 314 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 54
绘图生成的可及性图我无法发布，因为这是我在StackExchange上遇到的第一个问题...但是如果您运行R代码，则可以轻松获得它。
我一直在同一个问题上挣扎，经过一番研究，我认为我终于了解了它是如何工作的。
基本想法：
我现在将添加
根据我的了解，可达性距离是距离从每个点到最接近的核心点。
可达性图中谷和穗的含义
看一下伪代码，现在将完全清楚：当一个点的最终可达距离非常大时，这意味着该点与最近的核心点相距很远，因此它不属于任何群集。这就是为什么可到达性图中的峰值表示群集之间的分离……这些峰值表示异常值。实际上，离群值是指可达距离大于指定的epsilon的点（它们不在任何核心点附近）。
至于为什么山谷代表集群，那必须与集群增长的方式有关。记住DBSCAN是如何工作的，通过一连串直接连接的核心点来扩展集群...使用OPTICS相同，同时还要考虑到跟踪添加到当前集群中每个点的可达距离。考虑一下簇的形成方式，以了解山谷的含义。
I am having a hard time understanding the concept of Ordering in OPTICS Clustering algorithm.
I Would be grateful if someone gives a logical and intuitive explanation of the ordering and also explain what res$order does in the following code and what is the reahability plot(which can be obtained by the command '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 gives the following output:
[1] 1 363 209 349 337 301 357 333 321 285 281 253 241 177 153 57 257 29 77 169 105 293 229 145 181 385 393 377 317 381 185 117 [33] 101 9 73 237 397 369 365 273 305 245 249 309 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 225 313 289 261 221 173 69 61 297 125 81 133 129 197 109 137 59 93 165 89 21 13 277 191 203 379 399 375 [97] 351 311 235 231 227 71 11 299 271 291 147 55 23 323 219 275 47 263 3 367 331 175 87 339 319 251 247 171 111 223 51 63 [129] 343 303 207 151 391 359 287 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 292 268 252 120 108 96 88 32 16 340 156 388 372 356 332 304 220 188 168 136 124 56 236 [225] 28 244 392 184 76 380 232 100 116 112 256 72 8 280 64 52 208 172 152 148 360 352 192 160 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 344 328 248 204 140 296 24 320 228 60 44 [289] 233 65 400 376 240 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] 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 54
and the 'plot' produces a reachability plot which I am not able to post because this is my first question on StackExchange...but if you run the R code you can easily get it.
I was struggling with the same issue and after some research I think I finally understood how it works.
BASIC IDEA:
I will now add the pseudocode provided by Wikipedia, commented by me to explain it a little bit:
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)
From that pseudocode, I get the following:
- You will need an ordered list (to represent the reachability plot)
- Clusters will grow as they do in the DBSCAN algorithm
- The difference with DBSCAN is that now, when you get the neighborhood of a core point, for every neighbor you will have to calculate a so called reachability distance; if the neighbor hasn't one, just save the one you get and put that point next to the core one in the ordered list; if it had one already, compare the old one with the one obtained when processing the core point and go with the smaller one. If that one happens to be the new one, an update must be done in the ordered list to accommodate the point close to the core point.
REACHABILITY DISTANCE
Now, it's crucial to understand what's the reachability distance. Also, from Wikipedia, we have:
From what I get, the reachability distance is the distance from every point to its closest core point.
MEANING OF VALLEYS AND SPIKES IN REACHABILITY PLOT
If we take a look at the pseudocode, now it will be totally clear: when the final reachability distance for a point is super big, that means the point is far far away from the closest core point, so it doesn't belong to any cluster. That's why the spikes in the reachability plot denote the separation between clusters ... those spikes represent outliers. In fact, outliers are those points which reachability distance is greater than the specified epsilon (they aren't in any core point neighbourhood).
As for why valleys represent clusters, that has to be with the way the clusters grow; remember how DBSCAN works, growing a cluster following a chain of directly connected core points ... with OPTICS that's the same, considering also we keep track of the reachability distance of every point we add to the current cluster. Think about the way clusters are form to understand the meaning of the valleys.
这篇关于我很难理解OPTICS聚类算法中的订购概念的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
