컨설팅을 하다 보면 각 클러스터의 크기 (클러스터링 한 인스턴스의 갯수)를 동일하게 시뮬레이션 해야 할 때가 있습니다.
창고의 위치를 Simulation 했는데 클러스터링 알고리즘 특성상 특정 클러스터에 포함되는 인스턴스의 수를 정할 수 없는 경우
특정 지역의 클러스터는 (ex. 강원권) 커버하는 고객의 수가 다른 클러스터보다 작은경우 이를 해결할 수 있는 방법이 필요합니다.
Mikko I. Malinen and Pasi Fr¨anti: Balanced K-Means for Clustering 논문을 보면 좋은 아이디어를 얻을 수 있습니다.
클러스터링의 결과를 수리적인 방법을 이용해서 후보정을 하는 방법을 제안을 하고 있는데
상대적으로 구현하기 쉬워서 아래와 같은 방법으로 구현 할 수 있습니다.
Mikko I. Malinen and Pasi Fr¨anti: Balanced K-Means for Clustering (2014)
from ortools.sat.python import cp_model
import numpy as np
import math
from sklearn.cluster import KMeans
def kmeansBalanced():
cities = np.array(
[[0.0, 0.0], [0.0, 900], [100, 500], [200, 200], [400, 100], [400, 800], [700, 200], [800, 500], [900, 0.0], [900, 900],
[0.0, 100], [0.0, 700], [400, 0.0], [400, 100], [400, 800], [400, 900], [700, 0.0], [700, 900], [900, 200], [900, 700]])
numPoints = len(cities)
numClusters = 2
eachClusterQty = 10
kmeans = KMeans(n_clusters=numClusters)
kmeans.fit(cities)
initClusterCenters = kmeans.cluster_centers_
distancesMatrix = np.zeros((numPoints, numClusters), dtype=int)
for i in range(numPoints):
for k in range(numClusters):
dist = math.sqrt(np.sum((cities[i] - initClusterCenters[k])**2))
distancesMatrix[i, k] = int(round(dist))
model = cp_model.CpModel()
# x[i][k]는 데이터 포인트 `i`가 클러스터 `k`에 속하면 True, 아니면 False
x = {}
for i in range(numPoints):
for k in range(numClusters):
x[(i, k)] = model.NewBoolVar(f'x_{i}_{k}')
# 각 데이터 포인트는 정확히 하나의 클러스터에 할당되어야 함
for i in range(numPoints):
model.Add(sum(x[(i, k)] for k in range(numClusters)) == 1)
# 각 클러스터가 갖는 인스턴스 수를 동일하게 하는 제약
for k in range(numClusters):
model.Add(sum(x[(i, k)] for i in range(numPoints)) == eachClusterQty)
objectiveList = []
for i in range(numPoints):
for k in range(numClusters):
objectiveList.append(x[(i, k)] * distancesMatrix[i, k])
model.Minimize(sum(objectiveList))
solver = cp_model.CpSolver()
# solver.parameters.max_time_in_seconds = 10.0
status = solver.Solve(model)
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
assignments = [[] for _ in range(numClusters)]
for i in range(numPoints):
for k in range(numClusters):
if solver.BooleanValue(x[(i, k)]):
assignments[k].append(i)
break
for k, clusterPoints in enumerate(assignments):
print(f"Cluster {k}:")
if clusterPoints:
print(f"City Index: {clusterPoints}")
if __name__ == '__main__':
kmeansBalanced()
Python
복사
Reference
[1] Mikko I. Malinen and Pasi Fr¨anti: Balanced K-Means for Clustering (2014)
