Data mining for commerce problems: Global optimization of clusterwise regression and neural networks applied to electronic negotiations

This work explores two commerce related data mining topics. The first is the exact optimization of the clusterwise regression problem and the second predictive negotiation modeling using neural networks.;Exact global optimization of the clusterwise regression problem (Charles 1977; Diday 1979; Spath 1979) is a challenging data mining technique. Before starting the current research work, there were no published feasible methods for performing this clustering optimally, even though it has been over thirty years since its original proposal. This first part of this work explores global optimization of the clusterwise regression problem using three optimization methods; mathematical programming, branch and bound optimization and column generation.;The first optimization approach applied to the clusterwise regression problem is by mathematical programming. A mixed logical-quadratic programming formulation with implication of constraints is presented and contrasted against a quadratic formulation based on the traditional big-M, which cannot guarantee optimality because the regression line coefficients, and thus errors, may be arbitrarily large. Clusterwise regression optimization times and solution optimality for two clusters were empirically tested on twenty real datasets and three series of synthetic datasets ranging from twenty to one hundred observations and from two to ten independent variables. Additionally, a few small real datasets were clustered into three lines (Carbonneau, Caporossi & Hansen 2011).;Secondly, a branch and bound strategy is proposed for solving the clusterwise regression problem, extending Brusco's repetitive branch and bound algorithm (RBBA) (Brusco & Stahl 2005; Brusco 2006). The resulting strategy relies on iterative heuristic optimization, new ways of observation sequencing, and branch and bound optimization of a limited number of ending subsets (BBHSE). These three key features lead to significantly faster optimization of the complete set and the strategy has more general applications than only for clusterwise regression. Additionally, an efficient implementation of incremental calculations within the branch and bound search algorithm eliminates most of the redundant ones. Experiments using both real and synthetic data compared the various features of the proposed optimization algorithm and contrasted them against a benchmark mixed logical-quadratic programming formulation optimized by CPLEX. The results indicate that all components of the proposed algorithm provide significant improvements in processing times, and, when combined, generally provide the best performance, significantly outperforming CPLEX (Carbonneau, Caporossi & Hansen 2011).;The third strategy is a column generation (Dantzig & Wolfe 1960; Barnhart, Johnson, Nemhauser, Savelsbergh & Vance 1998) based approach for solving the clusterwise regression problem. The proposed strategy firstly relies on heuristic optimization of the original problem for insertion of the best known columns and all possible one-observation-perturbations into the restricted master problem. Secondly, for the subproblem, a greedy heuristic based on the dual variables, another based on the best known solution to the original problem, and multistart heuristic optimization are all employed to attempt to insert one or more columns early and stop the subproblem search. If these heuristics fail to identify an improving column, an exhaustive search is performed starting with incrementally larger ending subsets, all the while iteratively performing heuristic optimization to ensure a proper balance of exact and heuristic optimization.;The application of data mining techniques to electronic negotiations is relevant to today's interconnected world. Electronic negotiation systems can incorporate computational models and algorithms in order to help negotiators achieve their objectives. An important opportunity in this respect is the development of a component which can assess an expected reaction by a counterpart to a given trial offer before it is submitted. This work proposes a pairwise modeling approach that provides the possibility of developing flexible and generic models for counteroffer prediction when the negotiation cases are similar. The key feature is that each negotiated issue is predicted while paired with each of the other issues and the permutations of issue pairs across all negotiation offers are confounded together. This data fusion permits extractions of common relationships across all issues, resulting in a type of pattern fusion. Experiments with electronic negotiation data demonstrated that the model's predictive performance is not compromised as compared to case-specific models while offering a high degree of flexibility and generality even when predicting for a new, previously unseen issue (Carbonneau, Kersten & Vahidov 2011). (Abstract shortened by UMI.).