Bus-stop detection

In the preprocessing section, we extracted the raw location records and stored them into MongoDB. Further, we removed outlier, and applied segmentation and interpolation to cater for the GPS outage and unavailability. We can now use these filtered location records for our first application of Automatic bus-stop detection. The bus-stop detection uses an unsupervised clustering based algorithm to detect stoppages on a route. We firstly describe the algorithm and then describe it’s application for bus-stop detection.

DBSCAN algorithm

Density-Based Spatial Clustering of Applications with Noise (DBSCAN) [1] is the data clustering algorithm which can detect clusters of arbitrary shapes in the data-set.

Steps to find the cluster in a data-set

  1. Find the points in the {:math:`varepsilon`} (eps) neighborhood of every point

  2. Mark core points if more than minPts

  3. Identify connected neighbor points with the core points

  4. If the point is not in the neighborhood of core point mark it as a noise

  5. Repeat step 1-4 for unvisited data point

DBSCANAlgo.png

DBSCAN clustring algorithm [2]

DBCAN based bus-stop detection

The idea behind using the DBSCAN based clustering algorithm is as follows: A bus follows a *stop-and-go* pattern during its trip. When a bus is in motion, the periodic data points are separated from one another by a certain distance. For example, in a typical urban scenario, during peak hours the average movement speed of a bus is 12-15 km/hr [3] in metropolitan cities of India. At this speed, the successive data points (published by the bus module) would be separated by 3-4 meters. When a bus is stopped at a bus-stop or a junction (due to red signal or congestion), the periodic location data points (published by bus module) are clustered at the same location.

We have set the value of \(eps = \bar{ac} + 2 \times \sigma_{ac}\). The bus module application sends the location update every second. Hence, if we consider the condition of normality on our filtered location records (>30 location records), then 95% of location record would have an accuracy within the range of eps. Thus when a bus is stopped a location record of a bus would be in the eps periphery of the point.

Now, varying *minPts* would led us to obtain different types of stoppages. For instance, by setting \(minPts=4\) would lead us to extract all the stoppages on a route including stoppages due to speed breaker or pothole. In the following, we would execute the interactive code for detecting bus-stops on a route using filtered location records. The interactive nature of the bus-stop detector enables the readers to change the value of \(minPts\) in run-time and observe its impact on a bus-stop detector.

We will extract the filtered trip records of morning trip from MongoDB database by querying TripInfo for status filteredLocationRecord:True and TripStartHour':'07'. Subsequently, we will utilize the meanAccuracy and stdAccuracy computed using Preprocessing.ApplyFiltering in the section of Preprocessing for calculating eps value.

[1]:

'''Imports '''
from __future__ import print_function
from ipywidgets import interact, interactive, fixed, interact_manual, GridBox, Layout
import ipywidgets as widgets

from pymongo import MongoClient
import pprint
import numpy as np
import sys
import os
from sklearn.cluster import DBSCAN
import folium

[2]:

'''Project specific library'''
sys.path.append("/".join(os.getcwd().split('/')) +'/Codes/LibCodes')
import StoppageDetection

[3]:

'''For updating the lib changes effects'''
'''
import importlib
importlib.reload(StoppageDetection)
'''

[3]:

'\nimport importlib\nimportlib.reload(StoppageDetection)\n'

[4]:

'''Initialize MongoClient'''
con = MongoClient()

RouteName='Git_ISCON_PDPU'

SingleTripsInfo = [rec['SingleTripInfo'] for rec in con[RouteName]['TripInfo'].find({'$and':
                                                                   [ {'filteredLocationRecord':True},
                                                                    {'TripStartHour':'07'} ] })]

'''List down the trips extracted from the above query'''
print([rec for rec in SingleTripsInfo])

['29_01_2018__07_39_47', '30_01_2018__07_42_30', '01_02_2018__07_39_12', '02_02_2018__07_38_50', '18_01_2018__07_38_10', '19_01_2018__07_38_47', '22_01_2018__07_41_04', '22_12_2017__07_38_21', '26_12_2017__07_32_35', '20_12_2017__07_38_14', '21_12_2017__07_52_59', '08_01_2018__07_41_43', '09_01_2018__07_40_01', '27_12_2017__07_55_48', '29_12_2017__07_37_27', '01_01_2018__07_38_27', '12_02_2018__07_40_14', '15_02_2018__07_45_52', '16_02_2018__07_45_41', '19_02_2018__07_46_19', '20_02_2018__07_41_48', '21_02_2018__07_42_42', '13_03_2018__07_29_52', '14_03_2018__07_35_46', '20_03_2018__07_28_45', '21_03_2018__07_32_39', '22_03_2018__07_38_43', '14_02_2018__07_41_04', '22_02_2018__07_42_45', '12_02_2018__07_40_14', '15_02_2018__07_45_52', '16_02_2018__07_45_41', '19_02_2018__07_46_19', '20_02_2018__07_41_48', '21_02_2018__07_42_42', '13_03_2018__07_29_52', '14_03_2018__07_35_46', '20_03_2018__07_28_45', '21_03_2018__07_32_39', '22_03_2018__07_38_43', '14_02_2018__07_41_04', '22_02_2018__07_42_45']

