1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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.. $\endgroup$
    – qshng
    Commented Apr 28, 2015 at 15:14
  • $\begingroup$ 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. $\endgroup$
    – Sid
    Commented Apr 28, 2015 at 16:19
  • $\begingroup$ 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$ $\endgroup$
    – qshng
    Commented Apr 28, 2015 at 18:45
  • $\begingroup$ 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. $\endgroup$
    – Sid
    Commented Apr 28, 2015 at 22:25
  • $\begingroup$ Hmm... Looks like my method was wrong. So what do you think would be a good way to make the cluster even? $\endgroup$
    – qshng
    Commented Apr 28, 2015 at 22:31

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.