1 연구의 배경 및 목적

데이터 클러스터링 분석에서 널리 사용되는 K-means는 빠르게 해를 탐색할 수 있지만, 지역해에 머물 가능성이 있다. Kang et al.[5]이 제안한 인공벌군집(Artificial Bee Colony)방법은 지역해에 머물지 않고 전역해를 탐색할 수 있으나, 해 평가 시 K-means와 같이 클러스터 내의 유클리드 거리만을 평가기준으로 고려하기 때문에 적절한 클러스터 수를 결정할 수 없다. 데이터 클러스터링 할 때 실루엣(Silhouette)은 적절한 클러스터 수를 결정할 수 있 는 적절한 평가기준(valid index)이다[11]. 여러 가지 데이 터 클러스터링 평가기준 중 Arbelaitz et al.[1]는 실루엣이 가장 우수하다고 서술하였고, Xu et al.[18]도 실루엣 평 가기준이 안정적이고 신뢰성이 높다고 서술하였으나, 실 루엣 값을 얻기 위해서는 모든 데이터간의 거리를 계산 해야 하기 때문에 계산 부담이 크다고 지적하였다.

데이터 클러스터링의 해에 대한 평가기준이 결정되면 수많은 해들 중 가장 좋은 해를 탐색해 내기 위해 최적 화 방법의 적용이 필요하다. Hruschka et al.[4]는 NP-hard 그룹핑 문제인 데이터 클러스터링 문제에 효율적인 진 화알고리즘 등 휴리스틱 알고리즘 적용 필요성을 주장 하였다. Ng et al.[9]는 클러스터 분석을 할 때 클러스터 수를 결정하는 것이 매우 어려운 문제라고 설명하고 이 를 해결하기 위해 휴리스틱 방법을 적용하였다. Lleti et al.[8]는 데이터 클러스터링을 할 때 가장 중요한 파라미 터는 그룹 수이고 K-means 클러스터링 분석을 하기 위 해 데이터의 그룹 수를 유전자 알고리즘과 실루엣을 이 용해 찾고자 하였다. Hruschka et al.[3]은 실루엣 평가기 준을 적용하고 유전자알고리즘(Genetic Algorithm, GA) 을 사용하여 적절한 클러스터 수를 결정하고 해를 탐색 하였다. Kim et al.[6]도 데이터에 대한 사전 정보가 없을 때, 적절한 클러스터 수를 결정하고 이에 맞는 최적의 데이터 클러스터링 해를 탐색할 수 있는 그룹탐색최적 화(Group Search Optimization, GSO) 방법을 제안하였다. 이와 같이 실루엣은 적절한 클러스터 수와 해를 동시에 탐색할 수 있는 유용한 평가기준이지만, 모든 데이터 사 이의 거리를 계산하여 평가하기 때문에 데이터의 크기 가 커질수록 계산 시간이 많이 소요된다. 따라서, 빅데 이터 분석 시 계산 시간을 단축할 수 있는 방법의 개발 이 필요하다.

본 논문의 목적은 데이터 클러스터링의 해 평가 척도 인 실루엣의 계산 부담을 극복할 수 있는 빠른 클러스터 수 선택 방법과 효율적인 휴리스틱 데이터 클러스터링 방법을 제안하는 것이다. 제안하는 방법은 일차적으로 거리의 상대적인 비율이 작은 순서대로 클러스터 수와 클러스터 중심 데이터를 정하고, 각 클러스터 수에 따른 실루엣 값 중에서 가장 큰 값에 해당하는 클러스터 수를 가장 적절한 클러스터 수로 빠르게 선택한다. 또한, 적절 한 클러스터 수가 선택된 상태에서, 거리의 상대적인 비 율의 크기가 작을수록 클러스터의 중심 데이터 역할을 할 수 있도록 확률적으로 중심 데이터를 선택하고 해를 생성한다. 이렇게 생성한 해들을 휴리스틱 알고리즘의 초기해로 적용하여 최적해를 효율적으로 탐색한다. 제 2 장에서는 데이터 클러스터링 문제를 설명하고 본 논문에 서 제안한 클러스터 수 선택 방법과 적용된 휴리스틱 알 고리즘 방법을 상세히 설명하고 제 3장에서는 제안하는 방법의 효율성을 검증한다.

