I.

반구조화된 바이오데이터 분석을 위한 반교사학습

Semisupervised Learning for Semistructured Biodata Analysis

Hye-Sung Yoon, M.S.*↕, Sang-Ho Lee, M.S., Ph.D.* , Ju Han Kim, M.D., Ph.D.↕

* Dept. of Computer Science and Engineering, Ewha Womans University, Seoul, 120-750, comet@ewha.ac.kr, shlee@ewha.ac.kr

↕ SNUBiomedical Informatics, Seoul National University college of Medicine, Seoul, 110-799, juhan@snu.ac.kr

Abstract: Many supervised learning algorithms have been developed and extensively studied. But, in many practical learning problems including bioinformatics area, there is a small amount of labeled data along with a large pool of unlabeled data. Our goal in this paper is apply a new strategy in bioinformatics to semisupervised learning for classification tasks. The main idea of semisupervised learning algorithm is to consider the problem of using a large unlabeled sample to boost the performance of a learning algorithm when only a small set of labeled examples is available. We also applied a co-training strategy for unlabeled data to improve the performance of standard supervised learning algorithms. Some empirical results for the suggested co-training strategy on real biopathway data are provided.

Keyword: semisupervised learning, semistructured data, XML

배 경

DM(Direct mail) 반응여부, 가장 높은 수익을 얻을 수 있는 목표 시장을 찾는 문제와 같이 예측하고자 하는 목적변수(target value)가 있는 데이터마이닝 과정 또는 학습과정을 교사학습(supervised learning)이라고 하는 반면 이런 예측의 대상이 되는 목적변수가 없으면 이를 비교사학습(unsupervised learning)이라 한다. 이러한 학습방법은 우리가 탐사한 지식, 데이터베이스의 종류, 정보의 종류, 적용할 탐사 기법에 따라서 다르게 적용된다.

현재 생물정보학(bioinformatics)에서 바이오(bio) 데이터들로부터 유용한 정보를 얻고자하는 연구가 많이 진행되고 있다. 하지만 각기 다른 형식과 내용으로 산재해 있는 데이터들에서, 찾고자 하는 목적에 부합된 관련 정보를 추출하기 위해서는 바이오 데이터의 형식에 대한 연구와 적합한 적용 알고리즘들이 필요하다. 더구나 생물정보학에서 분석하고자 하는 많은 데이터의 형식이 반구조화된 데이터(semistructured data) 구조를 가지고 있다. 하지만 이러한 데이터 구조에 적합한 분석방법을 찾고 이를 적용하여 유용한 결과값을 얻어내기 위해서는 아직까지 연구해야 할 사항들이 많이 있다.

따라서 본 논문에서는 이러한 점을 고려하여 반구조화된 바이오 데이터에서 알려진 정보의 양이 적을 때 효과적인 방법을 적용하는 방법에 대해서 연구하고 이를 적용하였다. 본 논문의 실험에서 생물학적 데이터 구조인 반구조화된 데이터 구조 형식의 예로는 XML 데이터를, 분석방법으로는 반교사학습(semisupervised learning) 방법 중 co-training 알고리즘을 적용하였다. 그 결과 기존의 텍스트 분석에서 그 효과가 입증되었던 반교사학습 방법이 바이오 데이터의 분석방법에도 역시 효과가 있음을 발견할 수 있었다.

본 논문의 구성은 다음과 같다. 2절에서 적용 알고리즘의 설명과 실험에 이용된 데이터의 특성 및 실험방법에 대해 소개하고, 3절에서는  제안 방법에 대한 실험절차 및 수행 결과를 기존의 교사학습방법과 비교평가하고, 4절에서 결론을 맺는다.

II. 적 용 알 고 리 즘  및  실 험 방 법

본 절에서는 반구조화된 바이오 데이터 분석을 할때에 반교사학습 알고리즘을 적용하기 위한 기반작업을 설명한다. 먼저 반교사학습 알고리즘 중에서 본 논문에서 활용한 반구조화된 데이터의 특성과 co-training 알고리즘에 대해서 살펴보고, 이를 생물정보학에 적용하기 위한 실제 실험 방법에 대해 소개한다.

1. 반구조화된 데이터

반구조화된 데이터를 직관적으로 정의하면 처리하지 않은 데이터도 아니면서, 정형적인 구조도 가지고 있지 않은 데이터를 말한다. 즉, 데이터의 구조가 부분적으로 알려져 있으며 사전예고 없이 변화 가능한 데이터이다. 우리 주변에서 반구조화된 데이터들의 예로는 web, XML, Genome, CAD, 과학적인 계산 데이터들을 들 수 있다.

