선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 본 논문에서는 기존의 유전알고리즘을 이용한 k-NN 분류기의 최적화 방법에서 염색체의 표현 방식을 변형하여 k-NN의 분류성능 및 효율성을 높이기 위한 변수선택, 변수가중치 및 최근접 이웃 수 k의 선택을 동시에 고려하는 새로운 알고리즘을 제안하였다. 사용한 염색체 표현 방식은 Tahir 등 (2007)에 의해서 소개된 타부 탐색에서 사용된 인코딩 방법을 적용하여 염색체를 세 부분으로 구분하고 각각 다른 코딩방법을 사용하였다.
- 본 연구에서는 우수한 전역탐색기능과 뛰어난 정확도를 가지는 유전 알고리즘을 이용하여 k-NN에서 최적의 변수선택 및 가중치, k값의 선택을 동시에 하는 분류방법을 제안하였다. 전체적으로 다양한 실제 자료에 대하여 적용한 결과 자료의 규모에 상관없이 제안 알고리즘을 이용한 분류방법이 기존의 여러 분류기들에 비하여 분류정확도 및 효율성이 우수한 것으로 나타났다.
제안 방법
- 분할하였다. 각 자료마다 5번씩의 반복을 통하여 최적으로 추정된 k, 선택된 변수개수, 목적함수 값, 검증자료의 오분류율(%)을 살펴보았으며 그 결과는 표 2와 같다. 모든 자료에서 적합도 값이 비교적 일정하게 수렴하는 것을 볼 수 있으며 최적의 k값도 하나의 값으로 수렴하였다.
- 임시집단이 N개의 염색체로 채워질 때까지 위의 연산은 반복된다. 근접 이웃수 &를 선택하기 위한 염색체의 세 번째 부분의 교배는 임의로 선택된 부모 염색체 쌍에서 左값이 다르다면 임의로 한 값을 선택하고 左값이 동일하다면 부모의 유전자가 그대로 자손으로 내려오는 교배방법을 이용하였다.
- 이진코딩 염색체의 각 비트 1은 대응되는 변수가 선택됨을, 0은선택되지 않음을 의미한다. 두 번째, 변수 가중을 위한 염색체(wp부터 叱까지)는 1.0부터 10.0까지의 실수값의 열을 갖는 실수코딩(real encoding)방법을 사용했다. 총 /개의 실수값은 각각의 대응되는 변수의 가중치를 나타내며 변수선택 염색체의 값이 1 인 변수들의 가중치만사용된다.
- ) 시점의 모집단 P(f) 내의 개체들을 선택하고 교배급원을 형성해준다. 본연구에서는룰렛휠 선택 방법을 이용하여 초기모집단으로부터 선택된 개체를 얻었다.
- 첫 번째, 변수선택을 위한 염색체(&에서 可까지)에서는 총 Z개의 0 또는 1로 이뤄진 이진 코딩(binary encoding)방법을 사용하였다. 이진코딩 염색체의 각 비트 1은 대응되는 변수가 선택됨을, 0은선택되지 않음을 의미한다.
- 5 (Quinlan, 1993)와 일반적인 农NN 분류기와 Tahir (2007)의 .타부탐색 农NN 분류기(TS/农NN), 선형 판별분석, 베이지안 방법인 나이브 베이즈분류기(Naive Bayes classifier)이며 제안된 방법 이외의 모든 방법들에서는 설명변수들을 모두 사용하였다.
대상 데이터
- 각각의 자료에 대하여 살펴보면 Diabetes는 존스홉킨스 대학(The Johns Hopkins University)에서 제공한 피마족 인디언(Pima Indian)의 당뇨병 진단 자료로 임신횟수, 최소혈압, 혈청 인슐린, 나이 등을 포함한 8개의 변수들로 구성되어 있다. 모든 변수들은 연속형 변수이고 결측값(missing value)은 없다.
- 분류 성능 비교를 위하여 Statlog와 UCI의 자료 중에서 설명변수의 수가 8, 14, 34, 60개인 4개의 자료(표 1)를 사용하였다.
데이터처리
- 이 장에서는 몇 가지 실제 자료를 이용하여 기존의 연구들에서 사용했던 방법들과 본 논문에서 제안한 유전알고리즘을 이용하여 변수선택 및 가중치, 그리고 k값을 동시에 고려하는 방법을 적용한 결과를 교차타당성 방법을 통하여 비교하였다. 모든 프로그램은 日을 이용하여 작성하였다.
이론/모형
- k-NN의 효율성을 높이기 위해 변수선택, 변수가중치 및 최근접 이웃수 를 동시에 고려하는 염색체의 표현 방식은 기본적으로 변수선택과 변수가중치를 동시에 고려하는 Tahir 등 (2007)이 제시한 타부 탐색 방법에서 사용한 인코딩 방법을 적용하였다.
- 선택을 동시에 고려하는 새로운 알고리즘을 제안하였다. 사용한 염색체 표현 방식은 Tahir 등 (2007)에 의해서 소개된 타부 탐색에서 사용된 인코딩 방법을 적용하여 염색체를 세 부분으로 구분하고 각각 다른 코딩방법을 사용하였다.
- 단, Sonar 자료의 경우 과잉적합을 피하기 위해 반복세대수를 300으로 설정하였다. 이 값들은 기존의 연구결과와 비교를 위하여 Tahir 등 (2007)과 Kudo와 Sklansky (2000)에서 사용된 값을 그대로 적용하였다. 반복세대수의 경우에는 자료별로 반복 실험을 통하여 수렴 여부를 판단한 후 수렴하도록 조정하였다.
성능/효과
- 변수 선택 방법들 간의 직접적 인 비교를 위하여 표 4의 오분류율과 변수개수를 이용하여 목적함수값을 계산하였고 그 결과는 그림 3과 같다. Australian 자료를 제외한 세 개의 자료에서 다른 변수선택방법들에 비해 제안 알고리즘을 이용한분류방법의 목적함수값이 높은 것으로 나타나 목적함수의 측면에서도 효율적임을 알 수 있다.
- 서론에서 언급한 것과 같이 SFS, SFFS와 같은 순차적 알고리즘은 소규모 자료(Diabetes, Australian)에서 다른 분류 방법과 비슷한 성능을 보였지만, 변수개수가 큰 중/대규모 자료(Ionosphere, Sonar)에서는 지역 최적해에 빠지는 문제가 발생하므로 타부탐색과 유전 알고리즘과 같은 휴리스틱 알고리즘을 이용한 분류기의 성능이 우수했다. Ionosphere 자료에서는 제안 알고리즘의 경우 34개의 변수 중에 단 6개의 선택된 변수로써 97.2%의 높은 분류정확도를 보였고 Sonar 자료에서는 60개의 변수 중에 22개의 선택된 변수로써 98.4%의 높은 분류 결과를 보였다.
- 먼저, 제안 알고리즘을 이용한분류기의 분류성능은 Australian 자료를 제외한세 자료에서 가장 우수함을 알 수 있으며 특호], 변수의 개수가 많은 자료(Ionosphere, Sonar)에서 다른 변수선택방법보다 상대 적으로 매우 작았다. 선택된 변수의 개수도 다른 방법과 비슷하거 나 작으므로 효율성도 우수한 것으로 볼 수 있다.
- 각 자료마다 5번씩의 반복을 통하여 최적으로 추정된 k, 선택된 변수개수, 목적함수 값, 검증자료의 오분류율(%)을 살펴보았으며 그 결과는 표 2와 같다. 모든 자료에서 적합도 값이 비교적 일정하게 수렴하는 것을 볼 수 있으며 최적의 k값도 하나의 값으로 수렴하였다. 하지만 선택된 변수의 개수와 변수별 가중치에는 차이가 있는 것으로 나타나 다중 해가 존재함을 알 수 있다.
- 총 /개의 실수값은 각각의 대응되는 변수의 가중치를 나타내며 변수선택 염색체의 값이 1 인 변수들의 가중치만사용된다. 세 번째, 최적의 左값을 찾기 위한 염색체 부분에는 1, 3, 5, 7 중 하나의 값을 갖도록 하였다. 이론적으로는 k값으로 모든 홀수가 가능하지만 이를 제한하여 7보다 작거나 같은 값으로 한정하였으나 필요에 따라 더 큰 값을 갖도록 할 수 있다.
- 실험결과를 보면 k-NN에서 유전 알고리즘을 이용하여 최적화 시킨 제안 알고리즘의 분류정확도가 모든 자료에서 우수한 성능을 보였다. 사용한 오분류율은 각 자료마다 5회 반복 실험한 결과의 평균 오분류율이다.
- 6%로써 타부탐색법을 이용한 분류보다도 우수한 결과를 보였다. 위 표에서 C4.5, k-NN, 판별분석, 나이브베이즈 방법을 이용한 분류는 각 자료의 모든 변수를 이용한 분류결과이므로 최소의 변수 개수로 최소의 오분류율을 보인 제안 알고리즘의 효율성 또한 매우 우수함을 알 수 있다.
- 최적의 변수선택 및 가중치, k값의 선택을 동시에 하는 분류방법을 제안하였다. 전체적으로 다양한 실제 자료에 대하여 적용한 결과 자료의 규모에 상관없이 제안 알고리즘을 이용한 분류방법이 기존의 여러 분류기들에 비하여 분류정확도 및 효율성이 우수한 것으로 나타났다. 제안 알고리즘에서 고려한 변수 선택 및 가중치 그리고 k 중에서 左값은 Australian 자료를 제외하면 대부분의 경우에 기존의 방법들과 같은 값이 선택되어 상대적으로 중요성 이 낮은 것으로 보인다.
- 개수가 각각 34, 60개 인 Ionosphere, Sonar 자료에서는 유전 알고리즘과 타부탐색법을 农NN에 결합한 두 분류기(제 안 방법 , TS佐NN)의 성능이 월등히 우수했다. 특히 Ionosphere 자료에서 제 안 알고리즘의 오분류율은 3.0%, Sonar 자료에서 제안 알고리즘의 오분류율은 1.6%로써 타부탐색법을 이용한 분류보다도 우수한 결과를 보였다. 위 표에서 C4.
- 제안 알고리즘에서 고려한 변수 선택 및 가중치 그리고 k 중에서 左값은 Australian 자료를 제외하면 대부분의 경우에 기존의 방법들과 같은 값이 선택되어 상대적으로 중요성 이 낮은 것으로 보인다. 하지만 같은 k값의 경우에도 제안알고리즘이 기존의 방법들에 비하여 효율적인 것으로 나타나 선택된 변수들과 이들에 대한 가중치의 차이가 분류기의 성능에 많은 영향을 주는 것을 알 수 있다.
- 조정계수 a값 및 여타 유전알고리즘의 모수들에 대한 다양한 시뮬레이션을 통하여 주어진 자료에 최적인 모수들의 조율이 가능할 것이다. 하지만 제안 알고리즘은 여러 가지를 동시에 고려하는 방법인 만큼 수렴속도도 늦고 각 자료마다 지역최적해에 빠지지 않고 전역최적해에 수렴하기 위한 반복세대수, 모집단 크기, 재생산을 위한 방법 선택, 교배방법의 선택, 돌연변이 비율 등을 결정하는 것은 간단하지 않을 것으로 보인다.
후속연구
- 끝으로, 유전 알고리즘은 전역적 탐색방법으로 전체 공간에 대한 탐색을 통해 효율적으로 최적해에 수렴하는 특성을 갖고 있고, 타부 탐색법은 국소적 탐색방법으로 최적해 근방에서 시작하면 효율적으로 최적해에 수렴하는 특성을 갖고 있으므로 이 두 가지 방법을 적절히 결합시키는 방법도 연구할 가치가 있을 것이다.
- 01 로 고정한 결과만을 포함하였으나 계수 값에 따라최적의 변수, 가중치 그리고 k값에 많은 차이가 있을 것으로 예상된다. 조정계수 a값 및 여타 유전알고리즘의 모수들에 대한 다양한 시뮬레이션을 통하여 주어진 자료에 최적인 모수들의 조율이 가능할 것이다. 하지만 제안 알고리즘은 여러 가지를 동시에 고려하는 방법인 만큼 수렴속도도 늦고 각 자료마다 지역최적해에 빠지지 않고 전역최적해에 수렴하기 위한 반복세대수, 모집단 크기, 재생산을 위한 방법 선택, 교배방법의 선택, 돌연변이 비율 등을 결정하는 것은 간단하지 않을 것으로 보인다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.