Làm thế nào bạn nhóm/cụm ba khu vực trong mảng trong python?

Question

Vì vậy, bạn có một mảng

1 
2 
3 
60 
70 
80 
100 
220 
230 
250 

Đối với một sự hiểu biết tốt hơn:

Làm thế nào bạn nhóm/cụm ba lĩnh vực trong mảng trong python (v2.6), do đó bạn sẽ có được ba mảng trong trường hợp này có chứa

[1 2 3] [60 70 80 100] [220 230 250]

Bối cảnh:

trục y là tần số, trục x là số. Những con số này là mười biên độ cao nhất được thể hiện bằng tần số của chúng. Tôi muốn tạo ra ba số rời rạc từ chúng để nhận dạng mẫu. Có thể có nhiều điểm hơn nhưng tất cả chúng đều được nhóm lại bởi sự chênh lệch tần số tương đối lớn như bạn có thể thấy trong ví dụ này giữa khoảng 50 và khoảng 0 và giữa khoảng 100 và khoảng 220. Lưu ý rằng những gì lớn và thay đổi nhỏ là gì sự khác biệt giữa các cụm vẫn còn đáng kể so với sự khác biệt giữa các phần tử của một nhóm/cụm.

Answer 1

Đây là một thuật toán đơn giản thực hiện trong python mà kiểm tra có hay không một giá trị là quá xa (về độ lệch chuẩn) từ giá trị trung bình của một cụm:

from math import sqrt 

def stat(lst): 
    """Calculate mean and std deviation from the input list.""" 
    n = float(len(lst)) 
    mean = sum(lst)/n 
    stdev = sqrt((sum(x*x for x in lst)/n) - (mean * mean)) 
    return mean, stdev 

def parse(lst, n): 
    cluster = [] 
    for i in lst: 
     if len(cluster) <= 1: # the first two values are going directly in 
      cluster.append(i) 
      continue 

     mean,stdev = stat(cluster) 
     if abs(mean - i) > n * stdev: # check the "distance" 
      yield cluster 
      cluster[:] = [] # reset cluster to the empty list 

     cluster.append(i) 
    yield cluster   # yield the last cluster 

này sẽ trả lại những gì bạn mong đợi trong ví dụ của bạn với 5 < n < 9:

>>> array = [1, 2, 3, 60, 70, 80, 100, 220, 230, 250] 
>>> for cluster in parse(array, 7): 
...  print(cluster) 
[1, 2, 3] 
[60, 70, 80, 100] 
[220, 230, 250] 

Answer 2

Tôi cho rằng bạn muốn có một thuật toán khá đơn giản nhưng đơn giản ở đây.

Nếu bạn biết bạn muốn N cụm, thì bạn có thể lấy sự khác biệt (deltas) giữa các thành viên liên tiếp của danh sách nhập (sắp xếp). Ví dụ. in numpy:

deltas = diff(sorted(input)) 

Sau đó, bạn có thể đặt cuttoff nơi bạn tìm thấy sự khác biệt lớn nhất N-2.

Mọi thứ trở nên phức tạp hơn nếu bạn không biết N là gì. Ở đây bạn có thể đặt các cuttoff bất cứ khi nào bạn nhìn thấy một đồng bằng lớn hơn một kích thước nhất định. Sau đó, thông số này sẽ là thông số được điều chỉnh bằng tay, không tuyệt vời nhưng có thể đủ tốt cho bạn.

Answer 3

Bạn có thể sử dụng nhóm lân cận gần nhất. Đối với một điểm thuộc về một trong các cụm, hàng xóm gần nhất của nó cũng phải thuộc về cụm. Với trường hợp bạn đã hiển thị, bạn chỉ cần lặp lại dọc theo trục x và so sánh sự khác biệt với các điểm liền kề. Khi sự khác biệt với điểm trước đó lớn hơn sự khác biệt cho điểm tiếp theo, nó cho biết sự bắt đầu của một cụm mới.

Answer 4

Quan sát các điểm dữ liệu của bạn là thực sự một chiều nếu x chỉ đại diện cho một chỉ mục. Bạn có thể phân cụm các điểm của mình bằng mô-đun cluster.vq của Scipy, thực hiện thuật toán k.

>>> import numpy as np 
>>> from scipy.cluster.vq import kmeans, vq 
>>> y = np.array([1,2,3,60,70,80,100,220,230,250]) 
>>> codebook, _ = kmeans(y, 3) # three clusters 
>>> cluster_indices, _ = vq(y, codebook) 
>>> cluster_indices 
array([1, 1, 1, 0, 0, 0, 0, 2, 2, 2]) 

Kết quả có nghĩa là: người đầu tiên ba điểm hình thức cụm 1 (một nhãn tùy ý), trong bốn hình thức cụm 0 và ba cuối cùng hình thức cụm 2. Nhóm các điểm gốc theo các chỉ số còn lại như một bài tập cho người đọc.

Để biết thêm các thuật toán phân cụm trong Python, hãy xem scikit-learn.

Answer 5

Bạn có thể giải quyết vấn đề này theo nhiều cách khác nhau. Một trong những điều hiển nhiên khi bạn ném từ khóa "clustering" là sử dụng kmeans (xem các trả lời khác).

Tuy nhiên, trước tiên bạn có thể muốn hiểu rõ hơn về những gì bạn đang thực sự làm hoặc đang cố gắng làm. Thay vì chỉ ném một hàm ngẫu nhiên vào dữ liệu của bạn.

Theo như tôi có thể kể từ câu hỏi của bạn, bạn có một số giá trị 1 chiều và bạn muốn tách chúng thành số không rõ, phải không? Vâng, k-có nghĩa là có thể làm các thủ thuật, nhưng trên thực tế, bạn chỉ có thể tìm kiếm sự khác biệt lớn nhất trong tập dữ liệu của bạn sau đó là k. I.e. đối với bất kỳ chỉ mục nào i > 0, hãy tính k[i] - k[i-1] và chọn các chỉ mục k nơi số này lớn hơn số còn lại. Rất có thể, kết quả của bạn thực sự sẽ là tốt hơn và nhanh hơn sử dụng k-means.

Trong mã python:

k = 2 
a = [1, 2, 3, 60, 70, 80, 100, 220, 230, 250] 
a.sort() 
b=[] # A *heap* would be faster 
for i in range(1, len(a)): 
    b.append((a[i]-a[i-1], i)) 
b.sort() 
# b now is [... (20, 6), (20, 9), (57, 3), (120, 7)] 
# and the last ones are the best split points. 
b = map(lambda p: p[1], b[-k:]) 
b.sort() 
# b now is: [3, 7] 
b.insert(0, 0) 
b.append(len(a) + 1) 
for i in range(1, len(b)): 
    print a[b[i-1]:b[i]], 
# Prints [1, 2, 3] [60, 70, 80, 100] [220, 230, 250] 

(Đây btw có thể được coi là một đơn giản đơn liên kết clustering.!)

Một phương pháp tiên tiến hơn, mà thực sự được thoát khỏi những tham số k, tính độ lệch trung bình và chuẩn của b[*][1] và chia tách cho dù giá trị lớn hơn số mean+2*stddev. Tuy nhiên đây là một heuristic khá thô. Một tùy chọn khác sẽ thực sự giả định phân phối giá trị chẳng hạn như k phân phối bình thường và sau đó sử dụng ví dụ: Levenberg-Marquardt để phù hợp với các bản phân phối cho dữ liệu của bạn.

Nhưng đó thực sự là điều bạn muốn làm?

Trước tiên, hãy xác định nội dung phải là cụm và số không. Phần thứ hai quan trọng hơn nhiều.