{"id":2037,"date":"2025-10-26T17:43:58","date_gmt":"2025-10-26T16:43:58","guid":{"rendered":"https:\/\/xeddixx.cluster029.hosting.ovh.net\/?page_id=2037"},"modified":"2025-10-27T10:14:42","modified_gmt":"2025-10-27T09:14:42","slug":"hierarchical-problems","status":"publish","type":"page","link":"https:\/\/www.francq.info\/index.php\/hierarchical-problems\/","title":{"rendered":"Hierarchical Problems"},"content":{"rendered":"\n

Abstract<\/h4>\n\n\n\n

The hierarchical problems are a class of optimization problems where the goal is to place a set of objects in a tree of nodes, each object being assigned to one node only.<\/p>\n\n\n\n

Table of Contents<\/h5>\n\n\n\n

1.\u2003Description<\/a><\/p>\n\n\n\n

1.1. General Problem<\/a><\/p>\n\n\n\n

1.2. Set Theory Problem<\/a><\/p>\n\n\n\n

2. Constraints<\/a><\/p>\n\n\n\n

3. Criteria<\/a><\/p>\n\n\n\n

4. Algorithm evaluation<\/a><\/p>\n\n\n\n

4.1. Similarity Measure for Phylogenetic Trees<\/a><\/p>\n\n\n\n

4.2. Extension to Trees of Objects Sharing Attributes<\/a><\/p>\n\n\n\n

5. Related<\/a><\/p>\n\n\n\n

References<\/a><\/p>\n\n\n\n

Notes<\/a><\/p>\n\n\n\n

1. Description\u2191<\/a><\/h5>\n\n\n\n
1.1. General Problem\u2191<\/a><\/h6>\n\n\n\n

A hierarchical problem is the task to assigning a set of objects into a hierarchy (tree of nodes) according some criteria, each object being assigned to one node only. In general, the criteria is to regroup objects sharing similar characteristics in the same part of the tree (with regards to some characteristics), where each node can have as many child nodes as necessary. Nodes without children are called leaf nodes. But the goal may vary. For example when a taxonomy must be build<\/a>, the tree should be balanced: the words should be allocate homogeneously though the tree.<\/p>\n\n\n\n

The rigorous definition of the problem begins with a set \\(\\mathcal{O}\\)<\/mathml> of \\(|\\mathcal{O}|\\) objects to place in a set \\(\\mathcal{N}\\) of \\(|\\mathcal{N}|\\) nodes:<\/p>\n\n\n\n

\\[\\mathcal{O}=\\{o_{o}\\}\\quad\\quad\\forall\\,o=1,\\cdots,|\\mathcal{O}|\\]\n\n\n\n

\\[\\mathcal{N}=\\{n_{n}\\}\\quad\\quad\\forall\\,n=1,\\cdots,|\\mathcal{N}|\\]\n\n\n\n

Each node, \\(n_n\\), has a set of \\(\\mathcal{N}_{n}\\) or \\(|\\mathcal{N}_{n}|\\) children:<\/p>\n\n\n\n

\\[\\mathcal{N}_{n}=\\{n_{ni}\\}\\quad\\quad\\forall\\,n=1,\\cdots,|\\mathcal{N}|\\,,\\,\\forall\\,i=1,\\cdots,|\\mathcal{N}_{n}|\\]\n\n\n\n

Depending of the problem, the number of available nodes can be infinite (when a taxonomy must be build<\/a> for example) or limited (such as when a set of resources must be allocated to an organizational structure).<\/p>\n\n\n\n

1.2. Set Theory Problem\u2191<\/a><\/h6>\n\n\n\n

A particular class of hierarchical problems, for example the\u00a0taxonomy building<\/a>, consists in building a tree as defined in the set theory. In this case, the objects are defined using a set of attributes\u00a0\\(\\mathcal{A}=\\{a_{1},\\ldots,a_{|\\mathcal{A}|}\\}\\), each object,\u00a0\\(o_o\\), being defined by a vector,\u00a0\\(\\vec{o_{o}}=\\{o_{o1},\\ldots,o_{o|A|}\\}\\), where:<\/p>\n\n\n\n

\\[o_{oa}=\\left\\{ \\begin{array}{cc} 0 & \\mathrm{if}\\,a_{a}\\,\\mathrm{does\\,not\\,define}\\,o_{o}\\\\ 1 & \\mathrm{if}\\,a_{a}\\,\\mathrm{defines}\\,o_{o} \\end{array}\\right.\\]\n\n\n\n

Each node is also defined by a similar vector, \\(\\vec{n_{n}}=\\{n_{n1},\\ldots,o_{n|\\mathcal{A}|}\\}\\), where:<\/p>\n\n\n\n

\\[n_{na}=\\left\\{ \\begin{array}{cc} 0 & \\mathrm{if}\\,a_{a}\\,\\mathrm{does\\,not\\,define}\\,n_{n}\\\\ 1 & \\mathrm{if}\\,a_{a}\\,\\mathrm{defines}\\,n_{n} \\end{array}\\right.\\]\n\n\n\n

An object, \\(o_o\\), can then be assign to a node, \\(n_n\\), if:<\/p>\n\n\n\n

\\[\\left\\{ \\begin{array}{cc} n_{na}=o_{oa} & \\forall n_{oa}\\neq0\\\\ n_{na}=0 & \\forall o_{oa}=0 \\end{array}\\right.\\]\n\n\n\n

It is possible to build a rooted tree where each leaf node corresponds to a given object and each non-leaf node corresponds to a given sub-set of attributes shared by all its children (except the root associated with no attributes). An example of such a tree is a thesaurus where each leaf node correspond to a particular document, each non-leaf node corresponds to a topic and the attributes are concepts.<\/p>\n\n\n\n

For example, suppose we have the following set of objects where attributes are represented by identifiers:<\/p>\n\n\n\n

\\[\\begin{array}{l} a=\\{1,2,3,4,12\\}\\\\ b=\\{1,2,3,5,6\\}\\\\ c=\\{1,2,3,7,11\\}\\\\ d=\\{5,6,7,8,9\\}\\\\ e=\\{5,6,7,8,10\\} \\end{array}\\]\n\n\n\n

Figure 1 shows three trees representing different configurations for these objects. The attributes \u201cadded\u201d by each node are specified.<\/p>\n\n\n\n

\"\"<\/td>\"\"<\/td>\"\"<\/td><\/tr>
\\(T_1\\)<\/td>\\(T_2\\)<\/td>\\(T_3\\)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Figure 1. Different trees.<\/p>\n\n\n\n

Building such a tree becomes difficult when the number of objects and attributes increases. In fact, depending from the goal (building a balanced tree, minimizing the number of non-leaf nodes, etc.), the resulting tree may be different.<\/p>\n\n\n\n

2. Constraints\u2191<\/a><\/h5>\n\n\n\n

The hierarchical problems introduce several constraints, but it is always possible to define them as a member of one of the three constraints classes, namely the \u201ccapacity constraints\u201d class, the \u201chomogeneity constraints\u201d and the \u201cprofile constraints\u201d classes.<\/p>\n\n\n\n

The \u201ccapacity constraints\u201d\u00a0\\(\\mathcal{C}_{c}\\) constitute the first class. It regroups the constraints related to a given \u201ccapacity\u201d of each node. In the case the taxonomy building<\/a>, one constraint could be a homogeneous repartition of the words between them. These constraints may also introduce a minimal or maximal number of objects that a node must have.\u00a0<\/p>\n\n\n\n

The \u201chomogeneity constraints\u201d \\(\\mathcal{C}_{h}\\) are the second class. These constraints specify the conditions that must be respected by an object when it is put in an existing node. This may be, for example, a minimal similarity with the objects already assigned.<\/p>\n\n\n\n

The \u201cprofile constraints\u201d \\(\\mathcal{C}_{p}\\) are the last class. To obtain a valid solution, the clustering must respect the \u201cwishes\u201d of each object. For example, if the goal is to allocate persons to an organizational structure, a constraint could be to each person should be assigned to an unit where he or she knows someone working for it.<\/p>\n\n\n\n

3. Criteria\u2191<\/a><\/h5>\n\n\n\n

The criteria that should be optimized for the hierarchical problem vary from one problem to another. For some problems, the criteria are well defined. But, in the case of the thesaurus building for example, where the goal is to homogeneously organize terms in a hierarchy of concepts, the problem is\u00a0fuzzy<\/em>: is it not easy to express the fact that \u201ca word is related to a concept\u201d. When several criteria must be optimized, the hierarchical problem is a\u00a0multiple objective one<\/a>.<\/p>\n\n\n\n

Some hierarchical algorithms work with one type of problems (criteria) only. Other methods, such as the\u00a0Hierarchical Genetic Algorithms (HGA)<\/a>, may solve a whole range of problems.<\/p>\n\n\n\n

4. Algorithm evaluation\u2191<\/a><\/h5>\n\n\n\n

To evaluate the performance of an algorithm, it is necessary to have an \u201cideal\u201d solution for a given problem instance and some measures to compare the \u201ccomputed\u201d solution provided by the algorithm with this \u201cideal\u201d solution. Two situations exist:<\/p>\n\n\n\n

    \n
  1. The quality of a solution depends on a computation based on the clustering.<\/li>\n\n\n\n
  2. The quality of a solution depends on the particular assignment of the objects.<\/li>\n<\/ol>\n\n\n\n

    In the first case, a comparison between the computation done for the \u201ccomputed\u201d and \u201cideal\u201d solution evaluates the performance of the algorithm. For the second situation, we need some measures to compare the \u201ccomputed\u201d assignments to the ideal ones (each object is assigned to an \u201cideal node\u201d in the \u201cideal\u201d solution).<\/p>\n\n\n\n

    I propose an adaptation of a similarity measure for phylogenetic trees in the case when the tree to build is related to the set theory (section 1.2<\/a>).<\/p>\n\n\n\n

    4.1. Similarity Measure for Phylogenetic Trees\u2191<\/a><\/h6>\n\n\n\n

    In a work related to information retrieval in phylogenetic information systems, Whang, Shan, Shasha and Piel propose a similarity measure for phylogenetic trees that satisfy certain properties [1<\/a>]. Their method is based on an Up matrix<\/em>, \\(U=\\{U_{uv}\\}\\), associated with each tree, where the values \\(U_{uv}\\) represent the number of up operations needed to go from node \\(u\\) to node \\(v\\). <\/p>\n\n\n\n

    Taking the trees \\(T_1\\), \\(T_2\\) and \\(T_3\\) of Figure 1 as examples, we have \\(U_{T_{1},ab}=1\\) because it is necessary to have one up operation (and one down operation) to go from node \\(a\\) to note \\(b\\).<\/p>\n\n\n\n

    Similarly, \\(U_{T_{3},ea}=3\\) because it takes three up operations (and two down operations) to go from node \\(e\\) to node \\(a\\). Table 1 shows the up matrices for the trees \\(T_1\\), \\(T_2\\) and \\(T_3\\). Notice that \\(U_{uv}\\neq U_{vu}\\).<\/p>\n\n\n\n

    \\(\\left(\\begin{array}{ccccc} 0 & 1 & 1 & 2 & 2\\\\ 1 & 0 & 1 & 2 & 2\\\\ 1 & 1 & 0 & 2 & 2\\\\ 2 & 2 & 2 & 0 & 1\\\\ 2 & 2 & 2 & 1 & 0 \\end{array}\\right)\\)<\/td>\\(\\left(\\begin{array}{ccccc} 0 & 1 & 2 & 2 & 2\\\\ 1 & 0 & 2 & 2 & 2\\\\ 2 & 2 & 0 & 1 & 1\\\\ 3 & 3 & 2 & 0 & 1\\\\ 3 & 3 & 2 & 1 & 0 \\end{array}\\right)\\)<\/td>\\(\\left(\\begin{array}{ccccc} 0 & 2 & 1 & 2 & 2\\\\ 2 & 0 & 2 & 1 & 1\\\\ 1 & 2 & 0 & 2 & 2\\\\ 3 & 2 & 3 & 0 & 1\\\\ 3 & 2 & 3 & 1 & 0 \\end{array}\\right)\\)<\/td><\/tr>
    \\(U_1\\)<\/td>\\(U_2\\)<\/td>\\(U_3\\)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

    Table 1. Up Matrices for Phylogenetic Trees<\/p>\n\n\n\n

    The authors propose a measure of similarity between a query tree \\(P\\) and a data tree \\(D\\)\u200a1<\/a><\/sup>. To do so, they first define four different sets of labeled nodes : \\(V_P\\) is the set of those in \\(P\\), \\(V_D\\) is the set of those in \\(D\\), \\(I=V_{p}\\cap V_{D}\\) and \\(J=V_{P}\\setminus V_{D}\\).<\/p>\n\n\n\n

    Then, they introduce the Updown distance<\/em> from \\(P\\) to \\(D\\), denoted \\(Updown\\_dist(P,D)\\), as:<\/p>\n\n\n\n

    \\[Updown\\_dist(P,D)=\\sum_{u\\in I}\\sum_{v\\in I}\\left|U_{P,uv}-U_{D,uv}\\right|+\\sum_{u\\in J}\\sum_{v\\in J}U_{P,uv}\\]\n\n\n\n

    Finally, they propose a similarity measure, denoted \\(USim(P,D)\\in[0,1]\\), given by\u200a2<\/a><\/sup>:<\/p>\n\n\n\n

    \\[USim(P,D)=1-\\frac{Updown\\_dist(P,D)}{\\sum_{u\\in V_{P}}\\sum_{v\\in V_{P}}U_{P,uv}}\\]\n\n\n\n

    4.2. Extension to Trees of Objects Sharing Attributes\u2191<\/a><\/h6>\n\n\n\n

    The proposed similarity measure can be used for the hierarchical problem if we consider that the labeled nodes correspond to the objects, that the \u201cideal\u201d tree represents a sort of ideal query, and that the computed trees are data trees. Moreover, in our problem, since all the trees contain all the objects, \\(J=\\emptyset\\), and the second term of is always null. For the same reason, the reduction step described in the original paper is not necessary in our case [1<\/a>].<\/p>\n\n\n\n

    Let us suppose that \\(T_1\\) is the ideal tree and that \\(T_2\\) and \\(T_3\\) are two different computed trees. Using the previous introduced similarity measure with \\(P=T_1\\) and \\(D={T_2,T_3}\\), we can compute a similarity between the computed trees and the ideal one:<\/p>\n\n\n\n

    \\begin{align}USim(T_{1},T_{2})&=&0.688\\end{align}<\/p>\n\n\n\n

    \\begin{align}USim(T_{1},T_{3})&=&0.688\\end{align}<\/p>\n\n\n\n

    The fact that \\(USim(T_{1},T_{2})=USim(T_{1},T_{3})\\) is logical because the \u201cstructural differences\u201d are identical between \\(T_1\\) and \\(T_2\\), and \\(T_1\\) and \\(T_3\\).<\/p>\n\n\n\n

    Indeed, in both case, the \u201cleft\u201d part of the tree is composed from two leaf-nodes, and the \u201cright\u201d part of the tree is divided in two parts containing respectively an object normally assigned to the \u201cleft\u201d part (\\(c\\) in \\(T_2\\) and \\(b\\) in \\(T_3\\)), and the two objects \\(d\\) and \\(e\\).<\/p>\n\n\n\n

    But, regarding the attributes assigned to the non-leaf nodes, it is clear that \\(T_2\\) and \\(T_3\\) are not identical. Intuitively, we may consider that the sub-tree formed by \\(d\\), \\(e\\) and their parent node is more similar between \\(T_1\\) and \\(T_2\\) than between \\(T_1\\) and \\(T_3\\). In fact, in \\(T_2\\) this sub-tree shares one attribute (\\(7\\)) with another object (\\(c\\)); and in \\(T_3\\), it shares two attributes (\\(5\\) and \\(6\\)) with another object (\\(b\\)), while in \\(T_1\\) it shares no attributes at all.<\/p>\n\n\n\n

    Whang, Shan, Shasha and Piel propose a simple adaptation of their similarity measure for weighted tree [2<\/a>]. They propose to associate with each up operation a weight that equals the weight of the corresponding edge. The values of the Up matrix becomes then the sum of the weights associated to the up operations. We propose to use this extension and to define the weights as the number of non-shared attributes at a given node of the tree. <\/p>\n\n\n\n

    Let us take again the trees \\(T_1\\), \\(T_2\\) and \\(T_3\\) of Figure 1 and detail some examples. We have \\(U_{T_{1},ab}=2\\) because the up operation of a corresponds to two non-shared attributes (\\(4\\) and \\(12\\)).<\/p>\n\n\n\n

    In \\(T_2\\), \\(U_{T_{2},cd}=4\\) because the up operation of \\(c\\) corresponds to four non-shared attributes (\\(1\\), \\(2\\), \\(3\\) and \\(11\\)). <\/p>\n\n\n\n

    Finally, in \\(T_3\\), \\(U_{T3,eb}=3\\) because the two needed up-operations of \\(e\\) corresponds to three non-shared attributes (\\(9\\) for the first up operation, and \\(7\\) and \\(8\\) for the second one).<\/p>\n\n\n\n

    Table 2 shows the up matrices for the trees \\(T_1\\), \\(T_2\\) and \\(T_3\\) using the non-shared attributes weights.<\/p>\n\n\n\n

    \\(\\left(\\begin{array}{ccccc} 0 & 2 & 2 & 5 & 5\\\\ 2 & 0 & 2 & 5 & 5\\\\ 2 & 2 & 0 & 5 & 5\\\\ 5 & 5 & 5 & 0 & 1\\\\ 5 & 5 & 5 & 1 & 0 \\end{array}\\right)\\)<\/td>\\(\\left(\\begin{array}{ccccc} 0 & 2 & 5 & 5 & 5\\\\ 2 & 0 & 5 & 5 & 5\\\\ 5 & 5 & 0 & 4 & 4\\\\ 5 & 5 & 4 & 0 & 1\\\\ 5 & 5 & 4 & 1 & 0 \\end{array}\\right)\\)<\/td>\\(\\left(\\begin{array}{ccccc} 0 & 5 & 2 & 5 & 5\\\\ 5 & 0 & 5 & 3 & 3\\\\ 2 & 5 & 0 & 5 & 5\\\\ 5 & 3 & 5 & 0 & 1\\\\ 5 & 3 & 5 & 1 & 0 \\end{array}\\right)\\)<\/td><\/tr>
    \\(U_1\\)<\/td>\\(U_2\\)<\/td>\\(U_3\\)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

    Table 2. Up Matrices with Non-Shared Attributes Weights<\/p>\n\n\n\n

    Using the similarity measure with theses matrices, we can compute another similarity between these trees:<\/p>\n\n\n\n

    \\begin{align}USim(T_{1},T_{2})&=&0.784\\end{align}<\/p>\n\n\n\n

    \\begin{align}USim(T_{1},T_{3})&=&0.73\\end{align}<\/p>\n\n\n\n

    Now, as expected, \\(USim(T_{1},T_{2})>USim(T_{1},T_{3})\\).<\/p>\n\n\n\n

    5. Related\u2191<\/a><\/h5>\n\n\n\n

    Hierarchical Genetic Algorithms<\/a><\/p>\n\n\n\n

    References\u2191<\/a><\/h5>\n\n\n\n

    [1] Jason T. L. Wang, Huiyuan Shan, Dennis Shasha & William H. Piel, \u201cTreerank: A Similarity Measure for Nearest Neighbor Searching in Phylogenetic Databases\u201d, In Proceedings of the 15th International Conference on Scientific and Statistical Database Management<\/em>, pp. 171\u2014180, 2003.<\/p>\n\n\n\n

    [2] Jason T. L. Wang, Huiyuan Shan, Dennis Shasha & William H. Piel, \u201cFast Structural Search in Phylogenetic Databases\u201d, Evolutionary Bioinformatics Online<\/em>, 1, pp. 37\u201446, 2005.<\/p>\n\n\n\n

    Notes\u2191<\/a><\/h5>\n\n\n
    1. For their problem, they compute the similarities between the query tree and all the trees of the database and retrieve those who have a similarity greater than a given threshold. \u21a9\ufe0e<\/a><\/li>
    2. In their original formula, the similarity is given as a percentage. \u21a9\ufe0e<\/a><\/li><\/ol>","protected":false},"excerpt":{"rendered":"

      Abstract The hierarchical problems are a class of optimization problems where the goal is to place a set of objects in a tree of nodes, each object being assigned to one node only. Table of Contents 1.\u2003Description 1.1. General Problem 1.2. Set Theory Problem 2. Constraints 3. Criteria 4. Algorithm evaluation 4.1. Similarity Measure for […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":"[{\"content\":\"For their problem, they compute the similarities between the query tree and all the trees of the database and retrieve those who have a similarity greater than a given threshold.\",\"id\":\"bee65ef0-1ece-464e-8d59-994cdec29518\"},{\"content\":\"In their original formula, the similarity is given as a percentage.\",\"id\":\"0d13d2f6-09d3-4384-bea9-77e31a083cca\"}]"},"class_list":["post-2037","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/pages\/2037","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/comments?post=2037"}],"version-history":[{"count":18,"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/pages\/2037\/revisions"}],"predecessor-version":[{"id":2236,"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/pages\/2037\/revisions\/2236"}],"wp:attachment":[{"href":"https:\/\/www.francq.info\/index.php\/wp-json\/wp\/v2\/media?parent=2037"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}