2 빠른 클러스터 수 선택과 휴리스틱 알고리즘

데이터 클러스터링 평가기준인 실루엣의 계산 시간이 많이 소요된다는 문제점을 해결하기 위해 모든 데이터간 의 거리를 한 번 계산하여 저장 후 필요 시 재사용한다. 분석하고자 하는 모든 데이터에서 데이터 j까지 거리의 상대적인 비율 V_j를 고려하여 적절한 클러스터 수를 간 단하고 빠르게 찾아낼 수 있는 방법을 설명한다. 또한, 클러스터 수가 선택된 상태에서 휴리스틱 알고리즘에 적 용하여 최적해를 탐색 할 수 있는 방법을 설명한다.

2.1 데이터 클러스터링 문제와 빠른 클러스터 수 선택 방법

각각의 데이터는 {x_i, i = 1, 2, ⋯, n}이라하고 n개의 데이터 집합으로 구성된다. 각 데이터 i(x_i)는 P차원(i 징, feature)으로 구성되는데 x_ip는 데이터 i의 i징 p의 값을 표현할 수 있고 n개의 데이터를 K개의 그룹으로 클러스터링 하는 문제를 수리적으로 정립할 수 있다[7]. 간단하고 빠른 클러스터링 해 탐색 방법을 만들어 내기 위해 P개의 특징을 가진 데이터 i에서 데이터 j까지의 거리(dij)를 식 (1)을 사용하여 한번 계산하여 저장하고 필요 시 재사용한다.

본 연구에서는 실루엣 평가기준을 효율적으로 적용하 기 위해 식 (2) V_j(모든 데이터에서 데이터 j까지 거리의 상대적인 비율)를 활용하는데, 본래, Park et al.[10]이 제 안한 V_j는 K-medoid의 계산 문제점을 개선하기 위해 제 안한 효율적인 아이디어이다. V_j가 작을수록 해당 데이 터 j가 클러스터링을 할 때 중심 데이터 역할을 하는 것 이 유리하고 실루엣 값이 좋은 해 탐색에 효과적으로 적 용할 수 있다.

즉, 가장 작은 V_j값 순서대로 클러스터 수 K 개의 데 이터 중심을 결정하고 나머지 데이터는 가장 가까운 데 이터 중심에 소속시켜 클러스터링 했을 경우 해당 해에 대하여 실루엣 값을 계산하고 1에 가장 가까운 K 를 적 절한 클러스터 수로 결정할 수 있다. 클러스터링 해를 평 가할 때 식 (3)~식 (5)를 사용하여 데이터 i(x_i)에 대한 실루엣 S (x_i)를 계산한다[6, 11]. 실루엣 값 계산을 위한 식 (3)~식 (5)를 구체적으로 설명하면 다음과 같다. 클러 스터 A에 포함되어 있는 데이터 i(x_i)와 클러스터 A에 속한 다른 데이터들과의 평균 거리를 a(x_i)라 할 때, 이 값이 작을수록 클러스터 내의 데이터들이 조밀하게 모여 있다는 것을 의미한다. 클러스터 A와 다른 클러스터 B 와 C가 존재하고 클러스터 A에 속한 데이터 i에서 다른 클러스터 B와 C의 각 데이터들과의 평균거리를 각각 d(x_i, B)와 d(x_i, C)라 할 때, b(x_i)는 데이터 i에서 다른 클러스터에 포함된 데이터간의 평균거리 중 가장 작은 값을 의미한다. 만약, d(x_i, B)가 d(x_i, C)보다 작다면 b(x_i) = d(x_i, B)가 된다. b(x_i)는 식 (3)과 같이 나타낼 수 있는데, 이 값이 클수록 클러스터 간의 구별이 뚜렷하 다고 판단할 수 있다. 따라서, 식 (4)와 같이 S (x_i)를 계 산할 수 있고 모든 데이터 i(x_i)에 대하여 S (x_i)를 구하여 합한 값 ∑ i = 1 n S ( x i )을 데이터 수 n으로 나누면 평균 실 루엣 값 SIL (S (x_i))을 구할 수 있고 식 (5)로 나타낸다.