Now, before applying DBSCAN based Stoppage detection, we mark the stoppages observed by the data collection volunteers during their trips for comparison with the stoppages detected using the bus-stop detector algorithm. Kindly note that these are the comprehensive list of observed stoppages and might not include the stoppages where the bus would have occasionally slowed down and started moving. These stoppages would have been detected using the bus-stop detector algorithm. Secondly, for some trips, the bus would not have stopped at junction or crossroads due to lesser traffic and in such a scenario, the bus-stop detector algorithm would not detect the crossroad as stoppage. Concretely, the list of observed stoppages gives us the intuition whether the bus-stop detector algorithm is working properly or not and the bus-stop detector could detect more stoppages than marked on the list or lesser stoppages based on the bus movement on that day and the parameters selected for the bus-stop detector algorithm.

[5]:

def MarkActualStoppages(map_osm, AcutualBusStops, AcutualCrossRoad):
    '''
    input: The map object, list of bus-stops and crossroads
    output: The map object with the stoppages
    function: Mark actual bus-stop on a route for comparison with the detected stoppage
    '''
    StoppageList = [{'Location': [23.0281012, 72.5073624], 'id': 0,'Type':'BusStop', 'Name':'ISCON'}, #ISCON
     {'Location': [23.03870415090908, 72.51184797090909], 'id': 1, 'Type':'BusStop', 'Name':'Pakwaan'}, #Pakwaan
     {'Location': [23.046436509895834, 72.5153306670573], 'id': 2, 'Type':'BusStop', 'Name': 'GuruDwara' },
     {'Location': [23.05023487142857, 72.517192015625],  'id': 3, 'Type':'BusStop', 'Name': 'Thaltej'}, #Thaltej
     {'Location': [23.058987780666662, 72.51988011433333], 'id': 4, 'Type':'BusStop', 'Name': 'Zydus' }, #Zydus
     {'Location': [23.077070729310343, 72.52525763017242], 'id': 5, 'Type':'BusStop', 'Name': 'Kargil'}, #Kargil
     {'Location': [23.086530150000005, 72.52805168333333], 'id': 6,'Type':'BusStop', 'Name':'Sola'}, #Sola
     {'Location': [23.0991167, 72.5316183], 'id':7,'Type':'CrossRoad', 'Name':'Gota'}, #Gota
     {'Location': [23.136835, 72.54286], 'id':8,'Type':'CrossRoad', 'Name':'Vaishnodevi'}, #Vaishnodevi
     {'Location': [23.1607333,72.5569467], 'id':9,'Type':'CrossRoad', 'Name':'Khoraj'}, #Khoraj
     {'Location': [23.17621,72.5843483], 'id':10,'Type':'CrossRoad', 'Name':'Adalaj-Uvarsad'}, #Adalaj-Uvarsad
     {'Location': [23.1927733, 72.6151667], 'id':11,'Type':'CrossRoad', 'Name':'Sargasan'}, #Sargasan
     {'Location': [23.185605, 72.637985], 'id':12,'Type':'CrossRoad', 'Name': 'Raksha-shakti circle'}, #Raksha-shakti circle
     {'Location': [23.1605217, 72.63598], 'id':13,'Type':'CrossRoad', 'Name': 'Bhaijipura'}, #Bhaijipura
     {'Location': [23.15448, 72.66474], 'id': 14, 'Type':'BusStop', 'Name': 'PDPU'} #PDPU
    ]
    map_osm = StoppageDetection.MarkActualBusStopOnAMap(StoppageList, map_osm, AcutualBusStops, AcutualCrossRoad)
    return(map_osm)

[6]:

