# Clustering with Neural Network and Index

Gangli Liu  Tsinghua University<EMAIL_ADDRESS>
(0000)

###### Abstract.

A new model called _C_ lustering with _N_ eural _N_ etwork and _I_ ndex (CNNI)
is introduced. CNNI uses a Neural Network to cluster data points. Training of
the Neural Network mimics supervised learning, with an internal clustering
evaluation index acting as the loss function. An experiment is conducted to
test the feasibility of the new model, and compared with results of other
clustering models like K-means and Gaussian Mixture Model (GMM). The result
shows CNNI can work properly for clustering data; CNNI equipped with MMJ-SC,
achieves the first parametric (inductive) clustering model that can deal with
non-convex shaped (non-flat geometry) data.

Clustering; Neural Network; MMJ-SC; Clustering Evaluation; K-means; Gaussian
Mixture Model; Self-Organizing Map

††copyright: none††doi: 00.000/000_0††isbn: 000-0000-00-000/00/00††conference:
000; 0000; Beijing, China††journalyear: 0000††price: 00.00

##  1\. Introduction

Cluster analysis is the grouping of objects such that objects in the same
cluster are more similar to each other than they are to objects in another
cluster. Clustering is a type of unsupervised learning method of machine
learning. In unsupervised learning, the inferences are drawn from the data
sets which do not contain labeled output variable. Due to its intensive
applications in data analysis, people have developed a wide variety of
clustering algorithms. Such as K-Means, Gaussian mixtures, Spectral clustering
(Ng et al., 2001), Hierarchical clustering (Johnson, 1967), DBSCAN (Schubert
et al., 2017), BIRCH (Zhang et al., 1996) etc.

Evaluation (or “validation”) of clustering results is as difficult as the
clustering itself (Pfitzner et al., 2009). Popular approaches involve
“internal” evaluation and “external” evaluation. In internal evaluation, a
clustering result is evaluated based on the data that was clustered itself.
Popular internal evaluation indices are Davies-Bouldin index (Petrović, 2006),
Silhouette coefficient (Aranganayagi and Thangavel, 2007), Dunn index (Bezdek
and Pal, 1995), and Calinski-Harabasz index (Maulik and Bandyopadhyay, 2002)
etc. In external evaluation, the clustering result is compared to an existing
“ground truth” classification, such as the Rand index (Yeung and Ruzzo, 2001).

There have been proposed several types of Artificial Neural Networks (ANNs)
with numerous different implementations for clustering tasks. Most of these
Neural Networks apply competitive learning rather than error-correction
learning as most other types of Neural Networks do.

Unlike Neural Networks used in competitive learning, CNNI mimics an error-
correction learning model.

(a) data 0

(b) data 1

(c) data 2

Figure 1. Three datasets for Experiment I

(a) NN A

(b) NN B

(c) NN C

(d) NN D

Figure 2. Four Neural Networks

##  2\. RELATED WORK

###  2.1. Internal clustering evaluation index

Calinski-Harabasz index (Maulik and Bandyopadhyay, 2002), Silhouette
coefficient (Aranganayagi and Thangavel, 2007), and Davies-Bouldin index
(Petrović, 2006) are three of the most popular techniques for internal
clustering evaluation.

Besides the three popular ones, numerous criteria have been proposed in the
literature (Vendramin et al., 2010; Chou et al., 2004; Žalik and Žalik, 2011;
Baya and Granitto, 2013; Moulavi et al., 2014). Such as DBCV (Moulavi et al.,
2014), Xie-Beni (XB) (Xie and Beni, 1991), CDbw (Halkidi and Vazirgiannis,
2008), S_Dbw (Halkidi and Vazirgiannis, 2001), and RMSSTD (Halkidi et al.,
2001). Besides, new cluster validity indices keep emerging, such as the CVNN
(Liu et al., 2013), CVDD (Hu and Zhong, 2019), DSI (Guan and Loew, 2020), SCV
(Xu et al., 2020), AWCD (Li et al., 2020) and VIASCKDE (Şenol, 2022). The
author also proposed one (Liu, 2022).

Because only Silhouette coefficient is used in this paper, following is some
detailed recount about it.

###  2.2. Silhouette coefficient (SC)

The Silhouette coefficient for a single sample is given as:

$s=\frac{b-a}{max(a,b)}$

where $a$ is the mean distance between a sample and all other points in the
same class. $b$ is the mean distance between a sample and all other points in
the next nearest cluster. The Silhouette coefficient for a set of samples is
given as the mean of Silhouette coefficient for each sample. The range of
Silhouette coefficient is $[-1,1]$. A higher Silhouette coefficient score
relates to a model with better defined clusters.

###  2.3. Artificial Neural Network

