# 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
08.//Agolomeration Routine
09.For(t = 2,..., D - 1){
10.Consider each pair of clusters \(\left(C^{(t-1)}_{k},C^{(t-1)}_{l}\right)\), k,l \(\in\left\{1,\dots,\text{N}^{(t-1)}\right\}\)
11.Compute \(\text{RR}_{C^{(t-1)}_{k},C^{(t-1)}_{l}}\)for each pair using (1)
12.Select the best link \(\theta^{(t-1)}_{l}=\left(k^{*},l^{*}\right)\), with r = a or b using (6) or (7)
13.Merge \(C^{(t-1)}_{k^{*}}\) and \(C^{(t-1)}_{l^{*}}\):\(C^{(t)}_{\text{new}}=C^{(t-1)}_{k^{*}}\cup C^{(t-1)}_{l^{*}}\)
14.Compute the clustering solution \(S^{(t)}=\left(S^{(t-1)}\right)\left\{C^{(t-1)}_{k^{*}},C^{(t-1)}_{l^{*}}\right\} \cup C^{(t)}_{\text{new}}\)
15.Associate the visits of \(C^{(t-1)}_{k^{*}}\) and \(C^{(t-1)}_{l^{*}}\) to \(C^{(t)}_{\text{new}}\)
16.Compute \(\text{N}^{(t)}=\text{N}^{(t-1)}-1\)
17.Compute the quality indicators \(\text{RR}_{\text{intra}}\left(S^{(t)}\right)\) and \(\text{RR}_{\text{inter}}\left(S^{(t)}\right)\) using (3) and (4)
18.Compute the quality indicator \(\text{MS}\left(S^{(t)}\right)\) using (5)
19.If \(\text{RR}_{\text{intra}}\left(S^{(t)}\right)>1\){
20.I = I \(\cup\{t\}\)
21.} 22.} 23.//Selection of the optimal solution
25.S\({}^{*}=\operatorname*{argmax}_{S^{(t)}\
otin\text{I}}\text{MR}\left(S^{(t) }\right)\)
```  
**Algorithm 1** The new Hierarchical Agglomerative Clustering (HAC-cooc) algorithm pseudo-code. The complexity of Algorithm 1 is driven by the operation at lines 10, 11, 12 and 13, which each have a complexity \(O\left(\text{N}^{(t-1)}\right)\) or \(O\left(\left(\text{N}^{(t-1)}\right)^{2}\right)\) depending on whether they are optimized or not, i.e., whether the algorithm only updates proximity measures that have changed, or if it computes them for all pairs at each loop. It is also driven by the operation at line 15, which has a complexity of \(\text{O}(\text{N}_{\text{v}})\) as it changes the association between the \(\text{N}_{\text{v}}\) visits and the clusters. Therefore, considering the loop on t, the algorithm complexity is quadratic with \(\text{O}(\max(\text{D},\text{N}_{\text{v}})*\text{D})\) with the optimized form and third order with \(\text{O}\left(\max\left(\text{D}^{2},\text{N}_{\text{v}}\right)*\text{D}\right)\) otherwise. Using a non-optimized (third order) implementation with the R language (v4.0.1) and an Intel i5-4300M CPU at 2.60 GHz, the execution time was of 17 min with \(\text{D}=\ 151\) and \(\text{N}_{\text{v}}=114\ 391\). As \(\text{N}_{\text{v}}\ >\text{D}^{2}\), the complexity is driven linearly by the number of visits (\(\text{O}(\text{N}_{\text{v}}*\text{D})\)) and the optimized version does not offer a reduction in complexity. A sensibility analysis was performed on a nine-week period with \(\text{D}=\ 96\) and \(\text{N}_{\text{v}}=9317\) resulting in execution time of 2 min and 30 s, which is coherent with the complexity analysis. Keeping this configuration with \(D\) constant and considering the linear relationship with N\({}_{\rm v}\), a dataset with 1 million visits (N\({}_{\rm v}\)) would imply a run time between 3 and 5 h and one with 10 million visits (N\({}_{\rm v}\)) around 2 days, which begins to be quite long but still acceptable. However, with more visits, it would also be interesting to use more diagnoses that are more precise and thus increase D by scale factor between 1 and 10 for each increase in lexical depth of ICD10 codes.