2.  반교사학습

교사학습의 대부분의 계산적 모델들은 분류표시된 자료들만을 고려하고, 비분류표시된 자료의 가능한 역할은 무시한다. 보유하고 있는 데이터들은 점점 많아지고 있는 요즈음 이 데이터에서 유용한 정보를 추출하여 활용하고자 할 때에 기존의 교사학습은 많은 어려움이 있다. 우선은 보유 데이터들의 분류와 이에 따른 시간과 비용이 가장 큰 문제이다. 본 논문에서의 실험 목적은 주로 바이오 데이터를 분류하는 데에 분류표시된 자료와 비분류표시된 자료를 결합하여, 비분류표시된 자료를 이용하여 소수의 분류자들의 자료수를 높이고 이에 따른 분류 수행의 향상성을 보이고자 하였다. 이를 위해 반교사학습을 위한 여러 접근 방법들 중에서 co-training 알고리즘을 적용하였다.

3.  데이터 수집

반교사학습의 아이디어를 테스트해보기 위해서 실험 데이터는 생체정보경로(biopathway) BIND XML 문서 총 12,033개를 가지고 실험하였다. BIND XML 문서는 3가지 다른 XML 문서로 구성되어 있는데 이중에서 100개를 분류표시 자료로, 나머지를 비분류표시 자료로 구성하였다. BIND는 3가지 interactions, complexes, pathways XML 문서로 구성되어 있다. 이중에서 complex XML 문서를 목적함수(target function)로 두었다. 따라서 interaction XML 문서는 positive가 되고, 나머지, complex와 pathway XML 문서는 negative examples가 된다. 전체 데이터 셋에서 complex XML 문서는 전체 데이터 셋에서 7%(851개 문서)이다.

4.  분류자

생체정보경로 XML 문서는 전체를 2가지 다른 정보를 사용하여 설명할 수 있다. 그것은 XML 문서를 태그(tag)와 내용(content)으로 구분하여 설명할 수 있다는 것이다. 따라서 분류자 A, B로는 XML 문서의 태그와 내용으로 각각 놓고 이것을 tag-based와 content-based 분류자라고 놓았다.

5. XML문서 분석을 위한 Co-training 알고리즘

본 논문에서 적용한 co-training 알고리즘을 바이오 데이터의 구조적 성격을 가진 생체정보경로 XML 문서에 적용한 알고리즘을 Table 1에 기술하였다.

III. 실 험 방 법  및  결 과

본 논문에서는 기존의 co-training 알고리즘과 유사하지만 반구조화된 XML 데이터에 적합한 밥법으로 co-training 알고리즘을 적용한 기술적인 면을 이용한 것을 보인다. 그리고 문서간 비교 분류를 하기 위해 적절한 방법으로 표준화가 되어 있지 않은 생체정보경로 XML 문서를 가지고 실험하는 것이기 때문에 실험의 대상이 되는 XML 문서가 한정되어 있기 때문에 이에 따른 문서간 비교 분류를 하기 위해 적절한 방법으로 변수를 조절하고 선택하여 실험하였다. 이 실험의 결과를 요약하면 다음의 Table 2와 같다. 표에서 위의 행은 단지 분류표시된 자료를 가지고 훈련했을 때의 비율이고, 아래 행은 분류표시된 자료의 분류자를 가지고 비분류표시된 자료를 co-training 알고리즘을 적용하여 분류표시된 자료로 더하고 이것이 정확한 분류를 하였는지에 대한 에러율을 보여준다. 숫자는 10번의 반복실험 결과 생체정보경로 XML 문서를 찾는 비율을 나타낸다.

각 생체정보경로 XML 문서 전체를 x라하고 태그정보들로 분류한 문서들을 x1(x1 =xT1,xT2,xT3..............xTn)으로 보고, 내용으로 분류한 문서를 x2(x2 =xC1,xC2,xC3..............xCn)로 놓는다.(x=x1+x2)  분류자는 x1과 x2에서 각각 훈련되어 진 것을 사용한다. 그리고 이것을 각각 tag-based와 content-based로 놓는다.

