Data Mining Algorithms for Ranking Problems

Abstract

<p>Classification is the process of finding (or training) a set of models (or functions) that describe and distinguish data classes or concepts. That is for the purpose of being able to use the models to predict the unknown class labels of instances [12].</p> <p>We deal with the ranking problem in this thesis. The ranking problem is a special case of the classification problem, where the class labels are ranks or ratings, represented by integers from 1 to q. The ranking problem can also be cast as the process of training a rank-prediction model that assigns each instance a rank that is "as close as possible" to the instance's actual rank [8]. Popular applications of the ranking problem include ranking the importance of web pages, evaluating the financial credit of a person, and ranking the risks of investments.</p> <p>Two popular families of methods to solve ranking problems are MultiCriteria Decision Aid (MCDA) methods and Support Vector Machines (SVMs). The performance of successful MCDA methods, such as UTilites Additives DIScriminantes (UTADIS) and Generalized UTilites Additives DIScriminantes (GUTADIS) , is achieved by exploiting the background knowledge that describes the correlations between the attributes and the ranks. Unfortunately, the background knowledge is case-dependent, hence it is likely to be unavailable, inexact or difficult to be modeled in practice. This restricts the application of MCDA methods. SVMs, instead, do not require any background knowledge. Their good performance is achieved by keeping balance between minimizing the empirical loss and maximizing the separation margin. Normally, a multi-class Support Vector Machine Classifier is constructed by combining several binary Support Vector Machine Classifiers. In the SVM-based approach the ranking information is not used.</p> <p>This thesis attempts to construct an efficient algorithm for ranking problems. We compare the properties of existing algorithms for ranking problems and propose a hybrid algorithm that combines the multi-class SVM (MSVM) and the UTADIS model. In the new algorithm, the binary SVM classifiers are combined into a multi-class classifier based on the fuzzy voting technique. The optimal fuzzy voting strategy is searched by solving a Linear Program (LP). The new algorithm is called Fuzzy Voting based Support Vector Ranking (FVSVR) method. We also extend the idea of Fuzzy Voting from ranking problems to generic multi-class classification problems, which leads to a Fuzzy Voting based Support Vector Machine (FVSVM) method. The benefits of FVSVR and FVSVM are demonstrated by experimental results based on several databases of practical classification problems.</p>