Python Programming for Biology: Bioinformatics and Beyond

Density-based clustering

The threshold clustering method works fairly quickly to group our data, but we will now

consider  a  way  of  improving  the  method  so  that  it  takes  account  of  the  density  of  data

points, and thus the method is less likely to have intermediate points that greedily combine

otherwise separate clusters. The method we have chosen here is referred to as DBSCAN

1

and is commonly used in scientific analyses. We might have also considered the OPTICS

2

method,  but  we  omit  this  only  for  reasons  of  brevity.  The  basic  principle  here  is  that

distance alone is not sufficient to define the clusters; the number of neighbours should be

considered too. Hence cluster membership requires support, i.e. a certain density of points.

The  method  can  be  criticised  as  being  subjective,  given  that  the  threshold  distance  and

minimum number of supporting neighbours have to be specified. Nonetheless the method

is  free  from  any  assumptions  about  how  the  data  is  distributed  and  copes  well  when  the

clusters  are  irregular  shapes.  Also,  there  is  the  inherent  concept  of  ‘noise’  points:  data

items that are disconnected from the clusters.

---