Data Mining: The Textbook

11.5. REGRESSION MODELING WITH NUMERIC CLASSES

353

function is achieved. Let V be a vector with length equal to the number of Lagrangian variables and at most q nonzero elements. The goal is to determine the optimal choice for the q nonzero elements to determine the working set. An optimization problem is set up for determining V in which the dot product of V with the gradient of L_D (with respect to the Lagrangian variables) is optimized. This is a separate optimization problem that needs to be solved in each iteration to determine the optimal working set.

The second idea for speeding up support vector machines is that of shrinking the training data. In the support vector machine formulation, the focus is primarily on the decision boundary. Training examples that are on the correct size of the margin, and far away from it, have no impact on the solution to the optimization problem, even if they are removed. The early identification of these training examples is required during the optimization process to benefit as much as possible from their removal. A heuristic approach, based on the Lagrangian multiplier estimates, is used in the SVMLight approach. The specific details of determining these training examples are beyond the scope of this book but pointers are provided in the bibliographic notes. Another later approach, known as SVMPerf, shows how to achieve linear scale-up, but for the case of the linear model only. For some domains, such as text, the linear model works quite well in practice. Furthermore, the SVMPerf method has O(s · n) complexity where s is the number of nonzero features, and n is the number of training examples. In cases where s d, such a classifier is very effective. This is the case for sparse high-dimensional domains such as text and market basket data. Therefore, this approach will be described in Sect. 13.5.3 of Chap. 13 on text data.

11.5 Regression Modeling with Numeric Classes

In many applications, the class variables are numerical. In this case, the goal is to minimize the squared error of prediction of the numeric class variable. This variable is also referred to as the response variable, dependent variable, or regressand. The feature variables are referred

to as explanatory variables, input variables, predictor variables, independent variables , or regressors. The prediction process is referred to as regression modeling. This section will discuss a number of such regression modeling algorithms.

11.5.1 Linear Regression

Let D be an n × d data matrix whose ith data point (row) is the d-dimensional input feature vector X_i , and the corresponding response variable is y_i. Let the n-dimensional column-vector of response variables be denoted by y = (y₁, . . . y_n)T . In linear regression, the dependence of each response variable y_i on the corresponding independent variables X_i is modeled in the form of a linear relationship:

yi ≈		·		∀i ∈ {1 n}.	(11.2)