def PerformDBSCAN(TripIndex, minPts, AcutualBusStops, AcutualCrossRoad):
    '''
    input: The trip index for selection of one of the trips, DBSCAN parameter minPts,
           list of observed bus-stop stoppages and other stoppages
    output: Map with detected and observed bus-stop based on selected minPts
    function: Peform the DBSCAN based bus-stop detection algorithm on a selected trip and
            update the detected stoppages and observed stoppages on a map
    '''
    LocationRecord = [rec for rec in con [RouteName] [SingleTripsInfo[TripIndex]
                                                      +'.Filtered'].find().sort([('epoch',1)]) ]

    meanAccuracy = [rec['meanAccuracy'] for
                    rec in con[RouteName]['TripInfo'].find({'SingleTripInfo':SingleTripsInfo[TripIndex] })][0]

    stdAccuracy = [rec['stdAccuracy'] for
                    rec in con[RouteName]['TripInfo'].find({'SingleTripInfo':SingleTripsInfo[TripIndex]})][0]


    epsForDetection = meanAccuracy + 2 * stdAccuracy

    map_osm = StoppageDetection.InitializeMap(LocationRecord)

    LocationTupleList = np.asarray([(rec['Latitude'],rec['Longitude'])
                         for rec in LocationRecord])

    model = DBSCAN(eps=epsForDetection, min_samples=minPts, metric=StoppageDetection.mydistance).fit(LocationTupleList)

    clusters=np.amax(model.labels_)+1

    map_osm = StoppageDetection.MarkDetectedBusStopOnAMap(LocationTupleList, model, clusters, LocationRecord, map_osm)

    '''Mark actual bus-stop on a route for comparison'''
    map_osm = MarkActualStoppages(map_osm, AcutualBusStops, AcutualCrossRoad)

    return(map_osm)

We will now use one of the trips from SingleTripsInfo for an interactive demo of DBCSCAN based bus-stop detection. Let say we choose first trip 29_01_2018__07_39_47 i.e the trip with index 0. One can choose any of the trips and change the value of minPts and observe the output of the DBSCAN based bus-stop detection algorithm on a map.

The stoppages detected using the bus-stop detector algorithm are marked with a blue marker, and the observed bus-stops are marked with a green marker whereas the observed crossroad and junctions are marked with a red marker. Moreover, the route of the trip is marked with a red color.

[7]:

'''Display interactive stoppage detector on a map'''
index = widgets.Dropdown(options =[(SingleTripInfo,index) for index,SingleTripInfo in enumerate(SingleTripsInfo)],
                                  value=0,
                                  description = 'Select trip' )

minPts = widgets.IntSlider (min=1, max=15, value=4, description='minPts')

AcutualBusStops =  widgets.Checkbox(value=False, description='Display acutal bus-stop', disabled=False)
AcutualCrossRoad =  widgets.Checkbox(value=False, description='Display observed crossroad', disabled=False)

interact(PerformDBSCAN,
    TripIndex = index,
    minPts = minPts,
    AcutualBusStops = AcutualBusStops,
    AcutualCrossRoad = AcutualCrossRoad )

[7]:

<function __main__.PerformDBSCAN(TripIndex, minPts, AcutualBusStops, AcutualCrossRoad)>

Now, we will save the list of observed bus-stops and other stoppages for the ISCON to PDPU route (i.e. North bound) in MongoDB with a collection named BusStops.NorthBound. Likewise, we will store the list of observed bus-stops and other stoppages for the PDPU to ISCON route (i.e. South bound) in MongoDB with a collection named BusStops.SouthBound.

[8]:

