[논문]엔트로피 분포를 이용한 규칙기반 분류분석 연구

이정진; 박해기

doi:10.5351/ckss.2010.17.4.527

엔트로피 분포를 이용한 규칙기반 분류분석 연구
Rule-Based Classification Analysis Using Entropy Distribution 원문보기

한국통계학회 논문집 = Communications of the Korean Statistical Society, v.17 no.4, 2010년, pp.527 - 540

이정진 (숭실대학교 정보통계보험수리학과) , 박해기 (숭실대학교 정보통계보험수리학과)

초록
AI-Helper

규칙기반 분류분석(rule-based classification analysis)은 직관적인 이해가 쉽고 알고리즘이 복잡하지 않아 최근 대용량 데이터마이닝에 많이 이용되는 기법이다. 하지만 현재의 규칙기반 분석은 여러 개의 규칙들을 찾은후 이 규칙들을 단순히 다수결이나 또는 중요도의 가중 합으로서 새로운 데이터를 분류한다. 본 연구에서는 다항분포를 이용한 이항데이터의 분류분석 기법을 규칙 조합방법에 응용하고자한다. 다향분포의 추정을 위해서는 변형된 반복 비율 적합(iterative proportional fitting; IPF) 알고리즘을 이용하여 최대 엔트로피 분포(entropy distribution)를 찾는다. 시뮬레이션 실험 결과 이 방법은 두 집단의 데이터가 서로 유사한 경우 어느 정도 의미 있는 분류 결과를 보여주였다.

Abstract ▼ AI-Helper

Rule-based classification analysis is widely used for massive datamining because it is easy to understand and its algorithm is uncomplicated. In this classification analysis, majority vote of rules or weighted combination of rules using their supports are frequently used in order to combine rules. We propose a method to combine rules by using the multinomial distribution in this paper. Iterative proportional fitting algorithm is used to estimate the multinomial distribution which maximizes entropy constrained on rules' support. Simulation experiments show that this method can compete with other well known classification models in the case of two similar populations.

주제어

AI 본문요약
AI-Helper

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

문제 정의

Kantor과 Lee (1998), 이정진과 김수관 (2002) 이정진과 황준 (2003), 이정진 (2005)은 위와 같은 상황에서 표본 데이터의 주변확률분포와 최대 엔트로피 추정법(maximum entropy estimation)을 이용한 다항분포 모수의 추정을 연구하여 왔다. 본 연구에서는 규칙의 지지도를 이용하여 최대 엔트로피 추정법으로 다항분포 모수를 추정하고자 한다. 한 집단의 표본 데이터에서 찾아낸 N개의 규칙을 r₁,r₂, .
본 연구에서는 다항분포 확률모형을 이용한 규칙의 조합방법을 기존의 다수결이나 가중합을 이용하는 방법과 비교하여 보았다. 두 집단의 데이터가 유사하여 분류가 쉽지 않은 경우 다항분포 모형이어느 정도 경쟁력이 있다고 판단된다.
본 연구에서는 이러한 규칙 조합방법 대신에 저자가 그동안 연구해 온 다항분포를 이용한 이항데이터의 분류분석 기법을 응용하고자 한다. 2절에서는 일반적 분류분석 모형과 규칙기반 분류분석을 소개하고 현재 여러 규칙의 조합에 사용되는 방법의 문제점을 살펴본다.

가설 설정

- 최소 지지도가 커질수록 IPF의 정확도는 거의 모든 경우에 소폭 증가한다. 하지만 다수결이나 가중합에 의한 규칙기반 분류는 지지도가 증가하면 규칙의 수가 감소하기 때문에 정확도가 감소한다.
- 표본의 크기가 커질수록 IPF의 정확도는 증가한다. 이는 표본의 크기가 클 수록 모집단의 추정이 정확해 지기 때문으로 판단된다.
- 표본의 크기가 커질수록 각 분류 모형의 정확도는 증가한다.
- 표본의 크기는 각각의 모형에 관계없이 정확도에 큰 영향을 주지 않는다. 특히 변수의 수가 10인 경우 분류 정확도는 거의 비슷하다.

제안 방법

