Spark ML – Power Iteration Clustering
Power iteration clustering (PIC) is a scalable and efficient algorithm for clustering vertices of a graph given pairwise similarities as edge properties, described in the paper "Power Iteration Clustering" by Frank Lin and William W. Cohen. It computes a pseudo-eigenvector of the normalized affinity matrix of the graph via power iteration and uses it to cluster vertices. spark.mllib includes an implementation of PIC using GraphX as its backend. It takes an RDD of (srcId, dstId, similarity) tuples and outputs a model with the clustering assignments. The similarities must be nonnegative. PIC assumes that the similarity measure is symmetric. A pair (srcId, dstId) regardless of the ordering should appear at most once in the input data. If a pair is missing from input, their similarity is treated as zero.
ml_power_iteration( x, k = 4, max_iter = 20, init_mode = "random", src_col = "src", dst_col = "dst", weight_col = "weight", ... )
x |
A ‘spark_connection’ or a ‘tbl_spark’. |
k |
The number of clusters to create. |
max_iter |
The maximum number of iterations to run. |
init_mode |
This can be either “random”, which is the default, to use a random vector as vertex properties, or “degree” to use normalized sum similarities. |
src_col |
Column in the input Spark dataframe containing 0-based indexes of all source vertices in the affinity matrix described in the PIC paper. |
dst_col |
Column in the input Spark dataframe containing 0-based indexes of all destination vertices in the affinity matrix described in the PIC paper. |
weight_col |
Column in the input Spark dataframe containing non-negative edge weights in the affinity matrix described in the PIC paper. |
... |
Optional arguments. Currently unused. |
A 2-column R dataframe with columns named "id" and "cluster" describing the resulting cluster assignments
## Not run:
library(sparklyr)
sc <- spark_connect(master = "local")
r1 <- 1
n1 <- 80L
r2 <- 4
n2 <- 80L
gen_circle <- function(radius, num_pts) {
# generate evenly distributed points on a circle centered at the origin
seq(0, num_pts - 1) %>%
lapply(
function(pt) {
theta <- 2 * pi * pt / num_pts
radius * c(cos(theta), sin(theta))
}
)
}
guassian_similarity <- function(pt1, pt2) {
dist2 <- sum((pt2 - pt1) ^ 2)
exp(-dist2 / 2)
}
gen_pic_data <- function() {
# generate points on 2 concentric circle centered at the origin and then
# compute pairwise Gaussian similarity values of all unordered pair of
# points
n <- n1 + n2
pts <- append(gen_circle(r1, n1), gen_circle(r2, n2))
num_unordered_pairs <- n * (n - 1) / 2
src <- rep(0L, num_unordered_pairs)
dst <- rep(0L, num_unordered_pairs)
sim <- rep(0, num_unordered_pairs)
idx <- 1
for (i in seq(2, n)) {
for (j in seq(i - 1)) {
src[[idx]] <- i - 1L
dst[[idx]] <- j - 1L
sim[[idx]] <- guassian_similarity(pts[[i]], pts[[j]])
idx <- idx + 1
}
}
tibble::tibble(src = src, dst = dst, sim = sim)
}
pic_data <- copy_to(sc, gen_pic_data())
clusters <- ml_power_iteration(
pic_data, src_col = "src", dst_col = "dst", weight_col = "sim", k = 2, max_iter = 40
)
print(clusters)
## End(Not run)Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.