???? 1 - PDF Free Download

The Korean Journal of Applied Statistics (2012) 25(3), 471 483 DOI: http://dx.doi.org/10.5351/kjas.2012.25.3.471 A Variable Selection Procedure for K-Means Clustering Sung-Soo Kim 1 1 Department of Information Statistics, Korea National Open University (Received February 23, 2012; Revised March 29, 2012; Accepted April 18, 2012) Abstract One of the most important problems in cluster analysis is the selection of variables that truly define cluster structure, while eliminating noisy variables that mask such structure. Brusco and Cradit (2001) present VS-KM(variable-selection heuristic for K-means clustering) procedure for selecting true variables for K- means clustering based on adjusted Rand index. This procedure starts with the fixed number of clusters in K-means and adds variables sequentially based on an adjusted Rand index. This paper presents an updated procedure combining the VS-KM with the automated K-means procedure provided by Kim (2009). This automated variable selection procedure for K-means clustering calculates the cluster number and initial cluster center whenever new variable is added and adds a variable based on adjusted Rand index. Simulation result indicates that the proposed procedure is very effective at selecting true variables and at eliminating noisy variables. Implemented program using R can be obtained on the website http://faculty.knou.ac.kr/sskim/nvarkm.r and vnvarkm.r. Keywords: K-means clustering, variable selection, Mojena s stopping rule, VS-KM, HINoV, adjusted Rand index. 1. 서론 군집분석은데이터마이닝에서말하는자율학습 (un-supervised learning) 의대표적인방법중의하나로 군집을형성하는데있어서경험적인판단을상당히요구하고있는분석방법이다. 따라서군집분석을시 작할때변수선택에대한중요성에대해서는그리신경을쓰지않고진행되고있는것이사실이다. 즉 군집분석에이용되는변수들의선택에대해서는해당분야분석자의경험에전적으로의존하고있다고 해도과언이아니다. 더구나군집분석을하기위해실용적으로이용되고있는 SAS 나 SPSS 등의범용 통계패키지에서도군집분석에이용되는변수선택에대한옵션이없기때문에변수선택에대한중요성 이대부분간과되고있는실정이고, 군집분석을실행할때는가능한한얻을수있는많은변수들을이 용해서실행되고있다. 그러나군집분석에있어서는한두개의관계없는변수들이포함되는경우에도 내재된군집을밝히는데실패할수있다 (Milligan, 1980a, 1980b, 1989). 이와같이군집구조를왜 곡시키는변수를가면변수 (masking variable) 라고한다 (Fowlkes 와 Mallows, 1983). 가면변수를밝히 고가면변수의영향을줄이는방법으로는변수가중치방법 (variable weighting) 및변수선택 (variable selection) 방법이있다. 변수가중치방법은군집구조를밝히는상대적인중요성을고려하여변수들 This research was supported by Korea National Open University Research Fund in 2009. 1 Prefessor, Department of Information Statistics, Korea National Open University, Seoul 110-791, Korea. E-mail: sskim@knou.ac.kr

472 Sung-Soo Kim 의가중치를다르게주는방법이며, 변수선택방법은군집분석에유용한변수만을선택하는방법이다. 변수가중치방법으로는계층적군집분석방법에이용된가중치방법 (De Soete, 1986), 비계층적방법인 K-평균군집방법에적용된 SYNCLUS 방법 (DeSarbo 등, 1984) 등이있고, 변수선택방법으로는 Fowlkes 등 (1987, 1988) 가다변량분산분석의분리기준을이용하여제안한앞으로부터의변수선택방법, Carmone 등 (1999) 의 HINoV(heuristic identification of noisy variables) 방법, Brusco와 Cradit (2001) 가 HINoV 방법을수정하여제안한 VS-KM(variable-selection heuristic for K-means clustering) 방법등이있다. 이러한방법들은다양한연구들을통해서비교검토되었는데 (Miligan, 1989; Gnanadesikan 등, 1995; Steinley와 Brusco, 2008), 특히 Gnanadesikan 등 (1995) 은변수가중치방법에비해서변수선택방법의효과가더좋다는사실을언급하였다. 실제로변수선택방법은군집분석을위해유의하지않은변수들에대하여데이터수집에대한부담을덜수있게해주고, 또한가중변수에대한의미를해석하는어려움을덜어주는장점을가지고있다. 변수선택방법중에서 Carmone 등 (1999) 이제안한 HINoV 방법은 Hubert과 Arabie (1985) 의수정 Rand 지수 (Rand, 1971) 를이용하여 K-평균군집에서이용되는변수선택방법을다루었고, Brusco와 Cradit (2001) 이제안한 VS- KM 방법은 HINoV 방법을개선한방법으로 K-평균군집분석에서의변수선택방법을다루고있다. 최근에들어서군집분석의변수선택방법은모형기반군집분석에서활발한연구가진행되고있는데, 이를위해서는 Raftery와 Dean (2006), Kim (2011) 등을참조하기바란다. 본소고에서는 K-평균군집분석에서변수선택방법을다루고자한다. K-평균군집분석은잘알려진바와같이대량자료의군집분석에널리이용되는방법으로고객분류, 행동과학, 심리분류등에널리이용된다. 특히대량자료의구조를파악하기위한데이터마이닝의방법으로도널리이용되고있다. 그러나 K-평균군집분석절차에서가장큰문제점은군집의수 K를어떻게정하느냐와각군집의초기중심을어떻게구하느냐하는문제이다. 여기에덧붙여변수선택의문제까지포함된다면 K-평균군집분석의절차는매우어려워질수있을것이다. 본논문은이러한 K-평균군집분석의절차와변수선택의절차가일련적인과정으로자동적으로이루어질수있도록하는문제를다루고있다. 최근에제안된 Kim (2009) 의자동화 K-평균군집분석절차는군집의수를정하고, 초기중심을구하는일련의과정이자동적으로, 연속적으로이루어지도록되어있다. 또한데이터의수가많은대량의자료의경우에도효율적으로작동될수있도록구성되어있다. 따라서 K-평균군집분석의자동화절차에변수선택과정이같이연결되어이루어진다면탐색적인방법으로서의 K-평균군집분석의활용이매우효과적으로이루어질수있을것이다. 본소고에서는 2장에서 K-평균군집분석의변수선택방법으로서 HINoV 방법및이를개선한 VS-KM 방법을소개하고, 3장에서자동화 K-평균절차에 VS-KM 방법을연결하여변수를선택하는방법을제안하고, 4장에서 R을이용하여구현한결과및시뮬레이션결과를보이고자한다. 2. K-평균군집변수선택방법 2.1. HINoV 방법 Carmone 등 (1999) 은군집분석의재현성에근거하여군집분석에포함될변수선택방법으로서 HI- NoV(heuristic identification of noisy variables) 방법을제안하였다. 이방법은각각의변수들을이용하여 K-평균군집을구성한다음에재현성을측정하기위한측도로서 Hubert와 Arabie (1985) 의수정 Rand 지수 (Rand, 1971) 를이용하여변수를선택하고, 선택된변수들을이용하여 K-평균군집분석을시행하는절차로이루어져있다. 이방법은각각의변수에대한수정 Rand 지수의합을 TOPR j 라할때, 이값이상대적으로큰변수들을선택하는절차로구성되어있다.

