Leveraging Taxonomy Similarity for Next Activity Prediction in Patient Treatment

This paper proposes the TS4NAP approach, which leverages medical taxonomies (ICD-10-CM and ICD-10-PCS) and graph matching to enhance the accuracy and explainability of next-activity prediction in patient treatment planning using MIMIC-IV data.

The Gist

Imagine you are a doctor standing at a crossroads, trying to decide the next step for a patient's treatment. The patient's medical history is a massive, tangled library of thousands of books (past cases), but you only have a few minutes to find the one story that looks most like your current patient's situation.

This paper introduces a new "smart librarian" system called TS4NAP (Taxonomy Similarity for Next Activity Prediction) to help doctors make that decision.

Here is the breakdown of how it works, using simple analogies:

1. The Problem: The "Black Box" vs. The "Library"

In modern medicine, computers can predict what a patient needs next (like a surgery or a test) by looking at past data. However, many of these computer systems are "Black Boxes." They give you an answer, but they can't explain why. It's like a GPS that says "Turn left" but refuses to tell you there is a roadblock ahead. Doctors don't trust tools they can't understand.

Also, medical data is messy. Two patients might have the same disease but slightly different codes in the computer system. A standard computer might think they are totally different people, missing the connection.

2. The Solution: The "Medical Dictionary" (Taxonomies)

The authors realized that doctors use a special, organized dictionary called ICD-10.

• ICD-10-CM is the dictionary for Diagnoses (what is wrong with you).
• ICD-10-PCS is the dictionary for Procedures (what the doctor did).

Think of these dictionaries not just as lists of words, but as family trees.

• "Heart Attack" is a child of "Heart Disease."
• "Heart Disease" is a child of "Circulatory System Problems."

The TS4NAP system uses these family trees. It knows that even if two patients have slightly different codes, if those codes are "cousins" in the family tree, they are still very similar.

3. How It Works: The "Double-Check" Match

The system tries to find the best match for a current patient by looking at two things at once:

A. The Diagnosis List (The "Who they are" check)
Imagine you are looking for a twin. You don't just look at their face; you look at their whole family. The system looks at the patient's list of diagnoses. It uses a math trick called Graph Matching (think of it as a high-speed matchmaking service) to pair up the current patient's diagnoses with past patients' diagnoses.

• Analogy: If Patient A has "Broken Leg" and Patient B has "Broken Femur," a normal computer might say "No match." TS4NAP says, "Wait, those are the same thing in the family tree! They are a 90% match."

B. The Procedure History (The "What they did" check)
The system also looks at the order of past treatments. Did the patient get an X-ray before the surgery?

• Analogy: It's like matching two recipes. Even if the ingredients are slightly different, if the steps are similar, the dishes will taste similar.

4. The Magic Trick: "Weighted Similarity"

The system doesn't just count matches; it weighs them.

• If a diagnosis is very specific (like "Broken big toe"), it counts for a lot.
• If a diagnosis is very general (like "Pain"), it counts for less.
• It also checks the order. If the surgery happened before the X-ray in the past, but after in the current case, the system gives it a lower score, because the order matters.

5. The Result: A "Top 5" Recommendation

Instead of giving one single answer, the system looks at the top 5 most similar past patients and says:

"Based on these 5 people who were very similar to your patient, here are the 3 most likely next steps they took."

Crucially, it can explain its answer: "We suggest a CT scan because 4 out of the 5 most similar patients had one right after their diagnosis."

6. What the Study Found

The researchers tested this on real hospital data from Boston (MIMIC-IV).

• The Good News: The system worked much better than the "Black Box" versions, especially for complex cases with many different treatments. It was like having a librarian who actually knows the books, rather than just a robot that counts words.
• The Catch: For very simple cases (where there are only a few types of treatments), the fancy system didn't add much value. It's like using a super-computer to solve a Sudoku puzzle; sometimes a simple pencil is enough.

Summary

TS4NAP is a tool that helps doctors predict the next step in a patient's treatment by finding "medical twins" in the past. It uses the official medical family trees (ICD codes) to understand that different words can mean similar things.

