CODEWITHSUNDEEP
cluster-analysis
samarasa
samarasa

Reputation: 2125

An instance of online data clustering

I need to derive clusters of integers from an input array of integers in such a way that the variation within the clusters is minimized. (The integers or data values in the array are corresponding to the gas usage of 16 cars running between cities. At the end I will derive 4 clusters from the 16 cars into based on the clusters of the data values.)

Constraints: always the number of elements is 16, no. of clusters is 4 and the size of the cluster is 4.

One simple way I am planning to do is that I will sort the input array and then divide them into 4 groups as shown below. I think that I can also use k-means clustering.

However, the place where I stuck was as follows: The data in the array change over time. Basically I need to monitor the array for every 1 second and regroup/recluster them so that the variation within the cluster is minimized. Moreover, I need to satisfy the above constraint. For this, one idea I am getting is to select two groups based on their means and variations and move data values between the groups to minimize variation within the group. However, I am not getting any idea of how to select the data values to move between the groups and also how to select those groups. I cannot apply sorting on the array in every second because I cannot afford NlogN for every second. It would be great if you guide me to produce a simple solution.

sorted `input array: (12 14 16 16 18 19 20 21 24 26 27 29 29 30 31 32)`

cluster-1: (12  14 16 16)
cluster-2: (18 19 20 21)
cluster-3: (24 26 27 29)
cluster-4:  (29 30 31 32)

Upvotes: 0

Views: 231

Answers (1)

Has QUIT--Anony-Mousse
Has QUIT--Anony-Mousse

Reputation: 77485

Let me first point out that sorting a small number of objects is very fast. In particular when they have been sorted before, an "evil" bubble sort or insertion sort usually is linear. Consider in how many places the order may have changed! All of the classic complexity discussion doesn't really apply when the data fits into the CPUs first level caches.

Did you know that most QuickSort implementations fall back to insertion sort for small arrays? Because it does a fairly good job for small arrays and has little overhead.

All the complexity discussions are only for really large data sets. They are in fact proven only for inifinitely sized data. Before you reach infinity, a simple algorithm of higher complexity order may still perform better. And for n < 10, quadratic insertion sort often outperforms O(n log n) sorting.

k-means however won't help you much.

  1. Your data is one-dimensional. Do not bother to even look at multidimensional methods, they will perform worse than proper one-dimensional methods (which can exploit that the data can be ordered)
  2. If you want guaranteed runtime, k-means with possibly many iterations is quite uncontrolled.
  3. You can't easily add constraints such as the 4-cars rule into k-means

I believe the solution to your task (because of the data being 1 dimensional and the constraints you added) is:

Sort the integers
Divide the sorted list into k even-sized groups

Upvotes: 2

Related Questions