Scribd
Upload
14 views10 pages

Clustering and Outlier Detection Analysis

This document summarizes the results of a machine learning project analyzing medical data. Key findings include: 1) Hierarchical clustering using the ward linkage function best separated patients into clusters matching the actual disease status groups. 2) Gaussian mixture modeling with two components also produced similar valid results compared to the real patient groups. 3) Kernel density estimation identified several patient records as outliers due to unusual attribute value combinations, though most seemed physically possible. 4) K-nearest neighbors density and average relative density techniques also identified some outliers in low density regions.

Uploaded by

Riyaz Alam
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
14 views10 pages

Clustering and Outlier Detection Analysis

This document summarizes the results of a machine learning project analyzing medical data. Key findings include: 1) Hierarchical clustering using the ward linkage function best separated patients into clusters matching the actual disease status groups. 2) Gaussian mixture modeling with two components also produced similar valid results compared to the real patient groups. 3) Kernel density estimation identified several patient records as outliers due to unusual attribute value combinations, though most seemed physically possible. 4) K-nearest neighbors density and average relative density techniques also identified some outliers in low density regions.

Uploaded by

Riyaz Alam
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Technical University of Denmark

02450 Introduction to Machine Learning


and Data Mining

Project 3

s191985 Julian Böhm (Outlier Detection)


s196119 Emil Chrisander (Association Mining)
s192184 Jorge Montalvo Arvizu (Clustering Analysis)

December 2019
1 Clustering Analysis
To perform the hierarchical clustering it was necessary to perform the stan-
darization of the observations, given that our dataset presents high variance.
Apart from this, the variable famhist, which is a classification binary variable
taking values 0 or 1, was one-out-of-K coded. Therefore, our new dataset X is
a N xM matrix, where N = 462 and M = 14. The hierarchical/agglomerative
clustering was performed on the data matrix X using a maximum number of
clusters of 2, given that our target variable y consists of binary variables indi-
cating the presence of the sickness of the patient (observation). The clustering
was assessed by changing the linkage function and using the Euclidean distance
as the distance metric.

Linkage Function Cluster 1 Cluster 2


single 461 1
complete 16 446
average 461 1
ward 174 288

Table 1: Linkage functions - Observations allocated to each cluster

Table 1 shows the allocation of the observations in each cluster for each of the
linkage functions. The first three functions allocate most of the observations in
one cluster, as can be seen also from the dendrograms show in Figure 1a to 1c.
We can suggest that there may be outliers in the data, since the left-most side of
the dendrograms show a big height with only a few clusters. Nevertheless, the
ward function seems to obtain better results thanks to it’s nature of computing
the sum-of-squares error of the distance from each observation to its cluster
center. As a reference, the real classification is 160 persons with the disease
and 302 without the disease; which seem to somewhat match the ward function
classification results. Given the high dimensionality of our data, it’s hard to see
or interpret the results of the hierarchical clustering but we can at least obtain
a better visualization of them by projecting on the Principal Component 1 and
2 obtained in the Principal Component Analysis (PCA).

1
(a) Single

(b) Complete

(c) Average

(d) Ward

Figure 1: Hierarchical Clustering Results - Dendrograms

2
Figure 2 shows the results of each linkage function projected on PC1 and PC2;
where the colors represent the presence of the sickness (blue = not present,
orange = present), while the shape represent the cluster (circle = cluster 1,
cross = cluster 2). Only the ward function appears to cluster the observations
and allocate some of them correctly, compared to the real y classification, i.e.
blue circles in the upper-right side of Figure 2d.

(a) Single (b) Complete

(c) Average (d) Ward

Figure 2: Hierarchical Clustering Results - Projections on PC1 and PC2

We further analyzed the clustering by computing the supervised measures of


cluster validity: Rand Statistic, Jaccard coefficient and normalized mutual in-
formation (NMI), the results are shown in Figure 3 where the x-axis indicates
the linkage function (1=single, 2=complete, 3=average, 4=ward). Even though
the linkage functions single, complete and average seem to have better results
(similar to the real classification), this is in reality related to the results of Table
1; where almost all of the observations were classified in one particular cluster,
thus the validity measures show a high similarity value even though it’s only
taking all the observations and classifying them in one cluster. Again, the ward
function seems to give good results compared to the other linkage functions.

3
Figure 3: Validity measures - Linkage Functions

