1
$\begingroup$
    data=RandomReal[10,{30000}];
    FindClusters[data,2];

Why in this little data set, FindClusters Load so much memory?

and

    data=RandomReal[10,{number}];
    FindClusters[data,2];

and number before 5000(a proper number in your pc), the trend of memory size and timing is well.

My question is why dealing 30000 records should cost so much memory? Is it normal? How to overcome the problem?


I found one method is: convert to 2d data

data1=Transpose[{data,data}];
FindClusters[data1,5];
plots=Table[ListPlot[FindClusters[data1,n],AspectRatio->1,Frame->True,Axes->False,FrameTicks->None],{n,9}];
GraphicsGrid[Partition[plots,3]]

Another method is

data2=List/@data;
$\endgroup$

1 Answer 1

2
$\begingroup$

Although it is not clear from the Mathematica documentation, it appears that in the default Automatic method FindClusters[] may use an iterative algorithm to partition the data set into k clusters, compute a global merit function (such as sum of inter-point distances), then randomly select a point from one randomly selected cluster and assign that point to a different cluster, accepting this re-assignment if the global merit function is improved and then iterating until convergence. Such an iterative algorithm is appropriate in high-dimensional data, with large number of clusters and especially if the distance function is complicated, but it may be more rigorous than is necessary in some situations.

In particularly, your problem (as stated) is quite simple, and admits great reduction in computational cost at very minimal cost of accuracy. Finding two clusters amidst one-dimensional data corresponds to finding a single scalar, Theta, for which all points above Theta are in one cluster, all points below Theta in the other cluster. As such, you can partition your full data into subsets (technically called 'subsamples'), cluster each subsample to find the corresponding Theta, then average the resulting Thetas.

myThreshold[v_: List] := If[Min[v[[1]]] > Max[v[[2]]], (Min[v[[1]]] + Max[v[[2]]])/2, (Min[v[[2]]] + Max[v[[1]]])/2];

data = RandomReal[10, {30000}];

myPartitionedData = Partition[data, 500];

myClusterSet = FindClusters[#, 2] & /@ myPartitionedData;

Theta = Mean@(myThreshold /@ myClusterSet)

Then it is a simple matter to partition the full data into clusters of points above Theta and points below Theta:

myCluster1 = Select[data, # > Theta &];

myCluster2 = Complement[data, myCluster1]

This algorithm took 16 seconds on my Mac Pro and returned a threshold that was within 0.1% of that from the naive direct clustering of the full data set of 30000 points, which took a very long time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.