\documentclass{crorr} %%%%% journal info -- DO NOT CHANGE %%%%%%%%% \setcounter{page}{1} \renewcommand\thisnumber{x} \renewcommand\thisyear {201x} \renewcommand\thisvolume{x} \renewcommand\datereceived{xx xx, 201x} \renewcommand\dateaccepted{yy yy, 201x} \renewcommand\dateavailable{zz zz, 201x} %%%%%%%% end journal info %%%%%%%%%%%%% %%%%% author macros %%%%%%%%% \newcommand{\R}{\mathbb{R}} \newcommand{\A}{\mathcal{A}} \newcommand\argmin{\mathop{\mathrm{argmin}}\nolimits} \newcommand\conv{\mathop{\mathrm{conv}}\nolimits} \newcommand\diag{\mathop{\mathrm{diag}}\nolimits} \newcommand\argmax{\mathop{\mathrm{argmax}}\nolimits} \newtheorem{alg}{Algorithm} %% ZA LITERATURU \usepackage[numbers,sort&compress]{natbib} %\bibliographystyle{MathComm} %% ZA TABLICE \usepackage{booktabs} %% ZA CITATE \usepackage[style=english]{csquotes} %%%%% end %%%%%%%%% %%%%%%%%% already loaded packages -- DO NOT RELOAD %%%%% % \usepackage{amssymb} % \usepackage{amsmath,amsthm} % \usepackage{latexsym} % \usepackage{amsfonts} % \usepackage{amsbsyt} % \usepackage{graphicx} %%%%%% end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \markboth{Ivan Vidovi\'c, Dra\v{z}en Bajer and Rudolf Scitovski}{A new fusion algorithm for fuzzy clustering} \title{A new fusion algorithm for fuzzy clustering} \author[Names of authors]{\bf Ivan Vidovi\'c \affil{1}\comma\corrauth , \, Dra\v{z}en Bajer \affil{1} \, and \, Rudolf Scitovski\affil{2}} \address{\affilnum{1}\ Faculty of Electrical Engineering Osijek, Josip Juraj Strossmayer University of Osijek\\ Cara Hadrijana 10b, HR-31 000 Osijek, Croatia\\ E-mail: $\langle$\{ividovi2, dbajer\}@etfos.hr$\rangle$ \\ \medskip \affilnum{2}\ Department of Mathematics, Josip Juraj Strossmayer University of Osijek\\ Trg Lj. Gaja 6, HR-31 000 Osijek, Croatia\\ E-mail: $\langle$scitowsk@mathos.hr$\rangle$ } %\markboth{A new fusion algorithm for fuzzy clustering}{A new fusion algorithm for fuzzy clustering} %\title{A new fusion algorithm for fuzzy clustering} %%%%% Begin Abstract %%%%%%%%%%% \begin{abstract} In this paper we have considered the merging problem of two ellipsoidal clusters in order to construct a new fusion algorithm for fuzzy clustering. We have proposed a criterion for merging two ellipsoidal clusters $\pi_1,\pi_2$ with associated main Mahalanobis circles $E_j(c_j,\sigma_j)$, where $c_j$ is the centroid and $\sigma^2_j$ is the Mahalanobis variance of cluster $\pi_j$. Based on the well-known Davies-Bouldin index we have constructed a new fusion algorithm. The criterion has been tested on several data sets, and the performance of the fusion algorithm has been demonstrated on an illustrative example. \end{abstract} %%%%% end %%%%%%%%%%% %%%%% Keywords %%%%%%%%%%% \keywords{fusion algorithm, fuzzy clustering, Mahalanobis clustering, cluster merging, Davies-Bouldin index} %%%% maketitle %%%%% \maketitle %%%% Start %%%%%% %%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} \label{INT} Given is a data points set $\A=\{a^i\colon i=1,\dots,m\}\subset[\alpha,\beta]\subset\R^n$, where $\alpha=(\alpha_1,\dots,\alpha_n)^T$, $\beta=(\beta_1,\dots,\beta_n)^T\in\R^n$ and $[\alpha,\beta]=\{x\in\R^n\colon \alpha_s\leq x_s\leq \beta_s\}$. A partition of the set $\mathcal{A}$ into $k$ disjoint subsets $\pi_1,\dots,\pi_k$, $1\leq k\leq m$, such that \begin{equation}\label{part} \bigcup\limits_{j=1}^k \pi_j={\cal A},\qquad \pi_r\cap \pi_s=\emptyset,\quad r\neq s,\qquad |\pi_j|\geq 1,\quad j=1,\dots,k, \end{equation} will be denoted by $\Pi({\cal A})=\{\pi_1,\dots,\pi_k\}$ and the set of all such partitions will be denoted by $\mathcal{P}(\mathcal{A};k)$. The elements $\pi_1,\dots,\pi_k$ of the partition $\Pi$ are called \emph{clusters}. Clustering or grouping a data set into conceptually meaningful clusters is a well-studied problem in recent literature, and it has practical importance in a wide variety of applications (see e.g., \cite{Bezdek2005, Sabo2012, Scitovski2013}). If $d\colon\R^n\times\R^n\to\R_{+}$, $\R_{+}=[0,+\infty\rangle$ is some distance-like function (see e.g.\ \cite{Bezdek2005, Kogan2007}), then to each cluster $\pi_j\in\Pi$ we can associate its center $c_j$ defined by \begin{equation}\label{center} c_j:=\argmin\limits_{x\in[\alpha,\beta]}\sum\limits_{a\in\pi_j}d(x,a). \end{equation} After that, by introducing the objective function $\mathcal{F}\colon\mathcal{P}(\A;k)\to\R_+$, the quality of a partition can be defined, and searching for the \emph{globally optimal $k$-partition} comes down to solving the following optimization problem \begin{equation}\label{FF} \argmin\limits_{\Pi\in\mathcal{P}(\A;k)}\mathcal{F}(\Pi),\qquad \mathcal{F}(\Pi)=\sum\limits_{j=1}^k\sum\limits_{a\in\pi_j}d(c_j,a),\qquad c=(c_1,\dots,c_k). \end{equation} Conversely, for a given set of centers $c_1,\dots,c_k\in[\alpha,\beta]$, by applying the minimal distance principle, the partition $\Pi=\{\pi(c_1),\dots,\pi(c_k)\}$ of set ${\cal A}$ consisting of clusters: \[ \pi(c_j)=\{a\in {\cal A}: d(c_j,a)\leq d(c_s,a),\,\forall s=1,\dots,k\},\qquad j=1,\dots,k, \] can be defined. Therefore, the problem of finding an optimal partition of set $\mathcal{A}$ can be reduced to the following \emph{global optimization problem} (see e.g.\ \cite{Spath1983, Bezdek2005, Theodoridis2009}) \begin{equation}\label{F} \argmin\limits_{c\in[\alpha,\beta]^k}F(c),\qquad F(c)=\sum\limits_{i=1}^m \min\limits_{1\leq j\leq k}d(c_j,a^i). \end{equation} The solutions of \eqref{FF} and \eqref{F} coincide \cite{Scitovski2013, Spath1983}. Let $U\in\{0,1\}^{m\times k}$ be a matrix such that \begin{align} \label{u1}& u_{ij}=\begin{cases} 1,& \text{if $a^i\in\pi_j$}\\ 0,& \text{if $a^i\notin\pi_j$} \end{cases},\qquad i=1,\dots m,\quad j=1,\dots,k,\\ \label{u2}& \sum\limits_{j=1}^k u_{ij}=1,\quad i=1,\dots,m. \end{align} Then \eqref{FF} can be written as \cite{Bezdek2005, Theodoridis2009} \begin{equation}\label{FFU} \argmin\limits_{c\in[\alpha,\beta]^k,\,U\in\{0,1\}^{m\times k}}F(c,U),\qquad F(c,U)=\sum\limits_{i=1}^m\sum\limits_{j=1}^{k} u_{ij}d(c_j,a^i). \end{equation} In order to ensure all conditions from \eqref{part}, the following should be added to conditions \eqref{u1} and \eqref{u2}: \begin{equation}\label{u3} \sum\limits_{i=1}^m u_{ij}\geq 1,\quad j=1,\dots,k. \end{equation} Assuming that elements $a^i\in\A$ can partially belong to different clusters, then, due to \eqref{u2}, it must be $u_{ij}\in[0,1]$ (see e.g., \cite{Scitovski2014}). According to \cite{Bezdek2005, Theodoridis2009}, the membership grade of $a^i$ in cluster $\pi_j$ is determined by $u_{ij}^q$, where parameter $q>1$ is called the \emph{fuzzifier}, and the objective function becomes \begin{equation}\label{Fz1} F(c,U)=\sum\limits_{i=1}^m\sum\limits_{j=1}^k u_{ij}^q(c)\, d(c_j,a^i). \end{equation} The definition of membership functions $u_{ij}\colon\A\to[0,1]$ can be found in \cite{Hoppner2003}. In applied research, the most common value is $q\in[1.5,2.5]$. A partition with the most appropriate number of clusters can be estimated by the following well-known validity indexes for fuzzy clustering (see e.g., \cite{Bezdek2005, Kaymak2002, Theodoridis2009, Vendramin2009}): Xie-Beni index, fuzzy Davies -- Bouldin index, Fuzzy Hypervolume index, etc. In our paper we specially use the fuzzy Davies -- Bouldin index (DB) which, for the optimal partition $\Pi^\star(\pi^\star_1,\dots,\pi^\star_k)$, is defined by \begin{equation}\label{DB} \textrm{DB}(k)=\frac{1}{k}\sum\limits_{j=1}^k\max\limits_{\begin{subarray}{c} s\in\{1,\dots,k\}\\ s\neq j \end{subarray}} \frac{V(\pi_j^{\star})+V(\pi_s^{\star})}{d(c_j^{\star},c_s^{\star})}, \end{equation} where $c^\star_1,\dots,c^\star_k$ are centers of clusters and \[ V(\pi_j^{\star})=\tfrac{1}{\sum\limits_{i=1}^mu_{ij}^q(c)} \sum\limits_{i=1}^m u_{ij}^q(c)\, d(c_j,a^i). \] The term $D_j:=\max\limits_{\begin{subarray}{c} s\in\{1,\dots,k\},\, s\neq j \end{subarray}} \frac{V(\pi_j^{\star})+V(\pi_s^{\star})}{d(c_j^{\star},c_s^{\star})}$ represents the worst case within--to--between cluster spread involving the cluster $\pi_j^\star$. Minimizing $D_j$ for all clusters clearly minimizes the DB index. Therefore, more compact and better separated clusters in an optimal partition will result in a lower value of DB-index (see \cite{Theodoridis2009, Vendramin2009}). It is well-known that by using the Least Squares (LS) distance-like function \cite{Bezdek2005, Kogan2007} spherical clusters are obtained, and by using adaptive Mahalanobis clustering \cite{Gustafson1979, Spath1983, Theodoridis2009} ellipsoidal clusters are obtained. However, if different banana-form clusters should be recognized, then some fusion method can be applied \cite{Bezdek2005, Frossyniotis2002, Kaymak2002, Xiong2004}. The idea is in the following: First, to determine optimal partition with relatively many clusters using a certain method and then to keep merging close clusters for as long as the DB index value is decreasing. Such cluster-forms appear in different geographical, geological and medical research. The paper is organized as follows. In the next section the merging problem of two spherical data sets is discussed. In Section~\ref{ELI} the problem is generalised for two ellipsoidal data sets and a corresponding merging algorithm is proposed. A new fusion algorithm is proposed in Section~\ref{FUS} and in Section~\ref{NUM} a numerical example is shown. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Motivation: Merging of two spherical data sets} \label{MOT} Because of simplicity, we consider the merging problem of two spherical data sets in the plane. The problem in $\R^n$ is analogous. Let $d$ be the LS distance-like function, let $c\in\R^2$ be the point in plane in the neighborhood of which $m$ random points were generated by using Gaussian distributions with variance $\sigma^2$, then the circle $K(c,\sigma)$ contains about $68\%$ data points \cite{Bensic2012}. The set of all data points constitute the set $\A$. The circle $K(c,\sigma)$ is called \emph{main circle} of the set $\A$, and data points outside the circle $K(c,\sigma)$ are called \emph{peripheral elements} of the set $\A$. Let us suppose that two spherical data sets $\pi_1,\pi_2$ with their main circles $K_j(c_j,\sigma_j)$, $j=1,2$ are given, where \begin{equation}\label{f0} c_j=\tfrac{1}{|\pi_j|}\sum\limits_{a\in\pi_j}a,\qquad \sigma^2_j=\tfrac{1}{|\pi_j|}\sum\limits_{a\in\pi_j}(c_j-a)^2. \end{equation} \begin{figure}[h!] \centering \includegraphics[width=4cm]{Fig1a.eps} \put(-108,70){\footnotesize (a) $\|c_1-c_2\|>\sigma_1+\sigma_2$ } \hspace*{2cm} \includegraphics[width=4cm]{Fig1b.eps} \put(-115,70){\footnotesize (b) $\|c_1-c_2\|=\sigma_1+\sigma_2$ } \\[2ex] \includegraphics[width=4cm]{Fig1c.eps} \put(-128,73){\footnotesize (c) $\|c_1-c_2\|<\sigma_1+\sigma_2<2\|c_1-c_2\|$ } \hspace*{2cm} \includegraphics[width=4cm]{Fig1d.eps} \put(-120,73){\footnotesize (d) $\sigma_1+\sigma_2>2\|c_1-c_2\|$} \caption{\small Mutually different relationships between two spherical data sets} \label{Fig1} \end{figure} %\FloatBarrier Mutually different relationships between two spherical data sets with regard to the relation between their main circles are shown in Fig.~\ref{Fig1}. As can be seen in Fig.~\ref{Fig1}, merging of the sets can be thought of if main circles $K_1,K_2$ intersect, i.e.\ if \begin{equation}\label{f1} \|c_1-c_2\|\leq \sigma_1+\sigma_2, \end{equation} what is also in accordance with the result from \cite{Behboodian1979}: \enquote{a mixture of two normal distributions $\mathcal{N}(c_1,\sigma^2_1)$, $\mathcal{N}(c_2,\sigma^2_2)$ is unimodal if $\|c_1-c_2\|\leq 2\min\{\sigma_1, \sigma_2\}$}, since there holds: $2\min\{\sigma_1, \sigma_2\}\leq \sigma_1+\sigma_2$. Therefore, as an indicator of sets connectivity the following coefficient can be used (see also \cite{Xiong2004}) \begin{equation}\label{tau} \tau=\tfrac{\sigma_1+\sigma_2}{\|c_1-c_2\|}. \end{equation} \begin{lemma}\label{Lem1} Let $K_j(c_j,\sigma_j)$, $j=1,2$ be the main circles of sets $\pi_1,\pi_2$ and let $K(c,\sigma)$ be the minimal circle that includes both circles $K_1,K_2$. Then $\sigma=\tfrac{1}{2}(\|c_1-c_2\|+\sigma_1+\sigma_2)$, and $K_1\cap K_2\neq\emptyset$ if and only if \begin{align} \label{f2}&(i)\quad\|c_1-c_2\|\leq \sigma_1+\sigma_2,\quad \text{ or }\\ \label{f3}&(ii)\quad\tau=\tfrac{\sigma_1+\sigma_2}{\|c_1-c_2\|}\geq 1,\quad \text{ or }\\ \label{f4}&(iii)\quad\partial K\leq \partial K_1+\partial K_2,\quad \text{ or }\\ \label{f5}&(iv)\quad\sigma\leq \sigma_1+\sigma_2. \end{align} \end{lemma} Proof of the lemma is trivial: $(i)$ is obvious, $(ii)$ immediately follows from $(i)$, and $(iii)$ and $(iv)$ follow from $(i)$ and \[ \partial K=2\sigma\pi=(\|c_1-c_2\|+ \sigma_1+\sigma_2)\pi\leq 2\sigma_1\pi+2\sigma_2\pi=\partial K_1+\partial K_2. \] \begin{remark}\label{Rem1} Note that the condition $(ii)$ is in direct relationship with the DB-index. Note also that the merging of several sets inevitably leads to the merging problem of ellipsoidal sets. Namely, the merging of two spherical sets forms an ellipsoidal set. \end{remark} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Merging of two ellipsoidal data sets} \label{ELI} Because of simplicity, we consider the merging problem of two ellipsoidal data sets in the plane. The problem in $\R^n$ is analogous. Let $c\in\R^2$ be the point in plane in the neighborhood of which the set $\A=\{a^i=(x_i,y_i)\in\R^2\colon i=1,\dots,m\}$ of $m$ random points were generated by using Gaussian distributions with covariance matrix $S$, and let $d_M\colon\R^2\times\R^2\to\R_+$ be the Mahalanobis distance-like function \cite{Bezdek2005, Spath1983, Theodoridis2009} \begin{equation}\label{M1} d_M(u,v;S)=\sqrt{\det S}(u-v)^TS^{-1}(u-v). \end{equation} Note that than the ellipse \begin{equation}\label{M2} E(c,\sigma)=\left\{(x,y)\in\R^2\colon d_M(c,(x,y);S)\leq \sigma^2\right\},\quad \sigma^2=\tfrac{1}{m}\sum\limits_{i=1}^md_M(c,a^i;S), \end{equation} contains about $68\%$ data points \cite{Bensic2012}. The ellipse $E(c,\sigma)$ will be called \emph{main Mahalanobis circle} (M-circle), and data points outside the ellipse $E(c,\sigma)$ will be called \emph{peripheral elements} of the set $\A$. Let us suppose that two ellipsoidal data sets $\pi_1,\pi_2$ with their main M-circles $E_j(c_j,\sigma_j)$, $j=1,2$ are given, where \begin{equation}\label{M3} c_j=\tfrac{1}{|\pi_j|}\sum\limits_{a\in\pi_j}a,\qquad \sigma^2_j=\tfrac{1}{|\pi_j|}\sum\limits_{a\in\pi_j}d_M(c_j,a;S_j), \end{equation} where $S_j$ is the corresponding covariance matrix. Mutually different relationships between two ellipsoidal data sets with regard to the relation of their main M-circles are shown in Fig.~\ref{Fig2}. \begin{figure}[h!] \centering \includegraphics[width=4cm]{Fig2a.eps} \put(-85,90){\footnotesize (a) $\sigma>\sigma_1+\sigma_2$ } \quad \includegraphics[width=4cm]{Fig2b.eps} \put(-85,90){\footnotesize (b) $\sigma>\sigma_1+\sigma_2$ } \quad \includegraphics[width=4cm]{Fig2c.eps} \put(-85,90){\footnotesize (c) $\sigma<\sigma_1+\sigma_2$ } \\ \includegraphics[height=3.5cm,width=4cm]{Fig2d.eps} \put(-85,90){\footnotesize (d) $\sigma>\sigma_1+\sigma_2$ } \quad \includegraphics[height=3.cm,width=4cm]{Fig2e.eps} \put(-85,90){\footnotesize (e) $\sigma>\sigma_1+\sigma_2$ } \quad \includegraphics[height=3cm,width=3.cm]{Fig2f.eps} \put(-85,90){\footnotesize (f) $\sigma<\sigma_1+\sigma_2$ } \caption{\small Mutually different relationships between two ellipsoidal data sets} \label{Fig2} \end{figure} %\FloatBarrier Of the criteria stated in Lemma~\ref{Lem1}, it seems that only the criterion $(iii)$ given by \eqref{f4} could be adjusted, but unfortunately, there is no explicit formula for determining the minimal ellipse $E(c,\sigma)$ that includes both ellipses $E_1,E_2$. Assuming that the center $c$, of the ellipse $E$, coincides with centroid of the set $\pi_1\cup\pi_2$, then M-radius $\sigma$, of the ellipse $E$, can be iteratively determined by Algorithm~\ref{Alg1}. According to this condition, sets $\pi_1,\pi_2$ with main M-circles $E_j(c_j,\sigma_j)$, $j=1,2$, will be merged if the following criterion holds \begin{flalign}\label{f6} \textbf{Criterion~1:}\qquad&\sigma<\sigma_1+\sigma_2.& \end{flalign} In Fig.~\ref{Fig2} several typical situations are shown. The numerical complexity of the determining the parameter $\sigma$ can be mentioned as the lack of Criterion~1, but also the fact that clusters in Fig.~\ref{Fig2}b would not be merged according to this criterion, although that would be expected. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{alg}\label{Alg1} \textbf{(Merging of two ellipsoidal sets)} {\setlength{\leftmargini}{3.5em} \begin{itemize} \item[\textsf{Step\,1:}] Input $\pi_1,\pi_2$, and set: $\A\!=\!\pi_1\cup\pi_2$, $m_1\!=\!|\pi_1|$, $m_2\!=\!|\pi_2|$, $m=m_1\!+\!m_2$, $\alpha\!=\!1$, $\epsilon\!>\!0$; \item[\textsf{Step\,2:}] For each $j=1,2$ determine: \hspace*{-1cm} \begin{align*} c_j&=\tfrac{1}{m_j}\sum\limits_{a\in\pi_j}a,& S_j&=\tfrac{1}{m_j}\sum\limits_{a\in\pi_j}(c_j-a)(c_j-a)^T,\\ \sigma_j^2&=\tfrac{1}{m_j}\sum\limits_{a\in\pi_j}d_M(c_j,a;S_j),& E_j&=\{a\in\pi_j\colon d_M(c_j,a;S_j)\leq\sigma_j^2\}, \end{align*} \vspace*{-.8cm} \begin{align*} \hspace*{.6cm}c&=\tfrac{1}{m }\sum\limits_{a\in\A}a,& S&=\tfrac{1}{m}\sum\limits_{a\in\A}(c-a)(c-a)^T,& \sigma^2_0&=\tfrac{1}{m}\sum\limits_{a\in\A}d_M(c,a;S); \end{align*} \vspace*{-.8cm} \item[\textsf{Step\,3:}] Set: $\sigma=\alpha\,\sigma_0$;\\ While $[\{a\in E_1\cup E_2\colon d_M(c,a;S)\geq\sigma^2\}\neq \emptyset, \alpha:=\alpha+\epsilon; \sigma=\alpha\,\sigma_0]$. \end{itemize} } \end{alg} Therefore, we try to define new conditions which will simplify the calculation, but also refine the conditions for merging. Instead of Criterion~1 we will define a criterion which is analogous to the condition $(i)$ given by \eqref{f2}, i.e.\ which is analogous to the condition $(ii)$ given by \eqref{f3} \begin{flalign}\label{f7} \textbf{Criterion 2:}\qquad&\Delta(c_1,c_2):=\min\{\sqrt{d_M(c_1,c_2;S_1)},\sqrt{d_M(c_1,c_2;S_2)}\} <\sigma_1+\sigma_2.& \end{flalign} According to this criterion the sets in Fig.~\ref{Fig2}b would be merged, but sets in Fig.~\ref{Fig2}d and Fig.~\ref{Fig2}e would also be merged, which should definitely be avoided. Namely, sets should not be merged if the angle between main directions of their M-circles is greater than a limit value (e.g., $65^o$). Therefore, let us introduce the following additional criterion \begin{flalign}\label{f8} \textbf{Criterion 3:}\qquad&sp_{12}:=|\langle v^1_{max},v^2_{max}\rangle|>\cos 65^o\approx 0.42,& \end{flalign} where $v^1_{max},v^2_{max}$ are unit eigenvectors corresponding to the largest eigenvalues of covariance matrices $S_1,S_2$. However, a new problem arises here: This criterion would not allow for the merging of sets in Fig.~\ref{Fig2}f~! Namely, the merging of sets that are not essentially ellipsoidal should be allowed for, although the angle between main directions of their M-circles is greater than the given limit value. We will assume that two sets $\pi_1$ and $\pi_2$ are not essentially ellipsoidal if the relative difference of their eigenvalues is less then $0.5$. The Criterion~3 will be refined as follows \begin{align} \nonumber&\hspace*{-1cm}\textbf{Criterion $\mathbf{3}^\prime$:}\\ \label{f9}& \delta_1=\tfrac{\lambda^{(1)}_1-\lambda^{(1)}_2}{\lambda^{(1)}_2}<0.5 \,\vee\, \delta_2=\tfrac{\lambda^{(2)}_1- \lambda^{(2)}_2}{\lambda^{(2)}_2}<0.5 \,\vee\, sp_{12}=|\langle v^1_{max},v^2_{max}\rangle|>\cos 65^o, \end{align} where $\lambda^{(1)}_1>\lambda^{(1)}_2>0$ and $\lambda^{(2)}_1> \lambda^{(2)}_2>0$ are eigenvalues of covariance matrices $S_1,S_2$. Note also that, since there holds \[ \neg(A\vee B \vee C)=(\neg A)\wedge(\neg B)\wedge(\neg C), \] according to the Criterion $\mathbf{3}^\prime$, the sets $\pi_1, \pi_2$ will be merged if at least one of them is almost spherical or if the angle between their main directions is less than $65^o$, and that they will not be merged if both are essentially ellipsoidal or if the angle between their main directions is greater than $65^o$. In this way, the Criterion $\mathbf{3}^\prime$ will not allow for the merging of sets shown in Fig.~\ref{Fig2}d and Fig.~\ref{Fig2}e, but it will allow for the merging of sets shown in Fig.~\ref{Fig2}f. The analysis of the impact of all the criteria is given in Table~\ref{Tab1}. Thereby, the mark \enquote{+} means that the sets should be merged, and the mark \enquote{-} means that the sets should not be merged. As can be seen in Fig.~\ref{Fig2}, the criterion which is composed of the Criterion~2 and the Criterion~$3^\prime$ can be acceptable. This criterion will be denoted as \textbf{Criterion~4}. \begin{table}[h!] \begin{center} {\small \begin{tabular}{lcccccc} \toprule Criterion &Fig.~\ref{Fig2}a&Fig.~\ref{Fig2}b&Fig.~\ref{Fig2}c&Fig.~\ref{Fig2}d&Fig.~\ref{Fig2}e&Fig.~\ref{Fig2}f\\ \midrule Criterion~1&-&-&+&-&-&+\\ Criterion~2&-&+&+&+&+&+\\ Criterion~3&+&+&+&-&-&-\\ Criterion~$3^\prime$&+&+&+&-&-&+\\ Criterion~4&-&+&+&-&-&+\\ \bottomrule \end{tabular} } \caption{The analysis of the impact of the criteria on situations given in Fig.~\ref{Fig2}} \label{Tab1} \end{center} \end{table} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{A new fusion algorithm} \label{FUS} Given is a data points set $\A=\{a^i\colon i=1,\dots,m\}\subset[\alpha,\beta]\subset\R^n$. Suppose that by some method (see \cite{Gustafson1979, Bezdek2005}) an optimal fuzzy partition $\Pi=\{\pi_1,\dots,\pi_k\}$ with membership matrix $U\in\R^{m\times k}$ and fuzzifier $q\in[1.5,2.5]$ is determined. Based on the considerations from Section~\ref{ELI}, we propose a new fusion algorithm. The algorithm takes as input the set $\A$ and optimal fuzzy $k$-partition with membership matrix $U\in\R^{m\times k}$ and fuzzifier $q\in[1.5,2.5]$ (Step~1). First, for each cluster the algorithm determines their center, covariance matrix with their largest and smallest eigenvalue and corresponding eigenvectors, and the radius of main M-circle (Step~2). In Step~3 the DB-index of initial partition is calculated. The next step is to see if there are possible candidates for merging in the given $k$-partition (Step~4). If there are such candidates, among all the pairs of clusters for which the condition \eqref{f7} is satisfied up to an $\epsilon>0$, Algorithm~\ref{Alg2} looks for that pair $\pi_r, \pi_s$ which coincides the most (Step~4) and defines a new partition with $(k-1)$ clusters $\left(\{\pi_1,\dots,\pi_k\}\setminus\{\pi_r, \pi_s\}\right)\cup\hat{\pi}$, where $\hat{\pi}$ is a cluster resulting form merging of two clusters $\pi_r, \pi_s$ (Step~5). The procedure is repeated until there are candidates for merging and while the value of the DB index decreases. By using Algorithm~\ref{Alg2} a new partition with the most appropriate number of clusters is obtained. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{alg}\label{Alg2} \textbf{(Fusion algorithm)} {\setlength{\leftmargini}{3.5em} \begin{itemize} \item[\textsf{Step\,1:}] Input: $\A\subset\R^n$, $U\in\R^{m\times k}$ and set $\epsilon>0$; \item[\textsf{Step\,2:}] For each $j=1,\dots,k$ determine $c_j=\tfrac{1}{\sum\limits_{i=1}^mu_{ij}^q} \sum\limits_{i=1}^m u_{ij}^q\, a^i$,\\ $S_j=\tfrac{1}{\sum\limits_{i=1}^mu_{ij}^q} \sum\limits_{i=1}^m u_{ij}^q\, (c_j-a^i)(c_j-a^i)^T$,\quad $\sigma^2_j=\tfrac{1}{\sum\limits_{i=1}^mu_{ij}^q} \sum\limits_{i=1}^m u_{ij}^q\,d_M(c_j,a^i;S_j)$, \\ and largest and smallest eigenvalue $(\lambda_{max}^j,\lambda_{min}^j)$ and corresponding eigenvectors $(v_{max}^j,v_{min}^j)$ of covariance matrix $S_j$; \item[\textsf{Step\,3:}] Determine DB-index $DB(k)=\tfrac{1}{k}\sum\limits_{r=1}^k\max\limits_{\begin{subarray}{c} s\in\{1,\dots,k\}\\ s\neq r \end{subarray}}\frac{\sigma^2_r+\sigma^2_s}{\max\{d_M(c_r,c_s;S_r),d_M(c_r,c_s;S_s)\}}$; \item[\textsf{Step\,4:}] Determine the set \[ \mathcal{J}_0=\{(r,s)\in J\times J\colon r\neq s, \kappa_{rs}+\epsilon>0\wedge(\delta_r<0.5\vee\delta_s<0.5\vee sp_{rs}>\cos 65^o)\}, \] where $\delta_r,\delta_s,sp_{rs}$ are given by \eqref{f9}, and \[ \kappa_{rs}=\sigma_r+\sigma_s-\min\{\sqrt{d_M(c_r,c_s;S_r)},\sqrt{d_M(c_r,c_s;S_s)}\}; \] If $\mathcal{J}_0=\emptyset$, Print[There are no candidates for merging]; STOP;\\ Else, $\{r_0,s_0\}=\argmax\limits_{(r,s)\in\mathcal{J}_0}\kappa_{rs}$; \item[\textsf{Step\,5:}] Define new partition $\left(\{\pi_1,\dots,\pi_k\}\setminus\{\pi_{r_0}, \pi_{s_0}\}\right)\cup\hat{\pi}$, where $\hat{\pi}$ is defined according to \textsf{Step~2} of Algorithm~\ref{Alg1};\\ Determine new DB-index $DB(k-1)$; \item[\textsf{Step\,6:}] If $DB(k-1)