The intended reader for this thesis is a masters student or a professional with basic computer science skills and with some previous knowledge of machine learning and clustering. This thesis may also be of interest to medical personnel.
This thesis has 5 main sections. Section 2 gives an introduction to clustering in general, and a detailed description of existing algorithms, configurations, pre-processing methods and clustering validation methods used in this thesis. Section 3 describes the patient record on which the clustering methods are applied, and also describes tools utilised in this thesis. Section 4 describes the plan for the experiments which includes feature extraction, data preprocessing, clustering pro-cedure and clustering evaluation for each clustering task. Section 5 describes the results from the experiments. Section 6 explores, explains and discusses discover-ies or unexpected results obtained through the accomplishment of the clustering tasks. Section 7 summarises the findings of this thesis.
1.8 How to read this thesis 1 INTRODUCTION
2 CLUSTERING METHODS
2 Clustering methods
This section has two main objectives. Firstly, the section argue for the choice of which methods to utilise during the clustering procedures. Types of methods are clustering algorithms, distance measures, cluster validity/quality measures and preprocessing methods. Secondly, the concrete methods utilised in the thesis are explored for each type of method. Section 2.1 deals with clustering algorithms, Section 2.2 deals with the distance measures, Section 2.3 treats the validity indices while Section 2.4 deals with methods for preprocessing.
2.1 Clustering algorithms
According to (HK01) and (H.D02), there are several conceptual groups of clus-tering algorithms. The main groups are hierarchical clusclus-tering, which creates a hierarchical decomposition of the data set; partitioning methods, which partition the data into non-overlapping groups; density-based methods, which consider the density in the neighborhood of an object and grid-based methods, which partition the object space into a finite number of cells to improve the processing time. The two clustering algorithms implemented in this thesis were hierarchical clustering and the partitioning methodk-means clustering.
The main reason why hierarchical clustering was selected was the known lack of knowledge of the number of clusters underlying in the data set, and the size and shape of those clusters. Hierarchical algorithms do not require any input parameters from the user but can potentially give an idea of what the most correct number of clusters in the data set may be. Moreover, the algorithm can be run with several different strategies to how to select objects to merge or split.
Each of these strategies will tend to find clusters of different shapes and sizes, such that the quality of the results obtained by the different strategies will indicate the shape or size of the clusters hidden in the data set. These observations can then be used to guide the choice of algorithms or input parameters suitable for the data set. The hierarchical clustering method is also well-known and frequently used. The main disadvantage associated to hierarchical clustering is that objects are never moved between clusters, which can potentially hinder the algorithm to find the ideal clusters.
The k-means algorithm has its strength in the iterative moving of data objects between the clusters and was therefore believed to be strong where the hierarchical algorithm was weak. Due to this repeated object replacements the computation is more costly than the computation associated to the hierarchical clustering. The
k-2.1 Clustering algorithms 2 CLUSTERING METHODS
means method is therefore suitable only for data sets of size small-medium, which was the expected size of the data sets designed in this thesis. K-means tend to form spherical clusters of similar size. The disadvantage of k-means clustering is the need for calculating a mean object to represent each cluster. The method therefore does not work for categorical attributes, which are attributes that take a number of discrete values with no internal order. Due to the calculation of mean values, the k-means algorithm also suffer from outliers.
Other algorithms were also considered but refused due to a variety of reasons. The hierarchical clustering algorithms Birch and Cure were rejected due to a limiting branch structure and the demand for crucial input parameters respectively. The partitioning method Clarans, the density-based method DBscan and Denclue and the grid-based method Wave-cluster were also rejected due to influential input parameters such as the number of clusters, branching factor, neighborhood radius, cluster radius and the number of grids. The two selected algorithms are explored in the following paragraphs.
Hierarchical clustering As mentioned, the hierarchical clustering algorithms create a hierarchy of clusterings in the given set of data objects. The algorithm can be either agglomerative or divisive. An agglomerative clustering algorithm starts with each object forming a separate group, and merge two and two groups until all the objects belong to one group. The divisive approach starts with all the objects in the same cluster, and splits a cluster until each object forms its own cluster. The agglomerative approach is the one used in this thesis.
There are several strategies for how to choose which two clusters to merge next.
Three strategies are considered in this thesis: the minimum distance strategy, the maximum distance strategy and the average distance strategy.
• The minimum distance strategy merges the two clusters with the smallest minimum distance, where the minimum distance is given by
dmin(Ci, Cj) = min|p−p0|, p∈Ci, p0 ∈Cj (1) More intuitively, the minimum distance strategy merges the two clusters with the two closest objects that are not yet in the same cluster.
• The maximum distance strategy merges the two clusters with the smallest maximum distance, where the maximum distance is given by
dmax(Ci, Cj) =max|p−p0|, p∈Ci, p0 ∈Cj (2)
2 CLUSTERING METHODS 2.1 Clustering algorithms
This means that the maximum distance strategy merges the two clusters with the smallest maximum distance between two objects connected one to each cluster.
• The average distance merges the two clusters with the smallest average distance between two objects belonging one to each cluster. The average distance is given by
davg(Ci, Cj) = 1/(ni∗nj)X
p∈Ci
X
p0∈Cj
|p−p0| (3)
where ni is the number of objects in clusterCi.
K-means clustering The k-means clustering algorithm organises the objects into k partitions, where each partition represents a cluster. The algorithm first chooses k random objects to represent the k clusters. The other objects are assigned to the cluster for which the representing point is most similar. Then, for each cluster, a mean object is calculated based on the objects in the cluster, and all the objects in the data set are reassigned to the cluster with the most similar mean. The algorithm is repeated until there are no reassignments. The algorithm is described in Figure 2. The k-means algorithm can only be applied to data objects represented in such a way that a mean can be calculated.
Input:
Number of clusters k and database containing n objects Output:
A set of k klusters that minimizes the mean square error 1. Choose k random objects as the initial cluster "means"
2. While changes
a) assign each object to the same cluster as the most similar mean object
b) calculate new mean for each cluster based on the objects assigned to that cluster
Figure 2: The k-means algorithm