2절에서는 일반적 분류분석 모형과 규칙기반 분류분석을 소개하고 현재 여러 규칙의 조합에 사용되는 방법의 문제점을 살펴본다. 3절에서는 다항분포 모형을 이용한 베이즈 분류방법을 알아보고 반복 비율 적합 알고리즘을 이용한 다항분포 모수 추정 방법을 제안한다. 4절에서는 이러한 모형의 진단을 위하여 시뮬레이션으로 다른 모형과 비교한 결과를 살펴본다.
이 절에서는 기존의 다수결이나 가중합을 이용한 규칙기반 분류방법과 MLE 또는 IPF 알고리즘을 이용한 다항분포 모형의 규칙기반 분류방법을 시뮬레이션을 이용하여 비교하여 보았다. 그밖에 이항 데이터의 분류에 어느 정도 효과적이라고 알려져 있는 (Asparoukhov와 Krzanowski, 2001) 선형판별식(linear discriminant function), 의사결정나무(decision tree), k-근접이웃(k-nearest neighbor), 로지스틱 회귀(logistic regression), 지지벡터기계(supporting vector machine) 모형에 대해 같은 시뮬레이션 데이터를 이용하여 비교하여 보았다. 시뮬레이션 실험을 위한 데이터의 생성과 구체적인 실험방법은 다음과 같다.
IPF 알고리즘의 해의 존재성과 수렴성은 Ruschendorf (1995)와 Cramer (2000)에 의해 연구되었다. 본 논문에서는 이 알고리즘을 각 규칙의 표본비율을 이용하여 다항분포 모수를 반복적으로 추정하는 다음과 같은 형태로 변형하였다.
분포모형 1은 모집단 1(막대가 회색: pop1)을 지수분포(λ = 1.0), 모집단 2(막대가 검정색: pop2)는 지수분포(λ = 0.05)를 이용하였고, 분포모형 2는 모집단 1을 지수분포(λ = 0.01), 모집단 2는 지수분포(λ =0.01)의 대칭인 분포를 이용하여 표본을 생성하였다.
실험의 회수를 더 많이 할 수도 있으나 예비 실험결과 실험의 회수를 증가하면 표준오차는 어느 정도 감소하나 평균 정분류율은 거의 변하지 않아 전체 실험시간을 고려하여 10회로 정하였다.
이 절에서는 기존의 다수결이나 가중합을 이용한 규칙기반 분류방법과 MLE 또는 IPF 알고리즘을 이용한 다항분포 모형의 규칙기반 분류방법을 시뮬레이션을 이용하여 비교하여 보았다. 그밖에 이항 데이터의 분류에 어느 정도 효과적이라고 알려져 있는 (Asparoukhov와 Krzanowski, 2001) 선형판별식(linear discriminant function), 의사결정나무(decision tree), k-근접이웃(k-nearest neighbor), 로지스틱 회귀(logistic regression), 지지벡터기계(supporting vector machine) 모형에 대해 같은 시뮬레이션 데이터를 이용하여 비교하여 보았다.
접이웃 모형의 결과만 정리하였다. 마찬가지로 의사결정나무 모형도 3단계 및 5단계 모형에 대해 실험을 하였으나 결과가 큰 차이가 없어 3단계 모형의 결과만 정리하였다.
01), 모집단 2는 균등분포를 이용하여 표본을 생성하였다. 지수분포인 경우 무한대까지의 값을 가질 수 있으므로 최대값은 99.9퍼센타일(percentile)을 이용한 후 확률분포가 되도록 조정하였다.
IPF 알고리즘을 이용하는 다항분포 모수의 추정에는 변수의 수에 대한 제약은 크게 없지만 변수의 수가 증가하면 저장용량이 지수적으로 증가한다. 하지만 다른 분류모형은 변수의 수에 따라 실험시간 등 여러 가지 문제가 발생되어 본 실험에서는 비교를 위해 이항변수의 수 5개와 10개에 대하여만 우선적으로 실험하였다.

대상 데이터

표본은 각 모형에서 변수의 수에 따라 지수적으로 증가하는 모수의 수에 대략 1배수, 5배수 그리고 10배수의 표본을 추출하였다. 표본이 1배수인 경우 모수의 수와 표본의 수가 같아 보통의 통계적인 모수추정 방법은 적용하기가 힘들고, 10배수인 경우는 일반적인 통계모형의 적용이 가능하다 생각된다.

데이터처리

실험을 위해서 다수결이나 가중합을 이용하는 규칙기반 분류모형과 MLE 그리고 IPF 알고리즘은 C언어를 이용하여 직접 프로그램을 작성하였고 나머지 방법은 R 통계패키지를 이용하였다.

이론/모형

각각의 지지도에 대해 찾은 규칙을 이용하여 MLE 또는 IPF 알고리즘으로 다항분포의 모수를 추정한다.

성능/효과

일반적으로 표본의 크기가 커지면 여러 분류 모형의 정확도가 증가하고 비슷한 정확도를 보여준다. 종합하면 두 집단의 데이터가 서로 유사하여 분류 정확도가 전반적으로 떨어지는 경우는 IPF와 LDA, L REG 등이 경쟁할 만한 모형이고, 두 집단의 데이터가 확실히 구분되는 경우는 가중합(WRL)을 이용한 규칙기반 분류모형이 우수한 정확도를 보여준다.

후속연구

