CODEWITHSUNDEEP
javarecursion
Cap
Cap

Reputation: 363

Mathematical formula to a recursive method

I need to implement current formula.It is for scoring the nodes in a taxonomy. Basically, the score of a node depends on the amount of child nodes and their scores ((nodes(h+1)) is the amount of nodes on the next level and Cl(concept) is a set of children).

Formula

In my usecase term frequencies are only defined for the leaves as of now. I have made an implementation, but the issue is that when there are 2 children for the node then the implementation only goes to one side.

For a given taxonomy:

     1
    / \
   2   3
   |   |
   4   17
  / \
 11 13

the frequencies are given: freq(11) = 3, freq(13) = 5 and freq(17) = 10. When I try to get the score for node(1), the result is 0.0, because the recursion doesn't go into descendent node(4), it retrieves only freq(17) and that's it. Normally, the result should be 7.

Here is the implementation: 

public static float calcScore(int keyID, Map<Integer, Integer> frequencies, Map<Integer, Integer> subTaxonomy) {
    float res = 0f;
    int nodes = 0;
    if (frequencies.containsKey(keyID)) {
        return frequencies.get(keyID) + 0f;
    }

    for (Map.Entry<Integer, Integer> entry : subTaxonomy.entrySet()) {
        if (entry.getValue() - 1 == subTaxonomy.get(keyID)) {
            nodes++;
            res += calcScore(entry.getKey(), frequencies, subTaxonomy);
        }
    }
    return 1 / nodes * res;
}

NOTE:

subTaxonomy - stores the nodeID and its level in the taxonomy

frequencies - store the frequencies for leaf nodes.

I also created a snippet at Ideone: Source

How should I edit the code, so that it traverses all over the children for a given node?

UPDATE

So now, in updated source, it traverses all over taxonomy, but the result is 0.0 still.

Upvotes: 12

Views: 516

Answers (2)

Liam
Liam

Reputation: 29674

Copy of OPs answer that was posted into the question

CORRECT METHOD

public static float calcScore(int keyID, Map<Integer, Integer> frequencies, Map<Integer, Integer> subTax) {
    float res = 0f;
    int nodes = 1;
    if (frequencies.containsKey(keyID)) {
        return frequencies.get(keyID) + 0f;
    }

    for (Map.Entry<Integer, Integer> entry : subTax.entrySet()) {
        if (entry.getValue() == keyID) {
            res += calcScore(entry.getKey(), frequencies, subTax);
            nodes++;
        }
    }
    nodes--;
    return (float)1 / nodes * res;
}

NOTE

subTax - is the map containing (child_id, parent_id)

Upvotes: 1

PrR3
PrR3

Reputation: 1246

Your problem is located at this line of code

if (entry.getValue() - 1 == subTaxonomy.get(keyID)) {

The left part of your tree does not hold your intended convention that the childs id (which is not a leaf of the tree) follows the formula childs id = parents id - 1

I would suggest a change to your implementation including the parents id in your taxonomy instead of the node level. The level may be counted during recoursion and passed as another parameter.

New signature may look like this:

public static float calcScore(int keyID, Map<Integer, Integer> frequencies, Map<Integer, Integer> subTaxonomy, int level)

further you may consider to drop the level information from your code, if it doesn't contribute to your final result!

Upvotes: 1

Related Questions