Mining Value-Based Item Packages – An Integer Programming Approach - Data Mining: Theory, Methodology, Techniques, and Applications - page 78

Mining Value-Based Item Packages - An Integer
Programming Approach
N.R. Achuthan 1 , Raj P. Gopalan 2 , and Amit Rudra 3
1 Department of Mathematics and Statistics,
Curtin University of Technology, Kent St, Bentley WA 6102, Australia
[e-mail]
2 Department of Computing, Curtin University of Technology,
Kent St, Bentley WA 6102, Australia
[e-mail]
3 School of Information Systems,
Curtin University of Technology, Kent St, Bentley WA 6102, Australia
[e-mail]
Abstract. Traditional methods for discovering frequent patterns from large
databases assume equal weights for all items of the database. In the real world,
managerial decisions are based on economic values attached to the item sets. In
this paper, we first introduce the concept of the value based frequent item
packages problems. Then we provide an integer linear programming (ILP) model
for value based optimization problems in the context of transaction data. The
specific problem discussed in this paper is to find an optimal set of item packages
(or item sets making up the whole transaction) that returns maximum profit to the
organization under some limited resources. The specification of this problem
allows us to solve a number of practical decision problems, by applying the
existing and new ILP solution techniques. The model has been implemented and
tested with real life retail data. The test results are reported in the paper.
1 Introduction
As organizations accumulate vast amounts of data from day to day operations, the
prospect of finding hidden nuggets of knowledge has greatly increased [19]. Traditional
inventory systems help a retailer keep track of items in stock and to replenish specific
items as they fall below certain levels. The issue these days is not just replenishing the
stock on the shelves but also grouping them according to their perceived association
with items that attract the attention of customers. Using past sales data, the associations
among frequent items can be determined efficiently by current algorithms. The methods
for finding the frequent patterns involve different types of partial enumeration schemes
where all items are given equal importance. However, in most business environments,
items are associated with varying values of price, cost, and profit. So, the relative
importance of items differs significantly. Kleinberg et al. [1] noted that frequent
patterns and association rules extracted from real life data would be of use to business
organizations only if they solve problems in the microeconomic context of the business.
Brijs et al. [2] suggest that patterns in the data are interesting only to the extent to which