Table1에서 설명된 것처럼 분류표시된 문서를 L이라 놓고, 비분류표시된 문서를 U라 놓는다. 그리고 co-training 알고리즘 적용을 위하여 U에서 임의의 문서 샘플들을 추출하여(u) U'를 만든다. 그런후 다음과 같은 절차를 반복한다. 먼저, 분류표시된 문서에서 훈련된 두 개의 분류자 h1, h2를 구성한다. 여기서 h1은 x1의 분류기준이 되는 태그정보중  일부이고, h2는 x2의 분류기준이 되는 내용정보중의 일부이다. 그 다음 두 번째로는 비분류표시된 문서 U'를 실험하기 위해서 positive로 분류할수 있는 p개의 문서와 negative로 분류된 n개의 문서를 선택한다. 본 논문에서는 기존의 co-training 알고리즘에서 p와 n의 선택비율인 p=1, n=3을 적용하였다. 이런 방식으로 분류자들에 의해 선택된 positive와 negative 문서들이 L로 더해진다. 마지막으로, U'는 기존의 p와 n의 비율에서 반복할때마다 2p+2n의 비율로 확장되게 랜덤하게 선택한다. Table 2를 보면 파라미터를 p=1, n=3, k=10 그리고 u=30로 놓고 co-training 알고리즘을 수행한 결과이다. 우선 모든 3가지 분류자 타입(tag-based, content-based 그리고 combined)이 교사학습에 의한 분석정확도 보다 모두 우수하다는 것을 볼 수 있다. Combined classifier는 전체 문서 즉, x=(x1, x2)에서 tag-based와 content-based에 의한 수행결과를 곱한 확률값이다:

P(cj | x) □ P(cj | x1) P(cj | x2)

이러한 실험 결과를 보여준 것이 Figure 1으로써 10번의 반복실험에 따른 정확도의 변화율을 보여준다. 그리고 생체정보경로 XML 문서를 분류하는 데에 분류자 내용(content)의 요소가 태그(tag)보다 co-training 수행에 덜 도움을 준다는 것을 살펴볼 수 있다. 이것은 내용이 태그보다 문서마다 너무나 많은 서로 다른 단어가 사용되고 생체정보경로 XML content 특성상 목적함수에 적절한 정확성을 표현할 수 있는 h2를 찾는 것이 어렵기 때문이다. 하지만 교사학습에 비해서 두 배의 정확성을 가지기 때문에 co-training 알고리즘이 반복실행으로 XML 문서 즉, 반구조화된 성격의 데이터 값을 갖는 데에서도 효과적임을 발견할 수 있다. 그리고 생체정보경로 XML 문서를 통한 실험에서 앞으로 바이오 데이터 분석을 위한 여러 응용에 반교사학습 방법이 바

	Tag-based classifier	Content-based classifier	Combined classifier
Supervised training	42.5	72.5	33.8
Co-training	26.59	36.3	23.75

Figure 1. The error versus the number of iterations

이오 데이터 분석에 적합한 알고리즘으로 적용 가능하다는 것을 발견할 수 있었다. 즉, 발견된 바이오 데이터의 정보가 많지 않고 이와 유사한 데이터의 값이 있는데 분류가 되어 있지 않다면, 분석을 할 때에 더 많은 정보를 이용하여 정확한 분류를 하기위한 분류자를 만들기 위한 방법이 될 수 있겠다.

이 실험은 제한된 XML 문서 즉, 한가지 데이터 셋과, 한개의 목적 함수를 가지고 실험하였다. 그리고 실험 데이터 값을 XML 문서로 하였기 때문에 분류

자를 선택하는 데에 있어서 한정된 선택밖에 할 수 없었다. 하지만 현재 생체정보경로의 XML 문서를 살펴 볼 수 있어서 문서의 구조 파악과 분석의 정확성면에서는 효과적이라고 판단된다.

본 실험에서 중요한 것은 실험의 결과 반교사학습 알고리즘이 생물정보학 분야에서 이용가치가 있는 유용한 알고리즘으로 평가되었다는 것이다. 바이오 데이터를 분석할 때에도 분류표시된 데이터의 수가 적을 경우에 분류표시된 문서를 추가적으로 사용했을 때에 사용하지 않았을 때보다 문서 분류의 정확도가 증가하였으므로 반교사학습 알고리즘 적용은 유용한 방법이라 할 수 있다.

IV. 결 론  및  향 후 연 구 과 제

본 논문에서는 반구조화된 성격의 바이오 데이터 분석을 할 때에 분류표시된 데이터의 수가 많지 않을 경우 분류표시된 데이터의 수를 보충하기 위해서 비분류표시된 데이터를 이용하여 기존의 학습 방법인 반교사학습을 적용하였다. 그 결과 반교사학습 방법이 바이오 데이터 구조를 분류하는 데에도 효과적인 방법이라는 것이 입증되었다.

