1
$\begingroup$

I wish to try clustering a matrix of numerical data using swarm intelligence. (Matrix is 28000 X 53 and sparse). I'm working in R and found the REPPlab package and used the EPPlab function. My question is how do I go from here to actually cluster my data? I know PSO can be used for clustering as well as optimisation but I'm stuck!

$\endgroup$
1

1 Answer 1

2
$\begingroup$

I know nothing of this package, or of R, but I do know PSO and clustering.

Intro:

In short PSO, can only be used for Optimization, but Clustering can be described as an optimization problem.

We have some a set of points in N-Dimentionals Space (the columns of your matrix), -- call this set $X$ we want to partition the points into several clusters, call the set of clusters: $S=\{C_1,C_2,...,C_k\}$.

For any cluster $C\in S$ we can find its centroid: $\mu(C)=\dfrac{1}{|C|} \sum\limits_{\forall x\in C}x$

and its variance: $\sigma^2(C)= \sum\limits_{\forall x\in C}{\left(x-\mu(C)\right)^2}$

What makes a clustering Good?

One way is: We would like to minimize the average variance of the clusters.

We can express this as an optimization function to minimize: $g_{fit}(S)=\dfrac{1}{|S|}{\sum\limits_{\forall C\in S}}\:{\sum\limits_{\forall x\in C}{\left(x-\mu(C)\right)^2}}$

By minimising the average varience we are saying we don't care for one over the others. It is worth making one cluster half as compact, to make another 3 times a compact.

Not that $\dfrac{1}{|S|}$ is a constant. The work of Ahmadyfard (see below), uses another constant factor: $\dfrac{1}{|X|}$, but it also doesn't matter -- Constants scaling factors don't change the performance of PSO at all.

This is not the only measure we could use. Chen and Ye's 2004 paper (below) uses: $g(S)={\sum\limits_{\forall C\in S}}{\sum\limits_{\forall x\in X}{\left(x-\mu(C)^2\right)}}$

Ye and Chen's 2005 paper uses a much, much more complex optimization function.

Both the above formula are scalar valued Optimization functions, parameterized by numerical values, in this case the numerical values are the locations of the Centroids of the clusters. Note: There is a isomorphism between the location of all the centroids and points $X$, and the membership of the clusters -- Simply assign cluster membership to the cluster with the closest centroid, or to go in reverse take the centroid using the mean equation above.

To explain with math: That function of assigning membership can be describes as being given by: $\mathcal{C}:Z\to S: z\mapsto C_i$. Where $Z$ is the set of all centroids. And $C_i$ is the ith cluster, which as $z$ as its centroid: Then we reexpress the fitness function:

$g_{fit}(Z=\{z_1,z_2,...,z_k\})=\dfrac{1}{|Z|}{\sum\limits_{\forall z \in Z}}\:{\sum\limits_{\forall x\in \mathcal{C}(z)}{\left(x-z\right)^2}}$

Since we have a numerical optimization function, we can now solve it with a PSO.

You should probably look into the methods that combine PSO with K-Mean.


References

  • Chen, C.-Y. & Ye, F. Particle swarm optimization algorithm and its application to clustering analysis Networking, Sensing and Control, 2004 IEEE International Conference on, 2004, 2, 789-794
  • Ye, F. & Chen, C.-Y. Alternative KPSO-clustering algorithm Tamkang Journal of science and Engineering, TAMKANG UNIVERSITY, 2005, 8, 165
  • Ahmadyfard, A. & Modares, H. Combining PSO and k-means to enhance data clustering Telecommunications, 2008. IST 2008. International Symposium on, 2008, 688-691

See also:

  • Rana, S.; Jasola, S. & Kumar, R. A review on particle swarm optimization algorithms and their applications to data clustering Artificial Intelligence Review, Springer, 2011, 35, 211-222
  • Tsai, C.-Y. & Kao, I.-W. Particle swarm optimization with selective particle regeneration for data clustering Expert Systems with Applications, Elsevier, 2011, 38, 6565-6576
$\endgroup$

Your Answer

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