선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 목적 함수는 현재 세대가 얼마나 해에 근접한지를 판단 할 수 있는 기준으로서 유전자 알고리즘의 전체 성능을 좌우한다.
- 본 논문에서는 다양한 목적 함수를 사용하는 다목적 유전자 알고리즘이 하나의 목적 함수에 의해 지역 최적해에 수렴 할 때 또 다른 목적 함수가 이를 방지할 수 있기 때문에 이를 문서 클러스터링에 적용해보고 실험적으로 증명하고자 한다.
- 본 논문에서는 현재까지 문서 클러스터링 연구에 있어 다목적 유전자 알고리즘을 적용한 사례가 알려지지 않는 가운데 처음으로 다목적 유전자 알고리즘을 문서 클러스터링에 적용해 보았다. 적용한 결과 k-means 클러스터링과 유전자 알고리즘이 갖는 단점을 개선하여 성능이 향상됨을 알 수 있었다.
제안 방법
- 2) 유전자 인코딩 방식에 따라 문서 벡터와 매핑하여 적합도를 평가한다. 평가 후 파레토 최적해를 생성하고 NSGA-Ⅱ기법을 사용하여 염색체를 선택한다.
- 적합도 평가에서는 일차적으로 염색체에 대하여 문서 클러스터 행렬이 구성된다. 구성된 후 K 개의 문서 클러스터 행렬에 목적 함수를 적용하여 생성된 문서 클러스터가 최적인지 평가하게 된다.
- 다음에는 NSGA-Ⅱ기법을 사용하여 과 같이 같은 순위에 있는 비지배해들을 하나의 파레토 프론트에 위치시키고 밀집도를 비교하여 토너먼트 선택 연산을 수행한다.
- 본 논문의 구성은 2장에서는 다목적 최적화 문제 및 다목적 유전자 알고리즘에 대하여 설명하고, 3장에서는 제안하는 다목적 유전자 알고리즘을 이용한 문서 클러스터링 방법에 대하여 논의한다. 마지막으로 문서 클러스터링에 있어 세 가지 알고리즘(k-means 클러스터링, 유전자 알고리즘, 다목적 유전 알고리즘)을 비교 및 분석하였다.
- 목적 함수 공간에서 두 개의 목적 함수 평가값이 최대일 때를 가정하면 와 같이 최대화 방향의 비지배해들을 선정하여 파레토 최적해를 생성한다.
- 문서 클러스터링을 위하여 본 논문에서 적용한 다목적 유전자 알고리즘인 NSGA-Ⅱ의 시간 복잡도는 O(MN2)이며 M은 목적 함수의 개수, N은 개체수를 나타낸다. 이와 같이 클러스터링 인덱스를 목적 함수로 사용하는 다목적 유전자 알고리즘을 이용한 문서 클러스터링은 높은 계산 시간을 필요로 하므로 본 논문에서는 클러스터링 인덱스 중에 가장 간단한 CH(Calinski and Harabasz)[14]와 DB(Davis and Bouldin)[15]인덱스를 사용하였다.
- 본 논문에서 제안하는 다목적 유전자 알고리즘을 이용한 문서 클러스터링에서는 염색체의 적합도를 평가하기 위해 문서 클러스터 행렬을 구성하는 단계가 필요하다.
- 본 논문에서 제안하는 다목적 유전자 알고리즘을 이용한 문서 클러스터링은 문서 벡터를 구성하는 단계, 다목적 유전자 알고리즘을 이용하여 문서를 클러스터링하는 단계로 나누어지며 과 같다.
- 본 논문에서 진화 연산은 아래와 같이 선택 연산은 토너먼트 선택, 교배 연산은 다점 교배 연산, 돌연변이 연산은 확률적 돌연변이 연산을 사용하였다[16].
- 본 논문에서는 k-means 클러스터링과 유전자 알고리즘, 그리고 다목적 유전자 알고리즘 사용하였을 때의 클러스터링 성능을 비교 및 분석하였다. 유전자 알고리즘과 다목적 유전자 알고리즘은 300개의 동일한 개체수와 세대수가 1,000이거나 성능 향상 없이 20번의 세대가 진행될 때 알고리즘이 종료되도록 설정하였다.
- 본 논문에서는 k-means 클러스터링을 포함한 단일의 목적 함수를 갖는 유전자 알고리즘 그리고 다수의 목적 함수를 갖는 다목적 유전자 알고리즘을 문서 클러스터링에 적용하여 비교해 보았다. 유전자 알고리즘에서는 목적 함수로 사용된 클러스터링 인덱스에 따라 성능의 차이가 보였다.
- 본 논문에서는 과 같이 초기 설정되는 클러스터의 수 1∼K 범위의 정수로 유전자를 인코딩하였다.
- 평가 후 파레토 최적해를 생성하고 NSGA-Ⅱ기법을 사용하여 염색체를 선택한다. 선택된 염색체들에 진화연산을 적용하여 자식 개체군을 생성한다.
- 본 논문에서는 k-means 클러스터링과 유전자 알고리즘, 그리고 다목적 유전자 알고리즘 사용하였을 때의 클러스터링 성능을 비교 및 분석하였다. 유전자 알고리즘과 다목적 유전자 알고리즘은 300개의 동일한 개체수와 세대수가 1,000이거나 성능 향상 없이 20번의 세대가 진행될 때 알고리즘이 종료되도록 설정하였다.
대상 데이터
- 클러스터링 알고리즘의 성능을 비교하기 위해 데이터 셋은 한국일보-20000/한국일보-40075 문서 범주화 실험문서 집합을 사용하였다. 총 3개의 테스트 셋을 만들어 각각 4개의 주제를 선정하였으며 <표 1>과 같다.
이론/모형
- 본 논문에서 사용한 목적 함수는 클러스터링 결과를 평가하기 위해 사용되는 클러스터링 인덱스(Clustering Validity Index)를 사용하였다. 클러스터링 인덱스는 클러스터링 결과의 유효성을 평가하기 위해 사용되는 평가기준이며 최적의 클러스터가 생성되었을 경우 값은 최소값 또는 최대값을 가지게 된다.
- 본 논문에서는 여러 가지 문서 특징 추출 방법 중에서도 Okapi's 계산법[13]을 사용하여 문서의 용어들의 가중치를 계산하였다.
- )이며 M은 목적 함수의 개수, N은 개체수를 나타낸다. 이와 같이 클러스터링 인덱스를 목적 함수로 사용하는 다목적 유전자 알고리즘을 이용한 문서 클러스터링은 높은 계산 시간을 필요로 하므로 본 논문에서는 클러스터링 인덱스 중에 가장 간단한 CH(Calinski and Harabasz)[14]와 DB(Davis and Bouldin)[15]인덱스를 사용하였다.
- 2) 유전자 인코딩 방식에 따라 문서 벡터와 매핑하여 적합도를 평가한다. 평가 후 파레토 최적해를 생성하고 NSGA-Ⅱ기법을 사용하여 염색체를 선택한다. 선택된 염색체들에 진화연산을 적용하여 자식 개체군을 생성한다.
성능/효과
- 유전자 알고리즘에서는 목적 함수로 사용된 클러스터링 인덱스에 따라 성능의 차이가 보였다. 다목적 유전자 알고리즘은 k-means 클러스터링, 유전자 알고리즘 보다 약 20%이상의 성능 향상을 보였다. 특히, 코사인 유사도를 사용한 DB 인덱스와 CH 인덱스를 목적 함수로 사용하였을 때가 다른 알고리즘에 비해서 우수한 클러스터링 결과를 보였다.
- 모든 테스트 셋에 대해 유전자 알고리즘이 k-means 클러스터링보다 성능이 우수하였고 특히, CH 인덱스를 적용하였을 때 약 10%의 가장 높은 성능 향상을 보였다. 또한, 다목적 유전자 알고리즘은 k-means 클러스터링과 유전자 알고리즘보다 성능이 우수하였으며, k-means 클러스터링보다 약 20%, 유전자 알고리즘보다 약 15%의 성능 향상을 보였다.
- 모든 테스트 셋에 대해 유전자 알고리즘이 k-means 클러스터링보다 성능이 우수하였고 특히, CH 인덱스를 적용하였을 때 약 10%의 가장 높은 성능 향상을 보였다. 또한, 다목적 유전자 알고리즘은 k-means 클러스터링과 유전자 알고리즘보다 성능이 우수하였으며, k-means 클러스터링보다 약 20%, 유전자 알고리즘보다 약 15%의 성능 향상을 보였다.
- 본 논문에서는 현재까지 문서 클러스터링 연구에 있어 다목적 유전자 알고리즘을 적용한 사례가 알려지지 않는 가운데 처음으로 다목적 유전자 알고리즘을 문서 클러스터링에 적용해 보았다. 적용한 결과 k-means 클러스터링과 유전자 알고리즘이 갖는 단점을 개선하여 성능이 향상됨을 알 수 있었다.
- 전체적으로 다른 클러스터링 알고리즘보다 다목적 유전자 알고리즘을 이용한 문서 클러스터링이 월등한 성능을 보였으며, DB 인덱스에서 코사인 유사도와 CH 인덱스를 목적 함수로 적용하였을 때가 가장 우수한 성능을 보였다.
- 다목적 유전자 알고리즘은 k-means 클러스터링, 유전자 알고리즘 보다 약 20%이상의 성능 향상을 보였다. 특히, 코사인 유사도를 사용한 DB 인덱스와 CH 인덱스를 목적 함수로 사용하였을 때가 다른 알고리즘에 비해서 우수한 클러스터링 결과를 보였다.
후속연구
- 향후 이와 관련된 연구를 통하여 본 논문에서 소개된 클러스터링 인덱스 이외의 다양한 인덱스를 파악하고 이를 목적 함수에 적용하며 성능을 향상시킬 계획이다. 또한, 클러스터링 인덱스들 사이의 관계성을 파악함으로써 클러스터링 성능에 영향력이 큰 요소를 찾을 수 있을 것이다.
- 문서 클러스터링에 있어 다목적 유전자 알고리즘을 적용한 사례가 아직까지 찾아지지 않고 있다. 향후 이와 관련된 연구를 통하여 본 논문에서 소개된 클러스터링 인덱스 이외의 다양한 인덱스를 파악하고 이를 목적 함수에 적용하며 성능을 향상시킬 계획이다. 또한, 클러스터링 인덱스들 사이의 관계성을 파악함으로써 클러스터링 성능에 영향력이 큰 요소를 찾을 수 있을 것이다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.