# How to calculate IV, EV and optimal k for K-means?

Could someone explain how to calculate the following 3 evaluative properties:

• Intercluster Variability (IV) - How different are the data points within the same cluster
• Extracluster Variability (EV) - How different are the data points that are in distinct clusters
• Optimum value of k

The third one I believe is by min EV/IV

$C$ is a cluster, $c$ is centroid, $d$ is provided distance function, $\delta$ is Dirac measure, $x$ is element.
$IV = \sum \limits_C \sum \limits_{x \in C} d(x, c)$ meaning for each cluster calculate the sum of distances from it's centroid, and sum the results.

$EV = \frac{1}{N} \sum \limits_i \sum \limits_j\delta(C(x_i) \ne C(x_j))d(x_i, x_j)$ meaning sum the distances between elements from different clusters and divide the result by number of elements.
One possibility for optimal $k$ is to minimize $\frac{IV}{EV}$. But there are some other techniques of determining optimal number of clusters or referenced from there eight methods of finding $k$. In fact I would not state that any given method is better, preferable or can be determined blindly in advance, this is the part where you should define your optimum that makes sense to you, your data and outcome of what you use clusters for.

• Thank you very much for a great explanation of IV and EV. Regarding the optimal k, from these 8 methods which one would you recommend as the easiest to implement in java? – Tesla May 24 '16 at 14:23
• Use division from 3 point. If you have libraries, pick any that is built-in. Anyway this is not the best idea to pick one by the easiest implementation, it would be preferable to suit needs. – Evil May 24 '16 at 14:32

## How to get the optimal value for $k$?

You have to define a measure for optimiality. The problem with that is that with bigger $k$ most measures become smaller (better). One measure which is independent from $k$ is the silhouette coefficient:

Let $C = (C_1, \dots, C_k)$ be the clusters. Then:

• Average distance between an object $o$ and other objects in the same cluster: $$a(o) = \frac{1}{|C(o)|} \sum_{p \in C(o)} dist(o, p)$$
• Average distance to the next cluster: $$b(o) = \min_{C_i \in \text{Cluster} \setminus C(o)}(\frac{1}{C_i}) \sum_{p\in C_i} \sum_{p \in C_i} \text{dist}(o, p)$$
• Silhouette of an object: $$s(o) = \begin{cases}0 &\text{if } a(o) = 0, \text{i.e. } |C_i|=1\\ \frac{b(o)-a(o)}{\max(a(o), b(o))} &\text{otherwise}\end{cases}$$
• Silhouette of a clustering $C$: $$\text{silh}(C) = \frac{1}{|C|} \sum_{C_i \in C} \frac{1}{|C_i|} \sum_{o \in C_i} s(o)$$

You can see that $s(o) \in [-1, 1]$ and $\text{silh}(C) \in [-1, 1]$. Higher is better. Smaller than 0 is very bad.

Now you can start with $k=1$ and increase $k$ until $\text{silh}(C)$ gets smaller again.

However, there are alternatives to $k$-means clustering:

There isn't an optimum value for k, all you can do is use one which is not too bad! To do so (it's a maths approach), I use a PCA (principal components analysis) which gives me the proportion of variance explained by each axis of the eigen vectors. Suppose you have 10 variables and you see that 4 axis explained 90% of the variance, then you can set k to 4.

• could you explain how the PCA works ? – Tesla May 24 '16 at 13:43
• Although PCA is not that bad idea, it just makes components itself so making components to count them to make components once more by different method and call them clusters is not very optimal. @Tesla the question how PCA works is very broad, moreover there are at least 2 well known types (and at least 6 not that rare). Anyway it is nice to let people know if they are helpful. – Evil May 24 '16 at 15:10
• I'll try to explain briefly the PCA for you: suppose you have your data in matrix M nxd and v is a vector of size d, you want to find the v which maximizes t(v)*M*t under the hypothesis t(v)*v = 1. Solving it ends up that v is the eigen vector which corresponds to the biggest eigen value. That's the first axis of the PCA. Let's call it v1. Then you solve the same equation adding the hypothesis t(v)*v1 = 0, and you get the second axis etc... The d axis form a basis in which you can rewrite the columns (your variables) of your data. Now if you plot your data (express in the new basis) ... – galzra May 24 '16 at 16:24
• This is wrong. Applying PCA to the features doesn't help. You can have one dimensional data but any number of clusters. – Martin Thoma May 25 '16 at 8:44
• @Clemk I guess you just didn't get what they used PCA for or you just did a bad job explaining what you meant. If you meant it like I phrased it and the department does it like this, then yes, your department is doing it wrong. As I said, just think of a set of one-dimensional datapoints. There are $n$ clusters at integer positions $1, \dots, n$. They are perfect clusters, lets say 100 points each on exactly the integer position. Now what does PCA give you? – Martin Thoma May 25 '16 at 23:24