# Simple K-Medoids Partitioning Algorithm for Mixed Variable Data
## 2 Related Works and the Proposed Method
### Proposed K-Medoids Algorithm  
Even though SFKM can adopt any distances, this algorithm was originally simulated in pure numerical and categorical datasets. It performs well in a balanced orientation of a simulated numerical dataset. Unfortunately, when it comes to an unbalanced orientation dataset, the result is poor (Figure 1a). The dataset in Figure 1a has 800 objects with two variables [20]. The objects are assigned into five clusters, and the clusters have a spatially-unbalanced orientation in a two-dimensional space. Thus, we develop a simple k-medoids (SKM) algorithm, which also applies medoid updating within its clusters in k-medoids setting. The term \"simple\" is borrowed from the SFKM algorithm for the initial medoids selection. What distinguishes the SFKM and SKM algorithms is that SKM considers the local optima and empty clusters. To minimize the local optima problem, several initializations have been used [21]. The SKM algorithm is as follows:  
1. Select a set of initial medoids \(\mathcal{M}_{k}\), i.e., selecting \(k\) objects from \(X_{n}\), randomly. The random initialization is preferred because the random initialization repeated several times is the best approach [21]. However, a restriction is applied to a single point of the \(\mathcal{M}_{k}\) set. One of the \(\mathcal{M}_{k}\) sets, which is randomly selected, is replaced by the most centrally-located object. It is argued that an optimal medoid is when \(k=1\) is the centrally-located object that minimizes the sum distance to the other objects. Then, the most centrally-located object can be selected based on the row/column sum of the distance matrix. It is given as: \[a_{i}=\sum_{j=1}^{n}d_{ij}=\sum_{j=1}^{n}d_{ji},\quad i=1,2,3,\ldots,n,\] where \(a_{i}\) is the sum distance of the object \(i\) to the other objects. If vector \(a_{i}\) is ordered, the first \(\mathcal{M}_{k}\) is selected by the smallest \(a_{i}\), which is the most centrally-located object. Note that one/more medoids from the medoids set \(\mathcal{M}_{k}\) can be non-unique objects, for example, two medoids have equal values in all their variables. 2. Assign the label/membership of each object \(x_{n}\in X_{n}\), \(l(x_{n})\), to the closest medoid \(\mathcal{M}_{k}\). When the medoid set of \(\mathcal{M}_{k}\) is non-unique objects, an empty cluster can occur because the non-unique medoids and their closest objects will have the same membership label. To avoid an empty cluster, the non-unique medoids are restricted to preserve their label. While the closest  
Figure 1: The simple and fast k-medoids (SFKM) (**a**) and simple k-medoids (SKM) (**b**) partitioning results. objects to the non-unique centroids can be labeled as any cluster membership in the k-means case [18], we regulate that the closest objects to the non-unique medoids are assigned/labeled as only one of the medoids, i.e., a single cluster membership. Hence, this guarantees a faster medoid updating step provided that the non-unique medoid set is not the most centrally-located object. 3. Update the new set of medoids \(\mathcal{M}_{k}\), maintaining the clusters label \(l(x_{n})\) fixed. \[m_{p} := \underset{p\in K}{argmin}\sum_{n:l(x_{n})=m_{p}}d(x_{n},m_{p}),\] \[p=1,2,3,\ldots,k\] A medoid, \(m_{p}\), is defined as an object that minimizes the sum distance of this object to the other objects within its cluster. 4. Calculate the sum of each cluster sum distance (\(E\)), i.e., the sum distance between objects and their medoids. \[E=\sum_{p=1}^{k}\ \sum_{n:l(x_{n})=m_{p}}d(x_{n},m_{p}).\]
5. Repeat Steps 2-4 until \(E\) is equal to the previous \(E\), or the set of medoids \(\mathcal{M}_{k}\) does not change, or a pre-determined number of iterations is attained. 6. Repeat Steps 1-5 \(s\) times to attain multiple random seeding of the initial medoids. Note that the centrally-located object always becomes one of the initial medoids. Among the cluster medoids from the multiple random seeding \(s\), the cluster medoid set that has a minimum value of \(E\) is selected as the final cluster medoids. 7.