Leader Cluster is a simple clustering algorithm and is as described in the book "Clustering Algorithms" by John A. Hartigan (pg. 74, §3.2), published by Wiley. This project is inspired by a similar implementation in R's Leader Cluster package.

In Java Leader Cluster, we have modified the original leader cluster to create clusters of fixed size in a single pass over the data points.

• Allows clustering based on road distances, either using Google Distance API or OSRM HTTP API
• Just specify the URL, basic Auth for OSRM (optional) and/or Google Key in config/CONFIG.ini

It requires two basic inputs:-

• Data points comprising of their coordinates and weights
• Radius of the cluster in meters

Optionally you can also provide your own distance calculator, by default, it uses Haversine distance calculator.

The steps of the algorithm are:-

• It first sorts the data points in decreasing order of their weights.
• The first data point forms its own cluster
• For each of the remaining points, it first checks if they can be inserted into any of the existing clusters
• This involves checking if the point's distance from the centroid of the cluster is less than the cluster radius and
• The resulting weighted coordinates of the cluster on inserting this point, do not result in exceeding the cluster radius for the existing members of the cluster
• Before each iteration, all the existing clusters are sorted in decreasing order of their weights to ensure that we create clusters of greater weights

Requirements:-

• Java 8 (Ubuntu 16.04): sudo apt-get install openjdk-8-jdk
• Apache Maven: sudo apt-get install maven
• Set the environment variable JAVA_HOME

After, that, clone the project to a folder and to build the project, use commands:

cd LeaderCluster
mvn clean package

There are three ways to use it:-

• You can directly use it as a tool for clustering spatial points by using the spatialClustering package
• You can implement the interfaces given in algorithm package and integrate Leader Cluster Algorithm into your project
• You can use it as a standalone runnable jar to cluster points given in a input csv file.

Using runnable jar
After mvn install, a runnable jar is created in the target folder. You can use it as shown below:

java -jar target/JavaLeaderCluster-1.1.jar /path/to/input.csv <radius-of-cluster-in-meters>

• You can specify the distance calculator - either one of haversine, osrm or google as:

java -jar target/JavaLeaderCluster-1.1.jar /path/to/input.csv <radius-of-cluster-in-meters> <distance-calculator-name>

For a sample use case, please look at LeaderClusterTest.java

Add this project as a submodule or place the jar file in the libs folder, and then include this in your project's pom.xml

<plugin>
     <groupId>org.apache.maven.plugins</groupId>
     <artifactId>maven-install-plugin</artifactId>
     <version>2.5.2</version>
     <executions>
         <execution>
             <id>install-external</id>
             <phase>clean</phase>
             <configuration>
                 <file>${basedir}/path/to/JavaLeaderCluster-1.1.jar</file>
                 <repositoryLayout>default</repositoryLayout>
                 <groupId>com.delhivery</groupId>
                 <artifactId>JavaLeaderCluster</artifactId>
                 <version>1.1</version>
                 <packaging>jar</packaging>
                 <generatePom>true</generatePom>
             </configuration>
             <goals>
                 <goal>install-file</goal>
             </goals>
         </execution>
     </executions>
</plugin>