Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a situation where we are given a set of objects each with a numeric score stating it's importance. Let's call them Level 1 (or L1) objects.

There is another set of objects that are similarly scored/ranked. Let's call them L2 (for level 2). Each L2 object belongs to exactly one parent (i.e. L1 object). Thus we have a tree where the root is just an empty node (L0), so to speak, parents at L1, their children at L2 and so on.

The question is what is a "correct" way of scaling the scores of the children as per their parents so that the sum of scores at each level is 1?

Approach currently used:

  1. Normalize L1 so that scores are between 0 and 1 and add up to 1
  2. Normalize the children of each node in L1 so that sum of children = 1 and then multiply (scale) by the parent's score.
  3. Repeat for every level

This however has an anomaly in that if a particular parent has only one child, then the score of that child is equal to that of the parent - which makes the resulting prioritization skewed. It seems the less children that a parent has the higher the child scores and conversely if there are more children each child gets a smaller score.

Is there a more "correct" way of handling hierarchical scaling/prioritization or do we just accept this as an anomaly of mathematics and 'ignore' outliers?

UPDATE: Clarification on what is meant by 'score is influenced by parent' - It implies that although the child levels can be scored/prioritized independent of their parents (i.e. by comparing with each other perhaps) the final score should be 'scaled by' (read influenced by) that of their parent.

  • Parent A $(5)$
    • child x $(2)$
    • child y $(3)$
    • child z $(6)$
  • Parent B $(8)$
    • child p $(6)$
    • child q $(4)$
    • child r $(3)$
    • child s $(5)$
  • ...and so on**

(The numbers in parenthesis are the scores of that item)

So all parents could be scored/prioritized independently and so their children and children's children (not shown). The scoring scheme needs to be such so as to prioritize these items in a mathematically correct manner. A simple scheme would be to multiply the score of each child by that of the parent (similar to solution shown above)

Context: This is a prioritization scheme for ordering groups and must also lend itself for ordering the children within the subgroups and so on. Items at a particular level i.e. all parents or all children in the above example are 'comparable' i.e. a comparing A and s make no sense but x and s does.

share|improve this question
    
I was unable to find any suitable tags. Please feel free to retag the question with appropriate tags... –  PhD Jun 29 '12 at 1:45
1  
You're not happy if an only child has the same score as its parent, so I think you have to decide what you want the score of such a child to be - half the parent's score? some function depending on the level? or depending on the total number of objects on this level? Only you know what you do and what you don't consider acceptable. Once you can put that into words, we can do some mathematics. –  Gerry Myerson Jun 29 '12 at 6:01
    
@GerryMyerson - well my question is I don't want to have a function for each child score. I just want it to be influenced by the parent, that's it. It's just it feels anomalous... –  PhD Jun 29 '12 at 6:30
    
Fine. But you still have to decide what feels anomalous, and what doesn't, before you can start to do any mathematics on it. –  Gerry Myerson Jun 29 '12 at 7:08
    
@GerryMyerson - don't really know if it indeed is. If folks claim it isn't I'll be confident and use this approach and leave it at that. I've made that point clear in the question. I just want to know if there is "another" way or "my" way 'correct' - mathematically speaking –  PhD Jun 29 '12 at 7:20

3 Answers 3

This is not really an answer but it's too long for a comment.

While the added context is helpful, it is still lacking enough structure for me to provide any specific answer. However, let me take this opportunity to describe a potentially useful approach to figure out what is going on here. The idea is that the initial re-scoring system proposed by the asker produced "anomalous" results. The real question is "what do we mean by 'anomalous'?". One way to get at this is to establish some properties that a good re-scoring system should have.

For example, suppose we let $p(x)$ be the initial score and $q(x)$ be the re-scaled scores taking into account parent scores. We may require a scaling rule to have properties like:

  1. Let $x$ and $y$ be siblings (i.e.: have the same parent) such that $p(x) < p(y)$. Then, $q(x) < q(y)$. If $p(x) = p(y)$, then $q(x) = q(y)$.
  2. Let $x$ and $y$ have parents $u$ and $v$, respectively ($u \neq v$). Let $p(x) = p(y)$ and $p(u) < p(v)$. Then, $q(x) < q(y)$.

