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

they can be used in the decision making process of the enterprise. For example, the
management of a supermarket could be interested in identifying combinations of items
that generate the maximum profit and requires physical storage space within certain
limits. Another example is finding association rules where the items are most profitable
or have the lowest margin.
Many such real-world problems can be expressed as optimization problems that
maximize or minimize a real valued function. In this paper, we will focus on one such
optimization problem in the context of transaction data and refer to it as value based
frequent item packages problem . A package consists of items that are usually sold
together. The aim is to find a set of items that can be sold as part of various packages
to realize the maximum profit overall for the business.
Data mining research in the last decade has produced several efficient algorithms
for association rule mining [3] [4] [5], with potential applications in financial data
analysis, retail industry, telecommunications industry, and biomedical data analysis.
However, literature on the use of these algorithms to solve real-world problems is
limited [2]. Ali et al [6] reported the application of association rules to reducing fall-
out in the processing of telecommunication service orders. They also used the
technique to study associations between medical tests on patients. Viveros et al [7]
applied data mining to health insurance data to discover unexpected relationships
between services provided by physicians and to detect overpayments.
Most of the data mining algorithms developed for transaction data give equal
importance for all the items. However, in a real business, not all the items are of equal
value and many management decisions are made based on the money value associated
with the items. The value may be in terms of the profit made or cost incurred or any
other utility function defined on the items. Recent works by Aumann and Lindel [18]
and Webb [17] discuss the quantitative aspects of association rules and tackle the
problem using a rule based approach. More recently, Brij et al [2] developed a zero-
one mathematical programming model for determining a subset of frequent item sets
that account for total maximum profit from a pre-specified collection of frequent item
sets with certain restrictions on the items selected. They used this model for the
market basket analysis of a supermarket. Demiriz and Bennett [8] have successfully
used similar optimization approaches for semi-supervised learning.
Mathematical programming has been applied as the basis for developing some of the
traditional techniques of data mining such as classification, feature selection, support
vector machines, and regression [9] [8]. However, these techniques do not address the
value based business decision problems arising in the context of data mining and
knowledge discovery. To the best of our knowledge, except for [2], mathematical
modeling approach to classes of real world decision problems that integrate patterns
discovered by data mining has not been reported so far. In this paper, we address this
relatively unexplored research area and propose a new mathematical model for some
classes of the value based frequent item packages problem. We contend that frequently
occurring and profitable baskets are of greater importance to the retailer than just
frequent subsets of transactions. The items that occur in a transaction can be packaged
together or alternatively sold as individual items. We consider the expected minimum
revenue, minimum and maximum number of items in the optimal item packages, and
storage constraint pertinent to a real life retailer.