# Questions tagged [clustering]

Clustering is the problem of finding groups of data points (often modelled as nodes in a graph) that are closer to each other than to other points.

145 questions
Filter by
Sorted by
Tagged with
18 views

• 1
1 vote
86 views

### How to group thousand of data points for each user

I have thousands of data points associated with users. So a single user can have 2000-10000 data points. These data points are identified by contiguous numbers (e.g. all numbers from 0 to 2000). Each ...
1 vote
51 views

### Is n-dimentional assignment problem for points NP-hard?

We have $n$ sets of $k$ points in $\mathbb R^d$ and we are trying to partition them to $k$ clusters of $n$ points such that from each set every point is mapped to a different cluster and the sum of ...
81 views

### Is there an approximation algorithm for the three-person stable roommates problem?

While there's an algorithm for solving the stable roommates problem, I understand that the three-people-per-room version of that problem, sometimes called the "threesome roommates problem", ...
• 101
85 views

### How do I assign homes to hospitals based on locality? (clustering, kmeans?)

I have a large set of $(X)$ hospitals and $(Y)$ homes, where $(Y)$ is much larger than $(X)$, and their respective coordinates. Each hospital can handle any home within a 50 mile radius, and up to 10,...
1 vote
46 views

### Tips on speeding up hierarchical linkage clustering algorithm

I implemented a hierarchical linkage algorithm for a set of 5,000 points. Each point is defined with a longitude and a latitude. I read about this algorithm here. These are the steps: Compute ...
• 113
237 views

### Group time series events into minimal amount of buckets

I'm trying to efficiently compute events in a time series by grouping them into buckets. My goal is to have as few buckets as possible. The constraint is that events within one bucket are all within a ...
• 123
2k views

### Is there an online/offline tool that can perform K-means/median, given an initial centroid from the user?

The types of problems I am trying to solve are as follows: Given a set of co-ordinates such as: (1,2), (3,3), (6,2), (7,1), a value of k such as k=3 and an initial set of centroids such as c1=(2,2) ...
22 views

### Separating labelled points with a plane, minimizing label variance

Suppose we have observations with associated labels $\{({\bf x}_1, y_1), ({\bf x}_2, y_2), \dots, ({\bf x}_n, y_n)\}$ where ${\bf x}_i \in \mathbb{R}^d$ and $y_i \in \mathbb{R}$. Can we efficiently ...
• 13.6k
1 vote
I was reading Ke chen's paper about coreset construction for K-median clustering. In this paper, he assumed that $A$ is an $[α, β]$-bicriteria approximation for K-median clustering for some $α, β=O(1)$...