Simple implementation of DBSCAN in python with scikit-learn

DBSCAN.py

import numpy as np
import matplotlib.pyplot as plt
from sklearn.neighbors import NearestNeighbors

def get_eps_nei(neigh, X, i):
    """ Wrap the unnecessary output from sklearn.
    Returns the indices of the k nearest neigbhors of a point,
    excluding the query point.
    """
    e = list(neigh.radius_neighbors(X[i].reshape(1, -1),
               return_distance=False)[0])

    e_filter = [j for j in e if j !=i]
    return e_filter


def my_dbscan(X, eps=0.3, min_pts=4):
    """ My implementation of DBSCAN.
    
    Pseudocode:
        * For each unseen point, get its density
        * If too sparse, mark as noise
        * If dense enough start a new cluster
            * Mark all its neighbourhood with cluster.
            * For each point in neighbourhood, add neighbors if they are core
        * Stop if no new unvisited points
    
    Arguments
    -----------
    X: np Nxd array
    eps: radius of neighbourhood
    min_pts: minimum neighbourhood size
    
    Returns
    --------
    list:
        List of n elements with cluster assignments for each point in X. -1 for noise, 1,2..,k for clusters.
    
    """
    n_pts = X.shape[0]
    neigh = NearestNeighbors(radius=eps)
    neigh.fit(X)
    
    # 0 is undefined
    # -1 is noise
    # >=1 is cluster ID
    clusters = [0] * n_pts
    
    cluster_id = 1
    for i in range(n_pts):
        N = get_eps_nei(neigh, X, i)
        # we already saw this point
        if clusters[i] != 0:
            continue
        # noise
        if len(N) < min_pts:
            clusters[i] = -1
            continue
        # we are in a dense region
        if len(N) >= min_pts:
            clusters[i] = cluster_id
            while len(N):
                n = N.pop()
                # this was a noise point but now it is border
                if clusters[n] == -1:
                    clusters[n] = cluster_id
                    continue
                # already clustered
                if clusters[n] > 0:
                    continue
                # check unprocessed or noise points
                clusters[n] = cluster_id
                Q = get_eps_nei(neigh, X, n)
                if len(Q) >= min_pts:
                    N.extend(Q)
        cluster_id += 1
            
    return clusters

def draw(X, clusts):
  colors = np.array(['tab:blue','tab:orange','tab:green','tab:red','tab:purple','tab:brown','tab:pink','tab:gray','tab:olive','tab:cyan','black'])
  # matplotlib tableau palette, plus black for outliers
  colors = np.hstack([colors] * 20)
  fig = plt.figure(figsize=(10,10))
  ax = plt.gca()
  ax.scatter(X[:, 0], X[:, 1], c=colors[clusts].tolist(), s=10)
  plt.show()

############

X = np.loadtxt('smile.txt')
my_clusts = my_dbscan(X, eps=0.1)
draw(X, my_clusts)

requirements.txt

matplotlib
numpy
scikit-learn

smile.txt

