1
$\begingroup$

I know that k-mean/median is to find a set $F$ that minimize $$\sum_{i\in C}\min_{j \in F} d(i,j)$$ Where $C$ is set of clients and $F$ set of facilities. (For k-mean you just square the distance).

The thing I am confused about is what is k-center about? Is it similar to k-mean/median?

$\endgroup$
1
0
$\begingroup$

I have been doing research on this subject for quite some time. I faced a lot of confusion in the beginning, but now it is clear. The following is an answer close to completion:

The $k$-median problem is defined as follows: Given a set $C$ of clients and a set $L$ of facility locations defined over a distance metric $d$. Open a set $F$ of $k$ facility such that $F \subseteq L$ and the total cost of assigning the clients to their closest facilities is minimized, i.e.,

$$\text{minimize} \quad \Phi_C(F) \equiv \sum_{i \in C} \, \min_{j \in F} \big\{ d(j,i) \big\}$$

If the distance $d(.,.)$ is replaced with $d(.,.)^{2}$, it is known as the $k$-means problem (referenced from here).


In the $k$-center problem, there are two changes:

  1. $C = L$
  2. The objective function is to find $F\subseteq L$ of size $k$ that minimize $\max_{i \in C} \Big\{ \min_{j \in F} d(i,j) \Big\}$. That is, we aim to minimize the maximum distance from a client to the closest facility.

Now, when $C$ is not necessarily the same as $L$, the $k$-center problem is known as the $k$-supplier problem.


However, for the $k$-median and $k$-means problem, when $C= L$, there is no different name given for the problem. However, in very few pieces of literature, they call the $k$-means problem with $L = C$ as the $k$-medoid problem.


Summary: You should differentiate the $k$-median/$k$-means/$k$-center problems on the basis of the objective function only. The remaining details like if $C = L$ or not, must be taken from where you are reading it from. Different authors make different assumptions. Furthermore, these assumptions can be of the following form:

Type of Space:

  1. The space can be Euclidean, i.e., $d(.,.)$ is $\ell_{2}$ norm or Euclidean norm

  2. The space can be $\mathbb{R}^{d}$, with distance measure $d(.,.)$ as $\ell_{1}$ norm, i.e., taxi-cab norm. Be careful here: In the solution to this problem, the optimal center of a cluster is the co-ordinate median of the points in the cluster. Therefore, some people like to call this problem, the $k$-median problem.

  3. Likewise, space can be $\mathbb{R}^{d}$, but with distance functions: $\ell_{0},\dotsc, \ell_{\infty}$ (see this and related references for the studies done on this topic).

  4. The space can be non-metric also, where distances do not follow the properties of metric space, like symmetry, triangle inequality, etc. (see this and related references for the studies done on this topic)

Continuous or Discontinuous Space:

  1. In the $\mathbb{R}^{d}$ space, it possible that $L$ is given to you as a discrete/finte set of points in $\mathbb{R}^{d}$. More precisely, we call this problem as the discrete $k$-median/$k$-means/$k$-center problem.

  2. On the other hand, it is possible that the entire space $\mathbb{R}^{d}$ is the feasible set of facility locations, i.e., $L = \mathbb{R}^{d}$. We call this the continuous space. It means that there are infinitely many facility locations and also $C \subseteq L$. Therefore, an algorithm for discrete $k$-median/$k$-means/$k$-center will not work here. (see this and related references for the studies done on this topic)


Please let me know in the comments if you want me to add something more, in case I missed something.

$\endgroup$
4
  • $\begingroup$ I am doubting whether this is accurate. The statement of the $k$-means and $k$-medians problem that I am familiar with does not contain any requirement that $F \subseteq L$; it allows $F$ to be arbitrary. Have I misunderstood? $\endgroup$
    – D.W.
    Jun 23 at 7:22
  • $\begingroup$ @D.W. arbitrary means what precisely? $\endgroup$ Jun 23 at 7:23
  • $\begingroup$ It means that $F$ can be any subset of $\mathbb{R}^d$ (well, it has to have contain $k$ points). In particular, there is no input $L$ to the algorithm. $\endgroup$
    – D.W.
    Jun 23 at 7:24
  • $\begingroup$ @D.W. Yes that version is known as the continuous Euclidean $k$-median/$k$-means problem (if using $\ell_{2}$-norm as distance measure). The first definition is the most general definition. It encapsulates the definition that you are talking about. $\endgroup$ Jun 23 at 7:28
0
$\begingroup$

In the k-center problem, $F$ must be a subset of $C$; that is, you can only build facilities on top of clients.

In the k-mean/median problem, this is not required: you can build facilities anywhere in the metric space.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy