Repository: scikit-learn/scikit-learn
Pull request: [MRG+1] Fix OPTICS processing order
#### Reference Issues/PRs
Fixes #12090: a subtle bug that only the neighbors of the current point - not earlier neighbors - were considered for expanding clusters in OPTICS.
Fixes #12134: test case is included and passes

#### What does this implement/fix? Explain your changes.

With these changes, the result is the same as ELKIs, and the unit test contains reference data generated with ELKI. R currently differs, because ELKI changed the order to prefer smaller ids on ties, while R is still replicating older ELKI behavior of prefering higher ids on ties. A pull request for this is open with R dbscan: https://github.com/mhahsler/dbscan/pull/25

#### Any other comments?

This probably also obsoletes #12054
and helps with resolving #11857 and #12049 and #11677

Problem statement:
OPTICS test_reach_dists inappropriate
I begin to suspect the correctness of the test. Seems that our implementation and the referenced implementation are not the same. In our implementation, when there're multiple points with the same reachability-distance, we choose the point which is closest to current point. In the referenced implementation, we choose the point with the smallest index. See the example below (taken from the referenced implementation):
```
X = np.array([[ 15.,  70.], [ 31.,  87.], [ 45.,  32.], [ 32.,  83.],
              [ 26.,  50.], [  7.,  31.], [ 43.,  97.]])
###
# result from our implementation
clust = OPTICS(min_samples=5)
clust.fit(X)
clust.core_distances_
# array([38.89730068, 37.33630941, 52.63078947, 33.54101966, 33.54101966,
#        57.69748695, 49.979996  ])
clust.reachability_
# array([        inf, 33.54101966, 33.54101966, 38.89730068, 33.54101966,
#        33.54101966, 33.54101966])
clust.ordering_
# array([0, 3, 1, 6, 4, 2, 5])
###
# result from referenced implementation
RD, CD, order = optics(X, 4)
CD
# array([38.89730068, 37.33630941, 52.63078947, 33.54101966, 33.54101966,
#        57.69748695, 49.979996  ])
RD
# array([ 0.        , 38.89730068, 33.54101966, 37.33630941, 33.54101966,
#        33.54101966, 33.54101966])
order
# [0, 1, 3, 4, 2, 5, 6]
```
We get the same CD, but different order (e.g., after choosing point 0, point 1&3&4&6 have the same RD, our implementation choose point 3 because it's closest to point 0, the referenced implementation choose point 1 because it has the smallest index), thus different RD (RD of current point is only related to previous points)
Correct me if I'm wrong @jnothman @espg @adrinjalali

Hints from issue discussion:
Interesting. Our policy seems appropriate, although more computationally
complex.

Should the test still be valid in the min_samples=2 case?

> Should the test still be valid in the min_samples=2 case?

I guess it will be valid when min_samples=2 (not sure though), because when min_samples=2, reachability-distance means distance between points and we'll always move on to the closest point (when there're multiple points, we'll always choose the one with smallest index).
So as long as we don't encounter this edge case, the two algorithms should return the same RD, which I guess would be the case for our randomly generated data. I don't think that renders the test invalid, it just means we should avoid this edge case and document it in the test.
> So as long as we don't encounter this edge case, the two algorithms should return the same RD, which I guess would be the case for our randomly generated data.

How can you prove that in our (randomly) generated dataset, there will never be two points with the same RD (I think it's impossible unless min_samples=2)? I don't think it's an edge case. After picking point 0 at the beginning, there're at least (n_samples-1) points with the same RD and these two implementations will choose different point unless the first point with smallest RD is closest to point 0. 
And yes, maybe we can carefully construct a test to avoid the difference, but honestly I don't like the idea. We compare our implementation with an existing implementation but seems that the output of our implementation is different even with the example provided by the existing implementation.
Awesome point @qinhanmin2014 , fair enough, Although I'm not sure why our generated RDs are identical to theirs. What's your proposal here?
Also, I don't think as far as checking the RD generated by the algorithm goes, the test is invalid. Maybe comparing it to another implementation which is incompatible with ours is invalid.
> Although I'm not sure why our generated RDs are identical to theirs.

I'd rather regard it as an coincidence. Actually, I'm not able to reproduce the test (i.e., I get different results even with current test).

> What's your proposal here?

Maybe remove the test. I'm not sure at this point. It's good to compare with other implementations but I think we need to ensure that the implementation we compare is the same as ours. 
Regardless of which implementation we're comparing with (or even if do compare with another implementation), I think that we want this test. All of the other tests check the output of the clusters-- this is the only test that directly verifies that the reachability distances aren't changing as people update code. I think that we need a test that verifies that our reachability distances are invariant from one release to the next...
So what's your proposal here @espg ?
Is there any reference/packages to support your implementation (i.e., choose the closest point when there're multiple point with the same RD)?
Things are getting more and more complex here. For the above example:
```
X = np.array([[ 15.,  70.], [ 31.,  87.], [ 45.,  32.], [ 32.,  83.],
              [ 26.,  50.], [  7.,  31.], [ 43.,  97.]])
```
We get another result from R dbscan:
```
# CD is the same
# RD from referenced implementation
# 0. , 38.89730068, 33.54101966, 37.33630941, 33.54101966...
# RD from our implementation
# inf, 33.54101966, 33.54101966, 38.89730068, 33.54101966 ...
# RD from R
# Inf 33.5410196624968 33.5410196624968 33.5410196624968 38.8973006775534...
# order from referenced implementation
# 0, 1, 3, 4, 2, 5, 6
# order from our implementation
# 0, 3, 1, 6, 4, 2, 5
# order from R
# 0 6 4 5 3 2 1
```
I'm not able to figure out how R works immediately.

Commit message: Add a test case for OPTICS bug (closes #12134)

Patch to review:
diff --git a/sklearn/cluster/tests/test_optics.py b/sklearn/cluster/tests/test_optics.py
index 5163504ab0401..3b01dec7ef35b 100755
--- a/sklearn/cluster/tests/test_optics.py
+++ b/sklearn/cluster/tests/test_optics.py
@@ -459,3 +459,11 @@ def test_precomputed_dists():
 
     assert_allclose(clust1.reachability_, clust2.reachability_)
     assert_array_equal(clust1.labels_, clust2.labels_)
+
+def test_processing_order():
+    """Unit test for bug in ca. version 0.20, see #12090"""
+    Y = [[0], [10], [-10], [25]]
+    clust = OPTICS(min_samples=3, max_eps=15).fit(Y)
+    assert_array_equal(clust.reachability_, [np.inf, 10, 10, 15])
+    assert_array_equal(clust.core_distances_, [10, 15, 20, 25])
+    assert_array_equal(clust.ordering_, [0, 1, 2, 3])


Code review comments:
diff_hunk: @@ -217,236 +216,168 @@ def test_cluster_sigmin_pruning(reach, n_child, members):
 
 
 def test_reach_dists():
-    # Tests against known extraction array
+    # Expected values, computed with ELKI using:
+    # java -jar elki.jar cli -dbc.in csv -dbc.filter FixedDBIDsFilter
+    #   -algorithm clustering.optics.OPTICSHeap -optics.minpts 5
+    # where the FixedDBIDsFilter gives 0-indexed ids.
+    r = [np.inf, 0.7865694338710508, 0.4373157299595305, 0.4121908069391695,
+         0.302907091394212, 0.20815674060999778, 0.20815674060999778,
+         0.15190193459676368, 0.15190193459676368, 0.28229645104833345,
+         0.302907091394212, 0.30507239477026865, 0.30820580778767087,
+         0.3289019667317037, 0.3458462228589966, 0.3458462228589966,
+         0.2931114364132193, 0.2931114364132193, 0.2562790168458507,
+         0.23654635530592025, 0.37903448688824876, 0.3920764620583683,
+         0.4121908069391695, 0.4364542226186831, 0.45523658462146793,
+         0.458757846268185, 0.458757846268185, 0.4752907412198826,
+         0.42350366820623375, 0.42350366820623375, 0.42350366820623375,
+         0.47758738570352993, 0.47758738570352993, 0.4776963110272057,
+         0.5272079288923731, 0.5591861752070968, 0.5592057084987357,
+         0.5609913790596295, 0.5909117211348757, 0.5940470220777727,
+         0.5940470220777727, 0.6861627576116127, 0.687795873252133,
+         0.7538541412862811, 0.7865694338710508, 0.8038180561910464,
+         0.8038180561910464, 0.8242451615289921, 0.8548361202185057,
+         0.8790098789921685, 2.9281214555815764, 1.3256656984284734,
+         0.19590944671099267, 0.1339924636672767, 0.1137384200258616,
+         0.061455005237474075, 0.061455005237474075, 0.061455005237474075,
+         0.045627777293497276, 0.045627777293497276, 0.045627777293497276,
+         0.04900902556283447, 0.061455005237474075, 0.06225461602815799,
+         0.06835750467748272, 0.07882900172724974, 0.07882900172724974,
+         0.07650735397943846, 0.07650735397943846, 0.07650735397943846,
+         0.07650735397943846, 0.07650735397943846, 0.07113275489288699,
+         0.07890196345324527, 0.07052683707634783, 0.07052683707634783,
+         0.07052683707634783, 0.08284027053523288, 0.08725436842020087,
+         0.08725436842020087, 0.09010229261951723, 0.09128578974358925,
+         0.09154172670176584, 0.0968576383038391, 0.12007572768323092,
+         0.12024155806196564, 0.12141990481584404, 0.1339924636672767,
+         0.13694322786307633, 0.14275793459246572, 0.15093125027309579,
+         0.17927454395170142, 0.18151803569400365, 0.1906028449191095,
+         0.1906028449191095, 0.19604486784973194, 0.2096539172540186,
+         0.2096539172540186, 0.21614333983312325, 0.22036454909290296,
+         0.23610322103910933, 0.26028003932256766, 0.2607126030060721,
+         0.2891824876072483, 0.3258089271514364, 0.35968687619960743,
+         0.4512973330510512, 0.4746141313843085, 0.5958585488429471,
+         0.6468718886525733, 0.6878453052524358, 0.6911582799500199,
+         0.7172169499815705, 0.7209874999572031, 0.6326884657912096,
+         0.5755681293026617, 0.5755681293026617, 0.5755681293026617,
+         0.6015042225447333, 0.6756244556376542, 0.4722384908959966,
+         0.08775739179493615, 0.06665303472021758, 0.056308477780164796,
+         0.056308477780164796, 0.05507767260835565, 0.05368146914586802,
+         0.05163427719303039, 0.05163427719303039, 0.05163427719303039,
+         0.04918757627098621, 0.04918757627098621, 0.05368146914586802,
+         0.05473720349424546, 0.05473720349424546, 0.048442038421760626,
+         0.048442038421760626, 0.04598840269934622, 0.03984301937835033,
+         0.04598840269934622, 0.04598840269934622, 0.04303884892957088,
+         0.04303884892957088, 0.04303884892957088, 0.0431802780806032,
+         0.0520412490141781, 0.056308477780164796, 0.05080724020124642,
+         0.05080724020124642, 0.05080724020124642, 0.06385565101399236,
+         0.05840878369200427, 0.0474472391259039, 0.0474472391259039,
+         0.04232512684465669, 0.04232512684465669, 0.04232512684465669,
+         0.0474472391259039, 0.051802632822946656, 0.051802632822946656,
+         0.05316405104684577, 0.05316405104684577, 0.05840878369200427,
+         0.06385565101399236, 0.08025248922898705, 0.08775739179493615,
+         0.08993337040710143, 0.08993337040710143, 0.08993337040710143,
+         0.08993337040710143, 0.297457175321605, 0.29763608186278934,
+         0.3415255849656254, 0.34713336941105105, 0.44108940848708167,
+         0.35942962652965604, 0.35942962652965604, 0.33609522256535296,
+         0.5008111387107295, 0.5333587622018111, 0.6223243743872802,
+         0.6793840035409552, 0.7445032492109848, 0.7445032492109848,
+         0.6556432627279256, 0.6556432627279256, 0.6556432627279256,
+         0.8196566935960162, 0.8724089149982351, 0.9352758042365477,
+         0.9352758042365477, 1.0581847953137133, 1.0684332509194163,
+         1.0887817699873303, 1.2552604310322708, 1.3993856001769436,
+         1.4869615658197606, 1.6588098267326852, 1.679969559453028,
+         1.679969559453028, 1.6860509219163458, 1.6860509219163458,
+         1.1465697826627317, 0.992866533434785, 0.7691908270707519,
+         0.578131499171622, 0.578131499171622, 0.578131499171622,
+         0.5754243919945694, 0.8416199360035114, 0.8722493727270406,
+         0.9156549976203665, 0.9156549976203665, 0.7472322844356064,
+         0.715219324518981, 0.715219324518981, 0.715219324518981,
+         0.7472322844356064, 0.820988298336316, 0.908958489674247,
+         0.9234036745782839, 0.9519521817942455, 0.992866533434785,
+         0.992866533434785, 0.9995692674695029, 1.0727415198904493,
+         1.1395519941203158, 1.1395519941203158, 1.1741737271442092,
+         1.212860115632712, 0.8724097897372123, 0.8724097897372123,
+         0.8724097897372123, 1.2439272570611581, 1.2439272570611581,
+         1.3524538390109015, 1.3524538390109015, 1.2982303284415664,
+         1.3610655849680207, 1.3802783392089437, 1.3802783392089437,
+         1.4540636953090629, 1.5879329500533819, 1.5909193228826986,
+         1.72931779186001, 1.9619075944592093, 2.1994355761906257,
+         2.2508672067362165, 2.274436122235927, 2.417635732260135,
+         3.014235905390584, 0.30616929141177107, 0.16449675872754976,
+         0.09071681523805683, 0.09071681523805683, 0.09071681523805683,
+         0.08727060912039632, 0.09151721189581336, 0.12277953408786725,
+         0.14285575406641507, 0.16449675872754976, 0.16321992344119793,
+         0.1330971730344373, 0.11429891993167259, 0.11429891993167259,
+         0.11429891993167259, 0.11429891993167259, 0.11429891993167259,
+         0.0945498340011516, 0.11410457435712089, 0.1196414019798306,
+         0.12925682285016715, 0.12925682285016715, 0.12925682285016715,
+         0.12864887158869853, 0.12864887158869853, 0.12864887158869853,
+         0.13369634918690246, 0.14330826543275352, 0.14877705862323184,
+         0.15203263952428328, 0.15696350160889708, 0.1585326700393211,
+         0.1585326700393211, 0.16034306786654595, 0.16034306786654595,
+         0.15053328296567992, 0.16396729418886688, 0.16763548009617293,
+         0.1732029325454474, 0.21163390061029352, 0.21497664171864372,
+         0.22125889949299, 0.240251070192081, 0.240251070192081,
+         0.2413620965310808, 0.26319419022234064, 0.26319419022234064,
+         0.27989712380504483, 0.2909782800714374]
+    o = [0, 3, 6, 7, 15, 4, 27, 28, 49, 17, 35, 47, 46, 39, 13, 19,
+         22, 29, 30, 38, 34, 32, 43, 8, 25, 9, 37, 23, 33, 40, 44, 11, 36, 5,
+         45, 48, 41, 26, 24, 20, 31, 2, 16, 10, 18, 14, 42, 12, 1, 21, 234,
+         132, 112, 115, 107, 110, 120, 114, 100, 131, 137, 145, 130, 121, 134,
+         116, 149, 108, 111, 113, 142, 148, 119, 104, 126, 133, 138, 127, 101,
+         105, 103, 106, 125, 140, 123, 147, 144, 129, 141, 117, 143, 136, 128,
+         122, 124, 102, 109, 249, 146, 118, 135, 245, 139, 224, 241, 217, 202,
+         248, 233, 214, 236, 211, 206, 231, 212, 221, 229, 244, 208, 226, 83,
+         76, 53, 77, 88, 62, 66, 65, 89, 93, 79, 95, 74, 70, 82, 51, 73, 87,
+         67, 94, 56, 52, 63, 80, 75, 57, 96, 60, 69, 90, 86, 58, 68, 81, 64,
+         84, 85, 97, 59, 98, 61, 71, 78, 92, 50, 91, 55, 54, 72, 99, 210, 201,
+         216, 239, 203, 218, 219, 222, 240, 294, 243, 246, 204, 220, 200, 215,
+         230, 225, 205, 207, 237, 223, 235, 209, 228, 238, 227, 285, 232, 256,
+         281, 270, 260, 252, 272, 268, 292, 298, 269, 275, 257, 250, 284, 283,
+         286, 295, 297, 293, 289, 258, 299, 282, 262, 296, 287, 267, 255, 263,
+         288, 276, 251, 266, 274, 271, 277, 261, 279, 290, 253, 254, 291, 259,
+         280, 278, 273, 247, 265, 242, 264, 213, 199, 174, 154, 152, 180, 186,
+         195, 170, 181, 176, 187, 173, 157, 159, 158, 172, 182, 183, 151, 197,
+         177, 160, 156, 171, 175, 184, 193, 161, 179, 196, 185, 192, 165, 166,
+         164, 189, 155, 162, 188, 153, 178, 169, 194, 150, 163, 198, 190, 191,
+         168, 167]
+    p = [-1, 0, 3, 6, 7, 15, 15, 27, 27, 4, 7, 49, 47, 4, 39, 39,
+         19, 19, 29, 30, 30, 13, 6, 43, 34, 32, 32, 25, 23, 23, 23, 3, 11, 46,
+         46, 45, 9, 38, 33, 26, 26, 8, 20, 33, 0, 18, 18, 2, 18, 44, 0, 234,
+         132, 112, 115, 107, 107, 120, 114, 114, 114, 114, 107, 100, 100, 134,
+         134, 149, 149, 108, 108, 108, 148, 113, 104, 104, 104, 142, 127, 127,
+         126, 138, 126, 148, 127, 148, 127, 112, 147, 116, 117, 101, 145, 128,
+         128, 122, 136, 136, 249, 102, 102, 118, 143, 146, 245, 123, 139, 241,
+         241, 217, 248, 202, 248, 224, 231, 212, 212, 212, 229, 229, 226, 83,
+         76, 53, 53, 88, 62, 66, 66, 66, 93, 93, 79, 93, 70, 82, 82, 73, 87,
+         73, 94, 56, 56, 56, 63, 67, 53, 96, 96, 96, 69, 86, 58, 58, 81, 81,
+         81, 58, 64, 64, 59, 59, 86, 69, 78, 83, 84, 55, 55, 55, 72, 50, 201,
+         210, 216, 203, 203, 219, 54, 240, 239, 240, 236, 236, 220, 220, 220,
+         217, 139, 243, 243, 204, 211, 246, 215, 223, 294, 209, 227, 227, 209,
+         281, 270, 260, 252, 272, 272, 272, 298, 269, 298, 275, 275, 284, 283,
+         283, 283, 284, 286, 283, 298, 299, 260, 260, 250, 299, 258, 258, 296,
+         250, 276, 276, 276, 289, 289, 267, 267, 279, 261, 277, 277, 258, 266,
+         290, 209, 207, 290, 228, 278, 228, 290, 199, 174, 154, 154, 154, 186,
+         186, 180, 170, 174, 187, 173, 157, 159, 157, 157, 159, 183, 183, 172,
+         197, 160, 160, 171, 171, 171, 151, 173, 184, 151, 196, 185, 185, 179,
+         179, 189, 177, 165, 175, 162, 164, 181, 169, 169, 181, 178, 178, 178,
+         168]
 
-    clust = OPTICS(min_samples=10, metric='minkowski').fit(X)
-
-    # Expected values, matches 'RD' results from:
-    # http://chemometria.us.edu.pl/download/optics.py
-
-    v = [np.inf, 0.606005, 0.472013, 0.162951, 0.161000, 0.385547, 0.179715,
-         0.213507, 0.348468, 0.308146, 0.560519, 0.266072, 0.764384, 0.253164,
-         0.435716, 0.153696, 0.363924, 0.194267, 0.392313, 0.230589, 0.260023,
-         0.535348, 0.168173, 0.296736, 0.310583, 0.277204, 0.250654, 0.153696,
-         0.215533, 0.175710, 0.168173, 0.283134, 0.256372, 0.313931, 0.234164,
-         0.179715, 0.352957, 0.277052, 0.180986, 0.203819, 0.296022, 0.356691,
-         0.515438, 0.219208, 0.265821, 0.346630, 0.275305, 0.229332, 0.433715,
-         0.153696, 0.584960, 0.265821, 0.471049, 0.259154, 0.461707, 0.400021,
-         0.422748, 0.300699, 0.162951, 0.290504, 0.315199, 0.327130, 0.168864,
-         0.462826, 0.188862, 0.259784, 0.216788, 0.259784, 0.195673, 0.315199,
-         0.313931, 0.189128, 0.461707, 0.265821, 0.233594, 0.433715, 0.222260,
-         0.251734, 0.352957, 0.218134, 0.453792, 0.179715, 0.296736, 0.260023,
-         0.311162, 0.214549, 0.266072, 0.318744, 0.180986, 0.194267, 0.262882,
-         0.420186, 0.352957, 0.288388, 0.360962, 0.328054, 0.293849, 0.198271,
-         0.248772, 0.461707, 0.216788, 0.396450, 0.352957, 0.289448, 0.241311,
-         0.213742, 0.220516, 0.218134, 0.153696, 0.516090, 0.218134, 0.221507,
-         0.328647, 0.255933, 0.195766, 0.233594, 0.205270, 0.296736, 0.726008,
-         0.251991, 0.168173, 0.214027, 0.262882, 0.342089, 0.260023, 0.266072,
-         0.253164, 0.230345, 0.262882, 0.296022, 0.227047, 0.205974, 0.328647,
-         0.184315, 0.196304, 0.831185, 0.514116, 0.168173, 0.189784, 0.664306,
-         0.327130, 0.379139, 0.208932, 0.266140, 0.362751, 0.168173, 0.764384,
-         0.327130, 0.187107, 0.194267, 0.414196, 0.251734, 0.220516, 0.363924,
-         0.166886, 0.327130, 0.233594, 0.203819, 0.230589, 0.203819, 0.222972,
-         0.311526, 0.218134, 0.422748, 0.314870, 0.315199, 0.315199, 0.594179,
-         0.328647, 0.415638, 0.244046, 0.250654, 0.214027, 0.203819, 0.213507,
-         0.260023, 0.311442, 0.168173, 0.389432, 0.229343, 0.162951, 0.311162,
-         0.153696, 0.214027, 0.250654, 0.315199, 0.172484, 0.153696, 0.352957,
-         0.314870, 0.328647, 0.546505, 0.378118, 0.260023, 0.387830, 0.199714,
-         0.262882, 0.250654, 0.345254, 0.396450, 0.250654, 0.179715, 0.328647,
-         0.179715, 0.263104, 0.265821, 0.231714, 0.514116, 0.213507, 0.474255,
-         0.212568, 0.376760, 0.196304, 0.844945, 0.194267, 0.264914, 0.210320,
-         0.316374, 0.184315, 0.179715, 0.250654, 0.153696, 0.162951, 0.315199,
-         0.179965, 0.297876, 0.213507, 0.475420, 0.439372, 0.241311, 0.260927,
-         0.194267, 0.422748, 0.222260, 0.411940, 0.414733, 0.260923, 0.396450,
-         0.380672, 0.333277, 0.290504, 0.196014, 0.844945, 0.506989, 0.153696,
-         0.218134, 0.392313, 0.698970, 0.168173, 0.227047, 0.028856, 0.033243,
-         0.028506, 0.057003, 0.038335, 0.051183, 0.063923, 0.022363, 0.030677,
-         0.036155, 0.017748, 0.062887, 0.036041, 0.051183, 0.078198, 0.068936,
-         0.032418, 0.040634, 0.022188, 0.022112, 0.036858, 0.040199, 0.025549,
-         0.083975, 0.032209, 0.025525, 0.032952, 0.034727, 0.068887, 0.040634,
-         0.048985, 0.047450, 0.022422, 0.023767, 0.028092, 0.047450, 0.029202,
-         0.026105, 0.030542, 0.032250, 0.062887, 0.038335, 0.026753, 0.028092,
-         0.099391, 0.021430, 0.020496, 0.021430, 0.025043, 0.023868, 0.050069,
-         0.023868, 0.044140, 0.038032, 0.022112, 0.044140, 0.031528, 0.028092,
-         0.020065, 0.055926, 0.031508, 0.025549, 0.028062, 0.036155, 0.023694,
-         0.029423, 0.026105, 0.028497, 0.023868, 0.044808, 0.035783, 0.033090,
-         0.038779, 0.032146, 0.038421, 0.057328, 0.020065, 0.020065, 0.028858,
-         0.021337, 0.041226, 0.022507, 0.028506, 0.030257, 0.057912, 0.050876,
-         0.120109, 0.020065, 0.034727, 0.038596, 0.037008, 0.031609, 0.095640,
-         0.083728, 0.064906, 0.030677, 0.057003, 0.037008, 0.018705, 0.030677,
-         0.044140, 0.034727, 0.045226, 0.032146, 0.032418, 0.029332, 0.030104,
-         0.033243, 0.030104, 0.032209, 0.026405, 0.024092, 0.048441, 0.036379,
-         0.030745, 0.023454, 0.018705, 0.124248, 0.041114, 0.020700, 0.042633,
-         0.042455, 0.028497, 0.029202, 0.057859, 0.053157, 0.036155, 0.029534,
-         0.032209, 0.038032, 0.024617, 0.023071, 0.033090, 0.023694, 0.047277,
-         0.024617, 0.023868, 0.043916, 0.025549, 0.046198, 0.041086, 0.042003,
-         0.022507, 0.021430, 0.038779, 0.025043, 0.036379, 0.036326, 0.029421,
-         0.023454, 0.058683, 0.025549, 0.039904, 0.022507, 0.046198, 0.029332,
-         0.032209, 0.036155, 0.038421, 0.025043, 0.023694, 0.030104, 0.022363,
-         0.048544, 0.035180, 0.030677, 0.022112, 0.030677, 0.036678, 0.022507,
-         0.024092, 0.064231, 0.022507, 0.032209, 0.025043, 0.221152, 0.029840,
-         0.038779, 0.040634, 0.024617, 0.032418, 0.025525, 0.033298, 0.028092,
-         0.045754, 0.032209, 0.017748, 0.033090, 0.017748, 0.048931, 0.038689,
-         0.022112, 0.027129, 0.032952, 0.036858, 0.027704, 0.032146, 0.052191,
-         0.042633, 0.071638, 0.044140, 0.022507, 0.046647, 0.028270, 0.050525,
-         0.036772, 0.058995, 0.038335, 0.025185, 0.022507, 0.040293, 0.032418,
-         0.064308, 0.026023, 0.036155, 0.032418, 0.038032, 0.018705, 0.040293,
-         0.030104, 0.030845, 0.064906, 0.025525, 0.036155, 0.022507, 0.022363,
-         0.032418, 0.021430, 0.032209, 0.102770, 0.036960, 0.031062, 0.025043,
-         0.036155, 0.031609, 0.036379, 0.030845, 0.048985, 0.021848, 0.025549,
-         0.022507, 0.035783, 0.023698, 0.034422, 0.032418, 0.022507, 0.023868,
-         0.020065, 0.023694, 0.040634, 0.055633, 0.054549, 0.044662, 0.087660,
-         0.048066, 0.143571, 0.068669, 0.065049, 0.076927, 0.044359, 0.041577,
-         0.052364, 0.100317, 0.062146, 0.067578, 0.054549, 0.047239, 0.062809,
-         0.033917, 0.087660, 0.077113, 0.055633, 0.061854, 0.059756, 0.059537,
-         0.052364, 0.060347, 0.170251, 0.108492, 0.046370, 0.070684, 0.049589,
-         0.044662, 0.049013, 0.043303, 0.069573, 0.075044, 0.054354, 0.065072,
-         0.073135, 0.046126, 0.055569, 0.047239, 0.062146, 0.056093, 0.059986,
-         0.096182, 0.100317, 0.051649, 0.054354, 0.077420, 0.100317, 0.046370,
-         0.043303, 0.045845, 0.061422, 0.091580, 0.206234, 0.051405, 0.071684,
-         0.061574, 0.063666, 0.052692, 0.051649, 0.100124, 0.077909, 0.033917,
-         0.058680, 0.044359, 0.065498, 0.080214, 0.123231, 0.052957, 0.056582,
-         0.061540, 0.076794, 0.043303, 0.054884, 0.044359, 0.145249, 0.081741,
-         0.041577, 0.056093, 0.076799, 0.044359, 0.068483, 0.051649, 0.092275,
-         0.044359, 0.108492, 0.092275, 0.046126, 0.106422, 0.054354, 0.052957,
-         0.073329, 0.046126, 0.086402, 0.048194, 0.128569, 0.104042, 0.061854,
-         0.069573, 0.070035, 0.050346, 0.043303, 0.053576, 0.054549, 0.033917,
-         0.063666, 0.058680, 0.099130, 0.080198, 0.050118, 0.054549, 0.041577,
-         0.143571, 0.095965, 0.047643, 0.052364, 0.105168, 0.048685, 0.043303,
-         0.052814, 0.076927, 0.054549, 0.041577, 0.066657, 0.189930, 0.046370,
-         0.075044, 0.121331, 0.043303, 0.223897, 0.198621, 0.150328, 0.100317,
-         0.053576, 0.070708, 0.100898, 0.047239, 0.043613, 0.065049, 0.049146,
-         0.068669, 0.055569, 0.062124, 0.096408, 0.044662, 0.087660, 0.083012,
-         0.050118, 0.069573, 0.046126, 0.049146, 0.049146, 0.050808, 0.080198,
-         0.059986, 0.071974, 0.047239, 0.050808, 0.059986, 0.065850, 0.044863,
-         0.052814, 0.044359, 0.052364, 0.108492, 0.143571, 0.050926, 0.049146,
-         0.049146, 0.055569, 0.033917, 0.527659, 0.143547, 0.077113, 0.046126,
-         0.106422, 0.068669, 0.108492, 0.063666, 0.054549, 0.054884, 0.056907,
-         0.068669, 0.080198, 0.120887, 0.054549, 0.052692, 0.085801, 0.054884,
-         0.050808, 0.094595, 0.059545, 0.054354, 0.062124, 0.087660, 0.052814,
-         0.086715, 0.146253, 0.046370, 0.041577, 0.116083, 0.076927, 0.047239,
-         0.084375, 0.134652, 0.217969, 0.063559, 0.061540, 0.044662, 0.054354,
-         0.063666, 0.145466, 0.101700, 0.090491, 0.078536, 0.054884, 0.062124,
-         0.041577, 0.043303, 0.194473, 0.079780, 0.059704, 0.054780, 0.048194,
-         0.062146, 0.069573, 0.086898, 0.046675, 0.056258, 0.074141, 0.048066,
-         0.052957, 0.057982, 0.058966, 0.061048, 0.050885, 0.049146, 0.080993,
-         0.056093, 0.061854, 0.124025, 0.062146, 0.060906, 0.150328, 0.058680,
-         0.077420, 0.051800, 0.102359, 0.113301, 0.073096, 0.116715, 0.131476,
-         0.140601, 0.097667, 0.051800, 0.051800, 0.127964, 0.108870, 0.111926,
-         0.093532, 0.102390, 0.144266, 0.098271, 0.102541, 0.136497, 0.127964,
-         0.085569, 0.157863, 0.096739, 0.054008, 0.106219, 0.076838, 0.099076,
-         0.093532, 0.059861, 0.079975, 0.116715, 0.133625, 0.053641, 0.066110,
-         0.122302, 0.081313, 0.140601, 0.259889, 0.094437, 0.098271, 0.105776,
-         0.225742, 0.100097, 0.147592, 0.099076, 0.093128, 0.093532, 0.134946,
-         0.133625, 0.120869, 0.065932, 0.103395, 0.125172, 0.147842, 0.105278,
-         0.173584, 0.168241, 0.111524, 0.093532, 0.099076, 0.100426, 0.137132,
-         0.065356, 0.091108, 0.141202, 0.054008, 0.075298, 0.073717, 0.122817,
-         0.105278, 0.094437, 0.067080, 0.108530, 0.115467, 0.093532, 0.085569,
-         0.145180, 0.100426, 0.116715, 0.151726, 0.073096, 0.193781, 0.090614,
-         0.081162, 0.051800, 0.133625, 0.136497, 0.100670, 0.081313, 0.506893,
-         0.084567, 0.108530, 0.087353, 0.063184, 0.123639, 0.168333, 0.314422,
-         0.091108, 0.079975, 0.091108, 0.136497, 0.122302, 0.167297, 0.067080,
-         0.144266, 0.065932, 0.087667, 0.100426, 0.099460, 0.091108, 0.100637,
-         0.116715, 0.079975, 0.077977, 0.090340, 0.136723, 1.943026, 0.108870,
-         0.090340, 0.065932, 0.102245, 0.157863, 0.157863, 0.215574, 0.156830,
-         0.093532, 0.122302, 0.097667, 0.063000, 0.116715, 0.076838, 0.148372,
-         0.093532, 0.099076, 0.141202, 0.096505, 0.096739, 0.091108, 0.099076,
-         0.079975, 0.108870, 0.102390, 0.079975, 0.244121, 0.167071, 0.096739,
-         0.102390, 0.103395, 0.073096, 0.094887, 0.065932, 0.190667, 0.099460,
-         0.102390, 0.096739, 0.102390, 0.116715, 0.100637, 0.256554, 0.103395,
-         0.081313, 0.068962, 0.109645, 0.059364, 0.147842, 0.099460, 0.079262,
-         0.099460, 0.065932, 0.123687, 0.090614, 0.131352, 0.098271, 0.102541,
-         0.098983, 0.057224, 0.074797, 0.057224, 0.250559, 0.079975, 0.103395,
-         0.100426, 0.065932, 0.120661, 0.079262, 0.065932, 0.118665, 0.081162,
-         0.066283, 0.099076, 0.102359, 0.108530, 0.079975, 0.168333, 0.096739,
-         0.168333, 0.097008, 0.055288, 0.172411, 0.092801, 0.051800, 0.102541,
-         0.084567, 0.054008, 0.090991, 0.172411, 0.057224, 0.148396, 0.200965,
-         0.076838, 0.157863, 0.053535, 0.121919, 0.126609, 0.123890, 0.118081,
-         0.097008, 0.125311, 0.099460, 0.122302, 0.134946, 0.080975, 0.084567,
-         0.110093, 0.102245, 0.103395, 0.171601, 0.094887, 0.126240, 0.137742,
-         0.099954, 0.108530, 0.157863, 0.096739, 0.051800, 0.127964, 0.066110,
-         0.061021, 0.105147, 0.100426, 0.079975, 0.088187, 0.116421, 0.076838,
-         0.098271, 0.116715, 0.137656, 0.075298, 0.148396, 0.112166, 1.083905,
-         0.326598, 0.428987, 0.395963, 0.224541, 0.326598, 0.030677, 0.410454,
-         0.122771, 1.140305, 0.641074, 0.432159, 0.429335, 0.422908, 0.461926,
-         0.293083, 0.477078, 0.714856, 0.515861, 0.405418, 0.054354, 0.341177,
-         0.410008, 0.514245, 0.641074, 0.816459, 0.455115, 0.400707, 0.382240,
-         0.431832, 1.618970, 0.683953, 0.182992, 0.763699, 0.515861, 0.717145,
-         0.409629, 0.074134, 0.398273, 0.864974, 0.400707, 0.591403, 0.435354,
-         0.514245, 1.337152, 0.841077, 0.410008, 0.683953, 0.338649, 0.557595,
-         0.442092, 0.326598, 0.984189, 0.429608, 0.395963, 1.152055, 0.587222,
-         1.748492, 0.477078, 0.395459, 0.717145, 0.575811, 0.210115, 0.487785,
-         0.431832, 0.383852, 0.806708, 0.428987, 0.278405, 0.395963, 0.395459,
-         0.383852, 1.083905, 0.428510, 0.326598, 0.108492, 0.541644, 0.612110,
-         0.382240, 0.833511, 0.382240, 0.456628, 0.326598, 0.458880, 0.398273,
-         0.957748, 0.326598, 0.295049, 0.629646, 0.429765, 0.439942, 0.633617,
-         0.566297, 0.429335, 0.086507, 0.477078, 0.526753, 0.375240, 0.584436,
-         0.355776, 0.395963, 0.644924, 0.129793, 0.484880, 0.470001, 0.572306,
-         0.383852, 1.110081, 0.841077, 0.395963, 0.683953, 0.428745, 0.387752,
-         0.545299, 0.686537, 0.635219, 0.840499, 0.527659, 0.400707, 0.480982,
-         0.541644, 0.714856, 0.942673, 0.398273, 0.428987, 0.356781, 0.428510,
-         1.140961, 0.395963, 0.356781, 0.410454, 0.541644, 0.641074, 0.484778,
-         0.410008, 0.433108, 0.278405, 0.278405, 0.503141, 0.428745, 0.125103,
-         0.633617, 0.410454, 0.124025, 0.461926, 0.398273, 0.410008, 1.181303,
-         0.635219, 0.593537, 0.395963, 0.717145, 0.409629, 0.492595, 0.806708,
-         0.503820, 0.423834, 0.557595, 0.429335, 0.470749, 0.461926, 1.890036,
-         0.236343, 0.806708, 0.123561, 0.433744, 0.427348, 0.427348, 0.962234,
-         0.395963, 0.409629, 0.527659, 0.425727, 0.602549, 0.901331, 0.326598,
-         0.635949, 0.541644, 0.375240, 0.598969, 1.140961, 0.391998, 0.719443,
-         0.410008, 0.515861, 0.714856, 0.842273, 0.410454, 0.389377, 0.431078,
-         0.515861, 0.515861, 0.429335, 0.332495, 0.398273, 0.428987, 0.635219,
-         0.387752, 0.384289, 0.383852, 0.430504, 0.428510, 0.431832, 0.375240,
-         0.278405, 0.374102, 0.428745, 0.692878, 1.152055, 0.503820, 0.428745,
-         0.352868, 0.429335, 0.375240, 0.400707, 0.427348, 0.256183, 0.962234,
-         0.505376, 0.058995, 0.410454, 0.172880, 0.395963, 0.470749, 0.356781,
-         1.332700, 0.683953, 0.395963, 0.806708, 0.400707, 0.330982, 0.427731,
-         0.934845, 0.375240, 0.191534, 0.047239, 1.083905, 0.348794, 0.409708,
-         0.503820, 0.557595, 0.429335, 0.498780, 0.293083, 0.363069, 0.442092,
-         1.152055, 0.375240, 0.335677, 0.452443, 0.655156, 0.929928, 0.614869,
-         1.411031, 1.101132, 0.469030, 0.404976, 0.538209, 0.655828, 0.674748,
-         0.365182, 0.641612, 0.555434, 0.521651, 0.386679, 0.386679, 0.980304,
-         0.659111, 0.651366, 0.538209, 0.521651, 0.884780, 1.287829, 0.558322,
-         0.446161, 0.817970, 0.568499, 0.533507, 0.639746, 0.484404, 0.591751,
-         0.913016, 0.446161, 0.533907, 0.606885, 0.672320, 1.150642, 0.655828,
-         0.365182, 0.665088, 1.094242, 0.629401, 0.540676, 0.733026, 1.248265,
-         1.273499, 0.867854, 0.538656, 0.386679, 0.922273, 0.515686, 1.321022,
-         0.624444, 0.655828, 0.922273, 0.386679, 0.762191, 0.779432, 0.601851,
-         0.655156, 0.926213, 0.762191, 0.641612, 0.558322, 1.025370, 0.641067,
-         0.651366, 0.633434, 0.459580, 0.859221, 0.552291, 0.591751, 0.819965,
-         0.669977, 1.185083, 0.499338, 0.533907, 0.752871, 0.571388, 0.539772,
-         0.449182, 1.025370, 0.365182, 1.321022, 0.926213, 0.886360, 0.562272,
-         0.669977, 0.796046, 0.557598, 0.596776, 0.672336, 0.659111, 0.453719,
-         0.477716, 0.477716, 1.592069, 0.591751, 0.539772, 0.641612, 0.946254,
-         0.744165, 0.386679, 0.593825, 0.539772, 0.449182, 0.604273, 0.794951,
-         0.752871, 0.539772, 0.648732, 0.469030, 0.665088, 1.332700, 1.341388,
-         0.533507, 0.544212, 1.025992, 0.645967, 0.612945, 0.868492, 0.648732,
-         0.752300, 0.624444, 1.219748, 0.446161, 0.520818, 0.469044, 0.669977,
-         0.926213, 0.638752, 0.762191, 0.922273, 0.794951, 0.606885, 0.669977,
-         0.550113, 0.641067, 0.733026, 0.604273, 0.648732, 0.533507, 0.746506,
-         0.733026, 0.980683, 0.538209, 0.669977, 0.469030, 0.648732, 0.609190,
-         1.219748, 0.373113, 0.539772, 1.744047, 1.004716, 0.926213, 0.562272,
-         0.752871, 0.538656, 0.449182, 0.365182, 0.469030, 0.446161, 0.484404,
-         0.768592, 0.648732, 0.655156, 0.521651, 0.779432, 0.446161, 0.596776,
-         0.538209, 0.726740, 0.539772, 0.469030, 0.521651, 0.561950, 0.601851,
-         0.533907, 0.922273, 1.248265, 0.476800, 0.737990, 0.817970, 0.792127,
-         0.533907, 0.486038, 0.624444, 0.798241, 0.476800, 1.059373, 0.645967,
-         0.619940, 0.528726, 0.669977, 0.865406, 0.980683, 0.980683, 0.834671,
-         1.001353, 0.752871, 0.449182, 1.096520, 0.449182, 0.593825, 0.636558,
-         0.762191, 0.638591, 0.538209, 0.865406, 0.779432, 0.469044, 0.645967,
-         0.557598, 0.499338, 0.484404, 0.515686, 0.794951, 0.619456, 0.733026,
-         0.821769, 0.752300, 0.643302, 0.636558, 0.655156, 0.655156, 0.484404,
-         0.648732, 0.726023, 0.365182, 0.606885, 0.499338, 0.520818, 0.612945,
-         0.446161, 0.557598, 0.469044, 1.134650, 0.629401, 0.538656, 0.561950,
-         1.364861, 0.459580, 1.025370, 0.980304, 0.607592, 0.533907, 1.134650,
-         0.446161, 0.629962]
-
-    # FIXME: known failure in 32bit Linux; numerical imprecision results in
-    # different ordering in quick_scan
-    if _IS_32BIT:  # pragma: no cover
-        assert_allclose(clust.reachability_, np.array(v), rtol=1e-2)
-    else:
-        # we compare to truncated decimals, so use atol
-        assert_allclose(clust.reachability_, np.array(v), atol=1e-5)
+    # Tests against known extraction array
+    # Does NOT work with "euclidean", because sklearn euclidean has worse
+    # numerics
+    clust = OPTICS(min_samples=5, metric='minkowski').fit(X)
+
+    # we compare to truncated decimals, so use atol
+    assert_array_equal(clust.ordering_, np.array(o))
+    assert_array_equal(clust.predecessor_[clust.ordering_], np.array(p))
+    assert_allclose(clust.reachability_[clust.ordering_],
+                    np.array(r), atol=1e-15)
path: sklearn/cluster/tests/test_optics.py
text: @user1:
I guess we don't need such a high precision here? I'm not an expert on these things but I think there might be some unexpected numeric issues in other environments (we only test some environments here). Maybe using the default value provided by ``assert_allclose``?

diff_hunk: @@ -459,3 +390,12 @@ def test_precomputed_dists():
 
     assert_allclose(clust1.reachability_, clust2.reachability_)
     assert_array_equal(clust1.labels_, clust2.labels_)
+
+
+def test_processing_order():
+    """Unit test for bug in ca. version 0.20, see #12090"""
path: sklearn/cluster/tests/test_optics.py
text: @user1:
I guess we can remove this comment. This is not a bug because OPTICS is not released.

@author:
I'd keep the issue number in there, in case someone wonders where this test case comes from.
How about naming this test_processing_order_issue12090 and dropping the comment?

@user1:
Maybe remove ``bug`` and ``version 0.20`` ? It's not a bug in 0.20. Another thing is that this one is actually a different bug, so I doubt whether it's good to link to #12090.

diff_hunk: @@ -217,236 +216,168 @@ def test_cluster_sigmin_pruning(reach, n_child, members):
 
 
 def test_reach_dists():
path: sklearn/cluster/tests/test_optics.py
text: @user1:
This name is no longer valid, replace it with ``test_optics_ELKI`` or anything you like.