Artificial Neural Networks (ANNs), usually simply called Neural Networks (NNs)
or neural nets, are based on a collection of connected units or nodes called
artificial neurons, which loosely model the neurons in a biological brain
(Anderson, 1995; Gurney, 2018). Typically, neurons are aggregated into layers.
Different layers may perform different transformations on their inputs.
Signals travel from the first layer (the input layer), to the last layer (the
output layer), possibly after traversing the layers multiple times.

Training of a Neural Network is usually conducted by determining the
difference between the processed output of the network (often a prediction)
and a target output (Lu, 2022). This difference is the error. The network then
adjusts its parameters (weights and biases) according to a learning rule and
using this error value. Successive adjustments will cause the Neural Network
to produce output which is increasingly similar to the target output. After a
sufficient number of these adjustments the training can be terminated based
upon certain criteria. This is known as supervised learning.

###  2.4. Self-Organizing Map

Probably, the most popular type of neural nets used for clustering is called
Self-Organizing Map (SOM), also known as Kohonen network (Kohonen, 1990).
“There are many different types of Kohonen networks. These Neural Networks are
very different from most types of Neural Networks used for supervised tasks.
Kohonen networks consist of only two layers”. The structure of SOM may look
like perceptrons. “However, SOM works in a different way than perceptrons or
any other networks for supervised learning”.

In a SOM, each neuron of an output layer holds a vector whose dimensionality
equals the number of neurons in the input layer. “In turn, the number of
neurons in the input layer must be equal to the dimensionality of data points
given to the network”.

“When the network gets an input, the input is traversed into only one neuron
of the output layer, whose value is closer to the input vector than the values
of other output neurons. This neuron is called a winning neuron or the best
matching unit (BMU). This is a very important distinction from many other
types of Neural Networks, in which values propagate to all neurons in a
succeeding layer. And this process constitutes the principle of competitive
learning”. 111http://www.kovera.org/neural-network-for-clustering-in-python/

CNNI is also a Neural Network for clustering, but it works like Neural
Networks for supervised learning. The only difference is that we use an
internal clustering evaluation index as the loss function, adjust the weights
of the Neural Network to reduce the loss (improve the value of the index).

###  2.5. Deep Clustering

Deep clustering models use a Deep Neural Network (DNN) to transform high
dimensional data into more clustering-friendly representations without manual
feature extraction, then use a classic clustering model to cluster the
transformed data (Aljalbout et al., 2018; Ren et al., 2022; Zhou et al.,
2022). In these models, a Neural Network is used as a helper for clustering,
the “clustering” part of these models is still accomplished by classic
clustering models, such as K-means, Agglomerative clustering etc. In CNNI, no
other classic clustering models are needed.

##  3\.  The Structure of CNNI

The structure of CNNI is simple: a Neural Network for supervised learning plus
an internal clustering evaluation index. The index acts as the loss function,
because there is no target output associated with each input data point in
clustering scenario.

The number of neurons in the input layer of CNNI equals to the dimension of
the data points given to the network. The number of neurons in the output
layer of CNNI equals to number of $K$ clusters we want to classify. By
comparing values of output neurons, label of one data point is obtained (e.g.,
find out the maximum of output neurons).

Training of CNNI has some difference from other supervised learning Neural
Networks. We need to compute each data point’s label according to the Neural
Network’s current state, then calculate the value of the clustering evaluation
index, according to the labels of all data points. Adjustment of the weights
of the Neural Network is based on the value of the index.

(a) NN A

(b) NN B

(c) NN C

(d) K-means

(e) GMM

(f) NN A

(g) NN B

(h) NN C

(i) K-means

(j) GMM

Figure 3. Clustering results and decision boundaries of data 0

(a) NN A

(b) NN B

(c) NN C

(d) K-means

(e) GMM

(f) NN A

(g) NN B

(h) NN C

(i) K-means

(j) GMM

Figure 4. Clustering results and decision boundaries of data 1

(a) NN A

(b) NN B

(c) NN C

(d) K-means

(e) GMM

(f) NN A

(g) NN B

(h) NN C

(i) K-means

(j) GMM

Figure 5. Clustering results and decision boundaries of data 2

(a) data 3

(b) Clu-res

(c) Deci-boun

(d) Deci-boun-data

(e) Trans-data

(f) data 4

(g) Clu-res

(h) Deci-boun

(i) Deci-boun-data

(j) Trans-data

(k) data 5

(l) Clu-res

(m) Deci-boun

(n) Deci-boun-data

(o) Trans-data

Figure 6.  Clustering results, decision boundaries, and transformed data of
data 3,4,5 Figure 7. Clustering results of two-moons and two-circles by other
models (from the scikit-learn project)

