Выбор непересекающихся кластеров наилучшего качества - PullRequest
Новая
       9

Выбор непересекающихся кластеров наилучшего качества

0 голосов
/ 10 мая 2018

Скажем, я сделал кластеризацию на моем наборе данных и у меня есть 10 кластеров.Эти кластеры не перекрываются.Но теперь предположим, что я изменил какую-то функцию во всех моих точках данных и снова делаю кластеризацию.Теперь у меня есть еще 10 кластеров.Если я повторю это, скажем еще 3 раза, в конце у меня будет 50 кластеров.С каждым кластером связана оценка, которая рассчитывается на основе составляющих его точек данных.

Эти 50 кластеров теперь имеют перекрывающиеся точки данных.Я хочу выбрать все возможные непересекающиеся кластеры из этих 50 кластеров, но с наивысшей общей оценкой.

Одним из способов является жадный метод, при котором я сортирую кластеры на основе оценки от наивысшей к наименьшей.Затем выберите кластер с наивысшей оценкой.Затем продолжайте выбирать кластеры, которые имеют непересекающиеся точки данных с уже выбранными кластерами.Но это не кажется оптимальным решением, хотя оно и быстрое.

Пример: скажем, у меня есть 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

Жадный подход вернет {C1, C4, C5} с общим счетом10 + 5 + 7 = 22, тогда как лучшим вариантом является {C2, C3, C4, C5} с общим счетом 6 + 6 + 5 + 7 = 24.

Я ищу другой метод, которыйможет дать оптимальное решение или лучшее решение, чем вышеупомянутый жадный подход.

1 Ответ

0 голосов
/ 11 мая 2018

Вы можете решить эту проблему, используя методы исследования операций.

Смоделируйте эту проблему как проблему разделения множеств с 

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

, а затем решите ее, используя MIP-решатель или любой другой метод (например, альпинист Хилла, генетический алгоритм и т. Д.) Масштабы вашей проблемы очень малы, следовательно, разрешимы любым алгоритмом оптимизации. Я также работаю над аналогичной проблемой, но в области планирования экипажа авиакомпании. Масштабы моей проблемы настолько велики, что возможные расписания экипажа (эквивалентные вашим кластерам) составляют> миллиард комбинаций для расписания полета ~ 4500 рейсов (эквивалентно вашим точкам данных);)

Я кодировал ваш пример на python и использовал MIP-решатель от Gurobi, доступный бесплатно для академического использования. Вы также можете использовать другие 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
...