본 논문의 목적은 데이터에 대한 사전 정보가 없을 때, 실루엣 평가기준을 적용하여 적절한 클러스터 수와 클러 스터링 해를 제시할 수 있는 간단하고 빠른 방법을 제안 하는 것이다. 클러스터 수 K가 2라면 V_j가 가장 작은 데 이터 2개를 선택하고 해당 데이터를 데이터의 중심으로 설정하고 다른 데이터들은 이 2개의 데이터에서 가장 가 까운 데이터 중심의 클러스터로 포함시켜 해를 구성하고 이 해에 대한 실루엣 값을 계산한다. 추가적으로 클러스 터 수가 3~K를 수행하여 해당 실루엣 값을 계산하고 실 루엣 값이 가장 큰 해당 클러스터 수 K를 가장 적절한 클 러스터 수로 결정한다.

이와 같이 적절한 클러스터 수와 클러스터링 해를 결 정할 수 있는 간단하고 빠른 방법은 <Table 1> 10개의 데 이터 예제(각 데이터 x_i는 i징 a₁과 a₂로 표시)로 다음과 같이 설명할 수 있다. 먼저, 식 (1)로 모든 데이터간의 거 리를 1회 계산하여 저장하여 필요 시 재사용하고 식(2)로 10개의 데이터의 V_j를 <Table 1>과 같이 계산한다.

만약, K가 2라면 V_j값이 가장 작은 x₇과 x₅가 데이터 중심으로 선택되고 나머지 데이터 x₁, x₂, x₃, x₄는 데이 터 중심 x₅에 가까워 한 개의 클러스터가 형성되고 다른 나머지 데이터 x₆, x₈, x₉, x₁₀은 데이터 중심 x₇에 가까워 다른 한 개의 클러스터가 형성된다. 이와 같이 2개의 클 러스터로 구성된 클러스터링 해의 실루엣 값은 식 (3)~식 (5)를 사용하여 0.272938로 계산된다. 만약, K가 3이라면 V_j 값이 가장 작은 x₇, x₅, x₆이 데이터 중심으로 선택되 고 나머지 데이터 x₁ , x₂ , x₃, x₄는 데이터 중심 x₅에 가까 워 한 개의 클러스터가 형성되고 데이터 x₈, x₉, x₁₀은 데 이터 중심 x₇에 가까워 다른 한 개의 클러스터가 형성되 고 나머지 x₆는 1개의 데이터로 하나의 클러스터가 형성 된다. 이와 같이 3개의 클러스터로 구성된 클러스터링 해 의 실루엣 값은 0.181605로 계산된다. 만약, K가 4라면 V_j 값이 가장 작은 x₇, x₅, x₆, x₄이 데이터 중심으로 선 택되고 나머지 데이터 x₁, x₂, x₃는 데이터 중심 x₅에 가 까워 한 개의 클러스터가 형성되고 데이터 x₈, x₉, x₁₀은 데이터 중심 x₇에 가까워 다른 한 개의 클러스터가 형성 되고 나머지 x₄와 x₆는 각각 1개의 데이터로 하나의 클러 스터가 형성된다. 이와 같이 4개의 클러스터로 구성된 클 러스터링 해의 실루엣 값은 0.390931로 계산된다.

이런 과정을 통하여 가능한 클러스터 수 K의 모든 경 우를 계산 한 후, 실루엣 값이 가장 클 때(1에 가까울 때)의 K 값을 적절한 클러스터 수로 선택할 수 있다. 제 3.1절에서 UCI 데이터를 활용하여 이 예제와 같이 실험 을 통하여 적절한 클러스터 수를 결정하는 과정을 설명 한다.

2.2 거리의 상대적인 비율을 적용한 휴리스틱 알고리즘

본 절에서는 제 2.1절에서 결정된 클러스터 수 K를 고 정한 상태에서 다음 과정을 진행한다. V_j값에 반비례하는 확률로 K개의 중심 데이터를 선택하고, 이 데이터를 중 심으로 다른 모든 데이터가 클러스터링 된 해를 초기해 로 사용한 휴리스틱 알고리즘을 적용하여 최적해를 탐색 한다.

