# Clustering of a Health Dataset Using Diagnosis Co-Occurrences
## 2 Materials and Methods
### Statistical Analysis: A New Hierarchical Agglomerative Clustering Algorithm
#### 2.2.3 The HAC-Cooc Algorithm  
This section describes the proposed Hierarchical Agglomerative Clustering for co-occurrence analysis, denoted HAC-cooc, which clusters the blocks of diagnoses [23; 24]. The algorithm constructs a clustering solution by first considering each diagnosis block as a cluster and then by iteratively agglomerating pairs of diagnosis clusters using a local rule based on the maximization of the RR measure. Let \(\text{S}^{(t)}=\left\{\text{C}_{1}^{(t)},\ldots,\text{C}_{\text{N}^{(t)}}^{(t) }\right\}\) be the clustering solution at iteration \(t\in\left\{1,2,\ldots,\text{D}-1\right\}\) of the algorithm. Instead of using the [PERSON] recurrence formula traditionally used to update the measures of similarity with each new agglomeration [34], the relation (1) is performed at each stage of agglomeration for each pair of clusters, leading to a set of \(\text{RR}_{\text{C}_{k}^{(t)},\text{C}_{1}^{(t)}},\ \forall k,1\in\left\{1, \ldots,\text{N}^{(t)}\right\}\). To select the cluster pair to agglomerate, two rules (a) and (b) are used and compared. The rule (a) can be expressed as:  
\[\theta_{\text{a}}^{(t)}=\text{argmax}_{\text{k},\text{l}\in\left\{1,\ldots, \text{N}^{(t)}\right\}}\text{RR}_{\text{C}_{k}^{(t)}}\text{C}_{1}^{(t)} \tag{6}\]  
where \(\theta_{\text{a}}^{(t)}\) is the pair of clusters indices chosen for current agglomeration with rule (a). Rule (a) simply selects the best current link while rule (b) uses a more indirect approach:  
\[\theta_{\text{b}}^{(t)}=\text{argmax}_{\text{k},\text{l}\in\left\{1,\ldots, \text{N}^{(t)}\right\}}\frac{\text{RR}_{\text{C}_{k}^{(t)}}\text{C}_{1}^{(t)}} {\text{max}\left(\text{min}\left(\max_{1\leq t^{\prime}\leq\text{N}^{(t)}|t \
eq\text{I}^{\prime}}\text{RR}_{\text{C}_{k}^{(t)}}\text{C}_{\text{r}^{(t)}}^ {(t)},\max_{1\leq t^{\prime}\leq\text{N}^{(t)}|k\
eq\text{I}^{\prime}}\text{RR} _{\text{C}_{k}^{(t)}}\text{C}_{1}^{(t)}\right),1\right)} \tag{7}\]  
where \(\theta_{\text{b}}^{(t)}\) is the pair of clusters indices chosen for current agglomeration with rule (b). Rule (b) is designed to select the most exclusive link by comparing the \(\text{RR}_{\text{C}_{k}^{(t)},\text{C}_{1}^{(t)}}\) measure of a pair of clusters \(\text{C}_{k}^{(t)}\) and \(\text{C}_{1}^{(t)}\) with the other RR measures of clusters k and l. This method was hypothesized to be safer and better in the long run than choosing local optimums, by considering the multiple relations that each diagnosis cluster has with the others. Applying either rule (a) or (b) leads to a new clustering solution, having one less cluster than the previous one. The algorithm continues the agglomerations until all blocks are distributed into two clusters, the solution with one cluster being irrelevant. Thisprocess produces a set of clustering solutions, each obtained at a stage of agglomeration. The best solution \(S^{*}\), with a particular number of clusters, is determined by maximizing the global quality criterion MR, \(S^{*}=\operatorname*{argmax}_{S^{(t)}}\text{MR}\left(S^{(t)}\right)\). This solution represents the optimal partition of diagnosis blocks within a set of optimal clusters. The global constraint \(\text{RR}_{\text{intra}}\,>\,1\) is imposed on the clustering solution to obtain a solution where clusters are compact, meaning here that the co-occurrence probability is on average higher than would be expected by chance. Algorithm 1 describes the approach of the HAC-cooc algorithm with the initialization phase, the agglomeration routine phase and the selection of the optimal solution phase (Supplementary Algorithm S1 illustrates a possible implementation of algorithm 1 using matrices). ```
01.//Initialization
02.D:Total number of diagnoses to be clustered
03.N\({}^{(1)}=\text{D}\):Initial total number of clusters
04.C\({}^{(1)}_{k}\),k \(\in\{1,\dots,\text{D}\}\):Initial k\({}^{\text{th}}\) singleton cluster, with the diagnosis k
05.S\({}^{(1)}=\left\{C^{(1)}_{1},\dots,C^{(1)}_{\text{D}}\right\}\):First clustering solution
06.I = \(\varnothing\):Indices set of possible clustering solutions
07.