haversine_distance_clustering_clustersonly.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(37.96766891, 23.72920298) 0\n",
      "(37.9682968, 23.729191) 0\n",
      "(37.9671963, 23.7284495) 0\n",
      "(37.9685356, 23.727942) 0\n",
      "(37.967217, 23.7284915) 0\n",
      "(37.9672278, 23.7284826) 0\n",
      "(37.9672084, 23.7284791) 0\n",
      "(37.9672257, 23.7284896) 0\n",
      "(37.9672105, 23.7284766) 0\n",
      "(37.9672144, 23.7284955) 0\n",
      "(37.9672177, 23.7284984) 0\n",
      "(37.9671985, 23.7284931) 0\n",
      "(37.9672202, 23.7285048) 0\n",
      "(37.9672049, 23.7285091) 0\n",
      "(37.9672243, 23.7284976) 0\n",
      "(37.9672253, 23.728485) 0\n",
      "(37.9672111, 23.7284896) 0\n",
      "(37.967221, 23.7285007) 0\n",
      "(37.9672103, 23.7284929) 0\n",
      "(37.9672069, 23.7285041) 0\n",
      "(37.9672152, 23.7284958) 0\n",
      "(37.9672248, 23.7284963) 0\n",
      "(37.9672162, 23.7284926) 0\n",
      "(37.9672066, 23.7284601) 0\n",
      "(37.9672269, 23.7285194) 0\n",
      "(37.9672094, 23.7284671) 0\n",
      "(37.9672254, 23.7285122) 0\n",
      "(37.9672153, 23.728503) 0\n",
      "(37.9672182, 23.7284817) 0\n",
      "(37.9672119, 23.7284703) 0\n",
      "(37.9672151, 23.7285058) 0\n",
      "(37.9672276, 23.7284712) 0\n",
      "(37.9672066, 23.728485) 0\n",
      "(37.9672085, 23.7285126) 0\n",
      "(37.967212, 23.7284926) 0\n",
      "(37.9672353, 23.728487) 0\n",
      "(37.9672096, 23.7285095) 0\n",
      "(37.9671899, 23.7285362) 0\n",
      "(37.9671937, 23.7284965) 0\n",
      "(37.9686699, 23.7282983) 0\n",
      "(37.9672018, 23.7284295) 0\n",
      "(37.9688762, 23.7281395) 0\n",
      "(37.9667664, 23.7278716) 0\n",
      "(37.9701252, 23.7285451) 0\n",
      "(37.9758167, 23.7356097) 1\n",
      "(37.9755988, 23.7346204) 1\n",
      "(37.975692, 23.7350702) 1\n",
      "(37.9762192, 23.7267812) 2\n",
      "(37.9765965, 23.725825) 2\n",
      "(37.9767907, 23.7259763) 2\n"
     ]
    }
   ],
   "source": [
    " #! /usr/bin/python   \n",
    "from math import radians, cos, sin, asin, sqrt, pi, pow, atan2\n",
    "import re, math\n",
    "\n",
    " class DBSCAN:  \n",
    " #Density-Based Spatial Clustering of Application with Noise -> http://en.wikipedia.org/wiki/DBSCAN  \n",
    "   def __init__(self):  \n",
    "     self.name = 'DBSCAN'  \n",
    "     self.DB = [] #Database  \n",
    "     self.esp = 150 #neighborhood distance for search  \n",
    "     self.MinPts = 2 #minimum number of points required to form a cluster  \n",
    "     self.cluster_inx = -1  \n",
    "     self.cluster = []  \n",
    "       \n",
    "   def DBSCAN(self):  \n",
    "     for i in range(len(self.DB)):  \n",
    "       p_tmp = self.DB[i]  \n",
    "       if (not p_tmp.visited):  \n",
    "         #for each unvisited point P in dataset  \n",
    "         p_tmp.visited = True  \n",
    "         NeighborPts = self.regionQuery(p_tmp)  \n",
    "         if(len(NeighborPts) < self.MinPts):  \n",
    "           #that point is a noise  \n",
    "           p_tmp.isnoise = True  \n",
    "           #print p_tmp.show(), 'is a noise'  \n",
    "         else:  \n",
    "           self.cluster.append([])  \n",
    "           self.cluster_inx = self.cluster_inx + 1  \n",
    "           self.expandCluster(p_tmp, NeighborPts)     \n",
    "       \n",
    "   def expandCluster(self, P, neighbor_points):  \n",
    "     self.cluster[self.cluster_inx].append(P)  \n",
    "     iterator = iter(neighbor_points)  \n",
    "     while True:  \n",
    "       try:   \n",
    "         npoint_tmp = iterator.next()  \n",
    "       except StopIteration:  \n",
    "         # StopIteration exception is raised after last element  \n",
    "         break  \n",
    "       if (not npoint_tmp.visited):  \n",
    "         #for each point P' in NeighborPts   \n",
    "         npoint_tmp.visited = True  \n",
    "         NeighborPts_ = self.regionQuery(npoint_tmp)  \n",
    "         if (len(NeighborPts_) >= self.MinPts):  \n",
    "           for j in range(len(NeighborPts_)):  \n",
    "             neighbor_points.append(NeighborPts_[j])  \n",
    "       if (not self.checkMembership(npoint_tmp)):  \n",
    "         #if P' is not yet member of any cluster  \n",
    "         self.cluster[self.cluster_inx].append(npoint_tmp)  \n",
    "       else:  \n",
    "         #print npoint_tmp.show(), 'is belonged to some cluster'\n",
    "         continue\n",
    "   \n",
    "   def checkMembership(self, P): \n",
    "     #will return True if point is belonged to some cluster  \n",
    "     ismember = False  \n",
    "     for i in range(len(self.cluster)):  \n",
    "       for j in range(len(self.cluster[i])):  \n",
    "         if (P.x == self.cluster[i][j].x and P.y == self.cluster[i][j].y):  \n",
    "           ismember = True  \n",
    "     return ismember  \n",
    "       \n",
    "   def regionQuery(self, P):  \n",
    "   #return all points within P's eps-neighborhood, except itself  \n",
    "     pointInRegion = []  \n",
    "     for i in range(len(self.DB)):  \n",
    "       p_tmp = self.DB[i]  \n",
    "       if (self.dist(P, p_tmp) < self.esp and P.x != p_tmp.x and P.y != p_tmp.y):  \n",
    "         pointInRegion.append(p_tmp)  \n",
    "     return pointInRegion  \n",
    "   \n",
    "   def dist(self, p1, p2):  \n",
    "   #return distance between two point  \n",
    "     dx = (p1.x - p2.x)  \n",
    "     dy = (p1.y - p2.y) \n",
    "     lat = p1.x/180*pi\n",
    "     lon = p1.y/180*pi  \n",
    "     p_lat = p2.x/180*pi\n",
    "     p_lon = p2.y/180*pi\n",
    "     dlat=lat-p_lat\n",
    "     dlon=lon-p_lon\n",
    "     a = pow((sin(dlat/2)),2) + cos(lat) * cos(p_lat) * pow((sin(dlon/2)),2) \n",
    "     d = 2 * 6373000* atan2( sqrt(a), sqrt(1-a) )\n",
    "     return d\n",
    "\n",
    " class Point:  \n",
    "   def __init__(self, x = 0, y = 0, visited = False, isnoise = False):  \n",
    "     self.x = x  \n",
    "     self.y = y  \n",
    "     self.visited = False  \n",
    "     self.isnoise = False  \n",
    "   \n",
    "   def show(self):  \n",
    "     return self.x, self.y  \n",
    "       \n",
    " if __name__=='__main__':  \n",
    "   #this is a mocking data just for test  \n",
    "    vecPoint = [Point(37.96766891, 23.72920298), Point(37.9682968, 23.729191), Point(37.9686369, 23.7317783), Point(37.9688425, 23.7375), Point(37.9700731, 23.7401936), Point(37.9720792, 23.733686), Point(37.9758167, 23.7356097), Point(37.9755988, 23.7346204), Point(37.9763044, 23.7287133), Point(37.9762192, 23.7267812), Point(37.9765965, 23.725825), Point(37.9747424, 23.7247172), Point(37.9767907, 23.7259763), Point(37.9671963, 23.7284495), Point(37.9685356, 23.727942), Point(37.9688762, 23.7281395), Point(37.9701252, 23.7285451), Point(37.97175634, 23.72589367), Point(37.9720922, 23.7289803), Point(37.9667664, 23.7278716), Point(37.9713652, 23.7236495), Point(37.9758867, 23.7241544), Point(37.9772489, 23.7231517), Point(37.9704348, 23.7198505), Point(37.9743998, 23.7196783), Point(37.9693647, 23.723635), Point(37.9692997, 23.7329933), Point(37.967217, 23.7284915), Point(37.9672278, 23.7284826), Point(37.9672084, 23.7284791), Point(37.9672257, 23.7284896), Point(37.9672105, 23.7284766), Point(37.9672144, 23.7284955), Point(37.9672177, 23.7284984), Point(37.9671985, 23.7284931), Point(37.9672202, 23.7285048), Point(37.9672049, 23.7285091), Point(37.9672243, 23.7284976), Point(37.9672253, 23.728485), Point(37.9672111, 23.7284896), Point(37.967221, 23.7285007), Point(37.9672103, 23.7284929), Point(37.9672069, 23.7285041), Point(37.9672152, 23.7284958), Point(37.9672248, 23.7284963), Point(37.9672162, 23.7284926), Point(37.9672066, 23.7284601), Point(37.9672269, 23.7285194), Point(37.9672094, 23.7284671), Point(37.9672254, 23.7285122), Point(37.9672153, 23.728503), Point(37.9672182, 23.7284817), Point(37.9672119, 23.7284703), Point(37.9672151, 23.7285058), Point(37.9672276, 23.7284712), Point(37.9672066, 23.728485), Point(37.9672085, 23.7285126), Point(37.967212, 23.7284926), Point(37.9672353, 23.728487), Point(37.9892244, 23.7315974), Point(37.9892248, 23.7315976), Point(37.9672096, 23.7285095), Point(37.9671899, 23.7285362), Point(37.9671937, 23.7284965), Point(37.9686699, 23.7282983), Point(37.9672018, 23.7284295), Point(37.975692, 23.7350702)] \n",
    "   #Create object  \n",
    "    dbScan = DBSCAN()  \n",
    "   #Load data into object  \n",
    "    dbScan.DB = vecPoint;  \n",
    "   #Do clustering  \n",
    "    dbScan.DBSCAN()  \n",
    "   #Show result cluster  \n",
    "    for i in range(len(dbScan.cluster)):  \n",
    "        #print 'Cluster: ', i  \n",
    "        for j in range(len(dbScan.cluster[i])):  \n",
    "            print dbScan.cluster[i][j].show(),i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}