Dataset Descriptions

The dataset is a collection of pollutants for eight places, namely Tirupathi, Vishakapatnam, Gaya, Velachery, Ahmedabad, BTM Layout, Nagpur, and Agra in India. The data is taken from the Central Pollution Control Board (CPCB) (2019), which records data every 15 minutes from among various air stations located in different states in India. For a particular place and particular year, the daily values of these pollutant values have been recorded. The recorded data in the CPCB website consist of various parameters among which the air pollutant parameters are chosen and air quality index is identified. Details about the pollutant parameters are given in Section 6.4.

To add to the control measures in place, the administration of India has also implemented various sources to measure and record air pollution data. The sources include: the Centre for Geographic Analysis (CGA), which is maintained by Harvard University; the Central Pollution Control Board (Ministry of Environment, India); the Central Pollution Control Board Ministry of Environment (Historical Ambient AQI); the World AQI Project; the Delhi Pollution Control Committee, and the EPoD India-Air Pollution and Health Project.

Methodology

The data was consolidated for the years 2016-2018. The pollutant parameters included are PM, ₅, SO,. CO, and O,. The pre-processing involves handling missing values and identifying outliers: ^[1]

Year-wise data is consolidated and three clustering algorithms, namely hierarchical clustering, fuzzy C means clustering, and К-means, are applied. For each set of data, the optimal number of clusters was determined to be two, using the elbow method.

The overall procedure for weighted ensemble graph clustering is:

• 1. The air pollution dataset is loaded.
• 2. Data has to be pre-processed before applying the clustering techniques.
• 3. The first pre-processing step concerns the values for the chosen Air Quality Index (AQI) parameters (PM_{2 5}, SO,, O,, and CO) which are taken and loaded in a data frame.
• 4. The outliers are identified and replaced with the mean value.
• 5. Similarly, the missing values in the data will be imputed with the mean value.
• 6. In the final pre-processing step, the data for the various regions in India are consolidated, based on the year.
• 7. The pre-processed data is then used to determine the optimum number of clusters for each set of year-wise data. The number of clusters selected for each dataset is given in Figure 6.4.

FIGURE 6.4 Optimal duster plot of a base clustering algorithm.

• 8. As the optimal clusters are known, the base clustering techniques are applied, which are hierarchical clustering using ward linkage, fuzzy C-means clustering, and К-means clustering.
• 9. The results from the base models are represented in binary form using Equation
• 6.1 of the object membership in the respective clusters.
• 10. Each object weight is obtained from every pair of objects using Equations 6.2-6.5.
• 11. The Jaccard coefficient is calculated as the proportion of the intersection of objects to the union of objects in different clusters. Cluster weightage assignment is calculated using Jaccard similarity (using Equation 6.6).
• 12. The final cluster weights are used to form the similarity matrix which is an input to the graph-partitioning algorithm METIS.
• 13. METIS gives us the list of partition indices which are used to merge and obtain the final ensemble clustering output.
• 14. The final cluster labels along with the original pre-processed data are used to measure the effectiveness of the ensemble clustering technique.
• 15. As ground truth labels are not available in the case of clustering, intrinsic evaluation metrics such as the Davies-Bouldin Index, the Calinski-Harabasz Index, and the Silhouette Coefficient are used.

The evaluation metric results for the base clustering and ensemble clustering are then compared.

From the results of each base clustering algorithm, the cluster labels are represented as a binary membership value using Equation 6.1 (Alqurashi and Wang 2019). If the object is present in the particular cluster, then the value is 1, else 0. Figure 6.4 gives the optimal number of clusters for each base clustering algorithm, as mentioned in Table 6.1. The representation is given for hierarchical clustering for the years 2016, 2017, and 2018. The graph shows the optimal number of clusters as two. In the same way, the optimal number of clusters are chosen for the fuzzy C-means and К-means algorithm. So the co-association matrix of 6 x 6 is produced. The sample data is given in Table 6.2.

TABLE 6.1

Optimal Number of Clusters for Base Clustering

TABLE 6.2

Binary Representation of Base Clustering Models

Note: FCM: fuzzy C means; HC: hierarchical clustering.

In the next step, using all the base clustering results, a one-shot weight assignment is developed for the objects. The object weight assignment formula is given by:

