Generalized weighted tree similarity algorithms for taxonomy trees
| Autor: | K Venu Gopal Rao, D Pramodh Krishna |
|---|---|
| Jazyk: | angličtina |
| Předmět: |
Matching (statistics)
Binary tree business.industry Computer science Weight-balanced tree 020206 networking & telecommunications Pattern recognition 02 engineering and technology General Medicine Missing data Tree (graph theory) Set (abstract data type) Similarity (network science) Ternary search tree 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Artificial intelligence business Algorithm |
| Zdroj: | EURASIP Journal on Information Security. 2016(1) |
| ISSN: | 1687-417X |
| DOI: | 10.1186/s13635-016-0035-2 |
| Popis: | Taxonomy trees are used in machine learning, information retrieval, bioinformatics, and multi-agent systems for matching as well as matchmaking in e-business, e-marketplaces, and e-learning. A weighted tree similarity algorithm has been developed earlier which combines matching and missing values between two taxonomy trees. It is shown in this paper that this algorithm has some limitations when the same sub-tree appears at different positions in a pair of trees. In this paper, we introduce a generalized formula to combine matching and missing values. Subsequently, two generalized weighted tree similarity algorithms are proposed. The first algorithm calculates matching and missing values between two taxonomy trees separately and combines them globally. The second algorithm calculates matching and missing values at each level of the two trees and combines them at every level recursively which preserves the structural information between the two trees. The proposed algorithms efficiently use the missing value in similarity computation in order to distinguish among taxonomy trees that have the same matching value but with different miss trees at different positions. A set of synthetic weighted binary trees is generated and computational experiments are carried out that demonstrate the effects of arc weights, matching as well as missing values in a pair of trees. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|