A Variable Selection Procedure for K-Means Clustering 473 HINoV 절차는한번의수행으로군집분석에이용될변수들을모두선택하는절차로서구현하기가매우간단하고, 효율적이나다음과같은제약점을가지고있다. 첫째로 HINoV 방법은 TOPR j 값의스크리그림을이용하기때문에분석자에따라주관적으로흐르기쉽고, 둘째로참변수 (true variables) 간의수정 Rand 지수는크고반면에가면변수간 ( 또는가면변수와참변수간 ) 의수정 Rand 지수는작다는가정을전제로한다. 여기서가면변수간의상관관계가매우큰경우에는각각의변수들을이용한군집결과는거의유사한구조를따를것이므로이들변수간의수정 Rand 지수는클것이고, 따라서잘못된변수들이포함될경우가많아질수있는단점을가지고있다. 2.2. VS-KM 방법 Brusco 와 Cradit (2001) 은 HINoV 방법의단점을보완하고, Fowlkes 등 (1988) 이제안한앞으로부터의 선택방법을가미하여 K- 평균군집분석을위한변수선택방법인 VS-KM(variable-selection heuristic for K-means clustering) 방법을제안하였다. 이방법도기본적으로수정 Rand 지수를이용하고있 다. 예를들어 3 개의변수가선택되어있다고하자. 이경우에선택된 3 개의변수를이용한군집과다 른 4 번째변수만을이용하여분류된군집간의수정 Rand 지수를계산하여이값이큰경우에는 4 번째 변수를포함시키고, 반대로이값이작으면포함시키지않는방법이다. 또한이방법에서는 Fowlkes 등 (1988) 이변수선택방법에이용했던군집간제곱합에대한총제곱합의비율을이용한다. 구체적인절차 는다음과같다. M = 개체의수, (i = 1, 2,..., M) D = 변수수, (j = 1, 2,..., D), D = D 1 + D 2 D 1 = 참변수 (true variable) 의개수 D 2 = 가면변수 (masking variable) 의개수 X = M D 관측값행렬, x ij = i 개체의 j 변수의관측값 C = 군집의수, (c = 1, 2,..., C) p j = 변수 j를이용한소속을나타내는 1 M 행벡터, p + ji = 개체 i 가속하는군집 R = D D 수정 Rand 지수, (r jk = r kj ): 소속군집 p j 와 p k 의수정 Rand 지수, S = 선택된변수군 j = 1,..., D 1, k = j + 1,..., D U = 선택되지않은변수군, S U = {1, 2,..., D}, S U = {ϕ} w jk = 변수 (j, k) 를이용한소속군집을나타내는 (1 M) 행벡터, j = 1,..., D 1, k = j + 1,..., D w jki = 개체 i 의소속군집 Q = 분류된군집 w jk 에대하여총제곱합에대한군집간제곱합비율, q jk = q kj, j = 1,..., D 1, k = j + 1,..., D T = 처음두변수쌍을선택하기위한기준값

