요구 사항
가까운 위치에 뜬 Annotation들이 너무 많으면 오히려 가독성이 떨어지는 문제가 있었다.
그래서 Map Annotation들을 묶어서 그 Center location에 Annotation갯수를 보여주는 새로운 Clustered Annotation을 만들고 싶어서 공부를 시작했다.
클러스터링 알고리즘
좌표평면의 여러 산개한 포인트들을 비슷한 성격을 가진 녀석들끼리 묶는것을 클러스터링, 그리고 그것을 가능하게 해 주는 알고리즘을 클러스터링 알고리즘이라고 한다.
나는 이런 저런 알고리즘을 찾아보다가 가장 쉬워 보이고 자원도 덜 들어 보이는 K-Means알고리즘을 활용하기로 했다.
K-Means 알고리즘
K-means 알고리즘은 K값(클러스터의 갯수)을 입력받고, 각 포인트들 사이의 거리를 토대로 클러스터링을 하는 알고리즘이다. 자세한 설명은 다음 블로그글을 토대로 알아보자
기본적으로
클러스터 위치 정하기 -> 포인트들을 가장 가까운 클러스터에 포함하기 -> 클러스터에 포함된 포인트들의 중간 값으로 클러스터 위치 재조정 하기 -> 포인트들을 가장 가까운 클러스터에 포함하기 -> ...
순으로 반복해서 진행된다. 5회 반복정도면 괜찮게 클러스터링이 될 것이라고 생각하고 iteration은 최대 5회로 정했다.
구현하기
우선 좌표값의 사이를 유클리드 거리로 반환하는 함수 distance를 로케이션에 만들어 두었다.
extension CLLocationCoordinate2D {
func squaredDistance(to : CLLocationCoordinate2D) -> Double {
return (self.latitude - to.latitude) * (self.latitude - to.latitude) + (self.longitude - to.longitude) * (self.longitude - to.longitude)
}
func distance(to: CLLocationCoordinate2D) -> Double {
return sqrt(squaredDistance(to: to))
}
}클러스터 클래스
클러스터는 로케이션들의 집합으로 이루어지고, center로케이션을 가진다.
로케이션을 추가 삭제할 수 있어야 하고 center location을 업데이트 하는 기능이 필요하다.
Center location은 각 로케이션들의 평균의 위치로 정해지므로 각 로케이션들을 모두 합하고 count로 나누었다.
class Cluster: Equatable {
static func == (lhs: Cluster, rhs: Cluster) -> Bool {
lhs.center == rhs.center
}
static let greatestFinite: Cluster = Cluster(center: .init(latitude: 1000, longitude: 1000))
var sumLocs: [CLLocationCoordinate2D]
var center: CLLocationCoordinate2D
init(center: CLLocationCoordinate2D) {
self.center = center
self.sumLocs = []
}
func updateCenter(with other: Cluster) {
self.sumLocs.append(contentsOf: other.sumLocs)
updateCenter()
}
func add(loc: CLLocationCoordinate2D) {
sumLocs.append(loc)
}
func remove(loc: CLLocationCoordinate2D) {
sumLocs.removeAll(where: {$0 == loc})
}
func updateCenter() {
let sumloc = sumLocs.reduce(CLLocationCoordinate2D(latitude: 0, longitude: 0)){CLLocationCoordinate2D(latitude: $0.latitude + $1.latitude, longitude: $0.longitude + $1.longitude)}
let count = sumLocs.count
center = CLLocationCoordinate2D(latitude: sumloc.latitude / Double(count), longitude: sumloc.longitude / Double(count))
}
}KMeans 클래스
final class KMeans: Operation {
let k: Int
let locs: [Location]
var clusters: [Cluster]
var isChanged: Bool
init(k: Int, locs: [Location]) {
self.k = k
self.locs = locs
self.clusters = []
self.isChanged = false
}
}K-Means에서는 K 값과 Location(프로젝트에서 location 및 기타 정보를 저장하는 구조체)들을 입력받아야 한다.
비동기 방식으로 구현되게 하기 위해서 Operation을 활용하였다. 관련 정보는 비동기 공부하는 중에 공부했으니 그만알아보자
extension KMeans {
override var isAsynchronous: Bool {
true
}
override func main() {
guard !isCancelled else {return}
run()
}
}비동기로 작동하기 위해 isAsynchronous 프로퍼티를 true로, cancelled일 때는 바로 리턴하도록 main()을 작성하였다.
extension KMeans {
func runOperation(_ operations: [() -> Void]) {
guard !isCancelled else { return }
self.queuePriority = QueuePriority(rawValue: k + 4) ?? .high
operations.forEach{
$0()
}
}
func run() {
let maxIteration = 5
let initCenters = randomCentersLocations(count: k, locs: locs)
clusters = generateClusters(centers: initCenters)
runOperation([classifyPoints, updateCenters])
var iteration = 0
repeat {
runOperation([updatePoints, updateCenters])
iteration += 1
} while isChanged && (iteration < maxIteration) && !isCancelled
}
}runOperation 함수는 QueuePriority를 최상으로 설정하고 오퍼레이션들을 시행한다.
run 함수에서는 클러스터의 초기 설정을 하고, 5번 update points, update centers를 반복한다.
//MARK: - 로케이션을 k개로 나눈다음 첫 번째 값들로 초기 위치 선정
private func randomCentersLocations(count: Int, locs: [Location]) -> [Location] {
guard locs.count > count else {return locs}
guard let firstpoint = locs.first else {return []}
var result = [firstpoint]
switch count {
case 1:
return result
default :
let diff = locs.count / (count - 1)
(1..<count).forEach{
result.append(locs[$0 * diff - 1])
}
return result
}
}
//MARK: - 로케이션 배열로 클러스터 배열을 만든다.
private func generateClusters(centers: [Location]) -> [Cluster] {
let centroids = centers.map {$0.coordinate}
return centroids.map{Cluster(center: $0)}
}클러스터의 초기 설정을 하는 많은 방법 중에서 그냥 k값의 크기 만큼 location들을 나누고, 그 첫 번 째 위치로 클러스터의 위치를 정했다.
//MARK: - 로케이션마다의 가까운 클러스터를 찾고 로케이션의 정보를 추가한다
private func classifyPoints() {
locs.forEach{
let cluster = findNearestCluster(loc: $0.coordinate)
cluster.add(loc: $0.coordinate)
}
}
private func updatePoints() {
isChanged = false
clusters.forEach { cluster in
let locs = cluster.sumLocs
for loc in locs {
let nearestCluster = findNearestCluster(loc: loc)
if cluster == nearestCluster { continue
}
isChanged = true
nearestCluster.add(loc: loc)
cluster.remove(loc: loc)
}
}
}classyfyPoints()함수는 초기값을 설정할 때, updatePoints()함수는 iteration을 수행하면서 동작한다. 만약 값이 변하지 않는다면(최적의 클러스터링 상태) isChanged가 false이므로 iteration이 멈추고 그렇지 않더라도 5회 반복하면 멈춘다.
K값을 구하자
K는 클러스터링의 갯수를 의미한다. K값을 정하는데 영향을 미치는 요소는 다음과 같다.
- Mapkit의 camera.distance = 맵을 비추는 카메라의 높이를 M단위로 알려준다.
- Annotation의 갯수 = 최다 K값은 어노테이션의 갯수여야 한다 (각자 하나인 경우)
이를 토대로 계산해보자면
- Annotation 사이의 거리를 모두 구한다
- 맵의 distance로 값을 나눈다
- 나누어진 값이 특정 숫자 밑으로 내려간 경우 두 로케이션을 합친다.
이런 식으로 하면 어떨까 생각했었는데 맵을 보면서 distance가 2000m 씩 늘어났을 때 경우의 수를 따지고 있었는데,,
mapkit에는 clustering annotation이 이미 있다는 것을 이 쯤에서야 알고야 말았다.
그래도 배웠다.
아무튼 배웠다.. 그래서 아깝지 않다....