Next, we clustered our data using the Gaussian Mixture Model (GMM), where
we make use of the empirical mean, empirical covariance and empirical mass of
the clusters and iteratively update the parameters and calculate the likelihood
until we reach convergence or maximum iterations. Given the non-deterministic
nature of the model, we initialized it’s parameters by setting the number of fits
with different initialization to 10 and using the k-means method as initialization
procedure. We then proceeded to create a K-fold cross-validation for K = 1 to
10, the results are shown in Figure 4.

Figure 4: GMM Component - K-folded Crossvalidation, BIC and AIC

From the results, we can either take K = 2 or K = 3. By following the elbow


method, K = 2 is preferred by us. By selecting K = 2, we obtain the empirical
mean, covariance and mass of the clusters, i.e. the cluster center, shape and
relative size/density. By focusing on the centers µ, we can argue that these
empirical means are the centroids of the clusters that best fit the data, i.e. the
value of the parameter that maximizes the log of the likelihood of the data.

4
Figure 5: GMM Results - K=2

Figure 5 shows the results of the GMM with K=2. We can see that compared
to Figure 2d the results are similar, with the difference that GMM clustered the
top part of the graph in a single cluster, while hierarchical clustering did it only
in the bottom part of the top cluster. By computing the supervised measures
of cluster validity (Rand, Jaccard and NMI), we can compare the results of
GMM against the real classification and against the hierarchical clustering at
K=2 (which are the same results as above). Table 2 shows the results of
the comparison. We can see that even though the comparison between GMM
and Hierarchical clustering isn’t 100% similar, they both have almost identical
validity measures against the real classification. It is hard to decide which model
might be better given the high dimensionality of our data, but we can have a
good idea of how both approaches work and we can say that at least the quality
of the classification on both models is around 50%, depending on the validity
measure.

Measure GMM vs. Real GMM vs. Hierarchical


Rand 54.63 67.00
Jaccard 40.03 51.92
NMI 5.60 4.21

Table 2: Validity Measures - GMM vs. Real and GMM vs. Hierarchical Clus-
tering

2 Outlier and Anomaly Detection


In this section, we focus on the detection of outliers and anomalies. In general,
observation outliers are assumed to lie in regions with low density1 . Therefore,
we firstly estimate the density of the data set. Secondly, the observations located
in the low density regions are identified.
Following methods have been applied to evaluate the density distribution:
1 Introduction to Machine Learning and Data Mining. Chapter 20, 2019; Tue Herlau,

Mikkel N. Schmidt, Morten Mørup.

5
• Normalization of the data due to scale variation of the different parameters
• Kernel density estimation (KDE) using the leave-one-out cross-validation
• KNN density
• KNN average relative density (ARD)

Figure 6: Kernel Density Estimation: 20 observation located in the lowest den-


sity region

numbers of the 6 lowest-density observations


(ascending)
Kernel density estimation [44, 114, 345, 161, 374, 81]
KNN density (K=5) [44, 114, 345, 161, 397, 374]
KNN average relative density (K=5) [44, 114, 217, 218, 345, 67]

Table 3: The 6 lowest-density observations generated by different density esti-


mators

Results - Kernel density estimator (KDE): The results are generated


with an optimal kernel width λ of 0.25. In Figure 6, one can note that some
observations are present in regions with very low densities. After investigating
the table with sorted densities (excerpt in table 3), following observations could
be framed. Observation number 44 lies in the region with the lowest density
(1.68192e-23). Having a closer look at this observation, it seems unusual that
the value of obesity is with 46.58 the highest of the whole data set and adiposity
is in the lower range with 9.74 (range of adiposity in the data: min 6.74, max
42.49). Nevertheless, it is physically possible that a person has a very high
Body-Mass-Index but a low body fat percentage, e.g. athletes or muscular

6
people can show these characteristics2 . Supported by the fact that the suspect
neither consumes alcohol nor tobacco, we keep the observation in the data set.
Additionally, observations 114, 345 and 161 are located in a region with a low
density (from 1.47275e-20 to 1.87351e-14). However, in this observations no
contradictory or unrealistic values could be detected.

(a) KNN average relative density: 20 observa-


tion located in the lowest density region (K =
5)

(b) KNN density: 20 observation located in the


lowest density region (orange: K = 5)

Results - KNN density and average relative density (ARD): The


results are obtained using K = 5. Green and blue plots in figure 7b were pro-
duced using K = 2 and K = 10, respectively. The results gained by KNN
density and ARD are comparable to the ones of KDE. Table 3 shows the same
4 lowest-density solutions for KDE and KNN density. Besides, one can see a
deviation of ARD observations after the second lowest object. This may be
caused by the different non-probability based methodology of ARD. Finally, it
2 see [Link]

