Mathematical Programming in Data Mining.
Mathematical programming approaches to three fundamental problems will be described: feature selection, clustering and robust representation. The feature selection problem considered is that of discriminating between two sets while recognizing irrelevant and redundant features and suppressing them. This creates a lean model that often generalizes better to new unseen data. Computational results on real data confirm improved generalization of leaner models. Clustering is exemplified by the unsupervised learning of patterns and clusters that may exist in a given database and is a useful tool for knowledge discovery in databases (KDD). A mathematical programming formulation of this problem is proposed that is theoretically justifiable and computationally implementable in a finite number of steps. A resulting k-Median Algorithm is utilized to discover very useful survival curves for breast cancer patients from a medical database. Robust representation is concerned with minimizing trained model degradation when applied to new problems. A novel approach is proposed that purposely tolerates a small error in the training process in order to avoid overfitting data that may contain errors. Examples of applications of these concepts are given.
Introduction
Mathematical programming, that is optimization subject to constraints, is a broad discipline that
has been applied to a great variety of theoretical and applied problems such as operations research
[29, 54], network problems [60, 53], game theory and economics [71, 35], engineering mechanics
[57, 37] and more recently to machine learning [3, 61, 23, 48, 46]. In this paper we describe three
recent mathematical-programming-based developments that are relevant to data mining: feature
selection [45, 10], clustering [11] and robust representation [67]. We note at the outset that we
do not plan to survey either the fields of data mining or mathematical programming, but rather
highlight some recent and highly effective applications of the latter to the former. We will, however,
point out other approaches that are mostly not based on mathematical programming.
The fundamental nonlinear programming problem [6, 44] consists of minimizing an objective
function subject to inequality and equality constraints and is typically written as follows
f(x) subject to g(x) - 0;
where x is an n-dimensional vector of real variables, f is a real-valued function of x, g and h
are finite dimensional vector functions of x. If all the functions f , g and h are linear then the
problem simplifies to a linear program [15, 52, 69] which is the classical problem of mathematical
Mathematical Programming Technical Report 96-05, August 1996 - Revised November 1996 & March 1997. This
material is based on research supported by National Science Foundation Grant CCR-9322479.
y Computer Sciences Department, University of Wisconsin, 1210 West Dayton Street, Madison, WI 53706, email:
programming. If x is two-dimensional, a linear program can be thought of as the problem of finding
a lowest point (not necessarily unique) on a tilted plane surrounded by a piecewise-linear fence.
Extremely efficient algorithms exist for the solution of linear programs. Thus reducing a problem
to a single or finite sequence of linear programs is tantamount to solving the problem.
Another reason for emphasizing mathematical programming in this work is the very broad
applicability of the optimization-under-constraints paradigm. A great variety of problems from
many fields can be formulated and effectively solved as mathematical programs. According to the
great eighteenth century mathematician Leonhard Euler: "Nothing happens in the universe that
does not have a sense of either certain maximum or minimum" [68, p 1]. From the point of view
of applicability to large-scale data mining problems, the proposed algorithms employ either linear
programming (Sections 2 and 3) which is polynomial-time-solvable [36, 69], or convex quadratic
programming (Section 4) which is also polynomial-time-solvable [69]. Extremely fast linear and
quadratic programming codes [14] that are capable of solving linear programs with millions of
variables [8, 40] and very large quadratic programs, make the proposed algorithms easily scalable
and effective for solving a wide range of problems. One limitation however is that the problem
features must be real numbers or easily mapped into real numbers. If some of the features are
discrete and can be represented as integers, then the techniques of integer programming [24, 55, 14]
can be employed. Integer programming approaches have been applied for example to clustering
problems [64, 1], but will not be described here, principally because the combinatorial approach is
fundamentally different than the analytical approach of optimization with real variables. Stochastic
optimization methods based on simulated annealing have also been used in problems of inductive
concept learning [50].
The problems considered in this paper are:
1. Feature Selection The feature selection problem treated is that of discriminating between
two finite point sets in n-dimensional feature space by a separating plane that utilizes as few
of the features as possible. The problem is formulated as a mathematical program with a
parametric objective function and linear constraints [10]. A step function that appears in
the objective function is approximated by a concave exponential on the nonnegative real line
instead of the conventional sigmoid function of neural networks [28]. This leads to a very fast
iterative linear-programming-based algorithm for solving the problem that terminates in a
finite number of steps. On the Wisconsin Prognosis Breast Cancer (WPBC) [72, 51] database
the proposed algorithm reduced cross-validation error on a cancer prognosis database by
while reducing problem features from to 4.
2. Clustering The clustering problem considered in this paper is that of assigning m points
in the n-dimensional real space R n to k clusters. The problem is formulated as that of
determining k centers in R n such that the sum of distances of each point to the nearest
center is minimized. Once the cluster centers are determined by a training set, a new point
is assigned to the cluster with the nearest cluster center. If a polyhedral distance (such
as the 1-norm distance) is used, the problem can be formulated as that of minimizing a
piecewise-linear concave function on a polyhedral set which is shown to be equivalent to a
bilinear program: minimizing the product of two linear functions on a set determined by
satisfying a system of linear inequalities [11]. Although a bilinear program is a nonconvex
optimization problem (i.e. minimizing a function that is not valley-like), a fast finite k-Median
Algorithm consisting of solving few linear programs in closed form leads to a stationary point.
Computational testing of this algorithm as a KDD tool [18] has been quite encouraging. On
the Wisconsin Prognosis Breast Cancer Database (WPBC), distinct and clinically important
survival curves were discovered from the database by the k-Median Algorithm, whereas the
traditional k-Mean Algorithm [32, 64], which uses the square of the 2-norm distance, thus
emphasizing outliers, failed to obtain such distinct survival curves for the same database. On
four other publicly available databases each of the k-Median and k-Mean Algorithms did best
on two of the databases.
3. Robust Representation This problem deals with modeling a system of relations within a
database in a manner that preserves, to the extent possible, the validity of the representation
when the data on which the model is based changes. This problem is closely related to the
generalization problem of machine learning of how to train a system on a given training set
so as to improve generalization on a new unseen testing set [39, 63, 73]. We use here a simple
linear model [67] and will show that if a sufficiently small error - is purposely tolerated in
constructing the model, then for a broad class of perturbations the model will be a more
accurate representation than one obtained by a conventional zero error tolerance. A simple
example demonstrates this result.
1.1 Notation
We summarize below notation and background material used in this paper.
ffl All vectors will be column vectors unless transposed to a row vector by a superscript T .
ffl For a vector x in the n-dimensional real space R n , jxj will denote a vector of absolute values
of components x of x.
ffl The base of the natural logarithm will be denoted by ", and for y \Gammay will denote a
vector in R m with component " \Gammay
ffl For x 1, the norm kxk p will denote the p-norm, that is (
.
ffl The notation A 2 R m\Thetan will signify a real m \Theta n matrix. For such a matrix, A T will denote the
transpose, A i will denote row i and A I will denote those rows A i such that i 2 I ae
for a given subset I of
ffl A vector of ones in a real space of arbitrary dimension will be denoted by e. A vector of zeros
in a real space of arbitrary dimension will be denoted by 0.
ffl If x and y are vectors in R n , the notation minfx; yg will denote the vector in R n of componentwise
minimum of x i and y i ,
ffl The notation arg min
f(x) will denote the set of minimizers of f(x) on the set S. Similarly
arg vertex min
f(x) will denote the set of vertex minimizers of f(x) on a polyhedral set S.
ffl A polyhedral set S in R n is the the intersection of a finite number of closed halfspaces in R n .
ffl A vertex of a polyhedral set S is a boundary point of S that lies on the intersection of n
linearly independent planes constituting the boundary. Typically
is a vertex of S if for some subset I of
A I I and A I 2 R n\Thetan is nonsingular.
ffl A separating plane, with respect to two given point sets A and B in R n , is a plane that
attempts to separate R n into two halfspaces such that each open halfspace contains points
mostly of A or B:
ffl Alternatively, a separating plane can be interpreted as a classical perceptron [62, 43] with a
threshold determined by the distance of the plane to the origin, and the incoming arc weights
of the perceptron determined by the components of the normal vector to the plane.
Feature Selection
Feature selection (or extraction) attempts to use the simplest model to describe the essence of a
phenomenon. Hence it can be considered as an application of Occam's ``law of parsimony'', also
known as Occam's Razor [65, 9], which states: "What can be done with fewer [assumptions] is done
in vain with more". There are statistical [22], machine learning [39, 33] as well as mathematical
programming [12, 45, 10] approaches to the feature selection problem. In this work we shall deal
principally with the latter because of the novelty of the approach and it effectiveness.
The problem that we shall address is the binary classification problem, i.e. the problem of
discriminating between two given point sets A and B in the n-dimensional real space R n by using
as few of the n dimensions of the space as possible. For example in the medical application
described at the end of this section, we attempt to discriminate, with as few of the features as
possible, between breast cancer patients that had a recurrence of the disease within two years of
diagnosis and those who had not. The model that we shall adopt will be that of a perceptron or
linear threshold unit (LTU) that employs as few of the features of the given problem as possible.
Extensions to more complex models leading to compact and accurate decision trees have also been
made [12]. Geometrically our approach corresponds to constructing a plane in R n defined by
with normal w 2 R n and distance jflj
to the origin, while suppressing as many of the components
of w as possible. In addition, the set A must lie, to the extent possible, in the open halfspace
and the set B in the open halfspace
This corresponds to an LTU with a threshold fl and and incoming arc weights w 2 R n , with as
many of the weights as possible set to zero. If we represent the set A by the matrix A 2 R m\Thetan and
the set B by the matrix B 2 R k\Thetan , then the problem is to find fl 2 R and w 2 R n , with as many
components equal to zero as possible, such that the following inequalities are satisfied in some best
sense:
where e is a vector of ones. Because linear programming cannot handle strict inequality constraints
we rescale (5) as follows. We divide the variables (w; fl) by the positive quantity
min
and call the rescaled variables (with notational economy in mind and a slight abuse of notation)
(w; fl) again, then (5) is equivalent to:
e: (6)
Since these inequalities may not have a solution in general, one resorts to satisfying them in some
best approximate sense by minimizing an average sum of their violations. This leads to the following
Robust Linear Programming formulation [4]:
RLP min
w;fl;y;z
Robustness here refers to the fact that the useless null vector (w = 0) is naturally excluded as
a solution of (7), which is not the case in other linear programming formulations of this problem
[41, 66, 26, 25]. Note that because of the constraints of the problem, the variables y and z will
satisfy the following conditions:
Hence minimizing e T
will force the satisfaction in some best sense of (6), and equivalently
(5), by minimizing the average violations of (6):m
which will be zero if and only if (6), or equivalently (5), is exactly satisfied. The linear programming
formulation (7) which has a number of natural theoretical properties including robustness is also
very effective computationally [4, 49]. However it does not address the problem of suppressing
irrelevant features. In order suppress such features, the objective function of (7), which merely
measures the average sum of the violations of the inequalities (6), is modified so as to also suppress
as many of the components of the weight vector w as possible. This is achieved by weighting the
original objective of (7) by weighting by - an exponential function
approximation of the absolute value v of the weight vector w. This exponential function, e T
approximates the 1-norm of a step function of v and leads to the following mathematical
program with a concave objective function and linear constraints:(Feature Selection Concave)
the problem degenerates to the robust (that is w 6= linear program of (7) which
obtains a plane P (2) that separates the sets A and B in an optimal fashion without regard to
feature suppression. When - ? 0, then in addition to the objective of separating A and B, we
attempt to suppress as many of the components of w as possible by minimizing an exponential
smoothing of the step function on the nonnegative real line for each
where " is the base of the natural logarithms, and v is the absolute value of w. In most our
applications a value of sufficient to make the exponential a good approximation of
the step function to force suppression of unnecessary components of w. As described below in
Algorithm 2.1 the parameter - is chosen to give the best cross-validated error. For small values
of - it can be shown theoretically [47] that the minimization problem (8) picks that solution of
the Robust Linear Program (7) that minimizes the exponential term of (8), and hence solves the
RLP (7) while suppressing redundant components of w. Because the objective function of (8) is
a concave function bounded below by zero on the nonempty polyhedral set of (8), it follows that
it has a vertex solution if the feasible region does not contain lines extending to infinity in both
directions [59, Corollaries 32.3.3, 32.3.4]. (Excluding such lines can be readily accomplished by a
simple transformation of the variables (w; fl) into the nonnegative variables (w 1 using the
standard transformation . For the sake of simplicity and because it is
not needed computationally, we shall forgo this transformation here.) A fast, finitely-terminating
successive linear programming algorithm has been proposed for solving this problem [10] as follows.
Algorithm 2.1 Successive Linearization Algorithm (SLA) for FSV (8). Choose - 2 [0; 1).
Start with a random (w Having (w determine the next iterate by
solving the linear program:
(w
Stop when
(v
Comment: The parameter ff was set to 5. The parameter - was chosen in the set f0, 0.05,
with the desired - being the one achieving the best cross-validated separation.
It has been shown [45, Theorem 4.2] that this algorithm terminates in a finite number of steps,
typically five or six, at a global solution or a stationary point satisfying a necessary optimality
condition.
This algorithm was tested on the 32-feature Wisconsin Prognostic Breast Cancer (WPBC)
database [72, 51] which was collected from 28 patients for which cancer recurred within two years,
and 119 patients for which cancer did not recur within two years. Thus in the terminology of our
formulation 28 and 118. For this problem the separating plane obtained
by the Successive Linearization Algorithm 2.1 with used only 4 features out of 32, while
increasing tenfold cross-validation correctness by 35.4% [10]. If other values of the parameter - are
used in the Successive Linearization Algorithm 2.1, then the number of features that determine the
separating plane will vary between 1 and 32. The effect of using a different number of features is
shown in Figure 1 which shows a plot of tenfold cross-validation correctness corresponding to the
number of features used. As just indicated, Figure 1 shows that the best tenfold correctness occurs
at four features.
Number of Nonzero Elements of w
Test
Correctness

Figure

1: Feature Selection in the Prognosis Problem: Tenfold cross-validation correctness versus
number of features selected by the Successive Linearization Algorithm 2.1
3 Clustering via Mathematical Programming
The unsupervised assignment of elements of a given set into groups or clusters of like points, is
the objective of cluster analysis. There are many approaches to this problem, including statistical
[32], machine learning [20], integer and mathematical programming approaches [64, 1, 58, 11]. We
shall describe here the recent approach of [11] that utilizes a fast bilinear programming
minimizing the product of two linear functions on a set defined by linear inequalities. A principal
motivation behind our mathematical programming approach is a precise and concise statement of
the clustering problem as a concave minimization problem (11) which has not been given before. We
note that a concave minimization problem which involves minimizing a concave function (mountain-
like function) on a polyhedral set S is more difficult than minimizing a convex function (valley-like
function) on S because the former may have many local minima at vertices of S that are not
global minima, whereas for the latter each local minimum is a global minimum. Nevertheless for
our clustering application the concave formulation is very effective in discovering well separated
survival curves by determining k cluster centers such that the sum of the 1-norm distances of each
point in a given database to the nearest cluster center is minimized. A new point is then assigned
to the cluster with center nearest to the point. This simple formulation can be restated as a bilinear
program (12) that leads to a fast k-Median Algorithm 3.1. A reformulation of (11) using the square
of the 2-norm instead of the 1-norm, leads to the k-Mean Algorithm [32, 64]. Although it is not
the intention here to carry out a detailed comparative study of these two clustering algorithms,
the k-Median Algorithm, as described below, does give well separated survival curves for breast
cancer patients whereas the k-Mean algorithm does not. On four other publicly available databases,
each of the k-Median and k-Mean Algorithms did best on two of the databases. This indicates the
potential of the k-Median Algorithm as a KDD tool. We describe the mathematical programming
approach now.
For a given set A of m points in R n represented by the matrix A 2 R m\Thetan and a number k
of desired clusters, we formulate the clustering problem as follows. Find cluster centers C
such that the sum of the minima over ' 2 of the 1-norm distance between
each point A and the cluster centers C specifically
we need to solve the following mathematical program:
minimize
C;D
min
subject to \GammaD i' - A T
Here D i' 2 R n , is a dummy variable that bounds the components of the difference A T
between point A T
i and center C ' , and e is an n \Theta 1 vector of ones in R n . Hence e T D i' bounds
the 1-norm distance between A i and C ' . We note that just as in the case of robust regression
[31],[27, pp 82-87], the use of the 1-norm here to measure the error criterion leads to insensitivity
to outliers such as those resulting from distributions with pronounced tails. We also note that
since the objective function of (11) is the minimum of k linear (and hence concave) functions, it
is a piecewise-linear concave function [44, Corollary 4.1.14]. This is not the case for the 2-norm or
p-norm, p 6= 1. Although (11) is NP-hard, it can be reformulated as the following bilinear program
which can be solved effectively by using a k-Median Algorithm that consists of solving a succession
of simple linear programs in closed form. We state the bilinear programming formulation and
k-Median Algorithm for solving the clustering problem.
Proposition 3.1 Clustering as a Bilinear Program The clustering problem (11) is equivalent
to the following bilinear program:
minimize
subject to \GammaD i' - A T
This essentially obvious result [11, Proposition 2.2] can be seen from the fact that, for a fixed i,
setting all the components of T i' equal to zero except one corresponding to a smallest
e T D i' , with respect to ', equal to 1, leads to the objective function of (11) from that of (12). Note
that the constraints of (12) are uncoupled in the variables (C; D) and the variable T . Hence the
Uncoupled Bilinear Program Algorithm UBPA [5, Algorithm 2.1] is applicable. Simply stated, this
algorithm alternates between solving a linear program in the variable T and a linear program in the
variables (C; D). The algorithm terminates in a finite number of iterations at a stationary point
satisfying the minimum principle necessary optimality condition for problem (12) [5, Theorem 2.1].
We note however, because of the simple structure the bilinear program (12), the two linear programs
can be solved explicitly in closed form. This leads to the following algorithmic implementation.
Algorithm 3.1 k-Median Algorithm Given the cluster centers C j
k at iteration j, compute
k by the following two steps:
(a) Cluster Assignment: For each A T
determine '(i) such that C j
'(i) is closest to
A T
i in the one norm.
(b) Cluster Center Update: For choose C j+1
' as a median of all A T
i assigned to
Stop when C j+1
' . Assign each point to a cluster whose center is closest in the 1-norm to the
point.
Although the k-Median Algorithm is similar to the k-Mean Algorithm wherein the 2-norm distance
is used [64, 22], it differs from it computationally, and theoretically. In fact, the underlying
problem (12) of the k-Median Algorithm is a concave minimization on a polyhedral set while the
corresponding problem for a two- or p-norm, p 6= 1, is:
minimize
C;D
min
subject to \GammaD i' - A T
This is not a concave minimization on a polyhedral set, because the minimum of a set of convex
functions is not in general concave. We also note that the k-Mean Algorithm finds a stationary
point not of problem (13) with but of the same problem except that kD i' k 2 is replaced
by kD i' k 2
2 and thus favoring outliers. Without this squared distance term, the subproblem of the
k-Mean Algorithm becomes the considerably harder Weber problem [56, 13] which locates a center
in R n closest in sum of Euclidean distances (not their squares!) to a finite set of given points. The
Weber problem has no closed form solution. However, using the mean as a cluster center of points
assigned to the cluster, as done in the k-Mean Algorithm, minimizes the sum of the squares of the
distances from the cluster center to the points.
Because there is no guaranteed way to ensure global optimality of the solution obtained by
either the k-Median or k-Mean Algorithms, different starting points can be used to initiate the
algorithm. Random starting cluster centers or some other heuristic can be used such as placing k
initial centers along the coordinate axes at densest, second densest intervals on the
axes. The latter heuristic was used in our computational results.
To test the effectiveness of the k-Median Algorithm it was used as a KDD tool [18] to mine the
Breast Cancer Database (WPBC) in order to discover medical knowledge. For
such medical databases, extracting well-separated survival curves provides an essential prognostic
tool. Survival curves [34, 38] give expected percent of surviving patients as a function of time. The
k-Median Algorithm was applied to WPBC to extract such curves. Survival curves were constructed
for 194 patients using two clinically available features for each patient: tumor size and number of
cancerous lymph nodes excised. Using the k-Median Algorithm separated the points into
3 clusters. The survival curve for each cluster is depicted in Figure 2(a). The key observation
to make here is that curves are well separated, and hence the clusters can be used as prognostic
indicators to assign a survival curve to a patient depending on the cluster into which the patient
falls. By contrast, the k-Mean Algorithm obtained poorly separated survival curves as shown in

Figure

2(b), and hence are not useful for prognosis.
Another comparison of the k-Median and k-Mean Algorithms was performed on databases with
known classes. Correctness was measured by the ratio of the sum of the number of majority points
in each cluster to the total number of points m in the data set. Table 1 shows results averaged over
ten random starts for four databases from the Irvine repository of databases [51]. We note that for
two of the databases the k-Median gave better correctness than the k-Mean and for the other two
the k-Mean was better.
Months
Percent
Disease-Free
Survival Curves for 3 Clusters Using (Tumor,Lymph) (k-Median)
(a) k-Median
Percent
Disease-Free
Survival Curves for 3 Clusters Using (Tumor,Lymph) (k-Mean)
(b) k-Mean

Figure

2: Survival curves for the 3 clusters of 194 cancer patients obtained by the k-Median and
k-Mean Algorithms
Algorithm # Database ! WDBC Cleveland Votes Star/Galaxy-Bright
Unsupervised k-Median 93.2% 80.6% 84.6% 87.6%
Unsupervised k-Mean 91.1% 83.1% 85.5% 85.6%

Table

1 Training set correctness using the unsupervised k-Median
and k-Mean Algorithms and the supervised Robust LP on four databases
Robust Representation
We consider now the problem of how to generate a robust representation of a system so that the
model remains valid under a class of data perturbation. This problem is closely related to the
generalization problem of machine learning of how to train a system on a given training set so as
to improve generalization on a new unseen testing set [39, 63, 73]. We shall concentrate on some
recent results [67] obtained for a simple linear model and which make essential use of mathematical
programming ideas. These ideas, although rigorously established for a simple linear model here, are
likely to extend to more complex systems. In a somewhat related approach Vapnik has proposed a
quadratic program for constructing a plane to obtain a smallest probability of error for separating
two point sets [70, Section 5.4]. Bennett and Bredensteiner [2] have formulated a similar problem
using linear programming. Vapnik [70, Section 5.9] also makes use of Huber's robust regression
ideas [30] and extends the latter's robust regression loss function [70, p 152] by adding an ffl-
insensitive zone to it. This ffl-insensitive zone is similar to our -tolerance zone (see (17) and (18)
below) wherein errors are disregarded if they fall within the band [\Gamma- ]. Another similarity with
Vapnik's work is the presence of a regularization term fflkxk 2
2 in our minimization (17) problem
(introduced here in order to make the solution unique and to rigorously derive our generalization
theorems) and Vapnik's bounding his weight vector in order to control the VC dimension [70, p 128,
Theorem 5.1]. However, what our approach provides here that is novel, are precise deterministic
conditions (Propositions 4.1 and 4.2 below) under which tolerating a -insensitivity zone will give
better generalization results than the conventional zero-tolerance that is used in an ordinary least
squares approach.
The model that we shall consider here consists of the training set fA; ag where A is a given
m \Theta n real matrix and a is a given m \Theta 1 real vector. A vector x in R n is to be "learned" such that
the linear system
which does not have an exact solution, is satisfied in some approximate fashion, and such that the
error in satisfying
for some unseen testing set (C; c) 2 R k\Thetan \Theta R k , is minimized. Of course, if we disregard the testing
set error (15), the problem becomes the standard least-norm problem:
min
where k\Deltak is some norm on R m . However with an eye to possible perturbations in the given training
set fA; ag, we pose the following motivational question: If the vector a of the training set is known
only to an accuracy of - , where - is some small positive number, does it make sense to attempt
to drive the error to zero as is done in (16), or is it not better to tolerate errors in the satisfaction
of a up to a magnitude of -? In other words, instead of (14), we should try to satisfy the
following system of inequalities, in some best sense:
To do that, we solve the following regularized quadratic program for some nonnegative - and a
small positive ffl:
minimize x;y;z2
2subject to \Gammaz \Gamma e- Ax \Gamma a - e-
Here y and z are the errors in satisfying the inequalities of (17) and ffl is a small fixed positive
regularization constant that ensures the uniqueness of the x component of the solution. Although
ffl was held fixed in our computational experiments, it is possible to optimize its value by cross-validation
on a tuning set in order to obtain better generalization. We note immediately, that if
degenerates to the regularized classical least squares problem:
min
x2R
The key question to ask here, is this: Under what conditions does a solution x(-) of (18), for
some - ? 0 give a smaller error than x(0) on a testing set? We are able to give an answer to
this question and corroborate it computationally [67], by considering a general testing set (C; c) 2
R k\Thetan \Theta R k for the problem (15) as well as a simpler testing set, where only the right side of (14)
is perturbed. We first restrict ourselves to the latter and simpler perturbation, that is:
where p is some arbitrary fixed perturbation in R m , and consider the following associated error
In particular we would like to know when is f(0) not a local minimum of f(-) on the set f- j - 0g.
In fact we are only interested in the -interval [0; - ], where -
- is defined by
because the minimum value of (18) approaches zero, for -
- , as ffl approaches zero. The following
proposition gives a sufficient condition which ensures that solving (18), for some positive - , produces
an x(-) that generalizes better on the system (20) than that obtained by solving a plain regularized
least squares problem (19), that is f(-
Proposition 4.1 Robust Representation of [67]. For a solution x(-)
of (18) the testing set error function f(-) of (21) has a strict local maximum at 0 and a global
minimum on [0; -], where - is defined by (22), at some - ? 0, whenever
for some - 2 (0; ~ - ], for some sufficiently small ~
- .
410121416Tolerance
Test

Figure

3: A computational example of Proposition 4.1. The bottom curve depicts a decreasing
test error f(-) of (21) for the perturbed system (23). The top
curve demonstrates an increasing error effect of violating (23) for sufficiently small ffl.
Computational results carried out in [67] have corroborated the improved generalization results
of Proposition 4.1 above. We depict in Figure 3 a simple numerical example that uses the training
model (14), where the vector x is learned with various error tolerances - (18) and is then tested
on the perturbed system p. In the learning situation depicted by the bottom curve of

Figure

makes an acute angle with in the neighborhood of
Hence, as - increases, the test error in satisfying decreases. In the upper curve, we
show a perturbation for which the angle is reversed: the testing model is using the
same perturbation p. Here the testing error goes up as - increases away from zero.
We conclude this section by extending Proposition 4.1 to a more general testing model
where C 2 R k\Thetan and c 2 R k are chosen arbitrarily. To do this we define a corresponding error
function g(-) to (21) which measures the error in satisfying (24) by the x(-) learned by solving the
regularized quadratic program (18). We thus have the error
ck 2
For this very general formulation we are able to give the following result that tells us when tolerant
training does lead to improved generalization.
Proposition 4.2 Improved generalization with positive tolerance for testing model
Let x(-) be defined by the tolerant training of Ax = a by the regularized quadratic
program (18) with tolerance - 0. Let g(-) denote the error generated by x(-) in the testing model
defined by (25). The zero-tolerance error g(0) is a local maximum of g(-) over the set
f- 0g whenever
where r(-) is the residual vector defined by
Furthermore, the testing set error function g(-) of (25) has a global minimum on [0; -
-], for -
defined by (22), at some - ? 0, whenever condition (26) holds and -
5 Conclusion
A number of ideas based on mathematical programming have been proposed for the solution of
the fundamental problems of feature selection, clustering and robust representation. Examples of
applications of these ideas have been given to show their effectiveness. We discuss now some issues
associated with these approaches.
All the methods here use real variables. Even though the class of problems falling in this
category is quite broad, this requirement imposes a restriction on the type of problems that can
be handled. Nevertheless the proposed methods can be applied to problems with discrete variables
if one is willing to use the techniques of integer and mixed integer programming [55, 21] which
are more difficult. In fact one of the proposed algorithms, the k-Median Algorithm, whose finite
termination is established for problems with real variables, is directly applicable with no change to
problems with ordered discrete variables such as integers. How well it performs on such problems
would be an interesting problem to examine.
Another important practical issue is scalability. As mentioned earlier, since linear programs with
millions of variables can be solved with present day state-of-the-art methods, large-scale databases
are amenable to the proposed linear-programming-based methods. In addition there is a large
body of literature on the parallel solution and decomposition of large scale mathematical programs
[7, 16, 17, 19] where for many of the algorithms only part of the data is loaded into memory at a
time. Such parallel and decomposition algorithms extend further the applicability of the proposed
methods to very large scale databases.
From a numerical standpoint, mathematical programming codes, and especially linear and
quadratic programming codes, are reliable and robust codes that have been in a constant state of
improvement over last fifty years. The well-understood polynomial-time finite termination of linear
and quadratic programming interior methods has led to very powerful and reliable commercial
software such as CPLEX [14] that can easily and reliably implement all the proposed algorithms.
Finally we point out that although a linear model was used for both the feature selection and
robust representation models, nonlinear models that are linear in their parameters, e.g. quadratic
surfaces, can be easily transformed into a linear system, as was done for example in [41] where
quadratic separation was achieved by linear programming. However in some inherently nonlinear
problems where for example the parameters of a separating surface appear nonlinearly, one may
have to resort to nonlinear models and the theory and algorithms of nonlinear programming [42, 6].
This would again be a promising problem to pursue.
We conclude with the hope that the problems solved demonstrate the theoretical and computational
potential of mathematical programming as a versatile and effective tool for solving important
problems in data mining and knowledge discovery in databases.



--R

A Tabu search approach to the clustering problem.
Geometry in learning.
Neural network training via linear programming.
Robust linear programming discrimination of two linearly inseparable sets.
Bilinear separation of two sets in n-space
Nonlinear Programming.
Parallel and Distributed Computation.
Very large-scale linear programming: a case study combining interior point and simplex methods
Occam's razor.
Feature selection via mathematical pro- gramming
Clustering via concave minimization.
Feature minimization within decision trees.
On the Fermat-Weber problem with convex cost functionals
CPLEX Optimization Inc.
Linear Programming and Extensions.
Serial and parallel solution of large scale linear programs by augmented Lagrangian successive overrelaxation.

The KDD process for extracting useful knowledge from volumes of data.
Parallel variable distribution.
Knowledge acquisition via incremental conceptual clustering.
Fundamentals and Applications (Topics in Chemical Engineering.
Statistical Pattern Recognition.
Convergence properties of backpropagation for neural nets via theory of stochastic gradient methods.
Integer Programming.
Improved linear programming models for discriminant analysis.
Mathematical methods for pattern classification.
Fundamentals of Artificial Neural Networks.
Introduction to the Theory of Neural Computation.
Introduction to Operations Research.
Robust estimation of location parameter.
Robust Statistics.
Algorithms for Clustering Data.
Irrelevant features and the subset selection problem.
Nonparametric estimation from incomplete observations.
Mathematical Methods and Theory in Games
A new polynomial time algorithm for linear programming.
Mathematical programming in contact problems.
Survival Analysis.
Optimal brain damage.

Linear and nonlinear separation of patterns by linear programming.
Nonlinear Programming.
Mathematical programming in neural networks.
Nonlinear Programming.
Machine learning via polyhedral concave minimization.
Mathematical programming in machine learning.
Nonlinear perturbation of linear programs.
Serial and parallel backpropagation convergence via nonmonotone perturbed minimization.
Breast cancer diagnosis and prognosis via linear programming.
Combinatorial optimization in inductive concept learning.
UCI repository of machine learning databases.
Linear Programming.
Network Programming.
Operations Research.
John Wiley
A quadratically convergent method for minimizing a sum of euclidean norms.
Inequality Problems in Mechanics and Applications.
analysis and mathematical programming.
Convex Analysis.
Network Flows and Monotropic Optimization.
A polynomial time algorithm for the construction and training of a class of multilayer perceptrons.
Parallel Distributed Processing.
Overfitting avoidance as bias.

Readings in Machine Learning.
Pattern classifier design by linear programming.
Improved generalization via tolerant training.
Foundations of the Theory of Learning Systems.
Linear Programming: Foundations and Extensions.
The Nature of Statistical Learning Theory.
Theory of Games and Economic Behavior.
WPBC: Wisconsin Prognostic Breast Cancer Database.
The Mathematics of Generalization
--TR

--CTR
Bernardete Ribeiro, Learning adaptive kernels for model diagnosis, Design and application of hybrid intelligent systems, IOS Press, Amsterdam, The Netherlands,
M. A. Goberna , V. Jeyakumar , N. Dinh, Dual Characterizations of Set Containments with Strict Convex Inequalities, Journal of Global Optimization, v.34 n.1, p.33-54, January   2006
Sanjeev Arora , Prabhakar Raghavan , Satish Rao, Approximation schemes for Euclidean
Carlotta Orsenigo , Carlo Vercellis, Accurately learning from few examples with a polyhedral classifier, Computational Optimization and Applications, v.38 n.2, p.235-247, November  2007
V. F. Demyanov , A. M. Bagirov , A. M. Rubinov, A method of truncated codifferential with application to some problems of cluster analysis, Journal of Global Optimization, v.23 n.1, p.63-80, May 2002
P. S. Bradley , O. L. Mangasarian , J. B. Rosen, Parsimonious Least Norm Approximation, Computational Optimization and Applications, v.11 n.1, p.5-21, Oct. 1998
scalable decision tree system and its application in pattern recognition and intrusion detection, Decision Support Systems, v.41 n.1, p.112-130, November 2005
Jong-Shi Pang, Guest Editorial, Computational Optimization and Applications, v.13 n.1-3, p.5-12, April 1999
Jong-Shi Pang, Guest Editorial, Computational Optimization and Applications, v.12 n.1-3, p.5-12, Jan. 1999
Tapas Kanungo , David M. Mount , Nathan S. Netanyahu , Christine Piatko , Ruth Silverman , Angela Y. Wu, The analysis of a simple
Gentile, A new approximate maximal margin classification algorithm, The Journal of Machine Learning Research, 2, 3/1/2002
Tapas Kanungo , David M. Mount , Nathan S. Netanyahu , Christine D. Piatko , Ruth Silverman , Angela Y. Wu, An Efficient k-Means Clustering Algorithm: Analysis and Implementation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.7, p.881-892, July 2002
Gunnar Rtsch , Sebastian Mika , Bernhard Schlkopf , Klaus-Robert Mller, Constructing Boosting Algorithms from SVMs: An Application to One-Class Classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.9, p.1184-1199, September 2002
Balaji Padmanabhan , Alexander Tuzhilin, On the Use of Optimization for Data Mining: Theoretical Interactions and eCRM Opportunities, Management Science, v.49 n.10, p.1327-1343, October
Sudipto Guha , Adam Meyerson , Nina Mishra , Rajeev Motwani , Liadan O'Callaghan, Clustering Data Streams: Theory and Practice, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.515-528, March
robust representation;mathematical programming;clustering;feature selection