# Two Medoid-Based Algorithms for Clustering Sets
## 1 Introduction  
Unsupervised clustering aims to group data into clusters in such a way that data within the same cluster are similar to each other, and data in different clusters are dissimilar. K-means [1, 2] is a widely used clustering algorithm due to its simplicity and efficiency. Another reason to prefer K-means instead of a more sophisticated algorithm is the fact that its properties and limitations have been thoroughly investigated [3, 4]. Two main limitations of K-means are that (1) it operates on numerical data using Euclidean distance and (2) it requires calculation of the mean of the objects (centroid) in the set. Dealing with data that have mixed numerical and categorical attributes or only categorical attributes is difficult [5]. Such data can be handled either by preliminarily converting, most often in an unnatural way that can imply sparsity and multi-dimensional problem, categorical attributes to numerical ones, or by introducing a non-Euclidean distance function. Adapting K-means to deal with data objects which are sets of elementary items [6] poses similar problems to coping with categorical attributes. In addition, the need exists to handle sets of different sizes. A histogram-based approach has been used for clustering categorical data [5, 7] and recently for clustering sets [8]. The idea is to use a histogram of the categorical values to represent the cluster. This eliminates the need to define the mean value. In the case of categorical data, the distance to the cluster can be defined based on the frequency of the category labels of the object in the cluster. In the case of sets, the distance between objects and the clusters can be derived from classical set-matching measures such as Jaccard and Otsuka-Ochiai cosine distance [8]. As a practical example of an application of clustering sets, the records of medical patient diagnoses can be considered, where the goal is to find groups of similar patients to support the estimation of the risk for a patient to develop some future illness due to his/her previous medical history and from correlations to other patients with similar diseases. In this paper, we propose a new approach for clustering sets which is based on K-medoids. Medoid is the object in the cluster having a minimum total distance from all other objects in the cluster. Then, all we need is a distance measure between the objects. Since both the data and the cluster representative (medoid) are sets, we can apply the classical set-distance measures slightly modified, as in [8], by considering application-sensitive information. We apply the medoid approach within two clustering algorithms: K-medoids [9; 10] and random swap [11; 12]. The proposed approach retains the generality and effectiveness of the corresponding K-sets and K-swaps algorithms described in [8] at the cost of a somewhat slower running time. The original contributions provided by this paper are the following:  
* Introducing two new algorithms for clustering sets: K-medoids and random swap using medoid and the two classical set-matching distances of Jaccard and Otsuka-Ochiai cosine coefficients [13], adapted by considering the frequency of use of the items in the whole dataset. * Exploring the effect of random initialization versus K-means++ initialization [14; 15; 16; 17; 18]. * Implementing parallel variants using Java parallel streams and lambda expressions [12; 19; 20], which provide better time efficiency on a multi-core machine. The effectiveness of the new approach is demonstrated by applying it to the 15 synthetic datasets used in [8]. The algorithms both achieve good clustering quality, which is very similar to that of the previous K-swaps algorithm. However, the proposed medoid-based approach is simpler to implement, and it avoids the threshold parameter for truncating the histogram size. While this might not be the big issue with most data, there are always some potential pathological cases that the proposed approach is likely to avoid.