474 Sung-Soo Kim y = 선택변수군 j S 을이용하여분류된 1 M 행벡터, y i: i 번째개체의소속군집 G i = 두분류 p j 와 y의수정 Rand 지수, j = 1,..., D G min = 변수선택을위한 G j 의최소허용값 G jac = 다음번변수선택을위해 G j 에곱하는요인값 단계 0: 초기화한다. y = 0; p j = 0, j = 1,..., D w jk = 0, j = 1,..., D 1, k = j + 1,..., D, S = {ϕ}, U = {1, 2, 3,..., D} 단계 1: 각각의변수를이용하여고정된군집수 C에대한분류를수행하고 p j (j = 1,..., D) 를구한 다. 단계 2: 두분류군 p j,p p k (j = 1,..., D 1, k = j + 1,..., D) 의 D(D 1)/2 쌍에대한수정 Rand 지수를계산한다. 단계 3: 변수 (j, k) 를이용하여고정된군집수 C에대한분류를수행하고소속군집 w jk 를구한후, 분류된군집 w jk 에대하여총제곱합에대한군집간제곱합비율인 q jk 를계산한다. (j = 1,..., D 1, k = j + 1,..., D) 단계 4: Max j,k (r jk ) T 이면 δ = Max j,k (q jk r jk T ), 아니면 δ = Max j,k (q jk ). q j k = δ인두변 수 (j, k ) 를선택하고, η = r j,k, S = S {j, k }, U = U {j, k } 으로한다. 단계 5: 선택된변수들 j S 를이용하여고정된군집수 C 에대한분류를수행하고, 군집결과인 y 를 얻는다. 단계 6: 선택되지않은변수들에대한분류결과인 p j 와기존의선택된변수들의분류결과인 y와의수정 Rand 지수 G j 를계산한다. 단계 7: λ = Max j U (G j), λ < G min 이거나 λ < η G jac 이면다음단계 8 로간다. 아니면최대값을 갖는변수 j 을택하여, G j = λ, η = λ 로하고, S = S {j }, U = U {j } 로한다. U = ϕ 이 면단계 8 로가고, 아니면단계 5 로간다. 단계 8: 선택된변수 S 를이용하여 K- 평균군집분석을수행한다. VS-KM 절차는 HINoV 절차의가장큰단점인상관관계가큰두가면변수의사전선택을방지하기위 해군집효과를나타내는측도인군집간제곱합비율을이용하고있다. 또한 HINoV 절차는한번의수 행으로군집분석에이용될변수들을모두선택하는반면에 VS-KM 절차는앞으로부터의변수선택방법 을사용하여추가해나가므로써군집분석에유용한모든변수들을선택할가능성을높여주고있다. VS- KM 절차에서는처음에선택되는두변수가매우중요한역할을한다. 처음선택되는두쌍의변수군과 동일한군집형태를지니는변수부터차례로더해나가기때문이다. VS-KM 절차에서는군집효과가떨 어지지만상관관계가큰두가면변수의초기선택을방지하기위하여단계 3 에서가능한모든두쌍에 대하여총제곱합에대한군집간제곱합의비율을계산하고있다. 그러나기본적으로이용되는측도가 수정 Rand 지수이기때문에모든가능한두쌍에대하여이를계산할필요는없고, 수정 Rand 지수가 큰상위몇쌍을고르고, 이에대한제곱합의비율을고려하게된다면계산량이많이줄어들게된다.

A Variable Selection Procedure for K-Means Clustering 475 VS-KM 방법은 HINoV 절차에비해여러가지장점을가지고있지만, 이방법에서도 K-평균군집방법이가지는근본적인문제점, 즉몇개의군집으로구성되어있고, 또한초기군집중심에대한문제가여전히남아있는것이사실이다. 군집분석에서적정군집수는선택된변수에따라달라질수있다. VS-KM 방법에서는초기부터고정된군집수를이용하여 K-평균군집분석을수행하고변수를더해나가는과정을택하기때문에선택된변수에따라적정군집수가달라질수있는문제를간과하고있다. 따라서 K-평균군집분석에있어서군집수를고정하고변수선택과정을진행하는것보다는변수선택과정을군집수의결정과동시에연계하여진행하는것이바람직하다고할수있다. 3. 자동화 K-평균군집과 VS-KM 방법의연계 K-평균군집분석은데이터의수가많은경우에도효율적으로활용되고있지만, 초기군집수를사전에정해야하고, 또한초기군집중심에따라서군집결정이달라질수있는문제를안고있다. 따라서 K- 평균군집분석을행할때는군집수를여러개로바꾸어가면서행한후에군집결과를비교하여선택하기도하고, 군집중심에있어서도사전정보를이용하거나, 계층적군집분석의결과를이용하거나또는초기중심을임의로선택하여이용하기도한다 (Everitt 등, 2001). K-평균군집분석이가진이러한어려움을줄이기위해최근에제안된절차로는 Kim (2009) 의자동화 K-평균군집절차를들수있다. 이절차는 K-평균군집분석에초기값으로제공되어야하는군집수및군집중심이자동으로계산되고, 이를이용하여 K-평균군집분석이수행되도록구성되어있다. Kim (2009) 의자동화 K-평균군집절차는대량데이터의경우에도효율적으로수행될수있도록일부표본을랜덤추출하는과정을활용하고있다. 대량데이터를고려한 Kim (2009) 의자동화 K-평균군집분석절차는다음과같다. < 자동화 K-평균군집분석절차 > i) 단순랜덤추출또는계통추출을통해서표본을추출한다. ii) 추출된표본에계층적군집분석을행한후, 군집수및초기군집중심을구한다. iii) 위 i), ii) 단계를반복수행한후, 가장많이나타나는군집수를초기군집수로하고, 각군집중심의평균을통하여초기군집중심을구한다. iv) iii) 단계에서결정된군집수및군집중심을초기값으로하여 K-평균군집분석을행한다. 자동화 K-평균군집분석절차에서데이터의수가적당한경우에는모든데이터를이용하여계층적군집분석을행하여군집수및초기군집중심을구한뒤에이를이용하여 K-평균군집분석을수행하도록되어있다. 이러한자동화 K-평균군집절차는기본적으로모든변수를활용하여처리하도록되어있다. 앞에서언급한바와같이가면변수가포함되어있는경우에모든변수를이용하여군집분석을행하는경우에는처음부터잘못된군집수를정하여시작할수있다. 따라서자동화 K-평균군집분석절차에변수선택절차가추가되는것이바람직하다. 자동화 K-평균군집분석절차에변수선택절차가가미되기위해서는선택된변수에따라적정군집수가달라지는절차를고려하여군집수를정하고, 나머지변수에대해서도여기서정해진군집수를이용하는것이필요하다. VS-KM 절차에서는처음부터고정된군집수로 K-평균군집분석을행하면서변수를하나씩더해나가는과정을택하고있으나선택된변수에따라적정군집수가달라지는문제를고려할필요가있다. VS-KM 절차를살펴보면처음두변수쌍을어떻게선택하느냐가매우중요하다는것을알수있다. 처음두변수쌍이선택된후, 여기에다른변수들이추가적으로더해지는과정으로이루어져있기때문이다. 따라서각각의개별변수를이용하여자동화 K-평균군집분석을수행한뒤, 각

