Нахождение «горячие точки» в одномерном списке в Python

Question

Учитывая список пара одномерных координат (или сегментов), как следующее:

[1]: 1200, 1210 
[2]: 1212, 1222 
[3]: 1190, 1200 
[4]: 300, 310 
... 
[n]: 800, 810 

(где вы можете взять центр каждой пару для представления каждого элемента) Я хочу знать, какой алгоритм или какой алгоритм я могу использовать, чтобы найти «горячие точки» или кластеры.

Точка доступа представляет собой сегмент, содержащий определенное количество элементов в нем (допустим, k).

Например, [3], [1] и [2] будет принадлежать к той же группе, и полученный список будет что-то вроде:

[1']: 1190, 1222 ([1], [2], [3]) 

(начала, конца, содержащиеся элементы)

Answer 1

Проблема на самом деле не определена, но, возможно, это поможет вам.

KMeans - это способ группировки предметов по расстоянию. Scikit-learn имеет реализацию, которая довольно проста в использовании. См. Пример http://scikit-learn.org/stable/auto_examples/cluster/plot_kmeans_digits.html#example-cluster-plot-kmeans-digits-py.

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

from sklearn.cluster import KMeans 

data = [[1200, 1210], [1212, 1222], [1190, 1200], [300, 310], [800, 810]] 
centers = [[sum(x)/len(x)] for x in data] 

clf = KMeans(n_clusters=3) 

clf.fit(centers) 

for points in data: 
    center = sum(points)/len(points) 
    print points, center, clf.predict([center]) 

Выход:

[1200, 1210] 1205 [1]

[1212, 1222] 1217 [1]

[1190, 1200 ] 1195 [1]

[300, 310] 305 [0]

[800, 810] 805 [2]

EDIT: Еще один алгоритм, предоставляемый в SKLearn, - это Affinity Propagation, который не требует, чтобы количество кластеров было задано перед рукой. Я не знаю, как это работает, но вы можете найти информацию об этом самостоятельно.

Пример:

from sklearn.cluster import AffinityPropagation 
import numpy as np 

data = [[1200, 1210], [1212, 1222], [1190, 1200], [300, 310], [800, 810]] 
centers = np.array([[sum(x)/len(x)] for x in data]) 

clf = AffinityPropagation() 


for (points, cluster) in zip(data, clf.fit_predict(centers)): 
    center = sum(points)/len(points) 
    print points, center, cluster 

Выход:

[1200, 1210] 1205 0

[1212, 1222] 1217 0

[1190, 1200] 1 195 0

[300, 310] 305 1

[800, 810] 805 2