선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 대규모 데이터에 대한 특성 값에 따라 몇 개의 클러스터로 군집화하는 클러스터링 기법은 계층적 클러스터링[1,9]이나 분할 클러스터링[6,10] 등 다양한 기법으로 나누어 설명할 수 있는데 현대 사회의 정보 대량화는 계층적 클러스터링이나 그래프 이론 클러스터링으로는 처리할 수 있는 데이터에 한계가 있고 시간 복잡도 측면에서 비효율적이다[3]. 본 논문에서는 대량 데이터에 대한 클러스터링 기법으로 용이한 분할 클러스터링 중 K-Means 알고리즘을 다루고자 한다. K-Means 알고리즘은 구현이 쉽고, 패턴수가 n일 때 시간 복잡도가 O(n)인 장점을 가지고 있다.
- 본 논문에서는 대량의 데이터에 대한 클러스터링에 주로 사용되는 분할 클러스터링 중 K-Means 알고리즘의 성능을 개선하기 위하여 중심 선정 방법을 제안하였다. K-Means는 구현이 쉽고, 패턴 수가 N일 때 시간 복잡도가 선형적이기 때문에 일반적이다.
- 본 논문에서는 초기 클러스터 중심들 간의 거리가 최대가 되도록 한다. 이를 통해 초기 클러스터 중심들이 데이터 집합에 고르게 분포되도록 한다.
- 본 논문에서는 클러스터링 초기 중심에 새로운 방법을 이용하여 K-Means 알고리즘을 개선하고자 한다. 제안하고자 하는 초기 클러스터 중심 선정 방법은 초기 클러스터 중심들을 가능한 한 멀리 선정하도록 한다.
- 본 논문은 2장에서 K-Means 알고리즘에 대해 간략히 살펴보고 기존의 중심 선정 방법에 대해 살펴본다. 3장에서 K-Means 알고리즘을 개선하기 위한 초기 중심 선정 방법으로 최대 평균 거리를 이용한 기법을 제안한다.
- 제안하고자 하는 초기 클러스터 중심 선정 방법은 초기 클러스터 중심들을 가능한 한 멀리 선정하도록 한다. 이렇게 함으로써 무작위로 선정된 초기 클러스터 중심이 일부 영역으로 편향되는 현상을 막을 수 있고, 이에 따라 클러스터링 속도 향상과 클러스터링의 정확도를 높이고자 하였다. 제안한 K-Means 알고리즘의 초기 클러스터 중심 집합C는 다음 식(4)와 같다.
- 그러나 초기 클러스터 중심이 어느 한쪽에 편중되어 선정되면 클러스터링 결과가 적절하지 못하게 산출되거나 할당-재계산에 소요되는 시간이 증가하게 된다. 이에 본 논문에서는 기존 방법인 무작위 추출을 통한 초기 클러스터 중심 선정 방법에서 벗어나 계산을 통한 초기 클러스터 중심을 선정함으로써 K-Means 알고리즘 성능을 개선하고자 한다.
- 초기 클러스터 중심을 무작위로 선정하는 방식에서 벗어나 초기 중심들을 최대한 멀리 배치함으로써 클러스터링의 성능을 향상시키고자 하였다. 정확도 측면에서 보면, 표준 알고리즘의 경우 정확하게 클러스터링 되는 경우도 있으나 상대적으로 그렇지 않은 경우도 발생하여 클러스터링 결과가 초기 클러스터 중심에 종속적임을 확인할 수 있다.
가설 설정
- (1) 미리 정의된 반복 횟수만큼 반복한다. 이 조건은 클러스터링 알고리즘의 실행 시간을 제한한다.
- (2) 벡터가 속한 클러스터가 더 이상 변하지 않을 때까지 반복한다. 이 조건은 지역 최소(local minimum)에 들어가는 경우를 제외하고는 군집화의 질이 매우 좋다.
- (3) 중심이 더 이상 변하지 않을 때까지 반복한다.
- (4) RSS가 임계치 이하로 떨어질 때까지 반복한다. 이 기준에 따라 종료되면 군집화의 질이 매우 좋다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.