가까운 도시 찾기
요구사항 분석
프로그램 목적
주어진 도시 데이터를 처리하여 임의의 중심값을 기준으로 가까운 도시 간 클러스터 생성 및 그래프 시각화
프로그래밍 요구사항
kmeans_pop(), kmeans_long() 함수 구현
kmeans_pop()- x축 : 년도, y축 : 인구수
kmeans_long()- x축 : 년도, y축 : 경도
프로그램 로직
- 입력 데이터 실행되는 함수에 따라 파싱
- 2 <= K <= 10 사이 임의의 값 K개의 임시 중심값 생성
- 도시를 기준으로 임시 중심값 까지의 거리 계산
- 가장 가까운 임시 중심값에 속하는 K개 그룹 생성
- 각 그룹별 포함된 도시들 무게 중심 계산
- if(이전 중심값 !== 새 중심값) 다시 도시 순회하며 중심값 계산
- if(이전 중심값 === 새 중심값) 그룹별 중심값, 그룹에 포함된 도시 표시
주의사항
- 년도는 숫자 크기 영향받아 정규화 필요
- 결과 출력 소수점 발생 시 3번째 자리에서 절삭
데이터 구조
손그림
데이터 흐름도(피그잼)
class Cluster{
Point p[]
Point centerP
}
class Point{
float x
float y
}
//kmeans 함수 내부
clusters[]=newClusr()[k]
clusters = Array.from({ length: k }, () => new Cluster());구현
Point, Cluster 클래스
// 클러스터 및 포인트 클래스
class Cluster {
// 기본값 + 객체형으로 인수 넣을 수 있게
constructor({ centerPoint = null } = {}) {
// 좌표에 근접한 포인트 = 도시들
this.points = [];
// 해당 좌표
this.centerpoint = centerPoint;
}
}
class Point {
constructor({ x, y, name }) {
this.x = x;
this.y = y;
this.name = name;
}
}군집을 담는 cluster변수를 Array로 선언하고, 군집은 Cluster class를 선언해 각 도시들을 담을 수 있게, 각 도시는 Point class를 구성하는 방식으로 데이터 구조를 구성했다.
Point 클래스
K_mean 함수 호출시 입력되는 도시 데이터세트를 Point클래스를 통해 name, x, y 프로퍼티만갖는 인스턴스로 변환한다.
Cluster 클래스
그룹핑된 도시목록(최단거리)이 들어갈 Points배열과, Points의 도시목록에 대한 중심좌표값을 가진다.
데이터 정규화, 비정규화
function NormalizeData(data) {
const xArray = data.map((point) => point.x);
const yArray = data.map((point) => point.y);
const xMax = Math.max(...xArray);
const xMin = Math.min(...xArray);
const yMax = Math.max(...yArray);
const yMin = Math.min(...yArray);
return data.map((point) => {
return {
x: (point.x - xMin) / (xMax - xMin),
y: (point.y - yMin) / (yMax - yMin),
name: point.name,
};
});
}
// 정규화 복구 함수
function DenomalizeData(data, xMax, xMin, yMax, yMin) {
return data.map((point) => {
return {
x: point.x * (xMax - xMin) + xMin,
y: point.y * (yMax - yMin) + yMin,
name: point.name,
};
});
}- 파싱된
Point객체의x,y좌표(년도,pop/long값)을 정규화하는 함수이다. - 정규화를 썼던 이유
- 데이터의 크기들이 서로 달라서 계산하기 용이하게 데이터 가시성, 스케일을 동일하게 하기 위함.
- 일관성이 없어 정확도가 낮아질 수도 있어서 예방하기 위함.
initCenterPoint
function initCenterpoint(data, k) {
// 임시 중심점을 담을 배열
const centerpoint = [];
// centerpoint에 추가된 인덱스 검별용 Set
const usedIdx = new Set();
// k만큼 임시 중심점 생성
while (centerpoint.length <= k) {
// 도시 데이터를 랜덤으로 뽑을 인덱스
const randomIdx = Math.floor(Math.random() * data.length);
// 뽑은 인덱스가 아니라면 임시 중심점 추가
if (!usedIdx.has(randomIdx)) {
centerpoint.push(
new Point({
x: data[randomIdx].x,
y: data[randomIdx].y,
name: data[randomIdx].name,
}),
);
usedIdx.add(randomIdx);
}
}
return centerpoint;
}- 무작위로 K개의 임시 중심 좌표를 뽑는 함수이다.
- 도시목록중 중복되지 않게 임의로 K개의 도시를 고르고, 각 도시의 x,y좌표를 반환한다.
addClusters, calculateDistance
function addClusters(data, clusters, tempCenterpoints) {
// 데이터를 순회하며 클러스터에 푸시
data.forEach((city) => {
let minDistance = 99999999;
let clusterIdx = 0;
// 길이를 대조하며, 최소 길이를 구함
tempCenterpoints.forEach((centerpoint, idx) => {
const curDistance = calculateDistance(centerpoint, city);
if (curDistance < minDistance) {
minDistance = curDistance;
clusterIdx = idx;
}
});
clusters[clusterIdx].points.push(city);
});
}
// 거리 계산 함수
function calculateDistance(point1, point2) {
// 피타고라스 정리 이용
return Math.sqrt(
Math.pow(point1.x - point2.x, 2) + Math.pow(point1.y - point2.y, 2),
);
}addClusters 함수를 통해 모든 도시들을 순회하면서, 모든 도시에 대해 현재 K개의 centerpoint에 대한 거리를 구한다.(calculateDistance 함수를 통해 계산)
centerpoint 별로 거리가 최소인 도시끼리 그룹핑 시키는 함수이다. 코드상으론 아래와 같이 동작한다.
- K개의
centerpoint에 대해 Cluster객체가 생성되고, 각 cluster의 points배열에 거리가최소인 도시들이 할당된다. - 각 도시들은 더가까운
centerPoint에 대해 Cluster객체의 points배열에 할당되는 식으로 동작한다.
kmeans_pop, kmeans_long
function kmeans_pop(k) {
let clusters = Array.from({ length: k }, () => new Cluster());
const parsedData = popData;
const [normalizedData, xMax, xMin, yMax, yMin] = NormalizeData(parsedData);
// 처음에 임시 중심점 초기화
let centerpoints = initCenterpoint(normalizedData, k);
let newCenterpoints = null;
// 모든 cluster의 중심점 데이터가 이전과 동일할때까지 반복
do {
// 클러스터 초기화
clusters = Array.from(
{ length: k },
(_, idx) => new Cluster({ centerpoints: centerpoints[idx] }),
);
// 가장 가까운 중심점에 속하는 그룹 생성
addClusters(normalizedData, clusters, centerpoints);
// 새로운 중심점 계산
newCenterpoints = calculateCenterpoint(clusters);
// console.log(centerpoints);
// console.log(newCenterpoints);
} while (
centerpoints.x !== newCenterpoints.x &&
centerpoints.y !== newCenterpoints.y
);
clusters.forEach((cluster) => {
cluster.points = DenomalizeData(cluster.points, xMax, xMin, yMax, yMin);
cluster.centerpoint = {
x: cluster.centerpoint.x * (xMax - xMin) + xMin,
y: cluster.centerpoint.y * (yMax - yMin) + yMin,
};
});
return clusters;
}- k개의 cluster를 초기화한뒤, 각 도시들의 데이터를 파싱후 정규화한다.
- 이후 무작위 k개의 중심좌표 설정하고 순회를 시작한다.
- 그룹별 무게중심을 구하고, 기준 중심좌표와 무게중심을 비교하며
- 중심좌표와 무게중심이 같아질때까지 반복한다.
결과
import { CITY_DATA } from './static.mjs';
// 클러스터 및 포인트 클래스
class Cluster {
// 기본값 + 객체형으로 인수 넣을 수 있게
constructor({ centerPoint = null } = {}) {
// 좌표에 근접한 포인트 = 도시들
this.points = [];
// 해당 좌표
this.centerpoint = centerPoint;
}
}
class Point {
constructor({ x, y, name }) {
this.x = x;
this.y = y;
this.name = name;
}
}
// 데이터 파싱
const popData = CITY_DATA.map((city) => {
const [seq, name, year, latitude, longitude, population] = city;
return new Point({ x: year, y: population, name });
});
const longData = CITY_DATA.map((city) => {
const [seq, name, year, latitude, longitude, population] = city;
return new Point({ x: year, y: longitude, name });
});
// 데이터 정규화
function NormalizeData(data) {
const xArray = data.map((point) => point.x);
const yArray = data.map((point) => point.y);
const xMax = Math.max(...xArray);
const xMin = Math.min(...xArray);
const yMax = Math.max(...yArray);
const yMin = Math.min(...yArray);
return [
data.map((point) => {
return {
x: (point.x - xMin) / (xMax - xMin),
y: (point.y - yMin) / (yMax - yMin),
name: point.name,
};
}),
xMax,
xMin,
yMax,
yMin,
];
}
// 정규화 복구 함수
function DenomalizeData(data, xMax, xMin, yMax, yMin) {
return data.map((point) => {
return {
x: point.x * (xMax - xMin) + xMin,
y: point.y * (yMax - yMin) + yMin,
name: point.name,
};
});
}
// 임시 중심점 초기화
function initCenterpoint(data, k) {
// 임시 중심점을 담을 배열
const centerpoint = [];
// centerpoint에 추가된 인덱스 검별용 Set
const usedIdx = new Set();
// k만큼 임시 중심점 생성
while (centerpoint.length < k) {
// 도시 데이터를 랜덤으로 뽑을 인덱스
const randomIdx = Math.floor(Math.random() * data.length);
// 뽑은 인덱스가 아니라면 임시 중심점 추가
if (!usedIdx.has(randomIdx)) {
centerpoint.push(
new Point({
x: data[randomIdx].x,
y: data[randomIdx].y,
name: data[randomIdx].name,
}),
);
usedIdx.add(randomIdx);
}
}
return centerpoint;
}
// 거리 계산 함수
function calculateDistance(point1, point2) {
// 피타고라스 정리 이용
return Math.sqrt(
Math.pow(point1.x - point2.x, 2) + Math.pow(point1.y - point2.y, 2),
);
}
// 4. 가장 가까운 임시 중심값에 속하는 K개 그룹 생성
function addClusters(data, clusters, tempCenterpoints) {
// 데이터를 순회하며 클러스터에 푸시
data.forEach((city) => {
let minDistance = 99999999;
let clusterIdx = 0;
// 길이를 대조하며, 최소 길이를 구함
tempCenterpoints.forEach((centerpoint, idx) => {
const curDistance = calculateDistance(centerpoint, city);
if (curDistance < minDistance) {
minDistance = curDistance;
clusterIdx = idx;
}
});
clusters[clusterIdx].points.push(city);
});
}
// 무게중심을 이용해 중심값을 계산하는 함수
function calculateCenterpoint(clusters) {
clusters.forEach((cluster) => {
const xSum = cluster.points.reduce((acc, cur) => acc + cur.x, 0);
const ySum = cluster.points.reduce((acc, cur) => acc + cur.y, 0);
cluster.centerpoint = new Point({
x: xSum / cluster.points.length,
y: ySum / cluster.points.length,
});
});
return clusters.map((cluster) => cluster.centerpoint);
}
function kmeans_pop(k) {
let clusters = Array.from({ length: k }, () => new Cluster());
const parsedData = popData;
const [normalizedData, xMax, xMin, yMax, yMin] = NormalizeData(parsedData);
// 처음에 임시 중심점 초기화
let centerpoints = initCenterpoint(normalizedData, k);
let newCenterpoints = null;
// 모든 cluster의 중심점 데이터가 이전과 동일할때까지 반복
do {
// 클러스터 초기화
clusters = Array.from(
{ length: k },
(_, idx) => new Cluster({ centerpoints: centerpoints[idx] }),
);
// 가장 가까운 중심점에 속하는 그룹 생성
addClusters(normalizedData, clusters, centerpoints);
// 새로운 중심점 계산
newCenterpoints = calculateCenterpoint(clusters);
// console.log(centerpoints);
// console.log(newCenterpoints);
} while (
centerpoints.x !== newCenterpoints.x &&
centerpoints.y !== newCenterpoints.y
);
clusters.forEach((cluster) => {
cluster.points = DenomalizeData(cluster.points, xMax, xMin, yMax, yMin);
// console.log(cluster.centerpoint.x * (xMax - xMin), xMax, xMin);
cluster.centerpoint = {
x: Math.floor(cluster.centerpoint.x * (xMax - xMin) + xMin),
y: Math.floor(cluster.centerpoint.y * (yMax - yMin) + yMin),
};
});
return clusters;
}
function kmeans_long(k) {
let clusters = Array.from({ length: k }, () => new Cluster());
const parsedData = longData;
const [normalizedData, xMax, xMin, yMax, yMin] = NormalizeData(parsedData);
// 처음에 임시 중심점 초기화
let centerpoints = initCenterpoint(normalizedData, k);
let newCenterpoints = null;
// 모든 cluster의 중심점 데이터가 이전과 동일할때까지 반복
do {
// 클러스터 초기화
clusters = Array.from(
{ length: k },
(_, idx) => new Cluster({ centerpoints: centerpoints[idx] }),
);
// 가장 가까운 중심점에 속하는 그룹 생성
addClusters(normalizedData, clusters, centerpoints);
// 새로운 중심점 계산
newCenterpoints = calculateCenterpoint(clusters);
// console.log(centerpoints);
// console.log(newCenterpoints);
} while (
centerpoints.x !== newCenterpoints.x &&
centerpoints.y !== newCenterpoints.y
);
clusters.forEach((cluster) => {
cluster.points = DenomalizeData(cluster.points, xMax, xMin, yMax, yMin);
// console.log(cluster.centerpoint.x * (xMax - xMin), xMax, xMin);
cluster.centerpoint = {
x: (cluster.centerpoint.x * (xMax - xMin) + xMin).toFixed(2),
y: (cluster.centerpoint.y * (yMax - yMin) + yMin).toFixed(2),
};
});
return clusters;
}
const returnClusters = kmeans_long(5).map((cluster, idx) => {
return `그룹#${idx + 1} 중심값 (${cluster.centerpoint.x}, ${
cluster.centerpoint.y
})\n그룹#${idx + 1} 도시들 ${cluster.points
.map((point) => point.name)
.join(', ')}`;
});
console.log(returnClusters);
코뿔소처럼 저돌적으로