I'm trying to solve a clustering problem with size constrains.

Minimize $J=\sum_{i=1}^c\sum_{j=1}^n {{u_i}_j}^2{d_i}_j$

Subject to $\forall 1\le j\le n : \sum_{i=1}^c {{u_i}_j}=1$

and $\sum_{j=1}^n {{u_i}_j}=\frac nc$ (size constraint)

I used Lagrange multiplier method based on Fuzzy C-means algorithm, and got the formula

n=number of property $j\in[1,n]$

c=number of cluster $i\in[1,c]$

$L=\sum_{i=1}^c\sum_{j=1}^n {{u_i}_j}^2{d_i}_j+\sum_{j=1}^n\alpha_j(1-\sum_{i=1}^c {{u_i}_j})+\sum_{i=1}^c\beta_j(\frac nc-\sum_{j=1}^n {{u_i}_j})$

Then I took the partial derivatives of each variable and solved the system of linear equations using matrix method.

However, after the clusters returned are still uneven. I'm not sure why this doesn't work. There implementation should be correct. So I'm thinking it's the problem with the algorithm. Some how the sum of membership degree doesn't correlated to cluster size as I thought. I don't understand why is that. If this doesn't work, what are the other ways to solve this problem? Any comments are appreciated.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.