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

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

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

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

Пример: скажем, у меня есть 3 кластера со следующими оценками:

C1 = (A,B,C,D,E,F) Оценка = 10

C2 = (A,B,C,D) Оценка = 6

C3 = (D, E, F) Оценка = 6

Допустимое перекрытие составляет 1 элемент или менее 40% размера меньшего кластера.

Жадный подход вернет {C1} с общим счетом 10, в то время как лучшим вариантом является {C2, C3} с общим счетом 6+6=12, с перекрытием элемента 'D', т.е. 1/размер(C3 ) = 1/3 = 33,33% ‹ 40%

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


optimization cluster-analysis threshold nonlinear-optimization
person Jitin Singla    schedule 18.06.2018    source источник
comment
О каком количестве кластеров и о скольких точках данных идет речь?   -  person juvian    schedule 18.06.2018
comment
Пробовали ли вы использовать универсальный оптимизатор? Если у вас всего 50 кластеров, вы можете себе это позволить.   -  person Has QUIT--Anony-Mousse    schedule 18.06.2018
comment
@juvian В моей проблеме количество кластеров увеличивается после каждой итерации. Он начинается с 20, а затем после каждой итерации добавляется еще 20. И мне нужно выбрать перекрывающиеся кластеры, как определено ранее, на каждой итерации. Так что я сделаю с 20 кластерами, затем во 2-й итерации с 40 кластерами, затем в 3-й итерации с 60 кластерами..... До 400 или 600 итераций. Всего точек данных также может быть 50 000.   -  person Jitin Singla    schedule 18.06.2018
comment
Хорошо звучит как слишком много данных для оптимального решения. Не могу придумать лучшего жадного алгоритма, можно попробовать эвристические алгоритмы, такие как запретный поиск или генетический алгоритм.   -  person juvian    schedule 19.06.2018
comment
Генетический алгоритм мог бы сработать... но я все еще ищу другие методы...   -  person Jitin Singla    schedule 19.06.2018

Ответы (1)


arrow_upward
1
arrow_downward

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

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

Вот код Python для вышеуказанной проблемы:

from gurobipy import *
import string
# List of all subtomograms
data_points = string.ascii_uppercase[:6]
data_points = list(data_points)

# Clusters as list of lists, where each list is list of subtomograms
clusters = []
clusters.append(['A', 'B', 'C', 'D', 'E', 'F'])
clusters.append(['A', 'B', 'C', 'D'])
clusters.append(['D', 'E', 'F'])

# Create a matrix: num_subtomograms x num_clusters
matrix = {}
for dp in data_points:
    matrix[dp] = [0]*len(clusters)

# Make matrix[subtomogram_i][cluster_i] = 1, if subtomogram_i is present in cluster_i
for i in range(0, len(clusters)):
    for dp in clusters[i]:
        matrix[dp][i] = 1

# Score of each cluster in the same order as used in matrix
cost = [10, 6, 6]

# Gurobi MIP model
m = Model("Cluster selection optimization")
m.params.outputflag = 1
m.params.method = 2 # for barrier method in Gurobi, it is used to solve quadratic programming problems

# Adding a variable x where x[i] will represent whether or not ith cluster is selected or not
x = m.addVars(len(clusters), vtype=GRB.BINARY, name='x')

# generate objective function: score[0]x[0] + score[1]x[1] .....
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)

# Generate constraints
threshhold = 0.4 # 40% threshold set
count = 0
m_sum = []
for i in range(len(clusters)):
    m_sum.append(sum([matrix[k][i] for k in data_points]))
for i in range(len(clusters)):
    for j in range(i+1, len(clusters)):
        if i==j:
            continue
        tmp = (sum([matrix[k][i]*matrix[k][j] for k in data_points])*x[i]*x[j] <= threshhold*min(m_sum[i], m_sum[j]))
        m.addConstr(tmp, "C"+str(count))
        count += 1

# Optimize
m.optimize()
print("Optimized")

Результат и данные журнала вышеуказанного запуска:

Parameter outputflag unchanged
   Value: 1  Min: 0  Max: 1  Default: 1
Changed value of parameter method to 2
   Prev: -1  Min: -1  Max: 5  Default: -1
Optimize a model with 0 rows, 3 columns and 0 nonzeros
Model has 3 quadratic constraints
Variable types: 0 continuous, 3 integer (3 binary)
Coefficient statistics:
  Matrix range     [0e+00, 0e+00]
  QMatrix range    [1e+00, 4e+00]
  Objective range  [6e+00, 1e+01]
  Bounds range     [1e+00, 1e+00]
  RHS range        [0e+00, 0e+00]
  QRHS range       [1e+00, 2e+00]
Found heuristic solution: objective -0.0000000
Modified 2 Q diagonals
Modified 2 Q diagonals
Presolve time: 0.00s
Presolved: 0 rows, 3 columns, 0 nonzeros
Variable types: 0 continuous, 3 integer (3 binary)
Presolve removed 0 rows and 3 columns
Presolve: All rows and columns removed

Root relaxation: objective 2.200000e+01, 0 iterations, 0.00 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0      12.0000000   12.00000  0.00%     -    0s

Explored 0 nodes (2 simplex iterations) in 0.01 seconds
Thread count was 32 (of 32 available processors)

Solution count 2: 12 -0 

Optimal solution found (tolerance 1.00e-04)
Best objective 1.200000000000e+01, best bound 1.200000000000e+01, gap 0.0000%
Optimized
Final Obj: 12.0
1
2

Существуют и другие методы решения этой проблемы, такие как методы искусственного интеллекта (Hill Climber, имитация отжига и т. д.), методы эволюционной оптимизации, такие как генетический алгоритм (вы можете использовать NSGA2 после изменения его в соответствии с вашей проблемой, код доступен на http://www.iitk.ac.in/kangal/codes.shtml)

person Divyam Aggarwal    schedule 19.06.2018