问题描述¶
在 K-Means 聚类问题（最小平方和聚类，MSSC）中，我们希望将一组多维观测点划分为 k 个聚类，每个聚类由其重心定义。每个观测点属于具有最近重心的聚类。更多细节，请参阅 Wikipedia。
学习要点¶
- 添加 集合决策变量 来建模聚类
- 使用 符号 Lambda 函数 来计算每个聚类的重心和方差
建模思路¶
K-Means 聚类问题 (MSSC) 的 OptAgent 模型使用 集合决策变量。每个 set variable 表示一个聚类，其内部的元素表示属于该聚类的观测点。我们使用一个 partition operator 来确保每个观测点恰好属于一个聚类。
我们使用 符号 Lambda 函数 对每个聚类内所有观测点在所有维度上的坐标应用 sum 算子来计算每个聚类的重心。注意，此求和中项的数量在搜索过程中会随着集合的大小变化而变化。
然后我们可以计算总方差。一个聚类的方差是该聚类重心与每个观测点之间的欧几里得距离平方之和。与重心类似，我们使用 符号 Lambda 函数 计算每个聚类的方差。目标是最小化这些方差之和。
Python 实现¶
from pathlib import Path
from optagent import OptModel, solve
def read_elem(filename):
return Path(filename).read_text(encoding="utf-8").split()
#
# Read instance data
#
def read_instance(filename):
file_it = iter(read_elem(filename))
# Data properties
nb_observations = int(next(file_it))
nb_dimensions = int(next(file_it))
coordinates_data = [None] * nb_observations
for o in range(nb_observations):
coordinates_data[o] = [None] * (nb_dimensions)
for d in range(nb_dimensions):
coordinates_data[o][d] = float(next(file_it))
next(file_it) # skip initial clusters
return nb_observations, nb_dimensions, coordinates_data
def main(instance_file, output_file=None, time_limit=60, k=2):
nb_observations, nb_dimensions, coordinates_data = read_instance(instance_file)
model = OptModel()
# clusters[c] represents the observations assigned to cluster c.
clusters = [model.set(nb_observations) for c in range(k)]
# Each observation must belong to exactly one cluster.
model.constraint(model.partition(clusters))
coordinates = model.array(coordinates_data)
variances = []
for cluster in clusters:
size = model.count(cluster)
# Keep the empty-cluster guard from the Hexaly model.
centroid = []
for d in range(nb_dimensions):
coordinate_lambda = model.lambda_function(
lambda i: model.at(coordinates, i // 1, d)
)
centroid.append(
model.iif(size == 0, 0.0, model.sum(cluster, coordinate_lambda) / size)
)
dimension_variances = []
for d in range(nb_dimensions):
centroid_d = centroid[d]
dimension_variance_lambda = model.lambda_function(
lambda i: model.pow(
model.at(coordinates, i // 1, d) - centroid_d, 2
)
)
dimension_variances.append(model.sum(cluster, dimension_variance_lambda))
variances.append(model.sum(dimension_variances))
# Minimize the total within-cluster sum of squares.
total_variance = model.sum(variances)
model.minimize(total_variance)
solution = solve(model, time_limit_s=float(time_limit))
print(f"Observations = {nb_observations}; Dimensions = {nb_dimensions}; "
f"Clusters = {k}; Total variance = {total_variance.value}; "
f"Status = {solution.feasible}")
if solution.feasible:
for c, cluster in enumerate(clusters):
print(f"Cluster {c}: {sorted(cluster.value)}")
if output_file is not None:
lines = [str(total_variance.value), str(k)]
lines.extend(" ".join(str(o) for o in sorted(cluster.value)) for cluster in clusters)
Path(output_file).write_text("\n".join(lines) + "\n", encoding="utf-8")
return solution
本地运行¶
以下代码格演示如何调用 OptAgent 模型。k 使用数据集中的类别数；如需更长搜索，可增大 time_limit。
INSTANCE_DIR = Path.cwd() / "instances"
print("Instances:", INSTANCE_DIR)
solution_ruspini = main(INSTANCE_DIR / "ruspini.dat", k=4, time_limit=1)
solution_iris = main(INSTANCE_DIR / "iris.dat", k=3, time_limit=1)
solution_glass = main(INSTANCE_DIR / "glass.dat", k=6, time_limit=1)
solution_segment = main(INSTANCE_DIR / "segment.dat", k=7, time_limit=1)