Data mining algorithms based on support vector learning such as the Support Vector Machines (SVMs) and the Support Vector Data Description (SVDD) have many the benefits over other data mining algorithms, and have been widely used in many research areas including bioinformatics. The conventional SVMs and the original SVDD, however, lack a mechanism for reflecting variations in the significance of data in a given data set; they treat all data equivalently. In many real world problems, however, data may have different degrees of significance due to noise, missing values, or density. Thus the main objective of this thesis is to propose new methods that can more correctly identify the optimal solution by reflecting the different significance into the data mining algorithms such as SVMs and SVDD, and to apply the proposed methods to the real areas especially in the bioinformatics field.
To achieve the purpose mentioned above, we tried to address the following three questions in this thesis: 1) how to propose new SVMs that take into account all differences in significance to more accurately identify the optimal hyperplane (OHP) from a data set that has different significance among its members, 2) how to propose a new SVDD to more correctly identify the optimal description of a target data set by reflecting the differences in significance owing to the different density degree of each data point, and 3) how to apply the proposed methods to the real world problems such as the prediction of protein subcellular localization.
To answer the first question, in this thesis we have proposed S-SVMs which can reflect the differences in the significance of training data. In the S-SVMs we have introduced a new distance measure called a significance-based distance which calculate the distance between a data point and a hyperplane based on the significance degree of the data point. Using the distance measure S-SVMs find the optimal hyperplane while incorporating the significance of each data point. Furthermore, for the S-SVMs, we have proposed several significance extraction methods and a refinement algorithm based on the number of missing attributes or geometric characteristics of each data point. After the benchmarking the performance of S-SVMs against performances of conventional SVMs and Fuzzy SVMs, we observed that the proposed approach better reflects varying significance in a given data set.
For the second question, we have proposed a novel method called Density-induced Support Vector Machine (D-SVDD) which is incorporating the density distribution of a given target data set when identifying the hyperspherical data description of the target data set. To reflect the density distribution, we associated each data point with a relative density degree, and proposed two kinds of density-induced distance measurement based on the degrees. From several experiments with real data sets, we have observed that the proposed D-SVDD method outperformed the other data description methods including the conventional SVDD for all tested data sets regardless of the kinds of kernel function and regardless of the use of negative data in training. When the information of negative data is available, the performance of proposed method was also compatible with well-known multi-class classifiers such as k-Nearest Neighbor classifier, and SVMs.
For the last problem, we developed a new method for the prediction of protein localization, which can find the likelihood of a specific localization of a protein more easily and more correctly. Even though many previous works have been done for the task of protein subcellular localization prediction, none of them tackles effectively all the characteristics of the task: many classes (there are more than 10 localizations), a multi-label classification problem (a protein may have several different localizations), and an imbalanced data set (a protein data set is imbalanced in nature). To get more reliable results, thus, a new computational method is eventually needed. To achieve the purpose we have proposed the Protein Localization Predictor using proposed Density-induced Support Vector Data Description (PLPD) method by modifying the proposed D-SVDD in order to apply to a multi-class and multi-label classification problem. As the results of three data sets which is made from the Huh\'s data set, the PLPD method outperformed the Isort method which is the previous multi-label method regardless of the data set used and regardless of the measure used. Moreover, after finding the good boundary of each localization using the proteins whose localizations are known as training data, we predicted the subcellular localizations of 241 proteins whose subcellular localizations could not be observed or whose subcellular localizations are ambiguous in the experiments of the Huh et. al.
서포트벡터머신 및 서포터벡터데이터기술방법과 같은 서포트벡터기반 데이터마이닝기법들은 많은 장점으로 인해 최근에 바이오인포메틱스를 포함해 여러 분야에서 많이 사용되고 있다. 하지만 고전적인 포트벡터기반 데이터마이닝 방법들에는 데이터 마다 존재 가능한 서로 다른 정도의 중요성을 반영할 수 있는 수단이 존재하지 않고, 모든 데이터를 동등하게 취급한다. 그러나 실 세계 문제에서는 데이터의 노이즈, 부정확성, 결여된 값, 또는 분포상의 특이성 등으로 인해 데이터마다 서로 다른 정도의 중요성이 존재 할 수 있다. 예를 들어 아웃라이어 또는 부정확한 데이터는 서포트벡터머신의 최적의 해를 찾는 과정을 방해 할 수 있다. 또한 성능을 높이기 위해서는 높은 밀도값을 가지는 데이터는 그렇지 않은 데이터보다 서포터벡터데이터기술방법의 최적의 해에 포함될 가능성은 높아야 된다. 따라서 그러한 데이터 마다 존재 가능한 차이성을 고려 하지 않은 해는 최적의 해가 되지 않을 가능성이 높다.
데이터에 존재 가능한 서로 다른 정도의 중요성이 해를 찾는 과정에 영향을 미칠 수 있다는 사실에도 불구하고 이러한 문제점을 다루고 있는 기존 방법론은 많지 않은 실정이다. 고전적인 서포트벡터머신의 최상의 해를 찾는 과정에 데이터의 서로 다른 중요성을 반영하려는 한 방법론으로 퍼지서포트벡터머신이 있다. 그러나 이 방법론 역시 데이터에 존재 가능한 모든 서로 다른 중요성을 반영하지는 못하고 단지 잘못 구분된 데이터의 서로 다른 중요성만 반영 한다. 또한 서포터벡터데이터기술방법에서 이러한 문제를 다루고 있는 기존 연구는 거의 찾을 수가 없다. 따라서 본 논문에서의 목표는 서포트벡터머신이나 서포터벡터데이터기술방법과 같은 마이닝 기법들의 최적의 해를 찾는 과정에서 실 세계 문제에 존재 가능한 데이터의 서로 다른 정도의 중요성을 정확하게 반영할 수 있는 새로운 방법론들을 제안하는 것이다. 이 목표를 이루기 위해서 우리는 다음의 3가지 문제에 대한 해를 제시하고자 하였다.
1) 어떻게 하면 서포트벡트머신이 서로 다른 정도의 중요성을 가지는 데이터 집합을 잘 구분 할 수 있는가?
2) 어떻게 하면 서포터벡터데이터기술방법론이 데이터의 분포에 의한 다른 정도의 중요성을 가지는 데이터 집합의 간결한 묘사를 찾을 수 있는가?
3) 어떻게 하면 제안된 방법들을 단백질의 세포 내 위치정보 예측과 같은 실 세계 문제에 적용할 수 있는가?
첫 번째 문제를 해결하기 위해 우리는 데이터 마다 존재 가능한 서로 다른 정도의 중요성을 반영할 수 있는 중요성기반 스포트벡터머신을 제안하였다. 이 중요성기반 스포트벡터머신에서 초평면과 하나의 데이터와의 거리를 재는 중요성 기반 거리라는 새로운 거리척도를 소개하였다. 그 제안된 거리척도를 이용해서 데이터의 상이한 중요성이 잘 반영된 최적의 초평면을 구하도록 하였다. 또한 본 논문에서는 주어진 데이터로부터 자동적으로 중요성을 추출할 수 있는 방법들과 보정 방법을 소개하였다.
그리고 제안된 방법론의 우수성을 입증하기 위해 고전적인 서포트벡트머신과 퍼지서포트벡트머신과의 비교 실험을 한 결과 제안된 방법론이 주어진 데이터 집합의 상이한 중요성을 반영하는데 효과적이며 우수함을 확인 하였다.
두 번째 문제를 위해서 우리는 밀도유도서포트벡터데이터기술방법을 제안하였다. 이 방법론에서는 주어진 대상 데이터 집합의 최적의 해를 찾을 때 각 데이터의 밀도를 반영하면서 해를 찾도록 하였다. 그 목적을 위해 우리는 각각의 데이터에 상대밀도 정도를 나타내는 수치를 연계시켜 사용하였고, 그 상대밀도 정도를 반영할 수 있는 새로운 거리척도를 두 가지 제안하였다. 그리고 그 제안된 거리척도를 이용해서 새로운 서포트벡터데이터기술방법론은 개발하였다.
5개의 실제 데이터 집합으로 실험을 한 결과 제안된 방법론이 고전적인 서포트벡터데이터기술방법이나 다른 데이터기술방법론들 보다 사용된 데이터 집합이나 사용된 커널 함수, 그리고 학습과정에서 네거티브 데이터의 사용 유무에 관계 없이 항상 우수한 성능을 보임을 확인하였다. 또한 학습과정에서 대상 데이터의 해의 영역에 포함되지 않아야 되는 네거티브 데이터의 정보를 사용되었을 때는 서포트벡터머신이나 k-NNC과 같은 잘 알려진 다중 분류자들과 대등한 성능을 보여줌을 확인 할 수 있었다. 더욱이 제안된 시스템이 가오시안 커널 함수를 사용했을 때 가장 우수한 성능을 보임을 확인 할 수 있었다. 그리고 주어진 데이터 집합이 밀도의 변화량이 많을 때 고전적인 서포트벡터데이터기술방법보다 많은 성능 향상을 보임을 확인하였다.
마지막 질문을 해결하기 위해 이 논문에서 우리는 단백질의 세포 내 위치 정보를 정확하게 자동적으로 추출할 수 있는 새로운 방법론을 제안하고자 하였다. 세포 내 위치 정보는 단백질의 가장 근본적인 기능에 관련된 특성 중의 하나이다. 또한 위치 정보가 알려지지 않은 많은 수의 단백질 증가로 인해 자동적이면서 효율적으로 그 정보를 추출할 수 있는 방법론이 절실히 필요한 실정이다. 비록 많은 기존 연구가 수행되어 왔었지만 위치 정보의 예측이 가지는 특징들을 모두 고려하고 있는 기존 연구가 없다. 이 특징들에는 세포 내에는 많은 다른 위치가 존재하고 하나의 단백질은 여러 개의 위치 정보를 가질 수 있고, 또한 각 위치마다 존재하는 단백질의 종류의 수에 많은 차이가 있다는 특성들이 존재한다. 이런 특징들이 단백질의 위치 정보 예측을 어렵게 하므로 좀더 신뢰할 만한 결과를 획득하기 위해서는 새로운 방법론이 절실히 필요한 실정이다.
따라서 우리는 제안된 밀도유도서포트벡터데이터기술방법론을 수정하는 방식으로 단백질 위치 정보 예측에 적합한 새로운 방법론을 제안하였다. 원래 밀도유도서포트벡터데이터기술방법론은 단일클래스 및 단일레이블 구분 문제를 위해 만들어 졌으므로 다중클래스 및 다중레이블 문제에 맞도록 각 클래스에 속할 정도를 나타내는 소속 정도를 추출하여 쉽고 정확하게 그 문제를 해결할 수 있도록 하였다. 실제 생물학적 실험 데이터를 사용해서 제안된 방법론과 기존의 방법론과 성능 비교를 해 본 결과 사용된 데이터의 정보나 사용된 평가 척도에 관계없이 항상 우수한 성능을 보여 줌을 확인 할 수 있었다. 또한 위치 정보가 알려진 단백질로부터 최적의 위치 정보의 구역을 찾은 후 생물학적 실험으로 위치 정보가 명확히 알려 지지 않은 237개의 단백질의 위치 정보를 예측해 보았다.