476 Sung-Soo Kim 두변수별로수정 Rand 지수및총제곱에대한군집간제곱합비율을계산하여초기변수쌍을선택하고자동화 K-평균군집절차를수행하면서변수를더해나가는과정을반복하면될것이다. 변수선택과정을가미한자동화 K-평균군집분석절차는다음과같다. 단계 0: VS-KM 절차와같이초기화한다. y = 0; p j = 0, j = 1,..., D w jk = 0, j = 1,..., D 1, k = j + 1,..., D, S = {ϕ}, U = {1, 2, 3,..., D} 단계 1: 전개체또는추출된표본을이용하여각각의변수에대하여자동화 K-평균군집절차를시행한다. 단계 2: 가능한모든두변수쌍에대하여수정 Rand 지수를구한다. 단계 3: 수정 Rand 지수가큰상위변수군에대하여총제곱합에대한군집간제곱합비율을계산한다. 단계 4: 수정 Rand 지수가지정값 T 이상이면서총제곱합에대한군집간제곱합비율이큰두변수쌍을선택한다. 두변수 (j, k ) 가선택된경우, S = S {j, k }, U = U {j, k } 으로한다. 단계 5: 선택된변수들 j S을이용하여자동화 K-평균군집절차를수행하고, 군집결과인 y를얻는다. 단계 6: 선택되지않은변수들에대하여단계 5에서얻어진군집수로군집분석을실시하고분류결과인 p j 와기존의선택된변수들의분류결과인 y와의수정 Rand 지수 G j 를계산한다. 단계 7: 단계 6에서얻어진수정 Rand 지수중최대값 λ = Max j U (G j ) 를구한다. λ < G min 이거나, λ < η G jac 이면변수선택과정을끝내고단계 8로간다. 아니면최대값을갖는변수 j 을택하여 η = λ으로하고, S = S {j }, U = U {j } 로한다. U = ϕ이면단계 8로가고, 아니면단계 5로간다. 단계 8: 선택된변수 S를이용하여자동화 K-평균군집분석을수행한다. 4. R 구현및시뮬레이션결과 K-평균군집분석에서적정군집수를구하기위해활용된방법은 Ward (1963) 의계층군집분석을행한뒤, Mojena 등 (1980) 이제안한규칙을이용해군집수를정하고각군집중심을구하여 K-평균군집의초기값으로활용하는방법을이용하였다. 여기서데이터의수가대량인경우에는랜덤추출된표본을이용하여초기군집수와군집중심을구하는과정을이용하였다. 군집수를정하는방법은이외에도다양한방법이있으므로다른방법을사용하는것도좋을것이다. 이러한예로서는모형근거군집방법 (Banfield와 Raftery, 1993) 을행하고, BIC(Bayesian Information Criteria) 를이용하여군집수를정하는방법도한예라할수있다. 군집방법들의효과를살펴보기위해서는가상데이터가많이이용된다. 군집분석에이용되는가상데이터를만드는알고리즘으로는 Miligan (1985), Waller 등 (1999), Qui와 Joe (2006) 등의알고리즘을들수있다. 특히 Miligan (1985) 은실험계획법관점에서군집데이터를생산했는데, 예를들어군집수, 변수수, 군집크기, 이상치, 잡음 (noisy) 변수, 측정오류등을고려하여군집데이터를만드는알고리즘을제안하였다. Qui와 Joe (2006) 는군집간의이격도 (degree of separation) 개념을도입하여 Miligan의알고리즘을개선하였고, 특히 R 패키지 clustergeneration 을제공하여다양한군집데이터를생산할수있게하였다.

