초록

용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

클러스터링이란 주어진 데이터들을 유사한 성질을 가지는 군집으로 나누는 것으로 많은 분야에서 응용되고 있으며, 특히 최근 관심의 대상인 데이터 마이닝의 중요한 기술로서 활발히 응용되고 있다. 클러스터링에 있어서 기존의 알고리즘들은 지역적 최적해에 수렴하는 것과 사전에 클러스터 개수를 미리 결정해야 하는 문제점을 가지고 있다. 본 논문에서는 병렬 탐색을 통해 최적해를 찾는 진화알고리즘을 사용하여 지역적 최적해에 수렴되는 문제점을 개선하였으며, 자동으로 적절한 클러스터 개수를 결정할 수 있게 하였다. 또한 진화알고리즘의 단점인 탐색공간의 확대에 따른 탐색시간의 증가는 휴리스틱 연산을 정의하여 개선하였다. 제안한 알고리즘의 성능 및 타당성을 보이기 위해 가우시안 분포 데이터를 사용하여 제안한 알고리즘의 성능이 우수함을 보였다.

클러스터링이란 주어진 데이터들을 유사한 성질을 가지는 군집으로 나누는 것으로 많은 분야에서 응용되고 있으며, 특히 최근 관심의 대상인 데이터 마이닝의 중요한 기술로서 활발히 응용되고 있다. 클러스터링에 있어서 기존의 알고리즘들은 지역적 최적해에 수렴하는 것과 사전에 클러스터 개수를 미리 결정해야 하는 문제점을 가지고 있다. 본 논문에서는 병렬 탐색을 통해 최적해를 찾는 진화알고리즘을 사용하여 지역적 최적해에 수렴되는 문제점을 개선하였으며, 자동으로 적절한 클러스터 개수를 결정할 수 있게 하였다. 또한 진화알고리즘의 단점인 탐색공간의 확대에 따른 탐색시간의 증가는 휴리스틱 연산을 정의하여 개선하였다. 제안한 알고리즘의 성능 및 타당성을 보이기 위해 가우시안 분포 데이터를 사용하여 제안한 알고리즘의 성능이 우수함을 보였다.

AI 본문요약

엑셀 다운로드 AI-Helper

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

• 연구 주제
• 연구 방법
• 연구 결과

문제 정의

• 본 논문에서는 기존의 교배 연산 대신 휴리스틱 연산을 사용한 진화성이 우수한 진화알고리즘을 이용하여 클러스터링 알고리즘의 문제점을 개선하였다.
• 본 논문에서는 모든 클러스터의 표준편차 백터를 계산하여 클러스터 내의 유사성을 정의하였다. 즉, 클러스터의 표준편차 백터 요소들 중 임계값 公보다 크면 클러스터 내의 유사성이 낮다고 판단하고 분할 연산 을 적용하여 (그림2.
• 본 논문에서는 분할적 클러스터링 알고리즘의 문제점을 개선한 알고리즘을 제안한다. 제안한 알고리즘에서는 병렬탐색을 통해 최적의 해를 찾는 진화알고리즘을 이용하여 전역적 최적해를 찾올 뿐만 아니라 클러스터링의 특성인 '클러스터 내의 유사성과 클러스터 간의 차별성'을 각각 분산도와 분리도로 나타내고, 입력 데이터들의 분포에 따라 자동으로 적절한 클러스터 개수를 결정하도록 하였다.
• 본 논문에서는 정의된 합병 연산을 적용하기 위해 두 클러스터 간의 거리를 계산하여 두 클러스터의 차별성을 조사한다. 여기서 두 클러스터 간의 차별성은 임계 값 力』보다 작으면 낮다고 보고 합병 연산을 적용하여 (그림2 왼쪽)와 같이 두 클러스터의 중심점 V】, V2을 합하여 한 개의 클러스터로 만든다.
• 클러스터 간의 차별성을 동시에 고려해야만 한다. 본 논문에서는 클러스터 간의 차별성을 FCM에서 고려하고 있는 소속 정도를 이용하여 고려하였다. 즉, 각각의 클러스터에 포함된 데이터에 대한 평균 소속 정도를 합한 것을 분리도(separation) s 어 人 X, 卩)으로 식⑷과같이 정의하였다.
• 본 논문에서는 휴리스틱 연산을 사용한 진화 알고리즘을 이용하여 자동으로 클러스터 개수를 결정하는 클러스터링 알고리즘 올 제안하였다. 제안한 알고리즘은 기존의 진화알고리즘을 사용한 클러스터링의 클러스터의 수를 자동으로 찾아주며, 초기값에 민감하지 않는다는 장점은 유지하면서 문제점인 수렵속도가 느리다는 점을 개선하였다.

제안 방법

