[논문]혼합정수 선형계획법 기반의 비선형 패턴 분류 기법

김광수; 류홍서

혼합정수 선형계획법 기반의 비선형 패턴 분류 기법
An MILP Approach to a Nonlinear Pattern Classification of Data 원문보기

대한산업공학회지 = Journal of the Korean Institute of Industrial Engineers, v.32 no.2, 2006년, pp.74 - 81

김광수 (고려대학교 산업시스템정보공학과) , 류홍서 (고려대학교 산업시스템정보공학과)

Abstract ▼ AI-Helper

In this paper, we deal with the separation of data by concurrently determined, piecewise nonlinear discriminant functions. Toward the end, we develop a new $l_1$-distance norm error metric and cast the problem as a mixed 0-1 integer and linear programming (MILP) model. Given a finite number of discriminant functions as an input, the proposed model considers the synergy as well as the individual role of the functions involved and implements a simplest nonlinear decision surface that best separates the data on hand. Hence, exploiting powerful MILP solvers, the model efficiently analyzes any given data set for its piecewise nonlinear separability. The classification of four sets of artificial data demonstrates the aforementioned strength of the proposed model. Classification results on five machine learning benchmark databases prove that the data separation via the proposed MILP model is an effective supervised learning methodology that compares quite favorably to well-established learning methodologies.

주제어

AI 본문요약
AI-Helper

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

문제 정의

그리고 이렇게』와 B의 영역을 구분할 수 있도록 k개의 독립된 의사결정 곡면으로부터 조각별 비선형 곡모델 개발에 대한 이해를 돕기 위해를 제시하였다.
본 논문에서는 3가 선형을 이루는 곡면들을 편의상 f(3L, X) 로 나타내고 이러한 곡면들을 동시에 矽개 이용한 비선형 패턴 분류 모델을 제시할 것이다. 모델 개발에 앞서 矽개의 곡면을 동시에 이용하여 얻을 수 있는 의사결정 곡면들의 예를 <Figure 1>에서 제시하였다.
본 논문에서는 k-조각별 비선형 분류를 위하여 MILP 모델인 kPNC 모델을 개발하였다. kPNC 모델은 비선형 함수를 동시에 k 개 사용하되, 각 함수의 상호 작용을 고려할 수 있기 때문에 분리 능력이 높으면서도 가장 정확한 의사결정 곡면을 제공해준다.
본 논문에서는 데이터를 구성하는 집합의 개수가 두 개인이진 분류를 패턴 분류와 동일한 문제로 간주하고 이진 분류를 위한 혼합정수 선형계획법(Mixed Integer and Linear Programming : MILP) 기반의 비선형 패턴 분류 기법을 제시할 것이다. 이는 대부분의 패턴 분류 문제들이 이진 분류 문제에 속하며, 다범주 분류 문제의 경우도 이진 분류의 연속적인 적용으로 해결될 수 있기 때문이디(Ullman, 1973).
본 논문에서는 탐욕적 기법의 한계 및 과대적합 문제점을 해결하기 위해 k 개의 비선형 곡면을 동시에 이용하여 의사결정 곡면을 구축하는 패턴 분류 기법을 개발하였다 이를 위해 Mangasarian(1965) 의 연구를 바탕으로 패턴 분류에 사용되는 곡면을 단순한 선형 곡면에서 비선형 곡면으로 확장시켰으며 k 개의 비선형 곡면이 동시에 사용되는 경우를 위해 .norm 에러 측정 지표를 새롭게 설계하였고 마지막으로 이를 이용하여 새로운 MILP 모델을 개발하였다.
하지만 (Ryoo and Sahinidis, 2003)에서 나타난 바와 같이 위의 MP 분류 모델은 그 해를 구하기가 어려우며 더욱이 관련된 알고리즘과 소프트웨어들이 부족하다는 단점이 있다 따라서 이러한 MP 모델의 단점을 피하고 새로운 모델을 개발하기 위해 본 논문에서는 새로운 에러 측정 지표를 설계하였다

가설 설정

