# Two Medoid-Based Algorithms for Clustering Sets
## 3 Medoid-Based Approaches
### New Distance Functions  
A dataset is defined as a set \(X\) of \(N\) objects, where each object \(X_{j}\) is a set of \(l\) items taken from a vocabulary of \(L\) distinct items:  
\[X_{j}=\left\{x_{j\mu}\right\}_{i=1}^{l}\]  
From the dataset, a global histogram \(H\) is built from all the \(L\) items and their corresponding frequencies in the dataset, denoted by \(f_{H}(x_{i})\). The global histogram was adopted because the frequency of occurrences of an item (for example the disease code in a medical application) naturally can be interpreted as the relative importance of the item with reference to all the other items. Similar to [8], the global frequency of an item, instead of its local frequency in a cluster, is here used as an application-dependent weight (priority) which replaces 1 when counting, by exact match, the size of the intersection of two sets. We use two weighted distance functions, _Jaccard_ and _Otsuka-Ochiai cosine distance_. They are defined as follows:  
\[d_{f}(X_{1},X_{2})=1-\frac{\sum_{x_{j}}\delta\left(x_{j}\right)}{\sum_{x_{j}} \delta\left(x_{j}\right)+\sum_{x_{j}}\delta\left(x_{i}\right)} \tag{4}\]  
\[d_{C}(X_{1},X_{2})=1-\frac{\sum_{x_{j}}\delta\left(x_{j}\right)}{\sqrt{\sum_{ x_{j}}\delta\left(x_{j}\right)+\sum_{x_{j}}\delta_{1}\left(x_{i}\right)} \times\sqrt{\sum_{x_{j}}\delta\left(x_{j}\right)+\sum_{x_{i}}\delta_{2}\left(x _{i}\right)}} \tag{5}\]  
Here, \(\delta\left(x_{j}\right)=f_{H}(x_{j})\) if \(x_{j}\in X_{1}\cap\ X_{2}\), 0 otherwise; \(\overline{\delta}\left(x_{i}\right)=1\) if \(x_{i}\
otin X_{1}\cap\ X_{2}\), 0 otherwise; \(\delta_{1}\left(x_{i}\right)=1\) if \(x_{i}\in X_{1}\backslash X_{2}\), 0 otherwise; \(\delta_{2}\left(x_{i}\right)=1\) if \(x_{i}\in X_{2}\backslash X_{1}\), 0 otherwise. So, the maximal distance between two sets is 1 and the minimal one is 0. If the weights of items evaluate to 1, the two distance measures reduce to the standard Jaccard and cosine distances. The use of modified \(d_{J}\) or \(d_{C}\) distance measure, enables K-medoids [9; 10] (see Algorithm 1) and random swap [11; 12] (see Algorithm 2) to easily adapt to sets, and also to possibly exploit careful seeding methods. _Input_: The dataset \(X\) and the number \(K\) of required clusters  
_Output_: The partitions and medoids of the emerged clustering solution, together with some accuracy measures including the \(SDM\) cost  
1. _Initialization_. Initialize the \(K\) medoids by a certain seeding method  
2. _Partitioning_: Assign each data object \(X_{i}\in X\) to the cluster \(C_{j}\), if \(m_{j}=nm(X_{i})\)  
3. _Update_. Define the new medoid of each cluster as that data object \(m^{\prime}_{j}\) which has minimal sum of the distances from all the remaining points of the cluster:  
\(m^{\prime}|_{j=1}^{K}=Y\in C_{j}\) : \(Y=argmin_{X_{j}\in C_{j}}\sum\limits_{X_{i}\in C_{j},X_{j}\
eq X_{i}}d\left(X _{p},X_{i}\right)\)  
4. _Check termination_. If medoids are not stable, restart from Step 2; otherwise stop  
**Algorithm 1: Pseudo-code of K-Medoids for sets**  
_Input_: The dataset \(X\) and the number \(K\) of required clusters  
_Output_: The partitions and medoids of the emerged clustering solution, together with some accuracy measures including the \(SDM\) cost  
1. _Initialization_. Initialize the \(K\) medoids by a certain seeding method  
2. _Initial Partitioning_. Assign data objects to clusters according to the nearest initial medoids;  
\(previous\_cost=SDM\)  
Repeat \(T\) times:  
1. _Susp_. A medoid is uniform randomly chosen in the vector of medoids, and it gets replaced by a data object uniform randomly chosen in the dataset:  
\(m_{s}\ \leftarrow\ X_{i}\), \(s=rand(1,K)\), \(i=rand(1,N)\)
2. _Medoids refinement_. A few iterations of K-medoids (Algorithm 1) are executed to refine medoids; \(current_{cost}=SDM\)
3. _Test_. If(\(current\_cost<previous\_cost\)) then the new solution is accepted and becomes current for the next iteration, with \(previous\_cost=current\_cost\); otherwise, previous medoids and corresponding partitioning are restored.