The DBSCAN Clustering Algorithm on P Systems

The DBSCAN Clustering Algorithm on P Systems Gy¨orgy Vaszil Department of Computer Science, Faculty of Informatics University of Debrecen Kassai ´ut 26, 4028 Debrecen, Hungary [email protected] Summary. We show how to implement the DBSCAN clustering algorithm (Density Based Spatial Clustering of Applications with Noise) on membrane systems using evolution rules with promoters and priorities. 1 Introduction Clustering is the process of partitioning elements of a dataset according to some similarity measure in such a way that elements in the same cluster are similar, elements in different clusters are dissimilar. Clustering analysis is widely used in several areas of data mining as a tool to discover implicit patterns and deduce knowledge based on the data, or it can also be used for preprocessing before the application of other algorithms. The reader is referred to [3] for more details about clustering, and the area of data mining in general. The density based clustering of applications with noise (DBSCAN) clustering algorithm was introduced in [2]. It clusters data points based on density (a point is dense if it has many neighbors within a given radius. The algorithm can be summarized in the following steps: Input: A set of points, the neighborhood radius , and the density threshold MinPts. 1. Mark all points “univisited”. 2. Pick an unvisited point p, •change its mark to “visited”, and •count the number of points in its neighborhood to see if it is a core point, that is, if the number of points in its neighborhood is at least MinP ts. •If pis not a core point, mark it as “noise”, otherwise create Cas a new cluster and add pto C, together with those points in its neighborhood which do not belong to any cluster yet. 172 Gy¨orgy Vaszil 3. Pick an unvisited point p0in C •change the mark of p0to “visited”, •count the number of points in its neighborhood to see if it is a core point. •If p0is a core point, add those points to Cin its neighborhood which do not belong to any cluster yet. •If there are unvisited points in C, go back to 3. 4. If there are unvisited points in the data set, go back to 2. Output: The clustering result. In the following we intend to give an implementation of this algorithm in terms of P systems. The system will use evolution rules with promoters and priorities. Our goal is to exploit the parallelism of P systems in order to parallelize, and thus, to speed up the DBSCAN algorithm which in its original version works with O(n2) time complexity on a sequential machine (where nis the number of points to be clustered). On P systems, the running time can be reduced to O(n). Ours is not the only proposal for clustering with P systems. As examples, see [4], or see [9] for a so called k-nearest base clustering algorithm on P systems with active membranes, and [8] for clustering with splicing P systems. Even a DBSCAN algorithm implementation was already presented in [11], we believe however, that our present proposal is conceptually simpler. 2 Preliminaries and Definitions Let Obe a finite nonempty set (the set of object) and Nbe the set of non-negative integers. A multiset M(or an multiset Mfor short), over Ois a pair (O, f), where f:O→Nis mapping which gives the multiplicity of each object a∈O. The set supp(M) = {a∈O|f(a)>0}is called the support of M. If supp(M) = ∅, then Mis the empty multiset. If a∈supp(M), then a∈M, and a∈nMif f(a) = n. In the following we represent a multiset Mover O={a1, . . . , ak}by the string aM(a1) 1. . . aM(ak) k(or any of its permutations). Membrane systems, or P systems, were introduced in [5] as computing models inspired by the functioning of the living cell. The main component of such a system is a membrane structure with membranes enclosing regions as multisets of objects. Each membrane has an associated set of operators working on the objects contained by the region. These operators can be of different types, they can change the objects present in the regions or they can provide the possibility of transferring the objects from one region to another one. The evolution of the objects inside the membrane structure from an initial configuration to a final configuration corresponds to a computation having a result which is derived from some properties of the final configuration. Several variants of the basic notion have been introduced and studied proving the power of the framework, see the monograph [6] for a comprehensive introduc- The DBSCAN Clustering Algorithm on P Systems 173 tion, the handbook [7] for a summary of notions and results of the area, and the volumes [1, 10] for various applications. An n+ 3-tuple Π= (O, w1, . . . , wn, R1, . . . , Rn, ρ) is a Psystem of degree n, where •Ois a finite set called the alphabet of objects Π; •wi, 1 ≤i≤n, is a finite multiset of objects containing the initial contents of compartment iof Π; •Ri, 1 ≤i≤n, is a finite set of rules of the form u→vor u→v|αwith u, α ∈O∗and v∈O∪ {here, in, out}; •ρ⊂R×Ris a priority relation defined on the rules of R=S1≤i≤nRiwhich may also be empty. For a P system Π= (O, w1, . . . , wn, R1, . . . , Rn, ρ) as above, an n-tuple c= (u1, . . . , un) with ui∈O∗for each i, is called a configuration of Πand c0= (w1, . . . , wn) is called its initial configuration. The multisets u1, . . . , unare also called the contents of compartments 1, . . . , n, in configuration c. A P system changes its configurations by applying its rules in the so-called maximally parallel manner. A multiset of rules from Rifor some 1 ≤i≤n, as given above, is applicable to a configuration c, if and only if the union of the multisets on the lefthand sides of the rules is a submultiset of ui, the contents of the ith region. As a result of applying the rules to c, each object of the multisets on the righthand sides of the rules replace the objects on the lefthand side. Moreover, if the objects are moved to the respective neighboring regions according to the target indicators here, in, out. Rules multisets are applied in all regions in parallel, producing a series of configuration changes. We say that the configuration c0= (v1, . . . , vn) of Πis obtained directly from c= (u1, . . . , un) by applying the rules in a maximally parallel manner, if the rule multisets applied in the regions are maximal, that is, by adding any rule to the multiset, they are not applicable simultaneously any more. A rule of the form x→y|αis applicable only if α∈O∗(the promoter mutiset) is a submutiset of the respective region. When the priority relation ρis nonempty, we denote by r1> r2if (r1, r2)∈ρ, that is, if a rule r1has higher priority than r2. In such a case, r2can only be applied to configurations where r1is not applicable. A sequence of configurations c0, c1, . . . of Π, obtained directly from each other and starting from the initial configuration, is called a computation. The computation halts if no rule can be applied in the current configuration. The result of a halting computation are the multisets of objects in the compartments at halting. 3 Implementing the DBSCAN Algorithm In order to perform the clustering algorithm, let us construct a P system Π= (O, [ ], w, R, ρ) with 174 Gy¨orgy Vaszil O={pi, p0 i, pi,j?, pi,j , p0 i,j, pcr i, pns i, pns i,j?, pcr i,j, pncr i,j |1≤i, j ≤n} ∪ {Ei, Hi|1≤i≤n}∪{A, B, C, D, F, F 0, F00}. The objects of the form pirepresent the npoints of the data set. We assume that we have a distance function d:{p1, . . . , pn}2→N. The initial contents of the system is the multiset w=Ap1. . . pn, corresponding to the npoints, and a synchronizing symbol A. Now we present the rules of Rand at the same time, describe the functioning of the system. Let R=Rpick ∪Rcehck ∪Rmark ∪Rcheck2∪Rmark2, and let us describe these rule sets as follows. Rpick ={Api→Bp0 i|1≤i≤n}. Using the single occurrence of A, the application of one of these rules picks a point pifor some 1 ≤i≤nby changing it to its primed version p0 i. Now, in the presence of p0 i, the system checks whether the ith point is dense, that is, whether it has more than MinPts points in its neighborhood. This is achieved by the rules Rcheck ={pk→Eipk,i?|Bp0 i, pncr k,j →Eipncr k,j |Bp0 i, pns k→Eipns k,i?|Bp0 i|for 1≤i, j, k ≤n, such that d(pi, pk)< }∪{B→C} where d(pi, pk) denotes the distance between the locations of the ith and the kth points. The application of these rules produce a number of Eiobjects which is equal to the number of points that are in the neighborhood of the ith point. Now we mark the point corresponding to p0 icore or non-core, depending on the number of its neighbors with the following rules. If m=MinPts, then we have Rmark ={p0 i→pcr i|C(Ei)m> p0 i→pns i|C|1≤i≤n} ∪ {pj,i?→p0 j,i|Dpcr i, pns j,i?→p0 j,i|Dpcr i|1≤i, j ≤n} ∪ {pj,i?→pj|Dpns i, pns j,i?→pns j|Dpns i|1≤i, j ≤n} ∪ {Ei→ε|C|1≤i≤n}∪{C→D, D →F} where the symbol >shows the priority among the first group of rules in Rmark. The rules here are used for two consecutive steps: First, the chosen point is marked core or noise (based the number of points in its neighborhood) by changing p0 i to pcr ior to pns idepending on the number of Eisymbols that are present (these were created in the previous step, their number corresponds to the number of neighbors). Second, if the point is marked core, its neighborhood is also added to this cluster (the cluster denoted by i). The next group of rules serves to see if the recently created cluster (cluster i) can be expanded further. The DBSCAN Clustering Algorithm on P Systems 175 Rcheck2={pcr j,i →Hipcr j,i|F p0 k,i , pncr j,i →Hipncr j,i |F p0 k,i , pns j→Hipns j,i?|F p0 k,i , pj→Hipj,i?|F p0 k,i |for 1 ≤i, j, k ≤n, such that d(pj, pk)< } ∪ {F→F0}. These rules examine the neighborhood of the kth point which has recently been added to the cluster denoted by i. The number of Hisymbols is the same as the number of points in the neighborhood of point (k). The next group of rules is the following. Rmark2={p0 k,i →pcr k,i|F0(Hi)m> p0 k,i →pncr k,i |F0|1≤i, k ≤n} ∪ {pj,i?→p0 j,i|F00 pcr k,i , pns j,i?→p0 j,i|F00 pcr k,i |1≤i, j, k ≤n} ∪ {pj,i?→pj|F00 pncr k,i , pns j,i?→pns j|F00 pncr i|1≤i, j ≤n} ∪ {Hi→ε|F0|1≤i≤n}∪{F0→F00} {F00 →F|p0 k,i > F 00 →A|1≤i, k ≤n}, where m=MinPts, as before. Similarly to Rmark, these rules decide whether the cluster denoted by ishould be expanded with the elements of the neighborhood of point (k). If the number of neighbors is sufficient, they are added to the cluster, and also marked for further investigation. If there are points which are newly added to the cluster, that is, if further neighborhood checks are necessary, then the symbol F0is changed to F00, and then back to F, so the rules in Rcheck2become applicable again, and the checking process can repeated. If no new points are added to the cluster, F00 is changed to A, so the rules in Rcheck are activated, and the search for additional clusters can start with the identification of a yet unclassified point by Rpick. To see how the system Πoperates, consider the initial configuration Ap1. . . pn. By applying a rule Api→Bp0 i∈Rpick for some 1 ≤i≤n, a not yet classified point (i) is chosen from the point set (1),...,(n), and we obtain Bp1. . . p0 i. . . pn. To show how the system works, we start with a more general case Bx1. . . p0 i. . . xn, where xi∈ {pi, pns i, pcr i, pcr i,j, pncr i,j }. Now, because Bis present, the rules of Rcheck are applicable, so we get C . . . p0 i. . . y1Ei. . . ylEi. . . where yj∈ {pk,i?, pns k,i?|for some 1 ≤k≤n}, 1 ≤j≤l. All symbols which correspond to unclassified points or noise points (k) in the neighborhood of 176 Gy¨orgy Vaszil point (i) are marked as candidates for inclusion in the same cluster as (i) (denoted by the index i?). If the number of neighbors (equal to the number of Eisymbols) is not sufficient (less than MinPts), we get D . . . pns i. . . y1. . . yl. . . , and then Fx1. . . pns i. . . xn by the rules of Rmark. Now Fis changed to F0,F00, and then back to A, when the rules of Rpick become applicable again, and the system continues with choosing an other point for examination. Otherwise, if the number of neighbors of point (i) are sufficient, we get D . . . pcr i. . . y1. . . yl. . . , and then F . . . pcr i. . . p0 X1,i . . . p0 Xl,i . . . , where 1 ≤Xj≤n, 1 ≤j≤l, marking the point (i) as core point, and marking its neighbors as members of the cluster denoted by i. Now, the newly added points (X1),...,(Xl), corresponding to the symbols p0 X1,i, . . . , p0 Xl,i have to be checked, which is done by the rules of Rcheck2If the  neighborhood of a point (k) contains a sufficient number of points, then similarly to Rcheck, the rules of Rcheck2introduce a sufficient number of Hisymbols for the rule p0 k,i →pcr k,i to be applicable, and point (k) is marked as a core point, denoted by a corresponding symbol pcr k,i. Otherwise, if the number of neighbors is not sufficient, then point (k) is marked as non-core, denoted by the symbol pncr k,i introduced by the rule p0 k,i →pncr k,i . These checks are executed in parallel for all p0 Xk,i, resulting in marking some of them core, some of them non-core, and priming all neighbors of core points in two computational steps, using the rules in Rcheck2and Rmark2. If the result contains primed points, that is, points that have to be checked by counting the number of their neghbors, then F00 is rewritten to F, so the process can start all over again, otherwise it is rewritten to A, meaning that the cluster denoted by icannot be expanded any more, the search for new clusters can begin by picking a new point using the rules of Rpick. If all points are classified, then no rule of Rpick can be used, the system halts in a configuration containing the symbol A, and with all points (i),1≤i≤n, having a corresponding symbol, which is either •pcr i: point (i) is a core point, belonging to the cluster denoted by i, •pcr i,j : point (i) is a core point, belonging to the cluster denoted by j, •pncr i,j : point (i) is a non-core point, belonging to the cluster denoted by j, •pns i: point (i) is a noise point, it does not belong to any cluster. The DBSCAN Clustering Algorithm on P Systems 177 4 Conclusion We have shown how to implement the DBSCAN clustering algorithm on P systems. The model we used worked with evolution rules, promoters and priorities, Due to the parallel nature of P systems, our implementation has a time complexity of O(n) which is clear improvement compared to the time complexity of O(n2) of a sequential DBSCAN implementation. Our P system implementation presented in in this paper is not the first one, but we believe that it is conceptually more simple than the implementation presented in [11]. Considering the parallelity of our approach, the points of the dataset are examined by the algorithm one-by-one, but the number of neighbors of the examined points is calculated in parallel. Moreover, all points examined in step 3 of the algorithm (see the introduction for the numbering of the steps of the algorithm) are examined in parallel which further reduces the time complexity of the P system implementation. An interesting challenge would be to find a way in which the parallelity of the algorithm can further be increased, and thus, the time complexity further reduced. Acknowledgments This research is supported in part by project no. K 120558 of the National Research, Development and Innovation Fund of Hungary, financed under the K 16 funding scheme, and by the EFOP-3.6.1-16-2016-00022 project, co-financed by the European Union and the European Social Fund. References 1. Ciobanu, G., P´erez-Jim´enez, M.J., P˘aun, G. (eds.): Applications of Membrane Computing. Natural Computing Series, Springer (2006) 2. Ester, M., Kriegel, H.P., Sander, J., Xu, X.: A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise. In: Proceedings of the Second International Conference on Knowledge Discovery and Data Mining. pp. 226–231. KDD’96, AAAI Press (1996) 3. Han, J., Kamber, M., Pei, J.: Data Mining: Concepts and Techniques. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 3rd edn. (2011) 4. Jiang, Y., Peng, H., Huang, X., Zhang, J., Shi, P.: A novel clustering algorithm based on p systems. International journal of innovative computing, information & control: IJICIC 10, 753–765 (01 2014) 5. P˘aun, G.: Computing with membranes. Journal of Computer and System Sciences 61(1), 108 – 143 (2000) 6. P˘aun, G.: Membrane Computing: An Introduction. Springer-Verlag, Berlin, Heidelberg (2002) 7. P˘aun, G., Rozenberg, G., Salomaa, A.: The Oxford Handbook of Membrane Computing. Oxford University Press, Inc., New York, NY, USA (2010) 178 Gy¨orgy Vaszil 8. Xu, J., Liu, X., Xue, J.: Cluster analysis by a class of splicing p systems. In: Park, J.J.J.H., Pan, Y., Kim, C.S., Yang, Y. (eds.) Future Information Technology. pp. 575–581. Springer Berlin Heidelberg, Berlin, Heidelberg (2014) 9. Xue, J., Liu, X.: A k-nearest based clustering algorithm by P systems with active membranes. JSW 9(3), 716–725 (2014), https://doi.org/10.4304/jsw.9.3.716-725 10. Zhang, G., P´erez-Jim´enez, M.J., Gheorghe, M.: Real-life Applications with Membrane Computing. Springer Publishing Company, Incorporated (2017) 11. Zhao, Y., Liu, X., Li, X.: An improved DBSCAN algorithm based on cell-like P systems with promoters and inhibitors. PLoS ONE 13, e0200751 (Dec 2018)