개요

• 서비스하고 있는 앱에 회원들이 늘어남에 따라 지도에 노출시키는 회원들의 마커를 로드하는 속도가 많이 느려지게 되었다. 단순 백엔드 API에서 데이터를 호출하는 문제뿐만 아니라 마커 하나 하나를 앱 단에 그려주는 과정에서 소요되는 시간 역시 UX 차원에서 좋지 못했기에 클러스터링을 적용하여 UI/UX를 개선시키고자 프로젝트를 진행하게 되었다.

클러스터링이란?
쉽게 말해 유사한 성격(?)을 가진 데이터를 하나의 군집으로 묶어 구성하는 것

클러스터링 적용하기

지도 데이터에 알맞은 클러스터링 알고리즘 선정

0. ML 라이브러리 적용

현재 백엔드는 SpringBoot를 사용하고 있었기에 ML 라이브러리로 난 Smile을 선택하였다.

Smile 공식 홈페이지

1. 주소값 기준으로 데이터 묶기

이 방식은 별도의 알고리즘을 적용하지 않고 시도별 행정 구역의 지자체 좌푯값과 행정 구역, 회원들이 등록한 주소 데이터를 기준으로 클러스터를 생성한 방법이다.

• 시도별 지자체 좌푯값과 행정 구역 데이터를 미리 별도의 테이블에 저장하고 지도 레벨 별 행정 구역 기준을 지정 후 지정한 기준으로 주소 데이터를 묶어 지도 상에 그려주는 방식으로 구현
• 장점
  • 별도의 복잡한 알고리즘을 고려할 필요가 없음
• 단점
  • 사전 데이터를 별도로 관리해야함
  • 행정 구역 명칭이 변경될 시 데이터 모두 다 변경해야 함
  • 이로 인해 유지보수가 힘들며 데이터에 종속적임
  • 지자체 좌푯값에 클러스터를 생성하므로 하위 레벨로 접근 시 데이터가 미노출될 우려가 있음
• 결론
  • 데이터를 정제하고 관리하는 시점부터 뭔가 잘못됐다는 것을 크게 느꼈으며 앞서 언급한 단점이 너무나 컸기에 테스트까지만 진행하고 실제로 적용하진 않음

2. KMeans 알고리즘 활용

클러스터링 알고리즘을 활용하고자 했을 시점에 가장 먼저 떠오른 것은 KMeans 알고리즘이었다.

Kmeans 알고리즘이란?
쉽게 말해 주어진 데이터를 K개의 클러스터로 묶는 방식으로 목표 클러스터 개수인 K값에 따라 결과가 크게 달라짐
Hyper Parameter: K (목표 클러스터 개수)
위키백과 참고

Smile을 활용하여 KMeans를 Java/Kotlin에서 사용하는 간단한 방식은 아래와 같다.

import smile.clustering.KMeans;

private static List<ClusteringDto> getClusterInfoWithKMeans(double[][] coordinates) {
		log.warn("Start KMeans Clustering");

		int maxK = 10;
		double[] distortions = new double[maxK];
		double lastDistortion = Double.MAX_VALUE;

		List<KMeans> kMeansResults = new ArrayList<>();
		List<ClusteringDto> clustering = new ArrayList<>();

		// 각 K에 대한 클러스터링 수행 및 결과 저장
		for (int k = 2; k <= maxK; k++) {
			KMeans kMeans = KMeans.fit(coordinates, k);
			kMeansResults.add(kMeans);

			distortions[k - 1] = kMeans.distortion;

			double distortionDrop = lastDistortion - distortions[k - 1];

			log.warn("distortion :: {}", distortionDrop);

			if (distortionDrop < 0.10 * lastDistortion) {
				int optimalK = k - 1;

				KMeans optimalKMeans = kMeansResults.get(optimalK - 1);

				double[][] centroids = optimalKMeans.centroids;
				int[] sizes = optimalKMeans.size;

				getPointsInClusterWithKMeans(coordinates, optimalKMeans, k);

				for (int i = 0; i < centroids.length; i++) {
						ClusteringDTO.builder()
							.count(sizes[i])
							.latitude(centroids[i][0])
							.longitude(centroids[i][1])
							.build();
				}

				return clustering;
			}

			lastDistortion = distortions[k - 1];
		}

		return clustering;
	}

	private static void getPointsInClusterWithKMeans(double[][] coordinates, KMeans optimalKMeans, int k) {
		int kk = optimalKMeans.k;
		int[] labels = optimalKMeans.y;

		ArrayList<double[]>[] clusters = new ArrayList[kk];

		for (int i = 0; i < k; i++) {
			clusters[i] = new ArrayList<>();
		}

		for (int i = 0; i < coordinates.length; i++) {
			int clusterId = labels[i];

			double[] point = new double[2];
			point[0] = coordinates[i][0];
			point[1] = coordinates[i][1];

			clusters[clusterId].add(point);
		}
	}