where Vy is the co-occurrence count of the objects x, and x₍. within the same cluster and the ensemble size is given by R and A_tj [0, 1]. A_t> « 1 means that x, and x_J are grouped into the same cluster. A_tj « 0 means that x_f and л, are grouped into separate clusters. When A_tj « 0.5. half of the clusterings group the objects x, and x- together and the other half place them in different clusters. This is an uncertain scenario, since it shows no agreement on how to cluster the objects x, and x. This trend is captured in a quadratic function by mapping A_:), which is given by v(x) = x(l - x), where x e [0,1]. The graph of the quadratic function is given in Figure 6.5. The level of uncertainty between the two clustering objects x, and Xj is measured by:

When Ay = 0.5, the maximum value of 0.25 of the confusion index is reached. The value of the confusion index is 0 when the value of A_tj = 1 or A,, = 0. Each object’s weight is defined by the confusion measure using:

FIGURE 6.5 Quadratic function>'(дг) =дг(1 -x).

We add a smoothing term using Equation 6.5 to avoid instability by making sure that the weight value is not equal to 0.

where a small positive number equal to 0.01 is taken as e in our experiment. The result is wj e (0.1]. The weight assignment of each cluster is computed by using a binary Jaccard measure given in Equation 6.6 which provides the similarity of proportion between the size of intersection and size of the union for objects within each pair of clusters C, and C, and associated object weights.

From Figure 6.6, the weight between the pair of clusters is given by:

where the Ath object’s weight is represented as w_k and is calculated from Equations 6.2-6.5 and S₀ e [0,1 ]. If S_tJ = 0, there is no edge between C, and C, in Graph G. When S„ = 1, this indicates C, and Cj contains the same points. S,-, is a similarity measure which we use to partition the meta-graph into к* meta-clusters. The partitioning algorithm adopted is METIS, which was developed by Karypis and Kumar (1998). The output of METIS is the assignment of each object to a meta-cluster based on the ratio of participation in each cluster. Finally, the object is assigned to the cluster which has the highest ratio. The optimal number of clusters from the cluster similarity matrix is found to be three clusters. The METIS function takes this as an input. The sample output of the METIS results are explained in the following section.

FIGURE 6.6 Similarity measure between the clusters C, and C,.

Final Cluster Labeling

The METIS function gives two outputs in the form of a tuple. The first is the objective function’s value that was minimized and the second one is a list of partition indices. Our method focuses on ensemble clustering which involves assigning object weights which we use to determine cluster weights, which are converted into an adjacency list which the METIS function takes as an input. The output of the list of partition indices gives us the columns of the binary representation that have to be merged to obtain the final class labels. Once the columns are merged, their values are compared and the cluster is assigned based on the final voting value.

As an example, for representing the single object, the binary representation is given in Table 6.3. According to the METIS function, the output of [1, 2, 2, 0, 0, 1] represents the columns to be merged, which is shown in Table 6.4. Now, the merged columns give the values shown in Table 6.5. Finally, the object is assigned to the cluster that gained the majority of the votes, as shown in Table 6.6.

TABLE 6.3

Binary Representation for a Single Object along with the METIS Output

TABLE 6.4

METIS Output to Base Learner Output

TABLE 6.5

Cluster Labeling for Object X Based on Voting Scheme

TABLE 6.6

Aggregated Counts of Predictions by Base Learners

The final clusters are generated and visualization is given in geography (Figure 6.7). The cluster results from the METIS function are partitioned into good, unhealthy, and hazardous for a given air pollution dataset. The states that fall under these categories are plotted in Figure 6.7.

METIS Function

In comparison to various spectral partitioning algorithms, the METIS algorithm is known to consistently produce 10-50% better results for graph partitioning (Karypis and Kumar 1998). It is a group of serial programs used to reduce the orderings for sparse matrices, to partition finite element meshes, and to partition graphs. Multi-constraint partitioning, multi-level к-way, and multi-level recursive- bisection schemes form the basis of the algorithms implemented in METIS, which is used to partition undirected graphs because the directionality of an edge does not play any role during partitioning. This is because if an edge (u, v) is cut, the edge (v, u) will also be cut. For a directed graph to be partitioned by METIS, it first needs to be converted into an undirected graph by adding an edge (v, u) for each directed edge (u, v).