(a) Clu-res

(b) Deci-boun

(c) Deci-boun-data

(d) Clu-res

(e) Deci-boun

(f) Deci-boun-data

Figure 8.  Clustering results and decision boundaries of automatic model
selection

##  4\. Experiments

We tested the practicability of CNNI with several experiments. In the
experiments, six synthetic datasets are to be clustered by four simple feed-
forward Neural Networks (FNNs) with different model capacity (Figure 2). All
the synthetic datasets are generated with library functions from the scikit-
learn project (Pedregosa et al., 2011).

Coordinate descent is used to train the Neural Networks.

###  4.1. Coordinate descent

Coordinate descent is an optimization algorithm that successively minimizes
along coordinate directions to find the minimum of a function. At each
iteration, the algorithm determines a coordinate or coordinate block via some
coordinate selection rule, then exactly or inexactly minimizes over the
corresponding coordinate hyperplane while fixing all other coordinates or
coordinate blocks. A line search along the coordinate direction can be
performed at the current iterate to determine the appropriate step size.
Coordinate descent is applicable in both differentiable and derivative-free
contexts. 222https://en.wikipedia.org/wiki/Coordinate_descent

In the experiments, we use a naive coordinate descent algorithm (Algorithm 1)
for adjusting parameters of the Neural Network. People can test more advanced
optimization techniques like gradient descent, genetic algorithms, and
particle swarm optimization etc.

Algorithm 1 Naive coordinate descent for CNNI

0: Neural Network’s parameter set: $N$, an Index: $I$, Epochs: $E$;

0: Optimized parameters of $N$;

1: Randomly initialize each member of $N$;

2: for $e$ in $E$;

3: for $n$ in $N$;

4: Make a random variation to $n$. If it improves $I$, keep it. Otherwise,
discard it;

5: return $N$.

###  4.2. Experiment I

In Experiment I, data 0, 1, and 2 are clustered with Neural Networks A, B, and
C. We trained each Neural Network with 30 Epochs for each dataset. After
training of the Neural Networks, we predict labels of 10,000 new data points,
and plot the decision boundaries of each model. Figure 3, 4, and 5 illustrate
the clustering results and decision boundaries discovered by the Neural
Networks, for each dataset, and compared with results of K-means and Gaussian
Mixture Model (GMM). Note the interesting decision boundaries discovered by
different Neural Networks for each dataset.

###  4.3. Experiment II

In another paper (Liu, 2023), we introduced a new internal clustering
evaluation index, called MMJ-based Silhouette coefficient (MMJ-SC). In
Experiment II, we test CNNI with this new index. In the experiment, data 3 and
4 are clustered with Neural Network D, data 5 is clustered with Neural Network
C.

The result is shown in Figure 6. The last column of Figure 6 plots the
transformed data by the Neural Networks after convergence. To get a
transformed point, after training of a Neural Network, we feed the Network
with a data point, the values of the output neurons are the coordinate of the
transformed data point. As shown by sub-figure (e) and (j) of Figure 6,
linearly non-separable data becomes linearly separable by the line $f(x)=x$,
after transformation by the Neural Network.

Figure 7 is clustering results of the two-moons and two-circles data by other
models (from the scikit-learn project). It can be seen that only Spectral
clustering, Agglomerative clustering, DBSCAN and OPTICS can deal with these
non-convex shaped (non-flat geometry) data. However, all these models are non-
parametric (transductive). That means we cannot get a set of parameters, and
predict the label of a new point based on the parameters. Therefore, we can
conclude that: CNNI equipped with MMJ-SC, is the first parametric (inductive)
clustering model that can deal with non-convex shaped (non-flat geometry)
data.

##  5\. Indices based on Fuzzy clustering

Fuzzy clustering (also referred to as soft clustering) is a form of clustering
in which each data point can belong to more than one cluster with probability.
As a comparison, in non-fuzzy clustering (also known as hard clustering), data
are divided into distinct clusters, where each data point can only belong to
exactly one cluster. By far we are using indices based on hard clustering,
however, Neural Networks can naturally output soft clustering, by applying a
Softmax activation to the last layer of a Neural Network.

In this section, we propose two soft clustering based indices and test one of
them on two challenging data.

###  5.1. Two soft clustering indices (SCIs)

####  5.1.1. SCI V1

###### Definition 5.1.

SCI V1

(1) $I_{sci}=\sum_{l\in L}P(l)I(l)$

where $L$ is the set of all possible labeling of data $X$; $l$ belongs to $L$;
$P(l)$ is the possibility of labeling $l$, it is easy to compute when we have
soft clustering of data $X$; $I(l)$ is an ordinary hard clustering based
index, like SC or MMJ-SC.

