<figure><img src="image_1.png" /></figure>

HAL
open science

# Duality in fuzzy linear programming

José-Luis Verdegay

► To cite this version:

José-Luis Verdegay. Duality in fuzzy linear programming. Bulletin pour les sous-ensembles flous et leurs applications, 1983, 16, pp.91–95. hal-04583357

HAL Id: hal-04583357

https://hal.science/hal-04583357

Submitted on 22 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Fuzzy clustering with additional information

Witold Pedrycz

Department of Automatic Control and Computer Sci.

Silesian Technical University

44-100 Gliwice

16, Pstrowskiego

Poland

**Abstract** The paper deals with fuzzy clustering algorithms based on minimization of an objective function performance index in a presence of additional information conveyed by some labelled patterns.

## 1. Introduction

Nowadays fuzzy clustering methods (unsupervised pattern recognition) - a fundamental tool for pattern recognition, are in rapid growth [1] - [8]. They provide a data analyst with information on a structure in a data set under consideration, pointing out a grade of belonging to a concrete class. By comparison, nonfuzzy clustering methods generate a {0, 1} partition of the data set. We would like to underline here that this way of thinking may radically mask imprecision (uncertainty) existing in a real world. Remembering that clustering is an initial stage of various data analysis, which usually are concerned with complex or imprecise concepts (e.g. handwritten characters, biological signals) we prefer to characterize the object by a value from the [0, 1]-interval rather than obtaining the information about a total belonging or nonbelonging.
# Fuzzy clustering with additional information

Witold Pedrycz

Department of Automatic Control and Computer Sci.

Silesian Technical University

44-100 Gliwice

16, Pstrowskiego

Poland

**Abstract** The paper deals with fuzzy clustering algorithms based on minimization of an objective function performance index in a presence of additional information conveyed by some labelled patterns.

## 1. Introduction

Nowadays fuzzy clustering methods (unsupervised pattern recognition) - a fundamental tool for pattern recognition, are in rapid growth [1] - [8]. They provide a data analyst with information on a structure in a data set under consideration, pointing out a grade of belonging to a concrete class. By comparison, nonfuzzy clustering methods generate a {0, 1} partition of the data set. We would like to underline here that this way of thinking may radically mask imprecision (uncertainty) existing in a real world. Remembering that clustering is an initial stage of various data analysis, which usually are concerned with complex or imprecise concepts (e.g. handwritten characters, biological signals) we prefer to characterize the object by a value from the [0, 1]-interval rather than obtaining the information about a total belonging or nonbelonging.
The problem we are interested in, is tied with clustering in a presence of a group of labelled patterns (elements of the data set) to which we can assign a grade of belongingness to the classes. Such a situation may occur while discussing a set of a few categories of handwritten characters with several elements carefully investigated by the data analyst and labelled by him. Of course, the process of labelling is time consuming, so we can speak about a situation where only few elements are investigated. The classification performed by a human being is subjective and therefore we can expect grades of belongingness in a whole range between 0 and 1.

In the paper we shall illustrate above stated problem by the use of Fuzzy c-means algorithm provided by Bezdek (cf. e.g. [2]). We shall formulate some new objective functions and present iterative procedures leading to their minimization (Section 3). A numerical example in Section 4 deals with illustration of the algorithms proposed by means of a data set known as Gustafson's cross [3]. Let us start our discussion remebering essential notions and notations, which will be useful in further considerations.

## 2. Preliminaries

Consider a finite data set $X=\{\underline{x}_i\}_{i=1,2,...,n}$ with elements being the points in p-dimensional Euclidean space, $\underline{x}_i \in \mathbb{R}^p$. The problem of the fuzzy clustering of the data set into "c" clusters (classes) deals with a generation of a fuzzy partition matrix $U$, viz. the matrix with the entries from the [0, 1] -interval,