• 이는 클러스터의 특성 중 유사성에 의하여 클러스터 중심이 될 가능성이 있는 데이터의 주위에는 관련된 많은 데이터들이 분포될 가능성이 높다고 할 수 있다. 따라서 본 논문에서는 중심(V)에 대해서 각 차원별로 표준편차를 계산하여 데이터의 분산를 측정하였다. 계산된 모든 클러스터의 표준편차 벡터 요소를 합함으로써 클러스터 중심으로부터 데이터들이 얼마나 분산되어 있는가를 나타내는 분산도(dispersion) disp{X, 卩)을 식⑶와 같이 정의한다.
• 제안한 알고리즘에서는 병렬탐색을 통해 최적의 해를 찾는 진화알고리즘을 이용하여 전역적 최적해를 찾올 뿐만 아니라 클러스터링의 특성인 '클러스터 내의 유사성과 클러스터 간의 차별성'을 각각 분산도와 분리도로 나타내고, 입력 데이터들의 분포에 따라 자동으로 적절한 클러스터 개수를 결정하도록 하였다. 또한 진화알고리즘이 가지고 있는 단점인 탐색공간의 확대에 따른 탐색 시간의 증가를 휴리스틱 연산을 정의하여 개선하였다.
• 제안한 알고리즘이 전역적 최적해에 수렴하면서 가장 적합한 클러스터 개수를 자동으로 찾는 것을 시각적으로 확인할 수 있도록 2차원 가우시안 분포 데이터를 이용하여 기존의 알고리즘과 비교하였으며 다차원 가우시안 분포 데이터에서는 클러스터링 후의 클러스터 분류율을 기존의 알고리즘과 비교하였고, 생성된 클러스터 중심은 가우시안 분포 데이터의 원 중심 간의 오차를 계산하여 타당한지 확인하였다. 또한 휴리스틱 연산을 사용하지 않고 교배 연산과 돌연변이 연산을 사용한 알고리즘[3]과 휴리스틱 연산을 사용한 제안한 알고리즘과의 진화속도를 비교하였다. 본 실험에서는 실험 데이터 변수로 표1과 같이 선언하였다.
• 본 논문에서 사용하는 휴리스틱 연산은 가까이 있는 두 클러스터를 합병(merge)하고, 큰 클러스터는 두 개의 클러스터로 분할(split)하는 개념에서 비롯된다.
• 본 논문에서 제안한 알고리즘은 진화알고리즘을 사용하여 클러스터링을 하였다. 진화알고리즘은 자연도태와 진화의 메카니즘(mechanism)에 기반을 둔 확률적인 탐색 알고리즘으로서 특히 최적화 문제에 효율적인 알고리즘⑸이다.
• 본 논문에서는 제안한 알고리즘의 타당성을 검증하기 위해 기존의 알고리즘, 즉 K-means, FCM, Isodata 과 비교 실험하였다. 제안한 알고리즘이 전역적 최적해에 수렴하면서 가장 적합한 클러스터 개수를 자동으로 찾는 것을 시각적으로 확인할 수 있도록 2차원 가우시안 분포 데이터를 이용하여 기존의 알고리즘과 비교하였으며 다차원 가우시안 분포 데이터에서는 클러스터링 후의 클러스터 분류율을 기존의 알고리즘과 비교하였고, 생성된 클러스터 중심은 가우시안 분포 데이터의 원 중심 간의 오차를 계산하여 타당한지 확인하였다.
• 본 논문에서는 분할적 클러스터링 알고리즘의 문제점을 개선한 알고리즘을 제안한다. 제안한 알고리즘에서는 병렬탐색을 통해 최적의 해를 찾는 진화알고리즘을 이용하여 전역적 최적해를 찾올 뿐만 아니라 클러스터링의 특성인 '클러스터 내의 유사성과 클러스터 간의 차별성'을 각각 분산도와 분리도로 나타내고, 입력 데이터들의 분포에 따라 자동으로 적절한 클러스터 개수를 결정하도록 하였다. 또한 진화알고리즘이 가지고 있는 단점인 탐색공간의 확대에 따른 탐색 시간의 증가를 휴리스틱 연산을 정의하여 개선하였다.
• 일반적으로 진화알고리즘에서의 각 개체들은 순서화된 고정 길이이며, 한 유전인자를 나타내는 값들의 배열로 표현된다. 제안한 알고리즘에서는 최적의 클러스터 개수를 찾아주기 위해 각 클러스터의 중심점으로 개체를 표현하였으며, 각 개체는 가변적인 길이를 가지도록 코딩하였다.

대상 데이터

