2
$\begingroup$

Given n points, each with one of two assigned classes, I am looking for an efficient method to select two subsets, one per class, with k < n points. In the simplest terms, the selection should follow the criteria:

  1. The distance between points within a selected subset should be minimal.
  2. The distance between points from different subsets should be maximal.

I have found several methods to select a minimum or maximum distance, but not both for subsets with class constraints. I assume this is a known optimization problem, but I lack the terms to search for it. This solution should also be scalable to higher dimensions. It is okay if the solution is not optimal but a good approximation.

I am looking forward to any help!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Use Greedy optimization

  1. start with k random points per class
  2. minimize internal distance , by iterative swapping points to reduce total within subset distance
  3. maxmize enternal distance by choosing fathest points between subsets during swaps

here are details --

To solve your problem efficiently, use the Greedy Algorithm:

  1. Randomly select $k$ points from each class $A$ and $B$.

  2. Minimize the sum of pairwise distances within subsets $S_A$ and $S_B$.

    • Maximize distances between points in $S_A$ and $S_B$.

  3. Swap a point in $S_A$ (or $S_B$) with one outside if it improves: [ C = \alpha \cdot \text{SumInternalDistances} - (1 - \alpha) \cdot \text{SumExternalDistances} ] where $\alpha$ balances compactness vs. separation.

  4. Stop when no further improvement is possible.

For scalability:

  • Use KD-trees for faster distance computation in high dimensions.
  • For a good approximation, tune $\alpha$ empirically.

Tools:
Python with Scipy (distance.cdist), NumPy, or Gurobi for exact Mixed-Integer Programming (MIP) solutions. sorry for any bad writing or inconvenieces and hope this helps , also i would be thankful if someone edited my answer

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.