$$ U = [u_{ik}] \quad i=1,2,...,c \quad k=1,2,...,n \qquad (1) $$
The problem we are interested in, is tied with clustering in a presence of a group of labelled patterns (elements of the data set) to which we can assign a grade of belongingness to the classes. Such a situation may occur while discussing a set of a few categories of handwritten characters with several elements carefully investigated by the data analyst and labelled by him. Of course, the process of labelling is time consuming, so we can speak about a situation where only few elements are investigated. The classification performed by a human being is subjective and therefore we can expect grades of belongingness in a whole range between 0 and 1.

In the paper we shall illustrate above stated problem by the use of Fuzzy c-means algorithm provided by Bezdek (cf. e.g. [2]). We shall formulate some new objective functions and present iterative procedures leading to their minimization (Section 3). A numerical example in Section 4 deals with illustration of the algorithms proposed by means of a data set known as Gustafson's cross [3]. Let us start our discussion remebering essential notions and notations, which will be useful in further considerations.

## 2. Preliminaries

Consider a finite data set $X=\{\underline{x}_i\}_{i=1,2,...,n}$ with elements being the points in p-dimensional Euclidean space, $\underline{x}_i \in \mathbb{R}^p$. The problem of the fuzzy clustering of the data set into "c" clusters (classes) deals with a generation of a fuzzy partition matrix $U$, viz. the matrix with the entries from the [0, 1] -interval,

$$ U = [u_{ik}] \quad i=1,2,...,c \quad k=1,2,...,n \qquad (1) $$
where for a fixed column, say $k_0$, their elements reflect a strength of
belonginess of the $k_0$-th pattern to respective classes. Moreover the
following conditions are usually imposed (e.g. [2]),

- every cluster is nonempty,

$$ \bigvee_{1 \le i \le c} \sum_{k=1}^{n} u_{ik} > 0 \qquad (2) $$

- a sum in every column is equal to 1,

$$ \bigvee_{1 \le k \le n} \sum_{i=1}^{c} u_{ik} = 1 \qquad (3) $$

Denote by $\mathcal{U}$ a family of fuzzy partition matrices of $n$,

$$ \mathcal{U} = \{ \mathcal{U} \mid \mathcal{U} \text{ satisfies (2) and (3)} \} \qquad (4) $$

the elements of $\mathcal{X}$ are clustered in order to minimize a performance index
introduced. It may take a form (cf. [8])

$$ \mathcal{Q} = \sum_{l=1}^{n} \sum_{i=1}^{c} \sum_{k=1}^{n} g(w_k, u_{ik}) d(x_k, x_l) \qquad (5) $$

subject to $U \in \mathcal{U}$

with "d" being a dissimilarity measure of the elements of $X, x_1, x_2, \dots, w_k$ stands for the a priori weights assigned to all objects of $X$.

If "d" is any inner-product induced on $\mathbb{R}^p$, $g(w_k, u_{ik})$ is defined by $u_{ik}^m/c$ then (5) is read as

$$ \mathcal{Q} = \sum_{i=1}^{c} \sum_{k=1}^{n} u_{ik}^{m} d_{ik}^{2} \qquad (6) $$
where for a fixed column, say $k_0$, their elements reflect a strength of
belonginess of the $k_0$-th pattern to respective classes. Moreover the
following conditions are usually imposed (e.g. [2]),

- every cluster is nonempty,

$$ \bigvee_{1 \le i \le c} \sum_{k=1}^{n} u_{ik} > 0 \qquad (2) $$

- a sum in every column is equal to 1,

$$ \bigvee_{1 \le k \le n} \sum_{i=1}^{c} u_{ik} = 1 \qquad (3) $$

Denote by $\mathcal{U}$ a family of fuzzy partition matrices $U$,

$$ \mathcal{U} = \{ U \mid U \text{ satisfies (2) and (3)} \} \qquad (4) $$

the elements of $X$ are clustered in order to minimize a performance index
introduced. It may take a form (cf. [8])

$$ q = \sum_{l=1}^{n} \sum_{i=1}^{c} \sum_{k=1}^{n} g(w_k, u_{ik}) d(x_k, x_l) \qquad (5) $$

