Introduction
In the modern business landscape, data is rarely flat. User profiles, product catalogs, and service plans are increasingly represented as hierarchical trees. For instance, a telecom account typically branches into various services, which further divide into specific plans and granular usage items like voice or data. Traditional similarity measures, such as Tree Edit Distance (TED), often struggle with these structures because they rely on strict one-to-one node mapping. This paper proposes a comprehensive similarity measure designed to handle the conceptual overlaps and complex mappings inherent in business data.
The Challenge of Concept Inclusion
Standard tree-matching algorithms assume that a node in one tree corresponds to exactly one node in another. However, business concepts often exhibit "concept inclusion" or one-to-many relationships. A high-level "Fusion" plan in one system might encompass both "Landline" and "Broadband" services found in another. Traditional methods fail to capture these relationships, leading to inaccurate similarity scores that undermine the performance of recommender systems.
The Comprehensive Similarity Model
The authors introduce a model that evaluates similarity across two primary dimensions: conceptual meaning and numerical values.
1. Conceptual Similarity
This stage measures the alignment of node meanings and overall structure. By incorporating a domain ontology—a set of expert-defined rules—the algorithm allows for "less constrained" mappings. If the ontology indicates that Concept A includes Concepts B and C, the model can map a single node in the first tree to multiple nodes in the second. For standard one-to-one scenarios, the model employs maximum weighted bipartite matching to optimize sub-tree alignment.
2. Value Similarity
Beyond conceptual alignment, the model assesses the similarity of actual data points, such as plan costs or data consumption. To ensure a fair comparison in one-to-many scenarios, the values of the "many" nodes are aggregated (e.g., summed) before being compared to the "one" node. The final similarity score is a weighted sum of these two components, allowing for adjustable prioritization between conceptual "spirit" and numerical "letter."
Illustrative Application
To demonstrate the model's utility, the authors utilize a synthetic telecom dataset representing different user account structures.
As shown in Figure 1, Account 1 ($T_1$) contains a "Fusion" plan (node 5), while Account 2 ($T_2$) separates services into "Broadband" (node 5) and "Lad" (nodes 3 and 4). A domain ontology allows the system to recognize that the single "Fusion" node in $T_1$ conceptually maps to the multiple service nodes in $T_2$, facilitating a more accurate comparison than traditional 1-to-1 matching.
Empirical Evaluation
The model was rigorously tested using the HetRec 2011 MovieLens dataset, where movies were represented as trees containing genres, directors, and filming locations. The proposed measure achieved a Mean Absolute Error (MAE) of 0.703.
When compared to traditional Collaborative Filtering (CF), the tree-based approach demonstrated significant advantages in robustness:
- Cold Start Problem: While CF achieved a similar MAE (0.71), it failed to provide recommendations for 523 test cases due to insufficient ratings. The tree-based similarity measure successfully generated recommendations for all cases.
- Sparse Data Performance: For items with fewer than five ratings, CF's error increased to 0.902. In contrast, the proposed measure maintained a stable MAE of 0.71, proving its effectiveness in data-sparse environments.
Conclusion
The proposed comprehensive similarity measure offers a sophisticated solution for comparing complex business data. By integrating domain ontologies and allowing for one-to-many mappings, it overcomes the limitations of traditional tree-matching algorithms. While the model currently relies on expert-defined ontologies and weights, future work aims to automate these processes and test the system in large-scale industrial environments.
Summary updated