价值百万的it技术知识bi数据挖掘families

1、Mining of Massive DatasetsLeskovec, Rajaraman, and UllmanStanford University¡ For cosine distance, there is a techniqueanalogous to minhashing for generating a (d1,d2,(1-d1/180),(1-d2/180)-sensitive family for any d1 and d2.¡ Called random hyperplanes.20¡ Each vector v determines a ha

2、sh function hvwith two buckets.¡ hv(x) = +1 if v.x > 0; = -1 if v.x < 0.¡ LS-family H = set of all functions derived fromany vector.¡ Claim: Probh(x)=h(y) = 1 (angle between xand y divided by 180).21vLook in theplane of xand y.xHyperplanes(normal to v )for which h(x) h(y)yProbRe

3、d case= /180Hyperplanesfor whichh(x) = h(y)22¡ Pick somber of vectors, and hash yourdata for each vector.¡ The result is a signature (sketch) of +1s and1s that can be used for LSH like theminhash signatures for Jaccard distance.¡ But you dont have to think this way.¡ The existenc

4、e of the LSH-family is sufficient for amplification by AND/OR.23¡ We need not pick from among all possiblevectors vto form a component of a sketch.¡ It suffices to consider only vectors vof +1 and 1 components.consisting24¡ Simple idea: hash functions correspond to lines.¡ Partit

5、ion the line into buckets of size a.¡ Hash each point to the bucket containing its projection onto the line.¡ Nearby points are alwaysare rarely in same bucket.; distant points25Points atdistance dIf d << a, thenthe chance the points are in the same bucket isIf d >> a, mustto 9

6、0obefor there to beany chance points go to the same bucket.at least 1 d/a.d cos Randomlychosen lineBucketwidth a26¡ If points are distance > 2a apart, then60 < < 90 for there to be a chance that the points go in the same bucket.§ I.e., at most 1/3 probability.¡ If points are

7、distance < a/2, then there is at least ½ chance they share a bucket.¡ Yields a (a/2, 2a, 1/2, 1/3)-sensitive family of hash functions.27¡ For previous distance measures, we could startwith a (d, e, p, q)-sensitive family for any d < e,and drive pand qto 1 and 0 by AND/ORconstructions.¡ Here, we seem to need e > 4d.28¡ But as long as d < e, the probability of points atdistance d falling in the same bucket is greater than the probability of points at distance e doi