Set enumeration trees (SE-trees) can be very useful in machine learning and data mining applications. We'll begin to cover some of the basics of these trees today, and go into more detail about their structure, traversal, and uses later.
1. Background
Binary trees were first proposed in the 1950’s as a search
methodology to locate one piece of data from within a large dataset quickly and
efficiently. During the 1960’s formal
proofs were developed to substantiate theorems and algorithms associated with
these search trees. The 1970’s brought
forth a proliferation of various mutated tree types to solve unique search
problems associated with more complex data structures. Within this same period of time trees, along
with lists, stacks, and queues, became the basic data structure building blocks
of the rapidly growing computer science field.
After several false starts, the 1980’s saw resurgence in the field of
artificial intelligence. Data mining
began to take shape and evolve with the advent of decision trees.
In 1990 a formal definition was developed for a unary
predicate set operator which produced what was termed an enumerated set (Trybulec 1990) . This enumerated set was also known as a power
set P(A) of set A in the
domain of mathematics. In 1992 a tree
structure was proposed based upon this enumerated set. This structure was named the set enumeration tree, or SE-tree (Rymon 1992). The SE-tree, or one of its fundamental
equivalents (i.e. lexicographic tree, search space lattice, prefix tree, trie),
has become the standard for search itemset identification in the field of
associative rule mining since its introduction.
If a set was composed of the elements {1,2,3,4},
then the resulting enumerated set would be as shown in Figure 1.
Figure 1
Enumerated set for
{1,2,3,4}
2.
Implementation
2.1.
Tree
Structure
There are two features that must be implemented in a general
tree structure which will be used to form a set enumerated tree. These features differentiate the general tree
from a binary search tree structure.
First, any parent node must be able to accommodate k number of child nodes (siblings).
A binary search tree has at most two child nodes for each parent
node. Second, any node must be able to
represent a set of data containing m
number of elements. A binary search tree
holds only one data element per node, with each element placed in a particular position
(or ordered) within the binary search tree depending on the element’s value.
Figure 2 represents the conceptual model of a general tree
structure which satisfies the requirements for a set enumerated tree of the set
{1,2,3}.
The root node of a set
enumerated tree is always a null value, or empty set. The tree consists of two node types. The first node is the member node, which contains the actual set member values (the
braces are not included in any of the member nodes; they are just in the
diagrams to help define where a particular set begins and ends). If there is more than one member in a
particular set, then member nodes can be linked together through the next member pointer to represent each
additional set member. The second node
type is a child node. If a member node set has any child sets, then
the first member node of the parent set will be linked to a child node through
the first child pointer. The child node then will be linked to the
first member of the child set of data through the first member pointer. If a
parent set has more than one child set, additional child nodes can be linked
together through the next child pointer
for each additional child set.
Figure 2 Tree structure
for enumerated set {1,2,3}
2.2.
Node Structure
In order to simplify data structures and recursive
algorithms, it was decided to define a universal node structure which would
satisfy the needs of both a member node structure and a child node
structure. A block diagram of this
universal node structure is shown in Figure
3. The role of
the universal node structure is determined by the state of isChildNode. If isChildNode
is set to true, the universal node represents a child node. Conversely, if isChildNode is false, the universal node
represents a member node.
Figure 3
Universal Node Structure
When configured as a member node, the active variables of
the universal node structure are member,
level, *firstChild, and *nextMember. The member
variable contains the actual member value at this particular location within a
set. The level variable holds the depth within the set enumeration tree at
which this set member resides. This
variable and its usefulness will be discussed in more detail later. The *firstChild
variable is a pointer type which references the location of the first child
node if this member node has any children.
If this member node has no children (a leaf node), then the value of *firstChild is null. The *nextMember
variable is a pointer type which references the location of the next member of
a set, if one exists. If this member
node is the last or only member of the set, then the value of *nextMember is null.
When configured as a child node, the active variables of the
universal node structure are *firstMember,
and *nextChild. The *firstMember
variable is a pointer type which references the location of the first member
node of the set associated with this child node. The *nextChild
variable is a pointer type which references the location of the next child node,
if one exists. If this child node is the
last or only child set, then the value of *nextChild
is null.
2.3 Code Structure
2.3.1 Universal Node Structure Class:
typedef
int setType; //configure type of set here
class universalNode
{
public:
universalNode(void);
~universalNode(void);
private:
setType
member;
bool
isChildNode;
int level;
universalNode * firstChild;
universalNode * nextMember;
universalNode * firstMember;
universalNode * nextChild;
// for a doubly-linked structure, uncomment
the following items:
//universalNode *
backMemberFromMember;
//universalNode *
backChildFromMember;
//universalNode *
backMemberFromChild;
//universalNode *
backChildFromChild;
friend class SETree;
};
2.3.1 Universal Node Constructor:
universalNode::universalNode(void)
{
member = NULL;
level = 0;
isChildNode = false;
firstChild = NULL;
nextMember = NULL;
firstMember = NULL;
nextChild = NULL;
// for a doubly-linked structure, uncomment
the following items:
//backMemberFromMember
= NULL;
//backChildFromMember
= NULL;
//backMemberFromChild
= NULL;
//backChildFromChild
= NULL;
}
2.3.1 Set Enumeration Interface:
typedef int * arrayPtr;
class SETree
{
public:
SETree(void);
~SETree(void);
SETree(const
setType memberList[],const int size);
universalNode * buildTree(const setType memberList[],const
int size);
int
getLevelCount(universalNode *& setPtr);
int
getNodeCount(universalNode *& setPrt);
arrayPtr * getSearchArray(universalNode
*& setPtr, int & arrayDepth, int & arrayWidth);
arrayPtr *
getReverseSearchArray(universalNode *& setPtr, int
& arrayDepth, int & arrayWidth);
arrayPtr *
getLevelSearchArray(universalNode *& setPtr, const
int level, int
& arrayDepth, int & arrayWidth);
private:
universalNode *head;
universalNode *child;
void
addMember(universalNode *setPtr, const setType
newMember, int & currentLevel);
void
addNewChildSet(universalNode *setPtr,const
setType newMember, int & currentLevel);
universalNode *copySet(universalNode
*setPtr, universalNode *& lastPtr, int
& currentLevel);
int
traverseChildren(universalNode *setPtr);
void
getLevels(universalNode *setPtr);
void
getNodes(universalNode *setPtr);
void
searchTraverse(universalNode *setPtr, arrayPtr * searchArray, int searchLevel, int
& arrayCount);
void
searchCopy(universalNode *setPtr, arrayPtr * searchArray, int & arrayCount);
int
nCombinationR(int n, int
r);
int
factorial(int n);
int levels;
int nodes;
int
maxSize;
};
References:
Rymon, R. (1992). Search through
systematic set enumeration. Proceedings of the International Conference on
Principles of Knowledge Representation and Reasoning, Cambridge, MA, Morgan
Kauffman.
Trybulec, A. (1990). "Enumerated sets." Formalized
Mathematics Volume 1(1): 25--34.
