# Lagrange Multiplier for fuzzy clustering with size constrains

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$

$d_{ij}$ is the distance from each element to it's cluster center. Usually euclidean, but I substitue this with the Haversine formula, since I'm working with geocoordiantes.

$U = u_{i,j} \in[0, 1],\; i = 1, . . . , n,\; j = 1, . . . , c$

$u_{ij}$ tells the degree to which element $\mathbf{x}_i$ belongs to cluster $\mathbf{c}_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})$

A dummy example:

I have 9 points to cluster into 3 groups, to solve the $u_{ij}$ matrix subject to sum of rows equals 1, and sum of columns equals 3(the average cluster size).

$$\begin{matrix} u_{11} & u_{12} & u_{13}\\ u_{21} & u_{22} & u_{23}\\ \vdots & \vdots & \vdots\\ u_{91} & u_{92} & u_{93} \end{matrix}$$

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.

I am not sure of the specifics of this algorithm (don't know what u and d are) but I think you need $u_{ij} \geq 0$ otherwise you can get negative membership (in fact for one negative $d_{ij}$ the objective function can be made $-\infty$.
Furthermore your relaxation will yield fractional assignment of clusters (since $u_{ij}$ need not be an integer.). If you do the final classification by chosing the maximum $u_{ij}$ over all $i$ for a fixed $j$ then it is no surprise that the clusters are uneven
• Hi, thanks for your help. I added the explanation for u and d in the post. d is the distance so it won't be negative. I'm choosing the maximum uij over all i for a fixed j. But to calculate the uij, I added the constraint $\sum_{j=1}^n {{u_i}_j}=\frac nc$ , and I think that should make sure uij are calculated evenly.. – qshng Apr 28 '15 at 15:14
• Suppose j=3 and $c=n$ and $u_{j}= [u_{1j}, u_{2j}, u_{3j}]$. Suppose $u_{1} = [0.4 0.33 0.33]$, $u_{2} =[0.4 0.33 0.34]$ and $u_{3} = [0.2, 0.34, 0.33]$, the cluster assignments will be 1,1 and 2, hence uneven clusters. – Sid Apr 28 '15 at 16:19
• Thanks, but I used two lagrange multipliers to constrain both the sum of all rows(to be 1) and columns(to equal the average). And your example doesn't meet the criteria. Since $sum(u_1)=1.06,sum(u_2)=1.06,sum(u_3)=0.88$ – qshng Apr 28 '15 at 18:45
• Ahh..sorry...see $u_{1} = [0.45, 0.15, 0.4]$ $u_{2} = [0.45, 0.3, 0.25]$ and $u_{3} = [0.1, 0.55, 0.35]$. The point holds in genereal. – Sid Apr 28 '15 at 22:25