Most Cluster algorithms requires a full distance matrix and this won't work. Memory is one thing, and runtime the other thing.

There is a few algorithms who subsets your data first, do the clustering on the subset and then combine the results. One is implemented in R in package cluster, the function called clara(). You may try it but I'm in doubt if it will run, probably also the distance matrix is the input in the algorithm, which you hardly can compute.

One question which you might ask if a clustering of a subset of your data and combing the cluster information with your full data set could work?

Hello Matthias,

Thank you for replying to my question.

I am relatively new to cluster analysis (maybe 5 years), and I came up with an approach to such a problem, but I need feedback from the experts in the field.

I keep the clustering globally, but I change the resolution at each stage. I start with large units, followed by re-analyzing resulting clusters from stage 1 with finer units in stage 2, ... etc. I would be more comfortable here than with combining subsets.

Hello Paul,

Thank you for your suggestions. It appears to require a very fast computer, in addition to a specialized software, as you have explained above. I am trying to get the job done with what I currently have access to. My student is a Master's student and not a Ph.D. student. I involve my Master's students in such applied research. You propose to work up from step 4 to step 3 to step 2 to step 1, while I have been going step 1 first ... 

I am trying to do a cluster analysis with the disease surveillance software SaTScan. It creator (Martin Kulldorff, Harvard U) told me that I may need a faster computer than what I am using to try running SaTScan, but maybe the data set is too large.

www.satscan.org

The "ordering" of hundreds of air pollutants is based on toxicity, and the hazard score is a weighted sum or average of carcinogenic air elements. I want to get some relative ordering on each small geographical area in the 48 contiguous states.

If I understand your data analysis correctly, you want to cluster air pollutants in time and space which you will then use to created a weighted sum of toxicity for that spatial region?

Sounds relatively straightforward and shouldn't be too slow at all. You want to cluster the data based on 4 dimensions, lat, long, alt and time? (Or only 2 dimensions, lat & long?)

Then, for each cluster, create your weighted sum?

Clustering in 4 dimensions should be a matter of minutes at most. If your data has no time component and is at a fixed altitude then even easier! Clustering on 2 dims should take only seconds. (I just tested DDC on 2.5m samples, 3 dimensions and it took about 8 seconds.)

Heres how I would approach it:

1. Read only the data to cluster on (saves memory), this would be lat, long, alt(?), time(?)

2. use a density based clustering technique, select a radius to have a suitable geographical meaning (also a suitable time period if necessary)

3. run your clustering technique to find all the data samples within each cluster region (at each time step)

4. read the full data for each of these samples in each cluster and you now have the full list of air pollutants in each region

5. calculate your weighted sum for each region

You can now plot each cluster with it's centre, radius and toxicity value (at any given time step)

Simply use the cluster centres spatial information to find which cliuster belong to each 'block', or to each 'block group' etc

How does that sound?

Regards,

Richard

Hello Richard,

Thank you for your detailed feedback to my question. I need to know from you the following:

1. Which computer are you using?

2. Which cluster analysis software are you using? 

3. What does DDC stand for?

I am analyzing air quality data for the 48 contiguous States in the USA. When we try to use SaTScan for a cluster analysis, it does not seem to be manageable with our PC for 10 million values (lat, long, air quality score). We use circular shaped windows in SaTScan, with max window size 5% and with the Normal model. I wonder whether we are doing something  incorrectly or whether SaTScan requires a lot of memory due to the built-in Monte Carlo algorithm to estimate the p-values for the Likelihood Ratio values. Our "Step 3" does not run for so many values. I asked Martin Kulldorff (Harvard U) about it as he created SaTScan, and he told me that I would need a very fast computer to be able to run SaTScan with so many values, and this is not guaranteed to work either.

www.satscan.org

I am glad that now we have several people here giving us their expert opinions on how to succeed in running a cluster analysis on millions of data values. Maybe it is not as complicated as I have envisioned, but the person who is working with me on it  is very knowledgeable in working with very large data sets. I have forwarded to him your feedback, as I have done with the feedback by Matthias and Paul, of course.  

I we had been able to run a cluster analysis directly, we would not have been turning to a stepwise clustering approach.

Hi Raid,

I'm using a Dell Optiplex9010, Core-i7, 8GB RAM.

DDC is my own technique, you can see the paper on my profile page. It's been designed from the ground up to be memory efficient and quick so it should be faster than most. I have no problem sharing the code when it's 'finalised' but it's still very much 'development' code at the moment.

I'm not familiar with SaTScan, but at a quick glance it looks tailored to solving a specific problem. It does further analysis on the created clusters which may require high memory use? I can't see why it should need such a large amount of memory for the clustering itself unless it uses, e.g. hierarchical clustering at it's core andneeds the large distance matrix or some such.

SaTScan tests each cluster, and the testing may require more computing power. So the created clusters require a Monte Carlo simulation to obtain the p-values. This may be the reason why I could not run SaTScan on several hundred Gigabytes of data.

It is the Monte Carlo runs that require lots of memory, Martin Kulldorff just told me.

Hello Paul,

Thank you for your advise. One helpful result for p-values is the excellent approximation with the Gumbel distribution. You can reduce the number of MC runs from (say) 100,000 runs to get 5 decimal places to only 1000 runs and still be able to get p-values with 18 decimal places or so. 

I will give a talk or two on the stepwise approach that I have used to see what type of feedback I will get on it.

Here is a recording of my talk today on this issue.

https://sas.elluminate.com/mr.jnlp?suid=M.6B99EC3A89A2A1DC0ED82595632CC1&sid=uwf0707

Hi Raid,

I've watched the talk today and it's much clearer now. I think this is exactly the sort of thing I can help with. If I have understood it correctly then I believe we could cluster the 10m data samples you discuss in the first half of the talk in the way you want in minutes rather than hours.

I'd be very interested in discussing this with you further.

Hello Richard,

Best is to email me. I have received an email from Professor Angelov. You must have given him the link to my recorded lecture. Thanks.