## 2 Fuzzy and Noise Clustering  
The \(k\)-means clustering algorithm requires as input a dataset \(\{x_{1},\ldots,x_{n}\}\subset\mathbb{R}^{q}\). Assuming a predefined number of clusters \(k\), the algorithm tries to minimise the objective function, as follows:  
\[f\ =\ \sum_{i=1}^{k}\sum_{j=1}^{n}u_{ij}d_{ij} \tag{1}\]under the constraints  
\[\sum_{i=1}^{k}u_{ij}\ =\ 1\quad\quad\text{for all }j\in\{1,\ldots,n\} \tag{2}\]  
where \(u_{ij}\in\{0,1\}\) indicates whether data point \(x_{j}\) is assigned to cluster \(i\) (\(u_{ij}=1\)) or not (\(u_{ij}=0\)). \(d_{ij}=\parallel x_{j}-v_{i}\parallel^{2}\) denotes the squared Euclidean distance between data point \(x_{j}\) and cluster centre \(v_{i}\). As already mentioned before, the \(k\)-means algorithm tries to solve an NP-hard problem [16], which is a mixed discrete and continuous optimisation problem. The assignment of the data points to the clusters is a discrete problem whereas the estimation of the cluster centres is a continuous problem.  
Fuzzy clustering turns the mixed optimisation problem into a purely continuous one by relaxing the constraint \(u_{ij}\in\{0,1\}\) to \(u_{ij}\in[0,1]\). It is, however, quite easy to see that the optimum of the objective function with the relaxed constraint is still found at the margins, i.e., for the optimum \(u_{ij}\in\{0,1\}\) will hold although intermediate values are permitted. The simple reason is that for a data point, there is no benefit in assigning any share of its membership degree to a cluster centre that is not closest to the data point, as this would obviously increase the value of the objective function. There are essentially two different strategies to avoid the problem [20]. One way is the \"fuzzification\" of the membership transformation, i.e., to modify the linear weighting with the membership degrees \(u_{ij}\) in Equation (1) to  
\[f\ =\ \sum_{i=1}^{k}\sum_{j=1}^{n}h(u_{ij})d_{ij} \tag{3}\]  
with a suitable non-linear function, \(h\). The most common function, \(h\), is \(h(u)=u^{2}\)[21], or its generalisation, \(h(u)=u^{m}\), with the so-called fuzzifier, \(m>1\)[22].  
The alternative is to keep the linear weighting with the membership degrees and to introduce a regularisation term instead that punishes the values \(0\) and \(1\) by  
\[f\ =\ \sum_{i=1}^{k}\sum_{j=1}^{n}u_{ij}d_{ij}\ +\ \alpha\sum_{i=1}^{k}\sum_{j=1}^{ n}g(u_{ij}) \tag{4}\]  
with a suitable convex function, \(g\), on the unit interval. The parameter \(\alpha\) controls the penalty for membership degrees of \(0\) and \(1\). For \(\alpha=0\), one obtains the original \(k\)-means objective function. The larger the \(\alpha\), the more the membership degrees are pushed away from \(0\) and \(1\). As pointed out in [20], Daroczy entropy [23] provides a number of example functions for \(g\), leading to an approach that is very closely related to the EM algorithm [24]. In Section 3, the approach in Equation (4) will be used with a specific choice of the function \(g\) and the introduction of a so-called noise cluster.  
The idea of noise clustering goes back to [PERSON] [25] who introduced an additional cluster without a cluster centre or any other parameter to be optimised. Instead, the noise cluster has a fixed large predefined distance \(\delta\) to all data points. In this way, this noise cluster collects all points lying far away from all other clusters or cluster centres.