An improved MkNN clustering algorithm based on graph theory and membrane computing

Abstract

This paper combines the graph theory and P system to solve the clustering problem. In order to effectively identify clusters with arbitrary shapes and uneven densities, we combine MkNN clustering algorithm and graph theory to propose a mutual $k$ -nearest neighbors graph (MkNNG) clustering algorithm. In order to further improve the efficiency of MkNNG algorithm, based on the non-determinism and great parallelism of P system, a cell-like P system with multi-promoters and multi-inhibitors named mutual $k$ -nearest neighbors graph P system (MkNNG-P) is designed. And then based on MkNNG-P system, a novel clustering algorithm named MkNNG-P clustering algorithm is proposed, which uses the membrane objects and rules to solve the clustering problem. MkNNG-P algorithm first calculates the dissimilarity between any two nodes in $n-1$ membranes in parallel. After then it uses one membrane to get $k$ -nearest neighbors of $n$ nodes. Finally, one membrane is used to find mutual $k$ -nearest neighbors and construct MkNNG to discover the natural clusters in the data set. Experiments show that MkNNG-P algorithm has the advantages of both MkNNG and P system. It not only can obtain good clustering quality for data of different sizes and shapes without presetting clustering numbers, but also has extremely high computing speed.

Keywords

Membrane computing P system graph theory MkNN clustering algorithm

1. Introduction

As an unsupervised learning process, data clustering is a common tool for data analysis, which divides data points into several groups or clusters with intra-cluster data as similar as possible and extra-cluster data as dissimilar as possible. Over the past years, cluster analysis is widely used in many areas and many kinds of classical clustering algorithms have been proposed, such as hierarchical algorithms, partitioning algorithms, density-based algorithms, grid-based algorithms and so on. In recent years, due to the sharply increasing amounts of new-generated data and the growing kinds of disparate data sources, it becomes more and more difficult to obtain useful information from complex data using traditional clustering algorithms. Therefore, it is necessary to study clustering algorithms which can deal with these complex data such as high-dimensional data, complex structural data, large-scale data and so on. Graph-based clustering algorithms transform the clustering problem into the graph partitioning problem by treating objects as graph vertices and dissimilarities as edges with weights, regardless of the specific shape of the data, so it can cluster data of any shape, density, dimension [4].

A very important graph-based clustering algorithm is the spectral clustering algorithm [20]. The core idea of this algorithm is to construct a similar matrix from the input data, then calculate the eigenvectors of the matrix, and then select some vectors to map to a low-dimensional space. In this low-dimensional space, data is clustered into several clusters using traditional clustering methods such as K-means. Due to the use of dimensionality reduction, the complexity of spectral clustering is lower than that of traditional clustering algorithms when clustering high-dimensional data. However, since no effective parallel computing method is adopted, the computational complexity of spectral clustering is too high and the amount of computation is large, so this method is only suitable for small datasets. In addition, the number of feature vectors and the final number of clusters need to be determined in advance by experience, and these are very difficult.

As a new branch of natural computing, membrane computing, known as P system [5], is a class of distributed parallel computing models. It abstracts computing models from the structure and the functioning of living cells as well as from the cooperation of cells in tissues, organs, and other higher order structures such as colonies of cells. Because of its attractive features such as distribution, maximum parallelism and non-determinism, $P$ system has the higher computing power and satisfies the requirement of improving the processing speed of the large-scale data [18, 19]. Up to now, $P$ system has been applied in various areas such as biological modeling, graph theory, cryptology, fault diagnosis, combinatorial problems [21, 22, 25] and other fields [13].

This paper combines the graph theory and $P$ system to design a cell-like P system with multi-promoters and multi-inhibitors named mutual $k$ -nearest neighbors graph $P$ system (MkNNG-P). And then based on MkNNG-P system, a novel clustering algorithm named MkNNG-P clustering algorithm is proposed, which uses the membrane objects and rules to solve the clustering problem. Experiments and analyzes show that MkNNG-P algorithm not only can obtain good clustering quality for data of different sizes and shapes without presetting clustering numbers, but also has extremely high computing speed due to the inherent parallelism of $P$ system.

The remaining sections are organized as follows. Section 2 proposes an improved Graph-based clustering algorithm named mutual $k$ -nearest neighbors graph clustering algorithm (MkNNG). In Section 3, based on the parallel mechanism of $P$ system, we designed an MkNNG-P system and proposed an efficient clustering algorithm-MkNNG-P clustering algorithm. Then, in Section 4, the superiority of MkNNG-P clustering algorithm is proved through analysis and experiment. Finally, Section 5 concludes work.

2. The mutual $k$ -nearest neighbors graph clustering algorithm

In this section, we introduce the mutual $k$ -nearest neighbor graph (MkNNG) clustering algorithm. First, we formally describe the related concepts of MkNNG. Then, we describe the clustering process of MkNNG clustering algorithm in detail.

2.1 Preliminary

Firstly, we introduce two definitions related to MkNN clustering algorithm.

2.1.1 Definition 1: $k$ -nearest neighbors (kNN)

Let $x_{1},x_{2},\ldots x_{n}$ be $n$ data points in data set $S$ . For each $x_{i}$ in $S$ , $k$ most similar neighbors of $x_{i}$ are called $k$ -nearest neighbors (kNN) of $x_{i}$ , denoted as kNN ( $x_{i}$ ), kNN $(x_{i})\subseteq S$ .

2.1.2 Definition 2: Mutual $k$ -nearest neighbors (MkNN)

Given a data set $S$ , two points $x_{i}$ and $x_{j}$ , if and only if $x_{i}\in\textit{kNN}(x_{j})$ and $x_{j}\in\textit{kNN}(x_{i})$ , then $x_{i}$ and $x_{j}$ are mutual $k$ -nearest neighbors (MkNN) [16].

