opened
viirya
username_0
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).
[SPARK-5832][Mllib] Add Affinity Propagation clustering algorithm
issue
created
mengxr
username_1
@username_0 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?
comment
created
viirya
username_0
@username_1 okay.
comment
created
viirya
username_0
@username_1 I updated the JIRA page. Please take a look. Thanks!
comment
created
viirya
username_0
@username_1 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!
comment
created
mengxr
username_1
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.
comment
created
mengxr
username_1
@username_0 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).
comment
created
mengxr
username_1
@username_0 Any plan to update this PR?
comment
created
viirya
username_0
@username_1 I will update this soon.
comment
created
viirya
username_0
@username_1 I updated for small comments. For the bigger ones, I will update later.
comment
created
viirya
username_0
@username_1 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?
comment
created
vanzin
username_2
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.
comment
created
viirya
username_0
Thanks @username_2, I think it might be a problem. I decided to move to custom method for median computation.
comment
created
viirya
username_0
@username_1 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.
comment
created
viirya
username_0
@username_1 I have addressed all your comments. Please take a look. Thanks.
comment
created
dbtsai
username_3
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.
comment
created
viirya
username_0
@username_3 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).
comment
created
dbtsai
username_3
@username_0 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.
comment
created
viirya
username_0
@username_1 any plan to revisit this and merge it?
comment
created
rxin
username_4
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!
comment