# What is the global function we are trying to Optimise with Clustering Algorithms?

I am doing some reading (and implementation) of some Clustering Algorithms.

First I started with the well known K-Mean algorithm and implemented it directly from a paper. Got a kind of decent understanding of what I going on there.

What I am actually interested in is Particle Swarm Optimisation based clustering.

For Particle Swarm Optimisation, you need to have a global fitness function that will (in this case) tell you how well clusters this is.

The general notion of well clustered I have found is that each cluster is compact. But how to express this mathematically?

I thought that we would go though each cluster and check its positional variance (away from its centroid).

For some cluster C :

$$\mu(C)=\dfrac{1}{|C|}\sum_{\forall\tilde{x}\in C}\tilde{x}$$

$$\sigma^{2}(C)=\sum_{\forall\tilde{x}\in C}\left(\tilde{x}-\mu(C)\right)^{2}$$

No point converting to standard deviation, unless using a gradient based optimization approach, which PSO is not.

then the global fitness would be to minimize the average variance, which is proportional to minimizing the total variance since we have a fixed number of clusters.

if $S$ is the set of all clusters the we are to minimise some function $g$.

$g_{mine}(S)=\sum_{\forall C\in S}\sigma^{2}(C)$

ie $$g_{mine}(S)=\sum_{\forall C\in S}\sum_{\forall\tilde{x}\in C}\left(\tilde{x}-\mu(C)\right)^{2}$$

According to 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

Equation 7 (Rewritten to use my notation)

$$g_{chen}(S)=\sum_{\forall C\in S}\sum_{\forall\tilde{x}\in X}(\tilde{x}-\mu(C))$$

The difference from what I had is the $\forall\tilde{x}\in X$, for $X$ the whole spaceof data rather than $\forall\tilde{x}\in C$.

This is what got me wondering if I was correct in the first place. as it can be seen that $g_{mine}\ne g_{chen}$. It can't since the extra points are going to change it and will not cancel since all variances are positive. However they are equivalent if $\forall S, S'$ $g_{mine}(S)\ge g_{mine}(S') \iff g_{chen}(S)\ge g_{chen}(S')$

In: Ahmadyfard, A. & Modares, H. Combining PSO and k-means to enhance data clustering Telecommunications, 2008. IST 2008. International Symposium on, 2008, 688-691

Equation 6 has: (again with notation switched)

$$g_{ahmadfard}(S)=\dfrac{1}{|X|} \sum_{\forall C\in S}\sum_{\forall\tilde{x}\in C}\left(\tilde{x}-\mu(C)\right)^{2}$$

This is equivalent to mine (at least in proportionality) as: $|X| \times g_{ahmadfard}(S) = g_{mine}$, and since $|X|>0$ thus $\forall S, S'$ $g_{mine}(S)\ge g_{mine}(S') \iff g_{ahmadfard}(S)\ge g_{ahmadfard}(S')$

Ye and Chen also came up with another function in: Ye, Fun, and Ching-Yi Chen. "Alternative KPSO-clustering algorithm." Tamkang Journal of science and Engineering 8.2 (2005): 165. It is very complicated and beyond the scope of this question

• What are the pros and cons of $g_{chen}$ vs $g_{mine}$ vs $g_{ahmadfard}$ ?
• What research have you done? There is tons written on clustering, and many possible metrics to measure how good a candidate clustering is. I suggest you start by reading some of the standard materials on clustering and familiarize yourself with standard metrics, then see which ones best meet your needs. There is no one right answer: different applications will call for different metric. Therefore, your question "Is this correct?" cannot be answered: there is no one correct answer. – D.W. Aug 31 '14 at 3:41
• @D.W. Sorry, I was called away before I could put in my references. I thought it was enough to get started with. I have now put in the references, to the two papers that got me thinking. I think the question is now much clearer? – Lyndon White Aug 31 '14 at 4:09
• @D.W. Have I satisified your request for information on what research I have done? – Lyndon White Sep 1 '14 at 12:37
• Yes. However, now it's not clear to me what your question is, as your question seems to contain multiple questions. If you question is, "what metric are Chen & Ye using?", it seems like you have answered your question. Same if your question is "what metrics are Ahmadyfard and Modares using?". If the question is "Is $g_{mine}$ reasonable?", again, it sounds like you have proposed an answer (anyway, that is a pretty subjective question). If the question is "What are the pros and cons of these three metrics?", that could be a fine question. – D.W. Sep 2 '14 at 7:05
• D.W: You are correct. I have removed the side questions, and left just the last, which is what I am really interested in. – Lyndon White Sep 2 '14 at 9:55