proof.『 먼저 (挤, 「y_*, z_*, u*, 『을 (kPNC) 모델의 최적해라 가정하자. 이 최적해의(3如_*, y_*, z_*)을 이용하여(3_*, 7_*, y_*, z_*, u_*, 挤) 과 동일하거나 새로운 최적해를 구할 수 있는데 그 방법은 다음과 같다.

제안 방법

3 장에서는 kPNC 모델을 이용한 기계 학습의 장점을 보이기 위해 패턴 분류의 다른 기계 학습 기법인 MSM, LAD, SVM 과 비교하였다. MSM 은 (Nakayama and Kagaku, 1998)에서 제시된 LP 모델 및 기법을 이용하였고 LAD 는 (Ryoo and Jang, 2005) 의 MILP 모델을 이용한 패턴 분류 기법을 적용하였으며, SVM 은 Mangasarian(2000) 이 제시한 LP 모델을 사용하였다.
개의 비선형 곡면이 동시에 사용되는 경우를 위해 .norm 에러 측정 지표를 새롭게 설계하였고 마지막으로 이를 이용하여 새로운 MILP 모델을 개발하였다. 이 MILP 모델을 이용한 기계학습은 여러 개의 비선형 곡면을 동시에 이용하되 각 곡면의 상호 작용을 고려할 수 있기 때문에 데이터에 대한 분리능력 (separability) 이 높으면서도 간결하고 정확한 의사결정 곡면을 구축할 수 있다.
본 논문의 구성은 다음과 같다 다음 장에서는 k -조각별 비선형 분류를 위한 MILP 모델(이하 kPNC 모델)을 개발하고, 3 장과 4장에서는 kPNC 모델을 이용한 패턴 분류 기법과 다른 기계학습 기법들(MSM, LAD, SVM) 을 비교하였다. 이를 위해 MSM, LAD, SVM, kPNC 를 2차원 상에서 인위적으로 만든 문제들과(3장), 기계학습 데이터베이스(Murphy and Aha, 1994) 에서선택한 다섯 개의 표준(benchmark) 데이터베이스;4장)에 적용하여 학습 및 테스트 정확도를 도출하였다 그리고 마지막 5 장에서는 이러한 결과들을 바탕으로 kPNC 모델을 이용한 기계학습의 우수성을 정리하고 향후 연구 과제에 대 해 제시하였다
우리는 학습 및 테스트를 위하여 각 데이 터베이 스에 속한 전체 원소들 중에서 P% (, e{50, 80}) 를 무작위로 선택하여 학습 문제를 만들고 나머지 데이터를 가지고 테스트 문제를 구성하였다. 이렇게 만들어진 학습 및 테스트 문제에 MSM, LAD, SVM, kPNC 기법을 적용하여 정확도를 구하였으며 이러한 과정을 30번 반복하여 정확도에 대한 평균 및 표준편차를 구하였다 우리는 이 과정에서 LP 및 MILP의 해법을 위해 ILOG CPLEX 9.
기법들(MSM, LAD, SVM) 을 비교하였다. 이를 위해 MSM, LAD, SVM, kPNC 를 2차원 상에서 인위적으로 만든 문제들과(3장), 기계학습 데이터베이스(Murphy and Aha, 1994) 에서선택한 다섯 개의 표준(benchmark) 데이터베이스;4장)에 적용하여 학습 및 테스트 정확도를 도출하였다 그리고 마지막 5 장에서는 이러한 결과들을 바탕으로 kPNC 모델을 이용한 기계학습의 우수성을 정리하고 향후 연구 과제에 대 해 제시하였다

대상 데이터

본 논문에서 개발된 kPNC 모델을 이용한 기계학습의 학습능력을 테스트하고 MSM, LAD, SVM 과의 비교를 위해서 기계학습 연구에 통용되는 다섯 개의 현실 데이터베이스를 Murphy and Aha(1994) 로부터 다운로드 받았다. 그리고 다섯 개의 현실 데이터베이스를 실험에 적용하기 위해 각 데이터 집합으로부터 잃어버린 항목이 있는 데이터는 삭제하였다 <Table 2>는 다섯 개의 데이터베이스에 대한 정보를 정리한 것이다.

데이터처리

