UNSUPERVISED CLASSIFIERS FOR EDUCATIONAL DATA MINING

Unsupervised Machine Learning

In Chapter 6, we learned about supervised learning, in which models are trained using labelled
data. In contrast to supervised learning, unsupervised learning doesn't require labelled data for
training. Instead, it aims to discover hidden patterns and insights within the dataset. Just like
how humans learn, unsupervised learning enables models to act on unlabelled datasets
without explicit guidance. Due to the absence of corresponding output data, unsupervised
learning cannot be directly applied to regression or classification problems. Its primary goal is to
uncover a dataset's inherent structure, group data based on similarities, and represent the
dataset in a more condensed form.

Consider a dataset of images of cats and dogs (Figure 1). Without prior training on this specific
dataset, the algorithm's task is to identify each image's distinctive features independently. The
algorithm will then cluster the images into groups based on similarities.

Figure 1: Image dataset

Why use Unsupervised Learning?

• It helps find useful insights from the data.
• It is similar to human learning, which involves thinking based on experiences
• In the real world, we don't always have input data with corresponding output. To solve such
cases, unsupervised learning is needed.
Figure 2 illustrates how unsupervised learning works.

Figure 2: Working principle of unsupervised learning

Dr. Saswati Mukherjee, School of Education Technology, JU

1
Here, the unlabelled input data is taken, which is not categorised, and corresponding outputs
are not given. This unlabelled input data is now fed to the machine learning model to train it.
Firstly, it will interpret the raw data to find the hidden patterns from the data and then apply
suitable algorithms such as k-means clustering, decision trees, etc. Once the suitable algorithm
is applied, the algorithm divides the data objects into groups according to the similarities and
differences between the objects.

Types of Unsupervised Learning Algorithm

The unsupervised learning algorithm can be categorised into two types of problems:
• Clustering: Clustering is a method of grouping objects into groups so that objects with the
most similarities remain in a group and have fewer or no similarities with the objects of
another group. Cluster analysis finds the commonalities between the data objects and
categorises them based on the presence or absence of those commonalities.
• Association: An association rule is an unsupervised learning method to find the
relationships between variables in a large database. It determines the set of items that
occur together in the dataset. Association rules make marketing strategies more effective.
For example, people who buy X items (such as bread) also tend to purchase Y items (like
butter or jam). A typical example of an association rule is Market Basket Analysis.

Some popular unsupervised learning algorithms are as follows.

• K-means clustering
• KNN (k-nearest neighbours)
• Hierarchal clustering
• Anomaly detection
• Neural Networks
• Principle Component Analysis
• Independent Component Analysis
• Apriori algorithm
• Singular value decomposition

Clustering in Machine Learning

Clustering or cluster analysis is a way of grouping similar data points into clusters. The objects
with the similarities remain in a group that has less or no similarities with another group. It
does this by finding similar patterns in the unlabelled dataset, such as shape, size, colour,
behaviour, etc., and dividing them according to the presence and absence of those similar
patterns. The clustering technique is commonly used for statistical data analysis.

Dr. Saswati Mukherjee, School of Education Technology, JU

2
Note: Clustering is similar to the classification algorithm, but the dataset type differs. The
data set is labelled in classification, whereas we work with an unlabelled dataset in
clustering.

Example: Let's explore the clustering technique with a real-world mall example. In a shopping
mall, we can observe that similar-use items are grouped together. For example, T-shirts are in
one section, trousers are in another, and different types of fruits and vegetables are in separate
sections. Another example of clustering is grouping the documents based on their topics. Some
of the most common uses of this clustering technique are:
• Market Segmentation
• Statistical data analysis
• Social network analysis
• Image segmentation
• Anomaly detection, etc.
In addition to these general uses, Amazon uses clustering in the recommendation system to
provide personalised recommendations based on past product searches. Netflix also employs
this technique to suggest movies and web series to its users based on their watch history.
Figure 3 explains how the clustering algorithm works. The various fruits are divided into several
groups based on their similar properties.

Figure 3: Clustering Algorithm

Types of Clustering Methods

The clustering methods are broadly divided into hard clustering (data points belonging to only
one group) and soft clustering (data points belonging to another group). Below are the main
clustering methods used in machine learning:
a) Partitioning Clustering
b) Density-Based Clustering
c) Distribution Model-Based Clustering
d) Hierarchical Clustering
e) Fuzzy Clustering

Dr. Saswati Mukherjee, School of Education Technology, JU