subject to $U \in \mathcal{U}$

with "d" being a dissimilarity measure of the elements of $X, x_1, x_2, \dots, w_k$ stands for the a priori weights assigned to all objects of $X$.

If "d" is any inner-product induced on $\mathbb{R}^p$, $g(w_k, u_{ik})$ is defined by $u_{ik}^m/c$ then (5) is read as

$$ Q = \sum_{i=1}^{c} \sum_{k=1}^{n} u_{ik}^{m} d_{ik}^{2} \qquad (6) $$
where $d_{ik}^2$ is equal to

$$d_{ik}^2 = \|x_k - v_i\|^2 \quad (7)$$

with $v_i$ being a fuzzy mean of the i-th cluster,

$$v_i = \frac{\sum_{k=1}^{n} x_k u_{ik}}{\sum_{k=1}^{n} u_{ik}} \quad (8)$$

$\|\cdot\|$ is treated as any inner product induced on $\mathbb{R}^p, m \in (1, \infty)$. Very often one takes,

$$\|x_k - v_i\|^2 = \sum_{j=1}^{p} (x_{kj} - v_{ij})^2 \quad (9)$$

Thus we get the optimization task,

$$\begin{array}{ll} \min & Q \\ \mathcal{U} \in \mathcal{U}, & v_1, v_2, \dots, v_c \\ \text{Its solution is well-known as Fuzzy c-means algorithm given by Bezdek.} \\ \text{It is a iteration procedure which converges to a local minimum of (10),} \\ \text{generating the partition matrix and fuzzy means of respective classes.} \\ \text{Starting with any initial } \mathcal{U}^0 \text{ we follow a sequence of steps, } l=0, 1, 2, \dots \\ \text{1. Calculate fuzzy means } v_i, i=1, 2, \dots, c \text{ according to (8),} \\ \text{2. Update } \mathcal{U}^l \text{ as} \\ & u_{ik}^l = 1 / \sum_{j=1}^{c} \left( \frac{d_{ik}}{d_{jk}} \right)^{2/(n-1)} \\ & \text{if } \|x_k - v_i\| < \delta \text{ then stop, otherwise return to} \\ & \text{1 making use of the partition matrix calculated in the step } l. \\ \text{3. Compare } \mathcal{U}^l \text{ to } \mathcal{U}^{l+1}, \text{ if } \|x_k - v_i\| < \delta \text{ then stop, otherwise return to} \\ & \text{1 making use of the partition matrix calculated in the step } l. \\ \text{2.} \\ \end{array} \quad (10)$$

$$u_{ik}^l = 1 / \sum_{j=1}^{c} \left( \frac{d_{ik}}{d_{jk}} \right)^{2/(n-1)} \quad (11)$$

Now we present possible modifications of the performance index (6) in order to use information contained in the labelled points.
where $d_{ik}^2$ is equal to

$$d_{ik}^2 = \|x_k - v_i\|^2 \qquad (7)$$

with $v_i$ being a fuzzy mean of the i-th cluster,

$$v_i = \frac{\sum_{k=1}^{n} x_k u_{ik}}{\sum_{k=1}^{n} u_{ik}} \qquad (8)$$

$\|\cdot\|$ is treated as any inner product induced on $\mathbb{R}^p, m \in (1, \infty)$. Very often one takes,

$$\|x_k - v_i\|^2 = \sum_{j=1}^{p} (x_{kj} - v_{ij})^2 \qquad (9)$$

Thus we get the optimization task,

$$\begin{array}{ll} \min & Q \\ U \in \mathcal{U}, & v_1, v_2, \dots, v_c \end{array} \qquad (10)$$

Its solution is well-known as Fuzzy c-means algorithm given by Bezdek.

It is an iteration procedure which converges to a local minimum of (10), generating the partition matrix and fuzzy means of respective classes.

Starting with any initial $U^0$ we follow a sequence of steps, $l=0, 1, 2, \dots$

