i have a dataset of thousands of points and a means of measuring the distance between any two points, but the data points have no dimensionality. i want an algorithm to find cluster centers in this dataset. i imagine that because the data has no dimensions, a cluster center might consist of several data points and a tolerance, and membership within the cluster might be determined by the average of the distance of a data point to every data point in the cluster center.please forgive me if this question has a well known solution, i know very little about this kind of problem! my (very limited) research has only turned up clustering algorithms for dimensional data, but i apologize in advance if i've missed something obvious.thank you!
clustering algorithm for non-dimensional data
machine learning;lg.learning;clustering
If the distance function is a metric, then you can employ either $k$-center clustering (where the maximum radius of a ball is minimized) or $k$-median clustering (which minimizes the sum of distances to cluster centers). $k$-center clustering is easy: merely pick the $k$-farthest points, and you're guaranteed to get a 2-approximation via triangle inequality (this is an old result due to Gonzalez).For $k$-median clustering, there's been a ton of work, too much to review here. Michael Shindler at UCLA has a nice survey of the main ideas. Both these problems are NP-hard in general, and are hard to approximate to within an arbitrary factor. Note that if you drop the condition of being a metric, things get a lot worse in terms of approximability. Another, more heuristic approach which might be ok for your application is to use a technique like MDS (multidimensional scaling) to embed your distance matrix in a Euclidean space, and then use one of many different Euclidean clustering methods (or even $k$-means clustering). If you are sure that your distance function is a metric, then you can do a slightly more intelligent embedding into Euclidean space and get a provable (albeit weak) guarantee on the quality of your answer. Ultimately, as with most clustering problems, your final choice depends on the application, your data size, and so on. 