I am working on a k-means algorithm that embodies a step of variable weighting. In each step is assigned a different weight to each variable according to a contribution to the cluster measure. The algorithm starts with a random partition into k groups, a step that computes centers, a step that affect data, and a step that compute weights of variables, on so on until convergence (no cluster switches of points).
Now I would evaluate the sensitivity of the algorithm to the initialization (apart from the number of steps and time spent by each initialization). I take the same dataset, I execute the algo, and obtain a label for each object (obviously I obtain the means and the final sum of within error squares, but affected by the weights of the variables), I repeat this 100 times. In order to asses the sensitivity to initialization I can work only on the final configuration of the cluster labels, I cannot really compare the final criterion (it may have a different scale due to the weights), or I can compare the centers (if they are close enough (but how enough). I can compare for each couple of clustering a RandIndex and observe the distribution of it (but this can be time expensive 100x99/2 comparisons), or can I do something else?
Do you want to study the influence of the initial choice or to find a good initial choice. In the latter case, there are good heuristics, like starting from a subset of points as far as possible from each other.
The first, I want to study the influence of the initial choice, i.e. starting with a random partition, will I arrive to a esame result? I know the literature about good starting points (forma example, kmeans++).
From a random starting point, you arrive to the local optimum which is nearest from this point. Then, except when the clusters are well separated, you do not obtain the same result. These are the limits of local optimisation approaches: the final point is linked to the initial one by a strictly increasing path in the space of all possible partitions.
@Renato The paper is interesting, however, my problem is a bit different. If I have no apriori information (K-means is an exploratory method) about class structure, I can consider only what I ask to a clustering method. Classic K-means looks for spherical clusters, so, if in the reality clusters are not spherically shaped, K-means couldn't be a good choice. So, taken a particular clustering algorithm that is randomly initialized, I suppose that a stability evaluation should be done accordingly its capacity of reaching (more or less) always the same final configuration. Do you agree?
- Badges
- Science topic