SCI V1 is very expensive to calculate naively, since there are $K^{N}$
possible labeling of data $X$, where $N$ is the number of points in $X$, $K$
is the number of clusters. Therefore, we do not test it in this paper.
Hopefully mathematicians will find a smart way to calculate it efficiently.

####  5.1.2. SCI V2

###### Definition 5.2.

SCI V2

(2) $I=\frac{1}{N}\sum_{x\in X}s(x)$

(3) $I_{sci}=\frac{1}{N}\sum_{x\in X}P(x)s(x)$

SCI V2 revises an ordinary hard clustering based index like SC or MMJ-SC, in
which the index for a set of samples is given as the mean of index for each
sample (Equation 2).

In the revision, we first determine the label for each sample $x$, by finding
the maximum probability of sample $x$ belonging to a cluster; $P(x)$ is the
probability of sample $x$ belonging to the cluster. After labels of all
samples are determined, then we can calculate the index value $s(x)$ for each
sample $x$. $N$ is the number of points in data $X$.

If $P(x)=1$ for all samples $x\in X$, then $I_{sci}=I$.

###  5.2. A new optimization algorithm for CNNI

Naive coordinate descent (Algorithm 1) works good for simple clustering task,
such as data 0-5 in Experiment I and II. For more challenging clustering tasks
like data 6 and 7 in Figure 9, naive coordinate descent seems not works.
Therefore, a new optimization algorithm for dealing with these more
challenging clustering tasks is designed.

The algorithm is called Step Back to See a Bigger Picture (SBSBP). In SBSBP,
we set a criteria to identify a local minima. If the criteria for recognizing
a local minima is reached, we randomly step back some steps; making the Neural
Network worse for clustering the data judged by the Index, so that the Neural
Network can jump out of the local minima region, and try to step to the global
minima. The best parameters so far are recorded so that we can restore it
after the training.

A local minima is identified if there is no improvement within some steps
(Patience).

Algorithm 2 Step Back to See a Bigger Picture (SBSBP)

0: Neural Network’s parameter set: $N$, an Index: $I$, Maximum steps: $M$,
hyper-parameter: $Patience$;

0: Optimized parameters of $N$;

1: Randomly initialize each member of $N$;

2: Calculate the Index $I$;

3: $Counter\leftarrow 0$;

4: for $i$ in $M$;

5: Randomly select a parameter $n$ from $N$;

6: Generate a random number $\delta$;

7: $n\leftarrow n+\delta$;

8: Calculate the Index $I$;

9: If $I$ improves:

10: $Counter\leftarrow 0$;

11: Keep the variation to $n$, continue;

12: Elif $I$ is invariant:

13: $Counter++$;

14: Restore previous value of $n$, $n\leftarrow n-\delta$;

15: Else:

16: $Counter++$;

17: If $Counter>Patience$:

18: $Counter\leftarrow 0$;

19: Randomly_step_back_some_steps;

20: Else:

21: Restore previous value of $n$, $n\leftarrow n-\delta$;

22: return $N$.

Algorithm 3 Randomly_step_back_some_steps

0: Neural Network’s parameter set: $N$, an Index: $I$, hyper-parameter:
$\rho_{1},\rho_{2}$;

1: $another\\_counter\leftarrow 0$;

2: $Steps\leftarrow random.randint(\rho_{1},\rho_{2})$;

3: while $another\\_counter<Steps$;

4: Randomly select a parameter $n$ from $N$;

5: Generate a random number $\delta$;

6: $n\leftarrow n+\delta$;

7: Calculate the Index $I$;

8: If $I$ worsens:

9: $another\\_counter++$;

10: Keep the variation to $n$, continue;

11: Else:

12: Restore previous value of $n$, $n\leftarrow n-\delta$;

###  5.3. Experiment III

In Experiment III, we revise MMJ-SC with SCI V2, and tested it with more
challenging clustering tasks of data 6 and 7 in Figure 9. Data 6 and 7 are
referred to as Data 45 and Data 106 in (Liu, 2022). The data sources
corresponding to the data IDs can be found at this URL.
333https://github.com/mike-liuliu/Experiment_data_of_a_paper

The Neural Network used in Experiment III has similar structure as the Neural
Networks in Figure 2, with one layer deeper and more nodes. It has shape
$2\rightarrow 80\rightarrow 80\rightarrow 80\rightarrow 10$, which has 14,010
parameters. The activation to the last layer is changed to Softmax. As
mentioned in Section 7.3.1, CNNI has some ability of automatic model
selection. Therefore, we set the number of output neurons to 10 and let the
Neural Network automatically select the true number of clusters. The Neural
Network is optimized with SBSBP.

