2.1. K-means Clustering Algorithm

The K-means clustering algorithm is probably the best-known non-hierarchical method.

In general, there are n data points x _i , i = 1…n that have to be partitioned into k clusters. The purpose is to appropriate a cluster to each data point. K-means is a method that tends to find the positions u _i , i = 1…k of the clusters that minimise the distance from the data points to the cluster. K-means clustering solves:

(1) $$\mathop {arg\;min}\limits_c \sum\limits_{i = 1}^k {\sum\limits_{x \in c_i} {d(x,u_i ) =}} \mathop {arg\;min}\limits_c \sum\limits_{i = 1}^k {\sum\limits_{x \in c_i} { \vert \vert x - u_i \vert \vert _2^2 \vert}} $$

where c _i is the collection of samples that belong to cluster i. K-means clustering uses the square of the Euclidean distance:

(2) $$d(x,u_i ) = \vert \vert x - u_i \vert \vert _2^2 $$

The procedure starts by determining the number of clusters, k. In the next step the algorithm designates a point as the cluster centre for each of the clusters: u _i  = a certain value, i = 1…k. In the third step all the samples are compared with each centre and assigned to the nearest cluster centre:

(3) $$c_i = \left\{ {\,j:d(x_j, u_i ) \le d(x_j, u_l ),\;l \ne i,j = 1, \ldots, n} \right\}$$

In the fourth step the centres of each cluster are recalculated by using the average vector of the samples assigned to the cluster:

(4) $$u_i = \displaystyle{1 \over { \vert c_i \vert}} \sum\nolimits_{\,j \in c_i} {x_j, \forall i} $$

where |c| is number of elements in c. The procedure is repeated until the centres no longer move around significantly (Li, Reference Li2007).

2.2. Hierarchical Clustering Algorithms

The agglomerative hierarchical algorithms fundamentally work in the following way. In the first step each of the samples to be clustered is examined as a unique cluster. The next step is to find the similarity or dissimilarity between every pair of samples in the data set. In this step the samples are compared using a selected measure of distance: Euclidean distance, standardised Euclidean distance, Minkowski distance, Mahalanobis distance, Chebychev distance or other. Next, the two clusters with smaller distance are linked. Only two clusters can be linked in each step (Mignoti and Lima, Reference Mignoti and Lima2006). A linkage method is used to compare the clusters in each step and to decide which should be grouped. There are several procedures for computing distance between clusters:

• • average (uses the average distance between all pairs of objects in any two clusters):

  (5) $$d(r,s) = \displaystyle{1 \over {n_r n_s}} \sum\limits_{i = 1}^{n_r} {\sum\limits_{\,j = 1}^{n_s} {dist(x_{ri}, x_{sj} )}} $$

• • centroid (uses the Euclidean distance between the centroids of the two clusters):

  (6) $$d(r,s) = \vert \vert \bar x_r - \bar x_s \vert \vert _2 $$
  where
  (7) $$\bar x(r) = \displaystyle{1 \over {n_r}} \sum\limits_{i = 1}^{n_r} {x_{ri}} $$

• • complete (uses the largest distance between objects in the two clusters):

  (8) $$d(r,s) = max\left( {dist(x_{ri}, x_{sj} )} \right),\quad i \in (1, \ldots, n_r ),\;j \in (1, \ldots, n_s )$$

• • median (uses the Euclidean distance between weighted centroids of the two clusters):

  (9) $$d(r,s) = \vert \vert \widetilde{{x_r}} - \widetilde{{x_s}} \vert \vert _2 $$

• • single (uses the smallest distance between objects in the two clusters):

  (10) $$d(r,s) = min\left( {dist(x_{ri}, x_{sj} )} \right),\quad i \in (1, \ldots, n_r ),\;j \in (1, \ldots, n_s )$$

• • wards (uses the incremental sum of squares):

  (11) $$d(r,s) = \sqrt {\displaystyle{{2n_r n_s} \over {(n_r + n_s )}}} \vert \vert \bar x_r - \bar x_s \vert \vert _2 $$

where: r,s are clusters, n is the number of samples in a cluster, x is a sample in the cluster, $\bar x$ is the centroid of the cluster, and $\tilde x$ is the weighted centroid of the cluster.

As samples are paired into binary clusters, the newly formed clusters are grouped into larger clusters until a hierarchical tree is formed. The procedure is repeated until the desired number of clusters is achieved.

2.3. Self-Organising Map (SOM)

A new idea to solve computational problems associated with processing abundant amounts of bathymetric data is to use Artificial Neural Networks (ANN). Various aspects of ANN solutions for navigation purposes have been described by several authors, e.g. Balicki et al. (Reference Balicki, Kitowski and Stateczny1998), Stateczny (Reference Stateczny and Katebi2002b; Reference Stateczny, Rutkowski, Siekmann and Tadeusiewicz2004). A very interesting idea is to cluster data by using a self-organising Kohonen network (Ciampi et al., Reference Ciampi, Lechevallier and Clustering2000; Kohonen, Reference Kohonen1982).

