选择非重叠的最佳质量集群

Question

说，我已经对我的数据集进行了聚类并且有 10 个聚类。这些集群是不重叠的。但现在假设我更改了所有数据点中的某些特征并再次进行聚类。现在我还有 10 个集群。如果我再重复 3 次，最后我会有 50 个簇。每个集群都有一个与之关联的分数，该分数是根据其组成数据点计算得出的。

这 50 个集群现在有重叠的数据点。我想 select 这 50 个集群中所有可能的非重叠集群，但总分最高。

一种方法是贪心法，我根据分数从高到低对聚类进行排序。然后 select 得分最高的集群。然后从那里保留 selecting 具有非重叠数据点的集群与已经 selected 的集群。但是虽然速度很快，但似乎不是最优解。

示例：假设我有 5 个具有以下分数的集群：

C1 = (A,B,C,D,E,F) 得分 = 10

C2 = (A,B,C) 分数 = 6

C3 = (D,E,F) 得分 = 6

C4 = (G,H,I,J) 分数 = 5

C5 = (K,L) 分数 = 7

贪婪的方法会return{C1,C4,C5}总分10+5+7=22，而更好的选择是{C2,C3,C4,C5}总分得分6+6+5+7=24.

我正在寻找另一种方法，它可以提供比上述贪婪方法更好的解决方案。

Answer 1

您可以使用运筹学技术解决这个问题。

将此问题建模为 set-partitioning 问题

Objective function: maximize score
Constraints: each data point is covered exactly once

然后使用 MIP 求解器或任何其他技术（例如爬山算法、遗传算法等）对其进行求解。您的问题规模非常小，因此可以通过任何优化算法解决。我也在研究类似的问题，但在航空公司机组人员调度领域。我的问题规模如此之大，以至于可能的机组人员时间表（相当于您的集群）是 ~4500 次航班（相当于您的数据点）的航班时间表的 > 无数种组合 ;)

我已经在 python 中编写了您的示例，并且我使用了 Gurobi 的 MIP 求解器，可免费用于学术用途。您也可以使用其他 MIP 求解器。

这里是 python 代码：

from gurobipy import *
import string

data_points = string.ascii_uppercase[:12]

clusters = []
clusters.append(string.ascii_uppercase[:6])
clusters.append(string.ascii_uppercase[:3])
clusters.append(string.ascii_uppercase[3:6])
clusters.append(string.ascii_uppercase[6:10])
clusters.append(string.ascii_uppercase[10:12])

matrix = {}
for dp in string.ascii_uppercase[:12]:
    matrix[dp] = [0]*5

for i in range(0, len(clusters)):
    for dp in clusters[i]:
        matrix[dp][i] = 1

cost = [10, 6, 6, 5, 7]

# Gurobi MIP model
m = Model("Jitin's cluster optimization problem")
m.params.outputflag = 1
x = m.addVars(len(clusters), vtype=GRB.INTEGER, name='x')
indices = range(0, len(clusters))
coef_x = dict()
obj = 0.0
for i in indices:
    coef_x[i] = cost[i]
    obj += coef_x[i] * x[i]
m.setObjective(obj, GRB.MAXIMIZE)
flight_in_pairings = [[] for i in range(0, 4228)]
for dp,j in zip(data_points, range(0, len(data_points))):
    m.addConstr(sum([x[i]*matrix[dp][i] for i in range(0, len(matrix[dp]))]) == 1, "C"+str(j))
m.optimize()
print('Final Obj:', m.objVal)
m.write('results.sol')

代码的输出：

# Solution for model Jitin's cluster optimization problem
# Objective value = 24
x[0] 0
x[1] 1
x[2] 1
x[3] 1
x[4] 1

选择非重叠的最佳质量集群

Selecting non-overlapping best quality clusters

cluster-analysis

greedy