A Similarity Measure on Tree Structured Business Data

Dianshuang Wu, Guangquan Zhang, Jie Lu, Wolfgang A. Halang

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.

Figure 1: Comparison of two tree-structured telecom accounts (T1 and T2) showing different service plan hierarchies.

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

Abstract

In many business situations, products or user profile data are so complex that they need to be described by use of tree structures. Evaluating the similarity between tree-structured data is essential in many applications, such as recommender systems. To evaluate the similarity between two trees, concept corresponding nodes should be identified by constructing an edit distance mapping between them. Sometimes, the intension of one concept includes the intensions of several other concepts. In that situation, a one-to-many mapping should be constructed from the point of view of structures. This paper proposes a tree similarity measure model that can construct this kind of mapping. The similarity measure model takes into account all the information on nodes’ concepts, weights, and values. The conceptual similarity and the value similarity between two trees are evaluated based on the constructed mapping, and the final similarity measure is assessed as a weighted sum of their conceptual and value similarities. The effectiveness of the proposed similarity measure model is shown by an illustrative example and is also demonstrated by applying it into a recommender system.
BibTeX
@inproceedings{wu2012similarity,
  author = {Dianshuang Wu and Guangquan Zhang and Jie Lu and Wolfgang A. Halang},
  title = {{A Similarity Measure on Tree Structured Business Data}},
  booktitle = {ACIS},
  year = {2012},
}
Figure