In the process of network learning there is no association between input signals and the output of the network. In the case of Kohonen networks, competition between neurons provides the basis for updating values assigned to weights. Put mathematically, it can be assumed that k is the number of clusters, x = (x ₁, x ₂, …, x _p )′ is the input vector in the training case, where p is the number of variables, and w _l  = (w _l1, w _l2, …, w _lp )′ is the weight vector associated with the node l, where w _lj indicates the weight assigned to input x _j to the node l. Several objects of the training data set are presented to the network in random order. During the competition between neurons, the neuron closest to the input sources, in the meaning of the chosen distance method calculation, is a winner for the input data set. The degree of adjustment depends on the distance of the neuron from the input data. The node l is moved some proportion of the distance between it and the training case. The proportion is determined by the learning rate. For several objects i in the training data set, the distance d _i between the weight vector and the input signal is calculated. Then the competition begins, and the node l with the smallest distance d _i is the winner. The weights of the winner are then updated using the learning rule. The weights of the non-winner are not modified. In general, the Euclidean distance is used to compare several neurons with several samples though any other metric could be chosen. The Euclidean distance between an object with observed vector x and the weight vector w _l is:

(12) $$d(x,w_l ) = {\left\lceil {\sum\limits_{\,j = 1}^p {(x_j - w_{lj} )^2}} \right\rceil}^{1 \over 2}$$

The weight vector for the lth node in the sth step of the algorithm can be represented as $w_l^s $ , X _i is the input vector for the ith training case and α^s is the learning rate for the sth step of training. After several steps, a training case X _i is selected and the index q of the winning node is determined:

(13) $$q = \mathop {arg\;min}\limits_l \vert \vert w_l^s - X_i \vert \vert $$

The Kohonen update rule for the winner node is:

(14) $$w_q^{s + 1} = w_q^s (1 - \alpha ^s ) + X_i \alpha ^s = w_q^s + \alpha ^s (X_i - w_q^s )$$

It should be noted that for all non-winning nodes l, $w_l^{s + 1} = w_l^s $ (Mignoti and Lima, Reference Mignoti and Lima2006). SOMs learn to cluster data based on similarity and topology, with a preference (but no guarantee) of assigning the same number of instances to each class. In Matlab software, SOMs take these arguments: layer topology function, row vector of dimension sizes, number of training steps for initial covering of the input space, initial neighbourhood size and neuron distance function.

3.1. Test Area

For collecting bathymetric data the authors used the interferometric sonar system GeoSwath Plus 250 kHz. The measurement profiles were realised maintaining 100% coverage of the measured body of water. Test data were collected within Szczecin Harbour, near the Babina Canal, on 23 May 2010. During the survey a large amount of data was collected. Nowadays typical data sets for hydrographic surveys might contain in the order of several hundred million to a billion or more soundings, spread over a hectare of surface area. Very high-density data present the main operational limitation when using a standard computer. In order to solve this problem, the authors divided the original data point sets into smaller subsets, which could be trained separately. In the next stages of the research, the authors will use the selected method over several differing test areas.

The test data set included 3,760 samples of three elements (x,y,z), as shown in Figure 2. Each point has three attributes: latitude, longitude, and a predetermined depth at a given point. The minimum depth is 3·60 m, the maximum is 5·23 m and the mean depth is 4·42 m.

Figure 2.

Test data from an area of 100 m² (Wlodarczyk-Sielicka and Stateczny, Reference Wlodarczyk-Sielicka, Stateczny and Rohling2015).

The data positions are given by the Universal Transverse Mercator (UTM) coordinate system, an international locational reference system.

3.2. Test Procedure

The main criterion for evaluating each method for reduction of bathymetric maps is the legibility of the maps. Therefore, at this stage of the research several populations were generated with number of clusters k = 9, 25, 49, 100. For the purpose of clustering, the K-means clustering algorithm, traditional hierarchical clustering algorithms and SOM were applied.

In the K-means algorithm, the Euclidean distance was used to measure similarities among clusters. In hierarchical clustering algorithms, four methods of grouping samples were selected: single, average, centroid and complete. In each method the Euclidean distance was used to calculate the distance between every pair of objects in a data set. In a data set made up of n objects, there are n(n − 1)/2 pairs. After selection of a hierarchical method, the number of clusters was specified. In the last method, during the training the network applies the rule Winner Take Most (WTM) according to which weight vector associated with each neuron moves to become the centre of a cluster of input vectors. In addition, neurons that are adjacent to each other in the topology are also moved close to each other in the input space. The authors decided to select the hexagonal network topology, where each of the hexagons represents a neuron. The numbers of rows and columns was set to 3 × 3, 5 × 5, 7 × 7 and 10 × 10, which provided 9, 25, 49 and 100 neurons, respectively. The initial neighbourhood size was set at three and the number of training steps for initial coverage of the input space was set at 100. Distances between neurons are calculated from their positions by means of a link distance function. The link distance from one neuron is the number of links or steps that must be taken to get to the neuron under consideration. The number of epochs was set at 200 based on recent research (Stateczny and Wlodarczyk-Sielicka, Reference Stateczny, Wlodarczyk-Sielicka and Kryszkiewicz2014). The total yield of 24 different sets of clusters was analysed. During the research the authors adopted the precision of two decimal places.