한국지형공간정보학회지 (Journal of the Korean Society for Geospatial Information System) Vol.22 No.4 December 2014 pp.175-181 연구논문 ISSN: 1598-2955 (Print) ISSN: 2287-6693(Online) http://dx.doi.org/10.7319/kogsis.2014.22.4.175 유전자알고리즘을이용한서울시군집화최적변수선정 Selection of Optimal Variables for Clustering of Seoul using Genetic Algorithm * 김형진 * ㆍ정재훈 ** ㆍ이정빈 *** ㆍ김상민 **** ㆍ허준 ***** Kim, Hyung Jin ㆍ Jung, Jae Hoon ㆍ Lee, Jung Bin ㆍ Kim, Sang Min ㆍ Heo, Joon 要旨 정부 3.0 이라는새로운정부운영계획과함께다양한공공정보를민간이활용할수있게되었으며, 특히서울은이러한행정정보공개및활용을선도하고있다. 공개된행정정보를통해각지역을특징짓는행정요소를발견할경우, 각종행정정책을위한의사결정수단에반영할수있을뿐만아니라특정지역의고객특성을파악하여특화된서비스나상품을판매하는마케팅수단으로도사용할수있을것으로사료된다. 하지만, 방대한양의행정자료로부터각군집의특성을명확히구분할수있는최적의조합을찾는과정은조합최적화문제로서상당한연산량을요구한다. 본연구에서는서울시에서제공하는다차원행정자료로부터서울시를대표하는문화 산업의중심인서초구, 강남구, 송파구등의강남 3 구를다른지역과효과적으로구분하는행정요인를찾고자하였다. 방대한양의행정정보로부터두군집간의차이점을극대화하는요인을선별하기위한최적화방법으로유전자알고리즘을이용하였으며, 군집간차이를계산하는척도로는 Dunn 지수를이용하였다. 또한유전자알고리즘의연산속도의향상을위해 Microsoft Azure 에서제공하는 cloud computing 을이용한분산처리를수행하였다. 자료로는통계청으로부터취득한총 718 개의행정자료를이용하였으며, 그중 28 개가최적변수로선정되었다. 검증을위해선정된 28 개의변수를입력값으로 Ward 의최소분산법및 K-means 알고리즘을통한군집화를수행한결과두경우모두강남 3 구가다른지역으로부터효과적으로분류됨을확인하였다. 핵심용어 : 군집화, Dunn 지수, Ward 의최소분산법, K-means 알고리즘, 유전자알고리즘 Abstract 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. Keywords : Clustering, Dunn s Index, Ward s Minimum Variance, K-means Algorithm, Genetic Algorithm Received: 2014.12.19, accepted: 2014.12.19 * 정회원ㆍ연세대학교토목환경공학과석사과정 (Member, Department of Civil and Environmental Engineering, Yonsei University, awg1@yonsei.ac.kr) ** 정회원ㆍ연세대학교토목환경공학과박사후연구원 (Member, Department of Civil and Environmental Engineering, Yonsei University, lionheart_kr@yonsei.ac.kr) *** 토목환경공학과박사과정 (Department of Civil and Environmental Engineering, Yonsei University, ortolan@yonsei.ac.kr) **** 정회원ㆍ토목환경공학과박사과정 (Member, Department of Civil and Environmental Engineering, Yonsei University, netgo82@yonsei.ac.kr) ***** 교신저자ㆍ정회원ㆍ연세대학교토목환경공학과교수 (Corresponding author, Member, Department of Civil and Environmental Engineering, Yonsei University, jheo@yonsei.ac.kr) 175
176 김형진ㆍ정재훈ㆍ이정빈ㆍ김상민ㆍ허준 1. 서론 가수 Psy 의대표곡인 강남스타일 의성공은전세계에한국의명소인강남지역을알리는계기가되었다. 일반적으로우리나라에서서울강남지역이라함은 서초구, 강남구, 송파구를가리키고있다 (Fig. 1). 이지역에는수많은기업사무실과고급주택가, 유명한학군이몰려있으며노래가사에서와마찬가지로서울을 대표하는문화 산업의중심지역이라할수있다. 그러나이러한강남을비롯하여서울내부의다양한지역을구체적으로특징짓는속성들이무엇인지에대한군집 화시도는아직까지연구가진행된바없다. 우리나라는최근이슈가되고있는데이터주도경제 (data-driven economy) 를활성화시키기위해 정부 3.0 이라는새로운아젠다를세우고, 행정기관들이민간인들을대상으로특별한공개청구없이행정정보를자유롭게열람할수있는서비스를제공하고있다. 특 히서울시는이미수많은행정정보를대중들에게공개해왔으며, 공개되는대부분의데이터가 구 단위의공간정보를포함하고있다. 이렇게중요한정보를담고 있는수많은자료들을통해서울시군집화문제에대한분석과해결방안을제시할수있을것으로판단된다. 이러한군집화연구는첫째, 군집화를통해각지역을 특징짓는행정요소를발견, 의사결정수단에반영할수있으며, 둘째, 비즈니스관점에서고객특성을파악하여특화된서비스나상품을판매하는마케팅수단으로 이용될수있을것으로사료된다. 하지만, 서울시는우리나라에서가장큰도시답게방대한양의행정정보를포함하고있다. 이러한자료로부 터서울시의특징을분석하고군집화하기위해서는우선방대한종류의데이터들로부터군집화요인을분류 하고, 빠른시간내에처리해야하는기술적인문제가발생한다. 예를들어, 강남 3 구를다른구들로부터군집화한다고가정했을때, 수많은행정정보로부터군집화 차이점을최대화시킬수있는요인들만을선별해야하는과정은조합최적화문제 (combinatorial optimization problem) 에해당하며, 일반적으로자료의종류가증가 할수록막대한양의연산을요구한다. 본연구에서는서울시를대상으로강남 3 구가이미군집화되어있다는가정하에다른구와차이점을나타 내는대표적인요인이무엇인지를찾고자하였다. 자료로는통계청에서제공한 718 종류의행정정보를이용하였으며, 방대한양의행정정보로부터강남 3 구를특징 짓는요인을효과적으로선별하기위해유전자알고리즘을이용한방법을제시하였으며, 군집간차이를분석 Figure 1. Twenty five districts (Gu) in Seoul and the Gangnam area in orange color 하여적합성을평가하기위한척도로는 Dunn 지수 (Dunn s index) 를사용하였다. 또한유전자알고리즘연산에소요되는시간소요를효과적으로줄이기위해 Microsoft 에서제공하는 Azure cloud computing 을이 용한분산처리를시도하였다. 아울러, 유전자알고리즘으로선별된요인들이실제로강남 3 구를효과적으로구별하는지를검증하기위해기존의군집화알고리즘 인 Ward 의최소분산법 (Ward`s Minimum Variance) 과 K-means 알고리즘을이용하였다. 2. 연구내용 2.1 연구자료본연구에서는강남 3 구를군집화하기위한기초자 료로써통계청에존재하는 718 가지항목의자료를이용하였다. 다음의 Table 1 은통계청으로부터취득한자료들을크게 9 가지항목으로요약한자료이며, 해당자 료는국가통계포털 (www.kosis.kr) 을통해다운받을수있다. 2.2 Dunn 지수다수의변수에서강남 3 구를특징짓는최적화된변수를선정하기위해서는변수의종류와개수를바꾸어 가면서군집간의차이점을최대화하기위한적합성평가 (cluster validity measure) 과정이필요하다. 군집간특징을판단하는대표적인척도로 Silhouette 지수와 Dunn 지수등이사용되고있으며 (Kim et al., 2012), 본연구에서는그중에서도 Dunn 지수를사용하였다.
유전자알고리즘을이용한서울시군집화최적변수선정 177 Dunn 지수는 Euclidean distance 를이용하여나누어진 군집이유효한지에대한것을계산하는 index 이다. 다음의수식 (1) 은이러한 Dunn 지수를나타내고있다. 여기서 은군집의총개수를, 는두군집의각원소간거리를, 는군집내가장먼거리 를이루는원소둘이이루는반경을, 는 번째군집을 나타낸다. 분모는 번째군집내의원소들중에서가장먼거리의값이들어가며, 분자는 와 번째군집이포함하는원소들중에서최소거리를나타낸다. Dunn 지수의정의에따르면 Dunn 지수가크면클수록군집화는잘되었다고평가할수있다 (Bezdek and Nikhil, 되며, 이는약 2 의 제곱에해당한다. 즉, 현속성정보의종류가 718 개이므로전수조사를위해서는약 2718 번이라는엄청난숫자의 Dunn 지수연산과각각의값들을비교하여최대값을찾는과정이필요하며, 실질적 으로전수조사는불가능하다. 이와같이변수가증가할때그연산량이극단적으로증가하는경우를조합최적화문제라하며, traveling salesman problem 등이대표 적인사례이다 (Rademacher, 2005). 이러한경우는전수조사가아닌휴리스틱 (heuristic) 기법을통해문제를해결하며, 본연구에서는유전자알고리즘을이용해문 제해결을시도하였다. 1995). 2.3 유전자알고리즘 Maximize: 유전자알고리즘은다윈의적자생존이론을기본개 min min 념으로하여최적화문제를해결하는하나의방법이다. max (1) 우선문제의해를유전자형식으로표현하기위해해를 표현하는유전자들의집합을염색체로정의한다. 각각 Where 의염색체는적합도함수를통하여평가하며, 선택, 교 min 차, 변이의과정을반복하여최적의해를계산하는방 식이다 (Ray and Srivastava, 2008; Kim et al., 2010, max Kwak et al., 2012). 초기화는유전자알고리즘을수행하기위한첫번째세대를생성하는과정으로보통임의로염색체에유전한편 를속성정보의종류 (dimension) 라할때, 속자를채우는과정이다. 여기서염색체내의유전자개 성숫자의증가에따라계산량은 로증가하게수와세대내의염색체의개수는주어진문제에따라 수행자가값을선정하게된다. Table 1. Some examples of attributes in each category of open dataset(statistics Korea: www.kosis.kr) Category Items Time average air pollution level, Daily meteorological information, Day average air pollution Environment information at roadside in period, Hour air pollution information in realtime at roadside, observatory, etc. Culture Cultural heritage information, Library for handicapped information, Cultural space In Seoul (Exhibition facilities), Library for handicapped information, etc. Industry Market and mart Information, Market status in Seoul (by Gu), City gas usage in Seoul, Financial institutions in Seoul, Distributor status in Seoul, etc. Safety Prevention of disasters facility status (shelters), stormwater pumping stations operation information in Seoul, etc.. Welfare Facilities for disabled, marriages with foreigners, Child care facilities, Population who health insurance coverage status, Elderly welfare facilities, etc. Public Health Tubercular status, Pharmaceutical manufacturing and dealership status, Spatial information about public toilet, Smoking status, etc. Education Employment rate of vocational high school, Private institutions and reading room, Continuing education person arrangement, Public library, etc. Administrative Chartered house price index, Road infrastructure, Unauthorized buildings, Apartment status, Stormwater pumping stations, etc. Transportation Persons get on and off by each subway station, Parking capacity in public parking lot, Bike paths, Parking lots, etc.
178 김형진ㆍ정재훈ㆍ이정빈ㆍ김상민ㆍ허준 선택은부모세대에서자식세대로전해지는염색체를 결정하는과정이다. 선택방법에는균등비례룰렛휠선택, 토너먼트선택, 순위기반선택등이있다. 염색체의선택은유전자알고리즘의성능에큰영향을끼친 다. 어떤선택방법을이용하느냐에따라나쁜염색체가자식세대에전해질수도있고, 좋은염색체만자식세대에전해질수있다. 그렇지만적합성함수를통하여 나쁜염색체로결정이났을지라도전역최적값에더가까울수있으므로실제로는나쁜염색체도선택될수있도록비례균등룰렛휠선택이많이이용되고있다. 교차는선택을통해자식세대에전해질염색체들을교배하여새로운유전자조합의염색체를자식세대에가지게하는방법이다. 보통교차는부모세대의염색체 2 개를각각나누어서로위치를치환하는방법을이용한다. 좋은염색체를이용하여교차를수행한다하여도적합도평가에서는결과가나빠질수있다. 그렇기때 문에교차의경우에도확률적인접근을통하여수행하는것이일반적이다. 마지막으로변이는기존의염색체에서특정유전자 가임의로다른유전자로바뀌는방법이다. 선택과교차는부모의염색체사이에서자식세대를생성하는과정이지만변이는부모의염색체이외의임의의염색체 에서자식세대를생성하는과정으로지역최적값에빠질위험을줄여주며문제해의다양성을높여준다. 2.4 Ward 의최소분산법 Ward 의최소분산법 (Ward`s Minimum Variance) 은일반적으로사용되는계층군집방법중하나로잔차제 곱합 (Error Sum of Squares, ESS) 의증가가최소화하도록군집을만드는방법이며, 개체간의거리는 Euclidean distance 를사용한다. 번째군집내의잔차제곱합을 라하면, 그계산은수식 (2) 와같이표 현된다. (2) 여기서 는군집내포함된원소벡터, 은 번째군집의원소총개수, 는전체속성값의차원를나타 내며전체 개군집에대한잔차제곱합은다음수식 (3) 과같이계산된다. (3) 잔차제곱합은군집이병합될때마다증가하며두군 집 와 가병합될때에잔차제곱합의증분은다음 수식 (4) 와같이두군집사이의거리를가리킨다. 즉, 새로운군집으로인하여파생되는 의증가량을 두군집사이의거리 () 로정의하고, 가장유사성이큰 군집으로묶어나가는방법이다. 여기서 는군집원소값의평균벡터를나타낸다 (Statistical Research Institute, 2008; Milligan and Cooper, 1985). (4) 2.5 K-Means 알고리즘 K-Means 알고리즘은군집화방법중대표적인비계층적방법의하나이다. 먼저 K 개의원소는초기중심값을통하여군집이이루어지고각각의원소는군집중 심으로부터가까운거리에따라해당군집으로할당되게된다. 초기군집으로부터새로운중심값이계산되면각원소를다시재할당하는연산을반복하여, 궁극적으 로주어진데이터를 K 개의군집으로묶는과정에서군집내제곱합 (within sum of squares) 이최소가되도록각원소를가까운중심으로재할당하는방법이다. 개체 들간의거리는 Euclidean distance 를사용하게되며 재할당기준인군집내제곱합 () 은다음의수식 (5) 와같다 (Statistical Research Institute, 2008; Hartigan and Wong, 1979). (5) 3. 연구결과 강남 3 구와다른구를구별짓는속성정보를찾기위하여미리강남 3 구와다른구들이 2 가지로군집화가 되어있다고가정하고유전자알고리즘의적합도함수인 Dunn 지수를최대로만드는속성의종류와갯수를 찾는방향으로연구를진행하였다. 우선, 유전자알고리즘을본연구에서는 Dunn 지수를최대로만드는속성의차원을모르는상태이기때문에이에대응되는 염색체의유전자수를 1 부터 718 개로증가시켜가며, 각각의경우에대하여유전자알고리즘을계산하였다. 만약유전자수가 1 개일경우와 718 개일경우는각각 718 번과 1 번만의전수조사를수행하고, 그외의경우 는사용하는유전자의개수 ( 속성의차원, ) 에따라조합으로계산되어 ( ) 연산량이급격히증가하므로
유전자알고리즘을이용한서울시군집화최적변수선정 179 Table 2. Test resource Item Product specifications Head CPU 2.1 GHz node Memory 7.0 GB Worker CPU 2.1 GHz node Memory 14.0 GB Operating system Windows Server 2012 Program MATLAB Number of cluster 116 Figure 2. Flow chart 유전자알고리즘을통한방법을이용하였다. 유전자알고리즘을수행하기위한초기염색체의개수 (population number) 는 20, 교배확률은 0.825, 변이확률은 0.05 로선택하였으며, 각유전자알고리즘시행시의반복횟수 (iteration number) 는 1,000 회로제한하였다. 다음의 Fig. 2 는본연구에서수행한유전자알고리즘연산의연구흐름도를나타내고있다. 한편, 본연구에서는연산속도의향상을위해 Microsoft Azure cloud computing 에기반한병렬처리 연산을이용하였다 (Microsoft Azure, 2014). 병렬처리연산에이용한컴퓨팅환경은 Table 2 와같으며, 병렬처리전연산시간은 33.7 시간이소요된데반해, 병렬 처리이후의소요시간은약 3.8 시간정도로많은시간이단축된것을확인할수있었다. 최종적으로유전자알고리즘적용후, Table 3 과같은 28 개의속성을사용 하여수행하였을때, Dunn 지수가 0.999 이상으로가장높게나타난것으로확인되었다. 또한, 유전자알고리즘과 Dunn 지수를통해선택된 28 개의속성에대한검증을위해기존에군집화방법중계층적방법인 Ward 의최소분산법 과비계층적방법인 K-means Algorithms 의결과를비교하였다. 두 방법은 SAS 를이용하여계산하였다. 다음의 Fig. 3 은 Ward 의최소분산법을통해각군집간의병합과정을보여주는덴드로그램 (dendrogram) 이다. 그림에서 x 축 은개체 ( 구 ), y 축은해당군집수에대한결정계수 ( ) 를나타낸다. 덴드로그램은군집형성에대한시각적탐색기능을제공함으로써군집의개수를정하는데좋은 Table 3. The selected attributes by Genetic algorithm and Dunn s index Number of male volunteers aged 40 to 49 Number of female volunteers aged 20 to 29 Number of oriental medicine wholesale stores Number of postman Number of special transports Number of child welfare institutions Number of nurses in public health centers Human resources in public health centers Value of old public land Roads in land use Number of foreign wives Number of marketplaces Number of private day care centers Number of national basic livelihood act recipients Number of private high school graduates Number of classrooms in private high schools Number of parcels from abroad Land use zoning Forest areas Number of rooms per household Number of unregistered labor unions Numbers of the Korean Confederation of Trade Union Members State of land use Number of vans Children of families without parents in high school Female householders among children of families without parents Number of second grade tourist hotels Number of guest rooms of tourist hotels
180 김형진ㆍ정재훈ㆍ이정빈ㆍ김상민ㆍ허준 참고가될수있다. Ward 의최소분산법을통해 28 개 속성값이최후의 2 개로군집화된결과를보면, x 축에서강남 3 구를나타내는서초구, 강남구, 송파구가다른구들과분리된것을쉽게확인할수있었다. K-means 의경우별도의그래픽을제공하고있진않지만, K=2 일경우군집결과에서역시강남 3 구가성공적으로분류된것을확인할수있었다. 한편, 두방법의군집화결과의타당성을정량적으로판단하는데는일반적으로 PSeudo F(PSF) 통계량이사용된다 (Milligan and Cooper, 1985; Statistical Research Institute, 2008). PSF 는군집의밀집정도를측정하는통계량으로서, 군집간분산과군집내분산의비를사용한다 (Milligan and Cooper, 1983; Statistical Research Institute, 2008). PSF 는다음과같이계산된다. (6) 여기서 는군집개수, 는결정계수로서, 군집간분산을의미하고, 은총원소의수를나타낸다. 이때 PSF 값이클수록좋은군집결과를나타낸다. Table 4 는 Ward 의최소분산법과 K-means 방법을 통해군집분석을수행한결과를나타내고있다. SAS 에서통계량이제공된최대 5 개부터 2 개까지의군집분류결과를분석해본결과, Ward 의최소분산법및 K-Means 알고리즘모두군집개수가줄어듬에따라 PSF 지수가지속적으로증가하여강남 3 구와다른 22 Figure 3. Dendrogram of Ward s minimum variance Table 4. Clustering results Methods Number of clusters PSF 5 34.8 Ward s 4 34.9 minimum 3 40.9 variance 2 49.6 5 25.1 4 35.9 K-means 3 43.1 2 49.6 개의구를두군집으로분류했을때최대수치가계산 됐음을확인할수있었으며, 이를통해유전자알고리즘을이용하여선정된속성값이강남 3 구를다른구들과성공적으로구별했음을확인할수있었다. 4. 결론 본연구는 Dunn 지수를적합성평가함수로이용한 유전자알고리즘을통해강남 3 구 ( 와나머지구들을구별짓는속성을찾아내고자하였다. 그결과, 총 718 개의통계자료중에서 Dunn 지수와유전자알고리즘을 통해강남 3 구를구별짓는속성값은총 28 개로결정되었으며, 그결과는 Table 3 과같이나타났다. 또한선별된 28 개속성을이용하여기존의군집화방법인 Ward 의최소분산법과 K-means 알고리즘을이용하여군집을형성할경우강남 3 구와나머지구들이성공적으로 분류되었음을덴드로그램과 PSF 통계량계산을통해알수있었다. 강남 3 구를특징짓는요소는호텔등록현황, 토지평 가액, 사립고등학교졸업자수등일반적으로생각할수있을만한강남의특징을대변하는속성정보가포함되어있는반면, 민주노총조합원수, 보건소인력현 황, 한약도매상판매업소등의예상치못한속성정보역시포함되어있다. 후속연구에서는분류된속성정보에대한심도깊은분석을통해앞서설명한마케팅, 사업전략수립및의사결정지원등실직적인활용방안을모색해볼것이다. 한편, 향후 동 단위혹은인구조사단위까지세밀한공간구분의적용이가능할경우, 새로운형태의군집간특성을찾아낼수있을것으로사료된다. 한편, 유전자알고리즘은휴리스틱기법중하나이므 로매수행마다결과가달라질수있다. 따라서국소최저치를피하고최적화된결과를얻기위해서는파라미터를변경하면서연산을반복할필요가있다. 또한본 연구에서적합도평가를위해사용한 Dunn 지수와군
유전자알고리즘을이용한서울시군집화최적변수선정 181 집화알고리즘인 Ward 의최소분산법및 K-means 알 고리즘외에보다다양한알고리즘간의비교 분석을수행할예정이다. 아울러본연구에서효과적인유전자알고리즘연산을위해사용한클라우드분산컴퓨팅방 식은 MATLAB 기반의 for 문처리에만사용하였으며, 사용한 cluster 의숫자에비해효율성은떨어지는결과를나타내었다. 따라서향후프로그래밍최적화를통한 연산속도향상에대한연구를병행할예정이다. 감사의글 본연구는 국토교통부국토공간정보연구사업국토공간정보의빅데이터관리, 분석및서비스플랫폼기술개발 (14NSIP-B081011-01) 과제 의연구비지원에의 해연구되었음. References 1. 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. 2. 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. 3. 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. 4. 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. 5. 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. 6. 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. 7. Microsoft, 2014, Microsoft azure, http://azure. microsoft.com/ko-kr/ 8. 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. 9. Rademacher, L., 2005, Combinatorial optimization, http://www-math.mit.edu/ ~goemans/18433-fall05. html. 10. 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. 11. Statistical Research Institute, 2008, Segmentation of rural areas based on the attributes of agricultural and fishing villages, Technical report, p. 40.