Mining Frequent Patterns with Multiple Item Support Thresholds in Tourism Information Databases - Technologies and Applications of Artificial Intelligence - page 93

3 Algorithm

The proposed approach is an improvement over CFP-growth++ algorithm proposed in
[6]. The basic concepts of the algorithm can be decomposed into three stages: (1)
construction of MIS-tree (2) generating compact MIS-tree and (3) mining frequent
patterns from the compact MIS-tree.
A detailed description of the algorithm is given in Algorithm 1 and Algorithm 2.
First, we construct MIS-tree. The MIS-tree consists of two components: prefix-tree
structure and MIS header table. The prefix-tree structure is similar to FP-tree structure
[4]. The difference is that items in the MIS-tree are ordered in descending order ac-
cording to their MIS values. Each entry in the MIS header table consists of three
fields: item, the MIS value of each item, and head of node link which point to the first
node in the MIS-tree with that item. The following example is used to illustrate the
MIS-tree construction process.

Fig. 2. Initial MIS-tree

Example 2. Following the example above, let us consider the database shown in
Table 1. The MIS value of each item is shown in the MIS header table in Fig. 2,
which is computed by using equation 3. According to Algorithm 1, the items in each
transaction ( see the third column in Table 1) and the order of item list in MIS header
table are arranged in decreasing order according to their MIS value.
Next, a MIS-tree is created as follows. First, the root node is created. Then, the
scan of the first transaction leads to the construction of the first branch of the tree with
four nodes <21*:1>, <111:1>, <211:1> and <121:1>. The second transaction contain-
ing the items '111', '22*', '221' '123' will result in a branch where '111' is linked to
root node, '22*' is linked to '111', '221' is linked to '22*' and '123' is linked to
'221'. The remaining transactions in TDB can be done in the same way. To facilitate
tree traversal, a MIS header table is built in which each item points to its occurrences
in the MIS-tree via the head of node link. Moreover, nodes with the same item are