In the experiment, the $Patience$ hyper-parameter is fixed. However, we can
also make it dynamic, so that it is lager in later stages of training. When
the index is a continuous value, we need to set a $Tolerance$ hyper-parameter
to decide whether the index has improved, or worsened, or unaffected. In the
experiment, the $Tolerance$ hyper-parameter is set to $10^{-8}$.

As shown by Figure 9, after millions of steps of training, the Neural Network
finally clustered the two data correctly, and learned reasonable (although
unsatisfactory) decision boundaries.

(a) data 6

(b) Clu-res

(c) Deci-boun

(d) Deci-boun-data

(e) data 7

(f) Clu-res

(g) Deci-boun

(h) Deci-boun-data

Figure 9. Clustering results and decision boundaries of data 6 and 7

##  6\. MMJ-K-means loss

Section 7.2 mentions we can use other losses like MMJ-K-means loss. In this
section, we conduct experiments to test this idea.

Equation 4 is the loss of standard K-means.

(4)
$\mathcal{L}=\frac{1}{N}\sum\limits_{i=1}^{N}\sum\limits_{k=1}^{K}\mathds{1}\\{c_{i}=k\\}\lvert\lvert
x_{i}-\mu_{k}\rvert\rvert^{2}$

where $N$ is number of points in data $X$, $K$ is the number of clusters.
$\mu_{k}$ is the centroid of cluster $k$, $c_{i}$ is the label of data point
$x_{i}$.

In MMJ-K-means loss, Euclidean distance is replaced by MMJ distance (Liu,
2023), centroid of a cluster is replaced by the One-SCOM of the cluster (Liu,
2021, 2023).

###  6.1. Experiment IV

In Experiment IV, we tested MMJ-K-means loss with data 6. The Neural Network
is optimized with SBSBP. Figure 10 illustrates the clustering result and
decision boundary. The result shows MMJ-K-means loss also works for
clustering, besides using an index as the loss function.

(a) Clu-res

(b) Deci-boun-data

Figure 10. Data 6 trained with MMJ-K-means loss

###  6.2. MMJ-K-means loss based on Soft Clustering

We can also revise the MMJ-K-means loss to utilize Soft Clustering.

(5)
$\mathcal{L}_{s}=\frac{1}{N}\sum\limits_{i=1}^{N}\sum\limits_{k=1}^{K}\mathds{1}\\{c_{i}=k\\}\lvert\lvert
x_{i}-\mu_{k}\rvert\rvert^{2}(2-P(x_{i}))$

Equation 5 is similar to SCI V2. We first use Hard Clustering to decide which
cluster data point $x_{i}$ belongs to, then use Soft Clustering to decide the
probability of data point $x_{i}$ belongs to the cluster. $P(x_{i})$ is the
probability.

If $P(x_{i})=1$ for all samples $x_{i}\in X$, then
$\mathcal{L}_{s}=\mathcal{L}$.

###  6.3. Experiment V

In Experiment V, we tested MMJ-K-means loss based on Soft Clustering, with
data 3 and 7. Section 7.4 discusses about training the Neural Network with
Mini-Batches of data $X$. In Experiment V, we use a variant of Mini-Batches,
and devise a new optimization algorithm (Algorithm 4) for optimizing the
Neural Network. In each iteration of Algorithm 4, we first draw a sample from
data X, then train the Neural Network with the sample and SBSBP for some
steps, then check if the Neural Network has improved for clustering the whole
data X. If it is, record the best parameters so far. The MMJ distance matrix
of sample $S$ is calculated under the context of data $X$, not $S$ itself. For
the definition of _context_ in MMJ distance, see (Liu, 2023).

(a) Clu-res

(b) Deci-boun-data

(c) Clu-res

(d) Deci-boun-data

Figure 11. Data 3 and 7 trained with MMJ-K-means loss based on Soft Clustering
(Equation 5) Algorithm 4 SBSBP and variant of Mini-Batch (MB-SBSBP)

0: Neural Network’s parameter set: $N$, Loss: $L$, Maximum iterations: $T$,
hyper-parameter: $M$;

0: Optimized parameters of $N$;

1: Randomly initialize each member of $N$;

2: for $j$ in $T$;

3: Draw a sample $S$ from data $X$, $S\subseteq X$;

4: Train the Neural Network with sample $S$ and SBSBP for $M$ steps;

5: Calculate the Loss $L$ over the whole data $X$;

6: If $L$ improves:

7: Record parameter set $N$;

8: return Recorded best parameters so far $N_{best}$.

Figure 11 illustrates the clustering results and decision boundaries. The
result shows optimizing MMJ-K-means loss based on Soft Clustering also works
for clustering.

