org.apache.spark.mllib.clustering

Class PowerIterationClustering

Object

org.apache.spark.mllib.clustering.PowerIterationClustering

All Implemented Interfaces:

java.io.Serializable

public class PowerIterationClustering
extends Object
implements scala.Serializable

:: Experimental ::

Power Iteration Clustering (PIC), a scalable graph clustering algorithm developed by Lin and Cohen. From the abstract: PIC finds a very low-dimensional embedding of a dataset using truncated power iteration on a normalized pair-wise similarity matrix of the data.

See Also:

, Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	PowerIterationClustering.Assignment :: Experimental :: Cluster assignment.

Constructor Summary

Constructors

Constructor and Description
PowerIterationClustering() Constructs a PIC instance with default parameters: {k: 2, maxIterations: 100, initMode: "random"}.
PowerIterationClustering(int k, int maxIterations, String initMode)

Method Summary

Methods

Modifier and Type	Method and Description
static Graph<Object,Object>	initDegreeVector(Graph<Object,Object> g) Generates the degree vector as the vertex properties (v0) to start power iteration.
static VertexRDD<Object>	kMeans(VertexRDD<Object> v, int k) Runs k-means clustering.
static Graph<Object,Object>	normalize(RDD<scala.Tuple3<Object,Object,Object>> similarities) Normalizes the affinity matrix (A) by row sums and returns the normalized affinity matrix (W).
static VertexRDD<Object>	powerIter(Graph<Object,Object> g, int maxIterations) Runs power iteration.
static Graph<Object,Object>	randomInit(Graph<Object,Object> g) Generates random vertex properties (v0) to start power iteration.
PowerIterationClusteringModel	run(JavaRDD<scala.Tuple3<Long,Long,Double>> similarities) A Java-friendly version of PowerIterationClustering.run.
PowerIterationClusteringModel	run(RDD<scala.Tuple3<Object,Object,Object>> similarities) Run the PIC algorithm.
PowerIterationClustering	setInitializationMode(String mode) Set the initialization mode.
PowerIterationClustering	setK(int k) Set the number of clusters.
PowerIterationClustering	setMaxIterations(int maxIterations) Set maximum number of iterations of the power iteration loop

Methods inherited from class Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

PowerIterationClustering

public PowerIterationClustering(int k,
                        int maxIterations,
                        String initMode)

PowerIterationClustering

public PowerIterationClustering()

Constructs a PIC instance with default parameters: {k: 2, maxIterations: 100, initMode: "random"}.

Method Detail

normalize

public static Graph<Object,Object> normalize(RDD<scala.Tuple3<Object,Object,Object>> similarities)

Normalizes the affinity matrix (A) by row sums and returns the normalized affinity matrix (W).

randomInit

public static Graph<Object,Object> randomInit(Graph<Object,Object> g)

Generates random vertex properties (v0) to start power iteration.

Parameters:

g - a graph representing the normalized affinity matrix (W)

Returns:

a graph with edges representing W and vertices representing a random vector with unit 1-norm

initDegreeVector

public static Graph<Object,Object> initDegreeVector(Graph<Object,Object> g)

Generates the degree vector as the vertex properties (v0) to start power iteration. It is not exactly the node degrees but just the normalized sum similarities. Call it as degree vector because it is used in the PIC paper.

Parameters:

g - a graph representing the normalized affinity matrix (W)

Returns:

a graph with edges representing W and vertices representing the degree vector

powerIter

public static VertexRDD<Object> powerIter(Graph<Object,Object> g,
                          int maxIterations)

Runs power iteration.

Parameters:

g - input graph with edges representing the normalized affinity matrix (W) and vertices representing the initial vector of the power iterations.

maxIterations - maximum number of iterations

Returns:

a VertexRDD representing the pseudo-eigenvector

kMeans

public static VertexRDD<Object> kMeans(VertexRDD<Object> v,
                       int k)

Runs k-means clustering.

Parameters:

v - a VertexRDD representing the pseudo-eigenvector

k - number of clusters

Returns:

a VertexRDD representing the clustering assignments

setK

public PowerIterationClustering setK(int k)

Set the number of clusters.

setMaxIterations

public PowerIterationClustering setMaxIterations(int maxIterations)

Set maximum number of iterations of the power iteration loop

setInitializationMode

public PowerIterationClustering setInitializationMode(String mode)

Set the initialization mode. This can be either "random" to use a random vector as vertex properties, or "degree" to use normalized sum similarities. Default: random.

run

public PowerIterationClusteringModel run(RDD<scala.Tuple3<Object,Object,Object>> similarities)

Run the PIC algorithm.

Parameters:

similarities - an RDD of (i, j, s,,ij,,) tuples representing the affinity matrix, which is the matrix A in the PIC paper. The similarity s,,ij,, must be nonnegative. This is a symmetric matrix and hence s,,ij,, = s,,ji,,. For any (i, j) with nonzero similarity, there should be either (i, j, s,,ij,,) or (j, i, s,,ji,,) in the input. Tuples with i = j are ignored, because we assume s,,ij,, = 0.0.

Returns:

a PowerIterationClusteringModel that contains the clustering result

run

public PowerIterationClusteringModel run(JavaRDD<scala.Tuple3<Long,Long,Double>> similarities)

A Java-friendly version of PowerIterationClustering.run.