\documentclass{crorr} %%%%% journal info -- DO NOT CHANGE %%%%%%%%% \setcounter{page}{1} \renewcommand\thisnumber{1} \renewcommand\thisyear {2014} \renewcommand\thisvolume{6} \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 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \usepackage[displaymath,mathlines,pagewise]{lineno} \begin{document} \begin{linenumbers} \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$ } \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} \keywords{fusion algorithm, fuzzy clustering, Mahalanobis clustering, cluster merging, Davies-Bouldin index} \maketitle \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{Bezdek, Sabo, Scitovski2}). If $d\colon\R^n\times\R^n\to\R_{+}$, $\R_{+}=[0,+\infty\rangle$ is some distance-like function (see e.g.,\ \cite{Bezdek, Kogan}), 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 the 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 the set $\mathcal{A}$ can be reduced to the following \emph{global optimization problem} (see e.g.,\ \cite{Spath, Bezdek, Theodoridis}) \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{Scitovski2, Spath}. 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{Bezdek, Theodoridis} \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{Scitovski}). According to \cite{Bezdek, Theodoridis}, the membership grade of $a^i$ in cluster $\pi_j$ is determined by $u_{ij}^q$, where parameter $q>1$ is called a \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{Hoppner}. 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{Bezdek, Kaymak, Theodoridis, Vendramin}): Xie-Beni index, fuzzy Davies -- Bouldin index, Fuzzy Hypervolume index, etc. In our paper, we specially use the fuzzy Davies -- Bouldin index (DB) which is for the optimal partition $\Pi^\star(\pi^\star_1,\dots,\pi^\star_k)$ 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{Theodoridis, Vendramin}). It is well-known that by using the Least Squares (LS) distance-like function \cite{Bezdek, Kogan} spherical clusters are obtained, and by using adaptive Mahalanobis clustering \cite{Gustafson, Spath, Theodoridis} ellipsoidal clusters are obtained. However, if different banana-form clusters should be recognized, then some fusion method can be applied \cite{Bezdek, Frossyniotis, Kaymak, Xiong}. The idea is in the following: First, determine an optimal partition with relatively many clusters using a certain method and then 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 generalized for two ellipsoidal data sets and a corresponding merging algorithm is proposed. A new fusion algorithm is proposed in Section~\ref{FUS}, and Section~\ref{NUM} shows 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, $c\in\R^2$ the point in the 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{Bensic}. The set of all data points constitutes the set $\A$. The circle $K(c,\sigma)$ is called the \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}[ht!] \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{\it 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 Figure \ref{Fig1}. As can be seen in Figure \ref{Fig1}, merging of the sets can be thought of if the 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{Behboodian}: \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, the following coefficient can be used as an indicator of sets connectivity (see also \cite{Xiong}) \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 $K(c,\sigma)$ 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} The 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 condition $(ii)$ is in direct relationship with the DB-index. Note also that merging of several sets inevitably leads to the merging problem of ellipsoidal sets. Namely, 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 the 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 was 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{Bezdek, Spath, Theodoridis} \begin{equation}\label{M1} d_M(u,v;S)=\sqrt{\det S}(u-v)^TS^{-1}(u-v). \end{equation} Note that then 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{Bensic}. The ellipse $E(c,\sigma)$ will be called the \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 Figure \ref{Fig2}. \begin{figure}[ht!] \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{\it 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 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 the centroid of the set $\pi_1\cup\pi_2$, then the 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 the 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 Figure~\ref{Fig2}, several typical situations are shown. The numerical complexity of determining the parameter $\sigma$ can be mentioned as the lack of Criterion~1, but also the fact that clusters in Figure \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 to refine the conditions for merging. Instead of Criterion~1, we will define a criterion which is analogous to condition $(i)$ given by \eqref{f2}, i.e.,\ which is analogous to condition $(ii)$ given by \eqref{f3} \begin{flalign}\label{f7} \nonumber&\hspace{-0.7cm}\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 Figure \ref{Fig2}b would be merged, but sets in Figure \ref{Fig2}d and Figure\ref{Fig2}e would also be merged, which should definitely be avoided. Namely, sets should not be merged if the angle between the 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 Figure \ref{Fig2}f! Namely, the merging of sets that are not essentially ellipsoidal should be allowed for, although the angle between the 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 than $0.5$. Criterion~3 will be refined as follows: \begin{align} \nonumber&\hspace{-0.5cm}\textbf{Criterion $\mathbf{3}^\prime$:}\\ %\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), \] \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{\it Analysis of the impact of the criteria on situations given in Figure \ref{Fig2}} \label{Tab1} \end{center} \end{table} \noindent according to Criterion $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, Criterion $3^\prime$ will not allow for the merging of sets shown in Figures \ref{Fig2}d and \ref{Fig2}e, but it will allow for the merging of sets shown in Figure \ref{Fig2}f. The analysis of the impact of all criteria is given in Table~\ref{Tab1}. Thereby, marks \enquote{+} and \enquote{-} mean that the sets should be merged and not merged, respectively. As can be seen in Figure \ref{Fig2}, the criterion composed of Criterion~2 and Criterion~$3^\prime$ can be acceptable. This criterion will be denoted as Criterion~4. \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{Gustafson, Bezdek}) 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. As an input, the algorithm takes the set $\A$ and an 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 the corresponding eigenvectors, and the radius of the main M-circle (Step~2). In Step~3, the DB-index of the 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 pairs of clusters for which condition \eqref{f7} is satisfied up to an $\epsilon>0$, Algorithm~\ref{Alg2} looks for that pair $\pi_r, \pi_s$ which coincides 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 as long as 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 the largest and smallest eigenvalue $(\lambda_{max}^j,\lambda_{min}^j)$ and the 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 a 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 a new DB-index $DB(k-1)$; \item[\textsf{Step\,6:}] If $DB(k-1)