하지만 시뮬레이션 비교실험의 제약상 제한된 변수의 수와 표본에 대해서만 실험을 하였기 때문에 위와 같은 결론을 일반화하기 위해서는 좀 더 다양한 환경에서의 실험과 이론적인 연구가 뒷받침되어야 한다고 할 수 있다. 무엇보다도 다항분포를 이용한 분류모형의 평가는 다양한 상황에서 실제 현실데이터를 이용한 후 이루어질 수 있을 것이다.
모형 1과 모형 2의 중간 정도인 모형 3의 경우는 분류의 정확도가 70% 내외인데 다수결(MAJ) 보다는 IPF 알고리즘이, 그리고 이보다는 가중합(WRL)이 일반적으로 우수한 분류 정확도를 가진다. 왜 가중합이 모형 3의 경우 월등한 분류 정확도를 갖는지는 향후 연구해볼만한 과제이다. 그밖에 모형 3에서 관찰된 결과는 다음과 같다.
두 집단의 데이터가 유사하여 분류가 쉽지 않은 경우 다항분포 모형이어느 정도 경쟁력이 있다고 판단된다. 하지만 시뮬레이션 비교실험의 제약상 제한된 변수의 수와 표본에 대해서만 실험을 하였기 때문에 위와 같은 결론을 일반화하기 위해서는 좀 더 다양한 환경에서의 실험과 이론적인 연구가 뒷받침되어야 한다고 할 수 있다. 무엇보다도 다항분포를 이용한 분류모형의 평가는 다양한 상황에서 실제 현실데이터를 이용한 후 이루어질 수 있을 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	분류분석이란 무엇인가?	분류분석이란 집단이 결정되지 않은 미지의 한 데이터를 여러 개의 집단 중의 하나로 결정하는 기법이다. 통계학에서는 이를 판별분석(discriminant analysis)이라 하고, 기계학습(machine learning)을 연구하는 사람들은 계획된 기계학습(supervised learning)이라 부르기도 한다.
	규칙기반(rule-based) 분류모형에서 적절한 규칙을 찾는 방법으로 어떤 것들을 이용하는가?	규칙기반(rule-based) 분류모형은 표본 데이터에서 각 집단의 분류에 적절한 규칙들을 찾아낸 후 이를 이용하여 새로운 데이터를 분류한다. 적절한 규칙을 찾는 방법에는 선험적 알고리즘(apriori algorithm)과 같은 직접적인 방법 또는 의사결정나무 모형이나 신경망 모형 등과 같은 모형을 이용하기도 한다.
	분류분석 기법에는 어떤 모형이 있는가?	분류분석은 다양한 분야에서 응용되고 있는데 예를 들면 의사가 환자를 진찰하여 그 진찰기록으로 어느 병인지 분류하는 일, 이메일 제목을 이용하여 스팸메일을 가려내는 일, 백화점의 매장에 온 고객이 상품을 구매할 고객인지 구별하는 일 등이다. 분류분석 기법에는 의사결정나무(decision tree), 베이즈(Bayesian) 분류, 신경망(neural network), 규칙기반(rule-based) 분류, 인접이웃(nearest neighbor) 분류, 지지벡터기계(support vector machine), 통합기법(ensemble method) 등 다양한 모형이 있다. 여러 가지 분류분석 모형은 서로 장단점을 가지고 있어 주어진 문제에 대해 가장 적합한 모형을 찾는 것이 중요하다.

참고문헌 (12)

이정진 (2005). Discriminant analysis of binary data with multinomial distribution by using the iterative cross entropy minimization, , 12, 125-137.

원문보기 상세보기
이정진, 김수관 (2002). Classification analysis in information retrieval by using Gauss patterns, , 9, 1-11.

원문보기 상세보기
이정진, 황준 (2003). Discriminant analysis of binary data by using the maximum entropy distribution, , 10, 909-917.

원문보기 상세보기
Asparoukhov, O. K. and Krzanowski, W. J. (2001). A comparison of discriminant procedures for binary variables, Computational Statistics and Data Analysis, 38, 139-160.

상세보기
Cramer, E. (2000). Probability measures with given marginals and conditionals: I-projections and conditional iterative proportional fitting, Statistics & Decisions, 18, 311-329.
Duda, R. O., Hart, P. E. and Stork, D. G. (2001). Pattern Classification, Wiley, New York.
Han, J. and Kamber, M. (2000). Data Mining Concepts and Technique, Elsevier.
Ireland, C. T. and Kullback, S. (1968). Contingency tables with given marginals, Biometrika, 55, 179-188.

상세보기
Kantor, P. B. and Lee, J. J. (1998). Testing the maximum entropy principle for information retrieval, Journal of American Society for Information Science, 49, 557-566.

상세보기
Lachenbruch (1981). Discriminant Analysis, Prentice Hall.
Liu, B., Hsu, W. and Ma, Y. (1998). Integrating classification and association rule mining, Proceeding 1998 International Conference Knowledge Discovery and Data Mining, 80-86, New York, August 1998.
Ruschendorf, L. (1995) Convergence of the iterative proportional fitting procedure, The Annals of Statistics, 23, 1160-1174.

상세보기

저자의 다른 논문 :

표제어: 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

연합인증