휴리스틱 알고리즘 중에 하나인 그룹탐색최적화(Group search optimization, GSO)는 He et al.[2]가 동물의 탐색 행태를 모방하여 개발하였다. GSO는 Producer, Scrounger 및 Ranger의 세 가지 역할을 담당하는 구성원(member)들의 해로 이루어진다. Kim et al.[6]은 기본 실루엣 평가기준 을 적용한 GSO를 다음과 같이 제안하였다. 단계 1에서는 초기 구성원(해) 표현과 해 생성 후 실루엣 평가하였다. 단계 2에서는 Producer(가장 좋은 해) 선택과 producing을 진행하였다. 단계 3에서는 Scrounger 선택과 scrounging을 진행하였다. 단계 4는 Ranger 선택과 ranging을 진행하였다. 단계 5는 모든 해에 대하여 실루엣 평가 후 해를 업데이 트하였다. 단계 6에서는 종료 조건 확인 후 최적해 탐색 진행하였다. 기존 GSO 방법을 사용하여 데이터 수 75개 Ruspini[12]와 UCI 데이터[14, 15, 16, 17] 중 데이터 수 각각 150, 178, 683, 214인 Iris, Wine, Breast cancer, Glass 에 대하여 최적해를 탐색하였다. 상대적으로 큰 사이즈의 데이터인 Breast cancer, Glass는 탐색한 실루엣 값이 0에 가까워 실루엣 값이 0.5 이상인 적절한 클러스터링 해를 탐색할 수 없다는 한계가 있음을 <Table 3>으로 확인할 수 있다. 이런 문제점을 극복하기 위해 본 논문의 제 2.1 절에서 제안하는 간단하고 빠른 클러스터링 해 탐색 방법 이 적용된 효율적인 알고리즘인 GSO 방법은 다음과 같 이 설명할 수 있다.

제 2.1절 식 (2)를 사용한 V_j 값으로 얻은 해는 효율적 GSO 방법의 중요한 초기 정보가 된다. 본 논문에서 제 안하는 방법의 단계 1에서는 GSO의 초기해 군을 생성할 때, 제 2.1절의 방법을 적용하여 초기해 1개를 생성한다. 만약, V_j 값이 가장 작은 K개의 데이터를 선택하고 그 데 이터를 중심으로 다른 데이터를 클러스터링 할 경우 중 심점으로 선택한 데이터가 고르게 분포하지 못하고 한쪽 으로 쏠릴 경우가 발생할 가능성이 있다. 따라서, GSO 방법에 적용 할 때는 중심데이터가 다양하게 분포하여 위치 될 수 있도록 각 데이터의 V_j 값이 작을수록 선택확률을 높도록 하여 확률적으로 중심데이터를 선택한다. 이렇게 생성된 해 1개를 초기해 군에 포함시키고 나머지 해들은 랜덤하게 생성한다.

위의 방법으로 얻은 초기해는 랜덤하게 생성한 해들 보다 실루엣 값이 높아(제 3.1절에 Ruspini, Iris, Wine, Breast cancer, Glass 데이터에 대하여 빠른 해 탐색 방법 적용하여 실루엣 값 계산 결과로 확인 할 수 있음), GSO 를 적용하여 시작할 때 Producer가 될 확률이 높고 producing 할 때도 현재의 Producer보다 더 좋은 해를 생성 할 수 있다. 나머지 scrounger들은 V_j를 고려하여 만들어 진 현재의 Producer를 모방하여 닮아 가면서 새로운 해 들을 생성하고 더 좋은 해들을 탐색하게 되는 scrounging 을 진행한다. 나머지 Ranger들은 다양한 해 탐색을 수행 한다. V_j값이 적용된 해가 포함된 초기해 군의 해들은 GSO 를 적용하여 최적해를 탐색할 때 효율적으로 해를 탐색 할 수 있고 계산시간을 상당히 줄일 수 있다는 것을 제 3.2절의 실험을 통하여 검증하고자 한다. <Figure 1>은 본 논문의 제 2장에서 제안한 간단하고 빠른 클러스터 수 선택과 효율적인 데이터 클러스터링 방법의 흐름도를 나 타낸 것이다.

