《海量数据挖掘-王永利》ch10-graphs1.pptVIP

Approximates the optimal cut [Shi-Malik, ’00] Can be used to approximate optimal k-way normalized cut Emphasizes cohesive clusters Increases the unevenness in the distribution of the data Associations between similar points are amplified, associations between dissimilar points are attenuated The data begins to “approximate a clustering” Well-separated space Transforms data to a new “embedded space”, consisting of k orthogonal basis vectors Multiple eigenvectors prevent instability due to information loss J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * Searching for small communities in the Web graph What is the signature of a community / discussion in a Web graph? [Kumar et al. ‘99] Dense 2-layer graph Intuition: Many people all talking about the same things … … … Use this to define “topics”: What the same people on the left talk about on the right Remember HITS! J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * A more well-defined problem:Enumerate complete bipartite subgraphs Ks,t Where Ks,t : s nodes on the “left” where each links to the same t other nodes on the “right” K3,4 |X| = s = 3 |Y| = t = 4 X Y Fully connected J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * Market basket analysis. Setting: Market: Universe U of n items Baskets: m subsets of U: S1, S2, …, Sm ? U(Si is a set of items one person bought) Support: Frequency threshold f Goal: Find all subsets T s.t. T ? Si of at least f sets Si (items in T were bought together at least f times) What’s the connection between the itemsets and complete bipartite graphs? [Agrawal-Srikant ‘99] J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * [Kumar et al. ‘99] i b c d a Si={a,b,c,d} j i k b c d a X Y s … minimum support (|X|=s) t … itemset size (|Y|=t) J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * [Kumar et al. ‘99] i b c d a Si={a,b,c,d} x y z b c a X Y Find frequent itemsets: s … minimum suppor