在满足约束的同时最小化距离的聚类算法

数据挖掘 聚类 优化
2022-03-06 07:44:43

我有90个人的数据。

一个人的数据:
- x 坐标
- y 坐标
- 分数(1 到 6)

我想组成 9 人一组,这样:
- 一组人之间的距离尽可能小
- 具有相同坐标的人在不同的组中
- 组内的人应该有不同的分数

我并不期待一个成熟的算法,而是向正确的方向暗示。到目前为止,我正在使用一个简单的 k-means 算法来形成组,以便人们之间的距离最小化,但是不幸的是,没有考虑其他两个约束。

2个回答

我发现这篇关于“使用约束进行聚类”的文章对您正在谈论的内容很有帮助:

学分:将先验知识纳入聚类的约束聚类,改编自 Sugato Basu 和 Ian Davidson 的教程(SDM 2005)

您正在描述优化的变体,通过从允许的集合中系统地选择输入值并计算函数的值来最大化实际函数。具体来说,一种称为线性规划的变体,您可以在其中最大化相似性(相似性是距离的倒数),但要受到几个约束:

在此处输入图像描述