클러스터링

• 우선 클러스터링을 구현하는 방법부터 알아보자.
  자주 사용되는 클러스터링 알고리즘은 DBSCAN, K-Means, 그리고 Grid-based 클러스터링 등이 있다.

• 위 그림을 보면 쉽게 알아낼 수 있는데 쉽게 말하면 K-Means는 거리 기반이고 DBSCAN은 밀도 기반이다.
  물론 위 둘은 각각 장단점이 존재한다. 하지만 장점이 DBSCAN 방식이 훨씬 많기에 DBSCAN 방식을 많이 기용하지만 내 생각은 데이터 관점이고 지도의 클러스터링은 어디까지나 거리 기준이 더 적합하다. 그래서 K-Means 알고리즘을 구현해보자.

개념

• 개념 K-Means 기능 구현의 원리는 데이터를 K개의 클러스터로 그룹화 방법으로,
  각 클러스터는 중심점으로 표현된다.
  알고리즘은 초기에 무작위로 K개의 중심점을 설정하고, 데이터 포인트들을 가장 가까운 중심점에 할당한 뒤, 새로운 중심점을 계산하여 클러스터를 업데이트하는 방식이다.
  그리고 이 과정을 반복하면서 중심점이 수렴하게 되고, 그것이 바로 클러스터링이다.

구현

export interface Point {
    x?: number;
    y?: number;
}

export class KMeans {
    private k: number;
    private data: Point[];
    private centroids: Point[];

    constructor(k: number, data: Point[]) {
        this.k = k;
        this.data = data;
        this.centroids = this.initializeCentroids();
    }

    private initializeCentroids(): Point[] {
        const centroids: Point[] = [];
        const dataCopy = this.data.slice();
        for (let i = 0; i < this.k; i++) {
            const randomIndex = Math.floor(Math.random() * dataCopy.length);
            centroids.push(dataCopy.splice(randomIndex, 1)[0]);
        }
        return centroids;
    }

    private euclideanDistance(a: Point={x:0,y:0}, b: Point={x:0,y:0}): number {
        return Math.sqrt(((a.x || 0) - (b.x || 0)) ** 2 + ((a.y || 0) - (b.y || 0)) ** 2);
    }

    private updateCentroids(clusteredData: Point[][]): void {
        this.centroids = clusteredData.map((cluster) => {
            const clusterSize = cluster.length;
            const sumX = cluster.reduce((sum, point) => sum + (point.x || 0), 0);
            const sumY = cluster.reduce((sum, point) => sum + (point.y || 0), 0);
            return { x: sumX / clusterSize, y: sumY / clusterSize };
        });
    }

    private assignDataToCentroids(): Point[][] {
        const clusteredData: Point[][] = new Array(this.k).fill(null).map(() => []);

        this.data.forEach((point) => {
            let minDistance = Number.MAX_VALUE;
            let closestCentroidIndex = -1;

            this.centroids.forEach((centroid, index) => {
                const distance = this.euclideanDistance(point, centroid);
                if (distance < minDistance) {
                    minDistance = distance;
                    closestCentroidIndex = index;
                }
            });

            clusteredData[closestCentroidIndex].push(point);
        });

        return clusteredData;
    }

    public run(maxIterations: number = 100): void {
        for (let i = 0; i < maxIterations; i++) {
            const clusteredData = this.assignDataToCentroids();
            this.updateCentroids(clusteredData);
        }
    }

    public getClusters(): Point[][] {
        return this.assignDataToCentroids();
    }

    public getCentroid(): Point[]{
        return this.centroids;
    }
}

사용

// 클러스터링 만드는 함수
const clusterData = kMeans.getClusters();
const clusterCircle = kMeans.getCentroid();
if(vw3dViewer.value.camera._positionCartographic.height > 10000){
  clusterCircle.forEach((data, index) => {
    vw3dViewer.value.entities.add({
      position: Cesium.Cartesian3.fromDegrees(data.x, data.y, 4000.0),
      label: {
        text: clusterData[index].length.toString(),
        font: '24px Helvetica',
        fillColor: ws3d.value.common.Color.GOLD,
        outlineColor: ws3d.value.common.Color.GOLD,
        outlineWidth: 2,
      },
      name: "Green circle at height with outline",
      ellipse: {
        semiMinorAxis: 30000.0/kCount.value^50,
        semiMajorAxis: 30000.0/kCount.value^50,
        height: 4000.0,
        material: ws3d.value.common.Color.ROYALBLUE,
        outline: true,
      },
    });
  })
}

핵심 개념 설명

1. initializeCentroids 메서드:

   • 이 메서드는 k-means 알고리즘을 위해 초기 중심점(centroid)들을 설정하는 역할을 한다.
   • 이 알고리즘은 랜덤한 중심점에서 시작하여 데이터를 군집화하는 과정을 반복하면서 최적의 중심점을 찾아나간다.
   • initializeCentroids 메서드는 클래스 생성자에서 호출되며, 주어진 데이터(this.data)에서 무작위로 k개의 중심점을 선택한다.
     데이터를 무작위로 섞은 후, 처음 k개의 데이터를 초기 중심점으로 설정한다. 이렇게 초기 중심점이 설정된 뒤에는 k-means 알고리즘이 실행된다.

2. assignDataToCentroids 메서드:

   • 이 메서드는 주어진 데이터를 초기 중심점에 할당하여 클러스터를 형성하는 역할을 한다. k-means 알고리즘의 핵심 로직이 구현된 메서드이다.
   • assignDataToCentroids 메서드는 초기 중심점을 기준으로 주어진 데이터(this.data)를 클러스터에 할당한다. 주어진 데이터의 각 데이터 포인트들을 가장 가까운 중심점에 할당하며, 이를 바탕으로 클러스터를 형성한다.
     즉, 각 클러스터는 하나의 중심점과 해당 중심점에 할당된 데이터 포인트들로 이루어진다.
   • 이 메서드를 통해 클러스터링이 수행되고, 그 결과로 클러스터에 속한 데이터들을 담은 배열(clusteredData)이 반환됩니다.

즉, initializeCentroids 메서드는 초기 중심점을 설정하고 assignDataToCentroids 메서드는 데이터를 클러스터에 할당하는 역할을 수행한다.
이후에는 updateCentroids 메서드를 통해 클러스터링 결과에 따라 중심점을 업데이트하며 알고리즘이 반복적으로 실행된다.