이렇게 만들어진 학습 및 테스트 문제에 MSM, LAD, SVM, kPNC 기법을 적용하여 정확도를 구하였으며 이러한 과정을 30번 반복하여 정확도에 대한 평균 및 표준편차를 구하였다 우리는 이 과정에서 LP 및 MILP의 해법을 위해 ILOG CPLEX 9.0(2003) 을 이용하였다. kPNC 의 경우, MILP 의 해법에서 분지한계기법의 노드 수를 최대 10, 000개로 제한하고 가장 좋은 해를 이용하여 PNC 분류자를 구축하였다.

이론/모형

MSM 은 (Nakayama and Kagaku, 1998)에서 제시된 LP 모델 및 기법을 이용하였고 LAD 는 (Ryoo and Jang, 2005) 의 MILP 모델을 이용한 패턴 분류 기법을 적용하였으며, SVM 은 Mangasarian(2000) 이 제시한 LP 모델을 사용하였다.
그런 의미에서 두 개의 선형 곡면을 동시에 이용한 Bennett and Mangasarian(1994) 의 겹선형 분리 (bilinear separa tion) 는 기존의 선형계획법을 이용한 탐욕 접근법 greedy ap- proach)과는 근본적으로 다르다. 이 연구에서 그들은 겹 선형분리 문제를 세 종류의 겹선형계획법Bilinear Programming : BP) 기반의 모델로 구축하였고, 그로부터 두 개의 선형 곡면으로 구성되는 의사결정 곡면을 구하였다 하지만 겹 선형계획법은 특별히 어려운 문제로 알려진 곱셈 계획법Multiplicative Programming : MP) 에 속하여 해법이 어렵기 때문에(Ryoo and Sahinidis, 2003), 그들은 겹선형계획법 모델에 대한 해법으로 일종의 휴리스틱인 Frank and Wolfe(1956) 의 알고리즘을 이용하였을 뿐 전역 최적해법을 이 용하지 는 않았다

성능/효과

있음을 주목할 수 있다. 이 결과는 위의 데이터에 잡음이 포함되어 있다는 점을 감안할 때 SVM 이 잡음에 민감한 기법이라는 것과 LAD 가 위의 세 학습기법 중 잡음에 적게 영향을 받는 기법이라는 것으로 해석할 수 있다 마지막으로 MSM 은 탐욕적 기법의 한계로 인하여 과도하게 복잡한 의사결정 곡면을 구축하는 문제점과 데이터의 100% 적합으로 인한 과대 적합 문제점을 가지고 있는데 이로 인해 LAD 및 kPNC 에 비해 일반화능력이 떨어지는 것 같다
kPNC 모델은 비선형 함수를 동시에 k 개 사용하되, 각 함수의 상호 작용을 고려할 수 있기 때문에 분리 능력이 높으면서도 가장 정확한 의사결정 곡면을 제공해준다. 이러한 kPNC 모델의 우수성을 살펴보기 위해 MSM, LAD, SVM 과 비교하였는데, kPNC 모델을 이용한 새로운 기법은 다른 기법들보다 단순하고 정 확한 분류자를 구축하였으며 가장 우수한 일반화 능력을 나타내 었다

후속연구

앞으로 수행되어야 할 연구는 kPNC 모델의 해법 개발에 관한 것이다. 현재 kPNC 모델의 해법으로 MILP 관련 전역 최적화 기법인 분지한계기법을 사용하고 있는데 LP 완화모델이 좋은 한계를 제공하지 못하는 어려움이 있다 따라서 이에 대한 해결을 위해 절단면 기법 분할 기법에 관한 연구를 수행할 것이며, 데이터의 감소를 위한 효율적인 군집화 기법 및 지지 벡터 추출 기법 개발에 대한 연구가 진행될 것이다
것이다. 현재 kPNC 모델의 해법으로 MILP 관련 전역 최적화 기법인 분지한계기법을 사용하고 있는데 LP 완화모델이 좋은 한계를 제공하지 못하는 어려움이 있다 따라서 이에 대한 해결을 위해 절단면 기법 분할 기법에 관한 연구를 수행할 것이며, 데이터의 감소를 위한 효율적인 군집화 기법 및 지지 벡터 추출 기법 개발에 대한 연구가 진행될 것이다

참고문헌 (26)

Al-Khayyal, F. A. and Falk, J. E. (1983), Jointly constrained biconvex programming, Mathematics of Operations Research, 8(2), 273-286