3 실험 및 분석

제 2장에서 제안하는 실루엣 기반 간단하고 빠른 클러 스터 수 선택 방법과 효율적인 휴리스틱 알고리즘 적용 에 대한 실용성을 검증하기 위해 본 절의 실험 및 분석 은 윈도우10 프로세서 : Intel(R) Core™ i5-4590 CPU @ 3.30GHz 3.30GHz 메모리(RAM) : 4.00GB, 64비트, x64 기반 프로세서 운영체제, Visual C⁺⁺ 환경에서 수행하였다.

3.1 빠른 클러스터 수 선택

간단하고 빠른 클러스터 수 선택 방법을 적용하면 제 2.1절의 예제와 같이 어느 정도 실루엣 평가값 이상의 해를 <Table 2>와 같이 찾을 수 있다. 즉, Ng et al.[9]와 Struyf et al.[13]가 제시한 실루엣 값 해석에 따르면 실루 엣 값이 0.5 이상이면 클러스터링이 적절히 된 것으로 해석하는데, 데이터 Ruspini, Iris, Wine는 최적화 방법과 추가적인 계산시간을 사용하지 않더라도 0.5에 가깝거나 그 이상인 해를 찾아낼 수 있다.

<Table 2>의 4가지 UCI 데이터의 경우 제 2.1절의 방 법으로 얻을 수 있는 실루엣 값을 각각의 K에 대하여 계 산한다. 실루엣 값이 가장 클 때의 K를 적절한 클러스터 수 K로 결정할 수 있다. 즉, Ruspini 데이터는 K = 2일 때 실루엣 값 0.383177, K = 3일 때 실루엣 값 0.616466 ··· K = 9일 때 실루엣 값 0.330007을 본 논문 제 2.1절의 방법만으로도 얻을 수 있고, 이중 가장 좋은 해(<Table 2>의 K = 3일 때 실루엣 값 0.616466)를 탐색 해 낼 수 있다. 다른 데이터에 대하여 제 2.1절의 방법만을 적용했 을 경우 Iris의 경우 K = 2일 때 실루엣 최대값 0.532872, Wine의 경우 K = 2일 때 실루엣 최대값 0.488526, Breast cancer의 경우 K = 2일 때 실루엣 최대값 0.369373과 이 에 해당하는 해를 빠르고 간단하게 탐색해 낼 수 있다. 그러나, Glass의 경우 빠른 클러스터 수 선택 방법만으로 는 실루엣 값이 0에 가까워 적절한 클러스터 해를 탐색 해 내지 못하였다.

3.2 거리의 상대적인 비율을 적용한 휴리스틱 알고리즘 분석

제 3.1절의 간단하고 빠른 방법만으로는 최적의 클러 스터링 해를 탐색할 수 없고 추가적인 수렴과 해 개선이 필요할 때, 휴리스틱 알고리즘을 적용할 수 있다. 본 논 문에서 제안하는 간단하고 빠른 방법을 그룹탐색최적화 (GSO) 방법에 적용하여 계산시간 부담을 줄이면서 더 좋은 실루엣 값의 해를 탐색한다. 본 절에서는 제 2.2절 에서 제안한 방법의 성능을 검증하기 위해 UCI 데이터 에 대하여 실험 분석하였다. 각 데이터의 실루엣 평가값 이 수렴 할 때 일정 세대가 진행되어도 실루엣 값이 더 이상 추가적으로 수렴되지 않을 때 종료하고 그 때까지 의 계산시간을 측정하였다.

<Figure 2>는 간단하고 빠른 클러스터 수 선택과 효율 적인 해 탐색 방법을 GSO에 적용 했을 때, 각 클러스터 수 K 에서 가장 좋은 실루엣 값을 탐색하는 과정의 수렴 경향을 나타낸 것이다. 예를 들어, Ruspini 경우 <Table 2> 에서 실루엣 값이 큰 클러스터 수는 3~5이고, Ruspini_3, 4, 5로 나타낸다. 클러스터 수가 4일 때 가장 좋은 값 0.737657을 탐색함을 나타낸다. Iris, Wine과 Breast cancer 경우 클러스터 수가 각각 2일 때 가장 좋은 값 0.686232, 0.660087, 0.595527을 Glass 경우 클러스터 수가 5일 때 가장 좋은 값 0.597413을 수렴 탐색함을 나타낸다.

