In biomedical applications where the size and complexity of SNOMED CT are challenging, using a more compact subset that can act as a reasonable substitute is often preferred (e.g., in problem lists, using the CORE problem list subset of SNOMED CT, covering 95% of usage in less than 1% its size). Ontology modularization is the area of research that studies how to extract such subsets, also called modules or segments. In a special class of use cases including ontology-based quality assurance, scaling experiments for real-time performance, and developing scalable testbeds for software tools, it is essential that modules are representative of SNOMED CT's sub-hierarchies in terms of concept distribution, therefore preserving the original shape of SNOMED CT. How to extract such balanced modules remains unclear, as most previous work on ontology modularization has focused on the opposite problem: on extracting a representative module for a specific domain. In this study, we investigate to what extent extracting balanced modules that preserve the original shape of SNOMED CT is possible by presenting and evaluating an iterative algorithm.
The size and complexity of SNOMED CT1 constitute a problem
in many biomedical applications (
How to extract such subsets is studied by the area of research of
ontology modularization (Stuckenschmi
A signature is an initial set of concepts (called seeds)
that bootstraps the modularization process, on which many
ontology modularization techniques rely, including graph-traversal
(
To the knowledge of the authors, little research on ontology modularization has focused on extracting balanced modules for such applications, where keeping the original shape of a large ontology such as SNOMED CT regarding sub-hierarchies is a requirement.
In this paper, we study the concept distribution of SNOMED CT’s sub-hierarchies and we propose an evaluate an iterative algorithm for extracting balanced modules. Our main goal is to investigate to what extent it is possible to obtain modules that preserve the original shape of SNOMED CT in order to be used in our identified class of use cases.
As a useful way of visualizing concept distribution and for comparative purposes (see Section 4), the same information is displayed in form of a treemap in Figure 1. The treemap represents SNOMED CT’s hierarchical information as a set of rectangles, where the area of each rectangle is proportional to the number of concepts in the sub-hierarchy.
As remarke
As input, we used the OWL-EL version of SNOMED CT obtained using the Perl script included in the distribution as input (SCT ). For our purposes, presented in the introduction, we define a balanced SNOMED CT module (M ) as a minimal collection of classes from SCT that conform to the following requirements: (a) All classes in M are hierarchically connected to SNOMED CT’s root concept in the same way as in SCT . (b) All classes in M share the same axiomatical class definition as in SCT . (c) Sub-hierarchies in M are distributed (approximately) in the same proportion as in SCT . In practical terms, when visualized using a treemap, M should look similar to the treemap of SNOMED CT shown in Figure 1. (d) Our model is restricted to classes. SNOMED CT metadata concepts are not subject to modularization. 3.2
To create our module M , we followed a similar approach to
10 7 8 13 14
17 19
20 6 11 12 16 22 24 25
B The strategy to build a module using seeds presented in the previous section guarantees requirements (a) and (b) from our definition of M , but does not guarantee requirement (c), i.e., that sub-hierarchies in M will be distributed (approximately) in the same proportion as in SCT . The reason is that there is no control over classes from other sub-hierarchies that are added in the process when following the right-hand expressions of the seeds.
Therefore, in order not to conflict with requirements (a) and (b) when creating M , the only possibility is to carefully select the initial signature that bootstraps the modularization algorithm. For that purpose, we investigated an iterative algorithm that dynamically adjusts the distribution of classes used as seeds in the initial signature. Before presenting the algorithm, we introduce the following notation:
As introduced before, SCT represents the OWL EL version of SNOMED CT used as input. Sub-hierarchies are termed SHk. M represents, the output module, whose sub-hierarchy distribution (Table 1) should match SCT ’s as much as possible.
SIGN , is the input signature, consisting of classes from SCT , that is used to boostrap the modularization process described in Subsection 3.2.
Error(SHk) = Size(MSHk ) Size(SCTSHk ) indicates the error on a per sub-hierarchy basis. Errors are calculated in percentage terms (see distribution in Table 1).
RSS = 118 P1k8=1 Error(SHk)2, where RSS represents the residual sum of squares. Convergence of the algorithm is defined when RSS < 1.
The algorithm, at each iteration i is the following: 1. A random signature SIGNi consisting of 2000 classes from SCT is selected, following the same class sub-hierarchy distribution as SCT , and ensuring at all sub-hierarchies in the signature contains at least one class. 2. A module Mi is computed following the principles described in
Subsection 3.2. Its sub-hierarchy distribution is calculated. 3. Convergence is checked. If RSS >= 1, Steps 1 to 3 are repeated after adjusting the scaling factor for the sub-hierarchy distribution of the signatures in the next iteration i + 1: = with f(SCTSHk ) f (SIGNi+1SHk ) f (SIGNiSHk ) f(MiSHk ) f (MiSHk ) being the relative frequency of sub-hierarchy SHk measured in the resulting module in iteration i, Mi. 4
In our experiments, the algorithm converged after 7 iterations, extracting a module M with 10 834 classes. Figure 4 (Page 4) shows the error after each iteration for sub-hierarchies with more than 1% error, as well as the residual sum of squares.
As can be seen in the table below the graph, the sub-hierarchies Clinical Finding, Procedure, and Organism were under-represented in M , while Body Structure and Substance were over-represented. The same results can be confirmed graphically in the treemaps shown in Figure 5, at iterations 1, 3, and 7. (a) Module Shape - Iteration 1 (b) Module Shape - Iteration 3 (c) Module Shape - Iteration 7 (convergence) (d) Full SNOMED CT Shape (target)
Our results suggest that it is difficult for ontology modules to meet all of our modularization criteria without relaxing the constraints of how concepts in the modules are distributed by sub-hierarchies, because modularization criteria are conflicting. In our experiments, all obtained modules over-represented or under-represented some of SNOMED CT’s sub-hierarchies in different degrees. These results were partly expected, due to the nature of the modularization approach that uncontrollably adds class definitions to preserve SNOMED CT’s hierarchy and class definitions.
The error figures that we obtained after convergence, however, never reached 8% for any sub-hierarchy and all our modules contained a fair representation of all of them. Furthermore, convergence was reached after only 7 iterations. Such modules might be sufficient in many of the use cases that motivated their creation, i.e., extracting modules that show an (approximately) concept distribution to the one shown in SNOMED CT.
In this study, we have studied SNOMED CT sub-hierarchies and proposed and evaluated an iterative algorithm for extracting compact modules that preserve the shape of SNOMED CT that we termed balanced modules. Extracting such modules has generally been neglected by work on ontology modularization, even though there are many use cases where balanced modules constitute an extremely valuable tool, such as in ontology-based quality assurance, scaling experiments for real-time performance, or developing scalable testbeds for software tools. Our proposed algorithm and our resulting modules show that graph-traversal ontology modularization techniques can effectively be used to create balanced modules, if the concept distribution of the input signature is dynamically and iteratively adjusted.
It is important to note that our algorithm and experiments are still at an initial stage and some aspects need to be further explored and more carefully evaluated. As future work, we plan to further (a) analyze how to select a minimal signature, (b) study how signature size influences the final size of the modules, and (c) improve the randomization process of the signature selection, e.g., by stratifying the randomization by node depth.
Our current results, however, show that SNOMED CT can indeed be squeezed without losing its shape, provided that we accept a moderate (up to 8%) under- and over-representation of some of its hierarchies.
The authors acknowledge ICBO reviewers for their elaborate feedback and suggestions.