# A Review on Clustering Techniques: Creating Better User Experience for Online Roadshow
## 2 Clustering Techniques
### Partition-Based Clustering  
The partition-based clustering uses an iterative method, based on a selected distance measure to update the clusters, until an optimal partition is obtained [21]. In this technique, the number of the resulting clusters is pre-defined by the user. There are two notable partition-based clustering techniques that are used in web usage mining, namely the _k-means_ and _k-medoids_. _K-means_** clustering** is a case where the cluster is represented by its centroid. The centroids that are selected do not have to be a member of the cluster. The basic steps are illustrated in Figure 2.  
1. Randomly select centroids for each cluster. 2. Calculate the distance of all data points to the centroids and assign them to the closest cluster. 3. Get the new centroids of each cluster by taking the mean of all data points in the cluster. 4. Repeat steps 2 and 3 until all the points converged and the centroids stop moving. _K-means_ clustering is one of the easiest techniques to implement, as it is easy to interpret and understand. In [22; 23; 24; 25; 26], the conventional _k-means_ clustering technique is applied for web usage mining. As _k-means_ clustering has its drawbacks, such as the need to predetermine the number of clusters and its high sensitivity to outliers, many researchers work on improving this technique. There is a slight difference between the conventional _k-means_ clustering technique with [27; 28]. In the modified _k-means_ clustering technique [27], the old cluster centroid value is updated by delta, where delta is the average distance value of each cluster. When the modified technique is tested with the conventional _k-means_ on a simple dataset, the results revealed that the modified _k-means_ clustering works better than the basic technique in terms of reducing the number of iterations taken to converge and the quality of the clusters formed. Instead of randomly choosing the initial centroid value, the centroid values are calculated with an additional step to divide between the minimal and the maximal intra-cluster distance in [28]. In another study, [PERSON] et al. [29] performed particle swarm optimization (PSO) to the data after applying _k-means_ clustering. The PSO will group the data objects based on the minimum distance criterion and evaluate the fitness function. The combination of PSO and _k-means_ clustering shows a more promising performance than the conventional _k-means_ clustering. _K-medoids_ clustering works in a similar way to _k-means_ clustering. However, unlike _k-means_ clustering, the medoid (centre value) in _k-medoids_ clustering must be a member of the cluster, where its dissimilarities with all other points in the cluster are at the minimum. The basic steps of _k-medoids_ clustering are illustrated in Figure 3.  
1. Randomly select \(k\) random points out of the data points as medoids. 2. Calculate the distance of all data points to the medoids and assign them to the closest cluster. 3. Randomly select one non-medoid point and recalculate the cost. 4. Swap the medoid with the non-medoid point as the new medoid point if the swap reduces the cost. 5. Repeat steps 2 to 4 until all the points converge and the medoid point stop moving. As _k-means_ clustering is more sensitive to outliers, _k-medoids_ clustering is claimed to be more robust than _k-means_ because medoids are less influenced by outlier [30]. In [30; 31; 32], the authors performed the traditional _k-medoids_ clustering technique on the dataset. [PERSON] et al. [33] improved the clustering quality of _k-medoids_ by not selecting the initial medoids at random. Instead, \(k\) data points that differ greatly from each other are added into the existing data and are used as the initial medoids, where \(k\) is the number of clusters. In [34], [PERSON] et al. also modified the calculation of the centroid by introducing the alpha and beta values as the thresholds for choosing the initial medoids and determining if a particular data point is an outlier.