penalty Kmeans의 MaxK값 결정 방식 수정

[hoonv]

feat

최대 K의 값 설정해주는 방식을 기존에는 축적에 따라 해주었다면 place의 개수에 따라 결정하도록 변경

penalty 클러스터링 알고리즘의 시간복잡도를 구해본 결과 5nk^2 + nk의 복잡도를 가짐 위의 복잡도에서 값이 MAXOPERATION 120000을 넘지 않는 최대의 K를 Maximum K로 결정 MAXOPERATION이 120000인 이유는 값을 바꿔가며 돌려보았을 때 평균 계산시간이 13ms (130ms인것 같네요 ?)가 되는 값이기 때문

public func measureTime(_ closure: () -> ()) -> TimeInterval {
    let startDate = Date()
    closure()
    return Date().timeIntervalSince(startDate)
}

시간측정은 위의 함수를 이용하였습니다

더 의논하고 싶은점

더 개선해야할 부분이 있을까요 ? 제가 봤을때 보이는 부분은 Kmeans의 중심을 이동하는 부분을 5번하는데 하는데 있어서 place를 초기화 해주었다가 다시 할당을 해주는데 이부분을 개선하면 좀 효과가 있을지..

[SkydevilK]

• determinateMaxK Function의 return 값 결정 조건을 서술해주셨으면 좋겠습니다.

• 이 부분 제가 이해한 바로는 가까이에 있는 것들 묶는 것인데, 왜 5번으로 고정하셨나요? 변경이 안될 때로 바꿔주는게 더 좋지 않을까요?

      for _ in 0..<iterationCount {
          var newCentroids = centroids.map { PenaltyCluster(lat: $0.latitude, lng: $0.longitude, places: [])}
          newCentroids = distributeToCentroid(places: places, centroids: newCentroids)
          centroids = newCentroids
      }

[hoonv]

얼마나 loop를 돌아야 하는것은 중요한 고려사항이긴 합니다.

고려해볼만한 방법들은 아래와 같은데요,

• 미리 정의된 반복 횟수만큼 반복한다. 이 조건은 클러스터링 알고리즘의 실행 시간을 제한한다. 그러나 반복 횟수가 모자라서 클러스터링의 질이 떨어질 수 있다.
• 벡터가 속한 클러스터가 더 이상 변하지 않을 때까지 반복한다. 이 조건은 지역 최소 (local minimum)에 들어가는 경우를 제외하고는 군집화의 질이 매우 좋다. 그러나 실행 시간이 길어진다는 단점이 있다.
• 중심이 더 이상 변하지 않을 때까지 반복한다.
• RSS가 임계치 이하로 떨어질 때까지 반복 한다. 이 기준에 따라 종료되면 군집화의 질이 매우 좋다.

4번째 방법은 RSS의 임계치를 결정하는 방법이 모호합니다. 3번째 방법은 중심이 계속 변할 수 있습니다. 그래서 루프가 끝나지 않을 위험성도 존재합니다. 2번째 방법은 3번째 방법과 같은 위험성을 갖고있습니다. 첫번째 방법의 단점은 클러스터링의 질이 떨어질 수 있다는 단점이 존재하는데요 초기 클러스터링의 위치를 최대 평균 거리로 잘 떨어뜨려 놓아서 반복회수를 높게 가져가지 않아도 꽤나 잘 떨어져 있는 것을 느꼈습니다 결정적으로는 시간복잡도를 계산할 수 있고 어느정도 시간이 보장되어서 사용하였습니당.ㅎㅎ

[hoonv]

    private func determinateMaxK(count: Int) -> Int {
        let MAXOPERATION: Double = 125000
        let a: Double = 5
        let b: Double = 1
        let c: Double = MAXOPERATION / Double(count)
        let root = Int((-b + sqrt(1 + 4 * a * c)) / Double(2 * a))

        switch (count, root) {
        case (let x, let y) where x > y:
            return y
        case (let x, let y) where x <= y:
            return x
        case (_, let y) where y == 0:
            return 1
        default:
            return 1
        }
    }

그부분의 설명이 많이 부족하네용.. 설명드리자면 시간복잡도가 2차 방정식이고 5nk^2 + nk, 이 값은 125000보다 작아야 하니까 <= 125000 인데, 이때의 Max K는 교점이여서 결국 5nk^2 + nk - 125000의 근을 구하기 위해 근의공식을 사용했고, 이때의 K값과 place값의 갯수를 비교해서 더 작은 K값을 사용하도록 했습니다.

[beggu84]

오옷, place 1000개 일 때가 place 37개 일 때 보다 더 적게 걸린 건가요?

[hoonv]

총 K의 갯수가 작아져서 그렇습니당.. ㅎㅎ

[beggu84]

아, 어느 정도 균일된 속도를 내기 위해 poi 개수와 max k 값을 적절히 조절하는 거군요.

혹시 완젼 병렬적으로 할 수 있는 단순한 작업은 없을까요? GPU 로 돌릴 수 있는?

[hoonv]

앗 지금 ㅎㅎ K값에 따라 클러스터링 하는부분을 병렬 처리로 해보겠습니다 ㅎㅎ

[hoonv]

        let clusterQueue = DispatchQueue(label: "cluster", attributes: .concurrent)
        let candidateQueue = DispatchQueue(label: "candidate")
        let group = DispatchGroup()

        print("place \(places.count) maxK \(maximumK)")

        for k in 1..<maximumK where !isCancelled {
            clusterQueue.async(group: group) {
                let clusters = self.clustering(places: places, k: k)
                candidateQueue.sync {
                    candidateCluster.append(clusters)
                }
            }
        }

        let result = group.wait(timeout: .distantFuture)

group을 만들어서 병렬처리로 진행했습니다. 약간의 시간을 줄여준 거 같습니다. ㅎㅎ 조언 감사합니다. 근데 뭔가 극적으로 줄어든 거 같진 않아서 병렬처리를 잘했나 다시 확인해봐야겠습니다