3
1. Partitioning Clustering
K-Means is a partitioning clustering algorithm, also known as the centroid-based method,
which groups the unlabeled dataset into different clusters. It is an iterative algorithm that
divides the unlabelled dataset into k different clusters so that each data point belongs to only
one group with similar properties. It is a centroid-based algorithm where each cluster is
associated with a centroid. The main aim of this algorithm is to minimise the sum of distances
between the data point and their corresponding clusters. The algorithm takes the unlabelled
clusters, divides the dataset into k-number of clusters, and repeats the process until it does not
find the best clusters (Figures 3 and 4). Here, K defines the number of pre-defined clusters that
need to be assigned in the algorithm; for K=2, there will be two clusters; for K=3, there will be
three clusters, and so on.

Figure 3: No. of clusters = 4 Figure 4: Iterative Cluster formation

Suppose grouping the visitors in a museum using their age as follows.

16, 16, 17, 20, 20, 21, 21, 22, 23, 29, 36, 41, 42, 43, 44, 45, 61, 62, 66
Initial Cluster:
K=2
Centroid(C1) = 16 [16]
Centroid(C2) = 22 [22]
Note: These two points are chosen randomly from the dataset.
Iteration-1:
C1 = 16.33 [16, 16, 17]
C2 = 37.25 [20, 20, 21, 21, 22, 23, 29, 36, 41, 42, 43, 44, 45, 61, 62, 66]
Iteration-2:
C1 = 19.55 [16, 16, 17, 20, 20, 21, 21, 22, 23]
C2 = 46.90 [29, 36, 41, 42, 43, 44, 45, 61, 62, 66]
Iteration-3:

Dr. Saswati Mukherjee, School of Education Technology, JU

4
C1 = 20.50 [16, 16, 17, 20, 20, 21, 21, 22, 23, 29]
C2 = 48.89 [36, 41, 42, 43, 44, 45, 61, 62, 66]
Iteration-4:
C1 = 20.50 [16, 16, 17, 20, 20, 21, 21, 22, 23, 29]
C2 = 48.89 [36, 41, 42, 43, 44, 45, 61, 62, 66]
There was no change between Iterations 3 and 4, so the algorithm stopped. Therefore, the
clusters (16-29) and (36-66) are the two clusters.

K-means clustering algorithm mainly performs two tasks:

• Determines the best value for K-center points or centroids by an iterative process.
• Assign each data point to its closest K-center. Those data points that are near the particular
K-center create a cluster.

Steps in the K-Means algorithm:

Step 1: Initialize K, i.e., the number of clusters to be created.
Step 2: Randomly select K points from the dataset, which will be the initial cluster centroids.
Step 3: Measure the distance between each point and the centroid. Assign the data point to
the cluster whose centroid is closest to it, forming K clusters.
Step 4: Update the centroid by taking the mean of all data points assigned to each cluster.
Step 5: Repeat Step 3, i.e., reassigning each datapoint to the new closest centroid of each
cluster.
Step 6: If any reassignment occurs, repeat step 4; otherwise, stop.
Stopping criteria for K-Means clustering algorithm
1. Centroids of newly formed clusters do not change
2. Points remain in the same cluster
3. Maximum number of iterations is reached
Hence, each cluster has data points with some commonalities, and those with dissimilarities
are away from other clusters (Figure 5).

Figure 5: Cluster formation using K- Means

Dr. Saswati Mukherjee, School of Education Technology, JU

5
Elbow Method
The elbow method is a graphical method for finding the optimal number of clusters or value of
K. The within-cluster sum-of-square (WCSS) metric finds this optimal number of clusters. The
WSS is the sum of the squared distances between each data point and its cluster centroid. The
elbow method plots the WSS against the number of clusters and looks for the point where the
curve bends sharply, forming an elbow. This point indicates that adding more clusters does not
improve the WSS significantly and thus represents the optimal number of clusters. The
advantage of the elbow method is that it is simple and intuitive. The disadvantage is that it can
be ambiguous and subjective, as the elbow point may not be clear or unique. Equation 1
calculates the value of WCSS (for 3 clusters).

𝑾𝑪𝑺𝑺 = ∑(𝒙𝒊 −𝒄𝟏 )𝟐 − − − 𝑬𝒒. 𝟏

𝒊=𝟏

𝒘𝒉𝒆𝒓𝒆 , 𝒙𝒊 = 𝒅𝒂𝒕𝒂 𝒑𝒐𝒊𝒏𝒕 𝒂𝒏𝒅 𝒄𝒊 = 𝒄𝒍𝒐𝒔𝒆𝒔𝒕 𝒑𝒐𝒊𝒏𝒕 𝒕𝒐 𝒄𝒆𝒏𝒕𝒓𝒐𝒊𝒅