1. Calculate fuzzy means $v_i, i=1, 2, \dots, c$ according to (8),

2. Update $U^l$ as

$$u_{ik}^{l+1} = 1 / \sum_{j=1}^{c} \left( \frac{d_{ik}}{d_{jk}} \right)^{2/(n-1)} \qquad (11)$$

$i=1, 2, \dots, c, k=1, 2, \dots, n$.

3. Compare $U^l$ to $U^{l+1}$, if $\|U^{l+1} - U^l\| < \delta$ then stop, otherwise return to 1 making use of the partition matrix calculated in the step 2.

Now we present possible modifications of the performance index (6) in order to use information contained in the labelled points.
### 3. Minimization of the objective functions with the aid of labelled patterns

Now we reconsider several modifications of the objective function (6) in order to handle labelled patterns.

Let us denote by $F$ a partition matrix representing labelled patterns,

$$F= [f_{ik}] \qquad (12) \\ i=1,2,...,c \\ k=1,2,...,n$$

with values assigned:

- if $x_k \in \Lambda_l$ (set of labelled elements of $\Lambda_l$) then $f_{ik}$ are given by the data analyst, with the condition $\sum_{i=1}^c f_{ik}$ satisfied,

- if $x_k \notin \Lambda_l$ then $f_{ik}$ takes any value, $i=1,2,...,c$.

Denote by $g$ an n-dimensional vector with the entries,

$$g_k = \begin{cases} 1, & \text{if } x_k \in \Lambda_l \\ 0, & \text{otherwise} \end{cases} \qquad (13)$$

Several modifications of $g$ are listed below.

#### 1. $g_k = \sum_{i=1}^{c} u_{ik}^2 d_{ik}^2$

$$g_k = \sum_{i=1}^{c} u_{ik}^2 d_{ik}^2 + \sum_{i=1}^{c} (u_{ik} - f_{ik})^2 d_{ik}^2 \qquad (14)$$

This modification of the performance index takes into account a sum of weighted distances between $u_{ik}$ and $f_{ik}$ with weights being $d_{ik}^2$. Then we get

$$\min_{U \in \mathcal{U}} \sum_{i=1}^{c} v_i^2 \qquad (15) \\ U \in \mathcal{U}, v_1, v_2, \dots, v_c$$
### 3. Minimization of the objective functions with the aid of labelled patterns

Now we reconsider several modifications of the objective function (6) in order to handle labelled patterns.

Let us denote by $F$ a partition matrix representing labelled patterns,

$$ F = \begin{bmatrix} f_{ik} \\ \vdots \\ f_{1k} \end{bmatrix}_{\substack{i=1,2,\dots,c \\ k=1,2,\dots,n}} \qquad (12) $$

with values assigned:

- if $x_k \in \Lambda_l$ (set of labelled elements of $\Lambda_l$) then $f_{ik}$ are given by the data analyst, with the condition $\sum_{i=1}^c f_{ik}$ satisfied,

- if $x_k \notin \Lambda_l$ then $f_{ik}$ takes any value, $i=1,2,\dots,c$.

Denote by $g$ an n-dimensional vector with the entries,

$$ g_k = \begin{cases} 1, & \text{if } x_k \in \Lambda_l \\ 0, & \text{otherwise} \end{cases} \qquad (13) $$

Several modifications of $g$ are listed below.

#### 1. $g_k = \sum_{i=1}^c u_{ik}^2 d_{ik}^2$

$$ g = \sum_{i=1}^{c} u_{ik}^{2} d_{ik}^{2} + \sum_{i=1}^{c} (u_{ik} - f_{ik})^{2} d_{ik}^{2} \qquad (14) $$

This modification of the performance index takes into account a sum of weighted distances between $u_{ik}$ and $f_{ik}$ with weights being $d_{ik}^2$. Then we get

$$ \begin{gathered} \min g \qquad (15) \\ U \in \mathcal{U}, v_1, v_2, \dots, v_c \end{gathered} $$
In order to find a local minimum of Q with regards to the constraint $\sum_{i=1}^{c} u_{ik}=1$, we apply a technique of Lagrange multipliers. It leads to unconstrained minimization of an index,

