Python bitmasking и точка кластера/группы происхождения

Question

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

Например:

data = [[10,10],[20,20],[5,3],[7,2],[90,78]] #Data of length 5 
clusters = [[[10,10],[20,20]],[[5,3],[7,2],[90,78]]] #List containing two clusters (cluster 0 and cluster 1) 

output = [0,0,1,1,1] 

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

Answer 1

data = [[10,10],[20,20],[5,3],[7,2],[90,78]] #Data of length 5 
clusters = [[[10,10],[20,20]],[[5,3],[7,2],[90,78]]] #List containing two clusters (cluster 0 and cluster 1) 

gen = (count for count, y in enumerate(clusters) for x in data if x in y) 
output = list(gen) 

Вот выражение генератора, которое делает то же самое.

Answer 2

Преобразование пары точек в кортеж вместо списка, позволяет использовать каждую точку в качестве ключа в словаре (потому что ключ должен быть hashable), с кластером происхождения в качестве значения

data = [[10,10],[20,20],[5,3],[7,2],[90,78]] 
clusters = [[[10,10], [20,20]], [[5,3], [7,2], [90,78]]] 
cd = dict((tuple(p), i) for i, cl in enumerate(clusters) for p in cl) 
output = [cd[tuple(p)] for p in data] # output = list(map(lambda p: cd[tuple(p)], data)) 
print(output) 

производит

[0, 0, 1, 1, 1] 

ИСПОЛНЕНИЯ

из любопытства, я сравнил мое решение с @ Back2B asics ', чтобы выяснить, насколько хорошо эти два масштаба с растущей совокупностью данных.

следующие функции полезности создания набора данных N x N точек и разбить его в кластерах одинакового размера

def gen_data(n): 
    return [[x, y] for x in range(n) for y in range(n)] 

def gen_clusters(data, c_size): 
    g = [iter(data)]*c_size 
    return [list(c) for c in zip(*g)] 

И эти два решения:

def ck_pynchia(data, clusters): 
    cd = dict((tuple(p), i) for i, cl in enumerate(clusters) for p in cl) 
    output = [cd[tuple(p)] for p in data] 
    return output 

def ck_b2b(data, clusters): 
    gen = (count for count, y in enumerate(clusters) for x in data if x in y) 
    output = list(gen) 
    return output 

Теперь пришло время их

с набором данных 10 * 10 точек

python3 -mtimeit 'import clusters as cl; data = cl.gen_data(10); clusters = cl.gen_clusters(data, 10); cl.ck_pynchia(data,clusters)' 
10000 loops, best of 3: 73.2 usec per loop 

python3 -mtimeit 'import clusters as cl; data = cl.gen_data(10); clusters = cl.gen_clusters(data, 10); cl.ck_b2b(data,clusters)' 
1000 loops, best of 3: 330 usec per loop 

с набором данных 50 * 50 точек

python3 -mtimeit 'import clusters as cl; data = cl.gen_data(50); clusters = cl.gen_clusters(data, 50); cl.ck_pynchia(data,clusters)' 
1000 loops, best of 3: 1.59 msec per loop 

python3 -mtimeit 'import clusters as cl; data = cl.gen_data(50); clusters = cl.gen_clusters(data, 50); cl.ck_b2b(data,clusters)' 
10 loops, best of 3: 177 msec per loop 

с набором данных 100 * 100 точек

python3 -mtimeit 'import clusters as cl; data = cl.gen_data(100); clusters = cl.gen_clusters(data, 100); cl.ck_pynchia(data,clusters)' 
100 loops, best of 3: 6.37 msec per loop 

python3 -mtimeit 'import clusters as cl; data = cl.gen_data(100); clusters = cl.gen_clusters(data, 100); cl.ck_b2b(data,clusters)' 
10 loops, best of 3: 2.82 sec per loop 

Как мы можем видеть, вычислительная сложность двух алгоритмов довольно другой.

Конечная нота: если бы вы могли держать точки в кортеже, а не список, все было бы немного проще и быстрее:

data = [(10,10),(20,20),(5,3),(7,2),(90,78)] 
clusters = [[(10,10), (20,20)], [(5,3), (7,2), (90,78)]] 

cd = dict((p,i) for i, cl in enumerate(clusters) for p in cl) 
output = [cd[p] for p in data] # output = list(map(lambda p: cd[p], data)) 

Answer 3

Вы могли бы сделать это с постижениями:

[idx for d in data for (c, idx) in zip(clusters, range(len(clusters))) if d in c]

Если вы настаиваете на использовании функции карты, вы можете сделать что-то вроде этого:

list(
    map(lambda tup: tup.index(True), 
     map(lambda d: list(map(lambda c: d in c, clusters)), data) 
    ) 
) 

Внутренняя карта создает список списков: для каждого элемента данных есть список значений True или False, показывающих, содержится ли он в соответствующем кластере.

[[True, False], [True, False], [False, True], [False, True], [False, True]] 

Внешняя карта дает индекс первого вхождения Правда во внутренних списках, что случается индекс кластера этого элемента данных.