The Data Mining Forum 
IMPORTANT: This is the old Data Mining forum.
I keep it online so that you can read the old messages.
Please post your new messages in the new forum: https://forum2.philippe-fournier-viger.com/index.php
how to balance the expanded tree
Posted by:
lycaphe8x
Date: December 17, 2014 05:18PM
Given the following sorted integers: 1 2 3. How would you construct a balanced search tree?
a problem when the tree is expanding the number of itemset is always concentrated in the first branch (red arrow)
The first branch is always more the number of items than others, the branch in the back as they expand the number of samples less
How to balance the branches to each other
I would really appreciate if somebody could explain for me.
Edited 2 time(s). Last edit at 12/17/2014 09:34PM by lycaphe8x.
a problem when the tree is expanding the number of itemset is always concentrated in the first branch (red arrow)
The first branch is always more the number of items than others, the branch in the back as they expand the number of samples less
How to balance the branches to each other
I would really appreciate if somebody could explain for me.
Edited 2 time(s). Last edit at 12/17/2014 09:34PM by lycaphe8x.
Re: how to balance the expanded tree
Posted by:
webmasterphilfv
Date: December 17, 2014 11:20PM
It is true that some branches have more nodes than others in the search tree. This may be a problem if you are doing a depth-first search.
There is a solution that is used in the Eclat algorithm and other depth-first algorithms for pattern mining. It is to first sort items by the order of increasing support instead of using the alphabetical order. For example, in your example, the items 1,2,3,4,5.. would be sorted from the most rare item to the most frequent item.
By doing this, most nodes in the leftmost branches would be infrequent and would be pruned during the search, and more nodes in the rightmost branches would be frequent and would not be pruned during the search. Thus, it helps to balance the search tree.
Hope this helps,
Philippe
Edited 1 time(s). Last edit at 12/17/2014 11:28PM by webmasterphilfv.
There is a solution that is used in the Eclat algorithm and other depth-first algorithms for pattern mining. It is to first sort items by the order of increasing support instead of using the alphabetical order. For example, in your example, the items 1,2,3,4,5.. would be sorted from the most rare item to the most frequent item.
By doing this, most nodes in the leftmost branches would be infrequent and would be pruned during the search, and more nodes in the rightmost branches would be frequent and would not be pruned during the search. Thus, it helps to balance the search tree.
Hope this helps,
Philippe
Edited 1 time(s). Last edit at 12/17/2014 11:28PM by webmasterphilfv.
Re: how to balance the expanded tree
Posted by:
lycaphe8x
Date: December 19, 2014 04:10PM
Thank you a lot, it's very helpful