$$V=Q-\lambda(\sum_{i=1}^{c} u_{ik}-1) \qquad (16)$$

Then

$$\partial V / \partial u_{st}=2 u_{st} d_{st}^{2}+2\left(u_{st}-f_{st} g_{t}\right) d_{st}^{2}-\lambda=0, \qquad (17)$$

so

$$u_{st} = (f_{st}g_{t}d_{st}^{2} + \lambda) / 4d_{st}^{2}, \qquad (18)$$

and

$$\sum_{j=1}^{c} u_{jt} = \sum_{j=1}^{c} \left( f_{jt} g_{t} d_{jt}^{2} + \lambda \right) / 4 d_{jt}^{2} = 1 \qquad (19)$$

The Lagrange multiplier is equal to

$$\lambda = \left( 4 - \sum_{j=1}^{c} f_{jt} g_{t} \right) / \sum_{j=1}^{c} \left( 1 / d_{jt}^{2} \right) \qquad (20)$$

and next it leads to,

$$u_{st} = \left( 4 - \sum_{j=1}^{c} f_{jt} g_{t} \right) / \left( 4 \sum_{j=1}^{c} \left( \frac{d_{st}^{2}}{d_{jt}^{2}} \right) + f_{st} g_{t} / 4 \right) \qquad (21)$$

The basic iterative scheme given in the previous section is modified in the step 2, where a calculation of the partition matrix is processed by means of (21). Note that if $g_t=0$ for all $t=1, 2, ..., n$ then (21) reduces to the formula derived before,

$$u_{st}=1 / \sum_{j=1}^{c} \left( \frac{d_{st}^{2}}{d_{jt}^{2}} \right) \qquad (22)$$
In order to find a local minimum of Q with regards to the constraint $\sum_{i=1}^{c} u_{ik}=1$, we apply a technique of Lagrange multipliers. It leads to unconstrained minimization of an index,

$$V=Q-\lambda(\sum_{i=1}^{c} u_{ik}-1) \quad (16)$$

Then

$$\partial V / \partial u_{st}=2 u_{st} d_{st}^{2}+2\left(u_{st}-f_{st} g_{t}\right) d_{st}^{2}-\lambda=0, \quad (17)$$

so

$$u_{st} = (f_{st}g_{t}d_{st}^{2} + \lambda) / 4d_{st}^{2}, \quad (18)$$

and

$$\sum_{j=1}^{c} u_{jt} = \sum_{j=1}^{c} \left( f_{jt} g_{t} d_{jt}^{2} + \lambda \right) / 4 d_{jt}^{2} = 1 \quad (19)$$

The Lagrange multiplier is equal to

$$\lambda = \left( 4 - \sum_{j=1}^{c} f_{jt} g_{t} \right) / \sum_{j=1}^{c} \left( 1 / d_{jt}^{2} \right) \quad (20)$$

and next it leads to,

$$u_{st} = \left( 4 - \sum_{j=1}^{c} f_{jt} g_{t} \right) / \left( 4 \sum_{j=1}^{c} \left( \frac{d_{st}^{2}}{d_{jt}^{2}} \right) + f_{st} g_{t} / 4 \right) \quad (21)$$

The basic iterative scheme given in the previous section is modified in the step 2, where a calculation of the partition matrix is processed by means of (21). Note that if $g_t=0$ for all $t=1, 2, \dots, n$ then (21) reduces to the formula derived before,

$$u_{st}=1 / \sum_{j=1}^{c} \left( \frac{d_{st}^{2}}{d_{jt}^{2}} \right) \quad (22)$$
D. The labelled elements are an important source of information about an internal structure of the data set. It will be applied by specification of the inner product induced on $\mathbb{R}^p$. Introduce fuzzy covariance matrices generated by labelled data,