Note that the initial re-scoring system proposed by the asker satisfies rule number 1 but violates rule number 2.

Now, it should be clear that the correctness of a scoring rule depends entirely on the specific properties that it is expected to have. It is likely infeasible for the asker to provide the full context of the significance of these priority scores, but they may be able to provide a (more or less) complete set of properties that a suitable re-scoring system should have. Thinking about extreme cases may help sharpen the intuition (e.g.: what happens when all scores are equal? what happens when there's one score much, much bigger than all the others? are zero or negative scores possible?).

share|improve this answer

Perhaps you should - at least for a momement - not think about the scores as single numbers, but instead as strings of numbers: the rescoring of your description would then translate into appending the raw score number of the child to the string of the parent. On these strings you could then perform lexicographical comparisons.

There are two extreme scoring mechanisms which you can model in this fashion:

  • Parent first: order children by their parent first, and use the child scores only to order siblings
  • Child first: order children by unmodified child score, and only use the parent score to break ties

I guess what you actually want would be somewhere between those two extremes. So how to turn this back into a mixed form? Suppose that each score is given as a number between 0 and 1 with three decimals. Then you could multiply scores by 1000 for each level, and ensure that the score values would never overlap, thus resulting in lexicographical sorting. Now you can adjust that factor from 1000 (one lexicographical sorting) through 1 (simply add all scores along the path) to 1/1000 (the opposite lexicographical sorting). If this were a computer user interface, you'd see a logarithmic slider here.

Maybe there is a point somewhere along this way where things feel right. And even if this exact scheme doesn't fulfill your needs, maybe thinking more about addition and less about multiplication will help someone to come up with a better solution.

Oh, I forgot the requirement that scores of one level should again add up to 1. But that normalization is easy to accomplish, once you're back to numbers.

share|improve this answer

What about this almost childish way of ordering?

You start by having a parent $L_{0}$ with no score, then some children $a$, $b$, $c$ ... of that parent with a score $s_{a}, s_{b}, s_{c}, ..., s_{n}$ You sum each score $s_{a}+s_{b}+s_{c}+ ...+ s_{n}$ and reassign a normalized score for each children (so, $s_{a}$ becomes $s^{'}_{a} = \displaystyle \frac{s_{a}}{s_{a}+s_{b}+s_{c}+...+s_{n}}$ and so on). Now you have a set of children for $L_{1}$ that sum $1$. Then you go to normalize again children of children nodes ($L_{2}$ nodes). You divide those elements by $10$ and then add its parent score. So if you have a parent with normalized score 0.3 and a children with normalized score 0.7, after you have divided children of children's score by $10$, you'd have $0.3+0.7/10 = 0.37$, and that's the score for that child.

If you want to order nodes in $L_{1}$, you only need to consider the first digit after the decimal point of every node in $L_{1}$. If you want to order nodes in $L_{2}$ (disregarding their parents's score) you only consider the second digit after the decimal point in nodes belonging to that level, and so on. If you want to order nodes in $L_{2}$ taking into account their parent's score, you consider the first and second digit after the decimal point. Well, you get the point.

share|improve this answer
    
I'm not sure I understand the divide by 10 bit. Why and where did 10 come from? Seems like a magic number or maybe I'm missing something. If not too much to ask could you depict your example in a tabular fashion so as to better 'see' the math in action? –  PhD Jul 15 '12 at 18:50
    
PS: I think I understand the reason for divide by 10 to only 'place the digit at that decimal location' - but you assume that scores will be only 1 decimal. It could be (and is) upto 4 for precision and preventing ties. So I'd land up with 'huge' decimal numbers upto 8-12 places for 2-3 levels!! –  PhD Jul 15 '12 at 18:52
1  
Yes, divide by 10 serves that purpose you mentioned. I didn't know your scores could have several digits of length as your example only considered single digit scores, but it's a fair point. Probably you can't map your scores within [0, 9] so this won't work for you. I will post something else if I come up with a new idea. –  Robert Smith Jul 15 '12 at 20:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.