[논문]계층적 군집화를 이용한 능동적 학습

우호영; 박정희

doi:10.3745/ktsde.2013.2.10.705

[국내논문] 계층적 군집화를 이용한 능동적 학습
Active Learning based on Hierarchical Clustering 원문보기

정보처리학회논문지. KIPS transactions on software and data engineering. 소프트웨어 및 데이터 공학, v.2 no.10, 2013년, pp.705 - 712

초록
AI-Helper

능동적 학습(active learning)은 소수의 라벨 데이터로 구성된 훈련 집합이 주어진 경우에 분류기 학습에 가장 도움이 될 만한 언라벨드 데이터를 선택하여 전문가에 의한 라벨링을 통해 훈련 집합에 포함시키는 과정을 반복함으로써 분류기의 성능을 향상시키는 것을 목적으로 한다. 본 논문에서는 워드 연결(ward's linkage)을 이용한 계층적 군집화(hierarchical clustering)를 바탕으로 한 능동적 학습 방법을 제안한다. 제안된 방법은 각 군집에서 적어도 하나의 샘플을 포함하도록 초기 훈련 집합을 능동적으로 구성하거나 또는 기존의 훈련 집합을 확장함으로써 전체 데이터 분포를 반영할 수 있게 한다. 기존의 능동적 학습 방법들 중 대부분은 초기 훈련 집합이 주어져 있을 경우를 가정하는 반면에 제안하는 방법은 초기 클래스 정보를 가진 훈련 데이터가 주어지지 않은 경우와 주어진 경우에 모두 적용 가능하다. 실험을 통하여 제안하는 방법이 비교 방법들에 비해 분류기 성능을 크게 향상시킬 수 있는 효과적인 데이터 선택을 수행함을 보인다.

Abstract ▼ AI-Helper

Active learning aims to improve the performance of a classification model by repeating the process to select the most helpful unlabeled data and include it to the training set through labelling by expert. In this paper, we propose a method for active learning based on hierarchical agglomerative clustering using Ward's linkage. The proposed method is able to construct a training set actively so as to include at least one sample from each cluster and also to reflect the total data distribution by expanding the existing training set. While most of existing active learning methods assume that an initial training set is given, the proposed method is applicable in both cases when an initial training data is given or not given. Experimental results show the superiority of the proposed method.

Keyword

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

우리가 군집화를 능동적 학습을 위해 활용하려는 이유는 잘 형성된 군집에서 각 군집을 대표하는 데이터를 선택함으로써 최소의 데이터 선택으로 전체 데이터 분포를 잘 반영할 수 있기 때문이다. 우리는 좋은 군집을 형성하는 방법을 찾고, 그 방법을 활용한 능동적 학습 방법을 제안하고자 한다.
본 논문에서는 계층적 군집화를 이용하여, 초기 클래스 정보를 가진 훈련 데이터가 주어지지 않은 경우와 주어진 경우에 모두 적용 가능한 능동적 학습 방법을 제안하였다. 제안하는 방법은 군집화를 활용하여 잘 형성된 군집에서 각 군집을 대표하는 데이터를 선택함으로써 최소의 데이터 선택으로 전체 데이터 분포를 잘 반영할 수 있다.

가설 설정

기존의 능동적 학습 방법들 중 대부분은 초기 훈련 집합이 주어져 있을 경우를 가정한다. 대표적인 방법으로서, 기존의 학습된 모델에 의해 가장 불확실성이 높다고 판단되는 데이터에 대한 클래스 정보를 얻는 uncertainty sampling 방법[2,7], 다수의 분류기 모델을 구성하여 의견이 가장 불일치 하는 데이터를 선택하는 query by committee 방법[8,9], 현재 모델의 일반화 오류(generalization error)를 최대로 감소시킬 수 있는 데이터를 추정하여 선택하는 Expected Error Reduction 방법[10] 등이 있다.

제안 방법

예를 들어, 서포트 벡터 머신(support vector machine, SVM)을 기본 분류기로 이용한 능동적 학습인 SVMactive[2]는 초기 훈련 집합으로 SVM을 학습한 후, 분류기에 도움이 되는 데이터로서 현재 결정 경계에 가장 근접한 데이터를 선택한다. 현재 분류 모델을 이용하여 데이터 샘플들의 불확실성(uncertainty)이나 불순도(entropy)를 측정하여 다음 모델 학습에 포함시킬 샘플을 선택하는 것이다.
제안된 방법은 각 군집에서 적어도 하나의 샘플을 포함하도록 초기 훈련 집합을 능동적으로 구성하거나 또는 기존의 훈련 집합을 확장함으로써 전체 데이터 분포를 반영할 수 있게 한다. 2절에서는 능동적 학습에 대한 설명 및 대표적인 방법에 대한 소개를 하고, 3절에서는 계층적 군집화에 대한 설명과 연결 방법 등을 비교하고, 4절에서는 계층적 군집화를 이용한 능동적 학습을 제안한다.
군집화는 클래스 정보가 주어지지 않은 상황에서 유사한 데이터들을 같은 그룹에 속하게 하고 상이한 데이터들은 다른 그룹에 속하도록 전체 데이터를 몇 개의 그룹으로 나누는 방법이다[5]. 우리는 유사한 특징을 갖는 데이터를 그룹으로 묶는 군집화 방법을 이용하여, 초기 훈련 집합이 주어지지 않을 경우와 초기 훈련 집합이 주어졌을 경우 모두 적용이 가능한 능동적 학습 방법을 제안한다. 본 논문은 학술발표논문 [6]에서 제안되었던 초기 훈련 집합이 주어지지 않았을 경우의 능동적 학습 방법을 초기 훈련 집합이 주어졌을 경우까지 확장하고 있다.
한 쌍의 데이터가 가장 가까운 거리를 가지면 두 데이터는 같은 클래스 정보를 가질 가능성이 크다는 것에 기반을 두고 있다. 이 논문에서는 거리 측정 방법으로 두가지 방법을 제시하는데, 유클리디안 거리를 이용한 방법과 그래프 기반의 최단 거리를 이용한 측정 방법이다. 그러나, 임의 추출을 사용하여 전체 데이터의 부분 집합을 선택하므로 데이터 전체의 분포를 잘알 수 없는 경우가 발생한다.
우리는 4절에서 군집화 알고리즘 중에 계층적 병합 군집화를 이용한 능동적 학습 방법을 제안한다. 우리가 군집화를 능동적 학습을 위해 활용하려는 이유는 잘 형성된 군집에서 각 군집을 대표하는 데이터를 선택함으로써 최소의 데이터 선택으로 전체 데이터 분포를 잘 반영할 수 있기 때문이다.
제안하는 능동적 학습 알고리즘을 설명하기 전에 4가지 결합 방법에 의한 군집화 성능을 비교하고자 한다. 계층적 병합 군집화에 사용되는 여러 연결 방법에 대한 군집화 성능을 비교하기 위해 다음의 세 가지 척도를 사용하였다.
Table 1에 있는 다른 데이터 집합에 대해서도 유사한 결과를 얻었다. 우리는 단일 연결, 완전 연결, 평균 연결, 워드 연결을 이용한 덴드로그램을 구성하고, 각 군집화 방법에서 1부터 100까지 군집의 수를 변화시켜가면서 수치를 측정하였다. Davies-Bauldin 에 대한 결과에서 워드 방법은 가장 높은 값을 가지고, 단일 연결 방법은 가장 낮은 값을 가졌다.
이것은 각 군집에 속한 데이터들이 가장 동일한 클래스 정보를 가지고 있는 연결 방법이 워드 방법이라는 것을 나타낸다. 세 개의 평가 방법을 통하여 우리가 하고자 하는 방향을 제일 수치적으로 잘 표현한 워드 방법을 이용하여 능동적 학습에 적용하고자 한다.
그리고 각 군집에서 대표적인 하나의 데이터를 선택한다. 각 군집에 속한 데이터들은 서로 유사한 특성을 가지기 때문에 하나의 군집으로 묶여 있으며, 각 군집에서 대표적인 하나의 데이터를 선택함으로써 전체 데이터 분포를 잘 표현하는 데이터 집합을 구성하고자 한다. 얻고자 하는 데이터의 수를 k라 하고, 선택되는 샘플의 집합을 {s₁,.
초기 훈련 집합이 주어진 상황에서 덴드로그램을 활용하여 능동적 학습에 적용하고자 한다. 주어진 초기 훈련 집합을 L이라고 하자.
4에서는 L이 붉은 원으로 표시된 세개의 데이터 샘플을 포함하고 있다고 할 때, 첫 번째 군집에 모두 속해 있는 경우를 나타낸다. 따라서 추가하고자 하는 원소의 수가 k개라고 할 때, k+1개의 군집이 형성되는 지점부터 시작하여 L의 원소를 포함하지 않는 군집이 k개가 될 때까지 덴드로그램의 분할 방향을 따라 군집의 수를 늘리면서 탐색을 한다. L의 원소를 포함하고 있지 않은 군집의 수가 k개가 되었을 때 각 군집에서 하나씩 대표 샘플을 선택하여 L의 집합에 추가한다.
제안하는 방법은 계층적 병합 군집화가 구성된 역방향으로 군집의 개수를 증가시키면서, 초기 훈련집합의 원소를 포함하고 있지 않은 군집에서 데이터를 선택하는 방법이다.
제안하는 계층적 군집화를 이용한 능동적 학습 방법(Active Learning using Hierarchical Agglomerative Clustering, AL-HAC)을 Fig. 5에 요약하였다.
Table 1은 실험에 사용된 데이터 정보이다. 각 데이터 집합에 대해 전체 데이터를 6:4의 비율로 클래스 정보가 없는 집합(unlabeled pool)과 테스트 집합으로 나누었다. 성능측정을 위한 기본 분류기로 선형 커널을 사용한 libSVM[17]과 WEKA[18]의 다층 퍼셉트론(Multi-Layer Perceptron, MLP)을 이용하였고, 10번 실험을 반복하여 측정한 분류 정확도의 평균을 결과로 나타냈다.
초기 훈련 집합이 없는 경우의 제안한 방법을 평가하기 위해서, 선택하는 데이터 샘플의 수를 10부터 100까지 10개씩 증가시키며 선택하고, 선택한 데이터를 가지고 SVM과 MLP를 이용하여 테스트 데이터에 대한 분류 정확도를 측정하였다. 다음과 같은 4개의 알고리즘의 성능을 비교 하였다.
각 클래스에서 한 개씩의 데이터 샘플을 임의적으로 선택하여 초기 훈련 데이터를 구성하였다. Fig. 5의 알고리즘에서 k=1로 하여 한 개씩의 샘플을 추가하는 것을 100번 반복 하여 총 100개의 샘플을 훈련집합에 더하면서 SVM과 MLP 를 이용하여 분류 정확도를 측정하였다. 우리는 비교를 위해서, 2절에서 설명한 SVMactive[2], BvSB[7]와 임의 추출 (random sampling)을 사용하여 실험하였다.
5의 알고리즘에서 k=1로 하여 한 개씩의 샘플을 추가하는 것을 100번 반복 하여 총 100개의 샘플을 훈련집합에 더하면서 SVM과 MLP 를 이용하여 분류 정확도를 측정하였다. 우리는 비교를 위해서, 2절에서 설명한 SVMactive[2], BvSB[7]와 임의 추출 (random sampling)을 사용하여 실험하였다.

대상 데이터

실험은 Table 1에 설명된 UCI 데이터를 이용하였고, 본 논문에는 그 중 pandigit과 segment데이터에 대한 실험결과를 나타낸다.
UCI[16]의 4개의 데이터와 LLR[3]에서 사용된 USPS 이미지 데이터를 실험 데이터로 사용하였다. Table 1은 실험에 사용된 데이터 정보이다.
각 클래스에서 한 개씩의 데이터 샘플을 임의적으로 선택하여 초기 훈련 데이터를 구성하였다. Fig.

데이터처리

제안한 방법의 성능 평가를 위해 실제 데이터를 이용한 분류 정확도를 비교하였다. 5.
각 데이터 집합에 대해 전체 데이터를 6:4의 비율로 클래스 정보가 없는 집합(unlabeled pool)과 테스트 집합으로 나누었다. 성능측정을 위한 기본 분류기로 선형 커널을 사용한 libSVM[17]과 WEKA[18]의 다층 퍼셉트론(Multi-Layer Perceptron, MLP)을 이용하였고, 10번 실험을 반복하여 측정한 분류 정확도의 평균을 결과로 나타냈다.

성능/효과

이 평가 법은 군집간 거리는 멀고, 군집내 데이터간의 거리는 좁을 수록 작은 척도 값을 가진다. 군집간의 엔트로피를 측정한 결과는 워드 방법이 가장 높은 값을 나타냈다. 값이 높다는 것은 불순도가 가장 높은 결과를 나타내며, 이것을 군집에 적용하였을 경우, 균일한 크기의 군집들을 형성하는 것이 워드 방법이라는 것을 알 수 있다.
x축은 훈련 집합에 추가되는 샘플의 수, y축은 분류 정확도를 나타낸다. segment 데이터를 제외한 나머지 모든 데이터에서, 제안한 방법이 분류 정확도가 높은 것을 알 수 있다. 이것은 초기 클래스 정보를 가진 데이터가 주어지지 않은 상황에서 제안된 방법이 효과적이라는 것을 나타낸다.
segment 데이터를 제외한 나머지 모든 데이터에서, 제안한 방법이 분류 정확도가 높은 것을 알 수 있다. 이것은 초기 클래스 정보를 가진 데이터가 주어지지 않은 상황에서 제안된 방법이 효과적이라는 것을 나타낸다.
본 논문에서는 계층적 군집화를 이용하여, 초기 클래스 정보를 가진 훈련 데이터가 주어지지 않은 경우와 주어진 경우에 모두 적용 가능한 능동적 학습 방법을 제안하였다. 제안하는 방법은 군집화를 활용하여 잘 형성된 군집에서 각 군집을 대표하는 데이터를 선택함으로써 최소의 데이터 선택으로 전체 데이터 분포를 잘 반영할 수 있다. 초기 훈련 데이터가 없을 경우는 워드 방법을 이용한 군집화를 통해 데이터의 군집을 나누고 각 군집을 대표하는 데이터를 선택하여 전체 데이터 분포를 고려한 효과적인 데이터를 선택한다.
초기 훈련 데이터가 있을 경우, 형성된 덴드로그램을 이용하여 초기 훈련 데이터를 포함하지 않은 군집들에서 대표적인 데이터를 선택한다. 이것은 전체 데이터 분포와 초기 훈련 집합으로 주어진 클래스 정보를 가진 데이터 분포를 모두 고려한 방법으로 실험을 통하여 만족스러운 분류 정확도를 보였다. 또한 대부분의 능동적 학습 방법들이 사용되는 분류기에 의존하여 데이터 선택을 하지만 제안하는 방법은 사용하는 분 분류기와 독립적으로 사용될 수 있다는 장점이 있다.
이것은 전체 데이터 분포와 초기 훈련 집합으로 주어진 클래스 정보를 가진 데이터 분포를 모두 고려한 방법으로 실험을 통하여 만족스러운 분류 정확도를 보였다. 또한 대부분의 능동적 학습 방법들이 사용되는 분류기에 의존하여 데이터 선택을 하지만 제안하는 방법은 사용하는 분 분류기와 독립적으로 사용될 수 있다는 장점이 있다.

질의응답

핵심어	질문	논문에서 추출한 답변
	LLR의 단점은 무엇인가?	LLR[3]은 각 데이터 샘플과 주변 이웃들이 선형 결합 관계로 나타내진다는 가정 하에 전체 데이터에 대한 새로운 공간을 재구성 했을 때, 재구성 에러를 가장 최소화시키는 대표적 샘플들을 선택한다. 그러나 큰 규모의 데이터 집합에 대해 데이터와 이웃 데이터 간의 관계에 대한 반복적 행렬 연산으로 인해 시간적 소모가 매우 크다는 단점이 있다. Random Sampling and Backward Deletion[4]은 가장 단순하면서 대표적으로 데이터를 선택하는 방법인 임의추출법을 이용하여 전체 데이터 중 부분집합을 선택한 후 그 중에서 가장 불필요한 데이터 샘플을 선택하여 제거하는 것을 반복한다.
	능동적 학습의 목적은 무엇인가?	클래스 정보가 없는 데이터(unlabeled data, 언라벨 데이 터)에 비해서 클래스 정보가 있는 데이터(labeled data, 라벨 데이터)를 얻기 위해서는 많은 비용과 시간이 들게 된다. 능동적 학습(active learning)은 소수의 라벨 데이터로 구성된 훈련 집합이 주어진 경우에 분류기 학습에 가장 도움이 될만한 언라벨드 데이터를 선택하여 전문가에 의한 라벨링을 통해 훈련 집합에 포함시키는 과정을 반복함으로써 분류기의 성능을 향상시키는 것을 목적으로 한다[1].
	임의 추출 방법의 단점은 무엇인가?	굉장히 단순하며 빠르고 성능적으로도 평균은 도달하기 때문에, 여러 연구나 응용에서 사용되어지고 있다. 그러나 이것은 표현 그대로 임의적으로 추출하기 때문에 만족할만한 성능에 도달하기까지 비교적 많은 데이터를 필요로 한다.

참고문헌 (18)

B. Settles, "Active learning literature survey: Computer sciences technical report 1648", University of Wisconsin-Madison, 2009
S. Tong and D. Koller, "Support Vector Machine Active Learning with Applications to Text Classification", J. Machine Learning Research, Vol.2, pp.45-66, 2002.
L. Zhang, C. Chen, J. Bu, D. Cai, X. He, T. S. Huang, "Active Learning Based on Locally Linear Reconstruction", IEEE Trans. Pattern Anal. Machine Int., Vol.33, No.10, pp. 2026-2038, 2011.

상세보기
Hoyoung Woo, Cheong Hee Park, "Efficient Active Learning Method Based on Random Sampling and Backward Deletion", LNCS Vol.7751, 2013.
P. Tan, M. "Steinbach, and V. Kumar, Introduction to Data Mining", Addison Wesley, Boston 2006.
Woo H, C. H. Park, "Active Learning using Hierarchical Clustering and stratified sampling", KISSE proceeding, Vol.39, No.2(B), pp.216-218, 2012.
A. J. Joshi, F. Porikli, and N. Papanikolopoulos, "Multi-class active learning for image classification", in Proc. IEEE Int. Conf. Comput. Vis. Pattern Recognition, pp.2372-2379, 2009.
Y. Freund, H.S. Seung, E. Shamir, and N. Tishby, "Selective sampling using the query by committee algorithm", Machine learning, Vol.28(2-3), 1997.
P. Melville and R. Mooney. "Diverse ensembles for active learning", In Proceedings of the International Conference on Machine Learning (ICML), pp.584-591. Morgan Kaufmann, 2004.
N. Roy and A. McCallum. "Toward optimal active learning through sampling estimation of error reduction", In Proceedings of the International Conference on Machine Learning (ICML), pp.441-448. Morgan Kaufmann, 2001.
Ward, J. H., Jr., "Hierarchical Grouping to Optimize an Objective Function", Journal of the American Statistical Association, 48, 236-244, 1963.
N. Semmar, B. Bruguerolle, N. Simon, "Cluster Analysis: An Alternative Method for Covariate Selection in Population Pharmacokinetic Modeling", Journal of Pharmacokinetics and Pharmacodynamics, Vol.32, 2005.

상세보기
Davies, David L. Bouldin, Donald W. A "Cluster Separation Measure", IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-1 (2): 224-227. 1979.

상세보기
Ihara, Shunsuke., "Information theory for continuous systems", World Scientific. p. 2. ISBN 978-981-02-0985-8. 1993.
Christopher D. Manning, Prabhakar Raghavan & Hinrich Schutze. "Introduction to Information Retrieval". Cambridge University Press. ISBN 978-0-521-86571-5, 2008.
UCI Machine Learning Repository [Internet], http://archive.ics.uci.edu/ml
A Library for Support Vector Machines [Internet], http://csie.ntu.edu.tw/-cjlin/libsvm/
Machine Learning Group at University of Waikato [Internet], http://www.cs.waikato.ac.nz/ml/weka/

저자의 다른 논문 :

활용도 분석정보

상세보기

다운로드

내보내기

활용도 Top5 논문

해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다.
더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증