# Double-Constraint Fuzzy Clustering Algorithm
## 3 Double-Constraint Fuzzy Clustering  
Let \(X=\{x_{j}\}\) be a dataset with \(n\) data objects that are distributed in \(c\) clusters in a \(d\)-dimensional data space, \(x_{j}\in R^{d}\). According to the fuzzy partition matrix \(U\) in FCM, we define two symbols as follows:  
\[p_{i}=\sum_{j=1}^{n}u_{ij}\ \text{and}\ q_{j}=\sum_{i=1}^{c}u_{ij},\ i=1,2, \ldots,c;\ j=1,2,\ldots,n \tag{10}\]  
The value of \(p_{i}\) is the constraint for the \(i\)th cluster if the constraint can be known a priori, whereas the value of \(q_{j}\) is the constraint for \(j\)th data object. The meaning of \(q_{j}\) in PFCM is illustrated as follows:  
1. \(q_{j}<1\), the \(j\)th data object is under sparse distribution, likely being a noisy point or outlier;
2. \(q_{j}=1\), the \(j\)th data object does not have an additional importance degree, and thus the point has the same membership degree value as it has in FCM;\(q_{j}>1\), the \(j\)th cluster may be an aggregation of data with high density such as a clustering center and so on; these points act as the main structure of various clusters. Alternatively, the meaning of \(p_{i}\) in CCM is defined as the number of data points in the \(i\)th cluster, and it is usually a mandatory requirement of the clustering results of any clustering algorithm. To date, no existing fuzzy clustering algorithm can combine the constraints of both data objects and clusters to enhance clustering quality. Since \(q_{j}\) reflects the importance of each point whereas \(p_{i}\) reflects that of each point, they can represent the typicality or compatibility of points and clusters together. According to the constraints on both point and cluster importance degrees, a double-constraint fuzzy clustering algorithm is proposed, abbreviated as DFCM. The objective function of DFCM is formulated as  
\[\min\!/(U,V)=\sum_{i=1}^{c}\sum_{j=1}^{n}u_{ij}^{m}d_{ij}^{2},\ \ s.t.\sum_{j=1}^{n}u_{ij}=p_{i}, \sum_{i=1}^{c}u_{ij}=q_{j},\ i=1,2,\ldots,c;\ j=1,2,\ldots,n \tag{11}\]  
Taking \(n+c\) Lagrange multipliers: \(\lambda_{j}\), \(j=1\), \(2\),\(\ldots\), \(n\); \(u_{i}\), \(i=1\), \(2\), \(\ldots\), \(c\), the typical alternative optimization way [25] is used to solve (11). And the Lagrange function is formulated as  
\[F_{m}=\sum_{i=1}^{c}\sum_{j=1}^{n}u_{ij}^{m}(x_{j}-v_{i})^{2}+\sum_{j=1}^{n} \lambda_{j}(\sum_{i=1}^{c}u_{ij}-q_{j})+\sum_{i=1}^{c}u_{i}(\sum_{j=1}^{n}u_{ ij}-p_{i}), \tag{12}\]  
Equation (12) is solved by the following two alternative optimization problems. **Problem P1:**  
Fix \(u_{\bar{y}}\): solve the \(k\)th cluster center \(v_{k}\). The derivative of \(F_{m}\) on \(v_{k}\) is  
\[ \begin{array}{l}\frac{\partial q_{\pi_{k}}}{\partial v_{k}}=\sum_{i=1}^{c} \sum_{j=1}^{n}\frac{\partial u_{ij}^{m}d_{ij}^{2}}{\partial v_{k}}-\frac{ \partial}{\partial v_{k}}(\sum_{j=1}^{n}\lambda_{j}(\sum_{i=1}^{c}u_{ij}-q_{ j}))-\frac{\partial}{\partial v_{k}}(\sum_{i=1}^{c}u_{i}(\sum_{j=1}^{n}u_{ij}-p_{i}))\\ =\sum_{i=1}^{c}\sum_{j=1}^{n}\frac{\partial u_{ij}^{m}(x_{j}-c_{i})^{2}}{ \partial v_{k}}=-2\sum_{j=1}^{n}u_{kj}^{m}(x_{j}-v_{k})=0\end{array} ,\]  
Thus  
\[v_{k}=\sum_{j=1}^{n}u_{kj}x_{j}/\sum_{j=1}^{n}u_{kj},\ \ s.t.,\ k=1,\ 2,\ldots,c, \tag{13}\]  
**Problem P2:**  
Fix \(v_{k}\), solve \(u_{kg}\) from the \(g\)th data vector to \(v_{k}\). The derivative of \(F_{m}\) on \(u_{kg}\) yields  
\[\partial F_{m}/\partial u_{kg}=mu_{kg}^{m-1}(x_{j}-v_{i})^{2}+\lambda_{g}+\mu _{k}=0,\]  
it is  
\[u_{kg}^{m-1}=(-\lambda_{g}-\mu_{k})/(m(x_{g}-v_{k})^{2}). \tag{14}\]  
Taking it into \(\sum_{j=1}^{n}u_{ij}=p_{i}\), \(\sum_{i=1}^{c}u_{ij}=q_{j}\), they are  
\[\left\{ \begin{array}{l}\sum\limits_{i=1}^{c}u_{ig}=\sum\limits_{i=1}^{c}( \frac{-\lambda_{g}-\mu_{k}}{m(x_{g}-v_{i})^{2}})^{1/(m-1)}=&q_{g},\ g=1,2,\ldots,n \\ \sum\limits_{j=1}^{n}u_{kj}=\sum\limits_{i=1}^{c}(\frac{-\lambda_{j}-\mu_{k} }{m(x_{j}-v_{k})^{2}})^{1/(m-1)}=&p_{k},\ k=1,2,\ldots,c\end{array}