$$C_{f_i} = \frac{\sum_{k=1}^{n} f_{ik}^2 g_k (x_k - w_i)(x_k - w_i)^T}{\sum_{k=1}^{n} f_{ik}^2 g_k} \quad (23)$$

where $w_i$ are fuzzy means,

$$w_i = \frac{\sum_{k=1}^{n} f_{ik} g_k x_k}{\sum_{k=1}^{n} f_{ik} g_k} \quad (24)$$

i=1,2,...,c. Next distances between pattern and the fuzzy means are computed with the help of $C_{f_i}$ introduced above,

$$d_{ik} = (x_k - v_i)^T C_{f_i}^{-1} (x_k - v_i) \quad (25)$$

The performance index we take into account is given by,

$$Q = \sum_{i,k} u_{ik}^2 d_{ik}^2 \quad (26)$$

In this performance index the labelled data generate a structure of the inner product on $\mathbb{R}^p$.

C. This criterion makes use of the labelled data in two ways: firstly they are applied in order to generate the underlying structure $C_{f_i}$ secondly, to measure a distance between partition matrices U and F,
D. The labelled elements are an important source of information about an internal structure of the data set. It will be applied by specification of the inner product induced on $\mathbb{R}^p$. Introduce fuzzy covariance matrices generated by labelled data,

$$C_{f_i} = \frac{\sum_{k=1}^{n} f_{ik}^2 g_k (x_k - w_i)(x_k - w_i)^T}{\sum_{k=1}^{n} f_{ik}^2 g_k} \quad (23)$$

where $w_i$ are fuzzy means,

$$w_i = \frac{\sum_{k=1}^{n} f_{ik} g_k x_k}{\sum_{k=1}^{n} f_{ik} g_k} \quad (24)$$

i=1,2,...,c. Next distances between pattern and the fuzzy means are computed with the help of $C_{f_i}$ introduced above,

$$d_{ik} = (x_k - v_i)^T C_{f_i}^{-1} (x_k - v_i) \quad (25)$$

The performance index we take into account is given by,

$$Q = \sum_{i,k} u_{ik}^2 d_{ik}^2 \quad (26)$$

In this performance index the labelled data generate a structure of the inner product on $\mathbb{R}^p$.

C. This criterion makes use of the labelled data in two ways: firstly they are applied in order to generate the underlying structure $C_{f_i}$ secondly, to measure a distance between partition matrices U and F,
$$Q = \sum_{i,k} u_{ik}^2 d_{ik}^2 + \sum_{i,k} (u_{ik} - f_{ik} g_k)^2 d_{ik}^2 \quad (27)$$

The criteria B. and C. are constructed in such a manner that the algorithms presented before can be used without significant modifications.

## 4. Numerical illustration

As an illustration of the clustering methods discussed above, we consider the data set known as Gustafson's crosss (see Fig. 1), which consists of two classes of points with a certain overlap. Six points indicated in Fig. 1 are labelled.

For comparison we test four algorithms: Fuzzy c-means without the use of the labelled objects, and next the method A, B, and C. In order to evaluate a character of convergence of the methods established we take into account an index, which is a norm defined in the space $U$

$$e(l) = \max_{\substack{1 \le i \le c \\ 1 \le k \le n}} |u_{ik}^1 - u_{ik}^{1-1}| \quad (28)$$

$l=1,2,...$. The results are displayed in Fig. 2. Fuzzy c-means algorithm is characterized by a slow rate of convergence; it is not surprising remembering the fact that Euclidean distance prefers hyperellipsoidal shapes of clusters, while A, B, and C indicate the same speed of convergence.

Moreover, we evaluate the methods tested calculating a sum of squared deviations between values of the membership functions of the labelled
$$Q = \sum_{i,k} u_{ik}^2 d_{ik}^2 + \sum_{i,k} (u_{ik} - f_{ik} g_k)^2 d_{ik}^2 \quad (27)$$

The criteria B. and C. are constructed in such a manner that the algorithms presented before can be used without significant modifications.

## 4. Numerical illustration

