events.action: opened
events.author: viirya
events.text: 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).
events.title: [SPARK-5832][Mllib] Add Affinity Propagation clustering algorithm
events.type: issue
events.action: created
events.author: mengxr
events.text: @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?
events.type: comment
events.action: created
events.author: viirya
events.text: @mengxr okay.
events.type: comment
events.action: created
events.author: viirya
events.text: @mengxr I updated the JIRA page. Please take a look. Thanks!
events.type: comment
events.action: created
events.author: viirya
events.text: @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!
events.type: comment
events.action: created
events.author: mengxr
events.text: 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.
events.type: comment
events.action: created
events.author: mengxr
events.text: @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).
events.type: comment
events.action: created
events.author: mengxr
events.text: @viirya Any plan to update this PR?
events.type: comment
events.action: created
events.author: viirya
events.text: @mengxr I will update this soon.
events.type: comment
events.action: created
events.author: viirya
events.text: @mengxr I updated for small comments. For the bigger ones, I will update later.
events.type: comment
events.action: created
events.author: viirya
events.text: @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?
events.type: comment
events.action: created
events.author: vanzin
events.text: 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.
events.type: comment
events.action: created
events.author: viirya
events.text: Thanks @vanzin, I think it might be a problem. I decided to move to custom method for median computation.
events.type: comment
events.action: created
events.author: viirya
events.text: @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.
events.type: comment
events.action: created
events.author: viirya
events.text: @mengxr I have addressed all your comments. Please take a look. Thanks.
events.type: comment
events.action: created
events.author: dbtsai
events.text: General question. In euclidean space, the negative squared error is used as similarity. If we want to use affinity propagation to clustering lots of samples in euclidean space, it's impossible to create all the pairs of similarity data even it's symmetrical. What's the criteria to filter out those pairs which have very low similarity? Also, it's impossible to compute all the pairs of `RDD[Vector]` since it's O(N^2) operation, and how people address this in practice? 
  
  I really like this algorithm, but still have concern about how people can use it in practice. 
  
  Thanks.
events.type: comment
events.action: created
events.author: viirya
events.text: @dbtsai Thanks for comments and the question.
  I have no very good answer to the question. We have used a threshold to filter out the insignificant similarities of large scale data. As you said, it is impossible to compute all the pairs. However, the data we process is very high dimensional and very sparse, so the all-pair computation can be much reduced by only considering the pairs having corresponding dimensions with values more than zero (or a threshold defined).
events.type: comment
events.action: created
events.author: dbtsai
events.text: @viirya Maybe you can comment on this in the documentation and in the comment of the code, and it will be useful for people trying to understand the use-case.
events.type: comment
events.action: created
events.author: viirya
events.text: @mengxr any plan to revisit this and merge it?
events.type: comment
events.action: created
events.author: rxin
events.text: 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!
events.type: comment
data_with_bots.bot: [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.
data_with_bots.meta: This message directly preceded comment from bot *SparkQA* by author *viirya*:
data_with_bots.text: @mengxr okay.
data_with_bots.bot: [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(`
data_with_bots.meta: This message directly preceded comment from bot *SparkQA* by author *viirya*:
data_with_bots.text: @mengxr I updated the JIRA page. Please take a look. Thanks!
data_with_bots.bot: [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).
data_with_bots.meta: This message directly preceded comment from bot *SparkQA* by author *viirya*:
data_with_bots.text: @mengxr I updated for small comments. For the bigger ones, I will update later.
data_with_bots.bot: [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).
data_with_bots.meta: This message directly preceded comment from bot *SparkQA* by author *viirya*:
data_with_bots.text: @mengxr I have addressed all your comments. Please take a look. Thanks.
data_without_bots.meta: This message directly preceded comment from bot *SparkQA* by author *viirya*:
data_without_bots.text: @mengxr okay.
data_without_bots.meta: This message directly preceded comment from bot *SparkQA* by author *viirya*:
data_without_bots.text: @mengxr I updated the JIRA page. Please take a look. Thanks!
data_without_bots.meta: This message directly preceded comment from bot *SparkQA* by author *viirya*:
data_without_bots.text: @mengxr I updated for small comments. For the bigger ones, I will update later.
data_without_bots.meta: This message directly preceded comment from bot *SparkQA* by author *viirya*:
data_without_bots.text: @mengxr I have addressed all your comments. Please take a look. Thanks.