# A Review on Clustering Techniques: Creating Better User Experience for Online Roadshow
## 2 Clustering Techniques
### Hierarchical Clustering  
The hierarchical clustering technique can be further categorized into agglomerative (bottom-up) and divisive (top-down) approaches. The hierarchical clustering works by grouping objects in a hierarchical manner, which is a tree of cluster [35]. The result of the agglomerative hierarchical clustering can be visualised using a dendrogram to show how the clusters are formed. The resulting clusters are then determined by slicing the dendrogram with a horizontal line. Although partition-based clustering techniques are simple to implement, the number of clusters has to be predetermined beforehand. Thus, many researchers need to experiment with different \(k\) values to get the optimal clusters. On the contrary, the number of clusters does not need to be predetermined in agglomerative hierarchical technique. However, the divisive hierarchical clustering requires the number of clusters to be predetermined. Both types of hierarchical clustering techniques have its own disadvantages. The clusters cannot be undone once it is merged or split. Therefore, many researchers designed the improved version of hierarchical clustering techniques to overcome the limitation of the original technique. For the agglomerative approach, _CURE_ and _CHAMELEON_ techniques are discussed. In agglomerative hierarchical clustering techniques, each observation starts in its own cluster, and pairs of clusters are merged as it moves up the hierarchy. _CURE_ is an agglomerative hierarchical clustering technique that adopts a middle ground between the centroid and the all-point extremes. The basic steps are illustrated in Figure 4.  
Figure 4: Basic steps of _CURE_. Figure 3: Basic steps of _k-medoids_ clustering. In [36], the authors compared the traditional and optimized version of the _CURE_ technique to perform clustering in their weblog data. The _CURE_ technique is optimized by introducing two components. The two components are the initialization of the initial clusters and the use of k-dimensional (k-d) tree and heap tree data structures. When the cluster quality of both traditional _CURE_ and optimized _CURE_ are measured, the optimized algorithm shows a more promising result [37]. As _CURE_ chooses random points as representative points from each cluster, this gives a problem when the datasets do not have a centroid tendency. To overcome this problem, [PERSON] et al. proposed using shared nearest neighbours (SNN) of the data points to form clusters. The authors aim to apply this improved _CURE_ technique in data mining to uncover beneficial information from a big amount of data. Nevertheless, the improved _CURE_ clustering technique from [PERSON] et al. is yet to be applied in web usage mining. _CHAMELEON_ is an agglomerative hierarchical clustering technique that uses dynamic modelling. _CHAMELEON_ measures the similarity of two clusters based on a dynamic model. It has two major phases: (1) partitioning and (2) merging. The basic steps are illustrated in Figure 5.  
1. Construct a k-NN graph. 2. Partition the graph to produce equal-sized partitions and minimize the number of edges cut using a partitioning algorithm. 3. Merge the partitioned clusters whose relative interconnectivity and relative closeness are above some user-specified thresholds. The key steps are partitioning and merging. The partitioning process has three stages, namely the coarsening phase, initial partitioning phase, and the uncoarsening phase. In the coarsening phase, the size of the hypergraph is decreased by reducing the number of vertices. In the initial partitioning phase, the hypergraph of a smaller size after the coarsening phase is partitioned. In the uncoarsening phase, the partitioned hypergraph is projected to the finer next level hypergraph by using a partitioning refinement algorithm to optimize the objective function without violating the partitioning balancing constraints.