정부 3.0이라는 새로운 정부운영 계획과 함께 다양한 공공정보를 민간이 활용할 수 있게 되었으며, 특히 서울은 이러한 행정정보 공개 및 활용을 선도하고 있다. 공개된 행정정보를 통해 각 지역을 특징짓는 행정요소를 발견할 경우, 각종 행정정책을 위한 의사결정 수단에 반영할 수 있을 뿐만 아니라 특정 지역의 고객 특성을 파악하여 특화된 서비스나 상품을 판매하는 마케팅 수단으로도 사용할 수 있을 것으로 사료된다. 하지만, 방대한 양의 행정자료로부터 각 군집의 특성을 명확히 구분할 수 있는 최적의 조합을 찾는 과정은 조합최적화 문제로서 상당한 연산량을 요구한다. 본 연구에서는 서울시에서 제공하는 다차원 행정자료로부터 서울시를 대표하는 문화 산업의 중심인 서초구, 강남구, 송파구 등의 강남 3구를 다른 지역과 효과적으로 구분하는 행정요인를 찾고자 하였다. 방대한 양의 행정정보로부터 두 군집간의 차이점을 극대화하는 요인을 선별하기 위한 최적화 방법으로 유전자 알고리즘을 이용하였으며, 군집간 차이를 계산하는 척도로는 Dunn 지수를 이용하였다. 또한 유전자 알고리즘의 연산속도의 향상을 위해 Microsoft Azure에서 제공하는 cloud computing을 이용한 분산처리를 수행하였다. 자료로는 통계청으로 부터 취득한 총 718개의 행정자료를 이용하였으며, 그 중 28개가 최적 변수로 선정되었다. 검증을 위해 선정된 28개의 변수를 입력값으로 Ward의 최소분산법 및 K-means 알고리즘을 통한 군집화를 수행한 결과 두 경우 모두 강남 3구가 다른 지역으로부터 효과적으로 분류됨을 확인하였다.
정부 3.0이라는 새로운 정부운영 계획과 함께 다양한 공공정보를 민간이 활용할 수 있게 되었으며, 특히 서울은 이러한 행정정보 공개 및 활용을 선도하고 있다. 공개된 행정정보를 통해 각 지역을 특징짓는 행정요소를 발견할 경우, 각종 행정정책을 위한 의사결정 수단에 반영할 수 있을 뿐만 아니라 특정 지역의 고객 특성을 파악하여 특화된 서비스나 상품을 판매하는 마케팅 수단으로도 사용할 수 있을 것으로 사료된다. 하지만, 방대한 양의 행정자료로부터 각 군집의 특성을 명확히 구분할 수 있는 최적의 조합을 찾는 과정은 조합최적화 문제로서 상당한 연산량을 요구한다. 본 연구에서는 서울시에서 제공하는 다차원 행정자료로부터 서울시를 대표하는 문화 산업의 중심인 서초구, 강남구, 송파구 등의 강남 3구를 다른 지역과 효과적으로 구분하는 행정요인를 찾고자 하였다. 방대한 양의 행정정보로부터 두 군집간의 차이점을 극대화하는 요인을 선별하기 위한 최적화 방법으로 유전자 알고리즘을 이용하였으며, 군집간 차이를 계산하는 척도로는 Dunn 지수를 이용하였다. 또한 유전자 알고리즘의 연산속도의 향상을 위해 Microsoft Azure에서 제공하는 cloud computing을 이용한 분산처리를 수행하였다. 자료로는 통계청으로 부터 취득한 총 718개의 행정자료를 이용하였으며, 그 중 28개가 최적 변수로 선정되었다. 검증을 위해 선정된 28개의 변수를 입력값으로 Ward의 최소분산법 및 K-means 알고리즘을 통한 군집화를 수행한 결과 두 경우 모두 강남 3구가 다른 지역으로부터 효과적으로 분류됨을 확인하였다.
Korean government proposed a new initiative 'government 3.0' with which the administration will open its dataset to the public before requests. City of Seoul is the front runner in disclosure of government data. If we know what kind of attributes are governing factors for any given segmentation, the...
Korean government proposed a new initiative 'government 3.0' with which the administration will open its dataset to the public before requests. City of Seoul is the front runner in disclosure of government data. If we know what kind of attributes are governing factors for any given segmentation, these outcomes can be applied to real world problems of marketing and business strategy, and administrative decision makings. However, with respect to city of Seoul, selection of optimal variables from the open dataset up to several thousands of attributes would require a humongous amount of computation time because it might require a combinatorial optimization while maximizing dissimilarity measures between clusters. In this study, we acquired 718 attribute dataset from Statistics Korea and conducted an analysis to select the most suitable variables, which differentiate Gangnam from other districts, using the Genetic algorithm and Dunn's index. Also, we utilized the Microsoft Azure cloud computing system to speed up the process time. As the result, the optimal 28 variables were finally selected, and the validation result showed that those 28 variables effectively group the Gangnam from other districts using the Ward's minimum variance and K-means algorithm.
Korean government proposed a new initiative 'government 3.0' with which the administration will open its dataset to the public before requests. City of Seoul is the front runner in disclosure of government data. If we know what kind of attributes are governing factors for any given segmentation, these outcomes can be applied to real world problems of marketing and business strategy, and administrative decision makings. However, with respect to city of Seoul, selection of optimal variables from the open dataset up to several thousands of attributes would require a humongous amount of computation time because it might require a combinatorial optimization while maximizing dissimilarity measures between clusters. In this study, we acquired 718 attribute dataset from Statistics Korea and conducted an analysis to select the most suitable variables, which differentiate Gangnam from other districts, using the Genetic algorithm and Dunn's index. Also, we utilized the Microsoft Azure cloud computing system to speed up the process time. As the result, the optimal 28 variables were finally selected, and the validation result showed that those 28 variables effectively group the Gangnam from other districts using the Ward's minimum variance and K-means algorithm.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 연구는 Dunn 지수를 적합성 평가 함수로 이용한 유전자 알고리즘을 통해 강남 3구(와 나머지 구들을 구별 짓는 속성을 찾아내고자 하였다. 그 결과, 총 718개의 통계자료 중에서 Dunn 지수와 유전자 알고리즘을 통해 강남 3구를 구별 짓는 속성값은 총 28개로 결정되었으며, 그 결과는 Table 3과 같이 나타났다.
본 연구에서는 서울시를 대상으로 강남 3구가 이미군집화되어 있다는 가정 하에 다른 구와 차이점을 나타내는 대표적인 요인이 무엇인지를 찾고자 하였다. 자료로는 통계청에서 제공한 718종류의 행정정보를 이용하였으며, 방대한 양의 행정정보로부터 강남 3구를 특징짓는 요인을 효과적으로 선별하기 위해 유전자 알고리즘을 이용한 방법을 제시하였으며, 군집간 차이를 분석하여 적합성을 평가하기 위한 척도로는 Dunn 지수(Dunn’s index)를 사용하였다.
제안 방법
강남 3구와 다른 구를 구별짓는 속성정보를 찾기 위하여 미리 강남 3구와 다른 구들이 2가지로 군집화가 되어있다고 가정하고 유전자 알고리즘의 적합도 함수인 Dunn 지수를 최대로 만드는 속성의 종류와 갯수를 찾는 방향으로 연구를 진행하였다. 우선, 유전자 알고리즘을 본 연구에서는 Dunn 지수를 최대로 만드는 속성의 차원을 모르는 상태이기 때문에 이에 대응 되는 염색체의 유전자 수를 1부터 718개로 증가시켜 가며, 각각의 경우에 대하여 유전자 알고리즘을 계산하였다.
자료로는 통계청에서 제공한 718종류의 행정정보를 이용하였으며, 방대한 양의 행정정보로부터 강남 3구를 특징짓는 요인을 효과적으로 선별하기 위해 유전자 알고리즘을 이용한 방법을 제시하였으며, 군집간 차이를 분석하여 적합성을 평가하기 위한 척도로는 Dunn 지수(Dunn’s index)를 사용하였다. 또한 유전자 알고리즘 연산에 소요되는 시간 소요를 효과적으로 줄이기 위해 Microsoft에서 제공하는 Azure cloud computing을 이용한 분산처리를 시도하였다. 아울러, 유전자 알고리즘으로 선별된 요인들이 실제로 강남 3구를 효과적으로 구별하는 지를 검증하기 위해 기존의 군집화 알고리즘인 Ward의 최소분산법(Ward`s Minimum Variance)과 K-means 알고리즘을 이용하였다.
우선, 유전자 알고리즘을 본 연구에서는 Dunn 지수를 최대로 만드는 속성의 차원을 모르는 상태이기 때문에 이에 대응 되는 염색체의 유전자 수를 1부터 718개로 증가시켜 가며, 각각의 경우에 대하여 유전자 알고리즘을 계산하였다. 만약 유전자 수가 1개일 경우와 718개일 경우는 각각 718번과 1번만의 전수 조사를 수행하고, 그 외의 경우는 사용하는 유전자의 개수(속성의 차원, d)에 따라 조합으로 계산되어(718Cd ) 연산량이 급격히 증가하므로 유전자 알고리즘을 통한 방법을 이용하였다. 유전자 알고리즘을 수행하기 위한 초기 염색체의 개수(population number)는 20, 교배 확률은 0.
강남 3구와 다른 구를 구별짓는 속성정보를 찾기 위하여 미리 강남 3구와 다른 구들이 2가지로 군집화가 되어있다고 가정하고 유전자 알고리즘의 적합도 함수인 Dunn 지수를 최대로 만드는 속성의 종류와 갯수를 찾는 방향으로 연구를 진행하였다. 우선, 유전자 알고리즘을 본 연구에서는 Dunn 지수를 최대로 만드는 속성의 차원을 모르는 상태이기 때문에 이에 대응 되는 염색체의 유전자 수를 1부터 718개로 증가시켜 가며, 각각의 경우에 대하여 유전자 알고리즘을 계산하였다. 만약 유전자 수가 1개일 경우와 718개일 경우는 각각 718번과 1번만의 전수 조사를 수행하고, 그 외의 경우는 사용하는 유전자의 개수(속성의 차원, d)에 따라 조합으로 계산되어(718Cd ) 연산량이 급격히 증가하므로 유전자 알고리즘을 통한 방법을 이용하였다.
이와 같이 변수가 증가할 때 그 연산량이 극단적으로 증가하는 경우를 조합최적화 문제라 하며, traveling salesman problem 등이 대표적인 사례이다 (Rademacher, 2005). 이러한 경우는 전수조사가 아닌 휴리스틱(heuristic) 기법을 통해 문제를 해결하며, 본 연구에서는 유전자 알고리즘을 이용해 문제 해결을 시도하였다.
대상 데이터
본 연구에서는 강남 3구를 군집화하기 위한 기초 자료로써 통계청에 존재하는 718가지 항목의 자료를 이용하였다. 다음의 Table 1은 통계청으로부터 취득한 자료들을 크게 9가지 항목으로 요약한 자료이며, 해당 자료는 국가통계포털(www.
데이터처리
그 결과, 총 718개의 통계자료 중에서 Dunn 지수와 유전자 알고리즘을 통해 강남 3구를 구별 짓는 속성값은 총 28개로 결정되었으며, 그 결과는 Table 3과 같이 나타났다. 또한 선별된 28개 속성을 이용하여 기존의 군집화 방법인 Ward 의 최소분산법과 K-means 알고리즘을 이용하여 군집을 형성할 경우 강남 3구와 나머지 구들이 성공적으로 분류되었음을 덴드로그램과 PSF 통계량 계산을 통해 알 수 있었다.
또한, 유전자 알고리즘과 Dunn 지수를 통해 선택된 28개의 속성에 대한 검증을 위해 기존에 군집화 방법 중 계층적 방법인 ‘Ward의 최소분산법’과 비계층적 방법인 ‘K-means Algorithms’의 결과를 비교하였다.
이론/모형
다수의 변수에서 강남 3구를 특징짓는 최적화된 변수를 선정하기 위해서는 변수의 종류와 개수를 바꾸어 가면서 군집간의 차이점을 최대화하기 위한 적합성 평가(cluster validity measure) 과정이 필요하다. 군집간 특징을 판단하는 대표적인 척도로 Silhouette 지수와 Dunn 지수 등이 사용되고 있으며 (Kim et al., 2012), 본 연구에서는 그 중에서도 Dunn 지수를 사용하였다.
또한 유전자 알고리즘 연산에 소요되는 시간 소요를 효과적으로 줄이기 위해 Microsoft에서 제공하는 Azure cloud computing을 이용한 분산처리를 시도하였다. 아울러, 유전자 알고리즘으로 선별된 요인들이 실제로 강남 3구를 효과적으로 구별하는 지를 검증하기 위해 기존의 군집화 알고리즘인 Ward의 최소분산법(Ward`s Minimum Variance)과 K-means 알고리즘을 이용하였다.
자료로는 통계청에서 제공한 718종류의 행정정보를 이용하였으며, 방대한 양의 행정정보로부터 강남 3구를 특징짓는 요인을 효과적으로 선별하기 위해 유전자 알고리즘을 이용한 방법을 제시하였으며, 군집간 차이를 분석하여 적합성을 평가하기 위한 척도로는 Dunn 지수(Dunn’s index)를 사용하였다.
한편, 본 연구에서는 연산 속도의 향상을 위해 Microsoft Azure cloud computing에 기반한 병렬처리 연산을 이용하였다(Microsoft Azure, 2014). 병렬 처리 연산에 이용한 컴퓨팅 환경은 Table 2와 같으며, 병렬 처리 전 연산 시간은 33.
성능/효과
Table 4는 Ward의 최소분산법과 K-means 방법을 통해 군집 분석을 수행한 결과를 나타내고 있다. SAS에서 통계량이 제공된 최대 5개부터 2개까지의 군집 분류 결과를 분석해 본 결과, Ward의 최소분산법 및 K-Means 알고리즘 모두 군집개수가 줄어 듬에 따라 PSF 지수가 지속적으로 증가하여 강남 3구와 다른 22개의 구를 두 군집으로 분류했을 때 최대 수치가 계산됐음을 확인할 수 있었으며, 이를 통해 유전자 알고리즘을 이용하여 선정된 속성값이 강남 3구를 다른 구들과 성공적으로 구별했음을 확인할 수 있었다.
덴드로그램은 군집형성에 대한 시각적 탐색 기능을 제공함으로써 군집의 개수를 정하는 데 좋은 참고가 될 수 있다. Ward의 최소분산법을 통해 28개 속성값이 최후의 2개로 군집화 된 결과를 보면, x축에서 강남 3구를 나타내는 서초구, 강남구, 송파구가 다른 구들과 분리된 것을 쉽게 확인할 수 있었다. K-means의 경우 별도의 그래픽을 제공하고 있진 않지만, K=2일 경우 군집결과에서 역시 강남 3구가 성공적으로 분류된 것을 확인할 수 있었다.
본 연구는 Dunn 지수를 적합성 평가 함수로 이용한 유전자 알고리즘을 통해 강남 3구(와 나머지 구들을 구별 짓는 속성을 찾아내고자 하였다. 그 결과, 총 718개의 통계자료 중에서 Dunn 지수와 유전자 알고리즘을 통해 강남 3구를 구별 짓는 속성값은 총 28개로 결정되었으며, 그 결과는 Table 3과 같이 나타났다. 또한 선별된 28개 속성을 이용하여 기존의 군집화 방법인 Ward 의 최소분산법과 K-means 알고리즘을 이용하여 군집을 형성할 경우 강남 3구와 나머지 구들이 성공적으로 분류되었음을 덴드로그램과 PSF 통계량 계산을 통해 알 수 있었다.
또한 본 연구에서 적합도 평가를 위해 사용한 Dunn 지수와 군집화 알고리즘인 Ward의 최소분산법 및 K-means 알고리즘 외에 보다 다양한 알고리즘 간의 비교·분석을 수행할 예정이다. 아울러 본 연구에서 효과적인 유전자 알고리즘 연산을 위해 사용한 클라우드 분산 컴퓨팅 방식은 MATLAB 기반의 for문 처리에만 사용하였으며, 사용한 cluster의 숫자에 비해 효율성은 떨어지는 결과를 나타내었다. 따라서 향후 프로그래밍 최적화를 통한 연산 속도 향상에 대한 연구를 병행할 예정이다.
8시간 정도로 많은 시간이 단축된 것을 확인할 수 있었다. 최종적으로 유전자 알고리즘 적용 후, Table 3과 같은 28개의 속성을 사용하여 수행하였을 때, Dunn 지수가 0.999 이상으로 가장 높게 나타난 것으로 확인되었다.
후속연구
아울러 본 연구에서 효과적인 유전자 알고리즘 연산을 위해 사용한 클라우드 분산 컴퓨팅 방식은 MATLAB 기반의 for문 처리에만 사용하였으며, 사용한 cluster의 숫자에 비해 효율성은 떨어지는 결과를 나타내었다. 따라서 향후 프로그래밍 최적화를 통한 연산 속도 향상에 대한 연구를 병행할 예정이다.
또한 본 연구에서 적합도 평가를 위해 사용한 Dunn 지수와 군집화 알고리즘인 Ward의 최소분산법 및 K-means 알고리즘 외에 보다 다양한 알고리즘 간의 비교·분석을 수행할 예정이다.
이렇게 중요한 정보를 담고 있는 수많은 자료들을 통해 서울시군집화 문제에 대한 분석과 해결방안을 제시 할 수 있을 것으로 판단된다. 이러한 군집화 연구는 첫째, 군집화를 통해 각 지역을 특징짓는 행정요소를 발견, 의사결정 수단에 반영할 수 있으며, 둘째, 비즈니스 관점에서 고객 특성을 파악하여 특화된 서비스나 상품을 판매하는 마케팅 수단으로 이용될 수 있을 것으로 사료된다.
한편, 향후 ’동’ 단위 혹은 인구 조사 단위까지 세밀한 공간구분의 적용이 가능할 경우, 새로운 형태의 군집 간 특성을 찾아 낼 수 있을 것으로 사료된다.
강남 3구를 특징짓는 요소는 호텔 등록 현황, 토지평가액, 사립고등학교 졸업자 수 등 일반적으로 생각할수 있을 만한 강남의 특징을 대변하는 속성 정보가 포함되어 있는 반면, 민주노총 조합원수, 보건소 인력현황, 한약도매상 판매업소 등의 예상치 못한 속성 정보 역시 포함되어 있다. 후속 연구에서는 분류된 속성 정보에 대한 심도 깊은 분석을 통해 앞서 설명한 마케팅, 사업 전략 수립 및 의사결정 지원 등 실직적인 활용 방안을 모색해 볼 것이다. 한편, 향후 ’동’ 단위 혹은 인구 조사 단위까지 세밀한 공간구분의 적용이 가능할 경우, 새로운 형태의 군집 간 특성을 찾아 낼 수 있을 것으로 사료된다.
질의응답
핵심어
질문
논문에서 추출한 답변
Dunn 지수란 무엇인가?
Dunn 지수는 Euclidean distance를 이용하여 나누어진 군집이 유효한지에 대한 것을 계산하는 index이다. 다음의 수식 (1)은 이러한 Dunn 지수를 나타내고 있다.
Ward의 최소분산법이란 무엇인가?
Ward의 최소분산법(Ward`s Minimum Variance)은 일반적으로 사용되는 계층 군집 방법 중 하나로 잔차제곱합(Error Sum of Squares, ESS)의 증가가 최소화하도록 군집을 만드는 방법이며, 개체간의 거리는 Euclidean distance를 사용한다. i번째 군집내의 잔차 제곱합을 ESSi라 하면, 그 계산은 수식 (2)와 같이 표현된다.
유전자 알고리즘은 어떤 방식으로 최적의 해를 계산하는가?
유전자 알고리즘은 다윈의 적자생존 이론을 기본 개념으로 하여 최적화 문제를 해결하는 하나의 방법이다. 우선 문제의 해를 유전자 형식으로 표현하기 위해 해를 표현하는 유전자들의 집합을 염색체로 정의한다. 각각의 염색체는 적합도 함수를 통하여 평가하며, 선택, 교차, 변이의 과정을 반복하여 최적의 해를 계산하는 방식이다(Ray and Srivastava, 2008; Kim et al., 2010, Kwak et al.
참고문헌 (11)
Bezdek, J. C. and Nikhil R. P., 1995, Cluster validation with generalized dunn's indices, Proc. of the 2nd New Zealand Conference, pp. 190-193.
Hartigan, J. A. and Wong, M. A., 1979, Algorithm as 136: a k-means clustering algorithm. Journal of the Royal Statistical Society, Vol. 28, No. 1, pp. 100-108.
Hinneburg, A. and Kein, D. A., 1998, An efficient approach to clustering in large multimedia databases with noise, Proc. of the 4th International Conference on Knowledge Discovery and Data Mmining, pp. 58-65.
Kwak, S. Y., Nam, H. W. and Jun, C. M., 2012, An optimal model for indoor pedestrian evacuation considering the entire distribution of building pedestrians, Korea Society for Geospatial Information System, Vol. 20, No. 2, pp. 23-29.
Kim, S. W. and Ahn, H. C., 2010, Development of an intelligent trading system using support vector machines and genetic algorithms, Korea Intelligent Information System Society, Vol. 16, No. 1, pp. 71-92.
Kim, U. G., Ahn, W. S., Lee, C. Y. and Um, M. J., 2012, The optimal analysis of data preprocessing method for clustering the region of precipitation, Journal of Korean Society of Hazard Mitigation, Vol. 12, No. 5, pp. 233-240.
Microsoft, 2014, Microsoft azure, http://azure.microsoft.com/ko-kr/
Milligan, G. W. and Cooper, M. C., 1985, Anexamination of procedures for determining the number of clusters in a data set, Psychometrika, Vol. 50, pp. 159-179.
Ray, A. and Srivastava, D. C., 2008, Non-linear least squares ellipse fitting using the genetic algorithm with applications to strain analysis, Journal of Structural Geology, Vol. 30, pp. 1593-1602.
Statistical Research Institute, 2008, Segmentation of rural areas based on the attributes of agricultural and fishing villages, Technical report, p. 40.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.