Parallel Data Mining and Warehousing on Large Transactional Dataset

Significant Achievements, Anticipated Outcomes and Future Work

The project this year looked into the feasibility of parallel data mining techniques using MILP (mixed integer linear programming).  To be more specific it used real-life transactional data from a Belgian supermarket retailer.  It proved that these techniques are feasible to be run on the super-cluster for small to medium problems.  For large problems i.e. problems in integer programming that are likely to traverse many nodes it may still be infeasible to solve using the existing configuration and resources and will need further investigation.

We have also published a chapter in a Springer-Verlag publication on data mining using MILP techniques.

Data Sources, Curation Techniques, Data Access Policy and Method

None

Computational Techniques Used

To solve the problem of data mining optimal item packages using MILP techniques CPLEX package from ILOG was used. This was installed on the APAC-AC for evaluation purpose.

Method:

Following is an integer linear programming model for the OIPP. Let y_i denote the 0-1 decision variable that assumes value 1 when ever item i is chosen. Let z_j denote the 0-1 decision variable that assumes value 1 whenever the frequent item set X_j is covered by the set of selected items, that is, by the set of items { i: y_i = 1}.

(6) Lower and upper bound constraints: N_L ≤ ≤ N_U.

(7) Occurrence constraint of X_j: -n_j z_j ≥ 0, 1≤j≤k

(8) Storage space constraint: ≤S.

(9) Lower bound constraint on profit: ≥Minprofit

(10) Restrictions on variables: y_i = 0 or 1, z_t = 0 or 1.

(11) Objective function: Maximize - .

In this value based frequent item set problem the input information regarding X₁,..., X_k , p_j, f_j , s_i and c_i must be extracted through data mining of frequent item sets.

For the above model (6)-(11), the constraints and the objective function may be validated as follows:

Let the set of selected items to cover all the selected frequent item sets be denoted by = { i: y_i = 1}. It is easy to see that | | = and the constraint (6) provides the lower and upper bound restrictions on this number. The number of items common to the set and the frequent item set X_j is given by . Whenever = |X_j| = n_j , the set covers the frequent item set X_j . The constraint (7) ensures that the decision variable z_j is 1 if and only if the frequent item set X_j covered by . In this case note that F = { X_j : z_j = 1} is the collection of frequent item sets selected. The storage space required by the items of the selected set is . The constraint (8) expresses the upper bound restriction on the available storage space. The contribution made by the frequent item set X_j to the profit may be expressed as p_jf_j z_j where z_j =1 if and only if X_j is covered by the set . The constraint (9) ensures a minimum revenue contribution from the set of all covered frequent item sets. The constraints of (10) express the 0-1 restrictions of the decision variables y_i and z_j. The objective function in (11) maximizes the total profit contribution expressed as the total net revenue.

Publications, Awards and External Funding

External Funding and Awards

None

Publications

N. R. Achuthan, R. Gopalan, & A. Rudra, Mining Value-Based Item Packages - An Integer Programming Approach in Data Mining, G.J. Williams and S.J. Simoff (Eds.): Data Mining, LNAI 3755, 2006, pp. 78 – 89. © Springer-Verlag Berlin Heidelberg.