{"action":"created","comment":{"url":"https://api.github.com/repos/apache/spark/pulls/comments/29738695","id":29738695,"diff_hunk":"@@ -0,0 +1,475 @@\n+/*\n+ * Licensed to the Apache Software Foundation (ASF) under one or more\n+ * contributor license agreements.  See the NOTICE file distributed with\n+ * this work for additional information regarding copyright ownership.\n+ * The ASF licenses this file to You under the Apache License, Version 2.0\n+ * (the \"License\"); you may not use this file except in compliance with\n+ * the License.  You may obtain a copy of the License at\n+ *\n+ *    http://www.apache.org/licenses/LICENSE-2.0\n+ *\n+ * Unless required by applicable law or agreed to in writing, software\n+ * distributed under the License is distributed on an \"AS IS\" BASIS,\n+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n+ * See the License for the specific language governing permissions and\n+ * limitations under the License.\n+ */\n+\n+package org.apache.spark.mllib.clustering\n+\n+import scala.collection.mutable\n+\n+import org.apache.spark.{Logging, SparkException}\n+import org.apache.spark.annotation.Experimental\n+import org.apache.spark.api.java.JavaRDD\n+import org.apache.spark.graphx._\n+import org.apache.spark.graphx.impl.GraphImpl\n+import org.apache.spark.rdd.RDD\n+\n+/**\n+ * :: Experimental ::\n+ *\n+ * Model produced by [[AffinityPropagation]].\n+ *\n+ * @param id cluster id.\n+ * @param exemplar cluster exemplar.\n+ * @param members cluster members.\n+ */\n+@Experimental\n+case class AffinityPropagationCluster(val id: Long, val exemplar: Long, val members: Array[Long])\n+\n+/**\n+ * :: Experimental ::\n+ *\n+ * Model produced by [[AffinityPropagation]].\n+ *\n+ * @param clusters the clusters of AffinityPropagation clustering results.\n+ */\n+@Experimental\n+class AffinityPropagationModel(\n+    val clusters: RDD[AffinityPropagationCluster]) extends Serializable {\n+\n+  /**\n+   * Set the number of clusters\n+   */\n+  lazy val getK: Long = clusters.count()\n+ \n+  /**\n+   * Find the cluster the given vertex belongs\n+   * @param vertexID vertex id.\n+   * @return a [[Array]] that contains vertex ids in the same cluster of given vertexID. If\n+   *         the given vertex doesn't belong to any cluster, return null.\n+   */\n+  def findCluster(vertexID: Long): Array[Long] = {\n+    val cluster = clusters.filter(_.members.contains(vertexID)).collect()\n+    if (cluster.nonEmpty) {\n+      cluster(0).members\n+    } else {\n+      null\n+    }\n+  } \n+ \n+  /**\n+   * Find the cluster id the given vertex belongs to\n+   * @param vertexID vertex id.\n+   * @return the cluster id that the given vertex belongs to. If the given vertex doesn't belong to\n+   *         any cluster, return -1.\n+   */\n+  def findClusterID(vertexID: Long): Long = {\n+    val clusterIds = clusters.flatMap { cluster =>\n+      if (cluster.members.contains(vertexID)) {\n+        Seq(cluster.id)\n+      } else {\n+        Seq()\n+      }\n+    }.collect()\n+    if (clusterIds.nonEmpty) {\n+      clusterIds(0)\n+    } else {\n+      -1\n+    }\n+  } \n+}\n+\n+/**\n+ * The message exchanged on the node graph\n+ */\n+private case class EdgeMessage(\n+    similarity: Double,\n+    availability: Double,\n+    responsibility: Double) extends Equals {\n+  override def canEqual(that: Any): Boolean = {\n+    that match {\n+      case e: EdgeMessage =>\n+        similarity == e.similarity && availability == e.availability &&\n+          responsibility == e.responsibility\n+      case _ =>\n+        false\n+    }\n+  }\n+}\n+\n+/**\n+ * The data stored in each vertex on the graph\n+ */\n+private case class VertexData(availability: Double, responsibility: Double)\n+\n+/**\n+ * :: Experimental ::\n+ *\n+ * Affinity propagation (AP), a graph clustering algorithm based on the concept of \"message passing\"\n+ * between data points. Unlike clustering algorithms such as k-means or k-medoids, AP does not\n+ * require the number of clusters to be determined or estimated before running it. AP is developed\n+ * by [[http://doi.org/10.1126/science.1136800 Frey and Dueck]].\n+ *\n+ * @param maxIterations Maximum number of iterations of the AP algorithm.\n+ * @param lambda lambda parameter used in the messaging iteration loop\n+ * @param normalization Indication of performing normalization\n+ * @param symmetric Indication of using symmetric similarity input\n+ *\n+ * @see [[http://en.wikipedia.org/wiki/Affinity_propagation Affinity propagation (Wikipedia)]]\n+ */\n+@Experimental\n+class AffinityPropagation private[clustering] (\n+    private var maxIterations: Int,\n+    private var lambda: Double,\n+    private var normalization: Boolean,\n+    private var symmetric: Boolean) extends Serializable {\n+\n+  import org.apache.spark.mllib.clustering.AffinityPropagation._\n+\n+  /** Constructs a AP instance with default parameters: {maxIterations: 100, lambda: `0.5`,\n+   *    normalization: false, symmetric: true}.\n+   */\n+  def this() = this(maxIterations = 100, lambda = 0.5, normalization = false, symmetric = true)\n+\n+  /**\n+   * Set maximum number of iterations of the messaging iteration loop\n+   */\n+  def setMaxIterations(maxIterations: Int): this.type = {\n+    this.maxIterations = maxIterations\n+    this\n+  }\n+ \n+  /**\n+   * Get maximum number of iterations of the messaging iteration loop\n+   */\n+  def getMaxIterations(): Int = {\n+    this.maxIterations\n+  }\n+ \n+  /**\n+   * Set lambda of the messaging iteration loop\n+   */\n+  def setLambda(lambda: Double): this.type = {\n+    this.lambda = lambda\n+    this\n+  }\n+ \n+  /**\n+   * Get lambda of the messaging iteration loop\n+   */\n+  def getLambda(): Double = {\n+    this.lambda\n+  }\n+ \n+  /**\n+   * Set whether to do normalization or not\n+   */\n+  def setNormalization(normalization: Boolean): this.type = {\n+    this.normalization = normalization\n+    this\n+  }\n+ \n+  /**\n+   * Get whether to do normalization or not\n+   */\n+  def getNormalization(): Boolean = {\n+    this.normalization\n+  }\n+\n+  /**\n+   * Set whether the input similarities are symmetric or not.\n+   * When symmetric is set to true, we assume that input similarities only contain triangular\n+   * matrix. That means, only s,,ij,, is included in the similarities. If both s,,ij,, and\n+   * s,,ji,, are given in the similarities, it very possibly causes error.\n+   */\n+  def setSymmetric(symmetric: Boolean): this.type = {\n+    this.symmetric = symmetric\n+    this\n+  }\n+\n+  /**\n+   * Get whether the input similarities are symmetric or not\n+   */\n+  def getSymmetric(): Boolean = {\n+    this.symmetric\n+  }\n+\n+  /**\n+   * Calculate the median value of similarities\n+   */\n+  private def getMedian(similarities: RDD[(Long, Long, Double)]): Double = {\n+    import org.apache.spark.SparkContext._\n+\n+    val sorted = similarities.sortBy(_._3).zipWithIndex().map {\n+      case (v, idx) => (idx, v)\n+    }","path":"mllib/src/main/scala/org/apache/spark/mllib/clustering/AffinityPropagation.scala","position":217,"original_position":217,"commit_id":"97cef01f1e9f1bd2fcaa2d7718302c8ae79cf25a","original_commit_id":"97cef01f1e9f1bd2fcaa2d7718302c8ae79cf25a","user":{"login":"dbtsai","id":1134574,"avatar_url":"https://avatars.githubusercontent.com/u/1134574?v=3","gravatar_id":"","url":"https://api.github.com/users/dbtsai","html_url":"https://github.com/dbtsai","followers_url":"https://api.github.com/users/dbtsai/followers","following_url":"https://api.github.com/users/dbtsai/following{/other_user}","gists_url":"https://api.github.com/users/dbtsai/gists{/gist_id}","starred_url":"https://api.github.com/users/dbtsai/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dbtsai/subscriptions","organizations_url":"https://api.github.com/users/dbtsai/orgs","repos_url":"https://api.github.com/users/dbtsai/repos","events_url":"https://api.github.com/users/dbtsai/events{/privacy}","received_events_url":"https://api.github.com/users/dbtsai/received_events","type":"User","site_admin":false},"body":"Do you want to persistence the sorted RDD, and unpersistence later after you find the median? I will add type of `sorted` to explicitly indicate it's RDD. PS, `val count = sorted.count()` can be used to persistence the sorted RDD. ","created_at":"2015-05-06T07:21:40Z","updated_at":"2015-05-06T07:21:40Z","html_url":"https://github.com/apache/spark/pull/4622#discussion_r29738695","pull_request_url":"https://api.github.com/repos/apache/spark/pulls/4622","_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/comments/29738695"},"html":{"href":"https://github.com/apache/spark/pull/4622#discussion_r29738695"},"pull_request":{"href":"https://api.github.com/repos/apache/spark/pulls/4622"}}},"pull_request":{"url":"https://api.github.com/repos/apache/spark/pulls/4622","id":29357037,"html_url":"https://github.com/apache/spark/pull/4622","diff_url":"https://github.com/apache/spark/pull/4622.diff","patch_url":"https://github.com/apache/spark/pull/4622.patch","issue_url":"https://api.github.com/repos/apache/spark/issues/4622","number":4622,"state":"open","locked":false,"title":"[SPARK-5832][Mllib] Add Affinity Propagation clustering algorithm","user":{"login":"viirya","id":68855,"avatar_url":"https://avatars.githubusercontent.com/u/68855?v=3","gravatar_id":"","url":"https://api.github.com/users/viirya","html_url":"https://github.com/viirya","followers_url":"https://api.github.com/users/viirya/followers","following_url":"https://api.github.com/users/viirya/following{/other_user}","gists_url":"https://api.github.com/users/viirya/gists{/gist_id}","starred_url":"https://api.github.com/users/viirya/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/viirya/subscriptions","organizations_url":"https://api.github.com/users/viirya/orgs","repos_url":"https://api.github.com/users/viirya/repos","events_url":"https://api.github.com/users/viirya/events{/privacy}","received_events_url":"https://api.github.com/users/viirya/received_events","type":"User","site_admin":false},"body":"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).","created_at":"2015-02-16T08:44:27Z","updated_at":"2015-05-06T07:21:40Z","closed_at":null,"merged_at":null,"merge_commit_sha":"3c70000656f02f687e58cc2823dd40bad0a4ae7a","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/apache/spark/pulls/4622/commits","review_comments_url":"https://api.github.com/repos/apache/spark/pulls/4622/comments","review_comment_url":"https://api.github.com/repos/apache/spark/pulls/comments{/number}","comments_url":"https://api.github.com/repos/apache/spark/issues/4622/comments","statuses_url":"https://api.github.com/repos/apache/spark/statuses/97cef01f1e9f1bd2fcaa2d7718302c8ae79cf25a","head":{"label":"viirya:ap_clustering","ref":"ap_clustering","sha":"97cef01f1e9f1bd2fcaa2d7718302c8ae79cf25a","user":{"login":"viirya","id":68855,"avatar_url":"https://avatars.githubusercontent.com/u/68855?v=3","gravatar_id":"","url":"https://api.github.com/users/viirya","html_url":"https://github.com/viirya","followers_url":"https://api.github.com/users/viirya/followers","following_url":"https://api.github.com/users/viirya/following{/other_user}","gists_url":"https://api.github.com/users/viirya/gists{/gist_id}","starred_url":"https://api.github.com/users/viirya/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/viirya/subscriptions","organizations_url":"https://api.github.com/users/viirya/orgs","repos_url":"https://api.github.com/users/viirya/repos","events_url":"https://api.github.com/users/viirya/events{/privacy}","received_events_url":"https://api.github.com/users/viirya/received_events","type":"User","site_admin":false},"repo":{"id":21467907,"name":"spark-1","full_name":"viirya/spark-1","owner":{"login":"viirya","id":68855,"avatar_url":"https://avatars.githubusercontent.com/u/68855?v=3","gravatar_id":"","url":"https://api.github.com/users/viirya","html_url":"https://github.com/viirya","followers_url":"https://api.github.com/users/viirya/followers","following_url":"https://api.github.com/users/viirya/following{/other_user}","gists_url":"https://api.github.com/users/viirya/gists{/gist_id}","starred_url":"https://api.github.com/users/viirya/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/viirya/subscriptions","organizations_url":"https://api.github.com/users/viirya/orgs","repos_url":"https://api.github.com/users/viirya/repos","events_url":"https://api.github.com/users/viirya/events{/privacy}","received_events_url":"https://api.github.com/users/viirya/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/viirya/spark-1","description":"Mirror of Apache Spark","fork":true,"url":"https://api.github.com/repos/viirya/spark-1","forks_url":"https://api.github.com/repos/viirya/spark-1/forks","keys_url":"https://api.github.com/repos/viirya/spark-1/keys{/key_id}","collaborators_url":"https://api.github.com/repos/viirya/spark-1/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/viirya/spark-1/teams","hooks_url":"https://api.github.com/repos/viirya/spark-1/hooks","issue_events_url":"https://api.github.com/repos/viirya/spark-1/issues/events{/number}","events_url":"https://api.github.com/repos/viirya/spark-1/events","assignees_url":"https://api.github.com/repos/viirya/spark-1/assignees{/user}","branches_url":"https://api.github.com/repos/viirya/spark-1/branches{/branch}","tags_url":"https://api.github.com/repos/viirya/spark-1/tags","blobs_url":"https://api.github.com/repos/viirya/spark-1/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/viirya/spark-1/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/viirya/spark-1/git/refs{/sha}","trees_url":"https://api.github.com/repos/viirya/spark-1/git/trees{/sha}","statuses_url":"https://api.github.com/repos/viirya/spark-1/statuses/{sha}","languages_url":"https://api.github.com/repos/viirya/spark-1/languages","stargazers_url":"https://api.github.com/repos/viirya/spark-1/stargazers","contributors_url":"https://api.github.com/repos/viirya/spark-1/contributors","subscribers_url":"https://api.github.com/repos/viirya/spark-1/subscribers","subscription_url":"https://api.github.com/repos/viirya/spark-1/subscription","commits_url":"https://api.github.com/repos/viirya/spark-1/commits{/sha}","git_commits_url":"https://api.github.com/repos/viirya/spark-1/git/commits{/sha}","comments_url":"https://api.github.com/repos/viirya/spark-1/comments{/number}","issue_comment_url":"https://api.github.com/repos/viirya/spark-1/issues/comments{/number}","contents_url":"https://api.github.com/repos/viirya/spark-1/contents/{+path}","compare_url":"https://api.github.com/repos/viirya/spark-1/compare/{base}...{head}","merges_url":"https://api.github.com/repos/viirya/spark-1/merges","archive_url":"https://api.github.com/repos/viirya/spark-1/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/viirya/spark-1/downloads","issues_url":"https://api.github.com/repos/viirya/spark-1/issues{/number}","pulls_url":"https://api.github.com/repos/viirya/spark-1/pulls{/number}","milestones_url":"https://api.github.com/repos/viirya/spark-1/milestones{/number}","notifications_url":"https://api.github.com/repos/viirya/spark-1/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/viirya/spark-1/labels{/name}","releases_url":"https://api.github.com/repos/viirya/spark-1/releases{/id}","created_at":"2014-07-03T15:40:08Z","updated_at":"2015-03-23T06:46:39Z","pushed_at":"2015-05-06T03:09:34Z","git_url":"git://github.com/viirya/spark-1.git","ssh_url":"git@github.com:viirya/spark-1.git","clone_url":"https://github.com/viirya/spark-1.git","svn_url":"https://github.com/viirya/spark-1","homepage":null,"size":101031,"stargazers_count":0,"watchers_count":0,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"apache:master","ref":"master","sha":"e40ea8742a8771ecd46b182f45b5fcd8bd6dd725","user":{"login":"apache","id":47359,"avatar_url":"https://avatars.githubusercontent.com/u/47359?v=3","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"repo":{"id":17165658,"name":"spark","full_name":"apache/spark","owner":{"login":"apache","id":47359,"avatar_url":"https://avatars.githubusercontent.com/u/47359?v=3","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/apache/spark","description":"Mirror of Apache Spark","fork":false,"url":"https://api.github.com/repos/apache/spark","forks_url":"https://api.github.com/repos/apache/spark/forks","keys_url":"https://api.github.com/repos/apache/spark/keys{/key_id}","collaborators_url":"https://api.github.com/repos/apache/spark/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/apache/spark/teams","hooks_url":"https://api.github.com/repos/apache/spark/hooks","issue_events_url":"https://api.github.com/repos/apache/spark/issues/events{/number}","events_url":"https://api.github.com/repos/apache/spark/events","assignees_url":"https://api.github.com/repos/apache/spark/assignees{/user}","branches_url":"https://api.github.com/repos/apache/spark/branches{/branch}","tags_url":"https://api.github.com/repos/apache/spark/tags","blobs_url":"https://api.github.com/repos/apache/spark/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/apache/spark/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/apache/spark/git/refs{/sha}","trees_url":"https://api.github.com/repos/apache/spark/git/trees{/sha}","statuses_url":"https://api.github.com/repos/apache/spark/statuses/{sha}","languages_url":"https://api.github.com/repos/apache/spark/languages","stargazers_url":"https://api.github.com/repos/apache/spark/stargazers","contributors_url":"https://api.github.com/repos/apache/spark/contributors","subscribers_url":"https://api.github.com/repos/apache/spark/subscribers","subscription_url":"https://api.github.com/repos/apache/spark/subscription","commits_url":"https://api.github.com/repos/apache/spark/commits{/sha}","git_commits_url":"https://api.github.com/repos/apache/spark/git/commits{/sha}","comments_url":"https://api.github.com/repos/apache/spark/comments{/number}","issue_comment_url":"https://api.github.com/repos/apache/spark/issues/comments{/number}","contents_url":"https://api.github.com/repos/apache/spark/contents/{+path}","compare_url":"https://api.github.com/repos/apache/spark/compare/{base}...{head}","merges_url":"https://api.github.com/repos/apache/spark/merges","archive_url":"https://api.github.com/repos/apache/spark/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/apache/spark/downloads","issues_url":"https://api.github.com/repos/apache/spark/issues{/number}","pulls_url":"https://api.github.com/repos/apache/spark/pulls{/number}","milestones_url":"https://api.github.com/repos/apache/spark/milestones{/number}","notifications_url":"https://api.github.com/repos/apache/spark/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/apache/spark/labels{/name}","releases_url":"https://api.github.com/repos/apache/spark/releases{/id}","created_at":"2014-02-25T08:00:08Z","updated_at":"2015-05-06T07:20:08Z","pushed_at":"2015-05-06T07:02:23Z","git_url":"git://github.com/apache/spark.git","ssh_url":"git@github.com:apache/spark.git","clone_url":"https://github.com/apache/spark.git","svn_url":"https://github.com/apache/spark","homepage":null,"size":1618638,"stargazers_count":3869,"watchers_count":3869,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":3372,"mirror_url":"git://git.apache.org/spark.git","open_issues_count":303,"forks":3372,"open_issues":303,"watchers":3869,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/4622"},"html":{"href":"https://github.com/apache/spark/pull/4622"},"issue":{"href":"https://api.github.com/repos/apache/spark/issues/4622"},"comments":{"href":"https://api.github.com/repos/apache/spark/issues/4622/comments"},"review_comments":{"href":"https://api.github.com/repos/apache/spark/pulls/4622/comments"},"review_comment":{"href":"https://api.github.com/repos/apache/spark/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/apache/spark/pulls/4622/commits"},"statuses":{"href":"https://api.github.com/repos/apache/spark/statuses/97cef01f1e9f1bd2fcaa2d7718302c8ae79cf25a"}}}}