The K-Means clustering 알고리즘은 주어진 데이터를 K number로 군집화하는 알고리즘입니다. 그리고 각 cluster 간의 거리 차이를 최소화하는 방식으로 작동합니다. 이 알고리즘은 Unsupervised-Learning의 한 종류이며 레이블이 없는 입력 데이터에 label을 부여하는 역할을 합니다.
K-Means 알고리즘은 clustering 방법 중 partitioning 방법에 속합니다. Partitioning 방법은 주어진 데이터를 여러 개의 partition으로 나누는 분할 방식입니다. 예를 들어, n개의 데이터 객체가 입력된다고 가정해보겠습니다. 이때 partitioning 방법은 주어진 데이터를 N보다 작은 K개의 그룹으로 나누며, 이때 각 그룹은 cluster를 형성합니다. 즉, 하나의 데이터를 하나 이상의 데이터 객체로 분할하는 것입니다. K-means clustering, divided by 10
Implementation
K-Means clustering의 작동 과정은 다음 5단계로 구성됩니다:
K(cluster의 개수)를 선택하고 데이터 입력
cluster의 초기 centroid를 무작위로 설정
가장 가까운 centroid를 기준으로 각 cluster에 데이터 할당
cluster의 새로운 centroid를 재계산하고 4단계 재실행
centroid의 위치가 더 이상 업데이트되지 않으면 종료
위의 단계를 기반으로 K-Means 알고리즘을 구현해보겠습니다. 먼저, KMeans 객체를 정의합니다. 입력값으로 분할할 cluster의 개수(K), points cloud, 그리고 centroid 업데이트 반복 횟수인 iteration_count를 받습니다.
class KMeans(PointHelper):
def __init__(self, points=None, k=3, iteration_count=20, random_seed=0):
"""KMeansCluster simple implementation using Rhino Geometry
Args:
points (Rhino.Geometry.Point3d, optional): Points to classify. Defaults to None. if points is None, make random points
k (int, optional): Number to classify. Defaults to 3.
iteration_count (int, optional): Clusters candidates creation count. Defaults to 20.
random_seed (int, optional): Random seed number to fix. Defaults to 0.
"""
PointHelper.__init__(self)
self.points = points
self.k = k
self.iteration_count = iteration_count
self.threshold = 0.1
import random # pylint: disable=import-outside-toplevel
self.random = random
self.random.seed(random_seed)
다음으로, 주어진 points cloud에서 K개만큼 무작위로 선택하여 K개수만큼 cluster의 centroid를 초기화합니다. 초기 centroid 설정이 완료되면, 각 centroid와 주어진 points cloud 사이의 거리를 계산하고, 가장 가까운 거리에 있는 cluster에 데이터를 할당합니다. 이제 모든 cluster의 centroid를 업데이트해야 합니다. 이를 위해 초기 cluster들(points cloud clusters)의 centroid를 계산 해야 합니다.
마지막으로, 업데이트된 centroid와 이전 centroid 사이의 거리를 계산합니다. 이 거리가 더 이상 변화가 없다면 종료합니다. 그렇지 않다면, 위에서 설명한 주요 과정들을 반복합니다.
def kmeans(self, points, k, threshold):
"""Clusters by each iteration
Args:
points (Rhino.Geometry.Point3d): Initialized given points
k (int): Initialized given k
threshold (float): Initialized threshold
Returns:
Tuple[List[List[Rhino.Geometry.Point3d]], List[List[int]]]: Clusters by each iteration, Indices by each iteration
"""
centroids = self.random.sample(points, k)
while True:
clusters = [[] for _ in centroids]
indices = [[] for _ in centroids]
for pi, point in enumerate(points):
point_to_centroid_distance = [
point.DistanceTo(centroid) for centroid in centroids
]
nearest_centroid_index = point_to_centroid_distance.index(
min(point_to_centroid_distance)
)
clusters[nearest_centroid_index].append(point)
indices[nearest_centroid_index].append(pi)
shift_distance = 0.0
for ci, current_centroid in enumerate(centroids):
if len(clusters[ci]) == 0:
continue
updated_centroid = self.get_centroid(clusters[ci])
shift_distance = max(
updated_centroid.DistanceTo(current_centroid),
shift_distance,
)
centroids[ci] = updated_centroid
if shift_distance < threshold:
break
return clusters, indices
이제 위의 코드에서 K를 설정하여 point cluster들을 얻을 수 있습니다. 그리고 K-Means의 상세 코드는 이 링크에서 확인할 수 있습니다. Implemented K-means clustering, divided by 10 From the left, Given Points · Result clusters
K-Rooms clusters
K-Means 알고리즘은 위에서 설명한 것처럼 주어진 점들을 K개수만큼 군집화하는 데 사용됩니다. 이를 활용하면 주어진 건축 경계를 K개수만큼 분할할 수 있습니다. 이는 K개수의 방을 얻을 수 있다는 것을 의미합니다.
코드를 작성하기 전에 다음 순서를 설정합니다.
입력값으로 건물 외벽선(닫힌 선)과 분할할 방의 개수를 받습니다
oriented bounding box를 생성하고 grid를 생성합니다
grid 중심점들을 위에서 구현한 K-Means clustering 알고리즘에 삽입합니다
군집화된 grid 중심점들의 인덱스를 기반으로 grid들을 병합합니다
core에서 각 방까지의 최단 경로를 탐색하고 복도를 생성합니다
이제 K-Rooms cluster 알고리즘을 구현해보겠습니다. KRoomsClusters 클래스를 다음과 같이 정의하고 1단계에서 정의한 것을 입력값으로 받습니다. 그리고 KMeans 클래스를 상속받습니다.
class KRoomsCluster(KMeans, PointHelper, LineHelper, ConstsCollection):
"""
To use the inherited moduels, refer the link below.
https://github.com/PARKCHEOLHEE-lab/GhPythonUtils
"""
def __init__(self, floor, core, hall, target_area, axis=None):
self.floor = floor
self.core = core
self.hall = hall
self.sorted_hall_segments = self.get_sorted_segment(self.hall)
self.target_area = target_area
self.axis = axis
KMeans.__init__(self)
PointHelper.__init__(self)
LineHelper.__init__(self)
ConstsCollection.__init__(self)
다음으로, grid를 생성하기 위해 OBB(oriented bounding box)를 생성합니다. OBB는 grid의 xy축을 정의하기 위한 것입니다. (OBB 생성 알고리즘을 보려면 이 링크를 참조하세요) 그런 다음, grid와 grid centroid를 생성하고, grid의 중심점들과 K값을 넣어 clustering indices를 추출한 후, 같은 cluster 내에 존재하는 모든 grid들을 병합합니다. K-Rooms clustering key process, divided by 5 From the left, Grid and centroids creation · Divided rooms
def _gen_grid(self):
self.base_rectangles = [
self.get_2d_offset_polygon(seg, self.grid_size)
for seg in self.sorted_hall_segments[:2]
]
counts = []
planes = []
for ri, base_rectangle in enumerate(self.base_rectangles):
x_vector = (
rg.AreaMassProperties.Compute(base_rectangle).Centroid
- rg.AreaMassProperties.Compute(self.hall).Centroid
)
y_vector = copy.copy(x_vector)
y_transform = rg.Transform.Rotation(
math.pi * 0.5,
rg.AreaMassProperties.Compute(base_rectangle).Centroid,
)
y_vector.Transform(y_transform)
base_rectangle.Translate(
(
self.sorted_hall_segments[0].PointAtStart
- self.sorted_hall_segments[0].PointAtEnd
)
/ 2
)
base_rectangle.Translate(
self.get_normalized_vector(x_vector) * -self.grid_size / 2
)
anchor = rg.AreaMassProperties.Compute(base_rectangle).Centroid
plane = rg.Plane(
origin=anchor,
xDirection=x_vector,
yDirection=y_vector,
)
x_proj = self.get_projected_point_on_curve(
anchor, plane.XAxis, self.obb
)
x_count = (
int(math.ceil(x_proj.DistanceTo(anchor) / self.grid_size)) + 1
)
y_projs = [
self.get_projected_point_on_curve(
anchor, plane.YAxis, self.obb
),
self.get_projected_point_on_curve(
anchor, -plane.YAxis, self.obb
),
]
y_count = [
int(math.ceil(y_proj.DistanceTo(anchor) / self.grid_size)) + 1
for y_proj in y_projs
]
planes.append(plane)
counts.append([x_count] + y_count)
x_grid = []
for base_rectangle, count, plane in zip(
self.base_rectangles, counts, planes
):
xc, _, _ = count
for x in range(xc):
copied_rectangle = copy.copy(base_rectangle)
vector = plane.XAxis * self.grid_size * x
copied_rectangle.Translate(vector)
x_grid.append(copied_rectangle)
y_vectors = [planes[0].YAxis, -planes[0].YAxis]
y_counts = counts[0][1:]
all_grid = [] + x_grid
for rectangle in x_grid:
for y_count, y_vector in zip(y_counts, y_vectors):
for yc in range(1, y_count):
copied_rectangle = copy.copy(rectangle)
vector = y_vector * self.grid_size * yc
copied_rectangle.Translate(vector)
all_grid.append(copied_rectangle)
union_all_grid = rg.Curve.CreateBooleanUnion(all_grid, self.TOLERANCE)
for y_count, y_vector in zip(y_counts, y_vectors):
for yc in range(1, y_count):
copied_hall = copy.copy(self.hall)
copied_hall.Translate(
(
self.sorted_hall_segments[0].PointAtStart
- self.sorted_hall_segments[0].PointAtEnd
)
/ 2
)
vector = y_vector * self.grid_size * yc
copied_hall.Translate(vector)
all_grid.extend(
rg.Curve.CreateBooleanDifference(
copied_hall, union_all_grid
)
)
self.grid = []
for grid in all_grid:
for boundary in self.boundaries:
tidied_grid = list(
rg.Curve.CreateBooleanIntersection(
boundary.boundary, grid, self.TOLERANCE
)
)
self.grid.extend(tidied_grid)
self.grid_centroids = [
rg.AreaMassProperties.Compute(g).Centroid for g in self.grid
]
마지막으로, 각 방을 복도로 연결하면 완성입니다! (최단 경로 알고리즘을 위해 Dijkstra 알고리즘을 구현했습니다. 구현 내용은 다음 링크에서 확인할 수 있습니다. 다음 기회에 이에 대한 포스트를 작성하도록 하겠습니다.) Corridor creation
Limitation of K-Rooms clusters
우리가 구현한 K-Rooms Clusters 알고리즘은 아직 불완전합니다. 위에서 보여진 이미지들은 K값이 작을 때 유효한 결과입니다. K값이 증가하고 방의 개수가 증가할 때, 건축적으로 적절한 형태가 도출되지 않는 문제가 발생합니다. 아래 예시와 같습니다: Improper shapes, divided by 13 From the left, K-Rooms · Result corridor 이 문제를 해결하기 위해 앞으로 해야 할 일은 적절한 형태를 정의하고 post-processing으로 이를 완화하는 로직을 만드는 것입니다. 그리고 K-Rooms clusters의 전체 코드는 이 링크에서 확인할 수 있습니다.