• Why it matters: It makes predictions accurate (by understanding medical nuances) and explainable (by showing the doctor which past patients it compared against).
• The Metaphor: It turns a chaotic pile of medical records into a well-organized library where the librarian knows exactly which book to pull off the shelf to help you solve your problem today.

Technical Summary

1. Problem Statement

The paper addresses the challenge of Next Activity Prediction (NAP) in clinical settings, a core task within Predictive Process Monitoring (PPM). While NAP can assist physicians in treatment planning, resource allocation, and capacity management, existing approaches face significant hurdles in the medical domain:

• High Variability & Knowledge Intensity: Patient pathways are highly heterogeneous and rely on complex medical knowledge that generic models often fail to capture.
• Data Scarcity & Quality: Medical data is often sparse, unstructured, or noisy.
• The "Black Box" Problem: State-of-the-art deep learning models (e.g., LSTMs, Transformers) offer high accuracy but lack explainability. Clinicians are reluctant to trust predictions they cannot understand or trace back to specific reasoning.
• Limitations of Exact Matching: Traditional similarity-based methods (Case-Based Reasoning) often rely on exact code matching. In medicine, where codes are hierarchical (e.g., ICD-10), two different codes might represent clinically similar conditions, but exact matching fails to recognize this semantic relationship.

The authors propose a solution that bridges the gap between interpretability and accuracy by leveraging the semantic structure of medical taxonomies.

2. Methodology: TS4NAP

The authors propose TS4NAP (Taxonomy Similarity for Next Activity Prediction), a white-box, instance-based learning approach. Instead of training a black-box model, TS4NAP retrieves the most similar historical patient cases (traces) to the current partial trace and predicts the next step based on those cases.

The core innovation lies in how "similarity" is calculated using Medical Taxonomies (ICD-10-CM for diagnoses and ICD-10-PCS for procedures).

A. Semantic Similarity via Information Content (IC)

The approach uses the Sánchez similarity measure, which relies on Information Content (IC).

• Concept: Specific concepts (e.g., "Cardiac Surgery") have higher IC than general concepts (e.g., "Surgery").
• Calculation: The similarity between two codes $c_1$ and $c_2$ is determined by the IC of their Least Common Subsumer (LCS) (the most specific ancestor they share in the taxonomy) relative to the total IC of both concepts.
• Formula:
  $$sim_{Sánchez}(c_1, c_2) = \frac{2 \cdot IC(LCS(c_1, c_2))}{IC(c_1) + IC(c_2)}$$
  This allows the system to recognize that "Myocardial Infarction" and "Acute Myocardial Infarction" are highly similar, even if the codes differ.

B. Bipartite Graph Matching

To handle variability in the sequence of events (control flow) and lists of diagnoses, TS4NAP transforms traces into Bipartite Graphs.

• Nodes: Events from Trace A and Events from Trace B.
• Edges: Connect every event in Trace A to every event in Trace B.
• Edge Weights: A composite weight is assigned to each edge combining:
  1. Taxonomic Similarity: The Sánchez similarity between the codes.
  2. Order Penalty: A weight based on the positional difference ($|pos(u) - pos(v)|$) to penalize events that appear in very different orders.
• Optimization: The Hungarian Algorithm (or Kuhn-Munkres) is used to find the Maximum Weight Matching. This identifies the optimal alignment between two traces, maximizing the total semantic similarity while respecting the sequence order.

C. Aggregation and Prediction

The final similarity between a query trace and a historical trace is a weighted sum of:

1. Diagnosis Similarity ($sim_{list}$): Calculated on the list of patient diagnoses (ICD-10-CM).
2. Control-Flow Similarity ($sim_{cf}$): Calculated on the sequence of procedures (ICD-10-PCS).

The weights ($\alpha_1, \alpha_2$) are dynamically adjusted based on trace length. The $N$ most similar historical traces are retrieved, and their immediate next activities are aggregated to form a ranked prediction list.

3. Experimental Setup