obesity-definition-full-story/

7
can be summarized that the methods showed us the observations which feature
some odd values. However, after checking the credibility of the observations, we
decided to exclude non.

3 Association Mining
We decided to set the aim of our association mining to find association rules
for a positive heart disease diagnose. That is, we want to explore whether
there are specific item sets (patient attributes) which are associated with a
positive heart disease diagnose. This allows us to create a simple screening
device that in principle could be used manually by health care personal in South
African villages. Before we present our association mining results, we explain
our procedure.

3.1 Association Mining Procedure


Our approach is:
1. Seperate numerical and categorical attributes into two groups.
2. For each numerical attributes we create a new string attribute indicating
whether the row value is within 1st , 2nd , 3rd , or 4th quartile. We ap-
ply quartiles, as it gives us a good mix of differences in attribute levels
while maintaining a sufficient amount of persons in each ’bin’. We did try
with both less and more granular percentiles for binarization. The most
convincing association rules were obtained when we applied quartiles.
3. We binarize the variables from step two using one-hot-encoding. Thus, we
obtain 4 binary attributes for each numerical attribute.
4. We binarize the categorical attributes using one-hot-encoding.
5. We combine the binarized numerical and categorical attributes into a sin-
gle data set.
6. We transform the binary values to attribute labels. I.e. a label value may
be age 75% to 100%, which indicates that the person is in the 4th quartile
in the age distribution of our sample.
7. We run the apriori algorithm using the apyori module in python. We tried
different values of support and conf idence to explore the forthcomming
rules. In our final analysis we apply support at 0.05 and conf idence at 0.6.
Recall, that only 35 percent of the sample have a positive heart disease.
Hence, we cannot expect to get any higher support than 0.35. A 0.05
value of support is equivalent to at least 23 persons in our sample having
the item set {X}. We do not go any lower than 0.05 to avoid association
rules based on very few people in our sample. We set confidence at 0.6 to

8
ensure that more than 60% do actually have the heart disease when they
have an item set {X}.
8. As an additional feature we also calculate the so-called lift. Lift is a
measure of how more likely the item set X is when Y is include3 . In our
context it tells us something about how much more likely a person is to be
diagnosed with a heart disease if the person has a given item set X. I.e.
if the lift is 3 for X, Y = {age 75% to 100% chd yes}, we know the 4th
quartile of age is three times more likely to have a heart disease diagnosed.

3.2 Association Mining Results


Table 4 shows our 7 identified association rules. The rules are ordered by their
support size. The rules are surprisingly intuitive and close to what one would
expect. We only obtain rules based on two or three items. 6 out of 7 rules
include a presence of heart diseases in the family. For example, if a person has
a family history of heart diseases and the person is in the 4th quartile of the
ldl (”bad cholesterol”) distribution, the person is 7.2 times more likely to have
a heart disease than not having one. The support of this rule is 0.1. Hence, 10
percent of the sample apply to this rule. Another interesting association rule
is {X, Y } = {[tobacco 75% to 100%, age 75% to 100%], chd yes}. It has a sup-
port of 0.07 and lift of 9.1 making it a relatively strong screening rule. Moreover,
the doctors would not need to make any medical examinations of the patient to
determine the age and tobacco consumption. Thus, in practice this would make
it a very low cost and feasible screening device rule. Obviously, the rule would
have to be re-transformed into actual levels of age and tobacco consumption
prior to handing out to local village doctors.

We conclude that association rule mining has a strong potential to serve as


simple low cost screening devices for the Ischaemic heart disease in local South
African villages.

X Y support confidence lift


ldl 75% to 100%, famhist present yes chd yes 0.10 0.72 7.2
adiposity 75% to 100%, famhist present yes chd yes 0.08 0.63 7.9
age 75% to 100%, famhist present yes chd yes 0.08 0.70 8.8
sbp 75% to 100%, famhist present yes chd yes 0.08 0.64 8.0
tobacco 75% to 100%, famhist present yes chd yes 0.08 0.64 8.0
tobacco 75% to 100%, age 75% to 100% chd yes 0.07 0.64 9.1
adiposity 75% to 100%, obesity 75% to 100%, chd yes 0.05 0.61 12.2
famhist present yes

Table 4: Association rules for heart disease being diagnosed

3 see [Link]

Common questions

Powered by AI

