Đếm thua lỗ là gì?

Question

Có ai có thể giải thích cho tôi thuật toán Đếm số tổn thất không? Đây là thuật toán phát trực tuyến về việc tìm tần suất của các mục trong luồng. Cảm ơn.

Answer 1

Giả sử bạn đang xem lưu lượng truy cập cho tiểu sử trên facebook. Bạn có hàng tỷ lượt truy cập. Bạn muốn tìm những cấu hình nào được truy cập thường xuyên nhất. Bạn có thể giữ một số đếm cho mỗi hồ sơ, nhưng sau đó bạn sẽ có một số lượng rất lớn đếm để theo dõi, phần lớn trong số đó sẽ là vô nghĩa.

Với tính toán mất dữ liệu, bạn định kỳ xóa các phần tử đếm rất thấp khỏi bảng. Các hồ sơ truy cập thường xuyên nhất sẽ hầu như không bao giờ có số lượng thấp anyway, và nếu họ đã làm, họ sẽ không có khả năng ở lại đó lâu dài.

Thuật toán về cơ bản liên quan đến việc nhóm các đầu vào thành các khối hoặc khối và đếm trong mỗi đoạn. Sau đó, bạn giảm số lượng cho từng phần tử một, giảm bất kỳ phần tử nào có số lượng giảm xuống 0.

Các tiểu sử truy cập thường xuyên nhất sẽ nhận được số của bạn và ở lại đó. Bất kỳ hồ sơ nào không được đánh rất thường xuyên sẽ giảm xuống 0 trong một vài khối và bạn sẽ không phải theo dõi chúng nữa.

Lưu ý rằng kết quả cuối cùng phụ thuộc vào thứ tự, cho trọng lượng nặng hơn cho số lượng được xử lý cuối cùng. Trong một số trường hợp, điều này làm cho cảm giác hoàn hảo và là một upside chứ không phải là một nhược điểm. (Nếu bạn muốn biết về cơ bản hồ sơ nào là phổ biến nhất bây giờ, bạn muốn cân nhắc truy cập ngày hôm nay nhiều hơn truy cập vào tháng trước.)

Có một số lượng lớn các sàng lọc cho thuật toán. Nhưng ý tưởng cơ bản là - để tìm những người chơi nặng mà không phải theo dõi mọi yếu tố, định kỳ thanh lọc số lượng của bạn về bất kỳ yếu tố nào dường như không phải là những người chơi nặng nề dựa trên dữ liệu cho đến nay.

Answer 2

Bạn có thể tìm thấy giải thích về cách tính năng Lossy Counting (và Sticky Sampling) hoạt động on this blog post và open-source version here.

Các mục được xem thường xuyên nhất "tồn tại". Cho một ngưỡng tần số f, sai số tần số e, và tổng số phần tử N, đầu ra có thể được biểu diễn như sau: Các phần tử có số đếm vượt quá fN - eN.

Trường hợp xấu nhất chúng tôi cần (1/e) * nhật ký (eN) quầy.

Ví dụ: chúng tôi có thể in các trang Facebook của những người bị trúng hơn 20%, với ngưỡng lỗi là 2% (quy tắc ngón tay cái: lỗi = 10% ngưỡng tần số).

Đối với tần số f = 20%, e = 2%, tất cả các phần tử có tần số thực vượt quá f = 20% sẽ là đầu ra - không có âm bản sai. Nhưng chúng ta thiếu. Tần số đầu ra của một phần tử có thể nhỏ hơn tần số thực của nó tối đa là 2%. Sai tích cực có thể xuất hiện với tần suất từ ​​18% - 20%. Cuối cùng, không có phần tử nào có tần suất nhỏ hơn 18% sẽ là đầu ra.

Với cửa sổ có kích thước 1/e, bên nhận bảo lãnh sau giữ:

• tần số được đánh giá thấp bởi ít nhất e * N
• Không false negative
• Sai tích cực có tần số đúng ít nhất là f N - e N