As an illustration of the clustering methods discussed above, we consider the data set known as Gustafson's crosss (see Fig. 1), which consists of two classes of points with a certain overlap. Six points indicated in Fig. 1 are labelled.

For comparison we test four algorithms: Fuzzy c-means without the use of the labelled objects, and next the method A, B, and C. In order to evaluate a character of convergence of the methods established we take into account an index, which is a norm defined in the space $U$

$$e(l) = \max_{\substack{1 \le i \le c \\ 1 \le k \le n}} |u_{ik}^1 - u_{ik}^{1-1}| \quad (28)$$

$l=1,2,...$. The results are displayed in Fig. 2. Fuzzy c-means algorithm is characterized by a slow rate of convergence; it is not surprising remembering the fact that Euclidean distance prefers hyperellipsoidal shapes of clusters, while A, B, and C indicate the same speed of convergence.

Moreover, we evaluate the methods tested calculating a sum of squared deviations between values of the membership functions of the labelled
elements and values of the computed membership functions,

$$q= \sum_{i=1}^{c} \sum_{x_k \in X_l} |u_{ik}-f_{ik}| \quad (29)$$

The results are summarized in the Tab.1. It is clear that introduction of the fuzzy covariance matrices which control shapes of the generated clusters, makes it possible to diminish the values of q, while the introduction of the constraints in terms of membership functions only, has minor influence on q.

The results of the last method (C) are shown in Fig.1.

<table><caption>Table 1. Calculated values of the membership functions for the labelled patterns</caption><thead><tr><th>pattern</th><th>label</th><th>Fuzzy c-means</th><th>A</th><th>B</th><th>C</th></tr></thead><tbody><tr><td>x<sub>1</sub></td><td>1.0,0.0</td><td>0.71,0.29</td><td>0.64,0.36</td><td>0.99,0.01</td><td>0.99,0.01</td></tr><tr><td>x<sub>5</sub></td><td>0.5,0.5</td><td>0.78,0.22</td><td>0.91,0.09</td><td>0.92,0.08</td><td>0.81,0.19</td></tr><tr><td>x<sub>10</sub></td><td>1.0,0.0</td><td>0.16,0.84</td><td>0.66,0.34</td><td>0.99,0.01</td><td>0.99,0.01</td></tr><tr><td>x<sub>11</sub></td><td>0.0,1.0</td><td>0.74,0.26</td><td>0.20,0.80</td><td>0.00,1.00</td><td>0.00,1.00</td></tr><tr><td>x<sub>15</sub></td><td>0.5,0.5</td><td>0.89,0.11</td><td>0.01,0.99</td><td>0.00,1.00</td><td>0.13,0.37</td></tr><tr><td>x<sub>20</sub></td><td>0.0,1.0</td><td>0.35,0.65</td><td>0.50,0.50</td><td>0.00,1.00</td><td>0.00,1.00</td></tr><tr><td>q</td><td></td><td>5.78</td><td>4.60</td><td>1.88</td><td>1.40</td></tr></tbody></table>

References

1.3. Backer, Cluster analysis by optimal decomposition of induced fuzzy sets, Delft Univ. Press, Delft, 1978.
elements and values of the computed membership functions,

$$q= \sum_{i=1}^{c} \sum_{x_k \in X_l} |u_{ik}-f_{ik}| \quad (29)$$

The results are summarized in the Tab.1. It is clear that introduction of the fuzzy covariance matrices which control shapes of the generated clusters, makes it possible to diminish the values of q, while the introduction of the constraints in terms of membership functions only, has minor influence on q.

The results of the last method (C) are shown in Fig.1.