상세보기
Bennett, K. P. (1993), Decision tree construction via linear programming, In Proceedings of the 9th Conference on Artificial Intelligence for Applications, Orlando, Florida, 212-218
Bennett, K. P. and Mangasarian, O. L. (1992), Robust linear programming discrimination of two linearly inseparable sets, Optimization Methods and Software, 1, 23-34

상세보기
Bennett, K. P. and Mangasarian, O. L. (1994), Bilinear separation of two sets in n-space, Computational Optimization and Applications, 2, 207-227

상세보기
Boros, E., Hammer, P. L., Ibaraki, T., Kogan, A., Mayoraz, E., and Muchnik, I. (2000), An implementation of logical analysis of data, IEEE Transactions on Knowledge and Data Engineering, 12(2), 292-306

상세보기
Bradley, P. S. and Mangasarian, O. L. (2000), Massive data discrimination via linear support vector machines, Optimization Methods and Software, 13, 1-10

상세보기
Carter, C. and Catlett, J. (1997), Assessing credit card applications using machine learning, IEEE Expert, Fall, 71-79
Falk, J. E. and Lopez-Cardona, E. (1997), The surgical separation of sets, Journal of Global Optimization, 11, 433-462
Frank, M. and Wolfe, P. (1956), An algorithm for quadratic programming, Naval Research Logistics Quarterly, 3, 95-110

상세보기
ILOG CPLEX 9.0 User's Manual, ILOG CPLEX Division, Incline, Nevada, October 2001
Mangasarian, O. L. (1965), Linear and nonlinear separation of patterns by linear programming, Operations Research, 13, 444-452

상세보기
Mangasarian, O. L. (1968), Multisurface method of pattern separation, IEEE Transactions on Information Theory, 14(6), 801-807

상세보기
Mangasarian, O. L. (1993), Mathematical programming in neural networks, ORSA Journal on Computing, 5, 349-360

상세보기
Mangasarian, O. L. (2000), Generalized support vector machines, In A. Smola, P. Bartlett, B. Scholkopf and D. Schuurmans, editors, Advances in Large margin classifiers, MIT Press, 135-146
Mangasarian, O. L. and Musicant, D. R. (2000), Data discrimination via nonlinear generalized support vector machines, In M. C. Ferris, O. L. Mangasarian, and J.-S. Pang, editors, Complementarity: Applications, Algorithms and Extensions, chapter 1. Kluwer Academic Publishers
Mangasarian, O. L., Setiono, R., and Wolberg, W. H. (1990), Pattern recognition via linear programming : Theory and application to medical diagnosis, Large-Scale Numerical Optimization, 22-31
Mangasarian, O. L., Street, W. N., and Wolberg, W. H. (1995), Breast cancer diagnosis and prognosis via linear programming, Operations Research, 43(4), 570-577

상세보기
Megiddo, N. (1988), On the complexity of polyhedral separability, Discrete and Computational Geometry, 3, 325-337

상세보기
Murphy, P. M. and Aha, D. W. (1994), UCI repository of machine learning databases, Department of Computer Science, University of California at Irvine, CA
Nakayama, H. and Kagaku, N. (1998), Pattern classification by linear goal programming and its extensions, Journal of Global Optimization, 12, 111-126
Osuna, E., Freund, R., and Girosi, F. (1997), Training support vector machines: an application to face detection, In IEEE Conference on Computer Vision and Pattern Recognition, Puerto Rico, 130-136
Ryoo, H. S. and Jang, I.-Y. (2005), MILP approach to pattern generation in logical analysis of data, Machine Learning, submitted
Ryoo, H. S. and Sahinidis, N. V. (2001), Analysis of bounds for multilinear functions, Journal of Global Optimization, 19(4), 403-424
Ryoo, H. S. and Sahinidis, N. V. (2003), Global optimization of multiplicative programs, Journal of Global Optimization, 26, 387-418
Ullman, J. R. (1973), Pattern recognition techniques, Crane, London
Wolberg, W. H. and Mangasarian, O. L. (1990), Multisurface method of pattern separation for medical diagnosis applied to breast cytology, Proceedings of the National Academy of Sciences, 87, 9193-9196

저자의 다른 논문 :

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

연합인증