Raggruppamento/clustering di numeri in Python

Question

Ho cercato su Google, ho provato e questo mi ha messo alla prova. Ho una lista di numeri che ho bisogno di raggruppare per similarità. Ad esempio, in una lista di [1, 6, 9, 100, 102, 105, 109, 134, 139], 1 6 9 verrebbe inserito in una lista, 100, 102, 105 e 109 verrebbero inseriti in una lista lista, e 134 e 139. Sono terribile in matematica, e ho provato e provato questo, ma non riesco a farlo funzionare. Per essere il più esplicito possibile, desidero raggruppare i numeri che si trovano entro 10 valori l'uno dall'altro. Qualcuno può aiutare? Grazie.

Answer 1

Ci sono molti modi per fare cluster analysis. Un approccio semplice è quello di esaminare il formato divario tra elementi successivi di dati:

def cluster(data, maxgap): 
    '''Arrange data into groups where successive elements 
     differ by no more than *maxgap* 

     >>> cluster([1, 6, 9, 100, 102, 105, 109, 134, 139], maxgap=10) 
     [[1, 6, 9], [100, 102, 105, 109], [134, 139]] 

     >>> cluster([1, 6, 9, 99, 100, 102, 105, 134, 139, 141], maxgap=10) 
     [[1, 6, 9], [99, 100, 102, 105], [134, 139, 141]] 

    ''' 
    data.sort() 
    groups = [[data[0]]] 
    for x in data[1:]: 
     if abs(x - groups[-1][-1]) <= maxgap: 
      groups[-1].append(x) 
     else: 
      groups.append([x]) 
    return groups 

if __name__ == '__main__': 
    import doctest 
    print(doctest.testmod()) 

Answer 2

Questo troveranno i gruppi:

nums = [1, 6, 9, 100, 102, 105, 109, 134, 139] 
for k, g in itertools.groupby(nums, key=lambda n: n//10): 
    print k, list(g) 

0 [1, 6, 9] 
10 [100, 102, 105, 109] 
13 [134, 139] 

Si noti che se non viene effettivamente nums ordinati come i tuoi programmi di esempio, è necessario risolvere la prima.

Answer 3

primo luogo, si può facilmente convertire qualsiasi sequenza in una sequenza di coppie di elementi adiacenti. Basta collegarlo, spostarlo in avanti e comprimere le copie non spostate e non spostate. L'unico accorgimento è che è necessario iniziare con (<something>, 1) o (139, <something>), perché in questo caso non vogliamo ciascuna coppia di elementi, ma un paio per ogni elemento:

def pairify(it): 
    it0, it1 = itertools.tee(it, 2) 
    first = next(it0) 
    return zip(itertools.chain([first, first], it0), it1) 

(questo non è il modo più semplice per scriverlo, ma credo che questo può essere il modo che è più leggibile per le persone che non hanno familiarità con itertools.)

>>> a = [1, 6, 9, 100, 102, 105, 109, 134, 139] 
>>> list(pairify(a)) 
[(1, 1), (1, 6), (6, 9), (9, 100), (100, 102), (102, 105), (105, 109), (109, 134), (134, 139)] 

Poi, con una versione leggermente più complicata della chiave di Ned Batchelder, si può semplicemente utilizzare groupby .

Tuttavia, penso che in questo caso finirà per essere più complicato di un generatore esplicito che fa la stessa cosa.

def cluster(sequence, maxgap): 
    batch = [] 
    for prev, val in pairify(sequence): 
     if val - prev >= maxgap: 
      yield batch 
      batch = [] 
     else: 
      batch.append(val) 
    if batch: 
     yield batch