Given: E-a set of data events k-the number of clusters LEF- the clustering quality criterion Choose initial“seedevents from Determine a star for each seed against the other seed events By appropriately modifying and selecting complexes from stars, construct a disjoint cover of E that optimizes the criterion LEF Y Is the termination END Criterion satisfied? N
Choose initial “seed” events from E Determine a star for each seed against the other seed events By appropriately modifying and selecting complexes from stars, construct a disjoint cover of E that optimizes the criterion LEF Is the termination Criterion satisfied? END a Given: E-a set of data events k-the number of clusters LEFthe clustering quality criterion Y N
Is the clustering quality improving Y Choose k new seeds which Choose k new seeds which Are central events are“ border' events a
Is the clustering quality improving? Choose k new seeds which Are central events Choose k new seeds which are “border” events a Y N
XI X2 e abcabc e3 4 e5 e6 2 ab e7 e 8 ce9 e10 20120 X4 X3
a b c e3 a e4 b c e5 a e6 b e7 e8 c e9 e10 0 1 2 0 1 2 0 1 2 e1 e2 X1 X2 0 1 2 X4 0 1 2 X3
Event Ⅹ2 X3 Ⅹ4 e2 000 00101 022 5 6 e e ee 89 22222 abcacabbcc 0102 01202 e 0
Event X1 X2 X3 X4 e1 0 a 0 1 e2 0 b 0 0 e3 0 c 1 2 e4 1 a 0 2 e5 1 c 1 1 e6 2 a 1 0 e7 2 b 0 1 e8 2 b 1 2 e9 2 c 0 0 e10 2 c 2 2
f K=2; LEF-Sparseness, Complexity, Termination criterion: base=2. probe=2 Iteration 1 Step I Select seed ele2 Step 2 Produce Stars: RG(ele2m)RG(e2el,m)m=5 RG(ell2,m)={[x2=ax3=0V1][X4=1V2]} RG(e2el, m=x2=b Vcl[x4=0 V2)
d f a b c K=2 ; LEF-sparseness, Complexity; Termination criterion:base=2,probe=2 Iteration 1 Step 1: Select seed: e1,e2 Step 2: Produce Stars: RG(e1|e2,m) RG(e2|e1,m) m=5 RG(e1|e2,m)={[x2=a][x3=0∨1],[X4=1 ∨2]} RG(e2|e1,m)={[x2=b ∨c],[x4=0 ∨2]}
Generalize RG(ele2, m=X2=a [X3=1l[X4=1) RG(e2ll,m)={[x2=fx4=0V2]} Step 3 Evaluation and Modification( disjoint Sparseness Complexity (a) Complex 1 [X2-a[X3=1] 15 Complex 2: [X2=f 47 62 (b)Complex 1: x4=1V2 Complex 2: [X2-f (c)Complex 1: X2=a X31] Complex 2: [X4=0V2
Generalize: RG(e1|e2,m)={[x2=a][x3≦1],[X4=1∨2]} RG(e2|e1,m)={[x2=f],[x4=0∨2]} Step 3: Evaluation and Modification(disjoint) Sparseness Complexity (a) Complex 1: [x2=a][x3≦1] 15 2 Complex 2: [x2=f] 47 1 62 3 (b) Complex 1: [x4=1∨2] Complex 2: [X2=f] (c) Complex 1: [x2=a][x3≦1] Complex 2: [X4=0∨2]
(d)Complex 1: [x4=1V2 Complex 2: [x4=0V2 Step 4 The termination criterion is tested Step 5: select new seeds el,e4,e6}{e2,e3,e5e7e8,e9,10} Central events e4 e8 Iteration 2 Step 2 Produce satrs RG(e4e&, m),RG(e8e4, m) RG(e4le8,m)={x2=a]x31]x11x31][x3=0]} RG(e8e4,m){x1=2x2][x3三1}
(d) Complex 1: [x4=1∨2] Complex 2: [x4=0∨2] Step 4: The termination criterion is tested Step 5:select new seeds {e1,e4,e6} {e2,e3,e5,e7,e8,e9,e10} Central events: e4,e8 Iteration 2 Step 2: Produce satrs RG(e4|e8,m ), RG(e8|e4,m) RG(e4|e8,m)={[x2=a][x3≦1],[x1≦1][x3 ≦1],[x3=0]} RG(e8|e4,m)={[x1=2],[x2=f],[x3≧1]}
sparseness Complexity Complex 1:[xl≤lx3≤1 31 2 Complex 2: x1=2 22 53 Step 4 Termination criterion is tested(the last of the base iterations Step 5 el,e2,e3,e4e5}{e6,e7e8,e9,10} New seeds: el e8 Iteration 3 The iteration produces the same clustering as iteration Step 4: Termination criterion is tested(the first of the two probe Stp 5: not better than the previous one, border events are selected
sparseness Complexity Complex 1: [x1≤1][x3≤1] 31 2 Complex 2: [x1=2] 22 1 53 3 Step 4: Termination criterion is tested (the last of the base iterations) Step 5: {e1,e2,e3,e4,e5} {e6,e7,e8,e9,e10} New seeds: e1,e8 Iteration 3 The iteration produces the same clustering as iteration1 Step 4: Termination criterion is tested (the first of the two probe Stp 5: not better than the previous one, border events are selected
New seeds e2. e6 Iteration 4 Produces a new clustering Sparseness Complexity Complex 1: x3>1] 49 Complex 2: [ X3=0 22 结果 x1≤lx3≤1 x1=2]
New seeds e2,e6 Iteration 4 Produces a new clustering: Sparseness Complexity Complex 1: [x3≥1] 49 1 Complex 2: [x3=0] 22 1 71 2 结果： [x1≤1][x3 ≤1] [x1=2]
XI X2 e abcab cab 6 2 eg 20120 X4 X3
a b c e3 a e4 b c e5 a e6 b e7 e8 c e9 e10 0 1 2 0 1 2 0 1 2 e1 e2 X1 X2 0 1 2 X4 0 1 2 X3