StoppageListNorthBound = [{'Location': [23.0281012, 72.5073624], 'id': 0,'Type':'BusStop', 'Name':'ISCON'}, #ISCON
     {'Location': [23.03870415090908, 72.51184797090909], 'id': 1, 'Type':'BusStop', 'Name':'Pakwaan'}, #Pakwaan
     {'Location': [23.046436509895834, 72.5153306670573], 'id': 2, 'Type':'BusStop', 'Name': 'GuruDwara' },
     {'Location': [23.05023487142857, 72.517192015625],  'id': 3, 'Type':'BusStop', 'Name': 'Thaltej'}, #Thaltej
     {'Location': [23.058987780666662, 72.51988011433333], 'id': 4, 'Type':'BusStop', 'Name': 'Zydus' }, #Zydus
     {'Location': [23.077070729310343, 72.52525763017242], 'id': 5, 'Type':'BusStop', 'Name': 'Kargil'}, #Kargil
     {'Location': [23.086530150000005, 72.52805168333333], 'id': 6,'Type':'BusStop', 'Name':'Sola'}, #Sola
     {'Location': [23.0991167, 72.5316183], 'id':7, 'Type':'CrossRoad', 'Name':'Gota'}, #Gota
     {'Location': [23.136835, 72.54286], 'id':8, 'Type':'CrossRoad', 'Name':'Vaishnodevi'}, #Vaishnodevi
     {'Location': [23.1607333,72.5569467], 'id':9, 'Type':'CrossRoad', 'Name':'Khoraj'}, #Khoraj
     {'Location': [23.17621,72.5843483], 'id':10, 'Type':'CrossRoad', 'Name':'Adalaj-Uvarsad'}, #Adalaj-Uvarsad
     {'Location': [23.1927733, 72.6151667], 'id':11, 'Type':'CrossRoad', 'Name':'Sargasan'}, #Sargasan
     {'Location': [23.185605, 72.637985], 'id':12, 'Type':'CrossRoad', 'Name': 'Raksha-shakti circle'}, #Raksha-shakti circle
     {'Location': [23.1605217, 72.63598], 'id':13, 'Type':'CrossRoad', 'Name': 'Bhaijipura'}, #Bhaijipura
     {'Location': [23.15448, 72.66474], 'id': 14, 'Type':'BusStop', 'Name': 'PDPU'} #PDPU
    ]

con[RouteName]['BusStops.NorthBound'].insert_many(StoppageListNorthBound)

StoppageListSouthBound = [{'Location': [23.0279711, 72.5078451], 'id': 0, 'Type': 'BusStop', 'Name': 'ISCON'}, #ISCON
    {'Location': [23.038713706, 72.511958278], 'id': 1, 'Type': 'BusStop', 'Name': 'Pakwaan'}, #Pakwaan
    {'Location': [23.046480342276425, 72.51585688109755], 'id': 2, 'Type': 'BusStop', 'Name': 'Gurudwara'}, #Gurudwara
    {'Location': [23.0498, 72.5174528], 'id': 3, 'Type': 'BusStop', 'Name': 'Thaltej'}, #Thaltej
    {'Location': [23.0582231, 72.5201619], 'id': 4, 'Type': 'BusStop', 'Name': 'Zydus'}, #Zydus
    {'Location': [23.076668105241932, 72.5253161935484], 'id': 5, 'Type': 'BusStop', 'Name': 'Kargil'}, #Kargil
    {'Location': [23.086980111684788, 72.5283425548913], 'id': 6, 'Type': 'BusStop', 'Name': 'Sola'}, #Sola
    {'Location': [23.0991004, 72.5319368], 'id': 7, 'Type':'CrossRoad', 'Name': 'Gota'}, #Gota m1
    {'Location': [23.1372724, 72.5430607], 'id': 8, 'Type':'CrossRoad', 'Name': 'Vaishnodevi'}, #Vaishnodevi m2
    {'Location': [23.1607333,72.5569467], 'id': 9, 'Type':'CrossRoad', 'Name': 'Khoraj'}, #Khoraj m3
    {'Location': [23.1776699 , 72.5869957], 'id': 10, 'Type':'CrossRoad', 'Name': 'Adalaj-uvarsad'}, #Adalaj-uvarsad m4
    {'Location': [23.1926012, 72.6154206], 'id': 11, 'Type':'CrossRoad','Name': 'Sargasan'}, #Sargasan m5
    {'Location': [23.1852905, 72.6386404], 'id': 12, 'Type':'CrossRoad', 'Name': 'RakshaShakti'}, #RakshaShakti m6
    {'Location': [23.1604408, 72.635821], 'id': 13, 'Type':'CrossRoad', 'Name': 'Bhaijipura'}, #Bhaijipura m7
    {'Location': [23.15448, 72.66474], 'id': 14,'Type': 'BusStop', 'Name': 'PDPU'} #PDPU b8
]

con[RouteName]['BusStops.SouthBound'].insert_many(StoppageListSouthBound)

[8]:

<pymongo.results.InsertManyResult at 0x7fde002db1c8>

References:

  • [1] Martin Ester, Hans-Peter Kriegel, Jorg Sander, and Xiaowei Xu. August, 1996. A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise. 2nd ACM conference on International Conference on Knowledge Discovery and Data Mining (KDD) (August, 1996), 226–231.

  • [2] W. Commons”, “”file:dbscan-density-data.svg — wikimedia commons, the free media repository”,” ”2011”, ”[Online; accessed 30-April-2019]”

  • [3] 2011. Bangalore Mobility Indicators 2010-11. Urban Mass Transit Company Limited (UMTC) (2011)