Day_10 문제

학습 목표

K-MEAN 알고리즘 동작 방식을 이해하고 구현할 수 있다.

사전지식

• 없음.

기능요구사항

데이터 목록을 보고 요구사항에 맞게 분류하고 구현할 수 있어야 한다.

• 최소 2명 이상이 하나의 형식에 대해 도전한다.
• 어떤 함수를 구현할 것인가 2명 이상이 함께 결정한다.
• 프로그래밍 요구사항을 만족하는 공통 함수를 설계한다.
• 전달할 데이터 구조를 어떻게 표현할 것인가 결정한다.
• 설계 후에 구현을 해도 무방하지만 구현만 해서는 안된다.

설계 결과 제출

• 설계는 데이터 구조와 데이터 흐름을 명시한 그림을 손으로 그린다.
• 손으로 그린 그림을 캡처해서 gist에 첨부한다.
• gist에 README.md 파일을 추가하고 설계 의도와 방향에 대해 간략하게 설명을 붙인다.

데이터 세트

우리나라 40개 시를 편입년도, 위도, 경도, 인구수를 함께 기록하면 다음 표와 같다. 이 표의 데이터 항목을 분석해서 분류하는 것을 구현하려고 한다.

seq	city	year	latitude	longitude	population
0	서울	1946	37.567	126.978	9720846
1	부산	1963	35.18	129.0756	3413841
2	인천	1981	37.456	126.7052	2938420
3	대구	1981	35.871	128.6014	2414220
4	대전	1995	36.35	127.3845	1475221
5	광주	1986	35.16	126.8526	1454677
6	울산	1997	35.538	129.3114	1159673
7	세종	2012	36.488	127.2816	362259
8	수원	1949	37.264	127.0286	1240374
9	창원	2010	35.229	128.6811	1046188
10	포항	1949	36.019	129.3435	511807
11	전주	1949	35.824	127.148	658346
12	청주	1949	36.642	127.489	847110
13	제주	1955	33.5	126.5312	486306
14	고양	1992	37.656	126.835	1075500
15	용인	1996	37.241	127.1776	1081914
16	천안	1995	36.815	127.1139	666417
17	김해	1995	35.234	128.8811	559648
18	평택	1986	36.992	127.1122	519075
19	마산	1949	35.214	128.5833	424192
20	군산	1949	35.967	126.7364	266569
21	원주	1955	37.342	127.9202	364738
22	의정부	1963	37.739	127.0455	442782
23	김포	1998	37.624	126.7145	442453
24	광명	1981	37.477	126.8664	345262
25	춘천	1995	37.881	127.7298	285584
26	안산	1995	36.79	127.0049	321355
27	성남	1973	37.42	127.1265	944626
28	구미	1978	36.12	128.3446	402607
29	시흥	1989	37.38	126.8031	446420
30	목포	1949	34.812	126.3922	238718
31	익산	1947	35.948	126.9577	292524
32	경주	1955	35.856	129.2247	257041
33	의왕	1986	37.345	126.9688	157346
34	부천	1973	37.499	126.7831	843794
35	남양주	1995	37.637	127.2143	736287
36	파주	1997	37.76	126.7805	453589
37	거제	1989	34.881	128.6216	241253
38	화성	2001	37.2	126.831	791057
39	강릉	1995	37.752	128.8761	213658

