Làm thế nào để giữ một biểu đồ động?

Question

có một thuật toán đã biết + cấu trúc dữ liệu để duy trì một biểu đồ động không?

Hãy tưởng tượng tôi có luồng dữ liệu (x_1, w_1), (x_2, w_2), ... trong đó x_t tăng gấp đôi, đại diện cho một số biến được đo và w_t là trọng số liên quan.

tôi chỉ có thể làm (mã pseudo-python) rõ ràng:

x0,xN = 0, 10 
numbins = 100 
hist = [(x0 + i * delta , 0) for i in xrange(numbins)] 
def updateHistogram(x, w): 
    k = lookup(x, hist) #find the adequated bin where to put x 
    hist[k][1] += 1 

Nhưng tôi có một số vấn đề với điều đó khi tôi có một dòng liên tục của dữ liệu. Tôi không có tập dữ liệu đầy đủ trong tay và tôi phải kiểm tra biểu đồ ở giữa thu thập dữ liệu. Và tôi không có kỳ vọng về:

• kích thước bin lý tưởng cho không kết thúc với rất nhiều thùng rỗng,
• phạm vi của dữ liệu

Vì vậy, tôi muốn xác định thùng tự động. Tôi có thể làm điều ngu ngốc:

for x in data_stream: 
     data.append(x) 
     hist = make_histogram(data) 

nhưng tôi đoán đây sẽ được làm chậm rất nhanh chóng ...

Nếu tất cả các trọng nơi bằng một trong những điều tôi nghĩ đã được lưu trữ dữ liệu trong một mảng được sắp xếp và chèn dữ liệu mới theo cách giữ cho mảng được sắp xếp. Bằng cách này, tôi có thể có:

data = sortedarray(); 
for x in data_stream: 
    data.insert(x) 
    bins = [ data[int(i * data.size()/numbins)] for i in xrange(numbins)] 

và số bên trong mỗi thùng sẽ bằng với dữ liệu.size()/numbins cho tất cả các thùng.

Tôi không thể nghĩ ra một cách để bao gồm trọng số trong này mặc dù ... có ai có đề xuất không? (kiến thức về thư viện C++ làm điều này cũng sẽ được hoan nghênh).

CHỈNH SỬA: (để được giải thích rõ)

X_t là số dấu phẩy động. Để tính toán biểu đồ, tôi phải chia phạm vi liên tục trong đó x thuộc về một số thùng. Vì vậy, tôi sẽ có một chuỗi số bin [0], bin [1], v.v ... vì vậy tôi phải xác định những gì tôi làm bin [i] < x < bin [i + 1].

Đây là cách bạn thường làm biểu đồ khi bạn có tất cả dữ liệu trước. Sau đó, bạn sẽ biết giới hạn tối đa (x) và min (x) và sẽ dễ dàng xác định các thùng đầy đủ. Bạn có thể có chúng khoảng cách bằng nhau giữa min (x) và max (x), ví dụ.

Nếu bạn không biết phạm vi trước, bạn không thể xác định các thùng. Bạn có thể nhận được một x mà không rơi vào bất kỳ thùng. Hoặc bạn có thể có nhiều thùng rỗng khiến bạn chọn một phạm vi quá lớn để tạo ra các thùng.

Answer 1

Làm thế nào để xác định số lượng thùng

Có một số quy tắc để xác định number of bins trong một biểu đồ.Đối với vấn đề của bạn, tôi sẽ đi với sự lựa chọn của Scott:

bin_width = 3.5*sd*n^{-1/3} 

nơi sd là độ lệch chuẩn và n là số điểm dữ liệu. Quan trọng, bạn có thể sử dụng thuật toán online để tính toán độ lệch chuẩn. Số lượng thùng, k, được cho bởi:

k = ceil((max(x) - min(x))/bin_width) 

lưu trữ dữ liệu

Giả sử chúng ta đã quan sát N điểm dữ liệu. Sau đó, khoảng tin cậy cho độ lệch chuẩn,

Lower limit: sd*sqrt((N-1)/CHIINV((alpha/2), N-1)) 
Upper limit: sd*sqrt((N-1)/CHIINV(1-(alpha/2), N-1)) 

trong đó CHIINV là giá trị từ phân phối chi bình phương. Khi N = 1000, TCTD cho sd là:

(0.96*sd, 1.05*sd) 

và do đó, một CI 95% thùng-width là:

(3.5*0.96*sd*1000^{-1/3}, 3.5*1.05*sd*1000^{-1/3}) 
(0.336*sd, 0.3675*sd) 

Bạn có thể nhận được một cái gì đó tương tự cho số lượng thùng.

Algorithm