According to this definition, MkNN defines a two-way relationship between points [17]. If $x_{i}$ and $x_{j}$ are mutual $k$ -nearest neighbors, it means that $x_{i}$ is one of the $k$ -nearest neighbors of $x_{j}$ , and at the same time, $x_{j}$ is also belongs to the $k$ -nearest neighbors of $x_{i}$ .

In this paper, we extend this concept to graph: the data points are used as graph vertices and dissimilarities are used as edges with weight [15]. We propose the following two definitions:

2.1.3 Definition 3: $k$ -nearest neighbor graph (kNNG)

A $k$ -NNG is a directed weighted graph $G=(V,E)$ , where $V=\{v_{1},v_{2},\ldots v_{n}\}$ is the set of vertices and $E=\{e_{ij}|v_{i},v_{j}\in V,v_{j}\in\textit{kNN}(v_{i})\}$ is the set of edges. Each vertex $v_{i}$ is connected to its $k$ nearest neighbors with $k$ directed edges, and the direction of each edge is from $v_{i}$ to its $k$ nearest neighbors.

So, $k$ -NNG is a directed graph connecting each node to its $k$ nearest neighbors.

2.1.4 Definition 4: Mutual $k$ -nearest neighbor graph (MkNNG)

An MkNNG is an undirected weighted graph $G=(V,E)$ , where $V=\{v_{1},v_{2},\ldots v_{n}\}$ is the set of vertices and $E=\{e_{ij}|v_{i},v_{j}\in V,v_{j}\in\textit{kNN}(v_{i})\}$ .

$E=\{e_{ij}|v_{i},v_{j}\in V,v_{i}\in\textit{kNN}(v_{j})\cap v_{j}\in\textit{% kNN}(v_{i})\}$ is the set of edges. In MkNNG, for any vertex $v_{i}$ and $v_{j}$ in $V$ , there is an edge between $v_{i}$ and $v_{j}$ , if and only if vertex $v_{i}$ and $v_{j}$ are mutually $k$ -nearest-neighbors (MkNN).

There are several important characteristics of the MkNNG. These are:

(1)
MkNNG is symmetric and it is a sub-graph of the kNNG.

In kNNG, there is an edge between vertex $v_{i}$ and $v_{j}$ , if one of them belongs to the $k$ -nearest neighbors of the other. In contrast, MkNNG defines a two-way relationship between the vertices: there is an edge between vertex $v_{i}$ and $v_{j}$ if and only if $v_{i}$ is one of the $k$ nearest neighbors of $v_{j}$ and $v_{j}$ is also belongs to the $k$ -nearest neighbors of $v_{i}$ at the same time. Therefore, with the same data set and the same value of parameter $k$ , MkNNG is a sub-graph of kNNG.
(2)
Points in the same cluster can be grouped together by MkNNG.

In MkNNG, the mutually $k$ -neighbors (MkNN) are relatively close. They are connected one by one to form a connected subgraph. The nodes contained in the connected subgraphs are relatively close together so that they are clustered into the same clusters while the nodes in the non-connected subgraphs are relatively distant so that they belong to different clusters. Hence, points in the same cluster can be grouped together by MkNNG.

2.2 MkNNG clustering process

Assuming the data set to be clustered contains $n$ data points $S=\{x_{1},x_{2},\ldots x_{n}\}$ , where data point $x_{i}$ is an $m$ -dimensional vector, $x_{is}$ (1 $<s<m$ ) is the value of the $s$ -th vector of point $x_{i}$ and its value is a non-negative integer. Therefore, the data set $S$ can be expressed as a matrix $P_{nm}$ as Eq. (1):

$\displaystyle P_{nm}=\begin{bmatrix}x_{11}&x_{12}&\ldots&x_{1m}\\ x_{21}&x_{22}&\ldots&x_{2m}\\ \ldots&\ldots&\ldots&\ldots\\ x_{n1}&x_{n2}&\ldots&x_{nm}\\ \end{bmatrix}$ (1)

After transforming the data points $x_{1},x_{2},\ldots x_{n}$ of the data set into nodes $a_{1},a_{2},\ldots a_{n}$ of the graph, for a given parameter $k$ , MkNNG clustering algorithm is carried out through four key steps:

(1)

The first step, calculate the dissimilarity between any two nodes.

A $n\times n$ dissimilarity matrix $D_{nn}$ is defined as Eq. (2) to show the dissimilarity between any two nodes.

$\displaystyle D_{nn}=\begin{bmatrix}w_{11}&w_{12}&\ldots&w_{1n}\\ w_{21}&w_{22}&\ldots&w_{2n}\\ \ldots&\ldots&\ldots&\ldots\\ w_{n1}&w_{n2}&\ldots&w_{nn}\\ \end{bmatrix}$ (2)

Where, $w_{ij}$ is the dissimilarity between $a_{i}$ and $a_{j}$ . The smaller the dissimilarity value of $a_{i}$ and $a_{j}$ , the more similar they are. There are many ways to calculate the dissimilarity. Which method should be used depends on the type of object. In this paper, we use Manhattan Distance [26] to measure dissimilarity. Hence, the smaller the Manhattan distance between $a_{i}$ and $a_{j}$ , the more similar they are.

In this paper, $w_{ij}$ is defined as Eq. (3).

$\displaystyle w_{ij}=d(a_{i},a_{j})=\sum_{s=1}^{m}(|x_{is}-x_{js}|),x_{i}=\{x_% {i1},\ldots x_{im}\}(1<i,j<n).$ (3)

The distance matrix $D_{nn}$ is a symmetric matrix, where $w_{ij}=w_{ji}$ . In general, $m\ll n$ ( $m$ is the dimension of the data, $n$ is the number of data point in dataset), therefore, the time complexity of this step is $O(n^{2})$ .

(2)

The second step, search for the $k$ -nearest neighbors for each node, construct kNNG.

After getting the distance matrix $D_{nn}$ , kNNG can be constructed by searching the distance matrix $D_{nn}$ .

In computing and storage, the kNNG can be expressed as a form of adjacency matrix $A_{k-nn}$ , the elements of the matrix $a_{ij}$ are defined as Eq. (4).