• Dataset: MIMIC-IV, a large-scale critical care database from a US hospital.
• Data Construction: 36 distinct event logs were created, one for each primary diagnosis category (e.g., Acute Myocardial Infarction, Sepsis) containing at least 500 patient traces.
• Preprocessing:
  • Diagnoses mapped to ICD-10-CM.
  • Procedures mapped to ICD-10-PCS.
  • Traces filtered to include only patients with at least one procedure.
• Evaluation Metric: Average Similarity. Instead of strict accuracy (which penalizes clinically similar but non-identical codes), the metric measures the semantic similarity between the predicted next activity and the actual next activity using the Sánchez measure.
• Baselines:
  • TS4NAP$_T$: The proposed method using taxonomic similarity.
  • TS4NAP$_B$: A baseline using Boolean similarity (1 if codes match exactly, 0 otherwise), effectively ignoring taxonomy.
• Validation: Leave-One-Out Cross-Validation (LOO-CV) across all prefixes of every trace.

4. Key Results

The study validates two hypotheses: (H1) Taxonomic knowledge improves prediction, and (H2) The improvement varies by diagnosis complexity.

• Overall Performance: TS4NAP$_T$ significantly outperformed the baseline TS4NAP$_B$ in 34 out of 36 event logs.
  • Average Similarity: The overall average similarity score for TS4NAP$_T$ was 74%, compared to lower scores for the baseline.
  • Peak Performance: The highest score reached 97% (for Osteoarthritis of the knee, M17).
  • Statistical Significance: The improvements were statistically significant ($p < 0.05$) for the vast majority of cases.
• Impact of Complexity:
  • The benefit of using taxonomies was positively correlated with the number of unique events and trace variants in the dataset.
  • In complex scenarios with high variability, the semantic matching of TS4NAP$_T$ mitigated data sparsity issues that plagued the exact-matching baseline.
  • In simple, highly standardized scenarios (few unique events), the improvement was marginal, suggesting the computational overhead of taxonomy integration is most justified in complex cases.
• Prefix Length: TS4NAP$_T$ showed consistent gains for short to medium prefixes (length 1–9). Gains diminished for very long prefixes due to data sparsity, a common issue in process mining.

5. Key Contributions

1. Novel Approach (TS4NAP): A deterministic, explainable NAP framework that integrates medical taxonomies (ICD-10-CM/PCS) via semantic similarity and bipartite graph matching.
2. Explainability: Unlike deep learning models, TS4NAP provides trace-level explanations. The prediction is derived from specific, similar past patients, allowing clinicians to see why a recommendation was made (e.g., "This patient was predicted to undergo X because they are similar to Patient Y who had X").
3. Empirical Validation: Comprehensive evaluation on 36 real-world medical event logs from MIMIC-IV, demonstrating that domain knowledge significantly boosts performance in high-variability clinical settings.
4. Insight on Applicability: The study identifies that taxonomy-based methods are most effective in complex, heterogeneous environments, providing a guideline for when to deploy such computationally intensive methods.

6. Significance and Future Work

• Clinical Impact: The approach supports Clinical Decision Support Systems (CDSS) by offering transparent, medically grounded recommendations. It aids in short-term capacity planning (beds, staff, equipment) by predicting likely next steps.
• White-Box Advantage: It addresses the "black box" critique of AI in healthcare, offering a method that aligns with the need for accountability and traceability in medical decision-making.
• Future Directions:
  • Efficiency: Optimizing the retrieval mechanism (currently $O(n^4)$ due to matching) for real-time use.
  • Advanced Alignment: Replacing the simple order penalty with more sophisticated sequence alignment algorithms (e.g., Smith-Waterman).
  • Hybrid Models: Integrating deep learning (e.g., LSTMs) where the loss function is regularized by taxonomic knowledge, combining the predictive power of DL with the interpretability of TS4NAP.
  • Data Expansion: Incorporating patient attributes (age, gender) and timestamps to further refine similarity calculations.

In conclusion, the paper demonstrates that leveraging the structured knowledge within medical taxonomies via graph matching is a powerful, interpretable strategy for predicting patient treatment paths, particularly in complex and variable clinical scenarios.