1. Lưu trữ tất cả các dữ liệu cho đến khi bạn có một tốt ước tính của bin-width tối ưu, nói khi CI thấp hơn và trên cho số lượng thùng đều bình đẳng.
2. Tạo số lượng thùng và đặt dữ liệu vào thùng.
3. Tất cả các điểm dữ liệu mới được đưa vào thùng, sau đó bị loại bỏ.

Comments

1. quy tắc Các Freedman-Diaconis' là tốt hơn cho việc lựa chọn số lượng thùng, nhưng nó liên quan đến phạm vi liên quantile đó là khó khăn hơn một chút tính toán trực tuyến.
2. Về mặt kỹ thuật, khoảng CI không chính xác khi dữ liệu được tuần tự. Nhưng nếu bạn đặt số điểm dữ liệu tối thiểu hợp lý để quan sát, hãy nói ~ 100 hoặc 1000, bạn sẽ không sao.
3. Điều này giả định tất cả dữ liệu đều theo cùng một phân phối.
4. Số lượng thùng phụ thuộc vào n^{- 1/3}. Nếu bạn biết khoảng bao nhiêu điểm mong đợi, tức là 10^5, 10^6 hoặc 10^7, thì bạn có thể tạo các thùng nhỏ hơn với hy vọng thay đổi chiều rộng thùng trong tương lai.

Answer 2

ROOT là công cụ được các nhà vật lý hạt sử dụng cho loại công việc này ... và nó đi kèm với các ràng buộc python. Tâm trí bạn, nó không phải là một phần mềm nhẹ.

Trong C++ bạn sẽ làm điều gì đó như

TH1D hist("hist","longer title for hist",numbins,lowlimit,highimit); 

... 

for (int i=0; i<num; ++i){ 
    hist.Fill(x[i],w[i]); 
} 

... 

hist.Draw(); 

---

ROOT không cung cấp tích hợp giải pháp cho vấn đề di chuyển chuột, đầu vào bên dưới/trên phạm vi binned được thêm vào under-/quá dòng thùng.

Ban đầu, bạn có thể đặt chế độ ăn trên một phạm vi rộng và chuyển đổi thành phạm vi ngắn hơn sau đó. Tôi nghĩ phương pháp là Rebin. Tất cả các giới hạn rõ ràng được áp dụng.

Answer 3

Tôi có một số kinh nghiệm với bảng tần số và biểu đồ. Bạn chỉ cần các giá trị nhỏ nhất và tối đa để quyết định chiều rộng thùng rác tốt đẹp. Vì vậy, trong trường hợp dữ liệu lớn, bạn đã biết các giá trị có thể có của min và max. và do đó dễ dàng tính toán độ rộng của thùng trước, trước khi dữ liệu được truyền trực tuyến.

Là một phần của dữ liệu đang đến, bạn chỉ có thể cập nhật các thùng cần thiết theo từng khu vực thùng và hiển thị biểu đồ.

Answer 4

Có vẻ như bạn muốn thực hiện loại dữ liệu trừu tượng sau.

insert(x, w): add item x to the collection with weight x 
select(p): return the item greater than a p weighted fraction of the items 

Ví dụ, select(0) trả mức tối thiểu, select(0.5) trả về trung bình có trọng số, và select(1) trả mức tối đa.

Tôi sẽ triển khai ADT này theo một trong hai cách. Nếu lựa chọn là không thường xuyên, tôi sẽ đặt dữ liệu trong một mảng và sử dụng một thuật toán lựa chọn tuyến tính-thời gian, cho O (1) thời gian chèn và O (n) -time chọn. Nếu lựa chọn là thường xuyên, tôi sẽ sử dụng một cây tìm kiếm nhị phân, nơi mỗi nút lưu trữ tổng trọng lượng trong cây con của nó. Ví dụ, sau

insert(2, 10) 
insert(1, 5) 
insert(3, 100) 
insert(4, 20) 

cây có thể trông như

2 (135) 
/\ 
/ \ 
1 (5) 4 (120) 
    /
    /
    3 (100) 

Bây giờ, để tìm ra trung bình có trọng số, nhân 135 bởi 0.5 và nhận 67.5 là "chỉ số" mong muốn. Bắt đầu từ gốc 2, chúng tôi thấy rằng 5 nhỏ hơn 67.5, vì vậy mục không nằm trong nhánh trái và chúng tôi trừ 5 để lấy được 62.5, chỉ mục vào phần còn lại của cây. Kể từ 135 - 120 = 15 nhỏ hơn 62.5, trung vị không phải là 2. Chúng tôi trừ 15 từ 62.5 để nhận được 47.5 và hạ xuống 4. Tại 4, chúng tôi thấy rằng 100 lớn hơn 47.5, vì vậy 3 là trung vị.

Giả sử một cây cân bằng, thời gian chạy của cả hai số insert và select là O(log n). Nếu tôi đã thực hiện từ đầu, tôi có thể lựa chọn không cho một cây splay.