DBSCAN

I was looking for the way to cluster a points, grouping a neighbourhood points together, but since I don't know number clusters in the data and therefore the k-mean clustering can't be use. After do some search on Google and our good friend Wikipedia I come across this alternative clustering algorithm.

DBSCAN is short from Density-Based Spatial Clustering of Application with Noise (reference from wiki : DBSCAN)

Explanation in plain english
DBSCAN requires two parameters: (eps) and the minimum number of points required to form a cluster (minPts). It starts with an arbitrary starting point that has not been visited. This point's -neighborhood is retrieved, and if it contains sufficiently many points, a cluster is started. Otherwise, the point is labeled as noise. Note that this point might later be found in a sufficiently sized -environment of a different point and hence be made part of a cluster.
If a point is found to be a dense part of a cluster, its -neighborhood is also part of that cluster. Hence, all points that are found within the -neighborhood are added, as is their own -neighborhood when they are also dense. This process continues until the density-connected cluster is completely found. Then, a new unvisited point is retrieved and processed, leading to the discovery of a further cluster or noise.

Here is a code in Python

 #! /usr/bin/python  
 from math import sqrt, pow  
   
 class DBSCAN:  
 #Density-Based Spatial Clustering of Application with Noise -> http://en.wikipedia.org/wiki/DBSCAN  
   def __init__(self):  
     self.name = 'DBSCAN'  
     self.DB = [] #Database  
     self.esp = 4 #neighborhood distance for search  
     self.MinPts = 2 #minimum number of points required to form a cluster  
     self.cluster_inx = -1  
     self.cluster = []  
       
   def DBSCAN(self):  
     for i in range(len(self.DB)):  
       p_tmp = self.DB[i]  
       if (not p_tmp.visited):  
         #for each unvisited point P in dataset  
         p_tmp.visited = True  
         NeighborPts = self.regionQuery(p_tmp)  
         if(len(NeighborPts) < self.MinPts):  
           #that point is a noise  
           p_tmp.isnoise = True  
           print p_tmp.show(), 'is a noise'  
         else:  
           self.cluster.append([])  
           self.cluster_inx = self.cluster_inx + 1  
           self.expandCluster(p_tmp, NeighborPts)     
       
   def expandCluster(self, P, neighbor_points):  
     self.cluster[self.cluster_inx].append(P)  
     iterator = iter(neighbor_points)  
     while True:  
       try:   
         npoint_tmp = iterator.next()  
       except StopIteration:  
         # StopIteration exception is raised after last element  
         break  
       if (not npoint_tmp.visited):  
         #for each point P' in NeighborPts   
         npoint_tmp.visited = True  
         NeighborPts_ = self.regionQuery(npoint_tmp)  
         if (len(NeighborPts_) >= self.MinPts):  
           for j in range(len(NeighborPts_)):  
             neighbor_points.append(NeighborPts_[j])  
       if (not self.checkMembership(npoint_tmp)):  
         #if P' is not yet member of any cluster  
         self.cluster[self.cluster_inx].append(npoint_tmp)  
       else:  
         print npoint_tmp.show(), 'is belonged to some cluster'  
   
   def checkMembership(self, P):  
     #will return True if point is belonged to some cluster  
     ismember = False  
     for i in range(len(self.cluster)):  
       for j in range(len(self.cluster[i])):  
         if (P.x == self.cluster[i][j].x and P.y == self.cluster[i][j].y):  
           ismember = True  
     return ismember  
       
   def regionQuery(self, P):  
   #return all points within P's eps-neighborhood, except itself  
     pointInRegion = []  
     for i in range(len(self.DB)):  
       p_tmp = self.DB[i]  
       if (self.dist(P, p_tmp) < self.esp and P.x != p_tmp.x and P.y != p_tmp.y):  
         pointInRegion.append(p_tmp)  
     return pointInRegion  
   
   def dist(self, p1, p2):  
   #return distance between two point  
     dx = (p1.x - p2.x)  
     dy = (p1.y - p2.y)  
     return sqrt(pow(dx,2) + pow(dy,2))  
   
 class Point:  
   def __init__(self, x = 0, y = 0, visited = False, isnoise = False):  
     self.x = x  
     self.y = y  
     self.visited = False  
     self.isnoise = False  
   
   def show(self):  
     return self.x, self.y  
       
 if __name__=='__main__':  
   #this is a mocking data just for test  
   vecPoint = [Point(11,3), Point(10,4), Point(11,5), Point(12,4), Point(13,5), Point(12,6), Point(6,10), Point(8,10), Point(5,12), Point(7,12)]  
   
   #Create object  
   dbScan = DBSCAN()  
   #Load data into object  
   dbScan.DB = vecPoint;  
   #Do clustering  
   dbScan.DBSCAN()  
   #Show result cluster  
   for i in range(len(dbScan.cluster)):  
     print 'Cluster: ', i  
     for j in range(len(dbScan.cluster[i])):  
       print dbScan.cluster[i][j].show()