• 본 데이타는 입력공간에 대한 각 차원의 영역이 10, [이인 2차원 가우시안 분포 데이터로써 10개의 원 중심으로부터 가우시안 분포를 갖도록 각각 50개씩 데이터를 생성하였다. 따라서 총 500개의 데이터를 가지고 있다, 단, 원 중심은 초기 클러스터의 평균 중심은 아니다.

데이터처리

• 이와 같이 형성된 각각의 클러스터에 대해서 중심 狄을 평균(mean)으로 하고 표준편차 벡터를 계산한다. 이는 클러스터의 특성 중 유사성에 의하여 클러스터 중심이 될 가능성이 있는 데이터의 주위에는 관련된 많은 데이터들이 분포될 가능성이 높다고 할 수 있다.
• 본 논문에서는 제안한 알고리즘의 타당성을 검증하기 위해 기존의 알고리즘, 즉 K-means, FCM, Isodata 과 비교 실험하였다. 제안한 알고리즘이 전역적 최적해에 수렴하면서 가장 적합한 클러스터 개수를 자동으로 찾는 것을 시각적으로 확인할 수 있도록 2차원 가우시안 분포 데이터를 이용하여 기존의 알고리즘과 비교하였으며 다차원 가우시안 분포 데이터에서는 클러스터링 후의 클러스터 분류율을 기존의 알고리즘과 비교하였고, 생성된 클러스터 중심은 가우시안 분포 데이터의 원 중심 간의 오차를 계산하여 타당한지 확인하였다. 또한 휴리스틱 연산을 사용하지 않고 교배 연산과 돌연변이 연산을 사용한 알고리즘[3]과 휴리스틱 연산을 사용한 제안한 알고리즘과의 진화속도를 비교하였다.

이론/모형

• 또한 진화알고리즘의 단점인 탐색공간이 커짐에 따라 진화속도가 느려지는 문제점을 휴리스틱 연산을 적용하여 개선하였다. 10차원 가우시안 분포 데이터로 1000세대 실험한 결과는 (그림 4)와 같이 기존의 진화 연산을 적용하였을 때보다 휴리스틱 연산을 적용하였을 때의 수렴속도가 훨씬 빠르며 지역적 최소 해에서도 빨리 벗어남을 알 수 있다.
• 지금까지 정의된 적합도 함수는 각 개체들의 특성을 평가하여 다음 세대의 개체집단을 선택하기 위한 척도가 된다. 본 논문에서는 다음 세대의 개체집단을 선택하기 위한 방법으로 룰렛훨(roulette wheel)방법 과 최상의 개체를 보존하는 엘리트 방법(이itist model)을 사용하였다.
• 들연변이 연산, 합병 연산, 분할 연산에 의해 생성된 중심은 클러스터 내에서 정확한 중심이 아닌 대략적인 중심에 위치하고 있어 정확한 중심을 찾기 위해서 더 진화를 시켜야 할 필요가 있다. 이러한 문제를 개선하기 위해서 K-means 알고리즘을 한 단계 적용한 연산을 사용하였다. K-means 연산을 통해 매 세대마다 클러스터 중심들을 입력데이터 분포에 가장 적합한 중심으로 교정함으로써 진화 속도를 개선한다.

성능/효과

• 또한 진화알고리즘의 단점인 탐색공간이 커짐에 따라 진화속도가 느려지는 문제점을 휴리스틱 연산을 적용하여 개선하였다. 10차원 가우시안 분포 데이터로 1000세대 실험한 결과는 (그림 4)와 같이 기존의 진화 연산을 적용하였을 때보다 휴리스틱 연산을 적용하였을 때의 수렴속도가 훨씬 빠르며 지역적 최소 해에서도 빨리 벗어남을 알 수 있다. 즉, (그림5)에서 보는 바와 같이 휴리스틱 연산자를 사용할 경우 8세대에 수렴함을 홀 수 있으나, 일반 진화연산자를 사용할 경우 1000세대가 지나도 수렴되지 않음을 알 수 있다.
• 따라서 제안한 알고리즘은 입력데이터에 대해 기존의 알고리즘과는 다르개 자동적으로 입력데이터의 분포에 따라 클러스터 개수를 결정할 수 있으며 최적의 클러스터 중심 위치를 찾을 수 있음을 알 수 있다.
• 실험 결과는 (그림3) 와 같이 기존의 알고리즘은 지역적 최적해에 수렴하여 적절한 중심을 찾지 못한 반면 제안한 알고리즘은 자동적으로 클러스터 개수를 찾아낼 뿐만 아니라 적합한 클러스터링을 형성하고 있는 것을 보여주고 있다
• 본 논문에서는 휴리스틱 연산을 사용한 진화 알고리즘을 이용하여 자동으로 클러스터 개수를 결정하는 클러스터링 알고리즘 올 제안하였다. 제안한 알고리즘은 기존의 진화알고리즘을 사용한 클러스터링의 클러스터의 수를 자동으로 찾아주며, 초기값에 민감하지 않는다는 장점은 유지하면서 문제점인 수렵속도가 느리다는 점을 개선하였다.

후속연구

• 이러한 단점 역시 클러스터링의 응용 분야를 축소시키는 요인이 될 수 있다. 이러한 데이터들을 올바르게 분석하기 위해서는 제안한 알고리즘에 기호적 데이터를 분석할 수 있는 척도를 고려하여 보다 일반적인 클러스터링 알고리즘으로 확장되어야 할 것이다.
• 향후 계획으로는 기존의 분할적 클러스터링 알고리즘에서 다루기 힘들었던 기호적이나 이 산적인 값을 포함한 데이터를 적용하는 부분을 연구할 계획이다. 기존의 분할적 클러스터링 방법들은 기호적인 데이터를 수치 데이터로 변환하여 사용하였으며, 그 과정에서 데이터의 성질이 왜곡되어 적절한 클러스터링이 되지 않는 단점을 가지고 있다.

본문요약 정보가 도움이 되었나요? 예 아니오 제출

이 논문을 인용한 문헌

더보기