METIS Algorithm

• • Given the graph G = (N, E, EW)
• • Where, the nodes or vertices are represented by N;
• • The edges are represented by E;
• • The edge weights by EW.
• • Where N symbolizes clusters, an edge (j, k) in E can mean that an object j in EW_{(J k)} is related to an object k.

FIGURE 6.7 Ensemble clustering of air quality data with three clusters based on the severity of air pollution, i.e., good, unhealthy, and hazardous, represented by green, yellow, and red respectively.

A partition N = N_l и N₂ U ••• и N_P must be chosen such that

• • Load is balanced. There exists an even distribution of the weights in each TV,.
• • The parallel overhead is decreased. There should be minimization of the sum of all edge weights of edges that connect all the different partitions.
• • Work will be evenly divided and communication will be minimized.
• • A recursive application of partitioning the graph into two parts (graph bisection) can be carried out for complete partitioning.

Phases

METIS incorporates a multi-level approach which includes three phases. Each phase includes various algorithms:

• • A series of graphs, namely G₀, G,, G_v, can be generated to coarsen the graph. Here, the original graph is represented by G₀ and for each 0 < r G, will have a greater number of vertices than G, will have.
• • The partition of G,_v must then be computed.
• • With respect to each graph, the partition must be refined by projecting it back through the sequence in the order of (G_v, ..., G₀).
• • A partition of the original graph is the final partition that is computed during the third phase (the refined partition projected onto G₀).

Advantages

METIS is chosen as the graph-partitioning algorithm as it has various advantages. It is known to provide high quality partitions. Very large-scale integration (VLSI), linear programming, finite element methods, transportation, and various other domains in which experiments have been conducted on graphs have shown that in comparison to other widely used algorithms the partitions produced by METIS are consistently better. Another advantage of METIS is that it is extremely fast. In comparison to various other partitioning algorithms METIS has proven to be one to two orders of magnitude faster. It can partition graphs with several nodes in almost no time using current generation PCs and workstations.

Tables 6.7, 6.8, and 6.9 represent the cluster weights for each pair of clusters for the years 2016, 2017, and 2018, respectively. Figure 6.8 is the scatter plot representation of three clusters for three years based on the air pollutants. The pollutant points are represented in three different colors for three different clusters. A scatter plot is represented for the three main pollutants PM₂₅, CO, and O, for the year 2016, 2017, and 2018.

TABLE 6.7

Cluster Weights (S,j) for the Year 2016

	C,	c2	c3	c4	c5	Q
C,	1	0	0.159888	0.840112	0.909521	0.090479
c,	0	1	0.840112	0.159888	0.090479	0.909521
C,	0.159888	0.840112	1	0	0.069408	0.930592
C4	0.840112	0.159888	0	1	0.930592	0.069408
C,	0.909521	0.090479	0.069408	0.930592	1	0
C„	0.090479	0.909521	0.930592	0.069408	0	1

TABLE 6.8

Cluster Weights (S,_;) for the Year 2017

	C,	C2	C3	c4	C5	Q
C,	1	0	0.933622	0.066378	0.933305	0.066695
c,	0	1	0.066378	0.933622	0.066695	0.933305
C,	0.933622	0.066378	1	0	0.999683	0.000317
c4	0.066378	0.933622	0	1	0.000317	0.999683
c,	0.933305	0.066695	0.999683	0.000317	1	0
C6	0.066695	0.933305	0.000317	0.999683	0	1

TABLE 6.9

Cluster Weights (S,j) for the Year 2018

	С,	с2	Сз	с4	с5	Q
С,	1	0	0.793519	0.206481	0.247645	0.752355
с,	0	1	0.206481	0.793519	0.752355	0.247645
С3	0.793519	0.206481	1	0	0.046994	0.953006
с4	0.206481	0.793519	0	1	0.953006	0.046994
Сз	0.247645	0.752355	0.046994	0.953006	1	0
С,	0.752355	0.247645	0.953006	0.046994	0	1

FIGURE 6.8 Scatter plot of ensemble clustering for AQI parameters.

Algorithm 6.1: Weighted Ensemble Graph Clustering Algorithm

• [1] Through scatter plotting, the values having a high range of above 500 werefound to be outliers. • Missing values in the data are imputed with the overall mean value.