earticle

한국어

이 논문에서는 유전 알고리즘에 기반한 클러스터링 기법을 웹 페이지 클러스터링 문제에 적용하였다. 클러스터링 문제는 대표적인 조합 최적화 문제의 하나로서, 유의한 시간 내에 문제를 해결할 수 없는 NP-hard 문제이다. 클러스터링 알고리즘은 다양한 환경에서 적용되고 있으며 K-means 클러스터링 외에도 메타 휴리스틱 방법인 유전 알고리즘(Genetic Algorithm, GA), Simulated annealing(SA), Tabu search 등이 있다. 이 연구에서는 K-means 클러스터링 알고리즘의 거리 계산법을 유전알고리즘의 적응도 함수에 적용하였다. 웹 페이지 클러스터링을 위해 전처리 과정이 필요하고 본 연구에서는 정보검색기법에 주로 사용하는 tf․idf(term frequency and inverse document frequency) 모델을 사용하여 웹 페이지의 벡터를 벡터공간에 표현하였다. 유전 알고리즘을 통해 존재하는 여러 개의 해를 적합한 형태의 스트링으로 표현한 뒤, 선택, 교배, 변이 연산을 종료조건이 만족할 때까지 반복하여 최적해를 구하였다. 이 연구에서는 NP-hard인 웹 페이지 클러스터링 문제를 유전 알고리즘을 통하여 풀고 K-means 알고리즘과 비교 분석하여 우수한 결과를 얻었다.