Python Programming for Biology: Bioinformatics and Beyond

Figure 23.4.  Example results of density-based clustering, illustrating clusters and

noise points. Density-based clustering can be imagined as an extension of associative

clustering. Points are joined into the same cluster, but with the extra requirement that there

needs to be a minimum number of close points. This requirement reduces the occurrence

of sparse points bridging clusters. Also, because of the requirement of a minimum number

of close neighbours for a point to be included in a cluster, some points will be excluded

from clusters below threshold size and thus marked as ‘noise’.

Then  we  go  through  the  work  pool,  popping  out  indices  and  adding  to  clusters.

However,  we  now  check  that  the  item  (index  i)  has  enough  neighbours.  If  it  does  not

(len(neighbours) < minNeighbour), then the index is added to the noise set and clustering

is skipped for that item.

while pool:

i = pool.pop()

neighbours = neighbourDict[i]

if len(neighbours) < minNeighbour:

noise.add(i)

Otherwise the clustering proceeds. A new cluster is defined and the index is added to

the set.

else:

cluster = set()

cluster.add(i)

Next  a  new  pool  is  defined  from  the  neighbours  of  the  current  item.  However,  we  do

not  automatically  accept  all  neighbours  into  the  current  cluster.  Those  with  too  few

neighbours themselves are added to the noise set instead. All points, be they noise or not,

are removed from the work pool, so they are only ever considered once.

pool2 = set(neighbours)

while pool2:

j = pool2.pop()

if j in pool:

pool.remove(j)

---

neighbours2 = neighbourDict.get(j, [])

if len(neighbours2) < minNeighbour:

noise.add(j)

else:

pool2.update(neighbours2)

cluster.add(j)

clusters.append(cluster)

Finally, the function collates the data items based upon whether their indices ended up

in the noise set (isolated items) or in one of the main clusters.

noiseData = [data[i] for i in noise]

clusterData = []

for cluster in clusters:

clusterData.append( [data[i] for i in cluster] )

return clusterData, noiseData

This function can be tested in the same manner as the simple clustering:

clusters, noise = dbScanCluster(data, 0.10, 2)