You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@spark.apache.org by viirya <gi...@git.apache.org> on 2015/02/16 09:44:28 UTC
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
GitHub user viirya opened a pull request:
https://github.com/apache/spark/pull/4622
[SPARK-5832][Mllib] Add Affinity Propagation clustering algorithm
Affinity Propagation (AP), a graph clustering algorithm based on the concept of "message passing" between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not require the number of clusters to be determined or estimated before running it. AP is developed by Frey and Dueck. Please refer to the [paper](http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf).
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/viirya/spark-1 ap_clustering
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/spark/pull/4622.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #4622
----
commit d469d12257e68e437328a90d647a67bd002622f4
Author: Liang-Chi Hsieh <vi...@gmail.com>
Date: 2015-02-16T08:19:06Z
Add Affinity Propagation clustering algorithm.
----
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r27896111
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not
+ * require the number of clusters to be determined or estimated before running it. AP is developed
+ * by [[http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf Frey and Dueck]].
+ *
+ * @param maxIterations Maximum number of iterations of the AP algorithm.
+ *
+ * @see [[http://en.wikipedia.org/wiki/Affinity_propagation (Wikipedia)]]
+ */
+@Experimental
+class AffinityPropagation private[clustering] (
+ private var maxIterations: Int,
+ private var lambda: Double,
+ private var normalization: Boolean) extends Serializable {
+
+ import org.apache.spark.mllib.clustering.AffinityPropagation._
+
+ /** Constructs a AP instance with default parameters: {maxIterations: 100, lambda: 0.5,
+ * normalization: false}.
+ */
+ def this() = this(maxIterations = 100, lambda = 0.5, normalization = false)
+
+ /**
+ * Set maximum number of iterations of the messaging iteration loop
+ */
+ def setMaxIterations(maxIterations: Int): this.type = {
+ this.maxIterations = maxIterations
+ this
+ }
+
+ /**
+ * Get maximum number of iterations of the messaging iteration loop
+ */
+ def getMaxIterations(): Int = {
+ this.maxIterations
+ }
+
+ /**
+ * Set lambda of the messaging iteration loop
+ */
+ def setLambda(lambda: Double): this.type = {
+ this.lambda = lambda
+ this
+ }
+
+ /**
+ * Get lambda of the messaging iteration loop
+ */
+ def getLambda(): Double = {
+ this.lambda
+ }
+
+ /**
+ * Set whether to do normalization or not
+ */
+ def setNormalization(normalization: Boolean): this.type = {
+ this.normalization = normalization
+ this
+ }
+
+ /**
+ * Get whether to do normalization or not
+ */
+ def getNormalization(): Boolean = {
+ this.normalization
+ }
+
+ /**
+ * Run the AP algorithm.
+ *
+ * @param similarities an RDD of (i, j, s,,ij,,) tuples representing the similarity matrix, which
+ * is the matrix S in the AP paper. The similarity s,,ij,, is set to
+ * real-valued similarities. This is not required to be a symmetric matrix
+ * and hence s,,ij,, can be not equal to s,,ji,,. Tuples with i = j are
+ * referred to as "preferences" in the AP paper. The data points with larger
+ * values of s,,ii,, are more likely to be chosen as exemplars.
+ *
+ * @param symmetric the given similarity matrix is symmetric or not. Default value: true
+ * @return a [[AffinityPropagationModel]] that contains the clustering result
+ */
+ def run(similarities: RDD[(Long, Long, Double)], symmetric: Boolean = true)
+ : AffinityPropagationModel = {
+ val s = constructGraph(similarities, normalization, symmetric)
+ ap(s)
+ }
+
+ /**
+ * Runs the AP algorithm.
+ *
+ * @param s The (normalized) similarity matrix, which is the matrix S in the AP paper with vertex
+ * similarities and the initial availabilities and responsibilities as its edge
+ * properties.
+ */
+ private def ap(s: Graph[Seq[Double], Seq[Double]]): AffinityPropagationModel = {
+ val g = apIter(s, maxIterations, lambda)
+ chooseExemplars(g)
+ }
+}
+
+private[clustering] object AffinityPropagation extends Logging {
+ /**
+ * Construct the similarity matrix (S) and do normalization if needed.
+ * Returns the (normalized) similarity matrix (S).
+ */
+ def constructGraph(similarities: RDD[(Long, Long, Double)], normalize: Boolean,
+ symmetric: Boolean):
+ Graph[Seq[Double], Seq[Double]] = {
+ val edges = similarities.flatMap { case (i, j, s) =>
+ if (symmetric && i != j) {
+ Seq(Edge(i, j, Seq(s, 0.0, 0.0)), Edge(j, i, Seq(s, 0.0, 0.0)))
+ } else {
+ Seq(Edge(i, j, Seq(s, 0.0, 0.0)))
+ }
+ }
+
+ if (normalize) {
+ val gA = Graph.fromEdges(edges, Seq(0.0))
+ val vD = gA.aggregateMessages[Seq[Double]](
+ sendMsg = ctx => {
+ ctx.sendToSrc(Seq(ctx.attr(0)))
+ },
+ mergeMsg = (s1, s2) => Seq(s1(0) + s2(0)),
+ TripletFields.EdgeOnly)
+ val normalized = GraphImpl.fromExistingRDDs(vD, gA.edges)
+ .mapTriplets(
+ e => {
+ val s = if (e.srcAttr(0) == 0.0) { e.attr(0) } else { e.attr(0) / e.srcAttr(0) }
+ Seq(s, 0.0, 0.0)
+ }, TripletFields.Src)
+ Graph.fromEdges(normalized.edges, Seq(0.0, 0.0))
--- End diff --
If you mean `vD`, I think its type is different to what we use here (`Seq(0.0, 0.0)`)?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91795890
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/30067/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91402720
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/29989/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r27893371
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not
+ * require the number of clusters to be determined or estimated before running it. AP is developed
+ * by [[http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf Frey and Dueck]].
+ *
+ * @param maxIterations Maximum number of iterations of the AP algorithm.
+ *
+ * @see [[http://en.wikipedia.org/wiki/Affinity_propagation (Wikipedia)]]
+ */
+@Experimental
+class AffinityPropagation private[clustering] (
+ private var maxIterations: Int,
+ private var lambda: Double,
+ private var normalization: Boolean) extends Serializable {
+
+ import org.apache.spark.mllib.clustering.AffinityPropagation._
+
+ /** Constructs a AP instance with default parameters: {maxIterations: 100, lambda: 0.5,
+ * normalization: false}.
+ */
+ def this() = this(maxIterations = 100, lambda = 0.5, normalization = false)
+
+ /**
+ * Set maximum number of iterations of the messaging iteration loop
+ */
+ def setMaxIterations(maxIterations: Int): this.type = {
+ this.maxIterations = maxIterations
+ this
+ }
+
+ /**
+ * Get maximum number of iterations of the messaging iteration loop
+ */
+ def getMaxIterations(): Int = {
+ this.maxIterations
+ }
+
+ /**
+ * Set lambda of the messaging iteration loop
+ */
+ def setLambda(lambda: Double): this.type = {
+ this.lambda = lambda
+ this
+ }
+
+ /**
+ * Get lambda of the messaging iteration loop
+ */
+ def getLambda(): Double = {
+ this.lambda
+ }
+
+ /**
+ * Set whether to do normalization or not
+ */
+ def setNormalization(normalization: Boolean): this.type = {
+ this.normalization = normalization
+ this
+ }
+
+ /**
+ * Get whether to do normalization or not
+ */
+ def getNormalization(): Boolean = {
+ this.normalization
+ }
+
+ /**
+ * Run the AP algorithm.
+ *
+ * @param similarities an RDD of (i, j, s,,ij,,) tuples representing the similarity matrix, which
+ * is the matrix S in the AP paper. The similarity s,,ij,, is set to
+ * real-valued similarities. This is not required to be a symmetric matrix
--- End diff --
Yes. It can be. Will document it.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91574022
[Test build #30031 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/30031/consoleFull) for PR 4622 at commit [`a485422`](https://github.com/apache/spark/commit/a485422d9793c6523be3ea92410c42280d75791f).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092338
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not
+ * require the number of clusters to be determined or estimated before running it. AP is developed
+ * by [[http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf Frey and Dueck]].
+ *
+ * @param maxIterations Maximum number of iterations of the AP algorithm.
+ *
+ * @see [[http://en.wikipedia.org/wiki/Affinity_propagation (Wikipedia)]]
+ */
+@Experimental
+class AffinityPropagation private[clustering] (
+ private var maxIterations: Int,
+ private var lambda: Double,
+ private var normalization: Boolean) extends Serializable {
+
+ import org.apache.spark.mllib.clustering.AffinityPropagation._
+
+ /** Constructs a AP instance with default parameters: {maxIterations: 100, lambda: 0.5,
+ * normalization: false}.
+ */
+ def this() = this(maxIterations = 100, lambda = 0.5, normalization = false)
+
+ /**
+ * Set maximum number of iterations of the messaging iteration loop
+ */
+ def setMaxIterations(maxIterations: Int): this.type = {
+ this.maxIterations = maxIterations
+ this
+ }
+
+ /**
+ * Get maximum number of iterations of the messaging iteration loop
+ */
+ def getMaxIterations(): Int = {
+ this.maxIterations
+ }
+
+ /**
+ * Set lambda of the messaging iteration loop
+ */
+ def setLambda(lambda: Double): this.type = {
+ this.lambda = lambda
+ this
+ }
+
+ /**
+ * Get lambda of the messaging iteration loop
+ */
+ def getLambda(): Double = {
+ this.lambda
+ }
+
+ /**
+ * Set whether to do normalization or not
+ */
+ def setNormalization(normalization: Boolean): this.type = {
+ this.normalization = normalization
+ this
+ }
+
+ /**
+ * Get whether to do normalization or not
+ */
+ def getNormalization(): Boolean = {
+ this.normalization
+ }
+
+ /**
+ * Run the AP algorithm.
+ *
+ * @param similarities an RDD of (i, j, s,,ij,,) tuples representing the similarity matrix, which
+ * is the matrix S in the AP paper. The similarity s,,ij,, is set to
+ * real-valued similarities. This is not required to be a symmetric matrix
+ * and hence s,,ij,, can be not equal to s,,ji,,. Tuples with i = j are
+ * referred to as "preferences" in the AP paper. The data points with larger
+ * values of s,,ii,, are more likely to be chosen as exemplars.
+ *
+ * @param symmetric the given similarity matrix is symmetric or not. Default value: true
+ * @return a [[AffinityPropagationModel]] that contains the clustering result
+ */
+ def run(similarities: RDD[(Long, Long, Double)], symmetric: Boolean = true)
+ : AffinityPropagationModel = {
+ val s = constructGraph(similarities, normalization, symmetric)
+ ap(s)
+ }
+
+ /**
+ * Runs the AP algorithm.
+ *
+ * @param s The (normalized) similarity matrix, which is the matrix S in the AP paper with vertex
+ * similarities and the initial availabilities and responsibilities as its edge
+ * properties.
+ */
+ private def ap(s: Graph[Seq[Double], Seq[Double]]): AffinityPropagationModel = {
+ val g = apIter(s, maxIterations, lambda)
+ chooseExemplars(g)
+ }
+}
+
+private[clustering] object AffinityPropagation extends Logging {
+ /**
+ * Construct the similarity matrix (S) and do normalization if needed.
+ * Returns the (normalized) similarity matrix (S).
+ */
+ def constructGraph(similarities: RDD[(Long, Long, Double)], normalize: Boolean,
+ symmetric: Boolean):
+ Graph[Seq[Double], Seq[Double]] = {
+ val edges = similarities.flatMap { case (i, j, s) =>
+ if (symmetric && i != j) {
+ Seq(Edge(i, j, Seq(s, 0.0, 0.0)), Edge(j, i, Seq(s, 0.0, 0.0)))
+ } else {
+ Seq(Edge(i, j, Seq(s, 0.0, 0.0)))
+ }
+ }
+
+ if (normalize) {
+ val gA = Graph.fromEdges(edges, Seq(0.0))
--- End diff --
Why do you need to wrap doubles with `Seq`?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91614294
[Test build #30037 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/30037/consoleFull) for PR 4622 at commit [`ffe06c3`](https://github.com/apache/spark/commit/ffe06c32fa892fc36a3a7f225ba8df256813e653).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91016654
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/29876/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-74653282
[Test build #27628 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/27628/consoleFull) for PR 4622 at commit [`6cddeb2`](https://github.com/apache/spark/commit/6cddeb2f655fb477d23c1fbe5bf0230e2b97bdce).
* This patch **passes all tests**.
* This patch merges cleanly.
* This patch adds the following public classes _(experimental)_:
* `class AffinityPropagationModel(`
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-90644122
[Test build #29798 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/29798/consoleFull) for PR 4622 at commit [`d762697`](https://github.com/apache/spark/commit/d762697e4140781b2dc8882c4d654e19ce5bb80b).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-74638488
@mengxr I updated the JIRA page. Please take a look. Thanks!
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91601780
@mengxr I have addressed all your comments. Please take a look. Thanks.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092313
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
--- End diff --
`AffinityPropagation` -> `Affinity propagation`.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit closed the pull request at:
https://github.com/apache/spark/pull/4622
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-90992381
[Test build #29872 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/29872/consoleFull) for PR 4622 at commit [`f031efd`](https://github.com/apache/spark/commit/f031efdb45dd7bd879297d4a9d7b31e9d9a8804f).
* This patch **fails Scala style tests**.
* This patch merges cleanly.
* This patch adds no public classes.
* This patch **removes the following dependencies:**
* `RoaringBitmap-0.4.5.jar`
* `activation-1.1.jar`
* `akka-actor_2.10-2.3.4-spark.jar`
* `akka-remote_2.10-2.3.4-spark.jar`
* `akka-slf4j_2.10-2.3.4-spark.jar`
* `aopalliance-1.0.jar`
* `arpack_combined_all-0.1.jar`
* `avro-1.7.6.jar`
* `breeze-macros_2.10-0.11.1.jar`
* `breeze_2.10-0.11.1.jar`
* `chill-java-0.5.0.jar`
* `chill_2.10-0.5.0.jar`
* `commons-beanutils-1.7.0.jar`
* `commons-beanutils-core-1.8.0.jar`
* `commons-cli-1.2.jar`
* `commons-codec-1.10.jar`
* `commons-collections-3.2.1.jar`
* `commons-compress-1.4.1.jar`
* `commons-configuration-1.6.jar`
* `commons-digester-1.8.jar`
* `commons-httpclient-3.1.jar`
* `commons-io-2.1.jar`
* `commons-lang-2.5.jar`
* `commons-lang3-3.3.2.jar`
* `commons-math-2.1.jar`
* `commons-math3-3.1.1.jar`
* `commons-net-2.2.jar`
* `compress-lzf-1.0.0.jar`
* `config-1.2.1.jar`
* `core-1.1.2.jar`
* `curator-client-2.4.0.jar`
* `curator-framework-2.4.0.jar`
* `curator-recipes-2.4.0.jar`
* `gmbal-api-only-3.0.0-b023.jar`
* `grizzly-framework-2.1.2.jar`
* `grizzly-http-2.1.2.jar`
* `grizzly-http-server-2.1.2.jar`
* `grizzly-http-servlet-2.1.2.jar`
* `grizzly-rcm-2.1.2.jar`
* `groovy-all-2.3.7.jar`
* `guava-14.0.1.jar`
* `guice-3.0.jar`
* `hadoop-annotations-2.2.0.jar`
* `hadoop-auth-2.2.0.jar`
* `hadoop-client-2.2.0.jar`
* `hadoop-common-2.2.0.jar`
* `hadoop-hdfs-2.2.0.jar`
* `hadoop-mapreduce-client-app-2.2.0.jar`
* `hadoop-mapreduce-client-common-2.2.0.jar`
* `hadoop-mapreduce-client-core-2.2.0.jar`
* `hadoop-mapreduce-client-jobclient-2.2.0.jar`
* `hadoop-mapreduce-client-shuffle-2.2.0.jar`
* `hadoop-yarn-api-2.2.0.jar`
* `hadoop-yarn-client-2.2.0.jar`
* `hadoop-yarn-common-2.2.0.jar`
* `hadoop-yarn-server-common-2.2.0.jar`
* `ivy-2.4.0.jar`
* `jackson-annotations-2.4.0.jar`
* `jackson-core-2.4.4.jar`
* `jackson-core-asl-1.8.8.jar`
* `jackson-databind-2.4.4.jar`
* `jackson-jaxrs-1.8.8.jar`
* `jackson-mapper-asl-1.8.8.jar`
* `jackson-module-scala_2.10-2.4.4.jar`
* `jackson-xc-1.8.8.jar`
* `jansi-1.4.jar`
* `javax.inject-1.jar`
* `javax.servlet-3.0.0.v201112011016.jar`
* `javax.servlet-3.1.jar`
* `javax.servlet-api-3.0.1.jar`
* `jaxb-api-2.2.2.jar`
* `jaxb-impl-2.2.3-1.jar`
* `jcl-over-slf4j-1.7.10.jar`
* `jersey-client-1.9.jar`
* `jersey-core-1.9.jar`
* `jersey-grizzly2-1.9.jar`
* `jersey-guice-1.9.jar`
* `jersey-json-1.9.jar`
* `jersey-server-1.9.jar`
* `jersey-test-framework-core-1.9.jar`
* `jersey-test-framework-grizzly2-1.9.jar`
* `jets3t-0.7.1.jar`
* `jettison-1.1.jar`
* `jetty-util-6.1.26.jar`
* `jline-0.9.94.jar`
* `jline-2.10.4.jar`
* `jodd-core-3.6.3.jar`
* `json4s-ast_2.10-3.2.10.jar`
* `json4s-core_2.10-3.2.10.jar`
* `json4s-jackson_2.10-3.2.10.jar`
* `jsr305-1.3.9.jar`
* `jtransforms-2.4.0.jar`
* `jul-to-slf4j-1.7.10.jar`
* `kryo-2.21.jar`
* `log4j-1.2.17.jar`
* `lz4-1.2.0.jar`
* `management-api-3.0.0-b012.jar`
* `mesos-0.21.0-shaded-protobuf.jar`
* `metrics-core-3.1.0.jar`
* `metrics-graphite-3.1.0.jar`
* `metrics-json-3.1.0.jar`
* `metrics-jvm-3.1.0.jar`
* `minlog-1.2.jar`
* `netty-3.8.0.Final.jar`
* `netty-all-4.0.23.Final.jar`
* `objenesis-1.2.jar`
* `opencsv-2.3.jar`
* `oro-2.0.8.jar`
* `paranamer-2.6.jar`
* `parquet-column-1.6.0rc3.jar`
* `parquet-common-1.6.0rc3.jar`
* `parquet-encoding-1.6.0rc3.jar`
* `parquet-format-2.2.0-rc1.jar`
* `parquet-generator-1.6.0rc3.jar`
* `parquet-hadoop-1.6.0rc3.jar`
* `parquet-jackson-1.6.0rc3.jar`
* `protobuf-java-2.4.1.jar`
* `protobuf-java-2.5.0-spark.jar`
* `py4j-0.8.2.1.jar`
* `pyrolite-2.0.1.jar`
* `quasiquotes_2.10-2.0.1.jar`
* `reflectasm-1.07-shaded.jar`
* `scala-compiler-2.10.4.jar`
* `scala-library-2.10.4.jar`
* `scala-reflect-2.10.4.jar`
* `scalap-2.10.4.jar`
* `scalatest_2.10-2.2.1.jar`
* `slf4j-api-1.7.10.jar`
* `slf4j-log4j12-1.7.10.jar`
* `snappy-java-1.1.1.6.jar`
* `spark-bagel_2.10-1.4.0-SNAPSHOT.jar`
* `spark-catalyst_2.10-1.4.0-SNAPSHOT.jar`
* `spark-core_2.10-1.4.0-SNAPSHOT.jar`
* `spark-graphx_2.10-1.4.0-SNAPSHOT.jar`
* `spark-launcher_2.10-1.4.0-SNAPSHOT.jar`
* `spark-mllib_2.10-1.4.0-SNAPSHOT.jar`
* `spark-network-common_2.10-1.4.0-SNAPSHOT.jar`
* `spark-network-shuffle_2.10-1.4.0-SNAPSHOT.jar`
* `spark-repl_2.10-1.4.0-SNAPSHOT.jar`
* `spark-sql_2.10-1.4.0-SNAPSHOT.jar`
* `spark-streaming_2.10-1.4.0-SNAPSHOT.jar`
* `spire-macros_2.10-0.7.4.jar`
* `spire_2.10-0.7.4.jar`
* `stax-api-1.0.1.jar`
* `stream-2.7.0.jar`
* `tachyon-0.5.0.jar`
* `tachyon-client-0.5.0.jar`
* `uncommons-maths-1.2.2a.jar`
* `unused-1.0.0.jar`
* `xmlenc-0.52.jar`
* `xz-1.0.jar`
* `zookeeper-3.4.5.jar`
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-90644488
[Test build #29798 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/29798/consoleFull) for PR 4622 at commit [`d762697`](https://github.com/apache/spark/commit/d762697e4140781b2dc8882c4d654e19ce5bb80b).
* This patch **fails Scala style tests**.
* This patch merges cleanly.
* This patch adds the following public classes _(experimental)_:
* `class AffinityPropagationModel(`
* This patch does not change any dependencies.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-90643243
@mengxr I updated for small comments. For the bigger ones, I will update later.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-90694626
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/29799/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91784107
[Test build #30067 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/30067/consoleFull) for PR 4622 at commit [`97cef01`](https://github.com/apache/spark/commit/97cef01f1e9f1bd2fcaa2d7718302c8ae79cf25a).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r27930450
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not
+ * require the number of clusters to be determined or estimated before running it. AP is developed
+ * by [[http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf Frey and Dueck]].
+ *
+ * @param maxIterations Maximum number of iterations of the AP algorithm.
+ *
+ * @see [[http://en.wikipedia.org/wiki/Affinity_propagation (Wikipedia)]]
+ */
+@Experimental
+class AffinityPropagation private[clustering] (
+ private var maxIterations: Int,
+ private var lambda: Double,
+ private var normalization: Boolean) extends Serializable {
+
+ import org.apache.spark.mllib.clustering.AffinityPropagation._
+
+ /** Constructs a AP instance with default parameters: {maxIterations: 100, lambda: 0.5,
+ * normalization: false}.
+ */
+ def this() = this(maxIterations = 100, lambda = 0.5, normalization = false)
+
+ /**
+ * Set maximum number of iterations of the messaging iteration loop
+ */
+ def setMaxIterations(maxIterations: Int): this.type = {
+ this.maxIterations = maxIterations
+ this
+ }
+
+ /**
+ * Get maximum number of iterations of the messaging iteration loop
+ */
+ def getMaxIterations(): Int = {
+ this.maxIterations
+ }
+
+ /**
+ * Set lambda of the messaging iteration loop
+ */
+ def setLambda(lambda: Double): this.type = {
+ this.lambda = lambda
+ this
+ }
+
+ /**
+ * Get lambda of the messaging iteration loop
+ */
+ def getLambda(): Double = {
+ this.lambda
+ }
+
+ /**
+ * Set whether to do normalization or not
+ */
+ def setNormalization(normalization: Boolean): this.type = {
+ this.normalization = normalization
+ this
+ }
+
+ /**
+ * Get whether to do normalization or not
+ */
+ def getNormalization(): Boolean = {
+ this.normalization
+ }
+
+ /**
+ * Run the AP algorithm.
+ *
+ * @param similarities an RDD of (i, j, s,,ij,,) tuples representing the similarity matrix, which
+ * is the matrix S in the AP paper. The similarity s,,ij,, is set to
+ * real-valued similarities. This is not required to be a symmetric matrix
+ * and hence s,,ij,, can be not equal to s,,ji,,. Tuples with i = j are
+ * referred to as "preferences" in the AP paper. The data points with larger
+ * values of s,,ii,, are more likely to be chosen as exemplars.
+ *
+ * @param symmetric the given similarity matrix is symmetric or not. Default value: true
--- End diff --
Do we expect users use the same AP object but run with different datasets (symmetric/asymmetric)? If not, it should be okay to make symmetric a parameter. This is similar to the `k` in k-means. `k` is associated with the dataset, but we set it in the KMeans object.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092341
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not
+ * require the number of clusters to be determined or estimated before running it. AP is developed
+ * by [[http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf Frey and Dueck]].
+ *
+ * @param maxIterations Maximum number of iterations of the AP algorithm.
+ *
+ * @see [[http://en.wikipedia.org/wiki/Affinity_propagation (Wikipedia)]]
+ */
+@Experimental
+class AffinityPropagation private[clustering] (
+ private var maxIterations: Int,
+ private var lambda: Double,
+ private var normalization: Boolean) extends Serializable {
+
+ import org.apache.spark.mllib.clustering.AffinityPropagation._
+
+ /** Constructs a AP instance with default parameters: {maxIterations: 100, lambda: 0.5,
+ * normalization: false}.
+ */
+ def this() = this(maxIterations = 100, lambda = 0.5, normalization = false)
+
+ /**
+ * Set maximum number of iterations of the messaging iteration loop
+ */
+ def setMaxIterations(maxIterations: Int): this.type = {
+ this.maxIterations = maxIterations
+ this
+ }
+
+ /**
+ * Get maximum number of iterations of the messaging iteration loop
+ */
+ def getMaxIterations(): Int = {
+ this.maxIterations
+ }
+
+ /**
+ * Set lambda of the messaging iteration loop
+ */
+ def setLambda(lambda: Double): this.type = {
+ this.lambda = lambda
+ this
+ }
+
+ /**
+ * Get lambda of the messaging iteration loop
+ */
+ def getLambda(): Double = {
+ this.lambda
+ }
+
+ /**
+ * Set whether to do normalization or not
+ */
+ def setNormalization(normalization: Boolean): this.type = {
+ this.normalization = normalization
+ this
+ }
+
+ /**
+ * Get whether to do normalization or not
+ */
+ def getNormalization(): Boolean = {
+ this.normalization
+ }
+
+ /**
+ * Run the AP algorithm.
+ *
+ * @param similarities an RDD of (i, j, s,,ij,,) tuples representing the similarity matrix, which
+ * is the matrix S in the AP paper. The similarity s,,ij,, is set to
+ * real-valued similarities. This is not required to be a symmetric matrix
+ * and hence s,,ij,, can be not equal to s,,ji,,. Tuples with i = j are
+ * referred to as "preferences" in the AP paper. The data points with larger
+ * values of s,,ii,, are more likely to be chosen as exemplars.
+ *
+ * @param symmetric the given similarity matrix is symmetric or not. Default value: true
+ * @return a [[AffinityPropagationModel]] that contains the clustering result
+ */
+ def run(similarities: RDD[(Long, Long, Double)], symmetric: Boolean = true)
+ : AffinityPropagationModel = {
+ val s = constructGraph(similarities, normalization, symmetric)
+ ap(s)
+ }
+
+ /**
+ * Runs the AP algorithm.
+ *
+ * @param s The (normalized) similarity matrix, which is the matrix S in the AP paper with vertex
+ * similarities and the initial availabilities and responsibilities as its edge
+ * properties.
+ */
+ private def ap(s: Graph[Seq[Double], Seq[Double]]): AffinityPropagationModel = {
+ val g = apIter(s, maxIterations, lambda)
+ chooseExemplars(g)
+ }
+}
+
+private[clustering] object AffinityPropagation extends Logging {
+ /**
+ * Construct the similarity matrix (S) and do normalization if needed.
+ * Returns the (normalized) similarity matrix (S).
+ */
+ def constructGraph(similarities: RDD[(Long, Long, Double)], normalize: Boolean,
+ symmetric: Boolean):
+ Graph[Seq[Double], Seq[Double]] = {
+ val edges = similarities.flatMap { case (i, j, s) =>
+ if (symmetric && i != j) {
+ Seq(Edge(i, j, Seq(s, 0.0, 0.0)), Edge(j, i, Seq(s, 0.0, 0.0)))
+ } else {
+ Seq(Edge(i, j, Seq(s, 0.0, 0.0)))
+ }
+ }
+
+ if (normalize) {
+ val gA = Graph.fromEdges(edges, Seq(0.0))
+ val vD = gA.aggregateMessages[Seq[Double]](
+ sendMsg = ctx => {
+ ctx.sendToSrc(Seq(ctx.attr(0)))
+ },
+ mergeMsg = (s1, s2) => Seq(s1(0) + s2(0)),
+ TripletFields.EdgeOnly)
+ val normalized = GraphImpl.fromExistingRDDs(vD, gA.edges)
+ .mapTriplets(
--- End diff --
style:
~~~
.mapTriplets({ e =>
...
}, TripletFields.Src)
~~~
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-74644181
[Test build #27628 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/27628/consoleFull) for PR 4622 at commit [`6cddeb2`](https://github.com/apache/spark/commit/6cddeb2f655fb477d23c1fbe5bf0230e2b97bdce).
* This patch merges cleanly.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-74653294
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/27628/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092352
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not
+ * require the number of clusters to be determined or estimated before running it. AP is developed
+ * by [[http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf Frey and Dueck]].
+ *
+ * @param maxIterations Maximum number of iterations of the AP algorithm.
+ *
+ * @see [[http://en.wikipedia.org/wiki/Affinity_propagation (Wikipedia)]]
+ */
+@Experimental
+class AffinityPropagation private[clustering] (
+ private var maxIterations: Int,
+ private var lambda: Double,
+ private var normalization: Boolean) extends Serializable {
+
+ import org.apache.spark.mllib.clustering.AffinityPropagation._
+
+ /** Constructs a AP instance with default parameters: {maxIterations: 100, lambda: 0.5,
+ * normalization: false}.
+ */
+ def this() = this(maxIterations = 100, lambda = 0.5, normalization = false)
+
+ /**
+ * Set maximum number of iterations of the messaging iteration loop
+ */
+ def setMaxIterations(maxIterations: Int): this.type = {
+ this.maxIterations = maxIterations
+ this
+ }
+
+ /**
+ * Get maximum number of iterations of the messaging iteration loop
+ */
+ def getMaxIterations(): Int = {
+ this.maxIterations
+ }
+
+ /**
+ * Set lambda of the messaging iteration loop
+ */
+ def setLambda(lambda: Double): this.type = {
+ this.lambda = lambda
+ this
+ }
+
+ /**
+ * Get lambda of the messaging iteration loop
+ */
+ def getLambda(): Double = {
+ this.lambda
+ }
+
+ /**
+ * Set whether to do normalization or not
+ */
+ def setNormalization(normalization: Boolean): this.type = {
+ this.normalization = normalization
+ this
+ }
+
+ /**
+ * Get whether to do normalization or not
+ */
+ def getNormalization(): Boolean = {
+ this.normalization
+ }
+
+ /**
+ * Run the AP algorithm.
+ *
+ * @param similarities an RDD of (i, j, s,,ij,,) tuples representing the similarity matrix, which
+ * is the matrix S in the AP paper. The similarity s,,ij,, is set to
+ * real-valued similarities. This is not required to be a symmetric matrix
+ * and hence s,,ij,, can be not equal to s,,ji,,. Tuples with i = j are
+ * referred to as "preferences" in the AP paper. The data points with larger
+ * values of s,,ii,, are more likely to be chosen as exemplars.
+ *
+ * @param symmetric the given similarity matrix is symmetric or not. Default value: true
+ * @return a [[AffinityPropagationModel]] that contains the clustering result
+ */
+ def run(similarities: RDD[(Long, Long, Double)], symmetric: Boolean = true)
+ : AffinityPropagationModel = {
+ val s = constructGraph(similarities, normalization, symmetric)
+ ap(s)
+ }
+
+ /**
+ * Runs the AP algorithm.
+ *
+ * @param s The (normalized) similarity matrix, which is the matrix S in the AP paper with vertex
+ * similarities and the initial availabilities and responsibilities as its edge
+ * properties.
+ */
+ private def ap(s: Graph[Seq[Double], Seq[Double]]): AffinityPropagationModel = {
+ val g = apIter(s, maxIterations, lambda)
+ chooseExemplars(g)
+ }
+}
+
+private[clustering] object AffinityPropagation extends Logging {
+ /**
+ * Construct the similarity matrix (S) and do normalization if needed.
+ * Returns the (normalized) similarity matrix (S).
+ */
+ def constructGraph(similarities: RDD[(Long, Long, Double)], normalize: Boolean,
+ symmetric: Boolean):
+ Graph[Seq[Double], Seq[Double]] = {
+ val edges = similarities.flatMap { case (i, j, s) =>
+ if (symmetric && i != j) {
+ Seq(Edge(i, j, Seq(s, 0.0, 0.0)), Edge(j, i, Seq(s, 0.0, 0.0)))
+ } else {
+ Seq(Edge(i, j, Seq(s, 0.0, 0.0)))
+ }
+ }
+
+ if (normalize) {
+ val gA = Graph.fromEdges(edges, Seq(0.0))
+ val vD = gA.aggregateMessages[Seq[Double]](
+ sendMsg = ctx => {
+ ctx.sendToSrc(Seq(ctx.attr(0)))
+ },
+ mergeMsg = (s1, s2) => Seq(s1(0) + s2(0)),
+ TripletFields.EdgeOnly)
+ val normalized = GraphImpl.fromExistingRDDs(vD, gA.edges)
+ .mapTriplets(
+ e => {
+ val s = if (e.srcAttr(0) == 0.0) { e.attr(0) } else { e.attr(0) / e.srcAttr(0) }
+ Seq(s, 0.0, 0.0)
+ }, TripletFields.Src)
+ Graph.fromEdges(normalized.edges, Seq(0.0, 0.0))
+ } else {
+ Graph.fromEdges(edges, Seq(0.0, 0.0))
+ }
+ }
+
+ /**
+ * Runs AP's iteration.
+ * @param g input graph with edges representing the (normalized) similarity matrix (S) and
+ * the initial availabilities and responsibilities.
+ * @param maxIterations maximum number of iterations.
+ * @return a [[Graph]] representing the final graph.
+ */
+ def apIter(
+ g: Graph[Seq[Double], Seq[Double]],
+ maxIterations: Int, lambda: Double): Graph[Seq[Double], Seq[Double]] = {
--- End diff --
Chop down `lambda`.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-74559761
@viirya For new algorithms, we need to discuss whether we want to include it in MLlib on the JIRA page first (before implementing it). Could you describe more about this algorithm on the JIRA page, e.g., scalability, usage, and alternatives?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092347
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not
+ * require the number of clusters to be determined or estimated before running it. AP is developed
+ * by [[http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf Frey and Dueck]].
+ *
+ * @param maxIterations Maximum number of iterations of the AP algorithm.
+ *
+ * @see [[http://en.wikipedia.org/wiki/Affinity_propagation (Wikipedia)]]
+ */
+@Experimental
+class AffinityPropagation private[clustering] (
+ private var maxIterations: Int,
+ private var lambda: Double,
+ private var normalization: Boolean) extends Serializable {
+
+ import org.apache.spark.mllib.clustering.AffinityPropagation._
+
+ /** Constructs a AP instance with default parameters: {maxIterations: 100, lambda: 0.5,
+ * normalization: false}.
+ */
+ def this() = this(maxIterations = 100, lambda = 0.5, normalization = false)
+
+ /**
+ * Set maximum number of iterations of the messaging iteration loop
+ */
+ def setMaxIterations(maxIterations: Int): this.type = {
+ this.maxIterations = maxIterations
+ this
+ }
+
+ /**
+ * Get maximum number of iterations of the messaging iteration loop
+ */
+ def getMaxIterations(): Int = {
+ this.maxIterations
+ }
+
+ /**
+ * Set lambda of the messaging iteration loop
+ */
+ def setLambda(lambda: Double): this.type = {
+ this.lambda = lambda
+ this
+ }
+
+ /**
+ * Get lambda of the messaging iteration loop
+ */
+ def getLambda(): Double = {
+ this.lambda
+ }
+
+ /**
+ * Set whether to do normalization or not
+ */
+ def setNormalization(normalization: Boolean): this.type = {
+ this.normalization = normalization
+ this
+ }
+
+ /**
+ * Get whether to do normalization or not
+ */
+ def getNormalization(): Boolean = {
+ this.normalization
+ }
+
+ /**
+ * Run the AP algorithm.
+ *
+ * @param similarities an RDD of (i, j, s,,ij,,) tuples representing the similarity matrix, which
+ * is the matrix S in the AP paper. The similarity s,,ij,, is set to
+ * real-valued similarities. This is not required to be a symmetric matrix
+ * and hence s,,ij,, can be not equal to s,,ji,,. Tuples with i = j are
+ * referred to as "preferences" in the AP paper. The data points with larger
+ * values of s,,ii,, are more likely to be chosen as exemplars.
+ *
+ * @param symmetric the given similarity matrix is symmetric or not. Default value: true
+ * @return a [[AffinityPropagationModel]] that contains the clustering result
+ */
+ def run(similarities: RDD[(Long, Long, Double)], symmetric: Boolean = true)
+ : AffinityPropagationModel = {
+ val s = constructGraph(similarities, normalization, symmetric)
+ ap(s)
+ }
+
+ /**
+ * Runs the AP algorithm.
+ *
+ * @param s The (normalized) similarity matrix, which is the matrix S in the AP paper with vertex
+ * similarities and the initial availabilities and responsibilities as its edge
+ * properties.
+ */
+ private def ap(s: Graph[Seq[Double], Seq[Double]]): AffinityPropagationModel = {
+ val g = apIter(s, maxIterations, lambda)
+ chooseExemplars(g)
+ }
+}
+
+private[clustering] object AffinityPropagation extends Logging {
+ /**
+ * Construct the similarity matrix (S) and do normalization if needed.
+ * Returns the (normalized) similarity matrix (S).
+ */
+ def constructGraph(similarities: RDD[(Long, Long, Double)], normalize: Boolean,
+ symmetric: Boolean):
+ Graph[Seq[Double], Seq[Double]] = {
+ val edges = similarities.flatMap { case (i, j, s) =>
+ if (symmetric && i != j) {
+ Seq(Edge(i, j, Seq(s, 0.0, 0.0)), Edge(j, i, Seq(s, 0.0, 0.0)))
+ } else {
+ Seq(Edge(i, j, Seq(s, 0.0, 0.0)))
+ }
+ }
+
+ if (normalize) {
+ val gA = Graph.fromEdges(edges, Seq(0.0))
+ val vD = gA.aggregateMessages[Seq[Double]](
+ sendMsg = ctx => {
+ ctx.sendToSrc(Seq(ctx.attr(0)))
+ },
+ mergeMsg = (s1, s2) => Seq(s1(0) + s2(0)),
+ TripletFields.EdgeOnly)
+ val normalized = GraphImpl.fromExistingRDDs(vD, gA.edges)
+ .mapTriplets(
+ e => {
+ val s = if (e.srcAttr(0) == 0.0) { e.attr(0) } else { e.attr(0) / e.srcAttr(0) }
+ Seq(s, 0.0, 0.0)
+ }, TripletFields.Src)
+ Graph.fromEdges(normalized.edges, Seq(0.0, 0.0))
--- End diff --
We already have the vertex RDD. Can we re-use it?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-75288067
I didn't see `cartesian` in your code. So the complexity is really `O(nnz * k)` but not `O(n^2 * k)`, correct? This is the same complexity as PIC/PageRank. If this is the case, let's check the code.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-90987246
[Test build #29872 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/29872/consoleFull) for PR 4622 at commit [`f031efd`](https://github.com/apache/spark/commit/f031efdb45dd7bd879297d4a9d7b31e9d9a8804f).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-74475569
[Test build #27546 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/27546/consoleFull) for PR 4622 at commit [`d469d12`](https://github.com/apache/spark/commit/d469d12257e68e437328a90d647a67bd002622f4).
* This patch merges cleanly.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-74484544
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/27546/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-74639094
[Test build #27622 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/27622/consoleFull) for PR 4622 at commit [`6dbec7d`](https://github.com/apache/spark/commit/6dbec7d451511d17f39750815d4a7d11da03561b).
* This patch **passes all tests**.
* This patch merges cleanly.
* This patch adds the following public classes _(experimental)_:
* `class AffinityPropagationModel(`
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092309
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
--- End diff --
`Option` is not Java friendly. Would `-1` work here?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-89915614
@viirya Any plan to update this PR?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-90694610
[Test build #29799 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/29799/consoleFull) for PR 4622 at commit [`68947bd`](https://github.com/apache/spark/commit/68947bd619650c5b25ef574d155a24bf97f0356a).
* This patch **passes all tests**.
* This patch merges cleanly.
* This patch adds the following public classes _(experimental)_:
* `class AffinityPropagationModel(`
* This patch does not change any dependencies.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91641037
[Test build #30037 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/30037/consoleFull) for PR 4622 at commit [`ffe06c3`](https://github.com/apache/spark/commit/ffe06c32fa892fc36a3a7f225ba8df256813e653).
* This patch **passes all tests**.
* This patch merges cleanly.
* This patch adds the following public classes _(experimental)_:
* `public class JavaAffinityPropagation `
* `case class AffinityPropagationCluster(val id: Long, val exemplar: Long, val members: Array[Long])`
* `class AffinityPropagationModel(`
* This patch does not change any dependencies.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by rxin <gi...@git.apache.org>.
Github user rxin commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-168112592
I'm going to close this pull request. If this is still relevant and you are interested in pushing it forward, please open a new pull request. Thanks!
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91016629
[Test build #29876 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/29876/consoleFull) for PR 4622 at commit [`250b6a4`](https://github.com/apache/spark/commit/250b6a40206b4a540432bb340ef598bef0dd457d).
* This patch **passes all tests**.
* This patch merges cleanly.
* This patch adds the following public classes _(experimental)_:
* `class AffinityPropagationModel(`
* This patch does not change any dependencies.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092363
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not
+ * require the number of clusters to be determined or estimated before running it. AP is developed
+ * by [[http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf Frey and Dueck]].
+ *
+ * @param maxIterations Maximum number of iterations of the AP algorithm.
+ *
+ * @see [[http://en.wikipedia.org/wiki/Affinity_propagation (Wikipedia)]]
+ */
+@Experimental
+class AffinityPropagation private[clustering] (
+ private var maxIterations: Int,
+ private var lambda: Double,
+ private var normalization: Boolean) extends Serializable {
+
+ import org.apache.spark.mllib.clustering.AffinityPropagation._
+
+ /** Constructs a AP instance with default parameters: {maxIterations: 100, lambda: 0.5,
+ * normalization: false}.
+ */
+ def this() = this(maxIterations = 100, lambda = 0.5, normalization = false)
+
+ /**
+ * Set maximum number of iterations of the messaging iteration loop
+ */
+ def setMaxIterations(maxIterations: Int): this.type = {
+ this.maxIterations = maxIterations
+ this
+ }
+
+ /**
+ * Get maximum number of iterations of the messaging iteration loop
+ */
+ def getMaxIterations(): Int = {
+ this.maxIterations
+ }
+
+ /**
+ * Set lambda of the messaging iteration loop
+ */
+ def setLambda(lambda: Double): this.type = {
+ this.lambda = lambda
+ this
+ }
+
+ /**
+ * Get lambda of the messaging iteration loop
+ */
+ def getLambda(): Double = {
+ this.lambda
+ }
+
+ /**
+ * Set whether to do normalization or not
+ */
+ def setNormalization(normalization: Boolean): this.type = {
+ this.normalization = normalization
+ this
+ }
+
+ /**
+ * Get whether to do normalization or not
+ */
+ def getNormalization(): Boolean = {
+ this.normalization
+ }
+
+ /**
+ * Run the AP algorithm.
+ *
+ * @param similarities an RDD of (i, j, s,,ij,,) tuples representing the similarity matrix, which
+ * is the matrix S in the AP paper. The similarity s,,ij,, is set to
+ * real-valued similarities. This is not required to be a symmetric matrix
+ * and hence s,,ij,, can be not equal to s,,ji,,. Tuples with i = j are
+ * referred to as "preferences" in the AP paper. The data points with larger
+ * values of s,,ii,, are more likely to be chosen as exemplars.
+ *
+ * @param symmetric the given similarity matrix is symmetric or not. Default value: true
+ * @return a [[AffinityPropagationModel]] that contains the clustering result
+ */
+ def run(similarities: RDD[(Long, Long, Double)], symmetric: Boolean = true)
+ : AffinityPropagationModel = {
+ val s = constructGraph(similarities, normalization, symmetric)
+ ap(s)
+ }
+
+ /**
+ * Runs the AP algorithm.
+ *
+ * @param s The (normalized) similarity matrix, which is the matrix S in the AP paper with vertex
+ * similarities and the initial availabilities and responsibilities as its edge
+ * properties.
+ */
+ private def ap(s: Graph[Seq[Double], Seq[Double]]): AffinityPropagationModel = {
+ val g = apIter(s, maxIterations, lambda)
+ chooseExemplars(g)
+ }
+}
+
+private[clustering] object AffinityPropagation extends Logging {
+ /**
+ * Construct the similarity matrix (S) and do normalization if needed.
+ * Returns the (normalized) similarity matrix (S).
+ */
+ def constructGraph(similarities: RDD[(Long, Long, Double)], normalize: Boolean,
+ symmetric: Boolean):
+ Graph[Seq[Double], Seq[Double]] = {
+ val edges = similarities.flatMap { case (i, j, s) =>
+ if (symmetric && i != j) {
+ Seq(Edge(i, j, Seq(s, 0.0, 0.0)), Edge(j, i, Seq(s, 0.0, 0.0)))
+ } else {
+ Seq(Edge(i, j, Seq(s, 0.0, 0.0)))
+ }
+ }
+
+ if (normalize) {
+ val gA = Graph.fromEdges(edges, Seq(0.0))
+ val vD = gA.aggregateMessages[Seq[Double]](
+ sendMsg = ctx => {
+ ctx.sendToSrc(Seq(ctx.attr(0)))
+ },
+ mergeMsg = (s1, s2) => Seq(s1(0) + s2(0)),
+ TripletFields.EdgeOnly)
+ val normalized = GraphImpl.fromExistingRDDs(vD, gA.edges)
+ .mapTriplets(
+ e => {
+ val s = if (e.srcAttr(0) == 0.0) { e.attr(0) } else { e.attr(0) / e.srcAttr(0) }
+ Seq(s, 0.0, 0.0)
+ }, TripletFields.Src)
+ Graph.fromEdges(normalized.edges, Seq(0.0, 0.0))
+ } else {
+ Graph.fromEdges(edges, Seq(0.0, 0.0))
+ }
+ }
+
+ /**
+ * Runs AP's iteration.
+ * @param g input graph with edges representing the (normalized) similarity matrix (S) and
+ * the initial availabilities and responsibilities.
+ * @param maxIterations maximum number of iterations.
+ * @return a [[Graph]] representing the final graph.
+ */
+ def apIter(
+ g: Graph[Seq[Double], Seq[Double]],
+ maxIterations: Int, lambda: Double): Graph[Seq[Double], Seq[Double]] = {
+ val tol = math.max(1e-5 / g.vertices.count(), 1e-8)
+ var prevDelta = (Double.MaxValue, Double.MaxValue)
+ var diffDelta = (Double.MaxValue, Double.MaxValue)
+ var curG = g
+ for (iter <- 0 until maxIterations
+ if math.abs(diffDelta._1) > tol || math.abs(diffDelta._2) > tol) {
+ val msgPrefix = s"Iteration $iter"
+
+ // update responsibilities
+ val vD_r = curG.aggregateMessages[Seq[Double]](
+ sendMsg = ctx => ctx.sendToSrc(Seq(ctx.attr(0) + ctx.attr(1))),
+ mergeMsg = _ ++ _,
+ TripletFields.EdgeOnly)
+
+ val updated_r = GraphImpl.fromExistingRDDs(vD_r, curG.edges)
+ .mapTriplets(
+ (e) => {
+ val filtered = e.srcAttr.filter(_ != (e.attr(0) + e.attr(1)))
+ val pool = if (filtered.size < e.srcAttr.size - 1) {
+ filtered.:+(e.attr(0) + e.attr(1))
+ } else {
+ filtered
+ }
+ val maxValue = if (pool.isEmpty) { 0.0 } else { pool.max }
--- End diff --
remove `{ ... }`
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-75284420
@mengxr have we decided no to include this algorithm? If so, please let me know. Then I will close this pr and maintain it as third-party package. Thanks!
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91321346
[Test build #29955 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/29955/consoleFull) for PR 4622 at commit [`6ad4905`](https://github.com/apache/spark/commit/6ad4905b0de5ac6ca9602ea30ce515bd75151221).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092359
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not
+ * require the number of clusters to be determined or estimated before running it. AP is developed
+ * by [[http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf Frey and Dueck]].
+ *
+ * @param maxIterations Maximum number of iterations of the AP algorithm.
+ *
+ * @see [[http://en.wikipedia.org/wiki/Affinity_propagation (Wikipedia)]]
+ */
+@Experimental
+class AffinityPropagation private[clustering] (
+ private var maxIterations: Int,
+ private var lambda: Double,
+ private var normalization: Boolean) extends Serializable {
+
+ import org.apache.spark.mllib.clustering.AffinityPropagation._
+
+ /** Constructs a AP instance with default parameters: {maxIterations: 100, lambda: 0.5,
+ * normalization: false}.
+ */
+ def this() = this(maxIterations = 100, lambda = 0.5, normalization = false)
+
+ /**
+ * Set maximum number of iterations of the messaging iteration loop
+ */
+ def setMaxIterations(maxIterations: Int): this.type = {
+ this.maxIterations = maxIterations
+ this
+ }
+
+ /**
+ * Get maximum number of iterations of the messaging iteration loop
+ */
+ def getMaxIterations(): Int = {
+ this.maxIterations
+ }
+
+ /**
+ * Set lambda of the messaging iteration loop
+ */
+ def setLambda(lambda: Double): this.type = {
+ this.lambda = lambda
+ this
+ }
+
+ /**
+ * Get lambda of the messaging iteration loop
+ */
+ def getLambda(): Double = {
+ this.lambda
+ }
+
+ /**
+ * Set whether to do normalization or not
+ */
+ def setNormalization(normalization: Boolean): this.type = {
+ this.normalization = normalization
+ this
+ }
+
+ /**
+ * Get whether to do normalization or not
+ */
+ def getNormalization(): Boolean = {
+ this.normalization
+ }
+
+ /**
+ * Run the AP algorithm.
+ *
+ * @param similarities an RDD of (i, j, s,,ij,,) tuples representing the similarity matrix, which
+ * is the matrix S in the AP paper. The similarity s,,ij,, is set to
+ * real-valued similarities. This is not required to be a symmetric matrix
+ * and hence s,,ij,, can be not equal to s,,ji,,. Tuples with i = j are
+ * referred to as "preferences" in the AP paper. The data points with larger
+ * values of s,,ii,, are more likely to be chosen as exemplars.
+ *
+ * @param symmetric the given similarity matrix is symmetric or not. Default value: true
+ * @return a [[AffinityPropagationModel]] that contains the clustering result
+ */
+ def run(similarities: RDD[(Long, Long, Double)], symmetric: Boolean = true)
+ : AffinityPropagationModel = {
+ val s = constructGraph(similarities, normalization, symmetric)
+ ap(s)
+ }
+
+ /**
+ * Runs the AP algorithm.
+ *
+ * @param s The (normalized) similarity matrix, which is the matrix S in the AP paper with vertex
+ * similarities and the initial availabilities and responsibilities as its edge
+ * properties.
+ */
+ private def ap(s: Graph[Seq[Double], Seq[Double]]): AffinityPropagationModel = {
+ val g = apIter(s, maxIterations, lambda)
+ chooseExemplars(g)
+ }
+}
+
+private[clustering] object AffinityPropagation extends Logging {
+ /**
+ * Construct the similarity matrix (S) and do normalization if needed.
+ * Returns the (normalized) similarity matrix (S).
+ */
+ def constructGraph(similarities: RDD[(Long, Long, Double)], normalize: Boolean,
+ symmetric: Boolean):
+ Graph[Seq[Double], Seq[Double]] = {
+ val edges = similarities.flatMap { case (i, j, s) =>
+ if (symmetric && i != j) {
+ Seq(Edge(i, j, Seq(s, 0.0, 0.0)), Edge(j, i, Seq(s, 0.0, 0.0)))
+ } else {
+ Seq(Edge(i, j, Seq(s, 0.0, 0.0)))
+ }
+ }
+
+ if (normalize) {
+ val gA = Graph.fromEdges(edges, Seq(0.0))
+ val vD = gA.aggregateMessages[Seq[Double]](
+ sendMsg = ctx => {
+ ctx.sendToSrc(Seq(ctx.attr(0)))
+ },
+ mergeMsg = (s1, s2) => Seq(s1(0) + s2(0)),
+ TripletFields.EdgeOnly)
+ val normalized = GraphImpl.fromExistingRDDs(vD, gA.edges)
+ .mapTriplets(
+ e => {
+ val s = if (e.srcAttr(0) == 0.0) { e.attr(0) } else { e.attr(0) / e.srcAttr(0) }
+ Seq(s, 0.0, 0.0)
+ }, TripletFields.Src)
+ Graph.fromEdges(normalized.edges, Seq(0.0, 0.0))
+ } else {
+ Graph.fromEdges(edges, Seq(0.0, 0.0))
+ }
+ }
+
+ /**
+ * Runs AP's iteration.
+ * @param g input graph with edges representing the (normalized) similarity matrix (S) and
+ * the initial availabilities and responsibilities.
+ * @param maxIterations maximum number of iterations.
+ * @return a [[Graph]] representing the final graph.
+ */
+ def apIter(
+ g: Graph[Seq[Double], Seq[Double]],
+ maxIterations: Int, lambda: Double): Graph[Seq[Double], Seq[Double]] = {
+ val tol = math.max(1e-5 / g.vertices.count(), 1e-8)
+ var prevDelta = (Double.MaxValue, Double.MaxValue)
+ var diffDelta = (Double.MaxValue, Double.MaxValue)
+ var curG = g
+ for (iter <- 0 until maxIterations
+ if math.abs(diffDelta._1) > tol || math.abs(diffDelta._2) > tol) {
+ val msgPrefix = s"Iteration $iter"
+
+ // update responsibilities
+ val vD_r = curG.aggregateMessages[Seq[Double]](
+ sendMsg = ctx => ctx.sendToSrc(Seq(ctx.attr(0) + ctx.attr(1))),
+ mergeMsg = _ ++ _,
+ TripletFields.EdgeOnly)
+
+ val updated_r = GraphImpl.fromExistingRDDs(vD_r, curG.edges)
+ .mapTriplets(
--- End diff --
same style issus
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r27930452
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not
+ * require the number of clusters to be determined or estimated before running it. AP is developed
+ * by [[http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf Frey and Dueck]].
+ *
+ * @param maxIterations Maximum number of iterations of the AP algorithm.
+ *
+ * @see [[http://en.wikipedia.org/wiki/Affinity_propagation (Wikipedia)]]
+ */
+@Experimental
+class AffinityPropagation private[clustering] (
+ private var maxIterations: Int,
+ private var lambda: Double,
+ private var normalization: Boolean) extends Serializable {
+
+ import org.apache.spark.mllib.clustering.AffinityPropagation._
+
+ /** Constructs a AP instance with default parameters: {maxIterations: 100, lambda: 0.5,
+ * normalization: false}.
+ */
+ def this() = this(maxIterations = 100, lambda = 0.5, normalization = false)
+
+ /**
+ * Set maximum number of iterations of the messaging iteration loop
+ */
+ def setMaxIterations(maxIterations: Int): this.type = {
+ this.maxIterations = maxIterations
+ this
+ }
+
+ /**
+ * Get maximum number of iterations of the messaging iteration loop
+ */
+ def getMaxIterations(): Int = {
+ this.maxIterations
+ }
+
+ /**
+ * Set lambda of the messaging iteration loop
+ */
+ def setLambda(lambda: Double): this.type = {
+ this.lambda = lambda
+ this
+ }
+
+ /**
+ * Get lambda of the messaging iteration loop
+ */
+ def getLambda(): Double = {
+ this.lambda
+ }
+
+ /**
+ * Set whether to do normalization or not
+ */
+ def setNormalization(normalization: Boolean): this.type = {
+ this.normalization = normalization
+ this
+ }
+
+ /**
+ * Get whether to do normalization or not
+ */
+ def getNormalization(): Boolean = {
+ this.normalization
+ }
+
+ /**
+ * Run the AP algorithm.
+ *
+ * @param similarities an RDD of (i, j, s,,ij,,) tuples representing the similarity matrix, which
+ * is the matrix S in the AP paper. The similarity s,,ij,, is set to
+ * real-valued similarities. This is not required to be a symmetric matrix
+ * and hence s,,ij,, can be not equal to s,,ji,,. Tuples with i = j are
+ * referred to as "preferences" in the AP paper. The data points with larger
+ * values of s,,ii,, are more likely to be chosen as exemplars.
+ *
+ * @param symmetric the given similarity matrix is symmetric or not. Default value: true
+ * @return a [[AffinityPropagationModel]] that contains the clustering result
+ */
+ def run(similarities: RDD[(Long, Long, Double)], symmetric: Boolean = true)
+ : AffinityPropagationModel = {
+ val s = constructGraph(similarities, normalization, symmetric)
+ ap(s)
+ }
+
+ /**
+ * Runs the AP algorithm.
+ *
+ * @param s The (normalized) similarity matrix, which is the matrix S in the AP paper with vertex
+ * similarities and the initial availabilities and responsibilities as its edge
+ * properties.
+ */
+ private def ap(s: Graph[Seq[Double], Seq[Double]]): AffinityPropagationModel = {
+ val g = apIter(s, maxIterations, lambda)
+ chooseExemplars(g)
+ }
+}
+
+private[clustering] object AffinityPropagation extends Logging {
+ /**
+ * Construct the similarity matrix (S) and do normalization if needed.
+ * Returns the (normalized) similarity matrix (S).
+ */
+ def constructGraph(similarities: RDD[(Long, Long, Double)], normalize: Boolean,
+ symmetric: Boolean):
+ Graph[Seq[Double], Seq[Double]] = {
+ val edges = similarities.flatMap { case (i, j, s) =>
+ if (symmetric && i != j) {
+ Seq(Edge(i, j, Seq(s, 0.0, 0.0)), Edge(j, i, Seq(s, 0.0, 0.0)))
+ } else {
+ Seq(Edge(i, j, Seq(s, 0.0, 0.0)))
+ }
+ }
+
+ if (normalize) {
+ val gA = Graph.fromEdges(edges, Seq(0.0))
+ val vD = gA.aggregateMessages[Seq[Double]](
+ sendMsg = ctx => {
+ ctx.sendToSrc(Seq(ctx.attr(0)))
+ },
+ mergeMsg = (s1, s2) => Seq(s1(0) + s2(0)),
+ TripletFields.EdgeOnly)
+ val normalized = GraphImpl.fromExistingRDDs(vD, gA.edges)
+ .mapTriplets(
+ e => {
+ val s = if (e.srcAttr(0) == 0.0) { e.attr(0) } else { e.attr(0) / e.srcAttr(0) }
+ Seq(s, 0.0, 0.0)
+ }, TripletFields.Src)
+ Graph.fromEdges(normalized.edges, Seq(0.0, 0.0))
--- End diff --
We can map attributes from `vD`. `fromEdges` needs to re-generate the vertex RDD, which could be expensive.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-74544855
[Test build #27556 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/27556/consoleFull) for PR 4622 at commit [`99d812a`](https://github.com/apache/spark/commit/99d812a77d858a1f8079a981d53f43c22109bba0).
* This patch **passes all tests**.
* This patch merges cleanly.
* This patch adds the following public classes _(experimental)_:
* `class AffinityPropagationModel(`
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092308
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
--- End diff --
Document the behavior if the given vertex doesn't belong to any cluster.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-74639103
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/27622/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-74484533
[Test build #27546 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/27546/consoleFull) for PR 4622 at commit [`d469d12`](https://github.com/apache/spark/commit/d469d12257e68e437328a90d647a67bd002622f4).
* This patch **passes all tests**.
* This patch merges cleanly.
* This patch adds the following public classes _(experimental)_:
* `class AffinityPropagationModel(`
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092362
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not
+ * require the number of clusters to be determined or estimated before running it. AP is developed
+ * by [[http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf Frey and Dueck]].
+ *
+ * @param maxIterations Maximum number of iterations of the AP algorithm.
+ *
+ * @see [[http://en.wikipedia.org/wiki/Affinity_propagation (Wikipedia)]]
+ */
+@Experimental
+class AffinityPropagation private[clustering] (
+ private var maxIterations: Int,
+ private var lambda: Double,
+ private var normalization: Boolean) extends Serializable {
+
+ import org.apache.spark.mllib.clustering.AffinityPropagation._
+
+ /** Constructs a AP instance with default parameters: {maxIterations: 100, lambda: 0.5,
+ * normalization: false}.
+ */
+ def this() = this(maxIterations = 100, lambda = 0.5, normalization = false)
+
+ /**
+ * Set maximum number of iterations of the messaging iteration loop
+ */
+ def setMaxIterations(maxIterations: Int): this.type = {
+ this.maxIterations = maxIterations
+ this
+ }
+
+ /**
+ * Get maximum number of iterations of the messaging iteration loop
+ */
+ def getMaxIterations(): Int = {
+ this.maxIterations
+ }
+
+ /**
+ * Set lambda of the messaging iteration loop
+ */
+ def setLambda(lambda: Double): this.type = {
+ this.lambda = lambda
+ this
+ }
+
+ /**
+ * Get lambda of the messaging iteration loop
+ */
+ def getLambda(): Double = {
+ this.lambda
+ }
+
+ /**
+ * Set whether to do normalization or not
+ */
+ def setNormalization(normalization: Boolean): this.type = {
+ this.normalization = normalization
+ this
+ }
+
+ /**
+ * Get whether to do normalization or not
+ */
+ def getNormalization(): Boolean = {
+ this.normalization
+ }
+
+ /**
+ * Run the AP algorithm.
+ *
+ * @param similarities an RDD of (i, j, s,,ij,,) tuples representing the similarity matrix, which
+ * is the matrix S in the AP paper. The similarity s,,ij,, is set to
+ * real-valued similarities. This is not required to be a symmetric matrix
+ * and hence s,,ij,, can be not equal to s,,ji,,. Tuples with i = j are
+ * referred to as "preferences" in the AP paper. The data points with larger
+ * values of s,,ii,, are more likely to be chosen as exemplars.
+ *
+ * @param symmetric the given similarity matrix is symmetric or not. Default value: true
+ * @return a [[AffinityPropagationModel]] that contains the clustering result
+ */
+ def run(similarities: RDD[(Long, Long, Double)], symmetric: Boolean = true)
+ : AffinityPropagationModel = {
+ val s = constructGraph(similarities, normalization, symmetric)
+ ap(s)
+ }
+
+ /**
+ * Runs the AP algorithm.
+ *
+ * @param s The (normalized) similarity matrix, which is the matrix S in the AP paper with vertex
+ * similarities and the initial availabilities and responsibilities as its edge
+ * properties.
+ */
+ private def ap(s: Graph[Seq[Double], Seq[Double]]): AffinityPropagationModel = {
+ val g = apIter(s, maxIterations, lambda)
+ chooseExemplars(g)
+ }
+}
+
+private[clustering] object AffinityPropagation extends Logging {
+ /**
+ * Construct the similarity matrix (S) and do normalization if needed.
+ * Returns the (normalized) similarity matrix (S).
+ */
+ def constructGraph(similarities: RDD[(Long, Long, Double)], normalize: Boolean,
+ symmetric: Boolean):
+ Graph[Seq[Double], Seq[Double]] = {
+ val edges = similarities.flatMap { case (i, j, s) =>
+ if (symmetric && i != j) {
+ Seq(Edge(i, j, Seq(s, 0.0, 0.0)), Edge(j, i, Seq(s, 0.0, 0.0)))
+ } else {
+ Seq(Edge(i, j, Seq(s, 0.0, 0.0)))
+ }
+ }
+
+ if (normalize) {
+ val gA = Graph.fromEdges(edges, Seq(0.0))
+ val vD = gA.aggregateMessages[Seq[Double]](
+ sendMsg = ctx => {
+ ctx.sendToSrc(Seq(ctx.attr(0)))
+ },
+ mergeMsg = (s1, s2) => Seq(s1(0) + s2(0)),
+ TripletFields.EdgeOnly)
+ val normalized = GraphImpl.fromExistingRDDs(vD, gA.edges)
+ .mapTriplets(
+ e => {
+ val s = if (e.srcAttr(0) == 0.0) { e.attr(0) } else { e.attr(0) / e.srcAttr(0) }
+ Seq(s, 0.0, 0.0)
+ }, TripletFields.Src)
+ Graph.fromEdges(normalized.edges, Seq(0.0, 0.0))
+ } else {
+ Graph.fromEdges(edges, Seq(0.0, 0.0))
+ }
+ }
+
+ /**
+ * Runs AP's iteration.
+ * @param g input graph with edges representing the (normalized) similarity matrix (S) and
+ * the initial availabilities and responsibilities.
+ * @param maxIterations maximum number of iterations.
+ * @return a [[Graph]] representing the final graph.
+ */
+ def apIter(
+ g: Graph[Seq[Double], Seq[Double]],
+ maxIterations: Int, lambda: Double): Graph[Seq[Double], Seq[Double]] = {
+ val tol = math.max(1e-5 / g.vertices.count(), 1e-8)
+ var prevDelta = (Double.MaxValue, Double.MaxValue)
+ var diffDelta = (Double.MaxValue, Double.MaxValue)
+ var curG = g
+ for (iter <- 0 until maxIterations
+ if math.abs(diffDelta._1) > tol || math.abs(diffDelta._2) > tol) {
+ val msgPrefix = s"Iteration $iter"
+
+ // update responsibilities
+ val vD_r = curG.aggregateMessages[Seq[Double]](
+ sendMsg = ctx => ctx.sendToSrc(Seq(ctx.attr(0) + ctx.attr(1))),
+ mergeMsg = _ ++ _,
+ TripletFields.EdgeOnly)
+
+ val updated_r = GraphImpl.fromExistingRDDs(vD_r, curG.edges)
+ .mapTriplets(
+ (e) => {
+ val filtered = e.srcAttr.filter(_ != (e.attr(0) + e.attr(1)))
+ val pool = if (filtered.size < e.srcAttr.size - 1) {
+ filtered.:+(e.attr(0) + e.attr(1))
--- End diff --
use `filtered :+ (a.attr(0) + e.attr(1)`
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91322337
[Test build #29956 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/29956/consoleFull) for PR 4622 at commit [`d70b70a`](https://github.com/apache/spark/commit/d70b70a4b2813ac8219cfe5f5e8c4c3e41f48c4b).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-89915963
@mengxr I will update this soon.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092334
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not
+ * require the number of clusters to be determined or estimated before running it. AP is developed
+ * by [[http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf Frey and Dueck]].
+ *
+ * @param maxIterations Maximum number of iterations of the AP algorithm.
+ *
+ * @see [[http://en.wikipedia.org/wiki/Affinity_propagation (Wikipedia)]]
+ */
+@Experimental
+class AffinityPropagation private[clustering] (
+ private var maxIterations: Int,
+ private var lambda: Double,
+ private var normalization: Boolean) extends Serializable {
+
+ import org.apache.spark.mllib.clustering.AffinityPropagation._
+
+ /** Constructs a AP instance with default parameters: {maxIterations: 100, lambda: 0.5,
+ * normalization: false}.
+ */
+ def this() = this(maxIterations = 100, lambda = 0.5, normalization = false)
+
+ /**
+ * Set maximum number of iterations of the messaging iteration loop
+ */
+ def setMaxIterations(maxIterations: Int): this.type = {
+ this.maxIterations = maxIterations
+ this
+ }
+
+ /**
+ * Get maximum number of iterations of the messaging iteration loop
+ */
+ def getMaxIterations(): Int = {
+ this.maxIterations
+ }
+
+ /**
+ * Set lambda of the messaging iteration loop
+ */
+ def setLambda(lambda: Double): this.type = {
+ this.lambda = lambda
+ this
+ }
+
+ /**
+ * Get lambda of the messaging iteration loop
+ */
+ def getLambda(): Double = {
+ this.lambda
+ }
+
+ /**
+ * Set whether to do normalization or not
+ */
+ def setNormalization(normalization: Boolean): this.type = {
+ this.normalization = normalization
+ this
+ }
+
+ /**
+ * Get whether to do normalization or not
+ */
+ def getNormalization(): Boolean = {
+ this.normalization
+ }
+
+ /**
+ * Run the AP algorithm.
+ *
+ * @param similarities an RDD of (i, j, s,,ij,,) tuples representing the similarity matrix, which
+ * is the matrix S in the AP paper. The similarity s,,ij,, is set to
+ * real-valued similarities. This is not required to be a symmetric matrix
+ * and hence s,,ij,, can be not equal to s,,ji,,. Tuples with i = j are
+ * referred to as "preferences" in the AP paper. The data points with larger
+ * values of s,,ii,, are more likely to be chosen as exemplars.
+ *
+ * @param symmetric the given similarity matrix is symmetric or not. Default value: true
+ * @return a [[AffinityPropagationModel]] that contains the clustering result
+ */
+ def run(similarities: RDD[(Long, Long, Double)], symmetric: Boolean = true)
+ : AffinityPropagationModel = {
+ val s = constructGraph(similarities, normalization, symmetric)
+ ap(s)
+ }
+
+ /**
+ * Runs the AP algorithm.
+ *
+ * @param s The (normalized) similarity matrix, which is the matrix S in the AP paper with vertex
+ * similarities and the initial availabilities and responsibilities as its edge
+ * properties.
+ */
+ private def ap(s: Graph[Seq[Double], Seq[Double]]): AffinityPropagationModel = {
+ val g = apIter(s, maxIterations, lambda)
+ chooseExemplars(g)
+ }
+}
+
+private[clustering] object AffinityPropagation extends Logging {
+ /**
+ * Construct the similarity matrix (S) and do normalization if needed.
+ * Returns the (normalized) similarity matrix (S).
+ */
+ def constructGraph(similarities: RDD[(Long, Long, Double)], normalize: Boolean,
+ symmetric: Boolean):
+ Graph[Seq[Double], Seq[Double]] = {
--- End diff --
Put this to the same line as the last argument.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91599267
[Test build #30031 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/30031/consoleFull) for PR 4622 at commit [`a485422`](https://github.com/apache/spark/commit/a485422d9793c6523be3ea92410c42280d75791f).
* This patch **passes all tests**.
* This patch merges cleanly.
* This patch adds the following public classes _(experimental)_:
* `public class JavaAffinityPropagation `
* `case class AffinityPropagationCluster(val id: Long, val exemplar: Long, val members: Array[Long])`
* `class AffinityPropagationModel(`
* This patch does not change any dependencies.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r27893348
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not
+ * require the number of clusters to be determined or estimated before running it. AP is developed
+ * by [[http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf Frey and Dueck]].
+ *
+ * @param maxIterations Maximum number of iterations of the AP algorithm.
+ *
+ * @see [[http://en.wikipedia.org/wiki/Affinity_propagation (Wikipedia)]]
+ */
+@Experimental
+class AffinityPropagation private[clustering] (
+ private var maxIterations: Int,
+ private var lambda: Double,
+ private var normalization: Boolean) extends Serializable {
+
+ import org.apache.spark.mllib.clustering.AffinityPropagation._
+
+ /** Constructs a AP instance with default parameters: {maxIterations: 100, lambda: 0.5,
+ * normalization: false}.
+ */
+ def this() = this(maxIterations = 100, lambda = 0.5, normalization = false)
+
+ /**
+ * Set maximum number of iterations of the messaging iteration loop
+ */
+ def setMaxIterations(maxIterations: Int): this.type = {
+ this.maxIterations = maxIterations
+ this
+ }
+
+ /**
+ * Get maximum number of iterations of the messaging iteration loop
+ */
+ def getMaxIterations(): Int = {
+ this.maxIterations
+ }
+
+ /**
+ * Set lambda of the messaging iteration loop
+ */
+ def setLambda(lambda: Double): this.type = {
+ this.lambda = lambda
+ this
+ }
+
+ /**
+ * Get lambda of the messaging iteration loop
+ */
+ def getLambda(): Double = {
+ this.lambda
+ }
+
+ /**
+ * Set whether to do normalization or not
+ */
+ def setNormalization(normalization: Boolean): this.type = {
+ this.normalization = normalization
+ this
+ }
+
+ /**
+ * Get whether to do normalization or not
+ */
+ def getNormalization(): Boolean = {
+ this.normalization
+ }
+
+ /**
+ * Run the AP algorithm.
+ *
+ * @param similarities an RDD of (i, j, s,,ij,,) tuples representing the similarity matrix, which
+ * is the matrix S in the AP paper. The similarity s,,ij,, is set to
+ * real-valued similarities. This is not required to be a symmetric matrix
+ * and hence s,,ij,, can be not equal to s,,ji,,. Tuples with i = j are
+ * referred to as "preferences" in the AP paper. The data points with larger
+ * values of s,,ii,, are more likely to be chosen as exemplars.
+ *
+ * @param symmetric the given similarity matrix is symmetric or not. Default value: true
--- End diff --
Do you mean to set `symmetric ` as a parameter of `AffinityPropagation`? Because it is closely related to the characters of the given `similarities`, I list it as a parameter of `run` method. But I don't feel strong about it.
I think if it is better to use other name instead of `symmetric`. This parameter indicates that `(i, j)` equals to `(j, i)`, so in order to avoid redundancy, the given `similarities` only cover triangular matrix. May just use `triangular`?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91641053
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/30037/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092300
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
--- End diff --
Please only import `mutable` and use `mutable.Map` and `mutable.Set` in the code. Sometimes, mixing the default `Map` with mutable `Map` causes problems that are hard to debug.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91402688
[Test build #29989 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/29989/consoleFull) for PR 4622 at commit [`22ef08e`](https://github.com/apache/spark/commit/22ef08e43fff3ad2bc1742620893b27441d8dd87).
* This patch **passes all tests**.
* This patch merges cleanly.
* This patch adds the following public classes _(experimental)_:
* `class AffinityPropagationModel(`
* This patch does not change any dependencies.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91319694
@mengxr The model is now distributed. Edge messages and vertex data are defined as private case classes too. I will try to add Java examples later.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092304
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
--- End diff --
So we store the entire clustering result to driver. How large could it be? It would be nice if we can store the model distributively. In PIC, the result is stored as `RDD[(Long, Int)]`. Please also consider Java users. Both `Seq` and `Set` are Scala collections. The best way to check this is to provide a Java example.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-74532945
[Test build #27556 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/27556/consoleFull) for PR 4622 at commit [`99d812a`](https://github.com/apache/spark/commit/99d812a77d858a1f8079a981d53f43c22109bba0).
* This patch merges cleanly.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092345
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not
+ * require the number of clusters to be determined or estimated before running it. AP is developed
+ * by [[http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf Frey and Dueck]].
+ *
+ * @param maxIterations Maximum number of iterations of the AP algorithm.
+ *
+ * @see [[http://en.wikipedia.org/wiki/Affinity_propagation (Wikipedia)]]
+ */
+@Experimental
+class AffinityPropagation private[clustering] (
+ private var maxIterations: Int,
+ private var lambda: Double,
+ private var normalization: Boolean) extends Serializable {
+
+ import org.apache.spark.mllib.clustering.AffinityPropagation._
+
+ /** Constructs a AP instance with default parameters: {maxIterations: 100, lambda: 0.5,
+ * normalization: false}.
+ */
+ def this() = this(maxIterations = 100, lambda = 0.5, normalization = false)
+
+ /**
+ * Set maximum number of iterations of the messaging iteration loop
+ */
+ def setMaxIterations(maxIterations: Int): this.type = {
+ this.maxIterations = maxIterations
+ this
+ }
+
+ /**
+ * Get maximum number of iterations of the messaging iteration loop
+ */
+ def getMaxIterations(): Int = {
+ this.maxIterations
+ }
+
+ /**
+ * Set lambda of the messaging iteration loop
+ */
+ def setLambda(lambda: Double): this.type = {
+ this.lambda = lambda
+ this
+ }
+
+ /**
+ * Get lambda of the messaging iteration loop
+ */
+ def getLambda(): Double = {
+ this.lambda
+ }
+
+ /**
+ * Set whether to do normalization or not
+ */
+ def setNormalization(normalization: Boolean): this.type = {
+ this.normalization = normalization
+ this
+ }
+
+ /**
+ * Get whether to do normalization or not
+ */
+ def getNormalization(): Boolean = {
+ this.normalization
+ }
+
+ /**
+ * Run the AP algorithm.
+ *
+ * @param similarities an RDD of (i, j, s,,ij,,) tuples representing the similarity matrix, which
+ * is the matrix S in the AP paper. The similarity s,,ij,, is set to
+ * real-valued similarities. This is not required to be a symmetric matrix
+ * and hence s,,ij,, can be not equal to s,,ji,,. Tuples with i = j are
+ * referred to as "preferences" in the AP paper. The data points with larger
+ * values of s,,ii,, are more likely to be chosen as exemplars.
+ *
+ * @param symmetric the given similarity matrix is symmetric or not. Default value: true
+ * @return a [[AffinityPropagationModel]] that contains the clustering result
+ */
+ def run(similarities: RDD[(Long, Long, Double)], symmetric: Boolean = true)
+ : AffinityPropagationModel = {
+ val s = constructGraph(similarities, normalization, symmetric)
+ ap(s)
+ }
+
+ /**
+ * Runs the AP algorithm.
+ *
+ * @param s The (normalized) similarity matrix, which is the matrix S in the AP paper with vertex
+ * similarities and the initial availabilities and responsibilities as its edge
+ * properties.
+ */
+ private def ap(s: Graph[Seq[Double], Seq[Double]]): AffinityPropagationModel = {
+ val g = apIter(s, maxIterations, lambda)
+ chooseExemplars(g)
+ }
+}
+
+private[clustering] object AffinityPropagation extends Logging {
+ /**
+ * Construct the similarity matrix (S) and do normalization if needed.
+ * Returns the (normalized) similarity matrix (S).
+ */
+ def constructGraph(similarities: RDD[(Long, Long, Double)], normalize: Boolean,
+ symmetric: Boolean):
+ Graph[Seq[Double], Seq[Double]] = {
+ val edges = similarities.flatMap { case (i, j, s) =>
+ if (symmetric && i != j) {
+ Seq(Edge(i, j, Seq(s, 0.0, 0.0)), Edge(j, i, Seq(s, 0.0, 0.0)))
+ } else {
+ Seq(Edge(i, j, Seq(s, 0.0, 0.0)))
+ }
+ }
+
+ if (normalize) {
+ val gA = Graph.fromEdges(edges, Seq(0.0))
+ val vD = gA.aggregateMessages[Seq[Double]](
+ sendMsg = ctx => {
+ ctx.sendToSrc(Seq(ctx.attr(0)))
+ },
+ mergeMsg = (s1, s2) => Seq(s1(0) + s2(0)),
+ TripletFields.EdgeOnly)
+ val normalized = GraphImpl.fromExistingRDDs(vD, gA.edges)
+ .mapTriplets(
+ e => {
+ val s = if (e.srcAttr(0) == 0.0) { e.attr(0) } else { e.attr(0) / e.srcAttr(0) }
--- End diff --
Remove `{ .. }` if you use `if ... else` in one line.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91342743
[Test build #29956 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/29956/consoleFull) for PR 4622 at commit [`d70b70a`](https://github.com/apache/spark/commit/d70b70a4b2813ac8219cfe5f5e8c4c3e41f48c4b).
* This patch **fails Spark unit tests**.
* This patch merges cleanly.
* This patch adds the following public classes _(experimental)_:
* `class AffinityPropagationModel(`
* This patch does not change any dependencies.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092310
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
--- End diff --
use this style for consistency:
~~~
cluster.foreach { cluster =>
...
}
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91337063
[Test build #29955 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/29955/consoleFull) for PR 4622 at commit [`6ad4905`](https://github.com/apache/spark/commit/6ad4905b0de5ac6ca9602ea30ce515bd75151221).
* This patch **fails Spark unit tests**.
* This patch merges cleanly.
* This patch adds the following public classes _(experimental)_:
* `class AffinityPropagationModel(`
* This patch does not change any dependencies.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91342764
Test FAILed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/29956/
Test FAILed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092331
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not
+ * require the number of clusters to be determined or estimated before running it. AP is developed
+ * by [[http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf Frey and Dueck]].
+ *
+ * @param maxIterations Maximum number of iterations of the AP algorithm.
+ *
+ * @see [[http://en.wikipedia.org/wiki/Affinity_propagation (Wikipedia)]]
+ */
+@Experimental
+class AffinityPropagation private[clustering] (
+ private var maxIterations: Int,
+ private var lambda: Double,
+ private var normalization: Boolean) extends Serializable {
+
+ import org.apache.spark.mllib.clustering.AffinityPropagation._
+
+ /** Constructs a AP instance with default parameters: {maxIterations: 100, lambda: 0.5,
+ * normalization: false}.
+ */
+ def this() = this(maxIterations = 100, lambda = 0.5, normalization = false)
+
+ /**
+ * Set maximum number of iterations of the messaging iteration loop
+ */
+ def setMaxIterations(maxIterations: Int): this.type = {
+ this.maxIterations = maxIterations
+ this
+ }
+
+ /**
+ * Get maximum number of iterations of the messaging iteration loop
+ */
+ def getMaxIterations(): Int = {
+ this.maxIterations
+ }
+
+ /**
+ * Set lambda of the messaging iteration loop
+ */
+ def setLambda(lambda: Double): this.type = {
+ this.lambda = lambda
+ this
+ }
+
+ /**
+ * Get lambda of the messaging iteration loop
+ */
+ def getLambda(): Double = {
+ this.lambda
+ }
+
+ /**
+ * Set whether to do normalization or not
+ */
+ def setNormalization(normalization: Boolean): this.type = {
+ this.normalization = normalization
+ this
+ }
+
+ /**
+ * Get whether to do normalization or not
+ */
+ def getNormalization(): Boolean = {
+ this.normalization
+ }
+
+ /**
+ * Run the AP algorithm.
+ *
+ * @param similarities an RDD of (i, j, s,,ij,,) tuples representing the similarity matrix, which
+ * is the matrix S in the AP paper. The similarity s,,ij,, is set to
+ * real-valued similarities. This is not required to be a symmetric matrix
+ * and hence s,,ij,, can be not equal to s,,ji,,. Tuples with i = j are
+ * referred to as "preferences" in the AP paper. The data points with larger
+ * values of s,,ii,, are more likely to be chosen as exemplars.
+ *
+ * @param symmetric the given similarity matrix is symmetric or not. Default value: true
--- End diff --
Could we set it as a parameter? Also document the expect input if `symmetric == true`. Do we expect both `(i, j)` and `(j, i)` in the input?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-74544862
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/27556/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-74622054
@mengxr okay.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-90992384
Test FAILed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/29872/
Test FAILed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91795886
[Test build #30067 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/30067/consoleFull) for PR 4622 at commit [`97cef01`](https://github.com/apache/spark/commit/97cef01f1e9f1bd2fcaa2d7718302c8ae79cf25a).
* This patch **passes all tests**.
* This patch merges cleanly.
* This patch adds the following public classes _(experimental)_:
* `public class JavaAffinityPropagation `
* `case class AffinityPropagationCluster(val id: Long, val exemplar: Long, val members: Array[Long])`
* `class AffinityPropagationModel(`
* This patch does not change any dependencies.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092316
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not
+ * require the number of clusters to be determined or estimated before running it. AP is developed
+ * by [[http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf Frey and Dueck]].
--- End diff --
Use DOI link: http://doi.org/10.1126/science.1136800
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91337081
Test FAILed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/29955/
Test FAILed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-75297368
@viirya I made a pass on the code. Some high-level feedback:
1. What is the expected size of the model? Should we store it distributively?
2. Defining a private case class to replace `Seq(Double, Double, Double)` would make the code much easier to read.
3. Please try to add a Java example, which helps test Java API compatibility.
I will go through the algorithm part again after 2).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092326
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not
+ * require the number of clusters to be determined or estimated before running it. AP is developed
+ * by [[http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf Frey and Dueck]].
+ *
+ * @param maxIterations Maximum number of iterations of the AP algorithm.
+ *
+ * @see [[http://en.wikipedia.org/wiki/Affinity_propagation (Wikipedia)]]
+ */
+@Experimental
+class AffinityPropagation private[clustering] (
+ private var maxIterations: Int,
+ private var lambda: Double,
+ private var normalization: Boolean) extends Serializable {
+
+ import org.apache.spark.mllib.clustering.AffinityPropagation._
+
+ /** Constructs a AP instance with default parameters: {maxIterations: 100, lambda: 0.5,
+ * normalization: false}.
+ */
+ def this() = this(maxIterations = 100, lambda = 0.5, normalization = false)
+
+ /**
+ * Set maximum number of iterations of the messaging iteration loop
+ */
+ def setMaxIterations(maxIterations: Int): this.type = {
+ this.maxIterations = maxIterations
+ this
+ }
+
+ /**
+ * Get maximum number of iterations of the messaging iteration loop
+ */
+ def getMaxIterations(): Int = {
+ this.maxIterations
+ }
+
+ /**
+ * Set lambda of the messaging iteration loop
+ */
+ def setLambda(lambda: Double): this.type = {
+ this.lambda = lambda
+ this
+ }
+
+ /**
+ * Get lambda of the messaging iteration loop
+ */
+ def getLambda(): Double = {
+ this.lambda
+ }
+
+ /**
+ * Set whether to do normalization or not
+ */
+ def setNormalization(normalization: Boolean): this.type = {
+ this.normalization = normalization
+ this
+ }
+
+ /**
+ * Get whether to do normalization or not
+ */
+ def getNormalization(): Boolean = {
+ this.normalization
+ }
+
+ /**
+ * Run the AP algorithm.
+ *
+ * @param similarities an RDD of (i, j, s,,ij,,) tuples representing the similarity matrix, which
+ * is the matrix S in the AP paper. The similarity s,,ij,, is set to
+ * real-valued similarities. This is not required to be a symmetric matrix
--- End diff --
So they could be negative?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by vanzin <gi...@git.apache.org>.
Github user vanzin commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91299289
> it has to add spark-hive as dependency of MLlib
spark-hive can be disabled (in fact it has to be explicitly enabled, it's disabled by default), while mllib cannot, so I guess that is a non-starter.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91304199
Thanks @vanzin, I think it might be a problem. I decided to move to custom method for median computation.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092335
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not
+ * require the number of clusters to be determined or estimated before running it. AP is developed
+ * by [[http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf Frey and Dueck]].
+ *
+ * @param maxIterations Maximum number of iterations of the AP algorithm.
+ *
+ * @see [[http://en.wikipedia.org/wiki/Affinity_propagation (Wikipedia)]]
+ */
+@Experimental
+class AffinityPropagation private[clustering] (
+ private var maxIterations: Int,
+ private var lambda: Double,
+ private var normalization: Boolean) extends Serializable {
+
+ import org.apache.spark.mllib.clustering.AffinityPropagation._
+
+ /** Constructs a AP instance with default parameters: {maxIterations: 100, lambda: 0.5,
+ * normalization: false}.
+ */
+ def this() = this(maxIterations = 100, lambda = 0.5, normalization = false)
+
+ /**
+ * Set maximum number of iterations of the messaging iteration loop
+ */
+ def setMaxIterations(maxIterations: Int): this.type = {
+ this.maxIterations = maxIterations
+ this
+ }
+
+ /**
+ * Get maximum number of iterations of the messaging iteration loop
+ */
+ def getMaxIterations(): Int = {
+ this.maxIterations
+ }
+
+ /**
+ * Set lambda of the messaging iteration loop
+ */
+ def setLambda(lambda: Double): this.type = {
+ this.lambda = lambda
+ this
+ }
+
+ /**
+ * Get lambda of the messaging iteration loop
+ */
+ def getLambda(): Double = {
+ this.lambda
+ }
+
+ /**
+ * Set whether to do normalization or not
+ */
+ def setNormalization(normalization: Boolean): this.type = {
+ this.normalization = normalization
+ this
+ }
+
+ /**
+ * Get whether to do normalization or not
+ */
+ def getNormalization(): Boolean = {
+ this.normalization
+ }
+
+ /**
+ * Run the AP algorithm.
+ *
+ * @param similarities an RDD of (i, j, s,,ij,,) tuples representing the similarity matrix, which
+ * is the matrix S in the AP paper. The similarity s,,ij,, is set to
+ * real-valued similarities. This is not required to be a symmetric matrix
+ * and hence s,,ij,, can be not equal to s,,ji,,. Tuples with i = j are
+ * referred to as "preferences" in the AP paper. The data points with larger
+ * values of s,,ii,, are more likely to be chosen as exemplars.
+ *
+ * @param symmetric the given similarity matrix is symmetric or not. Default value: true
+ * @return a [[AffinityPropagationModel]] that contains the clustering result
+ */
+ def run(similarities: RDD[(Long, Long, Double)], symmetric: Boolean = true)
+ : AffinityPropagationModel = {
+ val s = constructGraph(similarities, normalization, symmetric)
+ ap(s)
+ }
+
+ /**
+ * Runs the AP algorithm.
+ *
+ * @param s The (normalized) similarity matrix, which is the matrix S in the AP paper with vertex
+ * similarities and the initial availabilities and responsibilities as its edge
+ * properties.
+ */
+ private def ap(s: Graph[Seq[Double], Seq[Double]]): AffinityPropagationModel = {
+ val g = apIter(s, maxIterations, lambda)
+ chooseExemplars(g)
+ }
+}
+
+private[clustering] object AffinityPropagation extends Logging {
+ /**
+ * Construct the similarity matrix (S) and do normalization if needed.
+ * Returns the (normalized) similarity matrix (S).
+ */
+ def constructGraph(similarities: RDD[(Long, Long, Double)], normalize: Boolean,
+ symmetric: Boolean):
+ Graph[Seq[Double], Seq[Double]] = {
+ val edges = similarities.flatMap { case (i, j, s) =>
+ if (symmetric && i != j) {
+ Seq(Edge(i, j, Seq(s, 0.0, 0.0)), Edge(j, i, Seq(s, 0.0, 0.0)))
--- End diff --
Using `Seq(s, 0.0, 0.0)` may have performance issues. If the tuples are used frequently, we can define a case class for it. It also makes the code easier to read. It is definitely not clear to me what the second and the third values are.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092320
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not
+ * require the number of clusters to be determined or estimated before running it. AP is developed
+ * by [[http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf Frey and Dueck]].
+ *
+ * @param maxIterations Maximum number of iterations of the AP algorithm.
+ *
+ * @see [[http://en.wikipedia.org/wiki/Affinity_propagation (Wikipedia)]]
--- End diff --
`(Wikipedia)` -> `Affinity propagation (Wikipedia)`
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-74630811
[Test build #27622 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/27622/consoleFull) for PR 4622 at commit [`6dbec7d`](https://github.com/apache/spark/commit/6dbec7d451511d17f39750815d4a7d11da03561b).
* This patch merges cleanly.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-90995035
[Test build #29876 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/29876/consoleFull) for PR 4622 at commit [`250b6a4`](https://github.com/apache/spark/commit/250b6a40206b4a540432bb340ef598bef0dd457d).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-90652236
[Test build #29799 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/29799/consoleFull) for PR 4622 at commit [`68947bd`](https://github.com/apache/spark/commit/68947bd619650c5b25ef574d155a24bf97f0356a).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092321
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not
+ * require the number of clusters to be determined or estimated before running it. AP is developed
+ * by [[http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf Frey and Dueck]].
+ *
+ * @param maxIterations Maximum number of iterations of the AP algorithm.
+ *
+ * @see [[http://en.wikipedia.org/wiki/Affinity_propagation (Wikipedia)]]
+ */
+@Experimental
+class AffinityPropagation private[clustering] (
+ private var maxIterations: Int,
+ private var lambda: Double,
+ private var normalization: Boolean) extends Serializable {
+
+ import org.apache.spark.mllib.clustering.AffinityPropagation._
+
+ /** Constructs a AP instance with default parameters: {maxIterations: 100, lambda: 0.5,
--- End diff --
Put backticks around `0.5`. Otherwise, ScalaDoc will only show "... lambda: 0." as the preview.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91599290
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/30031/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092333
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not
+ * require the number of clusters to be determined or estimated before running it. AP is developed
+ * by [[http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf Frey and Dueck]].
+ *
+ * @param maxIterations Maximum number of iterations of the AP algorithm.
+ *
+ * @see [[http://en.wikipedia.org/wiki/Affinity_propagation (Wikipedia)]]
+ */
+@Experimental
+class AffinityPropagation private[clustering] (
+ private var maxIterations: Int,
+ private var lambda: Double,
+ private var normalization: Boolean) extends Serializable {
+
+ import org.apache.spark.mllib.clustering.AffinityPropagation._
+
+ /** Constructs a AP instance with default parameters: {maxIterations: 100, lambda: 0.5,
+ * normalization: false}.
+ */
+ def this() = this(maxIterations = 100, lambda = 0.5, normalization = false)
+
+ /**
+ * Set maximum number of iterations of the messaging iteration loop
+ */
+ def setMaxIterations(maxIterations: Int): this.type = {
+ this.maxIterations = maxIterations
+ this
+ }
+
+ /**
+ * Get maximum number of iterations of the messaging iteration loop
+ */
+ def getMaxIterations(): Int = {
+ this.maxIterations
+ }
+
+ /**
+ * Set lambda of the messaging iteration loop
+ */
+ def setLambda(lambda: Double): this.type = {
+ this.lambda = lambda
+ this
+ }
+
+ /**
+ * Get lambda of the messaging iteration loop
+ */
+ def getLambda(): Double = {
+ this.lambda
+ }
+
+ /**
+ * Set whether to do normalization or not
+ */
+ def setNormalization(normalization: Boolean): this.type = {
+ this.normalization = normalization
+ this
+ }
+
+ /**
+ * Get whether to do normalization or not
+ */
+ def getNormalization(): Boolean = {
+ this.normalization
+ }
+
+ /**
+ * Run the AP algorithm.
+ *
+ * @param similarities an RDD of (i, j, s,,ij,,) tuples representing the similarity matrix, which
+ * is the matrix S in the AP paper. The similarity s,,ij,, is set to
+ * real-valued similarities. This is not required to be a symmetric matrix
+ * and hence s,,ij,, can be not equal to s,,ji,,. Tuples with i = j are
+ * referred to as "preferences" in the AP paper. The data points with larger
+ * values of s,,ii,, are more likely to be chosen as exemplars.
+ *
+ * @param symmetric the given similarity matrix is symmetric or not. Default value: true
+ * @return a [[AffinityPropagationModel]] that contains the clustering result
+ */
+ def run(similarities: RDD[(Long, Long, Double)], symmetric: Boolean = true)
+ : AffinityPropagationModel = {
+ val s = constructGraph(similarities, normalization, symmetric)
+ ap(s)
+ }
+
+ /**
+ * Runs the AP algorithm.
+ *
+ * @param s The (normalized) similarity matrix, which is the matrix S in the AP paper with vertex
+ * similarities and the initial availabilities and responsibilities as its edge
+ * properties.
+ */
+ private def ap(s: Graph[Seq[Double], Seq[Double]]): AffinityPropagationModel = {
+ val g = apIter(s, maxIterations, lambda)
+ chooseExemplars(g)
+ }
+}
+
+private[clustering] object AffinityPropagation extends Logging {
+ /**
+ * Construct the similarity matrix (S) and do normalization if needed.
+ * Returns the (normalized) similarity matrix (S).
+ */
+ def constructGraph(similarities: RDD[(Long, Long, Double)], normalize: Boolean,
+ symmetric: Boolean):
--- End diff --
Chop down the arguments and use 4-space indentation.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r25092329
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
+ var i = 0
+ clusters.foreach(cluster => {
+ if (cluster.contains(vertexID)) {
+ return Some(i)
+ }
+ i += i
+ })
+ None
+ }
+}
+
+/**
+ * :: Experimental ::
+ *
+ * AffinityPropagation (AP), a graph clustering algorithm based on the concept of "message passing"
+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not
+ * require the number of clusters to be determined or estimated before running it. AP is developed
+ * by [[http://www.psi.toronto.edu/affinitypropagation/FreyDueckScience07.pdf Frey and Dueck]].
+ *
+ * @param maxIterations Maximum number of iterations of the AP algorithm.
+ *
+ * @see [[http://en.wikipedia.org/wiki/Affinity_propagation (Wikipedia)]]
+ */
+@Experimental
+class AffinityPropagation private[clustering] (
+ private var maxIterations: Int,
+ private var lambda: Double,
+ private var normalization: Boolean) extends Serializable {
+
+ import org.apache.spark.mllib.clustering.AffinityPropagation._
+
+ /** Constructs a AP instance with default parameters: {maxIterations: 100, lambda: 0.5,
+ * normalization: false}.
+ */
+ def this() = this(maxIterations = 100, lambda = 0.5, normalization = false)
+
+ /**
+ * Set maximum number of iterations of the messaging iteration loop
+ */
+ def setMaxIterations(maxIterations: Int): this.type = {
+ this.maxIterations = maxIterations
+ this
+ }
+
+ /**
+ * Get maximum number of iterations of the messaging iteration loop
+ */
+ def getMaxIterations(): Int = {
+ this.maxIterations
+ }
+
+ /**
+ * Set lambda of the messaging iteration loop
+ */
+ def setLambda(lambda: Double): this.type = {
+ this.lambda = lambda
+ this
+ }
+
+ /**
+ * Get lambda of the messaging iteration loop
+ */
+ def getLambda(): Double = {
+ this.lambda
+ }
+
+ /**
+ * Set whether to do normalization or not
+ */
+ def setNormalization(normalization: Boolean): this.type = {
+ this.normalization = normalization
+ this
+ }
+
+ /**
+ * Get whether to do normalization or not
+ */
+ def getNormalization(): Boolean = {
+ this.normalization
+ }
+
+ /**
+ * Run the AP algorithm.
+ *
+ * @param similarities an RDD of (i, j, s,,ij,,) tuples representing the similarity matrix, which
+ * is the matrix S in the AP paper. The similarity s,,ij,, is set to
+ * real-valued similarities. This is not required to be a symmetric matrix
+ * and hence s,,ij,, can be not equal to s,,ji,,. Tuples with i = j are
--- End diff --
`not equal to` -> `different from`
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-90644493
Test FAILed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/29798/
Test FAILed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91387899
[Test build #29989 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/29989/consoleFull) for PR 4622 at commit [`22ef08e`](https://github.com/apache/spark/commit/22ef08e43fff3ad2bc1742620893b27441d8dd87).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on the pull request:
https://github.com/apache/spark/pull/4622#issuecomment-91229215
@mengxr I have added a new function to automatically calculate the preferences used in AP algorithm. In fact, it just the median of similarities.
Because I use the function `percentile_approx` in Hive to calculate the median value, it has to add spark-hive as dependency of MLlib. I don't know if this is a good idea? How do you think?
If it is not, in order to provide this function to users, where it is better to put this in? Or it is better to implement a custom method to compute the median value?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5832][Mllib] Add Affinity Propagation c...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on a diff in the pull request:
https://github.com/apache/spark/pull/4622#discussion_r27893434
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala ---
@@ -0,0 +1,347 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.mllib.clustering
+
+import scala.collection.mutable.Map
+import scala.collection.mutable.Set
+
+import org.apache.spark.{Logging, SparkException}
+import org.apache.spark.annotation.Experimental
+import org.apache.spark.graphx._
+import org.apache.spark.graphx.impl.GraphImpl
+import org.apache.spark.rdd.RDD
+
+/**
+ * :: Experimental ::
+ *
+ * Model produced by [[AffinityPropagation]].
+ *
+ * @param clusters the vertexIDs of each cluster.
+ * @param exemplars the vertexIDs of all exemplars.
+ */
+@Experimental
+class AffinityPropagationModel(
+ val clusters: Seq[Set[Long]],
+ val exemplars: Seq[Long]) extends Serializable {
+
+ /**
+ * Set the number of clusters
+ */
+ def getK(): Int = clusters.size
+
+ /**
+ * Find the cluster the given vertex belongs
+ */
+ def findCluster(vertexID: Long): Set[Long] = {
+ clusters.filter(_.contains(vertexID))(0)
+ }
+
+ /**
+ * Find the cluster id the given vertex belongs
+ */
+ def findClusterID(vertexID: Long): Option[Int] = {
--- End diff --
ok, would work.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org