knitr::opts_chunk$set(eval = TRUE, include=TRUE)

Introduction

This document will illustrate several methods on clustering of schools. We will use 3 approaches, namely:

  1. kmeans clustering

  2. density-based clustering

  3. criterion-based clustering

Our case study is the SDO of Pasig.

##   Longitude Latitude
## 1  121.0833 14.61528
## 3  121.0823 14.61524
## 4  121.0952 14.61507
## 5  121.1022 14.60937
## 6  121.1031 14.60444
## 7  121.0951 14.60043

Our dataset contains the Longitude and Latitude of all schools in Pasic City. There are 40 schools in our data but only shown above are 6 schools for illustration purposes only.

Determining the Optimal Number of Clusters

An important consideration when doing cluster analysis is the number of clusters to be used given a set of observations (in this case schools).

For Kmeans clustering, the number of clusters have to be specified in the algorithm. Fortunately, there is also a method on determining the number of cluster using Elbow Method. By “eye-balling”, the part of the elbow where there is a joint, that’s the suggested number of clusters. In the example, it’s 3 clusters.

KMEANS Clustering

Given that we have identified the optimal number of clusters, we can now use Kmeans clustering to group the observations according to their clusters.

#set.seed to ensure replicability
set.seed(100)
k <- kmeans(minidb, centers = 3)
fviz_cluster(k, minidb,
             palette = "Set2", ggtheme = theme_minimal())

Kmeans algorithm produced an output where each observation has been provided with their respective clusters. This data can be seen from the data below.

##   Longitude Latitude cluster
## 1  121.0833 14.61528       1
## 3  121.0823 14.61524       1
## 4  121.0952 14.61507       1
## 5  121.1022 14.60937       1
## 6  121.1031 14.60444       1
## 7  121.0951 14.60043       1

Data Mapping

To check how good the clustering, it is important to visualize the data. The next step is to plot the data in a map together with cluster of each school.

It looks like the schools were clustered into North, West and East with some schools close to the borders of the other clusters. These schools that are close to the borders are clearly outliers. The Kmeans clustering forces schools to have their own clusters.

What if we want to calibrate the cluster of those that are outliers? How do we identify them in the first place?

DBSCAN Clustering

The second clustering method that we will use is the DBSCAN Algorithm. DBSCAN means Density-based Spatial Clustering of Applications with Noise. This approach is useful because it can identify the noise or outlier in our data.

The DBSCAN approach requires us to specify the radius (epsilon) of the cluster and the minimum number of observation for the cluster. Unlike Kmeans, DBSCAN can identify the number of clusters given these 2 parameters.

First, we identify the radius of the cluster using the same “elbow-method”.

library(factoextra)
library(dbscan)
kNNdistplot(minidb, k = 4)
abline(h=.015, title(main="Radius for DBSCAN Clustering"))

Now, we can perform the DBSCAN and we specify the radius as .015 and 3 as the minimum observations (schools) in a cluster.

set.seed(100)
db <- dbscan(minidb, eps = .0150, minPts = 3)
fviz_cluster(db, minidb,
             palette = "Set2", ggtheme = theme_minimal())

db
## DBSCAN clustering for 40 objects.
## Parameters: eps = 0.015, minPts = 3
## Using euclidean distances and borderpoints = TRUE
## The clustering contains 3 cluster(s) and 1 noise points.
## 
##  0  1  2  3 
##  1 14 19  6 
## 
## Available fields: cluster, eps, minPts, dist, borderPoints

The DBSCAN method was able to cluster all schools except Pasig City Science HS which is the only outlier. If we want, we can recalibrate the cluster of Pasig City Science HS using local knowledge.

CRITERION-based clustering

This approach is basically driven by parameters set by management. It involves knowing the criteria for organizing schools. These criteria aims to group schools together for ease of deploying human resources for schools.

The actual deployment problem goes like this:

Given 1,500 PDO 1 items, what if we want to cluster schools based on several criteria?

For example, we wanted to deploy the PDO 1 in a cluster of schools (composed of 1 Central School and at most 2 neighboring schools) that are closest to each other and each school having an AO II.

In this approach, we have to perform the following steps using the school data:

  1. Filter schools with AO II
  2. Filter Central Schools
  3. For each Central School, compute the distance to the next school.
  4. Filter the 2 schools with lowest distance from the Central School.

Crucial in this approach is distance formula. In this sample, we will use 2 approaches of computing for distances.

The first formula is the Haversine method which determines the great-circle distance between two points on a sphere given their longitudes and latitudes.

But we have to perform data cleaning and merging.

To compute for school-by-school distance, it requires to have data for Central School and Nearby Schools. After some data cleaning, we now have these two datasets.

Central School Data:

head(temp_main)
##        Main_LONG  Main_LAT
## 134979  120.6080 17.602800
## 135024  120.6570 17.617500
## 131593  125.5248  9.167068
## 131550  125.4088  8.968315
## 131584  125.5608  9.157540
## 131433  125.5155  9.341403

Nearby Schools Data:

head(temp_mynn)
##          NNLONG     NNLAT
## 134976 120.6120 17.601000
## 134982 120.6300 17.606400
## 131586 125.5280  9.166338
## 131508 125.4078  8.975098
## 131537 125.5608  9.157557
## 131436 125.5078  9.348566

Take note that for both tables, the row name is the same as the School ID.

We can now compute for Haversine distance using a function from geosphere package in R. The output produces a table where the first column is the Central School ID, the second column is the Nearby School ID, and the third column is the Haversine Distance (measured in meters) of the two columns.

In this table, we have already selected 2 nearby schools closest to the Central School.

## # A tibble: 3,010 × 3
## # Groups:   SchlID [1,500]
##    SchlID SchoolNN Distance
##     <int> <chr>       <dbl>
##  1 100006 100310       1.95
##  2 100006 150016    1898.  
##  3 100025 100041    1061.  
##  4 100025 150002    1161.  
##  5 100083 100099     986.  
##  6 100083 100081    1453.  
##  7 100092 100090     870.  
##  8 100092 100096    2837.  
##  9 100117 150012     796.  
## 10 100117 100111     900.  
## # ℹ 3,000 more rows

The second formula for computing distance is road distance used by Google. The Haversine formula measures the shortest distance between two points in a spherical surface. But for road distance in Google Maps, it takes into account the road network and mode of transportation. In a sense, road distance is more precise. However, there is a cost for using Google Maps services.

For purposes of illustrating how to compute school-by-school distance using Google Services, we secured a Google API which allows limited queries per day.

We will be using a function from gmapsdistance package to compute for road distance.

We randomly selected 5 Central Schools and 5 Nearby Schools and computed for their distances. The output table has 3 columns: Central School, Nearby School and Distance. The first two columns contain the geospatial data while the third contains the distance data.

##            Central_School        Nearby_School Distance
## 1      8.58084,124.776781  8.495463,123.512939  278.985
## 2    12.106802,124.502163  8.963303,124.781263  714.494
## 3 14.26292185,121.1283408  9.899779,123.901111  994.841
## 4 7.234531367,125.6420273 18.211316,121.553632  529.207
## 5    14.274581,121.454002  8.377279,124.696198 1023.046

Note that only the first observation is precise when compared to Google Map Online because other observations involve maritime travel.