최적의 K값을 선정하기 위해 Distortion(왜곡)의 차이가 가장 작은 시점의 K값을 도출한 후 (Elbow Method), 이 시점에 존재하는 각각의 클러스터 중심점과 크기를 가진 객체를getPointsInClusterWithKmeans 메소드로 생성하고 이를 최종 반환값으로 사용한다.
(사실 후술하게 되는 단점으로 인하여 유지 보수가 이루어지지 않은 프로토타입에 가까운 코드이기에 고도화 및 리팩토링이 필요한 상태이다)
위 코드를 활용하여 지도에 클러스터를 적용하였으나 큰 단점이 있다는 것을 적용한 후에 깨달았다. KMeans 알고리즘의 특성상 알고리즘을 동일한 데이터셋으로 호출하더라도 동일한 결과를 보장받을 수 없다. 회원 입장에서 지도에 접근할 때 마다 다른 클러스터링을 접하게 된다면 UX 차원에서 좋지 못할 것이라는 생각이 크게 들었다.

• 장점
  • 1번의 방식과 달리 사전 데이터를 관리할 필요없음
• 단점
  - Elbow Method가 적용되어 클러스터 생성에 소요되는 시간이 보다 길게 소요됨
  • 선정된 K값에 따라 클러스터의 값이 크게 좌우됨
  • 알고리즘을 실행할 때 마다 동일한 클러스터를 생성한다고 보장할 수 없음
• 결론
  • 동일한 클러스터링 결과를 노출할 수 없다는 문제가 너무 크게 와닿아 사용하지 않음

3. DBSCAN

KMeans를 활용하는 경우 UX를 해치는 문제가 있기에 이를 해결하고자 도입한 알고리즘은 DBSCAN이다.

DBSCAN 알고리즘이란?
주어진 데이터셋의 밀도를 기반으로 서로 더 가까운 데이터 포인트끼리 군집화 하는 알고리즘
Hyper Parameter: Epsilon, minPts
Epsilon: 클러스터를 이루는 최소 거리
minPts: 클러스터를 이루는데 필요한 최소 데이터 포인트 수
noise(outlier): 클러스터에 속하지 못한 이상치

KMeans와는 달리 DBSCAN은 주어진 데이터셋과 Hyper Paramter가 같은 경우 항상 같은 결괏값을 반환한다. 또한 위치 데이터의 경우 데이터들의 밀도와 분포 모양이 불규칙한데 이러한 경우에 더욱 효과적이게 사용할 수 있다.
Kotlin으로 구현한 smile.clustering.DBSCAN의 간략한 코드는 아래와 같다.

import smile.clustering.DBSCAN
private fun convertClusterInfoToDto(
		coordinates: Array<DoubleArray>,
		epsilon: Double
	): MutableList<ClusteringDto> {
		logger.warn { "Start DBSCAN Clustering" }

		val minPts = 1;
		val clustering: MutableList<ClusteringDto> = mutableListOf()

		val result: DBSCAN<DoubleArray> = DBSCAN.fit(coordinates, EuclideanDistance(), minPts, epsilon)

		val labels: IntArray = result.y;

		logger.info { "DBSCAN Result :: $result" }

		val centroidMap = calculateClusterCentroidsWithDBSCAN(labels, coordinates)

		for ((_, value) in centroidMap) {
			clustering.add(value)
		}

		return clustering
	}