1.088203 0.020008
1.048858 0.124636
1.093061 -0.023683
1.046791 0.030198
0.993571 0.070875
1.005221 0.135630
1.035199 0.081561
1.018311 0.104711
1.069635 0.090304
1.009239 0.070377
0.864434 0.158264
1.033645 0.100956
1.102094 0.077806
0.988921 0.153601
1.061142 0.248838
0.989964 0.206660
0.935385 0.101065
0.959782 0.220243
1.035940 0.284831
0.952152 0.221849
0.916030 0.178177
0.879930 0.358891
0.936394 0.251581
0.895717 0.324449
0.873990 0.286982
0.906088 0.328961
0.921348 0.262532
0.941355 0.354877
0.941816 0.360428
0.902352 0.338957
0.895875 0.350849
0.884123 0.294187
0.928787 0.372026
0.833396 0.426806
0.864386 0.417752
0.940906 0.433026
0.955979 0.376190
0.913540 0.414975
0.844156 0.431487
0.866251 0.474379
0.817563 0.527677
0.892958 0.416813
0.937803 0.599331
0.915908 0.506372
0.796874 0.578840
0.823561 0.597906
0.847308 0.596196
0.847755 0.593187
0.823371 0.657558
0.821972 0.598679
0.902434 0.521416
0.737274 0.647404
0.734537 0.706151
0.764782 0.581536
0.873755 0.702775
0.863008 0.683793
0.718468 0.743634
0.739908 0.697791
0.792330 0.659350
0.767213 0.722538
0.746755 0.630678
0.734155 0.761078
0.675709 0.696278
0.679763 0.805113
0.726106 0.741799
0.644857 0.757051
0.640389 0.740226
0.632960 0.780885
0.684123 0.744960
0.665530 0.708913
0.561502 0.793605
0.634632 0.811335
0.735590 0.834631
0.560829 0.850957
0.530615 0.779601
0.582844 0.895793
0.538772 0.776121
0.560748 0.791457
0.611575 0.777692
0.487354 0.816722
0.509223 0.941882
0.570909 0.856442
0.451396 0.900805
0.451806 0.787736
0.550287 0.887071
0.525920 0.893272
0.511634 0.850757
0.405921 0.923221
0.406231 0.860355
0.412322 0.901257
0.406028 0.837042
0.380108 0.799883
0.432046 0.836069
0.333998 0.923754
0.340610 1.003124
0.301256 0.944007
0.352188 0.876783
0.368513 0.930996
0.369081 0.984984
0.426743 1.014722
0.288162 0.939863
0.349595 0.988380
0.314563 0.878403
0.269239 0.925831
0.272308 0.961154
0.291637 0.985098
0.273221 0.948939
0.174422 0.954625
0.208497 0.996799
0.309985 0.978287
0.136862 0.965503
0.149090 1.009124
0.082814 0.990304
0.155237 1.000684
0.105080 0.978957
0.051256 0.967808
0.082810 1.014739
0.039621 1.034302
0.159615 0.892891
0.093651 1.031226
0.027902 0.978348
0.040557 0.983996
0.019169 0.915600
0.079650 1.053738
-0.031225 0.926634
0.022905 0.971206
-0.008641 0.983910
0.006250 1.034336
-0.077191 0.929995
-0.132635 1.029087
-0.125500 0.972475
-0.108432 0.994277
-0.187976 1.005275
-0.077499 0.999030
-0.131753 0.998095
-0.108753 0.853053
-0.043386 1.009488
-0.186256 0.968580
-0.141378 0.980310
-0.280003 1.087170
-0.196370 1.032629
-0.237790 1.055959
-0.201183 1.006946
-0.280041 1.034270
-0.205530 1.035860
-0.283629 0.943617
-0.149193 0.911415
-0.283309 1.017855
-0.283704 0.986601
-0.320595 0.972246
-0.377934 1.032789
-0.330451 0.911862
-0.303108 0.918674
-0.414970 0.870063
-0.325344 0.924961
-0.378436 0.982220
-0.439752 0.887044
-0.414253 0.923395
-0.408653 0.899286
-0.421098 0.903074
-0.465402 0.862454
-0.427033 0.853080
-0.509894 0.876390
-0.471105 0.999079
-0.509579 0.927503
-0.448031 0.814850
-0.457698 0.808922
-0.640211 0.892114
-0.605857 0.877889
-0.562992 0.931729
-0.486011 0.819357
-0.584388 0.774463
-0.582514 0.814158
-0.589086 0.828889
-0.552218 0.831283
-0.629552 0.734529
-0.533225 0.764437
-0.644078 0.765213
-0.713531 0.759612
-0.655177 0.806643
-0.605987 0.767804
-0.603932 0.776483
-0.660820 0.759281
-0.678975 0.723121
-0.692130 0.677975
-0.673914 0.676115
-0.654938 0.704579
-0.703518 0.732911
-0.682689 0.620742
-0.733948 0.734226
-0.817141 0.700415
-0.853531 0.620652
-0.747221 0.579562
-0.806709 0.579320
-0.683188 0.651535
-0.745270 0.622499
-0.799223 0.543018
-0.803936 0.575877
-0.754116 0.661019
-0.731224 0.636508
-0.841900 0.527908
-0.780919 0.591248
-0.914835 0.580846
-0.792706 0.555568
-0.849577 0.501702
-0.919410 0.571476
-0.869163 0.509080
-0.773561 0.544187
-0.848008 0.506194
-0.796765 0.574120
-0.832367 0.506224
-0.989510 0.472195
-0.897083 0.459529
-0.849081 0.306598
-0.930213 0.445758
-0.930461 0.350029
-0.868898 0.423263
-0.965985 0.413640
-0.881287 0.386580
-0.887129 0.378584
-0.951563 0.304997
-0.940595 0.360921
-0.896854 0.333634
-0.921974 0.279288
-0.988025 0.310076
-1.005524 0.344636
-0.933383 0.305557
-0.943190 0.380587
-0.987022 0.157352
-0.956905 0.252740
-0.995883 0.194134
-0.994951 0.239910
-1.000961 0.339196
-1.026520 0.166613
-1.095446 0.206507
-1.084199 0.154592
-0.999371 0.133682
-0.900695 0.206465
-0.923578 0.100176
-0.934843 0.156627
-0.954284 0.170807
-1.039716 0.085608
-0.952414 -0.038485
-0.920986 0.109410
-0.999888 0.080224
-1.049892 0.039135
-0.944015 0.108957
-0.864693 0.027777
-1.032749 -0.006825
-1.050882 0.002403
-0.980844 -0.008008
-0.945004 -0.030597
-1.016877 -0.060537
-1.080661 -0.122445
-1.057353 0.008440
-0.952840 -0.000450
-1.063263 -0.180185
-1.028547 -0.085505
-0.969343 -0.054425
-0.978640 -0.032201
-1.002403 -0.177480
-1.073595 -0.188746
-0.975533 -0.201181
-0.938750 -0.098552
-1.101858 -0.138362
-1.092995 -0.173857
-0.917252 -0.203026
-1.039805 -0.247845
-0.986073 -0.239955
-0.980152 -0.248570
-0.956196 -0.315699
-0.975680 -0.191511
-0.979368 -0.301727
-0.902630 -0.419562
-0.893723 -0.335218
-0.940697 -0.310780
-0.897721 -0.340898
-0.974547 -0.274497
-1.054507 -0.350190
-0.999198 -0.401046
-0.826595 -0.376901
-0.912613 -0.475394
-0.953882 -0.388071
-0.894609 -0.378575
-0.906688 -0.394524
-0.879059 -0.523749
-0.894383 -0.405187
-0.861083 -0.473025
-0.925061 -0.521925
-0.885395 -0.420459
-0.970355 -0.521135
-0.923540 -0.459843
-0.887912 -0.533494
-0.864555 -0.498483
-0.866702 -0.683768
-0.813158 -0.520132
-0.844409 -0.606824
-0.808819 -0.544111
-0.842754 -0.584270
-0.858475 -0.592633
-0.882075 -0.573015
-0.844230 -0.592059
-0.859642 -0.643454
-0.787075 -0.706876
-0.767877 -0.652590
-0.852712 -0.708485
-0.727178 -0.608134
-0.755748 -0.642159
-0.729561 -0.655296
-0.667936 -0.756401
-0.689779 -0.709318
-0.726067 -0.714386
-0.724750 -0.769529
-0.687853 -0.633505
-0.690742 -0.725841
-0.713108 -0.740250
-0.646134 -0.761376
-0.682726 -0.731071
-0.696425 -0.746860
-0.599894 -0.699618
-0.635713 -0.707245
-0.569658 -0.833322
-0.672360 -0.806521
-0.550005 -0.802523
-0.621378 -0.728807
-0.566799 -0.929830
-0.554993 -0.795051
-0.549188 -0.805690
-0.553360 -0.901087
-0.557972 -0.889307
-0.575429 -0.911905
-0.495438 -0.850448
-0.529660 -0.894265
-0.497532 -0.814157
-0.585602 -0.855454
-0.501629 -0.974569
-0.560507 -0.931882
-0.441051 -0.872352
-0.487708 -0.846775
-0.358272 -0.883300
-0.447587 -0.852219
-0.368775 -0.870260
-0.427832 -1.060405
-0.277571 -1.004122
-0.373539 -0.809295
-0.343504 -0.885477
-0.423377 -1.026282
-0.363062 -0.887172
-0.341855 -0.985603
-0.302709 -0.895786
-0.372869 -1.014270
-0.328023 -0.902721
-0.264770 -0.854403
-0.217567 -0.966171
-0.188971 -0.957094
-0.275267 -0.936769
-0.262595 -0.988233
-0.149111 -0.981568
-0.243345 -1.002357
-0.139754 -1.009248
-0.197812 -1.009460
-0.156869 -1.005389
-0.233727 -1.032487
-0.187821 -0.927818
-0.088072 -0.962320
-0.141477 -1.034014
-0.129069 -1.047203
0.033698 -1.108102
-0.050416 -1.061133
-0.071275 -1.047216
-0.112370 -1.055578
0.046838 -1.005812
-0.066612 -0.971809
-0.015221 -0.963874
-0.094361 -0.984815
0.048078 -1.083035
0.044443 -0.914948
0.033877 -0.958330
0.080729 -1.034261
0.061763 -1.076562
0.049773 -0.984096
0.121046 -0.995160
0.133429 -1.050388
0.104868 -0.992973
0.214939 -1.003182
0.109995 -0.989785
0.101456 -0.979438
0.141601 -1.076707
0.169341 -1.000927
0.103038 -0.986159
0.271487 -0.954334
0.239945 -1.044916
0.245489 -0.967705
0.260357 -0.951128
0.178139 -0.971307
0.220419 -0.968566
0.225586 -0.897109
0.239608 -1.004198
0.298341 -1.009472
0.285388 -0.993330
0.389140 -0.908605
0.327618 -0.963370
0.389395 -0.919313
0.379055 -0.936497
0.281488 -0.936278
0.350964 -0.893721
0.439810 -0.954043
0.424204 -0.829378
0.378903 -0.826957
0.381098 -0.904642
0.434542 -0.899808
0.404517 -0.924392
0.424247 -0.872793
0.485294 -0.772011
0.548426 -0.902828
0.507129 -0.821368
0.503346 -0.868456
0.515246 -0.815223
0.481022 -0.868347
0.557646 -0.829833
0.556706 -0.857103
0.603870 -0.724995
0.585992 -0.834290
0.613796 -0.844400
0.548772 -0.808485
0.467270 -0.860377
0.589072 -0.862776
0.564801 -0.809245
0.544150 -0.799887
0.609301 -0.770365
0.703439 -0.754940
0.656346 -0.750402
0.676122 -0.797901
0.668367 -0.723197
0.614815 -0.686806
0.746560 -0.752995
0.689453 -0.756559
0.745407 -0.756821
0.708119 -0.737705
0.730481 -0.775359
0.802832 -0.724658
0.747962 -0.677727
0.715202 -0.702057
0.808349 -0.674413
0.783188 -0.678565
0.745249 -0.605137
0.831983 -0.627674
0.722098 -0.509072
0.757971 -0.676013
0.937997 -0.609005
0.742539 -0.612752
0.841224 -0.558748
0.787350 -0.466722
0.810816 -0.606599
0.891755 -0.470330
0.809537 -0.596185
0.908491 -0.617734
0.802059 -0.456164
0.866907 -0.506822
0.893462 -0.490275
0.816894 -0.407766
0.953947 -0.450163
0.895680 -0.332235
0.885187 -0.450910
0.922675 -0.353011
0.989389 -0.428083
0.930323 -0.472571
0.904317 -0.434130
0.874439 -0.296422
0.889884 -0.395407
0.952361 -0.292203
0.962546 -0.207337
0.939031 -0.320525
0.960668 -0.249811
0.976224 -0.315427
0.907310 -0.285396
1.028424 -0.306093
0.988323 -0.261177
1.008420 -0.301590
1.085790 -0.313136
0.953241 -0.190059
0.989262 -0.183213
0.952372 -0.216166
0.980386 -0.121642
1.016738 -0.147919
0.951606 -0.126926
0.997912 -0.093503
1.089309 -0.165863
0.970108 -0.181267
0.984904 -0.144684
1.011561 -0.120310
0.976851 -0.047333
0.949224 -0.066371
0.976850 -0.039259
1.067282 -0.078071
1.020784 -0.041405
0.959316 -0.025726
1.014139 -0.004537
0.990001 -0.007882
0.942619 -0.017906
-0.372202 -0.035376
-0.421066 -0.081079
-0.388398 -0.082553
-0.372513 -0.189841
-0.401669 -0.093291
-0.448771 -0.027842
-0.390129 -0.039662
-0.437086 -0.169478
-0.385602 -0.214318
-0.385221 -0.131781
-0.344243 -0.107834
-0.414858 -0.203989
-0.307228 -0.194930
-0.443882 -0.215760
-0.334405 -0.193634
-0.426522 -0.166954
-0.397655 -0.213870
-0.347981 -0.132801
-0.334693 -0.153796
-0.362009 -0.286984
-0.296764 -0.189108
-0.347811 -0.154446
-0.304449 -0.195229
-0.352143 -0.252030
-0.369976 -0.270662
-0.405246 -0.278481
-0.374576 -0.187158
-0.205661 -0.235907
-0.428974 -0.187862
-0.373846 -0.289828
-0.345479 -0.324471
-0.341924 -0.272455
-0.345116 -0.254515
-0.343561 -0.278271
-0.329533 -0.263770
-0.392051 -0.361440
-0.340203 -0.366926
-0.329304 -0.253647
-0.299801 -0.358233
-0.369563 -0.294593
-0.342928 -0.331967
-0.289250 -0.370566
-0.335309 -0.366213
-0.363478 -0.374009
-0.273445 -0.333447
-0.347196 -0.352413
-0.381022 -0.382278
-0.187373 -0.354813
-0.253965 -0.358196
-0.268763 -0.326311
-0.336955 -0.365504
-0.198263 -0.408144
-0.300942 -0.388093
-0.254514 -0.350730
-0.199873 -0.356194
-0.261559 -0.322329
-0.218399 -0.464113
-0.122372 -0.304798
-0.252124 -0.378286
-0.172458 -0.409599
-0.197061 -0.349488
-0.279165 -0.438480
-0.177141 -0.388888
-0.171754 -0.422039
-0.227072 -0.518742
-0.264547 -0.419771
-0.160592 -0.398794
-0.202755 -0.442084
-0.179958 -0.427641
-0.115017 -0.427198
-0.253686 -0.501028
-0.098022 -0.498750
-0.130027 -0.456312
-0.170990 -0.452210
-0.095643 -0.457666
-0.152549 -0.526992
-0.134682 -0.426235
-0.127156 -0.385135
-0.130417 -0.442231
-0.044779 -0.536735
-0.143993 -0.389888
-0.068363 -0.429142
-0.067475 -0.448478
-0.021439 -0.447618
-0.084912 -0.460136
-0.081123 -0.527417
-0.046072 -0.477472
0.012673 -0.476019
-0.051176 -0.461096
-0.097280 -0.424910
0.035488 -0.476249
-0.068538 -0.494156
-0.141868 -0.486090
-0.028424 -0.425158
0.013315 -0.499318
-0.042234 -0.422796
-0.030764 -0.504891
0.053843 -0.427809
-0.008532 -0.509577
-0.103751 -0.450502
-0.041661 -0.578124
0.088712 -0.447489
-0.041168 -0.540409
0.065639 -0.523288
0.093200 -0.448168
0.061517 -0.458258
0.050546 -0.433870
0.024546 -0.472902
0.091112 -0.448255
0.000016 -0.500530
0.078642 -0.494918
0.160954 -0.493084
0.070312 -0.433765
0.101132 -0.478214
0.052942 -0.454490
0.148860 -0.444130
0.064110 -0.379667
0.036779 -0.543966
0.163197 -0.451769
0.093727 -0.516124
0.243245 -0.453380
0.159886 -0.441285
0.160854 -0.428025
0.181637 -0.471548
0.136301 -0.537503
0.117697 -0.434468
0.214754 -0.415552
0.151217 -0.506052
0.035092 -0.382605
0.150163 -0.459824
0.191822 -0.504798
0.173328 -0.330378
0.221613 -0.410533
0.122695 -0.313173
0.136107 -0.326008
0.106869 -0.348541
0.298847 -0.456631
0.244341 -0.384555
0.187734 -0.480819
0.167693 -0.377666
0.234420 -0.429204
0.292052 -0.371778
0.210917 -0.453354
0.279768 -0.416209
0.263417 -0.306472
0.288360 -0.424283
0.275998 -0.424608
0.353046 -0.400788
0.287570 -0.352982
0.289687 -0.461884
0.213851 -0.382092
0.306519 -0.361811
0.246994 -0.417722
0.279004 -0.369036
0.328880 -0.357174
0.337453 -0.365771
0.298524 -0.348558
0.276129 -0.294953
0.278415 -0.347284
0.319207 -0.381004
0.310304 -0.346574
0.310749 -0.308821
0.293684 -0.311588
0.402554 -0.296579
0.397740 -0.272616
0.382457 -0.323263
0.352181 -0.272392
0.319404 -0.314728
0.278534 -0.193229
0.307351 -0.195129
0.335433 -0.299922
0.392679 -0.282671
0.392633 -0.262023
0.390796 -0.288022
0.410817 -0.209404
0.325648 -0.095807
0.400926 -0.107546
0.456130 -0.225590
0.357605 -0.230367
0.288726 -0.238999
0.394479 -0.121892
0.345320 -0.148039
0.323051 -0.215383
0.364425 -0.161375
0.411703 -0.125722
0.428812 -0.155530
0.411124 -0.082090
0.367297 -0.116588
0.303577 -0.128547
0.370863 -0.142757
0.447974 -0.128410
0.441074 -0.056696
0.417015 -0.065561
0.381879 -0.118242
0.372624 -0.059392
0.419907 -0.130604
0.407285 -0.046859
0.397837 -0.140074
0.406546 -0.185343
0.438439 -0.101066
0.476534 0.543785
0.431742 0.597355
0.475988 0.473837
0.551061 0.535435
0.622561 0.489440
0.493980 0.426034
0.483395 0.463928
0.477562 0.412791
0.583030 0.429170
0.359890 0.440579
0.469808 0.442522
0.554915 0.493108
0.501269 0.530520
0.514301 0.548928
0.444526 0.472624
0.533298 0.373272
0.431241 0.525050
0.475988 0.546805
0.540459 0.440095
0.520333 0.560085
0.507372 0.451127
0.543969 0.531771
0.527131 0.535797
0.350269 0.544047
0.590407 0.521832
0.509636 0.534822
0.516911 0.532589
0.500074 0.461665
0.449784 0.450090
0.431348 0.446613
0.588063 0.537705
0.468749 0.480480
0.505628 0.467223
0.503376 0.538880
0.498213 0.516801
0.544325 0.486393
0.514240 0.484531
0.498574 0.483763
0.473557 0.508686
0.528327 0.507315
0.524936 0.463103
0.439813 0.520852
0.534394 0.502493
0.567402 0.545385
0.634029 0.489960
0.450058 0.462993
0.471725 0.523802
0.392097 0.565928
0.488035 0.487660
0.446033 0.494289
-0.499338 0.493903
-0.483047 0.470518
-0.544791 0.527416
-0.495067 0.509859
-0.447049 0.448872
-0.542762 0.562861
-0.574144 0.434529
-0.459107 0.511910
-0.494738 0.495417
-0.498437 0.495394
-0.432228 0.480093
-0.508069 0.589722
-0.498625 0.611601
-0.505249 0.568371
-0.582767 0.507682
-0.579224 0.542223
-0.560643 0.514188
-0.514110 0.442090
-0.580968 0.474448
-0.412969 0.485326
-0.454139 0.497148
-0.456164 0.408654
-0.520159 0.547470
-0.508163 0.495677
-0.521523 0.557469
-0.485124 0.502201
-0.467847 0.529411
-0.489371 0.577352
-0.503014 0.513904
-0.532148 0.507506
-0.420612 0.467837
-0.556680 0.549838
-0.507438 0.504800
-0.502256 0.503956
-0.457473 0.458044
-0.550589 0.504248
-0.580322 0.431347
-0.406666 0.537873
-0.500503 0.561900
-0.552030 0.484220
-0.468827 0.544534
-0.474354 0.372938
-0.548404 0.523853
-0.517798 0.627012
-0.453672 0.527904
-0.555847 0.498235
-0.487940 0.556389
-0.455943 0.551649
-0.546196 0.570608
-0.569022 0.473204
0.646157 -0.224837
-1.509055 -1.232325
-2.322381 0.797962
1.890853 -0.150590
-0.600523 -2.208484
1.369803 3.316956
-2.696184 -1.595149
-1.019390 -0.846477
0.341019 2.421374
1.512896 0.791396