반교사학습 방법중에 하나인  co-training 알고리즘은 한 개가 아닌 두 개의 독립된 분류자를 이용하여 훈련시키는 아이디어로 출발하였다. 그리고 이것은 기존의 텍스트 분류에 있어서 더욱 정확한 분류자들을 이끌어내고 분석하는 데에 기여하였다. 생물정보학의 여러 연구에서도 이미 알려진 데이터의 부족에 따른 지식을 습득하는 데에 병목을 해소하기 위해서 정확한 분석과 분류가 요구된다. 예를 들어 annotation 데이터의 양이 unannotation 데이터의 양보다 적은 경우 생물학적 개체인식을 하는 데에도 효과적일 것이라고 판단된다. 따라서 본 논문에서는 생물정보학 분야의 여러 방면에 co-training 알고리즘의 적용이 효과적이며, 이를 적용하여 분석과 분류의 정확성을 높이는 데에 기여함을 보이고자 하였다. 그 결과 기존의 co-training 알고리즘을 적용한 텍스트 분석과 마찬가지로 본 논문의 실험에서 co-training은 분석의 정확성을 높여준다는 것을 확인할 수 있었다.

본 논문에서 적용한 co-training 알고리즘은 한 개가 아닌 두 개의 독립된 분류자를 이용하여 훈련시키는 아이디어로 출발하였다. 그리고 이것은 기존의 텍스트 분류와 마찬가지로 더욱 정확한 분류자들을 이끌어내고 분석하는 데에 기여하였다.

생물정보학의 여러 연구에서도 이미 알려진 데이터의 부족에 따른 정확한 분석과 분류가 요구된다. 예를 들어 annotation 데이터의 양이 unannotation 데이터의 양보다 적은 경우 생물학적 개체 인식을 하는 데에도 효과적일 것이라고 판단된다. 실험에서는 파라미터를 정할 때의 문서선택의 다양한 비율을 가지고 실험하였으나 거의 같은 비율을 보여주었다.  생물정보학에서 바이오 데이터 분석을 할 때에 정확한 정보를 가진 분석을 위해서는 파라미터의 선택이 중요하다고 판단되어진다. 하지만 본 논문에서는 생물정보학의 여러 방면에 co-training 알고리즘의 적용이 효과적이며, 이를 적용하여 분석과 분류의 정확성을 높이는 데에 기여함을 보이고자 하였다. 그 결과 기존에 co-training 알고리즘을 적용한 텍스트 분석과 마찬가지로 본 논문의 실험에서 co-training은 분석의 정확성을 높여 준다는 것을 확인할 수 있었다.

앞으로의 향후 연구과제로 고려하고 있는 점은 관측된 패턴의 경향을 찾기 위한 정확한 측정방법 즉, 데이터 마이닝과 같은 기술이 필요하다는 것과 co-training 알고리즘의 일반적 양상을 더욱 관측할 수 있는 다양한 방법의 필요성이다. 우선은 생물정보학에서 생체정보경로 XML 문서를 가지고 실험을 하였고, 이 실험은 바이오 데이터 특성인 반구조화된 데이터 구조인 XML 데이터를 가지고 실험한 것이다. 따라서 이것을 적용 방법에 맞추어 새로운 알고리즘으로 디자인 설계하여 적용하는 것을 계획으로 두고 있다.

Acknowledgments

This study was supported by a grant of the Korea Health 21 R&D Project, Ministry of Health and Welfare, Republic of Korea (01-PJ10-PG6-01GM01-0004).

참고문헌

1. A. Blum and T. Mitchell, Combining Labeled and Unlabeled Data with Co-Training, Proceedings of the 11th Annual Conference on Computational Learning Theory(COLT), pp.92-100, 1998.

2. K. Nigam and Rayid Ghani, Understanding the Behavior of Co-training, In KDD-2000 Workshop on Text Mining, 2000.

3. S. Goldman and Y. Zhou, Enhancing Supervised Learning with Unlabeled Data, Proceedings of the 7th International Conference on Machine Learning(ICML), pp.327-334, 2000.

4. T. Mitchell, The Role of Unlabeled Data in Supervised Learn', Proceedings of the Sixth International Colloquium on Cognitive Science, San Sebastian, Spain, 1999.

5. P. Buneman, Tutorial: Semistructured Data, Proceedings of ACM symposium on Principles of Database Systems, pp.117-121, 1997.

6. D. Suciu, Semistructured Data and XML, International Conference on Foundations of Data Orgaization and Algorithms(FODO), 1998.