# Double-Constraint Fuzzy Clustering Algorithm
## 2 Related Work  
Let \(X=\{x_{i}\,|\,i=1,\,2,\,\ldots,\,n\}\) be a dataset with \(n\) data objects distributed in \(c\) clusters, \(x_{i}\)\(\in\)\(R^{d}\) in a \(d\)-dimensional data space. Four typical fuzzy clustering algorithms are reviewed as follows.  
1. [label=(0)]
2. [PERSON]'s FCM: the objective function in FCM can be stated as \[\min/(U,V)=\sum_{i=1}^{c}\sum_{j=1}^{n}u_{ij}^{m}d_{ij}^{2},\,\,\,\,s.t.\sum_{ i=1}^{c}u_{ij}=1,\,j=1,2,\ldots,n,0<\sum_{j=1}^{n}u_{ij}\leq n,\] (1) where \(d_{ij}=\)\(\big{|}\big{|}x_{j}-v_{i}\big{|}\big{|}\), \(v_{i}\) is the prototype (center) of \(i\)th cluster, \(u_{ij}\) the membership degree of \(j\)th point to \(i\)th cluster, \(m\) a fuzziness exponent, ranging in the interval [1; 3]. By the Lagrange multiplier optimization algorithm [25], the optimal membership and prototype functions of (1) is \[u_{ij}=(\sum_{r=1}^{c}d_{ij}^{2/(m-1)}/d_{rj}^{2/(m-1)})^{-1}\text{ and }v_{i}=\sum_{j=1}^{n}u^{m}_{ij}x_{j}/\sum_{j=1}^{n}u^{m}_{ij}.\] (2) All fuzzy membership degrees consist of a \(n\times c\) fuzzy partition matrix \(U=[u_{ij}]\). FCM has frequently been criticized as it cannot show the typicality (importance) or compatibility of points with clusters [6; 12], and thus the following algorithm was proposed.
3. [PERSON]'s conditional FCM (CFCM): Let \(w_{j}\) be the importance degree of \(j\)th point, Equation (1) in CFCM turns into \[\min/(U,V)=\sum_{i=1}^{c}\sum_{j=1}^{n}u_{ij}^{m}d_{ij}^{2},\,\,\,s.t.\sum_{i=1 }^{c}u_{ij}=w_{j},\,j=1,2,\ldots,n,\,\,0<\sum_{j=1}^{n}u_{ij}\leq n.\] (3)The membership degree of \(j\)th point to \(i\)th cluster in FCM is conducted as  
\[u_{ij}=w_{j}/(\sum_{r=1}^{c}d_{ij}^{2/(m-1)}/d_{rj}^{2/(m-1)}). \tag{4}\]  
The computation equation of the center \(v_{i}\) in CFCM is the same as in the case of FCM, \(i=1,2,\ldots,c\). The use of CFCM can enhance the typicality of different clusters and increase the accuracy of FCM. But CFCM only focuses on the typicality of points rather than clusters.
3. [PERSON] et al.'s possibilistic c-means (PCM): Along the objective function of FCM, PCM is formulated as \[\min J(U,V)=\sum_{i=1}^{c}\sum_{j=1}^{n}\left\{u_{ij}^{m}d_{ij}^{2}+(1-u_{ij} )^{m}\eta_{ij}\right),\ \ s.t.\ 0<\sum_{j=1}^{n}u_{ij}\leq n.\] (5) From (5), the optimal membership function is \[u_{ij}=\left\{1+\left(d_{ij}^{2}/\eta_{i}\right)^{1/(m-1)}\right\}^{-1},\ i=1,\ 2,\ \ldots,\ c\] (6) where \(\eta_{i}\) is associated with the size of each cluster, it is computed as \[\eta_{i}=\sum_{j=1}^{n}u_{ij}^{m}d_{ij}^{2}/\sum_{j=1}^{n}u_{ij}^{m}.\] (7) PCM can effectively stress the typicality of points but must strongly depend on an initialization procedure. In practice, FCM can realize this purpose [12].
4. [PERSON] et al.'s constrained CM (CCM): Equation (1) in FCM is turned into \[\min J(U,V)=\sum_{i=1}^{c}\sum_{j=1}^{n}u_{ij}^{m}d_{ij}^{2},\ s.t.\ \sum_{j=1}^{n}u_{ij}=w_{i},i=1,2,\ldots,c,\ u_{ij}=0\ or 1.\] (8) From (8), the clustering center is \[v_{i}=\sum_{j=1}^{n}u_{ij}x_{j}/\sum_{j=1}^{n}u_{ij},\ i=1,2,\ldots,c.\] (9)  
The optimal membership function \(u_{ij}\) in CCM turns into the typical transportation problem (see [19]) that can be solved by a set of existing algorithms. But the computational complexity of these algorithms is too large to be applied in large dataset.  
These algorithms have their own applicable ranges and limitations but cannot provide an assessment that utilizes the information on both data objects and clusters. Nevertheless, these constraints are not only helpful to boost clustering quality but also meet mandatory application requirements. In this paper, we propose a new method to solve these problems after conducting the iterative equation along a solid mathematical optimization process.