The elbow graph (Figure 6) shows the within-cluster sum-of-square (WCSS) values on the y-axis
corresponding to the different values of K on the x-axis.

Figure 6: Elbow graph

To calculate the value of WCSS (for 3 clusters) is given by Equation 2.

𝑊𝐶𝑆𝑆 = ∑ 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒(𝑃𝑖 𝐶1 )2 + ∑ 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒(𝑃𝑖 𝐶2 )2

Pi in Cluster1 Pi in Cluster2
) 2
+∑ 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒(𝑃𝑖 𝐶3 − − − 𝐸𝑞. 2
Pi in Cluster3

Following are the steps to find the optimal value of clusters using the elbow method.
• Execute the K-means clustering on a given dataset for different K values (1-10).
• For each value of K, calculate the WCSS value.

Dr. Saswati Mukherjee, School of Education Technology, JU

6
• Plots a curve between calculated WCSS values and the number of clusters K.
• The sharp point of the bend, or a point of the plot that looks like an arm, is considered the
best value of K.
Silhouette method
The silhouette method is a metric that evaluates how well each data point fits into its cluster
and how well it is separated from other clusters. The silhouette coefficient of a data point is the
difference between the average distance of the data points in the same cluster and the average
distance between the data points in one cluster and the data points in the neighbouring,
divided by the maximum of these two values (Figure 7).

Figure 7: Silhouette coefficient/score

The pairwise distances between each point and every other point i in a cluster 𝐶𝑖 are calculated
as given by Equation 3.
1
𝑎(𝑖) = ∑𝑗∈𝐶𝑖 ,𝑗≠𝑖 𝑑(𝑖, 𝑗) − − − 𝐸𝑞. 3
𝐶𝑖 −1
The distances between each point i in the cluster 𝐶𝑖 to all other points i in the cluster 𝐶𝑗 are
calculated as given by Equation 4. The cluster with the minimal mean distance is taken as 𝑏(𝑖).
𝑚𝑖𝑛
1
𝑏(𝑖) = 𝑗≠𝑖 ∑ 𝑑(𝑖, 𝑗) − − − 𝐸𝑞. 4
𝐶𝑗
𝑗∈𝐶𝑗
Equation 5 gives the silhouette coefficient/score (Figure 8) for a particular data point.
𝑏(𝑖) − 𝑎(𝑖)
𝑆(𝑖) = − − − 𝐸𝑞. 5
max{𝑎(𝑖), 𝑏(𝑖)}
Where,
• S(i) is the silhouette coefficient/score of the data point i.
• a(i) is the average distance between i and all other data points within the same cluster.
• b(i) is the average distance between i and all other data points outside/neighbouring
clusters.

Dr. Saswati Mukherjee, School of Education Technology, JU

7
Silhouette values lie in the [−1,1] interval, with -1 indicating a misclassified point, 1 indicating
that the point is closely tied with its cluster and poorly matched with the neighbouring clusters,
and a score of 0 means that there is no clear separation between the clusters and they might
overlap. Generally speaking, scores of 0.7 and higher are considered acceptable. The silhouette
method computes the average silhouette coefficient for each number of clusters and chooses
the one that maximises it. The average of the silhouette coefficient is calculated by Equation 6.
𝑛
1
𝑆𝐶 = ∑ 𝑆(𝑖) − − − 𝐸𝑞. 6
𝑛
𝑖=1
Figure 8 illustrates the silhouette score plotted against the number of clusters, ranging from 2
to 10. It shows that the silhouette score is maximised when the number of clusters is k=4. So,
the optimal number of clusters is 4. The silhouette method is robust but computationally
expensive and sensitive to noise and outliers.

Figure 7: Silhouette score for optimal k

To measure the distance between data points and the centroid, K-Means clustering supports
various kinds of distance measures, such as:
• Euclidean distance measure
• Manhattan distance measure
• A squared Euclidean distance measure
• Cosine distance measure

Advantages of K-means
• Simple and easy to implement.
• K-means is computationally efficient and can handle large datasets with high
dimensionality.

Dr. Saswati Mukherjee, School of Education Technology, JU

8
• Scalability: K-means can handle large datasets with many data points and can be easily
scaled to handle even larger datasets.
• Flexibility: K-means can be easily adapted to different applications and used with different
distance metrics and initialisation methods.

Disadvantages of K-Means
• Sensitivity to initial centroids: K-means is sensitive to the initial selection of centroids and
can converge to a suboptimal solution.
• Requires specifying the number of clusters: The number of clusters k needs to be specified
before running the algorithm, which can be challenging in some applications.
• Sensitive to outliers: K-means is sensitive to outliers, which can significantly impact the
resulting clusters.

2. Principal Component Analysis (PCA)

PCA is a method that reduces the dimensionality of large data sets by transforming a
large set of variables into a smaller one that retains most of the information in the
original set. The goal of dimensionality reduction is to replace a larger set of correlated
variables with a similar set of derived variables while discarding minimal information.
Smaller data sets are easier to explore and visualise, making data analysis simpler and
faster for machine learning algorithms by removing extraneous variables. The best way
to minimise the loss of information is by preserving variance. PCA is performed on a
covariance matrix with standardised numeric data variables. It is a statistical procedure
that converts a dataset into a new dataset containing linearly uncorrelated variables,
known as principal components.

Unlike factor analysis, PCA assumes no unique variance; the total variance equals the
common variance. If the total variance is 1, the common variance equals the
commonality. In simpler terms, PCA extracts the maximum variance from the dataset
and puts it into the first factor. The first factor, known as the First Principal Component,
captures the maximum variance in the dataset and determines the direction of the
highest variability in the data. No other component can have a higher variability than
the first principal component.

After identifying the first principal component, PCA removes the variance explained by
the first component and starts extracting the maximum variance for the second factor,
known as the Second Principal Component. It is also a linear combination of original
predictors that captures the remaining variance in the dataset and is uncorrelated with

Dr. Saswati Mukherjee, School of Education Technology, JU

9
the first principal component. All succeeding principal components follow a similar
concept, capturing the remaining variation without correlating with the previous
component. In general, for n*p dimensional data, a minimum of (n-1, p) principal
components can be constructed.

For a better understanding of PCA, a dataset of two different dimensions is considered

(Figure 6). The two dimensions are listed along the X-axis (Feature 2) and Y-axis
(Feature 1). Here, two vector components are defined as the First Principal Component
and the Second Principal Component and are computed based on a simple principle.
The components with a similar or greater variance are grouped under a single category,
and the components
Figure 5: Total Variance
with Figure 4: PCA Example varying or
smaller variance are grouped under the second category (Figure 7). Vectors calculated
in the Principal Component Method are not calculated randomly; they are combined as
linear components. Hence, a single straight vector of each component easily identifies
the feature difference. The direction of these components is identified in an
unsupervised way because the response variable is not used to determine the
component direction. Therefore, it is an unsupervised approach.

Figure 6: Elements that influence Figure 7: Variance structure of

observed variables observed variables

Steps in PCA
1. The range of continuous variables is calculated and standardised in this process to
analyse the contribution of each variable equally. Standardisation is done using
the following formula

Dr. Saswati Mukherjee, School of Education Technology, JU

10
2. Compute the covariance matrix to identify the correlation. A covariance matrix
of 2D data is shown here.

where,
The covariance of a number with itself is its variance (COV(X, X)=Var(X)) and (COV(Y,
Y)=Var(Y)). The entries of the Covariance Matrix at the main diagonal are symmetric,
i.e., covariance is commutative (COV(X, Y)=COV(Y, X)). If the value of the Covariance
Matrix is positive, then it indicates that the variables are correlated. (If X increases, Y
also increases and vice versa). If the value of the Covariance Matrix is negative, then it
indicates that the variables are inversely correlated. At the end of this step, correlations
of the variables are determined for categorisation.
• Compute the Eigenvectors and eigenvalues of the covariance matrix to identify the
Principal Components. The eigenvalues represent the principal components, and
these components represent the direction of the data. This indicates that if the line
contains many variables of large variances, there are many data points on the line.
Thus, there is more information on the line too. Finally, these principal components
form a line of new axes for easier data evaluation.
• Create a feature vector to decide the Principal Components.
• Recast the data along the Principal Component Axes. This step aims at the
reorientation of data from their original axes to the ones calculated from the
principal components. This is done by the following formula. [Final Data Set=
Standardized Original Data Set * Feature Vector]

Difference between PCA and FA

Although PCA is the default method for factor analysis, it is not a factor extraction
method. It is a data reduction technique to find components. There are technical
differences, factor analysis aims to reveal latent factors while PCA is only for data
reduction. While calculating the components, PCA does not assess the underlying
commonalities in the unobserved factors.
PCA components explain the total variance (i.e., no unique variance) in the observed
variables, whereas FA explains the covariance among variables. PCA components are
fully orthogonal to each other, whereas FA does not require factors to be orthogonal.
PCA component is a linear combination of observed variables, whereas in FA, the
observed variables are linear combinations of the unobserved variable or factor.

Dr. Saswati Mukherjee, School of Education Technology, JU

11