展开查看详情
1.K means ++ and K means Parallel Jun Wang
2.Review of K means Simple and fast Choose k centers randomly Class points to its nearest center Update centers
3.K means ++ Actually you are using it Spend some time on choosing k centers(seeding) Save time on clustering
4.K means ++ algorithm Seeding Choose a center from X randomly For k-1 times Sample one center each time from X with probability p Update center matrix Clustering
5.d i 2 =min( euclidean distance b/t Xi to each Ci )
6.How to choose K centers
7.Choose a point from X randomly
9.Calculate Pi D=d 1 2 +d 2 2 +d 3 2 + …+ d n 2 P i =d i 2 / D ∑P i =1 Points further away from red point have better chance to be chosen
10.Pick up point with probability p
11.Keep doing the following: Update center matrix Calculate d i 2 Calculate pi Until k centers are found
12.K means || algorithm Seeding Choose a small subset C from X Assign weight to points in C Cluster C and get k centers Clustering
13.Choose subset C from X Let D=Sum of square distance=d 1 2 +d 2 2 +d 3 2 + …+ d n 2 Let L be f(k) like 0.2k or 1.5k for ln(D) times Pick up each point in X using Bernoulli distribution P(chosen)= L *d i 2 /D Update the C
15.How many data in C? Ln(D) iterations Each iteration there suppose to be 1*P1+1*P2+ …+1*Pn =L points T otal Ln(D)*L points
16.Cluster the subset C Red points are in subset C
17.Cluster the sample C Calculate distances between point A to other points in C, and find the smallest distance In this case , d_c 1
18.Cluster the sample C Calculate distances between point A and all points in X, and get d_x i
19.Cluster the sample C Compare d_x i to d_c 1 , and let W A =number of d_x i < d_c 1 Then we get weight matrix, W Cluster W into k clusters, get k centers
20.Difference among three methods K means K means ++ K means || seeding choose k centers randomly Choose k centers proportionally Choose subset C and get k centers from C clustering
21.Hypothesis K means K means ++ K means || seeding choose k centers randomly fast Choose k centers proportionally slow Choose subset C and get k centers from C slower clustering
22.Hypothesis K means K means ++ K means || seeding choose k centers randomly fast Choose k centers proportionally slow Choose subset C and get k centers from C slower clustering slow fast faster
23.Test Hypothesis Toy data one – very small Cloud data – small Spam data – moderate Toy data two – very large
24.Simple data set N=100; d=2; k=2 ; Iteration=100
26.Cloud data consists of 1024 points in 10 dimension k=6
28.Executive time (in seconds)
