{"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\u00a0\\(\\mathcal{O}\\)<\/mathml>\u00a0of\u00a0\\(|\\mathcal{O}|\\) objects to place in a set\u00a0\\(\\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,\u00a0\\(n_n\\), has a set of\u00a0\\(\\mathcal{N}_{n}\\)\u00a0or\u00a0\\(|\\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,\u00a0\\(\\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,\u00a0\\(o_o\\), can then be assign to a node,\u00a0\\(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\u00a0shows 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\u00a0\\(\\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\u00a0\\(\\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\u00a01.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,\u00a0Whang,\u00a0Shan,\u00a0Shasha\u00a0and\u00a0Piel\u00a0propose a similarity measure for phylogenetic trees that satisfy certain properties\u00a0[1<\/a>]. Their method is based on an\u00a0Up matrix<\/em>, \\(U=\\{U_{uv}\\}\\), associated with each tree, where the values \\(U_{uv}\\)\u00a0represent the number of up operations needed to go from node\u00a0\\(u\\)\u00a0to node\u00a0\\(v\\). <\/p>\n\n\n\n

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

    Similarly,\u00a0\\(U_{T_{3},ea}=3\\)\u00a0because it takes three up operations (and two down operations) to go from node\u00a0\\(e\\)\u00a0to node\u00a0\\(a\\). Table\u00a01\u00a0shows the up matrices for the trees\u00a0\\(T_1\\),\u00a0\\(T_2\\) and\u00a0\\(T_3\\). Notice that\u00a0\\(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\u00a0\\(P\\)\u00a0and a data tree\u00a0\\(D\\)\u200a1<\/a><\/sup>. To do so, they first define four different sets of labeled nodes :\u00a0\\(V_P\\)\u00a0is the set of those in\u00a0\\(P\\),\u00a0\\(V_D\\)\u00a0is the set of those in\u00a0\\(D\\),\u00a0\\(I=V_{p}\\cap V_{D}\\)\u00a0and\u00a0\\(J=V_{P}\\setminus V_{D}\\).<\/p>\n\n\n\n

    Then, they introduce the\u00a0Updown distance<\/em>\u00a0from\u00a0\\(P\\)\u00a0to\u00a0\\(D\\), denoted\u00a0\\(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\u00a0[1<\/a>].<\/p>\n\n\n\n

    Let us suppose that\u00a0\\(T_1\\)\u00a0is the ideal tree and that\u00a0\\(T_2\\)\u00a0and\u00a0\\(T_3\\)\u00a0are two different computed trees. Using the previous introduced similarity measure with\u00a0\\(P=T_1\\)\u00a0and\u00a0\\(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\u00a0\\(USim(T_{1},T_{2})=USim(T_{1},T_{3})\\) is logical because the \u201cstructural differences\u201d are identical between\u00a0\\(T_1\\)\u00a0and\u00a0\\(T_2\\), and\u00a0\\(T_1\\)\u00a0and\u00a0\\(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\\)\u00a0in\u00a0\\(T_2\\)\u00a0and\u00a0\\(b\\)\u00a0in\u00a0\\(T_3\\)), and the two objects\u00a0\\(d\\)\u00a0and\u00a0\\(e\\).<\/p>\n\n\n\n

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

    Whang,\u00a0Shan,\u00a0Shasha\u00a0and\u00a0Piel\u00a0propose a simple adaptation of their similarity measure for weighted tree\u00a0[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.\u00a0<\/p>\n\n\n\n

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

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

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

    Table\u00a02\u00a0shows the up matrices for the trees\u00a0\\(T_1\\),\u00a0\\(T_2\\)\u00a0and\u00a0\\(T_3\\)\u00a0using 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,\u00a0\\(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]\u00a0Jason T. L. Wang,\u00a0Huiyuan Shan,\u00a0Dennis Shasha\u00a0&\u00a0William H. Piel, \u201cTreerank: A Similarity Measure for Nearest Neighbor Searching in Phylogenetic Databases\u201d, In\u00a0Proceedings of the 15th International Conference on Scientific and Statistical Database Management<\/em>, pp. 171\u2014180, 2003.<\/p>\n\n\n\n

    [2]\u00a0Jason T. L. Wang,\u00a0Huiyuan Shan,\u00a0Dennis Shasha\u00a0&\u00a0William H. Piel, \u201cFast Structural Search in Phylogenetic Databases\u201d,\u00a0Evolutionary 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}]}}