계층적 클러스터링

저번에 K-Mean 클러스터링을 구현하려고 고생하던 와중에 K값을 카메라 distance값에 따라 찾아 나가는 방식을 고민했는데

그냥 그대로 클러스터링 해버리면 안되나...?

라는 생각이 들어 찾아보니 비슷한 방법이 이 계층적 클러스터링 (Hiarachical Clustering) 이라고 하더라..

단순히 말하면 여러 지점들 사이의 거리를 전부 계산하고 가장 작은 값을 가지는 두 지점을 합친다.

그리고 합쳐진 값과 가장 가까이 있는 지점을 합친다. 이걸 반복하면 가까이 있는 값들 끼리 자동으로 묶이게 된다.

거대한 단점

Big-O가 n³이다.

물론 포인트 수가 적으면 상관이 없겠지만, 삼차원 그래프를 생각해보면 기하급수적으로 늘어난다는 것을 알 수 있다.

해결할 아이디어

스레시홀드를 주면 n제곱으로 줄일 수 있지 않을까? 그리고 n² 시간복잡도면 성능면에서도 괜찮을지도 모른다

Class cluster {
  let center : coordinate
  let locations: [Location]
}
stuct Distance {
  let startLocation: Location
  let endLocation: Location
}

1. 각 점들을 모두 클러스터로 등록한다.
2. 만약 클러스터 사이의 거리를 계산해서 특정 값 threshold밑으로 들어가면 두 클러스터를 합치고 센터를 조절한다.

그래서 카메라 Distance로 Threshold를 주는 방식으로 했다.

원리는 다음과 같다.

1. 모든 location들로 클러스터를 만든다.
2. 클러스터 사이의 거리를 구한다.
   1. 만약 클러스터 사이의 거리가 threshold보다 작다면 두 클러스터를 합치고 클러스터 센터를 재조정한다.
3. 클러스터들의 count가 끝날 때 까지 반복

이러면 킹론상 한 번의 시도에 시간복잡도 n² 번이 최대일 것이다.

그런데 카메라 distance값에 따라 반응해야 하니 distance도 단계별로 나누어야 할 것 같아 보인다.

    private func cluster(distance: Double) async  -> [Cluster] {
        let startCluster = self.polygonList.map{$0.polygon?.coordinate}
            .filter{!$0.isNil}
            .map{Cluster(center: $0!)}
        let result = await calculateDistance(from: startCluster, threshold: findThreshold(distance))
        return result
    }

처음으로는 가지고 있는 Polygon 스트럭쳐(폴리곤과 point location들과 기타등등을 가지고 있음)를 통해 같은 수의 Cluster를 생성한다.

    private func calculateDistance(from clusters: [Cluster], threshold: Double) async -> [Cluster] {
        var tempClusters = clusters
        var i = 0, j = 0
        while(i < tempClusters.count) {
            j = i + 1
            while(j < tempClusters.count) {
                let distance = tempClusters[i].center.distance(to: tempClusters[j].center)
                if distance < threshold {
                    tempClusters[i].updateCenter(with: tempClusters[j])
                    tempClusters.remove(at: j)
                }
                j += 1
            }
            i += 1
        }
        return tempClusters
    }

그리고 Cluster끼리 거리를 계산하고 그 값이 threshold값보다 작다면, 두 클러스터를 합치고, 합쳐진 클러스터는 지웠다.

func updateCenter(with other: Cluster) {
        self.sumLocs.append(contentsOf: other.sumLocs)
        updateCenter()
    }

클러스터 내부의 updateCenter는 다음과 같이 구성되어 있고, updateCenter()의 내부에는 모든 sumLocs 의 평균 값으로 center를 업데이트 하는 기능이 있다.

트러블 슈팅!

@Published 키워드르 설정된 viewModel 클래스의 clusters: [Cluster] 프로퍼티를 바인딩 하기 위해 async하게 작성된 함수들을 메인쓰레드로 진입시켜야 했다.

단순히 Task {} 를 사용해서 업데이트 하려고 했다면

Publishing changes from background threads is not allowed; make sure to publish values from the main thread (via operators like receive(on:)) on model updates.

경고를 받았을 것이다!

Task { @MainActor in
  do {
    clusters = cluster(distance: cameraDistance) // 뷰에서 호출된 매개변수
  }
}

이렇게 하니 이상 없이 잘 되엇다.

@MainActor 프로퍼티래퍼에 대해 더 공부를 해봐야겠다.

결과

클러스터링이 잘 된다.

Todo

이슈	사진
연산이 순간적으로 42%까지 치솟는다. ( 1초만에 끝나긴 함) 내가 생각한 원인으로는(가설) 1. 계산이 완료되지 않았을 때 줌을 또 하면 계산이 쌓인다. 2. 결국 바인딩 하는 과정에서 메인쓰레드 부담이 커진다

해결 아이디어 : Operation 클래스로 만들어서 isExecuting일 때 또 작업 들어오면 cancle해버리기?