Kernel Density Estimation (KDE) and KNN density methods both identify observations in low-density regions, aiding outlier detection. KDE utilizes a continuous approach estimating the density distribution with a kernel function, which is parameterized by a bandwidth λ. This method identified outlier observations by calculating very low density values for some data points like observation 44. KNN density, on the other hand, relies on localized density estimates based on the number of neighbors, providing similar results with small deviations due to its non-probability-based methodology. Despite the different approaches, both methods identified similar outlier observations .

Imbalanced cluster sizes in hierarchical clustering can lead to misleading interpretations, with larger clusters potentially masking smaller clusters' distinct characteristics. This imbalance might result from methods like single linkage, which can agglomerate most data into few clusters while ignoring smaller, meaningful groups. Such skewness complicates interpretation and validity evaluation, as observed when single, complete, and average linkage functions produced large single clusters compared to a more even distribution with ward linkage. An imbalanced outcome can distort subgroup analysis and affect subsequent data-driven decisions or clustering effectiveness .

The empirical mean of clusters in GMM aids interpretation by serving as the centroid of each cluster, offering a point of reference for understanding cluster characteristics. By analyzing these means, which maximize the likelihood of the observed data under the model, researchers can deduce the central tendency of each cluster. This allows interpretation of distinct group patterns and differences between clusters, whether identifying which features have higher means or comparing cluster positioning along specific axes .

The choice of the number of clusters in Gaussian Mixture Model (GMM) is influenced by methods like cross-validation and model selection criteria such as BIC and AIC. The elbow method applied to these criteria suggests an optimal K value based on a noticeable change in the plot slope. In the case provided, K=2 was preferred due to this method, which implies the model parameters at K=2 provide adequate data fit while avoiding overfitting. The specific cluster centers, shape, and density also play a role, with empirical observation of how clusters separate aiding in this decision .

The main differences between Gaussian Mixture Model (GMM) and hierarchical clustering are in their approach and outcomes. GMM uses probabilistic models to cluster data, updating parameters like mean and covariance to maximize likelihood. It showed similar, though not identical, validity measures to hierarchical clustering against real classifications, with flexibility in fitting data due to probabilistic nature. Hierarchical clustering, particularly with the ward method, uses agglomerative approaches based on variance minimization. The clusters' geometric center and distribution differ, as observed in cluster centers for K=2 in GMM compared to hierarchical dendrograms .

Association rules generated through the apriori algorithm suggest combinations of attributes more likely associated with heart disease, offering potential screening mechanisms. By evaluating attributes using the apriori algorithm, rules like high LDL levels in the 4th quartile combined with family history of heart disease significantly increase disease likelihood (e.g., a lift of 7.2). Such rules can be rapid, low-cost, and utilized by healthcare providers without elaborate tests, as they leverage observable attributes such as age and family history, enhancing early screening possibilities and practical application in resources-constrained environments .

In association rule mining, lift measures how much more likely a combination of attributes is to result in a condition, such as a heart disease diagnosis, compared to random chance. It indicates the strength of a rule beyond coincidence. For instance, a lift of 7.2 for a rule indicates that individuals with high LDL levels and family history of heart disease are 7.2 times more likely to have heart disease. Lift values thus help identify the most impactful attribute combinations for disease diagnosis, with higher values highlighting more significant predictive relationships .

High-dimensional data presents challenges in clustering analysis due to the 'curse of dimensionality,' where distance metrics become less meaningful as dimensions increase. This affects cluster formation, as distances between data points tend to converge, complicating the identification of distinct clusters. Additionally, visualization of clusters becomes less intuitive. In the discussed project, projecting onto principal components aided visualization but didn’t fully overcome analysis complexity. These challenges underscore the need for careful choice of distance metrics and dimensionality reduction techniques to achieve meaningful clustering outcomes .

The ward linkage function performs better than single, complete, and average linkage functions in hierarchical clustering. While single, complete, and average linkage mainly allocate observations into one cluster, ward produces more evenly distributed clusters (174 and 288). Ward calculates clusters based on sum-of-squares error, aligning better with actual classifications (160 patients with the disease and 302 without). This suggests ward offers a more balanced clustering compared to the other linkage functions .

Data standardization impacts hierarchical clustering by ensuring variance homogeneity across observations, which is crucial for accurate distance-based classification. Standardization negates the effects of variables having different scales or units, allowing the algorithm to treat all dimensions equally during clustering. Without standardization, features with larger scales could unduly influence the results. In the hierarchical clustering process discussed, standardization helped manage high variance in the dataset, contributing to more meaningful clusters .

You might also like