[["0","서울" ,"1946","37.5665","126.9780","9720846"],
["1","부산" ,"1963","35.1796","129.0756","3413841"],
["2","인천" ,"1981","37.4563","126.7052","2938420"],
["3","대구" ,"1981","35.8714","128.6014","2414220"],
["4","대전" ,"1995","36.3504","127.3845","1475221"],
["5","광주" ,"1986","35.1595","126.8526","1454677"],
["6","울산" ,"1997","35.5384","129.3114","1159673"],
["7","세종" ,"2012","36.4875","127.2816","362259"],
["8","수원" ,"1949","37.2636","127.0286","1240374"],
["9","창원" ,"2010","35.2286","128.6811","1046188"],
["10","포항" ,"1949","36.0190","129.3435","511807"],
["11","전주" ,"1949","35.8242","127.1480","658346"],
["12","청주" ,"1949","36.6424","127.4890","847110"],
["13","제주" ,"1955","33.4996","126.5312","486306"],
["14","고양" ,"1992","37.6564","126.8350","1075500"],
["15","용인" ,"1996","37.2411","127.1776","1081914"],
["16","천안" ,"1995","36.8151","127.1139","666417"],
["17","김해" ,"1995","35.2342","128.8811","559648"],
["18","평택" ,"1986","36.9921","127.1122","519075"],
["19","마산" ,"1949","35.2138","128.5833","424192"],
["20","군산" ,"1949","35.9672","126.7364","266569"],
["21","원주" ,"1955","37.3422","127.9202","364738"],
["22","의정부","1963","37.7389","127.0455","442782"],
["23","김포" ,"1998","37.6236","126.7145","442453"],
["24","광명" ,"1981","37.4772","126.8664","345262"],
["25","춘천" ,"1995","37.8813","127.7298","285584"],
["26","안산" ,"1995","36.7898","127.0049","321355"],
["27","성남" ,"1973","37.4200","127.1265","944626"],
["28","구미" ,"1978","36.1195","128.3446","402607"],
["29","시흥" ,"1989","37.3803","126.8031","446420"],
["30","목포" ,"1949","34.8118","126.3922","238718"],
["31","익산" ,"1947","35.9483","126.9577","292524"],
["32","경주" ,"1955","35.8562","129.2247","257041"],
["33","의왕" ,"1986","37.3446","126.9688","157346"],
["34","부천" ,"1973","37.4989","126.7831","843794"],
["35","남양주","1995","37.6367","127.2143","736287"],
["36","파주" ,"1997","37.7598","126.7805","453589"],
["37","거제" ,"1989","34.8806","128.6216","241253"],
["38","화성" ,"2001","37.1997","126.8310","791057"],
["39","강릉" ,"1995","37.7519","128.8761","213658"]]

프로그래밍 요구사항

위의 데이터를 분석해서 K개 그룹으로 분류해서 나눠주는 kmeans_pop(), kmeans_long() 함수를 구현해야 합니다. 다음과 같은 방식으로 동작하도록 구현해야 합니다. 단, K값은 2부터 10까지 가능합니다.

• kmeans_pop() : x축은 년도, y축은 인구수(population)를 기준으로 합니다.

• kmeans_long() : x축은 년도, y축은 경도(logitude)를 기준으로 합니다.

알고리즘

1. 입력받은 변수 개수에 따라 무작위로 K개를 임시 중심값으로 선택한다.

2. 모든 도시들을 순회하면서 중심값과 각각 거리를 계산한다.

3. 임시 중심값과 가까운 순으로 K개 그룹을 묶는다.

4. 각 그룹별로 포함된 도시들 무게 중심을 구한다.

5. 새로 계산한 무게 중심과 이전 중심값을 비교한다.

6. 중심값이 변경되었으면 2번부터 다시 반복해서 계산한다.

7. 중심값이 동일하면 멈추고 그룹별 중심값과 그룹에 포함된 도시를 출력한다.

예상결과 및 동작예시

알고리즘 구현에 따라 결과가 달라질 수 있으며, 거리를 계산할 때 년도는 숫자의 크기에 영향을 받기 때문에 어느정도 조정을 해야할 수도 있다.

예시 1. kmeans_pop(2)

그룹#1 중심값 : (1946, 9720847)
그룹#1 도시들 : [“서울”]
그룹#2 중심값 : (1986, 511807)
그룹#2 도시들 : [“부산”, “인천”…”화성”, “강릉”]

예시 2. kmeans_long(4)

그룹#1 중심값 (1996.67, 127.07)
그룹#1 도시들 : [대전, 세종, 고양, 용인, 천안, 김포, 춘천, 안산, 시흥, 남양주, 파주, 화성]
그룹#2 중심값 (1951.93, 127.60)
그룹#2 도시들 : [서울, 부산, 수원, 포항, 전주, 청주, 제주, 마산, 군산, 원주, 의정부, 성남, 고양, 안양, 서귀포]
그룹#3 중심값 (1994.50, 128.83)
그룹#3 도시들 : [대구, 울산, 창원, 김해, 거제, 강릉]
그룹#4 중심값 (1980.50, 127.09)
그룹#4 도시들 : [인천, 광주, 평택, 광명, 성남, 구미, 의왕, 부천]