Data mining techniques extract useful information from large databases. The techniques can be categorized as being either descriptive or predictive. In this thesis, we focus on classification, the predictive data mining used for discrete target variables, and variable selection for classification. We propose classification algorithms for multi-class classification problems, and variable selection algorithms for binary classification and multi-class classification using signomial function. Specifically, this research contributes to the field of classification and variable selection by:
1. Constructing a multi-class classifier directly by solving a single optimization problem to be capable of capturing the correlations among classes;
2. Obtaining classifiers which are sparse and can be explicitly described in original space, which facilitates interpretation;
3. Determining a subset of variables that is desirable for predicting the output, considering nonlinear interactions of variables;
4. Performing variable selection for multi-class classification by treating multiple classes jointly to select a small common subset of variables.
First, we propose two multi-class classification methods using signomial function. Each of them directly constructs a multi-class classifier by solving a single optimization problem. Since the number of possible signomial terms is huge, we propose a column generation method that iteratively generates good signomial terms. The both methods obtain better or comparable classification accuracies and give more sparse classifiers than the existing methods.
Next, we propose two embedded variable selection methods using signomial function. We attempt to select, among a set of the input variables, those that lead to the best performance of the classifier. One method repeatedly removes variables based on backward selection, and the other method directly select a set of the variables by solving an optimization problem. The proposed methods conduct variable selection considering nonlinear interactions of variables, and additionally obtain a signomial classifier with the selected variables. The proposed methods select more desirable variables for predicting the output and give the classifiers with the better or comparable test error rates, as compared with the existing methods.
Lastly, we develop some embedded variable selection methods for multi-class classification using signomial function. We introduce a sparsity function which measures the number of the selected variables, and add the sparsity function to an objective function. In addition to, we propose that different sparsity parameters are imposed on different variables according to their relative importance. The proposed methods treat multiple classes jointly in multi-class classification problems, and select variables that are desirable for predicting the output. In addtion to, the proposed methods automatically determine the number of the variables to be selected, and obtain classifiers without the additional training process.
데이터 마이닝이란, 대규모 데이터로부터 유용한 정보를 자동화된 방법으로 탐색하는 과정을 의미한다. 데이터 마이닝 작업은 크게 예측 작업과 서술 작업으로 나눌 수 있다. 예측 작업은 알고 있는 특징 정보들을 활용하여 임의의 특징 정보의 값을 예측하는 예측 작업으로, 알고자 하는 특징 정보가 이산형인 경우를 분류라고 부른다. 본 논문에서는 분류 분석과 분류 분석을 위한 변수 선택에 대해 초점을 고려하며, signomial function을 이용한 다중 분류 문제를 위한 분류 해법과 이진 분류 문제와 다중 분류 문제를 위한 변수 선택 해법을 개발한다. 본 연구의 구체적인 기여는 다음과 같다.
1. 다중 분류 문제에서의 클래스 간의 연관성을 고려하는 다중 분류기를 구하는 해법을 개발함.
2. 원공간에서 명확히 기술 가능하고, 포함하고 있는 항 수가 적은 희박한 분류기를 얻음으로 데이터와 분류 결과 해석을 용이하도록 함.
3. 변수간의 비선형 상호 작용을 고려하여, 예측에 도움이 되는 변수를 선택하는 알고리즘을 개발함.
4. 다중 분류 문제에서 다수의 클래스를 동시에 고려하여 예측에 도움이 되는 공동의 변수를 선택하는 방법을 개발함.
먼저, 두 가지 다중 분류 해법을 개발한다.분류기를 정규화하기 위하여, 하나의 방법은 L1-norm을, 다른 방법은L0-norm을 사용한다. 각각의 방법은 하나의 최적화 문제를 풂으로 signomial function으로 표현되는 다중 분류기를 구성한다. 다중 분류기를 구성하기 위해, 분류기의 항을 열 생성 기법을 통해 생성하여 분류에 도움이 되는 항만을 생성하게 한다. 두 방법 모두 기존의 방법들 보다 더 좋거나 비교할 만한 분류 정확도를 주고, 더 희박한 분류기를 생성한다.
다음으로, 두 가지 임베디드 변수 선택 방법을 개발한다.변수 선택이란 입력 변수들 중에 분류기의 성능을 좋게 하는 변수들은 선택하는 것이다. 후진 선택을 기반으로 변수를 하나씩 반복적으로 제거하는 방법과 원하는 변수들을 하나의 최적화 문제를 풂으로 즉시 얻어내는 방법을 제안한다. 제안 방법들은 변수들의 비선형 상호 작용을 고려하여 변수 선택을 수행하고, 선택한 변수들로 이루어진 분류기를 부가적으로 얻는다. 기존의 방법들과 비교하여, 제안된 방법들은 좋거나 비교할 만한 분류 오류률를 가지는 분류기를 주며, 이는 제안 방법이 예측에 도움이 되는 변수들을 선택하여 주는 것을 의미한다.
마지막으로, 다중 분류 문제를 위한 두 가지 임베디드 변수 선택 방법을 개발한다. 다중 분류 문제에서 더 적은 수로 좋은 예측 성능을 가지게 하는 변수를 선택하기 위해, 입력 변수 중 선택하는 변수의 수를 측정하는 희박 함수를 도입하여 이를 목적함수에 추가하는 방법을 제안한다. 추가적으로, 변수들의 상대적인 중요성을 반영하기 위해, 각 변수 마다 다른 희박 파라미터를 부과하는 방법도 제시한다. 제안 방법들은 다중 분류 문제에서 다수의 클래스를 동시에 고려하여 변수 선택을 할 수 있게 해주며, 기존의 방법과 비교하여 분류 예측에 도움이 되는 변수들을 효과적으로 선택하여준다. 또한, 제안 방법들은 좋은 예측 성능을 주는 변수의 수를 자동적으로 결정하며, 추가적인 훈련 과정 없이 분류기를 생성하여 준다.