The Neural Network used in Experiment IV and V has similar structure as the
Neural Network used in Experiment III. It has shape $2\rightarrow
80\rightarrow 80\rightarrow 80\rightarrow N\\_clusters$. We assume the true
number of clusters (N_clusters) is known in advance.

Section 6.2 of (Liu, 2023) discusses the issue of “multiple One-SCOMs in one
cluster”, in Experiment IV and V, we choose to keep them all.

Note although K-means loss is used in this section, the K-means model itself
is not used. Because a Neural Network can directly output Hard Clustering or
Soft Clustering label of a data point, we do not need the K-means model to
calculate the label of a data point. We just need the K-means loss.

##  7\. Discussion

###  7.1. Other choices

Because the purpose of this paper is to introduce CNNI and test its
feasibility. We used simple fully connected feed-forward Neural Networks, with
fixed activation function Tanh, and fixed clustering evaluation index
Silhouette coefficient and MMJ-SC in the experiments. We did not test more
advanced Neural Networks like convolutional neural network (CNN) or Bayesian
neural network (BNN), and more advanced optimization techniques like dropout
(Srivastava et al., 2014).

For optimization algorithms, we also tested “Nelder-Mead”, “Powell”, “CG”, and
“BFGS” implemented by SciPy (Virtanen et al., 2020). It seems “Powell” works
good for CNNI. Other optimization algorithms like gradient descent, genetic
algorithms, and other clustering evaluation indices were not tested either.

Further research is necessary to make more elaborate selections of these
factors.

###  7.2. Other losses

With labels of all data points known, another choice is to calculate other
losses, such as the likelihood of Gaussian Mixture Model, or the loss of MMJ-
K-means (Liu, 2023), then adjust Neural Network parameters by optimizing these
losses.

###  7.3. Model selection

Model selection of CNNI is easy and natural. We test Neural Networks with
different structures and different number of output neurons, and pick out the
one which obtains the best internal-clustering-evaluation-index value for
clustering the given dataset.

####  7.3.1. Automatic model selection

It seems CNNI has some ability of automatic model selection. Suppose the true
number of clusters is $K$, we can set the number of output neurons to $M$,
where $K\ll M$, hopefully, after training of the Neural Network, the number of
active output neurons will degenerate to $K$. We conducted an experiment to
test automatic model selection. In the experiment, we use Neural Network D to
cluster data 3 and 5. With the number of output neurons set to 30. The result
is shown in Figure 8. It can be seen that in the region where data appears,
the number of active output neurons degenerates to $K$, with some minor error.

###  7.4. Mini-Batch

Computing the internal clustering evaluation index over the whole dataset may
be time-consuming. We can divide the data into $M$ Mini-Batches by random
sampling, and use one Mini-Batch for training in one epoch. Or we can train
$M$ Neural Networks in parallel with the Mini-Batches, then calculate an
average Neural Network, then train the average Neural Network with the whole
dataset for several epochs.

###  7.5. How to understand the learning?

In supervised learning, the learning of the Neural Network is guided by a
tutor/teacher/supervisor, which is represented by a training dataset.

How to understand the learning of CNNI? What is guiding the learning? Maybe we
can consider the Neural Network is guided by some aesthetic sense, which is
represented by an internal clustering evaluation index.

###  7.6. Overfitting in unsupervised learning

(a) Clu-res

(b) Deci-boun-data

(c) Overfitting

Figure 12. Overfitting in unsupervised learning?

Overfitting is common in supervised learning models. Can overfitting occur in
unsupervised learning? Sub-figure 11(c) and 11(d) in Figure 11 seems provide a
new evidence, of overfitting in unsupervised learning.

As shown by Figure 12, although the Neural Network labeled each training data
point correctly, in the region indicated by the two black circles, the Neural
Network failed to learn a reasonable decision boundary. It seems the Neural
Network just “memorized” the correct labels of training data points, and
failed to generalize to new data points in the two regions.

##  8\. Conclusion and Future Works

We introduced a new clustering model called _C_ lustering with _N_ eural _N_
etwork and _I_ ndex (CNNI). Experiments are conducted to test the feasibility
of CNNI. In the experiments, synthetic datasets were clustered by simple feed-
forward Neural Networks (FNNs) with different model capacity. The result
shows:

  * $-$

CNNI can work properly for clustering data.

  * $-$

Different structures of Neural Networks result in different decision
boundaries.

  * $-$

CNNI equipped with MMJ-SC, achieves the first parametric (inductive)
clustering model that can deal with non-convex shaped (non-flat geometry)
data.

Further research is necessary to test other types of Neural Networks,
optimization techniques, and other clustering evaluation indices. And how CNNI
performs in higher dimensions.