A Variable Selection Procedure for K-Means Clustering 477 Figure 4.1. Running R program 본소고에서는제안된자동화변수선택방법의효과를살펴보기위하여 Qui와 Joe (2006) 의다음과같은 3가지요인을고려하여가상군집데이터 27(3 3 3) 개의데이터셋을만들어자동화 K-평균군집방법에서제안된변수선택방법의효과를살펴보았다. 데이터수는 400 1000개로하였다. 1 군집수 C = 3, 4, 5. 2 군집이격도 ( 이격도 = 0.01은두군집이 N(0, 1) 과 N(0, A) 에서 A = 4의분포에서생성된가까운군집을의미하며, 이격도 = 0.21은 A = 6에서생성된분리된군집, 이격도 = 0.34는 A = 8에서생성된잘분리된군집을나타낸다. 본실험에서는잘분리된군집에서이격도 = 0.40을시용하였다.) Separation = 0.01, 0.21, 0.40. 3 변수수 D = 6(2), 8(3), 10(4); ( ) 안은잡음 (noisy) 변수수임. Figure 4.1은 R프로그램 (http://faculty.knou.ac.kr/sskim/nvarkm.r)( 대량자료의경우에는 R 프로그램 http://faculty.knou.ac.kr/sskim/vnvarkm.r을이용하기바란다 ) 을실행한화면이다. 실행순서는다음과같다. 1 데이터파일입력 2 변수표준화여부 3 표본추출여부 4 군집수를정하기위한 Mojena k값입력 Figure 4.1의실행절차에서는표준화절차로서 0 1 변환절차를택하고있고, 케이스선택은단순임의표본추출방법으로 50% 를택하고, Mojena k값은 1.5를입력하는과정을보여주고있다. 대량자료의경우에는표본추출률을 10% 이하로하기바란다. Figure 4.2는변수선택절차가가미된자동화 K-평균군집분석결과를단계별로보여주고있다. 먼저단계 1에서는각개별변수들을이용한 K-평균군집수를보여주고있다. 단계 2에서는수정 Rand 지수가가장큰 5개의변수쌍을차례대로보여주고있고, 단계 3에서는단계2에서선택된다섯개의변

478 Sung-Soo Kim Figure 4.2. Process results of variable selection for K-means clustering 수쌍에대한총제곱합에대한군집간제곱합비율을보여주고있다. 이결과에서보면변수 (4, 1) 쌍이가장큰수정 Rand 지수값을갖는반면에변수 (4, 3) 쌍이총제곱합에대한군집간제곱합비율이가장크다는것을보여주고있다. 수정 Rand 지수가일정값이상이면서총제곱합에대한군집간제곱합비율이가장큰두변수를기준으로선택할때, 처음으로선택되는두변수군은 (4, 3) 이고, K-평균군집을한결과군집수는 6개가된다. 다음으로변수 6의수정 Rand 지수값이지정된기준값 ( 여기서는단계 7에서의최소기준값을 0.05로함 ) 보다크므로선택된변수군에합해진다. 이제변수 (4, 3, 6) 을이용한 K-평균군집을한결과군집수는 4개가되고, 나머지변수군중에서변수 1이더해지는것을알수있다. 마지막으로변수 5의경우에는수정 Rand 지수값이 0.007로서기준값 0.05보다작아지므로이단계에서변수를선택하는절차가끝나게된다. 따라서 K-평균군집변수로선택되는최종변수는 (4, 3, 6, 1) 이고, K-평균군집수는 3개로변하고, 잡음변수는 (2, 5) 가됨을보여준다. 이결과에서흥미있는사실은선택되는변수군에따라 K-평균적정군집수가달라지는것을알수있다. 즉, 변수개별로할때는군집수가각변수별로 (5, 5, 6, 3, 5, 4) 개에서변수 (4, 3) 이이용되는경우에는 6개로결정이되고, 변수 (4, 3, 6) 에서는군집수가 4개, 최종선택되는변수 (4, 3, 6, 1) 에서는군집수가 3개로결정되는것을알수있다. 따라서 K-평균군집분석의가장큰어려움인군집수를정해야하는문제도변수를

A Variable Selection Procedure for K-Means Clustering 479 Figure 4.3. Simulation results of clustering data 선택하는절차와더불어자동으로해결된다는것을알수있다. 물론이러한결과는데이터를랜덤으로추출하는과정을거치기때문에수행할때마다결과가달라지므로, 선택되는변수의순서가중요도를나타내지는않는다는사실을유념하기바란다. Table 4.1은총 27개가상군집데이터를이용하여변수선택절차를거친 K-평균군집분석결과 (Figure 4.3 참조 ) 를정리한표이다. Table 4.1의데이터셋 cls 3s42 는군집수 = 3, 이격도 = 0.01을나타내고, 참변수수는 4개, 잡음변수는 2개를나타낸다. Figure 4.1의실행절차와같이표준화절차로서 0 1 변환절차 ( 이격도 = 0.01의경우에는이웃한군집이가까이있으므로원자료의구조를유지하기위해변환하지않은원자료를선택 ) 를택하고, 단순임의표본추출방법으로 50% 의케이스를임의로선택한데이터를이용하여 Ward 군집분석을행하여초기군집수와군집중심을구한후 K-평균군집분석을수행하였다. Ward 군집분석방법에서군집수를결정하기위한 Mojena 규칙에서는 k = 1.5( 이격도 = 0.01의경우에는 k = 2.5를사용 ) 를사용하였다. Mojena 규칙은군집수를정하기위한값이므로 1 2.5 범위내의값을사용하면된다. 변수선택절차에서는처음두변수쌍을얻기위한기준으로 T = 0을사용하여총제곱합에대한군집간제곱합비율이가장큰두변수를택하고, 단계 7에서변수

480 Sung-Soo Kim Table 4.1. Results of variable selection for K-means clustering(g min = 0.05, G jac = 0.5) 데이터셋 가상군집데이터 K-평균변수선택결과군집수이격도참변수잡음변수군집수선택된변수수정 Rand 지수 cls 3s42 3 0.01 (2, 3, 4, 6) (1, 5) 3 (3, 2, 6, 4) 0.8808 cls 3m42 3 0.21 (1, 3, 4, 6) (2, 5) 3 (4, 3, 6, 1) 0.9939 cls 3v42 3 0.40 (1, 2, 3, 6) (4, 5) 3 (3, 2, 6, 1) 1.0000 cls 3s53 3 0.01 (1, 2, 6, 7, 8) (3, 4, 5) 3 (6, 1, 8, 2) 0.9062 cls 3m53 3 0.21 (1, 2, 3, 4, 5) (6, 7, 8) 3 (2, 1, 5, 4) 1.0000 cls 3v53 3 0.40 (1, 5, 6, 7, 8) (2, 3, 4) 3 (5, 1, 6, 8, 7) 1.0000 cls 3s64 3 0.01 (1, 3, 6, 8, 9, 10) (2, 4, 5, 7) 3 (6, 1, 8, 10, 9, 3) 0.8157 cls 3m64 3 0.21 (2, 3, 4, 5, 7, 10) (1, 6, 8, 9) 3 (4, 2, 10, 7, 3) 0.9850 cls 3v64 3 0.40 (2, 3, 4, 5, 6, 10) (1, 7, 8, 9) 3 (4, 3, 2, 5, 10) 1.0000 cls 4s42 4 0.01 (2, 3, 4, 5) (1, 6) 4 (5, 2, 4, 3) 1.8568 cls 4m42 4 0.21 (2, 3, 5, 6) (1, 4) 4 (5, 2, 6, 3) 1.0000 cls 4v42 4 0.40 (1, 2, 3, 4) (5, 6) 4 (4, 1, 2, 3) 1.0000 cls 4s53 4 0.01 (3, 4, 5, 6, 7) (1, 2, 8) 4 (7, 6, 3, 4, 5) 0.7859 cls 4m53 4 0.21 (1, 5, 6, 7, 8) (2, 3, 4) 4 (5, 1, 7) 0.9943 cls 4v53 4 0.40 (2, 3, 5, 7, 8) (1, 4, 6) 4 (7, 5, 3, 2, 8) 1.0000 cls 4s64 4 0.01 (3, 5, 7, 8, 9, 10) (1, 2, 4, 6) 4 (9, 7, 10, 5, 3) 0.8597 cls 4m64 4 0.21 (1, 2, 3, 4, 5, 6) (7, 8, 9, 10) 4 (5, 4, 2, 6, 1, 3) 0.9951 cls 4v64 4 0.40 (1, 5, 6, 7, 8, 10) (2, 3, 4, 9) 4 (10, 6, 1, 5, 8, 7) 1.0000 cls 5s42 5 0.01 (1, 4, 5, 6) (2, 3) 5 (4, 1, 6, 5) 0.8478 cls 5m42 5 0.21 (1, 3, 4, 5) (2, 6) 5 (5, 4, 1, 3) 0.9585 cls 5v42 5 0.40 (2, 3, 4, 6) (1, 5) 5 (6, 3, 2, 4) 1.0000 cls 5s53 5 0.01 (1, 3, 4, 5, 6) (2, 7, 8) 5 (5, 4, 6, 1) 0.8628 cls 5m53 5 0.21 (1, 3, 5, 7, 8) (2, 4, 6) 5 (7, 3, 8, 5, 1) 0.9895 cls 5v53 5 0.40 (2, 5, 6, 7, 8) (1, 3, 4) 5 (8, 2, 5, 7, 6) 1.0000 cls 5s64 5 0.01 (1, 3, 5, 6, 8, 9) (2, 4, 7, 10) 5 (6, 1, 3, 8) 0.8522 cls 5m64 5 0.21 (1, 2, 4, 5, 6, 10) (3, 7, 8, 9) 5 (10, 6, 4, 2, 5, 1) 0.9927 cls 5v64 5 0.40 (1, 2, 4, 6, 7, 9) (3, 5, 8, 10) 5 (4, 1, 9, 6, 2, 7) 1.0000 주 ) : 참변수일부가포함되어있지않은경우 를추가적으로포함시키기위한기준으로는 G min = 0.05, G jac = 0.5를사용하였다. 두번째데이터셋 cls 3m42를예로들면, 군집수가 3이고, 군집간이격도 = 0.21, 참변수는 4개로서변수 (1, 3, 4, 6) 이고, 잡음변수는 2개로서변수 (2, 5) 로생성된가상군집데이터인데, K-평균변수선택결과에서보면선택된변수는 4개로 (4, 3, 6, 1) 은처음에선택된두변수는 (4, 3) 이고변수 6과변수 1이순서대로선택된것을나타낸다. 여기서 K-평균군집수결과는 3개이며, 원데이터와의수정 Rand 지수는 0.9939로가상데이터와변수선택절차를거친 K-평균군집분석과의결과가거의일치하는것을보여준다. Table 4.1의결과에서군집간이격도가 0.01인경우는가상으로생성된군집데이터의구조를유지하기위해서자료를변환하지않고원시자료를이용하여분석하였다. 이격도가 0.21, 0.40인경우에는 0 1 변환한자료를이용하여분석하였다. 이결과에서보면전체적으로참변수가잘선택된것을알수있다. 일부데이터셋에서참변수의일부가포함되지않고있는경우를알수있는데 ( 표시 ), 군집분석결과의일치성을나타내는수정 Rand 지수를보면모두값이크다는것을알수있어선택된변수를이용한 K-평균군집분석을한결과가좋음을확인할수있다. 특히군집간이격도가 0.21, 0.40인경우에는

