5
$\begingroup$

Can anyone throw any light on any PTAS algorithm that I can apply for K-Clustering algorithm when the distance computation between the clustering points is costly.

In details, I have a set of N points and I have a customized distance metric between them. I want to compute a set of k clusters such that the cluster centers are far apart while among the clusters the points are very close. This customized distance metric is costly to calculate and hence I would like them to be calculated as less as it can possibly be.

I can give more clarification if required.

[EDIT] So the distance metric I have defined is $D(x,y) = 1 - \rho(x,y)$ where $\rho(x,y)$ is the Pearson Correlation Coefficient between points $x$ and $y$ ( $x$ and $y$ are data sets in themselves). Obviously to compute all such Pearson Correlations Coefficient when the number of data-points is 1000 (each set $x$ has another 1000 or so values within themselves) or so can be very expensive computationally.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ More clarification is required. These problems tend to be sensitive to the precise metric being optimized. $\endgroup$
    – Jeffε
    Feb 21, 2013 at 23:29
  • $\begingroup$ Please see edited problem $\endgroup$
    – rajaditya_m
    Feb 21, 2013 at 23:37

1 Answer 1

Reset to default
6
$\begingroup$

Have you seen this paper by Piotr Indyk ? It's old, but it's a good one. It solves a number of problems including k-median while making only sublinear number of calls to the distance oracle. It's not exactly the model you're looking for, but it does try to reduce the number of distance invocations.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. It does offer me some insights which can be the starting point for me to look for more optimized versions of this problem. $\endgroup$
    – rajaditya_m
    Feb 22, 2013 at 7:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.