[카테고리:] Algorithms

군집화 알고리즘(Clustering Algorithm) 중 K-Means 가 있습니다. K-Means 알고리즘에 대한 설명 이전에, 실제로 구현된 K-Means 알고리즘에 대한 실행 결과를 바로 설명하면서 자연스럽게 K-Means 알고리즘이 무엇인지 설명하겠습니다. 아래는 K-Means 알고리즘을 실행하기 위해 입력한 포인트 데이터입니다. SHP 파일을 통해 입력 받았습니다.

위의 이미지처럼 공간상에 무수히, 주관적 해석이긴 하지만 의미 없이 분포되어 있는 포인트들에 대해서 어떤 연관 관계에 대한 특성을 부여함으로써 몇개로 묶을 수 있는데요. 이처럼 묶는다라는 것을 그룹핑, 클러스터링이라고 합니다. K-Means 알고리즘에서 몇개(K개)로 묶을지를 지정하여 원하는 개수 만큼 클러스터링할 수 있습니다. 아래의 화면은 K-Means 알고리즘을 활용하여 12개의 그룹으로 공간상의 포인트를 묶은 결과입니다.

앞서 포인트를 그룹으로 묶을 때 어떤 관계에 대한 특성을 부여한다고 하였는데요. 위의 화면에서는 그 특성을 거리(Distance)로 하였습니다. 즉, 거리 상으로 가까운 포인트들을 그룹으로 묶는 것입니다.

이처럼 이미 확보한 수 많은 공간상의 데이터를 그룹핑하여 놓는다면, 새로운 포인트에 대해서 어느 그룹에 포함되는지에 대한 해석이 매우 빠르게 분류될 수 있습니다. 이미 확보한 데이터가 많으면 많을 수록, 새로운 데이터에 대한 해석이 보다 더 정확할 수 있겠죠.

아래는 K-Means 알고리즘을 구현한 C# 소스코드이며, 듀라맵(DuraMap-Xr)을 이용하여 K-Means 알고리즘에 필요한 포인트 데이터를 SHP 파일로부터 읽어 들이고 그 결과를 시각화 하였습니다.

Convex Hull은 볼록한 껍데기로.. 무수히 많은 포인트를 감싸는 볼록한 영역으로 정의할 수 있습니다. 입력 데이터인 포인트는 SHP 파일로부터 제공받아, 이를 듀라맵에서 그 결과를 표시하도록 하였습니다. 아래는 그 결과 화면입니다.

무수히 많은 작은 포인트를 감싸는 Convex Hull이 반투명한 빨간색 폴리곤으로 표시되어져 있습니다. 이러한 Convex-Hull에 대한 구현에 대해 C# 클래스로 정의했으며 아래와 같습니다.

using System;
using System.Collections.Generic;

namespace tstConvexHull
{
    public class ConvexHull
    {
        public class Point : IComparer
        {
            public double x;
            public double y;

            public Point()
            {
                x = 0.0;
                y = 0.0;
            }

            public Point(double x, double y)
            {
                this.x = x;
                this.y = y;
            }

            public int Compare(Point p1, Point p2)
            {
                if (p1.x == p2.x)
                {
                    return p1.y > p2.y ? 1 : p1.y < p2.y ? -1 : 0;
                }
                else
                {
                    return p1.x > p2.x ? 1 : p1.x < p2.x ? -1 : 0;
                }
            }
        }

        public static double Cross(Point O, Point A, Point B)
        {
            return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
        }

        public static Point[] Get(Point[] P)
        {
            if (P.Length > 1)
            {
                int n = P.Length, k = 0;
                Point[] H = new Point[2 * n];

                Array.Sort(P, new Point());

                for (int i = 0; i < n; ++i)
                {
                    while (k >= 2 && Cross(H[k - 2], H[k - 1], P[i]) <= 0)
                        k--;
                    H[k++] = P[i];
                }

                for (int i = n - 2, t = k + 1; i >= 0; i--)
                {
                    while (k >= t && Cross(H[k - 2], H[k - 1], P[i]) <= 0)
                        k--;
                    H[k++] = P[i];
                }

                if (k > 1)
                {
                    Point[] NewH = new Point[k - 1];
                    Array.Copy(H, NewH, k - 1);
                    H = NewH;
                }
                return H;
            }
            else if (P.Length <= 1)
            {
                return P;
            }
            else
            {
                return null;
            }
        }
    }
}

실제 위의 Convex-Hull 클래스에 대한 사용은 아래 코드와 같은데요. DuraMap-Xr에서 SHP 파일로부터 점 데이터를 읽어 입력 데이터를 구성하여 Convex-Hull을 실행하고 그 결과로 반투명 빨간색 폴리곤을 추가하는 코드 모두를 나타내고 있습니다.

XrMapLib.ShapeMapLayer lyr = axXr.Layers.GetLayerAsShapeMap("lyr");
XrMapLib.ShapeTable tbl = lyr.ShapeTable;
int cntRows = tbl.RowCount;

ConvexHull.Point[] pts = new ConvexHull.Point[cntRows];

for(int i=0; i
코드를 살짝 설명하면, 1~15번 코드는 SHP 파일로부터 포인트 데이터를 읽어와 Convex-Hull 알고리즘에 입력할 데이터를 준비하는 것이고, 17번 코드가 바로 Convex-Hull의 실행이며 19번 코드부터는 Convex-Hull의 결과를 그래픽 객체로 가시화시켜주는 코드들입니다.