A Variable Selection Procedure for K-Means Clustering 481 수정 Rand 지수값이모두 0.95 이상이어서선택된변수만을이용하여군집분석을한결과도매우뛰어남을알수있다. 또한가상데이터를이용한변수선택결과에서잡음변수는어느데이터셋에서도포함되어있지않다는것을알수있다. 이는선택된변수군에잡음변수가포함되는 Type II 오류가없다는것을보여주고있어변수선택절차가가미된자동화 K-평균군집분석이매우효용적임을알수있다. 변수를선택하기위한기준으로이용되는단계 7에서의기준값 G min, G jac 는경험적으로선택하면된다 (Brusco와 Cradit, 2001). 실제적으로기준을강화하여 G min = 0.03, G jac = 0.3을사용하는경우에도변수선택결과는 Table 4.1과거의유사한것을알수있다. Table 4.1의변수선택결과에서보면참변수의일부가선택되지못하는경우에도군집분석재현성결과가좋음을알수있고, 반면에잡음변수는어느데이터셋에도포함되는경우는하나도없음을알수있다. 이러한사실은 Miligan (1985) 및 Brusco와 Cradit (2001) 이언급한것처럼참변수의일부가포함되지못하는 Type I 오류인경우에는군집분석결과의재현성에문제가별로없는반면에, 잡음변수가포함되는 Type II 오류인경우심각한군집분석결과의오류가발생할수있다는사실을감안할때도제안된변수선택절차가매우효율적임을알수있다. 본실험결과는데이터수를 1000 이하로한경우이나데이터의수가큰대량자료인경우에는추출된표본만을이용하여군집분석을행하고, 수정 Rand 지수를구하여변수를선택하는과정으로압축할수있다. 대량자료변수선택프로그램 http://faculty.knou.ac.kr/sskim/vnvarkm.r(r에서메모리크기를알려면 memory.size, memory.limit 명령을참조하기바란다 ) 에서추출률을 5% 이하로하여도변수선택효과는매우뛰어남을알수있다. 5. 맺음말 K-평균군집분석을위한변수선택방법으로서 Brusco와 Cradit (2001) 이제안한 VS-KM 방법은미리고정된군집수를정하고변수를선택하는과정을거치게된다. 잘알려진바와같이 K-평균군집분석을행하는데있어서가장큰어려움은군집수를결정하는문제와초기군집중심을결정하는문제라고할수있다. Figure 4.2의분석절차에서나타내는바와같이선택된변수에따라적정군집수가달라질수있는문제를안고있기때문에사전에군집수를고정하고변수선택을실행하는 VS-KM 방법은효율성이떨어진다고할수있다. Brusco와 Cradit (2001) 는 K-평균군집분석을위한초기군집수를구하기위하여먼저일부추출된표본을이용하여 Ward의계층적군집분석을행하고이를이용하여고정된군집수를정하고변수선택절차를수행하였다. 본연구에서는이러한방법을개선하여변수선택절차를 Kim (2009) 이제안한자동화 K-평균군집분석절차와연계한방법을제안하고있다. 자동화 K-평균군집분석절차를위하여본소고에서사용한방법은대량자료의경우에도효율적으로이용될수있도록표본추출을통하여얻은데이터를이용하여 Ward 군집분석을행하고 Mojena의규칙을이용하는방법을사용하였으나, 군집수를정하는방법으로는이외에도모형근거군집분석을행한뒤에 BIC(Bayesian Information Criteria) 를이용하여군집수를정하는방법 (Banfield와 Raftery, 1993; Fraley와 Raftery, 1998) 이나다른다양한방법을이용할수도있을것이다. 또는그래프를이용하는방법으로서 Kim 등 (2000) 이활용한방법도응용할수있을것이다. 군집수를정하는방법은어느방법이절대적으로가장좋은결과를나타낸다고할수는없다. 왜냐하면데이터의구조에따라우선적으로선호되는방법들이있을것이기때문이다. 이러한의미에서군집수를정하기위한다양한방법들을비교하고, 데이터의구조에따른시뮬레이션결과들을보이는것도좋은연구가될것이다. 또한대량자료의경우에다양한군집구조를가지는데이터를생성하여추출률등을변수로한시뮬레이션결과를보이