A potential advantage of CNNI is its flexibility of model capacity. When the
hyperparameter $K$ (number of clusters) is fixed, the model capacity (number
of learnable parameters) of other parametric clustering models like K-means
and Gaussian Mixture Model (GMM) is fixed. The model capacity of CNNI is
flexible due to the utilization of Neural Network.

## References

  * (1)
  * Aljalbout et al. (2018) Elie Aljalbout, Vladimir Golkov, Yawar Siddiqui, Maximilian Strobel, and Daniel Cremers. 2018\.  Clustering with deep learning: Taxonomy and new methods.  _arXiv preprint arXiv:1801.07648_ (2018).
  * Anderson (1995) James A Anderson. 1995\.  _An introduction to neural networks_.  MIT press.
  * Aranganayagi and Thangavel (2007) S Aranganayagi and Kuttiyannan Thangavel. 2007.  Clustering categorical data using silhouette coefficient as a relocating measure. In _International conference on computational intelligence and multimedia applications (ICCIMA 2007)_ , Vol. 2. IEEE, 13–17.
  * Baya and Granitto (2013) Ariel E Baya and Pablo M Granitto. 2013.  How many clusters: A validation index for arbitrary-shaped clusters.  _IEEE/ACM Transactions on Computational Biology and Bioinformatics_ 10, 2 (2013), 401–414.
  * Bezdek and Pal (1995) James C Bezdek and Nikhil R Pal. 1995.  Cluster validation with generalized Dunn’s indices. In _Proceedings 1995 second New Zealand international two-stream conference on artificial neural networks and expert systems_. IEEE Computer Society, 190–190.
  * Chou et al. (2004) C-H Chou, M-C Su, and Eugene Lai. 2004.  A new cluster validity measure and its application to image compression.  _Pattern Analysis and Applications_ 7, 2 (2004), 205–220.
  * Guan and Loew (2020) Shuyue Guan and Murray Loew. 2020.  An internal cluster validity index using a distance-based separability measure. In _2020 IEEE 32nd international conference on tools with artificial intelligence (ICTAI)_. IEEE, 827–834.
  * Gurney (2018) Kevin Gurney. 2018\.  _An introduction to neural networks_.  CRC press.
  * Halkidi et al. (2001) Maria Halkidi, Yannis Batistakis, and Michalis Vazirgiannis. 2001\.  On clustering validation techniques.  _Journal of intelligent information systems_ 17, 2 (2001), 107–145.
  * Halkidi and Vazirgiannis (2001) Maria Halkidi and Michalis Vazirgiannis. 2001.  Clustering validity assessment: Finding the optimal partitioning of a data set. In _Proceedings 2001 IEEE international conference on data mining_. IEEE, 187–194.
  * Halkidi and Vazirgiannis (2008) Maria Halkidi and Michalis Vazirgiannis. 2008.  A density-based cluster validity approach using multi-representatives.  _Pattern Recognition Letters_ 29, 6 (2008), 773–786.
  * Hu and Zhong (2019) Lianyu Hu and Caiming Zhong. 2019.  An internal validity index based on density-involved distance.  _IEEE Access_ 7 (2019), 40038–40051.
  * Johnson (1967) Stephen C Johnson. 1967\.  Hierarchical clustering schemes.  _Psychometrika_ 32, 3 (1967), 241–254.
  * Kohonen (1990) Teuvo Kohonen. 1990\.  The self-organizing map.  _Proc. IEEE_ 78, 9 (1990), 1464–1480.
  * Li et al. (2020) Qi Li, Shihong Yue, Yaru Wang, Mingliang Ding, and Jia Li. 2020.  A new cluster validity index based on the adjustment of within-cluster distance.  _IEEE Access_ 8 (2020), 202872–202885.
  * Liu (2021) Gangli Liu. 2021\.  Topic model supervised by understanding map.  _arXiv preprint arXiv:2110.06043_ (2021).
  * Liu (2022) Gangli Liu. 2022\.  A New Index for Clustering Evaluation Based on Density Estimation.  _arXiv preprint arXiv:2207.01294_ (2022).
  * Liu (2023) Gangli Liu. 2023\.  Min-Max-Jump distance and its applications.  _arXiv preprint arXiv:2301.05994_ (2023).
  * Liu et al. (2013) Yanchi Liu, Zhongmou Li, Hui Xiong, Xuedong Gao, Junjie Wu, and Sen Wu. 2013\.  Understanding and enhancement of internal clustering validation measures.  _IEEE transactions on cybernetics_ 43, 3 (2013), 982–994.
  * Lu (2022) Wei Lu. 2022.  _Learning Guarantees for Graph Convolutional Networks in the Stochastic Block Model_.  Ph. D. Dissertation. Brandeis University.
  * Maulik and Bandyopadhyay (2002) Ujjwal Maulik and Sanghamitra Bandyopadhyay. 2002\.  Performance evaluation of some clustering algorithms and validity indices.  _IEEE Transactions on pattern analysis and machine intelligence_ 24, 12 (2002), 1650–1654.
  * Moulavi et al. (2014) Davoud Moulavi, Pablo A Jaskowiak, Ricardo JGB Campello, Arthur Zimek, and Jörg Sander. 2014\.  Density-based clustering validation. In _Proceedings of the 2014 SIAM international conference on data mining_. SIAM, 839–847.
  * Ng et al. (2001) Andrew Ng, Michael Jordan, and Yair Weiss. 2001\.  On spectral clustering: Analysis and an algorithm.  _Advances in neural information processing systems_ 14 (2001).
  * Pedregosa et al. (2011) F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. 2011.  Scikit-learn: Machine Learning in Python.  _Journal of Machine Learning Research_ 12 (2011), 2825–2830.
  * Petrović (2006) Slobodan Petrović. 2006\.  A comparison between the silhouette index and the davies-bouldin index in labelling ids clusters.  (2006).
  * Pfitzner et al. (2009) Darius Pfitzner, Richard Leibbrandt, and David Powers. 2009\.  Characterization and evaluation of similarity measures for pairs of clusterings.  _Knowledge and Information Systems_ 19, 3 (2009), 361–394.
  * Ren et al. (2022) Yazhou Ren, Jingyu Pu, Zhimeng Yang, Jie Xu, Guofeng Li, Xiaorong Pu, Philip S Yu, and Lifang He. 2022\.  Deep clustering: A comprehensive survey.  _arXiv preprint arXiv:2210.04142_ (2022).
  * Schubert et al. (2017) Erich Schubert, Jörg Sander, Martin Ester, Hans Peter Kriegel, and Xiaowei Xu. 2017\.  DBSCAN revisited, revisited: why and how you should (still) use DBSCAN.  _ACM Transactions on Database Systems (TODS)_ 42, 3 (2017), 1–21.
  * Şenol (2022) Ali Şenol. 2022\.  VIASCKDE Index: A Novel Internal Cluster Validity Index for Arbitrary-Shaped Clusters Based on the Kernel Density Estimation.  _Computational Intelligence and Neuroscience_ 2022 (2022).
  * Srivastava et al. (2014) Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. 2014.  Dropout: a simple way to prevent neural networks from overfitting.  _The journal of machine learning research_ 15, 1 (2014), 1929–1958.
  * Vendramin et al. (2010) Lucas Vendramin, Ricardo JGB Campello, and Eduardo R Hruschka. 2010.  Relative clustering validity criteria: A comparative overview.  _Statistical analysis and data mining: the ASA data science journal_ 3, 4 (2010), 209–235.
  * Virtanen et al. (2020) Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C J Carey, İlhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. 2020.  SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python.  _Nature Methods_ 17 (2020), 261–272.  https://doi.org/10.1038/s41592-019-0686-2
  * Xie and Beni (1991) Xuanli Lisa Xie and Gerardo Beni. 1991.  A validity measure for fuzzy clustering.  _IEEE Transactions on pattern analysis and machine intelligence_ 13, 8 (1991), 841–847.
  * Xu et al. (2020) Qin Xu, Qiang Zhang, Jinpei Liu, and Bin Luo. 2020\.  Efficient synthetical clustering validity indexes for hierarchical clustering.  _Expert Systems with Applications_ 151 (2020), 113367.
  * Yeung and Ruzzo (2001) Ka Yee Yeung and Walter L Ruzzo. 2001.  Details of the adjusted rand index and clustering algorithms, supplement to the paper an empirical study on principal component analysis for clustering gene expression data.  _Bioinformatics_ 17, 9 (2001), 763–774.
  * Žalik and Žalik (2011) Krista Rizman Žalik and Borut Žalik. 2011.  Validity index for clusters of different sizes and densities.  _Pattern Recognition Letters_ 32, 2 (2011), 221–234.
  * Zhang et al. (1996) Tian Zhang, Raghu Ramakrishnan, and Miron Livny. 1996\.  BIRCH: an efficient data clustering method for very large databases.  _ACM sigmod record_ 25, 2 (1996), 103–114.
  * Zhou et al. (2022) Sheng Zhou, Hongjia Xu, Zhuonan Zheng, Jiawei Chen, Jiajun Bu, Jia Wu, Xin Wang, Wenwu Zhu, Martin Ester, et al. 2022\.  A comprehensive survey on deep clustering: Taxonomy, challenges, and future directions.  _arXiv preprint arXiv:2206.07579_ (2022).