<Table 3>은 각각의 데이터에 대하여 빠른 해 탐색 방 법을 적용한 GSO와 기존 GSO[6]의 최적해 실루엣 평가값 과 계산시간을 비교한 것이다. <Table 3>의 경우 Ruspini 는 K = 3~5, Iris와 Wine의 경우 K = 2와 이와 근접한 K = 3~4, Breast cancer는 K = 2~4, Glass는 K = 5~7을 실험 하였다.

<Table 3>의 결과에 따르면 제 3.2절에서 제안하는 간 단하고 빠른 해 탐색 방법을 적용한 GSO 방법의 성능 이 월등한 것으로 분석되었다. Ruspini, Iris, Wine에 간단 하고 빠른 해 탐색 방법의 GSO 방법을 적용했을 경우 비슷한 실루엣 평가값의 해를 탐색하는데 소요되는 계 산시간이 기존 방법과 비교하여 각각 24~27%, 16~21%, 10~13% 수준으로 상당히 줄어들었다.

다른 데이터보다 상대적으로 큰 사이즈의 Breast cancer와 Glass는 클러스터 수 K 가 증가할수록 가능해의 경 우의 수가 기하급수적으로 증가하여 기존 GSO 방법의 한계로 인하여 클러스터링 해 탐색이 어렵고 탐색한 실 루엣 평균값들이 0에 가까워 적절한 클러스터링 해를 탐 색해 낼 수 없었다.

그러나, 새롭게 제안한 빠른 클러스터 수 선택과 GSO 데이터 클러스터링 방법은 실루엣 평균값이 0.5에 근접하 거나 그 이상의 해를 탐색해낼 수 있어 적절한(reasonable) 클러스터링 해를 탐색해낼 수 있다. 새로운 방법의 계산 시간이 줄어들지 않고 기존 방법과 유사하거나 다소 길게 소요된 이유는 더 좋은 해를 탐색하기 위해 소요되는 계 산시간이 필요하기 때문이다.

4 결 론

기존 연구에 따르면 데이터 클러스터링 할 때 해 평가 기준은 매우 중요하며, 여러 평가기준 중에서 실루엣이 여러 측면에서 유용하지만 계산 부담(히, 데이터 크기 가 커지거나 클러스터 수가 커질수록)으로 적용하는 것 에 한계가 있다.

본 논문에서는 실루엣 기반 간단하고 빠른 클러스터 수 선택 방법과 효율적인 휴리스틱 데이터 클러스터링 방법을 제안하였다. 이 방법은 1차적으로 거리의 상대적 인 비율을 사용하여 빠르게 클러스터 수를 선택한다. 클 러스터 수가 결정된 상태에서 2차적으로 거리의 상대적 인 비율을 확률적으로 적용하여 초기해를 생성하고, 이 해들을 활용하여 휴리스틱 데이터 클러스터링 방법으로 해를 효율적으로 탐색한다. 실제로 UCI 데이터에 본 논 문에서 제안하는 방법을 적용하여 최적해 탐색이 매우 효과적임을 검증하였다.

본 논문에서 제안한 방법을 적용할 경우, 기존 실루엣 만을 적용한 방법과 비교했을 때 성능(평가값과 계산시 간)이 상당히 향상 되었다. 상대적으로 작은 크기의 데이 터 경우 유사한 실루엣 평가값을 탐색 해 내는데 제안하 는 방법을 적용할 경우 계산시간이 크게 향상되었다. 상 대적으로 큰 크기의 데이터 일 때 기존 방법의 경우 해 탐색 시 전역해를 탐색하지 못할 경우가 많아 추가적인 수렴에 한계가 있었다. 제안하는 방법을 적용할 경우 해 탐색 시 전역해 탐색이 가능하고 추가적인 수렴이 가능하 게 되어 실루엣 평가값은 상당히 개선되어 본 논문에서 제안한 방법이 매우 효용성이 높다는 것을 검증하였다.