Консенсус / Кластер набор списков переменной длины в Python? - PullRequest
Новая
       1

Консенсус / Кластер набор списков переменной длины в Python?

1 голос
/ 13 марта 2020

У меня есть набор датчиков, измеряющих некоторые временные данные. В любой момент времени датчик выдает либо 0, либо 1. Датчик никогда не выдаст два 1 с последовательно.

Как мы можем найти наилучшую оценку, учитывая доступные датчики?

Например, скажем, четыре датчика вывели 1 при этих предоставленных показателях. 

A = [ 178,  511,  843, 1180, 1512, 1733]
B = [ 514,  846, 1182, 1515, 1736, 1937]
C = [ 182,  516,  848, 1517, 1738, 1939]
D = [ 179,  513,  845, 1181, 1513, 1735, 1936, 2124]

Из визуального осмотра я вижу, что:

  • A потерял значение в конце списка
  • B потерял значение в голове списка
  • C потерял значение в середине списка
  • D имеет дополнительное значение в конце списка 
# the None locations are not known to the consensus algorithm
a = [  178,  511,  843, 1180, 1512, 1733, None]
b = [ None,  514,  846, 1182, 1515, 1736, 1937]
c = [  182,  516,  848, None, 1517, 1738, 1939]
d = [  179,  513,  845, 1181, 1513, 1735, 1936] # 2124 removed

# Consensus: Average over columns with `None` removed
# rounded to the nearest integer
s = consensus((A,B,C,D))
s = [  180,  514,  849, 1181, 1514, 1736, 1937]

Если бы у нас было два дополнительных датчика E и F со следующими значениями: 

E = [ 2130 ]
F = [ 2121 ]
# these two sensors only have the one tail value
# therefore sensor D's extra reading is now part of consensus.
# All other values are unchanged.
s = consensus((A,B,C,D,E,F))
s = [  180,  514,  849, 1181, 1514, 1736, 1937, 2125]

Есть ли решение для этой проблемы, которое не является O (n ^ 2)?

1 Ответ

1 голос
/ 13 марта 2020

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

РЕДАКТИРОВАТЬ: Я не решаюсь отметить это как окончательный ответ, поскольку мы теряем информацию о том, что каждый датчик уникален, когда мы объединяем все показания в один массив. Также я думаю, что можно использовать итеративный или динамический c подход к программированию, отслеживающий расстояние до ближайшего значения для каждого датчика. 

from matplotlib import pyplot as plt
from sklearn.neighbors import KernelDensity
from scipy.signal import find_peaks

concat = A + B + C + D
X = np.array(concat)[:, np.newaxis]

X_plot = np.linspace(0, 1.1 * X.max(), 1000)[:, np.newaxis]

kde = KernelDensity(bandwidth=2).fit(X)
log_dens = kde.score_samples(X_plot)
dens = np.exp(log_dens)
peaks, _ = find_peaks(dens)

plt.plot(X_plot[:, 0], dens)
plt.plot(X_plot[peaks], dens[peaks], "X")
plt.show()

print(tuple(int(i) for i in X_plot[peaks].squeeze()))
# (180, 514, 846, 1181, 1513, 1735, 1936, 2123)

Consensus plotted

...