# jDBSCAN 

---
## Description                

**DBSCAN** is a density based clustering algorithm that works by successively growing a cluster from initial seed points **[1]**. If the density in the circle proximity (which has the radius parameter *Eps*) of a point is above or equal a threshold level, denoted by the *MinPts* parameter, the cluster is expanded forward by assigning all the unassigned points in the neighborhood to it. The algorithm then recursively proceeds with the same steps for each of the newly added points to the cluster. Points that will not be assigned to any cluster by the end of this process are labeled as noise. 

**The current implementation supports only two dimensional data.**

**[1]** http://en.wikipedia.org/wiki/DBSCAN


## Additional Features

 The algorithm also works on data points given by ***GPS coordinates***. Moreover, the algorithm can be used on data with a time dimension also. This allows for ***spatio-temporal*** clustering.   
 
## Usage
1. Import the script.

		<script type="text/javascript" src="jDBSCAN.js"></script>
		
2. Sample Data Format
#### Basic 2D Data
```javascript
		var point_data = [
					{ 	
						x: 0.1,
						y: 5
					}, 
					{ 
						x: 2,
						y: 4
					},
					{ 
						x: 0,
						y: 7
					}
				];
```
#### GPS Data
```javascript
var gps_point_data = [ 
			{ 
				location: {
					accuracy: 30,
					latitude: 55.7858667,
					longitude: 12.5233995
				}
			},
			{
				location: {
					accuracy: 10,
					latitude: 45.4238667,
					longitude: 12.5233995
				}
			},
		        { 	location: {
					accuracy: 5,
					latitude: 25.3438667,
					longitude: 11.6533995
				}
			}
		];
```
Where accuracy is given in meters.
#### Spatial and Temporal Data   
```javascript
		var time_gps_data = [ 
					{ 
						location: {
							accuracy: 30,
							latitude: 55.7858667,
							longitude: 12.5233995
						},
						timestamp: 1349958445
					},
					{
						location: {
							accuracy: 10,
							latitude: 45.4238667,
							longitude: 12.5233995
						},
						timestamp: 123958445
					},
					{ 
						location: {
							accuracy: 5,
							latitude: 25.3438667,
							longitude: 11.6533995
						},
						timestamp: 1350958445
					}
				];
```

### OR
 
```javascript
		var time_point_data = [ 
					{ 
						x: 0.1, 
						y: 5, 
						timestamp: 1350958445
					}, 
					{
						x: 2,
						y: 4,
						timestamp: 123958445
					},
					{
						x: 0,
						y: 7,	
						timestamp: 1349958445
					} 
				];
```
Where **timestamp** is given by the **UNIX timestamp in seconds** for the sample point.

3. Run the algorithm. 
To run the algorithm you need to provide the data along with the **eps** and **minPts** parameters. For the traditional **DBSCAN** the steps are the following: 
```javascript
	// Configure a DBSCAN instance.
	var dbscanner = jDBSCAN().eps(0.075).minPts(1).distance('EUCLIDEAN').data(point_data);
```
The distance functions available are: **'EUCLIDEAN', 'HAVERSINE'** (for GPS data), **'MANHATTAN'**.

Additionally you can provide your own distance function, which must accept at least two parameters (the two points), and passing it to the *distance* method. The next step is to simply run the clustering algorithm.

```javascript
	// This will return the assignment of each point to a cluster number, 
	// points which have  -1 as assigned cluster number are noise.
	var point_assignment_result = dbscanner();
		
	// (OPTIONAL) If you need the cluster centers for each of the
	// identified clusters use this 
	var cluster_centers = dbscanner.getClusters();  `
```

In case of **spatio-temporal data**, as described above, **additional parameters must be supplied**. Such as **time_eps** (difference in seconds used as the time equivalent of the distance eps value).

```javascript
	var dbscanner = jDBSCAN().eps(0.075).minPts(1).distance('EUCLIDEAN').timeEps(1800).data(data);
```
The default **time distance function** is given by the absolute difference between timestamps. Other functions can be used by passing a function to the *time_distance* method, it also should accept two objects with a *timestamp* field.
```javascript
	var dbscanner = jDBSCAN().eps(0.075).minPts(1).distance('EUCLIDEAN').timeEps(1800).timeDistance(custom_function).data(data);
```
The remaining steps are similar.

## Example
See **example.html**, use the console to view the raw input data and raw output.
![](example/default.png)
#### After DBSCAN
![](example/clusters.png)