482 Sung-Soo Kim 는것도좋은응용연구가될것이다. 본연구에서는 K-평균군집분석에서변수를선택하는알고리즘을구현하는데있어서특이값 (outlier) 검출에대한문제는고려하지않았다. 실제로 K-평균군집분석을행하는데있어서특이값검출에대한연구자체도완성되지않은과제이기때문에이러한방법들을연구하고, 변수선택과특이값검출을동시에연계한 K-평균군집분석을실행하는방법도도전해볼만한좋은과제라고할수있을것이다. 이러한절차들은본연구자가제공하는 R 프로그램 (http://faculty.knou.ac.kr/sskim/nvarkm.r; 대량자료의경우 vnvarkm.r) 에첨가구축하여사용하길바란다. 변수선택과연계한자동화 K-평균군집분석프로그램에서발견되는오류는전적으로저자의책임이며, 누구나이를수정하고보완하여활용하기를바란다. 또한이연구를계기로더나은변수선택방법이연구, 보완되고특이점검출기능이추가된자동화 K-평균군집방법및 R 프로그램이개발되기를기대해본다. References Banfield, J. D. and Raftery, A. E. (1993). Model-based Gaussian and non-gaussian clustering, Biometrics, 49, 803 821. Brusco, M. J. and Cradit, J. D. (2001). A variable-selection heuristic for K-means clustering, Psychometrika, 66, 249 270. Carmone, F. J., Kara, A. and Maxwell, S. (1999). HINoV; A new model to improve market segmentation by identifying noisy variables, Journal of Marketing Research, 36, 501 509. De Sarbo, W. S., Carroll, J. D., Clark, L. A. and Green, P. E. (1984). Synthesized clustering: A method for amalgamating alternative clustering bases with different weighting of variables, Psychometrika, 49, 57 78. De Soete, G. (1986). Optimal variable weighting for ultrametric and additive tree clustering, Quality and Quantity, 20, 169 180. Everitt, B. S., Landau, S. and Leese, M. (2001). Cluster Analysis, Arnold. Fowlkes, E. B., Gnanadesikan, R. and Kettenring, J. R. (1987). Variable selection in clustering other contexts, In C.L. Mallows(Ed.), Design, Data and Analysis, 13 34. Fowlkes, E. B., Gnanadesikan, R. and Kettenring, J. R. (1988). Variable selection in clustering, Journal of Classification, 5, 205 228. Fowlkes, E. B. and Mallows, C. L. (1983). A method for comparing two hierarchical clusterings (with comments and rejoinder), Journal of the American Statistical Association, 78, 553 584. Fraley, C. and Raftery, A. E. (1998). How many clusters? Which clustering methods? Answers via modelbased cluster analysis, Computer Journal, 41, 578 588. Gnanadesikan, R., Kettenring, J. R. and Tsao, S. L. (1995). Weighting and selection of variables for cluster analysis, Journal of Classification, 7, 271 285. Hubert, L. and Arabie, P. (1985). Comparing partitions, Journal of Classification, 2, 193 218. Kim, S. (1999). Interactive visualization of K-means and Hierarchical clusters, The Journal of Data Science and Classification, 3, 13 27. Kim, S. (2009). Automated K-means clustering and R implementation, The Korean Journal of Applied Statistics, 22, 723 733. Kim, S.-G. (2011). Variable selection in normal mixture model based clustering under heteroscedasticity, The Korean Journal of Applied Statistics, 24, 1213 1224. Kim, S., Kwon, S. and Cook, D. (2000). Interactive visualization of hierarchical clusters using MDS and MST, Metrika, 51, 39 51. Milligan, G. W. (1980a). An examination of six types of the effects of error perturbation on fifteen clustering algorithms, Psychometrika, 45, 325 342. Milligan, G. W. (1980b). An algorithm for generating artificial test clusters, Psychometrika, 50, 123 127. Milligan, G. W. (1989). A validation study of a variable-weighting algorithm for cluster analysis, Journal of Classification, 6, 53 71.

A Variable Selection Procedure for K-Means Clustering 483 Milligan, G. and Cooper, M. C. (1985). An examination of procedures for determining the number of clusters in a data set, Psychometrika, 50, 159 179. Mojena, R. (1977). Hierarchical grouping methods and stopping rules: An evaluation, The Computer Journal, 20, 259 363. Mojena, R., Wishart, D. and Andrews, G. B. (1980). Stopping rules for Wards clustering method, COMP- STAT,, 426 432. Raftery, A. E. and Dean, N. (2006). Variable selection for model-based clustering, Journal of the American Statistical Assocation, 101, 168 178. Rand, W. M. (1971). Objective criteria for the evaluation of clustering methods, Journal of the American Statistical Assocation, 66, 846 850. Qui, W.-L. and Joe, H. (2006). Generation of random clusters with specified degree of separation, Journal of Classification, 23, 315 334. Steinley, D. and Brusco, M. J. (2008). A new variable weighting and selection procedure for K-means cluster analysis, Multivariate Behavioral Research, 43, 77 108. Waller, N. G., Underhill, J. M. and Kaiser, H. (1999). A method for generating simulated plasmodes and artificial test clusters with user-defined shape, size, and orientation, Multivariate Behavioral Research, 34, 123 142. Ward, J. H. (1963). Hierarchical grouping to optimise an objective function, Journal of American Statistical Association, 58, 236 244.