// outlier를 포함한 centroid 계산
	private fun calculateClusterCentroidsWithDBSCAN(
		labels: IntArray,
		dataset: Array<DoubleArray>
	): Map<Int, ClusteringDto> {
		val clusters: MutableMap<Int, MutableList<DoubleArray>> = mutableMapOf()
		val centroids: MutableMap<Int, ClusteringDto> = mutableMapOf()
		var outlierId = -1

		// outlier 포함
		for (i in labels.indices) {
			val clusterId = labels[i]

			// outlier: Int.MAX_VALUE (2147483647)로 clusterId가 들어옴
			if (clusterId != Int.MAX_VALUE) {
				clusters.getOrPut(clusterId) { mutableListOf() }.add(dataset[i])
			} else {
				clusters.getOrPut(outlierId--) { mutableListOf() }.add(dataset[i])
			}
		}

		// 좌표의 평균을 활용하여 centroid 구함
		for ((key, value) in clusters) {
			val sum = DoubleArray(dataset[0].size) { 0.0 } // DoubleArray 0.0으로 초기화
			val clusterSize = value.size

			value.forEach {
				it.forEachIndexed { i, coordinate ->
					sum[i] += coordinate
				}
			}

			sum.forEachIndexed { i, v ->
				sum[i] = v / clusterSize
			}

			centroids[key] = ClusteringDto(
				count = clusterSize,
				latitude = sum[0],
				longitude = sum[1]
			)
		}

		return centroids
	}

DBSCAN의 경우 outlier(noise, 클러스터에 포함되지 못한 데이터)가 존재하는데, 위치 데이터의 경우 이러한 데이터들도 노출되어야 하기에 해당 데이터들 또한 클러스터링 결괏값에 포함시켜줬다.

// 위 코드 중 이부분
for (i in labels.indices) {
			val clusterId = labels[i]

			// outlier: Int.MAX_VALUE (2147483647)로 clusterId가 들어옴
			if (clusterId != Int.MAX_VALUE) {
				clusters.getOrPut(clusterId) { mutableListOf() }.add(dataset[i])
			} else {
				clusters.getOrPut(outlierId--) { mutableListOf() }.add(dataset[i])
			}
		}

smile의 경우 outlier의 clusterId를 INT.MAX_VALUE로 지정하며 clusterId값이 이런 경우에 관하여 -1부터 음수의 clusterId를 부여함으로써 각각의 클러스터로 취급할 수 있게 구현하였다.
또한 DBSCAN의 경우 별도의 centroids값을 지원해주지 않기 때문에 직접 해당 클러스터 내부 데이터의 좌푯값을 활용하여 평균값을 구하고 이를 클러스터의 중심 좌표로 활용하였다.

• 장점
  • 동일한 데이터셋에 대하여 동일한 클러스터 결과를 반환함
  • 밀도 기반으로 다룬 데이터라 위치 데이터에 적합한 클러스터링 결과를 도출 가능
• 단점
  • smile 알고리즘에서 centroid를 지원을 하지 않기에 centroid를 구하는 로직을 별도로 작성해야함
  • outlier를 별도의 클러스터로 다루는 로직을 별도로 작성해야함
  • 디바이스별 지도 레벨에 맞는 최적의 epsilon을 찾기 어려움

결론

최종적으로 3가지 방법 중 DBSCAN을 활용한 방법을 선택하였고 이를 실제 서비스에 적용하여 최대 4400%의 성능 개선율을 이루었다.
실제 API의 호출에서의 차이보다 앱 단의 차이가 훨씬 컸으며 단순히 백엔드 적인 성능 개선을 뛰어넘어 전체 비즈니스 차원의 성능 개선을 이루어서 개인적으로 만족스러운 프로젝트 결과를 얻었다.