Probabilistic reduced K-means cluster analysis
Seunghoon Leea, Juwon Song1, a
aDepartment of Statistics, Korea University
Abstract
Cluster analysis is one of unsupervised learning techniques used for discovering clusters when there is no prior knowledge of group membership. K-means, one of the commonly used cluster analysis techniques, may fail when the number of variables becomes large. In such high-dimensional cases, it is common to perform tandem analysis, K-means cluster analysis after reducing the number of variables using dimension reduction methods.
However, there is no guarantee that the reduced dimension reveals the cluster structure properly. Principal com- ponent analysis may mask the structure of clusters, especially when there are large variances for variables that are not related to cluster structure. To overcome this, techniques that perform dimension reduction and cluster analysis simultaneously have been suggested. This study proposes probabilistic reduced K-means, the transi- tion of reduced K-means (De Soete and Caroll, 1994) into a probabilistic framework. Simulation shows that the proposed method performs better than tandem clustering or clustering without any dimension reduction. When the number of the variables is larger than the number of samples in each cluster, probabilistic reduced K-means show better formation of clusters than non-probabilistic reduced K-means. In the application to a real data set, it revealed similar or better cluster structure compared to other methods.
Keywords: cluster analysis, dimension reduction, unsupervised learning, EM-algorithm, high-dimension
1.서론
군집분석이란 N개의 개체를 주어진 변수의 특성을 고려하여 K개의 상이한 그룹으로 묶어 군집으로 정의하 고, 그 군집의 대표적 특성을 찾아 분석하는 기법을 뜻한다. 기본적인 군집분석 중 하나인 K-means 군집분석은 유클리드 거리를 사용해 군집분석을 진행하기 때문에 변수의 수가 지나치게 많아지게 될 경우, 군집분석이 제대로 이루어지지 않을 수 있는 문제가 있다. 따라서 분석가들은 K-means 군집분석을 할 때 자료의 모든 변수가 군집을 형성하는데 연관 있는 것은 아니거나 변수의 개수가 지나치게 많다고 판단할 경우 주성분 분석 (principal component analysis), 또는 요인 분석(factor analysis)을 통해 주성분과 요인을 먼저 찾아내곤 한다.
즉, 차원 축소를 통해 몇 개의 주성분 또는 요인을 찾아내며, 그 축소된 차원상에서 군집분석을 실시한다. 이 렇게 차원 축소와 군집분석 두 개의 독립적인 단계로 이루어진 분석 방법을 Arabie와 Hubert (1994)는 Tandem 군집분석이라고 명명했다.
Tandem 군집분석에서 차원 축소를 통해 찾은 부분 차원이 반드시 군집 구조를 설명할 수 있는 차원일 것이라는 보장은 없다. 특히 군집의 구조와는 상관없는 변수들의 분산 또는 공분산이 클 때, 주성분 분석을 통한 차원 축소는 오히려 군집의 구조를 가릴 수 있다. 따라서, 군집 구조를 잘 밝혀낼 수 있는 저차원을 찾 아내는 것이 강조되었으며, 차원 축소와 군집분석 두 개의 독립적인 단계가 아닌, 차원 축소와 군집분석을
1Corresponding author: Department of Statistics, Korea University, 145, Anam-ro, Seongbuk-gu, Seoul 02841, Korea.
E-mail: jsong@korea.ac.kr
Published 31 December 2021/ journal homepage: http://kjas.or.kr
© 2021 The Korean Statistical Society. All rights reserved.
동시에 진행하는 방법론들이 개발되어 왔다. De Soete와 Carroll (1994)의 Reduced K-means (RKM)에서는 군집분석은 본래의 차원에서 진행하되 중심 좌표 행렬에 대해서 차원 축소를 실시한다. Vichi와 Kiers (2001) 가 제안한 Factorial K-means (FKM)에서는 자료와 중심 좌표 행렬 모두 축소된 차원에 투영시켜 차원 축소를 하고, 축소된 차원 하에서 군집분석을 진행한다. 또한, Timmerman 등 (2010)의 연구에서는 RKM과 FKM은 전체 잔차 대비 군집과 연관된 차원상에서의 잔차 비율 proportion of subspace residual (PSR) 수준에 따라, 상호 보완적인 관계임을 밝혔다. 즉, PSR 수준이 높을 때는 RKM이 우수하며, PSR 수준이 낮을 때는 FKM 이 우수하다. Rocci 등 (2011)이 제안한 factorial discriminent K-means (FDKM)에서는 Reduced K-means와 factorial K-means에서의 적재 행렬에 추가적인 제약을 줄 때 RKM과 FKM이 동등함을 밝히고, 좀 더 안정 적인 군집분석 방법 선택을 도왔다. Timmerman 등 (2013)이 제안한 subspace K-means 군집분석에서는 군집 중심 간의 차이를 드러내는 부분 공간(subspace)과, 각 군집별 군집 내 분산을 설명하는 부분 공간을 동시에 추론하는 방법론을 구축했으며, 두 부분 공간이 같지 않은 자료를 군집분석할 수 있게 되었다.
확률적인 관점에서 차원 축소와 군집분석을 동시에 진행하는 방법도 연구가 되어왔다. Ding 등 (2002)은 가우지안 혼합 모형 gaussian mixture model (GMM)을 활용하여 군집분석을 진행한 다음, 특이값 분해 singu- lar value decomposition (SVD) 등을 활용하여 차원 축소하는 과정을 반복하는 adaptive dimension reduction expectation maximization (ADR-EM) 방법을 제안했다. 또한 선형 잠재변수 모형을 활용하여 가우지안 혼합 분포 모형의 공분산 구조에 제약을 가함으로써 군집분석과 차원 축소를 동시에 진행하는 방법론도 논의가 되 었다. 이때의 선형 잠재변수 모형으로 Ghahramani와 Hinton (1996)은 요인 분석을 활용했고, Tipping과 Bishop (1999a)은 주성분 분석을 이용했다.
본 연구에서는 reduced K-means 군집분석 (De Soete와 Carroll, 1994)을 확률적 reduced K-means 모형으 로전환하고자 한다. 2 장에서는 reduced K-means 군집분석과 알고리듬을 간략하게 설명한다. 3 장에서는 reduced K-means 모형을 확률적 모형으로 확장하기 위한 가우지안 혼합 모형과 확률적 주성분 분석 모형에 대해 간략하게 설명한 후에, 확률적 reduced K-means 모형과 알고리듬을 소개한다. 4 장에서는 모의실험을 통해, 일반적인 K-means와 Tandem 군집분석에 비해 reduced K-means와 확률적 reduced K-means가 가지는 장점을 알아본다. 또한, 기존의 비확률적 방법에 비해 확률적 reduced K-means가 가지는 장점도 설명한다.
5 장에서는 Harrison과 Rubinfeld (1978)의 보스턴 자료를 통해 실제 응용 사례에 대해 다룬다. 6 장에서는 확률적 reduced K-means 모형이 가지는 의의와 추가로 필요한 연구에 대해 설명하도록 한다.
2. ReducedK-means군집분석
De Soete와 Caroll (1994)이 제안한 reduced K-means 군집분석은 차원축소와 K-means 군집분석을 동시에 실시하는 방법이다. N은 관측치의 개수, J는 변수의 개수, K는 군집의 개수, 그리고 Q(Q < J)는 축소하고 자 하는 차원의 개수로 나타내자. 군집분석을 위한 자료 행렬을 X(N × J)로 표현하고 군집 배정 행렬(cluster membership matrix)은 U(N × K)로, C(K × J)는 군집 중심 행렬(centroid matrix)로 나타내자. 이때, 군집 배정 행렬 U의 i번째 행의 k번째 열의 원소인 uik는 다음과 같이 정의된다.
uik=
1 개체 i가 군집 k에 속하는 경우,
0 이외의 경우. (2.1)
K-means 군집분석에서는 개체가 하나의 군집에만 배정되므로, uik는 다음과 같은 제약식을 가진다.
K
X
k=1
uik= 1. (2.2)
Reduced K-means 군집분석은 군집 중심 행렬 C가 Rank(C)= Q라는 가정하에서,
F(U, C)= kX − UCk2 (2.3)
을 최소화하는 군집을 찾는다. Reduced K-means 군집분석의 식 2.3은 다음과 같이 표현할 수 있다.
F(U, C)=
N
X
i=1 J
X
j=1
xi j−
K
X
k=1
uikck j
2
. (2.4)
여기서 xi j는 자료 행렬 X의 i번째 행의 j번째 열을 나타내며 i번째 개체의 j번째 변수 값을 나타낸다. ck j는 군집 중심행렬 C의 k번째 행의 j번째 열을 나타내며, k번째 군집의 j번째 변수의 중심값을 의미한다. 식 2.4는 각 개체와 각 개체가 배정된 군집 중심 사이의 거리 합을 뜻한다. k번째 군집의 개체 수를 nk= PNi=1uik라 정의 하고, k번째 군집에 속하는 개체들의 j번째 변수의 평균을 gk j = 1/nkPN
i=1uikxi j라 정의하면 식 2.4는 다음과 같이 U와 관련된 항과, C와 관련된 항으로 나눠서 정리할 수 있다.
F(U, C)=
N
X
i=1 K
X
k=1
uik J
X
j=1
xi j− gk j
2
+
K
X
k=1
nk J
X
j=1
gk j− ck j
2
. (2.5)
Reduced K-means 군집분석은 개체와 군집 중심 사이의 유클리드 거리 합이 최소가 되도록 개체를 군집 에 배정하고, 그에 따른 군집 중심 행렬에 대해 차원축소를 진행한다고 이해할 수 있다. 식 2.5는 alternating least-squares (ALS) 알고리듬에 따라 최소화될 수 있다. 즉, C가 주어진 상태에서 F(U, C)가 최소가 되도록 군집배정 행렬 U를 찾아주는 과정과, U가 주어진 상태에서 F(U, C)가 최소가 되도록 축소 차원에서의 군집 중심 행렬 C를 찾아주는 과정을 반복하게 된다. 차원 축소와 군집분석을 동시에 진행하게 되므로, 이때 찾게 되는 축소 차원은 주성분 분석을 통해 찾아지는 축소 차원과는 다른, 군집 구조를 드러내기에 적합한 차원이 라 기대할 수 있으며, Tandem 군집분석에 비해 좀 더 적절한 군집분석을 할 수 있다. 본 연구에서는 reduced K-means 군집분석을 확률적인 모형으로 전환하였다.
3.확률적reducedK-means군집분석
확률적 reduced K-means 모형을 구성할 때, 군집분석과 관련하여 가우지안 혼합 모형을 활용하며, 차원 축 소와 관련하여 확률적 주성분 분석 모형을 활용한다. 확률적 reduced K-means 모형 역시reduced K-means와 마찬가지로 군집분석을 진행하고 군집 중심 행렬에 대해 차원 축소하는 과정을 반복하게 된다.
혼합 분포(mixture density)는 K개 요인(factor)의 분포를 가중 합한 것이라 정의할 수 있다. 여기서 자료 X 의 분포는 K개의 가우지안 분포의 혼합으로 구성되어 있다고 가정하였다. 따라서 개체 x(J × 1)의 확률 밀도 함수는,
p(x)=
K
X
k=1
pk(zk)pk(x|zk) (3.1)
와 같이 정의된다. 여기서, zk= {0, 1}는 해당 개체가 k번째 가우지안 요인에 속하는지에 대한 잠재 지시 변수 이며, pk(zk = 1) = πk이고 이는 혼합 비율(mixing proportion)을 뜻한다. 따라서 πk(k = 1, . . . , K)는 0에서 1 사이 값을 가지며 PKk=1πk = 1를 만족한다. pk(x|zk)는 N(µk, σk)를 따르는 가우지안 요인이다. 이런 가우지안 혼합 밀도 함수는 먼저 다항 분포(multinomial distribution)로부터 개체가 생성되는 요인 k를 {π1, . . . , πK}에 따른 확률로 뽑고 난 후, 그 뽑힌 요인의 분포(N(x|µk, Σk))로부터 개체가 생성되는 일련의 프로세스를 모형화 한 것이라 이해할 수 있다. 가우지안 혼합 모형을 추정할 때, 로그 가능도 ln P(X)= ln ΠiN=1PK
k=1pk(zk)pk(x|zk)
를 최대화하는 모수 값을 찾아주며, 이를 위해서 개체(i= 1, . . . , N)가 어떤 요인(k = 1, . . . , K)으로부터 생성 되었는지에 대한 정보(zik)가 결측되었다고 간주하고 Dempster 등 (1977)의 EM 알고리듬을 활용할 수 있다.
주성분 분석(principal component analysis)을 확률적 모형으로 전환하기 위하여 선형 잠재 변수 모형, 특 히 Roweis (1998)와 Tipping과 Bishop (1999b)이 제안한 확률적 주성분 분석 모형을 활용할 수 있다. 확률적 주성분 분석 모형은 고차원 공간에 선형적으로 잠재되어 있는 저차원의 공간으로부터 자료가 생성되었다고 가정하며, 개체 x(J × 1)를 다음과 같이 잠재변수 y(Q × 1)의 가중 합으로 표현한다.
x= Ay + v. (3.2)
여기서 y는 N(0, I)를 따르며, 오차(Noise) v는 N(0, I)를 따른다. A(J × Q)의 열은 X(N × J)의 첫 Q개 주성분의 공간을 스팬(span)한다. 이에 따라 x|y와 x의 주변분포는 다음과 같다.
x|y ∼ N(Ay, I), (3.3)
x ∼ N(0, AA>+ I). (3.4) 확률적 주성분 분석 모형도 마찬가지로 로그 가능도가 최대가 되도록 모수를 추정하며, 이때 잠재 변수 y 값을 결측된 자료라고 간주하여 EM 알고리듬을 활용할 수 있다.
확률적 reduced K-means 모형에서 각각의 K개의 가우지안 요인은 군집 구조를 설명하는 Q개의 잠재 변 수의 선형 가중 합이라고 가정한다. 따라서 각 K개의 가우지안 요인에 대하여 확률적 주성분 분석 모형을 통해 차원 축소를 진행하도록 한다. 즉 k번째 요인의 개체 x는 다음의 선형 결합으로 구성된다고 가정한다.
x= Ayk+ v. (3.5)
여기서, yk(Q 차원)는 k번째 가우지안 요인의 잠재 변수를 뜻하며 N(µk, I)의 가우지안 분포를 따른다. A(J ×Q) 는 k번째 요인의 잠재변수 yk를 선형 결합하는 역할을 하는 가중치 행렬(weight matrix)이며, 모든 k= 1, . . . , K 에서 공통이다. 마지막으로 v는 모형의 오차에 해당되며 N(0, I)의 가우지안 분포를 따른다고 가정한다. 따 라서 각 K개의 요인의 확률 밀도 함수는,
pk(x|zk)= Z
yk
pk(x|yk, zk)pk(yk)dyk (3.6) 으로 표현되며 이때 pk(x|zk)는 N(Aµk, AA>+ I)를 따르고, pk(x|yk, zk)는 N(Ayk, I)를 따른다. x의 주변분포는 최종적으로
p(x)=
K
X
k=1
pk(zk) Z
yk
pk(x|yk, zk)pk(yk)dyk, (3.7)
으로 표현된다.
본 연구에서의 확률적 reduced K-means는 가중치 행렬 A에 대한 특별한 제약이 존재하지 않아 A>를 적 재 행렬로 해석할 수 없다. 무어-펜로즈 유사 역행렬(Moore–Penrose pseudoinverse matrix) A+를 정의하면, A+E(x)= E(yk), (k = 1, . . . , K)가 성립하게 되고, 이는 원 자료 X 차원상에서의 군집 중심값에 A+가중치 행렬을 통해 축소 차원에서의 군집 중심 값을 구할 수 있다고 해석할 수 있다. 즉, A+를 적재 행렬로 해석한다.
확률적 reduced K-means 모형의 추정은 로그 가능도 l(θ)= ln (p(X|θ))가 최대가 되도록 하는 모수를 찾 아줌으로써 이루어진다. 하지만, 식 3.7의 로그 가능도를 직접적으로 계산하는 것은 어려운 문제이다. 따라서 확률적 reduced K-means 모형에서는 로그 가능도를 직접적으로 높이는 대신, EM 알고리듬을 이용하여 로그 가능도의 하한 값이 최대가 되도록 하는 모수 값을 추정한다. 이때, 개체 x가 k번째 요인에 속하는지에 대한
정보 zk와 축소 차원에서의 k번째 요인의 잠재변수 yk(k= 1, . . . , K)를 결측된 자료로 간주하도록 한다. 추정하 고자 하는 모수를θ = {π1, . . . , πK, µ1, . . . , µK, A, }라 할 때, 해당 모수를 구하기 위한 EM 알고리듬은 다음에 정리되어있다. EM 알고리듬의 유도과정은 Appendix에 정리되어 있다.
알고리듬
단계 1 t= 0에서 ˆπ(0)1 , . . . , ˆπ(0)K, ˆµ(0)1 , . . . , ˆµ(0)K, ˆA(0), ˆ(0)의 초깃값을 임의로 지정한다.
단계 1 E-step : t+ 1(t = 0, 1, 2, . . . , )번째 반복에 대해서 다음의 수식에 따라 k = 1, . . . , K, i = 1, . . . , N에 다음의 기대값을 구한다.
(a) γ(zik)(t+1)= p(zik= 1|xi)=PKˆπ(t)k p(xi|zik=1) l=1ˆπ(t)l p(xi|zil=1),
(b) e(t+1)ik = E[yik|xi]= ˆµ(t)k + ˆA(t)>(M(t+1))−1(xi− ˆA(t)ˆµ(t)k),
(c) v(t+1)ik = E[yiky>ik|xi]= I − ˆA(t)>(M)(t+1)−1Aˆ(t+1)+ E(yik|xi)E(y>ik|xi), 여기서 M(t+1)= ˆA(t)Aˆ(t)>+ (t)I.
단계 1 M-step : t+1(t = 0, 1, 2, . . .)번째 반복에 대해서 k = 1, . . . , K에 대하여 추정치를 아래와 같이 갱신한다.
(a) ˆπ(t+1)k =PNi=1γ(zNik)(t+1), (b) ˆµ(tk+1)=PNi=1PNγ(zik)(t+1)e(t+1)ik
i=1γ(zik)(t+1) , (c) ˆA(t+1)= PNi=1PK
k=1γ(zik)(t+1)xie(t+1)>ik PN i=1PK
k=1γ(zik)(t+1)v(t+1)ik −1
, (d) ˆ(t+1)=PNi=1PKk=1γ(zik)(t+1)
x>ixi−2x>iAˆ(t+1)e(t+1)ik +tr(v(t+1)ik Aˆ(t+1)>Aˆ(t+1))
N J .
단계 1 위의 단계 2와 단계 3을 수렴할 때까지 반복한다.
단계 1 각 개체마다 사후 확률(γ(zik))이 가장 큰 군집으로 할당한다.
4.모의실험
모의실험을 통해 확률적 reduced K-means 모형의 성능을 확인하고 reduced K-means 모형과 가우지안 혼합 모형, 그리고 주성분 분석을 통해 차원 축소를 진행한 후에 K-means 모형으로 군집분석을 진행하는 Tandem 군집분석의 성능과 비교하였다. 이때, 확률적 reduced K-means 모형과의 동등한 비교를 위해 가우지안 혼합 모형의 공분산 행렬은 항등 행렬(identity matrix)로 제약하기로 하며, 모의실험 자료 또한 그에 맞도록 구성했 다. 본 모의실험을 통해 다양한 자료 유형에서, 차원 축소가 군집분석에 어떤 영향을 미치는지, 그리고 차원 축소와 군집분석을 동시에 진행하는 것이 Tandem 군집분석에 비해 어떤 이점이 있는지 파악하고자 하였다.
모형 평가 기준으로는 adjusted rand index (ARI)와 오분류율(misclassification rate)을 이용했다. 또한, 각 군집 분석 방법론마다 20개의 초깃값을 시도했다.
4.1.모의실험 자료 생성
Timmerman 등 (2010)에서 reduced K-means 모형은 X = UFB>+ ER로 나타낼 수있음을 보인다. 여기서 U(N × K)는 군집 배정 행렬을 뜻하며, 각각의 개체가 어느 군집에 속하는지를 지시한다. 개체 i가 군집 k에 속할 경우 uik = 1, 아닐 경우 uik = 0이며, PKk=1uik = 1을 만족한다. F(K × Q)는 축소 차원에서 군집의 중심을 나타내는 행렬로 fkq는 k번째 군집의 q번 째 요소 점수(component score)이다. B(J × Q)는 원 자료 X(N × J)
를 군집을 설명하는 축소 차원(Q 차원)으로 투영시키는 열 방향 정규 직교 적재 행렬(columnwise orthonormal loading matirx)이다. ER은 reduced K-means에서의 잔차항이다. 이에 따라 해당 연구에서는 모의실험 자료 생성 모형을 다음과 같이 구성한다.
X= UFB>+ EB>+ E⊥B⊥> (4.1) 여기서 B⊥(J × (J − Q))은 B>의 영 공간(null space)의 열 방향 정규 직교 기저(columnwise orthonormal basis) 로 구성하도록 했다. 즉 B>B⊥= 0 을 만족한다. E(N × Q)는 군집과 관련 있는 부분 공간에서의 잔차이며 각 원소는 N(0, σ2E)를 따른다. E⊥(N × (J − Q))는 그 외 공간에서의 잔차이고 각 원소는 N(0, σ2E⊥)를 따른다. 군 집이 내포되어 있는 자료 X는 군집 중심 행렬, 군집의 부분 공간에 놓여있는 잔차, 그리고 군집의 부분 공간과 직교한 부분 공간에 놓여있는 잔차로 완전하게 설명될 수 있다.
이 모형을 활용하여 모의실험을 위한 자료를 다음과 같이 구성하였다. 군집의 개수는 네 개(K= 4), 축소 차원의 개수는 두 개(Q = 2)로 고정했다. 또한 네 가지 요소를 활용하여 자료를 생성했다. 첫 번째 요소는 군집이 중첩되는 수준으로 이를 위해 군집 중심에 대한 정보를 가지고 있는 F를 다음의 구조로 생성하도록 한다.
F=
c −c c −c c −c −c c
>
. (4.2)
여기서 c에 의해서 군집 중심부 간의 거리가 결정되며, c가 클수록 군집 간 경계가 명확히 구별될 것이다. 반면, c가 작을수록 군집 간에 중첩되는 비율이 증가하게 될 것이다. c= 5와 c = 2.5인 경우를 고려했다.
두번째 요소는 전체 잔차의 분산 중에서 군집을 설명하는 축소 차원 하에 놓여있는 잔차가 설명하는 비중으로 proportion of subspace residual (PSR)을 고려했으며 식은 다음과 같다.
PSR= σ2E σ2E+ σ2E⊥
. (4.3)
이때σ2E = 1로 고정하도록 한다. c = 5인 경우 PSR = {0.05, 0.10, 0.15} 세 가지 수준을 고려했고 c = 2.5인 경우 PSR= {0.2, 0.25, 0.3} 세 가지 수준을 고려했다. 이는 c = 2.5인 경우 너무 작은 PSR 수준에서 군집이 거의 생성되지 못했기 때문이며, c= 5인 경우보다 조금 더 높은 수준의 PSR을 설정했다.
세 번째 요소는 변수의 개수이다. 변수의 개수가 10개인 경우와 50개인 경우, 그리고 100개인 경우 세 가 지를 고려했다. 이때, 변수의 개수에 따른 적재 행렬 B는 (8 × 2) 행렬에 0((J − 8) × 2) 행렬을 첨가한 형태이다.
예를들어 변수 개수 50개인 경우의 B는 다음과 같다.
B(50×2)=
0.25 0.25 0.25 0.25 0.25 0.25 0.56 0.56 0 0 , . . . , 0 0.41 0.41 0.41 −0.41 −0.41 −0.41 0 0 0 0 , . . . , 0
>
. (4.4)
마지막으로 네 번째 요소로는 표본 크기(sample size)를 고려했으며, 각 군집별 표본 크기가 100(총 400 개)인 경우와 50(총 200개)인 경우를 고려했다. 생성된 자료에 대한 예시는 Figure 1과 같다. Figure 1은 열 방향 정규 직교 행렬 B로 정의되는 축소 차원에 원 자료를 투사한 결과(XB)이며 실질적인 군집 구조를 드러 낸다. 실제 군집 구조에 PSR 수준과 변수의 개수는 영향을 주지 않는다. 각 요소의 조합마다 10개의 자료를 형성했다.
4.2.모의실험 결과
Table 1는 군집 별 표본 크기가 100일 때 c = 2.5인 경우의 변수 개수와 PSR 수준별 평균 ARI와 오분류율 (MR)을 방법론별로 요약한 결과이다. 편의상 확률적 reduced K-means 군집분석, reduced K-means 군집분석,
(a) c= 5, number of samples = 200 (b) c= 2.5, number of samples = 200
(c) c= 5, number of samples = 400 (d) c= 2.5, number of samples = 400 Figure 1:Example of true cluster structure in two-dimensional plane in simulation datasets.
Tandem 군집분석, 가우지안 혼합 모형, K-means 군집분석을 각각 PRKM, RKM, TKM, GMM, KM으로 표현 했다. Table 2와 Table 3는 각각 군집 별 표본 크기가 50일 때, c= 5인 경우와 c = 2.5인 경우의 변수 개수와 PSR 수준별 평균 ARI와 오분류율을 방법론별로 요약한 결과이다. 이때의 결과도 표본 크기가 100일 때의 결과와 같은 방식으로 정리했다. 표본 크기가 100이면서 c= 5인 경우의 실험 결과와 해석은 생략했으며 Lee (2021)에 정리되어 있다.
4.2.1. 군집 당 표본 크기가 100이고 c= 2.5인 경우
군집당 표본 크기가 100이고 군집 중첩이 발생한 경우 (c= 2.5)의 결과는 Table 1에 정리되어 있다. 변수가 10 개인 결과를 살펴보면 PSR 수준에 상관없이 모두 RKM이 가장 높은 평균 ARI를 주었으나 다른 방법론도 평 균 ARI가 크게 다르지 않았다. 변수 수에 비해 군집당 표본 크기가 충분하다면 군집 중첩이 있는 자료에서도 방법론에 따른 성능 차이는 크지 않다.
변수의 개수가 50개인 경우에 모든 PSR 수준에서 RKM이 가장 높은 ARI를 형성했으며 PRKM의 경우는 그다음으로 높았다. 반면, 다른 나머지 방법론의 경우 PSR 수준에 관계없이 ARI가 상대적으로 낮게 형성된 것을 볼 수 있었다.
변수의 개수가 100개인 경우에 PSR 수준 0.2에는 의미 있는 군집이 형성된 경우는 없었다. PSR 수준 0.25 에서는 PRKM이 평균 ARI 0.634의 가장 좋은 결과를 얻었으며 나머지 방법의 경우 ARI가 0.5 이하였다. 이 는 군집 별 표본 크기가 변수의 개수와 동일한 상황에서 PSR이 지나치게 작을 경우 올바로 군집을 형성하는 방법론은 없었지만, PSR이 일정 수준보다 높아질 경우에는 PRKM이 다른 방법론보다 군집을 잘 형성할 수 있음을 시사한다. PSR 수준 0.3에서는 RKM이 0.831로 가장 높은 평균 ARI를 가졌으며, PRKM이 0.810으로 두번째로 높았고, TKM은 0.6대, KM과 GMM의 경우에는 0.5대로 낮은 평균 ARI를 얻었다.
Table 1:Comparison of average ARI and misclassification rates for each cluster analysis methods when the sample size for each cluster is 100 and c= 2.5
Methods PSR 10 variables 50 variables 100 variables
ARI MR ARI MR ARI MR
PRKM
0.20 0.955 0.017 0.545 0.232 0.115 0.598
0.25 0.960 0.015 0.869 0.051 0.634 0.169
0.30 0.962 0.015 0.912 0.034 0.810 0.076
RKM
0.20 0.961 0.015 0.694 0.150 0.093 0.579
0.25 0.962 0.014 0.904 0.037 0.439 0.283
0.30 0.966 0.013 0.930 0.027 0.831 0.067
TKM
0.20 0.938 0.024 0.339 0.354 0.135 0.528
0.25 0.955 0.017 0.731 0.110 0.421 0.276
0.30 0.963 0.014 0.839 0.064 0.662 0.143
GMM
0.20 0.933 0.026 0.379 0.348 0.150 0.556
0.25 0.954 0.018 0.614 0.196 0.376 0.354
0.30 0.961 0.015 0.804 0.079 0.558 0.208
KM
0.20 0.951 0.019 0.369 0.348 0.147 0.532
0.25 0.956 0.017 0.692 0.134 0.340 0.369
0.30 0.962 0.015 0.835 0.066 0.569 0.198
Table 2:Comparison of average ARI and misclassification rates for each cluster analysis methods when the sample size for each cluster is 50 and c= 5
Methods PSR 10 variables 50 variables 100 variables
ARI MR ARI MR ARI MR
PRKM
0.05 0.807 0.126 0.036 0.651 0.019 0.665
0.10 1.000 0.000 0.982 0.007 0.764 0.132
0.15 1.000 0.000 0.997 0.001 0.981 0.007
RKM
0.05 1.000 0.000 0.067 0.610 0.026 0.651
0.10 1.000 0.000 0.992 0.003 0.268 0.437
0.15 1.000 0.000 1.000 0.000 0.889 0.049
TKM
0.05 0.740 0.112 0.068 0.608 0.046 0.625
0.10 1.000 0.000 0.805 0.079 0.447 0.266
0.15 1.000 0.000 0.970 0.012 0.799 0.080
GMM
0.05 0.815 0.113 0.075 0.594 0.051 0.620
0.10 1.000 0.000 0.805 0.087 0.345 0.407
0.15 1.000 0.000 0.984 0.006 0.748 0.112
KM
0.05 1.000 0.000 0.090 0.567 0.044 0.627
0.10 1.000 0.000 0.839 0.072 0.409 0.313
0.15 1.000 0.000 0.988 0.005 0.798 0.085
4.2.2. 군집 당 표본 크기가 50이고 c= 5인 경우
표본 크기가 50개이고 군집 중첩이 없는 경우(c= 5)의 결과는 Table 2에 정리되어 있다. 변수가 10개일 경우에 PSR 수준 0.05일 때, RKM과 KM의 경우 군집이 완벽하게 형성된 것을 확인할 수 있으나, TKM에서는 0.7대의 평균 ARI를 얻었다. 특히 PRKM에서는 0.807의 상대적으로 낮은 평균 ARI를 얻은 것을 볼 수 있으며, 평균 오분류율은 0.126으로 가장 컸다. 이는 해당 유형의 자료의 경우 PRKM의 성능이 10개 자료에 따라 편차가
Table 3:Comparison of average ARI and misclassification rates for each cluster analysis methods when the sample size for each cluster is 50 and c= 2.5
Methods PSR 10 variables 50 variables 100 variables
ARI MR ARI MR ARI MR
PRKM
0.20 0.931 0.027 0.151 0.553 0.062 0.615
0.25 0.952 0.018 0.649 0.172 0.235 0.481
0.30 0.952 0.018 0.840 0.064 0.547 0.232
RKM
0.20 0.950 0.019 0.188 0.489 0.065 0.603
0.25 0.951 0.019 0.538 0.225 0.108 0.555
0.30 0.960 0.015 0.860 0.055 0.254 0.415
TKM
0.20 0.898 0.040 0.150 0.538 0.090 0.588
0.25 0.942 0.018 0.480 0.249 0.214 0.467
0.30 0.949 0.020 0.700 0.126 0.426 0.275
GMM
0.20 0.855 0.058 0.161 0.504 0.088 0.588
0.25 0.934 0.025 0.411 0.314 0.190 0.494
0.30 0.948 0.020 0.590 0.192 0.301 0.403
KM
0.20 0.909 0.035 0.187 0.479 0.085 0.585
0.25 0.941 0.023 0.419 0.298 0.172 0.500
0.30 0.950 0.019 0.592 0.185 0.281 0.393
매우 심했기 때문이며, 초기치를 주는 횟수(20개)가 부족했던 것이 원인이었던 것으로 추측된다. PSR 수준 0.10과 0.15인 경우에서는 모든 방법론이 완벽하게 군집을 형성했다.
변수가 50개일 경우의 결과를 살펴보면, PSR 수준 0.05에서는 제대로 된 군집을 형성하는 방법론은 없었 다. PSR 수준 0.10에서는 RKM이 0.992로 가장 높은 평균 ARI의 결과를 얻었으며, PRKM는 평균 ARI 0.982 로 두 번째로 높았다. 반면 다른 방법론의 경우 평균 ARI가 0.85보다 낮은 수준이었다. PSR 수준 0.15인 경우 에도 마찬가지로, RKM이 완벽한 군집을 형성해 평균 ARI가 1이었으며, PRKM이 그다음으로 0.997이었다.
하지만 다른 방법론의 경우에도 0.95 이상으로 크게 뒤떨어지지 않는 ARI 결과를 주었다.
변수가 100개일 경우에는 PSR 수준 0.1인 경우에는 오직 PRKM이 0.764의 평균 ARI를 가졌으며 나머지 방법론의 경우 모두 0.5보다 낮은 ARI를 주었다. 특히 RKM의 경우 TKM보다도 평균 ARI가 낮았다. PSR 수준이 0.15인 경우에도, PRKM의 경우 0.981으로 가장 높은 평균 ARI 결과를 얻었으며, RKM이 0.889로 그 보다는 낮은 평균 ARI를 기록했다. 즉, 군집 중첩이 발생하지 않은 자료에서 군집당 표본 크기가 변수 수 보다 작은 경우 RKM의 성능이 PRKM에 비해 상대적으로 많이 떨어진다는 점을 알 수 있다.
4.2.3. 군집 당 표본 크기가 50이고 c= 2.5인 경우
군집당 표본 크기가 50개이고 군집 중첩이 발생한 경우(c= 2.5)의 결과는 Table 3에 정리되어 있다. 변수가 10개일 경우에 PSR 수준이 0.2인 경우 RKM과 PRKM이 차례로 0.950, 0.931로 높은 평균 ARI를 주었으며, GMM의 경우 0.855로 가장 낮은 평균 ARI를 얻었다. PSR 수준이 0.25 이상일 때는 전체 방법론에서 비등하게 높은 평균 ARI를 보였다.
변수가 50개일 경우에 PSR 수준 0.2에서 의미 있는 군집을 형성한 방법론은 없었다. PSR 수준 0.25에서 는 PRKM의 경우 0.649로 가장 높은 평균 ARI를 얻었으며, RKM의 경우 0.538로 그다음으로 높았다. 다른 방법론의 경우에는 0.5보다 낮은 평균 ARI를 보였다. PSR 수준 0.3인 경우에는 RKM과 PRKM 각각 평균 ARI 0.860과 0.840으로 높았으며, 다른 방법론의 경우 평균 ARI가 0.7 이하였다. 여기서도 마찬가지로 군집당 표본 크기가 변수 수와 같은 경우에 PSR이 일정 수준보다 낮을 때 RKM의 성능이 PRKM에 비해 떨어진다는
(a) 10 variables (b) 50 variables
(c) 100 variables
Figure 2:ARI line plot for different number of variables and PSR level, when the number of samples for each cluster is 50 and c= 2.5.
사실을 알 수 있다.
마지막으로 변수가 100개일 경우의 결과를 살펴보면, PSR 수준 0.2와 0.25에서 의미 있는 군집이 형성된 방법론은 없었다. 하지만 PSR 수준 0.3에서는 PRKM의 경우 0.547으로 가장 높은 평균 ARI를 주었으며, TKM 의 경우 두 번째로 높은 0.426의 평균 ARI를 주었다. 즉, 군집 중첩이 있는 자료에서도 군집 당 표본 크기보다 변수의 개수가 2배가량 많을 경우, PRKM의 성능이 다른 방법론에 비해 군집을 잘 형성한다.
4.2.4. 모의실험 결과 해석
전반적으로 PSR 수준이 낮아질수록, 변수의 개수가 많아질수록, 그리고 군집 당 표본 크기가 작아질수록 모든 방법론에서 군집이 올바로 형성되는 것이 어려움을 관찰했으며, 방법론 간의 성능 차이도 커진다는 것을 알 수 있었다. 이 상황에서 차원 축소와 군집분석을 동시에 진행하는 방법이 기존의 방법보다 더 좋은 군집 형성 을 보여준다. 또한, 군집 중첩이 없으면서(c= 5) 군집당 표본 크기가 변수 개수에 비해 크거나 같은 경우에는 오히려 TKM이 GMM과 KM보다 평균 ARI가 낮은 것을 볼 수 있었다. 이는 주성분 분석을 통한 차원 축소가 오히려 군집의 구조를 가릴 수 있다는 것을 뜻한다. 한편 군집의 중첩이 일어나는 경우에는(c = 2.5) TKM 이 GMM과 KM보다 높은 평균 ARI를 주기는 했으나, PRKM과 RKM만큼 높지는 않았기에 주성분 분석이 군집분석에적절한 차원 축소를 했다고는 생각할수 없다.
각 군집별 표본 크기가 변수 수보다 큰 경우, RKM이 PRKM을 포함한 다른 방법론보다 ARI가 항상 안 정적으로 높았다. 이는, PRKM이 찾아낸 축소차원이 RKM에 비해 적절하지 못했기 때문인 것으로 생각된다.
실험 과정에서 많은 경우에 PRKM이 찾아낸 축소차원 하에서 군집의 형태는 원형이 아닌 타원형인 경우가 많았다. 이는 PRKM에서 A를 정규 직교 행렬로 제약하지 않아 AA> = I가 만족하지 않았기 때문인 것으로 보인다. 따라서 차원축소를 위한 충분한 관측치가 있다면 RKM을 사용하는 것이 더 나은 선택일 것이다.
그러나각 군집 당 표본 크기가 변수 수 보다 작은 경우에서는 항상 PRKM의 ARI가 RKM의 ARI를 상회 했다. 또한, 군집 중첩이 발생하면서(c = 2.5) PSR 수준이 0.25인 경우 중에, 변수 수와 군집 당 표본 크기가 동일한 경우도 마찬가지로 PRKM의 ARI 결과가 RKM의 ARI 결과를 상회했다. 따라서 군집 당 표본 크기가 변수의 개수에 비해 작아질수록 작은 PSR 수준에서 PRKM이 RKM보다 더 높은 군집 분석 성능을 보여준다.
이를 확인하기 위해 군집별 표본 크기가 50이고, 군집 중첩이 발생한(c = 2.5) 자료를 변수 10개, 50개, 100 개에 대해서 PSR 수준 0.1에서 0.5까지 0.05 간격으로 10개씩 형성했으며, 각 군집분석 방법론의 평균 ARI를 확인했다. 이때도 초깃값은 20개를 부여했다.
결과는 Figure 2에서 정리되어 있으며 모든 방법론에서 변수 개수가 표본 크기인 50보다 많아질수록 PSR 수준에 따라 평균 ARI가 완만하게 증가하는 것을 알 수 있다. 그러나 RKM의 경우 다른 방법론에 비해 특히 더 변수의 개수에 영향을 많이 받는 것을 알 수 있으며, 변수 개수 100개일 때는 오히려 차원 축소를 고려하지 않는 방법론보다 평균 ARI가 낮은 구간도 나타난다. 반면에 PRKM의 경우에는 PSR 수준에 따라 평균 ARI 가 증가하는 정도가 변수 개수에 대해 가장 덜 민감함을 볼 수 있다. 따라서 군집 당 표본 크기가 변수 개수에 비해 충분히 크지 않은 상황에서는 PRKM을 선택하는 것이 가장 안전한 선택이라고 할 수 있다.
5.보스턴 자료분석
라벨이 없는 Harrison과 Rubinfeld (1978)의 보스턴 자료(Boston data)에 본 연구에서 제안하는 확률적 reduced Kmeans 군집분석 방법론을 적용했다. 보스턴 자료는 506개의 관측치을 가지고 있고, 주택 가치와 관련된 변수 14개로 구성되어 있으며 변수에 대한 설명은 Table 4에 정리되어 있다. 단, CHAS 변수는 이항 변수이며 분석에 포함할 경우 CHAS 변수 값대로 군집이 형성되어 분석에서 제외하여 총 13개의 변수를 사용했다. 좀 더 나은 군집분석 결과를 위해 CRIM, NOX, DIS, MEDV 변수는 로그 변환을 해줬으며, ZN 변수는 1을 더한 후 로그 변환을 했다. INDUS, LSTAT 변수는 제곱근 변환, PTRATIO와 AGE 변수는 각각1/PTRATIO1/2와 1/AGE1/5로 역변환을 시도했다. B 변수는 분포가 지나치게 치우쳐 있어 변수 변환이 도움이 되지 않아 그대 로사용했다. 이때, 보스턴 자료에 대한 오류를 수정한 Gilley와 Pace (1996)의 자료를 이용했다. 군집의 수는 두개로 정했으며(K= 2), 축소 차원의 수도 2로 정하여(Q=2) 표준화를 거친 자료를 가지고 확률적 reduced K means를 적용시켰다. 보스턴 자료는 라벨이 없는 자료이기 때문에 해석적인 측면에 맞추어 군집분석 방법론 의 성능을 판단했다.
본 연구에서 제안한 확률적 reduced K-means 군집분석을 적용했을 때, 특징이 다른 개체들로 군집이 형 성되는가를 알아보고자 하였다. 분석 결과 제 1 군집에는 132개의 개체가 배정이 되었고, 제 2 군집에는 374 개의 개체가 배정되었다. 원 자료의 변수에 대한 군집 별 평균값은 Table 5에 정리되어 있다. 제 1 군집의 경우 CRIM, INDUS, NOX, AGE, RAD, TAX, PTRATIO, LSTAT의 변수 값이 높았다. 반면에 제 2 군집에서는 ZN, RM, DIS, B, CMEDV의 변수 값이 더 높았다. 따라서 제 1 군집은 도심에 가깝고 슬럼화가 일어난 지역이라 고 추측할 수 있고 제 2 군집은 보스턴의 외곽에 위치한 주거지역에 좀 더 가까운 지역이라고 추측해 볼 수 있다. 특히 B 변수의 경우, 흑인의 비율이 너무 낮거나 높은 경우에 높은 값을 가지기 때문에 제 2 군집의 경우 흑인의 비율이 낮은 지역이라고 추측할 수 있다.
본 연구에서 사용한 수정된 보스턴 자료에는 실제 각 개체에 대한 위도와 경도 변수가 포함되어 있어, 실 제 군집이 형성된 위치를 확인할 수 있었다. Figure 3과 같이 각 개체의 위치를 살펴본 결과, 현재의 보스턴의 중심지에 제 1 군집이 형성된 것을 볼 수 있었다. Choi와 Baek (2017)에 따르면 20세기 초 미국은 대규모 이 민과 도시의 발전이 진행되면서 대도시의 인구가 급격하게 증가하였고, 도심지의 슬럼화가 일어났다. 특히,
Table 4:Variable description of Boston data
변수 명 변수 설명
CRIM 지차치별 1 인당 범죄율
ZN 25,000평방피트가 넘는 부지에 대한 주거지 면적 비율
INDUS 지자치별 비-소매 업종이 차지하는 면적의 비율
CHAS Charles 강에 대한 더미(dummy) 변수 (강의 경계일 시 1, 그렇지 않을 시 0)
NOX 10ppm 당 질소산화물 농도
RM 주택 당 평균 방의 개수
AGE 1940년 이전에 지어진 건물에 대한 소유 주택 비율
DIS 보스턴 고용 센터 5곳과의 가중 거리
RAD 방사선 고속도로에 대한 접근성 지수
TAX 1만 달러당 전체 재산세율
PTRATIO 지자체별 학생-교사 비율
B 1000(Bk − 0.63)2(Bk : 지자체당 흑인의 비율)
LSTAT 모집단의 하위 계층 비율
CMEDV 수정된 자가주택 가치의 중간값 (단위 : 1000달러)
Table 5:Mean of the variable in original Boston data according to PRKM cluster result
Variable CRIM ZN INDUS NOX RM AGE DIS RAD TAX PTRATIO B LSTAT CMEDV Cluster 1 12.8 0.0 18.1 0.7 6.0 89.8 2.1 24 666 20.2 288.1 18.6 16.4 Cluster 2 0.4 15.4 8.7 0.5 6.4 61.1 4.4 4.5 317.3 17.8 380.9 10.6 24.7
1960년에서 80년대 산업구조 변환기 미국은 급격한 교외화 및 도심 쇠퇴, 임대공동주택단지의 슬럼화 문제가 심했으므로 군집분석의 결과는 합리적이라 생각된다.
Figure 4은 군집분석 방법론별 결과를 축소된 차원에 보스턴 자료를 투사하여 2차원 평면에 나타낸 그림이 다. GMM과 KM의 경우에는 군집분석을 먼저 한 후, 주성분 분석으로 2차원 평면에 차원축소하여 나타냈다.
오직 PRKM만이 군집을 나누는 축소 차원을 적절하게 찾으면서도 합리적인 군집 할당을 했음을 알 수 있다.
반면 RKM의 경우 군집을 나눌 수 있는 축소 차원은 적절하게 찾았지만 군집 배정을 합리적으로 하지 못했다.
PRKM과는 다르게 RKM에서는 두 군집 간의 거리가 가까워 제 2 군집으로 할당되었어야 하는 개체 중 일부가 제 1 군집으로 잘못 할당된 것으로 보인다.
반면 보스턴 자료에서 PRKM이 찾아내는 공간은 직교 공간이 아닌 다른 공간(두 축의 각도는 약 110.4◦) 이기 때문에 두 군집 사이의 거리를 넓히는 작용이 일어났고, 따라서 RKM보다 더 적절한 군집분석 결과를 얻 었을 것이다. 보스턴 자료는 RAD와 TAX 등의 변수에서 값이 몰려있는 것이 군집형성에 주요한 역할을 했고, 군집 크기가 다른 비대칭 데이터이며, 실제 군집 차원상에서의 군집 형태가 원형인지도 알 수 없다. 즉, 모의 실험 자료와는 특성이 다른 자료이며, 이러한 유형의 자료에서는 관측치의 개수가 충분함에도 모의실험의 결과와 달리 RKM의 성능이 오히려 좋지 않은 것으로 생각된다.
한편, TKM에서는 군집을 나누기에 적당한 축소 차원을 적절하게 찾지 못했으며, 주성분 분석을 통한 차 원 축소 방법은 보스턴 자료를 군집분석할 때 좋은 선택이 아님을 알 수 있다. GMM과 KM에서도 거의 동일한 결과를 얻었다.
6.결론
차원 축소와 군집분석을 개별적으로 진행하는 Tandem 군집분석에서의 축소된 차원은 군집의 구조를 적절히 반영하지 않을 가능성이 있었다. 본 연구에서는 이런 Tandem 군집분석의 문제를 해결하기 위해 개발된 차원
Figure 3:Location of objects in Boston data.
축소와 군집분석을 동시에 진행하는 방법론 중 하나인 reduced K-means를 확률적인 모델로 전환을 시도했다.
이를 확률적 reduced K-means(PRKM)이라 명명했으며, 모델 추정을 위해 EM 알고리듬을 활용했다. 또한 그 성능을 기존의 reduced K-means 모형과 Tandem 군집분석, 그리고 차원 축소를 진행하지 않는 가우지안 혼합 모형(공분산을 제약함)과 K-means 모형과 비교했다.
본 연구는 변수의 개수에 비해 표본 크기가 작고, PSR이 작은 자료에 적합한 군집 분석 방법론을 제시했 다는데 의의가 있다. 모의실험 결과, 변수의 개수가 군집 당 표본 크기보다 상대적으로 클수록, 그리고 PSR 이 작을수록 reduced K-means 기반의 군집분석이 기존의 Tandem 군집분석과 차원 축소를 포함하지 않는 군 집분석보다 성능이 뛰어나다는 점을 확인할 수 있었다. 특히, 변수의 개수가 군집 당 표본 크기보다 큰 경우, 확률적 reduced K-means 모형의 성능은 기존의 reduced K-means의 성능을 상회했다. 이에 대한 원인은 변수 의 개수에 비하여 상대적 표본 크기가 작을 때, 비 확률적 차원 축소 방법보다는, 확률적 모형의 차원 축소가 더 적절하기 때문이었던 것으로 추정된다.
확률적 관점에서 확률적 reduced K-means 모형은 쉽게 확장이 가능하다는 장점이 있다. 먼저 EM 알고리 듬을 통해 추정되기 때문에, 결측이 존재하는 자료에 대해서 쉽게 확장할 수 있다. 군집에 대한 고려 없이 결측 대체를 진행한 후에 군집분석을 진행하는 것보다 본 모델에 결측자료에 대한 추정까지 통합하여 군집분석을 진행하는 것이 더 합리적일 수 있을 것이다. 또한, 비정규분포를 따르는 연속형 변수나 범주형 변수로의 확장 도 가능하여 좀 더 다양한 유형의 자료에 적합하도록 확장시킬 수 있을 것이다. 마지막으로, 사전분포를 고려 할 수 있기 때문에 베이지안적 모형으로도 확장할 수 있을것이다. 특히 본 연구에서 유도한 확률적 reduced K-means 모형의 EM 알고리듬에서는 군집 중 일부가 소멸되는 현상이 발생했으며 특히 PSR 수준이 낮은 경우 더 심한 경향이 있었다. 이는, 초기치에 따라 일부 군집의 비율(πk; k= 1, . . . , K)이 지나치게 0에 가까워지는
(a) PRKM (b) RKM
(c) TKM (d) GMM
(e) KM
Figure 4: Cluster structure for Boston data in two-dimensional planes produced by different cluster analysis methods.
경우가 있어 생기는 문제로 보인다. 이를 해결하기 위해 군집의 비율에 사전 확률(가령, πk= 1/K k = 1, . . . , K) 을 부여하여 잘못된 초기치에 대한 민감성을 낮추는 것이 한 방법이 될 수 있을 것이다.
본 연구에서는 군집의 개수(K)와 축소 차원의 수(Q)를 정하는 방법에 대해서는 다루지 않았다. 비확률 적인 군집분석에서의 군집의 개수를 정하는 문제에 대해서 Milligan과 Cooper (1985)는 Calinski-Harabasz 인덱스를 비롯한 30가지 방법을 비교했다. De Soete와 Carroll (1994)은 차원 축소를 위해서 Q는 min(K − 1, J) 보다 작게 정한다고 언급하고 있다. Vichi와 Kiers (2001)는 만일 min(K − 1, J)보다 작은 Q로도 군집구조가 설명될 경우, 더 적은 수의 차원을 시도해보는 것이 바람직하다고 말한다. 그러나 확률적인 군집분석 모형을
위한 K와 Q를 정하는 방법은 연구가 많이 진행된 바가 없다. 특히 확률적 reduced K-means 모형에서는 K와 Q가 서로 의존적이기 때문에 이는 더욱 어려운 문제이다. 따라서 본 연구에서는 해석에 초점을 맞추어 좀 더 합리적인 결과를 주는 군집의 개수와 축소 차원의 수를 사용했다. 하지만, AIC와 BIC를 활용하여 K와 Q를 보다 정량적인 기준으로 결정하는 방법에 대한 연구가 진행될 필요가 있다.
한편으로, 확률적 reduced K-means 모형에서 형성되는 축소 차원은 직교 공간이 아니다. 이에 따라서 축 소 차원의 랭크가 1인 경우를 제외하고는 기존의 reduced K-means과는 달리 변수에 대한 설명이 어려워진다.
따라서, 가중치 행렬(A)을 정규 직교 행렬로 제약하여 모형을 추정하는 연구도 필요할 것이며, 모의실험과 같 은 유형의 자료에서 관측치가 충분한 경우 PRKM의 성능이 RKM에 비해 떨어지는 문제도 해결될 가능성도 있다. 또한, 본 연구는 확률적 주성분 분석 모형을 확장시켰기 때문에 자료 x의 공분산의 잔차항을 I로 제약 했다. 모형의 일반성을 높이기 위해서 공분산의 잔차항을 일반적인 공분산 행렬(general covariance matrix)로 확장시키는 연구도 가능할 것이다.
Appendix:확률적reduced K-means의EM알고리듬 유도
확률적 reduced K-means 모형에서 자료 X의 로그 가능도는 다음을 만족한다. 이때, 간단한 표기를 위해 잠재 변수를 Y로, 각 개체가 어떤 군집에 해당하는지에 대한 정보를 Z로 표기했다. q(·)는 임의의 확률 밀도 함수를 뜻한다.
l(θ)= ln (p(X|θ))
= ln X
Z
Z
Y
p(X, Y, Z|θ)dY
= ln X
Z
Z
Y
q(Z)q(Y|Z)p(Y|X, Z, θ)p(Z|X, θ)p(X|θ) q(Z)q(Y|Z) dY
≥X
Z
q(Z) Z
Y
q(Y|Z)ln p(Y|X, Z, θ)p(Z|X, θ)p(X|θ) q(Z)q(Y|Z) dY
!
=X
Z
q(Z) Z
Y
q(Y|Z)
"
ln p(Z|X, θ) q(Z)
!
+ ln p(Y|X, Z, θ) q(Y|Z)
!
+ ln (p(X|θ))
# dY
= ln (p(X|θ)) −X
Z
q(Z)ln q(Z) p(Z|X, θ)
!
−X
Z
q(Z) Z
Y
q(Y|Z)ln q(Y|Z) p(Y|X, Z, θ)
!
dY (A.1)
식 A.1의 PZq(Z)ln (q(Z)/p(Z|X, θ)) 그리고P
Zq(Z)R
Yq(Y|Z)ln (q(Y|Z)/p(Y|X, Z, θ))dY 항은 KL-divergence 로이해할 수 있으며, q(Z)= p(Z|X, θ)와 q(Y|Z) = p(Y|X, Z, θ)를 만족할 시 두 개의 항은 모두 0이 된다. 이 경우, 로그 가능도의 하한 값은 자료 X의 본래 로그 가능도와 동일해진다. 따라서 E-step에서는 결측에 해당되 는 값 Y와 Z를 X와θ가 주어졌을 때의 기대값(expectation)으로 채우도록 한다. 또한 자료 X의 로그 가능도는
다음과 같이 표현 가능하다.
l(θ)= ln (p(X|θ))
= ln
X
Z
q(Z)p(X, Z|θ) q(Z)
≥X
Z
q(Z)ln p(X, Z|θ) q(Z)
!
=X
Z
q(Z)ln (p(X, Z|θ)) − q(Z)ln (q(Z))
=X
Z
"
q(Z)ln Z
Y
p(X, Y, Z|θ)dY
!
− q(Z)ln (q(Z))
#
≥X
Z
"
q(Z) Z
Y
q(Y|Z)ln p(X, Y, Z|θ) q(Y|Z)
!
dY − q(Z)ln (q(Z))
#
=X
Z
q(Z) Z
Y
q(Y|Z)ln (p(X, Y, Z|θ)) dY −X
Z
q(Z) Z
Y
q(Y|Z)ln (q(Y|Z)) dY −X
Z
q(Z)ln (q(Z))
= EY,Zln (p(X, Y, Z|θ)) −X
Z
q(Z) Z
Y
q(Y|Z)ln (q(Y|Z)) dY −X
Z
q(Z)ln (q(Z)) (A.2) 식 A.2에서 모수 θ와 관련이 있는 부분은 EY,Z[ln (p(X, Y, Z|θ))] 뿐이므로, M-step에서는 EY,Z[ln (p(X, Y, Z|θ))]
가 최대가 되도록 하는 모수 값을 추정하도록 한다. 이때 E-step에서 Y와 Z를 기대값으로 채웠을 때의 EY,Z[ln (p(X, Y, Z|θ))]은 다음과 같이 표현 가능하다.
EY,Zln (p(X, Y, Z|θ))
= EY,Z
ln
N
Y
i=1 K
Y
k=1
(pk(xi, yik|θ))zik|θ
= EY,Z
ln
N
Y
i=1 K
X
k=1
1zik|θ(pk(xi, yik|θ))
= EY,Z
N
X
i=1
ln
K
X
k=1
1zik|θpk(yik|θ)pk(xi|yik, θ)
=
N
X
i=1
ln
K
X
k=1
EZ
h1zik|θ
iEY|Z pk(yik|θ)pk(xi|yik, θ)
=
N
X
i=1
ln
K
X
k=1
E(1zik|θ) 1
(2π)Q/2exp −1
2E(yik−µk)>(yik−µk)
! 1
(2π)J/2|I|1/2exp −1
2E(xi− Ayik)>(xi− Ayik)
!
=
N
X
i=1
ln
K
X
k=1
E(1zik|θ) 1 (2π)Q/2exp
"
−1 2
Etr(yiky>ik)) − 2 yik>µk+ µ>kµk
#
× 1
(2π)J/2|I|1/2exp
"
−1
2 x>ixi− 2x>iAEyik+ tr(E yiky>ik A>A))
#
(A.3) 최종적으로 확률적 reduced K-means 모형의 EM 알고리듬은 E-step에서 E[yik|xi]과 E[yiky>ik|xi]를 채우도 록한다. 또한 M-step에서의 식의 간소화를 위해 각 개체 i가 각 군집 k에 속할 확률을 의미하는 γ(zik)= p(zik= 1|xi)를 추가적으로 구한다. 이어서 M-step에서는 식 A.3를 {π1, . . . , πK, µ1, . . . , µK, A, }에 대해서 최대화 한다 고 할 수 있다. γ(zik)을 이용하게 되며 이는 사후 확률(posterior)을 통해 구할 수 있으며 E[yik|xi]와 E[yiky>ik|xi]
는 다변량 정규분포의 조건부 확률을 통해 구할 수 있다. 모수 π1, . . . , πK는 라그랑주 함수를 통해 구할 수 있고, 나머지 모수의 경우에는 해당 모수로 편미분을 했을 때 0이 되는 값을 찾으면 된다.
References
Arabie P and Hubert L (1994). Cluster analysis in marketing research, Advanced Methods in Marketing Research, 160—189, Oxford: Blackwell.
Choi Y and Baek I (2017). Implication and lesson for city reconstruction experience in the United States, Monthly Housing Finance Report(in korean version), 157, 22–35.
Dempster A, Laird N, and Rubin D (1977). Maximum likelihood from incomplete data via the EM algorithm, Journal of the Royal Statistical Society, Series B (Methodological), 39, 1–38.
De Soete G and Carroll JD (1994). K-means clustering in a low-dimensional euclidean space, New Approaches in Classification and Data Analysis, 212–219, Heidelberg: Springer.
Ding C, He X, Zha H, and Simon HD (2002). Adaptive dimension reduction for Clustering High Dimensional Data, Proc 2nd IEEE Intl Conf Data Mining, 147–154.
Ghahramani Z and Hinton GE (1996). The EM algorithm for mixtures of factor analyzers, Technical Report CRG-TR-96-1, University of Toronto, Canada.
Gilley OW and Pace RK (1996). On the Harrison and Rubinfeld data, Journal of Environmental Economics and Management, 31, 403–405.
Harrison D and Rubinfeld DL (1978). Hedonic prices and the demand for clean air, Journal of Environmental Economics and Management, 5, 81–102.
Milligan GW and Cooper MC (1985). An examination of procedures for determining the number of clusters in a data set, Psychometrika, 50, 159-–179.
Rocci R, Gattone SA, and Vichi M (2011). A new dimension reduction method: factor discriminant K-means, Journal of Classification, 28, 210–226.
Roweis S (1998). EM algorithms for PCA and SPCA. Advances in Neural Information Processing Systems, Advances in Neural Information Processing Systems 10 - Proceedings of the 1997 Conference, 626—632, Elsevier.
Lee S (2021). Probabilistic reduced K-means cluster analysis, Master’s thesis, Department of Statistics, Korea University, Korea(in korean version).
Timmerman ME, Ceulemans E, De Roover K, and Van Leeuwen K (2013). Subspace K-means clustering, Be- havior Research Methods, 45, 1011–1023.
Timmerman ME, Ceulemans E, Kiers HAL, and Vichi M (2010). Factorial and reduced K-means reconsidered, Computational Statistics and Data Analysis, 54, 1858–1871.
Tipping ME and Bishop CM (1999a). Mixtures of probabilistic principal component analyzers, Neural Compu- tation, 11, 443–482.
Tipping ME and Bishop CM (1999b). Probabilistic principal component analysis, Journal of the Royal Statistical Society, Series B (Statistical Methodology), 61, 611–622.
Vichi M and Kiers HAL (2001). Factorial K-means analysis for two-way data, Computational Statistics and Data Analysis, 37, 49–64.
Received July 28, 2021; Revised September 24, 2021; Accepted September 25, 2021
확률적 reduced K-means 군집분석
이승훈a,송주원1, a
a고려대학교 통계학과
요 약
라벨 없이 진행되는 비지도 학습 중 하나인 군집분석은 자료에 어떤 그룹이 내포되어 있는지 사전 지식 이 없을 경우에 군집을 발굴하고, 군집 간의 특성 차이와 군집 안에서의 유사성을 분석하고자 할 때 유용한 방법이다. 기본적인 군집분석 중 하나인 K-means 방법은 변수의 개수가 많아질 때 잘 동작하지 않을 수 있 으며, 군집에 대한 해석도 쉽지 않은 문제가 있다. 따라서 고차원 자료의 경우 주성분 분석과 같은 차원 축소 방법을 사용하여 변수의 개수를 줄인 후에 K-means 군집분석을 행하는 Tandem 군집분석이 제안되었다. 하 지만 차원 축소 방법을 이용해서 찾아낸 축소 차원이 반드시 군집에 대한 구조를 잘 반영할 것이라는 보장은 없다. 특히 군집의 구조와는 상관없는 변수들의 분산 또는 공분산이 클 때, 주성분 분석을 통한 차원 축소는 오히려 군집의 구조를 가릴 수 있다. 이에 따라 군집분석과 차원 축소를 동시에 진행하는 방법들이 제안되 어 왔다. 그 중에서도 본 연구에서는 De Soete와 Carroll (1994)이 제안한 방법론을 확률적인 모형으로 바꿔 군집분석을 진행하는 확률적 reduced K-means를 제안한다. 모의실험 결과 차원 축소를 배제한 군집분석과 Tandem 군집분석보다 더 좋은 군집을 형성함을 알 수 있었고 군집 당 표본 크기에 비해 변수의 개수가 많은 자료에서 기존의 비 확률적 reduced K-means 군집분석에 비해 우수한 성능을 확인했다. 보스턴 자료에서는 다른 군집분석 방법론보다 명확한 군집이 형성됨을 확인했다.
주요용어: 군집분석, 차원 축소, 비지도 학습, EM 알고리듬, 고차원
1교신저자: (02841) 서울특별시 성북구 안암로 145, 고려대학교 통계학과. E-mail: jsong@korea.ac.kr
