《海量数据挖掘-王永利》ch04-streams2.pptVIP

* J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, 0thmoment = number of distinct elements The problem just considered 1st moment = count of the numbers of elements = length of the stream Easy to compute 2nd moment = surprise number S = a measure of how uneven the distribution is * J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * [Alon, Matias, and Szegedy] J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * Time t when the last i is seen (ct=1) Time t when the penultimate i is seen (ct=2) Time t when the first i is seen (ct=mi) Group times by the value seen a a a a 1 3 2 ma b b b b Count: Stream: mi … total count of item i in the stream (we are assuming stream has length n) J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * a a a a 1 3 2 ma b b b b Stream: Count: J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * * J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, (1) The variables X have n as a factor – keep n separately; just hold the count in X (2) Suppose we can only store k counts. We must throw some Xs out as time goes on: Objective: Each starting time t is selected with probability k/n Solution: (fixed-size sampling!) Choose the first k times for k variables When the nth element arrives (n k), choose it with probability k/n If you choose it, throw one of the previously stored variables X out, with equal probability J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * New Problem: Given a stream, which items appear more than s times in the window? Possible solution: Think of the