I am having a hard time understanding the concept of Ordering in OPTICS Clustering algorithm

Question

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.

Answer 1

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.

Answer 2

It is a reordering (permutation) of your data set, such that nearby points usually are close in the order.

Answer 3

A detailed description is included in the R packages.

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

See Section 2.2. OPTICS: Ordering Points To Identify Clustering Structure

OPTICS provides an augmented ordering. The algorithm starting with a point and expands it’s neighborhood like DBSCAN, but it explores the new point in the order of lowest to highest core-distance. The order in which the points are explored along with each point’s core- and reachability-distance is the final result of the algorithm.