Objective-To semi-automatically induce semantic categories of eligibility criteria from text and to automatically classify eligibility criteria based on their semantic similarity. Design-The UMLS semantic types and a set of previously developed semantic preference rules were utilized to create an unambiguous semantic feature representation to induce eligibility criteria categories through hierarchical clustering and to train supervised classifiers. Measurements-We induced 27 categories and measured the prevalence of the categories in 27,278 eligibility criteria from 1,578 clinical trials and compared the classification performance (i.e., precision, recall, and F1-score) between the UMLS-based feature representation and the "bag of words" feature representation among five common classifiers in Weka, including J48, Bayesian Network, Naïve Bayesian, Nearest Neighbor, and Instance-based Learning Classifier. Results-The UMLS semantic feature representation outperforms the "bag of words" feature representation in 89% of the criteria categories. Using the semantically induced categories, machine-learning classifiers required only 2,000 instances to stabilize classification performance. The J48 classifier yielded the best F1-score and the Bayesian Network classifier achieved the best learning efficiency. The UMLS is an effective knowledge source and can enable an efficient feature representation for semi-automated semantic category induction and automatic categorization for clinical research eligibility criteria and possibly other clinical text. Clinical Research Eligibility Criteria; Classification; Hierarchical Clustering; Knowledge Representation; Unified Medical Language System (UMLS); Machine Learning; Feature Representation Eligibility criteria specify the characteristics that a human volunteer must or must not possess to participate in a clinical study or to be treated according to a standard clinical care © 2011 Elsevier Inc. All rights reserved. Corresponding Author: Chunhua Weng, PhD, MS, Department of Biomedical Informatics, Columbia University, 622 W 168 Street, VC-5, New York, NY 10032, Tel: 212-305-3317, Fax: 212-305-3302, cw2384@columbia.edu. Publisher's Disclaimer: This is a PDF file of an unedited manuscript that has been accepted for publication. As a service to our customers we are providing this early version of the manuscript. The manuscript will undergo copyediting, typesetting, and review of the resulting proof before it is published in its final citable form. Please note that during the production process errors may be discovered which could affect the content, and all legal disclaimers that apply to the journal pertain.  NIH Public Access Figure 1 illustrates our machine-learning framework for integrated category induction and criteria classification, both sharing the same feature representation by annotating each eligibility criterion with a UMLS-based semantic lexicon 18 . Instead of using manually defined categories, we semi-automatically generated eligibility categories using a hierarchical clustering algorithm to augment humans for category induction. Then a supervised machine-learning classifier achieves automatic classification. More design details are provided below. Each criterion was first parsed by a previously published and freely available semantic annotator 18 to identify the UMLS-recognizable terms, many of which were associated with multiple semantic types and hence resulted in ambiguity. We removed such ambiguities by using a set of predefined semantic preference rules 19 to select specific types over general types 18 . For example, the UMLS concept pericardial was associated with two UMLS semantic types, Body Location or Region and Spatial Concept. In the UMLS Semantic Network, Body Location or Region was one of the sub-types of Spatial Concept. Hence, the semantic type Body Location or Region was more specific than Spatial Concept. Therefore, for the UMLS concept pericardial, the type Body Location or Region was retained as the preferred semantic type. We also created three new types to label terms that were not covered in the UMLS but frequently occurred in clinical research eligibility criteria. We defined the Numeral type for numbers (e.g. 18, 60, two). We also defined the Symbol type for comparison connector (e.g. +, >=, @) and the Unit type for measurement units (e.g. mm3, ph, kg). The example criterion "Prior adjuvant therapy for metastatic disease allowed" would be annotated as "prior /Temporal Concept | adjuvant therapy/Therapeutic or Preventive Procedure | for/ | metastatic disease / Neoplastic Process | allowed /Social Behavior", in which each UMLS concept (underlined) was separated from its corresponding UMLS semantic type (italic) by a slash. Figure 2 shows the process of transforming eligibility criteria into a semantic feature representation matrix. A criterion was denoted as S and it was mapped into a semantic type vector T (Figure 2 -A). The value of a semantic feature in the vector T was weighted by its frequency of occurrence, , where i = {1,2,3⋯k}, F j being the frequency of the semantic type j and k being the number of all the different semantic types in sentence S. For example, the above sentence contained 4 different UMLS semantic types, each occurring  NIH-PA Author Manuscript NIH-PA Author Manuscript once; therefore, the weighted frequency of each semantic type was 0.25. All the criteria instances were parsed and transformed into a feature representation matrix to support classifier learning, where each row was a criterion and each column was a UMLS semantic type, as shown in Figure 2 -B. After the semantic annotator transformed the criteria into a UMLS-based semantic feature matrix, the hierarchical agglomerative clustering algorithm (HAC) algorithm 20 was applied on the semantic feature matrix to induce the semantic categories of criteria. HAC used a bottom-up approach that initially created a cluster for each criterion and then progressively agglomerated clusters based on their semantic similarity, one pair each time, until all criteria were joined into a giant cluster. To assess the similarity of eligibility criteria, the Pearson correlation coefficient 21 was applied to quantify the relationship between the semantic representations of two criteria with the value ranging between −1 and 1. For example, if criterion A and B contained completely different sets of UMLS semantic type features, their correlation value would be −1.0 because they were perfectly divergent. If the two sets were not perfectly divergent, but still diverged, the correlation would remain negative, but would be greater than −1.0. In contrast, if criteria A and B were convergent, then their correlation would be 1.0. If there was no relationship, their correlation would be 0. A Pearson correlation coefficient was initially computed for every possible criterion comparison to create a table of correlation values between every possible pair of the criteria being clustered. Then the criterion pair that had the highest correlation value was first selected to merge into one cluster to form a new "pseudo-criterion". The new pseudo-criterion would contain the same number of feature representation, but each feature would now be the arithmetic mean of the two original feature sets. The two original criteria that were merged would be removed from the table of correlation values, and new correlations would be found between the new pseudo-criterion and all of the remaining criteria. The next highest remaining correlation value in the table would be identified and that pair of criteria would be joined for form a new pseudo-criterion. This process continued until all that remains was a single pseudo-criterion containing the arithmetic mean of all the original criteria at each feature. When clustering an original criterion with a previously formed pseudo-criterion, the newly formed pseudo-criterion must be an arithmetic mean of all the criteria' features that it contains, not a simple average between the pseudo-criterion's and the original criterion's features. By retracing the order in which the criteria were progressively joined into clusters and by knowing the correlation value of each step, we identified the criteria related to each other closely and the criteria related only distantly by setting a threshold from the [−1,1] value range, where any criteria paired with correlations greater than that threshold were considered a cluster, and any criteria or clusters with correlations less than that threshold were not. In this way, all criteria had a correlation greater than the threshold were considered as a cluster. A manual review was performed to merge and label these clusters to form semantic categories based on their semantic similarity 18 . For example, one cluster contained the criterion "SGOT <=2 times ULN", while the other cluster contained the criterion "Neutrophil count larger than 1000 per mm3". Both criteria had similar scores of the semantic similarity between instances in each cluster, which were typical laboratory test results; therefore, these two clusters were semantically related. In addition, the syntax of the instances in the two clusters was similar, both including a clinical object, a comparison symbol, numerical values, and measurement units. A manual review concluded that the two clusters were semantically similar and could be merged into one category: Diagnostic or Lab Results. Meaningful category names were created manually and supplied to the  NIH-PA Author Manuscript NIH-PA Author Manuscript classification module. We purposely reused the labels of the UMLS semantic types to name criteria categories since they are familiar to many informatics researchers. Two human raters independently labeled a set of criteria using the developed semantic categories and reached consensus on the categorization results. These instances were also parsed by the semantic annotator and transformed into semantic features. The manual categorization results and their semantic features were used to train five very commonly used supervised classifiers in the open-source Weka package 12 , including J48 13 , Bayesian Network 14 , Naïve Bayesian 15 , the nearest-neighbor (NNge) 16 , and the instance-based learning classifier IB1 17 . We compared the classification performance using the UMLSbased semantic feature representation and the standard "bag of words" representation respectively among all the five classifiers. Results ClinicalTrials.gov is a public registry of all clinical trials and their eligibility criteria 2 . From this web site, we randomly extracted 5,000 sentences. Excluding 179 non-criterion sentences and using the remaining 4,821 criteria sentences, the hierarchical clustering module initially recommended 41 clusters whose pair-wise similarity was above the threshold 0.75. We manually induced 27 eligibility criteria categories, whose organizational hierarchy includes 6 topic groups: Demographics (e.g., age or gender), Health Status (e.g., disease or organ status), Treatment or Health Care (e.g., therapy or medication), Diagnostic or Lab Tests, Ethical Consideration (e.g., willing to consent), and Lifestyle Choice (e.g. diet or exercise). More category information can be found in our previous publication 11 . Two independent human raters manually labeled 2,718 criteria sentences. The Cohen's Kappa 22 was 0.82, which indicated an excellent inter-rater agreement.  To assess the comprehensiveness of the semi-automatically induced eligibility criteria categories, we randomly selected 1,578 clinical trials and extracted 27,278 eligibility criteria to investigate the prevalence and frequency of each category in these criteria, as shown in  A total of 3,403 randomly selected eligibility criteria were used to train the classifiers. We conducted a 10-fold cross-validation to compare the classification performance among 5  NIH-PA Author Manuscript NIH-PA Author Manuscript commonly used machine-learning classifiers, which were J48, Bayesian Network, Naïve Bayesian, the nearest-neighbor (NNge), and the instance-based learning classifier IB1, each using the "bag of words" representation (baseline) and the UMLS semantic type representation. Our comparison was from the following perspectives: (1) classification accuracy measured by precision, recall, and F1-score (Table 3) ; (2) (4) classifier learning efficiency ( Figure 5 ). Recall, precision and F1-score are defined as follows: (1) (2) As shown in Table 3 , the UMLS semantic feature representation consistently outperformed the "bag of words" feature representation by achieving higher precision, recall and F1-score, with performance improvement ranging from 13.3% to 19.0% in all of the 5 classifiers. The Naïve Bayes classifier increased the F1-score by 19% by changing from the "bag of words" representation to the UMLS semantic type representation. Overall, the J48 classifier performed the best among the 5 classifiers, with a precision of 87.0%, recall at 87.2% and F1-score of 86.9% when using the UMLS semantic type representation. Figure 3 contrasts the average F1-scores for the 27 semantic categories using the UMLS semantic type representation and the "bag of words" representation respectively. In 24 of the 27 semantic categories (89%), the UMLS semantic type representation outperformed the "bag of words" representation by using semantic knowledge that was unavailable in the "bag of words" feature representation to identify the semantic similarity between seemingly different terms. For example, criteria "Sex: Male" and "Inclusion: Female" did not share any learning feature in the "bag of words" representation because of the term variations. However, the UMLS semantic representations for both criteria shared the same UMLS semantic type Organism Attribute. Therefore, the UMLS semantic type representation was able to detect semantic similarity that was not captured in the "bag of words" representation. The P-value of the difference between the two feature representations for all 27 categories measured by a t-test 23 was 0.00334 (P<0.05), indicating the statistical significance of the differences. Therefore, the performance of the UMLS semantic representation was significantly better than that of the "bag of words" representation. Three rare categories, Life expectancy, Consent, and Special patient characteristics, did not show the advantages of the UMLS semantic type representation because the criteria belonging to those classes often contained salient keywords that were more effective than their semantic types for classification. For example, 75.53% of the criteria in the category Consent contained phrase "informed consent". When using the "bag of words" representation, the classifier could easily tell whether a criterion belonged to the Consent category simply by looking up the keywords "informed" and "consent" in the feature set. In contrast, when using the semantic type representation, the term "informed consent" was  NIH-PA Author Manuscript NIH-PA Author Manuscript mapped to the UMLS semantic type Regulation or Law which also included terms in criteria that were not related to consent, such as "drug regulations" or "health policy". Using this semantic feature alone was not very sufficient to tell whether a criterion belonged to the Consent category. In this case, the use of the "bag of words" representation was more accurate than using the semantic type representation. Figure 4 shows that the UMLS semantic type representation consistently required significantly less time than the "bag of words" representation across the 5 classifiers. The learning dimension of "bag of words" representation was much bigger than that of the semantic type representation. This might be explained by the fact that we obtained 4,413 distinct "bag of words" features but only 135 semantic-type features for the 3,403 training criteria. We also found that BayesNet classifier and NaïveBayes classifier were robust to resist the fast growth in the learning dimension and retained high efficiency, while efficiency was significantly impaired in IB1, J48 and NNge as the learning dimension expanded, as shown in Figure 4 . We also carried out an experiment to measure the learning efficiency of the best performing classifier of the five, J48, by dividing the 3,403 training criteria into groups, each containing only 3 criteria. The training process was divided into 1,134 steps, each step incrementally increasing the size of the training data set by 3. Therefore, the step-wise training sizes are 3, 6, 9,…3*K instances, where K is the sequential number of the step. The classification accuracy for each step was documented and plotted as a learning curve that grows with the size of the training data set, as shown in Figure 5 . The learning speed increased fastest for the first 500 training instances. After that point, the learning performance increased relatively slowly. Finally, after about 2,000 training instances, the learning curve stabilized, indicating that a 3,403-sentence training set was sufficient to develop a stable model for classifying eligibility criteria. At the point of this study, there was no standard and automatic way to categorize and organize clinical research eligibility criteria. We applied the learned classifier (J48) to organize the eligibility criteria on Clinicaltrials.gov. Figure 6 shows the eligibility criteria section of a clinical trial study on Clinicaltrials.gov, which is a bullet list. Figure 7 show the results of dynamic eligibility criteria categorization 24 . Using our J48 decision tree classifier, we can assign each criterion to its corresponding semantic category and organize the criteria section into a hierarchical tree, which could facilitate fast content browsing 25 and faceted search 26 . Clustering is an unsupervised learning technique that does not need a human labeled training set but rather identifies the similarities between instances, whereas classification is a supervised machine learning approach that needs to be trained using manually labeled examples 27 . In this paper, we present an effective approach to dynamic categorization of clinical research eligibility criteria by integrating hierarchical clustering and classification algorithms through the use of a shared semantic feature representation based on the UMLS semantic types. Our method demonstrates the value of using the UMLS semantic types for feature representation. To improve machine learning efficiency, various approaches have been developed to automate training data generation [28] [29] [30] . Our semantic annotator automatically generates features based on the UMLS semantic types and significantly reduces the learning dimension compared to the traditional "bag of words" method. Prior studies manually defined categories for clinical eligibility criteria 4-5 . Our method reduces the human effort required for category development and contributes a set of fine-grained Our method for dynamic categorization of criteria sentences is inspired by and extends a notable related work for dynamic categorization of documents, which is the DynaCat system developed by Pratt 25 . DynaCat utilized the UMLS for knowledge-based query terms labeling and PubMed document classification. All query terms were automatically encoded with MeSH terms, but document categories and classification rules were manually specified for document categorization. We extended DynaCat by using the hierarchical clustering tools to automatically induce semantic categories for the objects to be categorized and by using a machine-learning approach to train the classifier, which was an improvement over manually defined rule-based classifiers. By using MeSH terms, DynaCat achieved standards-based query term annotation but did not reduce the feature space. As an extension, we used the UMLS semantic types to annotate eligibility criteria concepts and significantly reduced the feature dimension for machine learning-based classification. Furthermore, DynaCat performed categorization at the document level; in contrast, our method allows categorization at the sentence level. We also compared our We can improve our current methodology in several ways in the future. We identified two open research questions for classifying clinical sentences. One is to develop better machine learning algorithms for imbalanced training data. As we demonstrated in section 3.2, different categories achieved varying degrees of accuracy, which was partially caused by the different prevalence and incidence of these categories, as indicated in Table 2 . Learning from imbalanced data sets where the number of examples of one (majority) class is much higher than others, machine-learning algorithms tend to produce better predictive accuracy over the majority classes but poorer predictive accuracy over the minority classes. This is an open research challenge for the machine learning community. Over-sampling algorithms 36 can be used to improve the performance for minority classes. Another needed improvement is to develop multi-label classifier for eligibility criteria. Although the majority of eligibility criteria contain only one topic, there are still about 8% of eligibility queries containing multiple topics. For example, the criterion "pregnant women" contains two topics pregnancy and gender. Another example is "male and female with age between 18 and 65." Multiple topics may also be present less explicitly in some examples; for instance, "positive pregnancy lab tests" could be categorized as both Lab Test Results and Pregnancy. However, our classifier only assigns one category to these eligibility criteria. The categories resulting from hierarchical clustering are not completely mutually exclusive and can contain some hidden relations (e.g., a set of lab tests for measuring pregnancy), which also could have affected the classification accuracy. These research questions are worth more studies in the future. In this paper, we present a novel method that combines an unsupervised clustering algorithm with a supervised classification algorithm to develop a semantic classifier, which can be used to categorize clinical research eligibility criteria automatically. We also demonstrate the value of semantic knowledge such as the UMLS in improving the learning efficiency of semantic classifiers for clinical sentences such as clinical research eligibility criteria. Using the UMLS semantic types is far more effective and efficient than using words for feature representation when classifying clinical sentences, primarily because UMLS semantic knowledge matches the semantics in clinical text well.
Previous studies investigated the eligibility criteria in clinical trial protocol and developed approaches for eligibility criteria extraction and semantic representation, and used hierarchical clustering for dynamic categorization of such criteria REF .
Dynamic categorization of clinical research eligibility criteria by hierarchical clustering
Journal of biomedical informatics
Journal of biomedical informatics
Computer Science Medicine