<table><caption>Table 1. Calculated values of the membership functions for the labelled patterns</caption><thead><tr><th>pattern</th><th>label</th><th>Fuzzy c-means</th><th>A</th><th>B</th><th>C</th></tr></thead><tbody><tr><td>x<sub>1</sub></td><td>1.0,0.0</td><td>0.71,0.29</td><td>0.64,0.36</td><td>0.99,0.01</td><td>0.99,0.01</td></tr><tr><td>x<sub>5</sub></td><td>0.5,0.5</td><td>0.78,0.22</td><td>0.91,0.09</td><td>0.92,0.08</td><td>0.81,0.19</td></tr><tr><td>x<sub>10</sub></td><td>1.0,0.0</td><td>0.16,0.84</td><td>0.66,0.34</td><td>0.99,0.01</td><td>0.99,0.01</td></tr><tr><td>x<sub>11</sub></td><td>0.0,1.0</td><td>0.74,0.26</td><td>0.20,0.80</td><td>0.00,1.00</td><td>0.00,1.00</td></tr><tr><td>x<sub>15</sub></td><td>0.5,0.5</td><td>0.89,0.11</td><td>0.01,0.99</td><td>0.00,1.00</td><td>0.13,0.37</td></tr><tr><td>x<sub>20</sub></td><td>0.0,1.0</td><td>0.35,0.65</td><td>0.50,0.50</td><td>0.00,1.00</td><td>0.00,1.00</td></tr><tr><td>q</td><td></td><td>5.78</td><td>4.60</td><td>1.88</td><td>1.40</td></tr></tbody></table>

References

1.3. Backer, Cluster analysis by optimal decomposition of induced fuzzy sets, Delft Univ. Press, Delft, 1978.
2. J.C.Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms, Elenum Press, New York, 1981.

3. D.E.Gustafson, W.Kessel, Fuzzy clustering with a fuzzy covariance matrix, in Proc. IEEE-CDC, vol.2, F.S.Fu ed., IEEE Press, Piscataway, New Jersey, 1979, 761-766.

4. G.Libert, M.Roubens, Non metric fuzzy clustering algorithms, in Approximate Reasoning and Decision Analysis, M.M.Gupta, E.Sanchez eds., North Holland, Amsterdam, 1982, 417-426.

5. J.Pedrycz, E.Backer, Determination of the cores of fuzzy clusters, Fuzzy Sets and Systems submitted.

6. E.Ruspini, A new approach to clustering, Information and Control, 15, 1969, 22-32.

7. E.Ruspini, Numerical methods for fuzzy clustering, Information Sciences, 2, 1970, 319-350.

8. L.Roubens, Pattern classification problems and fuzzy sets, Fuzzy Sets and Systems, 1, 1978, 239-253.
2. J.C.Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms, Plenum Press, New York, 1981.

3. D.E.Gustafson, W.Kessel, Fuzzy clustering with a fuzzy covariance matrix, in Proc. IEEE-CDC, vol.2, F.S.Fu ed., IEEE Press, Piscataway, New Jersey, 1979, 761-766.

4. G.Libert, M.Roubens, Non metric fuzzy clustering algorithms, in Approximate Reasoning and Decision Analysis, M.M.Gupta, E.Sanchez eds., North Holland, Amsterdam, 1982, 417-426.

5. J.Pedrycz, E.Backer, Determination of the cores of fuzzy clusters, Fuzzy Sets and Systems submitted.

6. E.Ruspini, A new approach to clustering, Information and Control, 15, 1969, 22-32.

7. E.Ruspini, Numerical methods for fuzzy clustering, Information Sciences, 2, 1970, 319-350.

8. L.Roubens, Pattern classification problems and fuzzy sets, Fuzzy Sets and Systems, 1, 1978, 239-253.
<figure><img src="image_1.png" /><figcaption>Fig. 1. Gustafson's cross with the labelled patterns and the results of clustering produced by the method C.</figcaption></figure>

<figure><img src="image_2.png" /><figcaption>Fig. 2. The index of convergence $e(1)$ vs. number of iterations for various clustering methods.</figcaption></figure>
<figure><img src="image_3.png" /><figcaption>Fig. 1. Gustafson's cross with the labelled patterns and the results of clustering produced by the method C.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 2. The index of convergence $e(1)$ vs. number of iterations for various clustering methods.</figcaption></figure>