An Efficient Parallelized Ontology Network-Based Semantic Similarity Measure for Big Biomedical Document Clustering

Meijing Li, Tianjie Chen, Keun Ho Ryu, Cheng JinComputational 2021 · DOI

TL;DR

This paper tackles the challenge of clustering massive amounts of biomedical text data by proposing a novel, parallelized semantic similarity measure based on Hadoop MapReduce. Their approach leverages the MeSH ontology to capture rich semantic relationships, overcoming the scalability limitations of traditional methods and demonstrating significant improvements in efficiency and accuracy for large datasets.

What Problem Does This Paper Address?

The explosion of biomedical literature presents a significant challenge for information discovery. While semantic analysis and clustering are powerful tools for navigating this data, existing methods for calculating semantic similarity, particularly those relying on ontologies like MeSH, become computationally prohibitive when dealing with "big data" scales (tens of thousands of documents or more). Traditional pairwise similarity calculations lead to redundant computations and slow performance, rendering them impractical for large-scale biomedical text mining tasks. The authors aim to bridge this gap by developing an efficient and scalable parallelized approach.

Methods

The core of the proposed solution lies in a parallelized semantic similarity measurement method built upon the Hadoop MapReduce framework. The process involves several key steps:

  1. Preprocessing and Feature Extraction: Documents are associated with unique PubMed IDs (PMIDs) and tagged with MeSH (Medical Subject Headings) terms. These MeSH headings, which describe the document's subject, are treated as semantic features. The data is then transformed to group documents by shared MeSH headings, creating an input format like <MeSH_heading, list(document_IDs)>.
  2. MapReduce-Based Semantic Similarity Calculation:
    • MeSH Heading Similarity: The similarity between pairs of MeSH headings is pre-calculated. The paper explores various established semantic similarity measures for this, including SP, WP, LC, Resnik, Lin, and Sch.
  3. Document Similarity: The document similarity is then computed using an Average Maximum Match (AMM) strategy, adapted for parallel processing. This strategy leverages the pre-calculated MeSH heading similarities to determine the overall similarity between documents. The MapReduce framework is used to parallelize the computation of these similarities, avoiding redundant pairwise comparisons.
  4. Document Clustering: Once the semantic document similarity matrix is generated, standard clustering algorithms (K-means, agglomerative clustering, and spectral clustering) are applied to group the documents.

The novelty lies in the parallelization of the semantic similarity calculation using MapReduce, specifically by breaking down the document similarity computation into aggregations of heading-to-document similarities.

Datasets

The authors evaluated their method using two types of datasets:

  • SL (Small and Labelled): This dataset is derived from the TREC 2005 genomics track and contains biomedical documents associated with 50 topics. For evaluation, only "definitely relevant" documents were kept, and topics with fewer than 10 documents were removed. The final SL dataset comprised 2,317 documents across 24 topics, with 100 different datasets generated by randomly selecting 3-12 topics. This dataset was used for verifying the accuracy of the proposed method.
  • LUs (Large and Unlabelled): This dataset consists of six subsets randomly extracted from PubMed, with document counts ranging from 10,000 to 60,000. These subsets cover over 20,000 different MeSH headings and were used to test the efficiency of the method on large-scale data.

Key Insights and Ideas

  • Ontology Power for Big Data: The paper demonstrates that ontology-based semantic similarity, while computationally intensive traditionally, can be effectively scaled to "big data" problems through parallelization.
  • MapReduce as an Enabler: Hadoop MapReduce is shown to be a viable framework for parallelizing complex semantic similarity calculations, overcoming the limitations of sequential processing.
  • AMM Strategy's Adaptability: The Average Maximum Match (AMM) strategy, originally designed for smaller datasets, proves adaptable and effective when parallelized for large-scale document similarity computation.
  • Information Content Measures Shine: For clustering validation, information content-based semantic measures (Resnik and Lin) consistently outperformed other measures, suggesting their robustness in capturing meaningful semantic relationships.
  • Spectral Clustering's Advantage: Among the tested clustering algorithms, spectral clustering generally yielded higher Normalized Mutual Information (NMI) scores, indicating better clustering performance.

Key Results

  • Computational Efficiency: The proposed method significantly outperforms traditional methods in terms of computation time. For the small SL dataset, the traditional method took over an hour, while the proposed method completed it in under 3 minutes using a five-computer cluster. For the large LUs-10000 dataset, traditional methods were practically unusable, whereas the proposed method remained efficient.
  • Scalability and Parallelism: Experiments with increasing cluster nodes showed a near-linear speedup, indicating high parallelism. Increasing nodes from 1 to 5 reduced elapsed time from 12.63 minutes to 2.31 minutes.
  • Clustering Accuracy (NMI): On the SL dataset, the highest NMI of 0.647 was achieved with spectral clustering and the Resnik semantic measure. The paper notes that their method achieved slightly increased NMI compared to previous work using similar data and criteria, while drastically improving efficiency.
  • MapReduce Optimization: Optimizing MapReduce job settings (e.g., increasing reduce tasks, using combiners) led to substantial reductions in computation time, particularly for the shuffle stage, which is often a bottleneck.

Limitations and Future Work

  • Limitations: The paper acknowledges that the traditional methods struggle with datasets larger than ten thousand documents. While their proposed method is efficient, the shuffle stage in MapReduce can still be a bottleneck for very large datasets, as observed in Figure 5.
  • Future Work: The authors suggest that their proposed method is not limited to biomedical documents or the MeSH ontology. It can be extended to combine semantic similarity from different feature types. Further optimization of MapReduce job settings and exploring other parallel computing frameworks could also be avenues for future research. The choice of semantic measure and clustering algorithm can be dataset-dependent, suggesting potential for adaptive selection strategies.

Summary updated

Abstract

Semantic mining is always a challenge for big biomedical text data. Ontology has been widely proved and used to extract semantic information. However, the process of ontology-based semantic similarity calculation is so complex that it cannot measure the similarity for big text data. To solve this problem, we propose a parallelized semantic similarity measurement method based on Hadoop MapReduce for big text data. At first, we preprocess and extract the semantic features from documents. Then, we calculate the document semantic similarity based on ontology network structure under MapReduce framework. Finally, based on the generated semantic document similarity, document clusters are generated via clustering algorithms. To validate the effectiveness, we use two kinds of open datasets. The experimental results show that the traditional methods can hardly work for more than ten thousand biomedical documents. The proposed method keeps efficient and accurate for big dataset and is of high parallelism and scalability.
BibTeX
@inproceedings{li2021efficient,
  author = {Meijing Li and Tianjie Chen and Keun Ho Ryu and Cheng Jin},
  title = {{An Efficient Parallelized Ontology Network-Based Semantic Similarity Measure for Big Biomedical Document Clustering}},
  booktitle = {Computational},
  year = {2021},
  doi = {10.1155/2021/7937573},
}
Figure