1
$\begingroup$

I use Minkoski distance to measure distance, like so: $$D(\vec{x}, \vec{y})=\left(\sum_{i=1}^n|x_i-y_i|^p\right)^\frac{1}{p}$$

I'm trying to locally optimize centroids by averaging the points that were assigned to the centroids. After using k-means with (p,k) when p is the distance measuring governing parameter and k is the number of centroids, I got the following results:

k-means inertia graph

This didn't make much sense to me, since I expected that when I use more centroids (when k is becoming larger), the inertia would become smaller. But it seems like the opposite is happening.
Can someone help me understand why is this happening?

Pseudo code:

inertia_means = []
inertia_medians = []
pks = []

for p in [1,2,3,4,5]
    for k in [4,8,16]:
        centroids_mean, partitions_mean = kmeans(X, k=k, distance_measure=p, np.mean)
        centroids_median, partitions_median = kmeans(X, k=k, distance_measure=p, np.median)
        inertia_means.append(np.mean(distance(X, partitions_mean, current_p) ** 2))
        inertia_medians.append(np.mean(distance(X, partitions_median, p) ** 2))
        pks.append(f'({p},{k})')

plt.plot(pks, inertia_means, label='mean criteria')
plt.plot(pks, inertia_medians, label='median criteria')
plt.legend()
plt.show()

So basically I'm going over all my p's and k's and running kmeans for each iteration on a given dataset X. Then I'm calculating the squared means of the distances to know the inertia, and then appending the (p,k) so I could plot them later.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ Although this terminology is unfortunately widespread in the literature, it'd be better to reserve the term k-means for minimising the within-clusters sum of squared Euclidean distances to the cluster centroids, as for this method the cluster centroids minimising the objective function are actually the means (hence the name). If the term is used for other distances such as L1 and other centroids such as medians (?), more than one possible definition exists, and therefore it is not fully clear what method you're talking about. $\endgroup$
    – Christian Hennig
    Jun 16, 2021 at 10:23
  • $\begingroup$ @Lewian My chart shows both medians and means, but my question refers specifically to the means $\endgroup$
    – Lilo
    Jun 16, 2021 at 10:26
  • 1
    $\begingroup$ Can you write down a formal definition of what was actually optimised using "k-means" (as I wrote this is a misnomer) with distances other than squared L2? As I wrote, more than one definition exists. Also it is not quite clear to me whether the inertia used here to compare different solutions is always the same as what was optimised by the method (which particularly would mean that inertias for different $p$ cannot be compared). $\endgroup$
    – Christian Hennig
    Jun 16, 2021 at 10:29
  • $\begingroup$ I should also say that regardless of what I find unclear, I share your suspicion that something's wrong with the results as inertia should not normally go up when $k$ increases. As you don't show any details of what you have done, it is not clear to us what went wrong here. Note also that algorithms only produce local optima of the objective function that may not be global, and for this reason it can occasionally happen that intertia goes up with $k$, but it shouldn't happen with the regularity seen here. $\endgroup$
    – Christian Hennig
    Jun 16, 2021 at 10:33
  • $\begingroup$ @Lewian I added more information, hope it helps understanding the context $\endgroup$
    – Lilo
    Jun 16, 2021 at 11:08

0

Reset to default

Your Answer

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