$\displaystyle a_{ij}=\left\{\begin{array}[]{ll}1,&x_{j}\in\textit{KNN}(x_{i})% \\ 0,&x_{j}\notin\textit{KNN}(x_{i})\end{array}\right.$ (4)

In general, adjacency matrix $A_{k-nn}$ is not a symmetric matrix. The time complexity of constructing kNNG from distance matrix $D_{nn}$ is $O(n^{2})$ .

(3)

The third step, find mutual $k$ -nearest neighbors by searching kNNG, and then construct MkNNG.

In computing and storage, the mutual $k$ -nearest neighbor graph (MkNNG)also can be expressed as a form of adjacency matrix $A_{mk-nn}$ , the elements of the matrix $m_{ij}$ are defined as Eq. (5).

$\displaystyle m_{ij}=\left\{\begin{array}[]{ll}1,&a_{ij}*a_{ji}=1\\ 0,&a_{ij}*a_{ji}=0\end{array}.\right.$ (5)

Obviously, the adjacency matrix of MkNNG is a symmetric matrix. The time complexity of constructing MkNNG algorithm from kNNG is $O(n^{2})$ .

(4)

The fourth step, traverse MkNNG to get the clustering result.

MkNNG contains several connected subgraphs made up of mutual $k$ -nearest neighbors (when the subgraph contains only one node, it degenerates into an isolated point). Therefore, by traversing MkNNG, the final clustering result can be obtained.

As a novel clustering algorithm based on graph theory, MkNNG clustering algorithm has many advantages: (1) it does not need to preset the number of clusters; (2) it is robust to outliers; (3) it can find a variety of clusters with different densities and different shapes. While, for big database of high-dimensional data, its time complexity is too high. For instance, finding the $k$ -nearest neighbors of each node needs to calculate the distance between any two nodes in the data set and its time complexity is $O(n^{2})$ .

As a new bio-inspired computing model of membrane computing, $P$ system can reduce computational complexity due to its great parallelism, and it is especially suitable for dealing with complex problems. So, in order to further improve the time efficiency of MkNNG, in this paper, we combine the $P$ system and MkNNG clustering algorithm together to design a novel distributed and parallel computing model called mutual $k$ -nearest neighbors graph $P$ system (MkNNG-P) to solve the clustering problem.

3. MkNNG-P clustering algorithm

This section can be divided into three parts. In the first part, we introduce basic concept of cell-like $P$ system with promoters and inhibitors. In the second part, a $P$ System with Active Membrane named MkNNG-P system is designed. In the third part, we propose MkNNG clustering algorithm and describe the clustering process of it in detail.

3.1 Cell-like $P$ system with promoters and inhibitors

Membrane computing is a new branch of natural computing, which abstracts computing models from the structure and the functioning of living cells or tissues. The parallelism of $P$ system makes it has the higher computing power and been widely applied to many fields like graph theory, biological modeling, combinatorial problem and finite state problem [24]. In order to solve various practical problems, the scholars have been proposed many variants of the $P$ system [6, 9, 12]. There are three main types of $P$ systems: cell-like $P$ systems, neural-like $P$ systems [14] and tissue-like $P$ systems [2, 3, 23]. According to the scholars’ research, the applied research of membrane system can be divided into two categories, the direct membrane algorithm and the coupled membrane algorithm. The direct membrane algorithm designs the algorithm based on the structure, the objects and the rules of $P$ systems directly [1, 10, 11]. The coupled membrane algorithm is using indirect membrane algorithm to solve practical problems [7, 8].

Cell-like $P$ system is the most basic membrane computing model. A cell-like $P$ system is defined as follows:

$\displaystyle\Pi=(O,\mu,\omega_{0},\omega_{1},\omega_{2},\ldots\omega_{n-1},% \omega_{n},R_{0},R_{1},R_{2},\ldots R_{n-1},R_{n},\rho,i_{\textit{out}}),$

where,

•
$O$ is an alphabet which includes all the objects of the system.
•
$\mu$ is the membrane structure.
•
$w_{i}(0\leqslant i\leqslant n)$ is the initial multiset of objects in membrane $i$ .
•
$R_{i}(0\leqslant i\leqslant n)$ is the set of revolutionary rules in membrane $i$ . The form of $R_{i}$ is $u_{a}\rightarrow v$ , $u$ is the string of $O$ , and $v$ is the string over $\{a_{\textit{here}},a_{\textit{out}},a_{\textit{in}_{j}}|a\in 0,1<j<m\}$ , $a_{\textit{here}}$ means object $a$ remains in membran $i$ ï¿½, $a_{\textit{out}}$ means object $a$ is sent to the outer layer membrane, and $a_{\textit{in}_{j}}$ means object $a$ is sent to the inner membrane $j$ ï¿½. $a$ is the string over $\{g,\neg g^{\prime}\}$ . $g$ is a promoter and a rule can be executed when it exists. $\neg g^{\prime}$ is an inhibitors and a rule cannot be executed when it exists.
•
$\rho$ is the precedence level of rules.
•
$i_{\textit{out}}$ is the output membrane of this $P$ system.

3.2 The structure of MkNNG-P system

In this section, an active membrane $P$ system with promoters and inhibitors for MkNNG clustering algorithm is designed, which called MkNNG-P System. Its initial structure is shown in Fig. 1.

Figure 1.

The initial structure of MkNNG-P system.

The definition of MkNNG-P system is as follows:

$\displaystyle\Pi=(O,\mu,\omega_{0},\omega_{1},\omega_{2},\ldots\omega_{n-1},% \omega_{n},R_{0},R_{1},R_{2},\ldots R_{n-1},R_{n},\rho,n),$

where,

Alphabet: $O=\{a_{i},g,g^{\prime},D_{ij},o_{js},b_{js},h_{ij},v\}$ (1 $\leqslant i,j\leqslant n$ )

Membrane structure: $\mu=\left[[]_{1}[]_{2}\ldots[]_{n-1}[]_{n}\right]_{0}$ ;

Initial multisets:

$\displaystyle\omega_{0}=\{a_{i}^{k},g^{nk}\}(i=1,2,\ldots n),$ $\displaystyle\omega_{i}=\{o_{js}^{w_{is}},b_{js}^{w_{is}}\}(1\leqslant s% \leqslant m,1\leqslant i\leqslant n-1,i+1\leqslant j\leqslant n),$ $\displaystyle\omega_{n}=\{\lambda\};$

Output membrane: $i_{0}=n$

The rules in $R_{0}$ :

$\displaystyle r_{0}=\{a_{i}\neg(D_{ij},a_{ij})\rightarrow a_{ij}g^{\prime}\}(1% \leqslant i,j\leqslant n)$ $\displaystyle r_{1}=\{(D_{i1}D_{i2}\ldots D_{in})_{v}\rightarrow\lambda\}(1% \leqslant i\leqslant n)$ $\displaystyle r_{2}=\{(D_{ij_{1}}D_{ij_{2}}\ldots D_{ij_{(n-1)}})_{v}% \rightarrow\lambda\}(1\leqslant i,j_{1},j_{2},\ldots j_{(n-1)}\leqslant n)$ $\displaystyle r_{3}=\{(D_{ij_{1}}D_{ij_{2}}\ldots D_{ij_{(n-2)}})_{v}% \rightarrow\lambda\}(1\leqslant i,j_{1},j_{2},\ldots j_{(n-2)}\leqslant n)\ldots$ $\displaystyle r_{k}=\{(D_{ij_{1}}D_{ij_{2}}\ldots D_{ij_{(n-k+1)}})_{v}% \rightarrow\lambda\}(1\leqslant i,j_{1},j_{2},\ldots j_{(n-k+1)}\leqslant n)$ $\displaystyle r_{n-1}=\{(D_{ij_{1}}D_{ij_{2}})_{v}\rightarrow\lambda\}(1% \leqslant i,j_{1},j_{2}\leqslant n)$ $\displaystyle r_{n}=\{gg^{\prime}\rightarrow\lambda\}$ $\displaystyle r_{n+1}=\{a_{ij\neg g}\rightarrow(a_{ij})_{\textit{in }n}\}(1% \leqslant i,j\leqslant n)$

The rules in $R_{i}$ : (0 $\leqslant i\leqslant n-1$ )

$\displaystyle r_{i1}=\{o_{js}b_{js}\rightarrow\lambda\}(1\leqslant s\leqslant m% ,i+1\leqslant j\leqslant n)$ $\displaystyle r_{i2}=\{o_{js}\rightarrow(D_{ij}D_{ji},\textit{out})\}\cup\{b_{% js}\rightarrow(D_{ij}D_{ji},\textit{out})\}(1\leqslant s\leqslant m,i+1% \leqslant j\leqslant n)$

The rules in $R_{n}$ :

$\displaystyle r_{1-1}=\{a_{ij}a_{ji}\rightarrow h_{ij}\}(1\leqslant i<j% \leqslant n)$ $\displaystyle r_{1-2}=\{a_{ij}\rightarrow\lambda\}\cup\{a_{ji}\rightarrow% \lambda\}(1\leqslant i<j\leqslant n)$

The priority relations $\rho$ over $R$ :

$\displaystyle\rho=\{r_{i1}>r_{i2}\}\cup\{r_{j}>r_{k}\}\cup\{r_{1-1}>r_{1-2}\}(% 0\leqslant i\leqslant n-1,0\leqslant j<k\leqslant n+1)$

3.3 The computational process of MkNNG-P clustering algorithm

The MkNNG-P system contains $n+1$ membranes: $n-1$ membranes are used to calculate the dissimilarity (distance) between any two nodes in the data set, one membrane is used to obtained $k$ -nearest neighbors for each node, one membrane is used to find mutual $k$ -nearest neighbors in the data set and it is also used to store the results.

In the initial state, membrane $i$ (0 $<i<n-1$ ) contains objects $o_{js}^{x_{is}}$ , $b_{js}^{x_{js}}$ (1 $\leqslant s\leqslant m,i+1\leqslant j\leqslant n$ ). The object $o_{js}$ represents $i$ -th the data node $x_{i}$ of the data set and the object $b_{js}$ represents all the data nodes $x_{1}$ , $x_{2}$ , … $x_{n}$ . The number of $o_{js}^{x_{is}}$ and $b_{js}^{x_{js}}$ is equivalent to $x_{is}$ and $x_{js}$ of the matrix $P_{nm}$ .

In the initial state, membrane 0 (the skin membrane) contains the object $a_{i}^{k}$ , $g^{nk}$ ( $i=1,2,\ldots n$ ). Object $a_{i}$ means the $i$ -th data in the data set and $a_{i}^{k}$ means the $k$ -nearest neighbors of each object $a_{i}$ . Objects $g^{nk}$ are auxiliary objects which means the total number of $k$ nearest neighbors that all objects $a_{i}$ need to obtain is $n k$ .

Membrane $n$ is the output membrane, which does not contain any object in the initial state.

The computational process of MkNNG-P is as follows:

3.3.1 Calculate the dissimilarity (distance) between any two nodes

In the initial state of the $P$ system, the rules that can be executed are $r_{i1}$ and $r_{i2}$ in membrane $i$ (0 $<i<n-1$ ). Rule $r_{i1}$ eliminate the same parts of the individual $a_{i}$ and $a_{j}$ . Rule $r_{i2}$ transform the different parts into object $D_{ij}$ and $D_{ji}$ , sending them into the skin membrane and dissolving membrane $i$ . Here, the number of $D_{ij}$ represents the dissimilarity $w_{ij}$ between individual $a_{i}$ and $a_{j}$ .

3.3.2 Obtained $k$ -nearest neighbors for each object

When the objects $D_{ij}$ are received, the rules in the skin membrane are activated. Rule $r_{1}$ is executed first to eliminate the same number of objects $D_{i1}$ , $D_{i2}$ , … $D_{in}$ . The object $D_{ij-_{1}}$ , which is the first to be completely eliminated, has the least number of all objects $D_{i1}$ , $D_{i2}$ , … $D_{in}$ . It means the node $a_{j-_{1}}$ is the nearest neighbor of node $a_{i}$ . After that, Ruler $r_{0}$ is executed to generate an object $a_{ij-_{1}}$ to store the results. That is to say, $a_{ij-_{1}}$ represents the node $D_{j-_{1}}$ is the nearest neighbor of node $a_{i}$ . After then, rule $r_{2}$ is executed to eliminate the same number of objects $D_{ij_{1}}$ , $D_{ij_{2}}$ … $D_{ij_{(n-1)}}$ . The object $D_{ij-_{2}}$ , which is the second object to be completely eliminated, has the least number of all objects $D_{ij_{1}}$ , $D_{ij_{2}}$ … $D_{ij_{(n-1)}}$ . It means the node $a_{j-_{2}}$ is the second-nearest neighbor of node $a_{i}$ . After that, rule $r_{0}$ is executed to generate an object $a_{ij-_{2}}$ to store the result which represents the node $a_{j-_{2}}$ is the second-nearest neighbor of node $a_{i}$ . … The above process will continue until rule $r_{k}$ is executed to eliminate the same number of object $D_{i1}$ , $D_{i2}$ … $D_{ij_{(n-k+1)}}$ . The objects $D_{ij-_{k}}$ , which is the $k$ -th to be completely eliminated, has the least number of all objects $D_{i1}$ , $D_{i2}$ … $D_{ij_{(n-k+1)}}$ . It means node $a_{j-_{k}}$ is the ( $k$ -th)-nearest neighbor of node $a_{i}$ . Rule $r_{0}$ is executed to generate an object $a_{ij-_{k}}$ to store the result which represents the node $a_{j-_{k}}$ is the ( $k$ -th)-nearest neighbor of node $a_{i}$ .

When all $k$ -nearest neighbors of node $a_{i}$ (0 $<i<n$ ) have been obtained, the rule $r_{n+1}$ is activated to send all the generated objects $a_{ij}$ into membrane $n$ . Here, object $a_{ij}$ means node $a_{j}$ is one of the $k$ -nearest neighbors of node $a_{i}$ .

3.3.3 Cluster the mutual $k$ -nearest neighbors into the same cluster

When the object are received, the rule $r_{1-1}$ in membrane $n$ is activated. Object $a_{ij}$ means $a_{j}$ is one of the $k$ -nearest neighbors of $a_{i}$ and $a_{ji}$ means $a_{i}$ is one of the $k$ -nearest neighbors of $a_{j}$ . When objects $a_{ij}$ and $a_{ji}$ exist together, object $h_{ij}$ is generated. It means that $a_{i}$ and $a_{j}$ are mutual $k$ -nearest neighbors and should be clustered into the same cluster. After that, the remaining objects $a_{ij}$ are eliminated.

At the termination of the system, the objects $h_{ij}$ in the output membrane $n$ represent the final clustering result.

All the objects $h_{ij}$ that can be connected together form a connected subgraph. The nodes in the same connected subgraph belong to the same cluster and the nodes in different connected subgraphs belong to different clusters. The nodes that are not in any connected subgraphs are outliers.

Figure 2.

The sample points waiting for clustering.

That is, if there exists an object $h_{ij}$ , it means that the nodes $a_{i}$ and $a_{j}$ belong to the same cluster; if both $h_{ij}$ and $h_{jk}$ exist or both $h_{ij}$ and $h_{kj}$ exist, it means that the nodes $a_{i}$ , $a_{j}$ and $a_{k}$ belong to the same cluster. The nodes whose labels do not appear in $h_{ij}$ indicate that they are not in any connected subgraph and are outliers.

3.4 Example and illustration

We use a concrete example to illustrate the clustering process of the above MkNNG-P system. For simplicity, we choose two-dimensional data points to experiment. The data set $S=\{$ (1,3), (2,3), (3,3), (1,6), (5,2), (6,2), (6,4), (6,8), (8,6) $\}$ (as shown in Fig. 2), the number of nearest neighbors $k=$ 3. Obviously, $n=$ 9, $m=$ 2. Its data matrix is $P_{92}$ .

MkNNG-P system contains 10 membranes. Membrane 1 to membrane 8 are used to calculate the dissimilarity between any two nodes in the data set. Membrane 0 (the skin membrane) is used to obtain 3-nearest neighbors for each node. Membrane 9 is used to find mutual 3-nearest neighbors in the data set and it is also used as the output membrane to store the final result. The initial membrane structure of MkNNG-P system is shown in Fig. 3.

In the initial state of this $P$ system, the rules that can be executed are $r_{i1}$ and $r_{i2}$ of membrane 1-8 (0 $<i<$ 8). The rules $r_{i1}$ eliminate the same parts of the individual $a_{i}$ and $a_{j}$ . The rules $r_{i2}$ transform the different parts into object $D_{ij}$ and $D_{ji}$ , sending it into the skin membrane. The number of $D_{ij}$ represents the dissimilarity $w_{ij}$ between nodes $a_{i}$ and $a_{j}$ . The resulting objects $D_{ij}$ are as follows:

$\displaystyle\left(\begin{array}[]{ccccccccc}&D_{12}^{1}&D_{13}^{2}&D_{14}^{3}% &D_{15}^{2}&D_{16}^{6}&D_{17}^{6}&D_{18}^{8}&D_{19}^{10}\\ D_{12}^{1}&&D_{23}^{1}&D_{24}^{4}&D_{25}^{1}&D_{26}^{5}&D_{27}^{5}&D_{28}^{7}&% D_{29}^{9}\\ D_{31}^{2}&D_{32}^{1}&&D_{34}^{5}&D_{35}^{2}&D_{36}^{4}&D_{37}^{4}&D_{38}^{6}&% D_{39}^{8}\\ D_{41}^{3}&D_{42}^{4}&D_{43}^{5}&&D_{45}^{5}&D_{46}^{9}&D_{47}^{7}&D_{48}^{5}&% D_{49}^{7}\\ D_{51}^{2}&D_{52}^{1}&D_{53}^{2}&D_{54}^{5}&&D_{56}^{4}&D_{57}^{6}&D_{58}^{8}&% D_{59}^{10}\\ D_{61}^{6}&D_{62}^{5}&D_{63}^{4}&D_{64}^{9}&D_{65}^{4}&&D_{67}^{2}&D_{68}^{4}&% D_{69}^{6}\\ D_{71}^{6}&D_{72}^{5}&D_{73}^{4}&D_{74}^{7}&D_{75}^{6}&D_{76}^{2}&&D_{78}^{2}&% D_{79}^{4}\\ D_{81}^{8}&D_{82}^{7}&D_{83}^{6}&D_{84}^{5}&D_{85}^{8}&D_{86}^{4}&D_{87}^{2}&&% D_{89}^{2}\\ D_{91}^{10}&D_{92}^{9}&D_{93}^{8}&D_{94}^{7}&D_{95}^{10}&D_{96}^{6}&D_{97}^{4}% &D_{98}^{2}&\\ \end{array}\right)$

When the objects $D_{ij}$ are received, rule $r_{1}$ in the skin membrane is executed to eliminate the same number of objects $D_{i1}$ , $D_{i2}$ , … $D_{in}$ . The object which is the first to be completely eliminated is the nearest neighbor of node $a_{i}$ . The second object to be completely eliminated is the next nearest neighbor of $a_{i}$ . The third object to be completely eliminated is the third nearest neighbor of $a_{i}$ . Rule $r_{0}$ is executed to store the result. In this way, we get 3-neighbors of all nodes. They are:

$\displaystyle a_{12},a_{13},a_{15},\quad a_{21},a_{23},a_{25},\quad a_{31},a_{% 32},a_{35},\quad a_{41},a_{42},a_{43},\quad a_{51},a_{52},a_{53},$ $\displaystyle a_{63},a_{65},a_{67},\quad a_{73},a_{76},a_{78},\quad a_{86},a_{% 87},a_{89},\quad a_{96},a_{97},a_{98},$

After the membrane $n$ receives the objects $a_{i,j}$ which are sent from the membrane 0, it executes the rule $r_{1-1}$ to obtain all the mutual 3-nearest neighbors in the data set and represent them by the object $h_{i,j}$ .

The final state of this $P$ system is shown in Fig. 4. Based on the connectivity of the object $h_{i,j}$ , we can find that: nodes $a_{1}$ , $a_{2}$ , $a_{3}$ , $a_{5}$ form a connected subgraph, nodes $a_{6}$ , $a_{7}$ , $a_{8}$ , $a_{9}$ form another connected subgraph, and the node $a_{4}$ does not appear in $h_{i,j}$ means that it is an isolated node. Therefore, the clustering result of this P-system is: the data points in the data set $S$ are clustered into two clusters, $C_{1}=\{$ (1,3), (2,3), (3,3), (5,2)}, $C_{2}=\{$ (6,2), (6,4), (6,8), (8,6) $\}$ , data point (1,6) is an isolated point.

Figure 3.

The initial structure of an instance-based $P$ system.

Figure 4.

The final state of an instance-based $P$ system.

4. Test and analysis

In this section, we first analyze the time complexity of MkNNG-P clustering algorithm and compare it with several classical algorithms. Then, the effectiveness of MkNNG-P was verified by experiments. Finally, we analyze the effect of parameter $k$ on the experimental results.

4.1 Complexity analysis

According to the previous analysis, the time complexity of MkNNG is $O(kn^{2})$ , where $n$ is the number of data points in the data set and $k$ is the number of nearest neighbors for each node.

Due to the great parallelism of P-systems, the time complexity of MkNNG-P algorithm is greatly reduced. Since $n$ membranes work in parallel and the rules in each membrane are also extremely parallel, the time complexity of MkNNG-P clustering algorithm in the first step is $O(1)$ . In the second step, because $n$ nodes can find their $k$ -nearest neighbors in parallel, the time complexity of the algorithm in this step is $O(k)$ , where $k$ is the number of neighbors. In the third step, the time complexity of obtaining MkNNG is $O(1)$ . Therefore, the overall time complexity of MkNNG-P algorithm is $O(k)$ . In general, $k\ll n$ , so in this case, the time complexity of MkNNG-P is approximately equal to $O(1)$ .

In order to further prove the superiority of MkNNG-P algorithm in the execution efficiency, we list the time complexity of several classical algorithms in Table 1. It can be found that the MkNNG-P system greatly improves the time efficiency in computation, so it is suitable for clustering large data sets.

Table 1
Time complexities of several classical algorithms

Algorithm	$k$ -means	$k$ -medoids	PAM	CLARA	CLARANS
Time complexity	$O(knt)$	$O(k(n-k)^{2})$	$O(k(n-k)^{2})$	$O(ks^{2}+k(n-k))$	$O(n^{2})$
Algorithm	BIRCH	Chameleon	ROCK	MkNNG	MkNNG-P
Time complexity	$O(n)$	$O(n^{2})$	$O(n^{2}\log n)$	$O(kn^{2})$	$O(k)$

Table 2

A quantitative comparison of clustering results generated by $k$ -Means, DBSCAN, OPTICS, MkNNG-P on Compound and Jain datasets

Algorithm	Compound		Jain
	ARI	NMI	ARI	NMI
$k$ -Means	0.5364	0.5195	0.5112	0.4941
DBSCAN	0.8678	0.7104	0.8574	0.7712
OPTICS	0.7232	0.7031	0.9562	0.9251
MkNNG-P	0.8990	0.8623	0.9607	0.9408

4.2 Experiment

In this subsection, in order to evaluate the effectiveness of MkNNG-P clustering algorithms, we present the comparison results of MkNNG-P and three classical clustering algorithms ( $k$ -means, DBSCAN, OPTICS).

We use two real-world data sets Compound and Jain (Obtained from University of Eastern Finland website1

¹
http://cs.joensuu.fi/sipu/datasets/.

) to evaluate and compare our algorithm. In order to observe the clustering quality, the experiment uses two-dimensional data to cluster. These data sets representing some difficult clustering instances because they contain clusters with different sizes, varying densities and different shapes.

To quantify the performance of MkNNG-P, we measure the clustering results with Adjusted Rand Index (ARI) and Normalized Mutual Information (NMI). The corresponding ARI and NMI values of each algorithm on data sets Compound and Jain are listed in Table 2.

Compound is a very typical data set, which can represent many representative problems encountered during the clustering process. The true cluster structure of Compound is shown in Fig. 5. The two clusters on the upper left of it represent the spherical clusters and the density of the data points in the same cluster is not uniform; the external cluster at the lower left indicates that there is no clear central point in the cluster; the cluster on the right shows two different clusters with uneven density. Therefore, Compound is a data set containing multiple clusters of arbitrary shapes and uneven densities.

Figure 5.

A comparison of clustering results generated by $k$ -Means, DBSCAN, OPTICS, MkNNG-P in dataset Compound.

Figure 6.

A comparison of clustering results generated by $k$ -Means, DBSCAN, OPTICS, MkNNG-P in dataset Jain.

Figure 5 shows a comparison of clustering results generated by $k$ -means, DBSCAN, OPTICS, and MkNNG-P on dataset Compound. It can be seen that DBSCAN is not effective in the case of clustering different densities, OPTICS cannot separate the very dense cores of the graph from their sparse neighborhoods, and $k$ -means cannot obtain the ideal clustering result because the cluster center point cannot be correctly identified MkNNG-P can cluster most of the points correctly and only have errors in identify individual points. It can also be seen from Table 2 that MkNNG-P get the best ARI and NMI. Therefore, on Compound, the clustering effect of MkNNG-P is superior to three comparison algorithms.

The true cluster structure of Jain is shown in Fig. 6. It contains two non-spherical clusters, and the clusters at the top are composed of data points with unevenly distributed density. From the clustering results, it can be seen that $k$ -Means can’t distinguish two non-spherical clusters, and DBSCAN does not work well when clustering non-uniform density clusters. OPTICS and MkNNG-P can get the correct results. The corresponding ARI and NMI values in Table 2 prove this conclusion.

The above experimental results show that, in many cases, MkNNG-P algorithm is superior to the comparison algorithms. It can obtain good clustering results in different types of data sets including convex shapes, Non-convex shape, arbitrary shape, uniform density and various densities.

Figure 7.

A comparison of clustering results generated by different parameter $k$ on dataset Compound.

4.3 Parameter analysis

Different from the $k$ -means algorithm, MkNNG-P algorithm does not need to preset the number of clusters. MkNNG-P algorithm only needs one parameter $k$ , which is the number of nearest neighbors. The value of $k$ determines the number of clusters and the quality of clustering, so determining a suitable $k$ is a key point for a successful MkNNG-P algorithm.

Obviously, when $k=$ 0, there is no MkMN in MkNNG, and each object is a single cluster. In this way, the data set containing $n$ objects is clustered into $n$ clusters. As the value of $k$ increases, the number of clusters decreases. When $k=n-1$ , in, the degree of each vertex is $n-1$ , so that MkNNG is a strongly-connected graph. Therefore, the data set is clustered into one cluster.

With the change of the parameter $k$ , the clustering results in data set Compound are shown in Fig. 7. It can be seen that the clustering result changes as the value of $k$ changes from 5 to 20. When $k=$ 5, the data set compound is divided into many small clusters. As the value of $k$ increases, some small clusters are gradually merged into large ones. When $k=$ 15, a more accurate clustering results can be obtained. When $k=$ 20, some clusters maybe merged incorrectly.

Through further research, we found that when the value of $k$ is small, the data will be clustered into a large number of small clusters, but it will not be misclassified. As the $k$ increases, the small clusters merge into large clusters. This property helps the user to determine the best $k$ value based on the result of the gradual change. In general, the value of $k$ varies depending on different practical applications. For data with relatively uniform distribution, $k$ takes a smaller value to get a good clustering result. However, for unevenly distributed data, $k$ takes a larger value to get good clustering results. In practice, the value of $k$ varies depending on the actual application, so entering the appropriate value $k$ requires some field experience. In this case, you need to manually select the optimal clustering result.

5. Conclusions

This paper provides new ideas and methods for cluster analysis. In order to overcome the shortcomings of traditional clustering algorithms and further improve the computational efficiency, this paper combines the graph theory and $P$ system to propose a cell-like $P$ system with multi-promoters and multi-inhibitors named MkNNG-P system. And then based on it, an effective MkNNG-P clustering algorithm is proposed. Depending on the analysis and experiments we can conclude that MkNNG-P clustering algorithm has the following advantages: (1) It has very low time complexity and can great improve computational efficiency. (2) It does not need to preset the number of clusters and only needs one input parameter $k$ -the number of neighbors of each object need to be considered. (3) It is robust to outliers. (4) It can find a variety of clusters with different densities and different shapes. (5) It can cluster data in high-dimensional data set.

In this paper, the graph-based clustering method is combined with the cell-like $P$ system containing promoters and inhibitors to solve the clustering problem. This method is a new attempt in applications of membrane system. In the future, we will combine the graph theory with other membrane systems to improve accuracy and efficiency of clustering.

Footnotes

Acknowledgments

Project is supported by National Natural Science Foundation of China (nos. 61472231, 61502283, 61640201, 61602284, 61602285, 61602282, and ZR2016AQ21).

References

Song

Pérez-Jiménez

M.J.

and Pan

, Computational efficiency and universality of timed P systems with membrane creation, Soft Computing 9(11) (2015), 3043–3053.

Song

Zhang

and Pan

, Tissue-like P systems with evolutional symport/antiport rules, Information Sciences 378 (2017), 177–193.

Martín-Vide

Păun

Pazos

et al., Tissue P systems, Theoretical Computer Science 296(2) (2003), 295–326.

Hruschka

E.R.

and Freitas

A.A.

, A survey of evolutionary algorithms for clustering, IEEE Transactions on Systems Man and Cybernetics Part C Applications and Reviews 39(2) (2009), 133–155.

Păun

, Computing with membranes, Journal of Computer and System Sciences 61(1) (2000), 108–143.

Paun

Rozenberg

and Salomaa

, Membrane computing with external output, Fundamenta Informaticae 41(3) (1998), 313–340.

Singh

and Deep

, A new membrane algorithm using the rules of Particle Swarm Optimization incorporated within the framework of cell-like P-systems to solve Sudoku, Applied Soft Computing 45 (2016), 27–39.

Zhang

et al., A Population-membrane-system-inspired evolutionary algorithm for distribution network reconfiguration, Chinese Journal of Electronics 23(3) (2014), 437–441.

Zhang

and Pan

, A survey of membrane computing as a new branch of natural computing, Chinese Journal of Computers 33(2) (2010), 208–214.

10.

Peng

and Wang

, Optimal multi-level thresholding with membrane computing, Digital Signal Processing 37(1) (2015), 53–64.

11.

Peng

Wang

and Pérez-Jiménez

M.J.

, An unsupervised learning algorithm for membrane computing, Information Sciences 304 (2015), 80–91.

12.

Huang

, Research on Membrane Computing Optimization Methods , Ph.D. Dissertation, Dept Control Science and Engineering, Zhejiang Univ, Hangzhou, China, 2007.

13.

Martinez-del-Amor

M.A.

Garcia-Quismondo

and Macias-Ramos

L.F.

, Simulating P systems on GPU devices: A survey, Fundamenta Informaticae 136(3) (2015), 269–284.

14.

Ionescu

Păun

and Yokomori

, Spiking neural P systems, Fundameta Informaticae 71(2–3) (2006), 279–308.

15.

Sato

Anada

and Tsutsumi

, Formulations of patterns by a graph model for the game of Go, Journal of Computational Methods in Sciences and Engineering 17(1) (2017), 1–11.

16.

Altman

N.S.

, An introduction to kernel and nearest-neighbor nonparametric regression, The American Statistician 46(3) (1992), 175–185.

17.

Ding

and Boykin

, A framework for distributed nearest neighbor classification using Hadoop, Journal of Computational Methods in Sciences and Engineering 17 (2016), 1–9.

18.

Freund

Kari

and Oswald

, Computationally universal P systems without priorities: Two catalysts are sufficient, Theoretical Computer Science J 330(2) (2005), 251–266.

19.

Freund

Oswald

and Paun

, Catalytic and purely catalytic P system and P automata: Control mechnisms for obtaining computational completeness, in: 14th International Conference, CMC14, 2013, pp. 317–320.

20.

Luxburg

U.V.

, A tutorial on spectral clustering, Statistics and Computing 17(4) (2007), 395–416.

21.

Yuan

Zhang

and Pérez-Jiménez

M.J.

, P systems based computing polynomials: Design and formal verification, Natural Computing 15(4) (2016), 591–596.

22.

Liu

and Xue

, A cluster splitting technique by hopfield networks and P systems on simplices, Neural Processing Letters 24(1) (2017), 1–24.

23.

Liu

Zhao

and Sun

, Tissue P systems with cooperating rules, Chinese Journal of Electronics 27(2) (2018), 324–333.

24.

Zeng

Zhang

and Pan

, Homogeneous spiking neural P systems, Fundamenta Informaticae 97 (2009), 275–294.

25.

Zhao

Liu

and Yan

, A grid-based chameleon algorithm based on the tissue-like P system with promoters and inhibitors, Journal of Computational and Theoretical Nanoscience 13(6) (2016), 3652–3658.

26.

Jia

Z.W.

Cui

and Yu

H.J.

, Graph-clustering method based on the dissimilarity, Journal of Shanxi Agricultural University 29(3) (2009), 284–288.

An improved MkNN clustering algorithm based on graph theory and membrane computing

Abstract

Keywords

1. Introduction

2. The mutual k -nearest neighbors graph clustering algorithm

2.1 Preliminary

2.1.1 Definition 1: k -nearest neighbors (kNN)

2.1.2 Definition 2: Mutual k -nearest neighbors (MkNN)

2.1.3 Definition 3: k -nearest neighbor graph (kNNG)

2.1.4 Definition 4: Mutual k -nearest neighbor graph (MkNNG)

3.1 Cell-like P system with promoters and inhibitors

3.3.1 Calculate the dissimilarity (distance) between any two nodes

3.3.2 Obtained k -nearest neighbors for each object

3.3.3 Cluster the mutual k -nearest neighbors into the same cluster

4.1 Complexity analysis

Table 1 Time complexities of several classical algorithms

1 http://cs.joensuu.fi/sipu/datasets/.

5. Conclusions

Footnotes

Acknowledgments

References

2. The mutual $k$ -nearest neighbors graph clustering algorithm

2.1.1 Definition 1: $k$ -nearest neighbors (kNN)

2.1.2 Definition 2: Mutual $k$ -nearest neighbors (MkNN)

2.1.3 Definition 3: $k$ -nearest neighbor graph (kNNG)

2.1.4 Definition 4: Mutual $k$ -nearest neighbor graph (MkNNG)

3.1 Cell-like $P$ system with promoters and inhibitors

3.3.2 Obtained $k$ -nearest neighbors for each object

3.3.3 Cluster the mutual $k$ -nearest neighbors into the same cluster

Table 1
Time complexities of several classical algorithms

¹
http://cs.joensuu.fi/sipu/datasets/.